C/C++ Producer Implementation

2.1. Source code modules

For convenience, the source code is divided between a number of directories:

base/

The base directory contains only the module containing the main function, the basic type descriptions and the Makefile.

obj_c/

obj_tok/

obj_templ/

The directories obj_c and obj_tok contain respectively the C and #pragma token headers generated from the type algebra by calculus. The directory obj_templ contains certain calculus template files.

utility/

Routines for such utility operations as memory allocation and error reporting, including the error catalogue.

parse/

Routines concerned with parsing and preprocessing the input, including the sid grammar.

construct/

Routines for building up and analysing the internal representation of the parsed code.

output/

Routines for outputting the internal representation in various formats including as a TDF capsule (see TDF Specification), a C++ spec file (see C/C++ Producer Implementation), or a tdfc2dump symbol table dump file.

Each module consists of a C source file, file.c say, containing function definitions, and a corresponding header file file.h containing the declarations of these functions. The header is included within its corresponding source file to check these declarations; it is protected against multiple inclusions by a macro of the form file_INCLUDED. The header contains a brief comment describing the purpose of the module; each function in the source file contains a comment describing its purpose, its inputs and its output.

The following table lists all the source modules in the C++ producer with a brief description of the purpose of each:

2.2. Type system

This section describes the type system used in the C++ producer. Unless otherwise stated the types are declared using the calculus tool as part of the algebra, c_class.alg. The design of this type algebra was clearly largely based on the concepts underlying the C++ language; however TDF provided an important influence, not merely as the intended target language, but also because of its clear presentation of essential language features.

int = "int" ;
unsigned = "unsigned" ;
string = "character *" ;
ulong_type (ulong) = "unsigned long" ;
BITSTREAM_P (bits) = "BITSTREAM *" ;
PPTOKEN_P (pptok) = "PPTOKEN *" ;

typedef unsigned char character ;

template < class T, int n > class A {
    T a [n] ;
    // ....
} ;

PROC ( TYPE T, EXP const : int : n ) ....

token -> {
    IDENTIFIER tok ;
    LIST TOKEN args ;
}

3.1. Arithmetic types

The representations of the basic arithmetic types are target dependent, so, for example, an int may contain 16, 32, 64 or some other number of bits. Thus it is necessary to introduce a token to stand for each of the built-in arithmetic types (including the long long types). Each integral type is represented by a VARIETY token as follows:

Similarly each floating point type is represent by a FLOATING_VARIETY token:

Each integral type also has an encoding as a SIGNED_NAT as shown above. This number is a bit pattern built up from the following values:

Any target dependent integral type can be represented by a SIGNED_NAT token using this encoding. This representation, rather than one based on VARIETYs, is used for ease of manipulation. The token:

~convert : ( SIGNED_NAT ) -> VARIETY

gives the mapping from the integral encoding to the representing variety. For example, it will map 6 to ~signed_int.

The token:

~promote : ( SIGNED_NAT ) -> SIGNED_NAT

describes how to form the promotion of an integral type according to the ISO C/C++ value preserving rules, and is used by the producer to represent target dependent promotion types. For example, the promotion of unsigned short may be int or unsigned int depending on the representation of these types; that is to say, ~promote ( 9 ) will be 6 on some machines and 10 on others. Although ~promote is used by default, a program may specify another token with the same sort signature to be used in its place by means of the directive:

#pragma TenDRA compute promote identifier

For example, a standard token ~sign_promote is defined which gives the older C sign preserving promotion rules. In addition, the promotion of an individual type can be specified using:

#pragma TenDRA promoted type-id : promoted-type-id

The token:

~arith_type : ( SIGNED_NAT, SIGNED_NAT ) -> SIGNED_NAT

similarly describes how to form the usual arithmetic result type from two promoted integral operand types. For example, the arithmetic type of long and unsigned int may be long or unsigned long depending on the representation of these types; that is to say, ~arith_type ( 7, 10 ) will be 7 on some machines and 11 on others.

Any tokenised type declared using:

#pragma token VARIETY v # tv

will be represented by a SIGNED_NAT token with external name tv corresponding to the encoding of v. Special cases of this are the implementation dependent integral types which arise naturally within the language. The external token names for these types are given below:

So, for example, a sizeof expression has shape ~convert ( size_t ). The token ~cpp.bool is defined in the default implementation, but the other tokens are defined according to their definitions on the target machine in the normal API library building mechanism.

3.2. Integer literal types

The type of an integer literal is defined in terms of the first in a list of possible integral types. The first type in which the literal value can be represented gives the type of the literal. For small literals it is possible to work out the type exactly, however for larger literals the result is target dependent. For example, the literal 50000 will have type int on machines in which 50000 fits into an int, and long otherwise. This target dependent mapping is given by a series of tokens of the form:

~lit_* : ( SIGNED_NAT ) -> SIGNED_NAT

which map a literal value to the representation of an integral type. The token used depends on the list of possible types, which in turn depends on the base used to represent the literal and the integer suffix used, as given in the following table:

Thus, for example, the shape of the integer literal 50000 is:

~convert ( ~lit_int ( 50000 ) )

3.3. Bitfield types

The sign of a plain bitfield type, declared without using signed or unsigned, is left unspecified in C and C++. The token:

~cpp.bitf_sign : ( SIGNED_NAT ) -> BOOL

is used to give a mapping from integral types to the sign of a plain bitfield of that type, in a form suitable for use in the TDF bfvar_bits construct. (Note that ~cpp.bitf_sign should have been a standard C token but was omitted.)

4.1. Generic pointers

TDF has no concept of a generic pointer type, so tokens are used to defer the representation of void * and the basic operations on it to the target machine. The fundamental token is:

~ptr_void : () -> SHAPE

