#include "git-compat-util.h"

#include "environment.h"

#include "gettext.h"

#include "name-hash.h"

#include "read-cache-ll.h"

#include "repository.h"

#include "sparse-index.h"

#include "tree.h"

#include "pathspec.h"

#include "trace2.h"

#include "cache-tree.h"

#include "config.h"

#include "dir.h"

#include "fsmonitor-ll.h"

#include "advice.h"

/**

 * This global is used by expand_index() to determine if we should give the

 * advice for advice.sparseIndexExpanded when expanding a sparse index to a full

 * one. However, this is sometimes done on purpose, such as in the sparse-checkout

 * builtin, even when index.sparse=false. This may be disabled in

 * convert_to_sparse().

 */

static int give_advice_on_expansion = 1;

#define ADVICE_MSG \

  "The sparse index is expanding to a full index, a slow operation.\n"   \

  "Your working directory likely has contents that are outside of\n"     \

  "your sparse-checkout patterns. Use 'git sparse-checkout list' to\n"   \

  "see your sparse-checkout definition and compare it to your working\n" \

  "directory contents. Running 'git clean' may assist in this cleanup."

struct modify_index_context {

  struct index_state *write;

  struct pattern_list *pl;

};

static struct cache_entry *construct_sparse_dir_entry(

        struct index_state *istate,

        const char *sparse_dir,

        struct cache_tree *tree)

{

  struct cache_entry *de;

  de = make_cache_entry(istate, S_IFDIR, &tree->oid, sparse_dir, 0, 0);

  de->ce_flags |= CE_SKIP_WORKTREE;

  return de;

}

/*

 * Returns the number of entries "inserted" into the index.

 */

static int convert_to_sparse_rec(struct index_state *istate,

         int num_converted,

         int start, int end,

         const char *ct_path, size_t ct_pathlen,

         struct cache_tree *ct)

{

  int i, can_convert = 1;

  int start_converted = num_converted;

  struct strbuf child_path = STRBUF_INIT;

  /*

   * Is the current path outside of the sparse cone?

   * Then check if the region can be replaced by a sparse

   * directory entry (everything is sparse and merged).

   */

  if (path_in_sparse_checkout(ct_path, istate))

    can_convert = 0;

  for (i = start; can_convert && i < end; i++) {

    struct cache_entry *ce = istate->cache[i];

    if (ce_stage(ce) ||

        S_ISGITLINK(ce->ce_mode) ||

        !(ce->ce_flags & CE_SKIP_WORKTREE))

      can_convert = 0;

  }

  if (can_convert) {

    struct cache_entry *se;

    se = construct_sparse_dir_entry(istate, ct_path, ct);

    istate->cache[num_converted++] = se;

    return 1;

  }

  for (i = start; i < end; ) {

    int count, span, pos = -1;

    const char *base, *slash;

    struct cache_entry *ce = istate->cache[i];

    /*

     * Detect if this is a normal entry outside of any subtree

     * entry.

     */

    base = ce->name + ct_pathlen;

    slash = strchr(base, '/');

    if (slash)

      pos = cache_tree_subtree_pos(ct, base, slash - base);

    if (pos < 0) {

      istate->cache[num_converted++] = ce;

      i++;

      continue;

    }

    strbuf_setlen(&child_path, 0);

    strbuf_add(&child_path, ce->name, slash - ce->name + 1);

    span = ct->down[pos]->cache_tree->entry_count;

    count = convert_to_sparse_rec(istate,

                num_converted, i, i + span,

                child_path.buf, child_path.len,

                ct->down[pos]->cache_tree);

    num_converted += count;

    i += span;

  }

  strbuf_release(&child_path);

  return num_converted - start_converted;

}

int set_sparse_index_config(struct repository *repo, int enable)

{

  int res = repo_config_set_worktree_gently(repo,

              "index.sparse",

              enable ? "true" : "false");

  prepare_repo_settings(repo);

  repo->settings.sparse_index = enable;

  return res;

}

static int index_has_unmerged_entries(struct index_state *istate)

{

  int i;

  for (i = 0; i < istate->cache_nr; i++) {

    if (ce_stage(istate->cache[i]))

      return 1;

  }

  return 0;

}

int is_sparse_index_allowed(struct index_state *istate, int flags)

