[PATCH] LWG 2537 fix priority_queue constructors to establish invariant

[Jonathan Wakely]

This change is safe to make now (in stage 4), because the constructors
are currently incorrect and unusable (unless the supplied container
already contains a heap, in which case the new make_heap calls are
redundant but harmless).

	* doc/xml/manual/intro.xml: Document LWG 2537 status.
	* include/bits/stl_queue.h
	(priority_queue(const Compare&, const Container&, const Alloc&))
	(priority_queue(const Compare&, Container&&, const Alloc&)): Call
	make_heap.
	* testsuite/23_containers/priority_queue/dr2537.cc: New test.

Tested powerpc64le-linux, committed to trunk.

-------------- next part --------------
commit 00eb831064ca6c6cfff48b2f3f8b1217b0c5d527
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Feb 14 10:52:56 2019 +0000

    LWG 2537 fix priority_queue constructors to establish invariant
    
    This change is safe to make now (in stage 4), because the constructors
    are currently incorrect and unusable (unless the supplied container
    already contains a heap, in which case the new make_heap calls are
    redundant but harmless).
    
            * doc/xml/manual/intro.xml: Document LWG 2537 status.
            * include/bits/stl_queue.h
            (priority_queue(const Compare&, const Container&, const Alloc&))
            (priority_queue(const Compare&, Container&&, const Alloc&)): Call
            make_heap.
            * testsuite/23_containers/priority_queue/dr2537.cc: New test.

diff --git a/libstdc++-v3/doc/xml/manual/intro.xml b/libstdc++-v3/doc/xml/manual/intro.xml
index 2a3231f4eb4..656e32b00aa 100644
--- a/libstdc++-v3/doc/xml/manual/intro.xml
+++ b/libstdc++-v3/doc/xml/manual/intro.xml
@@ -1127,6 +1127,14 @@ requirements of the license of GCC.
     <listitem><para>Add static assertions to enforce the requirement.
     </para></listitem></varlistentry>
 
+    <varlistentry xml:id="manual.bugs.dr2566"><term><link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="&DR;#2566">2566</link>:
+       <emphasis>Constructors for <code>priority_queue</code> taking allocators
+	 should call <code>make_heap</code>
+       </emphasis>
+    </term>
+    <listitem><para>Call <code>make_heap</code>.
+    </para></listitem></varlistentry>
+
     <varlistentry xml:id="manual.bugs.dr2583"><term><link xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="&DR;#2583">2583</link>:
        <emphasis>There is no way to supply an allocator for <code>basic_string(str, pos)</code>
        </emphasis>
diff --git a/libstdc++-v3/include/bits/stl_queue.h b/libstdc++-v3/include/bits/stl_queue.h
index 1eb56810edc..dd1d5d9727a 100644
--- a/libstdc++-v3/include/bits/stl_queue.h
+++ b/libstdc++-v3/include/bits/stl_queue.h
@@ -520,14 +520,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	priority_queue(const _Compare& __x, const _Alloc& __a)
 	: c(__a), comp(__x) { }
 
+      // _GLIBCXX_RESOLVE_LIB_DEFECTS
+      // 2537. Constructors [...] taking allocators should call make_heap
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	priority_queue(const _Compare& __x, const _Sequence& __c,
 		       const _Alloc& __a)
-	: c(__c, __a), comp(__x) { }
+	: c(__c, __a), comp(__x)
+	{ std::make_heap(c.begin(), c.end(), comp); }
 
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	priority_queue(const _Compare& __x, _Sequence&& __c, const _Alloc& __a)
-	: c(std::move(__c), __a), comp(__x) { }
+	: c(std::move(__c), __a), comp(__x)
+	{ std::make_heap(c.begin(), c.end(), comp); }
 
       template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
 	priority_queue(const priority_queue& __q, const _Alloc& __a)
diff --git a/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc
new file mode 100644
index 00000000000..ecb51780ee5
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/priority_queue/dr2537.cc
@@ -0,0 +1,50 @@
+// Copyright (C) 2019 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 run { target c++11 } }
+
+#include <queue>
+#include <testsuite_hooks.h>
+
+struct Q : std::priority_queue<int>
+{
+  using priority_queue::priority_queue;
+
+  bool is_heap() const
+  { return std::is_heap(c.begin(), c.end()); }
+};
+
+void
+test01()
+{
+  const Q::value_compare cmp;
+  const Q::container_type c{ 2, 3, 5, 7, 11, 13, 17, 19, 23 };
+  const Q::container_type::allocator_type a;
+
+  Q q1(cmp, c, a);
+  VERIFY( q1.is_heap() );
+
+  auto c2 = c;
+  Q q2(cmp, std::move(c2), a);
+  VERIFY( q2.is_heap() );
+}
+
+int
+main()
+{
+  test01();
+}