Syntactic order of CXXBaseOrMemberInitializers

As currently the initializers are reordered to match member order in
record declaration there is no easy way for an AST consumer to know in
which order the initializers were written in the source file.

I'd suggest to insert an index field to each CXXBaseOrMemberInitializer
that is 1 for the first initializer, 2 for the second and so no. The
index is 0 for the initializers that are not present in source file.

Can we proceed in this direction?

As currently the initializers are reordered to match member order in
record declaration there is no easy way for an AST consumer to know in
which order the initializers were written in the source file.

Originally, I had imagined that we would compare based on source locations, and perhaps add an "implicit" bit for implicitly-generated initializers. Does that not work?

I'd suggest to insert an index field to each CXXBaseOrMemberInitializer
that is 1 for the first initializer, 2 for the second and so no. The
index is 0 for the initializers that are not present in source file.

Can we proceed in this direction?

I would like to avoid adding an index field, if the source locations suffice.

If comparing based on source locations works then we don't need an implicit bit - the source location for implicit initializers is always invalid.

- Anders

Sent from my iPhone

As currently the initializers are reordered to match member order in
record declaration there is no easy way for an AST consumer to know in
which order the initializers were written in the source file.

Originally, I had imagined that we would compare based on source locations, and perhaps add an "implicit" bit for implicitly-generated initializers. Does that not work?

We thought the same, but the fact that a sorting algorithm lead to a
worst case of O(n*log(n)) or O(n*2) calls to non trivial source location
comparison has worried us.

I'd suggest to insert an index field to each CXXBaseOrMemberInitializer
that is 1 for the first initializer, 2 for the second and so no. The
index is 0 for the initializers that are not present in source file.

Can we proceed in this direction?

I would like to avoid adding an index field, if the source locations suffice.

To tell you the truth we had considered that the smaller complexity
would pay the space cost.

However it's not a problem, should you accept a patch for adding

CXXConstructorDecl::getBaseOrMemberInitializersAsWritten()?

Sent from my iPhone

As currently the initializers are reordered to match member order in
record declaration there is no easy way for an AST consumer to know in
which order the initializers were written in the source file.

Originally, I had imagined that we would compare based on source locations, and perhaps add an "implicit" bit for implicitly-generated initializers. Does that not work?

We thought the same, but the fact that a sorting algorithm lead to a
worst case of O(n*log(n)) or O(n*2) calls to non trivial source location
comparison has worried us.

It seems highly unlikely that N will grow large enough for this to ever matter, since N should only include explicitly-written base classes.

I'd suggest to insert an index field to each CXXBaseOrMemberInitializer
that is 1 for the first initializer, 2 for the second and so no. The
index is 0 for the initializers that are not present in source file.

Can we proceed in this direction?

I would like to avoid adding an index field, if the source locations suffice.

To tell you the truth we had considered that the smaller complexity
would pay the space cost.

However it's not a problem, should you accept a patch for adding

CXXConstructorDecl::getBaseOrMemberInitializersAsWritten()?

Sure!

  - Doug

Several years ago, I reported a performance problem with Metrowerks compiler.
I was defining several hundred traits classes; and the compiler would keep the machine (a PowerPC) pegged for about 90 seconds compiling that file.

I sent this to the Metrowerks folks, and rather sheepishly got a response a couple of days later:
  "Oops. That was an N^2 loop. Try this new version; it's an log(N) version"

and the file compiled in about three seconds with the new compiler.

My (uninformed) opinion is to try to avoid the N^2 algorithm; because users write the damndest code. :wink:

-- Marshall

Hrm. I was thinking "base classes" rather than "base or member initializers."

Anyway, please go ahead with your original proposal to add an index field into CXXBaseOrMemberInitializer. We can do some shuffling to keep the structure the same size while still adding this field.

  - Doug

I've attached the patch for review/approval.

CXXBaseOrMemberInitializerOrder.patch (3.22 KB)

Looks good. You could probably pack NumArrayIndices and SourceOrder into one 32-bit word to save storage.

Also, would you like to update the AST printer to print the base and member initializers in order, now that the information is easier to get to?

  - Doug

Sent from my iPhone

As currently the initializers are reordered to match member order in
record declaration there is no easy way for an AST consumer to know in
which order the initializers were written in the source file.

Originally, I had imagined that we would compare based on source locations, and perhaps add an "implicit" bit for implicitly-generated initializers. Does that not work?

We thought the same, but the fact that a sorting algorithm lead to a
worst case of O(n*log(n)) or O(n*2) calls to non trivial source location
comparison has worried us.

It seems highly unlikely that N will grow large enough for this to ever matter, since N should only include explicitly-written base classes.

Hrm. I was thinking "base classes" rather than "base or member initializers."

Anyway, please go ahead with your original proposal to add an index field into CXXBaseOrMemberInitializer. We can do some shuffling to keep the structure the same size while still adding this field.

I've attached the patch for review/approval.
<CXXBaseOrMemberInitializerOrder.patch>

Looks good. You could probably pack NumArrayIndices and SourceOrder into one 32-bit word to save storage.

What about to have:

bool isImplicit:1;
unsigned NumArrayIndicesOrSourceOrder:15;

?

Also, would you like to update the AST printer to print the base and member initializers in order, now that the information is easier to get to?

I'm not confident with this area and however it's questionable what to
do there: we could print also implicit initializer (often the AST
printer print implicit things), we could print it in source order or in
execution order, etc.

Ping

Sent from my iPhone

As currently the initializers are reordered to match member order in

record declaration there is no easy way for an AST consumer to know in

which order the initializers were written in the source file.

Originally, I had imagined that we would compare based on source locations, and perhaps add an “implicit” bit for implicitly-generated initializers. Does that not work?

We thought the same, but the fact that a sorting algorithm lead to a

worst case of O(nlog(n)) or O(n2) calls to non trivial source location

comparison has worried us.

It seems highly unlikely that N will grow large enough for this to ever matter, since N should only include explicitly-written base classes.

Hrm. I was thinking “base classes” rather than “base or member initializers.”

Anyway, please go ahead with your original proposal to add an index field into CXXBaseOrMemberInitializer. We can do some shuffling to keep the structure the same size while still adding this field.

I’ve attached the patch for review/approval.

<CXXBaseOrMemberInitializerOrder.patch>

Looks good. You could probably pack NumArrayIndices and SourceOrder into one 32-bit word to save storage.

What about to have:

bool isImplicit:1;
unsigned NumArrayIndicesOrSourceOrder:15;

?

Yes, that’s good.

Also, would you like to update the AST printer to print the base and member initializers in order, now that the information is easier to get to?

I’m not confident with this area and however it’s questionable what to
do there: we could print also implicit initializer (often the AST
printer print implicit things), we could print it in source order or in
execution order, etc.

I like having the AST printer print the AST as we parsed it (without the implicit parts) to reflect our understanding of the source code. The AST dumper, on the other hand, should include the implicit nodes in its output.

  • Doug