lib/pluck/src/identity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Allocator = std.mem.Allocator;
3
4 const pexpr = @import("pexpr.zig");
5 const Symbol = pexpr.Symbol;
6 const PExpr = pexpr.PExpr;
7
8 pub const DefinitionId = struct {
9 name_hash: u64,
10 name: Symbol,
11
12 const Self = @This();
13
14 pub fn init(name: Symbol) Self {
15 var hasher = std.hash.Wyhash.init(0);
16 hasher.update(name);
17 return Self{
18 .name_hash = hasher.final(),
19 .name = name,
20 };
21 }
22
23 pub fn hash(self: Self) u64 {
24 return self.name_hash;
25 }
26
27 pub fn eql(a: Self, b: Self) bool {
28 return a.name_hash == b.name_hash and std.mem.eql(u8, a.name, b.name);
29 }
30 };
31
32 pub const DefinitionIdContext = struct {
33 pub fn hash(_: DefinitionIdContext, key: DefinitionId) u64 {
34 return key.hash();
35 }
36
37 pub fn eql(_: DefinitionIdContext, a: DefinitionId, b: DefinitionId) bool {
38 return a.eql(b);
39 }
40 };
41
42 pub const ContentHash = struct {
43 hash: u64,
44
45 const Self = @This();
46
47 pub fn fromExpr(expr: *const PExpr) Self {
48 var hasher = std.hash.Wyhash.init(0xDEF1717100);
49 hashExprStructure(&hasher, expr);
50 return Self{ .hash = hasher.final() };
51 }
52
53 pub fn fromSource(source: []const u8) Self {
54 var hasher = std.hash.Wyhash.init(0xDEF1717100);
55 var prev_was_space = false;
56 for (source) |c| {
57 if (std.ascii.isWhitespace(c)) {
58 if (!prev_was_space) {
59 hasher.update(" ");
60 prev_was_space = true;
61 }
62 } else {
63 hasher.update(&[_]u8{c});
64 prev_was_space = false;
65 }
66 }
67 return Self{ .hash = hasher.final() };
68 }
69
70 pub fn eql(a: Self, b: Self) bool {
71 return a.hash == b.hash;
72 }
73
74 fn hashExprStructure(hasher: *std.hash.Wyhash, expr: *const PExpr) void {
75 const head_tag = @backingInt(std.meta.activeTag(expr.head));
76 hasher.update(std.mem.asBytes(&head_tag));
77
78 switch (expr.head) {
79 .var_ref => |v| hasher.update(v.name),
80 .defined => |d| hasher.update(d.name),
81
82 .abs => |a| hasher.update(a.var_name),
83
84 .construct => |c| hasher.update(c.constructor),
85
86 .case_of => |c| {
87 for (c.branches) |branch| {
88 hasher.update(branch.constructor);
89 for (branch.args) |arg| {
90 hasher.update(arg);
91 }
92 }
93 },
94
95 .type_def => |t| {
96 hasher.update(t.type_name);
97 for (t.constructors) |ctor| {
98 hasher.update(ctor.name);
99 for (ctor.args) |arg| {
100 hasher.update(arg);
101 }
102 }
103 },
104
105 .const_native => |n| {
106 switch (n) {
107 .float => |f| {
108 const bits: u64 = @bitCast(f);
109 hasher.update(std.mem.asBytes(&bits));
110 },
111 .int => |i| hasher.update(std.mem.asBytes(&i)),
112 .symbol => |s| hasher.update(s),
113 .bool_val => |b| hasher.update(std.mem.asBytes(&b)),
114 }
115 },
116
117 .app,
118 .y_combinator,
119 .flip,
120 .factor,
121 .native_eq,
122 .get_args,
123 .get_constructor,
124 .pbool,
125 .get_config,
126 .mk_int,
127 .mk_int_weighted,
128 .int_dist_eq,
129 .print_op,
130 .f_div,
131 .f_mul,
132 .f_add,
133 .f_sub,
134 .error_op,
135 => {},
136 }
137
138 for (expr.args) |arg| {
139 hashExprStructure(hasher, arg);
140 }
141 }
142 };
143
144 pub const SourceThunkId = struct {
145 def_id: DefinitionId,
146 callstack_hash: u64,
147 position_hash: u64,
148
149 const Self = @This();
150
151 pub fn init(def_name: Symbol, callstack: []const i32, expr: *const PExpr) Self {
152 var cs_hasher = std.hash.Wyhash.init(0);
153 cs_hasher.update(std.mem.sliceAsBytes(callstack));
154
155 var pos_hasher = std.hash.Wyhash.init(0xB051710);
156 ContentHash.hashExprStructure(&pos_hasher, expr);
157
158 return Self{
159 .def_id = DefinitionId.init(def_name),
160 .callstack_hash = cs_hasher.final(),
161 .position_hash = pos_hasher.final(),
162 };
163 }
164
165 pub fn initQuery(callstack: []const i32, expr: *const PExpr) Self {
166 return init("__query__", callstack, expr);
167 }
168
169 pub fn hash(self: Self) u64 {
170 var h = std.hash.Wyhash.init(0);
171 h.update(std.mem.asBytes(&self.def_id.name_hash));
172 h.update(std.mem.asBytes(&self.callstack_hash));
173 h.update(std.mem.asBytes(&self.position_hash));
174 return h.final();
175 }
176
177 pub fn eql(a: Self, b: Self) bool {
178 return a.def_id.eql(b.def_id) and
179 a.callstack_hash == b.callstack_hash and
180 a.position_hash == b.position_hash;
181 }
182 };
183
184 pub const SourceThunkIdContext = struct {
185 pub fn hash(_: SourceThunkIdContext, key: SourceThunkId) u64 {
186 return key.hash();
187 }
188
189 pub fn eql(_: SourceThunkIdContext, a: SourceThunkId, b: SourceThunkId) bool {
190 return a.eql(b);
191 }
192 };
193
194 test "DefinitionId stability" {
195 const id1 = DefinitionId.init("foo");
196 const id2 = DefinitionId.init("foo");
197 const id3 = DefinitionId.init("bar");
198
199 try std.testing.expect(id1.eql(id2));
200 try std.testing.expectEqual(id1.hash(), id2.hash());
201 try std.testing.expect(!id1.eql(id3));
202 }
203
204 test "ContentHash from expression" {
205 const allocator = std.testing.allocator;
206
207 const expr1 = try PExpr.init(allocator, .{ .const_native = .{ .float = 42.0 } });
208 defer expr1.deinit(allocator);
209
210 const expr2 = try PExpr.init(allocator, .{ .const_native = .{ .float = 42.0 } });
211 defer expr2.deinit(allocator);
212
213 const expr3 = try PExpr.init(allocator, .{ .const_native = .{ .float = 43.0 } });
214 defer expr3.deinit(allocator);
215
216 const hash1 = ContentHash.fromExpr(expr1);
217 const hash2 = ContentHash.fromExpr(expr2);
218 const hash3 = ContentHash.fromExpr(expr3);
219
220 try std.testing.expect(hash1.eql(hash2));
221 try std.testing.expect(!hash1.eql(hash3));
222 }
223
224 test "SourceThunkId stability across re-parse" {
225 const allocator = std.testing.allocator;
226
227 const expr1 = try PExpr.init(allocator, .{ .const_native = .{ .float = 0.5 } });
228 defer expr1.deinit(allocator);
229
230 const expr2 = try PExpr.init(allocator, .{ .const_native = .{ .float = 0.5 } });
231 defer expr2.deinit(allocator);
232
233 const callstack: []const i32 = &[_]i32{ 1, 2, 3 };
234
235 const id1 = SourceThunkId.init("mydef", callstack, expr1);
236 const id2 = SourceThunkId.init("mydef", callstack, expr2);
237
238 try std.testing.expect(id1.eql(id2));
239 try std.testing.expectEqual(id1.hash(), id2.hash());
240 }