Stream.count broken when used with Sapp or Slazy nodes #5644
Comments
|
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). |
|
Comment author: @gasche (There was a mistake in the way patch were split, plus a typo in a comment. I just uploaded fixed versions.) |
|
Comment author: @bobzhang Is the semantics correct? let u = [<1;2;3;4>];val u : int LibUtil.Stream.t = Stream.next u;
Stream.count u;
In your toplevel, you could reproduce 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? |
|
Comment author: @bobzhang I also find the lazy evaluation semantics changed since revision 4144 let s = [< '(print_int 3 ); '(print_int 4) >];; before revision 4144(including 4144) |
|
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. |
|
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. |
|
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. |
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
The text was updated successfully, but these errors were encountered: