Raw
1 #include "git-compat-util.h"
2 #include "bloom.h"
3 #include "builtin.h"
4 #include "commit-graph.h"
5 #include "commit-slab.h"
6 #include "commit.h"
7 #include "config.h"
8 #include "diff.h"
9 #include "diffcore.h"
10 #include "environment.h"
11 #include "ewah/ewok.h"
12 #include "hashmap.h"
13 #include "hex.h"
14 #include "object-name.h"
15 #include "object.h"
16 #include "parse-options.h"
17 #include "prio-queue.h"
18 #include "quote.h"
19 #include "repository.h"
20 #include "revision.h"
21
22 /* Remember to update object flag allocation in object.h */
23 #define PARENT1 (1u<<16) /* used instead of SEEN */
24 #define PARENT2 (1u<<17) /* used instead of BOTTOM, BOUNDARY */
25
26 struct last_modified_entry {
27 struct hashmap_entry hashent;
28 struct object_id oid;
29 struct bloom_key key;
30 size_t diff_idx;
31 const char path[FLEX_ARRAY];
32 };
33
34 static int last_modified_entry_hashcmp(const void *unused UNUSED,
35 const struct hashmap_entry *hent1,
36 const struct hashmap_entry *hent2,
37 const void *path)
38 {
39 const struct last_modified_entry *ent1 =
40 container_of(hent1, const struct last_modified_entry, hashent);
41 const struct last_modified_entry *ent2 =
42 container_of(hent2, const struct last_modified_entry, hashent);
43 return strcmp(ent1->path, path ? path : ent2->path);
44 }
45
46 /*
47 * Hold a bitmap for each commit we're working with. In the bitmap, each bit
48 * represents a path in `lm->all_paths`. An active bit indicates the path still
49 * needs to be associated to a commit.
50 */
51 define_commit_slab(active_paths_for_commit, struct bitmap *);
52
53 struct last_modified {
54 struct hashmap paths;
55 struct rev_info rev;
56 bool show_trees;
57 bool nul_termination;
58 int max_depth;
59
60 const char **all_paths;
61 size_t all_paths_nr;
62 struct active_paths_for_commit active_paths;
63
64 /* 'scratch' to avoid allocating a bitmap every process_parent() */
65 struct bitmap *scratch;
66 };
67
68 static struct bitmap *active_paths_for(struct last_modified *lm, struct commit *c)
69 {
70 struct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);
71 if (!*bitmap)
72 *bitmap = bitmap_word_alloc(lm->all_paths_nr / BITS_IN_EWORD + 1);
73
74 return *bitmap;
75 }
76
77 static void active_paths_free(struct last_modified *lm, struct commit *c)
78 {
79 struct bitmap **bitmap = active_paths_for_commit_at(&lm->active_paths, c);
80 if (*bitmap) {
81 bitmap_free(*bitmap);
82 *bitmap = NULL;
83 }
84 }
85
86 static void last_modified_release(struct last_modified *lm)
87 {
88 struct hashmap_iter iter;
89 struct last_modified_entry *ent;
90
91 hashmap_for_each_entry(&lm->paths, &iter, ent, hashent)
92 bloom_key_clear(&ent->key);
93
94 hashmap_clear_and_free(&lm->paths, struct last_modified_entry, hashent);
95 release_revisions(&lm->rev);
96
97 free(lm->all_paths);
98 }
99
100 struct last_modified_callback_data {
101 struct last_modified *lm;
102 struct commit *commit;
103 };
104
105 static void add_path_from_diff(struct diff_queue_struct *q,
106 struct diff_options *opt UNUSED, void *data)
107 {
108 struct last_modified *lm = data;
109
110 for (int i = 0; i < q->nr; i++) {
111 struct diff_filepair *p = q->queue[i];
112 struct last_modified_entry *ent;
113 const char *path = p->two->path;
114
115 FLEX_ALLOC_STR(ent, path, path);
116 oidcpy(&ent->oid, &p->two->oid);
117 if (lm->rev.bloom_filter_settings)
118 bloom_key_fill(&ent->key, path, strlen(path),
119 lm->rev.bloom_filter_settings);
120 hashmap_entry_init(&ent->hashent, strhash(ent->path));
121 hashmap_add(&lm->paths, &ent->hashent);
122 }
123 }
124
125 static int populate_paths_from_revs(struct last_modified *lm)
126 {
127 int num_interesting = 0, ret = 0;
128 struct diff_options diffopt;
129
130 /*
131 * Create a copy of `struct diff_options`. In this copy a callback is
132 * set that when called adds entries to `paths` in `struct last_modified`.
133 * This copy is used to diff the tree of the target revision against an
134 * empty tree. This results in all paths in the target revision being
135 * listed. After `paths` is populated, we don't need this copy no more.
136 */
137 memcpy(&diffopt, &lm->rev.diffopt, sizeof(diffopt));
138 copy_pathspec(&diffopt.pathspec, &lm->rev.diffopt.pathspec);
139 diffopt.output_format = DIFF_FORMAT_CALLBACK;
140 diffopt.format_callback = add_path_from_diff;
141 diffopt.format_callback_data = lm;
142
143 for (size_t i = 0; i < lm->rev.pending.nr; i++) {
144 struct object_array_entry *obj = lm->rev.pending.objects + i;
145
146 if (obj->item->flags & UNINTERESTING)
147 continue;
148
149 if (num_interesting++) {
150 ret = error(_("last-modified can only operate on one commit at a time"));
151 goto out;
152 }
153
154 if (!repo_peel_to_type(lm->rev.repo, obj->path, 0, obj->item, OBJ_COMMIT)) {
155 ret = error(_("revision argument '%s' is a %s, not a commit-ish"), obj->name, type_name(obj->item->type));
156 goto out;
157 }
158
159 diff_tree_oid(lm->rev.repo->hash_algo->empty_tree,
160 &obj->item->oid, "", &diffopt);
161 diff_flush(&diffopt);
162 }
163
164 out:
165 clear_pathspec(&diffopt.pathspec);
166
167 return ret;
168 }
169
170 static void last_modified_emit(struct last_modified *lm,
171 const char *path, const struct commit *commit)
172
173 {
174 if (commit->object.flags & BOUNDARY)
175 putchar('^');
176 printf("%s\t", oid_to_hex(&commit->object.oid));
177
178 if (lm->nul_termination)
179 printf("%s%c", path, '\0');
180 else
181 write_name_quoted(path, stdout, '\n');
182 }
183
184 static void mark_path(const char *path, const struct object_id *oid,
185 struct last_modified_callback_data *data)
186 {
187 struct last_modified_entry *ent;
188
189 /* Is it even a path that we are interested in? */
190 ent = hashmap_get_entry_from_hash(&data->lm->paths, strhash(path), path,
191 struct last_modified_entry, hashent);
192 if (!ent)
193 return;
194
195 /*
196 * Is it arriving at a version of interest, or is it from a side branch
197 * which did not contribute to the final state?
198 */
199 if (oid && !oideq(oid, &ent->oid))
200 return;
201
202 last_modified_emit(data->lm, path, data->commit);
203
204 hashmap_remove(&data->lm->paths, &ent->hashent, path);
205 bloom_key_clear(&ent->key);
206 free(ent);
207 }
208
209 static void last_modified_diff(struct diff_queue_struct *q,
210 struct diff_options *opt UNUSED, void *cbdata)
211 {
212 struct last_modified_callback_data *data = cbdata;
213
214 for (int i = 0; i < q->nr; i++) {
215 struct diff_filepair *p = q->queue[i];
216 switch (p->status) {
217 case DIFF_STATUS_DELETED:
218 /*
219 * There's no point in feeding a deletion, as it could
220 * not have resulted in our current state, which
221 * actually has the file.
222 */
223 break;
224
225 default:
226 /*
227 * Otherwise, we care only that we somehow arrived at
228 * a final oid state. Note that this covers some
229 * potentially controversial areas, including:
230 *
231 * 1. A rename or copy will be found, as it is the
232 * first time the content has arrived at the given
233 * path.
234 *
235 * 2. Even a non-content modification like a mode or
236 * type change will trigger it.
237 *
238 * We take the inclusive approach for now, and find
239 * anything which impacts the path. Options to tweak
240 * the behavior (e.g., to "--follow" the content across
241 * renames) can come later.
242 */
243 mark_path(p->two->path, &p->two->oid, data);
244 break;
245 }
246 }
247 }
248
249 static void pass_to_parent(struct bitmap *c,
250 struct bitmap *p,
251 size_t pos)
252 {
253 bitmap_unset(c, pos);
254 bitmap_set(p, pos);
255 }
256
257 static bool maybe_changed_path(struct last_modified *lm,
258 struct commit *origin,
259 struct bitmap *active)
260 {
261 struct bloom_filter *filter;
262 struct last_modified_entry *ent;
263 struct hashmap_iter iter;
264
265 if (!lm->rev.bloom_filter_settings)
266 return true;
267
268 if (commit_graph_generation(origin) == GENERATION_NUMBER_INFINITY)
269 return true;
270
271 filter = get_bloom_filter(lm->rev.repo, origin);
272 if (!filter)
273 return true;
274
275 if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
276 return false;
277
278 hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
279 if (active && !bitmap_get(active, ent->diff_idx))
280 continue;
281
282 if (bloom_filter_contains(filter, &ent->key,
283 lm->rev.bloom_filter_settings))
284 return true;
285 }
286 return false;
287 }
288
289 static void process_parent(struct last_modified *lm,
290 struct prio_queue *queue,
291 struct commit *c, struct bitmap *active_c,
292 struct commit *parent, int parent_i)
293 {
294 struct bitmap *active_p;
295
296 if (repo_parse_commit(lm->rev.repo, parent))
297 return;
298 active_p = active_paths_for(lm, parent);
299
300 /*
301 * The first time entering this function for this commit (i.e. first parent)
302 * see if Bloom filters will tell us it's worth to do the diff.
303 */
304 if (parent_i || maybe_changed_path(lm, c, active_c)) {
305 diff_tree_oid(&parent->object.oid,
306 &c->object.oid, "", &lm->rev.diffopt);
307 diffcore_std(&lm->rev.diffopt);
308 }
309
310 /*
311 * Test each path for TREESAME-ness against the parent. If a path is
312 * TREESAME, pass it on to this parent.
313 *
314 * First, collect all paths that are *not* TREESAME in 'scratch'.
315 * Then, pass paths that *are* TREESAME and active to the parent.
316 */
317 for (int i = 0; i < diff_queued_diff.nr; i++) {
318 struct diff_filepair *fp = diff_queued_diff.queue[i];
319 const char *path = fp->two->path;
320 struct last_modified_entry *ent =
321 hashmap_get_entry_from_hash(&lm->paths, strhash(path), path,
322 struct last_modified_entry, hashent);
323 if (ent) {
324 size_t k = ent->diff_idx;
325 if (bitmap_get(active_c, k))
326 bitmap_set(lm->scratch, k);
327 }
328 }
329 for (size_t i = 0; i < lm->all_paths_nr; i++) {
330 if (bitmap_get(active_c, i) && !bitmap_get(lm->scratch, i))
331 pass_to_parent(active_c, active_p, i);
332 }
333
334 /*
335 * If parent has any active paths, put it on the queue (if not already).
336 */
337 if (!bitmap_is_empty(active_p) && !(parent->object.flags & PARENT1)) {
338 parent->object.flags |= PARENT1;
339 prio_queue_put(queue, parent);
340 }
341 if (!(parent->object.flags & PARENT1))
342 active_paths_free(lm, parent);
343
344 MEMZERO_ARRAY(lm->scratch->words, lm->scratch->word_alloc);
345 diff_queue_clear(&diff_queued_diff);
346 }
347
348 static int last_modified_run(struct last_modified *lm)
349 {
350 int max_count, queue_popped = 0;
351 struct commit *c, *n;
352 struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
353 struct prio_queue not_queue = { compare_commits_by_gen_then_commit_date };
354 struct commit_list *list;
355 struct last_modified_callback_data data = { .lm = lm };
356
357 lm->rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;
358 lm->rev.diffopt.format_callback = last_modified_diff;
359 lm->rev.diffopt.format_callback_data = &data;
360 lm->rev.no_walk = 1;
361
362 prepare_revision_walk(&lm->rev);
363
364 /*
365 * prepare_revision_walk() clears bloom_filter_settings for pathspecs
366 * without a Bloom key. Restore it so the per-path check keeps working.
367 */
368 if (!lm->rev.bloom_filter_settings)
369 lm->rev.bloom_filter_settings =
370 get_bloom_filter_settings(lm->rev.repo);
371
372 max_count = lm->rev.max_count;
373
374 init_active_paths_for_commit(&lm->active_paths);
375 lm->scratch = bitmap_word_alloc(lm->all_paths_nr);
376
377 /*
378 * lm->rev.commits holds the set of boundary commits for our walk.
379 *
380 * Loop through each such commit, and place it in the appropriate queue.
381 */
382 for (list = lm->rev.commits; list; list = list->next) {
383 struct commit *c = list->item;
384
385 if (c->object.flags & BOTTOM) {
386 prio_queue_put(&not_queue, c);
387 c->object.flags |= PARENT2;
388 } else if (!(c->object.flags & PARENT1)) {
389 /*
390 * If the commit is a starting point (and hasn't been
391 * seen yet), then initialize the set of interesting
392 * paths, too.
393 */
394 struct bitmap *active;
395
396 prio_queue_put(&queue, c);
397 c->object.flags |= PARENT1;
398
399 active = active_paths_for(lm, c);
400 for (size_t i = 0; i < lm->all_paths_nr; i++)
401 bitmap_set(active, i);
402 }
403 }
404
405 while ((c = prio_queue_get(&queue))) {
406 int parent_i;
407 struct commit_list *p;
408 struct bitmap *active_c = active_paths_for(lm, c);
409
410 if ((0 <= max_count && max_count < ++queue_popped) ||
411 (c->object.flags & PARENT2)) {
412 /*
413 * Either a boundary commit, or we have already seen too
414 * many others. Either way, stop here.
415 */
416 c->object.flags |= PARENT2 | BOUNDARY;
417 data.commit = c;
418 diff_tree_oid(lm->rev.repo->hash_algo->empty_tree,
419 &c->object.oid,
420 "", &lm->rev.diffopt);
421 diff_flush(&lm->rev.diffopt);
422 goto cleanup;
423 }
424
425 /*
426 * Otherwise, make sure that 'c' isn't reachable from anything
427 * in the '--not' queue.
428 */
429 if (repo_parse_commit(lm->rev.repo, c))
430 continue;
431
432 while ((n = prio_queue_get(&not_queue))) {
433 struct commit_list *np;
434
435 if (repo_parse_commit(lm->rev.repo, n))
436 continue;
437
438 for (np = n->parents; np; np = np->next) {
439 if (!(np->item->object.flags & PARENT2)) {
440 prio_queue_put(&not_queue, np->item);
441 np->item->object.flags |= PARENT2;
442 }
443 }
444
445 if (commit_graph_generation(n) < commit_graph_generation(c))
446 break;
447 }
448
449 /*
450 * Look at each parent and pass on each path that's TREESAME
451 * with that parent. Stop early when no active paths remain.
452 */
453 for (p = c->parents, parent_i = 0; p; p = p->next, parent_i++) {
454 process_parent(lm, &queue,
455 c, active_c,
456 p->item, parent_i);
457
458 if (bitmap_is_empty(active_c))
459 break;
460 }
461
462 /*
463 * Paths that remain active, or not TREESAME with any parent,
464 * were changed by 'c'.
465 */
466 if (!bitmap_is_empty(active_c)) {
467 data.commit = c;
468 for (size_t i = 0; i < lm->all_paths_nr; i++) {
469 if (bitmap_get(active_c, i))
470 mark_path(lm->all_paths[i], NULL, &data);
471 }
472 }
473
474 cleanup:
475 active_paths_free(lm, c);
476 }
477
478 if (hashmap_get_size(&lm->paths))
479 BUG("paths remaining beyond boundary in last-modified");
480
481 clear_prio_queue(&not_queue);
482 clear_prio_queue(&queue);
483 clear_active_paths_for_commit(&lm->active_paths);
484 bitmap_free(lm->scratch);
485
486 return 0;
487 }
488
489 static int last_modified_init(struct last_modified *lm, struct repository *r,
490 const char *prefix, int argc, const char **argv)
491 {
492 struct hashmap_iter iter;
493 struct last_modified_entry *ent;
494
495 hashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);
496
497 repo_init_revisions(r, &lm->rev, prefix);
498 lm->rev.def = "HEAD";
499 lm->rev.combine_merges = 1;
500 lm->rev.show_root_diff = 1;
501 lm->rev.boundary = 1;
502 lm->rev.no_commit_id = 1;
503 lm->rev.diff = 1;
504 lm->rev.diffopt.flags.no_recursive_diff_tree_combined = 1;
505 lm->rev.diffopt.flags.recursive = 1;
506 lm->rev.diffopt.flags.tree_in_recursive = lm->show_trees;
507 lm->rev.diffopt.max_depth = lm->max_depth;
508 lm->rev.diffopt.max_depth_valid = lm->max_depth >= 0;
509
510 argc = setup_revisions(argc, argv, &lm->rev, NULL);
511 if (argc > 1) {
512 error(_("unknown last-modified argument: %s"), argv[1]);
513 return argc;
514 }
515
516 lm->rev.bloom_filter_settings = get_bloom_filter_settings(lm->rev.repo);
517
518 if (populate_paths_from_revs(lm) < 0)
519 return -1;
520
521 CALLOC_ARRAY(lm->all_paths, hashmap_get_size(&lm->paths));
522 lm->all_paths_nr = 0;
523 hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
524 ent->diff_idx = lm->all_paths_nr++;
525 lm->all_paths[ent->diff_idx] = ent->path;
526 }
527
528 return 0;
529 }
530
531 int cmd_last_modified(int argc, const char **argv, const char *prefix,
532 struct repository *repo)
533 {
534 int ret;
535 struct last_modified lm = { 0 };
536
537 const char * const last_modified_usage[] = {
538 N_("git last-modified [--recursive] [--show-trees] [--max-depth=<depth>] [-z]\n"
539 " [<revision-range>] [[--] <pathspec>...]"),
540 NULL
541 };
542
543 struct option last_modified_options[] = {
544 OPT_SET_INT('r', "recursive", &lm.max_depth,
545 N_("recurse into subtrees"), -1),
546 OPT_BOOL('t', "show-trees", &lm.show_trees,
547 N_("show tree entries when recursing into subtrees")),
548 OPT_INTEGER_F(0, "max-depth", &lm.max_depth,
549 N_("maximum tree depth to recurse"), PARSE_OPT_NONEG),
550 OPT_BOOL('z', NULL, &lm.nul_termination,
551 N_("lines are separated with NUL character")),
552 OPT_END()
553 };
554
555 argc = parse_options(argc, argv, prefix, last_modified_options,
556 last_modified_usage,
557 PARSE_OPT_KEEP_ARGV0 | PARSE_OPT_KEEP_UNKNOWN_OPT |
558 PARSE_OPT_KEEP_DASHDASH);
559
560 repo_config(repo, git_default_config, NULL);
561
562 ret = last_modified_init(&lm, repo, prefix, argc, argv);
563 if (ret > 0)
564 usage_with_options(last_modified_usage,
565 last_modified_options);
566 if (ret)
567 goto out;
568
569 ret = last_modified_run(&lm);
570 if (ret)
571 goto out;
572
573 out:
574 last_modified_release(&lm);
575
576 return ret;
577 }