determine if regular expression only matches fixed-length strings

Question

Hi,

Is there a way of determining if the regular expression only matches fixed-length strings ? My idea would be to scan for *,+ and ? Then, some intelligent logic would be required to to look for {m,n} where m!=n. It is not necessary to take the | operator into account.
Small example: ^\d{4} is fixed-length; ^\d{4,5} or ^\d+ are variable-length

I am using PCRE.

Thanks.

Paul Praet

Answer 1

Well, you could make use of the fact that Python's regex engine only allows fixed-length regular expressions in lookbehind assertions:

import re
regexes = [r".x{2}(abc|def)", # fixed
           r"a|bc",           # variable/finite
           r"(.)\1",          # fixed
           r".{0,3}",         # variable/finite
           r".*"]             # variable/infinite

for regex in regexes:
    try:
        r = re.compile("(?<=" + regex + ")")
    except:
        print("Not fixed length: {}".format(regex))
    else:
        print("Fixed length: {}".format(regex))

will output

Fixed length: .x{2}(abc|def)
Not fixed length: a|bc
Fixed length: (.)\1
Not fixed length: .{0,3}
Not fixed length: .*

I'm assuming that the regex itself is valid.

Now, how does Python know whether the regex is fixed-length or not? Just read the source - in sre_parse.py, there is a method called getwidth() that returns a tuple consisting of the lowest and the highest possible length, and if these are not equal in a lookbehind assertion, re.compile() will raise an error. The getwidth() method walks through the regex recursively:

def getwidth(self):
    # determine the width (min, max) for this subpattern
    if self.width:
        return self.width
    lo = hi = 0
    UNITCODES = (ANY, RANGE, IN, LITERAL, NOT_LITERAL, CATEGORY)
    REPEATCODES = (MIN_REPEAT, MAX_REPEAT)
    for op, av in self.data:
        if op is BRANCH:
            i = sys.maxsize
            j = 0
            for av in av[1]:
                l, h = av.getwidth()
                i = min(i, l)
                j = max(j, h)
            lo = lo + i
            hi = hi + j
        elif op is CALL:
            i, j = av.getwidth()
            lo = lo + i
            hi = hi + j
        elif op is SUBPATTERN:
            i, j = av[1].getwidth()
            lo = lo + i
            hi = hi + j
        elif op in REPEATCODES:
            i, j = av[2].getwidth()
            lo = lo + int(i) * av[0]
            hi = hi + int(j) * av[1]
        elif op in UNITCODES:
            lo = lo + 1
            hi = hi + 1
        elif op == SUCCESS:
            break
    self.width = int(min(lo, sys.maxsize)), int(min(hi, sys.maxsize))
    return self.width

Answer 2

According to regular-expressions.info, the PCRE engine supports only fixed-length regexes and alternation inside lookbehinds.

So if you have a valid regex, surround it with (?<= and ) and see if it still compiles. Then you know that it's either fixed-size or an alternation of fixed-size regexes.

I'm not sure about something like a(b|cd)e - this is definitely not fixed-size, but it might still compile. You'd need to try it out (I don't have C/PCRE installed).

Answer 3

Just for fun.

Assuming the regex we are testing against only support +, *, ?, {m,n}, {n} and [...] (except some weird syntax like []] and [^]]). Then the regex is fixed length only if it follows the grammar:

 REGEX     -> ELEMENT *
 ELEMENT   -> CHARACTER ( '{' ( \d+ ) ( ',' \1 )? '}' )?
 CHARACTER -> [^+*?\\\[] | '\\' . | '[' ( '\\' . | [^\\\]] )+ ']'

which can be rewritten in PCRE as:

^(?:(?:[^+*?\\\[{]|\\.|\[(?:\\.|[^\\\]])+\])(?:\{(\d+)(?:,\1)?\})?)*$