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