Table of Contents | Prev | Next | Bottom |

XForms Processors are free (and encouraged) to skip or optimize any steps in this algorithm, as long as the end result is the same. The XForms recalculation algorithm considers model items and model item properties to be vertices in a directed graph. Edges between the vertices represent computational dependencies between vertices.

Following is the default handling for a `recalculate`

action. Action `recalculate`

is defined in **10.1.4 The recalculate Element**.

A master dependency directed graph is created as detailed in

**D.1 Details on Creating the Master Dependency Directed Graph**.To provide consistent behavior, implementations must reduce the number of vertices to be processed by computing a pertinent dependency subgraph consisting only of vertices and edges that are reachable from nodes that require recomputation. This is detailed in

**D.2 Details on Creating the Pertinent Dependency Subgraph**. Note that on a first recomputation (such as on form load), the pertinent dependency subgraph will be the same as the master dependency directed graph.A topological sort is performed on the vertices of the pertinent dependency subgraph, resulting in an order of evaluation in which each vertex is evaluated only after those vertices on which it depends and before all vertices which depend on it. The topological sort algorithm is discussed at [Algorithms].

The

`recalculate`

process completes.

The master dependency directed graph can be considered an array with one record for each vertex, each having the following fields:

InstanceNode: a reference to the associated instance data nodetype: indicates the aspect of the instance node represented by the vertex (the text content or a model item property such as readOnly or required)depList: a list of vertices that refer to this vertexin-degree: the number of vertices on which this vertex dependsvisited: a flag used to ensure vertices are not added to a subgraph multiple timesindex: an association between vertices in the master dependency directed graph and a subgraph

The `depList`

for each vertex is assigned to be the referenced XML nodes of a given instance node, which are obtained by parsing the computed expression in the node (e.g., the calculate, relevant, readonly, or required property). Any expression violating any Binding Expression Constraint causes an exception (**4.5.4 The xforms-compute-exception Event**), terminating the `recalculate`

process.

The `depList`

for a vertex `v`

is assigned to be the vertices other than `v`

whose computational expressions reference `v`

(described below). Vertex `v`

is excluded from its own `depList`

to allow self-references to occur without causing a circular reference exception.

A computational expression appearing in a `calculate`

attribute controls the text content (value) of one or more instance nodes. A vertex exists for each instance node to represent the expression in the context of the node. Likewise, computational expressions for model item properties such as `readOnly`

and `required`

are applied to one or more instance nodes, and vertices are created to represent such expressions in the context of each applicable node. The computational expression of each vertex must be examined to determine the XML nodes to which it refers. Any expression violating any Binding Expression Constraint causes an exception (**4.5.4 The xforms-compute-exception Event**), terminating the `recalculate`

process. A computation expression refers to a vertex `v`

if a subexpression indicates the InstanceNode for `v`

and `v`

represents the instance node text content (its value). In this version of XForms, model item properties such as `readOnly`

and `required`

cannot be referenced in an expression.

If all calculations must be performed, which is the case on form load, then the pertinent dependency subgraph is simply a duplicate of the master dependency directed graph. If the recalculation algorithm is invoked with a list of changed instance data nodes since the last recalculation, then the pertinent dependency subgraph is obtained by exploring the paths of edges and vertices in the computational dependency directed graph that are reachable from each vertex in the change list. The method of path exploration can be depth first search, a suitable version of which appears in the pseudo-code below.

Sample Algorithm to Create the Pertinent Dependency Subgraph

This algorithm creates a pertinent dependency subgraph `S`

from a list of changed instance data nodes `L<sub>c</sub>`

. Variables such as `v`

and `w`

represent vertices in the master dependency directed graph. The same variables ending with `S`

indicate vertices in the pertinent dependency subgraph `S`

.

