#include <stdbool.h>

#include <Python.h>

#include "tokenizer.h"

#include "pegen.h"

#include "string_parser.h"

static int

warn_invalid_escape_sequence(Parser *p, unsigned char first_invalid_escape_char, Token *t)

{

PyObject *msg =

PyUnicode_FromFormat("invalid escape sequence \\%c", first_invalid_escape_char);

if (msg == NULL) {

return -1;

}

if (PyErr_WarnExplicitObject(PyExc_DeprecationWarning, msg, p->tok->filename,

t->lineno, NULL, NULL) < 0) {

if (PyErr_ExceptionMatches(PyExc_DeprecationWarning)) {

/* Replace the DeprecationWarning exception with a SyntaxError

PyErr_Clear();

/* This is needed, in order for the SyntaxError to point to the token t,

p->known_err_token = t;

RAISE_SYNTAX_ERROR("invalid escape sequence \\%c", first_invalid_escape_char);

}

Py_DECREF(msg);

return -1;

}

Py_DECREF(msg);

return 0;

}

static PyObject *

decode_utf8(const char **sPtr, const char *end)

{

const char *s;

const char *t;

t = s = *sPtr;

while (s < end && (*s & 0x80)) {

s++;

}

*sPtr = s;

return PyUnicode_DecodeUTF8(t, s - t, NULL);

}

static PyObject *

decode_unicode_with_escapes(Parser *parser, const char *s, size_t len, Token *t)

{

PyObject *v;

PyObject *u;

char *buf;

char *p;

const char *end;

/* check for integer overflow */

if (len > SIZE_MAX / 6) {

return NULL;

}

/* "ä" (2 bytes) may become "\U000000E4" (10 bytes), or 1:5

u = PyBytes_FromStringAndSize((char *)NULL, len * 6);

if (u == NULL) {

return NULL;

}

p = buf = PyBytes_AsString(u);

if (p == NULL) {

return NULL;

}

end = s + len;

while (s < end) {

if (*s == '\\') {

*p++ = *s++;

if (s >= end || *s & 0x80) {

strcpy(p, "u005c");

p += 5;

if (s >= end) {

break;

}

}

}

if (*s & 0x80) {

PyObject *w;

int kind;

void *data;

Py_ssize_t w_len;

Py_ssize_t i;

w = decode_utf8(&s, end);

if (w == NULL) {

Py_DECREF(u);

return NULL;

}

kind = PyUnicode_KIND(w);

data = PyUnicode_DATA(w);

w_len = PyUnicode_GET_LENGTH(w);

for (i = 0; i < w_len; i++) {

Py_UCS4 chr = PyUnicode_READ(kind, data, i);

sprintf(p, "\\U%08x", chr);

p += 10;

}

/* Should be impossible to overflow */

assert(p - buf <= PyBytes_GET_SIZE(u));

Py_DECREF(w);

}

else {

*p++ = *s++;

}

}

len = p - buf;

s = buf;

const char *first_invalid_escape;

v = _PyUnicode_DecodeUnicodeEscape(s, len, NULL, &first_invalid_escape);

if (v != NULL && first_invalid_escape != NULL) {

if (warn_invalid_escape_sequence(parser, *first_invalid_escape, t) < 0) {

/* We have not decref u before because first_invalid_escape points

Py_XDECREF(u);

Py_DECREF(v);

return NULL;

}

}

Py_XDECREF(u);

return v;

}

static PyObject *

decode_bytes_with_escapes(Parser *p, const char *s, Py_ssize_t len, Token *t)

{

const char *first_invalid_escape;

PyObject *result = _PyBytes_DecodeEscape(s, len, NULL, &first_invalid_escape);

if (result == NULL) {

return NULL;

}

if (first_invalid_escape != NULL) {

if (warn_invalid_escape_sequence(p, *first_invalid_escape, t) < 0) {

Py_DECREF(result);

return NULL;

}

}

return result;

}

_PyPegen_parsestr(Parser *p, int *bytesmode, int *rawmode, PyObject **result,

const char **fstr, Py_ssize_t *fstrlen, Token *t)

{

const char *s = PyBytes_AsString(t->bytes);

if (s == NULL) {

return -1;

}

size_t len;

int quote = Py_CHARMASK(*s);

int fmode = 0;

*bytesmode = 0;

*rawmode = 0;

*result = NULL;

*fstr = NULL;

if (Py_ISALPHA(quote)) {

while (!*bytesmode || !*rawmode) {

if (quote == 'b' || quote == 'B') {

quote =(unsigned char)*++s;

*bytesmode = 1;

}

else if (quote == 'u' || quote == 'U') {

quote = (unsigned char)*++s;

}

else if (quote == 'r' || quote == 'R') {

quote = (unsigned char)*++s;

*rawmode = 1;

}

else if (quote == 'f' || quote == 'F') {

quote = (unsigned char)*++s;

fmode = 1;

}

else {

break;

}

}

}

/* fstrings are only allowed in Python 3.6 and greater */

if (fmode && p->feature_version < 6) {

p->error_indicator = 1;

RAISE_SYNTAX_ERROR("Format strings are only supported in Python 3.6 and greater");

return -1;

}

if (fmode && *bytesmode) {

PyErr_BadInternalCall();

return -1;

}

if (quote != '\'' && quote != '\"') {

PyErr_BadInternalCall();

return -1;

}

/* Skip the leading quote char. */

s++;

len = strlen(s);

if (len > INT_MAX) {

PyErr_SetString(PyExc_OverflowError, "string to parse is too long");

return -1;

}

if (s[--len] != quote) {

/* Last quote char must match the first. */

PyErr_BadInternalCall();

return -1;

}

if (len >= 4 && s[0] == quote && s[1] == quote) {

/* A triple quoted string. We've already skipped one quote at

s += 2;

len -= 2;

/* And check that the last two match. */

if (s[--len] != quote || s[--len] != quote) {

PyErr_BadInternalCall();

return -1;

}

}

if (fmode) {

/* Just return the bytes. The caller will parse the resulting

*fstr = s;

*fstrlen = len;

return 0;

}

/* Not an f-string. */

/* Avoid invoking escape decoding routines if possible. */

*rawmode = *rawmode || strchr(s, '\\') == NULL;

if (*bytesmode) {

/* Disallow non-ASCII characters. */

const char *ch;

for (ch = s; *ch; ch++) {

if (Py_CHARMASK(*ch) >= 0x80) {

RAISE_SYNTAX_ERROR(

"bytes can only contain ASCII "

"literal characters");

return -1;

}

}

if (*rawmode) {

*result = PyBytes_FromStringAndSize(s, len);

}

else {

*result = decode_bytes_with_escapes(p, s, len, t);

}

}

else {

if (*rawmode) {

*result = PyUnicode_DecodeUTF8Stateful(s, len, NULL, NULL);

}

else {

*result = decode_unicode_with_escapes(p, s, len, t);

}

}

return *result == NULL ? -1 : 0;

}

static bool

fstring_find_expr_location(Token *parent, char *expr_str, int *p_lines, int *p_cols)

{

*p_lines = 0;

*p_cols = 0;

if (parent && parent->bytes) {

char *parent_str = PyBytes_AsString(parent->bytes);

if (!parent_str) {

return false;

}

char *substr = strstr(parent_str, expr_str);

if (substr) {

// The following is needed, in order to correctly shift the column

// offset, in the case that (disregarding any whitespace) a newline

// immediately follows the opening curly brace of the fstring expression.

bool newline_after_brace = 1;

char *start = substr + 1;

while (start && *start != '}' && *start != '\n') {

if (*start != ' ' && *start != '\t' && *start != '\f') {

newline_after_brace = 0;

break;

}

start++;

}

// Account for the characters from the last newline character to our

// left until the beginning of substr.

if (!newline_after_brace) {

start = substr;

while (start > parent_str && *start != '\n') {

start--;

}

*p_cols += (int)(substr - start);

}

/* adjust the start based on the number of newlines encountered

for (char* p = parent_str; p < substr; p++) {

if (*p == '\n') {

(*p_lines)++;

}

}

}

}

return true;

}

static expr_ty

fstring_compile_expr(Parser *p, const char *expr_start, const char *expr_end,

Token *t)

{

expr_ty expr = NULL;

char *str;

Py_ssize_t len;

const char *s;

expr_ty result = NULL;

assert(expr_end >= expr_start);

assert(*(expr_start-1) == '{');

assert(*expr_end == '}' || *expr_end == '!' || *expr_end == ':' ||

*expr_end == '=');

/* If the substring is all whitespace, it's an error. We need to catch this

for (s = expr_start; s != expr_end; s++) {

char c = *s;

/* The Python parser ignores only the following whitespace

if (!(c == ' ' || c == '\t' || c == '\n' || c == '\f')) {

break;

}

}

if (s == expr_end) {

RAISE_SYNTAX_ERROR("f-string: empty expression not allowed");

return NULL;

}

len = expr_end - expr_start;

/* Allocate 3 extra bytes: open paren, close paren, null byte. */

str = PyMem_Malloc(len + 3);

if (str == NULL) {

PyErr_NoMemory();

return NULL;

}

// The call to fstring_find_expr_location is responsible for finding the column offset

// the generated AST nodes need to be shifted to the right, which is equal to the number

// of the f-string characters before the expression starts. In order to correctly compute

// this offset, strstr gets called in fstring_find_expr_location which only succeeds

// if curly braces appear before and after the f-string expression (exactly like they do

// in the f-string itself), hence the following lines.

str[0] = '{';

memcpy(str+1, expr_start, len);

str[len+1] = '}';

str[len+2] = 0;

int lines, cols;

if (!fstring_find_expr_location(t, str, &lines, &cols)) {

PyMem_Free(str);

return NULL;

}

// The parentheses are needed in order to allow for leading whitespace within

// the f-string expression. This consequently gets parsed as a group (see the

// group rule in python.gram).

str[0] = '(';

str[len+1] = ')';

struct tok_state* tok = PyTokenizer_FromString(str, 1);

if (tok == NULL) {

PyMem_Free(str);

return NULL;

}

Py_INCREF(p->tok->filename);

tok->filename = p->tok->filename;

Parser *p2 = _PyPegen_Parser_New(tok, Py_fstring_input, p->flags, p->feature_version,

NULL, p->arena);

p2->starting_lineno = t->lineno + lines - 1;

p2->starting_col_offset = t->col_offset + cols;

expr = _PyPegen_run_parser(p2);

if (expr == NULL) {

goto exit;

}

result = expr;

exit:

PyMem_Free(str);

_PyPegen_Parser_Free(p2);

PyTokenizer_Free(tok);

return result;

}

static int

fstring_find_literal(Parser *p, const char **str, const char *end, int raw,

PyObject **literal, int recurse_lvl, Token *t)

{

/* Get any literal string. It ends when we hit an un-doubled left

const char *s = *str;

const char *literal_start = s;

int result = 0;

assert(*literal == NULL);

while (s < end) {

char ch = *s++;

if (!raw && ch == '\\' && s < end) {

ch = *s++;

if (ch == 'N') {

if (s < end && *s++ == '{') {

while (s < end && *s++ != '}') {

}

continue;

}

break;

}

if (ch == '{' && warn_invalid_escape_sequence(p, ch, t) < 0) {

return -1;

}

}

if (ch == '{' || ch == '}') {

/* Check for doubled braces, but only at the top level. If

if (recurse_lvl == 0) {

if (s < end && *s == ch) {

/* We're going to tell the caller that the literal ends

*str = s + 1;

result = 1;

goto done;

}

/* Where a single '{' is the start of a new expression, a

if (ch == '}') {

*str = s - 1;

RAISE_SYNTAX_ERROR("f-string: single '}' is not allowed");

return -1;

}

}

/* We're either at a '{', which means we're starting another

s--;

break;

}

}

*str = s;

assert(s <= end);

assert(s == end || *s == '{' || *s == '}');

done:

if (literal_start != s) {

if (raw) {

*literal = PyUnicode_DecodeUTF8Stateful(literal_start,

s - literal_start,

NULL, NULL);

} else {

*literal = decode_unicode_with_escapes(p, literal_start,

s - literal_start, t);

}

if (!*literal) {

return -1;

}

}

return result;

}

static expr_ty

fstring_parse(Parser *p, const char **str, const char *end, int raw, int recurse_lvl,

Token *first_token, Token* t, Token *last_token);

static int

fstring_find_expr(Parser *p, const char **str, const char *end, int raw, int recurse_lvl,

PyObject **expr_text, expr_ty *expression, Token *first_token,

Token *t, Token *last_token)

{

/* Return -1 on error, else 0. */

const char *expr_start;

const char *expr_end;

expr_ty simple_expression;

expr_ty format_spec = NULL; /* Optional format specifier. */

int conversion = -1; /* The conversion char. Use default if not

/* 0 if we're not in a string, else the quote char we're trying to

char quote_char = 0;

/* If we're inside a string, 1=normal, 3=triple-quoted. */

int string_type = 0;

/* Keep track of nesting level for braces/parens/brackets in

Py_ssize_t nested_depth = 0;

char parenstack[MAXLEVEL];

*expr_text = NULL;

/* Can only nest one level deep. */

if (recurse_lvl >= 2) {

RAISE_SYNTAX_ERROR("f-string: expressions nested too deeply");

goto error;

}

/* The first char must be a left brace, or we wouldn't have gotten

assert(**str == '{');

*str += 1;

expr_start = *str;

for (; *str < end; (*str)++) {

char ch;

/* Loop invariants. */

assert(nested_depth >= 0);

assert(*str >= expr_start && *str < end);

if (quote_char) {

assert(string_type == 1 || string_type == 3);

} else {

assert(string_type == 0);

}

ch = **str;

/* Nowhere inside an expression is a backslash allowed. */

if (ch == '\\') {

/* Error: can't include a backslash character, inside

RAISE_SYNTAX_ERROR(

"f-string expression part "

"cannot include a backslash");

goto error;

}

if (quote_char) {

/* We're inside a string. See if we're at the end. */

/* This code needs to implement the same non-error logic

if (ch == quote_char) {

/* Does this match the string_type (single or triple

if (string_type == 3) {

if (*str+2 < end && *(*str+1) == ch && *(*str+2) == ch) {

/* We're at the end of a triple quoted string. */

*str += 2;

string_type = 0;

quote_char = 0;

continue;

}

} else {

/* We're at the end of a normal string. */

quote_char = 0;

string_type = 0;

continue;

}

}

} else if (ch == '\'' || ch == '"') {

/* Is this a triple quoted string? */

if (*str+2 < end && *(*str+1) == ch && *(*str+2) == ch) {

string_type = 3;

*str += 2;

} else {

/* Start of a normal string. */

string_type = 1;

}

/* Start looking for the end of the string. */

quote_char = ch;

} else if (ch == '[' || ch == '{' || ch == '(') {

if (nested_depth >= MAXLEVEL) {

RAISE_SYNTAX_ERROR("f-string: too many nested parenthesis");

goto error;

}

parenstack[nested_depth] = ch;

nested_depth++;

} else if (ch == '#') {

/* Error: can't include a comment character, inside parens

RAISE_SYNTAX_ERROR("f-string expression part cannot include '#'");

goto error;

} else if (nested_depth == 0 &&

(ch == '!' || ch == ':' || ch == '}' ||

ch == '=' || ch == '>' || ch == '<')) {

/* See if there's a next character. */

if (*str+1 < end) {

char next = *(*str+1);

/* For "!=". since '=' is not an allowed conversion character,

if ((ch == '!' && next == '=') || /* != */

(ch == '=' && next == '=') || /* == */

(ch == '<' && next == '=') || /* <= */

(ch == '>' && next == '=') /* >= */

) {

*str += 1;

continue;

}

/* Don't get out of the loop for these, if they're single

if (ch == '>' || ch == '<') {

continue;

}

}

/* Normal way out of this loop. */

break;

} else if (ch == ']' || ch == '}' || ch == ')') {

if (!nested_depth) {

RAISE_SYNTAX_ERROR("f-string: unmatched '%c'", ch);

goto error;

}

nested_depth--;

int opening = (unsigned char)parenstack[nested_depth];

if (!((opening == '(' && ch == ')') ||

(opening == '[' && ch == ']') ||

(opening == '{' && ch == '}')))

{

RAISE_SYNTAX_ERROR(

"f-string: closing parenthesis '%c' "

"does not match opening parenthesis '%c'",

ch, opening);

goto error;

}

} else {

/* Just consume this char and loop around. */

}

}

expr_end = *str;

/* If we leave this loop in a string or with mismatched parens, we

if (quote_char) {

RAISE_SYNTAX_ERROR("f-string: unterminated string");

goto error;

}

if (nested_depth) {

int opening = (unsigned char)parenstack[nested_depth - 1];

RAISE_SYNTAX_ERROR("f-string: unmatched '%c'", opening);

goto error;

}

if (*str >= end) {

goto unexpected_end_of_string;

}

/* Compile the expression as soon as possible, so we show errors

simple_expression = fstring_compile_expr(p, expr_start, expr_end, t);

if (!simple_expression) {

goto error;

}

/* Check for =, which puts the text value of the expression in

if (**str == '=') {

if (p->feature_version < 8) {

RAISE_SYNTAX_ERROR("f-string: self documenting expressions are "

"only supported in Python 3.8 and greater");

goto error;

}

*str += 1;

/* Skip over ASCII whitespace. No need to test for end of string

while (Py_ISSPACE(**str)) {

*str += 1;

}

/* Set *expr_text to the text of the expression. */

*expr_text = PyUnicode_FromStringAndSize(expr_start, *str-expr_start);

if (!*expr_text) {

goto error;

}

}

/* Check for a conversion char, if present. */

if (**str == '!') {

*str += 1;

if (*str >= end) {

goto unexpected_end_of_string;

}

conversion = (unsigned char)**str;

*str += 1;

/* Validate the conversion. */

if (!(conversion == 's' || conversion == 'r' || conversion == 'a')) {

RAISE_SYNTAX_ERROR(

"f-string: invalid conversion character: "

"expected 's', 'r', or 'a'");

goto error;

}

}

/* Check for the format spec, if present. */

if (*str >= end) {

goto unexpected_end_of_string;

}

if (**str == ':') {

*str += 1;

if (*str >= end) {

goto unexpected_end_of_string;

}

/* Parse the format spec. */

format_spec = fstring_parse(p, str, end, raw, recurse_lvl+1,

first_token, t, last_token);

if (!format_spec) {

goto error;

}

}

if (*str >= end || **str != '}') {

goto unexpected_end_of_string;

}

/* We're at a right brace. Consume it. */

assert(*str < end);

assert(**str == '}');

*str += 1;

/* If we're in = mode (detected by non-NULL expr_text), and have no format

if (*expr_text && format_spec == NULL && conversion == -1) {

conversion = 'r';

}

/* And now create the FormattedValue node that represents this

//TODO: Fix this

*expression = _PyAST_FormattedValue(simple_expression, conversion,

format_spec, first_token->lineno,

first_token->col_offset,

last_token->end_lineno,

last_token->end_col_offset, p->arena);

if (!*expression) {

goto error;

}

return 0;

unexpected_end_of_string:

RAISE_SYNTAX_ERROR("f-string: expecting '}'");

/* Falls through to error. */

error:

Py_XDECREF(*expr_text);

return -1;

}

