19 ms·

Code search is hard

302 points by stevekrouse 3y ago

semiquaver 3y ago
Be careful with trigram indexes. At least in the postgres 10 era they caused severe index bloat for frequently updated tables.
- peter_l_downs 3y ago
  Interesting, do you know anywhere I can easily read more about this? (I will do my own research, too.)
  - boyter 3y ago
    Its a result of trigrams themselves. For example turning searchcode (please ignore plug, this is just the example I had to hand) goes from 1 thing you would need to index into 8. "searchcode" -> [sea, ear, arc, rch, chc, hco, cod, ode] As a result the index rapidly becomes larger than you would expect.
healeycodes 3y ago
When a val is deployed on val town, my understanding is that it's parsed/compiled. At that point, can you save the parts of the program that people might search for? Names of imports, functions, variables, comments, etc.
- MH15 3y ago
  A val is just Typescript, no? So unless they are also storing the AST it would be JavaScript and that's it
nox101 3y ago
any nuggets here? https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/ https://github.blog/2023-02-06-the-technology-behind-githubs...
- SomaticPirate 3y ago
  Would also recommend the related video https://www.youtube.com/watch?v=CqZA_KmygKw https://www.youtube.com/watch?v=CqZA_KmygKw
- boyter 3y ago
  Yes, although the lack of detail about the sparse grams is frustrating.