{

  if (!core_apply_sparse_checkout || !core_sparse_checkout_cone)

    return 0;

  if (!(flags & SPARSE_INDEX_MEMORY_ONLY)) {

    int test_env;

    /*

     * The sparse index is not (yet) integrated with a split index.

     */

    if (istate->split_index || git_env_bool("GIT_TEST_SPLIT_INDEX", 0))

      return 0;

    /*

     * The GIT_TEST_SPARSE_INDEX environment variable triggers the

     * index.sparse config variable to be on.

     */

    test_env = git_env_bool("GIT_TEST_SPARSE_INDEX", -1);

    if (test_env >= 0)

      set_sparse_index_config(istate->repo, test_env);

    /*

     * Only convert to sparse if index.sparse is set.

     */

    prepare_repo_settings(istate->repo);

    if (!istate->repo->settings.sparse_index)

      return 0;

  }

  if (init_sparse_checkout_patterns(istate))

    return 0;

  /*

   * We need cone-mode patterns to use sparse-index. If a user edits

   * their sparse-checkout file manually, then we can detect during

   * parsing that they are not actually using cone-mode patterns and

   * hence we need to abort this conversion _without error_. Warnings

   * already exist in the pattern parsing to inform the user of their

   * bad patterns.

   */

  if (!istate->sparse_checkout_patterns->use_cone_patterns)

    return 0;

  return 1;

}

int convert_to_sparse(struct index_state *istate, int flags)

{

  /*

   * If the index is already sparse, empty, or otherwise

   * cannot be converted to sparse, do not convert.

   */

  if (istate->sparse_index == INDEX_COLLAPSED || !istate->cache_nr ||

      !is_sparse_index_allowed(istate, flags))

    return 0;

  /*

   * If we are purposefully collapsing a full index, then don't give

   * advice when it is expanded later.

   */

  give_advice_on_expansion = 0;

  /*

   * NEEDSWORK: If we have unmerged entries, then stay full.

   * Unmerged entries prevent the cache-tree extension from working.

   */

  if (index_has_unmerged_entries(istate))

    return 0;

  if (!cache_tree_fully_valid(istate->cache_tree)) {

    /* Clear and recompute the cache-tree */

    cache_tree_free(&istate->cache_tree);

    /*

     * Silently return if there is a problem with the cache tree update,

     * which might just be due to a conflict state in some entry.

     *

     * This might create new tree objects, so be sure to use

     * WRITE_TREE_MISSING_OK.

     */

    if (cache_tree_update(istate, WRITE_TREE_MISSING_OK))

      return 0;

  }

  remove_fsmonitor(istate);

  trace2_region_enter("index", "convert_to_sparse", istate->repo);

  istate->cache_nr = convert_to_sparse_rec(istate,

             0, 0, istate->cache_nr,

             "", 0, istate->cache_tree);

  /* Clear and recompute the cache-tree */

  cache_tree_free(&istate->cache_tree);

  cache_tree_update(istate, 0);

  istate->fsmonitor_has_run_once = 0;

  FREE_AND_NULL(istate->fsmonitor_dirty);

  FREE_AND_NULL(istate->fsmonitor_last_update);

  istate->sparse_index = INDEX_COLLAPSED;

  trace2_region_leave("index", "convert_to_sparse", istate->repo);

  return 0;

}

static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)

{

  ALLOC_GROW(istate->cache, nr + 1, istate->cache_alloc);

  istate->cache[nr] = ce;

  add_name_hash(istate, ce);

}

static int add_path_to_index(const struct object_id *oid,

           struct strbuf *base, const char *path,

           unsigned int mode, void *context)

{

  struct modify_index_context *ctx = (struct modify_index_context *)context;

  struct cache_entry *ce;

  size_t len = base->len;

  if (S_ISDIR(mode)) {

    int dtype;

    size_t baselen = base->len;

    if (!ctx->pl)

      return READ_TREE_RECURSIVE;

    /*

     * Have we expanded to a point outside of the sparse-checkout?

     *

     * Artificially pad the path name with a slash "/" to

     * indicate it as a directory, and add an arbitrary file

     * name ("-") so we can consider base->buf as a file name

     * to match against the cone-mode patterns.

     *

     * If we compared just "path", then we would expand more

     * than we should. Since every file at root is always

     * included, we would expand every directory at root at

     * least one level deep instead of using sparse directory

     * entries.

     */

    strbuf_addstr(base, path);

    strbuf_add(base, "/-", 2);

    if (path_matches_pattern_list(base->buf, base->len,

                NULL, &dtype,

                ctx->pl, ctx->write)) {

      strbuf_setlen(base, baselen);

      return READ_TREE_RECURSIVE;

    }

    /*

     * The path "{base}{path}/" is a sparse directory. Create the correct

     * name for inserting the entry into the index.

     */

    strbuf_setlen(base, base->len - 1);

  } else {

    strbuf_addstr(base, path);

  }

  ce = make_cache_entry(ctx->write, mode, oid, base->buf, 0, 0);

  ce->ce_flags |= CE_SKIP_WORKTREE | CE_EXTENDED;

  set_index_entry(ctx->write, ctx->write->cache_nr++, ce);

  strbuf_setlen(base, len);

  return 0;

}

void expand_index(struct index_state *istate, struct pattern_list *pl)

{

  int i;

  struct index_state *full;

  struct strbuf base = STRBUF_INIT;

  const char *tr_region;

  struct modify_index_context ctx;

  /*

   * If the index is already full, then keep it full. We will convert

   * it to a sparse index on write, if possible.

   */

  if (istate->sparse_index == INDEX_EXPANDED)

    return;

  /*

   * If our index is sparse, but our new pattern set does not use

   * cone mode patterns, then we need to expand the index before we

   * continue. A NULL pattern set indicates a full expansion to a

   * full index.

   */

  if (pl && !pl->use_cone_patterns) {

    pl = NULL;

  } else {

    /*

     * We might contract file entries into sparse-directory

     * entries, and for that we will need the cache tree to

     * be recomputed.

     */

    cache_tree_free(&istate->cache_tree);

    /*

     * If there is a problem creating the cache tree, then we

     * need to expand to a full index since we cannot satisfy

     * the current request as a sparse index.

     */

    if (cache_tree_update(istate, 0))

      pl = NULL;

  }

  if (!pl && give_advice_on_expansion) {

    give_advice_on_expansion = 0;

    advise_if_enabled(ADVICE_SPARSE_INDEX_EXPANDED,

          _(ADVICE_MSG));

  }

  /*

   * A NULL pattern set indicates we are expanding a full index, so

   * we use a special region name that indicates the full expansion.

   * This is used by test cases, but also helps to differentiate the

   * two cases.

   */

  tr_region = pl ? "expand_index" : "ensure_full_index";

  trace2_region_enter("index", tr_region, istate->repo);

  /* initialize basics of new index */

  full = xcalloc(1, sizeof(struct index_state));

  memcpy(full, istate, sizeof(struct index_state));

  /*

   * This slightly-misnamed 'full' index might still be sparse if we

   * are only modifying the list of sparse directories. This hinges

   * on whether we have a non-NULL pattern list.

   */

  full->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;

  /* then change the necessary things */

  full->cache_alloc = (3 * istate->cache_alloc) / 2;

  full->cache_nr = 0;

  ALLOC_ARRAY(full->cache, full->cache_alloc);

  ctx.write = full;

  ctx.pl = pl;

  for (i = 0; i < istate->cache_nr; i++) {

    struct cache_entry *ce = istate->cache[i];

    struct tree *tree;

    struct pathspec ps;

    int dtype;

    if (!S_ISSPARSEDIR(ce->ce_mode)) {

      set_index_entry(full, full->cache_nr++, ce);

      continue;

    }

    /* We now have a sparse directory entry. Should we expand? */

    if (pl &&

        path_matches_pattern_list(ce->name, ce->ce_namelen,

                NULL, &dtype,

                pl, istate) == NOT_MATCHED) {

      set_index_entry(full, full->cache_nr++, ce);

      continue;

    }

    if (!(ce->ce_flags & CE_SKIP_WORKTREE))

      warning(_("index entry is a directory, but not sparse (%08x)"),

        ce->ce_flags);

    /* recursively walk into cd->name */

    tree = lookup_tree(istate->repo, &ce->oid);

    memset(&ps, 0, sizeof(ps));

    ps.recursive = 1;

    ps.has_wildcard = 1;

    ps.max_depth = -1;

    strbuf_setlen(&base, 0);

    strbuf_add(&base, ce->name, strlen(ce->name));

    read_tree_at(istate->repo, tree, &base, 0, &ps,

           add_path_to_index, &ctx);

    /* free directory entries. full entries are re-used */

    discard_cache_entry(ce);

  }

  /* Copy back into original index. */

  memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));

  memcpy(&istate->dir_hash, &full->dir_hash, sizeof(full->dir_hash));

  istate->sparse_index = pl ? INDEX_PARTIALLY_SPARSE : INDEX_EXPANDED;

  free(istate->cache);

  istate->cache = full->cache;

  istate->cache_nr = full->cache_nr;

  istate->cache_alloc = full->cache_alloc;

  istate->fsmonitor_has_run_once = 0;

  FREE_AND_NULL(istate->fsmonitor_dirty);

  FREE_AND_NULL(istate->fsmonitor_last_update);

  strbuf_release(&base);

  free(full);

  /* Clear and recompute the cache-tree */

  cache_tree_free(&istate->cache_tree);

  cache_tree_update(istate, 0);

  trace2_region_leave("index", tr_region, istate->repo);

}

