critbit VS semantic-source

> Good use-case: routing. Say you have a list of 1 million IPs that are [deny listed].

Apparently, bloom filters make for lousy IP membership checks, read: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/

CritBit Trie [0] and possibly Allotment Routing Table (ART) are better suited for IPs.

[0] https://github.com/agl/critbit

[1] https://web.archive.org/web/20210720162224/https://www.harig...

developer here

I'd imagine the app should work over IPv6-only networks thanks to 464xlat. I may be wrong, because I've never tested it on a IPv6-only network.

The reason for IPv6 is two fold:

1. Firewall today simply stores classless IP address rules as strings in a sqlite table fronted by a lfu cache backed by a typical hash-map. With IPv6, I'd imagine, this won't scale. So, we need a more economical in-memory data-structure (like a crit-bit trie [0] or art tree).

2. Apparently LwIP has problems with HappyEyeballs (I personally never saw it, but got a couple of reports from users about it that it was an unrecoverable error once the connectivity was lost, and the firewall had to be restarted). We're in the process of replacing LwIP with gvisor/netstack now [2], just to get IPv6 support back on track.

[0] https://github.com/agl/critbit

[1] http://www.hariguchi.org/art/art.pdf

[2] https://github.com/celzero/firestack/issues/3

One production example I know: GitHub code navigation is written in Haskell https://github.com/github/semantic

ah, easy. it's because support has not been added into https://github.com/github/semantic which is the tech that powers the GitHub UI. Adding support is pretty easy/mainly glue code [1] that imports the tree sitter API.

[1] https://github.com/github/semantic/blob/793a876ae45d38a6bd17...

GitHub used Haskell for implementing Semantic, a command-line tool for parsing, analyzing, and comparing source code.

As far as engineering effort, you can read this GitHub comment for an overview of where we’d like to take the project in the future. The tl;dr here is that the open sum type view of the world made it very concise to fold over syntax trees (since such a view of data is ultimately unityped, recursion schemes Just Work), but the tradeoff thus associated—namely, that you have to parse a concrete syntax tree into an open-sum view (a complicated and painful-to-read process), that you can never really be sure how a given syntax tree is shaped, and that the types don’t help you nearly as much as they could—proved to be too onerous to deal with. Going forward, we’re generating syntax types from the AST once per target language, and working on an abstraction (probably via this generated code; I made five separate efforts at using Generics for this, and failed every time) that recovers at least some of the convenience of recursion schemes. It turns out that recursion schemes over a mutually recursive syntax tree—as pretty much every language’s syntax trees are, in practice—are pretty much an unsolved problem, especially when extended to languages like TypeScript, which have hundreds of different syntax nodes.

Meanwhile their Tree-Sitter-based semantic parser[1] looks abandoned. There is even rotting for years pull request[2] adding support of the same stack graphs into it.

[1] https://github.com/github/semantic

[2] https://github.com/github/semantic/pull/535

The semantic team at GitHub uses it for statically analyzing the dozens of languages that end up in GitHub repositories: https://github.com/github/semantic/blob/eaf13783838861fe5eb6cd46d59354774a8eb88d/docs/why-haskell.md

Yesterday I was looking for some examples of projects using tree-sitter (which is C) when I found GitHub's semantic, used to analyze and compare source code, and written in Haskell: https://github.com/github/semantic/