Virtual Machine

README.md

Virtual Machine

Abstract virtual machine done in TypeScript. Originally intended as a backend for my visual novel browser engine, but dropped it in favor of a generic state machine.

vm.test.ts

/**
 * Sealed Sins, 2023.
 */
import { VM, VmReg } from './vm';

describe('Virtual Machine', () => {
	it('is serializable', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['yld'],
			['let', VmReg.R0, 2],
			['yld'],
			['let', VmReg.R0, 3],
		]);
		vm.next();
		const state = vm.save();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(2);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(3);
		vm.load(state);
		expect(vm.getReg(VmReg.R0)).toEqual(1);
	});

	it('is suitable for writing a visual novel', () => {
		const vm = new VM([
			['let', VmReg.R0, { name: '', text: '' }],
			['sti', VmReg.R0, 'state'],

			// Mark page start.
			['tag', 'pageStart:1'],
			['yld'],

			// Load state & event info.
			['ldi', VmReg.R0, 'state'],
			['ldi', VmReg.R1, 'event'],

			// Check event type and proceed if it's `next`.
			['get', VmReg.R2, VmReg.R1, 'type'],
			['let', VmReg.R3, 'next'],
			['jeq', VmReg.R2, VmReg.R3, 'pageUpdate:1'],
			['jmp', 'pageStart:1'],

			// Update state.
			['tag', 'pageUpdate:1'],
			['let', VmReg.R4, { text: 'Hello!' }],
			['mrg', VmReg.R0, VmReg.R4],

			// Mark next page start...
			['tag', 'pageStart:2'],
			['yld'],
		]);

		vm.next();
		expect(vm.getVar('state')).toEqual({ name: '', text: '' });

		vm.setVar('event', { type: 'not-next' });
		vm.next();
		expect(vm.getVar('state')).toEqual({ name: '', text: '' });

		vm.setVar('event', { type: 'next' });
		vm.next();
		expect(vm.getVar('state')).toEqual({ name: '', text: 'Hello!' });
	});

	it('implements "let" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, 2],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "mov" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, 2],
			['mov', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(2);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "get" command', () => {
		const vm = new VM([
			['let', VmReg.R0, { a: 1, b: 2, c: [3, 4] }],
			['get', VmReg.R1, VmReg.R0, 'a'],
			['get', VmReg.R2, VmReg.R0, 'b'],
			['get', VmReg.R3, VmReg.R0, 'c[0]'],
			['get', VmReg.R4, VmReg.R0, 'c[1]'],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R1)).toEqual(1);
		expect(vm.getReg(VmReg.R2)).toEqual(2);
		expect(vm.getReg(VmReg.R3)).toEqual(3);
		expect(vm.getReg(VmReg.R4)).toEqual(4);
	});

	it('implements "set" command', () => {
		const vm = new VM([
			['let', VmReg.R0, {}],
			['let', VmReg.R1, 1],
			['let', VmReg.R2, 2],
			['set', VmReg.R1, VmReg.R0, 'a'],
			['set', VmReg.R2, VmReg.R0, 'b'],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual({ a: 1, b: 2 });
	});

	it('implements "mrg" command', () => {
		const vm = new VM([
			['let', VmReg.R0, { a: 1 }],
			['let', VmReg.R1, { b: 2, c: 3 }],
			['mrg', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual({ a: 1, b: 2, c: 3 });
		expect(vm.getReg(VmReg.R1)).toEqual({ b: 2, c: 3 });
	});

	it('implements "ldi" command', () => {
		const vm = new VM([
			['ldi', VmReg.R0, 'a'],
			['ldi', VmReg.R1, 'b'],
		]);
		vm.setVar('a', 1);
		vm.setVar('b', 2);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "sti" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, 2],
			['sti', VmReg.R0, 'a'],
			['sti', VmReg.R1, 'b'],
		]);
		vm.next();
		expect(vm.getVar('a')).toEqual(1);
		expect(vm.getVar('b')).toEqual(2);
	});

	it('implements "tag", "jmp" and "yld" commands', () => {
		const vm = new VM([
			['tag', 'start'],
			['let', VmReg.R0, 0],
			['yld'],
			['let', VmReg.R0, 1],
			['yld'],
			['jmp', 'start'],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(0);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(0);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
	});

	it('implements "jeq" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 0],
			['let', VmReg.R1, 1],
			['jeq', VmReg.R0, VmReg.R1, 'isEqual'],
			['yld'],
			['let', VmReg.R0, 1],
			['jeq', VmReg.R0, VmReg.R1, 'isEqual'],
			['yld'],
			['tag', 'isEqual'],
			['let', VmReg.R2, true],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R2)).not.toEqual(true);
		vm.next();
		expect(vm.getReg(VmReg.R2)).toEqual(true);
	});

	it('implements "jgt" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 0],
			['let', VmReg.R1, 0],
			['jgt', VmReg.R0, VmReg.R1, 'isGreater'],
			['yld'],
			['let', VmReg.R0, 1],
			['jgt', VmReg.R0, VmReg.R1, 'isGreater'],
			['yld'],
			['tag', 'isGreater'],
			['let', VmReg.R2, true],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R2)).not.toEqual(true);
		vm.next();
		expect(vm.getReg(VmReg.R2)).toEqual(true);
	});

	it('implements "jlt" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 0],
			['let', VmReg.R1, 0],
			['jlt', VmReg.R0, VmReg.R1, 'isSmaller'],
			['yld'],
			['let', VmReg.R1, 1],
			['jlt', VmReg.R0, VmReg.R1, 'isSmaller'],
			['yld'],
			['tag', 'isSmaller'],
			['let', VmReg.R2, true],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R2)).not.toEqual(true);
		vm.next();
		expect(vm.getReg(VmReg.R2)).toEqual(true);
	});

	it('implements "dbg" command', () => {
		const logMock = jest.spyOn(console, 'log').mockImplementation();
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, { a: 2, b: 3 }],
			['sti', VmReg.R0, 'x'],
			['sti', VmReg.R1, 'y'],
			['dbg', '{{ reg.R0 }} {{ reg.R1.a }} {{ reg.R1.b }}'],
			['dbg', '{{ mem.x }} {{ mem.y.a }} {{ mem.y.b }}'],
		]);
		vm.next();
		expect(logMock).toHaveBeenNthCalledWith(1, '1 2 3');
		expect(logMock).toHaveBeenNthCalledWith(2, '1 2 3');
		logMock.mockRestore();
	});

	it('implements "fmt" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, { a: 2, b: 3 }],
			['sti', VmReg.R0, 'x'],
			['sti', VmReg.R1, 'y'],
			['fmt', VmReg.R3, '{{ reg.R0 }} {{ reg.R1.a }} {{ reg.R1.b }}'],
			['fmt', VmReg.R4, '{{ mem.x }} {{ mem.y.a }} {{ mem.y.b }}'],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R3)).toEqual('1 2 3');
		expect(vm.getReg(VmReg.R4)).toEqual('1 2 3');
	});

	it('implements "not" command', () => {
		const vm = new VM([
			['let', VmReg.R0, true],
			['not', VmReg.R0],
			['yld'],
			['not', VmReg.R0],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(false);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(true);
	});

	it('implements "inc" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 0],
			['inc', VmReg.R0],
			['inc', VmReg.R0],
			['inc', VmReg.R0],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(+3);
	});

	it('implements "dec" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 0],
			['dec', VmReg.R0],
			['dec', VmReg.R0],
			['dec', VmReg.R0],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(-3);
	});

	it('implements "add" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 1],
			['let', VmReg.R1, 2],
			['add', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(3);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "sub" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 3],
			['let', VmReg.R1, 2],
			['sub', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(1);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "mul" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 4],
			['let', VmReg.R1, 2],
			['mul', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(8);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});

	it('implements "div" command', () => {
		const vm = new VM([
			['let', VmReg.R0, 4],
			['let', VmReg.R1, 2],
			['div', VmReg.R0, VmReg.R1],
		]);
		vm.next();
		expect(vm.getReg(VmReg.R0)).toEqual(2);
		expect(vm.getReg(VmReg.R1)).toEqual(2);
	});
});

