Lwt: Factor out Lwt_sequence (doubly-linked list)

[aantron]

Lwt_sequence (.mli, .ml) is pretty much an ordinary mutable doubly-linked list. As in the Lwt_pqueue issue (#360), it belongs in the standard library.

Unlike Lwt_pqueue, Lwt_sequence is actually referenced elsewhere in the Lwt API, in two places: Lwt.add_task_r and Lwt.add_task_l. Lwt_sequence will therefore need to stick around, or become a bunch of aliases, even if the stdlib gets a linked list.

Perhaps we should also start gradually deprecating these two functions. Their functionality can be implemented in terms of other Lwt functions, and they seem to be used in few places. I see them in use in:

• fdopen/uwt in several places (OPAM package uwt)
• nojb/ocaml-utp (OPAM package utp)
• ocamllabs/ocamlot
• ANSSI-FR/parsifal

[avsm]

ocamllabs/ocamlot is not in active use, so I've archived that repository

[avsm]

I went ahead and extracted this library into https://github.com/mirage/lwt-dllist so that deprecation warnings can be fixed.

It's called Lwt_dllist to reflect that it's a doubly linked list, and not a sequence (thus avoiding confusion with the Seq module in the standard library if we called it Lwt_seq). The term Dllist is also used in a few other places like Containers to signify this type of data structure.

I didn't call it Lwt_sequence to ease migration -- we just have to search-and-replace Lwt_sequence with Lwt_dllist and can do so immediately without waiting for a new release of Lwt.

If this name and scheme is ok with @mirage/core and @aantron I'll cut a release to opam...

[aantron]

This seems good to me.

[aantron]

We can later add a link to lwt-dllist in the Lwt_sequence deprecation message.

[avsm]

Released Lwt_dllist as v1.0.0 at https://github.com/ocaml/opam-repository/pull/13262

Will start doing the trivial ports of existing uses of Lwt_sequence in Mirage to this.

[toolslive]

What's the plan for:

val exit_hooks : (unit -> unit Lwt.t) Lwt_sequence.t

?

I do need a way to deplete/process the exit hooks, but I honestly don't care about the data structure that contains them.

[aantron]

We need to add accessor-style functions for adding and removing hooks. Adding a hook will return an object of some abstract type, that can later be used to remove that hook.

We'll keep exit_hooks itself around in the API for long after we add these functions, however, so there should be no need to worry about this going away suddenly.

[toolslive]

No worries, but a deprecation warning usually means : "we now have a better way of doing this, and the API you're using will eventually go away.". Alas, here there is no alternative yet, so there's no way to clean up the warning.

[aantron]

Closing this until there is a doubly-linked list in the standard library, or in another library that is likely to be published to system package managers.

I originally wanted to make Lwt depend on lwt-dllist, which is Lwt_sequence factored out of this repo. However, adding more little dependencies seems like a bad idea in light of this comment: https://github.com/ocaml/dune/issues/1847#issuecomment-518007209.

We already strongly discourage usage of Lwt_sequence with deprecation messages, and all exposed Lwt APIs that depend on it are also deprecated, and have alternatives. So, it is effectively an implementation detail.