C Checker Reference Manual

January 1998

F.1 Introduction

It is expected that the general user will have little direct contact with the token syntax, instead using the asbstract standard headers provided or using the tspec tool [Ref. 5] to generate their own token interface header files automatically. However, it may occasionally be necessary to use the raw power of the token syntax directly.

As an example of the power of the token syntax consider the program below:

	#pragma token TYPE FILE#
	#pragma token EXP rvalue:FILE *:stderr#
	int fprintf(FILE *, const char *, ...);
	void f(void) {
		fprintf(stderr,"hello world\n");
	}

The second line of the example, which introduces a token for an expression, is somewhat more complicated. In order to make use of an expression, it is necessary to know its type and whether or not it is an lvalue (i.e. whether or not it can be assigned to). As can be seen from the example however, it is not necessary to know the exact type of the expression because a token can be used to represent its type.

The TenDRA compiler makes no assumptions about the possible definitions of tokens and will raise an error if a program requires information about an undefined token. In this way many errors resulting from inadvertent use of a definition present on the developer's system can be detected. For example, developers often assume that the type FILE will be implemented by a structure type when in fact the ISO C standard permits the implementation of FILE by any type. In the program above, any attempt to access members of stderr would cause the compiler to raise an error.

In the compilation phase the source text written in the C language is mapped to an object code format. This object code is generally not complete in itself and must be linked with other program segments such as definitions from the system libraries.

When tokens are involved there is an extra stage in the construction process where undefined tokens in one program segment are linked with their definitions in another program segment. To summarise, program construction using TDF and the TenDRA tools has four basic operations:

1. Source file compilation to TDF. The TDF produced may be incomplete in the sense that it may contain undefined tokens;

2. TDF linking. The undefined tokens represented in TDF are linked to their definitions in other compilation modules or libraries. During linking, tokens with the same identifier are treated as the same token;

3. TDF translation. This is the conversion of TDF into standard object file format for a particular machine system. The program is still incomplete at this stage in the sense that it may contain undefined library functions;

4. Object file linking. This corresponds directly to standard object file linking.

F.3 The token syntax

	token identification:
		name-spaceopt identifier # external-identifier
opt

	name-space: 
		TAG

1. The label space, in which all label identifiers reside;

2. The tag space, in which structure, union and enumeration tags reside;

3. The member name space, in which structure and union member selectors reside;

4. The macro name space, in which all macro definitions reside. Token identifiers in the macro name space have no definition and so are not expanded. However, they behave as macros in all other respects;

5. The ordinary name space in which all other identifiers reside.

• Designation is the classification of the value delivered by evaluating the expression. The three possible designations, implied by the ISO C standard, section 6.3, are:
  • value - expression describes the computation of a value;

  • object - expression designates a variable which may have an associated type qualifier giving the access conditions;

  • function designation - expression designates a function.

• Type specifies the type of the expression ignoring any type qualification;

• Constancy is the property of being a constant expression as specified in the ISO C Standard section 6.4.

	exp-token:
		EXP exp-storage : type-name :
		NAT
	exp-storage:
		rvalue
		lvalue
		const

• The exp-storage is either lvalue or rvalue. If it is lvalue, then the token is an object designation without type qualification. If it is rvalue then the token is either a value or a function designation depending on whether or not its type is a function type.

• The type-name is the type of the expression to which the token refers.

• expression tokens cannot be hidden by using an inner scope;

• with respect to #ifdef, expression tokens are defined;

• the scope of expression tokens can be terminated by #undef.

	#pragma token EXP rvalue : int : x#

	#pragma token STATEMENT init_globs#
	int g(int);
	int f(int x) { init_globs return g(x);}

• the type char;
• signed integral types;
• unsigned integral types;
• floating types;
• character types;
• enumeration types;
• array types;
• structure types;
• union types;
• function types;
• pointer types;

• integral types - consisting of the signed integral types, the unsigned integral types and the type char;

• arithmetic types - consisting of the integral types and the floating types;

• scalar types - consisting of the arithmetic types and the pointer types;

• aggregate types - consisting of the structure and array types;

• derived types - consisting of array, structure, union, function and pointer types;

