Tags Data Structure

[droogmic]

https://wiki.openstreetmap.org/wiki/Tags

Requirements

Key

A key type, at its simplest it could be a &'static str or String. See also: https://lib.rs/crates/kstring.

• No heap usage when using &'static strs.
• Add trait implemented to support : joined keys (i.e. A + B + C == "a:b:c")

Value

A value type, at its simplest it could be a &'static str or String. Trait implemented to support ; joined keys. The result should also resemble an iterable. Example: [A, B, C].into() == "a;b;c".

Mapping

Support interaction mimicking a HashMap or BTreeMap <K, V>, for example:

• fn get<Q>(&self, key: &Q) -> Option<V>
• fn is<Q, U>(&self, key: &Q, value: &U) -> bool
• fn is_any<Q, W>(&self, key: &Q, values: &W) -> bool

Arguments of type Q should be possible directly from a &'static str, .e.g. tags.get("highway").

Tree

Support access as a tree structure, for : separated keys. Example:

// foo:bar:baz=toto
tags.tree().get("foo").unwrap().get("bar").unwrap().is("baz", "toto")

Performance Constraints

In addition to the constraints on the key (see kstring):

• The data must be stored once (not both as a tree and as a map, as is currently done)
• The data may not be stored as a naive map, as retrieving a key of foo:bar using foo will be O(N).
• Retrieving a multi-part key must not incur a runtime : split cost when not needed, i.e. get("foo" + "bar") must not allocate a String("foo:bar") which is then .split_once(':').

Deployment

For now, this should replace https://github.com/a-b-street/osm2lanes/tree/main/rust/osm2lanes/src/tag. Once proven, a separate crate should be made.

[droogmic]

for key types: https://github.com/epage/string-benchmarks-rs

Suggestions:

• Generally, String
• If you deal mostly with string literals but want some flexibility (like clap), generally you'll want Cow<'static, str>
• If a profiler says your strings are a problem: Try different crates and settings for that crate out with a profiler O(1) clones are important when doing a lot of clones. For one-off allocations, they are slower. For short-lived programs, look into string interning