Category Archives: pattern

S’exprimer régulièrement (Partie 3)

Dans cette troisième et dernière partie sur les expressions régulières en Java. Je vais aborder deux thèmes assez peu utilisés et pourtant très utiles.

  • Le premier, dans la continuité des groupes ce sont les constructions de look behind et look ahead.
  • Le deuxième point abordera le support de Unicode dans nos expressions régulières.

Avoir le coup d’œil

C’est bien de ça dont il s’agit; ce feature, introduit grâce aux groupes non-capturant, permet de vérifier si une autre expression matche avant ou après une expression capturante  sans consommer de caractères. Il y a 4 constructions de types :

  • Les constructions look ahead
    1. (?=X) X, via zero-width positive lookahead : L’expression cherche à matcher X après la position courante et sans consommer.
    2. (?!X) X, via zero-width negative lookahead : L’expression cherche à ne pas matcher X après la position courante et sans consommer.
  • Les expressions look behind
    1. (?<=X) X, via zero-width positive lookbehind : L’expression cherche à matcher X avant la position courante et sans consommer, ou X est une expression régulière de longueur connue.
    2. (?<!X) X, via zero-width negative lookbehind : L’expression cherche à ne pas matcher X avant la position courante et sans consommer, ou X est une expression régulière de longueur connue.

Ces assertions ressemblent aux bornes \b elles ont un fonctionnement similaire mais plus complexes. Passons aux tests pour voir leur fonctionnement.

Les groupes de look ahead

Par exemple avec le look ahead positif :

Ligne 10, on veut chopper les lignes qui se terminent par Label avec une expression usuelle. Si on ne voulais pas la partie Label, alors il aurait fallu créer un autre groupe autour de \w+, cependant le curseur aura consommé les caractères. L’alternative est d’utiliser un look ahead positif, c’est ce qu’on a à la ligne 15, ici le curseur s’arrête après le r juste avant Label.

Notez que dans l’exemple ce qui est retourné est le groupe 0 (ligne 21), c’est à dire l’ensemble de ce qui est capturé par toute la regex. Ceci illustre à nouveau que les groupes de look ahead/begind ne capturent pas (méthode positiveLookAhead, ligne 15). C’est assez pratique pour faire des sélections ou des remplacements, dans Eclipse par exemple.

Si typiquement on cherche des termes qui ne se terminent pas par Label. On écrira simplement :

L’expression chope en premier static, tout simplement parce que cette partie du texte matche le fait qu’il n’y a pas Label qui suit, si on veut chopper le nom d’une variable alors on peut ajouter des constructions de look behind. C’est ce qu’on regarde juste après.

Faisons d’autres tests :

À la ligne 5 attention, comme il y a devant un quantificateur gourmand \w+ et en dehors de la construction lookahead, celui-ci va avaler la chaîne complète aStaticVarLabel et comme tous les caractères auront été consommés le lookahead négatif (?!Label) sera également valide. La ligne 6 corrige ça en incluant la construction w+ à l’intérieur du lookahead.

Les groupes de look behind

Donc là j’ai préfixé la regex par ce que je voulais voir juste avant. De la même manière si on ne veut pas d’un terme, on utilisera un look behind négatif (?<!), par exmple si on ne veut pas de String.

Observez ici qu’il y a deux constructions adjacentes look behind, l’une positive l’autre négative, ce qui illustre encore mieux que ces constructions ne consomment pas la séquence de caractères.

Observez également que l’expression ici est de longueur connue : le \w{4,8} ne prend que de 4 à 8 caractères. Il n’est pas possible d’écrire un look behind avec un quantificateur où la longueur n’est pas connue, la construction suivante est fausse et provoquera une erreur de syntaxe : (?<!private \w+ ). C’est une limite technique qui impose aux groupes de look behind d’avoir une longueur fixe ou calculable; les quantificateurs bornés {n,m}, l’option ? ou l’alternative | tombent dans cette catégorie. Ainsi on pourrait écrire :

Et donc par opposition les quantificateurs * et + ne sont pas autorisés dans les lookbehind.

Attention aux quantificateurs sur une même classe de caractère

Bon, il existe certains cas un peu délicats ou les caractères adjacents d’une séquence font partie de la même classe. Dans le bout de texte utilisé dans le premier exemple, les noms variables correspondent typiquement à ça:
anotherStaticVarLabel
Le nom de la variable appartient à la classe de caractère [a-zA-Z0-9_] ou encore à \w.

Lorsqu’on faisait un positive look ahead, le quantificateur \w+ va chercher à matcher l’ensemble des caractères de cette classe, ce qui veut dire que \w+ va matcher et consommer les caractères anotherStaticVarLabel. Du coup lorsque la construction (?=Label) cherche à matcher Label, elle n’y arrive pas. Ce n’est pas grave, avec le backtracking l’expression \w+ reviens en arrière jusqu’à ce que (?=Label) matche.

L’histoire est différente avec un negative look ahead; une fois que la partie \w+ a matché anotherStaticVarLabel, le curseur est positionné après le l. Maintenant le moteur teste (?!Label), qui cherche donc à ne pas matcher Label, normal c’est une négation. Et là ça marche, cette partie de l’expression ne peut plus trouver Label, donc la construction est validée.

Bref ce n’est pas ce qu’on veut, nous voulons par exemple identifier les variables qui ne sont pas suffixées par Label !

Pour ne éviter ce problème, il faut placer le groupe look ahead négatif avant \w+. Cela ne posera pas de problème étant donné que les look ahead ne consomment pas la séquence de caractères. Ainsi en écrivant :

La première partie est un look behind pour avoir ce qui est après String , le deuxième groupe est le look ahead dont je parlais, ce groupe cherche à ne matcher \w+Label, si les derniers caractères Label de la regex ne sont pas trouvés alors c’est bon. Finalement l’expression se termine par \w+. L’astuce donc se fait en deux étapes:

  1. Déplacer le look ahead avant l’expression qui consomme les caractères et qu’on veut capturer, ici \w+
  2. Faire précéder dans le look ahead négatif l’expression qu’on veut capturer, ici le groupe est devenu (?!\w+Label), grâce au backtracking dans ce groupe une valeur aStaticVarLabel ne sera pas matchée (negative look ahead).

Voilà pour les possibilités de look ahead et de look behind dans les expressions rationnelles.

Passons maintenant au support Unicode par la classe Pattern.

Unicode

En quoi Unicode est intéressant dans nos regex en Java?

  1. Unicode est supporté nativement par Java, le format interne des String est Unicode.
  2. Unicode nous apporte des classes, des catégories ou des propriétés de caractères bien plus étendues que les classes ASCII couramment utilisées.

Juste pour une lettre

Par exemple, j’ai une application US qui vérifie que le texte entré est uniquement composé de lettres. Facile avec la regex suivante:

[a-zA-Z]

Maintenant je me dit que je souhaiterais avoir des clients français! Aille! L’approche facile mais peu élégante est d’écrire une regex dans ce genre :

[a-zA-Zéèêïôàù]

