Le but de cette section est de définir un processus de parcours générique de graphes d'objets qui soit performant. En effet, l'utilisation intensive de la réflexion que supposent les solutions précédemment étudiées induit une diminution des performances qui peut rapidement devenir inacceptable si l'on souhaite généraliser cette technique de parcours à un ensemble de processus d'un logiciel donné.

Les principes de cette approche sont les suivants:

Constructions des map

La construction des méthodes map est réalisé au moyen d'injection de bytecode par les classes IterableFactory et MakeIterable

Génération de l'itérateur

L'itérateur est contsruit selon les régles suivantes:

  1. Seules des classe concrètes seront instrumentées: les interfaces seront ignorées;
  2. L'itérateur parcours uniquement les champs non statiques ;
  3. La méthode iterator() retourne une instance spécifique à l'objet courant d'un Iterator parcourant l'ensemble des champs de l'objet. L'ordre des champs pour une classe est indertéminé.

Lorsqu'une classe instrumentée hérite d'une autre classe qui implante Iterable ou qui est suceptible de l'implanter (ie. parce qu'elle sera elle-même instrumentée), l'iterateur commence par déléguer l'itération à l'itérateur pour la super-classe, ce bien sûr de maniére récursive. Ce n'est que lorsque l'itérateur de la super-classe retourne false pour la méthode hasNext() que les éléments de la classe courante sont itérés.

L'usine à itérateurs transforme simultément un ensemble de classes ce qui permet de résoudre les problèmes d'héritage entre classe instrumentées plus simplement.

Contrôle du processus de génération

Le processus de génération est une simple interface permettant de produire les classes instrumentées à partir d'un ensemble de classe pré-existantes.

Stratégies de parcours

À la base des différentes stratégies de parcours se trouve l'interface Traversal. Cette interface extrêmement simple est rendu générique par le type de résultats qu'elle produit et elle spécifie une traversée d'un objet


package oqube.traversal;


public interface Traversal<R,T> {


   R traverse(T target);
}

L'utilisateur de ce mécanisme générique a vocation à fournir une ou plusieurs implantations de Traversal<R> qui réalisent une transformation ou effectuent une requête sur un certain type d'objets.

Sélection par le type

Une implantation de base de cette interface consiste à permettre de spécialiser le comportement du parcours en fonction du type des noeuds rencontrés, à la manière d'un visiteur. La classe Specialize combine plusieurs traversées de types compatibles unies par une même hiérarchie de classe mais spécialisée en fonction du type du paramètre de la méthode traverse(T). L'une de ces traversées est identifiée comme traversée par défaut et sera utilisée dans tous

Les contraintes sur les paramètres génériques permettent de s'assurer du respect des variances dûes à la redéfinition des méthodes en Java: covariance des paramètres, contravariance des valeurs de retours.

Le coeur de cette classe est constituée de la méthode extractTraversalType qui permet de récupérer l'instance de classe concrète par laquelle est paramétrée le parcours "intérieur". Il serait possible d'extraire cette information statiquement et d'instrumenter Specialize en conséquence pour éviter le surcoût de la reflexion mais au prix d'une complexité et d'une fragilité accrue des classes d'instrumentation.

Cette méthode analyse l'objet Traversal pour extraire la spécialisation de la méthode traverse(T) qui est produite à la compilation. L'objet Traversal est ensuite stocké avec la classe dans une Map, la classe servant de clé. 


  /*
   * extract parameter and return type Class for given traversal.
   */
  private Class extractTraversalType(Traversal<? extends R, ? extends T> inner2) {
    Class cls = inner2.getClass();
    Method[] ms = cls.getMethods();
    for (Method m : ms) {
      if ("traverse".equals(m.getName())) {
        Class[] pars = m.getParameterTypes();
        if (pars.length != 1) // not the right method
          continue;
        if (pars[0].equals(Object.class)) // not the right parameters
          continue;
        return pars[0];
      }
    }
    return Object.class;
  }

La méthode getTypedTraversal() permet de récupérer le type le plus proche (dans la hiérarchie de classe) d'un type donnée, c'est à dire du type réel de l'objet passé en paramètre de la méthode traverse(). Si aucune spécialisation n'est trouvée dans la hiérarchie de classes, alors c'est la méthode par défaut de parcours qui sera utilisée. 

