• Tom Lane's avatar
    Improve memory-usage accounting in regular-expression compiler. · 538b3b8b
    Tom Lane authored
    This code previously counted the number of NFA states it created, and
    complained if a limit was exceeded, so as to prevent bizarre regex patterns
    from consuming unreasonable time or memory.  That's fine as far as it went,
    but the code paid no attention to how many arcs linked those states.  Since
    regexes can be contrived that have O(N) states but will need O(N^2) arcs
    after fixempties() processing, it was still possible to blow out memory,
    and take a long time doing it too.  To fix, modify the bookkeeping to count
    space used by both states and arcs.
    
    I did not bother with including the "color map" in the accounting; it
    can only grow to a few megabytes, which is not a lot in comparison to
    what we're allowing for states+arcs (about 150MB on 64-bit machines
    or half that on 32-bit machines).
    
    Looking at some of the larger real-world regexes captured in the Tcl
    regression test suite suggests that the most that is likely to be needed
    for regexes found in the wild is under 10MB, so I believe that the current
    limit has enough headroom to make it okay to keep it as a hard-wired limit.
    
    In connection with this, redefine REG_ETOOBIG as meaning "regular
    expression is too complex"; the previous wording of "nfa has too many
    states" was already somewhat inapropos because of the error code's use
    for stack depth overrun, and it was not very user-friendly either.
    
    Back-patch to all supported branches.
    538b3b8b
regcomp.c 54.6 KB