Algorithm to find out whether the matches for two Glob patterns (or Regular Expressions) intersect

Question

I'm looking at matching glob-style patterns similar the what the Redis KEYS command accepts. Quoting:

• h?llo matches hello, hallo and hxllo
• h*llo matches hllo and heeeello
• h[ae]llo matches hello and hallo, but not hillo

But I am not matching against a text string, but matching the pattern against another pattern with all operators being meaningful on both ends.

For example these patterns should match against each other in the same row:

prefix*       prefix:extended* *suffix       *:extended:suffix left*right    left*middle*right a*b*c         a*b*d*b*c hello*        *ok pre[ab]fix*   pre[bc]fix* 

And these should not match:

prefix*       wrong:prefix:* *suffix       *suffix:wrong left*right    right*middle*left pre[ab]fix*   pre[xy]fix* ?*b*?         bcb 

So I'm wondering ...

• if this is possible to do (implement a verification algorithm), if at all?
• if not possible, what subset of regex would be possible? (i.e. disallow * wildcard?)
• if it is indeed possible, what is an efficient algorithm?
• what are the time complexity required?

---

EDIT: Found this other question on RegEx subset but this is not exactly the same as the words that hello* and *ok matches is not a subset/superset of each other but they do intersect.

So I guess mathematically, this might be phrased as; is it possible to deterministically check that a set of words that one pattern match, intersecting with a set of words that another pattern matches, result in a non-empty set?

---

EDIT: A friend @neizod drew up this elimination table which neatly visualize what might be a potential/partial solution: Elimination rule

---

EDIT: Will adds extra bounty for those who can also provide working code (in any language) and test cases that proves it.

---

EDIT: Added the ?*b*? test case discovered by @DanielGimenez in the comments.

Answer 1

Now witness the firepower of this fully ARMED and OPERATIONAL battle station!

(I have worked too much on this answer and my brain has broken; There should be a badge for that.)

In order to determine if two patterns intersect, I have created a recursive backtracking parser -- when Kleene stars are encountered a new stack is created so that if it fails in the future everything is rolled back and and the star consumes the next character.

You can view the history of this answer to determine how arrived at all this and why it was necessary, but basically it wasn't sufficient to determine an intersection by looking ahead only one token, which was what I was doing before.

This was the case that broke the old answer [abcd]d => *d. The set matches the d after the star, so the left side would still have tokens remaining, while the right side would be complete. However, these patterns two intersect on ad, bd, cd and dd, so that needed to be fixed. My almost O(N) answer was thrown out.

Lexer

The lexing process is trivial, except that is processes escape characters and removes redundant stars. Tokens are broken out into sets, stars, wild character (?), and character. This is different than my previous versions where one token was a string of characters instead of a single character. As more cases come up, having strings as tokens was more of a hindrance than advantage.

Parser

Most of the functions of the parser are pretty trivial. A switch given the left side's type, calls a function that is a switch that determines the appropriate function to compare it with the right side's type. The result from the comparison bubbles up the two switches to the original callee, typically the main loop of the parser.

Parsing Stars

The simplicity ends with the star. When that is encountered it takes over everything. First it compares its side's next token with the other side's, advancing the other side until if finds a match.

Once the match is found, it then checks if everything matches all the way up to the end of both patterns. If it does then the patterns intersect. Otherwise, it advances the other side's next token from the original one it was compared against and repeats the process.

When two anys are encountered then the take off into their own alternative branches starting from each others' next token.

