Input:

G: template call graph
M: method being edited
CS: call site x = q.m(...) being deleted

Output:

Updated template call graph G'

for each template node T of method M do

for each template C in calleesof(T, CS) do

delete_edge_and_save_template(T, C);

delete_types_after(CS, x) = union of gen_types(C, x) for all C;
add_types_after(CS, x) = union of reaching_types_out(p, x) for all p in pred(CS), for all C;
propagate_update(CS, x, delete_types_after, add_types_after, T);
Let del_types(T) = set of deleted reaching types at return from T;
Let add_types(T) = set of added reaching types at return from T;

end for

for each template CT in caller(M) do

for each C in callsite(CT) to callee M do

Let y = variable storing return value at C;
delete_types_after(C, y) = union of del_types(T) for all templates T of M;
add_types_after(C, y) = union of add_types(T) for all templates T of M;
propagate_update(C, y, delete_types_after, add_types_after, CT);

end for

end for

Temporary Variables

• T - template node of modified method M
• C - template in calleesof(T, CS)
• delete_types_after - set of reaching types generated by CS
• add_types_after - set of reaching types that now reach past the deleted call site CS
• del_types - set of deleted reaching types at return from a template T associated with the modified method M
• add_types - set of added reaching types at return from T

• CT - template in caller(M)
• C - call site in the caller CT that calls M
• y - variable storing return value at call site C
• delete_types_after - union of deleted reaching types (del_types(T)) at return from each template T of M
• add_types_after - union of added reaching types (add_types(T)) at return from each template T of M
• T - template node of M (same T as above)

Secondary Functions

English Walkthrough

1. Delete all edges in the template call graph G that correspond to the deleted call site CS and save the template and corresponding subgraph associated with each deleted edge. There will be a set of edges, as multiple templates could be mapped to the single modified method M, and polymorphic call sites have a set of bound receiver objects (q), each with its own relevant method (m₁, m₂, ... , m_n).

   for each template node T of method M do

   for each template C in calleesof(T, CS) do
   delete_edge_and_save_template(T, C);

2. Update the type information propagated from the modified method M - through the actual parameters - to the potential callees at CS (m₁, ..., m_n). Type information reaching each m_i from other callers is examined and the call subgraph of each m_i is updated to reflect the new reaching type information.

   for each template node T of method M do

   for each template C in calleesof(T, CS) do
   delete_edge_and_save_template(T, C);

3. The new set of types bound to the return variable x from the set of all callees m₁, ..., m_n is used to compute changes in the reaching types of x immediately after CS in M. In other words, the set of types bound to x at CS must be computed in order to update subsequent call sites reached by the return variable types. Both killed and newly reaching types are considered. delete_types_after is the set of types generated by CS - the set of return types from each m_i - while add_types_after is the set of types that now reach past the deleted call site.

   delete_types_after(CS, x) = union of gen_types(C, x) for all C;
   add_types_after(CS, x) = union of reaching_types_out(p, x) for all p in pred(CS), for all C;
   

4. The type information propagating to any potential subsequent callees in the modified method M and to those callees' subgraphs must be updated. The Propagate_Update algorithm performs this function. It has input 5 parameters:
   • CS: the call site affecting reaching type information in template T
   • v: the variable for which reaching type information is changing
   • del_set: the set of deleted reaching types immediately after CS
   • add_set: the set of added reaching types immediately after CS
   • T: the template associated with the method containing call site CS

   propagate_update(CS, x, delete_types_after, add_types_after, T);
   

5. The sets of deleted and added types reaching the return of each template T associated with the modified method M are computed. The return type set of M is updated (if necessary) to correspond to the updated types associated with the deleted call site.

   Let del_types(T) = set of deleted reaching types at return from T;
   Let add_types(T) = set of added reaching types at return from T;

6. The callers of M (and their subsequent callees and callers) must be updated to reflect changes in the return type information - sets of added and deleted reaching types - propagating back to each caller.

   First, all callers of the modified method M must be located. For every call site C in a caller that calls M, the types that must be deleted and added at call sites after C are calculated by taking the union of the del_types and add_types for each template corresponding to M. Propagate_Update is then called to execute the changes.

   for each template CT in caller(M) do

   for each C in callsite(CT) to callee M do
   Let y = variable storing return value at C;
   delete_types_after(C, y) = union of del_types(T) for all templates T of M;
   add_types_after(C, y) = union of add_types(T) for all templates T of M;
   propagate_update(C, y, delete_types_after, add_types_after, CT);
   end for
   end for

Required Data Representations and Access -> Java Data Structures

• Template call graph and subgraphs -> MetaCallGraph
• Templates -> MetaMethods
• Edges of call graph -> Relationships stored in instance variables callees1_cmpct and callees2_cmpct (caller to callees in general and at specific call sites)
• Methods -> HMethods
• Call sites within methods -> CALL (a Quad)
• Call sites to specific callee -> CALL.method() (Returns an HMethod.)
• Return variable -> Temp; found with CALL.retval()
• Sets of reaching types (added and deleted) -> Set
• Determination of callees and callers for a given method -> MetaCallGraph.getCallees and MetaAllCallers.getCallers
• Template repository -> Split relation mapping each HMethod to its corresponding MetaMethods