Valider une file de priorité stable pour iOS sur un Mac distant

Le préchargement d’images, les envois en attente et l’ordonnancement de tâches locales font souvent appel à une file de priorité. Sur la machine de développement, ajouter trois tâches d’affilée puis les retirer une à une donne facilement le résultat attendu. Mais dans les tests de régression exécutés sur un Mac distant, dès que les insertions et les retraits s’entremêlent, des tâches de même priorité peuvent changer de place. Il ne s’agit pas ici de construire un ordonnanceur complet, mais d’isoler un tas binaire en Swift pour vérifier qu’il respecte toujours son contrat d’ordre.

Définir la priorité et la stabilité

Nous retenons les règles suivantes : plus la valeur numérique de la priorité est faible, plus la tâche sort tôt de la file ; à priorité égale, la première tâche entrée est la première à sortir. L’identifiant d’une tâche reste une donnée métier et n’intervient pas dans la comparaison. Si une même tâche est remise en file, elle constitue une nouvelle entrée et reçoit un nouveau numéro d’insertion.

Commencez par formaliser ces règles dans les tests, puis implémentez la structure de données. N’utilisez pas l’indice dans le tableau comme numéro d’insertion permanent : les retraits et les échanges modifient les indices, ce qui empêche de garantir la stabilité. Évitez aussi de soustraire les priorités pour les comparer : avec des valeurs entières extrêmes, cette opération peut provoquer un dépassement de capacité.

La stabilité n’est pas synonyme d’équité. Si des tâches hautement prioritaires arrivent sans interruption, les tâches moins prioritaires peuvent rester longtemps en attente. Le vieillissement des priorités et les quotas relèvent de la politique d’ordonnancement ; ils ne doivent pas être introduits implicitement dans la fonction de comparaison du tas.

L’implémentation ci-dessous est un type valeur, réservé à un accès séquentiel. Pour l’intégrer à un traitement concurrent, confiez sa gestion à un unique périmètre d’isolation : plusieurs tâches ne doivent pas modifier la même instance simultanément.

Implémenter un tas min avec numéro d’insertion

Enregistrez ce code dans main.swift. La clé de comparaison associe la priorité à un numéro croissant. La remontée à l’insertion et la descente au retrait doivent utiliser la même fonction de comparaison, afin que ces deux chemins appliquent exactement la même définition de l’ordre.

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

Lorsque le compteur atteint sa limite, une erreur est explicitement levée : il ne reboucle pas et n’est pas non plus remis discrètement à zéro lorsque la file est vidée. Cette implémentation laisse la valeur maximale inutilisée afin que l’échec survienne avant toute modification du tableau. Un test doit vérifier que cet échec ne change pas l’ordre des entrées déjà présentes.

Détecter les erreurs de descente avec des opérations entrelacées

Ajoutez l’extrait suivant à la fin du même fichier. Il vérifie non seulement l’ordre final, mais aussi qu’après un retrait suivi de l’insertion d’une tâche de même priorité, les anciennes entrées restent devant la nouvelle.

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)

Dans le répertoire de travail du Mac distant, exécutez :

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

En cas de succès, le programme ne produit aucune sortie. En cas d’échec, un code de sortie non nul interrompt le traitement. Nous n’utilisons pas assert, pour éviter que les vérifications soient supprimées dans une compilation optimisée. Une compilation réussie ne remplace pas non plus la validation à l’exécution.

Ajoutez ensuite trois groupes de cas déterministes : toutes les entrées ont la même priorité et conservent leur ordre d’arrivée ; les priorités sont insérées en ordre décroissant, puis retirées en ordre croissant ; la file ne contient que deux éléments, l’un est retiré, puis les insertions et les retraits s’enchaînent. Ce dernier groupe révèle facilement les accès hors limites lorsque le fils droit n’existe pas.

Étendre la couverture avec un modèle de référence

Les cas écrits à la main illustrent le contrat, mais couvrent difficilement toutes les formes possibles du tas. Le modèle de référence peut simplement stocker dans un tableau l’identifiant de chaque tâche, sa priorité et son numéro d’insertion, puis trier les entrées sur ces deux derniers critères avant chaque retrait. Cette approche est lente, mais sa simplicité en fait un bon arbitre pour des tests de petite taille.

Lors de la génération d’opérations entrelacées, répercutez chaque insertion dans le modèle. À chaque retrait, comparez les identifiants optionnels obtenus des deux côtés, puis videz entièrement les deux structures à la fin des opérations. Comparer uniquement les priorités ne suffit pas : une permutation entre tâches de même priorité constitue elle aussi un défaut.

Utilisez un générateur pseudo-aléatoire dont la graine peut être fixée, plutôt qu’une source de hasard ne permettant pas de rejouer la séquence. Pour chaque échec, consignez au minimum la graine, l’indice de l’opération, le préfixe complet des opérations et les résultats des deux côtés. Pour isoler le problème, supprimez progressivement des portions de ce préfixe afin de conserver la séquence la plus courte qui reproduit encore l’échec.

Garantir l’indépendance du modèle et de l’implémentation

Le modèle de référence ne doit pas réutiliser la fonction de comparaison du tas : une même erreur pourrait alors passer inaperçue des deux côtés. Le modèle peut comparer d’abord les priorités, puis, uniquement en cas d’égalité, choisir l’entrée insérée le plus tôt. Il exprime ainsi directement la règle métier.

Intégrer les tests de régression et délimiter les conclusions

Avant chaque commit, exécutez systématiquement les tests de file vide, d’élément unique, de stabilité à priorité égale, de valeurs entières extrêmes et d’opérations entrelacées, puis une série de comparaisons avec le modèle à partir de graines fixes. Toute nouvelle graine révélant un échec doit rejoindre la suite de régression permanente. Ne vous contentez pas d’augmenter le nombre d’essais aléatoires avant de relancer les tests.

Il n’est pas réaliste d’atteindre l’épuisement des numéros de séquence par des insertions ordinaires. Dans le module destiné à la production, vous pouvez prévoir un initialiseur interne réservé aux tests pour placer le compteur juste avant sa limite. Vérifiez alors la frontière entre la dernière insertion autorisée et la suivante, qui doit être refusée, sans exposer d’interface publique permettant de modifier l’état de production.

Il suffit d’archiver la version de la chaîne d’outils Swift, l’identifiant du commit et la séquence d’opérations en échec ; les données métier n’ont pas besoin d’être conservées. La conclusion de la validation doit être explicite : ces tests établissent l’ordre et le comportement aux limites d’une file utilisée séquentiellement. Ils ne garantissent ni la sûreté vis-à-vis des accès concurrents, ni le taux de réussite des tâches, ni l’équité de l’ordonnancement. En précisant ces limites, vous éviterez, lors de l’intégration ultérieure à un exécuteur, de prendre les tests de la structure de données pour une garantie portant sur tout le système.

Questions fréquentes