Eine stabile Prioritätswarteschlange für iOS testen

Beim Vorladen von Bildern, bei ausstehenden Uploads und beim Sortieren lokaler Aufgaben kommen häufig Prioritätswarteschlangen zum Einsatz. Auf dem Entwicklungsrechner lassen sich drei Aufgaben nacheinander einfügen und anschließend in der richtigen Reihenfolge entnehmen. In Regressionstests auf einem Cloud-Mac wechseln sich Einfügen und Entnehmen jedoch ab – und plötzlich vertauschen Aufgaben mit gleicher Priorität ihre Plätze. Statt einen vollständigen Scheduler aufzubauen, betrachten wir hier einen binären Heap in Swift für sich und prüfen, ob er seinen Ordnungsvertrag durchgehend einhält.

Priorität und Stabilität zuerst festlegen

Für diesen Artikel gilt: Je kleiner der Prioritätswert, desto früher wird ein Eintrag entnommen. Bei gleichen Werten kommt der zuerst eingefügte Eintrag zuerst heraus. Die Aufgabenkennung ist lediglich ein fachlicher Datenwert und geht nicht in den Vergleich ein. Wird dieselbe Aufgabe erneut eingefügt, gilt sie als neuer Eintrag und erhält eine neue Einfügesequenznummer.

Diese Regeln sollten zuerst als Testanforderungen festgehalten werden, bevor die Datenstruktur implementiert wird. Array-Indizes eignen sich nicht als dauerhafte Sequenznummern: Beim Entnehmen und Vertauschen ändern sich die Indizes, sodass sich damit keine Stabilität garantieren lässt. Ebenso sollte die Reihenfolge nicht durch Subtraktion der Prioritäten ermittelt werden, da extreme Ganzzahlwerte einen Überlauf auslösen können.

Stabilität ist nicht dasselbe wie Fairness. Treffen ständig Aufgaben mit hoher Priorität ein, können Aufgaben mit niedriger Priorität weiterhin sehr lange warten. Aging und Kontingente gehören zur Scheduling-Strategie und dürfen nicht unbemerkt in die Vergleichsfunktion des Heaps einfließen.

Die folgende Implementierung ist ein Werttyp und ausschließlich für seriellen Zugriff vorgesehen. Für den Einsatz in nebenläufigem Code muss eine gemeinsame Isolationsgrenze den Zugriff verwalten. Mehrere Tasks dürfen nicht gleichzeitig dieselbe Instanz verändern.

Einen Min-Heap mit Einfügesequenznummer implementieren

Speichere den Code als main.swift. Der Vergleichsschlüssel besteht aus Priorität und aufsteigender Sequenznummer. Sowohl das Aufsteigen beim Einfügen als auch das Absinken beim Entnehmen müssen dieselbe Vergleichsfunktion verwenden. Andernfalls könnten die beiden Pfade unterschiedlich auslegen, welcher Eintrag Vorrang hat.

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
    }
}

Erreicht die Sequenznummer ihre Obergrenze, wird ausdrücklich ein Fehler ausgelöst. Der Zähler läuft weder über noch wird er beim Leeren der Warteschlange stillschweigend zurückgesetzt. Die Implementierung lässt den maximalen Wert ungenutzt, damit der Fehler vor einer Änderung am Array auftritt. Ein Test sollte sicherstellen, dass ein fehlgeschlagenes Einfügen die Reihenfolge vorhandener Einträge nicht verändert.

Fehler beim Absinken mit verschachtelten Operationen aufdecken

Füge den folgenden Abschnitt am Ende derselben Datei an. Er prüft nicht nur die abschließende Reihenfolge, sondern auch, ob nach dem Entnehmen eines Eintrags und dem Einfügen einer neuen Aufgabe gleicher Priorität die älteren Einträge weiterhin vor dem neuen stehen.

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)

Führe im Arbeitsverzeichnis auf dem Cloud-Mac Folgendes aus:

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

Bei Erfolg gibt es keine Ausgabe. Bei einem Fehler stoppt ein Exit-Code ungleich null den Job. Hier kommt bewusst kein assert zum Einsatz, damit die Prüfungen nicht durch eine optimierte Übersetzung entfernt werden. Auch eine erfolgreiche Kompilierung ersetzt nicht die Prüfung durch Ausführen.

