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 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsAll;
23 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsAt;
24 import static jdk.nashorn.internal.runtime.regexp.joni.BitStatus.bsOnAt;
25 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isFindCondition;
26 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isIgnoreCase;
27 import static jdk.nashorn.internal.runtime.regexp.joni.Option.isMultiline;
28 import static jdk.nashorn.internal.runtime.regexp.joni.ast.ConsAltNode.newAltNode;
29 import static jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode.isRepeatInfinite;
30 import java.util.HashSet;
31 import jdk.nashorn.internal.runtime.regexp.joni.ast.AnchorNode;
32 import jdk.nashorn.internal.runtime.regexp.joni.ast.BackRefNode;
33 import jdk.nashorn.internal.runtime.regexp.joni.ast.CClassNode;
34 import jdk.nashorn.internal.runtime.regexp.joni.ast.ConsAltNode;
35 import jdk.nashorn.internal.runtime.regexp.joni.ast.EncloseNode;
36 import jdk.nashorn.internal.runtime.regexp.joni.ast.Node;
37 import jdk.nashorn.internal.runtime.regexp.joni.ast.QuantifierNode;
38 import jdk.nashorn.internal.runtime.regexp.joni.ast.StringNode;
39 import jdk.nashorn.internal.runtime.regexp.joni.constants.AnchorType;
40 import jdk.nashorn.internal.runtime.regexp.joni.constants.EncloseType;
41 import jdk.nashorn.internal.runtime.regexp.joni.constants.NodeType;
42 import jdk.nashorn.internal.runtime.regexp.joni.constants.StackPopLevel;
43 import jdk.nashorn.internal.runtime.regexp.joni.constants.TargetInfo;
44 import jdk.nashorn.internal.runtime.regexp.joni.encoding.ObjPtr;
45 import jdk.nashorn.internal.runtime.regexp.joni.exception.InternalException;
46 import jdk.nashorn.internal.runtime.regexp.joni.exception.SyntaxException;
47 import jdk.nashorn.internal.runtime.regexp.joni.exception.ValueException;
48
49 final class Analyser extends Parser {
50
51 protected Analyser(final ScanEnvironment env, final char[] chars, final int p, final int end) {
52 super(env, chars, p, end);
53 }
54
55 @SuppressWarnings("unused")
56 protected final void compile() {
57 if (Config.DEBUG) {
58 Config.log.println(new String(chars, getBegin(), getEnd()));
59 }
60
61 reset();
62
63 regex.numMem = 0;
64 regex.numRepeat = 0;
65 regex.numNullCheck = 0;
66 //regex.repeatRangeAlloc = 0;
67 regex.repeatRangeLo = null;
68 regex.repeatRangeHi = null;
69
70 parse();
71
72 if (Config.DEBUG_PARSE_TREE_RAW && Config.DEBUG_PARSE_TREE) {
73 Config.log.println("<RAW TREE>");
74 Config.log.println(root + "\n");
75 }
76
77 root = setupTree(root, 0);
78 if (Config.DEBUG_PARSE_TREE) {
79 if (Config.DEBUG_PARSE_TREE_RAW) {
80 Config.log.println("<TREE>");
81 }
82 root.verifyTree(new HashSet<Node>(), env.reg.warnings);
83 Config.log.println(root + "\n");
84 }
85
86 regex.captureHistory = env.captureHistory;
87 regex.btMemStart = env.btMemStart;
88 regex.btMemEnd = env.btMemEnd;
89
90 if (isFindCondition(regex.options)) {
91 regex.btMemEnd = bsAll();
92 } else {
93 regex.btMemEnd = env.btMemEnd;
94 regex.btMemEnd |= regex.captureHistory;
95 }
96
97 regex.clearOptimizeInfo();
98
99 if (!Config.DONT_OPTIMIZE) {
100 setOptimizedInfoFromTree(root);
101 }
102
103 env.memNodes = null;
104
105 new ArrayCompiler(this).compile();
106
107 if (regex.numRepeat != 0 || regex.btMemEnd != 0) {
108 regex.stackPopLevel = StackPopLevel.ALL;
109 } else {
110 if (regex.btMemStart != 0) {
111 regex.stackPopLevel = StackPopLevel.MEM_START;
112 } else {
113 regex.stackPopLevel = StackPopLevel.FREE;
114 }
115 }
116
117 if (Config.DEBUG_COMPILE) {
118 Config.log.println("stack used: " + regex.stackNeeded);
119 if (Config.USE_STRING_TEMPLATES) {
120 Config.log.print("templates: " + regex.templateNum + "\n");
121 }
122 Config.log.println(new ByteCodePrinter(regex).byteCodeListToString());
123
124 } // DEBUG_COMPILE
125 }
126
127 private void swap(final Node a, final Node b) {
128 a.swap(b);
129
130 if (root == b) {
131 root = a;
132 } else if (root == a) {
133 root = b;
134 }
135 }
136
137 // USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
138 private int quantifiersMemoryInfo(final Node node) {
139 int info = 0;
140
141 switch(node.getType()) {
142 case NodeType.LIST:
143 case NodeType.ALT:
144 ConsAltNode can = (ConsAltNode)node;
145 do {
146 final int v = quantifiersMemoryInfo(can.car);
147 if (v > info) {
148 info = v;
149 }
150 } while ((can = can.cdr) != null);
151 break;
152
153 case NodeType.QTFR:
154 final QuantifierNode qn = (QuantifierNode)node;
155 if (qn.upper != 0) {
156 info = quantifiersMemoryInfo(qn.target);
157 }
158 break;
159
160 case NodeType.ENCLOSE:
161 final EncloseNode en = (EncloseNode)node;
162 switch (en.type) {
163 case EncloseType.MEMORY:
164 return TargetInfo.IS_EMPTY_MEM;
165
166 case EncloseType.OPTION:
167 case EncloseNode.STOP_BACKTRACK:
168 info = quantifiersMemoryInfo(en.target);
169 break;
170
171 default:
172 break;
173 } // inner switch
174 break;
175
176 case NodeType.BREF:
177 case NodeType.STR:
178 case NodeType.CTYPE:
179 case NodeType.CCLASS:
180 case NodeType.CANY:
181 case NodeType.ANCHOR:
182 default:
183 break;
184 } // switch
185
186 return info;
187 }
188
189 private int getMinMatchLength(final Node node) {
190 int min = 0;
191
192 switch (node.getType()) {
193 case NodeType.BREF:
194 final BackRefNode br = (BackRefNode)node;
195 if (br.isRecursion()) {
196 break;
197 }
198
199 if (br.backRef > env.numMem) {
200 throw new ValueException(ERR_INVALID_BACKREF);
201 }
202 min = getMinMatchLength(env.memNodes[br.backRef]);
203
204 break;
205
206 case NodeType.LIST:
207 ConsAltNode can = (ConsAltNode)node;
208 do {
209 min += getMinMatchLength(can.car);
210 } while ((can = can.cdr) != null);
211 break;
212
213 case NodeType.ALT:
214 ConsAltNode y = (ConsAltNode)node;
215 do {
216 final Node x = y.car;
217 final int tmin = getMinMatchLength(x);
218 if (y == node) {
219 min = tmin;
220 } else if (min > tmin) {
221 min = tmin;
222 }
223 } while ((y = y.cdr) != null);
224 break;
225
226 case NodeType.STR:
227 min = ((StringNode)node).length();
228 break;
229
230 case NodeType.CTYPE:
231 min = 1;
232 break;
233
234 case NodeType.CCLASS:
235 case NodeType.CANY:
236 min = 1;
237 break;
238
239 case NodeType.QTFR:
240 final QuantifierNode qn = (QuantifierNode)node;
241 if (qn.lower > 0) {
242 min = getMinMatchLength(qn.target);
243 min = MinMaxLen.distanceMultiply(min, qn.lower);
244 }
245 break;
246
247 case NodeType.ENCLOSE:
248 final EncloseNode en = (EncloseNode)node;
249 switch (en.type) {
250 case EncloseType.MEMORY:
251 if (en.isMinFixed()) {
252 min = en.minLength;
253 } else {
254 min = getMinMatchLength(en.target);
255 en.minLength = min;
256 en.setMinFixed();
257 }
258 break;
259
260 case EncloseType.OPTION:
261 case EncloseType.STOP_BACKTRACK:
262 min = getMinMatchLength(en.target);
263 break;
264
265 default:
266 break;
267 } // inner switch
268 break;
269
270 case NodeType.ANCHOR:
271 default:
272 break;
273 } // switch
274
275 return min;
276 }
277
278 private int getMaxMatchLength(final Node node) {
279 int max = 0;
280
281 switch (node.getType()) {
282 case NodeType.LIST:
283 ConsAltNode ln = (ConsAltNode)node;
284 do {
285 final int tmax = getMaxMatchLength(ln.car);
286 max = MinMaxLen.distanceAdd(max, tmax);
287 } while ((ln = ln.cdr) != null);
288 break;
289
290 case NodeType.ALT:
291 ConsAltNode an = (ConsAltNode)node;
292 do {
293 final int tmax = getMaxMatchLength(an.car);
294 if (max < tmax) {
295 max = tmax;
296 }
297 } while ((an = an.cdr) != null);
298 break;
299
300 case NodeType.STR:
301 max = ((StringNode)node).length();
302 break;
303
304 case NodeType.CTYPE:
305 max = 1;
306 break;
307
308 case NodeType.CCLASS:
309 case NodeType.CANY:
310 max = 1;
311 break;
312
313 case NodeType.BREF:
314 final BackRefNode br = (BackRefNode)node;
315 if (br.isRecursion()) {
316 max = MinMaxLen.INFINITE_DISTANCE;
317 break;
318 }
319
320 if (br.backRef > env.numMem) {
321 throw new ValueException(ERR_INVALID_BACKREF);
322 }
323 final int tmax = getMaxMatchLength(env.memNodes[br.backRef]);
324 if (max < tmax) {
325 max = tmax;
326 }
327 break;
328
329 case NodeType.QTFR:
330 final QuantifierNode qn = (QuantifierNode)node;
331 if (qn.upper != 0) {
332 max = getMaxMatchLength(qn.target);
333 if (max != 0) {
334 if (!isRepeatInfinite(qn.upper)) {
335 max = MinMaxLen.distanceMultiply(max, qn.upper);
336 } else {
337 max = MinMaxLen.INFINITE_DISTANCE;
338 }
339 }
340 }
341 break;
342
343 case NodeType.ENCLOSE:
344 final EncloseNode en = (EncloseNode)node;
345 switch (en.type) {
346 case EncloseType.MEMORY:
347 if (en.isMaxFixed()) {
348 max = en.maxLength;
349 } else {
350 max = getMaxMatchLength(en.target);
351 en.maxLength = max;
352 en.setMaxFixed();
353 }
354 break;
355
356 case EncloseType.OPTION:
357 case EncloseType.STOP_BACKTRACK:
358 max = getMaxMatchLength(en.target);
359 break;
360
361 default:
362 break;
363 } // inner switch
364 break;
365
366 case NodeType.ANCHOR:
367 default:
368 break;
369 } // switch
370
371 return max;
372 }
373
374 private static final int GET_CHAR_LEN_VARLEN = -1;
375 private static final int GET_CHAR_LEN_TOP_ALT_VARLEN = -2;
376 protected final int getCharLengthTree(final Node node) {
377 return getCharLengthTree(node, 0);
378 }
379
380 private int getCharLengthTree(final Node node, final int levelp) {
381 final int level = levelp + 1;
382
383 int len = 0;
384 returnCode = 0;
385
386 switch(node.getType()) {
387 case NodeType.LIST:
388 ConsAltNode ln = (ConsAltNode)node;
389 do {
390 final int tlen = getCharLengthTree(ln.car, level);
391 if (returnCode == 0) {
392 len = MinMaxLen.distanceAdd(len, tlen);
393 }
394 } while (returnCode == 0 && (ln = ln.cdr) != null);
395 break;
396
397 case NodeType.ALT:
398 ConsAltNode an = (ConsAltNode)node;
399 boolean varLen = false;
400
401 int tlen = getCharLengthTree(an.car, level);
402 while (returnCode == 0 && (an = an.cdr) != null) {
403 final int tlen2 = getCharLengthTree(an.car, level);
404 if (returnCode == 0) {
405 if (tlen != tlen2) {
406 varLen = true;
407 }
408 }
409 }
410
411 if (returnCode == 0) {
412 if (varLen) {
413 if (level == 1) {
414 returnCode = GET_CHAR_LEN_TOP_ALT_VARLEN;
415 } else {
416 returnCode = GET_CHAR_LEN_VARLEN;
417 }
418 } else {
419 len = tlen;
420 }
421 }
422 break;
423
424 case NodeType.STR:
425 final StringNode sn = (StringNode)node;
426 len = sn.length();
427 break;
428
429 case NodeType.QTFR:
430 final QuantifierNode qn = (QuantifierNode)node;
431 if (qn.lower == qn.upper) {
432 tlen = getCharLengthTree(qn.target, level);
433 if (returnCode == 0) {
434 len = MinMaxLen.distanceMultiply(tlen, qn.lower);
435 }
436 } else {
437 returnCode = GET_CHAR_LEN_VARLEN;
438 }
439 break;
440
441 case NodeType.CTYPE:
442 case NodeType.CCLASS:
443 case NodeType.CANY:
444 len = 1;
445 break;
446
447 case NodeType.ENCLOSE:
448 final EncloseNode en = (EncloseNode)node;
449 switch(en.type) {
450 case EncloseType.MEMORY:
451 if (en.isCLenFixed()) {
452 len = en.charLength;
453 } else {
454 len = getCharLengthTree(en.target, level);
455 if (returnCode == 0) {
456 en.charLength = len;
457 en.setCLenFixed();
458 }
459 }
460 break;
461
462 case EncloseType.OPTION:
463 case EncloseType.STOP_BACKTRACK:
464 len = getCharLengthTree(en.target, level);
465 break;
466
467 default:
468 break;
469 } // inner switch
470 break;
471
472 case NodeType.ANCHOR:
473 break;
474
475 default:
476 returnCode = GET_CHAR_LEN_VARLEN;
477 } // switch
478 return len;
479 }
480
481 /* x is not included y ==> 1 : 0 */
482 private static boolean isNotIncluded(final Node xn, final Node yn) {
483 Node x = xn;
484 Node y = yn;
485 Node tmp;
486
487 // !retry:!
488 retry: while(true) {
489
490 final int yType = y.getType();
491
492 switch(x.getType()) {
493 case NodeType.CTYPE:
494 switch(yType) {
495
496 case NodeType.CCLASS:
497 // !swap:!
498 tmp = x;
499 x = y;
500 y = tmp;
501 // !goto retry;!
502 continue retry;
503
504 case NodeType.STR:
505 // !goto swap;!
506 tmp = x;
507 x = y;
508 y = tmp;
509 continue retry;
510
511 default:
512 break;
513 } // inner switch
514 break;
515
516 case NodeType.CCLASS:
517 final CClassNode xc = (CClassNode)x;
518
519 switch(yType) {
520
521 case NodeType.CCLASS:
522 final CClassNode yc = (CClassNode)y;
523
524 for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {
525 boolean v = xc.bs.at(i);
526 if ((v && !xc.isNot()) || (!v && xc.isNot())) {
527 v = yc.bs.at(i);
528 if ((v && !yc.isNot()) || (!v && yc.isNot())) {
529 return false;
530 }
531 }
532 }
533 if ((xc.mbuf == null && !xc.isNot()) || yc.mbuf == null && !yc.isNot()) {
534 return true;
535 }
536 return false;
537 // break; not reached
538
539 case NodeType.STR:
540 // !goto swap;!
541 tmp = x;
542 x = y;
543 y = tmp;
544 continue retry;
545
546 default:
547 break;
548
549 } // inner switch
550 break; // case NodeType.CCLASS
551
552 case NodeType.STR:
553 final StringNode xs = (StringNode)x;
554 if (xs.length() == 0) {
555 break;
556 }
557
558 switch (yType) {
559
560 case NodeType.CCLASS:
561 final CClassNode cc = (CClassNode)y;
562 final int code = xs.chars[xs.p];
563 return !cc.isCodeInCC(code);
564
565 case NodeType.STR:
566 final StringNode ys = (StringNode)y;
567 int len = xs.length();
568 if (len > ys.length()) {
569 len = ys.length();
570 }
571 if (xs.isAmbig() || ys.isAmbig()) {
572 /* tiny version */
573 return false;
574 }
575 for (int i=0, pt=ys.p, q=xs.p; i<len; i++, pt++, q++) {
576 if (ys.chars[pt] != xs.chars[q]) {
577 return true;
578 }
579 }
580 break;
581
582 default:
583 break;
584 } // inner switch
585
586 break; // case NodeType.STR
587 default:
588 break;
589
590 } // switch
591
592 break;
593 } // retry: while
594 return false;
595 }
596
597 private Node getHeadValueNode(final Node node, final boolean exact) {
598 Node n = null;
599
600 switch(node.getType()) {
601 case NodeType.BREF:
602 case NodeType.ALT:
603 case NodeType.CANY:
604 break;
605
606 case NodeType.CTYPE:
607 case NodeType.CCLASS:
608 if (!exact) {
609 n = node;
610 }
611 break;
612
613 case NodeType.LIST:
614 n = getHeadValueNode(((ConsAltNode)node).car, exact);
615 break;
616
617 case NodeType.STR:
618 final StringNode sn = (StringNode)node;
619 if (sn.end <= sn.p)
620 {
621 break; // ???
622 }
623
624 if (exact && !sn.isRaw() && isIgnoreCase(regex.options)){
625 // nothing
626 } else {
627 n = node;
628 }
629 break;
630
631 case NodeType.QTFR:
632 final QuantifierNode qn = (QuantifierNode)node;
633 if (qn.lower > 0) {
634 if (qn.headExact != null) {
635 n = qn.headExact;
636 } else {
637 n = getHeadValueNode(qn.target, exact);
638 }
639 }
640 break;
641
642 case NodeType.ENCLOSE:
643 final EncloseNode en = (EncloseNode)node;
644
645 switch (en.type) {
646 case EncloseType.OPTION:
647 final int options = regex.options;
648 regex.options = en.option;
649 n = getHeadValueNode(en.target, exact);
650 regex.options = options;
651 break;
652
653 case EncloseType.MEMORY:
654 case EncloseType.STOP_BACKTRACK:
655 n = getHeadValueNode(en.target, exact);
656 break;
657
658 default:
659 break;
660 } // inner switch
661 break;
662
663 case NodeType.ANCHOR:
664 final AnchorNode an = (AnchorNode)node;
665 if (an.type == AnchorType.PREC_READ) {
666 n = getHeadValueNode(an.target, exact);
667 }
668 break;
669
670 default:
671 break;
672 } // switch
673
674 return n;
675 }
676
677 // true: invalid
678 private boolean checkTypeTree(final Node node, final int typeMask, final int encloseMask, final int anchorMask) {
679 if ((node.getType2Bit() & typeMask) == 0) {
680 return true;
681 }
682
683 boolean invalid = false;
684
685 switch(node.getType()) {
686 case NodeType.LIST:
687 case NodeType.ALT:
688 ConsAltNode can = (ConsAltNode)node;
689 do {
690 invalid = checkTypeTree(can.car, typeMask, encloseMask, anchorMask);
691 } while (!invalid && (can = can.cdr) != null);
692 break;
693
694 case NodeType.QTFR:
695 invalid = checkTypeTree(((QuantifierNode)node).target, typeMask, encloseMask, anchorMask);
696 break;
697
698 case NodeType.ENCLOSE:
699 final EncloseNode en = (EncloseNode)node;
700 if ((en.type & encloseMask) == 0) {
701 return true;
702 }
703 invalid = checkTypeTree(en.target, typeMask, encloseMask, anchorMask);
704 break;
705
706 case NodeType.ANCHOR:
707 final AnchorNode an = (AnchorNode)node;
708 if ((an.type & anchorMask) == 0) {
709 return true;
710 }
711
712 if (an.target != null) {
713 invalid = checkTypeTree(an.target, typeMask, encloseMask, anchorMask);
714 }
715 break;
716
717 default:
718 break;
719
720 } // switch
721
722 return invalid;
723 }
724
725 /* divide different length alternatives in look-behind.
726 (?<=A|B) ==> (?<=A)|(?<=B)
727 (?<!A|B) ==> (?<!A)(?<!B)
728 */
729 private Node divideLookBehindAlternatives(final Node nodep) {
730 Node node = nodep;
731 final AnchorNode an = (AnchorNode)node;
732 final int anchorType = an.type;
733 Node head = an.target;
734 Node np = ((ConsAltNode)head).car;
735
736 swap(node, head);
737
738 final Node tmp = node;
739 node = head;
740 head = tmp;
741
742 ((ConsAltNode)node).setCar(head);
743 ((AnchorNode)head).setTarget(np);
744 np = node;
745
746 while ((np = ((ConsAltNode)np).cdr) != null) {
747 final AnchorNode insert = new AnchorNode(anchorType);
748 insert.setTarget(((ConsAltNode)np).car);
749 ((ConsAltNode)np).setCar(insert);
750 }
751
752 if (anchorType == AnchorType.LOOK_BEHIND_NOT) {
753 np = node;
754 do {
755 ((ConsAltNode)np).toListNode(); /* alt -> list */
756 } while ((np = ((ConsAltNode)np).cdr) != null);
757 }
758
759 return node;
760 }
761
762 private Node setupLookBehind(final Node node) {
763 final AnchorNode an = (AnchorNode)node;
764 final int len = getCharLengthTree(an.target);
765 switch (returnCode) {
766 case 0:
767 an.charLength = len;
768 break;
769 case GET_CHAR_LEN_VARLEN:
770 throw new SyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
771 case GET_CHAR_LEN_TOP_ALT_VARLEN:
772 if (syntax.differentLengthAltLookBehind()) {
773 return divideLookBehindAlternatives(node);
774 }
775 throw new SyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
776 default:
777 break;
778 }
779 return node;
780 }
781
782 private void nextSetup(final Node nodep, final Node nextNode) {
783 Node node = nodep;
784
785 // retry:
786 retry: while(true) {
787
788 final int type = node.getType();
789 if (type == NodeType.QTFR) {
790 final QuantifierNode qn = (QuantifierNode)node;
791 if (qn.greedy && isRepeatInfinite(qn.upper)) {
792 if (Config.USE_QTFR_PEEK_NEXT) {
793 final StringNode n = (StringNode)getHeadValueNode(nextNode, true);
794 /* '\0': for UTF-16BE etc... */
795 if (n != null && n.chars[n.p] != 0) { // ?????????
796 qn.nextHeadExact = n;
797 }
798 } // USE_QTFR_PEEK_NEXT
799 /* automatic posseivation a*b ==> (?>a*)b */
800 if (qn.lower <= 1) {
801 if (qn.target.isSimple()) {
802 final Node x = getHeadValueNode(qn.target, false);
803 if (x != null) {
804 final Node y = getHeadValueNode(nextNode, false);
805 if (y != null && isNotIncluded(x, y)) {
806 final EncloseNode en = new EncloseNode(EncloseType.STOP_BACKTRACK); //onig_node_new_enclose
807 en.setStopBtSimpleRepeat();
808 //en.setTarget(qn.target); // optimize it ??
809 swap(node, en);
810
811 en.setTarget(node);
812 }
813 }
814 }
815 }
816 }
817 } else if (type == NodeType.ENCLOSE) {
818 final EncloseNode en = (EncloseNode)node;
819 if (en.isMemory()) {
820 node = en.target;
821 // !goto retry;!
822 continue retry;
823 }
824 }
825
826 break;
827 } // while
828 }
829
830 private void updateStringNodeCaseFoldMultiByte(final StringNode sn) {
831 final char[] ch = sn.chars;
832 final int end = sn.end;
833 value = sn.p;
834 int sp = 0;
835 char buf;
836
837 while (value < end) {
838 final int ovalue = value;
839 buf = EncodingHelper.toLowerCase(ch[value++]);
840
841 if (ch[ovalue] != buf) {
842
843 char[] sbuf = new char[sn.length() << 1];
844 System.arraycopy(ch, sn.p, sbuf, 0, ovalue - sn.p);
845 value = ovalue;
846 while (value < end) {
847 buf = EncodingHelper.toLowerCase(ch[value++]);
848 if (sp >= sbuf.length) {
849 final char[]tmp = new char[sbuf.length << 1];
850 System.arraycopy(sbuf, 0, tmp, 0, sbuf.length);
851 sbuf = tmp;
852 }
853 sbuf[sp++] = buf;
854 }
855 sn.set(sbuf, 0, sp);
856 return;
857 }
858 sp++;
859 }
860 }
861
862 private void updateStringNodeCaseFold(final Node node) {
863 final StringNode sn = (StringNode)node;
864 updateStringNodeCaseFoldMultiByte(sn);
865 }
866
867 private Node expandCaseFoldMakeRemString(final char[] ch, final int pp, final int end) {
868 final StringNode node = new StringNode(ch, pp, end);
869
870 updateStringNodeCaseFold(node);
871 node.setAmbig();
872 node.setDontGetOptInfo();
873 return node;
874 }
875
876 private static boolean expandCaseFoldStringAlt(final int itemNum, final char[] items,
877 final char[] chars, final int p, final int slen, final int end, final ObjPtr<Node> node) {
878
879 ConsAltNode altNode;
880 node.p = altNode = newAltNode(null, null);
881
882 StringNode snode = new StringNode(chars, p, p + slen);
883 altNode.setCar(snode);
884
885 for (int i=0; i<itemNum; i++) {
886 snode = new StringNode();
887
888 snode.catCode(items[i]);
889
890 final ConsAltNode an = newAltNode(null, null);
891 an.setCar(snode);
892 altNode.setCdr(an);
893 altNode = an;
894 }
895 return false;
896 }
897
898 private static final int THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION = 8;
899 private Node expandCaseFoldString(final Node node) {
900 final StringNode sn = (StringNode)node;
901
902 if (sn.isAmbig() || sn.length() <= 0) {
903 return node;
904 }
905
906 final char[] chars1 = sn.chars;
907 int pt = sn.p;
908 final int end = sn.end;
909 int altNum = 1;
910
911 ConsAltNode topRoot = null, r = null;
912 @SuppressWarnings("unused")
913 final ObjPtr<Node> prevNode = new ObjPtr<Node>();
914 StringNode stringNode = null;
915
916 while (pt < end) {
917 final char[] items = EncodingHelper.caseFoldCodesByString(regex.caseFoldFlag, chars1[pt]);
918
919 if (items.length == 0) {
920 if (stringNode == null) {
921 if (r == null && prevNode.p != null) {
922 topRoot = r = ConsAltNode.listAdd(null, prevNode.p);
923 }
924
925 prevNode.p = stringNode = new StringNode(); // onig_node_new_str(NULL, NULL);
926
927 if (r != null) {
928 ConsAltNode.listAdd(r, stringNode);
929 }
930
931 }
932
933 stringNode.cat(chars1, pt, pt + 1);
934 } else {
935 altNum *= (items.length + 1);
936 if (altNum > THRESHOLD_CASE_FOLD_ALT_FOR_EXPANSION) {
937 break;
938 }
939
940 if (r == null && prevNode.p != null) {
941 topRoot = r = ConsAltNode.listAdd(null, prevNode.p);
942 }
943
944 expandCaseFoldStringAlt(items.length, items, chars1, pt, 1, end, prevNode);
945 if (r != null) {
946 ConsAltNode.listAdd(r, prevNode.p);
947 }
948 stringNode = null;
949 }
950 pt++;
951 }
952
953 if (pt < end) {
954 final Node srem = expandCaseFoldMakeRemString(chars1, pt, end);
955
956 if (prevNode.p != null && r == null) {
957 topRoot = r = ConsAltNode.listAdd(null, prevNode.p);
958 }
959
960 if (r == null) {
961 prevNode.p = srem;
962 } else {
963 ConsAltNode.listAdd(r, srem);
964 }
965 }
966 /* ending */
967 final Node xnode = topRoot != null ? topRoot : prevNode.p;
968
969 swap(node, xnode);
970 return xnode;
971 }
972
973 private static final int IN_ALT = (1<<0);
974 private static final int IN_NOT = (1<<1);
975 private static final int IN_REPEAT = (1<<2);
976 private static final int IN_VAR_REPEAT = (1<<3);
977 private static final int EXPAND_STRING_MAX_LENGTH = 100;
978
979 /* setup_tree does the following work.
980 1. check empty loop. (set qn->target_empty_info)
981 2. expand ignore-case in char class.
982 3. set memory status bit flags. (reg->mem_stats)
983 4. set qn->head_exact for [push, exact] -> [push_or_jump_exact1, exact].
984 5. find invalid patterns in look-behind.
985 6. expand repeated string.
986 */
987 protected final Node setupTree(final Node nodep, final int statep) {
988 Node node = nodep;
989 int state = statep;
990
991 restart: while (true) {
992 switch (node.getType()) {
993 case NodeType.LIST:
994 ConsAltNode lin = (ConsAltNode)node;
995 Node prev = null;
996 do {
997 setupTree(lin.car, state);
998 if (prev != null) {
999 nextSetup(prev, lin.car);
1000 }
1001 prev = lin.car;
1002 } while ((lin = lin.cdr) != null);
1003 break;
1004
1005 case NodeType.ALT:
1006 ConsAltNode aln = (ConsAltNode)node;
1007 do {
1008 setupTree(aln.car, (state | IN_ALT));
1009 } while ((aln = aln.cdr) != null);
1010 break;
1011
1012 case NodeType.CCLASS:
1013 break;
1014
1015 case NodeType.STR:
1016 if (isIgnoreCase(regex.options) && !((StringNode)node).isRaw()) {
1017 node = expandCaseFoldString(node);
1018 }
1019 break;
1020
1021 case NodeType.CTYPE:
1022 case NodeType.CANY:
1023 break;
1024
1025 case NodeType.BREF:
1026 final BackRefNode br = (BackRefNode)node;
1027 if (br.backRef > env.numMem) {
1028 throw new ValueException(ERR_INVALID_BACKREF);
1029 }
1030 env.backrefedMem = bsOnAt(env.backrefedMem, br.backRef);
1031 env.btMemStart = bsOnAt(env.btMemStart, br.backRef);
1032 ((EncloseNode)env.memNodes[br.backRef]).setMemBackrefed();
1033 break;
1034
1035 case NodeType.QTFR:
1036 final QuantifierNode qn = (QuantifierNode)node;
1037 Node target = qn.target;
1038
1039 if ((state & IN_REPEAT) != 0) {
1040 qn.setInRepeat();
1041 }
1042
1043 if (isRepeatInfinite(qn.upper) || qn.lower >= 1) {
1044 final int d = getMinMatchLength(target);
1045 if (d == 0) {
1046 qn.targetEmptyInfo = TargetInfo.IS_EMPTY;
1047 if (Config.USE_MONOMANIAC_CHECK_CAPTURES_IN_ENDLESS_REPEAT) {
1048 final int info = quantifiersMemoryInfo(target);
1049 if (info > 0) {
1050 qn.targetEmptyInfo = info;
1051 }
1052 } // USE_INFINITE_REPEAT_MONOMANIAC_MEM_STATUS_CHECK
1053 // strange stuff here (turned off)
1054 }
1055 }
1056
1057 state |= IN_REPEAT;
1058 if (qn.lower != qn.upper) {
1059 state |= IN_VAR_REPEAT;
1060 }
1061
1062 target = setupTree(target, state);
1063
1064 /* expand string */
1065 if (target.getType() == NodeType.STR) {
1066 if (!isRepeatInfinite(qn.lower) && qn.lower == qn.upper &&
1067 qn.lower > 1 && qn.lower <= EXPAND_STRING_MAX_LENGTH) {
1068 final StringNode sn = (StringNode)target;
1069 final int len = sn.length();
1070
1071 if (len * qn.lower <= EXPAND_STRING_MAX_LENGTH) {
1072 final StringNode str = qn.convertToString(sn.flag);
1073 final int n = qn.lower;
1074 for (int i = 0; i < n; i++) {
1075 str.cat(sn.chars, sn.p, sn.end);
1076 }
1077 break; /* break case NT_QTFR: */
1078 }
1079
1080 }
1081 }
1082 if (Config.USE_OP_PUSH_OR_JUMP_EXACT) {
1083 if (qn.greedy && qn.targetEmptyInfo != 0) {
1084 if (target.getType() == NodeType.QTFR) {
1085 final QuantifierNode tqn = (QuantifierNode)target;
1086 if (tqn.headExact != null) {
1087 qn.headExact = tqn.headExact;
1088 tqn.headExact = null;
1089 }
1090 } else {
1091 qn.headExact = getHeadValueNode(qn.target, true);
1092 }
1093 }
1094 } // USE_OP_PUSH_OR_JUMP_EXACT
1095 break;
1096
1097 case NodeType.ENCLOSE:
1098 final EncloseNode en = (EncloseNode)node;
1099 switch (en.type) {
1100 case EncloseType.OPTION:
1101 final int options = regex.options;
1102 regex.options = en.option;
1103 setupTree(en.target, state);
1104 regex.options = options;
1105 break;
1106
1107 case EncloseType.MEMORY:
1108 if ((state & (IN_ALT | IN_NOT | IN_VAR_REPEAT)) != 0) {
1109 env.btMemStart = bsOnAt(env.btMemStart, en.regNum);
1110 /* SET_ENCLOSE_STATUS(node, NST_MEM_IN_ALT_NOT); */
1111
1112 }
1113 setupTree(en.target, state);
1114 break;
1115
1116 case EncloseType.STOP_BACKTRACK:
1117 setupTree(en.target, state);
1118 if (en.target.getType() == NodeType.QTFR) {
1119 final QuantifierNode tqn = (QuantifierNode)en.target;
1120 if (isRepeatInfinite(tqn.upper) && tqn.lower <= 1 && tqn.greedy) {
1121 /* (?>a*), a*+ etc... */
1122 if (tqn.target.isSimple()) {
1123 en.setStopBtSimpleRepeat();
1124 }
1125 }
1126 }
1127 break;
1128
1129 default:
1130 break;
1131
1132 } // inner switch
1133 break;
1134
1135 case NodeType.ANCHOR:
1136 final AnchorNode an = (AnchorNode)node;
1137 switch (an.type) {
1138 case AnchorType.PREC_READ:
1139 setupTree(an.target, state);
1140 break;
1141
1142 case AnchorType.PREC_READ_NOT:
1143 setupTree(an.target, (state | IN_NOT));
1144 break;
1145
1146 case AnchorType.LOOK_BEHIND:
1147 if (checkTypeTree(an.target, NodeType.ALLOWED_IN_LB, EncloseType.ALLOWED_IN_LB, AnchorType.ALLOWED_IN_LB)) {
1148 throw new SyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
1149 }
1150 node = setupLookBehind(node);
1151 if (node.getType() != NodeType.ANCHOR) {
1152 continue restart;
1153 }
1154 setupTree(((AnchorNode)node).target, state);
1155 break;
1156
1157 case AnchorType.LOOK_BEHIND_NOT:
1158 if (checkTypeTree(an.target, NodeType.ALLOWED_IN_LB, EncloseType.ALLOWED_IN_LB, AnchorType.ALLOWED_IN_LB)) {
1159 throw new SyntaxException(ERR_INVALID_LOOK_BEHIND_PATTERN);
1160 }
1161 node = setupLookBehind(node);
1162 if (node.getType() != NodeType.ANCHOR) {
1163 continue restart;
1164 }
1165 setupTree(((AnchorNode)node).target, (state | IN_NOT));
1166 break;
1167
1168 default:
1169 break;
1170
1171 } // inner switch
1172 break;
1173 default:
1174 break;
1175 } // switch
1176 return node;
1177 } // restart: while
1178 }
1179
1180 private static final int MAX_NODE_OPT_INFO_REF_COUNT = 5;
1181 private void optimizeNodeLeft(final Node node, final NodeOptInfo opt, final OptEnvironment oenv) { // oenv remove, pass mmd
1182 opt.clear();
1183 opt.setBoundNode(oenv.mmd);
1184
1185 switch (node.getType()) {
1186 case NodeType.LIST: {
1187 final OptEnvironment nenv = new OptEnvironment();
1188 final NodeOptInfo nopt = new NodeOptInfo();
1189 nenv.copy(oenv);
1190 ConsAltNode lin = (ConsAltNode)node;
1191 do {
1192 optimizeNodeLeft(lin.car, nopt, nenv);
1193 nenv.mmd.add(nopt.length);
1194 opt.concatLeftNode(nopt);
1195 } while ((lin = lin.cdr) != null);
1196 break;
1197 }
1198
1199 case NodeType.ALT: {
1200 final NodeOptInfo nopt = new NodeOptInfo();
1201 ConsAltNode aln = (ConsAltNode)node;
1202 do {
1203 optimizeNodeLeft(aln.car, nopt, oenv);
1204 if (aln == node) {
1205 opt.copy(nopt);
1206 } else {
1207 opt.altMerge(nopt, oenv);
1208 }
1209 } while ((aln = aln.cdr) != null);
1210 break;
1211 }
1212
1213 case NodeType.STR: {
1214 final StringNode sn = (StringNode)node;
1215
1216 final int slen = sn.length();
1217
1218 if (!sn.isAmbig()) {
1219 opt.exb.concatStr(sn.chars, sn.p, sn.end, sn.isRaw());
1220
1221 if (slen > 0) {
1222 opt.map.addChar(sn.chars[sn.p]);
1223 }
1224
1225 opt.length.set(slen, slen);
1226 } else {
1227 int max;
1228 if (sn.isDontGetOptInfo()) {
1229 max = sn.length();
1230 } else {
1231 opt.exb.concatStr(sn.chars, sn.p, sn.end, sn.isRaw());
1232 opt.exb.ignoreCase = true;
1233
1234 if (slen > 0) {
1235 opt.map.addCharAmb(sn.chars, sn.p, sn.end, oenv.caseFoldFlag);
1236 }
1237
1238 max = slen;
1239 }
1240 opt.length.set(slen, max);
1241 }
1242
1243 if (opt.exb.length == slen) {
1244 opt.exb.reachEnd = true;
1245 }
1246 break;
1247 }
1248
1249 case NodeType.CCLASS: {
1250 final CClassNode cc = (CClassNode)node;
1251 /* no need to check ignore case. (setted in setup_tree()) */
1252 if (cc.mbuf != null || cc.isNot()) {
1253 opt.length.set(1, 1);
1254 } else {
1255 for (int i=0; i<BitSet.SINGLE_BYTE_SIZE; i++) {
1256 final boolean z = cc.bs.at(i);
1257 if ((z && !cc.isNot()) || (!z && cc.isNot())) {
1258 opt.map.addChar(i);
1259 }
1260 }
1261 opt.length.set(1, 1);
1262 }
1263 break;
1264 }
1265
1266 case NodeType.CANY: {
1267 opt.length.set(1, 1);
1268 break;
1269 }
1270
1271 case NodeType.ANCHOR: {
1272 final AnchorNode an = (AnchorNode)node;
1273 switch (an.type) {
1274 case AnchorType.BEGIN_BUF:
1275 case AnchorType.BEGIN_POSITION:
1276 case AnchorType.BEGIN_LINE:
1277 case AnchorType.END_BUF:
1278 case AnchorType.SEMI_END_BUF:
1279 case AnchorType.END_LINE:
1280 opt.anchor.add(an.type);
1281 break;
1282
1283 case AnchorType.PREC_READ:
1284 final NodeOptInfo nopt = new NodeOptInfo();
1285 optimizeNodeLeft(an.target, nopt, oenv);
1286 if (nopt.exb.length > 0) {
1287 opt.expr.copy(nopt.exb);
1288 } else if (nopt.exm.length > 0) {
1289 opt.expr.copy(nopt.exm);
1290 }
1291 opt.expr.reachEnd = false;
1292 if (nopt.map.value > 0) {
1293 opt.map.copy(nopt.map);
1294 }
1295 break;
1296
1297 case AnchorType.PREC_READ_NOT:
1298 case AnchorType.LOOK_BEHIND: /* Sorry, I can't make use of it. */
1299 case AnchorType.LOOK_BEHIND_NOT:
1300 break;
1301
1302 default:
1303 break;
1304
1305 } // inner switch
1306 break;
1307 }
1308
1309 case NodeType.BREF: {
1310 final BackRefNode br = (BackRefNode)node;
1311
1312 if (br.isRecursion()) {
1313 opt.length.set(0, MinMaxLen.INFINITE_DISTANCE);
1314 break;
1315 }
1316
1317 final Node[]nodes = oenv.scanEnv.memNodes;
1318
1319 final int min = getMinMatchLength(nodes[br.backRef]);
1320 final int max = getMaxMatchLength(nodes[br.backRef]);
1321
1322 opt.length.set(min, max);
1323 break;
1324 }
1325
1326
1327 case NodeType.QTFR: {
1328 final NodeOptInfo nopt = new NodeOptInfo();
1329 final QuantifierNode qn = (QuantifierNode)node;
1330 optimizeNodeLeft(qn.target, nopt, oenv);
1331 if (qn.lower == 0 && isRepeatInfinite(qn.upper)) {
1332 if (oenv.mmd.max == 0 && qn.target.getType() == NodeType.CANY && qn.greedy) {
1333 if (isMultiline(oenv.options)) {
1334 opt.anchor.add(AnchorType.ANYCHAR_STAR_ML);
1335 } else {
1336 opt.anchor.add(AnchorType.ANYCHAR_STAR);
1337 }
1338 }
1339 } else {
1340 if (qn.lower > 0) {
1341 opt.copy(nopt);
1342 if (nopt.exb.length > 0) {
1343 if (nopt.exb.reachEnd) {
1344 int i;
1345 for (i = 2; i <= qn.lower && !opt.exb.isFull(); i++) {
1346 opt.exb.concat(nopt.exb);
1347 }
1348 if (i < qn.lower) {
1349 opt.exb.reachEnd = false;
1350 }
1351 }
1352 }
1353 if (qn.lower != qn.upper) {
1354 opt.exb.reachEnd = false;
1355 opt.exm.reachEnd = false;
1356 }
1357 if (qn.lower > 1) {
1358 opt.exm.reachEnd = false;
1359 }
1360
1361 }
1362 }
1363 final int min = MinMaxLen.distanceMultiply(nopt.length.min, qn.lower);
1364 int max;
1365 if (isRepeatInfinite(qn.upper)) {
1366 max = nopt.length.max > 0 ? MinMaxLen.INFINITE_DISTANCE : 0;
1367 } else {
1368 max = MinMaxLen.distanceMultiply(nopt.length.max, qn.upper);
1369 }
1370 opt.length.set(min, max);
1371 break;
1372 }
1373
1374 case NodeType.ENCLOSE: {
1375 final EncloseNode en = (EncloseNode)node;
1376 switch (en.type) {
1377 case EncloseType.OPTION:
1378 final int save = oenv.options;
1379 oenv.options = en.option;
1380 optimizeNodeLeft(en.target, opt, oenv);
1381 oenv.options = save;
1382 break;
1383
1384 case EncloseType.MEMORY:
1385 if (++en.optCount > MAX_NODE_OPT_INFO_REF_COUNT) {
1386 int min = 0;
1387 int max = MinMaxLen.INFINITE_DISTANCE;
1388 if (en.isMinFixed()) {
1389 min = en.minLength;
1390 }
1391 if (en.isMaxFixed()) {
1392 max = en.maxLength;
1393 }
1394 opt.length.set(min, max);
1395 } else { // USE_SUBEXP_CALL
1396 optimizeNodeLeft(en.target, opt, oenv);
1397 if (opt.anchor.isSet(AnchorType.ANYCHAR_STAR_MASK)) {
1398 if (bsAt(oenv.scanEnv.backrefedMem, en.regNum)) {
1399 opt.anchor.remove(AnchorType.ANYCHAR_STAR_MASK);
1400 }
1401 }
1402 }
1403 break;
1404
1405 case EncloseType.STOP_BACKTRACK:
1406 optimizeNodeLeft(en.target, opt, oenv);
1407 break;
1408
1409 default:
1410 break;
1411 } // inner switch
1412 break;
1413 }
1414
1415 default:
1416 throw new InternalException(ERR_PARSER_BUG);
1417 } // switch
1418 }
1419
1420 @SuppressWarnings("unused")
1421 protected final void setOptimizedInfoFromTree(final Node node) {
1422 final NodeOptInfo opt = new NodeOptInfo();
1423 final OptEnvironment oenv = new OptEnvironment();
1424
1425 oenv.options = regex.options;
1426 oenv.caseFoldFlag = regex.caseFoldFlag;
1427 oenv.scanEnv = env;
1428 oenv.mmd.clear(); // ??
1429
1430 optimizeNodeLeft(node, opt, oenv);
1431
1432 regex.anchor = opt.anchor.leftAnchor & (AnchorType.BEGIN_BUF |
1433 AnchorType.BEGIN_POSITION |
1434 AnchorType.ANYCHAR_STAR |
1435 AnchorType.ANYCHAR_STAR_ML);
1436
1437 regex.anchor |= opt.anchor.rightAnchor & (AnchorType.END_BUF |
1438 AnchorType.SEMI_END_BUF);
1439
1440 if ((regex.anchor & (AnchorType.END_BUF | AnchorType.SEMI_END_BUF)) != 0) {
1441 regex.anchorDmin = opt.length.min;
1442 regex.anchorDmax = opt.length.max;
1443 }
1444
1445 if (opt.exb.length > 0 || opt.exm.length > 0) {
1446 opt.exb.select(opt.exm);
1447 if (opt.map.value > 0 && opt.exb.compare(opt.map) > 0) {
1448 // !goto set_map;!
1449 regex.setOptimizeMapInfo(opt.map);
1450 regex.setSubAnchor(opt.map.anchor);
1451 } else {
1452 regex.setExactInfo(opt.exb);
1453 regex.setSubAnchor(opt.exb.anchor);
1454 }
1455 } else if (opt.map.value > 0) {
1456 // !set_map:!
1457 regex.setOptimizeMapInfo(opt.map);
1458 regex.setSubAnchor(opt.map.anchor);
1459 } else {
1460 regex.subAnchor |= opt.anchor.leftAnchor & AnchorType.BEGIN_LINE;
1461 if (opt.length.max == 0) {
1462 regex.subAnchor |= opt.anchor.rightAnchor & AnchorType.END_LINE;
1463 }
1464 }
1465
1466 if (Config.DEBUG_COMPILE || Config.DEBUG_MATCH) {
1467 Config.log.println(regex.optimizeInfoToString());
1468 }
1469 }
1470 }