Читання коду для складності

Grep знаходить кандидатів. Читання їх підтверджує. Коли ви відкриваєте файл кандидата, ви читаєте з одним питанням: чи вартість цієї операції зростає з розміром входу?

Для MOAD-0001 протокол підтвердження:

1. Find the outer loop. What bounds its iteration count?
2. Find the inner operation (.contains, .indexOf, 'in'). What data structure does it run against?
3. Does that data structure grow with the same input that drives the outer loop?
4. If yes: the cost is O(N²) where N = input size. Confirmed defect.
5. If no: the inner structure is bounded (config, enum, small constant). False positive.

Обхід графу, що відвідує N вузлів, перевіряючи список visited на кожному кроці: та цикл, та внутрішня структура даних зростають з N. Підтверджено.

Обробник запиту, що перевіряє список дозволів з 5 IP адрес адміна: список дозволів ніколи не зростає з обсягом запитів. Хибний позитив.

Той же протокол застосовується до кожного MOAD: визначте зовнішній драйвер, визначте внутрішню структуру, запитайте себе, чи обидва масштабуються разом.

Оцінка прилипу: визначення пріоритету для своїх знахідок

Не всі підтверджені вади потребують негайного виправлення. MOAD в бібліотеці з 10,000 залежних проектів має вищу оцінку прилипу, ніж той же MOAD в приватному внутрішньому інструменті.

Оцінка прилипу = прискорення × in-degree. Прискорення: наскільки швидше виконується виправлення на типовому масштабі виробництва? In-degree: скільки нижчестоящих пакетів або сервісів успадковуватимуть виправлення автоматично, коли апстрім його об'єднає?

Підтвердженний MOAD-0001 в роздільнику залежностей Apache Maven, що виконується на графах з 50,000 вузлами, з 1,000+ залежних плагінів Maven, які успадковують зміни автоматично: оцінка прилипу дуже висока. Це виправлення належить до переднього краю вашої черги.

Підтвердженний MOAD-0001 в CLI інструменті для одного користувача без залежних проектів: оцінка прилипу близька до нуля. Варто виправити, але не терміново.

Трудяга проти обжери. Вузол з високою центральністю середини та високим прискоренням — це трудяга: він обробляє критичний потік та промиває нижчестоящі черги при розблокуванні. Виправляйте його тільки після підтвердження нижчестоящої ємності. Вузол з високим ступенем виходу та низьким прискоренням — це обжера: споживає все, що йому дають, та не відчуває болю. Виправлення трудяги без підготовки нижчестоящої ємності створює MOAD-0005 (грозова череда) в масштабі інфраструктури.

Від сканування до злиття: MOAD конвеєр

Підтверджена вада з високою оцінкою прилипу проходить конвеєр. Кожен етап створює артефакт. Жоден етап не є факультативним.

scan    → candidate list (grep output, static analysis results)
ticket  → defect description (MOAD number, location, complexity analysis)
patch   → code change (data structure swap, primitive adoption)
test    → unit test (O(1) proof: time the fix at N=100 and N=10,000)
UNDF    → public disclosure post (undefect.com, public domain)
disclose → CVE or CWE reference if security-relevant
PR      → upstream pull request with patch + test + UNDF link
merge   → maintainer acceptance; fix propagates via version bump

Кожен артефакт живить наступний етап. Патч без тесту не можна перевірити. Тест без розкриття не може поширитися на інші екземпляри того ж патерну. Розкриття без апстрім PR залишає виправлення у форці.

MOAD пост (UNDF) — це етап, який найбільш інженерів пропускають. Вони виправляють ваду, подають PR, та вважають себе готовими. Але виправлення без названого посту означає, що кожен майбутній інженер, який зустріне той же патерн, повинен буде перевідкрити як проблему, так й виправлення самостійно. MOAD пост закриває цикл знань: він називає патерн, показує метод виявлення, та посилається на патч. Майбутні дослідники знаходять виправлення, шукаючи за назвою патерну.

Виправлення планети в масштабі. Одне MOAD-0001 виправлення в широко використовуваній бібліотеці поширюється на кожен проект, що її імпортує. MOAD пост забезпечує, що інженери в проектах, які ніколи не оновлюватимуть цю бібліотеку, все ще навчаються виправленню. Обидва шляхи виконуються паралельно.

Написання квитка про ваду

Добрий квиток про ваду відповідає на п'ять питань:

1. Where: exact file, class, function, and line range
2. What: the data structure type and the operation against it
3. Why: the complexity analysis (O(N²) or worse, with N defined)
4. Impact: what inputs trigger worst-case behavior, and at what scale
5. Fix: the data structure or primitive to substitute

Квиток, що відповідає на всі п'ять, є самовміщуючим: супроводжувач, який ніколи не читав вашого аналізу, може відтворити вашу знахідку та перевірити ваше виправлення. Квитки, що пропускають (3) або (4), вимагають від супроводжувача повторити ваш аналіз складності перед об'єднанням. Це тертя зменшує ймовірність об'єднання.

Вірогідність складається. Перший PR, що включає чіткий квиток, добре спрямований патч, та тест продуктивності, отримує об'єднання. Другий PR від того ж автора отримує перегляд з меншим тертям. Третій PR отримує перегляд від супроводжувача, який об'єднав перші два. Репутація в відкритому коді — це реєстр артефактів: кожен прийнятий патч здобуває довіру для наступного.

Читання реального кандидата

Ось реальний кандидат MOAD-0001 в Python. Прочитайте його та виконайте протокол тріажу.

class DependencyResolver:
    def resolve(self, package, resolved=None, seen=None):
        if resolved is None:
            resolved = []
        if seen is None:
            seen = []
        if package in seen:
            return
        seen.append(package)
        for dep in self.registry.get_dependencies(package):
            self.resolve(dep, resolved, seen)
        resolved.append(package)
        return resolved

Питання тріажу:

1. What data structure is `seen`?
2. What operation runs against it on line 6?
3. Does `seen` grow with input size?
4. Does the loop that drives recursive calls also grow with input size?
5. Is this a confirmed MOAD-0001 or a false positive?

Ваш патч

Підтверджена вада з високою оцінкою прилипу потребує повного патчу: виправлення коду, тест, що доводить покращення, та контур посту MOAD.

Тест повинен бути тестом продуктивності, а не тестом коректності. Тест коректності проходить до й після виправлення — це точка; вихід не змінюється. Тест продуктивності при двох розмірах входу доводить покращення:

import time

def build_graph(n):
    # n packages, each depending on the previous one
    return {f'pkg{i}': [f'pkg{i-1}'] if i > 0 else [] for i in range(n)}

for n in [100, 1000, 5000]:
    registry = build_graph(n)
    resolver = DependencyResolver(registry)
    start = time.perf_counter()
    resolver.resolve(f'pkg{n-1}')
    elapsed = time.perf_counter() - start
    print(f'n={n}: {elapsed:.4f}s')

Перед виправленням, час прослідження зростає квадратично з n. Після виправлення він зростає лінійно. Надрукуйте обидва та включіть цифри у опис PR.

Контур посту MOAD охоплює: назву патерну, субстрат (роздільник залежностей Python), метод виявлення (grep для in seen де seen починається як []), виправлення, та посилання на ваш PR. Пост йде на undefect.com як громадська власність. Майбутні інженери, шукаючи 'Python list membership in loop slow', знайдуть це.