GHC.Types.Demand

Describes an interval of evaluation cardinalities. See Note [Evaluation cardinalities] See Note [Bit vector representation for Card]

Absent, {0}. Pretty-printed as A.

Used at most once, {0,1}. Pretty-printed as M.

Every possible cardinality; the top element, {0,1,n}. Pretty-printed as L.

Bottom, {}. Pretty-printed as A.

Strict and used once, {1}. Pretty-printed as 1.

Strict and used (possibly) many times, {1,n}. Pretty-printed as S.

A subtype of Card for which the upper bound is never 0 (no C_00 or C_10). The only four inhabitants are C_01, C_0N, C_11, C_1N. Membership can be tested with isCardNonAbs. See D and Call for use sites and explanation.

A subtype of Card for which the upper bound is never 1 (no C_01 or C_11). The only four inhabitants are C_00, C_0N, C_10, C_1N. Membership can be tested with isCardNonOnce. See Poly for use sites and explanation.

A demand describes

• How many times a variable is evaluated, via a Cardinality, and

• How deep its value was evaluated in turn, via a SubDemand.

Examples (using Note [Demand notation]):

• seq puts demand `1A` on its first argument: It evaluates the argument strictly (`1`), but not any deeper (A).

• fst puts demand `1P(1L,A)` on its argument: It evaluates the argument pair strictly and the first component strictly, but no nested info beyond that (L). Its second argument is not used at all.

• $ puts demand `1C(1,L)` on its first argument: It calls (C) the argument function with one argument, exactly once (`1`). No info on how the result of that call is evaluated (L).

• maybe puts demand `MC(M,L)` on its second argument: It evaluates the argument function at most once ((M)aybe) and calls it once when it is evaluated.

• `fst p + fst p` puts demand `SP(SL,A)` on p: It's `1P(1L,A)` multiplied by two, so we get S (used at least once, possibly multiple times).

This data type is quite similar to `Scaled SubDemand', but it's scaled by Card, which is an interval on Multiplicity, the upper bound of which could be used to infer uniqueness types. Also we treat AbsDmd and BotDmd specially, as the concept of a SubDemand doesn't apply when there isn't any evaluation at all. If you don't care, simply use (:*).

c :* sd is a demand that says "evaluated c times, and any trace in which it is evaluated will evaluate at least as deep as sd".

Matching on this pattern synonym is a complete match. If the matched demand was AbsDmd, it will match as C_00 :* seqSubDmd. If the matched demand was BotDmd, it will match as C_10 :* botSubDmd. The builder of this pattern synonym simply discards the SubDemand if the Card was absent and returns AbsDmd or BotDmd instead. It will assert that the discarded sub-demand was seqSubDmd and botSubDmd, respectively.

Call sites should consider whether they really want to look at the SubDemand of an absent demand and match on AbsDmd and/or BotDmd otherwise. Really, any other SubDemand would be allowed and might work better, depending on context.

A sub-demand describes an evaluation context (in the sense of an operational semantics), e.g. how deep the denoted thing is going to be evaluated. See Demand for examples.

See Note [SubDemand denotes at least one evaluation] for a more detailed description of what a sub-demand means.

See Note [Demand notation] for the extensively used short-hand notation. See also Note [Why Boxity in SubDemand and not in Demand?].

A smart constructor for Prod, applying rewrite rules along the semantic equality Prod b [n :* Poly Boxed n, ...] === Poly b n, simplifying to Poly SubDemands when possible. Examples:

• Rewrites P(L,L) (e.g., arguments Boxed, [L,L]) to L

• Rewrites !P(L!L,L!L) (e.g., arguments Unboxed, [L!L,L!L]) to !L

• Does not rewrite P(1L), P(L!L), !P(L) or P(L,A)

viewProd n sd interprets sd as a Prod of arity n, expanding Poly demands as necessary.

Divergence characterises whether something surely diverges. Models a subset lattice of the following exhaustive set of divergence results:

n

nontermination (e.g. loops)

i

throws imprecise exception

p

throws precise exception

c

converges (reduces to WHNF).

The different lattice elements correspond to different subsets, indicated by juxtaposition of indicators (e.g. nc definitely doesn't throw an exception, and may or may not reduce to WHNF).

            Dunno (nipc)
                 |
           ExnOrDiv (nip)
                 |
           Diverges (ni)

As you can see, we don't distinguish n and i. See Note [Precise exceptions and strictness analysis] for why p is so special compared to i.

True if the Divergence indicates that evaluation will not return. See Note [Dead ends].

Captures the result of an evaluation of an expression, by

• Listing how the free variables of that expression have been evaluated (de_fvs)

• Saying whether or not evaluation would surely diverge (de_div)

See Note [Demand env Equality].

Build a potentially terminating DmdEnv from a finite map that says what has been evaluated so far

DmdEnv is a monoid via plusDmdEnv and nopDmdEnv; this is its msum

Characterises how an expression

• Evaluates its free variables (dt_env) including divergence info

• Evaluates its arguments (dt_args)

The depth of the wrapped DmdType encodes the arity at which it is safe to unleash. Better construct this through mkDmdSigForArity. See Note [Understanding DmdType and DmdSig]

Turns a DmdType computed for the particular Arity into a DmdSig unleashable at that arity. See Note [Understanding DmdType and DmdSig].

True if the signature diverges or throws an imprecise exception in a saturated call. NB: In constrast to isDeadEndSig this returns False for exnDiv. See Note [Dead ends] and Note [Precise vs imprecise exceptions].

True if the signature diverges or throws an exception in a saturated call. See Note [Dead ends].

Returns true if an application to n value args would diverge or throw an exception.

If a function having botDiv is applied to a less number of arguments than its syntactic arity, we cannot say for sure that it is going to diverge. Hence this function conservatively returns False in that case. See Note [Dead ends].

A demand transformer is a monotone function from an incoming evaluation context (SubDemand) to a DmdType, describing how the denoted thing (i.e. expression, function) uses its arguments and free variables, and whether it diverges.

See Note [Understanding DmdType and DmdSig] and Note [What are demand signatures?].

Extrapolate a demand signature (DmdSig) into a DmdTransformer.

Given a function's DmdSig and a SubDemand for the evaluation context, return how the function evaluates its free variables and arguments.

A special DmdTransformer for data constructors that feeds product demands into the constructor arguments.

A special DmdTransformer for dictionary selectors that feeds the demand on the result into the indicated dictionary component (if saturated). See Note [Demand transformer for a dictionary selector].

Drop all boxity

Remove the demand environment from the signature.

Remove all `C_01 :*` info (but not CM sub-demands) from the demand

Remove all `C_01 :*` info (but not CM sub-demands) from the strictness signature