Codesearch

Я думаю, примерно каждый из хоть раз искал по коду. А как это работает?

Самый базовый инструмент в нашем арсенале: grep. Устройство у него не очень сложное: забираем регулярку и идём по всем файлам слева направо сверху вниз. Пытаемся регулярку сматчить. Оно будет работать хорошо, пока ваша кодовая база не становится слишком жирной. Даже если вы используете ripgrep. На масштабах GitHub эта проблема показана в [3]. Ниже расскажу, что можно делать в таких случаях.

В изначальной задаче можно выделить два контекста:

1. Вы хотите искать по одному большому репозиторию. 

2. Вы хотите делать поиск на условном GitHub, когда репозиториев очень много. 

В первом случае, понятно, вам скорее всего важна точность и полнота, когда во втором вы наверняка хотите учитывать некоторые популярности репозиториев, а значит GitHub нужно ранжирование. В случае 1 скорее нет: скорее всего хочется видеть результаты и доверять поиску в том смысле, что если результата нет, то и в коде такого нет. Для особенно больших репозиториев ранжирование убивает возможность прогружать запросы "на лету". Kinda стримить результаты юзеру. Потому что в таком случае вам нужно сначала получить эти самые результаты и только потом начать их скорить. 

C GitHub конечно есть продуктовые вопросики. Например вот такой тред с замечательным названием Github search sucks (and how it could be better).
Про него писать отдельно не буду. В ссылочках можете найти всякого.

Когда мы говорим про быстрый поиск, мы всегда приходим к индексам. 

Что предлагал Russ Cox в [1]: пусть у нас есть строка

codesearch

Разобьём её на триграммы:

cod ode des ese sea ear arc rch

И сделаем стандартный обратный индекс (откуда он появляется, писал в посте про boolean retrieval model): для триграммы запишем список документов (постинг), в которых она встречается. 

cod: 1, 3, 4, 9, 15, ...
ode: 1, 2, 4, 5, 23, ...
...
rch: 4, 12, 73, ...

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

Конечно, это решение можно можно улучшать. Например хранить не триграммы, а 4-граммы. Когда вы увеличиваете размер n-граммы, поиск логично ускоряется, потому что вариативность падает и общее количество постингов уменьшается -> пересекать их проще. 

А можно усложнить постинг и хранить не только document_id, но и что-то рядом, что позволит нам сократить изначальное множество документов, по которым нужно делать проверку подстроки. Самое понятное и простое -- хранить позицию триграммы в документе. Тогда позиции последовательных триграмм в запросе будут отличаться на один. Проверять это становится не сильно проще, потому можно попробовать уложить это в маску. Например, хранить байт maskRow, в котором ставить 1 на позицию {номер строки в документе % 8}. Аналогично с колонками, но там надо учитывать offset триграммы в запросе относительно начала запроса. Это уже ощутимо может срезать общее количество документов, которые мы будем перепроверять после пересечения постингов. 

Рядом можно положить ещё один индекс для каждого документа вида:

n-gram: (n_gram_hash, line, column)

После того, как мы пересекли все постинги по запросу, можно бинпоиском по хешам поискать все n-граммы из запроса и быстро понять, есть ли нужная подстрока в документе. 

Часто можно увидеть настройку с вкл/выкл регистронезависимого поиска. Кажется, тут надо держать рядом индекс, который просто делает to_lower для всех символов в коде, но есть ли тут какие-то дополнительные манипуляции/оптимизации, я не знаю. Мб можно держать не второй индекс рядом, а в первый складывать to_lower(n-граммы), которые меняются после to_lower, ведь интуитивно кажется, что большинство n-грамм меняться не должны. И искать по обычному флоу. Но как на практике это работает и как сильно растёт память, хз. 

Но часто кодсёрч это не просто про точное совпадение запроса и подстроки в документе, а ещё и про регулярки. В их случае подход выше не особо применим. 

В зависимости от видов регулярок, которые хочется поддерживать, можно сводить задачу к boolean retrieval: искать по отдельным частям регулярки и объединять результат. 

Важный момент -- как индекс обновлять. Вообще это довольно сложная задача. Дефолтный подход -- строить индекс с нуля каждый раз. Мы год назад писали, что делаем так и сколько это занимает. Из базовых мыслей тут можно шардировать данные, особенно если объёмы этого требуют. Так можно будет переваривать не всё, а только один шард. А ещё обрабатывать отдельные случаи. Например, когда файл удалился, не реально удалять его, а просто выкидывать из результатов некоторое время.

Надеюсь, у вас всё найдётся.

Ссылочки:

[1]. [article] Regular Expression Matching with a Trigram Index or How Google Code Search Worked

[2]. [article] A brief history of code search at GitHub

[3]. [article] The technology behind GitHub’s new code search

[4]. [talk] Lessons from building GitHub code search

[5]. [article] A Survey of Techniques for Finding Code