2
\$\begingroup\$

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.)
\$\endgroup\$
3
  • \$\begingroup\$ "I don't care about the performance results at the moment"--just making sure you're aware of catastrophic backtracking, which can bring down a whole website--including the one you're on right now. I'm not sure offhand if adding | 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\$
    – ggorlen
    Commented Jun 6 at 16:56
  • \$\begingroup\$ @ggorlen Thanks for the comment. No, I am not aware of the CB behavior, and indeed I didn't consider it while implementing this function. I don't have any plans to use it in production so far, and this is why I'd like this code to be reviewed spotting what I might miss like the CB hint you provided and I'm really happy with that. The motivation for it is more for fun, but I'm really curious whether it might speed up the overall performance for regexp-based predicates when combined into a single regexp rather than testing n regexps until the first match. \$\endgroup\$ Commented Jun 6 at 17:38
  • 1
    \$\begingroup\$ Thanks, makes sense. Consider formatting with prettier.io/playground so your code style is standardized for JS. Also lint with eslint.org/play (your code passes lint though, congrats!). \$\endgroup\$
    – ggorlen
    Commented Jun 6 at 18:07

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
11
  • \$\begingroup\$ 1. Thanks for the review and your time! Regarding the specification section. I had to be more specific on the request and tell that it is more about the (too naive) algorithm the function builds a predicate for (just added the tag to the review request), and anything I might have missed in the regexp knowledge area. This is also why I omitted any documentation tags. \$\endgroup\$ Commented Jun 6 at 18:36
  • \$\begingroup\$ 2. Regarding the design by contract section. I would really love if JavaScript would support any in-language/standard assertions just like Java assert is (a keyword that can throw AssertionError if an assertion is violated in runtime if the JVM -ea flag is enabled). So this is also why I merely indicated the invariants as comments not even involving if statements that are not really assertions. \$\endgroup\$ Commented Jun 6 at 18:36
  • \$\begingroup\$ 3. Regarding the design of Public API section. I'm not really sure about removing the ...Predicate suffix from the name, but this suggestion makes me think that the function name is really not very clear, especially in context of the empty case. I guess it should return false because if there were no the 0- or 1- regexp specializations, the most "bold" predicate at the very bottom would merely return false right after the zero-iterations for the foo loop. (You also mentioned it as natural in the next section.) \$\endgroup\$ Commented Jun 6 at 18:37
  • \$\begingroup\$ 4.1 Regarding the premature optimization section. I believe that special cases can be and should easily handled if possible, not requiring the caller to be aware of the under the hood. Sure it also must be documented for any further maintainer and fully covered with unit tests. Another reason of why the special cases are handled right there is because I may expect the caller to use it for all cases of 0, 1 or 2+ regexps, not dealing with regexps directly in certain cases. \$\endgroup\$ Commented Jun 6 at 18:40
  • \$\begingroup\$ 4.2 For instance, consider a declarative DSL, that may accept custom-defined (but not user-defined) regexps, and its regexp-based function that is eventually based on testAnyRegExpPredicate optimizations as the caller is unable to handle special cases in DSL just by the DSL design (for example, something like ... foo MATCHES ANY (/rx1/ /rx2/) ... where the MATCHES ANY operand is a set of regexps syntactically, that also may be empty ()). I had to be more specific in the request since I really have one and didn't reveal it in the review request... \$\endgroup\$ Commented Jun 6 at 18:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.