1 /*
   2  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   3  * this software and associated documentation files (the "Software"), to deal in
   4  * the Software without restriction, including without limitation the rights to
   5  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   6  * of the Software, and to permit persons to whom the Software is furnished to do
   7  * so, subject to the following conditions:
   8  *
   9  * The above copyright notice and this permission notice shall be included in all
  10  * copies or substantial portions of the Software.
  11  *
  12  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  13  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  14  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  15  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  16  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  17  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  18  * SOFTWARE.
  19  */
  20 package jdk.nashorn.internal.runtime.regexp.joni;
  21 
  22 public abstract class SearchAlgorithm {
  23 
  24     public abstract String getName();
  25     public abstract int search(Regex regex, char[] text, int textP, int textEnd, int textRange);
  26     public abstract int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_);
  27 
  28 
  29     public static final SearchAlgorithm NONE = new SearchAlgorithm() {
  30 
  31         @Override
  32         public final String getName() {
  33             return "NONE";
  34         }
  35 
  36         @Override
  37         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
  38             return textP;
  39         }
  40 
  41         @Override
  42         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
  43             return textP;
  44         }
  45 
  46     };
  47 
  48     public static final SearchAlgorithm SLOW = new SearchAlgorithm() {
  49 
  50         @Override
  51         public final String getName() {
  52             return "EXACT";
  53         }
  54 
  55         @Override
  56         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
  57             char[] target = regex.exact;
  58             int targetP = regex.exactP;
  59             int targetEnd = regex.exactEnd;
  60 
  61 
  62             int end = textEnd;
  63             end -= targetEnd - targetP - 1;
  64 
  65             if (end > textRange) end = textRange;
  66 
  67             int s = textP;
  68 
  69             while (s < end) {
  70                 if (text[s] == target[targetP]) {
  71                     int p = s + 1;
  72                     int t = targetP + 1;
  73                     while (t < targetEnd) {
  74                         if (target[t] != text[p++]) break;
  75                         t++;
  76                     }
  77 
  78                     if (t == targetEnd) return s;
  79                 }
  80                 s++;
  81             }
  82 
  83             return -1;
  84         }
  85 
  86         @Override
  87         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
  88             char[] target = regex.exact;
  89             int targetP = regex.exactP;
  90             int targetEnd = regex.exactEnd;
  91 
  92             int s = textEnd;
  93             s -= targetEnd - targetP;
  94 
  95             if (s > textStart) {
  96                 s = textStart;
  97             }
  98 
  99             while (s >= textP) {
 100                 if (text[s] == target[targetP]) {
 101                     int p = s + 1;
 102                     int t = targetP + 1;
 103                     while (t < targetEnd) {
 104                         if (target[t] != text[p++]) break;
 105                         t++;
 106                     }
 107                     if (t == targetEnd) return s;
 108                 }
 109                 // s = enc.prevCharHead or s = s <= adjustText ? -1 : s - 1;
 110                 s--;
 111             }
 112             return -1;
 113         }
 114     };
 115 
 116     public static final class SLOW_IC extends SearchAlgorithm {
 117         private final int caseFoldFlag;
 118 
 119         public SLOW_IC(Regex regex) {
 120             this.caseFoldFlag = regex.caseFoldFlag;
 121         }
 122 
 123         @Override
 124         public final String getName() {
 125             return "EXACT_IC";
 126         }
 127 
 128         @Override
 129         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 130             char[] target = regex.exact;
 131             int targetP = regex.exactP;
 132             int targetEnd = regex.exactEnd;
 133 
 134             int end = textEnd;
 135             end -= targetEnd - targetP - 1;
 136 
 137             if (end > textRange) end = textRange;
 138             int s = textP;
 139 
 140             while (s < end) {
 141                 if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) return s;
 142                 s++;
 143             }
 144             return -1;
 145         }
 146 
 147         @Override
 148         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 149             char[] target = regex.exact;
 150             int targetP = regex.exactP;
 151             int targetEnd = regex.exactEnd;
 152 
 153             int s = textEnd;
 154             s -= targetEnd - targetP;
 155 
 156             if (s > textStart) {
 157                 s = textStart;
 158             }
 159 
 160             while (s >= textP) {
 161                 if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) return s;
 162                 s = EncodingHelper.prevCharHead(adjustText, s);
 163             }
 164             return -1;
 165         }
 166 
 167         private boolean lowerCaseMatch(char[] t, int tP, int tEnd,
 168                                        char[] chars, int p, int end) {
 169 
 170             while (tP < tEnd) {
 171                 if (t[tP++] != EncodingHelper.toLowerCase(chars[p++])) return false;
 172             }
 173             return true;
 174         }
 175     }
 176 
 177     public static final SearchAlgorithm BM = new SearchAlgorithm() {
 178 
 179         @Override
 180         public final String getName() {
 181             return "EXACT_BM";
 182         }
 183 
 184         @Override
 185         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 186             char[] target = regex.exact;
 187             int targetP = regex.exactP;
 188             int targetEnd = regex.exactEnd;
 189 
 190             int end = textRange + (targetEnd - targetP) - 1;
 191             if (end > textEnd) end = textEnd;
 192 
 193             int tail = targetEnd - 1;
 194             int s = textP + (targetEnd - targetP) - 1;
 195 
 196             if (regex.intMap == null) {
 197                 while (s < end) {
 198                     int p = s;
 199                     int t = tail;
 200 
 201                     while (text[p] == target[t]) {
 202                         if (t == targetP) return p;
 203                         p--; t--;
 204                     }
 205 
 206                     s += regex.map[text[s] & 0xff];
 207                 }
 208             } else { /* see int_map[] */
 209                 while (s < end) {
 210                     int p = s;
 211                     int t = tail;
 212 
 213                     while (text[p] == target[t]) {
 214                         if (t == targetP) return p;
 215                         p--; t--;
 216                     }
 217 
 218                     s += regex.intMap[text[s] & 0xff];
 219                 }
 220             }
 221             return -1;
 222         }
 223 
 224         private static final int BM_BACKWARD_SEARCH_LENGTH_THRESHOLD = 100;
 225 
 226         @Override
 227         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 228             char[] target = regex.exact;
 229             int targetP = regex.exactP;
 230             int targetEnd = regex.exactEnd;
 231 
 232             if (regex.intMapBackward == null) {
 233                 if (s_ - range_ < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD) {
 234                     // goto exact_method;
 235                     return SLOW.searchBackward(regex, text, textP, adjustText, textEnd, textStart, s_, range_);
 236                 }
 237                 setBmBackwardSkip(regex, target, targetP, targetEnd);
 238             }
 239 
 240             int s = textEnd - (targetEnd - targetP);
 241 
 242             if (textStart < s) {
 243                 s = textStart;
 244             }
 245 
 246             while (s >= textP) {
 247                 int p = s;
 248                 int t = targetP;
 249                 while (t < targetEnd && text[p] == target[t]) {
 250                     p++; t++;
 251                 }
 252                 if (t == targetEnd) return s;
 253 
 254                 s -= regex.intMapBackward[text[s] & 0xff];
 255             }
 256             return -1;
 257         }
 258 
 259 
 260         private void setBmBackwardSkip(Regex regex, char[] chars, int p, int end) {
 261             int[] skip;
 262             if (regex.intMapBackward == null) {
 263                 skip = new int[Config.CHAR_TABLE_SIZE];
 264                 regex.intMapBackward = skip;
 265             } else {
 266                 skip = regex.intMapBackward;
 267             }
 268 
 269             int len = end - p;
 270 
 271             for (int i=0; i<Config.CHAR_TABLE_SIZE; i++) skip[i] = len;
 272             for (int i=len-1; i>0; i--) skip[chars[i] & 0xff] = i;
 273         }
 274     };
 275 
 276     public static final SearchAlgorithm MAP = new SearchAlgorithm() {
 277 
 278         @Override
 279         public final String getName() {
 280             return "MAP";
 281         }
 282 
 283         @Override
 284         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 285             byte[] map = regex.map;
 286             int s = textP;
 287 
 288             while (s < textRange) {
 289                 if (text[s] > 0xff || map[text[s]] != 0) return s;
 290                 s++;
 291             }
 292             return -1;
 293         }
 294 
 295         @Override
 296         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 297             byte[] map = regex.map;
 298             int s = textStart;
 299 
 300             if (s >= textEnd) s = textEnd - 1;
 301             while (s >= textP) {
 302                 if (text[s] > 0xff || map[text[s]] != 0) return s;
 303                 s--;
 304             }
 305             return -1;
 306         }
 307     };
 308 
 309 }
--- EOF ---