Eli   Documents

General Information

 o Eli: Translator Construction Made Easy
 o Global Index
 o Frequently Asked Questions
 o Typical Eli Usage Errors

Tutorials

 o Quick Reference Card
 o Guide For new Eli Users
 o Release Notes of Eli
 o Tutorial on Name Analysis
 o Tutorial on Scope Graphs
 o Tutorial on Type Analysis
 o Typical Eli Usage Errors

Reference Manuals

 o User Interface
 o Eli products and parameters
 o LIDO Reference Manual
 o Typical Eli Usage Errors

Libraries

 o Eli library routines
 o Specification Module Library

Translation Tasks

 o Lexical analysis specification
 o Syntactic Analysis Manual
 o Computation in Trees

Tools

 o LIGA Control Language
 o Debugging Information for LIDO
 o Graphical ORder TOol

 o FunnelWeb User's Manual

 o Pattern-based Text Generator
 o Property Definition Language
 o Operator Identification Language
 o Tree Grammar Specification Language
 o Command Line Processing
 o COLA Options Reference Manual

 o Generating Unparsing Code

 o Monitoring a Processor's Execution

Administration

 o System Administration Guide

Mail Home

Name Analysis Reference Manual

Previous Chapter Next Chapter Table of Contents


Application Program Interface

Computational 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 instantiation

All 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.

GraphsDescrPtr
represents an instantiation of the ScopeGraphs module. Each instantiation of the ScopeGraphs module results in a single value of type GraphsDescrPtr, which is available as the value of the attribute *RootScope.*GraphsDescr.

NodeTuplePtr
represents a range. NodeTuplePtr has a distinguished value, NoNodeTuple, that represents no range. A NodeTuple is an array of scope graph nodes that are equivalent under the isomorphism defined by the ScopeGraphs module instantiation (see Scope graphs).

ScopeNodePtr
represents a scope graph node. ScopeNodePtr has a distinguished value, NoScopeNode, that represents no scope graph node.

FPItemPtr
represents a worklist task (see Worklist search).

As an example, consider the ScopeGraphs module instantiated by:

$/Name/ScopeGraphs.gnrc +instance=A_ :inst

Assume that MaxIsoGraph is set to 4, and that the attribute A_RootScope.A_NumberOfIsoGraphs has the value 2 (see Isomorphic Scope Graphs).

In this case, NodeTuplePtr values point to arrays of four ScopeNodePtr values. Instance A_ uses only the array elements with graph index 0 or 1, however, since A_RootScope.A_NumberOfIsoGraphs=2. The GraphsDescrPtr value that represents the instantiation can be found at A_RootScope.A_GraphsDescr.

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 *WL roles' computations create appropriate tasks and add them to a worklist rather than actually carrying them out (see Worklist search). Dependences among the tasks are represented by links between the worklist entries. Since none of the tasks is being executed, the program-specific dependences mentioned above do not affect the order of execution of the computations that create worklist tasks.

Once all tasks have been added to the worklist, they can be carried out by an indivisible operation called FPSolveItems. FPSolveItems scans through the worklist, completing each task that depends only on completed tasks, and iterates until all tasks have been completed. Although FPSolveItems could require @math{n} scans through a worklist of length @math{n}, in practice it seldom requires more than a single scan. The reasons seem to be that programmers don't use inherited names for edge tips, and that the ScopeGraphs module is careful to avoid out-of-order dependence by putting the individual tasks required to resolve a qualified edge tip name onto the worklist in execution order.

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 OutSideInDeps role (see The OutSideInDeps role). OutSideInDeps is automatically inherited by the root symbol, so every tree node has an OutSideInDeps ancestor even if the language has no type-qualified tip names.

Let @math{N} be the set of tree nodes whose symbols inherit OutSideInDeps, and let @math{T_n} be the subtree rooted at node @math{n \in N}. Finally, let @math{t_n} be @math{T_n - {T_k | k \in N} is a descendent of @math{n}}. Tasks must be added to the worklist, and FPSolveItems executed, independently for each @math{t_n}. The subtrees must be processed in outside-in order.

FPSolveItems cannot be executed in @math{t_n} until the instantiation's state satisfies three conditions:

This dependence is made explicit through the use of the abstract role PreWork, provided by the ScopeGraphs module.

PreWork is inherited by every role that establishes a range, processes a defining occurrence, establishes a bound edge, or creates a worklist task. The accumulating attribute *PreWork.*PreWorkDone represents the post-condition of the computation in each case (see Accumulating Computations of LIDO - Reference Manual). If a developer creates a computation that processes a defining occurrence, establishes a bound edge, or creates a worklist task, then the developer must arrange for that computation to have an attribute *PreWork.*PreWorkDone as a post-condition. Then the pre-condition for FPSolveItems in @math{t_n} is *OutSideInDeps.*PreWorkDone:

CLASS SYMBOL *OutSideInDeps COMPUTE
  SYNT.*PreWorkDone =
    CONSTITUENTS *PreWork.*PreWorkDone SHIELD *OutSideInDeps;
END;

*OutSideInDeps.*FPSolved is the void attribute that characterizes the state in which FPSolveItems has completed execution. In order to ensure that the subtrees are processed in outside-in order, any operation that adds a task to the worklist must have the following as a precondition:

INCLUDING *OutSideInDeps.*FPSolved

When FPSolveItems has completed execution, the scope graph is complete for the current @math{t_n}. Computations associated with the *GC roles can then be executed (see Graph-complete search). It may be necessary to intersperse type analysis computations to bind type names in declarations (see Interaction with type analysis).

Functions that create nodes, edges, and bindings

The 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 newNodeTuple is called by developer code, since that code is generally not associated with a particular line in the source text.

Any developer invocation of newNodeTuple must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

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 NodeTupleOwnerKey must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

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 NABindIdn must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

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 addEdge must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

Functions that initiate worklist operations

The 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 *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

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, FPInsertDef creates a temporary binding there that may be replaced later (see Functions that create nodes, edges, and bindings).

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 graphs

The 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 FPAddEdge task
 * On exit-
 *   getFPEdgeKey returns the edge key found by the task
 ***/

In the following functions, the argument u is a unique key whose properties characterize an applied occurrence. At least the properties Sym, GraphIndex, and Coord must be set to suitable values prior to invoking the function. Further properties may be set to support functions implementing the developer interface (see Implementing Language-Specific Behavior).

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 r is obtained from the qualifier, and the search does not follow parent edges (see The generic lookup).

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 SGPreDefId module provides the following functions, used to implement the pre-definition macros (see Pre-defined Identifiers). They may be called in any `.lido' file, and in any other context that includes the header file `SGPreDefMod.h'.

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 SGPreDefine must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.

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 SGPreDefineNode must guarantee that the *PreWorkDone attribute of some node inheriting *PreWork is assigned after the function returns.


Previous Chapter Next Chapter Table of Contents