Fakultas Ilmu Komputer UI

exercise3.md 10.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
# Exercise 3: Cyclomatic Complexity

## Cyclomatic Complexity in Software Testing

Cyclomatic Complexity [^1] is a metric to measure the complexity of a software by measuring the independent paths in the source code.
Cyclomatic complexity can be calculated by using control flow graphs or with respect to functions, modules, methods or classes within a software program.
Some of basic flow graph notation are shown below.

![Graph Flow](./images/graph-flow.png)

[^1]:  Arthur H. Watson and Thomas J. McCabe (1996). "Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric"

### Sequence

Represent basic flow of a program.
It can be a computation process after the initialization are completed.
It might be a next step of the computation process after the preceding step(s) is completed.

![Sequence Graph Flow](./images/sequence.png)

### Branch Statement

If there is decision-making that is based on the previous operation or computation, the flow will have a branch.
The most basic example of this flow is an if-else statement which creates two branches.
A more complex example includes a nested if statement, which creates branches inside a branch, or an if statement with several else-if conditions that create multiple branches from the preceding node.

![Branch Statement](./images/branch-statement.png)

### Loop

A loop happens when the program stays in a part to do some operations until the
loop condition is completed. For example, it can be an iteration through a group
of items or a computation process based on an algorithm. A control flow graph
(CFG) with a loop can be easily identified by nodes with edges that point to
each other (see the picture below).

![Loop Statement](./images/loop-statement.png)

## Calculating the Cyclomatic Complexity

From the CFG of the program, the cyclomatic complexity (`V(G)`) can be calculated
using the formula: `V(G) = E - N + 2`, where `E` is the number of edges and `N`
is the number of nodes in the graph `G`. There is also another formula variation:
`V (G) = P + 1` where `P` is the number of predicate nodes, i.e. the node that
has branches.

Let us use the program below as an example:

```java
@Service
public class MusicService {

    @Autowired;
    private SongQueue songQueue;

    @Autowired
    private SongManager manager;

    public String removeSong(int position) {
        if (position < 0 || position > songQueue.size()-1) {
            throw new SongIndexOutOfBound(String.format("The index you entered: %d is out of bound", position));
        }

        Song removedSong = songQueue.getSong(position);

        if (position == songQueue.getCurrentSongIndex()) {
            manager.skip();
        } else {
            songQueue.remove(position);
        }
        return removedSong;
    }
}
```

`removeSong` is a method to remove a song from a queue playlist.
The flow of this method consists of three branches (from one if statement and one if-else statement).
See the flow graph of this method below.

![Remove Song Original](./images/removeSongV1.png)

Computing mathematically based on the flow graph above will yield the cyclomatic complexity of 2.
The graph have one condition node (node 1); therefore, it has the following value:

```
V(G) = P +1
V(G) = 1 + 1
V(G) = 2
```

This implementation will have two independent paths: either throw an exception or return the removed song in the end.
It matches the mathematical calculation performed above.

Let us modify the implementation of `removeSong` a bit.
See the program below.
The return statements are inside the second if-statement and outside as the final statement of the program.
It will modify the flow graph a bit.

```java
@Service
public class MusicService {

    @Autowired;
    private SongQueue songQueue;

    @Autowired
    private SongManager manager;

    public String removeSong(int position) {
        if (position < 0 || position > songQueue.size()-1) {
            throw new SongIndexOutOfBound(String.format("The index you entered: %d is out of bound", position));
        }

        Song removedSong = songQueue.getSong(position);

        if (position != songQueue.getCurrentSongIndex()) {
            return songQueue.remove(position);
        }
        manager.skip();
        return removedSong;
    }
}
```

![Remove Song Modified](./images/removeSongV2.png)

The cyclomatic complexity of this modified version of `removeSong` is 3.
The possible outcome is either throw an exception, return statement from inside the if statement, or return from the last statement of the method.
This graph has two conditions node (node 1 and node 3) which yield the following results:


```
V (G) = P +1
V (G) = 2 + 1
V (G) = 3
```

## How this metric is useful for software testing?

