/**
* Tests for CSDL Parser
*/
import { Lexer } from './constraintLexer.js';
import { Parser } from './constraintParser.js';
import { TypeChecker } from './constraintTypeChecker.js';
import { astToString } from './constraintAST.js';
describe('CSDL Parser', () => {
function parseSource(source: string) {
const lexer = new Lexer(source);
const tokens = lexer.tokenize();
const parser = new Parser(tokens);
return parser.parse();
}
function parseAndTypeCheck(source: string) {
const ast = parseSource(source);
const checker = new TypeChecker();
const result = checker.check(ast);
return { ast, ...result };
}
describe('Variable Declarations', () => {
test('simple variable declaration', () => {
const source = 'var x: Int';
const ast = parseSource(source);
expect(ast.type).toBe('Program');
expect(ast.declarations).toHaveLength(1);
expect(ast.declarations[0].type).toBe('VarDecl');
expect((ast.declarations[0] as any).names).toEqual(['x']);
expect((ast.declarations[0] as any).varType.name).toBe('Int');
});
test('multiple variables of same type', () => {
const source = 'var x, y, z: Int';
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('VarDecl');
expect((ast.declarations[0] as any).names).toEqual(['x', 'y', 'z']);
});
test('variable with initializer', () => {
const source = 'var x: Int = 42';
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('VarDecl');
expect((ast.declarations[0] as any).initializer).toBeDefined();
expect((ast.declarations[0] as any).initializer.value).toBe(42);
});
test('variable with where clause', () => {
const source = 'var x: Int where x > 0';
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('VarDecl');
expect((ast.declarations[0] as any).whereClause).toBeDefined();
});
});
describe('Constant Declarations', () => {
test('constant declaration', () => {
const source = 'const PI: Real = 3.14159';
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('ConstDecl');
expect((ast.declarations[0] as any).name).toBe('PI');
expect((ast.declarations[0] as any).constType.name).toBe('Real');
expect((ast.declarations[0] as any).value.value).toBeCloseTo(3.14159);
});
});
describe('Function Declarations', () => {
test('simple function', () => {
const source = 'function is_even(n: Int) -> Bool: n % 2 == 0';
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('FunctionDecl');
expect((ast.declarations[0] as any).name).toBe('is_even');
expect((ast.declarations[0] as any).params).toHaveLength(1);
expect((ast.declarations[0] as any).returnType.name).toBe('Bool');
});
test('recursive function', () => {
const source = `function factorial(n: Int) -> Int:
if n <= 1 then 1
else n * factorial(n - 1)`;
const ast = parseSource(source);
expect(ast.declarations[0].type).toBe('FunctionDecl');
expect((ast.declarations[0] as any).name).toBe('factorial');
});
});
describe('Constraints', () => {
test('simple constraint', () => {
const source = 'x + y == 10';
const ast = parseSource(source);
expect(ast.constraints).toHaveLength(1);
expect(ast.constraints[0].type).toBe('BinaryExpr');
});
test('assert constraint', () => {
const source = 'assert: x > 0';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('Assert');
expect((ast.constraints[0] as any).expr.type).toBe('BinaryExpr');
});
test('named assert', () => {
const source = 'assert positive_x: x > 0';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('Assert');
expect((ast.constraints[0] as any).name).toBe('positive_x');
});
test('soft constraint', () => {
const source = 'soft: x > 10 weight 5';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('SoftConstraint');
expect((ast.constraints[0] as any).weight).toBe(5);
});
test('check_sat', () => {
const source = 'check_sat: x > 0 and y > 0';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('CheckSat');
});
test('minimize', () => {
const source = 'minimize: x + y';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('Optimize');
expect((ast.constraints[0] as any).direction).toBe('minimize');
});
test('maximize with name', () => {
const source = 'maximize profit: revenue - cost';
const ast = parseSource(source);
expect(ast.constraints[0].type).toBe('Optimize');
expect((ast.constraints[0] as any).direction).toBe('maximize');
expect((ast.constraints[0] as any).name).toBe('profit');
});
});
describe('Arithmetic Expressions', () => {
test('simple addition', () => {
const source = 'x + y == 10';
const ast = parseSource(source);
const constraint = ast.constraints[0] as any;
expect(constraint.left.type).toBe('BinaryExpr');
expect(constraint.left.operator).toBe('add');
});
test('operator precedence', () => {
const source = 'x + y * z';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('add');
expect(expr.right.operator).toBe('multiply');
});
test('power operator', () => {
const source = 'x ** 2';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('power');
});
test('parentheses override precedence', () => {
const source = '(x + y) * z';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('multiply');
expect(expr.left.operator).toBe('add');
});
});
describe('Logical Expressions', () => {
test('and operator', () => {
const source = 'x > 0 and y > 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('and');
});
test('or operator', () => {
const source = 'x < 0 or x > 10';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('or');
});
test('not operator', () => {
const source = 'not x';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('not');
});
test('implies operator', () => {
const source = 'x > 0 => y > 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('implies');
});
test('iff operator', () => {
const source = 'x > 0 <=> y > 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('iff');
});
});
describe('Comparison Expressions', () => {
test('equality', () => {
const source = 'x == 10';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('eq');
});
test('inequality', () => {
const source = 'x != 10';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('ne');
});
test('less than', () => {
const source = 'x < 10';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.operator).toBe('lt');
});
});
describe('If Expressions', () => {
test('simple if expression', () => {
const source = 'if x > 0 then 1 else 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('IfExpr');
expect(expr.condition).toBeDefined();
expect(expr.thenBranch).toBeDefined();
expect(expr.elseBranch).toBeDefined();
});
test('nested if expression', () => {
const source = 'if x > 0 then 1 else if x < 0 then -1 else 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('IfExpr');
expect(expr.elseBranch.type).toBe('IfExpr');
});
});
describe('Quantified Expressions', () => {
test('forall with range', () => {
const source = 'forall i in 0..10: arr[i] >= 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('QuantifiedExpr');
expect(expr.quantifier).toBe('forall');
expect(expr.variable).toBe('i');
expect(expr.domain.type).toBe('Range');
});
test('exists with set', () => {
const source = 'exists x in [1, 2, 3, 5, 8]: x > 5';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('QuantifiedExpr');
expect(expr.quantifier).toBe('exists');
expect(expr.domain.type).toBe('Set');
});
test('nested quantifiers', () => {
const source = 'forall i in 0..n: forall j in 0..m: matrix[i][j] >= 0';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('QuantifiedExpr');
expect(expr.body.type).toBe('QuantifiedExpr');
});
});
describe('Array Operations', () => {
test('array indexing', () => {
const source = 'arr[0]';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('IndexExpr');
expect(expr.array.name).toBe('arr');
expect(expr.index.value).toBe(0);
});
test('array literal', () => {
const source = '[1, 2, 3, 4, 5]';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('ArrayLiteral');
expect(expr.elements).toHaveLength(5);
});
test('array comprehension', () => {
const source = '[i * i for i in 0..10]';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('ArrayComprehension');
expect(expr.variable).toBe('i');
expect(expr.domain.type).toBe('Range');
});
test('array comprehension with filter', () => {
const source = '[i for i in 0..100 if i % 2 == 0]';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('ArrayComprehension');
expect(expr.condition).toBeDefined();
});
});
describe('Set Operations', () => {
test('set literal', () => {
const source = '{1, 2, 3, 4, 5}';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('SetLiteral');
expect(expr.elements).toHaveLength(5);
});
test('set comprehension', () => {
const source = '{x for x in 2..100 if is_prime(x)}';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('SetComprehension');
expect(expr.variable).toBe('x');
});
});
describe('Function Calls', () => {
test('simple function call', () => {
const source = 'abs(x)';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('CallExpr');
expect(expr.callee).toBe('abs');
expect(expr.args).toHaveLength(1);
});
test('function call with multiple arguments', () => {
const source = 'max(x, y, z)';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('CallExpr');
expect(expr.args).toHaveLength(3);
});
test('nested function calls', () => {
const source = 'abs(min(x, y))';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('CallExpr');
expect(expr.args[0].type).toBe('CallExpr');
});
});
describe('Member Access', () => {
test('array length', () => {
const source = 'arr.length';
const ast = parseSource(source);
const expr = ast.constraints[0] as any;
expect(expr.type).toBe('MemberAccess');
expect(expr.object.name).toBe('arr');
expect(expr.member).toBe('length');
});
});
describe('Type Checking', () => {
test('valid arithmetic types', () => {
const source = `
var x: Int = 5
var y: Int = 10
x + y == 15
`;
const { errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('type mismatch in assignment', () => {
const source = `
var x: Int = "hello"
`;
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
expect(errors[0]).toContain('Type mismatch');
});
test('boolean constraint type', () => {
const source = `
var x: Int
var y: Int
x + y > 10
`;
const { errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('non-boolean constraint error', () => {
const source = `
var x: Int
var y: Int
x + y
`;
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
expect(errors[0]).toContain('must be boolean');
});
test('function argument type checking', () => {
const source = `
function square(x: Int) -> Int: x * x
var result: Int = square(5)
result > 0
`;
const { errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('function argument type mismatch', () => {
const source = `
function square(x: Int) -> Int: x * x
square("hello")
`;
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
});
test('array element type checking', () => {
const source = `
var arr: Array[Int] = [1, 2, 3, 4, 5]
`;
const { errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('if branch type compatibility', () => {
const source = `
var x: Int
var result: Int = if x > 0 then 1 else 0
result > 0
`;
const { errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('quantifier body must be boolean', () => {
const source = `
var arr: Array[Int]
forall i in 0..10: arr[i]
`;
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
expect(errors[0]).toContain('must be boolean');
});
});
describe('Complex Examples', () => {
test('Example 1: Simple constraint problem', () => {
const source = `
var x, y: Int
x + y == 10
x > y
minimize: x
`;
const { ast, errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
expect(ast.declarations).toHaveLength(1);
expect(ast.constraints).toHaveLength(3);
});
test('Example 6: Meeting scheduler', () => {
const source = `
const NUM_MEETINGS: Int = 4
var meeting_starts: Array[Int]
var meeting_ends: Array[Int]
const WORK_START: Int = 540
const WORK_END: Int = 1020
const MIN_DURATION: Int = 30
forall i in 0..NUM_MEETINGS-1:
meeting_starts[i] >= WORK_START and
meeting_ends[i] <= WORK_END and
meeting_ends[i] >= meeting_starts[i] + MIN_DURATION
minimize: meeting_starts[0]
`;
const { ast, errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('Example 12: Sudoku (simplified)', () => {
const source = `
const SIZE: Int = 4
var grid: Array[Array[Int]]
forall i in 0..SIZE-1:
forall j in 0..SIZE-1:
grid[i][j] >= 1 and grid[i][j] <= SIZE
`;
const { ast, errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('Example 13: N-Queens', () => {
const source = `
const N: Int = 8
var queens: Array[Int]
forall i in 0..N-1:
queens[i] >= 0 and queens[i] < N
forall i in 0..N-1:
forall j in i+1..N-1:
queens[i] != queens[j]
`;
const { ast, errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
test('Example 15: Cryptarithmetic', () => {
const source = `
var S, E, N, D, M, O, R, Y: Int
S >= 0 and S <= 9
E >= 0 and E <= 9
N >= 0 and N <= 9
D >= 0 and D <= 9
M >= 0 and M <= 9
O >= 0 and O <= 9
R >= 0 and R <= 9
Y >= 0 and Y <= 9
S != 0
M != 0
var SEND: Int = 1000 * S + 100 * E + 10 * N + D
var MORE: Int = 1000 * M + 100 * O + 10 * R + E
var MONEY: Int = 10000 * M + 1000 * O + 100 * N + 10 * E + Y
SEND + MORE == MONEY
`;
const { ast, errors } = parseAndTypeCheck(source);
expect(errors).toHaveLength(0);
});
});
describe('Error Messages', () => {
test('undefined variable error', () => {
const source = 'x + y == 10';
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
expect(errors[0]).toContain('Undefined variable');
});
test('undefined function error', () => {
const source = 'foo(42)';
const { errors } = parseAndTypeCheck(source);
expect(errors.length).toBeGreaterThan(0);
expect(errors[0]).toContain('Undefined function');
});
test('parse error with location', () => {
const source = 'var x: Int =';
expect(() => parseSource(source)).toThrow(/Parse error/);
});
});
});
