This is an archive of the discontinued LLVM Phabricator instance.

[AST] Introduce GenericSelectionExpr::Association
ClosedPublic

Authored by riccibruno on Jan 23 2019, 10:04 AM.

Details

Summary

Introduce a new class GenericSelectionExpr::Association which bundle together
an association expression and its TypeSourceInfo.

An iterator GenericSelectionExpr::AssociationIterator is additionally added to make
it possible to iterate over ranges of Associations. This iterator is a kind of proxy
iterator which abstract how exactly the expressions and the TypeSourceInfos are stored.

Diff Detail

Repository
rL LLVM

Event Timeline

riccibruno created this revision.Jan 23 2019, 10:04 AM

Just in case you didn't know, you could have (and still can!) just update https://reviews.llvm.org/D57098 instead of creating a new PR.

steveire added inline comments.Jan 23 2019, 10:27 AM
lib/AST/ASTDumper.cpp
1465 ↗(On Diff #183122)

Range for loops in this file generally use auto.

riccibruno edited the summary of this revision. (Show Details)Jan 23 2019, 10:59 AM
aaron.ballman added inline comments.Jan 23 2019, 12:13 PM
include/clang/AST/Expr.h
5099 ↗(On Diff #183122)

Carrying over the conversation from D57098:

@aaron.ballman It seems like this should be pretty trivial to make into a random access iterator, or am I missing something?

@riccibruno Indeed, at the cost of some boilerplate. I can totally do this but from what I understood the motivation was to use this in ranges, and for this a forward iterator is good enough (although see the next comment)

You are correct, the primary motivation are range-based APIs. However, the iterator-based API should still behave in a reasonable manner and some algorithms do better with random access iterators than forward only. Even a bidirectional iterator would be preferred because I can at least use std::prev() on it.

5103 ↗(On Diff #183122)

Carrying over the conversation from D57098:

@aaron.ballman Cute, but I suspect this may come back to bite us at some point. For instance, if someone thinks they're working with a real pointer, they're likely to expect pointer arithmetic to work when it won't (at least they'll get compile errors though).

@riccibruno Hmm, but pointer is just the return type of operator-> no ? Is it actually required to behave like a pointer ? The only requirement I can find is that It->x must be equivalent to (*It).x, which is true here.

I double-checked and you're right, this is not a requirement of the STL.

Also looking at the requirements for forward iterators I think that this iterator should actually be downgraded to an input iterator, because of the requirement that reference = T&.

My concern is that with the less functional iterators, common algorithms get more expensive. For instance, std::distance(), std::advance() become more expensive without random access, and things like std::prev() become impossible.

It seems like the view this needs to provide is a read-only access to the AssociationTy objects (because we need to construct them on the fly), but not the data contained within them. If the only thing you can get back from the iterator is a const pointer/reference/value type, then we could store a local "current association" object in the iterator and return a pointer/reference to that. WDYT?

riccibruno marked an inline comment as done.Jan 24 2019, 6:13 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5103 ↗(On Diff #183122)

I am worried about lifetime issues with this approach. Returning a reference/pointer to an Association object stored in the iterator means that the reference/pointer will dangle as soon as the iterator goes out of scope. This is potentially surprising since the "container" (that is the GenericSelectionExpr) here will still be in scope. Returning a value is safer in this aspect.

I believe it should be possible to make the iterator a random access iterator, at least
if we are willing to ignore some requirements:

1.) For forward iterators and up, we must have reference = T& or const T&.
2.) For forward iterators and up, It1 == It2 if and only if *It1 and *It2 are bound to the same object.

Made GenericSelectionExpr::AssociationIterator a random access iterator.

aaron.ballman added subscribers: dblaikie, mclow.lists.

Adding some additional reviewers to help tease out the iterator design questions.

include/clang/AST/Expr.h
5103 ↗(On Diff #183122)

I am worried about lifetime issues with this approach. Returning a reference/pointer to an Association object stored in the iterator means that the reference/pointer will dangle as soon as the iterator goes out of scope. This is potentially surprising since the "container" (that is the GenericSelectionExpr) here will still be in scope. Returning a value is safer in this aspect.

That's valid.

I believe it should be possible to make the iterator a random access iterator, at least if we are willing to ignore some requirements:

1.) For forward iterators and up, we must have reference = T& or const T&.
2.) For forward iterators and up, It1 == It2 if and only if *It1 and *It2 are bound to the same object.

