Four numbers for a regular expression

When Diomidis Spinellis and I wrote the FIRE/J paper (it came out in Software: Practice and Experience in 2008), we needed a way to say that one benchmark expression was harder than another. "Longer" is not an answer; [a-z] is five characters and abcde is five characters, and nobody would call them equally hard. So I wrote a small Java program that counted the operators in each expression and computed two of the complexity measures of Ehrenfeucht and Zeiger (Journal of Computer and System Sciences, 1976). The operator counts became the occurrence table in the paper, and the two measures lined the expressions up.

That program has been sitting on my disk ever since. This week it became a public repository, with all four measures this time, not just the two we used.

What the four numbers are

The definitions are recursive, and that is the nice part; you only need to say what happens for a single symbol, for union (E|F), for concatenation (EF) and for the star. Everything else follows.

• Size (N) is the number of alphabet symbols written in the expression.
• Star height (H) is how deep the unbounded repetition is nested. A star adds one, union and concatenation take the maximum.
• Length (L) is the longest path that does not go around a loop. Concatenation adds, union takes the longer branch.
• Width (W) is the dual of length; union adds, concatenation takes the wider part.

So [a-z] is a union of 26 symbols; size 26, length 1, width 26. And abcde is size 5, length 5, width 1. Same five characters, opposite shapes. Star height is the one people find surprising. (a*)(b*) has height 1, because the two stars sit side by side, while (a+)+ has height 2, because one contains the other (and yes, that is exactly the shape that gets backtracking engines into trouble, but more on that below).

A more realistic one, the usual "good enough" e-mail expression:

$ java -cp build org.fire.complexity.RegexComplexity -e '[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}'

Size 185, star height 1, length 5, width 67. The size is almost all character classes (67 + 64 + 52 symbols, plus the @ and the dot), the length is the five positions a match walks through, and the width is the widest class. It reads as a simple expression, and by three of the four numbers it is one.

The decisions

Definitions from 1976 do not know about Java's regular expression dialect, so a few choices had to be made, and they are written down in the README rather than hidden in the code.

A quantifier does not copy its body; a{10} has size 1 and length 1, because the symbol is written once. A complement ([^a], \D, \W) is taken over ASCII, so [^a] is 127. The dot is one symbol, not the 128 things it can match. And case flags do not multiply letters, so (?i)[a-z] stays 26. You can argue with every one of these (I did, with myself), but at least the argument is in the open. Anything the tool cannot give an honest number for, like \p{L} or \X, is rejected instead of being given a made-up size.

The old code did not parse the expression at all. It rewrote \d into [0-9] and friends by string substitution, and then counted brackets with a stack. It was written for one paper, and it worked for the expressions in that paper. The new one is a real parser, and its tests check every character class against java.util.regex itself; for each class it counts how many of the 128 ASCII characters Java's matcher accepts, and the size has to agree.

Before publishing it, I went over it once more against Java's own Pattern and found five more places where the two disagreed. An inline (?x) inside a group leaked out of it (Java ends the flag with the group), \h and \v were refused, [\Q...\E] was refused, a bare \0 was accepted, and a byte-order mark at the top of a file was counted as a symbol. All small, all fixed, each with a test. The dead preprocessor and an unused commons-cli jar went with them.

Epilogue

Two things the tool does not do, and I want to be clear about both. First, these are measures of the expression as written. Ehrenfeucht and Zeiger also define the complexity of a language, as the minimum over every expression that describes it, and finding that minimum is a different (and much harder) problem. Second, it is not a ReDoS detector. Star height 2 is a property of the expression; whether it hurts depends on the engine, and a DFA does not care at all.

What remains is the usual question with tools like this; who keeps up with the dialect? Java added \h, \R and \X long after the paper, and every one of them is a decision about what to count. For now the answer is me, and the tests that compare against Java will tell me when I am behind.

The code is at bkarak/regex-complexity, Apache 2.0 licensed, built with Ant and nothing else, and it has a page here now. It is small, and after eighteen years it finally reports all four :)