data.lp

data.zig

+ +

This file contains the various data processing-related constants and functions referenced by the tangling and weaving processes.

+ +

*:

+ +

(Imports)
+
+(Processing limits)
+
+(Formatting keywords)
+
+(Configuration keywords)
+
+(Data structure types)
+
+(Error set)
+
+(Line splitting function)
+
+(Configuration searching function)
+
+(Section searching function)
+
+(Parsing functions)
+
+(Code generation functions)
+
+(Text generation function)
+

+ +

Constants

+ +

We first import the standard library and the logging function from log.zig.

+ +

Imports:

+ +

const std = @import("std");
+const log = @import("log.zig").log;
+
+const Allocator = std.mem.Allocator;
+

+ +

We define the maximum input file size of 4GiB, and the code generation function’s maximum recursion depth of 250 nested calls.

+ +

Processing limits:

+ +

pub const input_max = 0x1_0000_0000;
+pub const dereference_max = 250;
+

+ +

We then define the recognized formatting keywords. These consist of the following:

+ +

@:, which begins a new code section;
@+, which appends content to a previous code section;
@., which terminates the definition of a code section;
@=, which creates a reference to another code section;
*, which is a reserved section name representing the root level of the source code.

+ +

Formatting keywords:

+ +

pub const k_start   = "@: ";
+pub const k_add     = "@+ ";
+pub const k_end     = "@.";
+pub const k_ref     = "@= ";
+pub const k_root    = "*";
+

+ +

We similarly define the recognized configuration keywords, consisting of:

+ +

@start, which defines the leading formatted code delimiter when beginning new sections;
@add, which defines the leading formatted code delimiter when appending to existing sections;
@end, which defines the trailing formatted code delimiter;
@ref, which defines the format for section references;
@@, which is the escape sequence representing the current section name;
\n, which is the escape sequence representing a newline.

+ +

Configuration keywords:

+ +

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";
+

+ +

We then define the data structure used for parsing the input into code sections, described as follows:

+ +

The overall structure of the file is an array of Sections.
A Section consists of the section name and an array of Content elements.
A Content element may be either a range of literal lines of code or a reference to another section.
A LineRange is a pair of integers indicating the starting and ending line numbers of the section.

+ +

Data structure types:

+ +

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,
+};
+

+ +

We also define the set of errors which may be encountered by the various processing functions, consisting of:

+ +

Unexpected section start commands,
Unexpected section end commands,
Recursive dereferencing exceeding the specified depth limit,
References to nonexistent section names or configuration commands.

+ +

Error set:

+ +

pub const Errors = error{
+    UnexpectedStart,
+    UnexpectedEnd,
+    DereferenceLimit,
+    NotFound,
+};
+

+ +

Preprocessing & Searching

+ +

The line splitting function is defined, which operates on a buffer as follows.

+ +

Line splitting function:

+ +

pub fn split_lines(file: []const u8, alloc: Allocator) ![][]const u8 {
+    var buffer = std.ArrayList([]const u8).init(alloc);
+    defer buffer.deinit();
+
+    (Split file at each newline)
+
+    return buffer.toOwnedSlice();
+}
+

+ +

The function simply iteratively splits the file at each newline, and appends each resulting line to the buffer.

+ +

Split file at each newline:

+ +

var iterator = std.mem.split(u8, file, "\n");
+while (iterator.next()) |line| {
+    try buffer.append(line);
+}
+

+ +

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.

+ +

+ Split file at each newline:

+ +

if ((buffer.items.len > 0) and std.mem.eql(u8, buffer.items[buffer.items.len - 1], "")) {
+    _ = buffer.pop();
+}
+

+ +

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.

+ +

Configuration searching function:

+ +

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;
+}
+
+(Auxiliary formatting function)
+

+ +

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.

+ +

Auxiliary formatting function:

+ +

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();
+}
+

+ +

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.

+ +

Section searching function:

+ +

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;
+}
+// TODO return last match instead?
+

+ +

Parsing

+ +

We then define the parsing functions, consisting of the main parse function which builds the list of Sections, and its auxiliary parse_code subroutine which builds the contents of each CodeSection.

+ +

Parsing functions:

+ +