Yes, but then passing these iterators to STL algorithms will have UB because we claim to meet the requirements for random access iteration but don't actually meet the requirements. I am not certain what problems might arise from violating these requirements.

@dblaikie, @mclow.lists: do you have opinions on whether it's okay to not meet these requirements or suggestions on what we could do differently with the design?

Rebased on D57104. No other changes.

dblaikie added inline comments.Jan 24 2019, 2:46 PM
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

Worth using any of the iterator helpers LLVM has? (iterator_facade or the like)

5103 ↗(On Diff #183122)

My vote is usually "yeah, have a member inside the iterator you return a reference/pointer to" to meet the iterator requirements. Yes, it means if you keep a pointer/reference to it, that is invalidated when you increment the iterator. But that's well established in iterator semantics.

(might be shooting from the hip here/not fully understanding the nuances/tradeoffs in this case)

riccibruno marked 2 inline comments as done.Jan 25 2019, 5:46 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

I did try to use iteratore_facade but for some reason I was getting strange overload resolution failures with it.

In the end it did not save much and so I just rewrote the boiler-plate (especially given that if we end up going with an input iterator there is not going to be much boiler-plate).

5103 ↗(On Diff #183122)

I believe there are 3 possibilities here:

Option 1 : Make the iterator an input iterator, and make operator* return a value.
Pros : Safe, compliant with the spec.
Cons : Morally we can do all of the operations of a random iterator.

Option 2 : Make the iterator a random access iterator, and make operator* return a value.
Pros : Safe wrt lifetime issues.
Cons : Do not complies with the two requirement of forward iterators mentioned above.

Option 3 : Make the iterator a random access iterator, and make operator* return a
reference to an object stored inside the iterator.
Pros : Compliant with the spec.
Cons : Nasty lifetime issues (see below)

I believe that option 3 is problematic. An example:

AssociationIterator It = ...;
const Association &Assoc = *It++;
// oops, Assoc is dangling since It++ returns a value,
// which goes out of scope at the end of the full expression.
// The same problem do not exists when operator* returns a
// value since the lifetime of the returned Association will be
// extended when bound to the reference.

Probably the safe thing to do is to go with option 1.

aaron.ballman added inline comments.Jan 25 2019, 6:27 AM
include/clang/AST/Expr.h
5103 ↗(On Diff #183122)

Probably the safe thing to do is to go with option 1.

In the interests of solving the problem at hand, I think we should go with the safest option and can put a FIXME near the iterator_category that explains why it's an input iterator and that we'd like it to have stronger guarantees someday. It should meet our needs for the AST dumping refactoring; we can solve the harder problems if/when they arise in practice.

lib/AST/ASTDumper.cpp
1465 ↗(On Diff #183352)

I believe const auto & should be safe here even with the call to dumpChild() because the lambda captures Assoc by copy (even if the iterator does not return a reference, the value will be lifetime extended because of the const reference). Same applies elsewhere.

riccibruno marked 10 inline comments as done.

Moved back to an input iterator. Addressed Aaron's remaining comments.

riccibruno edited the summary of this revision. (Show Details)Jan 25 2019, 8:38 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5103 ↗(On Diff #183122)

Let's do this. I tried to summarize how we ended up with an input iterator.

lib/AST/ASTDumper.cpp
1465 ↗(On Diff #183352)

Yes it is safe. Done.

aaron.ballman added inline comments.Jan 25 2019, 10:50 AM
include/clang/AST/Expr.h
5100 ↗(On Diff #183552)

Note -> FIXME

iterator. -> iterator, and it would be nice if we could strengthen the iterator category someday.

5101 ↗(On Diff #183552)

do not -> does not

5084 ↗(On Diff #183352)

Does using the iterator_facade_base help now that we're back to an input iterator? It seems like that should be able to get rid of some of the boilerplate.

riccibruno marked 3 inline comments as done.Jan 25 2019, 2:13 PM
riccibruno added inline comments.
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

I must be holding it wrong; for some reason the post-fix operator ++ is not getting found when I use iterator_facade_base. It also forces me to define operator== as a member instead of a non-member function. Do you mind terribly if I don't use it ? It only at best avoid me to write operator!= and operator++(int).

Update the comment in the iterator as per Aaron's comments.

aaron.ballman added inline comments.Jan 26 2019, 9:59 AM
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

It also removes all of the typedefs and operator->(), so it does remove quite a bit of boilerplate. You shouldn't have to do anything special to get it to locate the postfix operator++ though (so long as you use public inheritance), which makes me wonder what's going on for your use. I would like to understand more about why this base class doesn't work here when it seems to work fine for the other uses in the code base.

riccibruno marked an inline comment as done.Jan 26 2019, 10:31 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

Right. Let me try again then. I will still have to provide operator-> though since the implementation from iterator_facade_base is not adequate as far as I can tell.

aaron.ballman added inline comments.Jan 26 2019, 12:21 PM
include/clang/AST/Expr.h
5084 ↗(On Diff #183352)

Yeah, I think you're right about operator->(); because of the odd semantics of the Association object, the facade implementation won't work there because it would return a pointer to a temporary.

Use iterator_facade_base. It didn't work the first time because I forgot to bring in the name operator++ from iterator_facade_base into AssociationIteratorTy. Since name lookup occurs before overload resolution and stops as soon as something is found, the postfix operator++ from iterator_facade_base was hidden by the prefix operator++ from AssociationIteratorTy.

riccibruno marked 3 inline comments as done.Jan 27 2019, 4:52 AM

Removed duplicated comment in AssociationIteratorTy

aaron.ballman accepted this revision.Jan 28 2019, 5:08 AM

LGTM aside from some possible minor nits. Thank you for working on this!

include/clang/AST/Expr.h
5122 ↗(On Diff #183755)

Can this continue to return reference instead of the concrete type? (Same in the cast expression.)

5126 ↗(On Diff #183755)

Can this return pointer instead?

5254 ↗(On Diff #183755)

If you like being explicit, you could use llvm::make_range() here, but I don't insist. Same below.

This revision is now accepted and ready to land.Jan 28 2019, 5:08 AM
riccibruno marked 3 inline comments as done.Jan 28 2019, 5:32 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5122 ↗(On Diff #183755)

Not literally reference since the base is dependent, but typename BaseTy::reference should work. Is that what you mean ?

5254 ↗(On Diff #183755)

I have no special preference on this, so llvm::make_range() it is.

aaron.ballman added inline comments.Jan 28 2019, 5:40 AM
include/clang/AST/Expr.h
5122 ↗(On Diff #183755)

Yes, that's what I meant, sorry. :-)

riccibruno marked 5 inline comments as done.Jan 28 2019, 5:44 AM
riccibruno added inline comments.
include/clang/AST/Expr.h
5122 ↗(On Diff #183755)

Right. I will land this today when I have some time. Thanks for the review !

This revision was automatically updated to reflect the committed changes.

This was subsequently reverted. Is there a status update? Rebasing and committing D56959 would unblock traverser work and would allow this to progress separately in parallel.

riccibruno marked an inline comment as done.Jan 29 2019, 4:53 AM

This was subsequently reverted. Is there a status update? Rebasing and committing D56959 would unblock traverser work and would allow this to progress separately in parallel.

Sorry about that! I am going to land it right now. I just didn't want to do it just before going to sleep.