Et encore j’oublie les accents sur les majuscules et encore d’autre caractères spéciaux, alors qu’ils ont pourtant pleine valeur orthographique sur les majuscules également. S’il fallait en plus gérer le grec, l’allemand, l’espagnol, nous aurions du mal avec une telle expression régulière. Et le raccourci w n’aide pas vraiment non plus! C’est là que viennent les classes de caractère Unicode, pour identifier un caractère qui est une lettre, on écrira très simplement :

\p{L}

Ainsi en Java on aura par exemple

IntelliJ est très bien, il fourni l’auto-complétion dans les regex c’est assez pratique à l’intérieur du code, mais pas d’explication sur la signification de ces blocs de caractères Unicode. Eclipse n’en parlons pas, et NetBeans je ne sais pas. En tous cas on trouve une réponse ici ou encore à propos des blocs Unicode:

Abréviation reconnue par Pattern Signification
L Letter
Lu Uppercase Letter
Ll Lowercase Letter
Lt Titlecase Letter
Lm Modifier Letter
Lo Other Letter
M Mark
Mn Non-Spacing Mark
Mc Spacing Combining Mark
Me Enclosing Mark
N Number
Nd Decimal Digit Number
Nl Letter Number
No Other Number
S Symbol
Sm Math Symbol
Sc Currency Symbol
Sk Modifier Symbol
So Other Symbol
P Punctuation
Pc Connector Punctuation
Pd Dash Punctuation
Ps Open Punctuation
Pe Close Punctuation
Pi Initial Punctuation
Pf Final Punctuation
Po Other Punctuation
Z Separator
Zs Space Separator
Zl Line Separator
Zp Paragraph Separator
C Other
Cc Control
Cf Format
Cs Surrogate
Co Private Use
Cn Not Assigned
- Any*
- Assigned*
- ASCII*

Matcher les caractère d’un alphabet seulement

Si je veux vérifier que mon texte appartient à de l’hébreu ou du chinois c’est faisable. Dans Unicode il faut remarquer qu’il y a plusieurs notion pour les “alphabets”; il y a les Blocs et les Scripts, cependant le moteur de Java qui se base essentiellement sur le moteur de perl, ne gère pas les scripts, donc on se contentera des blocs.

Ci-dessous je teste l’appartenance à un bloc :

Plusieures choses sont à remarquer :

  • Le nom de l’alphabet est précédé par In
  • Pour avoir une phrase en français on a très vite plusieurs blocs LATIN EXTENDED A pour le graphème œ, LATIN 1 SUPPLEMENT pour le ê e accent circonflexe.
  • D’autres alphabet sont plus pratique à utiliser comme l’hébreu, le cyrillique, le grecque, etc.
  • L’utilisation des alphabet Chinois, Japonais, Coréen peut aussi soulever des question surtout quand on ne le parle pas ;)

A noter également :

Sur les deux dernières lignes noter que j’ai utilisé le code hexadécimal UTF-16 (j’y reviendrais après) pour obtenir les caractères et (Chi en chinois traditionnel, Ki avec l’alphabet Hiragana). Pourquoi? Parce que Unicode c’est bien joli mais dans le monde réel il y a des limitations, pour moi il s’agit de la police de caractère de mon éditeur qui ne possède pas ces blocs de caractères défini. Peut-être aurez vous des limitations sur la police de votre navigateur. A noter également que l’encodage de vos fichier peut faire mal quand on joue avec les caractères en dehors du latin basique.

Chi (Chinois traditionnel) Ki (Alphabet Hiragana)
Chi (0x6C23) Ki (0x304D)

On peut encore s’amuser

Pour revenir dans les choses qui nous intéresse, imaginons que nous voulions compter tous les caractères accentués dans un texte. Le bloc Unicode \p{L} n’est pas approprié, mais comme je l’ai dit avec Unicode on peut accéder aux propriété d’un caractère.

Déjà pour commencer il faut savoir qu’en Unicode, un graphème comme é peut correspondre à un seul caractère é ou à deux caractères e suivi du modificateur accent grave. Cela dépend de la source, mais ces cas sont probables.

Ainsi dans les lignes précédentes pour rechercher un graphème représenté par un seul codepoint, il faudra aller le chercher dans le bloc idoine, ici LATIN 1 COMPLEMENT, 0x00E9 est le codepoint du caractère é. La forme décomposée de é est e (0x0065) suivi du modificateur accent grave (0x0301).

Pour matcher cette forme décomposée du graphème, il faut simplement écrire \p{L}\p{M}. Il est toujours possible d’affiner l’expression en choisissant des propriétés plus précises (cf. Tableau plus haut, voire la référence Unicode). Du coup pour matcher n’importe quelle forme d’un graphème on pourra écrire l’expression de la ligne 6.

Enfin rapidement on peut exprimer les compléments à la manière standard avec [^\p{Lu}] ou plus simple avec un grand P \P{Lu}. Les intersections entres les classes / propriétés Unicode se font sans problèmes également :

Petit retour sur les base de Java

Java gère nativement Unicode, les String sont encodées en UTF-16. Ce qui explique par conséquent que lorsque je veux exprimer un caractère sous forme hexadécimale, il faut l’écrire dans sa forme UTF-16.

Ces assertions marches toutes mais il faut noter que \u00E9 est compris par le compilateur et remplacera \u00E9 par é, alors que dans la forme ou le backslash est échappé \u00E9 le compilateur ne fera rien. Ce sera au moteur Pattern de traiter la chaîne.

La plupart des caractères tiendront dans le type primitif char qui fait donc 16 bits (voilà pourquoi Java gère nativement l’UTF-16), cependant il peut arriver que certains caractères demandent davantage. Character.toChars(int) prend donc un codepoint représenté par en entier, qui fait en Java 32 bits pour exprimer Unicode en UTF-32 donc. Dans le code ci-dessus la 3ème assertion montre d’ailleurs que Java doit splitter le caractère en question sur deux char.

De la même manière l’encodage change naturellement la taille d’un tableau de byte (8 bits).

Bilan

Voilà cet article clos la série que je voulais écrire sur les expressions régulière. Il y a probablement d’autres arcanes à connaître. Mais sur cette série le but était de couvrir ce que le moteur Java nous permet de faire. Je pense que comprendre le fonctionnement du moteur en particulier sur le backtracking, la manière du moteur de tester une expression, la manière dont le moteur parcoure / consomme les caractères en entrée, sont des facteurs clé pour réussir une bonne expression. Cette compréhension est d’autant plus importante quand celles-ci sont liée à des éléments de performance.

Les constructions apportées avec Unicode, même limitées, ouvrent certaines possibilités intéressantes, mais clairement il y a du travail à faire : Unicode n’est manifestement pas simple.

Références

S’exprimer régulièrement (Partie 2)

La première partie de cette mini-série s’est focalisée sur une petite intro, je n’ai pas vraiment insisté sur les bases des expressions régulières, j’ai juste abordé les ancres et les options, et j’ai parlé de certaines astuces à connaître. La suite de cette série continue comme prévu sur les constructions suivantes :

  • Les groupes qui ne capturent pas (non-capturing group)
  • Les backreferences
  • Les autres quantificateurs
    • Les quantificateurs gourmands (dits greedy quantifiers)
    • Les quantificateurs paresseux (dits lazy quantifiers ou comme le dit la javadoc de Pattern reluctant quantifiers)
    • Les quantificateurs possessifs (dits possessive quantifiers)
  • Le backtracking