// Use depth-first search to explore master digraph subtrees rooted at // each changed vertex. A 'visited' flag is used to stop exploration // at the boundaries of previously explored subtrees (because subtrees // can overlap in directed graphs). for each vertexrinLcifris not visited { Push the pair (NIL,r) onto a stack while the stack is not empty { (v,w) = pop dependency pair from stack ifwis not visited { Set the visited flag ofwto true Create a vertexwSin S to representwSet the index ofwequal to the array location ofwSSet the index ofwSequal to the array location ofwSet the InstanceNode ofwSequal to the InstanceNode ofwSet the type ofwSequal to the type ofwFor each dependency nodexofwPush the pair (w,x) onto the stack } else ObtainwSfrom index ofwifvis not NIL { ObtainvSfrom index ofvAdd dependency node forwStovSIncrement inDegree ofwS} } } // Now clear the visited flags set in the loop above for each vertexvSin S { Obtainvfrom index ofvSAssign false to the visited flag ofv}

Note that the number of vertices and dependency nodes in the pertinent dependency subgraph is not known beforehand, but a method such as array doubling (see [DDJ-ArrayDoubling]) can be used to ensure that building the subgraph is performed in time linear in the size of `S`

.

The following steps process vertices, resulting in a recalculated form:

A vertex with inDegree of 0 is selected for evaluation and removed from the pertinent dependency subgraph. In the case where more than one vertex has inDegree zero, no particular ordering is specified. If the pertinent dependency subgraph contains vertices, but none have an inDegree of 0, then the calculation structure of the form has a loop, and an exception (

**4.5.4 The xforms-compute-exception Event**) must be thrown, terminating processing.-
If the vertex corresponds to a computed item, computed expressions are evaluated as follows:

`calculate`

: If the value of the model item changes, the corresponding instance data is updated and the dirty flag is set.`relevant`

,`readOnly`

,`required`

,`constraint`

: If any or all of these computed properties change, the new settings are immediately placed into effect for associated form controls.

For each vertex in the

`depList`

of the removed vertex, decrement the inDegree by 1.If no vertices remain in the pertinent dependency subgraph, then the calculation has successfully completed. Otherwise, repeat this sequence from step 1.

For example, consider six vertices `a`

, `b`

, `v`

, `w`

, `x`

, and `y`

. Let `a`

and `b`

represent the text content of instance nodes that will be set by a binding from user input controls. Let `v`

and `w`

be vertices representing the calculated value and the validity property of a third instance node `c`

. These vertices would result from a `bind`

element `B`

with `calculate`

and `constraint`

attributes and a `nodeset`

attribute that indicates `c`

. Suppose that the value of `c`

is the product of `a`

and `b`

and that the value is only valid if it does not exceed 100. Likewise, suppose `x`

and `y`

are vertices representing the calculated value and the validity property of a fourth instance node `d`

. Let the value of `d`

be the sum of `a`

and `b`

, and let `d`

be valid if the value does not exceed 20. The figure below depicts the dependency digraph for this example.

Vertices `a`

and `b`

have edges leading to `v`

and `x`

because these vertices represent the calculate expressions of `c`

and `d`

, which reference `a`

and `b`

to compute their product and sum, respectively. Similarly, `v`

and `x`

have directed edges to `w`

and `y`

, respectively, because `w`

and `y`

represent the `constraint`

expressions of `c`

and `d`

, which reference the values of `c`

and `d`

to compare them with boundary values.

If `a`

and `b`

are initially equal to 10, and the user changes `a`

to 11, then it is necessary to first recalculate `v`

(the value of `c`

) then recalculate `w`

(the validity property of the value of `c`

). Likewise, `x`

(the value of `d`

) must be recalculated before recalculating `y`

(the validity property of the value of `d`

). In both cases, the validity of the value does not change to `false`

until after the new product and sum are computed based on the change to `a`

. However, there are no interdependencies between `v`

and `x`

, so the product and sum could be computed in either order.

The pertinent subgraph excludes `b`

and only vertex `a`

has in-degree of zero. The vertex `a`

is processed first. It is not a computed vertex, so no recalculation occurs on `a`

, but its removal causes `v`

and `x`

to have in-degree zero. Vertex `v`

is processed second. Its value changes to 121, and its removal drops the in-degree of vertex `w`

to zero. Vertex `x`

is processed next, changing value to 21. When `x`

is removed, its neighbor `y`

drops to in-degree zero. The fourth and fifth iterations of this process recalculate the validity of `w`

and `y`

, both of which change to false.

Table of Contents | Top |