AGG provides the analysis technique of
critical pair analysis3.
Critical pair analysis is known from term rewriting and
used there to check
if a term rewriting system is confluent.
It has been generalized to graph rewriting.
Critical pairs formalize the idea of a minimal example of a conflicting situation.
From the set of all critical pairs we can extract the objects and links which
cause conflicts or dependencies.
A critical pair is a pair of transformations
, with
and
which are in conflict, such that graph being minimal.
Roughly speaking, is the gluing of the left-hand sides of the rules and .
It can be computed by overlapping and in all possible
ways such that the intersection of and contains at least one item that is
deleted or changed by one of the rules
and both rules are applicable to at their respective occurences.
The set of critical pairs represents precisely all potential conflicts.
That means a critical pair exists iff,
the application of
disables that of or, vice versa.
After the computation of all critical pairs,
the overall rule set can be structured
into conflict-free and conflicting rules.
There are three reasons why rule applications can be conflicting. The first two are related to the graph structure while the last one concerns the graph attributes.
Two rule applications are in conflict if at least one of the conditions above is fulfilled. To find all conflicting rule applications, minimal critical graphs are computed to which rules can be applied in a conflicting way.
According to three conflict conditions mentioned above we distinguish three kinds of conflicts:
Analogously, there are three reasons why rule applications can depend of one another. The first two are related to the graph structure while the last one concerns the graph attributes.
One rule application is dependent of another one if at least one of the conditions above is fulfilled. To find all dependent rule applications, minimal critical graphs are computed which apply rules in a depending way.
According to three dependencies conditions mentioned above we distinguish three kinds of dependencies:
Dependencies of two rules can be computed by inverting the first rule and finding its conflicts with the second rule and then by renaming
Additionally, in each case we consider the obvious matches and analyze
the rule applications.
All conflicting and depending rule applications we found are called critical pairs.
AGG provides the possibility to detect these two kinds of critical pairs:
The algorithm which computes conflicts and dependencies
has been completely reworked. The new implementation is much faster
and provides better results.
The graphical user interface (GUI) of critical pair analysis (CPA)
was redesigned, too.
In its new shape, the CPA GUI gives clear and sufficient information
about critical pairs. The GUI is convenient to consider a critical pair in more detail.
I.e. for each pair the two rules, all critical overlapping graphs and corresponding
matches can be shown.
The currently selected overlapping graph and the rule graphs used for this overlapping
graph become highlighted in yellow.
The overlapping graph objects (nodes and edges) are numbered to show embeddings
of rule graphs.
The critical graph objects are colored in green.
The menu Critical Pair Analysis in Fig. 45 is part of menu
Analyzer. The availability of its items depends on the state of the
critical pair analysis.
The items of menu Critical Pair Analysis are described below:
The options of the critical pair analysis are available in menu
Preferences / Options... and shown in Figure 46.
The options are explaned here:
With AGG it is possible to show all conflicts and dependencies of rules
within the so-called CPA graph. In this graph the nodes are rules,
the red edges correspond to conflicts and the blue edges to dependencies
between rules. The directed edges mean asymmetric and
the undirected edges mean symmetric conflicts/dependencies between rules.
A pop-up menu invoked on the background of the CPA graph allows to manipulate
the graph view. Moreover, a pop-up menu on each entry of the critical pair table
allows to hide/show appropriate node or edge(s) of the CPA graph.
The critical pair analysis GUI is shown in Figure 47
for example ''StateCharts''.
Clicking on a field of the
certain rule pair in the table in the CPA panel
has the following effect
(the first rule is determined by the row, the second by the column):
Figure 48 shows the critical pairs of rule
addTrans_SaSaS with itself. This rule creats a new edge
abs. Its NAC forbids multi-creation of this edge.
So we can get a conflict situation during multi-application of this rule
as shown by graphs in Figure 48.
Another critical rule pair of this grammar is shown in Figure 49.
Here we can see critical graph objects. The conflict occurs, because the first rule deletes objects which the second rule needs.
In Figure 50 the complete set of generated critical pairs is shown as a table with red (critical) and green (non-critical) fields of rule pairs.
Critical pair analysis for grammar rules can be more efficient,
if a type graph is defined containing multiplicity constraints.
Upper bounds of multiplicity constraints are used to reduce
the set of critical pairs by throwing out the meaningless ones.
Dependent on the graph grammar, the number of critical
pairs can be reduced drastically by the use of multiplicity constraints.
Moreover, the set of critical pairs can be reduced considerably
by defining graph constraints. In the reduced set there
are critical pairs with consistent overlapping graphs only.
Please note: Not all kinds of graph constraints are used for
reduction, but only those which forbid the existence of graph
structures.
Figure 51 shows the type graph of the StateCharts grammar.
Figure 52 shows critical pairs of the StateCharts grammar with the type graph in Figure 51 and graph constraints in Figures 38 - 43.
Please note: the critical pair analysis may take time,
even for one particular rule pair.
As already said above, critical pairs show potential parallel conflicts
and sequential dependencies between transformations.
The computation of conflicts is started by menu item Generate/Conflicts,
the computation of dependencies by menu item Generate/Dependencies.
Now we want to use a refactorings example ''BasicGraph'' to show not only these two kinds of conflicts, but also to introduce a graph representation based on computed critical pairs. The grammar ''BasicGraph.ggx'' can be found in the examples folder Refactorings when downloading AGG . This example was introduced in the PhD thesis of Tom Mens: ''A Formal Foundation for Object-Oriented Software Evolution.'' (PhD thesis, Department of Computer Science, Vrije Universiteit Brussel, Belgium, September 1999.) ''BasicGraph'' is a very general case study. The models that can be represented by this grammar are directed, attributed, typed graphs. The rules are very simple, but allow to make arbitrarily complex changes to any given graph structure. There are the following rules : AddNode, AddEdge, DeleteNode, DeleteEdge, RenameNode, RenameEdge, RetypeNode and RetypeEdge. Figure 53 shows conflicts between the rule applications.
We want to get a closer look at the rule pair DeleteNode and AddEdge. The rules and two delete-use conflict situations are shown in Fig. 54. It is clear that the node to delete could be a source or a target node of a new edge to add. After the rule DeleteNode is applied, the rule AddEdge cannot be applied to previous two nodes.
Another example in Fig. 55 shows two attribute conflicts
of rule RenameNode with itself.
In the case of a change - use attribute conflict
this rule changes the name of a node which is in the match of its other application.
In the case of a change - forbid attribute conflict
the new name of the node can occur in a graph structure that is prohibited by a
negative application condition of the rule and its application is not possible anymore.
The table of critical pair analysis in Fig. 56 shows all those critical pairs reporting sequential dependencies between rule applications.
Now we have a look at the rule pair AddNode and AddEdge. The rules and two produce-use dependency situations are shown in Fig. 57. As we can see, first a special node should be added and then the desired edge.
An example of a change - use attribute dependency is shown in Fig. 58. The application of rule RetypeNode may read the value of the attribute name after the application of rule RenameNode has changed this attribute in suitable way.
As said above, AGG provides the possibility to visualize conflicts and dependencies within the so-called CPA graph. This graph is automatically computed by considering all critical pairs for conflicts and dependencies. The CPA graph for example ''BasicGraph'' is shown in Fig. 59.
Using the pop-up menu of this graph we can get a view on conflicts or dependencies only. Such views on the CPA graph are shown in Figures 60 - 61.
The CPA graph can be very complex if the given rules have many conflicts and
dependencies. In order to get a better understanding of all conflicts and
dependencies it is useful to hide certain edges and nodes dynamically.
This can be done by right-clicking
on a node or an edge and choosing item Hide Node/Edge of the appearing pop-up menu.
Another possibility to manipulate the CPA graph is by using pop-up menus
on the entries of the conflict and dependency tables and choosing item
Hide Relation or Hide Rule.
A certain rule has to be hidden in each table, before it becomes hidden in the
CPA graph.
Analysing the CPA graph, the user can get some help about the order in which the
transformations should be performed.
For example, Fig. 61 shows that DeleteEdge
should be performed before DeleteNode.
On the other hand, in Fig. 60 one can see
that the rules DeleteNode, RenameNode, RetypeNode and
AddEdge are all in symmetrical conflict with each other.
The automatic conflict resolution analysis in AGG is left to future work.
Critical pair analysis is described in:
Critical pair analysis is used in: