branch & tag: Add a --no-contains option

More notes about this patch:

* I'm not really happy with the "special attention" documentation example in git-branch.txt, but it follows logically from the description for --contains just above it which I think is overly specific as well. IMO that entire NOTES section in git-branch.txt could just be removed.

* I'm adding a --without option as an alias for --no-contains for consistency with --with and --contains. Since we don't even document --with anymore (or test it) perhaps we shouldn't be adding --without.

Change the branch & tag commands to have a --no-contains option in addition to their longstanding --contains options.

The use-case I have for this is mainly to find the last-good rollout tag given a known-bad <commit>. Right given a hypothetically bad commit v2.10.1-3-gcf5c7253e0 now you can find that with this hacky one-liner:

    (./git tag -l 'v[0-9]*'; ./git tag -l 'v[0-9]*' --contains v2.10.1-3-gcf5c7253e0)|sort|uniq -c|grep -E '^ *1 '|awk '{print $2}'

But with the --no-contains option you can now get the exact same output with:

    ./git tag -l 'v[0-9]*' --no-contains v2.10.1-3-gcf5c7253e0 | sort

Once I'd implemented this for "tag" it was easy enough to add it for "branch". I haven't added it to "for-each-ref" but that would be trivial if anyone cares, but that use-case would be even more obscure than adding it to "branch", so I haven't bothered.

The "describe" command also has a --contains option, but its semantics are unrelated to what tag/branch/for-each-ref use --contains for, and I don't see how a --no-contains option for it would make any sense.

t/t7004-tag.sh +2 -0

