5406352152

import * as pathlib from 'path'

import { parse } from '../../parser/parser'
import type { AcornOptions } from '../../parser/types'
import type { Context } from '../../types'
import assert from '../../utils/assert'
import {
  isIdentifier,
  isModuleDeclaration,
  isModuleDeclarationWithSource,
  isSourceImport
} from '../../utils/ast/typeGuards'
import type * as es from '../../utils/ast/types'
import { CircularImportError, ModuleNotFoundError } from '../errors'
import type { ImportResolutionOptions } from '../moduleTypes'
import analyzeImportsAndExports from './analyzer'
import { createInvokedFunctionResultVariableDeclaration } from './constructors/contextSpecificConstructors'
import { DirectedGraph } from './directedGraph'
import { transformFunctionNameToInvokedFunctionResultVariableName } from './filePaths'
import resolveModule from './resolver'
import hoistAndMergeImports from './transformers/hoistAndMergeImports'
import removeImportsAndExports from './transformers/removeImportsAndExports'
import {
  createAccessImportStatements,
  getInvokedFunctionResultVariableNameToImportSpecifiersMap,
  transformProgramToFunctionDeclaration
} from './transformers/transformProgramToFunctionDeclaration'

/**
 * Error type to indicate that preprocessing has failed but that the context
 * contains the underlying errors
 */
class PreprocessError extends Error {}

const defaultResolutionOptions: Required<ImportResolutionOptions> = {
  allowUndefinedImports: false,
  resolveDirectories: false,
  resolveExtensions: null
}

/**
 * Parse all of the provided files and figure out which modules
 * are dependent on which, returning that result in the form
 * of a DAG
 */
export const parseProgramsAndConstructImportGraph = async (
  files: Partial<Record<string, string>>,
  entrypointFilePath: string,
  context: Context,
  rawResolutionOptions: Partial<ImportResolutionOptions> = {}
): Promise<{
  programs: Record<string, es.Program>
  importGraph: DirectedGraph
}> => {
  const resolutionOptions = {
    ...defaultResolutionOptions,
    ...rawResolutionOptions
  }
  const programs: Record<string, es.Program> = {}
  const importGraph = new DirectedGraph()

  // If there is more than one file, tag AST nodes with the source file path.
  const numOfFiles = Object.keys(files).length
  const shouldAddSourceFileToAST = numOfFiles > 1

  async function resolve(path: string, node?: es.ModuleDeclarationWithSource) {
    let source: string
    if (node) {
      assert(
        typeof node.source.value === 'string',
        `${node.type} should have a source of type string, got ${node.source}`
      )
      source = node.source.value
    } else {
      source = path
    }

    const [resolved, modAbsPath] = await resolveModule(
      node ? path : '.',
      source,
      p => files[p] !== undefined,
      resolutionOptions
    )
    if (!resolved) throw new ModuleNotFoundError(modAbsPath, node)
    return modAbsPath
  }

  /**
   * Process each file (as a module) and determine which other (local and source)
   * modules are required. This function should always be called with absolute
   * paths
   *
   * @param currentFilePath Current absolute file path of the module
   */
  async function parseFile(currentFilePath: string): Promise<void> {
    if (currentFilePath in programs) {
      return
    }

    const code = files[currentFilePath]
    assert(
      code !== undefined,
      "Module resolver should've thrown an error if the file path did not resolve"
    )

    // Tag AST nodes with the source file path for use in error messages.
    const parserOptions: Partial<AcornOptions> = shouldAddSourceFileToAST
      ? {
          sourceFile: currentFilePath
        }
      : {}
    const program = parse<AcornOptions>(code, context, parserOptions, false)
    if (!program) {
      // Due to a bug in the typed parser where throwOnError isn't respected,
      // we need to throw a quick exit error here instead
      throw new PreprocessError()
    }

    const dependencies = new Set<string>()
    programs[currentFilePath] = program

    for (const node of program.body) {
      if (!isModuleDeclarationWithSource(node)) continue

      const modAbsPath = await resolve(currentFilePath, node)
      if (modAbsPath === currentFilePath) {
        throw new CircularImportError([modAbsPath, currentFilePath])
      }

      dependencies.add(modAbsPath)

      // Replace the source of the node with the resolved path
      node.source.value = modAbsPath
    }

    await Promise.all(
      Array.from(dependencies).map(async dependency => {
        // There is no need to track Source modules as dependencies, as it can be assumed
        // that they will always come first in the topological order
        if (!isSourceImport(dependency)) {
          await parseFile(dependency)
          // If the edge has already been traversed before, the import graph
          // must contain a cycle. Then we can exit early and proceed to find the cycle
          if (importGraph.hasEdge(dependency, currentFilePath)) {
            throw new PreprocessError()
          }

          importGraph.addEdge(dependency, currentFilePath)
        }
      })
    )
  }

  try {
    // Remember to resolve the entrypoint file too!
    const entrypointAbsPath = await resolve(entrypointFilePath)
    await parseFile(entrypointAbsPath)
  } catch (error) {
    if (!(error instanceof PreprocessError)) {
      context.errors.push(error)
    }
  }

  return {
    programs,
    importGraph
  }
}

