lib/xkb/src/compose/table.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const xkb = @import("../root.zig");
3
4 const Keysym = xkb.keysym.Keysym;
5
6 pub const max_sequence_length = 10;
7 pub const max_output_bytes = 255;
8 pub const max_nodes = 1 << 23;
9 pub const no_edge: u32 = std.math.maxInt(u32);
10
11 pub const Result = struct {
12 text: ?[]const u8 = null,
13 symbol: ?Keysym = null,
14 };
15
16 pub const StoredResult = struct {
17 text_offset: u32 = 0,
18 symbol: Keysym = .no_symbol,
19 text_length: u8 = 0,
20 has_result: bool = false,
21 has_text: bool = false,
22 };
23
24 pub const Node = struct {
25 first_edge: u32 = no_edge,
26 result: StoredResult = .{},
27 };
28
29 pub const Edge = struct {
30 symbol: Keysym,
31 node: u32,
32 next: u32 = no_edge,
33 };
34
35 pub const Entry = struct {
36 sequence: []const Keysym,
37 text: ?[]const u8,
38 symbol: ?Keysym,
39 };
40
41 pub const Table = struct {
42 nodes: []const Node,
43 edges: []const Edge,
44 text: []const u8,
45
46 pub fn iterator(self: *const Table) Iterator {
47 return Iterator.init(self);
48 }
49
50 pub fn view(self: *const Table) View {
51 return .{
52 .nodes = self.nodes,
53 .edges = self.edges,
54 .text = self.text,
55 };
56 }
57
58 pub fn transition(self: *const Table, node_index: u32, symbol: Keysym) ?u32 {
59 return self.view().transition(node_index, symbol);
60 }
61
62 pub fn result(self: *const Table, node_index: u32) ?Result {
63 return self.view().result(node_index);
64 }
65 };
66
67 pub const View = struct {
68 nodes: []const Node,
69 edges: []const Edge,
70 text: []const u8,
71
72 pub fn transition(self: View, node_index: u32, symbol: Keysym) ?u32 {
73 var edge_index = self.nodes[node_index].first_edge;
74 while (edge_index != no_edge) {
75 const edge = self.edges[edge_index];
76 const symbol_value = @backingInt(symbol);
77 const candidate_value = @backingInt(edge.symbol);
78 if (symbol_value < candidate_value) return null;
79 if (symbol_value == candidate_value) return edge.node;
80 edge_index = edge.next;
81 }
82 return null;
83 }
84
85 pub fn result(self: View, node_index: u32) ?Result {
86 const stored = self.nodes[node_index].result;
87 if (!stored.has_result) return null;
88 return .{
89 .text = if (stored.has_text)
90 self.text[stored.text_offset..][0..stored.text_length]
91 else
92 null,
93 .symbol = if (stored.symbol == .no_symbol) null else stored.symbol,
94 };
95 }
96 };
97
98 pub const Iterator = struct {
99 table: View,
100 frames: [max_sequence_length + 1]Frame = undefined,
101 sequence: [max_sequence_length]Keysym = undefined,
102 depth: usize = 0,
103
104 const Frame = struct {
105 node: u32,
106 next_edge: u32,
107 yielded: bool = false,
108 };
109
110 fn init(table: *const Table) Iterator {
111 var result = Iterator{ .table = table.view() };
112 result.frames[0] = .{
113 .node = 0,
114 .next_edge = result.table.nodes[0].first_edge,
115 };
116 return result;
117 }
118
119 pub fn next(self: *Iterator) ?Entry {
120 while (true) {
121 var frame = &self.frames[self.depth];
122 if (!frame.yielded) {
123 frame.yielded = true;
124 if (self.table.result(frame.node)) |result_value| {
125 return .{
126 .sequence = self.sequence[0..self.depth],
127 .text = result_value.text,
128 .symbol = result_value.symbol,
129 };
130 }
131 }
132
133 if (frame.next_edge != no_edge) {
134 const edge = self.table.edges[frame.next_edge];
135 frame.next_edge = edge.next;
136 self.sequence[self.depth] = edge.symbol;
137 self.depth += 1;
138 self.frames[self.depth] = .{
139 .node = edge.node,
140 .next_edge = self.table.nodes[edge.node].first_edge,
141 };
142 continue;
143 }
144
145 if (self.depth == 0) return null;
146 self.depth -= 1;
147 }
148 }
149 };
150
151 test "table traverses sorted linked transitions" {
152 const a: Keysym = @fromBackingInt(@intCast('a'));
153 const b: Keysym = @fromBackingInt(@intCast('b'));
154 const nodes = [_]Node{
155 .{ .first_edge = 0 },
156 .{ .result = .{ .has_result = true, .symbol = a } },
157 .{ .result = .{
158 .text_offset = 0,
159 .text_length = 1,
160 .has_result = true,
161 .has_text = true,
162 } },
163 };
164 const edges = [_]Edge{
165 .{ .symbol = a, .node = 1, .next = 1 },
166 .{ .symbol = b, .node = 2 },
167 };
168 const published = Table{ .nodes = &nodes, .edges = &edges, .text = "b" };
169 try std.testing.expectEqual(@as(?u32, 1), published.transition(0, a));
170 try std.testing.expectEqual(@as(?u32, 2), published.transition(0, b));
171 var iterator_value = published.iterator();
172 try std.testing.expectEqualSlices(Keysym, &.{a}, iterator_value.next().?.sequence);
173 try std.testing.expectEqualSlices(Keysym, &.{b}, iterator_value.next().?.sequence);
174 try std.testing.expect(iterator_value.next() == null);
175 }