///| Gitignore-style pattern matching
///
/// Pure gitignore pattern matcher with zero dependencies.
/// Implements the full `.gitignore` specification: `*`, `?`, `**` globs,
/// negation (`!`), directory-only rules (`/`), anchored patterns,
/// nested base directories, and comment/escape handling.
///
/// ## Quick start — filter files with `.gitignore` rules
///
/// ```moonbit
/// let m = @ignore.Matcher::new()
/// m.add_rules("", "node_modules/\n*.log\n!important.log\n")
///
/// assert_true(m.is_ignored("node_modules/express/index.js", false))
/// assert_true(m.is_ignored("debug.log", false))
/// assert_false(m.is_ignored("important.log", false))
/// assert_false(m.is_ignored("src/app.ts", false))
/// ```
///
/// ## Use as a git-aware glob filter
///
/// Stack multiple `.gitignore` files from nested directories,
/// then filter a file list in one pass:
///
/// ```moonbit
/// let m = @ignore.Matcher::new()
///
/// // Root .gitignore
/// m.add_rules("", "*.log\n/dist/\nbuild/\n")
///
/// // Subdirectory .gitignore (rules scoped to "src/")
/// m.add_rules("src", "*.generated.*\n!keep.generated.ts\n")
///
/// // Filter a list of paths
/// let files : Array[String] = [
///   "src/app.ts",            // kept
///   "src/data.generated.js", // ignored by src/.gitignore
///   "src/keep.generated.ts", // kept (negation)
///   "dist/bundle.js",        // ignored by /dist (anchored)
///   "lib/build/out.o",       // ignored by build/
///   "server.log",            // ignored by *.log
/// ]
/// let visible = files.filter(fn(p) { !(m.is_ignored(p, false)) })
/// // visible = ["src/app.ts", "src/keep.generated.ts"]
/// ```
///
/// ## Directory traversal with backtracking
///
/// Use `truncate()` to scope rules when walking a directory tree:
///
/// ```moonbit
/// let m = @ignore.Matcher::new()
/// m.add_rules("", "*.tmp\n")
///
/// // Enter "src/" — add its .gitignore
/// let saved = m.len()
/// m.add_rules("src", "*.bak\n")
/// assert_true(m.is_ignored("src/file.bak", false))
///
/// // Leave "src/" — restore matcher state
/// m.truncate(saved)
/// assert_false(m.is_ignored("src/file.bak", false))
/// // Root rules still active
/// assert_true(m.is_ignored("any/path/file.tmp", false))
/// ```
///
/// ## Standalone glob matching
///
/// `match_glob` works as a general-purpose glob matcher
/// (not tied to gitignore semantics):
///
/// ```moonbit
/// assert_true(@ignore.match_glob("*.ts", "app.ts"))
/// assert_true(@ignore.match_glob("src/*.test.*", "src/app.test.js"))
/// assert_false(@ignore.match_glob("*.ts", "app.js"))
/// ```
///
/// ## Pattern syntax reference
///
/// | Pattern | Matches |
/// |---------|---------|
/// | `*.log` | Any file ending in `.log` at any depth |
/// | `node_modules/` | The `node_modules` directory and all contents |
/// | `/build/` | Only `build/` directory at the root (anchored) |
/// | `!important.log` | Un-ignore `important.log` (negation) |
/// | `**/*.test.js` | `.test.js` files at any depth |
/// | `doc/**/*.md` | `.md` files under `doc/` at any depth |
/// | `temp?` | `temp` + any single character (`temp1`, `tempA`) |
/// | `[ab].txt` | `a.txt` or `b.txt` (character class) |
/// | `log[0-9]` | `log0` … `log9` (range; `[!0-9]` / `[^0-9]` negate) |
/// | `x[[:digit:]]` | `x` + a digit (POSIX class) |
/// | `file\?.txt` | Literal `file?.txt` (`\` escapes `?`, `*`, `[`, …) |
/// | `\!literal` | Match literal `!` (escaped) |
/// | `name\ ` | `name ` with its trailing space kept |
///
/// ## Performance
///
/// Pattern segments are pre-compiled at parse time. Path matching
/// operates on string ranges without allocating substrings.
///
/// - `match_glob`: ~0.3 µs per call
/// - `is_ignored` (20 rules): ~4–8 µs per path
/// - 1000 paths × 20 rules: ~4 ms

