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 : bool
32 34156956 : ForeverStackBase::Node::is_root () const
33 : {
34 2829538 : return !parent.has_value ();
35 : }
36 :
37 : bool
38 77232 : ForeverStackBase::Node::is_prelude () const
39 : {
40 77232 : return rib_values.kind == Rib::Kind::Prelude;
41 : }
42 :
43 : bool
44 20096 : ForeverStackBase::Node::is_leaf () const
45 : {
46 20096 : return children.empty ();
47 : }
48 :
49 : void
50 160 : ForeverStackBase::Node::insert_child (Link link, Node child)
51 : {
52 160 : children.insert ({link, child});
53 :
54 : // Do we want to error if the child already exists? Probably not, right?
55 : // That's kinda the point, isn't it. So this method always succeeds, right?
56 160 : }
57 :
58 : template <Namespace N>
59 : void
60 31322284 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
61 : tl::optional<Identifier> path)
62 : {
63 32650568 : push_inner (rib_kind, Link (id, path));
64 31322284 : }
65 :
66 : template <Namespace N>
67 : void
68 31322284 : ForeverStack<N>::push_inner (Rib::Kind rib_kind, Link link)
69 : {
70 31322284 : if (rib_kind == Rib::Kind::Prelude)
71 : {
72 : // If you push_inner into the prelude from outside the root, you will pop
73 : // back into the root, which could screw up a traversal.
74 20096 : rust_assert (&cursor_reference.get () == &root);
75 : // Prelude doesn't have an access path
76 20096 : rust_assert (!link.path);
77 20096 : update_cursor (this->lang_prelude);
78 20096 : return;
79 : }
80 : // If the link does not exist, we create it and emplace a new `Node` with the
81 : // current node as its parent. `unordered_map::emplace` returns a pair with
82 : // the iterator and a boolean. If the value already exists, the iterator
83 : // points to it. Otherwise, it points to the newly emplaced value, so we can
84 : // just update our cursor().
85 62604376 : auto emplace = cursor ().children.emplace (
86 31302188 : std::make_pair (link, Node (rib_kind, link.id, cursor ())));
87 :
88 31302188 : auto it = emplace.first;
89 31302188 : auto existed = !emplace.second;
90 :
91 31302190 : rust_debug ("inserting link: Link(%d [%s]): existed? %s", link.id,
92 : link.path.has_value () ? link.path.value ().as_string ().c_str ()
93 : : "<anon>",
94 : existed ? "yes" : "no");
95 :
96 : // We update the cursor
97 31302188 : update_cursor (it->second);
98 : }
99 :
100 : template <Namespace N>
101 : void
102 31322248 : ForeverStack<N>::pop ()
103 : {
104 31322248 : rust_assert (!cursor ().is_root ());
105 :
106 31322248 : rust_debug ("popping link");
107 :
108 39539069 : for (const auto &kv : cursor ().rib (N).get_values ())
109 8216821 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
110 : kv.second.to_string ().c_str ());
111 :
112 31322248 : if (cursor ().parent.has_value ())
113 614646288 : for (const auto &kv : cursor ().parent.value ().rib (N).get_values ())
114 583324040 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
115 : kv.second.to_string ().c_str ());
116 :
117 31322248 : update_cursor (cursor ().parent.value ());
118 31322248 : }
119 :
120 : static tl::expected<NodeId, DuplicateNameError>
121 1478941 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
122 : {
123 2957882 : return rib.insert (name, definition);
124 : }
125 :
126 : template <Namespace N>
127 : tl::expected<NodeId, DuplicateNameError>
128 1416892 : ForeverStack<N>::insert (Identifier name, NodeId node)
129 : {
130 1416892 : auto &innermost_rib = peek ();
131 :
132 : // So what do we do here - if the Rib has already been pushed in an earlier
133 : // pass, we might end up in a situation where it is okay to re-add new names.
134 : // Do we just ignore that here? Do we keep track of if the Rib is new or not?
135 : // should our cursor have info on the current node like "is it newly pushed"?
136 1416892 : return insert_inner (innermost_rib, name.as_string (),
137 2833784 : Rib::Definition::NonShadowable (node));
138 : }
139 :
140 : template <Namespace N>
141 : tl::expected<NodeId, DuplicateNameError>
142 47384 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
143 : {
144 47384 : auto &innermost_rib = peek ();
145 :
146 47384 : return insert_inner (innermost_rib, name.as_string (),
147 94768 : Rib::Definition::Shadowable (node));
148 : }
149 :
150 : template <Namespace N>
151 : tl::expected<NodeId, DuplicateNameError>
152 0 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
153 : {
154 0 : auto &innermost_rib = peek ();
155 :
156 0 : return insert_inner (innermost_rib, name.as_string (),
157 0 : Rib::Definition::Globbed (node));
158 : }
159 :
160 : template <Namespace N>
161 : tl::expected<NodeId, DuplicateNameError>
162 1335 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
163 : {
164 1335 : auto &root_rib = root.rib (N);
165 :
166 : // inserting in the root of the crate is never a shadowing operation, even for
167 : // macros
168 1335 : return insert_inner (root_rib, name.as_string (),
169 2670 : Rib::Definition::NonShadowable (node));
170 : }
171 :
172 : // Specialization for Macros and Labels - where we are allowed to shadow
173 : // existing definitions
174 : template <>
175 : inline tl::expected<NodeId, DuplicateNameError>
176 2244 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
177 : {
178 2244 : return insert_inner (peek (), name.as_string (),
179 4488 : Rib::Definition::Shadowable (node));
180 : }
181 :
182 : template <>
183 : inline tl::expected<NodeId, DuplicateNameError>
184 64 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
185 : {
186 64 : return insert_inner (peek (), name.as_string (),
187 128 : Rib::Definition::Shadowable (node));
188 : }
189 :
190 : template <>
191 : inline tl::expected<NodeId, DuplicateNameError>
192 8126 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
193 : {
194 8126 : return insert_inner (peek (), name.as_string (),
195 16252 : Rib::Definition::NonShadowable (node, true));
196 : }
197 :
198 : template <>
199 : inline tl::expected<NodeId, DuplicateNameError>
200 1405 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
201 : {
202 1405 : return insert_inner (peek (), name.as_string (),
203 2810 : Rib::Definition::NonShadowable (node, true));
204 : }
205 :
206 : template <Namespace N>
207 : inline void
208 1491 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
209 : {
210 4473 : insert_inner (lang_prelude.rib (N), name.as_string (),
211 2982 : Rib::Definition::NonShadowable (id, false));
212 1491 : }
213 :
214 : template <Namespace N>
215 : Rib &
216 1748809 : ForeverStack<N>::peek ()
217 : {
218 1689967 : return cursor ().rib (N);
219 : }
220 :
221 : template <Namespace N>
222 : const Rib &
223 : ForeverStack<N>::peek () const
224 : {
225 : return cursor ().rib (N);
226 : }
227 :
228 : template <Namespace N>
229 : void
230 51 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
231 : {
232 102 : return reverse_iter (cursor (), lambda);
233 : }
234 :
235 : template <Namespace N>
236 : void
237 : ForeverStack<N>::reverse_iter (
238 : std::function<KeepGoing (const Node &)> lambda) const
239 : {
240 : return reverse_iter (cursor (), lambda);
241 : }
242 :
243 : template <Namespace N>
244 : void
245 1133623 : ForeverStack<N>::reverse_iter (Node &start,
246 : std::function<KeepGoing (Node &)> lambda)
247 : {
248 1133623 : auto *tmp = &start;
249 :
250 2648047 : while (true)
251 : {
252 3781670 : auto keep_going = lambda (*tmp);
253 3781670 : if (keep_going == KeepGoing::No)
254 : return;
255 :
256 2728149 : if (tmp->is_root ())
257 : return;
258 :
259 2648047 : tmp = &tmp->parent.value ();
260 : }
261 : }
262 :
263 : template <Namespace N>
264 : void
265 : ForeverStack<N>::reverse_iter (
266 : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
267 : {
268 : auto *tmp = &start;
269 :
270 : while (true)
271 : {
272 : auto keep_going = lambda (*tmp);
273 : if (keep_going == KeepGoing::No)
274 : return;
275 :
276 : if (tmp->is_root ())
277 : return;
278 :
279 : tmp = &tmp->parent.value ();
280 : }
281 : }
282 :
283 : template <Namespace N>
284 : typename ForeverStack<N>::Node &
285 159517239 : ForeverStack<N>::cursor ()
286 : {
287 158566514 : return cursor_reference;
288 : }
289 :
290 : template <Namespace N>
291 : const typename ForeverStack<N>::Node &
292 : ForeverStack<N>::cursor () const
293 : {
294 : return cursor_reference;
295 : }
296 :
297 : template <Namespace N>
298 : void
299 31322284 : ForeverStack<N>::update_cursor (Node &new_cursor)
300 : {
301 31322284 : cursor_reference = new_cursor;
302 : }
303 :
304 : template <Namespace N>
305 : tl::optional<Rib::Definition>
306 1116831 : ForeverStack<N>::get (Node &start, const Identifier &name)
307 : {
308 1116831 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
309 :
310 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
311 4881081 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
312 : // we can't reference associated types/functions like this
313 3764250 : if (current.rib (N).kind == Rib::Kind::TraitOrImpl)
314 : return KeepGoing::Yes;
315 :
316 3305448 : auto candidate = current.rib (N).get (name.as_string ());
317 :
318 3305448 : if (candidate)
319 : {
320 320550 : if (candidate->is_variant ())
321 : return KeepGoing::Yes;
322 : // for most namespaces, we do not need to care about various ribs -
323 : // they are available from all contexts if defined in the current
324 : // scope, or an outermore one. so if we do have a candidate, we can
325 : // return it directly and stop iterating
326 320545 : resolved_definition = *candidate;
327 :
328 320545 : return KeepGoing::No;
329 : }
330 : else
331 : {
332 2984898 : if (current.rib (N).kind == Rib::Kind::Module)
333 : return KeepGoing::No;
334 : else
335 2268714 : return KeepGoing::Yes;
336 : }
337 3764250 : });
338 :
339 1116831 : return resolved_definition;
340 : }
341 :
342 : template <Namespace N>
343 : tl::optional<Rib::Definition>
344 892323 : ForeverStack<N>::get (const Identifier &name)
345 : {
346 892323 : return get (cursor (), name);
347 : }
348 :
349 : template <Namespace N>
350 : tl::optional<Rib::Definition>
351 11 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
352 : {
353 11 : return lang_prelude.rib (N).get (name.as_string ());
354 : }
355 :
356 : template <Namespace N>
357 : tl::optional<Rib::Definition>
358 94967 : ForeverStack<N>::get_lang_prelude (const std::string &name)
359 : {
360 94967 : return lang_prelude.rib (N).get (name);
361 : }
362 :
363 : template <Namespace N>
364 : tl::optional<Rib::Definition>
365 : ForeverStack<N>::get_from_prelude (NodeId prelude, const Identifier &name)
366 : {
367 : auto starting_point = dfs_node (root, prelude);
368 : if (!starting_point)
369 : return tl::nullopt;
370 :
371 : return get (*starting_point, name);
372 : }
373 :
374 : template <>
375 51 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
376 : const Identifier &name)
377 : {
378 51 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
379 :
380 51 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
381 : // looking up for labels cannot go through function ribs
382 : // TODO: What other ribs?
383 189 : if (current.rib_labels.kind == Rib::Kind::Function)
384 : return KeepGoing::No;
385 :
386 184 : auto candidate = current.rib_labels.get (name.as_string ());
387 :
388 : // FIXME: Factor this in a function with the generic `get`
389 184 : return candidate.map_or (
390 414 : [&resolved_definition] (Rib::Definition found) {
391 46 : resolved_definition = found;
392 :
393 46 : return KeepGoing::No;
394 : },
395 184 : KeepGoing::Yes);
396 189 : });
397 :
398 51 : return resolved_definition;
399 : }
400 :
401 : /* Check if an iterator points to the last element */
402 : template <typename I, typename C>
403 : static bool
404 154106 : is_last (const I &iterator, const C &collection)
405 : {
406 250077 : return iterator + 1 == collection.end ();
407 : }
408 :
409 : /* Check if an iterator points to the start of the collection */
410 : template <typename I, typename C>
411 : static bool
412 344717 : is_start (const I &iterator, const C &collection)
413 : {
414 344717 : return iterator == collection.begin ();
415 : }
416 :
417 : template <Namespace N>
418 : typename ForeverStack<N>::Node &
419 16741 : ForeverStack<N>::find_closest_module (Node &starting_point)
420 : {
421 16741 : auto *closest_module = &starting_point;
422 :
423 33972 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
424 17231 : if (current.rib (N).kind == Rib::Kind::Module || current.is_root ())
425 : {
426 16741 : closest_module = ¤t;
427 16741 : return KeepGoing::No;
428 : }
429 :
430 : return KeepGoing::Yes;
431 : });
432 :
433 16741 : return *closest_module;
434 : }
435 :
436 : /* If a the given condition is met, emit an error about misused leading path
437 : * segments */
438 : static inline bool
439 187813 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
440 : const ResolutionPath::Segment &segment,
441 : bool condition)
442 : {
443 187813 : if (condition)
444 11 : collect_errors.emplace_back (
445 11 : segment.locus, ErrorCode::E0433,
446 11 : "%qs in paths can only be used in start position", segment.name.c_str ());
447 :
448 187813 : return condition;
449 : }
450 :
451 : // we first need to handle the "starting" segments - `super`, `self` or
452 : // `crate`. we don't need to do anything for `self` and can just skip it. for
453 : // `crate`, we need to go back to the root of the current stack. for each
454 : // `super` segment, we go back to the cursor's parent until we reach the
455 : // correct one or the root.
456 : template <Namespace N>
457 : tl::optional<typename std::vector<ResolutionPath::Segment>::const_iterator>
458 84954 : ForeverStack<N>::find_starting_point (
459 : const std::vector<ResolutionPath::Segment> &segments,
460 : std::reference_wrapper<Node> &starting_point,
461 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
462 : std::vector<Error> &collect_errors)
463 : {
464 84954 : auto iterator = segments.begin ();
465 :
466 95977 : for (; iterator != segments.end (); iterator++)
467 : {
468 95971 : auto &seg = *iterator;
469 :
470 : // don't include a final self segment
471 95971 : if (is_last (iterator, segments) && seg.is_lower_self_seg ())
472 : break;
473 :
474 95971 : bool is_self_or_crate
475 95971 : = 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 95971 : if (check_leading_kw_at_start (collect_errors, seg,
480 95971 : !is_start (iterator, segments)
481 : && is_self_or_crate))
482 1 : return tl::nullopt;
483 :
484 95970 : if (seg.is_crate_path_seg ())
485 : {
486 31236 : starting_point = root;
487 31236 : insert_segment_resolution (Usage (seg.node_id),
488 31236 : Definition (starting_point.get ().id), N);
489 31236 : iterator++;
490 31236 : break;
491 : }
492 64734 : if (seg.is_lower_self_seg ())
493 : {
494 : // insert segment resolution
495 5854 : starting_point = find_closest_module (starting_point);
496 5854 : insert_segment_resolution (Usage (seg.node_id),
497 5854 : Definition (starting_point.get ().id), N);
498 : // don't exit -- we could see some "super" segments
499 5854 : continue;
500 : }
501 58880 : if (seg.is_super_path_seg ())
502 : {
503 5170 : starting_point = find_closest_module (starting_point);
504 5170 : 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 5169 : starting_point
513 5169 : = find_closest_module (starting_point.get ().parent.value ());
514 :
515 5169 : insert_segment_resolution (Usage (seg.node_id),
516 5169 : Definition (starting_point.get ().id), N);
517 5169 : 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 84952 : return iterator;
527 : }
528 :
529 : template <Namespace N>
530 : tl::optional<typename ForeverStack<N>::DfsResult>
531 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
532 : {
533 : auto values = starting_point.rib (N).get_values ();
534 :
535 : for (auto &kv : values)
536 : {
537 : for (auto id : kv.second.ids_shadowable)
538 : if (id == to_find)
539 : return {{starting_point, kv.first}};
540 : for (auto id : kv.second.ids_non_shadowable)
541 : if (id == to_find)
542 : return {{starting_point, kv.first}};
543 : for (auto id : kv.second.ids_globbed)
544 : if (id == to_find)
545 : return {{starting_point, kv.first}};
546 : }
547 :
548 : for (auto &child : starting_point.children)
549 : {
550 : auto candidate = dfs (child.second, to_find);
551 :
552 : if (candidate.has_value ())
553 : return candidate;
554 : }
555 :
556 : return tl::nullopt;
557 : }
558 :
559 : template <Namespace N>
560 : tl::optional<typename ForeverStack<N>::ConstDfsResult>
561 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
562 : NodeId to_find) const
563 : {
564 : auto values = starting_point.rib (N).get_values ();
565 :
566 : for (auto &kv : values)
567 : {
568 : for (auto id : kv.second.ids_shadowable)
569 : if (id == to_find)
570 : return {{starting_point, kv.first}};
571 : for (auto id : kv.second.ids_non_shadowable)
572 : if (id == to_find)
573 : return {{starting_point, kv.first}};
574 : for (auto id : kv.second.ids_globbed)
575 : if (id == to_find)
576 : return {{starting_point, kv.first}};
577 : }
578 :
579 : for (auto &child : starting_point.children)
580 : {
581 : auto candidate = dfs (child.second, to_find);
582 :
583 : if (candidate.has_value ())
584 : return candidate;
585 : }
586 :
587 : return tl::nullopt;
588 : }
589 :
590 : template <Namespace N>
591 : tl::optional<Rib &>
592 49804 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
593 : {
594 99169 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
595 49365 : return x.rib (N);
596 49804 : });
597 : }
598 :
599 : template <Namespace N>
600 : tl::optional<const Rib &>
601 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
602 : NodeId to_find) const
603 : {
604 : return dfs_node (starting_point, to_find)
605 : .map ([] (const Node &x) -> const Rib & { return x.rib (N); });
606 : }
607 :
608 : template <Namespace N>
609 : tl::optional<typename ForeverStack<N>::Node &>
610 4755023 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
611 : NodeId to_find)
612 : {
613 4755023 : if (auto found = check_cache (to_find))
614 82391 : return found;
615 :
616 4672632 : if (starting_point.id == to_find)
617 : {
618 906 : cache (to_find, starting_point);
619 :
620 906 : return starting_point;
621 : }
622 :
623 9341023 : for (auto &child : starting_point.children)
624 : {
625 4671287 : auto candidate = dfs_node (child.second, to_find);
626 :
627 4671287 : if (candidate.has_value ())
628 1990 : return candidate;
629 : }
630 :
631 4669736 : return tl::nullopt;
632 : }
633 :
634 : template <Namespace N>
635 : tl::optional<const typename ForeverStack<N>::Node &>
636 131 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
637 : NodeId to_find) const
638 : {
639 131 : if (starting_point.id == to_find)
640 16 : return starting_point;
641 :
642 189 : for (auto &child : starting_point.children)
643 : {
644 103 : auto candidate = dfs_node (child.second, to_find);
645 :
646 103 : if (candidate.has_value ())
647 29 : return candidate;
648 : }
649 :
650 86 : return tl::nullopt;
651 : }
652 :
653 : template <Namespace N>
654 : tl::optional<typename ForeverStack<N>::Node &>
655 4755023 : ForeverStack<N>::check_cache (NodeId to_find)
656 : {
657 4755023 : auto entry = dfs_cache.find (to_find);
658 :
659 4755023 : if (entry != dfs_cache.end ())
660 82391 : return entry->second;
661 :
662 4672632 : return tl::nullopt;
663 : }
664 :
665 : template <Namespace N>
666 : void
667 906 : ForeverStack<N>::cache (NodeId found, typename ForeverStack<N>::Node &result)
668 : {
669 906 : dfs_cache.insert ({found, result});
670 : }
671 :
672 : template <Namespace N>
673 : tl::optional<Rib &>
674 52 : ForeverStack<N>::to_rib (NodeId rib_id)
675 : {
676 52 : return dfs_rib (root, rib_id);
677 : }
678 :
679 : template <Namespace N>
680 : tl::optional<const Rib &>
681 : ForeverStack<N>::to_rib (NodeId rib_id) const
682 : {
683 : return dfs_rib (root, rib_id);
684 : }
685 :
686 : template <Namespace N>
687 : void
688 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
689 : const std::string &next,
690 : const std::string &next_next) const
691 : {
692 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
693 0 : stream << next << "rib [" << rib_kind << "]: {";
694 0 : if (rib.get_values ().empty ())
695 : {
696 0 : stream << "}\n";
697 0 : return;
698 : }
699 : else
700 : {
701 0 : stream << "\n";
702 : }
703 :
704 0 : for (const auto &kv : rib.get_values ())
705 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
706 :
707 0 : stream << next << "},\n";
708 0 : }
709 :
710 : template <Namespace N>
711 : void
712 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
713 : const ForeverStack<N>::Node &node,
714 : unsigned depth) const
715 : {
716 0 : auto indent = std::string (indentation, ' ');
717 0 : auto next = std::string (indentation + 4, ' ');
718 0 : auto next_next = std::string (indentation + 8, ' ');
719 :
720 : stream << indent << "Node {\n"
721 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
722 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
723 0 : << ",\n";
724 :
725 0 : stream_rib (stream, node.rib (N), next, next_next);
726 :
727 0 : stream << indent << "}\n";
728 :
729 0 : for (auto &kv : node.children)
730 : {
731 0 : auto link = kv.first;
732 0 : auto child = kv.second;
733 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
734 0 : << (link.path.has_value () ? link.path.value ().as_string ()
735 0 : : "<anon>")
736 0 : << "):\n";
737 :
738 0 : stream_node (stream, indentation + 4, child, depth + 1);
739 :
740 0 : stream << '\n';
741 : }
742 0 : }
743 :
744 : template <Namespace N>
745 : std::string
746 0 : ForeverStack<N>::as_debug_string () const
747 : {
748 0 : std::stringstream stream;
749 :
750 0 : stream_node (stream, 0, root);
751 :
752 0 : return stream.str ();
753 0 : }
754 :
755 : template <Namespace N>
756 : bool
757 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
758 : {
759 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
760 : }
761 :
762 : static tl::expected<Definition, LookupFinalizeError>
763 75805 : find_leaf_definition_inner (const Usage &key,
764 : const std::map<Usage, Definition> &resolved_nodes,
765 : std::set<Usage> &keys_seen)
766 : {
767 75805 : auto original_definition = resolved_nodes.find (key);
768 75805 : auto possible_import = Usage (original_definition->second.id);
769 :
770 75805 : if (original_definition == resolved_nodes.end ())
771 75805 : return tl::make_unexpected (LookupFinalizeError::NoDefinition);
772 :
773 0 : if (!keys_seen.insert (key).second)
774 0 : return tl::make_unexpected (LookupFinalizeError::Loop);
775 :
776 0 : if (resolved_nodes.find (possible_import) == resolved_nodes.end ())
777 0 : return original_definition->second;
778 :
779 : // We're dealing with an import - a reference to another
780 : // definition. Go through the chain and update the original key's
781 : // corresponding definition.
782 0 : return find_leaf_definition_inner (possible_import, resolved_nodes,
783 0 : keys_seen);
784 : }
785 :
786 : template <Namespace N>
787 : tl::expected<Definition, LookupFinalizeError>
788 75805 : ForeverStack<N>::find_leaf_definition (const NodeId &key) const
789 : {
790 75805 : std::set<Usage> keys_seen;
791 :
792 75805 : return find_leaf_definition_inner (Usage (key), resolved_nodes, keys_seen);
793 75805 : }
794 :
795 : #if 0
796 : template <Namespace N>
797 : void
798 : ForeverStack<N>::flatten ()
799 : {
800 : for (auto &k_v : resolved_nodes)
801 : {
802 : // Loop detection
803 : auto keys_seen = std::set<Usage> ();
804 :
805 : auto result
806 : = find_leaf_definition_inner (k_v.first, resolved_nodes, keys_seen);
807 :
808 : if (!result)
809 : {
810 : // Trigger an ICE if we haven't found a definition because that's
811 : // really weird
812 : rust_assert (result.error () != LookupFinalizeError::NoDefinition);
813 :
814 : // FIXME: This needs to be improved and tested, but later
815 : rust_error_at (UNDEF_LOCATION, "import loop");
816 : continue;
817 : }
818 :
819 : // Replace the Definition for this Usage in the map. This may be a no-op.
820 : k_v.second = result.value ();
821 : }
822 : }
823 : #endif
824 :
825 : // FIXME: Can we add selftests?
826 :
827 : } // namespace Resolver2_0
828 : } // namespace Rust
|
