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 }