10975808441

Committed 21 Sep 2024 09:30PM UTC coverage: 93.296% (-0.1%) from 93.407%

Build # 10975808441

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #77 from mellonis/npm+ts

#15 Write code in TS

Run Details

166 of 186 branches covered (89.25%)

Branch coverage included in aggregate %.

212 of 223 new or added lines in 12 files covered. (95.07%)

335 of 351 relevant lines covered (95.44%)

330.9 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.67

/packages/machine/src/classes/TuringMachine.ts

import State, {haltState} from './State';
import TapeBlock, {lockSymbol} from './TapeBlock';
import {symbolCommands} from './TapeCommand';

type RunParameter = { initialState: State, stepsLimit?: number };

export type MachineState = {
  step: number;
  state: State;
  currentSymbols: string[];
  nextSymbols: string[];
  movements: symbol[];
  nextState: State;
};

export default class TuringMachine {
  readonly #tapeBlock: TapeBlock;
  readonly #stack: State[] = [];

  constructor({
                tapeBlock,
              }: { tapeBlock?: TapeBlock } = {}) {
    if (!tapeBlock) {
      throw new Error('invalid tapeBlock');
    }

    this.#tapeBlock = tapeBlock;
  }

  get tapeBlock() {
    return this.#tapeBlock;
  }

  run({initialState, stepsLimit = 1e5, onStep}: RunParameter & { onStep?: (machineState: MachineState) => void }) {
    const generator = this.runStepByStep({initialState, stepsLimit});

    for (const machineState of generator) {
      if (onStep instanceof Function) {
        onStep(machineState);
      }
    }
  }

