Memory management for types in complex languages

I've come across a slight problem for writing memory management with regard to the internal representation of types in a compiler for statically typed, complex languages. Consider a simple snippet in C++ which easily demonstrates a type that refers to itself.

class X {
    void f(const X&) {}
};

Types can have nearly infinitely complex relationships to each other. So, as a compiler process, how do you make sure that they are properly collected?

So far, I've decided that garbage collection might be the right way to go, which I wouldn't be too happy with because I want to write the compiler in C++, or altern开发者_如何转开发atively, just leave them and never collect them for the life of the compile phase for which they are needed (which has a very fixed lifetime) and then collect them all afterwards. The problem with that is that if you had a lot of complex types, you could lose a lot of memory that way.

Memory management is easy, just have some table type-name -> type-descriptor for each declaration scopes. Types are uniquely identified by name, no matter how complex the nesting is. Even a recursive type is still only a single type. As tp1 says correctly, you typically perform multiple passes to fill in all blanks. For instance, you might check that a type name is known in the first pass and then compute all links, later on, you compute the type.

Keep in mind that languages like C don't have a really complex type system -- even though they have pointers (which allow for recursive types), there is not much type computation going on.

I think you can remove the cycles from the dependency graph by using separate objects to represent declarations and definitions. Assuming a type system similar to C++, you will then have a hierarchical dependency:

• Function definitions depend on type definitions and function declarations
• Type definitions depend on function and type declarations (and definitions of contained types)
• Function declarations depend on type declarations

In your example, the dependency graph is f_def -> X_def -> f_decl -> X_decl.

With no cycles in the graph, you can manage objects using simple reference counting.