I don’t really remember how we got there, but a couple of days ago at the office we ended up talking about the complexity of the codebase we have to deal with. Tommi mentioned the McCabe cyclomatic complexity, “which may be considered a broad measure of soundness and confidence for a program“. According to the Wikipedia article it “directly measures the number of linearly independent paths through a program’s source code“. And there’s this little table, with some pre-defined thresholds:
| Cyclomatic Complexity |
Risk Evaluation |
| 1-10 | a simple program, without much risk |
| 11-20 | more complex, moderate risk |
| 21-50 | complex, high risk program |
| greater than 50 | untestable program (very high risk) |
Well, fair enough. You always have to be a little skeptic about this kind of data, but it might give you some insights about a codebase. So “apt-get install pmccabe”, a tool to “calculate McCabe cyclomatic complexity or non-commented line counts for C and C++ programs“. The man page says:
The obvious application of pmccabe is illustrated by the following which gives a list of the “top ten” most complex functions:
pmccabe *.c | sort -nr | head -10
Sounds like fun! Let’s run it on the gtk/ directory in gtk+… (drum rolls):
| Cyclomatic complexity | Lines of code | Function name |
| 119 | 337 | gtk_notebook_calculate_tabs_allocation |
| 119 | 744 | gtk_tree_view_bin_expose |
| 89 | 467 | gtk_tree_view_column_cell_process_action |
| 88 | 545 | update_node (in gtkuimanager.c) |
| 68 | 404 | gtk_tree_view_button_press |
| 68 | 381 | gtk_toolbar_size_allocate |
| 64 | 218 | gtk_im_context_simple_filter_keypress |
| 64 | 230 | gtk_tree_view_key_press |
| 59 | 243 | gtk_menu_handle_scrolling |
| 58 | 175 | gtk_clist_motion |
Some of the functions are way past the threshold for intractability (and all of them surpass it), and GtkTreeView has 4 of the 10 most complex functions in gtk according to McCabe. I suppose you can extract many lessons from here, but I’ll only give one humble suggestion: we need regression testing for gtk, and we need it yesterday, as it seems that no human being can hack on some parts of gtk without breaking something 🙂
Those tree view functions are not that hard once you get the hang of them 🙂 Anyway, I’ve indeed been thinking about automatically testing most core GtkTreeView functionality, more on that later. I am surprised GtkTreeModelFilter didn’t show up in the table 😉
It will take some heavy refactoring before chunks of GTK+ can be automatically tested. For example, we’d need some standalone “layout calculator” for GtkCellRenderers that can be called by the test suite — right now that code is spread all over the place in GtkTreeView and cell renderers themselves.
Pingback: Raphaël’s Last Minutes » Blog Archive » Cyclomatic complexity in GIMP code
Try it on libc with “find -name “*c”|xargs pmccabe >> ~/report; sort -nr /home/haypo/report |head”.
Some hilarous results: 494 _IO_vfwscanf() ; 230 fnmatch() ; 222 strtod() ; 200 collate_read() ; 197 dl_main() ; 196 __isinfl_internal() (printf_fp.c) ; 175 wordexp()
Haw, I can beat that – try GCC:
1062 fold_binary
485 find_reloads
479 expand_expr_real_1
430 simplify_binary_operation_1
426 try_combine
and these may not even be the worst instances, because it gets confused by a bunch of preprocessor abuse.
You could take a look at MoMo, the Mozilla Monitor:
http://www.frontendart.com/momo.php
(this one uses another tool, not pmccabe)
The most complex function in an older version had 1323 McCabe, which beats GCC 🙂
Even the tenth in the row of the top 10 has complexity of 200. So keep on evolving….