28181093691

Committed 25 Jun 2026 03:25PM UTC coverage: 78.584% (+0.05%) from 78.53%

Build # 28181093691

Build Type

Pull #1995

github

Committed by

web-flow

Commit Message

Merge bf8fdcf90 into c5b34c1fc

Pull Request Pull Request #1995: Operators Fix

Coverage Stats

3155 of 4228 branches covered (74.62%)

Branch coverage included in aggregate %.

22 of 24 new or added lines in 8 files covered. (91.67%)

81 existing lines in 13 files now uncovered.

7064 of 8776 relevant lines covered (80.49%)

177913.25 hits per line

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

96.65

/src/validator/validator.ts

import type es from 'estree';

import { ConstAssignmentError, UndefinedVariableError } from '../errors/errors';
import { NoAssignmentToForVariableError } from '../errors/validityErrors';
import { parse } from '../parser/parser';
import type { Context, Node, NodeWithInferredType } from '../types';
import { getSourceVariableDeclaration } from '../utils/ast/helpers';
import { ancestor, base, type FullWalkerCallback } from '../utils/ast/walkers';
import {
  getFunctionDeclarationNamesInProgram,
  getIdentifiersInNativeStorage,
  getIdentifiersInProgram,
  getNativeIds,
  type NativeIds,
} from '../utils/uniqueIds';
import assert from '../utils/assert';

class Declaration {
  public accessedBeforeDeclaration: boolean = false;
  constructor(public isConstant: boolean) {}
}

