use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, HashMap, VecDeque};
use std::sync::Arc;
use rayon::prelude::*;
use tippecanoe::errors::{EXIT_IMPOSSIBLE, EXIT_PROTOBUF};
use super::key::{Key, TieBreak, cmp};
use super::overzoom::overzoom;
use super::source::{Loc, Source, TileRef};
use super::tile::{Decoded, decompress, is_compressed};
use crate::{Error, Result};
type Zxy = (i64, i64, i64);
const OVERZOOM_BATCH: usize = 256;
pub struct Settings {
pub want_overzoom: bool,
pub buffer: i32,
pub tie_break: TieBreak,
}
struct Made {
xy: (u32, u32),
data: Arc<[u8]>,
children: Vec<(u32, u32)>,
}
pub struct Reader<'s> {
pub source: &'s Source,
pub index: usize,
zoom: i64,
x: i64,
y: i64,
tile: TileRef,
made: bool,
key: Option<Key>,
seq: Option<u64>,
next_seq: u64,
cache: BTreeMap<u64, Key>,
current_tile_is_overzoomed: bool,
done: bool,
maxzoom_so_far: i32,
tiles_at_maxzoom_so_far: Vec<(u32, u32)>,
overzoomed_tiles: Vec<(u32, u32)>,
next_overzoomed_tiles: Vec<(u32, u32)>,
overzoom_consumed_at_this_zoom: bool,
pending: VecDeque<TileRef>,
exhausted: bool,
ready: VecDeque<Made>,
}
fn tilecmp(a: &(u32, u32), b: &(u32, u32)) -> Ordering {
if b.0 < a.0 {
return Ordering::Less;
}
if b.0 == a.0 {
if b.1 > a.1 {
return Ordering::Less;
}
if b.1 == a.1 {
return Ordering::Equal;
}
}
Ordering::Greater
}
impl<'s> Reader<'s> {
fn new(source: &'s Source, index: usize) -> Reader<'s> {
Reader {
source,
index,
zoom: 0,
x: 0,
y: 0,
tile: TileRef {
z: 0,
x: 0,
y: 0,
loc: Loc::Data(Arc::from(&[][..])),
},
made: true,
key: None,
seq: None,
next_seq: 0,
cache: BTreeMap::new(),
current_tile_is_overzoomed: false,
done: false,
maxzoom_so_far: -1,
tiles_at_maxzoom_so_far: Vec::new(),
overzoomed_tiles: Vec::new(),
next_overzoomed_tiles: Vec::new(),
overzoom_consumed_at_this_zoom: false,
pending: VecDeque::new(),
exhausted: false,
ready: VecDeque::new(),
}
}
pub fn begin(source: &'s Source, index: usize, s: &Settings) -> Result<Reader<'s>> {
let mut r = Reader::new(source, index);
r.advance(s)?;
Ok(r)
}
fn read_more(&mut self) -> bool {
if self.exhausted {
return false;
}
match self.source.next_chunk() {
Some(chunk) => self.pending.extend(chunk),
None => self.exhausted = true,
}
!self.exhausted
}
fn next_source_tile(&mut self) -> Option<TileRef> {
while self.pending.is_empty() && self.read_more() {}
let t = self.pending.pop_front()?;
self.seq = Some(self.next_seq);
self.next_seq += 1;
Some(t)
}
fn set_data(&mut self, tile: TileRef, made: bool) {
self.tile = tile;
self.made = made;
self.key = None;
if made {
self.seq = None;
}
let now = self.seq.unwrap_or(self.next_seq);
while self.cache.first_key_value().is_some_and(|(&k, _)| k < now) {
self.cache.pop_first();
}
}
fn has_key(&self) -> bool {
self.key.is_some() || self.seq.is_some_and(|q| self.cache.contains_key(&q))
}
fn key(&mut self, s: &Settings) -> Result<&Key> {
if self.key.is_none()
&& let Some(q) = self.seq
&& let Some(k) = self.cache.remove(&q)
{
self.key = Some(k);
}
if self.key.is_none() {
let data = self.source.data(&self.tile)?.shared();
let key = if self.made {
Key::Bytes(data)
} else {
Key::new(data, self.source.tippecanoe_made, s.tie_break)
};
self.key = Some(key);
}
Ok(self.key.as_ref().expect("just set"))
}
fn finished(&self) -> bool {
self.done && !self.overzoom_consumed_at_this_zoom
}
fn current(&mut self) -> (i64, i64, i64, TileRef) {
if self.current_tile_is_overzoomed {
self.overzoom_consumed_at_this_zoom = true;
}
(self.zoom, self.x, self.y, self.tile.clone())
}
fn advance(&mut self, s: &Settings) -> Result<()> {
if self.done {
if !s.want_overzoom {
return Err(Error::new(
EXIT_IMPOSSIBLE,
"overzoom advance called without -O",
));
}
if self.overzoomed_tiles.is_empty() {
self.next_overzoom();
self.overzoom_consumed_at_this_zoom = false;
}
let Some(xy) = self.overzoomed_tiles.last().copied() else {
self.current_tile_is_overzoomed = false;
self.zoom = 32;
return Ok(());
};
if self.ready.is_empty() {
self.make_overzoomed(s)?;
}
self.overzoomed_tiles.pop();
let made = self.ready.pop_front().expect("a batch was made");
debug_assert_eq!(made.xy, xy);
self.next_overzoomed_tiles.extend_from_slice(&made.children);
self.x = xy.0 as i64;
self.y = xy.1 as i64;
self.set_data(
TileRef {
z: self.zoom,
x: self.x,
y: self.y,
loc: Loc::Data(made.data),
},
true,
);
self.current_tile_is_overzoomed = true;
return Ok(());
}
self.current_tile_is_overzoomed = false;
match self.next_source_tile() {
Some(t) => {
self.zoom = t.z;
self.x = t.x;
self.y = t.y;
self.set_data(t, false);
}
None => self.done = true,
}
if self.done {
if s.want_overzoom {
self.next_overzoom();
self.advance(s)?;
} else {
self.zoom = 32;
}
} else {
if self.zoom > self.maxzoom_so_far as i64 {
self.maxzoom_so_far = self.zoom as i32;
self.tiles_at_maxzoom_so_far.clear();
}
if s.want_overzoom {
self.tiles_at_maxzoom_so_far
.push((self.x as u32, self.y as u32));
}
}
Ok(())
}
fn next_overzoom(&mut self) {
self.zoom += 1;
self.overzoomed_tiles.clear();
self.ready.clear();
let scale: i64 = 1i64.wrapping_shl((self.zoom + 1) as u32)
/ 1i64.wrapping_shl((self.maxzoom_so_far + 1) as u32);
if self.zoom == self.maxzoom_so_far as i64 + 1 {
for xy in &self.tiles_at_maxzoom_so_far {
for xx in 0..scale {
for yy in 0..scale {
self.overzoomed_tiles.push((
(xy.0 as i64 * scale + xx) as u32,
(xy.1 as i64 * scale + yy) as u32,
));
}
}
}
} else {
self.overzoomed_tiles = std::mem::take(&mut self.next_overzoomed_tiles);
}
self.overzoomed_tiles.sort_by(tilecmp);
self.overzoom_consumed_at_this_zoom = false;
}
fn make_overzoomed(&mut self, s: &Settings) -> Result<()> {
let n = self.overzoomed_tiles.len().min(OVERZOOM_BATCH);
let tiles: Vec<(u32, u32)> = self
.overzoomed_tiles
.iter()
.rev()
.take(n)
.copied()
.collect();
let z = self.zoom;
let maxzoom = self.maxzoom_so_far as i64;
let parent_of = |xy: &(u32, u32)| {
let (mut pz, mut px, mut py) = (z, xy.0 as i64, xy.1 as i64);
while pz > maxzoom {
pz -= 1;
px /= 2;
py /= 2;
}
(pz, px, py)
};
let parents: BTreeSet<Zxy> = tiles.iter().map(parent_of).collect();
let source = self.source;
let fetched: Vec<Result<(Zxy, Vec<u8>)>> = parents
.into_par_iter()
.map(|p| Ok((p, parent_tile(source, p)?)))
.collect();
let mut bytes: HashMap<Zxy, Vec<u8>> = HashMap::new();
for f in fetched {
let (p, b) = f?;
bytes.insert(p, b);
}
let mut parents: HashMap<Zxy, Decoded<'_>> = HashMap::new();
for (p, b) in &bytes {
let decoded = Decoded::decode(b).map_err(|_| {
Error::new(
EXIT_PROTOBUF,
format!("PBF decoding error in tile {}/{}/{}", p.0, p.1, p.2),
)
})?;
parents.insert(*p, decoded);
}
let made: Vec<Result<Made>> = tiles
.par_iter()
.map(|xy| {
let p = parent_of(xy);
let parent = &parents[&p];
let mut children = Vec::new();
let data = if parent.layers.is_empty() {
Vec::new()
} else {
overzoom(
parent,
(p.0 as i32, p.1, p.2),
(z as i32, xy.0 as i64, xy.1 as i64),
s.buffer,
&mut children,
)?
};
Ok(Made {
xy: *xy,
data: data.into(),
children,
})
})
.collect();
for m in made {
self.ready.push_back(m?);
}
Ok(())
}
fn lt(&mut self, r: &mut Reader<'_>, s: &Settings) -> Result<bool> {
if self.zoom < r.zoom {
return Ok(true);
}
if self.zoom > r.zoom {
return Ok(false);
}
if self.x < r.x {
return Ok(true);
}
if self.x > r.x {
return Ok(false);
}
let sorty = 1i64
.wrapping_shl(self.zoom as u32)
.wrapping_sub(1)
.wrapping_sub(self.y) as i32;
let r_sorty = 1i64
.wrapping_shl(r.zoom as u32)
.wrapping_sub(1)
.wrapping_sub(r.y) as i32;
if sorty < r_sorty {
return Ok(true);
}
if sorty > r_sorty {
return Ok(false);
}
let a = self.key(s)?;
let b = r.key(s)?;
Ok(cmp(a, b) == Ordering::Less)
}
}
fn parent_tile(source: &Source, (z, x, y): Zxy) -> Result<Vec<u8>> {
let data = source.get_tile(z, x, y)?;
if !is_compressed(&data) {
return Ok(data);
}
let mut buf = Vec::new();
let mut d = libdeflater::Decompressor::new();
if !decompress(&mut d, &data, &mut buf) {
return Err(Error::new(tippecanoe::errors::EXIT_MVT, String::new()));
}
Ok(buf)
}
pub struct Group {
pub z: i64,
pub x: i64,
pub y: i64,
pub members: Vec<(usize, TileRef)>,
}
pub struct Queue<'s> {
pub readers: Vec<Reader<'s>>,
pub order: Vec<usize>,
prefetched: Option<Option<Place>>,
}
type Place = (i64, i64, i32);
fn place(z: i64, x: i64, y: i64) -> Place {
(
z,
x,
1i64.wrapping_shl(z as u32).wrapping_sub(1).wrapping_sub(y) as i32,
)
}
const PREFETCH_BYTES: u64 = 16 << 20;
const PREFETCH_TILES: usize = 16384;
impl<'s> Queue<'s> {
pub fn new() -> Queue<'s> {
Queue {
readers: Vec::new(),
order: Vec::new(),
prefetched: None,
}
}
fn covered(&self, p: Place) -> bool {
match self.prefetched {
Some(None) => true,
Some(Some(bound)) => p <= bound,
None => false,
}
}
fn prefetch(&mut self, s: &Settings) -> Result<()> {
let mut bound: Option<Place> = None;
for r in self.readers.iter_mut() {
if r.done {
continue;
}
let (mut n, mut bytes) = (0usize, 0u64);
loop {
while n < r.pending.len() && n < PREFETCH_TILES && bytes < PREFETCH_BYTES {
bytes += r.pending[n].size();
n += 1;
}
if n < r.pending.len() || n >= PREFETCH_TILES || bytes >= PREFETCH_BYTES {
break;
}
if !r.read_more() {
break;
}
}
if n < r.pending.len() || !r.exhausted {
if let Some(t) = r.pending.get(n.saturating_sub(1)) {
let p = place(t.z, t.x, t.y);
bound = Some(bound.map_or(p, |b| b.min(p)));
} else {
bound = Some(
bound.map_or(place(r.zoom, r.x, r.y), |b| b.min(place(r.zoom, r.x, r.y))),
);
}
}
}
let mut tiles: Vec<(Place, usize, u64, TileRef)> = Vec::new();
for (i, r) in self.readers.iter().enumerate() {
if let Some(q) = r.seq
&& !r.done
{
tiles.push((place(r.zoom, r.x, r.y), i, q, r.tile.clone()));
}
for (k, t) in r.pending.iter().enumerate() {
let p = place(t.z, t.x, t.y);
if bound.is_some_and(|b| p > b) {
break;
}
tiles.push((p, i, r.next_seq + k as u64, t.clone()));
}
}
tiles.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(&b.1)));
let mut jobs = Vec::new();
let mut i = 0;
while i < tiles.len() {
let mut j = i + 1;
while j < tiles.len() && tiles[j].0 == tiles[i].0 {
j += 1;
}
if j - i > 1 {
for t in &tiles[i..j] {
let r = &self.readers[t.1];
let known =
r.cache.contains_key(&t.2) || (r.seq == Some(t.2) && r.key.is_some());
if !known {
jobs.push((t.1, t.2, &t.3));
}
}
}
i = j;
}
let readers = &self.readers;
let keys: Vec<Result<(usize, u64, Key)>> = jobs
.par_iter()
.map(|&(r, q, t)| {
let source = readers[r].source;
let data = source.data(t)?.shared();
Ok((
r,
q,
Key::new(data, source.tippecanoe_made, s.tie_break).forced(),
))
})
.collect();
for k in keys {
let (r, q, key) = k?;
self.readers[r].cache.insert(q, key);
}
self.prefetched = Some(bound);
Ok(())
}
pub fn insert(&mut self, r: usize, s: &Settings) -> Result<()> {
let p = place(self.readers[r].zoom, self.readers[r].x, self.readers[r].y);
let ties = self.order.iter().any(|&here| {
let h = &self.readers[here];
place(h.zoom, h.x, h.y) == p && (!h.has_key() || !self.readers[r].has_key())
});
if ties && self.readers[r].seq.is_some() && !self.covered(p) {
self.prefetch(s)?;
}
let mut at = self.order.len();
for (i, &here) in self.order.iter().enumerate() {
let (a, b) = two(&mut self.readers, r, here);
if a.lt(b, s)? {
at = i;
break;
}
}
self.order.insert(at, r);
Ok(())
}
pub fn add(&mut self, reader: Reader<'s>, s: &Settings) -> Result<()> {
self.readers.push(reader);
self.insert(self.readers.len() - 1, s)
}
fn all_done(&self) -> bool {
self.readers.iter().all(|r| r.finished())
}
pub fn run(
&mut self,
s: &Settings,
minzoom: i32,
maxzoom: i32,
limit: usize,
out: &mut Vec<Group>,
) -> Result<bool> {
loop {
if self.order.is_empty() || self.all_done() {
return Ok(false);
}
if out.len() >= limit {
let r = &self.readers[self.order[0]];
let last = &out[out.len() - 1];
if !(r.zoom == last.z && r.x == last.x && r.y == last.y) {
return Ok(true);
}
}
let head = self.order.remove(0);
let (z, x, y, tile) = self.readers[head].current();
if z >= minzoom as i64 && z <= maxzoom as i64 {
match out.last_mut() {
Some(g) if g.z == z && g.x == x && g.y == y => {
g.members.push((self.readers[head].index, tile))
}
_ => out.push(Group {
z,
x,
y,
members: vec![(self.readers[head].index, tile)],
}),
}
}
self.readers[head].advance(s)?;
self.insert(head, s)?;
}
}
}
impl Default for Queue<'_> {
fn default() -> Self {
Queue::new()
}
}
fn two<'a, 's>(
readers: &'a mut [Reader<'s>],
a: usize,
b: usize,
) -> (&'a mut Reader<'s>, &'a mut Reader<'s>) {
assert_ne!(a, b);
if a < b {
let (l, r) = readers.split_at_mut(b);
(&mut l[a], &mut r[0])
} else {
let (l, r) = readers.split_at_mut(a);
(&mut r[0], &mut l[b])
}
}