Normalizing the AST across languages

There are a few places in Clang where we build different AST nodes
depending on which language we are parsing. I believe we should seek
to eliminate those differences, so that clients only need to deal with
one AST node per kind of entity.

The most obvious example of what I'm talking about is the difference
between RecordDecl and CXXRecordDecl. RecordDecl is used when we're
parsing C, while CXXRecordDecl is used when we're parsing C++. Here's
the chunk of code from Sema::ActOnTag that handles the allocation:

    if (getLangOptions().CPlusPlus)
      // FIXME: Look for a way to use RecordDecl for simple structs.
      New = CXXRecordDecl::Create(Context, Kind, CurContext, Loc, Name);
    else
      New = RecordDecl::Create(Context, Kind, CurContext, Loc, Name);

The intent of CXXRecordDecl is clear: since C++ requires us to keep
additional information about classes in the AST (which isn't needed in
C), all that extra information goes into CXXRecordDecl so that we
don't bloat the C compilation with unused data. This means that
compiling a C program as C++ uses different ASTs and requires more
memory. I don't think that's a desirable outcome, for several reasons:

  (1) It's harder for AST clients to juggle two different kinds of AST
nodes that represent the same thing. (And it'll get really hard if we
start trying to deal with ASTs for multiple translation units, but
that's way off in the future)

  (2) We're not making the best use of our memory in C++: as the
comment above says, we really want to use the smaller RecordDecl for
simple classes in C++, but we don't know whether we'll have a simple
class or not until we've parsed it. So our approach to reducing memory
usage in C actually increases memory usage in C++. [*]

So, here is my suggestion: instead of making a distinction between
what the two languages support at the AST level, use a single AST node
(RecordDecl) that has a pointer to an optionally-allocated "extras"
data structure containing that extra information when we need to store
it. For RecordDecl, the "extras" structure should definitely have
information about C++ classes that isn't needed in C and isn't used by
the majority of C++ classes. For example, base classes, friends,
user-defined constructors/destructor/copy-assignment operators, and
user-defined conversion operators.

I've attached a patch that implements my suggestion. Unless I hear
screams of protest, I'll be committing it shortly. Essentially, it
moves the functionality of CXXRecordDecl into RecordDecl (eliminating
CXXRecord-everything from Clang), and puts the base class information
into RecordDeclExtras. With this change, structs in C take a little
bit more memory---since they are now a DeclContext---but simple
structs (= no base classes) in C++ take less memory. RecordDecl isn't
expected to get any bigger after this, but RecordDeclExtras will grow
as we implement support for more C++ features.

CXXFieldDecl is likely to get the same treatment, and I think we need
to decide whether CXXClassMemberWrapper adds more confusion than it
eliminates.

Comments?

  - Doug

remove-cxx-record-decl.patch (35 KB)

There are a few places in Clang where we build different AST nodes
depending on which language we are parsing. I believe we should seek
to eliminate those differences, so that clients only need to deal with
one AST node per kind of entity.

The most obvious example of what I'm talking about is the difference
between RecordDecl and CXXRecordDecl. RecordDecl is used when we're
parsing C, while CXXRecordDecl is used when we're parsing C++. Here's
the chunk of code from Sema::ActOnTag that handles the allocation:

   if (getLangOptions().CPlusPlus)
     // FIXME: Look for a way to use RecordDecl for simple structs.
     New = CXXRecordDecl::Create(Context, Kind, CurContext, Loc, Name);
   else
     New = RecordDecl::Create(Context, Kind, CurContext, Loc, Name);

The intent of CXXRecordDecl is clear: since C++ requires us to keep
additional information about classes in the AST (which isn't needed in
C), all that extra information goes into CXXRecordDecl so that we
don't bloat the C compilation with unused data. This means that
compiling a C program as C++ uses different ASTs and requires more
memory.

Right, this is something I asked Argiris to do. The intent was for "C like" struct definitions in C++ to use the lighter weight RecordDecl when possible (which is what the fixme is about).

I don't think that's a desirable outcome, for several reasons:

(1) It's harder for AST clients to juggle two different kinds of AST
nodes that represent the same thing. (And it'll get really hard if we
start trying to deal with ASTs for multiple translation units, but
that's way off in the future)

I'm not sure what you mean. Consider base classes. The intent here was for CXXRecordDecl to remain the same, but for RecordDecl to get something like this:

   unsigned getNumBases() const {
     if (const CXXRecordDecl *CXX = dyn_cast<CXXRecordDecl>(this))
       return CXX->getNumBases();
     return 0;
   }

This means that all *clients* should be able to use RecordDecl and never have to poke at CXXRecordDecl unless they want to. With this approach, CXXRecordDecl is just a hidden implementation detail.

(2) We're not making the best use of our memory in C++: as the
comment above says, we really want to use the smaller RecordDecl for
simple classes in C++, but we don't know whether we'll have a simple
class or not until we've parsed it. So our approach to reducing memory
usage in C actually increases memory usage in C++. [*]

This is true, and I don't know if there is an answer for things like "struct foo;" in C++. However, a common case for C++ is that code #includes a lot of C code, and if there is a full definition for the body, we could make it use RecordDecl.

So, here is my suggestion: instead of making a distinction between
what the two languages support at the AST level, use a single AST node
(RecordDecl) that has a pointer to an optionally-allocated "extras"
data structure containing that extra information when we need to store
it. For RecordDecl, the "extras" structure should definitely have
information about C++ classes that isn't needed in C and isn't used by
the majority of C++ classes. For example, base classes, friends,
user-defined constructors/destructor/copy-assignment operators, and
user-defined conversion operators.

That would also be ok I guess, if you don't think the approach outlined above will work.

I've attached a patch that implements my suggestion. Unless I hear
screams of protest, I'll be committing it shortly. Essentially, it
moves the functionality of CXXRecordDecl into RecordDecl (eliminating
CXXRecord-everything from Clang), and puts the base class information
into RecordDeclExtras. With this change, structs in C take a little
bit more memory---since they are now a DeclContext---but simple
structs (= no base classes) in C++ take less memory. RecordDecl isn't
expected to get any bigger after this, but RecordDeclExtras will grow
as we implement support for more C++ features.

Does the approach described above make any sense? I do think the CXXRecordDecl vs RecordDecl approach can work and be elegant :). Do you see a problem with it?

-Chris

Doug Gregor wrote:

So, here is my suggestion: instead of making a distinction between
what the two languages support at the AST level, use a single AST node
(RecordDecl) that has a pointer to an optionally-allocated "extras"
data structure containing that extra information when we need to store
it. For RecordDecl, the "extras" structure should definitely have
information about C++ classes that isn't needed in C and isn't used by
the majority of C++ classes. For example, base classes, friends,
user-defined constructors/destructor/copy-assignment operators, and
user-defined conversion operators.
  
It may be beneficial to "pull out" the 'members' fields from RecordDecl and put them into a RecordDefInfo, which is like the "extras" structure you mention with the purpose of
storing the info about the definition.
Currently there's a new RecordDecl created for each record reference and the 'Members' fields is wasted space for them.

After a class definition is parsed, we will know if it's a simple C-like struct or not, and we will create a RecordDefInfo or CXXRecordDefInfo accordingly (to add to RecordDecl).
RecordDefInfo will keep the instance members, while CXXRecordDefInfo will also keep the other C++ specific stuff (base classes, etc.).

-Argiris

There are a few places in Clang where we build different AST nodes
depending on which language we are parsing. I believe we should seek
to eliminate those differences, so that clients only need to deal with
one AST node per kind of entity.

The most obvious example of what I'm talking about is the difference
between RecordDecl and CXXRecordDecl. RecordDecl is used when we're
parsing C, while CXXRecordDecl is used when we're parsing C++. Here's
the chunk of code from Sema::ActOnTag that handles the allocation:

  if (getLangOptions().CPlusPlus)
    // FIXME: Look for a way to use RecordDecl for simple structs.
    New = CXXRecordDecl::Create(Context, Kind, CurContext, Loc, Name);
  else
    New = RecordDecl::Create(Context, Kind, CurContext, Loc, Name);

The intent of CXXRecordDecl is clear: since C++ requires us to keep
additional information about classes in the AST (which isn't needed in
C), all that extra information goes into CXXRecordDecl so that we
don't bloat the C compilation with unused data. This means that
compiling a C program as C++ uses different ASTs and requires more
memory.

Right, this is something I asked Argiris to do. The intent was for "C like"
struct definitions in C++ to use the lighter weight RecordDecl when possible
(which is what the fixme is about).

I don't see how it can work. The problem is that we need to allocate
the RecordDecl as soon as we see the "struct Blah". After we've done
that, we can't go back and make it into a CXXRecordDecl if we then
find out that it has friend declarations.

I don't think that's a desirable outcome, for several reasons:

(1) It's harder for AST clients to juggle two different kinds of AST
nodes that represent the same thing. (And it'll get really hard if we
start trying to deal with ASTs for multiple translation units, but
that's way off in the future)

I'm not sure what you mean. Consider base classes. The intent here was for
CXXRecordDecl to remain the same, but for RecordDecl to get something like
this:

unsigned getNumBases() const {
   if (const CXXRecordDecl *CXX = dyn_cast<CXXRecordDecl>(this))
     return CXX->getNumBases();
   return 0;
}

This means that all *clients* should be able to use RecordDecl and never
have to poke at CXXRecordDecl unless they want to. With this approach,
CXXRecordDecl is just a hidden implementation detail.

Ah, interesting. I did not realize that the intent was to make
CXXRecordDecl an implementation detail when I added the base-class
accessors into it. It would certainly make me happier if CXXRecordDecl
was fully an implementation detail, and didn't show up at all in Sema
except when we're calling CXXRecordDecl::Create.

Does the approach described above make any sense? I do think the
CXXRecordDecl vs RecordDecl approach can work and be elegant :). Do you see
a problem with it?

Let's see if the problem I mentioned above---that we can't go back and
turn a RecordDecl into a CXXRecordDecl if we find a friend function
inside the class definition---can be resolved. If it can, we can argue
the relative elegance of the solutions.

  - Doug

Are we going to be able to wait until the end of parsing before we
create the RecordDefInfo or CXXRecordDefInfo? It seems like that could
cause some pain with qualified name lookup, e.g.,

  class Foo {
    typedef int type;
    Foo::type member;
  };

Normally, I would think that name lookup for Foo::type would find the
RecordDecl that defines Foo and then go look for a "type" member
inside it. However, that doesn't work here, because at the point where
we need to lookup "Foo::type", there is no definition of Foo (yet),
since we're still parsing it.

To make this work, we would need to be able to do lookup into whatever
temporary data structures are used to store the fields of Foo before
it has been fully defined. That's certainly possible... and in the
template case, where we're looking up a "member of the current
instantiation", it might even be easier. Perhaps you and Chris are two
steps ahead of me... is this the direction in which CXXFieldCollector
was going?

  - Doug

Doug Gregor wrote:

Are we going to be able to wait until the end of parsing before we
create the RecordDefInfo or CXXRecordDefInfo? It seems like that could
cause some pain with qualified name lookup, e.g.,

  class Foo {
    typedef int type;
    Foo::type member;
  };

Normally, I would think that name lookup for Foo::type would find the
RecordDecl that defines Foo and then go look for a "type" member
inside it. However, that doesn't work here, because at the point where
we need to lookup "Foo::type", there is no definition of Foo (yet),
since we're still parsing it.
  
The way IdentifierResolver works, allows to put 'Foo' as the new DeclContext, insert into this new context the member declarations as we parse them and name lookup will find them.

But if there are base classes, we should probably create the CXXRecordDefInfo from the start, so that IdentifierResolver can see that the current DeclContext has base classes to look into.

To make this work, we would need to be able to do lookup into whatever
temporary data structures are used to store the fields of Foo before
it has been fully defined. That's certainly possible... and in the
template case, where we're looking up a "member of the current
instantiation", it might even be easier. Perhaps you and Chris are two
steps ahead of me... is this the direction in which CXXFieldCollector
was going?
  
The purpose of CXXFieldCollector wasn't for name lookup, but rather to collect the instance fields and call ActOnFields when parsing of the class definition is finished.
This takes a similar code-path to C's parsing of struct definitions and reuses the semantic checks done on ActOnFields.
For C, it's the parser that collects the fields and later passes them to ActOnFields, but it was not technically possible to have the parser collect the instance fields for C++ classes as well (I don't want to bore you with the details, but it boiled down to the parser not being able to distinguish when a member declaration is an instance field or not).

