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
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
|
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<style>
* {box-sizing: border-box;}
html {
--fs-sans: Helvetica, "Helvetica Neue", Arial, "San Francisco", sans;
--fs-mono: jetbrains-mono-regular, Consolas, Menlo, monospace;
font-size: 16px;
}
body {background-color: #111; color: #ddd; margin: 2rem calc(50% - 32rem); font-family: var(--fs-sans); font-size: 1rem; font-style: normal;}
body * {line-height: 1.5; text-align: justify; text-justify: inter-word;}
h1,h2 {font-family: var(--fs-sans); margin: 2rem 0 1rem; font-weight: bold; line-height: 1;}
h1 {font-size: 3rem;}
h2 {font-size: 2rem;}
h3 {margin: 1rem; font-size: 1rem; font-weight: normal; font-style: italic;}
code,code * {font-family: var(--fs-mono); hyphens: none; line-height: 1.25rem;}
body>pre {background-color: #000; margin: 1rem; padding: 1rem; white-space: pre-wrap; border-radius: 0.25rem;}
ul,ol {margin: 1rem 0; padding: 0 0 0 2rem;}
ul ul,ol ol {margin: 0;}
.ref {font-family: var(--fs-sans); font-style: italic;}
@media screen and (max-width: 68rem) {body {margin: 2rem calc(50% - 24rem);}}
@media screen and (max-width: 52rem) {body {margin: 2rem calc(50% - 16rem);}}
@media screen and (max-width: 36rem) {body {margin: 2rem; hyphens: auto;} h3,body>pre {margin: 1rem 0;}}
</style>
</head>
<body>
<h1>data.lp</h1>
<p>This file contains the various data processing-related constants and functions referenced by the tangling and weaving processes.</p>
<h3 id="section">*:</h3>
<pre><code><span class="ref" >(License)</span>
<span class="ref" >(Imports)</span>
<span class="ref" >(Processing limits)</span>
<span class="ref" >(Formatting keywords)</span>
<span class="ref" >(Configuration keywords)</span>
<span class="ref" >(Data structure types)</span>
<span class="ref" >(Error set)</span>
<span class="ref" >(Line splitting function)</span>
<span class="ref" >(Configuration searching function)</span>
<span class="ref" >(Section searching function)</span>
<span class="ref" >(Command type detection function)</span>
<span class="ref" >(Parsing functions)</span>
<span class="ref" >(Code generation functions)</span>
<span class="ref" >(Text generation function)</span>
</code></pre>
<h3 id="license">License:</h3>
<pre><code>// Copyright 2022 DistressNetwork° <uplink@distress.network>
// This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at https://mozilla.org/MPL/2.0/.
</code></pre>
<h2 id="constants">Constants</h2>
<p>We first import the standard library and the logging function from <code>log.zig</code>.</p>
<h3 id="imports">Imports:</h3>
<pre><code>const std = @import("std");
const log = @import("log.zig").log;
const Allocator = std.mem.Allocator;
</code></pre>
<p>We define the maximum input file size of 4GiB, and the code generation function’s maximum recursion depth of 250 nested calls.</p>
<h3 id="processing-limits">Processing limits:</h3>
<pre><code>pub const input_max = 0x1_0000_0000;
pub const dereference_max = 250;
</code></pre>
<p>We then define the recognized formatting keywords. These consist of the following:</p>
<ul>
<li><code>@:</code>, which begins a new code section;</li>
<li><code>@+</code>, which appends content to a previous code section;</li>
<li><code>@.</code>, which terminates the definition of a code section;</li>
<li><code>@=</code>, which creates a reference to another code section;</li>
<li><code>*</code>, which is a reserved section name representing the root level of the source code.</li>
</ul>
<h3 id="formatting-keywords">Formatting keywords:</h3>
<pre><code>pub const k_start = "@: ";
pub const k_add = "@+ ";
pub const k_end = "@.";
pub const k_ref = "@= ";
pub const k_root = "*";
</code></pre>
<p>We similarly define the recognized configuration keywords, consisting of:</p>
<ul>
<li><code>@start</code>, which defines the leading formatted code delimiter when beginning new sections;</li>
<li><code>@add</code>, which defines the leading formatted code delimiter when appending to existing sections;</li>
<li><code>@end</code>, which defines the trailing formatted code delimiter;</li>
<li><code>@ref</code>, which defines the format for section references;</li>
<li><code>@@</code>, which is the escape sequence representing the current section name;</li>
<li><code>\n</code>, which is the escape sequence representing a newline.</li>
</ul>
<h3 id="configuration-keywords">Configuration keywords:</h3>
<pre><code>pub const kc_start = "@start ";
pub const kc_add = "@add ";
pub const kc_end = "@end ";
pub const kc_ref = "@ref ";
pub const kc_esc = "@@";
pub const kc_nl = "\\n";
</code></pre>
<p>We then define the data structure used for parsing the input into code sections, described as follows:</p>
<ul>
<li>The overall structure of the file is an array of <code>Section</code>s.</li>
<li>A <code>Section</code> consists of the section name and an array of <code>Content</code> elements.</li>
<li>A <code>Content</code> element may be either a range of literal lines of code or a reference to another section.</li>
<li>A <code>LineRange</code> is a pair of integers indicating the starting and ending line numbers of the section.</li>
</ul>
<h3 id="data-structure-types">Data structure types:</h3>
<pre><code>pub const Section = struct {
name: []const u8,
content: []const Content,
};
pub const CodeType = enum { literal, reference };
pub const Content = union(CodeType) {
literal: LineRange,
reference: []const u8,
};
pub const LineRange = struct {
start: u32,
end: u32,
};
</code></pre>
<p>We also define the set of errors which may be encountered by the various processing functions, consisting of:</p>
<ul>
<li>Unexpected section start commands,</li>
<li>Unexpected section end commands, </li>
<li>Recursive dereferencing exceeding the specified depth limit,</li>
<li>References to nonexistent section names or configuration commands.</li>
</ul>
<h3 id="error-set">Error set:</h3>
<pre><code>pub const Errors = error {
UnexpectedStart,
UnexpectedEnd,
DereferenceLimit,
NotFound,
};
</code></pre>
<h2 id="preprocessing-searching">Preprocessing & Searching</h2>
<p>The line splitting function is defined, which operates on a buffer as follows.</p>
<h3 id="line-splitting-function">Line splitting function:</h3>
<pre><code>pub fn split_lines(file: []const u8, alloc: Allocator) ![][]const u8 {
var buffer = std.ArrayList([]const u8).init(alloc);
defer buffer.deinit();
<span class="ref" >(Split file at each newline)</span>
return buffer.toOwnedSlice();
}
</code></pre>
<p>The function simply iteratively splits the file at each newline, and appends each resulting line to the buffer.</p>
<h3 id="split-file-at-each-newline">Split file at each newline:</h3>
<pre><code>var iterator = std.mem.split(u8, file, "\n");
while (iterator.next()) |line| {
try buffer.append(line);
}
</code></pre>
<p>In addition, the final empty line created by the trailing newline at the end of the file (inserted automatically by some text editors) is removed, if it exists. This may only be performed if the file is non-empty, to avoid out-of-bounds indexing.</p>
<h3 id="split-file-at-each-newline-1">+ Split file at each newline:</h3>
<pre><code>if ((buffer.items.len > 0) and std.mem.eql(u8, buffer.items[buffer.items.len - 1], "")) {
_ = buffer.pop();
}
</code></pre>
<p>We define the configuration command searching function, which returns a list containing the segments of the split format string. The function will return from within the for loop if the declaration is found, otherwise an error is reported.</p>
<h3 id="configuration-searching-function">Configuration searching function:</h3>
<pre><code>pub fn get_conf(lines: [][]const u8, key: []const u8, alloc: Allocator) ![][]const u8 {
for (lines) |line| {
if (std.mem.startsWith(u8, line, key)) {
return try fmt_conf(line, key, alloc);
}
}
log(.err, "config declaration '{s}' not found", .{std.mem.trimRight(u8, key, " \t")});
return error.NotFound;
}
<span class="ref" >(Auxiliary formatting function)</span>
</code></pre>
<p>If the declaration is found, its contained format string is split along instances of the section name escape sequence, and each substring has its instances of the newline escape sequence replaced with a literal newline.</p>
<h3 id="auxiliary-formatting-function">Auxiliary formatting function:</h3>
<pre><code>fn fmt_conf(line: []const u8, key: []const u8, alloc: Allocator) ![][]const u8 {
var buffer = std.ArrayList([]const u8).init(alloc);
defer buffer.deinit();
var iterator = std.mem.split(u8, line[(key.len)..], kc_esc);
while (iterator.next()) |str| {
try buffer.append(try std.mem.replaceOwned(u8, alloc, str, kc_nl, "\n"));
}
return buffer.toOwnedSlice();
}
</code></pre>
<p>We define the code section searching function, which returns the index (into the section list) of the first section with a matching name, or returns an error if none exist.</p>
<h3 id="section-searching-function">Section searching function:</h3>
<pre><code>fn search(list: []Section, name: []const u8) !usize {
for (list) |section, index| {
if (std.mem.eql(u8, section.name, name)) return index;
}
log(.err, "section '{s}' not found", .{name});
return error.NotFound;
}
</code></pre>
<h2 id="parsing">Parsing</h2>
<p>We first define a function which, for a given line, determines whether it consists of a formatting command, and which type of command it contains. This is done in order to enable the use of switch statements in later functions using this routine.</p>
<h3 id="command-type-detection-function">Command type detection function:</h3>
<pre><code>const CommandType = enum { start, add, end, ref, none };
fn command_type(line: []const u8) CommandType {
if (std.mem.startsWith(u8, line, k_start)) {
return .start;
} else if (std.mem.startsWith(u8, line, k_add)) {
return .add;
} else if (std.mem.eql(u8, line, k_end)) {
return .end;
} else if (std.mem.startsWith(u8, std.mem.trimLeft(u8, line, " \t"), k_ref)) {
return .ref;
} else {
return .none;
}
}
</code></pre>
<p>We then define the parsing functions, consisting of the main <code>parse</code> function which builds the list of <code>Section</code>s, and its auxiliary <code>parse_code</code> subroutine which builds the contents of each <code>CodeSection</code>.</p>
<h3 id="parsing-functions">Parsing functions:</h3>
<pre><code>pub fn parse(lines: [][]const u8, alloc: Allocator) ![]Section {
var sections = std.ArrayList(Section).init(alloc);
defer sections.deinit();
<span class="ref" >(Main parsing routine)</span>
return sections.toOwnedSlice();
}
fn parse_code(lines: [][]const u8, index: u32, alloc: Allocator) !CodeReturn {
var content = std.ArrayList(Content).init(alloc);
defer content.deinit();
<span class="ref" >(Code parsing subroutine)</span>
return CodeReturn{ .content = content.toOwnedSlice(), .index = i + 1 };
}
</code></pre>
<p>The latter function takes as arguments the list of lines and the allocator similarly to the main function, but it is also passed the index of the current line being processed, and returns the line at which the main function should resume parsing after the code section is parsed. It thus returns a struct consisting of the contents of the code section and the next line number index, as follows.</p>
<h3 id="parsing-functions-1">+ Parsing functions:</h3>
<pre><code>const CodeReturn = struct {
content: []const Content,
index: u32,
};
</code></pre>
<p>The main parsing routine iterates over the list of lines, adding code sections where they occur, and otherwise ignoring text sections. If a section end command is encountered in the absence of a preceding starting command, an error is returned.</p>
<h3 id="main-parsing-routine">Main parsing routine:</h3>
<pre><code>var i: u32 = 0;
while (i < lines.len) {
const line = lines[i];
switch (command_type(line)) {
.start => {
<span class="ref" >(Add new section)</span>
},
.add => {
<span class="ref" >(Append to section)</span>
},
.end => {
log(.err, "line {d}: unexpected section end", .{i + 1});
return error.UnexpectedEnd;
},
else => {
i += 1;
},
}
}
</code></pre>
<p>To add a new section, the name (consisting of everything after the starting token) is first retrieved from the starting command. Then the code parsing subroutine is called, beginning at the line after the starting command, and it returns the resulting code section (<code>section.content</code>) and the next line at which to resume parsing (<code>section.index</code>). The code section is appended to the section list, and the parsing routine continues at the provided index.</p>
<h3 id="add-new-section">Add new section:</h3>
<pre><code>const name = line[(k_start.len)..];
log(.debug, "({d}) starting section '{s}'", .{ i + 1, name });
const section = try parse_code(lines, i + 1, alloc);
try sections.append(.{ .name = name, .content = section.content });
log(.debug, "({d}) ending section '{s}'", .{ section.index, name });
i = section.index;
</code></pre>
<p>To append to an existing section, the section name and the code section contents to be appended are retrieved as above. The index of the section is located, along with its address within the section list. Next, the new contents of the section are created by concatenating the old contents with the newly parsed code section contents. The section list is then updated to point to the new section contents, and the parsing routine continues.</p>
<h3 id="append-to-section">Append to section:</h3>
<pre><code>const name = line[(k_add.len)..];
log(.debug, "({d}) appending to section '{s}'", .{ i + 1, name });
const section = try parse_code(lines, i + 1, alloc);
const index = try search(sections.items, name);
const old = &sections.items[index];
const new = try std.mem.concat(alloc, Content, &[_][]const Content{ old.*.content, section.content });
old.*.content = new;
log(.debug, "({d}) ending section '{s}'", .{ section.index, name });
i = section.index;
</code></pre>
<p>The code parsing subroutine iterates over the list of lines similarly to the main routine. If a starting or appending command is encountered (lacking a matching ending command), an error is raised. Reference commands may be preceded with any amount of whitespace. The loop exits upon encountering an ending command. Otherwise, the line is appended as a literal element.</p>
<h3 id="code-parsing-subroutine">Code parsing subroutine:</h3>
<pre><code>var i = index;
while (i < lines.len) {
const line = lines[i];
switch (command_type(line)) {
.start, .add => {
log(.err, "line {d}: unexpected section start", .{i + 1});
return error.UnexpectedStart;
},
.ref => {
<span class="ref" >(Add reference)</span>
},
.end => {
break;
},
else => {
<span class="ref" >(Add literal range)</span>
},
}
}
</code></pre>
<p>To add a reference, the name of the referenced section is retrieved, consisting of the characters following the leading whitespace and the command token. The resulting string is appended to the section contents list, and the parser continues at the next line.</p>
<h3 id="add-reference">Add reference:</h3>
<pre><code>const ref_name = std.mem.trimLeft(u8, line, " \t")[(k_ref.len)..];
try content.append(.{ .reference = ref_name });
log(.debug, "({d}) \tappended reference '{s}'", .{ i + 1, ref_name });
i += 1;
</code></pre>
<p>To add a literal range, the parser either updates the end index of the previous literal element, or creates a new literal element if the last element added is a reference. This action of switching on the previous section element must only occur if the section contents list is non-empty, in order to prevent out-of-bounds indexing. Otherwise, the parser unconditionally appends a new literal element to the list. After either case, parsing continues at the next line.</p>
<h3 id="add-literal-range">Add literal range:</h3>
<pre><code>if (content.items.len > 0) {
switch (content.items[content.items.len - 1]) {
.literal => |*range| {
range.*.end = i;
},
.reference => {
try content.append(.{ .literal = .{ .start = i, .end = i } });
log(.debug, "({d}) \tappending literal", .{i + 1});
},
}
} else {
try content.append(.{ .literal = .{ .start = i, .end = i } });
log(.debug, "({d}) \tappending literal", .{i + 1});
}
i += 1;
</code></pre>
<h2 id="code-generation">Code Generation</h2>
<p>We define the source code generation procedure which is split into two functions, consisting of a wrapper function which begins code generation at (the index of) the top-level section, and the main procedure which iterates over the current section contents, recursively resolving section references and appending literal elements to the list of source code lines.</p>
<h3 id="code-generation-functions">Code generation functions:</h3>
<pre><code>pub fn codegen(lines: [][]const u8, list: []Section, alloc: Allocator) ![][]const u8 {
const root = try search(list, k_root);
return try codegen_main(lines, list, root, 0, alloc);
}
fn codegen_main(lines: [][]const u8, list: []Section, index: usize, depth: u8, alloc: Allocator) anyerror![][]const u8 {
var buffer = std.ArrayList([]const u8).init(alloc);
defer buffer.deinit();
const section = list[index];
log(.debug, "generating section '{s}'", .{section.name});
for (section.content) |content| switch (content) {
.literal => |range| {
<span class="ref" >(Append literal range)</span>
},
.reference => |name| {
<span class="ref" >(Resolve reference)</span>
},
};
log(.debug, "ending section '{s}'", .{section.name});
return buffer.toOwnedSlice();
}
</code></pre>
<p>To append a literal range, the range of lines is simply appended to the buffer.</p>
<h3 id="append-literal-range">Append literal range:</h3>
<pre><code>log(.debug, "adding literal range {d}-{d}", .{ range.start + 1, range.end + 1 });
try buffer.appendSlice(lines[(range.start)..(range.end + 1)]);
</code></pre>
<p>To resolve a section reference, the function must first check whether the current recursion depth has exceeded the configured limit, and return an error if this occurs. Otherwise, the index of the referenced section is retrieved, its contents are recursively parsed (with an incremented recursion depth), and the resulting source code lines are appended to the buffer.</p>
<h3 id="resolve-reference">Resolve reference:</h3>
<pre><code>if (depth > dereference_max) {
log(.err, "section dereferencing recursion depth exceeded (max {d})", .{dereference_max});
return error.DereferenceLimit;
}
const ref = try search(list, name);
const code = try codegen_main(lines, list, ref, depth + 1, alloc);
try buffer.appendSlice(code);
</code></pre>
<h2 id="text-generation">Text Generation</h2>
<p>Finally, we define the text generation function which iterates over the list of lines and produces the literate program text to be passed to an external document processor. In order to keep track of the name of the code section currently being formatted at any given point, the variable <code>current_name</code> is continually updated to contain the current name string. Configuration declarations are skipped, and lines which do not contain any formatting commands are appended as they are.</p>
<h3 id="text-generation-function">Text generation function:</h3>
<pre><code>pub fn textgen(lines: [][]const u8, alloc: Allocator) ![][]const u8 {
var buffer = std.ArrayList([]const u8).init(alloc);
defer buffer.deinit();
<span class="ref" >(Process configuration declarations)</span>
var current_name: []const u8 = undefined;
for (lines) |line| {
if ( std.mem.startsWith(u8, line, kc_start)
or std.mem.startsWith(u8, line, kc_add)
or std.mem.startsWith(u8, line, kc_end)
or std.mem.startsWith(u8, line, kc_ref)) {
continue;
} else switch (command_type(line)) {
.start => {
<span class="ref" >(Format starting command)</span>
},
.add => {
<span class="ref" >(Format appending command)</span>
},
.ref => {
<span class="ref" >(Format reference command)</span>
},
.end => {
<span class="ref" >(Format ending command)</span>
},
else => {
try buffer.append(line);
},
}
}
return buffer.toOwnedSlice();
}
</code></pre>
<p>The formatting strings given by each configuration declaration are first retrieved. If the declaration of the format string for the section appending command is omitted, the format string for the section starting command is used in its place.</p>
<h3 id="process-configuration-declarations">Process configuration declarations:</h3>
<pre><code>const conf_start = try get_conf(lines, kc_start, alloc);
const conf_add = get_conf(lines, kc_add, alloc) catch conf_start;
const conf_end = try get_conf(lines, kc_end, alloc);
const conf_ref = try get_conf(lines, kc_ref, alloc);
</code></pre>
<p>To process a section starting command, the current section name is updated, and the contents of the corresponding formatting command (that is, the segments of the split formatting string) are interspersed with copies of the current section name. The resulting string is then appended to the buffer.</p>
<h3 id="format-starting-command">Format starting command:</h3>
<pre><code>current_name = line[(k_start.len)..];
try buffer.append(try std.mem.join(alloc, current_name, conf_start));
</code></pre>
<p>Processing a section appending command is performed similarly.</p>
<h3 id="format-appending-command">Format appending command:</h3>
<pre><code>current_name = line[(k_add.len)..];
try buffer.append(try std.mem.join(alloc, current_name, conf_add));
</code></pre>
<p>To process a reference command, the index of the reference command keyword is first extracted. Then the formatted reference string is created, to which the reference command line’s leading whitespace is prepended (to preserve indentation). </p>
<h3 id="format-reference-command">Format reference command:</h3>
<pre><code>const start = std.mem.indexOf(u8, line, k_ref).?;
const ref = try std.mem.join(alloc, line[(start + k_ref.len)..], conf_ref);
try buffer.append(try std.mem.concat(alloc, u8, &[_][]const u8{ line[0..start], ref }));
</code></pre>
<p>Processing a section ending command is performed similarly to the starting and appending commands, however it does not require updating the current section name.</p>
<h3 id="format-ending-command">Format ending command:</h3>
<pre><code>try buffer.append(try std.mem.join(alloc, current_name, conf_end));
</code></pre>
</body>
</html>
|
