tricu

source_text.zig (7990B)

---

 //! Unicode scalar boundary for source IO and the browser adapter. Binary/string ABI codecs remain byte-oriented.
 const std = @import("std");
 const Arena = @import("arena.zig").Arena;
 const codecs = @import("codecs.zig");
 const reduce = @import("reduce.zig");
 
 pub fn fromUtf8(arena: *Arena, bytes: []const u8) !u32 {
     const view = std.unicode.Utf8View.init(bytes) catch return error.InvalidUtf8;
     var iter = view.iterator();
     var scalars: std.ArrayList(u32) = .empty;
     defer scalars.deinit(arena.allocator);
     while (iter.nextCodepoint()) |scalar| {
         try scalars.append(arena.allocator, try codecs.ofNumber(arena, scalar));
     }
     return codecs.ofList(arena, scalars.items);
 }
 
 // Match the Haskell source boundary's canonical-tree check, not merely its
 // numeric interpretation. Reject redundant high zero bits, non-Boolean bits,
 // overlong integers, surrogates and values beyond the Unicode scalar range.
 fn scalarNumber(arena: *Arena, input: u32, unbounded: bool) !u21 {
     var current = input;
     var value: u32 = 0;
     var bits: u5 = 0;
     var high_bit: u32 = 0;
     while (true) {
         const node = arena.get(try observe(arena, current, unbounded)).*;
         switch (node) {
             .leaf => {
                 if (bits != 0 and high_bit == 0) return error.InvalidScalarList;
                 if (value > 0x10ffff or (value >= 0xd800 and value <= 0xdfff)) return error.InvalidScalarList;
                 return @intCast(value);
             },
             .fork => |pair| {
                 if (bits == 21) return error.InvalidScalarList;
                 const bit = arena.get(try observe(arena, pair.left, unbounded)).*;
                 high_bit = switch (bit) {
                     .leaf => 0,
                     .stem => |s| if (arena.get(try observe(arena, s.child, unbounded)).* == .leaf) 1 else return error.InvalidScalarList,
                     else => return error.InvalidScalarList,
                 };
                 value |= high_bit << bits;
                 bits += 1;
                 current = pair.right;
             },
             else => return error.InvalidScalarList,
         }
     }
 }
 
 pub fn toUtf8(arena: *Arena, input: u32) ![]u8 {
     return toUtf8Bounded(arena, input, std.math.maxInt(usize));
 }
 
 // A scalar-count ceiling, not a fuel/deadline limit. Do not demand elements
 // beyond the ceiling; still inspect the spine to distinguish exact length.
 fn observe(arena: *Arena, input: u32, unbounded: bool) !u32 {
     return if (unbounded) reduce.reduceUnbounded(input, arena) else reduce.reduce(input, arena, 1_000_000);
 }
 
 pub fn toUtf8UnboundedWork(arena: *Arena, input: u32, limit: usize) ![]u8 {
     return decode(arena, input, limit, true);
 }
 
 pub fn toUtf8Bounded(arena: *Arena, input: u32, limit: usize) ![]u8 {
     return decode(arena, input, limit, false);
 }
 
 fn decode(arena: *Arena, input: u32, limit: usize, unbounded: bool) ![]u8 {
     const base = arena.roots.items.len;
     defer arena.roots.shrinkRetainingCapacity(base);
     try arena.roots.append(arena.allocator, input);
     var bytes: std.ArrayList(u8) = .empty;
     errdefer bytes.deinit(arena.allocator);
     var current = input;
     var count: usize = 0;
     while (true) {
         const node = arena.get(try observe(arena, current, unbounded)).*;
         switch (node) {
             .leaf => return bytes.toOwnedSlice(arena.allocator),
             .fork => |pair| {
                 if (count == limit) return error.ScalarLimit;
                 count += 1;
                 const scalar = try scalarNumber(arena, pair.left, unbounded);
                 var encoded: [4]u8 = undefined;
                 const len = try std.unicode.utf8Encode(scalar, &encoded);
                 try bytes.appendSlice(arena.allocator, encoded[0..len]);
                 current = pair.right;
             },
             else => return error.InvalidScalarList,
         }
     }
 }
 
 test "source scalar codec preserves exact UTF-8 including NUL, CRLF and noncharacters" {
     var arena = Arena.init(std.testing.allocator);
     defer arena.deinit();
     const bytes = "\x00a\r\né😀\u{ffff}\u{10ffff}\u{feff}";
     const scalars = try fromUtf8(&arena, bytes);
     var list = (try codecs.toList(&arena, scalars)).?;
     defer list.deinit(arena.allocator);
     const expected = [_]u64{ 0, 0x61, 13, 10, 0xe9, 0x1f600, 0xffff, 0x10ffff, 0xfeff };
     try std.testing.expectEqual(expected.len, list.items.len);
     for (list.items, expected) |item, n| try std.testing.expectEqual(n, (try codecs.toNumber(&arena, item)).?);
     arena.gc_enabled = true;
     try arena.setGcPolicy(1, 1);
     const result = try toUtf8(&arena, scalars);
     defer arena.allocator.free(result);
     try std.testing.expectEqualStrings(bytes, result);
     try std.testing.expect(arena.collections > 0);
     try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len);
 }
 
 test "source scalar codec rejects malformed UTF-8 and scalar trees" {
     var arena = Arena.init(std.testing.allocator);
     defer arena.deinit();
     for ([_][]const u8{ "\x80", "\xc0\xaf", "\xe2\x82", "\xed\xa0\x80", "\xf4\x90\x80\x80", "\xff" }) |bytes| {
         try std.testing.expectError(error.InvalidUtf8, fromUtf8(&arena, bytes));
     }
     for ([_]u64{ 0xd800, 0xdfff, 0x110000, std.math.maxInt(u64) }) |n| {
         const list = try codecs.ofList(&arena, &.{try codecs.ofNumber(&arena, n)});
         try std.testing.expectError(error.InvalidScalarList, toUtf8(&arena, list));
     }
     const leaf = try arena.alloc(.leaf);
     const zero_with_bit = try arena.alloc(.{ .fork = .{ .left = leaf, .right = leaf } });
     const bad_bit = try arena.alloc(.{ .stem = .{ .child = zero_with_bit } });
     const malformed = try arena.alloc(.{ .fork = .{ .left = bad_bit, .right = leaf } });
     for ([_]u32{ zero_with_bit, malformed, bad_bit }) |n| {
         const list = try codecs.ofList(&arena, &.{n});
         try std.testing.expectError(error.InvalidScalarList, toUtf8(&arena, list));
     }
     try std.testing.expectError(error.InvalidScalarList, toUtf8(&arena, bad_bit));
     // Failure after successful UTF-8 output must free the partial buffer too.
     const partial = try codecs.ofList(&arena, &.{ try codecs.ofNumber(&arena, 65), try codecs.ofNumber(&arena, 0xd800) });
     try std.testing.expectError(error.InvalidScalarList, toUtf8(&arena, partial));
 }
 
 test "source scalar codec accepts lazy scalar numerals" {
     var arena = Arena.init(std.testing.allocator);
     defer arena.deinit();
     const leaf = try arena.alloc(.leaf);
     const scalar = try codecs.ofNumber(&arena, 0x1f600);
     const constant = try arena.alloc(.{ .fork = .{ .left = leaf, .right = scalar } });
     const delayed = try arena.alloc(.{ .app = .{ .func = constant, .arg = leaf } });
     const list = try codecs.ofList(&arena, &.{delayed});
     arena.gc_enabled = true;
     try arena.setGcPolicy(1, 1);
     const bytes = try toUtf8(&arena, list);
     defer arena.allocator.free(bytes);
     try std.testing.expectEqualStrings("😀", bytes);
 }
 
 fn allocationProbe(allocator: std.mem.Allocator) !void {
     var arena = Arena.init(allocator);
     defer arena.deinit();
     const scalars = try fromUtf8(&arena, "aé😀");
     const bytes = try toUtf8(&arena, scalars);
     defer allocator.free(bytes);
     try std.testing.expectEqualStrings("aé😀", bytes);
 }
 
 test "source scalar codec cleans up on every allocation failure" {
     try std.testing.checkAllAllocationFailures(std.testing.allocator, allocationProbe, .{});
 }
 
 
 test "bounded scalar encoding handles exact limits and unwinds partial output" {
     var arena = Arena.init(std.testing.allocator);
     defer arena.deinit();
     const input = try fromUtf8(&arena, "é😀");
     const bytes = try toUtf8Bounded(&arena, input, 2);
     defer arena.allocator.free(bytes);
     try std.testing.expectEqualStrings("é😀", bytes);
     try std.testing.expectError(error.ScalarLimit, toUtf8Bounded(&arena, input, 1));
     try std.testing.expectEqual(@as(usize, 0), arena.roots.items.len);
 }