[Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly

public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed

* [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly
@ 2021-05-07 23:04 rs2740 at gmail dot com
  2021-05-07 23:09 ` [Bug libstdc++/100479] " redi at gcc dot gnu.org
                   ` (4 more replies)
  0 siblings, 5 replies; 6+ messages in thread
From: rs2740 at gmail dot com @ 2021-05-07 23:04 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

            Bug ID: 100479
           Summary: range adaptors handle cached iterators incorrectly
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rs2740 at gmail dot com
  Target Milestone: ---

template<forward_range _Range>
      struct _CachedPosition<_Range>
      {
      private:
        iterator_t<_Range> _M_iter{};

      public:
        constexpr bool
        _M_has_value() const
        { return _M_iter != iterator_t<_Range>{}; }

        constexpr iterator_t<_Range>
        _M_get(const _Range&) const
        {
          __glibcxx_assert(_M_has_value());
          return _M_iter;
        }

        constexpr void
        _M_set(const _Range&, const iterator_t<_Range>& __it)
        {
          __glibcxx_assert(!_M_has_value());
          _M_iter = __it;
        }
      };

- The domain of == for forward iterators is limited to iterators over the same
underlying sequence. While value-initialized forward iterators of the same type
may be compared against each other, comparing them against iterators into other
ranges is not required to be well-defined, so it cannot be used as a sentinel
value.
- The cache cannot be allowed to propagate when the view containing it is
copied/moved, and has to be invalidated when the view containing it is moved.
Any cached iterator points to the original underlying view, and not the new
one; also, moving from a view can change its value (if it is well-defined to
use the moved-from view), so the cache is no longer valid. (Handling this case
correctly was actually the original use case for non-propagating-cache in
range-v3.)

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Bug libstdc++/100479] range adaptors handle cached iterators incorrectly
  2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
@ 2021-05-07 23:09 ` redi at gcc dot gnu.org
  2021-05-11 15:28 ` ppalka at gcc dot gnu.org
                   ` (3 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2021-05-07 23:09 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
   Last reconfirmed|                            |2021-05-07

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Bug libstdc++/100479] range adaptors handle cached iterators incorrectly
  2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
  2021-05-07 23:09 ` [Bug libstdc++/100479] " redi at gcc dot gnu.org
@ 2021-05-11 15:28 ` ppalka at gcc dot gnu.org
  2021-05-24 19:24 ` cvs-commit at gcc dot gnu.org
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-05-11 15:28 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |ppalka at gcc dot gnu.org
             Status|NEW                         |ASSIGNED
                 CC|                            |ppalka at gcc dot gnu.org

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Bug libstdc++/100479] range adaptors handle cached iterators incorrectly
  2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
  2021-05-07 23:09 ` [Bug libstdc++/100479] " redi at gcc dot gnu.org
  2021-05-11 15:28 ` ppalka at gcc dot gnu.org
