Static Analysis (Week 12)

Most of the techniques we've dealt with up until now are used for "dynamic program analysis". This just means that a computer program is analyzed by running it, generally with some known or otherwise useful inputs.

On the other hand, "static program analysis" (or "static analysis" for short) is the analysis of a computer program without actually executing it. We all used a primitive kind of static analysis when we were learning to program. We would step through a program line by line, attempting to understand what each line would "do". The good news is that the computer can do all sorts of interesting and helpful static analysis for us, and this can help us prevent (or, failing that, find and eliminate) bugs in our programs.

Static Type Systems

The most common kind of static analysis is related to data types. This is the "int" or "String" labels you had to include with your methods and variables when you learned Java. But it goes so much further than that. A full treatment of type systems is well beyond the scope of this course, but since you all have some experience with Java you already know the basics. One category of bug that can crop up in Java programs due to a weakness in Java's type system (a flaw it shares with many other languages) is the Null Pointer (or Reference) Exception:

public void foo(String s) {

  int l = s.length(); // Might fail!

}

In the code above, if the method "foo" were to be called with the value "null" the code would fail on the given line. This doesn't really make sense, though, because we declared that "s" must be a "String" and instances of the "String" class have a "length()" method. But "null" doesn't have such a method, hence the exception. How can something other than a "String" end up assigned to "s"?

Fortunately, not all languages suffer from this issue, and some that do are being modified to work around it, at least in some cases. For example, Kotlin, a relatively new programming language that has gained a great deal of popularity among Android developers doesn't allow values to be null unless they are declared "nullable", and forces the programmer to check for "null" in that case. The code above could be rewritten in Kotlin like so:

fun foo(s: String?) {

  val l = s.length() // Won't compile!

}

In this case, the "?" after the type indicates that it might be null. Therefore, the compiler will fail because "s" wasn't checked for a null value before being used as a "String". We could correct the problem by checking for null, or by using special syntax to allow the "null" to be assigned to "l", without an exception.

fun foo(s: String?) {

  val l = s?.length() // If s is null, then l will become null

}

Further reading:

• https://en.wikipedia.org/wiki/Type_system
• http://www.cs.colorado.edu/~bec/courses/csci5535/reading/cardelli-typesystems.pdf
• https://www.cs.princeton.edu/courses/archive/spring12/cos320/typing.pdf (for the mathematically ambitious)

Code Structure

Linters

It is common to refer to a small blemish in a piece of code as "lint", and programs that search for such blemishes are typically referred to as "linters". The purpose of a linter is to find constructs that might cause problems or bugs. For example, in languages with dynamic type systems, or languages that allow "null" values, a linter might verify that the type or value of a variable is checked before methods are called on it.

Linters can also check for potential security vulnerabilities, memory leaks, and a host of other problems.

Further reading:

• Stack Overflow question about linting
• https://en.wikipedia.org/wiki/Lint_(software)
• Pylint (a Python linter)

Style Guides

Most software projects involve more than one programmer. Even small projects may involve multiple people over a period of time. For this reason many organizations choose to standardize how code is organized and formatted. For example, Google has an entire set of very detailed style guides for most of the languages in use within the company.

Style guide enforcement is often a manual process, but in some cases it can be automated. For example, Python's style guide (often called "PEP 8" after the Python Enhancement Proposal that spawned it) can be enforced with a command line tool and a large number of services and editor extensions built on top of it.

Further reading:

• Google Style Guides
• Mozilla Style Guide
• Python "PEP 8" Style Guide
• PEP 8 checker
• Style Guide for Arduino Tutorials

Formatters

Style guides are useful, and automatic style guide enforcement can be even more useful. But ideally we wouldn't have to worry about how we format our code when we write it. The main point of a style guide is to help everyone in a group of people read a program's code, so if we make a small mistake it shouldn't slow us down. Enter automatic code formatters. These have become more popular in recent years, and many people (myself included) don't even like using languages that can't be automatically formatted. That being said, if you disagree with what the formatter does you might find yourself resenting it.

Further reading:

• Go programming language formatter
• "Auto" PEP 8

Cyclomatic Complexity

One form of static analysis that we've already seen is cyclomatic complexity. The idea here is to get some sense of how complicated a given piece of code is, and therefore how likely it is to contain bugs.

Further Reading

• https://en.wikipedia.org/wiki/Static_program_analysis
• Academic treatment from Aarhus University (advanced)