census.rs
16.6 kB · rust · 561 lines
1use mrlycore::{json, Json};2use mrlylab::ledger::{closed, keys, terms, Cost, Key, Tier, TERMS};3use std::sync::{Mutex, OnceLock};4use wasm_bindgen::prelude::*;56const CAP: usize = 48;7const CELLS: u128 = 100_000;8const WINDOW: i128 = 1_000;9const BLOCK: usize = 8;10const DEPTHS: [usize; 4] = [8, 16, 32, 48];1112#[derive(Clone, Copy, PartialEq, Eq)]13enum Stop {14 Ceiling,15 Cap,16 Budget,17}1819impl Stop {20 fn slug(self) -> &'static str {21 match self {22 Stop::Ceiling => "ceiling",23 Stop::Cap => "cap",24 Stop::Budget => "budget",25 }26 }27 fn slot(self) -> usize {28 match self {29 Stop::Ceiling => 0,30 Stop::Cap => 1,31 Stop::Budget => 2,32 }33 }34}3536struct Row {37 key: Key,38 tier: Tier,39 stop: Stop,40 depth: usize,41 repeats: usize,42 low: usize,43 writes: Vec<(u16, u8)>,44}4546struct Snap {47 depth: usize,48 never: usize,49 once: usize,50 many: usize,51 first: usize,52 run: usize,53 incidences: u64,54 deep: usize,55}5657#[derive(Default)]58struct Sheet {59 listed: Vec<(Key, Tier)>,60 tiers: Vec<(Tier, usize)>,61 rows: Vec<Option<Row>>,62 built: usize,63 order: Vec<usize>,64 cursor: usize,65 stage: usize,66 counts: Vec<u32>,67 incidences: u64,68 pairs: u64,69 low: u64,70 stops: [usize; 3],71 blank: usize,72 unread: usize,73 snaps: Vec<Snap>,74}7576fn sheet() -> &'static Mutex<Sheet> {77 static SHEET: OnceLock<Mutex<Sheet>> = OnceLock::new();78 SHEET.get_or_init(|| Mutex::new(Sheet::default()))79}8081fn listing(sheet: &mut Sheet) {82 if !sheet.listed.is_empty() {83 return;84 }85 sheet.counts = vec![0; WINDOW as usize + 1];86 for tier in Tier::ALL {87 let batch = keys(tier);88 sheet.tiers.push((tier, batch.len()));89 sheet90 .listed91 .extend(batch.into_iter().map(|key| (key, tier)));92 }93 sheet.order = (0..sheet.listed.len()).collect();94 sheet.rows = (0..sheet.listed.len()).map(|_| None).collect();95}9697fn footprint(key: &Key, index: usize) -> Option<u128> {98 let (number, level) = key.axis.place(index, key.number());99 let number = number as u128;100 let dimension = key.dimension as u32;101 match key.measure.cost() {102 Cost::Closed => Some(1),103 Cost::Convolved => {104 let tile = number.checked_pow(dimension)?;105 let side = number.checked_pow(level)?;106 let span = key.dimension as u128 * (side - 1) + 1;107 tile.checked_add(span.checked_mul(level as u128)?)108 }109 Cost::Grid => number.checked_pow(dimension.checked_mul(level)?),110 }111}112113fn allowance(key: &Key) -> usize {114 (0..CAP)115 .take_while(|&index| footprint(key, index).is_some_and(|cells| cells <= CELLS))116 .count()117}118119fn ceiling_stop(read: &[i128]) -> Option<usize> {120 let mut previous: Option<i128> = None;121 for (index, &term) in read.iter().enumerate() {122 if previous.is_some_and(|last| term <= last) {123 return None;124 }125 if term > WINDOW {126 return Some(index);127 }128 previous = Some(term);129 }130 None131}132133fn gather(window: &[i128]) -> (Vec<(u16, u8)>, usize, usize) {134 let low = window.iter().filter(|&&term| term < 1).count();135 let mut writes: Vec<(u16, u8)> = Vec::new();136 let mut inside = 0;137 for (index, &term) in window.iter().enumerate() {138 if !(1..=WINDOW).contains(&term) {139 continue;140 }141 inside += 1;142 let value = term as u16;143 if let Err(slot) = writes.binary_search_by_key(&value, |&(term, _)| term) {144 writes.insert(slot, (value, index as u8));145 }146 }147 let repeats = inside - writes.len();148 (writes, repeats, low)149}150151fn render(key: &Key, tier: Tier, depth: usize) -> Option<Row> {152 let full = allowance(key);153 let allowed = full.min(depth);154 let mut count = BLOCK.min(allowed);155 let window;156 let stop;157 loop {158 let (read, capped) = terms(key, count, CELLS).ok()?;159 let short = capped || read.len() < count;160 if let Some(edge) = ceiling_stop(&read) {161 window = read[..=edge].to_vec();162 stop = Stop::Ceiling;163 break;164 }165 if short {166 window = read;167 stop = Stop::Budget;168 break;169 }170 if count >= allowed {171 window = read;172 stop = if allowed < full || full == CAP {173 Stop::Cap174 } else {175 Stop::Budget176 };177 break;178 }179 count = (count * 2).min(allowed);180 }181 let (writes, repeats, low) = gather(&window);182 Some(Row {183 key: *key,184 tier,185 stop,186 depth: window.len(),187 repeats,188 low,189 writes,190 })191}192193impl Sheet {194 fn add(&mut self, row: &Row, sign: i64) {195 for &(value, _) in &row.writes {196 let slot = &mut self.counts[value as usize];197 *slot = (*slot as i64 + sign) as u32;198 }199 let terms = row.writes.len() as i64;200 self.incidences = (self.incidences as i64 + sign * terms) as u64;201 self.pairs = (self.pairs as i64 + sign * (terms + row.repeats as i64)) as u64;202 self.low = (self.low as i64 + sign * row.low as i64) as u64;203 self.stops[row.stop.slot()] = (self.stops[row.stop.slot()] as i64 + sign) as usize;204 if row.writes.is_empty() {205 self.blank = (self.blank as i64 + sign) as usize;206 }207 }208 fn tally(&self) -> (usize, usize, usize) {209 let mut never = 0;210 let mut once = 0;211 let mut many = 0;212 for &count in &self.counts[1..] {213 match count {214 0 => never += 1,215 1 => once += 1,216 _ => many += 1,217 }218 }219 (never, once, many)220 }221 fn first_miss(&self) -> usize {222 self.counts[1..]223 .iter()224 .position(|&count| count == 0)225 .map_or(0, |index| index + 1)226 }227 fn longest_run(&self) -> usize {228 let mut best = 0;229 let mut run = 0;230 for &count in &self.counts[1..] {231 run = if count == 0 { 0 } else { run + 1 };232 best = best.max(run);233 }234 best235 }236 fn deepenable(&self) -> Vec<usize> {237 self.rows238 .iter()239 .enumerate()240 .filter(|(_, row)| row.as_ref().is_some_and(|row| row.stop == Stop::Cap))241 .map(|(index, _)| index)242 .collect()243 }244 fn snap(&mut self, depth: usize) {245 let (never, once, many) = self.tally();246 let deep = self.deepenable().len();247 self.snaps.push(Snap {248 depth,249 never,250 once,251 many,252 first: self.first_miss(),253 run: self.longest_run(),254 incidences: self.incidences,255 deep,256 });257 }258 fn bands(&self) -> Vec<Json> {259 let mut out = Vec::new();260 let mut first = 1usize;261 while first <= WINDOW as usize {262 let last = (first * 10 - 1).min(WINDOW as usize);263 let missed = self.counts[first..=last]264 .iter()265 .filter(|&&count| count == 0)266 .count();267 let width = last - first + 1;268 out.push(json!({269 "first": first,270 "last": last,271 "width": width,272 "missed": missed,273 "density": missed as f64 / width as f64,274 }));275 first *= 10;276 }277 out278 }279 fn coverage(&self) -> Vec<Json> {280 let width = WINDOW as usize + 1;281 let mut seen: Vec<Vec<bool>> = Tier::ALL.iter().map(|_| vec![false; width]).collect();282 let mut counted = [0usize; 4];283 for row in self.rows.iter().flatten() {284 let slot = Tier::ALL285 .iter()286 .position(|&tier| tier == row.tier)287 .unwrap_or(0);288 counted[slot] += 1;289 for &(value, _) in &row.writes {290 seen[slot][value as usize] = true;291 }292 }293 Tier::ALL294 .iter()295 .enumerate()296 .map(|(slot, tier)| {297 let written = seen[slot][1..].iter().filter(|&&hit| hit).count();298 let alone = (1..width)299 .filter(|&value| {300 seen[slot][value] && seen.iter().filter(|tier| tier[value]).count() == 1301 })302 .count();303 json!({304 "tier": tier.slug(),305 "rows": counted[slot],306 "written": written,307 "alone": alone,308 })309 })310 .collect()311 }312 fn depth(&self) -> usize {313 DEPTHS[self.stage.min(DEPTHS.len() - 1)]314 }315 fn shallow(&self) -> usize {316 self.snaps.last().map_or(0, |snap| snap.depth)317 }318}319320fn head(row: &Row) -> Vec<String> {321 terms(&row.key, TERMS.min(row.depth), CELLS)322 .map(|(read, _)| read.iter().map(|term| term.to_string()).collect())323 .unwrap_or_default()324}325326fn spell(row: &Row, value: u16) -> Json {327 let key = &row.key;328 let at = row329 .writes330 .binary_search_by_key(&value, |&(term, _)| term)331 .map_or(0, |slot| row.writes[slot].1);332 let side = key.axis.place(at as usize, key.number()).0;333 json!({334 "name": key.name(),335 "code": key.code.to_string(),336 "d": key.dimension,337 "q": key.base,338 "measure": key.measure.slug(),339 "axis": key.axis.slug(),340 "number": key.number(),341 "start": key.axis.start(),342 "tier": row.tier.slug(),343 "closed": closed(key).ok().flatten().map_or(String::new(), |form| form.text()),344 "stop": row.stop.slug(),345 "depth": row.depth,346 "index": at,347 "term": key.axis.start() + at as i32,348 "side": side,349 "writes": row.writes.len(),350 "head": head(row),351 })352}353354fn snapshot(snap: &Snap) -> Json {355 json!({356 "depth": snap.depth,357 "never": snap.never,358 "once": snap.once,359 "multiple": snap.many,360 "written": snap.once + snap.many,361 "first_miss": snap.first,362 "run": snap.run,363 "incidences": snap.incidences,364 "deepenable": snap.deep,365 })366}367368/// Prints the pinned window of the census: the term cap, the cells a term, the ceiling, the deepening passes and the registry the walk reads, as JSON.369#[wasm_bindgen]370pub fn census_window() -> String {371 let mut guard = sheet().lock().expect("the census sheet is not poisoned");372 listing(&mut guard);373 let tiers: Vec<Json> = guard374 .tiers375 .iter()376 .map(|(tier, count)| json!({ "tier": tier.slug(), "keys": count }))377 .collect();378 json!({379 "cap": CAP,380 "cells": CELLS.to_string(),381 "ceiling": WINDOW.to_string(),382 "head": TERMS,383 "depths": DEPTHS.to_vec(),384 "registry": guard.listed.len(),385 "tiers": tiers,386 })387 .to_string()388}389390/// Walks the next span of rows at the pass's depth, deepening only the rows the last pass cut at the depth, and reports how far the walk is, as JSON.391#[wasm_bindgen]392pub fn census_walk(span: usize) -> String {393 let mut guard = sheet().lock().expect("the census sheet is not poisoned");394 listing(&mut guard);395 let depth = guard.depth();396 let stop = guard.order.len().min(guard.cursor.saturating_add(span));397 for slot in guard.cursor..stop {398 let at = guard.order[slot];399 let (key, tier) = guard.listed[at];400 let Some(row) = render(&key, tier, depth) else {401 guard.unread += 1;402 continue;403 };404 guard.add(&row, 1);405 if let Some(old) = guard.rows[at].replace(row) {406 guard.add(&old, -1);407 } else {408 guard.built += 1;409 }410 }411 guard.cursor = stop;412 let done = stop;413 let total = guard.order.len();414 if done == total {415 guard.snap(depth);416 if guard.stage + 1 < DEPTHS.len() {417 guard.stage += 1;418 guard.order = guard.deepenable();419 guard.cursor = 0;420 } else {421 guard.order = Vec::new();422 guard.cursor = 0;423 }424 }425 let (never, once, many) = guard.tally();426 json!({427 "depth": depth,428 "done": done,429 "total": total,430 "rows": guard.built,431 "pending": guard.order.len().saturating_sub(guard.cursor),432 "next": guard.depth(),433 "complete": guard.shallow() == CAP,434 "never": never,435 "once": once,436 "multiple": many,437 })438 .to_string()439}440441/// Reads the census so far: the never, once and multiple counts of the window, the first miss, the longest written run, the incidences both ways, the truncation tally, the miss density by decade, the tier coverage and every completed depth, as JSON.442#[wasm_bindgen]443pub fn census_report() -> String {444 let guard = sheet().lock().expect("the census sheet is not poisoned");445 let (never, once, many) = guard.tally();446 let written = once + many;447 let depths: Vec<Json> = guard.snaps.iter().map(snapshot).collect();448 json!({449 "ceiling": WINDOW.to_string(),450 "depth": guard.shallow(),451 "rows": guard.built,452 "registry": guard.listed.len(),453 "never": never,454 "once": once,455 "multiple": many,456 "written": written,457 "share": written as f64 / WINDOW as f64,458 "first_miss": guard.first_miss(),459 "run": guard.longest_run(),460 "incidences": guard.incidences,461 "pairs": guard.pairs,462 "repeats": guard.pairs - guard.incidences,463 "low": guard.low,464 "ceiling_stopped": guard.stops[0],465 "cap_stopped": guard.stops[1],466 "budget_stopped": guard.stops[2],467 "blank": guard.blank,468 "unread": guard.unread,469 "bands": guard.bands(),470 "tiers": guard.coverage(),471 "depths": depths,472 })473 .to_string()474}475476/// Counts the rows writing every integer of the window in turn, the first entry the integer one.477#[wasm_bindgen]478pub fn census_counts() -> Vec<u32> {479 let guard = sheet().lock().expect("the census sheet is not poisoned");480 guard.counts[1..].to_vec()481}482483/// Lists the integers the most rows write, the heaviest first and the least integer ahead on a tie, as JSON.484#[wasm_bindgen]485pub fn census_champions(take: usize) -> String {486 let guard = sheet().lock().expect("the census sheet is not poisoned");487 let mut all: Vec<(usize, u32)> = guard488 .counts489 .iter()490 .enumerate()491 .skip(1)492 .map(|(value, &count)| (value, count))493 .collect();494 all.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));495 all.truncate(take);496 let rows: Vec<Json> = all497 .iter()498 .map(|&(value, count)| json!({ "value": value, "rows": count }))499 .collect();500 json!(rows).to_string()501}502503/// Lists the least integers of the window no row writes, as JSON.504#[wasm_bindgen]505pub fn census_misses(take: usize) -> String {506 let guard = sheet().lock().expect("the census sheet is not poisoned");507 let rows: Vec<usize> = guard508 .counts509 .iter()510 .enumerate()511 .skip(1)512 .filter(|(_, &count)| count == 0)513 .map(|(value, _)| value)514 .take(take)515 .collect();516 json!(rows).to_string()517}518519/// Reads every registry row writing one integer: the count, the tally by tier, and one page of rows with the design, the measure, the closed form and the index the integer lands on, as JSON.520#[wasm_bindgen]521pub fn census_writers(value: usize, page: usize, rows: usize) -> String {522 let guard = sheet().lock().expect("the census sheet is not poisoned");523 let inside = (1..=WINDOW as usize).contains(&value);524 let wanted = value as u16;525 let found: Vec<&Row> = if inside {526 guard527 .rows528 .iter()529 .flatten()530 .filter(|row| {531 row.writes532 .binary_search_by_key(&wanted, |&(term, _)| term)533 .is_ok()534 })535 .collect()536 } else {537 Vec::new()538 };539 let tiers: Vec<Json> = Tier::ALL540 .iter()541 .map(|tier| {542 let count = found.iter().filter(|row| row.tier == *tier).count();543 json!({ "tier": tier.slug(), "rows": count })544 })545 .collect();546 let shown: Vec<Json> = found547 .iter()548 .skip(page * rows)549 .take(rows)550 .map(|row| spell(row, wanted))551 .collect();552 json!({553 "value": value,554 "inside": inside,555 "count": guard.counts.get(value).copied().unwrap_or(0),556 "rows": found.len(),557 "tiers": tiers,558 "shown": shown,559 })560 .to_string()561}