1  /*
     2   * Copyright the original author or authors.
     3   * 
     4   * Licensed under the MOZILLA PUBLIC LICENSE, Version 1.1 (the "License");
     5   * you may not use this file except in compliance with the License.
     6   * You may obtain a copy of the License at
     7   * 
     8   *      http://www.mozilla.org/MPL/MPL-1.1.html
     9   * 
    10   * Unless required by applicable law or agreed to in writing, software
    11   * distributed under the License is distributed on an "AS IS" BASIS,
    12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13   * See the License for the specific language governing permissions and
    14   * limitations under the License.
    15   */
    16   
    17  import org.as2lib.regexp.Pattern;
    18  import org.as2lib.regexp.node.Node; 
    19  import org.as2lib.regexp.node.TreeInfo;
    20  
    21  /**
    22   * {@code GroupCurly} handles the curly-brace style repetition with a 
    23   * specified minimum and maximum occurrences in deterministic cases. 
    24   * 
    25   * This is an iterative optimization over the Prolog and Loop system 
    26   * which would handle this in a recursive way. The * quantifier is 
    27   * handled as a special case. This class saves group settings so that 
    28   * the groups are unset when backing off of a group match.
    29   * 
    30   * @author Igor Sadovskiy
    31   */
    32   
    33  class org.as2lib.regexp.node.GroupCurly extends Node {
    34  	
    35      private var atom:Node;
    36      private var type:Number;
    37      private var cmin:Number;
    38      private var cmax:Number;
    39      private var localIndex:Number;
    40      private var groupIndex:Number;
    41  
    42      public function GroupCurly(node:Node, cmin:Number, cmax:Number, type:Number, local:Number, group:Number) {
    43          this.atom = node;
    44          this.type = type;
    45          this.cmin = cmin;
    46          this.cmax = cmax;
    47          this.localIndex = local;
    48          this.groupIndex = group;
    49      }
    50      
    51      public function match(matcher:Object, i:Number, seq:String):Boolean {
    52          var groups:Array = matcher.groups; // of Number
    53          var locals:Array = matcher.locals; // of Number
    54          var save0:Number = locals[localIndex];
    55          var save1:Number = groups[groupIndex];
    56          var save2:Number = groups[groupIndex+1];
    57  
    58          // Notify GroupTail there is no need to setup group info
    59          // because it will be set here
    60          locals[localIndex] = -1;
    61  
    62          var ret:Boolean = true;
    63          for (var j:Number = 0; j < cmin; j++) {
    64              if (atom.match(matcher, i, seq)) {
    65                  groups[groupIndex] = i;
    66                  groups[groupIndex+1] = i = matcher.last;
    67              } else {
    68                  ret = false;
    69                  break;
    70              }
    71          }
    72          if (!ret) {
    73              ;
    74          } else if (type == Pattern.GREEDY) {
    75              ret = match0(matcher, i, cmin, seq);
    76          } else if (type == Pattern.LAZY) {
    77              ret = match1(matcher, i, cmin, seq);
    78          } else {
    79              ret = match2(matcher, i, cmin, seq);
    80          }
    81          if (!ret) {
    82              locals[localIndex] = save0;
    83              groups[groupIndex] = save1;
    84              groups[groupIndex+1] = save2;
    85          }
    86          return ret;
    87      }
    88      
    89      // Aggressive group match
    90      private function match0(matcher:Object, i:Number, j:Number, seq:String):Boolean {
    91          var groups:Array = matcher.groups; // of Number
    92          var save0:Number = groups[groupIndex];
    93          var save1:Number = groups[groupIndex+1];
    94          while (true) {
    95              if (j >= cmax)
    96                  break;
    97              if (!atom.match(matcher, i, seq))
    98                  break;
    99              var k:Number = matcher.last - i;
   100              if (k <= 0) {
   101                  groups[groupIndex] = i;
   102                  groups[groupIndex+1] = i = i + k;
   103                  break;
   104              }
   105              while (true) {
   106                  groups[groupIndex] = i;
   107                  groups[groupIndex+1] = i = i + k;
   108                  if (++j >= cmax)
   109                      break;
   110                  if (!atom.match(matcher, i, seq))
   111                      break;
   112                  if (i + k != matcher.last) {
   113                      if (match0(matcher, i, j, seq))
   114                          return true;
   115                      break;
   116                  }
   117              }
   118              while (j > cmin) {
   119                  if (next.match(matcher, i, seq)) {
   120                      groups[groupIndex+1] = i;
   121                      groups[groupIndex] = i = i - k;
   122                      return true;
   123                  }
   124                  // backing off
   125                  groups[groupIndex+1] = i;
   126                  groups[groupIndex] = i = i - k;
   127                  j--;
   128              }
   129              break;
   130          }
   131          groups[groupIndex] = save0;
   132          groups[groupIndex+1] = save1;
   133          return next.match(matcher, i, seq);
   134      }
   135      
   136      // Reluctant matching
   137      private function match1(matcher:Object, i:Number, j:Number, seq:String):Boolean {
   138          for (;;) {
   139              if (next.match(matcher, i, seq))
   140                  return true;
   141              if (j >= cmax)
   142                  return false;
   143              if (!atom.match(matcher, i, seq))
   144                  return false;
   145              if (i == matcher.last)
   146                  return false;
   147  
   148              matcher.groups[groupIndex] = i;
   149              matcher.groups[groupIndex+1] = i = matcher.last;
   150              j++;
   151          }
   152      }
   153      // Possessive matching
   154      private function match2(matcher:Object, i:Number, j:Number, seq:String):Boolean {
   155          for (; j < cmax; j++) {
   156              if (!atom.match(matcher, i, seq)) {
   157                  break;
   158              }
   159              matcher.groups[groupIndex] = i;
   160              matcher.groups[groupIndex+1] = matcher.last;
   161              if (i == matcher.last) {
   162                  break;
   163              }
   164              i = matcher.last;
   165          }
   166          return next.match(matcher, i, seq);
   167      }
   168      
   169      public function study(info:TreeInfo):Boolean {
   170          // Save original info
   171          var minL:Number = info.minLength;
   172          var maxL:Number = info.maxLength;
   173          var maxV:Boolean = info.maxValid;
   174          var detm:Boolean = info.deterministic;
   175          info.reset();
   176  
   177          atom.study(info);
   178  
   179          var temp:Number = info.minLength * cmin + minL;
   180          if (temp < minL) {
   181              temp = 0xFFFFFFF; // Arbitrary large number
   182          }
   183          info.minLength = temp;
   184  
   185          if (maxV && info.maxValid) {
   186              temp = info.maxLength * cmax + maxL;
   187              info.maxLength = temp;
   188              if (temp < maxL) {
   189                  info.maxValid = false;
   190              }
   191          } else {
   192              info.maxValid = false;
   193          }
   194  
   195          if (info.deterministic && cmin == cmax) {
   196              info.deterministic = detm;
   197          } else {
   198              info.deterministic = false;
   199          }
   200  
   201          return next.study(info);
   202      }
   203  }
   204  
   205  

• Overview
• Package
• Class
• Source
• Index