Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_geom/src/mvt.rs

20.6 KiB, 1 run

created by r1870400018:60369, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Mapbox Vector Tiles: the protocol buffer a street map arrives in, decoded.
2//!
3//! A tile is layers; a layer is features, a table of keys and a table of values; a feature is
4//! a geometry type, pairs of indices into those tables, and a run of geometry commands in tile
5//! coordinates, conventionally 0 to 4096 with `y` downward. The format is version 2.1 of the
6//! specification at <https://github.com/mapbox/vector-tile-spec>, and version 1 is read too.
7//!
8//! [`decode`] reads the message structure and checks it; a feature's geometry and properties
9//! are resolved when asked for ([`Feature::geometry`], [`Feature::properties`]), because a
10//! painter at a given zoom draws a fraction of what a tile carries. The decoder is held to the
11//! specification's own fixtures (`@mapbox/mvt-fixtures`) and to real Protomaps tiles decoded by
12//! the reference JavaScript decoder.
13//!
14//! What counts as malformed follows those fixtures: a field of the wrong wire type, a value of
15//! an unknown kind or of none, a layer with no name or version or of a version other than 1 or
16//! 2, a tag pointing past its table, and a geometry command whose count runs past the
17//! parameters that follow it are all refused, and a count is never trusted to size an
18//! allocation.
19
20use oxedyne_fe2o3_core::prelude::*;
21
22// ---------------------------------------------------------------------------------------------
23// Protocol buffer wire format
24// ---------------------------------------------------------------------------------------------
25
26const WIRE_VARINT: u8 = 0;
27const WIRE_I64: u8 = 1;
28const WIRE_LEN: u8 = 2;
29const WIRE_I32: u8 = 5;
30
31/// A cursor over protocol buffer bytes.
32struct Pb<'a> {
33 buf: &'a [u8],
34 pos: usize,
35}
36
37impl<'a> Pb<'a> {
38 fn new(buf: &'a [u8]) -> Self { Self { buf, pos: 0 } }
39
40 fn done(&self) -> bool { self.pos >= self.buf.len() }
41
42 fn varint(&mut self) -> Outcome<u64> {
43 let mut v: u64 = 0;
44 let mut shift = 0u32;
45 loop {
46 let b = match self.buf.get(self.pos) {
47 Some(b) => *b,
48 None => return Err(err!("A varint runs off the end of the buffer at byte {}.",
49 self.pos; Invalid, Input, Decode)),
50 };
51 self.pos += 1;
52 if shift >= 64 {
53 return Err(err!("A varint at byte {} is longer than ten bytes.", self.pos;
54 Invalid, Input, Decode));
55 }
56 v |= ((b & 0x7f) as u64) << shift;
57 if b < 0x80 {
58 return Ok(v);
59 }
60 shift += 7;
61 }
62 }
63
64 /// A field's number and wire type.
65 fn key(&mut self) -> Outcome<(u32, u8)> {
66 let k = res!(self.varint());
67 Ok(((k >> 3) as u32, (k & 7) as u8))
68 }
69
70 fn bytes(&mut self) -> Outcome<&'a [u8]> {
71 let n = res!(self.varint()) as usize;
72 let end = match self.pos.checked_add(n) {
73 Some(e) if e <= self.buf.len() => e,
74 _ => return Err(err!("A field of {} bytes at byte {} runs past the {} there are.",
75 n, self.pos, self.buf.len(); Invalid, Input, Decode)),
76 };
77 let out = &self.buf[self.pos..end];
78 self.pos = end;
79 Ok(out)
80 }
81
82 fn fixed(&mut self, n: usize) -> Outcome<&'a [u8]> {
83 match self.buf.get(self.pos..self.pos + n) {
84 Some(b) => {
85 self.pos += n;
86 Ok(b)
87 },
88 None => Err(err!("A {}-byte field at byte {} runs off the end.", n, self.pos;
89 Invalid, Input, Decode)),
90 }
91 }
92
93 fn skip(&mut self, wire: u8) -> Outcome<()> {
94 match wire {
95 WIRE_VARINT => { res!(self.varint()); },
96 WIRE_I64 => { res!(self.fixed(8)); },
97 WIRE_LEN => { res!(self.bytes()); },
98 WIRE_I32 => { res!(self.fixed(4)); },
99 _ => return Err(err!("Wire type {} at byte {} is not one this reads.", wire, self.pos;
100 Invalid, Input, Decode)),
101 }
102 Ok(())
103 }
104
105 /// A packed repeated `uint32`, or one element of an unpacked one.
106 fn u32s(&mut self, wire: u8, out: &mut Vec<u32>, what: &str) -> Outcome<()> {
107 match wire {
108 WIRE_LEN => {
109 let mut inner = Pb::new(res!(self.bytes()));
110 while !inner.done() {
111 out.push(res!(u32_of(res!(inner.varint()), what)));
112 }
113 },
114 WIRE_VARINT => out.push(res!(u32_of(res!(self.varint()), what))),
115 _ => return Err(err!("{} has wire type {}, not a packed integer.", what, wire;
116 Invalid, Input, Decode)),
117 }
118 Ok(())
119 }
120}
121
122fn u32_of(v: u64, what: &str) -> Outcome<u32> {
123 if v > u32::MAX as u64 {
124 return Err(err!("{} holds {}, more than 32 bits.", what, v; Invalid, Input, Decode));
125 }
126 Ok(v as u32)
127}
128
129fn want(wire: u8, expected: u8, what: &str) -> Outcome<()> {
130 if wire != expected {
131 return Err(err!("{} has wire type {}, not {}.", what, wire, expected; Invalid, Input, Decode));
132 }
133 Ok(())
134}
135
136fn zigzag(v: u64) -> i64 { ((v >> 1) as i64) ^ -((v & 1) as i64) }
137
138fn text(b: &[u8], what: &str) -> Outcome<String> {
139 match std::str::from_utf8(b) {
140 Ok(s) => Ok(s.to_string()),
141 Err(_) => Err(err!("{} is not UTF-8.", what; Invalid, Input, Decode, UTF8)),
142 }
143}
144
145// ---------------------------------------------------------------------------------------------
146// The tile
147// ---------------------------------------------------------------------------------------------
148
149/// A feature's geometry type.
150#[derive(Clone, Copy, Debug, PartialEq, Eq)]
151pub enum GeomKind {
152 Unknown,
153 Point,
154 LineString,
155 Polygon,
156}
157
158impl GeomKind {
159 /// The number the protocol buffer carries: 0 to 3.
160 pub fn code(self) -> u32 {
161 match self {
162 Self::Unknown => 0,
163 Self::Point => 1,
164 Self::LineString => 2,
165 Self::Polygon => 3,
166 }
167 }
168}
169
170/// A property value.
171#[derive(Clone, Debug, PartialEq)]
172pub enum Value {
173 Str(String),
174 Float(f32),
175 Double(f64),
176 Int(i64),
177 Uint(u64),
178 Sint(i64),
179 Bool(bool),
180}
181
182impl Value {
183 /// The value as a number, for any numeric kind and for a boolean as 0 or 1.
184 pub fn as_f64(&self) -> Option<f64> {
185 match self {
186 Self::Str(_) => None,
187 Self::Float(v) => Some(*v as f64),
188 Self::Double(v) => Some(*v),
189 Self::Int(v) => Some(*v as f64),
190 Self::Uint(v) => Some(*v as f64),
191 Self::Sint(v) => Some(*v as f64),
192 Self::Bool(v) => Some(if *v { 1.0 } else { 0.0 }),
193 }
194 }
195
196 pub fn as_str(&self) -> Option<&str> {
197 match self {
198 Self::Str(s) => Some(s),
199 _ => None,
200 }
201 }
202}
203
204/// One feature, its geometry still as commands.
205#[derive(Clone, Debug, PartialEq)]
206pub struct Feature {
207 pub id: Option<u64>,
208 pub kind: GeomKind,
209 pub tags: Vec<u32>, // key index, value index, key index, ...
210 pub geometry: Vec<u32>, // command integers and zig-zag parameters
211}
212
213/// One layer of a tile.
214#[derive(Clone, Debug, PartialEq)]
215pub struct Layer {
216 pub version: u32,
217 pub name: String,
218 pub extent: u32, // tile coordinates across, 4096 by default
219 pub keys: Vec<String>,
220 pub values: Vec<Value>,
221 pub features: Vec<Feature>,
222}
223
224impl Layer {
225 /// The value of one property of a feature of this layer, if it has it.
226 pub fn property(&self, feature: &Feature, key: &str) -> Option<&Value> {
227 for pair in feature.tags.chunks(2) {
228 if pair.len() == 2 {
229 if let (Some(k), Some(v)) = (self.keys.get(pair[0] as usize), self.values.get(pair[1] as usize)) {
230 if k == key {
231 return Some(v);
232 }
233 }
234 }
235 }
236 None
237 }
238}
239
240/// A decoded tile: its layers in the order the tile holds them.
241#[derive(Clone, Debug, Default, PartialEq)]
242pub struct Tile {
243 pub layers: Vec<Layer>,
244}
245
246impl Tile {
247 pub fn layer(&self, name: &str) -> Option<&Layer> {
248 self.layers.iter().find(|l| l.name == name)
249 }
250}
251
252/// Decodes a tile's message structure: layers, their tables and their features.
253///
254/// The bytes are the tile itself, not gzipped; a PMTiles archive says how its tiles are
255/// compressed ([`crate::tile::pmtiles::decompress`]).
256pub fn decode(bytes: &[u8]) -> Outcome<Tile> {
257 let mut pb = Pb::new(bytes);
258 let mut tile = Tile::default();
259 while !pb.done() {
260 let (field, wire) = res!(pb.key());
261 match field {
262 3 => {
263 res!(want(wire, WIRE_LEN, "A layer"));
264 let n = tile.layers.len();
265 tile.layers.push(res!(layer(res!(pb.bytes()), n)));
266 },
267 _ => res!(pb.skip(wire)),
268 }
269 }
270 Ok(tile)
271}
272
273fn layer(buf: &[u8], index: usize) -> Outcome<Layer> {
274 let mut pb = Pb::new(buf);
275 let mut version: Option<u32> = None;
276 let mut name: Option<String> = None;
277 let mut extent = 4096u32;
278 let mut keys = Vec::new();
279 let mut values = Vec::new();
280 let mut features = Vec::new();
281 while !pb.done() {
282 let (field, wire) = res!(pb.key());
283 match field {
284 15 => {
285 res!(want(wire, WIRE_VARINT, "A layer's version"));
286 version = Some(res!(u32_of(res!(pb.varint()), "A layer's version")));
287 },
288 1 => {
289 res!(want(wire, WIRE_LEN, "A layer's name"));
290 name = Some(res!(text(res!(pb.bytes()), "A layer's name")));
291 },
292 2 => {
293 res!(want(wire, WIRE_LEN, "A feature"));
294 features.push(res!(feature(res!(pb.bytes()))));
295 },
296 3 => {
297 res!(want(wire, WIRE_LEN, "A layer key"));
298 keys.push(res!(text(res!(pb.bytes()), "A layer key")));
299 },
300 4 => {
301 res!(want(wire, WIRE_LEN, "A layer value"));
302 values.push(res!(value(res!(pb.bytes()))));
303 },
304 5 => {
305 res!(want(wire, WIRE_VARINT, "A layer's extent"));
306 extent = res!(u32_of(res!(pb.varint()), "A layer's extent"));
307 },
308 _ => res!(pb.skip(wire)),
309 }
310 }
311 let name = match name {
312 Some(n) => n,
313 None => return Err(err!("Layer {} has no name.", index; Invalid, Input, Decode, Missing)),
314 };
315 let version = match version {
316 Some(v @ 1) | Some(v @ 2) => v,
317 Some(v) => return Err(err!("Layer {:?} is version {}; versions 1 and 2 exist.", name, v;
318 Invalid, Input, Decode, Version)),
319 None => return Err(err!("Layer {:?} has no version.", name; Invalid, Input, Decode, Missing)),
320 };
321 Ok(Layer { version, name, extent, keys, values, features })
322}
323
324fn feature(buf: &[u8]) -> Outcome<Feature> {
325 let mut pb = Pb::new(buf);
326 let mut f = Feature { id: None, kind: GeomKind::Unknown, tags: Vec::new(), geometry: Vec::new() };
327 while !pb.done() {
328 let (field, wire) = res!(pb.key());
329 match field {
330 1 => {
331 res!(want(wire, WIRE_VARINT, "A feature's id"));
332 f.id = Some(res!(pb.varint()));
333 },
334 2 => res!(pb.u32s(wire, &mut f.tags, "A feature's tags")),
335 3 => {
336 res!(want(wire, WIRE_VARINT, "A feature's type"));
337 // An unknown type is kept as unknown, as a proto2 enum would be.
338 f.kind = match res!(pb.varint()) {
339 1 => GeomKind::Point,
340 2 => GeomKind::LineString,
341 3 => GeomKind::Polygon,
342 _ => GeomKind::Unknown,
343 };
344 },
345 4 => res!(pb.u32s(wire, &mut f.geometry, "A feature's geometry")),
346 _ => res!(pb.skip(wire)),
347 }
348 }
349 Ok(f)
350}
351
352fn value(buf: &[u8]) -> Outcome<Value> {
353 let mut pb = Pb::new(buf);
354 let mut out: Option<Value> = None;
355 while !pb.done() {
356 let (field, wire) = res!(pb.key());
357 let v = match field {
358 1 => {
359 res!(want(wire, WIRE_LEN, "A string value"));
360 Value::Str(res!(text(res!(pb.bytes()), "A string value")))
361 },
362 2 => {
363 res!(want(wire, WIRE_I32, "A float value"));
364 let b = res!(pb.fixed(4));
365 Value::Float(f32::from_le_bytes([b[0], b[1], b[2], b[3]]))
366 },
367 3 => {
368 res!(want(wire, WIRE_I64, "A double value"));
369 let b = res!(pb.fixed(8));
370 Value::Double(f64::from_le_bytes([b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]]))
371 },
372 4 => {
373 res!(want(wire, WIRE_VARINT, "An int value"));
374 Value::Int(res!(pb.varint()) as i64)
375 },
376 5 => {
377 res!(want(wire, WIRE_VARINT, "A uint value"));
378 Value::Uint(res!(pb.varint()))
379 },
380 6 => {
381 res!(want(wire, WIRE_VARINT, "A sint value"));
382 Value::Sint(zigzag(res!(pb.varint())))
383 },
384 7 => {
385 res!(want(wire, WIRE_VARINT, "A bool value"));
386 Value::Bool(res!(pb.varint()) != 0)
387 },
388 other => return Err(err!("A value has field {}, which is no kind of value.", other;
389 Invalid, Input, Decode)),
390 };
391 if out.is_some() {
392 return Err(err!("A value holds more than one kind of value."; Invalid, Input, Decode));
393 }
394 out = Some(v);
395 }
396 match out {
397 Some(v) => Ok(v),
398 None => Err(err!("A value holds no value."; Invalid, Input, Decode, Missing)),
399 }
400}
401
402// ---------------------------------------------------------------------------------------------
403// Geometry and properties
404// ---------------------------------------------------------------------------------------------
405
406const CMD_MOVE_TO: u32 = 1;
407const CMD_LINE_TO: u32 = 2;
408const CMD_CLOSE_PATH: u32 = 7;
409
410impl Feature {
411 /// The geometry in tile coordinates: one run of points per `MoveTo`.
412 ///
413 /// A point feature's runs are single points; a line's are its lines; a polygon's are its
414 /// rings, each closed by repeating its first point, exterior rings wound clockwise on a
415 /// `y`-down screen and holes the other way, so a nonzero fill paints them right. Positions
416 /// accumulate with 32-bit wrapping, as the specification's overflow fixtures expect.
417 pub fn geometry(&self) -> Outcome<Vec<Vec<(i32, i32)>>> {
418 let g = &self.geometry;
419 let mut out: Vec<Vec<(i32, i32)>> = Vec::new();
420 let (mut x, mut y) = (0i32, 0i32);
421 let mut i = 0usize;
422 while i < g.len() {
423 let cmd = g[i] & 7;
424 let count = (g[i] >> 3) as usize;
425 i += 1;
426 match cmd {
427 CMD_MOVE_TO | CMD_LINE_TO => {
428 // A count is checked against what follows before anything is sized by it.
429 let left = (g.len() - i) / 2;
430 if count > left {
431 return Err(err!("A command at {} asks for {} points and {} follow.",
432 i - 1, count, left; Invalid, Input, Decode));
433 }
434 if count == 0 {
435 return Err(err!("A command at {} has a count of nought.", i - 1;
436 Invalid, Input, Decode));
437 }
438 if cmd == CMD_LINE_TO && out.last().map_or(true, |r| r.is_empty()) {
439 return Err(err!("A LineTo at {} comes before any MoveTo.", i - 1;
440 Invalid, Input, Decode));
441 }
442 for _ in 0..count {
443 x = x.wrapping_add(zigzag(g[i] as u64) as i32);
444 y = y.wrapping_add(zigzag(g[i + 1] as u64) as i32);
445 i += 2;
446 if cmd == CMD_MOVE_TO {
447 out.push(vec![(x, y)]);
448 } else if let Some(r) = out.last_mut() {
449 r.push((x, y));
450 }
451 }
452 },
453 CMD_CLOSE_PATH => {
454 if count != 1 {
455 return Err(err!("A ClosePath at {} has a count of {}, not one.", i - 1, count;
456 Invalid, Input, Decode));
457 }
458 if self.kind != GeomKind::Polygon {
459 return Err(err!("A ClosePath at {} in a {:?} feature.", i - 1, self.kind;
460 Invalid, Input, Decode));
461 }
462 match out.last_mut() {
463 Some(r) if !r.is_empty() => {
464 let first = r[0];
465 r.push(first);
466 },
467 _ => return Err(err!("A ClosePath at {} closes nothing.", i - 1;
468 Invalid, Input, Decode)),
469 }
470 },
471 other => return Err(err!("Command {} at {} is not MoveTo, LineTo or ClosePath.",
472 other, i - 1; Invalid, Input, Decode)),
473 }
474 }
475 Ok(out)
476 }
477
478 /// The feature's properties, as its layer's keys and values, in the order its tags list
479 /// them.
480 pub fn properties<'a>(&'a self, layer: &'a Layer) -> Outcome<Vec<(&'a str, &'a Value)>> {
481 if self.tags.len() % 2 != 0 {
482 return Err(err!("A feature has {} tags, which do not pair.", self.tags.len();
483 Invalid, Input, Decode));
484 }
485 let mut out = Vec::with_capacity(self.tags.len() / 2);
486 for pair in self.tags.chunks(2) {
487 let k = match layer.keys.get(pair[0] as usize) {
488 Some(k) => k,
489 None => return Err(err!("A tag names key {} of the {} layer {:?} has.",
490 pair[0], layer.keys.len(), layer.name; Invalid, Input, Decode, Index)),
491 };
492 let v = match layer.values.get(pair[1] as usize) {
493 Some(v) => v,
494 None => return Err(err!("A tag names value {} of the {} layer {:?} has.",
495 pair[1], layer.values.len(), layer.name; Invalid, Input, Decode, Index)),
496 };
497 out.push((k.as_str(), v));
498 }
499 Ok(out)
500 }
501}
502
503// ---------------------------------------------------------------------------------------------
504// Style classes
505// ---------------------------------------------------------------------------------------------
506
507/// A painter's rule: features of a layer, optionally only those whose `key` property is one of
508/// `values`, drawn from `min_zoom` on, belong to `class`.
509#[derive(Clone, Debug, PartialEq)]
510pub struct StyleRule {
511 pub layer: String,
512 pub key: String, // the property that says what a feature is: `kind`, `class`
513 pub values: Vec<String>, // empty for any
514 pub min_zoom: u8,
515 pub class: u16,
516}
517
518/// Sorts a tile's features into a painter's classes: `(class, layer index, feature index)` for
519/// every feature some rule takes, the first matching rule deciding, in rule order and then
520/// tile order, which is the order a painter draws them in.
521///
522/// `feature_min_zoom` names a per-feature property, as Protomaps' `min_zoom`, below which a
523/// feature is not yet drawn even where its rule would take it.
524pub fn classify(tile: &Tile, rules: &[StyleRule], zoom: u8, feature_min_zoom: Option<&str>)
525 -> Vec<(u16, usize, usize)>
526{
527 let mut hits: Vec<(usize, u16, usize, usize)> = Vec::new();
528 for (li, layer) in tile.layers.iter().enumerate() {
529 for (fi, f) in layer.features.iter().enumerate() {
530 if let Some(key) = feature_min_zoom {
531 if let Some(mz) = layer.property(f, key).and_then(|v| v.as_f64()) {
532 if mz > zoom as f64 {
533 continue;
534 }
535 }
536 }
537 for (ri, rule) in rules.iter().enumerate() {
538 if rule.layer != layer.name || zoom < rule.min_zoom {
539 continue;
540 }
541 if !rule.values.is_empty() {
542 let kind = layer.property(f, &rule.key).and_then(|v| v.as_str());
543 if !kind.map_or(false, |k| rule.values.iter().any(|v| v == k)) {
544 continue;
545 }
546 }
547 hits.push((ri, rule.class, li, fi));
548 break;
549 }
550 }
551 }
552 hits.sort_by_key(|h| (h.0, h.2, h.3));
553 hits.into_iter().map(|(_, c, l, f)| (c, l, f)).collect()
554}