`Fix.DataFlow`

This module performs a **forward data flow analysis** over a (possibly cyclic) directed graph. Like `Fix.Fix`

, it computes the least function of type `variable -> property`

that satisfies a fixed point equation. It is less widely applicable than `Fix.Fix`

, but, when it is applicable, it can be both easier to use and more efficient. It does not perform dynamic dependency discovery. The submodule `Fix.DataFlow.ForCustomMaps`

is particularly **tuned for performance**.

`Run`

requires a type `variable`

that is equipped with an implementation of imperative maps, a type `property`

that is equipped with `leq`

and `join`

functions, and a data flow graph whose edges describe the propagation of properties. It performs a forward data flow analysis and returns its result.

`module ForOrderedType (T : sig ... end) (P : sig ... end) (G : sig ... end) : sig ... end`

`ForOrderedType`

is a special case of `Run`

where it suffices to pass an ordered type `T`

as an argument. A reference to a persistent map is used to hold the memoization table.

`module ForHashedType (T : sig ... end) (P : sig ... end) (G : sig ... end) : sig ... end`

`ForHashedType`

is a special case of `Run`

where it suffices to pass a hashed type `T`

as an argument. A hash table is used to hold the memoization table.

`module ForIntSegment (K : sig ... end) (P : sig ... end) (G : sig ... end) : sig ... end`

`ForIntSegment`

is a special case of `Run`

where the type of variables is the integer segment `[0..n)`

. An array is used to hold the table.

`module ForCustomMaps (P : sig ... end) (G : sig ... end) (V : sig ... end) (B : sig ... end) : sig ... end`

`ForCustomMaps`

is a forward data flow analysis that is tuned for greater performance. It internally relies on `CompactQueue`

, instead of `Queue`

. Furthermore, instead of relying on a full-fledged implementation of maps as described by `MINIMAL_IMPERATIVE_MAPS`

, it expects the user to create and initialize two maps `V`

and `B`

that satisfy the signature `ARRAY`

. This typically allows the user to choose an efficient, specialized data representation.