sparse-index.c

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