不知道出于何种原因，我突然决定自己造轮子。索性这个轮子造的好像还不是特别没用。本文将记述我从零开始使用Kotlin实现一个Bencode编解码库。
前言
Java和Kotlin（JVM）具有比较好的互操作性，即便没有给Kotlin设计的库，如果有相应的Java库，在Kotlin上也是可以直接调用的。在此之前我尝试过com.dampcake:bencode这个库，用起来感觉还不错，但它的操作是类似DOM那种，即所有写入和读出的数据全部存在内存里以供操作。这种操作方式固然简单好用，但是如果你有很多数据的话，你可能更希望采用接近XML SAX的方式。后者是基于流的解析方案，也就是说解析器一边读入数据，一边将解析出来的结果交给你的代码。你可以选择将他们收集起来组装成DOM，也可以选择即时处理然后回收。本文将考虑如何构建一个基于流的Bencode编解码库。
Bencode
Bencode好像是一种不太常见的编码。考虑到早年间的XML，以及现在的Json，好像Bencode并没有什么用武之地？但作为一个P2P爱好者和版权左人，大名鼎鼎的BitTorrent协议就是用Bencode编码数据。这种编码形式以字符为基础，肯定不如ProtocolBuf这种二进制编码高效，同时它的结构比较简单，不太可能像XML或Json在功能上那么丰富（Bencode甚至不支持编码小数）。但从某种意义上来说，Bencode确实是最简单且紧凑的格式。
举个例子。在Json中表示一个结构是这样的：
{
"number": 1234,
"string": "hahaha",
"list": [
"string in list", 2345, [ "list in list!" ], { "name": "object in array!" }
],
"obj": {
"string": "An object",
"list": [ "List in object!" ],
"dict": { "num": 2345 }
}
}去掉所有多余的空格，一共是195个字符。如果表示成XML，那就更罗嗦了：
<?xml version="1.0" encoding="UTF-8" ?>
<root>
<number>1234</number>
<string>hahaha</string>
<list>string in list</list>
<list>2345</list>
<2>list in list!</2>
<list>
<name>object in array!</name>
</list>
<obj>
<string>An object</string>
<list>List in object!</list>
<dict>
<num>2345</num>
</dict>
</obj>
</root>XML需要295个字符，而且它还没有保留list in list的部分。这可能是我是用的Json到XML转换器有问题，也可能是XML并没有名且规定列表的格式。
如果将上述数据转换成Bencode，那就显得紧凑了不少：
d4:listl14:string in listi2345el13:list in list!ed4:name16:object in array!ee6:numberi1234e3:objd4:dictd3:numi2345ee4:listl15:List in object!e6:string9:An objecte6:string6:hahahaeBencode只要179个字符。而这段数据的所有文本内容需要125个字符（数字由对应的字符表示，且丢弃了所有结构信息）。
当然，如果只从格式上看的话，Bencode不是那么的“人类友好”，但这无伤大雅，我对于Bencode的主要用途是简单地导入和导出结构化数据，而不必考虑给人看。
说了这么多，不如我们来看看Bencode的编码规则。
Bencode的编码规则比较简单：
- Bencode使用ASCII字符作为分隔符和元素
- 对于数字，采用
i42e的形式来编码，其中42是数字42对应的十进制字符串。数字不允许前导0（即00042是非法的）。负数使用-作为前缀，即i-42e，但不允许负0 - 对于字节串（字节序列，并不一定是字符），采用
4:spam的形式来编码。其中4表示这个字节串的长度，采用十进制字符串表示，冒号表示分割，随后spam是字节串的实际内容。Bencode并没有提及数据无法被编码成ASCII时应当如何处理，在一些具体实现中，人们主要采用UTF-8来应对其他字符，或使用ISO 8859-1来编码字节数据，亦或采用Base64等编码将字节串编码为ASCII字符串 - 一个列表由
l<content>e表示。一个具有字符串“spam”和数字42的列表应当被表示为l4:spami42ee。其中首个字符是小写字母L，不是数字1。列表内的元素类型不受限制。 - 一个字典由
d<content>e表示。在字典中，字符串作为键后面总是直接跟着值。所有键必须按照字典序进行排列。例如字典{"bar": "spam", "foo": 42应当被表示成d3:bar4:spam3:fooi42ee。字典的值的类型不受限制。
通过上述这几条规则，基本上就没有Bencode表示不出来的结构。同时字典规定了键的排序，保证了编码结果的唯一性。
流式编码
上面说了半天编码，不如我们就从编码入手，看看怎么基于流来编码。编码器的输入往小了说就是那四个基本类型：整数、字符串、列表和字典，对应Java里面的BigInteger、String、List<*>和Map<String, *>。因为Bencode并没有规定整数的最大上限，因此使用BigInteger来存储整数。
整数和字符串
对于整数和字符串来说，流失编码好像没有太多的意义：除非一个整数或字符串占用了以G计算的内存，你可能需要流式处理，不然没有必要把他们拆开——就算拆开，字符串还好说，整数怎么拆呢？这个就需要看具体的应用场景了，而作为一个通用的库来说，我们没有办法提供一个不过度复杂同时还通用的机制。因此这两个元素没有什么流式不流式的说法。
列表
对于列表就不一样。这里我们通过循环的方式来模拟对列表内数据的访问和写入。如果我们有400万个Int，他们在内存中大约占用16MB的内存。如果我们将他们转换成BigInteger，都不使用List，就用最紧凑的数据，在128MB的内存限制（-Xmx128M）下，程序直接OOM了。
val array = IntArray(400_0000) { it }
val list = Array(400_0000) { array[it].toBigInteger() }
println(list.count())即便没有OOM，这个list所占用的额外内存也必须等待所有数据写完之后才会被垃圾回收——只要编码器还没写完，对于GC来说这个列表就是可达的，那么每一个元素都无法被回收，即便他们的一部分已经被写入了。
好在Kotlin提供了Sequence这个东西。Sequence的好处就是可以根据需求（on-demand）产生数据。也就是说，我通过循环的方式统计个数，而每次我只需要一个数据，处理完成之后这个数据就可以被GC回收了。使用Sequence，整个程序只占用了22MB的内存：
val array = IntArray(400_0000) { it }
val seq = sequence {
for (i in array)
yield(i.toBigInteger())
}
println(seq.count())我们只要使用Sequence，就可以保证数据只有被编码器需要的时候才会产生。这不就是流式处理吗？
字典
下面我们来看看字典。我们可以借鉴列表的经验，但是Sequence有一个问题：除非提供者保证，否则没法确保数据是有序的，而我们的字典在编码时要求键必须按照字典序排列。要么我们就接受用户的输入，如果检测到违反了字典序，就抛出异常；要么我们就想办法自己构建一个类似Sequence的Map。
好在我并不是第一个遇到这种问题的开发者。在Java中就提供了Supplier这个接口，而Kotlin中也有Lazy这种能够提供延迟求值的工具。但最简单的还是一个Lambda：() -> T，只要我们将Map的类型设置成Map<String, () -> T>就可以了。但是这个T怎么取呢？我们的元素有BigInteger、String、List和Map，且不说前两个没有共同的父类，后两者还有泛型擦除的问题，很显然编译器并不能要求传入的List必须是List<String>，而不能是List<UUID>。
在传统的Java开发中，这个时候我们就应该已经写出编码器的接口，同时还有BencodeSerializable接口了，但是我个人并不太喜欢接口满天飞。不过在这种情况下，接口可能是无法避免的：
sealed interface BEntry {
data class BInteger(val value: BigInteger) : BEntry
data class BString(val value: String) : BEntry
data class BList(val value: Sequence<BEntry>) : BEntry
data class BMap(val value: Map<String, () -> BEntry>) : BEntry
}由于我们接口下面的实现是已知的，毕竟Bencode中就规定了四种元素，因此完全可以使用密封类来修饰接口。这样，当我们使用BEntry作为when的参数时，编译器就会知道，这个参数只有四种可能的情况，而我们上面的T也就可以取值为BEntry了。
编码器
既然有了这个BEntry，我们就可以面向这个接口设计编码器了。我们的BencodeEncoder在构建时只需要一个Writer，这个对象负责处理字符的写入，而无需我们考虑字符集编码这些问题。关于成员函数，由于我们的BEntry设计的很清晰，因此只需要一个fun writeEntry(entry: BEntry): Unit就好了。
为了方便维护，我们可以针对不同的类型设计不同的私有函数，将writeEntry作为一个集中分派的入口：
fun writeEntry(entry: BEntry) = synchronized(writer) {
when (entry) {
is BEntry.BInteger -> writeBInteger(entry)
is BEntry.BString -> writeBString(entry)
is BEntry.BList -> writeBList(entry)
is BEntry.BMap -> writeBMap(entry)
}
}这里我们对writer加了锁，这是避免在多线程使用时造成冲突。例如一个列表正在输入，另一个线程突然开始写字典了，很有可能就会得到类似字典把列表截断，而列表又把字典截断的情况。
对于四种类型的写入也比较简单：
private fun writeBInteger(entry: BEntry.BInteger) {
writer.write("i")
writer.write(entry.value.toString(10))
writer.write("e")
}
private fun writeBString(entry: BEntry.BString) {
writer.write(entry.value.length.toString())
writer.write(":")
writer.write(entry.value)
}
private fun writeBList(entry: BEntry.BList) {
writer.write("l")
entry.value.forEach { writeEntry(it) }
writer.write("e")
}
private fun writeBMap(entry: BEntry.BMap) {
writer.write("d")
entry.value.keys.sorted().forEach { k ->
writeBString(BEntry.BString(k))
writeEntry(entry.value[k]!!())
}
writer.write("e")
}像是字典的键，我们知道它的类型，就可以直接调用writeBString，而对于值，我们并不知道它的类型，因此较为writeEntry进行分派。
Writer
有了编码器，但好像还不太够：这个编码器只能面向我们的BEntry工作。如果用户想要编码一个Map，还必须得转换成我们的BEntry.BMap，有点麻烦。如果我们能直接编码Map对象，甚至任意的对象呢？
我想到了两个思路。
第一个思路比较简单粗暴：提供一个接口，让用户可以实现这个接口，从而提供一个BEntry出来：
interface BencodeEncodable {
fun encodeToBEntry(): BEntry
}使用的时候看起来是这样的：
data class Point(
val x: Int,
val y: Int
) : BencodeEncodable {
override fun encodeToBEntry(): BEntry = BEntry.BMap(mapOf(
"x" to { BEntry.BInteger(this.x.toBigInteger()) },
"y" to { BEntry.BInteger(this.y.toBigInteger()) }
))
}第二个思路则相对灵活一些：在实例化Writer的时候提供一系列mapper，他们将对应类型的对象转换为BEntry。如果更进一步扩展这个概念，mapper可以把writer不认识的类型转换成它认识的类型。例如上面那个Point类的mapper可以是：
val mapper = BencodeEncoderMapper<Point> {
mapOf(
"x" to it.x,
"y" to it.y
)
}你会发现这个Mapper的返回值并不是BEntry，而是一个Map<String, Int>。而我们的Writer可以把这个Map转换成对应的BMap：只需要将值映射为{ it.value }就可以了。而完成转换之后，这个mapper返回的map就会被丢弃，从而可以被垃圾回收。不过在Mapper中不能返回lambda，因为JVM在运行的时候比较难判断一个值到底应该被包装成lambda，还是要作为lambda放进Map。
Kotlin在编译时并没有保证两个类型相同的Lambda对于JVM就一定是同一个类型的。因此同样都是() -> BEntry，他们可能是两个不同的类。当然，使用反射可以解决这个问题，查看一个对象是否具有invoke()的方法，并且返回值不是Unit或Nothing，但我本意是想避免这些黑魔法的。
另外还需要注意这两种思路的细微差别。对于实现接口来说，因为BEntry要求使用Supplier，所以BEntry.BInteger(this.x.toBigInteger())这一行只有在写入了键x之后才会被调用，可以认为获取到的值就是最新值了。而Mapper虽然也是在写入时调用，在Writer调用完成后，便得到了一个快照（因为在JVM上，对于Int的赋值是值复制，不是引用复制），也就是说，在Writer调用完成后、Encoder写入完成前，无论原来的Point.x怎么变，写入的内容都不会变了（在Encoder中调用的Supplier实际上只返回一个Int，这个Int是mapper中对it.x的求值）。
当然，如果对于数据类都是用不可变类型，那自然是极好的。如果涉及可变类型，那除了保证内存可见性之外，还要考虑将对象转换成BEntry的时机对于编码结果的影响。
总之，在这个库里面我实现了这两种思路，如果是自己编写类的话，建议使用第一种；如果是别人的类，那么就可以考虑使用Mapper在序列化时自动转换。
关于这部分的代码也比较简单，Writer的主要入口：
fun write(obj: Any): Unit = encoder.writeEntry(mapToBEntry(obj))而负责转换的函数实际上就是一个lookup table：
private fun mapToBEntry(obj: Any): BEntry = when (obj) {
is BEntry -> obj
is BencodeEncodable -> obj.encodeToBEntry()
// for signed value, convert to long
is Byte -> BEntry.BInteger(obj.toLong().toBigInteger())
is Short -> BEntry.BInteger(obj.toLong().toBigInteger())
is Int -> BEntry.BInteger(obj.toLong().toBigInteger())
is Long -> BEntry.BInteger(obj.toBigInteger())
// for unsigned value, convert to long so the value is same
is UByte -> BEntry.BInteger(obj.toLong().toBigInteger())
is UShort -> BEntry.BInteger(obj.toLong().toBigInteger())
is UInt -> BEntry.BInteger(obj.toLong().toBigInteger())
// for ULong, it's bigger than long, thus turn it into string
is ULong -> BEntry.BInteger(BigInteger(obj.toString()))
// for chat and string, just write string
is Char -> BEntry.BString(obj + "")
is String -> BEntry.BString(obj)
// for list, transform it to sequence
is List<*> -> BEntry.BList(obj.asSequence().map { mapToBEntry(it!!) })
// for map, map the key to string and map value to BEntry
is Map<*, *> -> BEntry.BMap(obj.mapKeys {
if (it.key is String) it.key as String else it.key.toString()
}.mapValues { { mapToBEntry(it.value!!) } })
// for general object, search mapper and apply the transform
else -> ((mapper.find { it.canHandle(obj) }
?: error("Mapper not found: ${obj.javaClass}"))
as BencodeEncoderMapper<Any>)
.invoke(obj)
.let { if (it is BEntry) it else mapToBEntry(it) }
}关于Mapper的设计，也比较简单：
interface BencodeEncoderMapper<T> {
fun canHandle(obj: Any): Boolean
fun invoke(obj: T): Any
}这个canHandle是用来询问一个mapper实例能否处理这个类。因为运行时的泛型擦除，Writer除了知道这是一个Mapper之外，并不知道它所实现的泛型是什么，更不要说什么类型间的继承应该如何处理了——有时候子类可以按照父类处理，有时候子类需要它独有的处理方式。
当然，每次实例化Mapper都需要写一个object : Interface { ... }都怪臃肿的，而且这个接口有两个函数，没法用SAM。但是啊，我们可以用同名函数来实现简化：
inline fun <reified T> BencodeEncoderMapper(crossinline block: (T) -> Any) =
object : BencodeEncoderMapper<T> {
override fun canHandle(obj: Any): Boolean = T::class.java.isInstance(obj)
override fun invoke(obj: T): Any = block(obj)
}当然了，简化的代价就是要服从一些约定。这里关于能否处理的判断，是调用了泛型类的isInstance方法。得益于Kotlin的inline和reified，我们可以在内联函数中访问泛型的具体类型。这也是实现第二个思路的关键。如果要我在Java中实现类似的机制，我肯定要舍弃掉第二个思路——无论使写起来还是用起来，都太臃肿了。
写到这里突然想到，使用Mapper可能会出现成环的情况。比如说一个类型A的Mapper返回了类型B，而类型B的Mapper又返回了类型A，这样不停的递归调用就会导致爆栈。
不过话又说回来，这样成环肯定说明这家伙的数据类型设计的很不合理，总之不是我的锅就对了。
解码
说完了编码，再说说解码。你会发现说解码的时候我可没提流式。我在不同的设计方案中思考了半天，最终决定像编码那样提供两个层级的API。底层可以是流式的，但顶层就比较困难了。解码意味着要处理一系列的输入流，而若像编码那样使用Supplier按需解码，就需要解码器能够知道要跳过多少字符以便解析下一个元素，同时还能倒回某一处，在需要的时候解码以前跳过的内容。这对于Reader来说实在是强人所难了。
但是这种限制并不意味着我们必须把一个元素完整的解析到内存中。我们可以根据当前的字符构造状态机啊！
例如我们读到一个字符i，我们就知道下一个元素应该是一个整数；如果读到1~9中的一个，那么下一个肯定是字符串；类似地，如果读到l或者d，那么下一个肯定是列表或字典。而且他们的终止符都是成双成对的，只要输入的是合法的数据，就不会出问题。
举个例子：
data class Person(
val name: String,
val age: Int,
val friends: List<Person>,
val attributes: Map<String, String>
)我们在读取的时候可以构建一个Builder，根据读到的内容填充builder。例如说：
- 在开始之前应该预期一个字符
d，因为对象将被处理成字典 - 接下来应该预期字符1~9中的一个，因为字典中总是键值的顺序，而键是字符串
根据读到的键，预期不同类型的数据
- 例如读到了name，就应该预期一个字符串
- 读到age，就预期一个整数
- 如果是friends，那就调用处理
List<Person>的函数，循环调用当前函数以读取Person列表，最后将读出的列表返回
- 当遇到字符
e的时候，检查这个Builder是否已经准备好build了。如果还有缺失数据，说明输入的有问题
显而易见地，这是个递归结构。如果你怕爆栈的话，改成链表+循环也可以。但脑子尖的读者应该已经注意到了：这个friends对应的列表，并没有流式解析啊，反倒是只有最顶层的Person是流式解析，而它的内容倒都变成DOM形式了。
对，你说得都对。
这个问题我也思考了很久，最后得出来的结论就是以实际需求为准。我上面那个例子是根据输入还原对象，也就是说无论如何我们都是避免不了DOM形式的。但如果说你是想即时更新数据库，那相比之下就简单了不少：你只需要在读到id之前暂存数据，读到id之后直接采用多个UPDATE语句的形式，读一个就产生一条语句，然后丢弃结果。
总之在这方面，我尽力了。如果一个对象不大的话，那么以对象为单位进行DOM形式的操作，而总体还是流式的话，我反正是能接受的。
解码器
关于解码部分的代码这里就不多说了，只介绍一下API。较为底层的API是BencodeDecoder，实例化时需要一个Reader来读入字符，它总共有如下方法：
fun hasNext(): Boolean
fun nextType(): BEntryType
fun readInteger(): BigInteger
fun readString(): String
fun startList(): Unit
fun startMap(): Unit
fun endEntity(): Unit这其中，hasNext不必多说，就是看Reader是否已经被处理干净了。如果还没有，那么就读入一个字符。而后nextType则是根据当前读入的字符来判断类型。这里你会发现我没有用BEntry，一来是它的实现都不是Object，没法直接用，二来是解码时l和d表示列表和字典的开始，而e则单独表示一个实体的结束，没办法与四种类型对应。因此就额外引入了一个Type类，它也是密封接口，而它的实现，除了EntityEnd比较特殊，其他的都是BEntry的四个实现的companion object，也就是说我们可以直接写BEntry.BList来表示一个BEntryType，我觉得很是优雅。
后面两个read就不用说了——直接读取对应类型的值，读完之后还要读入下一个字符，以便后续调用hasNext来判断。而至于列表和字典，这个start函数只是检查一下当前的字符是否正确。例如startList会检查当前字符是不是l，不是的话就会抛出异常，避免错误地开启列表。剩下的startMap和endEntity也是类似的操作。
Reader
而较高等级的API则提供了一种近似DOM方式的API：
class BencodeReader(
reader: Reader
) {
fun hasNext(): Boolean
fun nextType(): BEntryType
fun readInteger(): BigInteger
fun readString(): String
fun readList(): List<*>
fun iterateList(callback: Consumer<Any>)
fun readMap(): Map<String, *>
fun iterateMap(callback: BiConsumer<String, Any>)
}
前两个就不多说了，唯一值得一提的就是nextType，因为读出来就是完整的对象，所以不存在EntityEnd这种类型。后面的各种read也不必多说，读出来就是对象。
这里额外提供了两个iterate方法，为的是流式遍历顶层对象。比如说一个输入是几百万个小对象组成的列表，那么iterateList就会每次解析一个对象，然后交给callback处理，处理完成后再解析下一个。字典也是一样，每次解析一对键值，然后交给callback处理。
后记
至此这整个库的设计思路就介绍完了。这个库本身比较简单，不像Ktorm那种复杂的库。但碍于我没有设计库的经验，在设计的过程中考虑了好多有用的和没用的细节，以至于文章写起来很罗嗦。另外写文章的时候突然意识到一些问题，就把文章扔到一边修改代码去了，改完代码再接着写文章，难免会有些思路上的跳脱。好在这又不是出版书籍，有点问题就有点问题了。
也许有经验的读者看到我这边文章会说：就设计一个编解码的库，这孙子怎么写的那么啰嗦，这不脱了裤子放屁吗？有的地方还狗屁不通，这写的啥啊这是？我奶奶用脚写的都比这好
对，你说的都对，不爱看滚蛋。不过还是要感谢一下能耐心读到结尾的读者，感谢你们的耐心。
关于这个库，我已经开源到了GitHub上，可以在JitPack上使用相应的制品。
-全文完-
【代码札记】Bencode编解码（Kotlin） 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。