diff mbox

RFC: PR libstdc++/80064 make heap algorithms work with function types

Message ID 20170316130232.GA2682@redhat.com
State New
Headers show

Commit Message

Jonathan Wakely March 16, 2017, 1:02 p.m. UTC 
Richi reported a GCC 7 regression for a testcase from Cython that
boils down to:

void
test01(int* first, int* last)
{
  extern bool cmp(int, int);
  // PR libstdc++/80064
  // This is undefined, because [alg.sorting] requires the template argument
  // Compare to be a function object type, and bool(int, int) is not an
  // object type. We previously accepted it by accident, so keep doing so.
  std::make_heap<int*, bool(int, int)>(first, last, cmp);
}

I can restore support for this with the attached patch (changing the
heap algos to use the decayed type of the cmp parameter instead of the
original _Compare template argument type), but should we support it?

Is this worth fixing, or should we just say it worked by accident
before and the user code needs to be fixed?

FWIW MSVC accepts the example, libc++ rejects it for similar reasons
to GCC 7.

	PR libstdc++/80064
	* include/bits/stl_heap.h (__is_heap, push_heap, __adjust_heap)
	(pop_heap, make_heap, sort_heap, is_heap_until, is_heap): Cope with
	invalid instantiations using function types for _Compare argument.
	* testsuite/25_algorithms/make_heap/80064.cc: New test.
commit 873ca61fbfbd5b3a84d1f9c36cd09e8a5c54fbf5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Mar 16 12:24:42 2017 +0000

    PR libstdc++/80064 make heap algorithms work with function types
    
    	PR libstdc++/80064
    	* include/bits/stl_heap.h (__is_heap, push_heap, __adjust_heap)
    	(pop_heap, make_heap, sort_heap, is_heap_until, is_heap): Cope with
    	invalid instantiations using function types for _Compare argument.
    	* testsuite/25_algorithms/make_heap/80064.cc: New test.

Comments

Ville Voutilainen March 16, 2017, 1:31 p.m. UTC | #1 
On 16 March 2017 at 15:02, Jonathan Wakely <jwakely@redhat.com> wrote:
> Richi reported a GCC 7 regression for a testcase from Cython that
> boils down to:
>
> void
> test01(int* first, int* last)
> {
>  extern bool cmp(int, int);
>  // PR libstdc++/80064
>  // This is undefined, because [alg.sorting] requires the template argument
>  // Compare to be a function object type, and bool(int, int) is not an
>  // object type. We previously accepted it by accident, so keep doing so.
>  std::make_heap<int*, bool(int, int)>(first, last, cmp);
> }
>
> I can restore support for this with the attached patch (changing the
> heap algos to use the decayed type of the cmp parameter instead of the
> original _Compare template argument type), but should we support it?
>
> Is this worth fixing, or should we just say it worked by accident
> before and the user code needs to be fixed?
>
> FWIW MSVC accepts the example, libc++ rejects it for similar reasons
> to GCC 7.


All in all it seems to some extent reasonable to me to allow such
code. It seems rather easy
to fail to provide a function pointer as the comparator type, but also
rather easy for the implementation
to not mind that. I do find it suspicious that any user code would
bother providing the comparator
type as a template argument, though; whenever users feel encouraged to
do that, trouble ensues.
At this point I'm gravitating towards fixing the regression now, and
possibly being more stringent in the next
release, meaning gcc 8.
Jonathan Wakely March 16, 2017, 1:44 p.m. UTC | #2 
On 16/03/17 15:31 +0200, Ville Voutilainen wrote:
>All in all it seems to some extent reasonable to me to allow such
>code. It seems rather easy
>to fail to provide a function pointer as the comparator type, but also
>rather easy for the implementation
>to not mind that. I do find it suspicious that any user code would
>bother providing the comparator
>type as a template argument, though; whenever users feel encouraged to
>do that, trouble ensues.
>At this point I'm gravitating towards fixing the regression now, and
>possibly being more stringent in the next
>release, meaning gcc 8.

Yeah, we could add a static_assert with a user-friendly message
telling them why the code is invalid, instead of an impenetrable error
about internal implementation details.

So I'll commit the fix, treating it as a regression.
diff mbox

Patch

diff --git a/libstdc++-v3/include/bits/stl_heap.h b/libstdc++-v3/include/bits/stl_heap.h
index 3c102f1..f8cd0c0 100644
--- a/libstdc++-v3/include/bits/stl_heap.h
+++ b/libstdc++-v3/include/bits/stl_heap.h
@@ -100,7 +100,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
     inline bool
     __is_heap(_RandomAccessIterator __first, _Compare __comp, _Distance __n)
     {
-      __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+      typedef __decltype(__comp) _Cmp;
+      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
       return std::__is_heap_until(__first, __n, __cmp) == __n;
     }
 
@@ -313,8 +314,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       if (__last - __first > 1)
 	{
-	  using __gnu_cxx::__ops::_Iter_comp_iter;
-	  _Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+	  typedef __decltype(__comp) _Cmp;
+	  __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
 	  --__last;
 	  std::__pop_heap(__first, __last, __last, __cmp);
 	}
@@ -391,7 +392,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
-      __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+      typedef __decltype(__comp) _Cmp;
+      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
       std::__make_heap(__first, __last, __cmp);
     }
 
@@ -454,7 +456,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
       __glibcxx_requires_heap_pred(__first, __last, __comp);
 
-      __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+      typedef __decltype(__comp) _Cmp;
+      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
       std::__sort_heap(__first, __last, __cmp);
     }
 
@@ -508,7 +511,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_valid_range(__first, __last);
       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
-      __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+      typedef __decltype(__comp) _Cmp;
+      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
       return __first
 	+ std::__is_heap_until(__first, std::distance(__first, __last), __cmp);
     }
@@ -545,7 +549,8 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
       __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
 
       const auto __dist = std::distance(__first, __last);
-      __gnu_cxx::__ops::_Iter_comp_iter<_Compare> __cmp(_GLIBCXX_MOVE(__comp));
+      typedef __decltype(__comp) _Cmp;
+      __gnu_cxx::__ops::_Iter_comp_iter<_Cmp> __cmp(_GLIBCXX_MOVE(__comp));
       return std::__is_heap_until(__first, __dist, __cmp) == __dist;
     }
 #endif
diff --git a/libstdc++-v3/testsuite/25_algorithms/make_heap/80064.cc b/libstdc++-v3/testsuite/25_algorithms/make_heap/80064.cc
new file mode 100644
index 0000000..eedcc32
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/make_heap/80064.cc
@@ -0,0 +1,31 @@ 
+// Copyright (C) 2017 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-do compile }
+
+#include <algorithm>
+
+void
+test01(int* first, int* last)
+{
+  extern bool cmp(int, int);
+  // PR libstdc++/80064
+  // This is undefined, because [alg.sorting] requires the template argument
+  // Compare to be a function object type, and bool(int, int) is not an
+  // object type. We previously accepted it by accident, so keep doing so.
+  std::make_heap<int*, bool(int, int)>(first, last, cmp);
+}