1/*******************************************************************************
2 * Copyright (c) 2009, 2018 Mountainminds GmbH & Co. KG and Contributors
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 *    Evgeny Mandrikov - initial API and implementation
10 *
11 *******************************************************************************/
12package org.jacoco.core.internal.analysis.filter;
13
14import java.util.HashSet;
15import java.util.List;
16import java.util.Set;
17
18import org.objectweb.asm.Opcodes;
19import org.objectweb.asm.tree.AbstractInsnNode;
20import org.objectweb.asm.tree.JumpInsnNode;
21import org.objectweb.asm.tree.MethodNode;
22import org.objectweb.asm.tree.TryCatchBlockNode;
23import org.objectweb.asm.tree.VarInsnNode;
24
25/**
26 * Filters duplicates of finally blocks that compiler generates.
27 *
28 * To understand algorithm of filtering, consider following example:
29 *
30 * <pre>
31 * try {
32 * 	if (x) {
33 * 		a();
34 * 		return; // 1
35 * 	}
36 * 	b(); // 2
37 * } catch (Exception e) {
38 * 	c(); // 3
39 * } finally {
40 * 	d(); // 4
41 * }
42 * </pre>
43 *
44 * There are 4 <b>distinct</b> points of exit out of these "try/catch/finally"
45 * blocks - three without exception, and one with Throwable if it is thrown
46 * prior to reaching first three points of exit.
47 *
48 * "finally" block must be executed just before these points, so there must be 4
49 * copies of its bytecode instructions.
50 *
51 * One of them handles Throwable ("catch-any") and must cover all instructions
52 * of "try/catch" blocks. But must not cover instructions of other duplicates,
53 * because instructions of "finally" block also can cause Throwable to be
54 * thrown.
55 *
56 * Therefore there will be multiple {@link MethodNode#tryCatchBlocks} with
57 * {@link TryCatchBlockNode#type} null with same
58 * {@link TryCatchBlockNode#handler} for different non-intersecting bytecode
59 * regions ({@link TryCatchBlockNode#start}, {@link TryCatchBlockNode#end}).
60 *
61 * And each exit out of these regions, except one that handles Throwable, will
62 * contain duplicate of "finally" block.
63 *
64 * To determine exits out of these regions, they all must be processed together
65 * at once, because execution can branch from one region to another (like it is
66 * in given example due to "if" statement).
67 */
68public final class FinallyFilter implements IFilter {
69
70	public void filter(final String className, final String superClassName,
71			final MethodNode methodNode, final IFilterOutput output) {
72		for (final TryCatchBlockNode tryCatchBlock : methodNode.tryCatchBlocks) {
73			if (tryCatchBlock.type == null) {
74				filter(output, methodNode.tryCatchBlocks, tryCatchBlock);
75			}
76		}
77	}
78
79	private static void filter(final IFilterOutput output,
80			final List<TryCatchBlockNode> tryCatchBlocks,
81			final TryCatchBlockNode catchAnyBlock) {
82		final AbstractInsnNode e = next(catchAnyBlock.handler);
83		final int size = size(e);
84		if (size <= 0) {
85			return;
86		}
87
88		// Determine instructions inside regions
89		final Set<AbstractInsnNode> inside = new HashSet<AbstractInsnNode>();
90		for (final TryCatchBlockNode t : tryCatchBlocks) {
91			if (t.handler == catchAnyBlock.handler) {
92				AbstractInsnNode i = t.start;
93				while (i != t.end) {
94					inside.add(i);
95					i = i.getNext();
96				}
97			}
98		}
99
100		// Find and merge duplicates at exits of regions
101		for (final TryCatchBlockNode t : tryCatchBlocks) {
102			if (t.handler == catchAnyBlock.handler) {
103				boolean continues = false;
104				AbstractInsnNode i = t.start;
105
106				while (i != t.end) {
107					switch (i.getType()) {
108					case AbstractInsnNode.FRAME:
109					case AbstractInsnNode.LINE:
110					case AbstractInsnNode.LABEL:
111						break;
112					case AbstractInsnNode.JUMP_INSN:
113						final AbstractInsnNode jumpTarget = next(
114								((JumpInsnNode) i).label);
115						if (!inside.contains(jumpTarget)) {
116							merge(output, size, e, jumpTarget);
117						}
118						continues = i.getOpcode() != Opcodes.GOTO;
119						break;
120					default:
121						switch (i.getOpcode()) {
122						case Opcodes.IRETURN:
123						case Opcodes.LRETURN:
124						case Opcodes.FRETURN:
125						case Opcodes.DRETURN:
126						case Opcodes.ARETURN:
127						case Opcodes.RETURN:
128						case Opcodes.ATHROW:
129							continues = false;
130							break;
131						default:
132							continues = true;
133							break;
134						}
135						break;
136					}
137					i = i.getNext();
138				}
139
140				i = next(i);
141				if (continues && !inside.contains(i)) {
142					merge(output, size, e, i);
143				}
144			}
145
146			if (t != catchAnyBlock && t.start == catchAnyBlock.start
147					&& t.end == catchAnyBlock.end) {
148				final AbstractInsnNode i = next(next(t.handler));
149				if (!inside.contains(i)) {
150					// javac's empty catch - merge after ASTORE
151					merge(output, size, e, i);
152				}
153			}
154		}
155	}
156
157	private static void merge(final IFilterOutput output, final int size,
158			AbstractInsnNode e, AbstractInsnNode n) {
159		if (!isSame(size, e, n)) {
160			return;
161		}
162		output.ignore(e, e);
163		e = next(e);
164		for (int i = 0; i < size; i++) {
165			output.merge(e, n);
166			e = next(e);
167			n = next(n);
168		}
169		output.ignore(e, next(e));
170
171		if (n != null && n.getOpcode() == Opcodes.GOTO) {
172			// goto instructions at the end of non-executed duplicates
173			// cause partial coverage of last line of finally block,
174			// so should be ignored
175			output.ignore(n, n);
176		}
177	}
178
179	private static boolean isSame(final int size, AbstractInsnNode e,
180			AbstractInsnNode n) {
181		e = next(e);
182		for (int i = 0; i < size; i++) {
183			if (n == null || e.getOpcode() != n.getOpcode()) {
184				return false;
185			}
186			e = next(e);
187			n = next(n);
188		}
189		return true;
190	}
191
192	/**
193	 * @return number of instructions inside given "catch-any" handler
194	 */
195	private static int size(AbstractInsnNode i) {
196		if (Opcodes.ASTORE != i.getOpcode()) {
197			// when always completes abruptly
198			return 0;
199		}
200		final int var = ((VarInsnNode) i).var;
201		int size = -1;
202		do {
203			size++;
204			i = next(i);
205			if (i == null) {
206				// when always completes abruptly
207				return 0;
208			}
209		} while (!(Opcodes.ALOAD == i.getOpcode()
210				&& var == ((VarInsnNode) i).var));
211		i = next(i);
212		if (Opcodes.ATHROW != i.getOpcode()) {
213			return 0;
214		}
215		return size;
216	}
217
218	private static AbstractInsnNode next(AbstractInsnNode i) {
219		do {
220			i = i.getNext();
221		} while (i != null && (AbstractInsnNode.FRAME == i.getType()
222				|| AbstractInsnNode.LABEL == i.getType()
223				|| AbstractInsnNode.LINE == i.getType()));
224		return i;
225	}
226
227}
228