// Inline structure parsing

///|
/// Tokens for parsing inlines.
///
/// The list of tokens of a paragraph are the points to consider to
/// parse it into inlines. Tokens gradually become `Inline` tokens
/// containing parsed inlines. Between two tokens there is implicit
/// textual data. This data gradually becomes part of `Inline` tokens
/// or, at the end of of the parsing process, becomes `Text` inlines.
///
/// The token list also represents newlines explicitly, either via
/// the `Newline` token or via the `Inline` token since inlines may
/// start on a line and up on another one.
priv enum Token {
  AutolinkOrHtmlStart(TokenStart)
  Backticks(TokenBackticks)
  EmphasisMarks(TokenEmphasisMarks)
  Inline(TokenInline)
  LinkStart(TokenLinkStart)
  Newline(TokenNewline)
  RightBrack(TokenStart)
  StrikethroughMarks(TokenStrikethroughMarks)
  MathSpanMarks(TokenMathSpanMarks)
} derive(Debug)

///|
priv struct TokenStart {
  start : CharCodePos
} derive(Debug)

///|
priv struct TokenBackticks {
  start : CharCodePos
  count : Int32
  escaped : Bool
} derive(Debug)

///|
priv struct TokenEmphasisMarks {
  start : CharCodePos
  char : Char
  /// The number of marks left in the run.
  count : Int32
  /// The length of the delimiter run in the source (for the rule of 3).
  run_length : Int32
  may_open : Bool
  may_close : Bool
} derive(Debug)

///|
priv struct TokenInline {
  start : CharCodePos
  inline : Inline
  endline : LineSpan
  next : CharCodePos
} derive(Debug)

///|
priv struct TokenLinkStart {
  start : CharCodePos
  image : Bool
} derive(Debug)

///|
priv struct TokenNewline {
  /// Points at spaces or `\` on the broken line
  start : CharCodePos
  break_ty : InlineBreakType
  newline : LineSpan
} derive(Debug)

///|
priv struct TokenStrikethroughMarks {
  start : CharCodePos
  may_open : Bool
  may_close : Bool
} derive(Debug)

///|
priv struct TokenMathSpanMarks {
  start : CharCodePos
  count : Int32
  may_open : Bool
  may_close : Bool
} derive(Debug)

///|
fn Token::start(self : Token) -> CharCodePos {
  match self {
    AutolinkOrHtmlStart(t) => t.start
    Backticks(t) => t.start
    EmphasisMarks(t) => t.start
    Inline(t) => t.start
    LinkStart(t) => t.start
    Newline(t) => t.start
    RightBrack(t) => t.start
    StrikethroughMarks(t) => t.start
    MathSpanMarks(t) => t.start
  }
}

///|
fn CloserIndex::has_backticks(
  self : CloserIndex,
  count~ : Int32,
  after~ : Int32,
) -> Bool {
  self.exists(Backticks(count), after~)
}

///|
fn CloserIndex::has_right_brack(self : CloserIndex, after~ : Int32) -> Bool {
  self.exists(RightBrack, after~)
}

///|
fn CloserIndex::has_right_paren(self : CloserIndex, after~ : Int32) -> Bool {
  self.exists(RightParen, after~)
}

///|
fn CloserIndex::has_math_span(
  self : CloserIndex,
  count~ : Int32,
  after~ : Int32,
) -> Bool {
  self.exists(MathSpanMarks(count), after~)
}

///|
/// Used to make the text delimitation precise for nested inlines.
fn tokens_shorten_last_line(to_last~ : Int32, toks : Tokens) -> Unit {
  let last = to_last
  for i = toks.0.length() - 1; i >= 0; i = i - 1 {
    match toks.0[i] {
      Newline({ newline, .. } as nl) => {
        toks.0[i] = Newline({ ..nl, newline: { ..newline, last, }, })
        break
      }
      Inline({ endline, .. } as il) => {
        toks.0[i] = Inline({ ..il, endline: { ..endline, last, }, })
        break
      }
      _ => ()
    }
  }
}

///|
fn tokens_drop_stop_after_right_brack(rev_toks : RevTokens) -> Unit {
  for ;; {
    match rev_toks.pop() {
      None | Some(RightBrack(_)) => break
      Some(_) => continue
    }
  }
}

///|
fn tokens_pop_until(start~ : Int32, rev_toks : RevTokens) -> Unit {
  for ;; {
    guard rev_toks.pop() is Some(t) else { break }
    if t.start() < start {
      continue
    }
    rev_toks.push(t)
    break
  }
}