void ensure_full_index(struct index_state *istate)

{

  if (!istate)

    BUG("ensure_full_index() must get an index!");

  expand_index(istate, NULL);

}

void ensure_correct_sparsity(struct index_state *istate)

{

  /*

   * If the index can be sparse, make it sparse. Otherwise,

   * ensure the index is full.

   */

  if (is_sparse_index_allowed(istate, 0))

    convert_to_sparse(istate, 0);

  else

    ensure_full_index(istate);

}

struct path_found_data {

  /**

   * The path stored in 'dir', if non-empty, corresponds to the most-

   * recent path that we checked where:

   *

   *   1. The path should be a directory, according to the index.

   *   2. The path does not exist.

   *   3. The parent path _does_ exist. (This may be the root of the

   *      working directory.)

   */

  struct strbuf dir;

  size_t lstat_count;

};

#define PATH_FOUND_DATA_INIT { \

  .dir = STRBUF_INIT \

}

static void clear_path_found_data(struct path_found_data *data)

{

  strbuf_release(&data->dir);

}

/**

 * Return the length of the longest common substring that ends in a

 * slash ('/') to indicate the longest common parent directory. Returns

 * zero if no common directory exists.

 */

static size_t max_common_dir_prefix(const char *path1, const char *path2)

{

  size_t common_prefix = 0;

  for (size_t i = 0; path1[i] && path2[i]; i++) {

    if (path1[i] != path2[i])

      break;

    /*

     * If they agree at a directory separator, then add one

     * to make sure it is included in the common prefix string.

     */

    if (path1[i] == '/')

      common_prefix = i + 1;

  }

  return common_prefix;

}

static int path_found(const char *path, struct path_found_data *data)

{

  struct stat st;

  size_t common_prefix;

  /*

   * If data->dir is non-empty, then it contains a path that doesn't

   * exist, including an ending slash ('/'). If it is a prefix of 'path',

   * then we can return 0.

   */

  if (data->dir.len && !memcmp(path, data->dir.buf, data->dir.len))

    return 0;

  /*

   * Otherwise, we must check if the current path exists. If it does, then

   * return 1. The cached directory will be skipped until we come across

   * a missing path again.

   */

  data->lstat_count++;

  if (!lstat(path, &st))

    return 1;

  /*

   * At this point, we know that 'path' doesn't exist, and we know that

   * the parent directory of 'data->dir' does exist. Let's set 'data->dir'

   * to be the top-most non-existing directory of 'path'. If the first

   * parent of 'path' exists, then we will act as though 'path'

   * corresponds to a directory (by adding a slash).

   */

  common_prefix = max_common_dir_prefix(path, data->dir.buf);

  /*

   * At this point, 'path' and 'data->dir' have a common existing parent

   * directory given by path[0..common_prefix] (which could have length 0).

   * We "grow" the data->dir buffer by checking for existing directories

   * along 'path'.

   */

  strbuf_setlen(&data->dir, common_prefix);

  while (1) {

    /* Find the next directory in 'path'. */

    const char *rest = path + data->dir.len;

    const char *next_slash = strchr(rest, '/');

    /*

     * If there are no more slashes, then 'path' doesn't contain a

     * non-existent _parent_ directory. Set 'data->dir' to be equal

     * to 'path' plus an additional slash, so it can be used for

     * caching in the future. The filename of 'path' is considered

     * a non-existent directory.

     *

     * Note: if "{path}/" exists as a directory, then it will never

     * appear as a prefix of other callers to this method, assuming

     * the context from the clear_skip_worktree... methods. If this

     * method is reused, then this must be reconsidered.

     */

    if (!next_slash) {

      strbuf_addstr(&data->dir, rest);

      strbuf_addch(&data->dir, '/');

      break;

    }

    /*

     * Now that we have a slash, let's grow 'data->dir' to include

     * this slash, then test if we should stop.

     */

    strbuf_add(&data->dir, rest, next_slash - rest + 1);

    /* If the parent dir doesn't exist, then stop here. */

    data->lstat_count++;

    if (lstat(data->dir.buf, &st))

      return 0;

  }

  /*

   * At this point, 'data->dir' is equal to 'path' plus a slash character,

   * and the parent directory of 'path' definitely exists. Moreover, we

   * know that 'path' doesn't exist, or we would have returned 1 earlier.

   */

  return 0;

}

