From patchwork Sat Dec 3 15:35:43 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 129087 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 530E8B6F76 for ; Sun, 4 Dec 2011 02:36:10 +1100 (EST) Received: (qmail 4808 invoked by alias); 3 Dec 2011 15:36:05 -0000 Received: (qmail 4521 invoked by uid 22791); 3 Dec 2011 15:36:04 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL, BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_LOW X-Spam-Check-By: sourceware.org Received: from mail-ww0-f51.google.com (HELO mail-ww0-f51.google.com) (74.125.82.51) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 03 Dec 2011 15:35:46 +0000 Received: by wgbdr1 with SMTP id dr1so3098352wgb.8 for ; Sat, 03 Dec 2011 07:35:44 -0800 (PST) MIME-Version: 1.0 Received: by 10.227.60.12 with SMTP id n12mr2570998wbh.13.1322926543688; Sat, 03 Dec 2011 07:35:43 -0800 (PST) Received: by 10.216.68.76 with HTTP; Sat, 3 Dec 2011 07:35:43 -0800 (PST) In-Reply-To: References: <20111112135324.GA23388@x4.trippels.de> <20111112141241.GB23388@x4.trippels.de> Date: Sat, 3 Dec 2011 15:35:43 +0000 Message-ID: Subject: Re: empty range in pop_heap From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches Cc: Markus Trippelsdorf Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org On 12 November 2011 15:14, Jonathan Wakely wrote: > On 12 November 2011 15:04, Marc Glisse wrote: >> >> Debug-mode seems to check that first,last is a valid range, is a heap, but >> not that it is not empty. Maybe it could? > > Good idea, thanks.  I'll change that. As promised. * include/debug/macros.h (__glibcxx_check_non_empty_range): Define. * include/debug/debug.h (__glibcxx_requires_non_empty_range): Define. * include/debug/formatter.h (__msg_non_empty_range): Add. * src/debug.cc: Message text for __msg_non_empty_range. * include/bits/stl_heap.h (pop_heap): Check for non-empty range. * testsuite/25_algorithms/pop_heap/empty_neg.cc: New. Tested x86_64-linux, committed to trunk. Index: include/debug/macros.h =================================================================== --- include/debug/macros.h (revision 181967) +++ include/debug/macros.h (working copy) @@ -57,6 +57,13 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__val ._M_iterator(_First, #_First) \ ._M_iterator(_Last, #_Last)) +// Verify that [_First, _Last) forms a non-empty iterator range. +#define __glibcxx_check_non_empty_range(_First,_Last) \ +_GLIBCXX_DEBUG_VERIFY(_First != _Last, \ + _M_message(__gnu_debug::__msg_non_empty_range) \ + ._M_iterator(_First, #_First) \ + ._M_iterator(_Last, #_Last)) + /** Verify that we can insert into *this with the iterator _Position. * Insertion into a container at a specific position requires that * the iterator be nonsingular, either dereferenceable or past-the-end, Index: include/debug/debug.h =================================================================== --- include/debug/debug.h (revision 181967) +++ include/debug/debug.h (working copy) @@ -1,6 +1,6 @@ // Debugging support implementation -*- C++ -*- -// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 +// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free @@ -64,6 +64,7 @@ namespace __gnu_debug # define _GLIBCXX_DEBUG_ONLY(_Statement) ; # define __glibcxx_requires_cond(_Cond,_Msg) # define __glibcxx_requires_valid_range(_First,_Last) +# define __glibcxx_requires_non_empty_range(_First,_Last) # define __glibcxx_requires_sorted(_First,_Last) # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) # define __glibcxx_requires_sorted_set(_First1,_Last1,_First2) @@ -96,6 +97,8 @@ namespace __gnu_debug # define __glibcxx_requires_cond(_Cond,_Msg) _GLIBCXX_DEBUG_VERIFY(_Cond,_Msg) # define __glibcxx_requires_valid_range(_First,_Last) \ __glibcxx_check_valid_range(_First,_Last) +# define __glibcxx_requires_non_empty_range(_First,_Last) \ + __glibcxx_check_non_empty_range(_First,_Last) # define __glibcxx_requires_sorted(_First,_Last) \ __glibcxx_check_sorted(_First,_Last) # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \ Index: include/debug/formatter.h =================================================================== --- include/debug/formatter.h (revision 181967) +++ include/debug/formatter.h (working copy) @@ -108,7 +108,8 @@ namespace __gnu_debug __msg_erase_after_bad, __msg_valid_range2, // unordered sequence local iterators - __msg_local_iter_compare_bad + __msg_local_iter_compare_bad, + __msg_non_empty_range }; class _Error_formatter Index: src/debug.cc =================================================================== --- src/debug.cc (revision 181967) +++ src/debug.cc (working copy) @@ -176,7 +176,8 @@ namespace __gnu_debug ", \"%2.name;\" shall be before and not equal to \"%3.name;\"", // std::unordered_container::local_iterator "attempt to compare local iterators from different unordered container" - " buckets" + " buckets", + "function requires a non-empty iterator range [%1.name;, %2.name;)" }; void Index: include/bits/stl_heap.h =================================================================== --- include/bits/stl_heap.h (revision 181967) +++ include/bits/stl_heap.h (working copy) @@ -1,7 +1,7 @@ // Heap implementation -*- C++ -*- -// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 -// Free Software Foundation, Inc. +// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, +// 2011 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 @@ -270,6 +270,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION * @brief Pop an element off a heap. * @param __first Start of heap. * @param __last End of heap. + * @pre [__first, __last) is a valid, non-empty range. * @ingroup heap_algorithms * * This operation pops the top of the heap. The elements __first @@ -287,6 +288,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept< _RandomAccessIterator>) __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>) + __glibcxx_requires_non_empty_range(__first, __last); __glibcxx_requires_valid_range(__first, __last); __glibcxx_requires_heap(__first, __last); Index: testsuite/25_algorithms/pop_heap/empty_neg.cc =================================================================== --- testsuite/25_algorithms/pop_heap/empty_neg.cc (revision 0) +++ testsuite/25_algorithms/pop_heap/empty_neg.cc (revision 0) @@ -0,0 +1,37 @@ +// Copyright (C) 2011 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 Pred 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 +// . + +// 25.3.6 Heap operations [lib.alg.heap.operations] + +// { dg-require-debug-mode "" } +// { dg-do run { xfail *-*-* } } + +#include + +void +test01() +{ + int i = 0; + std::pop_heap(&i, &i); +} + +int +main() +{ + test01(); + return 0; +}