iOS-Ringpuffer auf dem Cloud-Mac auf Grenzfälle prüfen

Die Logik für den Datenempfang ist unter Windows geschrieben, die iOS-Tests laufen anschließend auf einem Cloud-Mac. Dabei kann ein Ringpuffer Daten nur unter einer bestimmten Abfolge verlieren: vollständig füllen, einen Teil auslesen und danach erneut schreiben. Ein einzelner Einfüge- und Entnahmevorgang deckt diesen Fehler nicht auf. Deshalb kapseln wir den Puffer zunächst in einem eigenständigen Swift-Typ, prüfen ihn im Terminal eines Cloud-Macs von OSXMesh und übernehmen anschließend dieselben Zusicherungen in das Test-Target der App.

Zuerst das Verhalten bei vollem und leerem Puffer sowie bei Fehlschlägen festlegen

Wir verwenden einen Integer-Puffer mit fester Kapazität nach dem FIFO-Prinzip: Die Kapazität muss größer als null sein. Ist der Puffer voll, werden neue Elemente abgewiesen, ohne vorhandene Daten zu überschreiben. Beim Lesen aus einem leeren Puffer wird nil zurückgegeben. Stapelschreibvorgänge dürfen teilweise erfolgreich sein: Sie liefern die Anzahl der tatsächlich angenommenen Elemente zurück; die verbleibenden Eingaben muss der Aufrufer selbst behandeln.

Das ist nicht die einzig mögliche Auslegung, aber eine muss vorab feststehen. Soll das Produkt die ältesten Daten überschreiben, braucht es dafür einen eigenen Typ und eigene Zusicherungen. Derselbe append-Aufruf darf seine Semantik nicht je nach Aufrufstelle unbemerkt ändern.

Ein korrekter Ringpuffer verhindert nicht nur Zugriffe außerhalb der Arraygrenzen: Fehlgeschlagene Operationen dürfen den Zustand nicht verändern, und erfolgreiche Lesevorgänge müssen die Elemente in der Reihenfolge ihrer Annahme liefern.

head bezeichnet die nächste Leseposition, count unterscheidet zwischen vollem und leerem Puffer. Das logische Ende ergibt sich aus diesen beiden Werten. Dadurch lassen sich sämtliche Speicherplätze nutzen. Das Beispiel begrenzt die maximale Kapazität, um einen Überlauf beim Addieren der Indizes zu vermeiden und versehentlich übergroße Kapazitätsangaben in Tests abzufangen.

Eine minimale, eigenständig ausführbare Implementierung schreiben

Legen Sie RingCheck.swift an und fügen Sie den folgenden Code ein. Er benötigt nur die Standardbibliothek, weder einen Simulator noch eine Projektsignierung. Führen Sie zunächst swift --version aus, um die Informationen zur Toolchain festzuhalten. Ist der Befehl nicht verfügbar, schließen Sie zuerst die Installation und Initialisierung der Entwicklungswerkzeuge über die grafische Oberfläche ab.

struct IntRing {
    let capacity: Int
    private var storage: [Int?]
    private var head = 0
    private(set) var count = 0

    init(capacity: Int) {
        precondition((1...1_000_000).contains(capacity))
        self.capacity = capacity
        storage = Array(repeating: nil, count: capacity)
    }

    mutating func append(_ value: Int) -> Bool {
        guard count < capacity else { return false }
        storage[(head + count) % capacity] = value
        count += 1
        return true
    }

    mutating func pop() -> Int? {
        guard count > 0 else { return nil }
        let value = storage[head]!
        storage[head] = nil
        head = (head + 1) % capacity
        count -= 1
        return value
    }

    mutating func appendBatch(_ values: [Int]) -> Int {
        var accepted = 0
        for value in values {
            guard append(value) else { break }
            accepted += 1
        }
        return accepted
    }

    func snapshot() -> [Int] {
        (0..<count).map {
            storage[(head + $0) % capacity]!
        }
    }
}

Das erzwungene Entpacken stützt sich hier auf eine interne Invariante: Im logisch belegten Bereich muss jeder Speicherplatz einen Wert enthalten. Verletzt die Implementierung diese Invariante, soll der Test unmittelbar fehlschlagen, statt den Fehler mit einem Standardwert zu verdecken. Das Leeren des Speicherplatzes nach dem Lesen sorgt außerdem dafür, dass Objekte bei einer späteren Umstellung auf Referenztypen zeitnah freigegeben werden können.

Mit kleinen Kapazitäten Umlauffehler aufdecken

Hängen Sie den folgenden Code an das Dateiende an. Im Szenario mit Kapazität drei wird der Puffer zunächst gefüllt. Danach werden zwei Elemente entnommen, bevor weitere Schreibvorgänge über das Arrayende hinweg zum Anfang zurückkehren. Eine Kapazität von eins deckt dagegen auf, wenn die Konvention eines freizuhaltenden Speicherplatzes mit dem hier gewählten Kapazitätsvertrag vermischt wird.

var ring = IntRing(capacity: 3)
precondition(ring.appendBatch([10, 20, 30]) == 3)
precondition(!ring.append(99))
precondition(ring.snapshot() == [10, 20, 30])
precondition(ring.pop() == 10)
precondition(ring.pop() == 20)
precondition(ring.appendBatch([40, 50, 60]) == 2)
precondition(ring.snapshot() == [30, 40, 50])
precondition(ring.pop() == 30)
precondition(ring.pop() == 40)
precondition(ring.pop() == 50)
precondition(ring.pop() == nil)
precondition(ring.count == 0)