which gives the representation of void *. This shape will be denoted by pv in the description of the following tokens. It is not guaranteed that pv is a TDF pointer shape, although normally it will be implemented as a pointer to a suitable alignment.

The token:

~null_pv : () -> EXP pv

gives the value of a null pointer of type void *. Generic pointers can also be converted to and from other pointers. These conversions are represented by the tokens:

~to_ptr_void : ( ALIGNMENT a, EXP POINTER a ) -> EXP pv
~from_ptr_void : ( ALIGNMENT a, EXP pv ) -> EXP POINTER a

where the given alignment describes the destination or source pointer type. Finally a generic pointer may be tested against the null pointer or two generic pointers may be compared. These operations are represented by the tokens:

~cpp.pv_compare : ( EXP pv, EXP pv, LABEL, NTEST ) -> EXP TOP

where the given NTEST gives the comparison to be applied and the given label gives the destination to jump to if the test fails. (Note that ~cpp.pv_compare should have been a standard C token but was omitted.)

4.2. Pointers to data members

The representation of, and operations on, pointers to data members are represented by tokens to allow for a variety of implementations. It is assumed that all pointers to data members (as opposed to pointers to function members) are represented by the same shape:

~cpp.pm.type : () -> SHAPE

This shape will be denoted by pm in the description of the following tokens.

There are two basic methods of constructing a pointer to a data member. The first is to take the address of a data member of a class. A data member is represented in TDF by an expression which gives the offset of the member from the start of its enclosing compound shape (note that it is not possible to take the address of a member of a virtual base). The mapping from this offset to a pointer to a data member is given by:

~cpp.pm.make : ( EXP OFFSET ) -> EXP pm

The second way of constructing a pointer to a data member is to use a null pointer to member:

~cpp.pm.null : () -> EXP pm

The other fundamental operation on a pointer to data member is to turn it back into an offset expression which can be added to a pointer to a class to access a member of that class in a .* or ->* operation. This is done by the token:

~cpp.pm.offset : ( EXP pm, ALIGNMENT a ) -> EXP OFFSET ( a, a )

Note that it is necessary to specify an alignment in order to describe the shape of the result. The value of this token is undefined if the given expression is a null pointer to data member.

A pointer to a data member of a non-virtual base class can be converted to a pointer to a data member of a derived class. The reverse conversion is also possible using static_cast. If the base is a primary base class then these conversions are trivial and have no effect. Otherwise null pointers to data members are converted to null pointers to data members, and the non-null cases are handled by the tokens:

~cpp.pm.cast : ( EXP pm, EXP OFFSET ) -> EXP pm
~cpp.pm.uncast : ( EXP pm, EXP OFFSET ) -> EXP pm

where the given offset is the offset of the base class within the derived class. It is also possible to convert between any two pointers to data members using reinterpret_cast. This conversion is implied by the equality of representation between any two pointers to data members and has no effect.

The only remaining operations on pointer to data members are to test one against the null pointer to data member and to compare two pointer to data members. These are represented by the tokens:

~cpp.pm.test : ( EXP pm, LABEL, NTEST ) -> EXP TOP
~cpp.pm.compare : ( EXP pm, EXP pm, LABEL, NTEST ) -> EXP TOP

where the given NTEST gives the comparison to be applied and the given label gives the destination to jump to if the test fails.

In the default implementation, pointers to data members are implemented as int. The null pointer to member is represented by 0 and the address of a class member is represented by 1 plus the offset of the member (in bytes). Casting to and from a derived class then correspond to adding or subtracting the base class offset (in bytes), and pointer to member comparisons correspond to integer comparisons.

4.3. Pointers to function members

As with pointers to data members, pointers to function members and the operations on them are represented by tokens to allow for a range of implementations. All pointers to function members are represented by the same shape:

~cpp.pmf.type : () -> SHAPE

This shape will be denoted by pmf in the description of the following tokens. Many of the tokens take an expression which has a shape which is a pointer to the alignment of pmf. This will be denoted by ppmf.

There are two basic methods for constructing a pointer to a function member. The first is to take the address of a non-static member function of a class. There are two cases, depending on whether or not the member function is virtual. The non-virtual case is given by the token:

~cpp.pmf.make : ( EXP PROC, EXP OFFSET, EXP OFFSET ) -> EXP pmf

where the first argument is the address of the corresponding function, the second argument gives any base class offset which is to be added when calling this function (to deal with inherited member functions), and the third argument is a zero offset.

For virtual functions, a pointer to function member of the form above is entered in the virtual function table for the corresponding class. The actual pointer to the virtual function member then gives a reference into the virtual function table as follows:

~cpp.pmf.vmake : ( SIGNED_NAT, EXP OFFSET, EXP, EXP ) -> EXP pmf

where the first argument gives the index of the function within the virtual function table, the second argument gives the offset of the vptr field within the class, and the third and fourth arguments are zero offsets.

The second way of constructing a pointer to a function member is to use a null pointer to function member:

~cpp.pmf.null : () -> EXP pmf
~cpp.pmf.null2 : () -> EXP pmf

For technical reasons there are two versions of this token, although they have the same value. The first token is used in static initialisers; the second token is used in other expressions.

The cast operations on pointers to function members are more complex than those on pointers to data members. The value to be cast is copied into a temporary and one of the tokens:

~cpp.pmf.cast : ( EXP ppmf, EXP OFFSET, EXP, EXP OFFSET ) -> EXP TOP
~cpp.pmf.uncast : ( EXP ppmf, EXP OFFSET, EXP, EXP OFFSET ) -> EXP TOP

is applied to modify the value of the temporary according to the given cast. The first argument gives the address of the temporary, the second gives the base class offset to be added or subtracted, the third gives the number to be added or subtracted to convert virtual function indexes for the base class into virtual function indexes for the derived class, and the fourth gives the offset of the vptr field within the class. Again, the ability to use reinterpret_cast to convert between any two pointer to function member types arises because of the uniform representation of these types.

