/* SPDX-License-Identifier: Unlicense
 */

#include "tracetab.h"
#include "vec.h"
#include "debug.h"

#include <cassert>
#include <cerrno>
#include <cstdlib>
#include <cstring>

TraceTable::~TraceTable(void)
{
    if (_types) {
        free(_types);
    }
    if (_nodes) {
        free(_nodes);
    }
    if (_shstr) {
        free(_shstr);
    }
    _types = nullptr;
    _nodes = nullptr;
    _shstr = nullptr;
    _types_count = 0;
    _nodes_count = 0;
}

const char *const g_escape_table[256] = {
    "\\x00", "\\x01", "\\x02", "\\x03", "\\x04", "\\x05", "\\x06", "\\x07",
    "\\x08", "\\t", "\\n", "\\x0b", "\\x0c", "\\r", "\\x0e", "\\x0f", "\\x10",
    "\\x11", "\\x12", "\\x13", "\\x14", "\\x15", "\\x16", "\\x17", "\\x18",
    "\\x19", "\\x1a", "\\x1b", "\\x1c", "\\x1d", "\\x1e", "\\x1f", " ", "!",
    "\\\"", "#", "$", "%", "&", "'", "(", ")", "*", "+", ",", "-", ".", "/", "0",
    "1", "2", "3", "4", "5", "6", "7", "8", "9", ":", ";", "\\<", "=", "\\>", "?",
    "@", "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",
    "{", "|", "}", "~", "\\x7f", "\\x80", "\\x81", "\\x82", "\\x83", "\\x84",
    "\\x85", "\\x86", "\\x87", "\\x88", "\\x89", "\\x8a", "\\x8b", "\\x8c",
    "\\x8d", "\\x8e", "\\x8f", "\\x90", "\\x91", "\\x92", "\\x93", "\\x94",
    "\\x95", "\\x96", "\\x97", "\\x98", "\\x99", "\\x9a", "\\x9b", "\\x9c",
    "\\x9d", "\\x9e", "\\x9f", "\\xa0", "\\xa1", "\\xa2", "\\xa3", "\\xa4",
    "\\xa5", "\\xa6", "\\xa7", "\\xa8", "\\xa9", "\\xaa", "\\xab", "\\xac",
    "\\xad", "\\xae", "\\xaf", "\\xb0", "\\xb1", "\\xb2", "\\xb3", "\\xb4",
    "\\xb5", "\\xb6", "\\xb7", "\\xb8", "\\xb9", "\\xba", "\\xbb", "\\xbc",
    "\\xbd", "\\xbe", "\\xbf", "\\xc0", "\\xc1", "\\xc2", "\\xc3", "\\xc4",
    "\\xc5", "\\xc6", "\\xc7", "\\xc8", "\\xc9", "\\xca", "\\xcb", "\\xcc",
    "\\xcd", "\\xce", "\\xcf", "\\xd0", "\\xd1", "\\xd2", "\\xd3", "\\xd4",
    "\\xd5", "\\xd6", "\\xd7", "\\xd8", "\\xd9", "\\xda", "\\xdb", "\\xdc",
    "\\xdd", "\\xde", "\\xdf", "\\xe0", "\\xe1", "\\xe2", "\\xe3", "\\xe4",
    "\\xe5", "\\xe6", "\\xe7", "\\xe8", "\\xe9", "\\xea", "\\xeb", "\\xec",
    "\\xed", "\\xee", "\\xef", "\\xf0", "\\xf1", "\\xf2", "\\xf3", "\\xf4",
    "\\xf5", "\\xf6", "\\xf7", "\\xf8", "\\xf9", "\\xfa", "\\xfb", "\\xfc",
    "\\xfd", "\\xfe",
};

static char *escapeStr(const char *in, size_t len)
{
    char *out = nullptr;
    size_t out_size = 0;
    FILE *f = open_memstream(&out, &out_size);
    if (nullptr == f) {
        return out;
    }
    for (size_t i = 0; i < len; i++) {
        const char *escaped = g_escape_table[static_cast<unsigned char>(in[i])];
        const int res = fwrite(escaped, strlen(escaped), 1, f);
        ASSERT(res == 1), (void)res;
    }
    fclose(f);
    return out;
}

