1 #include "extractor/extractor_callbacks.hpp"
2 #include "extractor/extraction_containers.hpp"
3 #include "extractor/extraction_node.hpp"
4 #include "extractor/extraction_way.hpp"
5 #include "extractor/profile_properties.hpp"
6 #include "extractor/query_node.hpp"
7 #include "extractor/restriction.hpp"
8 #include "extractor/road_classification.hpp"
9
10 #include "util/for_each_pair.hpp"
11 #include "util/guidance/turn_lanes.hpp"
12 #include "util/log.hpp"
13
14 #include <boost/optional/optional.hpp>
15 #include <boost/tokenizer.hpp>
16
17 #include <osmium/osm.hpp>
18
19 #include "osrm/coordinate.hpp"
20
21 #include <limits>
22 #include <string>
23 #include <vector>
24
25 namespace osrm
26 {
27 namespace extractor
28 {
ExtractorCallbacks(ExtractionContainers & extraction_containers_,std::unordered_map<std::string,ClassData> & classes_map,LaneDescriptionMap & lane_description_map,const ProfileProperties & properties)29 ExtractorCallbacks::ExtractorCallbacks(ExtractionContainers &extraction_containers_,
30 std::unordered_map<std::string, ClassData> &classes_map,
31 LaneDescriptionMap &lane_description_map,
32 const ProfileProperties &properties)
33 : external_memory(extraction_containers_), classes_map(classes_map),
34 lane_description_map(lane_description_map),
35 fallback_to_duration(properties.fallback_to_duration),
36 force_split_edges(properties.force_split_edges)
37 {
38 // we reserved 0, 1, 2, 3, 4 for the empty case
39 string_map[MapKey("", "", "", "", "")] = 0;
40 lane_description_map.data[TurnLaneDescription()] = 0;
41 }
42
43 /**
44 * Takes the node position from osmium and the filtered properties from the lua
45 * profile and saves them to external memory.
46 *
47 * warning: caller needs to take care of synchronization!
48 */
ProcessNode(const osmium::Node & input_node,const ExtractionNode & result_node)49 void ExtractorCallbacks::ProcessNode(const osmium::Node &input_node,
50 const ExtractionNode &result_node)
51 {
52 const auto id = OSMNodeID{static_cast<std::uint64_t>(input_node.id())};
53
54 external_memory.all_nodes_list.push_back(
55 QueryNode{util::toFixed(util::UnsafeFloatLongitude{input_node.location().lon()}),
56 util::toFixed(util::UnsafeFloatLatitude{input_node.location().lat()}),
57 id});
58
59 if (result_node.barrier)
60 {
61 external_memory.barrier_nodes.push_back(id);
62 }
63 if (result_node.traffic_lights)
64 {
65 external_memory.traffic_signals.push_back(id);
66 }
67 }
68
ProcessRestriction(const InputTurnRestriction & restriction)69 void ExtractorCallbacks::ProcessRestriction(const InputTurnRestriction &restriction)
70 {
71 external_memory.restrictions_list.push_back(restriction);
72 }
73
ProcessManeuverOverride(const InputManeuverOverride & override)74 void ExtractorCallbacks::ProcessManeuverOverride(const InputManeuverOverride &override)
75 {
76 external_memory.external_maneuver_overrides_list.push_back(override);
77 }
78
79 /**
80 * Takes the geometry contained in the ```input_way``` and the tags computed
81 * by the lua profile inside ```parsed_way``` and computes all edge segments.
82 *
83 * Depending on the forward/backwards weights the edges are split into forward
84 * and backward edges.
85 *
86 * warning: caller needs to take care of synchronization!
87 */
ProcessWay(const osmium::Way & input_way,const ExtractionWay & parsed_way)88 void ExtractorCallbacks::ProcessWay(const osmium::Way &input_way, const ExtractionWay &parsed_way)
89 {
90 if ((parsed_way.forward_travel_mode == extractor::TRAVEL_MODE_INACCESSIBLE ||
91 parsed_way.forward_speed <= 0) &&
92 (parsed_way.backward_travel_mode == extractor::TRAVEL_MODE_INACCESSIBLE ||
93 parsed_way.backward_speed <= 0) &&
94 parsed_way.duration <= 0)
95 { // Only true if the way is assigned a valid speed/duration
96 return;
97 }
98
99 if (!fallback_to_duration &&
100 (parsed_way.forward_travel_mode == extractor::TRAVEL_MODE_INACCESSIBLE ||
101 parsed_way.forward_rate <= 0) &&
102 (parsed_way.backward_travel_mode == extractor::TRAVEL_MODE_INACCESSIBLE ||
103 parsed_way.backward_rate <= 0) &&
104 parsed_way.weight <= 0)
105 { // Only true if the way is assigned a valid rate/weight and there is no duration fallback
106 return;
107 }
108
109 const auto &nodes = input_way.nodes();
110 if (nodes.size() <= 1)
111 { // safe-guard against broken data
112 return;
113 }
114
115 if (std::numeric_limits<decltype(input_way.id())>::max() == input_way.id())
116 {
117 util::Log(logDEBUG) << "found bogus way with id: " << input_way.id() << " of size "
118 << nodes.size();
119 return;
120 }
121
122 InternalExtractorEdge::DurationData forward_duration_data;
123 InternalExtractorEdge::DurationData backward_duration_data;
124 InternalExtractorEdge::WeightData forward_weight_data;
125 InternalExtractorEdge::WeightData backward_weight_data;
126
127 const auto toValueByEdgeOrByMeter = [&nodes](const double by_way, const double by_meter) {
128 using Value = detail::ByEdgeOrByMeterValue;
129 // get value by weight per edge
130 if (by_way >= 0)
131 {
132 // FIXME We divide by the number of edges here, but should rather consider
133 // the length of each segment. We would either have to compute the length
134 // of the whole way here (we can't: no node coordinates) or push that back
135 // to the container and keep a reference to the way.
136 const std::size_t num_edges = (nodes.size() - 1);
137 return Value(Value::by_edge, by_way / num_edges);
138 }
139 else
140 {
141 // get value by deriving weight from speed per edge
142 return Value(Value::by_meter, by_meter);
143 }
144 };
145
146 if (parsed_way.forward_travel_mode != extractor::TRAVEL_MODE_INACCESSIBLE)
147 {
148 BOOST_ASSERT(parsed_way.duration > 0 || parsed_way.forward_speed > 0);
149 forward_duration_data =
150 toValueByEdgeOrByMeter(parsed_way.duration, parsed_way.forward_speed / 3.6);
151 // fallback to duration as weight
152 if (fallback_to_duration)
153 {
154 forward_weight_data = forward_duration_data;
155 }
156 else
157 {
158 BOOST_ASSERT(parsed_way.weight > 0 || parsed_way.forward_rate > 0);
159 forward_weight_data =
160 toValueByEdgeOrByMeter(parsed_way.weight, parsed_way.forward_rate);
161 }
162 }
163 if (parsed_way.backward_travel_mode != extractor::TRAVEL_MODE_INACCESSIBLE)
164 {
165 BOOST_ASSERT(parsed_way.duration > 0 || parsed_way.backward_speed > 0);
166 backward_duration_data =
167 toValueByEdgeOrByMeter(parsed_way.duration, parsed_way.backward_speed / 3.6);
168 // fallback to duration as weight
169 if (fallback_to_duration)
170 {
171 backward_weight_data = backward_duration_data;
172 }
173 else
174 {
175 BOOST_ASSERT(parsed_way.weight > 0 || parsed_way.backward_rate > 0);
176 backward_weight_data =
177 toValueByEdgeOrByMeter(parsed_way.weight, parsed_way.backward_rate);
178 }
179 }
180
181 const auto classStringToMask = [this](const std::string &class_name) {
182 auto iter = classes_map.find(class_name);
183 if (iter == classes_map.end())
184 {
185 if (classes_map.size() > MAX_CLASS_INDEX)
186 {
187 throw util::exception("Maximum number of classes is " +
188 std::to_string(MAX_CLASS_INDEX + 1));
189 }
190 ClassData class_mask = getClassData(classes_map.size());
191 classes_map[class_name] = class_mask;
192 return class_mask;
193 }
194 else
195 {
196 return iter->second;
197 }
198 };
199 const auto classesToMask = [&](const auto &classes) {
200 ClassData mask = 0;
201 for (const auto &name_and_flag : classes)
202 {
203 if (!isValidClassName(name_and_flag.first))
204 {
205 throw util::exception("Invalid class name " + name_and_flag.first +
206 " only [a-Z0-9] allowed.");
207 }
208
209 if (name_and_flag.second)
210 {
211 mask |= classStringToMask(name_and_flag.first);
212 }
213 }
214 return mask;
215 };
216 const ClassData forward_classes = classesToMask(parsed_way.forward_classes);
217 const ClassData backward_classes = classesToMask(parsed_way.backward_classes);
218
219 const auto laneStringToDescription = [](const std::string &lane_string) -> TurnLaneDescription {
220 if (lane_string.empty())
221 return {};
222
223 TurnLaneDescription lane_description;
224
225 typedef boost::tokenizer<boost::char_separator<char>> tokenizer;
226 boost::char_separator<char> sep("|", "", boost::keep_empty_tokens);
227 boost::char_separator<char> inner_sep(";", "");
228 tokenizer tokens(lane_string, sep);
229
230 const constexpr std::size_t num_osm_tags = 11;
231 const constexpr char *osm_lane_strings[num_osm_tags] = {"none",
232 "through",
233 "sharp_left",
234 "left",
235 "slight_left",
236 "slight_right",
237 "right",
238 "sharp_right",
239 "reverse",
240 "merge_to_left",
241 "merge_to_right"};
242
243 const constexpr TurnLaneType::Mask masks_by_osm_string[num_osm_tags + 1] = {
244 TurnLaneType::none,
245 TurnLaneType::straight,
246 TurnLaneType::sharp_left,
247 TurnLaneType::left,
248 TurnLaneType::slight_left,
249 TurnLaneType::slight_right,
250 TurnLaneType::right,
251 TurnLaneType::sharp_right,
252 TurnLaneType::uturn,
253 TurnLaneType::merge_to_left,
254 TurnLaneType::merge_to_right,
255 TurnLaneType::empty}; // fallback, if string not found
256
257 for (auto iter = tokens.begin(); iter != tokens.end(); ++iter)
258 {
259 tokenizer inner_tokens(*iter, inner_sep);
260 TurnLaneType::Mask lane_mask = inner_tokens.begin() == inner_tokens.end()
261 ? TurnLaneType::none
262 : TurnLaneType::empty;
263 for (auto token_itr = inner_tokens.begin(); token_itr != inner_tokens.end();
264 ++token_itr)
265 {
266 auto position =
267 std::find(osm_lane_strings, osm_lane_strings + num_osm_tags, *token_itr);
268 const auto translated_mask =
269 masks_by_osm_string[std::distance(osm_lane_strings, position)];
270 if (translated_mask == TurnLaneType::empty)
271 {
272 // if we have unsupported tags, don't handle them
273 util::Log(logDEBUG) << "Unsupported lane tag found: \"" << *token_itr << "\"";
274 return {};
275 }
276
277 // In case of multiple times the same lane indicators withn a lane, as in
278 // "left;left|.." or-ing the masks generates a single "left" enum.
279 // Which is fine since this is data issue and we can't represent it anyway.
280 lane_mask |= translated_mask;
281 }
282 // add the lane to the description
283 lane_description.push_back(lane_mask);
284 }
285 return lane_description;
286 };
287
288 // If we could parse turn lanes but could not parse number of lanes,
289 // count the turn lanes and use them for the way's number of lanes.
290 auto road_classification = parsed_way.road_classification;
291 std::uint8_t road_deduced_num_lanes = 0;
292
293 // Deduplicates street names, refs, destinations, pronunciation, exits.
294 // In case we do not already store the key, inserts (key, id) tuple and return id.
295 // Otherwise fetches the id based on the name and returns it without insertion.
296 auto turn_lane_id_forward = INVALID_LANE_DESCRIPTIONID;
297 auto turn_lane_id_backward = INVALID_LANE_DESCRIPTIONID;
298
299 // RoadClassification represents a the class for unidirectional ways,
300 // therefore we need to add up deduced forward and backward lane counts.
301
302 if (!parsed_way.turn_lanes_forward.empty())
303 {
304 auto desc = laneStringToDescription(parsed_way.turn_lanes_forward);
305 turn_lane_id_forward = lane_description_map.ConcurrentFindOrAdd(desc);
306 road_deduced_num_lanes += desc.size();
307 }
308
309 if (!parsed_way.turn_lanes_backward.empty())
310 {
311 auto desc = laneStringToDescription(parsed_way.turn_lanes_backward);
312 turn_lane_id_backward = lane_description_map.ConcurrentFindOrAdd(desc);
313 road_deduced_num_lanes += desc.size();
314 }
315
316 road_classification.SetNumberOfLanes(std::max(road_deduced_num_lanes, // len(turn:lanes)
317 road_classification.GetNumberOfLanes()));
318
319 const auto GetNameID = [this, &parsed_way](bool is_forward) -> NameID {
320 const std::string &ref = is_forward ? parsed_way.forward_ref : parsed_way.backward_ref;
321 // Get the unique identifier for the street name, destination, and ref
322 const auto name_iterator = string_map.find(MapKey(parsed_way.name,
323 parsed_way.destinations,
324 ref,
325 parsed_way.pronunciation,
326 parsed_way.exits));
327
328 NameID name_id = EMPTY_NAMEID;
329 if (string_map.end() == name_iterator)
330 {
331 // name_offsets has a sentinel element with the total name data size
332 // take the sentinels index as the name id of the new name data pack
333 // (name [name_id], destination [+1], pronunciation [+2], ref [+3], exits [+4])
334 name_id = external_memory.name_offsets.size() - 1;
335
336 std::copy(parsed_way.name.begin(),
337 parsed_way.name.end(),
338 std::back_inserter(external_memory.name_char_data));
339 external_memory.name_offsets.push_back(external_memory.name_char_data.size());
340
341 std::copy(parsed_way.destinations.begin(),
342 parsed_way.destinations.end(),
343 std::back_inserter(external_memory.name_char_data));
344 external_memory.name_offsets.push_back(external_memory.name_char_data.size());
345
346 std::copy(parsed_way.pronunciation.begin(),
347 parsed_way.pronunciation.end(),
348 std::back_inserter(external_memory.name_char_data));
349 external_memory.name_offsets.push_back(external_memory.name_char_data.size());
350
351 std::copy(ref.begin(), ref.end(), std::back_inserter(external_memory.name_char_data));
352 external_memory.name_offsets.push_back(external_memory.name_char_data.size());
353
354 std::copy(parsed_way.exits.begin(),
355 parsed_way.exits.end(),
356 std::back_inserter(external_memory.name_char_data));
357 external_memory.name_offsets.push_back(external_memory.name_char_data.size());
358
359 auto k = MapKey{parsed_way.name,
360 parsed_way.destinations,
361 ref,
362 parsed_way.pronunciation,
363 parsed_way.exits};
364 auto v = MapVal{name_id};
365 string_map.emplace(std::move(k), std::move(v));
366 }
367 else
368 {
369 name_id = name_iterator->second;
370 }
371
372 return name_id;
373 };
374
375 const NameID forward_name_id = GetNameID(true);
376 const NameID backward_name_id = GetNameID(false);
377
378 const bool in_forward_direction =
379 (parsed_way.forward_speed > 0 || parsed_way.forward_rate > 0 || parsed_way.duration > 0 ||
380 parsed_way.weight > 0) &&
381 (parsed_way.forward_travel_mode != extractor::TRAVEL_MODE_INACCESSIBLE);
382
383 const bool in_backward_direction =
384 (parsed_way.backward_speed > 0 || parsed_way.backward_rate > 0 || parsed_way.duration > 0 ||
385 parsed_way.weight > 0) &&
386 (parsed_way.backward_travel_mode != extractor::TRAVEL_MODE_INACCESSIBLE);
387
388 // split an edge into two edges if forwards/backwards behavior differ
389 const bool split_edge =
390 in_forward_direction && in_backward_direction &&
391 (force_split_edges || (parsed_way.forward_rate != parsed_way.backward_rate) ||
392 (parsed_way.forward_speed != parsed_way.backward_speed) ||
393 (parsed_way.forward_travel_mode != parsed_way.backward_travel_mode) ||
394 (turn_lane_id_forward != turn_lane_id_backward) || (forward_classes != backward_classes) ||
395 (parsed_way.forward_ref != parsed_way.backward_ref));
396
397 if (in_forward_direction)
398 { // add (forward) segments or (forward,backward) for non-split edges in backward direction
399 const auto annotation_data_id = external_memory.all_edges_annotation_data_list.size();
400 external_memory.all_edges_annotation_data_list.push_back({forward_name_id,
401 turn_lane_id_forward,
402 forward_classes,
403 parsed_way.forward_travel_mode,
404 parsed_way.is_left_hand_driving});
405 util::for_each_pair(
406 nodes.cbegin(),
407 nodes.cend(),
408 [&](const osmium::NodeRef &first_node, const osmium::NodeRef &last_node) {
409 NodeBasedEdgeWithOSM edge = {
410 OSMNodeID{static_cast<std::uint64_t>(first_node.ref())},
411 OSMNodeID{static_cast<std::uint64_t>(last_node.ref())},
412 0, // weight
413 0, // duration
414 0, // distance
415 {}, // geometry id
416 static_cast<AnnotationID>(annotation_data_id),
417 {true,
418 in_backward_direction && !split_edge,
419 split_edge,
420 parsed_way.roundabout,
421 parsed_way.circular,
422 parsed_way.is_startpoint,
423 parsed_way.forward_restricted,
424 road_classification,
425 parsed_way.highway_turn_classification,
426 parsed_way.access_turn_classification}};
427
428 external_memory.all_edges_list.push_back(InternalExtractorEdge(
429 std::move(edge), forward_weight_data, forward_duration_data, {}));
430 });
431 }
432
433 if (in_backward_direction && (!in_forward_direction || split_edge))
434 { // add (backward) segments for split edges or not in forward direction
435 const auto annotation_data_id = external_memory.all_edges_annotation_data_list.size();
436 external_memory.all_edges_annotation_data_list.push_back({backward_name_id,
437 turn_lane_id_backward,
438 backward_classes,
439 parsed_way.backward_travel_mode,
440 parsed_way.is_left_hand_driving});
441 util::for_each_pair(
442 nodes.cbegin(),
443 nodes.cend(),
444 [&](const osmium::NodeRef &first_node, const osmium::NodeRef &last_node) {
445 NodeBasedEdgeWithOSM edge = {
446 OSMNodeID{static_cast<std::uint64_t>(first_node.ref())},
447 OSMNodeID{static_cast<std::uint64_t>(last_node.ref())},
448 0, // weight
449 0, // duration
450 0, // distance
451 {}, // geometry id
452 static_cast<AnnotationID>(annotation_data_id),
453 {false,
454 true,
455 split_edge,
456 parsed_way.roundabout,
457 parsed_way.circular,
458 parsed_way.is_startpoint,
459 parsed_way.backward_restricted,
460 road_classification,
461 parsed_way.highway_turn_classification,
462 parsed_way.access_turn_classification}};
463
464 external_memory.all_edges_list.push_back(InternalExtractorEdge(
465 std::move(edge), backward_weight_data, backward_duration_data, {}));
466 });
467 }
468
469 std::transform(nodes.begin(),
470 nodes.end(),
471 std::back_inserter(external_memory.used_node_id_list),
472 [](const osmium::NodeRef &ref) {
473 return OSMNodeID{static_cast<std::uint64_t>(ref.ref())};
474 });
475
476 auto way_id = OSMWayID{static_cast<std::uint64_t>(input_way.id())};
477 external_memory.ways_list.push_back(way_id);
478 external_memory.way_node_id_offsets.push_back(external_memory.used_node_id_list.size());
479 }
480
481 } // namespace extractor
482 } // namespace osrm
483