-Argiris

Doug Gregor wrote:

Are we going to be able to wait until the end of parsing before we
create the RecordDefInfo or CXXRecordDefInfo? It seems like that could
cause some pain with qualified name lookup, e.g.,

class Foo {
   typedef int type;
   Foo::type member;
};

Normally, I would think that name lookup for Foo::type would find the
RecordDecl that defines Foo and then go look for a "type" member
inside it. However, that doesn't work here, because at the point where
we need to lookup "Foo::type", there is no definition of Foo (yet),
since we're still parsing it.

The way IdentifierResolver works, allows to put 'Foo' as the new
DeclContext, insert into this new context the member declarations as we
parse them and name lookup will find them.

Okay, good. Now, I see that CXXFieldDecls are not ScopedDecls, but
that's something we'll need to change, right? For example:

  class C {
    int m;
    decltype(m) n;
  };

But if there are base classes, we should probably create the
CXXRecordDefInfo from the start, so that IdentifierResolver can see that the
current DeclContext has base classes to look into.

Sure.

To make this work, we would need to be able to do lookup into whatever
temporary data structures are used to store the fields of Foo before
it has been fully defined. That's certainly possible... and in the
template case, where we're looking up a "member of the current
instantiation", it might even be easier. Perhaps you and Chris are two
steps ahead of me... is this the direction in which CXXFieldCollector
was going?