///|
fn tokens_next_line(rev_toks : RevTokens) -> LineSpan? {
  tokens_next_line_consumed(rev_toks, [])
}

///|
/// Drops the tokens of `rev_toks` up to and including the next newline,
/// pushes them on `consumed` and returns the newline's line. Leaves
/// `rev_toks` and `consumed` untouched if there is no newline.
fn tokens_next_line_consumed(
  rev_toks : RevTokens,
  consumed : Array[Token],
) -> LineSpan? {
  let len = consumed.length()
  while rev_toks.pop() is Some(t) {
    consumed.push(t)
    if t is Newline({ newline, .. }) {
      return Some(newline)
    }
  }
  while consumed.length() > len {
    rev_toks.push(consumed.unsafe_pop())
  }
  None
}

///|
/// Puts back on `rev_toks` the tokens `consumed` by
/// `tokens_next_line_consumed`.
fn tokens_restore(rev_toks : RevTokens, consumed : Array[Token]) -> Unit {
  while consumed.pop() is Some(t) {
    rev_toks.push(t)
  }
}

// Tokenization

///|
fn Token::newline(
  s : String,
  prev_line : LineSpan,
  newline : LineSpan,
) -> Token {
  // https://spec.commonmark.org/current/#softbreak
  // https://spec.commonmark.org/current/#hard-line-breaks
  let { first, last, .. } = prev_line
  let non_space = @cmark_base.rev_drop_spaces(s, first~, start=last)
  // A final `\` is a hard break unless it is escaped by another `\`
  let odd_bslashes = () => {
    let line = s.view(start_offset=first, end_offset=last + 1)
    line.rev_iter().take_while(c => c == '\\').count() % 2 == 1
  }
  let (start, break_ty) = if non_space == last && odd_bslashes() {
    (non_space, Hard)
  } else {
    let start = non_space + 1
    (start, if last - start + 1 >= 2 { Hard } else { Soft })
  }
  Newline({ start, break_ty, newline, })
}

///|
fn tokens_add_backtick(
  toks : Tokens,
  cidx : CloserIndex,
  s : String,
  line : LineSpan,
  prev_bslash~ : Bool,
  start~ : Int32,
) -> Int32 {
  let last = @cmark_base.run_of(char='`', s, last=line.last, start=start + 1)
  let count = last - start + 1
  toks.push(Backticks({ start, count, escaped: prev_bslash, }))
  cidx.add(Backticks(count), start)
  last + 1
}

///|
fn tokens_try_add_image_link_start(
  toks : Tokens,
  s : String,
  line : LineSpan,
  start~ : Int32,
) -> Int32 {
  let next = start + 1
  guard next <= line.last && s[next] == '[' else { next }
  toks.push(LinkStart({ start, image: true, }))
  next + 1
}

///|
fn tokens_try_add_emphasis(
  toks : Tokens,
  s : String,
  line : LineSpan,
  start~ : Int32,
) -> Int32 {
  let { first, last, .. } = line
  let char = s[start].unsafe_to_char()
  let run_last = @cmark_base.run_of(char~, last~, s, start=start + 1)
  let count = run_last - start + 1
  let prev_char = @char.prev_char(s, first~, before=start)
  let next_char = @char.next_char(s, last~, after=run_last)
  let is_prev_white = is_whitespace(prev_char)
  let is_prev_punct = is_unicode_punctuation(prev_char)
  let is_next_white = is_whitespace(next_char)
  let is_next_punct = is_unicode_punctuation(next_char)
  let is_left_flanking = !is_next_white &&
    (!is_next_punct || is_prev_white || is_prev_punct)
  let is_right_flanking = !is_prev_white &&
    (!is_prev_punct || is_next_white || is_next_punct)
  let next = run_last + 1
  guard is_left_flanking || is_right_flanking else { next }
  let may_open = (char == '*' && is_left_flanking) ||
    (char == '_' && is_left_flanking && (!is_right_flanking || is_prev_punct))
  let may_close = (char == '*' && is_right_flanking) ||
    (char == '_' && is_right_flanking && (!is_left_flanking || is_next_punct))
  guard may_open || may_close else { next }
  toks.push(
    EmphasisMarks({
      start,
      char,
      count,
      run_length: count,
      may_open,
      may_close,
    }),
  )
  next
}

