lib/alloc/phase/src/capacity/capability.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const Allocator = std.mem.Allocator;
4
5 /// Recursively inspects a compile-time type to detect whether it exposes an
6 /// allocator capability. The traversal follows typed pointers, arrays, vectors,
7 /// optionals, error-union payloads, struct and union fields, and container
8 /// receiver methods whose return types lead to an allocator. It maintains a
9 /// compile-time tuple of visited containers to prevent infinite loops on
10 /// recursive data structures, and recognizes `std.mem.Allocator` as an
11 /// immediate capability. For bare function types, the check examines only the
12 /// return type, without scanning parameter lists. This public recursive
13 /// inspector differs from the narrower internal scanner used by
14 /// allocator-backed shapes, which inspects only immediate field types and
15 /// container allocator methods. The function does not inspect function bodies,
16 /// detect global allocator variables, or track capabilities through type-erased
17 /// pointers such as `*anyopaque`. It does not prove that runtime execution is
18 /// free from allocation side effects.
19 pub fn typeHasAllocatorCapability(comptime T: type) bool {
20 @setEvalBranchQuota(1_000_000);
21 return typeHasAllocatorCapabilitySeen(T, .{});
22 }
23
24 /// Shape validation uses this shallower predicate for allocator-backed owners
25 /// to identify immediate allocator access in a type's inspected surface.
26 /// Caller-provisioned shape validation selects the recursive predicate
27 /// `typeHasAllocatorCapability` instead.
28 ///
29 /// A type possesses immediate capability if it directly references
30 /// `std.mem.Allocator`, including references wrapped in arrays, vectors,
31 /// optional values, error union payloads, or pointer chains. For struct and
32 /// union values, inspection examines both declarations and fields: a container
33 /// qualifies if it declares a function named `allocator` returning an allocator
34 /// reference, or if any field contains a direct allocator reference, provides
35 /// an allocator factory directly or through a pointer, or exposes a function
36 /// type with allocator capability. Inspecting a pointer to a container,
37 /// however, checks only whether the pointee declares an `allocator` factory
38 /// function, without traversing stored fields. For example, a pointer to an
39 /// owner storing an allocator (`*BorrowedOwner`) evaluates to false because the
40 /// pointee lacks an allocator factory declaration, whereas
41 /// `std.heap.ArenaAllocator` evaluates to true because the arena declares an
42 /// `allocator` method returning an allocator reference. Function types qualify
43 /// when any typed parameter or return type contains an immediate allocator
44 /// reference.
45 ///
46 /// Inspection operates on type structure only: it does not analyze function
47 /// bodies, detect global state, or inspect type-erased targets such as
48 /// `*anyopaque`, and it provides no whole-program absence-of-allocation proof.
49 pub fn typeHasImmediateAllocatorCapability(comptime T: type) bool {
50 if (immediateAllocatorReference(T)) return true;
51 const Base = immediateSurface(T);
52 return switch (@typeInfo(Base)) {
53 .pointer => immediatePointeeHasAllocatorCapability(immediatePointeeBase(Base)),
54 .@"struct" => |structure| immediateContainerHasAllocatorCapability(
55 Base,
56 structure.field_types,
57 ),
58 .@"union" => |union_info| immediateContainerHasAllocatorCapability(
59 Base,
60 union_info.field_types,
61 ),
62 .@"fn" => |function| immediateFunctionHasAllocatorCapability(function),
63 else => false,
64 };
65 }
66
67 fn typeHasAllocatorCapabilitySeen(comptime T: type, comptime seen: anytype) bool {
68 if (T == Allocator) return true;
69 return switch (@typeInfo(T)) {
70 .array => |array| typeHasAllocatorCapabilitySeen(array.child, seen),
71 .error_union => |error_union| typeHasAllocatorCapabilitySeen(
72 error_union.payload,
73 seen,
74 ),
75 .optional => |optional| typeHasAllocatorCapabilitySeen(optional.child, seen),
76 .pointer => |pointer| typeHasAllocatorCapabilitySeen(pointer.child, seen),
77 .vector => |vector| typeHasAllocatorCapabilitySeen(vector.child, seen),
78 .@"struct" => |structure| containerHasAllocatorCapability(
79 T,
80 structure.field_types,
81 seen,
82 ),
83 .@"union" => |union_info| containerHasAllocatorCapability(
84 T,
85 union_info.field_types,
86 seen,
87 ),
88 .@"enum", .@"opaque" => containerHasAllocatorCapability(T, &.{}, seen),
89 .@"fn" => |function| functionResultHasAllocatorCapability(function, seen),
90 else => false,
91 };
92 }
93
94 fn containerHasAllocatorCapability(
95 comptime Container: type,
96 comptime field_types: []const type,
97 comptime seen: anytype,
98 ) bool {
99 inline for (seen) |Seen| {
100 if (Container == Seen) return false;
101 }
102 const next = seen ++ .{Container};
103 if (containerDeclaresAllocatorCapability(Container, next)) return true;
104 inline for (field_types) |field_type| {
105 if (typeHasAllocatorCapabilitySeen(field_type, next)) return true;
106 }
107 return false;
108 }
109
110 fn containerDeclaresAllocatorCapability(
111 comptime Container: type,
112 comptime seen: anytype,
113 ) bool {
114 const declaration_names = switch (@typeInfo(Container)) {
115 .@"struct" => |structure| structure.decl_names,
116 .@"union" => |union_info| union_info.decl_names,
117 .@"enum" => |enum_info| enum_info.decl_names,
118 .@"opaque" => |opaque_info| opaque_info.decl_names,
119 else => return false,
120 };
121 inline for (declaration_names) |declaration_name| {
122 const declaration_type = @TypeOf(@field(Container, declaration_name));
123 if (@typeInfo(declaration_type) != .@"fn") continue;
124 const function = @typeInfo(declaration_type).@"fn";
125 if (function.param_types.len == 0) continue;
126 const receiver = function.param_types[0] orelse continue;
127 if (comptime !containerReceiver(receiver, Container)) continue;
128 if (comptime functionResultHasAllocatorCapability(function, seen)) {
129 return true;
130 }
131 }
132 return false;
133 }
134
135 fn functionResultHasAllocatorCapability(
136 comptime function: std.builtin.Type.Fn,
137 comptime seen: anytype,
138 ) bool {
139 if (function.return_type) |result| {
140 return typeHasAllocatorCapabilitySeen(result, seen);
141 }
142 return false;
143 }
144
145 fn containerReceiver(comptime T: type, comptime Container: type) bool {
146 if (T == Container) return true;
147 return switch (@typeInfo(T)) {
148 .pointer => |pointer| pointer.child == Container,
149 else => false,
150 };
151 }
152
153 fn immediateAllocatorReference(comptime T: type) bool {
154 if (T == Allocator) return true;
155 return switch (@typeInfo(T)) {
156 .array => |array| immediateAllocatorReference(array.child),
157 .error_union => |error_union| immediateAllocatorReference(error_union.payload),
158 .optional => |optional| immediateAllocatorReference(optional.child),
159 .pointer => |pointer| immediateAllocatorReference(pointer.child),
160 .vector => |vector| immediateAllocatorReference(vector.child),
161 else => false,
162 };
163 }
164
165 fn immediateSurface(comptime T: type) type {
166 return switch (@typeInfo(T)) {
167 .array => |array| immediateSurface(array.child),
168 .error_union => |error_union| immediateSurface(error_union.payload),
169 .optional => |optional| immediateSurface(optional.child),
170 .vector => |vector| immediateSurface(vector.child),
171 else => T,
172 };
173 }
174
175 fn immediatePointeeBase(comptime T: type) type {
176 return switch (@typeInfo(T)) {
177 .array => |array| immediatePointeeBase(array.child),
178 .error_union => |error_union| immediatePointeeBase(error_union.payload),
179 .optional => |optional| immediatePointeeBase(optional.child),
180 .pointer => |pointer| immediatePointeeBase(pointer.child),
181 .vector => |vector| immediatePointeeBase(vector.child),
182 else => T,
183 };
184 }
185
186 fn immediateContainerHasAllocatorCapability(
187 comptime Container: type,
188 comptime field_types: []const type,
189 ) bool {
190 if (immediateContainerDeclaresAllocatorFactory(Container)) return true;
191 inline for (field_types) |field_type| {
192 if (immediateAllocatorReference(field_type)) return true;
193 const FieldSurface = immediateSurface(field_type);
194 const FieldBase = switch (@typeInfo(FieldSurface)) {
195 .pointer => immediatePointeeBase(FieldSurface),
196 else => FieldSurface,
197 };
198 if (immediatePointeeHasAllocatorCapability(FieldBase)) return true;
199 }
200 return false;
201 }
202
203 fn immediatePointeeHasAllocatorCapability(comptime T: type) bool {
204 return switch (@typeInfo(T)) {
205 .@"fn" => |function| immediateFunctionHasAllocatorCapability(function),
206 else => immediateContainerDeclaresAllocatorFactory(T),
207 };
208 }
209
210 fn immediateContainerDeclaresAllocatorFactory(comptime Container: type) bool {
211 switch (@typeInfo(Container)) {
212 .@"struct", .@"union", .@"enum", .@"opaque" => {},
213 else => return false,
214 }
215 if (!@hasDecl(Container, "allocator")) return false;
216 const allocator_type = @TypeOf(@field(Container, "allocator"));
217 if (@typeInfo(allocator_type) != .@"fn") return false;
218 const result = @typeInfo(allocator_type).@"fn".return_type orelse return false;
219 return immediateAllocatorReference(result);
220 }
221
222 fn immediateFunctionHasAllocatorCapability(
223 comptime function: std.builtin.Type.Fn,
224 ) bool {
225 inline for (function.param_types) |parameter_type_optional| {
226 if (parameter_type_optional) |parameter_type| {
227 if (immediateAllocatorReference(parameter_type)) return true;
228 }
229 }
230 if (function.return_type) |result| return immediateAllocatorReference(result);
231 return false;
232 }
233
234 test "phase owner shape recognizes transitive allocator capabilities" {
235 const BorrowedOwner = struct {
236 allocator: Allocator,
237 };
238 const Wrapper = struct {
239 borrowed: ?*BorrowedOwner,
240 };
241 const Cycle = struct {
242 next: ?*@This(),
243 };
244 const Consumer = struct {
245 pub fn init(_: Allocator) @This() {
246 return .{};
247 }
248 };
249 const Factory = struct {
250 handle: *anyopaque,
251
252 pub fn borrowed(_: *const @This()) Allocator {
253 unreachable;
254 }
255 };
256 const EnumFactory = enum {
257 handle,
258
259 pub fn borrowed(_: @This()) Allocator {
260 unreachable;
261 }
262 };
263 const OpaqueFactory = opaque {
264 pub fn borrowed(_: *const @This()) Allocator {
265 unreachable;
266 }
267 };
268
269 try std.testing.expect(typeHasAllocatorCapability(?Allocator));
270 try std.testing.expect(typeHasAllocatorCapability(error{Unavailable}!Allocator));
271 try std.testing.expect(typeHasAllocatorCapability(*Allocator));
272 try std.testing.expect(typeHasAllocatorCapability(std.heap.ArenaAllocator));
273 try std.testing.expect(typeHasAllocatorCapability(*std.heap.ArenaAllocator));
274 try std.testing.expect(typeHasAllocatorCapability(*const fn () Allocator));
275 try std.testing.expect(!typeHasAllocatorCapability(*const fn (Allocator) void));
276 try std.testing.expect(typeHasAllocatorCapability(*BorrowedOwner));
277 try std.testing.expect(typeHasAllocatorCapability([]?*Wrapper));
278 try std.testing.expect(!typeHasAllocatorCapability(Consumer));
279 try std.testing.expect(typeHasAllocatorCapability(Factory));
280 try std.testing.expect(typeHasAllocatorCapability(EnumFactory));
281 try std.testing.expect(typeHasAllocatorCapability(*OpaqueFactory));
282 try std.testing.expect(!typeHasAllocatorCapability(Cycle));
283 try std.testing.expect(!typeHasImmediateAllocatorCapability(*BorrowedOwner));
284 try std.testing.expect(
285 typeHasImmediateAllocatorCapability(std.heap.ArenaAllocator),
286 );
287 }