General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
Questions, Comments, ....
|
 |
Name analysis according to scope rules



This module implements a standard contour model for name analysis. The
data structure is a tree of scopes, each of which can contain an
arbitrary number of definitions. A definition is a binding of an
identifier to an object in the definition table
(see PDL Reference Manual).
For an identifier idn and a scope sc
there is at most one binding in sc .
The environment module provides operations for
building scope trees, adding definitions to specific scopes, and
searching individual scopes or sequences of scopes for the binding of
a particular identifier. Inheritance relations can be established
between scopes to support object-oriented name analysis.
The module is capable of building multiple trees of scopes
in order to model distinct name spaces, such that bindings
in one tree do not effect the lookup in another tree.
The module places no constraints on the sequence of construction,
definition and lookup operations; there is one exception: an
inheritance relation may not be established for a scope that
has already been involved in a lookup operation.
The module implements certain lookup operations such that
linear search through several scopes is avoided in order to
reduce the amortized asymptotic cost of name analysis.
This effect on efficiency can be lost if the sequence of
those lookup operations arbitrarily often switches the
scopes they are applied to.
The modules described in the Name Analysis Library (see Name Analysis of Specification Module Library: Name Analysis)
provide solutions for common name analysis tasks based on this
environment module.
If they are used the interface of this
module is available for use in .lido specifications;
otherwise the interface is made available by adding
$/Name/envmod.specs to the processor specification.
In C modules the interface of the environment module is introduced
by #include "envmod.h" .
The environment module exports the following types, values, functions
and macros.
Exported types and their null values:
Environment
- A value of type
Environment is a pointer to a node in the
tree of scopes.
It is used either to refer to a single scope, or to refer to
this scope and all the scopes that are visible from it, i.e.
its ancestors in the tree and the scopes that are inherited
by them.
NoEnv
- Is a value that represents no environment. Operations applied
to
NoEnv have no effect.
Binding
- A value of type
Binding is a pointer to a triple
(int idn, Environment sc, DefTableKey key)
that represents a binding of
of an identifier idn in a scope sc
to an object key .
The bindings of a scope form a list that can be traversed
using macors described below.
NoBinding
- is a value that represents no binding.
Scope, NoScope
- are synonyms for
Binding and NoBinding
InheritPtr
- is an opaque type that is used to traverse inheritance relations.
NoInherit
- is a value that indicates the end of inheritance traversal.
The following functions are provided for constructing the
tree of scopes:
Environment NewEnv ()
- creates a new tree consisting of a single, empty scope and
returns a reference to that empty scope.
Environment NewScope (Environment env)
- creates a new empty scope as a child of the scope referenced by its
argument and returns a reference to that empty scope.
The following functions are provided to establish and to check
inheritance relations between scopes:
int InheritClass (Environment tocl, Environment fromcl)
- establishes an inheritance relation from the scope
fromcl
to the scope tocl is established, if tocl and
fromcl are different scopes in the same tree of scopes,
and if the graph of inheritance relations remains acyclic
when adding the relation, and if the scope tocl
has not yet been involved in a lookup for a binding.
InheritClass returns 1 if the inheritance relation
could be established; otherwise it returns 0.
int Inheritsfrom (Environment tocl, Environment fromcl)
- returns 1 if
tocl and fromcl are the same scopes,
or if there is a direct or indirect inheritance relation from
the scope fromcl to the scope tocl ;
otherwise it returns 0.
After a call of Inheritsfrom no further inheritance relation
can be established for tocl or fromcl .
The following functions are provided to establish a binding
within a scope. They differ in the following aspects:
The key for the new binding is given as an argument
(BindKey , AddIdn , BindKeyInScope ), or a
new key is created for a new binding (BindIdn , DefineIdn ,
BindInScope ).
Functions that should be preferred for efficiency reasons
if several operations on one scope occur in a row
(BindKey , AddIdn , BindIdn , DefineIdn ),
or if scopes are arbtrarily switched
(BindKeyInScope , BindInScope ).
DefineIdn and AddIdn are macros for calls
of BindIdn and BindKey respectively.
They are provided for compatibility with previous versions
of the environment module.
Binding BindKey (Environment env, int idn, DefTableKey key)
- checks the scope referenced by its
env argument for a
binding of the identifier specified by its idn argument.
If no such binding is found, a binding of the identifier idn
to the definition table object specified by key is added to scope
env . BindKey returns the value NoBinding
if a binding already exists, and returns the new binding otherwise.
int AddIdn (Environment env, int idn, DefTableKey key)
- is a macro that calls
BindKey .
AddIdn returns the value 0 if a definition
for idn already exists, and returns 1 otherwise.
Binding BindKeyInScope (Environment env, int idn, DefTableKey key)
- has the same effect as
BindKey .
BindKeyInScope should be used for efficiency reasons
if bindings are established in several different scopes before
lookups are performed in them.
Binding BindIdn (Environment env, int idn)
- behaves exactly like
BindKey , except that if the
referenced scope contains no binding of idn then
BindIdn obtains a value from NewKey() and
binds idn to that value in scope env .
In addition, BindIdn always returns the
the binding associated with idn .
DefTableKey DefineIdn (Environment env, int idn)
- is a macro that calls
BindIdn .
Instead of a binding it returns its key.
Binding BindInScope (Environment env, int idn)
- has the same effect as
BindIdn .
BindInScope should be used for efficiency reasons
if bindings are established in several different scopes before
lookups are performed in them.
The following functions are provided to lookup bindings for
given identifiers. They differ in the following aspects:
Only the scope given as argument and those scopes it inherits
from are considered for the lookup
(BindingInScope , KeyInScope ),
or the scope given as argument, its ancestors in the tree of scopes
and those scopes they inherit from are considered for the lookup
(BindingInEnv , KeyInEnv ).
KeyInScope and KeyInEnv are macros for calls
of BindingInScope and BindingInEnv respectively.
They are provided for compatibility with previous versions
of the environment module.
For ease of understanding the effects of the functions
are described here as if the bindings of scopes were traversed
in a linear search. In fact the implementation avoids
such linear search where possible.
Binding BindingInScope (Environment env, int idn)
- checks the scope referenced by its
env argument,
for a binding of the identifier specified by its idn argument.
Thereafter the scopes that are directly or indirectly
inherited by env are searched, such that a scope tocl
is considered before a scope fromcl , if tocl
inherits from fromcl .
The binding that is found first is returned;
If no binding is found NoBinding is returned.
DefTableKey KeyInScope (Environment env, int idn)
- is a macro for a call of
BindingInScope such that
the key of the found binding is returned, or NoKey
if no binding is found.
Binding BindingInEnv (Environment env, int idn)
- has the same effect as
BindingInScope except that
if no binding for idn is found for scope env
then the search continues as if BindingInScope
was applied to successive ancestors of env .
The binding that is found first is returned;
If no binding is found NoBinding is returned.
DefTableKey KeyInEnv (Environment env, int idn)
- is a macro for a call of
BindingInEnv such that
the key of the found binding is returned, or NoKey
if no binding is found.
The following functions allow to find further bindings that
are related in some way to a given one:
Binding OverridesBinding (Binding bind)
- yields a hidden binding.
Let
bind be a binding of identifier idn in
a scope e . Then the binding for idn is
returned which the operation BindingInEnv would
have found next, if any; otherwise NoBinding is returned.
Binding NextInhBinding (Environment env, Binding bind)
- yields a binding that is also reachable and not hidden
due to multiple inheritance relations.
Let
bind be a binding of identifier idn in a scope e
that has been obtained by a call BindingInScope (env, idn)
by BindingInEnv (env, idn) , or by NextInhBinding (env, idn) ,
and let tocl be env or its next ancestor that
inherits from e .
Then NextInhBinding returns a binding of identifier idn ,
if any, in a scope ep that is inherited by tocl
but not by e ;
otherwise NoBinding is returned.
DefTableKey NextInhKey (Environment env, int idn, DefTableKey key)
- has the same effect as
NextInhBinding , except that
the object keys of bindings are supplied and returned instead of bindings.
The following functions are provided to obtain information on
environments:
Binding DefinitionsOf(Environment env)
- returns the first binding of the scope
env , if any;
otherwise NoBinding is returned.
int IdnOf(Binding b)
- returns the identifier of the binding triple.
DefTableKey KeyOf(Binding b)
- returns the key of the binding triple.
Environment EnvOf(Binding b)
- returns the environment of the binding triple.
Binding NextDefinition(Binding b)
- returns the next binding of the scope
env , if any;
otherwise NoBinding is returned.
Environment ParentOf(Environment env)
- returns the parent of
env int the tree of scopes, if any;
otherwise NoEnv is returned.
DefTableKey SetKeyOfEnv(Environment env, DefTableKey k)
- associates a key
k to the scope env , that
may be used to relate properties to it.
Initially NoKey is associated to env .
DefTableKey KeyOfEnv(Environment env)
- returns the key associated to
env .
int IsClass(Environment env)
- returns 1 if the scope
env has been argument of a
call of InheritClass ; otherwise 0 is returned.
InheritPtr DirectInherits(Environment env)
- returns one direct inheritance relation to
env
established by a call of
InheritClass(env,fromcl) ,
if any; otherwise NoInherit is returned.
Environment EnvOfInherit(InheritPtr inh)
- returns the scope
fromcl of the inheritance relation inh .
InheritPtr NextInherit(InheritPtr inh)
- returns the next direct inheritance relation,
if any; otherwise
NoInherit is returned.



|