static int

fstring_find_literal_and_expr(Parser *p, const char **str, const char *end, int raw,

int recurse_lvl, PyObject **literal,

PyObject **expr_text, expr_ty *expression,

Token *first_token, Token *t, Token *last_token)

{

int result;

assert(*literal == NULL && *expression == NULL);

/* Get any literal string. */

result = fstring_find_literal(p, str, end, raw, literal, recurse_lvl, t);

if (result < 0) {

goto error;

}

assert(result == 0 || result == 1);

if (result == 1) {

/* We have a literal, but don't look at the expression. */

return 1;

}

if (*str >= end || **str == '}') {

/* We're at the end of the string or the end of a nested

return 0;

}

/* We must now be the start of an expression, on a '{'. */

assert(**str == '{');

if (fstring_find_expr(p, str, end, raw, recurse_lvl, expr_text,

expression, first_token, t, last_token) < 0) {

goto error;

}

return 0;

error:

Py_CLEAR(*literal);

return -1;

}

#ifdef NDEBUG

#define ExprList_check_invariants(l)

static void

ExprList_check_invariants(ExprList *l)

{

/* Check our invariants. Make sure this object is "live", and

assert(l->size >= 0);

assert(l->p != NULL);

if (l->size <= EXPRLIST_N_CACHED) {

assert(l->data == l->p);

}

}

static void

ExprList_Init(ExprList *l)

{

l->allocated = EXPRLIST_N_CACHED;

l->size = 0;

/* Until we start allocating dynamically, p points to data. */

l->p = l->data;

ExprList_check_invariants(l);

}

static int

ExprList_Append(ExprList *l, expr_ty exp)

{

ExprList_check_invariants(l);

if (l->size >= l->allocated) {

/* We need to alloc (or realloc) the memory. */

Py_ssize_t new_size = l->allocated * 2;

/* See if we've ever allocated anything dynamically. */

if (l->p == l->data) {

Py_ssize_t i;

/* We're still using the cached data. Switch to

l->p = PyMem_Malloc(sizeof(expr_ty) * new_size);

if (!l->p) {

return -1;

}

/* Copy the cached data into the new buffer. */

for (i = 0; i < l->size; i++) {

l->p[i] = l->data[i];

}

} else {

/* Just realloc. */

expr_ty *tmp = PyMem_Realloc(l->p, sizeof(expr_ty) * new_size);

if (!tmp) {

PyMem_Free(l->p);

l->p = NULL;

return -1;

}

l->p = tmp;

}

l->allocated = new_size;

assert(l->allocated == 2 * l->size);

}

l->p[l->size++] = exp;

ExprList_check_invariants(l);

return 0;

}

static void

ExprList_Dealloc(ExprList *l)

{

ExprList_check_invariants(l);

/* If there's been an error, or we've never dynamically allocated,

if (!l->p || l->p == l->data) {

/* Do nothing. */

} else {

/* We have dynamically allocated. Free the memory. */

PyMem_Free(l->p);

}

l->p = NULL;

l->size = -1;

}

static asdl_expr_seq *

ExprList_Finish(ExprList *l, PyArena *arena)

{

asdl_expr_seq *seq;

ExprList_check_invariants(l);

/* Allocate the asdl_seq and copy the expressions in to it. */

seq = _Py_asdl_expr_seq_new(l->size, arena);

if (seq) {

Py_ssize_t i;

for (i = 0; i < l->size; i++) {

asdl_seq_SET(seq, i, l->p[i]);

}

}

ExprList_Dealloc(l);

return seq;

}

#ifdef NDEBUG

#define FstringParser_check_invariants(state)

static void

FstringParser_check_invariants(FstringParser *state)