import {ContextTracker, ExternalTokenizer, InputStream, Stack} from "@lezer/lr"
import {
  If,
  Then,
  Elif,
  Else,
  Fi,
  For,
  While,
  Until,
  Do,
  Done,
  Case,
  Esac,
  In,
  Function,
  Select,
  Time,
  Always,
  GroupOpen,
  GroupClose,
  CondOpen,
  CondOp,
  CondMatchOp,
  CondRegexOp,
  CondClose,
  NotOp,
  AssignName,
  ArrayAssignName,
  CompoundAssignName,
  Regex,
  Terminator,
  insertedTerminator,
  blankLine,
  HeredocBody,
  Comment,
  wordEnd,
  noSpace,
  LineContinuation,
  GlobQualifier,
  SubscriptOpen,
  ArithOpen
} from "./parser.terms.js"

const space = 32,
  tab = 9,
  carriage = 13,
  lineFeed = 10,
  hash = 35,
  semi = 59,
  amp = 38,
  pipe = 124,
  lt = 60,
  gt = 62,
  parenL = 40,
  parenR = 41,
  braceL = 123,
  braceR = 125,
  bracketL = 91,
  bracketR = 93,
  bang = 33,
  dash = 45,
  plus = 43,
  eq = 61,
  dollar = 36,
  quote = 34,
  apostrophe = 39,
  backtick = 96,
  backslash = 92,
  dot = 46

function isBlank(ch: number) {
  return ch == space || ch == tab || ch == carriage
}

// The characters that end a word. Everything else, `#` and `=` and `[` and `}`
// included, is an ordinary letter in the middle of one.
function endsWord(ch: number) {
  return (
    ch < 0 ||
    isBlank(ch) ||
    ch == lineFeed ||
    ch == semi ||
    ch == amp ||
    ch == pipe ||
    ch == parenL ||
    ch == parenR ||
    ch == lt ||
    ch == gt
  )
}

function isLower(ch: number) {
  return ch >= 97 && ch <= 122
}

function isNameStart(ch: number) {
  return (ch >= 65 && ch <= 90) || (ch >= 97 && ch <= 122) || ch == 95
}

function isNameChar(ch: number) {
  return isNameStart(ch) || (ch >= 48 && ch <= 57)
}

// ksh gives a variable named fields and writes them with a dot, as in
// `point.x=1`. No other shell has them, and no other shell has anything else
// that a dot in a name could be.
function isFieldChar(ch: number) {
  return isNameChar(ch) || ch == dot
}

// ── Words ─────────────────────────────────────────────────────────────────────

// The pieces of a word are parsed with nothing skipped between them, which
// leaves the grammar unable to see where the word stops. This token has no
// width and says exactly that: the shell would end the word here.
export const words = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  // A backslash before a newline joins the two lines. Between words the
  // grammar skips it as space, but inside one it is a piece of the word:
  // `echo ab\` and `cd` on the next line pass one argument. What tells the two
  // apart is whether it touches the word, as with `noSpace` below, and a
  // skipped token cannot also be shifted, so it is produced here.
  if (
    input.next == backslash &&
    input.peek(1) == lineFeed &&
    !isBlank(input.peek(-1)) &&
    stack.canShift(LineContinuation)
  ) {
    input.acceptToken(LineContinuation, 2)
    return
  }
  // zsh narrows a glob with a parenthesis after it: `*.txt(D)` matches the
  // hidden files too, `*(.)` only the plain ones. A parenthesis ends a word
  // everywhere else, so this has to be asked before `wordEnd` is, and it is
  // only asked at all where a word is already under way.
  if (input.next == parenL && stack.canShift(GlobQualifier)) {
    const length = globQualifierLength(input)
    if (length) {
      input.acceptToken(GlobQualifier, length)
      return
    }
  }
  // zsh reaches into an array without braces round it, `$path[1]`. A bracket
  // opens a glob everywhere else in a word, so this is only asked where the
  // parser has just read a `$name` and nothing else could follow it.
  if (input.next == bracketL && stack.canShift(SubscriptOpen)) {
    input.acceptToken(SubscriptOpen, 1)
    return
  }
  if (endsWord(input.next) && stack.canShift(wordEnd)) {
    input.acceptToken(wordEnd)
    return
  }
  // The other half of the same question, and the only place a word has to
  // begin where one has just ended. `x=1` assigns a value and `x= 1` runs a
  // command called `1` with `x` set to nothing, so the value of an assignment
  // has to touch the `=` that introduced it, and `arr=(a b)` has to touch its
  // parenthesis or it is a subshell.
  const before = input.peek(-1)
  if (isBlank(before) || before == lineFeed || before < 0) return
  if (startsValue(input.next) && stack.canShift(noSpace)) input.acceptToken(noSpace)
}, {contextual: true})

