Поисковый рефакторинг: модуляризация монолита и уборка кода как задача оптимизации

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

Начнём с самой соблазнительной и самой опасной задачи SBSE. Соблазнительной — потому что каждый, кто открывал легаси-монолит на 900 классов, мечтал нажать кнопку «разложи это по-человечески». Опасной — потому что «по-человечески» плохо превращается в число, а поиск оптимизирует ровно число.

Почему это вообще задача поиска

Вспомним асимметрию, на которой стоит вся дисциплина: сделать трудно, оценить легко. Для модуляризации она выполняется лишь наполовину.

• «Сделать трудно» — безусловно. Разложить $n$ классов по модулям — это число Белла $B_n$ вариантов, для $n = 900$ оно не помещается в воображение. Ручной перебор невозможен, эксперт держит в голове десяток классов, а не девятьсот.
• «Оценить легко» — только если согласиться на суррогат. Настоящая цель («модули понятны, изменения локальны, команды не мешают друг другу») не считается автоматически. Считается связность и зацепление на графе зависимостей — а это лишь коррелирующий с целью показатель.

Отсюда главное правило, которое стоит принять до первой строчки кода:

Поиск в задачах сопровождения производит кандидатов на ревью, а не готовые изменения. Единица результата — пул-реквест с объяснением «что улучшилось и на сколько», а не коммит в master.

Именно поэтому в квадранте из обзорной статьи модуляризация висит правее и ниже генерации тестов: пространство огромно, но сигнал фитнеса слабее. Слабый сигнал — не повод не применять поиск, повод не доверять его результату слепо.

Две разные задачи под одним словом «рефакторинг»

В литературе (и в разговорах) их постоянно путают, хотя это два разных поисковых проекта с разными представлениями, операторами и стоимостью оценки.

Разберём обе — сначала дешёвую и практичную, потом дорогую и амбициозную.

Часть I. Ремодуляризация: граф зависимостей и метрика MQ

Граф модульных зависимостей

Вход поиска — MDG (module dependency graph): узлы — классы, файлы или пакеты; рёбра — зависимости (импорт, вызов, наследование, использование типа). Строится статическим анализом за один проход по AST или по выводу компилятора. Для Python — ast и importlib, для Java — jdeps, для Go — go list -deps, для C# — анализ сборок Roslyn.

Практический нюанс, о котором забывают: у рёбер есть второй источник — история изменений. Если два файла в 70 % коммитов меняются вместе, между ними есть связь, даже если ни один не импортирует другой (общий формат, неявный контракт, копипаста). Это называют evolutionary coupling или co-change, и добывается оно из git одним запросом по истории. Практика, которая работает: строить MDG как сумму двух графов — статического и эволюционного — с весами, потому что вторая половина ловит именно те связи, которые ломаются при переносе кода. Про то, как из истории монорепозитория вообще извлекают такие данные, — в статье о монорепозиториях.

Фитнес: Modularization Quality

Классическая метрика пришла из системы Bunch (Mancoridis и соавторы, «Using automatic clustering to produce high-level system organizations of source code», IWPC 1998). Для каждого кластера $i$ считается modularization factor:

$$MF_i = \frac{\mu_i}{\mu_i + 0.5 \cdot \varepsilon_i}$$

где $\mu_i$ — число рёбер внутри кластера, $\varepsilon_i$ — число рёбер, пересекающих его границу. Итоговое $MQ = \sum_i MF_i$ (вариант TurboMQ). Интуиция простая: каждый кластер получает от 0 до 1 — долю «своих» связей, — а система суммирует. Коэффициент 0.5 — потому что внешнее ребро принадлежит двум кластерам сразу, каждому по половине.

Метрика устроена так, чтобы сопротивляться двум вырожденным решениям, к которым поиск скатился бы мгновенно:

• всё в одном модуле — внешних рёбер нет, но кластер один, значит $MQ \le 1$;
• каждый класс в своём модуле — внутренних рёбер нет, каждый $MF_i = 0$, значит $MQ = 0$.

Проверим на примере из картинки выше: 13 классов, 18 зависимостей. Для нарезки «всё в одном» $MQ = 1.00$, для «каждый сам по себе» $MQ = 0.00$, для экспертной нарезки на три модуля $MQ = 2.29$ при теоретическом максимуме 3.00. Метрика ведёт себя разумно — но, как увидим через двадцать строк, не идеально.

