lexer.ts

import { syntaxError } from '../error/syntaxError';

import type { Source } from './source';
import type { TokenKindEnum } from './tokenKind';
import { Token } from './ast';
import { TokenKind } from './tokenKind';
import { dedentBlockStringValue } from './blockString';

/**
 * Given a Source object, creates a Lexer for that source.
 * A Lexer is a stateful stream generator in that every time
 * it is advanced, it returns the next token in the Source. Assuming the
 * source lexes, the final Token emitted by the lexer will be of kind
 * EOF, after which the lexer will repeatedly return the same EOF token
 * whenever called.
 */
export class Lexer {
  source: Source;

  /**
   * The previously focused non-ignored token.
   */
  lastToken: Token;

  /**
   * The currently focused non-ignored token.
   */
  token: Token;

  /**
   * The (1-indexed) line containing the current token.
   */
  line: number;

  /**
   * The character offset at which the current line begins.
   */
  lineStart: number;

  constructor(source: Source) {
    const startOfFileToken = new Token(TokenKind.SOF, 0, 0, 0, 0);

    this.source = source;
    this.lastToken = startOfFileToken;
    this.token = startOfFileToken;
    this.line = 1;
    this.lineStart = 0;
  }

  /**
   * Advances the token stream to the next non-ignored token.
   */
  advance(): Token {
    this.lastToken = this.token;
    const token = (this.token = this.lookahead());
    return token;
  }

  /**
   * Looks ahead and returns the next non-ignored token, but does not change
   * the state of Lexer.
   */
  lookahead(): Token {
    let token = this.token;
    if (token.kind !== TokenKind.EOF) {
      do {
        if (token.next) {
          token = token.next;
        } else {
          // Read the next token and form a link in the token linked-list.
          const nextToken = readNextToken(this, token.end);
          // @ts-expect-error next is only mutable during parsing.
          token.next = nextToken;
          // @ts-expect-error prev is only mutable during parsing.
          nextToken.prev = token;
          token = nextToken;
        }
      } while (token.kind === TokenKind.COMMENT);
    }
    return token;
  }
}

/**
 * @internal
 */
export function isPunctuatorTokenKind(kind: TokenKindEnum): boolean {
  return (
    kind === TokenKind.BANG ||
    kind === TokenKind.DOLLAR ||
    kind === TokenKind.AMP ||
    kind === TokenKind.PAREN_L ||
    kind === TokenKind.PAREN_R ||
    kind === TokenKind.SPREAD ||
    kind === TokenKind.COLON ||
    kind === TokenKind.EQUALS ||
    kind === TokenKind.AT ||
    kind === TokenKind.BRACKET_L ||
    kind === TokenKind.BRACKET_R ||
    kind === TokenKind.BRACE_L ||
    kind === TokenKind.PIPE ||
    kind === TokenKind.BRACE_R
  );
}

/**
 * SourceCharacter ::
 *   - U+0009 (Horizontal Tab)
 *   - U+000A (New Line)
 *   - U+000D (Carriage Return)
 *   - U+0020-U+FFFF
 */
function isSourceCharacter(code: number): boolean {
  return (
    code >= 0x0020 || code === 0x0009 || code === 0x000a || code === 0x000d
  );
}

/**
 * Prints the code point (or end of file reference) at a given location in a
 * source for use in error messages.
 *
 * Printable ASCII is printed quoted, while other points are printed in Unicode
 * code point form (ie. U+1234).
 */
function printCodePointAt(lexer: Lexer, location: number): string {
  const body = lexer.source.body;
  if (location >= body.length) {
    return TokenKind.EOF;
  }
  const code = body.charCodeAt(location);
  // Printable ASCII
  if (code >= 0x0020 && code <= 0x007e) {
    return code === 0x0022 ? "'\"'" : `"${body[location]}"`;
  }
  // Unicode code point
  const zeroPad =
    code > 0xfff ? '' : code > 0xff ? '0' : code > 0xf ? '00' : '000';
  return `U+${zeroPad}${code.toString(16).toUpperCase()}`;
}

/**
 * Create a token with line and column location information.
 */
function createToken(
  lexer: Lexer,
  kind: TokenKindEnum,
  start: number,
  end: number,
  value?: string,
): Token {
  const line = lexer.line;
  const col = 1 + start - lexer.lineStart;
  return new Token(kind, start, end, line, col, value);
}

/**
 * Gets the next token from the source starting at the given position.
 *
 * This skips over whitespace until it finds the next lexable token, then lexes
 * punctuators immediately or calls the appropriate helper function for more
 * complicated tokens.
 */
function readNextToken(lexer: Lexer, start: number): Token {
  const body = lexer.source.body;
  const bodyLength = body.length;
  let position = start;

  while (position < bodyLength) {
    const code = body.charCodeAt(position);

    // SourceCharacter
    switch (code) {
      // Ignored ::
      //   - UnicodeBOM
      //   - WhiteSpace
      //   - LineTerminator
      //   - Comment
      //   - Comma
      //
      // UnicodeBOM :: "Byte Order Mark (U+FEFF)"
      //
      // WhiteSpace ::
      //   - "Horizontal Tab (U+0009)"
      //   - "Space (U+0020)"
      //
      // Comma :: ,
      case 0xfeff: // <BOM>
      case 0x0009: // \t
      case 0x0020: // <space>
      case 0x002c: // ,
        ++position;
        continue;
      // LineTerminator ::
      //   - "New Line (U+000A)"
      //   - "Carriage Return (U+000D)" [lookahead != "New Line (U+000A)"]
      //   - "Carriage Return (U+000D)" "New Line (U+000A)"
      case 0x000a: // \n
        ++position;
        ++lexer.line;
        lexer.lineStart = position;
        continue;
      case 0x000d: // \r
        if (body.charCodeAt(position + 1) === 0x000a) {
          position += 2;
        } else {
          ++position;
        }
        ++lexer.line;
        lexer.lineStart = position;
        continue;
      // Comment
      case 0x0023: // #
        return readComment(lexer, position);
      // Token ::
      //   - Punctuator
      //   - Name
      //   - IntValue
      //   - FloatValue
      //   - StringValue
      //
      // Punctuator :: one of ! $ & ( ) ... : = @ [ ] { | }
      case 0x0021: // !
        return createToken(lexer, TokenKind.BANG, position, position + 1);
      case 0x0024: // $
        return createToken(lexer, TokenKind.DOLLAR, position, position + 1);
      case 0x0026: // &
        return createToken(lexer, TokenKind.AMP, position, position + 1);
      case 0x0028: // (
        return createToken(lexer, TokenKind.PAREN_L, position, position + 1);
      case 0x0029: // )
        return createToken(lexer, TokenKind.PAREN_R, position, position + 1);
      case 0x002e: // .
        if (
          body.charCodeAt(position + 1) === 0x002e &&
          body.charCodeAt(position + 2) === 0x002e
        ) {
          return createToken(lexer, TokenKind.SPREAD, position, position + 3);
        }
        break;
      case 0x003a: // :
        return createToken(lexer, TokenKind.COLON, position, position + 1);
      case 0x003d: // =
        return createToken(lexer, TokenKind.EQUALS, position, position + 1);
      case 0x0040: // @
        return createToken(lexer, TokenKind.AT, position, position + 1);
      case 0x005b: // [
        return createToken(lexer, TokenKind.BRACKET_L, position, position + 1);
      case 0x005d: // ]
        return createToken(lexer, TokenKind.BRACKET_R, position, position + 1);
      case 0x007b: // {
        return createToken(lexer, TokenKind.BRACE_L, position, position + 1);
      case 0x007c: // |
        return createToken(lexer, TokenKind.PIPE, position, position + 1);
      case 0x007d: // }
        return createToken(lexer, TokenKind.BRACE_R, position, position + 1);
      // StringValue
      case 0x0022: // "
        if (
          body.charCodeAt(position + 1) === 0x0022 &&
          body.charCodeAt(position + 2) === 0x0022
        ) {
          return readBlockString(lexer, position);
        }
        return readString(lexer, position);
    }

    // IntValue | FloatValue (Digit | -)
    if (isDigit(code) || code === 0x002d) {
      return readNumber(lexer, position, code);
    }

    // Name
    if (isNameStart(code)) {
      return readName(lexer, position);
    }

    throw syntaxError(
      lexer.source,
      position,
      code === 0x0027
        ? 'Unexpected single quote character (\'), did you mean to use a double quote (")?'
        : isSourceCharacter(code)
        ? `Unexpected character: ${printCodePointAt(lexer, position)}.`
        : `Invalid character: ${printCodePointAt(lexer, position)}.`,
    );
  }

  return createToken(lexer, TokenKind.EOF, bodyLength, bodyLength);
}

/**
 * Reads a comment token from the source file.
 *
 * Comment :: # CommentChar* [lookahead != CommentChar]
 *
 * CommentChar :: SourceCharacter but not LineTerminator
 */
function readComment(lexer: Lexer, start: number): Token {
  const body = lexer.source.body;
  const bodyLength = body.length;
  let position = start + 1;

  while (position < bodyLength) {
    const code = body.charCodeAt(position);

    // LineTerminator (\n | \r)
    if (code === 0x000a || code === 0x000d) {
      break;
    }

    // SourceCharacter
    if (isSourceCharacter(code)) {
      ++position;
    } else {
      break;
    }
  }

  return createToken(
    lexer,
    TokenKind.COMMENT,
    start,
    position,
    body.slice(start + 1, position),
  );
}

/**
 * Reads a number token from the source file, either a FloatValue or an IntValue
 * depending on whether a FractionalPart or ExponentPart is encountered.
 *
 * IntValue :: IntegerPart [lookahead != {Digit, `.`, NameStart}]
 *
 * IntegerPart ::
 *   - NegativeSign? 0
 *   - NegativeSign? NonZeroDigit Digit*
 *
 * NegativeSign :: -
 *
 * NonZeroDigit :: Digit but not `0`
 *
 * FloatValue ::
 *   - IntegerPart FractionalPart ExponentPart [lookahead != {Digit, `.`, NameStart}]
 *   - IntegerPart FractionalPart [lookahead != {Digit, `.`, NameStart}]
 *   - IntegerPart ExponentPart [lookahead != {Digit, `.`, NameStart}]
 *
 * FractionalPart :: . Digit+
 *
 * ExponentPart :: ExponentIndicator Sign? Digit+
 *
 * ExponentIndicator :: one of `e` `E`
 *
 * Sign :: one of + -
 */
function readNumber(lexer: Lexer, start: number, firstCode: number): Token {
  const body = lexer.source.body;
  let position = start;
  let code = firstCode;
  let isFloat = false;

  // NegativeSign (-)
  if (code === 0x002d) {
    code = body.charCodeAt(++position);
  }

  // Zero (0)
  if (code === 0x0030) {
    code = body.charCodeAt(++position);
    if (isDigit(code)) {
      throw syntaxError(
        lexer.source,
        position,
        `Invalid number, unexpected digit after 0: ${printCodePointAt(
          lexer,
          position,
        )}.`,
      );
    }
  } else {
    position = readDigits(lexer, position, code);
    code = body.charCodeAt(position);
  }

  // Full stop (.)
  if (code === 0x002e) {
    isFloat = true;

    code = body.charCodeAt(++position);
    position = readDigits(lexer, position, code);
    code = body.charCodeAt(position);
  }

  // E e
  if (code === 0x0045 || code === 0x0065) {
    isFloat = true;

    code = body.charCodeAt(++position);
    // + -
    if (code === 0x002b || code === 0x002d) {
      code = body.charCodeAt(++position);
    }
    position = readDigits(lexer, position, code);
    code = body.charCodeAt(position);
  }

  // Numbers cannot be followed by . or NameStart
  if (code === 0x002e || isNameStart(code)) {
    throw syntaxError(
      lexer.source,
      position,
      `Invalid number, expected digit but got: ${printCodePointAt(
        lexer,
        position,
      )}.`,
    );
  }

  return createToken(
    lexer,
    isFloat ? TokenKind.FLOAT : TokenKind.INT,
    start,
    position,
    body.slice(start, position),
  );
}

/**
 * Returns the new position in the source after reading one or more digits.
 */
function readDigits(lexer: Lexer, start: number, firstCode: number): number {
  if (!isDigit(firstCode)) {
    throw syntaxError(
      lexer.source,
      start,
      `Invalid number, expected digit but got: ${printCodePointAt(
        lexer,
        start,
      )}.`,
    );
  }

  const body = lexer.source.body;
  let position = start;
  let code = firstCode;

  do {
    code = body.charCodeAt(++position);
  } while (isDigit(code));

  return position;
}

/**
 * Reads a single-quote string token from the source file.
 *
 * StringValue ::
 *   - `""` [lookahead != `"`]
 *   - `"` StringCharacter+ `"`
 *
 * StringCharacter ::
 *   - SourceCharacter but not `"` or `\` or LineTerminator
 *   - `\u` EscapedUnicode
 *   - `\` EscapedCharacter
 *
 * EscapedUnicode :: /[0-9A-Fa-f]{4}/
 *
 * EscapedCharacter :: one of `"` `\` `/` `b` `f` `n` `r` `t`
 */
function readString(lexer: Lexer, start: number): Token {
  const body = lexer.source.body;
  const bodyLength = body.length;
  let position = start + 1;
  let chunkStart = position;
  let value = '';

  while (position < bodyLength) {
    const code = body.charCodeAt(position);

    // Closing Quote (")
    if (code === 0x0022) {
      value += body.slice(chunkStart, position);
      return createToken(lexer, TokenKind.STRING, start, position + 1, value);
    }

    // Escape Sequence (\)
    if (code === 0x005c) {
      value += body.slice(chunkStart, position);
      const escape =
        body.charCodeAt(position + 1) === 0x0075 // u
          ? readEscapedUnicode(lexer, position)
          : readEscapedCharacter(lexer, position);
      value += escape.value;
      position += escape.size;
      chunkStart = position;
      continue;
    }

    // LineTerminator (\n | \r)
    if (code === 0x000a || code === 0x000d) {
      break;
    }

    // SourceCharacter
    if (isSourceCharacter(code)) {
      ++position;
    } else {
      throw syntaxError(
        lexer.source,
        position,
        `Invalid character within String: ${printCodePointAt(
          lexer,
          position,
        )}.`,
      );
    }
  }

  throw syntaxError(lexer.source, position, 'Unterminated string.');
}

// The string value and lexed size of an escape sequence.
interface EscapeSequence {
  value: string;
  size: number;
}

function readEscapedUnicode(lexer: Lexer, position: number): EscapeSequence {
  const body = lexer.source.body;
  const code = read16BitHexCode(body, position + 2);

  if (code >= 0) {
    return { value: String.fromCharCode(code), size: 6 };
  }

  throw syntaxError(
    lexer.source,
    position,
    `Invalid Unicode escape sequence: "${body.slice(position, position + 6)}".`,
  );
}

/**
 * Reads four hexadecimal characters and returns the positive integer that 16bit
 * hexadecimal string represents. For example, "000f" will return 15, and "dead"
 * will return 57005.
 *
 * Returns a negative number if any char was not a valid hexadecimal digit.
 */
function read16BitHexCode(body: string, position: number): number {
  // readHexDigit() returns -1 on error. ORing a negative value with any other
  // value always produces a negative value.
  return (
    (readHexDigit(body.charCodeAt(position)) << 12) |
    (readHexDigit(body.charCodeAt(position + 1)) << 8) |
    (readHexDigit(body.charCodeAt(position + 2)) << 4) |
    readHexDigit(body.charCodeAt(position + 3))
  );
}

/**
 * Reads a hexadecimal character and returns its positive integer value (0-15).
 *
 * '0' becomes 0, '9' becomes 9
 * 'A' becomes 10, 'F' becomes 15
 * 'a' becomes 10, 'f' becomes 15
 *
 * Returns -1 if the provided character code was not a valid hexadecimal digit.
 */
function readHexDigit(code: number): number {
  return code >= 0x0030 && code <= 0x0039 // 0-9
    ? code - 0x0030
    : code >= 0x0041 && code <= 0x0046 // A-F
    ? code - 0x0037
    : code >= 0x0061 && code <= 0x0066 // a-f
    ? code - 0x0057
    : -1;
}

/**
 * | Escaped Character | Code Point | Character Name               |
 * | ----------------- | ---------- | ---------------------------- |
 * | {`"`}             | U+0022     | double quote                 |
 * | {`\`}             | U+005C     | reverse solidus (back slash) |
 * | {`/`}             | U+002F     | solidus (forward slash)      |
 * | {`b`}             | U+0008     | backspace                    |
 * | {`f`}             | U+000C     | form feed                    |
 * | {`n`}             | U+000A     | line feed (new line)         |
 * | {`r`}             | U+000D     | carriage return              |
 * | {`t`}             | U+0009     | horizontal tab               |
 */
function readEscapedCharacter(lexer: Lexer, position: number): EscapeSequence {
  const body = lexer.source.body;
  const code = body.charCodeAt(position + 1);
  switch (code) {
    case 0x0022: // "
      return { value: '\u0022', size: 2 };
    case 0x005c: // \
      return { value: '\u005c', size: 2 };
    case 0x002f: // /
      return { value: '\u002f', size: 2 };
    case 0x0062: // b
      return { value: '\u0008', size: 2 };
    case 0x0066: // f
      return { value: '\u000c', size: 2 };
    case 0x006e: // n
      return { value: '\u000a', size: 2 };
    case 0x0072: // r
      return { value: '\u000d', size: 2 };
    case 0x0074: // t
      return { value: '\u0009', size: 2 };
  }
  throw syntaxError(
    lexer.source,
    position,
    `Invalid character escape sequence: "${body.slice(
      position,
      position + 2,
    )}".`,
  );
}

/**
 * Reads a block string token from the source file.
 *
 * StringValue ::
 *   - `"""` BlockStringCharacter* `"""`
 *
 * BlockStringCharacter ::
 *   - SourceCharacter but not `"""` or `\"""`
 *   - `\"""`
 */
function readBlockString(lexer: Lexer, start: number): Token {
  const body = lexer.source.body;
  const bodyLength = body.length;
  let position = start + 3;
  let chunkStart = position;
  let rawValue = '';

  while (position < bodyLength) {
    const code = body.charCodeAt(position);

    // Closing Triple-Quote (""")
    if (
      code === 0x0022 &&
      body.charCodeAt(position + 1) === 0x0022 &&
      body.charCodeAt(position + 2) === 0x0022
    ) {
      rawValue += body.slice(chunkStart, position);
      return createToken(
        lexer,
        TokenKind.BLOCK_STRING,
        start,
        position + 3,
        dedentBlockStringValue(rawValue),
      );
    }

    // Escaped Triple-Quote (\""")
    if (
      code === 0x005c &&
      body.charCodeAt(position + 1) === 0x0022 &&
      body.charCodeAt(position + 2) === 0x0022 &&
      body.charCodeAt(position + 3) === 0x0022
    ) {
      rawValue += body.slice(chunkStart, position) + '"""';
      position += 4;
      chunkStart = position;
      continue;
    }

    // LineTerminator
    if (code === 0x000a || code === 0x000d) {
      if (code === 0x000d && body.charCodeAt(position + 1) === 0x000a) {
        position += 2;
      } else {
        ++position;
      }
      ++lexer.line;
      lexer.lineStart = position;
      continue;
    }

    // SourceCharacter
    if (isSourceCharacter(code)) {
      ++position;
    } else {
      throw syntaxError(
        lexer.source,
        position,
        `Invalid character within String: ${printCodePointAt(
          lexer,
          position,
        )}.`,
      );
    }
  }

  throw syntaxError(lexer.source, position, 'Unterminated string.');
}

/**
 * Reads an alphanumeric + underscore name from the source.
 *
 * Name ::
 *   - NameStart NameContinue* [lookahead != NameContinue]
 *
 * NameStart ::
 *   - Letter
 *   - `_`
 *
 * NameContinue ::
 *   - Letter
 *   - Digit
 *   - `_`
 */
function readName(lexer: Lexer, start: number): Token {
  const body = lexer.source.body;
  const bodyLength = body.length;
  let position = start + 1;

  while (position < bodyLength) {
    const code = body.charCodeAt(position);
    // NameContinue
    if (isLetter(code) || isDigit(code) || code === 0x005f) {
      ++position;
    } else {
      break;
    }
  }

  return createToken(
    lexer,
    TokenKind.NAME,
    start,
    position,
    body.slice(start, position),
  );
}

function isNameStart(code: number): boolean {
  return isLetter(code) || code === 0x005f;
}

/**
 * Digit :: one of
 *   - `0` `1` `2` `3` `4` `5` `6` `7` `8` `9`
 */
function isDigit(code: number): boolean {
  return code >= 0x0030 && code <= 0x0039;
}

/**
 * Letter :: one of
 *   - `A` `B` `C` `D` `E` `F` `G` `H` `I` `J` `K` `L` `M`
 *   - `N` `O` `P` `Q` `R` `S` `T` `U` `V` `W` `X` `Y` `Z`
 *   - `a` `b` `c` `d` `e` `f` `g` `h` `i` `j` `k` `l` `m`
 *   - `n` `o` `p` `q` `r` `s` `t` `u` `v` `w` `x` `y` `z`
 */
function isLetter(code: number): boolean {
  return (
    (code >= 0x0061 && code <= 0x007a) || // A-Z
    (code >= 0x0041 && code <= 0x005a) // a-z
  );
}