path: root/src/parser.zig

const std = @import("std");
const opcodes = @import("opcodes.zig");

/// A symbol's value can be pure or point to a register
const SymbolValueType = enum {
    pure,
    register,
};
const SymbolValue = union {
    pure: u64,
    register: u8,
};

/// A constant can be a number of a string
const ConstantType = enum {
    number,
    string,
};
const ConstantValue = union(ConstantType) {
    number: u64,
    string: []const u8,
};

/// The Parser reads a provided input and assembles it into MMIX object code
pub const Parser = struct {
    allocator: std.mem.Allocator,
    input: []const u8,
    location: u64,
    ch_pos: usize,
    symbols: std.StringHashMap(SymbolValue),
    object: std.ArrayList(u8),

    /// Test is a character is whitespace
    /// Note that newlines are special and not included in this implementation.
    fn isWhitespace(ch: u8) bool {
        return ch == ' ' or ch == '\t' or ch == '\r';
    }

    /// Test if a character is a letter
    /// Note that underscores are letters for the purposes of symbol recognition.
    fn isLetter(ch: u8) bool {
        return ch == '_' or (ch >= 'a' and ch <= 'z') or (ch >= 'A' and ch <= 'Z');
    }

    /// Test if a character is a decimal digit
    fn isDecimal(ch: u8) bool {
        return ch >= '0' and ch <= '9';
    }

    /// Test if a character is a hexadecimal digit
    fn isHexadecimal(ch: u8) bool {
        return isDecimal(ch) or (ch >= 'a' and ch <= 'f') or (ch >= 'A' and ch <= 'F');
    }

    /// Test if a character is a symbol character
    /// Note that all valid unicode characters larger than 126 are also valid symbol characters.
    fn isSymbolChar(ch: u8) bool {
        return isLetter(ch) or isDecimal(ch) or ch > 126;
    }

    /// Get a byte from the input at a specified location
    /// Return 0 if the requested byte is out of range
    fn getByte(self: *Parser, pos: usize) u8 {
        if (pos < self.input.len) {
            return self.input[pos];
        }
        return 0;
    }

    /// Move the cursor forward until it does not point at whitespace
    fn skipWhitespace(self: *Parser) void {
        while (isWhitespace(self.getByte(self.ch_pos))) {
            self.ch_pose += 1;
        }
    }

    /// Determine whether the cursor points at a valid integer in base 10
    /// Move the cursor past the integer and return it
    fn identifyDecimal(self: *Parser) !u64 {
        const start = self.ch_pos;
        while (isDecimal(self.getByte(self.ch_pos))) {
            self.ch_pos += 1;
        }
        const end = self.ch_pos;

        return std.fmt.parseInt(u64, self.input[start..end], 10) catch return error.NoDecimal;
    }

    /// Determine whether the cursor points at a valid integer in base 16
    /// Base 16 is identified by a number starting with #
    /// Move the cursor past the integer and return it
    fn identifyHexadecimal(self: *Parser) !u64 {
        if (self.getByte(self.ch_pos) != '#') {
            return error.NoHexadecimal;
        }

        self.ch_pos += 1;

        const start = self.ch_pos;
        while (isHexadecimal(self.getByte(self.ch_pos))) {
            self.ch_pos += 1;
        }
        const end = self.ch_pos;

        return std.fmt.parseInt(u64, self.input[start..end], 16) catch return error.NoHexadecimal;
    }

    /// Determine whether the cursor points at a valid unicode character wrapped in single quotes
    /// Move the cursor past the closing quote and return the character
    fn identifyChar(self: *Parser) ![]const u8 {
        if (self.getByte(self.ch_pos) != '\'') {
            return error.NoChar;
        }

        self.ch_pos += 1;

        const start = self.ch_pos;
        while (self.getByte(self.ch_pos) != 0 and self.getByte(self.ch_pos) != '\'') {
            self.ch_pos += 1;

            if (self.ch_pos - start > 4) {
                return error.NoChar;
            }
        }
        const end = self.ch_pos;
        self.ch_pos += 1;

        if (end <= start) {
            return error.NoChar;
        }

        const view = std.unicode.Utf8View.init(self.input[start..end]) catch return error.NoChar;
        var iter = view.iterator();
        var count: u8 = 0;
        while (iter.nextCodepoint()) |_| {
            count += 1;
            if (count > 1) {
                return error.NoChar;
            }
        }
        if (count != 1) {
            return error.NoChar;
        }

        return self.input[start..end];
    }

    /// Determine whether the cursor points at a valid string wrapped in double quotes
    /// Note that a string has at least one character in it and that it cannot have " or newlines in it
    /// Move the cursor past the string and return the string
    fn identifyString(self: *Parser) ![]const u8 {
        if (self.getByte(self.ch_pos) != '"') {
            return error.NoString;
        }

        self.ch_pos += 1;
        const start = self.ch_pos;
        while (self.getByte(self.ch_pos) != 0 and self.getByte(self.ch_pos) != '"') {
            if (self.getByte(self.ch_pos) == '\n') {
                return error.NoString;
            }
            self.ch_pos += 1;
        }
        const end = self.ch_pos;
        if (self.getByte(self.ch_pos) == '"') {
            self.ch_pos += 1;
        }

        if (end <= start) {
            return error.NoString;
        }

        return self.input[start..end];
    }

    /// Determine whether the cursor points at a valid constant
    /// The constant may be a string or a number
    /// Move the cursor past the constant and return it
    fn identifyConstant(self: *Parser) !ConstantValue {
        switch (self.getByte(self.ch_pos)) {
            '0'...'9' => {
                const number = try identifyDecimal(self);
                return ConstantValue{ .number = number };
            },
            '#' => {
                const number = try identifyHexadecimal(self);
                return ConstantValue{ .number = number };
            },
            '\'' => {
                const string = try identifyChar(self);
                return ConstantValue{ .string = string };
            },
            '"' => {
                const string = try identifyString(self);
                return ConstantValue{ .string = string };
            },
            else => return error.NoConstant,
        }
    }

    /// Determine whether the cursor points at a symbol
    /// A symbol starts with a letter and only has symbol characters after that point
    /// There is an exception that there are 30 special symbols of the form xH, xF, and xB where x is a single decimal digit
    /// Move the cursor past the symbol and return its name
    fn identifySymbol(self: *Parser) ![]const u8 {
        const start = self.ch_pos;
        if ((isLetter(self.getByte(self.ch_pos)) or self.getByte(self.ch_pos) == '_')) {
            self.ch_pos += 1;

            while (isSymbolChar(self.getByte(self.ch_pos))) {
                self.ch_pos += 1;
            }
        } else if (isDecimal(self.getByte(self.ch_pos)) and
            (self.getByte(self.ch_pos + 1) == 'H' or self.getByte(self.ch_pos + 1) == 'F' or self.getByte(self.ch_pos + 1) == 'B'))
        {
            self.ch_pos += 2;
            return self.input[self.ch_pos - 2 .. self.ch_pos];
        }
        const end = self.ch_pos;

        if (end > start) {
            return self.input[start..end];
        }

        return error.NoSymbol;
    }

    /// Determine whether the cursor points at a valid opcode or pseudo operation
    /// An opcode consists solely of symbol characters (letters and numbers in fact)
    /// Move the cursor past the opcode and return it
    fn identifyOperation(self: *Parser) !opcodes.Operation {
        const start = self.ch_pos;
        while (isSymbolChar(self.getByte(self.ch_pos))) {
            self.ch_pos += 1;
        }
        const end = self.ch_pos;

        return opcodes.parseOp(self.allocator, self.input[start..end]);
    }

    pub fn init(allocator: std.mem.Allocator, input: []const u8) Parser {
        return Parser{
            .allocator = allocator,
            .input = input,
            .location = 0,
            .ch_pos = 0,
            .symbols = std.StringHashMap(SymbolValue).init(allocator),
            .object = std.ArrayList(u8).init(allocator),
        };
    }

    pub fn deinit(self: *Parser) void {
        self.symbols.deinit();
        self.object.deinit();
    }
};

test "normal ascii characters are recognized as symbol chars" {
    const chars = "qwertyuiopasdfghjklzxcvbnm1234567890QWERTYUIOPASDFGHJKLZXCVBNM_";

    for (chars) |c| {
        try std.testing.expect(Parser.isSymbolChar(c));
    }
}

test "large unicode characters are recognized as symbol chars" {
    const cuneiform = "𒀀𒀁𒀂𒀃𒀄𒀅𒀆𒀇𒀈𒀉𒀊𒀋𒀌𒀍𒀎𒀏𒀐𒀑𒀒𒀓𒀔𒀕𒀖𒀗𒀘𒀙𒀚𒀛𒀜𒀝𒀞𒀟𒀠𒀡𒀢𒀣𒀤𒀥𒀦𒀧𒀨𒀩𒀪𒀫𒀬𒀭𒀮𒀯𒀰𒀱𒈷𒌄";

    for (cuneiform) |c| {
        try std.testing.expect(Parser.isSymbolChar(c));
    }
}

test "non-symbol characters are detected" {
    const chars = "\n\r \t!@#$%^&*()-=+[]{}\\|;:'\"/?,.<>`~";

    for (chars) |c| {
        try std.testing.expect(!Parser.isSymbolChar(c));
    }
}

test "symbols are identified" {
    const test_cases = [_][]const u8{
        "_asdf$%@",
        "ASFLKJ3332__q5 ;asdf;lk",
        "asdf𒀤𒀥𒀦\nalsfkd",
        "2H",
        "5F",
        "0B",
    };

    const expected = [_][]const u8{
        "_asdf",
        "ASFLKJ3332__q5",
        "asdf𒀤𒀥𒀦",
        "2H",
        "5F",
        "0B",
    };

    for (0..6) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifySymbol();
        try std.testing.expect(std.mem.eql(u8, expected[i], symbol));
        parser.deinit();
    }
}

test "no symbols are found successfully" {
    const test_cases = [_][]const u8{
        " _asdf",
        ";ASFLKJ3332__q5",
        "\nasdf𒀤𒀥𒀦",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifySymbol();
        try std.testing.expectEqual(error.NoSymbol, symbol);
        parser.deinit();
    }
}