@@ -1708,8 +1782,91 @@ run_with_limited_stack () {
 
 test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
 
+# These are all the tags we've created above
+cat >expect.no-contains <<EOF

[...80 tags...]
+EOF

Quoted 8 lines · Ævar Arnfjörð Bjarmason

Change the branch & tag commands to have a --no-contains option in addition to their longstanding --contains options.

The use-case I have for this is mainly to find the last-good rollout tag given a known-bad <commit>. Right given a hypothetically bad commit v2.10.1-3-gcf5c7253e0 now you can find that with this hacky one-liner:

Quoted 6 lines

    (./git tag -l 'v[0-9]*'; ./git tag -l 'v[0-9]*' --contains v2.10.1-3-gcf5c7253e0)|sort|uniq -c|grep -E '^ *1 '|awk '{print $2}'

But with the --no-contains option you can now get the exact same output with:

    ./git tag -l 'v[0-9]*' --no-contains v2.10.1-3-gcf5c7253e0 | sort

I think that's a good goal.

I'm not sure about the name. I would have expected "--no-contains" to reset the list of "--contains" commits to the empty set. That's an option convention we've been slowly moving towards (e.g., with OPT_STRING_LIST).

What you've added here _does_ match "--no-merged", though. I'm not sure of the best way forward. At the very least, "--no-contains" is currently an error, so you would not be changing existing behavior.

Quoted 4 lines

Once I'd implemented this for "tag" it was easy enough to add it for "branch". I haven't added it to "for-each-ref" but that would be trivial if anyone cares, but that use-case would be even more obscure than adding it to "branch", so I haven't bothered.

I'd prefer to have it consistently in all three. We should be able to tell people to use for-each-ref in their scripts, and that's harder if it is missing features.

Quoted 3 lines

The "describe" command also has a --contains option, but its semantics are unrelated to what tag/branch/for-each-ref use --contains for, and I don't see how a --no-contains option for it would make any sense.

Yeah, I think that feature is orthogonal.

ref-filter.c static enum contains_result contains_tag_algo(struct commit *candidate, · line 1580

Quoted 10 lines

ref-filter.c +4 -3

-static int commit_contains(struct ref_filter *filter, struct commit *commit)
+static int commit_contains(struct ref_filter *filter, struct commit *commit, const int with_commit)
 {
+     struct commit_list *tmp = with_commit ? filter->with_commit : filter->no_commit;
      if (filter->with_commit_tag_algo)
-             return contains_tag_algo(commit, filter->with_commit);
-     return is_descendant_of(commit, filter->with_commit);
+             return contains_tag_algo(commit, tmp);
+     return is_descendant_of(commit, tmp);
 }

Perhaps it would be simpler if the caller just passed the right commit_list rather than a flag. We unfortunately do still need to pass the "filter" (for the algorithm field), but the caller is then:

if (filter->with_commit &&

      !commit_contains(filter, filter->with_commit, commit))
          return 0;
  if (filter->no_commit &&
      commit_contains(filter, filter->no_commit, commit))
          return 0;

which avoids the 0/1 flag whose meaning is not immediately apparent at the callsite. One day we can hopefully unify the two algorithms and ditch the extra filter parameter.

I almost suggested that there simply be an option to invert the match (like --invert-contains or something). But what you have here is more flexible, if somebody ever wanted to do:

  git tag --contains X --no-contains Y

Quoted 4 lines

t/t7004-tag.sh +0 -0

@@ -1708,8 +1782,91 @@ run_with_limited_stack () {
 
 test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
 

Quoted 4 lines

t/t7004-tag.sh +2 -0

+# These are all the tags we've created above
+cat >expect.no-contains <<EOF

[...80 tags...]
+EOF

That's a lot of tags, and I'd worry it makes the test a little brittle. Can we limit the set of tags with a name-match? It shouldn't affect the purpose of the test (the deep stack comes from traversing the commits, not the number of tags).

Quoted 5 lines

I almost suggested that there simply be an option to invert the match (like --invert-contains or something). But what you have here is more flexible, if somebody ever wanted to do:

  git tag --contains X --no-contains Y

Yeah that's really useful. E.g. this shows the branches I branched off (or have locally) from 2.6..2.8:

    $ ./git branch --contains v2.6.0 --no-contains v2.8.0
      avar/monkeypatch-untracked-cache-disabled
      avar/uc-notifs21
      dturner/pclouds-watchman-noshm

But I'd expect this to show all the tags between the two:

    $ ./git tag --contains v2.6.0 --no-contains v2.8.0
    $

But it just returns an empty list. Manually disabling the contains_tag_algo() path (i.e. effectively locally reverting your ffc4b8012d) makes it "work", but of course it's much slower now. I haven't dug into why it's not working yet.

Also I wonder if this should be an error:

    $ ./git [tag|branch|for-each-ref] --contains A --no-contains A

I.e. when you give the same argument to both, this can never return anything for obvious reasons.

Quoted 6 lines · Ævar Arnfjörð Bjarmason

Quoted 5 lines

I almost suggested that there simply be an option to invert the match (like --invert-contains or something). But what you have here is more flexible, if somebody ever wanted to do:

  git tag --contains X --no-contains Y

Quoted 7 lines

Yeah that's really useful. E.g. this shows the branches I branched off (or have locally) from 2.6..2.8:

    $ ./git branch --contains v2.6.0 --no-contains v2.8.0
      avar/monkeypatch-untracked-cache-disabled
      avar/uc-notifs21
      dturner/pclouds-watchman-noshm

Oh, that's a clever application.

Quoted 5 lines

But I'd expect this to show all the tags between the two:

    $ ./git tag --contains v2.6.0 --no-contains v2.8.0
    $

Quoted 4 lines

But it just returns an empty list. Manually disabling the contains_tag_algo() path (i.e. effectively locally reverting your ffc4b8012d) makes it "work", but of course it's much slower now. I haven't dug into why it's not working yet.

I'm almost certain this is because the contains_tag_algo one doesn't clean up the flag bits it sets on the commit objects. So running it twice in the same process is going to give you nonsense results.

Coincidentally, I've been looking into resurrecting the cleaner approach that I sent long ago:

http://public-inbox.org/git/[email protected]/

But it's sufficiently complex that it's probably worth fixing the existing algorithm to clean up its bits in the meantime.

Quoted 2 lines

Also I wonder if this should be an error:

Quoted 4 lines

    $ ./git [tag|branch|for-each-ref] --contains A --no-contains A

I.e. when you give the same argument to both, this can never return anything for obvious reasons.

It's clearly nonsense, but I don't think there's any need for it to be an error. GIGO.

Quoted 3 lines

I'm almost certain this is because the contains_tag_algo one doesn't clean up the flag bits it sets on the commit objects. So running it twice in the same process is going to give you nonsense results.

Yeah indeed.

I tried to hack something up to avoid this, but the lookup_commit_reference_gently() we call will return the same object.parent pointer for two invocations, i.e. the underlying {commit,object}.c API has a cache of objects it returns, couldn't find some way to quickly make it burst that cache.

The other approach of making contains_tag_algo() itself detect that it's been called before (or us passing a flag) and going around setting commit.object.flags on everything to 0 seemed even more brittle, particularly since I think between filter->with_commit & filter->no_commit we might end up visiting different commits, so it's not easy to just clear it.

I'm happy to hack on it given some pointers, will visit it again, but for now unless I'm missing something obvious / you can point out some way to hack this up I'll just submit v2 with the combination of --contains & --no-contains dying with a TODO message.

The patch without that functionality is still really useful, and we can implement that later.

Looking at this, I'm pretty sure that using "--contains" with "--merged" has similar problems, as they both use the UNINTERESTING bit. So even without your patch, there is a lurking bug.

[...]

ref-filter.c +0 -0

@@ -1874,6 +1886,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
                broken = 1;
        filter->kind = type & FILTER_REFS_KIND_MASK;

Quoted 12 lines · Jeff King

[...]

ref-filter.c +3 -0

@@ -1874,6 +1886,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
                broken = 1;
        filter->kind = type & FILTER_REFS_KIND_MASK;
 
+       init_contains_cache(&ref_cbdata.contains_cache);
+
        /*  Simple per-ref filtering */
[...]
 
+       clear_contains_cache(&ref_cbdata.contains_cache);

Quoted 2 lines

        /*  Filters that need revision walking */
        if (filter->merge_commit)

Shouldn't both of those be guarded by a "if (filter->with_commit)" test?

That init/clear codepath is rather light, but it seems to me that we can avoid it entirely if filter->with_commit isn't defined. I've tested this locally and it still passes all tests.

Quoted 10 lines · Jeff King

[...]

ref-filter.c +2 -0

@@ -1874,6 +1886,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
                broken = 1;
        filter->kind = type & FILTER_REFS_KIND_MASK;
 
+       init_contains_cache(&ref_cbdata.contains_cache);
+
        /*  Simple per-ref filtering */
[...]

Quoted 4 lines

+ clear_contains_cache(&ref_cbdata.contains_cache);

        /*  Filters that need revision walking */
        if (filter->merge_commit)

Shouldn't both of those be guarded by a "if (filter->with_commit)" test?

That init/clear codepath is rather light, but it seems to me that we can avoid it entirely if filter->with_commit isn't defined. I've tested this locally and it still passes all tests.

Quoted 3 lines · Jeff King

Looking at this, I'm pretty sure that using "--contains" with "--merged" has similar problems, as they both use the UNINTERESTING bit. So even without your patch, there is a lurking bug.

I wasn't able to come up with a simple case that actually demonstrates the bug. But I feel like it has to be triggerable with the right sequence of history.

Even without that, though, I feel like moving away from this flag usage is a good cleanup. Here's a cleaned-up series. What do you think of building your patch on top?

We can do it the other way around if you prefer.

[1/4]: ref-filter: move ref_cbdata definition into ref-filter.c [2/4]: ref-filter: use contains_result enum consistently [3/4]: ref-filter: die on parse_commit errors
[4/4]: ref-filter: use separate cache for contains_tag_algo

 ref-filter.c | 70 ++++++++++++++++++++++++++++++++++++++----------------------
 ref-filter.h |  5 -----
 2 files changed, 44 insertions(+), 31 deletions(-)

-Peff

Change the tag, branch & for-each-ref commands to have a --no-contains option in addition to their longstanding --contains options.

The use-case I have for this is to find the last-good rollout tag given a known-bad <commit>. Right now, given a hypothetically bad commit v2.10.1-3-gcf5c7253e0, you can find which git version to revert to with this hacky two-liner:

    (./git tag -l 'v[0-9]*'; ./git tag -l 'v[0-9]*' --contains v2.10.1-3-gcf5c7253e0) \
        |sort|uniq -c|grep -E '^ *1 '|awk '{print $2}' | tail -n 10

But with the --no-contains option you can now get the exact same output with:

    ./git tag -l 'v[0-9]*' --no-contains v2.10.1-3-gcf5c7253e0|sort|tail -n 10

The filtering machinery is generic between the tag, branch & for-each-ref commands, so once I'd implemented it for tag it was trivial to add support for this to the other two.

I'm adding a --without option to "tag" as an alias for --no-contains for consistency with --with and --contains. Since we don't even document --with anymore (or test it). The --with option is undocumented, and possibly the only user of it is Junio[1]. But it's trivial to support, so let's do that.

Where I'm changing existing documentation lines I'm mainly word wrapping at 75 columns to be consistent with the existing style.

Most of the test changes I've made are just doing the inverse of the existing --contains tests, with this change --no-contains for tag, branch & for-each-ref is just as well tested as the existing --contains option.

This is now based on top of pu, which has Jeff King's "fix object flag pollution in "tag --contains" series.

parse-options.h +4 -5

@@ -1586,11 +1587,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 }
 
 static int commit_contains(struct ref_filter *filter, struct commit *commit,
-			   struct contains_cache *cache)
+			   struct commit_list *list, struct contains_cache *cache)
 {
 	if (filter->with_commit_tag_algo)
-		return contains_tag_algo(commit, filter->with_commit, cache) == CONTAINS_YES;
-	return is_descendant_of(commit, filter->with_commit);
+		return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
+	return is_descendant_of(commit, list);
 }
 
 /*

@@ -1780,13 +1781,17 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
 	 * obtain the commit using the 'oid' available and discard all
 	 * non-commits early. The actual filtering is done later.
 	 */
-	if (filter->merge_commit || filter->with_commit || filter->verbose) {
+	if (filter->merge_commit || filter->with_commit || filter->no_commit || filter->verbose) {
 		commit = lookup_commit_reference_gently(oid->hash, 1);
 		if (!commit)
 			return 0;
-		/* We perform the filtering for the '--contains' option */

Quoted 14 lines · Ævar Arnfjörð Bjarmason

Change the tag, branch & for-each-ref commands to have a --no-contains option in addition to their longstanding --contains options.

The use-case I have for this is to find the last-good rollout tag given a known-bad <commit>. Right now, given a hypothetically bad commit v2.10.1-3-gcf5c7253e0, you can find which git version to revert to with this hacky two-liner:

    (./git tag -l 'v[0-9]*'; ./git tag -l 'v[0-9]*' --contains v2.10.1-3-gcf5c7253e0) \
        |sort|uniq -c|grep -E '^ *1 '|awk '{print $2}' | tail -n 10

But with the --no-contains option you can now get the exact same output with:

Quoted 1 line

    ./git tag -l 'v[0-9]*' --no-contains v2.10.1-3-gcf5c7253e0|sort|tail -n 10

This command line, while it may happen to work, logically does not make much sense. Move the pattern to the end, i.e.

        git tag -l --no-contains v2.10.1-3-gcf5c7253e0 'v[0-9]*'

Also if an overlong line in an example disturbs you, do not solve it by omitting SP around pipe. If you are trying to make the result readable, pick a readable solution, e.g.

git tag -l --no-contains v2.10.1-3-gcf5c7253e0 'v[0-9]*' | sort | tail -n 10

Oh, drop ./ from ./git while at it ;-)

Quoted 3 lines

The filtering machinery is generic between the tag, branch & for-each-ref commands, so once I'd implemented it for tag it was trivial to add support for this to the other two.

Also, we tend not to say "I did this, I do that".

Because the filtering machinery is generic ..., support it for all three consistently.

Quoted 5 lines

I'm adding a --without option to "tag" as an alias for --no-contains for consistency with --with and --contains. Since we don't even document --with anymore (or test it). The --with option is undocumented, and possibly the only user of it is Junio[1]. But it's trivial to support, so let's do that.

The sentence that begins "Since we don't" is unfinished. I think it can safely removed without losing any information (the next sentence says the same thing).

Quoted 2 lines

Where I'm changing existing documentation lines I'm mainly word wrapping at 75 columns to be consistent with the existing style.

Reviewers would appreciate you refrain from doing that in the same patch. Do a minimum patch so that the review can concentrate on what got changed (i.e. contents), followed by a mechanical reflow as a follow-up, or something like that, would be much nicer to handle.

Quoted 4 lines

Most of the test changes I've made are just doing the inverse of the existing --contains tests, with this change --no-contains for tag, branch & for-each-ref is just as well tested as the existing --contains option.

Again, we tend to try our commits not about "I, my, me".

Add --no-contains tests for tag, branch and for-each-ref that mostly do the inverse of the existing tests we have for --contains.

Quoted 2 lines

This is now based on top of pu, which has Jeff King's "fix object flag pollution in "tag --contains" series.

Thanks for this note. I obviously cannot queue on top of 'pu' ;-) but will fork this topic off of the jk/ref-filter-flags-cleanup topic.

Documentation/git-for-each-ref.txt SYNOPSIS · line 14

Quoted 5 lines

'git for-each-ref' [--count=<count>] [--shell|--perl|--python|--tcl]

                 [(--sort=<key>)...] [--format=<format>] [<pattern>...]
                 [--points-at <object>] [(--merged | --no-merged) [<object>]]

Documentation/git-for-each-ref.txt +1 -1

-                [--contains [<object>]]
+                [(--contains | --no-contains) [<object>]]

THis notation makes sense. We have to have one of these but <object> at the end could be omitted (to default to HEAD). I guess the same notation can be used in the log for the other "filtering implies --list mode for 'git tag'" topic.

Documentation/git-tag.txt This option is only applicable when listing tags without annotation lines. · line 129

Quoted 3 lines

+--no-contains [<commit>]::

Documentation/git-tag.txt +2 -0

+     Only list tags which don't contain the specified commit (HEAD if
+     not specified).

