summaryrefslogtreecommitdiff
path: root/anim/src/relations.zig
blob: 03165d5fd8c3d60fa1bdf4eb0f962cdc1b476b88 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
//! The relations' data (design/README.md, "4. Ties"), one table set a
//! frame, and the passes over it. The panels say, as they draw, where each
//! of their things is (`places`: a key, the kind of thing and its address
//! packed in one integer, a box, a pane) and which values they show that
//! could be addresses (`values`: the value, its box, its pane, a reference
//! such as a register's index). A relation is a join of the two on
//! address, or a step's own fact (a touch, a carry, the thread), and the
//! resolver (`ties.zig`) runs it as a pipeline of passes over slices:
//! candidates, `filter` by the knobs, `order` by priority, `cut` to the
//! budget, route, draw. `filter`, `order`, `cut` and `join` are pure, and
//! tested here with tables written by hand.
//!
//! Memory: the tables live in the frame's scratch arena (`sk.Frame.user`),
//! made at the frame's first place and gone with it: no process globals,
//! no allocation per relation, indices rather than pointers.
const std = @import("std");

/// The pane a place or a value is drawn in.
pub const Pane = enum(u8) { other, source, disasm, registers, stack, view, drawing, loupe };

/// A key: the kind of thing in its top byte, an address (or an index) in the rest.
pub const Key = u64;
pub const kind_shift = 56;
pub const address_mask: u64 = (1 << kind_shift) - 1;

pub fn keyOf(kind: u8, address: u64) Key {
    return @as(u64, kind) << kind_shift | (address & address_mask);
}

pub fn kindOf(key: Key) u8 {
    return @intCast(key >> kind_shift);
}

pub const Place = struct { key: Key, box: [4]f32, pane: Pane };
/// `at`: the address of the word that holds it (0: a register's); `ref`: a
/// register's index; `rules`: its panel's left and right rules.
pub const Value = struct { value: u64, box: [4]f32, pane: Pane, ref: u32 = 0, at: u64 = 0, rules: [2]f32 = .{ 0, 0 } };

/// One layer's tables: the working frame's, or the map's.
pub const Tables = struct {
    places: std.MultiArrayList(Place) = .{},
    values: std.MultiArrayList(Value) = .{},
    /// `places` by key (then by the order they were said), and `values` by
    /// value: built once, on the first lookup after a change.
    places_by_key: std.ArrayList(u32) = .empty,
    values_by_value: std.ArrayList(u32) = .empty,
    places_sorted: bool = true,
    values_sorted: bool = true,
    /// Nanoseconds this frame spent sorting.
    sort_ns: u64 = 0,

    pub fn add(t: *Tables, gpa: std.mem.Allocator, place: Place) void {
        t.places.append(gpa, place) catch return;
        t.places_sorted = false;
    }

    pub fn show(t: *Tables, gpa: std.mem.Allocator, value: Value) void {
        t.values.append(gpa, value) catch return;
        t.values_sorted = false;
    }

    /// The index of places by key: sorted once after a change.
    pub fn byKey(t: *Tables, gpa: std.mem.Allocator) []const u32 {
        if (!t.places_sorted) {
            const start = clock();
            sortIndex(gpa, &t.places_by_key, t.places.items(.key));
            t.places_sorted = true;
            t.sort_ns += clock() - start;
        }
        return t.places_by_key.items;
    }

    pub fn byValue(t: *Tables, gpa: std.mem.Allocator) []const u32 {
        if (!t.values_sorted) {
            const start = clock();
            sortIndex(gpa, &t.values_by_value, t.values.items(.value));
            t.values_sorted = true;
            t.sort_ns += clock() - start;
        }
        return t.values_by_value.items;
    }

    /// The box of the first place said with `key`: a binary search.
    pub fn find(t: *Tables, gpa: std.mem.Allocator, key: Key) ?[4]f32 {
        const order = t.byKey(gpa);
        const keys = t.places.items(.key);
        const i = lowerBound(order, keys, key);
        if (i == order.len or keys[order[i]] != key) return null;
        return t.places.items(.box)[order[i]];
    }

    /// The indices (into `places`) of the keys in `[lo, hi)`, in key order.
    pub fn range(t: *Tables, gpa: std.mem.Allocator, lo: Key, hi: Key) []const u32 {
        const order = t.byKey(gpa);
        const keys = t.places.items(.key);
        return order[lowerBound(order, keys, lo)..lowerBound(order, keys, hi)];
    }

    /// The greatest key of kind `kind` at or below `address`, within `within` of it.
    pub fn atOrBelow(t: *Tables, gpa: std.mem.Allocator, kind: u8, address: u64, within: u64) ?u64 {
        const order = t.byKey(gpa);
        const keys = t.places.items(.key);
        const i = lowerBound(order, keys, keyOf(kind, address) + 1);
        if (i == 0) return null;
        const k = keys[order[i - 1]];
        if (kindOf(k) != kind) return null;
        const a = k & address_mask;
        return if (address - a < within) a else null;
    }
};

