9front - general discussion about 9front
 help / color / mirror / Atom feed
From: Michael Forney <mforney@mforney.org>
To: 9front@9front.org
Subject: Re: [9front] git lca bug
Date: Sat, 05 Mar 2022 21:21:56 -0800	[thread overview]
Message-ID: <2XMT5L9VLBDA3.2ZSPGPD38FJJR@mforney.org> (raw)
In-Reply-To: <DFB090A5862CEA80EBC96B14BD54368D@eigenstate.org>

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
    |
   ...

  reply	other threads:[~2022-03-06  5:32 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-03-05 19:32 Michael Forney
2022-03-06  3:44 ` ori
2022-03-06  5:21   ` Michael Forney [this message]
2022-03-06 18:33     ` ori

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=2XMT5L9VLBDA3.2ZSPGPD38FJJR@mforney.org \
    --to=mforney@mforney.org \
    --cc=9front@9front.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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 NNTP newsgroup(s).