The purpose of CXXFieldCollector wasn't for name lookup, but rather to
collect the instance fields and call ActOnFields when parsing of the class
definition is finished.
This takes a similar code-path to C's parsing of struct definitions and
reuses the semantic checks done on ActOnFields.
For C, it's the parser that collects the fields and later passes them to
ActOnFields, but it was not technically possible to have the parser collect
the instance fields for C++ classes as well (I don't want to bore you with
the details, but it boiled down to the parser not being able to distinguish
when a member declaration is an instance field or not).

So I assume that CXXFieldCollector will either be extended to support
other kinds of members (member types, member functions, etc.) or that
there will be similar collectors for those other kinds of members
(CXXMethodCollector, etc.)?

  - Doug

Doug Gregor wrote:

Okay, good. Now, I see that CXXFieldDecls are not ScopedDecls, but
that's something we'll need to change, right? For example:

  class C {
    int m;
    decltype(m) n;
  };
  
CXXFieldDecls don't have to be ScopedDecls, they already carry their parent DeclContext (the class they belong to)
and this is enough for name lookup to find them.

So I assume that CXXFieldCollector will either be extended to support
other kinds of members (member types, member functions, etc.) or that
there will be similar collectors for those other kinds of members
(CXXMethodCollector, etc.)?
  
