# Bencodeの実装

* **Bencodingはパースしやすい構造**
* **BNFから機械的にコードを抽出**

## 見慣れたデータ構造に落とす

Benodingを実装してみましょう。Bencodingで扱えるデータは、Number, String, List, Dictionary でした。これらを、Dartから扱えるようにしましょう。

具体的には、Dartでサポートされているデータ構造に変換していきます。DartのNumber,Uint8Array,List,Mapへ変換していきます。

BencodeのNumberは、Dartのnumで表現できます。BencodeのStringは、UInt8Arrayで表現できます。Stringでないところは少しトリッキーです。Bencodeでは、バイト配列を扱うこともあります。Unicodeでは使えないデータもStringとして扱うことになりまいから、Stringでなく、UInt8Arrayを利用します。Bencodeのリストは、Dart言語の Listで、Bencodeの辞書は、Dart言語では Map で表現できます。

具体的には、以下のようなAPIを考えます。

```
class Bencode {
  static Uint8List encode(Object obj);
  static Object decode(List<int> buffer);
}
```

もちろん、Bencodeの実装は見慣れた形式に落とす方法だけではありません。BencodeのStringはBenString、ListはBenList、DictionaryはBenDict、といった専用のクラスに変換する方法も可能です。

Dartの Map は、BencodeのMapよりも扱える範囲が広いですから、Dartのデータ構造から、Bencodeのデータ構造へ変換ができないパターンがあります。例えば、以下のような形式はBencodeでは表現できません。

```
int // 0.1 といった少数点を含む場合
    // -1といつたマイナス値を含む場合

Map<int, String> // keyがStringでない場合
```

このような制約がある事を、BenString, BenList といった構造を定義する事でAPIとして表現する事ができます。

しかし、今回は「見慣れた構造に落とす」という方針で設計しました。

## Bencodeはパースしやすい構造

Bencode はパースが容易な構造になっています。なぜならば、 どのデータ構造なのかが、最初の一文字目で判別する事ができるからです。

“i” ならば、整数。 “0123456789” のどれかならば、文字列、”l” ならばリスト、”d” ならば辞書 といった感じです。

これを、コードに直すと、以下のような感じになります。

```
int index = 0;
Object decodeBenObject(Uint8List buffer) {
  if( 0x30 <= buffer[index] && buffer[index]<=0x39) {//0-9
    return decodeBytes(buffer);
  } else if(0x69 == buffer[index]) {// i
    return decodeNumber(buffer);
  } else if(0x6c == buffer[index]) {// l
    return decodeList(buffer);
  } else if(0x64 == buffer[index]) {// d
    return decodeDiction(buffer);
  }
   throw new ParseError("benobject", buffer, index);
}
```

見ての通り、先頭の値に応じて処理が分岐しているだけで す。後は、おのおのデータ構造とみなして、変換してあげれば 完成です。

## もっと Parser

Torrentクライアントを実装するにあたり、さまざまなプロトコルを実装していきます。 プログラム言語や自然言語ほど、複雑ではないので容易に解析可能です。 このタイミングでBNFで定義された文法を解析する方法について解説します。

### BNF から機械的にパーサーを書くことができる

BNFで書かれた構文は機械的にパーサーを書く事ができます。

```
• 規則名をメソッドにする。
• ルールに文字列がでてきた場合、一致するかチェックする
• ルールに規則がでてきた場合、そのメソッドを呼び出す
• ルールに違反かる場合は、Exception をスローする。
```

プログラム言語、自然言語といったものは、もう少し工夫が必 要ですが、今回は、基本的なルールを守るだけで実装できま す。もう少し詳細な情報が欲しい場合は、「Language Implementation Patterns 」という本を読む事をお勧めです。

具体的に、Bencode 用のパーサーを作成しながら、見ていきま しょう。 例えば、Dictionary は以下のように書けます。

```
Map decodeDiction(data.Uint8List buffer) {
  if(buffer[index++] != 0x64) {
    throw new ParseError("bendiction", buffer, index);
  }
  Map ret = decodeDictionElements(buffer);
  if(buffer[index++] != 0x65) {
    throw new ParseError("bendiction", buffer, index);
  }
  return ret;
}
```

BNFと一対一の関係がある事が解ると思います。Dictionary は 27 「 “d” bendictionelements “e”」と文法で表現されます。ですか ら、”d”という文字か確認。 dictionelements のメソッドを呼 び出す。“e”という文字か確認する。 ルール通りです。

## テストを書く

テストを書きながら、パーサーを書いていきましょう。まずは 整数からです。

```
unit.test("bencode: number", () {
  num ret = hetima.Bencode.decode(toBuffer("i1024e"));
  unit.expect(1024, ret);
});
```

このテストを満たすように、パーサーを書きます。bencodingで整数は、 「“i” \*(0-9) “e”」と書けます。なので、これもル ールに従って以下のように書けます。

```
num decodeNumber(data.Uint8List buffer) {
  if(buffer[index++] != 0x69) {
    throw new ParseError("bennumber", buffer, index);
  }
  int returnValue = 0;
  while(index<buffer.length && buffer[index] != 0x65) {
    if(!(0x30 <= buffer[index] && buffer[index]<=0x39)) {
      throw new ParseError("bennumber", buffer, index);
    }
    returnValue = returnValue*10+(buffer[index++]-0x30);
  }
  if(buffer[index++] != 0x65) {
    throw new ParseError("bennumber", buffer, index);
  }
  return returnValue;
}
```

数字を取り出す部分が少し複雑ですが、無事テストが通るコー ドがかけました。この調子で、文字列、リスト、と同じように テストしながら、作成すれば完成です。kyorohiroが作成した物 は、以下にあります。「<https://github.com/kyorohiro/dart_hetimatorrent」> 事の顛末を知りたい方は参照してください。

Kyorohiro work

<http://kyorohiro.strikingly.com>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nazenani-torrent.firefirestyle.net/torrentfile/implementation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.