Re: Checking whether a string is a prefix of any string matching a given regular expression

Hmm, interesting problem.

1. I think you need to start with the assumption that the pattern is anchored at the start: /a/ might match "bbbbb..." as long as you throw an "a" in there at some point in the future, but /^a/ certainly cannot.

2. To get this directly out of the regexp engine you'd need to disable all its optimisations (and that's not something it is possible to do right now) - matching /^abcdef/ against "abc" will never read individual characters of the string, since an optimisation will see that the string is shorter than the minimum possible length before getting that far.

3. Defining what you want may become trickier with lookaheads: matching "abcd" =~ /^ab(?=.*foo)cd/ makes defining the "right" answer rather more difficult.

4. I think the definitions need some work in any case: "this is a substring of something that would match" will be difficult to know in general, and may be impossible in some cases. To offer a variant of crashtest's example: "ab" =~ /^abc(?<=d)/ is something that an unoptimised regexp engine might see as a prefix, even though no string actually matches the pattern.

Better, perhaps, would be to look for the longest prefix of the string that matches some prefix of the pattern. This might even be doable in perl5 - you'd need a function that takes a pattern and removes the last element, and then try a variety of prefixes of the string against each prefix of the pattern. Note that chomping /^\d{3}-\d{3}/ should give you /^\d{3}-\d{2}/, so it isn't entirely trivial, but as long as you're prepared to accept that the granularity might not always be perfect I think the code wouldn't be too bad even to cope with quite complex regular expresssions.

5. It is possible that at some point the perl5 regexp engine may become improved to the point that you can a) disable optimisations and b) provide some code for the "get next character in string" hook. This would allow you to achieve at least a variant of what you want with little pain, but I wouldn't hold your breath for the facilities.

6. It is likely this will be possible in perl6 before it is in perl5, since the perl6 authors have the benefit of starting from scratch with the lessons of perl5. You might want to get involved in that effort, at least enough to make clear what facilities you would want - but I think the facilities I suggest in (5) would be enough, and I'm pretty certain those are already planned.

Hugo

Comment on Re: Checking whether a string is a prefix of any string matching a given regular expression Select or Download Code

Replies are listed 'Best First'.
Re^2: Checking whether a string is a prefix of any string matching a given regular expression by dbrockman (Initiate) on Jul 01, 2005 at 16:13 UTC
Thank you for your insightful reply, Hugo. Regarding `/^a/` and `/a/`: I don’t see any problem with either. You can make errors when typing against the former, as you said, and my algorithm detects those errors. On the other hand, you can never make an error when typing against the latter, as you also said (and my algorithm will never report a false positive). I’m not very familiar with the implications of lookaheads, but your example of `"abcd" =~ /^ab(?=.*foo)cd/` seems rather unproblematic to me. The engine would go looking for “foo” and thereby bump into the end of string, which means that `"abcd"` cannot be ruled out as a potential prefix of some match of the given pattern (which is indeed correct, because it is a prefix of, e.g., `"abcdfoo"`). Can you think of a case in which the algorithm gives the wrong answer? Your next example is more interesting. I agree that applying the algorithm to `"ab" =~ /^abc(?<=d)/` would fail to establish that `"ab"` is not a prefix of any matching string. But this is an imaginary/academic problem, because the given regular expression would never occur in the real world except as an outright bug. I wonder if the problem can occur non-pathological cases (i.e., for regular expressions that can actually match things). Can you think of any example? I find intriguing the idea of iterating through the Cartesian product of input string prefixes and pattern prefixes (the latter of which will be non-trivial to generate, as you point out), and attempting to match each string–pattern pair. Though obviously inefficient, I think the fact that this is something you could implement without touching any C code makes it the most attractive solution so far. `:-)`	[reply] [d/l] [select]
Re^3: Checking whether a string is a prefix of any string matching a given regular expression by hv (Prior) on Jul 02, 2005 at 00:12 UTC
I’m not very familiar with the implications of lookaheads, but your example of `"abcd" =~ /^ab(?=.foo)cd/` seems rather unproblematic to me. The engine would go looking for “foo” and thereby bump into the end of string, which means that `"abcd"` cannot be ruled out as a potential prefix of some match of the given pattern (which is indeed correct, because it is a prefix of, e.g., `"abcdfoo"`). Can you think of a case in which the algorithm gives the wrong answer? Compare the results against `"abxy" =~ /^ab(?=.foo)cd/`. The Cartesian product approach will say for both cases that `"ab" =~ /^ab/` is the longest matching prefix, while checking what characters are looked at would claim the whole string is ok in both cases. Your next example is more interesting. I agree that applying the algorithm to `"ab" =~ /^abc(?<=d)/` would fail to establish that `"ab"` is not a prefix of any matching string. But this is an imaginary/academic problem, because the given regular expression would never occur in the real world except as an outright bug. I wonder if the problem can occur non-pathological cases (i.e., for regular expressions that can actually match things). Can you think of any example? Well unmatchable patterns could quite reasonably arise in some situations, particularly if they are themselves generated. But I think the likely real-world problems would occur with backreferences, of the `/^(something)other\1/` variety, but I can't think of a concrete example off the top of my head. Hugo	[reply] [d/l] [select]