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

86.21

/src/tracer/nodes/Expression/BlockExpression.ts

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

// TODO: add docs, because this is a block expression, not a block statement, and this does not follow official estree spec
export class StepperBlockExpression implements 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 StepperBlockExpression(node.body.map(ast => convert(ast) as StepperStatement))
  }

  isContractible(): boolean {
    return (
      this.body.length === 0 ||
      (this.body.length === 1 && !this.body[0].isOneStepPossible()) || // { 1; } -> undefined;
      this.body[0].type === 'ReturnStatement'
    )
  }

  isOneStepPossible(): boolean {
    return this.isContractible() || this.body[0].isOneStepPossible() || this.body.length >= 2
  }

  contract(): StepperExpression | typeof undefinedNode {
    if (this.body.length === 0 || (this.body.length === 1 && !this.body[0].isOneStepPossible())) {
      redex.preRedex = [this]
      redex.postRedex = []
      return undefinedNode
    }

    if (this.body[0].type === 'ReturnStatement') {
      const returnStmt = this.body[0] as StepperReturnStatement
      returnStmt.contract()
      return returnStmt.argument || undefinedNode
    }
    throw new Error('Cannot contract block expression ' + JSON.stringify(this.isContractible()))
  }

  oneStep(): StepperBlockExpression | typeof undefinedNode | StepperExpression {
    if (this.isContractible()) {
      return this.contract()
    }
    // 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 StepperBlockExpression(
          [afterSubstitutedScope].flat(),
          this.innerComments,
          this.leadingComments,
          this.trailingComments,
          this.loc,
          this.range
        )
      }
      return new StepperBlockExpression(
        [firstStatementOneStep as StepperStatement, ...afterSubstitutedScope],
        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 StepperBlockExpression(
        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 StepperBlockExpression(
        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 StepperBlockExpression(
        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 StepperBlockExpression(
          [firstValueStatement, afterSubstitutedScope].flat(),
          this.innerComments,
          this.leadingComments,
          this.trailingComments,
          this.loc,
          this.range
        )
      }
      return new StepperBlockExpression(
        [
          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 StepperBlockExpression(
        [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 StepperBlockExpression(
        [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 StepperBlockExpression(
      this.body.slice(1),
      this.innerComments,
      this.leadingComments,
      this.trailingComments,
      this.loc,
      this.range
    )
  }

  substitute(id: StepperPattern, value: StepperExpression): StepperBlockExpression {
    const valueFreeNames = value.freeNames()
    const scopeNames = this.scanAllDeclarationNames()
    const repeatedNames = valueFreeNames.filter(name => scopeNames.includes(name))
    let protectedNamesSet = new Set(this.allNames())
    repeatedNames.forEach(name => protectedNamesSet.delete(name))
    const protectedNames = Array.from(protectedNamesSet)
    const newNames = getFreshName(repeatedNames, protectedNames)

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

    if (currentBlockExpression.scanAllDeclarationNames().includes(id.name)) {
      return currentBlockExpression
    }
    return new StepperBlockExpression(
      currentBlockExpression.body.map(
        statement => statement.substitute(id, value) as StepperStatement
      ),
      currentBlockExpression.innerComments,
      currentBlockExpression.leadingComments,
      currentBlockExpression.trailingComments,
      currentBlockExpression.loc,
      currentBlockExpression.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): StepperBlockExpression {
    return new StepperBlockExpression(
      this.body.map(statement => statement.rename(before, after) as StepperStatement),
      this.innerComments,
      this.leadingComments,
      this.trailingComments,
      this.loc,
      this.range
    )
  }
}

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

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