Инкрементальный пересчёт — единственная нетривиальная часть реализации

Полный пересчёт MQ стоит $O(E)$. При 20 000 рёбер и 20 000 оценок это 4·10⁸ операций на прогон — поиск станет неприлично медленным на ровном месте. Но оператор соседства переносит один узел, значит меняются только рёбра этого узла: обновление стоит $O(\deg(v))$. Ровно тот приём «оптимизируйте фитнес, а не алгоритм», о котором говорилось в обзоре.

"""Ремодуляризация: TurboMQ с инкрементальным пересчётом + восхождение с рестартами."""
from __future__ import annotations

import random
from collections import defaultdict


def build_mdg(edges: list[tuple[str, str]]) -> dict[str, set[str]]:
    """Граф модульных зависимостей. Направление для MQ не важно — важна связанность."""
    g: dict[str, set[str]] = defaultdict(set)
    for a, b in edges:
        if a == b:
            continue          # самозависимость ничего не говорит о границах модулей
        g[a].add(b)
        g[b].add(a)
    return dict(g)


class Modularization:
    """Назначение «узел -> кластер» плюс счётчики рёбер для инкрементального MQ."""

    def __init__(self, graph: dict[str, set[str]], assign: dict[str, int]):
        self.g = graph
        self.assign = dict(assign)
        self.intra: dict[int, int] = defaultdict(int)   # рёбра внутри кластера
        self.ext: dict[int, int] = defaultdict(int)     # рёбра, пересекающие границу
        for a, nbrs in graph.items():
            for b in nbrs:
                if a >= b:
                    continue                            # каждое ребро считаем один раз
                ca, cb = self.assign[a], self.assign[b]
                if ca == cb:
                    self.intra[ca] += 1
                else:
                    self.ext[ca] += 1
                    self.ext[cb] += 1
        self.mq = sum(self._mf(c) for c in set(self.assign.values()))

    def _mf(self, c: int) -> float:
        """MF = i / (i + 0.5 * e). Кластер без внутренних связей получает 0."""
        i, e = self.intra[c], self.ext[c]
        return 0.0 if i == 0 else i / (i + 0.5 * e)

    def move(self, node: str, dst: int) -> float:
        """Перенос узла с пересчётом MQ за O(deg(node)) вместо O(E)."""
        src = self.assign[node]
        if src == dst:
            return self.mq
        # затронуты только кластер-источник, кластер-приёмник и кластеры соседей
        touched = {src, dst} | {self.assign[u] for u in self.g.get(node, ())}
        self.mq -= sum(self._mf(c) for c in touched)

        for u in self.g.get(node, ()):
            cu = self.assign[u]
            if cu == src:                # ребро было внутренним для src
                self.intra[src] -= 1
            else:                        # ребро пересекало границу src
                self.ext[src] -= 1
                self.ext[cu] -= 1
            if cu == dst:                # станет внутренним для dst
                self.intra[dst] += 1
            else:                        # станет пересекающим границу dst
                self.ext[dst] += 1
                self.ext[cu] += 1

        self.assign[node] = dst
        self.mq += sum(self._mf(c) for c in touched)
        return self.mq

    def clusters(self) -> dict[int, list[str]]:
        out: dict[int, list[str]] = defaultdict(list)
        for n, c in self.assign.items():
            out[c].append(n)
        return {c: sorted(v) for c, v in out.items() if v}


def hill_climb(graph, evaluations: int, seed: int = 0) -> tuple[dict[str, int], float]:
    """Восхождение по переносам одного узла. Стартуем из «каждый класс сам по себе»:
    это худшая точка по MQ, зато не навязывает поиску структуру, которую мы ожидаем увидеть."""
    rnd = random.Random(seed)
    nodes = sorted(graph)
    state = Modularization(graph, {n: i for i, n in enumerate(nodes)})
    best_assign, best_mq = dict(state.assign), state.mq
    used = stagnation = 0

    while used < evaluations:
        node = rnd.choice(nodes)
        src = state.assign[node]
        dst = rnd.randrange(len(nodes))       # включая пустой кластер = «выделить в свой модуль»
        if dst == src:
            continue
        before = state.mq
        after = state.move(node, dst)
        used += 1
        if after >= before:                   # >= пропускает нейтральные шаги по плато
            if after > best_mq:
                best_assign, best_mq, stagnation = dict(state.assign), after, 0
            else:
                stagnation += 1
        else:
            state.move(node, src)             # откат тоже O(deg), не считается оценкой
            stagnation += 1
        if stagnation > 20 * len(nodes):      # застряли — рестарт из случайной нарезки
            state = Modularization(graph, {n: rnd.randrange(1, 8) for n in nodes})
            stagnation = 0
    return best_assign, best_mq

