okhttp

1
/*
2
 * Copyright (C) 2023 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 okhttp3.internal.idn
17

18
import kotlin.math.abs
19
import kotlin.streams.toList
20
import okio.Buffer
21

22
/** Index [table] for compactness as specified by `IdnaMappingTable`. */
23
fun buildIdnaMappingTableData(table: SimpleIdnaMappingTable): IdnaMappingTableData {
24
  val simplified = mergeAdjacentRanges(table.mappings)
25
  val withoutSectionSpans = withoutSectionSpans(simplified)
26
  val sections = sections(withoutSectionSpans)
27

28
  val rangesBuffer = Buffer()
29
  val mappingsBuffer = StringBuilder()
30
  val sectionIndexBuffer = Buffer()
31

32
  var previousMappedRanges: List<MappedRange>? = null
33

34
  for ((section, sectionMappedRanges) in sections) {
35
    // Skip sequential ranges when they are equal.
36
    if (sectionMappedRanges == previousMappedRanges) continue
37
    previousMappedRanges = sectionMappedRanges
38

39
    val sectionOffset = rangesBuffer.size.toInt() / 4
40

41
    // Section prefix.
42
    sectionIndexBuffer.writeByte(section and 0x1fc000 shr 14)
43
    sectionIndexBuffer.writeByte((section and 0x3f80) shr 7)
44

45
    // Section index.
46
    sectionIndexBuffer.writeByte((sectionOffset and 0x3f80) shr 7)
47
    sectionIndexBuffer.writeByte(sectionOffset and 0x7f)
48

49
    // Ranges.
50
    for (range in sectionMappedRanges) {
51
      rangesBuffer.writeByte(range.rangeStart)
52

53
      when (range) {
54
        is MappedRange.Constant -> {
55
          rangesBuffer.writeByte(range.b1)
56
          rangesBuffer.writeByte('-'.code)
57
          rangesBuffer.writeByte('-'.code)
58
        }
59
        is MappedRange.Inline1 -> {
60
          rangesBuffer.writeByte(range.b1)
61
          rangesBuffer.writeByte(range.b2)
62
          rangesBuffer.writeByte('-'.code)
63
        }
64
        is MappedRange.Inline2 -> {
65
          rangesBuffer.writeByte(range.b1)
66
          rangesBuffer.writeByte(range.b2)
67
          rangesBuffer.writeByte(range.b3)
68
        }
69
        is MappedRange.InlineDelta -> {
70
          rangesBuffer.writeByte(range.b1)
71
          rangesBuffer.writeByte(range.b2)
72
          rangesBuffer.writeByte(range.b3)
73
        }
74
        is MappedRange.External -> {
75
          // Write the mapping.
76
          val mappingOffset: Int
77
          val mappedTo = range.mappedTo.utf8()
78
          val mappingIndex = mappingsBuffer.indexOf(mappedTo)
79
          if (mappingIndex == -1) {
80
            mappingOffset = mappingsBuffer.length
81
            mappingsBuffer.append(mappedTo)
82
          } else {
83
            mappingOffset = mappingIndex
84
          }
85

86
          // Write the range bytes.
87
          val b1 = mappedTo.length
88
          val b2 = (mappingOffset and 0x3f80) shr 7
89
          val b3 = mappingOffset and 0x7f
90
          rangesBuffer.writeByte(b1)
91
          rangesBuffer.writeByte(b2)
92
          rangesBuffer.writeByte(b3)
93
        }
94
      }
95
    }
96
  }
97

98
  return IdnaMappingTableData(
99
    sections = sectionIndexBuffer.readUtf8(),
100
    ranges = rangesBuffer.readUtf8(),
101
    mappings = mappingsBuffer.toString(),
102
  )
103
}
104

105
/**
106
 * If [mapping] qualifies to be encoded as [MappedRange.InlineDelta] return new instance, otherwise null.
107
 * An [MappedRange.InlineDelta] must be a mapping from a single code-point to a single code-point with a difference
108
 * that can be represented in 2^18-1.
109
 */
110
internal fun inlineDeltaOrNull(mapping: Mapping): MappedRange.InlineDelta? {
111
  if (mapping.hasSingleSourceCodePoint) {
112
    val sourceCodePoint = mapping.sourceCodePoint0
113
    val mappedCodePoints = mapping.mappedTo.utf8().codePoints().toList()
114
    if (mappedCodePoints.size == 1) {
115
      val codePointDelta = mappedCodePoints.single() - sourceCodePoint
116
      if (MappedRange.InlineDelta.MAX_VALUE >= abs(codePointDelta)) {
117
        return MappedRange.InlineDelta(mapping.rangeStart, codePointDelta)
118
      }
119
    }
120
  }
121
  return null
122
}
123

124
/**
125
 * Inputs must have applied [withoutSectionSpans].
126
 */
127
internal fun sections(mappings: List<Mapping>): Map<Int, List<MappedRange>> {
128
  val result = mutableMapOf<Int, MutableList<MappedRange>>()
129

130
  for (mapping in mappings) {
131
    require(!mapping.spansSections)
132

133
    val section = mapping.section
134
    val rangeStart = mapping.rangeStart
135

136
    val sectionList = result.getOrPut(section) { mutableListOf() }
137

138
    sectionList +=
139
      when (mapping.type) {
140
        TYPE_MAPPED ->
141
          run {
142
            val deltaMapping = inlineDeltaOrNull(mapping)
143
            if (deltaMapping != null) {
144
              return@run deltaMapping
145
            }
146

147
            when (mapping.mappedTo.size) {
148
              1 -> MappedRange.Inline1(rangeStart, mapping.mappedTo)
149
              2 -> MappedRange.Inline2(rangeStart, mapping.mappedTo)
150
              else -> MappedRange.External(rangeStart, mapping.mappedTo)
151
            }
152
          }
153

154
        TYPE_IGNORED, TYPE_VALID, TYPE_DISALLOWED -> {
155
          MappedRange.Constant(rangeStart, mapping.type)
156
        }
157

158
        else -> error("unexpected mapping type: ${mapping.type}")
159
      }
160
  }
161

162
  for (sectionList in result.values) {
163
    mergeAdjacentDeltaMappedRanges(sectionList)
164
  }
165

166
  return result.toMap()
167
}
168

169
/**
170
 * Modifies [ranges] to combine any adjacent [MappedRange.InlineDelta] of same size to single entry.
171
 * @returns same instance of [ranges] for convenience
172
 */
173
internal fun mergeAdjacentDeltaMappedRanges(ranges: MutableList<MappedRange>): MutableList<MappedRange> {
174
  var i = 0
175
  while (i < ranges.size) {
176
    val curr = ranges[i]
177
    if (curr is MappedRange.InlineDelta) {
178
      val j = i + 1
179
      mergeAdjacent@ while (j < ranges.size) {
180
        val next = ranges[j]
181
        if (next is MappedRange.InlineDelta &&
182
          curr.codepointDelta == next.codepointDelta
183
        ) {
184
          ranges.removeAt(j)
185
        } else {
186
          break@mergeAdjacent
187
        }
188
      }
189
    }
190
    i++
191
  }
192
  return ranges
193
}
194

195
/**
196
 * Returns a copy of [mappings], splitting to ensure that each mapping is entirely contained within
197
 * a single section.
198
 */
199
internal fun withoutSectionSpans(mappings: List<Mapping>): List<Mapping> {
200
  val result = mutableListOf<Mapping>()
201

202
  val i = mappings.iterator()
203
  var current = i.next()
204

205
  while (true) {
206
    if (current.spansSections) {
207
      result +=
208
        Mapping(
209
          current.sourceCodePoint0,
210
          current.section + 0x7f,
211
          current.type,
212
          current.mappedTo,
213
        )
214
      current =
215
        Mapping(
216
          current.section + 0x80,
217
          current.sourceCodePoint1,
218
          current.type,
219
          current.mappedTo,
220
        )
221
    } else {
222
      result += current
223
      current = if (i.hasNext()) i.next() else break
224
    }
225
  }
226

227
  return result
228
}
229

230
/** Returns a copy of [mappings] with adjacent ranges merged wherever possible. */
231
internal fun mergeAdjacentRanges(mappings: List<Mapping>): List<Mapping> {
232
  var index = 0
233
  val result = mutableListOf<Mapping>()
234

235
  while (index < mappings.size) {
236
    val mapping = mappings[index]
237
    val type = canonicalizeType(mapping.type)
238
    val mappedTo = mapping.mappedTo
239

240
    var unionWith: Mapping = mapping
241
    index++
242

243
    while (index < mappings.size) {
244
      val next = mappings[index]
245

246
      if (type != canonicalizeType(next.type)) break
247
      if (type == TYPE_MAPPED && mappedTo != next.mappedTo) break
248

249
      unionWith = next
250
      index++
251
    }
252

253
    result +=
254
      Mapping(
255
        sourceCodePoint0 = mapping.sourceCodePoint0,
256
        sourceCodePoint1 = unionWith.sourceCodePoint1,
257
        type = type,
258
        mappedTo = mappedTo,
259
      )
260
  }
261

262
  return result
263
}
264

265
internal fun canonicalizeType(type: Int): Int {
266
  return when (type) {
267
    TYPE_IGNORED -> TYPE_IGNORED
268

269
    TYPE_MAPPED,
270
    TYPE_DISALLOWED_STD3_MAPPED,
271
    -> TYPE_MAPPED
272

273
    TYPE_DEVIATION,
274
    TYPE_DISALLOWED_STD3_VALID,
275
    TYPE_VALID,
276
    -> TYPE_VALID
277

278
    TYPE_DISALLOWED -> TYPE_DISALLOWED
279

280
    else -> error("unexpected type: $type")
281
  }
282
}
283

284
internal infix fun Byte.and(mask: Int): Int = toInt() and mask
285

286
internal infix fun Short.and(mask: Int): Int = toInt() and mask
287

288
internal infix fun Int.and(mask: Long): Long = toLong() and mask
289