git/ref-filter.c, branch v2.23.2

Merge branch 'ma/ref-filter-leakfix'

2019-07-19T18:30:23Z

Leakfix. * ma/ref-filter-leakfix: ref-filter: fix memory leak in `free_array_item()`

Merge branch 'tb/ref-filter-multiple-patterns'

2019-07-19T18:30:21Z

"git for-each-ref" with multiple patterns have been optimized. * tb/ref-filter-multiple-patterns: ref-filter.c: find disjoint pattern prefixes

ref-filter: fix memory leak in `free_array_item()`

2019-07-10T20:27:13Z

We treat the `value` pointer as a pointer to a struct and free its `s` field. But `value` is in fact an array of structs. As a result, we only free the first `s` out of `used_atom_cnt`-many and leak the rest. Make sure we free all items in `value`. In the caller, `ref_array_clear()`, this means we need to be careful not to zero `used_atom_cnt` until after we've called `free_array_item()`. We could move just a single line, but let's keep related things close together instead, by first handling `array`, then `used_atom`. Signed-off-by: Martin Ågren Signed-off-by: Junio C Hamano

Merge branch 'md/sort-detached-head-first'

2019-07-09T22:25:42Z

"git branch --list" learned to always output the detached HEAD as the first item (when the HEAD is detached, of course), regardless of the locale. * md/sort-detached-head-first: ref-filter: sort detached HEAD lines firstly

Merge branch 'nb/branch-show-other-worktrees-head'

2019-07-09T22:25:33Z

"git branch --list" learned to show branches that are checked out in other worktrees connected to the same repository prefixed with '+', similar to the way the currently checked out branch is shown with '*' in front. * nb/branch-show-other-worktrees-head: branch: add worktree info on verbose output branch: update output to include worktree info ref-filter: add worktreepath atom

ref-filter.c: find disjoint pattern prefixes

2019-06-27T20:14:06Z

Since cfe004a5a9 (ref-filter: limit traversal to prefix, 2017-05-22), the ref-filter code has sought to limit the traversals to a prefix of the given patterns. That code stopped short of handling more than one pattern, because it means invoking 'for_each_ref_in' multiple times. If we're not careful about which patterns overlap, we will output the same refs multiple times. For instance, consider the set of patterns 'refs/heads/a/*', 'refs/heads/a/b/c', and 'refs/tags/v1.0.0'. If we naÃ¯vely ran: for_each_ref_in("refs/heads/a/*", ...); for_each_ref_in("refs/heads/a/b/c", ...); for_each_ref_in("refs/tags/v1.0.0", ...); we would see 'refs/heads/a/b/c' (and everything underneath it) twice. Instead, we want to partition the patterns into disjoint sets, where we know that no ref will be matched by any two patterns in different sets. In the above, these are: - {'refs/heads/a/*', 'refs/heads/a/b/c'}, and - {'refs/tags/v1.0.0'} Given one of these disjoint sets, what is a suitable pattern to pass to 'for_each_ref_in'? One approach is to compute the longest common prefix over all elements in that disjoint set, and let the caller cull out the refs they didn't want. Computing the longest prefix means that in most cases, we won't match too many things the caller would like to ignore. The longest common prefixes of the above are: - {'refs/heads/a/*', 'refs/heads/a/b/c'} -> refs/heads/a/* - {'refs/tags/v1.0.0'} -> refs/tags/v1.0.0 We instead invoke: for_each_ref_in("refs/heads/a/*", ...); for_each_ref_in("refs/tags/v1.0.0", ...); Which provides us with the refs we were looking for with a minimal amount of extra cruft, but never a duplicate of the ref we asked for. Implemented here is an algorithm which accomplishes the above, which works as follows: 1. Lexicographically sort the given list of patterns. 2. Initialize 'prefix' to the empty string, where our goal is to build each element in the above set of longest common prefixes. 3. Consider each pattern in the given set, and emit 'prefix' if it reaches the end of a pattern, or touches a wildcard character. The end of a string is treated as if it precedes a wildcard. (Note that there is some room for future work to detect that, e.g., 'a?b' and 'abc' are disjoint). 4. Otherwise, recurse on step (3) with the slice of the list corresponding to our current prefix (i.e., the subset of patterns that have our prefix as a literal string prefix.) This algorithm is 'O(kn + n log(n))', where 'k' is max(len(pattern)) for each pattern in the list, and 'n' is len(patterns). By discovering this set of interesting patterns, we reduce the runtime of multi-pattern 'git for-each-ref' (and other ref traversals) from O(N) to O(n log(N)), where 'N' is the total number of packed references. Running 'git for-each-ref refs/tags/a refs/tags/b' on a repository with 10,000,000 refs in 'refs/tags/huge-N', my best-of-five times drop from: real 0m5.805s user 0m5.188s sys 0m0.468s to: real 0m0.001s user 0m0.000s sys 0m0.000s On linux.git, the times to dig out two of the latest -rc tags drops from 0.002s to 0.001s, so the change on repositories with fewer tags is much less noticeable. Co-authored-by: Jeff King Signed-off-by: Jeff King Signed-off-by: Taylor Blau Signed-off-by: Junio C Hamano

ref-filter: sort detached HEAD lines firstly

2019-06-19T15:24:41Z

Before this patch, "git branch" would put "(HEAD detached...)" and "(no branch, rebasing...)" lines before all the other branches *in most cases* except for when using Chinese-language messages. zh_CN generally uses a full-width "(" symbol (codepoint FF08) to match the full-width proportions of Chinese characters, and the translated strings we had did use them. This meant that the detached HEAD line would appear after all local refs and even after the remote refs if there were any. AFAIK, it is sometimes not jarring to see the half-width parenthesis in "full-width" text as in the CJK languages, for instance when there are no characters preceding or following the parenthesized text fragment. By removing the parenthesis from the localizable text, we can share strings with wt-status.c and remove a cautionary comment to translators. Remove the ( from the localizable portion of messages so the sorting happens properly regardless of locale. Helped-by: Johannes Schindelin Helped-by: Jonathan Nieder Signed-off-by: Matthew DeVore Signed-off-by: Junio C Hamano

Merge branch 'dr/ref-filter-push-track-fix'

2019-05-08T15:37:26Z

%(push:track) token used in the --format option to "git for-each-ref" and friends was not showing the right branch, which has been fixed. * dr/ref-filter-push-track-fix: ref-filter: use correct branch for %(push:track)

ref-filter: add worktreepath atom

2019-05-07T04:45:53Z

Add an atom providing the path of the linked worktree where this ref is checked out, if it is checked out in any linked worktrees, and empty string otherwise. Signed-off-by: Nickolai Belakovski Signed-off-by: Junio C Hamano

ref-filter: use correct branch for %(push:track)

2019-04-18T00:17:41Z

In ref-filter.c, when processing the atom %(push:track), the ahead/behind values are computed using `stat_tracking_info` which refers to the upstream branch. Fix that by introducing a new flag `for_push` in `stat_tracking_info` in remote.c, which does the same thing but for the push branch. Update the few callers of `stat_tracking_info` to handle this flag. This ensure that whenever we use this function in the future, we are careful to specify is this should apply to the upstream or the push branch. This bug was not detected in t/t6300-for-each-ref.sh because in the test for push:track, both the upstream and the push branches were behind by 1 from the local branch. Change the test so that the upstream branch is behind by 1 while the push branch is ahead by 1. This allows us to test that %(push:track) refers to the correct branch. This changes the expected value of some following tests (by introducing new references), so update them too. Signed-off-by: Damien Robert Reviewed-by: Jeff King Signed-off-by: Junio C Hamano