/// `index` made the permutation of `keys` that sorts them, ties in their order.
fn sortIndex(gpa: std.mem.Allocator, index: *std.ArrayList(u32), keys: []const u64) void {
    index.resize(gpa, keys.len) catch return;
    for (index.items, 0..) |*v, i| v.* = @intCast(i);
    std.sort.pdq(u32, index.items, keys, struct {
        fn less(k: []const u64, a: u32, b: u32) bool {
            return k[a] < k[b] or (k[a] == k[b] and a < b);
        }
    }.less);
}

/// The first position in `order` whose key is not below `key`.
fn lowerBound(order: []const u32, keys: []const u64, key: u64) usize {
    var lo: usize = 0;
    var hi: usize = order.len;
    while (lo < hi) {
        const mid = (lo + hi) / 2;
        if (keys[order[mid]] < key) lo = mid + 1 else hi = mid;
    }
    return lo;
}

/// A value shown and the place of kind `kind` at its address (masked by
/// `mask`: a view's row is its first byte's): indices into the tables.
pub const Pair = struct { value: u32, place: u32 };

/// The join of `values` (by value, `by_value` their order) with the
/// places of kind `kind` (by key, `by_key` their order) on address: a merge
/// of the two sorted sides, each value with the first place said at its
/// address. Appends to `out`; a value that is no place's address has none.
pub fn join(values: []const u64, by_value: []const u32, keys: []const Key, by_key: []const u32, kind: u8, mask: u64, out: *std.ArrayList(Pair), gpa: std.mem.Allocator) void {
    // The places of the kind: one run of the key order.
    const lo = lowerBound(by_key, keys, keyOf(kind, 0));
    const hi = lowerBound(by_key, keys, keyOf(kind + 1, 0));
    const run = by_key[lo..hi];
    // Masking keeps the values' order (a mask clears low bits): one walk.
    var p: usize = 0;
    for (by_value) |v| {
        const want = values[v] & mask & address_mask;
        while (p < run.len and keys[run[p]] & address_mask < want) p += 1;
        if (p == run.len) break;
        if (keys[run[p]] & address_mask == want) out.append(gpa, .{ .value = v, .place = run[p] }) catch return;
    }
}

// ---- The resolver's pure passes.

/// The kinds of relation, in the order they are drawn.
pub const Kind = enum(u8) { thread, beat, link, projection, touch, carry, code };

/// What turns a kind on. `always`: whenever the step has one (the scene's
/// beat, its own facts); the rest only where the author has turned it on
/// (or, for the thread and links, has not turned it off).
pub const Knob = enum(u8) { thread, links, carry, code, always };

/// A budget's class: how many of it a frame draws at most.
pub const Class = enum(u8) { standing, beat, step, carry, code };

/// A kind's row of data: its knob, its class, its priority (lower first)
/// and how many of it a frame draws at most.
pub const Spec = struct { knob: Knob, class: Class, priority: u8, most: u8 };

pub const specs = std.enums.EnumArray(Kind, Spec).init(.{
    .thread = .{ .knob = .thread, .class = .standing, .priority = 0, .most = 1 },
    .beat = .{ .knob = .always, .class = .beat, .priority = 1, .most = 1 },
    .link = .{ .knob = .links, .class = .step, .priority = 2, .most = 1 },
    .projection = .{ .knob = .always, .class = .step, .priority = 3, .most = 1 },
    // The first to give way: three lines at most, so not with a link and a projection.
    .touch = .{ .knob = .always, .class = .step, .priority = 4, .most = 1 },
    .carry = .{ .knob = .carry, .class = .carry, .priority = 5, .most = 1 },
    // One at a time: a standing row across panes, or the step's.
    .code = .{ .knob = .code, .class = .code, .priority = 6, .most = 1 },
});

