///|
struct CompiledRule {
  source : @rules.RuleSource
  words : Array[StringView]
  anchor : Int32
}

///|
priv struct Match {
  expression : String
  kind : String
  rule_id : String
  start_line : Int32
  end_line : Int32
  start_word : Int32
  end_word : Int32
}

///|
/// Reuse a scanner for repeated local scans without recompiling the corpus.
pub struct Scanner {
  priv rules : Array[CompiledRule]
  priv index : Map[StringView, Map[StringView, Array[Int32]]]
}

///|
pub fn Scanner::new() -> Scanner {
  let rules = []
  let index : Map[StringView, Map[StringView, Array[Int32]]] = Map([])
  for n, source in @rules.corpus() {
    let sequence = words(source.pattern).map(word => word.value)
    let anchor = source.anchor
    let first = sequence[anchor]
    let second = sequence[anchor + 1]
    let tails = match index.get(first) {
      Some(tails) => tails
      None => {
        let tails = Map([])
        index[first] = tails
        tails
      }
    }
    match tails.get(second) {
      Some(ids) => ids.push(n)
      None => tails[second] = [n]
    }
    rules.push({ source, words: sequence, anchor, })
  }
  { rules, index, }
}

///|
fn matches_at(rule : CompiledRule, input : Array[Word], start : Int32) -> Bool {
  for i in 0.. (Array[Match], Bool) {
  let positions : Array[Array[Int32]?] = Array::make(self.rules.length(), None)
  for i in 0..<(input.length() - 1) {
    guard self.index.get(input[i].value) is Some(tails) &&
      tails.get(input[i + 1].value) is Some(ids) else {
      continue
    }
    for id in ids {
      if positions[id] is Some(starts) && starts.length() > 256 {
        continue
      }
      let rule = self.rules[id]
      let start = i - rule.anchor
      if start >= 0 &&
        start + rule.words.length() <= input.length() &&
        matches_at(rule, input, start) {
        match positions[id] {
          Some(starts) => starts.push(start)
          None => positions[id] = Some([start])
        }
      }
    }
  }
  // Apply the evidence cap in corpus order, independent of index discovery order.
  let out : Array[Match] = []
  for id, rule in self.rules {
    guard positions[id] is Some(starts) else { continue }
    for start in starts {
      if out.length() >= 256 {
        return (out, false)
      }
      let end = start + rule.words.length() - 1
      out.push({
        expression: rule.source.expression,
        kind: rule.source.kind,
        rule_id: rule.source.id,
        start_line: input[start].line,
        end_line: input[end].line,
        start_word: start,
        end_word: end,
      })
    }
  }
  (out, true)
}

///|
// GNU license appendices show a grant with an unfilled copyright holder.
// Ignore only the adjacent grant; a later real grant in the same file remains evidence.
fn suppress_gnu_examples(text : String, candidates : Array[Match]) -> Array[Match] {
  fn gnu_grant(hit : Match) -> Bool {
    hit.kind == "fragment" && (
      hit.expression.has_prefix("GPL-") || hit.expression.has_prefix("LGPL-") ||
      hit.expression.has_prefix("AGPL-")
    )
  }
  if !text.contains("") || !candidates.any(gnu_grant) {
    return candidates
  }
  let template_lines : Set[Int32] = Set([])
  each_line(text, (line, raw) => {
    if raw.contains("") &&
      (raw.contains("") || raw.contains("")) {
      template_lines.add(line)
    }
  })
  candidates.filter(hit => {
    if gnu_grant(hit) {
      for offset in 1..<=4 {
        if template_lines.contains(hit.start_line - offset) {
          return false
        }
      }
    }
    true
  })
}

///|
fn consolidate(candidates : Array[Match]) -> (Array[Match], Bool) {
  candidates.sort_by((a, b) => {
    if a.start_word != b.start_word {
      a.start_word - b.start_word
    } else if a.end_word != b.end_word {
      b.end_word - a.end_word
    } else {
      a.rule_id.compare(b.rule_id)
    }
  })
  let out : Array[Match] = []
  let mut ambiguous = false
  for item in candidates {
    let mut redundant = false
    for kept in out {
      if item.start_word > kept.end_word || item.end_word < kept.start_word {
        continue
      }
      if item.expression == kept.expression {
        redundant = true
        break
      }
      if item.start_word >= kept.start_word &&
        item.end_word <= kept.end_word &&
        (
          item.kind == "ambiguous" ||
          (kept.kind == "text" && item.kind == "fragment")
        ) {
        redundant = true
        break
      }
      if item.start_word == kept.start_word && item.end_word == kept.end_word {
        ambiguous = true
      }
    }
    if !redundant {
      if item.kind == "ambiguous" {
        ambiguous = true
      } else {
        out.push(item)
      }
    }
  }
  (out, ambiguous)
}

///|
fn project_license(path : String) -> Bool {
  if path.contains("/") {
    return false
  }
  let name = path.to_lower()
  for exact in ["license", "licence", "copying"] {
    if name == exact ||
      name.has_prefix(exact + ".") ||
      name.has_prefix(exact + "-") {
      return true
    }
  }
  false
}

///|
fn Scanner::find(
  self : Scanner,
  path : String,
  text : String,
  maximum : Int32,
) -> (Array[Finding], Array[String], Bool) {
  let input = words(text)
  let (found, body_complete) = self.body_matches(input)
  let (matched, ambiguous) = consolidate(suppress_gnu_examples(text, found))
  let (explicit, review, explicit_complete) = spdx_labels(text)
  if ambiguous {
    review.push("ambiguous_rule_match")
  }
  let result : Array[Finding] = []
  let line_fingerprints : Map[(String, String, String), Int32] = Map([])
  let file_scope = if project_license(path) { "project" } else { "file" }
  fn add(hit : Match, fingerprint : String) -> Unit {
    if result.length() >= maximum {
      return
    }
    let key = (hit.kind, hit.expression, fingerprint)
    let n = line_fingerprints.get(key).unwrap_or(0)
    line_fingerprints[key] = n + 1
    let id = hash_text(
      Json((path, hit.kind, hit.expression, fingerprint, n)).stringify(),
    )
    result.push({
      id,
      expression: hit.expression,
      kind: hit.kind,
      scope: file_scope,
      rule_id: hit.rule_id,
      start_line: hit.start_line,
      end_line: hit.end_line,
      evidence_sha256: fingerprint,
    })
  }
  for hit in explicit {
    add(hit, hash_text(hit.expression))
  }
  for hit in matched {
    let content = StringBuilder()
    for i in hit.start_word..<=hit.end_word {
      if i != hit.start_word {
        content.write_char(' ')
      }
      content.write_stringview(input[i].value)
    }
    add(hit, hash_text(content.to_string()))
  }
  if result.is_empty() &&
    file_scope == "project" &&
    body_complete &&
    explicit_complete {
    review.push("unrecognized_project_license")
  }
  let mut first_expression = ""
  for hit in result {
    if first_expression == "" {
      first_expression = hit.expression
    }
    if first_expression != hit.expression {
      review.push("multiple_license_indications")
      break
    }
  }
  result.sort_by((a, b) => {
    if a.start_line != b.start_line {
      a.start_line - b.start_line
    } else if a.end_line != b.end_line {
      a.end_line - b.end_line
    } else {
      a.id.compare(b.id)
    }
  })
  (
    result,
    review,
    body_complete &&
    explicit_complete &&
    matched.length() + explicit.length() <= maximum,
  )
}