  * runStepByStep({initialState, stepsLimit = 1e5}: RunParameter): Generator<MachineState> {
    const executionSymbol = Symbol('execution');

    try {
      this.#tapeBlock[lockSymbol].check(executionSymbol);
      this.#tapeBlock[lockSymbol].lock(executionSymbol);


      const stack = this.#stack;
      let state = initialState;

      if (state.overrodeHaltState) {
        stack.push(state.overrodeHaltState);
      }

      let i = 0;

      while (!state.isHalt) {
        if (i === stepsLimit) {
          throw new Error('Long execution');
        }

        i += 1;

        const symbol = state.getSymbol(this.#tapeBlock);
        const command = state.getCommand(symbol);
        let nextState = state.getNextState(symbol).ref;

        try {
          const nextStateForYield = nextState.isHalt && stack.length
            ? stack.slice(-1)[0]
            : nextState;

          yield {
            step: i,
            state,
            currentSymbols: this.#tapeBlock.currentSymbols,
            nextSymbols: command.tapesCommands.map((tapeCommand, ix) => {
              if (typeof tapeCommand.symbol === 'symbol') {
                switch (tapeCommand.symbol) {
                  case symbolCommands.erase:
                    return this.#tapeBlock.tapes[ix].alphabet.blankSymbol;
                  case symbolCommands.keep:
                    return this.#tapeBlock.tapes[ix].symbol;
                  default:
                    throw new Error('invalid symbol command');
                }
              }

              return tapeCommand.symbol;
            }),
            movements: command.tapesCommands.map((tapeCommand) => tapeCommand.movement),
            nextState: nextStateForYield,
          };

          this.#tapeBlock.applyCommand(command, executionSymbol);

          if (nextState.isHalt && stack.length) {
            nextState = stack.pop()!;
          }

          if (state !== nextState && nextState.overrodeHaltState) {
            stack.push(nextState.overrodeHaltState);
          }

          state = nextState;
        } catch (error) {
          if (error !== haltState) {
            throw error;
          }

          break;
        }
      }
    } finally {
      this.#tapeBlock[lockSymbol].unlock(executionSymbol);
    }
  }
}

1	import State, {haltState} from './State';
2	import TapeBlock, {lockSymbol} from './TapeBlock';
3	import {symbolCommands} from './TapeCommand';
4
5	type RunParameter = { initialState: State, stepsLimit?: number };
6
7	export type MachineState = {
8	step: number;
9	state: State;
10	currentSymbols: string[];
11	nextSymbols: string[];
12	movements: symbol[];
13	nextState: State;
14	};
15
16	export default class TuringMachine {
17	readonly #tapeBlock: TapeBlock;
18	readonly #stack: State[] = [];	37✔
19
20	constructor({	×
21	tapeBlock,
22	}: { tapeBlock?: TapeBlock } = {}) {
23	if (!tapeBlock) {	37!
24	throw new Error('invalid tapeBlock');	×
25	}
26
27	this.#tapeBlock = tapeBlock;	37✔
28	}
29
30	get tapeBlock() {
31	return this.#tapeBlock;	14✔
32	}
33
34	run({initialState, stepsLimit = 1e5, onStep}: RunParameter & { onStep?: (machineState: MachineState) => void }) {	89✔
35	const generator = this.runStepByStep({initialState, stepsLimit});	99✔
36
37	for (const machineState of generator) {	99✔
38	if (onStep instanceof Function) {	1,016✔
39	onStep(machineState);	14✔
40	}
41	}
42	}
43
44	* runStepByStep({initialState, stepsLimit = 1e5}: RunParameter): Generator<MachineState> {	8✔
45	const executionSymbol = Symbol('execution');	113✔
46
47	try {	113✔
48	this.#tapeBlock[lockSymbol].check(executionSymbol);	113✔
49	this.#tapeBlock[lockSymbol].lock(executionSymbol);	111✔
50
51
52	const stack = this.#stack;	111✔
53	let state = initialState;	111✔
54
55	if (state.overrodeHaltState) {	111!
56	stack.push(state.overrodeHaltState);	×
57	}
58
59	let i = 0;	111✔
60
61	while (!state.isHalt) {	111✔
62	if (i === stepsLimit) {	1,042✔
63	throw new Error('Long execution');	6✔
64	}
65
66	i += 1;	1,036✔
67
68	const symbol = state.getSymbol(this.#tapeBlock);	1,036✔
69	const command = state.getCommand(symbol);	1,036✔
70	let nextState = state.getNextState(symbol).ref;	1,036✔
71
72	try {	1,036✔
73	const nextStateForYield = nextState.isHalt && stack.length	1,036✔
74	? stack.slice(-1)[0]
75	: nextState;
76
77	yield {	1,036✔
78	step: i,
79	state,
80	currentSymbols: this.#tapeBlock.currentSymbols,
81	nextSymbols: command.tapesCommands.map((tapeCommand, ix) => {
82	if (typeof tapeCommand.symbol === 'symbol') {	1,036✔
83	switch (tapeCommand.symbol) {	858!
84	case symbolCommands.erase:
85	return this.#tapeBlock.tapes[ix].alphabet.blankSymbol;	86✔
86	case symbolCommands.keep:
87	return this.#tapeBlock.tapes[ix].symbol;	772✔
88	default:
NEW 89	throw new Error('invalid symbol command');	×
90	}
91	}
92
93	return tapeCommand.symbol;	178✔
94	}),
95	movements: command.tapesCommands.map((tapeCommand) => tapeCommand.movement),	1,036✔
96	nextState: nextStateForYield,
97	};
98
99	this.#tapeBlock.applyCommand(command, executionSymbol);	1,030✔
100
101	if (nextState.isHalt && stack.length) {	1,030✔
102	nextState = stack.pop()!;	108✔
103	}
104
105	if (state !== nextState && nextState.overrodeHaltState) {	1,030✔
106	stack.push(nextState.overrodeHaltState);	108✔
107	}
108
109	state = nextState;	1,030✔
110	} catch (error) {
111	if (error !== haltState) {	6✔
112	throw error;	2✔
113	}
114
115	break;	4✔
116	}
117	}
118	} finally {
119	this.#tapeBlock[lockSymbol].unlock(executionSymbol);	113✔
120	}
121	}
122	}

mellonis / turing-machine-js / 10975808441

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous