c-tree.texi

GCC

@c Copyright (c) 1999, 2000, 2001 Free Software Foundation, Inc.
@c Free Software Foundation, Inc.
@c This is part of the GCC manual.
@c For copying conditions, see the file gcc.texi.

@c ---------------------------------------------------------------------
@c Trees
@c ---------------------------------------------------------------------

@node Trees
@chapter Trees: The intermediate representation used by the C and C++ front-ends
@cindex Trees
@cindex C/C++ Internal Representation

This chapter documents the internal representation used by GCC and C++ to
represent C and C++ source programs.  When presented with a C or C++
source program, GCC parses the program, performs semantic analysis
(including the generation of error messages), and then produces the
internal representation described here.  This representation contains a
complete representation for the entire translation unit provided as
input to the front-end.  This representation is then typically processed
by a code-generator in order to produce machine code, but could also be
used in the creation of source browsers, intelligent editors, automatic
documentation generators, interpreters, and any other programs needing
the ability to process C or C++ code.

This chapter explains the internal representation.  In particular, it
documents the internal representation for C and C++ source
constructs, and the macros, functions, and variables that can be used to
access these constructs.  The C++ representation which is largely a superset
of the representation used in the C front-end.  There is only one
construct used in C that does not appear in the C++ front-end and that
is the GNU ``nested function'' extension.  Many of the macros documented
here do not apply in C because the corresponding language constructs do
not appear in C.

If you are developing a ``back-end'', be it is a code-generator or some
other tool, that uses this representation, you may occasionally find
that you need to ask questions not easily answered by the functions and
macros available here.  If that situation occurs, it is quite likely
that GCC already supports the functionality you desire, but that the
interface is simply not documented here.  In that case, you should ask
the GCC maintainers (via mail to @email{gcc@@gcc.gnu.org}) about
documenting the functionality you require.  Similarly, if you find
yourself writing functions that do not deal directly with your back-end,
but instead might be useful to other people using the GCC front-end, you
should submit your patches for inclusion in GCC.

@menu
* Deficiencies::        Topics net yet covered in this document.
* Tree overview::       All about @code{tree}s.
* Types::               Fundamental and aggregate types.
* Scopes::              Namespaces and classes.
* Functions::           Overloading, function bodies, and linkage.
* Declarations::        Type declarations and variables.
* Expression trees::    From @code{typeid} to @code{throw}.
@end menu

@c ---------------------------------------------------------------------
@c Deficiencies
@c ---------------------------------------------------------------------

@node Deficiencies
@section Deficiencies

There are many places in which this document is incomplet and incorrekt.
It is, as of yet, only @emph{preliminary} documentation.

@c ---------------------------------------------------------------------
@c Overview
@c ---------------------------------------------------------------------

@node Tree overview
@section Overview
@cindex tree
@findex TREE_CODE

The central data structure used by the internal representation is the
@code{tree}.  These nodes, while all of the C type @code{tree}, are of
many varieties.  A @code{tree} is a pointer type, but the object to
which it points may be of a variety of types.  From this point forward,
we will refer to trees in ordinary type, rather than in @code{this
font}, except when talking about the actual C type @code{tree}.

You can tell what kind of node a particular tree is by using the
@code{TREE_CODE} macro.  Many, many macros take a trees as input and
return trees as output.  However, most macros require a certain kinds of
tree node as input.  In other words, there is a type-system for trees,
but it is not reflected in the C type-system.

For safety, it is useful to configure G++ with @option{--enable-checking}.
Although this results in a significant performance penalty (since all
tree types are checked at run-time), and is therefore inappropriate in a
release version, it is extremely helpful during the development process.

Many macros behave as predicates.  Many, although not all, of these
predicates end in @samp{_P}.  Do not rely on the result type of these
macros being of any particular type.  You may, however, rely on the fact
that the type can be compared to @code{0}, so that statements like
@example
if (TEST_P (t) && !TEST_P (y))
  x = 1;
