D.1 Détails de la création du graphe dirigé des dépendances maître

On peut assimiler le graphe dirigé des dépendances maître à un tableau dont chacun des enregistrements, un pour chaque sommet, comporte les champs suivants :

• InstanceNode : une référence au nœud de donnée d'instance associé ;
• type : indique l'aspect du nœud d'instance représenté par le sommet (un contenu textuel ou une propriété d'élément de modèle telle que readonly ou required) ;
• depList : une liste de sommets qui se rapporte à ce sommet ;
• in-degree : le nombre de sommets desquels ce sommet dépend ;
• visited : un drapeau servant à s'assurer que le sommet n'a pas été ajouté plusieurs fois à un sous-graphe ;
• index : une association entre des sommets dans le graphe dirigé des dépendances maître et un sous-graphe.

Le champ depList de chaque sommet a pour assignation les nœuds XML appelés d'un nœud d'instance donné, lesquels s'obtiennent en analysant l'expression calculée dans le nœud (par exemple, une propriété calculate, relevant, readonly ou required). Toute expression violant une contrainte d'expression de liaison entraîne une exception (cf. 4.5.4 L'événement xforms-compute-exception), ce qui termine le traitement de l'élément recalculate.

Le champ depList d'un sommet v reçoit comme assignation les sommets autres que v dont les expressions de calcul référencent v (ceci est décrit ensuite). Le sommet v est exclu de son propre champ depList afin de permettre les autoréférences sans provoquer une exception pour référence circulaire.

Une expression de calcul apparaissant dans un attribut calculate contrôle le contenu textuel (l'attribut value) d'un ou de plusieurs nœuds d'instance. Il y a un sommet pour chaque nœud d'instance afin de représenter l'expression dans le contexte du nœud. De même, des expressions de calcul de propriétés d'élément de modèle, telles que readonly et required, sont appliquées à un ou plusieurs nœuds d'instance, et des sommets sont créés afin de représenter ces expressions dans le contexte de chaque nœud pertinent. L'expression de calcul de chaque sommet doit être examinée pour déterminer les nœuds XML auxquels elle se réfère. Toute expression violant une contrainte d'expression de liaison entraîne une exception (cf. 4.5.4 L'événement xforms-compute-exception), ce qui termine le traitement de l'élément recalculate. Une expression de calcul se rapporte à un sommet v si une sous-expression indique le champ InstanceNode de v et si v représente le contenu textuel du nœud d'instance (sa valeur). Dans cette version de XForms, les propriétés d'élément de modèle, telles que readonly et required, ne peuvent pas être appelées dans une expression.

D.2 Détails sur la création du sous-graphe des dépendances pertinentes

Si tous les calculs doivent être effectués, ce qui est le cas au chargement du formulaire, alors le sous-graphe des dépendances pertinentes est simplement une copie du graphe dirigé des dépendances maître. Si l'algorithme de recalcul est invoqué avec une liste de nœuds de donnée d'instance changés depuis le dernier recalcul, alors le sous-graphe des dépendances pertinentes est obtenu en explorant les chemins des arcs et des sommets, dans le graphe dirigé des dépendances de calcul, accessibles à partir de chaque sommet dans la liste des changements. La méthode d'exploration des chemins peut constituer en une recherche en profondeur d'abord ; une version souhaitable apparaît dans le pseudo-code suivant.

// Utiliser d'abord une recherche en profondeur afin d'explorer les
// sous-arbres du graphe orienté maître ayant pour racine chaque
// sommet changé. On se sert d'un drapeau 'visited' pour arrêter
// l'exploration aux limites des sous-arbres explorés précédemment
// (car les sous-arbres peuvent se chevaucher dans les graphes dirigés).
pour chaque sommet r dans Lc
  si r n'est pas visité
  {
    Pousser le couple (NIL, r) sur la pile
    tant que la pile n'est pas vide
    {
      (v, w) = dépiler le couple de dépendance de la pile
      si w n'est pas visité
      {
        Fixer le drapeau visited de w à "true"
        Créer un sommet wS dans S pour représenter w
        Donner au champ index de w la valeur d'emplacement de tableau de wS
        Donner au champ index de wS la valeur d'emplacement de tableau de w
        Donner au champ InstanceNode de wS la valeur de celui de w
        Donner au champ type de wS la valeur de celui de w
        Pour chaque nœud de dépendance x de w
          Pousser le couple (w, x) sur la pile
      }
      sinon obtenir wS à partir du champ index de w
      si v n'est pas NIL
      {
        Obtenir vS à partir du champ index de v
        Ajouter le nœud de dépendance pour wS à vS
        Incrémenter le champ in-degree de wS
      }
    }
  }
        