As with pointers to data members, there are tokens implementing comparisons on pointers to function members:

~cpp.pmf.test : ( EXP ppmf, LABEL, NTEST ) -> EXP TOP
~cpp.pmf.compare : ( EXP ppmf, EXP ppmf, LABEL, NTEST ) -> EXP TOP

Note however that the arguments are passed by reference.

The most important, and most complex, operation is calling a function through a pointer to function member. The first step is to copy the pointer to function member into a temporary. The token:

~cpp.pmf.virt : ( EXP ppmf, EXP, ALIGNMENT ) -> EXP TOP

is then applied to the temporary to convert a pointer to a virtual function member to a normal pointer to function member by looking it up in the corresponding virtual function table. The first argument gives the address of the temporary, the second gives the object to which the function is to be applied, and the third gives the alignment of the corresponding class. Now the base class conversion to be applied to the object can be determined by applying the token:

~cpp.pmf.delta : ( ALIGNMENT a, EXP ppmf ) -> EXP OFFSET ( a, a )

to the temporary to find the offset to be added. Finally the function to be called can be extracted from the temporary using the token:

~cpp.pmf.func : ( EXP ppmf ) -> EXP PROC

The function call then procedes as normal.

The default implementation is that described in the ARM, where each pointer to function member is represented in the form:

struct PTR_MEM_FUNC {
    short delta ;
    short index ;
    union {
	void ( *func ) () ;
	short off ;
    } u ;
} ;

The delta field gives the base class offset (in bytes) to be added before applying the function. The index field is 0 for null pointers, -1 for non-virtual function pointers and the index into the virtual function table for virtual function pointers (as described below these indexes start from 1). For non-virtual function pointers the function itself is given by the u.func field. For virtual function pointers the offset of the vptr field within the class is given by the u.off field.

5.1. Member functions

Non-static member functions are implemented in the obvious fashion, by passing a pointer to the object the method is being applied to as the first argument (or the second argument if the method has an extra argument for its return value).

5.2. Ellipsis functions

Calls to functions declared with ellipses are via the apply_proc TDF construct, with all the arguments being treated as non-variable. However the definition of such a function uses the make_proc construct with a variable parameter. This parameter can be referred to within the program using the ... expression. The type of this expression is given by the built-in token:

~__va_t : () -> SHAPE

The va_start macro declared in the <stdarg.h> header then describes how the variable parameter (expressed as ...) can be converted to an expression of type va_list suitable for use in the va_arg macro.

Note that the variable parameter is in effect only being used to determine where the first optional parameter is defined. The assumption is that all such parameters are located contiguously on the stack, however the fact that calls to such functions do not use the variable parameter mechanism means that this is not automatically the case. Strictly speaking this means that the implementation of ellipsis functions uses undefined behaviour in TDF, however given the non-type-safe function calling rules in C this is unavoidable and installers need to make provision for such calls (by dumping any parameters from registers to the stack if necessary). Given the theoretically type-safe nature of C++ it would be possible to avoid such undefined behaviour, but the need for C-compatible calling conventions prevents this.

6.1. Class layout

Consider a class with no base classes:

class A {
    // A's members
} ;

Each object of class A needs its own copy of the non-static data members of A and, for polymorphic types, a means of referencing the virtual function table and run-time type information for A. This is accomplished using a layout of the form:

where the A component consists of the non-static data members and vptr A is a pointer to the virtual function table for A. For non-polymorphic classes the vptr A field is omitted; otherwise space for vptr A needs to be allocated within the class and the pointer needs to be initialised in each constructor for A. The precise layout of the virtual function table and the run-time type information is given below.

Two alternative ways of laying out the non-static data members within the class are implemented. The first, which is default, gives them in the order in which they are declared in the class definition. The second lays out the public, the protected, and the private members in three distinct sections, the members within each section being given in the order in which they are declared. The latter can be enabled using the -jo command-line option.

The offset of each member within the class (including vptr A) can be calculated in terms of the offset of the previous member. The first member has offset zero. The offset of any other member is given by the offset of the previous member plus the size of the previous member, rounded up to the alignment of the current member. The overall size of the class is given by the offset of the last member plus the size of the last member, rounded up using the token:

~comp_off : ( EXP OFFSET ) -> EXP OFFSET

which allows for any target dependent padding at the end of the class. The shape of the class is then a compound shape with this offset.

Classes with no members need to be treated slightly differently. The shape of such a class is given by the token:

~cpp.empty.shape : () -> SHAPE

(recall that an empty class still has a nonzero size). The token:

~cpp.empty.offset : () -> EXP OFFSET

is used to represent the offset required for an empty class when it is used as a base class. This may be a zero offset.

Bitfield members provide a slight complication to the picture above. The offset of a bitfield is additionally padded using the token:

~pad : ( EXP OFFSET, SHAPE, SHAPE ) -> EXP OFFSET

where the two shapes give the type underlying the bitfield and the bitfield itself.

The layout of unions is similar to that of classes except that all members have zero offset, and the size of the union is the maximum of the sizes of its members, suitably padded. Of course unions cannot be polymorphic and cannot have base classes.

Pointers to incomplete classes are represented by means of the alignment:

~cpp.empty.align : () -> ALIGNMENT

This token is also used for the alignment of a complete class if that class is never used in the generated TDF in a manner which requires it to be complete. This can lead to savings on the size of the generated code by preventing the need to define all the member offset tokens in order to find the shape of the class.

6.2. Derived class layout

The description of the implementation of derived classes will be given in terms of the example class hierarchy given by:

class A {
    // A's members
} ;

class B : public A {
    // B's members
} ;

class C : public A {
    // C's members
} ;

class D : public B, public C {
    // D's members
} ;

or, as a directed acyclic graph:

