From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org
X-Spam-Level: 
X-Spam-Status: No, score=-0.1 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
	DKIM_VALID_AU,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no
	version=3.4.4
Received: (qmail 2946 invoked from network); 6 Mar 2022 05:32:52 -0000
Received: from 4ess.inri.net (216.126.196.42)
  by inbox.vuxu.org with ESMTPUTF8; 6 Mar 2022 05:32:52 -0000
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
Received: from mail-qv1-f41.google.com ([209.85.219.41]) by 4ess; Sun Mar  6 00:27:53 -0500 2022
Received: by mail-qv1-f41.google.com with SMTP id eq14so3821623qvb.3
        for <9front@9front.org>; Sat, 05 Mar 2022 21:27:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=mforney.org; s=google;
        h=date:to:subject:from:references:in-reply-to:message-id:user-agent;
        bh=7dgil9Tjr8vmPmz84K45UAzsxTZTpnVyUGDxpbaB+R8=;
        b=YxiUQPjSHLbNOZquo2Q8MBxPJXBFrDYb89tIUAjF5jGm28HbdADqDgYNfJUIlT34b9
         IoAmlIcxCwdJ8oT2uNyKLgLCMeGZuwo96/dJPVJG3CXrlHe6blybwM4k3amxxdH0Ybj4
         vgcQ49FfzelA1aPoe4Tww3oURT3RpvgRzdX4cmKFHpohofgNLMbhcpjYmn8WKenYYR0B
         CUh8EkwcH+NA6TilcIM6vDYnKfzsJrAWFBLEOrFwDsZ5I+yBAcpDwMcBP+IjZEjz8UPl
         efOqo86WQiIwNeFWlCJ/Uewb3cbbPmGfQQW50iLnOM6ZAtaFLxHy91D07KhwYC2Hf8aR
         5q4Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20210112;
        h=x-gm-message-state:date:to:subject:from:references:in-reply-to
         :message-id:user-agent;
        bh=7dgil9Tjr8vmPmz84K45UAzsxTZTpnVyUGDxpbaB+R8=;
        b=P8/gGhIGHq7s0OoxFN5x4SmQtCyV1JWq+kFEryd4ngCEJ6jWGAv3Bdkk4hBN2bt3YP
         Z/GMWgkla+LV01BIacQYpIXD+ps9Ljkj460eSVP9t2gR4SN5V2c7B47MKn9og78i8o0W
         cB2JBxlRMX3d/D4EPNbMXyV+BuBE1sQqcINO3myNOxw6AKeZfJ1cAgmoLi9wxbYpT+9G
         dkWQWTxQ3dVy5vtBkrEH/faD+KUeLU5m+Srs20jVN8geSvEC0Hce4cytryRhZEmG/v8g
         loaNbz7h5fuAB2WmqTMRBu3aM+M/CH10V5ULHtPbpdQaMIjjnrSY6idp8J4Ccyqqg9c5
         xQuw==
X-Gm-Message-State: AOAM532wa7hjL5GEZfUVkWMGVKgBadwQ4/nJSqyomHHW5dGuvz8eCcOt
	3gcqe5kbFKabCRBz9U9NN6SkmO8exLfGrucssbU=
X-Google-Smtp-Source: ABdhPJwoEDLW6unEELkY0QLilAxtfmyCoYG/mLpPkUFyRMeuyvJaxcuAa3V3QGFsoP0i6lwrbsHD5Q==
X-Received: by 2002:a17:902:720a:b0:151:d7d7:6ac0 with SMTP id ba10-20020a170902720a00b00151d7d76ac0mr3818308plb.128.1646544118964;
        Sat, 05 Mar 2022 21:21:58 -0800 (PST)
Return-Path: <mforney@mforney.org>
Received: from localhost ([98.45.152.168])
        by smtp.gmail.com with ESMTPSA id r15-20020a63ce4f000000b00341c40f913esm8146689pgi.87.2022.03.05.21.21.57
        for <9front@9front.org>
        (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256);
        Sat, 05 Mar 2022 21:21:58 -0800 (PST)
Date: Sat, 05 Mar 2022 21:21:56 -0800
To: 9front@9front.org
From: Michael Forney <mforney@mforney.org>
References: <DFB090A5862CEA80EBC96B14BD54368D@eigenstate.org>
In-Reply-To: <DFB090A5862CEA80EBC96B14BD54368D@eigenstate.org>
Message-Id: <2XMT5L9VLBDA3.2ZSPGPD38FJJR@mforney.org>
User-Agent: mblaze/1.2
List-ID: <9front.9front.org>
List-Help: <http://lists.9front.org>
X-Glyph: ➈
X-Bullshit: flexible SVG realtime-java cloud browser rich-client-based control 
Subject: Re: [9front] git lca bug
Reply-To: 9front@9front.org
Precedence: bulk

ori@eigenstate.org wrote:
> How do you define 'lowest' in this case?  especially
> without walking the whole graph from the initial
> commit, which is very slow in large repos?

Yeah, it's a bit tricky, but I think it's fair to say that if A is
reachable through parent pointers from B, then B is lower than A
(but the converse is not necessarily true).

Interestingly, I found that when I do `B A @` instead of `A B @`,
it *does* end up walking the whole graph to the initial commit.
What happens here is that the Drop painting finds I first, and then
when we get to I through Keep painting. I is recorded as the best,
but then the loop continues (`if(... || ncolor == Drop) continue;`).
Then we keep painting the rest of the graph as Drop, finally returning
I when we run out of nodes.

> Not yet. Tweaking repainting to sum the weight when
> colors meet seems like it may fix it, but I haven't
> thought it through yet.

I also haven't thought this through fully, but here are some thoughts
I had:
- I don't think any nodes traversed by repaint() should be considered
  as candidates for the LCA. repaint() traverses starting at a
  common ancestor, so any nodes we traverse will be higher
  on the graph.
- Instead of repaint() painting nodes from Keep to Drop, maybe there
  should be a third color (Skip?). It could take a starting point
  of either color, repainting everything it finds as Skip, stopping
  when it repaints Blank nodes. If this happens to find our previous
  best common ancestor, then we use the repaint starting point as
  the new best.
- Then, when paint() pops a node painted Skip, it just skips it and
  continues in the loop, since the node was an ancestor of a common
  ancestor.
- paint() should be symmetric in its arguments. It can continue
  if e.color == ncolor, paint it if ncolor == Blank, and repaint
  to Skip otherwise, potentially choosing a new common ancestor.

I'll try those changes in a bit to see if that approach is promising.
I *think* it should at least guarantee that the node it returns is
not reachable from any other common ancestor of A and B.

There are still a few edge cases like the following that I'm not
sure how it would handle, but I don't know how often those come up
in practice.

A   B
|\ /|
| \ |
|/ \|
C   D
 \  |
  E |
   \|
    F
    |
   ...