[Basis path testing](http://www.mccabe.com/pdf/mccabe-nist235r.pdf) is one of white box technique and it guarantees to execute at least one statement during testing. It checks each linearly independent path through the program, which means number test cases, will be equivalent to the cyclomatic complexity of the program.

Using the cyclomatic complexity of the previous example (the second version), the number of test cases needed is three because there are three different paths.
The three test cases will also help to achieve branch coverage.
This will ensure every possible path of the program is covered by the test cases.

The cyclomatic complexity value has an implication. It determines the complexity of the program. Based on the cyclomatic complexity value, a conclusion can be made to determine whether function testability is good enough.

- 1-4: low complexity – easy to test
- 5-7: moderate complexity – tolerable
- 8-10: high complexity – refactoring should be considered to ease testing
- 11+: very high complexity – very difficult to test

## Tasks

You are asked to compute the cyclomatic complexity of a feature from your group
project **individually**. Create a **new branch** based on the previous
exercise's branch. The chosen function **must be a different function** from the
last exercise and it should be involved in implementing a business process of
the system (e.g. invoking service methods).

At the end of the exercise, do not forget to schedule an one-on-one meeting
with a teaching assistant to demonstrate your work.

164
165
166
167
The due date of this exercise is: **1 December 2021, 21:00 UTC+7**. Please
ensure any updates to the fork repository related to this exercise were made
and pushed before the due date.

168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
### Checklist

1. [ ] Choose one **complex function** from your group project.
   The complexity of your chosen function will affect the final grade of this
   exercise. You can choose a function that is implemented by your workmate, but
   do note that **plagiarism rule still applies**. Choose a different function
   from the previous exercise.
2. [ ] Create the CFG of the chosen function. Draw the picture of the graph
   using any tools (e.g. your favourite image editor, [Graph Coverage Web App](https://cs.gmu.edu:8443/offutt/coverage/GraphCoverage))
   and export the result as an image file. Put the image file in the
   `exercise-assets` folder in the root of your fork repository.
3. [ ] Compute the cyclomatic complexity of the chosen function based on the CFG
   you have drawn in the previous step. Document the process by describing the
   step-by-step calculation in a Markdown-formatted text file (`exercise3.md`) or
   a PDF file (`exercise3.pdf`). Put the file in the `docs` folder in your fork.
4. [ ] Use a library or plugin to compute the cyclomatic complexity of the chosen
   function. Compare the result with the one you have calculated manually.
   Is there any difference? Write your conclusion in `exercise3.md` or
   `exercise3.pdf`. You can use [JaCoCo](#jacoco) or [PMD](https://pmd.github.io/)
   to compute the cyclomatic complexity.
5. [ ] Based on the result of the cyclomatic complexity, write a conclusion
   about the complexity of the program that you test. Write the answer in
   `exercise3.md` or `exercise3.pdf`.
6. [ ] Code coverage measurement tools such as [JaCoCo](#jacoco) (Java) and
   [Coverage.py](https://coverage.readthedocs.io/) (Python) can compute coverage
   metrics such as **line/statement coverage** and **branch coverage**. Does
   **line/statement coverage** equivalent to a test requirement that derived
   using **node coverage criteria**? Explain your reasoning in the answer file
   i.e. `exercise3.md` or `exercise3.pdf`.
7. [ ] Similar to problem number 6, does **branch coverage** equivalent to a
   test requirement that derived using **edge coverage criteria**? Explain your
   reasoning in the answer file, i.e. `exercise3.md` or `exercise3.pdf`.
8. [ ] Based on the result of the cyclomatic complexity calculation, add more
   test cases into your fork until you can achieve **100% branch coverage** of
   the chosen function.
9. [ ] (Optional) Based on the cyclomatic complexity that you have computed,
   is there any relationship between cyclomatic complexity and the number of
   tests from a test requirement that derived from a coverage criteria mentioned
   in the text book? Explain your reasoning in the answer file.

## Appendix

### JaCoCo

JaCoCo provides information of the program you test such as line coverage,
branch coverage, etc. It also gives cyclomatic complexity and how many branch
missed during the test. See the picture below:

![JaCoCo Report](./images/JaCoCoCxty.png)

`IndonesianWordDescriptionHelper` has the cyclomatic complexity of 5 (Cxty column).
There is no branch missed during the test. Similarly, `IndonesianSynonymAntonymResponseCreator`
has cyclomatic complexity of 4, but have one missed branch. You can also click on
one of these classes to see the report of the individual methods.

![JaCoCo Report](./images/JaCoCoCxty-method.png)

Please compare the information provided by JaCoCo with the one you calculate manually.

### PDF

You can also submit the `exercise3.md` as `exercise3.pdf`.

> Tips: If you write using Markdown and want to export the document as PDF file,
> you can use [`pandoc`](https://pandoc.org/) to export text file written in
> Markdown into a PDF. You can also use an NPM package [md-to-pdf](https://www.npmjs.com/package/md-to-pdf)
> if you prefer a more simple way to export the markdown to PDF (assuming you
> have `npm`/`yarn` installed)

*[CFG]: Control Flow Graph