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         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 
swap(final Node a, final Node b)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
quantifiersMemoryInfo(final Node node)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 
getMinMatchLength(final Node node)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 
getMaxMatchLength(final Node node)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;
getCharLengthTree(final Node node)376     protected final int getCharLengthTree(final Node node) {
377         return getCharLengthTree(node, 0);
378     }
379 
getCharLengthTree(final Node node, final int levelp)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 */
isNotIncluded(final Node xn, final Node yn)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 
getHeadValueNode(final Node node, final boolean exact)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
checkTypeTree(final Node node, final int typeMask, final int encloseMask, final int anchorMask)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      */
divideLookBehindAlternatives(final Node nodep)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 
setupLookBehind(final Node node)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 
nextSetup(final Node nodep, final Node nextNode)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 
updateStringNodeCaseFoldMultiByte(final StringNode sn)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 
updateStringNodeCaseFold(final Node node)862     private void updateStringNodeCaseFold(final Node node) {
863         final StringNode sn = (StringNode)node;
864         updateStringNodeCaseFoldMultiByte(sn);
865     }
866 
expandCaseFoldMakeRemString(final char[] ch, final int pp, final int end)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 
expandCaseFoldStringAlt(final int itemNum, final char[] items, final char[] chars, final int p, final int slen, final int end, final ObjPtr<Node> node)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;
expandCaseFoldString(final Node node)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     */
setupTree(final Node nodep, final int statep)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;
optimizeNodeLeft(final Node node, final NodeOptInfo opt, final OptEnvironment oenv)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")
setOptimizedInfoFromTree(final Node node)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 }
1471