test "opcodes are identified" {
    const test_cases = [_][]const u8{
        "2ADDU%aldfk",
        "GO ",
        "ADD\taksfdjas",
        "GREG\n",
        "IS",
    };

    const expected = [_]opcodes.Operation{
        opcodes.Operation{ .opcode = opcodes.Opcode._2ADDU },
        opcodes.Operation{ .opcode = opcodes.Opcode.GO },
        opcodes.Operation{ .opcode = opcodes.Opcode.ADD },
        opcodes.Operation{ .pseudo_op = opcodes.PseudoOp.GREG },
        opcodes.Operation{ .pseudo_op = opcodes.PseudoOp.IS },
    };

    for (0..5) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const op = try parser.identifyOperation();
        try std.testing.expectEqual(expected[i], op);
        parser.deinit();
    }
}

test "no opcodes are found successfully" {
    const test_cases = [_][]const u8{
        " _asdf",
        ";ASFLKJ3332__q5",
        "\nasdf𒀤𒀥𒀦",
        "asdfklajsdfl",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifyOperation();
        try std.testing.expectEqual(error.NoOpcode, symbol);
        parser.deinit();
    }
}

test "decimals are recognized" {
    const test_cases = [_][]const u8{
        "012314aslkfdj",
        "1234567890  43",
        "1234567891234567889\n123124",
    };

    const expected = [_]u64{
        12314,
        1234567890,
        1234567891234567889,
    };

    for (0..3) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifyDecimal();
        try std.testing.expectEqual(expected[i], symbol);
        parser.deinit();
    }
}

test "malformed decimals are not recognized" {
    const test_cases = [_][]const u8{
        "",
        "asdf123",
        "  123",
        "12345678901234567890123456789012345678901234567890",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifyDecimal();
        try std.testing.expectEqual(error.NoDecimal, symbol);
        parser.deinit();
    }
}

test "hexadecimals are recognized" {
    const test_cases = [_][]const u8{
        "#012314saslkfdj",
        "#1234567890abcdef  43",
        "#1234567891\n123124",
    };

    const expected = [_]u64{
        0x12314,
        0x1234567890abcdef,
        0x1234567891,
    };

    for (0..3) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifyHexadecimal();
        try std.testing.expectEqual(expected[i], symbol);
        parser.deinit();
    }
}

test "malformed hexadecimals are not recognized" {
    const test_cases = [_][]const u8{
        "",
        "sasdf123",
        "  123",
        "#12345678901234567890123456789012345678901234567890",
        "#",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifyHexadecimal();
        try std.testing.expectEqual(error.NoHexadecimal, symbol);
        parser.deinit();
    }
}

test "characters are recognized" {
    const test_cases = [_][]const u8{
        "'a'",
        "'1'",
        "'𒀤'",
    };

    const expected = [_][]const u8{
        "a",
        "1",
        "𒀤",
    };

    for (0..3) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifyChar();
        try std.testing.expect(std.mem.eql(u8, expected[i], symbol));
        parser.deinit();
    }
}

test "invalid unicode sequences are not characters" {
    const test_cases = [_][]const u8{
        "'asdf'",
        "'asdfg'",
        "'as'",
        "''",
        "'",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifyChar();
        try std.testing.expectEqual(error.NoChar, symbol);
        parser.deinit();
    }
}

test "strings are recognized" {
    const test_cases = [_][]const u8{
        "\" \"",
        "\"aslkdfjlaskdfj lkasjflkasjdflaksjfd''12309)($)(#$[[]𒀤\"",
    };

    const expected = [_][]const u8{
        " ",
        "aslkdfjlaskdfj lkasjflkasjdflaksjfd''12309)($)(#$[[]𒀤",
    };

    for (0..2) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifyString();
        try std.testing.expect(std.mem.eql(u8, expected[i], symbol));
        parser.deinit();
    }
}

test "invalid strings are not recognized" {
    const test_cases = [_][]const u8{
        "\"\"",
        "\"",
        "\"\n\"",
    };

    for (test_cases) |case| {
        var parser = Parser.init(std.testing.allocator, case);
        const symbol = parser.identifyString();
        try std.testing.expectEqual(error.NoString, symbol);
        parser.deinit();
    }
}

test "constants are recognized" {
    const test_cases = [_][]const u8{
        "1234567890 1234",
        "#1234567890abcdef;%#*(",
        "'a'uuuuuu",
        "\"hello \"world",
    };

    const expected = [_]ConstantValue{
        ConstantValue{ .number = 1234567890 },
        ConstantValue{ .number = 0x1234567890abcdef },
        ConstantValue{ .string = "a" },
        ConstantValue{ .string = "hello " },
    };

    for (0..4) |i| {
        var parser = Parser.init(std.testing.allocator, test_cases[i]);
        const symbol = try parser.identifyConstant();
        switch (symbol) {
            .number => try std.testing.expectEqual(expected[i].number, symbol.number),
            .string => try std.testing.expect(std.mem.eql(u8, expected[i].string, symbol.string)),
        }
    }
}