On Wed, Apr 26, 2023 at 7:09 PM Derrick Stolee <derrickstolee@xxxxxxxxxx> wrote:
>
> On 4/26/2023 12:05 AM, Han Xin wrote:
> > Fixed the following problems:
>
> This might be a good time to reference the change from recursive to
> iterative:
>
> The mark_common() method in negotiator/skipping.c was converted
> from recursive to iterative in 4654134976f (negotiator/skipping:
> avoid stack overflow, 2022-10-25), but there is some more work
> to do:
>
Make sense.
> > while ((c = prio_queue_get(&queue))) {
> > struct commit_list *p;
> > if (c->object.flags & COMMON)
> > - return;
> > + continue;
> > c->object.flags |= COMMON;
> > if (!(c->object.flags & POPPED))
> > data->non_common_revs--;
> >
> > if (!c->object.parsed)
> > - return;
> > + continue;
> > for (p = c->parents; p; p = p->next) {
> > - if (p->item->object.flags & SEEN)
> > + if (p->item->object.flags & SEEN || p->item->object.flags & COMMON)
> > prio_queue_put(&queue, p->item);
>
> This is the incorrect check for the COMMON bit, because it is
> a positive check (we add the common bit after we pop a commit
> from the queue) _and_ because we could add a commit multiple
> times before it is first popped and that bit is added.
>
Yes, I introduced a silly thing.
> Instead, we need
>
> if ((p->item->object.flags & SEEN) &&
> !(p->item->object.flags & COMMON)) {
> p->item->object.flags |= COMMON;
> prio_queue_put(&queue, p->item);
> }
>
> and at the start of the loop we need to add the COMMON bit to
> the starting commit. We also need to remove this bit from the
> main section of the loop:
>
> if (c->object.flags & COMMON)
> continue;
> c->object.flags |= COMMON;
>
> because it does nothing if the COMMON bit is added before
> being added to the queue.
>
Make sense.
And with this, we should do return before loop:
if (seen_commit->object.flags & COMMON)
return;
prio_queue_put(&queue, seen_commit);
while ((c = prio_queue_get(&queue))) {
> I'm very suspicious that this change did not trigger a test
> failure, since the behavior is quite different from the previous
> version. Of course, the recursive-to-iterative change was first
> to change the behavior, so I'm not surprised that it isn't caught
> by tests. What kind of tests can we introduce to harden our
> coverage here?
>
With "p->item->object.flags & COMMON", it takes more meaningless
walking, but doesn't seem to introduce any errors. I haven't found any
good way to avoid similar problems.
Thanks
-Han Xin
