I've implemented a function that creates a multiple regular expressions predicate. The idea behind the predicate is combining regular expressions using the disjunction operator |
that have the same flags set (I mean the g
flag, i
, etc). I don't care about the performance results at the moment currently assuming that the |
operator may cause the regular expressions to be optimized by the engine (of course, depending on the environment as well).
How it works in general:
- the predicate factory method accepts a list of regexps;
- if no predicates are given, the always false predicate is returned (or should it return the always true predicate?);
- if only one regexp is given, a single regexp predicate is immediately returned;
- then the regexps are checked for uniqueness (not in terms of semantics/effects, but literals only; for instance
/(?:)/
and/(?:)(?:)/
do the same (match any input), but their literals are different); - and if there is only one regexp found after the uniqueness check, a single regexp is immediately returned;
- if there are more than one unique regexps found, then the regexps are grouped by theirs flags in an intermediate multimap, then converted to a pair-like array (#0 is the flag, #1 is a
|
-combined regexp) to be sorted by flags length (no-proof assumption the smaller regexp flag is, the more efficient the regexp is), and then the predicate testing all ordered combined regular expressions is returned.
// at this point, assume the regExps array length is greater than or equal to 2
// TODO: replace this with something like `[...new Set(regExps, ...)]` once Set supports a compare fn
const __toUniqueRegExps = (regExps) => {
const isSeen = new Map();
for ( const regExp of regExps ) {
isSeen.set(regExp.toString(), regExp);
}
return Array.from(isSeen.values());
}
// at this point, assume the regExps array length is greater than or equal to 2
const __groupRegExpsByFlags = (regExps) => {
const groups = new Map();
for ( const regExp of regExps ) {
if ( !groups.has(regExp.flags) ) {
groups.set(regExp.flags, [regExp]);
} else {
groups.get(regExp.flags).push(regExp);
}
}
return groups;
}
const __orderCombinedRegExpsByFlags = (regExpsByFlags) => {
const combinedRegExps = [];
for ( const [flags, regExps] of regExpsByFlags.entries() ) {
const combinedRegExp = new RegExp(regExps.map(regExp => regExp.source).join("|"), flags);
combinedRegExps.push([flags, combinedRegExp]);
}
// let's just assume the fewer flags the regexp is declared with, the cheaper it is
combinedRegExps.sort((l, r) => l[0].length - r[0].length);
return combinedRegExps.map(e => e[1]);
};
const testAnyRegExpPredicate = (...regExps) => {
if ( regExps.length === 0 ) {
// no regexps, nothing to test against, therefore return false
// or am i wrong and this should return true?
return () => false;
}
if ( regExps.length === 1 ) {
const onlyRegExp = regExps[0];
return (s) => onlyRegExp.test(s);
}
const uniqueRegExps = __toUniqueRegExps(regExps);
if ( uniqueRegExps.length === 1 ) {
const onlyRegExp = uniqueRegExps[0];
return (s) => onlyRegExp.test(s);
}
const combinedRegExps = __orderCombinedRegExpsByFlags(__groupRegExpsByFlags(uniqueRegExps));
return (s) => {
// assume the first regExp is cheapest, do linear search
for ( const regExp of combinedRegExps ) {
if ( regExp.test(s) ) {
return true;
}
}
return false;
};
};
General use:
const p = testAnyRegExpPredicate(/rx1/g, /rx2/i, /rx3/g, ...);
// the `p` predicate now tests against the following regular expressions:
// - g: rx1|rx3
// - i: rx2
p(str1);
p(str2);
...
My questions are:
- How efficient combining multiple regular expressions using the short circuiting
|
operator is? Does it depend on the regular expressions engine heavily (I'm interested in web browsers though)? For instance, may it exceed some "performance threshold" or whatever by using longer strings? - How idiomatic the code above is? I mostly have the Java background. (Please ignore the naming style for double underscores: in this example I only want them to be visually different.)
|
can cause CB (probably not) but I would want to be certain before using this in production anywhere. What's your motivation/use case for this code? \$\endgroup\$