Line data Source code
1 : // wok_layout -- stage 2. See wok_layout.h for the rules; this file implements
2 : // them and nothing else.
3 : //
4 : // It includes wok_token.h for the token shape and the continuation-lead
5 : // predicate, and it must never learn what a keyword is. If this file ever
6 : // needs to know a spelling, the design has gone wrong.
7 :
8 : #include "wok_layout.h"
9 :
10 : #include <stdio.h>
11 : #include <string.h>
12 :
13 : typedef struct {
14 : WokToken *out;
15 : usize n, cap;
16 : u32 stack[WOK_LAYOUT_MAX_DEPTH];
17 : u32 top;
18 : WokDiagSink *diag;
19 : } Filter;
20 :
21 980541 : static void put(Filter *f, WokKind k, const WokToken *at) {
22 : // The bound is proved, not hoped for: see invariant 5.
23 980541 : if (f->n >= f->cap) WOK_UNREACHABLE();
24 980541 : f->out[f->n++] = (WokToken){.off = at->off,
25 : .len = 0,
26 980541 : .col = at->col,
27 : .kind = (u8)k,
28 : .word = WW_NONE,
29 : .flags = 0};
30 980541 : }
31 :
32 3969322 : static void put_token(Filter *f, const WokToken *t) {
33 3969322 : if (f->n >= f->cap) WOK_UNREACHABLE();
34 3969322 : f->out[f->n++] = *t;
35 3969322 : }
36 :
37 : // Pop every level deeper than c, emitting a DEDENT for each. Shared by L3 and
38 : // L4 -- the difference between them is what happens AFTER the pop, not during.
39 305759 : static void pop_to(Filter *f, u32 c, const WokToken *at) {
40 473439 : while (f->top > 0 && f->stack[f->top] > c) {
41 167680 : f->top--;
42 167680 : put(f, WT_DEDENT, at);
43 : }
44 305759 : }
45 :
46 106143 : WokTokens wok_layout(WokTokens in, WokArena *arena, WokDiagSink *diag) {
47 106143 : Filter f = {.diag = diag};
48 106143 : f.stack[0] = 1;
49 : // 3n + MAX_DEPTH: each input token contributes itself and at most one
50 : // NEWLINE, total DEDENTs cannot exceed total INDENTs which cannot exceed
51 : // the line count, and EOF closes at most MAX_DEPTH levels.
52 106143 : f.cap = in.n * 3 + WOK_LAYOUT_MAX_DEPTH + 8;
53 106143 : f.out = WOK_NEW_N(arena, WokToken, f.cap);
54 :
55 106143 : u32 bracket = 0;
56 106143 : u32 bracket_block_col = 0;
57 106143 : const WokToken *bracket_open = nullptr;
58 106143 : bool first_logical = true;
59 :
60 3969322 : for (usize i = 0; i < in.n; i++) {
61 3969322 : const WokToken *t = &in.tok[i];
62 :
63 3969322 : if ((WokKind)t->kind == WT_EOF) {
64 106143 : if (bracket > 0 && bracket_open)
65 4779 : wok_diag_add(diag, WOK_E_LAY_BRACKET, bracket_open->off, 1,
66 : "unclosed bracket; it is still open at end of file");
67 106143 : if (!first_logical) put(&f, WT_NEWLINE, t);
68 106143 : pop_to(&f, 0, t);
69 106143 : put_token(&f, t);
70 106143 : break;
71 : }
72 :
73 3863179 : if ((t->flags & WOK_TF_FIRST_ON_LINE) != 0) {
74 : // L7 -- bracket abandonment. Layout is suppressed inside brackets, so an
75 : // unclosed opener would otherwise swallow the rest of the file into one
76 : // logical line. Indentation is the independent witness that survives:
77 : // a line STARTING AN ITEM at or left of the block column that was
78 : // current when the bracket opened cannot be inside it.
79 737604 : if (bracket > 0 && !wok_token_is_continuation_lead(t) &&
80 8202 : t->col <= bracket_block_col) {
81 5926 : wok_diag_add(diag, WOK_E_LAY_BRACKET, bracket_open->off, 1,
82 : "unclosed bracket; a new item begins at column %u, "
83 : "which cannot be inside it",
84 : t->col);
85 5926 : bracket = 0;
86 5926 : bracket_open = nullptr;
87 : }
88 :
89 5926 : if (bracket == 0) {
90 731607 : u32 c = t->col;
91 731607 : if (wok_token_is_continuation_lead(t)) {
92 : // L4/L5. Close deeper regions, emit NO item separator, and do NOT
93 : // check the landing column: a continuation is not claiming to start
94 : // anything at a level, so there is no level for it to match. This
95 : // is what admits a hanging `in`, a leading `|`, a leading `+`.
96 106882 : pop_to(&f, c, t);
97 : } else {
98 : // L3. A new item.
99 624725 : if (!first_logical) put(&f, WT_NEWLINE, t);
100 624725 : if (c > f.stack[f.top]) {
101 157825 : if (f.top + 1 >= WOK_LAYOUT_MAX_DEPTH) {
102 0 : wok_diag_add(diag, WOK_E_LAY_DEPTH, t->off, t->len,
103 : "indentation nested deeper than %d levels",
104 : WOK_LAYOUT_MAX_DEPTH);
105 : } else {
106 157825 : f.stack[++f.top] = c;
107 157825 : put(&f, WT_INDENT, t);
108 : }
109 466900 : } else if (c < f.stack[f.top]) {
110 92734 : pop_to(&f, c, t);
111 92734 : if (f.stack[f.top] != c) {
112 : // L6 -- repaired here, never forwarded. An inconsistent dedent
113 : // is not a grammar error and must not reach the parser.
114 9855 : wok_diag_add(diag, WOK_E_LAY_DEDENT, t->off, t->len,
115 : "this line starts at column %u, which matches no "
116 : "open indentation level (nearest is %u)",
117 9855 : t->col, f.stack[f.top]);
118 9855 : if (f.top + 1 < WOK_LAYOUT_MAX_DEPTH) {
119 9855 : f.stack[++f.top] = c;
120 9855 : put(&f, WT_INDENT, t); // keeps the stream balanced
121 : }
122 : }
123 : }
124 : }
125 : first_logical = false;
126 : }
127 : }
128 :
129 3863179 : if (wok_kind_is_open_bracket((WokKind)t->kind)) {
130 239243 : if (bracket == 0) {
131 199296 : bracket_block_col = f.stack[f.top];
132 199296 : bracket_open = t;
133 : }
134 239243 : bracket++;
135 3623936 : } else if (wok_kind_is_close_bracket((WokKind)t->kind)) {
136 237324 : if (bracket > 0) {
137 226296 : bracket--;
138 226296 : if (bracket == 0) bracket_open = nullptr;
139 : }
140 : }
141 :
142 3863179 : put_token(&f, t);
143 : }
144 :
145 106143 : return (WokTokens){.tok = f.out, .n = f.n};
146 : }
147 :
148 : // ------------------------------------------------------------ invariants
149 :
150 63960 : bool wok_layout_check(WokTokens out, usize input_n, bool strict_brackets,
151 : char *err, usize err_len) {
152 : #define FAIL(...) \
153 : do { \
154 : snprintf(err, err_len, __VA_ARGS__); \
155 : return false; \
156 : } while (0)
157 :
158 63960 : if (out.n == 0) FAIL("empty output stream");
159 63960 : if (out.tok[out.n - 1].kind != WT_EOF) FAIL("stream does not end at WT_EOF");
160 63960 : if (out.n > input_n * 3 + WOK_LAYOUT_MAX_DEPTH + 8)
161 0 : FAIL("invariant 5: output %zu exceeds the bound for input %zu", out.n,
162 : input_n);
163 :
164 63960 : u32 depth = 0;
165 63960 : u32 cols[WOK_LAYOUT_MAX_DEPTH + 1];
166 63960 : cols[0] = 1;
167 63960 : u32 bracket = 0;
168 63960 : bool balanced_brackets = true;
169 63960 : usize layout_inside_brackets = SIZE_MAX;
170 :
171 2347624 : for (usize i = 0; i < out.n; i++) {
172 2283664 : WokKind k = (WokKind)out.tok[i].kind;
173 2283664 : if (k == WT_INDENT) {
174 109492 : if (depth + 1 > WOK_LAYOUT_MAX_DEPTH) FAIL("invariant 1: depth overflow");
175 : // invariant 2 -- pushed columns strictly increase.
176 109492 : if (out.tok[i].col <= cols[depth])
177 0 : FAIL("invariant 2: INDENT at column %u does not exceed enclosing %u",
178 : out.tok[i].col, cols[depth]);
179 109492 : cols[++depth] = out.tok[i].col;
180 : // invariant 3 -- no empty block region.
181 109492 : if (i + 1 < out.n && out.tok[i + 1].kind == WT_DEDENT)
182 0 : FAIL("invariant 3: INDENT immediately followed by DEDENT at %zu", i);
183 2174172 : } else if (k == WT_DEDENT) {
184 109492 : if (depth == 0) FAIL("invariant 1: DEDENT with no matching INDENT at %zu", i);
185 109492 : depth--;
186 : }
187 2283664 : if (bracket > 0 && (k == WT_INDENT || k == WT_DEDENT || k == WT_NEWLINE) &&
188 : layout_inside_brackets == SIZE_MAX)
189 3860 : layout_inside_brackets = i;
190 2283664 : if (wok_kind_is_open_bracket(k)) bracket++;
191 2387528 : else if (wok_kind_is_close_bracket(k)) {
192 103864 : if (bracket == 0) balanced_brackets = false;
193 100106 : else bracket--;
194 : }
195 : }
196 63960 : if (bracket != 0) balanced_brackets = false;
197 :
198 63960 : if (depth != 0) FAIL("invariant 1: %u INDENT(s) never closed", depth);
199 63960 : if (strict_brackets && balanced_brackets && layout_inside_brackets != SIZE_MAX)
200 0 : FAIL("invariant 4: layout token inside a bracket group at %zu",
201 : layout_inside_brackets);
202 : return true;
203 : #undef FAIL
204 : }
|