The way I saw it, as far as the AST is concerned, the instance fields of C++ classes would be found in the 'members' array (like C structs),
and the other member declarations (nested types, methods, static data members, all are ScopedDecls) would be found through a declaration chain of their parent DeclContext (their class),
similar to how file scope declarations will be chained to the DeclContext of a namespace.

Do you think this is sufficient or should something like CXXRecordDefInfo allocate extra space to hold all the member declarations ?

-Argiris

Yep, this is a very good point. Perhaps Argiris' suggestion of making *all* instance variables be a separate allocation from the decl would help?

-Chris

Yeah, this I really like. It makes forward declarations relatively
cheap, and we can still keep C and simple C++ structs smaller than
full-fledged C++ structs.

  - Doug

Yeah, I think this is the best approach. By this point you have the full definition, and we have to do an allocation *anyway* to hold the field pointers. It should be straight-forward to make it "optionally" have the C++ fields or not. The only issue is that RecordDecl will unconditionally be a DeclContext, but this is probably a good thing for C anyway.

-Chris

It could certainly make things more uniform, because
RecordDecl::getMember can be replaced with a lookup into DeclContext.
Actually, maybe we just want all of the kinds of members to be
ScopedDecls stored within the DeclContext. That way there's only a
single lookup mechanism to implement (and optimize).

  - Doug

