1 /* <lambda>null2 * Copyright (C) 2016 Square, Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 package okio 17 18 import kotlin.jvm.JvmStatic 19 20 /** An indexed set of values that may be read with [BufferedSource.select]. */ 21 class Options private constructor( 22 internal val byteStrings: Array<out ByteString>, 23 internal val trie: IntArray, 24 ) : AbstractList<ByteString>(), RandomAccess { 25 26 override val size: Int 27 get() = byteStrings.size 28 29 override fun get(index: Int) = byteStrings[index] 30 31 companion object { 32 @JvmStatic 33 fun of(vararg byteStrings: ByteString): Options { 34 if (byteStrings.isEmpty()) { 35 // With no choices we must always return -1. Create a trie that selects from an empty set. 36 return Options(arrayOf(), intArrayOf(0, -1)) 37 } 38 39 // Sort the byte strings which is required when recursively building the trie. Map the sorted 40 // indexes to the caller's indexes. 41 val list = byteStrings.toMutableList() 42 list.sort() 43 val indexes = mutableListOf(*byteStrings.map { -1 }.toTypedArray()) 44 byteStrings.forEachIndexed { callerIndex, byteString -> 45 val sortedIndex = list.binarySearch(byteString) 46 indexes[sortedIndex] = callerIndex 47 } 48 require(list[0].size > 0) { "the empty byte string is not a supported option" } 49 50 // Strip elements that will never be returned because they follow their own prefixes. For 51 // example, if the caller provides ["abc", "abcde"] we will never return "abcde" because we 52 // return as soon as we encounter "abc". 53 var a = 0 54 while (a < list.size) { 55 val prefix = list[a] 56 var b = a + 1 57 while (b < list.size) { 58 val byteString = list[b] 59 if (!byteString.startsWith(prefix)) break 60 require(byteString.size != prefix.size) { "duplicate option: $byteString" } 61 if (indexes[b] > indexes[a]) { 62 list.removeAt(b) 63 indexes.removeAt(b) 64 } else { 65 b++ 66 } 67 } 68 a++ 69 } 70 71 val trieBytes = Buffer() 72 buildTrieRecursive(node = trieBytes, byteStrings = list, indexes = indexes) 73 74 val trie = IntArray(trieBytes.intCount.toInt()) 75 var i = 0 76 while (!trieBytes.exhausted()) { 77 trie[i++] = trieBytes.readInt() 78 } 79 80 return Options(byteStrings.copyOf() /* Defensive copy. */, trie) 81 } 82 83 /** 84 * Builds a trie encoded as an int array. Nodes in the trie are of two types: SELECT and SCAN. 85 * 86 * SELECT nodes are encoded as: 87 * - selectChoiceCount: the number of bytes to choose between (a positive int) 88 * - prefixIndex: the result index at the current position or -1 if the current position is not 89 * a result on its own 90 * - a sorted list of selectChoiceCount bytes to match against the input string 91 * - a heterogeneous list of selectChoiceCount result indexes (>= 0) or offsets (< 0) of the 92 * next node to follow. Elements in this list correspond to elements in the preceding list. 93 * Offsets are negative and must be multiplied by -1 before being used. 94 * 95 * SCAN nodes are encoded as: 96 * - scanByteCount: the number of bytes to match in sequence. This count is negative and must 97 * be multiplied by -1 before being used. 98 * - prefixIndex: the result index at the current position or -1 if the current position is not 99 * a result on its own 100 * - a list of scanByteCount bytes to match 101 * - nextStep: the result index (>= 0) or offset (< 0) of the next node to follow. Offsets are 102 * negative and must be multiplied by -1 before being used. 103 * 104 * This structure is used to improve locality and performance when selecting from a list of 105 * options. 106 */ 107 private fun buildTrieRecursive( 108 nodeOffset: Long = 0L, 109 node: Buffer, 110 byteStringOffset: Int = 0, 111 byteStrings: List<ByteString>, 112 fromIndex: Int = 0, 113 toIndex: Int = byteStrings.size, 114 indexes: List<Int>, 115 ) { 116 require(fromIndex < toIndex) 117 for (i in fromIndex until toIndex) { 118 require(byteStrings[i].size >= byteStringOffset) 119 } 120 121 var fromIndex = fromIndex 122 var from = byteStrings[fromIndex] 123 val to = byteStrings[toIndex - 1] 124 var prefixIndex = -1 125 126 // If the first element is already matched, that's our prefix. 127 if (byteStringOffset == from.size) { 128 prefixIndex = indexes[fromIndex] 129 fromIndex++ 130 from = byteStrings[fromIndex] 131 } 132 133 if (from[byteStringOffset] != to[byteStringOffset]) { 134 // If we have multiple bytes to choose from, encode a SELECT node. 135 var selectChoiceCount = 1 136 for (i in fromIndex + 1 until toIndex) { 137 if (byteStrings[i - 1][byteStringOffset] != byteStrings[i][byteStringOffset]) { 138 selectChoiceCount++ 139 } 140 } 141 142 // Compute the offset that childNodes will get when we append it to node. 143 val childNodesOffset = nodeOffset + node.intCount + 2 + (selectChoiceCount * 2) 144 145 node.writeInt(selectChoiceCount) 146 node.writeInt(prefixIndex) 147 148 for (i in fromIndex until toIndex) { 149 val rangeByte = byteStrings[i][byteStringOffset] 150 if (i == fromIndex || rangeByte != byteStrings[i - 1][byteStringOffset]) { 151 node.writeInt(rangeByte and 0xff) 152 } 153 } 154 155 val childNodes = Buffer() 156 var rangeStart = fromIndex 157 while (rangeStart < toIndex) { 158 val rangeByte = byteStrings[rangeStart][byteStringOffset] 159 var rangeEnd = toIndex 160 for (i in rangeStart + 1 until toIndex) { 161 if (rangeByte != byteStrings[i][byteStringOffset]) { 162 rangeEnd = i 163 break 164 } 165 } 166 167 if (rangeStart + 1 == rangeEnd && 168 byteStringOffset + 1 == byteStrings[rangeStart].size 169 ) { 170 // The result is a single index. 171 node.writeInt(indexes[rangeStart]) 172 } else { 173 // The result is another node. 174 node.writeInt(-1 * (childNodesOffset + childNodes.intCount).toInt()) 175 buildTrieRecursive( 176 nodeOffset = childNodesOffset, 177 node = childNodes, 178 byteStringOffset = byteStringOffset + 1, 179 byteStrings = byteStrings, 180 fromIndex = rangeStart, 181 toIndex = rangeEnd, 182 indexes = indexes, 183 ) 184 } 185 186 rangeStart = rangeEnd 187 } 188 189 node.writeAll(childNodes) 190 } else { 191 // If all of the bytes are the same, encode a SCAN node. 192 var scanByteCount = 0 193 for (i in byteStringOffset until minOf(from.size, to.size)) { 194 if (from[i] == to[i]) { 195 scanByteCount++ 196 } else { 197 break 198 } 199 } 200 201 // Compute the offset that childNodes will get when we append it to node. 202 val childNodesOffset = nodeOffset + node.intCount + 2 + scanByteCount + 1 203 204 node.writeInt(-scanByteCount) 205 node.writeInt(prefixIndex) 206 207 for (i in byteStringOffset until byteStringOffset + scanByteCount) { 208 node.writeInt(from[i] and 0xff) 209 } 210 211 if (fromIndex + 1 == toIndex) { 212 // The result is a single index. 213 check(byteStringOffset + scanByteCount == byteStrings[fromIndex].size) 214 node.writeInt(indexes[fromIndex]) 215 } else { 216 // The result is another node. 217 val childNodes = Buffer() 218 node.writeInt(-1 * (childNodesOffset + childNodes.intCount).toInt()) 219 buildTrieRecursive( 220 nodeOffset = childNodesOffset, 221 node = childNodes, 222 byteStringOffset = byteStringOffset + scanByteCount, 223 byteStrings = byteStrings, 224 fromIndex = fromIndex, 225 toIndex = toIndex, 226 indexes = indexes, 227 ) 228 node.writeAll(childNodes) 229 } 230 } 231 } 232 233 private val Buffer.intCount get() = size / 4 234 } 235 } 236