6 ms·

Code Search at Google: Han-Wen and Zoekt

jeffbee 3y ago
Is Zoekt actually in use at Google and if so how does it related to Kythe? I know the Zoekt instance for Bazel exists, but the Kythe index also exists (https://cs.opensource.google/bazel/bazel https://cs.opensource.google/bazel/bazel)
- dmoy 3y ago
  It has nothing to do with Kythe. I'm on the Kythe team, and I don't know off the top of my head what Zoekt is. Looking it up, I see it's some sort of trigram search, which means if it's used at all (I have no idea), it's codesearch proper, not Kythe. The Kythe index is the semantic index of the codebase, Codesearch does all of the text/regex/etc searching.
  - sluongng 3y ago
    Are you sure? There is find definition and references in https://cs.opensource.google/bazel/bazel https://cs.opensource.google/bazel/bazel and Im quite sure it's thanks to the Kythe indexing job Bazel team is running in CI.
    - dmoy 3y ago
      The refs & jump to def in bazel/bazel are using Kythe, yes. But that is Kythe's semantic index from running (also it's Kythe team running it, not bazel team). It's not the Codesearch trigram/text search (which again, I have no idea if it uses zoekt).
- hanwenn 3y ago
  Not in use that I know
frutiger 3y ago
I’m a bit confused as to how https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html isn’t mentioned at all.
- beyang 3y ago
  Zoekt was heavily inspired by Google's internal code search, as mentioned in the blog post. The original version of the internal code search is described in the rsc post. Zoekt keeps some of the foundational ideas (e.g., trigram index), but was a from-scratch implementation. We probably should link to the rsc post for completeness, will update.
  - hanwenn 3y ago
    At the time that I started Zoekt (2016), Google's internal codesearch used suffix arrays for the string matching, which the team wasn't happy with, presumably because of the algorithmic complexity and indexing slowness. The Codesearch team was exploring alternatives, one of them the technique described in https://link.springer.com/article/10.1007/s11390-016-1618-6 https://link.springer.com/article/10.1007/s11390-016-1618-6. The positional trigrams were a simplification of this, that they didn't mind me open sourcing. so, in terms of algorithms, Zoekt wasn't actually inspired by Google's internal code search. The precise query syntax of zoekt is mostly copied from google's internal syntax, though.
- IshKebab 3y ago
  It is mentioned.
  - frutiger 3y ago
    It is now, but wasn’t earlier.
- hanwenn 3y ago
  Russ Cox' trigram approach uses document IDs for the posting list, which makes the index much smaller, but gives less precise (ie. slower) matching. This is mentioned in the design doc at https://github.com/sourcegraph/zoekt/blob/main/doc/design.md#positional-trigrams https://github.com/sourcegraph/zoekt/blob/main/doc/design.md....
j2kun 3y ago
IIUC, the main thing that Google's internal codesearch does that makes it superior to external systems (outside of an IDE, like GitHub code search) is that Google actually builds everything, and so it can incorporate that information into its index. There's only so much text search can do when you have macros generating code.
- dmoy 3y ago
  Yea that would be Kythe. We build almost everything, across 44-45 different programming languages, and postprocess that into a giant semantic graph. Most major parts are open sourced at kythe.io, and there's a somewhat dated talk given by Luke here: https://youtu.be/VYI3ji8aSM0 https://youtu.be/VYI3ji8aSM0
  - dmoy 3y ago
    > macros Corollary: while we can do a lot with indexing generated code (even cross language) in Kythe, there are limits. Macros may be one, I forget atm
  - sa46 3y ago
    Do you have any cases studies or success stories for non-Google repos? I miss code search but I’m not sure how close Kythe is to code-search-in-a-box.
    - dmoy 3y ago
      Internally, we use variants of our pipeline to index a variety of open source repos, and some non-blaze/bazel internal repos. Those are often non-Google repos. But we're using some internal postprocessing and serving logic to actually create and host the final index. Unfortunately I don't know if there's any significant use of Kythe outside of Google. We get a handful of questions on the open source repo from time to time, but that's all I know about.
- beyang 3y ago
  Great call out! We've built this code navigation infra on top of Zoekt into Sourcegraph. Example: https://sourcegraph.com/github.com/golang/go/-/blob/src/net/http/server.go?L86:6-86:13#tab=references https://sourcegraph.com/github.com/golang/go/-/blob/src/net/... Docs: https://docs.sourcegraph.com/code_navigation/explanations/precise_code_navigation https://docs.sourcegraph.com/code_navigation/explanations/pr...
tromp 3y ago
Wondering how this tool got named after the Dutch verb for seek, I found this quote on its github page [1]. > "Zoekt, en gij zult spinazie eten" - Jan Eertink > ("seek, and ye shall eat spinach" - My primary school teacher) [1] https://github.com/sourcegraph/zoekt https://github.com/sourcegraph/zoekt
- est 3y ago
  author https://github.com/hanwen https://github.com/hanwen
