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