g/re/p

18.12.2025 · 23 мин чтения

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

Но за этой простотой скрывается удивительная история. История, которая начинается в 1973 году в лабораториях Bell Labs, где Кен Томпсон — один из создателей Unix — вытащил команду из текстового редактора и превратил её в отдельную утилиту. История, в которой литературоведческий спор о Федералистских статьях породил инструмент, ставший квинтэссенцией инженерного мышления. История, где алгоритм 1968 года оказался актуальнее своих «продвинутых» наследников и защищает сегодня крупнейшие CDN-сети от атак.

За полвека grep не просто выжил — он эволюционировал. В 2016 году появился ripgrep, который учитывал, что мир разработки изменился, и поиск по репозиторию — это не то же самое, что поиск по диску. А ugrep пошёл ещё дальше, превратив grep в швейцарский нож для работы с любыми данными: архивами, PDF-документами, бинарниками, сжатыми логами.

Три инструмента. Три эпохи. Три философии. И один жест — «найди мне строку в хаосе».

В этом посте мы проследим эволюцию текстового поиска от телетайпов до SIMD-инструкций. Разберёмся, почему регулярное выражение может положить глобальную CDN на полчаса — и как от этого защищаются современные движки. Познакомимся с людьми, которые создали эти инструменты: от легендарного Кена Томпсона до профессора-предпринимателя Роберта ван Энгелена. И, конечно, посмотрим на практические примеры — когда какой инструмент выбрать и почему бессмысленно спорить «кто быстрее» без контекста задачи.

Grep: когда текст был файлом, а не экосистемой

Рождение из редактора

Название grep — это не аббревиатура в привычном смысле. Это буквально команда из текстового редактора ed: g/re/p — «глобально найти строки по регулярному выражению и напечатать». Кен Томпсон, один из создателей Unix, вынес эту идею наружу: вместо того чтобы загружать файл целиком в редактор, инструмент начал стримить — работать с данными потоково, не пытаясь держать всё в памяти.

Сам Томпсон позже вспоминал: «grep был моей личной командой довольно долго, прежде чем я сделал её публичной… Мы очень тщательно следили за тем, чтобы не засорять директорию утилит мусором».

Первое публичное появление grep — четвёртая версия Unix, 1973 год. Но история его создания началась чуть раньше и связана с весьма неожиданным контекстом.

Федералистские статьи: когда литературоведение породило grep

В начале 1970-х Ли Макмахон из Bell Labs работал над проектом, который сегодня назвали бы computational humanities, — статистическим анализом текстов Федералистских статей. Это сборник из 85 эссе, опубликованных в 1787–1788 годах для агитации за ратификацию Конституции США. Авторами были Александр Гамильтон, Джеймс Мэдисон и Джон Джей, но писали они под псевдонимом Publius.

Проблема заключалась в том, что авторство 12 статей было спорным: и Гамильтон, и Мэдисон претендовали на них. Гамильтон составил список своих работ незадолго до роковой дуэли с Аароном Бёрром в 1804 году и приписал себе почти три четверти всех эссе. Мэдисон оспорил это лишь в 1818 году, деликатно заметив, что «список, видимо, был составлен впопыхах».

Спор тянулся более 150 лет. В 1963 году статистики Фредерик Мостеллер и Дэвид Уоллес потратили три года, анализируя словарный запас и стилистические паттерны обоих авторов. Их работа «Inference and Disputed Authorship: The Federalist» стала пионерской в области стилометрии — и окончательно установила, что все спорные статьи написал Мэдисон.

Но вернёмся в Bell Labs. Макмахону нужно было быстро искать паттерны в огромном корпусе текстов. Редактор ed поддерживал регулярные выражения, однако загружал файл целиком в память — для больших текстов это было неприемлемо. Томпсон выделил код поиска в отдельную утилиту, и grep родился как инструмент потоковой обработки.

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

Философия Unix и семейство grep

Даг Макилрой, создатель концепции Unix-пайпов, позже назвал grep «прототипическим программным инструментом», который «необратимо закрепил философию Томпсона в Unix». Эта философия проста: делай одну вещь и делай её хорошо. Grep берёт поток, режет по строкам, фильтрует. Точка.

В 1975 году Альфред Ахо (да, тот самый, соавтор AWK и «Книги дракона» по компиляторам) написал за выходные две вариации: egrep с поддержкой расширенных регулярных выражений (альтернации и группировки) и fgrep для быстрого поиска фиксированных строк. Так grep превратился в семейство.

Современный GNU grep объединяет все три варианта и добавляет PCRE-режим (-P). Но под капотом он всё ещё следует заветам Томпсона: работает потоково, не загружает файл целиком, минимизирует системные вызовы.