Certaines des constructions présentées ici démontrent que le moteur de regex de java fait partie des toutes dernières générations. Afin de mieux expliquer la manière de fonctionner des quantificateurs, je vais faire un tour sur la technique de backtracling du moteur de regex, feature essentiel pour faire fonctionner ces constructions.

Et aussi pourquoi certaines expressions régulières sont risquées en ce qui concerne les performances.

Les groupes qui ne capturent pas

Pour comparer voici les groupes capturant

Vous connaissez certainement déjà les groupes, par exemple :

Dans l’expression ci-dessus, il y a trois groupes définis dans l’expression rationnelle.

  • ([a-z]+) ( ?\[[a-z]+\] ([a-z]+))+ qui est donc le groupe 1
  • ([a-z]+) ( ?\[[a-z]+\] ([a-z]+))+ qui est le groupe 2
  • ([a-z]+) ( ?\[[a-z]+\] ([a-z]+))+ enfin qui est le groupe 3 il est défini à l’intérieur du groupe 2

Le moteur de l’expression régulière enregistre juste la référence du groupe, et lorsque qu’il y a récursion sur les groupes, le groupe prend la valeur du dernier contenu matché. Ainsi dans cet exemple après un premier appel à find, l’ensemble de la chaîne de caractère a été consommée, et les groupes 2 et 3 son valorisés par :

En plus de ça, les références aux groupes sont limitées à 10. Honnêtement c’est rare d’avoir besoin de plus de 10 groupes. Dans ce cas il faut splitter la chaîne ou la regex.

Cependant on peut en partie s’arranger pour que les groupes qui ne nous intéressent pas ne soit pas référencés, il faut utiliser un groupe on-capturant.

Les non-capturing groups

C’est presque à la fin de la javadoc de la classe Pattern. Ils se construisent de la manière suivante :

Pour reprendre l’exemple plus haut, le groupe 2 n’est pas vraiment utile à notre expression régulière. Du coup on pourrait écrire :

Il y a alors 2 groupes uniquement qui sont référencés.

Les constructions avancées des groupes sont la preuve que le moteur fait partie des dernière générations.

Les backreferences

Les références des groupes qui capturent, elles sont utilisées dans les moteurs de recherche et de remplacement. Typiquement avec Eclipse, le format utilisé pour faire référence à un groupe est :

Ou X est le numéro du groupe, sa référence.

En fait cette notation peut également s’utiliser à l’intérieur d’une expression régulière, c’est ce qu’on appelle donc une backrefrence. Pour back; parceque le groupe doit déjà être défini et matché pour être référencé dans une regex. Par exemple le cas le plus simple :

Première assertion; le groupe 1 matche 123, la backreference va chercher à matcher le contenu exacte qui a été matché par le groupe 1, donc 123. La deuxième assertion montre bien que la backreference ne matchera pas 1234, car elle s’attend donc au même contenu que 123 (notez quand même l’utilisation de l’appel matches() plutôt que find()).

Bien entendu il faut que ce soit un groupe capturant, sinon la backreference ne sait pas ou chercher sa valeur. L’exemple qui suit montre un Pattern qui compile, mais qui ne fonctionnera pas:

Le simple fait que ce pattern compile m’étonne, j’aurais plutôt choisi une approche fail-fast dans ce cas, c’est peut-être un oubli.

Ce genre de construction est assez pratique si on veut valider un langage comme le XML.

Attention il peut y avoir des astuces, en particulier sur le groupe qui fait le premier match. Par exemple dans le suivant on va voir le moteur regex valider l’expression, alors que la chaîne à valider n’est pas correcte :

Effectivement <strong></s> n’est pas correct syntaxiquement pour du XML pourtant, le moteur valide la séquence de caractère. En fait c’est un des features du moteur de regex, le backtracking, que je vais expliquer dans la section suivante. L’idée c’est que le moteur matche bien strong pour le groupe 1, mais lorsqu’il essaye de matcher la backreference avec strong, il n’y arrive pas donc il reviens en arrière jusqu’à ce que le groupe 1 est pour valeur s, ce qui permet à la backreference de matcher. Le reste de la balise trong est matchée par cette partie de l’expression [^>]*.

La solution, est d’utiliser une borne de mot vu dans la partie 1 de cette petite série d’article.

De cette façon le groupe 1 ([a-z]+\b) est littéralement obligé d’être suivi par autre chose qu’un caractère de mot (class \w). Avec cette expression la mauvaise séquence de caractère XML n’est donc plus validée.

Utilisation sympa des backreferences est de chercher dans un texte les mots répétés :

Les quantificateurs

Les quantificateurs permettent comme leur nom l’indique de quantifier (une expression). À l’exception de l’opérateur de Kleene, géré par les moteurs de regex depuis très longtemps, tous les autres quantificateurs sont des représentations simplifiées de ce qui est exprimable par des constructions basiques.

  • dady? Le quantificateur optionnel peut s’exprimer par une alternative (attention à l’ordre) : dady|dad
  • (?:pa){1,3} Le quantificateur borné peut s’exprimer en répétant les termes et/ou avec une alternative : pa|papa|papapa
  • vrou+m Le quantificateur 1 ou plus peut être remplacé par l’occurrence 1 puis par une construction avec l’opérateur de Kleene : vrouu*m

Bref ces notations simplifiées sont bien pratiques.

Les quantificateurs gourmands (greedy quantifiers)

Pas de surprise ces quantificateurs font partie de la catégorie des quantificateurs dit gourmands. Vous savez certainement déjà les utiliser, cependant il peut y avoir des cas qui peuvent poser problèmes.

Dans l’exemple suivant je voudrais chopper la balise ouvrante.

Dans la première approche on utilise un quantificateur gourmand <.+> ce qui veut dire que le moteur va essayer de consommer au maximum la séquence de caractères.

  1. Pour la section .+ de la regex, le quantificateur va essayer de valider au maximum le .
    • Du coup le premier caractère > est validé par la construction .,
    • Puis le deuxième (le dernier caractère) > est également validé par ..
  2. Après ce dernier > dans la séquence de caractère la chaîne complète est consommée, mais il reste le dernier > dans l’expression rationnelle.
  3. Du coup le moteur utilise le mécanisme de backtracking pour revenir en arrière, il tombe alors sur le 1 de </h1>.
  4. Finalement le > de l’expression matche le > de la séquence de caractère.

Comme ce n’est pas ce qu’on veut récupérer, la balise ouvrante, une solution serait donc de prendre un quantificateur paresseux identifiable par le point d’interrogation qui suit le quantificateur.

Question performance dans le cas présent, il est plus intéressant de ne pas utiliser le point . avec un quantificateur paresseux mais plutôt d’utiliser un complément de l’ensemble qu’on ne veut pas matcher, c’est à dire une classe de caractère avec exclusion du caractère non voulu >. C’est la troisième solution du bout de code (ligne 6).

Les quantificateurs paressseux (lazy quantifiers)

Ces quantificateurs sont bien nommés parce dans le genre, ils vont en faire vraiment le moins possible. Pour les comparer donc avec un quantificateur gourmand ou la séquence maximum est consommée (notez que la méthode regexFirstMatch est la même que dans le bout de code ci-dessus) :

