Uninitialized Variables

rascal-0.40.17

Given a graph-like model of a program -a control flow graph-, how can we detect the uninitialized variables? This recipe is simplified to the bone to highlight the algorithm, as opposed to the intermediate representation.

import Relation;
import analysis::graphs::Graph;

We model expressions as line numbers here. Normally you could use a Location to uniquely identify an expression or an Algebraic Data Type of an abstract syntax tree of the expression or statement:

alias Expr = int;
alias Varname = str;

The first line number is 1:

Expr root = 1;

rascal>Graph[Expr] pred = {<1,3>, <3,4>, <4,5>, <5,6>, <5,8>, <6,10>, <8,10>};
Graph[int]: {
  <1,3>,
  <3,4>,
  <4,5>,
  <6,10>,
  <8,10>,
  <5,8>,
  <5,6>
}
rascal>import vis::Graphs;
ok
rascal>graph(pred);

Now we represent the example definitions (assignments) of variables at given line numbers and the uses of variables at given lines:

rascal>rel[Varname,Expr] defs = {<"x", 3>, <"p", 4>, <"z", 6>, <"x", 8>, <"y", 10>};
rel[str,int]: {
  <"p",4>,
  <"y",10>,
  <"z",6>,
  <"x",8>,
  <"x",3>
}
rascal>rel[Varname, Expr] uses =  {<"q", 5>, <"y", 6>, <"x", 6>, <"z", 10>};
rel[str,int]: {
  <"q",5>,
  <"x",6>,
  <"y",6>,
  <"z",10>
}

The uninit function takes all the above information and computes for each variable name if it is used without being initialized at which line of code:

rel[Varname, Expr] uninit(rel[Varname,Expr] defs, rel[Varname, Expr] uses, Graph[Expr] pred) =
   { <v, e> | <Varname v, Expr e> <- uses,
              e in reachX(pred, {root}, defs[v])
   };

Let's give it a try:

rascal>UNINIT = uninit(defs, uses, pred);
rel[str,int]: {
  <"q",5>,
  <"y",6>,
  <"z",10>
}
rascal>assert UNINIT == {<"q", 5>, <"y", 6>, <"z", 10>};
bool: true

The unused variables should never be uninitialized:

rascal>UNUSED = domain(defs) - domain(uses);
set[str]: {"p"}
rascal>assert UNUSED == {"p"};
bool: true
rascal>assert UNUSED & UNINIT<0> == {}; // empty intersection
bool: true