10 #include "list-objects.h"
11 #include "list-objects-filter.h"
12 #include "list-objects-filter-options.h"
15 #include "object-store.h"
17 /* Remember to update object flag allocation in object.h */
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
27 #define FILTER_SHOWN_BUT_REVISIT (1<<21)
30 struct filter
*filter
;
33 struct object_id skip_tree
;
34 unsigned is_skipping_tree
: 1;
38 enum list_objects_filter_result (*filter_object_fn
)(
40 enum list_objects_filter_situation filter_situation
,
48 * Optional. If this function is supplied and the filter needs
49 * to collect omits, then this function is called once before
52 * This is required because the following two conditions hold:
54 * a. A tree filter can add and remove objects as an object
56 * b. A combine filter's omit set is the union of all its
57 * subfilters, which may include tree: filters.
59 * As such, the omits sets must be separate sets, and can only
60 * be unioned after the traversal is completed.
62 void (*finalize_omits_fn
)(struct oidset
*omits
, void *filter_data
);
64 void (*free_fn
)(void *filter_data
);
68 /* If non-NULL, the filter collects a list of the omitted OIDs here. */
72 static enum list_objects_filter_result
filter_blobs_none(
74 enum list_objects_filter_situation filter_situation
,
81 switch (filter_situation
) {
83 BUG("unknown filter_situation: %d", filter_situation
);
86 assert(obj
->type
== OBJ_TREE
);
87 /* always include all tree objects */
88 return LOFR_MARK_SEEN
| LOFR_DO_SHOW
;
91 assert(obj
->type
== OBJ_TREE
);
95 assert(obj
->type
== OBJ_BLOB
);
96 assert((obj
->flags
& SEEN
) == 0);
99 oidset_insert(omits
, &obj
->oid
);
100 return LOFR_MARK_SEEN
; /* but not LOFR_DO_SHOW (hard omit) */
104 static void filter_blobs_none__init(
105 struct list_objects_filter_options
*filter_options
,
106 struct filter
*filter
)
108 filter
->filter_object_fn
= filter_blobs_none
;
109 filter
->free_fn
= free
;
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.
116 struct filter_trees_depth_data
{
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.
122 * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
123 * it from being traversed at shallower depths.
125 struct oidmap seen_at_depth
;
127 unsigned long exclude_depth
;
128 unsigned long current_depth
;
131 struct seen_map_entry
{
132 struct oidmap_entry base
;
136 /* Returns 1 if the oid was in the omits set before it was invoked. */
137 static int filter_trees_update_omits(
139 struct oidset
*omits
,
146 return oidset_remove(omits
, &obj
->oid
);
148 return oidset_insert(omits
, &obj
->oid
);
151 static enum list_objects_filter_result
filter_trees_depth(
152 struct repository
*r
,
153 enum list_objects_filter_situation filter_situation
,
155 const char *pathname
,
156 const char *filename
,
157 struct oidset
*omits
,
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
;
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.
172 switch (filter_situation
) {
174 BUG("unknown filter_situation: %d", filter_situation
);
177 assert(obj
->type
== OBJ_TREE
);
178 filter_data
->current_depth
--;
182 filter_trees_update_omits(obj
, omits
, include_it
);
183 return include_it
? LOFR_MARK_SEEN
| LOFR_DO_SHOW
: LOFR_ZERO
;
185 case LOFS_BEGIN_TREE
:
186 seen_info
= oidmap_get(
187 &filter_data
->seen_at_depth
, &obj
->oid
);
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
);
196 filter_data
->current_depth
>= seen_info
->depth
;
200 filter_res
= LOFR_SKIP_TREE
;
202 int been_omitted
= filter_trees_update_omits(
203 obj
, omits
, include_it
);
204 seen_info
->depth
= filter_data
->current_depth
;
207 filter_res
= LOFR_DO_SHOW
;
208 else if (omits
&& !been_omitted
)
210 * Must update omit information of children
211 * recursively; they have not been omitted yet.
213 filter_res
= LOFR_ZERO
;
215 filter_res
= LOFR_SKIP_TREE
;
218 filter_data
->current_depth
++;
223 static void filter_trees_free(void *filter_data
) {
224 struct filter_trees_depth_data
*d
= filter_data
;
227 oidmap_free(&d
->seen_at_depth
, 1);
231 static void filter_trees_depth__init(
232 struct list_objects_filter_options
*filter_options
,
233 struct filter
*filter
)
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;
240 filter
->filter_data
= d
;
241 filter
->filter_object_fn
= filter_trees_depth
;
242 filter
->free_fn
= filter_trees_free
;
246 * A filter for list-objects to omit large blobs.
247 * And to OPTIONALLY collect a list of the omitted OIDs.
249 struct filter_blobs_limit_data
{
250 unsigned long max_bytes
;
253 static enum list_objects_filter_result
filter_blobs_limit(
254 struct repository
*r
,
255 enum list_objects_filter_situation filter_situation
,
257 const char *pathname
,
258 const char *filename
,
259 struct oidset
*omits
,
262 struct filter_blobs_limit_data
*filter_data
= filter_data_
;
263 unsigned long object_length
;
266 switch (filter_situation
) {
268 BUG("unknown filter_situation: %d", filter_situation
);
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
;
276 assert(obj
->type
== OBJ_TREE
);
280 assert(obj
->type
== OBJ_BLOB
);
281 assert((obj
->flags
& SEEN
) == 0);
283 t
= oid_object_info(r
, &obj
->oid
, &object_length
);
284 if (t
!= OBJ_BLOB
) { /* probably OBJ_NONE */
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
294 if (object_length
< filter_data
->max_bytes
)
298 oidset_insert(omits
, &obj
->oid
);
299 return LOFR_MARK_SEEN
; /* but not LOFR_DO_SHOW (hard omit) */
304 oidset_remove(omits
, &obj
->oid
);
305 return LOFR_MARK_SEEN
| LOFR_DO_SHOW
;
308 static void filter_blobs_limit__init(
309 struct list_objects_filter_options
*filter_options
,
310 struct filter
*filter
)
312 struct filter_blobs_limit_data
*d
= xcalloc(1, sizeof(*d
));
313 d
->max_bytes
= filter_options
->blob_limit_value
;
315 filter
->filter_data
= d
;
316 filter
->filter_object_fn
= filter_blobs_limit
;
317 filter
->free_fn
= free
;
321 * A filter driven by a sparse-checkout specification to only
322 * include blobs that a sparse checkout would populate.
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
331 * defval 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.
339 * 1 if the directory (recursively) contains any provisionally
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.
346 unsigned child_prov_omit
: 1;
349 struct filter_sparse_data
{
350 struct exclude_list el
;
353 struct frame
*array_frame
;
356 static enum list_objects_filter_result
filter_sparse(
357 struct repository
*r
,
358 enum list_objects_filter_situation filter_situation
,
360 const char *pathname
,
361 const char *filename
,
362 struct oidset
*omits
,
365 struct filter_sparse_data
*filter_data
= filter_data_
;
369 switch (filter_situation
) {
371 BUG("unknown filter_situation: %d", filter_situation
);
373 case LOFS_BEGIN_TREE
:
374 assert(obj
->type
== OBJ_TREE
);
376 val
= is_excluded_from_list(pathname
, strlen(pathname
),
377 filename
, &dtype
, &filter_data
->el
,
380 val
= filter_data
->array_frame
[filter_data
->nr
- 1].defval
;
382 ALLOC_GROW(filter_data
->array_frame
, filter_data
->nr
+ 1,
384 filter_data
->array_frame
[filter_data
->nr
].defval
= val
;
385 filter_data
->array_frame
[filter_data
->nr
].child_prov_omit
= 0;
389 * A directory with this tree OID may appear in multiple
390 * places in the tree. (Think of a directory move or copy,
391 * with no other changes, so the OID is the same, but the
392 * full pathnames of objects within this directory are new
393 * and may match is_excluded() patterns differently.)
394 * So we cannot mark this directory as SEEN (yet), since
395 * that will prevent process_tree() from revisiting this
396 * tree object with other pathname prefixes.
398 * Only _DO_SHOW the tree object the first time we visit
401 * We always show all tree objects. A future optimization
402 * may want to attempt to narrow this.
404 if (obj
->flags
& FILTER_SHOWN_BUT_REVISIT
)
406 obj
->flags
|= FILTER_SHOWN_BUT_REVISIT
;
410 assert(obj
->type
== OBJ_TREE
);
411 assert(filter_data
->nr
> 1);
413 frame
= &filter_data
->array_frame
[--filter_data
->nr
];
416 * Tell our parent directory if any of our children were
417 * provisionally omitted.
419 filter_data
->array_frame
[filter_data
->nr
- 1].child_prov_omit
|=
420 frame
->child_prov_omit
;
423 * If there are NO provisionally omitted child objects (ALL child
424 * objects in this folder were INCLUDED), then we can mark the
425 * folder as SEEN (so we will not have to revisit it again).
427 if (!frame
->child_prov_omit
)
428 return LOFR_MARK_SEEN
;
432 assert(obj
->type
== OBJ_BLOB
);
433 assert((obj
->flags
& SEEN
) == 0);
435 frame
= &filter_data
->array_frame
[filter_data
->nr
- 1];
438 val
= is_excluded_from_list(pathname
, strlen(pathname
),
439 filename
, &dtype
, &filter_data
->el
,
445 oidset_remove(omits
, &obj
->oid
);
446 return LOFR_MARK_SEEN
| LOFR_DO_SHOW
;
450 * Provisionally omit it. We've already established that
451 * this pathname is not in the sparse-checkout specification
452 * with the CURRENT pathname, so we *WANT* to omit this blob.
454 * However, a pathname elsewhere in the tree may also
455 * reference this same blob, so we cannot reject it yet.
456 * Leave the LOFR_ bits unset so that if the blob appears
457 * again in the traversal, we will be asked again.
460 oidset_insert(omits
, &obj
->oid
);
463 * Remember that at least 1 blob in this tree was
464 * provisionally omitted. This prevents us from short
465 * cutting the tree in future iterations.
467 frame
->child_prov_omit
= 1;
473 static void filter_sparse_free(void *filter_data
)
475 struct filter_sparse_data
*d
= filter_data
;
476 free(d
->array_frame
);
480 static void filter_sparse_oid__init(
481 struct list_objects_filter_options
*filter_options
,
482 struct filter
*filter
)
484 struct filter_sparse_data
*d
= xcalloc(1, sizeof(*d
));
485 if (add_excludes_from_blob_to_list(filter_options
->sparse_oid_value
,
486 NULL
, 0, &d
->el
) < 0)
487 die("could not load filter specification");
489 ALLOC_GROW(d
->array_frame
, d
->nr
+ 1, d
->alloc
);
490 d
->array_frame
[d
->nr
].defval
= 0; /* default to include */
491 d
->array_frame
[d
->nr
].child_prov_omit
= 0;
494 filter
->filter_data
= d
;
495 filter
->filter_object_fn
= filter_sparse
;
496 filter
->free_fn
= filter_sparse_free
;
499 /* A filter which only shows objects shown by all sub-filters. */
500 struct combine_filter_data
{
501 struct subfilter
*sub
;
505 static enum list_objects_filter_result
process_subfilter(
506 struct repository
*r
,
507 enum list_objects_filter_situation filter_situation
,
509 const char *pathname
,
510 const char *filename
,
511 struct subfilter
*sub
)
513 enum list_objects_filter_result result
;
516 * Check and update is_skipping_tree before oidset_contains so
517 * that is_skipping_tree gets unset even when the object is
518 * marked as seen. As of this writing, no filter uses
519 * LOFR_MARK_SEEN on trees that also uses LOFR_SKIP_TREE, so the
520 * ordering is only theoretically important. Be cautious if you
521 * change the order of the below checks and more filters have
524 if (sub
->is_skipping_tree
) {
525 if (filter_situation
== LOFS_END_TREE
&&
526 oideq(&obj
->oid
, &sub
->skip_tree
))
527 sub
->is_skipping_tree
= 0;
531 if (oidset_contains(&sub
->seen
, &obj
->oid
))
534 result
= list_objects_filter__filter_object(
535 r
, filter_situation
, obj
, pathname
, filename
, sub
->filter
);
537 if (result
& LOFR_MARK_SEEN
)
538 oidset_insert(&sub
->seen
, &obj
->oid
);
540 if (result
& LOFR_SKIP_TREE
) {
541 sub
->is_skipping_tree
= 1;
542 sub
->skip_tree
= obj
->oid
;
548 static enum list_objects_filter_result
filter_combine(
549 struct repository
*r
,
550 enum list_objects_filter_situation filter_situation
,
552 const char *pathname
,
553 const char *filename
,
554 struct oidset
*omits
,
557 struct combine_filter_data
*d
= filter_data
;
558 enum list_objects_filter_result combined_result
=
559 LOFR_DO_SHOW
| LOFR_MARK_SEEN
| LOFR_SKIP_TREE
;
562 for (sub
= 0; sub
< d
->nr
; sub
++) {
563 enum list_objects_filter_result sub_result
= process_subfilter(
564 r
, filter_situation
, obj
, pathname
, filename
,
566 if (!(sub_result
& LOFR_DO_SHOW
))
567 combined_result
&= ~LOFR_DO_SHOW
;
568 if (!(sub_result
& LOFR_MARK_SEEN
))
569 combined_result
&= ~LOFR_MARK_SEEN
;
570 if (!d
->sub
[sub
].is_skipping_tree
)
571 combined_result
&= ~LOFR_SKIP_TREE
;
574 return combined_result
;
577 static void filter_combine__free(void *filter_data
)
579 struct combine_filter_data
*d
= filter_data
;
581 for (sub
= 0; sub
< d
->nr
; sub
++) {
582 list_objects_filter__free(d
->sub
[sub
].filter
);
583 oidset_clear(&d
->sub
[sub
].seen
);
584 if (d
->sub
[sub
].omits
.set
.size
)
585 BUG("expected oidset to be cleared already");
590 static void add_all(struct oidset
*dest
, struct oidset
*src
) {
591 struct oidset_iter iter
;
592 struct object_id
*src_oid
;
594 oidset_iter_init(src
, &iter
);
595 while ((src_oid
= oidset_iter_next(&iter
)) != NULL
)
596 oidset_insert(dest
, src_oid
);
599 static void filter_combine__finalize_omits(
600 struct oidset
*omits
,
603 struct combine_filter_data
*d
= filter_data
;
606 for (sub
= 0; sub
< d
->nr
; sub
++) {
607 add_all(omits
, &d
->sub
[sub
].omits
);
608 oidset_clear(&d
->sub
[sub
].omits
);
612 static void filter_combine__init(
613 struct list_objects_filter_options
*filter_options
,
614 struct filter
* filter
)
616 struct combine_filter_data
*d
= xcalloc(1, sizeof(*d
));
619 d
->nr
= filter_options
->sub_nr
;
620 d
->sub
= xcalloc(d
->nr
, sizeof(*d
->sub
));
621 for (sub
= 0; sub
< d
->nr
; sub
++)
622 d
->sub
[sub
].filter
= list_objects_filter__init(
623 filter
->omits
? &d
->sub
[sub
].omits
: NULL
,
624 &filter_options
->sub
[sub
]);
626 filter
->filter_data
= d
;
627 filter
->filter_object_fn
= filter_combine
;
628 filter
->free_fn
= filter_combine__free
;
629 filter
->finalize_omits_fn
= filter_combine__finalize_omits
;
632 typedef void (*filter_init_fn
)(
633 struct list_objects_filter_options
*filter_options
,
634 struct filter
*filter
);
637 * Must match "enum list_objects_filter_choice".
639 static filter_init_fn s_filters
[] = {
641 filter_blobs_none__init
,
642 filter_blobs_limit__init
,
643 filter_trees_depth__init
,
644 filter_sparse_oid__init
,
645 filter_combine__init
,
648 struct filter
*list_objects_filter__init(
649 struct oidset
*omitted
,
650 struct list_objects_filter_options
*filter_options
)
652 struct filter
*filter
;
653 filter_init_fn init_fn
;
655 assert((sizeof(s_filters
) / sizeof(s_filters
[0])) == LOFC__COUNT
);
657 if (filter_options
->choice
>= LOFC__COUNT
)
658 BUG("invalid list-objects filter choice: %d",
659 filter_options
->choice
);
661 init_fn
= s_filters
[filter_options
->choice
];
665 filter
= xcalloc(1, sizeof(*filter
));
666 filter
->omits
= omitted
;
667 init_fn(filter_options
, filter
);
671 enum list_objects_filter_result
list_objects_filter__filter_object(
672 struct repository
*r
,
673 enum list_objects_filter_situation filter_situation
,
675 const char *pathname
,
676 const char *filename
,
677 struct filter
*filter
)
679 if (filter
&& (obj
->flags
& NOT_USER_GIVEN
))
680 return filter
->filter_object_fn(r
, filter_situation
, obj
,
683 filter
->filter_data
);
685 * No filter is active or user gave object explicitly. In this case,
686 * always show the object (except when LOFS_END_TREE, since this tree
687 * had already been shown when LOFS_BEGIN_TREE).
689 if (filter_situation
== LOFS_END_TREE
)
691 return LOFR_MARK_SEEN
| LOFR_DO_SHOW
;
694 void list_objects_filter__free(struct filter
*filter
)
698 if (filter
->finalize_omits_fn
&& filter
->omits
)
699 filter
->finalize_omits_fn(filter
->omits
, filter
->filter_data
);
700 filter
->free_fn(filter
->filter_data
);