previous
  private Traversal<? extends R, ? extends T> getTypedTraversal(Class k) {
    Traversal<? extends R, ? extends T> tr = null;
    while (tr == null && Object.class != k) {
      tr = typedTraversal.get(k);
      if (tr != null)
        return tr;
      k = k.getSuperclass();
    }
    return defaultTraversal;
  }
}

Ce mécanisme fonctionne mais n'est pas forcément trés efficace. Pour le rendre plus efficace, il est nécessaire d'intervenir au moment de l'instrumentation des classes parcourues afin de produire des classes Typeable, de la même manière que dans l'approche SYB il est nécessaire de rendre chaque type de donnée abstrait que l'on souhaite manipuler de manière générique instance de Typeable

Parcours à un niveau

Les objets parcourus étant potentiellement Iterable, une première étape dans la construction de parcours complexes consiste à pouvoir appliquer un parcours sur tous les fils d'un noeud, c'est-dire sur un niveau de profondeur.

C'est le rôle de la classe MapT qui encapsule un parcours et l'applique récursivement à chacun des fils d'un objet. 


public class MapT<R,T> implements Traversal<List<R>,T> {


  private Traversal<R,T> inner;


  public MapT(Traversal<R,T> tr) {
    this.inner = tr;
  }

Le résultat des différentes applications du parcours est concaténé dans une liste. La méthode traverse collationne les valeurs produites par le parcours intérieur lorsque celles-ci sont non nulles. La valeur de retour finale du parcours est la liste de toutes les valeurs produites durant le parcours. Si l'objet n'est pas itérable, une liste vide est simplement retournée. 

previous


 public List<R> traverse(T o) {
   List<R> res = new ArrayList<R>();
      try {
        // iterate over all elements in o if possible
        for (Object f : ((Iterable) o)) {
          R r = inner.traverse((T) f);
          if(r != null)
            res.add(r);
        }
      } catch (ClassCastException ex) {
        // non iterable - do nothing
      }
    return res;
  }
}

On notera qu'il est nécessaire de transtyper les éléments retournés par l'itérateur.

Parcours de graphes complets

Le parcours des graphes d'objets peut-être réalisé de nombreuses manières. Pour améliorer la souplesse et la généricité des objets réalisant les parcours, on offre plusieurs implantations différentes paramétrées par des types de structures de données selon l'ordre souhaité dans le parcours, et appliquant à chaque noeud rencontré un autre parcours soit de haut en bas, soit de bas en haut.

Top-down

L'opérateur everywhereTD applique un autre parcours Traversal<R,T> sur tous les noeuds d'un graphe d'objet à partir d'une racine. Le parcours secondaire est appliqué avant l'exploration des fils et par conséquent est réalisé de bas en haut.

Schématiquement, l'algorithme est le suivant:

Si C est une pile, alors on obtient un parcours en profondeur d'abord. Si C est une file (ie. une liste), alors le parcours est en largeur. Enfin, C peut-être un ensemble auquel cas l'ordre de parcours est l'ordre naturel des objets stockés ou un ordre arbitraire.

Une instance d'Everywhere stocke un second parcours et une collection de type Store<T> qui offre une interface simple et générique pour stocker des éléments. Ces objets peuvent être définis à la construction ou par appels aux méthodes get/set standards. Il est préférable de ne pas modifier ces objets durant l'exécution du parcours. 


public class EverywhereTD<R,T> implements Traversal<List<R>,T> {


  private Traversal<R,T> inner;


  private Store<T> todo;


  public EverywhereTD(Traversal<R,T> tr, Store<T> col) {
    this.inner = tr;
    this.todo = col;
  }

La méthode traverse collationne les valeurs produites par le parcours intérieur lorsque celles-ci sont non nulles. La valeur de retour finale du parcours est la liste de toutes les valeurs produites durant le parcours. 

previous


 public List<R> traverse(T o) {
    /* mark visited objects */
    Set<T> done = new HashSet<T>();
    List<R> res = new ArrayList<R>();
    todo.put(o);
    while (!todo.isEmpty()) {
      T cur = todo.get();
      if (done.contains(cur))
        continue;
      else
        done.add(cur);
      R r = inner.traverse(cur);
      if(r!= null)
         res.add(r);
      try {
        // iterate over all elements in o if possible
        for (Object f : ((Iterable) cur))
          todo.put((T) f);
      } catch (ClassCastException ex) {
        // non iterable - do nothing
      }
    }
    return res;
  }
}

Bottom-up

L'opérateur everywhereBU fait la même chose mais en invoquant l'opérateur de traversée intérieur de bas en haut. 