///|
/// A single ignore rule parsed from a gitignore file.
pub struct Rule {
  /// Base directory where the rule was defined (relative path)
  base : String
  /// The pattern to match against
  pattern : String
  /// Pre-compiled pattern code units for match_glob (avoids repeated to_array allocation)
  pattern_chars : FixedArray[UInt16]
  /// Pre-split pattern segments for path matching (avoids repeated split_path)
  pattern_segments : Array[FixedArray[UInt16]]
  /// Whether this is a negation rule (starts with !)
  negated : Bool
  /// Whether this rule only applies to directories (ends with /)
  dir_only : Bool
  /// Whether this rule is anchored to the base (starts with /)
  anchored : Bool
  /// Whether the pattern contains a slash (affects matching behavior)
  has_slash : Bool
  /// Length of base string (cached for fast prefix check)
  base_len : Int
}

///|
/// A collection of ignore rules that can check if paths are ignored.
pub struct Matcher {
  rules : Array[Rule]
  mut negation_count : Int
}

///|
/// Create a new empty matcher.
pub fn Matcher::new() -> Matcher {
  { rules: [], negation_count: 0 }
}

///|
/// Add rules from gitignore content.
/// `base` is the relative directory where the gitignore file is located.
pub fn Matcher::add_rules(
  self : Matcher,
  base : String,
  content : String,
) -> Unit {
  let parsed = parse(content, base)
  for rule in parsed {
    self.rules.push(rule)
    if rule.negated {
      self.negation_count = self.negation_count + 1
    }
  }
}

///|
/// Check if a path is ignored.
/// `rel_path` is the path relative to the root.
/// `is_dir` indicates whether the path is a directory.
pub fn Matcher::is_ignored(
  self : Matcher,
  rel_path : String,
  is_dir : Bool,
) -> Bool {
  let mut ignored = false
  for rule in self.rules {
    if rule_applies(rule, rel_path, is_dir) {
      ignored = !rule.negated
    }
  }
  ignored
}

///|
/// Remove rules added after a certain point (for backtracking during traversal).
pub fn Matcher::truncate(self : Matcher, len : Int) -> Unit {
  let mut i = len
  let total = self.rules.length()
  while i < total {
    if self.rules[i].negated {
      self.negation_count = self.negation_count - 1
    }
    i = i + 1
  }
  self.rules.truncate(len)
}

///|
/// Get current number of rules.
pub fn Matcher::len(self : Matcher) -> Int {
  self.rules.length()
}

///|
/// Whether any negation rules have been added.
pub fn Matcher::has_negation(self : Matcher) -> Bool {
  self.negation_count > 0
}

///|
/// Check if any negation rule could potentially un-ignore a child under `dir_rel`.
/// More precise than `has_negation()` — only returns true if a negation rule's
/// target path overlaps with the given directory.
pub fn Matcher::could_negate_under(self : Matcher, dir_rel : String) -> Bool {
  if self.negation_count == 0 {
    return false
  }
  for rule in self.rules {
    if !rule.negated {
      continue
    }
    // Non-path-specific rules (no slash, not anchored) could match anywhere
    if !rule.has_slash && !rule.anchored {
      return true
    }
    // Path-specific rule: compute target path and check prefix overlap
    let target = if rule.base.length() == 0 {
      rule.pattern
    } else {
      rule.base + "/" + rule.pattern
    }
    let prefix = negation_literal_prefix(target)
    if prefix.length() == 0 {
      return true
    }
    // Check if dir_rel is an ancestor of prefix or prefix is an ancestor of dir_rel
    if is_path_prefix(dir_rel, prefix) || is_path_prefix(prefix, dir_rel) {
      return true
    }
  }
  false
}

