XPATH pour SAX

Par Philippe PRADOS - 2010
www.prados.fr

XML est un langage de description de document textuel formidable par sa simplicité, mais pas toujours facile à manipuler. Une vue superficielle ne fait apparaître que des marqueurs ouverts ou fermés, et quelques zones de texte. C'est en réalité, beaucoup plus complexe. Un arbre XML est composé de différents nœuds, de différents types, reliés les uns aux autres par des agrégations ou des relations via l'emploi des attributs ID et IDREF. Ce n'est pas un langage de description de structure, mais de documents textuels. Une représentation DOM (Document Object Model) permet de naviguer entre les nœuds de différents types.

Pour permettre des requêtes dans un arbre XML, deux syntaxes sont utilisées : la syntaxe des feuilles de styles et celle de XPATH. Elles répondent à des besoins similaires : trouver un pattern dans la structure XML, pour appliquer un style ou pour manipuler les données. Il est même envisageable d'écrire un convertisseur de la syntaxe de sélecteur CSS vers la syntaxe XPATH et réciproquement.

Pour pouvoir identifier les patterns décrits par une requête XPATH, il est indispensable de disposer de l'intégralité de l'arbre XML en mémoire. En effet, une requête XPATH permet de retourner un ensemble de nœuds, avec leurs relations avec les autres nœuds. La syntaxe permet également d'exprimer des patterns faisant intervenir les relations de filiation d'un nœud par rapport à un autre.

On trouve plusieurs implémentations de requêtes XPATH s'appuyant sur DOM, Jaxen en est un exemple. Utiliser DOM peut être pénalisant pour les performances et la consommation mémoire notamment dans les périphériques en mobilité. Est-il nécessaire d'analyser toute une page XHTML et de la transformer en DOM pour y rechercher quelques informations à partir d'une requête XPATH ? Pas toujours.

Nous nous proposons de rédiger un requêteur XPATH n'imposant pas une analyse complète du document XML pour pouvoir y extraire les nœuds recherchés. Nous voulons pouvoir appliquer simultanément plusieurs requêtes XPATH lors d'une analyse du flux XML par l'API SAX. Cette dernière, à la différence de DOM, génère des événements au fur et à mesure des marqueurs.

Pour cela, il va falloir faire quelques compromis. D'une part, les nœuds sélectionnés ne pourront pas être en relation avec tous les autres nœuds. Ils seront orphelins et sans descendance. En revanche, les fils de type text() seront présents, car ils sont généralement intéressants pour les programmes.

D'autre part, certaines requêtes XPATH ne pourront pas être analysées, car elles dépendent d'un contexte qu'il n'est pas possible de connaître sans avoir accès à l'intégralité de l'arbre DOM.

Néanmoins, la très grande majorité des requêtes XPATH n'ont pas besoin de ces subtilités. A défaut, si une requête particulière ne peut être analysée par notre programme, il sera toujours possible d'appliquer le plan B, consistant à utiliser les analyseurs s'appuyant sur un arbre complet XML en DOM.

La syntaxe XPATH

Commençons par analyser la syntaxe d'une requête XPATH. Il existe plusieurs formes : les requêtes complètes, partant de la racine pour arriver vers le nœud recherché, et les requêtes partielles, proposant un pattern de relation d'un nœud par rapport aux autres.

Les requêtes partielles peuvent être très complexes, et obliger à avoir recours à des retours arrière dans l'analyse. Ce n'est pas possible lorsqu'on manipule un flux XML. Par exemple, la requête suivante : « //abc/def//ghi/jkl » indique qu'il faut rechercher un marqueur abc possédant un fils def, qui lui-même, possède dans une de ses branches, un marqueur ghi avec un fil jkl. Cette syntaxe est trop complexe pour notre analyseur. Elle oblige à un retour arrière lors de l'analyse de la deuxième partie. En revanche, un modèle comme « //abc/def » est parfaitement valide et implémentable.

La syntaxe XPATH de base permet de sélectionner des nœuds classiques, des nœuds attributs (oui, oui, ce sont des nœuds également), des nœuds text() ou des nœuds spéciaux comme les commentaires ou les processings-instructions. Ces dernières étant rares, la syntaxe ne les traitera pas, de même que les espaces de noms.

Les nœuds attributs peuvent être identifiés par leurs noms (@href) mais peuvent également être génériques (@*).

Chaque nœud de la syntaxe peut être enrichi de prédicats, encadré de crochets (img[@href='toto.gif']). Cela permet de sélectionner certains nœuds, en plus de leurs identifiants. La syntaxe des prédicats permet également beaucoup de choses, comme la détection de certains nœuds fils, la position du nœud dans son groupe ou différentes syntaxes de comparaison sur les valeurs des attributs. Nous allons nous focaliser sur les attributs et sur la position des nœuds dans leurs groupes.

Voilà le décor planté, nous pouvons nous mettre au travail. Nous allons réaliser le composant XPATH4SAX, permettant d'analyser une grande partie des requêtes XPATH à l'aide d'un analyseur SAX. Le temps d'analyse et la consommation mémoire est alors indépendante de la taille du flux.

Analyse du XPATH

<>La première chose à faire est d'analyser la syntaxe XPATH textuelle, pour la transformer en un modèle mémoire facilitant l'analyse des flux XML. Il faut découper l'expression en tokens, séparés par des slashs.

String[] splits = xpath.split("/");

Ensuite, il faut l'analyser individuellement chaque token pour identifier s'il s'agit d'un nom de nœud, d'un nom d'attribut ou d'une chaine de caractères, et extraire l'éventuel prédicat encadré de crochet s'il est présent. Une expression régulière va nous aider :

Pattern predicatRegExpr_ = Pattern.compile("([^\\[]+)(\\[(.*)\\])?");

Si on souhaite être efficace en termes de performance, il n'est pas conseillé de construire un objet avec plusieurs attributs pour chaque segment de la syntaxe. Il est beaucoup plus rapide de construire deux tableaux en parallèle, de même taille, avec dans l'un, les noms des nœuds, dans l'autre les prédicats à appliquer pour qualifier le nœud. L'utilisation d'un modèle objet n'est pas toujours compatible avec les performances.

Analyse du prédicat

Il faut maintenant analyser chaque prédicat. Ce n'est pas simple car la syntaxe utilise différents opérateurs, des priorités, etc. De nombreux papiers ont été écrits au sujet de ce genre d'analyse. Nous allons utiliser une approche un peu brutale, mais finalement assez simple pour gérer les priorités des opérateurs.

Le prédicat va être découpé en tokens, en exploitant les différents séparateurs de la syntaxe (/()[]=<> ) auxquels on ajoute la prise en compte des chaînes de caractères encadrées par des quotes ou des doubles quotes. Ce découpage va retourner, soit des mots, soit des ponctuations, soit des chaînes de caractères.

private static ArrayList<String> parseString(String line)
{
  ArrayList<String> rc=new ArrayList<String>(5);
  final int length=line.length();
  int start=0;
  int stop=0;
  for (int pos=0;pos<length;++pos)
  {
    char c=line.charAt(pos);
    if ("/()[]=<> ".indexOf(c)!=-1)
    {
      if (start!=stop) rc.add(line.substring(start,stop));
      if (c!=' ') rc.add(line.substring(pos,pos+1));
      start=stop=pos+1;
    }
    else if (c=='"')
    {
      while (++pos<length)
      {
        if (line.charAt(pos)=='\"')
        break;
      }
      rc.add(line.substring(start,pos+1));
      start=stop=pos;
    }
    else if (c=='\'')
    {
      while (++pos<length)
      {
        if (line.charAt(pos)=='\'')
          break;
      }
      rc.add(line.substring(start,pos+1));
      start=stop=pos;
    }
    else
      ++stop;
  }
  if (start!=stop) rc.add(line.substring(start,stop));
  return rc;
}

Nous pouvons alors lancer une analyse récursive, consistant à consommer chaque token et à le placer dans une pile, sauf si ce dernier possède une priorité supérieure. Chaque opérateur possède une priorité. Les tokens standards tel que les chaînes de caractères, les noms d'attributs, possèdent la priorité zéro. Les opérateurs de comparaisons, la priorité un ; les opérateurs or et and, la priorité deux.

Le processus est initialisé en demandant de partir du premier token, et d'avancer tant que le token suivant possède une priorité inférieure ou égale au maximum des priorités déjà rencontrées. Ainsi faisant, toute l'expression sera analysée.

Prenons l'exemple de l'analyse du prédicat suivant : [@a='abc' or @b!='def'].

L'algorithme va consommer le premier token, le nom d'un attribut. Ce dernier va permettre d'ajouter dans la pile, une closure (un traitement porté par un objet) permettant de retourner la valeur d'un attribut dans un nœud, respectant l'interface Predicat ci-dessous :

static interface Predicat
{
  public abstract Object value(String uri, String localName,
    String qName, Attributes attributes);
}