- consp 3y ago
  Note, "zoekt" is the imperative, which makes sense asking a tool to do something.
  - deleted 3y ago
    [deleted]
JohnMakin 3y ago
I didn't start my tech journey til late 00's, so it's constantly surprising to me that something as ubiquitous as git only came out in 2005. Is it possible at all this story helped spur the widespread adoption of git (the early implementation of this tool)?
- jeffbee 3y ago
  I think it is odd that the story mentions git at all. Git5, the mentioned wrapper around piper, has only a niche audience when I last used it 5 years ago, and it was a demonstrated fact that the users of it were less productive than perforce users. Whether that was causal or not was unknown.
  - hanwenn 3y ago
    Hi, I'm the Han-Wen from the title. The story mentions git because git5 got me into developer tooling. More in particular, it put me in touch with Shawn Pearce who ran the Git/Gerrit team at Google. When I went to work for him, Shawn wanted to have codesearch support in Gerrit, and Zoekt was ultimately the outcome of my explorations in this space. IIRC, Git5 was deleted approximately 5 years ago because Fig (the Hg based replacement) had taken over all the use cases
    - dag11 3y ago
      Is Fig still kicking? I worked on it a bit as an intern back in 2014, but Mercurial has also been on its way out of mainstream support over the last few years. It was a really neat project!
      - hanwenn 3y ago
        See https://www.youtube.com/watch?v=bx_LGilOuE4 https://www.youtube.com/watch?v=bx_LGilOuE4. I think the plan is to replace to it with something based off JJ.
  - billllll 3y ago
    I agree there doesn't seem to be a good connection between work on version control and work on code search. However, I don't think it makes sense to downplay git5. Anecdotally, basically everybody knew about it, and I'd constantly run into people using it (which is by itself noteworthy since nobody was exactly talking about version control all the time). Git5 was at the time the most robust solution to chain commits, which was tedious bordering on impossible without some tool. Without definitive data, I wouldn't say users were less productive with git5: it definitely was a useful tool that people at least recommended for chain commits. I was definitely more productive with it. There were a lot of footguns though, and I do think the hg wrapper that superseded it was way better.