function startsValue(ch: number) {
  return ch >= 0 && !endsWord(ch) || ch == parenL
}

// How long the qualifier is, or nothing if what follows the word is a
// parenthesis doing something else. Qualifiers are letters and a handful of
// punctuation; a space or a quote inside means this is a subshell, an extended
// pattern, or the parenthesis of a function definition.
function globQualifierLength(input: InputStream) {
  for (let at = 1; at < 64; at++) {
    const ch = input.peek(at)
    if (ch == parenR) return at > 1 ? at + 1 : 0
    if (!isQualifierChar(ch)) return 0
  }
  return 0
}

// A qualifier is letters and a little punctuation. The `#` is the flag form,
// `(#qN)` rather than `(N)`, which is what a pattern has to write when the
// option that allows the short one is off.
function isQualifierChar(ch: number) {
  return (
    isNameChar(ch) ||
    ch == dot ||
    ch == hash ||
    ch == dash ||
    ch == plus ||
    ch == 42 /* * */ ||
    ch == 44 /* , */ ||
    ch == 47 /* / */ ||
    ch == 58 /* : */ ||
    ch == 64 /* @ */ ||
    ch == 94 /* ^ */ ||
    ch == bracketL ||
    ch == bracketR
  )
}

// ── Arithmetic commands ───────────────────────────────────────────────────────

// `(( i++ ))` evaluates and `( (a) && b )` is a subshell holding a group. Three
// parens in a row are the one place the two readings collide, and which is
// meant is settled by how the whole thing closes: arithmetic ends in `))` and
// a subshell ends in a single `)`.
//
//   ((( n % 15 == 0 )) && echo)   a subshell holding an arithmetic command
//   (((x += 2) <= 8))             arithmetic holding a parenthesised sum
//
// The shell decides this by parsing the arithmetic and taking the other
// reading when that fails, which is a thing a parser with no backtracking
// cannot do. Counting the parens gets the same answer.
export const arithCommands = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  if (input.next != parenL || input.peek(1) != parenL) return
  if (!stack.canShift(ArithOpen)) return
  if (input.peek(2) == parenL && !closesTwice(input)) return
  input.advance(2)
  input.acceptToken(ArithOpen)
}, {contextual: true})

// How far ahead the paren count will look. Past that the answer is no, which
// is the reading that costs less when it is wrong: a subshell holds commands,
// and a command is nearly anything.
const parenScanLimit = 2048

function closesTwice(input: InputStream) {
  let depth = 0
  for (let at = 0; at < parenScanLimit; at++) {
    const ch = input.peek(at)
    if (ch < 0) return false
    if (ch == backslash) at++
    else if (ch == apostrophe || ch == quote) at = skipQuoted(input, at, parenScanLimit, ch) - 1
    else if (ch == parenL) depth++
    else if (ch == parenR && --depth == 0) return input.peek(at - 1) == parenR
  }
  return false
}

// ── Reserved words ────────────────────────────────────────────────────────────

// Longest first, so `=~` is not read as the `=` inside it.
const condOperators: Array<[string, number]> = [
  ["=~", CondRegexOp],
  ["==", CondMatchOp],
  ["!=", CondMatchOp],
  ["=", CondMatchOp],
  ["<", CondOp],
  [">", CondOp],
  ["-", CondOp]
]