Le token suivant est analysé. Il s'agit de l'opérateur égal. Si la priorité maximum est inférieure à 1, le niveau de priorité du égal, alors le processus s'interrompt en signalant qu'il s'est arrêté juste avant l'opérateur. Ce n'est pas le cas dans l'immédiat, car la priorité maximum autorisée au départ est de 2. Le traitement de l'opérateur égal continue alors, en demandant de consommer ce qu'il y a à droite, tant que la priorité n'est pas supérieure à la priorité du égal, donc strictement inférieure à 1. Un appel récursif est invoqué pour continuer l'analyse. Le token 'abc' est analysé et est inséré dans la pile. Nous avons alors dans la pile, sur le sommet, la chaîne de caractère 'abc' et en dessous, une closure nous permettant de récupérer la valeur de l'attribut @a. Le token suivant est un or. Or (c'est le cas de le dire), ce dernier possède une priorité de 2, supérieure à la priorité du égal. Donc, il refuse d'être analysé et interrompt le processus en indiquant qu'il s'est arrêté juste avant, à savoir sur la chaine de caractère. Nous remontons alors à l'appelant, à savoir le traitement de l'opérateur égal. Celui-ci possède alors dans la pile, l'expression de droite jusqu'au or, et en dessous, l'expression de gauche. Il peut dépiler tout cela pour ajouter dans la pile, une nouvelle closure, chargée d'invoquer la closure de gauche et la closure de droite pour comparer leurs valeurs. Cette closure se chargera d'exécuter la comparaison entre un attribut et une valeur, ou la valeur d'un attribut avec celle d'un autre attribut.

Le processus peut reprendre là où il s'était arrêté, à savoir sur le traitement du or. Il procède de même pour demander l'analyse de l'expression à sa droite. Cette dernière va consommer l'attribut @b, puis l'opérateur différent. Ce dernier va consommer son expression de droite, la valeur 'def', avant d'injecter dans la pile,une closure gérant l'opérateur. Au retour, l'opérateur or récupère bien une closure pour sa droite, et peut alors consommer la pile pour y ajouter une closure traitant du or.

Avec ce processus, une pile est alimentée au fur et à mesure, puis consommée par les opérateurs. Il ne doit y rester qu'une seule closure au final, celle représentant le prédicat, avec l'opérateur racine.

Voici un extrait de cet algorithme. Comme vous pouvez le constater, les closures sont rédigées à l'aide de classes anonymes, lorsqu'elles n'ont pas besoin d'être utilisées par ailleurs.

