text: /**
   * @typedef TokenStreamItem
   * @property {string} type
   * @property {string | Array<string|TokenStreamItem>} content
   *
   * @typedef {Array<string|TokenStreamItem>} TokenStream
   *
   * @typedef {Array<string | [string, string | Array]>} SimplifiedTokenStream
   *
   * @typedef {Array<PrettyTokenStreamItem>} PrettyTokenStream
   * @typedef {string | LineBreakItem | GlueItem | [string, string | Array]} PrettyTokenStreamItem
   */
  
  module.exports = {
    /**
     * Simplifies the token stream to ease the matching with the expected token stream.
     *
     * * Strings are kept as-is
     * * In arrays each value is transformed individually
     * * Values that are empty (empty arrays or strings only containing whitespace)
     *
     * @param {TokenStream} tokenStream
     * @returns {SimplifiedTokenStream}
     */
    simplify: function simplify(tokenStream) {
      return tokenStream
        .map(innerSimple)
        .filter((value) => !(typeof value === 'string' && isBlank(value)))
  
      /**
       * @param {string | TokenStreamItem} value
       * @returns {string | [string, string | Array]}
       */
      function innerSimple(value) {
        if (typeof value === 'object') {
          if (Array.isArray(value.content)) {
            return [value.type, simplify(value.content)]
          } else {
            return [value.type, value.content]
          }
        } else {
          return value
        }
      }
    },
  
    /**
     * @param {TokenStream} tokenStream
     * @returns {string}
     */
    prettyprint(tokenStream) {
      return printPrettyTokenStream(toPrettyTokenStream(tokenStream))
    },
  }
  
  /**
   * This item indicates that one or multiple line breaks are present between the preceding and following items in the
   * source token stream.
   *
   * Only if an item is enabled will it appear in the pretty-printed token stream.
   */
  class LineBreakItem {
    /** @param {number} sourceCount */
    constructor(sourceCount) {
      this.sourceCount = sourceCount
      this.enabled = false
    }
  }
  /**
   * This item indicates the the preceding and following items are to be printed on the same line in the pretty-printed
   * token stream.
   */
  class GlueItem {}
  
  /**
   * @param {TokenStream} tokenStream
   * @returns {PrettyTokenStream}
   */
  function toPrettyTokenStream(tokenStream) {
    /** @type {PrettyTokenStream} */
    const prettyStream = []
    for (const token of tokenStream) {
      if (typeof token === 'string') {
        if (isBlank(token)) {
          // blank string
          const lineBreaks = countLineBreaks(token)
          if (lineBreaks > 0) {
            prettyStream.push(new LineBreakItem(lineBreaks))
          }
        } else {
          // might start with line breaks
          const startLineBreaks = countLineBreaks(/^\s*/.exec(token)[0])
          if (startLineBreaks > 0) {
            prettyStream.push(new LineBreakItem(startLineBreaks))
          }
  
          prettyStream.push(token)
  
          const endLineBreaks = countLineBreaks(/\s*$/.exec(token)[0])
          if (endLineBreaks > 0) {
            prettyStream.push(new LineBreakItem(endLineBreaks))
          }
        }
      } else {
        prettyStream.push(innerSimple(token))
      }
    }
    /**
     * @param {TokenStreamItem} value
     * @returns {[string, string | Array]}
     */
    function innerSimple(value) {
      if (Array.isArray(value.content)) {
        return [value.type, toPrettyTokenStream(value.content)]
      } else {
        return [value.type, value.content]
      }
    }
  
    prettyFormat(prettyStream)
    return prettyStream
  }
  
  /**
   * @param {PrettyTokenStream} prettyStream
   * @returns {void}
   */
  function prettyFormat(prettyStream) {
    // The maximum number of (glued) tokens per line
    const MAX_TOKEN_PER_LINE = 5
    // The maximum number of characters per line
    // (this is based on an estimation. The actual output might be longer.)
    const MAX_PRINT_WIDTH = 80
  
    prettyTrimLineBreaks(prettyStream)
    // enable all line breaks with >=2 breaks in the source token stream
    prettyEnableLineBreaks(prettyStream, (br) => br.sourceCount >= 2)
  
    const ranges = prettySplit(
      prettyStream,
      (br) => br instanceof LineBreakItem && br.enabled,
    )
    for (const group of ranges) {
      if (prettySomeLineBreak(group, true, (br) => br.enabled)) {
        // Since we just split by enabled line break, only nested line breaks can be enabled. This usually
        // indicates complex token streams, so let's just enable all line breaks and call it a day.
        prettyEnableLineBreaks(group, () => true)
      } else {
        // try to optimize for the pattern /<token>{1,MAX_TOKEN_PER_LINE}(\n<token>{1,MAX_TOKEN_PER_LINE})*/
        const lines = prettySplit(group, (i) => i instanceof LineBreakItem)
  
        /**
         * Returns whether lines can generally be glued together (no line breaks within lines and don't glue with
         * nested tokens).
         */
        function glueable() {
          return lines.every((g) => {
            if (g.length > 1) {
              if (prettyContainsNonTriviallyNested(g)) {
                // the token with nested tokens might be glued together with other tokens and we can't allow
                // that to happen
                return false
              } else {
                return true
              }
            } else {
              // we can safely ignore all tokens that are on their own line
              return true
            }
          })
        }
        function tokensPerLine() {
          return lines.map((g) => prettyCountTokens(g, true))
        }
        /**
         * Returns an estimate for the output length each line will have
         */
        function widthPerLine() {
          return lines.map((g) => {
            if (g.length > 1) {
              return (
                g
                  .map((item) =>
                    isToken(item) ? ', '.length + JSON.stringify(item).length : 0,
                  )
                  .reduce((a, b) => a + b, 0) - ', '.length
              )
            } else {
              // we don't really care about the print width of a single-token line
              return 1
            }
          })
        }
  
        const glueTokens =
          glueable() &&
          // at most this many tokens per line
          Math.max(...tokensPerLine()) <= MAX_TOKEN_PER_LINE &&
          // the output of each line can be at most this many characters long
          Math.max(...widthPerLine()) <= MAX_PRINT_WIDTH &&
          // We need to have at least 2 lines in this group OR this group isn't the only group in the stream.
          // This will prevent all tokens of a really short token stream to be glued together.
          (lines.length > 1 || ranges.length > 1)
  
        if (glueTokens) {
          prettyGlueTogetherAll(prettyStream, group)
        } else {
          const flatTokenCount = prettyCountTokens(group, false)
          const deepTokenCount = prettyCountTokens(group, true)
          if (
            // prevent a one-token-per-line situation
            flatTokenCount > lines.length &&
            // require at least 2 tokens per line on average
            deepTokenCount >= lines.length * 2
          ) {
            prettyEnableLineBreaks(group, () => true)
          }
        }
      }
    }
  }
  
  /**
   * @param {PrettyTokenStream} prettyStream
   * @param {number} [indentationLevel]
   * @returns {string}
   */
  function printPrettyTokenStream(prettyStream, indentationLevel = 1) {
    const indentChar = '    '
  
    // can't use tabs because the console will convert one tab to four spaces
    const indentation = new Array(indentationLevel + 1).join(indentChar)
  
    let out = ''
    out += '[\n'
  
    let glued = false
    prettyStream.forEach((item, i) => {
      if (item instanceof LineBreakItem) {
        if (item.enabled) {
          out += '\n'
        }
      } else if (item instanceof GlueItem) {
        out = out.trimEnd()
        if (out[out.length - 1] === ',') {
          out += ' '
        }
        glued = true
      } else {
        if (glued) {
          glued = false
        } else {
          out += indentation
        }
  
        if (typeof item === 'string') {
          out += JSON.stringify(item)
        } else {
          const name = item[0]
          const content = item[1]
  
          out += '[' + JSON.stringify(name) + ', '
  
          if (typeof content === 'string') {
            // simple string literal
            out += JSON.stringify(content)
          } else if (content.length === 1 && typeof content[0] === 'string') {
            // token stream that only contains a single string literal
            out += JSON.stringify(content)
          } else {
            // token stream
            out += printPrettyTokenStream(content, indentationLevel + 1)
          }
  
          out += ']'
        }
  
        const lineEnd = i === prettyStream.length - 1 ? '\n' : ',\n'
        out += lineEnd
      }
    })
    out += indentation.substr(indentChar.length) + ']'
    return out
  }
  
  /**
   * Returns whether the given string is empty or contains only whitespace characters.
   *
   * @param {string} str
   * @returns {boolean}
   */
  function isBlank(str) {
    return /^\s*$/.test(str)
  }
  
  /**
   * @param {string} str
   * @returns {number}
   */
  function countLineBreaks(str) {
    return str.split(/\r\n?|\n/g).length - 1
  }
  
  /**
   * Trim all line breaks at the start and at the end of the pretty stream.
   *
   * @param {PrettyTokenStream} prettyStream
   * @returns {void}
   */
  function prettyTrimLineBreaks(prettyStream) {
    let value
    while ((value = prettyStream[0])) {
      if (value instanceof LineBreakItem) {
        prettyStream.shift()
      } else {
        break
      }
    }
    while ((value = prettyStream[prettyStream.length - 1])) {
      if (value instanceof LineBreakItem) {
        prettyStream.pop()
      } else {
        break
      }
    }
  }
  
  /**
   * Enables all line breaks in the pretty token stream (but not in nested token stream) that contain at least some
   * number of line breaks in the source token stream.
   *
   * @param {PrettyTokenStream} prettyStream
   * @param {(item: LineBreakItem) => boolean} cond
   */
  function prettyEnableLineBreaks(prettyStream, cond) {
    prettyStream.forEach((token) => {
      if (token instanceof LineBreakItem && cond(token)) {
        token.enabled = true
      }
    })
  }
  
  /**
   * Splits the given pretty stream on all items for which `cond` return `true`. The items for which `cond` returns
   * `true` will not be part of any of the created streams. No empty streams will be returned.
   *
   * @param {PrettyTokenStream} prettyStream
   * @param {(item: PrettyTokenStreamItem) => boolean} cond
   * @returns {PrettyTokenStream[]}
   */
  function prettySplit(prettyStream, cond) {
    /** @type {PrettyTokenStream[]} */
    const result = []
    /** @type {PrettyTokenStream} */
    let current = []
    for (const item of prettyStream) {
      if (cond(item)) {
        if (current.length > 0) {
          result.push(current)
          current = []
        }
      } else {
        current.push(item)
      }
    }
    if (current.length > 0) {
      result.push(current)
      current = []
    }
    return result
  }
  
  /**
   * @param {PrettyTokenStream} prettyStream
   * @param {boolean} recursive
   * @param {(item: LineBreakItem) => boolean} cond
   * @returns {boolean}
   */
  function prettySomeLineBreak(prettyStream, recursive, cond) {
    for (const item of prettyStream) {
      if (item instanceof LineBreakItem && cond(item)) {
        return true
      } else if (
        recursive &&
        isNested(item) &&
        prettySomeLineBreak(item[1], true, cond)
      ) {
        return true
      }
    }
    return false
  }
  /**
   * @param {PrettyTokenStream} prettyStream
   * @returns {boolean}
   */
  function prettyContainsNonTriviallyNested(prettyStream) {
    for (const item of prettyStream) {
      if (isNested(item) && !isTriviallyNested(item)) {
        return true
      }
    }
    return false
  }
  /**
   * @param {PrettyTokenStream} prettyStream
   * @param {boolean} recursive
   * @returns {number}
   */
  function prettyCountTokens(prettyStream, recursive) {
    let count = 0
    for (const item of prettyStream) {
      if (isToken(item)) {
        count++
        if (recursive && isNested(item) && !isTriviallyNested(item)) {
          count += prettyCountTokens(item[1], true)
        }
      }
    }
    return count
  }
  
  /**
   * Adds glue between the given tokens in the given stream.
   *
   * @param {PrettyTokenStream} prettyStream
   * @param {string | [string, string | any[]]} prev
   * @param {string | [string, string | any[]]} next
   */
  function prettyGlueTogether(prettyStream, prev, next) {
    // strings may appear more than once in the stream, so we have to search for tokens.
    if (typeof prev !== 'string') {
      let index = prettyStream.indexOf(prev)
      if (index === -1 || prettyStream[index + 1] !== next) {
        throw new Error(
          'Cannot glue: At least one of the tokens is not part of the given token stream.',
        )
      }
      prettyStream.splice(index + 1, 0, new GlueItem())
    } else {
      let index = prettyStream.indexOf(next)
      if (index === -1 || prettyStream[index - 1] !== prev) {
        throw new Error(
          'Cannot glue: At least one of the tokens is not part of the given token stream.',
        )
      }
      prettyStream.splice(index, 0, new GlueItem())
    }
  }
  /**
   * Glues together all token in the given slice of the given token stream.
   *
   * @param {PrettyTokenStream} prettyStream
   * @param {PrettyTokenStream} slice
   */
  function prettyGlueTogetherAll(prettyStream, slice) {
    for (let i = 1, l = slice.length; i < l; i++) {
      const prev = slice[i - 1]
      const next = slice[i]
      if (isToken(prev) && isToken(next)) {
        prettyGlueTogether(prettyStream, prev, next)
      }
    }
  }
  
  /**
   * @param {PrettyTokenStreamItem} item
   * @returns {item is (string | [string, string | any[]])}
   */
  function isToken(item) {
    return typeof item === 'string' || Array.isArray(item)
  }
  
  /**
   * @param {PrettyTokenStreamItem} item
   * @returns {item is [string, any[]]}
   */
  function isNested(item) {
    return Array.isArray(item) && Array.isArray(item[1])
  }
  /**
   * @param {PrettyTokenStreamItem} item
   * @returns {item is [string, [string]]}
   */
  function isTriviallyNested(item) {
    return (
      isNested(item) && item[1].length === 1 && typeof item[1][0] === 'string'
    )
  }
  