1 /*
2 * Copyright (c) 2022, 2025, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2024, Alibaba Group Holding Limited. All Rights Reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation. Oracle designates this
9 * particular file as subject to the "Classpath" exception as provided
10 * by Oracle in the LICENSE file that accompanied this code.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
23 * or visit www.oracle.com if you need additional information or have any
24 * questions.
25 *
26 */
27 package jdk.internal.classfile.impl;
28
29 import java.lang.classfile.Attribute;
30 import java.lang.classfile.Attributes;
31 import java.lang.classfile.Label;
32 import java.lang.classfile.attribute.StackMapTableAttribute;
33 import java.lang.classfile.constantpool.*;
34 import java.lang.constant.ClassDesc;
35 import java.lang.constant.MethodTypeDesc;
36 import java.util.ArrayList;
37 import java.util.Arrays;
38 import java.util.List;
39 import java.util.Objects;
40 import java.util.stream.Collectors;
41
42 import jdk.internal.classfile.impl.WritableField.UnsetField;
43 import jdk.internal.constant.ClassOrInterfaceDescImpl;
44 import jdk.internal.util.Preconditions;
45
46 import static java.lang.classfile.ClassFile.*;
47 import static java.lang.classfile.constantpool.PoolEntry.*;
48 import static java.lang.constant.ConstantDescs.*;
49 import static jdk.internal.classfile.impl.RawBytecodeHelper.*;
50
51 /**
52 * StackMapGenerator is responsible for stack map frames generation.
53 * <p>
54 * Stack map frames are computed from serialized bytecode similar way they are verified during class loading process.
55 * <p>
56 * The {@linkplain #generate() frames computation} consists of following steps:
57 * <ol>
58 * <li>{@linkplain #detectFrames() Detection} of mandatory stack map frames:<ul>
59 * <li>Mandatory stack map frame include all jump and switch instructions targets,
60 * offsets immediately following {@linkplain #noControlFlow(int) "no control flow"}
61 * and all exception table handlers.
62 * <li>Detection is performed in a single fast pass through the bytecode,
63 * with no auxiliary structures construction nor further instructions processing.
64 * </ul>
65 * <li>Generator loop {@linkplain #processMethod() processing bytecode instructions}:<ul>
66 * <li>Generator loop simulates sequence instructions {@linkplain #processBlock(RawBytecodeHelper) processing effect on the actual stack and locals}.
67 * <li>All mandatory {@linkplain Frame frames} detected in the step #1 are {@linkplain Frame#checkAssignableTo(Frame) retro-filled}
68 * (or {@linkplain Frame#merge(Type, Type[], int, Frame) reverse-merged} in subsequent processing)
69 * with the actual stack and locals for all matching jump, switch and exception handler targets.
70 * <li>All frames modified by reverse merges are marked as {@linkplain Frame#dirty dirty} for further processing.
71 * <li>Code blocks with not yet known entry frame content are skipped and related frames are also marked as dirty.
72 * <li>Generator loop process is repeated until all mandatory frames are cleared or until an error state is reached.
73 * <li>Generator loop always passes all instructions at least once to calculate {@linkplain #maxStack max stack}
74 * and {@linkplain #maxLocals max locals} code attributes.
75 * <li>More than one pass is usually not necessary, except for more complex bytecode sequences.<br>
76 * <i>(Note: experimental measurements showed that more than 99% of the cases required only single pass to clear all frames,
77 * less than 1% of the cases required second pass and remaining 0,01% of the cases required third pass to clear all frames.)</i>.
78 * </ul>
79 * <li>Dead code patching to pass class loading verification:<ul>
80 * <li>Dead code blocks are indicated by frames remaining without content after leaving the Generator loop.
81 * <li>Each dead code block is filled with <code>NOP</code> instructions, terminated with
82 * <code>ATHROW</code> instruction, and removed from exception handlers table.
83 * <li>Dead code block entry frame is set to <code>java.lang.Throwable</code> single stack item and no locals.
84 * </ul>
85 * </ol>
86 * <p>
87 * {@linkplain Frame#merge(Type, Type[], int, Frame) Reverse-merge} of the stack map frames
88 * may in some situations require to determine {@linkplain ClassHierarchyImpl class hierarchy} relations.
89 * <p>
90 * Reverse-merge of individual {@linkplain Type types} is performed when a target frame has already been retro-filled
91 * and it is necessary to adjust its existing stack entries and locals to also match actual stack map frame conditions.
92 * Following tables describe how new target stack entry or local type is calculated, based on the actual frame stack entry or local ("from")
93 * and actual value of the target stack entry or local ("to").
94 *
95 * <table border="1">
96 * <caption>Reverse-merge of general type categories</caption>
97 * <tr><th>to \ from<th>TOP<th>PRIMITIVE<th>UNINITIALIZED<th>REFERENCE
98 * <tr><th>TOP<td>TOP<td>TOP<td>TOP<td>TOP
99 * <tr><th>PRIMITIVE<td>TOP<td><a href="#primitives">Reverse-merge of primitive types</a><td>TOP<td>TOP
100 * <tr><th>UNINITIALIZED<td>TOP<td>TOP<td>Is NEW offset matching ? UNINITIALIZED : TOP<td>TOP
101 * <tr><th>REFERENCE<td>TOP<td>TOP<td>TOP<td><a href="#references">Reverse-merge of reference types</a>
102 * </table>
103 * <p>
104 * <table id="primitives" border="1">
105 * <caption>Reverse-merge of primitive types</caption>
106 * <tr><th>to \ from<th>SHORT<th>BYTE<th>BOOLEAN<th>LONG<th>DOUBLE<th>FLOAT<th>INTEGER
107 * <tr><th>SHORT<td>SHORT<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>SHORT
108 * <tr><th>BYTE<td>TOP<td>BYTE<td>TOP<td>TOP<td>TOP<td>TOP<td>BYTE
109 * <tr><th>BOOLEAN<td>TOP<td>TOP<td>BOOLEAN<td>TOP<td>TOP<td>TOP<td>BOOLEAN
110 * <tr><th>LONG<td>TOP<td>TOP<td>TOP<td>LONG<td>TOP<td>TOP<td>TOP
111 * <tr><th>DOUBLE<td>TOP<td>TOP<td>TOP<td>TOP<td>DOUBLE<td>TOP<td>TOP
112 * <tr><th>FLOAT<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>FLOAT<td>TOP
113 * <tr><th>INTEGER<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>TOP<td>INTEGER
114 * </table>
115 * <p>
116 * <table id="references" border="1">
117 * <caption>Reverse merge of reference types</caption>
118 * <tr><th>to \ from<th>NULL<th>j.l.Object<th>j.l.Cloneable<th>j.i.Serializable<th>ARRAY<th>INTERFACE*<th>OBJECT**
119 * <tr><th>NULL<td>NULL<td>j.l.Object<td>j.l.Cloneable<td>j.i.Serializable<td>ARRAY<td>INTERFACE<td>OBJECT
120 * <tr><th>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object
121 * <tr><th>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Cloneable<td>j.l.Object<td>j.l.Cloneable<td>j.l.Cloneable
122 * <tr><th>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.i.Serializable<td>j.l.Object<td>j.i.Serializable<td>j.i.Serializable
123 * <tr><th>ARRAY<td>ARRAY<td>j.l.Object<td>j.l.Object<td>j.l.Object<td><a href="#arrays">Reverse merge of arrays</a><td>j.l.Object<td>j.l.Object
124 * <tr><th>INTERFACE*<td>INTERFACE<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object
125 * <tr><th>OBJECT**<td>OBJECT<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>j.l.Object<td>Resolved common ancestor
126 * <tr><td colspan="8">*any interface reference except for j.l.Cloneable and j.i.Serializable<br>**any object reference except for j.l.Object
127 * </table>
128 * <p id="arrays">
129 * Array types are reverse-merged as reference to array type constructed from reverse-merged components.
130 * Reference to j.l.Object is an alternate result when construction of the array type is not possible (when reverse-merge of components returned TOP or other non-reference and non-primitive type).
131 * <p>
132 * Custom class hierarchy resolver has been implemented as a part of the library to avoid heavy class loading
133 * and to allow stack maps generation even for code with incomplete dependency classpath.
134 * However stack maps generated with {@linkplain ClassHierarchyImpl#resolve(java.lang.constant.ClassDesc) warnings of unresolved dependencies} may later fail to verify during class loading process.
135 * <p>
136 * Focus of the whole algorithm is on high performance and low memory footprint:<ul>
137 * <li>It does not produce, collect nor visit any complex intermediate structures
138 * <i>(beside {@linkplain RawBytecodeHelper traversing} the {@linkplain #bytecode bytecode in binary form}).</i>
139 * <li>It works with only minimal mandatory stack map frames.
140 * <li>It does not spend time on any non-essential verifications.
141 * </ul>
142 */
143
144 public final class StackMapGenerator {
145
146 static StackMapGenerator of(DirectCodeBuilder dcb, BufWriterImpl buf) {
147 return new StackMapGenerator(
148 dcb,
149 buf.thisClass().asSymbol(),
150 dcb.methodInfo.methodName().stringValue(),
151 dcb.methodInfo.methodTypeSymbol(),
152 (dcb.methodInfo.methodFlags() & ACC_STATIC) != 0,
153 dcb.bytecodesBufWriter.bytecodeView(),
154 dcb.constantPool,
155 dcb.context,
156 buf.getStrictInstanceFields(),
157 dcb.handlers);
158 }
159
160 private static final String OBJECT_INITIALIZER_NAME = "<init>";
161 private static final int FLAG_THIS_UNINIT = 0x01;
162 private static final int FRAME_DEFAULT_CAPACITY = 10;
163 private static final int T_BOOLEAN = 4, T_LONG = 11;
164 private static final Frame[] EMPTY_FRAME_ARRAY = {};
165
166 private static final int ITEM_TOP = 0,
167 ITEM_INTEGER = 1,
168 ITEM_FLOAT = 2,
169 ITEM_DOUBLE = 3,
170 ITEM_LONG = 4,
171 ITEM_NULL = 5,
172 ITEM_UNINITIALIZED_THIS = 6,
173 ITEM_OBJECT = 7,
174 ITEM_UNINITIALIZED = 8,
175 ITEM_BOOLEAN = 9,
176 ITEM_BYTE = 10,
177 ITEM_SHORT = 11,
178 ITEM_CHAR = 12,
179 ITEM_LONG_2ND = 13,
180 ITEM_DOUBLE_2ND = 14;
181
182 private static final Type[] ARRAY_FROM_BASIC_TYPE = {null, null, null, null,
183 Type.BOOLEAN_ARRAY_TYPE, Type.CHAR_ARRAY_TYPE, Type.FLOAT_ARRAY_TYPE, Type.DOUBLE_ARRAY_TYPE,
184 Type.BYTE_ARRAY_TYPE, Type.SHORT_ARRAY_TYPE, Type.INT_ARRAY_TYPE, Type.LONG_ARRAY_TYPE};
185
186 static record RawExceptionCatch(int start, int end, int handler, Type catchType) {}
187
188 private final Type thisType;
189 private final String methodName;
190 private final MethodTypeDesc methodDesc;
191 private final RawBytecodeHelper.CodeRange bytecode;
192 private final SplitConstantPool cp;
193 private final boolean isStatic;
194 private final LabelContext labelContext;
195 private final List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers;
196 private final List<RawExceptionCatch> rawHandlers;
197 private final ClassHierarchyImpl classHierarchy;
198 private final UnsetField[] strictFieldsToPut; // exact-sized, do not modify this copy!
199 private final boolean patchDeadCode;
200 private final boolean filterDeadLabels;
201 private Frame[] frames = EMPTY_FRAME_ARRAY;
202 private int framesCount = 0;
203 private final Frame currentFrame;
204 private int maxStack, maxLocals;
205
206 /**
207 * Primary constructor of the <code>Generator</code> class.
208 * New <code>Generator</code> instance must be created for each individual class/method.
209 * Instance contains only immutable results, all the calculations are processed during instance construction.
210 *
211 * @param labelContext <code>LabelContext</code> instance used to resolve or patch <code>ExceptionHandler</code>
212 * labels to bytecode offsets (or vice versa)
213 * @param thisClass class to generate stack maps for
214 * @param methodName method name to generate stack maps for
215 * @param methodDesc method descriptor to generate stack maps for
216 * @param isStatic information whether the method is static
217 * @param bytecode R/W <code>ByteBuffer</code> wrapping method bytecode, the content is altered in case <code>Generator</code> detects and patches dead code
218 * @param cp R/W <code>ConstantPoolBuilder</code> instance used to resolve all involved CP entries and also generate new entries referenced from the generated stack maps
219 * @param handlers R/W <code>ExceptionHandler</code> list used to detect mandatory frame offsets as well as to determine stack maps in exception handlers
220 * and also to be altered when dead code is detected and must be excluded from exception handlers
221 */
222 public StackMapGenerator(LabelContext labelContext,
223 ClassDesc thisClass,
224 String methodName,
225 MethodTypeDesc methodDesc,
226 boolean isStatic,
227 RawBytecodeHelper.CodeRange bytecode,
228 SplitConstantPool cp,
229 ClassFileImpl context,
230 UnsetField[] strictFields,
231 List<AbstractPseudoInstruction.ExceptionCatchImpl> handlers) {
232 this.thisType = Type.referenceType(thisClass);
233 this.methodName = methodName;
234 this.methodDesc = methodDesc;
235 this.isStatic = isStatic;
236 this.bytecode = bytecode;
237 this.cp = cp;
238 this.labelContext = labelContext;
239 this.handlers = handlers;
240 this.rawHandlers = new ArrayList<>(handlers.size());
241 this.classHierarchy = new ClassHierarchyImpl(context.classHierarchyResolver());
242 this.patchDeadCode = context.patchDeadCode();
243 this.filterDeadLabels = context.dropDeadLabels();
244 this.currentFrame = new Frame(classHierarchy);
245 if (OBJECT_INITIALIZER_NAME.equals(methodName)) {
246 this.strictFieldsToPut = strictFields;
247 } else {
248 this.strictFieldsToPut = UnsetField.EMPTY_ARRAY;
249 }
250 generate();
251 }
252
253 /**
254 * Calculated maximum number of the locals required
255 * @return maximum number of the locals required
256 */
257 public int maxLocals() {
258 return maxLocals;
259 }
260
261 /**
262 * Calculated maximum stack size required
263 * @return maximum stack size required
264 */
265 public int maxStack() {
266 return maxStack;
267 }
268
269 private Frame getFrame(int offset) {
270 //binary search over frames ordered by offset
271 int low = 0;
272 int high = framesCount - 1;
273 while (low <= high) {
274 int mid = (low + high) >>> 1;
275 var f = frames[mid];
276 if (f.offset < offset)
277 low = mid + 1;
278 else if (f.offset > offset)
279 high = mid - 1;
280 else
281 return f;
282 }
283 return null;
284 }
285
286 private void checkJumpTarget(Frame frame, int target) {
287 frame.checkAssignableTo(getFrame(target));
288 }
289
290 private int exMin, exMax;
291
292 private boolean isAnyFrameDirty() {
293 for (int i = 0; i < framesCount; i++) {
294 if (frames[i].dirty) return true;
295 }
296 return false;
297 }
298
299 private void generate() {
300 exMin = bytecode.length();
301 exMax = -1;
302 if (!handlers.isEmpty()) {
303 generateHandlers();
304 }
305 detectFrames();
306 do {
307 processMethod();
308 } while (isAnyFrameDirty());
309 maxLocals = currentFrame.frameMaxLocals;
310 maxStack = currentFrame.frameMaxStack;
311
312 //dead code patching
313 for (int i = 0; i < framesCount; i++) {
314 var frame = frames[i];
315 if (frame.flags == -1) {
316 deadCodePatching(frame, i);
317 }
318 }
319 }
320
321 private void generateHandlers() {
322 var labelContext = this.labelContext;
323 for (int i = 0; i < handlers.size(); i++) {
324 var exhandler = handlers.get(i);
325 int start_pc = labelContext.labelToBci(exhandler.tryStart());
326 int end_pc = labelContext.labelToBci(exhandler.tryEnd());
327 int handler_pc = labelContext.labelToBci(exhandler.handler());
328 if (start_pc >= 0 && end_pc >= 0 && end_pc > start_pc && handler_pc >= 0) {
329 if (start_pc < exMin) exMin = start_pc;
330 if (end_pc > exMax) exMax = end_pc;
331 var catchType = exhandler.catchType();
332 rawHandlers.add(new RawExceptionCatch(start_pc, end_pc, handler_pc,
333 catchType.isPresent() ? cpIndexToType(catchType.get().index(), cp)
334 : Type.THROWABLE_TYPE));
335 }
336 }
337 }
338
339 private void deadCodePatching(Frame frame, int i) {
340 if (!patchDeadCode) throw generatorError("Unable to generate stack map frame for dead code", frame.offset);
341 //patch frame
342 frame.pushStack(Type.THROWABLE_TYPE);
343 if (maxStack < 1) maxStack = 1;
344 int end = (i < framesCount - 1 ? frames[i + 1].offset : bytecode.length()) - 1;
345 //patch bytecode
346 var arr = bytecode.array();
347 Arrays.fill(arr, frame.offset, end, (byte) NOP);
348 arr[end] = (byte) ATHROW;
349 //patch handlers
350 removeRangeFromExcTable(frame.offset, end + 1);
351 }
352
353 private void removeRangeFromExcTable(int rangeStart, int rangeEnd) {
354 var it = handlers.listIterator();
355 while (it.hasNext()) {
356 var e = it.next();
357 int handlerStart = labelContext.labelToBci(e.tryStart());
358 int handlerEnd = labelContext.labelToBci(e.tryEnd());
359 if (rangeStart >= handlerEnd || rangeEnd <= handlerStart) {
360 //out of range
361 continue;
362 }
363 if (rangeStart <= handlerStart) {
364 if (rangeEnd >= handlerEnd) {
365 //complete removal
366 it.remove();
367 } else {
368 //cut from left
369 Label newStart = labelContext.newLabel();
370 labelContext.setLabelTarget(newStart, rangeEnd);
371 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
372 }
373 } else if (rangeEnd >= handlerEnd) {
374 //cut from right
375 Label newEnd = labelContext.newLabel();
376 labelContext.setLabelTarget(newEnd, rangeStart);
377 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
378 } else {
379 //split
380 Label newStart = labelContext.newLabel();
381 labelContext.setLabelTarget(newStart, rangeEnd);
382 Label newEnd = labelContext.newLabel();
383 labelContext.setLabelTarget(newEnd, rangeStart);
384 it.set(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), e.tryStart(), newEnd, e.catchType()));
385 it.add(new AbstractPseudoInstruction.ExceptionCatchImpl(e.handler(), newStart, e.tryEnd(), e.catchType()));
386 }
387 }
388 }
389
390 /**
391 * Getter of the generated <code>StackMapTableAttribute</code> or null if stack map is empty
392 * @return <code>StackMapTableAttribute</code> or null if stack map is empty
393 */
394 public Attribute<? extends StackMapTableAttribute> stackMapTableAttribute() {
395 return framesCount == 0 ? null : new UnboundAttribute.AdHocAttribute<>(Attributes.stackMapTable()) {
396 @Override
397 public void writeBody(BufWriterImpl b) {
398 int countPos = b.size();
399 b.writeU2(framesCount);
400 int extraFrameCount = 0;
401 Frame prevFrame = new Frame(classHierarchy);
402 prevFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType, strictFieldsToPut);
403 prevFrame.trimAndCompress();
404 for (int i = 0; i < framesCount; i++) {
405 var fr = frames[i];
406 fr.trimAndCompress();
407 extraFrameCount += fr.writeTo(b, prevFrame, cp);
408 prevFrame = fr;
409 }
410 if (extraFrameCount > 0) {
411 int size = framesCount + extraFrameCount;
412 if (size != (char) size) {
413 throw generatorError("Too many frames: " + size);
414 }
415 b.patchU2(countPos, size);
416 }
417 }
418
419 @Override
420 public Utf8Entry attributeName() {
421 return cp.utf8Entry(Attributes.NAME_STACK_MAP_TABLE);
422 }
423 };
424 }
425
426 private static Type cpIndexToType(int index, ConstantPoolBuilder cp) {
427 return Type.referenceType(cp.entryByIndex(index, ClassEntry.class).asSymbol());
428 }
429
430 private void processMethod() {
431 var frames = this.frames;
432 var currentFrame = this.currentFrame;
433 currentFrame.setLocalsFromArg(methodName, methodDesc, isStatic, thisType, strictFieldsToPut);
434 currentFrame.stackSize = 0;
435 currentFrame.offset = -1;
436 int stackmapIndex = 0;
437 var bcs = bytecode.start();
438 boolean ncf = false;
439 while (bcs.next()) {
440 currentFrame.offset = bcs.bci();
441 if (stackmapIndex < framesCount) {
442 int thisOffset = frames[stackmapIndex].offset;
443 if (ncf && thisOffset > bcs.bci()) {
444 throw generatorError("Expecting a stack map frame");
445 }
446 if (thisOffset == bcs.bci()) {
447 Frame nextFrame = frames[stackmapIndex++];
448 if (!ncf) {
449 currentFrame.checkAssignableTo(nextFrame);
450 }
451 while (!nextFrame.dirty) { //skip unmatched frames
452 if (stackmapIndex == framesCount) return; //skip the rest of this round
453 nextFrame = frames[stackmapIndex++];
454 }
455 bcs.reset(nextFrame.offset); //skip code up-to the next frame
456 bcs.next();
457 currentFrame.offset = bcs.bci();
458 currentFrame.copyFrom(nextFrame);
459 nextFrame.dirty = false;
460 } else if (thisOffset < bcs.bci()) {
461 throw generatorError("Bad stack map offset");
462 }
463 } else if (ncf) {
464 throw generatorError("Expecting a stack map frame");
465 }
466 ncf = processBlock(bcs);
467 }
468 }
469
470 private boolean processBlock(RawBytecodeHelper bcs) {
471 int opcode = bcs.opcode();
472 boolean ncf = false;
473 boolean this_uninit = false;
474 boolean verified_exc_handlers = false;
475 int bci = bcs.bci();
476 Type type1, type2, type3, type4;
477 if (RawBytecodeHelper.isStoreIntoLocal(opcode) && bci >= exMin && bci < exMax) {
478 processExceptionHandlerTargets(bci, this_uninit);
479 verified_exc_handlers = true;
480 }
481 switch (opcode) {
482 case NOP -> {}
483 case RETURN -> {
484 ncf = true;
485 }
486 case ACONST_NULL ->
487 currentFrame.pushStack(Type.NULL_TYPE);
488 case ICONST_M1, ICONST_0, ICONST_1, ICONST_2, ICONST_3, ICONST_4, ICONST_5, SIPUSH, BIPUSH ->
489 currentFrame.pushStack(Type.INTEGER_TYPE);
490 case LCONST_0, LCONST_1 ->
491 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
492 case FCONST_0, FCONST_1, FCONST_2 ->
493 currentFrame.pushStack(Type.FLOAT_TYPE);
494 case DCONST_0, DCONST_1 ->
495 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
496 case LDC ->
497 processLdc(bcs.getIndexU1());
498 case LDC_W, LDC2_W ->
499 processLdc(bcs.getIndexU2());
500 case ILOAD ->
501 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.INTEGER_TYPE);
502 case ILOAD_0, ILOAD_1, ILOAD_2, ILOAD_3 ->
503 currentFrame.checkLocal(opcode - ILOAD_0).pushStack(Type.INTEGER_TYPE);
504 case LLOAD ->
505 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
506 case LLOAD_0, LLOAD_1, LLOAD_2, LLOAD_3 ->
507 currentFrame.checkLocal(opcode - LLOAD_0 + 1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
508 case FLOAD ->
509 currentFrame.checkLocal(bcs.getIndex()).pushStack(Type.FLOAT_TYPE);
510 case FLOAD_0, FLOAD_1, FLOAD_2, FLOAD_3 ->
511 currentFrame.checkLocal(opcode - FLOAD_0).pushStack(Type.FLOAT_TYPE);
512 case DLOAD ->
513 currentFrame.checkLocal(bcs.getIndex() + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
514 case DLOAD_0, DLOAD_1, DLOAD_2, DLOAD_3 ->
515 currentFrame.checkLocal(opcode - DLOAD_0 + 1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
516 case ALOAD ->
517 currentFrame.pushStack(currentFrame.getLocal(bcs.getIndex()));
518 case ALOAD_0, ALOAD_1, ALOAD_2, ALOAD_3 ->
519 currentFrame.pushStack(currentFrame.getLocal(opcode - ALOAD_0));
520 case IALOAD, BALOAD, CALOAD, SALOAD ->
521 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
522 case LALOAD ->
523 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
524 case FALOAD ->
525 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
526 case DALOAD ->
527 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
528 case AALOAD ->
529 currentFrame.pushStack((type1 = currentFrame.decStack(1).popStack()) == Type.NULL_TYPE ? Type.NULL_TYPE : type1.getComponent());
530 case ISTORE ->
531 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.INTEGER_TYPE);
532 case ISTORE_0, ISTORE_1, ISTORE_2, ISTORE_3 ->
533 currentFrame.decStack(1).setLocal(opcode - ISTORE_0, Type.INTEGER_TYPE);
534 case LSTORE ->
535 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.LONG_TYPE, Type.LONG2_TYPE);
536 case LSTORE_0, LSTORE_1, LSTORE_2, LSTORE_3 ->
537 currentFrame.decStack(2).setLocal2(opcode - LSTORE_0, Type.LONG_TYPE, Type.LONG2_TYPE);
538 case FSTORE ->
539 currentFrame.decStack(1).setLocal(bcs.getIndex(), Type.FLOAT_TYPE);
540 case FSTORE_0, FSTORE_1, FSTORE_2, FSTORE_3 ->
541 currentFrame.decStack(1).setLocal(opcode - FSTORE_0, Type.FLOAT_TYPE);
542 case DSTORE ->
543 currentFrame.decStack(2).setLocal2(bcs.getIndex(), Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
544 case DSTORE_0, DSTORE_1, DSTORE_2, DSTORE_3 ->
545 currentFrame.decStack(2).setLocal2(opcode - DSTORE_0, Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
546 case ASTORE ->
547 currentFrame.setLocal(bcs.getIndex(), currentFrame.popStack());
548 case ASTORE_0, ASTORE_1, ASTORE_2, ASTORE_3 ->
549 currentFrame.setLocal(opcode - ASTORE_0, currentFrame.popStack());
550 case LASTORE, DASTORE ->
551 currentFrame.decStack(4);
552 case IASTORE, BASTORE, CASTORE, SASTORE, FASTORE, AASTORE ->
553 currentFrame.decStack(3);
554 case POP, MONITORENTER, MONITOREXIT ->
555 currentFrame.decStack(1);
556 case POP2 ->
557 currentFrame.decStack(2);
558 case DUP ->
559 currentFrame.pushStack(type1 = currentFrame.popStack()).pushStack(type1);
560 case DUP_X1 -> {
561 type1 = currentFrame.popStack();
562 type2 = currentFrame.popStack();
563 currentFrame.pushStack(type1).pushStack(type2).pushStack(type1);
564 }
565 case DUP_X2 -> {
566 type1 = currentFrame.popStack();
567 type2 = currentFrame.popStack();
568 type3 = currentFrame.popStack();
569 currentFrame.pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
570 }
571 case DUP2 -> {
572 type1 = currentFrame.popStack();
573 type2 = currentFrame.popStack();
574 currentFrame.pushStack(type2).pushStack(type1).pushStack(type2).pushStack(type1);
575 }
576 case DUP2_X1 -> {
577 type1 = currentFrame.popStack();
578 type2 = currentFrame.popStack();
579 type3 = currentFrame.popStack();
580 currentFrame.pushStack(type2).pushStack(type1).pushStack(type3).pushStack(type2).pushStack(type1);
581 }
582 case DUP2_X2 -> {
583 type1 = currentFrame.popStack();
584 type2 = currentFrame.popStack();
585 type3 = currentFrame.popStack();
586 type4 = currentFrame.popStack();
587 currentFrame.pushStack(type2).pushStack(type1).pushStack(type4).pushStack(type3).pushStack(type2).pushStack(type1);
588 }
589 case SWAP -> {
590 type1 = currentFrame.popStack();
591 type2 = currentFrame.popStack();
592 currentFrame.pushStack(type1);
593 currentFrame.pushStack(type2);
594 }
595 case IADD, ISUB, IMUL, IDIV, IREM, ISHL, ISHR, IUSHR, IOR, IXOR, IAND ->
596 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
597 case INEG, ARRAYLENGTH, INSTANCEOF ->
598 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
599 case LADD, LSUB, LMUL, LDIV, LREM, LAND, LOR, LXOR ->
600 currentFrame.decStack(4).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
601 case LNEG ->
602 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
603 case LSHL, LSHR, LUSHR ->
604 currentFrame.decStack(3).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
605 case FADD, FSUB, FMUL, FDIV, FREM ->
606 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
607 case FNEG ->
608 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
609 case DADD, DSUB, DMUL, DDIV, DREM ->
610 currentFrame.decStack(4).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
611 case DNEG ->
612 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
613 case IINC ->
614 currentFrame.checkLocal(bcs.getIndex());
615 case I2L ->
616 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
617 case L2I ->
618 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
619 case I2F ->
620 currentFrame.decStack(1).pushStack(Type.FLOAT_TYPE);
621 case I2D ->
622 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
623 case L2F ->
624 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
625 case L2D ->
626 currentFrame.decStack(2).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
627 case F2I ->
628 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
629 case F2L ->
630 currentFrame.decStack(1).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
631 case F2D ->
632 currentFrame.decStack(1).pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
633 case D2L ->
634 currentFrame.decStack(2).pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
635 case D2F ->
636 currentFrame.decStack(2).pushStack(Type.FLOAT_TYPE);
637 case I2B, I2C, I2S ->
638 currentFrame.decStack(1).pushStack(Type.INTEGER_TYPE);
639 case LCMP, DCMPL, DCMPG ->
640 currentFrame.decStack(4).pushStack(Type.INTEGER_TYPE);
641 case FCMPL, FCMPG, D2I ->
642 currentFrame.decStack(2).pushStack(Type.INTEGER_TYPE);
643 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE, IF_ICMPGT, IF_ICMPLE, IF_ACMPEQ, IF_ACMPNE ->
644 checkJumpTarget(currentFrame.decStack(2), bcs.dest());
645 case IFEQ, IFNE, IFLT, IFGE, IFGT, IFLE, IFNULL, IFNONNULL ->
646 checkJumpTarget(currentFrame.decStack(1), bcs.dest());
647 case GOTO -> {
648 checkJumpTarget(currentFrame, bcs.dest());
649 ncf = true;
650 }
651 case GOTO_W -> {
652 checkJumpTarget(currentFrame, bcs.destW());
653 ncf = true;
654 }
655 case TABLESWITCH, LOOKUPSWITCH -> {
656 processSwitch(bcs);
657 ncf = true;
658 }
659 case LRETURN, DRETURN -> {
660 currentFrame.decStack(2);
661 ncf = true;
662 }
663 case IRETURN, FRETURN, ARETURN, ATHROW -> {
664 currentFrame.decStack(1);
665 ncf = true;
666 }
667 case GETSTATIC, PUTSTATIC, GETFIELD, PUTFIELD ->
668 processFieldInstructions(bcs);
669 case INVOKEVIRTUAL, INVOKESPECIAL, INVOKESTATIC, INVOKEINTERFACE, INVOKEDYNAMIC ->
670 this_uninit = processInvokeInstructions(bcs, (bci >= exMin && bci < exMax), this_uninit);
671 case NEW ->
672 currentFrame.pushStack(Type.uninitializedType(bci));
673 case NEWARRAY ->
674 currentFrame.decStack(1).pushStack(getNewarrayType(bcs.getIndex()));
675 case ANEWARRAY ->
676 processAnewarray(bcs.getIndexU2());
677 case CHECKCAST ->
678 currentFrame.decStack(1).pushStack(cpIndexToType(bcs.getIndexU2(), cp));
679 case MULTIANEWARRAY -> {
680 type1 = cpIndexToType(bcs.getIndexU2(), cp);
681 int dim = bcs.getU1Unchecked(bcs.bci() + 3);
682 for (int i = 0; i < dim; i++) {
683 currentFrame.popStack();
684 }
685 currentFrame.pushStack(type1);
686 }
687 case JSR, JSR_W, RET ->
688 throw generatorError("Instructions jsr, jsr_w, or ret must not appear in the class file version >= 51.0");
689 default ->
690 throw generatorError(String.format("Bad instruction: %02x", opcode));
691 }
692 if (!verified_exc_handlers && bci >= exMin && bci < exMax) {
693 processExceptionHandlerTargets(bci, this_uninit);
694 }
695 return ncf;
696 }
697
698 private void processExceptionHandlerTargets(int bci, boolean this_uninit) {
699 for (var ex : rawHandlers) {
700 if (bci == ex.start || (currentFrame.localsChanged && bci > ex.start && bci < ex.end)) {
701 int flags = currentFrame.flags;
702 if (this_uninit) flags |= FLAG_THIS_UNINIT;
703 Frame newFrame = currentFrame.frameInExceptionHandler(flags, ex.catchType);
704 checkJumpTarget(newFrame, ex.handler);
705 }
706 }
707 currentFrame.localsChanged = false;
708 }
709
710 private void processLdc(int index) {
711 switch (cp.entryByIndex(index).tag()) {
712 case TAG_UTF8 ->
713 currentFrame.pushStack(Type.OBJECT_TYPE);
714 case TAG_STRING ->
715 currentFrame.pushStack(Type.STRING_TYPE);
716 case TAG_CLASS ->
717 currentFrame.pushStack(Type.CLASS_TYPE);
718 case TAG_INTEGER ->
719 currentFrame.pushStack(Type.INTEGER_TYPE);
720 case TAG_FLOAT ->
721 currentFrame.pushStack(Type.FLOAT_TYPE);
722 case TAG_DOUBLE ->
723 currentFrame.pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
724 case TAG_LONG ->
725 currentFrame.pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
726 case TAG_METHOD_HANDLE ->
727 currentFrame.pushStack(Type.METHOD_HANDLE_TYPE);
728 case TAG_METHOD_TYPE ->
729 currentFrame.pushStack(Type.METHOD_TYPE);
730 case TAG_DYNAMIC ->
731 currentFrame.pushStack(cp.entryByIndex(index, ConstantDynamicEntry.class).asSymbol().constantType());
732 default ->
733 throw generatorError("CP entry #%d %s is not loadable constant".formatted(index, cp.entryByIndex(index).tag()));
734 }
735 }
736
737 private void processSwitch(RawBytecodeHelper bcs) {
738 int bci = bcs.bci();
739 int alignedBci = RawBytecodeHelper.align(bci + 1);
740 int defaultOffset = bcs.getIntUnchecked(alignedBci);
741 int keys, delta;
742 currentFrame.popStack();
743 if (bcs.opcode() == TABLESWITCH) {
744 int low = bcs.getIntUnchecked(alignedBci + 4);
745 int high = bcs.getIntUnchecked(alignedBci + 2 * 4);
746 if (low > high) {
747 throw generatorError("low must be less than or equal to high in tableswitch");
748 }
749 keys = high - low + 1;
750 if (keys < 0) {
751 throw generatorError("too many keys in tableswitch");
752 }
753 delta = 1;
754 } else {
755 keys = bcs.getIntUnchecked(alignedBci + 4);
756 if (keys < 0) {
757 throw generatorError("number of keys in lookupswitch less than 0");
758 }
759 delta = 2;
760 for (int i = 0; i < (keys - 1); i++) {
761 int this_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i) * 4);
762 int next_key = bcs.getIntUnchecked(alignedBci + (2 + 2 * i + 2) * 4);
763 if (this_key >= next_key) {
764 throw generatorError("Bad lookupswitch instruction");
765 }
766 }
767 }
768 int target = bci + defaultOffset;
769 checkJumpTarget(currentFrame, target);
770 for (int i = 0; i < keys; i++) {
771 target = bci + bcs.getIntUnchecked(alignedBci + (3 + i * delta) * 4);
772 checkJumpTarget(currentFrame, target);
773 }
774 }
775
776 private void processFieldInstructions(RawBytecodeHelper bcs) {
777 var nameAndType = cp.entryByIndex(bcs.getIndexU2(), MemberRefEntry.class).nameAndType();
778 var desc = Util.fieldTypeSymbol(nameAndType.type());
779 var currentFrame = this.currentFrame;
780 switch (bcs.opcode()) {
781 case GETSTATIC ->
782 currentFrame.pushStack(desc);
783 case PUTSTATIC -> {
784 currentFrame.decStack(Util.isDoubleSlot(desc) ? 2 : 1);
785 }
786 case GETFIELD -> {
787 currentFrame.decStack(1);
788 currentFrame.pushStack(desc);
789 }
790 case PUTFIELD -> {
791 if (strictFieldsToPut.length > 0) {
792 currentFrame.putStrictField(nameAndType);
793 }
794 currentFrame.decStack(Util.isDoubleSlot(desc) ? 3 : 2);
795 }
796 default -> throw new AssertionError("Should not reach here");
797 }
798 }
799
800 private boolean processInvokeInstructions(RawBytecodeHelper bcs, boolean inTryBlock, boolean thisUninit) {
801 int index = bcs.getIndexU2();
802 int opcode = bcs.opcode();
803 var nameAndType = opcode == INVOKEDYNAMIC
804 ? cp.entryByIndex(index, InvokeDynamicEntry.class).nameAndType()
805 : cp.entryByIndex(index, MemberRefEntry.class).nameAndType();
806 var mDesc = Util.methodTypeSymbol(nameAndType.type());
807 int bci = bcs.bci();
808 var currentFrame = this.currentFrame;
809 currentFrame.decStack(Util.parameterSlots(mDesc));
810 if (opcode != INVOKESTATIC && opcode != INVOKEDYNAMIC) {
811 if (nameAndType.name().equalsString(OBJECT_INITIALIZER_NAME)) {
812 Type type = currentFrame.popStack();
813 if (type == Type.UNITIALIZED_THIS_TYPE) {
814 if (inTryBlock) {
815 processExceptionHandlerTargets(bci, true);
816 }
817 var owner = cp.entryByIndex(index, MemberRefEntry.class).owner();
818 if (!owner.name().equalsString(((ClassOrInterfaceDescImpl) thisType.sym).internalName())
819 && currentFrame.unsetFieldsSize != 0) {
820 throw generatorError("Unset fields mismatch");
821 }
822 currentFrame.initializeObject(type, thisType);
823 currentFrame.unsetFieldsSize = 0;
824 currentFrame.unsetFields = UnsetField.EMPTY_ARRAY;
825 thisUninit = true;
826 } else if (type.tag == ITEM_UNINITIALIZED) {
827 Type new_class_type = cpIndexToType(bcs.getU2(type.bci + 1), cp);
828 if (inTryBlock) {
829 processExceptionHandlerTargets(bci, thisUninit);
830 }
831 currentFrame.initializeObject(type, new_class_type);
832 } else {
833 throw generatorError("Bad operand type when invoking <init>");
834 }
835 } else {
836 currentFrame.decStack(1);
837 }
838 }
839 currentFrame.pushStack(mDesc.returnType());
840 return thisUninit;
841 }
842
843 private Type getNewarrayType(int index) {
844 if (index < T_BOOLEAN || index > T_LONG) throw generatorError("Illegal newarray instruction type %d".formatted(index));
845 return ARRAY_FROM_BASIC_TYPE[index];
846 }
847
848 private void processAnewarray(int index) {
849 currentFrame.popStack();
850 currentFrame.pushStack(cpIndexToType(index, cp).toArray());
851 }
852
853 /**
854 * {@return the generator error with attached details}
855 * @param msg error message
856 */
857 private IllegalArgumentException generatorError(String msg) {
858 return generatorError(msg, currentFrame.offset);
859 }
860
861 /**
862 * {@return the generator error with attached details}
863 * @param msg error message
864 * @param offset bytecode offset where the error occurred
865 */
866 private IllegalArgumentException generatorError(String msg, int offset) {
867 var sb = new StringBuilder("%s at bytecode offset %d of method %s(%s)".formatted(
868 msg,
869 offset,
870 methodName,
871 methodDesc.parameterList().stream().map(ClassDesc::displayName).collect(Collectors.joining(","))));
872 Util.dumpMethod(cp, thisType.sym(), methodName, methodDesc, isStatic ? ACC_STATIC : 0, bytecode, sb::append);
873 return new IllegalArgumentException(sb.toString());
874 }
875
876 /**
877 * Performs detection of mandatory stack map frames in a single bytecode traversing pass
878 * @return detected frames
879 */
880 private void detectFrames() {
881 var bcs = bytecode.start();
882 boolean no_control_flow = false;
883 int opcode, bci = 0;
884 while (bcs.next()) try {
885 opcode = bcs.opcode();
886 bci = bcs.bci();
887 if (no_control_flow) {
888 addFrame(bci);
889 }
890 no_control_flow = switch (opcode) {
891 case GOTO -> {
892 addFrame(bcs.dest());
893 yield true;
894 }
895 case GOTO_W -> {
896 addFrame(bcs.destW());
897 yield true;
898 }
899 case IF_ICMPEQ, IF_ICMPNE, IF_ICMPLT, IF_ICMPGE,
900 IF_ICMPGT, IF_ICMPLE, IFEQ, IFNE,
901 IFLT, IFGE, IFGT, IFLE, IF_ACMPEQ,
902 IF_ACMPNE , IFNULL , IFNONNULL -> {
903 addFrame(bcs.dest());
904 yield false;
905 }
906 case TABLESWITCH, LOOKUPSWITCH -> {
907 int aligned_bci = RawBytecodeHelper.align(bci + 1);
908 int default_ofset = bcs.getIntUnchecked(aligned_bci);
909 int keys, delta;
910 if (bcs.opcode() == TABLESWITCH) {
911 int low = bcs.getIntUnchecked(aligned_bci + 4);
912 int high = bcs.getIntUnchecked(aligned_bci + 2 * 4);
913 keys = high - low + 1;
914 delta = 1;
915 } else {
916 keys = bcs.getIntUnchecked(aligned_bci + 4);
917 delta = 2;
918 }
919 addFrame(bci + default_ofset);
920 for (int i = 0; i < keys; i++) {
921 addFrame(bci + bcs.getIntUnchecked(aligned_bci + (3 + i * delta) * 4));
922 }
923 yield true;
924 }
925 case IRETURN, LRETURN, FRETURN, DRETURN,
926 ARETURN, RETURN, ATHROW -> true;
927 default -> false;
928 };
929 } catch (IllegalArgumentException iae) {
930 throw generatorError("Detected branch target out of bytecode range", bci);
931 }
932 for (int i = 0; i < rawHandlers.size(); i++) try {
933 addFrame(rawHandlers.get(i).handler());
934 } catch (IllegalArgumentException iae) {
935 if (!filterDeadLabels)
936 throw generatorError("Detected exception handler out of bytecode range");
937 }
938 }
939
940 private void addFrame(int offset) {
941 Preconditions.checkIndex(offset, bytecode.length(), RawBytecodeHelper.IAE_FORMATTER);
942 var frames = this.frames;
943 int i = 0, framesCount = this.framesCount;
944 for (; i < framesCount; i++) {
945 var frameOffset = frames[i].offset;
946 if (frameOffset == offset) {
947 return;
948 }
949 if (frameOffset > offset) {
950 break;
951 }
952 }
953 if (framesCount >= frames.length) {
954 int newCapacity = framesCount + 8;
955 this.frames = frames = framesCount == 0 ? new Frame[newCapacity] : Arrays.copyOf(frames, newCapacity);
956 }
957 if (i != framesCount) {
958 System.arraycopy(frames, i, frames, i + 1, framesCount - i);
959 }
960 frames[i] = new Frame(offset, classHierarchy);
961 this.framesCount = framesCount + 1;
962 }
963
964 private final class Frame {
965
966 int offset;
967 int localsSize, stackSize, unsetFieldsSize;
968 int flags;
969 int frameMaxStack = 0, frameMaxLocals = 0;
970 boolean dirty = false;
971 boolean localsChanged = false;
972
973 private final ClassHierarchyImpl classHierarchy;
974
975 private Type[] locals, stack;
976 private UnsetField[] unsetFields = UnsetField.EMPTY_ARRAY; // sorted, modifiable oversized array
977
978 Frame(ClassHierarchyImpl classHierarchy) {
979 this(-1, 0, 0, 0, null, null, classHierarchy);
980 }
981
982 Frame(int offset, ClassHierarchyImpl classHierarchy) {
983 this(offset, -1, 0, 0, null, null, classHierarchy);
984 }
985
986 Frame(int offset, int flags, int locals_size, int stack_size, Type[] locals, Type[] stack, ClassHierarchyImpl classHierarchy) {
987 this.offset = offset;
988 this.localsSize = locals_size;
989 this.stackSize = stack_size;
990 this.flags = flags;
991 this.locals = locals;
992 this.stack = stack;
993 this.classHierarchy = classHierarchy;
994 }
995
996 @Override
997 public String toString() {
998 return (dirty ? "frame* @" : "frame @") + offset + " with locals " + (locals == null ? "[]" : Arrays.asList(locals).subList(0, localsSize)) + " and stack " + (stack == null ? "[]" : Arrays.asList(stack).subList(0, stackSize));
999 }
1000
1001 Frame pushStack(ClassDesc desc) {
1002 if (desc == CD_long) return pushStack(Type.LONG_TYPE, Type.LONG2_TYPE);
1003 if (desc == CD_double) return pushStack(Type.DOUBLE_TYPE, Type.DOUBLE2_TYPE);
1004 return desc == CD_void ? this
1005 : pushStack(
1006 desc.isPrimitive()
1007 ? (desc == CD_float ? Type.FLOAT_TYPE : Type.INTEGER_TYPE)
1008 : Type.referenceType(desc));
1009 }
1010
1011 Frame pushStack(Type type) {
1012 checkStack(stackSize);
1013 stack[stackSize++] = type;
1014 return this;
1015 }
1016
1017 Frame pushStack(Type type1, Type type2) {
1018 checkStack(stackSize + 1);
1019 stack[stackSize++] = type1;
1020 stack[stackSize++] = type2;
1021 return this;
1022 }
1023
1024 Type popStack() {
1025 if (stackSize < 1) throw generatorError("Operand stack underflow");
1026 return stack[--stackSize];
1027 }
1028
1029 Frame decStack(int size) {
1030 stackSize -= size;
1031 if (stackSize < 0) throw generatorError("Operand stack underflow");
1032 return this;
1033 }
1034
1035 Frame frameInExceptionHandler(int flags, Type excType) {
1036 return new Frame(offset, flags, localsSize, 1, locals, new Type[] {excType}, classHierarchy);
1037 }
1038
1039 void initializeObject(Type old_object, Type new_object) {
1040 int i;
1041 for (i = 0; i < localsSize; i++) {
1042 if (locals[i].equals(old_object)) {
1043 locals[i] = new_object;
1044 localsChanged = true;
1045 }
1046 }
1047 for (i = 0; i < stackSize; i++) {
1048 if (stack[i].equals(old_object)) {
1049 stack[i] = new_object;
1050 }
1051 }
1052 if (old_object == Type.UNITIALIZED_THIS_TYPE) {
1053 flags &= ~FLAG_THIS_UNINIT;
1054 assert flags == 0 : flags;
1055 }
1056 }
1057
1058 Frame checkLocal(int index) {
1059 if (index >= frameMaxLocals) frameMaxLocals = index + 1;
1060 if (locals == null) {
1061 locals = new Type[index + FRAME_DEFAULT_CAPACITY];
1062 Arrays.fill(locals, Type.TOP_TYPE);
1063 } else if (index >= locals.length) {
1064 int current = locals.length;
1065 locals = Arrays.copyOf(locals, index + FRAME_DEFAULT_CAPACITY);
1066 Arrays.fill(locals, current, locals.length, Type.TOP_TYPE);
1067 }
1068 return this;
1069 }
1070
1071 void putStrictField(NameAndTypeEntry nat) {
1072 int shift = 0;
1073 var array = unsetFields;
1074 for (int i = 0; i < unsetFieldsSize; i++) {
1075 var f = array[i];
1076 if (f.name().equals(nat.name()) && f.type().equals(nat.type())) {
1077 shift++;
1078 } else if (shift != 0) {
1079 array[i - shift] = array[i];
1080 array[i] = null;
1081 }
1082 }
1083 if (shift > 1) {
1084 throw generatorError(nat + "; discovered " + shift);
1085 }
1086 unsetFieldsSize -= shift;
1087 }
1088
1089 private void checkStack(int index) {
1090 if (index >= frameMaxStack) frameMaxStack = index + 1;
1091 if (stack == null) {
1092 stack = new Type[index + FRAME_DEFAULT_CAPACITY];
1093 Arrays.fill(stack, Type.TOP_TYPE);
1094 } else if (index >= stack.length) {
1095 int current = stack.length;
1096 stack = Arrays.copyOf(stack, index + FRAME_DEFAULT_CAPACITY);
1097 Arrays.fill(stack, current, stack.length, Type.TOP_TYPE);
1098 }
1099 }
1100
1101 private void setLocalRawInternal(int index, Type type) {
1102 checkLocal(index);
1103 localsChanged |= !type.equals(locals[index]);
1104 locals[index] = type;
1105 }
1106
1107 void setLocalsFromArg(String name, MethodTypeDesc methodDesc, boolean isStatic, Type thisKlass, UnsetField[] strictFieldsToPut) {
1108 int localsSize = 0;
1109 // Pre-emptively create a locals array that encompass all parameter slots
1110 checkLocal(Util.parameterSlots(methodDesc) + (isStatic ? -1 : 0));
1111 Type type;
1112 Type[] locals = this.locals;
1113 if (!isStatic) {
1114 if (OBJECT_INITIALIZER_NAME.equals(name) && !CD_Object.equals(thisKlass.sym)) {
1115 int strictFieldCount = strictFieldsToPut.length;
1116 this.unsetFields = UnsetField.copyArray(strictFieldsToPut, strictFieldCount);
1117 this.unsetFieldsSize = strictFieldCount;
1118 type = Type.UNITIALIZED_THIS_TYPE;
1119 this.flags = FLAG_THIS_UNINIT;
1120 } else {
1121 this.unsetFields = UnsetField.EMPTY_ARRAY;
1122 this.unsetFieldsSize = 0;
1123 type = thisKlass;
1124 this.flags = 0;
1125 }
1126 locals[localsSize++] = type;
1127 }
1128 for (int i = 0; i < methodDesc.parameterCount(); i++) {
1129 var desc = methodDesc.parameterType(i);
1130 if (desc == CD_long) {
1131 locals[localsSize ] = Type.LONG_TYPE;
1132 locals[localsSize + 1] = Type.LONG2_TYPE;
1133 localsSize += 2;
1134 } else if (desc == CD_double) {
1135 locals[localsSize ] = Type.DOUBLE_TYPE;
1136 locals[localsSize + 1] = Type.DOUBLE2_TYPE;
1137 localsSize += 2;
1138 } else {
1139 if (!desc.isPrimitive()) {
1140 type = Type.referenceType(desc);
1141 } else if (desc == CD_float) {
1142 type = Type.FLOAT_TYPE;
1143 } else {
1144 type = Type.INTEGER_TYPE;
1145 }
1146 locals[localsSize++] = type;
1147 }
1148 }
1149 this.localsSize = localsSize;
1150 }
1151
1152 void copyFrom(Frame src) {
1153 if (locals != null && src.localsSize < locals.length) Arrays.fill(locals, src.localsSize, locals.length, Type.TOP_TYPE);
1154 localsSize = src.localsSize;
1155 checkLocal(src.localsSize - 1);
1156 if (src.localsSize > 0) System.arraycopy(src.locals, 0, locals, 0, src.localsSize);
1157 if (stack != null && src.stackSize < stack.length) Arrays.fill(stack, src.stackSize, stack.length, Type.TOP_TYPE);
1158 stackSize = src.stackSize;
1159 checkStack(src.stackSize - 1);
1160 if (src.stackSize > 0) System.arraycopy(src.stack, 0, stack, 0, src.stackSize);
1161 unsetFieldsSize = src.unsetFieldsSize;
1162 unsetFields = UnsetField.copyArray(src.unsetFields, src.unsetFieldsSize);
1163 flags = src.flags;
1164 localsChanged = true;
1165 }
1166
1167 void checkAssignableTo(Frame target) {
1168 int localsSize = this.localsSize;
1169 int stackSize = this.stackSize;
1170 int myUnsetFieldsSize = this.unsetFieldsSize;
1171 if (target.flags == -1) {
1172 target.locals = locals == null ? null : locals.clone();
1173 target.localsSize = localsSize;
1174 if (stackSize > 0) {
1175 target.stack = stack.clone();
1176 target.stackSize = stackSize;
1177 }
1178 target.unsetFields = UnsetField.copyArray(this.unsetFields, myUnsetFieldsSize);
1179 target.unsetFieldsSize = myUnsetFieldsSize;
1180 target.flags = flags;
1181 target.dirty = true;
1182 } else {
1183 if (target.localsSize > localsSize) {
1184 target.localsSize = localsSize;
1185 target.dirty = true;
1186 }
1187 for (int i = 0; i < target.localsSize; i++) {
1188 merge(locals[i], target.locals, i, target);
1189 }
1190 if (stackSize != target.stackSize) {
1191 throw generatorError("Stack size mismatch");
1192 }
1193 for (int i = 0; i < target.stackSize; i++) {
1194 if (merge(stack[i], target.stack, i, target) == Type.TOP_TYPE) {
1195 throw generatorError("Stack content mismatch");
1196 }
1197 }
1198 if (myUnsetFieldsSize != 0) {
1199 mergeUnsetFields(target);
1200 }
1201 }
1202 }
1203
1204 private Type getLocalRawInternal(int index) {
1205 checkLocal(index);
1206 return locals[index];
1207 }
1208
1209 Type getLocal(int index) {
1210 Type ret = getLocalRawInternal(index);
1211 if (index >= localsSize) {
1212 localsSize = index + 1;
1213 }
1214 return ret;
1215 }
1216
1217 void setLocal(int index, Type type) {
1218 Type old = getLocalRawInternal(index);
1219 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1220 setLocalRawInternal(index + 1, Type.TOP_TYPE);
1221 }
1222 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1223 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1224 }
1225 setLocalRawInternal(index, type);
1226 if (index >= localsSize) {
1227 localsSize = index + 1;
1228 }
1229 }
1230
1231 void setLocal2(int index, Type type1, Type type2) {
1232 Type old = getLocalRawInternal(index + 1);
1233 if (old == Type.DOUBLE_TYPE || old == Type.LONG_TYPE) {
1234 setLocalRawInternal(index + 2, Type.TOP_TYPE);
1235 }
1236 old = getLocalRawInternal(index);
1237 if (old == Type.DOUBLE2_TYPE || old == Type.LONG2_TYPE) {
1238 setLocalRawInternal(index - 1, Type.TOP_TYPE);
1239 }
1240 setLocalRawInternal(index, type1);
1241 setLocalRawInternal(index + 1, type2);
1242 if (index >= localsSize - 1) {
1243 localsSize = index + 2;
1244 }
1245 }
1246
1247 private Type merge(Type me, Type[] toTypes, int i, Frame target) {
1248 var to = toTypes[i];
1249 var newTo = to.mergeFrom(me, classHierarchy);
1250 if (to != newTo && !to.equals(newTo)) {
1251 toTypes[i] = newTo;
1252 target.dirty = true;
1253 }
1254 return newTo;
1255 }
1256
1257 // Merge this frame's unset fields into the target frame
1258 private void mergeUnsetFields(Frame target) {
1259 int myUnsetSize = unsetFieldsSize;
1260 int targetUnsetSize = target.unsetFieldsSize;
1261 var myUnsets = unsetFields;
1262 var targetUnsets = target.unsetFields;
1263 if (!UnsetField.mismatches(myUnsets, myUnsetSize, targetUnsets, targetUnsetSize)) {
1264 return; // no merge
1265 }
1266 // merge sort
1267 var merged = new UnsetField[StackMapGenerator.this.strictFieldsToPut.length];
1268 int mergedSize = 0;
1269 int i = 0;
1270 int j = 0;
1271 while (i < myUnsetSize && j < targetUnsetSize) {
1272 var myCandidate = myUnsets[i];
1273 var targetCandidate = targetUnsets[j];
1274 var cmp = myCandidate.compareTo(targetCandidate);
1275 if (cmp == 0) {
1276 merged[mergedSize++] = myCandidate;
1277 i++;
1278 j++;
1279 } else if (cmp < 0) {
1280 merged[mergedSize++] = myCandidate;
1281 i++;
1282 } else {
1283 merged[mergedSize++] = targetCandidate;
1284 j++;
1285 }
1286 }
1287 if (i < myUnsetSize) {
1288 int len = myUnsetSize - i;
1289 System.arraycopy(myUnsets, i, merged, mergedSize, len);
1290 mergedSize += len;
1291 } else if (j < targetUnsetSize) {
1292 int len = targetUnsetSize - j;
1293 System.arraycopy(targetUnsets, j, merged, mergedSize, len);
1294 mergedSize += len;
1295 }
1296
1297 target.unsetFieldsSize = mergedSize;
1298 target.unsetFields = merged;
1299 target.dirty = true;
1300 }
1301
1302 private static int trimAndCompress(Type[] types, int count) {
1303 while (count > 0 && types[count - 1] == Type.TOP_TYPE) count--;
1304 int compressed = 0;
1305 for (int i = 0; i < count; i++) {
1306 if (!types[i].isCategory2_2nd()) {
1307 if (compressed != i) {
1308 types[compressed] = types[i];
1309 }
1310 compressed++;
1311 }
1312 }
1313 return compressed;
1314 }
1315
1316 void trimAndCompress() {
1317 localsSize = trimAndCompress(locals, localsSize);
1318 stackSize = trimAndCompress(stack, stackSize);
1319 }
1320
1321 private static boolean equals(Type[] l1, Type[] l2, int commonSize) {
1322 if (l1 == null || l2 == null) return commonSize == 0;
1323 return Arrays.equals(l1, 0, commonSize, l2, 0, commonSize);
1324 }
1325
1326 int writeTo(BufWriterImpl out, Frame prevFrame, ConstantPoolBuilder cp) {
1327 int extraFrames = 0;
1328 if (UnsetField.mismatches(unsetFields, unsetFieldsSize, prevFrame.unsetFields, prevFrame.unsetFieldsSize)) {
1329 // Emit unset_fields frame
1330 out.writeU1U2(StackMapDecoder.ASSERT_UNSET_FIELDS, unsetFieldsSize);
1331 var array = unsetFields;
1332 for (int i = 0; i < unsetFieldsSize; i++) {
1333 var f = array[i];
1334 out.writeIndex(cp.nameAndTypeEntry(f.name(), f.type()));
1335 }
1336 extraFrames++;
1337 }
1338 int localsSize = this.localsSize;
1339 int stackSize = this.stackSize;
1340 int offsetDelta = offset - prevFrame.offset - 1;
1341 if (stackSize == 0) {
1342 int commonLocalsSize = localsSize > prevFrame.localsSize ? prevFrame.localsSize : localsSize;
1343 int diffLocalsSize = localsSize - prevFrame.localsSize;
1344 if (-3 <= diffLocalsSize && diffLocalsSize <= 3 && equals(locals, prevFrame.locals, commonLocalsSize)) {
1345 if (diffLocalsSize == 0 && offsetDelta < 64) { //same frame
1346 out.writeU1(offsetDelta);
1347 } else { //chop, same extended or append frame
1348 out.writeU1U2(251 + diffLocalsSize, offsetDelta);
1349 for (int i=commonLocalsSize; i<localsSize; i++) locals[i].writeTo(out, cp);
1350 }
1351 return extraFrames;
1352 }
1353 } else if (stackSize == 1 && localsSize == prevFrame.localsSize && equals(locals, prevFrame.locals, localsSize)) {
1354 if (offsetDelta < 64) { //same locals 1 stack item frame
1355 out.writeU1(64 + offsetDelta);
1356 } else { //same locals 1 stack item extended frame
1357 out.writeU1U2(247, offsetDelta);
1358 }
1359 stack[0].writeTo(out, cp);
1360 return extraFrames;
1361 }
1362 //full frame
1363 out.writeU1U2U2(255, offsetDelta, localsSize);
1364 for (int i=0; i<localsSize; i++) locals[i].writeTo(out, cp);
1365 out.writeU2(stackSize);
1366 for (int i=0; i<stackSize; i++) stack[i].writeTo(out, cp);
1367 return extraFrames;
1368 }
1369 }
1370
1371 private static record Type(int tag, ClassDesc sym, int bci) {
1372
1373 //singleton types
1374 static final Type TOP_TYPE = simpleType(ITEM_TOP),
1375 NULL_TYPE = simpleType(ITEM_NULL),
1376 INTEGER_TYPE = simpleType(ITEM_INTEGER),
1377 FLOAT_TYPE = simpleType(ITEM_FLOAT),
1378 LONG_TYPE = simpleType(ITEM_LONG),
1379 LONG2_TYPE = simpleType(ITEM_LONG_2ND),
1380 DOUBLE_TYPE = simpleType(ITEM_DOUBLE),
1381 BOOLEAN_TYPE = simpleType(ITEM_BOOLEAN),
1382 BYTE_TYPE = simpleType(ITEM_BYTE),
1383 CHAR_TYPE = simpleType(ITEM_CHAR),
1384 SHORT_TYPE = simpleType(ITEM_SHORT),
1385 DOUBLE2_TYPE = simpleType(ITEM_DOUBLE_2ND),
1386 UNITIALIZED_THIS_TYPE = simpleType(ITEM_UNINITIALIZED_THIS);
1387
1388 //frequently used types to reduce footprint
1389 static final Type OBJECT_TYPE = referenceType(CD_Object),
1390 THROWABLE_TYPE = referenceType(CD_Throwable),
1391 INT_ARRAY_TYPE = referenceType(CD_int.arrayType()),
1392 BOOLEAN_ARRAY_TYPE = referenceType(CD_boolean.arrayType()),
1393 BYTE_ARRAY_TYPE = referenceType(CD_byte.arrayType()),
1394 CHAR_ARRAY_TYPE = referenceType(CD_char.arrayType()),
1395 SHORT_ARRAY_TYPE = referenceType(CD_short.arrayType()),
1396 LONG_ARRAY_TYPE = referenceType(CD_long.arrayType()),
1397 DOUBLE_ARRAY_TYPE = referenceType(CD_double.arrayType()),
1398 FLOAT_ARRAY_TYPE = referenceType(CD_float.arrayType()),
1399 STRING_TYPE = referenceType(CD_String),
1400 CLASS_TYPE = referenceType(CD_Class),
1401 METHOD_HANDLE_TYPE = referenceType(CD_MethodHandle),
1402 METHOD_TYPE = referenceType(CD_MethodType);
1403
1404 private static Type simpleType(int tag) {
1405 return new Type(tag, null, 0);
1406 }
1407
1408 static Type referenceType(ClassDesc desc) {
1409 return new Type(ITEM_OBJECT, desc, 0);
1410 }
1411
1412 static Type uninitializedType(int bci) {
1413 return new Type(ITEM_UNINITIALIZED, null, bci);
1414 }
1415
1416 @Override //mandatory override to avoid use of method reference during JDK bootstrap
1417 public boolean equals(Object o) {
1418 return (o instanceof Type t) && t.tag == tag && t.bci == bci && Objects.equals(sym, t.sym);
1419 }
1420
1421 boolean isCategory2_2nd() {
1422 return this == DOUBLE2_TYPE || this == LONG2_TYPE;
1423 }
1424
1425 boolean isReference() {
1426 return tag == ITEM_OBJECT || this == NULL_TYPE;
1427 }
1428
1429 boolean isObject() {
1430 return tag == ITEM_OBJECT && sym.isClassOrInterface();
1431 }
1432
1433 boolean isArray() {
1434 return tag == ITEM_OBJECT && sym.isArray();
1435 }
1436
1437 Type mergeFrom(Type from, ClassHierarchyImpl context) {
1438 if (this == TOP_TYPE || this == from || equals(from)) {
1439 return this;
1440 } else {
1441 return switch (tag) {
1442 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1443 from == INTEGER_TYPE ? this : TOP_TYPE;
1444 default ->
1445 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1446 };
1447 }
1448 }
1449
1450 Type mergeComponentFrom(Type from, ClassHierarchyImpl context) {
1451 if (this == TOP_TYPE || this == from || equals(from)) {
1452 return this;
1453 } else {
1454 return switch (tag) {
1455 case ITEM_BOOLEAN, ITEM_BYTE, ITEM_CHAR, ITEM_SHORT ->
1456 TOP_TYPE;
1457 default ->
1458 isReference() && from.isReference() ? mergeReferenceFrom(from, context) : TOP_TYPE;
1459 };
1460 }
1461 }
1462
1463 private static final ClassDesc CD_Cloneable = ClassOrInterfaceDescImpl.ofValidated("Ljava/lang/Cloneable;");
1464 private static final ClassDesc CD_Serializable = ClassOrInterfaceDescImpl.ofValidated("Ljava/io/Serializable;");
1465
1466 private Type mergeReferenceFrom(Type from, ClassHierarchyImpl context) {
1467 if (from == NULL_TYPE) {
1468 return this;
1469 } else if (this == NULL_TYPE) {
1470 return from;
1471 } else if (sym.equals(from.sym)) {
1472 return this;
1473 } else if (isObject()) {
1474 if (CD_Object.equals(sym)) {
1475 return this;
1476 }
1477 if (context.isInterface(sym)) {
1478 if (!from.isArray() || CD_Cloneable.equals(sym) || CD_Serializable.equals(sym)) {
1479 return this;
1480 }
1481 } else if (from.isObject()) {
1482 var anc = context.commonAncestor(sym, from.sym);
1483 return anc == null ? this : Type.referenceType(anc);
1484 }
1485 } else if (isArray() && from.isArray()) {
1486 Type compThis = getComponent();
1487 Type compFrom = from.getComponent();
1488 if (compThis != TOP_TYPE && compFrom != TOP_TYPE) {
1489 return compThis.mergeComponentFrom(compFrom, context).toArray();
1490 }
1491 }
1492 return OBJECT_TYPE;
1493 }
1494
1495 Type toArray() {
1496 return switch (tag) {
1497 case ITEM_BOOLEAN -> BOOLEAN_ARRAY_TYPE;
1498 case ITEM_BYTE -> BYTE_ARRAY_TYPE;
1499 case ITEM_CHAR -> CHAR_ARRAY_TYPE;
1500 case ITEM_SHORT -> SHORT_ARRAY_TYPE;
1501 case ITEM_INTEGER -> INT_ARRAY_TYPE;
1502 case ITEM_LONG -> LONG_ARRAY_TYPE;
1503 case ITEM_FLOAT -> FLOAT_ARRAY_TYPE;
1504 case ITEM_DOUBLE -> DOUBLE_ARRAY_TYPE;
1505 case ITEM_OBJECT -> Type.referenceType(sym.arrayType());
1506 default -> OBJECT_TYPE;
1507 };
1508 }
1509
1510 Type getComponent() {
1511 if (isArray()) {
1512 var comp = sym.componentType();
1513 if (comp.isPrimitive()) {
1514 return switch (comp.descriptorString().charAt(0)) {
1515 case 'Z' -> Type.BOOLEAN_TYPE;
1516 case 'B' -> Type.BYTE_TYPE;
1517 case 'C' -> Type.CHAR_TYPE;
1518 case 'S' -> Type.SHORT_TYPE;
1519 case 'I' -> Type.INTEGER_TYPE;
1520 case 'J' -> Type.LONG_TYPE;
1521 case 'F' -> Type.FLOAT_TYPE;
1522 case 'D' -> Type.DOUBLE_TYPE;
1523 default -> Type.TOP_TYPE;
1524 };
1525 }
1526 return Type.referenceType(comp);
1527 }
1528 return Type.TOP_TYPE;
1529 }
1530
1531 void writeTo(BufWriterImpl bw, ConstantPoolBuilder cp) {
1532 switch (tag) {
1533 case ITEM_OBJECT ->
1534 bw.writeU1U2(tag, cp.classEntry(sym).index());
1535 case ITEM_UNINITIALIZED ->
1536 bw.writeU1U2(tag, bci);
1537 default ->
1538 bw.writeU1(tag);
1539 }
1540 }
1541 }
1542 }