[1]: https://blog.burntsushi.net/unwrap/#what-about-when-invarian...

And do... what when the check fails? Can you please write the code for it? Because I don't understand what the heck you mean here. If you don't know Rust, pseudo code is fine.

> Long term: plug-in a richer type (logic) system, so one can safely prove the most costly runtime invariants at compile time.

This is just copying what I already said in the blog post. Until someone can show me how to prove the correctness of arbitrary DFA construction and search from a user provided regular expression pattern and demonstrate its use in a practical programming language like Rust, I consider this a total non-answer, not a "long term" answer.

Basically, your answer here confirms for me that your views on how code should be structured are incoherent.

    fn is_match(&self, haystack: &[u8]) -> Result<bool, Error> { ... }

So it looks like I already provided a rewrite of the code for you in your preferred style:

    // Returns true if the DFA matches the entire 'haystack'.
    // This routine always returns either Ok(true) or Ok(false) for all inputs.
    // It never returns an error unless there is a bug in its implementation.
    fn is_match(&self, haystack: &[u8]) -> Result<bool, &'static str> {
      let mut state_id = self.start_id;
      for &byte in haystack {
        let row = match state_id.checked_mul(256) {
          None => return Err("state id too big"),
          Some(row) => row,
        };
        let row_offset = match row.checked_add(usize::from(byte)) {
          None => return Err("row index too big"),
          Some(row_offset) => row_offset,
        };
        state_id = match self.transitions.get(row_offset) {
          None => return Err("invalid transition"),
          Some(&state_id) => state_id,
        };
        match self.is_match_id.get(state_id) {
          None => return Err("invalid state id"),
          Some(&true) => return Ok(true),
          Some(&false) => {}
        }
      }
      Ok(false)
    }

You can't even document the error conditions in a way that is related to the input of the routine, because if you could, you would have discovered a bug!

Another nail in the coffin of your preferred style is that this will absolutely trash the performance of a DFA search loop.

"this will absolutely trash the performance of a DFA search loop."

Do you happen to have some hard data to quantify? I'm curious.

Writeup from the contributor: https://nnethercote.github.io/2022/02/25/how-to-speed-up-the...

> The Decoder trait used for metadata decoding was fallible, using Result throughout. But decoding failures should only happen if something highly unexpected happens (e.g. metadata is corrupted) and on failure the calling code would just abort. This PR changed Decoder to be infallible throughout—panicking immediately instead of panicking slightly later—thus avoiding lots of pointless Result propagation, for wins across many benchmarks of up to 2%.

    fn find_fwd_imp<A: Automaton + ?Sized>(
        dfa: &A,
        input: &Input<'_, '_>,
        pre: Option<&'_ dyn Prefilter>,
        earliest: bool,
    ) -> Result<Option<HalfMatch>, MatchError> {
        let mut mat = None;
        let mut sid = init_fwd(dfa, input)?;
        let mut at = input.start();
        while at < input.end() {
            let byte = match input.haystack().get(at) {
                None => return Err(MatchError::GaveUp { offset: at }),
                Some(&byte) => byte,
            };
            sid = dfa.try_next_state(sid, byte)?;
            if dfa.is_special_state(sid) {
                if dfa.is_match_state(sid) {
                    let pattern = dfa.match_pattern(sid, 0);
                    mat = Some(HalfMatch::new(pattern, at));
                } else if dfa.is_dead_state(sid) {
                    return Ok(mat);
                }
            }
            at = match at.checked_add(1) {
                None => return Err(MatchError::GaveUp { offset: at }),
                Some(at) => at,
            };
        }
        eoi_fwd(dfa, input, &mut sid, &mut mat)?;
        Ok(mat)
    }

    $ regex-cli count matches dfa dense @$medium '\w{42}'
                parse time:  45.331µs
            translate time:  28.767µs
          compile nfa time:  9.577558ms
                nfa memory:  698148
    compile dense dfa time:  516.497476ms
          dense dfa memory:  6562848
     dense alphabet length:  113
              dense stride:  128
               search time:  531.808124ms
                    counts:  [2]

    fn find_fwd_imp<A: Automaton + ?Sized>(
        dfa: &A,
        input: &Input<'_, '_>,
        pre: Option<&'_ dyn Prefilter>,
        earliest: bool,
    ) -> Result<Option<HalfMatch>, MatchError> {
        let mut mat = None;
        let mut sid = init_fwd(dfa, input)?;
        let mut at = input.start();
        while at < input.end() {
            sid = dfa.next_state(sid, input.haystack()[at]);
            if dfa.is_special_state(sid) {
                if dfa.is_match_state(sid) {
                    let pattern = dfa.match_pattern(sid, 0);
                    mat = Some(HalfMatch::new(pattern, at));
                } else if dfa.is_dead_state(sid) {
                    return Ok(mat);
                }
            }
            at += 1;
        }
        eoi_fwd(dfa, input, &mut sid, &mut mat)?;
        Ok(mat)
    }

    $ regex-cli count matches dfa dense @$medium '\w{42}'
                parse time:  33.701µs
            translate time:  24.264µs
          compile nfa time:  9.55935ms
                nfa memory:  698148
    compile dense dfa time:  550.959698ms
          dense dfa memory:  6562848
     dense alphabet length:  113
              dense stride:  128
               search time:  468.932568ms
                    counts:  [2]

    fn find_fwd_imp<A: Automaton + ?Sized>(
        dfa: &A,
        input: &Input<'_, '_>,
        pre: Option<&'_ dyn Prefilter>,
        earliest: bool,
    ) -> Result<Option<HalfMatch>, MatchError> {
        let mut mat = None;
        let mut sid = init_fwd(dfa, input)?;
        let mut at = input.start();
        while at < input.end() {
            sid = unsafe {
                let byte = *input.haystack().get_unchecked(at);
                dfa.next_state_unchecked(sid, byte)
            };
            if dfa.is_special_state(sid) {
                if dfa.is_match_state(sid) {
                    let pattern = dfa.match_pattern(sid, 0);
                    mat = Some(HalfMatch::new(pattern, at));
                } else if dfa.is_dead_state(sid) {
                    return Ok(mat);
                }
            }
            at += 1;
        }
        eoi_fwd(dfa, input, &mut sid, &mut mat)?;
        Ok(mat)
    }

    $ regex-cli count matches dfa dense @$medium '\w{42}'
                parse time:  22.511µs
            translate time:  26.843µs
          compile nfa time:  8.709352ms
                nfa memory:  698148
    compile dense dfa time:  565.365005ms
          dense dfa memory:  6562848
     dense alphabet length:  113
              dense stride:  128
               search time:  456.402963ms
                    counts:  [2]

I bet if me and you sat down with a big codebase side-by-side, I could convince you that the style you're proposing is totally unworkable.

Now, whether it's worth it to use unsafe and elide bounds checks is harder. The gain I showed here is small, but it can be bigger in other examples. It depends. But it is certainly less clear. It helps that this is probanly the easiest kind of unsafe to justify, because you just have to make sure the index is in bounds. Other types of unsafe can be quite tricky to justify.

But to your original point, its true that a multiplexing server should probably try to stay up even if there is a bug uncovered in handling a request. But that's precisely why rust allows you to catch panics.

https://doc.rust-lang.org/std/panic/fn.catch_unwind.html

Edit. Re. already existing runtime checks, I'd expect a decent compiler to optimize away redundant checks, i.e. explicitly coded checks vs. checks injected automatically by the compiler, as long as their semantics is identical.

> The Result type is more appropriate to use for *functions that can fail on a regular basis.*

Emphasis mine. The DFA::is_match routine can never fail on any input. Yet, you want to use a 'Result' with it.

Seriously. Please please pretty please read the blog post. You are literally caught in precisely the tangled mess that I tried to untangle in the post. If my post didn't do it for you, then please consider responding to specific points you disagree with in the post.

Edit. For technical geeking around:

* The point is about redundant check elimination, not full check elimination. A decent compiler should be able to eliminate redundant checks, though perhaps the language could offer some intrinsics (was: pragmas) to make this 100% reliable.

* For DFA proofs, perhaps something like https://courses.grainger.illinois.edu/cs373/fa2013/Lectures/... could be a start. A great intern may tackle it over a summer ;)

If you mean "return an error instead," then bzzt again. Read the next section down.

Panic practically everywhere is just not an admissible option, most definitely not for anything that tries to call itself a systems language. Proving that there is no reasonable alternative would be equivalent to claiming the language is unusable.

> and sheer code execution performance is never the bottleneck in a realistic-sized system.

TIL that code execution perf doesn't matter and I've wasted almost a decade of my life focusing on it. Wow I wish you told me sooner!

What a ridiculous comment.

Ironically, that's exactly how you seem when just drop the "Turing completeness" bomb on a discussion about error handling. It's very hard not to see it as a ridiculously childish tantrum, since not only there's no actual argument, it is by definition impossible for it to be relevant to the discussion.

Anyway, I would not be writing this if it wasn't because you keep pumping direct personal attacks to everyone who dares counter your posts, which are already in a terrible tone.

Or, the obvious alternative that I was trying to point out: your analysis is wrong, and therefore, assuming the language is not useless, there must be a proper alternative to "panics everywhere" * that you are not accounting for !

https://lkml.org/lkml/2021/4/14/1099

* This is just to explicitly write the phrase again before it is (again) twisted as calling for a strict prohibition of all non-terminating conditions or some other childish nonsense.

Even unwinding panics (which are exceptions in all but name) can be an alternative, and Rust does support them.

That lkml post has zero relevance here. He's asking for fallible allocations. Which is totally reasonable.

Serious question: did you read the entire blog? If so, can you specifically point out passages you disagree with and why?

EDIT: And seriously, I started out this conversation with a serious comment asking you to elaborate on what you meant by asking something very concrete: how would you change the code example in my blog to conform to your view? You decided to flippantly respond with a non-answer in the first place. Why not go back to the original question I asked and give a real answer? If you don't know Rust, then use pseudo code. We're talking about a dozen lines here. It shouldn't take long.