Doug Gregor wrote:

Okay, good. Now, I see that CXXFieldDecls are not ScopedDecls, but
that's something we'll need to change, right? For example:

class C {
   int m;
   decltype(m) n;
};

CXXFieldDecls don't have to be ScopedDecls, they already carry their parent
DeclContext (the class they belong to)
and this is enough for name lookup to find them.

Okay, I see that now. Thanks for putting up with me :slight_smile:

So I assume that CXXFieldCollector will either be extended to support
other kinds of members (member types, member functions, etc.) or that
there will be similar collectors for those other kinds of members
(CXXMethodCollector, etc.)?

The way I saw it, as far as the AST is concerned, the instance fields of C++
classes would be found in the 'members' array (like C structs),
and the other member declarations (nested types, methods, static data
members, all are ScopedDecls) would be found through a declaration chain of
their parent DeclContext (their class),
similar to how file scope declarations will be chained to the DeclContext of
a namespace.

Do you think this is sufficient or should something like CXXRecordDefInfo
allocate extra space to hold all the member declarations ?

I'm concerned that putting the instance fields into one place and the
rest of the members into another place will complicate name lookup.
For example,

struct C {
  enum type { };
  char type;
};

We've already taught the IdentifierResolver to deal with these cases
appropriately, but if the first and second "type" declarations end up
in different places in the AST, we'll end up doing two name lookups
for each name, one through members and one through

I'm really starting to like the idea of just making FieldDecls into
ScopedDecls, and having the DeclContext associated with RecordType
store all of the declarations for name lookup. Auxiliary information
not found through normal lookup (base classes, constructors, etc.)
could still go into a CXXRecordDefInfo, of course. Does that seem
feasible to you?

  - Doug

Doug Gregor wrote:

I'm concerned that putting the instance fields into one place and the
rest of the members into another place will complicate name lookup.
For example,

struct C {
  enum type { };
  char type;
};

We've already taught the IdentifierResolver to deal with these cases
appropriately, but if the first and second "type" declarations end up
in different places in the AST, we'll end up doing two name lookups
for each name, one through members and one through
  
The problem is not actually 2 name lookups of the same name; both the field and nested type in your example can be treated uniformly and can be found by just the IdentifierResolver.
This is because IdentifierResolver doesn't actually go through the DeclContext declaration chain but, rather, it maintains its own data structures for optimized lookup.

The problem is having to check first whether 'struct C' is a C-like struct or a C++ class, so that the right name lookup is performed, through the getMember or through the IdentifierResolver respectively.
It will certainly complicate things.

I'm really starting to like the idea of just making FieldDecls into
ScopedDecls, and having the DeclContext associated with RecordType
store all of the declarations for name lookup. Auxiliary information
not found through normal lookup (base classes, constructors, etc.)
could still go into a CXXRecordDefInfo, of course. Does that seem
feasible to you?
  
Well, I love the idea, but Chris will probably freak out when he sees the FieldDecls getting bigger :slight_smile:

-Argiris

Yep, he's like that ;-). That said, if it is a cleanup that makes the ASTs easier to manipulate and manage for C code also, I'd support doing it.

-Chris