[AST] Make the last element in the linked list null

[void]

Summary

The last element in a linked list should point to null, so that we can
identify when the linked list ends.

[urnathan]

Huh? this web interface is confusing. How did this ever work -- doesn't the decl's ctor set this to null?

[erichkeane]

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?
2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

[void]

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

[void]

In D121063#3364780, @void wrote:

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

After looking at the randstruct code again, it's possible that it's not doing the correct thing. (#include "MildShockMeme.h"!) The Decls already have a their pointers set, but then we shuffle them and all Hell breaks loose when we call that function because the end is pointing back to somewhere within the structure beginning. This patch is probably not a bad idea in general, but if you want me to I can fix it on my end.

[erichkeane]

In D121063#3364810, @void wrote:

In D121063#3364780, @void wrote:

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

After looking at the randstruct code again, it's possible that it's not doing the correct thing. (#include "MildShockMeme.h"!) The Decls already have a their pointers set, but then we shuffle them and all Hell breaks loose when we call that function because the end is pointing back to somewhere within the structure beginning. This patch is probably not a bad idea in general, but if you want me to I can fix it on my end.

Ah! Shuffling declarations in a chain is not likely to do 'good things', I'm surprised that this is the first issue we've seen!. I presume that there needs to be a 'RebuildDeclChain' for the purposes of 'RandStruct' that first nulls-out the next-in-context-and-bits.

Alternatively, perhaps "RandStruct" should be 'randomizing' on the first call to this BuildDeclChain function.

[void]

In D121063#3364815, @erichkeane wrote:

In D121063#3364810, @void wrote:

In D121063#3364780, @void wrote:

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

After looking at the randstruct code again, it's possible that it's not doing the correct thing. (#include "MildShockMeme.h"!) The Decls already have a their pointers set, but then we shuffle them and all Hell breaks loose when we call that function because the end is pointing back to somewhere within the structure beginning. This patch is probably not a bad idea in general, but if you want me to I can fix it on my end.

Ah! Shuffling declarations in a chain is not likely to do 'good things', I'm surprised that this is the first issue we've seen!.

Same :-)

I presume that there needs to be a 'RebuildDeclChain' for the purposes of 'RandStruct' that first nulls-out the next-in-context-and-bits.

Without this patch, then yes. It might actually be a better idea to have it in the DeclContext anyway just in case someone else wants to use it.

Alternatively, perhaps "RandStruct" should be 'randomizing' on the first call to this BuildDeclChain function.

I assume that BuildDeclChain is called once (and only once) per Record? Will randomizing when calling BuildDeclChain mess up the ABI somehow? Or is it safer to do it here because the ABI is decided afterwards?

[erichkeane]

In D121063#3364833, @void wrote:

In D121063#3364815, @erichkeane wrote:

In D121063#3364810, @void wrote:

In D121063#3364780, @void wrote:

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

After looking at the randstruct code again, it's possible that it's not doing the correct thing. (#include "MildShockMeme.h"!) The Decls already have a their pointers set, but then we shuffle them and all Hell breaks loose when we call that function because the end is pointing back to somewhere within the structure beginning. This patch is probably not a bad idea in general, but if you want me to I can fix it on my end.

Ah! Shuffling declarations in a chain is not likely to do 'good things', I'm surprised that this is the first issue we've seen!.

Same :-)

I presume that there needs to be a 'RebuildDeclChain' for the purposes of 'RandStruct' that first nulls-out the next-in-context-and-bits.

Without this patch, then yes. It might actually be a better idea to have it in the DeclContext anyway just in case someone else wants to use it.

Alternatively, perhaps "RandStruct" should be 'randomizing' on the first call to this BuildDeclChain function.

I assume that BuildDeclChain is called once (and only once) per Record? Will randomizing when calling BuildDeclChain mess up the ABI somehow? Or is it safer to do it here because the ABI is decided afterwards?

Interestingly, the ONLY call I see to this is via calls of LoadLexicalDeclsFromExternalStorage and RecordDecl::LoadFieldsFromexternalStorage. I suspect that the purpose of this is only for restoring the declaration list after loading a module of some sort. I see this is the origin of the record-fields one: https://github.com/llvm/llvm-project/commit/0e88a565c0978bb6fd835a33e8069135661a1400 which seems to be most of this function as well.

So I don't have a good idea actually of when this would happen. It does NOT seem like something that happens during normal compilation I would expect though.

[void]

In D121063#3364872, @erichkeane wrote:

In D121063#3364833, @void wrote:

In D121063#3364815, @erichkeane wrote:

In D121063#3364810, @void wrote:

In D121063#3364780, @void wrote:

In D121063#3363852, @erichkeane wrote:

I suspect this works because we never really treated this as a LL, just as a pair of iterators. Two things:

1- Can you produce some situation where this is valuable to do?

Yes. In the randstruct feature I'm working on, if this code isn't there it goes into an infinite loop: https://reviews.llvm.org/D120857. It's possible that the way it's constructing and using the list of Decls is somehow wrong, but I wasn't able to identify how.

2- Can you switch this over so that the NextInContextAndBits initializes to nullptr/0 so that this line isn't necessary? I can't imagine we ever re-call this on a decl and have the answer be different.

I'll give it a shot. I'm with @urnathan though that it should have already been like that. :-) Probably just an oversight.

After looking at the randstruct code again, it's possible that it's not doing the correct thing. (#include "MildShockMeme.h"!) The Decls already have a their pointers set, but then we shuffle them and all Hell breaks loose when we call that function because the end is pointing back to somewhere within the structure beginning. This patch is probably not a bad idea in general, but if you want me to I can fix it on my end.

Ah! Shuffling declarations in a chain is not likely to do 'good things', I'm surprised that this is the first issue we've seen!.

Same :-)

I presume that there needs to be a 'RebuildDeclChain' for the purposes of 'RandStruct' that first nulls-out the next-in-context-and-bits.

Without this patch, then yes. It might actually be a better idea to have it in the DeclContext anyway just in case someone else wants to use it.

Alternatively, perhaps "RandStruct" should be 'randomizing' on the first call to this BuildDeclChain function.

I assume that BuildDeclChain is called once (and only once) per Record? Will randomizing when calling BuildDeclChain mess up the ABI somehow? Or is it safer to do it here because the ABI is decided afterwards?

Interestingly, the ONLY call I see to this is via calls of LoadLexicalDeclsFromExternalStorage and RecordDecl::LoadFieldsFromexternalStorage. I suspect that the purpose of this is only for restoring the declaration list after loading a module of some sort. I see this is the origin of the record-fields one: https://github.com/llvm/llvm-project/commit/0e88a565c0978bb6fd835a33e8069135661a1400 which seems to be most of this function as well.

So I don't have a good idea actually of when this would happen. It does NOT seem like something that happens during normal compilation I would expect though.

I reworked the rand struct code to no longer need this change. I'm going to abandon this change, since it doesn't appear to be necessary.

clang/lib/AST/DeclBase.cpp

for (auto *D : Decls) {
     if (PrevDecl)
       PrevDecl->NextInContextAndBits.setPointer(D);
     else
       FirstNewDecl = D;
 
     PrevDecl = D;
   }
 
+  if (PrevDecl)
+    // Last item in the linked list should have a null next pointer.
+    PrevDecl->NextInContextAndBits.setPointer(nullptr);
+
   return std::make_pair(FirstNewDecl, PrevDecl);
 }
 
 /// We have just acquired external visible storage, and we already have
 /// built a lookup map. For every name in the map, pull in the new names from
 /// the external storage.
 void DeclContext::reconcileExternalVisibleStorage() const {
   assert(hasNeedToReconcileExternalVisibleStorage() && LookupPtr);