Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / jacoco / 66234cf54b3e6f2b20f5174687d3c2625a4e41a4 / . / org.jacoco.doc / docroot / doc / flow.html
blob: fba26a758247ef83f259cad0f165cf6b544cfd8a [file] [log] [blame]
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]1<?xml version="1.0" encoding="ISO-8859-1" ?>
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml" lang="en">
4<head>
5 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" />
6 <link rel="stylesheet" href=".resources/doc.css" charset="ISO-8859-1" type="text/css" />
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]7 <link rel="stylesheet" href="../coverage/.resources/prettify.css" charset="ISO-8859-1" type="text/css" />
Marc R. Hoffmannd7d2f752010-05-06 21:12:31 +0000[diff] [blame]8 <link rel="shortcut icon" href=".resources/report.gif" type="image/gif" />
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]9 <script type="text/javascript" src="../coverage/.resources/prettify.js"></script>
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]10 <title>JaCoCo - Control Flow Analysis</title>
11</head>
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]12<body onload="prettyPrint()">
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]13
14<div class="breadcrumb">
Marc R. Hoffmannd7d2f752010-05-06 21:12:31 +0000[diff] [blame]15 <a href="../index.html" class="el_report">JaCoCo</a> &gt;
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]16 <a href="index.html" class="el_group">Documentation</a> &gt;
17 <span class="el_source">Control Flow Analysis</span>
18</div>
19<div id="content">
20
21<h1>Control Flow Analysis for Java Methods</h1>
22
23<p style="font-weight:bold;">
24 DRAFT - This document does not reflect the current JaCoCo implementation.
25</p>
26
27<p class="hint">
28 Implementing a coverage tool for branch coverage requires detailed analysis
29 of the internal control flow of Java methods. Due to the architecture of
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]30 JaCoCo this analysis needs to happen on compiled class files (bytecode).
31 This document defines graph structures for control flow analysis of Java
32 bytecode and discusses strategies for probe insertion.
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]33 Marc R. Hoffmann, July 2010
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]34</p>
35
36<h2>Motivation and Requirements</h2>
37
38<ul>
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]39 <li>Branch Coverage</li>
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]40 <li>Exception Detection</li>
41</ul>
42
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]43<h2>From Statement Coverage to Branch Coverage</h2>
44
45<p>
46 A
47 JaCoCo till version 0.4.x provides statement coverage
48 As as starting point
49 differnce between statement coverage and branch coverage.
50 probe insertion strategy.
51
52</p>
53
54<pre class="source lang-java">
55<span class="nr"> 1</span>public void example() {
56<span class="nr"> 2</span> a();
57<span class="nr"> 3</span> if (condition()) {
58<span class="nr"> 4</span> b();
59<span class="nr"> 5</span> }
60<span class="nr"> 6</span> c();
61<span class="nr"> 7</span>}
62</pre>
63
64
65<pre class="source">
66<span class="nr"> 1</span>public example() : void
67<span class="nr"> 2</span> L0
68<span class="nr"> 3</span> INVOKESTATIC Example.a() : void
69<span class="nr"> 4</span> L1
70<span class="nr"> 5</span> INVOKESTATIC Example.condition() : boolean
71<span class="nr"> 6</span> IFEQ L3
72<span class="nr"> 7</span> L2
73<span class="nr"> 8</span> INVOKESTATIC Example.b() : void
74<span class="nr"> 9</span> L3
75<span class="nr"> 10</span> INVOKESTATIC Example.c() : void
76<span class="nr"> 11</span> L4
77<span class="nr"> 11</span> RETURN
78</pre>
79
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]80<h2>The Control Flow Graph</h2>
81
Marc R. Hoffmann66234cf2010-10-28 15:24:37 +0000[diff] [blame^]82<h3>Flow Edges</h3>
83
84<p>
85 The control flow graph of a Java method defined by Java byte code may have
86 the following Edges. Each edge connects a source instruction with a target
87 instruction. In some cases the source instruction or the target instruction
88 does not exist (virtual edges for method entry and exit) or cannot be
89 exactly specified (exception handlers).
90</p>
91
92<table class="coverage">
93 <thead>
94 <tr>
95 <td>Type</td>
96 <td>Source</td>
97 <td>Target</td>
98 <td>Remarks</td>
99 </tr>
100 </thead>
101 <tbody>
102 <tr>
103 <td>ENTRY</td>
104 <td>-</td>
105 <td>First instruction in method</td>
106 <td></td>
107 </tr>
108 <tr>
109 <td>SEQUENCE</td>
110 <td>Instruction, except <code>GOTO</code>, <code>xRETURN</code>,
111 <code>THROW</code>, <code>TABLESWITCH</code> and <code>LOOKUPSWITCH</code></td>
112 <td>Subsequent instruction</td>
113 <td></td>
114 </tr>
115 <tr>
116 <td>JUMP</td>
117 <td><code>GOTO</code>, <code>IFx</code>, <code>TABLESWITCH</code> or
118 <code>LOOKUPSWITCH</code> instruction</td>
119 <td>Target instruction</td>
120 <td><code>TABLESWITCH</code> and <code>LOOKUPSWITCH</code> will define
121 multiple edges.</td>
122 </tr>
123 <tr>
124 <td>EXHANDLER</td>
125 <td>Any instruction in range</td>
126 <td>Target instruction</td>
127 <td></td>
128 </tr>
129 <tr>
130 <td>EXIT</td>
131 <td><code>xRETURN</code> or <code>THROW</code> instruction</td>
132 <td>-</td>
133 <td></td>
134 </tr>
135 <tr>
136 <td>EXEXIT</td>
137 <td>Any instruction</td>
138 <td>-</td>
139 <td>Unhandled exception.</td>
140 </tr>
141 </tbody>
142</table>
143
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]144
145<h2>Probe Insertion</h2>
146
147<p>
148 Code coverage analysis is a runtime metric that provides execution details
149 of the software under test. This requires detailed recording about the
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame]150 instructions (instruction coverage) that have been executed. For branch
151 coverage also the outcome of decisions has to be recorded. In any case
152 execution data is collected by so called probes:
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]153</p>
154
155<p class="hint">
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]156 A <b>probe</b> is a sequence of bytecode instructions that can be inserted
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]157 into a Java method. When the probe is executed, this fact is recorded and can
158 be reported by the coverage runtime.
159</p>
160
161<p>
162 The only purpose of the probe is to record that it has been executed at least
163 once. The probe does not record the number of times it has been called or
164 collect any timing information. The latter is out of scope for code coverage
165 analysis and more in the objective of a performance analysis tool. Typically
166 multiple probes needs to be inserted into each method, therefore probes needs
167 to be identified. Also the probe implementation and the storage mechanism it
168 depends on needs to be thread safe as multi-threaded execution is a common
169 scenario for java applications (albeit not for plain unit tests). Probes must
170 not have any side effects on the original code of the method. Also they should
171 add minimal overhead.
172</p>
173
174<p>
175 So to summarize the requirements for execution probes:
176</p>
177
178<ul>
179 <li>Record execution</li>
180 <li>Identification for different probes</li>
181 <li>Thread safe</li>
182 <li>No side effects on application code</li>
183 <li>Minimal runtime overhead</li>
184</ul>
185
186<p>
187 JaCoCo implements probes with a <code>boolean[]</code> array instance per
188 class. Each probe corresponds to a entry in this array. Whenever the probe is
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]189 executed the entry is set to <code>true</code> with the following four
190 bytecode instructions:
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]191</p>
192
193<pre class="source">
194ALOAD probearray
195xPUSH probeid
196ICONST_1
197BASTORE
198</pre>
199
200<p>
201 Note that this probe code is thread safe, does not modify the operand stack
202 or modify local variables and is also thread safe. It does also not leave the
203 method though an external call. The only prerequisite is that the probe array
204 is available as a local variable. For this at the beginning of each method
205 additional instrumentation code needs to be added to obtain the array instance
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]206 associated with the belonging class. To avoid code duplication the
207 initialization is delegated to a static private method
208 <code>$jacocoinit()</code> which is added to every non-interface class.
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]209</p>
210
211<p>
212 The size of the probe code above depends on the position of the probe array
213 variable and the value of the probe identifier as different opcodes can be
214 used. As calculated in the table below the overhead per probe ranges between 4
215 and 7 bytes of additional bytecode:
216</p>
217
218<table class="coverage">
219 <thead>
220 <tr>
221 <td>Possible Opcodes</td>
222 <td>Min. Size [bytes]</td>
223 <td>Max. Size [bytes]</td>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]224 </tr>
225 </thead>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]226 <tfoot>
227 <tr>
228 <td>Total:</td>
229 <td>4</td>
230 <td>7</td>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]231 </tr>
232 </tfoot>
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]233 <tbody>
234 <tr>
235 <td><code>ALOAD_x</code>, <code>ALOAD</code> <sup>1</sup></td>
236 <td>1</td>
237 <td>2</td>
238 </tr>
239 <tr>
240 <td><code>ICONST_x</code>, <code>BIPUSH</code>, <code>SIPUSH</code>, <code>LDC</code>, <code>LDC_W</code> <sup>2</sup></td>
241 <td>1</td>
242 <td>3</td>
243 </tr>
244 <tr>
245 <td><code>ICONST_1</code></td>
246 <td>1</td>
247 <td>1</td>
248 </tr>
249 <tr>
250 <td><code>BASTORE</code></td>
251 <td>1</td>
252 <td>1</td>
253 </tr>
254 </tbody>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]255</table>
256
257<p>
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]258 <sup>1</sup> The probe array is the first variable after the arguments.
259 If the method arguments do not consume more that 3 slots the 1-byte opcode can
260 be used.<br/>
261 <sup>2</sup> 1-byte opcodes for ids 0 to 5, 2-byte opcode for ids up to 127,
262 3-byte opcode for ids up to 32767. Ids values of 32768 or more require an
263 additional constant pool entry. For normal class files it is very unlikely to
264 require more than 32,000 probes.
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]265</p>
266
267<ul>
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]268 <li>Limitation: Only proves that the probe itself has been executed,
269 assumptions about the surrounding application code is interpolation</li>
270 <li>Probe in every edge of the control flow graph</li>
271 <li>Every exit path known (branch coverage)</li>
272 <li>Block entry known (exceptions within blocks)</li>
273</ul>
274
275<h2>Different Types of Edges</h2>
276
277<ul>
278 <li>Probe insertion strategies</li>
279</ul>
280
281<h2>Runtime Overhead</h2>
282
283<ul>
284 <li>Comparison to current basic block probes</li>
285</ul>
286
287</div>
288<div class="footer">
289 <div class="versioninfo"><a href="@jacoco.home.url@">JaCoCo</a> @qualified.bundle.version@</div>
290 <a href="license.html">Copyright</a> &copy; @copyright.years@ Mountainminds GmbH &amp; Co. KG and Contributors
291</div>
292
293</body>
294</html>