cheatah
Source BigBrain
Source

stdlib/memory/tests/memory_test.cpp

1// Copyright (c) 2026 BigBrain LLC. MIT-licensed (see LICENSE).
2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.
3// SPEC (for review) — the intended behaviour of the `memory` module. NOT wired into the build and
4// NOT expected to pass until the C++ backend engine is implemented; every test is a promise the
5// implementation must keep.
6//
7// Types (namespace cheatah::memory; PascalCase handles, lowercase tags/enums — matches File/Conn/
8// Pattern vs read/write):
9// Owner<T> — the sole owner + coordinator (non-copyable, pinned). `T` is the
10// ONLY class template arg. Policy is a CONSTRUCTOR arg; priority
11// is a compile-time arg on the write accessor.
12// Lease<T, read | write> — the only handle; read()=get, write(v)=set, write()=in-place ref (NOT get()).
13// Request<Lease> — what accessors return; `.acquire(on_interrupt)` BLOCKS -> Lease.
14// Access (EVERY accessor returns a Request for a lease, never a bare lease — a read included):
15// o.rread() -> Request<Lease<T, read>>. r = ....acquire(). r.read() -> const T&.
16// r.valid()/r.expired() track the owner's stop request.
17// o.rwrite<priority>() -> Request<Lease<T, write>>. w = ....acquire(). w.write(value) sets; w.write() -> T& for in-place. Exclusive.
18// priority is a compile-time int or the caller's enum value; higher = higher;
19// NEGATIVE (memory::immediate == -1) = immediate-write (preempt + resume).
20// own(value[, policy]) -> Owner<T>. policy is memory::interleave (default) | memory::writes_first.
21// Request::acquire(on_interrupt) — blocks for the lease; the optional callback is wired to the
22// lease's stop token and fires when the owner needs the lease back.
23// Safety: a write touches no byte until every read lease has released (drain-before-write); a reader
24// that re-acquires after a write sees the object's CURRENT location (no dangling).
26#include <algorithm>
27#include <atomic>
28#include <chrono>
29#include <map>
30#include <memory>
31#include <string>
32#include <thread>
33#include <type_traits>
34#include <utility>
35#include <vector>
37#include <gtest/gtest.h>
39#include "memory.hpp"
41namespace mem = cheatah::memory;
42using namespace std::chrono_literals;
44namespace { struct Point { int x = 0, y = 0; }; }
46// ── the core invariant: no accessor ever returns a bare lease ─────────────────────────────
48TEST(Memory, EveryAccessorReturnsARequestNotABareLease) {
49 auto o = mem::own(Point{});
50 static_assert(std::is_same_v<decltype(o.rread()),
51 mem::Request<mem::Lease<Point, mem::read>>>,
52 "rread() hands back a Request for a read lease, not a read lease");
53 static_assert(std::is_same_v<decltype(o.rwrite()),
54 mem::Request<mem::Lease<Point, mem::write>>>,
55 "rwrite() hands back a Request for a write lease, not a write lease");
56 // .acquire() is how a Request redeems into the lease.
57 static_assert(std::is_same_v<decltype(o.rread().acquire()), mem::Lease<Point, mem::read>>,
58 "Request::acquire() yields the lease");
59 SUCCEED();
62// read() must hand back a REFERENCE to the owned object — never a copy, never a raw pointer — so a
63// caller touches the object in place (and a big object isn't copied on every read).
64TEST(Memory, ReadReturnsAReferenceNotACopyOrPointer) {
65 struct Big { int a[64]; };
66 using RB = mem::Lease<Big, mem::read>;
67 static_assert(std::is_same_v<decltype(std::declval<const RB&>().read()), const Big&>,
68 "read() returns const T& — a reference to the owned object, not a copy or a T*");
69 static_assert(std::is_reference_v<decltype(std::declval<const RB&>().read())>,
70 "read() returns a reference");
71 static_assert(!std::is_pointer_v<std::remove_reference_t<decltype(std::declval<const RB&>().read())>>,
72 "read() does not return a raw pointer");
73 static_assert(std::is_void_v<decltype(std::declval<mem::Lease<Big, mem::write>&>().write(std::declval<Big>()))>,
74 "write(value) is a SETTER — it returns void, never an object/reference");
75 SUCCEED();
78// ── ownership basics ─────────────────────────────────────────────────────────────────────
80TEST(Memory, OwnerIsSoleAndNonCopyable) {
81 static_assert(!std::is_copy_constructible_v<mem::Owner<Point>>, "owner is the sole owner");
82 static_assert(!std::is_copy_assignable_v<mem::Owner<Point>>, "owner is the sole owner");
83 SUCCEED();
86TEST(Memory, ObjectDiesWithOwner) {
87 static int live = 0;
88 // std::movable (own<T> constrains on it): ctors count, assignments are no-ops for the count.
89 struct T {
90 T(){++live;} T(const T&){++live;} T(T&&){++live;}
91 T& operator=(const T&){return *this;} T& operator=(T&&){return *this;}
92 ~T(){--live;}
93 };
94 { auto o = mem::own(T{}); EXPECT_EQ(live, 1); }
95 EXPECT_EQ(live, 0);
98// The object is MOVED into the Owner (consumed), never copied; copying an Owner is forbidden.
99TEST(Memory, OwnerConsumesAndMovesTheObjectInNeverCopies) {
100 static_assert(!std::is_copy_constructible_v<mem::Owner<int>>, "Owner is non-copyable");
101 static_assert(!std::is_move_constructible_v<mem::Owner<int>>, "Owner is pinned (non-movable)");
103 struct Tracker {
104 int moves = 0, copies = 0;
105 std::shared_ptr<int> resource = std::make_shared<int>(7); // a movable resource we can watch
106 Tracker() = default;
107 Tracker(const Tracker& o) : moves(o.moves), copies(o.copies + 1), resource(o.resource) {}
108 Tracker(Tracker&& o) noexcept
109 : moves(o.moves + 1), copies(o.copies), resource(std::move(o.resource)) {}
110 Tracker& operator=(const Tracker&) = default;
111 Tracker& operator=(Tracker&&) noexcept = default;
112 };
114 Tracker src; // an lvalue we hand over
115 auto o = mem::own(std::move(src)); // consume it — Owner<Tracker>(Tracker&&)
116 auto r = o.rread().acquire();
117 EXPECT_EQ(r.read().copies, 0) << "the object must be MOVED into the Owner, never copied";
118 EXPECT_GE(r.read().moves, 1) << "the object must be moved in";
119 EXPECT_EQ(*r.read().resource, 7); // the Owner holds the resource
120 EXPECT_EQ(src.resource, nullptr) << "the source was consumed — its resource moved out";
123// For complex objects, each write form reaches the RIGHT item: index → the right element, key → the
124// right entry, whole-value → a clean replacement; everything else stays untouched.
125TEST(Memory, LeasesModifyTheCorrectItemsOfComplexObjects) {
126 { // sequence: the indexed setter hits exactly one element; the symmetric read getters read it back.
127 auto o = mem::own(std::vector<int>{10, 20, 30, 40});
128 { auto w = o.rwrite().acquire(); w.write(std::size_t{2}, 99); }
129 auto r = o.rread().acquire();
130 EXPECT_EQ(r.read(std::size_t{0}), 10); // read(index) mirrors write(index, value)
131 EXPECT_EQ(r.read(std::size_t{2}), 99); // only index 2 changed
132 EXPECT_EQ(r.read_front(), 10); // read_front / read_back convenience
133 EXPECT_EQ(r.read_back(), 40);
134 EXPECT_EQ(r.read().size(), 4u); // read() still gives the whole object
135 }
136 { // mapping: keyed setter updates/inserts; read(key) mirrors it (and throws on a missing key).
137 auto o = mem::own(std::map<std::string, int>{{"a", 1}, {"b", 2}});
138 { auto w = o.rwrite().acquire(); w.write(std::string("b"), 22); } // update
139 { auto w = o.rwrite().acquire(); w.write(std::string("c"), 3); } // insert
140 auto r = o.rread().acquire();
141 EXPECT_EQ(r.read(std::string("a")), 1); // read(key) mirrors write(key, value)
142 EXPECT_EQ(r.read(std::string("b")), 22);
143 EXPECT_EQ(r.read(std::string("c")), 3);
144 EXPECT_EQ(r.read().size(), 3u);
145 }
146 { // nested struct: whole-value setter replaces it; the read sees the new fields.
147 struct Inner { int x; std::string name; };
148 auto o = mem::own(Inner{1, "old"});
149 { auto w = o.rwrite().acquire(); w.write(Inner{42, "new"}); }
150 auto r = o.rread().acquire();
151 EXPECT_EQ(r.read().x, 42);
152 EXPECT_EQ(r.read().name, "new");
153 }
156TEST(Memory, PolicyIsAConstructorArgumentNotATemplateParameter) {
157 auto fair = mem::own(0); // default policy: memory::interleave
158 auto drain = mem::own(0, mem::writes_first); // policy chosen at construction
159 // Both are the same TYPE (Owner<int>) — policy is a stored value, not part of the type.
160 static_assert(std::is_same_v<decltype(fair), decltype(drain)>,
161 "Owner<T> carries only T; policy does not template the class");
162 SUCCEED();
165// ── read leases: coexist, and are accessed via read() (never get()) ──────────────────────
167TEST(Memory, ReadLeasesCoexist) {
168 auto o = mem::own(Point{3, 4});
169 auto r1 = o.rread().acquire(); // request -> acquire -> Lease<Point, read>
170 auto r2 = o.rread().acquire(); // a second read lease at the same time — allowed
171 EXPECT_TRUE(r1.valid());
172 EXPECT_TRUE(r2.valid());
173 EXPECT_EQ(r1.read().x, 3); // lease access is read()/write(), never get()
174 EXPECT_EQ(r2.read().y, 4);
177TEST(Memory, ReadLeaseValidUntilAWriterNeedsIn) {
178 auto o = mem::own(Point{1, 1});
179 std::atomic<bool> reader_saw_expired{false}, reader_holding{false};
180 std::thread reader([&] {
181 auto r = o.rread().acquire();
182 reader_holding = true;
183 while (r.valid()) std::this_thread::yield(); // read until the owner asks us to stop
184 reader_saw_expired = r.expired(); // we left the loop because the lease expired
185 }); // reader releases here
186 while (!reader_holding) std::this_thread::yield();
187 { auto w = o.rwrite().acquire(); auto p = w.read(); p.x = 9; w.write(p); } // write expires the read lease
188 reader.join();
189 EXPECT_TRUE(reader_saw_expired); // the reader observed expired()
190 EXPECT_EQ(o.rread().acquire().read().x, 9); // the write landed
193TEST(Memory, InterruptCallbackFiresWhenTheOwnerNeedsTheLeaseBack) {
194 // The callback passed INTO acquire() is the requester's "what to do if interrupted" — the owner
195 // decides when; the requester only suggests the reaction.
196 auto o = mem::own(0);
197 std::atomic<bool> asked_to_yield{false}, reader_holding{false};
198 std::thread reader([&] {
199 auto r = o.rread().acquire([&] { asked_to_yield = true; }); // wired to the lease's stop token
200 reader_holding = true;
201 while (r.valid()) std::this_thread::yield();
202 });
203 while (!reader_holding) std::this_thread::yield();
204 { auto w = o.rwrite().acquire(); w.write(42); } // requesting the write trips the reader's stop
205 reader.join();
206 EXPECT_TRUE(asked_to_yield); // the interrupt handler fired
209// ── drain-before-write: the writer waits until every reader has released ──────────────────
211TEST(Memory, WriteWaitsForReadersToDrain) {
212 auto o = mem::own<long long>(0);
213 std::atomic<bool> reader_released{false};
214 std::atomic<bool> write_began_before_release{false};
215 std::thread reader([&] {
216 auto r = o.rread().acquire();
217 while (r.valid()) std::this_thread::sleep_for(1ms); // hold briefly, honoring the stop
218 std::this_thread::sleep_for(5ms);
219 reader_released = true;
220 }); // release here
221 std::this_thread::sleep_for(1ms);
222 {
223 auto w = o.rwrite().acquire(); // must block until the reader released
224 if (!reader_released) write_began_before_release = true;
225 w.write(1);
226 }
227 reader.join();
228 EXPECT_FALSE(write_began_before_release); // no byte moved while a reader held on
229 EXPECT_EQ(o.rread().acquire().read(), 1);
232// ── renewal: a reader re-acquiring after a write sees the NEW value at the CURRENT location ─
234TEST(Memory, ReaderRenewsAndSeesTheNewValueEvenIfMoved) {
235 // A std::string can reallocate (move its bytes) when it grows — the renewed read lease must
236 // still be valid, pointing at the object's current location.
237 auto o = mem::own(std::string("x"));
238 std::atomic<bool> go{false};
239 std::string seen;
240 std::thread reader([&] {
241 while (!go) std::this_thread::yield();
242 for (;;) {
243 auto r = o.rread().acquire(); // re-request (renew); blocks behind a write
244 if (r.read().size() > 100) { seen = r.read(); break; }
245 }
246 });
247 std::thread writer([&] {
248 while (!go) std::this_thread::yield();
249 auto w = o.rwrite().acquire();
250 w.write(std::string(500, 'a')); // grows -> may relocate the buffer
251 });
252 go = true;
253 reader.join();
254 writer.join();
255 EXPECT_EQ(seen, std::string(500, 'a')); // renewed reader saw the new bytes safely
258// ── writer-may-be-a-reader: releasing your read then writing must not deadlock ────────────
260TEST(Memory, AReaderCanBecomeAWriterWithoutSelfDeadlock) {
261 auto o = mem::own(Point{0, 0});
262 { auto r = o.rread().acquire(); EXPECT_EQ(r.read().x, 0); } // finish reading (release)
263 { auto w = o.rwrite().acquire(); auto p = w.read(); p.x = 7; w.write(p); } // then write — no wait-on-self
264 { auto r = o.rread().acquire(); EXPECT_EQ(r.read().x, 7); } // and read again (renew)
265 SUCCEED();
268// ── scheduling: priority is a compile-time argument on rwrite; higher is served first ────
270namespace { enum class Job { normal = 0, high = 10 }; } // arbitrary names; higher = higher priority
272TEST(Memory, HigherPriorityWriteServedFirst) {
273 auto o = mem::own(std::string(""));
274 std::atomic<bool> blocker_holding{false}, release_blocker{false};
275 // Hold a read lease so both writers must queue; enqueue the normal one first, then the high one.
276 std::thread blocker([&] {
277 auto r = o.rread().acquire();
278 blocker_holding = true;
279 while (!release_blocker) std::this_thread::yield(); // hold the read lease so both writers QUEUE
280 });
281 while (!blocker_holding) std::this_thread::yield();
282 std::thread lo([&]{ auto w = o.rwrite<Job::normal>().acquire(); w.write(w.read() + "L"); });
283 std::this_thread::sleep_for(2ms); // ensure L enqueues first
284 std::thread hi([&]{ auto w = o.rwrite<Job::high>().acquire(); w.write(w.read() + "H"); });
285 std::this_thread::sleep_for(2ms);
286 release_blocker = true; // now the queue drains by priority
287 blocker.join(); lo.join(); hi.join();
288 EXPECT_EQ(o.rread().acquire().read(), "HL"); // High ran before Low despite arriving later
291// ── negative priority = immediate-write: bypass queue, preempt active writer, it resumes ──
293TEST(Memory, ImmediateConstantIsANegativeNamedForReadability) {
294 static_assert(mem::immediate == -1, "memory::immediate is the readable spelling of -1");
295 static_assert(mem::immediate < 0, "any negative priority is an immediate-write");
296 SUCCEED();
299// THE RULE THIS TEST OBEYS, and it is the whole reason it looks like this: a preempted writer may
300// wait ONLY by polling `w.valid()`. That poll is what ACKS the preempt — `lease.hpp`: *"the first
301// observation of a stop acks and wakes the owner … polling this from the holding thread is what lets
302// a drain/preempt make progress"* — and `grant_immediate()` blocks on
303// `writer_gate_->acked` until it happens. A writer that waits on anything else while holding its
304// lease (a condition variable, a flag only the immediate-write can set) is a CIRCULAR WAIT: the
305// immediate cannot proceed until the writer acks, and the writer will not ack until the immediate
306// proceeds. That is a deadlock, not a flake, and it is how a previous attempt at this test ended.
307//
308// WHAT WAS WRONG BEFORE. The writer slept 1 ms after each of three chunks and the main thread slept
309// 1 ms once, so the writer needed ~3 ms and the preempt was aimed at a 1 ms window. `sleep_for` was
310// doing the job of a synchronisation primitive, and under load the main thread was descheduled past
311// the writer entirely: the writer finished first, set `finished_first = 2`, and the assertion below
312// failed. Roughly one run in three on a loaded machine, and it blocked every push.
313//
314// Both interleavings are LEGAL to the module — `grant_immediate()` short-circuits on `!writer_`
315// with the comment *"a non-looping writer may release during the wait"* — so the module was never
316// the bug. This test is about the preempting interleaving specifically, so it now ARRANGES that
317// interleaving instead of gambling on the scheduler for it.
318TEST(Memory, NegativePriorityImmediateWritePreemptsTheActiveWriterWhichThenResumes) {
319 using clock = std::chrono::steady_clock;
320 // Every wait below is bounded. An unbounded spin would turn a genuine preempt/resume regression
321 // into a hung CI runner, which is a strictly worse failure than the flake being fixed here.
322 constexpr auto kPatience = std::chrono::seconds(5);
324 auto o = mem::own(std::string(""));
325 std::atomic<bool> writer_holding{false};
326 std::atomic<bool> preempt_seen{false};
327 std::atomic<bool> timed_out{false};
328 std::atomic<const char*> stuck_at{nullptr};
329 std::atomic<int> chunks_at_stall{-1};
330 std::atomic<int> chunks{0}, finished_first{0}; // 1 = immediate finished first, 2 = writer
332 // Cooperative spin: polls (so a preempt can make progress) and gives up rather than hanging.
333 //
334 // IT BACKS OFF, and that is not a nicety. A pure `yield()` loop keeps this thread permanently
335 // runnable, and on a loaded box the scheduler will happily keep feeding it while starving the
336 // very thread it is waiting for — the writer spinning at full tilt can hold off the main thread
337 // that owes it the preempt. That showed up as this test's own 5 s deadline firing under a 12x
338 // load. Spin briefly for latency, then sleep so somebody else can run.
339 const auto spin_until = [&](const char* what, auto&& done) {
340 const auto deadline = clock::now() + kPatience;
341 for (int i = 0; !done(); ++i) {
342 if (clock::now() > deadline) {
343 stuck_at = what; chunks_at_stall = chunks.load(); timed_out = true; return false;
344 }
345 if (i < 1000) std::this_thread::yield();
346 else std::this_thread::sleep_for(std::chrono::microseconds(100));
347 }
348 return true;
349 };
351 // A long-running writer: appends "A" three times, yielding to an immediate-write between chunks.
352 std::thread writer([&] {
353 auto w = o.rwrite().acquire(); // priority 0
354 writer_holding = true;
355 // ANY observation of `!valid()` is a preempt, wherever it happens — and it must be recorded
356 // there, not only at the top of the loop. Checking only at the top was a real bug and cost a
357 // 5 s stall: the immediate-write can be absorbed ENTIRELY by the await-regrant spin below,
358 // because that spin's `valid()` call is itself the ack. The writer would then resume with
359 // `preempt_seen` still false and sit waiting for a second preempt nobody was going to send.
360 const auto lease_valid = [&] {
361 const bool v = w.valid();
362 if (!v) preempt_seen = true;
363 return v;
364 };
365 for (int i = 0; i < 3; ++i) {
366 if (!spin_until("writer:await-regrant", lease_valid)) return; // await regrant
367 w.write(w.read() + "A"); // safe: w.valid(), write() is the CURRENT location
368 ++chunks;
369 // Refuse to finish until the preemption has actually been OBSERVED. This is what makes
370 // `finished_first` a fact rather than a coin flip. Skipped when the immediate-write
371 // already came and went before the first chunk — waiting for a second preempt that
372 // nobody will send would hang.
373 if (i == 0 && !preempt_seen) {
374 if (!spin_until("writer:await-preempt", [&] { return !lease_valid(); })) return;
375 preempt_seen = true;
376 }
377 }
378 if (finished_first == 0) finished_first = 2;
379 });
381 ASSERT_TRUE(spin_until("main:await-writer-holding", [&] { return writer_holding.load(); })) << "the writer never acquired";
382 {
383 auto w = o.rwrite<mem::immediate>().acquire(); // NEGATIVE priority (== -1) -> immediate-write
384 w.write(w.read() + "!"); // emergency correction, mid-writer
385 if (finished_first == 0) finished_first = 1;
386 } // release -> writer's lease becomes valid() again
387 writer.join();
389 ASSERT_FALSE(timed_out) << "a wait exceeded " << kPatience.count() << "s at ["
390 << (stuck_at.load() ? stuck_at.load() : "?") << "] with chunks="
391 << chunks_at_stall.load() << " preempt_seen=" << preempt_seen.load()
392 << " finished_first=" << finished_first.load()
393 << " — the preempt/resume handshake is not completing";
394 EXPECT_EQ(finished_first, 1); // the immediate-write completed before the writer resumed
395 EXPECT_EQ(chunks, 3); // the preempted writer resumed and finished all its work
396 const auto result = o.rread().acquire().read();
397 EXPECT_NE(result.find('!'), std::string::npos); // the emergency write landed
398 EXPECT_EQ(std::count(result.begin(), result.end(), 'A'), 3); // the preempted writer's work survived
401// ── compile-time-only write renewal (deliberate friction) ────────────────────────────────
403TEST(Memory, WriteRenewalIsCompileTimeOnly) {
404 // A plain write lease is one-shot; a renewable write lease is a DISTINCT, compile-time-selected
405 // type. The type system — not a runtime flag — is what lets a writer re-lease.
406 static_assert(!std::is_same_v<mem::Lease<int, mem::write>, mem::Lease<int, mem::write_renewable>>,
407 "renewable write is its own type, declared at compile time");
408 SUCCEED();