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         public final String getName() {
  32             return "NONE";
  33         }
  34 
  35         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
  36             return textP;
  37         }
  38 
  39         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
  40             return textP;
  41         }
  42 
  43     };
  44 
  45     public static final SearchAlgorithm SLOW = new SearchAlgorithm() {
  46 
  47         public final String getName() {
  48             return "EXACT";
  49         }
  50 
  51         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
  52             char[] target = regex.exact;
  53             int targetP = regex.exactP;
  54             int targetEnd = regex.exactEnd;
  55 
  56 
  57             int end = textEnd;
  58             end -= targetEnd - targetP - 1;
  59 
  60             if (end > textRange) end = textRange;
  61 
  62             int s = textP;
  63 
  64             while (s < end) {
  65                 if (text[s] == target[targetP]) {
  66                     int p = s + 1;
  67                     int t = targetP + 1;
  68                     while (t < targetEnd) {
  69                         if (target[t] != text[p++]) break;
  70                         t++;
  71                     }
  72 
  73                     if (t == targetEnd) return s;
  74                 }
  75                 s++;
  76             }
  77 
  78             return -1;
  79         }
  80 
  81         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
  82             char[] target = regex.exact;
  83             int targetP = regex.exactP;
  84             int targetEnd = regex.exactEnd;
  85 
  86             int s = textEnd;
  87             s -= targetEnd - targetP;
  88 
  89             if (s > textStart) {
  90                 s = textStart;
  91             }
  92 
  93             while (s >= textP) {
  94                 if (text[s] == target[targetP]) {
  95                     int p = s + 1;
  96                     int t = targetP + 1;
  97                     while (t < targetEnd) {
  98                         if (target[t] != text[p++]) break;
  99                         t++;
 100                     }
 101                     if (t == targetEnd) return s;
 102                 }
 103                 // s = enc.prevCharHead or s = s <= adjustText ? -1 : s - 1;
 104                 s--;
 105             }
 106             return -1;
 107         }
 108     };
 109 
 110     public static final class SLOW_IC extends SearchAlgorithm {
 111         private final int caseFoldFlag;
 112 
 113         public SLOW_IC(Regex regex) {
 114             this.caseFoldFlag = regex.caseFoldFlag;
 115         }
 116 
 117         public final String getName() {
 118             return "EXACT_IC";
 119         }
 120 
 121         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 122             char[] target = regex.exact;
 123             int targetP = regex.exactP;
 124             int targetEnd = regex.exactEnd;
 125 
 126             int end = textEnd;
 127             end -= targetEnd - targetP - 1;
 128 
 129             if (end > textRange) end = textRange;
 130             int s = textP;
 131 
 132             while (s < end) {
 133                 if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) return s;
 134                 s++;
 135             }
 136             return -1;
 137         }
 138 
 139         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 140             char[] target = regex.exact;
 141             int targetP = regex.exactP;
 142             int targetEnd = regex.exactEnd;
 143 
 144             int s = textEnd;
 145             s -= targetEnd - targetP;
 146 
 147             if (s > textStart) {
 148                 s = textStart;
 149             }
 150 
 151             while (s >= textP) {
 152                 if (lowerCaseMatch(target, targetP, targetEnd, text, s, textEnd)) return s;
 153                 s = EncodingHelper.prevCharHead(adjustText, s);
 154             }
 155             return -1;
 156         }
 157 
 158         private boolean lowerCaseMatch(char[] t, int tP, int tEnd,
 159                                        char[] chars, int p, int end) {
 160 
 161             while (tP < tEnd) {
 162                 if (t[tP++] != Character.toLowerCase(chars[p++])) return false;
 163             }
 164             return true;
 165         }
 166     };
 167 
 168     public static final SearchAlgorithm BM = new SearchAlgorithm() {
 169 
 170         public final String getName() {
 171             return "EXACT_BM";
 172         }
 173 
 174         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 175             char[] target = regex.exact;
 176             int targetP = regex.exactP;
 177             int targetEnd = regex.exactEnd;
 178 
 179             int end = textRange + (targetEnd - targetP) - 1;
 180             if (end > textEnd) end = textEnd;
 181 
 182             int tail = targetEnd - 1;
 183             int s = textP + (targetEnd - targetP) - 1;
 184 
 185             if (regex.intMap == null) {
 186                 while (s < end) {
 187                     int p = s;
 188                     int t = tail;
 189 
 190                     while (text[p] == target[t]) {
 191                         if (t == targetP) return p;
 192                         p--; t--;
 193                     }
 194 
 195                     s += regex.map[text[s] & 0xff];
 196                 }
 197             } else { /* see int_map[] */
 198                 while (s < end) {
 199                     int p = s;
 200                     int t = tail;
 201 
 202                     while (text[p] == target[t]) {
 203                         if (t == targetP) return p;
 204                         p--; t--;
 205                     }
 206 
 207                     s += regex.intMap[text[s] & 0xff];
 208                 }
 209             }
 210             return -1;
 211         }
 212 
 213         private static final int BM_BACKWARD_SEARCH_LENGTH_THRESHOLD = 100;
 214 
 215         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 216             char[] target = regex.exact;
 217             int targetP = regex.exactP;
 218             int targetEnd = regex.exactEnd;
 219 
 220             if (regex.intMapBackward == null) {
 221                 if (s_ - range_ < BM_BACKWARD_SEARCH_LENGTH_THRESHOLD) {
 222                     // goto exact_method;
 223                     return SLOW.searchBackward(regex, text, textP, adjustText, textEnd, textStart, s_, range_);
 224                 }
 225                 setBmBackwardSkip(regex, target, targetP, targetEnd);
 226             }
 227 
 228             int s = textEnd - (targetEnd - targetP);
 229 
 230             if (textStart < s) {
 231                 s = textStart;
 232             }
 233 
 234             while (s >= textP) {
 235                 int p = s;
 236                 int t = targetP;
 237                 while (t < targetEnd && text[p] == target[t]) {
 238                     p++; t++;
 239                 }
 240                 if (t == targetEnd) return s;
 241 
 242                 s -= regex.intMapBackward[text[s] & 0xff];
 243             }
 244             return -1;
 245         }
 246 
 247 
 248         private void setBmBackwardSkip(Regex regex, char[] chars, int p, int end) {
 249             int[] skip;
 250             if (regex.intMapBackward == null) {
 251                 skip = new int[Config.CHAR_TABLE_SIZE];
 252                 regex.intMapBackward = skip;
 253             } else {
 254                 skip = regex.intMapBackward;
 255             }
 256 
 257             int len = end - p;
 258 
 259             for (int i=0; i<Config.CHAR_TABLE_SIZE; i++) skip[i] = len;
 260             for (int i=len-1; i>0; i--) skip[chars[i] & 0xff] = i;
 261         }
 262     };
 263 
 264     public static final SearchAlgorithm MAP = new SearchAlgorithm() {
 265 
 266         public final String getName() {
 267             return "MAP";
 268         }
 269 
 270         public final int search(Regex regex, char[] text, int textP, int textEnd, int textRange) {
 271             byte[] map = regex.map;
 272             int s = textP;
 273 
 274             while (s < textRange) {
 275                 if (text[s] > 0xff || map[text[s]] != 0) return s;
 276                 s++;
 277             }
 278             return -1;
 279         }
 280 
 281         public final int searchBackward(Regex regex, char[] text, int textP, int adjustText, int textEnd, int textStart, int s_, int range_) {
 282             byte[] map = regex.map;
 283             int s = textStart;
 284 
 285             if (s >= textEnd) s = textEnd - 1;
 286             while (s >= textP) {
 287                 if (text[s] > 0xff || map[text[s]] != 0) return s;
 288                 s--;
 289             }
 290             return -1;
 291         }
 292     };
 293 
 294 }