rusyaev-roman added a comment.
First of all, thank you for your feedback! I've tried to address all your
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); }
+
----------------
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?
================
Comment at: llvm/include/llvm/ADT/SCCIterator.h:49-50
using SccTy = std::vector<NodeRef>;
- using reference = typename scc_iterator::reference;
+ using reference = const SccTy &;
+ using pointer = const SccTy *;
----------------
dblaikie wrote:
> does this need a `value` type too? (& then define the `reference` and
> `pointer` types relative to that)
Thanks, good point! I forgot to add additional types and member functions to
satisfy `forward iterator` requirements when I removed `iterator_facade` base
class. I'll update the patch (maybe get iterator_facade back)
================
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)
----------------
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())
...
```
================
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*(); }
----------------
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.
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
