[Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity

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

* [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity
@ 2014-03-13 20:03 redi at gcc dot gnu.org
  2014-10-13 15:02 ` [Bug libstdc++/60519] " redi at gcc dot gnu.org
                   ` (4 more replies)
  0 siblings, 5 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2014-03-13 20:03 UTC (permalink / raw)
  To: gcc-bugs

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60519

            Bug ID: 60519
           Summary: Debug mode should check comparators for irreflexivity
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: redi at gcc dot gnu.org

We could avoid a number of INVALID bug reports (e.g. PR59391) if Debug Mode did
this in <algorithm>

#ifdef _GLIBCXX_DEBUG
if (first < last)
    __glibcxx_assert( !cmp(*first, *first) );
#endif


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

* [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
  2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
@ 2014-10-13 15:02 ` redi at gcc dot gnu.org
  2015-04-11 19:09 ` redi at gcc dot gnu.org
                   ` (3 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2014-10-13 15:02 UTC (permalink / raw)
  To: gcc-bugs

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2014-10-13
                 CC|                            |fdumont at gcc dot gnu.org
     Ever confirmed|0                           |1


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

* [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
  2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
  2014-10-13 15:02 ` [Bug libstdc++/60519] " redi at gcc dot gnu.org
@ 2015-04-11 19:09 ` redi at gcc dot gnu.org
  2015-04-12 19:57 ` fdumont at gcc dot gnu.org
                   ` (2 subsequent siblings)
  4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2015-04-11 19:09 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
I was thinking we'd add a new macro to <debug/macros.h>

#define __glibcxx_check_strict_weak_order(_First,_Last,_Pred)          \
_GLIBCXX_DEBUG_VERIFY(_First==_Last || !_Pred(*_First, *_First),       \
                     _M_message(__gnu_debug::__msg_strict_weak_order))

(with accompanying __msg_strict_weak_order message)

Then simply add that where appropriate:

--- bits/stl_algo.h.orig        2015-04-11 13:58:05.253760716 +0100
+++ bits/stl_algo.h     2015-04-11 13:58:11.483766861 +0100
@@ -4725,6 +4725,7 @@
            typename iterator_traits<_RandomAccessIterator>::value_type,
            typename iterator_traits<_RandomAccessIterator>::value_type>)
       __glibcxx_requires_valid_range(__first, __last);
+      __glibcxx_check_strict_weak_order(__first, __last, __comp);

       std::__sort(__first, __last,
__gnu_cxx::__ops::__iter_comp_iter(__comp));
     }

We could also consider including the function name in the message, either
passed to the macro directly:

#define __glibcxx_check_strict_weak_order(_First,_Last,_Pred,_Where)   \
_GLIBCXX_DEBUG_VERIFY(_First==_Last || !_Pred(*_First, *_First),       \
                     _M_message(__gnu_debug::__msg_strict_weak_order)) \
                     ._M_string(_Where)

or using __func__ or __PRETTY_FUNCTION__:

#define __glibcxx_check_strict_weak_order(_First,_Last,_Pred)          \
_GLIBCXX_DEBUG_VERIFY(_First==_Last || !_Pred(*_First, *_First),       \
                     _M_message(__gnu_debug::__msg_strict_weak_order)) \
                     ._M_string(__func__)

This would allow something like:

/home/jwakely/gcc/5/include/c++/5.0.0/bits/stl_algo.h:4729:error: 
    comparison function passed to 'std::sort' is invalid because comp(x, x)
returns true (the function must define a Strict Weak Ordering, so must be
irreflexive).
Aborted (core dumped)


If the checks are added in _Iter_comp_iter we lost the ability to include the
location string in the output.


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

* [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
  2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
  2014-10-13 15:02 ` [Bug libstdc++/60519] " redi at gcc dot gnu.org
  2015-04-11 19:09 ` redi at gcc dot gnu.org
@ 2015-04-12 19:57 ` fdumont at gcc dot gnu.org
  2015-04-12 20:59 ` redi at gcc dot gnu.org
  2015-08-25 20:27 ` fdumont at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: fdumont at gcc dot gnu.org @ 2015-04-12 19:57 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #2 from François Dumont <fdumont at gcc dot gnu.org> ---
Created attachment 35305
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=35305&action=edit
Strict weak ordering debug check patch

On my side here what I had plan to do. This patch rely on additional feature in
the _Formatter type to pass a type or iterator value_type to point the user to
the invalid operator or functor. It also do not perform the check if the
comparator is not able to handle it.

So yes it doubles the number of comparisons which is definitely a performance
hint but your patch on the other hand expect to detect an implementation issue
on only 1 use case so it can miss many kind of wrong implementation on special
instances.
>From gcc-bugs-return-483450-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Apr 12 20:03:46 2015
Return-Path: <gcc-bugs-return-483450-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 15660 invoked by alias); 12 Apr 2015 20:03:45 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 15618 invoked by uid 48); 12 Apr 2015 20:03:41 -0000
From: "dimhen at gmail dot com" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug middle-end/65686] [4.9 regression] inconsistent warning maybe-uninitialized: warn about 'unsigned', not warn about 'int'
Date: Sun, 12 Apr 2015 20:03:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: middle-end
X-Bugzilla-Version: 5.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: dimhen at gmail dot com
X-Bugzilla-Status: UNCONFIRMED
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: short_desc
Message-ID: <bug-65686-4-szfG1VSbGG@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-65686-4@http.gcc.gnu.org/bugzilla/>
References: <bug-65686-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-04/txt/msg01002.txt.bz2
Content-length: 744