class A {
// A's members
} ;

class B : virtual public A {
// B's members
} ;

class C : virtual public A {
// C's members
} ;

class D : public B, public C {
// D's members
} ;

6.3. Constructors and destructors

The implementation of constructors and destructors, whether explicitly or implicitly defined, is slightly more complex than that of other member functions. For example, the constructors need to set up the internal vptr and ptr fields mentioned above.

The order of initialisation in a constructor is as follows:

• The internal ptr fields giving the locations of the virtual base classes are initialised.

• The constructors for the virtual base classes are called.

• The constructors for the non-virtual direct base classes are called.

• The internal vptr fields giving the locations of the virtual function tables are initialised.

• The constructors for the members of the class are called.

• The main constructor body is executed.

To ensure that each virtual base is only initialised once, if a class has a virtual base class then all its constructors have an implicit extra parameter of type int. The first two steps above are then only applied if this flag is nonzero. In normal applications of the constructor this argument will be 1, however in base class initialisations such as those in the third and fourth steps above, it will be 0.

Note that similar steps to protect virtual base classes are not taken in an implicitly declared operator= function. The order of assignment in this case is as follows:

• The assignment operators for the direct base classes (both virtual and non-virtual) are called.

• The assignment operators for the members of the class are called.

• A reference to the object assigned to (i.e. *this) is returned.

The order of destruction in a destructor is essentially the reverse of the order of construction:

• The main destructor body is executed.

• The destructor for the members of the class are called.

• The internal vptr fields giving the locations of the virtual function tables are re-initialised.

• The destructors for the non-virtual direct base classes are called.

• The destructors for the virtual base classes are called.

• If necessary the space occupied by the object is deallocated.

All destructors have an extra parameter of type int. The virtual base classes are only destroyed if this flag is nonzero when and-ed with 2. The space occupied by the object is only deallocated if this flag is nonzero when and-ed with 1. This deallocation is equivalent to inserting:

delete this ;

in the destructor. The operator delete function is called via the destructor in this way in order to implement the pseudo-virtual nature of these deallocation functions. Thus for normal destructor calls the extra argument is 2, for base class destructor calls it is 0, and for calls arising from a delete expression it is 3.

The point at which the virtual function tables are initialised in the constructor, and the fact that they are re-initialised in the destructor, is to ensure that virtual functions called from base class initialisers are handled correctly (see ISO C++ 12.7).

A further complication arises from the need to destroy partially constructed objects if an exception is thrown in a constructor. A count is maintained of the number of base classes and members constructed within a constructor. If an exception is thrown then it is caught in the constructor, the constructed base classes and members are destroyed, and the exception is re-thrown. The count variable is used to determine which bases and members need to be destroyed.

6.4. Virtual function tables

The virtual functions in a polymorphic class are given in its virtual function table in the following order: firstly those virtual functions inherited from its direct base classes (which may be overridden in the derived class) followed by those first declared in the derived class in the order in which they are declared. Note that this can result in virtual functions inherited from virtual base classes appearing more than once. The virtual functions are numbered from 1 (this is slightly more convenient than numbering from 0 in the default implementation).

The virtual function table for this class has shape:

~cpp.vtab.type : ( NAT ) -> SHAPE

the argument being n + 1 where n is the number of virtual functions in the class (there is also a token:

~cpp.vtab.diag : () -> SHAPE

which is used in the diagnostic output for a generic virtual function table). The table is created using the token:

~cpp.vtab.make : ( EXP pti, EXP OFFSET, NAT, EXP NOF ) -> EXP vt

where the first expression gives the address of the run-time type information structure for the class, the second expression gives the offset of the vptr field within the class (i.e. voff), the integer constant is n + 1, and the final expression is a make_nof construct giving information on each of the n virtual functions.

The information given on each virtual function in this table has the form of a pointer to function member formed using the token:

~cpp.pmf.make : ( EXP PROC, EXP OFFSET, EXP OFFSET ) -> EXP pmf

as above, except that the third argument gives the offset of the base class in virtual function tables such as vtbl B::A. For pure virtual functions the function pointer in this token is given by:

~cpp.vtab.pure : () -> EXP PROC

In the default implementation this gives a function __TCPPLUS_pure which just calls abort.

To avoid duplicate copies of virtual function tables and run-time type information structures being created, the ARM algorithm is used. The virtual function table and run-time type information structure for a class are defined in the module containing the definition of the first non-inline, non-pure virtual function declared in that class. If such a function does not exist then duplicate copies are created in every module which requires them. In the former case the virtual function table will have an external tag name; in the latter case it will be an internal tag. This scheme can be overridden using the -jv command-line option, which causes local virtual function tables to be output for all classes.

Note that the discussion above applies to both simple virtual function tables, such as vtbl B above, and to those arising from base classes, such as vtbl B::A. We are now in a position to precisely determine when vtbl B::A is an initial segment of vtbl B and hence can be eliminated. Firstly, A must be the first direct base class of B and cannot be virtual. This is to ensure both that there are no virtual functions in vtbl B before those inherited from A, and that the corresponding base class conversion is trivial so that the pointers to function members of B comprising the virtual function table can be equally regarded as pointers to function members of A. The second requirement is that if a virtual function for A, f, is overridden in B then the return type for B::f cannot differ from the return type for A::f by a non-trivial conversion (recall that ISO C++ allows the return types to differ by a base class conversion). In the non-trivial conversion case the function entered in vtbl B::A needs to be, not B::f as in vtbl B, but a stub function which calls B::f and converts its return value to the return type of A::f.

The virtual function call mechanism is implemented using the token:

~cpp.vtab.func : ( EXP ppvt, SIGNED_NAT ) -> EXP ppmf

