-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
-
24
-
25
-
26
-
27
-
28
-
29
-
30
-
31
-
32
-
33
-
34
-
35
-
36
-
37
-
38
-
39
-
40
-
41
-
42
-
43
-
44
-
45
-
46
-
47
-
48
-
49
-
50
-
51
-
52
-
53
-
54
-
55
-
56
-
57
-
58
-
59
-
60
-
61
-
62
-
63
-
64
-
65
-
66
-
67
-
68
-
69
-
70
-
71
-
72
-
73
-
74
-
75
-
76
-
77
-
78
-
79
-
80
-
81
-
82
-
83
-
84
-
85
-
86
-
87
-
88
-
89
-
90
-
91
-
92
-
93
-
94
-
95
-
96
-
97
-
98
-
99
-
100
-
101
-
102
-
103
-
104
-
105
-
106
-
107
-
108
-
109
-
110
-
111
-
112
-
113
-
114
-
115
-
116
-
117
-
118
-
119
-
120
-
121
-
122
-
123
-
124
-
125
-
126
-
127
-
128
-
129
-
130
-
131
-
132
-
133
-
134
-
135
-
136
-
137
-
138
-
139
-
140
-
141
-
142
-
143
-
144
-
145
-
146
-
147
-
148
-
149
-
150
-
151
-
152
-
153
-
154
-
155
-
156
-
157
-
158
-
159
-
160
-
161
-
162
-
163
-
164
-
165
-
166
-
167
-
168
-
169
-
170
-
171
-
172
-
173
-
174
-
175
-
176
-
177
-
178
-
179
-
180
-
181
-
182
-
183
-
184
-
185
-
186
-
187
-
188
-
189
-
190
-
191
-
192
-
193
-
194
-
195
-
196
-
197
-
198
-
199
-
200
-
201
-
202
-
203
-
204
-
205
-
206
-
207
-
208
-
209
-
210
-
211
-
212
-
213
-
214
-
215
-
216
-
217
-
218
-
219
-
220
-
221
-
222
-
223
-
224
-
225
-
226
-
227
-
228
-
229
-
230
-
231
-
232
-
233
-
234
-
235
-
236
-
237
-
238
-
239
-
240
-
241
-
242
-
243
-
244
-
245
-
246
-
247
-
248
-
249
-
250
-
251
-
252
-
253
-
254
-
255
-
256
-
257
-
258
-
259
-
260
-
261
-
262
-
263
-
264
-
265
-
266
-
267
-
268
-
269
-
270
-
271
-
272
-
273
-
274
-
275
-
276
-
277
-
278
-
279
-
280
-
281
-
282
-
283
-
284
-
285
-
286
-
287
-
288
-
289
-
290
-
291
-
292
-
293
-
294
-
295
-
296
-
297
-
298
-
299
-
300
-
301
-
302
-
303
-
304
-
305
-
306
-
307
-
308
-
309
-
310
-
311
-
312
-
313
-
314
-
315
-
316
-
317
-
318
-
319
-
320
-
321
-
322
-
323
-
324
-
325
-
326
-
327
-
328
-
329
-
330
-
331
-
332
-
333
-
334
-
335
-
336
-
337
-
338
-
339
-
340
-
341
-
342
-
343
-
344
-
345
-
346
-
347
-
348
-
349
-
350
-
351
-
352
-
353
-
354
-
355
-
356
-
357
-
358
-
359
-
360
-
361
-
362
-
363
-
364
-
365
-
366
-
367
-
368
-
369
-
370
-
371
-
372
-
373
-
374
-
375
-
376
-
377
-
378
-
379
-
380
-
381
-
382
-
383
-
384
-
385
-
386
-
387
-
388
-
389
-
390
-
391
-
392
-
393
-
394
-
395
-
396
-
397
-
398
-
399
-
400
-
401
-
402
-
403
-
404
-
405
-
406
-
407
-
408
-
409
-
410
-
411
-
412
-
413
-
414
-
415
-
416
-
417
-
418
-
419
-
420
-
421
-
422
-
423
-
424
-
425
-
426
-
427
-
428
-
429
-
430
-
431
-
432
-
433
-
434
-
435
-
436
-
437
-
438
-
439
-
440
-
441
-
442
-
443
-
444
-
445
-
446
-
447
-
448
-
449
-
450
-
451
-
452
-
453
-
454
-
455
-
456
-
457
-
458
-
459
-
460
-
461
-
462
-
463
-
464
-
465
-
466
-
467
-
468
-
469
-
470
-
471
-
472
-
473
-
474
-
475
-
476
-
477
-
478
-
479
-
480
-
481
-
482
-
483
-
484
-
485
-
486
-
487
-
488
-
489
-
490
-
491
-
492
-
493
-
494
-
495
-
496
-
497
-
498
-
499
-
500
-
501
-
502
-
503
-
504
-
505
-
506
-
507
-
508
-
509
-
510
-
511
-
512
-
513
-
514
-
515
-
516
-
517
-
518
-
519
-
520
-
521
-
522
-
523
-
524
-
525
-
526
-
527
-
528
-
529
-
530
-
531
-
532
-
533
-
534
-
535
-
536
-
537
-
538
-
539
-
540
-
541
-
542
-
543
-
544
-
545
-
546
-
547
-
548
-
549
-
550
-
551
-
552
-
553
-
554
-
555
-
556
-
557
-
558
-
559
-
560
-
561
-
562
-
563
-
564
-
565
-
566
-
567
-
568
-
569
-
570
-
571
-
572
-
573
-
574
-
575
-
576
-
577
-
578
-
579
-
580
-
581
-
582
-
583
-
584
-
585
-
586
-
587
-
588
-
589
-
590
-
591
-
592
-
593
-
594
-
595
-
596
-
597
-
598
-
599
-
600
-
601
-
602
-
603
-
604
-
605
-
606
-
607
-
608
-
609
-
610
-
611
-
612
-
613
-
614
-
615
-
616
-
617
-
618
-
619
-
620
-
621
-
622
-
623
-
624
-
625
-
626
-
627
-
628
-
629
-
630
-
631
-
632
-
633
-
634
-
635
-
636
-
637
-
638
-
639
-
640
-
641
-
642
-
643
-
644
-
645
-
646
-
647
-
648
-
649
-
650
-
651
-
652
-
653
-
654
-
655
-
656
-
657
-
658
-
659
-
660
-
661
-
662
-
663
-
664
-
665
-
666
-
667
-
668
-
669
-
670
-
671
-
672
-
673
-
674
-
675
-
676
-
677
-
678
-
679
-
680
-
681
-
682
-
683
-
684
-
685
-
686
-
687
-
688
-
689
-
690
-
691
-
692
-
693
-
694
-
695
-
696
-
697
-
698
-
699
-
700
-
701
-
702
-
703
-
704
-
705
-
706
-
707
-
708
-
709
-
710
-
711
-
712
-
713
-
714
-
715
-
716
-
717
-
718
-
719
-
720
-
721
-
722
-
723
-
724
-
725
-
726
-
727
-
728
-
729
-
730
-
731
-
732
-
733
-
734
-
735
-
736
-
737
-
738
-
739
-
740
-
741
-
742
-
743
-
744
-
745
-
746
-
747
-
748
-
749
-
750
-
751
-
752
-
753
-
754
-
755
-
756
-
757
-
758
-
759
-
760
-
761
-
762
-
763
-
764
-
765
-
766
-
767
-
768
-
769
-
770
-
771
-
772
-
773
-
774
-
775
-
776
-
777
-
778
-
779
-
780
-
781
-
782
-
783
-
784
-
785
-
786
-
787
-
788
-
789
-
790
-
791
-
792
-
793
-
794
-
795
-
796
-
797
-
798
-
799
-
800
-
801
-
802
-
803
-
804
-
805
-
806
-
807
-
808
-
809
-
810
-
811
-
812
-
813
-
814
-
815
-
816
-
817
-
818
-
819
-
820
-
821
-
822
-
823
-
824
-
825
-
826
-
827
-
828
-
829
-
830
-
831
-
832
-
833
-
834
-
835
-
836
-
837
-
838
-
839
-
840
-
841
-
842
-
843
-
844
-
845
-
846
-
847
-
848
-
849
-
850
-
851
-
852
-
853
-
854
-
855
-
856
-
857
-
858
-
859
-
860
-
861
-
862
-
863
-
864
-
865
-
866
-
867
-
868
-
869
-
870
-
871
-
872
-
873
-
874
-
875
-
876
-
877
-
878
-
879
-
880
-
881
-
882
-
883
-
884
-
885
-
886
-
887
-
888
-
889
-
890
-
891
-
892
-
893
-
894
-
895
-
896
-
897
-
898
-
899
-
900
-
901
-
902
-
903
-
904
-
905
-
906
-
907
-
908
-
909
-
910
-
911
-
912
-
913
-
914
-
915
-
916
-
917
-
918
-
919
-
920
-
921
-
922
-
923
-
924
-
925
-
926
-
927
-
928
-
929
-
930
-
931
-
932
-
933
-
934
-
935
-
936
-
937
-
938
-
939
-
940
-
941
-
942
-
943
-
944
-
945
-
946
-
947
-
948
-
949
-
950
-
951
-
952
-
953
-
954
-
955
-
956
-
957
-
958
-
959
-
960
-
961
-
962
-
963
-
964
-
965
-
966
-
967
-
968
-
969
-
970
-
971
-
972
-
973
-
974
-
975
-
976
-
977
-
978
-
979
-
980
-
981
-
982
-
983
-
984
-
985
-
986
-
987
-
988
-
989
-
990
-
991
-
992
-
993
-
994
-
995
-
996
-
997
-
998
-
999
-
1000
-
1001
-
1002
-
1003
-
1004
-
1005
-
1006
-
1007
-
1008
-
1009
-
1010
-
1011
-
1012
-
1013
-
1014
-
1015
-
1016
-
1017
-
1018
-
1019
-
1020
-
1021
-
1022
-
1023
-
1024
-
1025
-
1026
-
1027
-
1028
-
1029
-
1030
-
1031
-
1032
-
1033
-
1034
-
1035
-
1036
-
1037
-
1038
-
1039
-
1040
-
1041
-
1042
-
1043
-
1044
-
1045
-
1046
-
1047
-
1048
-
1049
-
1050
-
1051
-
1052
-
1053
-
1054
-
1055
-
1056
-
1057
-
1058
-
1059
-
1060
-
1061
-
1062
-
1063
-
1064
-
1065
-
1066
-
1067
-
1068
-
1069
-
1070
-
1071
-
1072
-
1073
-
1074
-
1075
-
1076
-
1077
-
1078
-
1079
-
1080
-
1081
-
1082
-
1083
-
1084
-
1085
-
1086
-
1087
-
1088
-
1089
-
1090
-
1091
-
1092
-
1093
-
1094
-
1095
-
1096
-
1097
-
1098
-
1099
-
1100
-
1101
-
1102
-
1103
-
1104
-
1105
-
1106
-
1107
-
1108
-
1109
-
1110
-
1111
-
1112
-
1113
-
1114
-
1115
-
1116
-
1117
-
1118
-
1119
-
1120
-
1121
-
1122
-
1123
-
1124
-
1125
-
1126
-
1127
-
1128
-
1129
-
1130
-
1131
-
1132
-
1133
-
1134
-
1135
-
1136
-
1137
-
1138
-
1139
-
1140
-
1141
-
1142
-
1143
-
1144
-
1145
-
1146
-
1147
-
1148
-
1149
-
1150
-
1151
-
1152
-
1153
-
1154
-
1155
-
1156
-
1157
-
1158
-
1159
-
1160
-
1161
-
1162
-
1163
-
1164
-
1165
-
1166
-
1167
-
1168
-
1169
-
1170
-
1171
-
1172
-
1173
-
1174
-
1175
-
1176
-
1177
-
1178
-
1179
-
1180
-
1181
-
1182
-
1183
-
1184
-
1185
-
1186
-
1187
-
1188
-
1189
-
1190
-
1191
-
1192
-
1193
-
1194
-
1195
-
1196
-
1197
-
1198
-
1199
-
1200
-
1201
-
1202
-
1203
-
1204
-
1205
-
1206
-
1207
-
1208
-
1209
-
1210
-
1211
-
1212
-
1213
-
1214
-
1215
-
1216
-
1217
-
1218
-
1219
-
1220
-
1221
-
1222
-
1223
-
1224
-
1225
-
1226
-
1227
-
1228
-
1229
-
1230
-
1231
-
1232
-
1233
-
1234
-
1235
-
1236
-
1237
-
1238
-
1239
-
1240
-
1241
-
1242
-
1243
-
1244
-
1245
-
1246
-
1247
-
1248
-
1249
-
1250
-
1251
-
1252
-
1253
-
1254
-
1255
-
1256
-
1257
-
1258
-
1259
-
1260
-
1261
-
1262
-
1263
-
1264
-
1265
-
1266
-
1267
-
1268
-
1269
-
1270
-
1271
-
1272
-
1273
-
1274
-
1275
-
1276
-
1277
-
1278
-
1279
-
1280
-
1281
-
1282
-
1283
-
1284
-
1285
-
1286
-
1287
-
1288
-
1289
-
1290
-
1291
-
1292
-
1293
-
1294
-
1295
-
1296
-
1297
-
1298
-
1299
-
1300
-
1301
-
1302
-
1303
-
1304
-
1305
-
1306
-
1307
-
1308
-
1309
-
1310
-
1311
-
1312
-
1313
-
1314
-
1315
-
1316
-
1317
-
1318
-
1319
-
1320
-
1321
-
1322
-
1323
-
1324
-
1325
-
1326
-
1327
-
1328
-
1329
-
1330
-
1331
-
1332
-
1333
-
1334
-
1335
-
1336
-
1337
-
1338
-
1339
-
1340
-
1341
-
1342
-
1343
-
1344
-
1345
-
1346
-
1347
-
1348
-
1349
-
1350
-
1351
-
1352
-
1353
-
1354
-
1355
-
1356
-
1357
-
1358
-
1359
-
1360
-
1361
-
1362
-
1363
-
1364
-
1365
-
1366
-
1367
-
1368
-
1369
-
1370
-
1371
-
1372
-
1373
-
1374
-
1375
-
1376
-
1377
-
1378
-
1379
-
1380
-
1381
-
1382
-
1383
-
1384
-
1385
-
1386
-
1387
-
1388
-
1389
-
1390
-
1391
-
1392
-
1393
-
1394
-
1395
-
1396
-
1397
-
1398
-
1399
-
1400
-
1401
-
1402
-
1403
-
1404
-
1405
-
1406
-
1407
-
1408
-
1409
-
1410
-
1411
-
1412
-
1413
-
1414
-
1415
-
1416
-
1417
-
1418
-
1419
-
1420
-
1421
-
1422
-
1423
-
1424
-
1425
-
1426
-
1427
-
1428
-
1429
-
1430
-
1431
-
1432
-
1433
-
1434
-
1435
-
1436
-
1437
-
1438
-
1439
-
1440
-
1441
-
1442
-
1443
-
1444
-
1445
-
1446
-
1447
-
1448
-
1449
-
1450
-
1451
-
1452
-
1453
-
1454
-
1455
-
1456
-
1457
-
1458
-
1459
-
1460
-
1461
-
1462
-
1463
-
1464
-
1465
-
1466
-
1467
-
1468
-
1469
-
1470
-
1471
-
1472
-
1473
-
1474
-
1475
-
1476
-
1477
-
1478
-
1479
-
1480
-
1481
-
1482
-
1483
-
1484
-
1485
-
1486
-
1487
-
1488
-
1489
-
1490
-
1491
-
1492
-
1493
-
1494
-
1495
-
1496
-
1497
-
1498
-
1499
-
1500
-
1501
-
1502
-
1503
-
1504
-
1505
-
1506
-
1507
-
1508
-
1509
-
1510
-
1511
-
1512
-
1513
-
1514
-
1515
-
1516
-
1517
-
1518
-
1519
-
1520
-
1521
-
1522
-
1523
-
1524
-
1525
-
1526
-
1527
-
1528
-
1529
-
1530
-
1531
-
1532
-
1533
-
1534
-
1535
-
1536
-
1537
-
1538
-
1539
-
1540
-
1541
-
1542
-
1543
-
1544
-
1545
-
1546
-
1547
-
1548
-
1549
-
1550
-
1551
-
1552
-
1553
-
1554
-
1555
-
1556
-
1557
-
1558
-
1559
-
1560
-
1561
-
1562
-
1563
-
1564
-
1565
-
1566
-
1567
-
1568
-
1569
-
1570
-
1571
-
1572
-
1573
-
1574
-
1575
-
1576
-
1577
-
1578
-
1579
-
1580
-
1581
-
1582
-
1583
-
1584
-
1585
-
1586
-
1587
-
1588
-
1589
-
1590
-
1591
-
1592
-
1593
-
1594
-
1595
-
1596
-
1597
-
1598
-
1599
-
1600
-
1601
-
1602
-
1603
-
1604
-
1605
-
1606
-
1607
-
1608
-
1609
-
1610
-
1611
-
1612
-
1613
-
1614
-
1615
-
1616
-
1617
-
1618
-
1619
-
1620
-
1621
-
1622
-
1623
-
1624
-
1625
-
1626
-
1627
-
1628
-
1629
-
1630
-
1631
-
1632
-
1633
-
1634
package regexp2
import (
"bytes"
"errors"
"fmt"
"math"
"strconv"
"strings"
"time"
"unicode"
"github.com/dlclark/regexp2/syntax"
)
type runner struct {
re *Regexp
code *syntax.Code
runtextstart int // starting point for search
runtext []rune // text to search
runtextpos int // current position in text
runtextend int
// The backtracking stack. Opcodes use this to store data regarding
// what they have matched and where to backtrack to. Each "frame" on
// the stack takes the form of [CodePosition Data1 Data2...], where
// CodePosition is the position of the current opcode and
// the data values are all optional. The CodePosition can be negative, and
// these values (also called "back2") are used by the BranchMark family of opcodes
// to indicate whether they are backtracking after a successful or failed
// match.
// When we backtrack, we pop the CodePosition off the stack, set the current
// instruction pointer to that code position, and mark the opcode
// with a backtracking flag ("Back"). Each opcode then knows how to
// handle its own data.
runtrack []int
runtrackpos int
// This stack is used to track text positions across different opcodes.
// For example, in /(a*b)+/, the parentheses result in a SetMark/CaptureMark
// pair. SetMark records the text position before we match a*b. Then
// CaptureMark uses that position to figure out where the capture starts.
// Opcodes which push onto this stack are always paired with other opcodes
// which will pop the value from it later. A successful match should mean
// that this stack is empty.
runstack []int
runstackpos int
// The crawl stack is used to keep track of captures. Every time a group
// has a capture, we push its group number onto the runcrawl stack. In
// the case of a balanced match, we push BOTH groups onto the stack.
runcrawl []int
runcrawlpos int
runtrackcount int // count of states that may do backtracking
runmatch *Match // result object
ignoreTimeout bool
timeout time.Duration // timeout in milliseconds (needed for actual)
timeoutChecksToSkip int
timeoutAt time.Time
operator syntax.InstOp
codepos int
rightToLeft bool
caseInsensitive bool
}
// run searches for matches and can continue from the previous match
//
// quick is usually false, but can be true to not return matches, just put it in caches
// textstart is -1 to start at the "beginning" (depending on Right-To-Left), otherwise an index in input
// input is the string to search for our regex pattern
func (re *Regexp) run(quick bool, textstart int, input []rune) (*Match, error) {
// get a cached runner
runner := re.getRunner()
defer re.putRunner(runner)
if textstart < 0 {
if re.RightToLeft() {
textstart = len(input)
} else {
textstart = 0
}
}
return runner.scan(input, textstart, quick, re.MatchTimeout)
}
// Scans the string to find the first match. Uses the Match object
// both to feed text in and as a place to store matches that come out.
//
// All the action is in the Go() method. Our
// responsibility is to load up the class members before
// calling Go.
//
// The optimizer can compute a set of candidate starting characters,
// and we could use a separate method Skip() that will quickly scan past
// any characters that we know can't match.
func (r *runner) scan(rt []rune, textstart int, quick bool, timeout time.Duration) (*Match, error) {
r.timeout = timeout
r.ignoreTimeout = (time.Duration(math.MaxInt64) == timeout)
r.runtextstart = textstart
r.runtext = rt
r.runtextend = len(rt)
stoppos := r.runtextend
bump := 1
if r.re.RightToLeft() {
bump = -1
stoppos = 0
}
r.runtextpos = textstart
initted := false
r.startTimeoutWatch()
for {
if r.re.Debug() {
//fmt.Printf("\nSearch content: %v\n", string(r.runtext))
fmt.Printf("\nSearch range: from 0 to %v\n", r.runtextend)
fmt.Printf("Firstchar search starting at %v stopping at %v\n", r.runtextpos, stoppos)
}
if r.findFirstChar() {
if err := r.checkTimeout(); err != nil {
return nil, err
}
if !initted {
r.initMatch()
initted = true
}
if r.re.Debug() {
fmt.Printf("Executing engine starting at %v\n\n", r.runtextpos)
}
if err := r.execute(); err != nil {
return nil, err
}
if r.runmatch.matchcount[0] > 0 {
// We'll return a match even if it touches a previous empty match
return r.tidyMatch(quick), nil
}
// reset state for another go
r.runtrackpos = len(r.runtrack)
r.runstackpos = len(r.runstack)
r.runcrawlpos = len(r.runcrawl)
}
// failure!
if r.runtextpos == stoppos {
r.tidyMatch(true)
return nil, nil
}
// Recognize leading []* and various anchors, and bump on failure accordingly
// r.bump by one and start again
r.runtextpos += bump
}
// We never get here
}
func (r *runner) execute() error {
r.goTo(0)
for {
if r.re.Debug() {
r.dumpState()
}
if err := r.checkTimeout(); err != nil {
return err
}
switch r.operator {
case syntax.Stop:
return nil
case syntax.Nothing:
break
case syntax.Goto:
r.goTo(r.operand(0))
continue
case syntax.Testref:
if !r.runmatch.isMatched(r.operand(0)) {
break
}
r.advance(1)
continue
case syntax.Lazybranch:
r.trackPush1(r.textPos())
r.advance(1)
continue
case syntax.Lazybranch | syntax.Back:
r.trackPop()
r.textto(r.trackPeek())
r.goTo(r.operand(0))
continue
case syntax.Setmark:
r.stackPush(r.textPos())
r.trackPush()
r.advance(0)
continue
case syntax.Nullmark:
r.stackPush(-1)
r.trackPush()
r.advance(0)
continue
case syntax.Setmark | syntax.Back, syntax.Nullmark | syntax.Back:
r.stackPop()
break
case syntax.Getmark:
r.stackPop()
r.trackPush1(r.stackPeek())
r.textto(r.stackPeek())
r.advance(0)
continue
case syntax.Getmark | syntax.Back:
r.trackPop()
r.stackPush(r.trackPeek())
break
case syntax.Capturemark:
if r.operand(1) != -1 && !r.runmatch.isMatched(r.operand(1)) {
break
}
r.stackPop()
if r.operand(1) != -1 {
r.transferCapture(r.operand(0), r.operand(1), r.stackPeek(), r.textPos())
} else {
r.capture(r.operand(0), r.stackPeek(), r.textPos())
}
r.trackPush1(r.stackPeek())
r.advance(2)
continue
case syntax.Capturemark | syntax.Back:
r.trackPop()
r.stackPush(r.trackPeek())
r.uncapture()
if r.operand(0) != -1 && r.operand(1) != -1 {
r.uncapture()
}
break
case syntax.Branchmark:
r.stackPop()
matched := r.textPos() - r.stackPeek()
if matched != 0 { // Nonempty match -> loop now
r.trackPush2(r.stackPeek(), r.textPos()) // Save old mark, textpos
r.stackPush(r.textPos()) // Make new mark
r.goTo(r.operand(0)) // Loop
} else { // Empty match -> straight now
r.trackPushNeg1(r.stackPeek()) // Save old mark
r.advance(1) // Straight
}
continue
case syntax.Branchmark | syntax.Back:
r.trackPopN(2)
r.stackPop()
r.textto(r.trackPeekN(1)) // Recall position
r.trackPushNeg1(r.trackPeek()) // Save old mark
r.advance(1) // Straight
continue
case syntax.Branchmark | syntax.Back2:
r.trackPop()
r.stackPush(r.trackPeek()) // Recall old mark
break // Backtrack
case syntax.Lazybranchmark:
{
// We hit this the first time through a lazy loop and after each
// successful match of the inner expression. It simply continues
// on and doesn't loop.
r.stackPop()
oldMarkPos := r.stackPeek()
if r.textPos() != oldMarkPos { // Nonempty match -> try to loop again by going to 'back' state
if oldMarkPos != -1 {
r.trackPush2(oldMarkPos, r.textPos()) // Save old mark, textpos
} else {
r.trackPush2(r.textPos(), r.textPos())
}
} else {
// The inner expression found an empty match, so we'll go directly to 'back2' if we
// backtrack. In this case, we need to push something on the stack, since back2 pops.
// However, in the case of ()+? or similar, this empty match may be legitimate, so push the text
// position associated with that empty match.
r.stackPush(oldMarkPos)
r.trackPushNeg1(r.stackPeek()) // Save old mark
}
r.advance(1)
continue
}
case syntax.Lazybranchmark | syntax.Back:
// After the first time, Lazybranchmark | syntax.Back occurs
// with each iteration of the loop, and therefore with every attempted
// match of the inner expression. We'll try to match the inner expression,
// then go back to Lazybranchmark if successful. If the inner expression
// fails, we go to Lazybranchmark | syntax.Back2
r.trackPopN(2)
pos := r.trackPeekN(1)
r.trackPushNeg1(r.trackPeek()) // Save old mark
r.stackPush(pos) // Make new mark
r.textto(pos) // Recall position
r.goTo(r.operand(0)) // Loop
continue
case syntax.Lazybranchmark | syntax.Back2:
// The lazy loop has failed. We'll do a true backtrack and
// start over before the lazy loop.
r.stackPop()
r.trackPop()
r.stackPush(r.trackPeek()) // Recall old mark
break
case syntax.Setcount:
r.stackPush2(r.textPos(), r.operand(0))
r.trackPush()
r.advance(1)
continue
case syntax.Nullcount:
r.stackPush2(-1, r.operand(0))
r.trackPush()
r.advance(1)
continue
case syntax.Setcount | syntax.Back:
r.stackPopN(2)
break
case syntax.Nullcount | syntax.Back:
r.stackPopN(2)
break
case syntax.Branchcount:
// r.stackPush:
// 0: Mark
// 1: Count
r.stackPopN(2)
mark := r.stackPeek()
count := r.stackPeekN(1)
matched := r.textPos() - mark
if count >= r.operand(1) || (matched == 0 && count >= 0) { // Max loops or empty match -> straight now
r.trackPushNeg2(mark, count) // Save old mark, count
r.advance(2) // Straight
} else { // Nonempty match -> count+loop now
r.trackPush1(mark) // remember mark
r.stackPush2(r.textPos(), count+1) // Make new mark, incr count
r.goTo(r.operand(0)) // Loop
}
continue
case syntax.Branchcount | syntax.Back:
// r.trackPush:
// 0: Previous mark
// r.stackPush:
// 0: Mark (= current pos, discarded)
// 1: Count
r.trackPop()
r.stackPopN(2)
if r.stackPeekN(1) > 0 { // Positive -> can go straight
r.textto(r.stackPeek()) // Zap to mark
r.trackPushNeg2(r.trackPeek(), r.stackPeekN(1)-1) // Save old mark, old count
r.advance(2) // Straight
continue
}
r.stackPush2(r.trackPeek(), r.stackPeekN(1)-1) // recall old mark, old count
break
case syntax.Branchcount | syntax.Back2:
// r.trackPush:
// 0: Previous mark
// 1: Previous count
r.trackPopN(2)
r.stackPush2(r.trackPeek(), r.trackPeekN(1)) // Recall old mark, old count
break // Backtrack
case syntax.Lazybranchcount:
// r.stackPush:
// 0: Mark
// 1: Count
r.stackPopN(2)
mark := r.stackPeek()
count := r.stackPeekN(1)
if count < 0 { // Negative count -> loop now
r.trackPushNeg1(mark) // Save old mark
r.stackPush2(r.textPos(), count+1) // Make new mark, incr count
r.goTo(r.operand(0)) // Loop
} else { // Nonneg count -> straight now
r.trackPush3(mark, count, r.textPos()) // Save mark, count, position
r.advance(2) // Straight
}
continue
case syntax.Lazybranchcount | syntax.Back:
// r.trackPush:
// 0: Mark
// 1: Count
// 2: r.textPos
r.trackPopN(3)
mark := r.trackPeek()
textpos := r.trackPeekN(2)
if r.trackPeekN(1) < r.operand(1) && textpos != mark { // Under limit and not empty match -> loop
r.textto(textpos) // Recall position
r.stackPush2(textpos, r.trackPeekN(1)+1) // Make new mark, incr count
r.trackPushNeg1(mark) // Save old mark
r.goTo(r.operand(0)) // Loop
continue
} else { // Max loops or empty match -> backtrack
r.stackPush2(r.trackPeek(), r.trackPeekN(1)) // Recall old mark, count
break // backtrack
}
case syntax.Lazybranchcount | syntax.Back2:
// r.trackPush:
// 0: Previous mark
// r.stackPush:
// 0: Mark (== current pos, discarded)
// 1: Count
r.trackPop()
r.stackPopN(2)
r.stackPush2(r.trackPeek(), r.stackPeekN(1)-1) // Recall old mark, count
break // Backtrack
case syntax.Setjump:
r.stackPush2(r.trackpos(), r.crawlpos())
r.trackPush()
r.advance(0)
continue
case syntax.Setjump | syntax.Back:
r.stackPopN(2)
break
case syntax.Backjump:
// r.stackPush:
// 0: Saved trackpos
// 1: r.crawlpos
r.stackPopN(2)
r.trackto(r.stackPeek())
for r.crawlpos() != r.stackPeekN(1) {
r.uncapture()
}
break
case syntax.Forejump:
// r.stackPush:
// 0: Saved trackpos
// 1: r.crawlpos
r.stackPopN(2)
r.trackto(r.stackPeek())
r.trackPush1(r.stackPeekN(1))
r.advance(0)
continue
case syntax.Forejump | syntax.Back:
// r.trackPush:
// 0: r.crawlpos
r.trackPop()
for r.crawlpos() != r.trackPeek() {
r.uncapture()
}
break
case syntax.Bol:
if r.leftchars() > 0 && r.charAt(r.textPos()-1) != '\n' {
break
}
r.advance(0)
continue
case syntax.Eol:
if r.rightchars() > 0 && r.charAt(r.textPos()) != '\n' {
break
}
r.advance(0)
continue
case syntax.Boundary:
if !r.isBoundary(r.textPos(), 0, r.runtextend) {
break
}
r.advance(0)
continue
case syntax.Nonboundary:
if r.isBoundary(r.textPos(), 0, r.runtextend) {
break
}
r.advance(0)
continue
case syntax.ECMABoundary:
if !r.isECMABoundary(r.textPos(), 0, r.runtextend) {
break
}
r.advance(0)
continue
case syntax.NonECMABoundary:
if r.isECMABoundary(r.textPos(), 0, r.runtextend) {
break
}
r.advance(0)
continue
case syntax.Beginning:
if r.leftchars() > 0 {
break
}
r.advance(0)
continue
case syntax.Start:
if r.textPos() != r.textstart() {
break
}
r.advance(0)
continue
case syntax.EndZ:
rchars := r.rightchars()
if rchars > 1 {
break
}
// RE2 and EcmaScript define $ as "asserts position at the end of the string"
// PCRE/.NET adds "or before the line terminator right at the end of the string (if any)"
if (r.re.options & (RE2 | ECMAScript)) != 0 {
// RE2/Ecmascript mode
if rchars > 0 {
break
}
} else if rchars == 1 && r.charAt(r.textPos()) != '\n' {
// "regular" mode
break
}
r.advance(0)
continue
case syntax.End:
if r.rightchars() > 0 {
break
}
r.advance(0)
continue
case syntax.One:
if r.forwardchars() < 1 || r.forwardcharnext() != rune(r.operand(0)) {
break
}
r.advance(1)
continue
case syntax.Notone:
if r.forwardchars() < 1 || r.forwardcharnext() == rune(r.operand(0)) {
break
}
r.advance(1)
continue
case syntax.Set:
if r.forwardchars() < 1 || !r.code.Sets[r.operand(0)].CharIn(r.forwardcharnext()) {
break
}
r.advance(1)
continue
case syntax.Multi:
if !r.runematch(r.code.Strings[r.operand(0)]) {
break
}
r.advance(1)
continue
case syntax.Ref:
capnum := r.operand(0)
if r.runmatch.isMatched(capnum) {
if !r.refmatch(r.runmatch.matchIndex(capnum), r.runmatch.matchLength(capnum)) {
break
}
} else {
if (r.re.options & ECMAScript) == 0 {
break
}
}
r.advance(1)
continue
case syntax.Onerep:
c := r.operand(1)
if r.forwardchars() < c {
break
}
ch := rune(r.operand(0))
for c > 0 {
if r.forwardcharnext() != ch {
goto BreakBackward
}
c--
}
r.advance(2)
continue
case syntax.Notonerep:
c := r.operand(1)
if r.forwardchars() < c {
break
}
ch := rune(r.operand(0))
for c > 0 {
if r.forwardcharnext() == ch {
goto BreakBackward
}
c--
}
r.advance(2)
continue
case syntax.Setrep:
c := r.operand(1)
if r.forwardchars() < c {
break
}
set := r.code.Sets[r.operand(0)]
for c > 0 {
if !set.CharIn(r.forwardcharnext()) {
goto BreakBackward
}
c--
}
r.advance(2)
continue
case syntax.Oneloop:
c := r.operand(1)
if c > r.forwardchars() {
c = r.forwardchars()
}
ch := rune(r.operand(0))
i := c
for ; i > 0; i-- {
if r.forwardcharnext() != ch {
r.backwardnext()
break
}
}
if c > i {
r.trackPush2(c-i-1, r.textPos()-r.bump())
}
r.advance(2)
continue
case syntax.Notoneloop:
c := r.operand(1)
if c > r.forwardchars() {
c = r.forwardchars()
}
ch := rune(r.operand(0))
i := c
for ; i > 0; i-- {
if r.forwardcharnext() == ch {
r.backwardnext()
break
}
}
if c > i {
r.trackPush2(c-i-1, r.textPos()-r.bump())
}
r.advance(2)
continue
case syntax.Setloop:
c := r.operand(1)
if c > r.forwardchars() {
c = r.forwardchars()
}
set := r.code.Sets[r.operand(0)]
i := c
for ; i > 0; i-- {
if !set.CharIn(r.forwardcharnext()) {
r.backwardnext()
break
}
}
if c > i {
r.trackPush2(c-i-1, r.textPos()-r.bump())
}
r.advance(2)
continue
case syntax.Oneloop | syntax.Back, syntax.Notoneloop | syntax.Back:
r.trackPopN(2)
i := r.trackPeek()
pos := r.trackPeekN(1)
r.textto(pos)
if i > 0 {
r.trackPush2(i-1, pos-r.bump())
}
r.advance(2)
continue
case syntax.Setloop | syntax.Back:
r.trackPopN(2)
i := r.trackPeek()
pos := r.trackPeekN(1)
r.textto(pos)
if i > 0 {
r.trackPush2(i-1, pos-r.bump())
}
r.advance(2)
continue
case syntax.Onelazy, syntax.Notonelazy:
c := r.operand(1)
if c > r.forwardchars() {
c = r.forwardchars()
}
if c > 0 {
r.trackPush2(c-1, r.textPos())
}
r.advance(2)
continue
case syntax.Setlazy:
c := r.operand(1)
if c > r.forwardchars() {
c = r.forwardchars()
}
if c > 0 {
r.trackPush2(c-1, r.textPos())
}
r.advance(2)
continue
case syntax.Onelazy | syntax.Back:
r.trackPopN(2)
pos := r.trackPeekN(1)
r.textto(pos)
if r.forwardcharnext() != rune(r.operand(0)) {
break
}
i := r.trackPeek()
if i > 0 {
r.trackPush2(i-1, pos+r.bump())
}
r.advance(2)
continue
case syntax.Notonelazy | syntax.Back:
r.trackPopN(2)
pos := r.trackPeekN(1)
r.textto(pos)
if r.forwardcharnext() == rune(r.operand(0)) {
break
}
i := r.trackPeek()
if i > 0 {
r.trackPush2(i-1, pos+r.bump())
}
r.advance(2)
continue
case syntax.Setlazy | syntax.Back:
r.trackPopN(2)
pos := r.trackPeekN(1)
r.textto(pos)
if !r.code.Sets[r.operand(0)].CharIn(r.forwardcharnext()) {
break
}
i := r.trackPeek()
if i > 0 {
r.trackPush2(i-1, pos+r.bump())
}
r.advance(2)
continue
default:
return errors.New("unknown state in regex runner")
}
BreakBackward:
;
// "break Backward" comes here:
r.backtrack()
}
}
// increase the size of stack and track storage
func (r *runner) ensureStorage() {
if r.runstackpos < r.runtrackcount*4 {
doubleIntSlice(&r.runstack, &r.runstackpos)
}
if r.runtrackpos < r.runtrackcount*4 {
doubleIntSlice(&r.runtrack, &r.runtrackpos)
}
}
func doubleIntSlice(s *[]int, pos *int) {
oldLen := len(*s)
newS := make([]int, oldLen*2)
copy(newS[oldLen:], *s)
*pos += oldLen
*s = newS
}
// Save a number on the longjump unrolling stack
func (r *runner) crawl(i int) {
if r.runcrawlpos == 0 {
doubleIntSlice(&r.runcrawl, &r.runcrawlpos)
}
r.runcrawlpos--
r.runcrawl[r.runcrawlpos] = i
}
// Remove a number from the longjump unrolling stack
func (r *runner) popcrawl() int {
val := r.runcrawl[r.runcrawlpos]
r.runcrawlpos++
return val
}
// Get the height of the stack
func (r *runner) crawlpos() int {
return len(r.runcrawl) - r.runcrawlpos
}
func (r *runner) advance(i int) {
r.codepos += (i + 1)
r.setOperator(r.code.Codes[r.codepos])
}
func (r *runner) goTo(newpos int) {
// when branching backward or in place, ensure storage
if newpos <= r.codepos {
r.ensureStorage()
}
r.setOperator(r.code.Codes[newpos])
r.codepos = newpos
}
func (r *runner) textto(newpos int) {
r.runtextpos = newpos
}
func (r *runner) trackto(newpos int) {
r.runtrackpos = len(r.runtrack) - newpos
}
func (r *runner) textstart() int {
return r.runtextstart
}
func (r *runner) textPos() int {
return r.runtextpos
}
// push onto the backtracking stack
func (r *runner) trackpos() int {
return len(r.runtrack) - r.runtrackpos
}
func (r *runner) trackPush() {
r.runtrackpos--
r.runtrack[r.runtrackpos] = r.codepos
}
func (r *runner) trackPush1(I1 int) {
r.runtrackpos--
r.runtrack[r.runtrackpos] = I1
r.runtrackpos--
r.runtrack[r.runtrackpos] = r.codepos
}
func (r *runner) trackPush2(I1, I2 int) {
r.runtrackpos--
r.runtrack[r.runtrackpos] = I1
r.runtrackpos--
r.runtrack[r.runtrackpos] = I2
r.runtrackpos--
r.runtrack[r.runtrackpos] = r.codepos
}
func (r *runner) trackPush3(I1, I2, I3 int) {
r.runtrackpos--
r.runtrack[r.runtrackpos] = I1
r.runtrackpos--
r.runtrack[r.runtrackpos] = I2
r.runtrackpos--
r.runtrack[r.runtrackpos] = I3
r.runtrackpos--
r.runtrack[r.runtrackpos] = r.codepos
}
func (r *runner) trackPushNeg1(I1 int) {
r.runtrackpos--
r.runtrack[r.runtrackpos] = I1
r.runtrackpos--
r.runtrack[r.runtrackpos] = -r.codepos
}
func (r *runner) trackPushNeg2(I1, I2 int) {
r.runtrackpos--
r.runtrack[r.runtrackpos] = I1
r.runtrackpos--
r.runtrack[r.runtrackpos] = I2
r.runtrackpos--
r.runtrack[r.runtrackpos] = -r.codepos
}
func (r *runner) backtrack() {
newpos := r.runtrack[r.runtrackpos]
r.runtrackpos++
if r.re.Debug() {
if newpos < 0 {
fmt.Printf(" Backtracking (back2) to code position %v\n", -newpos)
} else {
fmt.Printf(" Backtracking to code position %v\n", newpos)
}
}
if newpos < 0 {
newpos = -newpos
r.setOperator(r.code.Codes[newpos] | syntax.Back2)
} else {
r.setOperator(r.code.Codes[newpos] | syntax.Back)
}
// When branching backward, ensure storage
if newpos < r.codepos {
r.ensureStorage()
}
r.codepos = newpos
}
func (r *runner) setOperator(op int) {
r.caseInsensitive = (0 != (op & syntax.Ci))
r.rightToLeft = (0 != (op & syntax.Rtl))
r.operator = syntax.InstOp(op & ^(syntax.Rtl | syntax.Ci))
}
func (r *runner) trackPop() {
r.runtrackpos++
}
// pop framesize items from the backtracking stack
func (r *runner) trackPopN(framesize int) {
r.runtrackpos += framesize
}
// Technically we are actually peeking at items already popped. So if you want to
// get and pop the top item from the stack, you do
// r.trackPop();
// r.trackPeek();
func (r *runner) trackPeek() int {
return r.runtrack[r.runtrackpos-1]
}
// get the ith element down on the backtracking stack
func (r *runner) trackPeekN(i int) int {
return r.runtrack[r.runtrackpos-i-1]
}
// Push onto the grouping stack
func (r *runner) stackPush(I1 int) {
r.runstackpos--
r.runstack[r.runstackpos] = I1
}
func (r *runner) stackPush2(I1, I2 int) {
r.runstackpos--
r.runstack[r.runstackpos] = I1
r.runstackpos--
r.runstack[r.runstackpos] = I2
}
func (r *runner) stackPop() {
r.runstackpos++
}
// pop framesize items from the grouping stack
func (r *runner) stackPopN(framesize int) {
r.runstackpos += framesize
}
// Technically we are actually peeking at items already popped. So if you want to
// get and pop the top item from the stack, you do
// r.stackPop();
// r.stackPeek();
func (r *runner) stackPeek() int {
return r.runstack[r.runstackpos-1]
}
// get the ith element down on the grouping stack
func (r *runner) stackPeekN(i int) int {
return r.runstack[r.runstackpos-i-1]
}
func (r *runner) operand(i int) int {
return r.code.Codes[r.codepos+i+1]
}
func (r *runner) leftchars() int {
return r.runtextpos
}
func (r *runner) rightchars() int {
return r.runtextend - r.runtextpos
}
func (r *runner) bump() int {
if r.rightToLeft {
return -1
}
return 1
}
func (r *runner) forwardchars() int {
if r.rightToLeft {
return r.runtextpos
}
return r.runtextend - r.runtextpos
}
func (r *runner) forwardcharnext() rune {
var ch rune
if r.rightToLeft {
r.runtextpos--
ch = r.runtext[r.runtextpos]
} else {
ch = r.runtext[r.runtextpos]
r.runtextpos++
}
if r.caseInsensitive {
return unicode.ToLower(ch)
}
return ch
}
func (r *runner) runematch(str []rune) bool {
var pos int
c := len(str)
if !r.rightToLeft {
if r.runtextend-r.runtextpos < c {
return false
}
pos = r.runtextpos + c
} else {
if r.runtextpos-0 < c {
return false
}
pos = r.runtextpos
}
if !r.caseInsensitive {
for c != 0 {
c--
pos--
if str[c] != r.runtext[pos] {
return false
}
}
} else {
for c != 0 {
c--
pos--
if str[c] != unicode.ToLower(r.runtext[pos]) {
return false
}
}
}
if !r.rightToLeft {
pos += len(str)
}
r.runtextpos = pos
return true
}
func (r *runner) refmatch(index, len int) bool {
var c, pos, cmpos int
if !r.rightToLeft {
if r.runtextend-r.runtextpos < len {
return false
}
pos = r.runtextpos + len
} else {
if r.runtextpos-0 < len {
return false
}
pos = r.runtextpos
}
cmpos = index + len
c = len
if !r.caseInsensitive {
for c != 0 {
c--
cmpos--
pos--
if r.runtext[cmpos] != r.runtext[pos] {
return false
}
}
} else {
for c != 0 {
c--
cmpos--
pos--
if unicode.ToLower(r.runtext[cmpos]) != unicode.ToLower(r.runtext[pos]) {
return false
}
}
}
if !r.rightToLeft {
pos += len
}
r.runtextpos = pos
return true
}
func (r *runner) backwardnext() {
if r.rightToLeft {
r.runtextpos++
} else {
r.runtextpos--
}
}
func (r *runner) charAt(j int) rune {
return r.runtext[j]
}
func (r *runner) findFirstChar() bool {
if 0 != (r.code.Anchors & (syntax.AnchorBeginning | syntax.AnchorStart | syntax.AnchorEndZ | syntax.AnchorEnd)) {
if !r.code.RightToLeft {
if (0 != (r.code.Anchors&syntax.AnchorBeginning) && r.runtextpos > 0) ||
(0 != (r.code.Anchors&syntax.AnchorStart) && r.runtextpos > r.runtextstart) {
r.runtextpos = r.runtextend
return false
}
if 0 != (r.code.Anchors&syntax.AnchorEndZ) && r.runtextpos < r.runtextend-1 {
r.runtextpos = r.runtextend - 1
} else if 0 != (r.code.Anchors&syntax.AnchorEnd) && r.runtextpos < r.runtextend {
r.runtextpos = r.runtextend
}
} else {
if (0 != (r.code.Anchors&syntax.AnchorEnd) && r.runtextpos < r.runtextend) ||
(0 != (r.code.Anchors&syntax.AnchorEndZ) && (r.runtextpos < r.runtextend-1 ||
(r.runtextpos == r.runtextend-1 && r.charAt(r.runtextpos) != '\n'))) ||
(0 != (r.code.Anchors&syntax.AnchorStart) && r.runtextpos < r.runtextstart) {
r.runtextpos = 0
return false
}
if 0 != (r.code.Anchors&syntax.AnchorBeginning) && r.runtextpos > 0 {
r.runtextpos = 0
}
}
if r.code.BmPrefix != nil {
return r.code.BmPrefix.IsMatch(r.runtext, r.runtextpos, 0, r.runtextend)
}
return true // found a valid start or end anchor
} else if r.code.BmPrefix != nil {
r.runtextpos = r.code.BmPrefix.Scan(r.runtext, r.runtextpos, 0, r.runtextend)
if r.runtextpos == -1 {
if r.code.RightToLeft {
r.runtextpos = 0
} else {
r.runtextpos = r.runtextend
}
return false
}
return true
} else if r.code.FcPrefix == nil {
return true
}
r.rightToLeft = r.code.RightToLeft
r.caseInsensitive = r.code.FcPrefix.CaseInsensitive
set := r.code.FcPrefix.PrefixSet
if set.IsSingleton() {
ch := set.SingletonChar()
for i := r.forwardchars(); i > 0; i-- {
if ch == r.forwardcharnext() {
r.backwardnext()
return true
}
}
} else {
for i := r.forwardchars(); i > 0; i-- {
n := r.forwardcharnext()
//fmt.Printf("%v in %v: %v\n", string(n), set.String(), set.CharIn(n))
if set.CharIn(n) {
r.backwardnext()
return true
}
}
}
return false
}
func (r *runner) initMatch() {
// Use a hashtable'ed Match object if the capture numbers are sparse
if r.runmatch == nil {
if r.re.caps != nil {
r.runmatch = newMatchSparse(r.re, r.re.caps, r.re.capsize, r.runtext, r.runtextstart)
} else {
r.runmatch = newMatch(r.re, r.re.capsize, r.runtext, r.runtextstart)
}
} else {
r.runmatch.reset(r.runtext, r.runtextstart)
}
// note we test runcrawl, because it is the last one to be allocated
// If there is an alloc failure in the middle of the three allocations,
// we may still return to reuse this instance, and we want to behave
// as if the allocations didn't occur. (we used to test _trackcount != 0)
if r.runcrawl != nil {
r.runtrackpos = len(r.runtrack)
r.runstackpos = len(r.runstack)
r.runcrawlpos = len(r.runcrawl)
return
}
r.initTrackCount()
tracksize := r.runtrackcount * 8
stacksize := r.runtrackcount * 8
if tracksize < 32 {
tracksize = 32
}
if stacksize < 16 {
stacksize = 16
}
r.runtrack = make([]int, tracksize)
r.runtrackpos = tracksize
r.runstack = make([]int, stacksize)
r.runstackpos = stacksize
r.runcrawl = make([]int, 32)
r.runcrawlpos = 32
}
func (r *runner) tidyMatch(quick bool) *Match {
if !quick {
match := r.runmatch
r.runmatch = nil
match.tidy(r.runtextpos)
return match
} else {
// send back our match -- it's not leaving the package, so it's safe to not clean it up
// this reduces allocs for frequent calls to the "IsMatch" bool-only functions
return r.runmatch
}
}
// capture captures a subexpression. Note that the
// capnum used here has already been mapped to a non-sparse
// index (by the code generator RegexWriter).
func (r *runner) capture(capnum, start, end int) {
if end < start {
T := end
end = start
start = T
}
r.crawl(capnum)
r.runmatch.addMatch(capnum, start, end-start)
}
// transferCapture captures a subexpression. Note that the
// capnum used here has already been mapped to a non-sparse
// index (by the code generator RegexWriter).
func (r *runner) transferCapture(capnum, uncapnum, start, end int) {
var start2, end2 int
// these are the two intervals that are cancelling each other
if end < start {
T := end
end = start
start = T
}
start2 = r.runmatch.matchIndex(uncapnum)
end2 = start2 + r.runmatch.matchLength(uncapnum)
// The new capture gets the innermost defined interval
if start >= end2 {
end = start
start = end2
} else if end <= start2 {
start = start2
} else {
if end > end2 {
end = end2
}
if start2 > start {
start = start2
}
}
r.crawl(uncapnum)
r.runmatch.balanceMatch(uncapnum)
if capnum != -1 {
r.crawl(capnum)
r.runmatch.addMatch(capnum, start, end-start)
}
}
// revert the last capture
func (r *runner) uncapture() {
capnum := r.popcrawl()
r.runmatch.removeMatch(capnum)
}
//debug
func (r *runner) dumpState() {
back := ""
if r.operator&syntax.Back != 0 {
back = " Back"
}
if r.operator&syntax.Back2 != 0 {
back += " Back2"
}
fmt.Printf("Text: %v\nTrack: %v\nStack: %v\n %s%s\n\n",
r.textposDescription(),
r.stackDescription(r.runtrack, r.runtrackpos),
r.stackDescription(r.runstack, r.runstackpos),
r.code.OpcodeDescription(r.codepos),
back)
}
func (r *runner) stackDescription(a []int, index int) string {
buf := &bytes.Buffer{}
fmt.Fprintf(buf, "%v/%v", len(a)-index, len(a))
if buf.Len() < 8 {
buf.WriteString(strings.Repeat(" ", 8-buf.Len()))
}
buf.WriteRune('(')
for i := index; i < len(a); i++ {
if i > index {
buf.WriteRune(' ')
}
buf.WriteString(strconv.Itoa(a[i]))
}
buf.WriteRune(')')
return buf.String()
}
func (r *runner) textposDescription() string {
buf := &bytes.Buffer{}
buf.WriteString(strconv.Itoa(r.runtextpos))
if buf.Len() < 8 {
buf.WriteString(strings.Repeat(" ", 8-buf.Len()))
}
if r.runtextpos > 0 {
buf.WriteString(syntax.CharDescription(r.runtext[r.runtextpos-1]))
} else {
buf.WriteRune('^')
}
buf.WriteRune('>')
for i := r.runtextpos; i < r.runtextend; i++ {
buf.WriteString(syntax.CharDescription(r.runtext[i]))
}
if buf.Len() >= 64 {
buf.Truncate(61)
buf.WriteString("...")
} else {
buf.WriteRune('$')
}
return buf.String()
}
// decide whether the pos
// at the specified index is a boundary or not. It's just not worth
// emitting inline code for this logic.
func (r *runner) isBoundary(index, startpos, endpos int) bool {
return (index > startpos && syntax.IsWordChar(r.runtext[index-1])) !=
(index < endpos && syntax.IsWordChar(r.runtext[index]))
}
func (r *runner) isECMABoundary(index, startpos, endpos int) bool {
return (index > startpos && syntax.IsECMAWordChar(r.runtext[index-1])) !=
(index < endpos && syntax.IsECMAWordChar(r.runtext[index]))
}
// this seems like a comment to justify randomly picking 1000 :-P
// We have determined this value in a series of experiments where x86 retail
// builds (ono-lab-optimized) were run on different pattern/input pairs. Larger values
// of TimeoutCheckFrequency did not tend to increase performance; smaller values
// of TimeoutCheckFrequency tended to slow down the execution.
const timeoutCheckFrequency int = 1000
func (r *runner) startTimeoutWatch() {
if r.ignoreTimeout {
return
}
r.timeoutChecksToSkip = timeoutCheckFrequency
r.timeoutAt = time.Now().Add(r.timeout)
}
func (r *runner) checkTimeout() error {
if r.ignoreTimeout {
return nil
}
r.timeoutChecksToSkip--
if r.timeoutChecksToSkip != 0 {
return nil
}
r.timeoutChecksToSkip = timeoutCheckFrequency
return r.doCheckTimeout()
}
func (r *runner) doCheckTimeout() error {
current := time.Now()
if current.Before(r.timeoutAt) {
return nil
}
if r.re.Debug() {
//Debug.WriteLine("")
//Debug.WriteLine("RegEx match timeout occurred!")
//Debug.WriteLine("Specified timeout: " + TimeSpan.FromMilliseconds(_timeout).ToString())
//Debug.WriteLine("Timeout check frequency: " + TimeoutCheckFrequency)
//Debug.WriteLine("Search pattern: " + _runregex._pattern)
//Debug.WriteLine("Input: " + r.runtext)
//Debug.WriteLine("About to throw RegexMatchTimeoutException.")
}
return fmt.Errorf("match timeout after %v on input `%v`", r.timeout, string(r.runtext))
}
func (r *runner) initTrackCount() {
r.runtrackcount = r.code.TrackCount
}
// getRunner returns a run to use for matching re.
// It uses the re's runner cache if possible, to avoid
// unnecessary allocation.
func (re *Regexp) getRunner() *runner {
re.muRun.Lock()
if n := len(re.runner); n > 0 {
z := re.runner[n-1]
re.runner = re.runner[:n-1]
re.muRun.Unlock()
return z
}
re.muRun.Unlock()
z := &runner{
re: re,
code: re.code,
}
return z
}
// putRunner returns a runner to the re's cache.
// There is no attempt to limit the size of the cache, so it will
// grow to the maximum number of simultaneous matches
// run using re. (The cache empties when re gets garbage collected.)
func (re *Regexp) putRunner(r *runner) {
re.muRun.Lock()
re.runner = append(re.runner, r)
re.muRun.Unlock()
}