lucidiot's cybrecluster

Construire des expressions régulières avec m4

Lucidiot Informatique 2022-01-02
Factorisons la validation du Well-Known Text en utilisant des templates !


Dans l'article précédent, j'ai construit des expressions régulières incompréhensibles en écrivant des expressions plus petites et en les imbriquant à la main à l'aide du bon vieux copier-coller. On va voir dans cet article une technique qui permet de générer ces expressions sans le copier-coller...

Il y a moult façons de générer ces expressions, j'aurais par exemple pu utiliser un script Python avec des variables imbriquées :

number = r'[+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:[Ee][+-]?\d+)?'
point = rf'POINT\s*(?:\s+EMPTY|\(\s*{number}\s+{number}\s*\))'

Mais puisque j'en suis déjà à explorer les XSD pour faire la validation d'OpenSearch Geo, on peut essayer d'utiliser d'autres systèmes inhabituels pour générer ces expressions. En y réfléchissant un peu, je me suis souvenu de GNU m4, un utilitaire assez peu connu qui est pourtant utilisé assez fréquemment pour beaucoup de programmes en C ou C++. Si vous avez eu affaire à un projet où les instructions de compilation comprennent un appel à ./configure, alors il est très probable que GNU Autoconf aie été impliqué. Autoconf est lui-même basé sur m4.

J'avais initialement entendu parler de m4 au travers d'un article de blog de ~dozens qui mentionne son utilisation de m4 pour générer son site web. m4 est un langage de templating qui peut être apparenté aux macros de préprocesseur C ou aux templates C++. Il est conçu pour de la métaprogrammation, où des plus petites séquences de caractères sont transformées en plus gros morceaux de code. Voici un exemple très simple :

define(lol, world)dnl
Hello, lol()!

Si on sauvegarde ce script dans hellol.m4 et qu'on l'exécute avec m4 hellol.m4, on obtiendra ce texte extrêmement original :

Hello, world!

On va donc ici définir et utiliser moult fonctions pour essayer d'abstraire un peu la génération des expressions régulières pour OpenSearch Geo. Dans un prochain article, je pourrai ainsi exploiter ces nouvelles fonctions pour aller encore plus loin et faire des expressions de plusieurs dizaines de milliers de caractères.

Concepts de base

Avant de commencer à définir des macros spécifiques à WKT, il y a quelques concepts particuliers de m4 qu'il est important de mentionner. Ces concepts sont assez étranges quand on a l'habitude de langages de programmation classiques mais peuvent être assez puissants quand on sait s'en servir ou qu'on sait pourquoi ils existent.

Je ne vais pas documenter l'intégralité de m4, notamment parce que je suis très loin de connaître l'intégralité de m4, et je vais donc seulement introduire les concepts fondamentaux aux macros que nous définirons plus bas.

Chaînes de caractères

Par défaut, tout est une chaîne de caractères : dans l'exemple précédent, j'avais écrit world sans aucun échappement alors que j'étais à l'intérieur d'un appel de macro. Si un mot ne correspond pas à quelque chose que m4 connaît, c'est directement interprété comme une chaîne de caractères.