Just being curious. Can we do

        for-each-ref --contains --no-contains

and have both default to HEAD? I know that would not make sense as a set operation, but I am curious what our command line parser (which is oblivious to what the command is doing) does. I am guessing that it would barf saying "--contains" needs a commit but "--no-contains" is not a commit (which is very sensible)?

Quoted 3 lines

+
--points-at <object>::
Only list tags of the given object.

This is not a new issue (and certainly not a problem caused by your patch), but unlike "--contains", this does not default to HEAD when <object> is not explicitly given? It seems a bit inconsistent to me.

builtin/branch.c int cmd_branch(int argc, const char **argv, const char *prefix) · line 624

Quoted 7 lines

builtin/branch.c +1 -1

@@ -618,7 +620,7 @@ int cmd_branch(int argc, const char **argv, const char *prefix)
      if (!delete && !rename && !edit_description && !new_upstream && !unset_upstream && argc == 0)
              list = 1;
 
-     if (filter.with_commit || filter.merge != REF_FILTER_MERGED_NONE || filter.points_at.nr)
+     if (filter.with_commit || filter.no_commit || filter.merge != REF_FILTER_MERGED_NONE || filter.points_at.nr)
              list = 1;

OK.

parse-options.h extern int parse_opt_passthru_argv(const struct option *, const char *, int); · line 264

