Furthermore without knowing the exact implementation, you can't specify how it works, because the appropriate boundary depends on the optimization chosen, which is highly implementation-dependent.

The point that you're ignoring is that to make the spec work, you need to decide internally where and when to switch strategies.

Yes - any version that implements the spec is correct. If your version doesn't implement the spec, it is incorrect. Any changes you need to make to your version to have it match the spec is internal to that version.

(BTW your refusing to call this switch an "optimization" is disingenuous at best.)

Why? You said that the "optimization" fixed bugs. To me, that's a bugfix. That it optimized the code is often a consequence of correct implementation.

Saying "this must work" and "that must be fast" says that you need 2 different strategies. It doesn't say where the boundary between them should be.

"This must work according to spec." is all I'm saying. The spec contains a speed requirement.

It doesn't say where the boundary between them should be. That boundary should be invisible to the user of your code. And therefore you have an internal code boundary that is not part of the external specification.

Does the code implement the spec? If yes, you may pass Go. If no, then go directly to Jail. If your version implements the spec and is faster than mine, that's wonderful. If it's faster, but it's wrong, then we're not comparing apples.

Furthermore without knowing the exact implementation, you can't specify how it works, because the appropriate boundary depends on the optimization chosen, which is highly implementation-dependent.

This sentence makes absolutely no sense to me. A specification tells you what it does. It most certainly doesn't say how it accomplishes that goal. And, yes, an optimization may certainly be platform-dependent, tools-dependent, etc. If your implementation wants to take those factors into account, it is welcome to do so. However, you're still implementing the spec, which, at the end of the day, is all that matters.

---

My criteria for good software:

1. Does it work?
2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Here is what you are missing.

In the example that I provided, there is a general case matching algorithm and a special case matching algorithm. To get correct behaviour for all kinds of regular expressions, you sometimes need to use the general algorithm. To get the specified speed for some common regular expressions, you sometimes else need to use the special case matching algorithm.

The public specification does not say where the boundary between the special case and the general case is. It is a basic fact of life that there is a good chance of finding bugs around that boundary.

What I am saying is that you'll find corner cases along that boundary which are nowhere visible or obvious in the specification, and it is a very good idea to have white-box tests for those corner cases.

In pseudo-code, your implementation will contains something that looks like this:

  if (some conditions here) {
    use special case with performance guarantees
  }
  else {
    use general case that may be slow
  }
[download]

You need white-box testing to be sure that you're testing that all regex features which can show up under both implementations are tested under them. If you just use black-box testing, then your tests that the construct x{3,5} works properly may only test one implementation and your tests won't notice if it fails in the other. This is exactly what happened in Perl 5.6.0.

I really hope that this explanation is enough for you to understand the issue. If it is not then I really don't know how I can say this more clearly.