Ergänze drei Gruppen deterministischer Testfälle: Bei durchgehend gleicher Priorität bleibt die Eingabereihenfolge erhalten; nach dem Einfügen aller Einträge mit absteigenden Prioritätswerten werden sie in aufsteigender Reihenfolge entnommen; bei genau zwei Elementen wird zunächst eines entnommen, danach folgen wiederholt Einfüge- und Entnahmeoperationen. Die letzte Gruppe deckt besonders leicht ungültige Indexzugriffe auf, wenn kein rechtes Kind vorhanden ist.

Die Testabdeckung mit einem Referenzmodell erweitern

Handgeschriebene Testfälle veranschaulichen den Vertrag, decken aber kaum alle möglichen Heap-Formen ab. Ein Referenzmodell kann Aufgabenkennung, Priorität und Einfügesequenznummer einfach in einem Array speichern und dieses vor jeder Entnahme nach den letzten beiden Feldern sortieren. Das ist zwar langsam, aber leicht zu implementieren und eignet sich deshalb als Vergleichsinstanz für kleine Tests.

Bei der Erzeugung verschachtelter Operationen wird jeder eingefügte Eintrag auch im Modell gespeichert. Bei jeder Entnahme werden die optionalen Aufgabenkennungen beider Seiten verglichen. Nach der letzten Operation werden beide Warteschlangen vollständig geleert. Nur die Prioritäten zu vergleichen reicht nicht aus: Auch vertauschte Einträge gleicher Priorität sind ein Fehler.

Verwende einen Pseudozufallszahlengenerator mit einstellbarem Seed statt einer Zufallsquelle, deren Ergebnisse sich nicht reproduzieren lassen. Ein Fehlerprotokoll muss mindestens den Seed, den Operationsindex, die vollständige Operationsfolge bis zum Fehler sowie beide Ergebnisse enthalten. Zur Eingrenzung werden abschnittsweise Operationen aus dieser Folge entfernt, bis die kürzeste weiterhin fehlschlagende Sequenz übrig bleibt.

Das Referenzmodell von der Implementierung unabhängig halten

Das Referenzmodell darf die Vergleichsfunktion des Heaps nicht wiederverwenden. Sonst könnte derselbe Fehler auf beiden Seiten unentdeckt bleiben. Das Modell kann zunächst die Prioritäten vergleichen und nur bei Gleichheit den am frühesten eingefügten Eintrag auswählen. Damit bildet es die fachliche Regel unmittelbar ab.

In Regressionstests einbinden und die Aussage begrenzen

Vor jedem Commit sollten feste Tests für eine leere Warteschlange, ein einzelnes Element, Stabilität bei gleicher Priorität, Ganzzahl-Extremwerte und verschachtelte Operationen laufen. Anschließend folgt eine Reihe von Modellvergleichen mit festen Seeds. Neue Seeds, die einen Fehler aufdecken, gehören dauerhaft in die Regressionssuite. Es genügt nicht, lediglich die Anzahl der Zufallsdurchläufe zu erhöhen und erneut zu testen.

Das Ausschöpfen der Sequenznummern lässt sich nicht durch eine praktikable Anzahl normaler Einfügeoperationen testen. Das eigentliche Modul kann dafür einen internen, ausschließlich für Tests vorgesehenen Initialisierungsweg anbieten. Dieser setzt den Zähler kurz vor die Obergrenze, sodass sich das letzte zulässige und das darauffolgende abgewiesene Einfügen prüfen lassen. Eine öffentliche Schnittstelle zum Verändern des Produktionszustands sollte dafür nicht geschaffen werden.

Es genügt, die Version der Swift-Toolchain, die Commit-Kennung und die fehlgeschlagene Operationsfolge zu archivieren. Fachliche Nutzdaten müssen nicht gespeichert werden. Das abschließende Prüfergebnis sollte klar benennen, was hier nachgewiesen wird: die Reihenfolge und das Verhalten an den Grenzen einer seriell verwendeten Warteschlange, nicht aber Thread-Sicherheit, die erfolgreiche Ausführung von Aufgaben oder Scheduling-Fairness. Sind diese Grenzen ausdrücklich dokumentiert, werden die Datenstrukturtests bei der späteren Anbindung an einen Executor nicht fälschlich als Garantie für das gesamte System verstanden.

Häufig gestellte Fragen