<commit_before>/*
 *  Lexer for source files, ToNumber() string conversions, RegExp expressions,
 *  and JSON.
 *
 *  Provides a stream of Ecmascript tokens from an UTF-8/CESU-8 buffer.  The
 *  caller can also rewind the token stream into a certain position which is
 *  needed by the compiler part for multi-pass scanning.  Tokens are
 *  represented as duk_token structures, and contain line number information.
 *  Token types are identified with DUK_TOK_* defines.
 *
 *  Characters are decoded into a fixed size lookup window consisting of
 *  decoded Unicode code points, with window positions past the end of the
 *  input filled with an invalid codepoint (-1).  The tokenizer can thus
 *  perform multiple character lookups efficiently and with few sanity
 *  checks (such as access outside the end of the input), which keeps the
 *  tokenization code small at the cost of performance.
 * 
 *  Character data in tokens (such as identifier names and string literals)
 *  is encoded into CESU-8 format on-the-fly while parsing the token in
 *  question.  The string data is made reachable to garbage collection by
 *  placing the token-related values in value stack entries allocated for
 *  this purpose by the caller.  The characters exist in Unicode code point
 *  form only in the fixed size lookup window, which keeps character data
 *  expansion (of especially ASCII data) low.
 *
 *  Token parsing supports the full range of Unicode characters as described
 *  in the E5 specification.  Parsing has been optimized for ASCII characters
 *  because ordinary Ecmascript code consists almost entirely of ASCII
 *  characters.  Matching of complex Unicode codepoint sets (such as in the
 *  IdentifierStart and IdentifierPart productions) is optimized for size,
 *  and is done using a linear scan of a bit-packed list of ranges.  This is
 *  very slow, but should never be entered unless the source code actually
 *  contains Unicode characters.
 *
 *  Ecmascript tokenization is partially context sensitive.  First,
 *  additional future reserved words are recognized in strict mode (see E5
 *  Section 7.6.1.2).  Second, a forward slash character ('/') can be
 *  recognized either as starting a RegExp literal or as a division operator,
 *  depending on context.  The caller must provide necessary context flags
 *  when requesting a new token.
 *
 *  Future work:
 *
 *    * Make the input window a circular array to avoid copying.  This would
 *      not necessarily complicate the tokenizer much, although it would make
 *      the window fetches more expensive (one AND).
 *
 *    * Make line number tracking optional, as it consumes space.  Also, is
 *      tracking end line really useful for tokens?
 *
 *    * Add a feature flag for disabling UTF-8 decoding of input, as most
 *      source code is ASCII.  Because of Unicode escapes written in ASCII,
 *      this does not allow Unicode support to be removed from e.g.
 *      duk_unicode_is_identifier_start() nor does it allow removal of CESU-8
 *      encoding of e.g. string literals.
 *
 *    * Add a feature flag for disabling Unicode compliance of e.g. identifier
 *      names.  This allows for a build more than a kilobyte smaller, because
 *      Unicode ranges needed by duk_unicode_is_identifier_start() and
 *      duk_unicode_is_identifier_part() can be dropped.  String literals
 *      should still be allowed to contain escaped Unicode, so this still does
 *      not allow removal of CESU-8 encoding of e.g. string literals.
 *
 *    * Character lookup tables for codepoints above BMP could be stripped.
 *
 *    * Strictly speaking, E5 specification requires that source code consists
 *      of 16-bit code units, and if not, must be conceptually converted to
 *      that format first.  The current lexer processes Unicode code points
 *      and allows characters outside the BMP.  These should be converted to
 *      surrogate pairs while reading the source characters into the window,
 *      not after tokens have been formed (as is done now).  However, the fix
 *      is not trivial because two characters are decoded from one codepoint.
 *
 *    * Optimize for speed as well as size.  Large if-else ladders are slow.
 */

#include "duk_internal.h"

/*
 *  Various defines and file specific helper macros
 */

#define DUK__MAX_RE_DECESC_DIGITS     9
#define DUK__MAX_RE_QUANT_DIGITS      9   /* Does not allow e.g. 2**31-1, but one more would allow overflows of u32. */

#define DUK__LOOKUP(lex_ctx,index)    ((lex_ctx)->window[(index)])
#define DUK__ADVANCE(lex_ctx,count)   duk__advance_chars((lex_ctx), (count))
#define DUK__INITBUFFER(lex_ctx)      duk__initbuffer((lex_ctx))
#define DUK__APPENDBUFFER(lex_ctx,x)  duk__appendbuffer((lex_ctx), (int) (x))

/* whether to use macros or helper function depends on call count */
#define DUK__ISDIGIT(x)          ((x) >= '0' && (x) <= '9')
#define DUK__ISHEXDIGIT(x)       duk__is_hex_digit((x))
#define DUK__ISOCTDIGIT(x)       ((x) >= '0' && (x) <= '7')
#define DUK__ISDIGIT03(x)        ((x) >= '0' && (x) <= '3')
#define DUK__ISDIGIT47(x)        ((x) >= '4' && (x) <= '7')

