Partie 5 : Parser les commandes, création de la boîte à outils

Lecture 64 min. •


Table des matières

Les articles de la série

Bonjour à toutes et tous 😃

Dans la [précédente partie](/rustqlite-4 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:

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é.

CREATE TABLE User (
    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
);

CREATE TABLE Car (
    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

CREATE TABLE User (id INTEGER, name TEXT(50), email TEXT(25));

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

On a ici une subdivision et une factorisation à opérer.

Le type de la colonne devient alors une entité à part entière {column_def}

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à:

La ponctuation

Les types de champs

Puis les literals, les tokens qui sont dynamiques

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 ::= ';'

CreateTable:

ColumnType:


ColumTypeText:


LiteralString:


LiteralInteger:

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 ::= ';'

Select:

Column:


LiteralString:


LiteralInteger:


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 ::= ';'

InsertInto:


Column:


Value:


LiteralString:


LiteralInteger:

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.

struct Scanner<'a, T: Sized> {
    cursor: Cursor<&'a [T]>,
}

Puis on lui accroche des comportements

impl<'a, T> Scanner<'a, T> {
    /// Create a new Scanner
    pub fn new(input: &'a [T]) -> Scanner<'a, T> {
        Self {
            cursor: Cursor::new(input),
        }
    }

    /// Return the data remaining after the cursor position
    pub fn remaining(&self) -> &'a [T] {
        &self.cursor.get_ref()[self.cursor.position() as usize..]
    }

    /// Return the cursor position in the slice
    pub fn cursor(&self) -> usize {
        self.cursor.position() as usize
    }

    /// Jump the cursor at position can be after or before
    pub fn jump(&mut self, position: usize) {
        self.cursor.set_position(position as u64)
    }

    /// Move the cursor to N position to the right
    pub fn bump_by(&mut self, size: usize) {
        self.cursor.set_position((self.cursor() + size) as u64)
    }

    /// Return all data wrapped by the cursor
    pub fn data(&self) -> &'a [T] {
        self.cursor.get_ref()
    }
}

Erreurs

Pour rendre notre gestion d’erreurs, on se créé notre propre énumération.

type Result<T> = std::result::Result<T, ParseError>;

#[derive(Debug)]
enum ParseError {
    UnexpectedEOF,
    UnexpectedToken,
}

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.

trait Visitable<'a, T>: Sized {
    fn accept(scanner: &mut Scanner<'a, T>) -> parser::Result<Self>;
}

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.

enum Token {
    /// whitespace character 0x20 ascii char
    Whitespace,
    /// opening parenthesis "(" 0x28
    OpenParen,
    /// closing parenthesis ")" 0x29
    CloseParen,
    /// comma "," 0x2c
    Comma,
    /// semicolon ";" 0x3b
    Semicolon,
    /// semicolon "*" 0x2a
    Star,
    /// simple quote "'" 0x27
    Quote,
    /// CREATE token
    Create,
    /// TABLE token
    Table,
    /// INSERT token
    Insert,
    /// VALUES token
    Values,
    /// INTO token
    Into,
    /// SELECT token
    Select,
    /// FROM token
    From,
    /// Column type
    Field(Field),
    /// Literal value
    Literal(Literal),
    Wildcard,
}

pub enum Literal {
    /// number recognized
    Number,
    /// string recognized
    String,
}

pub enum Field {
    /// INTEGER token
    Integer,
    /// TEXT token
    Text,
}

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
fn match_char(input: &str, c: char) -> bool {
    input.as_bytes()[0] == c as u8
}

#[test]
fn test_match_char() {
    assert!(match_char("toto", 't'));
    assert!(!match_char("yoto", 't'));
}

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.

fn match_pattern(input: &str, pattern: &str) -> bool {
    input[..pattern.len()].as_bytes().to_ascii_lowercase()
        == pattern.as_bytes().to_ascii_lowercase()
}

#[test]
fn test_match_pattern() {
    assert!(match_pattern("create table", "create"));
    assert!(!match_pattern("creata table", "create"));
}

Mais on peut faire des choses plus intéressante, comme récupérer un nombre.

fn match_number(input: &str) -> bool {
    let mut pos = 0;
    let mut found = false;
    let input = input.as_bytes();
    loop {
        if pos == input.len() {
            return found;
        }
        if input[pos].is_ascii_digit() {
            found = true;
            pos += 1;
        } else {
            return found;
        }
    }
}

#[test]
fn test_match_number() {
    assert!(match_number("125titi"));
    assert!(!match_number("titi"))
}

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.

fn match_number(input: &str) -> (bool, usize) {
    let mut pos = 0;
    let mut found = false;
    let input = input.as_bytes();
    loop {
        if pos == input.len() {
            return (found, pos);
        }
        if input[pos].is_ascii_digit() {
            found = true;
            pos += 1;
        } else {
            return (found, pos);
        }
    }
}

#[test]
fn test_match_number() {
    assert_eq!(match_number("125titi"), (true, 3));
    assert_eq!(match_number("titi"), (false, 0));
}

Et à partir de là, il est possible de transformer des caractères ici “125” en un nombre 125.

let data = "125titi";
let (_, size) = match_number(data);
assert_eq!(data[..size].parse::<i64>(), Ok(125_i64));

On peut alors transformer les autres matchers pour également renvoyer la position.

fn match_char(input: &str, c: char) -> (bool, usize) {
    if input.as_bytes()[0] == c as u8 {
        return (true, 1);
    }
    (false, 0)
}

fn match_pattern(input: &str, pattern: &str) -> (bool, usize) {
    if input[..pattern.len()].as_bytes().to_ascii_lowercase()
        == pattern.as_bytes().to_ascii_lowercase()
    {
        return (true, pattern.len());
    }
    (false, 0)
}

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

fn match_string(input: &str) -> (bool, usize) {
    let mut pos = 0;
    let mut found = false;
    let input = input.as_bytes();
    loop {
        if pos == input.len() {
            return (found, pos);
        }
        if input[pos].is_ascii_alphanumeric() || input[pos] == b'_' {
            found = true;
            pos += 1;
        } else {
            return (found, pos);
        }
    }
}

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

trait Recognizable<'a, T, U> {
    fn recognize(self, scanner: &mut Scanner<'a, T>) -> Result<Option<U>>;
}

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> = Scanner<'a, u8>;

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.

fn match_pattern(input: &[u8], pattern: &str) -> (bool, usize) {
    if input[..pattern.len()].to_ascii_lowercase() == pattern.as_bytes().to_ascii_lowercase() {
        return (true, pattern.len());
    }
    (false, 0)
}

#[test]
fn test_at() {
    let source = b"create table users (id integer, name text);";
    let cursor = 7;
    let (_, size) = match_pattern(&source[cursor..], "table");
    let result = At::new(cursor, cursor + size, Token::Table, source);

    assert_eq!(
        String::from_utf8_lossy(&result.source[result.start..result.end]),
        "table"
    );
}

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!

fn match_number(input: &[u8]) -> (bool, usize) {
    let mut pos = 0;
    let mut found = false;
    loop {
        if pos == input.len() {
            return (found, pos);
        }
        if input[pos].is_ascii_digit() {
            found = true;
            pos += 1;
        } else {
            return (found, pos);
        }
    }
}

#[test]
fn test_number() {
    let source = b"name text(50);";
    let cursor = 10;
    let (_, size) = match_number(&source[cursor..]);
    let result = At::new(
        cursor,
        cursor + size,
        Token::Literal(Literal::Number),
        source,
    );

    assert_eq!(
        String::from_utf8_lossy(&result.source[result.start..result.end]),
        "50"
    );
}

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.

pub fn match_char(pattern: char) -> impl Fn(&[u8]) -> (bool, usize) {
    move |x: &[u8]| (x[0] == pattern as u8, 1)
}

On peut alors l’utiliser ainsi

#[test]
fn test_match_char_curry() {
    let match_c = super::match_char('c');
    assert_eq!(match_c("c".as_bytes()), (true, 1));
    assert_eq!(match_c("t".as_bytes()), (false, 1));
}

On voit que l’on retarde l’application du match.

Voici les matchers en mode curried

Matchers curried 
pub fn match_char(pattern: char) -> impl Fn(&[u8]) -> (bool, usize) {
    move |x: &[u8]| (x[0] == pattern as u8, 1)
}

pub fn match_pattern(pattern: &str) -> impl Fn(&[u8]) -> (bool, usize) + use<'_> {
    move |x: &[u8]| -> (bool, usize) {
        if pattern.is_empty() {
            return (false, 0);
        }
        if pattern.len() > x.len() {
            return (false, 0);
        }
        if pattern.as_bytes().to_ascii_lowercase() == x[..pattern.len()].to_ascii_lowercase() {
            return (true, pattern.len());
        }
        (false, 0)
    }
}

pub fn match_predicate<F>(predicate: F) -> impl Fn(&[u8]) -> (bool, usize)
where
    F: Fn(&[u8]) -> (bool, usize),
{
    move |x: &[u8]| predicate(x)
}

pub fn match_number() -> impl Fn(&[u8]) -> (bool, usize) {
    move |x: &[u8]| -> (bool, usize) {
        if x.is_empty() {
            return (false, 0);
        }

        let mut pos = 0;
        let mut found = false;
        loop {
            if pos == x.len() {
                return (found, pos);
            }
            if x[pos].is_ascii_digit() {
                found = true;
                pos += 1;
            } else {
                return (found, pos);
            }
        }
    }
}

pub fn match_string() -> impl Fn(&[u8]) -> (bool, usize) {
    move |x: &[u8]| -> (bool, usize) {
        if x.is_empty() {
            return (false, 0);
        }
        let mut pos = 0;
        let mut found = false;

        loop {
            if pos == x.len() {
                return (found, pos);
            }
            if x[pos].is_ascii_alphanumeric() || x[pos] == b'_' {
                found = true;
                pos += 1;
            } else {
                return (found, pos);
            }
        }
    }
}

Utiliser le Tokenizer pour reconnaître les tokens

On accroche à notre Tokenizer un fonction qui prend un ‘matcher’ en paramètre

impl Tokenizer<'_> {
    pub fn recognize<F>(&mut self, matcher: F) -> parser::Result<(bool, usize)>
    where
        F: Fn(&[u8]) -> (bool, usize),
    {
        if self.remaining().is_empty() {
            return Err(ParseError::UnexpectedEOF);
        }

        let data = self.remaining();
        Ok(matcher(data))
    }
}

Matcher les tokens

On y est presque !

On introduit un nouveau trait Match et un type Matcher.

pub type Matcher = Box<dyn Fn(&[u8]) -> (bool, usize)>;

pub trait Match {
    fn matcher(&self) -> 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.

impl Match for Token {
    fn matcher(&self) -> Matcher {
        match self {
            Token::Whitespace => Box::new(matchers::match_predicate(|x| {
                (x[0].is_ascii_whitespace(), 1)
            })),
            Token::OpenParen => Box::new(matchers::match_char('(')),
            Token::CloseParen => Box::new(matchers::match_char(')')),
            Token::Comma => Box::new(matchers::match_char(',')),
            Token::Create => Box::new(matchers::match_pattern("create")),
            Token::Table => Box::new(matchers::match_pattern("table")),
            Token::Insert => Box::new(matchers::match_pattern("insert")),
            Token::Into => Box::new(matchers::match_pattern("into")),
            Token::Values => Box::new(matchers::match_pattern("values")),
            Token::Select => Box::new(matchers::match_pattern("select")),
            Token::From => Box::new(matchers::match_pattern("from")),
            Token::Semicolon => Box::new(matchers::match_char(';')),
            Token::Star => Box::new(matchers::match_char('*')),
            Token::Quote => Box::new(matchers::match_char('\'')),
            Token::Field(field) => field.matcher(),
            Token::Literal(literal) => literal.matcher(),
        }
    }
}

impl Match for Literal {
    fn matcher(&self) -> Matcher {
        match self {
            Literal::Number => Box::new(matchers::match_number()),
            Literal::String => Box::new(matchers::match_string()),
        }
    }
}

impl Match for Field {
    fn matcher(&self) -> Matcher {
        match self {
            Field::Text => Box::new(matchers::match_pattern("Text")),
            Field::Integer => Box::new(matchers::match_pattern("Number")),
        }
    }
}

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> = At<'a, Token, u8>;

Pour enfin implémenter Recognizable sur Token !!

impl<'a> Recognizable<'a, u8, TokenOutput<'a>> for Token {
    fn recognize(self, tokenizer: &mut Tokenizer<'a>) -> parser::Result<Option<TokenOutput<'a>>> {
        // l'appel à matcher() est possible car Token implémente le trait Match
        // l'appel à recognize est possible car Tokenizer possède cette méthode (pas le Scanner)
        let (result, size) = tokenizer.recognize(self.matcher())?;
        if !result {
            return Ok(None);
        }
        let pos = tokenizer.cursor();
        // mais Tokenizer est un scanner et donc possède toutes les méthodes
        // du Scanner
        if !tokenizer.remaining().is_empty() {
            // comme faire avancer le curseur du nombre de bytes consommer par le Token
            tokenizer.bump_by(size);
        }
        // Finalement on renvoie le At
        Ok(Some(At::new(pos, pos + size, self, tokenizer.data())))
    }
}

Et on utilise cela ainsi

#[test]
fn test_recognize_token() {
    let data = b"create table user (id number, name text);";
    let mut tokenizer = Tokenizer::new(data);
    assert!(Token::Create
        .recognize(&mut tokenizer)
        .expect("Unable to recognize CREATE token")
        .is_some());

    let data = b"creata table user (id number, name text);";
    let mut tokenizer = Tokenizer::new(data);
    assert!(Token::Create
        .recognize(&mut tokenizer)
        .expect("Unable to recognize CREATE token")
        .is_none());
}

On peut finalement se faire une petite fonction utilitaire.

pub fn recognize<'a, U, R: Recognizable<'a, u8, U>>(
    element: R,
    scanner: &mut Tokenizer<'a>,
) -> Result<U> {
    element
        .recognize(scanner)?
        .ok_or(ParseError::UnexpectedToken)
}

Qui s’utilise ainsi

#[test]
fn test_recognize() {
    let data = b"create table user (id number, name text);";
    let mut tokenizer = Tokenizer::new(data);
    assert!(recognize(Token::Create, &mut tokenizer).is_ok());
    assert!(recognize(Token::Whitespace, &mut tokenizer).is_ok());
    assert!(recognize(Token::Table, &mut tokenizer).is_ok());
}

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

impl<'a, T> Scanner<'a, T> {
    pub fn visit<U: Visitable<'a, T>>(&mut self) -> parser::Result<U> {
        U::accept(self)
    }
}

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.

pub struct Whitespaces;

Pas besoin de champ dans cette structure, ce n’est qu’une accroche pour y appliquer le Visitor.

impl<'a> Visitable<'a, u8> for Whitespaces {
    fn accept(scanner: &mut Scanner<'a, u8>) -> parser::Result<Self> {
        let mut counter = 0;
        while Token::Whitespace.recognize(scanner)?.is_some() {
            counter += 1;
        }
        if counter == 0 {
            return Err(ParseError::UnexpectedToken);
        }
        Ok(Whitespaces)
    }
}

On peut alors consommer nos espaces blancs depuis le Tokenizer qui est un Scanner et donc qui possède la méthode “visit”.

#[test]
fn test_whitespaces() {
    let data = b"    data";
    let mut tokenizer = Tokenizer::new(data);
    tokenizer
        .visit::<Whitespaces>()
        .expect("failed to parse whitespaces");
    assert_eq!(tokenizer.remaining(), b"data");
}

#[test]
fn test_whitespaces_fail() {
    let data = b"data";
    let mut tokenizer = Tokenizer::new(data);
    assert!(tokenizer.visit::<Whitespaces>().is_err());
}

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].

pub struct CreateTablePrefix;

impl<'a> Visitable<'a, u8> for CreateTablePrefix {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        recognize(Token::Create, scanner)?;
        scanner.visit::<Whitespaces>()?;
        recognize(Token::Table, scanner)?;
        Ok(CreateTablePrefix)
    }
}


#[test]
fn test_create_table_prefix() {
    let input = b"CREATE   TABLE  User";
    let mut scanner = Scanner::new(input);
    assert!(CreateTablePrefix::accept(&mut scanner).is_ok());
    assert_eq!(scanner.remaining(), b"  User");
}

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.

pub struct Table(String);

impl<'a> Visitable<'a, u8> for Table {
    fn accept(scanner: &mut Scanner<'a, u8>) -> parser::Result<Self> {
        let tokens = recognize(Token::Literal(Literal::String), scanner)?;
        let data = String::from_utf8_lossy(&tokens.source[tokens.start..tokens.end]);
        Ok(Table(data.into()))
    }
}

// petit utilitaire pour récupérer le contenu
impl From<Table> for String {
    fn from(table: Table) -> String {
        table.0
    }
}

Et alors on peut même esquisser le travail du [prochain article](/rustqlite-6 de la série. En capturant le nom de la table à créer.

struct CreateTableCommand {
    table_name: String,
}

impl<'a> Visitable<'a, u8> for CreateTableCommand {
    fn accept(scanner: &mut Scanner<'a, u8>) -> parser::Result<Self> {
        // on visite les tokens CREATE TABLE
        scanner.visit::<CreateTablePrefix>()?;
        // suivi d'autant d'espace blancs que l'on veut, mais au moins un
        scanner.visit::<Whitespaces>()?;
        // finalement on récupère le literal string qui représente le nom de la table
        let table_name = scanner.visit::<Table>()?.into();
        // et on retourne la commande
        Ok(CreateTableCommand { table_name })
    }
}

#[test]
fn test_parse_create_table_command() {
    let data = b"create table   users   (   id   number,   name   text(50) )";
    let mut scanner = Scanner::new(data);
    let result = CreateTableCommand::accept(&mut scanner).expect("failed to parse");
    assert_eq!(
        result,
        CreateTableCommand {
            table_name: "users".to_string()
        }
    );
}

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.

trait Forecast<'a, T, S> {
    fn forecast(&self, data: &mut Scanner<'a, T>) -> parser::Result<ForecastResult<S>>;
}

Et une enumeration pour représenter le résultat de ce comportement.

enum ForecastResult<S> {
    /// Le groupe a été trouvé
    Found {
        /// token de début de groupe 
        start: S, 
        /// token de fin de groupe
        end: S 
        /// position de la fin du groupe relativement
        /// à la position du curseur
        end_slice: usize, 
    },
    /// Le groupe n'est pas trouvable depuis la position actuelle du scanner
    NotFound,
}

On peut alors en faire une fonction utilitaire qui permet de matcher tout ce qui est capable d’implémenter Forecast.

pub fn forecast<'a, U, F: Forecast<'a, u8, U>>(
    element: F,
    tokenizer: &mut Tokenizer<'a>,
) -> parser::Result<Forecasting<'a, u8, U>> {
    let source_cursor = tokenizer.cursor();
    if let ForecastResult::Found {
        start,
        end,
        end_slice,
    } = element.forecast(tokenizer)?
    {
        let data = &tokenizer.data()[source_cursor..source_cursor + end_slice];
        return Ok(Forecasting { start, end, data });
    }
    Err(ParseError::UnexpectedToken)
}

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.

fn match_for_balanced_group(
    tokenizer: &mut Tokenizer,
    balance: &mut usize,
    start: Token,
    end: Token,
) -> parser::Result<()> {
    // try to recognize start group token
    match start.recognize(tokenizer)? {
        // if not start token try to recognize end group token
        None => match end.recognize(tokenizer)? {
            // if end group token decrement balancing counter
            Some(_end_token) => *balance -= 1,
            // if neither, move by one byte
            None => {
                tokenizer.bump_by(1);
                return Ok(());
            }
        },
        // if start group token increment balancing counter
        Some(_start_token) => *balance += 1,
    };

    Ok(())
}

pub fn match_group<'a>(
    start: Token,
    end: Token,
) -> impl Fn(&[u8]) -> parser::Result<ForecastResult<Token>> + 'a {
    move |input| {
        // 0 if number of start token equals number of end token
        // i.e: ( 5 + 3 - ( 10 * 8 ) ) => 2 "(" and 2 ")" => balanced
        //      ( 5 + 3 - ( 10 * 8 )   => 2 "(" and 1 ")" => unbalanced
        let mut balance = 0;

        let mut tokenizer = Tokenizer::new(input);

        loop {
            match_for_balanced_group(&mut tokenizer, &mut balance, start, end)?;
            // if balancing is 0 then either there is no group at all or is balanced
            if balance == 0 {
                break;
            }
        }

        // not enough bytes to create a group
        if tokenizer.cursor() == 1 {
            return Ok(ForecastResult::NotFound);
        }

        Ok(ForecastResult::Found {
            end_slice: tokenizer.cursor(),
            start,
            end,
        })
    }
}

On peut alors matcher les groupes qui nous intéressent.

#[test]
fn test_match_group() {
    let data = b"( 5 + 3 - ( 10 * 8 ) ) + 54";
    let result =
        match_group(Token::OpenParen, Token::CloseParen)(data).expect("failed to parse");
    assert_eq!(
        result,
        ForecastResult::Found {
            end_slice: 22,
            start: Token::OpenParen,
            end: Token::CloseParen
        }
    );
    assert_eq!(&data[..22], b"( 5 + 3 - ( 10 * 8 ) )");
}

On se créé alors un objet GroupKind pour lui accrocher le comportement Forecast.

pub enum GroupKind {
    Parenthesis,
}

impl GroupKind {
    fn matcher<'a>(&self) -> Box<impl Fn(&'a [u8]) -> parser::Result<ForecastResult<Token>>> {
        match self {
            GroupKind::Parenthesis => Box::new(match_group(Token::OpenParen, Token::CloseParen)),
        }
    }
}

impl<'a> Forecast<'a, u8, Token> for GroupKind {
    fn forecast(&self, data: &mut Tokenizer<'a>) -> parser::Result<ForecastResult<Token>> {
        self.matcher()(data.remaining())
    }
}

Et alors cela nous ouvre le droit d’utiliser notre méthode forecast

#[test]
fn test_match_group_delimited() {
    let data = b"( 5 + 3 - ( 10 * 8 ) ) + 54";
    let mut tokenizer = Tokenizer::new(data);
    let result = forecast(GroupKind::Parenthesis, &mut tokenizer).expect("failed to parse");
    assert_eq!(
        result,
        Forecasting {
            start: Token::OpenParen,
            end: Token::CloseParen,
            data: &data[0..22],
        }
    );
    assert_eq!(&data[..22], b"( 5 + 3 - ( 10 * 8 ) )");
}

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:

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
struct SeparatedList<T, S> {
    data: Vec<T>,
    separator: PhantomData<S>,
}

On défini

enum YieldResult<V> {
    /// on a visité et il est possible 
    /// qu'un autre élément soit visitable
    /// cas: 1,2,3,
    MaybeNext(V),
    /// la dernière visite indique qu'il n'y a
    /// plus rien à visiter
    /// cas: 1,2,3
    Last(V),
}
fn yield_element<'a, V, S>(scanner: &mut Scanner<'a, u8>) -> parser::Result<YieldResult<V>>
where
    V: Visitable<'a, u8> + Debug,
    S: Visitable<'a, u8> + Debug,
{
    // visite de l'élement (il est assuré d'en avoir au moins un, sinon c'est une erreur)
    let element: V = scanner.visit()?;

    // s'il n'y a plus rien à parser c'est le dernier élément
    if scanner.remaining().is_empty() {
        return Ok(YieldResult::Last(element));
    }

    // on consomme le séparateur si ce n'est pas encore la fin
    scanner.visit::<S>()?;

    // on retourne l'élément visité
    Ok(YieldResult::MaybeNext(element))
}

On peut alors accrocher le Visitable dessus

impl<'a, T, S> Visitable<'a, u8> for SeparatedList<T, S>
where
    T: Visitable<'a, u8>,
    S: Visitable<'a, u8>,
{
    fn accept(scanner: &mut Tokenizer<'a>) -> parser::Result<Self> {
        let mut elements = vec![];
        // on enregistre la position du curseur
        let cursor = scanner.cursor();

        loop {
            if let Ok(result) = yield_element::<T, S>(scanner) {
                let element: YieldResult<T> = result;

                match element {
                    YieldResult::Last(element) => {
                        elements.push(element);
                        break;
                    }
                    YieldResult::MaybeNext(element) => {
                        elements.push(element);
                    }
                }
            } else {
                // on rétabli le curseur
                scanner.jump(cursor);
                break;
            }
        }

        Ok(SeparatedList {
            data: elements,
            separator: PhantomData,
        })
    }
}

Pour tester je vais créer deux Visitable artificiels.

pub struct SeparatorComma;

impl<'a> Visitable<'a, u8> for SeparatorComma {
    fn accept(scanner: &mut Tokenizer<'a>) -> parser::Result<Self> {
        recognize(Token::Comma, scanner)?;
        Ok(SeparatorComma)
    }
}

pub struct Number(i64);

impl<'a> Visitable<'a, u8> for Number {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        let data = recognize(Token::Literal(Literal::Number), scanner)?;
        let value = String::from_utf8_lossy(&data.source[data.start..data.end]).parse().unwrap();
        Ok(Number(value))
    }
}

Et on peut alors extraire ce que l’on veut.

#[test]
fn test_parse_number_list() {
    let data = b"12,4,78,22";
    let mut tokenizer = super::Tokenizer::new(data);
    let result = tokenizer
        .visit::<SeparatedList<Number, SeparatorComma>>()
        .expect("failed to parse");
    assert_eq!(
        result.data,
        vec![Number(12), Number(4), Number(78), Number(22)]
    );
    assert_eq!(tokenizer.cursor(), 10);
}

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

pub struct SelectCommand;

impl<'a> Visitable<'a, u8> for SelectCommand {
    fn accept(scanner: &mut Tokenizer<'a>) -> parser::Result<Self> {
        recognize(Token::Select, scanner)?;
        scanner.visit::<Whitespaces>()?;
        recognize(Token::Star, scanner)?;
        scanner.visit::<Whitespaces>()?;
        recognize(Token::From, scanner)?;

        Ok(SelectCommand)
    }
}

L’Acceptor permet de chaîner nos opération de visites

pub struct Acceptor<'a, 'b, T, V> {
    data: Option<V>,
    scanner: &'b mut Scanner<'a, T>,
}

impl<'a, 'b, T, V> Acceptor<'a, 'b, T, V> {
    pub fn new(scanner: &'b mut Scanner<'a, T>) -> Self {
        Self {
            data: None,
            scanner,
        }
    }
}

Il prend une fonction appelé un transformer qui permet de transformer le contenu de la variante en une variante d’énumération.

impl<'a, 'b, T, V> Acceptor<'a, 'b, T, V> {
    pub fn try_or<U: Visitable<'a, T>, F>(mut self, transformer: F) -> parser::Result<Self>
    where
        F: Fn(U) -> parser::Result<V>,
    {
        // Propagate result
        if self.data.is_some() {
            return Ok(self);
        }

        // Or apply current recognizer
        if let Ok(found) = U::accept(self.scanner) {
            self.data = Some(transformer(found)?);
        }

        Ok(self)
    }

    pub fn finish(self) -> Option<V> {
        self.data
    }
}

Et alors, on a un système très versatile.

enum Command {
    CreateTable(CreateTableCommand),
    Select(SelectCommand),
}

impl<'a> Visitable<'a, u8> for Command {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        Acceptor::new(scanner)
            // le système de type de Rust vient fixer le type de Visteur en se
            // basant sur le type de la variante
            .try_or(|command| Ok(Command::Select(command)))?
            .try_or(|command| Ok(Command::CreateTable(command)))?
            .finish()
            .ok_or(ParseError::UnexpectedToken)
    }
}

#[test]
fn test_parse_select() {
    let data = b"SELECT * FROM Users";
    let mut tokenizer = Tokenizer::new(data);
    let command = tokenizer.visit::<Command>().expect("failed to parse");
    assert_eq!(command, Command::Select(SelectCommand));
}

#[test]
fn test_parse_create_table() {
    let data = b"CREATE TABLE Users";
    let mut tokenizer = Tokenizer::new(data);
    let command = tokenizer.visit::<Command>().expect("failed to parse");
    assert_eq!(
        command,
        Command::CreateTable(CreateTableCommand {
            table_name: "Users".to_string(),
        })
    );
}

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à.