Changeset 3201

Timestamp:

02/16/08 08:50:14 (10 months ago)

Author:

jascha

Message:

- optimized DFA generation
- took care of unreachable code warnings (#913)
- fixed problem with lookahead at start of expression
- brought D code generation up-to-date
- minor changes

Files:

• trunk/tango/text/Regex.d (modified) (69 diffs)

trunk/tango/text/Regex.d

@@ -11 +11 @@
-    This is a regular expression compiler and interpreter based on the Tagged NFA/DFA method.
-
-
+
+
+
+
-    as opposed to what "regular expression" means in most implementations
-    (e.g. PCRE or those from the standard libraries of Perl, Java or Python).
@@ -19 +22 @@
-    for details on the differences.
-
-
-
+
+
+
-
-    The syntax of a regular expressions is as follows.
@@ -466 +470 @@
-    }
-}
+
+/* ************************************************************************************************
+
+**************************************************************************************************/
+void quickSort(T)(T[] a)
+{
+    quickSort(a,cast(size_t)0,a.length);
+}
+
+void quickSort(T)(T[] a, size_t l, size_t r)
+{
+    T t;
+    auto i = r-l;
+    if ( i < 3 )
+    {
+        if ( i < 2 )
+            return;
+        if ( a[l] < a[l+1] )
+            return;
+        t = a[l];
+        a[l] = a[l+1];
+        a[l+1] = t;
+        return;
+    }
+    
+    auto p = a[l];
+    i = l;
+    auto j = r;
+    
+    while ( true )
+    {
+        ++i;
+        for ( ; i < j && a[i] < p; ++i ) {}
+        --j;
+        for ( ; i < j && a[j] >= p; --j ) {}
+        if ( i >= j )
+            break;
+        t = a[i];
+        a[i] = a[j];
+        a[j] = t;
+    }
+    --i;
+    a[l] = a[i];
+    a[i] = p;
+
+    quickSort(a, l, i);
+    quickSort(a, i+1, r);
+}
-import tango.math.Math;
-
@@ -473 +525 @@
-struct CharRange(char_t)
-{
-, r
+_, r_
-
-    static CharRange opCall(char_t c)
-    {
-
-r.l
-r.r
-
+c
+cr.l_
+cr.r_
+c
-    }
-
-    static CharRange opCall(char_t a, char_t b)
-    {
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    int opCmp(CharRange cr)
-    {
- == cr.l
+_ == cr.l_
-            return 0;
- < cr.l
+_ < cr.l_
-            return -1;
-        return 1;
@@ -502 +567 @@
-    bool contains(char_t c)
-    {
- && c <= r
+_ && c <= r_
-    }
-
-    bool contains(CharRange cr)
-    {
- <= cr.l && r >= cr.r
+_ <= cr.l_ && r_ >= cr.r_
-    }
-
-    bool intersects(CharRange cr)
-    {
- >= cr.l && l <= cr.r
+_ >= cr.l_ && l_ <= cr.r_
-    }
-
@@ -519 +584 @@
-        assert(intersects(cr));
-        CharRange ir;
-
-
+
+
+
+
-        return ir;
-    }
@@ -536 +603 @@
-            if ( contains(cr) )
-            {
- = l
- = cr.l
- <= d.r
+_ = l_
+_ = cr.l_
+_ <= d.r_
-                    sr ~= d;
- = cr.r
- = r
- <= d.r
+_ = cr.r_
+_ = r_
+_ <= d.r_
-                    sr ~= d;
-            }
- > l
-
- = cr.r
- = r
- <= d.r
+_ > l_
+
+_ = cr.r_
+_ = r_
+_ <= d.r_
-                    sr ~= d;
-            }
- < r
-
- = l
- = cr.l
- <= d.r
+_ < r_
+
+_ = l_
+_ = cr.l_
+_ <= d.r_
-                    sr ~= d;
-            }
@@ -567 +634 @@
-        string str;
-        auto layout = new Layout!(char);
- == r
-
- > 0x20 && l
-
+_ == r_
+
+_ > 0x20 && l_
+_
-            else
-
+_
-        }
-        else
-        {
- > 0x20 && l
-
+_ > 0x20 && l_
+_
-            else
-
+_
-            str ~= "-";
- > 0x20 && r
-
+_ > 0x20 && r_
+_
-            else
-
+_
-        }
-        return str;
@@ -601 +668 @@
-    static const CharClass!(char_t)
-        line_startend = {parts: [
-:0x00, r
-:0x0a, r
-:0x13, r
+_:0x00, r_
+_:0x0a, r_
+_:0x13, r_
-        ]},
-        digit = {parts: [
-:0x30, r
+_:0x30, r_
-        ]},
-        whitespace = {parts: [
-
-
-
-
-
-
-
+
+
+
+
+
+
-        ]};
-
@@ -623 +689 @@
-        static const CharClass!(char_t)
-            any_char = {parts: [
-
-
-
-
+
-            ]},
-            dot_oper = {parts: [
-:0x09, r
-:0x20, r
-:0xa0, r
+_:0x09, r_
+_:0x20, r_
+_:0xa0, r_
-            ]},
-            alphanum_ = {parts: [
-:0x30, r
-:0x41, r
-:0x5f, r
-:0x61, r
+_:0x30, r_
+_:0x41, r_
+_:0x5f, r_
+_:0x61, r_
-            ]};
-    }
@@ -645 +708 @@
-        static const CharClass!(char_t)
-            any_char = {parts: [
-
-
-
-
-
+
-            ]},
-            dot_oper = {parts: [
-:0x09,r:0x13},{l:0x20, r:0x7e},{l:0xa0, r
-:0x0100, r
-:0x0180, r
-:0x20a3, r
+_:0x09,r_:0x13},{l_:0x20, r_:0x7e},{l_:0xa0, r_
+_:0x0100, r_
+_:0x0180, r_
+_:0x20a3, r_
-            ]},
-            alphanum_ = {parts: [
-:0x30, r
-:0x41, r
-:0x5f, r
-:0x61, r
+_:0x30, r_
+_:0x41, r_
+_:0x5f, r_
+_:0x61, r_
-            ]};
-    }
@@ -667 +726 @@
-    //---------------------------------------------------------------------------------------------
-    range_t[] parts;
+
+    invariant()
+    {
+//        foreach ( i, p; parts )
+//            assert(p.l_<=p.r_, Int.toString(i)~": "~Int.toString(p.l_)~" > "~Int.toString(p.r_));
+    }
+
+    static CharClass opCall(CharClass cc)
+    {
+        CharClass ncc;
+        ncc.parts = cc.parts.dup;
+        return ncc;
+    }
-
-    int opCmp(CharClass cc)
@@ -676 +748 @@
-        foreach ( i, p; cc.parts )
-        {
- != parts[i].l || p.r != parts[i].r
+_ != parts[i].l_ || p.r_ != parts[i].r_
-                return 1;
-        }
@@ -708 +780 @@
-            }
-        }
-        ic.optimize;
-        return ic;
-    }
@@ -717 +788 @@
-        add(cc);
-        negate;
+    }
+
+    void add(CharClass cc)
+    {
+        parts ~= cc.parts;
+    }
+
+    void add(char_t c)
+    {
+        parts ~= CharRange!(char_t)(c);
+    }
+    
+    /* ********************************************************************************************
+        Requires the CharClass to be optimized.
+    **********************************************************************************************/
+    void negate()
+    {
-        optimize;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-            return;
-        }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-
@@ -771 +852 @@
-            return;
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-
@@ -799 +881 @@
-}
-
+import tango.io.Stdout;
+unittest
+{
+    Stdout.formatln("CharClass unittest");
+    static CharClass!(char) cc = { parts: [{l_:0,r_:10},{l_:0,r_:6},{l_:5,r_:12},{l_:12,r_:17},{l_:20,r_:100}] };
+    Stdout.formatln("{}", cc.toString);
+    cc.optimize;
+    Stdout.formatln("optimized: {}", cc.toString);
+    cc.negate;
+    Stdout.formatln("negated: {}", cc.toString);
+    cc.optimize;
+    Stdout.formatln("optimized: {}", cc.toString);
+    cc.negate;
+    Stdout.formatln("negated: {}", cc.toString);
+    
+    static CharClass!(char) cc2 = { parts: [] };
+    Stdout.formatln("{}", cc2.toString);
+    cc2.optimize;
+    Stdout.formatln("optimized: {}", cc2.toString);
+    cc2.negate;
+    Stdout.formatln("negated: {}", cc2.toString);
+    cc2.optimize;
+    Stdout.formatln("optimized: {}", cc2.toString);
+    cc2.negate;
+    Stdout.formatln("negated: {}", cc2.toString);
+    
+    static CharClass!(char) cc3 = { parts: [{l_:0,r_:100},{l_:200,r_:0xff},] };
+    Stdout.formatln("{}", cc3.toString);
+    cc3.negate;
+    Stdout.formatln("negated: {}", cc3.toString);
+    cc3.negate;
+    Stdout.formatln("negated: {}", cc3.toString);
+    
+    static CharClass!(char) cc4 = { parts: [{l_:0,r_:200},{l_:100,r_:0xff},] };
+    Stdout.formatln("{}", cc4.toString);
+    cc4.optimize;
+    Stdout.formatln("optimized: {}", cc4.toString);
+
+    static CharClass!(dchar) cc5 = { parts: [{l_:0x9,r_:0x13},{0x20,r_:'~'},{l_:0xa0,r_:0xff},{l_:0x100,r_:0x17f},{l_:0x180,r_:0x24f},{l_:0x20a3,r_:0x20b5}] };
+    Stdout.formatln("{}", cc5.toString);
+    cc5.optimize;
+    Stdout.formatln("optimized: {}", cc5.toString);
+    cc5.negate;
+    Stdout.formatln("negated: {}", cc5.toString);
+    cc5.optimize;
+    Stdout.formatln("optimized: {}", cc5.toString);
+    cc5.negate;
+    Stdout.formatln("negated: {}", cc5.toString);
+    assert(0, "control the results for yourself, i'm too lazy to type all those asserts ;)");
+}
+
-
-/* ************************************************************************************************
@@ -818 +951 @@
-
-    // data for compiled predicates
-*8
+
-                MAX_SEARCH_LENGTH = 256;
-    enum MatchMode {
@@ -839 +972 @@
-        
-        // single char?
- == input.parts[0].r
+_ == input.parts[0].r_
-        {
-            mode = type==Type.consume ? MatchMode.single_char : MatchMode.single_char_l;
-
+_
-            return;
-        }
-        
-        // check whether we can use a bitmap
-        foreach ( p; input.parts )
-        {
- > MAX_BITMAP_LENGTH || p.r
+_ > MAX_BITMAP_LENGTH || p.r_
-                goto LnoBitmap;
-        }
@@ -857 +989 @@
-        foreach ( p; input.parts )
-        {
-; c <= p.r
+_; c <= p.r_
-                data_bmp[c/8] |= 1 << (c&7);
-        }
@@ -864 +996 @@
-
-    LnoBitmap:
+/*
-        // check whether the class is small enough to justify a string-search
-        // TODO: consider inverse class for 8bit chars?
-        uint class_size;
-        foreach ( p; input.parts )
-+1-p.l
+_+1-p.l_
-        if ( class_size > MAX_SEARCH_LENGTH )
-            goto Lgeneric;
@@ -875 +1008 @@
-        foreach ( p; input.parts )
-        {
-; c <= p.r
+_; c <= p.r_
-                data_str[ind++] = c;
-        }
-        mode = type==Type.consume ? MatchMode.string_search : MatchMode.string_search_l;
-        return;
-
+
-    Lgeneric:
-        data_str = cast(char_t[])input.parts;
@@ -1078 +1211 @@
-    alias char_t[]                  string_t;
-    alias CharRange!(char_t)        range_t;
+    alias CharClass!(char_t)        cc_t;
-
-    string_t    pattern;
@@ -1218 +1352 @@
-        // and matching bracket for total match group
-        if ( unanchored ) {
-CharClass!(char_t)
+cc_t
-            perform(Operator.zero_more_xr, false);
-            perform(Operator.concat, false);
@@ -1298 +1432 @@
-                        perform(Operator.concat, false);
-                    implicit_concat = true;
-CharClass!(char_t)
+cc_t
-                    break;
-                case '$':
@@ -1305 +1439 @@
-                    implicit_concat = true;
-
-CharClass!(char_t)
+cc_t
-                    break;
-                case '^':
@@ -1312 +1446 @@
-                    implicit_concat = true;
-
-CharClass!(char_t)
+cc_t
-                    break;
-                case '>':
@@ -1325 +1459 @@
-                    else
-                        goto default;
-                    break;
-                case '<':
-                    c = readPattern;
@@ -1337 +1470 @@
-                    else
-                        goto default;
-                    break;
-                case '\\':
-                    c = readPattern;
@@ -1357 +1489 @@
-                            break;
-                        case 'w':   // alphanumeric and _
-CharClass!(char_t)
+cc_t
-                            break;
-                        case 'W':   // non-(alphanum and _)
-CharClass!(char_t).alphanum_
+cc_t(cc_t.alphanum_)
-                            cc.negate;
-                            frags ~= constructChars(cc, pred_type);
-                            break;
-                        case 's':   // whitespace
-CharClass!(char_t)
+cc_t
-                            break;
-                        case 'S':   // non-whitespace
-CharClass!(char_t).whitespace
+cc_t(cc_t.whitespace)
-                            cc.negate;
-                            frags ~= constructChars(cc, pred_type);
-                            break;
-                        case 'd':   // digit
-CharClass!(char_t)
+cc_t
-                            break;
-                        case 'D':   // non-digit
-CharClass!(char_t).digit
+cc_t(cc_t.digit)
-                            cc.negate;
-                            frags ~= constructChars(cc, pred_type);
@@ -1385 +1517 @@
-
-                            // create (?<\S>\s|<\s>\S)
-CharClass!(char_t).whitespace
+cc_t(cc_t.whitespace)
-                            cc.negate;
-
@@ -1392 +1524 @@
-                            frags ~= constructChars(cc, predicate_t.Type.lookbehind);
-                            perform(Operator.concat, false);
-CharClass!(char_t)
+cc_t
-                            perform(Operator.altern, false);
-CharClass!(char_t)
+cc_t
-                            perform(Operator.concat, false);
-                            frags ~= constructChars(cc, predicate_t.Type.lookahead);
-
+
-                            perform(Operator.close_par, false);
-                            break;
@@ -1405 +1537 @@
-
-                            // create (?<\S>\S|<\s>\s)
-CharClass!(char_t).whitespace
+cc_t(cc_t.whitespace)
-                            cc.negate;
-
@@ -1414 +1546 @@
-                            frags ~= constructChars(cc, predicate_t.Type.lookahead);
-                            perform(Operator.altern, false);
-CharClass!(char_t)
+cc_t
-                            perform(Operator.concat, false);
-CharClass!(char_t)
-
+cc_t
+
-                            perform(Operator.close_par, false);
-                            break;
@@ -1436 +1568 @@
-                        case '<':
-                        case '>':
+                        default:
-                            frags ~= constructSingleChar(c, pred_type);
-                            break;
-
-
+
-                    }
-                    break;
@@ -1457 +1589 @@
-            if ( implicit_concat )
-                perform(Operator.concat, false);
-CharClass!(char_t)
+cc_t
-            perform(Operator.zero_more_ng, false);
-        }
@@ -1463 +1595 @@
-        // empty operator stack
-        while ( !perform(Operator.eos) ) {}
-
+
-        // set start and finish states
-        start = addState;
@@ -1703 +1835 @@
-    frag_t constructChars(string_t chars, predicate_t.Type type)
-    {
-CharClass!(char_t)
+cc_t
-        for ( int i = 0; i < chars.length; ++i )
-            cc.add(chars[i]);
@@ -1710 +1842 @@
-    }
-
-CharClass!(char_t)
-
-"
+cc_t
+
+ type={}", type
-
-        trans_t trans = addTransition;
-        trans.predicate.type = type;
-
-harclass
+c_t(charclass)
-
-        trans.predicate.optimize;
@@ -1730 +1862 @@
-    frag_t constructCharClass(predicate_t.Type type)
-    {
-"
+ type={}", type
-        auto oldCursor = cursor;
-
@@ -1941 +2073 @@
-            prev = f;
-        }
-
+
-        if ( maxOccur == 0 )
-        {
@@ -1967 +2099 @@
-            prev = f;
-        }
-
+
-        for ( int i = minOccur; i < maxOccur; ++i )
-        {
@@ -2054 +2186 @@
-{
-    alias Predicate!(char_t)    predicate_t;
+    alias CharRange!(char_t)    range_t;
+    alias CharClass!(char_t)    charclass_t;
-    alias char_t[]              string_t;
-
@@ -2159 +2293 @@
-        se.nfa_state = tnfa.start;
-        subset_start.elms ~= se;
-        subset_start = epsilonClosure(subset_start, subset_start);
-
-        // apply lookbehind closure for string/line start
-
-
-lookbehindClosure(subset_start, pred
+tmp_
+tmp_
+epsilonClosure(lookbehindClosure(epsilonClosure(subset_start, subset_start), tmp_pred), subset_start
-
-        start = addState;
@@ -2186 +2319 @@
-
-            // create transitions for each class, creating new states when necessary
-pred
+disjoint
-            {
-                // find NFA state we reach with pred
+                predicate_t pred;
+                pred.appendInput(disjoint);
+
+                // reach will set predicate type correctly
+                debug(tdfa) Stdout.format("from {} with {} reach", state.dfa_state.index, pred.toString);
-                SubsetState target = reach(state, pred);
-
-
-
-
-
-
+
+
+
-                }
-
-
-
-
-
+
+
-
-                Transition trans = new Transition;
@@ -2324 +2456 @@
-        }
-
-
-
+
-        // TODO: mark dead-end states (not leaving a non-finishing susbet)
-        // TODO: mark states that can leave the finishing subset of DFA states or use a greedy transition
@@ -2393 +2524 @@
-        TNFAState!(char_t)  nfa_state;
-        int[uint]           tags;
+        // use place-value priority with 2 places, value(maxPrio) > value(lastPrio)
-        uint                maxPriority,
-                            lastPriority;
@@ -2463 +2595 @@
-            }
-            return str~" ]";
+        }
+    }
+
+    /* ********************************************************************************************
+        Temporary structure used for disjoint predicate computation
+    **********************************************************************************************/
+    struct Mark
+    {
+        char_t  c;
+        bool    end;    /// false = start of range
+
+        int opCmp(Mark m)
+        {
+            if ( c < m.c )
+                return -1;
+            if ( c == m.c )
+            {
+                if ( !end )
+                    return -1;
+                if ( !m.end )
+                    return 1;
+                return 0;
+            }
+            return 1;
-        }
-    }
@@ -2490 +2646 @@
-    }
-
+    Mark[] marks_;
+    
-    /* ********************************************************************************************