Quoted 13 lines

parse-options.h +3 -1

index dcd8a0926c..0eac90b510 100644
@@ -258,7 +258,9 @@ extern int parse_opt_passthru_argv(const struct option *, const char *, int);
        PARSE_OPT_LASTARG_DEFAULT | flag, \
        parse_opt_commits, (intptr_t) "HEAD" \
      }
-#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h, 0)
+#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h, PARSE_OPT_NONEG)
+#define OPT_NO_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("no-contains", v, h, PARSE_OPT_NONEG)
 #define OPT_WITH(v, h) _OPT_CONTAINS_OR_WITH("with", v, h, PARSE_OPT_HIDDEN)
+#define OPT_WITHOUT(v, h) _OPT_CONTAINS_OR_WITH("without", v, h, PARSE_OPT_HIDDEN)

Hmph, perhaps WITH/WITHOUT also do not take "--no-" form hence need OPT_NONEG?

Quoted 25 lines

parse-options.h +4 -5

@@ -1586,11 +1587,11 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
 }
 
 static int commit_contains(struct ref_filter *filter, struct commit *commit,
-                        struct contains_cache *cache)
+                        struct commit_list *list, struct contains_cache *cache)
 {
      if (filter->with_commit_tag_algo)
-             return contains_tag_algo(commit, filter->with_commit, cache) == CONTAINS_YES;
-     return is_descendant_of(commit, filter->with_commit);
+             return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
+     return is_descendant_of(commit, list);
 }
 
 /*

@@ -1780,13 +1781,17 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
       * obtain the commit using the 'oid' available and discard all
       * non-commits early. The actual filtering is done later.
       */