Почему grep до сих пор быстр

В 2010 году Майк Хертель, оригинальный автор GNU grep, написал легендарное письмо в рассылку FreeBSD, объясняющее секреты производительности:

«Трюк номер один: GNU grep быстр, потому что ИЗБЕГАЕТ СМОТРЕТЬ НА КАЖДЫЙ ВХОДНОЙ БАЙТ.
Трюк номер два: GNU grep быстр, потому что ВЫПОЛНЯЕТ ОЧЕНЬ МАЛО ИНСТРУКЦИЙ для каждого байта, на который всё-таки смотрит».

GNU grep использует алгоритм Бойера-Мура, который начинает поиск с последнего символа паттерна и прыгает вперёд при несовпадении. В пределе grep выполняет менее трёх x86-инструкций на каждый проверяемый байт — и пропускает множество байтов вовсе.

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

В документации GNU grep есть ещё один «стариковский приём»: в однобайтовых локалях (например, LC_ALL=C) grep работает существенно быстрее из-за меньших затрат на обработку многобайтовых символов.

# Турбо-режим для огромных ASCII-логов
LC_ALL=C grep -F 'ERROR 504' huge.log

Чего у grep нет в ДНК

Но вот чего grep не понимает — это контекста проекта. Для grep мир состоит из файлов и строк. Не из .gitignore, не из «здесь мусор», не из «это бинарник», не из «не трогай node_modules».

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

Ripgrep: когда поиск стал «поиском по репозиторию»

Революция дефолтов

В 2016 году Эндрю Галлант выпустил ripgrep (rg) — и сделал простую, но революционную вещь: он встроил в дефолты то, что разработчик и так делает в голове.

В README сказано прямо: rg рекурсивно ищет по директории и по умолчанию уважает .gitignore, пропускает скрытые файлы и директории и игнорирует бинарники.

Это и есть та «скорость», которую ощущают руками. Не абстрактные миллисекунды бенчмарков — а меньше шума, меньше бесполезных файлов, меньше случайных совпадений в build-артефактах. Когда вы ищете FEATURE_FLAG_X в проекте, вас не интересует, что эта строка встречается в node_modules/some-package/dist/bundle.min.js.

# Просто работает
rg 'FEATURE_FLAG_X'

# Если нужно вообще везде, включая ignored/hidden
rg -uuu 'FEATURE_FLAG_X'

Флаг -u отключает один уровень фильтрации: -u игнорирует .gitignore, -uu добавляет скрытые файлы, -uuu — ещё и бинарники.

Эндрю Галлант: инженер с философией

Эндрю Галлант (известный в сети как BurntSushi) — программист из Мальборо, Массачусетс. Он работает в Salesforce, болеет за Patriots, любит сигары Padrón 1964 и пишет о конечных автоматах.

У него характерная инженерная линия: много утилит и библиотек вокруг темы «быстро и аккуратно», с заметным упором на то, чтобы инструмент был предсказуемым в реальности, а не в лаборатории. Помимо ripgrep, он создал xsv (быстрый CLI для работы с CSV), библиотеку bstr (байтовые строки для Rust) и, что особенно важно, — crate regex и regex-automata, которые лежат в основе поискового движка ripgrep.

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

Архитектура: ignore как отдельный проект

Одна из ключевых частей ripgrep — crate ignore, который описывается как «быстрый рекурсивный итератор директорий» с поддержкой .gitignore, типов файлов и прочих фильтров. Это не «фича» — это отдельный оптимизированный кусок архитектуры.

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

Галлант честно признаёт, что ignore — это «proof of concept», написанный под конкретные нужды ripgrep. Он не пытался сделать идеальную библиотеку для всех случаев жизни. Но функциональность и производительность оказались настолько хороши, что другие проекты начали использовать ignore несмотря на шероховатости API.

Rust: язык, который изменил правила

Ripgrep написан на Rust — и это не случайный выбор «модного языка». Rust предлагает уникальную комбинацию: производительность уровня C/C++ и гарантии безопасности памяти без сборщика мусора.

Система владения (ownership) в Rust устанавливает три правила, проверяемых компилятором: у каждого значения ровно один владелец, владение можно передать, но не скопировать, и когда владелец выходит из области видимости, значение автоматически уничтожается. Это исключает целые классы ошибок: use-after-free, двойное освобождение, гонки данных.

По данным National Vulnerability Database, ошибки работы с памятью составляют около 70% серьёзных уязвимостей в системном софте. Microsoft и Google независимо друг от друга пришли к тем же цифрам по своим кодовым базам. Rust закрывает эту проблему на уровне компилятора — без накладных расходов в рантайме.

