Support search expressions

[rvantonder]

Search expressions allows composing various filters and search patterns using and and or expressions. Previous requests and GH issues refer to a rich history of terminology, like "nested search" and "hierarchical search" #1005 #636. These terms mean different things in various contexts, but don't really define a language or semantics, only a high level desired behavior and proposed syntax. The prior discussions or proposals make it hard to concretely implement a spec for what has been called "nested search" and "hierarchical search". So, I am going to avoid that terminology and instead refer to search expressions, which have a concrete spec based on our grammar and search capabilities. Search expressions implement a set of operations that satisfy some (but not necessarily all) of the high level behavior described previously for "nested" and "hierarchical" search. Search expressions in their current form can be extended to satisfy all of the previously described behavior, subject to additional syntax and evaluation logic.

Search expressions simply mean that we can compose (or combine) various filters and search patterns with our current set of operators: and and or. For example, it supports expressing queries like:

• (repo:foo or repo:bar) (baz and qux)
• (repo:foo (file:bar or file:baz) qux) or (repo:foobar file:barfoo bazfoo)
• (type:commit or type:diff) my commit

Expressions can be nested and parenthesized group imply scope for certain filters (e.g., repo: scopes file: or search patterns). Nested expressions may also be called subqueries.

This issue tracks the implementation for supporting search expressions.

• As a first step, we normalize queries by expanding operators. This is implemented and explained in search: add DNF conversion for search expressions #12381.
• The normalized form must be validated. Our grammar supports various expressions, but not every syntactically valid search expression can be evaluated.
• Evaluate search expressions search: add general search expressions search: add general search expressions #13907
• Resolve leftover UI concerns:
  • UI issue 1: Query transformation for filters like case and patterntype that are erased by toggles. When multiple expressions contain these, the query transformation of toggles is too naive--it assumes subqueries are not possible and so does not transform all affected expressions. Search query with multiple case:yes|no is silently modified #13958 Implement TypeScript query parser in webapp #14016
  • UI issue 2: Tabs for different result types code, symbol, repo. However, we are slightly inconsistent with code already, so this needs to be rethought despite search expressions.
• Optionally: rewrite or-expressions to compatible regex forms, which are more efficient to evaluate. For example: repo:foo or repo:bar => repo:foo|bar, or translate directly to Zoekt query Add translation layer for optimizing backend search engine work #15145
• Optionally: define a way to process scope in the absence of parentheses. For example, should the query:

file:bar baz or qux

mean that file:bar scopes both of baz or qux, or only baz? The grammar by default does the latter, but we do perform heuristics for the former. One possibility is to define a scoping rule that is left-to-right for repo:, file:, and patterns, but this implies that order of parameters is significant and should be preserved, which could be a significant change.

• Open question: alerting on partial results of or-expressions, e.g., for repo:^github\.com/sourcegraph/sourcegraph$ (rev:3.18 or rev:3.17 or rev:3.16 or rev:3.15) file:CHANGELOG.md, no 3.16 rev exists, and we would get a runtime warning if we only searched 3.16. We should still show results. Question is: should we also be raising an alert here or not?

---

Search expressions are a generalization of work on related issues for and/or operators captured in #11009 #10623 #7823

[rvantonder]

Done.