Test a stable iOS priority queue on a cloud Mac

Image prefetching, pending uploads, and local task ordering often rely on priority queues. Enqueue three tasks in a row on a development machine, then dequeue them one by one, and the results can look correct. But when enqueue and dequeue operations are interleaved in regression tests on a cloud Mac, tasks with equal priority may start changing places. Rather than building a complete scheduler, we will isolate a Swift binary heap and verify that it consistently honors its ordering contract.

Define priority and stability first

The contract here is simple: lower priority numbers leave the queue first; tasks with the same priority leave in the order they were enqueued. Task identifiers are business data and do not participate in comparisons. Enqueuing the same task again creates a new entry with a new enqueue sequence number.

Write these rules down as test requirements before implementing the data structure. Do not use array indices as permanent sequence numbers: dequeuing and swapping change those indices, so they cannot guarantee stability. Do not compare priorities by subtracting them, either, because extreme integer values can cause overflow.

Stability is not fairness. If high-priority tasks keep arriving, low-priority tasks may still wait indefinitely. Aging and quotas are scheduling policies and should not be slipped into the heap's comparison function.

The implementation below is a value type intended only for serial access. When integrating it into concurrent code, manage it through a single isolation boundary rather than allowing multiple tasks to mutate the same instance simultaneously.

Implement a min-heap with enqueue sequence numbers

Save the code as main.swift. The comparison key consists of a priority and an increasing sequence number. Both sift-up during enqueue and sift-down during dequeue must use the same comparison function, so the two paths agree on which entry comes first.

struct StableQueue<Value> {
    enum Failure: Error {
        case sequenceExhausted
    }

    private struct Entry {
        let value: Value
        let priority: Int
        let sequence: UInt64
    }

    private var entries: [Entry] = []
    private var nextSequence: UInt64 = 0

    private func precedes(_ a: Entry, _ b: Entry) -> Bool {
        if a.priority != b.priority {
            return a.priority < b.priority
        }
        return a.sequence < b.sequence
    }

    mutating func enqueue(_ value: Value, priority: Int) throws {
        guard nextSequence < UInt64.max else {
            throw Failure.sequenceExhausted
        }
        entries.append(Entry(
            value: value,
            priority: priority,
            sequence: nextSequence
        ))
        nextSequence += 1

        var child = entries.count - 1
        while child > 0 {
            let parent = (child - 1) / 2
            guard precedes(entries[child], entries[parent]) else {
                break
            }
            entries.swapAt(child, parent)
            child = parent
        }
    }

    mutating func dequeue() -> Value? {
        guard !entries.isEmpty else { return nil }
        if entries.count == 1 {
            return entries.removeLast().value
        }

        let result = entries[0].value
        entries[0] = entries.removeLast()
        var parent = 0

        while parent < entries.count / 2 {
            let left = parent * 2 + 1
            let right = left + 1
            var candidate = left
            if right < entries.count,
               precedes(entries[right], entries[left]) {
                candidate = right
            }
            guard precedes(entries[candidate], entries[parent]) else {
                break
            }
            entries.swapAt(parent, candidate)
            parent = candidate
        }
        return result
    }
}

When the sequence counter reaches its limit, the queue explicitly throws an error. It neither wraps around nor silently resets after the queue is emptied. This implementation leaves the maximum value unused so that failure occurs before the array is modified. Tests should verify that a failed enqueue does not change the order of existing entries.

Catch sift-down bugs with interleaved operations

Append the following snippet to the same file. It checks not only the final ordering but also that, after removing an entry and inserting another task at the same priority, older entries still come before the new one.

func requireEqual<T: Equatable>(_ actual: T, _ expected: T) {
    precondition(actual == expected, "Queue contract failed")
}

var queue = StableQueue<String>()
requireEqual(queue.dequeue(), Optional<String>.none)

try queue.enqueue("A", priority: 2)
try queue.enqueue("B", priority: 1)
try queue.enqueue("C", priority: 2)
requireEqual(queue.dequeue(), Optional("B"))

try queue.enqueue("D", priority: 2)
try queue.enqueue("E", priority: Int.min)
requireEqual(queue.dequeue(), Optional("E"))
requireEqual(queue.dequeue(), Optional("A"))
requireEqual(queue.dequeue(), Optional("C"))
requireEqual(queue.dequeue(), Optional("D"))
requireEqual(queue.dequeue(), Optional<String>.none)

Run these commands in the working directory on the cloud Mac:

set -eu
mkdir -p .build
xcrun swiftc -Onone main.swift -o .build/queue-check
.build/queue-check

A successful run produces no output; a failure stops the job with a nonzero exit code. We use precondition rather than assert so that optimized builds do not remove the checks. Successful compilation alone is not a substitute for running the acceptance checks.

Add three more sets of deterministic cases: preserve input order when all priorities are equal; enqueue all entries in descending priority order, then dequeue them in ascending order; and start with just two elements, remove one, then continue interleaving insertions and removals. The last set is particularly useful for exposing out-of-bounds access when there is no right child.

Expand coverage with a reference model

Handwritten cases illustrate the contract, but they are unlikely to cover every heap shape. A reference model can simply store task identifiers, priorities, and enqueue sequence numbers in an array, sorting by the latter two fields before each dequeue. It is slow, but its simplicity makes it a useful oracle for small tests.

When generating interleaved operations, add each enqueued entry to the model as well. On every dequeue, compare the optional task identifiers returned by both implementations, then drain both queues after the operations finish. Comparing priorities alone is insufficient: changing the order of equal-priority tasks is also a defect.

Use a seedable pseudorandom generator rather than a source of randomness that cannot be replayed. Failure records should include at least the seed, operation index, complete operation prefix, and results from both sides. To narrow down a failure, remove chunks of operations from the failing prefix, retaining the shortest sequence that still fails.

Keep the reference model independent of the implementation

The reference model must not reuse the heap's comparison function, or the same bug could make both sides agree. Instead, the model can compare priorities first and, only when they are equal, choose the entry enqueued earliest. This expresses the business rule directly.

Add regression checks and define what they prove

Before committing, always run tests for an empty queue, a single element, equal-priority stability, integer extremes, and interleaved operations, followed by a batch of model comparisons using fixed seeds. Add newly failing seeds to the permanent regression suite rather than merely increasing the random test count and trying again.

Sequence exhaustion cannot realistically be covered through ordinary enqueue operations. A production module can provide an internal, test-only initializer that places the counter just below its limit. This lets tests check the boundary between the last permitted enqueue and the next rejected one without exposing a public interface for modifying production state.

Archive the Swift toolchain version, commit identifier, and failing operation sequence; there is no need to retain business payloads. The final acceptance statement should be explicit: these tests verify the ordering and boundary behavior of a serially accessed queue, not thread safety, task execution success rates, or scheduling fairness. Documenting those limits prevents data structure tests from being mistaken for guarantees about the entire system when an executor is integrated later.

Frequently asked questions