Принцип «zero-cost abstractions» означает, что высокоуровневые конструкции Rust (итераторы, паттерн-матчинг, умные указатели) компилируются в код, эквивалентный оптимизированному C++. В бенчмарках The Computer Language Benchmarks Game Rust стабильно показывает результаты в пределах 5–15% от C++ — при этом гарантируя безопасность.

Для ripgrep это означает: параллельный обход директорий без гонок данных, безопасная работа со строками и файлами, и уверенность в том, что программа не упадёт с segfault на неожиданном входе.

Regex-движок: философия предсказуемости

Здесь самый важный момент. Ripgrep по умолчанию использует движок на основе конечных автоматов (ДКА/НКА), который гарантирует линейное время работы на любых входных данных. Сложность — O(m × n), где m — длина паттерна, n — длина текста. Всегда. Без исключений.

Эта гарантия имеет цену: некоторые возможности классических regex-движков недоступны. Опережающие и ретроспективные проверки (lookahead/lookbehind), обратные ссылки (backreferences) — всё это требует алгоритма с откатами (backtracking), который может уйти в экспоненциальное время на специально подобранных входах.

Решение ripgrep — опциональное переключение на PCRE2:

# Negative lookbehind — только с PCRE2
rg -P '(?<!_)userId=(\d+)\b'

Флаг -P (или --pcre2) включает мощный движок с полной поддержкой Perl-совместимых регулярных выражений. Но это сознательный выбор пользователя, а не дефолт.

Философия ripgrep: «быстро и предсказуемо по умолчанию; мощно — по запросу».

ReDoS: когда регулярное выражение становится оружием

Анатомия катастрофы

2 июля 2019 года, 13:42 UTC. Инженер команды Cloudflare деплоит минорное изменение в правилах WAF для детекции XSS-атак. Через три минуты начинают сыпаться алерты. CPU на всех серверах, обрабатывающих HTTP/HTTPS-трафик, уходит в потолок. Cloudflare — одна из крупнейших CDN-сетей в мире — лежит 27 минут.

Причина? Одно регулярное выражение с паттерном, вызывающим катастрофический откат (backtracking).

Атака на отказ в обслуживании через регулярные выражения (Regular Expression Denial of Service, ReDoS) — это атака на алгоритмическую сложность. Классические regex-движки (PCRE, Java, Python, JavaScript) используют механизм откатов (backtracking): при неоднозначности они пробуют один путь, и если он не приводит к совпадению — откатываются и пробуют другой. На определённых комбинациях паттернов и входных данных количество путей растёт экспоненциально.

Анатомия «злого» regex

«Злые» регулярные выражения обычно содержат вложенную повторяемость или альтернацию с перекрытием внутри группы:

Паттерн	Проблема
`(a+)+$`	Вложенные квантификаторы
`(a)$`	Starred stars
`([a-zA-Z]+)*$`	Символьный класс с вложенным повторением
`(a\|a?)+$`	Альтернация с перекрытием
`(.*a){100}$`	Жадный матч с повторением

Попробуйте скормить паттерну ^(a+)+$ строку из 30 букв a и восклицательного знака в конце. Движок с откатами начнёт перебирать варианты разбиения строки на группы — и никогда не закончит за разумное время.

Реальные жертвы

Cloudflare — не единственный пострадавший. В 2024 году CVE-2024-9277 описывает уязвимость в Langflow (до версии 1.0.18), где атакующий мог вызвать ReDoS через аргумент remaining_text. Библиотека httplib2 для Python страдала от ReDoS при обработке заголовка www-authenticate с длинной последовательностью неразрывных пробелов. Популярный npm-пакет UAParser.js с шестью миллионами скачиваний оказался уязвим из-за регулярки для определения браузеров на телефонах Xiaomi.

Исследование тысяч популярных проектов на GitHub показало, что более 10% из них уязвимы к ReDoS. Атакующие могут провести такой же анализ — и целенаправленно бить по системам, использующим уязвимые библиотеки.

Как защищаются движки

RE2 — regex-библиотека от Google — была создана специально для защиты от ReDoS. Рассу Коксу, её главному разработчику, пришла идея из grep Кена Томпсона для Plan 9. RE2 использует детерминированный конечный автомат (DFA) и гарантирует линейное время — ценой отказа от проверок окружения (lookaround) и обратных ссылок (backreferences).

Google планировал использовать PCRE для Code Search, пока не осознали масштаб проблемы: «Code Search принимает регулярные выражения от кого угодно в интернете. Использование PCRE оставило бы нас открытыми для тривиальных DoS-атак».