-     if (filter->merge_commit || filter->with_commit || filter->verbose) {
+     if (filter->merge_commit || filter->with_commit || filter->no_commit || filter->verbose) {
              commit = lookup_commit_reference_gently(oid->hash, 1);
              if (!commit)
                      return 0;
-             /* We perform the filtering for the '--contains' option */

parse-options.h static int ref_filter_handler(const char *refname, const struct object_id *oid, · line 1796

Quoted 10 lines

parse-options.h +6 -1

+             /* We perform the filtering for the '--contains' option... */
              if (filter->with_commit &&
-                 !commit_contains(filter, commit, &ref_cbdata->contains_cache))
+                 !commit_contains(filter, commit, filter->with_commit, &ref_cbdata->contains_cache))
+                     return 0;
+             /* ...or for the `--no-contains' option */
+             if (filter->no_commit &&
+                 commit_contains(filter, commit, filter->no_commit, &ref_cbdata->no_contains_cache))
                      return 0;
      }

When asking "--contains A --contains B", we show refs that contain _EITHER_ A or B. Two predicates are ORed together, and I think it makes sense.

When asking "--contains A --no-contains B", we show refs that contain A but exclude refs that contains B. Two predicates are ANDed together, and I think this also makes sense.

When asking "--no-contains A --no-contains B", what should we show? This implementation makes the two predicates ANDed together [*1*].

The behaviour is sensible, but is it consistent with the way now existing --no-merged works?

I think the rule is something like:

A match with any positive selection criterion (like --contains
A) makes a ref eligible for output, but then a match with any negatigve selection criterion (like --no-merged) filters it out.

Is it easy to explain to the users? Do we need doc updates to clarify, or does the description for existing --no-merged already cover this?

And then later in the documentation:

    -l <pattern>, --list <pattern>

I.e. for git-branch this type of invocation wouldn't make sense and would just happen to work, but for git-tag the --list option is explicitly documented to immediately take a <pattern> argument.

I'll change it.

Quoted 2 lines

git tag -l --no-contains v2.10.1-3-gcf5c7253e0 'v[0-9]*' | sort | tail -n 10

Although I'll add a \ to that so you can still paste it to a terminal.

Quoted 4 lines

Reviewers would appreciate you refrain from doing that in the same patch. Do a minimum patch so that the review can concentrate on what got changed (i.e. contents), followed by a mechanical reflow as a follow-up, or something like that, would be much nicer to handle.

Okey, so two patches, one where I potentially produce very long lines & then re-flow them in a subsequent commit.

If I'd like to base on top of that to make things easier for you do you publish jk/ref-filter-flags-cleanup sowhere? I.e. as a git ref rather than me also following that topic, applying it on top of master, and then applying my topic on top of that.

Quoted 6 lines

and have both default to HEAD? I know that would not make sense as a set operation, but I am curious what our command line parser (which is oblivious to what the command is doing) does. I am guessing that it would barf saying "--contains" needs a commit but "--no-contains" is not a commit (which is very sensible)?

It'll spew out "error: malformed object name --no-contains".

You can do "--contains HEAD --no-contains HEAD" to get nothing.

In an earlier thread I was discussing with Jeff whether it would be worthwhile to error out in that case, but his opinion was (paraphrasing) "Nah, GIGO", which I think makes sense in this case.

Quoted 7 lines

parse-options.h extern int parse_opt_passthru_argv(const struct option *, const char *, int); · line 264

Quoted 5 lines

parse-options.h +3 -1

-#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h, 0)
+#define OPT_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("contains", v, h, PARSE_OPT_NONEG)
+#define OPT_NO_CONTAINS(v, h) _OPT_CONTAINS_OR_WITH("no-contains", v, h, PARSE_OPT_NONEG)
 #define OPT_WITH(v, h) _OPT_CONTAINS_OR_WITH("with", v, h, PARSE_OPT_HIDDEN)
+#define OPT_WITHOUT(v, h) _OPT_CONTAINS_OR_WITH("without", v, h, PARSE_OPT_HIDDEN)

Hmph, perhaps WITH/WITHOUT also do not take "--no-" form hence need OPT_NONEG?

I may be missing some subtlety here, but I think you've misread this (admittedly dense) chunk. the /WITH/ options don't supply NONEG, just HIDDEN.

Quoted 11 lines · Ævar Arnfjörð Bjarmason

Quoted 3 lines

I'm almost certain this is because the contains_tag_algo one doesn't clean up the flag bits it sets on the commit objects. So running it twice in the same process is going to give you nonsense results.

Yeah indeed.

I tried to hack something up to avoid this, but the lookup_commit_reference_gently() we call will return the same object.parent pointer for two invocations, i.e. the underlying {commit,object}.c API has a cache of objects it returns, couldn't find some way to quickly make it burst that cache.

Yeah, you'll always get the same struct for a given sha1.

Quoted 6 lines

The other approach of making contains_tag_algo() itself detect that it's been called before (or us passing a flag) and going around setting commit.object.flags on everything to 0 seemed even more brittle, particularly since I think between filter->with_commit & filter->no_commit we might end up visiting different commits, so it's not easy to just clear it.

You can clear the marks with clear_object_flags(). But I don't think that type of solution will quite help us here. We consider each ref independently and ask "does it match --contains" and "does it match --no-contains?". So there is no moment where we are done with all of the --contains marks, and can move on to the --no-contains ones. The lookups are interleaved.

We could move to doing them in chunks (the way filter->merge_commit works), and then clearing in between. Or we could use a separate bitset. The patch below does that.

Quoted 5 lines

I'm happy to hack on it given some pointers, will visit it again, but for now unless I'm missing something obvious / you can point out some way to hack this up I'll just submit v2 with the combination of --contains & --no-contains dying with a TODO message.

Quoted 2 lines

The patch without that functionality is still really useful, and we can implement that later.

I'm not opposed to that, though see what you think of the patch below. It's a bit noisy but it's conceptually pretty straightforward. It should hopefully be obvious how you'd add in a separate contains_cache for the "without" case.

Looking at this, I'm pretty sure that using "--contains" with "--merged" has similar problems, as they both use the UNINTERESTING bit. So even without your patch, there is a lurking bug.

ref-filter.c +43 -24

index 3820b21cc..42b1bc463 100644
@@ -14,6 +14,7 @@
 #include "git-compat-util.h"
 #include "version.h"
 #include "trailer.h"
+#include "commit-slab.h"
 
 typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
 

@@ -1137,10 +1138,22 @@ static void get_ref_atom_value(struct ref_array_item *ref, int atom, struct atom
        *v = &ref->value[atom];
 }
 
+/*
+ * Unknown has to be "0" here, because that's what unfilled entries in our slab
+ * will return.
+ */
 enum contains_result {
-       CONTAINS_UNKNOWN = -1,
-       CONTAINS_NO = 0,
-       CONTAINS_YES = 1
+       CONTAINS_UNKNOWN = 0,
+       CONTAINS_NO = 1,
+       CONTAINS_YES = 2,
+};
+
+define_commit_slab(contains_cache, enum contains_result);
+
+struct ref_filter_cbdata {
+       struct ref_array *array;
+       struct ref_filter *filter;
+       struct contains_cache contains_cache;
 };
 
 /*

@@ -1171,24 +1184,25 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)
  * Do not recurse to find out, though, but return -1 if inconclusive.
  */
 static enum contains_result contains_test(struct commit *candidate,
-                           const struct commit_list *want)
+                           const struct commit_list *want,
+                           struct contains_cache *cache)
 {
-       /* was it previously marked as containing a want commit? */
-       if (candidate->object.flags & TMP_MARK)
-               return 1;
-       /* or marked as not possibly containing a want commit? */
-       if (candidate->object.flags & UNINTERESTING)
-               return 0;
+       enum contains_result *cached = contains_cache_at(cache, candidate);
+
+       /* if we already found the answer, return it without traversing */
+       if (*cached)
+               return *cached;
+
        /* or are we it? */
        if (in_commit_list(want, candidate)) {
-               candidate->object.flags |= TMP_MARK;
-               return 1;
+               *cached = CONTAINS_YES;
+               return *cached;
        }
 
        if (parse_commit(candidate) < 0)
-               return 0;
+               return CONTAINS_NO;
 
-       return -1;
+       return CONTAINS_UNKNOWN;
 }
 
 static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)