/// How many of a class a frame draws at most.
pub const budget = std.enums.EnumArray(Class, u8).init(.{ .standing = 1, .beat = 1, .step = 2, .carry = 1, .code = 1 });

/// The knobs as the scene has them this frame.
pub const Knobs = std.enums.EnumSet(Knob);

/// A relation that could be drawn: its kind, its rank within its kind (a
/// register's place in pwndbg's order, a span's in the step), and the
/// indices of what it ties (`from`, `to`: into a table, or a kind's own).
pub const Candidate = struct { kind: Kind, rank: u32 = 0, from: u32 = 0, to: u32 = 0 };

/// Those whose kind's knob is on, in place.
pub fn filter(cands: []Candidate, knobs: Knobs) []Candidate {
    var n: usize = 0;
    for (cands) |c| if (knobs.contains(specs.get(c.kind).knob)) {
        cands[n] = c;
        n += 1;
    };
    return cands[0..n];
}

/// By priority, then rank, then as they came (`from`, each its own).
pub fn byPriority(cands: []Candidate) void {
    std.sort.pdq(Candidate, cands, {}, struct {
        fn less(_: void, a: Candidate, b: Candidate) bool {
            const pa = specs.get(a.kind).priority;
            const pb = specs.get(b.kind).priority;
            if (pa != pb) return pa < pb;
            if (a.rank != b.rank) return a.rank < b.rank;
            return a.from < b.from;
        }
    }.less);
}

/// The first of each kind up to its most, and of each class up to its
/// budget, in place: what is cut is the least urgent.
pub fn cut(cands: []Candidate) []Candidate {
    var per_kind = std.enums.EnumArray(Kind, u8).initFill(0);
    var per_class = std.enums.EnumArray(Class, u8).initFill(0);
    var n: usize = 0;
    for (cands) |c| {
        const spec = specs.get(c.kind);
        if (per_kind.get(c.kind) >= spec.most or per_class.get(spec.class) >= budget.get(spec.class)) continue;
        per_kind.set(c.kind, per_kind.get(c.kind) + 1);
        per_class.set(spec.class, per_class.get(spec.class) + 1);
        cands[n] = c;
        n += 1;
    }
    return cands[0..n];
}

/// Counts and nanoseconds of a frame's relations (`CANIM_RELATIONS=1`: a line a frame on stderr).
pub const Stats = struct {
    places: usize = 0,
    values: usize = 0,
    candidates: usize = 0,
    kept: usize = 0,
    drawn: usize = 0,
    map_places: usize = 0,
    map_values: usize = 0,
    map_pairs: usize = 0,
    ns: struct { sort: u64 = 0, candidates: u64 = 0, passes: u64 = 0, draw: u64 = 0, map: u64 = 0 } = .{},
};

/// Whether to say each frame's counts and times on stderr (`CANIM_RELATIONS=1`), read once.
pub fn reporting() bool {
    if (report_on == null) report_on = if (comptime @import("builtin").link_libc) std.c.getenv("CANIM_RELATIONS") != null else false;
    return report_on.?;
}
var report_on: ?bool = null;

pub fn clock() u64 {
    var ts: std.os.linux.timespec = undefined;
    _ = std.os.linux.clock_gettime(.MONOTONIC, &ts);
    return @as(u64, @intCast(ts.sec)) * std.time.ns_per_s + @as(u64, @intCast(ts.nsec));
}

// ---- Tests: hand-written tables in, tables out.

