# A description of the evaluation process

This chapter describes the process by which the evaluator turns a text string representing an XPath expression, into a sequence of items. This description should act as a guide for anyone interested in examining the code, and that includes the author (I'm writing it right now to help me check I am being consistent throughout).

Conceptually, the process proceeds in a series of phases. In practice, there is some limited overlapping of these phases. To get a good picture of how an XPath evaluation is supposed to work, see XML Path Language (XPath) 2.0.

The steps taken by the Gobo XPath evaluation engine are as follows:

- Parsing the expression text.
- Simplifying the parsed expression.
- Performing static type checking and optimization.
- Evaluating the expression.

## Items, Nodes, Values, Sequences, Iterators and Expressions

The input to the evaluation process is a text string, representing an XPath Expression, and a Context Item. First then, some definitions:

Sequence
  The result of evaluation is a sequence of zero or more Items. A sequence is a Value, but in the data model, it can also be represented as an Iterator.

  A sequence of one item is completely interchangeable with the item itself.

  The class for a sequence is `XM_XPATH_SEQUENCE_VALUE`.

Item
  The basic unit of information coming out of the evaluation process. An item is either an Atomic Value or else it is a Node.

  The class for an item is `XM_XPATH_ITEM`.

Node
  A node is a constituent of the XML input tree. It is one of:
  - Document
  - Element
  - Attribute
  - Namespace
  - Text
  - Comment
  - Processing instruction

  The class for a node is `XM_XPATH_NODE`.

  The architecture supports multiple implementations of the data model's tree structure. The only implementations at present are the standard tree implementation and the tiny tree implementation. In these implementation, the class for a node is `XM_XPATH_TREE_NODE` and `XM_XPATH_TINY_NODE` respectively.

Value
  A value is the result of evaluating an Expression, but it is also an expression in it's own right. However, it never has sub-expressions.

  A value can be regarded as a Sequence, although sometimes it is a sequence of length one, or even zero.

  The class for a value is `XM_XPATH_VALUE`.

Atomic Value
  An atomic value is a value consisting of a single Item.

  The class for an atomic value is `XM_XPATH_ATOMIC_VALUE`.

Expression
  An expression is the basic building block of Xpath. Expressions can be nested with full generality (`sub_expressions` lists the sub-expressions). Expressions evaluate to a Sequence of Items.

  The class for an expression is `XM_XPATH_EXPRESSION`.

  An expression is either a Value or an instance of `XM_XPATH_COMPUTED_EXPRESSION`.

Iterator
  An iterator is a construct within the programming model for traversing a Sequence of Items.

  The class for an iterator is `XM_XPATH_SEQUENCE_ITERATOR`.

## Parsing the expression text

`XM_XPATH_EXPRESSION_FACTORY` has a routine `make_expression` which takes a `STRING` (holding the text of the expression to be parsed) and an `XM_XPATH_STATIC_CONTEXT`. The result of calling `make_expression` is an optimized `XM_XPATH_EXPRESSION` in `parsed_expression`. If a parse error has occured though, this will be Void. In this case `is_parse_error` will be set to True, and `parsed_error_value` will be set to an instance of `XM_XPATH_ERROR_VALUE`.

A side-effect is that functions and variables may well be bound in the static context.

Setting the debug-key "XPath expression factory" will cause `make_expression` to print a textual representation of the expression tree to the standard error stream, immediately after parsing is sucessfull.

## Simplifying the parsed expression

If parsing is sucessful `XM_XPATH_EXPRESSION_FACTORY`'s `make_expression` routine goes on to call `simplify` on the expression. This performs context-independent optimizations on the expression and (recusively) it's sub-expressions. Current may be marked in error (So the caller of `simplify` must test `is_error`. If it is True, you can access `error_value`).

Note that if a simplification error occurs, `make_expression` treats it the same way as a parse error.

Setting the debug-key "XPath expression factory" will cause `make_expression` to print a textual representation of the simplified expression tree to the standard error stream, immediately after simplification.

## Performing static type checking and context-dependent optimizations

After the simplication process is complete (the picture here is itself simplified, as `simplify` may itself be called by later phases, especially if static analysis is unable to completely determine the type of an operand), the next phase is static analysis of the expression, to determine the types of all expressions. This is accomplished by calling `analyze` on the expression.

`Analyze` takes an `XM_XPATH_STATIC_CONTEXT` as it's sole parameter.

It may change the static context (?? check this some time).

As a command, is quite likely change the expression in one of several ways:

- It may mark Current as being in error (this is the chief purpose of static analysis). This is achieved by calling either `set_last_error` or `set_last_error_from_string`. Callers of `analyze` must check `is_error` afterwards.
- It may promote sub-expressions, via `promoted_expression`, or alter or replace them in some other way.
- It may replace Current with an alternative expression. In this case `was_expression_replaced` is set to True, and `replacement_expression` is set. Callers of `analyze` must check for this.

  Replacement may be done, for instance, because static analysis can show that the expression is in fact a constant value. In that case the expression can be pre-evaluated.

  Another reason for replacement is exactly the opposite: static analysis is unable to determine if the type or cardinality of the expression is correct or incorrect. In this case, the expression is wrapped in an `XM_XPATH_ITEM_CHECKER` or an `XM_XPATH_CARDINALITY_CHECKER` respectively. These classes postpone the checks until evaluation time.

Setting the debug-key "XPath evaluator" will cause `evaluate` to print a textual representation of the expression tree to the standard error stream, immediately after static analysis is sucessfull.

## Evaluating the expression

If static analysis is sucessfull, `evaluate` proceeds to the evaluation stage. `XM_XPATH_EXPRESSION` has no fewer than six routines for performing evaluation. All of them take an `XM_XPATH_CONTEXT` as sole parameter, though this may be Void on occaisions. If it is not Void, then it is liable to be altered by any of these routines (as the `context_item` is liable to change), so none of them are pure functions.

- `Effective_boolean_value` is called whenever an xs:boolean is expected. It always returns an `XM_XPATH_BOOLEAN_VALUE`, but the caller must check `is_error` upon return.

  TODO: pre-condition of analyzed - check if this is always checked for, as other evaluation routines cannot have it (because of cardinality-checker/item-checker)

  This is a function, so it does not change Current (but may change the evaluation context).

- `Evaluate_item` is called when a single `XM_XPATH_ITEM` is expected, although there exists the possibility of an empty sequence - denoted by Void.

  The result of evaluation is set in `last_evaluated_item`. This is Void if Current evaluates without error to an empty sequence.

  If an error is detected, then `last_evaluated_item`'s `is_error` will be set to True. Callers of `evaluate_item` must check for this possibility (after first checking for Void). The error value can be accessed via `error_value`. A class `XM_XPATH_INVALID_ITEM` is available for returning an error.

- `Evaluate_as_string` is used when it is known that Current can be evaluated to a single string (or an empty sequence, which can be represented by a zero-length string).
- `Iterator` is the usual routine called for evaluating a sequence. It always returns a result of type `XM_XPATH_SEQUENCE_ITERATOR[XM_XPATH_ITEM]`, althouh it may be marked as in error (callers must check `is_error` - if True, the error value is available in `error_value`).

  `XM_XPATH_SEQUENCE_ITERATOR[G -> XM_XPATH_ITEM]` is modelled on `DS_LIST_CURSOR`, although it only has a subset of the features (`before`, `after`, `off`, `item`, `start` and `forth`. It also has routine `another`, which produces another iterator which will iterate over the same items as the original would have initially done).

  Another difference is that `XM_XPATH_SEQUENCE_ITERATOR[G -> XM_XPATH_ITEM]` does not iterate over a physical list object - the sequences are only conceptual. Ususally the next `XM_XPATH_ITEM` will be evaluated (possibly changing the evaluation context as a side effect) when `start/forth` is called.

  `XM_XPATH_SEQUENCE_ITERATOR[G -> XM_XPATH_ITEM]` is a deferred class. A number of descendants are available for actual use:

  - `XM_XPATH_LAST_POSITION_FINDER [G-> XM_XPATH_ITEM]` is a deferred class that adds the routine `last_position` to it's descndants.
  - `XM_XPATH_REVERSIBLE_ITERATOR [G-> XM_XPATH_ITEM]` is a deferred class that adds the routine `reverse_iterator` to it's descndants.
  - `XM_XPATH_AXIS_ITERATOR [G -> XM_XPATH_NODE]` is also deferred. An instance is used for traversing an XPath Axis. Implementations for the tiny-tree implementation of the data model are:
    - `XM_XPATH_ANCESTOR_ENUMERATION`
    - `XM_XPATH_ATTRIBUTE_ENUMERATION`
    - `XM_XPATH_DESCENDANT_ENUMERATION`
    - `XM_XPATH_FOLLOWING_ENUMERATION`
    - `XM_XPATH_PRECEDING_ENUMERATION`
    - `XM_XPATH_PRECEDING_SIBLING_ENUMERATION`
    - `XM_XPATH_SIBLING_ENUMERATION`
  - `XM_XPATH_ARRAY_ITERATOR [G -> XM_XPATH_ITEM]` iterates across an `ARRAY [XM_XPATH_ITEM]`.
  - `XM_XPATH_ARRAY_LIST_ITERATOR [G -> XM_XPATH_ITEM]` iterates across a `DS_ARRAYED_LIST [XM_XPATH_ITEM]`.
  - `XM_XPATH_EMPTY_ITERATOR [G -> XM_XPATH_ITEM]` iterates across an empty sequence.
  - `XM_XPATH_INVALID_ITERATOR` is useful as a Result when an error is detected.
  - `XM_XPATH_SINGLETON_ITERATOR [G -> XM_XPATH_ITEM]` is used when only zero or one `XM_XPATH_ITEM`s are allowed.
  - `XM_XPATH_ARRAY_ITERATOR [G -> XM_XPATH_ITEM]` iterates across an `ARRAY [XM_XPATH_ITEM]`.
  - `XM_XPATH_FILTER_ITERATOR` provides filtered iteration across a sequence of `XM_XPATH_ITEM`s.
  - `XM_XPATH_MAPPING_ITERATOR` is used to flatten sequences of sequences of `XM_XPATH_ITEM`s, as XPath does not permit nested sequences.

    Classes that return an`XM_XPATH_MAPPING_ITERATOR` from their `iterator` routine need to implement `XM_XPATH_MAPPING_FUNCTION`. This has a single feature `map`, which returns an`XM_XPATH_MAPPED_ITEM`. This is either Void, or an `XM_XPATH_ITEM`, or an`XM_XPATH_SEQUENCE_ITERATOR[G -> XM_XPATH_ITEM]`. If `map` detects an error, then it's return value must encapsulate an `XM_XPATH_ITEM` in error.

  - `XM_XPATH_POSITION_ITERATOR` iterates across a sub-sequence.
  - `XM_XPATH_RANGE_ITERATOR` iterates across a monotonically increasing sequence of integers.
- `Eagerly_evaluate` is called to perform pre-evaluation, when static analysis of an `XM_XPATH_BINARY_EXPRESSION` has determined that both operands are constants.`XM_XPATH_FUNCTION_CALL` may also call this, to pre-evaluate arguments to a function call.
- `Lazily_evaluate` is called to create an `XM_XPATH_CLOSURE`.