Line data Source code
1 : // Copyright (C) 2020-2026 Free Software Foundation, Inc.
2 :
3 : // This file is part of GCC.
4 :
5 : // GCC is free software; you can redistribute it and/or modify it under
6 : // the terms of the GNU General Public License as published by the Free
7 : // Software Foundation; either version 3, or (at your option) any later
8 : // version.
9 :
10 : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : // for more details.
14 :
15 : // You should have received a copy of the GNU General Public License
16 : // along with GCC; see the file COPYING3. If not see
17 : // <http://www.gnu.org/licenses/>.
18 :
19 : #include "expected.h"
20 : #include "rust-ast.h"
21 : #include "rust-diagnostics.h"
22 : #include "rust-forever-stack.h"
23 : #include "rust-edition.h"
24 : #include "rust-rib.h"
25 : #include "rust-unwrap-segment.h"
26 : #include "optional.h"
27 :
28 : namespace Rust {
29 : namespace Resolver2_0 {
30 :
31 : template <Namespace N>
32 : bool
33 2015818 : ForeverStack<N>::Node::is_root () const
34 : {
35 415479 : return !parent.has_value ();
36 : }
37 :
38 : template <Namespace N>
39 : bool
40 : ForeverStack<N>::Node::is_prelude () const
41 : {
42 : return rib.kind == Rib::Kind::Prelude;
43 : }
44 :
45 : template <Namespace N>
46 : bool
47 18784 : ForeverStack<N>::Node::is_leaf () const
48 : {
49 18784 : return children.empty ();
50 : }
51 :
52 : template <Namespace N>
53 : void
54 : ForeverStack<N>::Node::insert_child (Link link, Node child)
55 : {
56 : auto res = children.insert ({link, child});
57 :
58 : // Do we want to error if the child already exists? Probably not, right?
59 : // That's kinda the point, isn't it. So this method always succeeds, right?
60 : }
61 :
62 : template <Namespace N>
63 : void
64 1597791 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : tl::optional<Identifier> path)
66 : {
67 2173293 : push_inner (rib_kind, Link (id, path));
68 1597791 : }
69 :
70 : template <Namespace N>
71 : void
72 1597791 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : {
74 1597791 : if (rib.kind == Rib::Kind::Prelude)
75 : {
76 : // If you push_inner into the prelude from outside the root, you will pop
77 : // back into the root, which could screw up a traversal.
78 14088 : rust_assert (&cursor_reference.get () == &root);
79 : // Prelude doesn't have an access path
80 14088 : rust_assert (!link.path);
81 14088 : update_cursor (this->lang_prelude);
82 14088 : return;
83 : }
84 : // If the link does not exist, we create it and emplace a new `Node` with the
85 : // current node as its parent. `unordered_map::emplace` returns a pair with
86 : // the iterator and a boolean. If the value already exists, the iterator
87 : // points to it. Otherwise, it points to the newly emplaced value, so we can
88 : // just update our cursor().
89 3167406 : auto emplace = cursor ().children.emplace (
90 1583703 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 :
92 1583703 : auto it = emplace.first;
93 1583703 : auto existed = !emplace.second;
94 :
95 1821030 : rust_debug ("inserting link: Link(%d [%s]): existed? %s", link.id,
96 : link.path.has_value () ? link.path.value ().as_string ().c_str ()
97 : : "<anon>",
98 : existed ? "yes" : "no");
99 :
100 : // We update the cursor
101 1583703 : update_cursor (it->second);
102 : }
103 :
104 : template <Namespace N>
105 : void
106 1597767 : ForeverStack<N>::pop ()
107 : {
108 1597767 : rust_assert (!cursor ().is_root ());
109 :
110 1597767 : rust_debug ("popping link");
111 :
112 1930403 : for (const auto &kv : cursor ().rib.get_values ())
113 332636 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : kv.second.to_string ().c_str ());
115 :
116 1597767 : if (cursor ().parent.has_value ())
117 3035424 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 1437657 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : kv.second.to_string ().c_str ());
120 :
121 1597767 : update_cursor (cursor ().parent.value ());
122 1597767 : }
123 :
124 : static tl::expected<NodeId, DuplicateNameError>
125 275311 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : {
127 550622 : return rib.insert (name, definition);
128 : }
129 :
130 : template <Namespace N>
131 : tl::expected<NodeId, DuplicateNameError>
132 244840 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : {
134 244840 : auto &innermost_rib = peek ();
135 :
136 : // So what do we do here - if the Rib has already been pushed in an earlier
137 : // pass, we might end up in a situation where it is okay to re-add new names.
138 : // Do we just ignore that here? Do we keep track of if the Rib is new or not?
139 : // should our cursor have info on the current node like "is it newly pushed"?
140 244840 : return insert_inner (innermost_rib, name.as_string (),
141 489680 : Rib::Definition::NonShadowable (node));
142 : }
143 :
144 : template <Namespace N>
145 : tl::expected<NodeId, DuplicateNameError>
146 24412 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : {
148 24412 : auto &innermost_rib = peek ();
149 :
150 24412 : return insert_inner (innermost_rib, name.as_string (),
151 48824 : Rib::Definition::Shadowable (node));
152 : }
153 :
154 : template <Namespace N>
155 : tl::expected<NodeId, DuplicateNameError>
156 63 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : {
158 63 : auto &innermost_rib = peek ();
159 :
160 63 : return insert_inner (innermost_rib, name.as_string (),
161 126 : Rib::Definition::Globbed (node));
162 : }
163 :
164 : template <Namespace N>
165 : tl::expected<NodeId, DuplicateNameError>
166 15 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : {
168 15 : auto &root_rib = root.rib;
169 :
170 : // inserting in the root of the crate is never a shadowing operation, even for
171 : // macros
172 15 : return insert_inner (root_rib, name.as_string (),
173 30 : Rib::Definition::NonShadowable (node));
174 : }
175 :
176 : // Specialization for Macros and Labels - where we are allowed to shadow
177 : // existing definitions
178 : template <>
179 : inline tl::expected<NodeId, DuplicateNameError>
180 167 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : {
182 167 : return insert_inner (peek (), name.as_string (),
183 334 : Rib::Definition::Shadowable (node));
184 : }
185 :
186 : template <>
187 : inline tl::expected<NodeId, DuplicateNameError>
188 46 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
189 : {
190 46 : return insert_inner (peek (), name.as_string (),
191 92 : Rib::Definition::Shadowable (node));
192 : }
193 :
194 : template <>
195 : inline tl::expected<NodeId, DuplicateNameError>
196 4324 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : {
198 4324 : return insert_inner (peek (), name.as_string (),
199 8648 : Rib::Definition::NonShadowable (node, true));
200 : }
201 :
202 : template <>
203 : inline tl::expected<NodeId, DuplicateNameError>
204 1186 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
205 : {
206 1186 : return insert_inner (peek (), name.as_string (),
207 2372 : Rib::Definition::NonShadowable (node, true));
208 : }
209 :
210 : template <Namespace N>
211 : inline void
212 258 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
213 : {
214 774 : insert_inner (lang_prelude.rib, name.as_string (),
215 516 : Rib::Definition::NonShadowable (id, false));
216 258 : }
217 :
218 : template <Namespace N>
219 : Rib &
220 331444 : ForeverStack<N>::peek ()
221 : {
222 331444 : return cursor ().rib;
223 : }
224 :
225 : template <Namespace N>
226 : const Rib &
227 : ForeverStack<N>::peek () const
228 : {
229 : return cursor ().rib;
230 : }
231 :
232 : template <Namespace N>
233 : void
234 28 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
235 : {
236 56 : return reverse_iter (cursor (), lambda);
237 : }
238 :
239 : template <Namespace N>
240 : void
241 : ForeverStack<N>::reverse_iter (
242 : std::function<KeepGoing (const Node &)> lambda) const
243 : {
244 : return reverse_iter (cursor (), lambda);
245 : }
246 :
247 : template <Namespace N>
248 : void
249 160737 : ForeverStack<N>::reverse_iter (Node &start,
250 : std::function<KeepGoing (Node &)> lambda)
251 : {
252 160737 : auto *tmp = &start;
253 :
254 295620 : while (true)
255 : {
256 456357 : auto keep_going = lambda (*tmp);
257 456357 : if (keep_going == KeepGoing::No)
258 : return;
259 :
260 368773 : if (tmp->is_root ())
261 : return;
262 :
263 295620 : tmp = &tmp->parent.value ();
264 : }
265 : }
266 :
267 : template <Namespace N>
268 : void
269 : ForeverStack<N>::reverse_iter (
270 : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
271 : {
272 : auto *tmp = &start;
273 :
274 : while (true)
275 : {
276 : auto keep_going = lambda (*tmp);
277 : if (keep_going == KeepGoing::No)
278 : return;
279 :
280 : if (tmp->is_root ())
281 : return;
282 :
283 : tmp = &tmp->parent.value ();
284 : }
285 : }
286 :
287 : template <Namespace N>
288 : typename ForeverStack<N>::Node &
289 8481840 : ForeverStack<N>::cursor ()
290 : {
291 8398068 : return cursor_reference;
292 : }
293 :
294 : template <Namespace N>
295 : const typename ForeverStack<N>::Node &
296 : ForeverStack<N>::cursor () const
297 : {
298 : return cursor_reference;
299 : }
300 :
301 : template <Namespace N>
302 : void
303 1597791 : ForeverStack<N>::update_cursor (Node &new_cursor)
304 : {
305 1597791 : cursor_reference = new_cursor;
306 : }
307 :
308 : template <Namespace N>
309 : tl::optional<Rib::Definition>
310 155393 : ForeverStack<N>::get (Node &start, const Identifier &name)
311 : {
312 155393 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
313 :
314 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
315 605985 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
316 : // we can't reference associated types/functions like this
317 450592 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
318 : return KeepGoing::Yes;
319 :
320 408191 : auto candidate = current.rib.get (name.as_string ());
321 :
322 408191 : if (candidate)
323 : {
324 71289 : if (candidate->is_variant ())
325 : return KeepGoing::Yes;
326 : // for most namespaces, we do not need to care about various ribs -
327 : // they are available from all contexts if defined in the current
328 : // scope, or an outermore one. so if we do have a candidate, we can
329 : // return it directly and stop iterating
330 71284 : resolved_definition = *candidate;
331 :
332 71284 : return KeepGoing::No;
333 : }
334 : else
335 : {
336 336902 : if (current.rib.kind == Rib::Kind::Module)
337 : return KeepGoing::No;
338 : else
339 : return KeepGoing::Yes;
340 : }
341 408191 : });
342 :
343 155393 : return resolved_definition;
344 : }
345 :
346 : template <Namespace N>
347 : tl::optional<Rib::Definition>
348 83772 : ForeverStack<N>::get (const Identifier &name)
349 : {
350 83772 : return get (cursor (), name);
351 : }
352 :
353 : template <Namespace N>
354 : tl::optional<Rib::Definition>
355 11 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
356 : {
357 11 : return lang_prelude.rib.get (name.as_string ());
358 : }
359 :
360 : template <Namespace N>
361 : tl::optional<Rib::Definition>
362 34222 : ForeverStack<N>::get_lang_prelude (const std::string &name)
363 : {
364 34222 : return lang_prelude.rib.get (name);
365 : }
366 :
367 : template <Namespace N>
368 : tl::optional<Rib::Definition>
369 0 : ForeverStack<N>::get_from_prelude (NodeId prelude, const Identifier &name)
370 : {
371 0 : auto starting_point = dfs_node (root, prelude);
372 0 : if (!starting_point)
373 0 : return tl::nullopt;
374 :
375 0 : return get (*starting_point, name);
376 : }
377 :
378 : template <>
379 28 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
380 : const Identifier &name)
381 : {
382 28 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
383 :
384 28 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
385 : // looking up for labels cannot go through function ribs
386 : // TODO: What other ribs?
387 28 : if (current.rib.kind == Rib::Kind::Function)
388 : return KeepGoing::No;
389 :
390 28 : auto candidate = current.rib.get (name.as_string ());
391 :
392 : // FIXME: Factor this in a function with the generic `get`
393 28 : return candidate.map_or (
394 79 : [&resolved_definition] (Rib::Definition found) {
395 23 : resolved_definition = found;
396 :
397 23 : return KeepGoing::No;
398 : },
399 28 : KeepGoing::Yes);
400 28 : });
401 :
402 28 : return resolved_definition;
403 : }
404 :
405 : /* Check if an iterator points to the last element */
406 : template <typename I, typename C>
407 : static bool
408 66496 : is_last (const I &iterator, const C &collection)
409 : {
410 66496 : return iterator + 1 == collection.end ();
411 : }
412 :
413 : /* Check if an iterator points to the start of the collection */
414 : template <typename I, typename C>
415 : static bool
416 84383 : is_start (const I &iterator, const C &collection)
417 : {
418 105511 : return iterator == collection.begin ();
419 : }
420 :
421 : template <Namespace N>
422 : typename ForeverStack<N>::Node &
423 5316 : ForeverStack<N>::find_closest_module (Node &starting_point)
424 : {
425 5316 : auto *closest_module = &starting_point;
426 :
427 11053 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
428 5737 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
429 : {
430 5316 : closest_module = ¤t;
431 5316 : return KeepGoing::No;
432 : }
433 :
434 : return KeepGoing::Yes;
435 : });
436 :
437 5316 : return *closest_module;
438 : }
439 :
440 : /* If a the given condition is met, emit an error about misused leading path
441 : * segments */
442 : static inline bool
443 47279 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
444 : const ResolutionPath::Segment &segment,
445 : bool condition)
446 : {
447 47279 : if (condition)
448 11 : collect_errors.emplace_back (
449 11 : segment.locus, ErrorCode::E0433,
450 11 : "%qs in paths can only be used in start position", segment.name.c_str ());
451 :
452 47279 : return condition;
453 : }
454 :
455 : // we first need to handle the "starting" segments - `super`, `self` or
456 : // `crate`. we don't need to do anything for `self` and can just skip it. for
457 : // `crate`, we need to go back to the root of the current stack. for each
458 : // `super` segment, we go back to the cursor's parent until we reach the
459 : // correct one or the root.
460 : template <Namespace N>
461 : tl::optional<typename std::vector<ResolutionPath::Segment>::const_iterator>
462 19811 : ForeverStack<N>::find_starting_point (
463 : const std::vector<ResolutionPath::Segment> &segments,
464 : std::reference_wrapper<Node> &starting_point,
465 : std::function<void (Usage, Definition)> insert_segment_resolution,
466 : std::vector<Error> &collect_errors)
467 : {
468 19811 : auto iterator = segments.begin ();
469 :
470 22382 : for (; !is_last (iterator, segments); iterator++)
471 : {
472 21128 : auto &seg = *iterator;
473 :
474 21128 : bool is_self_or_crate
475 21128 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
476 :
477 : // if we're after the first path segment and meet `self` or `crate`, it's
478 : // an error - we should only be seeing `super` keywords at this point
479 21128 : if (check_leading_kw_at_start (collect_errors, seg,
480 21128 : !is_start (iterator, segments)
481 21128 : && is_self_or_crate))
482 1 : return tl::nullopt;
483 :
484 21127 : if (seg.is_crate_path_seg ())
485 : {
486 818 : starting_point = root;
487 818 : insert_segment_resolution (Usage (seg.node_id),
488 818 : Definition (starting_point.get ().id));
489 818 : iterator++;
490 : break;
491 : }
492 20309 : if (seg.is_lower_self_seg ())
493 : {
494 : // insert segment resolution and exit
495 25 : starting_point = find_closest_module (starting_point);
496 25 : insert_segment_resolution (Usage (seg.node_id),
497 25 : Definition (starting_point.get ().id));
498 25 : iterator++;
499 : break;
500 : }
501 20284 : if (seg.is_super_path_seg ())
502 : {
503 2572 : starting_point = find_closest_module (starting_point);
504 2572 : if (starting_point.get ().is_root ())
505 : {
506 1 : collect_errors.emplace_back (
507 1 : seg.locus, ErrorCode::E0433,
508 : "too many leading %<super%> keywords");
509 1 : return tl::nullopt;
510 : }
511 :
512 2571 : starting_point
513 2571 : = find_closest_module (starting_point.get ().parent.value ());
514 :
515 2571 : insert_segment_resolution (Usage (seg.node_id),
516 2571 : Definition (starting_point.get ().id));
517 : continue;
518 : }
519 :
520 : // now we've gone through the allowed `crate`, `self` or leading `super`
521 : // segments. we can start resolving each segment itself.
522 : // if we do see another leading segment, then we can error out.
523 : break;
524 : }
525 :
526 19809 : return iterator;
527 : }
528 :
529 : template <Namespace N>
530 : tl::optional<typename ForeverStack<N>::Node &>
531 19809 : ForeverStack<N>::resolve_segments (
532 : Node &starting_point, const std::vector<ResolutionPath::Segment> &segments,
533 : typename std::vector<ResolutionPath::Segment>::const_iterator iterator,
534 : std::function<void (Usage, Definition)> insert_segment_resolution,
535 : std::vector<Error> &collect_errors)
536 : {
537 19809 : Node *current_node = &starting_point;
538 45960 : for (; !is_last (iterator, segments); iterator++)
539 : {
540 26151 : auto &seg = *iterator;
541 :
542 52302 : std::string str = seg.name;
543 26151 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
544 :
545 : // check that we don't encounter *any* leading keywords afterwards
546 26151 : if (check_leading_kw_at_start (collect_errors, seg,
547 26151 : seg.is_crate_path_seg ()
548 26151 : || seg.is_super_path_seg ()
549 52295 : || seg.is_lower_self_seg ()))
550 10 : return tl::nullopt;
551 :
552 26141 : tl::optional<std::reference_wrapper<Node>> child = tl::nullopt;
553 :
554 : /*
555 : * On every iteration this loop either
556 : *
557 : * 1. terminates
558 : *
559 : * 2. decreases the depth of the node pointed to by current_node until
560 : * current_node reaches the root
561 : *
562 : * 3. If the root node is reached, and we were not able to resolve the
563 : * segment, we search the prelude rib for the segment, by setting
564 : * current_node to point to the prelude, and toggling the
565 : * searched_prelude boolean to true. If current_node is the prelude
566 : * rib, and searched_prelude is true, we will exit.
567 : *
568 : * This ensures termination.
569 : *
570 : */
571 26141 : bool searched_prelude = false;
572 30181 : while (true)
573 : {
574 64414 : if (is_start (iterator, segments)
575 58313 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
576 : {
577 : // we can't reference associated types/functions like this
578 6101 : current_node = ¤t_node->parent.value ();
579 6115 : continue;
580 : }
581 :
582 : // may set the value of child
583 172753 : for (auto &kv : current_node->children)
584 : {
585 142572 : auto &link = kv.first;
586 :
587 285144 : if (link.path.map_or (
588 76413 : [&str] (Identifier path) {
589 76413 : auto &path_str = path.as_string ();
590 76413 : return str == path_str;
591 : },
592 142572 : false))
593 : {
594 74243 : child = kv.second;
595 : break;
596 : }
597 : }
598 :
599 52212 : if (child.has_value ())
600 : {
601 : break;
602 : }
603 :
604 30181 : auto rib_lookup = current_node->rib.get (seg.name);
605 30181 : if (rib_lookup && !rib_lookup->is_ambiguous ())
606 : {
607 4097 : if (Analysis::Mappings::get ()
608 4097 : .lookup_glob_container (rib_lookup->get_node_id ())
609 4097 : .has_value ())
610 : {
611 2274 : child = dfs_node (root, rib_lookup->get_node_id ()).value ();
612 : break;
613 : }
614 : else
615 : {
616 1823 : insert_segment_resolution (Usage (seg.node_id),
617 1823 : Definition (
618 : rib_lookup->get_node_id ()));
619 1823 : return tl::nullopt;
620 : }
621 : }
622 :
623 26084 : if (current_node->is_root () && !searched_prelude)
624 : {
625 14 : searched_prelude = true;
626 14 : current_node = &lang_prelude;
627 : continue;
628 : }
629 :
630 26070 : if (!is_start (iterator, segments)
631 26065 : || current_node->rib.kind == Rib::Kind::Module
632 52135 : || current_node->is_prelude ())
633 : {
634 13 : return tl::nullopt;
635 : }
636 :
637 26057 : current_node = ¤t_node->parent.value ();
638 : }
639 :
640 : // if child didn't point to a value
641 : // the while loop above would have returned or kept looping
642 24305 : current_node = &child->get ();
643 24305 : insert_segment_resolution (Usage (seg.node_id),
644 24305 : Definition (current_node->id));
645 : }
646 :
647 17963 : return *current_node;
648 : }
649 :
650 : template <>
651 : inline tl::optional<Rib::Definition>
652 4699 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
653 : std::string &seg_name,
654 : bool is_lower_self)
655 : {
656 4699 : if (is_lower_self)
657 204 : return Rib::Definition::NonShadowable (final_node.id);
658 : else
659 4495 : return final_node.rib.get (seg_name);
660 : }
661 :
662 : template <Namespace N>
663 : tl::optional<Rib::Definition>
664 13264 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
665 : bool is_lower_self)
666 : {
667 13264 : return final_node.rib.get (seg_name);
668 : }
669 :
670 : template <Namespace N>
671 : tl::optional<typename ForeverStack<N>::DfsResult>
672 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
673 : {
674 : auto values = starting_point.rib.get_values ();
675 :
676 : for (auto &kv : values)
677 : {
678 : for (auto id : kv.second.ids_shadowable)
679 : if (id == to_find)
680 : return {{starting_point, kv.first}};
681 : for (auto id : kv.second.ids_non_shadowable)
682 : if (id == to_find)
683 : return {{starting_point, kv.first}};
684 : for (auto id : kv.second.ids_globbed)
685 : if (id == to_find)
686 : return {{starting_point, kv.first}};
687 : }
688 :
689 : for (auto &child : starting_point.children)
690 : {
691 : auto candidate = dfs (child.second, to_find);
692 :
693 : if (candidate.has_value ())
694 : return candidate;
695 : }
696 :
697 : return tl::nullopt;
698 : }
699 :
700 : template <Namespace N>
701 : tl::optional<typename ForeverStack<N>::ConstDfsResult>
702 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
703 : NodeId to_find) const
704 : {
705 : auto values = starting_point.rib.get_values ();
706 :
707 : for (auto &kv : values)
708 : {
709 : for (auto id : kv.second.ids_shadowable)
710 : if (id == to_find)
711 : return {{starting_point, kv.first}};
712 : for (auto id : kv.second.ids_non_shadowable)
713 : if (id == to_find)
714 : return {{starting_point, kv.first}};
715 : for (auto id : kv.second.ids_globbed)
716 : if (id == to_find)
717 : return {{starting_point, kv.first}};
718 : }
719 :
720 : for (auto &child : starting_point.children)
721 : {
722 : auto candidate = dfs (child.second, to_find);
723 :
724 : if (candidate.has_value ())
725 : return candidate;
726 : }
727 :
728 : return tl::nullopt;
729 : }
730 :
731 : template <Namespace N>
732 : tl::optional<Rib &>
733 1297 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
734 : {
735 1297 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
736 1 : return x.rib;
737 1297 : });
738 : }
739 :
740 : template <Namespace N>
741 : tl::optional<const Rib &>
742 52 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
743 : NodeId to_find) const
744 : {
745 52 : return dfs_node (starting_point, to_find)
746 52 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
747 : }
748 :
749 : template <Namespace N>
750 : tl::optional<typename ForeverStack<N>::Node &>
751 1540069 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
752 : NodeId to_find)
753 : {
754 1540069 : if (starting_point.id == to_find)
755 40047 : return starting_point;
756 :
757 2924990 : for (auto &child : starting_point.children)
758 : {
759 1498726 : auto candidate = dfs_node (child.second, to_find);
760 :
761 1498726 : if (candidate.has_value ())
762 73758 : return candidate;
763 : }
764 :
765 1426264 : return tl::nullopt;
766 : }
767 :
768 : template <Namespace N>
769 : tl::optional<const typename ForeverStack<N>::Node &>
770 939 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
771 : NodeId to_find) const
772 : {
773 939 : if (starting_point.id == to_find)
774 68 : return starting_point;
775 :
776 1493 : for (auto &child : starting_point.children)
777 : {
778 859 : auto candidate = dfs_node (child.second, to_find);
779 :
780 859 : if (candidate.has_value ())
781 237 : return candidate;
782 : }
783 :
784 634 : return tl::nullopt;
785 : }
786 :
787 : template <Namespace N>
788 : tl::optional<Rib &>
789 : ForeverStack<N>::to_rib (NodeId rib_id)
790 : {
791 : return dfs_rib (root, rib_id);
792 : }
793 :
794 : template <Namespace N>
795 : tl::optional<const Rib &>
796 52 : ForeverStack<N>::to_rib (NodeId rib_id) const
797 : {
798 52 : return dfs_rib (root, rib_id);
799 : }
800 :
801 : template <Namespace N>
802 : void
803 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
804 : const std::string &next,
805 : const std::string &next_next) const
806 : {
807 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
808 0 : stream << next << "rib [" << rib_kind << "]: {";
809 0 : if (rib.get_values ().empty ())
810 : {
811 0 : stream << "}\n";
812 0 : return;
813 : }
814 : else
815 : {
816 0 : stream << "\n";
817 : }
818 :
819 0 : for (const auto &kv : rib.get_values ())
820 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
821 :
822 0 : stream << next << "},\n";
823 0 : }
824 :
825 : template <Namespace N>
826 : void
827 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
828 : const ForeverStack<N>::Node &node,
829 : unsigned depth) const
830 : {
831 0 : auto indent = std::string (indentation, ' ');
832 0 : auto next = std::string (indentation + 4, ' ');
833 0 : auto next_next = std::string (indentation + 8, ' ');
834 :
835 : stream << indent << "Node {\n"
836 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
837 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
838 0 : << ",\n";
839 :
840 0 : stream_rib (stream, node.rib, next, next_next);
841 :
842 0 : stream << indent << "}\n";
843 :
844 0 : for (auto &kv : node.children)
845 : {
846 0 : auto link = kv.first;
847 0 : auto child = kv.second;
848 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
849 0 : << (link.path.has_value () ? link.path.value ().as_string ()
850 0 : : "<anon>")
851 0 : << "):\n";
852 :
853 0 : stream_node (stream, indentation + 4, child, depth + 1);
854 :
855 0 : stream << '\n';
856 : }
857 0 : }
858 :
859 : template <Namespace N>
860 : std::string
861 0 : ForeverStack<N>::as_debug_string () const
862 : {
863 0 : std::stringstream stream;
864 :
865 0 : stream_node (stream, 0, root);
866 :
867 0 : return stream.str ();
868 0 : }
869 :
870 : template <Namespace N>
871 : bool
872 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
873 : {
874 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
875 : }
876 :
877 : // FIXME: Can we add selftests?
878 :
879 : } // namespace Resolver2_0
880 : } // namespace Rust
|
