From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 72766 invoked by alias); 11 May 2018 12:03:54 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 72756 invoked by uid 89); 11 May 2018 12:03:53 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-2.3 required=5.0 tests=AWL,BAYES_00,SPF_PASS autolearn=ham version=3.3.2 spammy=Hx-languages-length:1148, contract X-HELO: smtp.ispras.ru Received: from bran.ispras.ru (HELO smtp.ispras.ru) (83.149.199.196) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 11 May 2018 12:03:52 +0000 Received: from monopod.intra.ispras.ru (monopod.intra.ispras.ru [10.10.3.121]) by smtp.ispras.ru (Postfix) with ESMTP id E0A01203CC; Fri, 11 May 2018 15:03:49 +0300 (MSK) Date: Fri, 11 May 2018 12:16:00 -0000 From: Alexander Monakov To: Segher Boessenkool cc: Richard Biener , gcc-patches@gcc.gnu.org Subject: Re: [PATCH 0/2] Introduce gcc_qsort In-Reply-To: <20180511111732.GD17342@gate.crashing.org> Message-ID: References: <20180510155641.2950-1-amonakov@ispras.ru> <82E69EBE-92EB-41AB-8E1B-ADBD65516D73@gmail.com> <20180511102905.GC17342@gate.crashing.org> <20180511111732.GD17342@gate.crashing.org> User-Agent: Alpine 2.20.13 (LNX 116 2015-12-14) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII X-SW-Source: 2018-05/txt/msg00551.txt.bz2 On Fri, 11 May 2018, Segher Boessenkool wrote: > > In general such address-based comparisons steps are invalid; they lack > > anti-reflexivity. So comparators are not actually allowed to do that. > > I don't know what you mean here? Every comparator is required to be > *reflexive*! Subtracting two pointers to elements of the same array gives > a perfectly fine total order as far as I see (it is the same as the > difference between the array indices of those elements). I meant "anti-commutativity"; sorry about the mixup. Such strategy does not give a valid total order because the order changes while in-progress sorting reorders elements: suppose you have elements A and B such that A precedes B and compare A < B via address test. At some point, the sort routine may swap A with some unrelated element C, moving A past B. Now B < A. This is a contradiction. > In any case, every qsort call that is converted to one with this weaker > contract will need to be checked. Or we can wait for bug reports ;-) I think such comparators have a good chance of failing existing qsort_chk validation. Alexander