1 /*
<lambda>null2 * Copyright (C) 2019 The Android Open Source Project
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
17 package com.android.net.module.util
18
19 import com.android.testutils.ConcurrentInterpreter
20 import com.android.testutils.InterpretException
21 import com.android.testutils.InterpretMatcher
22 import com.android.testutils.SyntaxException
23 import com.android.testutils.__FILE__
24 import com.android.testutils.__LINE__
25 import com.android.testutils.intArg
26 import com.android.testutils.strArg
27 import com.android.testutils.timeArg
28 import org.junit.Test
29 import org.junit.runner.RunWith
30 import org.junit.runners.JUnit4
31 import java.util.concurrent.CyclicBarrier
32 import java.util.concurrent.TimeUnit
33 import kotlin.system.measureTimeMillis
34 import kotlin.test.assertEquals
35 import kotlin.test.assertFailsWith
36 import kotlin.test.assertFalse
37 import kotlin.test.assertNotEquals
38 import kotlin.test.assertNull
39 import kotlin.test.assertTrue
40 import kotlin.test.fail
41
42 val TEST_VALUES = listOf(4, 13, 52, 94, 41, 68, 11, 13, 51, 0, 91, 94, 33, 98, 14)
43 const val ABSENT_VALUE = 2
44 // Caution in changing these : some tests rely on the fact that TEST_TIMEOUT > 2 * SHORT_TIMEOUT
45 // and LONG_TIMEOUT > 2 * TEST_TIMEOUT
46 const val SHORT_TIMEOUT = 40L // ms
47 const val TEST_TIMEOUT = 200L // ms
48 const val LONG_TIMEOUT = 5000L // ms
49
50 @RunWith(JUnit4::class)
51 class TrackRecordTest {
52 @Test
53 fun testAddAndSizeAndGet() {
54 val repeats = 22 // arbitrary
55 val record = ArrayTrackRecord<Int>()
56 assertEquals(0, record.size)
57 repeat(repeats) { i -> record.add(i + 2) }
58 assertEquals(repeats, record.size)
59 record.add(2)
60 assertEquals(repeats + 1, record.size)
61
62 assertEquals(11, record[9])
63 assertEquals(11, record.getOrNull(9))
64 assertEquals(2, record[record.size - 1])
65 assertEquals(2, record.getOrNull(record.size - 1))
66
67 assertFailsWith<IndexOutOfBoundsException> { record[800] }
68 assertFailsWith<IndexOutOfBoundsException> { record[-1] }
69 assertFailsWith<IndexOutOfBoundsException> { record[repeats + 1] }
70 assertNull(record.getOrNull(800))
71 assertNull(record.getOrNull(-1))
72 assertNull(record.getOrNull(repeats + 1))
73 assertNull(record.getOrNull(800) { true })
74 assertNull(record.getOrNull(-1) { true })
75 assertNull(record.getOrNull(repeats + 1) { true })
76 }
77
78 @Test
79 fun testIndexOf() {
80 val record = ArrayTrackRecord<Int>()
81 TEST_VALUES.forEach { record.add(it) }
82 with(record) {
83 assertEquals(9, indexOf(0))
84 assertEquals(9, lastIndexOf(0))
85 assertEquals(1, indexOf(13))
86 assertEquals(7, lastIndexOf(13))
87 assertEquals(3, indexOf(94))
88 assertEquals(11, lastIndexOf(94))
89 assertEquals(-1, indexOf(ABSENT_VALUE))
90 assertEquals(-1, lastIndexOf(ABSENT_VALUE))
91 }
92 }
93
94 @Test
95 fun testContains() {
96 val record = ArrayTrackRecord<Int>()
97 TEST_VALUES.forEach { record.add(it) }
98 TEST_VALUES.forEach { assertTrue(record.contains(it)) }
99 assertFalse(record.contains(ABSENT_VALUE))
100 assertTrue(record.containsAll(TEST_VALUES))
101 assertTrue(record.containsAll(TEST_VALUES.sorted()))
102 assertTrue(record.containsAll(TEST_VALUES.sortedDescending()))
103 assertTrue(record.containsAll(TEST_VALUES.distinct()))
104 assertTrue(record.containsAll(TEST_VALUES.subList(0, TEST_VALUES.size / 2)))
105 assertTrue(record.containsAll(TEST_VALUES.subList(0, TEST_VALUES.size / 2).sorted()))
106 assertTrue(record.containsAll(listOf()))
107 assertFalse(record.containsAll(listOf(ABSENT_VALUE)))
108 assertFalse(record.containsAll(TEST_VALUES + listOf(ABSENT_VALUE)))
109 }
110
111 @Test
112 fun testEmpty() {
113 val record = ArrayTrackRecord<Int>()
114 assertTrue(record.isEmpty())
115 record.add(1)
116 assertFalse(record.isEmpty())
117 }
118
119 @Test
120 fun testIterate() {
121 val record = ArrayTrackRecord<Int>()
122 record.forEach { fail("Expected nothing to iterate") }
123 TEST_VALUES.forEach { record.add(it) }
124 // zip relies on the iterator (this calls extension function Iterable#zip(Iterable))
125 record.zip(TEST_VALUES).forEach { assertEquals(it.first, it.second) }
126 // Also test reverse iteration (to test hasPrevious() and friends)
127 record.reversed().zip(TEST_VALUES.reversed()).forEach { assertEquals(it.first, it.second) }
128 }
129
130 @Test
131 fun testIteratorIsSnapshot() {
132 val record = ArrayTrackRecord<Int>()
133 TEST_VALUES.forEach { record.add(it) }
134 val iterator = record.iterator()
135 val expectedSize = record.size
136 record.add(ABSENT_VALUE)
137 record.add(ABSENT_VALUE)
138 var measuredSize = 0
139 iterator.forEach {
140 ++measuredSize
141 assertNotEquals(ABSENT_VALUE, it)
142 }
143 assertEquals(expectedSize, measuredSize)
144 }
145
146 @Test
147 fun testSublist() {
148 val record = ArrayTrackRecord<Int>()
149 TEST_VALUES.forEach { record.add(it) }
150 assertEquals(record.subList(3, record.size - 3),
151 TEST_VALUES.subList(3, TEST_VALUES.size - 3))
152 }
153
154 fun testPollReturnsImmediately(record: TrackRecord<Int>) {
155 record.add(4)
156 val elapsed = measureTimeMillis { assertEquals(4, record.poll(LONG_TIMEOUT, 0)) }
157 // Should not have waited at all, in fact.
158 assertTrue(elapsed < LONG_TIMEOUT)
159 record.add(7)
160 record.add(9)
161 // Can poll multiple times for the same position, in whatever order
162 assertEquals(9, record.poll(0, 2))
163 assertEquals(7, record.poll(Long.MAX_VALUE, 1))
164 assertEquals(9, record.poll(0, 2))
165 assertEquals(4, record.poll(0, 0))
166 assertEquals(9, record.poll(0, 2) { it > 5 })
167 assertEquals(7, record.poll(0, 0) { it > 5 })
168 }
169
170 @Test
171 fun testPollReturnsImmediately() {
172 testPollReturnsImmediately(ArrayTrackRecord())
173 testPollReturnsImmediately(ArrayTrackRecord<Int>().newReadHead())
174 }
175
176 @Test
177 fun testPollTimesOut() {
178 val record = ArrayTrackRecord<Int>()
179 var delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0)) }
180 assertTrue(delay >= SHORT_TIMEOUT, "Delay $delay < $SHORT_TIMEOUT")
181 delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0) { it < 10 }) }
182 assertTrue(delay >= SHORT_TIMEOUT)
183 }
184
185 @Test
186 fun testPollWakesUp() {
187 val record = ArrayTrackRecord<Int>()
188 val barrier = CyclicBarrier(2)
189 Thread {
190 barrier.await(LONG_TIMEOUT, TimeUnit.MILLISECONDS) // barrier 1
191 barrier.await() // barrier 2
192 Thread.sleep(SHORT_TIMEOUT * 2)
193 record.add(31)
194 }.start()
195 barrier.await() // barrier 1
196 // Should find the element in more than SHORT_TIMEOUT but less than TEST_TIMEOUT
197 var delay = measureTimeMillis {
198 barrier.await() // barrier 2
199 assertEquals(31, record.poll(TEST_TIMEOUT, 0))
200 }
201 assertTrue(delay in SHORT_TIMEOUT..TEST_TIMEOUT)
202 // Polling for an element already added in anothe thread (pos 0) : should return immediately
203 delay = measureTimeMillis { assertEquals(31, record.poll(TEST_TIMEOUT, 0)) }
204 assertTrue(delay < TEST_TIMEOUT, "Delay $delay > $TEST_TIMEOUT")
205 // Waiting for an element that never comes
206 delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 1)) }
207 assertTrue(delay >= SHORT_TIMEOUT, "Delay $delay < $SHORT_TIMEOUT")
208 // Polling for an element that doesn't match what is already there
209 delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0) { it < 10 }) }
210 assertTrue(delay >= SHORT_TIMEOUT)
211 }
212
213 // Just make sure the interpreter actually throws an exception when the spec
214 // does not conform to the behavior. The interpreter is just a tool to test a
215 // tool used for a tool for test, let's not have hundreds of tests for it ;
216 // if it's broken one of the tests using it will break.
217 @Test
218 fun testInterpreter() {
219 val interpretLine = __LINE__ + 2
220 try {
221 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
222 add(4) | poll(1, 0) = 5
223 """)
224 fail("This spec should have thrown")
225 } catch (e: InterpretException) {
226 assertTrue(e.cause is AssertionError)
227 assertEquals(interpretLine + 1, e.stackTrace[0].lineNumber)
228 assertTrue(e.stackTrace[0].fileName.contains(__FILE__))
229 assertTrue(e.stackTrace[0].methodName.contains("testInterpreter"))
230 assertTrue(e.stackTrace[0].methodName.contains("thread1"))
231 }
232 }
233
234 @Test
235 fun testMultipleAdds() {
236 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
237 add(2) | | |
238 | add(4) | |
239 | | add(6) |
240 | | | add(8)
241 poll(0, 0) = 2 time 0..1 | poll(0, 0) = 2 | poll(0, 0) = 2 | poll(0, 0) = 2
242 poll(0, 1) = 4 time 0..1 | poll(0, 1) = 4 | poll(0, 1) = 4 | poll(0, 1) = 4
243 poll(0, 2) = 6 time 0..1 | poll(0, 2) = 6 | poll(0, 2) = 6 | poll(0, 2) = 6
244 poll(0, 3) = 8 time 0..1 | poll(0, 3) = 8 | poll(0, 3) = 8 | poll(0, 3) = 8
245 """)
246 }
247
248 @Test
249 fun testConcurrentAdds() {
250 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
251 add(2) | add(4) | add(6) | add(8)
252 add(1) | add(3) | add(5) | add(7)
253 poll(0, 1) is even | poll(0, 0) is even | poll(0, 3) is even | poll(0, 2) is even
254 poll(0, 5) is odd | poll(0, 4) is odd | poll(0, 7) is odd | poll(0, 6) is odd
255 """)
256 }
257
258 @Test
259 fun testMultiplePoll() {
260 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
261 add(4) | poll(1, 0) = 4
262 | poll(0, 1) = null time 0..1
263 | poll(1, 1) = null time 1..2
264 sleep; add(7) | poll(2, 1) = 7 time 1..2
265 sleep; add(18) | poll(2, 2) = 18 time 1..2
266 """)
267 }
268
269 @Test
270 fun testMultiplePollWithPredicate() {
271 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
272 | poll(1, 0) = null | poll(1, 0) = null
273 add(6) | poll(1, 0) = 6 |
274 add(11) | poll(1, 0) { > 20 } = null | poll(1, 0) { = 11 } = 11
275 | poll(1, 0) { > 8 } = 11 |
276 """)
277 }
278
279 @Test
280 fun testMultipleReadHeads() {
281 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
282 | poll() = null | poll() = null | poll() = null
283 add(5) | | poll() = 5 |
284 | poll() = 5 | |
285 add(8) | poll() = 8 | poll() = 8 |
286 | | | poll() = 5
287 | | | poll() = 8
288 | | | poll() = null
289 | | poll() = null |
290 """)
291 }
292
293 @Test
294 fun testReadHeadPollWithPredicate() {
295 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
296 add(5) | poll() { < 0 } = null
297 | poll() { > 5 } = null
298 add(10) |
299 | poll() { = 5 } = null // The "5" was skipped in the previous line
300 add(15) | poll() { > 8 } = 15 // The "10" was skipped in the previous line
301 | poll(1, 0) { > 8 } = 10 // 10 is the first element after pos 0 matching > 8
302 """)
303 }
304
305 @Test
306 fun testPollImmediatelyAdvancesReadhead() {
307 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
308 add(1) | add(2) | add(3) | add(4)
309 mark = 0 | poll(0) { > 3 } = 4 | |
310 poll(0) { > 10 } = null | | |
311 mark = 4 | | |
312 poll() = null | | |
313 """)
314 }
315
316 @Test
317 fun testParallelReadHeads() {
318 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
319 mark = 0 | mark = 0 | mark = 0 | mark = 0
320 add(2) | | |
321 | add(4) | |
322 | | add(6) |
323 | | | add(8)
324 poll() = 2 | poll() = 2 | poll() = 2 | poll() = 2
325 poll() = 4 | poll() = 4 | poll() = 4 | poll() = 4
326 poll() = 6 | poll() = 6 | poll() = 6 | mark = 2
327 poll() = 8 | poll() = 8 | mark = 3 | poll() = 6
328 mark = 4 | mark = 4 | poll() = 8 | poll() = 8
329 """)
330 }
331
332 @Test
333 fun testPeek() {
334 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
335 add(2) | | |
336 | add(4) | |
337 | | add(6) |
338 | | | add(8)
339 peek() = 2 | poll() = 2 | poll() = 2 | peek() = 2
340 peek() = 2 | peek() = 4 | poll() = 4 | peek() = 2
341 peek() = 2 | peek() = 4 | peek() = 6 | poll() = 2
342 peek() = 2 | mark = 1 | mark = 2 | poll() = 4
343 mark = 0 | peek() = 4 | peek() = 6 | peek() = 6
344 poll() = 2 | poll() = 4 | poll() = 6 | poll() = 6
345 poll() = 4 | mark = 2 | poll() = 8 | peek() = 8
346 peek() = 6 | peek() = 6 | peek() = null | mark = 3
347 """)
348 }
349 }
350
351 private object TRTInterpreter : ConcurrentInterpreter<TrackRecord<Int>>(interpretTable) {
interpretTestSpecnull352 fun interpretTestSpec(spec: String, useReadHeads: Boolean) = if (useReadHeads) {
353 interpretTestSpec(spec, initial = ArrayTrackRecord(),
354 threadTransform = { (it as ArrayTrackRecord).newReadHead() })
355 } else {
356 interpretTestSpec(spec, ArrayTrackRecord())
357 }
358 }
359
360 /*
361 * Quick ref of supported expressions :
362 * sleep(x) : sleeps for x time units and returns Unit ; sleep alone means sleep(1)
363 * add(x) : calls and returns TrackRecord#add.
364 * poll(time, pos) [{ predicate }] : calls and returns TrackRecord#poll(x time units, pos).
365 * Optionally, a predicate may be specified.
366 * poll() [{ predicate }] : calls and returns ReadHead#poll(1 time unit). Optionally, a predicate
367 * may be specified.
368 * EXPR = VALUE : asserts that EXPR equals VALUE. EXPR is interpreted. VALUE can either be the
369 * string "null" or an int. Returns Unit.
370 * EXPR time x..y : measures the time taken by EXPR and asserts it took at least x and at most
371 * y time units.
372 * predicate must be one of "= x", "< x" or "> x".
373 */
374 private val interpretTable = listOf<InterpretMatcher<TrackRecord<Int>>>(
375 // Interpret "XXX is odd" : run XXX and assert its return value is odd ("even" works too)
rnull376 Regex("(.*)\\s+is\\s+(even|odd)") to { i, t, r ->
377 i.interpret(r.strArg(1), t).also {
378 assertEquals((it as Int) % 2, if ("even" == r.strArg(2)) 0 else 1)
379 }
380 },
381 // Interpret "add(XXX)" as TrackRecord#add(int)
rnull382 Regex("""add\((\d+)\)""") to { i, t, r ->
383 t.add(r.intArg(1))
384 },
385 // Interpret "poll(x, y)" as TrackRecord#poll(timeout = x * INTERPRET_TIME_UNIT, pos = y)
386 // Accepts an optional {} argument for the predicate (see makePredicate for syntax)
rnull387 Regex("""poll\((\d+),\s*(\d+)\)\s*(\{.*\})?""") to { i, t, r ->
388 t.poll(r.timeArg(1), r.intArg(2), makePredicate(r.strArg(3)))
389 },
390 // ReadHead#poll. If this throws in the cast, the code is malformed and has passed "poll()"
391 // in a test that takes a TrackRecord that is not a ReadHead. It's technically possible to get
392 // the test code to not compile instead of throw, but it's vastly more complex and this will
393 // fail 100% at runtime any test that would not have compiled.
rnull394 Regex("""poll\((\d+)?\)\s*(\{.*\})?""") to { i, t, r ->
395 (if (r.strArg(1).isEmpty()) i.interpretTimeUnit else r.timeArg(1)).let { time ->
396 (t as ArrayTrackRecord<Int>.ReadHead).poll(time, makePredicate(r.strArg(2)))
397 }
398 },
399 // ReadHead#mark. The same remarks apply as with ReadHead#poll.
tnull400 Regex("mark") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).mark },
401 // ReadHead#peek. The same remarks apply as with ReadHead#poll.
tnull402 Regex("peek\\(\\)") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).peek() }
403 )
404
405 // Parses a { = x } or { < x } or { > x } string and returns the corresponding predicate
406 // Returns an always-true predicate for empty and null arguments
makePredicatenull407 private fun makePredicate(spec: String?): (Int) -> Boolean {
408 if (spec.isNullOrEmpty()) return { true }
409 val match = Regex("""\{\s*([<>=])\s*(\d+)\s*\}""").matchEntire(spec)
410 ?: throw SyntaxException("Predicate \"${spec}\"")
411 val arg = match.intArg(2)
412 return when (match.strArg(1)) {
413 ">" -> { i -> i > arg }
414 "<" -> { i -> i < arg }
415 "=" -> { i -> i == arg }
416 else -> throw RuntimeException("How did \"${spec}\" match this regexp ?")
417 }
418 }
419