///|
/// Extract the literal directory prefix before any wildcard in a pattern.
fn negation_literal_prefix(pattern : String) -> String {
  let mut last_slash = -1
  for i in 0.. Bool {
  let alen = a.length()
  let blen = b.length()
  if alen > blen {
    return false
  }
  for i in 0.. Array[Rule] {
  let rules : Array[Rule] = []
  let base_len = base.length()
  for line_view in content.split("\n") {
    let mut line = line_view.to_owned()
    // Handle CRLF
    if line.has_suffix("\r") {
      line = String::unsafe_substring(line, start=0, end=line.length() - 1)
    }
    // Trim trailing whitespace (but not leading - significant for patterns)
    line = trim_trailing_whitespace(line)
    // Skip empty lines
    if line.length() == 0 {
      continue
    }
    // Skip comments
    if line.has_prefix("#") {
      continue
    }
    // Handle escaped characters
    let mut negated = false
    if line.has_prefix("\\!") {
      line = String::unsafe_substring(line, start=1, end=line.length())
    } else if line.has_prefix("!") {
      negated = true
      line = String::unsafe_substring(line, start=1, end=line.length())
    }
    if line.has_prefix("\\#") {
      line = String::unsafe_substring(line, start=1, end=line.length())
    }
    if line.length() == 0 {
      continue
    }
    // Check for directory-only rule
    let mut dir_only = false
    if line.has_suffix("/") {
      dir_only = true
      line = String::unsafe_substring(line, start=0, end=line.length() - 1)
    }
    if line.length() == 0 {
      continue
    }
    // Check for anchored rule
    let mut anchored = false
    if line.has_prefix("/") {
      anchored = true
      line = String::unsafe_substring(line, start=1, end=line.length())
    }
    if line.length() == 0 {
      continue
    }
    let has_slash = line.contains("/")
    let pattern_chars = string_to_uint16_array(line)
    // Pre-split pattern into segments for path matching
    let pattern_segments = if has_slash || anchored {
      precompile_segments(line)
    } else {
      []
    }
    rules.push({
      base,
      pattern: line,
      pattern_chars,
      pattern_segments,
      negated,
      dir_only,
      anchored,
      has_slash,
      base_len,
    })
  }
  rules
}

///|
let char_star : UInt16 = {
  let c : Int = '*'.to_int()
  c.to_uint16()
}

///|
let char_question : UInt16 = {
  let c : Int = '?'.to_int()
  c.to_uint16()
}

///|
let char_slash : UInt16 = {
  let c : Int = '/'.to_int()
  c.to_uint16()
}

///|
fn string_to_uint16_array(s : String) -> FixedArray[UInt16] {
  let len = s.length()
  let arr = FixedArray::make(len, Default::default())
  for i in 0.. Array[FixedArray[UInt16]] {
  let segs : Array[FixedArray[UInt16]] = []
  let len = pattern.length()
  let mut start = 0
  while start < len {
    let mut end = start
    while end < len && pattern.unsafe_get(end) != char_slash {
      end += 1
    }
    if end > start {
      segs.push(
        string_to_uint16_array(String::unsafe_substring(pattern, start~, end~)),
      )
    }
    start = end + 1
  }
  segs
}

///|
/// Check if a single pattern matches a path segment, with gitignore glob
/// syntax: `*`, `?`, bracket expressions (`[ab]`, `[0-9]`, `[!0-9]`,
/// `[^a]`, `[[:digit:]]`) and backslash escapes (`\?`, `\*`, `\[`).
pub fn match_glob(pattern : String, text : String) -> Bool {
  let p = string_to_uint16_array(pattern)
  match_glob_precompiled_range(p, text, 0, text.length())
}

///|
/// Match a precompiled pattern against a substring of text (segment between
/// slashes).
fn match_glob_precompiled_range(
  p : FixedArray[UInt16],
  text : String,
  start : Int,
  end : Int,
) -> Bool {
  let plen = p.length()
  let mut pi = 0
  let mut si = start
  let mut star = -1
  let mut mark = start
  while si < end {
    if pi < plen && p[pi] == char_star {
      star = pi
      mark = si
      pi += 1
      continue
    }
    if pi < plen {
      let next = glob_match_one(p, pi, text.unsafe_get(si))
      if next == glob_abort {
        return false
      }
      if next >= 0 {
        pi = next
        si += 1
        continue
      }
    }
    if star == -1 {
      return false
    }
    pi = star + 1
    mark += 1
    si = mark
  }
  while pi < plen && p[pi] == char_star {
    pi += 1
  }
  pi == plen
}

///|
/// Returned by `glob_match_one` for a malformed pattern (an unterminated
/// bracket expression or a trailing backslash), which, as in git, never
/// matches anything.
let glob_abort : Int = -2

///|
/// Match the single-character pattern token at `pi` (a literal, `?`, an
/// escaped character or a bracket expression) against `c`. Returns the index
/// after the token on a match, -1 on a mismatch, or `glob_abort`.
fn glob_match_one(p : FixedArray[UInt16], pi : Int, c : UInt16) -> Int {
  let tok = p[pi]
  if tok == char_question {
    pi + 1
  } else if tok == char_backslash {
    if pi + 1 >= p.length() {
      glob_abort
    } else if p[pi + 1] == c {
      pi + 2
    } else {
      -1
    }
  } else if tok == char_open_bracket {
    glob_match_class(p, pi, c)
  } else if tok == c {
    pi + 1
  } else {
    -1
  }
}

///|
/// Match the bracket expression starting at `p[pi] == '['` against `c`.
fn glob_match_class(p : FixedArray[UInt16], pi : Int, c : UInt16) -> Int {
  let plen = p.length()
  let mut i = pi + 1
  let negated = i < plen && (p[i] == char_bang || p[i] == char_caret)
  if negated {
    i += 1
  }
  let mut matched = false
  let mut first = true
  while true {
    if i >= plen {
      return glob_abort
    }
    let tok = p[i]
    if tok == char_close_bracket && !first {
      break
    }
    first = false
    // POSIX character class such as [:digit:]
    if tok == char_open_bracket && i + 1 < plen && p[i + 1] == char_colon {
      match glob_posix_class_end(p, i + 2) {
        Some(name_end) => {
          if glob_posix_class_matches(p, i + 2, name_end, c) {
            matched = true
          }
          i = name_end + 2
          continue
        }
        None => ()
      }
    }
    let mut lo = tok
    if tok == char_backslash {
      i += 1
      if i >= plen {
        return glob_abort
      }
      lo = p[i]
    }
    // A range a-z; a `-` right before `]` is literal.
    if i + 2 < plen && p[i + 1] == char_dash && p[i + 2] != char_close_bracket {
      let mut hi = p[i + 2]
      i += 3
      if hi == char_backslash {
        if i >= plen {
          return glob_abort
        }
        hi = p[i]
        i += 1
      }
      if lo <= c && c <= hi {
        matched = true
      }
    } else {
      if lo == c {
        matched = true
      }
      i += 1
    }
  }
  if matched != negated {
    i + 1
  } else {
    -1
  }
}

///|
/// Index of the `:` closing a `[:name:]` whose name starts at `start`.
fn glob_posix_class_end(p : FixedArray[UInt16], start : Int) -> Int? {
  let mut j = start
  while j + 1 < p.length() {
    if p[j] == char_colon && p[j + 1] == char_close_bracket {
      return Some(j)
    }
    if p[j] == char_close_bracket {
      return None
    }
    j += 1
  }
  None
}

///|
fn glob_posix_class_matches(
  p : FixedArray[UInt16],
  start : Int,
  end : Int,
  c : UInt16,
) -> Bool {
  let name = StringBuilder()
  for k in start..= 'A'.to_int() && code <= 'Z'.to_int()
  let is_lower = code >= 'a'.to_int() && code <= 'z'.to_int()
  let is_digit = code >= '0'.to_int() && code <= '9'.to_int()
  let is_print = code >= 0x20 && code < 0x7f
  match name.to_string() {
    "alnum" => is_upper || is_lower || is_digit
    "alpha" => is_upper || is_lower
    "blank" => code == ' '.to_int() || code == '\t'.to_int()
    "cntrl" => code < 0x20 || code == 0x7f
    "digit" => is_digit
    "graph" => is_print && code != ' '.to_int()
    "lower" => is_lower
    "print" => is_print
    "punct" =>
      is_print && code != ' '.to_int() && !(is_upper || is_lower || is_digit)
    "space" => code == ' '.to_int() || (code >= 0x09 && code <= 0x0d)
    "upper" => is_upper
    "xdigit" =>
      is_digit ||
      (code >= 'a'.to_int() && code <= 'f'.to_int()) ||
      (code >= 'A'.to_int() && code <= 'F'.to_int())
    _ => false
  }
}

///|
let char_backslash : UInt16 = {
  let c : Int = '\\'.to_int()
  c.to_uint16()
}

///|
let char_close_bracket : UInt16 = {
  let c : Int = ']'.to_int()
  c.to_uint16()
}

///|
let char_bang : UInt16 = {
  let c : Int = '!'.to_int()
  c.to_uint16()
}

///|
let char_caret : UInt16 = {
  let c : Int = '^'.to_int()
  c.to_uint16()
}

///|
let char_colon : UInt16 = {
  let c : Int = ':'.to_int()
  c.to_uint16()
}

///|
let char_dash : UInt16 = {
  let c : Int = '-'.to_int()
  c.to_uint16()
}

///|
fn rule_applies(rule : Rule, path : String, is_dir : Bool) -> Bool {
  // Inline relative_to_base check to avoid Option allocation
  let blen = rule.base_len
  let plen = path.length()
  let rel_start : Int = if blen == 0 {
    0
  } else {
    if plen < blen {
      return false
    }
    // Check base prefix
    for i in 0.. Bool {
  // For dir rules, try matching against each directory prefix.
  // e.g., for "node_modules/express/lib/index.js", try "node_modules", "node_modules/express", etc.
  let mut seg_end = start
  while seg_end < end {
    if path.unsafe_get(seg_end) == char_slash {
      // Found a segment boundary — try matching path[start..seg_end]
      if match_rule_path_range(rule, path, start, seg_end) {
        return true
      }
    }
    seg_end += 1
  }
  // Try full path if it's a directory
  if is_dir {
    match_rule_path_range(rule, path, start, end)
  } else {
    false
  }
}

///|
/// Match a rule against a path range (without allocating substrings).
fn match_rule_path_range(
  rule : Rule,
  path : String,
  start : Int,
  end : Int,
) -> Bool {
  if rule.has_slash || rule.anchored {
    // Path-based matching: match segments against precompiled pattern segments
    match_segments_range(rule.pattern_segments, 0, path, start, end)
  } else {
    // Basename matching: check each segment against the precompiled pattern
    let mut seg_start = start
    while seg_start < end {
      let mut seg_end = seg_start
      while seg_end < end && path.unsafe_get(seg_end) != char_slash {
        seg_end += 1
      }
      if seg_end > seg_start &&
        match_glob_precompiled_range(
          rule.pattern_chars,
          path,
          seg_start,
          seg_end,
        ) {
        return true
      }
      seg_start = seg_end + 1
    }
    false
  }
}

///|
/// Match precompiled pattern segments against path segments in-place.
fn match_segments_range(
  pats : Array[FixedArray[UInt16]],
  pi : Int,
  path : String,
  start : Int,
  end : Int,
) -> Bool {
  if pi >= pats.length() {
    return start >= end
  }
  let pat = pats[pi]
  if is_double_star(pat) {
    // ** matches zero or more path segments
    // Try matching remaining patterns starting from each segment position
    let mut pos = start
    // Try matching with zero segments consumed by **
    if match_segments_range(pats, pi + 1, path, pos, end) {
      return true
    }
    while pos < end {
      // Advance to next segment
      while pos < end && path.unsafe_get(pos) != char_slash {
        pos += 1
      }
      if pos < end {
        pos += 1 // skip the slash
      }
      if match_segments_range(pats, pi + 1, path, pos, end) {
        return true
      }
    }
    false
  } else {
    // Find current segment boundaries
    if start >= end {
      return false
    }
    let mut seg_end = start
    while seg_end < end && path.unsafe_get(seg_end) != char_slash {
      seg_end += 1
    }
    if match_glob_precompiled_range(pat, path, start, seg_end) {
      let next_start = if seg_end < end { seg_end + 1 } else { end }
      match_segments_range(pats, pi + 1, path, next_start, end)
    } else {
      false
    }
  }
}

///|
fn is_double_star(p : FixedArray[UInt16]) -> Bool {
  p.length() == 2 && p[0] == char_star && p[1] == char_star
}

///|
fn trim_trailing_whitespace(s : String) -> String {
  let mut end = s.length()
  while end > 0 {
    let c = s.unsafe_get(end - 1)
    // A backslash keeps the whitespace after it ("foo\ " matches "foo ").
    if (c == ' ' || c == '\t') &&
      !(end >= 2 && s.unsafe_get(end - 2) == char_backslash) {
      end -= 1
    } else {
      break
    }
  }
  if end == s.length() {
    s
  } else {
    String::unsafe_substring(s, start=0, end~)
  }
}