///| Sparse checkout implementation

///|
pub fn sparse_default_patterns() -> Array[String] {
  ["/*", "!/*/"]
}

///|
fn sparse_read_or_default_config(
  rfs : &@bit.RepoFileSystem,
  path : String,
) -> String {
  if rfs.is_file(path) {
    @utf8.decode_lossy(
      (rfs.read_file(path) catch { _ => return "[core]\n" })[:],
    )
  } else {
    "[core]\n"
  }
}

///|
fn sparse_upsert_section_value(
  config : String,
  section : String,
  name : String,
  value_text : String,
) -> String {
  let header = "[\{section}]"
  let lines : Array[String] = []
  let mut in_section = false
  let mut found_section = false
  let mut key_set = false
  for line_view in config.split("\n") {
    let line = line_view.to_owned()
    let trimmed = sparse_trim(line)
    if trimmed == header {
      in_section = true
      found_section = true
      lines.push(line)
      continue
    }
    if in_section && trimmed.has_prefix("[") {
      if !key_set {
        lines.push("\t\{name} = \{value_text}")
        key_set = true
      }
      in_section = false
    }
    if in_section && trimmed.has_prefix("\{name} = ") {
      lines.push("\t\{name} = \{value_text}")
      key_set = true
      continue
    }
    lines.push(line)
  }
  if found_section {
    if in_section && !key_set {
      lines.push("\t\{name} = \{value_text}")
    }
  } else {
    if lines.length() > 0 && sparse_trim(lines[lines.length() - 1]) != "" {
      lines.push("")
    }
    lines.push(header)
    lines.push("\t\{name} = \{value_text}")
  }
  lines
  .iter()
  .fold(init="", fn(acc, line) {
    if acc == "" {
      line
    } else {
      acc + "\n" + line
    }
  })
}

///|
fn sparse_upsert_section_bool(
  config : String,
  section : String,
  name : String,
  value : Bool,
) -> String {
  let value_text = if value { "true" } else { "false" }
  sparse_upsert_section_value(config, section, name, value_text)
}

///|
fn sparse_upsert_core_bool(
  config : String,
  name : String,
  value : Bool,
) -> String {
  sparse_upsert_section_bool(config, "core", name, value)
}

///|
fn sparse_is_section_bool_enabled(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  section : String,
  name : String,
) -> Bool {
  let header = "[\{section}]"
  let config_paths = [
    join_path(git_dir, "config"),
    join_path(git_dir, "config.worktree"),
  ]
  for config_path in config_paths {
    if !rfs.is_file(config_path) {
      continue
    }
    let content = @utf8.decode_lossy(
      (rfs.read_file(config_path) catch { _ => continue })[:],
    )
    let mut in_section = false
    for line_view in content.split("\n") {
      let trimmed = sparse_trim(line_view.to_owned())
      if trimmed == header {
        in_section = true
        continue
      }
      if trimmed.has_prefix("[") {
        in_section = false
        continue
      }
      if in_section && trimmed.has_prefix(name) {
        if trimmed.contains("true") || trimmed.contains("= true") {
          return true
        }
      }
    }
  }
  false
}

