 
Navigation 
Synopsis Analyzing the call structure of an application.
Description Suppose a mystery box ends up on your desk. When you open it, it contains a huge software system with several questions attached to it:
Examples Consider the following call graph (a box represents a procedure and an arrow represents a call from one procedure to another procedure):
rascal>import Set; ok rascal>import Relation; ok rascal>import analysis::graphs::Graph; okRascal supports basic data types like integers and strings which are sufficient to formulate and answer the questions at hand. However, we can gain readability by introducing separately named types for the items we are describing. First, we introduce therefore a new type Proc (an alias for strings) to denote procedures:
rascal>alias Proc = str;
ok
Next, we have to represent the call relation as a Rascal datatype, and the relation is the most appropriate for it.
As preparation, we also import the libraries Rascal:Set, Rascal:Relation and Rascal:Graph that will come in handy.
rascal>rel[Proc, Proc] Calls = {<"a", "b">, <"b", "c">, <"b", "d">, <"d", "c">, >>>>>>> <"d", "e">, <"f", "e">, <"f", "g">, <"g", "e">}; rel[Proc,Proc]: { <"f","e">, <"g","e">, <"a","b">, <"b","d">, <"b","c">, <"d","c">, <"d","e">, <"f","g"> }Now we are in a good position to start asking some questions. How many calls occur in this system? We use the function Rascal:Set/size to determine the number of elements in a set or relation. Since each tuple in the Calls relation represents a call between procedures, the number of tuples is equal
to the number of calls.
rascal>size(Calls);
int: 8
How many procedures occur in this system? This question is more subtle, since a procedure may call (or be called) by
several others and the number of tuples is therefore not indicative. What we need are the set of procedures that
occur (as first or second element) in any tuple. This is precisely what the function Rascal:carrier gives us:
rascal>carrier(Calls);
set[Proc]: {"a","b","c","d","e","f","g"}
and computing the number of procedures is now easy:
rascal>size(carrier(Calls));
int: 7
As an aside, functions Rascal:domain and Rascal:range do the same for the first, respectively, second element of the pairs in a relation:
rascal>domain(Calls); set[Proc]: {"a","b","d","f","g"} rascal>range(Calls); set[Proc]: {"b","c","d","e","g"}What are the entry points for this system? The next step in the analysis is to determine which entry points this application has, i.e., procedures which call others but are not called themselves. Entry points are useful since they define the external interface of a system and may also be used as guidance to split a system in parts. The top of a relation contains those lefthand sides of tuples in a relation that do not occur in any righthand side. When a relation is viewed as a graph, its top corresponds to the root nodes of that graph. Similarly, the bottom of a relation corresponds to the leaf nodes of the graph. See the section called Rascal:Graph for more details. Using this knowledge, the entry points can be computed by determining the top of the Calls relation: rascal>top(Calls);
set[Proc]: {"a","f"}
What are the leaves of this application?
In a similar spirit, we can determine the leaves of this application, i.e., procedures that are being called but do not make any calls themselves: rascal>bottom(Calls);
set[Proc]: {"c","e"}
Which procedures call each other indirectly?
We can also determine the indirect calls between procedures, by taking the transitive closure of the Calls relation, written as Calls+ .
Observe that the transitive closure will contain both the direct and the indirect calls.
rascal>closureCalls = Calls+;
rel[Proc,Proc]: {
<"f","e">,
<"g","e">,
<"a","b">,
<"a","c">,
<"b","c">,
<"d","c">,
<"d","e">,
<"f","g">,
<"a","d">,
<"b","e">,
<"b","d">,
<"a","e">
}
Which procedures are called directly or indirectly from each entry point?
We now know the entry points for this application ("a" and "f") and the indirect call relations. Combining this information, we can determine which procedures are called from each entry point. This is done by indexing closureCalls with appropriate procedure name. The index operator yields all righthand sides of tuples that have a given value as lefthand side. This gives the following: rascal>calledFromA = closureCalls["a"]; set[Proc]: {"b","c","d","e"} rascal>calledFromF = closureCalls["f"]; set[Proc]: {"e","g"}Which procedures are called from all entry points? Finally, we can determine which procedures are called from both entry points by taking the intersection of the two sets calledFromA and calledFromF :
rascal>calledFromA & calledFromF;
set[Proc]: {"e"}
or if your prefer to write all of the above as a oneliner using a Rascal:Reducer expression:
rascal>(carrier(Calls)  it & (Calls+)[p]  p < top(Calls));
set[Proc]: {"e"}
The reducer is initialized with all procedures (carrier(Calls) ) and iterates over all entry points (p < top(Calls) ).
At each iteration the current value of the reducer (it ) is intersected (& ) with the procedures called directly or indirectly
from that entry point ((Calls+)[p] ).
Benefits
Pitfalls
