git.oblomov.eu Git - git/blob - 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 filter {
  30         enum list_objects_filter_result (*filter_object_fn)(
  31                 struct repository *r,
  32                 enum list_objects_filter_situation filter_situation,
  33                 struct object *obj,
  34                 const char *pathname,
  35                 const char *filename,
  36                 void *filter_data);
  37
  38         void (*free_fn)(void *filter_data);
  39
  40         void *filter_data;
  41 };
  42
  43 /*
  44  * A filter for list-objects to omit ALL blobs from the traversal.
  45  * And to OPTIONALLY collect a list of the omitted OIDs.
  46  */
  47 struct filter_blobs_none_data {
  48         struct oidset *omits;
  49 };
  50
  51 static enum list_objects_filter_result filter_blobs_none(
  52         struct repository *r,
  53         enum list_objects_filter_situation filter_situation,
  54         struct object *obj,
  55         const char *pathname,
  56         const char *filename,
  57         void *filter_data_)
  58 {
  59         struct filter_blobs_none_data *filter_data = filter_data_;
  60
  61         switch (filter_situation) {
  62         default:
  63                 BUG("unknown filter_situation: %d", filter_situation);
  64
  65         case LOFS_BEGIN_TREE:
  66                 assert(obj->type == OBJ_TREE);
  67                 /* always include all tree objects */
  68                 return LOFR_MARK_SEEN | LOFR_DO_SHOW;
  69
  70         case LOFS_END_TREE:
  71                 assert(obj->type == OBJ_TREE);
  72                 return LOFR_ZERO;
  73
  74         case LOFS_BLOB:
  75                 assert(obj->type == OBJ_BLOB);
  76                 assert((obj->flags & SEEN) == 0);
  77
  78                 if (filter_data->omits)
  79                         oidset_insert(filter_data->omits, &obj->oid);
  80                 return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
  81         }
  82 }
  83
  84 static void filter_blobs_none__init(
  85         struct oidset *omitted,
  86         struct list_objects_filter_options *filter_options,
  87         struct filter *filter)
  88 {
  89         struct filter_blobs_none_data *d = xcalloc(1, sizeof(*d));
  90         d->omits = omitted;
  91
  92         filter->filter_data = d;
  93         filter->filter_object_fn = filter_blobs_none;
  94         filter->free_fn = free;
  95 }
  96
  97 /*
  98  * A filter for list-objects to omit ALL trees and blobs from the traversal.
  99  * Can OPTIONALLY collect a list of the omitted OIDs.
 100  */
 101 struct filter_trees_depth_data {
 102         struct oidset *omits;
 103
 104         /*
 105          * Maps trees to the minimum depth at which they were seen. It is not
 106          * necessary to re-traverse a tree at deeper or equal depths than it has
 107          * already been traversed.
 108          *
 109          * We can't use LOFR_MARK_SEEN for tree objects since this will prevent
 110          * it from being traversed at shallower depths.
 111          */
 112         struct oidmap seen_at_depth;
 113
 114         unsigned long exclude_depth;
 115         unsigned long current_depth;
 116 };
 117
 118 struct seen_map_entry {
 119         struct oidmap_entry base;
 120         size_t depth;
 121 };
 122
 123 /* Returns 1 if the oid was in the omits set before it was invoked. */
 124 static int filter_trees_update_omits(
 125         struct object *obj,
 126         struct filter_trees_depth_data *filter_data,
 127         int include_it)
 128 {
 129         if (!filter_data->omits)
 130                 return 0;
 131
 132         if (include_it)
 133                 return oidset_remove(filter_data->omits, &obj->oid);
 134         else
 135                 return oidset_insert(filter_data->omits, &obj->oid);
 136 }
 137
 138 static enum list_objects_filter_result filter_trees_depth(
 139         struct repository *r,
 140         enum list_objects_filter_situation filter_situation,
 141         struct object *obj,
 142         const char *pathname,
 143         const char *filename,
 144         void *filter_data_)
 145 {
 146         struct filter_trees_depth_data *filter_data = filter_data_;
 147         struct seen_map_entry *seen_info;
 148         int include_it = filter_data->current_depth <
 149                 filter_data->exclude_depth;
 150         int filter_res;
 151         int already_seen;
 152
 153         /*
 154          * Note that we do not use _MARK_SEEN in order to allow re-traversal in
 155          * case we encounter a tree or blob again at a shallower depth.
 156          */
 157
 158         switch (filter_situation) {
 159         default:
 160                 BUG("unknown filter_situation: %d", filter_situation);
 161
 162         case LOFS_END_TREE:
 163                 assert(obj->type == OBJ_TREE);
 164                 filter_data->current_depth--;
 165                 return LOFR_ZERO;
 166
 167         case LOFS_BLOB:
 168                 filter_trees_update_omits(obj, filter_data, include_it);
 169                 return include_it ? LOFR_MARK_SEEN | LOFR_DO_SHOW : LOFR_ZERO;
 170
 171         case LOFS_BEGIN_TREE:
 172                 seen_info = oidmap_get(
 173                         &filter_data->seen_at_depth, &obj->oid);
 174                 if (!seen_info) {
 175                         seen_info = xcalloc(1, sizeof(*seen_info));
 176                         oidcpy(&seen_info->base.oid, &obj->oid);
 177                         seen_info->depth = filter_data->current_depth;
 178                         oidmap_put(&filter_data->seen_at_depth, seen_info);
 179                         already_seen = 0;
 180                 } else {
 181                         already_seen =
 182                                 filter_data->current_depth >= seen_info->depth;
 183                 }
 184
 185                 if (already_seen) {
 186                         filter_res = LOFR_SKIP_TREE;
 187                 } else {
 188                         int been_omitted = filter_trees_update_omits(
 189                                 obj, filter_data, include_it);
 190                         seen_info->depth = filter_data->current_depth;
 191
 192                         if (include_it)
 193                                 filter_res = LOFR_DO_SHOW;
 194                         else if (filter_data->omits && !been_omitted)
 195                                 /*
 196                                  * Must update omit information of children
 197                                  * recursively; they have not been omitted yet.
 198                                  */
 199                                 filter_res = LOFR_ZERO;
 200                         else
 201                                 filter_res = LOFR_SKIP_TREE;
 202                 }
 203
 204                 filter_data->current_depth++;
 205                 return filter_res;
 206         }
 207 }
 208
 209 static void filter_trees_free(void *filter_data) {
 210         struct filter_trees_depth_data *d = filter_data;
 211         if (!d)
 212                 return;
 213         oidmap_free(&d->seen_at_depth, 1);
 214         free(d);
 215 }
 216
 217 static void filter_trees_depth__init(
 218         struct oidset *omitted,
 219         struct list_objects_filter_options *filter_options,
 220         struct filter *filter)
 221 {
 222         struct filter_trees_depth_data *d = xcalloc(1, sizeof(*d));
 223         d->omits = omitted;
 224         oidmap_init(&d->seen_at_depth, 0);
 225         d->exclude_depth = filter_options->tree_exclude_depth;
 226         d->current_depth = 0;
 227
 228         filter->filter_data = d;
 229         filter->filter_object_fn = filter_trees_depth;
 230         filter->free_fn = filter_trees_free;
 231 }
 232
 233 /*
 234  * A filter for list-objects to omit large blobs.
 235  * And to OPTIONALLY collect a list of the omitted OIDs.
 236  */
 237 struct filter_blobs_limit_data {
 238         struct oidset *omits;
 239         unsigned long max_bytes;
 240 };
 241
 242 static enum list_objects_filter_result filter_blobs_limit(
 243         struct repository *r,
 244         enum list_objects_filter_situation filter_situation,
 245         struct object *obj,
 246         const char *pathname,
 247         const char *filename,
 248         void *filter_data_)
 249 {
 250         struct filter_blobs_limit_data *filter_data = filter_data_;
 251         unsigned long object_length;
 252         enum object_type t;
 253
 254         switch (filter_situation) {
 255         default:
 256                 BUG("unknown filter_situation: %d", filter_situation);
 257
 258         case LOFS_BEGIN_TREE:
 259                 assert(obj->type == OBJ_TREE);
 260                 /* always include all tree objects */
 261                 return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 262
 263         case LOFS_END_TREE:
 264                 assert(obj->type == OBJ_TREE);
 265                 return LOFR_ZERO;
 266
 267         case LOFS_BLOB:
 268                 assert(obj->type == OBJ_BLOB);
 269                 assert((obj->flags & SEEN) == 0);
 270
 271                 t = oid_object_info(r, &obj->oid, &object_length);
 272                 if (t != OBJ_BLOB) { /* probably OBJ_NONE */
 273                         /*
 274                          * We DO NOT have the blob locally, so we cannot
 275                          * apply the size filter criteria.  Be conservative
 276                          * and force show it (and let the caller deal with
 277                          * the ambiguity).
 278                          */
 279                         goto include_it;
 280                 }
 281
 282                 if (object_length < filter_data->max_bytes)
 283                         goto include_it;
 284
 285                 if (filter_data->omits)
 286                         oidset_insert(filter_data->omits, &obj->oid);
 287                 return LOFR_MARK_SEEN; /* but not LOFR_DO_SHOW (hard omit) */
 288         }
 289
 290 include_it:
 291         if (filter_data->omits)
 292                 oidset_remove(filter_data->omits, &obj->oid);
 293         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 294 }
 295
 296 static void filter_blobs_limit__init(
 297         struct oidset *omitted,
 298         struct list_objects_filter_options *filter_options,
 299         struct filter *filter)
 300 {
 301         struct filter_blobs_limit_data *d = xcalloc(1, sizeof(*d));
 302         d->omits = omitted;
 303         d->max_bytes = filter_options->blob_limit_value;
 304
 305         filter->filter_data = d;
 306         filter->filter_object_fn = filter_blobs_limit;
 307         filter->free_fn = free;
 308 }
 309
 310 /*
 311  * A filter driven by a sparse-checkout specification to only
 312  * include blobs that a sparse checkout would populate.
 313  *
 314  * The sparse-checkout spec can be loaded from a blob with the
 315  * given OID or from a local pathname.  We allow an OID because
 316  * the repo may be bare or we may be doing the filtering on the
 317  * server.
 318  */
 319 struct frame {
 320         /*
 321          * defval is the usual default include/exclude value that
 322          * should be inherited as we recurse into directories based
 323          * upon pattern matching of the directory itself or of a
 324          * containing directory.
 325          */
 326         int defval;
 327
 328         /*
 329          * 1 if the directory (recursively) contains any provisionally
 330          * omitted objects.
 331          *
 332          * 0 if everything (recursively) contained in this directory
 333          * has been explicitly included (SHOWN) in the result and
 334          * the directory may be short-cut later in the traversal.
 335          */
 336         unsigned child_prov_omit : 1;
 337 };
 338
 339 struct filter_sparse_data {
 340         struct oidset *omits;
 341         struct exclude_list el;
 342
 343         size_t nr, alloc;
 344         struct frame *array_frame;
 345 };
 346
 347 static enum list_objects_filter_result filter_sparse(
 348         struct repository *r,
 349         enum list_objects_filter_situation filter_situation,
 350         struct object *obj,
 351         const char *pathname,
 352         const char *filename,
 353         void *filter_data_)
 354 {
 355         struct filter_sparse_data *filter_data = filter_data_;
 356         int val, dtype;
 357         struct frame *frame;
 358
 359         switch (filter_situation) {
 360         default:
 361                 BUG("unknown filter_situation: %d", filter_situation);
 362
 363         case LOFS_BEGIN_TREE:
 364                 assert(obj->type == OBJ_TREE);
 365                 dtype = DT_DIR;
 366                 val = is_excluded_from_list(pathname, strlen(pathname),
 367                                             filename, &dtype, &filter_data->el,
 368                                             r->index);
 369                 if (val < 0)
 370                         val = filter_data->array_frame[filter_data->nr - 1].defval;
 371
 372                 ALLOC_GROW(filter_data->array_frame, filter_data->nr + 1,
 373                            filter_data->alloc);
 374                 filter_data->array_frame[filter_data->nr].defval = val;
 375                 filter_data->array_frame[filter_data->nr].child_prov_omit = 0;
 376                 filter_data->nr++;
 377
 378                 /*
 379                  * A directory with this tree OID may appear in multiple
 380                  * places in the tree. (Think of a directory move or copy,
 381                  * with no other changes, so the OID is the same, but the
 382                  * full pathnames of objects within this directory are new
 383                  * and may match is_excluded() patterns differently.)
 384                  * So we cannot mark this directory as SEEN (yet), since
 385                  * that will prevent process_tree() from revisiting this
 386                  * tree object with other pathname prefixes.
 387                  *
 388                  * Only _DO_SHOW the tree object the first time we visit
 389                  * this tree object.
 390                  *
 391                  * We always show all tree objects.  A future optimization
 392                  * may want to attempt to narrow this.
 393                  */
 394                 if (obj->flags & FILTER_SHOWN_BUT_REVISIT)
 395                         return LOFR_ZERO;
 396                 obj->flags |= FILTER_SHOWN_BUT_REVISIT;
 397                 return LOFR_DO_SHOW;
 398
 399         case LOFS_END_TREE:
 400                 assert(obj->type == OBJ_TREE);
 401                 assert(filter_data->nr > 1);
 402
 403                 frame = &filter_data->array_frame[--filter_data->nr];
 404
 405                 /*
 406                  * Tell our parent directory if any of our children were
 407                  * provisionally omitted.
 408                  */
 409                 filter_data->array_frame[filter_data->nr - 1].child_prov_omit |=
 410                         frame->child_prov_omit;
 411
 412                 /*
 413                  * If there are NO provisionally omitted child objects (ALL child
 414                  * objects in this folder were INCLUDED), then we can mark the
 415                  * folder as SEEN (so we will not have to revisit it again).
 416                  */
 417                 if (!frame->child_prov_omit)
 418                         return LOFR_MARK_SEEN;
 419                 return LOFR_ZERO;
 420
 421         case LOFS_BLOB:
 422                 assert(obj->type == OBJ_BLOB);
 423                 assert((obj->flags & SEEN) == 0);
 424
 425                 frame = &filter_data->array_frame[filter_data->nr - 1];
 426
 427                 dtype = DT_REG;
 428                 val = is_excluded_from_list(pathname, strlen(pathname),
 429                                             filename, &dtype, &filter_data->el,
 430                                             r->index);
 431                 if (val < 0)
 432                         val = frame->defval;
 433                 if (val > 0) {
 434                         if (filter_data->omits)
 435                                 oidset_remove(filter_data->omits, &obj->oid);
 436                         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 437                 }
 438
 439                 /*
 440                  * Provisionally omit it.  We've already established that
 441                  * this pathname is not in the sparse-checkout specification
 442                  * with the CURRENT pathname, so we *WANT* to omit this blob.
 443                  *
 444                  * However, a pathname elsewhere in the tree may also
 445                  * reference this same blob, so we cannot reject it yet.
 446                  * Leave the LOFR_ bits unset so that if the blob appears
 447                  * again in the traversal, we will be asked again.
 448                  */
 449                 if (filter_data->omits)
 450                         oidset_insert(filter_data->omits, &obj->oid);
 451
 452                 /*
 453                  * Remember that at least 1 blob in this tree was
 454                  * provisionally omitted.  This prevents us from short
 455                  * cutting the tree in future iterations.
 456                  */
 457                 frame->child_prov_omit = 1;
 458                 return LOFR_ZERO;
 459         }
 460 }
 461
 462
 463 static void filter_sparse_free(void *filter_data)
 464 {
 465         struct filter_sparse_data *d = filter_data;
 466         free(d->array_frame);
 467         free(d);
 468 }
 469
 470 static void filter_sparse_oid__init(
 471         struct oidset *omitted,
 472         struct list_objects_filter_options *filter_options,
 473         struct filter *filter)
 474 {
 475         struct filter_sparse_data *d = xcalloc(1, sizeof(*d));
 476         d->omits = omitted;
 477         if (add_excludes_from_blob_to_list(filter_options->sparse_oid_value,
 478                                            NULL, 0, &d->el) < 0)
 479                 die("could not load filter specification");
 480
 481         ALLOC_GROW(d->array_frame, d->nr + 1, d->alloc);
 482         d->array_frame[d->nr].defval = 0; /* default to include */
 483         d->array_frame[d->nr].child_prov_omit = 0;
 484         d->nr++;
 485
 486         filter->filter_data = d;
 487         filter->filter_object_fn = filter_sparse;
 488         filter->free_fn = filter_sparse_free;
 489 }
 490
 491 typedef void (*filter_init_fn)(
 492         struct oidset *omitted,
 493         struct list_objects_filter_options *filter_options,
 494         struct filter *filter);
 495
 496 /*
 497  * Must match "enum list_objects_filter_choice".
 498  */
 499 static filter_init_fn s_filters[] = {
 500         NULL,
 501         filter_blobs_none__init,
 502         filter_blobs_limit__init,
 503         filter_trees_depth__init,
 504         filter_sparse_oid__init,
 505 };
 506
 507 struct filter *list_objects_filter__init(
 508         struct oidset *omitted,
 509         struct list_objects_filter_options *filter_options)
 510 {
 511         struct filter *filter;
 512         filter_init_fn init_fn;
 513
 514         assert((sizeof(s_filters) / sizeof(s_filters[0])) == LOFC__COUNT);
 515
 516         if (filter_options->choice >= LOFC__COUNT)
 517                 BUG("invalid list-objects filter choice: %d",
 518                     filter_options->choice);
 519
 520         init_fn = s_filters[filter_options->choice];
 521         if (!init_fn)
 522                 return NULL;
 523
 524         filter = xcalloc(1, sizeof(*filter));
 525         init_fn(omitted, filter_options, filter);
 526         return filter;
 527 }
 528
 529 enum list_objects_filter_result list_objects_filter__filter_object(
 530         struct repository *r,
 531         enum list_objects_filter_situation filter_situation,
 532         struct object *obj,
 533         const char *pathname,
 534         const char *filename,
 535         struct filter *filter)
 536 {
 537         if (filter && (obj->flags & NOT_USER_GIVEN))
 538                 return filter->filter_object_fn(r, filter_situation, obj,
 539                                                 pathname, filename,
 540                                                 filter->filter_data);
 541         /*
 542          * No filter is active or user gave object explicitly. In this case,
 543          * always show the object (except when LOFS_END_TREE, since this tree
 544          * had already been shown when LOFS_BEGIN_TREE).
 545          */
 546         if (filter_situation == LOFS_END_TREE)
 547                 return 0;
 548         return LOFR_MARK_SEEN | LOFR_DO_SHOW;
 549 }
 550
 551 void list_objects_filter__free(struct filter *filter)
 552 {
 553         if (!filter)
 554                 return;
 555         filter->free_fn(filter->filter_data);
 556         free(filter);
 557 }