private static int parse(ArrayList<String> tokens, int start, int priomax,
    Stack<Predicat> stack) throws XPathSyntaxException
{
  for (int i = start; i < tokens.size(); ++i)
  {
    final String token = tokens.get(i);
    if (token.charAt(0) == '@')
    {
      stack.push(new AttributPredicat(token));
    }
    else if ((token.charAt(0)=='\'') || (token.charAt(0)=='\"'))
    {
      final String value = token.substring(1,token.length()-1);
      stack.push(new Predicat()
      {
        public Object value(String uri, String localName,
            String qName, Attributes attributes)
        {
          return value;
        }
        public String toString()
        {
          return "'" + value + "'";
        }
      });
    }
    else if ("0123456789".indexOf(token.charAt(0)) != -1)
    {
      final int integer = Integer.parseInt(token);
      stack.push(new DoublePredicat(integer));
    }
    else if ("=".equals(token))
    {
      if (priomax < 1)
        return i – 1; // Prio max trop faible, donc retour à l'appelant
      i = parse(tokens, i + 1, 0, stack); // Appel récursif à droite.
      final Predicat right = stack.pop();
      final Predicat left = stack.pop();
      stack.push(new Predicat()
      {
        public Object value(String uri, String localName,
            String qName, Attributes attributes)
        {
          Object lval = left.value(uri, localName, qName, attributes);
          Object rval = right.value(uri, localName, qName, attributes);
          if ((lval == null) || (rval == null))
            return false;
          return lval.equals(rval);
        }
        public String toString()
        {
          return left.toString() + "=" + right.toString();
        }
      });
    }
    …
  }

Au retour de cette fonction, on obtient un arbre de closures, permettant d'appliquer un filtre sur les nœuds candidats.

Il y a une petite subtilité dans la rédaction des prédicats. En effet, un prédicat composé uniquement d'une valeur numérique exprime la position d'un nœud, et non la comparaison d'une valeur. Il faut donc, au terme de l'analyse, vérifier si la closure retournée n'est pas la traduction d'une valeur numérique. Si c'est le cas, il faut la transformer pour une autre closure traitant de la position du nœud.

Il n'est finalement pas bien compliqué de traduire une expression complexe en closure, à condition de bien choisir la stratégie sous-jacente.

Nous avons alors, un tableau avec les noms des nœuds à rechercher dans le flux, et en parallèle, un tableau avec les closures à appliquer sur chaque nœud pour savoir s'il faut les garder.

Implémentation du SAX

Nous avons analysé les requêtes XPATH pour préparer le terrain. Il faut maintenant exploiter ces informations lors de l'analyse d'un flux par SAX, à base d'évènements déclenchés à chaque nouveau nœud détecté dans le flux. Contrairement aux analyseurs XPATH classiques, nous allons rechercher simultanément plusieurs requêtes XPATH. En effet, il n'est pas question de parcourir plusieurs fois le flux, sous prétexte d'avoir plusieurs requêtes à appliquer.

Notre XMLHandler sera donc initialisé avec une collection de XPATH. Charge à lui de jeter un événement pour chaque nœud correspondant à une des requêtes. L'événement doit, bien entendu, signaler de quel XPATH il s'agit. Il doit également fournir des informations sur le nœud découvert. Ce dernier ne sera construit en mémoire que s'il correspond à une ou plusieurs requêtes. Pour faire simple, construisons des nœuds DOM orphelins avant de générer l'événement.

Comment fonctionne l'algorithme ? Pour chaque nœud découvert par l'analyse SAX, il faut vérifier s'il ne correspond pas à une des requêtes. Si la requête est complète, c'est-à-dire si elle commence par un simple slash, alors, soit la requête est rejetée, soit le curseur associé à la requête avance d'un cran. Si le curseur est en butée, c'est que l'expression est valide.

C'est plus compliqué si la requête est relative. En effet, si le nœud courant ne « match » pas, il faudra essayer avec le nœud fils. En revanche, s'il « match », alors l'analyse complète peut commencer. Le point de départ est mémorisé. En cas de réussite ou d'échec, le curseur associé à la requête avance ou recule.

Par chaque nœud potentiel, la closure correspondante est appliquée avant de confirmer sa validité.

Comme il est important de pouvoir avoir le contenu textuel d'un nœud, si un candidat est découvert, un flag permet de signaler qu'il faut alors mettre au chaud tous les nœuds de type « text » fils de ce dernier. Les autres nœuds fils sont ignorés, pour ne pas avoir à reconstruire l'intégralité de l'arbre DOM.

L'usage est relativement simple. Un handler invoque la méthode findXpathNode() pour chaque nœud trouvé. Un premier paramètre indique l'expression correspondante. Le deuxième correspond à un nœud ou à une valeur String ou Integer.

XPathXMLHandler handler=new XPathXMLHandler()
{
  @Override
  public void findXpathNode(SAXXPath xpath, Object node)
  {
    System.out.println("node="+node);
  }
};
handler.setXPaths(XPathXMLHandler.toXPaths("//div[@id='Me']/p"));
SAXParser parser = SAXParserFactory.newInstance().newSAXParser();
parser.parse(new InputSource(new StringReader(xml)), handler);

Pour quoi faire ?

Quelques benchmarks rapides montrent que ce module est six fois plus rapide que l'approche traditionnelle sur un tout petit flux XML de 2 Ko. Plus il y a de requêtes XPATH à traiter et plus le volume du flux est important, plus les performances sont bonnes. Et cela, en économisant la mémoire, donc le travail du ramasse-miettes.

Il est alors possible de l'utiliser pour extraire de l'information d'une page XHTML ou d'un flux XML. Si la page d'un site est en HTML, non conforme à XHTML, des outils comme nu.validator.htmlparser sont capables d'analyser la page en générant des évènements SAX. XPATH4SAX est donc directement compatible. Il suffit de fournir le XPathXMLHandler.

Avec un téléphone portable, si on désire faire de nombreuses requêtes HTTP pour extraire des informations, il n'est pas raisonnable d'utiliser l'approche DOM. La consommation mémoire risque d'être trop importante. De même, si on est capable d'extraire les informations qui nous intéressent plus rapidement, cela économise la batterie.

XPATH4SAX a été conçu pour une application pour les téléphones Android, avec pour objectif d'améliorer l'empreinte mémoire, la consommation électrique et les performances. Moyennant le sacrifice de quelques syntaxes, il est parfaitement possible d'extraire les informations pertinentes d'un flux (X/HT)ML.

L'intégralité des sources est disponible en libre téléchargement, sous licence Apache v2, ici : http://xpath4sax.googlecode.com.

Le code est très petit. Les informations présentes dans cet article vous permettront de relire et/ou d'enrichir le moteur.