Проверка стабильной очереди приоритетов iOS на облачном Mac

Очередь с приоритетами часто нужна для предзагрузки изображений, ожидающих отправки файлов и упорядочивания локальных задач. На Mac разработчика легко получить правильный результат, если последовательно добавить три задачи, а затем извлечь их одну за другой. Но в регрессионных тестах на облачном Mac, где добавление чередуется с извлечением, задачи с одинаковым приоритетом могут начать меняться местами. Вместо полноценного планировщика мы выделим двоичную кучу на Swift в отдельный компонент и проверим, всегда ли она соблюдает контракт упорядочивания.

Определяем приоритет и стабильность

В этой статье действует правило: чем меньше числовое значение приоритета, тем раньше извлекается элемент. При равных значениях первым извлекается тот, который был добавлен раньше. Идентификатор задачи — это прикладные данные, в сравнении он не участвует. Повторное добавление той же задачи считается новой записью и получает новый порядковый номер.

Сначала запишем эти правила как требования к тестам, а затем реализуем структуру данных. Нельзя использовать индекс массива в качестве постоянного порядкового номера: при извлечении и обмене элементов индексы меняются, и гарантировать стабильность уже не получится. Также не стоит определять порядок вычитанием приоритетов: на предельных целочисленных значениях это может вызвать переполнение.

Стабильность не означает справедливость. Если задачи с высоким приоритетом поступают непрерывно, задачи с низким приоритетом могут ждать очень долго. Повышение приоритета по мере ожидания и квоты относятся к политике планирования; их нельзя незаметно встраивать в функцию сравнения кучи.

Приведённая ниже реализация — тип-значение, рассчитанный только на последовательный доступ. При интеграции в конкурентный код доступ следует централизовать в рамках одной границы изоляции: несколько задач не должны одновременно изменять один и тот же экземпляр.

Реализуем минимальную кучу с порядковыми номерами

Сохраните код в main.swift. Ключ сравнения состоит из приоритета и возрастающего порядкового номера. И просеивание вверх при добавлении, и просеивание вниз при извлечении должны использовать одну функцию сравнения, иначе эти два пути могут по-разному определять, какой элемент должен идти первым.

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

Когда счётчик достигает верхней границы, реализация явно сообщает об ошибке. Она не допускает перехода через максимум и не сбрасывает счётчик незаметно после опустошения очереди. Само максимальное значение остаётся неиспользованным, поэтому ошибка возникает до изменения массива. Тест должен подтвердить, что отказ не меняет порядок уже добавленных записей.

Чередуем операции, чтобы выявить ошибки просеивания вниз

Добавьте следующий фрагмент в конец того же файла. Он проверяет не только итоговый порядок, но и то, что после извлечения одного элемента и добавления задачи с тем же приоритетом старые записи по-прежнему опережают новую.

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)

В рабочем каталоге на облачном Mac выполните:

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

При успехе вывода не будет; при ошибке ненулевой код завершения остановит задание. Здесь не используется assert, чтобы проверки не исчезли в оптимизированной сборке. Успешная компиляция тоже не заменяет проверку при выполнении.

Добавьте ещё три группы детерминированных тестов: сохранение входного порядка при одинаковых приоритетах; извлечение по возрастанию после добавления всех элементов с приоритетами в обратном порядке; извлечение одного из двух элементов с последующим многократным чередованием добавления и извлечения. Последняя группа хорошо выявляет выход за границы массива при отсутствии правого потомка.

Расширяем покрытие с помощью эталонной модели

Тесты, написанные вручную, наглядно описывают контракт, но едва ли охватят все формы кучи. Для эталонной модели достаточно массива записей «номер задачи, приоритет, порядковый номер добавления», который перед каждым извлечением сортируется по двум последним полям. Такая модель медленная, зато простая, поэтому хорошо подходит для проверки результатов в небольших тестах.

При генерации смешанной последовательности операций каждое добавление нужно повторять в модели. При каждом извлечении сравнивайте возвращаемые обеими сторонами опциональные номера задач, а после завершения последовательности полностью опустошите обе очереди. Сравнивать только приоритеты недостаточно: перестановка задач с одинаковым приоритетом тоже считается дефектом.

Используйте генератор псевдослучайных чисел с задаваемым начальным значением, а не источник случайности, результаты которого нельзя воспроизвести. При сбое сохраняйте как минимум начальное значение генератора, индекс операции, полную последовательность операций до сбоя включительно и результаты обеих сторон. Для локализации ошибки удаляйте из этой последовательности фрагменты, оставляя кратчайшую последовательность, на которой сбой сохраняется.

Обеспечиваем независимость модели от реализации

Эталонная модель не должна повторно использовать функцию сравнения кучи. Иначе одна и та же ошибка окажется с обеих сторон, и проверка пройдёт. Модель может сначала сравнивать приоритеты и лишь при их равенстве выбирать запись, добавленную раньше остальных: так прикладное правило выражается напрямую.

Включаем проверки в регрессионный набор и ограничиваем выводы

Перед коммитом обязательно запускайте тесты пустой очереди, одного элемента, стабильности при равных приоритетах, предельных целочисленных значений и чередования операций. Затем выполняйте сравнение с моделью на фиксированном наборе начальных значений генератора. Новые значения, на которых обнаружен сбой, добавляйте в постоянный регрессионный набор, а не ограничивайтесь повторным запуском с увеличенным числом случайных проверок.

Исчерпание порядковых номеров невозможно практически проверить обычным количеством добавлений. В полноценном модуле можно предусмотреть внутренний способ инициализации только для тестов, позволяющий установить счётчик непосредственно перед верхней границей. Это даст возможность проверить последнее допустимое добавление и отказ при следующем, не открывая публичный интерфейс для изменения рабочего состояния.

Достаточно архивировать версию инструментария Swift, идентификатор коммита и последовательность операций, приведшую к сбою. Прикладные данные сохранять не нужно. В итоговом заключении следует явно указать: здесь проверены порядок и поведение на границах для очереди с последовательным доступом, но не потокобезопасность, доля успешно выполненных задач или справедливость планирования. Если обозначить эти границы заранее, при последующем подключении исполнителя тесты структуры данных не будут ошибочно восприниматься как гарантия корректности всей системы.

Часто задаваемые вопросы