@@ -1199,10 +1213,11 @@ static void push_to_contains_stack(struct commit *candidate, struct contains_sta
 }
 
 static enum contains_result contains_tag_algo(struct commit *candidate,
-               const struct commit_list *want)
+                                             const struct commit_list *want,
+                                             struct contains_cache *cache)
 {
        struct contains_stack contains_stack = { 0, 0, NULL };
-       int result = contains_test(candidate, want);
+       enum contains_result result = contains_test(candidate, want, cache);
 
        if (result != CONTAINS_UNKNOWN)
                return result;

@@ -1214,16 +1229,16 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
                struct commit_list *parents = entry->parents;
 
                if (!parents) {
-                       commit->object.flags |= UNINTERESTING;
+                       *contains_cache_at(cache, commit) = CONTAINS_NO;
                        contains_stack.nr--;
                }
                /*
                 * If we just popped the stack, parents->item has been marked,
-                * therefore contains_test will return a meaningful 0 or 1.
+                * therefore contains_test will return a meaningful yes/no.
                 */
-               else switch (contains_test(parents->item, want)) {
+               else switch (contains_test(parents->item, want, cache)) {
                case CONTAINS_YES:
-                       commit->object.flags |= TMP_MARK;
+                       *contains_cache_at(cache, commit) = CONTAINS_YES;
                        contains_stack.nr--;
                        break;
                case CONTAINS_NO:

@@ -1235,13 +1250,14 @@ static enum contains_result contains_tag_algo(struct commit *candidate,
                }
        }
        free(contains_stack.contains_stack);
-       return contains_test(candidate, want);
+       return contains_test(candidate, want, cache);
 }
 
-static int commit_contains(struct ref_filter *filter, struct commit *commit)
+static int commit_contains(struct ref_filter *filter, struct commit *commit,
+                          struct contains_cache *cache)
 {
        if (filter->with_commit_tag_algo)
-               return contains_tag_algo(commit, filter->with_commit);
+               return contains_tag_algo(commit, filter->with_commit, cache) == CONTAINS_YES;
        return is_descendant_of(commit, filter->with_commit);
 }
 

@@ -1438,7 +1454,7 @@ static int ref_filter_handler(const char *refname, const struct object_id *oid,
                        return 0;
                /* We perform the filtering for the '--contains' option */
                if (filter->with_commit &&
-                   !commit_contains(filter, commit))
+                   !commit_contains(filter, commit, &ref_cbdata->contains_cache))
                        return 0;
        }
 

@@ -1538,6 +1554,8 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
                broken = 1;
        filter->kind = type & FILTER_REFS_KIND_MASK;
 
+       init_contains_cache(&ref_cbdata.contains_cache);
+
        /*  Simple per-ref filtering */
        if (!filter->kind)
                die("filter_refs: invalid type");

@@ -1560,6 +1578,7 @@ int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int
                        head_ref(ref_filter_handler, &ref_cbdata);
        }
 
+       clear_contains_cache(&ref_cbdata.contains_cache);
 
        /*  Filters that need revision walking */
        if (filter->merge_commit)

ref-filter.h +0 -5

index 7b05592ba..89af9f451 100644
@@ -71,11 +71,6 @@ struct ref_filter {
                verbose;
 };
 
-struct ref_filter_cbdata {
-       struct ref_array *array;
-       struct ref_filter *filter;
-};
-
 /*  Macros for checking --merged and --no-merged options */
 #define _OPT_MERGED_NO_MERGED(option, filter, h) \
        { OPTION_CALLBACK, 0, option, (filter), N_("commit"), (h), \

(quoted diff) +1 -1

-       filter->with_commit_tag_algo = 1;
+       if ((filter->merge_commit + filter->with_commit +

filter->no_commit) > 1)

(quoted diff) +3 -0

+               filter->with_commit_tag_algo = 0;
+       else
+               filter->with_commit_tag_algo = 1;
        filter_refs(&array, filter, FILTER_REFS_TAGS);
        ref_array_sort(sorting, &array);

I think I'll amend the tip of my WIP v2 to have something like that, and then we can follow-up with making these cases where you supply multiple options faster.

Quoted 3 lines

Looking at this, I'm pretty sure that using "--contains" with "--merged" has similar problems, as they both use the UNINTERESTING bit. So even without your patch, there is a lurking bug.

I'm currently running this:
https://gist.github.com/avar/45cf288ce7cdc43e7395c6cbf9a98d68

Quoted 9 lines · Ævar Arnfjörð Bjarmason

(quoted diff) +1 -1

-       filter->with_commit_tag_algo = 1;
+       if ((filter->merge_commit + filter->with_commit +

filter->no_commit) > 1)

(quoted diff) +3 -0

+               filter->with_commit_tag_algo = 0;
+       else
+               filter->with_commit_tag_algo = 1;
        filter_refs(&array, filter, FILTER_REFS_TAGS);
        ref_array_sort(sorting, &array);

Quoted 3 lines

I think I'll amend the tip of my WIP v2 to have something like that, and then we can follow-up with making these cases where you supply multiple options faster.

Yeah, that's another option. I think you may find that it's unbearably slow if you have a lot of tags.

Quoted 6 lines

Quoted 3 lines

Looking at this, I'm pretty sure that using "--contains" with "--merged" has similar problems, as they both use the UNINTERESTING bit. So even without your patch, there is a lurking bug.

I'm currently running this:
https://gist.github.com/avar/45cf288ce7cdc43e7395c6cbf9a98d68

Cute. I'll be curious if it turns up anything.

Documentation/git-tag.txt +1 -1

index 525737a5d8..4938496194 100644
@@ -12,7 +12,7 @@ SYNOPSIS
 'git tag' [-a | -s | -u <keyid>] [-f] [-m <msg> | -F <file>]
        <tagname> [<commit> | <object>]
 'git tag' -d <tagname>...
-'git tag' [-n[<num>]] -l [--contains <commit>] [--points-at <object>]
+'git tag' [-n[<num>]] -l [--[no-]contains <commit>] [--points-at <object>]
        [--column[=<options>] | --no-column] [--create-reflog] [--sort=<key>]
        [--format=<format>] [--[no-]merged [<commit>]] [<pattern>...]
 'git tag' -v [--format=<format>] <tagname>...

Documentation/git-tag.txt +1 -0

+
 --points-at <object>::
        Only list tags of the given object.
 

builtin/branch.c +0 -0

index 94f7de7fa5..e8d534604c 100644

Quoted 15 lines · Ævar Arnfjörð Bjarmason

Documentation/git-tag.txt +1 -1

index 525737a5d8..4938496194 100644
@@ -12,7 +12,7 @@ SYNOPSIS
 'git tag' [-a | -s | -u <keyid>] [-f] [-m <msg> | -F <file>]
        <tagname> [<commit> | <object>]
 'git tag' -d <tagname>...
-'git tag' [-n[<num>]] -l [--contains <commit>] [--points-at <object>]
+'git tag' [-n[<num>]] -l [--[no-]contains <commit>] [--points-at <object>]
        [--column[=<options>] | --no-column] [--create-reflog] [--sort=<key>]
        [--format=<format>] [--[no-]merged [<commit>]] [<pattern>...]
 'git tag' -v [--format=<format>] <tagname>...

Documentation/git-tag.txt This option is only applicable when listing tags without annotation lines. · line 129

Quoted 6 lines

Documentation/git-tag.txt +3 -0

@@ -124,6 +124,10 @@ This option is only applicable when listing tags without annotation lines.
        Only list tags which contain the specified commit (HEAD if not
        specified).
 
+--no-contains [<commit>]::
+       Only list tags which don't contain the specified commit (HEAD if
+       not secified).