public class EverywhereBU<R,T> implements Traversal<List<R>,T> {

La traversée est ici réalisée non pas de manière itérative mais récursivement, afin que les noeuds fils soient traités avant les noeuds pères. La liste des noeuds déjà traités est ici stocké dans l'objet parcours et non plus dans 

previous
 public List<R> traverse(T o) {
   List<R> res = new ArrayList<R>();
   if(done.contains(o))
     return null;
   else
    done.add(o);
   /* first iterate */
   try {
       // iterate over all elements in o if possible
       for(Object f : ((Iterable)o)) {
         List<R> subs = traverse((T)f);
         if(subs != null)
           res.addAll(subs);
       }
   } catch (ClassCastException ex){ 
       // non iterable - do nothing
   }
   res.add(inner.traverse(o));
   return res;
  }
}

Parcours récursif

Les deux parcours présentés intégrent directement l'algorithme de traversée d'un graphe. Dans un certain nombre de cas, ils sont inadaptés. Reprenons l'exemple des expressions arithmétiques. On souhaite produire une représentation infixée de l'expression représentée par une instance quelconque de Expression. Pour ce faire, il est nécessaire de contrôler l'exploration pour les noeuds internes.

Dans le cas, fréquent, où la structure considérée est un arbre ou un graphe acyclique, il est plus simple d'appliquer une exploration récursive que d'utiliser les opérateurs de parcours définis ci-dessus.

On définit tout d'abord le parcours général à appliquer comme étant une spécialisation sur des types d'expression, produisant une chaîne de caractére. Pour éviter des recalculs inutiles, ce parcours est dérivé pour stocker des résultats intermédiaires (dans une table de hachage) et les retourner au besoin:

Le formattage est ensuite très simple: une spécialisation pour chaque opérateur suffit avec un appel récursif au formatteur de plus haut niveau pour les noeuds fils. 


  Traversal<String,Add> addfrm = new Traversal<String,Add>()
  {
     public String traverse(Add expr) {
        return format.traverse(expr.getLeft()) + " + " + format.traverse(expr.getRight()) ;
     }  
  };


  Traversal<String,Mult> mulfrm = new Traversal<String,Mult>()
  {
     public String traverse(Mult expr) {
        return format.traverse(expr.getLeft()) + " * " + format.traverse(expr.getRight()) ;
     }  
  };


  Traversal<String,Literal> litfrm = new Traversal<String,Literal>()
  {
     public String traverse(Literal expr) {
        return Integer.toString(expr.value);
     }  
  };


  Traversal<String,Var> varfrm = new Traversal<String,Var>()
  {
     public String traverse(Var expr) {
        return expr.var;
     }  
  };


  Traversal<String,Neg> negfrm = new Traversal<String,Neg>()
  {
     public String traverse(Neg expr) {
        return "-(" + format.traverse(expr.getSub())+ ")" ;
     }  
  };

Le test consiste in fine à compléter la boucle de récursion et à vérifier le formattage correct des sous-expressions. 

previous


  public void test01Format() {
    format.add(addfrm).add(mulfrm).add(litfrm).add(varfrm).add(negfrm);
    Add ad = new Add(new Mult(new Literal(10), new Var("x")), new Neg(
        new Literal(4)));
    String f = format.traverse(ad);
    System.err.println(f);
    assertEquals("10 * x + -(4)",f);
  }
}

Parcours filtrés

L'opérateur filter modifie un parcours en n'autorisant le parcours d'un objet que si celui-ci est accepté par un certain prédicat. Cet opérateur encapsule deux autre parcours: 


package oqube.traversal;


public class Filter<R,T> implements Traversal<R,T> {


  private Traversal<R,T> inner;


  private Traversal<Boolean,T> filter;


<<get-set>>


  public R traverse(T t) {
    if(filter.traverse(t)) 
       return inner.traverse(t);
    else
       return null;    
  } 
}

Parcours multiples

Les opérateurs anyOne et allOf appliquent un ensemble de parcours sur tous les noeuds sur lesquels ils s'appliquent. Leur comportement est symétrique: 


package oqube.traversal;


import java.util.List;
import java.util.ArrayList;


public class AnyOne<R,T> implements Traversal<R,T> {


  private List<Traversal<R,? extends T>> inners = new ArrayList<Traversal<R,? extends T>>();
<<any-one>>


