Table des matières

• Grammaire
• Ajout des tokens
• Parsing de l’expression
  • Recognizer
  • Binary Operator
  • ColumnExpression
  • Opérateur logique
  • Expression
  • LogicalExpression
• Test de parse
  • Expression simple
  • Expression logique
  • Expression logiques composites
• Conclusion

Bonjour à toutes et tous 😃

L’introduction du concept de clef primaire permet de récupérer une entrée dans la base de données sans devoir scanner tous les éléments un par un jusqu’à trouver le bon.

C’est pas mal du tout, mais un peu limité.

Généralement les requêtes sont un peu plus complexes et utiles.

Si l’on reprend la métaphore de notre annuaire téléphonique, c’est comme si pour trouver quelqu’un, vous n’avez que deux choix: soit vous chercher dans toutes les pages à la recherche du bon nom soit vous connaissez déjà le numéro de page et c’est nettement plus simple. Ça c’est le fonctionnement de l’index primaire et du full-scan.

Maintenant, imaginons que l’on veuille récupérer les numéros de tous les hommes habitant dans la ville “X”.

Dans la vraie vie, pour ceux qui n’ont jamais vu un, si si ça doit exister maintenant 😅. Les entrées sont décomposé en section pour chaque ville et trié par ordre alphabétique.

Nous pouvons modéliser notre annuaire au travers d’une table PhoneBook.

CREATE TABLE PhoneBook(name TEXT(50) PRIMARY KEY, city TEXT(50), phone_number TEXT(50), gender TEXT(1));

Notre requête dans l’annuaire ne peut pas être par clef primaire.

Il faut connaître les noms des personnes pour les trouver.

SELECT * FROM PhoneBook WHERE name='Alexandre Adams'
SELECT * FROM PhoneBook WHERE name='Amandine Agostini'
SELECT * FROM PhoneBook WHERE name='Arthur Almeida'
SELECT * FROM PhoneBook WHERE name='Anaïs Aubert'
...

Ce n’est pas très pratique… 😑

La vraie requête que l’on veut c’est:

SELECT * FROM PhoneBook WHERE city = 'X' AND gender = 'H';

Cette partie de la requête, nous allons l’appeler “expression”.

city = 'X' AND gender = 'H'

Je vous propose de mettre en place le parse de cette expression dans cette nouvelle partie de notre épopée.

Grammaire

Avant de partir en bataille avec notre parser, nous allons en définir les contours.

Expression logique

Expression ::= ColumnExpression | Expression LogicalOperator Expression
ColumnExpression ::= Column BinaryOperator LiteralValue
LogicalOperator ::= 'AND' | 'OR'
BinaryOperator ::= '=' | '!=' | '>' | '>=' | '<' | '<='
Column ::= [A-Za-z_]+
LiteralValue ::= LiteralString | LiteralInteger
LiteralString ::=  "'" [^']+ "'"
LiteralInteger ::= [0-9]+

Expression:

ColumnExpression:

LogicalOperator:

BinaryOperator:

Column:

LiteralValue:

LiteralString:

LiteralInteger:

Notre grammaire se complexifie. Nous avons tout une série de nouveaux tokens à rajouter.

• AND
• OR
• !=
• =
• >
• <
• >=
• <=

Nous avons introduit également le concept d’expression de colonne ColumnExpression.

On associe un identifiant de colonne et une valeur comparé par un opérateur binaire BinaryOperator.

id > 12
name != 'Max'

Mais nous avons également la possibilité de d’associer deux ColumnExpression via un LogicalOperator.

Et on peut le faire autant que l’on veut.

id > 12 AND name != 'Max' OR data = 'true'

Ajout des tokens

On rajoute nos différents tokens

enum Operator {
    /// AND token
    And,
    /// OR token
    Or,
    /// > token
    GreaterThan,
    /// < token
    LessThan,
    /// >= token
    GreaterThanOrEqual,
    /// <= token
    LessThanOrEqual,
    /// != token
    Different,
    /// = token
    Equal,
}


enum Token {
    // ...
    Operator(Operator),
    // ...
}

On y associe un Matcher

impl Match for Operator {
    fn matcher(&self) -> Matcher {
        match self {
            Operator::And => Box::new(matchers::match_pattern("and")),
            Operator::Or => Box::new(matchers::match_pattern("or")),
            Operator::GreaterThan => Box::new(matchers::match_pattern(">")),
            Operator::LessThan => Box::new(matchers::match_pattern("<")),
            Operator::GreaterThanOrEqual => Box::new(matchers::match_pattern(">=")),
            Operator::LessThanOrEqual => Box::new(matchers::match_pattern("<=")),
            Operator::Different => Box::new(matchers::match_pattern("!=")),
            Operator::Equal => Box::new(matchers::match_pattern("=")),
        }
    }
}

impl Match for Token {
    fn matcher(&self) -> Matcher {
        match self {
            // ...
            Token::Operator(operator) => operator.matcher(),
            // ...
        }
    }
}

Ainsi que la taille des tokens

impl Size for Operator {
    fn size(&self) -> usize {
        match self {
            Operator::And => 3,
            Operator::Or => 2,
            Operator::GreaterThan => 1,
            Operator::LessThan => 1,
            Operator::GreaterThanOrEqual => 2,
            Operator::LessThanOrEqual => 2,
            Operator::Different => 2,
            Operator::Equal => 1,
        }
    }
}


impl Size for Token {
    fn size(&self) -> usize {
        match self {
            // ...
            Token::Operator(operator) => operator.size(),
            // ...
        }
    }
}

Parsing de l’expression

Comme la grammaire le laisse supposer, parser une Expression est plus complexe que parser les embryon de commandes que nous avons déjà dans notre arsenal.

La principal difficulté étant qu’une Expression est récursivement une Expression.

Mais avant de nous attaquer au plat de resistance et de l’avoir sur l’estomac par indigestion. Nous allons décomposer le problèmes en sous-problèmes et recomposer le puzzle.

Recognizer

On avait déjà un Acceptor qui permettait d’avoir des alternatives de visiteurs, le Forecaster qui donnait le choix de forecast de groupe de token dans le futur.

Il nous manquait la possiblité de choisir une collection de tokens à reconnaître.

Avec le Recognizer c’est chose faite !

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

    pub fn try_or<R: Recognizable<'a, T, U>>(
        mut self,
        element: R,
    ) -> Result<Recognizer<'a, 'b, T, U>> {
        // Propagate result
        if self.data.is_some() {
            return Ok(self);
        }
        // Or apply current recognizer
        if let Some(found) = element.recognize(self.scanner)? {
            self.data = Some(found);
        }
        Ok(self)
    }

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

Même principe que pour les deux autres, on lui fourni une liste de choses à reconnaître et il tente de reconnaître le token, s’il n’y arrive pas, il passe au suivant, sinon il s’arrête et propage le token reconnu.

En sorti de méthode finish on obtient alors une Option du token.

Binary Operator

La première chose que l’on va vouloir reconnaître c’est nos opérateurs binaires.

• !=
• =
• >
• <
• >=
• <=

Nous avons besoin d’une énumération pour modéliser ces opérateurs

enum BinaryOperator {
    GreaterThanOrEqual,
    LessThanOrEqual,
    GreaterThan,
    LessThan,
    Equal,
    Different,
}

Ainsi que d’un TryFrom qui va permettre de passer du token reconnu à l’opérateur.

impl TryFrom<Token> for BinaryOperator {
    type Error = ParseError;
    fn try_from(value: Token) -> Result<Self, Self::Error> {
        match value {
            Token::Operator(Operator::GreaterThanOrEqual) => Ok(BinaryOperator::GreaterThanOrEqual),
            Token::Operator(Operator::LessThanOrEqual) => Ok(BinaryOperator::LessThanOrEqual),
            Token::Operator(Operator::GreaterThan) => Ok(BinaryOperator::GreaterThan),
            Token::Operator(Operator::LessThan) => Ok(BinaryOperator::LessThan),
            Token::Operator(Operator::Equal) => Ok(BinaryOperator::Equal),
            Token::Operator(Operator::Different) => Ok(BinaryOperator::Different),
            _ => Err(ParseError::UnexpectedToken),
        }
    }
}

On peut alors reconnaître notre opérateur.

#[test]
fn test_binary_operator() {
    let data = b"> 12";
    let mut scanner = Scanner::new(data);
    let result: BinaryOperator = Recognizer::new(&mut scanner)
        // reconnaissance de l'opérateur 👇
        .try_or(Token::Operator(Operator::GreaterThan))
        .expect("Unable to parse")
        .finish()
        .expect("No token recognize")
        .element
        .try_into()
        .expect("Unable to convert");
    assert_eq!(result, BinaryOperator::GreaterThan);
}

ColumnExpression

On peut désormais représenter notre ColumnExpression

struct ColumnExpression {
    column: Column,
    operator: BinaryOperator,
    value: Value,
}

impl ColumnExpression {
    pub fn new(column: Column, operator: BinaryOperator, value: Value) -> Self {
        Self {
            column,
            operator,
            value,
        }
    }
}

Que l’on peut alors visiter.

impl<'a> Visitable<'a, u8> for ColumnExpression {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        // reconnaissance de l'identifiant de colonne
        let column = Column::accept(scanner)?;
        // nettoyage d'eventuel d'espace blanc
        OptionalWhitespaces::accept(scanner)?;

        // reconnaissance de l'opérateur binaire
        let operator = Recognizer::new(scanner)
            .try_or(Token::Operator(Operator::GreaterThanOrEqual))?
            .try_or(Token::Operator(Operator::GreaterThan))?
            .try_or(Token::Operator(Operator::LessThanOrEqual))?
            .try_or(Token::Operator(Operator::LessThan))?
            .try_or(Token::Operator(Operator::Different))?
            .try_or(Token::Operator(Operator::Equal))?
            .finish()
            .ok_or(ParseError::UnexpectedToken)?
            .element
            .try_into()?;

        // nettoyage d'eventuel d'espace blanc
        OptionalWhitespaces::accept(scanner)?;
        // reconnaissance de la valeur
        let value = Value::accept(scanner)?;
        Ok(ColumnExpression::new(column, operator, value))
    }
}

Ce qui donne:

#[test]
fn test_column_expression() {
    let data = b"id = 12";
    let mut scanner = Scanner::new(data);
    let result = scanner.visit();
    assert_eq!(
        result,
        Ok(ColumnExpression {
            column: Column("id".to_string()),
            operator: BinaryOperator::Equal,
            value: Value::Integer(12)
        })
    );
}

Parfait! On peut maintenant parser une ColumnExpression 🤩

Opérateur logique

On fait de même pour les tokens:

• AND
• OR

enum LogicalOperator {
    Or,
    And,
}

impl TryFrom<Token> for LogicalOperator {
    type Error = ParseError;

    fn try_from(value: Token) -> Result<Self, Self::Error> {
        match value {
            Token::Operator(Operator::And) => Ok(LogicalOperator::And),
            Token::Operator(Operator::Or) => Ok(LogicalOperator::Or),
            _ => Err(ParseError::UnexpectedToken),
        }
    }
}

Permettant de reconnaître les opérateur logique.

#[test]
fn test_logical_operator() {
    let data = b"AND toto";
    let mut scanner = Scanner::new(data);
    let result: LogicalOperator = Recognizer::new(&mut scanner)
        .try_or(Token::Operator(Operator::And))
        .expect("Unable to parse")
        .finish()
        .expect("No token recognize")
        .element
        .try_into()
        .expect("Unable to convert");
    assert_eq!(result, LogicalOperator::And);
}

Expression

Notre expression est une suite de ColumnExpression séparé par de LogicalOperator.

Lorsque l’on a une expression du genre:

id > 12 AND name = 'toto'

Cela donne une expression du genre

ColumnExpression LogicalOperator ColumnExpression

Mais si on a quelque chose commen

id > 12 AND name = 'toto' AND gender = 'M'

Cela donne l’expression suivante

ColumnExpression LogicalOperator ColumnExpression LogicalOperator ColumnExpression

Sauf que l’opérateur logique n’a que deux paramètres:

• un à gauche lhs
• un à droite rhs

Si on redécoupe

ColumnExpression LogicalOperator [ ColumnExpression LogicalOperator ColumnExpression ]

On réduit encore

ColumnExpression LogicalOperator LogicalExpression

Et si l’on veut que le système soit totalement récursif, notre expression doit se réduire en

LogicalExpression

On en déduit deux choses.

Nous avons besoin d’une énumération qui permette de faire une union entre la ColumnExpression et la LogicalExpression

enum Expression {
    Logical(LogicalExpression),
    Column(ColumnExpression),
}

On la visite

impl<'a> Visitable<'a, u8> for Expression {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        Acceptor::new(scanner)
            .try_or(|value| Ok(Expression::Logical(value)))?
            .try_or(|value| Ok(Expression::Column(value)))?
            .finish()
            .ok_or(ParseError::UnexpectedToken)
    }
}

LogicalExpression

On peut alors en définir le LogicalExpression

struct LogicalExpression {
    lhs: Box<Expression>,
    operator: LogicalOperator,
    rhs: Box<Expression>,
}

Le boxing Box<Expression> est obligatoire car Expression peut contenir une LogicalExpression qui contient lui même une Expression, etc …

Cela conduit à une taille infinie.

Ça la stack n’aime pas du tout, la heap n’a pas ce problème.

On en défini également un constructeur

impl LogicalExpression {
    fn new(lhs: Expression, operator: LogicalOperator, rhs: Expression) -> Self {
        Self {
            lhs: Box::new(lhs),
            operator,
            rhs: Box::new(rhs),
        }
    }
}

Et finalement un visiteur

impl<'a> Visitable<'a, u8> for LogicalExpression {
    fn accept(scanner: &mut Scanner<'a, u8>) -> crate::parser::Result<Self> {
        // on forecast la fin d'un groupe d'expression car si l'on tente
        // de visiter une Expression sans avoir au préalable délimité
        // le contenu du scanner, nous allons éternellement 
        // parser le même morceau de LogicalExpression
        // ce qui fait exploser la stack !
        // Tout lhs fini nécessairement par AND ou OR
        let lhs_group = Forcaster::new(scanner)
            .try_or(UntilToken(Token::Operator(Operator::And)))?
            .try_or(UntilToken(Token::Operator(Operator::Or)))?
            .finish()
            .ok_or(ParseError::UnexpectedToken)?;

        let mut lhs_scanner = Scanner::new(lhs_group.data);
        // on visite l'Expression du lhs
        let lhs = lhs_scanner.visit()?;
        // on avance le curseur du scanner principal
        scanner.bump_by(lhs_group.data.len());
        
        // on nettoie d'éventuel blancs
        scanner.visit::<OptionalWhitespaces>()?;

        // on reconnait l'opérateur logique
        let operator = Recognizer::new(scanner)
            .try_or(Token::Operator(Operator::And))?
            .try_or(Token::Operator(Operator::Or))?
            .finish()
            .ok_or(ParseError::UnexpectedToken)?
            .element
            .try_into()?;
        // on reconnaît au moins un blanc après l'opérateur logique
        scanner.visit::<Whitespaces>()?;
        // on visite l'expression suivante
        let rhs = scanner.visit()?;
        Ok(LogicalExpression::new(lhs, operator, rhs))
    }
}

Test de parse

On peut finalement parser nos Expressions

Expression simple

D’abord une simple comparaison

#[test]
fn test_logical_expression_simple() {
    let data = b"id > 12";
    let mut scanner = Scanner::new(data);
    let result = scanner.visit();
    assert_eq!(
        result,
        Ok(Expression::Column(ColumnExpression::new(
            Column("id".to_string()),
            BinaryOperator::GreaterThan,
            Value::Integer(12),
        )))
    );
}

Expression logique

Puis une utilisant un connecteur logique

#[test]
fn test_logical_expression_or() {
    let data = b"id <= 12 OR name != 'toto'";
    let mut scanner = Scanner::new(data);
    let result = scanner.visit();

    let c1 = ColumnExpression::new(
        Column("id".to_string()),
        BinaryOperator::LessThanOrEqual,
        Value::Integer(12),
    );

    let c2 = ColumnExpression::new(
        Column("name".to_string()),
        BinaryOperator::Different,
        Value::Text("toto".to_string()),
    );

    let l1 = LogicalExpression::new(
        Expression::Column(c1),
        LogicalOperator::Or,
        Expression::Column(c2),
    );

    assert_eq!(result, Ok(Expression::Logical(l1)))
}

Expression logiques composites

Puis un chaînage de plusieurs expressions

#[test]
fn test_logical_expression_or_and() {
    let data = b"id <= 12 OR name != 'toto' AND gender = 'male'";
    let mut scanner = Scanner::new(data);
    let result = scanner.visit();

    let c1 = ColumnExpression::new(
        Column("id".to_string()),
        BinaryOperator::LessThanOrEqual,
        Value::Integer(12),
    );

    let c2 = ColumnExpression::new(
        Column("name".to_string()),
        BinaryOperator::Different,
        Value::Text("toto".to_string()),
    );

    let c3 = ColumnExpression::new(
        Column("gender".to_string()),
        BinaryOperator::Equal,
        Value::Text("male".to_string()),
    );

    let l1 = LogicalExpression::new(
        Expression::Column(c1),
        LogicalOperator::Or,
        Expression::Column(c2),
    );

    let l2 = LogicalExpression::new(
        Expression::Logical(l1),
        LogicalOperator::And,
        Expression::Column(c3),
    );

    assert_eq!(result, Ok(Expression::Logical(l2)))
}

Et voilà ! 🤩

Nous sommes capables de parser des expressions logiques SQL. 😍😍😍

Pas toutes biensûr, mais c’est un début.

En tout cas ça sera suffisant pour la suite de mes explications.

Conclusion

Oui, c’était encore un épisode de parsing, mais que voulez vous, il faut bien des outils pour bâtir des choses, et le parsing est nécessaire pour nous ouvir le champ des possibles. 😎

Dans la prochaine partie nous utiliserons nos expressions pour requêter notre base données sur autre chose que la clef primaire.

Merci de votre lecture ❤️

Vous pouvez trouver le code la partie ici et le diff là.