На графе с картинки (13 узлов, 18 рёбер, бюджет 20 000 переносов, 30 запусков с разными seed) восхождение стабильно даёт медиану $MQ = 2.753$ против экспертных 2.29 — и это самый поучительный результат статьи. Поиск нашёл решение лучше человеческого по метрике, разрезав систему не на 3 модуля, а на 5: billing распался на «деньги» и «документы», catalog — на «товар» и «поставки». Метрика довольна: мелкие плотные комки дают высокий $MF$ каждый.

Это не баг реализации, это свойство MQ, известное с первых работ: метрика любит дробить. Лечится тремя способами, и обычно нужны все три:

1. Ограничить число кластеров сверху и снизу (жёстко или штрафом за отклонение).
2. Ограничить размер кластера: модуль из двух классов не модуль, из двухсот — не модуль тоже.
3. Перейти к многокритериальной постановке, где размер и число кластеров — отдельные цели, а не спрятанные в одну сумму штрафы.

Многокритериальная ремодуляризация

Третий путь — канонический для SBSE и разобран в статье про Парето и NSGA-II. Правильная ссылка здесь — Praditwong, Harman, Yao, «Software Module Clustering as a Multi-Objective Search Problem», IEEE TSE 2011. Авторы разложили MQ на пять отдельных целей:

Результат: Парето-подход находит нарезки, которые по совокупности лучше, чем оптимизация одного MQ, и — важнее — отдаёт архитектору фронт вариантов: «вот 6 модулей покрупнее, вот 11 помельче, выбирайте». Для человека, принимающего решение, это принципиально удобнее одного «оптимума».

Как понять, что нарезка хорошая

Три уровня проверки, от академического к продакшн-годному.

1. MoJoFM — расстояние между двумя декомпозициями в терминах числа операций Move и Join, нормированное в проценты (Wen, Tzerpos, «An effectiveness measure for software clustering algorithms», IWPC 2004). Считается против «авторитетной» декомпозиции, сделанной архитектором системы. Хорошо для сравнения алгоритмов между собой, бесполезно, если авторитетной декомпозиции нет.
2. Стабильность. Прогоните поиск 30 раз с разными seed и посчитайте, как часто пары классов оказываются вместе. Пары со стабильностью 95 %+ — надёжное ядро, их предлагайте. Пары, которые болтаются, — предмет разговора с архитектором, а не рекомендации.
3. Проверка на будущем. Самая честная и единственная, которая измеряет цель, а не суррогат: возьмите нарезку, посчитанную по истории до какой-то даты, и посмотрите на коммиты после неё — сколько процентов пул-реквестов трогают больше одного модуля. Хорошая нарезка та, при которой типичное изменение локально. Эта метрика прямо соответствует смыслу модульности и считается из git.

Обратите внимание на пунктирную стрелку обратной связи. Решение архитектора «этот класс не двигать» или «эти два модуля не сливать» — это ограничение для следующего запуска, и его надо где-то хранить (файл modularization-constraints.yaml рядом с кодом). Без этого механизма инструмент будет каждый раз предлагать одно и то же отвергнутое изменение и умрёт от раздражения пользователей.

Ограничения реального проекта

В учебной постановке двигать можно всё. В настоящем репозитории — нет:

• публичный API и файлы, на которые смотрят внешние потребители, переносить нельзя без мажорной версии;
• сгенерированный код (protobuf, ORM-модели, клиенты OpenAPI) не двигают руками вообще;
• слоистая архитектура задаёт запрещённые направления рёбер: domain не может зависеть от infrastructure (см. слоистую, гексагональную и чистую архитектуры);
• владение кодом: перенос класса в чужой модуль меняет ревьюеров и дежурства.

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

Связь с DDD и распилом монолита

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