vm.ts

/**
 * Sealed Sins, 2023.
 */
import { pick, get, set, merge } from 'lodash';
import { compile as handlebarsCompile } from 'handlebars';
import { parseNumber, parseObject } from './utils';

// Inspired by:
// https://www.jmeiners.com/lc3-vm/

/**
 * VM register type.
 */
export enum VmReg {
	PC = 'PC',
	R0 = 'R0',
	R1 = 'R1',
	R2 = 'R2',
	R3 = 'R3',
	R4 = 'R4',
	R5 = 'R5',
	R6 = 'R6',
	R7 = 'R7',
	R8 = 'R8',
	R9 = 'R9',
}

/**
 * VM command type.
 */
// prettier-ignore
export type VmCommand = (
	| [ 'let', VmReg, VmVariable ]
	| [ 'mov', VmReg, VmReg ]
	| [ 'get', VmReg, VmReg, string ]
	| [ 'set', VmReg, VmReg, string ]
	| [ 'mrg', VmReg, VmReg ]
	| [ 'ldi', VmReg, string ]
	| [ 'sti', VmReg, string ]
	| [ 'tag', string ]
	| [ 'jmp', string ]
	| [ 'yld' ]
	| [ 'jeq', VmReg, VmReg, string ]	
	| [ 'jgt', VmReg, VmReg, string ]	
	| [ 'jlt', VmReg, VmReg, string ]	
	| [ 'dbg', string ]
	| [ 'fmt', VmReg, string ]
	| [ 'not', VmReg ]
	| [ 'inc', VmReg ]
	| [ 'dec', VmReg ]
	| [ 'add', VmReg, VmReg ]
	| [ 'sub', VmReg, VmReg ]
	| [ 'mul', VmReg, VmReg ]
	| [ 'div', VmReg, VmReg ]
);