• derived declarator types - consisting of array, function and pointer types.

	type-token:
		TYPE
		VARIETY
		ARITHMETIC
		STRUCT
		UNION

Once general type tokens have been introduced, they can be used to construct derived declarator types in the same way as conventional type declarators. For example:

	#pragma token TYPE t_t#
	#pragma token TYPE t_p#
	#pragma token NAT n#
	typedef t_t *ptr_type; /* introduces pointer type */
	typedef t_t fn_type(t_p);/*introduces function type */
	typedef t_t arr_type[n];/*introduces array type */

This definition of lvalue conversion for general token types is used to allow objects of general tokenised types to be assigned to and passed as arguments to functions. The extensions to the semantics of function argument passing and assignment are as follows: if the type token is defined to be an array then the components of the array are assigned and passed as arguments to the function call; in all other cases the assignment and function call are the same as if the defining type had been used directly.

The default name space for the internal identifiers for general type tokens is the ordinary name space and all such identifiers must reside in this name space. The local identifier behaves exactly as if it had been introduced with a typedef statement and is thus treated as a typedef-name by the syntax analyser.

Type tokens can only be defined by using one of the operations known as type-resolution and assignment-resolution. Note that, as type token identifiers do not reside in the macro name space, they cannot be defined using #define statements.

Type-resolution operates on two types and is essentially identical to the operation of type compatibility (ISO C standard section 6.1.3.6) with one major exception. In the case where an undefined type token is found to be incompatible with the type with which it is being compared, the type token is defined to be the type with which it is being compared, thereby making them compatible.

The ISO C standard prohibits the repeated use of typedef statements to define a type. However, in order to allow type resolution, the compiler allows types to be consistently redefined using multiple typedef statements if:

• there is a resolution of the two types;
• as a result of the resolution, at least one token is defined.

	#pragma token TYPE t_t#
	typedef t_t *ptr_t_t;
	typedef int **ptr_t_t;

Type-resolution can also result in the definition of other tokens. The program below results in the expression token N being defined as (4*sizeof(int)).

	#pragma token EXP rvalue:int:N#
	typedef int arr[N];
	typedef int arr[4*sizeof(int)];

Assignment-resolution is similar to type-resolution but it occurs when converting an object of one type to another type for the purposes of assignment. Suppose the conversion is not possible and the type to which the object is being converted is an undefined token type. If the token can be defined in such a way that the conversion is possible, then that token will be suitably defined. If there is more than one possible definition, the definition causing no conversion will be chosen.

The syntax for introducing member selector tokens as follows:

	selector-token:
		MEMBER selector-type-name : type-name :
	selector-type-name:
		type-name
		type-name % constant-expression

	#pragma token STRUCT TAG s_t#
	#pragma token MEMBER char*: struct s_t:s_t_mem#

Internal identifiers of member selector tokens can only reside in the member name space of the compound type to which they belong. Clearly this is also the default name space for such identifiers.

When structure or union types are declared, according to the ISO C standard there is an implied ordering on the member selectors. In particular this means that:

• during initialisation with an initialiser-list the identified members of a structure are initialised in the order in which they were declared. The first identified member of a union is initialised;

• the addresses of structure members will increase in the order in which they were declared.

The decision to allow unordered member selectors has been taken deliberately in order to separate the decision of which members belong to a structure from that of where such member components lie within the structure. This makes it possible to represent extensions to APIs which require extra member selectors to be added to existing compound types.

As an example of the use of token member selectors, consider the structure lconv specified in the ISO C Standard library (section 7.4.3.1). The standard does not specify all the members of struct lconv or the order in which they appear. This type cannot be represented naturally by existing C types, but can be described by the token syntax.

There are two methods for defining selector tokens, one explicit and one implicit. As selector token identifiers do not reside in the macro name space they cannot be defined using #define statements.

Suppose A is an undefined compound token type and mem is an undefined selector token for A. If A is later defined to be the compound type B and B has a member selector with identifier mem then A.mem is defined to be B.mem providing the type of A.mem can be resolved to the type of B.mem. This is known as implicit selector token definition.

