Feel.AST (feel v0.1.0)

Copy Markdown View Source

The syntax tree that Feel.parse/2 returns.

Every node is a tuple {kind, meta, ...}. meta is a map with the node's :span, the byte range of its source text. The tree describes the source as written; it does not resolve names or decode dates, and it keeps no parentheses, since the tree already shows the grouping.

Names

A name is a list of tokens, kept exactly as lexed (["first", "name"], ["a", "-", "b"]). Which tokens form a name depends on the names in scope, so the parser decides, and later stages derive the canonical string with Feel.Name. A name written in backticks (`first name`, D-81) is the same list of tokens, and its node (or the path that ends in it) has quoted: span in its meta, the span of what was in backticks; the analyzer reports it once (Feel.Analysis.QuotedNames). A qualified name such as import.Type is also a token list, with the "." as a token.

A node that a layer above builds from a boxed expression can have boxed: true in its meta: an {:if, …}, {:filter, …} or {:quantified, …} that is null with an error for a condition that is a value other than a boolean and null (D-212, Feel.Runtime.Boxed). The parser never makes it.

Expression nodes

NodeFEEL
{:literal, meta, value}number, string, true, false, null
{:at_literal, meta, text}@"2020-01-01" (text not yet decoded)
{:name, meta, tokens}a name
{:negate, meta, expr}-expr
{:binary, meta, operator, left, right}+ - * / ** = != < <= > >= and or
{:between, meta, value, low, high}value between low and high
{:in, meta, value, tests}value in test, value in (a, b)
{:prefix_test, meta, operator, endpoint}< 5, >= x, = 3, != 3
{:range, meta, start_included, from, to, end_included}[1..5), ]1..5[
{:instance_of, meta, expr, type}expr instance of type
{:if, meta, condition, then, otherwise}if … then … else …
{:for, meta, iterators, body}for x in xs return body
{:quantified, meta, :some | :every, bindings, test}some x in xs satisfies test
{:filter, meta, source, predicate}source[predicate]
{:path, meta, source, tokens}source.name
{:descendant, meta, source, tokens}source...name
{:call, meta, callee, arguments}callee(…)
{:function, meta, parameters, external, body}function(a, b) body
{:list, meta, items}[a, b]
{:context, meta, entries}{a: 1, "b": 2}
{:decision_table, meta, policy, aggregation, inputs, rules, outputs}a decision table: no text, see below
{:declared, meta, expression, type, allowed_values}expression converted to the Feel.Type.t() type (nil for none) and verified against the unary tests allowed_values, source text, or every constraint of a declared type (nil for none): no text, see below

not(x) is an ordinary call. A unary test such as < 5 inside an expression is a :prefix_test.

Decision tables

A decision table (DMN 1.6, clause 8) is a node that has no text: a layer above FEEL that reads a model builds it and gives it to Feel.prepare_ast/3, and the parser never makes one. It is in the tree because its meaning is FEEL's: the entries of a rule are unary tests of the input of their column, the outputs are expressions, and what the analysis knows of them gives the type of the table (Feel.Analysis.Tables). The outputs of a rule are analyzed knowing its entries: the rule matched, so what its entries say of the inputs holds in them (D-195). The run is Feel.Runtime.DecisionTable.

{:decision_table, meta, policy, aggregation, inputs, rules, outputs}
  • policy is :unique, :first, :any, :priority, :output_order, :rule_order or :collect, and aggregation is nil, or :sum, :count, :min or :max for a :collect table of one output.
  • inputs are the columns: {expression, input_values}, the input expression and the unary tests that its values are expected to satisfy (nil for none), which a - entry has to satisfy.
  • rules are {id, entries, results}: the id for the messages, one entry for each input (a {:unary_tests, …} node, or nil for -), and one output entry, an expression, for each output.
  • outputs are {name, order, default}: the name of the output (nil for the one output of a table that has one; a table of several has a context for each hit, with the name for the key), the output values as an expression that is a list, whose order is the priority of the policies :priority and :output_order (nil for none), and the default output entry (nil for none).

Declared values

{:declared, meta, expression, type, allowed_values} is the value of an expression that something declares a type and allowed values for, as a decision declares them for its result: a layer above FEEL builds it where it knows the declaration (the entry of a boxed context, the decision in a decision service, the body of a function) and gives the tree to Feel.prepare_ast/3. The value is converted to the type (a list of one element is its element for a type that is not a list, a value is a list of itself for a list type) and is null with an error when it does not conform or does not satisfy the allowed values (DMN 1.6, 10.3.2.9; D-138), the same code that does it for the :result_type and :result_allowed_values of the whole expression. type is a Feel.Type.t/0 whose names are those of the scope, and allowed_values the source of a list of unary tests, as for a scope, or the constraints of a declared type, a list of what Feel.ItemDefinitions.variable/2 gives: %{steps: steps, kind: :allowed_values | :type_constraint, source: text}, each for the value or, down its steps (a key of a context, :each for the elements of a list), for a member of it. All of them have to hold, each is the :allowed node of the IR around the one before (with meta.path when it is for a member), and the first member that a constraint turns down makes the value null with the error that says where it is. A value that is null, and a member that is not there or is null, is exempt.

Unary tests

{:unary_tests, meta, kind, tests} is the result of parsing with entry: :unary_tests. kind is :any for - (and tests is empty), :positive for a list of tests, or :negated for not(tests).

Type expressions

A type expression appears inside other nodes, after instance of and in the parameters of a function definition: {:type_name, meta, tokens}, {:list_type, meta, element}, {:range_type, meta, endpoint}, {:context_type, meta, members}, {:function_type, meta, parameters, result}, or {:non_null_type, meta, type} for a trailing ! (D-48). Feel.Type.parse/2 reads a type on its own, and reads two more that a host declares (D-178): {:union_type, meta, types} for T | U and {:not_type, meta, type} for Any except T.

Summary

Types

arguments()

The arguments of a call: all positional or all named, never mixed.

comparison_operator()
decision_aggregation()
decision_policy()
domain()

What a for iterator ranges over: a list, or from..to.

expression()
iterator()
key()

A context key: a name, or a string literal.

meta()
operator()
parameter()

A formal parameter with an optional declared type.

span()

A byte range in the source: from inclusive, to exclusive.

t()

A node of any entry point.

tokens()

The tokens of a name, as lexed, including symbols such as the hyphen and the period.

type_expression()
unary_tests()

Functions

kind(node)

Returns the kind of a node, the first element of its tuple.

shift(tree, offset)

Moves every span of a tree by offset bytes: the :span of every node, and the :quoted span of a name in backticks.

span(node)

Returns the byte range of a node's source text.

Types

arguments()

@type arguments() ::
  {:positional, [expression()]} | {:named, [{tokens(), expression()}]}

The arguments of a call: all positional or all named, never mixed.

comparison_operator()

@type comparison_operator() :: :eq | :neq | :lt | :lte | :gt | :gte

decision_aggregation()

@type decision_aggregation() :: :sum | :count | :min | :max | nil

decision_policy()

@type decision_policy() ::
  :unique | :first | :any | :priority | :output_order | :rule_order | :collect

domain()

@type domain() :: expression() | {:through, expression(), expression()}

What a for iterator ranges over: a list, or from..to.

expression()

@type expression() ::
  {:literal, meta(),
   Feel.Value.Number.t()
   | Feel.Value.String.t()
   | Feel.Value.Boolean.t()
   | Feel.Value.Null.t()}
  | {:at_literal, meta(), String.t()}
  | {:name, meta(), tokens()}
  | {:negate, meta(), expression()}
  | {:binary, meta(), operator(), expression(), expression()}
  | {:between, meta(), expression(), expression(), expression()}
  | {:in, meta(), expression(), [expression()]}
  | {:prefix_test, meta(), comparison_operator(), expression()}
  | {:range, meta(), boolean(), expression(), expression(), boolean()}
  | {:instance_of, meta(), expression(), type_expression()}
  | {:if, meta(), expression(), expression(), expression()}
  | {:for, meta(), [iterator(), ...], expression()}
  | {:quantified, meta(), :some | :every, [{tokens(), expression()}, ...],
     expression()}
  | {:filter, meta(), expression(), expression()}
  | {:path, meta(), expression(), tokens()}
  | {:descendant, meta(), expression(), tokens()}
  | {:call, meta(), expression(), arguments()}
  | {:function, meta(), [parameter()], boolean(), expression()}
  | {:list, meta(), [expression()]}
  | {:context, meta(), [{key(), expression()}]}
  | {:declared, meta(), expression(), Feel.Type.t() | nil,
     String.t() | [Feel.ItemDefinitions.constraint()] | nil}
  | {:decision_table, meta(), decision_policy(), decision_aggregation(),
     [{expression(), unary_tests() | nil}],
     [{String.t(), [unary_tests() | nil], [expression()]}],
     [{String.t() | nil, expression() | nil, expression() | nil}]}

iterator()

@type iterator() :: {tokens(), domain()}

key()

@type key() :: {:name, tokens()} | {:string, String.t()}

A context key: a name, or a string literal.

meta()

@type meta() :: %{span: span()}

operator()

@type operator() ::
  :add
  | :subtract
  | :multiply
  | :divide
  | :power
  | :eq
  | :neq
  | :lt
  | :lte
  | :gt
  | :gte
  | :and
  | :or

parameter()

@type parameter() :: {tokens(), type_expression() | nil}

A formal parameter with an optional declared type.

span()

@type span() :: Feel.Diagnostic.span()

A byte range in the source: from inclusive, to exclusive.

t()

@type t() :: expression() | type_expression() | unary_tests()

A node of any entry point.

tokens()

@type tokens() :: [String.t(), ...]

The tokens of a name, as lexed, including symbols such as the hyphen and the period.

type_expression()

@type type_expression() ::
  {:type_name, meta(), tokens()}
  | {:list_type, meta(), type_expression()}
  | {:range_type, meta(), type_expression()}
  | {:context_type, meta(), [{key(), type_expression()}, ...]}
  | {:function_type, meta(), [type_expression()], type_expression()}
  | {:non_null_type, meta(), type_expression()}
  | {:union_type, meta(), [type_expression(), ...]}
  | {:not_type, meta(), type_expression()}

unary_tests()

@type unary_tests() ::
  {:unary_tests, meta(), :any | :positive | :negated, [expression()]}

Functions

kind(node)

@spec kind(t()) :: atom()

Returns the kind of a node, the first element of its tuple.

iex> Feel.AST.kind({:name, %{span: {0, 1}}, ["x"]})
:name

shift(tree, offset)

@spec shift(t(), non_neg_integer()) :: t()

Moves every span of a tree by offset bytes: the :span of every node, and the :quoted span of a name in backticks.

A tree that was parsed from one text and is to be used as a part of a tree for a longer one (Feel.prepare_ast/3) needs its spans to be byte ranges of the longer text. The offset is where the first text starts in it.

iex> {:ok, tree} = Feel.parse("x + 1")
iex> {:binary, %{span: span}, :add, {:name, %{span: left}, ["x"]}, _right} = Feel.AST.shift(tree, 10)
iex> {span, left}
{{10, 15}, {10, 11}}

span(node)

@spec span(t()) :: span()

Returns the byte range of a node's source text.

iex> Feel.AST.span({:name, %{span: {0, 1}}, ["x"]})
{0, 1}