Привет, Хабр! Это продолжение истории про Waypoint — PHP-роутер, о создании которого я рассказывал в предыдущей статье. То, что начиналось как эксперимент, похоже, перерастает во что-то большее.

В комментариях к ней развернулась показательная дискуссия. Один из читателей попросил ИИ проанализировать репозиторий и получил ответ: «Это стандартный алгоритм, такой подход используется десятилетиями». Другой заметил, что «и в Symfony, и в FastRoute группировка идёт по trie-like структурам». Справедливо ли это?

Да и нет. Trie — действительно классическая структура данных, описанная в любом учебнике. Хеш-таблица — тем более. Но вот конкретная композиция этих структур, способ их взаимодействия и набор оптимизаций поверх — это то, чего я не нашёл ни в одном существующем PHP-роутере. И это не голословное утверждение — ниже я покажу код и объясню, чем конкретно отличается каждый компонент.

Предыдущая статья была про процесс создания. Эта — про инженерию. Не маркетинг, а алгоритмы и код.

Контекст: как работают популярные роутеры

Прежде чем погружаться в Waypoint, давайте вспомним, что делают «большие» — и разберёмся, в чём именно «trie-like структуры» Symfony отличаются от того, что делает Waypoint.

FastRoute (nikic/fast-route) компилирует маршруты в несколько больших регулярных выражений («chunk regex»). Каждый chunk объединяет десятки маршрутов в одну regex с numbered groups. Даже если URI /about полностью статичен, он проходит через regex-движок. Кеш — var_export() массива.

Symfony Routing строит StaticPrefixCollection — дерево, которое группирует маршруты по общим строковым префиксам (не по сегментам). Это действительно trie-подобная структура, но с принципиальными отличиями: она не разделяет статические и динамические сегменты на уровне узлов, не поддерживает O(1) hash-map lookup по сегменту, а конечный матчинг всё равно выполняется полным regex по всему URI. CompiledUrlMatcher генерирует PHP-файл с каскадом switch/if, кеш — var_export().

Laravel Router — обёртка над Symfony Routing с дополнительным слоем middleware, model binding и прочих фич. Наследует все характеристики Symfony.

Все три подхода работают хорошо. Но у каждого есть слепые зоны, которые становятся заметны при масштабировании. И главное — ни один из них не комбинирует O(1) хеш-таблицу для статических маршрутов, посегментный trie с hash-map на каждом уровне, prefix-grouped fallback и трёхфазный кеш с OPcache shared memory. Именно эта композиция — суть Waypoint.

Архитектура матчинга: три уровня, от O(1) до regex

Waypoint не выбирает одну стратегию. Он каскадирует три, переходя от самой быстрой к более общей:

Запрос: GET /api/health
        │
        ▼
┌─────────────────────────────┐
│  Tier 0: Static Hash Table  │  O(1)
│  key = "GET:/api/health"    │──── найдено? → готово
└─────────────────────────────┘
        │ нет
        ▼
┌─────────────────────────────┐
│  Tier 1: Prefix-Trie        │  O(глубина URI)
│  посегментный обход         │──── найдено? → готово
└─────────────────────────────┘
        │ нет
        ▼
┌─────────────────────────────┐
│  Tier 2: Fallback           │  O(n), но n << N
│  prefix-grouped regex       │──── найдено? → готово
└─────────────────────────────┘
        │ нет
        ▼
      404 / 405

Давайте посмотрим на каждый уровень в деталях.

Tier 0: Хеш-таблица статических маршрутов

Факт, который упускают из виду: в типичном приложении 30–50% маршрутов не содержат параметров. Это /login, /logout, /api/health, /dashboard, страницы со статическими URL. Они не нуждаются ни в trie, ни в regex.

Waypoint хранит такие маршруты в хеш-таблице с ключом "METHOD:/uri":

// RouteCollection::performMatch()

$key = $method . ':' . $uri;
if (isset($this->staticTable[$key])) {
    return new RouteMatchResult($this->staticTable[$key], []);
}

Одна операция isset() — и маршрут найден. Без обхода дерева, без regex, без аллокации промежуточных структур.

FastRoute пропустит такой маршрут через chunk regex. Symfony обойдёт дерево префиксов. Waypoint сделает lookup за O(1) и вернёт результат.

Tier 1: Prefix-Trie с посегментным матчингом

Для маршрутов с параметрами Waypoint использует классический prefix-trie, но с важной деталью: матчинг идёт посегментно, а не по всему URI сразу.

Каждый узел trie содержит два набора потомков:

final class RouteTrie
{
    /** Статические потомки — O(1) lookup по значению сегмента. */
    private array $staticChildren = [];