Le quantificateur ? essaye de matcher la regex du groupe, et il y arrive, donc la séquence complète est consommée. Par contre ci la regex utilise une construction avec un quantificateur paresseux ?? :

Alors le quantificateur ne va pas s’emmerder à matcher, si la regex matche déjà ce qui est fait par la première partie de la regex abc1. Ce qu’il faut retenir c’est qu’un lazy quantifier, ne matchera jamais si le moteur valide déjà l’expression, et le corollaire est que le lazy quantifer cherchera toujours à matcher si et uniquement si la regex n’a pas déjà été validée.

Autre exemple avec un quantificateur borné :

À la ligne 2, le quantificateur paresseux est obligé d’être exécuté une fois au moins pour matcher, mais il en fait le moins possible.

Les quantificateurs possessifs (possessive quantifiers)

Les quantificateurs gourmands et paresseux, utilisent intelligement la capacité de backtracking afin d’évaluer les permutations possible qui permettent de valider l’expression régulière suivant leur stratégies respectives (en faire le plus ou en faire le moins). Cette propriété permet d’avoir des expressions assez souples pour matcher un grand nombre de séquence de caractère.

Cependant cette souplesse a un coût, le backtracking a un coût en mémoire et en temps CPU. Ce coût monte suivant la complexité de l’expression rationnelle et en fonction de la séquence de caractère. Pour des raisons de performance les créateurs des moteurs de regex ont introduit une nouvelle construction qui améliore les performances de votre regex : les quantificateurs possessifs.

Cette catégorie de quantificateur est un peu différente des deux autres, dans la mesure ou le backtracking est désactivé. Ce qui veut dire, si vous avez suivi, que l’expression régulière ne peut pas revenir en arrière chercher une précédente position ou la regex validait. Cependant il faut noter qu’un possessive quantifier cherche également à matcher le plus possible.

Typiquement dans le code suivant :

La partie de l’expression régulière .+ va tout matcher jusqu’au point virgule ;. Seulement comme expliqué plus haut, une fois que la String est consommée, le caractère > dans la regex ne peut pas matcher, donc le moteur reviens plusieurs fois sur ses pas, puis ressaye de matcher le > de la regex. Ce comportement peut être désiré dans certains cas, mais parfois si on souhaite juste rechercher quelque chose de spécifique ou valider très vite un texte sans chercher d’autres combinaisons alors ce n’est pas l’idéal.

Ici l’expression est constituée d’un possessive quantifier, et en effet l’expression ne matche pas parce qu’une fois que la regex a consommée l’ensemble de la chaîne, et qu’elle ne peut plus matcher le dernier >, elle se déclare en erreur. On peut voir ça comme une construction du genre fail-fast.

L’intérêt véritable des constructions de cette catégorie est intéressante uniquement si les sections adjacentes de la regex sont mutuellement exclusives. L’exemple le plus prégnant est lorsqu’on utilise un complément avec un quantificateur possessif :

Ici le complément [^>] est naturellement mutuellement exclusif avec le caractère >, ce qui permet à la regex d’invalider très vite la séquence de caractères (notez la fin de la chaîne >>). Si on avait utilisé un greedy quantifier, alors le moteur serait revenu en arrière autant de fois que possible pour tenter de valider l’expression, ce qui est impossible avec la séquence passée en paramètre.

Exemple à ne pas faire, car les tokens ne sont pas mutuellement exclusifs ; a*+ immédiatement suivi d’un a, du coup la regex ne peut pas matcher car a*+ consomme tous les a :

Les quantificateurs possessifs sont des constructions qui sont supportées par les dernières générations de moteur de regex, parce qu’ils sont en réalité des groupes spéciaux. En effet dans la Javadoc de la classe Pattern, on trouve à la fin une partie sur les constructions spéciales, et celle qui nous intéresse dans ce cas, c’est celle là :

  • (?>X) X, as an independent, non-capturing group
  1. “non capturing” : Simplement parce que le groupe ne fait pas de capture lorsque X matche.
  2. “independant” : Ici ce n’est pas très clair dans la javadoc de Pattern, pour trouver la signification il faut se rendre sur la documentation des regex en Perl, on y apprend qu’il s’agit d’un groupe indépendant du reste de l’expression régulière, que ce groupe ne sait pas revenir en arrière (pas de backtracking), en gros le moteur de regex permet à ce groupe de consommer tout ce qu’il peut sans considérer les autres parties de la regex.

Une petite vérification :

Donc un quantificateur possessif est une notation simplifiée d’un groupe indépendant et non capturant!

Le backtracking

Comme vous le savez, je l’ai bien répété, le backtracking c’est ce qui permet au moteur de regex de traquer les constructions qui ont validé. Le backtracking n’a de sens que pour les quantificateurs, en effet ce sont les quantificateurs qui vont essayer de tester une construction un certain nombre de fois. Cela dit cette construction peut-être suvi par une autre et le moteur doit s’assurer que les constructions qui suivent le quantificateur valident également le reste de la séquence.

Prenons un exemple :

Dans le cas suivant on le pattern, observez le fait que le point . n’est pas mutuellement exclusif avec bob.

ab.*bob

Et on essaye de valider la chaine de caractères, les chiffres sont là pour illustrer la partie sur la quelle la construction .* devrait matcher, mais des lettres auraient pu faire l’affaire.

ab1234bob

A la première étape Pattern.compile, l’expression va être transformée dans un arbre. Techniquement le code ressemble à la fois au pattern Chain of Responsability et au pattern Composite (pour les groupes ou pour les quantificateurs notamment). Le moteur ajoute ses propres nœud au début et à la fin de l’arbre pour travailler avec cette représentation.

Dans le diagramme suivant chaque cadre correspond à l’état de la consommation de la séquence de caractère et à celui de l’expression régulière ainsi découpée en nœuds.

On comprend immédiatement le problèmes potentiels sur des expressions qui utilisent énormément les quantificateurs non-possessifs :

  • Plus la partie à matchée est longue pour le quantificateur, plus la mémoire sera consommée.
  • Si les constructions qui suivent ne matchent pas, celles-ci devront être annulée et réessayée, ce qui veut dire un temps d’exécution plus long!

La solution c’est de faire attention quand on construit une expression rationnelle. En particulier si elle est critique, l’idée serait de la benchmarquée, mais bon il faut pas tomber non plus dans ce qu’on appelle Premature Optimisation.

Bilan

Le backtracking c’est bien ; c’est ce qui permet à la regex d’être souple, mais clairement il faut faire attention à ce mécanisme. Il sera intéressant du coup d’utiliser des groupes non-capturants et indépendants si l’opportunité le permet.

Cette série s’achèvera par une troisième et dernière partie ou j’aborderaie les possibilité de travailler avec Unicode, et surtout comment indiquer dans une regex qu’on ne veut pas d’une construction complète.


Références

http://download.oracle.com/javase/6/docs/api/java/util/regex/Pattern.html

http://perldoc.perl.org/perlretut.html

S’exprimer régulièrement (Partie 1)

Il était une fois les expressions régulières