function intersects(left, right) {     var lt, rt,         result = new CompareResult(null, null, true);      lt = (!left || left instanceof Token) ? left : tokenize(left);     rt = (!right || right instanceof Token) ? right : tokenize(right);      while (result.isGood && (lt || rt)) {         result = tokensCompare(lt, rt);          lt = result.leftNext;         rt = result.rightNext;     }      return result; }  function tokensCompare(lt, rt) {     if (!lt && rt) return tokensCompare(rt, lt).swapTokens();      switch (lt.type) {         case TokenType.Char: return charCompare(lt, rt);         case TokenType.Single: return singleCompare(lt, rt);         case TokenType.Set: return setCompare(lt, rt);         case TokenType.AnyString: return anyCompare(lt, rt);     } }  function anyCompare(tAny, tOther) {     if (!tOther) return new CompareResult(tAny.next, null);      var result = CompareResult.BadResult;      while (tOther && !result.isGood) {         while (tOther && !result.isGood) {             switch (tOther.type) {                 case TokenType.Char: result = charCompare(tOther, tAny.next).swapTokens(); break;                 case TokenType.Single: result = singleCompare(tOther, tAny.next).swapTokens(); break;                 case TokenType.Set: result = setCompare(tOther, tAny.next).swapTokens(); break;                 case TokenType.AnyString:                     // the anyCompare from the intersects will take over the processing.                     result = intersects(tAny, tOther.next);                     if (result.isGood) return result;                     return intersects(tOther, tAny.next).swapTokens();             }              if (!result.isGood) tOther = tOther.next;         }          if (result.isGood) {             // we've found a starting point, but now we want to make sure this will always work.             result = intersects(result.leftNext, result.rightNext);             if (!result.isGood) tOther = tOther.next;         }     }      // If we never got a good result that means we've eaten everything.     if (!result.isGood) result = new CompareResult(tAny.next, null, true);      return result; }  function charCompare(tChar, tOther) {     if (!tOther) return CompareResult.BadResult;      switch (tOther.type) {         case TokenType.Char: return charCharCompare(tChar, tOther);          case TokenType.Single: return new CompareResult(tChar.next, tOther.next);         case TokenType.Set: return setCharCompare(tOther, tChar).swapTokens();          case TokenType.AnyString: return anyCompare(tOther, tChar).swapTokens();     } }  function singleCompare(tSingle, tOther) {     if (!tOther) return CompareResult.BadResult;      switch (tOther.type) {         case TokenType.Char: return new CompareResult(tSingle.next, tOther.next);         case TokenType.Single: return new CompareResult(tSingle.next, tOther.next);         case TokenType.Set: return new CompareResult(tSingle.next, tOther.next);         case TokenType.AnyString: return anyCompare(tOther, tSingle).swapTokens();     } } function setCompare(tSet, tOther) {     if (!tOther) return CompareResult.BadResult;      switch (tOther.type) {         case TokenType.Char: return setCharCompare(tSet, tOther);         case TokenType.Single: return new CompareResult(tSet.next, tOther.next);         case TokenType.Set: return setSetCompare(tSet, tOther);         case TokenType.AnyString: return anyCompare(tOther, tSet).swapTokens();     } }  function anySingleCompare(tAny, tSingle) {     var nextResult = (tAny.next) ? singleCompare(tSingle, tAny.next).swapTokens() :         new CompareResult(tAny, tSingle.next);     return (nextResult.isGood) ? nextResult: new CompareResult(tAny, tSingle.next); }  function anyCharCompare(tAny, tChar) {     var nextResult = (tAny.next) ? charCompare(tChar, tAny.next).swapTokens() :         new CompareResult(tAny, tChar.next);      return (nextResult.isGood) ? nextResult : new CompareResult(tAny, tChar.next); }  function charCharCompare(litA, litB) {     return (litA.val === litB.val) ?         new CompareResult(litA.next, litB.next) : CompareResult.BadResult; }  function setCharCompare(tSet, tChar) {     return (tSet.val.indexOf(tChar.val) > -1) ?         new CompareResult(tSet.next, tChar.next) : CompareResult.BadResult; }  function setSetCompare(tSetA, tSetB) {     var setA = tSetA.val,         setB = tSetB.val;      for (var i = 0, il = setA.length; i < il; i++) {         if (setB.indexOf(setA.charAt(i)) > -1) return new CompareResult(tSetA.next, tSetB.next);     }     return CompareResult.BadResult; } 

jsFiddle

Time Complexity

Anything with the words "recursive backtracking" in it is at least O(N²).

Maintainability and Readability

I purposely broke out any branches into there own functions with a singular switch. Assitionally I used named constants when a one character string would suffice. Doing this made the code longer and more verbose, but I think it makes it easier to follow.

Tests

You can view all the tests in the Fiddle. You can view the comments in the Fiddle output to glean their purposes. Each token type was tested against each token type, but I haven't made one that tried all possible comparisons in a single test. I also came up with a few random tough ones like the one below.

abc[def]?fghi?*nop*[tuv]uv[wxy]?yz => a?[cde]defg*?ilmn[opq]*tu*[xyz]*

I added an interface on the jsFiddle if anybody wants to test this out themselves. The logging is broken once I added the recursion.

I don't think I tried enough negative tests, especially with the last version I created.

Optimization

Currently the solution is a brute force one, but is sufficient to handle any case. I would like to come back to this at some point to improve the time complexity with some simple optimizations.

Checks at the start to reduce comparisons could increase processing time for certain common scenarios. For example, if one pattern starts with a star and one ends with one then we already know they will intersect. I can also check all the characters from the start and end of the patterns and remove them if the match on both patterns. This way they are excluded from any future recursion.

Acknowledgements

I used @m.buettner's tests initially to test my code before I came up with my own. Also I walked through his code to help me understand the problem better.

Answer 2

With your very reduced pattern language, the pastebin link in your question and jpmc26's comments are pretty much all the way there: the main question is, whether the literal left and right end of your input strings match. If they do, and both contain at least one *, the strings match (because you can always match the other strings intermediate literal text with that star). There is one special case: if only one of them is empty (after removing pre- and suffix), they can still match if the other consists entirely of *s.

Of course, when checking whether the ends of the string match, you need to take into account the single-character wildcard ? and character classes, too. The single-character wildcard is easy: it cannot fail, because it will always match whatever the other character is. If it's a character class, and the other is just a character, you need to check whether the character is in the class. If they are both classes, you need to check for an intersection of the classes (which is a simple set intersection).

Here is all of that in JavaScript (check out the code comments to see how the algorithm I outlined above maps to the code):

var trueInput = [     { left: 'prefix*', right: 'prefix:extended*' },     { left: '*suffix', right: '*:extended:suffix' },     { left: 'left*right', right: 'left*middle*right' },     { left: 'a*b*c', right: 'a*b*d*b*c' },     { left: 'hello*', right: '*ok' },     { left: '*', right: '*'},     { left: '*', right: '**'},     { left: '*', right: ''},     { left: '', right: ''},     { left: 'abc', right: 'a*c'},     { left: 'a*c', right: 'a*c'},     { left: 'a[bc]d', right: 'acd'},     { left: 'a[bc]d', right: 'a[ce]d'},     { left: 'a?d', right: 'acd'},     { left: 'a[bc]d*wyz', right: 'abd*w[xy]z'}, ];  var falseInput = [     { left: 'prefix*', right: 'wrong:prefix:*' },     { left: '*suffix', right: '*suffix:wrong' },     { left: 'left*right', right: 'right*middle*left' },     { left: 'abc', right: 'abcde'},     { left: 'abcde', right: 'abc'},     { left: 'a[bc]d', right: 'aed'},     { left: 'a[bc]d', right: 'a[fe]d'},     { left: 'a?e', right: 'acd'},     { left: 'a[bc]d*wyz', right: 'abc*w[ab]z'}, ];  // Expects either a single-character string (for literal strings // and single-character wildcards) or an array (for character // classes). var characterIntersect = function(a,b) {     // If one is a wildcard, there is an intersection.     if (a === '?' || b === '?')         return true;      // If both are characters, they must be the same.     if (typeof a === 'string' && typeof b === 'string')         return a === b;      // If one is a character class, we check that the other     // is contained in the class.     if (a instanceof Array && typeof b === 'string')         return (a.indexOf(b) > -1);     if (b instanceof Array && typeof a === 'string')         return (b.indexOf(a) > -1);      // Now both have to be arrays, so we need to check whether     // they intersect.     return a.filter(function(character) {         return (b.indexOf(character) > -1);     }).length > 0; };  var patternIntersect = function(a,b) {     // Turn the strings into character arrays because they are     // easier to deal with.     a = a.split("");     b = b.split("");      // Check the beginnings of the string (up until the first *     // in either of them).     while (a.length && b.length && a[0] !== '*' && b[0] !== '*')     {         // Remove the first character from each. If it's a [,         // extract an array of all characters in the class.         aChar = a.shift();         if (aChar == '[')         {             aChar = a.splice(0, a.indexOf(']'));             a.shift(); // remove the ]         }         bChar = b.shift();         if (bChar == '[')         {             bChar = b.splice(0, b.indexOf(']'));             b.shift(); // remove the ]         }          // Check if the two characters or classes overlap.         if (!characterIntersect(aChar, bChar))             return false;     }      // Same thing, but for the end of the string.     while (a.length && b.length && a[a.length-1] !== '*' && b[b.length-1] !== '*')     {         aChar = a.pop();         if (aChar == ']')         {             aChar = a.splice(a.indexOf('[')+1, Number.MAX_VALUE);             a.pop(); // remove the [         }         bChar = b.pop();         if (bChar == ']')         {             bChar = b.splice(b.indexOf('[')+1, Number.MAX_VALUE);             b.pop(); // remove the [         }          if (!characterIntersect(aChar, bChar))             return false;     }      // If one string is empty, the other has to be empty, too, or     // consist only of stars.     if (!a.length && /[^*]/.test(b.join('')) ||         !b.length && /[^*]/.test(b.join('')))         return false;      // The only case not covered above is that both strings contain     // a * in which case they certainly overlap.     return true; };  console.log('Should be all true:'); console.log(trueInput.map(function(pair) {     return patternIntersect(pair.left, pair.right); }));  console.log('Should be all false:'); console.log(falseInput.map(function(pair) {     return patternIntersect(pair.left, pair.right); })); 

It's not the neatest implementation, but it works and is (hopefully) still quite readable. There is a fair bit of code duplication with checking the beginning and the end (which could be alleviated with a simple reverse after checking the beginning - but I figured that would just obscure things). And there are probably tons of other bits that could be greatly improved, but I think the logic is all in place.

A few more remarks: the implementation assumes that the patterns are well-formatted (no unmatched opening or closing brackets). Also, I took the array intersection code from this answer because it's compact - you could certainly improve on the efficiency of that if necessary.

Regardless of those implementation details, I think I can answer your complexity question, too: the outer loop goes over both strings at the same time, a character at a time. So that's linear complexity. Everything inside the loop can be done in constant time, except the character class tests. If one character is a character class and the other isn't, you need linear time (with the size of the class being the parameter) to check whether the character is in the class. But this doesn't make it quadratic, because each character in the class means one less iteration of the outer loop. So that's still linear. The most costly thing is hence the intersection of two character classes. This might be more complex that linear time, but the worst it could get is O(N log N): after all, you could just sort both character classes, and then find an intersection in linear time. I think you might even be able to get overall linear time complexity, by hashing the characters in the character class to their Unicode code point (.charCodeAt(0) in JS) or some other number - and finding an intersection in a hashed set is possible in linear time. So, if you really want to, I think you should be able to get down to O(N).

And what is N? The upper limit is sum of the length of both patterns, but in most cases it will actually be less (depending on the length of prefixes and suffixes of both patterns).

Please point me to any edge-cases my algorithm is missing. I'm also happy about suggested improvements, if they improve or at least don't reduce the clarity of the code.

Here is a live demo on JSBin (thanks to chakrit for pasting it there).

---

EDIT: As Daniel pointed out, there is a conceptual edge-case that my algorithm misses out on. If (before or after elimination of the beginning and end) one string contains no * and the other does, there are cases, where the two still clash. Unfortunately, I don't have the time right now to adjust my code snippet to accommodate that problem, but I can outline how to resolve it.

After eliminating both ends of the strings, if both strings are either empty or both contain at least *, they will always match (go through the possible *-distributions after complete elimination to see this). The only case that's not trivial is if one string still contains *, but the other doesn't (be it empty or not). What we now need to do is walk both strings again from left to right. Let me call the string that contains * A and the one that doesn't contain * B.

We walk A from left to right, skipping all * (paying attention only to ?, character classes and literal characters). For each of the relevant tokens, we check from left to right, if it can be matched in B (stopping at the first occurrence) and advance our B-cursor to that position. If we ever find a token in A that cannot be found in B any more, they do not match. If we manage to find a match for each token in A, they do match. This way, we still use linear time, because there is no backtracking involved. Here are two examples. These two should match:

A: *a*[bc]*?*d* --- B: db?bdfdc     ^                    ^ A: *a*[bc]*?*d* --- B: db?bdfdc       ^                   ^ A: *a*[bc]*?*d* --- B: db?bdfdc            ^               ^ A: *a*[bc]*?*d* --- B: db?bdfdc              ^               ^ 

These two should not match:

A: *a*[bc]*?*d* --- B: dbabdfc     ^                    ^ A: *a*[bc]*?*d* --- B: dbabdfc       ^                   ^ A: *a*[bc]*?*d* --- B: dbabdfc            ^               ^ A: *a*[bc]*?*d* --- B: dbabdfc              !                

It fails, because the ? cannot possibly match before the second d, after which there is no further d in B to accommodate for the last d in A.

This would probably be easy to add to my current implementation, if I had taken the time to properly parse the string into token objects. But now, I'd have to go through the trouble of parsing those character classes again. I hope this written outline of the addition is sufficient help.

PS: Of course, my implementation does also not account for escaping metacharacters, and might choke on * inside character classes.