    /** Динамические потомки — regex применяется к одному сегменту. */
    private array $paramChildren = [];

    /** Маршруты, завершающиеся в этом узле. */
    private array $routes = [];
}

Алгоритм обхода при матчинге:

public function match(string $method, array $segments, int $depth, ...): ?array
{
    if ($depth === count($segments)) {
        // Все сегменты пройдены — проверяем маршруты в этом узле
        foreach ($this->routes as $route) {
            if ($route->allowsMethod($method)) {
                return ['route' => $route, 'params' => $params];
            }
            // Собираем allowed methods для будущего 405
            foreach ($route->getMethods() as $m) {
                $allowedMethods[$m] = true;
            }
        }
        return null;
    }

    $segment = $segments[$depth];

    // 1. Сначала статический потомок — O(1) hash-map lookup
    if (isset($this->staticChildren[$segment])) {
        $result = $this->staticChildren[$segment]->match(...);
        if ($result !== null) return $result;
    }

    // 2. Затем динамические потомки — regex только к одному сегменту
    foreach ($this->paramChildren as $child) {
        if (preg_match($child['regex'], $segment)) {
            $childParams[$child['paramName']] = $segment;
            $result = $child['node']->match(...);
            if ($result !== null) return $result;
        }
    }

    return null;
}

Ключевые отличия от других реализаций:

1. Приоритет static над dynamic. Если путь /users/admin может совпасть и со статическим сегментом admin, и с параметром {id}, статический проверяется первым. Это гарантирует предсказуемое поведение без магии порядка регистрации.

2. Backtracking. Если статическая ветвь привела в тупик (совпал сегмент, но дальше маршрут не нашёлся), алгоритм откатывается и пробует динамические потомки. Это корректно обрабатывает случаи, когда статический и динамический маршруты перекрываются на разных глубинах.

3. Regex применяется к одному сегменту, не к URI. Выражение \d+ проверяется на строке "42", а не на /users/42/posts. Это быстрее и проще для отладки.

Tier 2: Fallback с prefix-группировкой

Не все маршруты помещаются в trie. Паттерн files/{path:.+} (cross-segment capture) или report-{year:\d{4}}.pdf (смешанный статический/динамический сегмент) — это легитимные маршруты, которые не укладываются в модель «один сегмент = один узел».

Waypoint автоматически определяет совместимость:

public static function isCompatible(string $pattern): bool
{
    foreach (explode('/', $path) as $part) {
        if ($part === '' || !str_contains($part, '{')) {
            continue; // Статический сегмент — всегда ОК
        }

        // Должен быть ровно один параметр на весь сегмент
        if (!preg_match('#^\{(\w+)(?::([^{}]*))?}$#', $part, $m)) {
            return false; // Смешанный сегмент — не trie
        }

        // Regex параметра не должен матчить '/'
        if (preg_match($fullRegex, '/') === 1) {
            return false; // Cross-segment — не trie
        }
    }
    return true;
}

Несовместимые маршруты попадают в fallback. Но не в наивный линейный список. Они группируются по первому сегменту URI:

// Маршрут /api/report-{year}.pdf → группа "api"
// Маршрут /files/{path:.+}       → группа "files"
// Маршрут /{lang}/about           → группа "*" (catch-all)

При матчинге проверяются только маршруты из нужной группы:

$firstSeg = $segments[0] ?? '';
$candidates = self::mergeFallbackGroups(
    $this->fallbackRouteMap[$firstSeg] ?? [],  // Конкретный префикс
    $this->fallbackRouteMap['*'] ?? [],         // Catch-all
);

Merge двух отсортированных списков выполняется за O(|A|+|B|) — классический merge sort step. В результате из 200 fallback-маршрутов проверяются, допустим, 3–5, а не все 200.

Трёхфазное кеширование: от development до zero-allocation production

Большинство PHP-роутеров имеют два режима: «без кеша» и «с кешем». Waypoint вводит три фазы, каждая из которых — отдельный уровень оптимизации.

Phase 1: Development — ленивый runtime trie

В development маршруты регистрируются через API или PHP-атрибуты. Trie строится лениво при первом вызове match(). Reflection используется для анализа контроллеров. Это удобно при разработке — изменил маршрут, обновил страницу, всё работает.

Phase 2: Compiled Data — массивы без объектов

$router->compileTo(__DIR__ . '/cache/routes.php');

Trie сериализуется в plain PHP-массивы. Матчинг идёт напрямую по массивам через RouteTrie::matchArray() — без создания объектного графа RouteTrie:

