Parsing en Rust avec Nom

Objectifs : Découvrir la bibliothèque Nom pour faire du parsing de données en Rust. Thèmes : Développement, Rust, Nom, Parsing, Combinatory Parsing.

Consommer un message binaire

Je me suis remis à développer en Rust ces derniers temps, au travers de deux projets de serveurs. L'un d'eux est un serveur pour un jeu navigateur à base de WebSockets. Est donc arrivée à un moment la question :

Qu'est-ce qu'on a de bien à notre disposition pour parser des messages binaires en Rust ?

L'objectif de ce serveur en Rust étant d'avoir des performances excellentes – d'où la volonté d'avoir un protocole binaire bien conçu –, il fallait trouver un système léger et sans trop de complexité. Extensible et modifiable aussi (les spécifications du protocole changent souvent). Testable unitairement, si possible.

Et j'ai découvert Nom.

Manger de la donnée, la transformer en ensembles cohérents

Un message binaire, c'est une suite finie d'octets. En utilisant le protocole WebSocket, avec le type de message binary, on sait qu'on peut directement recevoir un message binaire. Pour exemple, voici le message Identité conçu pour le serveur (le client se présente au serveur) :

 0         1 2             3->X+3
+---------+---------------+------+
| 0x0 (8) | length X (16) | name |
+---------+---------------+------+

Sur le premier octet, on a l'opcode 0x0. Les deux octets suivants correspondent à la longueur X en octets du nom renseigné. Et enfin, X octets pour le nom en lui même.

Dans l'idéal, on souhaite que notre parser ait le prototype suivant :

fn parse_identity(input: &[u8]) -> Result<String, Error>;

Une méthode parse_identity, qui prend en paramètre une suite finie d'octets &[u8], et qui renvoie : * le nom, en tant que String, si le parsing réussit, * ou une Error descriptive si l'opération échoue.

On peut implémenter cette méthode de façon naïve :

fn parse_identity(input: &[u8]) -> Result<String, Error> {
    /// Consomme le premier octet, et vérifie que la valeur est 0x0. Sinon, renvoie une erreur.
    if let Err(error) = parse_opcode(input[0]) {
        return Err(error);
    }
    /// Puis consomme les deux prochains octets, et stock la longueur. Sinon, renvoie une erreur.
    let length = match parse_length(input[1..3]) {
        Ok(length) => length,
        Err(error) => return Err(error),
    }
    /// Puis consomme "length" octets si disponibles, et renvoie la chaîne. Sinon, renvoie une erreur.
    if 3 + length < input.len() {
        parse_name(input[3..3 + length])
    } else {
        Err(Error::new())
    }
}

fn parse_opcode(input: u8) -> Result<(), Error>;
fn parse_length(input: &[u8]) -> Result<u16, Error>;
fn parse_name(input: &[u8]) -> Result<String, Error>;

En regardant ce code, on peut visualiser un modèle de construction qui se répète : notre fonction parse_identity combine d'autres fonctions parse_x, chacune consommant petit à petit des données, et renvoyant soit une donnée construite, soit une erreur.

Ce modèle est la base d'une technique de parsing qui s'appelle le Combinatory Parsing.

Implémenter le parser avec Nom

Maintenant qu'on a une idée du fonctionnement global, on va pouvoir s'intéresser à une implémentation concrète en utilisant la bibliothèque Nom, ici en version 5.1.2.

Nom va fournir un ensemble complet de fonctions utilitaires, combinables, pour définir notre propre parser. La plus grosse difficulté consiste à connaître les parsers disponibles et savoir quand les utiliser.

On va commencer par recréer le prototype de notre fonction parse_identity, en utilisant Nom :

use nom::IResult;

fn parse_identity(input: &[u8]) -> IResult<&[u8], String>;

IResult est un type définissant le résultat d'un parser Nom. Il a 3 paramètres : l'input restant (ici &[u8]), l'output généré (ici String), et optionnellement l'erreur lancée (ici implicitement (&[u8], nom::error::ErrorKind)).

Puis, on va implémenter une première partie, la récupération de l'opcode :

use nom::{Err, IResult};
use nom::bytes::complete::tag;
use nom::error::ErrorKind;

fn parse_identity(input: &[u8]) -> IResult<&[u8], String> {
    /// On crée un parser qui reprend le parser "tag" fourni par Nom.
    let parse_opcode = tag([0]);

    /// On exécute le parser, et on récupère l'input restant.
    let (input, _) = parse_opcode(input)?;

    /// On renvoie l'input restant et une erreur.
    Err(Err::Error((input, ErrorKind::Tag)))    
}

Le principe du parser tag est d'essayer de consommer la suite d'octets donnée, ou de renvoyer une erreur.

Ensuite, on veut implémenter notre parse_length et notre parse_name :

use nom::{Err, IResult};
use nom::bytes::complete::{tag, take};
use nom::combinator::flat_map;
use nom::error::ErrorKind;
use nom::number::complete::be_u16;

fn parse_identity(input: &[u8]) -> IResult<&[u8], String> {
    let parse_opcode = tag([0]);
    let parse_name = flat_map(be_u16, take);

    let (input, _) = parse_opcode(input)?;
    let (input, name): (_, &[u8]) = parse_name(input)?;

    match String::from_utf8(name.to_vec()) {
        Ok(name) => Ok((input, name)),
        Err(_) => Err(Err::Error((input, ErrorKind::Tag)))
    }
}

On utilise ici une combinaison de be_u16 pour récupérer la longueur sur deux octets en Big Endian, de take pour récupérer une quantité précise d'octets, et de flat_map pour automatiquement passer le résultat du premier parser en paramètre du second. On essaye de convertir le contenu de name en chaîne de caractère UTF-8 (ça peut échouer si la séquence d'octets n'est pas une séquence UTF-8 valide), et la fonction est désormais correctement implémentée !

Cela dit, on va faire encore une petite révision. Actuellement, le parser utilise un style séquentiel. On appelle manuellement d'abord parse_opcode, puis si ça ne renvoie pas d'erreur, on jette le résultat et on appelle parse_name. Il y a une fonction Nom pour ça :

use nom::{Err, IResult};
use nom::bytes::complete::{tag, take};
use nom::combinator::flat_map;
use nom::error::ErrorKind;
use nom::number::complete::be_u16;
use nom::sequence::preceded;

fn parse_identity(input: &[u8]) -> IResult<&[u8], String> {
    let parse_opcode = tag([0]);
    let parse_name = flat_map(be_u16, take);
    let parse_identity = preceded(parse_opcode, parse_name);

    let (input, name) = parse_identity(input)?;

    match String::from_utf8(name.to_vec()) {
        Ok(name) => Ok((input, name)),
        Err(_) => Err(Err::Error((input, ErrorKind::Tag)))
    }
}

Le parser preceded prend en paramètre deux parsers, qu'il appliquera séquenciellement, et ne renverra que le résultat du second. On se retrouve maintenant avec une seule méga-combinaison pour notre parser (on a juste la conversion en chaîne de caractère UTF-8 qui est une étape séparée).

Installer Nom

Pour installer Nom dans un projet rust, il suffit d'ajouter la dépendance nom = "5.1.2" (version actuelle) au fichier cargo.toml.

Un dernier point : Nom est totalement compatible avec des tests unitaires Rust. On peut ajouter au fichier créé auparavant un module test derrière un flag de compilation #[cfg(test)] (qui excluera des binaires compilés ce module), contenant directement le test unitaire. Ce qui donne un fichier final avec :

use nom::{Err, IResult};
use nom::bytes::complete::{tag, take};
use nom::combinator::flat_map;
use nom::error::ErrorKind;
use nom::number::complete::be_u16;
use nom::sequence::preceded;

fn parse_identity(input: &[u8]) -> IResult<&[u8], String> {
    let parse_opcode = tag([0]);
    let parse_name = flat_map(be_u16, take);
    let parse_identity = preceded(parse_opcode, parse_name);

    let (input, name) = parse_identity(input)?;

    match String::from_utf8(name.to_vec()) {
        Ok(name) => Ok((input, name)),
        Err(_) => Err(Err::Error((input, ErrorKind::Tag)))
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn test_parse_identity() {
        let data = vec![0, 0, 2, 49, 49];
        assert_eq!(
            parse_identity(&data),
            Ok((
                &data[5..5],
                String::from("11")
            ))
        )
    }
}

Comme tous les tests en Rust, ils sont exécutables en utilisant la commande cargo test. C'est vivement recommandé d'associer des tests à chacun des parsers conçus : c'est rapide à relancer et pratique pour du TDD.

Liens