which has as its arguments a reference to the vptr field of the object the function is to be called for, and the number of the virtual function to be called. It returns a reference to the corresponding pointer to function member within the object's virtual function table. The function is then called by extracting the base class offset to be added, and the function to be called, from this reference using the tokens:

~cpp.pmf.delta : ( ALIGNMENT a, EXP ppmf ) -> EXP OFFSET ( a, a )
~cpp.pmf.func : ( EXP ppmf ) -> EXP PROC

described as part of the pointer to function member call mechanism above.

7.1. Try blocks

At the start of a try block a variable of shape:

~cpp.try.type : () -> SHAPE

is declared corresponding to the stack element for this block. This is then initialised using the token:

~cpp.try.begin : ( EXP ptb, EXP POINTER fa, EXP POINTER ca ) -> EXP TOP

where the first argument is a pointer to this variable, the second argument is the TDF current_env construct, and the third argument is the result of the TDF make_local_lv construct on the label which is used to mark the first handler associated with the block. Note that the last two arguments enable a TDF long_jump construct to be applied to transfer control to the first handler.

When control exits from a try block, whether by reaching the end of the block or jumping out of it, the block is removed from the stack using the token:

~cpp.try.end : ( EXP ptb ) -> EXP TOP

where the argument is a pointer to the try block variable.

7.2. Local variables

The technique used to add a local variable with a non-trivial destructor to the stack is similar to that used in the dynamic initialisation of global variables. A local variable of shape ~cpp.destr.type is declared at the start of the variable scope. This is initialised just after the constructor for the variable is called using the token:

~cpp.destr.local : ( EXP pd, EXP POINTER c, EXP PROC ) -> EXP TOP

where the first argument is a pointer to the variable being initialised, the second is a pointer to the local variable to be destroyed, and the third is the destructor to be called. At the end of the variable scope, just before its destructor is called, the token:

~cpp.destr.end : ( EXP pd ) -> EXP TOP

where the argument is a pointer to destructor variable, is called to remove the local variable destructor from the stack. Note that partially constructed objects are destroyed within their constructors (see §6.3) so that only completely constructed objects need to be considered.

In cases where the local variable may be conditionally initialised (for example a temporary variable in the second operand of a || operation) the local variable of shape ~cpp.destr.type is initialised to the value given by the token:

~cpp.destr.null : () -> EXP d

(normally it is left uninitialised). Before the destructor for this variable is called the value of the token:

~cpp.destr.ptr : ( EXP pd ) -> EXP POINTER c

is tested. If ~cpp.destr.local has been called for this variable then this token returns a pointer to the variable, otherwise it returns a null pointer. The token ~cpp.destr.end and the destructor are only called if this token indicates that the variable has been initialised.

7.3. Throwing an exception

When a throw expression with an argument is encountered a number of steps performed. Firstly, space is allocated to hold the exception value using the token:

~cpp.except.alloc : ( EXP VARIETY size_t ) -> EXP pv

the argument of which gives the size of the value. The space allocated is returned as an expression of type void *. Secondly, the exception value is copied into the space allocated, using a copy constructor if appropriate. Finally the exception is raised using the token:

~cpp.except.throw : ( EXP pv, EXP pti, EXP PROC ) -> EXP BOTTOM

The first argument gives the pointer to the exception value, returned by ~cpp.except.alloc, the second argument gives a pointer to the run-time type information for the exception type, and the third argument gives the destructor to be called to destroy the exception value (if any). This token sets the current exception to the given values and invokes the exception manager as above.

A throw expression without an argument results in a call to the token:

~cpp.except.rethrow : () -> EXP BOTTOM

which re-invokes the exception manager with the current exception. If there is no current exception then the implementation should call std::terminate.

7.4. Handling an exception

The exception manager proceeds to find an exception in the manner described above, unwinding the stack and calling destructors for local variables. When a try block is popped from the stack a TDF long_jump is applied to transfer control to its list of handlers. For each handler in turn it is checked whether the handler can catch the current exception. For ... handlers this is always true; for other handlers it is checked using the token:

~cpp.except.catch : ( EXP pti ) -> EXP VARIETY int

where the argument is a pointer to the run-time type information for the handler type. This token gives 1 if the exception is caught by this handler, and 0 otherwise. If the exception is not caught by the handler then the next handler is checked, until there are no more handlers associated with the try block. In this case control is passed back to the exception manager by re-throwing the current exception using ~cpp.except.rethrow.

If an exception is caught by a handler then a number of steps are performed. Firstly, if appropriate, the handler variable is initialised by copying the current exception value. A pointer to the current exception value can be obtained using the token:

~cpp.except.value : () -> EXP pv

Once this initialisation is complete the token:

~cpp.except.caught : () -> EXP TOP

is called to indicate that the exception has been caught. The handler body is then executed. When control exits from the handler, whether by reaching the end of the handler or by jumping out of it, the token:

~cpp.except.end : () -> EXP TOP

is called to indicate that the exception has been completed. Note that the implementation should call the destructor for the current exception and free the space allocated by ~cpp.except.alloc at this point. Execution then continues with the statement following the handler.

To conclude, the TDF generated for a try block and its associated list of handlers has the form:

variable (
    long_jump_access,
    stack_tag,
    make_value ( ~cpp.try.type ),
    conditional (
	handler_label,
	sequence (
	    ~cpp.try.begin (
		obtain_tag ( stack_tag ),
		current_env,
		make_local_lv ( handler_label ) ),
		try-block-body,
		~cpp.try.end ),
	    conditional (
		catch_label_1,
		sequence (
		    integer_test (
			not_equal,
			catch_label_1,
			~cpp.except.catch (
			    handler-1-typeid ) )
		    variable (
			handler_tag_1,
			handler-1-init (
			    ~cpp.except.value ),
			sequence (
			    ~cpp.except.caught,
			    handler-1-body ) )
		    ~cpp.except.end )
		conditional (
		    catch_label_2,
		    further-handlers,
		    ~cpp.except.rethrow ) ) ) )