export type PreprocessOptions = {
  allowUndefinedImports?: boolean
} & ImportResolutionOptions

const defaultOptions: Required<PreprocessOptions> = {
  ...defaultResolutionOptions,
  allowUndefinedImports: false
}

/**
 * Preprocesses file imports and returns a transformed Abstract Syntax Tree (AST).
 * If an error is encountered at any point, returns `undefined` to signify that an
 * error occurred. Details of the error can be found inside `context.errors`.
 *
 * The preprocessing works by transforming each imported file into a function whose
 * parameters are other files (results of transformed functions) and return value
 * is a pair where the head is the default export or null, and the tail is a list
 * of pairs that map from exported names to identifiers.
 *
 * See https://github.com/source-academy/js-slang/wiki/Local-Module-Import-&-Export
 * for more information.
 *
 * @param files              An object mapping absolute file paths to file content.
 * @param entrypointFilePath The absolute path of the entrypoint file.
 * @param context            The information associated with the program evaluation.
 */
const preprocessFileImports = async (
  files: Partial<Record<string, string>>,
  entrypointFilePath: string,
  context: Context,
  rawOptions: Partial<PreprocessOptions> = {}
): Promise<es.Program | undefined> => {
  const { allowUndefinedImports, ...resolutionOptions } = {
    ...defaultOptions,
    ...rawOptions
  }

  // Parse all files into ASTs and build the import graph.
  const { programs, importGraph } = await parseProgramsAndConstructImportGraph(
    files,
    entrypointFilePath,
    context,
    resolutionOptions
  )

  // Return 'undefined' if there are errors while parsing.
  if (context.errors.length !== 0) {
    return undefined
  }

  // Check for circular imports.
  const topologicalOrderResult = importGraph.getTopologicalOrder()
  if (!topologicalOrderResult.isValidTopologicalOrderFound) {
    context.errors.push(new CircularImportError(topologicalOrderResult.firstCycleFound))
    return undefined
  }

  let newPrograms: Record<string, es.Program> = {}
  try {
    // Based on how the import graph is constructed, it could be the case that the entrypoint
    // file is never included in the topo order. This is only an issue for the import export
    // analyzer, hence the following code
    const fullTopoOrder = topologicalOrderResult.topologicalOrder
    if (!fullTopoOrder.includes(entrypointFilePath)) {
      // Since it's the entrypoint, it must be loaded last
      fullTopoOrder.push(entrypointFilePath)
    }

    // This check is performed after cycle detection because if we tried to resolve export symbols
    // and there is a cycle in the import graph the constructImportGraph function may end up in an
    // infinite loop
    // For example, a.js: export * from './b.js' and b.js: export * from './a.js'
    // Then trying to discover what symbols are exported by a.js will require determining what symbols
    // b.js exports, which would in turn require the symbols exported by a.js
    // If the topological order exists, then this is guaranteed not to occur
    newPrograms = await analyzeImportsAndExports(programs, fullTopoOrder, allowUndefinedImports)
  } catch (error) {
    context.errors.push(error)
    return undefined
  }

  // We want to operate on the entrypoint program to get the eventual
  // preprocessed program.
  const entrypointProgram = newPrograms[entrypointFilePath]
  const entrypointDirPath = pathlib.resolve(entrypointFilePath, '..')

  // Create variables to hold the imported statements.
  const entrypointProgramModuleDeclarations = entrypointProgram.body.filter(isModuleDeclaration)
  const entrypointProgramInvokedFunctionResultVariableNameToImportSpecifiersMap =
    getInvokedFunctionResultVariableNameToImportSpecifiersMap(
      entrypointProgramModuleDeclarations,
      entrypointDirPath
    )
  const entrypointProgramAccessImportStatements = createAccessImportStatements(
    entrypointProgramInvokedFunctionResultVariableNameToImportSpecifiersMap
  )

  // Transform all programs into their equivalent function declaration
  // except for the entrypoint program.
  const [functionDeclarations, invokedFunctionResultVariableDeclarations] =
    topologicalOrderResult.topologicalOrder
      // The entrypoint program does not need to be transformed into its
      // function declaration equivalent as its enclosing environment is
      // simply the overall program's (constructed program's) environment.
      .filter(path => path !== entrypointFilePath)
      .reduce(
        ([funcDecls, invokeDecls], filePath) => {
          const program = newPrograms[filePath]
          const functionDeclaration = transformProgramToFunctionDeclaration(program, filePath)

          const functionName = functionDeclaration.id.name
          const invokedFunctionResultVariableName =
            transformFunctionNameToInvokedFunctionResultVariableName(functionName)

          const functionParams = functionDeclaration.params.filter(isIdentifier)
          assert(
            functionParams.length === functionDeclaration.params.length,
            'Function declaration contains non-Identifier AST nodes as params. This should never happen.'
          )

          // Invoke each of the transformed functions and store the result in a variable.
          const invokedFunctionResultVariableDeclaration =
            createInvokedFunctionResultVariableDeclaration(
              functionName,
              invokedFunctionResultVariableName,
              functionParams
            )

          return [
            [...funcDecls, functionDeclaration],
            [...invokeDecls, invokedFunctionResultVariableDeclaration]
          ]
        },
        [[], []] as [es.FunctionDeclaration[], es.VariableDeclaration[]]
      )

  // Re-assemble the program.
  const preprocessedProgram: es.Program = {
    ...entrypointProgram,
    body: [
      ...functionDeclarations,
      ...invokedFunctionResultVariableDeclarations,
      ...entrypointProgramAccessImportStatements,
      ...entrypointProgram.body
    ]
  }

  // console.log(generate(preprocessedProgram))

  // Import and Export related nodes are no longer necessary, so we can remove them from the program entirely
  removeImportsAndExports(preprocessedProgram)

  // Finally, we need to hoist all remaining imports to the top of the
  // program. These imports should be source module imports since
  // non-Source module imports would have already been removed. As part
  // of this step, we also merge imports from the same module so as to
  // import each unique name per module only once.
  hoistAndMergeImports(preprocessedProgram, newPrograms)
  return preprocessedProgram
}