enum class TokenKind {
    /// Used to indicate end of data
    kNone = 0,
    /// Used to indicate unexpected end of data or char
    kError,
    /// "0x[0-9a-fA-f]+"
    kNumHex,
    /// "0|[1-9][0-9]*"
    kNumDec,
    /// "0[0-7]+"
    kNumOct,
    /// "0b[01]+"
    kNumBin,
    /// "[a-zA-Z_][0-9a-zA-Z_]*"
    kAlphaNum,
    /// ","
    kComma,
    /// "["
    kLBracket,
    /// "]"
    kRBracket,
    /// "#.*$"
    kComment,
    /// "\"
    kBackslash,
    /// "\n|\r|\r\n"
    kNewLine,
};

struct Token {
    using T = Token;
    using K = TokenKind;
    K kind{};
    size_t pos{}, len{};
    constexpr const char *Str() const {
        switch(kind) {
        case K::kNone: return "<None>";
        case K::kError: return "<Error>";
        case K::kNumHex: return "hexadecimal numeric";
        case K::kNumDec: return "decimal numeric";
        case K::kNumOct: return "octal numeric";
        case K::kNumBin: return "binary numeric";
        case K::kAlphaNum: return "alphanumeric";
        case K::kComma: return "`,`";
        case K::kLBracket: return "`[`";
        case K::kRBracket: return "`]`";
        case K::kComment: return "comment";
        case K::kBackslash: return "backslash";
        case K::kNewLine: return "newline";
        }
        UNREACHABLE();
        return "<undefined>";
    }
    constexpr bool IsNum() const
    {
        return kind == K::kNumHex || kind == K::kNumDec || kind == K::kNumOct || kind == K::kNumBin;
    }
    static constexpr T None(size_t pos) { return T{ K::kNone, pos, 0}; }
    static constexpr T NumHex(size_t pos, size_t len) { return T{ K::kNumHex, pos, len}; }
    static constexpr T NumDec(size_t pos, size_t len) { return T{ K::kNumDec, pos, len}; }
    static constexpr T NumOct(size_t pos, size_t len) { return T{ K::kNumOct, pos, len}; }
    static constexpr T NumBin(size_t pos, size_t len) { return T{ K::kNumBin, pos, len}; }
    static constexpr T AlphaNum(size_t pos, size_t len) { return T{ K::kAlphaNum, pos, len}; }
    static constexpr T Comma(size_t pos) { return T{ K::kComma, pos, 1}; }
    static constexpr T LBracket(size_t pos) { return T{ K::kLBracket, pos, 1}; }
    static constexpr T RBracket(size_t pos) { return T{ K::kRBracket, pos, 1}; }
    static constexpr T Comment(size_t pos, size_t len) { return T{ K::kComment, pos, len}; }
    static constexpr T Backslash(size_t pos) { return T{ K::kBackslash, pos, 1}; }
};

static const char *ParseTypeFromStr(
        const char *input, size_t len, TraceNodeKind &k, DataType &dt)
{
    struct {
        const char *str;
        DataTypeKind type;
    } data[] {
        { "blob", DataTypeKind::kBlob, },
        { "str", DataTypeKind::kStr, },
        { "strz", DataTypeKind::kStrz, },
    };
    const char *intable[] { "ptr", "u8", "u16", "u32", };
    static char err[256];
    TRACE("Token: \"%.*s\"", static_cast<int>(len), input);
    if (0 == strncmp("fn", input, len)) {
        k = TraceNodeKind::kFunction;
        return nullptr;
    } else if (0 == strncmp("pc", input, len)) {
        k = TraceNodeKind::kPc;
        return nullptr;
    }
    for (size_t i = 0; i < (sizeof data) / (sizeof *data); i++) {
        if (0 == strncmp(data[i].str, input, len)) {
            k = TraceNodeKind::kData;
            dt = DataType{ data[i].type };
            return nullptr;
        }
    }
    for (size_t i = 0; i < (sizeof intable) / (sizeof *intable); i++) {
        const char *t = intable[i];
        if (0 == strncmp(t, input, len)) {
            snprintf(
                    err, sizeof err,
                    "`%s` trace node type only allowed in a table, "
                    "use `[%s]` syntax instead", t, t);
            return err;
        }
    }
    snprintf(err, sizeof err, "unknown trace node type");
    return err;
}

static const char *ParseTypeFromToken(
        const Token &t, const char *input, TraceNodeKind &k, DataType &dt)
{
    return ParseTypeFromStr(input + t.pos, t.len, k, dt);
}