Depuis bien longtemps je connais et pratique les expressions régulières, à la fois au moment de coder, mais également dans mes éditeurs de texte, parfois aussi dans le shell, lors d’un grep par exemple. Bref les expressions régulières sont pratiques dans la vie de tous les jours pour un ingénieur logiciel.

Seulement voilà je me suis aussi rendu compte que certains d’entre nous n’ont pas une connaissance approfondie des expressions régulières et de leurs arcanes. Effectivement il y a parfois certaines expressions qui sont assez absconses. Et aujourd’hui les moteurs des expressions régulières dépassent ce le cadre dans lequel ces expressions ont été conçue. Elle permettent certaines constructions qui sont peu connues.

Les expressions régulières hier et aujourd’hui

Sans remonter aux origines des expressions régulières -cette partie là est couverte par wikipedia- il est intéressant de noter que les expressions régulières et leur moteur ont bien évoluées en 60ans. En effet le mot régulier vient de l’état de fait que ces expressions permettaient de rechercher dans des langages formels et non-contextuel; aujourd’hui les recherches ont avancées et les moteurs permettent maintenant de dépasser le cadre du langage formel pour permettre de travailler dans l’espace du langage contextuel. Les racines des expressions régulières remontent bien avant l’avènement de l’informatique pour aller jusqu’aux raisonnements complexes de la logique mathématique.

Il y a une une grosse différence entre un langage non-contextuel et un lange contextuel, dans les faits cette évolution explique pourquoi il y a aujourd’hui des différences dans les moteurs qui sont intégrés dans les différents programmes (en fonction de la plateforme, des outils, du langages etc.) Aujourd’hui en Perl, en C#, et en Java nous avons la chance d’avoir des moteurs qui font partie des dernières générations. C’est sur cet héritage que je vais disserter, cela dit uniquement dans le cadre de Java et de sa fameuse classe Pattern. (Vous remarquerez d’ailleurs que le moteur est nommé Pattern plutôt que Regex ou quelque chose du genre, l’explication est simple : cette génération de moteur n’est plus simplement à propos d’expression régulière mais donc de pattern.) Je tiens aussi à préciser que cet article se concentre sur la création d’expressions régulières et non sur l’usage de la classe Pattern.

Les différentes constructions

Petit rappel

Je passe rapidement sur les bases, j’imagine que tout le monde connaît les constructions basiques d’une expression régulière :

  • Les classes de caractères [ ] et les compléments [^ ]
  • L’opérateur de Kleene *
  • L’alternative | (le pipe)
  • Les autres quantificateurs : +, ?, {}, ces quantificateurs ne sont vraiment que des raccourcis de ce qui est déjà exprimable avec les autres constructions, mais ils nous simplifient la vie.
  • Les groupes ()

Globalement pas de surprises ici, avec ses constructions il assez facile d’écrire l’expression la plus simple jusqu’à l’expression un poil plus élaborée.

Par exemple pour valider un mail (sans rentrer dans les arcanes de la RFC) on peut avoir ça:

Ok, c’est déjà pas mal, mais si on veut extraire une section d’un texte ou valider précisément certaines sections d’un texte, il faut connaitre les constructions un peu plus pointues.

Les ancres

Les ancres sont rangées dans la javadoc de la classe Pattern sous la catégorie Boundary matchers. Une ancre identifie juste une position à laquelle elle matche, elle ne consomme pas de caractères dans la séquence traitée.

Le début et la fin d’une ligne

Généralement les personnes qui ont beaucoup travaillé avec le shell connaissent les deux principales ancres, à savoir le début d’une ligne ^ et la fin d’une ligne $. Mais il y a une astuce en Java, c’est que par défaut ^ et $ repèrent le début et la fin du CharSequence uniquement, pas de notion de saut de ligne!

Pour s’en convaincre on écrit un petit test simple qu’on enrichira d’assertions, la méthode regexFirstMatch extrait la première section du texte qui matche la regex :

Et ouai, on ne s’attend pas à ça (matche T et 1) surtout quand la description de ces ancres utilise le mot ligne. En fait il faut activer l’option multiligne Pattern.MULTILINE dans le moteur, pour que celui-ci identifie les sauts de ligne.

Ainsi dans le contexte du bout de code du dessus, les lignes suivantes permettent de voire qu’il s’agit bien du caractère : de la première ligne qui est trouvé.

Nice, mais il y a encore mieux, le moteur de regex de Java (comme certains autres) permet de donner les options à l’intérieur de la regex, la javadoc de Pattern donne cette info dans la catégorie Special constructs (non-capturing), celle qui nous intéresse est la construction sur les options pour toute l’expression.

  • (?idmsux-idmsux) Nothing, but turns match flags on – off

Il faut le placer au début de l’expression régulière, ici (?m) :

On choppe alors bien le caractère à la fin de la première ligne.

Le début et la fin d’une séquence de caractères

Dans notre expression si on veut se caler dans tous les cas sur le début et la fin d’une séquence de caractères, il y a des ancres dédiées \A et \Z. Celles-ci ne sont bien entendu pas affectées par l’option multiligne.

Notez quand même qu’en ce qui concerne le \Z le dernier caractère de la séquence qui est un séparateur de ligne n’est pas retourné! Comme indiqué dans la javadoc, cette ancre repère la position avant le dernier caractère séparateur (écrit comme terminators dans la javadoc).

Il existe d’autres ancres, mais elles sont moins utiles, je vous laisse voir par vous même.

Les options

On a vu qu’on pouvait activer des options pour une expression régulière, effectivement c’est assez pratique.

Les options possibles utilisables à la construction ou dans le pattern sont dans la javadoc, mais les plus intéressantes sont :

Option Flag Flag à la construction
Multi-ligne m Pattern.MULTILINE
Insensibilité à la casse i Pattern.CASE_INSENSITIVE
Matching de la casse relatif aux règles Unicode u Pattern.UNICODE_CASE
Matching des caractère en fonction de leur forme canonique Pattern.CANON_EQ

Certaines options comme vu dans le tableau n’ont pas d’équivalence dans la regex.

Bon c’est bien pratique ça, mais parfois on aimerait bien s’assurer que la casse est ou n’est pas vérifiée sur une portion de la regex. Il existe une construction qui permet d’activer/désactiver une option dans une section de l’expression régulière :

  • (?idmsux-idmsux:X) X, as a non-capturing group with the given flags on – off

A peu près la même chose que pour les options avec une portée sur toute la regex, sauf que cette fois, la portion soumise à l’option changée est à l’intérieur d’un groupe. Et là vous remarquerez que la javadoc dit bien “non-capturing” ça veut dire que la regex ne gardera pas en mémoire le contenu de ce groupe, contrairement aux groupes qui, donc, capturent et sont identifiables par l’encadrement du groupe par des parenthèses (X).

Ainsi par exemple si on ne veut pas tenir compte de la casse dans une portion de la regex on écrirait:

Dans la première expression, qui ne marche pas, l’ensemble de l’expression est sensible à la casse c’est l’option (?-i) en début d’expression. Mais au milieu on voudrait quand même autoriser les majuscules. Pour ce faire on active l’insensibilité uniquement pour le groupe du milieu (?i:[a-z]+).

Les bornes de mot

