Using Active Patterns to decode and encode BEEncoding in F#

In the excellent post Building a BitTorrent client from scratch in C#, Seán O’Flynn implements decoding and encoding of the BEEncoding format — used in torrent files and defined by The BitTorrent Protocol Specification.

Seán’s implementation works on an IEnumerable<byte> in C#. Here I look at another approach: decoding and encoding BEEncoding in F# using Active Patterns operating on byte list. Active Patterns have been available in F# since version 1.9.1 and are a natural fit for parsing work.

Basic building blocks

We start with a basic function that consumes one element from a list if a predicate holds:

let basic e = function
    | c :: cs when e c -> Some(c, cs)
    | _ -> None

let (|Any1|_|)    e = basic ((=) e)
let (|Any1But|_|) e = basic ((<>) e)

Any1 consumes the first element if it equals e; Any1But consumes it if it differs from e.

Because Active Patterns are just functions, we can parameterise one over another to build combinators:

let (|ZeroOrMore|) q inp =
    let rec queryAcc rvs e =
        match q e with
        | Some(v, body) -> queryAcc (v :: rvs) body
        | None          -> (List.rev rvs, e)
    queryAcc [] inp

let (|OneOrMore|) q inp =
    match q inp with
    | Some (v, body) ->
        let xs, t = (|ZeroOrMore|) q body
        v :: xs, t
    | None -> [], inp

ZeroOrMore and OneOrMore take an Active Pattern as parameter and repeatedly apply it, accumulating results. They work exactly like * and + in regular expressions.

The BEEncoding data structure

The spec defines four types:

• String — length-prefixed: 4:spam → "spam"
• Integer — i3e → 3, i-3e → -3
• List — l4:spam4:eggse → ["spam"; "eggs"]
• Dictionary — d3:cow3:mooe → {"cow" → "moo"}, keys must be sorted

open System
open System.Text

type BEBytelist = byte list

type BEEncoding =
    | BENumber of Int64
    | BEString of BEBytelist
    | BEDict   of Map<BEBytelist, BEEncoding>
    | BEList   of BEEncoding list

And some helpers:

let dictStart, dictEnd   = byte 'd', byte 'e'
let listStart, listEnd   = byte 'l', byte 'e'
let numStart,  numEnd    = byte 'i', byte 'e'
let byteArrDivider       = byte ':'

let strToByteList (str : string)    = Encoding.UTF8.GetBytes str |> List.ofArray
let byteListToStr (xs : BEBytelist) = Encoding.UTF8.GetString (xs |> Array.ofList)

let byteListToTyp f byteList =
    let valid, num = Encoding.UTF8.GetString(Array.ofList byteList) |> f
    if not valid then failwithf "failed to parse %s" (byteListToStr byteList)
    num

let byteListToInt64 = byteListToTyp Int64.TryParse
let byteListToInt   = byteListToTyp Int32.TryParse

Parsing integers

BEEncoded integers look like i42e. We consume the i, then all bytes that are not e, then the e:

let (|INT|_|) = function
    | Any1 numStart (_, OneOrMore ((|Any1But|_|) numEnd) (xs, Any1 numEnd (_, t))) ->
        Some(byteListToInt64 xs, t)
    | _ -> None

let (INT i) = [byte 'i'; byte '-'; byte '3'; byte 'e']
// i = -3L

Parsing strings

BEEncoded strings are length-prefixed: 4:spam. We read bytes until :, parse the length, then take that many bytes:

let (|STRING|_|) = function
    | OneOrMore ((|Any1But|_|) byteArrDivider) (cs, Any1 byteArrDivider (_, t)) ->
        Some(List.splitAt (byteListToInt cs) t)
    | _ -> None

let (STRING(s, _)) = [byte '4'; byte ':'; byte 's'; byte 'p'; byte 'a'; byte 'm']
byteListToStr s  // "spam"

Parsing lists and dictionaries

Lists and dicts are recursive — they contain other BEEncoded values. We express this with three mutually recursive Active Patterns:

let rec (|BEENCODING|_|) = function
    | INT(i, t)    -> Some(BENumber i, t)
    | DICT(d, t)   -> Some(BEDict d,   t)
    | LIST(l, t)   -> Some(BEList l,   t)
    | STRING(s, t) -> Some(BEString s, t)
    | _            -> None

and (|LIST|_|) = function
    | Any1 listStart (_, ZeroOrMore (|BEENCODING|_|) (xs, Any1 listEnd (_, t))) ->
        Some(xs, t)
    | _ -> None

and (|DICT|_|) xs =
    let (|PAIRS|_|) = function
        | STRING(key, BEENCODING(value, t)) -> Some((key, value), t)
        | _ -> None
    let validateDict xs =
        let keys, _ = List.unzip xs
        if keys <> List.sort keys then failwith "dictionary keys not sorted"
    match xs with
    | Any1 dictStart (_, ZeroOrMore (|PAIRS|_|) (xs, Any1 dictEnd (_, t))) ->
        validateDict xs
        Some(Map.ofList xs, t)
    | _ -> None

The key insight: ZeroOrMore accepts (|BEENCODING|_|) as its pattern argument, so parsing a list body is just ZeroOrMore (|BEENCODING|_|). The grammar almost writes itself.

Decode and encode

let decode = function
    | BEENCODING(x, []) -> x
    | t -> failwithf "failed to decode: %s" (byteListToStr t)

let encode value =
    let s = StringBuilder()
    let append (str : string) = s.Append str |> ignore
    let rec encode' = function
        | BEString xs  -> append (sprintf "%i:%s" xs.Length (byteListToStr xs))
        | BENumber n   -> append (sprintf "i%ie" n)
        | BEDict m     -> append "d"; encodeMap m; append "e"
        | BEList l     -> append "l"; encodeList l; append "e"
    and encodeMap m =
        Map.toList m
        |> List.sortBy fst
        |> List.iter (fun (k, v) ->
            append (sprintf "%i:%s" k.Length (byteListToStr k))
            encode' v)
    and encodeList l = List.iter encode' l
    encode' value
    s.ToString() |> strToByteList

Round-trip test

let testData =
    "d8:announce33:http://192.168.1.74:6969/announce7:comment17:Comment goes here10:created by25:" +
    "Transmission/2.92 (14714)13:creation datei1460444420e8:encoding5:UTF-84:infod6:lengthi59616e" +
    "4:name9:lorem.txt12:piece lengthi32768e6:pieces40:..." +
    "7:privatei0eee"
    |> strToByteList

testData = (decode testData |> encode)  // true

Decode then re-encode produces the identical byte sequence — our implementation is at least internally consistent.

Takeaways

The ZeroOrMore/OneOrMore combinator pattern works just as well on byte list as on char list. The approach scales naturally: each Active Pattern is independently testable, the recursive structure mirrors the grammar directly, and there are zero external dependencies.

If you want to extend this — say, to validate integer constraints (i-0e is invalid per the spec) — you just add a guard inside the relevant Active Pattern without touching anything else.