Crate regex для Rust, написанный Эндрю Галлантом, следует тем же принципам. В документации прямо сказано: «Эта реализация использует конечные автоматы и гарантирует линейное время матчинга на всех входных данных».

После инцидента 2019 года Cloudflare перешёл на Rust’овый regex-движок, полностью исключив риск ReDoS.

Защита на практике

Используйте безопасные движки: RE2, Rust regex, Go regexp — все они построены на автоматах и гарантируют линейное время.
Переписывайте уязвимые паттерны: (.*a)+ можно заменить на ([^a]*a)+ — это убирает перекрытие.
Устанавливайте таймауты: .NET с версии 4.5 позволяет передать таймаут в конструктор Regex. Ruby 3.2 добавил глобальную настройку Regexp.timeout.
Никогда не принимайте regex от пользователей: если атакующий может модифицировать паттерн, он сконструирует опасный.
Используйте инструменты анализа: regexploit, safe-regex и подобные утилиты находят уязвимые паттерны автоматически.

Ugrep: когда grep решил стать прожектором

Другой замысел

Ugrep часто воспринимают как «ещё один ripgrep, только на C++». На деле это другой проект с другой философией.

Если ripgrep — это grep для репозиториев, то ugrep — grep для всего. Его автор, доктор Роберт ван Энгелен, позиционирует инструмент как «grep-замену, совместимую по привычкам», но расширенную «без комплексов».

На сайте подчёркивается совместимость с опциями GNU/BSD grep — чтобы порог входа был низким. Можно буквально сделать alias grep=ugrep и продолжить работать как раньше. А потом обнаружить, что инструмент умеет гораздо больше.

Роберт ван Энгелен: профессор и предприниматель

Ван Энгелен — не типичный open source-разработчик. Он защитил PhD в Лейденском университете (1994–1998), был профессором Computer Science во Флоридском государственном университете (включая должность заведующего кафедрой в 2011–2014), а в 2003 году основал компанию Genivia.

Его академические интересы — высокопроизводительные вычисления, веб-сервисы, байесовские сети. Google Scholar показывает более 2400 цитирований его работ. В 2022 году он получил Google OSPB Award за вклад в open source — конкретно за ugrep.

Помимо ugrep, ван Энгелен — автор gSOAP (популярного инструментария для веб-сервисов) и RE/flex (высокопроизводительной C++-библиотеки регулярных выражений). И это не случайное соседство: RE/flex — сердце ugrep.

Чем ugrep отличается от остальных

Список возможностей выглядит как спецификация швейцарского ножа:

TUI с интерактивным поиском: команда ug запускает интерфейс, где можно уточнять запрос в реальном времени
Boolean-поиск в стиле Google: AND, OR, NOT прямо в запросе
Fuzzy matching: нечёткий поиск с ошибками
Поиск в архивах: tar, zip, 7z, cpio, pax — включая вложенные
Поиск в сжатых файлах: gz, bz2, xz, lz4, zstd, brotli
Поиск в документах: PDF и офисные форматы
Hexdump бинарников: когда нужно найти паттерн в исполняемом файле
Цветной вывод с контекстом: как в современных grep-альтернативах

История лицензий: почему он написал всё сам

Одна из самых показательных деталей — мотивация по лицензированию. В wiki ugrep ван Энгелен объясняет: чтобы сохранить исходники «чистыми» под BSD-3-Clause и не тащить GPL/LGPL-зависимости, он написал собственные распаковщики tar/zip/pax/cpio с нуля.

Это редкая степень контроля над технологическим стеком. Внешние библиотеки декомпрессии (zlib, liblzma и т.д.) подключаются опционально — но базовая функциональность работает без них.

Архитектура: предсказание + ДКА + SIMD + асинхронный ввод-вывод

Если у ripgrep ключевой «секрет» — дисциплина обхода и дефолты, то ugrep делает ставку на алгоритмику и низкоуровневые оптимизации.

В wiki описана многоступенчатая архитектура:

Match prediction: сначала делается быстрое предсказание, может ли строка содержать совпадение (на основе хешированного Bitap-алгоритма)
RE/flex matchers: затем применяется полноценный ДКА-матчинг через высокопроизводительную библиотеку
SIMD-оптимизации: AVX, SSE2, ARM NEON, AArch64 — используются везде, где возможно
Async I/O: асинхронное чтение файлов с упреждением
Worker threads с балансировкой: параллелизм не наивный, а с учётом размера файлов