IshKebab 3y ago
The same algorithm is also used in Hound (https://github.com/hound-search/hound https://github.com/hound-search/hound) though I have to say the best implementation of code search by far that I've seen is https://grep.app https://grep.app You really should check it out if you haven't already. It's incredibly useful; I used it all the time. Not open source though.

Is Zoekt actually in use at Google and if so how does it related to Kythe? I know the Zoekt instance for Bazel exists, but the Kythe index also exists (https://cs.opensource.google/bazel/bazel https://cs.opensource.google/bazel/bazel)

dmoy 3y ago
It has nothing to do with Kythe. I'm on the Kythe team, and I don't know off the top of my head what Zoekt is. Looking it up, I see it's some sort of trigram search, which means if it's used at all (I have no idea), it's codesearch proper, not Kythe. The Kythe index is the semantic index of the codebase, Codesearch does all of the text/regex/etc searching.
- sluongng 3y ago
  Are you sure? There is find definition and references in https://cs.opensource.google/bazel/bazel https://cs.opensource.google/bazel/bazel and Im quite sure it's thanks to the Kythe indexing job Bazel team is running in CI.
  - dmoy 3y ago
    The refs & jump to def in bazel/bazel are using Kythe, yes. But that is Kythe's semantic index from running (also it's Kythe team running it, not bazel team). It's not the Codesearch trigram/text search (which again, I have no idea if it uses zoekt).
hanwenn 3y ago
Not in use that I know

frutiger 3y ago

I’m a bit confused as to how https://swtch.com/~rsc/regexp/regexp4.html https://swtch.com/~rsc/regexp/regexp4.html isn’t mentioned at all.

beyang 3y ago
Zoekt was heavily inspired by Google's internal code search, as mentioned in the blog post. The original version of the internal code search is described in the rsc post. Zoekt keeps some of the foundational ideas (e.g., trigram index), but was a from-scratch implementation. We probably should link to the rsc post for completeness, will update.
- hanwenn 3y ago
  At the time that I started Zoekt (2016), Google's internal codesearch used suffix arrays for the string matching, which the team wasn't happy with, presumably because of the algorithmic complexity and indexing slowness. The Codesearch team was exploring alternatives, one of them the technique described in https://link.springer.com/article/10.1007/s11390-016-1618-6 https://link.springer.com/article/10.1007/s11390-016-1618-6. The positional trigrams were a simplification of this, that they didn't mind me open sourcing. so, in terms of algorithms, Zoekt wasn't actually inspired by Google's internal code search. The precise query syntax of zoekt is mostly copied from google's internal syntax, though.
IshKebab 3y ago
It is mentioned.
- frutiger 3y ago
  It is now, but wasn’t earlier.
hanwenn 3y ago
Russ Cox' trigram approach uses document IDs for the posting list, which makes the index much smaller, but gives less precise (ie. slower) matching. This is mentioned in the design doc at https://github.com/sourcegraph/zoekt/blob/main/doc/design.md#positional-trigrams https://github.com/sourcegraph/zoekt/blob/main/doc/design.md....

j2kun 3y ago

IIUC, the main thing that Google's internal codesearch does that makes it superior to external systems (outside of an IDE, like GitHub code search) is that Google actually builds everything, and so it can incorporate that information into its index. There's only so much text search can do when you have macros generating code.

dmoy 3y ago
Yea that would be Kythe. We build almost everything, across 44-45 different programming languages, and postprocess that into a giant semantic graph. Most major parts are open sourced at kythe.io, and there's a somewhat dated talk given by Luke here: https://youtu.be/VYI3ji8aSM0 https://youtu.be/VYI3ji8aSM0
- dmoy 3y ago
  > macros Corollary: while we can do a lot with indexing generated code (even cross language) in Kythe, there are limits. Macros may be one, I forget atm
- sa46 3y ago
  Do you have any cases studies or success stories for non-Google repos? I miss code search but I’m not sure how close Kythe is to code-search-in-a-box.
  - dmoy 3y ago
    Internally, we use variants of our pipeline to index a variety of open source repos, and some non-blaze/bazel internal repos. Those are often non-Google repos. But we're using some internal postprocessing and serving logic to actually create and host the final index. Unfortunately I don't know if there's any significant use of Kythe outside of Google. We get a handful of questions on the open source repo from time to time, but that's all I know about.
beyang 3y ago
Great call out! We've built this code navigation infra on top of Zoekt into Sourcegraph. Example: https://sourcegraph.com/github.com/golang/go/-/blob/src/net/http/server.go?L86:6-86:13#tab=references https://sourcegraph.com/github.com/golang/go/-/blob/src/net/... Docs: https://docs.sourcegraph.com/code_navigation/explanations/precise_code_navigation https://docs.sourcegraph.com/code_navigation/explanations/pr...

tromp 3y ago

Wondering how this tool got named after the Dutch verb for seek, I found this quote on its github page [1]. > "Zoekt, en gij zult spinazie eten" - Jan Eertink > ("seek, and ye shall eat spinach" - My primary school teacher) [1] https://github.com/sourcegraph/zoekt https://github.com/sourcegraph/zoekt

est 3y ago
author https://github.com/hanwen https://github.com/hanwen
consp 3y ago
Note, "zoekt" is the imperative, which makes sense asking a tool to do something.
- deleted 3y ago
  [deleted]

JohnMakin 3y ago

I didn't start my tech journey til late 00's, so it's constantly surprising to me that something as ubiquitous as git only came out in 2005. Is it possible at all this story helped spur the widespread adoption of git (the early implementation of this tool)?

jeffbee 3y ago
I think it is odd that the story mentions git at all. Git5, the mentioned wrapper around piper, has only a niche audience when I last used it 5 years ago, and it was a demonstrated fact that the users of it were less productive than perforce users. Whether that was causal or not was unknown.
- hanwenn 3y ago
  Hi, I'm the Han-Wen from the title. The story mentions git because git5 got me into developer tooling. More in particular, it put me in touch with Shawn Pearce who ran the Git/Gerrit team at Google. When I went to work for him, Shawn wanted to have codesearch support in Gerrit, and Zoekt was ultimately the outcome of my explorations in this space. IIRC, Git5 was deleted approximately 5 years ago because Fig (the Hg based replacement) had taken over all the use cases
  - dag11 3y ago
    Is Fig still kicking? I worked on it a bit as an intern back in 2014, but Mercurial has also been on its way out of mainstream support over the last few years. It was a really neat project!
    - hanwenn 3y ago
      See https://www.youtube.com/watch?v=bx_LGilOuE4 https://www.youtube.com/watch?v=bx_LGilOuE4. I think the plan is to replace to it with something based off JJ.
- billllll 3y ago
  I agree there doesn't seem to be a good connection between work on version control and work on code search. However, I don't think it makes sense to downplay git5. Anecdotally, basically everybody knew about it, and I'd constantly run into people using it (which is by itself noteworthy since nobody was exactly talking about version control all the time). Git5 was at the time the most robust solution to chain commits, which was tedious bordering on impossible without some tool. Without definitive data, I wouldn't say users were less productive with git5: it definitely was a useful tool that people at least recommended for chain commits. I was definitely more productive with it. There were a lot of footguns though, and I do think the hg wrapper that superseded it was way better.

IshKebab 3y ago

The same algorithm is also used in Hound (https://github.com/hound-search/hound https://github.com/hound-search/hound) though I have to say the best implementation of code search by far that I've seen is https://grep.app https://grep.app You really should check it out if you haven't already. It's incredibly useful; I used it all the time. Not open source though.