[PATCH] libstdc++: Avoid double-deref of __first in ranges::minmax [PR104858]

[PATCH] libstdc++: Avoid double-deref of __first in ranges::minmax [PR104858]

[Patrick Palka]

Tested on x86_64-pc-linux-gnu, does this look OK for trunk and 11/10
once the branch is unfrozen?

	PR libstdc++/104858

libstdc++-v3/ChangeLog:

	* include/bits/ranges_algo.h (__minmax_fn): Avoid dereferencing
	__first twice at the start.
	* testsuite/25_algorithms/minmax/constrained.cc (test06): New test.
---
 libstdc++-v3/include/bits/ranges_algo.h       |  2 +-
 .../25_algorithms/minmax/constrained.cc       | 23 +++++++++++++++++++
 2 files changed, 24 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index 62dc605080a..3d30fb1428c 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -3084,7 +3084,7 @@ namespace ranges
 	auto __last = ranges::end(__r);
 	__glibcxx_assert(__first != __last);
 	auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
-	minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
+	minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
 	if (++__first == __last)
 	  return __result;
 	else
diff --git a/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
index 90882afb6d0..306c495babe 100644
--- a/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
@@ -129,6 +129,28 @@ test05()
   VERIFY( result.min == "a"s && result.max == "c"s );
 }
 
+struct A {
+  A() = default;
+  A(const A&) = default;
+  A(A&&) { ++move_count; }
+  A& operator=(const A&) = default;
+  A& operator=(A&&) = default;
+  friend auto operator<=>(const A&, const A&) = default;
+  static inline int move_count = 0;
+};
+
+void
+test06()
+{
+  // PR libstdc++/104858
+  // Verify ranges::minmax doesn't dereference the iterator for the first
+  // element in the range twice.
+  A a;
+  ranges::subrange r = {std::move_iterator(&a), std::move_sentinel(&a + 1)};
+  ranges::minmax(r);
+  VERIFY( A::move_count == 1 );
+}
+
 int
 main()
 {
@@ -137,4 +159,5 @@ main()
   test03();
   test04();
   test05();
+  test06();
 }
-- 
2.36.0.rc2.10.g1ac7422e39

Re: [PATCH] libstdc++: Avoid double-deref of __first in ranges::minmax [PR104858]

[Jonathan Wakely]

On Thu, 14 Apr 2022 at 16:21, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk and 11/10
> once the branch is unfrozen?
>
>         PR libstdc++/104858
>
> libstdc++-v3/ChangeLog:
>
>         * include/bits/ranges_algo.h (__minmax_fn): Avoid dereferencing
>         __first twice at the start.
>         * testsuite/25_algorithms/minmax/constrained.cc (test06): New test.
> ---
>  libstdc++-v3/include/bits/ranges_algo.h       |  2 +-
>  .../25_algorithms/minmax/constrained.cc       | 23 +++++++++++++++++++
>  2 files changed, 24 insertions(+), 1 deletion(-)
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index 62dc605080a..3d30fb1428c 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -3084,7 +3084,7 @@ namespace ranges
>         auto __last = ranges::end(__r);
>         __glibcxx_assert(__first != __last);
>         auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
> -       minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
> +       minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};

Clever ... I'm surprised this even works. I would have expected it to
evaluate both initializers before actually initializing the members.
TIL.

OK for trunk now, and branches once thawed.


>         if (++__first == __last)
>           return __result;
>         else
> diff --git a/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
> index 90882afb6d0..306c495babe 100644
> --- a/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
> +++ b/libstdc++-v3/testsuite/25_algorithms/minmax/constrained.cc
> @@ -129,6 +129,28 @@ test05()
>    VERIFY( result.min == "a"s && result.max == "c"s );
>  }
>
> +struct A {
> +  A() = default;
> +  A(const A&) = default;
> +  A(A&&) { ++move_count; }
> +  A& operator=(const A&) = default;
> +  A& operator=(A&&) = default;
> +  friend auto operator<=>(const A&, const A&) = default;
> +  static inline int move_count = 0;
> +};
> +
> +void
> +test06()
> +{
> +  // PR libstdc++/104858
> +  // Verify ranges::minmax doesn't dereference the iterator for the first
> +  // element in the range twice.
> +  A a;
> +  ranges::subrange r = {std::move_iterator(&a), std::move_sentinel(&a + 1)};
> +  ranges::minmax(r);
> +  VERIFY( A::move_count == 1 );
> +}
> +
>  int
>  main()
>  {
> @@ -137,4 +159,5 @@ main()
>    test03();
>    test04();
>    test05();
> +  test06();
>  }
> --
> 2.36.0.rc2.10.g1ac7422e39
>

Re: [PATCH] libstdc++: Avoid double-deref of __first in ranges::minmax [PR104858]

[Patrick Palka]

On Thu, 14 Apr 2022, Jonathan Wakely wrote:

> On Thu, 14 Apr 2022 at 16:21, Patrick Palka via Libstdc++
> <libstdc++@gcc.gnu.org> wrote:
> >
> > Tested on x86_64-pc-linux-gnu, does this look OK for trunk and 11/10
> > once the branch is unfrozen?
> >
> >         PR libstdc++/104858
> >
> > libstdc++-v3/ChangeLog:
> >
> >         * include/bits/ranges_algo.h (__minmax_fn): Avoid dereferencing
> >         __first twice at the start.
> >         * testsuite/25_algorithms/minmax/constrained.cc (test06): New test.
> > ---
> >  libstdc++-v3/include/bits/ranges_algo.h       |  2 +-
> >  .../25_algorithms/minmax/constrained.cc       | 23 +++++++++++++++++++
> >  2 files changed, 24 insertions(+), 1 deletion(-)
> >
> > diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> > index 62dc605080a..3d30fb1428c 100644
> > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > @@ -3084,7 +3084,7 @@ namespace ranges
> >         auto __last = ranges::end(__r);
> >         __glibcxx_assert(__first != __last);
> >         auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
> > -       minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
> > +       minmax_result<range_value_t<_Range>> __result = {*__first, __result.min};
> 
> Clever ... I'm surprised this even works. I would have expected it to
> evaluate both initializers before actually initializing the members.
> TIL.

Indeed, it seems to do the right thing, practically speaking at least :)
FWIW the alternative approach

-       minmax_result<range_value_t<_Range>> __result = {*__first, *__first};
+       minmax_result<range_value_t<_Range>> __result;
+       __result.max = __result.min = *__first;

wouldn't be right because the value type is not necessarily default
constructible.  I beefed up the new testcase to verify we don't demand
default constructibility here.