/**
 * VM variable type.
 */
// prettier-ignore
export type VmVariable = (
	number | string | boolean | null | Array<VmVariable> | { [key: string]: VmVariable }
);

/**
 * VM error with additional metadata.
 */
export class VmError extends Error {
	// prettier-ignore
	constructor(public messageOriginal: string, public lineNumber?: number) {
		super(`VmError (at ${lineNumber ?? '?'}): ${messageOriginal}`);
	}
}

/**
 * Generic Virtual Machine.
 */
export class VM {
	private mem: Record<string, VmVariable>;
	private reg: Record<VmReg, VmVariable>;

	constructor(private readonly code: Array<VmCommand> = []) {
		this.mem = {};
		this.reg = {
			[VmReg.R0]: 0,
			[VmReg.R1]: 0,
			[VmReg.R2]: 0,
			[VmReg.R3]: 0,
			[VmReg.R4]: 0,
			[VmReg.R5]: 0,
			[VmReg.R6]: 0,
			[VmReg.R7]: 0,
			[VmReg.R8]: 0,
			[VmReg.R9]: 0,
			[VmReg.PC]: 0,
		};
	}

	/**
	 * Serialize VM state.
	 */
	public save() {
		const data = pick(this, ['reg', 'mem', 'code']);
		return JSON.stringify(data);
	}

	/**
	 * Deserialize VM state.
	 */
	public load(state: string) {
		const data = parseObject(JSON.parse(state));
		Object.assign(this, data);
	}

	/**
	 * Get register scope.
	 */
	public regs() {
		return this.reg;
	}

	/**
	 * Get register.
	 */
	public getReg<T extends VmVariable>(reg: VmReg) {
		return this.reg[reg] as T;
	}

	/**
	 * Set register.
	 */
	public setReg<T extends VmVariable>(reg: VmReg, value: T) {
		this.reg[reg] = value;
	}

	/**
	 * Get variable scope.
	 */
	public vars() {
		return this.mem;
	}

	/**
	 * Get variable.
	 */
	public getVar<T extends VmVariable>(key: string) {
		return (this.mem[key] ?? null) as T;
	}

	/**
	 * Set variable.
	 */
	public setVar<T extends VmVariable>(key: string, value: T) {
		this.mem[key] = value;
	}

	/**
	 * Format string using data from VM.
	 * Use `reg` to access registers and `mem` to access variable memory.
	 */
	public format(fmt: string) {
		const fscope = { reg: this.regs(), mem: this.vars() };
		const render = handlebarsCompile(fmt);
		return render(fscope);
	}

	/**
	 * Jump to the given tag (label).
	 */
	public jump(tag: string) {
		for (const [index, cmd] of this.code.entries()) {
			if (cmd[0] === 'tag' && cmd[1] === tag) {
				this.setReg(VmReg.PC, index + 1);
				return;
			}
		}
		// prettier-ignore
		throw new VmError(
			`Invalid jump target: ${tag}`
		);
	}

