@=~
~p maximum_input_line_length = infinity

~A~<Variable Usage~>

The style guide requires that a program must not have variables
which are never used. 
Furthermore programs must not rely upon default initialisation. 
Hence each variable must be assigned to before it is used. 

You decide to suggest to your manager that the programmers 
should use lint before they release their programs. 
Inspite of that you try to let your analysis tool check these 
requirements, and compare the results with those of lint. 

For the program

~O~<vars.in~>~{~-
{ int a, b, c, d, e;
  int f;
  int a;

  a = read (x);
  b = a + c;
  c = a * c;
  e = d + a;
  print (e);
}
~}

your analysis tool shall produce messages like

~O~<vars.out~>~{~-
"vars.in", line 5:13 ERROR: variable is not defined
"vars.in", line 1:7 ERROR: variable is multiply defined
"vars.in", line 2:7 WARNING: variable is never used
"vars.in", line 3:7 ERROR: variable is multiply defined
"vars.in", line 5:13 WARNING: variable is used before set
"vars.in", line 6:11 WARNING: variable is used before set
"vars.in", line 7:11 WARNING: variable is used before set
"vars.in", line 8:7 WARNING: variable is used before set
~}

The following questions may help to focus your attention on the
significant aspects of this problem:

1. Decompose the whole task into subproblems: a name analysis
task and several single tasks which need to compute a property
of variables each. Solve the tasks separately.

2. How do you solve the name analysis task?

3. For each property subtask answer the following questions:
What are the property values? 
In which contexts is the property to be set?
In which contexts is the property to be read?
What is the sequencing relation between setting and reading
the property.

4. Discuss the write before read subproblem for the
statement ~{c = a * c;~}.

~B~<Solution~>

Name Analysis:

The task requires to associate properties to program objects.
We first determine which identifier stands for which
program object, represented by a key. 
The name analysis module ~{CScope~} is used for that purpose:

~$~<Name analysis module instance~>~{
$/Name/CScope.gnrc:inst
~}

This module provides computational roles for a root symbol 
~{RootScope~} that contains all scopes, 
for a symbol ~{RangeScope~} that forms a possibly
nested scope, and for defining and applied identifier occurrences,
~{IdDefScope~}, ~{IdUseEnv~}.
These roles are associated to our grammar symbols.

Additionally we have to make the value of the terminal ~{Ident~}
available one level up at the ~{VarDecl~} and ~{VarUse~} nodes.
That is achieved by the computation associated to the ~{CLASS~}
symbol ~{IdOcc~}.

~$~<Name analysis module roles~>~{
SYMBOL Prog    INHERITS RootScope END;
SYMBOL Block   INHERITS RangeScope END;
SYMBOL VarDecl INHERITS IdDefScope END;
SYMBOL VarUse  INHERITS IdUseEnv END;

CLASS SYMBOL IdOcc: Sym: int;
CLASS SYMBOL IdOcc COMPUTE THIS.Sym = TERM; END;
SYMBOL VarDecl INHERITS IdOcc END;
SYMBOL VarUse  INHERITS IdOcc END;
~}

Check Variable Definitions:

The scope rules can be violated in any of two cases:
A variable is used but not defined, or a variable is defined
more than once in a range.
In each case we want to produce an error message.

The first case is checked by inspecting the ~{Key~} attribute
of an applied identifier occurrence:

~$~<Undefined variables~>~{
SYMBOL VarUse COMPUTE
  IF (EQ (THIS.Key, NoKey),
  message (ERROR, "variable is not defined", 0, COORDREF));
END;
~}

In order to check for multiple definitions we use a property:
~$~<Multiple definitions property~>~{
MultDef: int;
~}

For each key it may have one of 3 values which are encoded
for better readability in the following ~{.head~} file
fragment:
~$~<Definition state macros~>~{
#define NotDefined      0
#define OnceDefined     1
#define MultipleDefined 2
~}

The ~{SetMultDef~} in ~{VarDecl~} context sets the
state either to 1 if no definition has been encountered
so far, or to 2 otherwise.
The ~{CONSTITUENTS~} and ~{INCLUDING~} pair using
the attribute ~{GotMultDef~} ensures that all set operations
are done before any check for a message is executed:

