1 package io.jawk.intermediate;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 import java.io.PrintStream;
26 import java.io.Serializable;
27 import java.util.ArrayDeque;
28 import java.util.ArrayList;
29 import java.util.Arrays;
30 import java.util.Collections;
31 import java.util.Deque;
32 import java.util.HashMap;
33 import java.util.HashSet;
34 import java.util.IdentityHashMap;
35 import java.util.Map;
36 import java.util.Set;
37 import java.util.function.Supplier;
38 import java.util.regex.Pattern;
39 import edu.umd.cs.findbugs.annotations.SuppressFBWarnings;
40 import io.jawk.ext.ExtensionFunction;
41 import io.jawk.jrt.JRT;
42
43
44
45
46
47
48
49
50 public class AwkTuples implements Serializable {
51
52 private static final long serialVersionUID = 2L;
53
54
55 private final AddressManager addressManager = new AddressManager();
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72 private java.util.List<Tuple> queue = new ArrayList<Tuple>(100) {
73 private static final long serialVersionUID = -6334362156408598578L;
74
75 @Override
76 public boolean add(Tuple t) {
77 t.setLineNumber(linenoStack.peek());
78 return super.add(t);
79 }
80 };
81
82
83 private boolean postProcessed;
84
85
86 private boolean optimized;
87
88
89 private boolean evalTupleStream;
90
91
92
93
94
95
96
97
98
99 public static String toOpcodeString(int opcode) {
100 return Opcode.fromId(opcode).name();
101 }
102
103
104
105
106
107
108 public void pop() {
109 queue.add(new Tuple.NoOperandTuple(Opcode.POP));
110 }
111
112
113
114
115
116
117
118
119 public void push(Object o) {
120 if (o instanceof String) {
121 queue.add(new Tuple.PushStringTuple(o.toString()));
122 } else if (o instanceof Integer) {
123 queue.add(new Tuple.PushLongTuple((long) (Integer) o));
124 } else if (o instanceof Long) {
125 queue.add(new Tuple.PushLongTuple((long) (Long) o));
126 } else if (o instanceof Double) {
127 queue.add(new Tuple.PushDoubleTuple((Double) o));
128 }
129 }
130
131
132
133
134
135
136
137
138 public void ifFalse(Address address) {
139 queue.add(new Tuple.AddressTuple(Opcode.IFFALSE, address));
140 }
141
142
143
144
145
146
147 public void toNumber() {
148 queue.add(new Tuple.NoOperandTuple(Opcode.TO_NUMBER));
149 }
150
151
152
153
154
155
156
157
158 public void ifTrue(Address address) {
159 queue.add(new Tuple.AddressTuple(Opcode.IFTRUE, address));
160 }
161
162
163
164
165
166
167
168
169 public void gotoAddress(Address address) {
170 queue.add(new Tuple.AddressTuple(Opcode.GOTO, address));
171 }
172
173
174
175
176
177
178
179
180
181 public Address createAddress(String label) {
182 return addressManager.createAddress(label);
183 }
184
185
186
187
188
189
190
191
192
193 public AwkTuples address(Address address) {
194 addressManager.resolveAddress(address, queue.size());
195 return this;
196 }
197
198
199
200
201
202
203 public void nop() {
204 queue.add(new Tuple.NoOperandTuple(Opcode.NOP));
205 }
206
207
208
209
210
211
212
213
214 public void print(int numExprs) {
215 queue.add(new Tuple.CountTuple(Opcode.PRINT, numExprs));
216 }
217
218
219
220
221
222
223
224
225
226 public void printToFile(int numExprs, boolean append) {
227 queue.add(new Tuple.CountAndAppendTuple(Opcode.PRINT_TO_FILE, numExprs, append));
228 }
229
230
231
232
233
234
235
236
237 public void printToPipe(int numExprs) {
238 queue.add(new Tuple.CountTuple(Opcode.PRINT_TO_PIPE, numExprs));
239 }
240
241
242
243
244
245
246
247
248 public void printf(int numExprs) {
249 queue.add(new Tuple.CountTuple(Opcode.PRINTF, numExprs));
250 }
251
252
253
254
255
256
257
258
259
260 public void printfToFile(int numExprs, boolean append) {
261 queue.add(new Tuple.CountAndAppendTuple(Opcode.PRINTF_TO_FILE, numExprs, append));
262 }
263
264
265
266
267
268
269
270
271 public void printfToPipe(int numExprs) {
272 queue.add(new Tuple.CountTuple(Opcode.PRINTF_TO_PIPE, numExprs));
273 }
274
275
276
277
278
279
280
281
282 public void sprintf(int numExprs) {
283 queue.add(new Tuple.CountTuple(Opcode.SPRINTF, numExprs));
284 }
285
286
287
288
289
290
291
292
293 public void length(int numExprs) {
294 queue.add(new Tuple.CountTuple(Opcode.LENGTH, numExprs));
295 }
296
297
298
299
300
301
302 public void concat() {
303 queue.add(new Tuple.NoOperandTuple(Opcode.CONCAT));
304 }
305
306
307
308
309
310
311
312
313
314 public void assign(int offset, boolean isGlobal) {
315 queue.add(new Tuple.VariableTuple(Opcode.ASSIGN, offset, isGlobal));
316 }
317
318
319
320
321
322
323
324
325
326 public void assignArray(int offset, boolean isGlobal) {
327 queue.add(new Tuple.VariableTuple(Opcode.ASSIGN_ARRAY, offset, isGlobal));
328 }
329
330
331
332
333 public void assignMapElement() {
334 queue.add(new Tuple.NoOperandTuple(Opcode.ASSIGN_MAP_ELEMENT));
335 }
336
337
338
339
340
341
342 public void assignAsInput() {
343 queue.add(new Tuple.NoOperandTuple(Opcode.ASSIGN_AS_INPUT));
344 }
345
346
347
348
349
350
351 public void markEvalTupleStream() {
352 evalTupleStream = true;
353 }
354
355
356
357
358
359
360 public void assignAsInputField() {
361 queue.add(new Tuple.NoOperandTuple(Opcode.ASSIGN_AS_INPUT_FIELD));
362 }
363
364
365
366
367
368
369
370
371
372
373 public void dereference(int offset, boolean isArray, boolean isGlobal) {
374 queue.add(new Tuple.DereferenceTuple(offset, isArray, isGlobal));
375 }
376
377
378
379
380
381
382
383
384
385 public void plusEq(int offset, boolean isGlobal) {
386 queue.add(new Tuple.CompoundAssignTuple(Opcode.PLUS_EQ, offset, isGlobal));
387 }
388
389
390
391
392
393
394
395
396
397 public void minusEq(int offset, boolean isGlobal) {
398 queue.add(new Tuple.CompoundAssignTuple(Opcode.MINUS_EQ, offset, isGlobal));
399 }
400
401
402
403
404
405
406
407
408
409 public void multEq(int offset, boolean isGlobal) {
410 queue.add(new Tuple.CompoundAssignTuple(Opcode.MULT_EQ, offset, isGlobal));
411 }
412
413
414
415
416
417
418
419
420
421 public void divEq(int offset, boolean isGlobal) {
422 queue.add(new Tuple.CompoundAssignTuple(Opcode.DIV_EQ, offset, isGlobal));
423 }
424
425
426
427
428
429
430
431
432
433 public void modEq(int offset, boolean isGlobal) {
434 queue.add(new Tuple.CompoundAssignTuple(Opcode.MOD_EQ, offset, isGlobal));
435 }
436
437
438
439
440
441
442
443
444
445 public void powEq(int offset, boolean isGlobal) {
446 queue.add(new Tuple.CompoundAssignTuple(Opcode.POW_EQ, offset, isGlobal));
447 }
448
449
450
451
452
453
454
455
456
457 public void plusEqArray(int offset, boolean isGlobal) {
458 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.PLUS_EQ_ARRAY, offset, isGlobal));
459 }
460
461
462
463
464 public void plusEqMapElement() {
465 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.PLUS_EQ_MAP_ELEMENT));
466 }
467
468
469
470
471
472
473
474
475
476 public void minusEqArray(int offset, boolean isGlobal) {
477 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.MINUS_EQ_ARRAY, offset, isGlobal));
478 }
479
480
481
482
483 public void minusEqMapElement() {
484 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.MINUS_EQ_MAP_ELEMENT));
485 }
486
487
488
489
490
491
492
493
494
495 public void multEqArray(int offset, boolean isGlobal) {
496 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.MULT_EQ_ARRAY, offset, isGlobal));
497 }
498
499
500
501
502 public void multEqMapElement() {
503 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.MULT_EQ_MAP_ELEMENT));
504 }
505
506
507
508
509
510
511
512
513
514 public void divEqArray(int offset, boolean isGlobal) {
515 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.DIV_EQ_ARRAY, offset, isGlobal));
516 }
517
518
519
520
521 public void divEqMapElement() {
522 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.DIV_EQ_MAP_ELEMENT));
523 }
524
525
526
527
528
529
530
531
532
533 public void modEqArray(int offset, boolean isGlobal) {
534 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.MOD_EQ_ARRAY, offset, isGlobal));
535 }
536
537
538
539
540 public void modEqMapElement() {
541 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.MOD_EQ_MAP_ELEMENT));
542 }
543
544
545
546
547
548
549
550
551
552 public void powEqArray(int offset, boolean isGlobal) {
553 queue.add(new Tuple.CompoundAssignArrayTuple(Opcode.POW_EQ_ARRAY, offset, isGlobal));
554 }
555
556
557
558
559
560 public void powEqMapElement() {
561 queue.add(new Tuple.CompoundAssignMapElementTuple(Opcode.POW_EQ_MAP_ELEMENT));
562 }
563
564
565
566
567
568
569 public void plusEqInputField() {
570 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.PLUS_EQ_INPUT_FIELD));
571 }
572
573
574
575
576
577
578 public void minusEqInputField() {
579 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.MINUS_EQ_INPUT_FIELD));
580 }
581
582
583
584
585
586
587 public void multEqInputField() {
588 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.MULT_EQ_INPUT_FIELD));
589 }
590
591
592
593
594
595
596 public void divEqInputField() {
597 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.DIV_EQ_INPUT_FIELD));
598 }
599
600
601
602
603
604
605 public void modEqInputField() {
606 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.MOD_EQ_INPUT_FIELD));
607 }
608
609
610
611
612
613
614 public void powEqInputField() {
615 queue.add(new Tuple.CompoundAssignInputFieldTuple(Opcode.POW_EQ_INPUT_FIELD));
616 }
617
618
619
620
621
622
623
624
625 public void srand(int num) {
626 queue.add(new Tuple.CountTuple(Opcode.SRAND, num));
627 }
628
629
630
631
632
633
634 public void rand() {
635 queue.add(new Tuple.NoOperandTuple(Opcode.RAND));
636 }
637
638
639
640
641
642
643 public void intFunc() {
644 queue.add(new Tuple.NoOperandTuple(Opcode.INTFUNC));
645 }
646
647
648
649
650
651
652 public void sqrt() {
653 queue.add(new Tuple.NoOperandTuple(Opcode.SQRT));
654 }
655
656
657
658
659
660
661 public void log() {
662 queue.add(new Tuple.NoOperandTuple(Opcode.LOG));
663 }
664
665
666
667
668
669
670 public void exp() {
671 queue.add(new Tuple.NoOperandTuple(Opcode.EXP));
672 }
673
674
675
676
677
678
679 public void sin() {
680 queue.add(new Tuple.NoOperandTuple(Opcode.SIN));
681 }
682
683
684
685
686
687
688 public void cos() {
689 queue.add(new Tuple.NoOperandTuple(Opcode.COS));
690 }
691
692
693
694
695
696
697 public void atan2() {
698 queue.add(new Tuple.NoOperandTuple(Opcode.ATAN2));
699 }
700
701
702
703
704
705
706 public void match() {
707 queue.add(new Tuple.NoOperandTuple(Opcode.MATCH));
708 }
709
710
711
712
713
714
715 public void index() {
716 queue.add(new Tuple.NoOperandTuple(Opcode.INDEX));
717 }
718
719
720
721
722
723
724
725
726 public void subForDollar0(boolean isGsub) {
727 queue.add(new Tuple.BooleanTuple(Opcode.SUB_FOR_DOLLAR_0, isGsub));
728 }
729
730
731
732
733
734
735
736
737 public void subForDollarReference(boolean isGsub) {
738 queue.add(new Tuple.BooleanTuple(Opcode.SUB_FOR_DOLLAR_REFERENCE, isGsub));
739 }
740
741
742
743
744
745
746
747
748
749
750 public void subForVariable(int offset, boolean isGlobal, boolean isGsub) {
751 queue.add(new Tuple.SubstitutionVariableTuple(Opcode.SUB_FOR_VARIABLE, offset, isGlobal, isGsub));
752 }
753
754
755
756
757
758
759
760
761
762
763 public void subForArrayReference(int offset, boolean isGlobal, boolean isGsub) {
764 queue.add(new Tuple.SubstitutionVariableTuple(Opcode.SUB_FOR_ARRAY_REFERENCE, offset, isGlobal, isGsub));
765 }
766
767
768
769
770
771
772
773 public void subForMapReference(boolean isGsub) {
774 queue.add(new Tuple.BooleanTuple(Opcode.SUB_FOR_MAP_REFERENCE, isGsub));
775 }
776
777
778
779
780
781
782
783
784 public void split(int numargs) {
785 queue.add(new Tuple.CountTuple(Opcode.SPLIT, numargs));
786 }
787
788
789
790
791
792
793
794
795 public void substr(int numargs) {
796 queue.add(new Tuple.CountTuple(Opcode.SUBSTR, numargs));
797 }
798
799
800
801
802
803
804 public void tolower() {
805 queue.add(new Tuple.NoOperandTuple(Opcode.TOLOWER));
806 }
807
808
809
810
811
812
813 public void toupper() {
814 queue.add(new Tuple.NoOperandTuple(Opcode.TOUPPER));
815 }
816
817
818
819
820
821
822 public void system() {
823 queue.add(new Tuple.NoOperandTuple(Opcode.SYSTEM));
824 }
825
826
827
828
829
830
831 public void swap() {
832 queue.add(new Tuple.NoOperandTuple(Opcode.SWAP));
833 }
834
835
836
837
838
839
840 public void add() {
841 queue.add(new Tuple.NoOperandTuple(Opcode.ADD));
842 }
843
844
845
846
847
848
849 public void subtract() {
850 queue.add(new Tuple.NoOperandTuple(Opcode.SUBTRACT));
851 }
852
853
854
855
856
857
858 public void multiply() {
859 queue.add(new Tuple.NoOperandTuple(Opcode.MULTIPLY));
860 }
861
862
863
864
865
866
867 public void divide() {
868 queue.add(new Tuple.NoOperandTuple(Opcode.DIVIDE));
869 }
870
871
872
873
874
875
876 public void mod() {
877 queue.add(new Tuple.NoOperandTuple(Opcode.MOD));
878 }
879
880
881
882
883
884
885 public void pow() {
886 queue.add(new Tuple.NoOperandTuple(Opcode.POW));
887 }
888
889
890
891
892
893
894
895
896
897 public void inc(int offset, boolean isGlobal) {
898 queue.add(new Tuple.VariableTuple(Opcode.INC, offset, isGlobal));
899 }
900
901
902
903
904
905
906
907
908
909 public void dec(int offset, boolean isGlobal) {
910 queue.add(new Tuple.VariableTuple(Opcode.DEC, offset, isGlobal));
911 }
912
913
914
915
916
917
918
919
920
921 public void postInc(int offset, boolean isGlobal) {
922 queue.add(new Tuple.VariableTuple(Opcode.POSTINC, offset, isGlobal));
923 }
924
925
926
927
928
929
930
931
932
933 public void postDec(int offset, boolean isGlobal) {
934 queue.add(new Tuple.VariableTuple(Opcode.POSTDEC, offset, isGlobal));
935 }
936
937
938
939
940
941
942
943
944
945 public void incArrayRef(int offset, boolean isGlobal) {
946 queue.add(new Tuple.VariableTuple(Opcode.INC_ARRAY_REF, offset, isGlobal));
947 }
948
949
950
951
952 public void incMapRef() {
953 queue.add(new Tuple.NoOperandTuple(Opcode.INC_MAP_REF));
954 }
955
956
957
958
959
960
961
962
963
964 public void decArrayRef(int offset, boolean isGlobal) {
965 queue.add(new Tuple.VariableTuple(Opcode.DEC_ARRAY_REF, offset, isGlobal));
966 }
967
968
969
970
971 public void decMapRef() {
972 queue.add(new Tuple.NoOperandTuple(Opcode.DEC_MAP_REF));
973 }
974
975
976
977
978
979
980 public void incDollarRef() {
981 queue.add(new Tuple.NoOperandTuple(Opcode.INC_DOLLAR_REF));
982 }
983
984
985
986
987
988
989 public void decDollarRef() {
990 queue.add(new Tuple.NoOperandTuple(Opcode.DEC_DOLLAR_REF));
991 }
992
993
994
995
996
997
998 public void dup() {
999 queue.add(new Tuple.NoOperandTuple(Opcode.DUP));
1000 }
1001
1002
1003
1004
1005
1006
1007 public void not() {
1008 queue.add(new Tuple.NoOperandTuple(Opcode.NOT));
1009 }
1010
1011
1012
1013
1014
1015
1016 public void negate() {
1017 queue.add(new Tuple.NoOperandTuple(Opcode.NEGATE));
1018 }
1019
1020
1021
1022
1023
1024
1025 public void unaryPlus() {
1026 queue.add(new Tuple.NoOperandTuple(Opcode.UNARY_PLUS));
1027 }
1028
1029
1030
1031
1032
1033
1034 public void cmpEq() {
1035 queue.add(new Tuple.NoOperandTuple(Opcode.CMP_EQ));
1036 }
1037
1038
1039
1040
1041
1042
1043 public void cmpLt() {
1044 queue.add(new Tuple.NoOperandTuple(Opcode.CMP_LT));
1045 }
1046
1047
1048
1049
1050
1051
1052 public void cmpGt() {
1053 queue.add(new Tuple.NoOperandTuple(Opcode.CMP_GT));
1054 }
1055
1056
1057
1058
1059
1060
1061 public void matches() {
1062 queue.add(new Tuple.NoOperandTuple(Opcode.MATCHES));
1063 }
1064
1065
1066
1067
1068
1069
1070 public void dereferenceArray() {
1071 queue.add(new Tuple.NoOperandTuple(Opcode.DEREF_ARRAY));
1072 }
1073
1074
1075
1076
1077
1078 public void peekArrayElement() {
1079 queue.add(new Tuple.NoOperandTuple(Opcode.PEEK_ARRAY_ELEMENT));
1080 }
1081
1082
1083
1084
1085
1086 public void ensureArrayElement() {
1087 queue.add(new Tuple.NoOperandTuple(Opcode.ENSURE_ARRAY_ELEMENT));
1088 }
1089
1090
1091
1092
1093
1094
1095 public void keylist() {
1096 queue.add(new Tuple.NoOperandTuple(Opcode.KEYLIST));
1097 }
1098
1099
1100
1101
1102
1103
1104
1105
1106 public void isEmptyList(Address address) {
1107 queue.add(new Tuple.AddressTuple(Opcode.IS_EMPTY_KEYLIST, address));
1108 }
1109
1110
1111
1112
1113
1114
1115 public void getFirstAndRemoveFromList() {
1116 queue.add(new Tuple.NoOperandTuple(Opcode.GET_FIRST_AND_REMOVE_FROM_KEYLIST));
1117 }
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127 public boolean checkClass(Class<?> cls) {
1128 queue.add(new Tuple.ClassTuple(cls));
1129 return true;
1130 }
1131
1132
1133
1134
1135
1136
1137 public void getInputField() {
1138 queue.add(new Tuple.NoOperandTuple(Opcode.GET_INPUT_FIELD));
1139 }
1140
1141
1142
1143
1144
1145
1146
1147
1148 public void getInputField(long fieldIndex) {
1149 queue.add(new Tuple.InputFieldTuple(fieldIndex));
1150 }
1151
1152
1153
1154
1155
1156
1157
1158
1159 public void consumeInput(Address address) {
1160 queue.add(new Tuple.AddressTuple(Opcode.CONSUME_INPUT, address));
1161 }
1162
1163
1164
1165
1166
1167
1168 public void getlineInput() {
1169 queue.add(new Tuple.NoOperandTuple(Opcode.GETLINE_INPUT));
1170 }
1171
1172
1173
1174
1175
1176
1177 public void getlineInputToTarget() {
1178 queue.add(new Tuple.NoOperandTuple(Opcode.GETLINE_INPUT_TO_TARGET));
1179 }
1180
1181
1182
1183
1184
1185
1186 public void useAsFileInput() {
1187 queue.add(new Tuple.NoOperandTuple(Opcode.USE_AS_FILE_INPUT));
1188 }
1189
1190
1191
1192
1193
1194
1195 public void useAsCommandInput() {
1196 queue.add(new Tuple.NoOperandTuple(Opcode.USE_AS_COMMAND_INPUT));
1197 }
1198
1199
1200
1201
1202
1203
1204
1205
1206 public void nfOffset(int offset) {
1207 queue.add(new Tuple.LongTuple(Opcode.NF_OFFSET, offset));
1208 }
1209
1210
1211
1212
1213
1214
1215
1216
1217 public void nrOffset(int offset) {
1218 queue.add(new Tuple.LongTuple(Opcode.NR_OFFSET, offset));
1219 }
1220
1221
1222
1223
1224
1225
1226
1227
1228 public void fnrOffset(int offset) {
1229 queue.add(new Tuple.LongTuple(Opcode.FNR_OFFSET, offset));
1230 }
1231
1232
1233
1234
1235
1236
1237
1238
1239 public void fsOffset(int offset) {
1240 queue.add(new Tuple.LongTuple(Opcode.FS_OFFSET, offset));
1241 }
1242
1243
1244
1245
1246
1247
1248
1249
1250 public void rsOffset(int offset) {
1251 queue.add(new Tuple.LongTuple(Opcode.RS_OFFSET, offset));
1252 }
1253
1254
1255
1256
1257
1258
1259
1260
1261 public void ofsOffset(int offset) {
1262 queue.add(new Tuple.LongTuple(Opcode.OFS_OFFSET, offset));
1263 }
1264
1265
1266
1267
1268
1269
1270
1271
1272 public void orsOffset(int offset) {
1273 queue.add(new Tuple.LongTuple(Opcode.ORS_OFFSET, offset));
1274 }
1275
1276
1277
1278
1279
1280
1281
1282
1283 public void rstartOffset(int offset) {
1284 queue.add(new Tuple.LongTuple(Opcode.RSTART_OFFSET, offset));
1285 }
1286
1287
1288
1289
1290
1291
1292
1293
1294 public void rlengthOffset(int offset) {
1295 queue.add(new Tuple.LongTuple(Opcode.RLENGTH_OFFSET, offset));
1296 }
1297
1298
1299
1300
1301
1302
1303
1304
1305 public void filenameOffset(int offset) {
1306 queue.add(new Tuple.LongTuple(Opcode.FILENAME_OFFSET, offset));
1307 }
1308
1309
1310
1311
1312
1313
1314
1315
1316 public void subsepOffset(int offset) {
1317 queue.add(new Tuple.LongTuple(Opcode.SUBSEP_OFFSET, offset));
1318 }
1319
1320
1321
1322
1323
1324
1325
1326
1327 public void convfmtOffset(int offset) {
1328 queue.add(new Tuple.LongTuple(Opcode.CONVFMT_OFFSET, offset));
1329 }
1330
1331
1332
1333
1334
1335
1336
1337
1338 public void ofmtOffset(int offset) {
1339 queue.add(new Tuple.LongTuple(Opcode.OFMT_OFFSET, offset));
1340 }
1341
1342
1343
1344
1345
1346
1347
1348
1349 public void environOffset(int offset) {
1350 queue.add(new Tuple.LongTuple(Opcode.ENVIRON_OFFSET, offset));
1351 }
1352
1353
1354
1355
1356
1357
1358
1359
1360 public void argcOffset(int offset) {
1361 queue.add(new Tuple.LongTuple(Opcode.ARGC_OFFSET, offset));
1362 }
1363
1364
1365
1366
1367
1368
1369
1370
1371 public void argvOffset(int offset) {
1372 queue.add(new Tuple.LongTuple(Opcode.ARGV_OFFSET, offset));
1373 }
1374
1375
1376
1377 public void pushNF() {
1378 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_NF));
1379 }
1380
1381
1382 public void assignNF() {
1383 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_NF));
1384 }
1385
1386
1387 public void pushNR() {
1388 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_NR));
1389 }
1390
1391
1392 public void assignNR() {
1393 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_NR));
1394 }
1395
1396
1397 public void pushFNR() {
1398 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_FNR));
1399 }
1400
1401
1402 public void assignFNR() {
1403 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_FNR));
1404 }
1405
1406
1407 public void pushFS() {
1408 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_FS));
1409 }
1410
1411
1412 public void assignFS() {
1413 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_FS));
1414 }
1415
1416
1417 public void pushRS() {
1418 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_RS));
1419 }
1420
1421
1422 public void assignRS() {
1423 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_RS));
1424 }
1425
1426
1427 public void pushOFS() {
1428 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_OFS));
1429 }
1430
1431
1432 public void assignOFS() {
1433 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_OFS));
1434 }
1435
1436
1437 public void pushORS() {
1438 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_ORS));
1439 }
1440
1441
1442 public void assignORS() {
1443 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_ORS));
1444 }
1445
1446
1447 public void pushRSTART() {
1448 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_RSTART));
1449 }
1450
1451
1452 public void assignRSTART() {
1453 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_RSTART));
1454 }
1455
1456
1457 public void pushRLENGTH() {
1458 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_RLENGTH));
1459 }
1460
1461
1462 public void assignRLENGTH() {
1463 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_RLENGTH));
1464 }
1465
1466
1467 public void pushFILENAME() {
1468 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_FILENAME));
1469 }
1470
1471
1472 public void assignFILENAME() {
1473 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_FILENAME));
1474 }
1475
1476
1477 public void pushSUBSEP() {
1478 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_SUBSEP));
1479 }
1480
1481
1482 public void assignSUBSEP() {
1483 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_SUBSEP));
1484 }
1485
1486
1487 public void pushCONVFMT() {
1488 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_CONVFMT));
1489 }
1490
1491
1492 public void assignCONVFMT() {
1493 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_CONVFMT));
1494 }
1495
1496
1497 public void pushOFMT() {
1498 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_OFMT));
1499 }
1500
1501
1502 public void assignOFMT() {
1503 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_OFMT));
1504 }
1505
1506
1507 public void pushARGC() {
1508 queue.add(new Tuple.BuiltinVarTuple(Opcode.PUSH_ARGC));
1509 }
1510
1511
1512 public void assignARGC() {
1513 queue.add(new Tuple.BuiltinVarTuple(Opcode.ASSIGN_ARGC));
1514 }
1515
1516
1517
1518
1519
1520
1521 public void applyRS() {
1522 queue.add(new Tuple.NoOperandTuple(Opcode.APPLY_RS));
1523 }
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533 public void function(String funcName, int numFormalParams) {
1534 queue.add(new Tuple.FunctionTuple(funcName, numFormalParams));
1535 }
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547 public void callFunction(
1548 Supplier<Address> addressSupplier,
1549 String funcName,
1550 int numFormalParams,
1551 int numActualParams) {
1552 queue.add(new Tuple.CallFunctionTuple(addressSupplier, funcName, numFormalParams, numActualParams));
1553 }
1554
1555
1556
1557
1558
1559
1560 public void setReturnResult() {
1561 queue.add(new Tuple.NoOperandTuple(Opcode.SET_RETURN_RESULT));
1562 }
1563
1564
1565
1566
1567
1568
1569 public void returnFromFunction() {
1570 queue.add(new Tuple.NoOperandTuple(Opcode.RETURN_FROM_FUNCTION));
1571 }
1572
1573
1574
1575
1576
1577
1578
1579
1580 public void setNumGlobals(int numGlobals) {
1581 queue.add(new Tuple.CountTuple(Opcode.SET_NUM_GLOBALS, numGlobals));
1582 }
1583
1584
1585
1586
1587
1588
1589 public void close() {
1590 queue.add(new Tuple.NoOperandTuple(Opcode.CLOSE));
1591 }
1592
1593
1594
1595
1596
1597
1598
1599
1600 public void applySubsep(int count) {
1601 queue.add(new Tuple.CountTuple(Opcode.APPLY_SUBSEP, count));
1602 }
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612 public void deleteArrayElement(int offset, boolean isGlobal) {
1613 queue.add(new Tuple.VariableTuple(Opcode.DELETE_ARRAY_ELEMENT, offset, isGlobal));
1614 }
1615
1616
1617
1618
1619 public void deleteMapElement() {
1620 queue.add(new Tuple.NoOperandTuple(Opcode.DELETE_MAP_ELEMENT));
1621 }
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631 public void deleteArray(int offset, boolean isGlobal) {
1632 queue.add(new Tuple.VariableTuple(Opcode.DELETE_ARRAY, offset, isGlobal));
1633 }
1634
1635
1636
1637
1638
1639
1640
1641
1642 public void setExitAddress(Address addr) {
1643 queue.add(new Tuple.AddressTuple(Opcode.SET_EXIT_ADDRESS, addr));
1644 }
1645
1646
1647
1648
1649
1650
1651
1652
1653 public void setWithinEndBlocks(boolean b) {
1654 queue.add(new Tuple.BooleanTuple(Opcode.SET_WITHIN_END_BLOCKS, b));
1655 }
1656
1657
1658
1659
1660
1661
1662 public void exitWithCode() {
1663 queue.add(new Tuple.NoOperandTuple(Opcode.EXIT_WITH_CODE));
1664 }
1665
1666
1667
1668
1669
1670
1671 public void exitWithoutCode() {
1672 queue.add(new Tuple.NoOperandTuple(Opcode.EXIT_WITHOUT_CODE));
1673 }
1674
1675
1676
1677
1678
1679
1680
1681
1682 public void regexp(String regexpStr) {
1683
1684
1685 Pattern precompiled = Pattern.compile(regexpStr);
1686 queue.add(new Tuple.RegexTuple(regexpStr, precompiled));
1687 }
1688
1689
1690
1691
1692
1693
1694 public void conditionPair() {
1695 queue.add(new Tuple.NoOperandTuple(Opcode.CONDITION_PAIR));
1696 }
1697
1698
1699
1700
1701
1702
1703 public void isIn() {
1704 queue.add(new Tuple.NoOperandTuple(Opcode.IS_IN));
1705 }
1706
1707
1708
1709
1710 public void scriptThis() {
1711 queue.add(new Tuple.NoOperandTuple(Opcode.THIS));
1712 }
1713
1714
1715
1716
1717
1718
1719
1720
1721 public void extension(ExtensionFunction function, int paramCount, boolean isInitial) {
1722 queue.add(new Tuple.ExtensionTuple(function, paramCount, isInitial));
1723 }
1724
1725
1726
1727
1728
1729
1730 public void dump(PrintStream ps) {
1731 ps.println("(intermediate serialVersionUID = " + serialVersionUID + ")");
1732 ps.println();
1733 for (int i = 0; i < queue.size(); i++) {
1734 Address address = addressManager.getAddress(i);
1735 if (address == null) {
1736 ps.println(i + " : " + queue.get(i));
1737 } else {
1738 ps.println(i + " : [" + address + "] : " + queue.get(i));
1739 }
1740 }
1741 }
1742
1743
1744
1745
1746
1747
1748
1749
1750 public PositionTracker top() {
1751 return new PositionTracker(queue);
1752 }
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763 public void postProcess() {
1764 if (postProcessed) {
1765 return;
1766 }
1767 if (!queue.isEmpty() && queue.get(0).hasNext()) {
1768 postProcessed = true;
1769 return;
1770 }
1771 assignSequentialNextPointers();
1772 for (Tuple tuple : queue) {
1773 tuple.touch(queue);
1774 }
1775 postProcessed = true;
1776 }
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794 public void optimize() {
1795 if (optimized) {
1796 return;
1797 }
1798 if (!postProcessed) {
1799 postProcess();
1800 }
1801 boolean queueModified = removeRedundantEvalSetNumGlobals();
1802 queueModified |= peepholeOptimize();
1803 if (queueModified) {
1804 reprocessQueue();
1805 }
1806 simplifyControlFlow();
1807 optimizeQueue();
1808 optimized = true;
1809 }
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824 private boolean removeRedundantEvalSetNumGlobals() {
1825 int setNumGlobalsIndex = -1;
1826 for (int i = 0; i < queue.size(); i++) {
1827 Opcode opcode = queue.get(i).getOpcode();
1828 if (opcode == null) {
1829 continue;
1830 }
1831 switch (opcode) {
1832 case SET_NUM_GLOBALS:
1833 if (setNumGlobalsIndex != -1) {
1834 return false;
1835 }
1836 setNumGlobalsIndex = i;
1837 break;
1838 default:
1839 if (requiresEvalGlobalFrame(opcode)) {
1840 return false;
1841 }
1842 break;
1843 }
1844 }
1845 if (!evalTupleStream || setNumGlobalsIndex < 0) {
1846 return false;
1847 }
1848
1849 int[] indexMapping = new int[queue.size()];
1850 for (int i = 0, nextIndex = 0; i < queue.size(); i++) {
1851 if (i == setNumGlobalsIndex) {
1852 indexMapping[i] = nextIndex;
1853 } else {
1854 indexMapping[i] = nextIndex++;
1855 }
1856 }
1857 queue.remove(setNumGlobalsIndex);
1858 remapAddresses(indexMapping);
1859 return true;
1860 }
1861
1862 private boolean peepholeOptimize() {
1863 boolean modified = false;
1864 boolean passModified;
1865 do {
1866 passModified = peepholeOptimizePass();
1867 modified |= passModified;
1868 } while (passModified);
1869 return modified;
1870 }
1871
1872 private boolean peepholeOptimizePass() {
1873 int originalSize = queue.size();
1874 if (originalSize < 2) {
1875 return false;
1876 }
1877
1878 java.util.List<Tuple> original = new ArrayList<Tuple>(queue);
1879 int[] indexMapping = new int[originalSize];
1880 Arrays.fill(indexMapping, -1);
1881 java.util.List<Tuple> optimizedQueue = new ArrayList<Tuple>(originalSize);
1882
1883 boolean modified = false;
1884 int oldIndex = 0;
1885 int newIndex = 0;
1886 while (oldIndex < originalSize) {
1887 Tuple tuple = original.get(oldIndex);
1888 Object literal = literalValue(tuple);
1889 if (literal != null) {
1890 if ((oldIndex + 1) < originalSize) {
1891 Tuple nextTuple = original.get(oldIndex + 1);
1892 if (nextTuple.getOpcode() == Opcode.GET_INPUT_FIELD) {
1893 long fieldIndex = JRT.toLong(literal);
1894 Tuple replacement = createGetInputFieldConst(
1895 fieldIndex,
1896 tuple.getLineNumber());
1897 optimizedQueue.add(replacement);
1898 mapFoldedRange(indexMapping, oldIndex, 2, newIndex);
1899 oldIndex += 2;
1900 newIndex++;
1901 modified = true;
1902 continue;
1903 }
1904 }
1905 if ((oldIndex + 2) < originalSize) {
1906 Tuple nextTuple = original.get(oldIndex + 1);
1907 Tuple opTuple = original.get(oldIndex + 2);
1908 Object secondLiteral = literalValue(nextTuple);
1909 if (secondLiteral != null) {
1910 Object folded = foldBinary(literal, secondLiteral, opTuple);
1911 if (folded != null) {
1912 Tuple replacement = createLiteralPush(folded, tuple.getLineNumber());
1913 optimizedQueue.add(replacement);
1914 mapFoldedRange(indexMapping, oldIndex, 3, newIndex);
1915 oldIndex += 3;
1916 newIndex++;
1917 modified = true;
1918 continue;
1919 }
1920 }
1921 }
1922 if ((oldIndex + 1) < originalSize) {
1923 Tuple opTuple = original.get(oldIndex + 1);
1924 Object folded = foldUnary(literal, opTuple);
1925 if (folded != null) {
1926 Tuple replacement = createLiteralPush(folded, tuple.getLineNumber());
1927 optimizedQueue.add(replacement);
1928 mapFoldedRange(indexMapping, oldIndex, 2, newIndex);
1929 oldIndex += 2;
1930 newIndex++;
1931 modified = true;
1932 continue;
1933 }
1934 }
1935 }
1936
1937 optimizedQueue.add(tuple);
1938 indexMapping[oldIndex] = newIndex;
1939 oldIndex++;
1940 newIndex++;
1941 }
1942
1943 if (!modified) {
1944 return false;
1945 }
1946
1947 for (int i = 0; i < optimizedQueue.size(); i++) {
1948 queue.set(i, optimizedQueue.get(i));
1949 }
1950 for (int i = queue.size() - 1; i >= optimizedQueue.size(); i--) {
1951 queue.remove(i);
1952 }
1953
1954 remapAddresses(indexMapping);
1955 return true;
1956 }
1957
1958 private void mapFoldedRange(int[] indexMapping, int startIndex, int length, int newIndex) {
1959 for (int idx = 0; idx < length; idx++) {
1960 indexMapping[startIndex + idx] = newIndex;
1961 }
1962 }
1963
1964 private Object literalValue(Tuple tuple) {
1965 switch (tuple.getOpcode()) {
1966 case PUSH_LONG:
1967 return Long.valueOf(((Tuple.PushLongTuple) tuple).getValue());
1968 case PUSH_DOUBLE:
1969 return Double.valueOf(((Tuple.PushDoubleTuple) tuple).getValue());
1970 case PUSH_STRING:
1971 return ((Tuple.PushStringTuple) tuple).getValue();
1972 default:
1973 return null;
1974 }
1975 }
1976
1977 private Object foldBinary(Object left, Object right, Tuple operation) {
1978 Opcode opcode = operation.getOpcode();
1979 if (opcode == null) {
1980 return null;
1981 }
1982 switch (opcode) {
1983 case ADD: {
1984 double d1 = JRT.toDouble(left);
1985 double d2 = JRT.toDouble(right);
1986 double ans = d1 + d2;
1987 if (JRT.isActuallyLong(ans)) {
1988 return Long.valueOf((long) Math.rint(ans));
1989 }
1990 return Double.valueOf(ans);
1991 }
1992 case SUBTRACT: {
1993 double d1 = JRT.toDouble(left);
1994 double d2 = JRT.toDouble(right);
1995 double ans = d1 - d2;
1996 if (JRT.isActuallyLong(ans)) {
1997 return Long.valueOf((long) Math.rint(ans));
1998 }
1999 return Double.valueOf(ans);
2000 }
2001 case MULTIPLY: {
2002 double d1 = JRT.toDouble(left);
2003 double d2 = JRT.toDouble(right);
2004 double ans = d1 * d2;
2005 if (JRT.isActuallyLong(ans)) {
2006 return Long.valueOf((long) Math.rint(ans));
2007 }
2008 return Double.valueOf(ans);
2009 }
2010 case DIVIDE: {
2011 double d1 = JRT.toDouble(left);
2012 double d2 = JRT.toDouble(right);
2013 double ans = d1 / d2;
2014 if (JRT.isActuallyLong(ans)) {
2015 return Long.valueOf((long) Math.rint(ans));
2016 }
2017 return Double.valueOf(ans);
2018 }
2019 case MOD: {
2020 double d1 = JRT.toDouble(left);
2021 double d2 = JRT.toDouble(right);
2022 double ans = d1 % d2;
2023 if (JRT.isActuallyLong(ans)) {
2024 return Long.valueOf((long) Math.rint(ans));
2025 }
2026 return Double.valueOf(ans);
2027 }
2028 case POW: {
2029 double d1 = JRT.toDouble(left);
2030 double d2 = JRT.toDouble(right);
2031 double ans = Math.pow(d1, d2);
2032 if (JRT.isActuallyLong(ans)) {
2033 return Long.valueOf((long) Math.rint(ans));
2034 }
2035 return Double.valueOf(ans);
2036 }
2037 case CMP_EQ:
2038 return JRT.compare2(left, right, 0) ? Long.valueOf(1L) : Long.valueOf(0L);
2039 case CMP_LT:
2040 return JRT.compare2(left, right, -1) ? Long.valueOf(1L) : Long.valueOf(0L);
2041 case CMP_GT:
2042 return JRT.compare2(left, right, 1) ? Long.valueOf(1L) : Long.valueOf(0L);
2043 case CONCAT:
2044 if (left instanceof String && right instanceof String) {
2045 return ((String) left) + ((String) right);
2046 }
2047 return null;
2048 default:
2049 return null;
2050 }
2051 }
2052
2053 private Object foldUnary(Object literal, Tuple operation) {
2054 Opcode opcode = operation.getOpcode();
2055 if (opcode == null) {
2056 return null;
2057 }
2058 switch (opcode) {
2059 case NEGATE: {
2060 double value = JRT.toDouble(literal);
2061 double ans = -value;
2062 if (JRT.isActuallyLong(ans)) {
2063 return Long.valueOf((long) Math.rint(ans));
2064 }
2065 return Double.valueOf(ans);
2066 }
2067 case UNARY_PLUS: {
2068 double value = JRT.toDouble(literal);
2069 if (JRT.isActuallyLong(value)) {
2070 return Long.valueOf((long) Math.rint(value));
2071 }
2072 return Double.valueOf(value);
2073 }
2074 default:
2075 return null;
2076 }
2077 }
2078
2079 private Tuple createLiteralPush(Object value, int lineNumber) {
2080 Tuple tuple;
2081 if (value instanceof Long) {
2082 tuple = new Tuple.PushLongTuple(((Long) value).longValue());
2083 } else if (value instanceof Integer) {
2084 tuple = new Tuple.PushLongTuple(((Integer) value).longValue());
2085 } else if (value instanceof Double) {
2086 tuple = new Tuple.PushDoubleTuple(((Double) value).doubleValue());
2087 } else if (value instanceof Number) {
2088 double d = ((Number) value).doubleValue();
2089 if (JRT.isActuallyLong(d)) {
2090 tuple = new Tuple.PushLongTuple((long) Math.rint(d));
2091 } else {
2092 tuple = new Tuple.PushDoubleTuple(d);
2093 }
2094 } else if (value instanceof String) {
2095 tuple = new Tuple.PushStringTuple((String) value);
2096 } else {
2097 throw new IllegalArgumentException("Unsupported literal value: " + value);
2098 }
2099 tuple.setLineNumber(lineNumber);
2100 return tuple;
2101 }
2102
2103 private Tuple createGetInputFieldConst(long fieldIndex, int lineNumber) {
2104 Tuple tuple = new Tuple.InputFieldTuple(fieldIndex);
2105 tuple.setLineNumber(lineNumber);
2106 return tuple;
2107 }
2108
2109 private void remapAddresses(int[] indexMapping) {
2110 if (indexMapping.length == 0) {
2111 return;
2112 }
2113 Set<Address> processedAddresses = Collections.newSetFromMap(new IdentityHashMap<Address, Boolean>());
2114 for (Tuple tuple : queue) {
2115 Address address = tuple.getAddress();
2116 if (address != null && processedAddresses.add(address)) {
2117 int oldIndex = address.index();
2118 if (oldIndex >= 0 && oldIndex < indexMapping.length) {
2119 int mappedIndex = indexMapping[oldIndex];
2120 if (mappedIndex < 0) {
2121 throw new Error("Address " + address + " references removed tuple " + oldIndex);
2122 }
2123 address.assignIndex(mappedIndex);
2124 }
2125 }
2126 }
2127 addressManager.remapIndexes(indexMapping);
2128 }
2129
2130 private void reprocessQueue() {
2131 assignSequentialNextPointers();
2132 for (Tuple tuple : queue) {
2133 tuple.touch(queue);
2134 }
2135 }
2136
2137 private boolean simplifyControlFlow() {
2138 boolean modified = false;
2139 boolean passModified;
2140 do {
2141 passModified = simplifyControlFlowPass();
2142 if (passModified) {
2143 reprocessQueue();
2144 }
2145 modified |= passModified;
2146 } while (passModified);
2147 return modified;
2148 }
2149
2150 private boolean simplifyControlFlowPass() {
2151 int size = queue.size();
2152 if (size < 2) {
2153 return false;
2154 }
2155
2156 boolean modified = false;
2157 boolean[] remove = new boolean[size];
2158 int[] redirectTargets = new int[size];
2159 int[] visitStamps = new int[size];
2160 int nextVisitStamp = 1;
2161 Arrays.fill(redirectTargets, -1);
2162
2163 for (int i = 0; i < size; i++) {
2164 Tuple tuple = queue.get(i);
2165 Address address = tuple.getAddress();
2166 if (address != null) {
2167 int resolvedTarget = resolveJumpEquivalentIndex(
2168 address.index(),
2169 size,
2170 visitStamps,
2171 nextVisitStamp++);
2172 if (resolvedTarget >= 0 && resolvedTarget != address.index()) {
2173 addressManager.reassignAddress(address, resolvedTarget);
2174 modified = true;
2175 }
2176 }
2177
2178 switch (tuple.getOpcode()) {
2179 case NOP: {
2180 int redirectTarget = resolveJumpEquivalentIndex(
2181 i + 1,
2182 size,
2183 visitStamps,
2184 nextVisitStamp++);
2185 if (redirectTarget >= 0) {
2186 remove[i] = true;
2187 redirectTargets[i] = redirectTarget;
2188 modified = true;
2189 }
2190 break;
2191 }
2192 case GOTO: {
2193 int target = resolveJumpEquivalentIndex(
2194 tuple.getAddress().index(),
2195 size,
2196 visitStamps,
2197 nextVisitStamp++);
2198 int fallthroughTarget = resolveJumpEquivalentIndex(
2199 i + 1,
2200 size,
2201 visitStamps,
2202 nextVisitStamp++);
2203 if (target >= 0 && target == fallthroughTarget) {
2204 remove[i] = true;
2205 redirectTargets[i] = fallthroughTarget;
2206 modified = true;
2207 }
2208 break;
2209 }
2210 default:
2211 break;
2212 }
2213 }
2214
2215 if (!modified) {
2216 return false;
2217 }
2218
2219 boolean anyRemoved = false;
2220 for (boolean removeTuple : remove) {
2221 if (removeTuple) {
2222 anyRemoved = true;
2223 break;
2224 }
2225 }
2226 if (!anyRemoved) {
2227 return true;
2228 }
2229
2230 int[] indexMapping = new int[size];
2231 Arrays.fill(indexMapping, -1);
2232 int nextIndex = 0;
2233 for (int i = 0; i < size; i++) {
2234 if (!remove[i]) {
2235 indexMapping[i] = nextIndex++;
2236 }
2237 }
2238 for (int i = 0; i < size; i++) {
2239 if (remove[i] && redirectTargets[i] >= 0) {
2240 indexMapping[i] = indexMapping[redirectTargets[i]];
2241 }
2242 }
2243
2244 compactQueue(remove);
2245
2246 remapAddresses(indexMapping);
2247 return true;
2248 }
2249
2250 private int resolveJumpEquivalentIndex(int index, int size, int[] visitStamps, int stamp) {
2251 if (index < 0 || index >= size) {
2252 return -1;
2253 }
2254 int current = index;
2255 while (current >= 0 && current < size && visitStamps[current] != stamp) {
2256 visitStamps[current] = stamp;
2257 Tuple tuple = queue.get(current);
2258 switch (tuple.getOpcode()) {
2259 case NOP:
2260 current++;
2261 break;
2262 case GOTO: {
2263 Address address = tuple.getAddress();
2264 if (address == null) {
2265 return current;
2266 }
2267 current = address.index();
2268 break;
2269 }
2270 default:
2271 return current;
2272 }
2273 }
2274 return -1;
2275 }
2276
2277 private void assignSequentialNextPointers() {
2278 for (int i = 0; i < queue.size(); i++) {
2279 Tuple nextTuple = (i + 1) < queue.size() ? queue.get(i + 1) : null;
2280 queue.get(i).setNext(nextTuple);
2281 }
2282 }
2283
2284 private void compactQueue(boolean[] remove) {
2285 ArrayList<Tuple> compactedQueue = new ArrayList<Tuple>(queue.size());
2286 for (int i = 0; i < remove.length; i++) {
2287 if (!remove[i]) {
2288 compactedQueue.add(queue.get(i));
2289 }
2290 }
2291 queue.clear();
2292 queue.addAll(compactedQueue);
2293 }
2294
2295 private void optimizeQueue() {
2296 int size = queue.size();
2297 if (size <= 1) {
2298 return;
2299 }
2300
2301 boolean[] reachable = new boolean[size];
2302 int[] referencesFromReachable = new int[size];
2303
2304 Deque<Integer> worklist = new ArrayDeque<>();
2305 if (!queue.isEmpty()) {
2306 reachable[0] = true;
2307 worklist.add(0);
2308 }
2309
2310 while (!worklist.isEmpty()) {
2311 int index = worklist.removeFirst();
2312 Tuple tuple = queue.get(index);
2313
2314 if (fallsThrough(tuple.getOpcode())) {
2315 Tuple nextTuple = tuple.getNext();
2316 if (nextTuple != null) {
2317 int nextIndex = index + 1;
2318 if (!reachable[nextIndex]) {
2319 reachable[nextIndex] = true;
2320 worklist.addLast(nextIndex);
2321 }
2322 }
2323 }
2324
2325 Address address = tuple.getAddress();
2326 if (address != null) {
2327 int targetIndex = address.index();
2328 if (targetIndex < 0 || targetIndex >= size) {
2329 throw new Error("address " + address + " doesn't resolve to an actual list element");
2330 }
2331 referencesFromReachable[targetIndex]++;
2332 if (!reachable[targetIndex]) {
2333 reachable[targetIndex] = true;
2334 worklist.addLast(targetIndex);
2335 }
2336 }
2337 }
2338
2339 for (int i = 0; i < size; i++) {
2340 if (!reachable[i] && referencesFromReachable[i] > 0) {
2341 reachable[i] = true;
2342 worklist.addLast(i);
2343 }
2344 }
2345
2346 while (!worklist.isEmpty()) {
2347 int index = worklist.removeFirst();
2348 Tuple tuple = queue.get(index);
2349
2350 if (fallsThrough(tuple.getOpcode())) {
2351 Tuple nextTuple = tuple.getNext();
2352 if (nextTuple != null) {
2353 int nextIndex = index + 1;
2354 if (!reachable[nextIndex]) {
2355 reachable[nextIndex] = true;
2356 worklist.addLast(nextIndex);
2357 }
2358 }
2359 }
2360
2361 Address address = tuple.getAddress();
2362 if (address != null) {
2363 int targetIndex = address.index();
2364 if (targetIndex < 0 || targetIndex >= size) {
2365 throw new Error("address " + address + " doesn't resolve to an actual list element");
2366 }
2367 referencesFromReachable[targetIndex]++;
2368 if (!reachable[targetIndex]) {
2369 reachable[targetIndex] = true;
2370 worklist.addLast(targetIndex);
2371 }
2372 }
2373 }
2374
2375 boolean anyRemoved = false;
2376 boolean[] remove = new boolean[size];
2377 for (int i = 0; i < size; i++) {
2378 if (!reachable[i]) {
2379 remove[i] = true;
2380 anyRemoved = true;
2381 continue;
2382 }
2383 Tuple tuple = queue.get(i);
2384 if (tuple.getOpcode() == Opcode.NOP && referencesFromReachable[i] == 0) {
2385 remove[i] = true;
2386 anyRemoved = true;
2387 }
2388 }
2389
2390 if (!anyRemoved) {
2391 return;
2392 }
2393
2394 int[] indexMapping = new int[size];
2395 int nextIndex = 0;
2396 for (int i = 0; i < size; i++) {
2397 if (remove[i]) {
2398 indexMapping[i] = -1;
2399 } else {
2400 indexMapping[i] = nextIndex++;
2401 }
2402 }
2403
2404 compactQueue(remove);
2405
2406 if (!queue.isEmpty()) {
2407 assignSequentialNextPointers();
2408 }
2409
2410 remapAddresses(indexMapping);
2411 }
2412
2413 private boolean fallsThrough(Opcode opcode) {
2414 if (opcode == null) {
2415 return true;
2416 }
2417 switch (opcode) {
2418 case GOTO:
2419 case EXIT_WITH_CODE:
2420 case EXIT_WITHOUT_CODE:
2421 return false;
2422 default:
2423 return true;
2424 }
2425 }
2426
2427
2428 private Map<String, Integer> globalVarOffsetMap = new HashMap<String, Integer>();
2429
2430
2431 private Map<String, Boolean> globalVarAarrayMap = new HashMap<String, Boolean>();
2432
2433
2434 private Set<String> functionNames = new HashSet<String>();
2435
2436
2437 private boolean metadataFrozen;
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447 public void addGlobalVariableNameToOffsetMapping(String varname, int offset, boolean isArray) {
2448 ensureMetadataMutable();
2449 if (globalVarOffsetMap.get(varname) != null) {
2450 return;
2451 }
2452 globalVarOffsetMap.put(varname, offset);
2453 globalVarAarrayMap.put(varname, isArray);
2454 }
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464 public void setFunctionNameSet(Set<String> names) {
2465 ensureMetadataMutable();
2466
2467
2468
2469
2470
2471
2472
2473
2474 this.functionNames = new HashSet<String>(names);
2475 }
2476
2477
2478
2479
2480
2481
2482 public void freezeMetadata() {
2483 if (metadataFrozen) {
2484 return;
2485 }
2486 globalVarOffsetMap = freezeMap(globalVarOffsetMap);
2487 globalVarAarrayMap = freezeMap(globalVarAarrayMap);
2488 functionNames = freezeSet(functionNames);
2489 metadataFrozen = true;
2490 }
2491
2492
2493
2494
2495
2496
2497
2498
2499 @SuppressFBWarnings(value = "EI_EXPOSE_REP", justification = "freezeMetadata() replaces this field with an unmodifiable snapshot before compiled tuples are exposed")
2500 public Map<String, Integer> getGlobalVariableOffsetMap() {
2501 return globalVarOffsetMap;
2502 }
2503
2504
2505
2506
2507
2508
2509
2510
2511 @SuppressFBWarnings(value = "EI_EXPOSE_REP", justification = "freezeMetadata() replaces this field with an unmodifiable snapshot before compiled tuples are exposed")
2512 public Map<String, Boolean> getGlobalVariableAarrayMap() {
2513 return globalVarAarrayMap;
2514 }
2515
2516
2517
2518
2519
2520
2521
2522
2523 @SuppressFBWarnings(value = "EI_EXPOSE_REP", justification = "freezeMetadata() replaces this field with an unmodifiable snapshot before compiled tuples are exposed")
2524 public Set<String> getFunctionNameSet() {
2525 return functionNames;
2526 }
2527
2528 private void ensureMetadataMutable() {
2529 if (metadataFrozen) {
2530 throw new IllegalStateException("Tuple metadata is frozen.");
2531 }
2532 }
2533
2534 private static <K, V> Map<K, V> freezeMap(Map<K, V> map) {
2535 if (map.isEmpty()) {
2536 return Collections.emptyMap();
2537 }
2538 return Collections.unmodifiableMap(new HashMap<K, V>(map));
2539 }
2540
2541 private static <T> Set<T> freezeSet(Set<T> set) {
2542 if (set.isEmpty()) {
2543 return Collections.emptySet();
2544 }
2545 return Collections.unmodifiableSet(new HashSet<T>(set));
2546 }
2547
2548 private boolean requiresEvalGlobalFrame(Opcode opcode) {
2549 switch (opcode) {
2550 case ASSIGN:
2551 case ASSIGN_ARRAY:
2552 case DEREFERENCE:
2553 case PLUS_EQ:
2554 case MINUS_EQ:
2555 case MULT_EQ:
2556 case DIV_EQ:
2557 case MOD_EQ:
2558 case POW_EQ:
2559 case PLUS_EQ_ARRAY:
2560 case MINUS_EQ_ARRAY:
2561 case MULT_EQ_ARRAY:
2562 case DIV_EQ_ARRAY:
2563 case MOD_EQ_ARRAY:
2564 case POW_EQ_ARRAY:
2565 case CALL_FUNCTION:
2566 case SET_RETURN_RESULT:
2567 case RETURN_FROM_FUNCTION:
2568 case MATCH:
2569 case DELETE_ARRAY_ELEMENT:
2570 case DELETE_ARRAY:
2571 case ENVIRON_OFFSET:
2572 case ARGC_OFFSET:
2573 case ARGV_OFFSET:
2574 case ASSIGN_ARGC:
2575 case PUSH_ARGC:
2576 return true;
2577 default:
2578 return false;
2579 }
2580 }
2581
2582
2583 private Deque<Integer> linenoStack = new ArrayDeque<Integer>();
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595 public void pushSourceLineNumber(int lineno) {
2596 linenoStack.push(lineno);
2597 }
2598
2599
2600
2601
2602
2603
2604
2605
2606 public void popSourceLineNumber(int lineno) {
2607 linenoStack.pop();
2608 }
2609
2610 }