export function validateAndAnnotate(
  program: es.Program,
  context: Context,
): NodeWithInferredType<es.Program> {
  const accessedBeforeDeclarationMap = new Map<Node, Map<string, Declaration>>();
  const scopeHasCallExpressionMap = new Map<Node, boolean>();
  function processBlock(node: es.Program | es.BlockStatement) {
    const initialisedIdentifiers = new Map<string, Declaration>();
    for (const statement of node.body) {
      if (statement.type === 'VariableDeclaration') {
        initialisedIdentifiers.set(
          getSourceVariableDeclaration(statement).id.name,
          new Declaration(statement.kind === 'const'),
        );
      } else if (statement.type === 'FunctionDeclaration') {
        assert(
          !!statement.id,
          'Encountered a FunctionDeclaration node without an identifier. This should have been caught when parsing.',
        );
        initialisedIdentifiers.set(statement.id.name, new Declaration(true));
      }
    }
    scopeHasCallExpressionMap.set(node, false);
    accessedBeforeDeclarationMap.set(node, initialisedIdentifiers);
  }
  function processFunction(node: es.FunctionDeclaration | es.ArrowFunctionExpression) {
    accessedBeforeDeclarationMap.set(
      node,
      new Map((node.params as es.Identifier[]).map(id => [id.name, new Declaration(false)])),
    );
    scopeHasCallExpressionMap.set(node, false);
  }

  // initialise scope of variables
  ancestor(program as Node, {
    Program: processBlock,
    BlockStatement: processBlock,
    FunctionDeclaration: processFunction,
    ArrowFunctionExpression: processFunction,
    ForStatement(forStatement: es.ForStatement, _ancestors: Node[]) {
      const init = forStatement.init!;
      if (init.type === 'VariableDeclaration') {
        accessedBeforeDeclarationMap.set(
          forStatement,
          new Map([
            [getSourceVariableDeclaration(init).id.name, new Declaration(init.kind === 'const')],
          ]),
        );
        scopeHasCallExpressionMap.set(forStatement, false);
      }
    },
  });

  function validateIdentifier(id: es.Identifier, ancestors: Node[]) {
    const name = id.name;
    const lastAncestor: Node = ancestors[ancestors.length - 2];
    for (let i = ancestors.length - 1; i >= 0; i--) {
      const a = ancestors[i];
      const map = accessedBeforeDeclarationMap.get(a);
      if (map?.has(name)) {
        map.get(name)!.accessedBeforeDeclaration = true;
        if (lastAncestor.type === 'AssignmentExpression' && lastAncestor.left === id) {
          if (map.get(name)!.isConstant) {
            context.errors.push(new ConstAssignmentError(lastAncestor, name));
          }
          if (a.type === 'ForStatement' && a.init !== lastAncestor && a.update !== lastAncestor) {
            context.errors.push(new NoAssignmentToForVariableError(lastAncestor));
          }
        }
        break;
      }
    }
  }
  const customWalker = {
    ...base,
    VariableDeclarator(node: es.VariableDeclarator, st: never, c: FullWalkerCallback<never>) {
      // don't visit the id
      if (node.init) {
        c(node.init, st, 'Expression');
      }
    },
  };
  ancestor(
    program,
    {
      VariableDeclaration(node: NodeWithInferredType<es.VariableDeclaration>, ancestors: Node[]) {
        const lastAncestor = ancestors[ancestors.length - 2];
        const { name } = getSourceVariableDeclaration(node).id;
        const accessedBeforeDeclaration = accessedBeforeDeclarationMap
          .get(lastAncestor)!
          .get(name)!.accessedBeforeDeclaration;
        node.typability = accessedBeforeDeclaration ? 'Untypable' : 'NotYetTyped';
      },
      Identifier: validateIdentifier,
      FunctionDeclaration(node: NodeWithInferredType<es.FunctionDeclaration>, ancestors: Node[]) {
        // a function declaration can be typed if there are no function calls in the same scope before it
        const lastAncestor = ancestors[ancestors.length - 2];
        node.typability = scopeHasCallExpressionMap.get(lastAncestor) ? 'Untypable' : 'NotYetTyped';
      },
      Pattern(node: es.Pattern, ancestors: Node[]) {
        if (node.type === 'Identifier') {
          validateIdentifier(node, ancestors);
        } else if (node.type === 'MemberExpression') {
          if (node.object.type === 'Identifier') {
            validateIdentifier(node.object, ancestors);
          }
        }
      },
      CallExpression(call: es.CallExpression, ancestors: Node[]) {
        for (let i = ancestors.length - 1; i >= 0; i--) {
          const a = ancestors[i];
          if (scopeHasCallExpressionMap.has(a)) {
            scopeHasCallExpressionMap.set(a, true);
            break;
          }
        }
      },
    },
    customWalker,
  );

  /*
  simple(program, {
    VariableDeclaration(node: TypeAnnotatedNode<es.VariableDeclaration>) {
      console.log(getVariableDecarationName(node) + " " + node.typability);
    },
    FunctionDeclaration(node: TypeAnnotatedNode<es.FunctionDeclaration>) {
      console.log(node.id!.name + " " + node.typability);
    }
  })

   */
  return program;
}

export function checkProgramForUndefinedVariables(program: es.Program, context: Context) {
  const usedIdentifiers = new Set<string>([
    ...getIdentifiersInProgram(program),
    ...getIdentifiersInNativeStorage(context.nativeStorage),
  ]);
  const globalIds = getNativeIds(program, usedIdentifiers);
  return checkForUndefinedVariables(program, context, globalIds, false);
}

