sparse-index.c

   1 #include "cache.h"
   2 #include "repository.h"
   3 #include "sparse-index.h"
   4 #include "tree.h"
   5 #include "pathspec.h"
   6 #include "trace2.h"
   7 #include "cache-tree.h"
   8 #include "config.h"
   9 #include "dir.h"
  10 #include "fsmonitor.h"
  11
  12 struct modify_index_context {
  13         struct index_state *write;
  14         struct pattern_list *pl;
  15 };
  16
  17 static struct cache_entry *construct_sparse_dir_entry(
  18                                 struct index_state *istate,
  19                                 const char *sparse_dir,
  20                                 struct cache_tree *tree)
  21 {
  22         struct cache_entry *de;
  23
  24         de = make_cache_entry(istate, S_IFDIR, &tree->oid, sparse_dir, 0, 0);
  25
  26         de->ce_flags |= CE_SKIP_WORKTREE;
  27         return de;
  28 }
  29
  30 /*
  31  * Returns the number of entries "inserted" into the index.
  32  */
  33 static int convert_to_sparse_rec(struct index_state *istate,
  34                                  int num_converted,
  35                                  int start, int end,
  36                                  const char *ct_path, size_t ct_pathlen,
  37                                  struct cache_tree *ct)
  38 {
  39         int i, can_convert = 1;
  40         int start_converted = num_converted;
  41         struct strbuf child_path = STRBUF_INIT;
  42
  43         /*
  44          * Is the current path outside of the sparse cone?
  45          * Then check if the region can be replaced by a sparse
  46          * directory entry (everything is sparse and merged).
  47          */
  48         if (path_in_sparse_checkout(ct_path, istate))
  49                 can_convert = 0;
  50
  51         for (i = start; can_convert && i < end; i++) {
  52                 struct cache_entry *ce = istate->cache[i];
  53
  54                 if (ce_stage(ce) ||
  55                     S_ISGITLINK(ce->ce_mode) ||
  56                     !(ce->ce_flags & CE_SKIP_WORKTREE))
  57                         can_convert = 0;
  58         }
  59
  60         if (can_convert) {
  61                 struct cache_entry *se;
  62                 se = construct_sparse_dir_entry(istate, ct_path, ct);
  63
  64                 istate->cache[num_converted++] = se;
  65                 return 1;
  66         }
  67
  68         for (i = start; i < end; ) {
  69                 int count, span, pos = -1;
  70                 const char *base, *slash;
  71                 struct cache_entry *ce = istate->cache[i];
  72
  73                 /*
  74                  * Detect if this is a normal entry outside of any subtree
  75                  * entry.
  76                  */
  77                 base = ce->name + ct_pathlen;
  78                 slash = strchr(base, '/');
  79
  80                 if (slash)
  81                         pos = cache_tree_subtree_pos(ct, base, slash - base);
  82
  83                 if (pos < 0) {
  84                         istate->cache[num_converted++] = ce;
  85                         i++;
  86                         continue;
  87                 }
  88
  89                 strbuf_setlen(&child_path, 0);
  90                 strbuf_add(&child_path, ce->name, slash - ce->name + 1);
  91
  92                 span = ct->down[pos]->cache_tree->entry_count;
  93                 count = convert_to_sparse_rec(istate,
  94                                               num_converted, i, i + span,
  95                                               child_path.buf, child_path.len,
  96                                               ct->down[pos]->cache_tree);
  97                 num_converted += count;
  98                 i += span;
  99         }
 100
 101         strbuf_release(&child_path);
 102         return num_converted - start_converted;
 103 }
 104
 105 int set_sparse_index_config(struct repository *repo, int enable)
 106 {
 107         int res = repo_config_set_worktree_gently(repo,
 108                                                   "index.sparse",
 109                                                   enable ? "true" : "false");
 110         prepare_repo_settings(repo);
 111         repo->settings.sparse_index = enable;
 112         return res;
 113 }
 114
 115 static int index_has_unmerged_entries(struct index_state *istate)
 116 {
 117         int i;
 118         for (i = 0; i < istate->cache_nr; i++) {
 119                 if (ce_stage(istate->cache[i]))
 120                         return 1;
 121         }
 122
 123         return 0;
 124 }
 125
 126 int is_sparse_index_allowed(struct index_state *istate, int flags)
 127 {
 128         if (!core_apply_sparse_checkout || !core_sparse_checkout_cone)
 129                 return 0;
 130
 131         if (!(flags & SPARSE_INDEX_MEMORY_ONLY)) {
 132                 int test_env;
 133
 134                 /*
 135                  * The sparse index is not (yet) integrated with a split index.
 136                  */
 137                 if (istate->split_index || git_env_bool("GIT_TEST_SPLIT_INDEX", 0))
 138                         return 0;
 139                 /*
 140                  * The GIT_TEST_SPARSE_INDEX environment variable triggers the
 141                  * index.sparse config variable to be on.
 142                  */
 143                 test_env = git_env_bool("GIT_TEST_SPARSE_INDEX", -1);
 144                 if (test_env >= 0)
 145                         set_sparse_index_config(istate->repo, test_env);
 146
 147                 /*
 148                  * Only convert to sparse if index.sparse is set.
 149                  */
 150                 prepare_repo_settings(istate->repo);
 151                 if (!istate->repo->settings.sparse_index)
 152                         return 0;
 153         }
 154
 155         if (init_sparse_checkout_patterns(istate))
 156                 return 0;
 157
 158         /*
 159          * We need cone-mode patterns to use sparse-index. If a user edits
 160          * their sparse-checkout file manually, then we can detect during
 161          * parsing that they are not actually using cone-mode patterns and
 162          * hence we need to abort this conversion _without error_. Warnings
 163          * already exist in the pattern parsing to inform the user of their
 164          * bad patterns.
 165          */
 166         if (!istate->sparse_checkout_patterns->use_cone_patterns)
 167                 return 0;
 168
 169         return 1;
 170 }
 171
 172 int convert_to_sparse(struct index_state *istate, int flags)
 173 {
 174         /*
 175          * If the index is already sparse, empty, or otherwise
 176          * cannot be converted to sparse, do not convert.
 177          */
 178         if (istate->sparse_index == INDEX_COLLAPSED || !istate->cache_nr ||
 179             !is_sparse_index_allowed(istate, flags))
 180                 return 0;
 181
 182         /*
 183          * NEEDSWORK: If we have unmerged entries, then stay full.
 184          * Unmerged entries prevent the cache-tree extension from working.
 185          */
 186         if (index_has_unmerged_entries(istate))
 187                 return 0;
 188
 189         if (!cache_tree_fully_valid(istate->cache_tree)) {
 190                 /* Clear and recompute the cache-tree */
 191                 cache_tree_free(&istate->cache_tree);
 192
 193                 /*
 194                  * Silently return if there is a problem with the cache tree update,
 195                  * which might just be due to a conflict state in some entry.
 196                  *
 197                  * This might create new tree objects, so be sure to use
 198                  * WRITE_TREE_MISSING_OK.
 199                  */
 200                 if (cache_tree_update(istate, WRITE_TREE_MISSING_OK))
 201                         return 0;
 202         }
 203
 204         remove_fsmonitor(istate);
 205
 206         trace2_region_enter("index", "convert_to_sparse", istate->repo);
 207         istate->cache_nr = convert_to_sparse_rec(istate,
 208                                                  0, 0, istate->cache_nr,
 209                                                  "", 0, istate->cache_tree);
 210
 211         /* Clear and recompute the cache-tree */
 212         cache_tree_free(&istate->cache_tree);
 213         cache_tree_update(istate, 0);
 214
 215         istate->fsmonitor_has_run_once = 0;
 216         FREE_AND_NULL(istate->fsmonitor_dirty);
 217         FREE_AND_NULL(istate->fsmonitor_last_update);
 218
 219         istate->sparse_index = INDEX_COLLAPSED;
 220         trace2_region_leave("index", "convert_to_sparse", istate->repo);
 221         return 0;
 222 }
 223
 224 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 225 {
 226         ALLOC_GROW(istate->cache, nr + 1, istate->cache_alloc);
 227
 228         istate->cache[nr] = ce;
 229         add_name_hash(istate, ce);
 230 }
 231
 232 static int add_path_to_index(const struct object_id *oid,
 233                              struct strbuf *base, const char *path,
 234                              unsigned int mode, void *context)
 235 {
 236         struct modify_index_context *ctx = (struct modify_index_context *)context;
 237         struct cache_entry *ce;
 238         size_t len = base->len;
 239
 240         if (S_ISDIR(mode)) {
 241                 int dtype;
 242                 size_t baselen = base->len;
 243                 if (!ctx->pl)
 244                         return READ_TREE_RECURSIVE;
 245
 246                 /*
 247                  * Have we expanded to a point outside of the sparse-checkout?
 248                  *
 249                  * Artificially pad the path name with a slash "/" to
 250                  * indicate it as a directory, and add an arbitrary file
 251                  * name ("-") so we can consider base->buf as a file name
 252                  * to match against the cone-mode patterns.
 253                  *
 254                  * If we compared just "path", then we would expand more
 255                  * than we should. Since every file at root is always
 256                  * included, we would expand every directory at root at
 257                  * least one level deep instead of using sparse directory
 258                  * entries.
 259                  */
 260                 strbuf_addstr(base, path);
 261                 strbuf_add(base, "/-", 2);
 262
 263                 if (path_matches_pattern_list(base->buf, base->len,
 264                                               NULL, &dtype,
 265                                               ctx->pl, ctx->write)) {
 266                         strbuf_setlen(base, baselen);
 267                         return READ_TREE_RECURSIVE;
 268                 }
 269
 270                 /*
 271                  * The path "{base}{path}/" is a sparse directory. Create the correct
 272                  * name for inserting the entry into the index.
 273                  */
 274                 strbuf_setlen(base, base->len - 1);
 275         } else {
 276                 strbuf_addstr(base, path);
 277         }
 278
 279         ce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);
 280         ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;
 281         set_index_entry(ctx->write, ctx->write->cache_nr++, ce);
 282
 283         strbuf_setlen(base, len);
 284         return 0;
 285 }
 286
 287 void expand_index(struct index_state *istate, struct pattern_list *pl)
 288 {
 289         int i;
 290         struct index_state *full;
 291         struct strbuf base = STRBUF_INIT;
 292         const char *tr_region;
 293         struct modify_index_context ctx;
 294
 295         /*
 296          * If the index is already full, then keep it full. We will convert
 297          * it to a sparse index on write, if possible.
 298          */
 299         if (istate->sparse_index == INDEX_EXPANDED)
 300                 return;
 301
 302         /*
 303          * If our index is sparse, but our new pattern set does not use
 304          * cone mode patterns, then we need to expand the index before we
 305          * continue. A NULL pattern set indicates a full expansion to a
 306          * full index.
 307          */
 308         if (pl && !pl->use_cone_patterns) {
 309                 pl = NULL;
 310         } else {
 311                 /*
 312                  * We might contract file entries into sparse-directory
 313                  * entries, and for that we will need the cache tree to
 314                  * be recomputed.
 315                  */
 316                 cache_tree_free(&istate->cache_tree);
 317
 318                 /*
 319                  * If there is a problem creating the cache tree, then we
 320                  * need to expand to a full index since we cannot satisfy
 321                  * the current request as a sparse index.
 322                  */
 323                 if (cache_tree_update(istate, 0))
 324                         pl = NULL;
 325         }
 326
 327         /*
 328          * A NULL pattern set indicates we are expanding a full index, so
 329          * we use a special region name that indicates the full expansion.
 330          * This is used by test cases, but also helps to differentiate the
 331          * two cases.
 332          */
 333         tr_region = pl ? "expand_index" : "ensure_full_index";
 334         trace2_region_enter("index", tr_region, istate->repo);
 335
 336         /* initialize basics of new index */
 337         full = xcalloc(1, sizeof(struct index_state));
 338         memcpy(full, istate, sizeof(struct index_state));
 339
 340         /*
 341          * This slightly-misnamed 'full' index might still be sparse if we
 342          * are only modifying the list of sparse directories. This hinges
 343          * on whether we have a non-NULL pattern list.
 344          */
 345         full->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;
 346
 347         /* then change the necessary things */
 348         full->cache_alloc = (3 * istate->cache_alloc) / 2;
 349         full->cache_nr = 0;
 350         ALLOC_ARRAY(full->cache, full->cache_alloc);
 351
 352         ctx.write = full;
 353         ctx.pl = pl;
 354
 355         for (i = 0; i < istate->cache_nr; i++) {
 356                 struct cache_entry *ce = istate->cache[i];
 357                 struct tree *tree;
 358                 struct pathspec ps;
 359                 int dtype;
 360
 361                 if (!S_ISSPARSEDIR(ce->ce_mode)) {
 362                         set_index_entry(full, full->cache_nr++, ce);
 363                         continue;
 364                 }
 365
 366                 /* We now have a sparse directory entry. Should we expand? */
 367                 if (pl &&
 368                     path_matches_pattern_list(ce->name, ce->ce_namelen,
 369                                               NULL, &dtype,
 370                                               pl, istate) == NOT_MATCHED) {
 371                         set_index_entry(full, full->cache_nr++, ce);
 372                         continue;
 373                 }
 374
 375                 if (!(ce->ce_flags & CE_SKIP_WORKTREE))
 376                         warning(_("index entry is a directory, but not sparse (%08x)"),
 377                                 ce->ce_flags);
 378
 379                 /* recursively walk into cd->name */
 380                 tree = lookup_tree(istate->repo, &ce->oid);
 381
 382                 memset(&ps, 0, sizeof(ps));
 383                 ps.recursive = 1;
 384                 ps.has_wildcard = 1;
 385                 ps.max_depth = -1;
 386
 387                 strbuf_setlen(&base, 0);
 388                 strbuf_add(&base, ce->name, strlen(ce->name));
 389
 390                 read_tree_at(istate->repo, tree, &base, &ps,
 391                              add_path_to_index, &ctx);
 392
 393                 /* free directory entries. full entries are re-used */
 394                 discard_cache_entry(ce);
 395         }
 396
 397         /* Copy back into original index. */
 398         memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
 399         memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));
 400         istate->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;
 401         free(istate->cache);
 402         istate->cache = full->cache;
 403         istate->cache_nr = full->cache_nr;
 404         istate->cache_alloc = full->cache_alloc;
 405         istate->fsmonitor_has_run_once = 0;
 406         FREE_AND_NULL(istate->fsmonitor_dirty);
 407         FREE_AND_NULL(istate->fsmonitor_last_update);
 408
 409         strbuf_release(&base);
 410         free(full);
 411
 412         /* Clear and recompute the cache-tree */
 413         cache_tree_free(&istate->cache_tree);
 414         cache_tree_update(istate, 0);
 415
 416         trace2_region_leave("index", tr_region, istate->repo);
 417 }
 418
 419 void ensure_full_index(struct index_state *istate)
 420 {
 421         if (!istate)
 422                 BUG("ensure_full_index() must get an index!");
 423         expand_index(istate, NULL);
 424 }
 425
 426 void ensure_correct_sparsity(struct index_state *istate)
 427 {
 428         /*
 429          * If the index can be sparse, make it sparse. Otherwise,
 430          * ensure the index is full.
 431          */
 432         if (is_sparse_index_allowed(istate, 0))
 433                 convert_to_sparse(istate, 0);
 434         else
 435                 ensure_full_index(istate);
 436 }
 437
 438 static int path_found(const char *path, const char **dirname, size_t *dir_len,
 439                       int *dir_found)
 440 {
 441         struct stat st;
 442         char *newdir;
 443         char *tmp;
 444
 445         /*
 446          * If dirname corresponds to a directory that doesn't exist, and this
 447          * path starts with dirname, then path can't exist.
 448          */
 449         if (!*dir_found && !memcmp(path, *dirname, *dir_len))
 450                 return 0;
 451
 452         /*
 453          * If path itself exists, return 1.
 454          */
 455         if (!lstat(path, &st))
 456                 return 1;
 457
 458         /*
 459          * Otherwise, path does not exist so we'll return 0...but we'll first
 460          * determine some info about its parent directory so we can avoid
 461          * lstat calls for future cache entries.
 462          */
 463         newdir = strrchr(path, '/');
 464         if (!newdir)
 465                 return 0; /* Didn't find a parent dir; just return 0 now. */
 466
 467         /*
 468          * If path starts with directory (which we already lstat'ed and found),
 469          * then no need to lstat parent directory again.
 470          */
 471         if (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))
 472                 return 0;
 473
 474         /* Free previous dirname, and cache path's dirname */
 475         *dirname = path;
 476         *dir_len = newdir - path + 1;
 477
 478         tmp = xstrndup(path, *dir_len);
 479         *dir_found = !lstat(tmp, &st);
 480         free(tmp);
 481
 482         return 0;
 483 }
 484
 485 void clear_skip_worktree_from_present_files(struct index_state *istate)
 486 {
 487         const char *last_dirname = NULL;
 488         size_t dir_len = 0;
 489         int dir_found = 1;
 490
 491         int i;
 492         int path_count[2] = {0, 0};
 493         int restarted = 0;
 494
 495         if (!core_apply_sparse_checkout ||
 496             sparse_expect_files_outside_of_patterns)
 497                 return;
 498
 499         trace2_region_enter("index", "clear_skip_worktree_from_present_files",
 500                             istate->repo);
 501 restart:
 502         for (i = 0; i < istate->cache_nr; i++) {
 503                 struct cache_entry *ce = istate->cache[i];
 504
 505                 if (ce_skip_worktree(ce)) {
 506                         path_count[restarted]++;
 507                         if (path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {
 508                                 if (S_ISSPARSEDIR(ce->ce_mode)) {
 509                                         if (restarted)
 510                                                 BUG("ensure-full-index did not fully flatten?");
 511                                         ensure_full_index(istate);
 512                                         restarted = 1;
 513                                         goto restart;
 514                                 }
 515                                 ce->ce_flags &= ~CE_SKIP_WORKTREE;
 516                         }
 517                 }
 518         }
 519
 520         if (path_count[0])
 521                 trace2_data_intmax("index", istate->repo,
 522                                    "sparse_path_count", path_count[0]);
 523         if (restarted)
 524                 trace2_data_intmax("index", istate->repo,
 525                                    "sparse_path_count_full", path_count[1]);
 526         trace2_region_leave("index", "clear_skip_worktree_from_present_files",
 527                             istate->repo);
 528 }
 529
 530 /*
 531  * This static global helps avoid infinite recursion between
 532  * expand_to_path() and index_file_exists().
 533  */
 534 static int in_expand_to_path = 0;
 535
 536 void expand_to_path(struct index_state *istate,
 537                     const char *path, size_t pathlen, int icase)
 538 {
 539         struct strbuf path_mutable = STRBUF_INIT;
 540         size_t substr_len;
 541
 542         /* prevent extra recursion */
 543         if (in_expand_to_path)
 544                 return;
 545
 546         if (!istate->sparse_index)
 547                 return;
 548
 549         in_expand_to_path = 1;
 550
 551         /*
 552          * We only need to actually expand a region if the
 553          * following are both true:
 554          *
 555          * 1. 'path' is not already in the index.
 556          * 2. Some parent directory of 'path' is a sparse directory.
 557          */
 558
 559         if (index_file_exists(istate, path, pathlen, icase))
 560                 goto cleanup;
 561
 562         strbuf_add(&path_mutable, path, pathlen);
 563         strbuf_addch(&path_mutable, '/');
 564
 565         /* Check the name hash for all parent directories */
 566         substr_len = 0;
 567         while (substr_len < pathlen) {
 568                 char temp;
 569                 char *replace = strchr(path_mutable.buf + substr_len, '/');
 570
 571                 if (!replace)
 572                         break;
 573
 574                 /* replace the character _after_ the slash */
 575                 replace++;
 576                 temp = *replace;
 577                 *replace = '\0';
 578                 if (index_file_exists(istate, path_mutable.buf,
 579                                       path_mutable.len, icase)) {
 580                         /*
 581                          * We found a parent directory in the name-hash
 582                          * hashtable, because only sparse directory entries
 583                          * have a trailing '/' character.  Since "path" wasn't
 584                          * in the index, perhaps it exists within this
 585                          * sparse-directory.  Expand accordingly.
 586                          */
 587                         ensure_full_index(istate);
 588                         break;
 589                 }
 590
 591                 *replace = temp;
 592                 substr_len = replace - path_mutable.buf;
 593         }
 594
 595 cleanup:
 596         strbuf_release(&path_mutable);
 597         in_expand_to_path = 0;
 598 }