Performance penalty: combinatorial explosion in `transform`

[DNikolaevAtRocket]

Description

Using docopt for building utilities with relatively wide range of options is pretty limited because of a huge performance penalty. Namely, a combinatorial explosion may happen in the transform function: the pattern expansion (like ((-a | -b) (-c | -d)) => (-a -c | -a -d | -b -c | -b -d)) has unacceptable computational complexity.

A good example would be the GNU ls utility. See the sample below.

To Reproduce

The script below takes almost 3 seconds to run which is terribly slow for just to parse CLI arguments.

"""
ls with a subset of GNU options (that's not even all of them!)

Usage:
    ls [-a|-A] [--hide=PATTERN] [-I=PATTERN] [-dLR]
       [--color] [-h|--si] [--indicator-style=WORD|-p|-F|--file-type]
       [--format=WORD|-x|-m|-x|-l|-1|-C|-g|-n|-o] [-Giks]
       [--sort=WORD|-f|-U|-S|-t|-v|-X] [--group-directories-first] [-r]
       [--time=WORD|-u|-c] [--time-style=TIME_STYLE]
       [FILES ...]
    ls --help
    ls --version

Arguments:
    FILES
        list of files
"""
from docopt import docopt

args = docopt()

[h4l]

I noticed this while digging around in the commit history just now for another issue I reported. This change was introduced in some refactoring by the original author after the last release of docopt (0.6.2): https://github.com/jazzband/docopt-ng/commit/ba4740e0e27aefe52d52ad29c6273223c1e12231

i.e. the original author never released this change, but it got picked up into docopt-ng as it was in docopt's master branch.

[NickCrews]

If anyone wants to tackle this, I will gladly review. Thanks for the bug report!

[ThosRTanner]

I don't think it's that commit that affects the performance. I've just undone that individual one and seen no difference in the time taken. (Although moving the definition of parent outside the function speeds it up from 2.6s to 2.5s roughly)