Partie 5 : Parser les commandes, création de la boîte à outils
Bonjour à toutes et tous 😃
Dans la précédante partie nous avons rajouté la possibilité de stocker des type de données différents via l'introduction du concept de table.
db > create user
Table created successfully
db > insert user 1 name email@example.com
Record inserted successfully
db > insert user 2 name2 email2@example.com
Record inserted successfully
db > create car
Table created successfully
db > select car
db > insert car XXX Volvo
Record inserted successfully
db > insert car YYY Renault
Record inserted successfully
db > select user
User(User { id: 1, username: "name", email: "email@example.com" })
User(User { id: 2, username: "name2", email: "email2@example.com" })
db > select car
Car(Car { id: "XXX", brand: "Volvo" })
Car(Car { id: "YYY", brand: "Renault" })
Bien que fonctionnel, ce design a deux gros problèmes:
- les schémas de données sont fixes
- rajouter un nouveau type de données nécessite :
- d'écrire le parser
- définir un nouveau type de table
- implémenter la sérialisation de la données
C'est pas souple pour un sou. 😑
Je vous propose dans cette partie d'introduire une nouvelle notation qui va nous permettre de faire ce que l'on a besoin.
Pour cela nous allons avoir besoin d'un nouveau parser bien plus efficace et versatile.
C'est ce que je vous propose de construire aujourd'hui.
Je suis conscient que la marche de complexité est grande entre cette partie et la précédente.
Si vous ne comprenez pas tout malgré mes explications, ce n'est pas grave, nous utiliseront le travail de cette partie comme une lib.
Vous n'aurez qu'à la considérer comme une boîte noire. 😃
Cahier des charges
Avant de nous lancer à corps perdu dans le code. Definissons les contours de l'API désirée.
Nous voulons que l'utilisateur à la création de la table puisse annoncer le schéma associé.
(
id INTEGER, -- un nombre
name TEXT(50), -- chaîne de caractèrees sur 50 bytes
email TEXT(25) -- chaîne de caractèrees sur 25 bytes
);
(
id TEXT(128),
brand TEXT(50),
);
Nous voulons également que lors de l'insertion, l'utilisateur définisse le mapping entre les champs et leurs valeurs
INSERT INTO User (id, name, email)
VALUES(42, 'name1', 'email1@example.com');
INSERT INTO Car (id, brand)
VALUES('XXX', 'Volvo');
Et finalement nous désirons sélectionner les champs renvoyés (on dit projeté) depuis la table. L'*
signifie tous les champs.
SELECT id, name FROM User;
SELECT * FROM User;
Tokenization
Notre oeil est capable en connaissant la syntaxe SQL d'interpréter ce que la commande va ou doit faire. Mais la machine n'a pas d'yeux.
Elle manipule des bytes et donc tout doit rentrer dans se mode pensé.
Une machine pour interpréter une commande va d'abord tokenizer une chaîne de caratères, puis interpréter cet emchaînement de tokens dans ce que l'on appelle une grammaire.
Le INSERT INTO User
a une signification, INSERT
tout seul ou INTO
tout seul ne veut rien dire, par contre INSERT INTO table
signifie "insérer dans la table 'table'".
Comme en français, en fait, vous me direz, et vous avez raison. ^^
Laissez moi vous montrer comment la machine voit
INTEGER, name TEXT(50), email TEXT(25));
(id
- token "CREATE" : mot clef réservé
- token Whitespace : espace blanc
- token "TABLE" : mot clef réservé
- token Whitespace : espace blanc
- literal "User" : enchaînement de char jusqu'à un espace blanc ou un parenthèse ouvrante
- token Whitespace : espace blanc
- token "(" : parenthèse ouvrante
- literal "id"
- token Whitespace : espace blanc
- token "INTEGER"
- token "," : séparateur réservé
- token Whitespace
- literal "name"
- token Whitespace
- token "TEXT"
- token "("
- literal 50 : un nombre
- token ")"
- token ","
- token Whitespace
- literal "name"
- token Whitespace
- token "TEXT"
- token "("
- literal 25 : un nombre
- token ")"
- token ")"
- token ";"
Si on sérialise ça donne
CREATE, WHITESPACE, TABLE, WHITESPACE, "User", WHITESPACE, OPEN_PAREN, "id", WHITESPACE, INTEGER, COMMA, WHITESPACE, "name", WHITESPACE, TEXT, OPEN_PAREN, 50, CLOSE_PAREN, COMMA, WHITESPACE, "email", WHITESPACE, TEXT, OPEN_PAREN, 25, CLOSE_PAREN
Mais ça ce n'est que le début, il faut ensuite regrouper ce qui le doit.
Si j'écris :
- WHITESPACE* ça veut dire 0 ou plus espace blancs
- WHITESPACE+ ça veut dire au moins un espace blanc
- CREATE, WHITESPACE+, TABLE, WHITESPACE+, "User" : définition de la commande et du nom de la table à créer
- WHITESPACE*, OPEN_PAREN : début de groupe de définition du schéma
- "id", WHITESPACE+, NUMBER : définition du champ "id"
- COMMA, WHITESPACE* : séparateur de champ
- "name", WHITESPACE+, TEXT, OPEN_PAREN, 50, CLOSE_PAREN : définition du champ "name"
- COMMA, WHITESPACE* : séparateur de champ
- "email", WHITESPACE+, TEXT, OPEN_PAREN, 25, CLOSE_PAREN : définition du champ "email"
- WHITESPACE*, CLOSE_PAREN
- WHITESPACE*, SEMICOLON
On a ici une subdivision et une factorisation à opérer.
Le type de la colonne devient alors une entité à part entière {column_def}
- NUMBER
- TEXT, OPEN_PAREN, 50, CLOSE_PAREN
- TEXT, OPEN_PAREN, 25, CLOSE_PAREN
Si on nettoie pour ne garder que les espaces essentiel et que l'on utilise notre factorisation, cela donne
CREATE, WHITESPACE, TABLE, WHITESPACE, {table name}, OPEN_PAREN, [{column_name}, WHITESPACE, {column_def}, COMMA ]+, CLOSE_PAREN, SEMICOLON
le
[...]+
signifie que le groupe se répète au moins une fois.
Vous la sentez la difficulté du problème auquel on s'attèle? 😅
Sans une rigueur à tout épreuve, nous allons aller très vite dans le mur !
Tokens
La première chose à faire est de faire l'inventaire exhaustif des tokens.
Les mot clefs déjà:
- CREATE
- TABLE
- INSERT
- INTO
- VALUES
- SELECT
- FROM
La ponctuation
- OPEN_PAREN
- CLOSE_PAREN
- COMMA
- SEMICOLON
- QUOTE
- WHITESPACE
- STAR
Les types de champs
- INTEGER
- TEXT
Puis les literals, les tokens qui sont dynamiques
- LITERAL_INTEGER : tout ce qui se parse vers du i64
- LITERAL_STRING : tout le reste qui ne peut pas être interprété
Grammaire
Pour définir les grammaire, à comprendre l'enchaînement des tokens.
Je vous propose d'utiliser une syntaxe appelée l'BNF.
Et un site qui permet de les visualiser.Grammaire de CREATE TABLE
CreateTable ::= 'CREATE' 'TABLE' LiteralString OpenParen ColumnDef* CloseParen Semicolon
ColumnDef ::= LiteralString ColumnType | LiteralString ColumnType Comma
ColumnType ::= 'INTEGER' | ColumTypeText
ColumTypeText ::= 'TEXT' OpenParen LiteralInteger CloseParen
LiteralString ::= [A-Za-z0-9_]*
LiteralInteger ::= [0-9]+
OpenParen ::= '('
CloseParen ::= ')'
Comma ::= ','
Semicolon ::= ';'
Grammaire de SELECT
Select ::= 'SELECT' Column* 'FROM' LiteralString Semicolon
Column ::= '*' | LiteralString | LiteralString Comma
LiteralString ::= [A-Za-z0-9_]*
LiteralInteger ::= [0-9]+
OpenParen ::= '('
CloseParen ::= ')'
Comma ::= ','
Semicolon ::= ';'
Grammaire de INSERT INTO
InsertInto ::= 'INSERT' 'INTO' LiteralString OpenParen Column* CloseParen 'VALUES' OpenParen Value* CloseParen Semicolon
Column ::= LiteralString | LiteralString Comma
Value ::= (LiteralInteger | LiteralString ) | ((LiteralInteger | LiteralString) Comma )
LiteralString ::= "'" [A-Za-z0-9_]* "'"
LiteralInteger ::= [0-9]+
OpenParen ::= '('
CloseParen ::= ')'
Comma ::= ','
Semicolon ::= ';'
Scanner
Je vous est dit que nous humain, nous balayons la commande de nos yeux de gauche à droite, et nous interprétons la série de lettres, chiffres, symboles comme des mots, des groupes ou des nombres.
Notre ordinateur va devoir faire pareil.
L'opération de balayage se nomme en anglais un scan.
A l'état initial le curseur est à la position 0.
CREATE TABLE User (id INTEGER, name TEXT(50), email TEXT(25));
^
On peut alors le faire avancer de 1, pour consommer un caractère, ici le 'C'
CREATE TABLE User (id INTEGER, name TEXT(50), email TEXT(25));
^
Ou manger plus d'un caractère. Ici on consomme le 'CREATE'.
CREATE TABLE User (id INTEGER, name TEXT(50), email TEXT(25));
^
Nous allons bâtir ce Scanner.
Il a beaucoup de point de commun avec le Cursor qui permet lui aussi de balayer une chaîne de caractères.
Notre Scanner sera un wrapper autours de ce Cursor, mais on ne peut pas l'utiliser tel quel car il n'est pas possible d'accrocher des comportements sur une structure qui ne nous appartient pas.
Nous allons le rendre générique pour pouvoir l'utiliser sur autre chose que des chaîne de caractères plus tard. D'où le T
.
Puis on lui accroche des comportements
Erreurs
Pour rendre notre gestion d'erreurs, on se créé notre propre énumération.
type Result<T> = Result;
Visitor
Tout notre fonctionnement de parse va se reposer sur un patron de développement bien connu qui se nomme le Pattern Visitor.
Celui-ci permet de définir des cahiers des charges qui indique si l'enchaînement des tokens est valides ou pas sur n'importe quelle stucture de données qui peuvent enchâsser n'importe quelle autre structures de données et ça à profondeur infinie et même récursive.
Ce trait paye pas de mine, mais il est incroyablement puissant! Lorsque l'on bâtira les structures de plus haut niveau, vous verrez ses pouvoirs. ^^
Tokens
Dans la partie des cahiers des charges nous avons fait l'inventaire des tokens que l'on veut reconnaître.
Matchers
C'est beau d'avoir une énumération mais comment on passe de notre chaîne de caractères à l'énumération ?
Et bien réfléchissez à comment vous vous lisez. Vous regardez la lettre ou le symbole et vous le comparez à votre base de données stockée quelque part dans votre cerveau.
Ah ça c'est une virgule! ça c'est un 'a' ! etc ...
/// On regarde le premier caractère de la chaîne et on le compare
/// avec ce que l'on a besoin de vérifier
Vérifier un token complet comme 'CREATE' est la même chose, mais non plus sur le premier caractère mais sur le pattern complet.
Mais on peut faire des choses plus intéressante, comme récupérer un nombre.
Alors c'est intéressant de savoir que c'est un nombre, mais est-ce qu'il fait 1 caractère, 2, 3, 4, plus ?
On sait pas en l'état.
Modifions le retour de la méthode pour renvoyer la position en plus du résultat.
Et à partir de là, il est possible de transformer des caractères ici "125" en un nombre 125.
let data = "125titi";
let = match_number;
assert_eq!;
On peut alors transformer les autres matchers pour également renvoyer la position.
Dans ces deux cas on peut alors maintenant déplacer le curseur du bon nombre de caractères en cas de succès.
Une fois que l'on a compris ça, on peut match tout ce qu'on veut, si on dit que une string c'est tout les alphanumeric et '_' alors le matcher est
Reconnaissance des tokens
On a nos token, on des matcher qui nous permettent à partir d'une slice de savoir si les N premiers caractères sont corrects ou non.
Pour cela on introduit un nouveau trait
- T : le type de données de la slice du curseur du Scanner
- U : ce que l'on tente de reconnaître
Tokenizer
Notre Scanner est conçu pour être le plus versatile possible.
Le T peut être fixé comme on l'entend, ici par exemple nous allons le définir à u8
parce que nous allons uniquement manipuler des bytes.
type Tokenizer<'a> = ;
At
Nous n'avons pas encore tout nos protagonistes, laissez moi vous présenter At
. 😀
Il va avoir pour travail de conserver la place de donnée recherchée dans l'ensemble de la slice.
Grâce à ce mécanisme, il est possible de conserver une trace de ce l'on a récupéré.
Pour un token ce n'est pas très utile, mais on peut aussi l'utiliser avec le match_number
Et là tout de suite l'intérêt devient évident!
Matchers
Les matcher que nous avons créé son bien mais manque de versalité.
Je voudrais les balader dans le code et ne les utiliser que lorsque c'est utile en lazy exécution.
Et il existe un pattern de développement parfait pour cela qui se nomme le currying.
C'est basiquement une fonction qui en renvoit une autre.
En rust, cela passe par les closure et le impl Fn
, j'ai expliqué toutes ces subtilités dans un précédent article.
Curryons le match_char, il devient.
On peut alors l'utiliser ainsi
On voit que l'on retarde l'application du match.
Voici les matchers en mode curriedMatchers curried
+ use<'_>
Utiliser le Tokenizer pour reconnaître les tokens
On accroche à notre Tokenizer un fonction qui prend un 'matcher' en paramètre
Matcher les tokens
On y est presque !
On introduit un nouveau trait Match
et un type Matcher
.
pub type Matcher = ;
Le Box est obligatoire car deux closures différentes sont deux types de structures différentes or dans la suite nous avons un match
qui force la cohérence des types.
Que l'on applique à Token
.
Finalement nous pouvons vérouiller le type de At<'a, T, U>
en At<'a, u8, Token>
. Car nous ne manipulerons que des bytes qui deviennent des Token.
type TokenOutput<'a> = ;
Pour enfin implémenter Recognizable
sur Token
!!
Et on utilise cela ainsi
On peut finalement se faire une petite fonction utilitaire.
Qui s'utilise ainsi
On voit bien que l'on se déplace dans la slice et que l'on match les tokens au fur et à mesure. 😍
Composants
Maintenant que nous avons des tokens, nous allons pouvoir les assembler.
Pour y arriver nous allons ajouter un comportement à notre Scanner
Tout objet U qui implémente Visitable est maintenant capable de visiter le Scanner, ce pattern s'appelle une blanket implementation.
Whitespaces
Pour mette en pratique, prenons l'exemple le plus simple: capturer plus d'un espace blanc.
On se créé une structure Whitespaces
.
;
Pas besoin de champ dans cette structure, ce n'est qu'une accroche pour y appliquer le Visitor.
On peut alors consommer nos espaces blancs depuis le Tokenizer qui est un Scanner et donc qui possède la méthode "visit".
C'est le niveau 1 de la puissance du Visitor, mais on peut l'utiliser pour faire des choses bien plus complexe.
Assembler des Visitor
On va faire un example un artificiel.
Par exemple on peut définir un Visiteur pour l'echaînement de tokens [CREATE,TABLE].
;
On y mélange à la fois du Recognizable et du Visitable.
Et puis on peut aussi avoir des composants qui ont plus de logique, comme pour capturer le nom de la table.
;
// petit utilitaire pour récupérer le contenu
Et alors on peut même esquisser le travail du prochain article de la série. En capturant le nom de la table à créer.
J'espère que vous commencez à entrevoir la puissance du pattern de développement que l'on a choisi ? 😊
Tout est composable, et donc on peut assembler des morceaux relativement simple et bâtir des cathédrales de complexité pour parser des choses qui de prime abord semblent insurmontables.
Groupes
Un autre problème dans l'art du parsing est d'avoir la capacité de comprendre le concept de groupe.
Si on prend la commande de création de table, le groupe est représenté par un ensemble de caractères délimité par "(" et ")".
create table users ( id number, name text(50) );
^ ^
début fin
Nous devons trouver un moyen de faire comprendre à la machine cette notion.
Forecasting
Savoir si on commence un groupe c'est facile, on match un token ici le "(".
Mais par contre trouver la fin du groupe est plus tricky.
Il faut littéralement voir le futur du parse, voir au-delà du curseur du Scanner.
On défini un trait pour réprésenter ce comportement de recherche.
Et une enumeration pour représenter le résultat de ce comportement.
On peut alors en faire une fonction utilitaire qui permet de matcher tout ce qui est capable d'implémenter Forecast.
Groupe délimité
Ok! Là on rentre dans le dur, on va régler le problème que toute personne qui s'attaque à la création d'un parser rencontre : les groupes imbriqués.
Voici le vrai groupe.
create table users ( id number, name text(50) );
^ ^
début fin
Le contenu est alors : "( id number, name text(50) )"
Il ne faut surtout pas matcher le premier token ")".
create table users ( id number, name text(50) );
^ ^
début mauvaise fin
Sinon on se retrouve avec un groupe incorrect : "( id number, name text(50)"
L'idée est alors de compter les tokens de début et de fin pour savoir si on délimite correctement ou non.
Voici une implémentation qui renvoie un ForecastResult.
+ 'a
On peut alors matcher les groupes qui nous intéressent.
On se créé alors un objet GroupKind pour lui accrocher le comportement Forecast.
Et alors cela nous ouvre le droit d'utiliser notre méthode forecast
Separated List
Le concept de liste séparée est assez basique.
Vous avez par exemple l'enchaînement suivant 12,4,78,22
.
Et vous voulez récupérer les nombres 12
, 4
, 78
et 22
.
Nous avons alors deux critères:
- le séparateur que l'on doit reconnaître
- les éléments qui doivent être visités
Attention, le dernier élément ne possède pas toujours de séparateur terminal.
Nous allons accrocher nos comportement sur une structure.
/// S : le séparateur
/// T : les éléments de la liste
On défini
On peut alors accrocher le Visitable dessus
Pour tester je vais créer deux Visitable artificiels.
;
;
Et on peut alors extraire ce que l'on veut.
Attention, le concepteur du parseur est responsable de la chaîne visitée par le SeparatedList.
Si elle contient plus de token que la liste elle-même, par exemple "1,2,3) + (4,5,6)"
Alors le parse échouera à la première ")".
La SeparatedList doit-être utilisé dans un contexte de groupe délimité.
Acceptor
Allez dernier concept et on aura fini. 😅 Courage ! 🙏
Le principe d'Acceptor est de pouvoir enchaîner plusieurs essaie de Visitable et matcher le bon.
On a esquissé le Create Table
On va esquisser le Select * From
;
L'Acceptor permet de chaîner nos opération de visites
Il prend une fonction appelé un transformer qui permet de transformer le contenu de la variante en une variante d'énumération.
Et alors, on a un système très versatile.
Du point de vue du constructeur de la grammaire du parseur, il manipule des concepts de haut-niveau qui viennent abstraire les opérations de bas niveau de reconnaissance de tokens, de leur enchaînement puis de leur transformation.
Conclusion
Bon c'était un peu complexe et long, mais bravo si vous êtes arrivé jusqu'ici. 😎
Nous avons bâtis tous les outils nécessaire pour parser à peu près n'importe quoi.
Dans la prochaine partie, nous mettrons en place la vraie grammaire. Promis ça sera bien plus simple. 😅
Merci de votre lecture ❤️
Vous pouvez trouver le code la partie ici et le diff là.
Ce travail est sous licence CC BY-NC-SA 4.0.