RE/flex, написанный тем же ван Энгеленом, позиционируется как «альтернатива Flex, которая быстрее Flex». Бенчмарки показывают, что RE/flex токенизирует репрезентативный C-файл (2 КБ, 244 токена) за 8.7 микросекунд — быстрее, чем Boost.Regex, std::regex, PCRE2 и RE2.

Отдельная история — алгоритм PM-k, придуманный ван Энгеленом для приблизительного поиска по нескольким строкам. Принцип его работы называют «предсказание-сравнение» («predict-match»). Он ускоряет нечёткий поиск, совмещая хеширование с Bitap. Статья регулярно обновлялась вплоть до 2025 года.

C++: мощь и ответственность

Ugrep написан на C++ — языке с полувековой историей и огромной экосистемой. В отличие от Rust, C++ не гарантирует безопасность памяти на уровне компилятора. Ответственность за корректную работу с памятью лежит на программисте.

Это компромисс, сделанный осознанно. C++ предлагает:

Максимальный контроль над памятью и производительностью
Зрелую экосистему библиотек (40+ лет развития)
Лёгкую интеграцию с существующим C/C++ кодом
Предсказуемую производительность без сборщика мусора

Для опытного разработчика вроде ван Энгелена C++ позволяет выжать максимум из железа. RE/flex использует DFA-трансформации, изобретённые автором специально для ленивых квантификаторов (lazy quantifiers) — это уровень оптимизаций, требующий полного контроля над генерируемым кодом.

Обратная сторона — C++ не защищает от ошибок. Но ugrep — не веб-сервис, принимающий произвольные данные из интернета. Это утилита, работающая с локальными файлами. Модель угроз другая.

Сравнение regex-движков: что под капотом

Движки с откатами против автоматных движков

Все regex-движки делятся на две большие категории:

Движки с откатами (backtracking) — PCRE, Java, Python, JavaScript, .NET:

Строят НКА (недетерминированный конечный автомат) и обходят его с откатами
Поддерживают проверки окружения (lookaround), обратные ссылки (backreferences), условные подвыражения (conditional patterns)
Худший случай: экспоненциальное время
Уязвимы к ReDoS

Автоматные движки (automata-based) — RE2, Rust regex, Go regexp, RE/flex:

Строят ДКА (детерминированный конечный автомат) или симулируют НКА без откатов
Ограниченная выразительность (нет проверок окружения и обратных ссылок)
Гарантированное линейное время
Иммунны к ReDoS

Интересно, что алгоритм построения Томпсона (Thompson’s construction) 1968 года лежит в основе современных «безопасных» движков. Кен Томпсон описал его в статье «Regular Expression Search Algorithm» для Communications of the ACM. Спустя полвека его подход оказался актуальнее, чем альтернативы с откатами.

Ленивый ДКА: компромисс ripgrep

Ripgrep использует «ленивый» ДКА — гибрид между НКА и полным ДКА. Полный ДКА строится за экспоненциальное время от числа состояний НКА, что неприемлемо для сложных паттернов. Ленивый ДКА (lazy DFA) строит состояния «по требованию»: начинает с НКА и конструирует ДКА-состояния по мере прохождения по тексту.

Это даёт:

линейное время матчинга (как у ДКА);
разумное время компиляции (состояния строятся лениво);
ограниченное потребление памяти (можно сбрасывать кэш состояний).

GNU grep и RE2 используют тот же подход. В документации regex-automata это называется «гибридный НКА/ДКА» (hybrid NFA/DFA).

RE/flex: ДКА с суперсилами

RE/flex идёт дальше. Ван Энгелен разработал алгоритм ДКА-трансформации для ленивых квантификаторов (типа .*?), который позволяет матчить их без откатов за линейное время. Это нетривиальная задача: стандартные ДКА не поддерживают «ленивость».

В RE/flex 4.0 (февраль 2024) появился новый алгоритм отсечения ДКА (DFA cut algorithm), который ускоряет предсказание совпадений (match prediction) — и эти оптимизации сразу попали в ugrep 5.0.

Кроме того, RE/flex предлагает FuzzyMatcher — матчер с поддержкой редакционного расстояния (edit distance), который тоже работает за «практически линейное» время благодаря ДКА-базе и ограничению на количество ошибок.

PCRE2: мощь ценой риска

PCRE2 (Perl-совместимые регулярные выражения, Perl Compatible Regular Expressions) — это Ford F-150 среди regex-движков. Огромный, мощный, везде проедет. Поддерживает:

опережающие и ретроспективные проверки (lookahead/lookbehind), включая переменной длины в пределах альтернатив;
обратные ссылки (backreferences);
рекурсивные паттерны (recursive patterns);
условные подвыражения (conditional subpatterns);
свойства Юникода (Unicode properties);
JIT-компиляцию.