@end example
@noindent
and
@example
int i = (TEST_P (t) != 0);
@end example
@noindent
are legal.  Macros that return @code{int} values now may be changed to
return @code{tree} values, or other pointers in the future.  Even those
that continue to return @code{int} may return multiple non-zero codes
where previously they returned only zero and one.  Therefore, you should
not write code like
@example
if (TEST_P (t) == 1)
@end example
@noindent
as this code is not guaranteed to work correctly in the future.

You should not take the address of values returned by the macros or
functions described here.  In particular, no guarantee is given that the
values are lvalues.

In general, the names of macros are all in uppercase, while the names of
functions are entirely in lower case.  There are rare exceptions to this
rule.  You should assume that any macro or function whose name is made
up entirely of uppercase letters may evaluate its arguments more than
once.  You may assume that a macro or function whose name is made up
entirely of lowercase letters will evaluate its arguments only once.

The @code{error_mark_node} is a special tree.  Its tree code is
@code{ERROR_MARK}, but since there is only ever one node with that code,
the usual practice is to compare the tree against
@code{error_mark_node}.  (This test is just a test for pointer
equality.)  If an error has occurred during front-end processing the
flag @code{errorcount} will be set.  If the front-end has encountered
code it cannot handle, it will issue a message to the user and set
@code{sorrycount}.  When these flags are set, any macro or function
which normally returns a tree of a particular kind may instead return
the @code{error_mark_node}.  Thus, if you intend to do any processing of
erroneous code, you must be prepared to deal with the
@code{error_mark_node}.

Occasionally, a particular tree slot (like an operand to an expression,
or a particular field in a declaration) will be referred to as
``reserved for the back-end.''  These slots are used to store RTL when
the tree is converted to RTL for use by the GCC back-end.  However, if
that process is not taking place (e.g., if the front-end is being hooked
up to an intelligent editor), then those slots may be used by the
back-end presently in use.

If you encounter situations that do not match this documentation, such
as tree nodes of types not mentioned here, or macros documented to
return entities of a particular kind that instead return entities of
some different kind, you have found a bug, either in the front-end or in
the documentation.  Please report these bugs as you would any other
bug.

@menu
* Macros and Functions::Macros and functions that can be used with all trees.
* Identifiers::         The names of things.
* Containers::          Lists and vectors.
@end menu

@c ---------------------------------------------------------------------
@c Trees
@c ---------------------------------------------------------------------

@node Macros and Functions
@subsection Trees
@cindex tree

This section is not here yet.

@c ---------------------------------------------------------------------
@c Identifiers
@c ---------------------------------------------------------------------

@node Identifiers
@subsection Identifiers
@cindex identifier
@cindex name
@tindex IDENTIFIER_NODE

An @code{IDENTIFIER_NODE} represents a slightly more general concept
that the standard C or C++ concept of identifier.  In particular, an
@code{IDENTIFIER_NODE} may contain a @samp{$}, or other extraordinary
characters.

There are never two distinct @code{IDENTIFIER_NODE}s representing the
same identifier.  Therefore, you may use pointer equality to compare
@code{IDENTIFIER_NODE}s, rather than using a routine like @code{strcmp}.

You can use the following macros to access identifiers:
@ftable @code
@item IDENTIFIER_POINTER
The string represented by the identifier, represented as a
@code{char*}.  This string is always @code{NUL}-terminated, and contains
no embedded @code{NUL} characters.

@item IDENTIFIER_LENGTH
The length of the string returned by @code{IDENTIFIER_POINTER}, not
including the trailing @code{NUL}.  This value of
@code{IDENTIFIER_LENGTH (x)} is always the same as @code{strlen
(IDENTIFIER_POINTER (x))}.

@item IDENTIFIER_OPNAME_P
This predicate holds if the identifier represents the name of an
overloaded operator.  In this case, you should not depend on the
contents of either the @code{IDENTIFIER_POINTER} or the
@code{IDENTIFIER_LENGTH}.

@item IDENTIFIER_TYPENAME_P
This predicate holds if the identifier represents the name of a
user-defined conversion operator.  In this case, the @code{TREE_TYPE} of
the @code{IDENTIFIER_NODE} holds the type to which the conversion
operator converts.

@end ftable

