/
code-path.js
342 lines (297 loc) · 11.5 KB
/
code-path.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
/**
* @fileoverview A class of the code path.
* @author Toru Nagashima
*/
"use strict";
//------------------------------------------------------------------------------
// Requirements
//------------------------------------------------------------------------------
const CodePathState = require("./code-path-state");
const IdGenerator = require("./id-generator");
//------------------------------------------------------------------------------
// Public Interface
//------------------------------------------------------------------------------
/**
* A code path.
*/
class CodePath {
/**
* Creates a new instance.
* @param {Object} options Options for the function (see below).
* @param {string} options.id An identifier.
* @param {string} options.origin The type of code path origin.
* @param {CodePath|null} options.upper The code path of the upper function scope.
* @param {Function} options.onLooped A callback function to notify looping.
*/
constructor({ id, origin, upper, onLooped }) {
/**
* The identifier of this code path.
* Rules use it to store additional information of each rule.
* @type {string}
*/
this.id = id;
/**
* The reason that this code path was started. May be "program",
* "function", "class-field-initializer", or "class-static-block".
* @type {string}
*/
this.origin = origin;
/**
* The code path of the upper function scope.
* @type {CodePath|null}
*/
this.upper = upper;
/**
* The code paths of nested function scopes.
* @type {CodePath[]}
*/
this.childCodePaths = [];
// Initializes internal state.
Object.defineProperty(
this,
"internal",
{ value: new CodePathState(new IdGenerator(`${id}_`), onLooped) }
);
// Adds this into `childCodePaths` of `upper`.
if (upper) {
upper.childCodePaths.push(this);
}
}
/**
* Gets the state of a given code path.
* @param {CodePath} codePath A code path to get.
* @returns {CodePathState} The state of the code path.
*/
static getState(codePath) {
return codePath.internal;
}
/**
* The initial code path segment. This is the segment that is at the head
* of the code path.
* This is a passthrough to the underlying `CodePathState`.
* @type {CodePathSegment}
*/
get initialSegment() {
return this.internal.initialSegment;
}
/**
* Final code path segments. These are the terminal (tail) segments in the
* code path, which is the combination of `returnedSegments` and `thrownSegments`.
* All segments in this array are reachable.
* This is a passthrough to the underlying `CodePathState`.
* @type {CodePathSegment[]}
*/
get finalSegments() {
return this.internal.finalSegments;
}
/**
* Final code path segments that represent normal completion of the code path.
* For functions, this means both explicit `return` statements and implicit returns,
* such as the last reachable segment in a function that does not have an
* explicit `return` as this implicitly returns `undefined`. For scripts,
* modules, class field initializers, and class static blocks, this means
* all lines of code have been executed.
* These segments are also present in `finalSegments`.
* This is a passthrough to the underlying `CodePathState`.
* @type {CodePathSegment[]}
*/
get returnedSegments() {
return this.internal.returnedForkContext;
}
/**
* Final code path segments that represent `throw` statements.
* This is a passthrough to the underlying `CodePathState`.
* These segments are also present in `finalSegments`.
* @type {CodePathSegment[]}
*/
get thrownSegments() {
return this.internal.thrownForkContext;
}
/**
* Tracks the traversal of the code path through each segment. This array
* starts empty and segments are added or removed as the code path is
* traversed. This array always ends up empty at the end of a code path
* traversal. The `CodePathState` uses this to track its progress through
* the code path.
* This is a passthrough to the underlying `CodePathState`.
* @type {CodePathSegment[]}
* @deprecated
*/
get currentSegments() {
return this.internal.currentSegments;
}
/**
* Traverses all segments in this code path.
*
* codePath.traverseSegments((segment, controller) => {
* // do something.
* });
*
* This method enumerates segments in order from the head.
*
* The `controller` argument has two methods:
*
* - `skip()` - skips the following segments in this branch
* - `break()` - skips all following segments in the traversal
*
* A note on the parameters: the `options` argument is optional. This means
* the first argument might be an options object or the callback function.
* @param {Object} [optionsOrCallback] Optional first and last segments to traverse.
* @param {CodePathSegment} [optionsOrCallback.first] The first segment to traverse.
* @param {CodePathSegment} [optionsOrCallback.last] The last segment to traverse.
* @param {Function} callback A callback function.
* @returns {void}
*/
traverseSegments(optionsOrCallback, callback) {
// normalize the arguments into a callback and options
let resolvedOptions;
let resolvedCallback;
if (typeof optionsOrCallback === "function") {
resolvedCallback = optionsOrCallback;
resolvedOptions = {};
} else {
resolvedOptions = optionsOrCallback || {};
resolvedCallback = callback;
}
// determine where to start traversing from based on the options
const startSegment = resolvedOptions.first || this.internal.initialSegment;
const lastSegment = resolvedOptions.last;
// set up initial location information
let record = null;
let index = 0;
let end = 0;
let segment = null;
// segments that have already been visited during traversal
const visited = new Set();
// tracks the traversal steps
const stack = [[startSegment, 0]];
// tracks the last skipped segment during traversal
let skippedSegment = null;
// indicates if we exited early from the traversal
let broken = false;
/**
* Maintains traversal state.
*/
const controller = {
/**
* Skip the following segments in this branch.
* @returns {void}
*/
skip() {
if (stack.length <= 1) {
broken = true;
} else {
skippedSegment = stack[stack.length - 2][0];
}
},
/**
* Stop traversal completely - do not traverse to any
* other segments.
* @returns {void}
*/
break() {
broken = true;
}
};
/**
* Checks if a given previous segment has been visited.
* @param {CodePathSegment} prevSegment A previous segment to check.
* @returns {boolean} `true` if the segment has been visited.
*/
function isVisited(prevSegment) {
return (
visited.has(prevSegment) ||
segment.isLoopedPrevSegment(prevSegment)
);
}
// the traversal
while (stack.length > 0) {
/*
* This isn't a pure stack. We use the top record all the time
* but don't always pop it off. The record is popped only if
* one of the following is true:
*
* 1) We have already visited the segment.
* 2) We have not visited *all* of the previous segments.
* 3) We have traversed past the available next segments.
*
* Otherwise, we just read the value and sometimes modify the
* record as we traverse.
*/
record = stack[stack.length - 1];
segment = record[0];
index = record[1];
if (index === 0) {
// Skip if this segment has been visited already.
if (visited.has(segment)) {
stack.pop();
continue;
}
// Skip if all previous segments have not been visited.
if (segment !== startSegment &&
segment.prevSegments.length > 0 &&
!segment.prevSegments.every(isVisited)
) {
stack.pop();
continue;
}
// Reset the skipping flag if all branches have been skipped.
if (skippedSegment && segment.prevSegments.includes(skippedSegment)) {
skippedSegment = null;
}
visited.add(segment);
/*
* If the most recent segment hasn't been skipped, then we call
* the callback, passing in the segment and the controller.
*/
if (!skippedSegment) {
resolvedCallback.call(this, segment, controller);
// exit if we're at the last segment
if (segment === lastSegment) {
controller.skip();
}
/*
* If the previous statement was executed, or if the callback
* called a method on the controller, we might need to exit the
* loop, so check for that and break accordingly.
*/
if (broken) {
break;
}
}
}
// Update the stack.
end = segment.nextSegments.length - 1;
if (index < end) {
/*
* If we haven't yet visited all of the next segments, update
* the current top record on the stack to the next index to visit
* and then push a record for the current segment on top.
*
* Setting the current top record's index lets us know how many
* times we've been here and ensures that the segment won't be
* reprocessed (because we only process segments with an index
* of 0).
*/
record[1] += 1;
stack.push([segment.nextSegments[index], 0]);
} else if (index === end) {
/*
* If we are at the last next segment, then reset the top record
* in the stack to next segment and set its index to 0 so it will
* be processed next.
*/
record[0] = segment.nextSegments[index];
record[1] = 0;
} else {
/*
* If index > end, that means we have no more segments that need
* processing. So, we pop that record off of the stack in order to
* continue traversing at the next level up.
*/
stack.pop();
}
}
}
}
module.exports = CodePath;