/* lookup shorthands (note: assume context variable is named 'lex_ctx') */
#define DUK__L0()  DUK__LOOKUP(lex_ctx, 0)
#define DUK__L1()  DUK__LOOKUP(lex_ctx, 1)
#define DUK__L2()  DUK__LOOKUP(lex_ctx, 2)
#define DUK__L3()  DUK__LOOKUP(lex_ctx, 3)
#define DUK__L4()  DUK__LOOKUP(lex_ctx, 4)
#define DUK__L5()  DUK__LOOKUP(lex_ctx, 5)

/* packed advance/token number macro used by multiple functions */
#define DUK__ADVTOK(adv,tok)  (((adv) << 8) + (tok))

/*
 *  Read a character from the window leading edge and update the line counter.
 *
 *  Decodes UTF-8/CESU-8 leniently with support for code points from U+0000 to
 *  U+10FFFF, causing an error if the input is unparseable.  Leniency means:
 *
 *    * Unicode code point validation is intentionally not performed,
 *      except to check that the codepoint does not exceed 0x10ffff.
 *
 *    * In particular, surrogate pairs are allowed and not combined, which
 *      allows source files to represent all SourceCharacters with CESU-8.
 *      Broken surrogate pairs are allowed, as Ecmascript does not mandate
 *      their validation.
 *
 *    * Allow non-shortest UTF-8 encodings.
 *
 *  Leniency here causes few security concerns because all character data is
 *  decoded into Unicode codepoints before lexer processing, and is then
 *  re-encoded into CESU-8.  The source can be parsed as strict UTF-8 with
 *  a compiler option.  However, Ecmascript source characters include -all-
 *  16-bit unsigned integer codepoints, so leniency seems to be appropriate.
 *
 *  Note that codepoints above the BMP are not strictly SourceCharacters,
 *  but the lexer still accepts them as such.  Before ending up in a string
 *  or an identifier name, codepoints above BMP are converted into surrogate
 *  pairs and then CESU-8 encoded, resulting in 16-bit Unicode data as
 *  expected by Ecmascript.
 *
 *  An alternative approach to dealing with invalid or partial sequences
 *  would be to skip them and replace them with e.g. the Unicode replacement
 *  character U+FFFD.  This has limited utility because a replacement character
 *  will most likely cause a parse error, unless it occurs inside a string.
 *  Further, Ecmascript source is typically pure ASCII.
 *
 *  See:
 *
 *     http://en.wikipedia.org/wiki/UTF-8
 *     http://en.wikipedia.org/wiki/CESU-8
 *     http://tools.ietf.org/html/rfc3629
 *     http://en.wikipedia.org/wiki/UTF-8#Invalid_byte_sequences
 *
 *  Future work:
 *
 *    * Reject other invalid Unicode sequences (see Wikipedia entry for examples)
 *      in strict UTF-8 mode.
 * 
 *    * Size optimize.  An attempt to use a 16-byte lookup table for the first
 *      byte resulted in a code increase though.
 *
 *    * Is checking against maximum 0x10ffff really useful?  4-byte encoding
 *      imposes a certain limit anyway.
 */