static int clear_skip_worktree_from_present_files_sparse(struct index_state *istate)

{

  struct path_found_data data = PATH_FOUND_DATA_INIT;

  int path_count = 0;

  int to_restart = 0;

  trace2_region_enter("index", "clear_skip_worktree_from_present_files_sparse",

          istate->repo);

  for (int i = 0; i < istate->cache_nr; i++) {

    struct cache_entry *ce = istate->cache[i];

    if (ce_skip_worktree(ce)) {

      path_count++;

      if (path_found(ce->name, &data)) {

        if (S_ISSPARSEDIR(ce->ce_mode)) {

          to_restart = 1;

          break;

        }

        ce->ce_flags &= ~CE_SKIP_WORKTREE;

      }

    }

  }

  trace2_data_intmax("index", istate->repo,

         "sparse_path_count", path_count);

  trace2_data_intmax("index", istate->repo,

         "sparse_lstat_count", data.lstat_count);

  trace2_region_leave("index", "clear_skip_worktree_from_present_files_sparse",

          istate->repo);

  clear_path_found_data(&data);

  return to_restart;

}

static void clear_skip_worktree_from_present_files_full(struct index_state *istate)

{

  struct path_found_data data = PATH_FOUND_DATA_INIT;

  int path_count = 0;

  trace2_region_enter("index", "clear_skip_worktree_from_present_files_full",

          istate->repo);

  for (int i = 0; i < istate->cache_nr; i++) {

    struct cache_entry *ce = istate->cache[i];

    if (S_ISSPARSEDIR(ce->ce_mode))

      BUG("ensure-full-index did not fully flatten?");

    if (ce_skip_worktree(ce)) {

      path_count++;

      if (path_found(ce->name, &data))

        ce->ce_flags &= ~CE_SKIP_WORKTREE;

    }

  }

  trace2_data_intmax("index", istate->repo,

         "full_path_count", path_count);

  trace2_data_intmax("index", istate->repo,

         "full_lstat_count", data.lstat_count);

  trace2_region_leave("index", "clear_skip_worktree_from_present_files_full",

          istate->repo);

  clear_path_found_data(&data);

}

void clear_skip_worktree_from_present_files(struct index_state *istate)

{

  if (!core_apply_sparse_checkout ||

      sparse_expect_files_outside_of_patterns)

    return;

  if (clear_skip_worktree_from_present_files_sparse(istate)) {

    ensure_full_index(istate);

    clear_skip_worktree_from_present_files_full(istate);

  }

}

/*

 * This static global helps avoid infinite recursion between

 * expand_to_path() and index_file_exists().

 */

static int in_expand_to_path = 0;

void expand_to_path(struct index_state *istate,

        const char *path, size_t pathlen, int icase)

{

  struct strbuf path_mutable = STRBUF_INIT;

  size_t substr_len;

  /* prevent extra recursion */

  if (in_expand_to_path)

    return;

  if (!istate->sparse_index)

    return;

  in_expand_to_path = 1;

  /*

   * We only need to actually expand a region if the

   * following are both true:

   *

   * 1. 'path' is not already in the index.

   * 2. Some parent directory of 'path' is a sparse directory.

   */

  if (index_file_exists(istate, path, pathlen, icase))

    goto cleanup;

  strbuf_add(&path_mutable, path, pathlen);

  strbuf_addch(&path_mutable, '/');

  /* Check the name hash for all parent directories */

  substr_len = 0;

  while (substr_len < pathlen) {

    char temp;

    char *replace = strchr(path_mutable.buf + substr_len, '/');

    if (!replace)

      break;

    /* replace the character _after_ the slash */

    replace++;

    temp = *replace;

    *replace = '\0';

    substr_len = replace - path_mutable.buf;

    if (index_file_exists(istate, path_mutable.buf,

              substr_len, icase)) {

      /*

       * We found a parent directory in the name-hash

       * hashtable, because only sparse directory entries

       * have a trailing '/' character.  Since "path" wasn't

       * in the index, perhaps it exists within this

       * sparse-directory.  Expand accordingly.

       */

      ensure_full_index(istate);

      break;

    }

    *replace = temp;

  }

cleanup:

  strbuf_release(&path_mutable);

  in_expand_to_path = 0;

}