С версии 10.30 (2017) PCRE2 использует кучу (heap) вместо стека для хранения состояний отката, что снимает проблему переполнения стека. Но это не решает проблему экспоненциального времени — просто теперь программа не падает, а зависает.

Ripgrep опционально поддерживает PCRE2 через флаг -P. Это разумный компромисс: по умолчанию безопасно и быстро, по запросу — максимальная выразительность.

Скорость: почему бессмысленно спорить «кто круче»

Разные бенчмарки — разные победители

Самое честное, что можно сказать про «ugrep быстрее ripgrep» — это: иногда да, иногда нет, а чаще сравнивают разные задачи.

Эндрю Галлант в обсуждении бенчмарков ugrep указал на важный нюанс: ripgrep значительно быстрее при уважении .gitignore, потому что пропускает огромное количество файлов. Ugrep по умолчанию этого не делает — нужно явно включить, и это меняет картину.

С другой стороны, ugrep вкладывается в механики ускорения самого матчинга: предсказание совпадений, ДКА, SIMD-инструкции, асинхронный ввод-вывод. На задачах типа «найди паттерн в терабайте логов» это даёт преимущество.

Когда что выбрать

Ripgrep — если ваш мир это репозитории:

правильные дефолты из коробки;
уважение .gitignore без лишних телодвижений;
предсказуемость regex-движка;
интеграция в редакторы (VS Code использует ripgrep для поиска).

Ugrep — если мир это файловая свалка:

архивы, сжатые файлы, вложенные архивы;
PDF, офисные документы;
бинарники с hexdump;
нечёткий поиск по логам с опечатками;
интерактивный TUI для итеративного уточнения.

GNU grep — если нужен минимализм:

доступен везде без установки;
отлично работает в пайпах;
LC_ALL=C для максимальной скорости на ASCII;
совместимость со скриптами, написанными 30 лет назад.

Примеры из жизни

Поиск по коду: базовый случай

# ripgrep: просто работает, .gitignore учтён
rg 'FEATURE_FLAG_X'

# Показать только имена файлов
rg -l 'FEATURE_FLAG_X'

# С контекстом: 2 строки до и после
rg -C2 'FEATURE_FLAG_X'

# В конкретных типах файлов
rg -t py 'FEATURE_FLAG_X'
rg -t js -t ts 'FEATURE_FLAG_X'

PCRE-магия: проверки окружения

# Найти userId=123, но не _userId=123
rg -P '(?<!_)userId=(\d+)\b'

# Найти import, за которым НЕ следует from
rg -P 'import(?!\s+from)'

# Найти функции, которые начинаются с get и заканчиваются на Async
rg -P 'function\s+get\w+Async\s*\('

Boolean-поиск: ugrep-специфика

# В файле есть timeout И (retry ИЛИ backoff), НО НЕТ deprecated
# -%% применяет условие ко всему файлу (не построчно)
ugrep -%% -l 'timeout AND (retry OR backoff) NOT deprecated'

# То же, но с выводом совпадений
ugrep -%% 'timeout AND (retry OR backoff) NOT deprecated'

Нечёткий (Fuzzy) поиск: когда опечатки неизбежны

# Найти authorizaton/authorization/authorisation с 2 ошибками
ugrep -Z2 'authorization'

# best — найти наилучшее совпадение
ugrep -Z2best 'authentication'

# Комбинируем с ограничением типов ошибок:
# + insertions, - deletions, ~ substitutions
ugrep -Z'2+-' 'kubernetes'  # только вставки и удаления, не замены

Архивы: когда распаковывать лень

# Поиск по всем файлам в директории, включая архивы
ugrep -z 'signature mismatch' logs/

# Показать, в каком архиве и файле найдено
ugrep -z --format='%z%~%f:%n:%O%~%m' 'ERROR' backups/