Note that for a local variable to maintain its previous value when an exception is caught in this way it is necessary to declare it using the TDF long_jump_access construct. Any local variable which contains a try block in its scope is declared in this way.

To aid implementations in the writing of exception managers the following standard tokens are provided:

~cpp.ptr.code : () -> SHAPE POINTER ca
~cpp.ptr.frame : () -> SHAPE POINTER fa
~cpp.except.jump : ( EXP POINTER fa, EXP POINTER ca ) -> EXP BOTTOM

These give the shape of the TDF make_local_lv construct, the shape of the TDF current_env construct, and direct access to the TDF long_jump access. The exception manager in the default implementation is a function called __TCPPLUS_throw.

7.5. Exception specifications

If a function is declared with an exception specification then extra code needs to be generated in the function definition to catch any unexpected exceptions thrown by the function and to call std::unexpected . Since this is a potentially high overhead for small functions, this extra code is not generated if it can be proved that such unexpected exceptions can never be thrown (the analysis is essentially the same as that in the exception analysis check; see tdfc2pragma).

The implementation of exception specification is to enclose the entire function definition in a try block. The handler for this block uses ~cpp.except.catch to check whether the current exception can be caught by any of the types listed in the exception specification. If so the current exception is re-thrown. If none of these types catch the current exception then the token:

~cpp.except.bad : ( SIGNED_NAT ) -> EXP TOP

is called. The argument is 1 if the exception specification includes the special type std::bad_exception, and 0 otherwise. The implementation should call std::unexpected, but how any exceptions thrown during this call are to be handled depends on the value of the argument.

8.1. Defining run-time type information structures

For built-in types, the run-time type information structure may be referenced by the token:

~cpp.typeid.basic : ( SIGNED_NAT ) -> EXP pti

where the argument gives the encoding of the type as given in the following table:

Note that the encoding for the basic integral types is the same as that given above. The other types are assigned to unused values. Note that the encodings for ptrdiff_t and size_t are not used, instead that for their implementation is used (using the standard tokens ptrdiff_t and size_t). The encodings for bool and wchar_t are used because they are conceptually distinct types even though they are implemented as one of the basic integral types. The type labelled ... is the dummy used in the representation of ellipsis functions. The default implementation uses an array of type information structures, __TCPPLUS_typeid, to implement ~cpp.typeid.basic.

The run-time type information structures for classes are defined in the same place as their virtual function tables. Other run-time type information structures are defined in whatever modules require them. In the former case the type information structure will have an external tag name; in the latter case it will be an internal tag.

8.2. Accessing run-time type information

The primary means of accessing the run-time type information for an object is using the typeid construct. In cases where the operand type can be determined statically, the address of the corresponding type information structure is returned. In other cases the token:

~cpp.typeid.ref : ( EXP ppvt ) -> EXP pti

is used, where the argument gives a reference to the vptr field of the object being checked. From this information it is trivial to trace the corresponding type information.

Another means of querying the run-time type information for an object is using the dynamic_cast construct. When the result cannot be determined statically, this is implemented using the token:

~cpp.dynam.cast : ( EXP ppvt, EXP pti ) -> EXP pv

where the first expression gives a reference to the vptr field of the object being cast and the second gives the run-time type information for the type being cast to. In the default implementation this token is implemented by the procedure __TCPPLUS_dynamic_cast. The key point to note is that the virtual function table contains the offset, voff, of the vptr field from the start of the most complete object. Thus it is possible to find the address of the most complete object. The run-time type information contains enough information to determine whether this object has a sub-object of the type being cast to, and if so, how to find the address of this sub-object. The result is returned as a void *, with the null pointer indicating that the conversion is not possible.

9.1. Mangling identifier names

Simple identifier names are mapped to themselves. Unicode characters of the forms \uxxxx and \Uxxxxxxxx are mapped to __kxxxx and __Kxxxxxxxx respectively, where the hex digits are output in their canonical lower-case form. Constructors are mapped to __ct and destructors to __dt. Conversions functions are mapped to __optype where type is the mangled form of the conversion type. Overloaded operator functions, operator@, are mapped as follows:

Note that this table contains a number of operators which are not part of C++ or cannot be overloaded in C++. These are used in the representation of target dependent integer constants.

9.2. Mangling namespace names

The global namespace is mapped to an empty string. Simple namespace and class names are mapped as above, but are preceded by a series of decimal digits giving the length of the mangled name. Nested namespaces and classes are represented by a sequence of such namespace names, preceded by the number of elements in the sequence. This takes the form Qdigit if there are less than 10 elements, or Q_digits_ if there are more than 10. Note that members of anonymous classes or namespaces are local to their translation unit, and so do not have external tag names.

9.3. Mangling types

The mangling of types is essentially similar to that used in the tdfc2dump symbol table dump format. The type used in the mangled name for an identifier ignores the return type for a function and ignores the most significant bound for an array.

The built-in types are mapped in precisely the same way as in the symbol table dump. Class and enumeration types are mapped to their type names mangled in the same way as the namespace names above. The exception to this is that in a class member, the parent class is mapped to X.

The composite types are again mapped in a similar fashion to that in the dump file. For example, PCc represents const char *. The only difficult case concerns function parameter types where the ARM T and N encodings are used for duplicate parameter types. The function return type is included in the mangled form except for function identifier types. In the cases where the identifier is known always to represent a function (constructors, destructors etc.) the initial F indicating a function type is also omitted.

The types of template functions and classes are represented by the underlying template and the template arguments giving rise to the instance. Template classes are preceded by t; template functions are preceded by G rather than F. Type arguments are represented by Z followed by the type value; non-type arguments are represented by the argument type followed by the argument value. In the underlying type the template parameters are represented by m0, m1 etc. An alternative scheme, in which the mangled form of a template function includes the type of that instance, rather than the underlying template, can be enabled using the -j-f command-line option.

