-- reset marks if repeat_one tail doesn't match

   (this should fix Sjoerd's xmllib problem)
-- added skip field to INFO header
-- changed compiler to generate charset INFO header
-- changed trace messages to support post-mortem analysis

1 files changed, 153 insertions, 103 deletions

diff --git a/Lib/sre_compile.py b/Lib/sre_compile.py
index abd619e..97a57e2 100644
--- a/Lib/sre_compile.py
+++ b/Lib/sre_compile.py
@@ -14,72 +14,6 @@ from sre_constants import *
 
 MAXCODE = 65535
 
-def _charset(charset, fixup=None):
-    # internal: optimize character set
-    if not fixup:
-        fixup = lambda x: x
-    out = []
-    charmap = [0]*256
-    try:
-        for op, av in charset:
-            if op is NEGATE:
-                out.append((op, av))
-            elif op is LITERAL:
-                charmap[fixup(av)] = 1
-            elif op is RANGE:
-                for i in range(fixup(av[0]), fixup(av[1])+1):
-                    charmap[i] = 1
-            elif op is CATEGORY:
-                # FIXME: could append to charmap tail
-                return charset # cannot compress
-    except IndexError:
-        # unicode
-        return charset
-    # compress character map
-    i = p = n = 0
-    runs = []
-    for c in charmap:
-        if c:
-            if n == 0:
-                p = i
-            n = n + 1
-        elif n:
-            runs.append((p, n))
-            n = 0
-        i = i + 1
-    if n:
-        runs.append((p, n))
-    if len(runs) <= 2:
-        # use literal/range
-        for p, n in runs:
-            if n == 1:
-                out.append((LITERAL, p))
-            else:
-                out.append((RANGE, (p, p+n-1)))
-        if len(out) < len(charset):
-            return out
-    else:
-        # use bitmap
-        data = []
-        m = 1; v = 0
-        for c in charmap:
-            if c:
-                v = v + m
-            m = m << 1
-            if m > MAXCODE:
-                data.append(v)
-                m = 1; v = 0
-        out.append((CHARSET, data))
-        return out
-    return charset
-
-def _simple(av):
-    # check if av is a "simple" operator
-    lo, hi = av[2].getwidth()
-    if lo == 0:
-        raise error, "nothing to repeat"
-    return lo == hi == 1 and av[2][0][0] != SUBPATTERN
-
 def _compile(code, pattern, flags):
     # internal: compile a (sub)pattern
     emit = code.append
@@ -99,27 +33,7 @@ def _compile(code, pattern, flags):
                 emit(OPCODES[op])
                 fixup = lambda x: x
             skip = len(code); emit(0)
-            for op, av in _charset(av, fixup):
-                emit(OPCODES[op])
-                if op is NEGATE:
-                    pass
-                elif op is LITERAL:
-                    emit(fixup(av))
-                elif op is RANGE:
-                    emit(fixup(av[0]))
-                    emit(fixup(av[1]))
-                elif op is CHARSET:
-                    code.extend(av)
-                elif op is CATEGORY:
-                    if flags & SRE_FLAG_LOCALE:
-                        emit(CHCODES[CH_LOCALE[av]])
-                    elif flags & SRE_FLAG_UNICODE:
-                        emit(CHCODES[CH_UNICODE[av]])
-                    else:
-                        emit(CHCODES[av])
-                else:
-                    raise error, "internal: unsupported set operator"
-            emit(OPCODES[FAILURE])
+            _compile_charset(av, flags, code, fixup)
             code[skip] = len(code) - skip
         elif op is ANY:
             if flags & SRE_FLAG_DOTALL:
@@ -159,6 +73,7 @@ def _compile(code, pattern, flags):
             if av[0]:
                 emit(OPCODES[MARK])
                 emit((av[0]-1)*2)
+            # _compile_info(code, av[1], flags)
             _compile(code, av[1], flags)
             if av[0]:
                 emit(OPCODES[MARK])
@@ -195,6 +110,7 @@ def _compile(code, pattern, flags):
             tail = []
             for av in av[1]:
                 skip = len(code); emit(0)
+                # _compile_info(code, av, flags)
                 _compile(code, av, flags)
                 emit(OPCODES[JUMP])
                 tail.append(len(code)); emit(0)
@@ -219,6 +135,97 @@ def _compile(code, pattern, flags):
         else:
             raise ValueError, ("unsupported operand type", op)
 
+def _compile_charset(charset, flags, code, fixup=None):
+    # compile charset subprogram
+    emit = code.append
+    if not fixup:
+        fixup = lambda x: x
+    for op, av in _optimize_charset(charset, fixup):
+        emit(OPCODES[op])
+        if op is NEGATE:
+            pass
+        elif op is LITERAL:
+            emit(fixup(av))
+        elif op is RANGE:
+            emit(fixup(av[0]))
+            emit(fixup(av[1]))
+        elif op is CHARSET:
+            code.extend(av)
+        elif op is CATEGORY:
+            if flags & SRE_FLAG_LOCALE:
+                emit(CHCODES[CH_LOCALE[av]])
+            elif flags & SRE_FLAG_UNICODE:
+                emit(CHCODES[CH_UNICODE[av]])
+            else:
+                emit(CHCODES[av])
+        else:
+            raise error, "internal: unsupported set operator"
+    emit(OPCODES[FAILURE])
+
+def _optimize_charset(charset, fixup):
+    # internal: optimize character set
+    out = []
+    charmap = [0]*256
+    try:
+        for op, av in charset:
+            if op is NEGATE:
+                out.append((op, av))
+            elif op is LITERAL:
+                charmap[fixup(av)] = 1
+            elif op is RANGE:
+                for i in range(fixup(av[0]), fixup(av[1])+1):
+                    charmap[i] = 1
+            elif op is CATEGORY:
+                # FIXME: could append to charmap tail
+                return charset # cannot compress
+    except IndexError:
+        # character set contains unicode characters
+        return charset
+    # compress character map
+    i = p = n = 0
+    runs = []
+    for c in charmap:
+        if c:
+            if n == 0:
+                p = i
+            n = n + 1
+        elif n:
+            runs.append((p, n))
+            n = 0
+        i = i + 1
+    if n:
+        runs.append((p, n))
+    if len(runs) <= 2:
+        # use literal/range
+        for p, n in runs:
+            if n == 1:
+                out.append((LITERAL, p))
+            else:
+                out.append((RANGE, (p, p+n-1)))
+        if len(out) < len(charset):
+            return out
+    else:
+        # use bitmap
+        data = []
+        m = 1; v = 0
+        for c in charmap:
+            if c:
+                v = v + m
+            m = m << 1
+            if m > MAXCODE:
+                data.append(v)
+                m = 1; v = 0
+        out.append((CHARSET, data))
+        return out
+    return charset
+
+def _simple(av):
+    # check if av is a "simple" operator
+    lo, hi = av[2].getwidth()
+    if lo == 0:
+        raise error, "nothing to repeat"
+    return lo == hi == 1 and av[2][0][0] != SUBPATTERN
+
 def _compile_info(code, pattern, flags):
     # internal: compile an info block.  in the current version,
     # this contains min/max pattern width, and an optional literal
@@ -228,13 +235,60 @@ def _compile_info(code, pattern, flags):
         return # not worth it
     # look for a literal prefix
     prefix = []
+    prefix_skip = 0
     charset = [] # not used
     if not (flags & SRE_FLAG_IGNORECASE):
+        # look for literal prefix
         for op, av in pattern.data:
             if op is LITERAL:
+                if len(prefix) == prefix_skip:
+                    prefix_skip = prefix_skip + 1
                 prefix.append(av)
+            elif op is SUBPATTERN and len(av[1]) == 1:
+                op, av = av[1][0]
+                if op is LITERAL:
+                    prefix.append(av)
+                else:
+                    break
             else:
                 break
+        # if no prefix, look for charset prefix
+        if not prefix and pattern.data:
+            op, av = pattern.data[0]
+            if op is SUBPATTERN and av[1]:
+                op, av = av[1][0]
+                if op is LITERAL:
+                    charset.append((op, av))
+                elif op is BRANCH:
+                    c = []
+                    for p in av[1]:
+                        if not p:
+                            break
+                        op, av = p[0]
+                        if op is LITERAL:
+                            c.append((op, av))
+                        else:
+                            break
+                    else:
+                        charset = c
+            elif op is BRANCH:
+                c = []
+                for p in av[1]:
+                    if not p:
+                        break
+                    op, av = p[0]
+                    if op is LITERAL:
+                        c.append((op, av))
+                    else:
+                        break
+                else:
+                    charset = c
+            elif op is IN:
+                charset = av
+##     if prefix:
+##         print "*** PREFIX", prefix, prefix_skip
+##     if charset:
+##         print "*** CHARSET", charset
     # add an info block
     emit = code.append
     emit(OPCODES[INFO])
@@ -243,7 +297,7 @@ def _compile_info(code, pattern, flags):
     mask = 0
     if prefix:
         mask = SRE_INFO_PREFIX
-        if len(prefix) == len(pattern.data):
+        if len(prefix) == prefix_skip == len(pattern.data):
             mask = mask + SRE_INFO_LITERAL
     elif charset:
         mask = mask + SRE_INFO_CHARSET
@@ -260,22 +314,18 @@ def _compile_info(code, pattern, flags):
         emit(0)
     # add literal prefix
     if prefix:
-        emit(len(prefix))
-        if prefix:
-            code.extend(prefix)
-            # generate overlap table
-            table = [-1] + ([0]*len(prefix))
-            for i in range(len(prefix)):
-                table[i+1] = table[i]+1
-                while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]:
-                    table[i+1] = table[table[i+1]-1]+1
-            code.extend(table[1:]) # don't store first entry
+        emit(len(prefix)) # length
+        emit(prefix_skip) # skip
+        code.extend(prefix)
+        # generate overlap table
+        table = [-1] + ([0]*len(prefix))
+        for i in range(len(prefix)):
+            table[i+1] = table[i]+1
+            while table[i+1] > 0 and prefix[i] != prefix[table[i+1]-1]:
+                table[i+1] = table[table[i+1]-1]+1
+        code.extend(table[1:]) # don't store first entry
     elif charset:
-        # FIXME: use charset optimizer!
-        for char in charset:
-            emit(OPCODES[LITERAL])
-            emit(char)
-        emit(OPCODES[FAILURE])
+        _compile_charset(charset, 0, code)
     code[skip] = len(code) - skip
 
 STRING_TYPES = [type("")]