In the program shown below the redefinition of the compound type s_t causes the token for the selector mem_x to be implicitly defined to be the second member of struct s_tag. The consequential type resolution leads to the token type t_t being defined to be int.

	#pragma token TYPE t_t#
	#pragma token STRUCT s_t#
	#pragma token MEMBER t_t : s_t : mem_x#
	#pragma token MEMBER t_t : s_t : mem_y#
	struct s_tag { int a, mem_x, b; }
	typedef struct s_tag s_t;

	#pragma DEFINE MEMBER type-name identifier : member-designator


	member-designator:
		identifier
		identifier . member-designator

The identifier provides the identification of the member selector within that compound type.

The member-designator provides the definition of the selector token. It must identify a selector of a compound type.

If the member-designator is an identifier, then the identifier must be a member of the compound type specified by the type-name. If the member-designator is an identifier, id say, followed by a further member-designator, M say, then:

• the identifier id must be a member identifying a selector of the compound type specified by type-name;

• the type of the selector identified by id must have compound type, C say;

• the member-designator M must identify a member selector of the compound type C.

In the example shown below, the selector token mem is defined to be the second member of struct s which in turn is the second member of struct s_t.

	#pragma token STRUCT s_t#
	#pragma token MEMBER int : s_t : mem#
	typedef struct {int x; struct {char y; int z;} s; } s_t;
	#pragma DEFINE MEMBER s_t : mem s.z

	#define SWAP(T,A,B) { \
		T x; \
		x=B; \
		B=A; \
		A=x; \
	}

Procedure tokens are based on this concept of parameterisation. Procedure tokens reference program constructs that are parameterised by other program constructs.

There are three methods of introducing procedure tokens. These are described in the sections below.

	general procedure:
		PROC { bound-toksopt | prog-pars
opt } token-introduction

	simple procedure:
		PROC ( bound-toksopt ) token-introduction


	bound-toks:
		bound-token
		bound-token, bound-toks

	bound-token:
		token-introduction name-spaceopt identifier


	prog-pars:
		program-parameter
		program-parameter, prog-pars

	program parameter:
		EXP identifier
		STATEMENT identifier
		TYPE type-name-identifier
		MEMBER type-name-identifier : identifier

The bound-toks are the bound token dependencies which describe the program constructs upon which the procedure token depends. These should not be confused with the parameters of the token. The procedure token introduced in:

	#pragma token PROC {TYPE t,EXP rvalue:t**:e|EXP e} EXP:rvalue:t:dderef#

The bound token dependencies are introduced in exactly the same way as the tokens described in the previous sections with the identifier corresponding to the internal identification of the token. No external identification is allowed. The scope of these local identifiers terminates at the end of the procedure token introduction, and whilst in scope, they hide all other identifiers in the same name space. Such tokens are referred to as "bound" because they are local to the procedure token.

Once a bound token dependency has been introduced, it can be used throughout the rest of the procedure token introduction in the construction of other components.

The prog-pars are the program parameters. They describe the parameters with which the procedure token is called. The bound token dependencies are deduced from these program parameters.

Each program parameter is introduced with a keyword expressing the kind of program construct that it represents. The keywords are as follows:

• EXP . The parameter is an expression and the identifier following EXP must be the identification of a bound token for an expression. When the procedure token is called, the corresponding parameter must be an assignment-expression and is treated as the definition of the bound token, thereby providing definitions for all dependencies relating to that token. For example, the call of the procedure token dderef, introduced above, in the code below:

  	char f(char **c_ptr_ptr){
  		return dderef(c_ptr_ptr);
  	}
  

  causes the expression, e, to be defined to be c_ptr_ptr thus resolving the type t** to be char **. The type t is hence defined to be char, also providing the type of the expression obtained by the application of the procedure token dderef;

• STATEMENT. The parameter is a statement. Its semantics correspond directly to those of EXP;

• TYPE. The parameter is a type. When the procedure token is applied, the corresponding argument must be a type-name. The parameter type is resolved to the argument type in order to define any related dependencies;

• MEMBER. The parameter is a member selector. The type-name specifies the composite type to which the member selector belongs and the identifier is the identification of the member selector. When the procedure token is applied, the corresponding argument must be a member-designator of the compound type.

