Subject: Re: jk/tag-contains: stalled

From: Jeff King <[email-masked]>
Date: Thu, 5 Aug 2010 15:06:54 -0400

On Thu, Aug 05, 2010 at 11:47:09AM -0700, Junio C Hamano wrote:

> > The only bad log message should be the final one, which should be
> > dropped anyway. I would recommend just merging the first two for now,
> > and Ted can tweak his core.clockskew manually.
> 
> After re-reviewing the one that is queued, the use of TMP_MARK smelled
> somewhat bad to me.  It is named TMP_ exactly because it is meant to be
> used in a closed callpath---you can use it but you are supposed to clean
> it before you return the control to the caller, so that the caller can
> rely on TMP_MARK absent from any objects.
> 
> Use of UNINTERESTING is similarly not kosher if this were to be used in
> larger context outside of "do 'tags --contains' and exit".  You noted
> these two points in your original RFC patch.

Oops, thanks, I had forgotten that the marks needed to be addressed.
Should I be introducing new flags? We have 27 flag bits, but I would
hate to waste 2 of them.

> Besides, "contains()" is too generic a name to live in commit.h.

I agree it's a pretty generic name. I was trying to make this as generic
as possible, at least within the domain of commits, so it could be a
faster replacement for calls to is_descendant_of. Maybe commit_contains?

> My gut feeling is that it is probably Ok if contains() and its
> recursive helper are moved to builtin/tag.c and are made static, to
> make it clear that this should not be reused outside the current
> context as a generic "contains" function.  It would probably help to
> have a comment at the end of list_tags() to say that TMP_MARK _ought_
> to be cleaned before leaving the function but we don't do that because
> we know it is the last function in the callchain before we exit.

But my intent was to have a generic contains function. I was planning on
applying this to "git branch --contains", as well, but my initial
approach wasn't really any faster than the current code (probably
because the number of branches tends to be small compared to the number
of tags).

In an ideal object-oriented world, the interface would be:

  void contains_init(struct contains_context *c,
                     struct commit_list *needles);
  void contains_check(struct contains_context *c, struct commit *haystack);
  void contains_free(struct contains_context *c);

But for memory use reasons, we don't get our own private copy of each
commit. We can drop the "init" and have a "free" or "clear" which clears
marks on the global commit objects. But you also _must_ use the same
needle list for each contains check, or you will get bogus results
(since the marks are essentially partial cached answers).

I guess we could do:

  static struct commit_list *contains_needles;

  void contains_init(struct commit_list *needles)
  {
          if (contains_needles)
                  die("BUG: somebody else is already checking contains!");
          copy_commit_list(&contains_needles, needles);
  }

  void contains_check(struct commit *haystack)
  {
     /* like contains, but check against our static contains_needles */
  }

  void contains_clear(struct contains_context *c)
  {
          /* free contains_needles list, set it to NULL */
          /* clear commit marks */
  }

> By the way, I wonder why pop_most_recent_commit() with a commit_list,
> which is the usual revision traversal ingredient for doing something like
> this, was not used in the patch, though.  Is it because depth-first was
> necessary?

Yes, it is because of the depth-first nature. The intent is to mark
whole sections of the subgraph as "does not contain". If you can think
of a clever way around that, I would be interested to hear it. The fact
that it is a DFS is why we can possibly perform worse than the current
code (we might follow the wrong branch of a merge all the way down to
the root before realizing the commit in question is on the other side).

-Peff