public static function matchArray(
    array $trieNode,    // Просто массив из кеша
    array $routeData,   // Плоский список данных маршрутов
    string $method,
    array $segments,
    int $depth,
    array $params,
    array &$allowedMethods,
): ?array {
    if ($depth === count($segments)) {
        foreach ($trieNode['routes'] as $routeIndex) {
            if (in_array($method, $routeData[$routeIndex]['methods'], true)) {
                return ['index' => $routeIndex, 'params' => $params];
            }
        }
        return null;
    }
    // ... тот же алгоритм, но по массивам, не по объектам
}

Ни один объект RouteTrie не создаётся. Route-объект материализуется только для найденного маршрута.

Phase 3: Compiled Matcher — generated PHP class + OPcache shared memory

Это ключевая оптимизация, которой нет у конкурентов. Waypoint генерирует именованный PHP-класс:

// Auto-generated by Waypoint RouteCompiler. Do not edit.

if (!class_exists('WaypointCompiledMatcher_a1b2c3d4e5f6', false)) {

class WaypointCompiledMatcher_a1b2c3d4e5f6 implements CompiledMatcherInterface
{
    private const ROUTES = [
        0 => ['h' => ['App\Controller\UserController', 'list'], 'M' => ['GET'], 'p' => '/users'],
        1 => ['h' => ['App\Controller\UserController', 'show'], 'M' => ['GET'], 'p' => '/users/{id:\d+}',
              'r' => '#^/users/(\d+)$#', 'N' => ['id'],
              'a' => [['source' => 'param', 'name' => 'id', 'cast' => 'int']]],
        // ...
    ];

    private const STATIC_TABLE = [
        'GET:/users' => 0,
        'GET:/api/health' => 5,
        // ...
    ];

    private const TRIE = [
        'static' => ['users' => ['static' => [], 'param' => [...], 'routes' => [0]]],
        'param' => [],
        'routes' => [],
    ];

    private const NAME_INDEX = ['users.list' => 0, 'users.show' => 1];

    private const STATIC_ONLY_URIS = ['/users' => true, '/api/health' => true];

    // ...методы матчинга...
}

}

return new WaypointCompiledMatcher_a1b2c3d4e5f6();

Почему это важно?

PHP OPcache хранит private const массивы в shared memory. Это значит:

• Данные загружаются один раз при первом запросе worker-процесса.

• На каждом последующем запросе ничего не аллоцируется — PHP использует immutable массивы прямо из shared memory.

• Guard class_exists(..., false) гарантирует, что при повторном include (тот же worker) определение класса не дублируется — выполняется только return new ClassName().

Сравним с конкурентами:

Разница особенно заметна при большом количестве маршрутов (500+), где размер таблицы маршрутов начинает влиять на потребление памяти.

Pre-computed Argument Resolution Plans: нулевой Reflection в runtime

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

// При компиляции (RouteCompiler::buildArgPlan):

foreach ($reflection->getParameters() as $param) {
    $name = $param->getName();
    $type = $param->getType();

    if (is_a($type->getName(), ServerRequestInterface::class, true)) {
        $plan[] = ['source' => 'request'];
    } elseif (isset($routeParamNames[$name])) {
        $plan[] = ['source' => 'param', 'name' => $name, 'cast' => 'int'];
    } elseif (!$type->isBuiltin()) {
        $plan[] = ['source' => 'container', 'class' => $type->getName()];
    } elseif ($param->isDefaultValueAvailable()) {
        $plan[] = ['source' => 'default', 'value' => $param->getDefaultValue()];
    }
}

Результат попадает в кеш. При диспатче RouteHandler использует план напрямую:

// RouteHandler::resolveFromPlan() — runtime, zero Reflection:

foreach ($plan as $entry) {
    $args[] = match ($entry['source']) {
        'request'   => $request,
        'param'     => $this->coercePlanValue(
                           $this->parameters[$entry['name']],
                           $entry['cast'],
                       ),
        'container' => $this->container->get($entry['class']),
        'default'   => $entry['value'] ?? null,
    };
}

Один match expression, никакого ReflectionMethod, никакого ReflectionParameter::getType(). Для контроллера с 5 параметрами это экономит ~20 вызовов Reflection API на каждый запрос.

Для сравнения: в Symfony ArgumentResolver каждый запрос проходит через цепочку ArgumentValueResolverInterface, каждый из которых может использовать Reflection. В Laravel — аналогично через RouteDependencyResolverTrait.

Early 405: мгновенный ответ без обхода trie

Представьте: 50 статических маршрутов, 200 динамических, 10 fallback. Приходит POST /about, а маршрут /about зарегистрирован только для GET. Стандартный роутер:

1. Не найдёт POST:/about в статической таблице.

2. Обойдёт trie — пустой результат.

3. Проверит fallback-маршруты — пустой результат.

4. Соберёт allowed methods и выбросит 405.

