Re: [External] Re: [PATCH v2 2/2] negotiator/skipping: fix some problems in mark_common()

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

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

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

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