Combining multiple regexps using the `|` operator and grouping the regexps by their flags

Question

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:

1. 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?
2. 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.)

Answer 1

This code does not yet have a strong design, nor would it easily be maintained by a team.

specification

Thank you for the Review Context, it is somewhat helpful. Certainly it is much, much better than nothing. It could go into ReadMe.md, but some or all of it should appear in the source code as /** JSDoc comments, so it doesn't get lost. Also, it should be tightened up, and written from the perspective of caller rather than implementor. Why would I want to call into this library routine? Answer that question and you have some good documentation.

Please write a single English sentence which explains what args your routine accepts and what it returns. Optionally follow it with a few sentences which expand on that, fleshing out defined terms and describing assumptions.

DbC

Twice you say, "// at this point, assume ...".

Both of those helper functions should simply assert that pre-condition is met, that we have an appropriate length.

Absent language support for an assert verb, conditionally throw a fatal exception, or (minimally) log an error to the console, explaining that caller did The Wrong Thing. Hopefully that will encourage repairs in the calling code.

design of Public API

Consider removing the ...Predicate suffix from the function name.

        // or am i wrong and this should return true?

It's up to you, you're designing this thing.

Look at what happens at typical call sites, and what caller would usually want for the empty case. The name testAny... is a little on the vague side. A name of grepAny... would suggest we are extracting matches, and would help to answer your "return true or false?" conundrum. A name of filterAny... would focus on discarding input lines, and might help you arrive at the opposite answer. Your call.

premature optimization

There are several early returns in testAnyRegExpPredicate(). They apparently are trying to save CPU cycles for the easy cases. Trouble is, this makes the function more complex, and makes it harder for a test suite to thoroughly exercise the logic. Please such tests, and measure their coverage.

The empty case is naturally handled by the function's final return false;.

The single input case and the single unique regex case are both naturally handled by the final for loop, albeit at the expense of calling the occasional helper. You did not reveal typical usage pattern nor timing measurements, so it's not clear that special casing these is a win. Special casing them definitely leads to a more complex function for maintainers to understand, and multiplies the need for additional unit tests. A caller that knows it is working with just a single regex could optimize by not calling into this routine at all.

assumptions vs measurements

assumption the smaller regexp flag is, the more efficient the regexp is

        // assume the first regExp is cheapest, do linear search

This codebase would benefit from greater clarity of thinking.

Assemble a text corpus of interest. When presented with several regexes, obtain benchmark timings for each one against the corpus. Sort them numerically, and then you know the first one is cheapest, as long as caller's production corpus resembles your test corpus.

If you care about matching speed, you want to take a dependency on a library which turns a NFA into a DFA, rather than being at the mercy of backtracking. It's easy for caller to accidentally incur catastrophic backtracking overhead, and it isn't pretty.

---

review summary

I feel the single biggest thing missing in this submission was not some code aspect, but rather the context / documentation. I didn't understand the motivating use case, nor the input data nor the expected interactive performance. The OP suggested that performance matters, yet included zero timing measurements.

Recently OP has revealed that the corpus scanned by regexes won't be paragraphs or chapters of text, but rather (relatively brief) URLs. So given a hundred or a thousand alternative regex fragments, there's a good chance we'll spend more time figuring out which (a|b|c) alternative is the appropriate one than we will spend on processing a successful match. In other words, far more "nope, not this one, move on to next" negative results than positive results. I am assuming you have hundreds or thousands of such alternatives. With smaller numbers the elapsed time differences are unlikely to be significant.

right tool for the job

The regex is a powerful technique, and often an appropriate one. But there's more than one tool in the CS toolbox.

URLs, by design, have a great deal of structure. If we focus on a single site, we might have three broad tree branches along the lines of
^https://example.com/(register|search|purchase)(.*). Within e.g. reddit.com the various subreddit prefixes would matter. Even if we can't exploit structure within a site, for a multi-site analysis we can always rely on the URI spec to support this kind of breakdown:
^https://(a.com|b.net|c.org)/(.*)

If that is the dominant selection method for your use case, then don't use regexes. Create a hashmap with keys of {'a.com', 'b.net', 'c.org'}, with relevant regexes for the values. Now when we see a prefix of "https://c.org/", we don't need to ask some poor regex engine to make an inefficient scan across | alternatives. We can hash in \$O(1)\$ constant time to find a regex value which encodes our knowledge regarding the matching website. Note that you may want to downcase the key before probing the map.