Re:Doug McIlroy's C++ regular expression matching library
by mehrdadn on Tuesday July 31, 2018 @09:01AM
(#17652776)
Yeah, the fact that it's hard is partly why I haven't implemented a working one one myself. :-)
Regarding streaming: I don't remember exactly when I ran into this, but a text or hex editor which you also mentioned for the other use case is a clear example (e.g. if I want to search for a pattern on my disk). I would have to think back to what the actual use case I ran into myself was; it may have been this or something else... it was quite a while ago.
> Is the trie data structure containing all of the file paths in memory?
Well obviously not in network example (the network aspect would be moot) but there are also times when this is the case. Thanks for linking to your library! I haven't learned Rust yet but I'll take a look at it.
With that said, yes, there are definitely specific use cases in which the operations you describe are indeed critical. A common one I've seen is in the development of a text editor, which probably does not store the file it's editing in a single contiguous block of memory, but still wants a way to search it with a regex.
Supporting the streaming use case is something I'd like to work on. I don't know if I'll succeed, but I've documented my thoughts here: https://github.com/rust-lang/regex/issues/425 --- If you'd like to elaborate and go more in depth about the specific use cases you have, I'd love to have that data, since it would be quite useful! (I am particularly interested in supporting streaming matching. Suffix extraction and more flexible automaton construction are also interesting to me. Working on non-string data is probably outside my scope. That's too hard to bake into a general purpose regex engine.)
> Requirements 1-3 are extremely important when you have a trie-like data structure that is expensive to traverse (like, say, file paths on a network folder, or even a local disk sometimes) -- you don't want to expand nodes or traverse edges needlessly.
I'm trying to unpack this... Is the trie data structure containing all of the file paths in memory? If so, it should be possible to build a finite automaton from a regex and then "simply" intersect it with your trie (which is, of course, itself also a finite state automaton). This is, for example, what my fst library does: https://docs.rs/fst/0.3.0/fst/#example-case-insensitive-sear...