1 #pragma once
2
3 #include "vector_tile/vector_tile_config.hpp"
4 #include <mapbox/geometry.hpp>
5 #include <protozero/pbf_reader.hpp>
6
7 #include <cmath>
8 #include <cstdint>
9 #include <map>
10 #include <functional> // reference_wrapper
11 #include <string>
12 #include <stdexcept>
13
14 #include <experimental/optional>
15
16 template <typename T>
17 using optional = std::experimental::optional<T>;
18
19 namespace mapbox { namespace vector_tile {
20
21 using point_type = mapbox::geometry::point<std::int16_t>;
22
23 class points_array_type : public std::vector<point_type> {
24 public:
25 using coordinate_type = point_type::coordinate_type;
26 template <class... Args>
points_array_type(Args &&...args)27 points_array_type(Args&&... args) : std::vector<point_type>(std::forward<Args>(args)...) {}
28 };
29
30 class points_arrays_type : public std::vector<points_array_type> {
31 public:
32 using coordinate_type = points_array_type::coordinate_type;
33 template <class... Args>
points_arrays_type(Args &&...args)34 points_arrays_type(Args&&... args) : std::vector<points_array_type>(std::forward<Args>(args)...) {}
35 };
36
37 class layer;
38
39 class feature {
40 public:
41 using properties_type = mapbox::geometry::property_map;
42 using packed_iterator_type = protozero::iterator_range<protozero::pbf_reader::const_uint32_iterator>;
43
44 feature(protozero::data_view const&, layer const&);
45
getType() const46 GeomType getType() const { return type; }
47 optional<mapbox::geometry::value> getValue(std::string const&) const;
48 properties_type getProperties() const;
49 optional<mapbox::geometry::identifier> const& getID() const;
50 std::uint32_t getExtent() const;
51 std::uint32_t getVersion() const;
52 template <typename GeometryCollectionType>
53 GeometryCollectionType getGeometries(float scale) const;
54
55 private:
56 const layer& layer_;
57 optional<mapbox::geometry::identifier> id;
58 GeomType type = GeomType::UNKNOWN;
59 packed_iterator_type tags_iter;
60 packed_iterator_type geometry_iter;
61 };
62
63 class layer {
64 public:
65 layer(protozero::data_view const& layer_view);
66
featureCount() const67 std::size_t featureCount() const { return features.size(); }
68 protozero::data_view const& getFeature(std::size_t) const;
69 std::string const& getName() const;
getExtent() const70 std::uint32_t getExtent() const { return extent; }
getVersion() const71 std::uint32_t getVersion() const { return version; }
72
73 private:
74 friend class feature;
75
76 std::string name;
77 std::uint32_t version;
78 std::uint32_t extent;
79 std::map<std::string, std::uint32_t> keysMap;
80 std::vector<std::reference_wrapper<const std::string>> keys;
81 std::vector<protozero::data_view> values;
82 std::vector<protozero::data_view> features;
83 };
84
85 class buffer {
86 public:
87 buffer(std::string const& data);
88 std::vector<std::string> layerNames() const;
getLayers() const89 std::map<std::string, const protozero::data_view> getLayers() const { return layers; };
90 layer getLayer(const std::string&) const;
91
92 private:
93 std::map<std::string, const protozero::data_view> layers;
94 };
95
parseValue(protozero::data_view const & value_view)96 static mapbox::geometry::value parseValue(protozero::data_view const& value_view) {
97 mapbox::geometry::value value;
98 protozero::pbf_reader value_reader(value_view);
99 while (value_reader.next())
100 {
101 switch (value_reader.tag()) {
102 case ValueType::STRING:
103 value = value_reader.get_string();
104 break;
105 case ValueType::FLOAT:
106 value = static_cast<double>(value_reader.get_float());
107 break;
108 case ValueType::DOUBLE:
109 value = value_reader.get_double();
110 break;
111 case ValueType::INT:
112 value = value_reader.get_int64();
113 break;
114 case ValueType::UINT:
115 value = value_reader.get_uint64();
116 break;
117 case ValueType::SINT:
118 value = value_reader.get_sint64();
119 break;
120 case ValueType::BOOL:
121 value = value_reader.get_bool();
122 break;
123 default:
124 value_reader.skip();
125 break;
126 }
127 }
128 return value;
129 }
130
feature(protozero::data_view const & feature_view,layer const & l)131 inline feature::feature(protozero::data_view const& feature_view, layer const& l)
132 : layer_(l),
133 id(),
134 type(GeomType::UNKNOWN),
135 tags_iter(),
136 geometry_iter()
137 {
138 protozero::pbf_reader feature_pbf(feature_view);
139 while (feature_pbf.next()) {
140 switch (feature_pbf.tag()) {
141 case FeatureType::ID:
142 id = optional<mapbox::geometry::identifier>{ feature_pbf.get_uint64() };
143 break;
144 case FeatureType::TAGS:
145 tags_iter = feature_pbf.get_packed_uint32();
146 break;
147 case FeatureType::TYPE:
148 type = static_cast<GeomType>(feature_pbf.get_enum());
149 break;
150 case FeatureType::GEOMETRY:
151 geometry_iter = feature_pbf.get_packed_uint32();
152 break;
153 default:
154 feature_pbf.skip();
155 break;
156 }
157 }
158 }
159
getValue(const std::string & key) const160 inline optional<mapbox::geometry::value> feature::getValue(const std::string& key) const {
161 auto keyIter = layer_.keysMap.find(key);
162 if (keyIter == layer_.keysMap.end()) {
163 return optional<mapbox::geometry::value>();
164 }
165
166 const auto values_count = layer_.values.size();
167 const auto keymap_count = layer_.keysMap.size();
168 auto start_itr = tags_iter.begin();
169 const auto end_itr = tags_iter.end();
170 while (start_itr != end_itr) {
171 std::uint32_t tag_key = static_cast<std::uint32_t>(*start_itr++);
172
173 if (keymap_count <= tag_key) {
174 throw std::runtime_error("feature referenced out of range key");
175 }
176
177 if (start_itr == end_itr) {
178 throw std::runtime_error("uneven number of feature tag ids");
179 }
180
181 std::uint32_t tag_val = static_cast<std::uint32_t>(*start_itr++);;
182 if (values_count <= tag_val) {
183 throw std::runtime_error("feature referenced out of range value");
184 }
185
186 if (tag_key == keyIter->second) {
187 return parseValue(layer_.values[tag_val]);
188 }
189 }
190
191 return optional<mapbox::geometry::value>();
192 }
193
getProperties() const194 inline feature::properties_type feature::getProperties() const {
195 auto start_itr = tags_iter.begin();
196 const auto end_itr = tags_iter.end();
197 properties_type properties;
198 auto iter_len = std::distance(start_itr,end_itr);
199 if (iter_len > 0) {
200 properties.reserve(static_cast<std::size_t>(iter_len/2));
201 while (start_itr != end_itr) {
202 std::uint32_t tag_key = static_cast<std::uint32_t>(*start_itr++);
203 if (start_itr == end_itr) {
204 throw std::runtime_error("uneven number of feature tag ids");
205 }
206 std::uint32_t tag_val = static_cast<std::uint32_t>(*start_itr++);
207 properties.emplace(layer_.keys.at(tag_key),parseValue(layer_.values.at(tag_val)));
208 }
209 }
210 return properties;
211 }
212
getID() const213 inline optional<mapbox::geometry::identifier> const& feature::getID() const {
214 return id;
215 }
216
getExtent() const217 inline std::uint32_t feature::getExtent() const {
218 return layer_.getExtent();
219 }
220
getVersion() const221 inline std::uint32_t feature::getVersion() const {
222 return layer_.getVersion();
223 }
224
225 template <typename GeometryCollectionType>
getGeometries(float scale) const226 GeometryCollectionType feature::getGeometries(float scale) const {
227 std::uint8_t cmd = 1;
228 std::uint32_t length = 0;
229 std::int64_t x = 0;
230 std::int64_t y = 0;
231
232 GeometryCollectionType paths;
233
234 paths.emplace_back();
235
236 auto start_itr = geometry_iter.begin();
237 const auto end_itr = geometry_iter.end();
238 bool first = true;
239 std::uint32_t len_reserve = 0;
240 std::size_t extra_coords = 0;
241 if (type == GeomType::LINESTRING) {
242 extra_coords = 1;
243 } else if (type == GeomType::POLYGON) {
244 extra_coords = 2;
245 }
246 bool is_point = type == GeomType::POINT;
247
248 while (start_itr != end_itr) {
249 if (length == 0) {
250 std::uint32_t cmd_length = static_cast<std::uint32_t>(*start_itr++);
251 cmd = cmd_length & 0x7;
252 length = len_reserve = cmd_length >> 3;
253 // Prevents the creation of vector tiles that would cause
254 // a denial of service from massive over allocation. Protection
255 // limit is based on the assumption of an int64_t point which is
256 // 16 bytes in size and wanting to have a maximum of 1 MB of memory
257 // used.
258 constexpr std::uint32_t MAX_LENGTH = (1024 * 1024) / 16;
259 if (len_reserve > MAX_LENGTH) {
260 len_reserve = MAX_LENGTH;
261 }
262 }
263
264 --length;
265
266 if (cmd == CommandType::MOVE_TO || cmd == CommandType::LINE_TO) {
267
268 if (is_point) {
269 if (first && cmd == CommandType::MOVE_TO) {
270 // note: this invalidates pointers. So we always
271 // dynamically get the path with paths.back()
272 paths.reserve(len_reserve);
273 first = false;
274 }
275 } else {
276 if (first && cmd == CommandType::LINE_TO) {
277 paths.back().reserve(len_reserve + extra_coords);
278 first = false;
279 }
280 }
281
282 if (cmd == CommandType::MOVE_TO && !paths.back().empty()) {
283 if (paths.back().size() < paths.back().capacity()) {
284 // Assuming we had an invalid length before
285 // lets shrink to fit, just to make sure
286 // we don't have a large capacity vector
287 // just wasting memory
288 paths.back().shrink_to_fit();
289 }
290 paths.emplace_back();
291 if (!is_point) {
292 first = true;
293 }
294 }
295
296 x += protozero::decode_zigzag32(static_cast<std::uint32_t>(*start_itr++));
297 y += protozero::decode_zigzag32(static_cast<std::uint32_t>(*start_itr++));
298 float px = ::roundf(static_cast<float>(x) * scale);
299 float py = ::roundf(static_cast<float>(y) * scale);
300 static const float max_coord = static_cast<float>(std::numeric_limits<typename GeometryCollectionType::coordinate_type>::max());
301 static const float min_coord = static_cast<float>(std::numeric_limits<typename GeometryCollectionType::coordinate_type>::min());
302
303 if (px > max_coord ||
304 px < min_coord ||
305 py > max_coord ||
306 py < min_coord
307 ) {
308 std::runtime_error("paths outside valid range of coordinate_type");
309 } else {
310 paths.back().emplace_back(
311 static_cast<typename GeometryCollectionType::coordinate_type>(px),
312 static_cast<typename GeometryCollectionType::coordinate_type>(py));
313 }
314 } else if (cmd == CommandType::CLOSE) {
315 if (!paths.back().empty()) {
316 paths.back().push_back(paths.back()[0]);
317 }
318 length = 0;
319 } else {
320 throw std::runtime_error("unknown command");
321 }
322 }
323 if (paths.size() < paths.capacity()) {
324 // Assuming we had an invalid length before
325 // lets shrink to fit, just to make sure
326 // we don't have a large capacity vector
327 // just wasting memory
328 paths.shrink_to_fit();
329 }
330 #if defined(DEBUG)
331 for (auto const& p : paths) {
332 assert(p.size() == p.capacity());
333 }
334 #endif
335 return paths;
336 }
337
buffer(std::string const & data)338 inline buffer::buffer(std::string const& data)
339 : layers() {
340 protozero::pbf_reader data_reader(data);
341 while (data_reader.next(TileType::LAYERS)) {
342 const protozero::data_view layer_view = data_reader.get_view();
343 protozero::pbf_reader layer_reader(layer_view);
344 std::string name;
345 bool has_name = false;
346 while (layer_reader.next(LayerType::NAME)) {
347 name = layer_reader.get_string();
348 has_name = true;
349 }
350 if (!has_name) {
351 throw std::runtime_error("Layer missing name");
352 }
353 layers.emplace(name, layer_view);
354 }
355 }
356
layerNames() const357 inline std::vector<std::string> buffer::layerNames() const {
358 std::vector<std::string> names;
359 names.reserve(layers.size());
360 for (auto const& layer : layers) {
361 names.emplace_back(layer.first);
362 }
363 return names;
364 }
365
getLayer(const std::string & name) const366 inline layer buffer::getLayer(const std::string& name) const {
367 auto layer_it = layers.find(name);
368 if (layer_it == layers.end()) {
369 throw std::runtime_error(std::string("no layer by the name of '")+name+"'");
370 }
371 return layer(layer_it->second);
372 }
373
layer(protozero::data_view const & layer_view)374 inline layer::layer(protozero::data_view const& layer_view) :
375 name(),
376 version(1),
377 extent(4096),
378 keysMap(),
379 keys(),
380 values(),
381 features()
382 {
383 bool has_name = false;
384 bool has_extent = false;
385 bool has_version = false;
386 protozero::pbf_reader layer_pbf(layer_view);
387 while (layer_pbf.next()) {
388 switch (layer_pbf.tag()) {
389 case LayerType::NAME:
390 {
391 name = layer_pbf.get_string();
392 has_name = true;
393 }
394 break;
395 case LayerType::FEATURES:
396 {
397 features.push_back(layer_pbf.get_view());
398 }
399 break;
400 case LayerType::KEYS:
401 {
402 // We want to keep the keys in the order of the vector tile
403 // https://github.com/mapbox/mapbox-gl-native/pull/5183
404 auto iter = keysMap.emplace(layer_pbf.get_string(), keysMap.size());
405 keys.emplace_back(std::reference_wrapper<const std::string>(iter.first->first));
406 }
407 break;
408 case LayerType::VALUES:
409 {
410 values.emplace_back(layer_pbf.get_view());
411 }
412 break;
413 case LayerType::EXTENT:
414 {
415 extent = layer_pbf.get_uint32();
416 has_extent = true;
417 }
418 break;
419 case LayerType::VERSION:
420 {
421 version = layer_pbf.get_uint32();
422 has_version = true;
423 }
424 break;
425 default:
426 {
427 layer_pbf.skip();
428 }
429 break;
430 }
431 }
432 if (!has_version || !has_name || !has_extent) {
433 std::string msg("missing required field:");
434 if (!has_version) {
435 msg += " version ";
436 }
437 if (!has_extent) {
438 msg += " extent ";
439 }
440 if (!has_name) {
441 msg += " name";
442 }
443 throw std::runtime_error(msg.c_str());
444 }
445 }
446
getFeature(std::size_t i) const447 inline protozero::data_view const& layer::getFeature(std::size_t i) const {
448 return features.at(i);
449 }
450
getName() const451 inline std::string const& layer::getName() const {
452 return name;
453 }
454
455 }} // namespace mapbox/vector_tile
456