lib/xkb/src/keymap/model.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const xkb = @import("../root.zig");
3
4 pub const ModifierMask = u32;
5 pub const Keycode = u32;
6 pub const max_layouts = 32;
7 pub const core_modifier_count = 8;
8 pub const core_modifier_mask: ModifierMask = (1 << core_modifier_count) - 1;
9
10 pub const Modifier = struct {
11 name: []const u8,
12 mapping: ModifierMask,
13 kind: Kind,
14
15 pub const Kind = enum {
16 real,
17 virtual,
18 };
19 };
20
21 pub const core_modifiers = [_]Modifier{
22 .{ .name = "Shift", .mapping = 1 << 0, .kind = .real },
23 .{ .name = "Lock", .mapping = 1 << 1, .kind = .real },
24 .{ .name = "Control", .mapping = 1 << 2, .kind = .real },
25 .{ .name = "Mod1", .mapping = 1 << 3, .kind = .real },
26 .{ .name = "Mod2", .mapping = 1 << 4, .kind = .real },
27 .{ .name = "Mod3", .mapping = 1 << 5, .kind = .real },
28 .{ .name = "Mod4", .mapping = 1 << 6, .kind = .real },
29 .{ .name = "Mod5", .mapping = 1 << 7, .kind = .real },
30 };
31
32 pub const TypeEntry = struct {
33 modifiers: ModifierMask,
34 preserve: ModifierMask = 0,
35 level: usize,
36 };
37
38 pub const KeyType = struct {
39 modifiers: ModifierMask,
40 level_count: usize,
41 entries: []const TypeEntry,
42 };
43
44 pub const Level = struct {
45 symbols: []const xkb.keysym.Keysym,
46 uppercase_symbols: ?[]const xkb.keysym.Keysym = null,
47
48 pub fn resolvedSymbols(self: *const Level, uppercase: bool) []const xkb.keysym.Keysym {
49 if (uppercase) return self.uppercase_symbols orelse self.symbols;
50 return self.symbols;
51 }
52 };
53
54 pub const Group = struct {
55 type_index: usize,
56 levels: []const Level,
57 };
58
59 pub const OutOfRange = union(enum) {
60 wrap,
61 saturate,
62 redirect: usize,
63 };
64
65 pub const Key = struct {
66 code: Keycode,
67 groups: []const Group,
68 out_of_range: OutOfRange = .wrap,
69 repeats: bool = false,
70 };
71
72 pub const Definition = struct {
73 modifiers: []const Modifier,
74 types: []const KeyType,
75 keys: []const Key,
76 };
77
78 pub const ValidationError = error{
79 TooManyModifiers,
80 InvalidCoreModifiers,
81 DuplicateModifierName,
82 InvalidModifierMapping,
83 EmptyKeyType,
84 InvalidTypeEntry,
85 DuplicateTypeEntry,
86 InvalidGroupType,
87 InvalidGroupLevels,
88 InvalidGroupRedirect,
89 InvalidKeyOrder,
90 InvalidLayoutCount,
91 InvalidKeysym,
92 InvalidUppercaseSymbols,
93 };
94
95 const Backing = struct {
96 definition: Definition,
97 layout_count: usize,
98 };
99
100 pub const Keymap = opaque {
101 pub const Storage = struct {
102 bytes: [@sizeOf(Backing)]u8 align(@alignOf(Backing)),
103 };
104
105 pub fn init(storage_value: *Storage, definition: Definition) ValidationError!*const Keymap {
106 const layout_count = try validate(definition);
107 const backing: *Backing = @ptrCast(storage_value);
108 backing.* = .{
109 .definition = definition,
110 .layout_count = layout_count,
111 };
112 return @ptrCast(storage_value);
113 }
114
115 pub fn modifierIndex(self: *const Keymap, name: []const u8) ?usize {
116 for (self.storage().definition.modifiers, 0..) |modifier, index| {
117 if (std.mem.eql(u8, modifier.name, name)) return index;
118 }
119 return null;
120 }
121
122 pub fn modifierMapping(self: *const Keymap, index: usize) ?ModifierMask {
123 const modifiers = self.storage().definition.modifiers;
124 if (index >= modifiers.len) return null;
125 return modifiers[index].mapping;
126 }
127
128 pub fn canonicalModifierMask(self: *const Keymap) ModifierMask {
129 _ = self;
130 return core_modifier_mask;
131 }
132
133 pub fn effectiveModifiers(self: *const Keymap, input: ModifierMask) ModifierMask {
134 const modifiers = self.storage().definition.modifiers;
135 var result = input & core_modifier_mask;
136 for (modifiers[core_modifier_count..], core_modifier_count..) |modifier, index| {
137 if (input & modifierBit(index) != 0) result |= modifier.mapping;
138 }
139 return result;
140 }
141
142 pub fn resolveToCanonicalModifiers(self: *const Keymap, input: ModifierMask) ModifierMask {
143 return (input & core_modifier_mask) |
144 self.effectiveModifiers(input & ~core_modifier_mask);
145 }
146
147 pub fn layoutCount(self: *const Keymap) usize {
148 return self.storage().layout_count;
149 }
150
151 pub fn keyType(self: *const Keymap, index: usize) ?*const KeyType {
152 const types = self.storage().definition.types;
153 if (index >= types.len) return null;
154 return &types[index];
155 }
156
157 pub fn key(self: *const Keymap, code: Keycode) ?*const Key {
158 const keys = self.storage().definition.keys;
159 var low: usize = 0;
160 var high = keys.len;
161 while (low < high) {
162 const middle = low + (high - low) / 2;
163 const candidate = &keys[middle];
164 if (code < candidate.code) {
165 high = middle;
166 } else if (code > candidate.code) {
167 low = middle + 1;
168 } else {
169 return candidate;
170 }
171 }
172 return null;
173 }
174
175 pub fn group(self: *const Keymap, key_value: *const Key, effective_layout: i32) ?usize {
176 _ = self;
177 if (key_value.groups.len == 0) return null;
178 return groupInRange(effective_layout, key_value.groups.len, key_value.out_of_range);
179 }
180
181 fn storage(self: *const Keymap) *const Backing {
182 return @ptrCast(@alignCast(self));
183 }
184 };
185
186 comptime {
187 std.debug.assert(@sizeOf(Keymap.Storage) == @sizeOf(Backing));
188 std.debug.assert(@alignOf(Keymap.Storage) == @alignOf(Backing));
189 }
190
191 pub fn modifierBit(index: usize) ModifierMask {
192 std.debug.assert(index < @bitSizeOf(ModifierMask));
193 return @as(ModifierMask, 1) << @intCast(index);
194 }
195
196 pub fn groupInRange(group: i32, count: usize, out_of_range: OutOfRange) usize {
197 std.debug.assert(count != 0);
198 if (group >= 0 and @as(usize, @intCast(group)) < count) return @intCast(group);
199 return switch (out_of_range) {
200 .redirect => |redirect| if (redirect < count) redirect else 0,
201 .saturate => if (group < 0) 0 else count - 1,
202 .wrap => @intCast(@mod(@as(i64, group), @as(i64, @intCast(count)))),
203 };
204 }
205
206 fn validate(definition: Definition) ValidationError!usize {
207 if (definition.modifiers.len > @bitSizeOf(ModifierMask)) return error.TooManyModifiers;
208 if (definition.modifiers.len < core_modifier_count) return error.InvalidCoreModifiers;
209
210 for (definition.modifiers, 0..) |modifier, index| {
211 if (index < core_modifier_count) {
212 const core = core_modifiers[index];
213 if (modifier.kind != .real or modifier.mapping != core.mapping or
214 !std.mem.eql(u8, modifier.name, core.name))
215 {
216 return error.InvalidCoreModifiers;
217 }
218 } else if (modifier.kind != .virtual or modifier.mapping & ~core_modifier_mask != 0) {
219 return error.InvalidModifierMapping;
220 }
221 for (definition.modifiers[index + 1 ..]) |other| {
222 if (std.mem.eql(u8, modifier.name, other.name)) return error.DuplicateModifierName;
223 }
224 }
225
226 for (definition.types) |key_type| {
227 if (key_type.level_count == 0) return error.EmptyKeyType;
228 for (key_type.entries, 0..) |entry, entry_index| {
229 if (entry.level >= key_type.level_count or
230 entry.modifiers & ~key_type.modifiers != 0 or
231 entry.preserve & ~entry.modifiers != 0)
232 {
233 return error.InvalidTypeEntry;
234 }
235 for (key_type.entries[entry_index + 1 ..]) |other| {
236 if (entry.modifiers == other.modifiers) return error.DuplicateTypeEntry;
237 }
238 }
239 }
240
241 var layout_count: usize = 0;
242 var previous_code: ?Keycode = null;
243 for (definition.keys) |key_value| {
244 if (previous_code) |previous| {
245 if (key_value.code <= previous) return error.InvalidKeyOrder;
246 }
247 previous_code = key_value.code;
248 layout_count = @max(layout_count, key_value.groups.len);
249 if (layout_count > max_layouts) return error.InvalidLayoutCount;
250 if (key_value.out_of_range == .redirect and
251 key_value.out_of_range.redirect >= key_value.groups.len)
252 {
253 return error.InvalidGroupRedirect;
254 }
255 for (key_value.groups) |group_value| {
256 if (group_value.type_index >= definition.types.len) return error.InvalidGroupType;
257 if (group_value.levels.len != definition.types[group_value.type_index].level_count) {
258 return error.InvalidGroupLevels;
259 }
260 for (group_value.levels) |level| try validateLevel(level);
261 }
262 }
263 return layout_count;
264 }
265
266 fn validateLevel(level: Level) ValidationError!void {
267 for (level.symbols) |symbol| try validateSymbol(symbol);
268 if (level.uppercase_symbols) |uppercase_symbols| {
269 if (uppercase_symbols.len != level.symbols.len) return error.InvalidUppercaseSymbols;
270 var changed = false;
271 for (level.symbols, uppercase_symbols) |symbol, uppercase_symbol| {
272 try validateSymbol(uppercase_symbol);
273 if (xkb.keysym.upper(symbol) != uppercase_symbol) return error.InvalidUppercaseSymbols;
274 changed = changed or symbol != uppercase_symbol;
275 }
276 if (!changed) return error.InvalidUppercaseSymbols;
277 } else {
278 for (level.symbols) |symbol| {
279 if (xkb.keysym.upper(symbol) != symbol) return error.InvalidUppercaseSymbols;
280 }
281 }
282 }
283
284 fn validateSymbol(symbol: xkb.keysym.Keysym) ValidationError!void {
285 if (symbol == .no_symbol or @backingInt(symbol) > xkb.keysym.max) return error.InvalidKeysym;
286 }
287
288 test "compiled keymap validates and resolves virtual modifiers" {
289 const modifiers = core_modifiers ++ [_]Modifier{
290 .{ .name = "LevelThree", .mapping = 1, .kind = .virtual },
291 };
292 const entries = [_]TypeEntry{.{ .modifiers = 1, .level = 1 }};
293 const types = [_]KeyType{.{ .modifiers = 1, .level_count = 2, .entries = &entries }};
294 const levels = [_]Level{
295 .{ .symbols = &.{@fromBackingInt(@intCast('a'))}, .uppercase_symbols = &.{@fromBackingInt(@intCast('A'))} },
296 .{ .symbols = &.{@fromBackingInt(@intCast('A'))} },
297 };
298 const groups = [_]Group{.{ .type_index = 0, .levels = &levels }};
299 const keys = [_]Key{.{ .code = 38, .groups = &groups }};
300 var storage: Keymap.Storage = undefined;
301 const compiled = try Keymap.init(&storage, .{
302 .modifiers = &modifiers,
303 .types = &types,
304 .keys = &keys,
305 });
306
307 try std.testing.expectEqual(@as(?usize, 8), compiled.modifierIndex("LevelThree"));
308 try std.testing.expectEqual(@as(ModifierMask, 1), compiled.effectiveModifiers(modifierBit(8)));
309 try std.testing.expectEqual(core_modifier_mask, compiled.canonicalModifierMask());
310 try std.testing.expectEqual(@as(?Keycode, 38), if (compiled.key(38)) |key_value| key_value.code else null);
311 try std.testing.expectEqual(@as(usize, 1), compiled.layoutCount());
312 }
313
314 test "key group policies cover negative and overflowing layouts" {
315 try std.testing.expectEqual(@as(usize, 2), groupInRange(-1, 3, .wrap));
316 try std.testing.expectEqual(@as(usize, 1), groupInRange(4, 3, .wrap));
317 try std.testing.expectEqual(@as(usize, 0), groupInRange(-1, 3, .saturate));
318 try std.testing.expectEqual(@as(usize, 2), groupInRange(4, 3, .saturate));
319 try std.testing.expectEqual(@as(usize, 1), groupInRange(9, 3, .{ .redirect = 1 }));
320 }
321
322 test "empty keymaps retain core modifiers and repeat-only keys have no group" {
323 const keys = [_]Key{.{ .code = 38, .groups = &.{}, .repeats = true }};
324 var storage: Keymap.Storage = undefined;
325 const compiled = try Keymap.init(&storage, .{
326 .modifiers = &core_modifiers,
327 .types = &.{},
328 .keys = &keys,
329 });
330 try std.testing.expectEqual(core_modifier_mask, compiled.canonicalModifierMask());
331 try std.testing.expectEqual(core_modifier_mask, compiled.effectiveModifiers(std.math.maxInt(u32)));
332 try std.testing.expectEqual(@as(usize, 0), compiled.layoutCount());
333 try std.testing.expect(compiled.group(compiled.key(38).?, 0) == null);
334 }
335
336 test "canonical levels reject NoSymbol and invalid preserve masks" {
337 const no_symbol_levels = [_]Level{.{ .symbols = &.{.no_symbol} }};
338 const groups = [_]Group{.{ .type_index = 0, .levels = &no_symbol_levels }};
339 const keys = [_]Key{.{ .code = 38, .groups = &groups }};
340 const invalid_preserve = [_]TypeEntry{.{ .modifiers = 1, .preserve = 2, .level = 0 }};
341 const types = [_]KeyType{.{
342 .modifiers = 3,
343 .level_count = 1,
344 .entries = &invalid_preserve,
345 }};
346 var storage: Keymap.Storage = undefined;
347 try std.testing.expectError(error.InvalidTypeEntry, Keymap.init(&storage, .{
348 .modifiers = &core_modifiers,
349 .types = &types,
350 .keys = &keys,
351 }));
352
353 const valid_types = [_]KeyType{.{ .modifiers = 0, .level_count = 1, .entries = &.{} }};
354 try std.testing.expectError(error.InvalidKeysym, Keymap.init(&storage, .{
355 .modifiers = &core_modifiers,
356 .types = &valid_types,
357 .keys = &keys,
358 }));
359 }
360
361 test "compiled construction requires canonical core and uppercase data" {
362 var invalid_core = core_modifiers;
363 invalid_core[0].name = "Shifted";
364 var storage: Keymap.Storage = undefined;
365 try std.testing.expectError(error.InvalidCoreModifiers, Keymap.init(&storage, .{
366 .modifiers = &invalid_core,
367 .types = &.{},
368 .keys = &.{},
369 }));
370
371 const levels = [_]Level{.{ .symbols = &.{@fromBackingInt(@intCast('a'))} }};
372 const types = [_]KeyType{.{ .modifiers = 0, .level_count = 1, .entries = &.{} }};
373 const groups = [_]Group{.{ .type_index = 0, .levels = &levels }};
374 const keys = [_]Key{.{ .code = 38, .groups = &groups }};
375 try std.testing.expectError(error.InvalidUppercaseSymbols, Keymap.init(&storage, .{
376 .modifiers = &core_modifiers,
377 .types = &types,
378 .keys = &keys,
379 }));
380 }