9.4. Other mangled names

The virtual function table for a class, when this is a variable with external linkage, is named __vt__type , where type is the mangled form of the class name. The virtual function table for a base class is named __vt__base where base is a sequence of mangled class names specifying the base class. The run-time type information structure for a type, when this is a variable with external linkage, is named __ti__type, where type is the mangled form of the type name.

9.5. Mangled name examples

The following gives some examples of the name mangling scheme:

class A {
    static int a ;               // a__1Ai
public :
    A () ;                       // __ct__1A
    A ( int ) ;                  // __ct__1Ai
    A ( const A & ) ;            // __ct__1ARCX
    virtual ~A () ;              // __dt__1A
    operator bool () ;           // __opb__1A
    bool operator! () ;          // __nt__1A
} ;

// virtual function table        __vt__1A
// run-time type information     __ti__1A

int f ( A *, int, A * ) ;        // f__FP1AiT1
int b = 2 ;                      // b__i
int c [3] ;                      // c__A_i

namespace N {
    int *p = 0 ;                 // p__1NPi
}

10.1. Parsing C++

The parser used in the C++ producer is generated using the sid tool. Because of the large size of the generated code (1.3MB), sid is instructed to split its output into a number of more manageable modules.

sid is designed as a parser for grammars which can be transformed into LL(1) grammars. The distinguishing feature of these grammars is that the parser can always decide what to do next based on the current terminal. This is not the case in C++; in some circumstances a potentially unlimited look-ahead is required to distinguish, for example, declaration statements from expression statements. In the technical phrase, C++ is an LL(k) grammar. Fortunately there are relatively few such situations, and sid provides a mechanism, predicates, for bypassing the normal parsing mechanism in these cases. Thus it is possible, although difficult, to express C++ as a sid grammar.

The sid grammar file, syntax.sid, is closely based on the ISO C++ grammar. In particular, the same production names have been used. The grammar has been extended slightly to allow common syntactic errors to be detected elegantly. Other parsing errors are handled by sid's exception mechanism. At present there is only limited recovery after such errors.

The lexical analysis routines in the C++ producer are hand-crafted, based on an initial version generated by the simple lexical analyser generator, lexi. lexi has been used more directly to generate the lexical analysers for certain of the other automatic code generating tools, including calculus, used in the producer.

The sid grammar contains a number of entry points. The most important is parse_file, which is used to parse a complete C++ translation unit. The syntax for the tdfc2pragma #pragma TenDRA directives is included within the same grammar with two entry points, parse_tendra in normal use, and parse_preproc for use in preprocessing mode. There are also entry points in the grammar for each of the kinds of token argument. The parsing routines for token and template arguments are largely hand-crafted, based on these primitives.

Certain parsing operations are performed before control passes to the sid grammar. As mentioned above, these include the processing of token and template applications. The other important case concerns nested name specifiers. For example, in:

class A {
    class B {
    static int c ;
    } ;
} ;

int A::B::c = 0 ;

the qualified identifier A::B::c is split into two terminals, a nested name specifier, A::B::, and an identifier, c, which is looked up in the corresponding namespace. Note that it is at this stage that name look-up occurs. An identifier can be mapped to one of a number of terminals, including keywords, type names, namespace names and other identifiers, according to the result of this look-up. If the look-up gives a macro then this is expanded at this stage.

10.2. Undefined conversions

Several conversions in C and C++ can only be represented by undefined TDF. For example, converting a pointer to an integer can only be represented in TDF by forming a union of the pointer and integer shapes, putting the pointer into the union and pulling the integer out. Such conversions are tokenised. Undefined conversions not mentioned below may be performed by combining those given with the standard, well-defined, conversions.

The token:

~ptr_to_ptr : ( ALIGNMENT a, ALIGNMENT b, EXP POINTER a ) -> EXP POINTER b

is used to convert between two incompatible pointer types. The first alignment describes the source pointer shape while the second describes the destination pointer shape. Note that if the destination alignment is greater than the source alignment then the source pointer can be used in most TDF constructs in place of the destination pointer, so the use of ~ptr_to_ptr can be omitted (the exception is pointer_test which requires equal alignments). Base class pointer conversions are examples of these well-behaved, alignment preserving conversions.

The tokens:

~f_to_pv : ( EXP PROC ) -> EXP pv
~pv_to_f : ( EXP pv ) -> EXP PROC

are used to convert pointers to functions to and from void * (these conversions are not allowed in ISO C/C++ but are in older dialects).

The tokens:

~i_to_p : ( VARIETY v, ALIGNMENT a, EXP INTEGER v ) -> EXP POINTER a
~p_to_i : ( ALIGNMENT a, VARIETY v, EXP POINTER a ) -> EXP INTEGER v
~i_to_pv : ( VARIETY v, EXP INTEGER v ) -> EXP pv
~pv_to_i : ( VARIETY v, EXP pv ) -> EXP INTEGER v

are used to convert integers to and from void * and other pointers.

10.3. Integer division

The precise form of the integer division and remainder operations in C and C++ is left unspecified with respect to the sign of the result if either operand is negative. The tokens:

~div : ( EXP INTEGER v, EXP INTEGER v ) -> EXP INTEGER v
~rem : ( EXP INTEGER v, EXP INTEGER v ) -> EXP INTEGER v

are used to represent integer division and remainder. They will map onto one of the pairs of TDF constructs, div0 and rem0, div1 and rem1 or div2 and rem2.

10.4. Dynamic initialisation

