mymarkdown

IndentationScanner.zig (21012B)

---

 //! # Indentation iterator for mymarkdown
 //!
 //! This file focuses on parsing just the 2d structure of mymarkdown.
 //!
 //! An IndentationIterator maintains the following state:
 //! - a cursor indicating what the current line is
 //! - a stack of expected indentations
 //!
 //! It supports the following operations:
 //! - `it.peek() : ?struct { IndentAlignment, PaddedSlice }`
 //! -- no matter what, peek does not mutate state.
 //! -- peek returns .line if the current indentation is at least to the expected indentation,
 //! -- else .misaligned_line, if the current intendation is greater than the parent's expected indentation,
 //! -- else .end_of_block, signalling the end of the current indented section.
 //! - the remaining functions always return `void` and always mutate state.
 //! - `it.advance() : void`
 //! -- advance updates the cursor to the next line
 //! - `it.indent(options: struct { skip: usize }) : void`
 //! -- indent pushes a new entry onto the stack of expected indentations.
 //! -- first, indent treats the first `skip` characters after the expected indentation as spaces.
 //! -- then, it scans forward for the next non-whitespace character.
 //! --- if no such character is found, the indentation level is treated as if it were "infinity"
 //!     i.e. no indented block exists.
 //! --- otherwise, the whitespace before the non-whitespace character found is added to the expected indentation.
 //! - `it.dedent() : void`
 //! -- pops from the stack of expected indentations.
 //!
 //! ## Example API trace (happy case)
 //!
 //! Input:
 //!
 //! ==
 //! > line 1
 //!   > line 2
 //!     > line 3
 //!  line 4
 //!    line 5
 //! line 6
 //! ==
 //!
 //! - .peek() -> .{ .correct, "> line 1" }
 //! - .peek() -> .{ .correct, "> line 1" }
 //! + (peek does not mutate state)
 //! - .indent(1)
 //! -- .peek() -> .{ .correct, "line 1" }
 //! ++ (indent treats the hyphen as a space, thus removing it from
 //!     the current line.)
 //! -- .advance()
 //! -- .peek() -> .{ .correct, "> line 2" }
 //! -- .indent(1)
 //! --- .peek() -> .{ .correct, "line 2" }
 //! --- .advance()
 //! --- .peek() -> .{ .correct, "> line 3" }
 //! --- .indent(1)
 //! ---- .peek() -> .{ .correct, "line 3" }
 //! ---- .advance()
 //! ++++ (the cursor is now on line 4, which has 1 space of indentation,
 //!       less than the expected 6 spaces, and less than the 4 spaces
 //!       the parent expects.)
 //! ---- .peek() -> null
 //! --- .dedent()
 //! --- .peek() -> null
 //! -- .dedent()
 //! ++ (line 4 has only 1 space of indentation, but it is still indented
 //!     relative to the parent. so it is considered part of the current
 //!     indented block, just that it is misaligned.)
 //! -- .peek() -> .{ .misaligned, "line 4" }
 //! -- .advance()
 //! -- .peek() -> .{ .correct, " line 5" }
 //! ++ (line 5 matches 2 spaces of indent. the excess spaces are simply
 //!     included in the line.)
 //! -- .advance()
 //! -- .peek() -> null
 //! ++ (expected 2 spaces, parent expects 0 spaces, line 6 has 0 spaces,
 //!     matching the parent.)
 //! - .dedent()
 //! - .peek() -> .{ .correct, "line 6" }
 //! - .advance()
 //! - .peek() -> null
 //!
 //! ## Tabs
 //!
 //! Tabs are treated as non-whitespace because it is too hard to give
 //! intuitive semantics to them. See git tag `tab-rant` to see a version
 //! of this doc comment that tried to do so.
 //!
 //! ## What should happen for misaligned indented blocks
 //!
 //! ==
 //! >   line 1
 //!   > line 2
 //! ==
 //!
 //! - .peek() -> .{ .correct, ">   line 1" }
 //! - .indent(1)
 //! -- .peek() -> .{ .correct, "line 1" }
 //! ++ (the indentation is now considered to be 4 spaces)
 //! -- .advance()
 //! -- .peek() -> .{ .misaligned, "> line 2" }
 //! ++ (line 2 is misaligned as it only has 2 spaces)
 //! -- .indent(1)
 //! ++ (**what should happen now?**)
 //!
 //! ### Does not work: Simply push the new alignment on the stack
 //!
 //! The alignment of "line 2" is 4 spaces, so if we simply push it
 //! onto the indentation stack, we have:
 //!
 //! - indentation_stack = .{ 0, 4, 4 }
 //!
 //! The parent indentation is the same as our indentation! That means
 //! "error recovery" is impossible. A 3 space indent will be treated
 //! as misaligned to the parent, and null will be emitted.
 //! After the dedent, this 3 space indent is still considered misaligned,
 //! but it's misaligned to the parent.
 //!
 //! ==
 //! >   line 1
 //!   > line 2
 //!    line 3
 //! ==
 //!
 //! -- .indent(1)
 //! ++ (resuming from the first example)
 //! --- .peek() -> .{ .correct, "line 2" }
 //! --- .advance()
 //! --- .peek() -> null
 //! -- .dedent()
 //! -- .peek() -> .{ .misaligned, "line 3" }
 //!
 //! This is also an odd case. Without line 1, line 3 would be considered
 //! misaligned to line 2, however because it matches up with the parent,
 //! it actually triggers an null, followed by .line after .dedent().
 //!
 //! ==
 //! >   line 1
 //!   >  line 2
 //!     line 3
 //! ==
 //!
 //! -- .indent(1)
 //! ++ (resuming from the first example)
 //! --- .peek() -> .{ .correct, "line 2" }
 //! --- .advance()
 //! --- .peek() -> null
 //! -- .dedent()
 //! -- .peek() -> .{ .correct, "line 3" }
 //!
 //! ### What we actually do: Push two elements for each added indentation level
 //!
 //! The idea here is that each indentation level will have its own pair of
 //! "misaligned" and "actual" alignments.
 //!
 //! The indentation stack will start with .{ 0, 0 }, indicating that
 //! the root alignment is at 0 spaces and has no "misalignment zone".
 //! Each .indent(...) pushes 2 values onto the stack.
 //!
 //! Going back to this example, after the first .indent(1), the indentation
 //! stack will contain .{ 0, 0, 0, 4 }. After the second .indent(1),
 //! the indentation stack will contain .{ 0, 0, 0, 4, 2, 4 },
 //! indicating that there are 2 spaces worth of "misalignment" possible.
 //!
 //! ==
 //! >   line 1
 //!   > line 2
 //!    line 3
 //! ==
 
 const std = @import("std");
 const maxInt = std.math.maxInt;
 const assert = std.debug.assert;
 const testing = std.testing;
 
 const padded_str = @import("padded_str.zig");
 const PaddedMany = @import("padded_str.zig").PaddedMany;
 const PaddedSlice = @import("padded_str.zig").PaddedSlice;
 
 const IndentationScanner = @This();
 
 // ==================================
 // Fields Fields Fields Fields Fields
 
 /// Stack of expected indentations.
 /// The current indentation level is equal to the number of entries.
 _expected_indents: std.BoundedArray(ExpectedIndent, IndentLevel.NUM_INDENT_LEVELS),
 
 /// The line that would be returned by peek (if indentation matches).
 /// We always pre-scan for indentation when assigning to this field.
 /// `null` indicates EOF.
 _cur_line: ?struct {
     IndentLevel,
     NumSpaces,
     PaddedSlice,
 },
 
 /// The remaining lines of the input.
 _rest_lines: PaddedSlice,
 
 // =======================================
 // Methods Methods Methods Methods Methods
 
 /// Create an IndentationScanner that tokenizes the given input.
 pub fn initUnpadded(input_: []const u8) error{InputNotPadded}!IndentationScanner {
     const input: PaddedSlice = try .init(input_);
     const first_line, const rest_lines = input.splitOneLine();
     return .{
         ._expected_indents = while (true) {
             var out: std.BoundedArray(ExpectedIndent, IndentLevel.NUM_INDENT_LEVELS) = .{};
             out.appendAssumeCapacity(.{ .misalignment_start = 0, .correct_start = 0 });
             break out;
         },
         ._cur_line = if (first_line) |line| .{ .root, 0, line } else null,
         ._rest_lines = rest_lines,
     };
 }
 
 /// Create an IndentationScanner that tokenizes the given input.
 pub fn init(input: PaddedSlice) IndentationScanner {
     const first_line, const rest_lines = input.splitOneLine();
     return .{
         ._expected_indents = while (true) {
             var out: std.BoundedArray(ExpectedIndent, IndentLevel.NUM_INDENT_LEVELS) = .{};
             out.appendAssumeCapacity(.{ .misalignment_start = 0, .correct_start = 0 });
             break out;
         },
         ._cur_line = if (first_line) |line| .{ .root, 0, line } else null,
         ._rest_lines = rest_lines,
     };
 }
 
 /// Peek at the current line's contents, with indentation stripped.
 /// If indentation matches the parent or less, null is emitted.
 pub fn peek(it: *const IndentationScanner) PeekResult {
     const level, const spaces, const content = it._cur_line orelse return null;
     if (level.compare(.lt, it.curLevel())) return null;
     assert(level.compare(.eq, it.curLevel()));
     if (spaces >= it.curExpectedIndents().correct_start)
         return .{ .correct, content }
     else
         return .{ .misaligned, content };
 }
 
 /// Advances the cursor to the next line.
 /// Precondition: peek() would not have returned null.
 pub noinline fn advance(it: *IndentationScanner) void {
     assert(it.peek() != null);
     it._cur_line = null;
     const line_maybe, it._rest_lines = it._rest_lines.splitOneLine();
     const line = line_maybe orelse return;
     const spaces = line.indexOfNotSpace();
     if (spaces == line.len) {
         // Lie to the caller -- pretend empty lines have been indented to the correct level
         it._cur_line = .{ it.curLevel(), it.curExpectedIndents().correct_start, line.sliceOpen(spaces) };
         return;
     }
     it._cur_line = for (0..it._expected_indents.len) |rev_i| {
         const i = it._expected_indents.len - 1 - rev_i;
         const misalignment_start = it._expected_indents.buffer[i].misalignment_start;
         const correct_start = it._expected_indents.buffer[i].correct_start;
         if (spaces >= correct_start) {
             break .{ IndentLevel.from(i) orelse unreachable, correct_start, line.sliceOpen(correct_start) };
         } else if (spaces >= misalignment_start) {
             break .{ IndentLevel.from(i) orelse unreachable, spaces, line.sliceOpen(spaces) };
         }
     } else unreachable;
 }
 
 pub const IndentOptions = struct { skip: usize };
 
 /// Treats the next `skip` characters as whitespace,
 /// finds the correct level of indentation,
 /// then pushes it onto the indentation stack.
 /// Each `.indent(...)` call should be paired with a `.dedent()` call.
 /// Precondition: peek() would not have returned null.
 pub fn indent(
     it: *IndentationScanner,
     opts: IndentOptions,
 ) error{TooMuchIndentation}!void {
     const level, const spaces, const content = it._cur_line orelse unreachable;
     assert(level.compare(.eq, it.curLevel()));
     const additional_indent = opts.skip + content.sliceOpen(opts.skip).indexOfNotSpace();
     if (additional_indent == content.len) {
         it._expected_indents.append(
             .{ .misalignment_start = MAX_SPACES, .correct_start = MAX_SPACES },
         ) catch return error.TooMuchIndentation;
         it._cur_line = .{ it.curLevel(), spaces + additional_indent, content.sliceOpen(additional_indent) };
         it.advance();
     } else {
         it._expected_indents.append(
             .{ .misalignment_start = spaces + 1, .correct_start = spaces + additional_indent },
         ) catch return error.TooMuchIndentation;
         it._cur_line = .{ it.curLevel(), spaces + additional_indent, content.sliceOpen(additional_indent) };
     }
 }
 
 /// Pops from the indentation stack.
 /// Each `.indent(...)` call should be paired with a `.dedent()` call.
 /// Precondition: peek would return null, i.e. cursor is at EOF or
 ///               current indentation level is less than expected.
 pub fn dedent(it: *IndentationScanner) void {
     assert(it.peek() == null);
     assert(it._expected_indents.len > 1);
     _ = it._expected_indents.pop();
 }
 
 // =======================================
 // Helpers Helpers Helpers Helpers Helpers
 
 fn curLevel(it: *const IndentationScanner) IndentLevel {
     return IndentLevel.from(it._expected_indents.len - 1).?;
 }
 
 fn curExpectedIndents(it: *const IndentationScanner) ExpectedIndent {
     return it._expected_indents.buffer[it._expected_indents.len - 1];
 }
 
 // ===================================
 // Types Types Types Types Types Types
 
 const NumSpaces = usize;
 const MAX_SPACES = maxInt(NumSpaces);
 const ExpectedIndent = struct {
     /// Indentation between misalignment_start..correct_start is considered misaligned
     misalignment_start: NumSpaces,
     /// Indentation between correct_start..infinity is considered correct
     correct_start: NumSpaces,
 };
 
 const IndentAlignment = enum { correct, misaligned };
 const IndentLevel = enum(u8) {
     root = 0,
     max = 254,
     infinity = 255,
     _,
 
     const NUM_INDENT_LEVELS = 255;
 
     fn from(i: usize) ?IndentLevel {
         if (i > 254) return null;
         return @enumFromInt(i);
     }
     fn pred(a: IndentLevel) IndentLevel {
         return @enumFromInt(@intFromEnum(a) - 1);
     }
     fn succ(a: IndentLevel) ?IndentLevel {
         if (a.compare(.eq, .max)) return null;
         return @enumFromInt(@intFromEnum(a) + 1);
     }
     fn compare(a: IndentLevel, op: std.math.CompareOperator, b: IndentLevel) bool {
         return std.math.compare(@intFromEnum(a), op, @intFromEnum(b));
     }
 };
 
 pub const PeekResult = ?struct { IndentAlignment, PaddedSlice };
 
 // =======================================
 // Testing Testing Testing Testing Testing
 inline fn expectEqualDeep(comptime T: type, expected: T, actual: T) !void {
     try testing.expectEqualDeep(expected, actual);
 }
 inline fn expectEqualPeekResults(expected: PeekResult, actual: PeekResult) !void {
     const UnpaddedPeekResult = ?struct { IndentAlignment, [:'\n']const u8 };
     try expectEqualDeep(
         UnpaddedPeekResult,
         if (expected) |r| .{ r.@"0", r.@"1".toUnpaddedSlice() } else null,
         if (actual) |r| .{ r.@"0", r.@"1".toUnpaddedSlice() } else null,
     );
 }
 
 test IndentationScanner {
     const input_ =
         \\line 1
         \\>
         \\  line 3
         \\> line 4
         \\
         \\  line 5
         \\ line 6
         \\line 7
         \\> line 8
         \\  > line 9
         \\line 10
         \\>    line 11
         \\  > line 12
         \\     line 13
         \\    line 14
         \\   line 15
         \\  line 16
         \\ line 17
         \\     line 18
         \\> line 19
         \\  > line 20
         \\
     ;
     const input_with_padding = try PaddedSlice.pad(testing.allocator, input_);
     defer testing.allocator.free(input_with_padding);
     const input = try PaddedSlice.init(input_with_padding);
     var it: IndentationScanner = .init(input);
 
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 1") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from(">") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = MAX_SPACES, .correct_start = MAX_SPACES },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("  line 3") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("> line 4") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 4") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("line 5") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .misaligned, .from("line 6") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 7") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("> line 8") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 8") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("> line 9") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
         .{ .misalignment_start = 3, .correct_start = 4 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 9") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 10") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from(">    line 11") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 5 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 11") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .misaligned, .from("> line 12") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 5 },
         .{ .misalignment_start = 3, .correct_start = 4 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 12") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from(" line 13") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("line 14") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .misaligned, .from("line 15") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 5 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .misaligned, .from("line 16") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .misaligned, .from("line 17") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("line 18") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("> line 19") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 19") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(.{ .correct, .from("> line 20") }, it.peek());
 
     try it.indent(.{ .skip = 1 });
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
         .{ .misalignment_start = 3, .correct_start = 4 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(.{ .correct, .from("line 20") }, it.peek());
 
     it.advance();
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
         .{ .misalignment_start = 1, .correct_start = 2 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(null, it.peek());
 
     it.dedent();
     try expectEqualDeep([]const ExpectedIndent, &.{
         .{ .misalignment_start = 0, .correct_start = 0 },
     }, it._expected_indents.slice());
     try expectEqualPeekResults(null, it.peek());
 }