2004
Colin Adams and others
Colin
Adams
colin@colina.demon.co.uk Thursday, April 15th, 2004

# 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`.