regexopt.py 3.2 KB

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