const keywords: {[name: string]: number} = {
  if: If,
  then: Then,
  elif: Elif,
  else: Else,
  fi: Fi,
  for: For,
  while: While,
  until: Until,
  do: Do,
  done: Done,
  case: Case,
  esac: Esac,
  in: In,
  function: Function,
  select: Select,
  time: Time,
  always: Always
}

// A reserved word is reserved where a command may start and nowhere else, which
// is why `while true; do echo done; done` prints the word and then ends the
// loop. A command cannot start until the one before it is terminated, so the
// question "is this a keyword" is the question "has the parser room for one",
// and the parser is the one that knows.
//
// `{`, `}`, `[[`, `]]` and `!` are reserved words too, and are here rather than
// in the grammar's own tokens because a word would otherwise swallow them:
// `echo }` prints a brace.
export const reservedWords = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  const ch = input.next
  // An operator inside `[[ ]]` has blanks around it, and the same characters
  // written against a word belong to the word: `[[ $line == *=* ]]` asks
  // whether a line holds an equals sign, and only the first of the three is an
  // operator.
  const before = input.peek(-1)
  if (isBlank(before) || before == lineFeed) {
    for (const [text, term] of condOperators) {
      let at = 0
      while (at < text.length && input.peek(at) == text.charCodeAt(at)) at++
      if (at < text.length) continue
      if (text == "-" && !(isLower(input.peek(1)) && isLower(input.peek(2)))) continue
      const length = text == "-" ? 3 : text.length
      if (!blankFollows(input, length) || !stack.canShift(term)) continue
      input.advance(length)
      input.acceptToken(term)
      return
    }
  }
  // A brace and a `!` open something only when a space follows. `{x,y}` is a
  // brace expansion and `!=` is a comparison, and neither is a reserved word.
  if (ch == braceL) return takeIf(input, stack, GroupOpen, 1, blankFollows(input, 1))
  if (ch == bang) return takeIf(input, stack, NotOp, 1, blankFollows(input, 1))
  if (ch == braceR) return takeIf(input, stack, GroupClose, 1, endsWord(input.peek(1)))
  if (ch == bracketL && input.peek(1) == bracketL)
    return takeIf(input, stack, CondOpen, 2, blankFollows(input, 2))
  if (ch == bracketR && input.peek(1) == bracketR)
    return takeIf(input, stack, CondClose, 2, endsWord(input.peek(2)))
  if (!isNameStart(ch)) return
  let length = 0,
    word = ""
  while (isNameChar(input.peek(length))) word += String.fromCharCode(input.peek(length++))
  const term = keywords[word]
  if (term == null) return
  takeIf(input, stack, term, length, endsWord(input.peek(length)))
}, {contextual: true})

function blankFollows(input: InputStream, at: number) {
  const ch = input.peek(at)
  return ch < 0 || isBlank(ch) || ch == lineFeed
}

function takeIf(input: InputStream, stack: Stack, term: number, length: number, ok: boolean) {
  if (!ok || !stack.canShift(term)) return
  input.advance(length)
  input.acceptToken(term)
}

// ── Assignments ───────────────────────────────────────────────────────────────

