0. 问题
我在解析 Redis Simple Strings 和 Errors 时用到了 Netty 的一个工具类 io.netty.buffer.ByteBufUtil 里的 indexOf(ByteBuf needle, ByteBuf haystack) 方法。也忘记了是如何找到了这个方法，但是一直这么用着。
最近升级了一下 Netty 版本（ 4.1.45.Final --> 4.1.72.Final），结果解析 +PONG\r\n 就出错了，原来能正确解析出 PONG，现在解析的结果是 PON。
简化的处理逻辑如下所示：
ByteBuf in = Unpooled.copiedBuffer("+PONG\r\n", CharsetUtil.UTF_8);
ByteBuf SEP_CRLF = Unpooled.copiedBuffer("\r\n", CharsetUtil.UTF_8);
in.readByte();
int index = ByteBufUtil.indexOf(SEP_CRLF, in);
System.out.printf("expect 5, actual %d%n", index);
4.1.72.Final 版本的执行结果是 expect 5, actual 4。
感觉上新版本返回的“相对 index”而不是之前的“绝对 index”。
1. ByteBufUtil.indexOf(ByteBuf needle, ByteBuf haystack) 的使用
通过 IDEA 的 Find Usages 工具发现这个这个方法只在 io.netty.handler.codec.http2.Http2ConnectionHandler 使用：
// If the input so far doesn't match the preface, break the connection.
if (bytesRead == 0 || !ByteBufUtil.equals(in, in.readerIndex(),
clientPrefaceString, clientPrefaceString.readerIndex(),
bytesRead)) {
int maxSearch = 1024; // picked because 512 is too little, and 2048 too much
int http1Index =
ByteBufUtil.indexOf(HTTP_1_X_BUF, in.slice(in.readerIndex(), min(in.readableBytes(), maxSearch)));
if (http1Index != -1) {
String chunk = in.toString(in.readerIndex(), http1Index - in.readerIndex(), CharsetUtil.US_ASCII);
throw connectionError(PROTOCOL_ERROR, "Unexpected HTTP/1.x request: %s", chunk);
}
String receivedBytes = hexDump(in, in.readerIndex(),
min(in.readableBytes(), clientPrefaceString.readableBytes()));
throw connectionError(PROTOCOL_ERROR, "HTTP/2 client preface string missing or corrupt. " +
"Hex dump for received bytes: %s", receivedBytes);
}
在一个异常的分支，通过 indexOf 搜索 HTTP_1_X_BUF 关键字，判断该种特定的错误类型。
在此处， haystack 参数的 readerIndex 肯定是 0，所以不会触发我遇到的问题。
2. ByteBufUtil.indexOf(ByteBuf needle, ByteBuf haystack) 的单元测试
又看了一下单元测试：
final ByteBuf needle = Unpooled.copiedBuffer("abc12", CharsetUtil.UTF_8);
haystack.readerIndex(1);
needle.readerIndex(1);
assertEquals(0, ByteBufUtil.indexOf(needle, haystack));
haystack.readerIndex(2);
needle.readerIndex(3);
assertEquals(1, ByteBufUtil.indexOf(needle, haystack));
haystack.readerIndex(1);
needle.readerIndex(2);
assertEquals(1, ByteBufUtil.indexOf(needle, haystack));
haystack.release();
从这部分来看，indexOf 的预期返回值就是“相对 index”。
这就有点儿绕晕了，那在 4.1.45.Final 这个单元测试是如何 pass 的？肯定报错呀。
翻了一下 commits 记录，发现该方法之前就没有单元测试，现在我看到的单元测试就是在代码优化时添加的：
3. ByteBufUtil.indexOf(ByteBuf needle, ByteBuf haystack) 的实现
看了一下现在的实现，说实话有点儿拉低 Netty 的代码质量，也不知道这个 pr 是如何 merge 进来的。
/**
* Returns the reader index of needle in haystack, or -1 if needle is not in haystack.
* This method uses the <a href="https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm">Two-Way
* string matching algorithm</a>, which yields O(1) space complexity and excellent performance.
*/
public static int indexOf(ByteBuf needle, ByteBuf haystack) {
if (haystack == null || needle == null) {
return -1;
}
if (needle.readableBytes() > haystack.readableBytes()) {
return -1;
}
int n = haystack.readableBytes();
int m = needle.readableBytes();
if (m == 0) {
return 0;
}
// When the needle has only one byte that can be read,
// the firstIndexOf method needs to be called
if (m == 1) {
return firstIndexOf((AbstractByteBuf) haystack, haystack.readerIndex(),
haystack.writerIndex(), needle.getByte(needle.readerIndex()));
}
int i;
int j = 0;
int aStartIndex = needle.readerIndex();
int bStartIndex = haystack.readerIndex();
long suffixes = maxSuf(needle, m, aStartIndex, true);
long prefixes = maxSuf(needle, m, aStartIndex, false);
int ell = Math.max((int) (suffixes >> 32), (int) (prefixes >> 32));
int per = Math.max((int) suffixes, (int) prefixes);
int memory;
int length = Math.min(m - per, ell + 1);
if (equals(needle, aStartIndex, needle, aStartIndex + per, length)) {
memory = -1;
while (j <= n - m) {
i = Math.max(ell, memory) + 1;
while (i < m && needle.getByte(i + aStartIndex) == haystack.getByte(i + j + bStartIndex)) {
++i;
}
if (i > n) {
return -1;
}
if (i >= m) {
i = ell;
while (i > memory && needle.getByte(i + aStartIndex) == haystack.getByte(i + j + bStartIndex)) {
--i;
}
if (i <= memory) {
return j;
}
j += per;
memory = m - per - 1;
} else {
j += i - ell;
memory = -1;
}
}
} else {
per = Math.max(ell + 1, m - ell - 1) + 1;
while (j <= n - m) {
i = ell + 1;
while (i < m && needle.getByte(i + aStartIndex) == haystack.getByte(i + j + bStartIndex)) {
++i;
}
if (i > n) {
return -1;
}
if (i >= m) {
i = ell;
while (i >= 0 && needle.getByte(i + aStartIndex) == haystack.getByte(i + j + bStartIndex)) {
--i;
}
if (i < 0) {
return j;
}
j += per;
} else {
j += i - ell;
}
}
}
return -1;
}
private static long maxSuf(ByteBuf x, int m, int start, boolean isSuffix) {
int p = 1;
int ms = -1;
int j = start;
int k = 1;
byte a;
byte b;
while (j + k < m) {
a = x.getByte(j + k);
b = x.getByte(ms + k);
boolean suffix = isSuffix ? a < b : a > b;
if (suffix) {
j += k;
k = 1;
p = j - ms;
} else if (a == b) {
if (k != p) {
++k;
} else {
j += p;
k = 1;
}
} else {
ms = j;
j = ms + 1;
k = p = 1;
}
}
return ((long) ms << 32) + p;
}
大部分情况确实返回的是“相对 index”，但是在 needle 长度为 1 的情况下，调用的是 ByteBuf 的 indexOf(int fromIndex, int toIndex, byte value) 方法，返回的是“绝对 index”。
再看之前 4.1.45.Final 版本的实现，是一个很简单的暴力搜索算法：
/**
* Returns the reader index of needle in haystack, or -1 if needle is not in haystack.
*/
public static int indexOf(ByteBuf needle, ByteBuf haystack) {
// TODO: maybe use Boyer Moore for efficiency.
int attempts = haystack.readableBytes() - needle.readableBytes() + 1;
for (int i = 0; i < attempts; i++) {
if (equals(needle, needle.readerIndex(),
haystack, haystack.readerIndex() + i,
needle.readableBytes())) {
return haystack.readerIndex() + i;
}
}
return -1;
}
返回的是“绝对 index”。
给 Netty 提了一个 issue，但是还没有回应。。。
4. 最后
是不是优秀的 Java 开发者都转别的语言了？以小见大，Netty 的代码质量真的是在下滑。
对一个开源项目来说，单元测试真是太重要了。
不过新的 Two-Way string matching algorithm 看起来还挺有趣，看 wikipedia 上的介绍，glibc 的 strstr 函数也是基于该算法实现的，并且还有 SSE2 硬件优化实现，接下来深入学习一下。