pub fn parse(lines: [][]const u8, alloc: Allocator) ![]Section {
+    var sections = std.ArrayList(Section).init(alloc);
+    defer sections.deinit();
+
+    (Main parsing routine)
+
+    return sections.toOwnedSlice();
+}
+
+fn parse_code(lines: [][]const u8, index: u32, alloc: Allocator) !CodeReturn {
+    var content = std.ArrayList(Content).init(alloc);
+    defer content.deinit();
+
+    (Code parsing subroutine)
+
+    return CodeReturn{ .content = content.toOwnedSlice(), .index = i + 1 };
+}
+

+ +

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.

+ +

+ Parsing functions:

+ +

const CodeReturn = struct {
+    content: []const Content,
+    index: u32,
+};
+

+ +

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.

+ +

Main parsing routine:

+ +

var i: u32 = 0;
+while (i < lines.len) {
+    const line = lines[i];
+    if (std.mem.startsWith(u8, line, k_start)) {
+        (Add new section)
+    } else if (std.mem.startsWith(u8, line, k_add)) {
+        (Append to section)
+    } else if (std.mem.eql(u8, line, k_end)) {
+        log(.err, "line {d}: unexpected section end", .{i + 1});
+        return error.UnexpectedEnd;
+    } else {
+        i += 1;
+    }
+}
+

+ +

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 (section.content) and the next line at which to resume parsing (section.index). The code section is appended to the section list, and the parsing routine continues at the provided index.

+ +

Add new section:

+ +

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;
+

+ +

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.

+ +

Append to section:

+ +

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;
+

+ +

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.

+ +

Code parsing subroutine:

+ +

var i = index;
+while (i < lines.len) {
+    const line = lines[i];
+    if (std.mem.startsWith(u8, line, k_start) or std.mem.startsWith(u8, line, k_add)) {
+        log(.err, "line {d}: unexpected section start", .{i + 1});
+        return error.UnexpectedStart;
+    } else if (std.mem.startsWith(u8, std.mem.trimLeft(u8, line, " \t"), k_ref)) {
+        (Add reference)
+    } else if (std.mem.eql(u8, line, k_end)) {
+        break;
+    } else {
+        (Add literal range)
+    }
+}
+

+ +

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.

+ +

Add reference:

+ +

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;
+

+ +

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.

+ +

Add literal range:

+ +

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 Generation

+ +

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.

+ +

Code generation functions:

+ +

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| {
+            (Append literal range)
+        },
+        .reference => |name| {
+            (Resolve reference)
+        },
+    };
+
+    log(.debug, "ending section '{s}'", .{section.name});
+    return buffer.toOwnedSlice();
+}
+

+ +

To append a literal range, the range of lines is simply appended to the buffer.

+ +

Append literal range:

+ +

log(.debug, "adding literal range {d}-{d}", .{ range.start + 1, range.end + 1 });
+try buffer.appendSlice(lines[(range.start)..(range.end + 1)]);
+

+ +

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.

+ +

Resolve reference:

+ +

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);
+

+ +

Text Generation

+ +

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 current_name 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.

+ +

Text generation function:

+ +

pub fn textgen(lines: [][]const u8, alloc: Allocator) ![][]const u8 {
+    var buffer = std.ArrayList([]const u8).init(alloc);
+    defer buffer.deinit();
+
+    (Process configuration declarations)
+
+    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 if (std.mem.startsWith(u8, line, k_start)) {
+            (Format starting command)
+        } else if (std.mem.startsWith(u8, line, k_add)) {
+            (Format appending command)
+        } else if (std.mem.startsWith(u8, line, k_end)) {
+            (Format ending command)
+        } else if (std.mem.startsWith(u8, std.mem.trimLeft(u8, line, " \t"), k_ref)) {
+            (Format reference command)
+        } else {
+            try buffer.append(line);
+        }
+    }
+    
+    return buffer.toOwnedSlice();
+}
+

+ +

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.

+ +

Process configuration declarations:

+ +

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);
+

+ +

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.

+ +

Format starting command:

+ +

current_name = line[(k_start.len)..];
+try buffer.append(try std.mem.join(alloc, current_name, conf_start));
+

+ +

Processing a section appending command is performed similarly.

+ +

Format appending command:

+ +

current_name = line[(k_add.len)..];
+try buffer.append(try std.mem.join(alloc, current_name, conf_add));
+

+ +

