Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / jacoco / ae8c2a836703bf06c07bb3d8a981b5743c62b2ef / . / org.jacoco.doc / docroot / doc / flow.html
blob: b256071266f86d94be768bea665c2764b89ef34d [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
82<ul>
83 <li>Virtual Entry and Exit Nodes</li>
84 <li>Subsequent Instructions</li>
85 <li>(Conditional) Jump</li>
86 <li>Table/Lookup Switch</li>
87 <li>Exception Handlers</li>
88 <li>Unhandled Exceptions</li>
89</ul>
90
91<h2>Probe Insertion</h2>
92
93<p>
94 Code coverage analysis is a runtime metric that provides execution details
95 of the software under test. This requires detailed recording about the
Marc R. Hoffmannae8c2a82010-10-05 16:20:10 +0000[diff] [blame^]96 instructions (instruction coverage) that have been executed. For branch
97 coverage also the outcome of decisions has to be recorded. In any case
98 execution data is collected by so called probes:
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]99</p>
100
101<p class="hint">
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]102 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]103 into a Java method. When the probe is executed, this fact is recorded and can
104 be reported by the coverage runtime.
105</p>
106
107<p>
108 The only purpose of the probe is to record that it has been executed at least
109 once. The probe does not record the number of times it has been called or
110 collect any timing information. The latter is out of scope for code coverage
111 analysis and more in the objective of a performance analysis tool. Typically
112 multiple probes needs to be inserted into each method, therefore probes needs
113 to be identified. Also the probe implementation and the storage mechanism it
114 depends on needs to be thread safe as multi-threaded execution is a common
115 scenario for java applications (albeit not for plain unit tests). Probes must
116 not have any side effects on the original code of the method. Also they should
117 add minimal overhead.
118</p>
119
120<p>
121 So to summarize the requirements for execution probes:
122</p>
123
124<ul>
125 <li>Record execution</li>
126 <li>Identification for different probes</li>
127 <li>Thread safe</li>
128 <li>No side effects on application code</li>
129 <li>Minimal runtime overhead</li>
130</ul>
131
132<p>
133 JaCoCo implements probes with a <code>boolean[]</code> array instance per
134 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]135 executed the entry is set to <code>true</code> with the following four
136 bytecode instructions:
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]137</p>
138
139<pre class="source">
140ALOAD probearray
141xPUSH probeid
142ICONST_1
143BASTORE
144</pre>
145
146<p>
147 Note that this probe code is thread safe, does not modify the operand stack
148 or modify local variables and is also thread safe. It does also not leave the
149 method though an external call. The only prerequisite is that the probe array
150 is available as a local variable. For this at the beginning of each method
151 additional instrumentation code needs to be added to obtain the array instance
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]152 associated with the belonging class. To avoid code duplication the
153 initialization is delegated to a static private method
154 <code>$jacocoinit()</code> which is added to every non-interface class.
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]155</p>
156
157<p>
158 The size of the probe code above depends on the position of the probe array
159 variable and the value of the probe identifier as different opcodes can be
160 used. As calculated in the table below the overhead per probe ranges between 4
161 and 7 bytes of additional bytecode:
162</p>
163
164<table class="coverage">
165 <thead>
166 <tr>
167 <td>Possible Opcodes</td>
168 <td>Min. Size [bytes]</td>
169 <td>Max. Size [bytes]</td>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]170 </tr>
171 </thead>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]172 <tfoot>
173 <tr>
174 <td>Total:</td>
175 <td>4</td>
176 <td>7</td>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]177 </tr>
178 </tfoot>
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]179 <tbody>
180 <tr>
181 <td><code>ALOAD_x</code>, <code>ALOAD</code> <sup>1</sup></td>
182 <td>1</td>
183 <td>2</td>
184 </tr>
185 <tr>
186 <td><code>ICONST_x</code>, <code>BIPUSH</code>, <code>SIPUSH</code>, <code>LDC</code>, <code>LDC_W</code> <sup>2</sup></td>
187 <td>1</td>
188 <td>3</td>
189 </tr>
190 <tr>
191 <td><code>ICONST_1</code></td>
192 <td>1</td>
193 <td>1</td>
194 </tr>
195 <tr>
196 <td><code>BASTORE</code></td>
197 <td>1</td>
198 <td>1</td>
199 </tr>
200 </tbody>
Marc R. Hoffmann102e8372010-04-27 15:46:23 +0000[diff] [blame]201</table>
202
203<p>
Marc R. Hoffmann97728292010-04-27 20:29:23 +0000[diff] [blame]204 <sup>1</sup> The probe array is the first variable after the arguments.
205 If the method arguments do not consume more that 3 slots the 1-byte opcode can
206 be used.<br/>
207 <sup>2</sup> 1-byte opcodes for ids 0 to 5, 2-byte opcode for ids up to 127,
208 3-byte opcode for ids up to 32767. Ids values of 32768 or more require an
209 additional constant pool entry. For normal class files it is very unlikely to
210 require more than 32,000 probes.
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]211</p>
212
213<ul>
Marc R. Hoffmann096bd1d2010-04-27 04:21:39 +0000[diff] [blame]214 <li>Limitation: Only proves that the probe itself has been executed,
215 assumptions about the surrounding application code is interpolation</li>
216 <li>Probe in every edge of the control flow graph</li>
217 <li>Every exit path known (branch coverage)</li>
218 <li>Block entry known (exceptions within blocks)</li>
219</ul>
220
221<h2>Different Types of Edges</h2>
222
223<ul>
224 <li>Probe insertion strategies</li>
225</ul>
226
227<h2>Runtime Overhead</h2>
228
229<ul>
230 <li>Comparison to current basic block probes</li>
231</ul>
232
233</div>
234<div class="footer">
235 <div class="versioninfo"><a href="@jacoco.home.url@">JaCoCo</a> @qualified.bundle.version@</div>
236 <a href="license.html">Copyright</a> &copy; @copyright.years@ Mountainminds GmbH &amp; Co. KG and Contributors
237</div>
238
239</body>
240</html>