jakarta-regexp-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From vgritse...@apache.org
Subject svn commit: r517955 - in /jakarta/regexp/trunk: docs/changes.html src/java/org/apache/regexp/RE.java src/java/org/apache/regexp/RECompiler.java xdocs/changes.xml
Date Wed, 14 Mar 2007 00:42:09 GMT
Author: vgritsenko
Date: Tue Mar 13 17:42:08 2007
New Revision: 517955

URL: http://svn.apache.org/viewvc?view=rev&rev=517955
Log:
compiler optimization: omit unnecessary branch operations

Modified:
    jakarta/regexp/trunk/docs/changes.html
    jakarta/regexp/trunk/src/java/org/apache/regexp/RE.java
    jakarta/regexp/trunk/src/java/org/apache/regexp/RECompiler.java
    jakarta/regexp/trunk/xdocs/changes.xml

Modified: jakarta/regexp/trunk/docs/changes.html
URL: http://svn.apache.org/viewvc/jakarta/regexp/trunk/docs/changes.html?view=diff&rev=517955&r1=517954&r2=517955
==============================================================================
--- jakarta/regexp/trunk/docs/changes.html (original)
+++ jakarta/regexp/trunk/docs/changes.html Tue Mar 13 17:42:08 2007
@@ -91,6 +91,8 @@
 
 <h3>Version 1.5-dev</h3>
 <ul>
+<li>Implemented optimization: RE compiler omits branch instruction if only one
+    branch is present (VG)</li>
 <li>Fixed Bug
     <a href="http://issues.apache.org/bugzilla/show_bug.cgi?id=9153">9153</a>:
     {m,n} implementation had exponential complexity (VG)</li>

Modified: jakarta/regexp/trunk/src/java/org/apache/regexp/RE.java
URL: http://svn.apache.org/viewvc/jakarta/regexp/trunk/src/java/org/apache/regexp/RE.java?view=diff&rev=517955&r1=517954&r2=517955
==============================================================================
--- jakarta/regexp/trunk/src/java/org/apache/regexp/RE.java (original)
+++ jakarta/regexp/trunk/src/java/org/apache/regexp/RE.java Tue Mar 13 17:42:08 2007
@@ -483,7 +483,7 @@
      */
     public RE()
     {
-        this((REProgram)null, MATCH_NORMAL);
+        this((REProgram) null, MATCH_NORMAL);
     }
 
     /**

Modified: jakarta/regexp/trunk/src/java/org/apache/regexp/RECompiler.java
URL: http://svn.apache.org/viewvc/jakarta/regexp/trunk/src/java/org/apache/regexp/RECompiler.java?view=diff&rev=517955&r1=517954&r2=517955
==============================================================================
--- jakarta/regexp/trunk/src/java/org/apache/regexp/RECompiler.java (original)
+++ jakarta/regexp/trunk/src/java/org/apache/regexp/RECompiler.java Tue Mar 13 17:42:08 2007
@@ -1092,16 +1092,17 @@
     }
 
     /**
-     * Compile one branch of an or operator (implements concatenation)
+     * Compile body of one branch of an or operator (implements concatenation)
+     *
      * @param flags Flags passed by reference
-     * @return Pointer to branch node
+     * @return Pointer to first node in the branch
      * @exception RESyntaxException Thrown if the regular expression has invalid syntax.
      */
     int branch(int[] flags) throws RESyntaxException
     {
         // Get each possibly closured piece and concat
         int node;
-        int ret = node(RE.OP_BRANCH, 0);
+        int ret = -1;
         int chain = -1;
         int[] closureFlags = new int[1];
         boolean nullable = true;
@@ -1123,12 +1124,15 @@
 
             // Chain starts at current
             chain = node;
+            if (ret == -1) {
+                ret = node;
+            }
         }
 
         // If we don't run loop, make a nothing node
-        if (chain == -1)
+        if (ret == -1)
         {
-            node(RE.OP_NOTHING, 0);
+            ret = node(RE.OP_NOTHING, 0);
         }
 
         // Set nullable flag for this branch
@@ -1136,12 +1140,14 @@
         {
             flags[0] |= NODE_NULLABLE;
         }
+
         return ret;
     }
 
     /**
      * Compile an expression with possible parens around it.  Paren matching
      * is done at this level so we can tie the branch tails together.
+     *
      * @param flags Flag value passed by reference
      * @return Node index of expression in instruction array
      * @exception RESyntaxException Thrown if the regular expression has invalid syntax.
@@ -1155,11 +1161,11 @@
         if ((flags[0] & NODE_TOPLEVEL) == 0 && pattern.charAt(idx) == '(')
         {
             // if its a cluster ( rather than a proper subexpression ie with backrefs )
-            if ( idx + 2 < len && pattern.charAt( idx + 1 ) == '?' &&
pattern.charAt( idx + 2 ) == ':' )
+            if (idx + 2 < len && pattern.charAt(idx + 1) == '?' && pattern.charAt(idx
+ 2) == ':')
             {
                 paren = 2;
                 idx += 3;
-                ret = node( RE.OP_OPEN_CLUSTER, 0 );
+                ret = node(RE.OP_OPEN_CLUSTER, 0);
             }
             else
             {
@@ -1170,7 +1176,8 @@
         }
         flags[0] &= ~NODE_TOPLEVEL;
 
-        // Create a branch node
+        // Process contents of first branch node
+        boolean open = false;
         int branch = branch(flags);
         if (ret == -1)
         {
@@ -1184,14 +1191,20 @@
         // Loop through branches
         while (idx < len && pattern.charAt(idx) == '|')
         {
+            // Now open the first branch since there are more than one
+            if (!open) {
+                nodeInsert(RE.OP_BRANCH, 0, branch);
+                open = true;
+            }
+
             idx++;
-            branch = branch(flags);
-            setNextOfEnd(ret, branch);
+            setNextOfEnd(branch, branch = node(RE.OP_BRANCH, 0));
+            branch(flags);
         }
 
         // Create an ending node (either a close paren or an OP_END)
         int end;
-        if ( paren > 0 )
+        if (paren > 0)
         {
             if (idx < len && pattern.charAt(idx) == ')')
             {
@@ -1201,13 +1214,13 @@
             {
                 syntaxError("Missing close paren");
             }
-            if ( paren == 1 )
+            if (paren == 1)
             {
                 end = node(RE.OP_CLOSE, closeParens);
             }
             else
             {
-                end = node( RE.OP_CLOSE_CLUSTER, 0 );
+                end = node(RE.OP_CLOSE_CLUSTER, 0);
             }
         }
         else

Modified: jakarta/regexp/trunk/xdocs/changes.xml
URL: http://svn.apache.org/viewvc/jakarta/regexp/trunk/xdocs/changes.xml?view=diff&rev=517955&r1=517954&r2=517955
==============================================================================
--- jakarta/regexp/trunk/xdocs/changes.xml (original)
+++ jakarta/regexp/trunk/xdocs/changes.xml Tue Mar 13 17:42:08 2007
@@ -34,6 +34,8 @@
 
 <h3>Version 1.5-dev</h3>
 <ul>
+<li>Implemented optimization: RE compiler omits branch instruction if only one
+    branch is present (VG)</li>
 <li>Fixed Bug
     <a href="http://issues.apache.org/bugzilla/show_bug.cgi?id=9153">9153</a>:
     {m,n} implementation had exponential complexity (VG)</li>



---------------------------------------------------------------------
To unsubscribe, e-mail: regexp-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: regexp-dev-help@jakarta.apache.org


Mime
View raw message