static const char *ParseTableTypeFromStr(
        const char *input, size_t len, DataType &dt)
{
    struct {
        const char *str;
        DataTypeKind type;
    } data[] {
        { "ptr", DataTypeKind::kPtr, },
        { "u32", DataTypeKind::kU32, },
        { "u16", DataTypeKind::kU16, },
        { "u8", DataTypeKind::kU8, },
    };
    static char err[256];
    TRACE("Token: \"%.*s\"", static_cast<int>(len), input);
    for (size_t i = 0; i < (sizeof data) / (sizeof *data); i++) {
        if (0 == strncmp(data[i].str, input, len)) {
            dt = DataType{ data[i].type, 1 };
            return nullptr;
        }
    }
    snprintf(err, sizeof err, "unknown table type");
    return err;
}

static const char *ParseTableTypeFromToken(
        const Token &t, const char *input, DataType &dt)
{
    return ParseTableTypeFromStr(input + t.pos, t.len, dt);
}

enum class TokenizerState {
    kFree = 0,
    kNumAmbiguous,
    kNumHexStillNoDigits,
    kNumHex,
    kNumDec,
    kNumOct,
    kNumBinStillNoDigits,
    kNumBin,
    kAlphaNum,
    kComment,
    kNewLine,
    kError,
};

struct LinePosInfo {
    size_t lineno;
    size_t col;
    size_t pos;
};

class Tokenizer {
    FILE *_errstream{};
    const char *_filename{};
    size_t _pos{}, _token_pos{};
    TokenizerState _state{};
    TokenKind handleChar(char c, bool is_last);
    TokenKind errorExpect(void);
    char lookAhead() const { return in[_pos + 1]; }
    void printError(const LinePosInfo l, size_t underline_len, const char *str);
public:
    const char *in{};
    size_t in_size{};
    Tokenizer(){}
    Tokenizer(const void *input, size_t size, FILE *errstream, const char *filename)
        : _errstream(errstream)
        , _filename(filename)
        , in(static_cast<const char *>(input))
        , in_size(size)
    {}
    Token Next()
    {
        while (_pos < in_size) {
            const char c = in[_pos];
            const TokenKind tk = handleChar(c, _pos + 1 >= in_size);
            _pos++;
            if (tk != TokenKind::kNone) {
                return Token{ tk, _token_pos, _pos - _token_pos };
            }
        }
        return Token::None(_pos);
    }
    LinePosInfo GetLinePosInfo(const size_t pos)
    {
        LinePosInfo l{};
        bool cr = false;
        for (size_t i = 0; i < pos; i++) {
            const char c = in[i];
            if (c == '\r') {
                cr = true;
                l.pos = i + 1;
                l.lineno++;
                l.col = 0;
            } else if (c == '\n') {
                if (!cr) {
                    l.lineno++;
                }
                cr = false;
                l.pos = i + 1;
                l.col = 0;
            } else {
                cr = false;
                l.col++;
            }
        }
        return l;
    }
    void PrintError(const Token& t, const char *errstr)
    {
        return printError(GetLinePosInfo(t.pos), t.len, errstr);
    }
    void PrintError(const char *errstr)
    {
        return printError(GetLinePosInfo(_pos), 1, errstr);
    }
};

const char *TokenizerStateToExpectedText(TokenizerState s)
{
    switch (s) {
    case TokenizerState::kFree:
        return "digit, alphabetic, `_`, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kNumAmbiguous:
        return "`x`, `b` or octal digit";
    case TokenizerState::kNumHexStillNoDigits:
        return "hexadecimal digit";
    case TokenizerState::kNumHex:
        return "hexadecimal digit, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kNumDec:
        return "decimal digit, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kNumOct:
        return "octal digit, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kNumBinStillNoDigits:
        return "binary digit";
    case TokenizerState::kNumBin:
        return "binary digit, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kAlphaNum:
        return "decimal digit, alphabetic, `_`, `,`, `[`, `]`, `#`, space, tab, CR or LF";
    case TokenizerState::kComment:
        UNREACHABLE();
        return "<Comment>";
    case TokenizerState::kNewLine:
        UNREACHABLE();
        return "<NewLine>";
    case TokenizerState::kError:
        UNREACHABLE();
        return "<Error>";
    }
    UNREACHABLE();
    return "<undefined>";
}