Consider the two procedure token introductions below, corresponding to the macro SWAP described earlier.

	/* General procedure introduction */
	#pragma token PROC{TYPE t,EXP lvalue:t:e1,EXP lvalue:t:e2 | \
		TYPE t,EXP e1,EXP e2 } STATEMENT SWAP#
	/* Simple procedure introduction */
	#pragma token PROC(TYPE t,EXP lvalue:t:,EXP lvalue:t: ) STATEMENT SWAP#

The syntax for introducing function procedure tokens is:

	function-procedure:
		FUNC type-name :

	EXP rvalue:

	#pragma token FUNC int(int): putchar#

	#undef putchar

The syntax for defining procedure tokens is given below and is based upon the standard parameterised macro definition. However, as in the definitions of expressions and statements, the #defines of procedure token identifiers are evaluated in phase 7 of translation as described in the ISO C standard.

	#define identifier ( id-listopt ) assignment-expression

	#define identifier ( id-listopt ) statement


	id-list:
		identifier
		identifer, id-list

None of the bound token dependencies can be defined during the evaluation of the definition of the procedure token since they are effectively provided by the arguments of the procedure token each time it is called. To illustrate this, consider the example below based on the dderef token used earlier.

	#pragma token PROC{TYPE t, EXP rvalue:t**:e|EXP e}EXP rvalue:t:dderef#
	#define dderef (A) (**(A))

Again, the presence of a procedure token introduction can alter the semantics of a program. Consider the program below.

	#pragma token PROC {TYPE t, EXP lvalue:t:,EXP lvalue:t:}STATEMENT SWAP#
	#define SWAP(T,A,B)\
		{T x; x=B; B=A; A=x;}
	void f(int x, int y) {
		SWAP(int, x, y)
	}

Function procedure tokens are introduced with tentative implicit definitions, defining them to be direct calls of the functions they reference and effectively removing the in-lining capability. If a genuine definition is found later in the compilation, it overrides the tentative definition. An example of a tentative definition is shown below:

	#pragma token FUNC int(int, long) : func#
	#define func(A, B) (func) (A, B)

F.10 Tokens and APIs

In order to produce executable code, definitions of the interface tokens must be provided on all target machines. This is done by compiling the interfaces with the system headers and libraries.

When developing applications, programmers must ensure that they do not accidentally define a token expressing an API. Implementers of APIs, however, do not want to inadvertently fail to define a token expressing that API. Token definition states have been introduced to enable programmers to instruct the compiler to check that tokens are defined when and only when they wish them to be. This is fundamental to the separation of programs into portable and unportable parts.

When tokens are first introduced, they are in the free state. This means that the token can be defined or left undefined and if the token is defined during compilation, its definition will be output as TDF.

Once a token has been given a valid definition, its definition state moves to defined. Tokens may only be defined once. Any attempt to define a token in the defined state is flagged as an error.

There are three more token definition states which may be set by the programmer. These are as follows:

• Indefinable - the token is not defined and must not be defined. Any attempt to define the token will cause an error. When compiling applications, interface tokens should be in the indefinable state. It is not possible for a token to move from the state of defined to indefinable;

• Committed - the token must be defined during the compilation. If no definition is found the compiler will raise an error. Interface tokens should be in the committed state when being compiled with the system headers and libraries to provide definitions;

• Ignored - any definition of the token that is assigned during the compilation of the program will not be output as TDF;

	#pragma token-op token-id-listopt

	token-op:
		define
		no_def
		ignore
		interface

	token-id-list:	
		TAGopt identifier dot-listopt
 token-id-listopt

	dot-list:
		. member-designator

The token-op specifies the definition state to be associated with the tokens in the token-id-list. There are three literal operators and one context dependent operator, as follows:

1. no_def causes the token state to move to indefinable.

2. define causes the token state to move to committed;

3. ignore causes the token state to move to ignored;

4. interface is the context dependent operator and is used when describing extensions to existing APIs.

The interface operator has a variable interpretation to allow the correct definition state to be associated with these `base-API tokens'. The compiler associates a compilation state with each file it processes. These compilation states determine the interpretation of the interface operator within that file.

The default compilation state is the standard state. In this state the interface operator is interpreted as the no_def operator. This is the standard state for compiling applications in the presence of APIs;

Files included using:

	#include header

The implementation compilation state is associated with files included using:

	#pragma implement interface header

Including a file using:

	#pragma extend interface header