static int duk__read_char(duk_lexer_ctx *lex_ctx) {
	/* attempting to reduce size of 'len' and/or 'i' resulted in larger code */
	int x;
	int len;
	int i;
	duk_uint8_t *p;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
	int mincp;
#endif

	if (lex_ctx->input_offset >= lex_ctx->input_length) {
		return -1;
	}

	p = &lex_ctx->input[lex_ctx->input_offset];
	x = (int) *p++;

	if (x < 0x80) {
		/* 0xxx xxxx -> fast path */
		len = 1;
		goto fastpath;
	} else if (x < 0xc0) {
		/* 10xx xxxx -> invalid */
		goto error;
	} else if (x < 0xe0) {
		/* 110x xxxx   10xx xxxx  */
		len = 2;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x80;
#endif
		x = x & 0x1f;
	} else if (x < 0xf0) {
		/* 1110 xxxx   10xx xxxx   10xx xxxx */
		len = 3;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x800;
#endif
		x = x & 0x0f;
	} else if (x < 0xf8) {
		/* 1111 0xxx   10xx xxxx   10xx xxxx   10xx xxxx */
		len = 4;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x10000;
#endif
		x = x & 0x07;<commit_msg>Fix a potential 64-bit pointer arithmetic issue<commit_after>/*
 *  Lexer for source files, ToNumber() string conversions, RegExp expressions,
 *  and JSON.
 *
 *  Provides a stream of Ecmascript tokens from an UTF-8/CESU-8 buffer.  The
 *  caller can also rewind the token stream into a certain position which is
 *  needed by the compiler part for multi-pass scanning.  Tokens are
 *  represented as duk_token structures, and contain line number information.
 *  Token types are identified with DUK_TOK_* defines.
 *
 *  Characters are decoded into a fixed size lookup window consisting of
 *  decoded Unicode code points, with window positions past the end of the
 *  input filled with an invalid codepoint (-1).  The tokenizer can thus
 *  perform multiple character lookups efficiently and with few sanity
 *  checks (such as access outside the end of the input), which keeps the
 *  tokenization code small at the cost of performance.
 * 
 *  Character data in tokens (such as identifier names and string literals)
 *  is encoded into CESU-8 format on-the-fly while parsing the token in
 *  question.  The string data is made reachable to garbage collection by
 *  placing the token-related values in value stack entries allocated for
 *  this purpose by the caller.  The characters exist in Unicode code point
 *  form only in the fixed size lookup window, which keeps character data
 *  expansion (of especially ASCII data) low.
 *
 *  Token parsing supports the full range of Unicode characters as described
 *  in the E5 specification.  Parsing has been optimized for ASCII characters
 *  because ordinary Ecmascript code consists almost entirely of ASCII
 *  characters.  Matching of complex Unicode codepoint sets (such as in the
 *  IdentifierStart and IdentifierPart productions) is optimized for size,
 *  and is done using a linear scan of a bit-packed list of ranges.  This is
 *  very slow, but should never be entered unless the source code actually
 *  contains Unicode characters.
 *
 *  Ecmascript tokenization is partially context sensitive.  First,
 *  additional future reserved words are recognized in strict mode (see E5
 *  Section 7.6.1.2).  Second, a forward slash character ('/') can be
 *  recognized either as starting a RegExp literal or as a division operator,
 *  depending on context.  The caller must provide necessary context flags
 *  when requesting a new token.
 *
 *  Future work:
 *
 *    * Make the input window a circular array to avoid copying.  This would
 *      not necessarily complicate the tokenizer much, although it would make
 *      the window fetches more expensive (one AND).
 *
 *    * Make line number tracking optional, as it consumes space.  Also, is
 *      tracking end line really useful for tokens?
 *
 *    * Add a feature flag for disabling UTF-8 decoding of input, as most
 *      source code is ASCII.  Because of Unicode escapes written in ASCII,
 *      this does not allow Unicode support to be removed from e.g.
 *      duk_unicode_is_identifier_start() nor does it allow removal of CESU-8
 *      encoding of e.g. string literals.
 *
 *    * Add a feature flag for disabling Unicode compliance of e.g. identifier
 *      names.  This allows for a build more than a kilobyte smaller, because
 *      Unicode ranges needed by duk_unicode_is_identifier_start() and
 *      duk_unicode_is_identifier_part() can be dropped.  String literals
 *      should still be allowed to contain escaped Unicode, so this still does
 *      not allow removal of CESU-8 encoding of e.g. string literals.
 *
 *    * Character lookup tables for codepoints above BMP could be stripped.
 *
 *    * Strictly speaking, E5 specification requires that source code consists
 *      of 16-bit code units, and if not, must be conceptually converted to
 *      that format first.  The current lexer processes Unicode code points
 *      and allows characters outside the BMP.  These should be converted to
 *      surrogate pairs while reading the source characters into the window,
 *      not after tokens have been formed (as is done now).  However, the fix
 *      is not trivial because two characters are decoded from one codepoint.
 *
 *    * Optimize for speed as well as size.  Large if-else ladders are slow.
 */

#include "duk_internal.h"

/*
 *  Various defines and file specific helper macros
 */

#define DUK__MAX_RE_DECESC_DIGITS     9
#define DUK__MAX_RE_QUANT_DIGITS      9   /* Does not allow e.g. 2**31-1, but one more would allow overflows of u32. */

#define DUK__LOOKUP(lex_ctx,index)    ((lex_ctx)->window[(index)])
#define DUK__ADVANCE(lex_ctx,count)   duk__advance_chars((lex_ctx), (count))
#define DUK__INITBUFFER(lex_ctx)      duk__initbuffer((lex_ctx))
#define DUK__APPENDBUFFER(lex_ctx,x)  duk__appendbuffer((lex_ctx), (int) (x))

/* whether to use macros or helper function depends on call count */
#define DUK__ISDIGIT(x)          ((x) >= '0' && (x) <= '9')
#define DUK__ISHEXDIGIT(x)       duk__is_hex_digit((x))
#define DUK__ISOCTDIGIT(x)       ((x) >= '0' && (x) <= '7')
#define DUK__ISDIGIT03(x)        ((x) >= '0' && (x) <= '3')
#define DUK__ISDIGIT47(x)        ((x) >= '4' && (x) <= '7')

/* lookup shorthands (note: assume context variable is named 'lex_ctx') */
#define DUK__L0()  DUK__LOOKUP(lex_ctx, 0)
#define DUK__L1()  DUK__LOOKUP(lex_ctx, 1)
#define DUK__L2()  DUK__LOOKUP(lex_ctx, 2)
#define DUK__L3()  DUK__LOOKUP(lex_ctx, 3)
#define DUK__L4()  DUK__LOOKUP(lex_ctx, 4)
#define DUK__L5()  DUK__LOOKUP(lex_ctx, 5)

/* packed advance/token number macro used by multiple functions */
#define DUK__ADVTOK(adv,tok)  (((adv) << 8) + (tok))

/*
 *  Read a character from the window leading edge and update the line counter.
 *
 *  Decodes UTF-8/CESU-8 leniently with support for code points from U+0000 to
 *  U+10FFFF, causing an error if the input is unparseable.  Leniency means:
 *
 *    * Unicode code point validation is intentionally not performed,
 *      except to check that the codepoint does not exceed 0x10ffff.
 *
 *    * In particular, surrogate pairs are allowed and not combined, which
 *      allows source files to represent all SourceCharacters with CESU-8.
 *      Broken surrogate pairs are allowed, as Ecmascript does not mandate
 *      their validation.
 *
 *    * Allow non-shortest UTF-8 encodings.
 *
 *  Leniency here causes few security concerns because all character data is
 *  decoded into Unicode codepoints before lexer processing, and is then
 *  re-encoded into CESU-8.  The source can be parsed as strict UTF-8 with
 *  a compiler option.  However, Ecmascript source characters include -all-
 *  16-bit unsigned integer codepoints, so leniency seems to be appropriate.
 *
 *  Note that codepoints above the BMP are not strictly SourceCharacters,
 *  but the lexer still accepts them as such.  Before ending up in a string
 *  or an identifier name, codepoints above BMP are converted into surrogate
 *  pairs and then CESU-8 encoded, resulting in 16-bit Unicode data as
 *  expected by Ecmascript.
 *
 *  An alternative approach to dealing with invalid or partial sequences
 *  would be to skip them and replace them with e.g. the Unicode replacement
 *  character U+FFFD.  This has limited utility because a replacement character
 *  will most likely cause a parse error, unless it occurs inside a string.
 *  Further, Ecmascript source is typically pure ASCII.
 *
 *  See:
 *
 *     http://en.wikipedia.org/wiki/UTF-8
 *     http://en.wikipedia.org/wiki/CESU-8
 *     http://tools.ietf.org/html/rfc3629
 *     http://en.wikipedia.org/wiki/UTF-8#Invalid_byte_sequences
 *
 *  Future work:
 *
 *    * Reject other invalid Unicode sequences (see Wikipedia entry for examples)
 *      in strict UTF-8 mode.
 * 
 *    * Size optimize.  An attempt to use a 16-byte lookup table for the first
 *      byte resulted in a code increase though.
 *
 *    * Is checking against maximum 0x10ffff really useful?  4-byte encoding
 *      imposes a certain limit anyway.
 */

static int duk__read_char(duk_lexer_ctx *lex_ctx) {
	/* attempting to reduce size of 'len' and/or 'i' resulted in larger code */
	int x;
	int len;
	int i;
	duk_uint8_t *p;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
	int mincp;
#endif

	if (lex_ctx->input_offset >= lex_ctx->input_length) {
		return -1;
	}

	DUK_ASSERT(lex_ctx->input_offset >= 0);
	DUK_ASSERT(lex_ctx->input_offset < lex_ctx->input_length);
	p = lex_ctx->input + lex_ctx->input_offset;
	x = (int) *p++;

	if (x < 0x80) {
		/* 0xxx xxxx -> fast path */
		len = 1;
		goto fastpath;
	} else if (x < 0xc0) {
		/* 10xx xxxx -> invalid */
		goto error;
	} else if (x < 0xe0) {
		/* 110x xxxx   10xx xxxx  */
		len = 2;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x80;
#endif
		x = x & 0x1f;
	} else if (x < 0xf0) {
		/* 1110 xxxx   10xx xxxx   10xx xxxx */
		len = 3;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x800;
#endif
		x = x & 0x0f;
	} else if (x < 0xf8) {
		/* 1111 0xxx   10xx xxxx   10xx xxxx   10xx xxxx */
		len = 4;
#ifdef DUK_USE_STRICT_UTF8_SOURCE
		mincp = 0x10000;
#endif
		x = x & 0x07;
{'fraction_non_alphanumeric': 0.07876998495905521, 'fraction_numerical': 0.016990696897108797, 'mean_word_length': 3.388169151796627, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5675285', 'n_tokens_mistral': 5796, 'n_tokens_neox': 5464, 'n_words': 2264}