5 ms·

ripgrep is based on re2, a c library I would guess it contains more c than rust code... But what I love about this article is its lack of hype. It makes clear

ripgrep is based on re2, a c library I would guess it contains more c than rust code... But what I love about this article is its lack of hype. It makes clear arguments both ways and all of them I can get behind Hype doesn't help Edit: To all my downvoters; I anticipated you :) With love and best wishes

burntsushi 6y ago
No it's not. Its regex library is written in Rust, but was inspired by RE2. It shares no code with RE2. (And RE2 is a C++ library, not C.) Off the top of my head, the only C code in ripgrep is optional integration with PCRE2. In addition to whatever libc is being used on POSIX platforms. Everything else is pure Rust.
- tsegratis 6y ago
  Ah, thanks burntsushi, I believe you are the ripgrep author even? Great work btw. Ripgrep is the best ... I will have to restrict my comment to just LLVM being a larger, c++, dependency ... Just angling for more downvotes ;) Thanks for the reply
  - burntsushi 6y ago
    To be clear, ripgrep has no runtime dependency on any LLVM or C++ library. rustc does.
    - tsegratis 6y ago
      The interesting thing here is that rust has good threading and fantastic crates I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed This requires a cycle catching gc, or, just a preallocated arena... It was my first foray into rust and felt I would need to be hitting into unsafe, which I wasn't ready for. Array indexing might decompose into an arena, but syntactically just a bit messier (imho) Would be interesting to see how the RE2 does it in rust (didn't know that) I like how the article shows both sides of the fence, it makes me realize: I get a lot of optimizations from ptr stuffing in c. But sometimes we should lay down the good, for the better
      - burntsushi 6y ago
        You're overcomplicating it. When it comes to finite state machines at least, it's very easy to use an ID index instead of the raw pointer itself. That's exactly what the regex crate does. For reference, I am also the author of the regex crate. The only unsafe it uses specific to finite automata is to do explicit elimination of bounds checks in the core hybrid NFA/DFA loop.
        rstuart4133 6y ago
        > When it comes to finite state machines at least, it's very easy to use an ID index instead of the raw pointer itself. As an old C programmer, the difference between an array index and a pointer caught me by surprise. In C a pointer is just an unchecked offset into memory. A real array index is just a unchecked offset into ... maybe a smaller chunk of raw memory. But in rust, an array index is something that comes with additional bounds checking overheads with every use. And the memory it points to is also constrained - the entire array has to be initialised, so if the index passes the bounds check you are guaranteed rusts memory consistency invariants are preserved. Indexes also allow you to escape the borrow checker. If you own the slice, there is no need to prove you can access an element of the slice. So yeah, you can use indexes instead of pointers, but for rust that's like saying you can use recursion instead of iteration. Indexing and pointers are two very different things in rust.
        burntsushi 6y ago
        I guess so. But note that I didn't equate them. I just said that you can use an ID index instead. For the particular program of FSMs, they work very well. If bounds checks prove to be a problem, you can explicitly elide them. Indeed, Rust's regex does just that. :-)
      - eru 6y ago
        > I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed You could instead go with a derivatives approach. https://en.wikipedia.org/wiki/Brzozowski_derivative https://en.wikipedia.org/wiki/Brzozowski_derivative
- eru 6y ago
  It couldn't figure it out from looking through ripgrep's website: does ripgrep support intersection and complement of expressions? Like eg https://github.com/google/redgrep https://github.com/google/redgrep does. Regular languages are closed under those operations after all.
  - burntsushi 6y ago
    No, it doesn't. It's only theoretically easy to implement. In practice, they explode the size of the underlying FSM. Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining. Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk https://www.youtube.com/watch?v=Ukqb6nMjFyk ripgrep's regex syntax is the same as Rust's regex crate: https://docs.rs/regex/1.4.4/regex/#syntax https://docs.rs/regex/1.4.4/regex/#syntax (Which is in turn similar to RE2, although it supports a bit more niceties.)
    - eru 6y ago
      > No, it doesn't. It's only theoretically easy to implement. Oh, I didn't say anything about easy! I am on and off working on a Haskell re-implementation (but with GADTs and in Oleg's tagless final interpreter style etc, so it's more about exploring the type system). > In practice, they explode the size of the underlying FSM. You may be right, but that's still better than the gymnastics you'd have to do by hand to get the same features out of a 'normal' regex. > Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining. Alas, that only works, if your intersection or complement happen at the top level. You can't do something like (A & not B) followed by (C & D) that way. > Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk https://www.youtube.com/watch?v=Ukqb6nMjFyk I have, and I agree! Perhaps I'll try and implement a basic version of redgrep in Rust as an exercise. (I just want something that supports basically all the operations regular languages are closed, but don't care too much about speed, as long as the runtime complexity is linear.)
      - 6y ago
mplanchard 6y ago
I don’t think people are downvoting you because they disagree on a matter of opinion. You’ve literally got the author of ripgrep having replied to you to tell you that what you’ve said is categorically false.
- tsegratis 6y ago
  I anticipated my own falsity. I'm aware and at home with it
  - eru 6y ago
    Huh? Why do you say something that you anticipate to be false?
    - tsegratis 6y ago
      Simply bervity I anticipated I could well be wrong. I ALSO anticipated it would be a hard statement for people to take I think it was a reasonable statement -- I can't research everything I say, and I had read re2 and regexes in rust to be the same Interesting to read about redgrep and derivatives approach. Currently I'm programming a language that adds turing completeness to PEG expressions -- as in functions, but extended so the lhs is like a PEG -- just as function body can call sub functions, so too can the lhs I'm hoping this will give a simple unified language -- Philosophically: We make mistakes. If we can't handle that, then either we don't speak or program; or we deny it, program in c, then have flamewars and real wars Or thirdly, we accept it, program in rust, and let others correct us We can say you are my rustc compiler. So in effect I used a rust philosophy..... While programming in c
      - tsegratis 6y ago
        In one word: Jesus
      - mplanchard 6y ago
        I guess the thing is that if we’re not sure whether or not what we’re saying is true, it can be considerate to phrase it that way, e.g. “I think ripgrep’s regex library is written in C” rather than stating it as a fact. While it is particularly likely that folks on this website will correct mistaken statements, stating them as fact seems more likely to potentially spread misinformation. But anyways, cheers and good luck with your programming language!
carols10cents 6y ago
Why would you guess about how much C or Rust code that ripgrep contains when you could very quickly look? https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep
- ben0x539 6y ago
  Hm, how do I go from the github repo to a language breakdown of the dependency tree?
  - deleted 6y ago
    [deleted]

burntsushi 6y ago

No it's not. Its regex library is written in Rust, but was inspired by RE2. It shares no code with RE2. (And RE2 is a C++ library, not C.) Off the top of my head, the only C code in ripgrep is optional integration with PCRE2. In addition to whatever libc is being used on POSIX platforms. Everything else is pure Rust.

tsegratis 6y ago
Ah, thanks burntsushi, I believe you are the ripgrep author even? Great work btw. Ripgrep is the best ... I will have to restrict my comment to just LLVM being a larger, c++, dependency ... Just angling for more downvotes ;) Thanks for the reply
- burntsushi 6y ago
  To be clear, ripgrep has no runtime dependency on any LLVM or C++ library. rustc does.
  - tsegratis 6y ago
    The interesting thing here is that rust has good threading and fantastic crates I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed This requires a cycle catching gc, or, just a preallocated arena... It was my first foray into rust and felt I would need to be hitting into unsafe, which I wasn't ready for. Array indexing might decompose into an arena, but syntactically just a bit messier (imho) Would be interesting to see how the RE2 does it in rust (didn't know that) I like how the article shows both sides of the fence, it makes me realize: I get a lot of optimizations from ptr stuffing in c. But sometimes we should lay down the good, for the better
    - burntsushi 6y ago
      You're overcomplicating it. When it comes to finite state machines at least, it's very easy to use an ID index instead of the raw pointer itself. That's exactly what the regex crate does. For reference, I am also the author of the regex crate. The only unsafe it uses specific to finite automata is to do explicit elimination of bounds checks in the core hybrid NFA/DFA loop.
      - rstuart4133 6y ago
        > When it comes to finite state machines at least, it's very easy to use an ID index instead of the raw pointer itself. As an old C programmer, the difference between an array index and a pointer caught me by surprise. In C a pointer is just an unchecked offset into memory. A real array index is just a unchecked offset into ... maybe a smaller chunk of raw memory. But in rust, an array index is something that comes with additional bounds checking overheads with every use. And the memory it points to is also constrained - the entire array has to be initialised, so if the index passes the bounds check you are guaranteed rusts memory consistency invariants are preserved. Indexes also allow you to escape the borrow checker. If you own the slice, there is no need to prove you can access an element of the slice. So yeah, you can use indexes instead of pointers, but for rust that's like saying you can use recursion instead of iteration. Indexing and pointers are two very different things in rust.
        burntsushi 6y ago
        I guess so. But note that I didn't equate them. I just said that you can use an ID index instead. For the particular program of FSMs, they work very well. If bounds checks prove to be a problem, you can explicitly elide them. Indeed, Rust's regex does just that. :-)
    - eru 6y ago
      > I played with making a regex library in rust. Which, as per RE2 design involves constructing graphs and glueing them together as the regex is traversed You could instead go with a derivatives approach. https://en.wikipedia.org/wiki/Brzozowski_derivative https://en.wikipedia.org/wiki/Brzozowski_derivative
