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.