15235726114

Committed 25 May 2025 07:55AM UTC coverage: 77.048%. First build

Build # 15235726114

Build Type

Pull #1742

github

Committed by

web-flow

Commit Message

Merge d7783cf1e into 0be74e78c

Pull Request Pull Request #1742: Rewrite: Stepper

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%)

10099 of 12737 relevant lines covered (79.29%)

140954.8 hits per line

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

85.03

/src/tracer/nodes/Statement/BlockStatement.ts

import { BlockStatement, Comment, SourceLocation } from 'estree'
import { StepperBaseNode } from '../../interface'
import { StepperExpression, StepperPattern, undefinedNode } from '..'
import { convert } from '../../generator'
import { redex } from '../..'
import { assignMuTerms, getFreshName } from '../../utils'
import { StepperVariableDeclaration } from './VariableDeclaration'
import { StepperFunctionDeclaration } from './FunctionDeclaration'
import { StepperReturnStatement } from './ReturnStatement'
import { StepperStatement } from '.'

export class StepperBlockStatement implements BlockStatement, StepperBaseNode {
  type: 'BlockStatement'
  body: StepperStatement[]
  innerComments?: Comment[] | undefined
  leadingComments?: Comment[] | undefined
  trailingComments?: Comment[] | undefined
  loc?: SourceLocation | null | undefined
  range?: [number, number] | undefined

  constructor(
    body: StepperStatement[],
    innerComments?: Comment[] | undefined,
    leadingComments?: Comment[] | undefined,
    trailingComments?: Comment[] | undefined,
    loc?: SourceLocation | null | undefined,
    range?: [number, number] | undefined
  ) {
    this.type = 'BlockStatement'
    this.body = body
    this.innerComments = innerComments
    this.leadingComments = leadingComments
    this.trailingComments = trailingComments
    this.loc = loc
    this.range = range
  }

  static create(node: BlockStatement) {
    return new StepperBlockStatement(
      node.body.map(ast => convert(ast) as StepperStatement),
      node.innerComments,
      node.leadingComments,
      node.trailingComments,
      node.loc,
      node.range
    )
  }

  isContractible(): boolean {
    return this.body.length === 0 || (this.body.length === 1 && !this.body[0].isContractible())
  }

  isOneStepPossible(): boolean {
    return true
  }

  contract(): StepperBlockStatement | StepperStatement | typeof undefinedNode {
    if (this.body.length === 0) {
      redex.preRedex = [this]
      redex.postRedex = []
      return undefinedNode
    }

    if (this.body.length === 1) {
      redex.preRedex = [this]
      redex.postRedex = [this.body[0]]
      return this.body[0]
    }

    throw new Error('Not implemented')
  }

  contractEmpty() {
    redex.preRedex = [this]
    redex.postRedex = []
  }

  oneStep(): StepperBlockStatement | StepperStatement | typeof undefinedNode {
    if (this.isContractible()) {
      return this.contract()
    }

    if (this.body[0].type === 'ReturnStatement') {
      const returnStmt = this.body[0] as StepperReturnStatement
      redex.preRedex = [this]
      redex.postRedex = [returnStmt]
      return returnStmt
    }

    // reduce the first statement
    if (this.body[0].isOneStepPossible()) {
      const firstStatementOneStep = this.body[0].oneStep()
      const afterSubstitutedScope = this.body.slice(1)
      if (firstStatementOneStep === undefinedNode) {
        return new StepperBlockStatement(
          [afterSubstitutedScope].flat(),
          this.innerComments,
          this.leadingComments,
          this.trailingComments,
          this.loc,
          this.range
        )
      }
      return new StepperBlockStatement(
        [firstStatementOneStep as StepperStatement, afterSubstitutedScope].flat(),
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
    }

    // If the first statement is constant declaration, gracefully handle it!
    if (this.body[0].type == 'VariableDeclaration') {
      const declarations = assignMuTerms(this.body[0].declarations)
      const afterSubstitutedScope = this.body
        .slice(1)
        .map(current =>
          declarations
            .filter(declarator => declarator.init)
            .reduce(
              (statement, declarator) =>
                statement.substitute(declarator.id, declarator.init!) as StepperStatement,
              current
            )
        ) as StepperStatement[]
      const substitutedProgram = new StepperBlockStatement(
        afterSubstitutedScope,
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
      redex.preRedex = [this.body[0]]
      redex.postRedex = declarations.map(x => x.id)
      return substitutedProgram
    }

    // If the first statement is function declaration, also gracefully handle it!
    if (this.body[0].type == 'FunctionDeclaration') {
      const arrowFunction = (
        this.body[0] as StepperFunctionDeclaration
      ).getArrowFunctionExpression()
      const functionIdentifier = (this.body[0] as StepperFunctionDeclaration).id
      const afterSubstitutedScope = this.body
        .slice(1)
        .map(
          statement => statement.substitute(functionIdentifier, arrowFunction) as StepperStatement
        ) as StepperStatement[]
      const substitutedProgram = new StepperBlockStatement(
        afterSubstitutedScope,
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
      redex.preRedex = [this.body[0]]
      redex.postRedex = afterSubstitutedScope
      return substitutedProgram
    }

    const firstValueStatement = this.body[0]
    // After this stage, the first statement is a value statement. Now, proceed until getting the second value statement.
    // if the second statement is return statement, remove the first statement
    if (this.body.length >= 2 && this.body[1].type == 'ReturnStatement') {
      redex.preRedex = [this.body[0]]
      const afterSubstitutedScope = this.body.slice(1)
      redex.postRedex = []
      return new StepperBlockStatement(
        afterSubstitutedScope,
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
    }

    if (this.body.length >= 2 && this.body[1].isOneStepPossible()) {
      const secondStatementOneStep = this.body[1].oneStep()
      const afterSubstitutedScope = this.body.slice(2)
      if (secondStatementOneStep === undefinedNode) {
        return new StepperBlockStatement(
          [firstValueStatement, afterSubstitutedScope].flat(),
          this.innerComments,
          this.leadingComments,
          this.trailingComments,
          this.loc,
          this.range
        )
      }
      return new StepperBlockStatement(
        [
          firstValueStatement,
          secondStatementOneStep as StepperStatement,
          afterSubstitutedScope
        ].flat(),
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
    }

    // If the second statement is constant declaration, gracefully handle it!
    if (this.body.length >= 2 && this.body[1].type == 'VariableDeclaration') {
      const declarations = assignMuTerms(this.body[1].declarations)
      const afterSubstitutedScope = this.body
        .slice(2)
        .map(current =>
          declarations
            .filter(declarator => declarator.init)
            .reduce(
              (statement, declarator) =>
                statement.substitute(declarator.id, declarator.init!) as StepperStatement,
              current
            )
        ) as StepperStatement[]
      const substitutedProgram = new StepperBlockStatement(
        [firstValueStatement, afterSubstitutedScope].flat(),
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
      redex.preRedex = [this.body[1]]
      redex.postRedex = declarations.map(x => x.id)
      return substitutedProgram
    }

    // If the second statement is function declaration, also gracefully handle it!
    if (this.body.length >= 2 && this.body[1].type == 'FunctionDeclaration') {
      const arrowFunction = (
        this.body[1] as StepperFunctionDeclaration
      ).getArrowFunctionExpression()
      const functionIdentifier = (this.body[1] as StepperFunctionDeclaration).id
      const afterSubstitutedScope = this.body
        .slice(2)
        .map(
          statement => statement.substitute(functionIdentifier, arrowFunction) as StepperStatement
        ) as StepperStatement[]
      const substitutedProgram = new StepperBlockStatement(
        [firstValueStatement, afterSubstitutedScope].flat(),
        this.innerComments,
        this.leadingComments,
        this.trailingComments,
        this.loc,
        this.range
      )
      redex.preRedex = [this.body[1]]
      redex.postRedex = afterSubstitutedScope
      return substitutedProgram
    }

    // After this stage, we have two value inducing statement. Remove the first one.
    this.body[0].contractEmpty() // update the contracted statement onto redex
    return new StepperBlockStatement(
      this.body.slice(1),
      this.innerComments,
      this.leadingComments,
      this.trailingComments,
      this.loc,
      this.range
    )
  }

  substitute(
    id: StepperPattern,
    value: StepperExpression,
    upperBoundName?: string[]
  ): StepperBaseNode {
    // Alpha renaming
    // Check whether should be renamed
    // Renaming stage should not be counted as one step.
    const valueFreeNames = value.freeNames()
    const scopeNames = this.scanAllDeclarationNames()
    const repeatedNames = valueFreeNames.filter(name => scopeNames.includes(name))
    let protectedNamesSet = new Set([this.allNames(), upperBoundName ?? []].flat())
    repeatedNames.forEach(name => protectedNamesSet.delete(name))
    const protectedNames = Array.from(protectedNamesSet)
    const newNames = getFreshName(repeatedNames, protectedNames)

    const currentBlockStatement = newNames.reduce(
      (current: StepperBlockStatement, name: string, index: number) =>
        current.rename(repeatedNames[index], name) as StepperBlockStatement,
      this
    )

    if (currentBlockStatement.scanAllDeclarationNames().includes(id.name)) {
      // DO nothing
      return currentBlockStatement
    }
    return new StepperBlockStatement(
      currentBlockStatement.body.map(
        statement => statement.substitute(id, value) as StepperStatement
      ),
      this.innerComments,
      this.leadingComments,
      this.trailingComments,
      this.loc,
      this.range
    )
  }

  scanAllDeclarationNames(): string[] {
    return this.body
      .filter(ast => ast.type === 'VariableDeclaration' || ast.type === 'FunctionDeclaration')
      .flatMap((ast: StepperVariableDeclaration | StepperFunctionDeclaration) => {
        if (ast.type === 'VariableDeclaration') {
          return ast.declarations.map(ast => ast.id.name)
        } else {
          // Function Declaration
          return [(ast as StepperFunctionDeclaration).id.name]
        }
      })
  }

  freeNames(): string[] {
    const names = new Set(this.body.flatMap(ast => ast.freeNames()))
    this.scanAllDeclarationNames().forEach(name => names.delete(name))
    return Array.from(names)
  }

  allNames(): string[] {
    return Array.from(new Set(this.body.flatMap(ast => ast.allNames())))
  }

  rename(before: string, after: string): StepperBlockStatement {
    return new StepperBlockStatement(
      this.body.map(statement => statement.rename(before, after) as StepperStatement),
      this.innerComments,
      this.leadingComments,
      this.trailingComments,
      this.loc,
      this.range
    )
  }
}

1	import { BlockStatement, Comment, SourceLocation } from 'estree'
2	import { StepperBaseNode } from '../../interface'
3	import { StepperExpression, StepperPattern, undefinedNode } from '..'	61✔
4	import { convert } from '../../generator'	61✔
5	import { redex } from '../..'	61✔
6	import { assignMuTerms, getFreshName } from '../../utils'	61✔
7	import { StepperVariableDeclaration } from './VariableDeclaration'
8	import { StepperFunctionDeclaration } from './FunctionDeclaration'
9	import { StepperReturnStatement } from './ReturnStatement'
10	import { StepperStatement } from '.'
11
12	export class StepperBlockStatement implements BlockStatement, StepperBaseNode {	61✔
13	type: 'BlockStatement'
14	body: StepperStatement[]
15	innerComments?: Comment[] \| undefined
16	leadingComments?: Comment[] \| undefined
17	trailingComments?: Comment[] \| undefined
18	loc?: SourceLocation \| null \| undefined
19	range?: [number, number] \| undefined
20
21	constructor(
22	body: StepperStatement[],
23	innerComments?: Comment[] \| undefined,
24	leadingComments?: Comment[] \| undefined,
25	trailingComments?: Comment[] \| undefined,
26	loc?: SourceLocation \| null \| undefined,
27	range?: [number, number] \| undefined
28	) {
29	this.type = 'BlockStatement'	2,219✔
30	this.body = body	2,219✔
31	this.innerComments = innerComments	2,219✔
32	this.leadingComments = leadingComments	2,219✔
33	this.trailingComments = trailingComments	2,219✔
34	this.loc = loc	2,219✔
35	this.range = range	2,219✔
36	}
37
38	static create(node: BlockStatement) {
39	return new StepperBlockStatement(	432✔
40	node.body.map(ast => convert(ast) as StepperStatement),	525✔
41	node.innerComments,
42	node.leadingComments,
43	node.trailingComments,
44	node.loc,
45	node.range
46	)
47	}
48
49	isContractible(): boolean {
50	return this.body.length === 0 \|\| (this.body.length === 1 && !this.body[0].isContractible())	237✔
51	}
52
53	isOneStepPossible(): boolean {
54	return true	1,486✔
55	}
56
57	contract(): StepperBlockStatement \| StepperStatement \| typeof undefinedNode {
58	if (this.body.length === 0) {	38✔
59	redex.preRedex = [this]	12✔
60	redex.postRedex = []	12✔
61	return undefinedNode	12✔
62	}
63
64	if (this.body.length === 1) {	26✔
65	redex.preRedex = [this]	26✔
66	redex.postRedex = [this.body[0]]	26✔
67	return this.body[0]	26✔
68	}
69
NEW 70	throw new Error('Not implemented')	×
71	}
72
73	contractEmpty() {
NEW 74	redex.preRedex = [this]	×
NEW 75	redex.postRedex = []	×
76	}
77
78	oneStep(): StepperBlockStatement \| StepperStatement \| typeof undefinedNode {
79	if (this.isContractible()) {	233✔
80	return this.contract()	38✔
81	}
82
83	if (this.body[0].type === 'ReturnStatement') {	195✔
84	const returnStmt = this.body[0] as StepperReturnStatement	12✔
85	redex.preRedex = [this]	12✔
86	redex.postRedex = [returnStmt]	12✔
87	return returnStmt	12✔
88	}
89
90	// reduce the first statement
91	if (this.body[0].isOneStepPossible()) {	183✔
92	const firstStatementOneStep = this.body[0].oneStep()	12✔
93	const afterSubstitutedScope = this.body.slice(1)	12✔
94	if (firstStatementOneStep === undefinedNode) {	12✔
95	return new StepperBlockStatement(	7✔
96	[afterSubstitutedScope].flat(),
97	this.innerComments,
98	this.leadingComments,
99	this.trailingComments,
100	this.loc,
101	this.range
102	)
103	}
104	return new StepperBlockStatement(	5✔
105	[firstStatementOneStep as StepperStatement, afterSubstitutedScope].flat(),
106	this.innerComments,
107	this.leadingComments,
108	this.trailingComments,
109	this.loc,
110	this.range
111	)
112	}
113
114	// If the first statement is constant declaration, gracefully handle it!
115	if (this.body[0].type == 'VariableDeclaration') {	171✔
116	const declarations = assignMuTerms(this.body[0].declarations)	3✔
117	const afterSubstitutedScope = this.body	3✔
118	.slice(1)
119	.map(current =>
120	declarations	6✔
121	.filter(declarator => declarator.init)	6✔
122	.reduce(
123	(statement, declarator) =>
124	statement.substitute(declarator.id, declarator.init!) as StepperStatement,	6✔
125	current
126	)
127	) as StepperStatement[]
128	const substitutedProgram = new StepperBlockStatement(	3✔
129	afterSubstitutedScope,
130	this.innerComments,
131	this.leadingComments,
132	this.trailingComments,
133	this.loc,
134	this.range
135	)
136	redex.preRedex = [this.body[0]]	3✔
137	redex.postRedex = declarations.map(x => x.id)	3✔
138	return substitutedProgram	3✔
139	}
140
141	// If the first statement is function declaration, also gracefully handle it!
142	if (this.body[0].type == 'FunctionDeclaration') {	168!
143	const arrowFunction = (
NEW 144	this.body[0] as StepperFunctionDeclaration	×
145	).getArrowFunctionExpression()
NEW 146	const functionIdentifier = (this.body[0] as StepperFunctionDeclaration).id	×
NEW 147	const afterSubstitutedScope = this.body	×
148	.slice(1)
149	.map(
NEW 150	statement => statement.substitute(functionIdentifier, arrowFunction) as StepperStatement	×
151	) as StepperStatement[]
NEW 152	const substitutedProgram = new StepperBlockStatement(	×
153	afterSubstitutedScope,
154	this.innerComments,
155	this.leadingComments,
156	this.trailingComments,
157	this.loc,
158	this.range
159	)
NEW 160	redex.preRedex = [this.body[0]]	×
NEW 161	redex.postRedex = afterSubstitutedScope	×
NEW 162	return substitutedProgram	×
163	}
164
165	const firstValueStatement = this.body[0]	168✔
166	// After this stage, the first statement is a value statement. Now, proceed until getting the second value statement.
167	// if the second statement is return statement, remove the first statement
168	if (this.body.length >= 2 && this.body[1].type == 'ReturnStatement') {	168✔
169	redex.preRedex = [this.body[0]]	11✔
170	const afterSubstitutedScope = this.body.slice(1)	11✔
171	redex.postRedex = []	11✔
172	return new StepperBlockStatement(	11✔
173	afterSubstitutedScope,
174	this.innerComments,
175	this.leadingComments,
176	this.trailingComments,
177	this.loc,
178	this.range
179	)
180	}
181
182	if (this.body.length >= 2 && this.body[1].isOneStepPossible()) {	157✔
183	const secondStatementOneStep = this.body[1].oneStep()	132✔
184	const afterSubstitutedScope = this.body.slice(2)	132✔
185	if (secondStatementOneStep === undefinedNode) {	132✔
186	return new StepperBlockStatement(	1✔
187	[firstValueStatement, afterSubstitutedScope].flat(),
188	this.innerComments,
189	this.leadingComments,
190	this.trailingComments,
191	this.loc,
192	this.range
193	)
194	}
195	return new StepperBlockStatement(	131✔
196	[
197	firstValueStatement,
198	secondStatementOneStep as StepperStatement,
199	afterSubstitutedScope
200	].flat(),
201	this.innerComments,
202	this.leadingComments,
203	this.trailingComments,
204	this.loc,
205	this.range
206	)
207	}
208
209	// If the second statement is constant declaration, gracefully handle it!
210	if (this.body.length >= 2 && this.body[1].type == 'VariableDeclaration') {	25✔
211	const declarations = assignMuTerms(this.body[1].declarations)	5✔
212	const afterSubstitutedScope = this.body	5✔
213	.slice(2)
214	.map(current =>
215	declarations	4✔
216	.filter(declarator => declarator.init)	4✔
217	.reduce(
218	(statement, declarator) =>
219	statement.substitute(declarator.id, declarator.init!) as StepperStatement,	4✔
220	current
221	)
222	) as StepperStatement[]
223	const substitutedProgram = new StepperBlockStatement(	5✔
224	[firstValueStatement, afterSubstitutedScope].flat(),
225	this.innerComments,
226	this.leadingComments,
227	this.trailingComments,
228	this.loc,
229	this.range
230	)
231	redex.preRedex = [this.body[1]]	5✔
232	redex.postRedex = declarations.map(x => x.id)	5✔
233	return substitutedProgram	5✔
234	}
235
236	// If the second statement is function declaration, also gracefully handle it!
237	if (this.body.length >= 2 && this.body[1].type == 'FunctionDeclaration') {	20!
238	const arrowFunction = (
NEW 239	this.body[1] as StepperFunctionDeclaration	×
240	).getArrowFunctionExpression()
NEW 241	const functionIdentifier = (this.body[1] as StepperFunctionDeclaration).id	×
NEW 242	const afterSubstitutedScope = this.body	×
243	.slice(2)
244	.map(
NEW 245	statement => statement.substitute(functionIdentifier, arrowFunction) as StepperStatement	×
246	) as StepperStatement[]
NEW 247	const substitutedProgram = new StepperBlockStatement(	×
248	[firstValueStatement, afterSubstitutedScope].flat(),
249	this.innerComments,
250	this.leadingComments,
251	this.trailingComments,
252	this.loc,
253	this.range
254	)
NEW 255	redex.preRedex = [this.body[1]]	×
NEW 256	redex.postRedex = afterSubstitutedScope	×
NEW 257	return substitutedProgram	×
258	}
259
260	// After this stage, we have two value inducing statement. Remove the first one.
261	this.body[0].contractEmpty() // update the contracted statement onto redex	20✔
262	return new StepperBlockStatement(	20✔
263	this.body.slice(1),
264	this.innerComments,
265	this.leadingComments,
266	this.trailingComments,
267	this.loc,
268	this.range
269	)
270	}
271
272	substitute(
273	id: StepperPattern,
274	value: StepperExpression,
275	upperBoundName?: string[]
276	): StepperBaseNode {
277	// Alpha renaming
278	// Check whether should be renamed
279	// Renaming stage should not be counted as one step.
280	const valueFreeNames = value.freeNames()	1,557✔
281	const scopeNames = this.scanAllDeclarationNames()	1,557✔
282	const repeatedNames = valueFreeNames.filter(name => scopeNames.includes(name))	1,557✔
283	let protectedNamesSet = new Set([this.allNames(), upperBoundName ?? []].flat())	1,557✔
284	repeatedNames.forEach(name => protectedNamesSet.delete(name))	1,557✔
285	const protectedNames = Array.from(protectedNamesSet)	1,557✔
286	const newNames = getFreshName(repeatedNames, protectedNames)	1,557✔
287
288	const currentBlockStatement = newNames.reduce(	1,557✔
289	(current: StepperBlockStatement, name: string, index: number) =>
NEW 290	current.rename(repeatedNames[index], name) as StepperBlockStatement,	×
291	this
292	)
293
294	if (currentBlockStatement.scanAllDeclarationNames().includes(id.name)) {	1,557✔
295	// DO nothing
296	return currentBlockStatement	15✔
297	}
298	return new StepperBlockStatement(	1,542✔
299	currentBlockStatement.body.map(
300	statement => statement.substitute(id, value) as StepperStatement	1,876✔
301	),
302	this.innerComments,
303	this.leadingComments,
304	this.trailingComments,
305	this.loc,
306	this.range
307	)
308	}
309
310	scanAllDeclarationNames(): string[] {
311	return this.body	5,186✔
312	.filter(ast => ast.type === 'VariableDeclaration' \|\| ast.type === 'FunctionDeclaration')	6,100✔
313	.flatMap((ast: StepperVariableDeclaration \| StepperFunctionDeclaration) => {
314	if (ast.type === 'VariableDeclaration') {	920✔
315	return ast.declarations.map(ast => ast.id.name)	460✔
316	} else {
317	// Function Declaration
318	return [(ast as StepperFunctionDeclaration).id.name]	460✔
319	}
320	})
321	}
322
323	freeNames(): string[] {
324	const names = new Set(this.body.flatMap(ast => ast.freeNames()))	2,288✔
325	this.scanAllDeclarationNames().forEach(name => names.delete(name))	2,072✔
326	return Array.from(names)	2,072✔
327	}
328
329	allNames(): string[] {
330	return Array.from(new Set(this.body.flatMap(ast => ast.allNames())))	5,618✔
331	}
332
333	rename(before: string, after: string): StepperBlockStatement {
334	return new StepperBlockStatement(	33✔
335	this.body.map(statement => statement.rename(before, after) as StepperStatement),	46✔
336	this.innerComments,
337	this.leadingComments,
338	this.trailingComments,
339	this.loc,
340	this.range
341	)
342	}
343	}

source-academy / js-slang / 15235726114

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