Les bornes de mots sont des ancres de type particulier. Comme n’importe quelle ancre, ces bornes ne consomment aucun caractère. La borne \b s’utilise avant ou après un mot pour marquer le début ou la fin d’un mot.

Par exemple en utilisant la classe de caractère \w.

Effectivement \b marque la différence entre une classe de caractère de type lettre par rapport aux classes adjacentes. On remarque néanmoins que s’il n’y a donc pas de classes de type caractère avant ou après, la borne fait sauter l’expression. De la même manière la borne ne fonctionne pas avec une classe de caractère composée de caractères qui sont considérés comme ne faisant pas partie des mots (exemple en ajoutant le tiret à la classe suivante : [0-9a-z-]).
Évidemment aussi, mettre une borne dans une regex au milieu de caractères ne marchera pas.

Bon c’est bien cool, mais si je veux matcher un texte en allemand, du grec ou simplement des lettres accentuées de notre bon français ? Là ça pèche un peu si on utilise le \w.

En effet la classe \w ne connait que les caractères ASCII et plus précisément; uniquement ceux de cette classe [a-zA-Z0-9_] tel que c’est mentionné dans la javadoc. Pour palier à cette limitation soit il faut ajouter le caractère accentué à une classe de caractère, soit on utilise une classe de caractère Unicode, c’est ce qui est fait dans la dernière assertion j’utilise \p{L} ! Je reviendrais plus tard sur Unicode avec les expressions régulières.

Attention à l’encodage de vos codes source ! J’ai eu des erreurs d’encodage du fichier sur Eclipse, IntelliJ et NetBeans qui provenaient de plateformes différentes (MacOSX et Windows), du coup le caractère É n’était pas bien encodé (comprendre que l’IDE encodait ce caractère dans autre chose qu’une lettre), ce qui faisait évidement échouer l’expression.

Enfin le complément d’une borne \b est représenté par la borne \B, celle-ci matche tout ce que \b ne matche pas. Dans les faits \B marque la borne entre deux classes de caractères à l’exception d’une classe composée des caractères qu’on peut trouvé dans \w.

Fin de la partie 1

Voilà pour la première partie, la plus simple, sur les expressions régulières en Java. Pour la suite qui arrive très bientôt j’exposerai la manière de fonctionner de certaines constructions un peu particulières :  les backreferences, les quantificateurs possessifs, les possibilités de lookahead / lookbehind.

Références

Les visiteurs, une question de nommage, et le double-dispatch

Une histoire qui commence mal

OK, je tranche le malheureux pattern Visiteur a la vie dure; on ne l’aime pas trop, il est mal compris, et le pauvre est sous utilisé. Alors bon même s’il a ses défauts, pourquoi lui en vouloir autant, alors qu’il apporte justement ses avantages au code orienté objet.

Et oui vous avez bien lu orienté objet. Jusqu’à aujourd’hui j’ai vu du code qui ressemble à ça?

  1. On a soit des objets très complexes, avec des comportements qu’il n’est pas forcément intéressant de mettre dans l’objet même. Le code ci-dessous montre un objet ou les méthodes qui permettent de récupérer les livres d’un certain genre ne sont pas forcément appropriées dans cette partie du code. Pourquoi parce qu’il est envisageable (selon le bon sens) que d’autres genres serait apprécié. Et s’il faut ajouter d’autres méthodes encore.

  2. Ou alors on a des objets anémiques (cf Martin Fowler) et le comportement est bien en dehors des objets traités, mais, et c’est la ça pèche, le comportement est délocalisé dans des helpers. Bref en gros c’est de la programmation procédurale, ce sont des structures qui sont manipulées par des fonctions, c’est du C avec des espaces de nommage (les classes *Helper.java). La programmation objet en prends un coup, pas étonnant que les principes objets ne marchent pas dans ce contexte, mais je diverge. Bref on a du code qui ressemble à ce qui suit. Un objet anémique qui ne fait rien. Au mieux il aura probablement les méthodes equals et hashCode et peut-être un toString.

    Et le démoniaque helper :

Comme vous le voyez les deux exemples ci-dessus ne sont pas vraiment élégants, même si je préfère la première voie. A long terme ce n’est probablement pas une bonne idée. J’aimerais d’ailleurs avoir l’avis des gens du DDD?

Et c’est là que notre ami le visiteur va nous aider.

Pourquoi le visiteur nous aide, qu’apporte-t-il ?

Bonne question, ce pattern est souvent incompris, et pour cause, il ne porte pas un nom qui lui facilite la vie.

Et oui pour le coup un visiteur n’est pas fait pour visiter. Page 387 de la traduction française du livre Design Patterns (par le GoF), nous pouvons lire :

Le visiteur fait la représentation d’une opération applicable aux éléments d’une structure d’objet. Il permet de définir une nouvelle opération, sans qu’il soit nécessaire de modifier la classe des éléments sur lesquels il agit.

Effectivement aussi, ce livre donne comme un exemple un arbre. Et le visiteur prends toute sa puissance sur un arbre ou sur une structure composite. Mais ce n’est le seul cas ou celui-ci est utile, dans tous les cas il s’agit bien de permettre l’ajout / la suppression / la modification de comportements d’une manière objet sans retoucher à ce qui existe déjà. Je le répète le fait que le visiteur marche super bien sur un arbre est un bonus, mais le problème adressé, l’intention du visiteur n’est pas de visiter, mais de définir une nouvelle opération sans changer l’existant sur lequel il agit.

Il faut mesurer l’intérêt du visiteur suivant deux axes.

  1. S’il y a beaucoup d’objet du domaine qui peuvent avoir le même comportement, ou si la grappe de nœud d’un arbre est importante, un ou des visiteurs sera une bonne solution de conception pour mutualiser du code.
  2. S’il n’y a pas énormément d’objet du domaine, voir qu’un seul, mais que les comportements relatifs sont à la fois divers et volatiles. Alors le visiteur est un candidat pour ajouter des comportements sans faire de satané helper et sans avoir à modifier les éléments du domaine.
  3. Si vous avez des opérations différentes et un arbre ou des objets composite, le visiteur est le pattern pour vous, c’est la qu’il prendra toute son essence.
  4. Si finalement vous n’avez pas beaucoup de comportement, qu’ils ne risque pas beaucoup de bouger et que vous n’avez pas des objets variés pour mutualiser ce code, alors le visiteur n’est probablement pas pour vous.

Egalement aussi le visiteur étant un objet permet de conserver un état, ce que ne permettent pas les objets même du domaine ou les helpers (sauf si on utilise des objets contextes passé de fonction en fonction, ce n’est pas exceptionnel).

Exemple sans prétention de visiteurs

D’abord la grappe d’objet “complète” :

Et la partie relatives aux visiteurs, d’abord l’interface (ou j’ai choisi volontairement de ne pas mettre les mot Visitor et visit) :

Et voilà on des comportements différents liés à un objet en particulier, pas besoin de retoucher notre élément. Et on a une manière élégante de sortir nos comportements. Bien entendu, ce genre de chose est à faire avec du bon sens, en fonction du contexte et de l’opération à effectuer.

Quand on a davatage d’objets du domaine à visiter, attention!