static size_t FindLineLength(const char *const str)
{
    for (size_t i = 0;; i++) {
        const char c = str[i];
        if (c == '\n' || c == '\r' || c == '\000') {
            return i;
        }
    }
    return 0;
}

void Tokenizer::printError(const LinePosInfo l, size_t underline_len, const char *err)
{
    const char *name = _filename ? _filename : "<stdin>";
    fprintf(_errstream, "%s:%zu:%zu: error: %s\n", name, l.lineno, l.col, err);
    const char *const line = in + l.pos;
    const int line_length = FindLineLength(line);
    fprintf(_errstream, "%5lu | %.*s\n", l.lineno + 1, line_length, line);
    fputs("      | ", _errstream);
    for (size_t i = 0; i < l.col; i++) {
        if (in[l.pos + i] == '\t') {
            fputc('\t', _errstream);
        } else {
            fputc(' ', _errstream);
        }
    }
    fputc('^', _errstream);
    for (size_t i = 1; i < underline_len; i++) {
        fputc('~', _errstream);
    }
    fputc('\n', _errstream);
}

TokenKind Tokenizer::errorExpect(void)
{
    _state = TokenizerState::kError;
    size_t size{};
    char *errstr{};
    FILE *memstream = open_memstream(&errstr, &size);
    if (nullptr == memstream) {
        return TokenKind::kError;
    }
    fprintf(
            memstream,
            "unexpected char `%s`, expected %s\n",
            g_escape_table[static_cast<unsigned char>(in[_pos])],
            TokenizerStateToExpectedText(_state));
    fclose(memstream);
    PrintError(errstr);
    free(errstr);
    return TokenKind::kError;
}

static constexpr bool IsSpace(char c)
{
    return c == ' ' || c == '\t';
}

static constexpr bool IsNewLine(char c)
{
    return c == '\n' || c == '\r';
}

static constexpr bool IsValidSequenceBreaker(char c)
{
    return c == ',' || c == '[' || c == ']' || c == '#' || c == '\\'
        || IsNewLine(c) || IsSpace(c);
}

static constexpr bool IsAlphabetic(char c)
{
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c == '_');
}

static constexpr bool IsAlphaNumeric(char c)
{
    return IsAlphabetic(c) || (c >= '0' && c <= '9');
}

static constexpr bool IsDecimal(char c)
{
    return (c >= '0' && c <= '9');
}