var single = IntRing(capacity: 1)
precondition(single.pop() == nil)
precondition(single.append(7))
precondition(!single.append(8))
precondition(single.pop() == 7)
precondition(single.appendBatch([]) == 0)

Prüfen Sie insbesondere den Snapshot nach einem abgewiesenen Schreibvorgang. Nur den Rückgabewert false zu kontrollieren, reicht nicht: Eine fehlerhafte Implementierung könnte zunächst einen Index weiterschieben und erst danach feststellen, dass der Puffer voll ist. Dasselbe gilt für das Lesen aus einem leeren Puffer. Dabei darf sich die Position des nächsten gültigen Lesevorgangs nicht unbemerkt ändern.

Mit festem Startwert Schritt für Schritt gegen eine Referenzwarteschlange prüfen

Sind die Grenzfälle bestanden, ergänzen Sie einen modellbasierten Test. Als Referenzmodell dient ein gewöhnliches Array. Das Entfernen am Anfang ist zwar langsamer, doch bei den kleinen Kapazitäten ist hier die einfache Überprüfbarkeit wichtiger. Werden Inhalt und Anzahl nach jedem Schritt verglichen, lässt sich die erste Abweichung leichter finden als bei einer reinen Kontrolle des Endergebnisses.

var seed: UInt64 = 0x5EED
func next() -> UInt64 {
    seed = seed &* 6364136223846793005 &+ 1
    return seed
}

for capacity in [1, 2, 3, 7] {
    var tested = IntRing(capacity: capacity)
    var model: [Int] = []

    for step in 0..<20_000 {
        if (next() >> 32) % 2 == 0 {
            let value = Int(next() % 10_000)
            let accepted = model.count < capacity
            precondition(tested.append(value) == accepted)
            if accepted { model.append(value) }
        } else {
            let expected = model.isEmpty ? nil : model.removeFirst()
            precondition(tested.pop() == expected)
        }

        precondition(
            tested.snapshot() == model,
            "capacity=\(capacity), step=\(step)"
        )
        precondition(tested.count == model.count)
    }
}

Führen Sie swift RingCheck.swift aus. Der Test gilt nur dann als bestanden, wenn das Programm regulär endet und keine Zusicherung fehlschlägt. Daraus folgt keine Aussage zur Performance; die Schleifenanzahl bestimmt lediglich den Testumfang. Für Stapelschreibvorgänge sollten Sie zusätzlich drei explizite Fälle prüfen: kein freier Speicherplatz, genau ausreichend Platz und ein Speicherplatz zu wenig. Kontrollieren Sie dabei sowohl die zurückgegebene Anzahl als auch den nicht angenommenen Suffix der Eingabe.

Der Generator wählt die Operation anhand der höherwertigen Bits. So wird verhindert, dass regelmäßige Muster in den niederwertigen Bits eines einfachen Generators zu einem mechanischen Wechsel der Operationen führen. Halten Sie für die Reproduktion den ursprünglichen Startwert, die Kapazität und den fehlgeschlagenen Schritt fest, nicht nur den Generatorzustand zum Zeitpunkt des Fehlers.

In das Projekt integrieren und die Einsatzgrenzen einhalten

Sobald das eigenständige Skript alle Prüfungen besteht, verschieben Sie den Typ in das Modul mit der Geschäftslogik und ersetzen die Zusicherungen durch Gleichheitsprüfungen des Testframeworks. Behalten Sie mindestens die folgenden drei Prüfkategorien bei:

• Zustandsbedingungen: Die Anzahl liegt stets zwischen null und der Kapazität. Die Snapshots vor und nach einer fehlgeschlagenen Operation sind vollständig identisch.
• Reihenfolgebedingungen: Auch wiederholte Werte und negative Zahlen müssen in der Reihenfolge ihrer Annahme zurückgegeben werden. Ein Mengenvergleich darf den Arrayvergleich nicht ersetzen.
• Bedingungen für Stapeloperationen: Der Rückgabewert entspricht der Anzahl tatsächlich geschriebener Elemente. Den nicht angenommenen Suffix darf der Aufrufer nicht als bereits verarbeitet behandeln.

Bietet die Geschäftslogik eine Operation zum Leeren an, testen Sie diese jeweils bei leerem, vollem und bereits umgelaufenem Puffer. Füllen Sie den Puffer anschließend erneut vollständig, um sicherzustellen, dass alte Daten nicht wieder auftauchen. Wird der Elementtyp generisch, muss zusätzlich die Freigabe von Referenzen geprüft werden. Bestandene Integer-Tests belegen keine korrekte Lebensdauerverwaltung.

Diese Implementierung eignet sich nur für sequenziellen Zugriff. Sie ist keine lockfreie Warteschlange und darf auch nicht unverändert in einem Audio-Callback mit Echtzeitanforderungen eingesetzt werden. Soll sie von mehreren Tasks gemeinsam genutzt werden, legen Sie zuerst die Synchronisationsgrenzen fest und testen Sie anschließend das nebenläufige Verhalten. Reichen Sie schließlich die Implementierung, die Grenzfalltests und den Modelltest mit festem Startwert gemeinsam ein. So lässt sich auch die nächste Änderung am Indexalgorithmus anhand derselben Kriterien abnehmen.

Häufig gestellte Fragen