codekingpro/portable-devtools

1"""2    pygments.regexopt3    ~~~~~~~~~~~~~~~~~4 5    An algorithm that generates optimized regexes for matching long lists of6    literal strings.7 8    :copyright: Copyright 2006-present by the Pygments team, see AUTHORS.9    :license: BSD, see LICENSE for details.10"""11 12import re13from re import escape14from itertools import groupby15from operator import itemgetter16 17CS_ESCAPE = re.compile(r'[\[\^\\\-\]]')18FIRST_ELEMENT = itemgetter(0)19 20 21def commonprefix(m):22    """Given an iterable of strings, returns the longest common leading substring"""23    if not m:24        return ""25    s1 = min(m)26    s2 = max(m)27    for i, c in enumerate(s1):28        if c != s2[i]:29            return s1[:i]30    return s131 32 33def make_charset(letters):34    return '[' + CS_ESCAPE.sub(lambda m: '\\' + m.group(), ''.join(letters)) + ']'35 36 37def regex_opt_inner(strings, open_paren):38    """Return a regex that matches any string in the sorted list of strings."""39    close_paren = open_paren and ')' or ''40    # print strings, repr(open_paren)41    if not strings:42        # print '-> nothing left'43        return ''44    first = strings[0]45    if len(strings) == 1:46        # print '-> only 1 string'47        return open_paren + escape(first) + close_paren48    if not first:49        # print '-> first string empty'50        return open_paren + regex_opt_inner(strings[1:], '(?:') \51            + '?' + close_paren52    if len(first) == 1:53        # multiple one-char strings? make a charset54        oneletter = []55        rest = []56        for s in strings:57            if len(s) == 1:58                oneletter.append(s)59            else:60                rest.append(s)61        if len(oneletter) > 1:  # do we have more than one oneletter string?62            if rest:63                # print '-> 1-character + rest'64                return open_paren + regex_opt_inner(rest, '') + '|' \65                    + make_charset(oneletter) + close_paren66            # print '-> only 1-character'67            return open_paren + make_charset(oneletter) + close_paren68    prefix = commonprefix(strings)69    if prefix:70        plen = len(prefix)71        # we have a prefix for all strings72        # print '-> prefix:', prefix73        return open_paren + escape(prefix) \74            + regex_opt_inner([s[plen:] for s in strings], '(?:') \75            + close_paren76    # is there a suffix?77    strings_rev = [s[::-1] for s in strings]78    suffix = commonprefix(strings_rev)79    if suffix:80        slen = len(suffix)81        # print '-> suffix:', suffix[::-1]82        return open_paren \83            + regex_opt_inner(sorted(s[:-slen] for s in strings), '(?:') \84            + escape(suffix[::-1]) + close_paren85    # recurse on common 1-string prefixes86    # print '-> last resort'87    return open_paren + \88        '|'.join(regex_opt_inner(list(group[1]), '')89                 for group in groupby(strings, lambda s: s[0] == first[0])) \90        + close_paren91 92 93def regex_opt(strings, prefix='', suffix=''):94    """Return a compiled regex that matches any string in the given list.95 96    The strings to match must be literal strings, not regexes.  They will be97    regex-escaped.98 99    *prefix* and *suffix* are pre- and appended to the final regex.100    """101    strings = sorted(strings)102    return prefix + regex_opt_inner(strings, '(') + suffix103