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