tiny.sql.diff
Defined in tiny.sql.
API (12)
Actions
Public operations.
Rows.scan: Starts a scan of the rows fromstartup toendintarget.Scan.deinitScan.nextrelation
Types and contracts
Public types and contracts.
Source
Source: lib/sql/src/diff.zig
zig
const std = @import("std");const catalog_mod = @import("catalog.zig");const key = @import("key.zig");const relation_mod = @import("relation.zig");const row = @import("row.zig");const tree = @import("tree.zig");const version = @import("version.zig");const wal = @import("wal.zig");const Allocator = std.mem.Allocator;pub const Error = Allocator.Error || relation_mod.Error || key.Error || row.Error;pub const ChangeKind = enum { added, removed, modified, schema,};pub const Change = struct { kind: ChangeKind, rowid: i64, from: ?[]u8 = null, to: ?[]u8 = null, fn deinit(self: *Change, allocator: Allocator) void { if (self.from) |bytes| allocator.free(bytes); if (self.to) |bytes| allocator.free(bytes); self.* = undefined; }};pub const RelationSnapshot = struct { root: *const version.RelationRoot, rows: Rows,};pub const Row = struct { rowid: i64, bytes: []const u8,};pub const Rows = union(enum) { live: *const catalog_mod.RelationHandle, materialized: []const version.RelationRow, /// Starts a scan of the rows from `start` up to `end` in `target`. pub fn scan( self: Rows, target: *Scan, allocator: Allocator, start: ?i64, end: ?i64, ) Error!void { switch (self) { .live => |handle| { target.* = .{ .live = undefined }; try handle.relation.scan(&target.live, allocator, start, end); }, .materialized => |rows| target.* = .{ .materialized = MaterializedScan.init(rows, start, end), }, } }};pub const Scan = union(enum) { live: relation_mod.Scan, materialized: MaterializedScan, pub fn deinit(self: *Scan) void { switch (self.*) { .live => |*scan| scan.deinit(), .materialized => {}, } self.* = undefined; } pub fn next(self: *Scan) Error!?Row { return switch (self.*) { .live => |*scan| if (try scan.next()) |entry| .{ .rowid = entry.rowid, .bytes = entry.bytes, } else null, .materialized => |*scan| scan.next(), }; }};const MaterializedScan = struct { rows: []const version.RelationRow, index: usize, start: ?i64, end: ?i64, fn init(rows: []const version.RelationRow, start: ?i64, end: ?i64) MaterializedScan { var index: usize = 0; while (index < rows.len and beforeStart(rows[index].rowid, start)) : (index += 1) {} return .{ .rows = rows, .index = index, .start = start, .end = end, }; } fn next(self: *MaterializedScan) ?Row { while (self.index < self.rows.len) : (self.index += 1) { const row_value = self.rows[self.index]; if (beforeStart(row_value.rowid, self.start)) continue; if (!beforeEnd(row_value.rowid, self.end)) return null; self.index += 1; return .{ .rowid = row_value.rowid, .bytes = row_value.bytes, }; } return null; }};pub const RelationDiff = struct { allocator: Allocator, schema_changed: bool, skipped_ranges: usize = 0, changes: []Change, pub fn deinit(self: *RelationDiff) void { for (self.changes) |*change| change.deinit(self.allocator); if (self.changes.len != 0) self.allocator.free(self.changes); self.* = undefined; }};pub fn relation(allocator: Allocator, left: RelationSnapshot, right: RelationSnapshot) Error!RelationDiff { const schema_changed = !version.same(left.root.schema, right.root.schema); if (!schema_changed and version.same(left.root.hash, right.root.hash)) { return .{ .allocator = allocator, .schema_changed = false, .skipped_ranges = 1, .changes = &.{}, }; } const skipped = if (schema_changed) &.{} else try equalTableRanges(allocator, &left.root.table, &right.root.table); defer if (skipped.len != 0) allocator.free(skipped); var changes: std.ArrayList(Change) = .empty; errdefer { for (changes.items) |*change| change.deinit(allocator); changes.deinit(allocator); } var start: ?i64 = null; for (skipped) |skip| { if (start != null or skip.start != null) try appendRangeDiff(allocator, &changes, left, right, schema_changed, start, skip.start); start = skip.end; if (start == null) break; } if (start != null or skipped.len == 0) try appendRangeDiff(allocator, &changes, left, right, schema_changed, start, null); return .{ .allocator = allocator, .schema_changed = schema_changed, .skipped_ranges = skipped.len, .changes = try changes.toOwnedSlice(allocator), };}const RowRange = struct { start: ?i64, end: ?i64,};fn appendRangeDiff(allocator: Allocator, changes: *std.ArrayList(Change), left: RelationSnapshot, right: RelationSnapshot, schema_changed: bool, start: ?i64, end: ?i64) Error!void { if (!rangeCanContainRows(start, end)) return; var left_scan: Scan = undefined; try left.rows.scan(&left_scan, allocator, start, end); defer left_scan.deinit(); var right_scan: Scan = undefined; try right.rows.scan(&right_scan, allocator, start, end); defer right_scan.deinit(); var left_entry = try left_scan.next(); var right_entry = try right_scan.next(); while (left_entry != null or right_entry != null) { if (left_entry == null) { try appendAdded(allocator, changes, right_entry.?); right_entry = try right_scan.next(); continue; } if (right_entry == null) { try appendRemoved(allocator, changes, left_entry.?); left_entry = try left_scan.next(); continue; } const l = left_entry.?; const r = right_entry.?; if (l.rowid < r.rowid) { try appendRemoved(allocator, changes, l); left_entry = try left_scan.next(); continue; } if (l.rowid > r.rowid) { try appendAdded(allocator, changes, r); right_entry = try right_scan.next(); continue; } if (!std.mem.eql(u8, l.bytes, r.bytes)) { try appendChanged(allocator, changes, .modified, l.rowid, l.bytes, r.bytes); } else if (schema_changed) { try appendChanged(allocator, changes, .schema, l.rowid, l.bytes, r.bytes); } left_entry = try left_scan.next(); right_entry = try right_scan.next(); }}fn equalTableRanges(allocator: Allocator, left: *const version.MapRoot, right: *const version.MapRoot) Error![]RowRange { var ranges: std.ArrayList(RowRange) = .empty; errdefer ranges.deinit(allocator); if (left.nodes.len != 0 and right.nodes.len != 0) { try appendEqualRanges(allocator, &ranges, left, left.rootNode(), right, right.rootNode()); } return try ranges.toOwnedSlice(allocator);}fn appendEqualRanges(allocator: Allocator, ranges: *std.ArrayList(RowRange), left: *const version.MapRoot, left_node: *const tree.Node, right: *const version.MapRoot, right_node: *const tree.Node) Error!void { if (sameSubtree(left_node, right_node)) { const range = RowRange{ .start = try decodeLower(left_node.lower), .end = try decodeUpper(left_node.upper), }; if (rangeCanContainRows(range.start, range.end)) try ranges.append(allocator, range); return; } if (left_node.kind != .branch or right_node.kind != .branch) return; for (left.childIndexes(left_node)) |left_child_index| { const left_child = &left.nodes[left_child_index]; const right_child = matchingChild(right, right_node, left_child) orelse continue; try appendEqualRanges(allocator, ranges, left, left_child, right, right_child); }}fn matchingChild(root: *const version.MapRoot, parent: *const tree.Node, target: *const tree.Node) ?*const tree.Node { for (root.childIndexes(parent)) |child_index| { const child = &root.nodes[child_index]; if (sameRange(child, target)) return child; } return null;}fn sameSubtree(left: *const tree.Node, right: *const tree.Node) bool { return left.kind == right.kind and sameRange(left, right) and std.mem.eql(u8, left.hash[0..], right.hash[0..]);}fn sameRange(left: *const tree.Node, right: *const tree.Node) bool { return std.mem.eql(u8, left.lower, right.lower) and sameUpper(left.upper, right.upper);}fn sameUpper(left: ?[]const u8, right: ?[]const u8) bool { if (left) |left_bytes| { const right_bytes = right orelse return false; return std.mem.eql(u8, left_bytes, right_bytes); } return right == null;}fn decodeLower(bytes: []const u8) Error!?i64 { if (bytes.len == 0) return null; return try key.decodeRowId(bytes);}fn decodeUpper(bytes: ?[]const u8) Error!?i64 { const bound = bytes orelse return null; return try decodeLower(bound);}fn rangeCanContainRows(start: ?i64, end: ?i64) bool { if (start) |lower| { if (end) |upper| return lower < upper; } return true;}fn beforeStart(rowid: i64, start: ?i64) bool { const lower = start orelse return false; return rowid < lower;}fn beforeEnd(rowid: i64, end: ?i64) bool { const upper = end orelse return true; return rowid < upper;}fn appendAdded(allocator: Allocator, changes: *std.ArrayList(Change), entry: Row) Error!void { const to = try allocator.dupe(u8, entry.bytes); errdefer allocator.free(to); try changes.append(allocator, .{ .kind = .added, .rowid = entry.rowid, .to = to, });}fn appendRemoved(allocator: Allocator, changes: *std.ArrayList(Change), entry: Row) Error!void { const from = try allocator.dupe(u8, entry.bytes); errdefer allocator.free(from); try changes.append(allocator, .{ .kind = .removed, .rowid = entry.rowid, .from = from, });}fn appendChanged(allocator: Allocator, changes: *std.ArrayList(Change), kind: ChangeKind, rowid: i64, from_bytes: []const u8, to_bytes: []const u8) Error!void { const from = try allocator.dupe(u8, from_bytes); errdefer allocator.free(from); const to = try allocator.dupe(u8, to_bytes); errdefer allocator.free(to); try changes.append(allocator, .{ .kind = kind, .rowid = rowid, .from = from, .to = to, });}test "relation diff reports added removed and modified rows" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "diff.db", .wal = "diff.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 512 }); var catalog = try catalog_mod.Catalog.open(&database, .{}); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "left", .columns = &.{.{ .name = "value" }}, }, .{ .durability = .buffered }); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "right", .columns = &.{.{ .name = "value" }}, }, .{ .durability = .buffered }); var left = try catalog.openRelation(std.testing.allocator, "left"); defer left.deinit(); var right = try catalog.openRelation(std.testing.allocator, "right"); defer right.deinit(); const schema = try catalog.schemaState(std.testing.allocator); _ = try left.relation.put(std.testing.allocator, 1, &.{.{ .text = "same" }}, .{ .durability = .buffered }); _ = try left.relation.put(std.testing.allocator, 2, &.{.{ .text = "old" }}, .{ .durability = .buffered }); _ = try left.relation.put(std.testing.allocator, 3, &.{.{ .text = "removed" }}, .{ .durability = .buffered }); _ = try right.relation.put(std.testing.allocator, 1, &.{.{ .text = "same" }}, .{ .durability = .buffered }); _ = try right.relation.put(std.testing.allocator, 2, &.{.{ .text = "new" }}, .{ .durability = .buffered }); _ = try right.relation.put(std.testing.allocator, 4, &.{.{ .text = "added" }}, .{ .durability = .buffered }); var left_root = try version.relationRoot(std.testing.allocator, "left", schema, &left, null); defer left_root.deinit(); var right_root = try version.relationRoot(std.testing.allocator, "right", schema, &right, null); defer right_root.deinit(); var result = try relation(std.testing.allocator, .{ .root = &left_root, .rows = .{ .live = &left }, }, .{ .root = &right_root, .rows = .{ .live = &right }, }); defer result.deinit(); try std.testing.expect(!result.schema_changed); try std.testing.expectEqual(@as(usize, 3), result.changes.len); try std.testing.expectEqual(ChangeKind.modified, result.changes[0].kind); try std.testing.expectEqual(@as(i64, 2), result.changes[0].rowid); try std.testing.expectEqual(ChangeKind.removed, result.changes[1].kind); try std.testing.expectEqual(@as(i64, 3), result.changes[1].rowid); try std.testing.expectEqual(ChangeKind.added, result.changes[2].kind); try std.testing.expectEqual(@as(i64, 4), result.changes[2].rowid);}test "relation diff marks rows when schema roots differ" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "schema-diff.db", .wal = "schema-diff.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 512 }); var catalog = try catalog_mod.Catalog.open(&database, .{}); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "left", .columns = &.{.{ .name = "value" }}, }, .{ .durability = .buffered }); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "right", .columns = &.{.{ .name = "value", .column = .{ .collation = .nocase } }}, }, .{ .durability = .buffered }); var left = try catalog.openRelation(std.testing.allocator, "left"); defer left.deinit(); var right = try catalog.openRelation(std.testing.allocator, "right"); defer right.deinit(); const schema = try catalog.schemaState(std.testing.allocator); _ = try left.relation.put(std.testing.allocator, 1, &.{.{ .text = "same" }}, .{ .durability = .buffered }); _ = try right.relation.put(std.testing.allocator, 1, &.{.{ .text = "same" }}, .{ .durability = .buffered }); var left_root = try version.relationRoot(std.testing.allocator, "left", schema, &left, null); defer left_root.deinit(); var right_root = try version.relationRoot(std.testing.allocator, "right", schema, &right, null); defer right_root.deinit(); var result = try relation(std.testing.allocator, .{ .root = &left_root, .rows = .{ .live = &left }, }, .{ .root = &right_root, .rows = .{ .live = &right }, }); defer result.deinit(); try std.testing.expect(result.schema_changed); try std.testing.expectEqual(@as(usize, 1), result.changes.len); try std.testing.expectEqual(ChangeKind.schema, result.changes[0].kind); try std.testing.expectEqual(@as(i64, 1), result.changes[0].rowid);}test "relation diff skips equal table subtrees" { var tmp = std.testing.tmpDir(.{}); defer tmp.cleanup(); var database = try @import("file.zig").Database.openForTesting(std.testing.allocator, tmp.dir, .{ .paths = .{ .database = "subtree-diff.db", .wal = "subtree-diff.wal" }, .header = testingHeader(), }); defer database.deinit(); try database.reserve(.{ .wal_frames = 768 }); var catalog = try catalog_mod.Catalog.open(&database, .{}); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "left", .columns = &.{.{ .name = "value" }}, }, .{ .durability = .buffered }); _ = try catalog.createRelation(std.testing.allocator, .{ .name = "right", .columns = &.{.{ .name = "value" }}, }, .{ .durability = .buffered }); var left = try catalog.openRelation(std.testing.allocator, "left"); defer left.deinit(); var right = try catalog.openRelation(std.testing.allocator, "right"); defer right.deinit(); var rowid: i64 = 0; while (rowid < 260) : (rowid += 1) { var value_buffer: [16]u8 = undefined; const value = try std.fmt.bufPrint(&value_buffer, "v{d:0>8}", .{rowid}); _ = try left.relation.put(std.testing.allocator, rowid, &.{.{ .text = value }}, .{ .durability = .buffered }); _ = try right.relation.put(std.testing.allocator, rowid, &.{.{ .text = value }}, .{ .durability = .buffered }); } _ = try right.relation.put(std.testing.allocator, 259, &.{.{ .text = "changed" }}, .{ .durability = .buffered }); const schema = try catalog.schemaState(std.testing.allocator); var left_root = try version.relationRoot(std.testing.allocator, "left", schema, &left, null); defer left_root.deinit(); var right_root = try version.relationRoot(std.testing.allocator, "right", schema, &right, null); defer right_root.deinit(); var result = try relation(std.testing.allocator, .{ .root = &left_root, .rows = .{ .live = &left }, }, .{ .root = &right_root, .rows = .{ .live = &right }, }); defer result.deinit(); try std.testing.expect(!result.schema_changed); try std.testing.expect(result.skipped_ranges > 0); try std.testing.expectEqual(@as(usize, 1), result.changes.len); try std.testing.expectEqual(ChangeKind.modified, result.changes[0].kind); try std.testing.expectEqual(@as(i64, 259), result.changes[0].rowid);}test "relation diff recursively skips equal descendant table subtrees" { const shared = testHash(7); const left_specs = [_]TestNode{ .{ .kind = .branch, .lower = null, .upper = null, .depth = 0, .hash = testHash(1), .children_start = 0, .children_len = 2 }, .{ .kind = .branch, .lower = null, .upper = 100, .depth = 1, .hash = testHash(2), .children_start = 2, .children_len = 2 }, .{ .kind = .leaf, .lower = 100, .upper = null, .depth = 1, .hash = testHash(3) }, .{ .kind = .leaf, .lower = null, .upper = 50, .depth = 2, .hash = shared }, .{ .kind = .leaf, .lower = 50, .upper = 100, .depth = 2, .hash = testHash(4) }, }; const right_specs = [_]TestNode{ .{ .kind = .branch, .lower = null, .upper = null, .depth = 0, .hash = testHash(11), .children_start = 0, .children_len = 2 }, .{ .kind = .branch, .lower = null, .upper = 100, .depth = 1, .hash = testHash(12), .children_start = 2, .children_len = 2 }, .{ .kind = .leaf, .lower = 100, .upper = null, .depth = 1, .hash = testHash(13) }, .{ .kind = .leaf, .lower = null, .upper = 50, .depth = 2, .hash = shared }, .{ .kind = .leaf, .lower = 50, .upper = 100, .depth = 2, .hash = testHash(14) }, }; const edges = [_]usize{ 1, 2, 3, 4 }; var left = try syntheticRoot(std.testing.allocator, &left_specs, &edges); defer left.deinit(); var right = try syntheticRoot(std.testing.allocator, &right_specs, &edges); defer right.deinit(); const ranges = try equalTableRanges(std.testing.allocator, &left, &right); defer std.testing.allocator.free(ranges); try std.testing.expectEqual(@as(usize, 1), ranges.len); try std.testing.expect(ranges[0].start == null); try std.testing.expectEqual(@as(i64, 50), ranges[0].end.?);}fn testingHeader() wal.Header { return .{ .sequence = 1901, .salt = .{ .first = 0xfeed_0101, .second = 0xbeef_0202 }, };}const TestNode = struct { kind: tree.NodeKind, lower: ?i64, upper: ?i64, depth: usize, hash: tree.Hash, children_start: usize = 0, children_len: usize = 0,};fn syntheticRoot(allocator: Allocator, specs: []const TestNode, edge_specs: []const usize) Error!version.MapRoot { const nodes = try allocator.alloc(tree.Node, specs.len); var node_count: usize = 0; errdefer { for (nodes[0..node_count]) |node| { allocator.free(node.lower); if (node.upper) |upper| allocator.free(upper); } allocator.free(nodes); } for (specs) |spec| { const lower = try rowLower(allocator, spec.lower); var lower_assigned = false; errdefer if (!lower_assigned) allocator.free(lower); const upper = try rowUpper(allocator, spec.upper); var upper_assigned = upper == null; errdefer if (!upper_assigned) allocator.free(upper.?); nodes[node_count] = .{ .kind = spec.kind, .lower = lower, .upper = upper, .depth = spec.depth, .summary = .{}, .hash = spec.hash, .children_start = spec.children_start, .children_len = spec.children_len, }; lower_assigned = true; upper_assigned = true; node_count += 1; } const edges = try allocator.dupe(usize, edge_specs); errdefer allocator.free(edges); return .{ .allocator = allocator, .summary = .{}, .hash = specs[0].hash, .subtree = specs[0].hash, .nodes = nodes, .edges = edges, };}fn rowLower(allocator: Allocator, value: ?i64) Error![]u8 { const rowid = value orelse return try allocator.dupe(u8, &.{}); const bytes = try allocator.alloc(u8, key.rowid_size); errdefer allocator.free(bytes); _ = try key.encodeRowId(bytes, rowid); return bytes;}fn rowUpper(allocator: Allocator, value: ?i64) Error!?[]u8 { const rowid = value orelse return null; const bytes = try allocator.alloc(u8, key.rowid_size); errdefer allocator.free(bytes); _ = try key.encodeRowId(bytes, rowid); return bytes;}fn testHash(seed: u8) tree.Hash { var hash: tree.Hash = undefined; @memset(hash[0..], seed); return hash;}Source: lib/sql/src/root.zig:37
zig
pub const diff = @import("diff.zig");Audit
| Definitions | 10 |
|---|---|
| Public names | 11 |
| Members | 8 |
| Version | 26.7.0 |
| Revision | daab053ee433 |