s/secified/specified/

Quoted 4 lines

Documentation/git-tag.txt +1 -0

+
 --points-at <object>::
        Only list tags of the given object.
 

builtin/branch.c int cmd_branch(int argc, const char **argv, const char *prefix) · line 553

Quoted 11 lines

builtin/branch.c +2 -0

index 94f7de7fa5..e8d534604c 100644
@@ -548,7 +548,9 @@ int cmd_branch(int argc, const char **argv, const char *prefix)
                OPT_SET_INT('r', "remotes",     &filter.kind, N_("act on remote-tracking branches"),
                        FILTER_REFS_REMOTES),
                OPT_CONTAINS(&filter.with_commit, N_("print only branches that contain the commit")),
+               OPT_NO_CONTAINS(&filter.no_commit, N_("print only branches that don't contain the commit")),
                OPT_WITH(&filter.with_commit, N_("print only branches that contain the commit")),
+               OPT_WITHOUT(&filter.with_commit, N_("print only branches that don't contain the commit")),

s/with_commit/no_commit/

Quoted 30 lines · Christian Couder

Quoted 15 lines · Ævar Arnfjörð Bjarmason

Documentation/git-tag.txt +1 -1

index 525737a5d8..4938496194 100644
@@ -12,7 +12,7 @@ SYNOPSIS
 'git tag' [-a | -s | -u <keyid>] [-f] [-m <msg> | -F <file>]
        <tagname> [<commit> | <object>]
 'git tag' -d <tagname>...
-'git tag' [-n[<num>]] -l [--contains <commit>] [--points-at <object>]
+'git tag' [-n[<num>]] -l [--[no-]contains <commit>] [--points-at <object>]
        [--column[=<options>] | --no-column] [--create-reflog] [--sort=<key>]
        [--format=<format>] [--[no-]merged [<commit>]] [<pattern>...]
 'git tag' -v [--format=<format>] <tagname>...

Documentation/git-tag.txt This option is only applicable when listing tags without annotation lines. · line 129

Quoted 6 lines

Documentation/git-tag.txt +3 -0

@@ -124,6 +124,10 @@ This option is only applicable when listing tags without annotation lines.
        Only list tags which contain the specified commit (HEAD if not
        specified).
 
+--no-contains [<commit>]::
+       Only list tags which don't contain the specified commit (HEAD if
+       not secified).

s/secified/specified/

Quoted 4 lines

Documentation/git-tag.txt +1 -0

+
 --points-at <object>::
        Only list tags of the given object.
 

Quoted 13 lines

builtin/branch.c int cmd_branch(int argc, const char **argv, const char *prefix) · line 553

Quoted 11 lines

builtin/branch.c +2 -0

index 94f7de7fa5..e8d534604c 100644
@@ -548,7 +548,9 @@ int cmd_branch(int argc, const char **argv, const char *prefix)
                OPT_SET_INT('r', "remotes",     &filter.kind, N_("act on remote-tracking branches"),
                        FILTER_REFS_REMOTES),
                OPT_CONTAINS(&filter.with_commit, N_("print only branches that contain the commit")),
+               OPT_NO_CONTAINS(&filter.no_commit, N_("print only branches that don't contain the commit")),
                OPT_WITH(&filter.with_commit, N_("print only branches that contain the commit")),
+               OPT_WITHOUT(&filter.with_commit, N_("print only branches that don't contain the commit")),

s/with_commit/no_commit/

Thanks!

FWIW this is the current status of my WIP v3. I noticed a couple of other issues where --contains was mentioned without --no-contains.

Documentation/git-tag.txt +0 -0

index 4938496194..d9243bf5e4 100644
@@ -129 +129 @@ This option is only applicable when listing tags

without annotation lines.

Documentation/git-tag.txt +1 -1

-       not secified).
+       not specified).

builtin/branch.c +0 -1

index e8d534604c..dd96319726 100644
@@ -553 +553 @@ int cmd_branch(int argc, const char **argv, const char *prefix)
-               OPT_WITHOUT(&filter.with_commit, N_("print only

branches that don't contain the commit")),
+ OPT_WITHOUT(&filter.no_commit, N_("print only branches
that don't contain the commit")),

builtin/for-each-ref.c +1 -1

index b1ae2388e6..a11542c4fd 100644
@@ -12 +12 @@ static char const * const for_each_ref_usage[] = {
-       N_("git for-each-ref [--contains [<object>]]"),
+       N_("git for-each-ref [(--contains | --no-contains) [<object>]]"),

builtin/tag.c +1 -1

index d83674e3e6..57289132a9 100644
@@ -25 +25 @@ static const char * const git_tag_usage[] = {
-       N_("git tag -l [-n[<num>]] [--contains <commit>] [--points-at <object>]"
+       N_("git tag -l [-n[<num>]] [--[no-]contains <commit>]

[--points-at <object>]"

These last two hunks are going to bust the i18n files for most languages. Junio/Jiang, in cases like these where I could fix those up with a search/replace on po/* without knowing the languages in question (since it's purely changing e.g. --contains to --[no-]contains), what do you prefer to do, have that as part of this patch, or do it after the fact through the normal i18n maintenance process?