///|
fn sparse_enable_worktree_config(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Unit raise @bit.GitError {
  // The extension lives in the repository's shared config: for a linked
  // worktree that is the common dir's, not `.git/worktrees//config`
  // (which git never reads). Only the main worktree's sparseCheckout goes
  // there too; a linked worktree keeps it in its own config.worktree so the
  // main worktree is not made sparse.
  let common_dir = resolve_common_git_dir(rfs, git_dir)
  let linked = normalize_path(common_dir) != normalize_path(git_dir)
  let config_path = join_path(common_dir, "config")
  let config = sparse_read_or_default_config(rfs, config_path)
  let with_version = sparse_upsert_section_value(
    config, "core", "repositoryformatversion", "1",
  )
  let config_with_extension = sparse_upsert_section_bool(
    if linked {
      with_version
    } else {
      sparse_upsert_core_bool(with_version, "sparseCheckout", true)
    },
    "extensions",
    "worktreeConfig",
    true,
  )
  fs.write_string(config_path, config_with_extension)

  let worktree_config_path = join_path(git_dir, "config.worktree")
  let worktree_config = sparse_read_or_default_config(rfs, worktree_config_path)
  fs.write_string(
    worktree_config_path,
    sparse_upsert_core_bool(worktree_config, "sparseCheckout", true),
  )
}

///|
pub fn sparse_set_index_sparse_config(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  value : Bool,
) -> Unit raise @bit.GitError {
  sparse_enable_worktree_config(fs, rfs, git_dir)
  let worktree_config_path = join_path(git_dir, "config.worktree")
  let worktree_config = sparse_read_or_default_config(rfs, worktree_config_path)
  fs.write_string(
    worktree_config_path,
    sparse_upsert_section_bool(worktree_config, "index", "sparse", value),
  )
}

///|
fn sparse_is_core_bool_enabled(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  name : String,
) -> Bool {
  sparse_is_section_bool_enabled(rfs, git_dir, "core", name)
}

///|
pub fn is_sparse_checkout_cone_enabled(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Bool {
  sparse_is_core_bool_enabled(rfs, git_dir, "sparseCheckoutCone")
}

///|
pub fn sparse_set_cone_config(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  value : Bool,
) -> Unit raise @bit.GitError {
  sparse_enable_worktree_config(fs, rfs, git_dir)
  let worktree_config_path = join_path(git_dir, "config.worktree")
  let worktree_config = sparse_read_or_default_config(rfs, worktree_config_path)
  let updated = sparse_upsert_core_bool(
    sparse_upsert_core_bool(worktree_config, "sparseCheckout", true),
    "sparseCheckoutCone",
    value,
  )
  fs.write_string(worktree_config_path, updated)
}

///|
fn sparse_normalize_cone_pattern(pattern : String) -> String? {
  let trimmed = sparse_trim(pattern)
  if trimmed.length() == 0 || trimmed == "/*" || trimmed == "!/*/" {
    return None
  }
  let without_bang = if trimmed.has_prefix("!") {
    String::unsafe_substring(trimmed, start=1, end=trimmed.length())
  } else {
    trimmed
  }
  let without_leading = if without_bang.has_prefix("/") {
    String::unsafe_substring(without_bang, start=1, end=without_bang.length())
  } else {
    without_bang
  }
  let normalized = if without_leading.has_suffix("/") &&
    without_leading.length() > 1 {
    String::unsafe_substring(
      without_leading,
      start=0,
      end=without_leading.length() - 1,
    )
  } else {
    without_leading
  }
  if normalized.length() == 0 {
    None
  } else {
    Some(normalized)
  }
}

///|
fn sparse_cone_is_descendant(path : String, parent : String) -> Bool {
  path.length() > parent.length() && path.has_prefix(parent + "/")
}

///|
fn sparse_is_stored_cone_pattern(pattern : String) -> Bool {
  let trimmed = sparse_trim(pattern)
  if trimmed == "/*" || trimmed == "!/*/" {
    return true
  }
  if trimmed.has_prefix("!/") {
    return trimmed.has_suffix("/*/") && trimmed.length() > 4
  }
  trimmed.has_prefix("/") && trimmed.has_suffix("/") && trimmed.length() > 2
}

///|
fn sparse_canonicalize_cone_patterns(patterns : Array[String]) -> Array[String] {
  let canonical : Array[String] = []
  for pattern in patterns {
    match sparse_normalize_cone_pattern(pattern) {
      None => ()
      Some(normalized) => {
        let mut covered = false
        let kept : Array[String] = []
        for existing in canonical {
          if existing == normalized ||
            sparse_cone_is_descendant(normalized, existing) {
            covered = true
          }
          // A duplicate stays (once): only descendants are dropped.
          if !sparse_cone_is_descendant(existing, normalized) {
            kept.push(existing)
          }
        }
        canonical.clear()
        for existing in kept {
          canonical.push(existing)
        }
        if !covered {
          canonical.push(normalized)
        }
      }
    }
  }
  canonical
}

///|
fn sparse_patterns_use_cone_mode(patterns : Array[String]) -> Bool {
  if patterns.length() == 0 {
    return true
  }
  if !patterns.contains("/*") || !patterns.contains("!/*/") {
    return false
  }
  for pattern in patterns {
    if !sparse_is_stored_cone_pattern(pattern) {
      return false
    }
  }
  true
}

///|
fn sparse_encode_cone_patterns(patterns : Array[String]) -> Array[String] {
  let out = sparse_default_patterns()
  for relative in sparse_canonicalize_cone_patterns(patterns) {
    let parts : Array[String] = []
    for part_view in relative.split("/") {
      let part = part_view.to_owned()
      if part.length() > 0 {
        parts.push(part)
      }
    }
    let mut current = ""
    if parts.length() > 1 {
      for i in 0..<(parts.length() - 1) {
        current = if current == "" {
          parts[i]
        } else {
          current + "/" + parts[i]
        }
        let parent = "/" + current + "/"
        if !out.contains(parent) {
          out.push(parent)
        }
        let exclude_children = "!/" + current + "/*/"
        if !out.contains(exclude_children) {
          out.push(exclude_children)
        }
      }
    }
    let stored = "/" + relative + "/"
    if !out.contains(stored) {
      out.push(stored)
    }
  }
  out
}

///|
/// Check if sparse checkout is enabled.
pub fn is_sparse_checkout_enabled(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Bool {
  sparse_is_core_bool_enabled(rfs, git_dir, "sparseCheckout")
}

///|
fn sparse_is_index_sparse_enabled(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Bool {
  sparse_is_section_bool_enabled(rfs, git_dir, "index", "sparse")
}

///|
/// Read sparse checkout patterns from .git/info/sparse-checkout.
pub fn read_sparse_patterns(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Array[String] raise @bit.GitError {
  let sparse_path = join_path(git_dir, "info/sparse-checkout")
  if !rfs.is_file(sparse_path) {
    return []
  }
  let content = rfs.read_file(sparse_path)
  let text = @utf8.decode_lossy(content[:])
  let patterns : Array[String] = []
  for line_view in text.split("\n") {
    let line = sparse_trim(line_view.to_owned())
    if line.length() > 0 && !line.has_prefix("#") {
      patterns.push(line)
    }
  }
  patterns
}

///|
pub fn read_sparse_display_patterns(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
) -> Array[String] raise @bit.GitError {
  let patterns = read_sparse_patterns(rfs, git_dir)
  if !is_sparse_checkout_cone_enabled(rfs, git_dir) {
    return patterns
  }
  let positive : Array[String] = []
  let exclude_children : Map[String, Bool] = Map([])
  for pattern in patterns {
    if pattern == "/*" || pattern == "!/*/" {
      continue
    }
    if pattern.has_prefix("!/") && pattern.has_suffix("/*/") {
      let normalized = String::unsafe_substring(
        pattern,
        start=2,
        end=pattern.length() - 3,
      )
      if normalized.length() > 0 {
        exclude_children[normalized] = true
      }
      continue
    }
    if pattern.has_prefix("!") {
      continue
    }
    match sparse_normalize_cone_pattern(pattern) {
      Some(normalized) if !positive.contains(normalized) =>
        positive.push(normalized)
      _ => ()
    }
  }
  let display : Array[String] = []
  for candidate in positive {
    let mut intermediate = false
    if exclude_children.contains(candidate) {
      for other in positive {
        if sparse_cone_is_descendant(other, candidate) {
          intermediate = true
          break
        }
      }
    }
    if !intermediate {
      display.push(candidate)
    }
  }
  display
}

///|
/// Write sparse checkout patterns to .git/info/sparse-checkout.
pub fn write_sparse_patterns(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  patterns : Array[String],
) -> Unit raise @bit.GitError {
  let info_dir = join_path(git_dir, "info")
  fs.mkdir_p(info_dir)
  let sparse_path = join_path(git_dir, "info/sparse-checkout")
  let lock_path = sparse_path + ".lock"
  if rfs.is_file(lock_path) {
    raise @bit.GitError::InvalidObject(
      "Unable to create '\{lock_path}': File exists.",
    )
  }
  let content = patterns
    .iter()
    .fold(init="", fn(acc, p) {
      if acc.length() == 0 {
        p + "\n"
      } else {
        acc + p + "\n"
      }
    })
  fs.write_string(sparse_path, content)
}

///|
/// Initialize sparse checkout.
pub fn sparse_checkout_init(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
  cone? : Bool = false,
  update_worktree? : Bool = true,
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  // extensions.worktreeConfig belongs in the shared (common dir) config.
  let config_path = join_path(resolve_common_git_dir(rfs, git_dir), "config")
  let config = sparse_read_or_default_config(rfs, config_path)
  let updated = sparse_upsert_section_bool(
    sparse_upsert_section_value(config, "core", "repositoryformatversion", "1"),
    "extensions",
    "worktreeConfig",
    true,
  )
  fs.write_string(config_path, updated)
  sparse_set_cone_config(fs, rfs, git_dir, cone)
  let sparse_path = join_path(git_dir, "info/sparse-checkout")
  if !rfs.is_file(sparse_path) {
    write_sparse_patterns(fs, rfs, git_dir, sparse_default_patterns())
  }
  if update_worktree {
    sparse_update_worktree(fs, rfs, root)
  }
}

///|
/// Set sparse checkout patterns (replaces existing patterns).
pub fn sparse_checkout_set(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
  patterns : Array[String],
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  // Ensure sparse checkout is initialized -- without applying the default
  // patterns first: git goes straight to the new ones.
  if !is_sparse_checkout_enabled(rfs, git_dir) {
    sparse_checkout_init(fs, rfs, root, update_worktree=false)
  }
  sparse_enable_worktree_config(fs, rfs, git_dir)
  let stored_patterns = if is_sparse_checkout_cone_enabled(rfs, git_dir) {
    sparse_encode_cone_patterns(patterns)
  } else {
    patterns
  }
  write_sparse_patterns(fs, rfs, git_dir, stored_patterns)
  // Update worktree
  sparse_update_worktree(fs, rfs, root)
}

///|
/// Add patterns to sparse checkout.
pub fn sparse_checkout_add(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
  new_patterns : Array[String],
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  // Ensure sparse checkout is initialized
  if !is_sparse_checkout_enabled(rfs, git_dir) {
    sparse_checkout_init(fs, rfs, root)
  }
  sparse_enable_worktree_config(fs, rfs, git_dir)
  let cone_mode = is_sparse_checkout_cone_enabled(rfs, git_dir)
  let existing = read_sparse_patterns(rfs, git_dir)
  if cone_mode && !sparse_patterns_use_cone_mode(existing) {
    raise @bit.GitError::InvalidObject(
      "existing sparse-checkout patterns do not use cone mode",
    )
  }
  let next_patterns = if cone_mode {
    let display = read_sparse_display_patterns(rfs, git_dir)
    for p in new_patterns {
      if !display.contains(p) {
        display.push(p)
      }
    }
    sparse_encode_cone_patterns(display)
  } else {
    for p in new_patterns {
      if !existing.contains(p) {
        existing.push(p)
      }
    }
    existing
  }
  write_sparse_patterns(fs, rfs, git_dir, next_patterns)
  // Update worktree
  sparse_update_worktree(fs, rfs, root)
}

///|
/// Disable sparse checkout.
pub fn sparse_checkout_disable(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  // Update config to disable
  let config_path = join_path(git_dir, "config")
  if rfs.is_file(config_path) {
    let config = @utf8.decode_lossy(rfs.read_file(config_path)[:])
    let new_config = config
      .replace(old="sparseCheckout = true", new="sparseCheckout = false")
      .replace(
        old="sparseCheckoutCone = true",
        new="sparseCheckoutCone = false",
      )
    fs.write_string(config_path, new_config)
  }
  let worktree_config_path = join_path(git_dir, "config.worktree")
  if rfs.is_file(worktree_config_path) {
    let worktree_config = sparse_read_or_default_config(
      rfs, worktree_config_path,
    )
    fs.write_string(
      worktree_config_path,
      sparse_upsert_core_bool(
        sparse_upsert_core_bool(worktree_config, "sparseCheckout", false),
        "sparseCheckoutCone",
        false,
      ),
    )
  }
  // Materialize the skipped entries that are missing, keep the index
  // (staged changes) and every existing file, and clear the bits.
  if !rfs.is_file(join_path(git_dir, "index")) ||
    read_unmerged_paths(rfs, git_dir).length() > 0 {
    return
  }
  let db = ObjectDb::load(rfs, git_dir)
  let raw_entries = read_index_entries(rfs, git_dir)
  let entries = expand_sparse_index_entries(rfs, git_dir, raw_entries)
  let skip = expand_sparse_skip_worktree_paths(
    rfs,
    git_dir,
    raw_entries,
    read_skip_worktree_paths(rfs, git_dir),
  )
  let to_write : Map[String, TreeFileEntry] = Map([])
  for e in entries {
    if skip.contains(e.path) &&
      !is_gitlink_mode_int(e.mode) &&
      @bitio.worktree_entry_meta_sync(rfs, join_path(root, e.path)) is None {
      to_write[e.path] = { id: e.id, mode: e.mode }
    }
  }
  write_worktree_from_files(db, fs, rfs, root, git_dir, to_write)
  write_skip_worktree_paths(fs, git_dir, [])
  write_index_entries_with_skip_worktree(fs, git_dir, entries, Map([]))
}

///|
///
/// `leave` lists paths whose file stays on disk even when it is clean (a
/// checkout's new entries that it did not write: git marks them
/// skip-worktree without removing what is already there).
pub fn sparse_checkout_reapply(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
  leave? : Map[String, Bool] = Map([]),
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  if !is_sparse_checkout_enabled(rfs, git_dir) {
    sparse_checkout_init(fs, rfs, root)
  }
  sparse_enable_worktree_config(fs, rfs, git_dir)
  sparse_update_worktree(fs, rfs, root, preserve_index=true, leave~)
}

///|
/// Check if a path matches any of the sparse checkout patterns.
pub fn matches_sparse_pattern(path : String, patterns : Array[String]) -> Bool {
  if patterns.length() == 0 {
    return true // No patterns means include everything
  }
  let mut included = false
  for pattern in patterns {
    if pattern.has_prefix("!") {
      // Negation pattern
      let neg_pattern = String::unsafe_substring(
        pattern,
        start=1,
        end=pattern.length(),
      )
      if sparse_path_matches(path, neg_pattern) {
        included = false
      }
    } else if sparse_path_matches(path, pattern) {
      included = true
    }
  }
  included
}

///|
/// Simple glob-like pattern matching for sparse checkout.
fn sparse_path_matches(path : String, pattern : String) -> Bool {
  let anchored = pattern.has_prefix("/")
  let normalized_pattern = if pattern.has_prefix("/") &&
    pattern != "/*" &&
    pattern != "!/*/" {
    String::unsafe_substring(pattern, start=1, end=pattern.length())
  } else {
    pattern
  }
  // Handle common patterns:
  // "/*" - match all files in root
  // "!/*/  " - exclude all directories in root
  // "dir/" - match directory and contents
  // "dir/*" - match files in directory
  // "*.txt" - match files ending in .txt
  if normalized_pattern == "/*" {
    // Match files in root (no slash in path)
    return !path.contains("/")
  }
  if normalized_pattern == "/*/" {
    // Used by the default negation pattern "!/*/" to exclude root directories.
    return path.contains("/")
  }
  if normalized_pattern.has_prefix("*") &&
    normalized_pattern.has_suffix("*") &&
    normalized_pattern.length() > 1 {
    let needle = String::unsafe_substring(
      normalized_pattern,
      start=1,
      end=normalized_pattern.length() - 1,
    )
    return needle.length() == 0 || path.contains(needle)
  }
  if normalized_pattern.has_suffix("/*/") {
    let dir = String::unsafe_substring(
      normalized_pattern,
      start=0,
      end=normalized_pattern.length() - 3,
    )
    if path.has_prefix(dir + "/") {
      let rest = String::unsafe_substring(
        path,
        start=dir.length() + 1,
        end=path.length(),
      )
      return rest.contains("/")
    }
    return false
  }
  if normalized_pattern.has_suffix("/") {
    // Directory pattern - match if path starts with this directory
    let dir = String::unsafe_substring(
      normalized_pattern,
      start=0,
      end=normalized_pattern.length() - 1,
    )
    return sparse_path_matches_unanchored_prefix(path, dir, anchored)
  }
  if normalized_pattern.has_suffix("/*") {
    // Match files directly in directory
    let dir = String::unsafe_substring(
      normalized_pattern,
      start=0,
      end=normalized_pattern.length() - 2,
    )
    if path.has_prefix(dir + "/") {
      let rest = String::unsafe_substring(
        path,
        start=dir.length() + 1,
        end=path.length(),
      )
      return !rest.contains("/")
    }
    return false
  }
  if normalized_pattern.has_prefix("*") {
    // Wildcard at start
    let suffix = String::unsafe_substring(
      normalized_pattern,
      start=1,
      end=normalized_pattern.length(),
    )
    return path.has_suffix(suffix)
  }
  if normalized_pattern.has_suffix("*") {
    // Wildcard at end
    let prefix = String::unsafe_substring(
      normalized_pattern,
      start=0,
      end=normalized_pattern.length() - 1,
    )
    return path.has_prefix(prefix)
  }
  if normalized_pattern.contains("**") {
    // Double star matches any path
    let parts = normalized_pattern.split("**")
    let parts_arr : Array[String] = []
    for p in parts {
      parts_arr.push(p.to_owned())
    }
    if parts_arr.length() == 2 {
      let prefix = parts_arr[0]
      let suffix = parts_arr[1]
      return (prefix.length() == 0 || path.has_prefix(prefix)) &&
        (suffix.length() == 0 || path.has_suffix(suffix))
    }
  }
  // Exact match or path prefix
  sparse_path_matches_unanchored_prefix(path, normalized_pattern, anchored)
}

///|
fn sparse_path_matches_unanchored_prefix(
  path : String,
  pattern : String,
  anchored : Bool,
) -> Bool {
  if anchored {
    return path == pattern || path.has_prefix(pattern + "/")
  }
  path == pattern ||
  path.has_prefix(pattern + "/") ||
  path.has_suffix("/" + pattern) ||
  path.contains("/" + pattern + "/")
}

///|
fn sparse_collect_tree_ids(
  db : ObjectDb,
  rfs : &@bit.RepoFileSystem,
  tree_id : @bit.ObjectId,
  prefix : String,
  out : Map[String, @bit.ObjectId],
) -> Unit raise @bit.GitError {
  let tree_obj = db.get(rfs, tree_id)
  match tree_obj {
    None =>
      raise @bit.GitError::InvalidObject(
        "Missing tree object: " + tree_id.to_hex(),
      )
    Some(obj) => {
      if obj.obj_type != @bit.ObjectType::Tree {
        raise @bit.GitError::InvalidObject("Object is not a tree")
      }
      let entries = @bit.parse_tree(obj.data)
      for entry in entries {
        if entry.mode != "40000" {
          continue
        }
        let path = if prefix == "" {
          entry.name
        } else {
          prefix + "/" + entry.name
        }
        out[path] = entry.id
        sparse_collect_tree_ids(db, rfs, entry.id, path, out)
      }
    }
  }
}

///|
fn sparse_parent_dirs(path : String) -> Array[String] {
  let out : Array[String] = []
  let mut current = path
  while current.contains("/") {
    let mut slash = -1
    for i = current.length() - 1; i >= 0; i = i - 1 {
      if current.unsafe_get(i) == '/' {
        slash = i
        break
      }
    }
    if slash <= 0 {
      break
    }
    current = String::unsafe_substring(current, start=0, end=slash)
    if current.length() > 0 && !out.contains(current) {
      out.push(current)
    }
  }
  out
}

///|
fn sparse_path_depth(path : String) -> Int {
  let mut depth = 0
  for i = 0; i < path.length(); i = i + 1 {
    if path.unsafe_get(i) == '/' {
      depth = depth + 1
    }
  }
  depth
}

///|
fn sparse_is_under_dir(path : String, dir : String) -> Bool {
  path.has_prefix(dir + "/")
}

///|
fn sparse_build_sparse_index_entries(
  db : ObjectDb,
  rfs : &@bit.RepoFileSystem,
  commit_id : @bit.ObjectId,
  all_files : Map[String, TreeFileEntry],
  skip_paths : Array[String],
) -> (Array[IndexEntry], Map[String, Bool]) raise @bit.GitError {
  let tree_ids : Map[String, @bit.ObjectId] = Map([])
  let commit_obj = db.get(rfs, commit_id)
  match commit_obj {
    None => raise @bit.GitError::InvalidObject("Missing commit object")
    Some(obj) => {
      if obj.obj_type != @bit.ObjectType::Commit {
        raise @bit.GitError::InvalidObject("Object is not a commit")
      }
      let info = @bit.parse_commit(obj.data)
      sparse_collect_tree_ids(db, rfs, info.tree, "", tree_ids)
    }
  }

  let candidate_dirs : Array[String] = []
  for path in skip_paths {
    for dir in sparse_parent_dirs(path) {
      if !candidate_dirs.contains(dir) {
        candidate_dirs.push(dir)
      }
    }
  }
  candidate_dirs.sort_by(fn(left, right) {
    let left_depth = sparse_path_depth(left)
    let right_depth = sparse_path_depth(right)
    if left_depth == right_depth {
      String::compare(left, right)
    } else {
      left_depth - right_depth
    }
  })

  let sparse_dirs : Array[String] = []
  for dir in candidate_dirs {
    let mut has_files = false
    let mut fully_skipped = true
    for path in all_files.keys() {
      if !sparse_is_under_dir(path, dir) {
        continue
      }
      has_files = true
      if !skip_paths.contains(path) {
        fully_skipped = false
        break
      }
    }
    if !has_files || !fully_skipped {
      continue
    }
    let mut shadowed = false
    for existing in sparse_dirs {
      if sparse_is_under_dir(dir, existing) {
        shadowed = true
        break
      }
    }
    if !shadowed {
      sparse_dirs.push(dir)
    }
  }

  let sparse_dir_set : Map[String, Bool] = Map([])
  for dir in sparse_dirs {
    sparse_dir_set[dir] = true
  }

  let kept_files : Map[String, TreeFileEntry] = Map([])
  let skip_set : Map[String, Bool] = Map([])
  for path, entry in all_files {
    let mut collapsed = false
    for dir in sparse_dirs {
      if sparse_is_under_dir(path, dir) {
        collapsed = true
        break
      }
    }
    if collapsed {
      continue
    }
    kept_files[path] = entry
    if skip_paths.contains(path) {
      skip_set[path] = true
    }
  }

  let entries = tree_files_to_index(db, rfs, kept_files)
  for dir in sparse_dirs {
    match tree_ids.get(dir) {
      Some(tree_id) =>
        entries.push(IndexEntry::new(dir + "/", tree_id, 0o040000, 0))
      None => ()
    }
    skip_set[dir + "/"] = true
  }
  entries.sort_by((a, b) => index_path_compare_git_order(a.path, b.path))
  (entries, skip_set)
}

///|
/// Update worktree based on sparse checkout patterns.
fn sparse_update_worktree(
  fs : &@bit.FileSystem,
  rfs : &@bit.RepoFileSystem,
  root : String,
  preserve_index? : Bool = false,
  leave? : Map[String, Bool] = Map([]),
) -> Unit raise @bit.GitError {
  let git_dir = resolve_root_git_dir(rfs, root)
  if !rfs.is_file(join_path(git_dir, "index")) {
    return
  }
  let patterns = read_sparse_patterns(rfs, git_dir)
  // Unmerged entries are left as they are (git warns about them); the
  // other entries still get their skip-worktree bits updated, and the
  // conflict stages are written back unchanged.
  let unmerged = read_unmerged_paths(rfs, git_dir)
  if unmerged.length() > 0 &&
    sparse_is_index_sparse_enabled(rfs, git_dir) &&
    is_sparse_checkout_cone_enabled(rfs, git_dir) {
    return
  }
  let head = resolve_head_commit(rfs, git_dir)
  match head {
    None => ()
    Some(commit_id) => {
      let db = ObjectDb::load(rfs, git_dir)
      let autocrlf = read_autocrlf_setting(rfs, git_dir)
      let current_raw_entries = read_index_entries(rfs, git_dir).filter(e => !unmerged.contains(
        e.path,
      ))
      // Like git, the index is kept as is (staged changes survive); only
      // the skip-worktree bits and the worktree files change.
      let current_entries = expand_sparse_index_entries(
        rfs, git_dir, current_raw_entries,
      )
      let prev_skip = expand_sparse_skip_worktree_paths(
        rfs,
        git_dir,
        current_raw_entries,
        read_skip_worktree_paths(rfs, git_dir),
      )
      let all_files : Map[String, TreeFileEntry] = Map([])
      let to_write : Map[String, TreeFileEntry] = Map([])
      let skip_paths : Array[String] = []
      let emptied : Array[String] = []
      for entry in current_entries {
        all_files[entry.path] = { id: entry.id, mode: entry.mode }
        let abs = join_path(root, entry.path)
        let present = @bitio.worktree_entry_meta_sync(rfs, abs) is Some(_)
        if matches_sparse_pattern(entry.path, patterns) {
          // Newly in the cone: materialize what was skipped (an existing
          // file is left alone).
          if prev_skip.contains(entry.path) &&
            !present &&
            !is_gitlink_mode_int(entry.mode) {
            to_write[entry.path] = { id: entry.id, mode: entry.mode }
          }
          continue
        }
        if !present || leave.contains(entry.path) {
          skip_paths.push(entry.path)
          continue
        }
        // Reapply prunes root-level skipped files back to the patterns,
        // while dirty paths inside skipped directories are preserved.
        let clean = (preserve_index && !entry.path.contains("/")) ||
          sparse_worktree_matches_index_entry(
            rfs,
            root,
            entry.path,
            entry,
            autocrlf,
          )
        if clean {
          if is_gitlink_mode_int(entry.mode) {
            skip_paths.push(entry.path)
            continue
          }
          fs.remove_file(abs)
          emptied.push(parent_dir(abs))
          skip_paths.push(entry.path)
        }
        // A dirty file stays, and stays tracked normally (git warns).
      }
      write_worktree_from_files(db, fs, rfs, root, git_dir, to_write)
      // Only directories this update emptied go (git), not every empty one.
      tree_ops_prune_empty_dirs(fs, rfs, root, emptied)
      write_skip_worktree_paths(fs, git_dir, skip_paths)
      let use_sparse_index = sparse_is_index_sparse_enabled(rfs, git_dir) &&
        is_sparse_checkout_cone_enabled(rfs, git_dir)
      if unmerged.length() > 0 {
        let skip_set : Map[String, Bool] = Map([])
        for path in skip_paths {
          skip_set[path] = true
        }
        write_index_stage_entries(
          fs,
          git_dir,
          read_index_stage_entries(rfs, git_dir),
          skip=skip_set,
        )
      } else if use_sparse_index {
        let (entries, skip_set) = sparse_build_sparse_index_entries(
          db, rfs, commit_id, all_files, skip_paths,
        )
        write_index_entries_with_flags(fs, git_dir, entries, skip_set, Map([]))
      } else {
        let skip_set : Map[String, Bool] = Map([])
        for path in skip_paths {
          skip_set[path] = true
        }
        write_index_entries_with_skip_worktree(
          fs, git_dir, current_entries, skip_set,
        )
      }
    }
  }
}

///|
fn sparse_worktree_matches_index_entry(
  rfs : &@bit.RepoFileSystem,
  root : String,
  path : String,
  entry : IndexEntry,
  autocrlf : AutoCrlf,
) -> Bool raise @bit.GitError {
  let abs = join_path(root, path)
  match @bitio.worktree_entry_meta_sync(rfs, abs) {
    None => false
    Some(info) =>
      match info.kind {
        @bitio.WorktreeKindMeta::Regular => {
          if info.mode != entry.mode {
            return false
          }
          let content = rfs.read_file(abs)
          let attrs = resolve_eol_attrs(rfs, root, path)
          let normalized = clean_for_storage(content, attrs, autocrlf)
          @bit.hash_blob(normalized) == entry.id
        }
        @bitio.WorktreeKindMeta::Symlink => {
          // The meta mode of a symlink is not 120000; the kind is what counts.
          if entry.mode != 0o120000 {
            return false
          }
          match @bitio.read_symlink_target_path(abs) {
            Some(target) => @bit.hash_blob(@utf8.encode(target)) == entry.id
            None => false
          }
        }
      }
  }
}

///|
fn sparse_trim(s : String) -> String {
  @string_utils.trim_string(s)
}

///|
/// Keep only `paths` inside the sparse-checkout patterns (all of them when
/// sparse checkout is off): git's `commit -a` / `add -u` leave tracked
/// paths outside the cone alone even when they are dirty.
pub fn filter_paths_in_sparse_checkout(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  paths : Array[String],
) -> Array[String] {
  if !is_sparse_checkout_enabled(rfs, git_dir) {
    return paths
  }
  let patterns = read_sparse_patterns(rfs, git_dir) catch { _ => return paths }
  paths.filter(p => matches_sparse_pattern(p, patterns))
}

///|
/// Paths inside the sparse cone that a merge-like command wrote over an
/// untracked file. git reports them with its "already present and thus
/// not updated despite sparse patterns" warning even though, with sparse
/// checkout, unpack-trees still writes the new entry there (5fabca56).
/// The command layer drains this with `take_sparse_not_updated_paths`.
let sparse_not_updated_paths : Array[String] = []

///|
/// Record the untracked paths a command is about to write over; only those
/// inside the sparse cone are what git's warning lists.
pub fn note_sparse_not_updated(
  rfs : &@bit.RepoFileSystem,
  git_dir : String,
  paths : Array[String],
) -> Unit {
  if paths.length() == 0 || !is_sparse_checkout_enabled(rfs, git_dir) {
    return
  }
  let patterns = read_sparse_patterns(rfs, git_dir) catch { _ => return }
  for p in paths {
    if matches_sparse_pattern(p, patterns) && !sparse_not_updated_paths.contains(p) {
      sparse_not_updated_paths.push(p)
    }
  }
}

///|
/// Return (and clear) the paths recorded by `note_sparse_not_updated`,
/// sorted.
pub fn take_sparse_not_updated_paths() -> Array[String] {
  let out = sparse_not_updated_paths.copy()
  sparse_not_updated_paths.clear()
  out.sort()
  out
}