///|
fn tokens_try_add_strikethrough_marks(
  toks : Tokens,
  s : String,
  line : LineSpan,
  start~ : Int32,
) -> Int32 {
  let { first, last, .. } = line
  let char = s[start].unsafe_to_char()
  let run_last = @cmark_base.run_of(char~, s, last~, start=start + 1)
  let count = run_last - start + 1
  let next = run_last + 1
  guard count == 2 else { next }
  let prev_char = @char.prev_char(s, first~, before=start)
  let next_char = @char.next_char(s, last~, after=run_last)
  let may_open = !@char.is_ascii_whitespace(next_char)
  let may_close = !@char.is_ascii_whitespace(prev_char)
  toks.push(StrikethroughMarks({ start, may_open, may_close, }))
  next
}

///|
fn tokens_try_add_math_span_marks(
  toks : Tokens,
  cidx : CloserIndex,
  s : String,
  line : LineSpan,
  start~ : Int32,
) -> Int32 {
  let { first, last, .. } = line
  let char = s[start].unsafe_to_char()
  let run_last = @cmark_base.run_of(char~, s, last~, start=start + 1)
  let count = run_last - start + 1
  let next = run_last + 1
  guard count <= 2 else { next }
  let mut may_open = true
  let mut may_close = true
  if count == 1 {
    let prev_char = @char.prev_char(s, first~, before=start)
    let next_char = @char.next_char(s, last~, after=run_last)
    may_open = !@char.is_ascii_whitespace(next_char)
    may_close = !@char.is_ascii_whitespace(prev_char)
  }
  guard may_open || may_close else { next }
  toks.push(MathSpanMarks({ start, count, may_open, may_close, }))
  if may_close {
    cidx.add(MathSpanMarks(count), start)
  }
  next
}

///|
fn tokenize(
  exts~ : Bool,
  s : String,
  lines : Array[LineSpan],
) -> (CloserIndex, Tokens, LineSpan, Bool) {
  guard lines is [line, .. lines] else { abort("expected at least one line") }
  let toks : Tokens = Deque([])
  let cidx = CloserIndex::new()
  let only_newlines = for lines = lines, line = line, prev_bslash = false, k = line.first, only_newlines = true {
    if k > line.last {
      match lines {
        [] => break only_newlines
        [newline, .. lines] => {
          let t = Token::newline(s, line, newline)
          toks.push(t)
          continue lines, newline, false, newline.first, only_newlines
        }
      }
    }
    let (next, only_newlines) = match s[k] {
      '\\' => continue lines, line, !prev_bslash, k + 1, only_newlines
      '`' =>
        (tokens_add_backtick(toks, cidx, s, line, prev_bslash~, start=k), false)
      _ if prev_bslash => (k + 1, only_newlines)
      '*' | '_' => {
        let before = toks.0.length()
        let next = tokens_try_add_emphasis(toks, s, line, start=k)
        (next, only_newlines && toks.0.length() == before)
      }
      ']' => {
        toks.push(RightBrack({ start: k, }))
        cidx.add(RightBrack, k)
        (k + 1, false)
      }
      '[' => {
        toks.push(LinkStart({ start: k, image: false, }))
        (k + 1, false)
      }
      '!' => {
        let next = tokens_try_add_image_link_start(toks, s, line, start=k)
        (next, only_newlines && next == k + 1)
      }
      '<' => {
        toks.push(AutolinkOrHtmlStart({ start: k, }))
        (k + 1, false)
      }
      ')' => {
        cidx.add(RightParen, k)
        (k + 1, only_newlines)
      }
      '~' if exts => {
        let before = toks.0.length()
        let next = tokens_try_add_strikethrough_marks(toks, s, line, start=k)
        (next, only_newlines && toks.0.length() == before)
      }
      '$' if exts => {
        let before = toks.0.length()
        let next = tokens_try_add_math_span_marks(toks, cidx, s, line, start=k)
        (next, only_newlines && toks.0.length() == before)
      }
      _ => (k + 1, only_newlines)
    }
    continue lines, line, false, next, only_newlines
  }
  (cidx, toks, line, only_newlines)
}

// Making inlines and inline tokens

///|
fn Parser::break_inline(
  self : Parser,
  line : LineSpan,
  start~ : Int32,
  break_ty~ : InlineBreakType,
  newline~ : LineSpan,
) -> Inline {
  let layout_before = { ..line, first: start, }
  let layout_after = {
    let non_blank = self.first_non_blank_in_span(newline)
    { ..newline, last: non_blank - 1, }
  }
  let m = self.meta_of_spans(first=layout_before, last=layout_after)
  let layout_before = self.layout_clean_raw_span(layout_before)
  let layout_after = self.layout_clean_raw_span(layout_after)
  Break({ v: { ty: break_ty, layout_before, layout_after, }, meta: m, })
}

