Lwt: [easy-ish] Tests for Lwt_sequence

[aantron]

Lwt_sequence doesn't have a test suite at all, but it is not immune to potential serious bugs. We should create a test suite for it. See "Workflow" in #385 for how to create a test suite, and how to run coverage analysis. It's fine to add a few tests at a time, and build up a full test suite over several PRs.

Background

Lwt_sequence is a mutable doubly-linked list, like found in most imperative languages. It is written in pure OCaml, i.e. it doesn't involve any C bindings or I/O operations, as elsewhere in Lwt. So, it is pretty easy to work with. Lwt_sequence is heavily used by the I/O layer of Lwt, however, so it is an important module.

Lwt_sequence unfortunately has unnecessary unsafe casts, so it's not model OCaml code. Lwt_sequence is marked deprecated because we want Lwt users not to depend on this module, because Lwt is not a data structures library. We want to make it an internal implementation detail of Lwt. It will remain in Lwt for the foreseeable future, however.

The only thing that makes Lwt_sequence somewhat complicated is that it supports (or tries to support?) removal of elements during traversal [[1](https://github.com/ocsigen/lwt/blob/6649ef6f74fdff417e705e131e5ec31487ea9032/src/core/lwt_sequence.ml#L51)] [[2](https://github.com/ocsigen/lwt/blob/6649ef6f74fdff417e705e131e5ec31487ea9032/src/core/lwt_sequence.ml#L190-L193)]. A really thorough test suite (maybe not from the first PRs) will cover this code. I believe the only way to trigger it is to remove the current node in f, and then remove the next/previous node also. See comments in #405 for details.

The current coverage of Lwt_sequence is something like 42%, but that is almost all due to implicit use of Lwt_sequence during testing of the I/O layer.

[cedlemo]

@aantron, I would like to work on it.

[aantron]

Great, thank you :)

[cedlemo]

@aantron,

I started today and it seems that there are some deprecation warnings that make the tests fail.

File "test/core/test_lwt_sequence.ml", line 24, characters 5-17:
Warning 3: deprecated: module Lwt_sequence
 This module is an implementation detail of Lwt. See
   https://github.com/ocsigen/lwt/issues/361
File "test/core/test_lwt_sequence.ml", line 1:
Error: Some fatal warnings were triggered (1 occurrences)
      ocamlc test/core/test_lwt_sequence.{cmi,cmo,cmt} (exit 2)
(cd _build/default && /home/cedlemo/.opam/4.05.0/bin/ocamlc.opt -w @a-4-29-40-41-42-44-45-48-58-59-60-40 -strict-sequence -strict-formats -short-paths -keep-locs -w +A-40-42 -g -bin-annot -I /home/cedlemo/.opam/4.05.0/lib/bisect_ppx/runtime -I /home/cedlemo/.opam/4.05.0/lib/bytes -I /home/cedlemo/.opam/4.05.0/lib/ocaml -I /home/cedlemo/.opam/4.05.0/lib/ocaml/threads -I /home/cedlemo/.opam/4.05.0/lib/result -I src/core -I src/logger -I src/unix -I test -no-alias-deps -I test/core -o test/core/test_lwt_sequence.cmo -c -impl test/core/test_lwt_sequence.ml)
make: *** [Makefile:21: test] Error 1

[aantron]

@cedlemo, we are suppressing those warnings internally in Lwt like this:

[@@@ocaml.warning "-3"]
module Lwt_sequence = Lwt_sequence
[@@@ocaml.warning "+3"]

See

https://github.com/ocsigen/lwt/blob/c7ad8b33977ecee1943a060ba1303f555e1b5997/src/core/lwt.ml#L377-L384

[aantron]

I'm leaving this open for now, as there are still a couple of conditions to check (make coverage should show some unvisited code, and IIRC this is one of the few ways to trigger it).

[cedlemo]

hum, I have to say that I don't see how to test for example the Lwt_sequence.length reported by the coverage tool:

let length seq =
  let rec loop curr len =
    if curr == seq then
      len
    else
      let node = node_of_seq curr in
      if node.node_active then
        loop node.node_next (len + 1)
      else
        loop node.node_next len
  in
  loop seq.next 0

It is a loop in the length function, I don't have access to it, I can not remove a node while it runs.

There is another thing that blocks me, it is the coverage of the Lwt_sequence.fold_r that indicates that a branch of the function is still not visited. But with the last test, this branch should be visited, the test is for the problem solved by https://github.com/ocsigen/lwt/commit/f180e240994ee77d9ed267b5f096e63b9beafd47#diff-bbb42ff8920b54e9ebe307858bfea58a . here you can see the post where I found a case that generate a bad iteration https://github.com/ocsigen/lwt/pull/536#issuecomment-356952130.

[aantron]

Yeah, it looks like that branch in length should be dead code. We should probably delete it.

I'm not sure why the code you posted before didn't visit that branch (I didn't look deep enough).

For the simple case of deleting the next node, it seems that whether it would be visited anyway depends on the order of evaluation of the arguments in loop node.node_next (f node.node_data acc).

I was able to trigger that code independently of the order of evaluation with this test, by deleting two nodes, the one currently being visited, and the next one. The second deletion doesn't update the next pointer of the current node, because the current node is already deleted and not the previous node of the next node. To me, your code looks like it should accomplish that also, but like I said, I didn't look that deep at why not.

test "fold_l multiple removal" begin fun () ->
    let seq = Lwt_sequence.create () in
    let node_1 = Lwt_sequence.add_r 1 seq in
    let node_2 = Lwt_sequence.add_r 2 seq in
    ignore (Lwt_sequence.add_r 3 seq);
    let product =
      Lwt_sequence.fold_l begin fun v acc ->
        if v <> 1 then
          v * acc
        else begin
          Lwt_sequence.remove node_1;
          Lwt_sequence.remove node_2;
          acc
        end
      end seq 1
    in
    Lwt.return (product = 3)
  end;

[cedlemo]

  test "fold_r with multiple removal" begin fun () ->
   let s = filled_sequence () in
   let acc = Lwt_sequence.fold_r
   (fun v e ->
      (if v = (-1) then
         let n = Lwt_sequence.find_node_r (fun v' -> v' = (-1)) s in
         let _ = Lwt_sequence.remove n in
         let n = Lwt_sequence.find_node_r (fun v' -> v' = (-2)) s in
         let _ = Lwt_sequence.remove n in
         let n = Lwt_sequence.find_node_r (fun v' -> v' = 1) s in
         ignore(Lwt_sequence.remove n)
      );
      v * e
    ) s 1 in
    Lwt.return (acc = 18)
  end;

this test with fold_r visits the last branch. In the previous test, the current node was the last to be removed.

1. the current node n(-1) is set inactive,
   
   
   
   • the node n(-2).next is set to node n(1)
   
   
   • the node n(1).prev is set to node n(-2)
   
   
2. the node n(-2) is set inactive
   
   
   
   • the node n(-3).next is set to node n(1)
   
   
   • the node n(1).prev is set to node n(-3)
   
   
3. the node n(1) is set to inactive
   
   
   
   • the node n(-3).next is set to node n(2)
   
   
   • the node n(2).prev is set to node n(-3)
   
   

then is pass current_node.node_prev (n(-2)) which is inactive because I removed the current node and
its previous node is an inactive node.

In my previous code:

1. the node n(1) is set to inactive
   
   
   
   • the node n(-1).next is set to node n(2)
   
   
   • the node n(2).prev is set to node n(-1)
   
   
2. the node n(-2) is set inactive
   
   
   
   • the node n(-3).next is set to node n(-1)
   
   
   • the node n(-1).prev is set to node n(-3)
   
   
3. the current node n(-1) is set inactive,
   
   
   
   • the node n(-3).next is set to node n(1)
   
   
   • the node n(3).prev is set to node n(-3)
   
   

So that the current node is updated with an active previous node.

I have to check if this set of removals trigger the error of the issue #405.