Waypoint делает это иначе. На этапе компиляции он вычисляет набор «purely static» URI — тех, для которых ни один динамический маршрут не может совпасть:

private function computeStaticOnlyUris(...): array
{
    foreach ($staticUris as $uri => $_) {
        // Проверка 1: на пути по trie нет параметризованных потомков
        if (!$this->hasNoParamChildrenAlongPath($trieArray, $uri)) {
            continue;
        }

        // Проверка 2: ни один fallback-маршрут не матчит этот URI
        $matchesFallback = false;
        foreach ($fallbackIndices as $idx) {
            if ($allRoutes[$idx]->match($uri) !== null) {
                $matchesFallback = true;
                break;
            }
        }

        if (!$matchesFallback) {
            $result[$uri] = true;
        }
    }
    return $result;
}

При матчинге в runtime:

$staticAllowed = $this->compiledMatcher->staticMethods($uri);

if ($staticAllowed !== []) {
    if ($this->compiledMatcher->isStaticOnly($uri)) {
        // URI "purely static" — 405 мгновенно, без trie и fallback
        throw new MethodNotAllowedException($staticAllowed, $method, $uri);
    }
    // Pre-populate allowed methods для будущего 405
    foreach ($staticAllowed as $m) {
        $allowedMethods[$m] = true;
    }
}

Для purely static URI ответ 405 возвращается за два lookup в const-массивах — без обхода trie и без проверки fallback-маршрутов.

Lazy Route Hydration: материализуй только то, что нужно

При загрузке из кеша Waypoint не создаёт Route-объекты для всех маршрутов. Объект создаётся только когда он действительно нужен:

private function getCachedCompactRoute(int $idx): Route
{
    return $this->routeCache[$idx] ??= Route::fromCompactArray(
        $this->compiledMatcher->getRoute($idx)
    );
}

Паттерн ??= (null coalescing assignment) гарантирует, что объект создаётся ровно один раз и кешируется.

Это значит:

• На запрос матчинга — 1 Route-объект (найденный маршрут).

• На запрос URL generation — 1 Route-объект (именованный маршрут).

• Полная гидратация — только при вызове all() (диагностика, вывод таблицы маршрутов).

Для приложения с 500 маршрутами разница ощутима: 1 объект вместо 500 на каждый запрос.

Автоматическая классификация маршрутов: trie или fallback?

Разработчику не нужно знать, какие маршруты «trie-совместимы», а какие нет. API одинаковый:

// Оба маршрута регистрируются одинаково
$router->get('/users/{id:\d+}', [UserController::class, 'show']);          // → trie
$router->get('/files/{path:.+}', [FileController::class, 'download']);     // → fallback
$router->get('/report-{year:\d{4}}.pdf', [ReportController::class, 'pdf']); // → fallback

Waypoint автоматически проверяет каждый маршрут через RouteTrie::isCompatible() и направляет его в нужную стратегию. Правила просты:

1. Каждый сегмент — либо целиком статический, либо целиком параметр.

2. Regex параметра не матчит /.

3. Нет смешанных сегментов (prefix-{name}.txt).

Если хотя бы одно условие нарушено — fallback. Прозрачно, без ошибок, без конфигурации.

Сводная таблица

Заключение: стандартные алгоритмы, нестандартная композиция

Вернёмся к критике из комментариев к предыдущей статье. «Это стандартный алгоритм» — и да, и нет.

Да: trie — стандартная структура данных. Хеш-таблица — стандартная. Regex — стандартный. Каждый из этих компонентов по отдельности описан в учебниках и реализован тысячи раз.

Нет: конкретная композиция — три каскадных уровня матчинга с автоматической классификацией маршрутов, трёхфазный кеш с генерацией именованного PHP-класса и immutable const в OPcache shared memory, pre-computed argument resolution plans, early 405 через статический анализ trie на этапе компиляции, lazy hydration с материализацией ровно одного объекта на запрос — этого набора оптимизаций нет ни в FastRoute, ни в Symfony Routing, ни в каком-либо другом PHP-роутере, который мне удалось найти.

Waypoint — это не попытка заменить Symfony или FastRoute. Это исследование вопроса: а что если не выбирать компромисс, а использовать несколько стратегий одновременно?

В совокупности они дают роутер, который:

• Тратит O(1) на статические маршруты (а их обычно 30–50%).

• Не создаёт лишних объектов при загрузке из кеша.

• Не вызывает Reflection при диспатче.

• Использует OPcache shared memory вместо per-request аллокаций.

• Автоматически выбирает лучшую стратегию для каждого маршрута.

Проект open source, лицензия MIT: github.com/ascetic-soft/Waypoint.

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