Visualizing Early Aspects with Use Case Maps - Transactions on Aspect-Oriented Software Development - page 125

4.1 Matching Algorithm

The matching algorithm compares the static structure of a pointcut map with
all other maps in the UCM model except for other pointcut maps. The matching
algorithm establishes a mapping from each path node on the pointcut map to
path nodes in the UCM model. A successful match requires a mapping of each
path node on the pointcut map to exactly one path node in the UCM model. As
thepointcutmapmaybematchedseveraltimesbytheUCMmodel,theresult
contains a list of mappings for each matched instance of the pattern described
by the pointcut map. Several path node types such as direction arrows as well
as stubs including the start and end points of its plug-ins are not relevant to the
matching algorithm and are therefore not mapped. These path node types are
called map “white space”.
The matching algorithm is a recursive algorithm that begins at a start point
of the pointcut map and at each step scans the next relevant path node following
the current path node on the pointcut map (i.e., map “white space” is skipped).
If multiple branches leave or enter the current path node, all branches are consid-
ered in one step. The following step will then continue to consider all branches
at once. If the matching algorithm finds a matching path node in the UCM
model for the initial path node of the pointcut map, the matching algorithm
scans the base UCM model and the pointcut map in parallel. At each step, the
algorithm tries to match all next path nodes of the pointcut map against all next
path nodes in the UCM model. This match requires all possible permutations
to be considered. For example, let us assume that the matching algorithm has
mapped an OR-fork from the pointcut map to an OR-fork in the UCM model
and both OR-forks have two branches. Then, the first branch of the OR-fork on
the pointcut map can be matched either against the first or second branch of
the OR-fork in the UCM model. The same applies to the second branch. If more
than one permutation can be matched against the path nodes on the pointcut
map, the matching algorithm will continue to explore recursively each matched
permutation as an individual match candidate.
At each step, new mappings are added to the result if the matching is success-
ful. If the matching is not successful, the mappings established for the current
match candidate are discarded and the candidate is not pursued further. The
matching, however, continues with all other still valid permutations and their
corresponding mappings. Matching may not be successful in one of the following
cases:

- The next path node of the pointcut map cannot be matched against the next
path node in the base UCM model (in case only one branch and therefore
only one next path node has to be considered).
- The set of next path nodes of the point cut map cannot be matched against
the set of next path nodes in the base UCM model (in case several branches
have to be considered).
- The next path node or set of path nodes can be matched but a new mapping
contradicts the already established mappings.