Proposal: expand @odk/xpath function implementation to handle all aspects of expressions

[eyelidlessness]

Motivation

Despite overwhelming similarities and copious documented references between the XPath and ODK XForms specifications (as well as ODK XForms both in real world use and in existing test suites), there are crucial semantic differences in how certain node-set references are expected to be resolved. These semantic differences depend on structural information about an XForm which is out of band from its ultimate evaluation context.

There may be other cases, but the most prominent case which comes to mind is how dependencies are resolved in expressions from repeats and their descendants. Take this example, an abbridged version of a test fixture ported from JavaRosa:

<h:html>
  <h:head>
    <model>
      <instance>
        <data id="repeat-calcs">
          <repeat>
            <position/>
            <position_2/>
          </repeat>
        </data>
      </instance>
      <bind nodeset="/data/repeat/position" calculate="position(..)"/>
      <bind nodeset="/data/repeat/position_2" calculate="/data/repeat/position * 2"/>
    </model>
  </h:head>
  <h:body>
    <repeat nodeset="/data/repeat" />
  </h:body>
</h:html>

Strictly adhering to XPath semantics, the calculation of position_2 will always produce 2. This is because the reference to the absolute path /data/repeat/position will resolve the first matching node, in document order.

The expectation in ODK XForms is that the same path will resolve to the node nearest its context node. In a second repeat instance, the path reference should resolve to the position node in the same repeat parent. More concretely:

<repeat>
  <position><!-- position(..) = 1 --></position>
  <position_2><!-- /data/repeat[1]/position * 2 = 2 --></position_2>
</repeat>
<repeat>
  <position><!-- position(..) = 2 --></position>
  <position_2><!-- /data/repeat[2]/position * 2 = 4 --></position_2>
</repeat>

The closest semantic equivalent in XPath, per spec, would be as if the expression were relative:

<repeat>
  <position><!-- position(..) = 1 --></position>
  <position_2><!-- ../position * 2 = 2 --></position_2>
</repeat>
<repeat>
  <position><!-- position(..) = 2 --></position>
  <position_2><!-- ../position * 2 = 4 --></position_2>
</repeat>

A tempting solution is to rewrite such expressions in exactly this way, and then evaluate them according to standard XPath semantics. I've explored this, and it is promising. But I have a couple of concerns with this approach:

• It's unclear to me how broadly this kind of a semantic mapping applies. Every exception, every permutation of special consideration for certain form structures and expression specifics, is a potential explosion of complexity and bugs.
• It introduces a huge indirection between a given XForm's actual expressions and the expressions that actually get evaluated. It's already challenging to maintain and debug a custom interpreter inside a host language.

Having mulled this for the last few weeks, I think a more appropriate way to address this semantic discrepancy is to build on the same mechanisms already used to address other XPath/XForms semantic discrepancies: function implementations, namespacing, and shadowing/overrides.

I believe the function implementation interface is, or is very nearly, well suited to handle this particular issue and its many permutations we'll likely encounter as we fill out support for repeats. I also believe this will have tremendous potential benefits for performance optimization (more on that below).

Proposal summary

In brief, this is a proposal to:

1. Extend the capabilities of XPath function implementations to support evaluation of all supported XPath syntax… as if each part of the XPath syntax were a function call.
2. Migrate internal implementation of non-function expression syntax to utilize said function implementation support.
3. Provide interfaces for function implementations to conditionally override, supplement, and defer to, their internal/default counterparts.
4. In support of the above, improve the pertinent APIs themselves for better ergonomics and maintainability of XPath function implementations generally.

I'll address the last of these first, then the others in order.

Improved function implementation APIs

The existing FunctionImplementation API (and its derivatives) has proven successful enough to support a full reimplementation of the current Enketo evaluator's scope. But it has a few really glaring weaknesses:

• Type safety around arity: every FunctionImplementation's host implementation (as in the function which is actually called in the JavaScript runtime) is typed as variadic, with zero required arguments. The vast majority use the unsafe ! (non-null assertion) operator extensively to work around this limitation.