~$~<Multiple definitions~>~{
SYMBOL Prog COMPUTE
  SYNT.GotMultDef = CONSTITUENTS VarDecl.GotMultDef;
END;

SYMBOL VarDecl COMPUTE
  SYNT.GotMultDef = 
    SetMultDef (THIS.Key, OnceDefined, MultipleDefined);

  IF (EQ (GetMultDef (THIS.Key, NotDefined), MultipleDefined),
  message (ERROR, "variable is multiply defined", 0, COORDREF))
  <- INCLUDING Prog.GotMultDef;
END;
~}

Used Variables:

For checking whether a defined variable is used somewhere in the
program we use the same technique as for checking for
multiple definitions. A property is introduced:

~$~<Used property~>~{
IsUsed: int;
~}

All variable uses have to be encountered before the check
for an unused variable is done in the context of a variable
definition.

~$~<Uses of variables~>~{
SYMBOL Prog COMPUTE 
  THIS.GotIsUsed = CONSTITUENTS VarUse.GotIsUsed;
END;

SYMBOL VarUse COMPUTE
  THIS.GotIsUsed = ResetIsUsed (THIS.Key, 1);
END;

SYMBOL VarDecl COMPUTE
  IF (NOT (GetIsUsed (THIS.Key, 0)),
  message (WARNING, "variable is never used", 0, COORDREF))
  <- INCLUDING Prog.GotIsUsed;
END;
~}

Read before Write:

We now determine whether a variable is read before written.
For that purpose we use a boolean property that describes whether
a variable is already written in left-to-right order
throughout the program. 

~$~<Is written property~>~{
IsWritten: int;
~}

We simulate assignments and accesses
of variables along a left-to-right chain through the program. 
(This simulation is of course not accurate in the presence of 
loops or if statements. Hence not all situation where a 
variable may be used before it is set will be flagged with a warning.)

That chain is started in the ~{Prog~} context. 
It does not carry a value. The states have to be computed
for each variable individually.

A message is issued when a variable with not ~{IsWritten~}
is encountered in a ~{VarUse~} which is not the left-hand
side of an assignment. The ~{VarUse~} on the left-hand
side of an assignment turns the state into ~{IsWritten~}.

We use a boolean attribute ~{Lhs~} to distinguish
the left-hand side of an assignment from other ~{VarUse~}s.

Furthermore, we have to locally modify the chain order in
assignment contexts such that the left-hand side is
encountered after the right-hand side.

~$~<Variable access computation~>~{
CHAIN VarAccess: VOID;

SYMBOL Prog COMPUTE
  CHAINSTART HEAD.VarAccess = "yes";
END;

SYMBOL VarUse: Lhs: int;
SYMBOL VarUse COMPUTE
  INH.Lhs = 0; /* default */
  THIS.VarAccess =
    IF (INH.Lhs,
	ResetIsWritten (THIS.Key, 1),
    IF (NOT (GetIsWritten (THIS.Key, 0)),
        message (WARNING, "variable is used before set", 0, COORDREF)))
    <- THIS.VarAccess;
END;

RULE: Assign ::= VarUse '=' Expr COMPUTE
  VarUse.Lhs = 1;
  Expr.VarAccess = Assign.VarAccess;
  VarUse.VarAccess = Expr.VarAccess;
  Assign.VarAccess = VarUse.VarAccess;
END;
~}

~B~<Further Questions~>

1. Do you know a library module role that supports the check
for undefind variables?

2. Do you know a library module that supports the check
for multiple definitions?

3. How did you solve the problem that a variable use in the
right-hand side of an assignment has to be considered
before the left-hand side? Do you see alternative solutions?

~B~<Output files~>

~O~<vars.specs~>~{
~<Name analysis module instance~>
~}

~O~<vars.lido~>~{
~<Name analysis module roles~>
~<Undefined variables~>
~<Multiple definitions~>
~<Uses of variables~>
~<Variable access computation~>
~}

~O~<vars.pdl~>~{
~<Multiple definitions property~>
~<Used property~>
~<Is written property~>
~}

~O~<vars.head~>~{
~<Definition state macros~>
~}