Si on veut éviter explicitement que m4 reconnaisse un mot comme une macro ou une fonction prédéfinie, on peut utiliser des chaînes de caractères littérales. Dans la plupart des langages, un seul caractère délimitera les chaînes de caractères : par exemple en SQL, l'apostrophe simple est utilisée : 'bla bla'. Mais avec m4, deux caractères délimitent les chaînes : il y a un caractère ouvrant et un caractère fermant. Le caractères ouvrant est l'accent grave (`) et le caractère fermant est l'apostrophe. Ce choix est un peu plus compréhensible quand on sait que les deux caractères sont souvent affichés comme étant le miroir de l'autre dans beaucoup de polices de caractères.

Une des raisons pour lesquelles il y a deux caractères est de permettre des chaînes de caractères imbriquées sans avoir à constamment échapper des caractères :

`une chaîne de caractères avec `une chaîne de caractères dedans' !'

Avec deux caractères différents, on peut savoir si on ouvre ou si on ferme une chaîne, donc on peut imbriquer des chaînes. Après chaque accent grave, m4 ignorera la prochaine apostrophe et ne considérera pas que la chaîne de caractères se termine encore.

Si ces caractères ne nous plaisent pas, ou si on est dans une situation où cet échappement de caractères peut nous poser problème, on peut les changer à n'importe quelle autre séquence :

changequote(<!--, -->)dnl
<!--une chaîne de caractères qui ressemble à un commentaire HTML-->

Échappement de caractères

Il n'y a pas de caractère d'échappement contrairement à beaucoup de langages : la controblique \ ne veut rien dire. Ça sera à notre avantage pour les expressions régulières vu que la controblique y est utilisée fréquemment. À la place, on peut entourer les caractères dans des chaînes littérales, par exemple `define', ou dans le cas des caractères déjà utilisés pour lesdites chaînes de caractères on peut les doubler comme en SQL : '' désignera ainsi une seule apostrophe et pas une fermeture de chaîne de caractères.

Commentaires

Le caractère # délimite des commentaires par défaut. On peut le changer tout comme on peut changer les caractères de chaînes avec changecom. Mais les commentaires ne se comportent pas comme dans d'autres langages : tout ce qui suit ne sera pas interprété par m4, mais sera quand même affiché.

define(lol, world)dnl
Hello, lol!
Hello, # lol!

On obtiendra avec cet exemple deux lignes :

Hello, world!
Hello, # lol!

Les commentaires sont donc le plus souvent utilisés dans m4 seulement pour que les commentaires du langage de programmation sous-jacent soient aussi compris comme ça. Par exemple, si vous codez en C, vous ne voudriez peut-être pas que tout ce qui est dans // soit interprété comme une macro m4, mais vous voulez quand même pouvoir lire les commentaires générés. On utiliserait alors changecom(//).

DNL

Il existe une macro intégrée qui a multiples usages, dont celui de commentaire plus standard : dnl, acronyme de Discard until Next Line (supprimer jusqu'à la prochaine ligne). Lorsque cette macro est utilisée, tout le reste de la ligne est ignoré. Cela inclut même le saut de ligne, ce qui signifie que dnl est utilisable pour relier deux lignes entre elles.

define(lol, world)dnl
Hello, dnl
lol!

Cet exemple nous renverra encore Hello, world!.

J'ai mis dnl juste après chaque define dans mes exemples précédents pour éviter de nous retrouver avec \nHello, world!, puisque l'appel à define n'est pas compris comme une ligne d'instruction complète mais comme une macro au milieu de la ligne.

Appel de macro

Il n'existe pas de distinction entre les variables et les fonctions dans m4 !

define(lol, world)dnl
Hello, lol!
Hello, lol()!

Les deux lol et lol() seront reconnus exactement de la même manière.

Paramètres de macro

Le mot-clé define sert à définir de nouvelles macros. Elles ont toutes un nom et une valeur, qui n'est pas grand chose de plus qu'un remplacement du nom de la macro par une chaîne de caractères. On peut utiliser des paramètres dans l'appel de macro avec $1, $2 et ainsi de suite :

define(lol, Hello, $1!)dnl
lol(world)

Appels imbriqués

Contrairement à un langage de programmation classique, m4 n'est pas capable d'appeler des fonctions dans des fonctions. À la place, m4 va continuer à réinterpréter le fichier plusieurs fois en boucle jusqu'à ce qu'il n'y ait plus rien de spécial à exécuter. Voyons un exemple :

define(lol, Hello, $1!)dnl
define(hello1, lol(world))dnl
define(hello2, `lol(world)')dnl
hello1
hello2

Les deux macros ont été définies à des valeurs différentes : la macro hello1 contient déjà Hello, world! alors que la macro hello2 contient la chaîne de caractères lol(world). Mais si on exécute ce script, on obtiendra :

Hello, world!
Hello, world!

m4 a commencé par exécuter lol(world) avant d'exécuter define(hello1, ...), donc le résultat de la fonction a été stocké directement dans la définition de la macro. Mais pour hello2, m4 a seulement stocké une chaîne de caractères lambda. Quand on a ensuite appelé hello2, m4 remplace ça par lol(world), et relance ensuite son interprétation pour découvrir un nouvel appel de lol avec le paramètre world. On se retrouve donc dans les deux cas avec le même résultat.

Dans ce cas précis où tout n'est que des constantes, ça n'a pas beaucoup d'intérêt. Mais lorsque des fonctions utilisent des paramètres, ça peut devenir beaucoup plus important. Prenons ce nouvel exemple :

define(_lol, Hello, $1!)dnl
define(lol1, _lol($1))dnl
define(lol2, `_lol($1)')dnl
lol1(world)
lol2(world)

Cette fois, si on exécute le script, on obtiendra des sorties différentes :

Hello, $1!
Hello, world!

Avec la première définition lol1, on a exécuté _lol avant de faire la définition, donc on passe $1 en paramètre directement. On n'est même pas encore dans le contexte d'une macro, mais dans le script global, donc $1 n'existe même pas et il n'y a aucune interpolation de variable effectuée. Par contre, pour lol2, rien n'est exécuté dans la définition. Ce n'est que plus tard, quand on appelle lol2(world), que la chaîne _lol(world) est générée, et donc qu'on fait passer le paramètre correctement.

Macros pour WKT

Maintenant qu'on a vu certaines des bizarreries de m4, on va pouvoir commencer à s'en servir. Commençons déjà par définir ce que nous voulons automatiser : tous les processus assez répétitifs des expressions régulières de la dernière fois. Prenons l'exemple du point pour commencer :

[Pp][Oo][Ii][Nn][Tt]\s*(?:\s+[Ee][Mm][Pp][Tt][Yy]|\(\s*[+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:[Ee][+-]?\d+)?\s+[+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:[Ee][+-]?\d+)?\s*\))

Le nombre

La façon la plus rapide de raccourcir cette expression, quand on sait qu'elle doit correspondre à juste POINT (30.4, -3E4) est qu'on peut dédupliquer le nombre. On peut utiliser une macro constante sans paramètres pour ça :

define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:[Ee][+-]?\d+)?)dnl
[Pp][Oo][Ii][Nn][Tt]\s*(?:\s+[Ee][Mm][Pp][Tt][Yy]|\(\s*number\s+number\s*\))

Ignorer la casse

La deuxième chose relativement évidente ici est qu'on écrit des mots de façon beaucoup trop compliquée. Il y a un assez grand risque de se planter en écrivant [Pp] à la place de juste P à la main. On pourrait pour cela utiliser une fonction avec des paramètres :

define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
ignorecase(POINT)\s*(?:\s+ignorecase(EMPTY)|\(\s*number\s+number\s*\))

L'expression devient presque plus longue qu'avant, mais cette fois-ci on comprend vraiment l'intention : on veut ignorer la casse pour ces mots. Mais comment va-t-on définir la macro ignorecase ?

m4 dispose d'une macro intégrée de remplacement à base d'expressions régulières appellée patsubst :

patsubst(`Hello, world!', [eo], a))
=> Halla, warld!

Les expressions régulières disponibles dans m4 sont celles de Emacs. Elles n'ont pas autant de fonctionnalités que celles utilisées dans Vim : notamment, je n'ai pas accès à \u et \l qui m'auraient permis de facilement transformer une lettre en majuscule ou minuscule.

m4 dispose aussi de la fonction translit, l'équivalent de la commande y dans sed ou du programme tr : on donne deux classes de caractères (le A-Z dans une expression régulière [A-Z]) et translit transformera chaque caractère d'une classe à l'autre.

translit(`HELLO WORLD', A-Z, a-z)
=> hello world

On peut utiliser ces deux macros et définir notre propre macro pour ignorer la casse :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl

Cette macro est assez complexe, donc on va l'exécuter en pas-à-pas à la main :

  1. On appelle ignorecase(LOL).

  2. La macro est remplacée par patsubst(LOL, \w, \[\&'translit(\&, A-Z, a-z)]').

  3. patsubst s'exécute. translit est ignorée pour l'instant vu que tout est encore entre apostrophes.

    L'expression de recherche contient \w qui va donc trouver n'importe quelle lettre ou chiffre, et s'exécutera une fois par lettre. \& dans l'expression de remplacement correspond à "tout ce que l'expression a trouvé", donc on obtient [Ltranslit(L, A-Z, a-z)][Otranslit(O, A-Z, a-z)][Ltranslit(L, A-Z, a-z)].

  4. Les trois appels à translit s'exécutent, et remplacent chacun la lettre par la lettre minuscule, donc on a [Ll][Oo][Ll].

Je ne cache pas qu'il m'a fallu beaucoup d'expérimentation pour y arriver, notamment en ce qui concerne la bonne quantité de chaînes de caractères. On notera que cette version de la macro ne marche que si on donne des caractères majuscules ; des minuscules donneraient [ll][oo][ll], ce qui est inutile. Comme tout en WKT est écrit par défaut en majuscules, c'est plus simple pour moi de taper des majuscules dans le script de toute façon.

Notre script ressemble donc maintenant à ceci :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl
define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
ignorecase(POINT)\s*(?:\s+ignorecase(EMPTY)|\(\s*number\s+number\s*\))

Coordonnées 2D

On peut commencer à se préparer à gérer des géométries autres que le point en faisant quelques autres modifications : d'abord, toutes les géométries travaillent avec des paires de coordonnées. On pourrait définir un coords qui correspond juste à une paire de coordonnées avec des espaces :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl
define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
define(coords, number\s+number)dnl
ignorecase(POINT)\s*(?:\s+ignorecase(EMPTY)|\(\s*coords\s*\))

Géométries optionnellement vides

Toutes les géométries peuvent être complètement vides avec EMPTY ou contenir des coordonnées, des listes de coordonnées, ou des listes de géométries. On peut donc ajouter une autre macro qui nous permet de fournir le nom de la géométrie et ce qu'elle contient quand elle n'est pas vide, et la macro s'occupe de gérer le cas d'une géométrie vide et d'emballer le contenu avec des parenthèses :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl
define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
define(coords, number\s+number)dnl
define(make_geometry, `ignorecase($1)\s*(?:\s+ignorecase(EMPTY)|\(\s*$2\s*\))')dnl
make_geometry(POINT, coords)

Géométries sous forme de listes

On va maintenant passer à la vitesse supérieure et implémenter le LINESTRING:

make_geometry(LINESTRING, coords(?:\s*,\s*coords)*)

On définit ici la capacité de la ligne brisée à stocker une ou plusieurs coordonnées. Chaque coordonnée est séparée par des virgules, avec optionnellement des espaces. Toutes les listes de coordonnées ou les listes de listes de coordonnées (pour les polygones) sont représentées sous cette forme, donc on peut encore faire une nouvelle macro :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl
define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
define(coords, number\s+number)dnl
define(make_geometry, `ignorecase($1)\s*(?:\s+ignorecase(EMPTY)|\(\s*$2\s*\))')dnl
define(make_geometry_list, `make_geometry($1, $2(?:\s*,\s*$2)*)')dnl
make_geometry(POINT, coords)
make_geometry_list(LINESTRING, coords)

Éléments de liste optionnellement vides

On va pouvoir monter d'un cran et définir le polygone :

make_geometry_list(POLYGON, (?:ignorecase(EMPTY)|\(\s*coords(?:\s*,\s*coords)*\s*\)))

Encore de la répétition ! Cette fois, c'est dans le contenu du polygone qu'on peut avoir des éléments vides. Un exemple plus concret sera plus parlant :

POLYGON (
  (10 20, 30 20, 30 40, 10 40, 10 20),
  EMPTY,
  (15 18, 15.4 18, 15.4 18.5, 15 18)
)

Les polygones sont constitués de plusieurs anneaux linéaires, mais la grammaire du WKT autorise que les anneaux soient vides. Par conséquent, les éléments à l'intérieur de notre liste sont eux-mêmes vides, et POLYGON EMPTY est différent de POLYGON (EMPTY) !

On va pouvoir simplifier ça de deux façons. D'abord, on va rajouter une macro qui permet juste de rendre n'importe quoi optionnellement vide, pas juste une géométrie :

define(emptyable, `(?:'ignorecase(EMPTY)`|\(\s*$1\s*\))')dnl
make_geometry_list(POLYGON, emptyable(coords(?:\s*,\s*coords)*))

On peut ensuite définir une autre fonction pour générer une liste de n'importe quoi, et pas une géométrie entière contenant des listes :

define(make_list, emptyable($1(?:\s*,\s*$1)*))dnl
make_geometry_list(POLYGON, make_list(coords))

On utilise make_geometry_list, donc on construit une géométrie qui contiendra une liste de make_list(coords), c'est-à-dire une liste de listes de coordonnées. Vu que make_list rend la liste optionnellement vide, on autorise un polygone vide, un polygone avec des anneaux linéaires vides, mais pas des coordonnées vides dans les anneaux.

On n'utilisera cependant pas directement make_list à l'intérieur de make_geometry_list : cela utilise emptyable, qui ne requiert pas une particularité liées aux géométries elles-mêmes. Avec make_list, il deviendrait possible de taper POINTEMPTY, alors qu'au moins un espace est requis entre POINT et EMPTY. Cependant, POINT(1 2) doit rester valide, sans espace avant la parenthèse. make_geometry_list gère ce cas correctement en placant un \s+ avant EMPTY mais make_list ne le fait et ne doit pas le faire car l'espace n'est pas forcément nécessaire dans toutes les listes.

Géométries multiples

Il ne nous reste plus qu'à définir les 3 derniers types de géométries, celles qui regroupent d'autres géométries sans avoir de propriétés particulières. Elles sont plus flexibles et autorisent des éléments vides n'importe où !

make_geometry_list(MULTIPOINT, emptyable(coords))
make_geometry_list(MULTILINESTRING, make_list(coords))
make_geometry_list(MULTIPOLYGON, make_list(make_list(coords)))

Pour mieux comprendre, voici une liste de toutes les possibilités de géométries multiples vides :

En fait, les seules possibilités interdites sont que ni les lignes brisées ni les anneaux linéaires ne peuvent contenir des points vides. C'est assez logique, puisque les lignes brisées sont censées relier des points entre eux ; si un des points est vide, la ligne brisée... se brise.

Avec make_geometry_list, on gère déjà tous les cas où les multi-géométries sont elles-mêmes vides, mais il nous faut ensuite gérer les autres cas en modulant les éléments contenus dans la liste. On utilise emptyable(coords) dans MULTIPOINT pour autoriser des points vides. On utilise make_list, qui génère toujours des listes qui peuvent être vides, pour gérer les lignes brisées vides, mais on n'utilise pas emptyable pour les coordonnées puisque les points ne peuvent être vides. Pour le multi-polygone, on utilise deux fois make_list pour faire une liste de listes d'anneaux linéaires où les anneaux linéaires peuvent être vides, les polygones peuvent être vides, mais toujours pas les points.

On notera que la définition de POLYGON faite précédemment est exactement la même que celle de MULTILINESTRING ; en fait on avait déjà fait cette remarque dans l'article précédent. On peut fusionner les deux définitions en une seule :

make_geometry_list((?:POLYGON|MULTILINESTRING), make_list(coords))

On utilise ici une propriété implicite de notre macro ignorecase : elle ne travaille que sur les lettres, par sur les caractères spéciaux des expressions régulières comme (?:|). On peut donc les insérer en toute sécurité et ils seront reproduits tels quels, mais à la fois POLYGON et MULTILINESTRING seront rendus insensibles à la casse comme prévu.

Script final

Voilà notre script m4 enfin terminé :

define(ignorecase, `patsubst($1, \w, `[`\&'translit(\&, A-Z, a-z)]')')dnl
define(number, [+-]?(?:\d+(?:[.,]\d*)?|[.,]\d+)(?:ignorecase(E)[+-]?\d+)?)dnl
define(coords, number\s+number)dnl
define(emptyable, `(?:'ignorecase(EMPTY)`|\(\s*$1\s*\))')dnl
define(make_list, emptyable($1(?:\s*,\s*$1)*))dnl
define(make_geometry, `ignorecase($1)\s*(?:\s+ignorecase(EMPTY)|\(\s*$2\s*\))')dnl
define(make_geometry_list, `make_geometry($1, $2(?:\s*,\s*$2)*)')dnl
make_geometry(POINT, coords)
make_geometry_list(LINESTRING, coords)
make_geometry_list((?:POLYGON|MULTILINESTRING), make_list(coords))
make_geometry_list(MULTIPOINT, emptyable(coords))
make_geometry_list(MULTIPOLYGON, make_list(make_list(coords)))

C'est loin d'être le plus lisible au monde, mais le plus important est que ça me permettra dans le prochain article d'aller encore plus loin, bien au-dessus de ce que OpenSearch autorise : écrire une seule expression régulière qui prenne en charge l'intégralité du Well-Known Text. Cela incluera des géométries en 4 dimensions !


Commentaires

Il n'y a pour l'instant aucun commentaire. Soyez le premier !