15237418122

Committed 25 May 2025 11:31AM UTC coverage: 77.048% (-3.5%) from 80.538%

Build # 15237418122

Build Type

push

github

Committed by

web-flow

Commit Message

Rewrite: Stepper (#1742)

Run Details

3433 of 4826 branches covered (71.14%)

Branch coverage included in aggregate %.

1032 of 1260 new or added lines in 27 files covered. (81.9%)

440 existing lines in 29 files now uncovered.

10099 of 12737 relevant lines covered (79.29%)

142411.96 hits per line

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

95.86

/src/validator/validator.ts

import type es from 'estree'

import { ConstAssignment, UndefinedVariable } from '../errors/errors'
import { NoAssignmentToForVariable } from '../errors/validityErrors'
import { parse } from '../parser/parser'
import type { Context, Node, NodeWithInferredType } from '../types'
import {
  getFunctionDeclarationNamesInProgram,
  getIdentifiersInNativeStorage,
  getIdentifiersInProgram,
  getNativeIds,
  type NativeIds
} from '../utils/uniqueIds'
import { ancestor, base, type FullWalkerCallback } from '../utils/walkers'
import { getSourceVariableDeclaration } from '../utils/ast/helpers'

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') {
        if (statement.id === null) {
          throw new Error(
            '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 ConstAssignment(lastAncestor, name))
          }
          if (a.type === 'ForStatement' && a.init !== lastAncestor && a.update !== lastAncestor) {
            context.errors.push(new NoAssignmentToForVariable(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 UndefinedVariable(name, identifier)
    }
  }
}

1	import type es from 'estree'
2
3	import { ConstAssignment, UndefinedVariable } from '../errors/errors'	77✔
4	import { NoAssignmentToForVariable } from '../errors/validityErrors'	77✔
5	import { parse } from '../parser/parser'	77✔
6	import type { Context, Node, NodeWithInferredType } from '../types'
7	import {	77✔
8	getFunctionDeclarationNamesInProgram,
9	getIdentifiersInNativeStorage,
10	getIdentifiersInProgram,
11	getNativeIds,
12	type NativeIds
13	} from '../utils/uniqueIds'
14	import { ancestor, base, type FullWalkerCallback } from '../utils/walkers'	77✔
15	import { getSourceVariableDeclaration } from '../utils/ast/helpers'	77✔
16
17	class Declaration {
18	public accessedBeforeDeclaration: boolean = false	116,373✔
19	constructor(public isConstant: boolean) {}	116,373✔
20	}
21
22	export function validateAndAnnotate(	77✔
23	program: es.Program,
24	context: Context
25	): NodeWithInferredType<es.Program> {
26	const accessedBeforeDeclarationMap = new Map<Node, Map<string, Declaration>>()	1,819✔
27	const scopeHasCallExpressionMap = new Map<Node, boolean>()	1,819✔
28	function processBlock(node: es.Program \| es.BlockStatement) {
29	const initialisedIdentifiers = new Map<string, Declaration>()	46,496✔
30	for (const statement of node.body) {	46,496✔
31	if (statement.type === 'VariableDeclaration') {	89,017✔
32	initialisedIdentifiers.set(	7,274✔
33	getSourceVariableDeclaration(statement).id.name,
34	new Declaration(statement.kind === 'const')
35	)
36	} else if (statement.type === 'FunctionDeclaration') {	81,743✔
37	if (statement.id === null) {	34,381!
38	throw new Error(	×
39	'Encountered a FunctionDeclaration node without an identifier. This should have been caught when parsing.'
40	)
41	}
42	initialisedIdentifiers.set(statement.id.name, new Declaration(true))	34,381✔
43	}
44	}
45	scopeHasCallExpressionMap.set(node, false)	46,496✔
46	accessedBeforeDeclarationMap.set(node, initialisedIdentifiers)	46,496✔
47	}
48	function processFunction(node: es.FunctionDeclaration \| es.ArrowFunctionExpression) {
49	accessedBeforeDeclarationMap.set(	46,261✔
50	node,
51	new Map((node.params as es.Identifier[]).map(id => [id.name, new Declaration(false)]))	74,361✔
52	)
53	scopeHasCallExpressionMap.set(node, false)	46,261✔
54	}
55
56	// initialise scope of variables
57	ancestor(program as Node, {	1,819✔
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	480,260✔
78	const lastAncestor: Node = ancestors[ancestors.length - 2]	480,260✔
79	for (let i = ancestors.length - 1; i >= 0; i--) {	480,260✔
80	const a = ancestors[i]	3,143,386✔
81	const map = accessedBeforeDeclarationMap.get(a)	3,143,386✔
82	if (map?.has(name)) {	3,143,386✔
83	map.get(name)!.accessedBeforeDeclaration = true	357,076✔
84	if (lastAncestor.type === 'AssignmentExpression' && lastAncestor.left === id) {	357,076✔
85	if (map.get(name)!.isConstant) {	739✔
86	context.errors.push(new ConstAssignment(lastAncestor, name))	1✔
87	}
88	if (a.type === 'ForStatement' && a.init !== lastAncestor && a.update !== lastAncestor) {	739✔
89	context.errors.push(new NoAssignmentToForVariable(lastAncestor))	4✔
90	}
91	}
92	break	357,076✔
93	}
94	}
95	}
96	const customWalker = {	1,819✔
97	...base,
98	VariableDeclarator(node: es.VariableDeclarator, st: never, c: FullWalkerCallback<never>) {
99	// don't visit the id
100	if (node.init) {	7,631✔
101	c(node.init, st, 'Expression')	7,631✔
102	}
103	}
104	}
105	ancestor(	1,819✔
106	program,
107	{
108	VariableDeclaration(node: NodeWithInferredType<es.VariableDeclaration>, ancestors: Node[]) {
109	const lastAncestor = ancestors[ancestors.length - 2]	7,631✔
110	const { name } = getSourceVariableDeclaration(node).id	7,631✔
111	const accessedBeforeDeclaration = accessedBeforeDeclarationMap	7,631✔
112	.get(lastAncestor)!
113	.get(name)!.accessedBeforeDeclaration
114	node.typability = accessedBeforeDeclaration ? 'Untypable' : 'NotYetTyped'	7,631✔
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,381✔
120	node.typability = scopeHasCallExpressionMap.get(lastAncestor) ? 'Untypable' : 'NotYetTyped'	34,381✔
121	},
122	Pattern(node: es.Pattern, ancestors: Node[]) {
123	if (node.type === 'Identifier') {	109,588✔
124	validateIdentifier(node, ancestors)	109,527✔
125	} else if (node.type === 'MemberExpression') {	61✔
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--) {	189,427✔
133	const a = ancestors[i]	998,147✔
134	if (scopeHasCallExpressionMap.has(a)) {	998,147✔
135	scopeHasCallExpressionMap.set(a, true)	189,427✔
136	break	189,427✔
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,819✔
156	}
157
158	export function checkProgramForUndefinedVariables(program: es.Program, context: Context) {	77✔
159	const usedIdentifiers = new Set<string>([	1,287✔
160	...getIdentifiersInProgram(program),
161	...getIdentifiersInNativeStorage(context.nativeStorage)
162	])
163	const globalIds = getNativeIds(program, usedIdentifiers)	1,287✔
164	return checkForUndefinedVariables(program, context, globalIds, false)	1,287✔
165	}
166
167	export function checkForUndefinedVariables(	77✔
168	program: es.Program,
169	context: Context,
170	globalIds: NativeIds,
171	skipUndefined: boolean
172	) {
173	const preludes = context.prelude	2,061✔
174	? getFunctionDeclarationNamesInProgram(parse(context.prelude, context)!)
175	: new Set<string>()
176
177	const env = context.runtime.environments[0].head \|\| {}	2,061!
178
179	const builtins = context.nativeStorage.builtins	2,061✔
180	const identifiersIntroducedByNode = new Map<es.Node, Set<string>>()	2,061✔
181	function processBlock(node: es.Program \| es.BlockStatement) {
182	const identifiers = new Set<string>()	45,990✔
183	for (const statement of node.body) {	45,990✔
184	if (statement.type === 'VariableDeclaration') {	87,924✔
185	const {
186	id: { name }
187	} = getSourceVariableDeclaration(statement)	7,323✔
188	identifiers.add(name)	7,323✔
189	} else if (statement.type === 'FunctionDeclaration') {	80,601✔
190	if (statement.id === null) {	33,725!
UNCOV 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,725✔
196	} else if (statement.type === 'ImportDeclaration') {	46,876✔
197	for (const specifier of statement.specifiers) {	15✔
198	identifiers.add(specifier.local.name)	15✔
199	}
200	}
201	}
202	identifiersIntroducedByNode.set(node, identifiers)	45,990✔
203	}
204	function processFunction(
205	node: es.FunctionDeclaration \| es.ArrowFunctionExpression,
206	_ancestors: es.Node[]
207	) {
208	identifiersIntroducedByNode.set(	45,435✔
209	node,
210	new Set(
211	node.params.map(id =>
212	id.type === 'Identifier'	72,820✔
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[]>()	2,061✔
220	ancestor(program, {	2,061✔
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 }
230	} = getSourceVariableDeclaration(init)	353✔
231	identifiersIntroducedByNode.set(forStatement, new Set([name]))	353✔
232	}
233	},
234	Identifier(identifier: es.Identifier, ancestors: es.Node[]) {
235	identifiersToAncestors.set(identifier, [...ancestors])	431,227✔
236	},
237	Pattern(node: es.Pattern, ancestors: es.Node[]) {
238	if (node.type === 'Identifier') {	115,052✔
239	identifiersToAncestors.set(node, [...ancestors])	115,001✔
240	} else if (node.type === 'MemberExpression') {	51✔
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))	20,610✔
248
249	for (const [identifier, ancestors] of identifiersToAncestors) {	2,061✔
250	const name = identifier.name	480,157✔
251	const isCurrentlyDeclared = ancestors.some(a => identifiersIntroducedByNode.get(a)?.has(name))	1,877,711✔
252	if (isCurrentlyDeclared) {	480,157✔
253	continue	357,431✔
254	}
255	const isPreviouslyDeclared = context.nativeStorage.previousProgramsIdentifiers.has(name)	122,726✔
256	if (isPreviouslyDeclared) {	122,726✔
257	continue	215✔
258	}
259	const isBuiltin = builtins.has(name)	122,511✔
260	if (isBuiltin) {	122,511✔
261	continue	120,702✔
262	}
263	const isPrelude = preludes.has(name)	1,809✔
264	if (isPrelude) {	1,809✔
265	continue	33✔
266	}
267	const isInEnv = name in env	1,776✔
268	if (isInEnv) {	1,776!
UNCOV 269	continue	×
270	}
271	const isNativeId = nativeInternalNames.has(name)	1,776✔
272	if (!isNativeId && !skipUndefined) {	1,776✔
273	throw new UndefinedVariable(name, identifier)	16✔
274	}
275	}
276	}

source-academy / js-slang / 15237418122

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