404-solution / includes / diagnostics / DiagnosticEvidenceBudget.php

DiagnosticEvidenceBudget.php in 404 Solution trunk, at includes/diagnostics/DiagnosticEvidenceBudget.php

204 lines 7.9 KB

Raw Download Zip

1	<?php
2
3	if (!defined('ABSPATH')) {
4	exit;
5	}
6
7	/**
8	* Which line indexes survive a hard byte ceiling, given an already
9	* priority-ordered list of request groups.
10	*
11	* ABJ_404_Solution_DiagnosticEvidencePriority decides WHO is prioritized and
12	* in what order; this class decides, mechanically, how many of each
13	* prioritized group's bytes actually fit. A request with no terminal event is
14	* granted its full record run before any reserve is split across the rest,
15	* because its middle is the only account of a stall (report 193: a
16	* 165-second holder with no request_end had 7 mid-flight records dropped by
17	* an even split before this ordering existed). Every other group competes
18	* for whatever budget remains and loses its own middle first when it does
19	* not fully fit, because a terminal event anchors its tail as "where it
20	* stopped" and its middle is comparatively spendable.
21	*/
22	final class ABJ_404_Solution_DiagnosticEvidenceBudget {
23
24	/**
25	* Grant budget in priority order. Each prioritized request still to come
26	* holds a reserved share, so an early one can use everything that is not
27	* reserved but can never consume a later failure's guarantee.
28	*
29	* @param array<int, string> $lines
30	* @param array<string, ABJ_404_Solution_DiagnosticRequestGroup> $groups
31	* @param array<int, string> $ordered
32	* @return array{lines: array<int, string>, requests: int, records: int, bytes: int,
33	* includedIds: array<string, bool>, elided: int}
34	*/
35	public static function allocate(array $lines, array $groups, array $ordered,
36	int $prioritizedCount, int $budgetBytes): array {
37	$remaining = max(0, $budgetBytes);
38	$keptIndexes = array();
39	$notes = array();
40	$included = array();
41	$elided = 0;
42
43	$grantedWhole = array();
44	foreach ($ordered as $position => $id) {
45	if ($position >= $prioritizedCount \|\| !$groups[$id]->isMaximallyDecisive()) {
46	continue;
47	}
48	$bytes = $groups[$id]->bytes();
49	if ($bytes > $remaining) {
50	// Does not even fit in what is left of the whole budget;
51	// fall through to the ordinary allowance-based picking below
52	// rather than dropping it outright.
53	continue;
54	}
55	foreach ($groups[$id]->indexes() as $index) {
56	$keptIndexes[$index] = true;
57	}
58	$remaining -= $bytes;
59	$included[$id] = true;
60	$grantedWhole[$id] = true;
61	}
62
63	$rest = array();
64	$prioritizedLeft = 0;
65	foreach ($ordered as $position => $id) {
66	if (isset($grantedWhole[$id])) {
67	continue;
68	}
69	$isPrioritized = $position < $prioritizedCount;
70	if ($isPrioritized) {
71	$prioritizedLeft++;
72	}
73	$rest[] = array('id' => $id, 'prioritized' => $isPrioritized);
74	}
75	$reservePerRequest = $prioritizedLeft > 0 ? intdiv(max(0, $remaining), $prioritizedLeft) : 0;
76
77	foreach ($rest as $entry) {
78	$id = $entry['id'];
79	if ($entry['prioritized']) {
80	$prioritizedLeft--;
81	}
82	$heldBack = $entry['prioritized'] ? ($prioritizedLeft * $reservePerRequest) : 0;
83	$allowance = max(0, $remaining - $heldBack);
84	if ($allowance <= 0) {
85	continue;
86	}
87	$picked = self::pickWithinAllowance($lines, $groups[$id]->indexes(), $allowance, $id);
88	if ($picked['indexes'] === array()) {
89	continue;
90	}
91	foreach ($picked['indexes'] as $index) {
92	$keptIndexes[$index] = true;
93	}
94	$remaining -= $picked['bytes'];
95	$included[$id] = true;
96	$elided += $picked['elided'];
97	if ($picked['elided'] > 0) {
98	$notes[max($picked['indexes'])] = self::elisionNote($id, $picked['elided']);
99	}
100	}
101
102	ksort($keptIndexes);
103	$out = array();
104	$records = 0;
105	foreach (array_keys($keptIndexes) as $index) {
106	$out[] = $lines[$index];
107	$records++;
108	if (isset($notes[$index])) {
109	$out[] = $notes[$index];
110	}
111	}
112
113	return array(
114	'lines' => $out,
115	'requests' => count($included),
116	'records' => $records,
117	'bytes' => max(0, $budgetBytes) - $remaining,
118	'includedIds' => $included,
119	'elided' => $elided,
120	);
121	}
122
123	/**
124	* The line indexes of one request that fit in $allowance. When the whole
125	* request does not fit, records are taken from both ENDS: the opening
126	* records carry the environment the request ran in, and the last ones are
127	* where it stopped. The middle is what a reader can most afford to lose --
128	* true only because a terminal event exists to anchor that tail. A request
129	* with no terminal event is granted its full run before this is ever
130	* called (see allocate()); this heuristic is backwards for one, because
131	* its middle is the only account of the stall, not the least of it.
132	*
133	* @param array<int, string> $lines
134	* @param array<int, int> $indexes
135	* @return array{indexes: array<int, int>, bytes: int, elided: int}
136	*/
137	private static function pickWithinAllowance(array $lines, array $indexes, int $allowance,
138	string $requestId): array {
139	$total = 0;
140	foreach ($indexes as $index) {
141	$total += strlen($lines[$index]) + 1;
142	}
143	if ($total <= $allowance) {
144	return array('indexes' => $indexes, 'bytes' => $total, 'elided' => 0);
145	}
146
147	// The note that will declare the elision costs bytes too, and its
148	// length depends on the request id (up to 64 characters) and the
149	// count. Reserved at its true upper bound rather than at a guessed
150	// constant: a reserve that is one byte short makes the returned block
151	// exceed a budget the caller was promised was hard.
152	$noteReserve = strlen(self::elisionNote($requestId, PHP_INT_MAX)) + 1;
153	$allowance -= $noteReserve;
154	$head = array();
155	$tail = array();
156	$used = $noteReserve;
157	$low = 0;
158	$high = count($indexes) - 1;
159	$fromHead = true;
160	while ($low <= $high && $allowance > 0) {
161	$index = $fromHead ? $indexes[$low] : $indexes[$high];
162	$cost = strlen($lines[$index]) + 1;
163	if ($cost > $allowance) {
164	if (!$fromHead) {
165	break;
166	}
167	// The head record did not fit; a shorter tail record still might.
168	$fromHead = false;
169	continue;
170	}
171	$allowance -= $cost;
172	$used += $cost;
173	if ($fromHead) {
174	$head[] = $index;
175	$low++;
176	} else {
177	array_unshift($tail, $index);
178	$high--;
179	}
180	$fromHead = !$fromHead;
181	}
182
183	$kept = array_merge($head, $tail);
184	if ($kept === array()) {
185	return array('indexes' => array(), 'bytes' => 0, 'elided' => 0);
186	}
187	return array('indexes' => $kept, 'bytes' => $used, 'elided' => count($indexes) - count($kept));
188	}
189
190	/**
191	* A JSON line, so the excerpt stays parseable as JSONL end to end, saying
192	* exactly what was dropped and why.
193	*/
194	private static function elisionNote(string $requestId, int $elided): string {
195	$note = json_encode(array(
196	'abj404_excerpt_note' => 'records elided to fit the support budget',
197	'request_id' => $requestId === ABJ_404_Solution_DiagnosticEvidencePriority::UNJOINABLE_KEY
198	? '' : $requestId,
199	'elided_records' => $elided,
200	), JSON_UNESCAPED_SLASHES);
201	return is_string($note) ? $note : '{"abj404_excerpt_note":"records elided"}';
202	}
203	}
204