  public R traverse(T t) {
    R ret = null;
    for(Traversal tr : inners) 
       try {
         ret = (R)tr.traverse(t);
         if(ret != null)
           return ret;
       } catch(ClassCastException e) {
         // NOP
       }
    return ret;
  } 
}


package oqube.traversal;


import java.util.List;
import java.util.ArrayList;


public class AllOf<R,T> implements Traversal<List<R>,T> {


  private List<Traversal<R,? extends T>> inners = new
  ArrayList<Traversal<R,? extends T>>();
<<all-of>>


  public List<R> traverse(T t) {
    List<R> ret = new ArrayList<R>();
    for(Traversal tr : inners) 
       try {
         R r = (R)tr.traverse(t);
         if(r != null)
           ret.add(r);
       } catch(ClassCastException e) {
         // NOP
       }
    return ret;
  } 
}

Exemple: l'évaluateur

Nous pouvons reprendre ici l'exemple de l'évaluateur décrit dans Visiteur pour illustrer cette approche.

Pour chacune des classes de notre hiérarchie d'expressions, on définit un parcours spécifique instanciant l'opération à réaliser en fonction du résultat courant. Ce résultat courant est une pile construite à partir de l'évaluation des différents termes de bas en haut. Il est par ailleurs nécessaire de disposer d'un environnement définissant les liaisons de variables libres dans l'expression. 




   Stack<Integer> stack = new Stack<Integer>();


   Map<String,Integer> env = new HashMap<String,Integer>();

Le code pour Add et Mult est relativement évident: il s'agit de la simple application des opérateurs arithmétiques correspondant. 

previous
   Traversal<Integer,Add> add = new Traversal<Integer,Add>() {
      public Integer traverse(Add add) {
        return stack.push(stack.pop() + stack.pop());
      } 
   };


   Traversal<Integer,Mult> mult = new Traversal<Integer,Mult>() {
      public Integer traverse(Mult mult) {
        return stack.push(stack.pop() * stack.pop());
      } 
   };

De même pour l'opérateur Neg : 

previous
   Traversal<Integer,Neg> neg = new Traversal<Integer,Neg>() {
      public Integer traverse(Neg neg) {
        return stack.push(-stack.pop());
      } 
   };

Les littéraux et les variables enfin, se traitent tout aussi aisément: 

previous
   Traversal<Integer,Literal> literal = new Traversal<Integer,Literal>() {
      public Integer traverse(Literal lit) {
         stack.push(lit.value);
         return lit.value;
      } 
   };


   Traversal<Integer,Var> var = new Traversal<Integer,Var>() {
      public Integer traverse(Var var) {
        int i = env.get(var.var); 
        stack.push(i);
        return i;
      } 
   };

Il ne reste plus qu'à définir un objet parcours correspondant à notre évaluateur. De toute évidence, le parcours doit être réalisé de bas en haut et en largeur d'abord. Les différents parcours individuels pour chacun des types d'expression sont composés par un opérateur AnyOne qui applique un opérateur parmi tous ceux disponibles. On notera la composition avec AllOf permettant d'afficher l'état de la pile durant l'évaluation. 

previous
  public void test01EvalOK() {
    AnyOne<Integer, Expression> one = new AnyOne<Integer, Expression>();
    one.add(add).add(mult).add(neg).add(literal).add(var);
    AllOf allof = new AllOf();
    allof.add(one).add(new Traversal() {


      public Object traverse(Object target) {
        System.err.println(stack);
        return null;
      }


    });
    EverywhereBU<Integer, Expression> bu = new EverywhereBU<Integer, Expression>(
        allof);
    env.put("x", 12);
    Add ad = new Add(new Mult(new Literal(10), new Var("x")), new Neg(
        new Literal(4)));
    List<Integer> res = bu.traverse(ad);
    assertTrue(!res.isEmpty());
    System.err.println(res);
    assertEquals((int) 116, (int)stack.pop());
   }
}

Article sur l'utilisation de XPath dans Java5 avec comparaison des performances. http://searchwebservices.techtarget.com/tip/1%2c289483%2csid26_gci1166338%2c00.html

Footnotes: [1] Ceci constitue un cas particulier du schéma plus général

d'implantations des classes de types du langage Haskell (type classes) en Java: au lieu de déclarer explicitement un type comme implémentant telle ou telle interface, on définit une interface et d'éventuelles implantations par défaut qui sont injectées a posteriori dans le type, en faisant une implantation (on parle d'instance en Haskell) de l'interface considérée.

© 2006

\Nouveau et intéressant