Name Analysis Reference Manual
 
The ScopeGraphs module is based upon a lookup algorithm that implements
concepts developed over the years to handle visibility of names
(see The generic lookup).
While these concepts are present in most languages, they are often
embellished with additional rules and restrictions.
It is impossible to build a module that will handle any but the simplest
language "out of the box"; a developer must almost always specialize it for
their application.
Our intent is to provide a powerful substrate for the developer, and to
make the critical controls easily available.
We have chosen to define a developer interface consisting of functions
called at specific points in the lookup process.
A developer may provide implementations of some, all, or none of these
functions; default versions of those not provided will be used
automatically.
The arguments of these functions are definition table keys representing the
applied occurrence being sought and the candidate binding(s) found by the
generic lookup.
Some of the properties of those keys are set by module computations.
The developer is free to set arbitrary properties of keys, so that the
functions can have access to whatever information the developer deems
necessary.
Some of the interface functions are called when the generic lookup
finds a candidate binding.
Those functions may apply semantic information to accept or reject the
candidate binding.
If the binding is to be rejected, then the function can specify whether
and in what manner the search is to continue.
Other functions are called to resolve ambiguities when several bindings
have satisfied the search criteria.
Finally, initialization and finalization routines allow for the use of
state information that may vary from one lookup to another.
Information about the applied occurrence and the candidate binding is not
always sufficient to make a decision.
Sometimes the path through a scope graph between applied and defining
occurrences is important, and therefore the module provides functions that
the developer can call to explore the graph.
The name of the file containing the default version of each of the
developer-coded functions is given after the interface description.
If the default behavior of one of these routines is inadequate, it is
nevertheless a good starting point for implementing a replacement.
To obtain a copy of (say) the source code for `LookupBegin' as file
`LookupBegin.c' in your current directory, give the Eli request:
-> $elipkg/Name/LookupBegin.c > LookupBegin.c
After modifying `LookupBegin.c', simply add its name to your
type-`specs' file to make it available.
Definition table keys are used as arguments to the interface functions
because an arbitrary set of information can be associated with a definition
table key without affecting the interface specification.
This gives maximum flexibility without imposing either a physical or
conceptual burden.
An argument representing the applied occurrence being sought is the value
of the *UseKey attribute of that applied occurrence
(see Applied Occurrences).
Module computations set the following properties of the *UseKey:
Sym
- is an integer-valued property holding the value of the applied occurrence's
Sym attribute.
Coord
- is a
CoordPtr-valued property holding the source code location of
the applied occurrence.
*GraphIndex
- is an integer-valued property holding the value of the applied occurrence's
GraphIndex attribute
(see Isomorphic Scope Graphs).
Other *UseKey properties can be set by developer computations.
To ensure that those property values are actually set before the search
begins, an additional attribute,
*GotUseKeyProp, is provided for all applied occurrences
(see Applied Occurrences).
*GotUseKeyProp should be stated as the postcondition of any computations
the developer adds to set properties of *UseKey needed by
language-specific functions.
Accumulating computations must be used for this purpose
(see Accumulating Computations of LIDO -- Reference Manual).
Here is an example that sets a property called NodeTuple
to hold a representation of the range containing the applied occurrence:
TREE SYMBOL MethodIdUse INHERITS GCSimpleName COMPUTE
SYNT.GotUseKeyProp +=
ResetNodeTuple(THIS.UseKey,INCLUDING AnyScope.Env);
END;
An argument representing a binding candidate is the value
of the *Key attribute of the candidate's defining occurrence.
See Defining Occurrences, for the properties of that value.
The construct `q.i' consists of a qualifier `q' and
a qualified identifier `i'.
Name analysis of `q.i' begins by looking up the qualifier `q'.
Suppose that this lookup results in the definition table key `k'.
In order to look up the qualified identifier `i', an appropriate
NodeTuplePtr value representing a range will be obtained from
`k' and the *UseKey of `i' by invoking
AccessNodesFromQualifier.
If the developer does not provide that routine, the following will be used
automatically:
NodeTuplePtr
AccessNodesFromQualifier(DefTableKey qualifier, DefTableKey app)
/* On entry-
* qualifier specifies an entity from which a range can be obtained
* app specifies the qualified identifier sought in that range
* On exit-
* AccessNodesFromQualifier represents the range
***/
{ return GetOwnedNodeTuple(qualifier, NoNodeTuple); }
Source code: `$elipkg/Name/AccessNodesFromQualifier.c'
In the case of the computational role *GCQualName, the developer has
additional options for obtaining a suitable range
(see Graph-complete search).
Those options are not available for the computational role
*WLQualName, where AccessNodesFromQualifier is invoked by
the module as soon as the qualifier's key is available
(see Worklist search).
If the generic algorithm finds a binding for an applied occurrence in
@math{Bind(n)}, it immediately invokes one of three functions.
The result of each function is one of three integer-valued flags
with the names:
AcceptBinding
- The generic algorithm should terminate, returning the definition key of the
binding.
IgnoreContinue
- The generic algorithm should continue as though no binding had been found.
IgnoreSkipPath
- The generic algorithm should continue, but it should not explore paths
starting at node @math{n}
(see The generic lookup).
The function called depends on the context of the search:
isAcceptableSimple
- is invoked in a search for a simple identifier when @math{n} is
the initial node or a node reached by following a parent edge.
If the developer does not provide isAcceptableSimple,
the following will be used automatically:
int
isAcceptableSimple (DefTableKey def, DefTableKey app)
/* On entry-
* def is the key of the binding found
* app is the UseKey of the applied occurrence sought
* On exit-
* isAcceptableSimple is the desired continuation
***/
{ return AcceptBinding; }
Source code: `$elipkg/Name/isAcceptableSimple.c'
isAcceptableQualified
- is invoked in a search for a qualified identifier when @math{n} is
the initial node.
If the developer does not provide isAcceptableQualified,
the following will be used automatically:
int
isAcceptableQualified (DefTableKey def, DefTableKey app)
/* On entry-
* def is the key of the binding found
* app is the UseKey of the applied occurrence sought
* On exit-
* isAcceptableQualified is the desired continuation
***/
{ return AcceptBinding; }
Source code: `$elipkg/Name/isAcceptableQualified.c'
isAcceptablePath
- is invoked in a search for a simple identifier or a qualified identifier
when @math{n} is the tip of a path edge.
If the developer does not provide isAcceptablePath,
the following will be used automatically:
int
isAcceptablePath (DefTableKey def, DefTableKey app, int lab)
/* On entry-
* def is the key of the binding found
* app is the UseKey of the applied occurrence sought
* lab is the label of the path edge
* On exit-
* isAcceptablePath is the desired continuation
***/
{ return AcceptBinding; }
Source code: `$elipkg/Name/isAcceptablePath.c'
Recall that the generic algorithm traverses all paths starting at node
@math{n} and made up solely of edges labeled @math{k}
(see The generic lookup).
When it finds an acceptable binding, it stops traversing the current path,
backs up to node @math{n}, and traverses the next path made up solely of
edges labeled @math{k} that starts at node @math{n}.
This means that if there are several such paths, the search starting at
node @math{n} may yield several bindings.
The result is of type DefTableKeyList, implemented using the Eli
PtrList module
(see Linear Lists of Any Type of Abstract data types to be used in specifications).
When the complete search yields no bindings, the result is NoKey.
If exactly one binding is found, the result is the key for that binding.
If there is more than one binding, the generic algorithm invokes the
function DisambiguatePaths and returns the result of that invocation.
If the developer does not provide DisambiguatePaths, the following
will be used automatically:
DefTableKey
DisambiguatePaths (DefTableKeyList kl, DefTableKey app, int lab)
/* On entry-
* kl is the list of keys from the acceptable bindings
* app is the UseKey of the applied occurrence sought
* lab is the label of the edges making up the paths searched
* On exit-
* DisambiguatePaths is the selected key
***/
{ return NoKey; }
Source code: `$elipkg/Name/DisambiguatePaths.c'
By returning the value NoKey, this implementation of
DisambiguatePaths requires that all searches yield unambiguous results.
Another possible ambiguity occurs when the applied occurrence is in a weak
context
(see Isomorphic Scope Graphs).
In that case, searches must be carried out in more than one scope graph and
each search might yield an acceptable binding.
When all searches are complete, the generic algorithm invokes
DisambiguateGraphs and returns the result of that invocation.
If the developer does not provide DisambiguateGraphs, the following
will be used automatically:
DefTableKey
DisambiguateGraphs (DefTableKey G[], int N, DefTableKey app)
/* On entry-
* G[] is an array with N elements giving the result for each search
* app is the UseKey of the applied occurrence sought
* On exit-
* DisambiguateGraphs is the selected key
***/
{ int i;
DefTableKey result = NoKey;
for (i = 0; i < N; i++) {
if (G[i] != NoKey) {
if (result != NoKey) return NoKey;
result = G[i];
}
}
return result;
}
Source code: `$elipkg/Name/DisambiguateGraphs.c'
This implementation requires that exactly one of the graph searches yields
an acceptable binding.
The developer may sometimes need to initialize and/or finalize data
structures that their functions use during a single lookup.
Thus the generic algorithm invokes LookupBegin upon entry,
and invokes LookupComplete as it exits.
If the developer does not provide LookupBegin, the following
will be used automatically:
void
LookupBegin (DefTableKey app)
/* On entry-
* app is the UseKey of the applied occurrence sought
***/
{ return; }
Source code: `$elipkg/Name/LookupBegin.c'
If the developer does not provide LookupComplete, the following
will be used automatically:
DefTableKey
LookupComplete(DefTableKey def, DefTableKey app)
/* On entry-
* def is the key of the binding found
* app is the UseKey of the applied occurrence sought
* On exit-
* LookupComplete is the final result of the lookup
***/
{ return def; }
Source code: `$elipkg/Name/LookupComplete.c'
The functions described in this section are provided by the
ScopeGraphs module.
They may be invoked by developer-coded routines that need to traverse the
scope graph in order to check language-specific name analysis rules.
Their interfaces are defined in LangSpecFct.h, which must be
included by any code using them.
The DefTableKey value of the *ScopeKey attribute of a symbol
inheriting the *RangeScope role is used to represent a node in these
functions
(see The RangeScope role).
That key has a property, NodeTuple, giving the value of the symbol's
*Env attribute.
Representing the node by a definition table key allows the developer to
associate arbitrary language-specific information with a particular range.
Several of these functions require the developer to provide a function
that will be called for each scope graph node visited.
That function can determine whether or not the scope graph node satisfies
some language-specific condition.
The type of this function is CallBackDTKFct, defined by:
typedef int (*CallBackDTKFct)(DefTableKey)
The argument of a function of type CallBackDTKFct
specifies the graph node to be examined.
If the condition is not satisfied, the function returns 0.
CheckPaths
- follows paths in the scope graph that are made up of path edges with a
given label.
A developer-coded function is invoked at each node.
int
CheckPaths(DefTableKey f, DefTableKey t, int i,
CallBackDTKFct fnc)
/* On entry-
* f specifies the initial node of the path
* t specifies the final node of the path
* i specifies the label of the edges making up the path
* fnc is a developer-code function invoked at each node
* If no such path exists then on exit-
* CheckPaths=0
* Else if any invocation of fnc yields 0 then
* CheckPaths exits immediately
* CheckPaths=0
* Else on exit-
* CheckPaths=1
***/
isAcceptablePath might invoke CheckPaths to check
whether a certain property holds for each node on the path between
the context of the use of an identifier and its definition.
For example, in Java an inherited name must be accessible in every class
along the inheritance path.
In this case, fnc would be a developer-coded function that verified
the accessibility of the identifier, using information from the node and
information stored about the identifier by isAcceptablePath.
CheckPathsNsp
- follows paths in the scope graph that are made up of path edges with a
given label.
A developer-coded function is invoked at each node.
CheckPathsNsp is identical to CheckPaths except that
f and t are NodeTuple values instead of definition
table keys.
int
CheckPathsNsp (NodeTuplePtr f, NodeTuplePtr t, int i,
CallBackDTKFct fnc)
/* On entry-
* f specifies the initial node of the path
* t specifies the final node of the path
* i specifies the label of the edges making up the path
* fnc is a developer-code function invoked at each node
* If no such path exists then on exit-
* CheckPathsNsp=0
* Else if any invocation of fnc yields 0 then
* CheckPathsNsp exits immediately
* CheckPathsNsp=0
* Else on exit-
* CheckPathsNsp=1
***/
DFSCompleteFrom
- does a depth-first scan of the scope graph using path edges with a given
label.
A developer-coded function is invoked at each node.
void
DFSCompleteFrom (DefTableKey f, int i, CallBackDTKFct fnc)
/* On entry-
* f specifies the starting node for the search
* i specifies the label of the path edges to be used
* fnc is a developer-code function invoked at each node
* the results returned by fnc calls are ignored
***/
HidesOnPaths
- accesses bindings along a specified path that are hidden by a specified
binding according to the generic lookup
(see The generic lookup).
DefTableKey
HidesOnPaths (DefTableKey def, DefTableKey app, int i)
/* On entry-
* def specifies a defining occurrence that may hide other
* bindings
* app specifies an applied occurrence
* i specifies the label of the path edges to be searched
* On exit-
* HidesOnPaths=binding that would be returned
* by the generic lookup when isAcceptablePath(def, app)
* returned IgnoreContinue
***/
HidesNestAndPaths
- accesses bindings that are hidden by a specified binding according
to the generic lookup
(see The generic lookup).
DefTableKey
HidesNestAndPaths (DefTableKey def, DefTableKey app)
/* On entry-
* def specifies a defining occurrence that may hide other
* bindings
* On exit-
* HidesNestAndPaths=binding that would be returned
* by the generic lookup when isAcceptibleSimple(def, app)
* returned IgnoreContinue
***/
reachableNode
- checks for the existence of a path in a (possibly incomplete) scope graph.
The path contains only path edges with a given label, and may or may not
also contain parent edges.
int
reachableNode (DefTableKey f, DefTableKey t, int i, int par)
/* On entry-
* f specifies the initial node of the path
* t specifies the final node of the path
* i specifies the label of the edges making up the path
* if par==0 then the path cannot contain parent edges
* If no such path exists then on exit-
* reachableNode=0
* Else on exit-
* reachableNode=1
***/
Note that because the scope graph may not be complete when
reachableNode is called, a node that is
reported to be unreachable may become reachable later in the analysis.
GCPathReachable
- tests for the existence of a path in a complete scope graph.
The path contains only path edges with a given label.
int
GCPathReachable (NodeTuplePtr f, NodeTuplePtr t, int i)
/* On entry-
* f specifies the initial node of the path
* t specifies the final node of the path
* i specifies the label of the edges making up the path
* If f != t and such path exists then on exit-
* GCPathReachable=1
* Else on exit-
* GCPathReachable=0
***/
The scope graphs are assumed to be complete. The function does not
walk the graph, but it uses bitsets to decide reachability.
|