Практический сценарий, который реально работает: перед распилом монолита на модули (см. модульный монолит) прогнать кластеризацию и наложить её на предполагаемые контексты. Классы, попавшие «не в свой» кластер, — это ровно те места, где будущий распил будет болеть.

Часть II. Поиск последовательности рефакторингов

Вторая задача амбициознее: не «как надо было бы разложить», а «какие конкретно операции применить, чтобы код стал лучше». Здесь решение — программа преобразований.

Представление и его коварство

Особь — последовательность операций: Move Method(A.foo -> B), Extract Class(C, {f1,f2}), Pull Up Field(D.x), Inline Method(E.bar). Проблема, которой нет в кластеризации: операции зависят друг от друга. После Extract Class половина последующих операций ссылается на классы, которых уже нет, или нарушает предусловия. Пространство поиска дырявое: большинство случайных последовательностей невалидны целиком.

Три стандартных ответа:

1. Repair при выполнении: применяем операции по очереди, неприменимые молча пропускаем. Дёшево, но фитнес становится «шумным» — одна и та же особь в другом контексте значит другое.
2. Генерация только валидных: оператор мутации спрашивает у движка рефакторинга список применимых сейчас операций и выбирает из него. Дороже, зато пространство связное.
3. Короткие последовательности: 5–15 операций вместо сотни. Ограничение длины — заодно ограничение размера диффа, что нужно и для ревью.

Фитнес: метрики плюс обязательный жёсткий фильтр

Мягкая часть фитнеса — метрики качества кода. Классический набор — QMOOD (Bansiya, Davis, «A hierarchical model for object-oriented design quality assessment», IEEE TSE 2002): шесть характеристик (reusability, flexibility, understandability, functionality, extendibility, effectiveness) выражены через одиннадцать структурных метрик — связность, зацепление, размер, глубину иерархии. Альтернатива или дополнение — число обнаруженных запахов кода: God Class, Feature Envy, Long Method считаются детекторами автоматически, и «минус пять запахов» — понятная человеку цель.

Жёсткая часть — сохранение поведения. Она не входит в фитнес как слагаемое, она отсекает кандидата:

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

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

Что показали исследования

• CODe-Imp (O’Keeffe, Ó Cinnéide) — первая систематическая система поискового рефакторинга Java: hill climbing и отжиг по последовательностям операций, фитнес — метрики качества дизайна. См. «Search-based refactoring for software maintenance», Journal of Systems and Software, 2008.
• Парето вместо взвешенной суммы: Harman, Tratt, «Pareto optimal search based refactoring at the design level», GECCO 2007 — показали, что склеивать связность и зацепление в одну сумму с весами хуже, чем строить фронт: веса подобрать не у кого, а фронт даёт архитектору выбор.
• Многокритериальные рекомендации: Ouni и соавторы добавили к метрикам две очень практичные цели — семантическую связность (не переносить метод туда, где он бессмысленен по именам и типам) и согласие с историей изменений (предпочитать правки, похожие на те, что команда уже делала руками). См. «Maintainability defects detection and correction: a multi-objective approach», ASE Journal, 2013.
• Many-objective и стабильность: Mkaouer и соавторы применили NSGA-III к рефакторингу и добавили цель «минимум отличий от предыдущей рекомендации» — иначе инструмент при каждом запуске предлагает новый план, и доверие к нему исчезает («Many-objective software remodularization using NSGA-III», ACM TOSEM 2015).

Честно о зрелости: промышленных внедрений поискового рефакторинга существенно меньше, чем внедрений генерации тестов. Причина — не в алгоритмах, а в трёх вещах: слабый сигнал фитнеса, дорогая оценка и высокая цена ошибки (сломанный рефакторинг — это инцидент, а лишний тест — просто лишний тест). Ближайший работающий родственник в проде — массовые автоматические правки кода в больших компаниях (codemod-инструменты), но там нет поиска: преобразование задано человеком, машина только применяет его масштабно.

Куда это движется: LLM как генератор, поиск как фильтр

Самое интересное направление сегодня — ровно то, чем закончилась девятая статья. Языковая модель хорошо предлагает рефакторинги, которые выглядят как человеческие, — она снимает ровно ту проблему, с которой не справлялись метрики (семантическая осмысленность). А проверяющий контур остаётся прежним: компиляция, тесты, метрики, размер диффа, ревью. Схема «LLM предлагает — детерминированные фильтры отсеивают» здесь работает лучше, чем в APR, потому что рефакторинг по определению не должен менять поведение, а значит, у фильтра есть точный критерий.

Что отдавать поиску, а что нет

Левый верхний угол — то, что стоит автоматизировать первым и без всякого «умного» поиска: поиск циклов в графе зависимостей и мёртвого кода решается точными алгоритмами (см. обход графов), метаэвристики там просто не нужны. Правый нижний — «улучшить читаемость», «сделать код красивее»: числа нет, а значит, и оптимизировать нечего; попытка приведёт к оптимизации случайного суррогата.

Сложность и бюджет

Практический вывод для планирования: ремодуляризация — задача на ноутбук, даже для монолита на 5 000 классов (миллион оценок MQ считаются минуты). Поиск последовательности рефакторингов — задача на CI-ферму, и первым делом там надо сокращать не число итераций, а стоимость одной проверки: инкрементальная сборка и прогон затронутых тестов дают на порядок больше, чем замена hill climbing на модный алгоритм.

Типичные ошибки

1. Автоприменение результата. Инструмент, который сам мержит рефакторинг, будет выключен после первого же инцидента. Рекомендация и объяснение — единственный жизнеспособный формат.
2. Оптимизация MQ в чистом виде. Метрика дробит систему на мелкие плотные комки. Без ограничений на число и размер кластеров вы получите 40 «модулей» по три класса.
3. Только статический граф. Половина настоящих связей — неявные (общий формат данных, общий конфиг, копипаста). Co-change из истории ловит их и обычно улучшает результат сильнее, чем смена алгоритма.
4. Игнорирование стабильности рекомендаций. Если инструмент каждый запуск предлагает другое — он бесполезен, даже если каждое предложение по отдельности разумно. Считайте частоту совместного попадания пар по 30 запускам и показывайте только устойчивое ядро.
5. Метрика как цель (закон Гудхарта). Рост QMOOD на 0.1 не является ценностью сам по себе; ценность — меньше времени на изменение и меньше инцидентов. Про этот разрыв стоит прочитать про метрики и закон Гудхарта.
6. Рефакторинг без надёжных тестов. При слабом покрытии поиск найдёт «улучшение», которое ломает непокрытое поведение, и вы узнаете об этом в проде.
7. Гигантский дифф. Технически корректный перенос 400 файлов не пройдёт ревью никогда. Размер изменения — такая же цель оптимизации, как связность.
8. Отсутствие памяти об отказах. Отвергнутые архитектором границы обязаны стать ограничениями, иначе инструмент будет предлагать их снова и снова.

Мини-итог

• Ремодуляризация и поиск последовательности рефакторингов — две разные задачи: первая дешёвая и работающая, вторая дорогая и пока преимущественно исследовательская.
• Фитнес для кластеризации — MQ и его многокритериальные наследники; метрика склонна дробить систему, поэтому ограничения на число и размер кластеров обязательны.
• Инкрементальный пересчёт фитнеса ($O(\deg v)$ вместо $O(E)$) — то, что делает задачу решаемой на ноутбуке.
• Граф зависимостей стоит строить из двух источников: статического анализа и co-change из git.
• Для последовательностей рефакторингов сохранение поведения — жёсткий фильтр (компиляция + тесты), а не слагаемое фитнеса; стоимость оценки измеряется минутами, и это определяет весь дизайн.
• Результат поиска в задачах сопровождения — всегда предложение человеку: маленький дифф, объяснённые метрики, память об отказах.

Источники

• Mancoridis et al. «Using automatic clustering to produce high-level system organizations of source code», IWPC 1998 — система Bunch и метрика MQ.
• Praditwong, Harman, Yao. «Software Module Clustering as a Multi-Objective Search Problem», IEEE TSE 2011.
• Wen, Tzerpos. «An effectiveness measure for software clustering algorithms», IWPC 2004 — MoJoFM.
• Bansiya, Davis. «A hierarchical model for object-oriented design quality assessment», IEEE TSE 2002 — QMOOD.
• Fowler. «Refactoring: Improving the Design of Existing Code» — каталог операций, который поиск использует как алфавит.
• Остальные работы по поисковому рефакторингу — по ссылкам в разделе «Что показали исследования».

Что дальше

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

Конфигурируемые системы: покрывающие массивы, модели фич и поиск по конфигурациям