Практика: фильтры товаров (Product filter language) ​

Маркетолог пишет условие подборки строкой, а код превращает её в дерево выражений и проверяет на каждом товаре; опечатка ловится при разборе, с позицией в строке.

Базовый пример: Интерпретатор. Там дерево собирается в коде, и вопрос «откуда оно берётся» остаётся за кадром. Практика отвечает на него: текст разбирается токенизатором и рекурсивным парсером с приоритетами операций, а ошибки разбора говорят, где именно в строке беда.

Задача ​

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

Решили дать маркетологам маленький язык условий: price > 100 and category = "books" or not in_stock. Строка хранится в настройках подборки, при сохранении разбирается, и если в ней ошибка, админка показывает, в каком месте. Первая версия парсила строку регулярками и молча возвращала false на незнакомом поле: опечатка prise > 100 давала пустую подборку, и рассылка уходила без товаров.

Что урезано ​

• Три поля: число price, строка category, флаг in_stock. В проекте схема полей приходит из каталога, а не зашита в код.
• Числа только целые, строки без экранирования кавычек, позиции считаются для ASCII-строк.
• Нет in (...), like, дат и арифметики в условиях.
• Подборка проверяется на списке товаров в памяти; в проекте дерево переводят в SQL или в запрос к поисковому индексу.

Решение ​

Дерево — то же, что в базовом примере, только узлы возвращают bool: Filter с одной операцией matches(product) вместо interpret(context), контекстом служит Product. Новое — два шага перед деревом: токенизатор режет строку на слова, числа, строки и операторы, парсер собирает из них дерево по грамматике. Разобранный фильтр — обычный объект: его разбирают один раз при сохранении подборки и потом проверяют на тысячах товаров.

Структура ​

Терминалы — Compare (поле, оператор, значение) и Flag (булево поле само по себе). Поле хранится не именем, а функцией-геттером из таблицы полей: имя проверено парсером, и при вычислении искать уже нечего. Таблиц три, по типу поля, поэтому price сравнивается только с числом, а category только через = и !=.

Грамматика и приоритеты ​

Нетерминалы And, Or, Not ничего не знают о тексте, приоритет задаёт форма дерева. Парсер строит её по грамматике, где каждый уровень приоритета — своя функция:

or         := and ("or" and)*
and        := unary ("and" unary)*
unary      := "not" unary | "(" or ")" | comparison
comparison := flag | number_field op NUMBER | text_field ("=" | "!=") STRING

or вызывает and, and вызывает unary, поэтому not связывает сильнее всех, а or слабее: a and b or not c становится Or(And(a, b), Not(c)). Скобки возвращают разбор на верхний уровень, и a and (b or c) даёт другое дерево. В PHP нетерминалы называются AndFilter, OrFilter, NotFilter: and, or зарезервированы.

Токенизатор ​

Токенизатор — одно регулярное выражение с группами (число, слово, строка в кавычках, оператор, скобка), которое применяется с текущей позиции. Слова and, or, not становятся ключевыми словами, остальные — полями. Каждый токен помнит колонку, с которой начался, а в конце добавляется токен end с позицией сразу за строкой: «не хватает значения» показывает туда, где его ждали. Незакрытая кавычка и неизвестный символ (&& вместо and) падают уже здесь.

Парсер ​

Парсер — рекурсивный спуск с двумя примитивами: accept берёт токен, если он нужного вида, expect требует его и иначе падает с текстом «expected X, got Y» и позицией токена. Неизвестное поле — тоже ошибка разбора: фильтр с опечаткой не сохранится, вместо того чтобы молча отобрать ноль товаров. После разбора парсер требует end, так что хвост вроде price > 100 in_stock не проглатывается.

Как это собирается ​

Строку фильтра пишет маркетолог в админке, а разбирает её обработчик сохранения подборки. Если Parser::parse бросил FilterSyntaxError, подборка не сохраняется, и админка показывает текст ошибки с позицией: в примере опечатка prise отклонена с "parse error at 1". Правильные строки превращаются в дерево Filter один раз, и дальше задача рассылки или баннера просто вызывает matches на каждом товаре каталога.

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

Сценарий целиком с выводом: пример на PHP, он же на Go, Python и TypeScript в панели кода.

Реализации ​

Запуск: make test T=patterns/behavioral/interpreter/practice

Что проверяют тесты ​

Тесты одинаковы во всех языках. Первая таблица — выражения на четырёх товарах (роман 150, комикс 50, ручка 30 не в наличии, ноутбук 900). price > 100 and category = "books" or not in_stock отбирает роман и ручку: and сильнее or. Те же условия со скобками вокруг or оставляют только роман: скобки меняют дерево. not category = "books" and in_stock даёт ноутбук: not относится только к сравнению. Вторая таблица — семь ошибок разбора с точным текстом и колонкой: неизвестное поле, пропущенное значение, строка вместо числа, > для строкового поля, незакрытая скобка, незакрытая кавычка, &&. Ни одна не доходит до вычисления: плохой фильтр не превращается в пустую подборку.

Где граница ​

• Язык растёт: in, like, даты, функции, вложенные поля. Самописный парсер становится проектом; дальше берут готовый язык выражений с проверкой типов и песочницей: CEL (cel-go, cel-python), Symfony ExpressionLanguage, JsonLogic, или генератор парсеров (ANTLR, Lark, PEG).
• Фильтр должен работать на миллионах товаров: дерево не вычисляют на объектах, а переводят в WHERE или запрос к поиску. Это новая операция над деревом, и её удобнее оформить Посетителем, чем методом в каждом узле.
• Условия меняются редко и их делает программист: строковый язык избыточен, хватит Спецификаций, собранных в коде, или формы с галочками в админке.
• Строку пишут посторонние (покупатели, партнёры): нужны лимиты на длину и глубину вложенности, иначе ((((... уронит рекурсивный парсер.

Отличия между языками ​

• PHP — and, or, not — зарезервированные слова, поэтому классы называются AndFilter и т. д., а методы or()/and() разрешены. <=> сравнивает и числа, и строки, поэтому Compare один на оба типа. Пропущенная ветка match стала бы UnhandledMatchError, PHPStan требует default.
• Go — Compare[T cmp.Ordered] типобезопасен: Compare[int] не сравнит число со строкой. Ошибки внутри рекурсивного спуска протаскивать через каждый уровень утомительно, поэтому парсер паникует своим типом и Parse ловит только его через recover; чужая паника пробрасывается дальше. Позиции считаются в байтах.
• Python — TOKEN.match(source, pos) применяет шаблон с позиции без обрезки строки, lastgroup сразу даёт вид токена. Таблица OPERATORS из функций operator.gt и т. п. заменяет switch.
• TypeScript — флаг y делает регулярку «липкой»: она совпадает только ровно с lastIndex. Из-за noUncheckedIndexedAccess поиск поля в Record даёт T | undefined, и проверка «поле известно» получается сама собой.

Связанные темы ​

• Интерпретатор (базовый пример)
• Компоновщик (Composite) — дерево фильтров устроено как дерево компоновщика
• Практика Стратегии: расчёт доставки — правила из конфига без своего языка: когда условий немного, этого хватает