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 33591867 : ForeverStackBase::Node::is_root () const
33 : {
34 2841301 : return !parent.has_value ();
35 : }
36 :
37 : bool
38 75934 : ForeverStackBase::Node::is_prelude () const
39 : {
40 75934 : return rib_values.kind == Rib::Kind::Prelude;
41 : }
42 :
43 : bool
44 19476 : ForeverStackBase::Node::is_leaf () const
45 : {
46 19476 : 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 30745908 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
61 : tl::optional<Identifier> path)
62 : {
63 35952024 : push_inner (rib_kind, Link (id, path));
64 30745908 : }
65 :
66 : template <Namespace N>
67 : void
68 30745908 : ForeverStack<N>::push_inner (Rib::Kind rib_kind, Link link)
69 : {
70 30745908 : 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 19476 : rust_assert (&cursor_reference.get () == &root);
75 : // Prelude doesn't have an access path
76 19476 : rust_assert (!link.path);
77 19476 : update_cursor (this->lang_prelude);
78 19476 : 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 61452864 : auto emplace = cursor ().children.emplace (
86 30726432 : std::make_pair (link, Node (rib_kind, link.id, cursor ())));
87 :
88 30726432 : auto it = emplace.first;
89 30726432 : auto existed = !emplace.second;
90 :
91 30912597 : 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 30726432 : update_cursor (it->second);
98 : }
99 :
100 : template <Namespace N>
101 : void
102 30745872 : ForeverStack<N>::pop ()
103 : {
104 30745872 : rust_assert (!cursor ().is_root ());
105 :
106 30745872 : rust_debug ("popping link");
107 :
108 38859128 : for (const auto &kv : cursor ().rib (N).get_values ())
109 8113256 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
110 : kv.second.to_string ().c_str ());
111 :
112 30745872 : if (cursor ().parent.has_value ())
113 612759236 : for (const auto &kv : cursor ().parent.value ().rib (N).get_values ())
114 582013364 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
115 : kv.second.to_string ().c_str ());
116 :
117 30745872 : update_cursor (cursor ().parent.value ());
118 30745872 : }
119 :
120 : static tl::expected<NodeId, DuplicateNameError>
121 1429555 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
122 : {
123 2859110 : return rib.insert (name, definition);
124 : }
125 :
126 : template <Namespace N>
127 : tl::expected<NodeId, DuplicateNameError>
128 1370156 : ForeverStack<N>::insert (Identifier name, NodeId node)
129 : {
130 1370156 : 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 1370156 : return insert_inner (innermost_rib, name.as_string (),
137 2740312 : Rib::Definition::NonShadowable (node));
138 : }
139 :
140 : template <Namespace N>
141 : tl::expected<NodeId, DuplicateNameError>
142 45618 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
143 : {
144 45618 : auto &innermost_rib = peek ();
145 :
146 45618 : return insert_inner (innermost_rib, name.as_string (),
147 91236 : 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 1275 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
163 : {
164 1275 : 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 1275 : return insert_inner (root_rib, name.as_string (),
169 2550 : 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 2054 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
177 : {
178 2054 : return insert_inner (peek (), name.as_string (),
179 4108 : Rib::Definition::Shadowable (node));
180 : }
181 :
182 : template <>
183 : inline tl::expected<NodeId, DuplicateNameError>
184 63 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
185 : {
186 63 : return insert_inner (peek (), name.as_string (),
187 126 : Rib::Definition::Shadowable (node));
188 : }
189 :
190 : template <>
191 : inline tl::expected<NodeId, DuplicateNameError>
192 7606 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
193 : {
194 7606 : return insert_inner (peek (), name.as_string (),
195 15212 : Rib::Definition::NonShadowable (node, true));
196 : }
197 :
198 : template <>
199 : inline tl::expected<NodeId, DuplicateNameError>
200 1301 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
201 : {
202 1301 : return insert_inner (peek (), name.as_string (),
203 2602 : Rib::Definition::NonShadowable (node, true));
204 : }
205 :
206 : template <Namespace N>
207 : inline void
208 1482 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
209 : {
210 4446 : insert_inner (lang_prelude.rib (N), name.as_string (),
211 2964 : Rib::Definition::NonShadowable (id, false));
212 1482 : }
213 :
214 : template <Namespace N>
215 : Rib &
216 1685569 : ForeverStack<N>::peek ()
217 : {
218 1631753 : 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 50 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
231 : {
232 100 : 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 1137779 : ForeverStack<N>::reverse_iter (Node &start,
246 : std::function<KeepGoing (Node &)> lambda)
247 : {
248 1137779 : auto *tmp = &start;
249 :
250 2667256 : while (true)
251 : {
252 3805035 : auto keep_going = lambda (*tmp);
253 3805035 : if (keep_going == KeepGoing::No)
254 : return;
255 :
256 2741877 : if (tmp->is_root ())
257 : return;
258 :
259 2667256 : 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 156573611 : ForeverStack<N>::cursor ()
286 : {
287 155645333 : 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 30745908 : ForeverStack<N>::update_cursor (Node &new_cursor)
300 : {
301 30745908 : cursor_reference = new_cursor;
302 : }
303 :
304 : template <Namespace N>
305 : tl::optional<Rib::Definition>
306 1122024 : ForeverStack<N>::get (Node &start, const Identifier &name)
307 : {
308 1122024 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
309 :
310 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
311 4910677 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
312 : // we can't reference associated types/functions like this
313 3788653 : if (current.rib (N).kind == Rib::Kind::TraitOrImpl)
314 : return KeepGoing::Yes;
315 :
316 3315280 : auto candidate = current.rib (N).get (name.as_string ());
317 :
318 3315280 : if (candidate)
319 : {
320 343818 : 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 343813 : resolved_definition = *candidate;
327 :
328 343813 : return KeepGoing::No;
329 : }
330 : else
331 : {
332 2971462 : if (current.rib (N).kind == Rib::Kind::Module)
333 : return KeepGoing::No;
334 : else
335 2267872 : return KeepGoing::Yes;
336 : }
337 3788653 : });
338 :
339 1122024 : return resolved_definition;
340 : }
341 :
342 : template <Namespace N>
343 : tl::optional<Rib::Definition>
344 874863 : ForeverStack<N>::get (const Identifier &name)
345 : {
346 874863 : 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 90566 : ForeverStack<N>::get_lang_prelude (const std::string &name)
359 : {
360 90566 : 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 50 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
376 : const Identifier &name)
377 : {
378 50 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
379 :
380 50 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
381 : // looking up for labels cannot go through function ribs
382 : // TODO: What other ribs?
383 187 : if (current.rib_labels.kind == Rib::Kind::Function)
384 : return KeepGoing::No;
385 :
386 182 : auto candidate = current.rib_labels.get (name.as_string ());
387 :
388 : // FIXME: Factor this in a function with the generic `get`
389 182 : return candidate.map_or (
390 409 : [&resolved_definition] (Rib::Definition found) {
391 45 : resolved_definition = found;
392 :
393 45 : return KeepGoing::No;
394 : },
395 182 : KeepGoing::Yes);
396 187 : });
397 :
398 50 : 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 144631 : is_last (const I &iterator, const C &collection)
405 : {
406 235880 : 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 334897 : is_start (const I &iterator, const C &collection)
413 : {
414 334897 : return iterator == collection.begin ();
415 : }
416 :
417 : template <Namespace N>
418 : typename ForeverStack<N>::Node &
419 15705 : ForeverStack<N>::find_closest_module (Node &starting_point)
420 : {
421 15705 : auto *closest_module = &starting_point;
422 :
423 31900 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
424 16195 : if (current.rib (N).kind == Rib::Kind::Module || current.is_root ())
425 : {
426 15705 : closest_module = ¤t;
427 15705 : return KeepGoing::No;
428 : }
429 :
430 : return KeepGoing::Yes;
431 : });
432 :
433 15705 : 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 177657 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
440 : const ResolutionPath::Segment &segment,
441 : bool condition)
442 : {
443 177657 : 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 177657 : 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 80795 : 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 80795 : auto iterator = segments.begin ();
465 :
466 91255 : for (; iterator != segments.end (); iterator++)
467 : {
468 91249 : auto &seg = *iterator;
469 :
470 : // don't include a final self segment
471 91249 : if (is_last (iterator, segments) && seg.is_lower_self_seg ())
472 : break;
473 :
474 91249 : bool is_self_or_crate
475 91249 : = 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 91249 : if (check_leading_kw_at_start (collect_errors, seg,
480 91249 : !is_start (iterator, segments)
481 : && is_self_or_crate))
482 1 : return tl::nullopt;
483 :
484 91248 : if (seg.is_crate_path_seg ())
485 : {
486 29820 : starting_point = root;
487 29820 : insert_segment_resolution (Usage (seg.node_id),
488 29820 : Definition (starting_point.get ().id), N);
489 29820 : iterator++;
490 29820 : break;
491 : }
492 61428 : if (seg.is_lower_self_seg ())
493 : {
494 : // insert segment resolution
495 5767 : starting_point = find_closest_module (starting_point);
496 5767 : insert_segment_resolution (Usage (seg.node_id),
497 5767 : Definition (starting_point.get ().id), N);
498 : // don't exit -- we could see some "super" segments
499 5767 : continue;
500 : }
501 55661 : if (seg.is_super_path_seg ())
502 : {
503 4694 : starting_point = find_closest_module (starting_point);
504 4694 : 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 4693 : starting_point
513 4693 : = find_closest_module (starting_point.get ().parent.value ());
514 :
515 4693 : insert_segment_resolution (Usage (seg.node_id),
516 4693 : Definition (starting_point.get ().id), N);
517 4693 : 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 80793 : 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 48925 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
593 : {
594 97450 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
595 48525 : return x.rib (N);
596 48925 : });
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 4620373 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
611 : NodeId to_find)
612 : {
613 4620373 : if (auto found = check_cache (to_find))
614 79937 : return found;
615 :
616 4540436 : if (starting_point.id == to_find)
617 : {
618 718 : cache (to_find, starting_point);
619 :
620 718 : return starting_point;
621 : }
622 :
623 9077379 : for (auto &child : starting_point.children)
624 : {
625 4539318 : auto candidate = dfs_node (child.second, to_find);
626 :
627 4539318 : if (candidate.has_value ())
628 1657 : return candidate;
629 : }
630 :
631 4538061 : 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 4620373 : ForeverStack<N>::check_cache (NodeId to_find)
656 : {
657 4620373 : auto entry = dfs_cache.find (to_find);
658 :
659 4620373 : if (entry != dfs_cache.end ())
660 79937 : return entry->second;
661 :
662 4540436 : return tl::nullopt;
663 : }
664 :
665 : template <Namespace N>
666 : void
667 718 : ForeverStack<N>::cache (NodeId found, typename ForeverStack<N>::Node &result)
668 : {
669 718 : 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 103002 : find_leaf_definition_inner (const Usage &key,
764 : const std::map<Usage, Definition> &resolved_nodes,
765 : std::set<Usage> &keys_seen)
766 : {
767 103002 : auto original_definition = resolved_nodes.find (key);
768 103002 : auto possible_import = Usage (original_definition->second.id);
769 :
770 103002 : if (original_definition == resolved_nodes.end ())
771 103002 : 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 103002 : ForeverStack<N>::find_leaf_definition (const NodeId &key) const
789 : {
790 103002 : std::set<Usage> keys_seen;
791 :
792 103002 : return find_leaf_definition_inner (Usage (key), resolved_nodes, keys_seen);
793 103002 : }
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
|