	/**
	 * Execute VM commands until the next `yld` command.
	 */
	public next() {
		const pc = this.getReg<number>(VmReg.PC);
		const cmd = this.code[pc];
		if (cmd) {
			try {
				this.setReg(VmReg.PC, pc + 1);
				if (cmd[0] !== 'yld') {
					this.exec(cmd);
					this.next();
				}
			} catch (err: any) {
				const text = err.messageOriginal || err.message || err.toString();
				const lineNumber = err.lineNumber ?? pc + 1;
				throw new VmError(text, lineNumber);
			}
		}
	}

	/**
	 * Execute given comand within current VM context.
	 */
	public exec(cmd: VmCommand) {
		switch (cmd[0]) {
			case 'let': {
				const [_, reg, value] = cmd;
				this.setReg(reg, value);
				break;
			}
			case 'mov': {
				const [_, regAcc, regVal] = cmd;
				const val = this.getReg(regVal);
				this.setReg(regAcc, val);
				break;
			}
			case 'get': {
				const [_, regAcc, regObj, path] = cmd;
				const obj = parseObject(this.getReg(regObj));
				const val = get(obj, path, null) as VmVariable;
				this.setReg(regAcc, val);
				break;
			}
			case 'set': {
				const [_, regAcc, regObj, path] = cmd;
				const obj = parseObject(this.getReg(regObj));
				const val = this.getReg(regAcc);
				set(obj, path, val);
				break;
			}
			case 'mrg': {
				const [_, regAcc, regUpd] = cmd;
				const acc = parseObject(this.getReg(regAcc));
				const upd = parseObject(this.getReg(regUpd));
				merge(acc, upd);
				break;
			}
			case 'ldi': {
				const [_, reg, key] = cmd;
				this.setReg(reg, this.getVar(key));
				break;
			}
			case 'sti': {
				const [_, reg, key] = cmd;
				this.setVar(key, this.getReg(reg));
				break;
			}
			case 'tag': {
				break; // handled by jump() method
			}
			case 'jmp': {
				const [_, tag] = cmd;
				this.jump(tag);
				break;
			}
			case 'yld': {
				break; // handled by next() method
			}
			case 'jeq': {
				const [_, regA, regB, tag] = cmd;
				const a = this.getReg(regA);
				const b = this.getReg(regB);
				if (a === b) {
					this.jump(tag);
				}
				break;
			}
			case 'jgt': {
				const [_, regA, regB, tag] = cmd;
				const a = parseNumber(this.getReg(regA));
				const b = parseNumber(this.getReg(regB));
				if (a > b) {
					this.jump(tag);
				}
				break;
			}
			case 'jlt': {
				const [_, regA, regB, tag] = cmd;
				const a = parseNumber(this.getReg(regA));
				const b = parseNumber(this.getReg(regB));
				if (a < b) {
					this.jump(tag);
				}
				break;
			}
			case 'dbg': {
				const [_, fmt] = cmd;
				const str = this.format(fmt);
				console.log(str);
				break;
			}
			case 'fmt': {
				const [_, regAcc, fmt] = cmd;
				const str = this.format(fmt);
				this.setReg(regAcc, str);
				break;
			}
			case 'not': {
				const [_, regAcc] = cmd;
				const acc = this.getReg(regAcc);
				this.setReg(regAcc, !acc);
				break;
			}
			case 'inc': {
				const [_, regAcc] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				this.setReg(regAcc, acc + 1);
				break;
			}
			case 'dec': {
				const [_, regAcc] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				this.setReg(regAcc, acc - 1);
				break;
			}
			case 'add': {
				const [_, regAcc, regVal] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				const val = parseNumber(this.getReg(regVal));
				this.setReg(regAcc, acc + val);
				break;
			}
			case 'sub': {
				const [_, regAcc, regVal] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				const val = parseNumber(this.getReg(regVal));
				this.setReg(regAcc, acc - val);
				break;
			}
			case 'mul': {
				const [_, regAcc, regVal] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				const val = parseNumber(this.getReg(regVal));
				this.setReg(regAcc, acc * val);
				break;
			}
			case 'div': {
				const [_, regAcc, regVal] = cmd;
				const acc = parseNumber(this.getReg(regAcc));
				const val = parseNumber(this.getReg(regVal));
				this.setReg(regAcc, acc / val);
				break;
			}
			default: {
				const exhaustiveSwitchTest: never = cmd;
				throw new VmError(`Unexpected: ${cmd}`);
			}
		}
	}
}