Re: [RFH] revision limiting sometimes ignored

Junio C Hamano [off-list ref] writes:

Once we find the set of bottom commits in "newlist", we would
need to prove that none of them can be reached from any of the
negative commits still in "list".  We can do this traversal
using two bits from flags, exactly like commit.c::merge_bases()

    for each bottom commit B {
      L = empty list
      B.flags |= PARENT2
      L.append(B)
      for each negative commit C in "list from limit_list()"
          C.flags |= PARENT1
          L.append(C)
      while (L) {
          C = shift L;
          flag = C.flags & (PARENT1|PARENT2);
            if (flag ==  (PARENT1|PARENT2))
              continue; /* common */
          for each parent P of commit C:
              pflag = P.flags & (PARENT1|PARENT2);
              if (pflag == flag)
                    continue;
              P.flags |= flags;
                L.append(P)
      }
      if (B.flags & PARENT1)
          we still need to traverse -- everybody_uninteresting()
          in limit_list() main loop was not enough!
    }

Actually when we do this traversal, we can mark the positive
commits on "newlist" as negative when it is painted with
PARENT1.  I was assuming that as soon as we find that we are in
problematic history with this procedure we exit the whole thing
and resume to limit_list(), but we may be able to use this as
the postprocessing step to clean-up the result.  I just need to
prove that this postprocessing step will smudge all the "falsely
positive but in reality negative" ones...