• Static and runtime handling of parameter value types: currently, parameter type information is unused (even if it is present). Parameters which should always be (or be cast to) a particular type must be manually cast in each host function. More problematic, functions operating on nodes rely on manual runtime type validation in each host function as well. The latter is a particular footgun for this proposal.

• Parameter ergonomics: parameters are always evaluated lazily—which is necessary in a few cases (e.g. if(false(), explode(), kittens()) must return kittens without exploding them or anything else), and potentially good for performance in a few others (e.g. short-circuiting on NaN values)—but mostly it's just a lot of unnecessary ceremony.

• Return types: the base FunctionImplementation class has no support for specifying a return type at all, and certainly no means of enforcing it. Its typed subclasses are somewhat an improvement. This is currently less pressing an issue, but it's one I'd like to bring along for the ride. And it's a potential opportunity for other improvements, like automatic documentation generation, and possibly adding certain runtime checks e.g. to ensure a given function implementation valid to substitute/supplement another.

• Ambiguity around use of context: every host function currently takes a context parameter, and must use it to resolve each other parameter due to the aforementioned pervasive lazy evaluation. This makes it unclear when and how functions actually operate explicitly on their calling context.

• Alignment between signature definition and actual host function signature: there really isn't any, largely due to the other issues discussed above.

I believe all of these can be addressed with judicious use of a few complex TypeScript types, and careful consideration in particular around how/whether to keep evaluation lazy. Examples in the sections below, while pseudocode, will be at least partly based on prototyping around these API improvements.

Migrate internal non-function syntax to function implementations

Each non-function aspect of an XPath expression could be expressed as a function call. For instance, this expression:

//foo[position() = 2]

… could be expressed something like this psuedo-code:

(xpath/absolute-path
  (xpath/step
    (xpath/axis :descendant-or-self)
    (xpath/node-type :node))
  (xpath/step
    (xpath/axis :child)
    (xpath/name-test "foo")
    (xpath/predicate
      (xpath/=
        (fn/position)
        (xpath/number "2")))))

I chose to make this example lisp-y, because it can concisely express concepts like namespacing and special keywords, and because the intent is to show the idea of syntax-as-functions in the abstraact without overly tying it to how that would be implemented here.