https://gcc.gnu.org/bugzilla/show_bug.cgi?ide686

Dmitry G. Dyachenko <dimhen at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|incorrect warning           |[4.9 regression]
                   |maybe-uninitialized         |inconsistent warning
                   |                            |maybe-uninitialized: warn
                   |                            |about 'unsigned', not warn
                   |                            |about 'int'

--- Comment #1 from Dmitry G. Dyachenko <dimhen at gmail dot com> ---
gcc version 4.9.3 20150412 (prerelease) [gcc-4_9-branch revision 222021] (GCC)
PASS


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

* [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
  2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
                   ` (2 preceding siblings ...)
  2015-04-12 19:57 ` fdumont at gcc dot gnu.org
@ 2015-04-12 20:59 ` redi at gcc dot gnu.org
  2015-08-25 20:27 ` fdumont at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: redi at gcc dot gnu.org @ 2015-04-12 20:59 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to François Dumont from comment #2)
> So yes it doubles the number of comparisons which is definitely a

Well actually your patch doesn't double the number, because you only do the
reverse check when the first check returns true.

> performance hint but your patch on the other hand expect to detect an
> implementation issue on only 1 use case so it can miss many kind of wrong
> implementation on special instances.

The most common mistake I want this to detect is simply trying to define
something equivalent to operator<= instead of operator< (see PR 59391 that I
linked to) and that will be detected for every value, so you only need to check
the first one. i.e. I want to check for irreflexivity.

Your patch checks for antisymmetry instead, which is also required for a strict
weak order, but is a different property.

Checking for antisymmetry is necessary to check broken orders like this:

bool cmp(const pair<int,int>& l, const pair<int,int>& r)
{ return l.first < r.first || l.second < r.second; }


Your patch also only works for C++11, but there's no reason this shouldn't work
for C++03 too. Which algorithms benefit from handling heterogeneous types in
these checks?
>From gcc-bugs-return-483452-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Sun Apr 12 21:03:13 2015
Return-Path: <gcc-bugs-return-483452-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 129702 invoked by alias); 12 Apr 2015 21:03:13 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 129635 invoked by uid 48); 12 Apr 2015 21:03:09 -0000
From: "redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
Date: Sun, 12 Apr 2015 21:03:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: libstdc++
X-Bugzilla-Version: 4.9.0
X-Bugzilla-Keywords:
X-Bugzilla-Severity: enhancement
X-Bugzilla-Who: redi at gcc dot gnu.org
X-Bugzilla-Status: NEW
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: unassigned at gcc dot gnu.org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-60519-4-1lXRBELHDn@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-60519-4@http.gcc.gnu.org/bugzilla/>
References: <bug-60519-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-04/txt/msg01004.txt.bz2
Content-length: 473

https://gcc.gnu.org/bugzilla/show_bug.cgi?id`519

--- Comment #4 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Jonathan Wakely from comment #3)
> Your patch checks for antisymmetry instead, which is also required for a
> strict weak order, but is a different property.

Maybe we want both, because the irreflexivity check can be done very cheaply,
so is suitable for the Debug Mode Lite I've talked about, but the antisymmetry
check is more expensive.


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

* [Bug libstdc++/60519] Debug mode should check comparators for irreflexivity
  2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
                   ` (3 preceding siblings ...)
  2015-04-12 20:59 ` redi at gcc dot gnu.org
@ 2015-08-25 20:27 ` fdumont at gcc dot gnu.org
  4 siblings, 0 replies; 6+ messages in thread
From: fdumont at gcc dot gnu.org @ 2015-08-25 20:27 UTC (permalink / raw)
  To: gcc-bugs

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

--- Comment #5 from François Dumont <fdumont at gcc dot gnu.org> ---
Author: fdumont
Date: Tue Aug 25 20:27:03 2015
New Revision: 227189

URL: https://gcc.gnu.org/viewcvs?rev=227189&root=gcc&view=rev
Log:
2015-08-24  François Dumont  <fdumont@gcc.gnu.org>

        PR libstdc++/60519
        * include/debug/formatter.h
(_Debug_msg_id::__msg_irreflexive_ordering):
        New enum entry.
        * include/debug/functions.h (_Irreflexive_checker): New.
        (__is_irreflexive, __is_irreflexive_pred): New.
        * include/debug/macros.h
        (__glibcxx_check_irreflexive, __glibcxx_check_irreflexive_pred): New
        macros.
        (__glibcxx_check_irreflexive2, __glibcxx_check_irreflexive_pred2): New
        macros limited to post-C++11 mode.
        * include/debug/debug.h
        (__glibcxx_requires_irreflexive, __glibcxx_requires_irreflexive_pred):
        New macros, use latter.
        (__glibcxx_requires_irreflexive2,
__glibcxx_requires_irreflexive_pred2):
        Likewise.
        * include/bits/stl_algo.h
        (partial_sort_copy): Add irreflexive debug check.
        (partial_sort_copy): Likewise.
        (lower_bound): Likewise.
        (upper_bound): Likewise.
        (equal_range): Likewise.
        (binary_search): Likewise.
        (inplace_merge): Likewise.
        (includes): Likewise.
        (next_permutation): Likewise.
        (prev_permutation): Likewise.
        (is_sorted_until): Likewise.
        (minmax_element): Likewise.
        (partial_sort): Likewise.
        (nth_element): Likewise.
        (sort): Likewise.
        (merge): Likewise.
        (stable_sort): Likewise.
        (set_union): Likewise.
        (set_intersection): Likewise.
        (set_difference): Likewise.
        (set_symmetric_difference): Likewise.
        (min_element): Likewise.
        (max_element): Likewise.
        * include/bits/stl_algobase.h
        (lower_bound): Likewise.
        (lexicographical_compare): Likewise.
        * include/bits/stl_heap.h
        (push_heap): Likewise.
        (pop_heap): Likewise.
        (make_heap): Likewise.
        (sort_heap): Likewise.
        (is_heap_until): Likewise.
        * testsuite/25_algorithms/lexicographical_compare/debug/
        irreflexive_neg.cc: New.
        * testsuite/25_algorithms/lower_bound/debug/irreflexive.cc: New.
        * testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc:
        New.

Added:
    trunk/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/
   
trunk/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/debug/irreflexive_neg.cc
    trunk/libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/
    trunk/libstdc++-v3/testsuite/25_algorithms/lower_bound/debug/irreflexive.cc
    trunk/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/
   
trunk/libstdc++-v3/testsuite/25_algorithms/partial_sort_copy/debug/irreflexive_neg.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/stl_algo.h
    trunk/libstdc++-v3/include/bits/stl_algobase.h
    trunk/libstdc++-v3/include/bits/stl_heap.h
    trunk/libstdc++-v3/include/debug/debug.h
    trunk/libstdc++-v3/include/debug/formatter.h
    trunk/libstdc++-v3/include/debug/functions.h
    trunk/libstdc++-v3/include/debug/macros.h
    trunk/libstdc++-v3/src/c++11/debug.cc
>From gcc-bugs-return-495647-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org Tue Aug 25 20:29:35 2015
Return-Path: <gcc-bugs-return-495647-listarch-gcc-bugs=gcc.gnu.org@gcc.gnu.org>
Delivered-To: listarch-gcc-bugs@gcc.gnu.org
Received: (qmail 11275 invoked by alias); 25 Aug 2015 20:29:35 -0000
Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Id: <gcc-bugs.gcc.gnu.org>
List-Archive: <http://gcc.gnu.org/ml/gcc-bugs/>
List-Post: <mailto:gcc-bugs@gcc.gnu.org>
List-Help: <mailto:gcc-bugs-help@gcc.gnu.org>
Sender: gcc-bugs-owner@gcc.gnu.org
Delivered-To: mailing list gcc-bugs@gcc.gnu.org
Received: (qmail 11225 invoked by uid 55); 25 Aug 2015 20:29:31 -0000
From: "mpolacek at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>
To: gcc-bugs@gcc.gnu.org
Subject: [Bug middle-end/67330] ICE handling weak attributes
Date: Tue, 25 Aug 2015 20:29:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: gcc
X-Bugzilla-Component: middle-end
X-Bugzilla-Version: 6.0
X-Bugzilla-Keywords: ice-on-invalid-code
X-Bugzilla-Severity: normal
X-Bugzilla-Who: mpolacek at gcc dot gnu.org
X-Bugzilla-Status: ASSIGNED
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P3
X-Bugzilla-Assigned-To: mpolacek at gcc dot gnu.org
X-Bugzilla-Target-Milestone: 6.0
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields:
Message-ID: <bug-67330-4-7UvF0MzmkU@http.gcc.gnu.org/bugzilla/>
In-Reply-To: <bug-67330-4@http.gcc.gnu.org/bugzilla/>
References: <bug-67330-4@http.gcc.gnu.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://gcc.gnu.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-08/txt/msg01789.txt.bz2
Content-length: 718

https://gcc.gnu.org/bugzilla/show_bug.cgi?idg330

--- Comment #6 from Marek Polacek <mpolacek at gcc dot gnu.org> ---
Author: mpolacek
Date: Tue Aug 25 20:28:59 2015
New Revision: 227190

URL: https://gcc.gnu.org/viewcvs?rev"7190&root=gcc&view=rev
Log:
        PR middle-end/67330
        * varasm.c (declare_weak): Return after giving an error.

        * c-common.c (handle_weak_attribute): Don't check whether the
        visibility can be changed here.

        * gcc.dg/weak/weak-18.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/weak/weak-18.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/c-family/ChangeLog
    trunk/gcc/c-family/c-common.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/varasm.c


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

end of thread, other threads:[~2015-08-25 20:27 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-03-13 20:03 [Bug libstdc++/60519] New: Debug mode should check comparators for irreflexivity redi at gcc dot gnu.org
2014-10-13 15:02 ` [Bug libstdc++/60519] " redi at gcc dot gnu.org
2015-04-11 19:09 ` redi at gcc dot gnu.org
2015-04-12 19:57 ` fdumont at gcc dot gnu.org
2015-04-12 20:59 ` redi at gcc dot gnu.org
2015-08-25 20:27 ` fdumont 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).