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 android.net.testutils
18
19 import com.android.testutils.ArrayTrackRecord
20 import com.android.testutils.ConcurrentIntepreter
21 import com.android.testutils.InterpretException
22 import com.android.testutils.InterpretMatcher
23 import com.android.testutils.SyntaxException
24 import com.android.testutils.TrackRecord
25 import com.android.testutils.__FILE__
26 import com.android.testutils.__LINE__
27 import com.android.testutils.intArg
28 import com.android.testutils.strArg
29 import com.android.testutils.timeArg
30 import org.junit.Test
31 import org.junit.runner.RunWith
32 import org.junit.runners.JUnit4
33 import java.util.concurrent.CyclicBarrier
34 import java.util.concurrent.TimeUnit
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 testPollWakesUp() {
189 val record = ArrayTrackRecord<Int>()
190 val barrier = CyclicBarrier(2)
191 Thread {
192 barrier.await(LONG_TIMEOUT, TimeUnit.MILLISECONDS) // barrier 1
193 barrier.await() // barrier 2
194 Thread.sleep(SHORT_TIMEOUT * 2)
195 record.add(31)
196 }.start()
197 barrier.await() // barrier 1
198 // Should find the element in more than SHORT_TIMEOUT but less than TEST_TIMEOUT
199 var delay = measureTimeMillis {
200 barrier.await() // barrier 2
201 assertEquals(31, record.poll(TEST_TIMEOUT, 0))
202 }
203 assertTrue(delay in SHORT_TIMEOUT..TEST_TIMEOUT)
204 // Polling for an element already added in anothe thread (pos 0) : should return immediately
205 delay = measureTimeMillis { assertEquals(31, record.poll(TEST_TIMEOUT, 0)) }
206 assertTrue(delay < TEST_TIMEOUT, "Delay $delay > $TEST_TIMEOUT")
207 // Waiting for an element that never comes
208 delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 1)) }
209 assertTrue(delay >= SHORT_TIMEOUT, "Delay $delay < $SHORT_TIMEOUT")
210 // Polling for an element that doesn't match what is already there
211 delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0) { it < 10 }) }
212 assertTrue(delay >= SHORT_TIMEOUT)
213 }
214
215 // Just make sure the interpreter actually throws an exception when the spec
216 // does not conform to the behavior. The interpreter is just a tool to test a
217 // tool used for a tool for test, let's not have hundreds of tests for it ;
218 // if it's broken one of the tests using it will break.
219 @Test
220 fun testInterpreter() {
221 val interpretLine = __LINE__ + 2
222 try {
223 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
224 add(4) | poll(1, 0) = 5
225 """)
226 fail("This spec should have thrown")
227 } catch (e: InterpretException) {
228 assertTrue(e.cause is AssertionError)
229 assertEquals(interpretLine + 1, e.stackTrace[0].lineNumber)
230 assertTrue(e.stackTrace[0].fileName.contains(__FILE__))
231 assertTrue(e.stackTrace[0].methodName.contains("testInterpreter"))
232 assertTrue(e.stackTrace[0].methodName.contains("thread1"))
233 }
234 }
235
236 @Test
237 fun testMultipleAdds() {
238 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
239 add(2) | | |
240 | add(4) | |
241 | | add(6) |
242 | | | add(8)
243 poll(0, 0) = 2 time 0..1 | poll(0, 0) = 2 | poll(0, 0) = 2 | poll(0, 0) = 2
244 poll(0, 1) = 4 time 0..1 | poll(0, 1) = 4 | poll(0, 1) = 4 | poll(0, 1) = 4
245 poll(0, 2) = 6 time 0..1 | poll(0, 2) = 6 | poll(0, 2) = 6 | poll(0, 2) = 6
246 poll(0, 3) = 8 time 0..1 | poll(0, 3) = 8 | poll(0, 3) = 8 | poll(0, 3) = 8
247 """)
248 }
249
250 @Test
251 fun testConcurrentAdds() {
252 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
253 add(2) | add(4) | add(6) | add(8)
254 add(1) | add(3) | add(5) | add(7)
255 poll(0, 1) is even | poll(0, 0) is even | poll(0, 3) is even | poll(0, 2) is even
256 poll(0, 5) is odd | poll(0, 4) is odd | poll(0, 7) is odd | poll(0, 6) is odd
257 """)
258 }
259
260 @Test
261 fun testMultiplePoll() {
262 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
263 add(4) | poll(1, 0) = 4
264 | poll(0, 1) = null time 0..1
265 | poll(1, 1) = null time 1..2
266 sleep; add(7) | poll(2, 1) = 7 time 1..2
267 sleep; add(18) | poll(2, 2) = 18 time 1..2
268 """)
269 }
270
271 @Test
272 fun testMultiplePollWithPredicate() {
273 TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
274 | poll(1, 0) = null | poll(1, 0) = null
275 add(6) | poll(1, 0) = 6 |
276 add(11) | poll(1, 0) { > 20 } = null | poll(1, 0) { = 11 } = 11
277 | poll(1, 0) { > 8 } = 11 |
278 """)
279 }
280
281 @Test
282 fun testMultipleReadHeads() {
283 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
284 | poll() = null | poll() = null | poll() = null
285 add(5) | | poll() = 5 |
286 | poll() = 5 | |
287 add(8) | poll() = 8 | poll() = 8 |
288 | | | poll() = 5
289 | | | poll() = 8
290 | | | poll() = null
291 | | poll() = null |
292 """)
293 }
294
295 @Test
296 fun testReadHeadPollWithPredicate() {
297 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
298 add(5) | poll() { < 0 } = null
299 | poll() { > 5 } = null
300 add(10) |
301 | poll() { = 5 } = null // The "5" was skipped in the previous line
302 add(15) | poll() { > 8 } = 15 // The "10" was skipped in the previous line
303 | poll(1, 0) { > 8 } = 10 // 10 is the first element after pos 0 matching > 8
304 """)
305 }
306
307 @Test
308 fun testPollImmediatelyAdvancesReadhead() {
309 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
310 add(1) | add(2) | add(3) | add(4)
311 mark = 0 | poll(0) { > 3 } = 4 | |
312 poll(0) { > 10 } = null | | |
313 mark = 4 | | |
314 poll() = null | | |
315 """)
316 }
317
318 @Test
319 fun testParallelReadHeads() {
320 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
321 mark = 0 | mark = 0 | mark = 0 | mark = 0
322 add(2) | | |
323 | add(4) | |
324 | | add(6) |
325 | | | add(8)
326 poll() = 2 | poll() = 2 | poll() = 2 | poll() = 2
327 poll() = 4 | poll() = 4 | poll() = 4 | poll() = 4
328 poll() = 6 | poll() = 6 | poll() = 6 | mark = 2
329 poll() = 8 | poll() = 8 | mark = 3 | poll() = 6
330 mark = 4 | mark = 4 | poll() = 8 | poll() = 8
331 """)
332 }
333
334 @Test
335 fun testPeek() {
336 TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
337 add(2) | | |
338 | add(4) | |
339 | | add(6) |
340 | | | add(8)
341 peek() = 2 | poll() = 2 | poll() = 2 | peek() = 2
342 peek() = 2 | peek() = 4 | poll() = 4 | peek() = 2
343 peek() = 2 | peek() = 4 | peek() = 6 | poll() = 2
344 peek() = 2 | mark = 1 | mark = 2 | poll() = 4
345 mark = 0 | peek() = 4 | peek() = 6 | peek() = 6
346 poll() = 2 | poll() = 4 | poll() = 6 | poll() = 6
347 poll() = 4 | mark = 2 | poll() = 8 | peek() = 8
348 peek() = 6 | peek() = 6 | peek() = null | mark = 3
349 """)
350 }
351 }
352
353 private object TRTInterpreter : ConcurrentIntepreter<TrackRecord<Int>>(interpretTable) {
interpretTestSpecnull354 fun interpretTestSpec(spec: String, useReadHeads: Boolean) = if (useReadHeads) {
355 interpretTestSpec(spec, initial = ArrayTrackRecord(),
356 threadTransform = { (it as ArrayTrackRecord).newReadHead() })
357 } else {
358 interpretTestSpec(spec, ArrayTrackRecord())
359 }
360 }
361
362 /*
363 * Quick ref of supported expressions :
364 * sleep(x) : sleeps for x time units and returns Unit ; sleep alone means sleep(1)
365 * add(x) : calls and returns TrackRecord#add.
366 * poll(time, pos) [{ predicate }] : calls and returns TrackRecord#poll(x time units, pos).
367 * Optionally, a predicate may be specified.
368 * poll() [{ predicate }] : calls and returns ReadHead#poll(1 time unit). Optionally, a predicate
369 * may be specified.
370 * EXPR = VALUE : asserts that EXPR equals VALUE. EXPR is interpreted. VALUE can either be the
371 * string "null" or an int. Returns Unit.
372 * EXPR time x..y : measures the time taken by EXPR and asserts it took at least x and at most
373 * y time units.
374 * predicate must be one of "= x", "< x" or "> x".
375 */
376 private val interpretTable = listOf<InterpretMatcher<TrackRecord<Int>>>(
377 // Interpret "XXX is odd" : run XXX and assert its return value is odd ("even" works too)
rnull378 Regex("(.*)\\s+is\\s+(even|odd)") to { i, t, r ->
379 i.interpret(r.strArg(1), t).also {
380 assertEquals((it as Int) % 2, if ("even" == r.strArg(2)) 0 else 1)
381 }
382 },
383 // Interpret "add(XXX)" as TrackRecord#add(int)
rnull384 Regex("""add\((\d+)\)""") to { i, t, r ->
385 t.add(r.intArg(1))
386 },
387 // Interpret "poll(x, y)" as TrackRecord#poll(timeout = x * INTERPRET_TIME_UNIT, pos = y)
388 // Accepts an optional {} argument for the predicate (see makePredicate for syntax)
rnull389 Regex("""poll\((\d+),\s*(\d+)\)\s*(\{.*\})?""") to { i, t, r ->
390 t.poll(r.timeArg(1), r.intArg(2), makePredicate(r.strArg(3)))
391 },
392 // ReadHead#poll. If this throws in the cast, the code is malformed and has passed "poll()"
393 // in a test that takes a TrackRecord that is not a ReadHead. It's technically possible to get
394 // the test code to not compile instead of throw, but it's vastly more complex and this will
395 // fail 100% at runtime any test that would not have compiled.
rnull396 Regex("""poll\((\d+)?\)\s*(\{.*\})?""") to { i, t, r ->
397 (if (r.strArg(1).isEmpty()) i.interpretTimeUnit else r.timeArg(1)).let { time ->
398 (t as ArrayTrackRecord<Int>.ReadHead).poll(time, makePredicate(r.strArg(2)))
399 }
400 },
401 // ReadHead#mark. The same remarks apply as with ReadHead#poll.
tnull402 Regex("mark") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).mark },
403 // ReadHead#peek. The same remarks apply as with ReadHead#poll.
tnull404 Regex("peek\\(\\)") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).peek() }
405 )
406
407 // Parses a { = x } or { < x } or { > x } string and returns the corresponding predicate
408 // Returns an always-true predicate for empty and null arguments
makePredicatenull409 private fun makePredicate(spec: String?): (Int) -> Boolean {
410 if (spec.isNullOrEmpty()) return { true }
411 val match = Regex("""\{\s*([<>=])\s*(\d+)\s*\}""").matchEntire(spec)
412 ?: throw SyntaxException("Predicate \"${spec}\"")
413 val arg = match.intArg(2)
414 return when (match.strArg(1)) {
415 ">" -> { i -> i > arg }
416 "<" -> { i -> i < arg }
417 "=" -> { i -> i == arg }
418 else -> throw RuntimeException("How did \"${spec}\" match this regexp ?")
419 }
420 }
421