///|
fn Parser::try_add_text_inline(
  self : Parser,
  line : LineSpan,
  first~ : Int32,
  last~ : Int32,
  acc : Array[Inline],
  strip~ : Bool = true,
) -> Unit {
  if first > last {
    return
  }
  let mut first = first
  if strip && first == line.first {
    first = self.first_non_blank_in_span(line) // Strip leading blanks
  }
  acc.push(Text(self.clean_unesc_unref_span({ ..line, first, last, })))
}

///|
fn Parser::inlines_inline(
  self : Parser,
  first~ : CharCodePos,
  last~ : CharCodePos,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  acc : Array[Inline],
) -> Inline {
  match acc {
    [i] => i
    is_ => {
      let text_loc = self.text_loc_of_lines(
        first~,
        last~,
        first_line~,
        last_line~,
      )
      Inlines({ v: is_, meta: self.meta(text_loc), })
    }
  }
}

///|
fn Parser::code_span_token(
  self : Parser,
  count~ : Int32,
  first~ : CharCodePos,
  last~ : CharCodePos,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  spans : ArrayView[Span],
) -> Token {
  let text_loc = self.text_loc_of_lines(first~, last~, first_line~, last_line~)
  let code_layout = self.raw_tight_block_lines(spans~)
  let meta = self.meta(text_loc)
  let cs = CodeSpan({ v: { backticks: count, code_layout, }, meta, })
  Inline({ start: first, inline: cs, endline: last_line, next: last + 1, })
}

///|
fn Parser::autolink_token(
  self : Parser,
  line : LineSpan,
  first~ : Int32,
  last~ : Int32,
  is_email~ : Bool,
) -> Token {
  let meta = self.meta(self.text_loc_of_span({ ..line, first, last, }))
  let link = { ..line, first: first + 1, last: last - 1, }
  let link = self.clean_unref_span(link)
  let inline = Autolink({ v: { link, is_email, }, meta, })
  Inline({ start: first, inline, endline: line, next: last + 1, })
}

///|
fn Parser::raw_html_token(
  self : Parser,
  first~ : Int32,
  last~ : Int32,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  spans : ArrayView[Span],
) -> Token {
  let _ = first_line
  let raw = Seq::from_array(self.raw_tight_block_lines(spans~))
  let text_loc = {
    let first = raw[0].node.meta.loc
    let { last: last_ccode, pos: last_line, .. } = spans[spans.length() - 1].span
    { ..first, last_ccode, last_line, }
  }
  let inline = RawHtml({ v: raw, meta: self.meta(text_loc), })
  Inline({ start: first, inline, endline: last_line, next: last + 1, })
}

///|
fn Parser::link_token(
  self : Parser,
  first~ : Int32,
  last~ : Int32,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  image~ : Bool,
  link : InlineLink,
) -> Token {
  let text_loc = self.text_loc_of_lines(first~, last~, first_line~, last_line~)
  let link = { v: link, meta: self.meta(text_loc), }
  let inline : Inline = if image { Image(link) } else { Link(link) }
  Inline({ start: first, inline, endline: last_line, next: last + 1, })
}

///|
fn Parser::emphasis_token(
  self : Parser,
  first~ : Int32,
  last~ : Int32,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  strong~ : Bool,
  emph : Inline,
) -> Token {
  let text_loc = self.text_loc_of_lines(first~, last~, first_line~, last_line~)
  let delim = self.i[first].unsafe_to_char()
  let emph = { v: { delim, inline: emph, }, meta: self.meta(text_loc), }
  let inline = if strong { StrongEmphasis(emph) } else { Emphasis(emph) }
  Inline({ start: first, inline, endline: last_line, next: last + 1, })
}

///|
fn Parser::ext_strikethough_token(
  self : Parser,
  first~ : Int32,
  last~ : Int32,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  s : Inline,
) -> Token {
  let text_loc = self.text_loc_of_lines(first~, last~, first_line~, last_line~)
  let inline = ExtStrikethrough({ v: s, meta: self.meta(text_loc), })
  Inline({ start: first, inline, endline: last_line, next: last + 1, })
}

///|
fn Parser::ext_math_span_token(
  self : Parser,
  count~ : Int32,
  first~ : Int32,
  last~ : Int32,
  first_line~ : LineSpan,
  last_line~ : LineSpan,
  spans : ArrayView[Span],
) -> Token {
  let textloc = self.text_loc_of_lines(first~, last~, first_line~, last_line~)
  let tex_layout = self.raw_tight_block_lines(spans~)
  let meta = self.meta(textloc)
  let ms = { display: count == 2, tex_layout, }
  let inline = ExtMathSpan({ v: ms, meta, })
  Inline({ start: first, inline, endline: last_line, next: last + 1, })
}

// Parsers

///|
/// https://spec.commonmark.org/current/#code-span
/// Tries to push an inline code span to the `rev_toks` stack.
/// If this function returns `Some((line_span, token))`, it means the stack has been modified.
fn Parser::try_code(
  self : Parser,
  rev_toks : Ref[RevTokens],
  start_line : LineSpan,
  start~ : CharCodePos,
  count~ : Int32,
  escaped~ : Bool,
) -> (LineSpan, Token)? {
  // If the run is preceded by a `\`, its first backtick is escaped: the
  // backtick string that opens starts after it.
  let (cstart, count) = if escaped {
    (start + 1, count - 1)
  } else {
    (start, count)
  }
  guard count > 0 && self.cidx.has_backticks(count~, after=cstart) else { None }
  let first = cstart + count
  let mut line = { ..start_line, first, }
  let spans = []
  let mut k = first
  let old_rev_toks = rev_toks.val.0.copy()
  for ;; {
    match rev_toks.val.pop() {
      None => break
      Some(Backticks({ start, count: c, .. })) => {
        guard c == count else { continue }
        let span : Span = {
          start: line.first,
          span: { ..line, first: k, last: start - 1, },
        }
        spans.push(span)
        let t = self.code_span_token(
          count~,
          first=cstart,
          last=start + count - 1,
          first_line=start_line,
          last_line=line,
          spans[:],
        )
        return Some((line, t))
      }
      Some(Newline({ newline, .. })) => {
        let span : Span = { start: line.first, span: { ..line, first: k, }, }
        spans.push(span)
        k = self.first_non_blank_in_span(newline)
        line = newline
      }
      Some(_) => continue
    }
  }
  rev_toks.val = old_rev_toks
  None
}

///|
/// Tries to push an inline math span to the `rev_toks` stack.
/// If this function returns `Some((line_span, token))`, it means the stack has been modified.
fn Parser::try_math_span(
  self : Parser,
  rev_toks : Ref[RevTokens],
  start_line : LineSpan,
  start~ : CharCodePos,
  count~ : Int32,
) -> (LineSpan, Token)? {
  let cstart = start
  guard self.cidx.has_math_span(count~, after=cstart) else { None }
  let old_rev_toks = rev_toks.val.0.copy()
  let first = cstart + count
  let mut line = { ..start_line, first, }
  let spans = []
  let mut k = first
  for ;; {
    match rev_toks.val.pop() {
      None => break
      Some(MathSpanMarks({ start, count: c, may_close, .. })) => {
        guard c == count && may_close else { continue }
        let span : Span = {
          start: line.first,
          span: { ..line, first: k, last: start - 1, },
        }
        spans.push(span)
        let t = self.ext_math_span_token(
          count~,
          first=cstart,
          last=start + count - 1,
          first_line=start_line,
          last_line=line,
          spans[:],
        )
        return Some((line, t))
      }
      Some(Newline({ newline, .. })) => {
        let span : Span = { start: line.first, span: { ..line, first: k, }, }
        spans.push(span)
        k = self.first_non_blank_in_span(newline)
        line = newline
      }
      Some(_) => continue
    }
  }
  rev_toks.val = old_rev_toks
  None
}

///|
/// For the kinds of raw HTML that end with a specific string (see
/// `raw_html_end_kind`), the first position in a token stream from which
/// they were found not to end. Later ones cannot end either: this keeps
/// unterminated constructs from making parsing quadratic.
priv struct RawHtmlNoEnd(FixedArray[Int32])

///|
fn RawHtmlNoEnd::new() -> RawHtmlNoEnd {
  RawHtmlNoEnd(FixedArray::make(4, @int.MAX_VALUE))
}

///|
/// The kind of raw HTML starting at `start` if it ends with a specific
/// string: 0 for processing instructions (`?>`), 1 for CDATA sections
/// (`]]>`), 2 for declarations (`>`) and 3 for comments (`-->`).
fn raw_html_end_kind(s : String, start~ : CharCodePos) -> Int32? {
  match s.view(start_offset=start) {
    [.. " Some(0)
    [.. " Some(1)
    [.. " Some(2)
    [.. "