skybrian 3y ago
It seems like some of their gists have documentation attached and maybe that’s enough? I’m not sure I’m all that interested in seeing undocumented gists in search results.
peter_l_downs 3y ago
Surprised not to see Livegrep [0] on the list of options. Very well-engineered technology; the codebase is clean (if a little underdocumented on the architecture side) and you should be able to index your code without much difficulty. Built with Bazel (~meh, but useful if you don't have an existing cpp toolchain all set up) and there are prebuilt containers you can run. Try that first. By the way, there's a demo running here for the linux kernel, you can try it out and see what you think: https://livegrep.com/search/linux https://livegrep.com/search/linux EDIT: by the way, "code search" is deeply underspecified. Before trying to compare all these different options, you really would benefit from writing down all the different types of queries you think your users will want to ask, including why they want to run that query and what results they'd expect. Building/tuning search is almost as difficult a product problem as it is an engineering problem. [0] https://github.com/livegrep/livegrep https://github.com/livegrep/livegrep
- isker 3y ago
  When I investigated using livegrep for code search at work, it really struggled to scale to a large number of repositories. At least at the time (a few years ago) indexing in livegrep was a monolithic operation: you index all repos at once, which produces one giant index. This does not work well once you're past a certain threshold. I also recall that the indexes it produces are pretty heavyweight in terms of memory requirements, but I don't have any numbers on hand to justify that claim. Zoekt (also mentioned in TFA) has the correct properties in this regard. Except in niche configurations that are probably only employed at sourcegraph, each repo is (re)indexed independently and produces a separate set of index files. But its builtin web UI left much to be desired (especially compared to livegrep), so I built one: https://github.com/isker/neogrok https://github.com/isker/neogrok.
  - peter_l_downs 3y ago
    I like this better than livegrep. I haven't actually operated either zoekt OR livegrep before, but I'll probably start with zoekt+neogrok next time I want to stand up a codesearch page. Thanks for building and sharing this!
  - 3y ago
ayberk 3y ago
It indeed is hard, and a good code search platform makes life so much easier. If I ever leave Google, the internal code search is for sure going to be the thing I miss the most. It's so well integrated into how everything else works (blaze target finding, guice bindings etc), I can't imagine my life without it. I remember to appreciate it even more every time I use Github's search. Not that it's bad, it's just inherently so much harder to build a generalized code search platform.
- peter_l_downs 3y ago
  If you ever leave you can use Livegrep, which was based on code-search work done at Google. I personally don't use it right now but it's great and will probably meet all your needs. [0] https://github.com/livegrep/livegrep https://github.com/livegrep/livegrep
  - init 3y ago
    I've used both Code Search and Livegrep. No, Livegrep does not even come close to what Code Search can do. Sourcegraph is the closest thing I know of.
    - isker 3y ago
      Agreed. There are some public building blocks available (e.g. Kythe or meta's Glean) but having something generic that produces the kind of experience you can get on cs.chromium.org seems impossible. You need such bespoke build integration across an entire organization to get there. Basic text search, as opposed to navigation, is all you'll get from anything out of the box.
      - init 3y ago
        In a past job I built a code search clone on top of Kythe, Zoekt and LSP (for languages that didn't have bazel integration). I got help from another colleague to make the UI based on Monaco. We create a demo that many people loved but we didn't productionize it for a few reasons (it was an unfunded hackathon project and the company was considering another solution when they already had Livegrep) Producing the Kythe graph from the bazel artifacts was the most expensive part. Working with Kythe is also not easy as there is no documentation on how to run it at scale.
chasil 3y ago
Oracle has USER/ALL/DBA_SOURCE views, and all of the PL/SQL (SQL/PSM) code that has been loaded into the database is presented there. These are all cleartext visible unless they have been purposefully obfuscated. It has columns for the owner, object name, LINE[NUMBER] and TEXT[VARCHAR2(4000)] columns and you can use LIKE or regexp_like() on any of the retained source code. I wonder if EnterpriseDB implements these inside of Postgres, and/or if they are otherwise available as an extension. Since most of SQL/PSM came from Oracle anyway, these would be an obvious desired feature. https://en.wikipedia.org/wiki/SQL/PSM https://en.wikipedia.org/wiki/SQL/PSM
worldsayshi 3y ago
I suppose using something like tree sitter to get a consistent abstract syntax tree to work with would be a good starting point. And then try building a custom analyzer (if using elasticsearch lingo) with that?
- azornathogron 3y ago
  Another option is to start with Kythe, which is Google's own open source framework for getting a uniform cross-language semantic layer: https://kythe.io/ https://kythe.io/ Worth looking at as a source of inspiration and design ideas even if you don't want to use it itself.
- samatman 3y ago
  Might be overkill unless you're looking to do semantic search. I've thought about what a search DSL for code would look like, it's challenging to embody a query like "method which takes an Int64 and has a variable idx in it" into something compact and memorable. But a tokenizer seems like a good place to start, I think that's the right granularity for this kind of application. You'd want to do some chunking so that foo.bar doesn't find every foo and every bar, that sort of thing. Code search is, as the title says, a hard problem. But a language-aware token stream, the one you'd get from the lexer, is probably where one should start in building the database.
  - worldsayshi 3y ago
    Sure you should definitively not try to do the overkill use case first but I would assume that tree sitter can emit "just" tokens as well? Getting the flexibility and control of a tool like tree sitter should allow you to quickly throw away stuff like comments and keywords if you want since you can do syntax aware filtering. Then again I haven't used tree-sitter, can just imagine that this is a strength of it.
IshKebab 3y ago
I would use Hound.
jackbravo 3y ago
Would LLM vector embeddings work in this context? I'm guessing they should since they are very good at understanding code.
- CityOfThrowaway 3y ago
  Yes but generating that index would be expensive
  - anonymousDan 3y ago
    Why exactly? You mean to construct the embeddings or to embed the queries?
- ivanovm 3y ago
  I've found embeddings to perform quite poorly on code because 1) user queries are not semantically similar to target code in most cases 2) often times two very concretely related pieces of code are not at all semantically similar
sqs 3y ago
I'm at Sourcegraph (mentioned in the blog post). We obviously have to deal with massive scale, but for anyone starting out adding code search to their product, I'd recommend not starting with an index and just doing on-the-fly searching until that does not scale. It actually will scale well for longer than you think if you just need to find the first N matches (because that result buffer can be filled without needing to search everything exhaustively). Happy to chat with anyone who's building this kind of thing, including with folks at Val Town, which is awesome.
- isker 3y ago
  And when you're ready to do indexed search, Zoekt (over which Sourcegraph graciously took maintainership a while ago) is the best way to do it that I've found. After discounting both Livegrep and Hound (they both struggled to perform in various dimensions with the amount of stuff we wanted indexed, Hound moreso than Livegrep), we migrated to Zoekt from a (necessarily) very old and creaky deployment of OpenGrok and it's night and day, both in terms of indexing performance and search performance/ergonomics. Sourcegraph of course adds many more sophisticated features on top of just the code search that Zoekt provides.
- morgante 3y ago
  I've been surprised at how far you can get without indexing. Ex. I always assume we'll need to add an index to speed up GritQL (https://github.com/getgrit/gritql https://github.com/getgrit/gritql), but we've gotten pretty far with doing search entirely on the fly.
  - worldsayshi 3y ago
    What does 'on the fly' entail here?
    - simonw 3y ago
      I'm going to guess brute force - scan everything for the search term, rather than trying to use an index. I'm always amazed at how fast ripgrep (rg) can brute force it's way through hundreds of MBs of source code.
bawolff 3y ago
Surprised that hound https://github.com/hound-search/hound https://github.com/hound-search/hound isn't mentioned. I thought it was the leader of open source solutions in this space. I've been using Wikimedia's instance ( https://codesearch.wmcloud.org/search/ https://codesearch.wmcloud.org/search/ ) and have generally been pretty happy with what it provides.
- isker 3y ago
  Hound has made an interesting choice to not bound searches. https://codesearch.wmcloud.org/search/?q=test&files=&excludeFiles=&repos= https://codesearch.wmcloud.org/search/?q=test&files=&exclude... produces an ajax request that (for me) took 13s to produce a 55MB JSON response, and then takes many more seconds to render into the DOM. Properly bounding search response sizes was one of the things I had to ensure Zoekt could do in its JSON APIs that I use in neogrok: https://github.com/sourcegraph/zoekt/pull/615 https://github.com/sourcegraph/zoekt/pull/615
  - bawolff 3y ago
    Yeah, i agree, that is weird. Especially if you search for something super common like "function" you basically DoS it.
sdesol 3y ago
> It’s hard to find any accounts of code-search using FTS I'm actually going to be doing this soon. I've thought about code search for close to a decade, but I walked away from it, because there really isn't a business for it. However, now with AI, I'm more interested in using it to help find relevant context and I have no reason to believe FTS won't work. In the past I used Lucene, but I'm planning on going all in with Postgres. The magic to fast code search (search in general), is keeping things small. As long as your search solution is context aware, you can easily leverage Postgres sharding to reduce index sizes. I'm a strong believer in "disk space is cheap, time isn't", which means I'm not afraid to create as many indexes as required, to shave 100's of milliseconds of searches.
- bevekspldnw 3y ago
  Mmm, it’s not that straight forward: indexes can vastly slow down large scale ingest, so it’s really about when to index as well. I work with a lot of multi billion row datasets and a lot of my recent focus has been on developing strategies to avoid the slow down with ingest, and then enjoying the speed up for indexed on search. I’ve also gotten some mjnd boggling speed increases by summarizing key searchable data in smaller tables, some with JSONB columns that are abstractions of other data, indexing those, and using pg prewarm to serve those tables purely from memory. I literally went from queries taking actual days to < 1 sec.
  - sdesol 3y ago
    Yeah I agree. I've had a lot of practice so far with coordinating between hundreds of thousands of tables to ensure ingestion/lookup is fast. Everything boils down to optimizing for your query patterns. I also believe in using what I call "compass tables" (like your summarization tables), which I guess are indexes of indexes.
    - bevekspldnw 3y ago
      Scaling databases both oddly frustrating and also rewarding. Getting that first query that executes at 10x of the old one feels great. The week of agony that makes it possible…less so.
jessemhan 3y ago
Good scalable codebase search is tough. We built a scalable, fast, and super simple solution for codebase semantic search: https://phorm.ai https://phorm.ai
Macha 3y ago
> This is a pretty bad index: it has words that should be stop words, like function, and won’t split a.toString() into two tokens because . is not a default word boundary. So github used to (maybe still does) "fix" this one and it's annoying. Although github are ramping up their IDE like find-usages, it's still not perfect, so somethings you just want to a text search equivalent for "foo.bar()" for all the uses it misses and this stemming behaviour then finds every while where foo and bar are mentioned which bloats results.
ricardobeat 3y ago
I don't understand their hand-waving of Zoekt. It was built exactly for this purpose, and is not a "new infrastructure commitment" any more than the other options. The server is a single binary, the indexer is also a single binary, can't get any simpler than that. To me it doesn't make sense to be more scared of it than Elasticsearch...
- deleted 3y ago
  [deleted]
- deleted 3y ago
  [deleted]
philippemnoel 3y ago
ParadeDB founder here. We'd love to be supported on Render, if the Render folks are open to it...
727564797069706 3y ago
If you're serious about scaling up, definitely consider Vespa (https://vespa.ai https://vespa.ai). At serious scale, Vespa will likely knock all the other options out of the park.
herrington_d 3y ago
Is it possible to combine n-gram and AST to dump a better indexing? Take `sourceCode.toString()` as an example, the AST can dump it to `sourceCode` and `toString`. A further indexer can break `sourceCode` to `source` and `code`. For ast dumping, project like https://github.com/ast-grep/ast-grep https://github.com/ast-grep/ast-grep can help.
- boyter 3y ago
  You could, but I don't know what you gain out of it. The underlying index would be almost the same size, and n-gram would also allow you to search for e.t for example which you are losing in this process.
campbel 3y ago
> Sourcegraph’s maintained fork of Zoekt is pretty cool, but is pretty fearfully niche and would be a big, new infrastructure commitment. I don't think Zoekt is as scary as this article makes it out to be. I set this up at my current company after getting experience with it at Shopify and its really great.
boyter 3y ago
Code search is indeed hard. Stop words, stemming and such do rule out most off the shelf indexing solutions but you can usually turn them off. You can even get around the splitting issues of things like a.toString() With some pre-processing of the content. However were you really get into a world of pain is allowing someone to search for ring in the example. You can use partial term search, prefix, infix, or suffix but this massively bloats the index and is slow to run. The next thing you try is trigrams, and suddenly you have to deal with false positive matches. So you add a positional portion to your index, and all of a sudden the underlying index is larger than the content you are indexing. Its good fun though. For those curious about it I would also suggest reading posts by Michael Stapelberg https://michael.stapelberg.ch/posts/ https://michael.stapelberg.ch/posts/ who writes about Debian Code Search (which I believe he started) in addition to the other posts mentioned here. Shameless plug, I also write about this https://boyter.org/posts/how-i-built-my-own-index-for-searchcode/ https://boyter.org/posts/how-i-built-my-own-index-for-search... where I go into some of the issues when building a custom index for searchcode.com Oddly enough I think you can go a long way brute forcing the search if you don't do anything obviously wrong. For situations where you are only allowed to search a small portion of the content, say just your own (which looks applicable in this situation) that's what I would do. Adding an index is really only useful when you start searching at scale or you are getting semantic search out of it. For keywords which is what the article appears to be talking about, that's what I would be inclined to do.
- sgift 3y ago
  The preprocessing that you need is (in Lucene nomenclature, but it's the same principle for search in general) an Analyzer (the component, which knows to prepare the plain text that gets inside for storing it in an index and the corresponding component for a search query) made for code search. That's not different from analyzers for other languages (Stemming sucks for almost everything but English). Thinking about it .. the frontend of most compilers for a language could maybe make a pretty good Analyzer. It already knows language specific components and can split them into parts it needs for further processing, which is basically what an analyzer does.
nbenitezl 3y ago
Also https://github.com/Debian/dcs https://github.com/Debian/dcs
simonw 3y ago
A feature I'd appreciate from Val Town is the ability to point it to a GitHub repo that I own and have it write the source code for all of my Vals to that repo, on an ongoing basis. Then I could use GitHub code search, or even "git pull" and run ripgrep.
- nbbaier 3y ago
  I've actually built a tool in Val Town that could be used as the basis for something like this: https://www.val.town/v/nbbaier/valToGH https://www.val.town/v/nbbaier/valToGH Right now it only commits one val, but it would be trivial to write it into a loop and then use a scheduled val to have it run over all your vals as a cron job!
  - nbbaier 3y ago
    nvm, just went in and changed it so now you could theoretically do all your vals at once. I realized though that it will not update file contents as is, so need to figure that out ...
thesuperbigfrog 3y ago
OpenGrok (https://github.com/oracle/opengrok https://github.com/oracle/opengrok) is a wonderful tool to search a codebase. It runs on-prem and handles lots of popular programming languages.
- AstralJaeger 3y ago
  I fully agree with you there, OpenGrok is a wonderful, oudated-looking and feeling but lightning fast code search engine!
pomdtr 3y ago
Hey! I'm a val.town fanboy and I immediately thought about a workaround while reading the blog post: What if I dumped every publics vals in Github, in order to be able to user their (awesome) search ? So here is my own "Val Town Search": https://val-town-search.pomdtr.me https://val-town-search.pomdtr.me And here is the repo containing all vals, updated hourly thanks to a github action: https://github.com/pomdtr/val-town-mirror https://github.com/pomdtr/val-town-mirror
- simonw 3y ago
  Well this is fun... git clone https://github.com/pomdtr/val-town-mirror cd val-town-mirror rg news.ycombinator.com Now I can ripgrep search public Vals, e.g. to see who's hitting Hacker News from a Val.
  - pomdtr 3y ago
    Yeah, and you can finally run/debug vals locally (kind of, the version query param is not yet supported)
- MatthiasPortzel 3y ago
  That is, uh, one solution, to say the least. There’s a HN comment I’ll never forget where the commenter suggests that Discord move their search infrastructure to a series of text file searched with ripgrep, but Val.town’s scale is small enough that they could actually consider it.
- nbbaier 3y ago
  This is great!
- pomdtr 3y ago
  I ended up writing my own article: https://code-search-is-easy.pomdtr.me/ https://code-search-is-easy.pomdtr.me/
fizx 3y ago
There's a million paths, but here's one I like. Use ElasticSearch. It will scale more than Postgres. Three hosted options are AWS, Elastic, Bonsai. I founded Bonsai and retired (so am partial), but they will provide the best human support for you, and you won't have to worry about java Xmx. Your goal with ES is to use the Regex PatternAnalyzer to split the code into reasonable exact code-shaped tokens (not english words). Here's a rough GPT4 explanation with sample config that I'd head towards: https://chat.openai.com/share/e4d08586-b7ef-48f2-9de1-7f82ea3c1f14 https://chat.openai.com/share/e4d08586-b7ef-48f2-9de1-7f82ea...
- bytefish 3y ago
  GitLab is also using ElasticSearch, so one could recreate the ElasticSearch Indices they came up with. [1] They also share some of the challenges, they faced along the way. It also discusses interesting challenges, like implementing the authorization model. [2], [3] When GitHub removed its most useful Search feature, which is sorting results by date, I wrote a small “Search Engine” with ElasticSearch to selectively index Microsoft repositories. It works good enough for my needs. [4] [1] https://gitlab.com/gitlab-org/gitlab/-/blob/7bbbc00bd871aeb67660a1c42ff30c65ba6ed47a/ee/lib/elastic/latest/config.rb https://gitlab.com/gitlab-org/gitlab/-/blob/7bbbc00bd871aeb6... [2] https://about.gitlab.com/blog/2019/07/16/elasticsearch-update/ https://about.gitlab.com/blog/2019/07/16/elasticsearch-updat... [3] https://about.gitlab.com/blog/2020/04/28/elasticsearch-update/ https://about.gitlab.com/blog/2020/04/28/elasticsearch-updat... [4] https://github.com/bytefish/ElasticsearchCodeSearch https://github.com/bytefish/ElasticsearchCodeSearch
- philippemnoel 3y ago
  Elasticsearch is good, and it does scale, but it is much more cumbersome and expensive to scale and operate than Postgres. If you use the managed service, you'll pay for the operational pain in the form of higher pricing. The Postgres movement is strong and extensions like ParadeDB https://github.com/paradedb/paradedb https://github.com/paradedb/paradedb are designed specifically to solve this pain point (Disclaimer: I work for ParadeDB)
deleted 3y ago
[deleted]
johnthescott 3y ago
the rum index has worked well for us on roughly 1TB of pdfs. written by postgrespro, same folks who wrote core text search and json indexing. not sure why rum not in core. we have no problems. https://github.com/postgrespro/rum
- philippemnoel 3y ago
  RUM is good, but it lacks some of the more complex features like language tokenizers, etc. that a full search engine library like Lucene/Tantivy (and ParadeDB in Postgres) offer
  - johnthescott 2y ago
    could you elaborate? i was under the impression the text search config and dictionaries did support such remappings. we only query in english or literal, so my knowledge is limited.
civilized 3y ago
Is "hard" a bit of an overstatement for problems like "I'm using a library that mangles the query"? Couldn't you search for the literal text the user inputs? Maybe let them use regex?
metalrain 3y ago
I think you need to parse the code and build AST to make good search. Even then normalizing over different aliases, may not be simple.
- vladak 3y ago
  The question is what code. In preprocessed languages there can be lots of ifdefs and such for various environments and architectures.
amarshall 3y ago
> GitHub’s search is excellent Is it? I find it near-useless most of the time, and cloning + ripgrep to be way more efficient. Perhaps the problem is more in the UX being awful than the actual search.
ethanwillis 3y ago
There are tools from bioinformatics that would be more applicable here for code search than the ones linguistics has made for searching natural language.
hiAndrewQuinn 3y ago
Basic code searching skills seems like something new developers are never explicitly taught, but which is an absolutely crucial skill to build early on. I guess the knowledge progression I would recommend would look something kind this: - Learning about Ctrl+F, which works basically everywhere. - Transitioning to ripgrep https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep - I wouldn't even call this optional, it's truly an incredible and very discoverable tool. Requires keeping a terminal open, but that's a good thing for a newbie! - Optional, but highly recommended: Learning one of the powerhouse command line editors. Teenage me recommended Emacs; current me recommends vanilla vim, purely because some flavor of it is installed almost everywhere. This is so that you can grep around and edit in the same window. - In the same vein, moving back from ripgrep and learning about good old fashioned grep, with a few flags rg uses by default: `grep -r` for recursive search, `grep -ri` for case insensitive recursive search, and `grep -ril` for case insensitive recursive "just show me which files this string is found in" search. Some others too, season to taste. - Finally hitting the wall with what ripgrep can do for you and switching to an actual indexed, dedicated code search tool.
- datascienced 3y ago
  Also Github is a fantastic tool for searching code across repos, ones you may not even have cloned yet! Either public ones or org ones.
  - lambdaba 3y ago
    yeah, I particularly like the combo regex + path: or lang:
  - tex0 3y ago
    The new GitHub CS is pretty great indeed. Still not on par with it's role model, but getting closer.
    - greymalik 3y ago
      What’s its role model?
bch 3y ago
Why am I not seeing anything here about ctags[0] or cscope[1]? Are they that out of fashion? cscope language comprehension appears limited to C/C++ and Java, but “ctags” (I think I use “uctags” atm) language support is quite broad and ubiquitous… [0] https://en.wikipedia.org/wiki/Ctags https://en.wikipedia.org/wiki/Ctags [1] https://en.wikipedia.org/wiki/Cscope https://en.wikipedia.org/wiki/Cscope
- signa11 3y ago
  exactly THIS <sorry for shouting !> the only problem with `cscope` is that for modern c++ based code-bases it is woefully inadequate. for plain / vanilla c based code-bases f.e. linux-kernel etc. it is just _excellent_ language-servers using clangd/ccls/... are definitely useful, but quite resource heavy. for example, each of these tools seem to starting new threads per file (!) and there are no knobs to not do that. i don't really understand this rationale at all. yes, i have seen this exact behavior with both clangd and ccls. oftentimes, the memory in these processes balloon to some godawful numbers (more with clangd than ccls), necessitating a kill. moreover, this might be an unpopular opinion, but mixing any regex based tool (ripgrep/... come to mind) with language-server f.e. because the language server does not really find what you are looking for, or does not do that fast enough, are major points against it. if you already have language-server running, regex based tools should not be required at all. i don't really understand the reason for sql'ization of code searches at all. it is not a 'natural' interface. typical usage is to see 'who calls this function', 'where is the definition at' of this function etc. etc.
jillesvangurp 3y ago
It's why IDE and developer tool builders have long had the insight that in order to do code search properly, you need to open up the compiler platform as a lot of what you need to do boils down to reconstructing the exact same internal representations that a compiler would use. And of course good code search is the basis for refactoring support, auto completion, and other common IDE features. Easier said then done of course as tools are often an afterthought for compiler builders. Even Jetbrains made this mistake with Kotlin initially, which is something they are partially rectifying with Kotlin 2.0 now to make it easier to support things like incremental compilation. The Rust community had this insight as well with a big effort a few years ago to make Rust more IDE friendly. IBM actually nailed this with Eclipse back in the day and that hasn't really been matched since then. Intellij never even got close to this being 2-3 orders of magnitudes slower. We're talking seconds vs. milliseconds here. Eclipse had a blazing fast incremental compiler for Java that could even partially compile code in the presence of syntax errors. The IDEs representation of that code was hooked into that compiler. With Eclipse, you could introduce a typo and break part of your code and watch the IDE mark all the files that now had issues across your code base getting red squiggles instantly. Fix the typo and the squiggles went away, also without any delay. That's only possible if you have a mapping between those files and your syntax tree, which is exactly what Eclipse was doing because it was hooked into the incremental compiler. Intellij was never able to do this, it will actively lie to you about things being fine/not fine until you rebuild your code and it will show phantom errors a lot when it's internal state gets out of sync with what's on disk. It often requires full rebuilds to fix this. If you run something, there's a several second lag while it compiles things. Reason: the IDE internal state is calculated separately from the compiler and this gets out of sync easily. When you run something, it has to compile your code because it hasn't been compiled yet. That's often when you find out the IDE was lying to you about things being ready to run. With Eclipse all this was instantly and unambiguous because it shared the internal state with the compiler. If it compiled, your IDE would be error free, if it didn't it wouldn't be. And it compiled incrementally and really quickly so you would know instantly. It had many flaws and annoying bugs but that's a feature I miss.
- high_na_euv 3y ago
  >Easier said then done of course as tools are often an afterthought for compiler builders. Except for Microsoft's Roslyn (.NET compiler) https://willspeak.me/2021/11/24/red-green-syntax-trees-an-overview.html https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov... https://ericlippert.com/2012/06/08/red-green-trees/ https://ericlippert.com/2012/06/08/red-green-trees/ Ive used Roslyn SDKs to build tools and it is really good
reeyadalli 3y ago
I have never actually given it much thought about the difference between code search and normal "literature". Interesting read!!
louiskw 3y ago
https://github.com/BloopAI/bloop https://github.com/BloopAI/bloop Is fully open source and has full text + regex search built on tantivy fyi
nojvek 3y ago
You can do to_tsvector “plain” and keep the strings intact. No lemming, stemming. We use plain tsvectors on a gin index and change the queries to allow prefix based searching. So “wo he” matches “hello world”. Perhaps I should write a blog about it. Took me a few days to read PG documentation to get where we are at. The only thing it doesn’t handle is typo tolerance.
- philippemnoel 3y ago
  Tsvector is amazing and it goes a long way, but unfortunately as you say it lacks some of more complex FTS features like typo tolerance, language tokenizers, etc.
ectopasm83 3y ago
>Lemmatization: some search indexes are even fancy enough to substitute synonyms for more common words, so that you can search for “excellent” and get results for documents including “great.” This isn't what lemmatization is about. Stemming the word ‘Caring‘ would return ‘Car‘. Lemmatizing the word ‘Caring‘ would return ‘Care‘.
kermatt 3y ago
Are any of the tools mentioned in these comments better suited to searching SQL code, both DML and DDL? We maintain a tree of files with each object in a separate "CREATE TABLE|VIEW|PROCEDURE|FUNCTION" script. This supports code search with grep, but something that could find references to an object when the name qualifications are not uniform would be very useful: INSERT INTO table INSERT INTO schema.table INSERT INTO database.schema.table Can all be done with regex, but search is not so easy for programmers new to expressions.
ivanovm 3y ago
One of the most interesting approaches to code search I've seen recently (no affiliation) https://github.com/pyjarrett/septum https://github.com/pyjarrett/septum The hardest part about getting code search right imo is grabbing the right amount of surrounding context, which septum is aimed at solving on a per-file basis. Another one I'm surprised hasn't been mentioned is stack-graphs (https://github.com/github/stack-graphs https://github.com/github/stack-graphs), which tries to incrementally resolve symbolic relationships across the whole codebase. It powers github's cross-file precise indexing and conceptually makes a lot of sense, though I've struggled to get the open source version to work
hanwenn 3y ago
Hi, I wrote zoekt. From what I understand valtown does, I would try to use brute force first (ie. something equivalent to ripgrep). Once that starts breaking down, you could use last-updated-timestamps to reduce the brute force: * make a trigram index using Zoekt or Hound for JS snippets older than X * do brute force on snippets newer than X * advance X as you're indexing newer data. If the snippets are small, you can probably use a (trigram => snippets) index for space savings relative to a (trigram => offset) index.

302 points by stevekrouse 3y ago

Be careful with trigram indexes. At least in the postgres 10 era they caused severe index bloat for frequently updated tables.

peter_l_downs 3y ago
Interesting, do you know anywhere I can easily read more about this? (I will do my own research, too.)
- boyter 3y ago
  Its a result of trigrams themselves. For example turning searchcode (please ignore plug, this is just the example I had to hand) goes from 1 thing you would need to index into 8. "searchcode" -> [sea, ear, arc, rch, chc, hco, cod, ode] As a result the index rapidly becomes larger than you would expect.

healeycodes 3y ago

When a val is deployed on val town, my understanding is that it's parsed/compiled. At that point, can you save the parts of the program that people might search for? Names of imports, functions, variables, comments, etc.

MH15 3y ago
A val is just Typescript, no? So unless they are also storing the AST it would be JavaScript and that's it

nox101 3y ago

any nuggets here? https://github.blog/2023-02-06-the-technology-behind-githubs-new-code-search/ https://github.blog/2023-02-06-the-technology-behind-githubs...

SomaticPirate 3y ago
Would also recommend the related video https://www.youtube.com/watch?v=CqZA_KmygKw https://www.youtube.com/watch?v=CqZA_KmygKw
boyter 3y ago
Yes, although the lack of detail about the sparse grams is frustrating.

skybrian 3y ago

It seems like some of their gists have documentation attached and maybe that’s enough? I’m not sure I’m all that interested in seeing undocumented gists in search results.

peter_l_downs 3y ago

Surprised not to see Livegrep [0] on the list of options. Very well-engineered technology; the codebase is clean (if a little underdocumented on the architecture side) and you should be able to index your code without much difficulty. Built with Bazel (~meh, but useful if you don't have an existing cpp toolchain all set up) and there are prebuilt containers you can run. Try that first. By the way, there's a demo running here for the linux kernel, you can try it out and see what you think: https://livegrep.com/search/linux https://livegrep.com/search/linux EDIT: by the way, "code search" is deeply underspecified. Before trying to compare all these different options, you really would benefit from writing down all the different types of queries you think your users will want to ask, including why they want to run that query and what results they'd expect. Building/tuning search is almost as difficult a product problem as it is an engineering problem. [0] https://github.com/livegrep/livegrep https://github.com/livegrep/livegrep

isker 3y ago
When I investigated using livegrep for code search at work, it really struggled to scale to a large number of repositories. At least at the time (a few years ago) indexing in livegrep was a monolithic operation: you index all repos at once, which produces one giant index. This does not work well once you're past a certain threshold. I also recall that the indexes it produces are pretty heavyweight in terms of memory requirements, but I don't have any numbers on hand to justify that claim. Zoekt (also mentioned in TFA) has the correct properties in this regard. Except in niche configurations that are probably only employed at sourcegraph, each repo is (re)indexed independently and produces a separate set of index files. But its builtin web UI left much to be desired (especially compared to livegrep), so I built one: https://github.com/isker/neogrok https://github.com/isker/neogrok.
- peter_l_downs 3y ago
  I like this better than livegrep. I haven't actually operated either zoekt OR livegrep before, but I'll probably start with zoekt+neogrok next time I want to stand up a codesearch page. Thanks for building and sharing this!
- 3y ago

ayberk 3y ago

It indeed is hard, and a good code search platform makes life so much easier. If I ever leave Google, the internal code search is for sure going to be the thing I miss the most. It's so well integrated into how everything else works (blaze target finding, guice bindings etc), I can't imagine my life without it. I remember to appreciate it even more every time I use Github's search. Not that it's bad, it's just inherently so much harder to build a generalized code search platform.

peter_l_downs 3y ago
If you ever leave you can use Livegrep, which was based on code-search work done at Google. I personally don't use it right now but it's great and will probably meet all your needs. [0] https://github.com/livegrep/livegrep https://github.com/livegrep/livegrep
- init 3y ago
  I've used both Code Search and Livegrep. No, Livegrep does not even come close to what Code Search can do. Sourcegraph is the closest thing I know of.
  - isker 3y ago
    Agreed. There are some public building blocks available (e.g. Kythe or meta's Glean) but having something generic that produces the kind of experience you can get on cs.chromium.org seems impossible. You need such bespoke build integration across an entire organization to get there. Basic text search, as opposed to navigation, is all you'll get from anything out of the box.
    - init 3y ago
      In a past job I built a code search clone on top of Kythe, Zoekt and LSP (for languages that didn't have bazel integration). I got help from another colleague to make the UI based on Monaco. We create a demo that many people loved but we didn't productionize it for a few reasons (it was an unfunded hackathon project and the company was considering another solution when they already had Livegrep) Producing the Kythe graph from the bazel artifacts was the most expensive part. Working with Kythe is also not easy as there is no documentation on how to run it at scale.

chasil 3y ago

Oracle has USER/ALL/DBA_SOURCE views, and all of the PL/SQL (SQL/PSM) code that has been loaded into the database is presented there. These are all cleartext visible unless they have been purposefully obfuscated. It has columns for the owner, object name, LINE[NUMBER] and TEXT[VARCHAR2(4000)] columns and you can use LIKE or regexp_like() on any of the retained source code. I wonder if EnterpriseDB implements these inside of Postgres, and/or if they are otherwise available as an extension. Since most of SQL/PSM came from Oracle anyway, these would be an obvious desired feature. https://en.wikipedia.org/wiki/SQL/PSM https://en.wikipedia.org/wiki/SQL/PSM

worldsayshi 3y ago

I suppose using something like tree sitter to get a consistent abstract syntax tree to work with would be a good starting point. And then try building a custom analyzer (if using elasticsearch lingo) with that?

azornathogron 3y ago
Another option is to start with Kythe, which is Google's own open source framework for getting a uniform cross-language semantic layer: https://kythe.io/ https://kythe.io/ Worth looking at as a source of inspiration and design ideas even if you don't want to use it itself.
samatman 3y ago
Might be overkill unless you're looking to do semantic search. I've thought about what a search DSL for code would look like, it's challenging to embody a query like "method which takes an Int64 and has a variable idx in it" into something compact and memorable. But a tokenizer seems like a good place to start, I think that's the right granularity for this kind of application. You'd want to do some chunking so that foo.bar doesn't find every foo and every bar, that sort of thing. Code search is, as the title says, a hard problem. But a language-aware token stream, the one you'd get from the lexer, is probably where one should start in building the database.
- worldsayshi 3y ago
  Sure you should definitively not try to do the overkill use case first but I would assume that tree sitter can emit "just" tokens as well? Getting the flexibility and control of a tool like tree sitter should allow you to quickly throw away stuff like comments and keywords if you want since you can do syntax aware filtering. Then again I haven't used tree-sitter, can just imagine that this is a strength of it.

IshKebab 3y ago

I would use Hound.

jackbravo 3y ago

Would LLM vector embeddings work in this context? I'm guessing they should since they are very good at understanding code.

CityOfThrowaway 3y ago
Yes but generating that index would be expensive
- anonymousDan 3y ago
  Why exactly? You mean to construct the embeddings or to embed the queries?
ivanovm 3y ago
I've found embeddings to perform quite poorly on code because 1) user queries are not semantically similar to target code in most cases 2) often times two very concretely related pieces of code are not at all semantically similar

sqs 3y ago

I'm at Sourcegraph (mentioned in the blog post). We obviously have to deal with massive scale, but for anyone starting out adding code search to their product, I'd recommend not starting with an index and just doing on-the-fly searching until that does not scale. It actually will scale well for longer than you think if you just need to find the first N matches (because that result buffer can be filled without needing to search everything exhaustively). Happy to chat with anyone who's building this kind of thing, including with folks at Val Town, which is awesome.

isker 3y ago
And when you're ready to do indexed search, Zoekt (over which Sourcegraph graciously took maintainership a while ago) is the best way to do it that I've found. After discounting both Livegrep and Hound (they both struggled to perform in various dimensions with the amount of stuff we wanted indexed, Hound moreso than Livegrep), we migrated to Zoekt from a (necessarily) very old and creaky deployment of OpenGrok and it's night and day, both in terms of indexing performance and search performance/ergonomics. Sourcegraph of course adds many more sophisticated features on top of just the code search that Zoekt provides.
morgante 3y ago
I've been surprised at how far you can get without indexing. Ex. I always assume we'll need to add an index to speed up GritQL (https://github.com/getgrit/gritql https://github.com/getgrit/gritql), but we've gotten pretty far with doing search entirely on the fly.
- worldsayshi 3y ago
  What does 'on the fly' entail here?
  - simonw 3y ago
    I'm going to guess brute force - scan everything for the search term, rather than trying to use an index. I'm always amazed at how fast ripgrep (rg) can brute force it's way through hundreds of MBs of source code.

bawolff 3y ago

Surprised that hound https://github.com/hound-search/hound https://github.com/hound-search/hound isn't mentioned. I thought it was the leader of open source solutions in this space. I've been using Wikimedia's instance ( https://codesearch.wmcloud.org/search/ https://codesearch.wmcloud.org/search/ ) and have generally been pretty happy with what it provides.

isker 3y ago
Hound has made an interesting choice to not bound searches. https://codesearch.wmcloud.org/search/?q=test&files=&excludeFiles=&repos= https://codesearch.wmcloud.org/search/?q=test&files=&exclude... produces an ajax request that (for me) took 13s to produce a 55MB JSON response, and then takes many more seconds to render into the DOM. Properly bounding search response sizes was one of the things I had to ensure Zoekt could do in its JSON APIs that I use in neogrok: https://github.com/sourcegraph/zoekt/pull/615 https://github.com/sourcegraph/zoekt/pull/615
- bawolff 3y ago
  Yeah, i agree, that is weird. Especially if you search for something super common like "function" you basically DoS it.

sdesol 3y ago

> It’s hard to find any accounts of code-search using FTS I'm actually going to be doing this soon. I've thought about code search for close to a decade, but I walked away from it, because there really isn't a business for it. However, now with AI, I'm more interested in using it to help find relevant context and I have no reason to believe FTS won't work. In the past I used Lucene, but I'm planning on going all in with Postgres. The magic to fast code search (search in general), is keeping things small. As long as your search solution is context aware, you can easily leverage Postgres sharding to reduce index sizes. I'm a strong believer in "disk space is cheap, time isn't", which means I'm not afraid to create as many indexes as required, to shave 100's of milliseconds of searches.

bevekspldnw 3y ago
Mmm, it’s not that straight forward: indexes can vastly slow down large scale ingest, so it’s really about when to index as well. I work with a lot of multi billion row datasets and a lot of my recent focus has been on developing strategies to avoid the slow down with ingest, and then enjoying the speed up for indexed on search. I’ve also gotten some mjnd boggling speed increases by summarizing key searchable data in smaller tables, some with JSONB columns that are abstractions of other data, indexing those, and using pg prewarm to serve those tables purely from memory. I literally went from queries taking actual days to < 1 sec.
- sdesol 3y ago
  Yeah I agree. I've had a lot of practice so far with coordinating between hundreds of thousands of tables to ensure ingestion/lookup is fast. Everything boils down to optimizing for your query patterns. I also believe in using what I call "compass tables" (like your summarization tables), which I guess are indexes of indexes.
  - bevekspldnw 3y ago
    Scaling databases both oddly frustrating and also rewarding. Getting that first query that executes at 10x of the old one feels great. The week of agony that makes it possible…less so.

jessemhan 3y ago

Good scalable codebase search is tough. We built a scalable, fast, and super simple solution for codebase semantic search: https://phorm.ai https://phorm.ai

Macha 3y ago

> This is a pretty bad index: it has words that should be stop words, like function, and won’t split a.toString() into two tokens because . is not a default word boundary. So github used to (maybe still does) "fix" this one and it's annoying. Although github are ramping up their IDE like find-usages, it's still not perfect, so somethings you just want to a text search equivalent for "foo.bar()" for all the uses it misses and this stemming behaviour then finds every while where foo and bar are mentioned which bloats results.

ricardobeat 3y ago

I don't understand their hand-waving of Zoekt. It was built exactly for this purpose, and is not a "new infrastructure commitment" any more than the other options. The server is a single binary, the indexer is also a single binary, can't get any simpler than that. To me it doesn't make sense to be more scared of it than Elasticsearch...

deleted 3y ago
[deleted]
deleted 3y ago
[deleted]

philippemnoel 3y ago

ParadeDB founder here. We'd love to be supported on Render, if the Render folks are open to it...

727564797069706 3y ago

If you're serious about scaling up, definitely consider Vespa (https://vespa.ai https://vespa.ai). At serious scale, Vespa will likely knock all the other options out of the park.

herrington_d 3y ago

Is it possible to combine n-gram and AST to dump a better indexing? Take `sourceCode.toString()` as an example, the AST can dump it to `sourceCode` and `toString`. A further indexer can break `sourceCode` to `source` and `code`. For ast dumping, project like https://github.com/ast-grep/ast-grep https://github.com/ast-grep/ast-grep can help.

boyter 3y ago
You could, but I don't know what you gain out of it. The underlying index would be almost the same size, and n-gram would also allow you to search for e.t for example which you are losing in this process.

campbel 3y ago

> Sourcegraph’s maintained fork of Zoekt is pretty cool, but is pretty fearfully niche and would be a big, new infrastructure commitment. I don't think Zoekt is as scary as this article makes it out to be. I set this up at my current company after getting experience with it at Shopify and its really great.

boyter 3y ago

Code search is indeed hard. Stop words, stemming and such do rule out most off the shelf indexing solutions but you can usually turn them off. You can even get around the splitting issues of things like a.toString() With some pre-processing of the content. However were you really get into a world of pain is allowing someone to search for ring in the example. You can use partial term search, prefix, infix, or suffix but this massively bloats the index and is slow to run. The next thing you try is trigrams, and suddenly you have to deal with false positive matches. So you add a positional portion to your index, and all of a sudden the underlying index is larger than the content you are indexing. Its good fun though. For those curious about it I would also suggest reading posts by Michael Stapelberg https://michael.stapelberg.ch/posts/ https://michael.stapelberg.ch/posts/ who writes about Debian Code Search (which I believe he started) in addition to the other posts mentioned here. Shameless plug, I also write about this https://boyter.org/posts/how-i-built-my-own-index-for-searchcode/ https://boyter.org/posts/how-i-built-my-own-index-for-search... where I go into some of the issues when building a custom index for searchcode.com Oddly enough I think you can go a long way brute forcing the search if you don't do anything obviously wrong. For situations where you are only allowed to search a small portion of the content, say just your own (which looks applicable in this situation) that's what I would do. Adding an index is really only useful when you start searching at scale or you are getting semantic search out of it. For keywords which is what the article appears to be talking about, that's what I would be inclined to do.

sgift 3y ago
The preprocessing that you need is (in Lucene nomenclature, but it's the same principle for search in general) an Analyzer (the component, which knows to prepare the plain text that gets inside for storing it in an index and the corresponding component for a search query) made for code search. That's not different from analyzers for other languages (Stemming sucks for almost everything but English). Thinking about it .. the frontend of most compilers for a language could maybe make a pretty good Analyzer. It already knows language specific components and can split them into parts it needs for further processing, which is basically what an analyzer does.

nbenitezl 3y ago

Also https://github.com/Debian/dcs https://github.com/Debian/dcs

simonw 3y ago

A feature I'd appreciate from Val Town is the ability to point it to a GitHub repo that I own and have it write the source code for all of my Vals to that repo, on an ongoing basis. Then I could use GitHub code search, or even "git pull" and run ripgrep.

nbbaier 3y ago
I've actually built a tool in Val Town that could be used as the basis for something like this: https://www.val.town/v/nbbaier/valToGH https://www.val.town/v/nbbaier/valToGH Right now it only commits one val, but it would be trivial to write it into a loop and then use a scheduled val to have it run over all your vals as a cron job!
- nbbaier 3y ago
  nvm, just went in and changed it so now you could theoretically do all your vals at once. I realized though that it will not update file contents as is, so need to figure that out ...

thesuperbigfrog 3y ago

OpenGrok (https://github.com/oracle/opengrok https://github.com/oracle/opengrok) is a wonderful tool to search a codebase. It runs on-prem and handles lots of popular programming languages.

AstralJaeger 3y ago
I fully agree with you there, OpenGrok is a wonderful, oudated-looking and feeling but lightning fast code search engine!

pomdtr 3y ago

Hey! I'm a val.town fanboy and I immediately thought about a workaround while reading the blog post: What if I dumped every publics vals in Github, in order to be able to user their (awesome) search ? So here is my own "Val Town Search": https://val-town-search.pomdtr.me https://val-town-search.pomdtr.me And here is the repo containing all vals, updated hourly thanks to a github action: https://github.com/pomdtr/val-town-mirror https://github.com/pomdtr/val-town-mirror

simonw 3y ago
Well this is fun... git clone https://github.com/pomdtr/val-town-mirror cd val-town-mirror rg news.ycombinator.com Now I can ripgrep search public Vals, e.g. to see who's hitting Hacker News from a Val.
- pomdtr 3y ago
  Yeah, and you can finally run/debug vals locally (kind of, the version query param is not yet supported)
MatthiasPortzel 3y ago
That is, uh, one solution, to say the least. There’s a HN comment I’ll never forget where the commenter suggests that Discord move their search infrastructure to a series of text file searched with ripgrep, but Val.town’s scale is small enough that they could actually consider it.
nbbaier 3y ago
This is great!
pomdtr 3y ago
I ended up writing my own article: https://code-search-is-easy.pomdtr.me/ https://code-search-is-easy.pomdtr.me/

fizx 3y ago

There's a million paths, but here's one I like. Use ElasticSearch. It will scale more than Postgres. Three hosted options are AWS, Elastic, Bonsai. I founded Bonsai and retired (so am partial), but they will provide the best human support for you, and you won't have to worry about java Xmx. Your goal with ES is to use the Regex PatternAnalyzer to split the code into reasonable exact code-shaped tokens (not english words). Here's a rough GPT4 explanation with sample config that I'd head towards: https://chat.openai.com/share/e4d08586-b7ef-48f2-9de1-7f82ea3c1f14 https://chat.openai.com/share/e4d08586-b7ef-48f2-9de1-7f82ea...

bytefish 3y ago
GitLab is also using ElasticSearch, so one could recreate the ElasticSearch Indices they came up with. [1] They also share some of the challenges, they faced along the way. It also discusses interesting challenges, like implementing the authorization model. [2], [3] When GitHub removed its most useful Search feature, which is sorting results by date, I wrote a small “Search Engine” with ElasticSearch to selectively index Microsoft repositories. It works good enough for my needs. [4] [1] https://gitlab.com/gitlab-org/gitlab/-/blob/7bbbc00bd871aeb67660a1c42ff30c65ba6ed47a/ee/lib/elastic/latest/config.rb https://gitlab.com/gitlab-org/gitlab/-/blob/7bbbc00bd871aeb6... [2] https://about.gitlab.com/blog/2019/07/16/elasticsearch-update/ https://about.gitlab.com/blog/2019/07/16/elasticsearch-updat... [3] https://about.gitlab.com/blog/2020/04/28/elasticsearch-update/ https://about.gitlab.com/blog/2020/04/28/elasticsearch-updat... [4] https://github.com/bytefish/ElasticsearchCodeSearch https://github.com/bytefish/ElasticsearchCodeSearch
philippemnoel 3y ago
Elasticsearch is good, and it does scale, but it is much more cumbersome and expensive to scale and operate than Postgres. If you use the managed service, you'll pay for the operational pain in the form of higher pricing. The Postgres movement is strong and extensions like ParadeDB https://github.com/paradedb/paradedb https://github.com/paradedb/paradedb are designed specifically to solve this pain point (Disclaimer: I work for ParadeDB)

deleted 3y ago

[deleted]

johnthescott 3y ago

the rum index has worked well for us on roughly 1TB of pdfs. written by postgrespro, same folks who wrote core text search and json indexing. not sure why rum not in core. we have no problems. https://github.com/postgrespro/rum

philippemnoel 3y ago
RUM is good, but it lacks some of the more complex features like language tokenizers, etc. that a full search engine library like Lucene/Tantivy (and ParadeDB in Postgres) offer
- johnthescott 2y ago
  could you elaborate? i was under the impression the text search config and dictionaries did support such remappings. we only query in english or literal, so my knowledge is limited.

civilized 3y ago

Is "hard" a bit of an overstatement for problems like "I'm using a library that mangles the query"? Couldn't you search for the literal text the user inputs? Maybe let them use regex?

metalrain 3y ago

I think you need to parse the code and build AST to make good search. Even then normalizing over different aliases, may not be simple.

vladak 3y ago
The question is what code. In preprocessed languages there can be lots of ifdefs and such for various environments and architectures.

amarshall 3y ago

> GitHub’s search is excellent Is it? I find it near-useless most of the time, and cloning + ripgrep to be way more efficient. Perhaps the problem is more in the UX being awful than the actual search.

ethanwillis 3y ago

There are tools from bioinformatics that would be more applicable here for code search than the ones linguistics has made for searching natural language.

hiAndrewQuinn 3y ago

Basic code searching skills seems like something new developers are never explicitly taught, but which is an absolutely crucial skill to build early on. I guess the knowledge progression I would recommend would look something kind this: - Learning about Ctrl+F, which works basically everywhere. - Transitioning to ripgrep https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep - I wouldn't even call this optional, it's truly an incredible and very discoverable tool. Requires keeping a terminal open, but that's a good thing for a newbie! - Optional, but highly recommended: Learning one of the powerhouse command line editors. Teenage me recommended Emacs; current me recommends vanilla vim, purely because some flavor of it is installed almost everywhere. This is so that you can grep around and edit in the same window. - In the same vein, moving back from ripgrep and learning about good old fashioned grep, with a few flags rg uses by default: `grep -r` for recursive search, `grep -ri` for case insensitive recursive search, and `grep -ril` for case insensitive recursive "just show me which files this string is found in" search. Some others too, season to taste. - Finally hitting the wall with what ripgrep can do for you and switching to an actual indexed, dedicated code search tool.

datascienced 3y ago
Also Github is a fantastic tool for searching code across repos, ones you may not even have cloned yet! Either public ones or org ones.
- lambdaba 3y ago
  yeah, I particularly like the combo regex + path: or lang:
- tex0 3y ago
  The new GitHub CS is pretty great indeed. Still not on par with it's role model, but getting closer.
  - greymalik 3y ago
    What’s its role model?

bch 3y ago

Why am I not seeing anything here about ctags[0] or cscope[1]? Are they that out of fashion? cscope language comprehension appears limited to C/C++ and Java, but “ctags” (I think I use “uctags” atm) language support is quite broad and ubiquitous… [0] https://en.wikipedia.org/wiki/Ctags https://en.wikipedia.org/wiki/Ctags [1] https://en.wikipedia.org/wiki/Cscope https://en.wikipedia.org/wiki/Cscope

signa11 3y ago
exactly THIS <sorry for shouting !> the only problem with `cscope` is that for modern c++ based code-bases it is woefully inadequate. for plain / vanilla c based code-bases f.e. linux-kernel etc. it is just _excellent_ language-servers using clangd/ccls/... are definitely useful, but quite resource heavy. for example, each of these tools seem to starting new threads per file (!) and there are no knobs to not do that. i don't really understand this rationale at all. yes, i have seen this exact behavior with both clangd and ccls. oftentimes, the memory in these processes balloon to some godawful numbers (more with clangd than ccls), necessitating a kill. moreover, this might be an unpopular opinion, but mixing any regex based tool (ripgrep/... come to mind) with language-server f.e. because the language server does not really find what you are looking for, or does not do that fast enough, are major points against it. if you already have language-server running, regex based tools should not be required at all. i don't really understand the reason for sql'ization of code searches at all. it is not a 'natural' interface. typical usage is to see 'who calls this function', 'where is the definition at' of this function etc. etc.

jillesvangurp 3y ago

It's why IDE and developer tool builders have long had the insight that in order to do code search properly, you need to open up the compiler platform as a lot of what you need to do boils down to reconstructing the exact same internal representations that a compiler would use. And of course good code search is the basis for refactoring support, auto completion, and other common IDE features. Easier said then done of course as tools are often an afterthought for compiler builders. Even Jetbrains made this mistake with Kotlin initially, which is something they are partially rectifying with Kotlin 2.0 now to make it easier to support things like incremental compilation. The Rust community had this insight as well with a big effort a few years ago to make Rust more IDE friendly. IBM actually nailed this with Eclipse back in the day and that hasn't really been matched since then. Intellij never even got close to this being 2-3 orders of magnitudes slower. We're talking seconds vs. milliseconds here. Eclipse had a blazing fast incremental compiler for Java that could even partially compile code in the presence of syntax errors. The IDEs representation of that code was hooked into that compiler. With Eclipse, you could introduce a typo and break part of your code and watch the IDE mark all the files that now had issues across your code base getting red squiggles instantly. Fix the typo and the squiggles went away, also without any delay. That's only possible if you have a mapping between those files and your syntax tree, which is exactly what Eclipse was doing because it was hooked into the incremental compiler. Intellij was never able to do this, it will actively lie to you about things being fine/not fine until you rebuild your code and it will show phantom errors a lot when it's internal state gets out of sync with what's on disk. It often requires full rebuilds to fix this. If you run something, there's a several second lag while it compiles things. Reason: the IDE internal state is calculated separately from the compiler and this gets out of sync easily. When you run something, it has to compile your code because it hasn't been compiled yet. That's often when you find out the IDE was lying to you about things being ready to run. With Eclipse all this was instantly and unambiguous because it shared the internal state with the compiler. If it compiled, your IDE would be error free, if it didn't it wouldn't be. And it compiled incrementally and really quickly so you would know instantly. It had many flaws and annoying bugs but that's a feature I miss.

high_na_euv 3y ago
>Easier said then done of course as tools are often an afterthought for compiler builders. Except for Microsoft's Roslyn (.NET compiler) https://willspeak.me/2021/11/24/red-green-syntax-trees-an-overview.html https://willspeak.me/2021/11/24/red-green-syntax-trees-an-ov... https://ericlippert.com/2012/06/08/red-green-trees/ https://ericlippert.com/2012/06/08/red-green-trees/ Ive used Roslyn SDKs to build tools and it is really good

reeyadalli 3y ago

I have never actually given it much thought about the difference between code search and normal "literature". Interesting read!!

louiskw 3y ago

https://github.com/BloopAI/bloop https://github.com/BloopAI/bloop Is fully open source and has full text + regex search built on tantivy fyi

nojvek 3y ago

You can do to_tsvector “plain” and keep the strings intact. No lemming, stemming. We use plain tsvectors on a gin index and change the queries to allow prefix based searching. So “wo he” matches “hello world”. Perhaps I should write a blog about it. Took me a few days to read PG documentation to get where we are at. The only thing it doesn’t handle is typo tolerance.

philippemnoel 3y ago
Tsvector is amazing and it goes a long way, but unfortunately as you say it lacks some of more complex FTS features like typo tolerance, language tokenizers, etc.

ectopasm83 3y ago

>Lemmatization: some search indexes are even fancy enough to substitute synonyms for more common words, so that you can search for “excellent” and get results for documents including “great.” This isn't what lemmatization is about. Stemming the word ‘Caring‘ would return ‘Car‘. Lemmatizing the word ‘Caring‘ would return ‘Care‘.

kermatt 3y ago

Are any of the tools mentioned in these comments better suited to searching SQL code, both DML and DDL? We maintain a tree of files with each object in a separate "CREATE TABLE|VIEW|PROCEDURE|FUNCTION" script. This supports code search with grep, but something that could find references to an object when the name qualifications are not uniform would be very useful: INSERT INTO table INSERT INTO schema.table INSERT INTO database.schema.table Can all be done with regex, but search is not so easy for programmers new to expressions.

ivanovm 3y ago

One of the most interesting approaches to code search I've seen recently (no affiliation) https://github.com/pyjarrett/septum https://github.com/pyjarrett/septum The hardest part about getting code search right imo is grabbing the right amount of surrounding context, which septum is aimed at solving on a per-file basis. Another one I'm surprised hasn't been mentioned is stack-graphs (https://github.com/github/stack-graphs https://github.com/github/stack-graphs), which tries to incrementally resolve symbolic relationships across the whole codebase. It powers github's cross-file precise indexing and conceptually makes a lot of sense, though I've struggled to get the open source version to work

hanwenn 3y ago

Hi, I wrote zoekt. From what I understand valtown does, I would try to use brute force first (ie. something equivalent to ripgrep). Once that starts breaking down, you could use last-updated-timestamps to reduce the brute force: * make a trigram index using Zoekt or Hound for JS snippets older than X * do brute force on snippets newer than X * advance X as you're indexing newer data. If the snippets are small, you can probably use a (trigram => snippets) index for space savings relative to a (trigram => offset) index.