I also took some liberties to simplify some aspects of the example. Notably absent is the concept of "context", which should be a parameter to several of the function calls. Some of the functions as expressed here would also have a more complex signature than the present FunctionImplementation API can express (or would with the improvements discussed above, though I'm open to accommodating that if we prefer).

But for the purposes of this proposal, implementations for the functions involved might look something like (again, this is pseudo-code):

const absolutePath = fn(
  SYNTAX_NS,
  'absolute_path',

  // A syntax function's parameters could be:
  // - the evaluation context
  // - ...its child syntax nodes
  parameters(context, variadic(syntaxNode('step'))),

  // Explicit return annotation.
  returns(nodeSet),

  // Signature inferred from above `parameters` (and checked against `returns`)
  (context, ...steps) => {
    let currentContext = context;

    for (const step of steps) {
      // Each `step` here is a syntax node.
      //
      // Dispatch of syntax functions could be handled internally to simplify
      // host function usage (more on dispatch below).
      //
      // Syntax producing a node-set is frequently part of a sub-expression, and
      // frequently produces a new context for evaluation of the next sub-
      // expression, so this can also be handled internally.
      currentContext = currentContext.callSyntaxFn(step);
    }

    // Functions specifying a return type could be free to return either the
    // specified value type directly, or the appropriate "result" box type.
    // In this case, a node-set's result type is also a context, so the context
    // is an appropriate return value here, but it would also be valid to return
    // `currentContext.nodes` or just an `Iterable<Node>` in general.
    return currentContext;
  }
);

// The idea here is that many parts of the syntax are inherently "polymorphic",
// but individual syntax function implementations could opt to handle only a
// specific subset of the potential syntax (like a method overload).
const descendantOrSelfNodeStep = fn(
  SYNTAX_NS,
  'step',
  parameters(
    context,
    // This function implementation *only* handles this axis...
    syntaxNode('axis', 'descendant-or-self'),
    // ... and this node type test
    syntaxNode('node_type', 'node'),
    variadic(syntaxNode('predicate'))
  ),
  returns(nodeSet),

  // As described above, a node-set returning function may return `Iterable<Node>`
  // which means it can also be implemented as a generator.
  function* descendantOrSelfNodes(context, axis, nodeType, ...predicates) {
    // Context is already iterable; this is (for instance) how position is handled
    for (let currentContext of context) {
      // Which would allow it to be handled as a function as well.
      for (const predicate of predicates) {
        currentContext = currentContext.callSyntaxFn(predicate);
      }

      // This being a descendant-or-self axis, we first yield "self"...
      for (const node of currentContext.nodes) {
        yield node;

        // ... and then recurse for descendants.
        for (const child of node.childNodes) {
          const childContext = currentContext.fromNode(child);

          // Option 1: The calling context could retain a reference to the
          // currently evaluated syntax node, to facilitate such recursion.
          yield* childContext.callSyntaxFn(context.syntaxNode);

          // Option 2: this function is callable directly
          yield* descendantOrSelfNodes(childContext, axis, nodeType, ...predicates);
        }
      }
    }
  }
);

const namedChildStep = fn(
  SYNTAX_NS,
  'step',
  parameters(
    context,
    syntaxNode('axis', 'child'),
    syntaxNode('name_test', 'unqualified'),
    variadic(syntaxNode('predicate'))
  ),
  returns(nodeSet),
  function* (context, axis, nameTest, ...predicates) {
    // This is *sometimes* an oversimplification due to complexities in
    // namespaces, but not always. More on that below.
    const selector = `:scope > ${nameTest.text}`;

    for (const node of context.contextNodes) {
      const namedChildren = (node as MaybeElementNode).querySelectorAll?.(selector) ?? [];

      // We could also simplify predicate filtering with a dedicated API
      yield* context.applyPredicates(namedChildren, predicates);

      // Alternately, `step` implementations could defer handling predicates
      // entirely by simply omitting them from their `parameters` signature.
    }
  }
);

const position = fn(
  FN_NS,
  'position',
  parameters(context),
  returns(number),
  (context) => {
    // The current implementation defers to an internal `context` API, which
    // we could continue to do. An alternative option will help illustrate the
    // next section.
    return context.contextPosition;
  }
);

const eqExprNumberNumber = fn(
  SYNTAX_NS,
  'eq_expr',
  // Note: this is *only* an implementation of `eq_expr` where both operands
  // are evaluated as numbers. In this proposal as it stands, we'd provide
  // separate implementations for each permutation of operand types.
  parameters(number, number),
  returns(boolean),
  (lhs, rhs) => lhs === rhs
);

Provide interfaces for function implementations to conditionally override, supplement, and defer to, their internal/default counterparts.

This section is going to be somewhat handwavy. I've thought about the API aspects of this least of all. The general idea is that a consumer of the primary Evaluator can provide specialized syntax/function implementations suitable for specific conditions, and fall back to standard behavior when those specific conditions are not met.

I think the best way to illustrate this is to come right back to the motivation for this proposal. Assuming we have:

• A context node position_2
• In an XForms primary instance
• Whose path we already know as (or can look up/map back to) /data/repeat[2]/position_2
• An expression to evaluate in the form /data/repeat/position * 2

We can provide a function overriding absolute_path something like:

declare const state: EntryState;

const xformsAwareAbsolutePath = fn(
  SYNTAX_NS,
  'absolute_path',
  // Let's say the `string` parameter here is the full text of the absolute path.
  parameters(context, string),
  returns(nodeSet),
  function* (context, path) {
    let found: Node | null = null;

    for (const node of context.contextNodes) {
      found = state.getNodeState(node)?.getReferencedNode(path);

      if (found != null) {
        break;
      }
    }

    // If lookup failed, fall back to other (e.g. internal) implementations
    if (found == null) {
      return fallback();
    }

    // Otherwise
    yield found;
  }
);

Fallback?

Calling fallback() here is doing a lot of work to carry this example (and again, it's pseudo-code to illustrate the idea, not an actual API proposal), without much explanation of how it would work. Basically it's kinda sorta like a continuation, where it instructs the evaluator to try the next candidate syntax function capable of handling the same syntax node for the given syntax node in the given context.

To make explicit something that's only been implied up to this point: currently (as of #13), functions are looked up by name (local, optionally namespaced) in each of the FunctionLibrarys available to the current Evaluator context. Once a matching function is found, it's called, and that's that. This proposal would depend on potentially finding multiple implementations:

• for a given function name
• of a compatible signature

... calling each in turn until it does not "fall back"—essentially until one of the candidate functions returns a value satisfying its returns annotation.

(All matching implementations "falling back" would be considered an error.)

---

Other cases will be more complicated, of course. For XForms semantics, we'll need to handle at least path references with predicates between steps. I believe elements of the above provide some direction for how this might be handled within the scope of this proposal. I'm hesitant to go too much deeper into examples for this use case without prototyping further, with more team visibility and discussion.

But to fill out some other ideas alluded above…

Performance opportunity: named child steps

Name tests, as handled internally in @odk/xpath, are extraordinarily general in order to satisfy some edge cases around the XPath and XML namespace specs that we don't really need to accommodate in most (if not all) XForms usage. An earlier example included an "oversimplification" of such a name test, but with this proposal that simplification can be employed only in conditions we know it safe.

Suppose we take an upfront step to ensure the XForms namespace is used as the default namespace, and can ignore any more complicated namespace testing for unqualified names within a form entry's primary instance:

declare const state: EntryState;

const xformsAwareNamedChildStep = fn(
  SYNTAX_NS,
  'step',
  parameters(
    context,
    syntaxNode('axis', 'child'),
    syntaxNode('name_test', 'unqualified'),
    variadic(syntaxNode('predicate'))
  ),
  returns(nodeSet),
  function* (context, _, name, ...predicates) {
    let found: Node | null = null;

    for (const node of context.contextNodes) {
      found = state.getNodeState(node)?.getChildNamed(name.text);

      if (found != null) {
        break;
      }
    }

    // If lookup failed, fall back to other (e.g. internal) implementations
    if (found == null) {
      return fallback();
    }

    // Otherwise
    yield* context.applyPredicates([found], predicates);
  }
)

Performance opportunity: arbitrary static subtrees

Itemsets populated by instance()/... expressions are by far the biggest performance issue in the web-forms work so far. This is largely because the same expressions and sub-expressions are evaluated repeatedly, redundantly, without any notion of their static-ness. An example also feels redundant at this point, it would be a slight variation on the previous two. In any case, I believe that a similar lookup/fallback approach for secondary instance data would be a significant improvement to performance in this case… particularly combined with application of the approach for primary instance references in those same itemset predicates.

[lognaturel]

The expectation in ODK XForms is that the same path will resolve to the node nearest its context node.

This is no longer in the spec and is not produced by pyxform. It is supported by Enketo as a fallback if a xforms-version attribute is not specified but we should really think about whether it’s necessary for this engine to support.

That’s not meant to be a response to the overall proposal, just to this specific potential requirement.

[eyelidlessness]

Between clarifying the scope of absolute path semantics for repeats, and the changes landed in #166, I think the bulk of my motivation for this is pretty much moot at this point. I'd still like to do some of it (at the very least improving the FunctionImplementation interface) in the fullness of time. There may be other reasons for considering the basic idea proposed here, but I don't think they're likely to be a priority in the foreseeable future. So I'm closing this one for now!