export default preprocessFileImports

1	import * as pathlib from 'path'	52✔
2
3	import { parse } from '../../parser/parser'	52✔
4	import type { AcornOptions } from '../../parser/types'
5	import type { Context } from '../../types'
6	import assert from '../../utils/assert'	52✔
7	import {	52✔
8	isIdentifier,
9	isModuleDeclaration,
10	isModuleDeclarationWithSource,
11	isSourceImport
12	} from '../../utils/ast/typeGuards'
13	import type * as es from '../../utils/ast/types'
14	import { CircularImportError, ModuleNotFoundError } from '../errors'	52✔
15	import type { ImportResolutionOptions } from '../moduleTypes'
16	import analyzeImportsAndExports from './analyzer'	52✔
17	import { createInvokedFunctionResultVariableDeclaration } from './constructors/contextSpecificConstructors'	52✔
18	import { DirectedGraph } from './directedGraph'	52✔
19	import { transformFunctionNameToInvokedFunctionResultVariableName } from './filePaths'	52✔
20	import resolveModule from './resolver'	52✔
21	import hoistAndMergeImports from './transformers/hoistAndMergeImports'	52✔
22	import removeImportsAndExports from './transformers/removeImportsAndExports'	52✔
23	import {	52✔
24	createAccessImportStatements,
25	getInvokedFunctionResultVariableNameToImportSpecifiersMap,
26	transformProgramToFunctionDeclaration
27	} from './transformers/transformProgramToFunctionDeclaration'
28
29	/**
30	* Error type to indicate that preprocessing has failed but that the context
31	* contains the underlying errors
32	*/
33	class PreprocessError extends Error {}
34
35	const defaultResolutionOptions: Required<ImportResolutionOptions> = {	52✔
36	allowUndefinedImports: false,
37	resolveDirectories: false,
38	resolveExtensions: null
39	}
40
41	/**
42	* Parse all of the provided files and figure out which modules
43	* are dependent on which, returning that result in the form
44	* of a DAG
45	*/
46	export const parseProgramsAndConstructImportGraph = async (	52✔
47	files: Partial<Record<string, string>>,
48	entrypointFilePath: string,
49	context: Context,
50	rawResolutionOptions: Partial<ImportResolutionOptions> = {}	61✔
51	): Promise<{
52	programs: Record<string, es.Program>
53	importGraph: DirectedGraph
54	}> => {	1,997✔
55	const resolutionOptions = {	1,997✔
56	...defaultResolutionOptions,
57	...rawResolutionOptions
58	}
59	const programs: Record<string, es.Program> = {}	1,997✔
60	const importGraph = new DirectedGraph()	1,997✔
61
62	// If there is more than one file, tag AST nodes with the source file path.
63	const numOfFiles = Object.keys(files).length	1,997✔
64	const shouldAddSourceFileToAST = numOfFiles > 1	1,997✔
65
66	async function resolve(path: string, node?: es.ModuleDeclarationWithSource) {
67	let source: string
68	if (node) {	2,097✔
69	assert(	100✔
70	typeof node.source.value === 'string',
71	`${node.type} should have a source of type string, got ${node.source}`
72	)
73	source = node.source.value	100✔
74	} else {
75	source = path	1,997✔
76	}
77
78	const [resolved, modAbsPath] = await resolveModule(	2,097✔
79	node ? path : '.',	2,097✔
80	source,
81	p => files[p] !== undefined,	2,066✔
82	resolutionOptions
83	)
84	if (!resolved) throw new ModuleNotFoundError(modAbsPath, node)	2,097✔
85	return modAbsPath	2,095✔
86	}
87
88	/**
89	* Process each file (as a module) and determine which other (local and source)
90	* modules are required. This function should always be called with absolute
91	* paths
92	*
93	* @param currentFilePath Current absolute file path of the module
94	*/
95	async function parseFile(currentFilePath: string): Promise<void> {
96	if (currentFilePath in programs) {	2,062✔
97	return	2✔
98	}
99
100	const code = files[currentFilePath]	2,060✔
101	assert(	2,060✔
102	code !== undefined,
103	"Module resolver should've thrown an error if the file path did not resolve"
104	)
105
106	// Tag AST nodes with the source file path for use in error messages.
107	const parserOptions: Partial<AcornOptions> = shouldAddSourceFileToAST	2,060✔
108	? {	2,060✔
109	sourceFile: currentFilePath
110	}
111	: {}
112	const program = parse<AcornOptions>(code, context, parserOptions, false)	2,060✔
113	if (!program) {	2,060✔
114	// Due to a bug in the typed parser where throwOnError isn't respected,
115	// we need to throw a quick exit error here instead
116	throw new PreprocessError()	222✔
117	}
118
119	const dependencies = new Set<string>()	1,838✔
120	programs[currentFilePath] = program	1,838✔
121
122	for (const node of program.body) {	1,838✔
123	if (!isModuleDeclarationWithSource(node)) continue	2,960✔
124
125	const modAbsPath = await resolve(currentFilePath, node)	100✔
126	if (modAbsPath === currentFilePath) {	99✔
127	throw new CircularImportError([modAbsPath, currentFilePath])	2✔
128	}
129
130	dependencies.add(modAbsPath)	97✔
131
132	// Replace the source of the node with the resolved path
133	node.source.value = modAbsPath	97✔
134	}
135
136	await Promise.all(	1,835✔
137	Array.from(dependencies).map(async dependency => {	97✔
138	// There is no need to track Source modules as dependencies, as it can be assumed
139	// that they will always come first in the topological order
140	if (!isSourceImport(dependency)) {	97✔
141	await parseFile(dependency)	66✔
142	// If the edge has already been traversed before, the import graph
143	// must contain a cycle. Then we can exit early and proceed to find the cycle
144	if (importGraph.hasEdge(dependency, currentFilePath)) {	66!
145	throw new PreprocessError()	×
146	}
147
148	importGraph.addEdge(dependency, currentFilePath)	66✔
149	}
150	})
151	)
152	}
153
154	try {	1,997✔
155	// Remember to resolve the entrypoint file too!
156	const entrypointAbsPath = await resolve(entrypointFilePath)	1,997✔
157	await parseFile(entrypointAbsPath)	1,996✔
158	} catch (error) {
159	if (!(error instanceof PreprocessError)) {	226✔
160	context.errors.push(error)	4✔
161	}
162	}
163
164	return {	1,997✔
165	programs,
166	importGraph
167	}
168	}
169
170	export type PreprocessOptions = {
171	allowUndefinedImports?: boolean
172	} & ImportResolutionOptions
173
174	const defaultOptions: Required<PreprocessOptions> = {	52✔
175	...defaultResolutionOptions,
176	allowUndefinedImports: false
177	}
178
179	/**
180	* Preprocesses file imports and returns a transformed Abstract Syntax Tree (AST).
181	* If an error is encountered at any point, returns `undefined` to signify that an
182	* error occurred. Details of the error can be found inside `context.errors`.
183	*
184	* The preprocessing works by transforming each imported file into a function whose
185	* parameters are other files (results of transformed functions) and return value
186	* is a pair where the head is the default export or null, and the tail is a list
187	* of pairs that map from exported names to identifiers.
188	*
189	* See https://github.com/source-academy/js-slang/wiki/Local-Module-Import-&-Export
190	* for more information.
191	*
192	* @param files An object mapping absolute file paths to file content.
193	* @param entrypointFilePath The absolute path of the entrypoint file.
194	* @param context The information associated with the program evaluation.
195	*/
196	const preprocessFileImports = async (	52✔
197	files: Partial<Record<string, string>>,
198	entrypointFilePath: string,
199	context: Context,
200	rawOptions: Partial<PreprocessOptions> = {}	326✔
201	): Promise<es.Program \| undefined> => {	1,936✔
202	const { allowUndefinedImports, ...resolutionOptions } = {	1,936✔
203	...defaultOptions,
204	...rawOptions
205	}
206
207	// Parse all files into ASTs and build the import graph.
208	const { programs, importGraph } = await parseProgramsAndConstructImportGraph(	1,936✔
209	files,
210	entrypointFilePath,
211	context,
212	resolutionOptions
213	)
214
215	// Return 'undefined' if there are errors while parsing.
216	if (context.errors.length !== 0) {	1,936✔
217	return undefined	220✔
218	}
219
220	// Check for circular imports.
221	const topologicalOrderResult = importGraph.getTopologicalOrder()	1,716✔
222	if (!topologicalOrderResult.isValidTopologicalOrderFound) {	1,716✔
223	context.errors.push(new CircularImportError(topologicalOrderResult.firstCycleFound))	2✔
224	return undefined	2✔
225	}
226
227	let newPrograms: Record<string, es.Program> = {}	1,714✔
228	try {	1,714✔
229	// Based on how the import graph is constructed, it could be the case that the entrypoint
230	// file is never included in the topo order. This is only an issue for the import export
231	// analyzer, hence the following code
232	const fullTopoOrder = topologicalOrderResult.topologicalOrder	1,714✔
233	if (!fullTopoOrder.includes(entrypointFilePath)) {	1,714✔
234	// Since it's the entrypoint, it must be loaded last
235	fullTopoOrder.push(entrypointFilePath)	1,711✔
236	}
237
238	// This check is performed after cycle detection because if we tried to resolve export symbols
239	// and there is a cycle in the import graph the constructImportGraph function may end up in an
240	// infinite loop
241	// For example, a.js: export * from './b.js' and b.js: export * from './a.js'
242	// Then trying to discover what symbols are exported by a.js will require determining what symbols
243	// b.js exports, which would in turn require the symbols exported by a.js
244	// If the topological order exists, then this is guaranteed not to occur
245	newPrograms = await analyzeImportsAndExports(programs, fullTopoOrder, allowUndefinedImports)	1,714✔
246	} catch (error) {
247	context.errors.push(error)	1✔
248	return undefined	1✔
249	}
250
251	// We want to operate on the entrypoint program to get the eventual
252	// preprocessed program.
253	const entrypointProgram = newPrograms[entrypointFilePath]	1,713✔
254	const entrypointDirPath = pathlib.resolve(entrypointFilePath, '..')	1,713✔
255
256	// Create variables to hold the imported statements.
257	const entrypointProgramModuleDeclarations = entrypointProgram.body.filter(isModuleDeclaration)	1,713✔
258	const entrypointProgramInvokedFunctionResultVariableNameToImportSpecifiersMap =
259	getInvokedFunctionResultVariableNameToImportSpecifiersMap(	1,713✔
260	entrypointProgramModuleDeclarations,
261	entrypointDirPath
262	)
263	const entrypointProgramAccessImportStatements = createAccessImportStatements(	1,713✔
264	entrypointProgramInvokedFunctionResultVariableNameToImportSpecifiersMap
265	)
266
267	// Transform all programs into their equivalent function declaration
268	// except for the entrypoint program.
269	const [functionDeclarations, invokedFunctionResultVariableDeclarations] =
270	topologicalOrderResult.topologicalOrder	1,713✔
271	// The entrypoint program does not need to be transformed into its
272	// function declaration equivalent as its enclosing environment is
273	// simply the overall program's (constructed program's) environment.
274	.filter(path => path !== entrypointFilePath)	1,719✔
275	.reduce(
276	([funcDecls, invokeDecls], filePath) => {
277	const program = newPrograms[filePath]	6✔
278	const functionDeclaration = transformProgramToFunctionDeclaration(program, filePath)	6✔
279
280	const functionName = functionDeclaration.id.name	6✔
281	const invokedFunctionResultVariableName =
282	transformFunctionNameToInvokedFunctionResultVariableName(functionName)	6✔
283
284	const functionParams = functionDeclaration.params.filter(isIdentifier)	6✔
285	assert(	6✔
286	functionParams.length === functionDeclaration.params.length,
287	'Function declaration contains non-Identifier AST nodes as params. This should never happen.'
288	)
289
290	// Invoke each of the transformed functions and store the result in a variable.
291	const invokedFunctionResultVariableDeclaration =
292	createInvokedFunctionResultVariableDeclaration(	6✔
293	functionName,
294	invokedFunctionResultVariableName,
295	functionParams
296	)
297
298	return [	6✔
299	[...funcDecls, functionDeclaration],
300	[...invokeDecls, invokedFunctionResultVariableDeclaration]
301	]
302	},
303	[[], []] as [es.FunctionDeclaration[], es.VariableDeclaration[]]
304	)
305
306	// Re-assemble the program.
307	const preprocessedProgram: es.Program = {	1,713✔
308	...entrypointProgram,
309	body: [
310	...functionDeclarations,
311	...invokedFunctionResultVariableDeclarations,
312	...entrypointProgramAccessImportStatements,
313	...entrypointProgram.body
314	]
315	}
316
317	// console.log(generate(preprocessedProgram))
318
319	// Import and Export related nodes are no longer necessary, so we can remove them from the program entirely
320	removeImportsAndExports(preprocessedProgram)	1,713✔
321
322	// Finally, we need to hoist all remaining imports to the top of the
323	// program. These imports should be source module imports since
324	// non-Source module imports would have already been removed. As part
325	// of this step, we also merge imports from the same module so as to
326	// import each unique name per module only once.
327	hoistAndMergeImports(preprocessedProgram, newPrograms)	1,713✔
328	return preprocessedProgram	1,713✔
329	}
330
331	export default preprocessFileImports	52✔

source-academy / js-slang / 5406352152

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