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 static struct cache_entry *construct_sparse_dir_entry(
  13                                 struct index_state *istate,
  14                                 const char *sparse_dir,
  15                                 struct cache_tree *tree)
  16 {
  17         struct cache_entry *de;
  18
  19         de = make_cache_entry(istate, S_IFDIR, &tree->oid, sparse_dir, 0, 0);
  20
  21         de->ce_flags |= CE_SKIP_WORKTREE;
  22         return de;
  23 }
  24
  25 /*
  26  * Returns the number of entries "inserted" into the index.
  27  */
  28 static int convert_to_sparse_rec(struct index_state *istate,
  29                                  int num_converted,
  30                                  int start, int end,
  31                                  const char *ct_path, size_t ct_pathlen,
  32                                  struct cache_tree *ct)
  33 {
  34         int i, can_convert = 1;
  35         int start_converted = num_converted;
  36         struct strbuf child_path = STRBUF_INIT;
  37
  38         /*
  39          * Is the current path outside of the sparse cone?
  40          * Then check if the region can be replaced by a sparse
  41          * directory entry (everything is sparse and merged).
  42          */
  43         if (path_in_sparse_checkout(ct_path, istate))
  44                 can_convert = 0;
  45
  46         for (i = start; can_convert && i < end; i++) {
  47                 struct cache_entry *ce = istate->cache[i];
  48
  49                 if (ce_stage(ce) ||
  50                     S_ISGITLINK(ce->ce_mode) ||
  51                     !(ce->ce_flags & CE_SKIP_WORKTREE))
  52                         can_convert = 0;
  53         }
  54
  55         if (can_convert) {
  56                 struct cache_entry *se;
  57                 se = construct_sparse_dir_entry(istate, ct_path, ct);
  58
  59                 istate->cache[num_converted++] = se;
  60                 return 1;
  61         }
  62
  63         for (i = start; i < end; ) {
  64                 int count, span, pos = -1;
  65                 const char *base, *slash;
  66                 struct cache_entry *ce = istate->cache[i];
  67
  68                 /*
  69                  * Detect if this is a normal entry outside of any subtree
  70                  * entry.
  71                  */
  72                 base = ce->name + ct_pathlen;
  73                 slash = strchr(base, '/');
  74
  75                 if (slash)
  76                         pos = cache_tree_subtree_pos(ct, base, slash - base);
  77
  78                 if (pos < 0) {
  79                         istate->cache[num_converted++] = ce;
  80                         i++;
  81                         continue;
  82                 }
  83
  84                 strbuf_setlen(&child_path, 0);
  85                 strbuf_add(&child_path, ce->name, slash - ce->name + 1);
  86
  87                 span = ct->down[pos]->cache_tree->entry_count;
  88                 count = convert_to_sparse_rec(istate,
  89                                               num_converted, i, i + span,
  90                                               child_path.buf, child_path.len,
  91                                               ct->down[pos]->cache_tree);
  92                 num_converted += count;
  93                 i += span;
  94         }
  95
  96         strbuf_release(&child_path);
  97         return num_converted - start_converted;
  98 }
  99
 100 int set_sparse_index_config(struct repository *repo, int enable)
 101 {
 102         int res = repo_config_set_worktree_gently(repo,
 103                                                   "index.sparse",
 104                                                   enable ? "true" : "false");
 105         prepare_repo_settings(repo);
 106         repo->settings.sparse_index = enable;
 107         return res;
 108 }
 109
 110 static int index_has_unmerged_entries(struct index_state *istate)
 111 {
 112         int i;
 113         for (i = 0; i < istate->cache_nr; i++) {
 114                 if (ce_stage(istate->cache[i]))
 115                         return 1;
 116         }
 117
 118         return 0;
 119 }
 120
 121 int is_sparse_index_allowed(struct index_state *istate, int flags)
 122 {
 123         if (!core_apply_sparse_checkout || !core_sparse_checkout_cone)
 124                 return 0;
 125
 126         if (!istate->repo)
 127                 istate->repo = the_repository;
 128
 129         if (!(flags & SPARSE_INDEX_MEMORY_ONLY)) {
 130                 int test_env;
 131
 132                 /*
 133                  * The sparse index is not (yet) integrated with a split index.
 134                  */
 135                 if (istate->split_index || git_env_bool("GIT_TEST_SPLIT_INDEX", 0))
 136                         return 0;
 137                 /*
 138                  * The GIT_TEST_SPARSE_INDEX environment variable triggers the
 139                  * index.sparse config variable to be on.
 140                  */
 141                 test_env = git_env_bool("GIT_TEST_SPARSE_INDEX", -1);
 142                 if (test_env >= 0)
 143                         set_sparse_index_config(istate->repo, test_env);
 144
 145                 /*
 146                  * Only convert to sparse if index.sparse is set.
 147                  */
 148                 prepare_repo_settings(istate->repo);
 149                 if (!istate->repo->settings.sparse_index)
 150                         return 0;
 151         }
 152
 153         if (init_sparse_checkout_patterns(istate))
 154                 return 0;
 155
 156         /*
 157          * We need cone-mode patterns to use sparse-index. If a user edits
 158          * their sparse-checkout file manually, then we can detect during
 159          * parsing that they are not actually using cone-mode patterns and
 160          * hence we need to abort this conversion _without error_. Warnings
 161          * already exist in the pattern parsing to inform the user of their
 162          * bad patterns.
 163          */
 164         if (!istate->sparse_checkout_patterns->use_cone_patterns)
 165                 return 0;
 166
 167         return 1;
 168 }
 169
 170 int convert_to_sparse(struct index_state *istate, int flags)
 171 {
 172         /*
 173          * If the index is already sparse, empty, or otherwise
 174          * cannot be converted to sparse, do not convert.
 175          */
 176         if (istate->sparse_index || !istate->cache_nr ||
 177             !is_sparse_index_allowed(istate, flags))
 178                 return 0;
 179
 180         /*
 181          * NEEDSWORK: If we have unmerged entries, then stay full.
 182          * Unmerged entries prevent the cache-tree extension from working.
 183          */
 184         if (index_has_unmerged_entries(istate))
 185                 return 0;
 186
 187         if (!cache_tree_fully_valid(istate->cache_tree)) {
 188                 /* Clear and recompute the cache-tree */
 189                 cache_tree_free(&istate->cache_tree);
 190
 191                 /*
 192                  * Silently return if there is a problem with the cache tree update,
 193                  * which might just be due to a conflict state in some entry.
 194                  *
 195                  * This might create new tree objects, so be sure to use
 196                  * WRITE_TREE_MISSING_OK.
 197                  */
 198                 if (cache_tree_update(istate, WRITE_TREE_MISSING_OK))
 199                         return 0;
 200         }
 201
 202         remove_fsmonitor(istate);
 203
 204         trace2_region_enter("index", "convert_to_sparse", istate->repo);
 205         istate->cache_nr = convert_to_sparse_rec(istate,
 206                                                  0, 0, istate->cache_nr,
 207                                                  "", 0, istate->cache_tree);
 208
 209         /* Clear and recompute the cache-tree */
 210         cache_tree_free(&istate->cache_tree);
 211         cache_tree_update(istate, 0);
 212
 213         istate->fsmonitor_has_run_once = 0;
 214         FREE_AND_NULL(istate->fsmonitor_dirty);
 215         FREE_AND_NULL(istate->fsmonitor_last_update);
 216
 217         istate->sparse_index = 1;
 218         trace2_region_leave("index", "convert_to_sparse", istate->repo);
 219         return 0;
 220 }
 221
 222 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 223 {
 224         ALLOC_GROW(istate->cache, nr + 1, istate->cache_alloc);
 225
 226         istate->cache[nr] = ce;
 227         add_name_hash(istate, ce);
 228 }
 229
 230 static int add_path_to_index(const struct object_id *oid,
 231                              struct strbuf *base, const char *path,
 232                              unsigned int mode, void *context)
 233 {
 234         struct index_state *istate = (struct index_state *)context;
 235         struct cache_entry *ce;
 236         size_t len = base->len;
 237
 238         if (S_ISDIR(mode))
 239                 return READ_TREE_RECURSIVE;
 240
 241         strbuf_addstr(base, path);
 242
 243         ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
 244         ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;
 245         set_index_entry(istate, istate->cache_nr++, ce);
 246
 247         strbuf_setlen(base, len);
 248         return 0;
 249 }
 250
 251 void ensure_full_index(struct index_state *istate)
 252 {
 253         int i;
 254         struct index_state *full;
 255         struct strbuf base = STRBUF_INIT;
 256
 257         if (!istate || !istate->sparse_index)
 258                 return;
 259
 260         if (!istate->repo)
 261                 istate->repo = the_repository;
 262
 263         trace2_region_enter("index", "ensure_full_index", istate->repo);
 264
 265         /* initialize basics of new index */
 266         full = xcalloc(1, sizeof(struct index_state));
 267         memcpy(full, istate, sizeof(struct index_state));
 268
 269         /* then change the necessary things */
 270         full->sparse_index = 0;
 271         full->cache_alloc = (3 * istate->cache_alloc) / 2;
 272         full->cache_nr = 0;
 273         ALLOC_ARRAY(full->cache, full->cache_alloc);
 274
 275         for (i = 0; i < istate->cache_nr; i++) {
 276                 struct cache_entry *ce = istate->cache[i];
 277                 struct tree *tree;
 278                 struct pathspec ps;
 279
 280                 if (!S_ISSPARSEDIR(ce->ce_mode)) {
 281                         set_index_entry(full, full->cache_nr++, ce);
 282                         continue;
 283                 }
 284                 if (!(ce->ce_flags & CE_SKIP_WORKTREE))
 285                         warning(_("index entry is a directory, but not sparse (%08x)"),
 286                                 ce->ce_flags);
 287
 288                 /* recursively walk into cd->name */
 289                 tree = lookup_tree(istate->repo, &ce->oid);
 290
 291                 memset(&ps, 0, sizeof(ps));
 292                 ps.recursive = 1;
 293                 ps.has_wildcard = 1;
 294                 ps.max_depth = -1;
 295
 296                 strbuf_setlen(&base, 0);
 297                 strbuf_add(&base, ce->name, strlen(ce->name));
 298
 299                 read_tree_at(istate->repo, tree, &base, &ps,
 300                              add_path_to_index, full);
 301
 302                 /* free directory entries. full entries are re-used */
 303                 discard_cache_entry(ce);
 304         }
 305
 306         /* Copy back into original index. */
 307         memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
 308         memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));
 309         istate->sparse_index = 0;
 310         free(istate->cache);
 311         istate->cache = full->cache;
 312         istate->cache_nr = full->cache_nr;
 313         istate->cache_alloc = full->cache_alloc;
 314         istate->fsmonitor_has_run_once = 0;
 315         FREE_AND_NULL(istate->fsmonitor_dirty);
 316         FREE_AND_NULL(istate->fsmonitor_last_update);
 317
 318         strbuf_release(&base);
 319         free(full);
 320
 321         /* Clear and recompute the cache-tree */
 322         cache_tree_free(&istate->cache_tree);
 323         cache_tree_update(istate, 0);
 324
 325         trace2_region_leave("index", "ensure_full_index", istate->repo);
 326 }
 327
 328 void ensure_correct_sparsity(struct index_state *istate)
 329 {
 330         /*
 331          * If the index can be sparse, make it sparse. Otherwise,
 332          * ensure the index is full.
 333          */
 334         if (is_sparse_index_allowed(istate, 0))
 335                 convert_to_sparse(istate, 0);
 336         else
 337                 ensure_full_index(istate);
 338 }
 339
 340 static int path_found(const char *path, const char **dirname, size_t *dir_len,
 341                       int *dir_found)
 342 {
 343         struct stat st;
 344         char *newdir;
 345         char *tmp;
 346
 347         /*
 348          * If dirname corresponds to a directory that doesn't exist, and this
 349          * path starts with dirname, then path can't exist.
 350          */
 351         if (!*dir_found && !memcmp(path, *dirname, *dir_len))
 352                 return 0;
 353
 354         /*
 355          * If path itself exists, return 1.
 356          */
 357         if (!lstat(path, &st))
 358                 return 1;
 359
 360         /*
 361          * Otherwise, path does not exist so we'll return 0...but we'll first
 362          * determine some info about its parent directory so we can avoid
 363          * lstat calls for future cache entries.
 364          */
 365         newdir = strrchr(path, '/');
 366         if (!newdir)
 367                 return 0; /* Didn't find a parent dir; just return 0 now. */
 368
 369         /*
 370          * If path starts with directory (which we already lstat'ed and found),
 371          * then no need to lstat parent directory again.
 372          */
 373         if (*dir_found && *dirname && memcmp(path, *dirname, *dir_len))
 374                 return 0;
 375
 376         /* Free previous dirname, and cache path's dirname */
 377         *dirname = path;
 378         *dir_len = newdir - path + 1;
 379
 380         tmp = xstrndup(path, *dir_len);
 381         *dir_found = !lstat(tmp, &st);
 382         free(tmp);
 383
 384         return 0;
 385 }
 386
 387 void clear_skip_worktree_from_present_files(struct index_state *istate)
 388 {
 389         const char *last_dirname = NULL;
 390         size_t dir_len = 0;
 391         int dir_found = 1;
 392
 393         int i;
 394
 395         if (!core_apply_sparse_checkout ||
 396             sparse_expect_files_outside_of_patterns)
 397                 return;
 398
 399 restart:
 400         for (i = 0; i < istate->cache_nr; i++) {
 401                 struct cache_entry *ce = istate->cache[i];
 402
 403                 if (ce_skip_worktree(ce) &&
 404                     path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {
 405                         if (S_ISSPARSEDIR(ce->ce_mode)) {
 406                                 ensure_full_index(istate);
 407                                 goto restart;
 408                         }
 409                         ce->ce_flags &= ~CE_SKIP_WORKTREE;
 410                 }
 411         }
 412 }
 413
 414 /*
 415  * This static global helps avoid infinite recursion between
 416  * expand_to_path() and index_file_exists().
 417  */
 418 static int in_expand_to_path = 0;
 419
 420 void expand_to_path(struct index_state *istate,
 421                     const char *path, size_t pathlen, int icase)
 422 {
 423         struct strbuf path_mutable = STRBUF_INIT;
 424         size_t substr_len;
 425
 426         /* prevent extra recursion */
 427         if (in_expand_to_path)
 428                 return;
 429
 430         if (!istate || !istate->sparse_index)
 431                 return;
 432
 433         if (!istate->repo)
 434                 istate->repo = the_repository;
 435
 436         in_expand_to_path = 1;
 437
 438         /*
 439          * We only need to actually expand a region if the
 440          * following are both true:
 441          *
 442          * 1. 'path' is not already in the index.
 443          * 2. Some parent directory of 'path' is a sparse directory.
 444          */
 445
 446         if (index_file_exists(istate, path, pathlen, icase))
 447                 goto cleanup;
 448
 449         strbuf_add(&path_mutable, path, pathlen);
 450         strbuf_addch(&path_mutable, '/');
 451
 452         /* Check the name hash for all parent directories */
 453         substr_len = 0;
 454         while (substr_len < pathlen) {
 455                 char temp;
 456                 char *replace = strchr(path_mutable.buf + substr_len, '/');
 457
 458                 if (!replace)
 459                         break;
 460
 461                 /* replace the character _after_ the slash */
 462                 replace++;
 463                 temp = *replace;
 464                 *replace = '\0';
 465                 if (index_file_exists(istate, path_mutable.buf,
 466                                       path_mutable.len, icase)) {
 467                         /*
 468                          * We found a parent directory in the name-hash
 469                          * hashtable, because only sparse directory entries
 470                          * have a trailing '/' character.  Since "path" wasn't
 471                          * in the index, perhaps it exists within this
 472                          * sparse-directory.  Expand accordingly.
 473                          */
 474                         ensure_full_index(istate);
 475                         break;
 476                 }
 477
 478                 *replace = temp;
 479                 substr_len = replace - path_mutable.buf;
 480         }
 481
 482 cleanup:
 483         strbuf_release(&path_mutable);
 484         in_expand_to_path = 0;
 485 }