4 ms·

Can this be used for non-string lists? I always found it frustrating that we have this amazing machinery for searching and modifying lists of characters, but as

Can this be used for non-string lists? I always found it frustrating that we have this amazing machinery for searching and modifying lists of characters, but as soon as I have a list of numbers or dates it all goes out of the window. Let's say I have a list of login attempt dates, and I want all sequences of 5+ failed login attempts followed by a success. With a regex it's trivial, but I can't use that; I have to roll my own loop, flags, and temporary lists. Sure, I could convert my list to a string, process it, and (try to) convert it back, but the downsides are obvious. Even if the performance is not as good as string-based regex, why shouldn't we have regexes for arbitrary list types? --- Edit: I realized this is not the first time I had this idea, and found an old Python prototype: https://github.com/boppreh/listregex https://github.com/boppreh/listregex It's horribly slow, but as an API experiment I'm quite happy. It also gives some tools not available to regexes, like inverting and intersect patterns, and matched pairs.

saagarjha 3y ago
You're going to have to define some sort of API for matching on a sliding window of values. This isn't impossible, but most languages don't really have great interfaces for it.
- BoppreH 3y ago
  Parser combinators[1] seem perfectly suited for this. # A sequence of 5 or more failed login attempts followed by a successful one. obj_regex.search(repeat(is_failed, min=5)+is_success, my_list) [1]: https://en.wikipedia.org/wiki/Parser_combinator https://en.wikipedia.org/wiki/Parser_combinator
burntsushi 3y ago
Nope. The regex library is tightly coupled with searching strings. That's an intentional design decision. Making a regex engine like this have a generic alphabet is a total non-starter. It's impractically difficult for me to do. Especially the API design and doing it in a way that doesn't impact the perf of the primary use case. The kind of regex engine you want, especially one where you don't care about perf, is not hard to build. You could take the `regex-lite` crate I published, for example, and code it up to be as generic as you want. In so doing, I expect you'll run into a number of interesting challenges. Anyway, it's not like these things don't exist. They do. People attempt to build them[1]. They just usually don't gain much traction because I suspect you're overstating their general utility. :-) [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html https://docs.rs/automata/latest/automata/trait.Alphabet.html
- schuyler2d 3y ago
  That said it would be a really cool feature to have some of the more complicated but common regexes (urls, emails, dates) be some kind of "template" in the syntax. Eg what if I could do '(?D<h=22>)' or something like that to search for all dates in any format that had some version of 8pm represented. Anyway, super appreciate your work and your writing!
  - burntsushi 3y ago
    It's an interesting idea, but I think it would be worth trying to actually prototype it as its own library first and see if it catches on. My suspicion is that it probably won't work as nicely as you think it will unfortunately.
- IshKebab 3y ago
  I've also been looking for the same thing for something like SystemVerilog Assertions (SVA) which is very regex-like, so it isn't just him!
  - burntsushi 3y ago
    Indeed. I've been responding to questions like this for a long time. :-) https://old.reddit.com/r/rust/comments/4a8pbv/the_regex_crate_now_supports_matching_on_u8/d0z0oom/ https://old.reddit.com/r/rust/comments/4a8pbv/the_regex_crat... Someone should go out and built it. It won't be me though, that's for sure. Believe it or not, such a library wouldn't leverage much of my experience. The vast majority of the complexity inside the regex crate is about optimizing for sequences of bytes.
    - IshKebab 3y ago
      Yeah I am slowly working on it. I think even custom alphabets wouldn't work for me. I'm trying to build something so this works: let is_even = |x: &i32| *x % 2 == 0; let is_odd = |x: &i32| *x % 2 == 0; let pattern = sequence(&[ is_even, is_odd, repeat(or(is_even, is_odd), 2, 4), ]); let mut matcher = Matcher::compile(pattern); let elements = [4, 1, 23, 5, 6]; for element in elements { matcher.step(element); } assert!(matcher.matches()); I'll get there one day. Amazing work on the Regex crate by the way!
