Merge "Move TrackRecordTest to libs/net"

1 files changed, 446 insertions, 0 deletions

diff --git a/common/tests/unit/src/com/android/net/module/util/TrackRecordTest.kt b/common/tests/unit/src/com/android/net/module/util/TrackRecordTest.kt
new file mode 100644
index 00000000..9fb4d8ca
--- /dev/null
+++ b/common/tests/unit/src/com/android/net/module/util/TrackRecordTest.kt
@@ -0,0 +1,446 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.net.module.util
+
+import com.android.testutils.ConcurrentInterpreter
+import com.android.testutils.InterpretException
+import com.android.testutils.InterpretMatcher
+import com.android.testutils.SyntaxException
+import com.android.testutils.__FILE__
+import com.android.testutils.__LINE__
+import com.android.testutils.intArg
+import com.android.testutils.strArg
+import com.android.testutils.timeArg
+import org.junit.Test
+import org.junit.runner.RunWith
+import org.junit.runners.JUnit4
+import java.util.concurrent.CyclicBarrier
+import java.util.concurrent.TimeUnit
+import java.util.concurrent.atomic.AtomicInteger
+import kotlin.system.measureTimeMillis
+import kotlin.test.assertEquals
+import kotlin.test.assertFailsWith
+import kotlin.test.assertFalse
+import kotlin.test.assertNotEquals
+import kotlin.test.assertNull
+import kotlin.test.assertTrue
+import kotlin.test.fail
+
+val TEST_VALUES = listOf(4, 13, 52, 94, 41, 68, 11, 13, 51, 0, 91, 94, 33, 98, 14)
+const val ABSENT_VALUE = 2
+// Caution in changing these : some tests rely on the fact that TEST_TIMEOUT > 2 * SHORT_TIMEOUT
+// and LONG_TIMEOUT > 2 * TEST_TIMEOUT
+const val SHORT_TIMEOUT = 40L // ms
+const val TEST_TIMEOUT = 200L // ms
+const val LONG_TIMEOUT = 5000L // ms
+
+@RunWith(JUnit4::class)
+class TrackRecordTest {
+    @Test
+    fun testAddAndSizeAndGet() {
+        val repeats = 22 // arbitrary
+        val record = ArrayTrackRecord<Int>()
+        assertEquals(0, record.size)
+        repeat(repeats) { i -> record.add(i + 2) }
+        assertEquals(repeats, record.size)
+        record.add(2)
+        assertEquals(repeats + 1, record.size)
+
+        assertEquals(11, record[9])
+        assertEquals(11, record.getOrNull(9))
+        assertEquals(2, record[record.size - 1])
+        assertEquals(2, record.getOrNull(record.size - 1))
+
+        assertFailsWith<IndexOutOfBoundsException> { record[800] }
+        assertFailsWith<IndexOutOfBoundsException> { record[-1] }
+        assertFailsWith<IndexOutOfBoundsException> { record[repeats + 1] }
+        assertNull(record.getOrNull(800))
+        assertNull(record.getOrNull(-1))
+        assertNull(record.getOrNull(repeats + 1))
+        assertNull(record.getOrNull(800) { true })
+        assertNull(record.getOrNull(-1) { true })
+        assertNull(record.getOrNull(repeats + 1) { true })
+    }
+
+    @Test
+    fun testIndexOf() {
+        val record = ArrayTrackRecord<Int>()
+        TEST_VALUES.forEach { record.add(it) }
+        with(record) {
+            assertEquals(9, indexOf(0))
+            assertEquals(9, lastIndexOf(0))
+            assertEquals(1, indexOf(13))
+            assertEquals(7, lastIndexOf(13))
+            assertEquals(3, indexOf(94))
+            assertEquals(11, lastIndexOf(94))
+            assertEquals(-1, indexOf(ABSENT_VALUE))
+            assertEquals(-1, lastIndexOf(ABSENT_VALUE))
+        }
+    }
+
+    @Test
+    fun testContains() {
+        val record = ArrayTrackRecord<Int>()
+        TEST_VALUES.forEach { record.add(it) }
+        TEST_VALUES.forEach { assertTrue(record.contains(it)) }
+        assertFalse(record.contains(ABSENT_VALUE))
+        assertTrue(record.containsAll(TEST_VALUES))
+        assertTrue(record.containsAll(TEST_VALUES.sorted()))
+        assertTrue(record.containsAll(TEST_VALUES.sortedDescending()))
+        assertTrue(record.containsAll(TEST_VALUES.distinct()))
+        assertTrue(record.containsAll(TEST_VALUES.subList(0, TEST_VALUES.size / 2)))
+        assertTrue(record.containsAll(TEST_VALUES.subList(0, TEST_VALUES.size / 2).sorted()))
+        assertTrue(record.containsAll(listOf()))
+        assertFalse(record.containsAll(listOf(ABSENT_VALUE)))
+        assertFalse(record.containsAll(TEST_VALUES + listOf(ABSENT_VALUE)))
+    }
+
+    @Test
+    fun testEmpty() {
+        val record = ArrayTrackRecord<Int>()
+        assertTrue(record.isEmpty())
+        record.add(1)
+        assertFalse(record.isEmpty())
+    }
+
+    @Test
+    fun testIterate() {
+        val record = ArrayTrackRecord<Int>()
+        record.forEach { fail("Expected nothing to iterate") }
+        TEST_VALUES.forEach { record.add(it) }
+        // zip relies on the iterator (this calls extension function Iterable#zip(Iterable))
+        record.zip(TEST_VALUES).forEach { assertEquals(it.first, it.second) }
+        // Also test reverse iteration (to test hasPrevious() and friends)
+        record.reversed().zip(TEST_VALUES.reversed()).forEach { assertEquals(it.first, it.second) }
+    }
+
+    @Test
+    fun testIteratorIsSnapshot() {
+        val record = ArrayTrackRecord<Int>()
+        TEST_VALUES.forEach { record.add(it) }
+        val iterator = record.iterator()
+        val expectedSize = record.size
+        record.add(ABSENT_VALUE)
+        record.add(ABSENT_VALUE)
+        var measuredSize = 0
+        iterator.forEach {
+            ++measuredSize
+            assertNotEquals(ABSENT_VALUE, it)
+        }
+        assertEquals(expectedSize, measuredSize)
+    }
+
+    @Test
+    fun testSublist() {
+        val record = ArrayTrackRecord<Int>()
+        TEST_VALUES.forEach { record.add(it) }
+        assertEquals(record.subList(3, record.size - 3),
+                TEST_VALUES.subList(3, TEST_VALUES.size - 3))
+    }
+
+    fun testPollReturnsImmediately(record: TrackRecord<Int>) {
+        record.add(4)
+        val elapsed = measureTimeMillis { assertEquals(4, record.poll(LONG_TIMEOUT, 0)) }
+        // Should not have waited at all, in fact.
+        assertTrue(elapsed < LONG_TIMEOUT)
+        record.add(7)
+        record.add(9)
+        // Can poll multiple times for the same position, in whatever order
+        assertEquals(9, record.poll(0, 2))
+        assertEquals(7, record.poll(Long.MAX_VALUE, 1))
+        assertEquals(9, record.poll(0, 2))
+        assertEquals(4, record.poll(0, 0))
+        assertEquals(9, record.poll(0, 2) { it > 5 })
+        assertEquals(7, record.poll(0, 0) { it > 5 })
+    }
+
+    @Test
+    fun testPollReturnsImmediately() {
+        testPollReturnsImmediately(ArrayTrackRecord())
+        testPollReturnsImmediately(ArrayTrackRecord<Int>().newReadHead())
+    }
+
+    @Test
+    fun testPollTimesOut() {
+        val record = ArrayTrackRecord<Int>()
+        var delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0)) }
+        assertTrue(delay >= SHORT_TIMEOUT, "Delay $delay < $SHORT_TIMEOUT")
+        delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0) { it < 10 }) }
+        assertTrue(delay >= SHORT_TIMEOUT)
+    }
+
+    @Test
+    fun testConcurrentPollDisallowed() {
+        val failures = AtomicInteger(0)
+        val readHead = ArrayTrackRecord<Int>().newReadHead()
+        val barrier = CyclicBarrier(2)
+        Thread {
+            barrier.await(LONG_TIMEOUT, TimeUnit.MILLISECONDS) // barrier 1
+            try {
+                readHead.poll(LONG_TIMEOUT)
+            } catch (e: ConcurrentModificationException) {
+                failures.incrementAndGet()
+                // Unblock the other thread
+                readHead.add(0)
+            }
+        }.start()
+        barrier.await() // barrier 1
+        try {
+            readHead.poll(LONG_TIMEOUT)
+        } catch (e: ConcurrentModificationException) {
+            failures.incrementAndGet()
+            // Unblock the other thread
+            readHead.add(0)
+        }
+        // One of the threads must have gotten an exception.
+        assertEquals(failures.get(), 1)
+    }
+
+    @Test
+    fun testPollWakesUp() {
+        val record = ArrayTrackRecord<Int>()
+        val barrier = CyclicBarrier(2)
+        Thread {
+            barrier.await(LONG_TIMEOUT, TimeUnit.MILLISECONDS) // barrier 1
+            barrier.await() // barrier 2
+            Thread.sleep(SHORT_TIMEOUT * 2)
+            record.add(31)
+        }.start()
+        barrier.await() // barrier 1
+        // Should find the element in more than SHORT_TIMEOUT but less than TEST_TIMEOUT
+        var delay = measureTimeMillis {
+            barrier.await() // barrier 2
+            assertEquals(31, record.poll(TEST_TIMEOUT, 0))
+        }
+        assertTrue(delay in SHORT_TIMEOUT..TEST_TIMEOUT)
+        // Polling for an element already added in anothe thread (pos 0) : should return immediately
+        delay = measureTimeMillis { assertEquals(31, record.poll(TEST_TIMEOUT, 0)) }
+        assertTrue(delay < TEST_TIMEOUT, "Delay $delay > $TEST_TIMEOUT")
+        // Waiting for an element that never comes
+        delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 1)) }
+        assertTrue(delay >= SHORT_TIMEOUT, "Delay $delay < $SHORT_TIMEOUT")
+        // Polling for an element that doesn't match what is already there
+        delay = measureTimeMillis { assertNull(record.poll(SHORT_TIMEOUT, 0) { it < 10 }) }
+        assertTrue(delay >= SHORT_TIMEOUT)
+    }
+
+    // Just make sure the interpreter actually throws an exception when the spec
+    // does not conform to the behavior. The interpreter is just a tool to test a
+    // tool used for a tool for test, let's not have hundreds of tests for it ;
+    // if it's broken one of the tests using it will break.
+    @Test
+    fun testInterpreter() {
+        val interpretLine = __LINE__ + 2
+        try {
+            TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+                add(4) | poll(1, 0) = 5
+            """)
+            fail("This spec should have thrown")
+        } catch (e: InterpretException) {
+            assertTrue(e.cause is AssertionError)
+            assertEquals(interpretLine + 1, e.stackTrace[0].lineNumber)
+            assertTrue(e.stackTrace[0].fileName.contains(__FILE__))
+            assertTrue(e.stackTrace[0].methodName.contains("testInterpreter"))
+            assertTrue(e.stackTrace[0].methodName.contains("thread1"))
+        }
+    }
+
+    @Test
+    fun testMultipleAdds() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
+            add(2)         |                |                |
+                           | add(4)         |                |
+                           |                | add(6)         |
+                           |                |                | add(8)
+            poll(0, 0) = 2 time 0..1 | poll(0, 0) = 2 | poll(0, 0) = 2 | poll(0, 0) = 2
+            poll(0, 1) = 4 time 0..1 | poll(0, 1) = 4 | poll(0, 1) = 4 | poll(0, 1) = 4
+            poll(0, 2) = 6 time 0..1 | poll(0, 2) = 6 | poll(0, 2) = 6 | poll(0, 2) = 6
+            poll(0, 3) = 8 time 0..1 | poll(0, 3) = 8 | poll(0, 3) = 8 | poll(0, 3) = 8
+        """)
+    }
+
+    @Test
+    fun testConcurrentAdds() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
+            add(2)             | add(4)             | add(6)             | add(8)
+            add(1)             | add(3)             | add(5)             | add(7)
+            poll(0, 1) is even | poll(0, 0) is even | poll(0, 3) is even | poll(0, 2) is even
+            poll(0, 5) is odd  | poll(0, 4) is odd  | poll(0, 7) is odd  | poll(0, 6) is odd
+        """)
+    }
+
+    @Test
+    fun testMultiplePoll() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
+            add(4)         | poll(1, 0) = 4
+                           | poll(0, 1) = null time 0..1
+                           | poll(1, 1) = null time 1..2
+            sleep; add(7)  | poll(2, 1) = 7 time 1..2
+            sleep; add(18) | poll(2, 2) = 18 time 1..2
+        """)
+    }
+
+    @Test
+    fun testMultiplePollWithPredicate() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = false, spec = """
+                     | poll(1, 0) = null          | poll(1, 0) = null
+            add(6)   | poll(1, 0) = 6             |
+            add(11)  | poll(1, 0) { > 20 } = null | poll(1, 0) { = 11 } = 11
+                     | poll(1, 0) { > 8 } = 11    |
+        """)
+    }
+
+    @Test
+    fun testMultipleReadHeads() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+                   | poll() = null | poll() = null | poll() = null
+            add(5) |               | poll() = 5    |
+                   | poll() = 5    |               |
+            add(8) | poll() = 8    | poll() = 8    |
+                   |               |               | poll() = 5
+                   |               |               | poll() = 8
+                   |               |               | poll() = null
+                   |               | poll() = null |
+        """)
+    }
+
+    @Test
+    fun testReadHeadPollWithPredicate() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+            add(5)  | poll() { < 0 } = null
+                    | poll() { > 5 } = null
+            add(10) |
+                    | poll() { = 5 } = null   // The "5" was skipped in the previous line
+            add(15) | poll() { > 8 } = 15     // The "10" was skipped in the previous line
+                    | poll(1, 0) { > 8 } = 10 // 10 is the first element after pos 0 matching > 8
+        """)
+    }
+
+    @Test
+    fun testPollImmediatelyAdvancesReadhead() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+            add(1)                  | add(2)              | add(3)   | add(4)
+            mark = 0                | poll(0) { > 3 } = 4 |          |
+            poll(0) { > 10 } = null |                     |          |
+            mark = 4                |                     |          |
+            poll() = null           |                     |          |
+        """)
+    }
+
+    @Test
+    fun testParallelReadHeads() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+            mark = 0   | mark = 0   | mark = 0   | mark = 0
+            add(2)     |            |            |
+                       | add(4)     |            |
+                       |            | add(6)     |
+                       |            |            | add(8)
+            poll() = 2 | poll() = 2 | poll() = 2 | poll() = 2
+            poll() = 4 | poll() = 4 | poll() = 4 | poll() = 4
+            poll() = 6 | poll() = 6 | poll() = 6 | mark = 2
+            poll() = 8 | poll() = 8 | mark = 3   | poll() = 6
+            mark = 4   | mark = 4   | poll() = 8 | poll() = 8
+        """)
+    }
+
+    @Test
+    fun testPeek() {
+        TRTInterpreter.interpretTestSpec(useReadHeads = true, spec = """
+            add(2)     |            |               |
+                       | add(4)     |               |
+                       |            | add(6)        |
+                       |            |               | add(8)
+            peek() = 2 | poll() = 2 | poll() = 2    | peek() = 2
+            peek() = 2 | peek() = 4 | poll() = 4    | peek() = 2
+            peek() = 2 | peek() = 4 | peek() = 6    | poll() = 2
+            peek() = 2 | mark = 1   | mark = 2      | poll() = 4
+            mark = 0   | peek() = 4 | peek() = 6    | peek() = 6
+            poll() = 2 | poll() = 4 | poll() = 6    | poll() = 6
+            poll() = 4 | mark = 2   | poll() = 8    | peek() = 8
+            peek() = 6 | peek() = 6 | peek() = null | mark = 3
+        """)
+    }
+}
+
+private object TRTInterpreter : ConcurrentInterpreter<TrackRecord<Int>>(interpretTable) {
+    fun interpretTestSpec(spec: String, useReadHeads: Boolean) = if (useReadHeads) {
+        interpretTestSpec(spec, initial = ArrayTrackRecord(),
+                threadTransform = { (it as ArrayTrackRecord).newReadHead() })
+    } else {
+        interpretTestSpec(spec, ArrayTrackRecord())
+    }
+}
+
+/*
+ * Quick ref of supported expressions :
+ * sleep(x) : sleeps for x time units and returns Unit ; sleep alone means sleep(1)
+ * add(x) : calls and returns TrackRecord#add.
+ * poll(time, pos) [{ predicate }] : calls and returns TrackRecord#poll(x time units, pos).
+ *   Optionally, a predicate may be specified.
+ * poll() [{ predicate }] : calls and returns ReadHead#poll(1 time unit). Optionally, a predicate
+ *   may be specified.
+ * EXPR = VALUE : asserts that EXPR equals VALUE. EXPR is interpreted. VALUE can either be the
+ *   string "null" or an int. Returns Unit.
+ * EXPR time x..y : measures the time taken by EXPR and asserts it took at least x and at most
+ *   y time units.
+ * predicate must be one of "= x", "< x" or "> x".
+ */
+private val interpretTable = listOf<InterpretMatcher<TrackRecord<Int>>>(
+    // Interpret "XXX is odd" : run XXX and assert its return value is odd ("even" works too)
+    Regex("(.*)\\s+is\\s+(even|odd)") to { i, t, r ->
+        i.interpret(r.strArg(1), t).also {
+            assertEquals((it as Int) % 2, if ("even" == r.strArg(2)) 0 else 1)
+        }
+    },
+    // Interpret "add(XXX)" as TrackRecord#add(int)
+    Regex("""add\((\d+)\)""") to { i, t, r ->
+        t.add(r.intArg(1))
+    },
+    // Interpret "poll(x, y)" as TrackRecord#poll(timeout = x * INTERPRET_TIME_UNIT, pos = y)
+    // Accepts an optional {} argument for the predicate (see makePredicate for syntax)
+    Regex("""poll\((\d+),\s*(\d+)\)\s*(\{.*\})?""") to { i, t, r ->
+        t.poll(r.timeArg(1), r.intArg(2), makePredicate(r.strArg(3)))
+    },
+    // ReadHead#poll. If this throws in the cast, the code is malformed and has passed "poll()"
+    // in a test that takes a TrackRecord that is not a ReadHead. It's technically possible to get
+    // the test code to not compile instead of throw, but it's vastly more complex and this will
+    // fail 100% at runtime any test that would not have compiled.
+    Regex("""poll\((\d+)?\)\s*(\{.*\})?""") to { i, t, r ->
+        (if (r.strArg(1).isEmpty()) i.interpretTimeUnit else r.timeArg(1)).let { time ->
+            (t as ArrayTrackRecord<Int>.ReadHead).poll(time, makePredicate(r.strArg(2)))
+        }
+    },
+    // ReadHead#mark. The same remarks apply as with ReadHead#poll.
+    Regex("mark") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).mark },
+    // ReadHead#peek. The same remarks apply as with ReadHead#poll.
+    Regex("peek\\(\\)") to { i, t, _ -> (t as ArrayTrackRecord<Int>.ReadHead).peek() }
+)
+
+// Parses a { = x } or { < x } or { > x } string and returns the corresponding predicate
+// Returns an always-true predicate for empty and null arguments
+private fun makePredicate(spec: String?): (Int) -> Boolean {
+    if (spec.isNullOrEmpty()) return { true }
+    val match = Regex("""\{\s*([<>=])\s*(\d+)\s*\}""").matchEntire(spec)
+            ?: throw SyntaxException("Predicate \"${spec}\"")
+    val arg = match.intArg(2)
+    return when (match.strArg(1)) {
+        ">" -> { i -> i > arg }
+        "<" -> { i -> i < arg }
+        "=" -> { i -> i == arg }
+        else -> throw RuntimeException("How did \"${spec}\" match this regexp ?")
+    }
+}