Pattern matching when decode Bencode. Problems with pattern name and nested pattern

Question

I am writing a Mathematica function to import *.torrent files as Expression. The encoding used in *.torrent files are called Bencode. You can get more information on Wikipedia.

Here are some examples:

Bencode	Expression
"i-42e"	-42
"3:abc"	"abc"
"l4:hashi99ee"	{"hash", 99}
"d6:lengthi1737643423ee"	<|"length" -> 1737643423|>

I have previously written a Visual Basic script to do this, and it works well. However, it processes characters one by one, and there are many If ... Else ... to determine whether the currently processed character is in a list or in an association, and whether it is a key or a value.

I believe pattern matching functions can do the same thing in a more succinct and elegant way. Integer cases and string cases are easy to be matched, but when it comes to list cases and association cases, weird things happen.

In[1]:= integerPattern = 
  PatternSequence[105, sign : 45 | PatternSequence[], digits__, 101] /;
    And @@ Map[48 <= # <= 57 &, List[digits]];
byteList = {ToCharacterCode["i0e"], ToCharacterCode["i99e"], 
   ToCharacterCode["i-42e"]};
MatchQ[#, {integerPattern}] & /@ byteList

Out[3]= {True, True, True}

In[4]:= 
stringPattern = 
  PatternSequence[digits__, 58, letters__] /; 
   And @@ Map[48 <= # <= 57 &, List[digits]] && 
    Length[List[letters]] == 
     ToExpression[FromCharacterCode[List[digits]]];
byteList = {ToCharacterCode["1:a"], ToCharacterCode["4:hash"], 
   ToCharacterCode["13:a1b2c3d4e5f6g"]};
MatchQ[#, {stringPattern}] & /@ byteList

Out[6]= {True, True, True}

In[7]:= 
listPattern = 
  PatternSequence[108, (integerPattern | stringPattern) ..., 101];
byteList = {ToCharacterCode["le"], ToCharacterCode["li1ee"], 
   ToCharacterCode["li1ei2ee"], ToCharacterCode["li1e1:ae"], 
   ToCharacterCode["l1:ai1ee"], ToCharacterCode["li1e3:abce"], 
   ToCharacterCode["l3:abci1ee"], ToCharacterCode["l1:a3:abce"]};
MatchQ[#, {listPattern}] & /@ byteList

Out[9]= {True, True, False, True, True, False, False, False}

After some research, I found that it involves pattern name: If the pattern contains named parts, then each instance of these parts must be identical.

Question 1

integerPattern can be rewritten as follows so that it does not contain name. How should stringPattern be rewritten?

integerPattern = 
 PatternSequence[105, 45 | PatternSequence[], 
  Alternatives @@ Range[48, 57] .., 101]

Question 2

My code can not deal with complex data structures if lists/associations contain other lists/dictionaries. For example, "d2:idi1e7:contentl3:abci999eee" (<|"id" -> 1, "content" -> {"abc", 999}|>). Can Mathematica match a nested pattern? If it is impossible, could you solve this problem with depth-first search?

Answer 1

I think that actually just trying to parse the input is easier than coming up with patterns that you can use in MatchQ. If the parse fails, then you know that something didn't match.

It's difficult to come up with string patterns or regular expressions that find the items unambiguously, so I found it easier to do two passes.

BEParseCodes[codes_List] := BEParseCodes[{}, codes];

BEParseCodes[tokens_, {}] := BEParseTokens[tokens];

BEParseCodes[tokens_, {100, rest___}] :=
  BEParseCodes[Append[tokens, BEDictionary], {rest}];

BEParseCodes[tokens_, {108, rest___}] := 
  BEParseCodes[Append[tokens, BEList], {rest}];

BEParseCodes[tokens_, {101, rest___}] := 
  BEParseCodes[Append[tokens, BEEnd], {rest}];

BEParseCodes[tokens_, {105, digits : Alternatives @@ ToCharacterCode["-0123456789"] .., 101, rest___}] := 
  BEParseCodes[Append[tokens, BEData[BEInteger, {digits}]], {rest}];

BEParseCodes[tokens_, next : {Alternatives @@ ToCharacterCode["0123456789"], ___}] :=
  With[
    {stringParts = Check[SequenceSplit[next, {58}, 2], {next, {}}]},
    With[
      {count = ToExpression[FromCharacterCode[stringParts[[1]]]]},
      BEParseCodes[
        Append[tokens, BEData[BEString, Take[stringParts[[2]], UpTo[count]]]], 
        Drop[stringParts[[2]], UpTo[count]]]]];

BEParseTokens[tokens_List] :=
  Sequence @@ FixedPoint[
    SequenceReplace[{{head : BEDictionary | BEList, items___BEData, BEEnd} :> BEData[head, {items}]}], 
    tokens] /. BEData -> BEInterpret


BEInterpret[BEInteger, codes_] := ToExpression[FromCharacterCode[codes]];
BEInterpret[BEString, codes_] := FromCharacterCode[codes];
BEInterpret[BEList, tokens_] := tokens;
BEInterpret[BEDictionary, tokens_] := Association[Rule @@@ Partition[tokens, 2]];

Demonstrations:

test1 = "d3:bar4:spam3:fooi42ee";
BEParseCodes[ToCharacterCode[test1]]
(* {"bar" -> "spam", "foo" -> 42} *)

test2 = "i-42e";
BEParseCodes[ToCharacterCode[test2]]
(* "-42" *)

test3 = "l4:spami42ee";
BEParseCodes[ToCharacterCode[test3]]
(* {"spam", 42} *)

test4 = "d2:xyl4:spami42ee3:bar4:spam3:fooi42ee";
BEParseCodes[ToCharacterCode[test4]]
(* <|"xy" -> {"spam", 42}, "bar" -> "spam", "foo" -> 42|> *)

test5 = "d2:idi1e7:contentl3:abci999eee";
BEParseCodes[ToCharacterCode[test5]]
(* <|"id" -> 1, "content" -> {"abc", 999}|> *)

All of this assumes that the input is correctly formatted bencode. Failures indicate malformed bencode (assuming my implementation is correct).