aho-corasick VS nushell

You can't build the contiguous variant directly from a sequence of patterns. You need some kind of intermediate data structure to incrementally build a trie in memory. The contiguous NFA needs to know the complete picture of each state in order to compress it into memory. It makes decisions like, "if the number of transitions of this state is less than N, then use this representation" or "use the most significant N bits of the state pointer to indicate its representation." It is difficult to do this in an online fashion, and likely impossible to do without some sort of compromise. For example, you don't know how many transitions each state has until you've completed construction of the trie. But how do you build the trie if the state representation needs to know the number of transitions?

Note that the conversion from a non-contiguous NFA to a contiguous NFA is, relatively speaking, pretty cheap. The only real reason to not use a contiguous NFA is that it can't represent as many patterns as a non-contiguous NFA. (Because of the compression tricks it uses.)

The interesting bits start here: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

Right. I pointed it out because it isn't just about having portable SIMD that makes SIMD optimizations possible. Therefore, the lack of one in Rust doesn't have much explanatory power for why Rust's standard library doesn't contain SIMD. (It does have some.) It's good enough for things like memchr (well, kinda, NEON doesn't have `movemask`[1,2]), but not for things like Teddy that do multi-substring search. When you do want to write SIMD across platforms, it's not too hard to define your own bespoke portable API[3].

I'm basically just pointing out that a portable API is somewhat oversold, because it's not uncommon to need to abandon it, especially for string related ops that make creative use of ISA extensions. And additionally, that Rust unfortunately has other reasons for why std doesn't make as much use of SIMD as it probably should (the core/alloc/std split).

[1]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...

[2]: https://github.com/BurntSushi/memchr/blob/c6b885b870b6f1b9bf...

[3]: https://github.com/BurntSushi/aho-corasick/blob/f227162f7c56...

Oh I see. Yes, that's what is commonly used in academic publications. But I've yet to see it used in the wild.

I mentioned exactly that paper (I believe) in my write-up on Teddy: https://github.com/BurntSushi/aho-corasick/tree/master/src/p...

The byte offset (or equivalently in this case, the UTF-8 code unit offset) is almost certainly what you want. See: https://github.com/BurntSushi/aho-corasick/issues/72

This is an implementation of the algorithm in Rust as well if someone is curious. Though this code is written for production and not teaching.

A similar fix for the aho-corasick Rust crate was made in response

Teddy is a SIMD accelerated multiple substring matching algorithm. There's a nice description of Teddy here: https://github.com/BurntSushi/aho-corasick/tree/f9d633f970bb...

It's used in the aho-corasick and regex crates. It now supports SIMD acceleration on aarch64 (including Apple's M1 and M2). There are some nice benchmarks included in the PR demonstrating 2-10x speedups for some searches!

Even putting aside all of that, it might be really hard to add some of the improvements ripgrep has to their engine. The single substring search is probably the lowest hanging fruit, because you can probably isolate that code path pretty well. The multi-substring search is next, but the algorithm is very complicated and not formally described anywhere. The best description of it, Teddy, is probably my own. (I did not invent it.)

The first method is through downloading the pre-built binaries. With this method, you don't need to install anything other than Nushell's dependencies. Once you've downloaded the binaries, add them to your system's environment path to run it directly in your terminal.

I rather nushell for this purpose, it's more fun to write and easier to read.

https://www.nushell.sh/

These are just three small examples of what this shell written in Rust allows. The features are many and many more, but I'll leave it up to you to discover and enjoy them; I'm currently playing around with it and it's giving me a lot of satisfaction and immediacy, now it has a fixed place among the tools I use when working! The project is Open Source, so if you want to contribute, I invite you, as always, to do so, I leave you the link to the repo here!

Any thoughts on fish as compared to nushell [0]? It's similar to PowerShell in its philosophy and is also written in Rust.

[0] https://github.com/nushell/nushell

> In PowerShell, structured output is the default and it seems to work very well.

PowerShell goes a step beyond JSON, by supporting actual mutable objects. So instead of just passing through structured data, you effectively pass around opaque objects that allow you to go back to earlier pipeline stages, and invoke methods, if I understand correctly: https://learn.microsoft.com/en-us/powershell/module/microsof....

I'm rather fond of wrappers like jc and libxo, and experimental shells like https://www.nushell.sh/. These still focus on passing data, not objects with executable methods. On some level, I find this comfortable: Structured data still feels pretty Unix-like, if that makes sense? If I want actual objects, then it's probably time to fire up Python or Ruby.

Knowing when to switch from a shell script to a full-fledged programming language is important, even if your shell is basically awesome and has good programming features.

Maybe if the "popular" shells, but http://www.nushell.sh/ is looking better and better

Yeah agreed, especially now that PowerShell is available cross-platform.

Nushell[1] also seems like a promising alternative, but I haven’t had a chance to play with it yet.

[1]: https://www.nushell.sh/

I also discovered an existing discussion[1] related to this topic which includes a link[2] to a "helper to call nushell nuon/json/yaml commands from bash/fish/zsh" and a comment[3] that the current nushell dev focus is "on getting the experience inside nushell right and [we] probably won't be able to dedicate design time to get the interface of native Nu commands with an outside POSIX shell right and stable.".

[0] https://gitlab.com/RancidBacon/notes_public/-/blob/main/note...

[1] "Expose some commands to external world #6554": https://github.com/nushell/nushell/issues/6554

[2] https://github.com/cruel-intentions/devshell-files/blob/mast...

[3] https://github.com/nushell/nushell/issues/6554#issuecomment-...