Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stream.count broken when used with Sapp or Slazy nodes #5644

Closed
vicuna opened this issue Jun 9, 2012 · 7 comments

Comments

Projects
None yet
2 participants
@vicuna
Copy link

commented Jun 9, 2012

Original bug ID: 5644
Reporter: @gasche
Assigned to: @gasche
Status: closed (set by @xavierleroy on 2015-12-11T18:21:07Z)
Resolution: fixed
Priority: high
Severity: minor
Target version: 4.00.0+dev
Fixed in version: 4.00.0+beta2/+rc1
Category: standard library
Related to: #3492
Monitored by: mehdi @diml

Bug description

When using one of the Stream.{i,l}{cons,app} or Stream.slazy functions, the current Stream implementation does not preserve the internal stream counter, which is used by streams generated using Stream.from, in particular Stream.of_string. This bug was found by Michaël Sghaïer.

Attached is a proposed patch to fix the issue, with a corresponding test suite. The fix is more complex that I would have wished ('cons' is trivial to fix, just use (s.count - 1) instead of 0 as the new count, but Sapp/Slazy is more delicate) and I would therefore appreciate feedback.

In particular, Stream is heavily used in Camlp4, but I'm not familiar with Camlp4 bootstrap process so I did not test that it didn't affect it (I tried "sh build/bootstrap.sh" which did not seem to complain in any specific way). In particular, I would be interest in help on spotting potential performance regressions.

Steps to reproduce

let test_icons () =
let s = Stream.of_string "ab" in
(* let s = Stream.of_list ['a'; 'b'] in )
let s = Stream.icons 'c' s in
assert (Stream.next s = 'c');
assert (Stream.next s = 'a'); (
assert failure !? *)
()

let test_lcons () =
let s = Stream.of_string "ab" in
(* let s = Stream.of_list ['a'; 'b'] in )
let s = Stream.lcons (fun () -> 'c') s in
assert (Stream.next s = 'c');
assert (Stream.next s = 'a'); (
assert failure !? *)
()

let test_iapp () =
let s = Stream.of_string "ab" in
(* let s = Stream.of_list ['a'; 'b'] in )
let s = Stream.iapp (Stream.of_list ['c']) s in
assert (Stream.next s = 'c');
assert (Stream.next s = 'a'); (
assert failure !? *)
()

let test_lapp () =
let s = Stream.of_string "ab" in
(* let s = Stream.of_list ['a'; 'b'] in )
let s = Stream.lapp (fun () -> Stream.of_list ['c']) s in
assert (Stream.next s = 'c');
assert (Stream.next s = 'a'); (
assert failure !? *)
()

let test_slazy () =
let s = Stream.of_string "ab" in
assert (Stream.next s = 'a');
let s = Stream.slazy (fun () -> s) in
assert (Stream.next s = 'b');
Stream.empty s;
()

let () =
test_icons ();
test_lcons ();
test_iapp ();
test_lapp ();
test_slazy ();
()

File attachments

@vicuna

This comment has been minimized.

Copy link
Author

commented Jun 9, 2012

Comment author: @gasche

Based on the work to fix this bug, I have a second patch that attempts to simplify Stream's implementation by collapsing together the two memoization layers present (one for Sapp, one for Sgen).
The result is definitely simpler but, as it says, "if it ain't broke, don't fix it": I don't suggest this second patch be merged upstream directly, but would still welcome feedback.

@vicuna

This comment has been minimized.

Copy link
Author

commented Jun 10, 2012

Comment author: @gasche

(There was a mistake in the way patch were split, plus a typo in a comment. I just uploaded fixed versions.)

@vicuna

This comment has been minimized.

Copy link
Author

commented Nov 21, 2012

Comment author: @bobzhang

Is the semantics correct?

let u = [<1;2;3;4>];

val u : int LibUtil.Stream.t =

Stream.next u;

  • : int = 1

Stream.count u;

  • : int = -2

In your toplevel, you could reproduce
let u = [<'1;'2;'3;'4>];;
Stream.next u;;
Stream.count u;;

It's problematic since the patch of icons seems to incorrect, can you upload the initial error case of Stream.count when concat two streams?

@vicuna

This comment has been minimized.

Copy link
Author

commented Nov 21, 2012

Comment author: @bobzhang

I also find the lazy evaluation semantics changed since revision 4144

let s = [< '(print_int 3 ); '(print_int 4) >];;
let t = [< s; s>];;

before revision 4144(including 4144)
Stream.iter ignore t will print 3;4;3;4
after 4144
only 3;4 was printed

@vicuna

This comment has been minimized.

Copy link
Author

commented Dec 3, 2012

Comment author: @gasche

I can indeed reproduce the problem; I'll try to see if this can be fixed, or is in conflict with the change of behavior this patch implemented (and in this case, which is most important; I think the lazy evaluation semantics must not change). I may have to revert the change.

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 21, 2013

Comment author: @gasche

So I did more work on the problem.

My conclusion is that trying to fix the "count" behavior so that of_string would be called with count 0 upwards was the bad way to look at the problem. There is essentially no way to get "count" to behave in a really satisfying way in presence of concatenation and lazy streams, and the solution is not to rely on this value in Stream.of_string.

I reverted the previous patch and implemented this simpler approach. It may be the case that some parts of the previous work helped with deeper issues in the Stream implementation, but the cost in term of possible regressions is too high. Let's keep the code as working as it previously was, and fix the visible issue.

@vicuna

This comment has been minimized.

Copy link
Author

commented Jul 21, 2013

Comment author: @gasche

I now consider this issue resolved: there should be no regression, and the testsuite I provided "obviously" passes (because I fixed another part of the equation). Do tell me (quickly!) if there are remaining problems with the change.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.