nordisk/znippy-zoomies
osm-katana/src/tiles.rs
//! **Spatial TILING + per-zoom level-of-detail** — cut a region into many small
//! covering-packed GeoParquet **slippy tiles** (`out/tiles/z{Z}/{X}/{Y}.parquet`).
//!
//! [`crate::spatial::spatial_pack`] makes ONE object prunable (Hilbert order + a
//! `covering.bbox`) so a viewport reads a few row-groups of it. This module goes one
//! step further and is the reusable, **planet-capable** engine: it partitions
//! features into Web-Mercator slippy tiles and DECIMATES each zoom so the coarse
//! views are cheap, emitting one tiny object per `(zoom, x, y)`. A viewport then
//! fetches only the handful of tile objects it overlaps.
//!
//! **Two inputs, one pipeline.** [`tile_region`] accepts either
//! * [`TileSource::Pbf`] — a planet/region **PBF** (or XML/bz2/gz) plus a [`Clip`]:
//! it runs the existing [`crate::convert`] (the gatling streaming, rayon-free,
//! clip-at-decode pass that already scales to the 157 GB planet) to produce a
//! clipped region extract, THEN tiles that extract; or
//! * [`TileSource::Extract`] — an already-clipped region GeoParquet directory
//! (`nodes.parquet` / `ways.parquet`): it tiles it directly.
//!
//! So the SAME engine serves "planet → clip → tile" and "existing extract → tile".
//!
//! **Tile shape (no new format).** Each tile is a GeoParquet 1.1 object with a WKB
//! `geometry` column (Points from the node layer, LineStrings from the way layer),
//! a Utf8 `tags` column carrying each object's OSM tags as a JSON object string —
//! the SAME encoding the monolith `ways.parquet` uses ([`crate::tags::serialize_tags`],
//! e.g. `{"highway":"residential"}`) so a class-aware reader can colour tiled objects
//! exactly as it colours the monolith — plus the `covering.bbox` struct column
//! ([`crate::spatial`]'s `down`/`up` outward rounding + [`crate::spatial::wkb_bbox`])
//! and the `geo` metadata declaring the covering ([`crate::metadata::GeoMeta`]) —
//! exactly what a covering-aware reader already prunes and culls. The `tags` column is
//! **additive**: a reader that ignores it still works, and a pre-tags tile (no `tags`
//! column, or a null cell) reads as an object with no tags.
//!
//! **Per-zoom LOD.** Points are dropped to at most one per ~screen-pixel of the tile
//! (a 256-px grid at that zoom — the "drop sub-pixel nodes" decimation); ways are
//! simplified with **Douglas-Peucker** at an epsilon of ≈ one tile pixel (the zoom's
//! ground resolution), so each zoom keeps exactly the vertices that define the curve
//! at that scale. So z6 keeps a sparse country sketch and z12 keeps almost everything.
//!
//! **Ways use bbox-overlap duplication.** Points are placed in the single tile they
//! fall in; a way is emitted into EVERY tile its bounding box overlaps (standard slippy
//! tile duplication), so a way spanning a tile border appears in each tile it crosses
//! and never clips at an edge. A pathological giant (bbox over more than
//! [`MAX_WAY_TILE_FANOUT`] tiles) falls back to its single centroid tile so the tile
//! set can't explode.
//!
//! ## Fan-out, and why this is a WINDOW and not a stream
//!
//! [`tile_region`]'s scan used to run on the calling thread: one `for batch in
//! reader` loop over `ways.parquet` then `nodes.parquet`, Douglas–Peucker per zoom,
//! straight into per-zoom HashMaps, with only the closing write fanned out. Measured
//! on oden over a full Sweden tiling, 2026-08-03: **99.5–99.7 % CPU — exactly one
//! core of 32 — from t=4 s to t=62 s**, then ~6.7 cores for the write. And **12.21 GB
//! peak**, the curve monotone 0.5 → 11.4 GB *before a single tile was written*
//! (z15 alone: 36.36 GB).
//!
//! Both are fixed here, and the two fixes must not fight each other:
//!
//! * **The scan is row-group parallel.** The unit is one parquet row group; the
//! footer is parsed ONCE per file and shared, and only `geometry` + `tags` are
//! projected (Sweden's `ways.parquet` also carries `id`, `version` and
//! `node_refs` — 30 % of its uncompressed column bytes, decoded for nothing).
//! * **Accumulation is sharded on the TILE KEY, never per worker.** A worker-private
//! pyramid merged at the end would multiply residency by the worker count —
//! 12.21 GB × 32 = 390 GB on a 499 GB box — and force a merge of two halves of the
//! same tile. Keyed on the tile, the shards are disjoint and no tile is ever in
//! two places. See [`shard_of`].
//! * **Residency is a budget, not a function of the region.**
//! [`TileOptions::mem_budget_bytes`] caps the resident tile payload; over it, the
//! biggest tiles are pushed to a per-shard scratch file and replayed when the tile
//! is written.
//!
//! ## What the budget bounds, and what it cannot
//!
//! MEASURED on oden 2026-08-03, `sweden` at z6/9/12, region 10.5..24.5 x 55.0..69.2,
//! **28 974 tiles in every arm** (`benches/tile_pyramid_parallel`, each arm the only
//! tiling in its process):
//!
//! | arm | wall | scan | scan cores | peak RSS | payload | spill |
//! |---|---|---|---|---|---|---|
//! | serial-unbounded | 153.50 s | 75.24 s | 1.0 | 9.57 GiB | 8.85 | 0.00 |
//! | parallel-unbounded | 20.27 s | 6.35 s | 14.4 | 10.47 GiB | 8.89 | 0.00 |
//! | parallel-bounded (4 GiB) | 27.33 s | 16.98 s | 7.1 | **5.85 GiB** | 4.00 | 4.00 |
//!
//! Three terms make up that RSS, and only the first is the pyramid:
//!
//! * **payload** — what [`TileOptions::mem_budget_bytes`] bounds, held at 4.00 GiB.
//! * **bookkeeping** ([`TileStats::peak_bookkeeping_bytes`], 0.33 GiB when that table
//! was taken) — the per-tile [`PxSet`] dedup sets, the spilled-run indexes and the
//! shard tables. The budget CANNOT bound these: they are what makes a spill lossless,
//! so they are what survives one, and [`Shard::spill_down`] adds to them every time it
//! runs. They are the engine's floor, and the bench fails on a budget below it.
//! **The floor scales with the TILE COUNT, so it is the term z15 decides.** It is
//! bounded per tile by construction since `tilemem-1`: [`PX_DENSE_BYTES`] = 8 KiB,
//! the whole 65 536-pixel key space, against the 192 KiB a saturated `HashSet<u16>`
//! used to hold. See [`PxSet`].
//! * **glibc arena free list** — not live data at all, and the reason a fan-out
//! process holds more than it uses. 32 workers, one arena each, every arena grown
//! to its own high-water mark and nothing returned on `free`: 11.13 GiB of it in
//! the unbounded parallel arm against **0.01 GiB in the serial arm on the same
//! input**. `malloc_trim(0)` at the end of the scan hands it back.
//!
//! That last term is why this branch read 15.20 GiB for a 4.00 GiB budget when it was
//! first measured, and why that reading was wrong: the three arms shared one process,
//! nothing was ever trimmed, and the bounded arm was charged for the arenas the two
//! arms before it had left behind. It costs 5.85 GiB. See the bench's module header.
//!
//! ### The budget scales with the box, and z15 is why
//!
//! That table is z6/9/12, where the whole pyramid wants 8.85 GiB and a 4 GiB budget
//! costs 4 GiB of spill. z15 is a different order of magnitude, MEASURED on oden on
//! the same `sweden` extract:
//!
//! | arm | zooms | budget | spilled | write | peak RSS |
//! |---|---|---|---|---|---|
//! | `tilemem/z15-full.log` 2026-08-03 | 15 | 8 GiB | 29.41 GiB | 93.08 s @ 6.1 | 6.83 GiB |
//! | `tilemem/run-all4.log` 2026-08-03 | 6,9,12,15 | 8 GiB | 35.16 GiB | 126.07 s @ 6.0 | 7.13 GiB |
//! | `tilemem/budget-sweep.log` 2026-08-03 | 15 | **40 GiB** | **0.00 GiB** | 106.49 s @ 5.1 | **14.19 GiB** |
//! | `tilebench/z15-AFTER1.log` 2026-08-04 | 15 | 4 GiB | **115.27 GiB** | 378.51 s @ 3.6 | 5.73 GiB |
//!
//! Two things that table settles. **The payload a country wants at z15 is ~40 GiB, not
//! 4** — the 40 GiB arm is the one that spilled nothing. And **the budget is not the
//! RSS**: at a 40 GiB budget the process's true peak, `/usr/bin/time`'s
//! `Maximum resident set size`, was 14.19 GiB, because [`TileStats::peak_resident_bytes`]
//! is a SUM of per-shard high-water marks taken at independent instants and is therefore
//! an upper bound on a quantity that never all existed at once. A budget picked against
//! the payload figure is conservative by roughly 2.7x on this input, which is the
//! direction to be wrong in.
//!
//! Hence [`default_tile_mem_budget`]: a quarter of `MemAvailable`, floored at the old
//! 4 GiB constant and capped at [`MAX_TILE_MEM_BUDGET`].
//!
//! ## The pyramid is NOT byte-reproducible, and a correctness gate must know it
//!
//! MEASURED on oden 2026-08-03, two runs of the SAME binary over the same
//! `~/.korp/work/sweden` extract at z12, 12 sampled tiles of 28 281: the tile KEY SET
//! is identical (28 281 = 28 281), every sampled tile has the identical ROW COUNT, and
//! **0.140 % of rows (46 of 32 741) are different features**. Four of twelve tiles
//! differed.
//!
//! The mechanism is the sub-pixel dedup meeting the fan-out. Two nodes in the same
//! 1/256th of a tile are the same pixel, one of them is kept, and *which* one is
//! whichever of 32 scan workers reached the shard lock first. Both answers are correct
//! and neither is stable. The per-tile caps ([`TileOptions::max_tile_points`]) have the
//! same property once a tile saturates.
//!
//! So an equivalence gate — for the spatial-partition rewrite, for a network-layer
//! split, for any re-cut — must compare the **tile key set, the row counts and the tag
//! multiset**, never file bytes and never the id set. A gate written against bytes will
//! go red on a change that did nothing, which is the fastest way to teach a team to
//! ignore it. It also means a diff against the LIVE pyramid shows a residue that is not
//! a defect: 11 rows of 3 266 on a sampled z12 tile, same count, different
//! representatives.
//!
//! **A tile cannot be known complete before the scan ends, and this module does not
//! pretend otherwise.** Knowing it would need the input to arrive in an order that
//! bounds which tiles can still gain rows. It does not: measured on korp's `sweden`
//! extract 2026-08-03, every one of `ways.parquet`'s 32 row groups spans lat
//! 11°..67° and lon 0°..23° — the whole country and then some, in each group. The
//! extract has no `covering.bbox` column and has never been through
//! [`crate::spatial::spatial_pack`], so it is in OSM id order, which is temporal and
//! not spatial. The last row group can still put a way in the first tile.
//!
//! So what runs here is a **window with lossless spill**, not a stream: a tile leaves
//! memory when the budget says so, and is re-joined from scratch at write time — it
//! is never *published* early, because publishing an incomplete tile would be wrong
//! and no cheaper. Making this a true stream needs a spatially ordered input (Hilbert
//! order does visit every quadrant contiguously, so a `spatial_pack`ed extract WOULD
//! make z-quadrant completion decidable for points; ways duplicated by bbox overlap
//! would still need the bbox, not the centroid, to drive the ordering). That is a
//! change to the extract, not to the tiler.
//!
//! **A REGION's pyramid never leaves the region** ([`TileOptions::region`]). The tiler
//! used to be faithful to whatever the extract held, which sounds right and is not: a
//! region extract that leaks a handful of foreign objects publishes a pyramid scattered
//! over the whole globe, because ONE stray way is enough to create a tile. Measured on
//! korp's `sweden` extract 2026-08-02: **1 167 of 3 397 234 ways (0.034 %) lay wholly
//! outside Sweden's bbox — and none straddled it** — yet they produced **803 of the 829
//! z6 tiles (96.9 %)**, 7 846 of 8 471 at z9 and 15 281 of 39 494 at z12, `x` spanning
//! `0..63` (the entire 64-column world from lon −180°). The coarse level a whole-country
//! viewport reads was 97 % near-empty stubs. Set [`TileOptions::region`] and the tiler
//! **refuses** to write a tile whose extent lies outside those bounds, counting every
//! refusal in [`TileStats::refused_tiles`] so a leaking upstream clip is reported rather
//! than silently published as coverage.
use std::collections::HashMap;
use std::io::{Read as _, Seek as _, SeekFrom};
use std::path::{Path, PathBuf};
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
use std::sync::{Arc, Mutex};
use anyhow::Context as _;
use arrow::array::{
Array, ArrayRef, BinaryArray, Float32Array, Int64Array, RecordBatch, StringArray, StructArray,
};
use arrow::datatypes::{DataType, Field, Fields, Schema};
use parquet::arrow::arrow_reader::{
ArrowReaderMetadata, ParquetRecordBatchReaderBuilder, RowSelection, RowSelector,
};
use parquet::arrow::{ArrowWriter, ProjectionMask};
use parquet::file::properties::WriterProperties;
use crate::metadata::{BBOX_COLUMN, GEO_KEY, GeoMeta};
// The ONE spelling of an Arrow type in a recipe token (LAW 5).
use crate::shared::schema::short_type;
use crate::spatial::{down, up, wkb_bbox};
use crate::{Bounds, Clip, ConvertOptions};
/// A sane default zoom ladder for a country-sized region: z6 ≈ country overview,
/// z9 ≈ region, z12 ≈ town/street, z15 ≈ building/address. Callers pass their own
/// via [`TileOptions`].
///
/// **z15 is the step that makes the ladder cost real money.** MEASURED on oden
/// 2026-08-03 cutting `sweden` from the extract in `~/.korp/work/sweden`: the three-level
/// pyramid is 28 974 tiles / 2.8 GB, the four-level one 1 623 474 tiles / 22 GB — z15
/// alone is 1 594 500 tiles and 17.3 GB, i.e. 98.2 % of the objects and 78 % of the bytes.
/// The tiling itself stays cheap (168.85 s for all four levels); it is the UPLOAD of 1.6 M
/// small objects that dominates a re-cut end to end. Anyone adding z18 should price that
/// first: at the same fanout it is another ~50× on object count.
///
/// Changing this list changes [`TileRecipe::token`] (the `zooms=` field), so every stored
/// pyramid cut at the old ladder reads as STALE and gets re-cut — which is the intended
/// behaviour and the reason the axis lives in the recipe at all. See [`TileRecipe::zooms`].
pub const DEFAULT_TILE_ZOOMS: &[u8] = &[6, 9, 12, 15];
/// Backstop cap on points kept per tile (the sub-pixel dedup usually bites first).
pub const DEFAULT_MAX_TILE_POINTS: usize = 40_000;
/// Backstop cap on ways kept per tile.
pub const DEFAULT_MAX_TILE_WAYS: usize = 20_000;
/// **What a tile throws away when [`TileOptions::max_tile_ways`] is reached.**
///
/// # The defect this replaces (`natt-7`, "Mälaren is not in its own tile")
///
/// The cap used to be `if acc.n_ways >= max_ways { continue }` — a refusal decided by
/// ARRIVAL ORDER, i.e. by which parquet row group a worker happened to reach first.
/// MEASURED on the live `sweden` pyramid 2026-08-04, before this existed: relation
/// 1433877 (`name=Mälaren`, 1 140 km²) is a **997 630-byte** geometry in its z12 tile,
/// is in **exactly one** of the eight z9 tiles its bbox crosses — `z9/278/149`, the one
/// tile of that block NOT at the cap (59 199 rows) — and is in **none** of the z6 tiles
/// at all. Its neighbours `z9/279..282/149..151` all sit at exactly 60 000 rows and all
/// dropped it. The same feature, the same zoom, kept where there was room and refused
/// where a farmyard got there first.
///
/// The arithmetic of a "60 000-row" tile is worth spelling out because it names the cap
/// that actually binds: 60 000 = `max_tile_ways` (20 000) + `max_tile_points` (40 000).
/// `z6/35/18` holds **36 848** rows and still has no Mälaren — it is 20 000 ways plus
/// 16 848 points, i.e. AT the way cap while nowhere near the row total that made the
/// defect visible. Counting tiles at 60 000 rows undercounts the ways cap badly.
///
/// # The axis, and why it is this one
///
/// Roads and rails are already handed to the network tables ([`crate::network::TILED_OUT`]),
/// so the ways left contesting a tile are **areas and coastlines**: water, landuse,
/// buildings, boundaries. For those, extent IS importance, and the honest measure of
/// extent is the one the writer already computes to decide how much shape to keep —
/// [`tile_pixel_tol`], the ground size of one RENDERED pixel at this zoom. A feature's
/// rank is therefore its bbox span in rendered pixels, [`way_span_px`]: scale-free,
/// zoom-aware, and no new constant for the scale.
///
/// A single threshold would only move the arbitrariness, so the budgets are a **nested
/// ladder** — the same max-min idea korp's `fair_take` implements on the read side, where
/// no tile may starve another. Here no *lane* may starve a more important one:
///
/// | lane | span at this zoom | may fill up to |
/// |---|---|---|
/// | [`WayLane::Dust`] | < 1 rendered px | 40 % of the cap |
/// | [`WayLane::Small`] | 1 px … 1/32 tile | 80 % |
/// | [`WayLane::Dominant`] | ≥ 1/32 of the rendered tile | 100 % |
///
/// Because the budgets are non-decreasing in importance and are compared against the ONE
/// total `n_ways`, a dominant feature can only ever be refused by a tile already full of
/// other dominant features — never by dust. And because the top of the ladder is still
/// `max_tile_ways`, **rows per tile do not grow**: this changes what a full tile contains,
/// not how full it gets.
///
/// The 40 % floor for dust is not a guess either. On `z6/35/18` before this landed,
/// **15 221 of the 20 000 way slots (76 %)** were areas that had simplified below one
/// pixel and shipped as points — features that by the writer's own epsilon contribute
/// nothing at that zoom. They keep 8 000 slots (they are texture, not nothing) and give
/// back 4 000 that only a feature spanning ≥ 1/32 of the tile can claim.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum WayLane {
/// Below one rendered pixel at this zoom — under the very epsilon
/// [`tile_pixel_tol`] simplifies to, so it cannot draw a shape here by construction.
Dust = 0,
/// At least one rendered pixel, but under [`DOMINANT_TILE_FRACTION`] of the tile.
Small = 1,
/// Spans at least [`DOMINANT_TILE_FRACTION`] of the rendered tile — a lake, a
/// coastline run, a municipal boundary. The reason anyone opens a country view.
Dominant = 2,
}
/// The fraction of a rendered tile's width a way's bbox must span to be
/// [`WayLane::Dominant`]: **1/32**, i.e. 64 px of a 2048-px tile.
///
/// At z6 one tile is 5.625° wide, so this is ≈ 0.176° ≈ 12 km of ground; at z9, ≈ 2.4 km.
/// Chosen so the lane holds the features a country view exists to show and not many more
/// — the run REPORTS its occupancy ([`ZoomTileStats::way_refused`]) rather than assuming
/// it, because a reserve that overflows is a positional cap wearing a hat.
pub const DOMINANT_TILE_FRACTION: u32 = 32;
/// Fraction of [`TileOptions::max_tile_ways`] each [`WayLane`] may fill, indexed by lane.
/// Non-decreasing by construction — the guard `the_lane_ladder_never_starves_the_lane_above`
/// asserts it, because a ladder that inverted would be the old defect with more code.
pub const WAY_LANE_KEEP_PERCENT: [usize; 3] = [40, 80, 100];
/// The lane budgets in ROWS for a given `max_ways` — one writer (LAW 5), so the guard
/// and `absorb` cannot disagree about what 40 % of a cap is.
#[inline]
pub fn way_lane_budgets(max_ways: usize) -> [usize; 3] {
let mut b = [0usize; 3];
for (i, pct) in WAY_LANE_KEEP_PERCENT.iter().enumerate() {
b[i] = max_ways.saturating_mul(*pct) / 100;
}
b
}
/// **A way's bbox span in RENDERED tile pixels at zoom `z`** — the rank the per-tile cap
/// sorts on. `max` of the two axes, so a long thin coastline ranks by its length and not
/// by an area it does not enclose.
///
/// Denominated in [`tile_pixel_tol`] deliberately: that is already the unit in which this
/// writer decides what is too small to keep, so "smaller than one pixel" means the same
/// thing to the simplifier and to the cap. Saturating at `u32::MAX` — a country-spanning
/// way is off the top of every scale that matters here.
#[inline]
pub fn way_span_px(minx: f64, miny: f64, maxx: f64, maxy: f64, z: u8, raster_px: u32) -> u32 {
let tol = tile_pixel_tol(z, raster_px);
if !(tol > 0.0) {
return u32::MAX;
}
let span = (maxx - minx).abs().max((maxy - miny).abs()) / tol;
if !span.is_finite() || span >= f64::from(u32::MAX) {
u32::MAX
} else {
span as u32
}
}
/// The [`WayLane`] of a rank produced by [`way_span_px`], at a given render width.
#[inline]
pub fn way_lane(span_px: u32, raster_px: u32) -> WayLane {
if span_px >= raster_px / DOMINANT_TILE_FRACTION.max(1) {
WayLane::Dominant
} else if span_px >= 1 {
WayLane::Small
} else {
WayLane::Dust
}
}
/// Safety cap on how many tiles one viewport query may fan out to (a reader helper —
/// a request whose bbox+zoom would touch more than this is a whole-region scan, not
/// a viewport). See [`covering_tiles`].
pub const MAX_QUERY_TILES: usize = 512;
// ── slippy Web-Mercator tile math (pure, testable, the tile-scheme source of truth) ─
/// Fractional slippy tile X of a longitude at zoom `z`: `(lon+180)/360 · 2^z`.
#[inline]
pub fn lon_to_tile_x(lon: f64, z: u8) -> f64 {
(lon + 180.0) / 360.0 * f64::from(1u32 << z)
}
/// Fractional slippy tile Y of a latitude at zoom `z` (standard Web-Mercator;
/// latitude clamped to the ±85.0511° Mercator limit).
#[inline]
pub fn lat_to_tile_y(lat: f64, z: u8) -> f64 {
let lat_rad = lat.clamp(-85.051_128_78, 85.051_128_78).to_radians();
(1.0 - (lat_rad.tan() + 1.0 / lat_rad.cos()).ln() / std::f64::consts::PI) / 2.0
* f64::from(1u32 << z)
}
/// The integer slippy tile `(x, y)` a `(lon, lat)` point falls in at zoom `z`.
#[inline]
pub fn lonlat_to_tile(lon: f64, lat: f64, z: u8) -> (u32, u32) {
let n = 1u32 << z;
let hi = f64::from(n - 1);
let x = lon_to_tile_x(lon, z).floor().clamp(0.0, hi) as u32;
let y = lat_to_tile_y(lat, z).floor().clamp(0.0, hi) as u32;
(x, y)
}
/// The longitude of fractional slippy tile X at zoom `z` — the inverse of
/// [`lon_to_tile_x`].
#[inline]
pub fn tile_x_to_lon(x: f64, z: u8) -> f64 {
x / f64::from(1u32 << z) * 360.0 - 180.0
}
/// The latitude of fractional slippy tile Y at zoom `z` — the inverse of
/// [`lat_to_tile_y`] (`atan(sinh(π − 2πy/2^z))`).
///
/// **Public because a caller inverting a viewport's pixel height into a latitude span
/// must use THIS, not a flat `h·180/scale`.** Web Mercator's degrees of latitude per
/// pixel depends on the latitude; treating it as constant is right only at φ=60° and
/// is 11.5 % short at Malmö / 33 % long at Kiruna. korp's `viewport_bbox` had that
/// copy, and then handed the box to [`covering_tiles`] here, which uses the real
/// projection — so the reader culled to a box the pane did not agree with.
#[inline]
pub fn tile_y_to_lat(y: f64, z: u8) -> f64 {
let n = std::f64::consts::PI - 2.0 * std::f64::consts::PI * y / f64::from(1u32 << z);
n.sinh().atan().to_degrees()
}
/// The WGS84 lon/lat [`Bounds`] of slippy tile `(z, x, y)`. Y grows downward, so the
/// tile's top edge (`y`) is the MAXIMUM latitude and its bottom edge (`y+1`) the min.
pub fn tile_bounds(z: u8, x: u32, y: u32) -> Bounds {
Bounds::new(
tile_x_to_lon(f64::from(x), z),
tile_y_to_lat(f64::from(y + 1), z),
tile_x_to_lon(f64::from(x + 1), z),
tile_y_to_lat(f64::from(y), z),
)
}
// **There is no lod→zoom mapping in this crate, and that is the point** (`mapwire-9`).
//
// `lod_to_tile_zoom` used to live here: a NEAREST-rung search that reached for a rung
// FINER than the camera whenever the camera was more than halfway to it. It was removed
// on 2026-08-25 with no caller anywhere in the fleet — the only mention left was a
// korp test that asserted a *replica* of this body still matched this body, which is a
// guard that cannot fail for any reason a reader cares about and was the sole thing
// keeping the function alive.
//
// The serving rule is FLOOR — the nearest tiled rung AT OR BELOW the lod — and it lives
// in `facett_map::layer::lod_step`, the SAME function the painter picks its LOD tier
// with, so the level served and the tier drawn cannot be two expressions that merely
// agree sometimes. osm-katana is the DATA PRODUCER and does not depend on facett, so it
// must not own a second copy of that rule (LAW 5): there is no floor variant here on
// purpose, and there is no longer a nearest variant either. The measured cost of the
// nearest rule is written down where the rule that replaced it is asserted —
// `korp/tests/lod_one_threshold.rs`.
/// **The inclusive slippy tile range `(x0, x1, y0, y1)` at zoom `z` that [`Bounds`]
/// overlaps** — the ONE place a lon/lat box becomes a tile box.
///
/// Three callers need exactly this arithmetic and used to each own a copy:
/// [`covering_tiles`] (the reader's viewport fan), [`way_tiles`] (the writer's
/// duplication fan) and the region refusal in [`tile_region`]. LAW 5 — one writer, so
/// the reader's idea of "which tiles cover this box" can never drift from the writer's.
#[inline]
pub fn tile_range(b: &Bounds, z: u8) -> (u32, u32, u32, u32) {
let n = 1u32 << z;
let hi = f64::from(n - 1);
let xa = lon_to_tile_x(b.min_lon, z).floor().clamp(0.0, hi) as u32;
let xb = lon_to_tile_x(b.max_lon, z).floor().clamp(0.0, hi) as u32;
// Larger latitude ⇒ smaller Y, so max_lat gives the top (min Y) row.
let ya = lat_to_tile_y(b.max_lat, z).floor().clamp(0.0, hi) as u32;
let yb = lat_to_tile_y(b.min_lat, z).floor().clamp(0.0, hi) as u32;
(xa.min(xb), xa.max(xb), ya.min(yb), ya.max(yb))
}
/// Every slippy tile `(x, y)` at zoom `z` that the query [`Bounds`] overlaps, clamped
/// to [`MAX_QUERY_TILES`]; the `bool` is `true` when the list was clamped.
pub fn covering_tiles(q: &Bounds, z: u8) -> (Vec<(u32, u32)>, bool) {
let (x0, x1, y0, y1) = tile_range(q, z);
let mut out = Vec::new();
let mut clamped = false;
'outer: for x in x0..=x1 {
for y in y0..=y1 {
if out.len() >= MAX_QUERY_TILES {
clamped = true;
break 'outer;
}
out.push((x, y));
}
}
(out, clamped)
}
/// The relative key of tile `(z, x, y)`: `tiles/z{Z}/{X}/{Y}.parquet`.
pub fn tile_key(z: u8, x: u32, y: u32) -> String {
format!("tiles/z{z}/{x}/{y}.parquet")
}
/// The relative key of the tile manifest: `tiles/manifest.json`.
pub fn manifest_key() -> String {
String::from("tiles/manifest.json")
}
/// The manifest key carrying the [`TileRecipe`] that cut the pyramid.
pub const MANIFEST_RECIPE_KEY: &str = "tile_recipe";
/// The parquet key-value-metadata key carrying the [`TileRecipe`] **in every tile**.
///
/// The manifest's copy is a CLAIM (one small document, written once, at the end); this
/// one is EVIDENCE — it rides in the footer of the object a reader actually decodes, so
/// a hand-edited manifest, a half-finished re-cut or a pyramid assembled out of two runs
/// cannot make an old tile look current.
pub const TILE_RECIPE_META_KEY: &str = "osm-katana:tile-recipe";
/// Render the tile-manifest JSON document (the reader GETs this to learn WHETHER an
/// asset is tiled, at which zooms, and **by which recipe**).
///
/// `recipe` is [`TileRecipe::token`] of the run that produced these tiles — see
/// [`TileRecipe`] for why the manifest carries it at all.
/// The manifest key naming the tile the run wrote LAST. See
/// [`TileStats::deepest_tile`] and [`manifest_deepest_tile`].
pub const MANIFEST_DEEPEST_TILE_KEY: &str = "deepest_tile";
/// One JSON string literal — quotes, backslashes and control characters escaped.
///
/// # Why this exists rather than a `format!("\"{s}\"")`
///
/// [`manifest_json`] used to interpolate `region`, `recipe` and `deepest_tile` RAW into
/// its document. Every one of the three is caller data: `region` is
/// `--region-name`/the collector's region key (an operator string), `deepest_tile` is a
/// path, and `recipe` is a token whose axes are assembled from tag selectors. One `"` in
/// any of them and the manifest is not JSON at all — at which point
/// [`manifest_recipe`], [`manifest_zooms`] and [`manifest_deepest_tile`] all return
/// `None`, and `None` is the *load-bearing* answer those three document: **"cut before
/// this key existed ⇒ stale"**. So a quote in a region name does not produce a parse
/// error someone notices; it produces a pyramid that is re-cut on every pass, silently,
/// and a manifest that never reads current no matter how fresh the tiles are.
///
/// `serde_json::Value::String(_).to_string()` is the escaper the parsers on the other
/// side (`serde_json::from_str`) are the inverse of — one codec, not a hand-rolled
/// second opinion (LAW 5). It is infallible for a `String`, so there is no error arm to
/// swallow.
fn json_str(s: &str) -> String {
serde_json::Value::String(s.to_string()).to_string()
}
pub fn manifest_json(
region: &str,
zooms: &[u8],
recipe: &str,
deepest_tile: Option<&str>,
) -> String {
let z = zooms
.iter()
.map(|z| z.to_string())
.collect::<Vec<_>>()
.join(",");
// Omitted rather than rendered `null` when there is none, so `manifest_deepest_tile`
// has one absent case and not two.
let deepest = match deepest_tile {
Some(t) => format!(
r#","{MANIFEST_DEEPEST_TILE_KEY}":{}"#,
json_str(t)
),
None => String::new(),
};
let region = json_str(region);
let recipe = json_str(recipe);
format!(
r#"{{"region":{region},"zooms":[{z}],"format":"geoparquet-1.1-covering-tiles","{MANIFEST_RECIPE_KEY}":{recipe}{deepest}}}"#
)
}
/// Parse the [`TileStats::deepest_tile`] key out of a manifest document.
///
/// **`None` means "this manifest predates the deepest-tile key"**, not "the pyramid is
/// fine". A reader that wants to know whether a pyramid is WHOLE and gets `None` here
/// has learned that it cannot cheaply find out — which is the honest answer, and the
/// one the coarsest-zoom probe used to give as `Current`.
pub fn manifest_deepest_tile(json: &str) -> Option<String> {
let v: serde_json::Value = serde_json::from_str(json).ok()?;
let s = v.get(MANIFEST_DEEPEST_TILE_KEY)?.as_str()?;
(!s.is_empty()).then(|| s.to_string())
}
/// Parse the tiled `zooms` out of a manifest document; `None` ⇒ absent/unparsable/
/// empty (⇒ not tiled).
pub fn manifest_zooms(json: &str) -> Option<Vec<u8>> {
let v: serde_json::Value = serde_json::from_str(json).ok()?;
let arr = v.get("zooms")?.as_array()?;
let zooms: Vec<u8> = arr
.iter()
.filter_map(|z| z.as_u64().and_then(|z| u8::try_from(z).ok()))
.collect();
if zooms.is_empty() { None } else { Some(zooms) }
}
/// Parse the [`TileRecipe::token`] out of a manifest document.
///
/// **`None` is the load-bearing answer, not an error case.** Every pyramid cut before
/// this key existed parses to `None`, and a reader that wants current tiles must treat
/// that as *stale*, never as *unknown-so-probably-fine*: the 28 974-tile `sweden`
/// pyramid live on oden on 2026-08-03 was cut with no `id` column and a 256-px
/// tolerance, and its manifest is byte-identical to the one a current run would write.
pub fn manifest_recipe(json: &str) -> Option<String> {
let v: serde_json::Value = serde_json::from_str(json).ok()?;
let s = v.get(MANIFEST_RECIPE_KEY)?.as_str()?;
(!s.is_empty()).then(|| s.to_string())
}
// ── WKB codec (tile geometry payload) ───────────────────────────────────────────
/// The tile writer's WKB codec is [`crate::shared::geometry`]'s — ONE encoder and
/// ONE decoder shared with the relation assembler (LAW 5), so a MultiPolygon that
/// `relgeom` assembled and one the tiler re-encodes after simplification cannot
/// disagree about their bytes.
///
/// The decoder replaced here was RING-FLATTENING: it concatenated every ring of a
/// Polygon into one vertex list and answered WKB type 6 (MultiPolygon) with an
/// EMPTY list. See `shared::geometry`'s module comment for what that cost.
use crate::shared::geometry::{
WkbShape, decode_wkb, encode_wkb_line_into, encode_wkb_multipolygon,
encode_wkb_multipolygon_into, push_wkb_point,
};
/// The allocating WKB encoders. Production code in this module writes into a buffer it
/// already owns ([`TileRows`], `katana-9`), so these two are only reached by the tests
/// that need owned bytes — importing them unconditionally warned on every release build.
#[cfg(test)]
use crate::shared::geometry::{encode_wkb_line, encode_wkb_point};
/// **Per-RING Douglas-Peucker for an area.** Simplifies every ring on its own,
/// keeps it explicitly closed, and drops the ones that no longer bound anything.
///
/// # Why not just run DP over the flat vertex list
///
/// Because that is what the tiler used to do, and it is wrong twice. A polygon's
/// rings concatenated into one run put a chord between the outer ring's last
/// vertex and the first hole's first vertex; DP then measures deviation from THAT
/// chord, which is not an edge of the geometry, and keeps or drops real vertices
/// on the strength of it. And the result was re-encoded as a `LineString`, so the
/// hole stopped being a hole at all.
///
/// A ring needs 4 vertices to enclose area once closed (3 corners + the repeat).
/// One that simplifies below that is genuinely sub-pixel at this zoom and is
/// dropped — a hole first, and the whole polygon if its outer ring goes. Holes
/// survive independently of their outer ring: a lake that is still 40 px across
/// keeps an island that is still 4 px across.
pub(crate) fn simplify_polys(
polys: &[(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)],
eps: f64,
) -> Vec<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)> {
let mut scratch = DpScratch::default();
simplify_polys_into(polys, eps, &mut scratch);
fold_selfx_books(scratch.books);
scratch.polys.as_slice().to_vec()
}
/// **The retry loop's books** (row 24). One per worker, inside its [`DpScratch`], folded
/// once at the end of the worker's unit — never an atomic in the ring loop.
///
/// `shipped_source` is the count the row asked for: how often the pack gave up on
/// simplifying a ring and shipped its SOURCE vertices instead. A pyramid or a packed
/// column where this is large is one whose rungs are not smaller than the base — the
/// number to read before trusting a rung's byte size.
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct SelfxBooks {
/// Halvings of epsilon taken because the previous pass crossed itself.
pub retries: u64,
/// Rings shipped with their SOURCE vertices — for either reason below.
pub shipped_source: u64,
/// Of `shipped_source`: rings whose simplification was too big to check within the
/// pack's budget ([`crate::verify::SELFX_PACK_MAX_SEGS`]), shipped unsimplified
/// rather than unchecked — a bowtie the census cannot see is still a bowtie on the map.
pub unchecked: u64,
/// **Orientation-pair tests the crossing sweep actually charged**, summed over every
/// ring and every retry.
///
/// This is the number row 24 is ABOUT, and it is here because a wall clock is not.
/// The defect was an exact O(n²) walk with no cap — ~1.25 × 10⁹ pairs for one
/// 50 000-vertex ring, per retry, per rung, per pack. A guard that says "and now it
/// takes under 50 ms" is a statement about the box; this is a statement about the
/// algorithm, it is identical on every run, and it cannot be moved by another lane's
/// build. MEASURED on oden at load 120/32 the same fixture's WALL TIME swung
/// 193.7 ms → 402.3 ms (2.08×) while this number did not move at all.
///
/// Counted per worker in its own scratch and folded once per unit, exactly like the
/// three above — never a `fetch_add` in the ring loop.
pub pairs: u64,
}
impl SelfxBooks {
pub(crate) fn add(&mut self, o: SelfxBooks) {
self.retries += o.retries;
self.shipped_source += o.shipped_source;
self.unchecked += o.unchecked;
self.pairs += o.pairs;
}
}
/// **The process-wide fold of every worker's [`SelfxBooks`]** — three counters, and the
/// ONE place the pack's ring-safety numbers are reported from.
///
/// Written once per worker UNIT, never per ring: a `fetch_add` inside the retry loop is
/// a cache line shared by 32 threads in the hottest loop of the pack, which is the exact
/// shape of contention `tilemem-2` and the gatling fan-out exist to avoid. The worker
/// counts into its own scratch and folds here when its unit is done.
static SELFX_RETRIES: AtomicU64 = AtomicU64::new(0);
static SELFX_SHIPPED_SOURCE: AtomicU64 = AtomicU64::new(0);
static SELFX_UNCHECKED: AtomicU64 = AtomicU64::new(0);
static SELFX_PAIRS: AtomicU64 = AtomicU64::new(0);
/// Fold one worker's books into the process totals. Call ONCE per unit.
pub(crate) fn fold_selfx_books(b: SelfxBooks) {
if b == SelfxBooks::default() {
return;
}
SELFX_RETRIES.fetch_add(b.retries, Ordering::Relaxed);
SELFX_SHIPPED_SOURCE.fetch_add(b.shipped_source, Ordering::Relaxed);
SELFX_UNCHECKED.fetch_add(b.unchecked, Ordering::Relaxed);
SELFX_PAIRS.fetch_add(b.pairs, Ordering::Relaxed);
}
/// **How often the ring-safe simplifier gave up**, since [`reset_selfx_books`] (or since
/// the process started).
///
/// `shipped_source` is the number the row asks for: rings the pack could not simplify
/// without producing a bowtie, and shipped at full source precision instead. It is the
/// number to read before trusting a rung column's byte size — a rung that is not much
/// smaller than its base is one where this ran high. `unchecked` is the part of it the
/// bounded crossing test could not answer at all (over the segment cap, or out of pair
/// budget); those rings are shipped unsimplified rather than unchecked.
#[must_use]
pub fn selfx_books() -> SelfxBooks {
SelfxBooks {
retries: SELFX_RETRIES.load(Ordering::Relaxed),
shipped_source: SELFX_SHIPPED_SOURCE.load(Ordering::Relaxed),
unchecked: SELFX_UNCHECKED.load(Ordering::Relaxed),
pairs: SELFX_PAIRS.load(Ordering::Relaxed),
}
}
/// Zero the counters [`selfx_books`] reads — so one pack's numbers are one pack's.
pub fn reset_selfx_books() {
SELFX_RETRIES.store(0, Ordering::Relaxed);
SELFX_SHIPPED_SOURCE.store(0, Ordering::Relaxed);
SELFX_UNCHECKED.store(0, Ordering::Relaxed);
SELFX_PAIRS.store(0, Ordering::Relaxed);
}
/// **The simplified polygons of the last [`simplify_polys_into`] call**, in ring buffers
/// that outlive the call and are reused by the next one.
///
/// A `Vec<(Vec, Vec<Vec>)>` is the encoder's input shape, so that is what is held — but
/// `clear` does not drop a single inner `Vec`: outer rings are cleared in place and hole
/// rings go to `spare`, where the next polygon that needs a hole takes them back. After
/// the first call that reached this pool's high-water mark, a call allocates nothing.
#[derive(Default)]
pub(crate) struct PolyPool {
slots: Vec<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)>,
len: usize,
spare: Vec<Vec<(f64, f64)>>,
}
impl PolyPool {
/// The polygons the last call kept, in input order.
pub(crate) fn as_slice(&self) -> &[(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)] {
&self.slots[..self.len]
}
pub(crate) fn is_empty(&self) -> bool {
self.len == 0
}
fn clear(&mut self) {
let Self { slots, len, spare } = self;
for (outer, holes) in &mut slots[..*len] {
outer.clear();
spare.extend(holes.drain(..).map(|mut h| {
h.clear();
h
}));
}
*len = 0;
}
}
/// [`simplify_polys`] into the caller's [`DpScratch`] — the ONE implementation (LAW 5);
/// the allocating form above is a three-line wrapper over it. The result is read off
/// `scratch.polys` ([`PolyPool::as_slice`]) and the retry loop's counts land in
/// `scratch.books`.
///
/// Why into a scratch rather than out to a `Vec` (row 24): the tile scan and the pack
/// call this once per area per rung, and the retry loop inside used to allocate a fresh
/// DP scratch, a fresh output ring and — on giving up — a clone of the source ring, per
/// attempt. Every buffer here is the worker's, reused across attempts, rings, and rows.
pub(crate) fn simplify_polys_into(
polys: &[(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)],
eps: f64,
scratch: &mut DpScratch,
) {
let DpScratch { dp, selfx, polys: pool, books } = scratch;
pool.clear();
let PolyPool { slots, len, spare } = pool;
for (outer, holes) in polys {
if *len == slots.len() {
slots.push((Vec::new(), Vec::new()));
}
let (o, hs) = &mut slots[*len];
if !simplify_ring_safe(outer, eps, dp, selfx, books, o) {
continue;
}
for h in holes {
let mut v = spare.pop().unwrap_or_default();
if simplify_ring_safe(h, eps, dp, selfx, books, &mut v) {
hs.push(v);
} else {
spare.push(v);
}
}
*len += 1;
}
}
/// Close `ring` in place if its first and last vertex differ — a WKB linear ring must
/// repeat its first vertex.
fn close_ring(ring: &mut Vec<(f64, f64)>) {
if ring.len() > 1 && ring.first() != ring.last() {
if let Some(&f) = ring.first() {
ring.push(f);
}
}
}
/// **RING-SAFE DP for one ring, into `out`.** `true` when `out` holds a ring worth
/// keeping (≥ 4 vertices, closed); `false` when the ring is sub-pixel at `eps` and the
/// caller must drop it.
///
/// (The sea-wedge defect's second source, 2026-09-02.) Plain DP on a wiggly shore can
/// drop exactly the vertices that kept two arms of the shoreline apart, and the
/// simplified ring then CROSSES ITSELF — the census counted 11 510 such rings in the
/// live relations `geometry_z9` column, and every one of them tessellates as a bowtie
/// wedge on the map. So a crossing result is retried at half the epsilon, up to four
/// times (each halving roughly doubles the kept detail), and a ring that still crosses
/// at eps/16 ships its SOURCE vertices: a few unsimplified rings cost bytes; a wedge
/// costs the map. The crossing test is the census's own (LAW 5 — one writer).
///
/// **The bound (row 24).** A z12 Vänern ring is tens of thousands of vertices, and the
/// check used to be exact O(n²) with no bound — one adversarial ring could hold a
/// worker for seconds, per attempt, per rung. It is now
/// [`crate::verify::ring_self_intersects_bounded`]: an x-interval sweep with a segment
/// cap and a pair-test budget, which answers `Unknown` rather than overrunning. An
/// `Unknown` ring is not checked, so it is not shipped either — the source ring goes
/// instead, counted in [`SelfxBooks::unchecked`] — because an unchecked simplified ring
/// is a bowtie nobody can see, while the source ring is what the base column serves.
fn simplify_ring_safe(
r: &[(f64, f64)],
eps: f64,
dp: &mut DpKernel,
selfx: &mut crate::verify::SelfxScratch,
books: &mut SelfxBooks,
out: &mut Vec<(f64, f64)>,
) -> bool {
use crate::verify::SelfxVerdict;
let mut e = eps;
for attempt in 0..5 {
// Straight into the caller's buffers: the kernel's, and the ring the caller will
// read. No allocation anywhere in this loop after the first pass over a scratch.
dp_kernel(r, e, dp, out);
// DP preserves the first and last vertex, so a ring that came in closed comes
// out closed — but a source ring that was not explicitly closed must be closed
// here or the WKB is not a valid linear ring.
close_ring(out);
if out.len() < 4 {
return false;
}
let (verdict, pairs) = crate::verify::ring_self_intersects_bounded(out, selfx);
books.pairs += pairs as u64;
match verdict {
SelfxVerdict::Clean => return true,
SelfxVerdict::Unknown => {
// Over the segment cap, or the pair budget ran out on a shape the sweep
// could not settle. Either way this ring was NOT checked, so it is not
// shipped: halving the epsilon would only hand the next pass the same
// unanswerable question.
books.unchecked += 1;
break;
}
SelfxVerdict::Crosses => {}
}
if attempt == 4 {
break;
}
books.retries += 1;
e /= 2.0;
}
// Still crossing at eps/16, or too big to check: the shape is adversarial at this
// scale — ship the source ring, closed, rather than any crossing simplification.
books.shipped_source += 1;
out.clear();
out.extend_from_slice(r);
close_ring(out);
out.len() >= 4
}
#[cfg(test)]
mod ring_safe_dp_tests {
use super::simplify_polys;
use crate::shared::generalise::generalisation_eps;
use crate::verify::ring_self_intersects;
/// **A simplified ring must not cross itself** — the wedge face of the v2.1 map
/// defect, at its SECOND source. The zoom sweep's oracle A still found straight
/// diagonal water wedges at stockholm z11 AFTER korp's flat-decode fix, and the
/// geometry-quality census names why: 11 510 of the relations `geometry_z9`
/// rings self-intersect — plain Douglas–Peucker on a wiggly shore drops the
/// vertices that kept two arms of the shoreline apart, and the tessellator then
/// fills the bowtie as a wedge.
///
/// The fixture is REAL: relation 6208486's shore ring (72 vertices) off the live
/// Sweden cut, whose z9 DP output (11 vertices) crosses itself — extracted
/// 2026-09-02, not synthesised. SEEN RED on plain DP before the retry landed.
#[test]
fn a_simplified_ring_never_crosses_itself() {
let shore: Vec<(f64, f64)> = vec![(12.6251364, 56.127182), (12.6249933, 56.1274223), (12.624753, 56.1276093), (12.6246948, 56.1276474), (12.62465, 56.1277199), (12.6246338, 56.1278915), (12.6246414, 56.1279984), (12.6245689, 56.1280174), (12.6245127, 56.1280136), (12.6244593, 56.1279678), (12.6243916, 56.127903), (12.6241989, 56.1278534), (12.6239948, 56.1278648), (12.6238718, 56.1278992), (12.6238184, 56.1279221), (12.6237698, 56.1279678), (12.6237593, 56.1280365), (12.6237755, 56.1281967), (12.6237755, 56.1282959), (12.623724, 56.1284103), (12.6236324, 56.128479), (12.6234446, 56.1285362), (12.6229115, 56.1285362), (12.6224241, 56.1286011), (12.6219435, 56.1286392), (12.6212893, 56.1287308), (12.6211252, 56.1287613), (12.6210012, 56.1288452), (12.6203451, 56.1292229), (12.6203766, 56.1299858), (12.6198893, 56.1302452), (12.6189117, 56.1303864), (12.6188459, 56.1303749), (12.6187544, 56.1302643), (12.6187115, 56.1301651), (12.6187057, 56.1300621), (12.6187887, 56.1301384), (12.6188459, 56.1301308), (12.6189013, 56.1301041), (12.620429, 56.1289291), (12.6204996, 56.1288719), (12.620595, 56.1288261), (12.6207476, 56.1287689), (12.6209793, 56.1287155), (12.6214828, 56.1286545), (12.6226549, 56.1285248), (12.6230574, 56.1285057), (12.6233501, 56.1284943), (12.6234598, 56.1284676), (12.6235533, 56.1284218), (12.6236343, 56.1283531), (12.6236744, 56.1282616), (12.6236801, 56.1280975), (12.6236877, 56.1279793), (12.6237154, 56.1279373), (12.6237631, 56.1278915), (12.6238565, 56.1278534), (12.6239777, 56.1278343), (12.6242332, 56.1278152), (12.6243715, 56.1277885), (12.6244717, 56.1277428), (12.6246538, 56.1275826), (12.6248417, 56.1273918), (12.6250563, 56.127079), (12.6251469, 56.1268921), (12.6251688, 56.1267586), (12.6251612, 56.1266823), (12.6251259, 56.1266365), (12.6249723, 56.1265678), (12.6252127, 56.1266365), (12.6253538, 56.126667), (12.6251364, 56.127182)];
let eps = generalisation_eps(9);
// The precondition that makes the assertion meaningful: plain DP at this eps
// really does produce a crossing on this ring (the red, pinned as an arm so
// a future DP change cannot silently make this test vacuous).
let plain = super::douglas_peucker(&shore, eps);
assert!(
ring_self_intersects(&plain),
"the fixture stopped reproducing the crossing under plain DP — find a new \
ring or this guard proves nothing (got {} vertices)",
plain.len(),
);
let out = simplify_polys(&[(shore.clone(), Vec::new())], eps);
assert_eq!(out.len(), 1, "the ring survives simplification");
assert!(
!ring_self_intersects(&out[0].0),
"simplify_polys must never emit a self-crossing ring — the tessellator \
fills the bowtie as the sea-wedge defect: {:?}",
out[0].0,
);
// And it is still a simplification, not a give-up-everything fallback for
// every ring: the output must not exceed the source.
assert!(out[0].0.len() <= shore.len());
}
}
/// **Row 24 — the uncapped O(n²) crossing test at pack, and the allocations around it.**
///
/// | test | the defect it is red for |
/// |---|---|
/// | [`a_50k_vertex_ring_packs_in_under_50_ms`] | exact O(n²) with no cap: 1.25 G pair tests on ONE z12 Vänern ring, per retry, per rung |
/// | [`the_retry_loop_allocates_nothing_after_warm_up`] | a fresh `douglas_peucker` `Vec` per attempt, a fresh output ring per ring, a `clone` of the source on give-up |
/// | [`a_ring_that_crosses_at_every_tolerance_ships_its_source`] | (guard) the give-up path must ship the SOURCE ring and COUNT it |
/// | [`a_ring_over_the_segment_cap_ships_its_source_unchecked`] | a capped test that silently PASSES the rings it did not check |
///
/// Run: `cargo test -p osm-katana --lib row24 -- --nocapture`
#[cfg(test)]
mod row24_selfx_budget_tests {
use super::{DpScratch, SelfxBooks, simplify_polys_into};
use crate::shared::generalise::generalisation_eps;
use crate::verify::{SELFX_PACK_MAX_SEGS, ring_self_intersects};
/// **A 50 000-vertex ring the simplifier must KEEP.** A star-shaped ripple
/// `r(θ) = r0 + amp·sin(mθ)` at four samples per period: every third vertex sits
/// `amp` off the chord between its neighbours, and `amp` is far over the rung's
/// epsilon, so Douglas–Peucker keeps essentially all of it — which is the point.
/// The simplified ring is then ~50 000 segments and the crossing test is what the
/// row is about.
///
/// Star-shaped ⇒ simple: no two segments cross, so the test cannot exit early and
/// pays the FULL quadratic. That is the shape of a real big shore ring, and the
/// worst case for the old code.
fn rippled_ring(n: usize, cx: f64, cy: f64, r0: f64, amp: f64, m: f64) -> Vec<(f64, f64)> {
let mut v = Vec::with_capacity(n + 1);
for i in 0..n {
#[allow(clippy::cast_precision_loss)]
let t = (i as f64) / (n as f64) * std::f64::consts::TAU;
let r = amp.mul_add((m * t).sin(), r0);
v.push((r.mul_add(t.cos(), cx), r.mul_add(t.sin(), cy)));
}
v.push(v[0]);
v
}
/// The z9 shore ring of `a_simplified_ring_never_crosses_itself`, whose plain-DP
/// output crosses itself — the forced retry in the timing fixture.
fn shore() -> Vec<(f64, f64)> {
vec![(12.6251364, 56.127182), (12.6249933, 56.1274223), (12.624753, 56.1276093), (12.6246948, 56.1276474), (12.62465, 56.1277199), (12.6246338, 56.1278915), (12.6246414, 56.1279984), (12.6245689, 56.1280174), (12.6245127, 56.1280136), (12.6244593, 56.1279678), (12.6243916, 56.127903), (12.6241989, 56.1278534), (12.6239948, 56.1278648), (12.6238718, 56.1278992), (12.6238184, 56.1279221), (12.6237698, 56.1279678), (12.6237593, 56.1280365), (12.6237755, 56.1281967), (12.6237755, 56.1282959), (12.623724, 56.1284103), (12.6236324, 56.128479), (12.6234446, 56.1285362), (12.6229115, 56.1285362), (12.6224241, 56.1286011), (12.6219435, 56.1286392), (12.6212893, 56.1287308), (12.6211252, 56.1287613), (12.6210012, 56.1288452), (12.6203451, 56.1292229), (12.6203766, 56.1299858), (12.6198893, 56.1302452), (12.6189117, 56.1303864), (12.6188459, 56.1303749), (12.6187544, 56.1302643), (12.6187115, 56.1301651), (12.6187057, 56.1300621), (12.6187887, 56.1301384), (12.6188459, 56.1301308), (12.6189013, 56.1301041), (12.620429, 56.1289291), (12.6204996, 56.1288719), (12.620595, 56.1288261), (12.6207476, 56.1287689), (12.6209793, 56.1287155), (12.6214828, 56.1286545), (12.6226549, 56.1285248), (12.6230574, 56.1285057), (12.6233501, 56.1284943), (12.6234598, 56.1284676), (12.6235533, 56.1284218), (12.6236343, 56.1283531), (12.6236744, 56.1282616), (12.6236801, 56.1280975), (12.6236877, 56.1279793), (12.6237154, 56.1279373), (12.6237631, 56.1278915), (12.6238565, 56.1278534), (12.6239777, 56.1278343), (12.6242332, 56.1278152), (12.6243715, 56.1277885), (12.6244717, 56.1277428), (12.6246538, 56.1275826), (12.6248417, 56.1273918), (12.6250563, 56.127079), (12.6251469, 56.1268921), (12.6251688, 56.1267586), (12.6251612, 56.1266823), (12.6251259, 56.1266365), (12.6249723, 56.1265678), (12.6252127, 56.1266365), (12.6253538, 56.126667), (12.6251364, 56.127182)]
}
/// One z12 Vänern-sized ring plus four rings whose DP output crosses (so the retry
/// ladder really runs) — the pack's unit of work for this row.
fn timing_polys() -> Vec<(Vec<(f64, f64)>, Vec<Vec<(f64, f64)>>)> {
let big = rippled_ring(50_000, 13.2, 58.9, 0.5, 1.0e-3, 12_500.0);
assert_eq!(big.len(), 50_001, "50 000 distinct vertices, closed");
let mut polys = vec![(big, Vec::new())];
for _ in 0..4 {
polys.push((shore(), Vec::new()));
}
polys
}
/// **The bound this test holds the pack to — a PAIR-TEST CEILING, not a clock.**
///
/// # The clock was a flake, and it was measured being one
///
/// This guard asserted wall time: 50 ms under `--release`, 700 ms under
/// `debug_assertions` (50 ms at the ~14× the unoptimised build costs). It was
/// reported flaking on t14s at **55 ms against 45.7 ms solo** in a fully parallel
/// test run, and REPRODUCED here on oden: six back-to-back full-suite runs at box
/// load 120–131 on 32 cores gave **193.7 · 292.5 · 402.3 · 311.6 · 232.6 · 301.5 ms**
/// for byte-identical code — a **2.08× spread**. The release bound had 9 % of
/// headroom (45.7 against 50), so a 2.08× swing goes straight through it. The bound
/// was not too tight; a wall clock is not an oracle for this question. Raising it
/// would have bought silence, not truth: at 4× headroom the guard would stop failing
/// AND stop being able to fail for the reason it exists.
///
/// # What the row is actually about, and it is a COUNT
///
/// The defect is an exact O(n²) crossing test with no cap — for one 50 000-vertex
/// ring that is ~1.25 × 10⁹ orientation pairs, and a shape that does not cross
/// cannot exit early, so it pays all of them; per retry, per rung, per pack. The
/// bounded sweep charges every pair it tests to [`SelfxBooks::pairs`]. That number
/// is a property of the algorithm and the fixture: identical on every run, on every
/// box, at every load, in either profile. It is what changed when the row landed and
/// it is therefore what the guard asserts.
///
/// # The ceiling was CHOSEN BY DRIVING IT RED, and the first one was blind
///
/// MEASURED on this fixture: the whole retry ladder charges **1 741 616** pair
/// tests, identical on six consecutive full-suite runs at box load 124–128 on 32
/// cores while the wall clock ranged 244.0–304.7 ms in the same six.
///
/// The first ceiling written here was 8 000 000, reasoned from the per-segment
/// budget. **It could not fail.** Driving the red arm — the sweep's x-interval
/// retirement disabled, which is the O(n²) shape the row removed — charges
/// **6 281 824**, and 6 281 824 < 8 000 000, so the guard sailed through the exact
/// defect it exists to catch. That is the hollow-guard shape LAW 2 is about, and it
/// was in a guard written WHILE replacing another hollow one.
///
/// **3 000 000** is the number: 1.72× over what the fixture really costs (room for a
/// legitimate change to the candidate filter) and 2.09× under what the unbounded
/// sweep costs (so removing the bound fails). Both ends are measured, not reasoned.
const PAIR_CEILING: u64 = 3_000_000;
/// **The wall clock is still MEASURED and PRINTED — it is just not the assertion.**
/// A number nobody can act on is worse than no number, and the release figure is the
/// one to quote at a human ("a 50 000-vertex ring packs in ~46 ms"). It is reported
/// beside the box load so a reader can see what it is a number about.
const REPORT_ONLY_BOUND: std::time::Duration = if cfg!(debug_assertions) {
std::time::Duration::from_millis(700)
} else {
std::time::Duration::from_millis(50)
};
/// **A 50 000-vertex ring packs for a BOUNDED number of orientation tests.**
///
/// Before this row the crossing test on its DP output was exact O(n²) with no cap —
/// ~1.25 × 10⁹ pairs, and a shape that does not cross cannot exit early, so it pays
/// all of them; per retry, per rung, per pack. See [`PAIR_CEILING`] for why this
/// asserts a count and only PRINTS the clock the guard used to assert.
#[test]
fn a_50k_vertex_ring_packs_for_a_bounded_number_of_pair_tests() {
let polys = timing_polys();
let eps = generalisation_eps(9);
let mut s = DpScratch::default();
// Warm: the pack calls this once per row on a scratch that has already served
// thousands of rows, so a cold high-water mark is not what is being measured.
simplify_polys_into(&polys, eps, &mut s);
let kept = s.polys.as_slice()[0].0.len();
// MEASURED 24 536: DP keeps the ripple's EXTREMA and drops the samples that sit
// on the chord between them — half of 50 000, which is what a real shore does
// too. The arm is here so a future DP change that quietly collapsed the fixture
// could not leave this timing guard green over nothing.
assert!(
kept > 20_000,
"the fixture must stay BIG through DP or the timing proves nothing (kept {kept})",
);
// The books are per-scratch, so they are this fixture's alone — no reset of a
// process-global is needed and no other test in this binary can perturb them.
s.books = SelfxBooks::default();
let t0 = std::time::Instant::now();
const REPS: u32 = 3;
for _ in 0..REPS {
simplify_polys_into(&polys, eps, &mut s);
}
let per = t0.elapsed() / REPS;
let pairs = s.books.pairs / u64::from(REPS);
let books = s.books;
// NOT a per-segment rate: `pairs` is charged over the whole fixture — the big
// ring, the four forced-retry shores and every retry of each — while `kept` is
// the big ring's output alone. Dividing them would print a ratio between two
// different populations, which is the arithmetic this constellation keeps
// catching itself doing. The raw count is the number; what it covers is said.
println!(
"row24 pack of a 50 000-vertex ring: {pairs} orientation-pair tests over the \
whole fixture (1 big ring + 4 forced-retry shores, all retries; ceiling \
{PAIR_CEILING}), big ring kept {kept} of 50 001 vertices, books {books:?}; \
wall {per:?} REPORTED ONLY (indicative bound {REPORT_ONLY_BOUND:?}, \
profile {})",
if cfg!(debug_assertions) { "debug" } else { "release" },
);
// NOT VACUOUS: a fixture that stopped charging any pairs would pass a ceiling
// trivially, and that is precisely how a guard dies quietly.
assert!(
pairs > 1_000,
"the sweep charged only {pairs} pair tests — the fixture is not exercising \
the crossing test at all, so the ceiling below proves nothing",
);
assert!(
pairs < PAIR_CEILING,
"packing a 50 000-vertex ring charged {pairs} orientation-pair tests \
(ceiling {PAIR_CEILING}) — the crossing test is unbounded again",
);
// **The CONSEQUENCE, not the proxy.** An unbounded sweep does not merely cost
// more: it exhausts its budget, answers `Unknown`, and the pack then ships the
// ring's SOURCE vertices — so the rung stops being smaller than the base, which
// is the thing a user would actually see. The red arm above moved `kept` from
// 24 536 to 50 001 and `shipped_source` from 0 to 1; both are asserted, because
// a count ceiling alone would still pass a sweep that got cheap by giving up.
assert!(
(kept as u64) < 50_001,
"the big ring shipped its SOURCE vertices ({kept} of 50 001) — the sweep \
could not answer it, so the rung is not smaller than the base",
);
assert_eq!(
(books.shipped_source, books.unchecked),
(0, 0),
"the pack gave up on a ring of this fixture (books {books:?}) — every one of \
them must be answered WITHIN the budget, or the ceiling above is being met \
by refusing work rather than by bounding it",
);
}
/// **The retry loop allocates NOTHING after warm-up.** It used to allocate a fresh
/// `Vec` per Douglas–Peucker attempt, a fresh output ring per ring, a fresh holes
/// `Vec` per polygon and a `clone` of the source ring on give-up — in the pack's
/// hot loop, which is exactly the `tilemem-2` shape (11.13 GiB of glibc arena free
/// list behind a 32-worker fan-out).
#[test]
fn the_retry_loop_allocates_nothing_after_warm_up() {
// Small enough that a slow instrument does not slow the suite, and it carries
// every path: a clean ring, four retry-then-succeed rings, a hole.
let mut polys = vec![(
rippled_ring(2_000, 13.2, 58.9, 0.5, 1.0e-3, 500.0),
vec![rippled_ring(400, 13.2, 58.9, 0.05, 1.0e-3, 100.0)],
)];
for _ in 0..4 {
polys.push((shore(), Vec::new()));
}
let eps = generalisation_eps(9);
let mut s = DpScratch::default();
// Two warm-up passes: the first reaches the pool's high-water mark, the second
// proves the first one's growth was the last.
simplify_polys_into(&polys, eps, &mut s);
simplify_polys_into(&polys, eps, &mut s);
let (_, allocs) = crate::alloc_probe::count_allocs(|| {
simplify_polys_into(&polys, eps, &mut s);
});
assert_eq!(
allocs, 0,
"the retry loop allocated {allocs} times on a warm scratch — the pack's \
hot loop must reuse the worker's buffers, not the glibc arena",
);
}
/// **A ring over the segment cap ships its SOURCE, and says so.** The census's
/// exact test caps at 512 segments and counts what it skipped (`big_ring_unchecked`)
/// — it never passes a ring it did not check. The pack must hold the same line: over
/// [`SELFX_PACK_MAX_SEGS`] it does not check, so it does not ship the simplification
/// either. An unchecked simplified ring is a bowtie nobody can see; the source ring
/// is what the base column already serves.
#[test]
fn a_ring_over_the_segment_cap_ships_its_source_unchecked() {
// The cap is on the ring being CHECKED — the simplification — and this ripple
// keeps its extrema, so about half the source survives DP: 160 000 vertices in
// puts ~78 000 segments over the 65 536 cap.
const N: usize = 160_000;
#[allow(clippy::cast_precision_loss)]
let big = rippled_ring(N, 13.2, 58.9, 0.5, 1.0e-3, (N / 4) as f64);
let polys = vec![(big.clone(), Vec::new())];
let mut s = DpScratch::default();
simplify_polys_into(&polys, generalisation_eps(9), &mut s);
let out = s.polys.as_slice();
assert_eq!(out.len(), 1);
assert!(
super::douglas_peucker(&big, generalisation_eps(9)).len() - 1
> SELFX_PACK_MAX_SEGS,
"the fixture no longer simplifies to more than the cap — it stopped testing \
the path it exists for",
);
assert_eq!(
out[0].0.len(),
big.len(),
"over the cap the SOURCE ring ships, vertex for vertex",
);
// `pairs` is compared separately: it is a WORK count, so pinning it to a
// literal here would make this assertion about the sweep's candidate filter as
// well as about the books, and a filter improvement would then fail a test about
// give-up counts. Over the segment cap the sweep is never entered at all, which
// IS the claim, so zero is the right assertion and it is a specific one.
assert_eq!(
SelfxBooks { pairs: 0, ..s.books },
SelfxBooks { retries: 0, shipped_source: 1, unchecked: 1, pairs: 0 },
"the pack must COUNT the rings it shipped unsimplified — a rung that is \
not smaller than its base is a number, not a surprise",
);
assert_eq!(
s.books.pairs, 0,
"a ring over SELFX_PACK_MAX_SEGS is refused BEFORE the sweep, so it must \
charge no pair tests at all",
);
}
/// **A ring that still crosses at eps/16 ships its SOURCE ring** — not a crossing
/// simplification, and not silence: `shipped_source` counts it.
///
/// The fixture is [`SELFX_ADVERSARIAL_RING`] at [`SELFX_ADVERSARIAL_EPS`]: the real
/// shore ring with a 1/16-scale copy of itself pinched onto its first vertex, so the
/// same inlet defect exists at two scales four octaves apart and the ladder's five
/// halvings cannot walk past both. The precondition is asserted below rather than
/// assumed — a fixture that stopped reproducing would otherwise leave this guard
/// green over nothing.
#[test]
fn a_ring_that_crosses_at_every_tolerance_ships_its_source() {
let src = SELFX_ADVERSARIAL_RING();
let eps = SELFX_ADVERSARIAL_EPS;
// The precondition, pinned as an arm: the SOURCE is a clean ring, and plain DP
// crosses at every one of the five tolerances the ladder walks.
assert!(!ring_self_intersects(&src), "the source ring must itself be clean");
let mut e = eps;
for k in 0..5 {
let t = super::douglas_peucker(&src, e);
assert!(
ring_self_intersects(&t),
"the fixture stopped crossing at eps/{} — it no longer defeats the ladder",
1 << k,
);
e /= 2.0;
}
let mut s = DpScratch::default();
simplify_polys_into(&[(src.clone(), Vec::new())], eps, &mut s);
let out = s.polys.as_slice();
assert_eq!(out.len(), 1, "the ring survives");
assert!(
!ring_self_intersects(&out[0].0),
"the packed ring still crosses itself — the census would count it a bowtie",
);
assert_eq!(
out[0].0.len(),
src.len(),
"having failed at every tolerance, the SOURCE ring must ship",
);
assert_eq!(
s.books.shipped_source, 1,
"the give-up must be COUNTED, not silent (books {:?})",
s.books,
);
assert_eq!(
s.books.retries, 4,
"the ladder must really have been walked before giving up (books {:?})",
s.books,
);
assert_eq!(s.books.unchecked, 0, "this ring is far under the cap: it WAS checked");
}
/// **The ring that defeats the WHOLE retry ladder**, and the epsilon it does it at.
///
/// One scale is not enough. MEASURED on this box: the real [`shore`] ring's plain-DP
/// output crosses over a window of about three consecutive halvings and is clean
/// either side of it — a bowtie needs an epsilon coarse enough to merge the two arms
/// of an inlet and fine enough to still keep both. The ladder walks FIVE halvings, so
/// a ring that defeats it must carry the same defect at two scales four octaves
/// apart: this is the shore with a 1/16-scale point-reflected copy of itself pinched
/// onto its first vertex.
///
/// Star-shaped rings were tried first and are the wrong instrument: a ring whose
/// radius is single-valued in θ has no two arms of boundary near each other, so
/// Douglas–Peucker cannot bowtie it at ANY epsilon (surveyed over 8 octaves of a
/// `1/f^0.8` coastline spectrum, 12 seeds — not one crossing).
///
/// `5.0e-4` is not a rung epsilon; it lies between z8 (6.87e-4) and z9 (3.43e-4).
/// That is honest rather than convenient: the ladder is a function of the epsilon it
/// is handed, and no RUNG epsilon defeats all five of its own halvings on any fixture
/// this hunt found — which is itself the measurement that says how rare the give-up
/// path is. [`ladder_crossing_survey`] is the hunt, kept runnable.
#[allow(non_snake_case)]
fn SELFX_ADVERSARIAL_RING() -> Vec<(f64, f64)> {
lobed_shore(&[(-0.0625, 0)])
}
const SELFX_ADVERSARIAL_EPS: f64 = 5.0e-4;
/// The [`shore`] motif pinched onto itself at several scales and anchors: each
/// `(scale, anchor)` appends a copy of the ring scaled about `shore()[anchor]`,
/// re-entering the polyline at that vertex. A `scale` of 0 is no lobe.
fn lobed_shore(lobes: &[(f64, usize)]) -> Vec<(f64, f64)> {
let a = shore();
let n = a.len() - 1;
let mut ls: Vec<(f64, usize)> =
lobes.iter().copied().filter(|&(s, _)| s != 0.0).map(|(s, i)| (s, i % n)).collect();
ls.sort_by_key(|&(_, i)| i);
let mut v: Vec<(f64, f64)> = Vec::new();
let mut cut = 0usize;
for &(s, anchor) in &ls {
v.extend_from_slice(&a[cut..=anchor]);
let (px, py) = a[anchor];
// The lobe re-enters the host ring at the SAME vertex it left from, so the
// polyline stays closed and the join is a self-TOUCH, not a crossing.
for &(x, y) in a.iter().skip(1) {
v.push((s.mul_add(x - px, px), s.mul_add(y - py, py)));
}
cut = anchor + 1;
}
v.extend_from_slice(&a[cut..]);
v
}
/// **The hunt that produced [`SELFX_ADVERSARIAL_RING`]**, kept runnable — a
/// measurement, not a guard.
///
/// Sweeps the shore motif pinched onto itself at up to two extra scales and anchors,
/// keeps only the candidates whose SOURCE ring is clean, and reports every one whose
/// plain-DP output crosses at five CONSECUTIVE halvings — the length of the retry
/// ladder. It also prints the pinned fixture's behaviour at every real rung epsilon,
/// which is the measurement behind [`SELFX_ADVERSARIAL_EPS`]'s note that no rung
/// epsilon defeats its own ladder.
#[test]
#[ignore = "a measurement, not a guard: cargo test -p osm-katana --lib row24 -- --ignored --nocapture"]
fn ladder_crossing_survey() {
/// Crossing pattern of plain DP over `n` halvings from `e0`; `X` = crosses.
fn pattern(r: &[(f64, f64)], e0: f64, n: usize) -> String {
let mut e = e0;
(0..n)
.map(|_| {
let t = super::douglas_peucker(r, e);
e *= 0.5;
if ring_self_intersects(&t) { 'X' } else { '.' }
})
.collect()
}
const E0: f64 = 4.0e-3;
let mut hits = 0;
for s2 in [-0.5_f64, -0.25, -0.125, -0.0625, -0.031_25] {
for a2 in [0usize, 12, 24, 36, 48, 60] {
for s3 in [0.0_f64, -0.25, -0.125, -0.0625, -0.031_25, -0.015_625] {
for a3 in [0usize, 18, 30, 42, 54] {
if s3 == 0.0 && a3 != 0 {
continue;
}
let r = lobed_shore(&[(s2, a2), (s3, a3)]);
if ring_self_intersects(&r) {
continue; // a crossing SOURCE would prove nothing
}
let pat = pattern(&r, E0, 48);
let b = pat.as_bytes();
if let Some(i) = (0..b.len() - 5).find(|&i| b[i..i + 5] == *b"XXXXX") {
#[allow(clippy::cast_possible_truncation, clippy::cast_possible_wrap)]
let eps = E0 * 0.5_f64.powi(i as i32);
println!(
"HIT s2={s2} a2={a2} s3={s3} a3={a3} eps={eps:e} n={} {pat}",
r.len(),
);
hits += 1;
}
}
}
}
}
println!("hits: {hits}");
let r = SELFX_ADVERSARIAL_RING();
println!(
"pinned: n={} simple={} from {SELFX_ADVERSARIAL_EPS:e}: {}",
r.len(),
!ring_self_intersects(&r),
pattern(&r, SELFX_ADVERSARIAL_EPS, 5),
);
for z in 6u8..=14 {
let e = generalisation_eps(z);
println!(" z{z} eps={e:e}: {}", pattern(&r, e, 5));
}
}
}
/// **Douglas-Peucker polyline simplification** (`eps` in degrees ≈ one tile pixel at
/// the target zoom — see [`tile_pixel_tol`]). Keeps the first and last vertex and,
/// recursively, any vertex whose PERPENDICULAR distance from the chord between the
/// current segment's kept endpoints exceeds `eps`; everything within `eps` of the
/// chord is dropped. This is the proper shape-preserving LOD — radial thinning merely
/// kept whichever vertices happened to be `tol` apart (dropping the ones that actually
/// carry a bend, and keeping redundant collinear runs); DP keeps exactly the vertices
/// that define the curve at this scale.
///
/// A coarser zoom ⇒ larger `eps` ⇒ never MORE vertices survive, and the two endpoints
/// are always preserved. `eps <= 0` or a ≤2-pt line is a no-op. Iterative (an explicit
/// index-range stack + a keep-bitmap) so even a 2000-node way can never blow the stack.
pub(crate) fn douglas_peucker(coords: &[(f64, f64)], eps: f64) -> Vec<(f64, f64)> {
let mut scratch = DpScratch::default();
let mut out = Vec::new();
douglas_peucker_into(coords, eps, &mut scratch, &mut out);
out
}
/// The two working buffers [`douglas_peucker_into`] would otherwise allocate on every
/// call: the keep-bitmap and the index-range stack.
///
/// # Why a scratch type exists at all (`tilemem-2`)
///
/// The tile scan calls the simplifier **once per way per zoom**, and each call used to
/// allocate `keep`, `stack` and the output — three `Vec`s — plus the flat coordinate
/// list that fed it and the WKB buffer that came out. MEASURED on oden 2026-08-03:
/// the 32-worker scan holds 21.46 GiB of glibc arena against 10.34 GiB live, while the
/// SERIAL arm on the same input holds 10.33 against 10.32 — **11.13 GiB of arena free
/// list that is nothing but the fan-out's short-lived allocations**, never returned to
/// the kernel because glibc grows one arena per thread and frees to it, not to the OS.
///
/// The buffers are pure scratch: nothing outside the call reads them, and their
/// contents are fully overwritten each time. One per worker, held for the whole scan
/// unit, is the same lifetime the worker already has.
#[derive(Default)]
pub(crate) struct DpScratch {
/// The kernel's keep-bitmap and index stack.
dp: DpKernel,
/// The self-intersection sweep's segment order and active list (row 24).
selfx: crate::verify::SelfxScratch,
/// The polygons of the last [`simplify_polys_into`] call, ring buffers reused.
pub(crate) polys: PolyPool,
/// The ring-safe retry loop's counts, folded once per worker (row 24).
pub(crate) books: SelfxBooks,
}
/// The two buffers [`dp_kernel`] needs: the keep-bitmap and the `[a, b]` span stack.
#[derive(Default)]
pub(crate) struct DpKernel {
keep: Vec<bool>,
stack: Vec<(usize, usize)>,
}
/// A longitude below this scale is treated as this scale — `cos(lat)` at 89.43°.
///
/// Not a tuning knob: at the pole `cos(lat)` is 0 and every longitude difference
/// collapses to nothing, so a polar feature would simplify to a straight line whatever
/// its shape. OSM has geometry above 89° (the Arctic research stations, the 90°N
/// coastline artefacts), and a floor is the difference between "very aggressive" and
/// "deleted".
const MIN_LON_SCALE: f64 = 0.01;
/// **How much a degree of longitude is worth here, against a degree of latitude.**
///
/// `cos(mid-latitude)`, floored at [`MIN_LON_SCALE`].
///
/// # Why the simplifier needs this at all (row 29a, 2026-09-05)
///
/// Douglas–Peucker's perpendicular distance used to be computed straight out of
/// `(lon, lat)` pairs. A degree of latitude is ~111 km everywhere; a degree of longitude
/// is 111 km at the equator and **55.6 km at 60°N**, the middle of Sweden. So the same
/// physical deviation measured across a NORTH–SOUTH feature — where the deviation lands
/// in longitude — read about **twice its true size**, and cleared an `eps` that its
/// EAST–WEST twin did not.
///
/// That is not a rounding difference. It made the generaliser's aggressiveness a
/// function of a feature's compass bearing: two identical bays, one facing north and one
/// facing east, came back at different levels of detail on the same rung. MEASURED
/// through a real pack at 60°N, one metrically identical 20 km shore in both
/// orientations, `geometry_z9` read off disk: **east–west kept 17 vertices, north–south
/// kept 30** — a 43.3 % spread (`tests/metric_dp.rs`, the arm this constant exists for).
///
/// # One scale per input, and why not per segment
///
/// The factor is taken once from the mid-latitude of the whole input, not per chord.
/// Douglas–Peucker is recursive and a vertex is measured against several different
/// chords on its way to a verdict; if the metric changed between those frames the same
/// vertex could be "far" in one and "near" in another, and the result would depend on
/// the recursion order rather than on the shape. One scale per input keeps the metric a
/// metric.
///
/// The cost is a real approximation for a feature spanning many degrees of latitude — a
/// clip polygon for all of Sweden runs 55°N to 69°N, where `cos` moves from 0.57 to
/// 0.36. That is stated rather than hidden: it is still far closer than the 1.0 this
/// code used before, and the alternative (a projected copy of every input) is an
/// allocation per ring in the hottest loop of the pack.
fn lon_scale_of(coords: &[(f64, f64)]) -> f64 {
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for &(_, lat) in coords {
if lat < lo {
lo = lat;
}
if lat > hi {
hi = lat;
}
}
if !lo.is_finite() || !hi.is_finite() {
return 1.0;
}
let mid = (lo + hi) * 0.5;
let k = mid.to_radians().cos().abs();
if k.is_finite() { k.max(MIN_LON_SCALE) } else { 1.0 }
}
/// [`douglas_peucker`] writing into a caller-owned `out` and borrowing caller-owned
/// working buffers — the ONE implementation (LAW 5); the allocating form above is a
/// three-line wrapper over it, so the two can never drift.
///
/// `out` is cleared first; `scratch` may hold anything.
pub(crate) fn douglas_peucker_into(
coords: &[(f64, f64)],
eps: f64,
scratch: &mut DpScratch,
out: &mut Vec<(f64, f64)>,
) {
dp_kernel(coords, eps, &mut scratch.dp, out);
}
/// The Douglas–Peucker kernel itself, on its two buffers. [`douglas_peucker_into`] is
/// this on a whole [`DpScratch`]; the ring-safe loop calls it directly because it holds
/// the scratch's other fields at the same time.
fn dp_kernel(
coords: &[(f64, f64)],
eps: f64,
scratch: &mut DpKernel,
out: &mut Vec<(f64, f64)>,
) {
out.clear();
let n = coords.len();
if n <= 2 || eps <= 0.0 {
out.extend_from_slice(coords);
return;
}
let eps2 = eps * eps;
// **The longitude scale (row 29a, 2026-09-05).** See [`lon_scale_of`]: without it
// this kernel thins a feature by its COMPASS BEARING.
let k = lon_scale_of(coords);
let k2 = k * k;
let keep = &mut scratch.keep;
keep.clear();
keep.resize(n, false);
keep[0] = true;
keep[n - 1] = true;
// Each frame is an inclusive [a, b] index span whose interior we still must split.
let stack = &mut scratch.stack;
stack.clear();
stack.push((0usize, n - 1));
while let Some((a, b)) = stack.pop() {
if b <= a + 1 {
continue; // no interior vertices between a and b
}
let (ax, ay) = coords[a];
let (bx, by) = coords[b];
let (dx, dy) = (bx - ax, by - ay);
// Chord length² in the SCALED space: x' = lon·k, y' = lat.
let seg2 = dx * dx * k2 + dy * dy;
let mut max_d2 = 0.0_f64;
let mut split = a;
for i in (a + 1)..b {
let (px, py) = coords[i];
// Perpendicular distance² from vertex i to the infinite line a→b (the
// classic DP metric), measured in the scaled space. A degenerate chord
// (a==b) falls back to |i−a|².
//
// The scale factors out of the cross product exactly:
// cross' = (px−ax)·k·dy − (py−ay)·dx·k = k·[(px−ax)·dy − (py−ay)·dx]
// so only `k²` and the scaled `seg2` are needed and no coordinate is
// rewritten — the kernel stays allocation-free.
let d2 = if seg2 <= 0.0 {
let (ex, ey) = ((px - ax) * k, py - ay);
ex * ex + ey * ey
} else {
let cross = (px - ax) * dy - (py - ay) * dx;
k2 * cross * cross / seg2
};
if d2 > max_d2 {
max_d2 = d2;
split = i;
}
}
if max_d2 > eps2 {
keep[split] = true;
stack.push((a, split));
stack.push((split, b));
}
}
out.extend(
coords
.iter()
.zip(keep.iter())
.filter_map(|(&p, &k)| k.then_some(p)),
);
}
/// [`douglas_peucker`] for a closed RING: simplify, then re-close, so a ring
/// never comes back open. The one simplifier in the crate, shared by the tile
/// pyramid's LOD and [`crate::Polygon::simplify`] (LAW 5).
pub(crate) fn simplify_ring(ring: &[(f64, f64)], eps: f64) -> Vec<(f64, f64)> {
let mut out = douglas_peucker(ring, eps);
if out.len() >= 3 {
if let (Some(&first), Some(&last)) = (out.first(), out.last()) {
if first != last {
out.push(first);
}
}
}
out
}
/// Bbox of a flat coord list.
fn coords_bbox(coords: &[(f64, f64)]) -> Option<(f64, f64, f64, f64)> {
let mut it = coords.iter().copied();
let (mut minx, mut miny) = it.next()?;
let (mut maxx, mut maxy) = (minx, miny);
for (x, y) in it {
minx = minx.min(x);
miny = miny.min(y);
maxx = maxx.max(x);
maxy = maxy.max(y);
}
Some((minx, miny, maxx, maxy))
}
/// **How wide, in screen pixels, one tile is actually drawn** — the denominator of
/// [`tile_pixel_tol`], and therefore the thing that decides how much shape the writer
/// throws away.
///
/// # Why this is a parameter and not `256`
///
/// It WAS `256`, unnamed, inline in the epsilon. 256 is the historical slippy-map
/// *raster* size, and it is not the size anything in this stack renders at: facett draws
/// one tile across the map viewport, ~1920 px wide. A `256`-based epsilon therefore
/// permits a deviation of **1 tile pixel = 7.5 screen pixels**, and the writer spends it:
/// MEASURED on the live `sweden` pyramid 2026-08-03, 120 sampled tiles / 1 336 419 rows
/// carried **2.02 / 2.26 / 2.32 vertices per way** at z6 / z9 / z12 against **13.3 in the
/// source extract** — geometry flattened almost to a straight line before it was ever
/// stored, with **zero polygons and zero hole vertices surviving anywhere**. The densest
/// z6 tile averaged exactly 2.00 vertices per way, i.e. two-point "rings" that triangulate
/// to nothing. Detail was being discarded in the WRITER and then looked for in the reader.
///
/// # Why 2048 and not 1920
///
/// 1920 is one consumer's current viewport width, and hard-coding it would only swap one
/// arbitrary constant for another. 2048 is the next power of two at or above it, so the
/// epsilon stays sub-pixel for any viewport up to 2048 px with one doubling of headroom,
/// and it is a [`TileOptions`] field precisely so the next person to change the render
/// size can see — and move — the coupling from the render side. It rides in the
/// [`TileRecipe`], so raising it makes every existing pyramid read as STALE and be re-cut,
/// instead of silently serving geometry cut for a smaller screen.
///
/// Cost of the 256 → 2048 move: the epsilon shrinks 8×, so more vertices survive and tiles
/// grow. Measure it per run — [`ZoomTileStats`] reports mean/max bytes per zoom.
pub const DEFAULT_TILE_RASTER_PX: u32 = 2048;
/// The Douglas-Peucker epsilon (and legacy way-thinning tolerance) for zoom `z`, in
/// degrees ≈ one **rendered** pixel (`360° / (raster_px · 2^z)`) — the ground resolution
/// of a pixel at that zoom on a tile drawn `raster_px` wide, so a way is simplified only
/// until its deviation is sub-pixel *as actually displayed*. See
/// [`DEFAULT_TILE_RASTER_PX`] for why `raster_px` is not the constant 256 it used to be.
#[inline]
pub(crate) fn tile_pixel_tol(z: u8, raster_px: u32) -> f64 {
360.0 / (f64::from(raster_px.max(1)) * f64::from(1u32 << z))
}
/// **The columns every tile carries**, and the ONE place they are declared (LAW 5):
/// [`write_tile_parquet`] builds its schema from this, and [`TileRecipe`] describes it
/// from this, so a column added here moves the recipe automatically. A recipe that had
/// to be bumped by hand would be exactly one forgotten edit away from the defect it
/// exists to catch.
pub(crate) fn tile_fields() -> Vec<Field> {
vec![
Field::new("id", DataType::Int64, false),
crate::shared::schema::geometry_field(),
Field::new("tags", DataType::Utf8, true),
// The packer's own covering field (LAW 5) — this used to be a four-line twin of
// `spatial::bbox_field`, and since `short_type` spells a struct's children the
// twin would have been two spellings of one column the moment either moved.
crate::spatial::bbox_field(),
]
}
/// The leaf fields of the GeoParquet 1.1 `covering.bbox` struct column — read off
/// [`crate::spatial::bbox_field`], never declared a second time.
fn bbox_leaf_fields() -> Fields {
match crate::spatial::bbox_field().data_type() {
DataType::Struct(leaves) => leaves.clone(),
other => unreachable!("spatial::bbox_field is a Struct, got {other:?}"),
}
}
/// **Everything about a tiling run that a reader must re-cut for when it changes.**
///
/// # The defect this exists to make impossible
///
/// `format` in the manifest has said `"geoparquet-1.1-covering-tiles"` since the manifest
/// existed, and it kept saying exactly that when the `id` column was added. So on
/// 2026-08-03 korp-server booted, GET the manifest, saw a valid zoom set plus 28 974 tile
/// objects, concluded "tiled", and skipped tiling — while every one of those tiles was cut
/// **without `id`**, which is the column facett's `layer.rs` uses as the sole discriminator
/// in its GPU signature. The server could not tell a current pyramid from a two-schema-old
/// one, and there was no value anywhere in the store that would have let it. Filed
/// `collauto-6`.
///
/// # Why a derived token and not an `if id column missing`
///
/// A check that recognises *`id`* fixes today and not the next change. This token is
/// DERIVED — from [`tile_fields`] (so a new, removed or retyped column moves it with no
/// edit here) and from the simplification basis [`TileOptions::tile_raster_px`] (so
/// re-tuning the tolerance also forces a re-cut, because tiles cut for a 256-px raster are
/// the wrong DATA for a 2048-px one even though their schema is identical). Anything that
/// changes what a tile *contains* belongs in here; anything that only changes where tiles
/// live does not.
///
/// The token is a readable descriptor rather than a hash on purpose: it lands in a manifest
/// an operator greps, and the diff between two of them should say *what* changed. It must
/// NOT be a `DefaultHasher` digest — that is only stable within one toolchain, and a
/// toolchain bump would re-cut a planet for nothing.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct TileRecipe {
/// `name:Type` per column, in writer order.
pub columns: Vec<String>,
/// The render width the LOD epsilon was computed against.
pub raster_px: u32,
/// **The geometry classes a tile may CONTAIN**, from [`TileGeom::CLASSES`].
///
/// The schema axis alone could not see the change that added `Poly`: the
/// `geometry` column is `Binary` before and after, and a pyramid cut when the
/// writer could only emit Point and LineString holds a lake's island as a
/// notch cut to the shore, under a byte-identical schema. Same defect class as
/// the one that made `raster_px` part of the recipe — different DATA, same
/// shape — so it is DERIVED from the enum and moves with no edit here.
pub geometry_classes: String,
/// **What this run handed to a network table instead of tiling** — empty when the
/// pyramid carries everything. [`crate::network::tiled_out_selector`], so adding a
/// network to the hand-over moves every tile recipe with no edit here.
pub excluded: String,
/// **The zoom levels the pyramid was cut at**, ascending.
///
/// In here because adding a zoom is a change to what the pyramid CONTAINS, and
/// because without it nothing in the fleet can observe one. Measured on the live
/// stack 2026-08-03: korp's gate is `korp::map_tiles::tiling_action` (cited by
/// SYMBOL — see the ruling on `TileRecipe` below; a line number in another repo
/// rots the first time anyone edits above it), whose
/// `TiledState::Tiled(_)` arm **discards the manifest's zoom list** and defers
/// entirely to the recipe — so a build whose `DEFAULT_TILE_ZOOMS` had gained `15`
/// would read a `[6,9,12]` manifest, get `Serve`, and go on serving the old
/// pyramid forever. Same family as `collauto-6`: a gate that cannot see the axis
/// that moved.
///
/// Putting it here rather than adding a fourth probe to korp is the fix BY
/// CONSTRUCTION (LAW 5): the staleness machinery korp already has — manifest claim
/// + probe one tile's own footer + `recipe_verdict` — starts reporting the zoom set
/// with no korp change at all, and a tile carries the answer in its own bytes
/// rather than in a document beside it.
pub zooms: Vec<u8>,
/// **WHICH features a full tile keeps** — the [`WayLane`] ladder, spelled
/// `lanes=40.80.100@1/32`.
///
/// In here for the same reason `raster_px` is: two pyramids with an identical schema,
/// an identical zoom set and identical row counts can hold different DATA. Before
/// this ladder existed a full tile kept whatever arrived first, and `sweden` shipped
/// z9 tiles at exactly 60 000 rows with Mälaren nowhere in them (`natt-7`). A server
/// that could not see the selection policy would GET that manifest, read a valid
/// recipe, and go on serving lakeless coarse zooms forever — `collauto-6` with a
/// different column. DERIVED from [`WAY_LANE_KEEP_PERCENT`] and
/// [`DOMINANT_TILE_FRACTION`], so retuning the ladder moves every recipe with no
/// edit here.
pub selection: String,
/// **Whether the relations were RESOLVED when this pyramid was cut** —
/// [`relations_axis`], one of [`RELS_RESOLVED`] / [`RELS_RESOLVED_EMPTY`] /
/// [`RELS_RAW`] / [`RELS_NONE`] / [`RELS_UNKNOWN`].
///
/// The six axes before it all exist because a real gate could not see a real change,
/// and this is the same family: the tiler picks its relation table on
/// `relations.resolved.parquet.exists()` and CUTS EITHER WAY, so a pyramid with not
/// one multipolygon in it stamped a byte-identical token to a complete one. MEASURED
/// on the live stack 2026-08-04: 0 of 14 592 834 geometries set, and the mean tile
/// 12.7 kB against 26.6 kB for the same region WITH relations — **relations are
/// ~52 % of a tile's bytes**, and korp's `tiling_action` said `Serve` on the empty
/// one forever.
///
/// [`Self::for_zooms`] stamps [`RELS_RESOLVED`], because that is the only complete
/// cut and korp compares a stored pyramid against `TileOptions::default().recipe()`.
/// A run OVERRIDES it with what it actually read ([`tile_region`]), so an incomplete
/// pyramid reads `Stale` and the chain resumes at step c by itself — with no korp
/// change at all, which is the point.
pub relations: String,
/// **The sub-pixel grid the NODE dedup collapsed on** — [`NODE_DEDUP_GRID_PX`].
///
/// In the token beside `raster` because they are two different answers to "how big
/// is a pixel here", eight times apart, and only one of them had a name. `raster_px`
/// is a recipe axis, so raising it re-cuts a planet — and the point resolution does
/// not move a millimetre. The token said `raster=2048` while the point path
/// implemented 256, and no gate in the fleet could see the difference. Now an
/// operator grepping a manifest reads `raster=2048;dedup=256` and the gap is on the
/// line. Derived from the constant, so closing the gap moves every recipe with no
/// edit here.
pub dedup_grid_px: u32,
}
/// The canonical spelling of the [`WayLane`] ladder for a [`TileRecipe`] — one writer,
/// so the token and the ladder cannot drift apart.
pub fn way_lane_selector() -> String {
format!(
"{}.{}.{}@1/{};order={}",
WAY_LANE_KEEP_PERCENT[0],
WAY_LANE_KEEP_PERCENT[1],
WAY_LANE_KEEP_PERCENT[2],
DOMINANT_TILE_FRACTION,
TILE_ROW_ORDER,
)
}
/// **The order rows are written in inside one tile file** — part of the selection policy,
/// because a reader that takes the first N rows gets different DATA under a different
/// order even though the file holds the same set.
///
/// `extent-desc` = biggest covering bbox first. See [`write_tile_parquet`].
pub const TILE_ROW_ORDER: &str = "extent-desc";
impl TileRecipe {
/// The recipe [`write_tile_parquet`] and [`tile_region`] implement **right now**
/// at the DEFAULT zoom set — the token korp's gate compares a stored pyramid
/// against (`korp::map_tiles::asset_recipe_state`, via `korp_tile_options()`).
///
/// Cited by SYMBOL, not by line. This file used to say `korp/src/map_tiles.rs:622`;
/// that line is now a local `let` in an unrelated function, because a line number in
/// another repo is a citation that rots the first time anyone edits above it and
/// nothing in either repo can go red about it. `korp_tile_options()` is also the
/// correction to what this used to name: since korp `ebf46d1` the gate compares
/// against KORP's ladder, not `TileOptions::default().recipe()`.
///
/// Kept at this signature deliberately. korp depends on this crate by path, so a
/// changed signature here is a broken build in another repo at merge time, for a
/// caller that means exactly "the default cut" anyway. [`Self::for_zooms`] is the
/// one writer; this is the default-argument case of it.
pub fn current(raster_px: u32) -> Self {
Self::for_zooms(DEFAULT_TILE_ZOOMS, raster_px)
}
/// [`Self::current`] for an explicit zoom set — what [`TileOptions::recipe`] uses,
/// so a run at a non-default zoom set stamps the recipe it actually implements.
pub fn for_zooms(zooms: &[u8], raster_px: u32) -> Self {
let mut zooms = zooms.to_vec();
// Ascending and deduped, so `[12,6,9]` and `[6,9,12]` are the same recipe —
// a re-cut is for a pyramid that differs, not for options spelled differently.
zooms.sort_unstable();
zooms.dedup();
Self {
columns: tile_fields()
.iter()
.map(|f| format!("{}:{}", f.name(), short_type(f.data_type())))
.collect(),
raster_px,
geometry_classes: TileGeom::CLASSES.to_string(),
excluded: String::new(),
zooms,
selection: way_lane_selector(),
// The COMPLETE cut — the only one a reader may serve. A run that read
// anything else overwrites this, and then does not match.
relations: String::from(RELS_RESOLVED),
dedup_grid_px: NODE_DEDUP_GRID_PX,
}
}
/// The stamped form:
/// `v1;cols=id:Int64,geometry:Binary,…;raster=2048;zooms=6.9.12;excl=…;
/// geoms=Point,Line,Poly;lanes=40.80.100@1/32`.
///
/// Zooms are `.`-joined because the token already uses `,` between columns and `;`
/// between fields, and a manifest an operator greps should stay one greppable line.
///
/// Five axes, all DERIVED, all answering the same question from a different side:
/// what columns a tile has, how hard it was simplified, which zooms exist, what was
/// handed to a network table instead, which geometry CLASSES the writer could emit,
/// and — when a tile is FULL — which features it kept ([`WayLane`]). Each was added
/// because a real gate could not see a real change.
///
/// **Every field of the struct must reach this string.** `selection` was added to
/// [`TileRecipe`] and NOT to the token in the first pass of this work, and the run
/// that proved it was reading its own manifest: a whole 46.29 GB Sweden cut under a
/// brand-new selection policy stamped a token byte-identical to the one the OLD
/// policy stamped, so korp would have read the new pyramid as current and — worse —
/// would have read the OLD one as current too. `every_recipe_field_reaches_the_token`
/// is the guard; it is field-driven, so the next axis cannot be forgotten the same
/// way.
pub fn token(&self) -> String {
let zooms: Vec<String> = self.zooms.iter().map(|z| z.to_string()).collect();
format!(
"v1;cols={};raster={};zooms={};excl={};geoms={};lanes={};rels={};dedup={}",
self.columns.join(","),
self.raster_px,
zooms.join("."),
self.excluded,
self.geometry_classes,
self.selection,
self.relations,
self.dedup_grid_px,
)
}
/// The recipe a tile parquet's footer declares, or `None` when it declares none —
/// which is what every pre-`collauto-6` tile does, and is the STALE answer.
///
/// Reads the footer only; no row group is decoded.
pub fn of_tile(path: &Path) -> anyhow::Result<Option<String>> {
Self::of_tile_bytes(bytes::Bytes::from(std::fs::read(path)?))
}
/// [`Self::of_tile`] for a tile that was **fetched, not opened** — the shape korp's
/// staleness probe needs, since the pyramid it must judge lives in an object store
/// and never touches the local filesystem. One writer for the footer lookup (LAW 5),
/// so the disk path and the store path can never disagree about what a tile claims.
pub fn of_tile_bytes(bytes: bytes::Bytes) -> anyhow::Result<Option<String>> {
let b = ParquetRecordBatchReaderBuilder::try_new(bytes)?;
Ok(b.metadata()
.file_metadata()
.key_value_metadata()
.and_then(|kv| kv.iter().find(|k| k.key == TILE_RECIPE_META_KEY))
.and_then(|k| k.value.clone())
.filter(|v| !v.is_empty()))
}
}
// The spelling of an Arrow type for the recipe descriptor USED TO LIVE HERE, as a private
// copy of the identical match in `network.rs`. The two had already drifted (that one grew
// an `Int8` arm for the graph's `oneway`, this one did not), and both ended in an `Other`
// catch-all that could not tell two types apart. One writer now:
// `shared::schema::short_type`. Every type a TILE column uses spells the same as before,
// so this move does NOT move a TileRecipe token — pinned by
// `the_tile_columns_spell_exactly_what_the_cut_pyramid_declares` against the literal
// string a tile on the live Sweden cut declares.
/// Backstop on how many tiles ONE way may be duplicated into at a single zoom. A way
/// whose bbox overlaps more tiles than this (e.g. a country-spanning coastline way at
/// a street zoom) is instead placed in the SINGLE tile of its bbox centre, so a
/// pathological geometry can never fan out to tens of thousands of tiles. Bbox-overlap
/// duplication with a sane ceiling.
pub const MAX_WAY_TILE_FANOUT: usize = 4096;
/// Every slippy tile `(x, y)` at zoom `z` whose extent the way bbox
/// `(minx, miny, maxx, maxy)` overlaps — **standard tile duplication**, so a way
/// straddling a tile border is emitted into EVERY tile it crosses (no edge clipping),
/// not just its centroid tile. If that span would exceed [`MAX_WAY_TILE_FANOUT`] tiles
/// the way falls back to the single tile of its bbox centre (the range is always finite
/// — bounded by `2^z` per axis — this cap only tames the pathological giant).
///
/// **The `bool` is `true` when the cap fired**, i.e. when this way was NOT placed in
/// the tiles it crosses but collapsed to one. That is geometry leaving the pyramid, so
/// it is returned rather than hidden: the cap is a fixed tile COUNT, but a tile is a
/// fixed fraction of the world, so the ground area it permits shrinks by 4× per zoom.
/// 4096 tiles is 64×64 of them — ≈ 620 × 620 km at z12 and ≈ 40 × 40 km at z15.
///
/// MEASURED on Sweden 2026-08-03, one run at `[6,9,12,15]`: **3 ways at z12 and 227
/// at z15**, both 0.00 % of 9 203 168 scanned. Note the z12 figure: the cap was never
/// wholly inert there either, which nobody knew until it was counted. It is far
/// fewer than the shrinking area suggests, because OSM splits long linear features
/// into segments, so almost nothing carries a 40 km bbox. 0.00 % is a MEASUREMENT,
/// and the only reason it can be reported as one is that the run counts it instead of
/// assuming it. At z18 the same constant permits ≈ 5 × 5 km and the number will not
/// be 227.
fn way_tiles(minx: f64, miny: f64, maxx: f64, maxy: f64, z: u8) -> (Vec<(u32, u32)>, bool) {
let mut out = Vec::new();
let capped = way_tiles_into(minx, miny, maxx, maxy, z, &mut out);
(out, capped)
}
/// [`way_tiles`] into a caller-owned buffer, returning only the capped flag — the ONE
/// implementation (LAW 5); the allocating form above is a three-line wrapper.
///
/// `out` is cleared first. The scan calls this once per way PER ZOOM and drops the
/// result at the end of the iteration, so a fresh `Vec` per call is pure churn — the
/// same `tilemem-2` shape as the simplifier's scratch, and the buffer's capacity
/// carries over to the next way for free.
fn way_tiles_into(
minx: f64,
miny: f64,
maxx: f64,
maxy: f64,
z: u8,
out: &mut Vec<(u32, u32)>,
) -> bool {
way_tiles_into_budget(minx, miny, maxx, maxy, z, MAX_WAY_TILE_FANOUT, out)
}
/// **The byte budget one feature may spend duplicating itself into tiles, at one zoom
/// — 8 MiB** ([`fanout_budget_tiles`]).
///
/// It is deliberately generous: it exists to stop a pathological giant from blowing the
/// staging buffer, not to ration ordinary geometry. At the ~80 bytes a coastline run
/// simplified for z15 actually costs, it permits ≈ 100 000 tiles; at the 8 KB a dense
/// polygon costs it permits ≈ 1 000, and the floor below keeps that from ever being
/// stricter than the old fixed count.
pub const MAX_WAY_FANOUT_BYTES: usize = 8 * 1024 * 1024;
/// **A hard ceiling on placements per feature per zoom**, whatever the budget says —
/// 512 × 512 tiles. A bound that a byte estimate can never argue its way past.
pub const MAX_WAY_FANOUT_TILES_CEILING: usize = 512 * 512;
/// **How many tiles one feature may be placed into, from what a placement COSTS.**
///
/// # Why the old fixed count was the wrong measure (`K18`)
///
/// [`MAX_WAY_TILE_FANOUT`] is a fixed number of TILES, and a tile is a fixed fraction of
/// the world — so the ground area it permits shrinks 4× per zoom step: ≈ 620 × 620 km at
/// z12, ≈ 40 × 40 km at z15, and the constant's own doc predicts ≈ 5 × 5 km at z18. The
/// consequence is that **the same feature is accepted at one zoom and refused at the next
/// for no reason that has anything to do with the feature.** MEASURED on the 2026-08-30
/// Sweden cut: `z12 = 4` capped and `z15 = 455` — a coastline, a river or a long railway
/// placed in its CENTROID TILE ONLY, so the shore is served in one of the many tiles it
/// crosses and vanishes from the rest exactly when a reader zooms in far enough to want
/// it. The run says so itself, as `failed_precondition[korp-map-36]`.
///
/// What the cap is actually protecting is the staging buffer, and that is measured in
/// BYTES. A long feature is cheap to duplicate precisely BECAUSE it is long and simple —
/// Douglas–Peucker has already thinned a coastline run at z15 to a handful of vertices —
/// while a dense polygon is expensive whatever its span. So the budget is
/// `MAX_WAY_FANOUT_BYTES / per`, clamped:
///
/// * never BELOW [`MAX_WAY_TILE_FANOUT`], so this change can only ever place MORE
/// geometry than before — it cannot newly refuse anything, which is what makes it safe
/// to land without re-measuring every zoom;
/// * never ABOVE [`MAX_WAY_FANOUT_TILES_CEILING`], so a mis-estimated `per` cannot ask
/// for an unbounded number of placements.
#[must_use]
pub fn fanout_budget_tiles(per: usize) -> usize {
let by_bytes = MAX_WAY_FANOUT_BYTES / per.max(1);
by_bytes.clamp(MAX_WAY_TILE_FANOUT, MAX_WAY_FANOUT_TILES_CEILING)
}
/// [`way_tiles_into`] with an explicit tile budget — the ONE implementation (LAW 5).
fn way_tiles_into_budget(
minx: f64,
miny: f64,
maxx: f64,
maxy: f64,
z: u8,
budget: usize,
out: &mut Vec<(u32, u32)>,
) -> bool {
out.clear();
let (x0, x1, y0, y1) = tile_range(&Bounds::new(minx, miny, maxx, maxy), z);
let span = (x1 - x0 + 1) as usize * (y1 - y0 + 1) as usize;
if span > budget {
let (cx, cy) = ((minx + maxx) * 0.5, (miny + maxy) * 0.5);
out.push(lonlat_to_tile(cx, cy, z));
return true;
}
out.reserve(span);
for x in x0..=x1 {
for y in y0..=y1 {
out.push((x, y));
}
}
false
}
/// Global 256-px-tile pixel coordinate of `(lon, lat)` at zoom `z`; `>> 8` is the
/// slippy tile, the low 8 bits are the pixel WITHIN the tile (the sub-pixel dedup
/// key), so one computation yields both.
#[inline]
fn global_pixel(lon: f64, lat: f64, z: u8) -> (u64, u64) {
let scale = f64::from(NODE_DEDUP_GRID_PX) * f64::from(1u32 << z);
let gx = ((lon + 180.0) / 360.0 * scale)
.floor()
.clamp(0.0, scale - 1.0) as u64;
let lat_rad = lat.clamp(-85.051_128_78, 85.051_128_78).to_radians();
let gy = ((1.0 - (lat_rad.tan() + 1.0 / lat_rad.cos()).ln() / std::f64::consts::PI) / 2.0
* scale)
.floor()
.clamp(0.0, scale - 1.0) as u64;
(gx, gy)
}
// ── tile GeoParquet writer (covering + geo metadata) ────────────────────────────
/// **One tile's rows, held FLAT** — `katana-9`.
///
/// # The defect this replaces
///
/// The write phase used to rebuild every tile as `Vec<Vec<u8>>` + `Vec<String>` +
/// `Vec<i64>` before handing it to [`write_tile_parquet`], which then copied the same
/// bytes AGAIN into the Arrow builders. That is **two heap allocations per ROW** — one
/// `Vec<u8>` for the WKB (`TileGeom::to_wkb`, a full `to_vec()` of an `Arc<[u8]>` the
/// accumulator already owns) and one `String` for the tag JSON, allocated even for the
/// untagged rows that are the common case. On the real Sweden pyramid at `[6, 9, 12]`
/// that is 13.8 M way placements + 70.0 M point placements = **~84 M rows, so ~168 M
/// short-lived allocations**, and 1.58 M tiles' worth again at z15. Across the write
/// phase's 31 workers those are exactly the churn `tilemem-2` measured as 11.13 GiB of
/// glibc per-thread arena free list that is never returned. (The two placement counts
/// are the filer's measurement of the live pyramid; the row-to-allocation arithmetic
/// is this code's own.)
///
/// **What this does NOT change: the byte COUNT.** The payload still moves twice —
/// `Arc<[u8]>` into a buffer, buffer into the Arrow builder — because the writer sorts
/// rows by covering extent and Arrow owns its own contiguous storage. What is gone is
/// the per-row heap object each of those bytes used to land in.
///
/// # The shape
///
/// Three buffers per TILE instead of two allocations per row: the WKB bytes
/// concatenated into one `Vec<u8>`, the tag JSON concatenated into one `String`, and
/// an end offset per row into each. A row is `geo[end[i-1]..end[i]]` — random access,
/// which [`write_tile_parquet_rows`] needs because it sorts rows by covering extent
/// ([`TILE_ROW_ORDER`]) and therefore cannot take a one-shot iterator.
///
/// The buffers survive `clear()`, so the write loop keeps ONE `TileRows` per worker
/// and every tile after the first reuses the capacity of the largest tile that worker
/// has already written. The steady state is zero allocations per row and zero per
/// tile — the same "preallocate and reuse" the scan got in `tilemem-2`.
#[derive(Default)]
pub struct TileRows {
/// Every row's WKB, concatenated.
geo: Vec<u8>,
/// `geo_end[i]` is the END offset of row `i` in [`Self::geo`]; row 0 starts at 0.
geo_end: Vec<usize>,
/// Every row's tag JSON, concatenated. An empty slice is an untagged row and is
/// written as a NULL cell, exactly as the slice-taking form has always done.
tags: String,
/// `tag_end[i]` is the END offset of row `i` in [`Self::tags`].
tag_end: Vec<usize>,
ids: Vec<i64>,
}
impl TileRows {
pub fn new() -> Self {
Self::default()
}
/// Drop the rows, KEEP the capacity — the reuse this type exists for.
pub fn clear(&mut self) {
self.geo.clear();
self.geo_end.clear();
self.tags.clear();
self.tag_end.clear();
self.ids.clear();
}
pub fn len(&self) -> usize {
self.ids.len()
}
pub fn is_empty(&self) -> bool {
self.ids.is_empty()
}
/// Append a row from borrowed parts. Nothing is allocated once the buffers have
/// reached the tile's high-water mark.
pub fn push(&mut self, geom: &[u8], tag: &str, id: i64) {
self.geo.extend_from_slice(geom);
self.close_row(tag, id);
}
/// Append a row whose geometry is ENCODED straight into the flat buffer, so an
/// inline point never gets a 21-byte `Vec` of its own on the way in.
fn push_encoded(&mut self, id: i64, tag: &str, encode: impl FnOnce(&mut Vec<u8>)) {
encode(&mut self.geo);
self.close_row(tag, id);
}
fn close_row(&mut self, tag: &str, id: i64) {
self.geo_end.push(self.geo.len());
self.tags.push_str(tag);
self.tag_end.push(self.tags.len());
self.ids.push(id);
}
#[inline]
fn start(ends: &[usize], i: usize) -> usize {
if i == 0 { 0 } else { ends[i - 1] }
}
/// Row `i`'s WKB. Panics on an out-of-range index, like any slice.
pub fn geom(&self, i: usize) -> &[u8] {
&self.geo[Self::start(&self.geo_end, i)..self.geo_end[i]]
}
/// Row `i`'s tag JSON; empty means "no tags" and is written as NULL.
pub fn tag(&self, i: usize) -> &str {
&self.tags[Self::start(&self.tag_end, i)..self.tag_end[i]]
}
pub fn id(&self, i: usize) -> i64 {
self.ids[i]
}
/// The rows as three owned parallel vectors — the shape the pre-`katana-9` write
/// phase built, kept so the spill round-trip tests can compare against it. Test
/// only: production never materialises this.
#[cfg(test)]
fn parts(&self) -> (Vec<Vec<u8>>, Vec<String>, Vec<i64>) {
(
(0..self.len()).map(|i| self.geom(i).to_vec()).collect(),
(0..self.len()).map(|i| self.tag(i).to_string()).collect(),
self.ids.clone(),
)
}
}
/// Serialise a set of WKB geometries into one small GeoParquet **tile** buffer: a
/// `geometry` (WKB) column, a Utf8 `tags` column (one JSON tag string per geometry,
/// parallel to `geoms` — the monolith's [`crate::tags::serialize_tags`] encoding; an
/// empty entry is written as a null cell), the GeoParquet 1.1 `covering.bbox` struct
/// column ([`crate::spatial`]'s outward-rounded per-row bbox) and the `geo` metadata
/// declaring the covering. One row group (a tile is tiny).
///
/// `tags` must be the same length as `geoms`; pass a slice of empty strings to write an
/// all-null `tags` column (the pre-tags tile shape, still schema-uniform).
///
/// `ids` must be the same length too. It carries the **OSM id** of each geometry — the
/// object's only stable identity across zooms, and the only thing that tells two
/// different ways apart once they are decimated to the same handful of vertices. A
/// downstream renderer keys its GPU cache on it (facett `layer.rs`'s `osm_id`), so a
/// tile without it hands every object the same key: two different way sets hash to the
/// same signature and the renderer never rebakes on zoom. Ids are not optional and there
/// is no "unknown id" value; both source tables declare `id` non-null.
///
/// `recipe` is stamped into the footer under [`TILE_RECIPE_META_KEY`] so the object can
/// be asked, later and on its own, which writer produced it.
pub fn write_tile_parquet(
geoms: &[Vec<u8>],
tags: &[String],
ids: &[i64],
compression: &str,
recipe: &TileRecipe,
) -> anyhow::Result<Vec<u8>> {
anyhow::ensure!(
tags.len() == geoms.len(),
"write_tile_parquet: tags ({}) and geoms ({}) must be parallel",
tags.len(),
geoms.len()
);
anyhow::ensure!(
ids.len() == geoms.len(),
"write_tile_parquet: ids ({}) and geoms ({}) must be parallel",
ids.len(),
geoms.len()
);
let mut rows = TileRows::new();
for i in 0..geoms.len() {
rows.push(&geoms[i], &tags[i], ids[i]);
}
write_tile_parquet_rows(&rows, compression, recipe)
}
/// [`write_tile_parquet`] over a [`TileRows`] — **the ONE implementation** (LAW 5).
/// The slice-taking form above is a wrapper that copies its three parallel vectors
/// into a `TileRows` and calls this; the engine's own write loop builds the
/// `TileRows` directly and never pays for those vectors at all.
pub fn write_tile_parquet_rows(
rows: &TileRows,
compression: &str,
recipe: &TileRecipe,
) -> anyhow::Result<Vec<u8>> {
let n = rows.len();
// Per-row covering bbox, rounded OUTWARD so the stored f32 box always CONTAINS
// the true geometry (never a false prune) — the `spatial_pack` invariant.
let boxes: Vec<Option<crate::spatial::Bbox>> = (0..n).map(|i| wkb_bbox(rows.geom(i))).collect();
// **BIGGEST FIRST — [`TILE_ROW_ORDER`], and the other half of `natt-7`.**
//
// The per-tile ways ladder ([`WayLane`]) decides WHICH features a full tile keeps.
// It does not decide what a reader that cannot afford the whole tile sees, and on
// 2026-08-04 that was the binding constraint on the live map: with Mälaren restored
// to all 2 of its z6 tiles and all 8 of its z9 tiles, korp's own viewport budget
// (`map_tiles.rs`, 20 000 ways shared over 11 covering tiles ⇒ ~1 818 per tile) still
// drew no lake — because it takes rows in FILE ORDER, and Mälaren sat at row 16 775
// of 56 917 in `z6/34/18`, row 16 304 of 33 215 in `z6/35/18` and row 16 337 of
// 56 413 in `z9/280/150`. A tiler that fixes its own cap and leaves the file in
// arrival order has moved the positional cut one process to the right.
//
// So the ROW ORDER is part of the contract: **the first N rows of a tile are the N
// features with the largest covering bbox.** Every reader that truncates — this one,
// korp's viewport budget, a `LIMIT` in a query engine — then truncates detail
// instead of truncating whichever corner of the tile the scan reached first, with no
// change on its side (LAW 5: one writer, and it is this function, the only place a
// tile file is produced).
//
// The key is the bbox extent in DEGREES, which is the same ranking as
// [`way_span_px`]: every row in one file is at one zoom, so degrees and rendered
// pixels differ by a constant factor. A row whose geometry has no bbox (an
// undecodable blob) sorts last — it can contribute nothing to any pane. The sort is
// STABLE, so rows of equal extent keep their arrival order and two runs over the
// same input still produce the same file.
let order: Vec<usize> = {
let mut ix: Vec<usize> = (0..n).collect();
ix.sort_by(|&a, &b| {
let ext = |i: usize| -> f64 {
match &boxes[i] {
Some(bb) => (bb.xmax - bb.xmin).abs().max((bb.ymax - bb.ymin).abs()),
None => f64::NEG_INFINITY,
}
};
ext(b)
.partial_cmp(&ext(a))
.unwrap_or(std::cmp::Ordering::Equal)
});
ix
};
let geom_arr = BinaryArray::from_iter_values(order.iter().map(|&i| rows.geom(i)));
let id_arr = Int64Array::from(order.iter().map(|&i| rows.id(i)).collect::<Vec<_>>());
// A tag JSON per geometry, in the same order; an empty string ⇒ null (no tags),
// so an untagged object reads uniformly whether stored null here or "{}" upstream.
let tags_arr = StringArray::from_iter(order.iter().map(|&i| {
let t = rows.tag(i);
if t.is_empty() { None } else { Some(t) }
}));
let (mut xmin, mut ymin, mut xmax, mut ymax) = (
Vec::with_capacity(n),
Vec::with_capacity(n),
Vec::with_capacity(n),
Vec::with_capacity(n),
);
for &i in &order {
match &boxes[i] {
Some(b) => {
xmin.push(Some(down(b.xmin)));
ymin.push(Some(down(b.ymin)));
xmax.push(Some(up(b.xmax)));
ymax.push(Some(up(b.ymax)));
}
None => {
xmin.push(None);
ymin.push(None);
xmax.push(None);
ymax.push(None);
}
}
}
let leaf_fields = bbox_leaf_fields();
let bbox_arr = StructArray::new(
leaf_fields.clone(),
vec![
Arc::new(Float32Array::from(xmin)) as ArrayRef,
Arc::new(Float32Array::from(ymin)),
Arc::new(Float32Array::from(xmax)),
Arc::new(Float32Array::from(ymax)),
],
None,
);
let geo_json = GeoMeta::new(&["Point", "LineString"])
.with_covering(BBOX_COLUMN)
.to_json();
let mut schema_meta = HashMap::new();
schema_meta.insert(String::from(GEO_KEY), geo_json.clone());
schema_meta.insert(String::from(TILE_RECIPE_META_KEY), recipe.token());
let schema = Arc::new(Schema::new_with_metadata(tile_fields(), schema_meta));
let batch = RecordBatch::try_new(
schema.clone(),
vec![
Arc::new(id_arr) as ArrayRef,
Arc::new(geom_arr),
Arc::new(tags_arr),
Arc::new(bbox_arr),
],
)?;
let props = WriterProperties::builder()
.set_compression(crate::writer::codec(compression))
.set_key_value_metadata(Some(vec![
parquet::file::metadata::KeyValue::new(String::from(GEO_KEY), geo_json),
// The EVIDENCE copy of the recipe (see `TILE_RECIPE_META_KEY`): ~60 bytes in
// the footer of every tile, so "was this object cut by the current writer?"
// is answerable from the object itself and not only from a sidecar that
// describes it.
parquet::file::metadata::KeyValue::new(
String::from(TILE_RECIPE_META_KEY),
recipe.token(),
),
]))
.build();
let mut buf: Vec<u8> = Vec::new();
{
let mut w = ArrowWriter::try_new(&mut buf, schema, Some(props))?;
w.write(&batch)?;
w.close()?;
}
Ok(buf)
}
// ── the tiling engine ───────────────────────────────────────────────────────────
/// Where a tiling run gets its features.
pub enum TileSource<'a> {
/// An already-clipped region GeoParquet directory (`nodes.parquet` /
/// `ways.parquet`) — tile it directly.
Extract(&'a Path),
/// A planet/region PBF (or XML/bz2/gz) plus a region [`Clip`] — run
/// [`crate::convert`] (gatling streaming, clip-at-decode) into a scratch extract
/// THEN tile it. This is the planet-scale path.
Pbf { input: &'a Path, clip: Clip },
}
/// Knobs for a tiling run.
#[derive(Clone, Debug)]
pub struct TileOptions {
pub zooms: Vec<u8>,
pub compression: String,
pub max_tile_points: usize,
pub max_tile_ways: usize,
/// **The region's own bounds — the tiler REFUSES to write a tile outside them.**
///
/// `None` keeps the old faithful-to-the-input behaviour (tile whatever is there),
/// which is right for an ad-hoc extract of unknown extent and WRONG for a named
/// region: see the module header for the measured 97 %-stray `sweden` pyramid a
/// leaking upstream clip produced. Any caller that knows which region it is tiling
/// — korp's `--tile-maps <region>`, and [`TileSource::Pbf`], which derives it from
/// its own [`Clip`] — should set it. Refusals are counted in
/// [`TileStats::refused_tiles`]; the geometry itself is not modified, only its
/// PLACEMENT is bounded, so a way legitimately straddling the region edge still
/// reaches every in-region tile it crosses.
pub region: Option<Bounds>,
/// Scan/write workers. `0` ⇒ one per core (gatling's default).
///
/// The scan used to run on the CALLING thread alone: measured over a full
/// Sweden tiling on 2026-08-03, 99.5–99.7 % of one core — exactly one of 32 —
/// from t=4 s to t=62 s, and only the closing write fanned out (~6.7 cores).
/// It is now row-group-parallel; see [`tile_region`].
pub workers: usize,
/// **Ceiling on the resident tile payload, in bytes.** `0` ⇒ unbounded (hold
/// the whole pyramid, the pre-2026-08-03 behaviour).
///
/// The pyramid used to be built entirely in RAM before a single tile was
/// written: measured 12.21 GB peak for Sweden at z6/9/12, the curve monotone
/// 0.5 → 11.4 GB with nothing on disk yet, and 36.36 GB for z15 alone. Over
/// this budget the biggest tiles are SPILLED to a per-shard scratch file and
/// re-joined when the tile is written, so peak resident payload is a knob and
/// not a function of the region's size.
///
/// Accounted per placement (`geom + tag + overhead`), which OVER-counts the
/// PAYLOAD it bounds, because payloads are `Arc`-shared across the tiles a feature
/// is duplicated into.
///
/// **It does not follow that RSS sits below the budget, and it does not.** Two
/// other terms are resident and neither is payload: the unspillable bookkeeping
/// ([`TileStats::peak_bookkeeping_bytes`], 0.33 GiB on Sweden at z6/9/12) and the
/// allocator's own free list. Measured on oden 2026-08-03, a 4.00 GiB budget on
/// that corpus costs 5.85 GiB of RSS. Ask what the process will hold, not what the
/// budget says — [`TileStats::memory_attribution`] answers it.
pub mem_budget_bytes: u64,
/// **The pixel width one tile is RENDERED at** — the basis of the Douglas-Peucker
/// epsilon, i.e. how much shape this run is allowed to throw away. See
/// [`DEFAULT_TILE_RASTER_PX`] for the measurement that made this a parameter instead
/// of the inline `256` it used to be. It is part of the [`TileRecipe`], so changing it
/// makes existing pyramids read as stale rather than silently mixing two tolerances.
pub tile_raster_px: u32,
/// **Hand the road and rail networks to a network table instead of duplicating them
/// into every tile.** Default `true`.
///
/// A way is written into EVERY tile its bbox overlaps ([`way_tiles`]) — the pyramid
/// is therefore larger than the data it comes from (2.83 GB on disk out of a 1.5 GB
/// source, measured on `sweden` 2026-08-03) and the cost is worst for exactly the
/// features a network table serves best: long lines cross the most tiles. Measured on
/// that pyramid, all 28 974 tiles, every row group: **3 620 322 of 83 800 927 rows
/// are `highway=*`** (z6 72 707 · z9 993 000 · z12 2 554 615) against 2 251 123 in the
/// source, i.e. a 1.61x duplication over three levels — and the factor grows with
/// zoom, not the row count, so z15 is where it hurts.
///
/// The excluded features are not lost: they are in `roads.parquet` / `rails.parquet`,
/// stored once at FULL geometric detail, read through the same covering-bbox seam.
/// A pyramid cut with this on is different DATA from one cut with it off, so it rides
/// in the [`TileRecipe`] — otherwise a server would GET a manifest, see a valid zoom
/// set, and serve a road-bearing pyramid as current (`collauto-6`, again).
pub exclude_networks: bool,
}
/// **Floor** of the auto-scaled resident-payload ceiling: 4 GiB — the constant this
/// default used to be, unconditionally. It stays the floor so no box ever gets a
/// SMALLER budget than it had before [`budget_for_available`] existed; the scaling
/// only ever raises it.
pub const DEFAULT_TILE_MEM_BUDGET: u64 = 4 << 30;
/// **Ceiling** of the auto-scaled budget: 64 GiB. A share of available memory with no
/// absolute cap is a budget that grows without bound as boxes do, and this tree has
/// already paid for that once — an `ldeflate` test binary reached **474,9 GiB RSS** on
/// oden 2026-08-03 and took the machine down in a global OOM. The engine's own numbers
/// say 64 GiB is not a limitation on the region it is asked for: Sweden at z15 wanted
/// 38,36 GiB of payload with the whole ladder in RAM (`budget-sweep.log`, oden
/// 2026-08-03, spilled 0,00 GiB) and the process's true peak RSS at that budget was
/// **14,19 GiB** — measured by `/usr/bin/time`, not by the engine's own books.
pub const MAX_TILE_MEM_BUDGET: u64 = 64 << 30;
/// Denominator of the auto-scaled budget: the tiler claims **one quarter** of
/// `MemAvailable`. Three quarters is not politeness — the payload is the largest term
/// but not the only one (bookkeeping, the allocator's free list, the parquet encoder's
/// per-tile buffers), and this box runs an agent fleet, not one job.
const TILE_MEM_BUDGET_DIVISOR: u64 = 4;
/// **The budget for a box with `avail` bytes of `MemAvailable`** — a quarter of it,
/// clamped into [[`DEFAULT_TILE_MEM_BUDGET`], [`MAX_TILE_MEM_BUDGET`]].
///
/// Split out from [`default_tile_mem_budget`] because a policy that reads `/proc` cannot
/// be tested: the tests below feed it the numbers of boxes that do not exist here.
pub fn budget_for_available(avail: u64) -> u64 {
(avail / TILE_MEM_BUDGET_DIVISOR).clamp(DEFAULT_TILE_MEM_BUDGET, MAX_TILE_MEM_BUDGET)
}
/// **The budget a default [`TileOptions`] carries** — [`budget_for_available`] of the
/// box's `MemAvailable`, unless `OSM_KATANA_TILE_MEM_BUDGET` overrides it (bytes, or a
/// `K`/`M`/`G`/`T` suffix; `0` = unbounded, which is the engine's existing "no budget"
/// value).
///
/// It scales because the old flat 4 GiB was a **policy about a machine**, written once,
/// and on the machine it actually runs on it was plainly wrong. MEASURED on oden
/// 2026-08-04, korp's `sweden` cut ran the 4,00 GiB default with **345 GiB
/// MemAvailable** and was therefore forced to spill **33,06 GiB** at z6/9/12/15 — and
/// **115,27 GiB** once relation geometry joined the scan (`tilebench/z15-AFTER1.log`,
/// z15 alone, write 378,51 s at 3,6 cores). The scan phase spent 358,0 of its 897,5
/// thread-seconds inside spill `pwrite`, 12,5 of 32 threads asleep in the kernel, for a
/// ceiling nothing on that box needed.
///
/// What it is NOT is "unbounded on a big box": the quarter-share and
/// [`MAX_TILE_MEM_BUDGET`] both bind, and a box that is *busy* shrinks the budget on its
/// own, because `MemAvailable` is what is left after everyone else. A planet still does
/// not fit any box, so a big region still spills — just not a country on a 500 GB host.
pub fn default_tile_mem_budget() -> u64 {
let Ok(raw) = std::env::var("OSM_KATANA_TILE_MEM_BUDGET") else {
return budget_for_available(crate::node_store::available_ram_bytes() as u64);
};
match parse_budget_env(&raw) {
Some(n) => n,
None => {
// A budget that cannot be parsed must NOT fall through as "unbounded" — that
// is the one wrong answer that looks like it worked until the box OOMs.
let fallback = budget_for_available(crate::node_store::available_ram_bytes() as u64);
eprintln!(
"osm-katana/tiles: OSM_KATANA_TILE_MEM_BUDGET={raw:?} is not a byte count \
(optionally suffixed K/M/G/T) — keeping the {:.2} GiB default",
fallback as f64 / (1u64 << 30) as f64
);
fallback
}
}
}
/// `OSM_KATANA_TILE_MEM_BUDGET`'s grammar, split out from the `std::env::var` read so a
/// test can exercise it. A test that sets the variable instead would be a test that
/// fails whenever another test in the same process runs beside it.
///
/// `None` = "not a byte count"; the caller decides what to do about that, and the one
/// answer it must not choose is `0`, which this engine reads as UNBOUNDED.
fn parse_budget_env(raw: &str) -> Option<u64> {
let raw = raw.trim();
let (digits, mult) = match raw.chars().last() {
Some('K') | Some('k') => (&raw[..raw.len() - 1], 1u64 << 10),
Some('M') | Some('m') => (&raw[..raw.len() - 1], 1u64 << 20),
Some('G') | Some('g') => (&raw[..raw.len() - 1], 1u64 << 30),
Some('T') | Some('t') => (&raw[..raw.len() - 1], 1u64 << 40),
_ => (raw, 1u64),
};
digits
.trim()
.parse::<u64>()
.ok()
.map(|n| n.saturating_mul(mult))
}
impl Default for TileOptions {
fn default() -> Self {
Self {
zooms: DEFAULT_TILE_ZOOMS.to_vec(),
compression: String::from("zstd"),
max_tile_points: DEFAULT_MAX_TILE_POINTS,
max_tile_ways: DEFAULT_MAX_TILE_WAYS,
region: None,
workers: 0,
mem_budget_bytes: default_tile_mem_budget(),
tile_raster_px: DEFAULT_TILE_RASTER_PX,
exclude_networks: true,
}
}
}
impl TileOptions {
/// The [`TileRecipe`] a run with these options implements.
pub fn recipe(&self) -> TileRecipe {
let mut r = TileRecipe::for_zooms(&self.zooms, self.tile_raster_px);
if self.exclude_networks {
r.excluded = crate::network::tiled_out_selector();
}
r
}
}
/// Per-zoom summary of a tiling run.
#[derive(Clone, Debug, Default)]
pub struct ZoomTileStats {
pub zoom: u8,
pub tiles: usize,
pub points: usize,
pub ways: usize,
pub total_bytes: u64,
pub min_bytes: u64,
pub max_bytes: u64,
}
impl TileStats {
/// **One line naming every byte the process held at the payload high-water mark,
/// and which of them the budget could see.**
///
/// Exists because the branch that introduced the budget shipped with a 4.00 GiB
/// accounted payload against a 15.20 GiB process (oden, 2026-08-03, `sweden` at
/// z6/9/12) and nothing in the program could say what the other 11.2 GiB was. A
/// budget whose own report cannot close against RSS is a budget on a subset.
pub fn memory_attribution(&self) -> String {
let g = |b: u64| b as f64 / (1u64 << 30) as f64;
let books = self.peak_resident_bytes + self.peak_bookkeeping_bytes;
// Deliberately NOT written as a sum. `arena - uordblks` is free list measured
// in ADDRESS SPACE, and an arena keeps address space it has already madvised
// back to the kernel — so it is an upper bound on the resident part and adding
// it to RSS would be arithmetic on two different quantities. What the trim
// returns is the part that provably WAS resident and provably was not data.
format!(
"MEMORY at the scan's high-water mark — RSS {:.2} GiB (peak over the run {:.2}). \
Allocator: {:.2} GiB live, {:.2} GiB of arena ⇒ {:.2} GiB free list (address \
space, an UPPER bound on the resident part); malloc_trim(0) handed {:.2} GiB of \
RSS back on the spot, and that part was provably free list and not data. \
Engine accounts {:.2} GiB of the live heap (payload {:.2} + bookkeeping {:.2}), \
unaccounted {:.2} GiB.",
g(self.scan_rss_bytes),
g(self.peak_rss_bytes),
g(self.scan_live_heap_bytes),
g(self.scan_heap_from_kernel_bytes),
g(self
.scan_heap_from_kernel_bytes
.saturating_sub(self.scan_live_heap_bytes)),
g(self.trim_reclaimed_bytes),
g(books),
g(self.peak_resident_bytes),
g(self.peak_bookkeeping_bytes),
g(self.scan_live_heap_bytes.saturating_sub(books)),
)
}
}
impl ZoomTileStats {
pub fn mean_bytes(&self) -> u64 {
if self.tiles == 0 {
0
} else {
self.total_bytes / self.tiles as u64
}
}
}
/// **The books of the tile scan, for ONE source kind — every row the file held, in
/// exactly one column.**
///
/// # The defect this exists to make impossible (`K15`, the 1 523-way gap)
///
/// The 2026-08-27 Sweden cut produced 9 325 142 ways in pass 2. The tiler reported
/// `ways scanned: 6 991 961` and `2 331 658 feature(s) handed to a network table`.
/// 6 991 961 + 2 331 658 = 9 323 619 — **1 523 ways short of what pass 2 wrote, and no
/// counter in the run knew about them.** The run's own summary said `UNDECODABLE
/// blobs: 0`, which reads as "nothing was dropped".
///
/// They went out through three `continue`s in the scan's inner loop, every one of them
/// BEFORE the `local_n += 1` that bumps the scanned count:
///
/// * `if geom.is_null(i) { continue; }` — a NULL geometry cell. The comment on the
/// row-group prune above it admits the consequence in as many words: "no placement,
/// no count, no warning".
/// * `let Some(bbox) = shape.bbox() else { continue; }` — a row that DECODED (so
/// `undecodable` never sees it) into a shape with no extent.
/// * `let Some((lon, lat)) = shape.vertices().next() else { continue; }` — the same
/// for a point source.
///
/// Neither `undecodable`, nor `collapsed_areas`, nor `refused_features` could see any
/// of them, and each `continue` is individually defensible — which is exactly why the
/// class survived. The repair is not a fourth counter; it is an IDENTITY that has to
/// close, so a class nobody enumerated shows up as a non-zero
/// [`unaccounted`](Self::unaccounted) instead of as a number an operator has to
/// subtract by hand.
///
/// Every field is a count of ROWS of one source table, and the identity is
/// [`Self::balances`].
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct ScanLedger {
/// `"ways"` / `"nodes"` / `"relations"` — the source table this column is about.
pub kind: &'static str,
/// **Rows the parquet footers say the source files hold.** Read from the row-group
/// metadata, not counted while decoding, so it is the number to reconcile the
/// PRODUCER against: for `ways.parquet` it is pass 2's own way count.
pub file_rows: usize,
/// Rows in row groups the all-NULL-geometry prune dropped without decoding. Real
/// rows of the file, deliberately never read — so they belong in the books.
pub pruned_all_null_groups: usize,
/// Rows actually handed to the decode loop (`geom.len()`, summed).
pub rows_read: usize,
/// Read, and the `geometry` cell was NULL. Previously invisible.
pub null_geometry: usize,
/// Read, non-NULL, and the ring-preserving WKB decoder refused it.
pub undecodable: usize,
/// Read and excluded because a network table carries it — not a loss.
pub handed_to_a_network: usize,
/// **Decoded fine and still yielded no geometry to place**: `bbox()` was `None` for
/// an extent-bearing source, or `vertices().next()` was `None` for a point source.
/// Previously invisible, and the larger half of the 1 523.
pub no_geometry_extent: usize,
/// **Read, decoded, and carrying NO TAGS — a bare geometry vertex, not a feature**
/// (`K16`). Only ever non-zero for `"nodes"`.
///
/// In OpenStreetMap the overwhelming majority of nodes exist to give a way its
/// shape and carry no tags of their own; the ways that use them are already in the
/// pyramid (or in a network table), so the vertex adds nothing a reader can see and
/// nothing a classifier can name. MEASURED whole-country from this run's OWN ledger
/// on the 2026-08-31 Sweden cut: **101 081 991 of 103 488 583 nodes — 97.7 % —
/// carried no tags at all**, and the books close to `UNACCOUNTED 0` over them.
/// (An earlier note here quoted "107 299 of 188 112 rows (57.0 %) over all nineteen
/// z6 tiles"; that census flattened the pyramid's paths when copying, so
/// `z6/33/15.parquet` and `z6/34/15.parquet` overwrote each other and only 7 of 19
/// tiles were read. A ledger cannot be sampled wrong.) `map_networks`' own header had already
/// measured the same thing from the other side ("removing ways from the [6,9,12]
/// pyramid shrank it by only 5.54 % of bytes … **because nodes dominate at those
/// zooms**"); this is that sentence acted on.
///
/// It is a LEDGER COLUMN and not a silent `continue` for the reason the whole struct
/// exists: a row that leaves has to leave through a name.
pub untagged_nodes: usize,
/// Rows that reached at least one placement — the old `ways/nodes/relations
/// scanned` figure.
pub placed: usize,
}
impl ScanLedger {
/// **Rows of the file that no column above claims** — zero when the books close.
///
/// Signed on purpose: a negative value means a row was counted twice, which is a
/// different bug from a row nobody counted, and a `usize` would print it as
/// 18 446 744 073 709 551 615.
#[allow(clippy::cast_possible_wrap)]
pub fn unaccounted(&self) -> i64 {
self.file_rows as i64
- (self.pruned_all_null_groups as i64
+ self.null_geometry as i64
+ self.undecodable as i64
+ self.handed_to_a_network as i64
+ self.no_geometry_extent as i64
+ self.untagged_nodes as i64
+ self.placed as i64)
}
/// Do the books close? [`Self::unaccounted`] `== 0`.
pub fn balances(&self) -> bool {
self.unaccounted() == 0
}
/// The one line an operator reads — every column named, and the residual last.
pub fn line(&self) -> String {
format!(
"{}: file {} = placed {} + handed to a network {} + NULL geometry {} + \
undecodable {} + no geometry extent {} + untagged nodes {} + pruned \
all-NULL row groups {} · rows read {} · UNACCOUNTED {}",
self.kind,
self.file_rows,
self.placed,
self.handed_to_a_network,
self.null_geometry,
self.undecodable,
self.no_geometry_extent,
self.untagged_nodes,
self.pruned_all_null_groups,
self.rows_read,
self.unaccounted(),
)
}
}
/// Result of [`tile_region`].
#[derive(Clone, Debug, Default)]
pub struct TileStats {
/// Features handed to a network table instead of being tiled
/// ([`TileOptions::exclude_networks`]). Zero when the knob is off.
///
/// The SUM of [`Self::network_features_by_kind`]; kept because every existing
/// reader asks for the total.
pub network_features: usize,
/// **The scan's books, per source kind** — `[ways, nodes, relations]`, indexed by
/// [`SrcKind::idx`]. See [`ScanLedger`]: this is where the `K15` 1 523-way gap
/// became a printed number instead of a subtraction an operator had to do.
///
/// A caller that reports a pyramid MUST read
/// [`ScanLedger::unaccounted`]/[`ScanLedger::balances`] — a run whose books do not
/// close has dropped source rows into a class nobody enumerated.
pub scan_ledger: [ScanLedger; 3],
/// **The same exclusion, split by the SOURCE TABLE the row came from** —
/// `[ways, nodes, relations]`, indexed by [`SrcKind::idx`].
///
/// # Why the aggregate could not be trusted (`granska-1`)
///
/// The exclusion has now been source-blind twice, and BOTH times the aggregate
/// counter reported a healthy non-zero number while a whole source was being
/// deleted with nothing carrying it: 567 179 nodes in the first instance
/// (`a7e9cd3`), 683 assembled relation multipolygons in the second (`9b6fc83`) —
/// and 683 relations disappearing into ~2.27 M ways and rails is a 0.03 % move in
/// a single `AtomicUsize`. The module's own doc line said "an exclusion nobody
/// counts is indistinguishable from a predicate that never fired"; one counter
/// over three sources makes an exclusion that took the WRONG source
/// indistinguishable from one that took the right one, which is the same blindness
/// one level up.
///
/// Split, the invariant becomes assertable rather than narrated:
/// **`network_features_by_kind[SrcKind::Relation.idx()]` is 0 by construction**,
/// because [`SrcKind::network_source`] returns `None` for a relation and no
/// network table has ever been cut from a relation table. A non-zero there is the
/// third instance of the class, caught by the run that causes it.
pub network_features_by_kind: [usize; 3],
pub zooms: Vec<ZoomTileStats>,
/// The `out_dir/tiles` directory the objects were written under.
pub tiles_dir: PathBuf,
/// The zoom levels that produced at least one tile (for the manifest).
pub produced_zooms: Vec<u8>,
/// **The relative key of the tile this run wrote LAST** — the lexicographically
/// greatest `(x, y)` at the FINEST zoom that produced anything, e.g.
/// `tiles/z15/18584/9377.parquet`. `None` only when nothing was tiled.
///
/// It exists so a reader can probe the END of a run instead of its beginning.
/// A pyramid is written coarse-to-fine, so the coarsest zoom is complete long
/// before the run is, and a probe there cannot tell a finished pyramid from one
/// interrupted in its deepest zoom — the `katana-probe-1` defect, measured live
/// on oden 2026-08-05 as 34 footerless tiles under a store the recipe probe
/// called `Current`.
///
/// Carried into the manifest by [`manifest_json`] so the check costs one GET and
/// no LIST at all — cheaper than the coarsest-zoom LIST it replaces.
pub deepest_tile: Option<String>,
/// **How many `(zoom, x, y)` placements [`TileOptions::region`] refused** — i.e.
/// how many tiles this run would have written OUTSIDE the region. Zero on a clean
/// extract; a large number means the upstream clip leaked and the pyramid would
/// have been scattered. Always zero when `region` is `None` (nothing to refuse
/// against), which is why a caller that knows its region must set it.
pub refused_tiles: usize,
/// **`(zoom, ways)` the [`MAX_WAY_TILE_FANOUT`] cap collapsed to a single centroid
/// tile at that zoom** — geometry that is absent from every tile it crosses but one.
///
/// The cap is a fixed count of tiles and a tile covers 4× less ground per zoom step,
/// so the ground area it permits is `≈ 620 × 620 km` at z12 and `≈ 40 × 40 km` at
/// z15. MEASURED on Sweden 2026-08-03 in one `[6,9,12,15]` run: 3 ways at z12, 227
/// at z15, both 0.00 % of 9 203 168 — small, because OSM splits long features into
/// segments. A count at one zoom still says nothing about the next, which is why
/// this is a per-zoom count and not a boolean.
pub fanout_capped_ways: Vec<(u8, usize)>,
/// **Way placements the [`WayLane`] ladder refused, `[zoom index][lane]`**, parallel
/// to [`TileOptions::zooms`].
///
/// The cap this replaces reported nothing at all: a tile that dropped a lake and a
/// tile that dropped nothing produced identical run output, which is why `natt-7` had
/// to be found by reading tile files off the live pyramid instead of by reading a
/// number the tiler already knew. Three counts and not one, because they mean
/// opposite things — refused [`WayLane::Dust`] is the ladder WORKING (sub-pixel
/// clutter making room), while a non-zero [`WayLane::Dominant`] is the ladder
/// degenerating back into a positional cut and the one figure that must be looked at.
pub way_refused: Vec<[usize; 3]>,
/// How many source features (ways + nodes) contributed at least one refused
/// placement — the count of foreign objects the extract actually held.
pub refused_features: usize,
/// Wall seconds of the SCAN phase (parquet → placements → shards).
pub scan_wall_s: f64,
/// Average cores held over the scan, from the same `/proc/self/stat` counter
/// `phase_log` publishes as `cpu_cores`. The pre-2026-08-03 scan reads ~1.0.
pub scan_cpu_cores: f64,
/// Wall seconds of the WRITE phase (encode + one file per tile).
pub write_wall_s: f64,
/// Average cores held over the write.
pub write_cpu_cores: f64,
/// **High-water mark of the accounted resident tile payload**, in bytes — the
/// quantity [`TileOptions::mem_budget_bytes`] bounds.
///
/// Not RSS, and deliberately an UPPER bound on three counts: it excludes the
/// parquet decoder's own buffers and the scan workers' staging (both real RSS,
/// neither the pyramid), it charges a geometry to every tile it is duplicated
/// into although the `Arc` is shared, and it is the SUM of each shard's own peak,
/// which the shards need not have reached at the same instant. Read it as "the
/// pyramid never held more than this", never as a memory measurement — the
/// bench samples RSS for that.
pub peak_resident_bytes: u64,
/// Payload bytes written to (and read back from) the spill scratch. `0` ⇒ the
/// whole pyramid fitted the budget and nothing left RAM before its tile file.
pub spilled_bytes: u64,
/// **Peak resident bytes a spill cannot free** — the per-tile [`PxSet`] dedup
/// sets, the spilled-run indexes and the shards' `HashMap` tables, summed over
/// shards. See [`bookkeeping_bytes`].
///
/// This is the engine's FLOOR: `mem_budget_bytes = 0` would not remove one byte of
/// it, because every byte of it is what makes a spilled tile still correct.
pub peak_bookkeeping_bytes: u64,
/// **Peak RSS of the whole process across this run**, sampled at
/// [`crate::phase_log::RSS_SAMPLE`]. The quantity a memory gate must actually
/// bound — [`Self::peak_resident_bytes`] is a subset of it and always was.
pub peak_rss_bytes: u64,
/// RSS at the END of the scan, i.e. at the payload high-water mark. The instant
/// the three numbers below describe.
pub scan_rss_bytes: u64,
/// Bytes the allocator has handed to LIVE allocations at that instant
/// (`mallinfo2`). `peak_resident_bytes + peak_bookkeeping_bytes` should approach
/// this; whatever is left is heap the engine holds and does not account.
pub scan_live_heap_bytes: u64,
/// Bytes the allocator has taken from the KERNEL and not returned, at that
/// instant. `scan_heap_from_kernel_bytes - scan_live_heap_bytes` is free list.
pub scan_heap_from_kernel_bytes: u64,
/// RSS actually reclaimed by a `malloc_trim(0)` at that instant — the part of the
/// free list the allocator could give back once asked. See
/// [`crate::phase_log::trim_malloc`].
pub trim_reclaimed_bytes: u64,
/// **The [`TileRecipe::token`] THIS run stamped into its tiles.** Carried out of the
/// engine (rather than re-derived by the caller from a default) so the manifest can
/// only ever claim the recipe the objects beside it were actually written with.
pub recipe: String,
}
/// One accumulating tile: sub-pixel-deduped points + thinned ways, capped.
///
/// Payloads are `Arc`-shared, never cloned per placement: a way duplicated into
/// k tiles of one zoom holds k pointers to ONE simplified WKB, and one feature's
/// tag JSON is one allocation however many tiles and zooms it reaches. The old
/// `Vec<u8>` / `String` clone per placement paid the fanout factor in bytes.
///
/// `*_segs` are runs already pushed out to the owning shard's spill file; the
/// `n_*` totals count resident AND spilled, so neither the per-tile cap nor the
/// sub-pixel dedup resets when a tile is spilled.
#[derive(Default)]
struct TileAccum {
seen_px: PxSet,
points: Vec<Payload>,
ways: Vec<Payload>,
point_segs: Vec<Seg>,
way_segs: Vec<Seg>,
n_points: usize,
n_ways: usize,
/// Accounted resident payload bytes of this tile.
bytes: u64,
}
/// Bytes of one tile's flat sub-pixel bitmap: 65 536 pixels, one bit each.
///
/// This is the WHOLE key space of a `px` key, so it is also the most any correct
/// dedup for one tile can ever need.
const PX_DENSE_BYTES: usize = (NODE_DEDUP_GRID_PX as usize * NODE_DEDUP_GRID_PX as usize) / 8;
/// Distinct pixels a tile keeps in the sparse tier before it becomes a bitmap.
///
/// At 2 bytes each the sparse tier tops out at 4 KiB — half the bitmap — so promotion
/// can at most double a tile's dedup state, never step it up by an order of magnitude,
/// and the linear scan the sparse tier costs is bounded by that same 4 KiB.
const PX_SPARSE_MAX: usize = 2048;
/// **The sub-pixel grid a NODE is deduped on — 256x256 per tile.**
///
/// This is NOT [`DEFAULT_TILE_RASTER_PX`], and the two being eight times apart is a
/// real difference the recipe used to hide. The way side simplifies against
/// `tile_pixel_tol(z, opts.tile_raster_px)` at **2048**, and its doc argues the whole
/// case: *"256 ... is not the size anything in this stack renders at: facett draws one
/// tile across the map viewport, ~1920 px wide. A `256`-based epsilon therefore permits
/// a deviation of 1 tile pixel = 7.5 screen pixels."* The point side never got that fix.
/// Its dedup key is which of one tile's **256x256** sub-pixels the node fell in, so
/// **two POIs up to 7.5 screen pixels apart collapse to one** — on exactly the screen
/// width the way-side argument uses.
///
/// Named and STAMPED (`dedup=256` in [`TileRecipe::token`]) rather than riding unnamed
/// on the other constant's name. `raster_px` is already a recipe axis, so raising it
/// re-cuts a planet and the node resolution does not move a millimetre; the token said
/// `raster=2048` while the point path implemented 256, and nothing in the fleet could
/// see the difference because only one of the two had a name.
///
/// **Not yet the full fix**, and this constant says so out loud. Deriving the key from
/// `tile_raster_px` bursts the `u16` key and the 8 KiB bitmap: at 2048 the key space is
/// 4 Mi bits = 512 KiB per saturated tile, which is precisely the `tilemem-1` budget
/// [`PxSet`] exists to hold. That is a change to [`PxSet`]'s tiers, not a constant edit.
/// This step makes the two *visible* as different instead of one silently wearing the
/// other's name.
///
/// It is also the slippy-tile convention: a tile is 256 units wide at every zoom, which
/// is why [`global_pixel`] scales by it and the tile address is the key shifted right by
/// [`NODE_DEDUP_SHIFT`]. Changing it changes both, together, from here.
pub const NODE_DEDUP_GRID_PX: u32 = 256;
/// **Does this row's `tags` cell name a FEATURE?** — the test
/// [`ScanLedger::untagged_nodes`] is counted by.
///
/// The `tags` column is the osm2geoparquet Utf8 JSON object every reader on both sides
/// parses (korp's `map_paint::parse_tags`, the label pass, the classifier). Three
/// spellings mean "this row carries nothing": the cell is NULL, it is empty, or it is the
/// empty object. All three occur in a real cut — `nodes.parquet` writes `{}` for a bare
/// vertex and the monolith path has left the cell null — so testing only one of them
/// would let the other two through and report a fix that measured as nearly no change.
///
/// It is deliberately a SPELLING test and not a parse: this runs once per row of a
/// hundred-million-row scan, and `serde_json` on this exact column was 55.9 % of a tile
/// read's allocations (korp `map_networks`, 2026-08-04). A cell that is neither empty nor
/// `{}` is treated as a feature without being parsed; the classifier downstream is what
/// decides what KIND of feature it is.
#[must_use]
pub fn tag_is_a_feature(tag: Option<&str>) -> bool {
match tag {
None => false,
Some(t) => {
let t = t.trim();
!(t.is_empty() || t == "{}")
}
}
}
/// `log2(NODE_DEDUP_GRID_PX)` — global pixel to tile address.
const NODE_DEDUP_SHIFT: u32 = NODE_DEDUP_GRID_PX.trailing_zeros();
/// Global pixel to sub-tile pixel.
const NODE_DEDUP_MASK: u64 = NODE_DEDUP_GRID_PX as u64 - 1;
// The `px` key is a `u16` and the dense tier is its whole key space as a bitmap. A grid
// past 256 silently wraps two different pixels onto one key, which is a dedup that
// deletes map. Refused at COMPILE time rather than by a test, because the wrap has no
// runtime symptom to assert on.
const _: () = assert!(
NODE_DEDUP_GRID_PX.is_power_of_two()
&& (NODE_DEDUP_GRID_PX as u64) * (NODE_DEDUP_GRID_PX as u64) <= u16::MAX as u64 + 1,
"NODE_DEDUP_GRID_PX must be a power of two whose square fits a u16 px key",
);
/// **Per-tile sub-pixel dedup membership, bounded by construction.**
///
/// The key is `px = (gx & MASK) << SHIFT | (gy & MASK)` for
/// [`NODE_DEDUP_GRID_PX`] = 256: which of one tile's 256×256 sub-pixels a node fell in.
/// **That grid is EIGHT TIMES coarser than the way side's
/// [`DEFAULT_TILE_RASTER_PX`]** — see [`NODE_DEDUP_GRID_PX`] for what it costs and why
/// closing it is not a constant edit. The whole key space is therefore 65 536 bits =
/// [`PX_DENSE_BYTES`] = 8 KiB, and no correct dedup for one tile needs more.
///
/// A `HashSet<u16>` — what this replaces — needs more, and that was `tilemem-1`. It
/// grows by doubling with the number of DISTINCT pixels a tile has seen and never
/// shrinks (not on spill, not on eviction, because the dedup has to outlive both); at
/// the per-tile cap ([`TileOptions::max_tile_points`], 40 000) it holds 65 536 buckets
/// × (2 + 1) bytes = **192 KiB to answer a question that costs 8 KiB to answer
/// exactly**. Since this is the FLOOR ([`bookkeeping_bytes`]) — the residency a spill
/// cannot free — that excess is multiplied by the tile count, not bounded by the
/// budget. z15 has ~64× z12's tiles.
///
/// Two tiers, because the z15 direction and the z12 direction fail differently:
/// * `Sparse` — an unsorted `Vec<u16>`, linearly scanned. 2 bytes per distinct pixel,
/// cheaper than the hash table at every size. This is the tier 1.8 M thin z15 tiles
/// live in, where a flat 8 KiB each would be a 14 GiB floor of its own.
/// * `Dense` — the flat 8 KiB bitmap, entered once past [`PX_SPARSE_MAX`] and never
/// left. O(1) from there, and it is the cap: **this is the constant the guard
/// `per_tile_dedup_floor_is_capped_by_the_key_space` asserts.**
enum PxSet {
Sparse(Vec<u16>),
Dense(Box<[u64; PX_DENSE_BYTES / 8]>),
}
impl Default for PxSet {
fn default() -> Self {
// No allocation for a tile that never sees a node — and at z15 most tiles are
// thin, so the empty case is the common case.
PxSet::Sparse(Vec::new())
}
}
impl PxSet {
/// Insert `px`, returning `true` if it was NOT already present — deliberately the
/// same contract as `HashSet::insert`, so the pyramid this decides is byte-identical
/// to the one the hash set decided.
#[inline]
fn insert(&mut self, px: u16) -> bool {
match self {
PxSet::Sparse(v) => {
if v.contains(&px) {
return false;
}
if v.len() >= PX_SPARSE_MAX {
let mut bits = Box::new([0u64; PX_DENSE_BYTES / 8]);
for &p in v.iter() {
bits[usize::from(p >> 6)] |= 1u64 << (p & 63);
}
bits[usize::from(px >> 6)] |= 1u64 << (px & 63);
*self = PxSet::Dense(bits);
return true;
}
v.push(px);
true
}
PxSet::Dense(bits) => {
let w = usize::from(px >> 6);
let b = 1u64 << (px & 63);
let had = bits[w] & b != 0;
bits[w] |= b;
!had
}
}
}
/// Heap bytes this set holds — the term [`bookkeeping_bytes`] charges to the floor.
/// Capped at [`PX_DENSE_BYTES`] whatever the tile contains; that cap is the fix.
#[inline]
fn heap_bytes(&self) -> u64 {
match self {
PxSet::Sparse(v) => (v.capacity() * std::mem::size_of::<u16>()) as u64,
PxSet::Dense(_) => PX_DENSE_BYTES as u64,
}
}
}
/// A spilled run inside a shard's scratch file: `(offset, byte_len, records)`.
type Seg = (u64, u64, u32);
/// `(zoom index, x, y)` — a tile's identity while it accumulates. The zoom INDEX
/// (not the zoom) so the write phase can bucket by `opts.zooms` position directly.
type TileId = (u8, u32, u32);
/// Which shard owns a tile. **Sharding is on the TILE KEY, never per worker**: a
/// worker-private accumulator merged at the end would multiply the resident set by
/// the worker count — 12.21 GB × 32 = 390 GB on a 499 GB box — and the merge would
/// have to combine two halves of the same tile. Keyed this way the shard sets are
/// disjoint, no tile ever needs merging, and total resident memory is what one
/// accumulator held before.
///
/// Mixed (splitmix64 finaliser) rather than taken raw: adjacent tiles are the norm,
/// and `x % n` would hand a whole tile column to one shard.
#[inline]
fn shard_of(t: TileId, n: usize) -> usize {
let mut h = (u64::from(t.1) << 33) ^ (u64::from(t.2) << 9) ^ u64::from(t.0);
h = h.wrapping_mul(0x9E37_79B9_7F4A_7C15);
h ^= h >> 29;
h = h.wrapping_mul(0xBF58_476D_1CE4_E5B9);
h ^= h >> 32;
(h % n as u64) as usize
}
/// Bucket count of a `hashbrown` table (which is what `std`'s `HashMap`/`HashSet`
/// are) that reports `cap` as its capacity — the inverse of hashbrown's own
/// `capacity_to_buckets`, whose rule is "buckets is a power of two and capacity is
/// 7/8 of it" above 8, and a fixed 4 or 8 below.
#[inline]
fn table_buckets(cap: usize) -> usize {
if cap == 0 {
0
} else if cap < 4 {
4
} else if cap < 8 {
8
} else {
(cap * 8 / 7).next_power_of_two()
}
}
/// Heap bytes a `hashbrown` table of `cap` capacity holds for entries of type `T`:
/// one `T` slot plus one control byte per bucket.
#[inline]
fn table_bytes<T>(cap: usize) -> u64 {
(table_buckets(cap) * (std::mem::size_of::<T>() + 1)) as u64
}
/// **The resident bytes of one tile that the payload budget does NOT bound**, and
/// cannot: its bookkeeping.
///
/// A tile's `seen_px` dedup set, its `HashMap` slot and its spilled-run index are
/// what make spilling *lossless* — a spilled tile must still refuse a duplicate pixel
/// and must still know where its bytes went — so they are precisely the part that
/// survives a spill. [`Shard::spill_down`] drives `bytes` to zero and leaves every one
/// of these standing.
///
/// This is therefore the FLOOR of the engine: the residency a budget of zero would
/// still have. Counting it is the difference between a budget that bounds the process
/// and one that bounds a subset of it and lets the rest run.
///
/// Disjoint from [`placement_bytes`] by construction: the `points`/`ways` vectors are
/// `shrink_to_fit`-ed by [`spill_run`], so their storage is payload and is charged
/// there; what is left here is only what a spill cannot free. The owning shard adds
/// its `HashMap` slot on top ([`Shard::book`]).
#[inline]
fn bookkeeping_bytes(acc: &TileAccum) -> u64 {
acc.seen_px.heap_bytes()
+ (acc.point_segs.capacity() * std::mem::size_of::<Seg>()) as u64
+ (acc.way_segs.capacity() * std::mem::size_of::<Seg>()) as u64
}
/// Accounted bytes of one placement: the payload plus the `Vec` slot and `Arc`
/// headers it occupies. Deliberately charges the geometry to EVERY tile it is
/// duplicated into even though the `Arc` is shared, so the budget errs toward
/// spilling early — the residency it bounds is then an upper bound on the truth.
#[inline]
fn placement_bytes(p: &Payload) -> u64 {
let g = match &p.0 {
// A point is 24 bytes inline; charged as the 21-byte WKB it becomes on
// disk so the budget means the same thing however the geometry is held.
TileGeom::Point(..) => 21,
TileGeom::Line(b) | TileGeom::Poly(b) => b.len(),
};
(g + p.1.as_ref().map_or(0, |t| t.len()) + 48 + 8) as u64
}
/// The geometry of one accumulating tile row.
///
/// **A point is held INLINE, not on the heap.** Sweden's pyramid is 70.0 M point
/// placements against 13.8 M way placements, and an `Arc<[u8]>` per point meant
/// one heap allocation per node per zoom for a *21-byte* WKB that
/// [`encode_wkb_point`] can rebuild from the two coordinates in nanoseconds. Across 32
/// scan threads that is ~200 M short-lived small allocations churned through
/// glibc's per-thread arenas — which do not return the memory — and it showed up
/// as RSS that had nothing to do with the payload the budget accounts. Only a
/// polyline needs the heap, and there the `Arc` is shared across every tile the
/// way is duplicated into.
#[derive(Clone)]
enum TileGeom {
Point(f64, f64),
Line(Arc<[u8]>),
/// A WKB **MultiPolygon** (type 6) — rings intact, holes intact.
///
/// # Why this variant had to exist before relations were worth reading
///
/// Until it did, `tile_fields`'s `geometry` column held only types 1 and 2:
/// every areal feature in the pyramid was a `LineString`. A source polygon's
/// rings were concatenated by the old flat decoder, so a lake with an island
/// arrived as ONE run with a false seam from the outer ring's last vertex to
/// the island's first — and Douglas-Peucker then ran ACROSS that seam,
/// simplifying a chord that is not part of the geometry. facett's hole
/// punching was unreachable from any tile osm-katana could produce.
///
/// So assembling relation multipolygons without this is not half a fix, it is
/// a worse map: the relation path would deliver correct MultiPolygon WKB into
/// a writer that flattens it into a wrong LineString. The two land together.
Poly(Arc<[u8]>),
}
impl TileGeom {
/// The WKB this row is written (and spilled) as, APPENDED to `out` — the ONE
/// encoder, so an inline point and a heap polyline can never disagree about
/// their bytes. `katana-9`: the write phase concatenates a whole tile into one
/// flat buffer ([`TileRows`]), so the row's bytes must be able to land there
/// without a `Vec` of their own on the way.
#[inline]
fn write_wkb(&self, out: &mut Vec<u8>) {
match self {
TileGeom::Point(lon, lat) => {
push_wkb_point(out, *lon, *lat);
}
TileGeom::Line(b) | TileGeom::Poly(b) => out.extend_from_slice(b),
}
}
/// [`Self::write_wkb`] into a fresh `Vec` — the allocating wrapper, kept for the
/// spill serialiser and the tests that want owned bytes.
#[inline]
fn to_wkb(&self) -> Vec<u8> {
let mut b = Vec::new();
self.write_wkb(&mut b);
b
}
/// The variant names, in declaration order — the [`TileRecipe`] axis that says
/// **what a tile may CONTAIN**. Derived rather than written out, so adding a
/// geometry class moves the recipe (and re-cuts every pyramid) with no edit to
/// the recipe. A pyramid cut before `Poly` existed holds LineStrings where a
/// current one holds MultiPolygons; that is different DATA under an identical
/// schema, which is exactly the case `format` in the manifest could not see.
const CLASSES: &'static str = "Point,Line,Poly";
}
/// One tile row: its geometry, its tag JSON and its **OSM id**. `None` tags is the
/// common case — Sweden's 102.5 M nodes carry ~1 byte of tag each, i.e. almost all
/// are untagged, and an `Arc<str>` built from `""` is still an allocation.
///
/// The id is a plain `i64` and not shared: it is 8 bytes, smaller than the `Arc`
/// header that sharing it would cost, and it is the one field that must DIFFER per
/// object — a renderer keys its GPU cache on it (facett `layer.rs`'s `osm_id`), so a
/// tile that ships a constant here collapses every cache signature onto one key and
/// nothing rebakes on zoom.
type Payload = (TileGeom, Option<Arc<str>>, i64);
/// One `(tile, payload)` routed from a scan worker to its shard.
struct Placement {
tile: TileId,
/// `Some(px)` for a node — the sub-pixel dedup key, applied under the shard
/// lock so the dedup stays exact however the scan is fanned out. `None` ⇒ way.
px: Option<u16>,
/// **The way's bbox span in rendered tile pixels at this zoom** ([`way_span_px`]),
/// i.e. the rank the per-tile ways cap keeps by. Computed at placement time because
/// the bbox is in hand there and the geometry here is already simplified; recovering
/// it in `absorb` would mean decoding the WKB again. Meaningless (and unread) when
/// `px` is `Some` — a node has no extent.
rank: u32,
load: Payload,
}
/// One run of payloads **evicted from a shard, its byte range already reserved**,
/// waiting to be serialized and `pwrite`n by the worker that evicted it.
///
/// # Why the spill leaves the critical section
///
/// [`Shard::spill_down`] used to serialize the payloads AND `write_all` them with
/// the shard mutex held. MEASURED on oden 2026-08-04, `sweden` at z15: of the
/// 548.6 thread-seconds the scan spent inside its units, **305.0 were threads
/// asleep on a shard mutex** and 112.5 of the 173.1 lock-held seconds were that
/// spill — 115.27 GiB of it. 32 workers queue behind one shard doing disk I/O, so
/// a 2.7-core scan on a 32-core box was not a parallelism bug in the fan-out, it
/// was one lock held across a write.
///
/// The fix is the gatling rule applied to a byte range rather than a file: the
/// **offset is allocated under the lock** (so `way_segs` / `point_segs` still record
/// runs in exactly the order they were evicted, and no two runs can ever be handed
/// the same bytes), and the **serialization and the `pwrite` happen outside it**.
/// Every byte range has exactly one writer, which is what made the lock unnecessary
/// in the first place. The exact length is known before a single byte is built —
/// see [`run_spill_bytes`] — so no reservation ever has to be corrected.
struct SpillJob {
/// Shared read/write handle to the shard's scratch file. `pwrite` takes `&File`,
/// so no worker needs the shard, or each other, to write its own range.
file: Arc<std::fs::File>,
/// The reserved absolute offset in that file.
start: u64,
/// The payloads to serialize there. Moved out of the tile under the lock.
payloads: Vec<Payload>,
}
/// One shard's disjoint slice of the pyramid, plus its spill scratch.
struct Shard {
tiles: HashMap<TileId, TileAccum>,
/// Accounted resident payload bytes across this shard's tiles.
resident: u64,
/// `Arc` rather than a bare `File` because a [`SpillJob`] carries a handle out
/// of the critical section and writes its own reserved range with `write_all_at`.
spill: Option<Arc<std::fs::File>>,
spill_path: PathBuf,
spill_len: u64,
spilled_bytes: u64,
peak_resident: u64,
/// **Resident bytes this shard holds that a spill cannot free** — the sum of
/// [`bookkeeping_bytes`] over its tiles plus its own `HashMap` table. Tracked as a
/// delta on every mutation rather than swept, because the peak is what matters and
/// a sweep would only ever see the end state.
book: u64,
peak_book: u64,
}
/// Bytes [`encode_wkb_point`] always emits: byte order (1) + type (4) + lon (8) +
/// lat (8). A `Point` payload is the one geometry whose WKB does not exist until
/// it is asked for, so [`run_spill_bytes`] needs this to reserve a range without
/// building it. Pinned by `wkb_point_length_is_what_the_reservation_assumes`,
/// which fails the moment the encoder emits anything else.
const WKB_POINT_BYTES: usize = 21;
/// The **exact** serialized length of a spill run, computed without building a
/// single byte of it.
///
/// This is what lets the byte range be reserved under the shard lock while the
/// bytes themselves are built outside it. Every field is fixed-width or has a
/// length known from the value it will be written from — a `Point` is the 21 bytes
/// [`encode_wkb_point`] always emits, a `Line`/`Poly` is the length of the WKB it
/// already holds — so the reservation can never be short or long. It is the same
/// per-record layout [`serialize_spill_run`] writes and [`read_run`] reads; the
/// three are kept adjacent so a change to one is a change in front of the others.
#[inline]
fn run_spill_bytes(v: &[Payload]) -> u64 {
v.iter()
.map(|p| {
let g = match &p.0 {
TileGeom::Point(..) => WKB_POINT_BYTES,
TileGeom::Line(b) | TileGeom::Poly(b) => b.len(),
};
let t = p.1.as_deref().map_or(0, str::len);
(4 + g + 4 + t + 8) as u64
})
.sum()
}
/// Serialize a spill run into bytes, in the layout [`read_run`] replays.
fn serialize_spill_run(v: Vec<Payload>, exact_len: u64) -> Vec<u8> {
let mut buf: Vec<u8> = Vec::with_capacity(exact_len as usize);
for p in v {
let g = p.0.to_wkb();
let t = p.1.as_deref().unwrap_or("");
buf.extend_from_slice(&(g.len() as u32).to_le_bytes());
buf.extend_from_slice(&g);
buf.extend_from_slice(&(t.len() as u32).to_le_bytes());
buf.extend_from_slice(t.as_bytes());
buf.extend_from_slice(&p.2.to_le_bytes());
}
debug_assert_eq!(
buf.len() as u64,
exact_len,
"run_spill_bytes disagreed with the bytes actually written — the reserved \
range would overlap its neighbour"
);
buf
}
impl SpillJob {
/// Serialize and `pwrite` this run into its reserved range. Runs **outside**
/// the shard mutex, on the worker that evicted it; no other job can be handed
/// the same bytes, so there is nothing to synchronize.
fn write(self) -> std::io::Result<()> {
use std::os::unix::fs::FileExt;
let len = run_spill_bytes(&self.payloads);
let buf = serialize_spill_run(self.payloads, len);
self.file.write_all_at(&buf, self.start)
}
}
/// Replay a spilled run back into the write phase's flat `geoms`/`tags`/`ids`
/// vectors. Every column the resident path appends, this one appends too — a spilled
/// tile and a resident tile must be indistinguishable in the file.
/// `scratch` is the caller's re-used read buffer — one per WRITE worker, not one per
/// segment (`katana-9`); it is resized to the run's byte length and its capacity
/// survives every tile that worker writes.
fn read_run(
f: &mut std::fs::File,
seg: Seg,
scratch: &mut Vec<u8>,
rows: &mut TileRows,
) -> anyhow::Result<()> {
f.seek(SeekFrom::Start(seg.0))?;
scratch.clear();
scratch.resize(usize::try_from(seg.1)?, 0u8);
let buf = &mut scratch[..];
f.read_exact(buf)?;
let mut o = 0usize;
let get = |b: &[u8], o: usize| -> anyhow::Result<usize> {
anyhow::ensure!(o + 4 <= b.len(), "truncated spill run");
Ok(u32::from_le_bytes(b[o..o + 4].try_into().expect("4 bytes")) as usize)
};
for _ in 0..seg.2 {
let gl = get(buf, o)?;
o += 4;
anyhow::ensure!(o + gl <= buf.len(), "truncated spill geometry");
let g_at = o;
o += gl;
let tl = get(buf, o)?;
o += 4;
anyhow::ensure!(o + tl <= buf.len(), "truncated spill tag");
let t_at = o;
o += tl;
anyhow::ensure!(o + 8 <= buf.len(), "truncated spill id");
let id = i64::from_le_bytes(buf[o..o + 8].try_into().expect("8 bytes"));
o += 8;
// The tag was written as UTF-8 by this same module's spill serialiser. A
// `from_utf8_lossy` on the borrowed bytes is free in the (always taken) valid
// case and only allocates on a corrupted spill file, which is a bug, not a
// shape this loop should pay for on every row.
let tag = String::from_utf8_lossy(&buf[t_at..t_at + tl]);
rows.push(&buf[g_at..g_at + gl], tag.as_ref(), id);
}
Ok(())
}
/// The write phase's per-worker scratch (`katana-9`).
///
/// A tile is rebuilt from its spilled runs and its resident tail before it can be
/// encoded, and doing that into freshly allocated vectors cost two heap allocations
/// per ROW — ~84 M rows on Sweden at `[6, 9, 12]`, 1.58 M tiles' worth at z15. Both
/// buffers are pure working memory: nothing outside one tile reads them and every
/// tile overwrites them, so they belong to the WORKER, not to the tile.
///
/// It is a `thread_local` and not a closure-local because `gatling_for_each` hands
/// its closure an INDEX (`Fn(usize)`, `gatling_forkjoin.rs`) and calls it once per
/// tile — a closure-local buffer would be per-tile, which is the shape being
/// removed. The pool's OS threads live for the whole fan-out, so one buffer per
/// thread is reused across every tile that thread writes and reaches the high-water
/// mark of the largest tile it has seen. The single-worker case runs inline on the
/// calling thread, which is what makes the allocation guard readable.
#[derive(Default)]
struct WriteScratch {
rows: TileRows,
/// The spill-run read buffer — resized per run, capacity kept.
spill_buf: Vec<u8>,
}
thread_local! {
static WRITE_SCRATCH: std::cell::RefCell<WriteScratch> =
std::cell::RefCell::new(WriteScratch::default());
}
/// Thread-nanoseconds spent inside [`Shard::spill_down`], summed across every scan
/// worker. The shard mutex is held throughout, so this is **exactly the time the
/// shard is unavailable to its 31 siblings** — the number that has to stay small.
static SPILL_NS: AtomicU64 = AtomicU64::new(0);
/// Thread-nanoseconds spent serializing and `pwrite`ing the evicted runs — the work
/// that used to be counted in `SPILL_NS` because it happened under the lock, and is
/// now out here where it blocks nobody. The two moving in opposite directions is the
/// change, stated in the run's own output.
static SPILL_WRITE_NS: AtomicU64 = AtomicU64::new(0);
impl Shard {
/// Absorb one scan worker's batch of placements, applying the per-tile caps
/// and the node sub-pixel dedup, then evict down to `low` if `high` is passed.
///
/// Returns the evicted runs **unwritten**, with their byte ranges already
/// reserved. The caller must drop the shard guard and then [`SpillJob::write`]
/// every one of them before the scan ends — the disk is deliberately not
/// touched while this lock is held.
#[must_use = "the evicted runs are not on disk until SpillJob::write is called"]
fn absorb(
&mut self,
batch: &mut Vec<Placement>,
max_points: usize,
lane_budgets: [usize; 3],
raster_px: u32,
// Way placements refused, `[zoom index][lane]`. The caller owns it per worker
// so the count costs no atomic on the hot path; it is folded in once per unit.
refused: &mut [[usize; 3]],
high: u64,
low: u64,
) -> anyhow::Result<Vec<SpillJob>> {
let mut jobs: Vec<SpillJob> = Vec::new();
// The shard's own table, before and after: a rehash of the tile map is a
// multi-megabyte event on a country and it belongs in the books.
let map0 = table_bytes::<(TileId, TileAccum)>(self.tiles.capacity());
for p in batch.drain(..) {
let acc = self.tiles.entry(p.tile).or_default();
let b = placement_bytes(&p.load);
// `seen_px` grows by doubling and NEVER shrinks — not on spill, not on
// eviction, because the dedup it implements has to outlive both. Charge
// the delta at the one place it can change.
let book0 = bookkeeping_bytes(acc);
match p.px {
Some(px) => {
if acc.n_points >= max_points || !acc.seen_px.insert(px) {
self.book += bookkeeping_bytes(acc) - book0;
continue;
}
acc.n_points += 1;
acc.points.push(p.load);
}
None => {
// **The cap keeps by rank, not by arrival order.** One comparison
// against the ONE total, with a budget that rises with the lane, so
// dust can fill 40 % of a tile and no more — and the slots above
// that are reachable only by something the reader can actually see.
let lane = way_lane(p.rank, raster_px);
if acc.n_ways >= lane_budgets[lane as usize] {
if let Some(r) = refused.get_mut(usize::from(p.tile.0)) {
r[lane as usize] += 1;
}
continue;
}
acc.n_ways += 1;
acc.ways.push(p.load);
}
}
self.book += bookkeeping_bytes(acc) - book0;
acc.bytes += b;
self.resident += b;
}
self.book = self.book + table_bytes::<(TileId, TileAccum)>(self.tiles.capacity()) - map0;
self.peak_resident = self.peak_resident.max(self.resident);
self.peak_book = self.peak_book.max(self.book);
if high > 0 && self.resident > high {
let t = std::time::Instant::now();
let r = self.spill_down(low);
SPILL_NS.fetch_add(t.elapsed().as_nanos() as u64, Ordering::Relaxed);
jobs = r?;
}
Ok(jobs)
}
/// Evict the BIGGEST tiles until the resident payload is back under `target`,
/// **reserving** each run's byte range and handing the bytes back unwritten.
/// Biggest-first because one eviction of a fat tile buys what a hundred of thin
/// ones would, and the per-tile bookkeeping (`seen_px`, the counters) stays in
/// memory either way.
///
/// Nothing here touches the disk. The returned [`SpillJob`]s are serialized and
/// `pwrite`n by the caller **after** it has dropped the shard guard — see
/// [`SpillJob`] for the 305-thread-second reason. Order is still fixed here,
/// inside the lock: `way_segs` / `point_segs` receive their entries in eviction
/// order, so a tile replays byte-for-byte as before however the writes race.
fn spill_down(&mut self, target: u64) -> anyhow::Result<Vec<SpillJob>> {
if self.spill.is_none() {
if let Some(dir) = self.spill_path.parent() {
std::fs::create_dir_all(dir)?;
}
self.spill = Some(Arc::new(
std::fs::OpenOptions::new()
.create(true)
.truncate(true)
.read(true)
.write(true)
.open(&self.spill_path)
.with_context(|| format!("open tile spill {:?}", self.spill_path))?,
));
}
let file = Arc::clone(self.spill.as_ref().expect("spill file just opened"));
let mut jobs: Vec<SpillJob> = Vec::new();
let mut order: Vec<(u64, TileId)> = self.tiles.iter().map(|(k, v)| (v.bytes, *k)).collect();
order.sort_unstable_by(|a, b| b.0.cmp(&a.0));
for (_, id) in order {
if self.resident <= target {
break;
}
let Some(acc) = self.tiles.get_mut(&id) else {
continue;
};
if acc.bytes == 0 {
continue;
}
let book0 = bookkeeping_bytes(acc);
for (runs, segs) in [
(std::mem::take(&mut acc.ways), &mut acc.way_segs),
(std::mem::take(&mut acc.points), &mut acc.point_segs),
] {
if runs.is_empty() {
continue;
}
let len = run_spill_bytes(&runs);
let start = self.spill_len;
self.spill_len += len;
self.spilled_bytes += len;
segs.push((start, len, runs.len() as u32));
jobs.push(SpillJob {
file: Arc::clone(&file),
start,
payloads: runs,
});
}
// Spilling ADDS bookkeeping (a segment index entry per run) and frees
// none: the dedup set stays. That direction is the whole point of
// measuring it — the floor rises every time the budget is enforced.
self.book += bookkeeping_bytes(acc) - book0;
self.resident -= acc.bytes;
acc.bytes = 0;
}
self.peak_book = self.peak_book.max(self.book);
Ok(jobs)
}
}
/// **The `rels=` axis of a complete cut** — the ONE value a reader may serve.
///
/// Everything else is a pyramid missing multipolygons, and a reader must re-cut rather
/// than serve it. [`TileRecipe::for_zooms`] stamps this, so korp's
/// `TileOptions::default().recipe().token()` demands it with no korp edit at all.
pub const RELS_RESOLVED: &str = "resolved";
/// The resolve step never ran: the raw `relations.parquet` a `convert` writes is all
/// this pyramid saw, and its `geometry` column is 100 % NULL.
pub const RELS_RAW: &str = "raw";
/// No relation table beside the extract at all.
pub const RELS_NONE: &str = "none";
/// `relations.resolved.parquet` exists but NOT ONE row carries assembled geometry —
/// the live 2026-08-04 shape, 0 of 14 592 834.
pub const RELS_RESOLVED_EMPTY: &str = "resolved-empty";
/// The relation table could not be read. Unknown is NOT current.
pub const RELS_UNKNOWN: &str = "unknown";
/// **What the relation half of this cut actually was — the recipe axis and the log line
/// it prints, from ONE reading of the table.**
///
/// The seventh axis of [`TileRecipe`], and the reason it exists: the tiler picks its
/// relation table on `relations.resolved.parquet.exists()` and cuts either way, and until
/// now the ONLY trace of which it got was an `eprintln!`. MEASURED on the live stack
/// 2026-08-04: `~/.korp/work/sweden/relations.parquet` held **0 of 14 592 834
/// geometries** and `relations.resolved.parquet` did not exist, so a whole Sweden pyramid
/// was cut with no lake, no forest clearing and no building outline in it — and stamped a
/// **byte-identical** recipe token to a complete one. `korp::pipeline::tile_recipe_state`
/// said `Complete`, `korp::map_tiles::asset_recipe_state` said `Current`,
/// `korp::map_tiles::tiling_action` said `Serve`, forever.
/// The mean tile was 12.7 kB against 26.6 kB for the same region with relations in it —
/// **relations are ~52 % of a tile's bytes.**
///
/// The producer side of that was fixed in korp `66d8fa1` (`regions::ensure_relations` is
/// now one writer both arms go through), but a pyramid ALREADY in the object store, cut
/// before that commit, is untouched by it: it carries the identical token and no
/// automatic path can reach it. The recipe axis is the only fix by construction.
///
/// Returns `(axis, log line)` together on purpose. Two readings of the same table would
/// be two judgements, and a log that can disagree with the token is the defect this
/// closes, one layer down.
pub fn relations_axis(rels: Option<&Path>, extract_dir: &Path) -> (String, String) {
let Some(rels) = rels else {
return (
String::from(RELS_NONE),
format!("no relation table under {extract_dir:?} — no multipolygons"),
);
};
// The tiler prefers `relations.resolved.parquet` and falls back to the raw table, so
// the NAME is what says whether the resolve step ran at all. Derived from the same
// join the caller makes, not from a second guess about the layout.
let is_resolved = rels == extract_dir.join("relations.resolved.parquet");
match crate::verify::verify(rels) {
Err(e) => (
String::from(RELS_UNKNOWN),
format!(
"cannot read {rels:?}: {e:#} — whether this pyramid has multipolygons in \
it is UNKNOWN, and unknown is not current"
),
),
Ok(v) if !is_resolved => (
String::from(RELS_RAW),
format!(
"{rels:?} is the RAW relation table ({} rows, {} carry geometry) — the \
resolve step never ran, so every multipolygon (lakes with islands, \
forest with clearings, building outlines) is missing from this pyramid. \
Run `osm-katana relations {extract_dir:?}` first.",
v.rows, v.geom_set,
),
),
// A resolved table with nothing in it is NOT a complete cut, and a 0-row one
// cannot be told apart from a resolve that produced nothing: both re-cut. The
// cost of being wrong here is one needless re-cut; the cost of the other
// direction is a permanently lakeless pyramid nothing can see is lakeless.
Ok(v) if v.geom_set == 0 => (
String::from(RELS_RESOLVED_EMPTY),
format!(
"{rels:?} has {} rows and NOT ONE carries geometry — every multipolygon \
is missing from this pyramid. Run `osm-katana relations {extract_dir:?}` \
to clip and assemble it first.",
v.rows,
),
),
Ok(v) => (
String::from(RELS_RESOLVED),
format!(
// ── THE DENOMINATOR IS THE WHOLE POINT (`K17`) ──────────────────
// This used to read "{rows} rows, {geom_set} carry assembled geometry
// ({pct} %)" against ALL rows, and on the 2026-08-30 Sweden cut that
// printed **82.3 %** — which reads as "one relation in six failed" and
// cost a reader an afternoon chasing 48 407 phantom failures.
//
// Only an AREA relation is ever GIVEN geometry (`RelationKind::Area`);
// a `type=route` is an ordered set of ways, a `type=restriction` is a
// rule and a `type=public_transport` is a stop group — none of them is a
// shape, and `relgeom`'s own doc says so. MEASURED on that same file:
// of 274 206 rows, 226 967 are areas and **225 799 of them assembled
// (99.49 %)**; the 48 407 without geometry are 14 588 routes, 14 412
// stop areas, 5 633 turn restrictions and so on. The failures are the
// ~1 324 areas that did NOT assemble, not the difference from 274 206.
//
// So the line names both populations and takes the percentage against
// the one it is a percentage OF. A ratio whose denominator is the wrong
// set is not a smaller truth, it is a different claim.
"{rels:?} — {} rows: {} carry assembled geometry, {} carry none because \
of WHAT THEY ARE (a route is an ordered set of ways, a restriction is a \
rule, a stop area is a group — only an area relation is given a shape). \
A failure ratio is a percentage of the AREA relations; this probe does \
not classify them, so it prints no ratio — `osm-katana relations` \
reports that one",
v.rows,
v.geom_set,
v.rows.saturating_sub(v.geom_set),
),
),
}
}
/// **One unit of the tiling scan: a ROW RANGE of a parquet row group.**
///
/// The unit used to be the row group itself, and that made the writer's row-group size
/// the scan's degree of parallelism — two knobs in two crates, one of which nobody
/// tuning the other could see. MEASURED on korp's `sweden` cut 2026-08-04:
/// `relations.resolved.parquet` is **270 923 rows in ONE row group** (189 179 084 B),
/// because `writer::ROW_GROUP_SIZE` is 524 288 and 270 923 < 524 288 — so the whole
/// relation half of the scan ran on **one thread of 32**, and its rows are the most
/// expensive per row in the run (223 382 assembled multipolygons). `ways.parquet` was
/// barely better: 32 row groups on a 32-core box is exactly one unit per core and zero
/// slack for a slow one.
///
/// Splitting on the READ side rather than shrinking the row group is the fix that holds
/// (LAW 5): the writer keeps ONE row-group size, chosen for compression, and no future
/// re-tuning of it can quietly serialise the scan again.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct ScanUnit {
/// Index into the scan's source list.
pub si: usize,
/// The row group this unit reads from.
pub rg: usize,
/// Rows skipped at the head of that row group.
pub skip: usize,
/// Rows read after the skip. Never 0 — an empty unit is a worker doing nothing.
pub take: usize,
}
/// **The smallest a split part may be.**
///
/// Below this the per-unit cost — open a `ParquetRecordBatchReaderBuilder`, decode the
/// row group's page headers, walk a `RowSelection` — stops being amortised by the rows
/// it covers, and the fan-out starts costing more than the serialisation it removes.
pub(crate) const MIN_SCAN_UNIT_ROWS: usize = 4_096;
/// **How many units per worker the planner aims for.**
///
/// One unit per worker has no slack: the run is as long as its slowest unit. Four gives
/// a late worker three chances to be handed something small.
pub(crate) const SCAN_UNITS_PER_WORKER: usize = 4;
/// **Cut each source's row groups into units small enough that `workers` threads all
/// get work.**
///
/// `groups` is `(si, rg, rows)` AFTER the all-NULL prune, in source order. The target
/// size is computed **per source**, not over the whole scan: a node row and a relation
/// row are not the same amount of work, and a global target computed over 102.5 M nodes
/// leaves the 270 923 relation rows as a single unit again — the exact defect this
/// exists to remove.
///
/// Every row of every group reaches exactly one unit: the parts of a group are
/// contiguous, start at 0 and sum to its row count. That is asserted, because a planner
/// that drops a range drops MAP, silently.
pub(crate) fn split_scan_units(groups: &[(usize, usize, usize)], workers: usize) -> Vec<ScanUnit> {
let workers = workers.max(1);
// Rows per source, so the target is a source's own scale.
let mut rows_per_src: HashMap<usize, usize> = HashMap::new();
for &(si, _, rows) in groups {
*rows_per_src.entry(si).or_insert(0) += rows;
}
let mut units = Vec::with_capacity(groups.len());
for &(si, rg, rows) in groups {
if rows == 0 {
continue;
}
let src_rows = rows_per_src.get(&si).copied().unwrap_or(rows);
let want = workers.saturating_mul(SCAN_UNITS_PER_WORKER).max(1);
let target = src_rows.div_ceil(want).max(MIN_SCAN_UNIT_ROWS);
// Near-equal parts rather than `target`-sized ones plus a runt tail: a 4 097-row
// group at target 4 096 is two units of 2 049/2 048, not 4 096 + 1.
let parts = rows.div_ceil(target).max(1);
let mut done = 0usize;
for p in 0..parts {
// `rows * (p+1) / parts - rows * p / parts` — integer, exact, and the parts
// provably sum to `rows` whatever the remainder is.
let end = rows * (p + 1) / parts;
let take = end - done;
if take == 0 {
continue;
}
units.push(ScanUnit {
si,
rg,
skip: done,
take,
});
done = end;
}
debug_assert_eq!(done, rows, "the parts of a row group must cover all of it");
}
units
}
/// **Tile a region into many small covering-packed slippy-tile GeoParquet objects.**
///
/// Writes `out_dir/tiles/z{Z}/{X}/{Y}.parquet` for every non-empty tile at each
/// [`TileOptions::zooms`] level, DECIMATING per zoom (sub-pixel node dedup + way
/// vertex-thinning), and returns a per-zoom report. For [`TileSource::Pbf`] the clip
/// stage is the existing [`crate::convert`] (streaming, gatling); for
/// [`TileSource::Extract`] the extract is tiled directly. Does NOT upload anywhere —
/// it produces files on disk; a caller (e.g. korp) ships them to its object store.
///
/// Ways are simplified per zoom with Douglas-Peucker and duplicated into every tile
/// their bbox overlaps (see [`way_tiles`] / [`MAX_WAY_TILE_FANOUT`]); points are
/// sub-pixel-deduped and placed in their single tile — and, when
/// [`TileOptions::region`] is set, NO tile is written outside the region.
pub fn tile_region(
source: TileSource,
out_dir: &Path,
opts: &TileOptions,
) -> anyhow::Result<TileStats> {
anyhow::ensure!(
!opts.zooms.is_empty(),
"tile_region needs at least one zoom level"
);
// **The region the pyramid may occupy.** An explicit `opts.region` wins; otherwise
// a PBF source's own `Clip` already names the region being cut, and tiling wider
// than the clip that produced the extract can never be right — so derive it rather
// than make every caller repeat itself.
let region = opts.region.or_else(|| match &source {
TileSource::Pbf { clip, .. } => Some(clip.bounds()),
TileSource::Extract(_) => None,
});
// Resolve the extract dir: tile it directly, or clip a PBF into a scratch dir first.
let (extract_dir, _scratch): (PathBuf, Option<PathBuf>) = match source {
TileSource::Extract(dir) => (dir.to_path_buf(), None),
TileSource::Pbf { input, clip } => {
let scratch = out_dir.join("_extract");
std::fs::create_dir_all(&scratch)
.with_context(|| format!("create scratch extract dir {scratch:?}"))?;
eprintln!(
"osm-katana/tiles: clipping {input:?} → {scratch:?} (convert, gatling streaming) \
before tiling"
);
let conv = ConvertOptions {
output_dir: scratch.clone(),
clip: Some(Arc::new(clip)),
keep_node_coords: false,
..Default::default()
};
crate::convert(input, &conv).with_context(|| format!("clip-convert {input:?}"))?;
(scratch.clone(), Some(scratch))
}
};
let nodes = extract_dir.join("nodes.parquet");
let ways = extract_dir.join("ways.parquet");
// **The relation table.** Prefer the RESOLVED one (`osm-katana relations`:
// clipped to this extract, member ways assembled into MultiPolygons); fall
// back to the raw one a `convert` wrote so the absence of the resolve step
// produces a warning instead of silence.
let resolved = extract_dir.join("relations.resolved.parquet");
let rels = if resolved.exists() {
resolved
} else {
extract_dir.join("relations.parquet")
};
anyhow::ensure!(
ways.exists() || nodes.exists(),
"no nodes.parquet / ways.parquet under {extract_dir:?} to tile"
);
// **The relation axis of the recipe, and the line that says it out loud — ONE
// judgement.** Until 2026-08-03 `tiles.rs` did not contain the string `relations` at
// all; then it grew the `eprintln!` below and cut anyway. A stderr line is not a
// gate: it is in no manifest, in no tile footer and in no `StepState`, so a pyramid
// with not one multipolygon in it stamped a byte-identical recipe token to a
// complete one and korp read it as `Current`/`Serve` forever. The log and the token
// now come out of the same call, so neither can say something the other does not.
let (rels_axis, rels_line) =
relations_axis(rels.exists().then_some(rels.as_path()), &extract_dir);
eprintln!("osm-katana/tiles: {rels_line}");
// **The recipe this run actually implements.** The option-derived axes come from
// `opts`; the relation axis is the one thing the options cannot know, because the
// tiler picks its relation table off the extract. Built ONCE here and used by both
// the stats and the tile writer, so the token in a tile's footer and the token in
// the manifest cannot come from two different judgements.
let run_recipe = {
let mut r = opts.recipe();
r.relations = rels_axis;
r
};
// **Say it out loud when a source has no `id`.** `id_at` falls back to 0 so a
// pre-`id` extract still tiles, and that fallback is exactly the shape of the
// defect this column exists to fix: a whole pyramid of objects that all hash to
// one key, produced with no error and no warning. A tiling run that silently
// reintroduces it is worse than one that fails, so name the file.
for p in [&ways, &nodes] {
if !p.exists() {
continue;
}
if !source_has_id_column(p).unwrap_or(true) {
eprintln!(
"osm-katana/tiles: {p:?} has NO `id` column — every object it \
contributes is tiled with id 0. A renderer keying its cache on the \
tile `id` (facett `layer.rs`'s `osm_id`) then sees ONE key for all of \
them and never rebakes on zoom. Re-run the convert that produced this \
extract; `ways_schema`/`nodes_schema` have declared `id` non-null \
throughout."
);
}
}
match ®ion {
Some(r) => eprintln!(
"osm-katana/tiles: tiling {extract_dir:?} at zooms {:?} \
(ways: Douglas-Peucker LOD + bbox-overlap duplication; nodes: sub-pixel dedup) \
· REGION-BOUNDED to lon {:.3}..{:.3} lat {:.3}..{:.3} — no tile is written outside it",
opts.zooms, r.min_lon, r.max_lon, r.min_lat, r.max_lat
),
None => eprintln!(
"osm-katana/tiles: tiling {extract_dir:?} at zooms {:?} \
(ways: Douglas-Peucker LOD + bbox-overlap duplication; nodes: sub-pixel dedup) \
· UNBOUNDED (no TileOptions::region) — a leaked foreign object WILL be tiled \
where it lies",
opts.zooms
),
}
// Per-zoom inclusive tile range the region occupies, precomputed once. Same
// `tile_range` the reader's `covering_tiles` uses, so "in the region" means the
// same thing to the writer and the reader.
let allowed: Vec<Option<(u32, u32, u32, u32)>> = opts
.zooms
.iter()
.map(|&z| region.as_ref().map(|r| tile_range(r, z)))
.collect();
// `true` when this tile placement is inside the region (or there is no region).
let in_region = |zi: usize, (x, y): (u32, u32)| match allowed[zi] {
None => true,
Some((x0, x1, y0, y1)) => x >= x0 && x <= x1 && y >= y0 && y <= y1,
};
let refused_tiles = AtomicUsize::new(0);
let refused_features = AtomicUsize::new(0);
// Features handed to a network table. Counted, never silent: an exclusion nobody
// counts is indistinguishable from a predicate that never fired. And counted PER
// SOURCE, because one counter over three sources cannot tell an exclusion that took
// the wrong source from one that took the right one — see
// [`TileStats::network_features_by_kind`].
let network_features: [AtomicUsize; 3] = Default::default();
let scanned_ways = AtomicUsize::new(0);
let scanned_nodes = AtomicUsize::new(0);
let scanned_relations = AtomicUsize::new(0);
// A geometry blob the ring-preserving decoder REFUSED (truncated, 3-D, or a
// WKB type it does not know). Counted and printed rather than skipped in
// silence — "0 features from a 1 GB file" and "this file is not for me" look
// identical in a pyramid, and the old decoder could not tell them apart at all.
let undecodable = AtomicUsize::new(0);
// ── The scan's BOOKS, per source kind (`K15`) ─────────────────────────────
// Three `continue`s in the inner loop below sit BEFORE `local_n += 1`, so a row
// they take is invisible to every counter this run had: `undecodable` (it decoded),
// `collapsed_areas` (it never reached a ring) and `refused_features` (it never
// reached a placement) all miss it. On the 2026-08-27 Sweden cut that was **1 523
// ways**, found only by subtracting the tiler's own two numbers from pass 2's way
// count by hand. The fix is not a fourth counter but an identity that has to close
// — see [`ScanLedger`].
let rows_read: [AtomicUsize; 3] = Default::default();
let null_geometry: [AtomicUsize; 3] = Default::default();
let no_geometry_extent: [AtomicUsize; 3] = Default::default();
let untagged_nodes: [AtomicUsize; 3] = Default::default();
let undecodable_by_kind: [AtomicUsize; 3] = Default::default();
// Areas whose every ring fell below 4 vertices at some zoom (legitimately
// sub-pixel, and shipped as a point) and areas that reached a tile as a real
// MultiPolygon.
let collapsed_areas = AtomicUsize::new(0);
let poly_placements = AtomicUsize::new(0);
// **Ways the [`MAX_WAY_TILE_FANOUT`] cap collapsed to one tile, per zoom.** Counted
// because the cap is a fixed tile count over a shrinking tile: inert at z12, and
// a way removed from every tile it crosses but one at z15. A pyramid that quietly
// drops long geometry at its finest zoom is exactly the shape of defect a report
// has to name — the alternative is a run that looks clean and serves a map with
// holes in the railways.
let fanout_capped: Vec<AtomicUsize> = opts.zooms.iter().map(|_| AtomicUsize::new(0)).collect();
// **Way placements the lane ladder refused, per zoom and per [`WayLane`].** The
// predecessor's cap reported NOTHING: a tile that dropped a lake and a tile that
// dropped nothing produced the same run output, which is why `natt-7` had to be
// found by reading tile files. A cap that cannot say what it threw away is a cap
// nobody can tune — and a full `Dominant` lane is the one number that would say
The file goes on; the console shows all of it.