The special “null-pointer” (C, C++, Ada) or “null-reference” (Java, C#, Python) value for a pointer-like type is often used to indicate the lack of a meaningful result/data. Accessing a non-existing value is an unnatural operation, resulting in either unpredictable behaviour of the program or the raising of an exception. The usage of pointers often leads to a defensive design: it is expected of the programmer to pre-emptively guard against the null state of a pointer, or handle the resulting exception. Together with a code organisation principle to prefer “early returns”, this defensive mechanism may result in variables in the local scope polluting the list of available symbols. These variables' existence does not pose a performance overhead at run time as virtually all compilers optimise the variable away by caching the loaded value. However, during code comprehension, these symbols remain visible, suggested by code completion tools which hinder understanding. Some programming languages ofer “conditional dereference” operations: in C#, the ?. operator propagates a null reference; in Haskell, the Maybe monad allows expressing such semantics. Modern C++ versions support expressing Maybe-like values with the optional<T> class template, but it encapsulates the value, not the indirect access. Adaptation of new language features or changing user-facing API is often met with business or technical challenges and is thus a slow process. In this paper, we discuss our investigation of the usage of pointer-like types (including iterators) for “nullability” semantics, not only for indirect access. We devised an automated analysis tool that marks potentially redundant pointer variables, lowering the number of visible local symbols. A post-refactoring view can show the landscape of the program where descent
in complex data structures (such as configuration maps) is expressed more concisely.
Configuration* Conf = GetGlobalConfiguration(); if (!Conf)
return; ConfigurationKey* SystemKind = Conf→getDataFor("SystemKind"); if (!SystemKind)
throw InvalidConfiguration("config must contain 'SystemKind'!"); SystemType Sys = (SystemType)SystemKind→value; switch (Sys) { case Platform1: /* ... */ break; /* ... */ }
Listing 1: Example of C++ program design preferring early returns when potentially null pointers are used. With minor transforma
tions, similar code could detail Java or C#, too.
Several mainstream programming languages support indirect access to values
in memory. In languages such as Java, C# or Python, it is through references,
while other languages, such as C, C++ and Ada uses the term pointers, although
there are no semantic diferences between the two categories. An inherent property
of pointers (or indirect accessors ) is that there is the possibility to assign a null
value to the pointer itself. This null value indicates that the pointer does not point
to any valid value, and various programming languages have defined operating a
null-pointer to be an unexpected operation. In managed or interpreted languages,
such as Java, C#, Lua, Python, etc. a run time exception is raised at the null
dereference. Lower level systems programming languages, such as C, C++ and Ada
define accessing through a null to be an undefined operation, with potential – but
not mandatory – run time support for defence against nulls. While method calls of
an object through a null pointer is undefined behaviour 1 [
Due to this, it is common in imperative programming languages with pointers to develop with a defensive design: the code at all points must either explicitly guard against the nulls, or specify in comments whether calling a function with a null argument is valid. Ada supports annotating the access variable with the Not Null tag, while Eifel ofers optional precondition checks. A common pattern together with the defensive design is to favour what is commonly referred to as “early returns”. By early returns, we commonly refer to a technique where the unlikely or erroneous conditions break the flow – with any flow-control statement, not just return – of the program ahead, without the “normal” flow being indented visually. An example of early returns in the context of pointers potentially not referring to any reasonable value is shown in Listing 1.
The issue with having to resort to such coding style is that in many cases there is a potential to reach the useful business logic with several pointer variables visible in the local scope that are not used in just one dereference, often with a null check. For example, in Listing 1, the switch statement’s condition could be written as GetGlobalConfiguration()→getDataFor("SystemKind")→value, were it not for the potential null value of the intermediate results. The increase of named symbols in a scope hinders development and code comprehension as development tools present additional potential suggestions.
In this paper, we discuss the problem related to null values, focused on the detection of potentially erroneous program points by an automated tool. In Section 2, related solutions from other languages and the theory are presented. Section 3 discusses the methodology behind finding bug-prone program sections. We measured open-source C and C++ projects for the prevalence of the problem, which is detailed in Section 4.
Two potential solutions exist that allows hiding or side-stepping an explicit null
check. The first such solution is mostly known from C# (version 6 and
onwards) as the null conditional operator [
Sys = getGlobalConfiguration >>= (getEntry "SystemKind") >>= getValue -- Type of 'Sys' is: Maybe Value
Listing 2: Concise writing of a traversal of a potentially nullable
chain of function applications. the null value is intercepted and coalesced before a further call could happen) and a language with reference semantics where virtually all variable the programmer could access has a null state. One downside of coalescing the null is that there is no way to distinguish if the obtained null was because the full expression without the ?s evaluated to null, or because there was an intermediate step where the execution chain broke.
In Haskell, the Maybe monad can be used to express optional semantics. Maybe
is a data type with two data constructors, Just x – for any value – or Nothing,
which indicates the lack of value. While the ?. operator in C# works for virtually
every type, the Maybe has to be “channelled through” the types of the functions
involved. Functions taking a Maybe x must either un-box the Just x and be a
partial function, or a total function must be defined that deals with the Nothing
case. A polymorphic definition of the bind operator (>>=) can be used concisely
express calculations where the Nothing case is defined to “just” pass the lack of
value on. (>>=) is a function of type Maybe a → (a → Maybe b) → Maybe b,
i.e. it takes a nullable of type a and applies a calculation on it (if it is not null )
resulting in a potentially null of b.2 An overview of the example of Listing 1
rewritten to Haskell’s Maybe monad can be seen in Listing 2. The downside of
this approach is that the point where the calculation failed cannot be easily found
as the end result is a Nothing. However, developers may use pattern matching
instead of the (>>=) operator, which allows for custom “error handling” codes. A
famous example of a program written in Haskell that deals with the optionality of
data and configuration is Pandoc [
Pattern matching has been suggested to be a language feature of C++ [
Various other works detail finding [
The modelled constructs in this paper fall into a subclause of taint or garbage value analysis, which is also often carried out by other means of static analysis, such as symbolic execution.
We created an automated tool based on the open-source LLVM/Clang Compiler
Infrastructure’s [
Given the example in Listing 1, the idea behind redundant pointers can be seen. Conf and SystemKind are only used to store a memory address only to be dereferenced later or flow away on a comparison. Formally, we define potentially redundant pointers as follows.
Definition 3.1. Local variables of the function which are of a dereferenceable type (pointers, smart pointers, iterators, etc.) are potentially redundant if: • initialised with a value at exactly one point • used at most once in a “early flow” branch (such as an early that only range-checks the pointer’s value return or throw) • the pointer is passed as an argument or dereferenced exactly once in its lifetime We refer to the “early flow branch” in the middle bullet-point as guards. 3.1. Rewriting single occurrences of variables Our first goal is to check whether the existence of such local variables is justified. Abstract examples for the matched source code fragments can be seen in Listing 3. struct T { int i; T* next; }; T * tp1 = malloc(sizeof(T)), * tp2 = init2(), * tp3 = init3(); free(tp1); // Single argument passing as usage point. if (!tp2) // Single conditional check.
return -1; // Flow breaking statement. printf("%f", sqrt(tp2→i));
// ∧~~~ Single dereference as usage point.
T* tnext = tp3→next; // Single dereference as usage point. T* tnext2 = tnext→next; // Ditto. free(tnext2); // Single passing of 'tnext2'.
Listing 3: Various cases of potentially redundant pointers. free( malloc(sizeof(T)) ); // tp1 substituted. int tp2i; if (T* tp2 = init2(); (!tp2) ‖ (tp2i = tp2→i, false))
return -1; printf("%f", sqrt(tp2i)); // tp2 substituted. free(init3()→next→next); // tp3, tnext and tnext2 substituted.
Listing 4: The examples of Listing 3 rewritten to omit the pointer.
There are various means to rewrite such potentially unnecessary pointers that depends on the language – C or C ++ – and the standard – mainly whether C ++17 is used or earlier – that applies to the project. The static analysis framework allows for suggesting code changes to the developer, and thus we wrote suggestions on potential rewrites. The previous example can be seen with the rewrites applied in Listing 4.
Certain constructs, such as pointer parameters of a function, loop variables that are pointers must be ignored by the matching rules as there are no reasonable ways of removing the variable while also keeping the semantics of the project intact. Furthermore, the example for tp2 in Listing 3 may only be reasonably rewritten in the newer C++17 and C++20 standards, and certain other restrictions – such as that the accessed member must be default-constructible and assignable (either copy or move) – also apply. The semantics, in this case, is slightly changed due to the default construction, so it is the responsibility of the developer with domain knowledge to decide whether the rewrite is sensible. 3.2. Dereference chains Modelling single occurrences allows for building chains of pointer dereferences, which we used to identify code constructs similar to those solved in other languages by operator?., Maybe, or optional (see Section 2).
Definition 3.2. A sequence of potentially redundant pointers each used in single dereferences that initialises another variable forms a chain. The last variable involved in a chain is not necessarily of dereferenceable type.
For clarity, chains of two are ignored as they are considered in the single occurrence case detailed in Section 3.1. An example of such a chain is [tp3, tnext, tnext2] in Listing 3, which can be rewritten step by step eliding the pointer variable. In case a chain contains a flow breaking statement, the rewrite has to happen with breaking semantics to a varying degree and changing the types involved to, e.g. an optional. The head element of a chain might be unusual in a way that it cannot be removed without changing the interface of the program element at hand. Such is the case for chains that begin with a loop variable or a function parameter.
Another solution could be the proposal and implementation of a ?.-like operator to the language, which takes care of seemingly continuing the calculation when a “null dereference” is encountered. However, given both the lack of a managed execution environment of Java or C# and the lack of referential transparency of functional languages like Haskell, an operation similar to ?. has to be carefully designed to fit well within the language framework ofered by current standard C++. Assuming such a feature existed, the example in Listing 1 could be rewritten as GetGlobalConfiguration?.getDataFor("SystemKind")?.value.
Chains are built by the traversal of the connections between the single occurrence cases which usages are marked initialising a new variable from the result of the dereference.
We measured a selection of free and open-source projects of various scale and domain for both C and C++ programming language. The measurement results for the single occurrence case (see Section 3.1) is detailed in Table 1. It is surprising to see that virtually all of the cases where pointers (and for C++, other dereferenceable types) are used in these mature projects happen without any checks for the null value. This could be attributed to a multitude of reasons. First, the measurement only considers pointers that have exactly one (meaningful) usage point – it could be that pointers with multiple usage points are checked more rigorously against a null dereference. Furthermore, various other means of checking for the potential null value exists, such as assertions, and macros or short predicate functions that evaluate to a logical value but do not pass the received pointer-like value further. The conclusions we can draw from the results is that these pointers contain a hidden invariant to them, namely, that they will not point to null. This lessens the type safety of the system and should be rewritten to an Ada Not Null-like type if such would be available.
The measurement in Table 2 details the prevalence of chains (see Section 3.2) in the same set of analysed projects. The first clear result is that the number of guarded variables within a chain is virtually non-existent. The LLVM/Clang compiler infrastructure is an outlier with various well-guarded chains, and also shows multiple longer chains. Given the results, omitting the pointers could be a possibility to lessen the number of local variables in the function’s scope. Another interesting result is that the amount of chains with a “trivial” (elidable) head is also low: almost all of the chains found have been identified with a non-trivial head. One such example is seen in Figure 1.
The initial premise of this work was to show that redundant local pointer variables
pollute the symbol list of the scope, potentially hindering development. We
intend to extend the measurement tool in the future with also measuring how much
percentage of the local symbols these pointers contribute, as in some cases these
seemingly “unused” local variables might contribute to semantic understanding via
their name [
More concise and compelling analysis methods, such as employing data-flow and path-sensitive analysis, might also lead to the discovery of further cases and potential refactoring eforts. As of writing this paper, data-flow information is not readily available for static analysis tools within the LLVM/Clang tool-chain.
While this work focused primarily on C and C++ projects, a similar problem with potentially elidable local references without a solution via language element exists in Java, which is an often-used application development language. 1 2 9 5 3 1 1 5 6 3 D
4
O n e e t s e c r n . n io G e um ion re ed nu se ay ssre . 81 80 71 23 77 93 42 75 75 26 52 80 28 99 ftoop lco. ehp .Drt) frceen cgon iilita tam xp oN 5 2 9 22 3 1 1 77 17 2 2 5 sce G tre p( ree ic in th .se E 1 n . e e d ren to sse lru e e h e rr p w rf is fee red ca eg t - - - - - - - 2 1 0 2 0 3 01 cu ty re s e ed ro s a ce 0 4 5 6 r r j 1 7 2 b ] 3 [ g ] ] ] t c
]
] 7 ] n 5 8 0
4 ] 13 ] la [1 [1 [
C 2 2 1 2 3 2 ] 3 [ re sg isn i-n eb .c f re i t e dn leb ead ton ,ee d fin ia h
n l t eh rav li a b a c i
a n T a y iv t r n d an t-r en av d . u se ro th in re w on f r a b i sg fo ch -w in tc n ) e flo s n id .2 th a ian fu ifn 3 f y h a e n o b c g D s d
n e n eh ud : i p i
u a t e2 cah ro ch se e
d 2
8 2 3 4 2 1 3 9
3 8 4 8 3 2 8 2 1 9 8 9 9 2 5 3 2 2 5 3 8 th io h d o ie
f n t t f c g e
d r b o e n r e 50 3 1 3 10 ils eS le au bm ito
tea (se y g u t
1 b s
i n e
e
jro ]22 ]4 ta [16 rse [19 [1 i[n li[6 /C CV fuB trca [s2
P l[ [2 ad P tsg isd xu tco tez VM en too sse rce
ru it te H o e M i u L p r e e
c g n P P R T B g L O P T X
] ]7 ] gn ]5 ]8 ]0 l t id
4 ] 13 ] la [1 [1 [
T e a e d C + +
C