From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B77F9CD4859 for ; Fri, 22 Sep 2023 19:27:12 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S233435AbjIVT1Q convert rfc822-to-8bit (ORCPT ); Fri, 22 Sep 2023 15:27:16 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:38090 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229590AbjIVT1Q (ORCPT ); Fri, 22 Sep 2023 15:27:16 -0400 Received: from secure.elehost.com (secure.elehost.com [185.209.179.11]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 8C0DBA3 for ; Fri, 22 Sep 2023 12:27:10 -0700 (PDT) X-Virus-Scanned: Debian amavisd-new at secure.elehost.com Received: from Mazikeen (cpebc4dfb928313-cmbc4dfb928310.cpe.net.cable.rogers.com [99.228.251.108] (may be forged)) (authenticated bits=0) by secure.elehost.com (8.15.2/8.15.2/Debian-22ubuntu3) with ESMTPSA id 38MJOPZT1919026 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Fri, 22 Sep 2023 19:24:25 GMT Reply-To: From: To: "'Ben Boeckel'" Cc: "'Junio C Hamano'" , References: <02d701d9ed6f$abcb4b00$0361e100$@nexbridge.com> <02e701d9ed78$436b3c60$ca41b520$@nexbridge.com> <032d01d9ed80$5e569670$1b03c350$@nexbridge.com> <033201d9ed85$991c6af0$cb5540d0$@nexbridge.com> In-Reply-To: Subject: RE: [BUG] `git describe` doesn't traverse the graph in topological order Date: Fri, 22 Sep 2023 15:27:01 -0400 Organization: Nexbridge Inc. Message-ID: <033c01d9ed8a$c6916f30$53b44d90$@nexbridge.com> MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 8BIT X-Mailer: Microsoft Outlook 16.0 Content-Language: en-ca Thread-Index: AQMniK2C5ueFGaecrAkj2WziqqcqsgIDXfPaAV8c8ysBL0/7iQKiZtYXAnm84MABE+XlegDThaDjAeynnB4CTDNPdq0NkXJQ Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org On Friday, September 22, 2023 3:06 PM, Ben Boeckel wrote: >On Fri, Sep 22, 2023 at 14:49:58 -0400, rsbecker@nexbridge.com wrote: >> On Friday, September 22, 2023 2:44 PM, Ben Boeckel wrote: >> >Yes. It is explained that the commit date stored is only to 1 second >> >granularity. Since the commits are stored in commit-date, an equal >> >commit date ends up "twisting" the history and traversing some ancestors of >commits before the commits themsevles. >> >This loses the "seen" bit tracking that is done and ends up labeling >> >way more commits as "not part of" ancestors. By sleeping for a >> >second, the commit dates can be totally ordered reliably. >> >> This is going to be awkward to resolve as time_t only resolves >> (portably) to 1 second intervals. I still would prefer the resolution >> to be path-based rather than time-based. > >I certainly agree, but I'm not sure of the best way of doing that. Do we create/load a >commit graph and use that for resolving insertion order into the commit heap? I actually thought it worked that way. This may end up in a bigger change than fixing the issue because --first-parent does not appear to be sufficient to resolve the correct tag from your graph. My thought on using multiple commitish values to do that may help, but implementing that could lead to an O(n*m) scan (n=max commit tree width, m=depth to tag), plus a commitish hash lookup.