///|
/// One finite linear path through a TokenGraph.
///
/// Tokens are normalized to path-local positions. A graph edge that spans
/// multiple input positions becomes one token position in the finite string,
/// while genuine gaps between graph nodes remain gaps.
pub struct TokenGraphPath {
  tokens : ReadOnlyArray[Token]
}

///|
pub fn TokenGraphPath::tokens(self : TokenGraphPath) -> ReadOnlyArray[Token] {
  self.tokens
}

///|
pub fn TokenGraphPath::length(self : TokenGraphPath) -> Int {
  self.tokens.length()
}

///|
/// Immutable snapshot of a token stream interpreted as a directed acyclic
/// graph. Every token is an edge from `position` to
/// `position + position_length`.
pub struct TokenGraph {
  tokens : ReadOnlyArray[Token]
  start_position : Int
  end_position : Int
}

///|
/// Validates and snapshots analyzed tokens as a TokenGraph.
///
/// Input order must be non-decreasing by position. Position lengths must be
/// positive, and UTF-8 byte offsets must describe non-negative source spans.
pub fn TokenGraph::from_tokens(
  tokens : Array[Token],
) -> TokenGraph raise AnalysisError {
  let frozen : Array[Token] = []
  let mut previous_position = -1
  let mut start_position = 0
  let mut end_position = 0
  for index in 0..= 0 else {
      raise AnalysisError::InvalidTokenGraph(
        "token position must be non-negative",
      )
    }
    guard token.position >= previous_position else {
      raise AnalysisError::InvalidTokenGraph(
        "token positions must be non-decreasing",
      )
    }
    guard token.position_length > 0 else {
      raise AnalysisError::InvalidTokenGraph(
        "token position_length must be positive",
      )
    }
    guard token.start_offset >= 0 && token.end_offset >= token.start_offset else {
      raise AnalysisError::InvalidTokenGraph("token offsets are invalid")
    }
    let token_end = token.position + token.position_length
    guard token_end > token.position else {
      raise AnalysisError::InvalidTokenGraph("token end position overflowed")
    }
    if index == 0 {
      start_position = token.position
    }
    if token_end > end_position {
      end_position = token_end
    }
    frozen.push(token)
    previous_position = token.position
  }
  { tokens: ReadOnlyArray::from_array(frozen), start_position, end_position }
}

///|
pub fn TokenGraph::tokens(self : TokenGraph) -> ReadOnlyArray[Token] {
  self.tokens
}

///|
pub fn TokenGraph::start_position(self : TokenGraph) -> Int {
  self.start_position
}

///|
pub fn TokenGraph::end_position(self : TokenGraph) -> Int {
  self.end_position
}

///|
fn clone_path_tokens(tokens : Array[Token]) -> Array[Token] {
  let cloned : Array[Token] = []
  for token in tokens {
    cloned.push(token)
  }
  cloned
}

///|
fn emit_token_graph_path(
  paths : Array[TokenGraphPath],
  tokens : Array[Token],
  max_paths : Int,
) -> Unit raise AnalysisError {
  guard paths.length() < max_paths else {
    raise AnalysisError::TokenGraphTooComplex(max_paths)
  }
  paths.push({ tokens: ReadOnlyArray::from_array(clone_path_tokens(tokens)) })
}

///|
fn enumerate_token_graph_paths(
  graph : TokenGraph,
  graph_position : Int,
  output_position : Int,
  current : Array[Token],
  paths : Array[TokenGraphPath],
  max_paths : Int,
) -> Unit raise AnalysisError {
  if graph_position >= graph.end_position {
    emit_token_graph_path(paths, current, max_paths)
    return
  }
  let edges : Array[Token] = []
  let mut next_start = -1
  for token in graph.tokens {
    if token.position == graph_position {
      edges.push(token)
    } else if token.position > graph_position && next_start < 0 {
      next_start = token.position
    }
  }
  if edges.length() == 0 {
    if next_start >= 0 {
      enumerate_token_graph_paths(
        graph,
        next_start,
        output_position + next_start - graph_position,
        current,
        paths,
        max_paths,
      )
    }
    return
  }
  for edge in edges {
    let next_path = clone_path_tokens(current)
    next_path.push({
      text: edge.text,
      position: output_position,
      position_length: 1,
      start_offset: edge.start_offset,
      end_offset: edge.end_offset,
    })
    enumerate_token_graph_paths(
      graph,
      edge.position + edge.position_length,
      output_position + 1,
      next_path,
      paths,
      max_paths,
    )
  }
}

///|
/// Enumerates all finite strings with an explicit expansion limit.
pub fn TokenGraph::finite_strings_with_limit(
  self : TokenGraph,
  max_paths : Int,
) -> Array[TokenGraphPath] raise AnalysisError {
  guard max_paths > 0 else {
    raise AnalysisError::InvalidTokenGraph("max_paths must be positive")
  }
  let paths : Array[TokenGraphPath] = []
  if self.tokens.length() == 0 {
    return paths
  }
  enumerate_token_graph_paths(
    self,
    self.start_position,
    0,
    [],
    paths,
    max_paths,
  )
  paths
}

///|
/// Enumerates at most 256 finite strings, protecting query construction from
/// accidental exponential graph expansion.
pub fn TokenGraph::finite_strings(
  self : TokenGraph,
) -> Array[TokenGraphPath] raise AnalysisError {
  self.finite_strings_with_limit(256)
}