@c ---------------------------------------------------------------------
@c Containers
@c ---------------------------------------------------------------------

@node Containers
@subsection Containers
@cindex container
@cindex list
@cindex vector
@tindex TREE_LIST
@tindex TREE_VEC
@findex TREE_PURPOSE
@findex TREE_VALUE
@findex TREE_VEC_LENGTH
@findex TREE_VEC_ELT

Two common container data structures can be represented directly with
tree nodes.  A @code{TREE_LIST} is a singly linked list containing two
trees per node.  These are the @code{TREE_PURPOSE} and @code{TREE_VALUE}
of each node.  (Often, the @code{TREE_PURPOSE} contains some kind of
tag, or additional information, while the @code{TREE_VALUE} contains the
majority of the payload.  In other cases, the @code{TREE_PURPOSE} is
simply @code{NULL_TREE}, while in still others both the
@code{TREE_PURPOSE} and @code{TREE_VALUE} are of equal stature.)  Given
one @code{TREE_LIST} node, the next node is found by following the
@code{TREE_CHAIN}.  If the @code{TREE_CHAIN} is @code{NULL_TREE}, then
you have reached the end of the list.

A @code{TREE_VEC} is a simple vector.  The @code{TREE_VEC_LENGTH} is an
integer (not a tree) giving the number of nodes in the vector.  The
nodes themselves are accessed using the @code{TREE_VEC_ELT} macro, which
takes two arguments.  The first is the @code{TREE_VEC} in question; the
second is an integer indicating which element in the vector is desired.
The elements are indexed from zero.

@c ---------------------------------------------------------------------
@c Types
@c ---------------------------------------------------------------------

@node Types
@section Types
@cindex type
@cindex pointer
@cindex reference
@cindex fundamental type
@cindex array
@tindex VOID_TYPE
@tindex INTEGER_TYPE
@tindex TYPE_MIN_VALUE
@tindex TYPE_MAX_VALUE
@tindex REAL_TYPE
@tindex COMPLEX_TYPE
@tindex ENUMERAL_TYPE
@tindex BOOLEAN_TYPE
@tindex POINTER_TYPE
@tindex REFERENCE_TYPE
@tindex FUNCTION_TYPE
@tindex METHOD_TYPE
@tindex ARRAY_TYPE
@tindex RECORD_TYPE
@tindex UNION_TYPE
@tindex UNKNOWN_TYPE
@tindex OFFSET_TYPE
@tindex TYPENAME_TYPE
@tindex TYPEOF_TYPE
@findex CP_TYPE_QUALS
@findex TYPE_UNQUALIFIED
@findex TYPE_QUAL_CONST
@findex TYPE_QUAL_VOLATILE
@findex TYPE_QUAL_RESTRICT
@findex TYPE_MAIN_VARIANT
@cindex qualified type
@findex TYPE_SIZE
@findex TYPE_ALIGN
@findex TYPE_PRECISION
@findex TYPE_ARG_TYPES
@findex TYPE_METHOD_BASETYPE
@findex TYPE_PTRMEM_P
@findex TYPE_OFFSET_BASETYPE
@findex TREE_TYPE
@findex TYPE_CONTEXT
@findex TYPE_NAME
@findex TYPENAME_TYPE_FULLNAME
@findex TYPE_FIELDS
@findex TYPE_PTROBV_P

All types have corresponding tree nodes.  However, you should not assume
that there is exactly one tree node corresponding to each type.  There
are often several nodes each of which correspond to the same type.

For the most part, different kinds of types have different tree codes.
(For example, pointer types use a @code{POINTER_TYPE} code while arrays
use an @code{ARRAY_TYPE} code.)  However, pointers to member functions
use the @code{RECORD_TYPE} code.  Therefore, when writing a
@code{switch} statement that depends on the code associated with a
particular type, you should take care to handle pointers to member
functions under the @code{RECORD_TYPE} case label.

In C++, an array type is not qualified; rather the type of the array
elements is qualified.  This situation is reflected in the intermediate
representation.  The macros described here will always examine the
qualification of the underlying element type when applied to an array