// `x=1` sets a variable and `echo x=1` prints it, and again the difference is
// position: a word assigns only before the command name has been read. The
// name and its `=` come out as one token so that what follows is an ordinary
// word, which is what `x=$(date)` needs it to be.
export const assignments = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  if (!isNameStart(input.next)) return
  let length = 0
  while (isFieldChar(input.peek(length))) length++
  // `arr[i]=1` and `arr[$k]=1` assign to one element, and ksh subscripts an
  // array of arrays with `grid[y][x]=1`.
  while (input.peek(length) == bracketL) {
    let depth = 1,
      at = length + 1
    while (depth > 0) {
      const ch = input.peek(at)
      if (ch < 0 || ch == lineFeed) return
      if (ch == bracketL) depth++
      else if (ch == bracketR) depth--
      at++
    }
    length = at
  }
  if (input.peek(length) == plus && input.peek(length + 1) == eq) length += 2
  else if (input.peek(length) == eq) length += 1
  else return
  // ksh's `typeset -T Point_t=( ... )` names a type, and what the parentheses
  // hold is commands rather than words: field declarations and the functions
  // that are the type's methods. Which of the two this is can be read off the
  // body, because a `;` is a syntax error in an array and the punctuation
  // between two commands everywhere else.
  const compound = input.peek(length) == parenL && holdsCommands(input, length)

  // After the command name a word does not assign, with one exception the
  // declaration builtins need: `local -a x=(1 2)` has an array on the right,
  // and an array is the one thing a plain word cannot be.
  let term = -1
  if (compound && stack.canShift(CompoundAssignName)) term = CompoundAssignName
  else if (stack.canShift(AssignName)) term = AssignName
  else if (input.peek(length) == parenL && stack.canShift(ArrayAssignName)) term = ArrayAssignName
  else return
  input.advance(length)
  input.acceptToken(term)
}, {contextual: true})

// Whether the parenthesis at `from` closes over something with a `;` in it,
// which is to say a list of commands rather than a list of words. Quotes are
// stepped over so that `x=(a ';' b)` stays an array.
function holdsCommands(input: InputStream, from: number) {
  let depth = 0
  for (let at = from; at < parenScanLimit; at++) {
    const ch = input.peek(at)
    if (ch < 0) return false
    if (ch == backslash) at++
    else if (ch == apostrophe || ch == quote) at = skipQuoted(input, at, parenScanLimit, ch) - 1
    else if (ch == parenL) depth++
    else if (ch == parenR && --depth == 0) return false
    else if (ch == semi && depth == 1) return true
  }
  return false
}

// ── The right-hand side of `=~` ───────────────────────────────────────────────

// `[[ $f =~ ^a+(b|c)$ ]]` holds a regular expression where a word would hold
// metacharacters, so it is read to the next space and no further. Space is the
// only thing that ends it: `(`, `|` and `<` are all ordinary here, which is
// what a word cannot say.
//
// That is the shell's own rule as well. A pattern with a space in it has to be
// quoted, and a quoted one is an ordinary word, which is why this steps aside
// for a quote or a `$`.
export const regexps = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  const first = input.next
  if (first == dollar || first == quote || first == apostrophe) return
  if (first < 0 || isBlank(first) || first == lineFeed || !stack.canShift(Regex)) return
  let length = 0
  for (;;) {
    const ch = input.peek(length)
    if (ch < 0 || isBlank(ch) || ch == lineFeed) break
    length++
  }
  input.advance(length)
  input.acceptToken(Regex)
}, {contextual: true})

// ── Newlines ──────────────────────────────────────────────────────────────────

// A newline ends a command where the parser has room for one and is skipped
// everywhere else, which is every place the shell allows a line to be broken:
// after `|`, `&&`, `do`, `then`, `else`, `{`, `(` or a `,` in an array.
//
// A run of `;` and newlines is one token, so that a blank line between two
// commands is not mistaken for a command of its own.
export const terminators = new ExternalTokenizer((input: InputStream, stack: Stack) => {
  // The last command in a file, a substitution or a `case` clause needs no
  // terminator of its own, so one is supplied where the text runs out. It is a
  // token of its own width, which is none, and only these three places produce
  // it; a shell that inserted one anywhere would read `if x then` as two
  // commands, and `then` is not a command.
  if (
    input.next < 0 ||
    input.next == parenR ||
    (input.next == semi && input.peek(1) == semi) ||
    // zsh closes a group without asking for a `;` first: `f() { echo hi }` is
    // a whole function. bash wants the semicolon, and a file that has one
    // reads the same either way. A `}` with no group standing open is the
    // character itself, which `echo done }` prints.
    (input.next == braceR && (stack.context > 0 || endsCompound(input)))
  ) {
    if (stack.canShift(insertedTerminator)) input.acceptToken(insertedTerminator)
    return
  }
  if (input.next != lineFeed && input.next != semi) return
  let length = 0,
    newlines = false
  for (;;) {
    const ch = input.peek(length)
    if (ch == lineFeed) {
      length++
      newlines = true
      // A line that promised a heredoc has its body on the next line, so the
      // run stops here and the heredoc tokenizer reads what follows.
      if (heredocsBefore(input, length - 1).length) break
    } else if (ch == semi) {
      // `;;` ends a `case` clause and is not a terminator.
      if (input.peek(length + 1) == semi) break
      length++
    } else if (isBlank(ch)) {
      length++
    } else {
      break
    }
  }
  if (length == 0) return
  if (stack.canShift(Terminator)) input.acceptToken(Terminator, length)
  // Nothing to end. A run of newlines here is a blank line between commands, or
  // a line broken inside one; either way it is space. A `;` here is the one in
  // a `for ((;;))` header, and is left for the grammar's own token.
  else if (newlines) input.acceptToken(blankLine, length)
}, {contextual: true})

