Re: C++ edge_iterator (was: Re: [SH] PR 53976 - Add RTL pass to eliminate clrt, sett insns)

[Trevor Saunders <tsaunders at mozilla dot com>]

On Mon, Dec 16, 2013 at 04:44:00PM +0100, Oleg Endo wrote:
> On Mon, 2013-12-16 at 09:57 -0500, Trevor Saunders wrote:
> > > 
> > > BTW, if you look at the patch, I haven't overloaded any ++ operators:
> > > 
> > > Index: gcc/vec.h
> > > ===================================================================
> > > --- gcc/vec.h	(revision 205866)
> > > +++ gcc/vec.h	(working copy)
> > > @@ -482,6 +482,15 @@
> > >    void quick_grow (unsigned len);
> > >    void quick_grow_cleared (unsigned len);
> > >  
> > > +  /* STL like iterator interface.  */
> > > +  typedef T* iterator;
> > > +  typedef const T* const_iterator;
> > > +
> > > +  iterator begin (void) { return &m_vecdata[0]; }
> > > +  iterator end (void) { return &m_vecdata[m_vecpfx.m_num]; }
> > > +  const_iterator begin (void) const { return &m_vecdata[0]; }
> > > +  const_iterator end (void) const { &m_vecdata[m_vecpfx.m_num]; }
> > > 
> > > This is because raw pointers can be used as random access iterators.
> 
> > yeah, somehow didn't occur to me T* just works (not that it wouldn't be
> > easier to see if the type had * in it)
> > 
> 
> Actually, it's the other way around.  (STL) Iterators behave like
> pointers.  The only difference is that depending on the iterator
> capabilities (which depend on the container type), the amount of pointer
> arithmetic that can be done with an iterator is restricted, where a
> random access iterator is a like a raw pointer.

Well, iterators are sort of irrelevent to what I was commenting on, the
point is the original code

for (iterator_type i = thing.begin (); i != thing.end (); i++)
works because i is a pointer and they define all the necessary
operations.

> > actually what I really want to do is make returning a const vector part
> > of the api for getting the edge list from a basic block and then just
> > write
> > 
> > for (edge *e = vec.begin (); e != vec.end (); e++)
> > 
> > which imo makes it clear what's happening and is short, but I guess
> > richi doesn't like the interface being that a vector is returned :/
> 
> The above usage assumes that the container stores elements in contiguous
> memory.  I know it's highly hypothetical in this case, but if one day
> somebody wanted to try out a more suitable container to store edges in
> basic blocks (let's say a linked list), it would be slightly impossible
> to replace it without touching all the code.

sure, you'd have to either touch all the code or leave this interface
with a slow wrapper that converted a linked list or whatever to a
vector.

> Apart from that, I guess iteration over a linked list or some kind of
> tree would look totally different.  I think iteration should look the
> same regardless of the container type being used.  It makes it easier to
> jump into foreign code and helps focusing on the actual problem the code
> is trying to solve.

I'd disagree, vectors linked lists and trees all work differently and
have totally different performance characteristics, so it makes sense
they have different interfaces.

> > > but that means, that there can be only one type of edge container ever.
> > 
> > gcc seems to have survived for a long time with a single edge_iterator
> > so I don't see much reason to worry about allowing
> > basic_block::edge_iterator and foobar::edge_iterator.
> 
> Yes, having one freestanding edge_iterator type is probably sufficient
> for the near future.  I just didn't want to break existing code.

and I was suggesting we just change all the existing code.

> > well, I meant edge_iterator instead of basic_block::edge_iterator which
> > afaik is what you proposed?
> 
> Yes, I was proposing to have a basic_block::edge_iterator or
> basic_block::edge_container::iterator or something similar.
> 
> > I know doing this for pointer wrappers is common and I think that's
> > fine.  However I'm not really convinced we need to or should make
> > basic_block a pointer wrapper class, I'd wrather see basic_block_def
> > become basic_block, and use basic_block * all over.
> 
> That could also be an option.  Although having pointer wrappers already
> in place might open some other opportunities in the future.  For
> instance it would make it relatively easy to try out reducing the number
> of garbage collected objects by adding smart pointer functionality to
> the pointer wrapper.

Well, I'd expect freeing stuff owned by basic_block should happen in
basic_block::~basic_block not some pointer wrapper which would be more
error prone.  However making that happen is kind of tricky while
basic_block is in gc memory, I've been idly considering allowing gentype
to call dtors somehow...

> > > Overloading "operator ->" is also required in iterators.  See
> > > http://www.cplusplus.com/reference/iterator/
> > > If raw pointers are used as iterators (as in my example patch), there's
> > > nothing to overload for those of course.
> > 
> > yeah, I'm not really a fan of that style of iterator :/
> 
> But in the end, that iterator style allows writing code as you suggested
> above:
> 
> > for (edge *e = vec.begin (); e != vec.end (); e++)

sure, I think writing that for a vector makes sense, though I might
manually pull the vec.end() out of the loop at which point I might just
use indicies instead of end() / begin(), but I don't think it makes much
sense to write that to iterate over a linked list.

Trev


> 
> The only difference is that you don't write "edge*" but e.g.
> "vec<edge>::iterator e", or just "auto" in C++11.
> 
> Cheers,
> Oleg
>