pattern combinations

pattern_combinations.py

def group(pattern, left, right):
    open_parens = 0
    close_idx = 0
    if pattern[0] != left:
        raise Exception(f"Group has to start with: '{left}' in pattern: '{pattern}'")
    for (idx, char) in enumerate(pattern):
        if char == left:
            open_parens += 1
        elif char == right:
            open_parens -= 1
        if open_parens == 0:
            close_idx = idx
            break
        idx += 1
    if close_idx > 0:
        # successful group
        head = pattern[1:close_idx]
        tail = pattern[close_idx+1:]
    else:
        # too many left parens
        head = left
        tail = pattern[1:]
    return (head, tail)

def possible_patterns(pattern):
    def combine(heads, tails):
        if not heads:
            return tails
        elif not tails:
            return heads
        else:
            return [head + tail for head in heads for tail in tails]
    
    def fix_whitespace(pattern):
        return re.sub("\s+", " ", pattern.strip())

    def parse_choice_group(pattern):
        (head, tail) = group(pattern, "(", ")")
        idx = 0
        choice_idx = 0
        choices = []
        while idx < len(head):
            char = head[idx]
            if char == "(":
                idx += len(group(head[idx:], "(", ")")[0]) + 1
            elif char == "[":
                idx += len(group(head[idx:], "[", "]")[0]) + 1
            elif char == "|":
                choices.append(head[choice_idx:idx])
                choice_idx = idx + 1
            idx += 1
        choices.append(head[choice_idx:])
        heads = []
        for choice in choices:
            heads.extend(parse(choice))
        tails = parse(tail)
        return combine(heads, tails)
        
    def parse(pattern):
        patterns = []
        if pattern in ["[", "]", "(", ")"]:
            return [pattern]
        for (idx, char) in enumerate(pattern):
            if char == "(":
                choices = parse_choice_group(pattern[idx:])
                patterns = [pattern[:idx] + choice for choice in choices]
            elif char == "[":
                (head, tail) = group(pattern[idx:], "[", "]")
                heads = parse(head)
                tails = parse(tail)
                with_optional = [pattern[:idx] + tail for tail in combine(heads, tails)]
                without_optional = [pattern[:idx] + tail for tail in tails]
                patterns = [*with_optional, *without_optional]
            elif char == "¦":
                patterns = parse(pattern[idx+1:])
            if patterns:
                break

        if not patterns:
            patterns = [pattern]

        return patterns
    
    all_patterns = parse(pattern)
    return [fix_whitespace(pat) for pat in all_patterns]