General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
Name Analysis Reference ManualApplication Program InterfaceComputational roles are implemented by calls of functions that operate on the ScopeGraphs module's state. For certain language-specific features of name analysis it may be necessary or convenient for a developer to call those functions directly in a context that cannot play the corresponding role. For example, the package structure in Java requires the developer to create nodes that don't correspond to subtrees of the abstract syntax tree. The solution is to formulate a computation in a context where the information is available, even though that context does not fit the requirements of any appropriate role. The functions described in this chapter can be invoked within any `.lido' file without further specification. Any other file invoking them must make the include file `ModelExport.h' available in the context of the invocation. Invocations of the functions described here usually depend on values yielded by other computations, and/or on the effects that other computations have on the state of a ScopeGraphs module instantiation. Value dependence is explicit in the data flow: if a value is passed as an argument to a function call, then that value must be computed before the function is called. State dependence must be made explicit through the use of void attributes (see State Dependencies of LIDO -- Computations in Trees). Eli uses explicit dependence information to statically schedule all computations. That schedule is independent of any particular program. The ScopeGraphs module's roles make all of the necessary dependence relations explicit. If additional computations are necessary, then the developer must establish explicit dependence relations to define the effect of those additional computations on the state of the instantiation. Thus the developer must have an understanding of the internal state of the module instantiation in order to select the appropriate pre- and post-conditions for function invocations.
The state of an instantiationAll of the elements of the ScopeGraphs module's data structure are represented by pointers. In the documentation we will refer to pointers to elements as though they were the elements themselves.
As an example, consider the ScopeGraphs module instantiated by:
$/Name/ScopeGraphs.gnrc +instance=A_ :inst
Assume that
In this case, We have seen that the scope graph nodes, the parent edges of the graph, and some of the path edges can be established based on information that exists in the abstract syntax tree prior to name analysis (see Establishing the Structure of a Scope Graph). Similarly, the properties of almost all defining occurrences can be determined without reference to name analysis results (see Defining Occurrences). The tip of a path edge that is identified by a name in the program cannot be located without a name analysis computation: the name must be resolved in order to create the edge. That resolution may depend on the creation of other path edges (see Applied Occurrences). The ordering of edge tip resolution operations is program-dependent, and therefore those operations cannot be scheduled statically.
Eli requires static scheduling of attribute computations.
Therefore all of the
Once all tasks have been added to the worklist,
they can be carried out by an indivisible operation
called
In some languages, names identifying path edge tips may be type-qualified
(see Interaction with type analysis).
Type-qualified tip names require that the abstract syntax tree be
partitioned into subtrees, with the root of each subtree inheriting the
Let @math{N} be the set of tree nodes whose symbols inherit
This dependence is made explicit through the use of the abstract role
CLASS SYMBOL *OutSideInDeps COMPUTE SYNT.*PreWorkDone = CONSTITUENTS *PreWork.*PreWorkDone SHIELD *OutSideInDeps; END;
INCLUDING *OutSideInDeps.*FPSolved
When
Functions that create nodes, edges, and bindingsThe functions described in this section do not depend on the state of the ScopeGraphs module. They can be called in any context where their arguments are available. NodeTuplePtr newNodeTuple (GraphsDescrPtr d, NodeTuplePtr p, int l) /* Create a representation of a range in a scope graph * On entry- * d specifies the module instantiation * p represents a range * l is the current line number in the input text * On exit- * newNodeTuple points to a new range in d * if p != NoNodeTuple then * d has a parent edge with tail newNodeTuple and tip p * else * d has no parent edge with tail newNodeTuple ***/
The third argument is generally set to 0 when
Any developer invocation of
NodeTuplePtr ParentOfNodeTuple (NodeTuplePtr r) /* On entry- * r represents a range * If r is the tail of a parent edge then on exit- * ParentOfNodeTuple represents the tip of r's parent edge * Else on exit- * ParentOfNodeTuple=NoNodeTuple ***/ ScopeNodePtr SelectNode (NodeTuplePtr r, int index) /* On entry- * r represents a range * index is a valid graph index for r * On exit- * SelectNode points to the scope node of r that is indexed by index
void NodeTupleOwnerKey (NodeTuplePtr r, DefTableKey owner) /* On entry- * r represents a range * owner specifies an entity * On exit- * owner owns the range r ***/
Any developer invocation of
DefTableKey OwnerKeyOfNodeTuple (NodeTuplePtr r) /* On entry- * r represents a range * If an entity owns r then on exit- * OwnerKeyOfNodeTuple specifies the entity that owns r * Else on exit- * OwnerKeyOfNodeTuple=NoKey ***/ The developer must ensure that the owner key is set before being accessed.
DefTableKey OwnerKeyOfOneNode (ScopeNodePtr n) /* On entry- * n represents a scope graph node * If n has an owner then on exit- * OwnerKeyOfOneNode is the key of the owner * Else on exit- * OwnerKeyOfOneNode=NoKey ***/ The developer must ensure that the owner key is set before being accessed.
DefTableKey NABindIdn (NodeTuplePtr r, int i, int id, DefTableKey k, CoordPtr c) /* Bind an identifier in a scope * On entry- * r[i] defines the desired scope graph node * id defines the identifier * k represents an existing binding or is NoKey * c specifies the source coordinates or is NoPosition * if Bind(r[i])(id) is undefined then * if k==NoKey then Bind(r[i])(id)=NewKey() * else Bind(r[i])(id)=k * else if Bind(r[i])(id)==NoKey and k!=NoKey then- * Bind(r[i])(id)=k * On exit- * NABindIdn returns Bind(r[i])(id) ***/
Any developer invocation of
DefTableKey addEdge (NodeTuplePtr tail, NodeTuplePtr tip, int l) /* Add path edges * On entry- * tail represents a range * tip represents a range * label is a valid path edge label * On exit- * k=NewKey() * A path edge has been added from tail[i] to node tip[i] * for each valid scope graph index i * Each added path edge has label l and key k * addEdge returns k ***/
Any developer invocation of
Functions that initiate worklist operationsThe functions described in this section initiate worklist operations. No function in this section may be invoked in a particular context unless that invocation depends on the following attribute in that context:
INCLUDING *OutSideInDeps.*FPSolved
Any invocation of a function described in this section must guarantee that
the Note: Do not use worklist operations for lookup of names if the lookup could be delayed until the graph is complete. FPItemPtr FPLookupPlain (NodeTuplePtr r, int i, DefTableKey u, GraphsDescrPtr d) /* Establish a task to look up a simple identifier * On entry- * r represents a range * i is a valid graph index * u is the user key of the applied occurrence * d specifies the module instantiation * On exit- * A task to seek applied occurrence u, starting at node r[i], * has been added to the worklist * FPLookupPlain returns a representation of the task ***/
FPItemPtr FPLookupQual (FPItemPtr q, int i, DefTableKey u, GraphsDescrPtr d) /* Establish a task to look up a qualified identifier * On entry- * q represents a task to find the qualifier * i is a valid graph index * u is the user key of the applied occurrence * d specifies the module instantiation * On exit- * A task to seek applied occurrence u, starting at node q[i], * has been added to the worklist * FPLookupQual returns a representation of the task ***/
FPItemPtr FPInsertDef (NodeTuplePtr r, int i, DefTableKey u, FPItemPtr def, GraphsDescrPtr d) /* Establish a task to import a binding * On entry- * r represents a range * i is a valid graph index * u is the user key of an applied occurrence * def describes a task yielding the binding to be imported * d specifies the module instantiation * if Bind(r[i])(u) is undefined then Bind(r[i])(u)=NoKey * On exit- * A task to set Bind(r[i])(u) to the result of def * has been added to the worklist * FPInsertDef returns a representation of the task ***/
If the applied occurrence is not already bound in the importing scope,
FPItemPtr FPAddEdge (NodeTuplePtr f, FPItemPtr t, int l, GraphsDescrPtr d, CoordPtr p) /* Establish a set of equivalent edges * On entry- * f represents a range * t represents a range * l is a valid path edge label * d specifies the module instantiation * p specifies the source coordinates or is NoPosition * On exit- * A task to create a path edge from f[i] to t[i], * for each valid scope graph index i, * has been added to the worklist * FPAddEdge returns a representation of the task ***/
Functions that search complete graphsThe functions described in this section assume that the worklist operations are complete. No function in this section may be invoked in a particular context unless that invocation depends on the following attribute in that context:
INCLUDING *OutSideInDeps.*FPSolved
int getFPItemDone (FPItemPtr t) /* On entry- * t represents a task * If t has been completed then on exit- * getFPItemDone returns 1 * Else on exit- * getFPItemDone returns 0 ***/ DefTableKey getFPItemKey (FPItemPtr t) /* On entry- * t represents a completed lookup task * On exit- * getFPItemKey returns the key found by the task ***/
DefTableKey
getFPEdgeKey (FPItemPtr t, int l)
/* On entry-
* t represents a completed
In the following functions, the argument
DefTableKey GCLookupPlainId (NodeTuplePtr r, int i, DefTableKey u) /* Look up a simple identifier * On entry- * r represents a range * i is a valid graph index * u is the user key of the applied occurrence * On exit- * GCLookupPlainId returns the key found for u starting at r[i] ***/
DefTableKey GCLookupQualId (NodeTuplePtr r, int i, DefTableKey u) /* Look up a qualified identifier * On entry- * r represents a range * i is a valid graph index * u is the user key of the applied occurrence * On exit- * GCLookupQualId returns the key found for u starting at r[i] ***/
Here the range
DefTableKey GCLookupLocalId (NodeTuplePtr r, int i, DefTableKey u) /* Look up an identifier * On entry- * r represents a range * i is a valid graph index * u is the user key of the applied occurrence * On exit- * GCLookupLocalId returns the key found for u starting at r[i] ***/ This search seeks only a binding @math{Bind(r[i])(id)}, where @math{id} is the identifier of the applied occurrence.
Functions that pre-define symbols
The
void SGPreDefineSym(const char *name, int *sym) /* Pre-code an identifier * On entry- * name is the external representation of the identifier * sym addresses an integer-valued variable * On exit- * The variable sym contains the internal representation of name ***/
void SGPreDefine (const char *name, int *sym, NodeTuplePtr env, int index, DefTableKey k) /* Pre-define an identifier * On entry- * name is the external representation of the identifier * sym addresses an integer-valued variable * env specifies the range in which to define the identifier * index specifies the graph in which to define the identifier * k is the known key bound to the identifier * On exit- * The variable sym contains the internal representation of name * The binding has been created ***/
Any developer invocation of
void SGPreDefineNode (GraphsDescrPtr descr, const char *name, int *sym, DefTableKey key, NodeTuplePtr *node, NodeTuplePtr parent) /* Pre-define a range * On entry- * descr is the metadata for the ScopeGraphs module instantiation * being initialized * name is the external representation of the pre-defined range's owner * key is the known key for the pre-defined range's owner * node addresses a NodeTuplePtr-valued variable * parent is tip of the pre-defined range's parent edge * On exit- * The variable sym contains the internal representation of name * the variable node contains a pointer to the pre-defined range ***/
Any developer invocation of
|