export function checkForUndefinedVariables(
  program: es.Program,
  context: Context,
  globalIds: NativeIds,
  skipUndefined: boolean,
) {
  const preludes = context.prelude
    ? getFunctionDeclarationNamesInProgram(parse(context.prelude, context)!)
    : new Set<string>();

  const env = context.runtime.environments[0].head || {};

  const builtins = context.nativeStorage.builtins;
  const identifiersIntroducedByNode = new Map<es.Node, Set<string>>();
  function processBlock(node: es.Program | es.BlockStatement) {
    const identifiers = new Set<string>();
    for (const statement of node.body) {
      if (statement.type === 'VariableDeclaration') {
        const {
          id: { name },
        } = getSourceVariableDeclaration(statement);
        identifiers.add(name);
      } else if (statement.type === 'FunctionDeclaration') {
        if (statement.id === null) {
          throw new Error(
            'Encountered a FunctionDeclaration node without an identifier. This should have been caught when parsing.',
          );
        }
        identifiers.add(statement.id.name);
      } else if (statement.type === 'ImportDeclaration') {
        for (const specifier of statement.specifiers) {
          identifiers.add(specifier.local.name);
        }
      }
    }
    identifiersIntroducedByNode.set(node, identifiers);
  }
  function processFunction(
    node: es.FunctionDeclaration | es.ArrowFunctionExpression,
    _ancestors: es.Node[],
  ) {
    identifiersIntroducedByNode.set(
      node,
      new Set(
        node.params.map(id =>
          id.type === 'Identifier'
            ? id.name
            : ((id as es.RestElement).argument as es.Identifier).name,
        ),
      ),
    );
  }
  const identifiersToAncestors = new Map<es.Identifier, es.Node[]>();
  ancestor(program, {
    Program: processBlock,
    BlockStatement: processBlock,
    FunctionDeclaration: processFunction,
    ArrowFunctionExpression: processFunction,
    ForStatement(forStatement: es.ForStatement) {
      const init = forStatement.init!;
      if (init.type === 'VariableDeclaration') {
        const {
          id: { name },
        } = getSourceVariableDeclaration(init);
        identifiersIntroducedByNode.set(forStatement, new Set([name]));
      }
    },
    Identifier(identifier: es.Identifier, ancestors: es.Node[]) {
      identifiersToAncestors.set(identifier, [...ancestors]);
    },
    Pattern(node: es.Pattern, ancestors: es.Node[]) {
      if (node.type === 'Identifier') {
        identifiersToAncestors.set(node, [...ancestors]);
      } else if (node.type === 'MemberExpression') {
        if (node.object.type === 'Identifier') {
          identifiersToAncestors.set(node.object, [...ancestors]);
        }
      }
    },
  });
  const nativeInternalNames = new Set(Object.values(globalIds).map(({ name }) => name));

  for (const [identifier, ancestors] of identifiersToAncestors) {
    const name = identifier.name;
    const isCurrentlyDeclared = ancestors.some(a => identifiersIntroducedByNode.get(a)?.has(name));
    if (isCurrentlyDeclared) {
      continue;
    }
    const isPreviouslyDeclared = context.nativeStorage.previousProgramsIdentifiers.has(name);
    if (isPreviouslyDeclared) {
      continue;
    }
    const isBuiltin = builtins.has(name);
    if (isBuiltin) {
      continue;
    }
    const isPrelude = preludes.has(name);
    if (isPrelude) {
      continue;
    }
    const isInEnv = name in env;
    if (isInEnv) {
      continue;
    }
    const isNativeId = nativeInternalNames.has(name);
    if (!isNativeId && !skipUndefined) {
      throw new UndefinedVariableError(name, identifier);
    }
  }
}