Processing a section ending command, however, does not require updating the current section name.

+ +

Format ending command:

+ +

try buffer.append(try std.mem.join(alloc, current_name, conf_end));
+

+ +

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).

+ +

Format reference command:

+ +

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 }));
+

tangle.lp

tangle.zig

+ +

The structure of this file is quite similar to that of weave.zig, only differing in terms of which functions are used to transform the input data.

+ +

*:

+ +

(Imports)
+
+pub fn main() !u8 {
+    (IO initialization)
+
+    (Allocator initialization)
+
+    (Read file from stdin)
+
+    (Split into lines)
+
+    (Parse lines into sections)
+
+    (Generate code)
+
+    (Write to stdout)
+
+    return 0;
+}
+

+ +

First we import the other files containing the core functions.

+ +

Imports:

+ +

const std = @import("std");
+const data = @import("data.zig");
+const log = @import("log.zig").log;
+
+const Allocator = std.mem.Allocator;
+

+ +

Within the main procedure, we first initialize the stdin and stdout interfaces.

+ +

IO initialization:

+ +

const stdin = std.io.getStdIn();
+const stdout = std.io.getStdOut();
+

+ +

We then initialize the allocator, deferring its deinitialization to the end of the process. Since the overall memory usage pattern is one in which all resources may be freed at once, the arena allocator is the most appropriate choice for this program.

+ +

Allocator initialization:

+ +

var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+var alloc = arena.allocator();
+defer arena.deinit();
+

+ +

The input file is then read from stdin. In the case of input exceeding the maximum permitted file size, the program may report the error and exit normally. All other errors which may be returned are memory allocation failures and should thus yield control to the panic handler.

+ +

Read file from stdin:

+ +

const input = stdin.reader().readAllAlloc(alloc, data.input_max) catch |err|      switch (err) {
+    error.StreamTooLong => {
+        log(.err, "input too large (maximum {})", .{std.fmt.fmtIntSizeBin(data.input_max)});
+        return 1;
+    },
+    else => |e| return e,
+};
+

+ +

We then pass the input into the line splitting function, creating an array of strings.

+ +

Split into lines:

+ +

const lines = try data.split_lines(input, alloc);
+

+ +

The lines are then passed into the parsing function, which may return a parsing error. Logging such errors is handled by the function itself, and thus the errors are handled here solely by exiting.

+ +

Parse lines into sections:

+ +

const sections = data.parse(lines, alloc) catch |err| switch (err) {
+    error.UnexpectedStart,
+    error.UnexpectedEnd => {
+        return 1;
+    },
+    else => |e| return e,
+};
+

+ +

The code file is then generated. This entails resolving references to section names, which may return an error, handled by exiting as above.

+ +

Generate code:

+ +

const code = data.codegen(lines, sections, alloc) catch |err| switch (err) {
+    error.DereferenceLimit,
+    error.NotFound => {
+        return 1;
+    },
+    else => |e| return e,
+};
+

+ +

Finally, the lines of the code file are written to stdout, separated by newlines.

+ +

Write to stdout:

+ +

for (code) |line| {
+    try stdout.writer().print("{s}\n", .{line});
+}
+

data.zig

*:

Constants

Imports:

Processing limits:

Formatting keywords:

Configuration keywords:

Data structure types:

Error set:

Preprocessing & Searching

Line splitting function:

Split file at each newline:

+ Split file at each newline:

Configuration searching function:

Auxiliary formatting function:

Section searching function:

Parsing

Parsing functions:

+ Parsing functions:

Main parsing routine:

Add new section:

Append to section:

Code parsing subroutine:

Add reference:

Add literal range:

Code Generation

Code generation functions:

Append literal range:

Resolve reference:

Text Generation

Text generation function:

Process configuration declarations:

Format starting command:

Format appending command:

Format ending command:

Format reference command:

log.zig

*:

Imports:

Level setting:

Logging function:

Compare with level threshold:

Define message string:

Print to console:

tangle.zig

*:

Imports:

IO initialization:

Allocator initialization:

Read file from stdin:

Split into lines:

Parse lines into sections:

Generate code:

Write to stdout:

weave.zig

*:

Imports:

IO initialization:

Allocator initialization:

Read file from stdin:

Split into lines:

Generate text:

Write to stdout: