用Kotlin实现一个超简陋的BitTorrent客户端（一）

前段时间没事做，然后朋友安利了一下手写torrent的项目。喵了一眼各种新手向的实现，有C++的也有go的，但是没有kotlin的，就想手写一个了。然后发现简直就是超级大坑，从一个坑跳到另一个坑……

从零开始用Kotlin写一个超简陋的BitTorrent客户端

不管怎样，目前的状态是可以（仅可以）从一个叫academictorrents的网站的单文件种子里面提取出链接，然后去获取Peers的程度了。接下来的工作涉及到：

• 和Peers沟通握手
• 进行信息交换
• 管理Pieces
• 多线程下载
• 合并下载完的文件

一看就是更大的坑了（（

考虑到已经踩了不少的坑，也许是时候先把到这个阶段为止的坑先记录下来吧。

Bencode解析

要想下载文件的话，得知道这些文件叫什么，去哪里才能找到它们还有一些其他额外的信息。这些信息在torrent文件里用一种叫Bencode的编码方式来保存，所以首先要做的就是解析这个Bencode。关于Bencode的编码的规范可以看这里。

Bencode的库的话，Kotlin可以说是没有，Java倒是有那么一个。我一开始想上Parser Combinator来着（嗯，想偷懒），但是这玩意看起来还是个上下文有关的，写不了。找了一下，找到个看起来很美的思路。

这个思路是利用了PeekingIterator，首先在顶层函数decode进行模式匹配（因为每个token的第一个字符肯定要么是i要么是l不然就是d或者数字），然后根据匹配到的情况递归地调用对应的解析函数。每个解析函数再调用readN，readWhile，readUntil或者递归地调用decode函数。这三个函数的具体实现则是作为Iterator的扩展函数，在符合条件的时候一边移动this的指针一边build一个字符串，最后把字符串包装成Result<>类返回出去。拿到了Result<String>，就可以在Decoder里面用flatMap和map了。最后得到的是一个Result<Bencode>，包装了一个解析的结果，这个结果可能是成功的（Result.Success），也可能是失败的（Result.Failure），通过给结果flatMap一个回调函数来进行进一步的变换。

因为Kotlin自带的Result不能用于返回类型，然后感觉没太必要上工业级的Result库，所以就把之前啃的The Joy of Kotlin书里面的Result库复制过来将就着用了。当然，这个库缺少了一些函数得自己手写。不过也不是很难的事情。

同样的，原repo用了google.common.collect.Iterators，看了一眼感觉只是为了使用PeekingIterator的话自己手写一下也好，就自己手写了一个。

顺便提一下这个解析用到了一个叫fanout的函数，感觉有点意思，实现放在这里：

inline fun <V, U> Result<V>.fanout(crossinline other: () -> Result<U>): Result<Pair<V, U>> {
    return this.flatMap { outer ->
        other().map { outer to it }
    }
}

看样子，是获得了一个A的Result后，同时传入一个返回B的Result的lambda，最后获得一个A to B的Result（大概）。

简单测试了一下，对d3:abce之类的例子看起来都没问题，就算解决了吧。看起来很美是吧，然而，后来才发现这里面隐藏着个大坑（

提取Torrent的信息

上一步只是把Bencode编码的字符串提取成Result<Bencode>的类型，这个类型可以理解为是一棵树，每一个子树都是Bencode的子类型。但是，并不能直接从这棵树里面简单地提取出想要的信息的。回过头看一下.torrent的文件结构：

d
  8:announce
    41:https://academictorrents.com/announce.php
  7:comment
    90:Torrent of academic paper https://www.tandfonline.com/doi/abs/10.1080/09515089.2012.729488
  10:created by
    14:uTorrent/3.5.5
  13:creation date
    i1566236877e
  8:encoding
    5:UTF-8
  4:info
    d
      6:length
        i150932e
      4:name
        22:MoralPsychHandbook.pdf
      12:piece length
        i16384e
      6:pieces
        200:�����PS�^��... (字符串长度为200的二进制数据)
    e
e

这里面需要的字段有：

• announce - Tracker的URL
• info - 存放了和文件有关的内容
  • length - 文件的长度
  • name - 文件名
  • piece length - 每个文件分块的长度
  • pieces - 每个文件的Sha-1编码串接起来的一个二进制数据

那么就开始建模吧。

data class TorrentInfo(
    val pieces: String, val pieceLength: Long, val length: Long, val name: String
)

data class TorrentSeed(
    val info: TorrentInfo, val announce: String, val infoHash: String
)

data class TorrentFile(
    val announce: String, val infoHash: String, val pieceHashes: List<String>, val pieceLength: Long, val length: Long, val name: String
)

（这里补充一下，一开始没在TorrentSeed里面提取infoHash，而是想着在提取出TorrentInfo后再去encode，以为可以通过拼接字符串来重新生成bencode编码，结果证明是不可以的（而且代码也变得非常面条）。最后还是决定在BencodeParser里面实现encode函数，encode函数实现倒是非常简单，但这个函数接受的是一个Bencode类型的实例。于是就在转TorrentInfo的时候顺便提取出info（一个字典，也就是Bencode的子类），并且从这个info生成encoded的编码来进行hash了，这也算是一个坑吧？）

因为这棵树里面，总是从一个字典里面获取其他类型（字符串/数字/列表或者字典）的Bencode子类，所以可以写出这样的辅助函数：

fun DictionaryLiteral.getIntAttr(attr: String): Result<BigInteger> = this.of[ByteStringLiteral(attr)]?.let {
    when (it) {
        is IntLiteral -> Result(it.value)
        else -> null
    }
} ?: Result.failure("Cannot get IntAttr $attr from dictionary")

其他的三个类型的话函数结构类似，只是要改变content的类型来跟要提取的值的类型对的上号。其实本质上说，这个函数的意思类似于Dictionary[attr]然后去判断结果的类型是否Int。

有了辅助函数，就可以进一步写从Result<DictionaryLiteral>生成TorrentSeed然后生成TorrentFile了。

fun Result<DictionaryLiteral>.getInfo(): Result<TorrentInfo> =
    this.flatMap { dict ->
        dict.getIntAttr("length").flatMap { length ->
            dict.getStringAttr("name").flatMap { name ->
                dict.getIntAttr("piece length").flatMap { pieceLength ->
                    dict.getStringAttr("pieces").flatMap { pieces ->
                        Result(TorrentInfo(length = length.toLong(), name = name, pieceLength = pieceLength.toLong(), pieces = pieces))
                    }
                }
            }
        }    
    }
    
// 这里调用了getInfoHash()函数，也就是在Result内部顺便计算了infoHash然后传给要返回的TorrentSeed里
fun Result<DictionaryLiteral>.getSeed(): Result<TorrentSeed> =
    this.flatMap { dict ->
        dict.getStringAttr("announce").flatMap { ann ->
            dict.getDictAttr("info").flatMap { info ->
                Result(info).getInfo().flatMap { infos ->
                    Result(info).getInfoHash().flatMap { ih ->
                        Result(TorrrentSeed(info = infos, announce = ann, infoHash = ih))
                    }
                }
            }
        }
    }

一大堆flatMap吓到我了 -- n0099

do
    dict <- this
    ann <- getStringAttr dict "announce" -- 返回的TorrentSeed的第二个参数
    info <- getDictAttr dict "info"      -- 这个info会被接下来两行consume掉
    infos <- getInfo (return info)       -- TorrentSeed的第一个参数
    ih <- getInfoHash (return info)      -- TorrentSeed的第三个参数
    return TorrentSeed infos ann ih

这样翻译的话可能看起来会清晰一点？因为kt里面没有do-notation所以只能用flatMap套lambda来表达同样的思路了（据说可以写个fmap函数然后用applicative，但是又不是不能用.jpg）

测试

看起来很顺利就完成任务了，接下来就是写Tracker的部分（这里略过，下文再提），写完PeerRetriever后开始测试，吓了一跳：两个种子，一个死循环了另一个报错。

死循环看来问题出在Parser上。试着把前文提到的那个kt的Parser实现下载下来，发现那人的源代码也跑不动（摔

鉴于kt上也没像样的bencode解析库，这一环节是绕不过的。就debug一下看看是怎么回事吧。于是发现问题出在列表或者字典的decode过程上。以列表为例，解码的过程中有一个循环while (!iter.consume(ENDING_MARKER).getOrElse(false))，假设有一个字符串列d3:abcde，这里的3:abc会被decodeString(firstDigit:)吃掉，指针指向d，这时并没有读取到e这个结尾符，会试图调用decode()函数，但是decode()函数里面只是peek喵一眼这个d字符然后发现不匹配就返回了个Result.failure了。因为被包装在Result<>里面所以不会报错，但是指针也不会再移动，就无限死循环了（

解决方案是在decode()里面把peek()改成nextChar()吃掉下一个字符，然后把这个字符传给各函数作为它们的参数（实际上只需要传给decodeString(marker:)，因为其他的函数都只会吃那么一个固定的字符）。

这样的话死循环就变成报错了。

分析一下报错的原因，有可能是因为数据结构不匹配（毕竟采用的是最简单的那种假设），但是这里还有一个问题，就是pieces的长度和字符串前面声明的那个数字（这里是200）对不上号。这一部分接下来在Encoding里面再讲吧。

技术选型

于是做到这里，我们有了一个简陋的Bencode编/解码的实现，而且是基于Result<>的。接下来的问题就是该用什么技术抄哪篇blog教程了。虽然是对照着那个go的教程走下来的，但是我是很不想看go的代码的，同样的，也希望能用较为接近fp、声明式的写法。

但是以有限的对fp的知识来说，如果要在monad里面套个网络编程的IO副作用，感觉写起来会非常复杂（

