Determining whether values can potentially match a regular expression, given more input

Question

I am currently writing an application in JavaScript where I'm matching input to regular expressions, but I also need to find a way how to match strings to parts of the regular expressions.

For example:

var invalid = "x",
    potentially = "g",
    valid = "ggg", 
    gReg = /^ggg$/;

gReg.test(invalid); //returns false (correct)
gReg.test(valid);   //returns true (correct)

Now I need to find a way to somehow determine that the value of the potentially variable doesn't exactly match the /^ggg$/ expression, BUT with more input, it potentially can!

So for example in this case, the potentially variable is g, but if two more g's are appended to it, it will match the regular expression /^ggg$/

But in the case of invalid, it can never match the /^ggg$/ expression, no matter how many characters you append to it.

---

So how can I determine if a string has or doesn't have potential to match a particular regular expression?

Answer 1

Try this:

var str = "abcdefgh";
var len = str.length;
var reg = "";
for(var i = str.length - 1; i > 0; i--)
{
  //replace '(' with '(?:' to make it non capturing.
  reg = '(' + str[i] + reg + ')?'; 
}
reg = "^" + str[0] + reg + "$";

var regex = new RegExp(reg);

Answer 2

Obviously the test function below isn't going to be exactly what you want ... hopefully it will give you an idea as to how to tackle the problem.

function test(reg,string){
   var r = reg.exec(string);
     if(r){
         if(r.pop()){
             return true;
         }
         return "potentially";
     }
     return false;
}

var invalid = "x",
    potentially = "a",
    potentially2 = "ab",
    valid = "abc", 
    gReg = /^a(b(c)?)?$/;

alert(test(gReg,invalid)); //returns false (correct)
alert(test(gReg,potentially));   //returns "potentially" (correct)
alert(test(gReg,potentially2));   //returns "potentially" (correct)
alert(test(gReg,valid));   //returns true (correct)

Answer 3

function have_potential(input, valid) {
    if ( (new RegExp('^' + valid + '$')).test(input) ) return false;
    if ( (new RegExp(input)).test( valid ) ) return true;
    return false;
}

var valid = 'aaa|bbb';

console.log( have_potential('a',valid) )
// true
console.log( have_potential('c',valid) )
// false
console.log( have_potential('aaa',valid) )
// false

Edit: shorten version

function have_potential(input, valid) {
    return ( (new RegExp(input)).test( valid ) && !(new RegExp('^' + valid + '$')).test(input) );
}

Edit2: indexOf would be better in first place. function requires flat string inputs and "valid" may contain a list separated by "|"

function have_potential(input, valid) {
    return ( valid.indexOf(input) !== -1 && !(new RegExp('^' + valid + '$')).test(input) );
}

Answer 4

There is no general solution. If the regexp is a simple string, like the one in the example (in which case there is no point in using a regexp at all), you can use simple string comparision:

var invalid = "x",
potentially = "g",
valid = "ggg";
var gReg = "ggg";

function test(t, s) {
  if (t === s) return true;
  if (t.indexOf(s) === 0) return "potentially";
  return false;
}

test(gReg, invalid);     // false
test(gReg, potentially); // "potentially"
test(gReg, valid);       // true

Otherwise you can manually construct another regexp which accepts every prefix of every string gReg accepts. You will have to use ()? a lot.

Answer 5

How about you simply "reverse" your thinking on this, and turn the "potential" into a regex, testing in the other direction, eg

var invalid = "x",
    potentially = "g",
    valid = "ggg", 
    validReg = new RegExp("^"+valid+"$"),
    invalidReg = new RegExp(invalid),
    potentialReg = new RegExp(potentially);

//test actual matches
validReg.test(invalid); //returns false (correct)
validReg.test(valid);   //returns true (correct)

//test potential matches
potentialReg.test(valid); //returns true
invalidReg.test(valid);   //returns false