dblaikie added inline comments.
================
Comment at: llvm/include/llvm/ADT/BreadthFirstIterator.h:128-131
+ bool operator==(iterator_sentinel) const { return VisitQueue.empty(); }
+
+ bool operator!=(iterator_sentinel RHS) const { return !(*this == RHS); }
+
----------------
rusyaev-roman wrote:
> dblaikie wrote:
> > Generally any operator that can be a non-member should be a non-member (but
> > can still be a friend) so there's equal conversion handling for LHS and
> > RHS. Could you make these non-members? (maybe a separate patch to do the
> > same to the existing op overloads, so the new ones don't look weird)
> >
> > do you need the inverse operators too, so the sentinel can appear on either
> > side of the comparison?
> Absolutely agree with all your points!
>
> But I didn't want to make the code inconsistent and complicated in this
> patch. So, I suggest making all these operators 'friend' in a separate patch,
> otherwise it can lead to some boilerplate code like this:
> ```
> friend bool operator==(const scc_iterator &SCCI, iterator_sentinel) {
> return SCCI.isAtEnd();
> }
>
> friend bool operator==(iterator_sentinel IS, const scc_iterator &SCCI) {
> return SCCI == IS;
> }
>
> friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
> return !(SCCI == IS);
> }
>
> friend bool operator!=(const scc_iterator &SCCI, iterator_sentinel IS) {
> return !(IS == SCCI);
> }
> ```
> This boilerplate code can be avoided using special helper classes, but I
> wouldn't like to implement them in this patch in order to keep it simple.
>
> What do you think?
Sure sure - before or after's fine by me.
================
Comment at: llvm/include/llvm/ADT/SCCIterator.h:152-162
+ bool hasCycle() const {
+ assert(!SCC.empty() && "Dereferencing END SCC iterator!");
+ if (SCC.size() > 1)
+ return true;
+ NodeRef N = SCC.front();
+ for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
+ ++CI)
----------------
rusyaev-roman wrote:
> dblaikie wrote:
> > I'm not quite following why this requires the proxy object - even after
> > reading the comment above. It looks like this function is entirely in terms
> > of the `SCC` object that's returned from `operator*` - so maybe this could
> > be a free function, called with `hasCycle(*some_iterator)`?
> > maybe this could be a free function, called with hasCycle(*some_iterator)?
>
> This was my initial intention.
>
> But in the case of free function (or maybe static function of scc_iterator
> class) a user should write the following code:
> ```
> for (const auto& SCC : scc_traversal(Graph))
> if (hasCycle<decltype(Graph)>(SCC)) // or in more complicated case
> when GraphTraits cannot be deduced from Graph type --
> hasCycle<decltype(Graph), SubtGraphTraits>(SCC))
> ...
> ```
>
> This is the main reason of SCCProxy introduction -- to make it possible to
> write like this:
> ```
> for (const auto& SCC : scc_traversal(Graph))
> if (SCC.hasCycle())
> ...
> ```
Ooh, it's the graph traits that's the extra (type) parameter. Makes sense.
Yeah, if this is workable while meeting the iterator requirements/proxy
discussion elsewhere, sounds good.
================
Comment at: llvm/include/llvm/ADT/SCCIterator.h:165-170
+ SCCProxy operator*() const {
assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
return CurrentSCC;
}
+ SCCProxy operator->() const { return operator*(); }
----------------
rusyaev-roman wrote:
> dblaikie wrote:
> > I always forget in which cases you're allowed to return a proxy object from
> > an iterator - I thought some iterator concepts (maybe random access is the
> > level at which this kicks in?) that required something that amounts to
> > "there has to be a real object that outlives the iterator"
> >
> > Could you refresh my memory on that/on why proxy objects are acceptable for
> > this iterator type? (where/how does this iterator declare what concept it
> > models anyway, since this removed the facade helper?)
> A proxy object is allowed to be returned while dereferencing an `input
> iterator` (https://en.cppreference.com/w/cpp/named_req/InputIterator#Notes)
>
> ```
> The reference type for an input iterator that is not also a
> LegacyForwardIterator does not have to be a reference type: dereferencing an
> input iterator may return a proxy object or value_type itself by value
> ```
>
> For our case (that's `forward iterator`) we need to satisfy the following
> thing:
> ```
> The type std::iterator_traits<It>::reference must be exactly
> ...
> * const T& otherwise (It is constant),
>
> (where T is the type denoted by std::iterator_traits<It>::value_type)
> ```
> I'll also update the patch according to this point. Other things are ok for
> using a proxy object.
Thanks for doing the legwork/quotations there.
so what's the solution here, if we're going to meet the forward iterator
requirements but want a proxy object?
Repository:
rG LLVM Github Monorepo
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D131448/new/
https://reviews.llvm.org/D131448
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