找到了个用Haskell来写的blog [1] [2]，好耶，是声明式的写法。不过这里有两个问题：

• 要用到Functor、Applicative等概念，Kotlin里面没有HKT，不过这个可以用ArrowKt来模拟出来。
• 涉及到网络编程和Socket的领域，Haskell的库提供的是纯FP的写法，但Kotlin应该是命令式的写法，怎样把Socket和网络副作用封装到monad里面呢？估计得自己手写了……复杂度++（

最后还是放弃FP的想法了。于是就在Result<>里面加了Result<T>.unsafeGet(): T函数备用了。

Encoding

前面提到那个pieces长度和声明的200不匹配（只有193）的问题，想了半天，用Hex Fiend看也是200个字节，最后想到应该是encoding的问题，然后就把encoding改成了ASCII，用了File.readText(Charsets.US_ASCII)，解码顺利完成。然而，这里有个大坑。

另一个坑是在反复测试bencode的过程中，因为intellijIDEA不能正确显示二进制内容，把种子里的一部分文本内容和二进制内容搅在一起了，就选择了bidi显示的left-to-right，结果，种子的内容被改变了（直接影响后面的一个环节）。

解码成功了就开始测试和Tracker沟通的环节吧。结果服务器返回错误说Hash对不上，然后一算Hash人傻了，算出来奇怪的东西（

首先，可以保证Sha1计算是没问题的，因为用了这里的样例测试过了。

从头开始吧，下载Bencode Editor，对着info算Hash，结果是9049……DCF6，然后找了几个在线编码Sha1还有字符串转Hex的网站，拼凑了一下，证明了info的字段加起来可以得到正确的Hash。考虑到之前encode实际上是采用的拼接字符串，会不会这里面有问题呢，于是就改成从Bencode里面直接encode的实现（前文提到过），还是不行。之后也试过读取后把字符串换成ByteArray，也是不行的。

然后进debug对比info列的字符值和种子里面的内容，发现了一堆3f，一顿测试修改后发现是从字符串转为ByteArray的时候不能用toByteArray(Charsets.ASCII)方法，要用this.map { it.code.toByte() }.toByteArray()。

然后发现了一堆fd……同样的，因为之前打开文件的时候用了ASCII编码所以丢信息了。解决方案是打开文件的时候用File.readBytes().map { it.toChar() }.joinToString("")，因为无论选择哪个encoding来readText，得到的都是错误的编码。

然后发现Hash还是对不上。原因是之前在IDEA里面选择了left-to-right的bidi改变了种子文件的内容……坑真多（

和Tracker沟通

获取了正确的Hash了，该和服务器沟通了吧。结果无论是把原Hash发过去，还是发的urlEncoded的Hash，还是hexDecoded的Hash（这个肯定不行），都报错说Hash对不上号。

问了知乎那边的作者，那边说用浏览器打开拼接的URL没问题。于是就有了个思路，用postman去测试，也得到了正确的结果了。但是为什么同样的参数在程序里面就不行呢。

最后还是注意到了%25这个奇怪的表现了，在khttp的这个issue里面也提到了，url里面的百分号会被再次encode成%25。这个库也很久没更新了，只好换库。换了Ktor后还是同样的结果，好在，Ktor提供了关闭UrlEncode的选项。于是就这样写了：

val rsp = client.get<HttpResponse>(urlString = announceUrl) {
    url {
        parameters.urlEncodingOption = UrlEncodingOption.NO_ENCODING // 关闭把parameter自动urlencode的机制
        parameters.append("info_hash", infoHash.hexToUrlEncode())
        parameters.append("peer_id", peerId)
        parameters.append("port", this@PeerRetriever.port.toString()) // 这里的port会和ktor内部的参数clash，用this@PeerRetriever来获取我们指定的port
        parameters.append("uploaded", "0")
        parameters.append("downloaded", byteDownloaded.toString())
        parameters.append("left", "${fileSize - byteDownloaded}")
        parameters.append("compact", "0")
        // 不知为何返回的永远是不compact的结果，所以和教程不一样，这里改为0了
        // 以后再来完善好了
    }
    timeout {
        requestTimeoutMillis = TRACKER_TIMEOUT
    }
}

然后就可以获得Peers的列表了，大概像这样的：

d8:intervali30e5:peersld2:ip14:189.191.137.567:peer id20:-BW122Q-ZgXOsz6y725Z4:porti6881eed2:ip13:46.232.211.957:peer id20:-lt0D60-f͔����4:porti62483eeee

Peer解包也很简单，这里就不重复解释了。

然后呢……

很遗憾，目前就只实现到这里了（

接下来的步骤难度只会更大，因为不能每个模块单独实现然后写个maina来单独测试每个模块的功能了（或者说很大程度上不同模块是互相耦合在一起的）

接下来可能得花上好几个月慢慢磨了（

那么就姑且写到这里，也当是个备忘录吧。