Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 3224x 29x 3224x 18569x 12928x 12928x 25713x 25713x 23286x 6661x 25713x 6661x 6267x 31497x 31497x 31497x 89709x 89709x 31497x 58212x 58212x 89709x 89709x 89709x 89709x 81422x 81422x 68912x 68912x 12510x 89709x 10563x 10563x 10563x 3403x 7339x 2514x 10563x 10742x 7339x 7339x 3403x 3403x 3403x 10563x 3403x 345x 345x 3403x 3403x 3403x 208538x 6666x 58968x | /**
* #1668 / #1664: 1.4 Resolve's half of the lexical frames, and the questions
* later passes ask of them.
*
* 1.3 recorded what each frame declares from one file's tree. Settling needs
* the whole program: a bare type may name a scope type another file declares
* (ADR-057), and a const local folds with whatever its names bind to. After
* this, a frame is frozen and every pass reads the same one.
*
* Positions compare as `(line, column)`. Stage 4d and Stage 5 reuse Stage 3's
* parse, so a node's position is the same in every pass.
*/
import ConstantFold from "../../utils/ConstantFold";
import DeferredTypes from "./DeferredTypes";
import type IConstantEnvironment from "../../utils/types/IConstantEnvironment";
import type TConstExpr from "../../types/TConstExpr";
import type TConstResult from "../../types/TConstResult";
import type ILexicalFrame from "../../types/ILexicalFrame";
import type ILocalDeclaration from "../../types/ILocalDeclaration";
import type ISourceSpan from "../../types/ISourceSpan";
/** A use's position */
type TPosition = Pick<ISourceSpan, "line" | "column">;
/**
* What a name in a constant expression is worth where it is written, as the
* program's binder decides it (#1175: the whole chain, not a bare name).
* `settled` answers for a local the binder returns: the frames the binder
* walks are the unsettled ones, and a local's value is known once its own
* declaration has been settled, which source order guarantees for every
* local a use can bind.
*/
type TValueOf = (
name: Extract<TConstExpr, { kind: "name" }>,
settled: (declaration: ILocalDeclaration) => ILocalDeclaration | undefined,
) => TConstResult;
class LexicalFrames {
/**
* The settled, frozen copy of a file's frames.
*
* @param isScopeType the whole program's ADR-057 answer
* @param valueOf a name's value where it is written, from the one binder
*/
static settle(
frame: ILexicalFrame,
isScopeType: (qualifiedName: string) => boolean,
valueOf: TValueOf,
/** A type name as C spells it where it is written (ADR-057) */
cTypeName: IConstantEnvironment["cTypeName"],
/**
* Filled with each declaration's settled copy, for a caller that must read
* the same answer -- a function's parameters, which the header writes
* (#1863 review: settled twice, `b[4]` in the .c was `b[0]` in the .h)
*/
settledOf: Map<ILocalDeclaration, ILocalDeclaration> = new Map(),
): ILexicalFrame {
const env: IConstantEnvironment = {
valueOf: (name) =>
valueOf(name, (declaration) => settledOf.get(declaration)),
cTypeName,
};
return LexicalFrames.settleFrame(frame, isScopeType, env, settledOf);
}
/** The innermost frame containing `at`; the file frame if none does */
static frameAt(root: ILexicalFrame, at: TPosition): ILexicalFrame {
return LexicalFrames.pathTo(root, at).at(-1) ?? root;
}
/**
* The declaration `name` binds to at `at`: in each frame from the innermost
* outward, the last declaration of `name` that starts before `at`. A later
* declaration in the same block does not bind an earlier use (#1702), and a
* sibling block's declaration is never visible (#1666).
*/
static declarationAt(
root: ILexicalFrame,
name: string,
at: TPosition,
): ILocalDeclaration | null {
const path = LexicalFrames.pathTo(root, at);
for (let i = path.length - 1; i >= 0; i--) {
// The LAST matching declaration: a redeclaration in the same frame wins
const declarations = path[i].declarations;
let found: ILocalDeclaration | undefined;
for (const declaration of declarations) {
if (
declaration.name === name &&
LexicalFrames.before(declaration.span, at)
) {
found = declaration;
}
}
if (found) {
return found;
}
}
return null;
}
/** The frames containing `at`, outermost first */
private static pathTo(root: ILexicalFrame, at: TPosition): ILexicalFrame[] {
const path = [root];
let current = root;
for (;;) {
const child = LexicalFrames.childAt(current, at);
if (!child) {
return path;
}
path.push(child);
current = child;
}
}
/**
* The child frame containing `at`, if one does. Children are in source
* order and never overlap, so the only candidate is the last that starts
* at or before `at`, found by binary search. #1760 second review: a
* linear scan here ran for every binding, so a file of N functions took
* O(N^2) -- 2000 functions compiled in 15s against main's 5s.
*/
private static childAt(
frame: ILexicalFrame,
at: TPosition,
): ILexicalFrame | undefined {
const children = frame.children;
let low = 0;
let high = children.length - 1;
let candidate: ILexicalFrame | undefined;
while (low <= high) {
const middle = (low + high) >> 1;
if (LexicalFrames.compare(children[middle].span, at) <= 0) {
candidate = children[middle];
low = middle + 1;
} else {
high = middle - 1;
}
}
return candidate !== undefined && LexicalFrames.contains(candidate.span, at)
? candidate
: undefined;
}
private static settleFrame(
frame: ILexicalFrame,
isScopeType: (qualifiedName: string) => boolean,
env: IConstantEnvironment,
settledOf: Map<ILocalDeclaration, ILocalDeclaration>,
): ILexicalFrame {
// Declarations and child frames in source order, so each local is
// settled before any use that can bind it.
const declarations: ILocalDeclaration[] = [];
const children: ILexicalFrame[] = [];
const items = [
...frame.declarations.map((d) => ({ span: d.span, declaration: d })),
...frame.children.map((f) => ({ span: f.span, child: f })),
].sort((a, b) => LexicalFrames.compare(a.span, b.span));
for (const item of items) {
if ("child" in item) {
children.push(
LexicalFrames.settleFrame(item.child, isScopeType, env, settledOf),
);
continue;
}
const settled = LexicalFrames.settleDeclaration(
item.declaration,
isScopeType,
env,
);
settledOf.set(item.declaration, settled);
declarations.push(settled);
}
return Object.freeze({
...frame,
declarations: Object.freeze(declarations),
children: Object.freeze(children),
});
}
/**
* #1760 review: a declaration's own dimensions come before its name, so
* they see the enclosing binding (`u8[N] N`). Its initializer comes after
* the name and sees the new one, as C scopes it and as emission binds it,
* so a const that names itself has no value; whether it is allowed at all
* is #1643's. Folding both at the name's start gave `const u16 N <- N + 1`
* the value 5 while the C read the uninitialized local.
*
* #1175: each name in a dimension or an initializer carries its own
* position, and binds there -- which is that rule, with nothing to pick.
*/
private static settleDeclaration(
declaration: ILocalDeclaration,
isScopeType: (qualifiedName: string) => boolean,
env: IConstantEnvironment,
): ILocalDeclaration {
const arrayDimensions = declaration.arrayDimensions.map((dimension, i) => {
const expr = declaration.arrayDimensionExprs[i];
return expr ? ConstantFold.dimension(expr, env) : dimension;
});
const type = DeferredTypes.settleType(declaration.type, isScopeType);
const constValue =
declaration.isConst &&
declaration.initialValueExpr !== null &&
arrayDimensions.length === 0
? ConstantFold.constValue(declaration.initialValueExpr, env, type)
: null;
return Object.freeze({
...declaration,
type,
arrayDimensions: Object.freeze(arrayDimensions),
constValue,
});
}
private static compare(a: TPosition, b: TPosition): number {
return a.line === b.line ? a.column - b.column : a.line - b.line;
}
/** Whether a span starts strictly before a position */
private static before(span: ISourceSpan, at: TPosition): boolean {
return LexicalFrames.compare(span, at) < 0;
}
/** Whether a position lies in a span, whose end is exclusive (ISourceSpan) */
private static contains(span: ISourceSpan, at: TPosition): boolean {
return (
LexicalFrames.compare(span, at) <= 0 &&
LexicalFrames.compare(at, {
line: span.endLine,
column: span.endColumn,
}) < 0
);
}
}
export default LexicalFrames;
|