General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
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 following types and constant values are provided to represent name
analysis data:
Environment
- A pointer to a node in the tree of scopes.
It is used either to refer to a single scope, or
to refer to a scope and all the scopes that are visible from it
(i.e. its ancestors in the tree and the scopes that are inherited
by each).
NoEnv
- A constant of type
Environment that represents no environment.
Binding
- A pointer to a triple
(int idn, Environment sc, DefTableKey key)
that represents the binding
of the identifier idn
in the scope pointed to by sc
to the entity key.
NoBinding
- A constant of type
Binding that represents no binding.
InheritPtr
- An opaque type used to traverse inheritance relations.
NoInherit
- A constant of type
InheritPtr that indicates the end of an
inheritance traversal.
The following operations are provided for constructing the
tree of scopes:
Environment NewEnv ()
- A function that creates a new tree consisting of a single, empty scope and
returns a reference to that empty scope.
Environment NewScope (Environment env)
- A function that creates a new empty scope as a child of the scope
pointed to by
env and returns a reference to that empty scope.
An inheritance relation from scope fromcl to scope tocl means
that the scope tocl inherits the bindings of the scope
fromcl.
The following operations are provided to establish and to check
inheritance relations:
int InheritClass (Environment tocl, Environment fromcl)
- A function that establishes an inheritance relation
from the scope
fromcl to the scope tocl
if and only if
tocl and fromcl are different scopes in the same tree of scopes
- the graph of inheritance relations remains acyclic when adding the relation
- 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)
- A function that 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 Inheritsfrom returns 0.
After a call of Inheritsfrom, no further inheritance relation
can be established for tocl or fromcl.
The following operations are provided to establish a binding
within a scope:
Binding BindKey (Environment env, int idn, DefTableKey key)
- A function that 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)
- A macro that calls
BindKey.
AddIdn returns the value 0 if BindKey returns
NoBinding, and returns 1 otherwise.
Binding BindKeyInScope (Environment env, int idn, DefTableKey key)
- A function that 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)
- A function that 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,
BindIdn obtains a value from NewKey() and
binds idn to that value in scope env.
BindIdn returns the
the binding associated with idn.
DefTableKey DefineIdn (Environment env, int idn)
- A macro that calls
BindIdn and returns the key of the binding
returned by BindIdn.
Binding BindInScope (Environment env, int idn)
- A function that 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.
These operations are very similar, but they differ in two aspects:
-
The key for the new binding is given as an argument
(
BindKey, AddIdn, BindKeyInScope), or a
new key is created for the new binding (BindIdn, DefineIdn,
BindInScope).
-
Functions that should be preferred for efficiency reasons
if several operations on one scope occur in sequence
(
BindKey, AddIdn, BindIdn, DefineIdn),
or if scopes are arbitrarily switched between operations
(BindKeyInScope, BindInScope).
DefineIdn and AddIdn
are provided for compatibility with previous versions
of the environment module.
The following operations are provided to lookup bindings for
given identifiers.
For ease of understanding they
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)
- A function that checks the scope referenced by its
env argument
for a binding of the identifier specified by its idn argument.
If no binding for idn is found,
the scopes that are directly or indirectly
inherited by env are searched.
During that search, a scope tocl
is considered before a scope fromcl if tocl
inherits from fromcl.
The first binding found is returned;
if no binding is found then NoBinding is returned.
DefTableKey KeyInScope (Environment env, int idn)
- A macro that calls
BindingInScope and returns the key of the
binding found.
NoKey is returned if no binding is found by BindingInScope.
Binding BindingInEnv (Environment env, int idn)
- A function that 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 successively to ancestors of env in the tree of scopes.
DefTableKey KeyInEnv (Environment env, int idn)
- A macro that calls
BindingInEnv and returns the key of the
binding found.
NoKey is returned if no binding is found by BindingInEnv.
These operations are very similar, but they differ in one aspect:
-
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
are provided for compatibility with previous versions
of the environment module.
The following operations find further bindings that
are related in some way to a given one:
Binding OverridesBinding (Binding bind)
- A function that yields a hidden binding.
Let
bind be a binding of identifier idn in a scope e.
Then OverridesBinding returns the value that
BindingInEnv(e,idn) would have returned if the binding bind
had not existed.
Binding NextInhBinding (Environment env, Binding bind)
- A function that yields a binding that is also visible
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),
BindingInEnv(env, idn), or 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)
- A function that has the same effect as
NextInhBinding, except that
the keys of bindings (instead of the bindings themselves)
are supplied and returned.
The following operations are provided to obtain information from
environments:
Binding DefinitionsOf(Environment env)
- A function that returns the first binding of the scope
env.
It returns NoBinding if env is NoEnv or
if no identifiers are bound in env.
Binding NextDefinition(Binding b)
- A function that returns the next binding of the scope
EnvOf(b).
It returns NoBinding if b is NoBinding or
if b is the last binding of EnvOf(b).
int IdnOf(Binding b)
- A function that returns the identifier bound by
b.
It returns NoIdn if b is NoBinding.
DefTableKey KeyOf(Binding b)
- A function that returns the key bound by
b.
It returns NoKey if b is NoBinding.
Environment EnvOf(Binding b)
- A function that returns the environment containing
b.
It returns NoEnv if b is NoBinding.
Environment ParentOf(Environment env)
- A function that returns the parent of
env in a tree of scopes.
It returns NoEnv if env is NoEnv or
if env is the root of the tree.
DefTableKey SetKeyOfEnv(Environment env, DefTableKey k)
- A function that associates the key
k with the scope env.
It returns k unless env is NoEnv;
in that case it returns NoKey.
DefTableKey KeyOfEnv(Environment env)
- A function that returns the key
k associated with the scope
env by the most recent operation SetKeyOfEnv(env,k).
It returns NoKey if env is NoEnv or
if SetKeyOfEnv(env,k) has never been executed.
int IsClass(Environment env)
- A function that returns 1 if the scope
env has been argument of a
call of InheritClass; otherwise 0 is returned.
InheritPtr DirectInherits(Environment env)
- A function that returns the first direct inheritance relation to
env
established by a call of InheritClass(env,fromcl).
It returns NoInherit if env is NoEnv or
if InheritClass(env,fromcl) has never been invoked.
InheritPtr NextInherit(InheritPtr inh)
- A function that returns the next direct inheritance relation.
It returns
NoInherit if inh is NoInherit or
if there are no more direct inheritances for the given scope.
Environment EnvOfInherit(InheritPtr inh)
- A function that returns the scope
fromcl
of the inheritance relation inh.
|