Attention quand même, comme précisé plus haut, le visiteur n’est pas non plus sans défaut. Sur une structure d’objet profonde ou large, votre pattern visiteur va créer une dépendance cyclique entre lui et les objets sur lesquels il est sensé s’appliquer.

Si mon visiteur doit par exemple travailler sur plusieurs sous type de l’objet (on pourrait typiquement avoir ce genre de problème avec les structures composites) :

On voit vite le problème ou le visiteur est forcé d’implémenter des opérations pour des objets qui ne l’intéresse pas forcément. Le problème est contournable en utilisant intelligemment les interfaces, mais cette solution palliative a également des limites; on ne va faire implémenter 45 interfaces à nos objets.

Pour cela il y a une solution un peu plus complexe qui est également un pattern, c’est le Visiteur Acyclique. Je n’approfondie pas trop, mais l’idée est d’avoir pour chaque sous type du domaine une interface de visiteur qui permet de vérifier que l’instance du visiteur est acceptable. Evidemment vous pourrez adapter le comportement, et vous n’êtes non plus obligé d’implémenter toutes les méthodes, c’est le but de ce pattern acyclique.

Et typiquement le code du accept pour chaque sous-type de collection aurait une tête du genre :

Et voilà on a cassé les dépendance, et on est pas obligé d’implémenter toute les interfaces de chaque type de collection.

Le double dispatch, à ne pas confondre avec un visiteur

Le lecteur avertit aura vite deviné que ça ressemble au pattern stratégie, et il aura raison, ce sont des patterns comportementaux. Mais là ou le visiteur se distingue, et notamment dans des langages comme Java, .Net, C++ c’est qu’il utilise la technique du double dispatch.

Alors le double dispatch (double répartition) c’est quoi exactement, c’est un moyen pour le logiciel de résoudre au runtime les méthodes à exécuter.

Je vais citer les exemples wikipédia et transformer leurs exemples en Java.

On a donc deux catégories d’objets, des astéroïdes et des vaisseaux spatiaux.

Ok, maintenant dans le code on a ça

Comme en java c’est la méthode de l’instance qui est appelée, pas de problème pour nos astéroïdes. Mais là ou ça coince c’est au niveau des vaisseaux spatiaux. Les deux appels vont afficher sur la sortie sandard:

En effet le type réel du vaisseau spatial n’est pas connu, sauf si on fait de la reflection avec un instanceof, mais il y a plus élégant, c’est le double dispatch.

Si maintenant nos vaisseaux spatiaux ont tous les deux cette méthode définie :

Maintenant notre code utilisera l’API de cette façon :

Et on aura le code correcte utilisé.

Cette technique est utilisée par le visiteur, mais nous ne somme pas obligé d’avoir des visiteurs pour l’utiliser (la preuve par l’exemple grâce à wikipédia). C’est utilisé régulièrement dans la JDK, typiquement pour la sérialisation (même si c’est caché). Coté performance si on a le choix, le double dispatch sera toujours plus rapide qu’un instanceof. Coté design c’est pratique quand on a des branches d’objets qui travaillent ensemble.

Certains langages proposent nativement un support pour ces problèmes de résolution de type d’opérande, comme Nice.

A regarder aussi, c’est le multi dispatch ou les multi-méthodes, il y a notamment une implémentation de Rémy Forax de l’université de Marne-la-Vallée, cette implémentation a le mérite d’être standard Java, c’est à dire qu’elle n’étends pas le langage lui-même.

Pour y jeter un œilhttp://www-igm.univ-mlv.fr/~forax/works/jmmf/index.html

Récapitulatif sur le visiteur

Le visiteur est bien un ami, mais comme tous les potes, il ne sait pas tous faire non plus.

Un visiteur sait parcourir des arbres, il se débrouille super bien avec, mais il est aussi utile quand il n’y a pas d’arbre.

Un visiteur sert avant tout à extraire des comportements lié à un structure d’objet qui bouge peu. La structure peut être plate, ou en profondeur (cela dit je privilégierait la composition à la lace de l’héritage).

Le visiteur utilise la technique du double dispatch, ne pas confondre les deux.

Le visiteur permet de respecter le SRP (Single Responsibility Principle).

Le visiteur aide à maintenir le CCP (Common Closure Principle), c’est une histoire de cohésion entre les classes qui sont regroupées dans un même package.

The classes in a package should be closed together against the same kind of changes. A change that affects a package affects all the classes in that package.

Bon voilà, le débat reste ouvert, si vous pensez que j’ai tort, que j’oublie un point important, ou pour autre chose, il y a les commentaires.

Références

http://www.objectmentor.com/omSolutions/oops_what.html

http://www.objectmentor.com/resources/articles/visitor.pdf

http://www.objectmentor.com/resources/articles/acv.pdf

http://www.artima.com/cppsource/top_cpp_aha_moments.html

http://butunclebob.com/ArticleS.UncleBob.VisitorVersusInstanceOf

http://www.javaperformancetuning.com/articles/ddispatch.shtml

A propos du design de vos objets, des getters et setters, de equals/hashCode et de la mutabilité

Prologue

A l’école nos professeurs nous apprenaient ce qu’était la programmation orientée objet; en particulier l’encapsulation. En effet avoir un accès public aux variables internes d’un objet n’est pas particulièrement recommandé, pourtant nous avons connaissons tous la convention JavaBean :

Manque de bol, cette convention qui a pourtant son utilité -voire sa nécéssité- peut dans certains contextes  briser l’encapsulation, et plus dangereux pour votre code, elle permet à vos objets d’être mutable, c’est à dire de pouvoir modifier l’état d’un objet après sa création. Bien que dans certains cas le design ou le rôle de la classe demande cette caractéristique, dans beaucoup d’autres situations la mutabilité peut poser problème.

D’ailleurs historiquement les JavaBeans ont été pensé pour être utilisé par des applications graphiques afin d’être construit itérativement et finalement pour être facilement dé/sérialisés [1]. Mais ces objets exposent publiquement leurs états, du coup :

  1. Il y a de l’adhérence à des propriétés internes d’un objet, s’il y a beaucoup de code qui utilise ces propriétés internes, l’évolutivité et la maintenance de ce code peut très vite devenir difficile et donc couteuse.
  2. Ce n’est plus vraiment de la programmation orientée objet. C’est en quelque sorte des variables globales, ça fait plus de 30 ans qu’on sait que les variables globales c’est mal! Demandez à Barbara Liskov [2].
  3. Avec cette possibilité de muter les objets, il peut y avoir des problèmes au runtime, et croyez moi avec l’arrivée de la parallélisation en plus dans vos applications il va y avoir des surprises.

Bon revenons au design, et aux problèmes rencontrés.

Illustration des problèmes de design du code

hashCode et equals

Donc pour commencer, on va juste faire quelques tests sur un objet sans les méthodes hashCode() et equals(). Prenons les test suivants, je créé 4 instances de beans, obj1 et obj3 puis obj2 et obj4 ont les mêmes propriétés.

Ce test montre les problèmes quand on oublie les méthodes equals et hashCode.

Si l’implémentation de AJavaBean oublie donc le hashCode et le equals, la plus part des assertions ne marchent plus.

En bref :

Que s’est-il passé? S’il n’y a pas de hashCode et de equals, ce sont les méthodes de la super classe qui sont utilisées, dans le code listé plus haut ce sont les méthodes de Object qui seront utilisées pour tester l’égalité et le hashCode.

  • Donc pour l’égalité Object.equals(Object) vérifie uniquement si l’instance est la même. Ce qui explique que les tests d’égalité échouent plus haut.
  • Pour le hashCode, c’est la JVM qui le génère, bref autant dire que le hashcode est différent pour chaque instance. Ceci explique que les instances obj1 et obj2 sont ajoutées au HashSet, si le hashcode avait été le même alors les opérations d’ajout et de suppression auraient renvoyé false (n’oublions pas qu’il s’agit d’un HashSet).

Et donc pour le code mutable

Ok, bon maintenant qu’on a vu ça, notre bean implémente les méthodes equals et hashCode de manière idoine, c’est à dire dans notre cas que le code se base sur les attributs name et sellingDate. Pas de mystère, on peut utiliser l’outils de génération de l’IDE.

Eclipse génère ça:

Bon à priori on se dit que notre code est safe puisqu’on a nos méthodes equals et hashcode, mais on se fourvoie ; notre objet est mutable!

Exemple :

Surprise! You just got

Alors on sait que les méthodes equals et hashCode utilisent les deux propriétés name et sellingDate, donc quand on ajoute un objet dans le HashSet le hashCode correspondra au calcul fait partir des valeurs des ces attributs. Mais voilà le hashcode de l’objet n’est calculé qu’une fois, au moment de l’interaction dans la Map (ajout, suppression, contains, etc…).

Donc ce qu’il se passe c’est qu’on a fait muter l’état de notre objet, du coup le hashcode est différent, mais la collection conserve la référence de l’objet qu’elle contiens et ne recalcule pas son hashcode! C’est aussi avec avec ce genre de code que vous pouvez avoir des fuites mémoires. Et on est même pas dans un contexte multithreadé, alors imaginez si la collection est partagée entre plusieurs thread!

Attention aux collections ou aux dates du JDK

Par ignorance puis par laxisme, j’avoue que j’ai écris du code qui ressemble à ça (et j’ai honte de le dire) :

Et forcement il y a des hics! A priori notre classe n’est pas mutable. Mais cela ne vous aura pas échappé, les propriétés aDate et aMap sont mutable!

Et là, vous vous retrouverez les mêmes surprises que celles vu plus haut, ou évidement pire si vous êtes dans une application multithreadée. A ce sujet j’ai vu des ConcurrentModificationException parceque levé par du code à priori immutable, une optimisation d’un vieux code multithreadé avait déplacé une section qui modifiait une Map.

Je vous conseille vivement d’utiliser des objets immutables pour vos property, les librairies Joda-Time [3] et Google-Collections [4] fournissent des objets immutables.

Le pattern Builder de Joshua Bloch

Pour Joshua Bloch, c’est un peu une référence en Java, je pense qu’on peut lui faire confiance. Il est l’auteur du fameux livre Effective Java [5].

Alors pourquoi le pattern Builder de Joshua Bloch et non le pattern Builder du GoF ? En fait ce design vient d’une constatation au sujet de la construction d’objet complexes et pour s’affranchir des inconvénients des accesseurs.

En gros un objet du genre agrégat pourrait être construit avec un constructeur avec un paquet d’argument ou itérativement avec une foule de setter. Mais, un les gros constructeur ce n’est pas très pratique, puis deux les setters ça peux vite être lourd et ça rends votre objet mutable (ce qui n’est donc pas souhaité dans tous les cas).

Cette déclinaison du builder permet de construire un objet itérativement sans forcer la mutabilité.

Exemple les collections google :

Ou encore avec une classe de notre domaine :

A noter que cette classe utilise des objets immutables pour ces attributs (DateTime, et ImmutableList).

Un des avantages, c’est qu’il est possible de valider les propriétés avant la création effective de l’objet. Avec les setters c’est faisable mais ça peut être délicat dans certaines situations.

Il y a un plugin Eclipse, qui permet de générer ces Builder, celà dit il est loin d’être super user friendly.

http://code.google.com/p/bpep/

Quoiqu’il en soit en aucun cas ce pattern n’est un remplacement du pattern Builder du GoF, il s’agit plus d’un pattern à appliquer dans un contexte ou il faut des objets immutable. Et encore ce n’est pas la seule solution, JodaTime typiquement n’utilise pas de builders.

Comment gérer la modification de l’objet

Si un comportement qui fait partit du domaine de l’objet et doit modifier l’état, alors il faut peut-être créer une nouvelle instance. La bibliothèque Joda-Time fait typiquement ça lorsqu’il y a modification d’un champs.

Je ne m’étends pas sur le sujet, mais ce genre de choses dépends de votre contexte, du rôle et du besoin. Un objet devrait être par défaut immutable, sauf si vraiment votre domaine identifie un cas ou l’état doit bouger et alors vous aurez des méthodes documentées qui appliqueront cette modification.

Conclusion

Mieux vaut des objets bien pensés et immutables que d’introduire la possibilité de changer l’état d’un objet et avoir des surprises. Et puis aussi :

  1. Il y a un risque fort d’avoir des problèmes au runtime, d’autant plus 10 ans après lorsqu’il y a une évolution à apporter et que plus personne ne sait qu’à tel endroit dans le code il y a le truc qui fout tout en l’air. Et les problèmes au runtime ca peut vite couter cher à analyser.
  2. Si vos objets ne peuvent pas être modifié alors vous n’aurez pas à vous soucier des problèmes de concurrences, c’est manifestement un gain de temps au développement et en maintenance. (Et donc un gain d’argent sur le long terme.)
  3. Bon ces objets sont bien cool, mais voilà il y a encore plein de framework (à tord ou à raison) qui se basent sur la convention JavaBean, je pense notamment aux objets marshallés en XML et consort.
  4. Ce code basé sur les builders est propre, mais il faut passer un petit peut plus de temps pour le faire. Il y a bien un plugin pour Eclipse, mais quid des autres IDE.

Quoi qu’il en soit, ces solutions sont toujours à appliquer avec du recul et toujours en fonction du contexte de votre domaine.

D’ailleurs cette entrée parle des problèmes rencontrés avec les collections du JDK, mais le problème pourrait se manifester différemment si une collection ou un de vos objets fonctionne autrement.

Encore une fois les remarques sont les bienvenues, ça fait plus de 40 ans que l’Homme fait du logiciel, et mafois on se plante encore assez souvent.

Références

  1. http://www.javaworld.com/javaworld/jw-09-2003/jw-0905-toolbox.html
  2. http://www.infoq.com/presentations/liskov-power-of-abstraction
  3. http://dutheil.brice.online.fr/blog/index.php/2010/02/09/a-propos-de-joda-time/
  4. http://dutheil.brice.online.fr/blog/index.php/2010/02/16/les-collections-par-google-comment-sy-retrouver/
  5. http://www.amazon.fr/Effective-Java-Joshua-Bloch/dp/0321356683/ref=sr_1_1?ie=UTF8&s=english-books&qid=1269958692&sr=8-1
  6. http://rwhansen.blogspot.com/2007/07/theres-builder-pattern-that-joshua.html