1	import type es from 'estree';
2
3	import { ConstAssignmentError, UndefinedVariableError } from '../errors/errors';
4	import { NoAssignmentToForVariableError } from '../errors/validityErrors';
5	import { parse } from '../parser/parser';
6	import type { Context, Node, NodeWithInferredType } from '../types';
7	import { getSourceVariableDeclaration } from '../utils/ast/helpers';
8	import { ancestor, base, type FullWalkerCallback } from '../utils/ast/walkers';
9	import {
10	getFunctionDeclarationNamesInProgram,
11	getIdentifiersInNativeStorage,
12	getIdentifiersInProgram,
13	getNativeIds,
14	type NativeIds,
15	} from '../utils/uniqueIds';
16	import assert from '../utils/assert';
17
18	class Declaration {
19	public accessedBeforeDeclaration: boolean = false;	115,159✔
20	constructor(public isConstant: boolean) {}	115,159✔
21	}
22
23	export function validateAndAnnotate(
24	program: es.Program,
25	context: Context,
26	): NodeWithInferredType<es.Program> {
27	const accessedBeforeDeclarationMap = new Map<Node, Map<string, Declaration>>();	1,699✔
28	const scopeHasCallExpressionMap = new Map<Node, boolean>();	1,699✔
29	function processBlock(node: es.Program \| es.BlockStatement) {
30	const initialisedIdentifiers = new Map<string, Declaration>();	46,090✔
31	for (const statement of node.body) {	46,090✔
32	if (statement.type === 'VariableDeclaration') {	88,190✔
33	initialisedIdentifiers.set(	7,086✔
34	getSourceVariableDeclaration(statement).id.name,
35	new Declaration(statement.kind === 'const'),
36	);
37	} else if (statement.type === 'FunctionDeclaration') {	81,104✔
38	assert(	34,196✔
39	!!statement.id,
40	'Encountered a FunctionDeclaration node without an identifier. This should have been caught when parsing.',
41	);
42	initialisedIdentifiers.set(statement.id.name, new Declaration(true));	34,196✔
43	}
44	}
45	scopeHasCallExpressionMap.set(node, false);	46,090✔
46	accessedBeforeDeclarationMap.set(node, initialisedIdentifiers);	46,090✔
47	}
48	function processFunction(node: es.FunctionDeclaration \| es.ArrowFunctionExpression) {
49	accessedBeforeDeclarationMap.set(	45,858✔
50	node,
51	new Map((node.params as es.Identifier[]).map(id => [id.name, new Declaration(false)])),	73,520✔
52	);
53	scopeHasCallExpressionMap.set(node, false);	45,858✔
54	}
55
56	// initialise scope of variables
57	ancestor(program as Node, {	1,699✔
58	Program: processBlock,
59	BlockStatement: processBlock,
60	FunctionDeclaration: processFunction,
61	ArrowFunctionExpression: processFunction,
62	ForStatement(forStatement: es.ForStatement, _ancestors: Node[]) {
63	const init = forStatement.init!;	358✔
64	if (init.type === 'VariableDeclaration') {	358✔
65	accessedBeforeDeclarationMap.set(	357✔
66	forStatement,
67	new Map([
68	[getSourceVariableDeclaration(init).id.name, new Declaration(init.kind === 'const')],
69	]),
70	);
71	scopeHasCallExpressionMap.set(forStatement, false);	357✔
72	}
73	},
74	});
75
76	function validateIdentifier(id: es.Identifier, ancestors: Node[]) {
77	const name = id.name;	444,548✔
78	const lastAncestor: Node = ancestors[ancestors.length - 2];	444,548✔
79	for (let i = ancestors.length - 1; i >= 0; i--) {	444,548✔
80	const a = ancestors[i];	2,821,998✔
81	const map = accessedBeforeDeclarationMap.get(a);	2,821,998✔
82	if (map?.has(name)) {	2,821,998✔
83	map.get(name)!.accessedBeforeDeclaration = true;	353,817✔
84	if (lastAncestor.type === 'AssignmentExpression' && lastAncestor.left === id) {	353,817✔
85	if (map.get(name)!.isConstant) {	736✔
86	context.errors.push(new ConstAssignmentError(lastAncestor, name));	1✔
87	}
88	if (a.type === 'ForStatement' && a.init !== lastAncestor && a.update !== lastAncestor) {	736✔
89	context.errors.push(new NoAssignmentToForVariableError(lastAncestor));	4✔
90	}
91	}
92	break;	353,817✔
93	}
94	}
95	}
96	const customWalker = {	1,699✔
97	...base,
98	VariableDeclarator(node: es.VariableDeclarator, st: never, c: FullWalkerCallback<never>) {
99	// don't visit the id
100	if (node.init) {	7,443!
101	c(node.init, st, 'Expression');	7,443✔
102	}
103	},
104	};
105	ancestor(	1,699✔
106	program,
107	{
108	VariableDeclaration(node: NodeWithInferredType<es.VariableDeclaration>, ancestors: Node[]) {
109	const lastAncestor = ancestors[ancestors.length - 2];	7,443✔
110	const { name } = getSourceVariableDeclaration(node).id;	7,443✔
111	const accessedBeforeDeclaration = accessedBeforeDeclarationMap	7,443✔
112	.get(lastAncestor)!
113	.get(name)!.accessedBeforeDeclaration;
114	node.typability = accessedBeforeDeclaration ? 'Untypable' : 'NotYetTyped';	7,443✔
115	},
116	Identifier: validateIdentifier,
117	FunctionDeclaration(node: NodeWithInferredType<es.FunctionDeclaration>, ancestors: Node[]) {
118	// a function declaration can be typed if there are no function calls in the same scope before it
119	const lastAncestor = ancestors[ancestors.length - 2];	34,196✔
120	node.typability = scopeHasCallExpressionMap.get(lastAncestor) ? 'Untypable' : 'NotYetTyped';	34,196✔
121	},
122	Pattern(node: es.Pattern, ancestors: Node[]) {
123	if (node.type === 'Identifier') {	108,479✔
124	validateIdentifier(node, ancestors);	108,458✔
125	} else if (node.type === 'MemberExpression') {	21✔
126	if (node.object.type === 'Identifier') {	16✔
127	validateIdentifier(node.object, ancestors);	12✔
128	}
129	}
130	},
131	CallExpression(call: es.CallExpression, ancestors: Node[]) {
132	for (let i = ancestors.length - 1; i >= 0; i--) {	156,680✔
133	const a = ancestors[i];	729,542✔
134	if (scopeHasCallExpressionMap.has(a)) {	729,542✔
135	scopeHasCallExpressionMap.set(a, true);	156,680✔
136	break;	156,680✔
137	}
138	}
139	},
140	},
141	customWalker,
142	);
143
144	/*
145	simple(program, {
146	VariableDeclaration(node: TypeAnnotatedNode<es.VariableDeclaration>) {
147	console.log(getVariableDecarationName(node) + " " + node.typability);
148	},
149	FunctionDeclaration(node: TypeAnnotatedNode<es.FunctionDeclaration>) {
150	console.log(node.id!.name + " " + node.typability);
151	}
152	})
153
154	*/
155	return program;	1,699✔
156	}
157
158	export function checkProgramForUndefinedVariables(program: es.Program, context: Context) {
159	const usedIdentifiers = new Set<string>([	1,073✔
160	...getIdentifiersInProgram(program),
161	...getIdentifiersInNativeStorage(context.nativeStorage),
162	]);
163	const globalIds = getNativeIds(program, usedIdentifiers);	1,073✔
164	return checkForUndefinedVariables(program, context, globalIds, false);	1,073✔
165	}
166
167	export function checkForUndefinedVariables(
168	program: es.Program,
169	context: Context,
170	globalIds: NativeIds,
171	skipUndefined: boolean,
172	) {
173	const preludes = context.prelude	1,805✔
174	? getFunctionDeclarationNamesInProgram(parse(context.prelude, context)!)
175	: new Set<string>();
176
177	const env = context.runtime.environments[0].head \|\| {};	1,805!
178
179	const builtins = context.nativeStorage.builtins;	1,805✔
180	const identifiersIntroducedByNode = new Map<es.Node, Set<string>>();	1,805✔
181	function processBlock(node: es.Program \| es.BlockStatement) {
182	const identifiers = new Set<string>();	45,314✔
183	for (const statement of node.body) {	45,314✔
184	if (statement.type === 'VariableDeclaration') {	86,664✔
185	const {
186	id: { name },	7,053✔
187	} = getSourceVariableDeclaration(statement);
188	identifiers.add(name);	7,053✔
189	} else if (statement.type === 'FunctionDeclaration') {	79,611✔
190	if (statement.id === null) {	33,467!
191	throw new Error(	×
192	'Encountered a FunctionDeclaration node without an identifier. This should have been caught when parsing.',
193	);
194	}
195	identifiers.add(statement.id.name);	33,467✔
196	} else if (statement.type === 'ImportDeclaration') {	46,144✔
197	for (const specifier of statement.specifiers) {	9✔
198	identifiers.add(specifier.local.name);	9✔
199	}
200	}
201	}
202	identifiersIntroducedByNode.set(node, identifiers);	45,314✔
203	}
204	function processFunction(
205	node: es.FunctionDeclaration \| es.ArrowFunctionExpression,
206	_ancestors: es.Node[],
207	) {
208	identifiersIntroducedByNode.set(	44,934✔
209	node,
210	new Set(
211	node.params.map(id =>
212	id.type === 'Identifier'	71,910✔
213	? id.name
214	: ((id as es.RestElement).argument as es.Identifier).name,
215	),
216	),
217	);
218	}
219	const identifiersToAncestors = new Map<es.Identifier, es.Node[]>();	1,805✔
220	ancestor(program, {	1,805✔
221	Program: processBlock,
222	BlockStatement: processBlock,
223	FunctionDeclaration: processFunction,
224	ArrowFunctionExpression: processFunction,
225	ForStatement(forStatement: es.ForStatement) {
226	const init = forStatement.init!;	354✔
227	if (init.type === 'VariableDeclaration') {	354✔
228	const {
229	id: { name },	353✔
230	} = getSourceVariableDeclaration(init);
231	identifiersIntroducedByNode.set(forStatement, new Set([name]));	353✔
232	}
233	},
234	Identifier(identifier: es.Identifier, ancestors: es.Node[]) {
235	identifiersToAncestors.set(identifier, [...ancestors]);	432,876✔
236	},
237	Pattern(node: es.Pattern, ancestors: es.Node[]) {
238	if (node.type === 'Identifier') {	113,531✔
239	identifiersToAncestors.set(node, [...ancestors]);	113,520✔
240	} else if (node.type === 'MemberExpression') {	11✔
241	if (node.object.type === 'Identifier') {	6✔
242	identifiersToAncestors.set(node.object, [...ancestors]);	3✔
243	}
244	}
245	},
246	});
247	const nativeInternalNames = new Set(Object.values(globalIds).map(({ name }) => name));	18,050✔
248
249	for (const [identifier, ancestors] of identifiersToAncestors) {	1,805✔
250	const name = identifier.name;	444,464✔
251	const isCurrentlyDeclared = ancestors.some(a => identifiersIntroducedByNode.get(a)?.has(name));	1,567,120✔
252	if (isCurrentlyDeclared) {	444,464✔
253	continue;	353,433✔
254	}
255	const isPreviouslyDeclared = context.nativeStorage.previousProgramsIdentifiers.has(name);	91,031✔
256	if (isPreviouslyDeclared) {	91,031✔
257	continue;	185✔
258	}
259	const isBuiltin = builtins.has(name);	90,846✔
260	if (isBuiltin) {	90,846✔
261	continue;	88,426✔
262	}
263	const isPrelude = preludes.has(name);	2,420✔
264	if (isPrelude) {	2,420✔
265	continue;	34✔
266	}
267	const isInEnv = name in env;	2,386✔
268	if (isInEnv) {	2,386!
UNCOV 269	continue;	×
270	}
271	const isNativeId = nativeInternalNames.has(name);	2,386✔
272	if (!isNativeId && !skipUndefined) {	2,386✔
273	throw new UndefinedVariableError(name, identifier);	12✔
274	}
275	}
276	}

source-academy / js-slang / 28181093691

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