// How many `{` groups the parser stands inside. The question comes up one
// token before the `}` is read, which is too early to ask the grammar, so the
// count is kept here.
export const trackGroups = new ContextTracker<number>({
  start: 0,
  shift(depth, term) {
    if (term == GroupOpen) return depth + 1
    if (term == GroupClose) return depth > 0 ? depth - 1 : 0
    return depth
  },
  hash: depth => depth
})

// `f() { if x; then y; fi }` closes without a `;` and `f() { echo hi }` does
// not, because `}` is a reserved word where a command may start and a plain
// word where an argument may. A command that ended in one of the shell's own
// closing words has left room for another command, so this asks what the line
// ended with. It is the same question bash asks of the token it read last.
function endsCompound(input: InputStream) {
  let at = -1
  while (isBlank(input.peek(at))) at--
  const ch = input.peek(at)
  if (ch == parenR || ch == braceR || ch == bracketR) return true
  return closingWords.some(word => {
    const start = at - word.length + 1
    for (let i = 0; i < word.length; i++)
      if (input.peek(start + i) != word.charCodeAt(i)) return false
    if (isNameChar(input.peek(start - 1))) return false
    // The word has to be standing where a command could, or it is not the
    // shell's word at all: `echo done` ends in the same four letters and means
    // nothing by them.
    let before = start - 1
    while (isBlank(input.peek(before))) before--
    const previous = input.peek(before)
    return (
      previous < 0 ||
      previous == semi ||
      previous == lineFeed ||
      previous == amp ||
      previous == pipe ||
      previous == parenL ||
      previous == parenR ||
      previous == braceL ||
      previous == braceR
    )
  })
}

const closingWords = ["fi", "done", "esac"]

// ── Comments ──────────────────────────────────────────────────────────────────

// `#` to the end of the line, but only where a word could start: `a#b` is one
// word and `a #b` is a word and a comment. Nothing is skipped inside a word, so
// this is never asked about a `#` in the middle of one.
export const comments = new ExternalTokenizer((input: InputStream) => {
  if (input.next != hash || !endsWord(input.peek(-1))) return
  while (input.next != lineFeed && input.next >= 0) input.advance()
  input.acceptToken(Comment)
})

// ── Heredocs ──────────────────────────────────────────────────────────────────

interface Heredoc {
  delimiter: string
  stripTabs: boolean
}

// The body of a heredoc starts on the line after the `<<` that promised it, and
// one line may promise several. Rather than carry the promise from token to
// token, it is recovered here by reading back over the line that just ended.
//
// The body is one token however many heredocs the line opened, and it is
// skipped like whitespace, since there is nowhere in the grammar for it to go.
export const heredocs = new ExternalTokenizer((input: InputStream) => {
  if (input.peek(-1) != lineFeed) return
  const pending = heredocsBefore(input, -1)
  if (!pending.length) return
  let length = 0
  for (const heredoc of pending) length = skipBody(input, length, heredoc)
  if (length > 0) input.acceptToken(HeredocBody, length)
})

// Reads the line that ends at `end` and returns the heredocs it opened.
function heredocsBefore(input: InputStream, end: number): readonly Heredoc[] {
  let start = end
  while (input.peek(start - 1) >= 0 && input.peek(start - 1) != lineFeed) start--
  // Cheap way out: a line with no `<` on it opened nothing, and nearly every
  // line is one of those.
  let seen = false
  for (let at = start; at < end && !seen; at++) if (input.peek(at) == lt) seen = true
  return seen ? scanLine(input, start, end) : none
}

const none: readonly Heredoc[] = []

function scanLine(input: InputStream, start: number, end: number): readonly Heredoc[] {
  const found: Heredoc[] = []
  let at = start,
    arithmetic = 0
  while (at < end) {
    const ch = input.peek(at)
    if (ch == backslash) {
      at += 2
    } else if (ch == apostrophe || ch == quote) {
      at = skipQuoted(input, at, end, ch)
    } else if (ch == hash && (at == start || endsWord(input.peek(at - 1)))) {
      break
    } else if (ch == parenL && input.peek(at + 1) == parenL) {
      // `$((1 << 2))` shifts a number and promises nothing.
      arithmetic++
      at += 2
    } else if (ch == parenR && input.peek(at + 1) == parenR && arithmetic > 0) {
      arithmetic--
      at += 2
    } else if (ch == lt && input.peek(at + 1) == lt && arithmetic == 0) {
      if (input.peek(at + 2) == lt) {
        // `<<<` is a here-string, which is written where it stands.
        at += 3
        continue
      }
      at += 2
      let stripTabs = false
      if (input.peek(at) == dash) {
        stripTabs = true
        at++
      }
      while (at < end && isBlank(input.peek(at))) at++
      const delimiter = readDelimiter(input, at, end)
      at = delimiter.at
      if (delimiter.text) found.push({delimiter: delimiter.text, stripTabs})
    } else {
      at++
    }
  }
  return found
}

function skipQuoted(input: InputStream, at: number, end: number, quoteChar: number) {
  at++
  while (at < end) {
    const ch = input.peek(at)
    if (ch == backslash && quoteChar == quote) at += 2
    else if (ch == quoteChar) return at + 1
    else at++
  }
  return at
}

// `<<EOF`, `<<'EOF'`, `<<"EOF"` and `<<\EOF` all name the same delimiter. The
// quoting decides whether the body is expanded, which is a question for the
// shell rather than for the parser.
function readDelimiter(input: InputStream, at: number, end: number) {
  let text = ""
  while (at < end) {
    const ch = input.peek(at)
    if (ch == apostrophe || ch == quote) {
      const closing = ch
      at++
      while (at < end && input.peek(at) != closing) text += String.fromCharCode(input.peek(at++))
      at++
    } else if (ch == backslash) {
      at++
      if (at < end) text += String.fromCharCode(input.peek(at++))
    } else if (endsWord(ch)) {
      break
    } else {
      text += String.fromCharCode(input.peek(at++))
    }
  }
  return {text, at}
}

// Reads lines from `at` until one of them is the delimiter on its own, and
// returns the offset just past it. An unclosed heredoc runs to the end of the
// file, which is what the shell does with it too.
function skipBody(input: InputStream, at: number, heredoc: Heredoc) {
  for (;;) {
    if (input.peek(at) < 0) return at
    let scan = at
    if (heredoc.stripTabs) while (input.peek(scan) == tab) scan++
    let matched = 0
    while (
      matched < heredoc.delimiter.length &&
      input.peek(scan + matched) == heredoc.delimiter.charCodeAt(matched)
    )
      matched++
    const closed =
      matched == heredoc.delimiter.length &&
      (input.peek(scan + matched) == lineFeed || input.peek(scan + matched) < 0)
    while (input.peek(at) >= 0 && input.peek(at) != lineFeed) at++
    if (input.peek(at) == lineFeed) at++
    if (closed) return at
  }
}