static constexpr bool IsHexadecimal(char c)
{
    return IsDecimal(c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
}

static constexpr bool IsOctal(char c)
{
    return (c >= '0' && c <= '7');
}

static constexpr bool IsBinary(char c)
{
    return c == '0' || c == '1';
}

TokenKind Tokenizer::handleChar(const char c, const bool is_last)
{
    switch (_state) {
    case TokenizerState::kFree:
        TRACE("kFree %zu", _pos);
        _token_pos = _pos;
        if (c == '\n') {
            return TokenKind::kNewLine;
        } else if (c == '\r') {
            if (is_last || '\n' != lookAhead()) {
                return TokenKind::kNewLine;
            }
            _state = TokenizerState::kNewLine;
            return TokenKind::kNone;
        } else if (c == ',') {
            return TokenKind::kComma;
        } else if (c == '[') {
            return TokenKind::kLBracket;
        } else if (c == ']') {
            return TokenKind::kRBracket;
        } else if (c == '#') {
            if (is_last || IsNewLine(lookAhead())) {
                return TokenKind::kComment;
            }
            _state = TokenizerState::kComment;
            return TokenKind::kNone;
        } else if (c == '\\') {
            return TokenKind::kBackslash;
        } else if (c == '0') {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                return TokenKind::kNumDec;
            }
            _state = TokenizerState::kNumAmbiguous;
            return TokenKind::kNone;
        } else if (IsDecimal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                return TokenKind::kNumDec;
            }
            _state = TokenizerState::kNumDec;
            return TokenKind::kNone;
        } else if (IsAlphaNumeric(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                return TokenKind::kAlphaNum;
            }
            _state = TokenizerState::kAlphaNum;
            return TokenKind::kNone;
        } else if (IsSpace(c)) {
            // Skip
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumAmbiguous:
        TRACE("kNumAmbiguous %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (c == 'b' || c == 'B') {
            _state = TokenizerState::kNumBinStillNoDigits;
            return TokenKind::kNone;
        } else if (c == 'x' || c == 'X') {
            _state = TokenizerState::kNumHexStillNoDigits;
            return TokenKind::kNone;
        } else if (IsOctal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumOct;
            }
            _state = TokenizerState::kNumOct;
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumHexStillNoDigits:
        TRACE("kNumHexStillNoDigits %zu", _pos);
        if (IsHexadecimal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumHex;
            }
            _state = TokenizerState::kNumHex;
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumHex:
        TRACE("kNumHex %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (IsHexadecimal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumHex;
            }
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumDec:
        TRACE("kNumDec %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (IsDecimal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumDec;
            }
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumOct:
        TRACE("kNumOct %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (IsOctal(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumOct;
            }
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumBinStillNoDigits:
        TRACE("kNumBinStillNoDigits %zu", _pos);
        if (IsBinary(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumBin;
            }
            _state = TokenizerState::kNumBin;
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kNumBin:
        TRACE("kNumBin %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (IsBinary(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kNumBin;
            }
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kAlphaNum:
        TRACE("kAlphaNum %zu", _pos);
        ASSERT(!IsValidSequenceBreaker(c));
        if (IsAlphaNumeric(c)) {
            if (is_last || IsValidSequenceBreaker(lookAhead())) {
                _state = TokenizerState::kFree;
                return TokenKind::kAlphaNum;
            }
            return TokenKind::kNone;
        }
        return errorExpect();
    case TokenizerState::kComment:
        TRACE("kComment %zu", _pos);
        if (is_last || IsNewLine(lookAhead())) {
            _state = TokenizerState::kFree;
            return TokenKind::kComment;
        }
        return TokenKind::kNone;
    case TokenizerState::kNewLine:
        TRACE("kNewLine %zu", _pos);
        ASSERT(c == '\n');
        _state = TokenizerState::kFree;
        return TokenKind::kNewLine;
    case TokenizerState::kError:
        TRACE("kError %zu", _pos);
        UNREACHABLE();
        return TokenKind::kNone;
    }
    UNREACHABLE();
    return TokenKind::kNone;
}

enum class ParserState {
    kAddress = 0,
    kType,
    kTableType,
    kTableTypeCountOrSep,
    kTableSep,
    kCountOrName,
    kName,
    kEscapeEndOfLine,
    kEndOfLine,
    kError,
};

enum class ParseResult {
    kOk = 0,
    kFinished,
    kError,
};

struct Statement {
    uint32_t address_value{};
    bool has_comment{};
    TraceNodeKind trace_node_kind{};
    DataType data_type{};
    uint32_t size_value{};
    size_t name_index{};
    size_t comment_index{};
};

class Parser {
    Statement _stmt;
    FILE *_shstr{};
    ParserState _state{};
    ParserState _saved_state{}; // For kEscapeEndOfLine
    TokenKind _prev_token_kind{};
    bool _error{};
    ParseResult handleToken(const Token &);
    ParseResult errorExpect(const Token &t, const char *expected);
    ParseResult error(const Token &t, const char *text);
    size_t addToShstr(const char *str, const size_t len)
    {
        if (nullptr == _shstr) {
            return false;
        }
        fflush(_shstr);
        ASSERT(shstr_size);
        const size_t index = shstr_size;
        if (len) {
            ASSERT(shstr[shstr_size - 1] == '\000'); // Make sure it is sealed
            const int res = fwrite(str, len, 1, _shstr);
            ASSERT(res == 1), (void)res;
        }
        fflush(_shstr);
        ASSERT(shstr_size);
        if (shstr[shstr_size - 1] != '\000') {
            const int res = fwrite("\000", 1, 1, _shstr);
            ASSERT(res == 1), (void) res;
        }
        return index;
    }
    size_t addToShstrRaw(const char *str, const size_t len)
    {
        if (nullptr == _shstr) {
            return false;
        }
        fflush(_shstr);
        ASSERT(shstr_size);
        const size_t index = shstr_size;
        if (len) {
            const int res = fwrite(str, len, 1, _shstr);
            ASSERT(res == 1), (void) res;
        }
        return index;
    }
    size_t addNameTokenToShstr(const Token &t)
    {
        const char *str = tokenizer.in + t.pos;
        const size_t len = t.len;
        ASSERT(len);
        if (__TRACE) {
            char *estr = escapeStr(tokenizer.in + t.pos, static_cast<int>(t.len));
            if (estr) {
                TRACE("Name token: \"%s\"", estr);
                free(estr);
            }
        }
        return addToShstr(str, len);
    }
    size_t addComment(const Token &t)
    {
        const char *str = tokenizer.in + t.pos + 1;
        const size_t len = t.len - 1;
        ASSERT(len);
        if (__TRACE) {
            char *estr = escapeStr(tokenizer.in + t.pos, static_cast<int>(t.len));
            if (estr) {
                TRACE("Comment token: \"%s\"", estr);
                free(estr);
            }
        }
        return addToShstrRaw(str, len);
    }
    void appendCommentNewline(void)
    {
        // Newlines are simulated instead of using original ones, because it is
        // easier to split multiline comment when printing if newlines used are
        // uniform (only "\n"), when original ones may be mixed, i.e. "\r\n",
        // "\n" and even "\r" inside a single multiline comment.
        addToShstrRaw("\n", (sizeof "\n") - 1);
    }
    void sealComment(void) { addToShstr(nullptr, 0); }
    void addTraceNode(Statement &&stmt)
    {
        nodes.PushBack(TraceNode{
                stmt.trace_node_kind,
                stmt.data_type,
                stmt.size_value,
                stmt.address_value,
                stmt.name_index,
                stmt.comment_index,
                });
        stmt = Statement();
    }
public:
    Tokenizer tokenizer{};
    Vec<DataType> types;
    Vec<TraceNode> nodes;
    char *shstr{};
    size_t shstr_size{};
    Parser(const void *input, size_t size, FILE *errstream, const char *filename)
        : _shstr(open_memstream(&shstr, &shstr_size))
        , tokenizer(input, size, errstream, filename)
    {
        // Write a single zero so any index 0 name or comment will point to it.
        const int res = fwrite("\000", 1, 1, _shstr);
        ASSERT(res == 1), (void) res;
    }
    ~Parser()
    {
        if (_shstr) {
            fclose(_shstr);
            _shstr = nullptr;
        }
    }
    ParseResult Parse(void)
    {
        ParseResult res{};
        do {
            const auto token = tokenizer.Next();
            TRACE("%s", token.Str());
            res = handleToken(token);
            _prev_token_kind = token.kind;
        } while (ParseResult::kOk == res);
        if (_shstr) {
            fclose(_shstr);
            _shstr = nullptr;
        }
        return _error ? ParseResult::kError : res;
    }
};

ParseResult Parser::errorExpect(const Token &t, const char *expected)
{
    _state = ParserState::kError;
    _error = true;
    size_t size{};
    char *errstr{};
    FILE *memstream = open_memstream(&errstr, &size);
    if (nullptr == memstream) {
        return ParseResult::kOk;
    }
    fprintf(
            memstream,
            "unexpected %s, expected %s",
            t.Str(), expected);
    fclose(memstream);
    tokenizer.PrintError(t, errstr);
    free(errstr);
    return ParseResult::kOk;
}

ParseResult Parser::error(const Token &t, const char *errstr)
{
    _state = ParserState::kError;
    tokenizer.PrintError(t, errstr);
    return ParseResult::kOk;
}

static bool ParseNumeric(const char *str, size_t len, uint32_t &value)
{
    // No need to thoroughly validate the number here, because we trust and
    // heavily rely on the tokenizer getting it right.
    if (len < 1) {
        return false;
    }
    errno = 0;
    unsigned long v = 0;
    if (str[0] == '0' && len > 2 && (str[1] == 'b' || str[1] == 'B')) {
        v = strtoul(str + 2, nullptr, 2);
    } else {
        v = strtoul(str, nullptr, 0);
    }
    if (0 == v && errno) {
        return false;
    }
    return value = v, true;
}

static bool IsEndOfStatement(const TokenKind k)
{
    return k == TokenKind::kComment || k == TokenKind::kNewLine || k == TokenKind::kNone;
}

ParseResult Parser::handleToken(const Token &t)
{
    // The trace node description line may be broken in multilpe lines at any
    // point using the backslash '\' symbol.
    if (t.kind == TokenKind::kBackslash && _state != ParserState::kEscapeEndOfLine) {
        _saved_state = _state;
        _state = ParserState::kEscapeEndOfLine;
        return ParseResult::kOk;
    }
    switch (_state) {
    case ParserState::kAddress:
        if (t.kind == TokenKind::kComment) {
            ASSERT(t.len);
            if (_stmt.has_comment) {
                appendCommentNewline();
                addComment(t);
            } else {
                _stmt.comment_index = addComment(t);
                _stmt.has_comment = true;
            }
            return ParseResult::kOk;
        } if (t.IsNum()) {
            if (false == ParseNumeric(tokenizer.in + t.pos, t.len, _stmt.address_value)) {
                return error(t, "number is too big");
            }
            sealComment();
            _state = ParserState::kType;
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            ASSERT(t.kind != TokenKind::kComment);
            if (t.kind == TokenKind::kNone) {
                sealComment();
            }
            if (t.kind == TokenKind::kNewLine && _prev_token_kind == TokenKind::kNewLine) {
                // An empty line separating comments means that a comment above it
                // does not belong to any trace node statement, hence we should
                // reset the heading comment parsing state and seal what has
                // been parsed so far.
                _stmt.has_comment = false;
                // It is easier to just seal the string than undo what has been
                // written to it so far.
                sealComment();
            }
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return errorExpect(t, "any numeric token");
    case ParserState::kType:
        if (t.kind == TokenKind::kAlphaNum) {
            const char *err = ParseTypeFromToken(
                    t, tokenizer.in, _stmt.trace_node_kind, _stmt.data_type);
            if (err) {
                return error(t, err);
            }
            _state = ParserState::kCountOrName;
            return ParseResult::kOk;
        } else if (t.kind == TokenKind::kLBracket) {
            _stmt.trace_node_kind = TraceNodeKind::kData;
            _stmt.data_type = DataType{ DataTypeKind::kTable, 0, types.Size() };
            _state = ParserState::kTableType;
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            addTraceNode(static_cast<Statement &&>(_stmt));
            _state = ParserState::kAddress;
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return errorExpect(t, "alphanumeric token");
    case ParserState::kTableType:
        if (t.kind == TokenKind::kAlphaNum) {
            DataType data_type{};
            const char *err = ParseTableTypeFromToken(t, tokenizer.in, data_type);
            if (err) {
                return error(t, err);
            }
            types.PushBack(data_type);
            _stmt.data_type.nested_num++;
            _state = ParserState::kTableTypeCountOrSep;
            return ParseResult::kOk;
        } else if (_stmt.data_type.nested_num) {
            // Allow closing bracket after comma, but only when the table
            // already contains at least a single type, i.e. empty table is not
            // allowed.
            if (t.kind == TokenKind::kRBracket) {
                _state = ParserState::kCountOrName;
                return ParseResult::kOk;
            }
            return errorExpect(t, "`]` or table type alphanumeric token, one of: `ptr`, `u32`, `u16` or `u8`");
        }
        return errorExpect(t, "table type alphanumeric token, one of: `ptr`, `u32`, `u16` or `u8`");
    case ParserState::kTableTypeCountOrSep:
        if (t.IsNum()) {
            uint32_t value{};
            if (false == ParseNumeric(tokenizer.in + t.pos, t.len, value)) {
                return error(t, "number is too big");
            }
            ASSERT(types.Size());
            types[types.Size() - 1].count = value;
            _state = ParserState::kTableSep;
            return ParseResult::kOk;
        } else if (t.kind == TokenKind::kComma) {
            _state = ParserState::kTableType;
            return ParseResult::kOk;
        } else if (_stmt.data_type.nested_num) {
            // Allow closing bracket after comma, but only when the table
            // already contains at least a single type, i.e. empty table is not
            // allowed.
            if (t.kind == TokenKind::kRBracket) {
                _state = ParserState::kCountOrName;
                return ParseResult::kOk;
            }
            return errorExpect(t, "`]`, `,`, number or table type alphanumeric token, one of: `ptr`, `u32`, `u16` or `u8`");
        }
        return errorExpect(t, "`,`, number or table type alphanumeric token, one of: `ptr`, `u32`, `u16` or `u8`");
    case ParserState::kTableSep:
        if (t.kind == TokenKind::kComma) {
            _state = ParserState::kTableType;
            return ParseResult::kOk;
        } else if (t.kind == TokenKind::kRBracket) {
            _state = ParserState::kCountOrName;
            return ParseResult::kOk;
        }
        return errorExpect(t, "`,` or `]`");
    case ParserState::kCountOrName:
        if (t.IsNum()) {
            uint32_t value{};
            if (false == ParseNumeric(tokenizer.in + t.pos, t.len, value)) {
                return error(t, "number is too big");
            }
            if (_stmt.trace_node_kind == TraceNodeKind::kData) {
                _stmt.data_type.count = value;
                if (_stmt.data_type.kind == DataTypeKind::kTable) {
                    uint32_t table_entry_size = 0;
                    for (size_t i = 0; i < _stmt.data_type.nested_num; i++) {
                        const auto &type = types[i + _stmt.data_type.nested_idx];
                        ASSERT(type.count);
                        table_entry_size += type.count * type.BaseSize();
                    }
                    _stmt.size_value = value * table_entry_size;
                } else {
                    _stmt.size_value = _stmt.data_type.count * _stmt.data_type.BaseSize();
                }
            } else {
                _stmt.size_value = value;
            }
            _state = ParserState::kName;
            return ParseResult::kOk;
        } else if (t.kind == TokenKind::kAlphaNum) {
            _stmt.name_index = addNameTokenToShstr(t);
            // Maybe there is something that should be done with the count here
            // like setting it to 1 in case if it is kTable, but for now let's
            // just face the fact that it turns out to be zero when count field
            // is omitted and move on.
            ASSERT(0 == _stmt.size_value);
            _state = ParserState::kEndOfLine;
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            addTraceNode(static_cast<Statement &&>(_stmt));
            _state = ParserState::kAddress;
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return errorExpect(t, "any numeric token");
    case ParserState::kName:
        if (t.kind == TokenKind::kAlphaNum) {
            _stmt.name_index = addNameTokenToShstr(t);
            _state = ParserState::kEndOfLine;
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            addTraceNode(static_cast<Statement &&>(_stmt));
            _state = ParserState::kAddress;
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return errorExpect(t, "alphanumeric token");
    case ParserState::kEscapeEndOfLine:
        if (t.kind == TokenKind::kComment) {
            // Comments are allowed at the end of the line when it supposed to
            // be escaped with a backslash, but these comments don't get
            // attached to the trace node, so skip these side comments.
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            // Restore the parsing state to continue parsing the trace node
            // expression.
            _state = _saved_state;
            return ParseResult::kOk;
        }
        // But backslash may not be inserted anywhere you wish, it is only
        // allowed before newlines or comments
        return errorExpect(t, "Comment, EOF, CR, LF or CRLF");
    case ParserState::kEndOfLine:
        if (t.kind == TokenKind::kComment) {
            // Side comments are skipped
            return ParseResult::kOk;
        } else if (IsEndOfStatement(t.kind)) {
            addTraceNode(static_cast<Statement &&>(_stmt));
            _state = ParserState::kAddress;
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return errorExpect(t, "Comment, EOF, CR, LF or CRLF");
    case ParserState::kError:
        // Error recovery: just skip everything to the end of the line, but
        // honoring the escape symbol '\' (see the top of the function)
        if (IsEndOfStatement(t.kind)) {
            _stmt = Statement();
            _state = ParserState::kAddress;
            return (t.kind == TokenKind::kNone)
                ? ParseResult::kFinished : ParseResult::kOk;
        }
        return ParseResult::kOk;
    }
    UNREACHABLE();
    return ParseResult::kError;
}

bool ParseTraceData(
        TraceTable &output,
        const void *trace_data,
        size_t trace_data_size,
        FILE *errstream,
        const char *trace_file_name)
{
    Parser p(trace_data, trace_data_size, errstream, trace_file_name);
    const ParseResult res = p.Parse();
    ASSERT(res != ParseResult::kOk);
    if (ParseResult::kFinished != res) {
        return false;
    }
    const auto types_count = p.types.Size();
    const auto nodes_count = p.nodes.Size();
    const auto shstr_size = p.shstr_size;
    auto *shstr = p.shstr;
    if (shstr_size <= 1) {
        // Nothing has been written to the shstr array, because it contains only
        // a single char which is a zero, that is written before the parsing
        // even starts.
        free(shstr);
        shstr = nullptr;
    }
    output._types = p.types.Extract();
    output._types_count = types_count;
    output._nodes = p.nodes.Extract();
    output._nodes_count = nodes_count;
    output._shstr = shstr;
    return true;
}