test "a lookup is the first place said with its key, by binary search" {
    const gpa = std.testing.allocator;
    var t: Tables = .{};
    defer {
        t.places.deinit(gpa);
        t.places_by_key.deinit(gpa);
    }
    t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 1, 0, 0, 0 }, .pane = .stack });
    t.add(gpa, .{ .key = keyOf(1, 0x10), .box = .{ 2, 0, 0, 0 }, .pane = .registers });
    t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 3, 0, 0, 0 }, .pane = .stack });
    try std.testing.expectEqual(@as(f32, 1), t.find(gpa, keyOf(3, 0x30)).?[0]);
    try std.testing.expectEqual(@as(f32, 2), t.find(gpa, keyOf(1, 0x10)).?[0]);
    try std.testing.expect(t.find(gpa, keyOf(3, 0x38)) == null);
    // Said after a lookup: the order is made again.
    t.add(gpa, .{ .key = keyOf(2, 0x20), .box = .{ 4, 0, 0, 0 }, .pane = .view });
    try std.testing.expectEqual(@as(f32, 4), t.find(gpa, keyOf(2, 0x20)).?[0]);
    // A range of one kind, and the nearest at or below an address.
    t.add(gpa, .{ .key = keyOf(3, 0x50), .box = .{ 5, 0, 0, 0 }, .pane = .stack });
    try std.testing.expectEqual(@as(usize, 3), t.range(gpa, keyOf(3, 0), keyOf(4, 0)).len);
    try std.testing.expectEqual(@as(?u64, 0x30), t.atOrBelow(gpa, 3, 0x48, 64));
    try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x48, 8));
    try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x10, 64));
}

test "a join pairs each value with the first place at its address, of one kind" {
    const gpa = std.testing.allocator;
    // Places: rows (kind 14) at 401000, 401004 (twice), 401010; a word (kind 3) at 401004.
    const keys = [_]Key{ keyOf(14, 0x401004), keyOf(3, 0x401004), keyOf(14, 0x401000), keyOf(14, 0x401010), keyOf(14, 0x401004) };
    var by_key: std.ArrayList(u32) = .empty;
    defer by_key.deinit(gpa);
    sortIndex(gpa, &by_key, &keys);
    // Values: 401004 (twice), 7fff0000, 401010, 401008.
    const values = [_]u64{ 0x401004, 0x7fff0000, 0x401010, 0x401004, 0x401008 };
    var by_value: std.ArrayList(u32) = .empty;
    defer by_value.deinit(gpa);
    sortIndex(gpa, &by_value, &values);
    var out: std.ArrayList(Pair) = .empty;
    defer out.deinit(gpa);
    join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 0), &out, gpa);
    try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 0 }, .{ .value = 3, .place = 0 }, .{ .value = 2, .place = 3 } }, out.items);
    // Masked: a view's row is its first byte's (sixteen-aligned).
    out.clearRetainingCapacity();
    join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 15), &out, gpa);
    try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 2 }, .{ .value = 3, .place = 2 }, .{ .value = 4, .place = 2 }, .{ .value = 2, .place = 3 } }, out.items);
}

test "the passes: off unless its knob is on, by priority, cut to the budget" {
    var cands = [_]Candidate{
        .{ .kind = .touch },
        .{ .kind = .code, .rank = 2 },
        .{ .kind = .link, .rank = 5 },
        .{ .kind = .projection },
        .{ .kind = .link, .rank = 1 },
        .{ .kind = .thread },
        .{ .kind = .code, .rank = 0 },
    };
    // The code kind is off by default: it goes; the rest are on.
    var knobs = Knobs.initMany(&.{ .thread, .links, .always });
    var kept = filter(&cands, knobs);
    try std.testing.expectEqual(@as(usize, 5), kept.len);
    byPriority(kept);
    try std.testing.expectEqual(Kind.thread, kept[0].kind);
    try std.testing.expectEqual(@as(u32, 1), kept[1].rank);
    kept = cut(kept);
    // One thread, one link (the first in the registers' order), one projection; the touch gives way.
    try std.testing.expectEqual(@as(usize, 3), kept.len);
    try std.testing.expectEqualSlices(Kind, &.{ .thread, .link, .projection }, &.{ kept[0].kind, kept[1].kind, kept[2].kind });
    try std.testing.expectEqual(@as(u32, 1), kept[1].rank);
    // With no projection the touch is drawn; with the knob on, one code pointer, the first in rank.
    var more = [_]Candidate{ .{ .kind = .touch }, .{ .kind = .link }, .{ .kind = .code, .rank = 3 }, .{ .kind = .code, .rank = 1 } };
    knobs.insert(.code);
    kept = filter(&more, knobs);
    byPriority(kept);
    kept = cut(kept);
    try std.testing.expectEqualSlices(Kind, &.{ .link, .touch, .code }, &.{ kept[0].kind, kept[1].kind, kept[2].kind });
    try std.testing.expectEqual(@as(u32, 1), kept[2].rank);
}