eru 6y ago
It couldn't figure it out from looking through ripgrep's website: does ripgrep support intersection and complement of expressions? Like eg https://github.com/google/redgrep https://github.com/google/redgrep does. Regular languages are closed under those operations after all.
- burntsushi 6y ago
  No, it doesn't. It's only theoretically easy to implement. In practice, they explode the size of the underlying FSM. Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining. Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk https://www.youtube.com/watch?v=Ukqb6nMjFyk ripgrep's regex syntax is the same as Rust's regex crate: https://docs.rs/regex/1.4.4/regex/#syntax https://docs.rs/regex/1.4.4/regex/#syntax (Which is in turn similar to RE2, although it supports a bit more niceties.)
  - eru 6y ago
    > No, it doesn't. It's only theoretically easy to implement. Oh, I didn't say anything about easy! I am on and off working on a Haskell re-implementation (but with GADTs and in Oleg's tagless final interpreter style etc, so it's more about exploring the type system). > In practice, they explode the size of the underlying FSM. You may be right, but that's still better than the gymnastics you'd have to do by hand to get the same features out of a 'normal' regex. > Moreover, in a command line tool, it's somewhat easy to work around that through the `-v` switch and shell pipelining. Alas, that only works, if your intersection or complement happen at the top level. You can't do something like (A & not B) followed by (C & D) that way. > Paul's talk introduced redgrep is amazing by the way. Give it a watch if you haven't yet: https://www.youtube.com/watch?v=Ukqb6nMjFyk https://www.youtube.com/watch?v=Ukqb6nMjFyk I have, and I agree! Perhaps I'll try and implement a basic version of redgrep in Rust as an exercise. (I just want something that supports basically all the operations regular languages are closed, but don't care too much about speed, as long as the runtime complexity is linear.)
    - 6y ago

mplanchard 6y ago

I don’t think people are downvoting you because they disagree on a matter of opinion. You’ve literally got the author of ripgrep having replied to you to tell you that what you’ve said is categorically false.

tsegratis 6y ago
I anticipated my own falsity. I'm aware and at home with it
- eru 6y ago
  Huh? Why do you say something that you anticipate to be false?
  - tsegratis 6y ago
    Simply bervity I anticipated I could well be wrong. I ALSO anticipated it would be a hard statement for people to take I think it was a reasonable statement -- I can't research everything I say, and I had read re2 and regexes in rust to be the same Interesting to read about redgrep and derivatives approach. Currently I'm programming a language that adds turing completeness to PEG expressions -- as in functions, but extended so the lhs is like a PEG -- just as function body can call sub functions, so too can the lhs I'm hoping this will give a simple unified language -- Philosophically: We make mistakes. If we can't handle that, then either we don't speak or program; or we deny it, program in c, then have flamewars and real wars Or thirdly, we accept it, program in rust, and let others correct us We can say you are my rustc compiler. So in effect I used a rust philosophy..... While programming in c
    - tsegratis 6y ago
      In one word: Jesus
    - mplanchard 6y ago
      I guess the thing is that if we’re not sure whether or not what we’re saying is true, it can be considerate to phrase it that way, e.g. “I think ripgrep’s regex library is written in C” rather than stating it as a fact. While it is particularly likely that folks on this website will correct mistaken statements, stating them as fact seems more likely to potentially spread misinformation. But anyways, cheers and good luck with your programming language!

carols10cents 6y ago

Why would you guess about how much C or Rust code that ripgrep contains when you could very quickly look? https://github.com/BurntSushi/ripgrep https://github.com/BurntSushi/ripgrep

ben0x539 6y ago
Hm, how do I go from the github repo to a language breakdown of the dependency tree?
- deleted 6y ago
  [deleted]