const assert = require('assert');
const { createLexer } = require('../src/core/lexer');
const { createParser } = require('../src/core/parser');
const { createInterpreter } = require('../src/core/interpreter');

describe('Turing Completeness Tests', () => {
  function interpret(code) {
    const lexer = createLexer(code);
    const tokens = lexer.allTokens();
    const parser = createParser(tokens);
    const ast = parser.parse();
    const interpreter = createInterpreter(ast);
    interpreter.interpret(); // Execute the code
    return interpreter; // Return the interpreter instance to access scope
  }

  describe('Church Numerals (Basic)', () => {
    it('should implement basic Church numerals', () => {
      const code = `
        // Church numerals: represent numbers as functions
        // Zero: applies function 0 times
        zero : f x -> x;
        
        // One: applies function 1 time
        one : f x -> f x;
        
        // Test with increment function
        inc : x -> x + 1;
        
        // Convert Church numeral to regular number
        toNumber : n -> n inc 0;
        
        // Test conversions
        result0 : toNumber zero;
        result1 : toNumber one;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('result0').value, 0);
      assert.strictEqual(interpreter.scope.get('result1').value, 1);
    });
  });

  describe('Lambda Calculus (Basic)', () => {
    it('should implement basic lambda calculus operations', () => {
      const code = `
        // Basic lambda calculus operations
        
        // Identity function
        id : x -> x;
        
        // Constant function
        const : x y -> x;
        
        // Function composition
        compose : f g x -> f (g x);
        
        // Test identity
        testId : id 42;
        
        // Test constant
        testConst : const 10 20;
        
        // Test composition
        testCompose : compose (x -> x + 1) (x -> x * 2) 5;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('testId').value, 42);
      assert.strictEqual(interpreter.scope.get('testConst').value, 10);
      assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11
    });
  });

  describe('Universal Function (Basic)', () => {
    it('should implement a basic universal function', () => {
      const code = `
        // Simple universal function using function encoding
        // This demonstrates that our language can simulate any computable function
        
        // Function registry
        functionRegistry : {
          inc: x -> x + 1;
          double: x -> x * 2;
        };
        
        // Universal function that can simulate any registered function
        universal : funcName input ->
          when funcName is
            "inc" then (functionRegistry.inc input)
            "double" then (functionRegistry.double input)
            _ then input;
        
        // Test the universal function
        result1 : universal "inc" 5;
        result2 : universal "double" 5;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('result1').value, 6);
      assert.strictEqual(interpreter.scope.get('result2').value, 10);
    });
  });

  describe('Turing Machine Simulator (Basic)', () => {
    it('should simulate a basic Turing machine', () => {
      const code = `
        // Simple Turing machine that counts 1s on the tape
        // States: "start", "halt"
        
        // Initialize Turing machine
        initTM : {
          tape: [1, 1, 0, 1],
          head: 0,
          state: "start"
        };
        
        // Transition function
        transition : tm ->
          when tm.state is
            "start" then when (tm.head >= (length tm.tape)) is
                            true then { tape: tm.tape, head: tm.head, state: "halt" }
                            _    then { tape: tm.tape, head: tm.head + 1, state: "start" }
            _ then tm;
        
        // Run Turing machine
        runTM : tm ->
          when tm.state is
            "halt" then tm
            _ then runTM (transition tm);
        
        // Test
        result : runTM initTM;
      `;

      const interpreter = interpret(code);
      const result = interpreter.scope.get('result');
      
      // Should reach halt state
      assert.strictEqual(result.state, "halt");
    });
  });

  describe('Recursive Functions (Turing Complete)', () => {
    it('should demonstrate Turing completeness through recursion', () => {
      const code = `
        // Ackermann function - a classic example of a computable but not primitive recursive function
        // This demonstrates that our language can compute any computable function
        
        ackermann : m n ->
          when m is
            0 then n + 1
            _ then
              when n is
                0 then ackermann (m - 1) 1
                _ then ackermann (m - 1) (ackermann m (n - 1));
        
        // Test with small values (larger values would cause stack overflow)
        result1 : ackermann 0 5;
        result2 : ackermann 1 3;
        result3 : ackermann 2 2;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('result1').value, 6);
      assert.strictEqual(interpreter.scope.get('result2').value, 5);
      assert.strictEqual(interpreter.scope.get('result3').value, 7);
    });
  });

  describe('Higher-Order Functions (Turing Complete)', () => {
    it('should demonstrate Turing completeness through higher-order functions', () => {
      const code = `
        // Higher-order functions that can simulate any computable function
        
        // Test with factorial using fixed point
        factorialHelper : f n ->
          when n is
            0 then 1
            _ then n * (f (n - 1));
        
        // Test with small values
        testFactorial : factorialHelper (n -> 1) 0;
        testFactorial2 : factorialHelper (n -> n * 1) 1;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('testFactorial').value, 1);
      // The helper calls f(0) when n=1; with f = (n -> n * 1), this evaluates to 0
      assert.strictEqual(interpreter.scope.get('testFactorial2').value, 0);
    });
  });

  describe('SKI Combinator Calculus (Basic)', () => {
    it('should implement basic SKI combinators', () => {
      const code = `
        // SKI Combinator Calculus - basic version
        
        // K combinator: Kxy = x
        K : x y -> x;
        
        // I combinator: Ix = x
        I : x -> x;
        
        // Test I combinator
        testI : I 42;
        
        // Test K combinator
        testK : K 10 20;
        
        // Test composition
        compose : f g x -> f (g x);
        testCompose : compose (x -> x + 1) (x -> x * 2) 5;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('testI').value, 42);
      assert.strictEqual(interpreter.scope.get('testK').value, 10);
      assert.strictEqual(interpreter.scope.get('testCompose').value, 11); // (5*2)+1 = 11
    });
  });

  describe('Mutual Recursion (Turing Complete)', () => {
    it('should demonstrate Turing completeness through mutual recursion', () => {
      const code = `
        // Mutual recursion example - isEven and isOdd
        // This demonstrates that our language can handle complex recursive patterns
        
        isEven : n ->
          when n is
            0 then true
            1 then false
            _ then isOdd (n - 1);
        
        isOdd : n ->
          when n is
            0 then false
            1 then true
            _ then isEven (n - 1);
        
        // Test mutual recursion
        result1 : isEven 0;
        result2 : isEven 1;
        result3 : isEven 2;
        result4 : isEven 3;
        result5 : isOdd 0;
        result6 : isOdd 1;
        result7 : isOdd 2;
        result8 : isOdd 3;
      `;

      const interpreter = interpret(code);
      
      assert.strictEqual(interpreter.scope.get('result1'), true);
      assert.strictEqual(interpreter.scope.get('result2'), false);
      assert.strictEqual(interpreter.scope.get('result3'), true);
      assert.strictEqual(interpreter.scope.get('result4'), false);
      assert.strictEqual(interpreter.scope.get('result5'), false);
      assert.strictEqual(interpreter.scope.get('result6'), true);
      assert.strictEqual(interpreter.scope.get('result7'), false);
      assert.strictEqual(interpreter.scope.get('result8'), true);
    });
  });
});