Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0005644OCamlOCaml standard librarypublic2012-06-09 13:042013-07-21 22:13
Reportergasche 
Assigned Togasche 
PriorityhighSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version 
Target Version4.00.0+devFixed in Version4.00.0+beta2/+rc1 
Summary0005644: Stream.count broken when used with Sapp or Slazy nodes
DescriptionWhen 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 Reproducelet 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 ();
  ()
TagsNo tags attached.
Attached Filespatch file icon 0001-Fix-a-count-concat-bug-for-Stream-i-l-cons-app-and-s.patch [^] (9,870 bytes) 2012-06-10 10:15 [Show Content]
patch file icon 0002-simplify-stdlib-stream.ml-by-collapsing-two-memoizat.patch [^] (3,594 bytes) 2012-06-10 10:16 [Show Content]

- Relationships
related to 0001284closed Fix offered for "illegal stream concatenation" in Stream 

-  Notes
(0007533)
gasche (developer)
2012-06-09 13:11

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.
(0007536)
gasche (developer)
2012-06-10 10:16

(There was a mistake in the way patch were split, plus a typo in a comment. I just uploaded fixed versions.)
(0008536)
hongboz (developer)
2012-11-21 01:29
edited on: 2012-11-21 01:31

Is the semantics correct?

# let u = [<1;2;3;4>];
val u : int LibUtil.Stream.t = <abstr>
# 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?

(0008537)
hongboz (developer)
2012-11-21 04:32

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
(0008556)
gasche (developer)
2012-12-03 15:06

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.
(0009819)
gasche (developer)
2013-07-21 22:12

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.
(0009820)
gasche (developer)
2013-07-21 22:13

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.

- Issue History
Date Modified Username Field Change
2012-06-09 13:04 gasche New Issue
2012-06-09 13:04 gasche Status new => assigned
2012-06-09 13:04 gasche Assigned To => guesdon
2012-06-09 13:04 gasche File Added: 0001-Fix-a-count-concat-bug-for-Stream-i-l-cons-app-and-s.patch
2012-06-09 13:04 gasche Assigned To guesdon =>
2012-06-09 13:04 gasche Status assigned => new
2012-06-09 13:07 gasche Relationship added related to 0001284
2012-06-09 13:11 gasche Note Added: 0007533
2012-06-09 13:11 gasche File Added: 0002-simplify-stdlib-stream.ml-by-collapsing-two-memoizat.patch
2012-06-10 10:14 gasche File Deleted: 0001-Fix-a-count-concat-bug-for-Stream-i-l-cons-app-and-s.patch
2012-06-10 10:15 gasche File Deleted: 0002-simplify-stdlib-stream.ml-by-collapsing-two-memoizat.patch
2012-06-10 10:15 gasche File Added: 0001-Fix-a-count-concat-bug-for-Stream-i-l-cons-app-and-s.patch
2012-06-10 10:16 gasche File Added: 0002-simplify-stdlib-stream.ml-by-collapsing-two-memoizat.patch
2012-06-10 10:16 gasche Note Added: 0007536
2012-06-26 18:15 doligez Priority normal => high
2012-06-26 18:15 doligez Status new => confirmed
2012-06-26 18:15 doligez Category OCamldoc => OCaml standard library
2012-07-09 14:52 doligez Target Version => 4.00.0+dev
2012-07-10 12:03 gasche Status confirmed => resolved
2012-07-10 12:03 gasche Fixed in Version => 4.00.0+beta2/+rc1
2012-07-10 12:03 gasche Resolution open => fixed
2012-07-10 12:03 gasche Assigned To => gasche
2012-11-21 01:29 hongboz Note Added: 0008536
2012-11-21 01:31 hongboz Note Edited: 0008536 View Revisions
2012-11-21 04:32 hongboz Note Added: 0008537
2012-11-21 04:34 hongboz Status resolved => feedback
2012-12-03 15:06 gasche Note Added: 0008556
2012-12-03 15:06 gasche Status feedback => assigned
2013-07-21 22:12 gasche Note Added: 0009819
2013-07-21 22:13 gasche Note Added: 0009820
2013-07-21 22:13 gasche Status assigned => resolved


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker