Introduction

Un parseur de fichiers .torrent

Peut-être avez-vous déjà eu la curiosité de regarder le contenu d’un fichier .torrent. Un fichier de ce type est utilisé pour renseigner un client sur la manière de récupérer un ensemble de fichiers en utilisant le protocole BitTorrent. Si vous avez eu cette curiosité, vous avez eu une mauvaise surprise: le contenu d’un fichier .torrent est cryptique. Si votre éditeur de texte a cru y voir de l’UTF-8 ou de l’UTF-16, il aura affiché à l’écran quelques mots lisibles noyés dans une soupe de symboles incompréhensibles. C’est parce que les fichiers .torrent sont encodés en Bencode, et que ce format d’encodage, bien que profondément basé sur des chaînes de caractères, supporte du contenu binaire non destiné à être directement lu par un humain.

Un fichier de ce type doit donc être décodé par un programme, ce qui implique le besoin de créer un parseur. C’est en général à ce moment qu’on jette l’éponge, en se remémorant le peu qu’il reste des cours de compilation: Bison, Flex, Yacc,… Tout cela est peu attrayant dans le développement « moderne », notamment parce qu’il est nécessaire de comprendre, de mettre en place et d’exploiter une chaîne de traitement qui nous permet de passer de la définition du format considéré à quelque chose d’utilisable au sein de votre langage de programmation préféré.

Dans cet article, je vous proposer de créer un parseur pour le format Bencode en 50 lignes de code Scala. Il s’agit d’un prétexte pour parler un peu des Parser Combinators, une des forces de ce langage.

Format Bencode

Dans le cas de Bencode, il n’y a que quatre concepts mis en œuvre, ce qui facilite son utilisation:

• Un entier, représenté sous la forme i<entier>e, où <entier> est l’entier (éventuellement signé), représenté sous forme de caractères (alpha)numériques. Les caractères litéraux i et e servent de marqueurs de début et de fin de représentation de l’entier, respectivement.
• Une chaîne d’octets, représenté sous la forme <n>:<chaine>, où <n> est un entier (positif) correspondant au nombre d’octets dans la chaîne, et <chaine> est la représentation octet par octet de la chaîne proprement dite. Lorsque cette séquence d’octets représente une chaîne de caractères, celle-ci est typiquement humainement lisible, car l’encodage ISO-8859-1, sur lequel repose Bencode, représente simplement chaque caractère par un octet.
• Une liste d’éléments, représente sous la forme l<éléments>e, où l et e servent de marqueurs de début et de fin de représentation de la liste, respectivement.
• Un dictionnaire, dont les clefs sont des chaînes d’octets (typiquement des chaînes de caractères) et les valeurs sont de type arbitraire. Un dictionnaire est représenté sous la forme d<paires>e, où d et e servent de marqueurs de début et de fin de représentation du dictionnaire, respectivement, et où <paires> est une séquence de paires de clef-valeur.

Voilà là tout le format Bencode. Il s’agit donc d’une alternative un peu particulière à des formats plus connus, tels que JSON ou XML. Un fichier BitTorrent est un dictionnaire Bencode dont les éléments sont standardisés. La norme spécifie ainsi sous quelle clef on peut retrouver la taille ou le nom de chaque fichier impliqué dans le torrent, ou encore à quel emplacement de la structure se trouve la liste des trackers auprès desquels un client BitTorrent peut obtenir les autres clients partageant le contenu de ce torrent.

Définition des concepts

Commençons par représenter les concepts de Bencode sous la forme de classes Scala.

sealed trait BeElement

case class BeBytes(value: Array[Byte]) extends BeElement 

object BeBytes {
  def apply(str: String): BeBytes = BeBytes(str.getBytes(StandardCharsets.ISO_8859_1))
}

case class BeDict(values: Map[BeBytes, BeElement]) extends BeElement

case class BeInteger(value: Integer) extends BeElement

case class BeList(components: List[BeElement]) extends BeElement

L’utilisation d’un trait scellée (sealed trait) permet de préciser que tous les sous-types de ce trait sont décrits dans ce bloc de code, le trait ne peut être étendu au-delà de ces définitions. Cela permet d’une part d’optimiser la gestion du polymorphisme, et d’autre part de s’assurer que tous les cas possibles d’implémentation du trait sont considérés, notamment dans le cas d’un pattern matching.

Notez que le trait lui-même n’est techniquement pas intéressant: il n’est pas utilisé pour placer en un seul endroit un aspect commun aux différents sous-types (d’ailleurs, il n’y en a pas). Au lieu de cela, cette hiérarchie de trait et de classes met en œuvre le typage algébrique: la structure des types est intéressante en soi, car elle permet la modélisation des concepts qui nous intéressent ainsi que leurs relations. Il est alors possible de les traiter selon une approche fonctionnelle, pratiquement mathématique.

Notez également l’objet compagnon de la classe BeBytes: cette classe a pour seul attribut la séquence d’octets qui en caractérise les instances. Cependant, en pratique, une telle classe est souvent utilisée pour représenter une chaîne de caractères. En Scala, plutôt que de créer un constructeur pour ce type particulier d’utilisation, on préfère créer un objet – dit compagnon – dont la tâche est de servir d’usine à instances particulières de la classe qui lui est associée.

Définition des parseurs

Créons à présent les parseurs dont nous avons besoin pour ce format de fichier. Il s’agit de composants (de pures fonctions en Scala) capables de reconnaître une certaine structure dans une entrée et d’en extraire des instances des différents types algébriques que nous venons de définir. Il s’agit donc en quelque sorte d’expressions régulières sous stéroïdes. Ces parseurs utilisent une syntaxe qui leur est propre, mais qui essentiellement permet d’exprimer des règles du type « si tu repères telle structure, alors il faut en extraire tel élément ».

Les premières règles sont relativement simples à comprendre. Elles permettent l’extraction des entiers, des listes et des dictionnaires en Bencode.

lazy val integer: Parser[BeInteger] = "i" ~> """-?\d+""".r <~ "e" ^^ { value => BeInteger(value.toInt) }

lazy val list: Parser[BeList] = "l" ~> rep(element) <~ "e" ^^ { values => BeList(values) }

lazy val dictionary: Parser[BeDict] = "d" ~> rep(beBytes ~ element) <~ "e" ^^ { pairs =>
    val entries = pairs.map {
      case key ~ value => key -> value
    }.toMap
    BeDict(entries)
}

La règle relative aux chaînes binaires est un peu plus complexe, car il est nécessaire de capturer sa longueur, puis de récupérer un nombre d’octets qui correspond à cette longueur. Notez que cela n’est pas possible avec une expression relationnelle traditionnelle, car il n’est pas possible, avec un automate fini, de « mémoriser dynamiquement » la première partie de l’expression à détecter et de se servir de cette mémoire pour la seconde partie de l’expression. Pour les parseurs de Scala que nous utilisons, cela est possible, même si le résultat est un peu moins élégant que pour une règle plus simple.

lazy val beBytes: Parser[BeBytes] = """\d+""".r ~ ":" ^^ {
    case lengthStr ~ ":" =>
      val length = lengthStr.toInt
      new Parser[BeBytes] {
        def apply(in: Input): ParseResult[BeBytes] = {
          val source = in.source
          val offset = in.offset

          if (offset + length <= source.length) {
            val bytes = source.subSequence(offset, offset + length).toString.getBytes(StandardCharsets.ISO_8859_1)
            Success(BeBytes(bytes), in.drop(length))
          } else {
            Failure(s"Expected $length bytes, but input is too short.", in)
          }
        }
      }
} flatMap identity

Enfin, une dernière règle nous permet de définir le type element comme étant l’union des types interprétables par notre système. Il s’agit d’une combinaison des parseurs précédemment définis. Nous en profitons pour ajouter une méthode recevant en argument une chaîne de caractères arbitraire servant d’entrée à notre système.

lazy val element: Parser[BeElement] = integer |||  list ||| dictionary ||| beBytes

def parseBencode(input: String): ParseResult[BeElement] = parseAll(element, input)

Les lignes de code de cette section constituent l’entièreté de notre parseur. Chaque parseur est une fonction, et, comme pour toute bonne fonction, leur capacité de composition est à l’origine de la richesse de leur utilisation.

Même en tenant compte des lignes vides, je compte 43 lignes de code. Promesse tenue, donc.

Un visiteur d’objets Bencode

Le résultat du parsing d’une entrée par les parseurs que nous avons créés est un objet de type BeElement. Typiquement, cet objet contiendra des sous-objets. Par exemple, un fichier BitTorrent est un dictionnaire contenant des listes, des chaînes de caractères, etc. En tant que développeur, vous avez la liberté de naviguer dans ces objets comme vous le souhaitez, par exemple pour implémenter un client BitTorrent. Contentons-nous d’implémenter un visiteur qui affiche le contenu d’un fichier BitTorrent sous la forme d’une hiérarchie textuelle. L’utilisation de types algébriques, et le système de pattern matching de Scala, nous facilitent grandement les choses.

def visit(element: BeElement, level: Int): String = element match {
    case BeBytes(value) =>
      if(value.forall(b => b >= 0 && b <= 127)) value.map(_.toChar).mkString
      else "<BINARY>"
    case BeDict(values) => values.map(entry => entry match {
      case (key, value) => "\n" + ("\t" * level) + s"${key.value.map(_.toChar).mkString} : " + visit(value, level + 1)
    }).mkString("")
    case BeInteger(value) => value.toString
    case BeList(components) => components.map(visit(_, level)).mkString("[", " , ", "]")
}

C’est, une fois de plus, surtout le type BeBytes qui nous embête: on souhaite ne pas véritablement afficher son contenu si celui-ci n’est pas exclusivement constitué de caractères ASCII, mais plutôt afficher <BINARY> à la place.

Appliquons notre visiteur à un torrent de la distribution Debian:

val url = "https://cdimage.debian.org/debian-cd/current/amd64/bt-cd/debian-12.8.0-amd64-netinst.iso.torrent"
val content = Source.fromURL(new URI(url).toURL, "ISO-8859-1").mkString

BeParser.parseBencode(content) match {
   case Success(result, _) => println(BeElementVisitor.visit(result, 0))
   case Failure(msg, _) => msg
}

Ce qui donne le résultat suivant:

url-list : [https://cdimage.debian.org/cdimage/release/12.8.0/amd64/iso-cd/debian-12.8.0-amd64-netinst.iso , https://cdimage.debian.org/cdimage/archive/12.8.0/amd64/iso-cd/debian-12.8.0-amd64-netinst.iso]
created by : mktorrent 1.1
creation date : 1731156219
announce : http://bttracker.debian.org:6969/announce
info : 
	length : 661651456
	name : debian-12.8.0-amd64-netinst.iso
	piece length : 262144
	pieces : <BINARY>
comment : "Debian CD from cdimage.debian.org"

Conclusion

En utilisant Bencode comme cas d’utilisation, nous avons conçu un parseur en Scala qui utilise les Parser Combinator. En moins de 50 lignes de code, nous avons créé les classes nécessaires à la représentation des concepts de ce format de fichier et avons implémenté les règles permettant d’extraire des instances de ces concepts d’un flux d’entrée.

La concision du parseur vient du langage de programmation choisi, mais surtout de la facilité avec laquelle les règles peuvent se combiner afin d’en créer de nouvelles plus complexes.

Le résultat produit par ce parseur est un ensemble de classes Scala dont le typage et le contenu constituent une représentation de l’élément parsé. Nous avons créé un visiteur qui, en quelques lignes, donne une représentation textuelle humainement compréhensible du contenu d’un fichier BitTorrent.