Name Analysis Reference Manual
 
At every applied occurrence, name analysis computations must search for
the defining occurrence that denotes the same entity.
Recall that the module provides a generic search algorithm based on the
structure of a scope graph
(see The generic lookup).
All of the computational roles implementing searches use the following
four attributes to provide the information on which that search is based
and to record the result:
Sym
- is an integer-valued attribute specifying the identifier.
This synthesized attribute is set by a module computation to the value
derived from the identifier
(see Tree Grammar Preconditions).
*UseKey
- is a
DefTableKey-valued attribute characterizing the applied
occurrence.
This synthesized attribute is set by a module computation.
A module computation sets the following properties of the value of the
*UseKey attribute:
Sym
- is an integer-valued property holding the value of the
Sym attribute.
Coord
- is a
CoordPtr-valued property holding the source code location
(see Source Text Coordinates and Error Reporting of The Eli Library).
Other *UseKey properties can be set by developer computations.
- *GotUseKeyProp
is a void attribute representing the state that all properties of the
*UseKey needed during a search have been set.
*GotUseKeyProp should be stated as the postcondition of any
developer computations that set properties of *UseKey needed
by the search process (see Information access).
Accumulating computations must be used for this purpose
(see Accumulating Computations of LIDO -- Reference Manual).
- *Key
is a
DefTableKey-valued attribute representing
the key of the corresponding defining occurrence.
This attribute is set by a module computation.
*Key is a postcondition of the search.
*Key is set to the value NoKey if the computation
has been unable to find a suitable defining occurrence.
*ChkIdUse can be inherited by any applied occurrence
to provide an error report when the value of *Key is NoKey
(see Report an unsuccessful search).
For the properties of the value of the *Key attribute, see
Defining Occurrences.
Suppose that the language allows a programmer to specify relationships
between ranges by using applied occurrences:
1 interface A {
2 class D { ... }
3 }
4 class B extends C.D { ... }
5 class C implements A { ... }
The inheritance relationship specified on line 4 would be represented in
the scope graph by a path edge with label 1 whose tail is the scope
node owned by the class being declared and whose
tip is the scope node found by looking up
the applied occurrence D.
That path edge can be added to the scope graph only after the search for
D has been completed.
But in order to complete the search for D, the path edge resulting
from the declaration on line 5 must have been added to the scope graph
before the search for D began.
Thus a search for an edge tip name could fail in two ways:
there might be no appropriate defining occurrence,
or some necessary edge might not have been added to the scope graph before
the search began.
If the search failed because of missing edges, it must be repeated after
edges have been added.
Such repeated searches are costly.
Most of the applied occurrences in a program probably don't describe the
tips of path edges.
Although searches for those symbols could use the same approach as
is used for edge tip names, there is no point in doing so.
For performance reasons, it is best to defer searches that don't affect the
set of edges until the scope graph is complete.
Then if a search fails, we know that there is no appropriate defining
occurrence; there is no need to repeat the search.
There are thus two distinct kinds of searches necessary to find
the appropriate defining occurrence, depending upon the context of
the applied occurrence:
- Worklist search
- If a scope graph is incomplete at the time the computation is initiated,
and an appropriate binding is not found, the lookup will be repeated when
that scope graph has been augmented.
- Graph-complete search
- If an appropriate binding is not found, the search fails.
*WL computational roles incorporate a worklist algorithm that
iterates operations until all are complete.
This algorithm is expensive, so if a language does not allow a programmer
to specify edge tip names or to copy named bindings
then the developer should not use *WL roles at all.
The items on the worklist are tasks, not values.
Each of the *WL roles provides an attribute that identifies the
corresponding task:
*FPItem
- is an
FPItemPtr-valued attribute that represents a worklist
computation.
This attribute is set by a module computation.
There are two computational roles that embody worklist actions to search
for bindings:
*WLSimpleName
- should be inherited by a simple identifier whose binding may be sought
before the scope graph is complete.
*WLQualName
- should be inherited by a qualified identifier whose binding may be sought
before the scope graph is complete.
Searches for bindings of qualified identifiers do not explore parent edges
of a scope graph.
The *WLQualName role provides an additional attribute:
*DependsOn
- is an
FPItemPtr-valued attribute that represents the computation
for the qualifier.
This attribute must be set by a developer computation to the value of a
*WLSimpleName.*FPItem attribute or a *WLQualName.*FPItem
attribute.
There is one computational role that embodies worklist actions to add a
path edge to a scope graph:
*WLCreateEdge
- should be inherited by some convenient symbol in a context where information
about the tip and tail of a named path edge can be determined.
It provides four additional attributes:
*tailEnv
- is a
NodeTuplePtr-valued attribute representing the range that is
the tail of the created edge.
This attribute must be set by a developer computation.
*tipFPItem
- is an
FPItemPtr-valued attribute that represents the computation
for the tip of the created edge.
This attribute must be set by a developer computation to the value of a
*WLSimpleName.*FPItem attribute or a *WLQualName.*FPItem
attribute.
*label
- is an integer-valued attribute that contains the edge label.
This synthesized attribute is set by a module computation to 1.
*EdgeKey
- is a
DefTableKey-valued attribute representing the key of the created
edge.
This attribute is set by a module computation.
EdgeKey is a postcondition for the worklist computation.
A module computation sets the following properties of the value of the
EdgeKey attribute:
FromNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*tailEnv attribute.
ToNodeTuple
- is a
NodeTuplePtr-valued property holding the value of the
*toEnv attribute.
EdgeLabel
- is an integer-valued property holding the value of the
*label
attribute.
Some languages allow bindings from one range to be added to the @math{Bind}
function of another range.
*WLInsertDef
- should be inherited by a defining occurrence that depends on the result
of a search for the binding of an applied occurrence.
The *WLInsertDef role uses the following attributes to provide
information and to record the result:
*DependsOn
- is an
FPItemPtr-valued attribute that represents the computation
yielding the existing binding.
This attribute must be set by a developer computation to the value of a
*WLSimpleName.*FPItem attribute or a *WLQualName.*FPItem
attribute.
*Scope
- is a
NodeTuplePtr-valued attribute representing the range into
which the existing binding is to be inserted.
This inherited attribute is set by a module computation to
INCLUDING *AnyScope.*Env.
Here is an example of WLInsertDef usage.
The goal is to import the binding of a type name defined elsewhere into the
range of the enclosing compilation unit.
There is a single identifier occurrence; its role as an applied occurrence
is embodied in the symbol ITName, and its role as a defining
occurrence is embodied in the symbol ImportedTypeName.
The two symbols are connected by a chain rule:
TREE SYMBOL ITName INHERITS WLSimpleName END;
TREE SYMBOL ImportedTypeName INHERITS WLInsertDef END;
RULE: ITName ::= Identifier END;
RULE: ImportedTypeName ::= ITName COMPUTE
ImportedTypeName.Sym=ITName.Sym;
ImportedTypeName.DependsOn=ITName.FPItem;
ImportedTypeName.Scope=INCLUDING CompilationUnit.TypeEnv;
END;
There are two ways that *WLInsertDef can fail:
there may be no existing binding, or
the range represented by the *Scope attribute may contain a local
binding for the given identifier.
In our example, the first case would result in ITName.Key having the
value NoKey
(see Applied Occurrences).
In the second case, the value of ImportedTypeName.Key will differ from
the the value of ITName.Key.
*GC computational roles assume that all work list tasks have been
completed
(see Worklist search).
*GCLocalName
- should be inherited by an identifier whose binding can be sought only
after the scope graph is complete.
Searches for bindings of local names do not explore any edges
of a scope graph.
The *GCLocalName role provides an additional attribute:
*Scope
- is a
NodeTuplePtr-valued attribute representing the range in which the
search for the identifier's binding should take place.
This inherited attribute is set by a module computation to the value of
INCLUDING *AnyScope.*Env.
*GCSimpleName
- should be inherited by a simple identifier whose binding can be sought only
after the scope graph is complete.
The *GCSimpleName role provides an additional attribute:
*Scope
- is a
NodeTuplePtr-valued attribute representing the range in which the
search for the identifier's binding should begin.
This inherited attribute is set by a module computation to the value of
INCLUDING *AnyScope.*Env.
- *GCQualName
should be inherited by a qualified identifier whose binding can be sought only
after the scope graph is complete.
Searches for bindings of qualified identifiers do not explore parent edges
of a scope graph.
The *GCQualName role provides two additional attributes:
*ScopeKey
- is a
DefTableKey-valued attribute representing the qualifier.
This inherited attribute is set by a module computation to the value
NoKey.
*Scope
- is a
NodeTuplePtr-valued attribute representing the qualifier.
This inherited attribute is set by a module computation to the value
GetOwnedNodeTuple(THIS.ScopeKey,NoNodeTuple)
(see The RangeScope role).
*GCQualName.*Scope must contain the NodeTuplePtr value
of the qualifier.
There are two possibilities:
-
A developer computation sets
*GCQualName.*ScopeKey to a
DefTableKey value from which the desired value can be obtained.
-
A developer computation sets
*GCQualName.*Scope to the desired value
and *GCQualName.*ScopeKey is ignored.
The developer can change the default computation of *GCQualName.*Scope
from *GCQualName.*ScopeKey by providing an extension function
(see Obtain a range from a qualifier).
If a search for a defining occurrence is unsuccessful, the *Key
attribute of the applied occurrence is set to the value NoKey.
The *ChkIdUse computational role is provided by the module to issue
a report in that case.
The *ChkIdUse role may be inherited by any applied occurrence
`app'.
*ChkIdUse provides two additional attributes:
*SymErr
- is an integer-valued attribute.
This synthesized attribute is set by the module computation
EQ(THIS.*Key, NoKey).
*SymMsg
- is a
VOID-valued attribute.
This synthesized attribute is set by the module computation
IF (THIS.*SymErr,
message(
ERROR,
CatStrInd("Identifier is not defined: ", THIS.Sym),
0,
COORDREF));
The behavior can be changed for all applied occurrences by symbol computations
overriding the computation of *SymError.*SymErr and/or
*SymError.*SymMsg.
It can be changed for individual contexts by rule computations
overriding the computation of `app'.*SymErr and/or
`app'.*SymMsg.
|
