Uploaded image for project: 'Data Management'
  1. Data Management
  2. DM-14992

Make sure proxy iterators are not declared random-access

    XMLWordPrintable

    Details

    • Type: Story
    • Status: In Progress
    • Resolution: Unresolved
    • Fix Version/s: None
    • Component/s: afw, ndarray
    • Labels:
      None

      Description

      It's impossible for a proxy iterator (an iterator that yields temporaries) to be a RandomAccessIterator, or even a ForwardIterator:

      • ForwardIterators must dereference to a true reference type.
      • If you try to meet that requirement by making the iterator itself hold a temporary by value, and return a reference to that, you run afoul of the ForwardIterator "multi-pass requirement", which demands that any two iterators that compare equal yield references to the same object in memory.

      I was unaware of the second condition when originally writing ndarray and afw::geom, and as a result we have a few proxy iterators that are incorrectly marked as RandomAccessIterators. The ones I've found so far are:

      • ndarray's NestedIterator
      • afw::geom::ellipses::PixelRegion::Iterator
      • afw::geom::SpanPixelIterator

      Fixing these may require reimplementing them without using the Boost.Iterator library, which seems to use iterator traversal tags to both determine the iterator category and what methods to implement (these iterators should still have e.g. efficient += operators, even if we can't use an iterator tag to indicate that they exist).

        Attachments

          Activity

          Hide
          krzys Krzysztof Findeisen added a comment -

          An alternative solution: do these need to be proxy iterators? I find C++'s use of proxy objects instead of interface-based polymorphism kind of weird...

          Show
          krzys Krzysztof Findeisen added a comment - An alternative solution: do these need to be proxy iterators? I find C++'s use of proxy objects instead of interface-based polymorphism kind of weird...
          Hide
          jbosch Jim Bosch added a comment - - edited

          I'm afraid they do need to be proxy iterators; making them not proxy iterators would require instantiating a container with all of the elements they would iterate over first, making them much more heavyweight to use.

          But yes, proxy iterators (like smart references) are in terrible shape in C++, and my understanding is that the standards committee has been considering (but not accepting) proposals to improve them since at least C++17. If you're curious, http://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/ is an interesting discussion of some of what makes it hard to fix (pre-C++17), and it ends with a nice framing of the options for the future (and from the comments, it seems quite likely that his option (3) - changes to the language itself - might be the only way forward).

          Show
          jbosch Jim Bosch added a comment - - edited I'm afraid they do need to be proxy iterators; making them not proxy iterators would require instantiating a container with all of the elements they would iterate over first, making them much more heavyweight to use. But yes, proxy iterators (like smart references) are in terrible shape in C++, and my understanding is that the standards committee has been considering (but not accepting) proposals to improve them since at least C++17. If you're curious, http://ericniebler.com/2015/01/28/to-be-or-not-to-be-an-iterator/ is an interesting discussion of some of what makes it hard to fix (pre-C++17), and it ends with a nice framing of the options for the future (and from the comments, it seems quite likely that his option (3) - changes to the language itself - might be the only way forward).

            People

            Assignee:
            jbosch Jim Bosch
            Reporter:
            jbosch Jim Bosch
            Watchers:
            Jim Bosch, Krzysztof Findeisen
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Dates

              Created:
              Updated:

                Jenkins Builds

                No builds found.