The dynamic initialisation of variables with static storage duration in C++ is implemented by means of the TDF initial_value construct. However in order for the producer to maintain control over the order of initialisation, rather than each variable being initialised separately using initial_value, a single expression is created which initialises all the variables in a module, and this initialiser expression is used to initialise a single dummy variable using initial_value. Note that, while this enables the variables within a single module to be initialised in the order in which they are defined, the order of initialisation between different modules is unspecified.

The implementation needs to keep a list of those variables with static storage duration which have been initialised so that it can call the destructors for these objects at the end of the program. This is done by declaring a variable of shape:

~cpp.destr.type : () -> SHAPE

for each such object with a non-trivial destructor. Each element of an array is considered a distinct object. Immediately after the variable has been initialised the token:

~cpp.destr.global : ( EXP pd, EXP POINTER c, EXP PROC ) -> EXP TOP

is called to add the variable to the list of objects to be destroyed. The first argument is the address of the dummy variable just declared, the second is the address of the object to be destroyed, and the third is the destructor to be used. In this way a list giving the objects to be destroyed, and the order in which to destroy them, is built up. Note that partially constructed objects are destroyed within their constructors (see §6.3) so that only completely constructed objects need to be considered.

The implementation also needs to ensure that it calls the destructors in this list at the end of the program, including calls of exit. This is done by calling the token:

~cpp.destr.init : () -> EXP TOP

at the start of each initial_value construct. In the default implementation this uses atexit to register a function, __TCPPLUS_term, which calls the destructors. To aid alternative implementations the token:

~cpp.start : () -> EXP TOP

is called at the start of the main function, however this has no effect in the default implementation.

10.5. The std namespace

Several classes declared in the std namespace arise naturally as part of the C++ language specification. These are as follows:

The definitions of these classes are found, when needed, by looking up the appropriate class name in the std namespace. Depending on the context, an error may be reported if the class is not found. It is possible to modify the namespace which is searched for these classes using the directive:

#pragma TenDRA++ set std namespace : scope-name

where scope-name can be an identifier giving a namespace name or ::, indicating the global namespace.

10.6. Error catalogue

This section describes the error catalogue which lies at the heart of the C++ producer's error reporting routines. The full error catalogue syntax is documented under make_err A typical entry in the catalogue is as follows:

class_union_deriv ( CLASS_TYPE: ct )
{
    USAGE:              serious
    PROPERTIES:         ansi
    KEY (ISO)           "9.5"
    KEY (STANDARD)      "The union '"ct"' can't have base classes"
}

This defines an error, class_union_deriv, which takes a single parameter ct of type CLASS_TYPE. The severity of this error is serious; that is to say, a constraint error. The error property ansi indicates that the error arises from the ISO C++ standard, the associated ISO key indicating section 9.5. Finally the text to be printed for this error, including a reference to ct, is given. Looking up section 9.5 in the ISO C++ standard reveals the corresponding constraint in paragraph 1:

A union shall not have base classes.

Each constraint within the ISO C++ standard has a corresponding error in this way. The errors are named in a systematic fashion using the section names used in the draft standard. For example, section 9.5 is called class.union, so all the constraint errors arising from this section have names of the form class_union_*. These error names can be used in the tdfc2pragma low level directives such as:

#pragma TenDRA++ error "class_union_deriv" allow

to modify the error severity. The effect of reducing the severity of a constraint error in this way is undefined.

In addition to the obvious error severity levels, serious, warning and none, the error catalogue specifies a list of optional severity levels along with their default values. For example, the entry:

link_incompat = serious

sets up an option named link_incompat which is a constraint error by default. Errors with this severity, such as:

dcl_stc_external ( LONG_ID: id, PTR_LOC: loc )
{
    USAGE:              link_incompat
    PROPERTIES:         ansi
    KEY (ISO)           "7.1.1"
    KEY (STANDARD)      "'"id"' previously declared with external
             linkage (at "loc")"
}

are therefore constraint errors. The severity associated with link_incompat can be modified either directly, using the directive:

#pragma TenDRA++ option "link_incompat" allow

or indirectly using the directive:

#pragma TenDRA incompatible linkage allow

the effect being to modify the severity of the associated error messages.

The error catalogue is processed by a simple tool, make_err, which generates C code which is compiled into the C++ producer. Each error in the catalogue is assigned a number (there are currently 873 errors in the catalogue) which gives an index into an automatically generated table of error information. It is this error number, together with a list of error arguments, which forms the associated ERROR object. make_err generates a macro for each error in the catalogue which takes arguments of the appropriate types (which may be statically checked) and creates an ERROR object. For example, for the entry above this macro takes the form:

ERROR ERR_class_union_deriv ( CLASS_TYPE ) ;

These macros hide the error catalogue numbers from the rest of the C++ producer.

It is also possible to join a number of simple ERROR objects to form a single composite ERROR. The severity of the composite error is the maximum of the severities of the component errors. To this purpose a dummy error severity level whatever is introduced which is less severe than any other level. This is intended for use with error messages which are only ever used to add information to existing errors, and which inherit their severity level from the main error.

The text of a simple error message can be found in the table of error information. The text contains certain escape sequences indicating where the error arguments are to be printed. For example, %1 indicates the second argument. The error argument sorts - what is referred to as the error signature - is also stored in the table of error information as an array of characters, each corresponding to an ERR_KEY_type macro. The producer defines printing routines for each of the types given by these values, and calls the appropriate routine to print the argument.

There are several command-line options which can be used to modify the form in which the error message is printed. The default format is as follows:

"file.C", line 42: Error: [ISO 9.5]: The union 'U' can't have base classes.

The ISO section number can be suppressed using -m-s. The -mc option causes the source code line giving rise to the error to be printed as part of the message, with !!!! marking the position of the error within the line. The -me option causes the error name, class_union_deriv, to be printed as part of the message. The -ml option causes the full file location, including the list of #include directives used in reaching the file, to be printed. The -mt option causes typedef names to be used when printing types, rather than expanding to the type definition.