mozilla/dxr — pull request #325 by erikrose (2014-09-05 20:39:58+00:00)
Title: Whip trigram extractor into shape, and sketch PathFilter

In order to do regex queries, we need to extract static substrings from the users' regexes. We then bang those against trigram indices in ES to (hopefully drastically) narrow down the document set we need to examine. Finally, we run the actual regex against those.

Previously, on a "trigrammer" branch, we were extracting actual trigrams from the regex. It turns out we don't need to do that: ES is more than happy to split longer strings into trigrams itself. In addition, that gives us a selectivity boost: the relative positions of the trigrams is something ES can deliver. Thus, we here take the old trigrammer machinery from the "trigrammer" branch and adapt it to return longer strings.

The most interesting work in this PR is the simplified() method of SubstringTree. This takes a tree of boolean nodes (Ands and Ors and, at the leaves, strings) and does some easy simplifications. For example, the regex `yo|hello|there` would emit `Or(['yo', 'hello', 'there'])`, simplified to `Or(['hello', 'there'])` since "yo" is too short to be any use against a trigram index. Ands come into play when there is a wildcard of some kind that we can't (or aren't yet smart enough to) make use of between two other, nonoptional strings: for example, `hello+ there` might become `And(['hello', ' there'])` (or `And(['hello', 'o there'])` if we were really smart.

es_regex_filter and PathFilter, the other attractions, are sketches, not yet intended to be complete, but they are useful as an illustration of why the lower-level stuff is the way it is, so I want them committed together.

I also deleted a lot of dead code. There still remain some parts of the Cox method I half started on; they live because I do intend to go in that direction eventually, probably post-launch, to enable us to extract strings more intelligently.