|
|
|
|
General Information
Tutorials
Reference Manuals
Libraries
Translation Tasks
Tools
Administration
|
|
Tutorial on Type Analysis
Type Definitions
This chapter introduces type definitions to the language.
A name can be defined for any Here is an example program with type definitions. It makes use of the facility that identifiers may be defined after their uses: TypedefExamp[102]== begin var tt rv; type t tt; type record int i, bool b, real r end t; var int j, bool c, real s; var t rt; j = rv.i; c = rv.b; s = rv.r; rt = rv; end This macro is attached to a product file. The following productions are added to the grammar: Abstract type declaration syntax[103]== RULE: Declaration ::= 'type' TypeDenoter TypeDefIdent ';' END; RULE: TypeDefIdent ::= Ident END; RULE: TypeDenoter ::= TypeUseIdent END; RULE: TypeUseIdent ::= Ident END; This macro is invoked in definition 113.
A type definition introduces a new name for a type given
by the
In our language we specify that
a type definition does not introduce a new type, rather it introduces
another name for a type. Hence, there may be many different
names for the same type. Furthermore, even two
Hence, in the following specification we only have to characterize
a defining occurrence of a type identifier by the corresponding
roles of the name analysis module and those for a defining
occurrence of a type identifier ( Type declaration computation[104]==
SYMBOL TypeDefIdent INHERITS
ChkUnique, IdDefScope, IdentOcc,
TypeDefDefId, ChkTypeDefDefId
END;
RULE: Declaration ::= 'type' TypeDenoter TypeDefIdent ';' COMPUTE
TypeDefIdent.Type = TypeDenoter.Type;
END;
This macro is invoked in definition 113.
Used occurrences of type identifiers are characterized by the module
roles Used type identifiers[105]== SYMBOL TypeUseIdent INHERITS IdUseEnv, IdentOcc, ChkIdUse, TypeDefUseId, ChkTypeDefUseId END; RULE: TypeDenoter ::= TypeUseIdent COMPUTE TypeDenoter.Type = TypeUseIdent.Type; END; This macro is invoked in definition 113. A language that has facilities to define names for types and allows identifier uses before their definitions, opens the possibility to define types recursively, e.g. type record int i, rt x end rt;In many languages such a type rt would be disallowed,
because a value of type rt may not contain another value
of the same type. However, if the type of the component x
was defined to be pointer to rt instead of rt,
then a useful list type would be defined.
This example illustrates that the existence of type definitions may cause the need to specify which recursive type definitions are considered legal for a certain language. In our language, as defined so far, any recursion in a type definition is considered to be disallowed. However, the situation changes when there are types, like pointer types, such that that recursion is allowed when it passes through such a type.
Hence, we introduce three properties:
IsRecursiveType: int; IsNotRecursiveType: int; AllowRecurType: int; This macro is invoked in definition 112.
Such a check is performed by a function Check for recursive types[107]==
SYMBOL TypeDefIdent COMPUTE
IF (ChkRecursiveType (THIS.Type),
message (ERROR, CatStrInd ("Recursively defined type: ",
THIS.Sym),
0, COORDREF))
<- INCLUDING Program.GotAllTypes;
END;
This macro is invoked in definition 113. The implementation of the type walk algorithm uses a property that indicates whether a type is currently visited by the algorithm: Visiting property[108]== Visiting: int; This macro is invoked in definition 112. The following C module implements an algorithm that walks recursively through the components of a type to check whether the type is defined illegally recursively. RecTypeChk.head[109]== #include "RecTypeChk.h" This macro is attached to a product file. RecTypeChk.h[110]== #include "deftbl.h" extern int ChkRecursiveType (DefTableKey tp); This macro is attached to a product file. RecTypeChk.c[111]==
#include "pdl_gen.h"
#include "StructEquiv.h"
#include "Typing.h"
#ifdef TEST
#define TEST 1
#include <stdio.h>
#endif
static DefTableKey origType;
int VisitCompOfType (DefTableKey node, DefTableKey component)
/* This is the function used by the type walk that checks
for recursive types. It is called for every visit from a type node
to one of its components. 5 cases are distinguished, as explained below:
*/
{
#ifdef TEST
printf ("visit at %s (%d) component %s (%d)\n",
GetTypeName (node, "no name"),
GetTypeLine (node, 0),
GetTypeName (component, "no name"),
GetTypeLine (component, 0));
#endif
if (GetAllowRecurType (component, 0))
/* do not visit a component type that allows recursion */
return 1;
else {
if (FinalType (component) == FinalType (origType)) {
/* the type under investigation contains itself on a path
that does not lead through a type which allows for
recursion
*/
ResetIsRecursiveType (origType, 1);
ResetIsRecursiveType (component, 1);
return 2; /* terminate walk */
}
if (GetIsRecursiveType (component, 0)) {
/* The component type of the node is already
recognized to be recursive
*/
ResetIsRecursiveType (origType, 1);
return 2; /* terminate walk */
}
if (GetVisiting (component, 0)) {
/* This component lies on a non-pointer cycle
not involving the original type under investigation
*/
ResetIsRecursiveType (origType, 1);
ResetIsRecursiveType (component, 1);
return 2; /* terminate walk */
}
}
return 0; /* visit this component */
}
int RecWalkType (DefTableKey currType)
/*
Every direct or indirect component type of tp is visited, unless
the call VisitCompOfType (curr, comp) shortcuts the walk.
If it returns
0: comp is visited
1: comp is skipped
2: the walk is terminated
*/
{ DefTableKeyList compseq;
DefTableKey compType;
int visitRes;
currType = FinalType (currType);
/* Do not visit a node, that is currently visited: */
if (GetVisiting (currType, 0)) return 1;
ResetVisiting (currType, 1);
/* consider all component types: */
for (compseq = GetComponentTypes (currType, NULLDefTableKeyList);
compseq != NULLDefTableKeyList;
compseq = TailDefTableKeyList (compseq)) {
compType = FinalType (HeadDefTableKeyList (compseq));
/* Skip non-type: */
if (compType == NoKey) continue;
/* Visit this component: */
visitRes = VisitCompOfType (currType, compType);
/* The component visit indicates how to continue: */
switch (visitRes) {
case 0: /* dive into the component */
if (RecWalkType (compType)) {
/* the type walk is to be terminated */
visitRes = 2;
goto ret;
};
break;
case 1: /* do not dive into the component */
break;
case 2: /* terminate the walk */
visitRes = 2;
goto ret;
default:;
}
/* iteration of components continues */
}
visitRes = 0; /* components elaborated */
ret:
ResetVisiting (currType, 0);
return visitRes;
}
int ChkRecursiveType (DefTableKey tp)
/* on entry:
The results of the type equivalence analysis must be computed and
stored in the type data base.
tp represents a type.
method:
A walk through the type structure of tp is initiated,
and then executed.
VisitCompOfType (curr, comp) is called whenever
a direct component comp of the type curr is visited.
origType stores the type for which the recursion check is initiated.
Every type that is found to be illegally recursive is marked by
the property IsRecursiveType. It is also used to shortcut
the walk through the type structure.
on exit:
1 is returned if the type tp directly or indirectly
has tp as a component type, and the path to it is not
legal for recursion
0 is returned otherwise.
*/
{
tp = FinalType (tp);
origType = tp;
if (GetIsRecursiveType (tp, 0)) return 1;
if (GetIsNotRecursiveType (tp, 0)) return 0;
/* the result is not yet known: */
RecWalkType (tp);
return GetIsRecursiveType (tp, 0);
}
This macro is attached to a product file. TypeDef.pdl[112]== Check recursive types properties[106] Visiting property[108] This macro is attached to a product file. TypeDef.lido[113]== Abstract type declaration syntax[103] Type declaration computation[104] Used type identifiers[105] Check for recursive types[107] This macro is attached to a product file.
|