kccqzy 3y ago
The C++ standard library std::basic_regex attempts to do this by exposing a templated class over a custom character type. https://en.cppreference.com/w/cpp/regex/basic_regex https://en.cppreference.com/w/cpp/regex/basic_regex You can provide your own trait class to define things for your custom "characters". Unfortunately performance goes out of the window. And it's likely to work as well as storing arbitrary non-character things into a custom std::basic_string.
- kzrdude 3y ago
  basic_regex seems to be for characters and not arbitrary objects like was asked for, I think.

saagarjha 3y ago

You're going to have to define some sort of API for matching on a sliding window of values. This isn't impossible, but most languages don't really have great interfaces for it.

BoppreH 3y ago
Parser combinators[1] seem perfectly suited for this. # A sequence of 5 or more failed login attempts followed by a successful one. obj_regex.search(repeat(is_failed, min=5)+is_success, my_list) [1]: https://en.wikipedia.org/wiki/Parser_combinator https://en.wikipedia.org/wiki/Parser_combinator

burntsushi 3y ago

Nope. The regex library is tightly coupled with searching strings. That's an intentional design decision. Making a regex engine like this have a generic alphabet is a total non-starter. It's impractically difficult for me to do. Especially the API design and doing it in a way that doesn't impact the perf of the primary use case. The kind of regex engine you want, especially one where you don't care about perf, is not hard to build. You could take the `regex-lite` crate I published, for example, and code it up to be as generic as you want. In so doing, I expect you'll run into a number of interesting challenges. Anyway, it's not like these things don't exist. They do. People attempt to build them[1]. They just usually don't gain much traction because I suspect you're overstating their general utility. :-) [1]: https://docs.rs/automata/latest/automata/trait.Alphabet.html https://docs.rs/automata/latest/automata/trait.Alphabet.html

schuyler2d 3y ago
That said it would be a really cool feature to have some of the more complicated but common regexes (urls, emails, dates) be some kind of "template" in the syntax. Eg what if I could do '(?D<h=22>)' or something like that to search for all dates in any format that had some version of 8pm represented. Anyway, super appreciate your work and your writing!
- burntsushi 3y ago
  It's an interesting idea, but I think it would be worth trying to actually prototype it as its own library first and see if it catches on. My suspicion is that it probably won't work as nicely as you think it will unfortunately.
IshKebab 3y ago
I've also been looking for the same thing for something like SystemVerilog Assertions (SVA) which is very regex-like, so it isn't just him!
- burntsushi 3y ago
  Indeed. I've been responding to questions like this for a long time. :-) https://old.reddit.com/r/rust/comments/4a8pbv/the_regex_crate_now_supports_matching_on_u8/d0z0oom/ https://old.reddit.com/r/rust/comments/4a8pbv/the_regex_crat... Someone should go out and built it. It won't be me though, that's for sure. Believe it or not, such a library wouldn't leverage much of my experience. The vast majority of the complexity inside the regex crate is about optimizing for sequences of bytes.
  - IshKebab 3y ago
    Yeah I am slowly working on it. I think even custom alphabets wouldn't work for me. I'm trying to build something so this works: let is_even = |x: &i32| *x % 2 == 0; let is_odd = |x: &i32| *x % 2 == 0; let pattern = sequence(&[ is_even, is_odd, repeat(or(is_even, is_odd), 2, 4), ]); let mut matcher = Matcher::compile(pattern); let elements = [4, 1, 23, 5, 6]; for element in elements { matcher.step(element); } assert!(matcher.matches()); I'll get there one day. Amazing work on the Regex crate by the way!

kccqzy 3y ago

The C++ standard library std::basic_regex attempts to do this by exposing a templated class over a custom character type. https://en.cppreference.com/w/cpp/regex/basic_regex https://en.cppreference.com/w/cpp/regex/basic_regex You can provide your own trait class to define things for your custom "characters". Unfortunately performance goes out of the window. And it's likely to work as well as storing arbitrary non-character things into a custom std::basic_string.

kzrdude 3y ago
basic_regex seems to be for characters and not arbitrary objects like was asked for, I think.