// Maintenant retirer les drapeaux visited placés dans la boucle ci-dessus
par chaque sommet vS dans S
{
  Obtenir v à partir du champ index de vS
  Assigner la valeur "false" au drapeau visited de v
}

Remarquez que le nombre des sommets et des nœuds de dépendance dans le sous-graphe des dépendances pertinentes n'est pas connu à l'avance, mais on peut se servir d'une méthode comme le dédoublement de tableau (cf. [DDJ-ArrayDoubling]) afin de s'assurer que la construction du sous-graphe s'effectue en temps linéaire dans la dimension de S.

D.3 Détails du calcul des sommets individuels

Les sommets sont traités au cours des étapes suivantes, aboutissant au formulaire recalculé :

1. Un sommet dont le champ in-degree vaut "0" est sélectionné pour évaluation et retiré du sous-graphe des dépendances pertinentes. Dans le cas où le champ de plusieurs sommets vaut "0", aucun ordre particulier n'est indiqué. Si le sous-graphe des dépendances pertinentes contient des sommets dont aucun n'a un champ in-degree valant "0", alors la structure de calcul boucle, et une exception (cf. 4.5.4 L'événement xforms-compute-exception) doit être générée, en terminant le traitement ;

2. Si le sommet correspond à un élément calculé, alors les expressions calculées s'évaluent comme suit :

   1. Pour la propriété calculate : Si la valeur de l'élément de modèle change, alors les données d'instance correspondantes sont mises à jour et le drapeau visited est placé ;

   2. Pour les propriétés relevant, readonly, required, constraint : Si l'une ou toutes ces propriétés calculées changent, alors les nouveaux paramètres entrent immédiatement en vigueur dans les commandes de formulaire associées.

3. Pour chaque sommet dans le champ depList du sommet retiré, décrémenter le champ in-degree de 1 ;

4. Si aucun sommet ne reste dans le sous-graphe des dépendances pertinentes, alors le calcul s'est achevé avec succès, sinon répéter cette séquence depuis l'étape 1.

D.4 Exemple de traitement des calculs

Prenons, par exemple, six sommets a, b, v, w, x et y. Soit a et b représentant le contenu textuel de nœuds d'instance qui seront fixés par une liaison depuis des commandes d'entrée d'utilisateur. Soit v et w des sommets représentant la valeur calculée et la propriété de validité d'un troisième nœud d'instance c. Ces sommets sont le produit d'un élément bind B ayant des attributs calculate et constraint, et un attribut nodeset qui indique c. Supposons que la valeur de c soit le produit de a et b, et que cette valeur soit valide seulement si elle n'excède pas "100". De même, supposons que x et y soient des sommets représentant la valeur calculée et la propriété de validité d'un quatrième nœud d'instance d. Supposons que la valeur de d soit la somme de a et b, et que cette valeur soit valide seulement si elle n'excède pas "20". La figure suivante illustre le graphe orienté des dépendances de cet exemple :

Les sommets a et b ont des arcs menant à v et x, parce que ces sommets représentent les expressions calculate des sommets c et d, lesquels appellent a et b pour calculer, respectivement, leur produit et leur somme. De même, les sommets v et x ont des arcs dirigés, respectivement, vers w et y, parce que les sommets w et y représentent les expressions constraint des sommets c et d, lesquels appels les valeurs de c et d pour les comparer aux valeurs limites.

Si les valeurs de a et b sont initialement égales à "10", et que l'utilisateur change la valeur de a pour "11", alors il est nécessaire de d'abord recalculer v (la valeur de c) puis de recalculer w (la propriété de validité de la valeur de c). De même, x (la valeur de d) doit être recalculée avant de recalculer y (la propriété de validité de la valeur de d). Dans les deux cas, la validité de la valeur ne change pas pour "false" tant que le nouveau produit et la nouvelle somme n'ont pas été calculés en fonction du changement de a. Toutefois, il n'y a pas d'interdépendances entre v et x, de sorte que le produit et la somme peuvent se calculer dans l'un ou l'autre ordre.

Le sous-graphe pertinent exclut b et seul le champ in-degree du sommet a a une valeur de "0". Le sommet a est d'abord traité. Ce n'est pas un sommet calculé, donc aucun recalcul n'a lieu sur a, mais son retrait fait les sommets v et x ont un champ in-degree valant "0". Le sommet v est traité en second. Sa valeur change pour "121" et son retrait fait chuter la valeur du champ in-degree du sommet w à zéro. Le sommet x est traité ensuite, changeant sa valeur pour "21". Lorsque x est retiré, la valeur du champ in-degree de son voisin y tombe à zéro. Les quatrième et cinquième itérations de ce processus recalculent les validités des valeurs w et y, lesquelles changent à "false" pour toutes les deux.