# Рекурсивно по вложенным архивам (tar внутри zip)
ugrep -z 'stack trace' releases/*.tar.gz

Hexdump: поиск в бинарниках

# Найти строку в бинарном файле
ugrep -U 'LICENSE' /usr/bin/grep

# Показать в hex-формате с контекстом
ugrep --hexdump 'MZ' suspicious.exe

# Поиск байтовой последовательности
ugrep -U '\x7fELF' /usr/bin/*

TUI: интерактивный режим

# Запустить интерактивный поиск
ug 'pattern' .

# В интерактивном режиме:
# - печатаете — результаты обновляются
# - стрелки — навигация по совпадениям
# - Enter — открыть файл в редакторе
# - Tab — переключение режимов отображения

GNU grep: старая школа

# Максимальная скорость на ASCII-логах
LC_ALL=C grep -F 'ERROR 504' huge.log

# Фиксированные строки (без regex) — ещё быстрее
grep -F -f patterns.txt logfile

# Инвертированный поиск: строки БЕЗ паттерна
grep -v 'DEBUG' application.log

# Подсчёт совпадений
grep -c 'WARNING' *.log

# Рекурсивно с исключением директорий
grep -r --exclude-dir={node_modules,vendor,.git} 'TODO' .

Пример из жизни. Ночной инцидент: почему инструменты не заменяют друг друга

Представьте: 3 часа ночи, падает продакшн. Алерты сыплются быстрее, чем вы успеваете читать.

Сначала — код. Нужно понять, какой сервис сломался и где менялось последним. rg 'PaymentProcessor' --type rust находит все упоминания в репозитории за секунду. Правильные дефолты: никаких target/, никаких .git/.

Потом — логи. Но они уже ротированы и сжаты. ugrep -z 'PaymentProcessor.*timeout' /var/log/myapp/*.gz ищет по сжатым файлам без распаковки. Находит паттерн в архиве двухчасовой давности.

Нужно понять, когда началось. Логи огромные, сотни гигабайт за неделю. LC_ALL=C grep -F 'PaymentProcessor timeout' combined.log | head -100 — старый grep с турборежимом локали выдаёт первые совпадения мгновенно.

А потом выясняется, что проблема в библиотеке, и нужно найти её версию в vendor-архиве. ugrep -z 'version.*1\.4\.' vendor-backup.tar.gz — и вот оно, вложенное в архив.

Каждый инструмент занял свою нишу. Не гонка «кто кого убьёт», а разветвление одного жеста «найти» под разные типы реальности.

Заключение: три эпохи, одна идея

Grep — прародитель и вечный нож для потоков. Родился из редактора ed и потребности анализировать исторические тексты. Пережил полвека, потому что делает одну вещь и делает её хорошо. Прост, прямолинеен, доступен на любой Unix-системе без установки.

Ripgrep — инструмент эпохи репозиториев. Встроил в дефолты то, что разработчик делает в голове: уважение .gitignore, игнорирование мусора, предсказуемость regex-движка. Написан на Rust с его гарантиями безопасности. Философия: «быстро и правильно по умолчанию».

Ugrep — инструмент эпохи «файловых вселенных». Расширяет grep до поисковика по артефактам, архивам, документам, бинарникам. За ним стоит собственная научная и инженерная база: RE/flex, алгоритмы PM-k, SIMD-оптимизации. Философия: «grep без ограничений».

Если хочется сказать «ugrep круче ripgrep» — точнее будет: ugrep шире. А ripgrep — точнее в доме разработчика.

И все трое живут на плечах Кена Томпсона, который в 1973 году вынес команду g/re/p из редактора в отдельную утилиту — и создал прототипический инструмент Unix.

Словарик терминов

ДКА (DFA, Deterministic Finite Automaton) — детерминированный конечный автомат. Математическая модель, где из каждого состояния по каждому символу существует ровно один переход. Гарантирует линейное время работы, но может требовать экспоненциальной памяти для построения.

НКА (NFA, Nondeterministic Finite Automaton) — недетерминированный конечный автомат. Из одного состояния по одному символу может быть несколько переходов. Компактнее ДКА, но требует особых алгоритмов для эффективного выполнения.

Ленивый ДКА (Lazy DFA) — гибридный подход, при котором состояния ДКА строятся «по требованию» во время матчинга. Сочетает скорость ДКА с разумным потреблением памяти.

Откаты (Backtracking) — метод работы regex-движка, при котором он пробует один вариант разбора, а при неудаче возвращается назад и пробует другой. Может приводить к экспоненциальному времени работы на специально подобранных входах.

Опережающая проверка (Lookahead) — проверка того, что после текущей позиции идёт (или не идёт) определённый паттерн, без включения его в совпадение. Синтаксис: (?=...) (позитивная), (?!...) (негативная).

Ретроспективная проверка (Lookbehind) — проверка того, что перед текущей позицией идёт (или не идёт) определённый паттерн. Синтаксис: (?<=...) (позитивная), (?<!...) (негативная).

Проверки окружения (Lookaround) — общее название для опережающих и ретроспективных проверок.

Обратные ссылки (Backreferences) — возможность сослаться на ранее захваченную группу внутри того же регулярного выражения. Например, (.)\1 найдёт два одинаковых символа подряд. Требует механизма откатов.

Ленивые квантификаторы (Lazy Quantifiers) — квантификаторы, которые захватывают минимально возможное количество символов: *?, +?, ??. В отличие от жадных (*, +, ?), которые захватывают максимум.

Редакционное расстояние (Edit Distance, Levenshtein Distance) — минимальное количество операций вставки, удаления и замены символов для превращения одной строки в другую. Используется в нечётком поиске.

ReDoS (Regular Expression Denial of Service) — атака на отказ в обслуживании через подбор входных данных, вызывающих экспоненциальное время работы regex-движка с откатами.

PCRE (Perl Compatible Regular Expressions) — библиотека регулярных выражений, реализующая синтаксис Perl. Мощная, но использует откаты и уязвима к ReDoS.

SIMD (Single Instruction, Multiple Data) — технология параллельной обработки данных на уровне процессора. Инструкции AVX, SSE, NEON позволяют обрабатывать несколько байт за одну операцию.

Алгоритм Бойера-Мура (Boyer-Moore) — эффективный алгоритм поиска подстроки, который начинает сравнение с конца паттерна и прыгает вперёд при несовпадении. Позволяет пропускать большую часть текста.

Bitap (Shift-Or) — алгоритм приближённого поиска строк, использующий битовые операции. Эффективен для коротких паттернов и поиска с ошибками.

Источники

grep — Wikipedia — история создания grep, связь с редактором ed, роль Кена Томпсона и Дага Макилроя в становлении Unix-философии
Ken Thompson — Wikipedia — биография создателя grep, Unix, языка B и соавтора Go
The Federalist Papers — Wikipedia — история Федералистских статей и полуторавекового спора об авторстве между Гамильтоном и Мэдисоном
How Statistics Solved a 175-Year-Old Mystery About Alexander Hamilton — Priceonomics — как Мостеллер и Уоллес применили статистику для установления авторства спорных эссе
Why GNU grep is fast — Mike Haertel — легендарное письмо оригинального автора GNU grep о секретах производительности: Boyer-Moore, избегание разбиения на строки, минимизация инструкций
GNU Grep Manual — официальная документация с рекомендациями по производительности, включая использование LC_ALL=C
ripgrep — GitHub — репозиторий с README, объясняющим философию дефолтов: .gitignore, hidden files, binary detection
About Me — Andrew Gallant’s Blog — личная страница автора ripgrep с описанием проектов и интересов
ripgrep FAQ — ответы на частые вопросы, включая объяснение выбора regex-движка и поддержки PCRE2
ignore crate — GitHub — документация библиотеки для быстрого обхода директорий с поддержкой .gitignore
regex crate — Docs.rs — документация Rust’ового regex-движка с объяснением гарантий линейного времени
regex-automata — GitHub — низкоуровневая библиотека конечных автоматов, объясняющая компромиссы между ДКА и НКА
ugrep — GitHub — репозиторий с полным описанием возможностей: интерактивный интерфейс (TUI), булев поиск, нечёткий поиск, архивы, документы
ugrep Wiki — техническая документация с описанием архитектуры: предсказание совпадений, RE/flex, SIMD, асинхронный ввод-вывод
A New Fast Approximate Multi-String Match and Search Method — Genivia — статья ван Энгелена об алгоритмах PM-k и Bitap, используемых в ugrep для ускорения поиска
Dr. Robert van Engelen — GitHub — профиль автора ugrep с информацией об академическом бэкграунде и проектах Genivia
RE/flex — GitHub — высокопроизводительная C++ библиотека регулярных выражений, движок ugrep
RE2 — Google Open Source Blog — анонс RE2 с объяснением, почему Google отказался от PCRE для Code Search
RE2 — GitHub — репозиторий с описанием гарантий линейного времени и защиты от ReDoS
Implementing Regular Expressions — Russ Cox — серия статей главного разработчика RE2 о теории и практике regex-движков, включая историческую связь с работами Томпсона
Regular expression Denial of Service (ReDoS) — OWASP — описание атаки, примеры уязвимых паттернов, рекомендации по защите
ReDoS — Wikipedia — обзор проблемы с примерами реальных инцидентов и CVE
Details of the Cloudflare outage on July 2, 2019 — Cloudflare Blog — детальный разбор инцидента: как одна регулярка положила глобальную CDN на 27 минут
PCRE2 Pattern Syntax — спецификация синтаксиса PCRE2, включая проверки окружения и обратные ссылки
Rust vs C++: A Modern Take on Performance and Safety — The New Stack — сравнение языков по безопасности памяти, производительности и экосистеме
The Computer Language Benchmarks Game — сравнительные бенчмарки языков программирования, включая Rust и C++