feat(sim/core): Add Java-based simulator core

This change introduces a new class, `SimulationScheduler`, which
provides the basis for simulations in OpenDC by allowing components to
schedule future tasks using delay-skipping queue and a virtual clock.

This new class is written in Java to remove any dependency on the
Kotlin and kotlinx-coroutines runtime when not necessary.

2 files changed, 337 insertions, 0 deletions

diff --git a/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/SimulationSchedulerTest.kt b/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/SimulationSchedulerTest.kt
new file mode 100644
index 00000000..eca3b582
--- /dev/null
+++ b/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/SimulationSchedulerTest.kt
@@ -0,0 +1,106 @@
+/*
+ * Copyright (c) 2022 AtLarge Research
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+package org.opendc.simulator
+
+import org.junit.jupiter.api.Assertions.assertEquals
+import org.junit.jupiter.api.Test
+import org.junit.jupiter.api.assertThrows
+import java.time.Instant
+
+/**
+ * Test suite for the [SimulationScheduler] class.
+ */
+class SimulationSchedulerTest {
+    /**
+     * Test the basic functionality of [SimulationScheduler.runCurrent].
+     */
+    @Test
+    fun testRunCurrent() {
+        val scheduler = SimulationScheduler()
+        var count = 0
+
+        scheduler.schedule(1) { count += 1 }
+        scheduler.schedule(2) { count += 1 }
+
+        scheduler.advanceBy(1)
+        assertEquals(0, count)
+        scheduler.runCurrent()
+        assertEquals(1, count)
+        scheduler.advanceBy(1)
+        assertEquals(1, count)
+        scheduler.runCurrent()
+        assertEquals(2, count)
+        assertEquals(2, scheduler.currentTime)
+
+        scheduler.advanceBy(Long.MAX_VALUE)
+        scheduler.runCurrent()
+        assertEquals(Long.MAX_VALUE, scheduler.currentTime)
+    }
+
+    /**
+     * Test the clock of the [SimulationScheduler].
+     */
+    @Test
+    fun testClock() {
+        val scheduler = SimulationScheduler()
+        var count = 0
+
+        scheduler.schedule(1) { count += 1 }
+        scheduler.schedule(2) { count += 1 }
+
+        scheduler.advanceBy(2)
+        assertEquals(2, scheduler.currentTime)
+        assertEquals(2, scheduler.clock.millis())
+        assertEquals(Instant.ofEpochMilli(2), scheduler.clock.instant())
+    }
+
+    /**
+     * Test large delays.
+     */
+    @Test
+    fun testAdvanceByLargeDelays() {
+        val scheduler = SimulationScheduler()
+        var count = 0
+
+        scheduler.schedule(1) { count += 1 }
+
+        scheduler.advanceBy(10)
+
+        scheduler.schedule(Long.MAX_VALUE) { count += 1 }
+        scheduler.schedule(100_000_000) { count += 1 }
+
+        scheduler.advanceUntilIdle()
+        assertEquals(3, count)
+    }
+
+    /**
+     * Test negative delays.
+     */
+    @Test
+    fun testNegativeDelays() {
+        val scheduler = SimulationScheduler()
+
+        assertThrows<IllegalArgumentException> { scheduler.schedule(-100) { } }
+        assertThrows<IllegalArgumentException> { scheduler.advanceBy(-100) }
+    }
+}
diff --git a/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/TaskQueueTest.kt b/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/TaskQueueTest.kt
new file mode 100644
index 00000000..a4d779cb
--- /dev/null
+++ b/opendc-simulator/opendc-simulator-core/src/test/kotlin/org/opendc/simulator/TaskQueueTest.kt
@@ -0,0 +1,231 @@
+/*
+ * Copyright (c) 2022 AtLarge Research
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+package org.opendc.simulator
+
+import org.junit.jupiter.api.Assertions.*
+import org.junit.jupiter.api.BeforeEach
+import org.junit.jupiter.api.Test
+
+/**
+ * Test suite for the [TaskQueue] class.
+ */
+class TaskQueueTest {
+    private lateinit var queue: TaskQueue
+
+    @BeforeEach
+    fun setUp() {
+        queue = TaskQueue(3)
+    }
+
+    /**
+     * Test whether a call to [TaskQueue.poll] returns `null` for an empty queue.
+     */
+    @Test
+    fun testPollEmpty() {
+        assertAll(
+            { assertEquals(Long.MAX_VALUE, queue.peekDeadline()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test whether a call to [TaskQueue.poll] returns the proper value for a queue with a single entry.
+     */
+    @Test
+    fun testSingleEntry() {
+        val entry = Runnable {}
+
+        queue.add(100, 1, entry)
+
+        assertAll(
+            { assertEquals(100, queue.peekDeadline()) },
+            { assertEquals(entry, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test whether [TaskQueue.poll] returns values in the queue in the proper order.
+     */
+    @Test
+    fun testMultipleEntries() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(48, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        assertAll(
+            { assertEquals(48, queue.peekDeadline()) },
+            { assertEquals(entryB, queue.poll()) },
+            { assertEquals(entryC, queue.poll()) },
+            { assertEquals(entryA, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test whether [TaskQueue.poll] returns values in the queue in the proper order with duplicates.
+     */
+    @Test
+    fun testMultipleEntriesDuplicate() {
+        val entryA = Runnable {}
+        queue.add(48, 0, entryA)
+
+        val entryB = Runnable {}
+        queue.add(48, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(48, 2, entryC)
+
+        assertAll(
+            { assertEquals(48, queue.peekDeadline()) },
+            { assertEquals(entryA, queue.poll()) },
+            { assertEquals(entryB, queue.poll()) },
+            { assertEquals(entryC, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test that the queue is properly resized when the number of entries exceed the capacity.
+     */
+    @Test
+    fun testResize() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(20, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        val entryD = Runnable {}
+        queue.add(38, 1, entryD)
+
+        assertAll(
+            { assertEquals(20, queue.peekDeadline()) },
+            { assertEquals(entryB, queue.poll()) },
+            { assertEquals(entryD, queue.poll()) },
+            { assertEquals(entryC, queue.poll()) },
+            { assertEquals(entryA, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test that we can remove an entry from the end of the queue.
+     */
+    @Test
+    fun testRemoveEntryTail() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(20, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        queue.remove(100, 1)
+
+        assertAll(
+            { assertEquals(20, queue.peekDeadline()) },
+            { assertEquals(entryB, queue.poll()) },
+            { assertEquals(entryC, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test that we can remove an entry from the head of the queue.
+     */
+    @Test
+    fun testRemoveEntryHead() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(20, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        queue.remove(20, 1)
+
+        assertAll(
+            { assertEquals(58, queue.peekDeadline()) },
+            { assertEquals(entryC, queue.poll()) },
+            { assertEquals(entryA, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test that we can remove an entry from the middle of a queue.
+     */
+    @Test
+    fun testRemoveEntryMiddle() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(20, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        queue.remove(58, 1)
+
+        assertAll(
+            { assertEquals(20, queue.peekDeadline()) },
+            { assertEquals(entryB, queue.poll()) },
+            { assertEquals(entryA, queue.poll()) },
+            { assertNull(queue.poll()) },
+        )
+    }
+
+    /**
+     * Test that we can "remove" an unknown entry without error.
+     */
+    @Test
+    fun testRemoveUnknown() {
+        val entryA = Runnable {}
+        queue.add(100, 1, entryA)
+
+        val entryB = Runnable {}
+        queue.add(20, 1, entryB)
+
+        val entryC = Runnable {}
+        queue.add(58, 1, entryC)
+
+        assertAll(
+            { assertFalse(queue.remove(10, 1)) },
+            { assertFalse(queue.remove(58, 2)) }
+        )
+    }
+}