9front - general discussion about 9front
 help / color / mirror / Atom feed
From: ori@eigenstate.org
To: 9front@9front.org
Subject: Re: [9front] git lca bug
Date: Sun, 06 Mar 2022 13:33:03 -0500	[thread overview]
Message-ID: <D305075FA2C3AB4586D4CB736371991A@eigenstate.org> (raw)
In-Reply-To: <2XMT5L9VLBDA3.2ZSPGPD38FJJR@mforney.org>

Quoth Michael Forney <mforney@mforney.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.

yes, though 

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

We may need to resplit the code, if we do that-- it's
also used for pushing and pulling, where the goal is
somewhat different; it wants to find all nodes that
are in one graph but not the other, so we can put
them into a pack file.

With the current code: In theory, we should always be
returning the node on the boundary between Keep and
Drop with the shortest number of steps from both parents.

Regardless of keep/drop, we'll need to explore more or
less the full boundary, and ideally not much more.

I think that this current approach should be more or
less correct, though possibly not 100% optimal -- there's
just a bug in the stop or selection condition.

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

In this case, torvalds git will return a list of
{c,d} as the set of ancestors. merging will be
done recursively, creating a virtual commit that
is merge(c,d) -- and if that creates a cross
branch, then the merge will be repeated.

for us, I'd be happy if we pick an arbitrary parent.

Though, in this case, thinking about it, we can
return *all* minimums in the reachability boundary
if we want to do that.

(I don't think we want to)

      reply	other threads:[~2022-03-06 18:40 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
2022-03-06 18:33     ` ori [this message]

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:

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

  git send-email \
    --in-reply-to=D305075FA2C3AB4586D4CB736371991A@eigenstate.org \
    --to=ori@eigenstate.org \
    --cc=9front@9front.org \


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