tiny.profiling.ingest.duplicate

1const std = @import("std");23pub const hash_seed: u64 = 6;45pub const KeyEntry = struct {6    offset: usize,7    len: usize,8    hash: u64,9};1011pub const ObjectFrame = struct {12    first_key: usize,13    first_byte: usize,14};1516pub const Scratch = struct {17    json_stack: []u8,18    key_bytes: []u8,19    keys: []KeyEntry,20    objects: []ObjectFrame,21};2223pub const Key = struct {24    bytes: []const u8,25    hash: u64,26};2728pub const Observation = union(enum) {29    none,30    unique: Key,31    duplicate,32};3334pub const Tracker = struct {35    scratch: Scratch,36    key_count: usize = 0,37    byte_count: usize = 0,38    object_count: usize = 0,39    key_start: usize = 0,40    key_hash: std.hash.Wyhash = std.hash.Wyhash.init(hash_seed),41    in_key: bool = false,4243    pub fn init(scratch: Scratch) Tracker {44        const result = Tracker{ .scratch = scratch };45        std.debug.assert(result.key_count == 0);46        std.debug.assert(result.byte_count == 0);47        std.debug.assert(result.object_count == 0);48        return result;49    }5051    pub fn observe(52        self: *Tracker,53        scanner: *const std.json.Scanner,54        token: std.json.Token,55    ) error{ScratchExceeded}!Observation {56        std.debug.assert(self.key_count <= self.scratch.keys.len);57        std.debug.assert(self.byte_count <= self.scratch.key_bytes.len);58        std.debug.assert(self.object_count <= self.scratch.objects.len);59        switch (token) {60            .object_begin => try self.pushObject(),61            .object_end => self.popObject(),62            else => {},63        }64        if (!scanner.string_is_object_key) return .none;65        switch (token) {66            .partial_string => |bytes| try self.feed(bytes),67            .partial_string_escaped_1 => |bytes| try self.feed(&bytes),68            .partial_string_escaped_2 => |bytes| try self.feed(&bytes),69            .partial_string_escaped_3 => |bytes| try self.feed(&bytes),70            .partial_string_escaped_4 => |bytes| try self.feed(&bytes),71            .string => |bytes| {72                try self.feed(bytes);73                return self.finishKey();74            },75            else => {},76        }77        return .none;78    }7980    fn pushObject(self: *Tracker) error{ScratchExceeded}!void {81        std.debug.assert(self.key_count <= self.scratch.keys.len);82        std.debug.assert(self.byte_count <= self.scratch.key_bytes.len);83        if (self.object_count >= self.scratch.objects.len) return error.ScratchExceeded;84        self.scratch.objects[self.object_count] = .{85            .first_key = self.key_count,86            .first_byte = self.byte_count,87        };88        self.object_count += 1;89        std.debug.assert(self.object_count <= self.scratch.objects.len);90    }9192    fn popObject(self: *Tracker) void {93        std.debug.assert(self.object_count > 0);94        self.object_count -= 1;95        const frame = self.scratch.objects[self.object_count];96        std.debug.assert(frame.first_key <= self.key_count);97        std.debug.assert(frame.first_byte <= self.byte_count);98        self.key_count = frame.first_key;99        self.byte_count = frame.first_byte;100    }101102    fn feed(self: *Tracker, bytes: []const u8) error{ScratchExceeded}!void {103        std.debug.assert(self.byte_count <= self.scratch.key_bytes.len);104        if (!self.in_key) {105            self.in_key = true;106            self.key_start = self.byte_count;107            self.key_hash = std.hash.Wyhash.init(hash_seed);108        }109        const end = std.math.add(usize, self.byte_count, bytes.len) catch110            return error.ScratchExceeded;111        if (end > self.scratch.key_bytes.len) return error.ScratchExceeded;112        @memcpy(self.scratch.key_bytes[self.byte_count..end], bytes);113        self.key_hash.update(bytes);114        self.byte_count = end;115        std.debug.assert(self.byte_count <= self.scratch.key_bytes.len);116    }117118    fn finishKey(self: *Tracker) error{ScratchExceeded}!Observation {119        std.debug.assert(self.in_key);120        std.debug.assert(self.object_count > 0);121        std.debug.assert(self.key_start <= self.byte_count);122        std.debug.assert(self.key_count <= self.scratch.keys.len);123        const len = self.byte_count - self.key_start;124        const hash = self.key_hash.final();125        const frame = self.scratch.objects[self.object_count - 1];126        std.debug.assert(frame.first_key <= self.key_count);127        for (self.scratch.keys[frame.first_key..self.key_count]) |key| {128            if (key.hash != hash or key.len != len) continue;129            const previous = self.scratch.key_bytes[key.offset..][0..key.len];130            const current = self.scratch.key_bytes[self.key_start..][0..len];131            if (std.mem.eql(u8, previous, current)) {132                self.in_key = false;133                return .duplicate;134            }135        }136        if (self.key_count >= self.scratch.keys.len) return error.ScratchExceeded;137        self.scratch.keys[self.key_count] = .{138            .offset = self.key_start,139            .len = len,140            .hash = hash,141        };142        self.key_count += 1;143        self.in_key = false;144        return .{ .unique = .{145            .bytes = self.scratch.key_bytes[self.key_start..][0..len],146            .hash = hash,147        } };148    }149};

1pub const duplicate = @import("duplicate.zig");