Skip to content

Commit 3da8fbb

Browse files
luisleo526claude
andcommitted
Cohort exposure fold: record the selector copy's sites and pin its order and boundary
The overflow completion's private copy of the original selector declares a next and a positions variable and a next inside its position loop; the reviewed site inventory did not know them, so the source-bounds gate named three new assign identities and the tests that run the gate on the real tree failed with it. The three records carry the scope text and ordinal the gate printed. No manifest entry changes state and none is added, so the entry and unreviewed counts stay as they are. The rows that guard the overflow path were too weak to catch an order or filter error in that copy: one live row of 1.0 units adds exactly in any order, and a path value of 3 is what both completions return. A new fold row uses four live rows with a 1e16 row among ones, derives the only double an acceptance-ordered sum can give (a different order gives another value), cycles NaN, both infinities, negative zero, denormals and the largest double through the finite and positive filter, and pins which completion ran from the step count at M one below, at, and above the selector charge. The work row now also asserts that two windows differing only in M cost exactly the same steps and that the cost stays within (R + P)(P + 2). Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent f035f95 commit 3da8fbb

3 files changed

Lines changed: 128 additions & 1 deletion

File tree

‎ci/cr150-source-sites.json‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30480,6 +30480,52 @@
3048030480
"spelling": "remaining = . . .",
3048130481
"ordinal": 1
3048230482
},
30483+
{
30484+
"file": "src/source/pine_adapter.cpp",
30485+
"symbol": "next",
30486+
"scope": [
30487+
"namespace pineforge :: source :: detail #1",
30488+
"CohortExposureFold fold_cohort_exposure ( const OriginRoster & origins , const std :: unordered_map < std :: uint64_t , double > & live_units_by_origin ) noexcept #1",
30489+
"if ( origins . members ( ) . size ( ) > 4 * live_units_by_origin . size ( ) + 16 ) #1",
30490+
"if ( static_cast < std :: uint64_t > ( origins . members ( ) . size ( ) ) > = selector_charge ) #1",
30491+
") #1"
30492+
],
30493+
"cls": "assign",
30494+
"spelling": "next = . . .",
30495+
"ordinal": 1
30496+
},
30497+
{
30498+
"file": "src/source/pine_adapter.cpp",
30499+
"symbol": "positions",
30500+
"scope": [
30501+
"namespace pineforge :: source :: detail #1",
30502+
"CohortExposureFold fold_cohort_exposure ( const OriginRoster & origins , const std :: unordered_map < std :: uint64_t , double > & live_units_by_origin ) noexcept #1",
30503+
"if ( origins . members ( ) . size ( ) > 4 * live_units_by_origin . size ( ) + 16 ) #1",
30504+
"if ( static_cast < std :: uint64_t > ( origins . members ( ) . size ( ) ) > = selector_charge ) #1",
30505+
") #1",
30506+
"for ( const auto & unit : live_units_by_origin ) #1"
30507+
],
30508+
"cls": "assign",
30509+
"spelling": "positions = . . .",
30510+
"ordinal": 1
30511+
},
30512+
{
30513+
"file": "src/source/pine_adapter.cpp",
30514+
"symbol": "next",
30515+
"scope": [
30516+
"namespace pineforge :: source :: detail #1",
30517+
"CohortExposureFold fold_cohort_exposure ( const OriginRoster & origins , const std :: unordered_map < std :: uint64_t , double > & live_units_by_origin ) noexcept #1",
30518+
"if ( origins . members ( ) . size ( ) > 4 * live_units_by_origin . size ( ) + 16 ) #1",
30519+
"if ( static_cast < std :: uint64_t > ( origins . members ( ) . size ( ) ) > = selector_charge ) #1",
30520+
") #1",
30521+
"for ( const auto & unit : live_units_by_origin ) #1",
30522+
"for ( const auto position : * positions ) #1",
30523+
"if ( ! have_next || position < next ) #1"
30524+
],
30525+
"cls": "assign",
30526+
"spelling": "next = . . .",
30527+
"ordinal": 1
30528+
},
3048330529
{
3048430530
"file": "src/source/pine_adapter.cpp",
3048530531
"symbol": "next",

‎tests/test_cohort_exposure_fold.cpp‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -154,6 +154,78 @@ void overflow_fallback_large_window() {
154154
assert(actual.total == static_cast<double>(mapped_positions));
155155
}
156156

157+
void overflow_selector_interleavings() {
158+
constexpr std::array<std::uint64_t, 3> small_ids{{19, 43, 71}};
159+
constexpr std::size_t live_rows = small_ids.size() + 1;
160+
constexpr std::size_t mapped_positions = detail::kCohortFoldStack + 2;
161+
constexpr auto selector_charge =
162+
(mapped_positions + 1) * (live_rows + mapped_positions);
163+
constexpr auto gather_steps = live_rows + mapped_positions;
164+
// In pass t = 0..P, each row is visited and t accepted positions are
165+
// skipped. Each unexhausted row adds one position visit. Those visits
166+
// total last_position + 1 per row: 5 + (P - 2) + (P - 1) + P = 3P + 2.
167+
constexpr auto selector_steps = gather_steps
168+
+ live_rows * (mapped_positions + 1)
169+
+ mapped_positions * (mapped_positions + 1) / 2
170+
+ 3 * mapped_positions + 2;
171+
const std::array<std::size_t, 3> windows{{
172+
mapped_positions + selector_charge, selector_charge - 1, selector_charge
173+
}};
174+
const double tiny = std::numeric_limits<double>::denorm_min();
175+
const std::array<double, 7> values{{
176+
std::numeric_limits<double>::quiet_NaN(),
177+
std::numeric_limits<double>::infinity(),
178+
-std::numeric_limits<double>::infinity(),
179+
-0.0, tiny, std::numeric_limits<double>::max(), -1.0
180+
}};
181+
for (const auto window : windows) {
182+
OriginRoster origins;
183+
Units units{{7, 1e16}, {19, 1.0}, {43, 1.0}, {71, 1.0}};
184+
for (std::size_t i = 0; i < mapped_positions - 1; ++i) {
185+
if (i == 4) push(origins, 7);
186+
push(origins, small_ids[i % small_ids.size()]);
187+
}
188+
assert(origins.members().size() == mapped_positions);
189+
assert(units.size() == live_rows);
190+
for (std::size_t i = origins.size(); i < window; ++i)
191+
push(origins, 1000 + i);
192+
assert(origins.members().size() == window);
193+
assert(window > 4 * live_rows + 16);
194+
const auto actual = check(origins, units);
195+
assert(actual.path == 3); // P exceeds the stack's capacity.
196+
// Four ones precede 1e16, giving the exactly representable sum below.
197+
// Its ULP is 2 and its significand is even, so later ones round away.
198+
// Moving 1e16 first loses every one; even three ones added before
199+
// 1e16 round to 1e16 + 4, unlike three added after it.
200+
const double expected = 10000000000000004.0;
201+
assert(std::memcmp(&actual.total, &expected, sizeof expected) == 0);
202+
if (window < selector_charge) {
203+
// The gather visits R + P; the roster completion visits all M.
204+
assert(actual.steps == gather_steps + window);
205+
assert(actual.steps >= origins.members().size());
206+
} else {
207+
assert(actual.steps == selector_steps);
208+
assert(actual.steps < origins.members().size());
209+
}
210+
for (const auto id : small_ids) {
211+
for (const auto value : values) {
212+
units[id] = value;
213+
const auto special = check(origins, units);
214+
assert(special.path == 3 && special.steps == actual.steps);
215+
}
216+
units[id] = 1.0;
217+
}
218+
units[7] = 0.0;
219+
for (const auto id : small_ids) units[id] = tiny;
220+
const auto denormal = check(origins, units);
221+
// The large row is zero; all P - 1 small positions contribute tiny.
222+
// This integer multiple is exact and makes rejecting denormals visible.
223+
const double expected_tiny = static_cast<double>(mapped_positions - 1) * tiny;
224+
assert(std::memcmp(&denormal.total, &expected_tiny, sizeof expected_tiny) == 0);
225+
assert(denormal.path == 3 && denormal.steps == actual.steps);
226+
}
227+
}
228+
157229
detail::CohortExposureFold check_stack_sort(const OriginRoster& origins,
158230
const Units& units) {
159231
assert(origins.members().size() > 4 * units.size() + 16);
@@ -277,6 +349,7 @@ int main() {
277349
special_values_and_multiplicity();
278350
boundary_values();
279351
overflow_fallback_large_window();
352+
overflow_selector_interleavings();
280353
stack_sort_special_values();
281354
stack_sort_interleavings();
282355
randomized_mutations();

‎tests/test_cohort_exposure_work.cpp‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -279,9 +279,10 @@ void history_guard() {
279279
static_cast<unsigned long long>(large.steps),
280280
static_cast<unsigned>(small.path), static_cast<unsigned>(large.path));
281281

282+
constexpr std::size_t live_rows = 1;
282283
constexpr std::size_t mapped_positions =
283284
source::detail::kCohortFoldStack + 1;
284-
const auto overflow_fold = [mapped_positions](std::size_t tail) {
285+
const auto overflow_fold = [](std::size_t tail) {
285286
source::OriginRoster origins;
286287
std::unordered_map<std::uint64_t, double> units{{1, 1.0}};
287288
for (std::size_t i = 0; i < mapped_positions; ++i)
@@ -312,6 +313,13 @@ void history_guard() {
312313
const auto derived_bound = static_cast<std::uint64_t>(
313314
mapped_positions * (mapped_positions + 1));
314315
CHECK(overflow_delta <= derived_bound);
316+
// Both M exceed selector_charge: the gather takes R + P steps, and
317+
// the selector's mapped lists and row scans are identical in both calls.
318+
// No tail member is visited, so changing only M adds exactly zero steps.
319+
CHECK(overflow_delta == 0);
320+
// The gather plus P + 1 selector passes cost at most
321+
// (R + P) + (P + 1) * (R + P) = (R + P) * (P + 2).
322+
CHECK(wide.steps <= (live_rows + mapped_positions) * (mapped_positions + 2));
315323
std::printf("exposure-history-overflow %llu %llu delta=%llu\n",
316324
static_cast<unsigned long long>(narrow.steps),
317325
static_cast<unsigned long long>(wide.steps),

0 commit comments

Comments
 (0)