This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[RFC] type safe trees


Hi,
I've been thinking more about type safe trees.  At the summit Zack & I
showed y'all a two level hierarchy implemented with macros.  (The
slides are at http://www.codesourcery.com/publications.html.)

We talked about language dependent derivations and such like, plus
how much of this could be automatically generated.  Some responses
from the floor were along the lines of 'can we use C++?'

Whilst avoiding the C++ route, I've come to the conclusion that a
two level scheme is too restrictive.  And anything more than two
levels would be a maintainance nightmare, unless it was automatically
generated.

Why do we need more than two levels? Consider a DECL hierarchy. We
need to represent, in approximately increasing complexity
unnamed decls (maybe as an expression adaptor, maybe for constants)
variables - adds a name
parameters - adds a pass-as type?
functions - adds a function body
methods - adds a class context
thunks (in C++ land) - adds a target method

Ok, this hierarchy is not strictly linear, but that's not the point.
The point is that one will have routines that want to deal with
named_decls, and not care whether it's a variable, parameter, function or
whatever.  With the simple two level scheme we'd have had to make all
these types sibling classes, whereas we really want to make them a hierarchy.

So, we want a hierarchy and we don't know apriori how many levels there
will be. Cfront-lite here we come :)

I've been playing with a syntax that would allow gengtype to do the
automatic generation of C.  We'd use this syntax to replace the stuff in
tree.def and replace the structures in tree.h etc.  Here's what I've come
up with,

	#ifndef GTY
	/* define the root expression node */
	class expr ('e')
	{
	  static char klass; // in C++ speak this would be a virtual member *variable*
	
	  unsigned char code; // must have this, it's the vtable equivalent
	  type_t type;
	};
	#else
	#include "expr_t.h"
	#endif

gengtype would produce that expr_t.h file, and it'd look something like,
	typedef struct expr_t
	{
	  ... whatever
	} *expr_t;
	// omitting the static/dynamic type checking for clarity
	#define EXPR_CODE(expr_t) whatever
	#define EXPR_KLASS(expr_t) expr_table[EXPR_CODE(expr_t)].klass
	#define EXPR_TYPE(expr_t) (expr_t)->type
	// enum of all expr codes
	enum expr_codes
	{
	  EXPR,
	  ...
	  DYADIC_EXPR, // see later
	  ...
	  PLUS_EXPR, // see later
	  ...
	};
In this case the KLASS of such an expression node would be 'e'. To extend it,
you'd do something like,
	#ifndef GTY
	class dyadic_expr ('2'): expr
	{
	  expr_t ops[2];
	};
	#else
	#include "dyadic_expr_t.h"
	#endif
and that'd declare a new structure and acessor macro for the ops array. It
also overrides the static klass value with '2'.  We'll also allocate a new
code for this structure, so we can recognise it in the class hierarchy.

To define an actual PLUS_EXPR node, we do not need to define a new structure,
but map a new tree code onto an existing structure.  Here's the syntax for that
	#ifndef GTY
	class plus_expr = dyadic_expr;
	#else
	#include "plus_expr_t.h"
	#endif
and to override the klass value, you'd say
	class gt_expr ('<') = dyadic_expr;

This system will allow language frontends to declare new tree nodes which
are first-class citizens.

A remaining question is how languages add new fields to common nodes - for
instance C++'s addition of class information to a RECORD_TYPE?  If we decide
that such additional fields can only be added to the most-derived type, it is
straight forward -- add some syntax to say 'this class extends that class but
keeps the same tree code' and this ensures that the correct information is
stored in the slot of whatever table holds the information about all the
types.  On the other hand, if we want to allow languages to add
information to bases too, it's going to be much harder --- can we not go there?

comments?

nathan

--
Nathan Sidwell    ::   http://www.codesourcery.com   ::     CodeSourcery LLC
nathan@codesourcery.com    ::     http://www.planetfall.pwp.blueyonder.co.uk



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]