Merge branch 'dl/complete-rebase-and-archive'
[git] / list-objects-filter.c
1 #include "cache.h"
2 #include "dir.h"
3 #include "tag.h"
4 #include "commit.h"
5 #include "tree.h"
6 #include "blob.h"
7 #include "diff.h"
8 #include "tree-walk.h"
9 #include "revision.h"
10 #include "list-objects.h"
11 #include "list-objects-filter.h"
12 #include "list-objects-filter-options.h"
13 #include "oidmap.h"
14 #include "oidset.h"
15 #include "object-store.h"
16
17 /* Remember to update object flag allocation in object.h */
18 /*
19  * FILTER_SHOWN_BUT_REVISIT -- we set this bit on tree objects
20  * that have been shown, but should be revisited if they appear
21  * in the traversal (until we mark it SEEN).  This is a way to
22  * let us silently de-dup calls to show() in the caller.  This
23  * is subtly different from the "revision.h:SHOWN" and the
24  * "sha1-name.c:ONELINE_SEEN" bits.  And also different from
25  * the non-de-dup usage in pack-bitmap.c
26  */
27 #define FILTER_SHOWN_BUT_REVISIT (1<<21)
28
29 struct subfilter {
30         struct filter *filter;
31         struct oidset seen;
32         struct oidset omits;
33         struct object_id skip_tree;
34         unsigned is_skipping_tree : 1;
35 };
36
37 struct filter {
38         enum list_objects_filter_result (*filter_object_fn)(
39                 struct repository *r,
40                 enum list_objects_filter_situation filter_situation,
41                 struct object *obj,
42                 const char *pathname,
43                 const char *filename,
44                 struct oidset *omits,
45                 void *filter_data);
46
47         /*
48          * Optional. If this function is supplied and the filter needs
49          * to collect omits, then this function is called once before
50          * free_fn is called.
51          *
52          * This is required because the following two conditions hold:
53          *
54          *   a. A tree filter can add and remove objects as an object
55          *      graph is traversed.
56          *   b. A combine filter's omit set is the union of all its
57          *      subfilters, which may include tree: filters.
58          *
59          * As such, the omits sets must be separate sets, and can only
60          * be unioned after the traversal is completed.
61          */
62         void (*finalize_omits_fn)(struct oidset *omits, void *filter_data);
63
64         void (*free_fn)(void *filter_data);
65
66         void *filter_data;
67
68         /* If non-NULL, the filter collects a list of the omitted OIDs here. */
69         struct oidset *omits;
70 };
71
72 static enum list_objects_filter_result filter_blobs_none(
73         struct repository *r,
74         enum list_objects_filter_situation filter_situation,
75         struct object *obj,
76         const char *pathname,
77         const char *filename,
78         struct oidset *omits,
79         void *filter_data_)
80 {
81         switch (filter_situation) {
82         default:
83                 BUG("unknown filter_situation: %d", filter_situation);
84
85         case LOFS_BEGIN_TREE:
86                 assert(obj->type == OBJ_TREE);
87                 /* always include all tree objects */
88                 return LOFR_MARK_SEEN | LOFR_DO_SHOW;
89
90         case LOFS_END_TREE:
91                 assert(obj->type == OBJ_TREE);
92                 return LOFR_ZERO;
93
94         case LOFS_BLOB:
95                 assert(obj->type == OBJ_BLOB);
96                 assert((obj->flags & SEEN) == 0);
97
98                 if (omits)
99                         oidset_insert(omits, &obj->oid);
100                 return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
101         }
102 }
103
104 static void filter_blobs_none__init(
105         struct list_objects_filter_options *filter_options,
106         struct filter *filter)
107 {
108         filter->filter_object_fn = filter_blobs_none;
109         filter->free_fn = free;
110 }
111
112 /*
113  * A filter for list-objects to omit ALL trees and blobs from the traversal.
114  * Can OPTIONALLY collect a list of the omitted OIDs.
115  */
116 struct filter_trees_depth_data {
117         /*
118          * Maps trees to the minimum depth at which they were seen. It is not
119          * necessary to re-traverse a tree at deeper or equal depths than it has
120          * already been traversed.
121          *
122          * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
123          * it from being traversed at shallower depths.
124          */
125         struct oidmap seen_at_depth;
126
127         unsigned long exclude_depth;
128         unsigned long current_depth;
129 };
130
131 struct seen_map_entry {
132         struct oidmap_entry base;
133         size_t depth;
134 };
135
136 /* Returns 1 if the oid was in the omits set before it was invoked. */
137 static int filter_trees_update_omits(
138         struct object *obj,
139         struct oidset *omits,
140         int include_it)
141 {
142         if (!omits)
143                 return 0;
144
145         if (include_it)
146                 return oidset_remove(omits, &obj->oid);
147         else
148                 return oidset_insert(omits, &obj->oid);
149 }
150
151 static enum list_objects_filter_result filter_trees_depth(
152         struct repository *r,
153         enum list_objects_filter_situation filter_situation,
154         struct object *obj,
155         const char *pathname,
156         const char *filename,
157         struct oidset *omits,
158         void *filter_data_)
159 {
160         struct filter_trees_depth_data *filter_data = filter_data_;
161         struct seen_map_entry *seen_info;
162         int include_it = filter_data->current_depth <
163                 filter_data->exclude_depth;
164         int filter_res;
165         int already_seen;
166
167         /*
168          * Note that we do not use _MARK_SEEN in order to allow re-traversal in
169          * case we encounter a tree or blob again at a shallower depth.
170          */
171
172         switch (filter_situation) {
173         default:
174                 BUG("unknown filter_situation: %d", filter_situation);
175
176         case LOFS_END_TREE:
177                 assert(obj->type == OBJ_TREE);
178                 filter_data->current_depth--;
179                 return LOFR_ZERO;
180
181         case LOFS_BLOB:
182                 filter_trees_update_omits(obj, omits, include_it);
183                 return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;
184
185         case LOFS_BEGIN_TREE:
186                 seen_info = oidmap_get(
187                         &filter_data->seen_at_depth, &obj->oid);
188                 if (!seen_info) {
189                         seen_info = xcalloc(1, sizeof(*seen_info));
190                         oidcpy(&seen_info->base.oid, &obj->oid);
191                         seen_info->depth = filter_data->current_depth;
192                         oidmap_put(&filter_data->seen_at_depth, seen_info);
193                         already_seen = 0;
194                 } else {
195                         already_seen =
196                                 filter_data->current_depth >= seen_info->depth;
197                 }
198
199                 if (already_seen) {
200                         filter_res = LOFR_SKIP_TREE;
201                 } else {
202                         int been_omitted = filter_trees_update_omits(
203                                 obj, omits, include_it);
204                         seen_info->depth = filter_data->current_depth;
205
206                         if (include_it)
207                                 filter_res = LOFR_DO_SHOW;
208                         else if (omits && !been_omitted)
209                                 /*
210                                  * Must update omit information of children
211                                  * recursively; they have not been omitted yet.
212                                  */
213                                 filter_res = LOFR_ZERO;
214                         else
215                                 filter_res = LOFR_SKIP_TREE;
216                 }
217
218                 filter_data->current_depth++;
219                 return filter_res;
220         }
221 }
222
223 static void filter_trees_free(void *filter_data) {
224         struct filter_trees_depth_data *d = filter_data;
225         if (!d)
226                 return;
227         oidmap_free(&d->seen_at_depth, 1);
228         free(d);
229 }
230
231 static void filter_trees_depth__init(
232         struct list_objects_filter_options *filter_options,
233         struct filter *filter)
234 {
235         struct filter_trees_depth_data *d = xcalloc(1, sizeof(*d));
236         oidmap_init(&d->seen_at_depth, 0);
237         d->exclude_depth = filter_options->tree_exclude_depth;
238         d->current_depth = 0;
239
240         filter->filter_data = d;
241         filter->filter_object_fn = filter_trees_depth;
242         filter->free_fn = filter_trees_free;
243 }
244
245 /*
246  * A filter for list-objects to omit large blobs.
247  * And to OPTIONALLY collect a list of the omitted OIDs.
248  */
249 struct filter_blobs_limit_data {
250         unsigned long max_bytes;
251 };
252
253 static enum list_objects_filter_result filter_blobs_limit(
254         struct repository *r,
255         enum list_objects_filter_situation filter_situation,
256         struct object *obj,
257         const char *pathname,
258         const char *filename,
259         struct oidset *omits,
260         void *filter_data_)
261 {
262         struct filter_blobs_limit_data *filter_data = filter_data_;
263         unsigned long object_length;
264         enum object_type t;
265
266         switch (filter_situation) {
267         default:
268                 BUG("unknown filter_situation: %d", filter_situation);
269
270         case LOFS_BEGIN_TREE:
271                 assert(obj->type == OBJ_TREE);
272                 /* always include all tree objects */
273                 return LOFR_MARK_SEEN | LOFR_DO_SHOW;
274
275         case LOFS_END_TREE:
276                 assert(obj->type == OBJ_TREE);
277                 return LOFR_ZERO;
278
279         case LOFS_BLOB:
280                 assert(obj->type == OBJ_BLOB);
281                 assert((obj->flags & SEEN) == 0);
282
283                 t = oid_object_info(r, &obj->oid, &object_length);
284                 if (t != OBJ_BLOB) { /* probably OBJ_NONE */
285                         /*
286                          * We DO NOT have the blob locally, so we cannot
287                          * apply the size filter criteria.  Be conservative
288                          * and force show it (and let the caller deal with
289                          * the ambiguity).
290                          */
291                         goto include_it;
292                 }
293
294                 if (object_length < filter_data->max_bytes)
295                         goto include_it;
296
297                 if (omits)
298                         oidset_insert(omits, &obj->oid);
299                 return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
300         }
301
302 include_it:
303         if (omits)
304                 oidset_remove(omits, &obj->oid);
305         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
306 }
307
308 static void filter_blobs_limit__init(
309         struct list_objects_filter_options *filter_options,
310         struct filter *filter)
311 {
312         struct filter_blobs_limit_data *d = xcalloc(1, sizeof(*d));
313         d->max_bytes = filter_options->blob_limit_value;
314
315         filter->filter_data = d;
316         filter->filter_object_fn = filter_blobs_limit;
317         filter->free_fn = free;
318 }
319
320 /*
321  * A filter driven by a sparse-checkout specification to only
322  * include blobs that a sparse checkout would populate.
323  *
324  * The sparse-checkout spec can be loaded from a blob with the
325  * given OID or from a local pathname.  We allow an OID because
326  * the repo may be bare or we may be doing the filtering on the
327  * server.
328  */
329 struct frame {
330         /*
331          * default_match is the usual default include/exclude value that
332          * should be inherited as we recurse into directories based
333          * upon pattern matching of the directory itself or of a
334          * containing directory.
335          */
336         enum pattern_match_result default_match;
337
338         /*
339          * 1 if the directory (recursively) contains any provisionally
340          * omitted objects.
341          *
342          * 0 if everything (recursively) contained in this directory
343          * has been explicitly included (SHOWN) in the result and
344          * the directory may be short-cut later in the traversal.
345          */
346         unsigned child_prov_omit : 1;
347 };
348
349 struct filter_sparse_data {
350         struct pattern_list pl;
351
352         size_t nr, alloc;
353         struct frame *array_frame;
354 };
355
356 static enum list_objects_filter_result filter_sparse(
357         struct repository *r,
358         enum list_objects_filter_situation filter_situation,
359         struct object *obj,
360         const char *pathname,
361         const char *filename,
362         struct oidset *omits,
363         void *filter_data_)
364 {
365         struct filter_sparse_data *filter_data = filter_data_;
366         int dtype;
367         struct frame *frame;
368         enum pattern_match_result match;
369
370         switch (filter_situation) {
371         default:
372                 BUG("unknown filter_situation: %d", filter_situation);
373
374         case LOFS_BEGIN_TREE:
375                 assert(obj->type == OBJ_TREE);
376                 dtype = DT_DIR;
377                 match = path_matches_pattern_list(pathname, strlen(pathname),
378                                                   filename, &dtype, &filter_data->pl,
379                                                   r->index);
380                 if (match == UNDECIDED)
381                         match = filter_data->array_frame[filter_data->nr - 1].default_match;
382
383                 ALLOC_GROW(filter_data->array_frame, filter_data->nr + 1,
384                            filter_data->alloc);
385                 filter_data->array_frame[filter_data->nr].default_match = match;
386                 filter_data->array_frame[filter_data->nr].child_prov_omit = 0;
387                 filter_data->nr++;
388
389                 /*
390                  * A directory with this tree OID may appear in multiple
391                  * places in the tree. (Think of a directory move or copy,
392                  * with no other changes, so the OID is the same, but the
393                  * full pathnames of objects within this directory are new
394                  * and may match is_excluded() patterns differently.)
395                  * So we cannot mark this directory as SEEN (yet), since
396                  * that will prevent process_tree() from revisiting this
397                  * tree object with other pathname prefixes.
398                  *
399                  * Only _DO_SHOW the tree object the first time we visit
400                  * this tree object.
401                  *
402                  * We always show all tree objects.  A future optimization
403                  * may want to attempt to narrow this.
404                  */
405                 if (obj->flags & FILTER_SHOWN_BUT_REVISIT)
406                         return LOFR_ZERO;
407                 obj->flags |= FILTER_SHOWN_BUT_REVISIT;
408                 return LOFR_DO_SHOW;
409
410         case LOFS_END_TREE:
411                 assert(obj->type == OBJ_TREE);
412                 assert(filter_data->nr > 1);
413
414                 frame = &filter_data->array_frame[--filter_data->nr];
415
416                 /*
417                  * Tell our parent directory if any of our children were
418                  * provisionally omitted.
419                  */
420                 filter_data->array_frame[filter_data->nr - 1].child_prov_omit |=
421                         frame->child_prov_omit;
422
423                 /*
424                  * If there are NO provisionally omitted child objects (ALL child
425                  * objects in this folder were INCLUDED), then we can mark the
426                  * folder as SEEN (so we will not have to revisit it again).
427                  */
428                 if (!frame->child_prov_omit)
429                         return LOFR_MARK_SEEN;
430                 return LOFR_ZERO;
431
432         case LOFS_BLOB:
433                 assert(obj->type == OBJ_BLOB);
434                 assert((obj->flags & SEEN) == 0);
435
436                 frame = &filter_data->array_frame[filter_data->nr - 1];
437
438                 dtype = DT_REG;
439                 match = path_matches_pattern_list(pathname, strlen(pathname),
440                                             filename, &dtype, &filter_data->pl,
441                                             r->index);
442                 if (match == UNDECIDED)
443                         match = frame->default_match;
444                 if (match == MATCHED) {
445                         if (omits)
446                                 oidset_remove(omits, &obj->oid);
447                         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
448                 }
449
450                 /*
451                  * Provisionally omit it.  We've already established that
452                  * this pathname is not in the sparse-checkout specification
453                  * with the CURRENT pathname, so we *WANT* to omit this blob.
454                  *
455                  * However, a pathname elsewhere in the tree may also
456                  * reference this same blob, so we cannot reject it yet.
457                  * Leave the LOFR_ bits unset so that if the blob appears
458                  * again in the traversal, we will be asked again.
459                  */
460                 if (omits)
461                         oidset_insert(omits, &obj->oid);
462
463                 /*
464                  * Remember that at least 1 blob in this tree was
465                  * provisionally omitted.  This prevents us from short
466                  * cutting the tree in future iterations.
467                  */
468                 frame->child_prov_omit = 1;
469                 return LOFR_ZERO;
470         }
471 }
472
473
474 static void filter_sparse_free(void *filter_data)
475 {
476         struct filter_sparse_data *d = filter_data;
477         free(d->array_frame);
478         free(d);
479 }
480
481 static void filter_sparse_oid__init(
482         struct list_objects_filter_options *filter_options,
483         struct filter *filter)
484 {
485         struct filter_sparse_data *d = xcalloc(1, sizeof(*d));
486         struct object_context oc;
487         struct object_id sparse_oid;
488
489         if (get_oid_with_context(the_repository,
490                                  filter_options->sparse_oid_name,
491                                  GET_OID_BLOB, &sparse_oid, &oc))
492                 die(_("unable to access sparse blob in '%s'"),
493                     filter_options->sparse_oid_name);
494         if (add_patterns_from_blob_to_list(&sparse_oid, "", 0, &d->pl) < 0)
495                 die(_("unable to parse sparse filter data in %s"),
496                     oid_to_hex(&sparse_oid));
497
498         ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc);
499         d->array_frame[d->nr].default_match = 0; /* default to include */
500         d->array_frame[d->nr].child_prov_omit = 0;
501         d->nr++;
502
503         filter->filter_data = d;
504         filter->filter_object_fn = filter_sparse;
505         filter->free_fn = filter_sparse_free;
506 }
507
508 /* A filter which only shows objects shown by all sub-filters. */
509 struct combine_filter_data {
510         struct subfilter *sub;
511         size_t nr;
512 };
513
514 static enum list_objects_filter_result process_subfilter(
515         struct repository *r,
516         enum list_objects_filter_situation filter_situation,
517         struct object *obj,
518         const char *pathname,
519         const char *filename,
520         struct subfilter *sub)
521 {
522         enum list_objects_filter_result result;
523
524         /*
525          * Check and update is_skipping_tree before oidset_contains so
526          * that is_skipping_tree gets unset even when the object is
527          * marked as seen.  As of this writing, no filter uses
528          * LOFR_MARK_SEEN on trees that also uses LOFR_SKIP_TREE, so the
529          * ordering is only theoretically important. Be cautious if you
530          * change the order of the below checks and more filters have
531          * been added!
532          */
533         if (sub->is_skipping_tree) {
534                 if (filter_situation == LOFS_END_TREE &&
535                     oideq(&obj->oid, &sub->skip_tree))
536                         sub->is_skipping_tree = 0;
537                 else
538                         return LOFR_ZERO;
539         }
540         if (oidset_contains(&sub->seen, &obj->oid))
541                 return LOFR_ZERO;
542
543         result = list_objects_filter__filter_object(
544                 r, filter_situation, obj, pathname, filename, sub->filter);
545
546         if (result & LOFR_MARK_SEEN)
547                 oidset_insert(&sub->seen, &obj->oid);
548
549         if (result & LOFR_SKIP_TREE) {
550                 sub->is_skipping_tree = 1;
551                 sub->skip_tree = obj->oid;
552         }
553
554         return result;
555 }
556
557 static enum list_objects_filter_result filter_combine(
558         struct repository *r,
559         enum list_objects_filter_situation filter_situation,
560         struct object *obj,
561         const char *pathname,
562         const char *filename,
563         struct oidset *omits,
564         void *filter_data)
565 {
566         struct combine_filter_data *d = filter_data;
567         enum list_objects_filter_result combined_result =
568                 LOFR_DO_SHOW | LOFR_MARK_SEEN | LOFR_SKIP_TREE;
569         size_t sub;
570
571         for (sub = 0; sub < d->nr; sub++) {
572                 enum list_objects_filter_result sub_result = process_subfilter(
573                         r, filter_situation, obj, pathname, filename,
574                         &d->sub[sub]);
575                 if (!(sub_result & LOFR_DO_SHOW))
576                         combined_result &= ~LOFR_DO_SHOW;
577                 if (!(sub_result & LOFR_MARK_SEEN))
578                         combined_result &= ~LOFR_MARK_SEEN;
579                 if (!d->sub[sub].is_skipping_tree)
580                         combined_result &= ~LOFR_SKIP_TREE;
581         }
582
583         return combined_result;
584 }
585
586 static void filter_combine__free(void *filter_data)
587 {
588         struct combine_filter_data *d = filter_data;
589         size_t sub;
590         for (sub = 0; sub < d->nr; sub++) {
591                 list_objects_filter__free(d->sub[sub].filter);
592                 oidset_clear(&d->sub[sub].seen);
593                 if (d->sub[sub].omits.set.size)
594                         BUG("expected oidset to be cleared already");
595         }
596         free(d->sub);
597 }
598
599 static void add_all(struct oidset *dest, struct oidset *src) {
600         struct oidset_iter iter;
601         struct object_id *src_oid;
602
603         oidset_iter_init(src, &iter);
604         while ((src_oid = oidset_iter_next(&iter)) != NULL)
605                 oidset_insert(dest, src_oid);
606 }
607
608 static void filter_combine__finalize_omits(
609         struct oidset *omits,
610         void *filter_data)
611 {
612         struct combine_filter_data *d = filter_data;
613         size_t sub;
614
615         for (sub = 0; sub < d->nr; sub++) {
616                 add_all(omits, &d->sub[sub].omits);
617                 oidset_clear(&d->sub[sub].omits);
618         }
619 }
620
621 static void filter_combine__init(
622         struct list_objects_filter_options *filter_options,
623         struct filter* filter)
624 {
625         struct combine_filter_data *d = xcalloc(1, sizeof(*d));
626         size_t sub;
627
628         d->nr = filter_options->sub_nr;
629         d->sub = xcalloc(d->nr, sizeof(*d->sub));
630         for (sub = 0; sub < d->nr; sub++)
631                 d->sub[sub].filter = list_objects_filter__init(
632                         filter->omits ? &d->sub[sub].omits : NULL,
633                         &filter_options->sub[sub]);
634
635         filter->filter_data = d;
636         filter->filter_object_fn = filter_combine;
637         filter->free_fn = filter_combine__free;
638         filter->finalize_omits_fn = filter_combine__finalize_omits;
639 }
640
641 typedef void (*filter_init_fn)(
642         struct list_objects_filter_options *filter_options,
643         struct filter *filter);
644
645 /*
646  * Must match "enum list_objects_filter_choice".
647  */
648 static filter_init_fn s_filters[] = {
649         NULL,
650         filter_blobs_none__init,
651         filter_blobs_limit__init,
652         filter_trees_depth__init,
653         filter_sparse_oid__init,
654         filter_combine__init,
655 };
656
657 struct filter *list_objects_filter__init(
658         struct oidset *omitted,
659         struct list_objects_filter_options *filter_options)
660 {
661         struct filter *filter;
662         filter_init_fn init_fn;
663
664         assert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT);
665
666         if (filter_options->choice >= LOFC__COUNT)
667                 BUG("invalid list-objects filter choice: %d",
668                     filter_options->choice);
669
670         init_fn = s_filters[filter_options->choice];
671         if (!init_fn)
672                 return NULL;
673
674         filter = xcalloc(1, sizeof(*filter));
675         filter->omits = omitted;
676         init_fn(filter_options, filter);
677         return filter;
678 }
679
680 enum list_objects_filter_result list_objects_filter__filter_object(
681         struct repository *r,
682         enum list_objects_filter_situation filter_situation,
683         struct object *obj,
684         const char *pathname,
685         const char *filename,
686         struct filter *filter)
687 {
688         if (filter && (obj->flags & NOT_USER_GIVEN))
689                 return filter->filter_object_fn(r, filter_situation, obj,
690                                                 pathname, filename,
691                                                 filter->omits,
692                                                 filter->filter_data);
693         /*
694          * No filter is active or user gave object explicitly. In this case,
695          * always show the object (except when LOFS_END_TREE, since this tree
696          * had already been shown when LOFS_BEGIN_TREE).
697          */
698         if (filter_situation == LOFS_END_TREE)
699                 return 0;
700         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
701 }
702
703 void list_objects_filter__free(struct filter *filter)
704 {
705         if (!filter)
706                 return;
707         if (filter->finalize_omits_fn && filter->omits)
708                 filter->finalize_omits_fn(filter->omits, filter->filter_data);
709         filter->free_fn(filter->filter_data);
710         free(filter);
711 }