path: root/common/tests/unit/src/com/android/net/module/util/TrackRecordTest.kt

/*
 * 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.INTERPRET_TIME_UNIT
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()) INTERPRET_TIME_UNIT 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 ?")
    }
}