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