# `Feel.Analysis.Analyzer`
[🔗](https://github.com/FeeJai/BDM/blob/feel-v0.1.0/apps/feel/lib/feel/analysis/analyzer.ex#L1)

Turns a syntax tree into the resolved form that a backend runs.

The analyzer is the step between `Feel.Syntax.Parser` and `Feel.Backend`. It walks
a `Feel.AST` with a `Feel.Analysis.ScopeStack` and produces a `Feel.IR`, the inferred
type of the whole expression, the names it reads, and the diagnostics it found. It
does the work that does not depend on the data, so it happens once per expression:

  * **Names.** Each name becomes a variable, a local, a built-in function, a key of
    a filter element, or, where the keys are only known at run time, a dynamic name.
    A name that is not in the scope is a variable that the run looks up, with a warning, or a `null`,
    or an error, depending on `:unknown_names`.
  * **Constants.** The `@"..."` literals are decoded into dates, times, and
    durations, and a literal that is not valid is reported.
  * **Types.** Every node gets its type, by `Feel.Type`. A filter whose brackets hold
    a boolean is a predicate, one that holds a number is an index, and otherwise the
    mode is left to run time.
  * **Calls.** The arguments of a call to a function that is known are checked
    against its signature and put in the order of its parameters. A call with named
    arguments to a built-in with several signatures picks the one that fits.
  * **Contexts.** The entries of a context literal are put in the order they can be
    evaluated, since an entry may refer to a later one, and a cycle or a duplicate
    key is reported.
  * **Unary tests.** The tests are checked for whether they use `?`, since that
    decides what a plain expression among them means.
  * **Dialects.** The `:dialect` is validated and not read yet. S-FEEL is checked on the syntax
    tree before the analyzer (`Feel.Syntax.SFeel`, D-49), and B-FEEL will change what the types of
    the operators are (D-49).

An error in the expression is returned as `{:error, diagnostics}`; warnings come
back in the result.

Function literals use a stable observable signature (D-219). A private AST copy identifies each
occurrence independently of its span. In full analysis a kind-only pass captures result signatures
in the written environment; the full pass and subsequent call specialization reuse them. Both passes
retain their specialization budgets and discard their preparation-local memo state on completion.
The more precise body result is a call refinement, not a new runtime signature.

> #### Not every construct is handled yet {: .warning}
>
> An unsupported built-in or an external function definition without an enabled implementation
> is an error with code `:not_implemented`, so preparation fails with an `:analysis` error instead
> of raising. Extensions can lower supported external definitions (`Feel.Analysis.External`, D-211);
> host-supplied function values are ordinary callable bindings (D-82). The names
> that a construct binds are the keys of a context literal, the parameters of a function (D-82), the iterators
> of `for`, `some` and `every` and `partial` (D-86), and `item` and the entries of an element in the brackets of
> a filter.

## Lists and contexts

A list is analyzed element by element, and is a list of the union of their types. The entries of a context
can read each other's keys, in any order (D-58), so they are analyzed in the order they depend on each other
(`Feel.Analysis.References` says what each reads, from the syntax tree). An entry that is read is a `:local`
of the type of its value, found before the names of the scope and shadowing a built-in function of the same
name; the locals are not free names. A key used twice, and entries that depend on each other in a circle,
make the context `null` with an error when it runs: the node carries it, as a call with invalid arity
does, and preparing it is a warning. A call whose argument types cannot fit instead retains ordinary
runtime argument validation. Its preparation warning describes inferred types; its runtime diagnostic
describes the values actually supplied, independently of the analysis tier.

## Paths

`source.name` selects an entry of a context, a property of a date, a time, a duration or a range, or
the same from each element of a list (D-65). The type is made as exactly as the source allows:

  * a source that is a constant (`{a: 1}`, `date("2018-12-10")`, a list of them) is selected from at once,
    so `{a: 1}.a` is `number = 1`, and `{a: 1}.b`, which the run will report, is `null` with a warning;
  * otherwise `Feel.Analysis.Paths` makes the type from the type of the source: an entry that a context
    type lists has its type (and no `Null` unless the type has one), a property has the range of its
    values (`month` is `number in [1..12]`), a list gives a list, and an entry a type does not list is
    `Any | Null`, since a context type allows more entries than it lists. The entries of a context
    literal are all it has, so there `{a: x}.b` is certainly `null`;
  * a path that starts at a variable is narrowed by the conditions around it, as the variable is:
    in `then` of `if p.age >= 18`, `p.age` is a number from 18 (`Feel.Analysis.Narrowing`).

`source...name`, the descendant, is the values under the key in a context and in the contexts nested in it,
always a list (D-65). A constant is evaluated; a closed context is walked as the run walks a value, so
`{a: {b: n}}...b` is `list<number | Null>`; an open one can have them anywhere, `list<Any | Null>`.

A selection that is certainly an error (a name the value does not have, or a source that is `null`) is a
`:invalid_property` warning of the expression. The `value` property of a date, a time and a date and
time is an error with the code `:not_implemented`.

## Filters

`source[brackets]` (D-71) is an element of the source, or the elements for which the brackets are true. The source
is analyzed outside the brackets; the brackets are analyzed with `item` and, where an element is a context, its
entries as names (`Feel.Analysis.Filters`): an `:item`, an `:item_field` for an entry that every element has, and a
`:dynamic_name` for one that some may have, found at run time and falling back to what the name is without the
elements. The type of the brackets decides whether they are an index or a predicate, and the value does when it
does not. The result is typed from the source and as exactly as the predicate allows: the elements it keeps are the
elements as they are when it is true, by the same facts as the branches of an `if` (`Feel.Analysis.Narrowing`, D-194).

## Conditionals

`if c then a else b` runs only the branch it takes: `a` if `c` is `true`, `b` for any other
value (Table 50), so unlike an operator it does not evaluate all its parts. The analyzer
analyzes all three, so an error in any of them is found, and types the node with
`Feel.Analysis.Inference.branches/3`. A branch that the type of the condition rules out
(`reachable/1`) never runs, so its type is not part of the result's and its warnings are not
said; nor does one in which a read finds that the facts of the conditions leave its name no value (D-152), or the facts of
a comparison of a call of a rounding function, `exp` or `log` (D-194). Such a branch
cannot run, so every node in it has the type of no value (`Feel.Type.Union.never/0`, `Feel.IR.unreachable/1`, D-173).
The names it reads stay free names, and are verified when the run starts (D-138) all the same.

The condition is analyzed first, because what it says about the names it reads holds in the
branches (D-194): in `then` it was `true`, in `else` it was not, `null` included. A name that it
compares, or that is the whole condition, has the type that is left (`Feel.Analysis.Narrowing`) in
every read of it in a branch, and in the conditions inside the branch. A condition that reads a
name and still has one outcome is a `:decided_condition` warning, since a branch can never run;
one of constants is not, for `if true` is how a branch is switched off. A branch that the type of the condition
leaves but in which a read finds that the facts leave its name no value is an `:unreachable_branch` warning, with the
span of the branch (D-173); not in the right operand of an `and` or an `or`, which is run all the same.

## Unary tests

A list of unary tests is analyzed to a `{:unary_tests, ...}` node whose tests are
expressions of the input `?`: `< 5` is `? < 5`, `[1..5)` is `? >= 1 and ? < 5`, and a
value such as `"a"` is `? = "a"`. A test whose meaning depends on the value of an
expression that is only known when it runs, as a name that may be a list or a range,
is a `:match` node, and so is an expression of `?` that can be `null` or a boolean, since that is the answer
itself and not a value that the input equals (D-209). `?` is a name in a context of its own, and not a free
name of the expression (D-40).

## Allowed values

The names that the expression reads and that have allowed values in the scope
(`Feel.Scope`) are verified when the run starts, and not where they are read (D-138). The
analyzer collects, for each such name, its tests (one set for the name, and one for each member of it that has some),
compiled by `Feel.Analysis.AllowedValues` with `?` typed as the variable or the member, and the span of its first
read, and puts one
`{:verify_bindings, meta, mode, verifications, body}` node around the expression. The reads in it are plain
`:var` nodes: they see `null` for a bound value that is not allowed, and the type of the
variable, since the verification only ever makes a value `null`. The names that the tests read are
free names, and the tests read them as the expression does, converted and verified, with the type their own allowed values
give them (D-170): `age` with `<= max age` is cut by the type of `max age`. The `:result_allowed_values` option verifies the result of the whole expression,
in an `:allowed` node with `:result` for the name and `?` typed as the expression.

## Verifying and narrowing

One option says what the declarations of the scope are used for, for the names the expression reads: `:declarations`, a
stance (`Feel.Analysis.Declarations`, D-138). It is about the whole expression; a setting for each name is for later.
The stance is two things, which the analyzer keeps apart inside, as `verify` and `narrow` of its context, and works out
from the stance and the tier in one place (`Feel.Analysis.Declarations.settings!/2`).

  * `verify` is what the run does with a bound value that does not fit the declared type of its name or its allowed
    values. `:enforce` converts it, or makes it `null` with an error: that is the `:conform_bindings` and
    `:verify_bindings` nodes above, in the mode `:enforce`. `:report` leaves every value as it is and only reports it: the
    same nodes in the mode `{:report, severity}`, where the severity is `:error` for a declared type, which is relied on
    whatever `narrow` says, and for allowed values that narrow, and `:warning` for allowed values that do not. `false`
    puts neither node in the expression.
  * `narrow` is whether the allowed values narrow the type of the name, so that `age` with `[0..150]` is
    `number in [0..150]`. It is where the run makes it so (`:enforce`) and where the caller says it is so (`:trust`,
    `:audit`). Without `:enforce` that is an assertion by the caller: if a value is not allowed after all, the types are
    wrong, and so is what the optimizer took out because of them.

## The result

A scope (or the options `:result_type` and `:result_allowed_values`) can say what the
expression gives (D-138). The result is converted to the declared type, as a decision's is
to its variable's: a `:conform` node, which unwraps a singleton list or wraps a value in
a list where that makes it fit, and gives `null` with an error where nothing does. A result that
certainly cannot conform, as a string for a number, is a `:type_mismatch` warning of the
expression. Then come the allowed values of the result, in an `:allowed` node around it, which has `each: true` when the
result is declared as a list, and then the tests are for its elements (D-51, D-138). The `:input` option types `?` in unary
tests, and the input is converted to the type and verified as the value of a name is, under the same `:declarations` (D-138);
`declarations: :ignore` reads the names as they are.

Allowed values that no value of the type satisfies, and a result that certainly fails its allowed values, are an
`:unsatisfiable_allowed_values` warning, at the first read of the name and at the expression (D-138). An operand of `and` or
`or` that reads a name and can be only one thing, and a unary test that no input satisfies, are a `:decided_condition`
warning as the condition of an `if` is.

## Names

A name is looked up in a `Feel.Analysis.ScopeStack` made from the `:scope` option
(D-37). A scope is not taken to have every name, so a name that is not in it is a
variable of type `:any` that is looked up in the bindings when the expression runs,
and an `:unknown_name` warning, with a suggestion when a name in the scope is close
(`:unknown_names` can make it a `null`, or an error). Without a scope, nothing is
known, so every name is such a variable, and there is no warning.
The variables an expression reads are returned in `:free_names`.

## Types

A type here is a `Feel.Type.Union`: the alternatives a value may have, with `:null`
among them when it may be `null` (D-39). A literal has the exact type of its value, a
variable the type the scope gives it with `null` added (every type of the specification
includes it), and an operation the type `Feel.Analysis.Inference` gives from the types
of its operands. An operation on literals only is evaluated, so `1 + 2` is `[:number]`,
never `null`, and `1 / 0` is `[:null]`. A divisor that is a literal zero, as in `x / 0`
or `x / (1 - 1)`, is a warning with the code `:division_by_zero` and the type `[:null]`, and so is an operation on
constants that is out of the range of decimal128 (`9.9E+6144 * 10`, `1E-6176 / 2`) with the code `:overflow`
(D-161). An operation on operands that cannot be `null` themselves, whose result can be `null` for some values of them, is an
info that tells which (D-161): a pair of values of the operands for which the run gives `null`, for each cause (a zero divisor,
a result too large or too small to write, a power with no value, a year out of the calendar, a zone on one operand only), in the
message and in `details.reasons`. Its code says what rules it out (D-161): `:operand_near_zero` for a name that can be zero or
very close to it, `:operand_too_large` for one that can be very large, and `:operand_unbounded` where both bounds are needed;
allowed values that keep the name within them rule it out. Any other is `:null_possible`. An operation that can only give `null` because
its operands do not fit, such as `1 + "a"`, gets the type `[:null]` and a warning with
the code `:type_mismatch`. At run time it is `null` with a diagnostic of its own.

# `option`

```elixir
@type option() ::
  {:scope, Feel.Scope.t() | nil}
  | {:dialect, Feel.Dialect.t()}
  | {:extensions, Feel.Extensions.t() | [atom()]}
  | {:unknown_names, :warn | :null | :error}
  | {:limits, Feel.Limits.t()}
  | {:input, Feel.Type.t() | Feel.Type.Union.t()}
  | {:declarations, Feel.Analysis.Declarations.stance()}
  | {:analysis, Feel.Analysis.Refinement.tier()}
  | {:result_allowed_values, String.t() | nil}
  | {:result_type, Feel.Type.t() | nil}
  | {:verify_result, boolean()}
  | {:input_conforms, boolean()}
  | {:unverified, [Feel.Analysis.AllowedValues.constraint()]}
  | {:complete_functions, [Feel.Name.t()]}
```

Options for `analyze/2`.

  * `:scope` - the `t:Feel.Scope.t/0` the names are resolved against. Without one,
    any name is accepted as a variable of type `:any`.
  * `:dialect` - `:feel` (default), `:s_feel`, or `:b_feel`. Raises `ArgumentError` for any other.
    Nothing reads it yet: S-FEEL is a restriction of the syntax, and B-FEEL is not written (D-49).
  * `:extensions` - the `Feel.Extensions` that are on, or a list of them (D-81). A call is resolved
    against the functions of DMN 1.6 with the overloads they add, and the functions they add. A call that one of
    their signatures may answer is marked `extension: true` in its metadata, and is folded with the extensions
    (D-45).
  * `:unknown_names` - what a name that is not in the `:scope` is: `:warn` (the default), a
    variable of type `:any` that is looked up in the bindings when the expression runs, with a
    warning, since a scope need not have every name; `:null`, a `null` with a warning, as the
    specification has it for a name that is nowhere; or `:error`, an error.
  * `:limits` - a `t:Feel.Limits.t/0`. The calls of built-in functions on constants that the analyzer evaluates for
    their types are evaluated within it, and one that passes a limit is not folded (D-45).
  * `:input` - the type of `?` in unary tests: a `t:Feel.Type.t/0`, which includes `null`, or
    a `t:Feel.Type.Union.t/0`. `:any` by default.
  * `:declarations` - the stance on the declarations of the scope: what the run does with a bound value that does not fit
    its declared type or allowed values, and whether the allowed values narrow the types (`t:Feel.Analysis.Declarations.stance/0`).
    `:enforce` by default; the table of the six stances is at `Feel.Analysis.Declarations` (D-138).
  * `:analysis` - `:full` (the default) or `:core`: how exact the types are (`Feel.Analysis.Refinement`, D-133).
  * `:result_allowed_values` - the allowed values of the result of the expression: the source
    text of a list of unary tests (D-138). The scope's, by default.
  * `:result_type` - the type of the result, a `t:Feel.Type.t/0`: the result is converted to
    it and has to conform (D-138). The scope's, by default.
  * `:verify_result` - whether the result is verified at all. `true` by default; the tests of
    allowed values are analyzed with `false`, since what the scope says about the result
    is about the expression and not about them.
  * `:input_conforms` - whether the input (`:input`) is a value that conforms to its type already, as the value a test of
    allowed values is run on is (it is the value of the name, converted, or the member of it). `false` by default: the
    input of unary tests that a caller gave is converted to the type as the value of a name is (D-138).
  * `:unverified` - the constraints that are not applied to a name that is read, whatever the stance says: the ones
    being compiled, and the ones whose tests read them (`Feel.Analysis.AllowedValues`, D-170). Each is
    `{name, steps, kind, index}`, as `Feel.Scope.constraints/2` has them. None by default.
  * `:complete_functions` - internal peer names supplied by linked preparation. Their values are
    single-signature FEEL closures constructed by `Feel.Recursion`, possibly null or wrapped by
    declaration conversion. This is not a public `Feel.prepare/2` option and must not be inferred
    from an ordinary host function declaration.

# `result`

```elixir
@type result() :: %{
  ir: Feel.IR.t(),
  type: Feel.Type.Union.t(),
  free_names: MapSet.t(Feel.Name.t()),
  diagnostics: [Feel.Diagnostic.t()]
}
```

What analysis produces: the resolved form, its inferred type, the names it reads
from the bindings, and the warnings found.

# `analyze`

```elixir
@spec analyze(Feel.AST.t(), [option()]) ::
  {:ok, result()} | {:error, [Feel.Diagnostic.t(), ...]}
```

Analyzes a syntax tree.

Returns `{:error, diagnostics}` with every error found; an expression with an error
has no resolved form. Raises `ArgumentError` for an unknown option.

    iex> {:ok, ast} = Feel.parse("1 + 2")
    iex> {:ok, result} = Feel.Analysis.Analyzer.analyze(ast, [])
    iex> {Feel.Type.Union.format(result.type), Feel.IR.kind(result.ir), result.diagnostics}
    {"number = 3", :arithmetic, []}

    iex> scope = Feel.Scope.new(%{"age" => :number})
    iex> {:ok, ast} = Feel.parse("age >= 18", scope: scope)
    iex> {:ok, result} = Feel.Analysis.Analyzer.analyze(ast, scope: scope)
    iex> {result.type, result.free_names}
    {[:boolean, :null], MapSet.new(["age"])}

    iex> {:ok, ast} = Feel.parse("if true then 1 else 2")
    iex> {:ok, result} = Feel.Analysis.Analyzer.analyze(ast, [])
    iex> {Feel.IR.kind(result.ir), Feel.Type.Union.format(result.type)}
    {:if, "number = 1"}

    iex> {:ok, ast} = Feel.parse("{a: 1, b: a + 1}")
    iex> {:ok, result} = Feel.Analysis.Analyzer.analyze(ast, [])
    iex> {Feel.IR.kind(result.ir), Feel.Type.Union.format(result.type)}
    {:context, "context<a: number = 1, b: number = 2>"}

    iex> ast = {:a_construct_nobody_wrote, %{span: {0, 3}}}
    iex> {:error, [diagnostic]} = Feel.Analysis.Analyzer.analyze(ast, [])
    iex> {diagnostic.code, diagnostic.message}
    {:not_implemented, "the a_construct_nobody_wrote construct is not supported yet"}

---

*Consult [api-reference.md](api-reference.md) for complete listing*