@ 2021-05-24 19:24 ` cvs-commit at gcc dot gnu.org
  2021-05-28 14:21 ` cvs-commit at gcc dot gnu.org
  2021-10-12 19:00 ` ppalka at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-05-24 19:24 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

--- Comment #1 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Patrick Palka <ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:46ed811bcb4b86a81ef3d78ea8cfffc6cd043144

commit r12-1018-g46ed811bcb4b86a81ef3d78ea8cfffc6cd043144
Author: Patrick Palka <ppalka@redhat.com>
Date:   Mon May 24 15:24:44 2021 -0400

    libstdc++: Fix iterator caching inside range adaptors [PR100479]

    This fixes two issues with our iterator caching as described in detail
    in the PR.  Since we recently added the __non_propagating_cache class
    template as part of r12-336 for P2328, this patch just rewrites the
    problematic _CachedPosition partial specialization in terms of this
    class template.

    For the offset partial specialization, it's safe to propagate the cached
    offset on copy/move, but we should still invalidate the cached offset in
    the source object on move.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100479
            * include/std/ranges (__detail::__non_propagating_cache): Move
            definition up to before that of _CachedPosition.  Make base
            class _Optional_base protected instead of private.  Add const
            overload for operator*.
            (__detail::_CachedPosition): Rewrite the partial specialization
            for forward ranges as a derived class of __non_propagating_cache.
            Remove the size constraint on the partial specialization for
            random access ranges.  Add
copy/move/copy-assignment/move-assignment
            members to the offset partial specialization for random
            access ranges that propagate the cached value but additionally
            invalidate it in the source object on move.
            * testsuite/std/ranges/adaptors/100479.cc: New test.

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Bug libstdc++/100479] range adaptors handle cached iterators incorrectly
  2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
                   ` (2 preceding siblings ...)
  2021-05-24 19:24 ` cvs-commit at gcc dot gnu.org
@ 2021-05-28 14:21 ` cvs-commit at gcc dot gnu.org
  2021-10-12 19:00 ` ppalka at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: cvs-commit at gcc dot gnu.org @ 2021-05-28 14:21 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

--- Comment #2 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The releases/gcc-11 branch has been updated by Patrick Palka
<ppalka@gcc.gnu.org>:

https://gcc.gnu.org/g:49f369fb33fb5bed4dadfb5b42b23cded888ab52

commit r11-8476-g49f369fb33fb5bed4dadfb5b42b23cded888ab52
Author: Patrick Palka <ppalka@redhat.com>
Date:   Mon May 24 15:24:44 2021 -0400

    libstdc++: Fix iterator caching inside range adaptors [PR100479]

    This fixes two issues with our iterator caching as described in detail
    in the PR.  Since we recently added the __non_propagating_cache class
    template as part of r12-336 for P2328, this patch just rewrites the
    problematic _CachedPosition partial specialization in terms of this
    class template.

    For the offset partial specialization, it's safe to propagate the cached
    offset on copy/move, but we should still invalidate the cached offset in
    the source object on move.

    libstdc++-v3/ChangeLog:

            PR libstdc++/100479
            * include/std/ranges (__detail::__non_propagating_cache): Move
            definition up to before that of _CachedPosition.  Make base
            class _Optional_base protected instead of private.  Add const
            overload for operator*.
            (__detail::_CachedPosition): Rewrite the partial specialization
            for forward ranges as a derived class of __non_propagating_cache.
            Remove the size constraint on the partial specialization for
            random access ranges.  Add
copy/move/copy-assignment/move-assignment
            members to the offset partial specialization for random
            access ranges that propagate the cached value but additionally
            invalidate it in the source object on move.
            * testsuite/std/ranges/adaptors/100479.cc: New test.

    (cherry picked from commit 46ed811bcb4b86a81ef3d78ea8cfffc6cd043144)

^ permalink raw reply	[flat|nested] 6+ messages in thread

* [Bug libstdc++/100479] range adaptors handle cached iterators incorrectly
  2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
                   ` (3 preceding siblings ...)
  2021-05-28 14:21 ` cvs-commit at gcc dot gnu.org
@ 2021-10-12 19:00 ` ppalka at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: ppalka at gcc dot gnu.org @ 2021-10-12 19:00 UTC (permalink / raw)
  To: gcc-bugs

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=100479

Patrick Palka <ppalka at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.2
             Status|ASSIGNED                    |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Patrick Palka <ppalka at gcc dot gnu.org> ---
Fixed for 11.2/12

^ permalink raw reply	[flat|nested] 6+ messages in thread

end of thread, other threads:[~2021-10-12 19:00 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2021-05-07 23:04 [Bug libstdc++/100479] New: range adaptors handle cached iterators incorrectly rs2740 at gmail dot com
2021-05-07 23:09 ` [Bug libstdc++/100479] " redi at gcc dot gnu.org
2021-05-11 15:28 ` ppalka at gcc dot gnu.org
2021-05-24 19:24 ` cvs-commit at gcc dot gnu.org
2021-05-28 14:21 ` cvs-commit at gcc dot gnu.org
2021-10-12 19:00 ` ppalka at gcc dot gnu.org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).