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 2012871 : ForeverStack<N>::Node::is_root () const
34 : {
35 417681 : 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 19084 : ForeverStack<N>::Node::is_leaf () const
48 : {
49 19084 : 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 1620462 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : tl::optional<Identifier> path)
66 : {
67 2204229 : push_inner (rib_kind, Link (id, path));
68 1620462 : }
69 :
70 : template <Namespace N>
71 : void
72 1620462 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : {
74 1620462 : 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 14313 : rust_assert (&cursor_reference.get () == &root);
79 : // Prelude doesn't have an access path
80 14313 : rust_assert (!link.path);
81 14313 : update_cursor (this->lang_prelude);
82 14313 : 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 3212298 : auto emplace = cursor ().children.emplace (
90 1606149 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 :
92 1606149 : auto it = emplace.first;
93 1606149 : auto existed = !emplace.second;
94 :
95 1847211 : 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 1606149 : update_cursor (it->second);
102 : }
103 :
104 : template <Namespace N>
105 : void
106 1620438 : ForeverStack<N>::pop ()
107 : {
108 1620438 : rust_assert (!cursor ().is_root ());
109 :
110 1620438 : rust_debug ("popping link");
111 :
112 1961149 : for (const auto &kv : cursor ().rib.get_values ())
113 340711 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : kv.second.to_string ().c_str ());
115 :
116 1620438 : if (cursor ().parent.has_value ())
117 3187720 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 1567282 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : kv.second.to_string ().c_str ());
120 :
121 1620438 : update_cursor (cursor ().parent.value ());
122 1620438 : }
123 :
124 : static tl::expected<NodeId, DuplicateNameError>
125 281563 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : {
127 563126 : return rib.insert (name, definition);
128 : }
129 :
130 : template <Namespace N>
131 : tl::expected<NodeId, DuplicateNameError>
132 250763 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : {
134 250763 : 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 250763 : return insert_inner (innermost_rib, name.as_string (),
141 501526 : Rib::Definition::NonShadowable (node));
142 : }
143 :
144 : template <Namespace N>
145 : tl::expected<NodeId, DuplicateNameError>
146 24689 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : {
148 24689 : auto &innermost_rib = peek ();
149 :
150 24689 : return insert_inner (innermost_rib, name.as_string (),
151 49378 : Rib::Definition::Shadowable (node));
152 : }
153 :
154 : template <Namespace N>
155 : tl::expected<NodeId, DuplicateNameError>
156 84 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : {
158 84 : auto &innermost_rib = peek ();
159 :
160 84 : return insert_inner (innermost_rib, name.as_string (),
161 168 : 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 164 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : {
182 164 : return insert_inner (peek (), name.as_string (),
183 328 : Rib::Definition::Shadowable (node));
184 : }
185 :
186 : template <>
187 : inline tl::expected<NodeId, DuplicateNameError>
188 48 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
189 : {
190 48 : return insert_inner (peek (), name.as_string (),
191 96 : Rib::Definition::Shadowable (node));
192 : }
193 :
194 : template <>
195 : inline tl::expected<NodeId, DuplicateNameError>
196 4348 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : {
198 4348 : return insert_inner (peek (), name.as_string (),
199 8696 : Rib::Definition::NonShadowable (node, true));
200 : }
201 :
202 : template <>
203 : inline tl::expected<NodeId, DuplicateNameError>
204 1194 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
205 : {
206 1194 : return insert_inner (peek (), name.as_string (),
207 2388 : 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 338473 : ForeverStack<N>::peek ()
221 : {
222 338473 : 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 30 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
235 : {
236 60 : 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 159084 : ForeverStack<N>::reverse_iter (Node &start,
250 : std::function<KeepGoing (Node &)> lambda)
251 : {
252 159084 : auto *tmp = &start;
253 :
254 298060 : while (true)
255 : {
256 457144 : auto keep_going = lambda (*tmp);
257 457144 : if (keep_going == KeepGoing::No)
258 : return;
259 :
260 371974 : if (tmp->is_root ())
261 : return;
262 :
263 298060 : 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 8598125 : ForeverStack<N>::cursor ()
290 : {
291 8513467 : 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 1620462 : ForeverStack<N>::update_cursor (Node &new_cursor)
304 : {
305 1620462 : cursor_reference = new_cursor;
306 : }
307 :
308 : template <Namespace N>
309 : tl::optional<Rib::Definition>
310 157186 : ForeverStack<N>::get (Node &start, const Identifier &name)
311 : {
312 157186 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
313 :
314 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
315 612388 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
316 : // we can't reference associated types/functions like this
317 455202 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
318 : return KeepGoing::Yes;
319 :
320 412491 : auto candidate = current.rib.get (name.as_string ());
321 :
322 412491 : if (candidate)
323 : {
324 72297 : 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 72292 : resolved_definition = *candidate;
331 :
332 72292 : return KeepGoing::No;
333 : }
334 : else
335 : {
336 340194 : if (current.rib.kind == Rib::Kind::Module)
337 : return KeepGoing::No;
338 : else
339 : return KeepGoing::Yes;
340 : }
341 412491 : });
342 :
343 157186 : return resolved_definition;
344 : }
345 :
346 : template <Namespace N>
347 : tl::optional<Rib::Definition>
348 84658 : ForeverStack<N>::get (const Identifier &name)
349 : {
350 84658 : 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 30916 : ForeverStack<N>::get_lang_prelude (const std::string &name)
363 : {
364 30916 : 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 30 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
380 : const Identifier &name)
381 : {
382 30 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
383 :
384 30 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
385 : // looking up for labels cannot go through function ribs
386 : // TODO: What other ribs?
387 30 : if (current.rib.kind == Rib::Kind::Function)
388 : return KeepGoing::No;
389 :
390 30 : auto candidate = current.rib.get (name.as_string ());
391 :
392 : // FIXME: Factor this in a function with the generic `get`
393 30 : return candidate.map_or (
394 85 : [&resolved_definition] (Rib::Definition found) {
395 25 : resolved_definition = found;
396 :
397 25 : return KeepGoing::No;
398 : },
399 30 : KeepGoing::Yes);
400 30 : });
401 :
402 30 : 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 29780 : is_last (const I &iterator, const C &collection)
409 : {
410 44839 : 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 102095 : is_start (const I &iterator, const C &collection)
417 : {
418 102095 : return iterator == collection.begin ();
419 : }
420 :
421 : template <Namespace N>
422 : typename ForeverStack<N>::Node &
423 1868 : ForeverStack<N>::find_closest_module (Node &starting_point)
424 : {
425 1868 : auto *closest_module = &starting_point;
426 :
427 3780 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
428 1912 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
429 : {
430 1868 : closest_module = ¤t;
431 1868 : return KeepGoing::No;
432 : }
433 :
434 : return KeepGoing::Yes;
435 : });
436 :
437 1868 : 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 32183 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
444 : const ResolutionPath::Segment &segment,
445 : bool condition)
446 : {
447 32183 : 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 32183 : 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 14141 : 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, Namespace)> insert_segment_resolution,
466 : std::vector<Error> &collect_errors)
467 : {
468 14141 : auto iterator = segments.begin ();
469 :
470 15059 : for (; !is_last (iterator, segments); iterator++)
471 : {
472 14669 : auto &seg = *iterator;
473 :
474 14669 : bool is_self_or_crate
475 14669 : = 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 14669 : if (check_leading_kw_at_start (collect_errors, seg,
480 14669 : !is_start (iterator, segments)
481 14669 : && is_self_or_crate))
482 1 : return tl::nullopt;
483 :
484 14668 : if (seg.is_crate_path_seg ())
485 : {
486 742 : starting_point = root;
487 742 : insert_segment_resolution (Usage (seg.node_id),
488 742 : Definition (starting_point.get ().id), N);
489 742 : iterator++;
490 : break;
491 : }
492 13926 : if (seg.is_lower_self_seg ())
493 : {
494 : // insert segment resolution and exit
495 24 : starting_point = find_closest_module (starting_point);
496 24 : insert_segment_resolution (Usage (seg.node_id),
497 24 : Definition (starting_point.get ().id), N);
498 24 : iterator++;
499 : break;
500 : }
501 13902 : if (seg.is_super_path_seg ())
502 : {
503 919 : starting_point = find_closest_module (starting_point);
504 919 : 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 918 : starting_point
513 918 : = find_closest_module (starting_point.get ().parent.value ());
514 :
515 918 : insert_segment_resolution (Usage (seg.node_id),
516 918 : Definition (starting_point.get ().id), N);
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 14139 : 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.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.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 1360 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
593 : {
594 1360 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
595 53 : return x.rib;
596 1360 : });
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; });
606 : }
607 :
608 : template <Namespace N>
609 : tl::optional<typename ForeverStack<N>::Node &>
610 1486819 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
611 : NodeId to_find)
612 : {
613 1486819 : if (starting_point.id == to_find)
614 28746 : return starting_point;
615 :
616 2850933 : for (auto &child : starting_point.children)
617 : {
618 1456766 : auto candidate = dfs_node (child.second, to_find);
619 :
620 1456766 : if (candidate.has_value ())
621 63906 : return candidate;
622 : }
623 :
624 1394167 : return tl::nullopt;
625 : }
626 :
627 : template <Namespace N>
628 : tl::optional<const typename ForeverStack<N>::Node &>
629 131 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
630 : NodeId to_find) const
631 : {
632 131 : if (starting_point.id == to_find)
633 16 : return starting_point;
634 :
635 189 : for (auto &child : starting_point.children)
636 : {
637 103 : auto candidate = dfs_node (child.second, to_find);
638 :
639 103 : if (candidate.has_value ())
640 29 : return candidate;
641 : }
642 :
643 86 : return tl::nullopt;
644 : }
645 :
646 : template <Namespace N>
647 : tl::optional<Rib &>
648 52 : ForeverStack<N>::to_rib (NodeId rib_id)
649 : {
650 52 : return dfs_rib (root, rib_id);
651 : }
652 :
653 : template <Namespace N>
654 : tl::optional<const Rib &>
655 : ForeverStack<N>::to_rib (NodeId rib_id) const
656 : {
657 : return dfs_rib (root, rib_id);
658 : }
659 :
660 : template <Namespace N>
661 : void
662 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
663 : const std::string &next,
664 : const std::string &next_next) const
665 : {
666 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
667 0 : stream << next << "rib [" << rib_kind << "]: {";
668 0 : if (rib.get_values ().empty ())
669 : {
670 0 : stream << "}\n";
671 0 : return;
672 : }
673 : else
674 : {
675 0 : stream << "\n";
676 : }
677 :
678 0 : for (const auto &kv : rib.get_values ())
679 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
680 :
681 0 : stream << next << "},\n";
682 0 : }
683 :
684 : template <Namespace N>
685 : void
686 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
687 : const ForeverStack<N>::Node &node,
688 : unsigned depth) const
689 : {
690 0 : auto indent = std::string (indentation, ' ');
691 0 : auto next = std::string (indentation + 4, ' ');
692 0 : auto next_next = std::string (indentation + 8, ' ');
693 :
694 : stream << indent << "Node {\n"
695 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
696 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
697 0 : << ",\n";
698 :
699 0 : stream_rib (stream, node.rib, next, next_next);
700 :
701 0 : stream << indent << "}\n";
702 :
703 0 : for (auto &kv : node.children)
704 : {
705 0 : auto link = kv.first;
706 0 : auto child = kv.second;
707 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
708 0 : << (link.path.has_value () ? link.path.value ().as_string ()
709 0 : : "<anon>")
710 0 : << "):\n";
711 :
712 0 : stream_node (stream, indentation + 4, child, depth + 1);
713 :
714 0 : stream << '\n';
715 : }
716 0 : }
717 :
718 : template <Namespace N>
719 : std::string
720 0 : ForeverStack<N>::as_debug_string () const
721 : {
722 0 : std::stringstream stream;
723 :
724 0 : stream_node (stream, 0, root);
725 :
726 0 : return stream.str ();
727 0 : }
728 :
729 : template <Namespace N>
730 : bool
731 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
732 : {
733 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
734 : }
735 :
736 : static tl::expected<Definition, LookupFinalizeError>
737 10963 : find_leaf_definition_inner (const Usage &key,
738 : const std::map<Usage, Definition> &resolved_nodes,
739 : std::set<Usage> &keys_seen)
740 : {
741 10963 : auto original_definition = resolved_nodes.find (key);
742 10963 : auto possible_import = Usage (original_definition->second.id);
743 :
744 10963 : if (original_definition == resolved_nodes.end ())
745 10963 : return tl::make_unexpected (LookupFinalizeError::NoDefinition);
746 :
747 0 : if (!keys_seen.insert (key).second)
748 0 : return tl::make_unexpected (LookupFinalizeError::Loop);
749 :
750 0 : if (resolved_nodes.find (possible_import) == resolved_nodes.end ())
751 0 : return original_definition->second;
752 :
753 : // We're dealing with an import - a reference to another
754 : // definition. Go through the chain and update the original key's
755 : // corresponding definition.
756 0 : return find_leaf_definition_inner (possible_import, resolved_nodes,
757 0 : keys_seen);
758 : }
759 :
760 : template <Namespace N>
761 : tl::expected<Definition, LookupFinalizeError>
762 10963 : ForeverStack<N>::find_leaf_definition (const NodeId &key) const
763 : {
764 10963 : std::set<Usage> keys_seen;
765 :
766 10963 : return find_leaf_definition_inner (Usage (key), resolved_nodes, keys_seen);
767 10963 : }
768 :
769 : #if 0
770 : template <Namespace N>
771 : void
772 : ForeverStack<N>::flatten ()
773 : {
774 : for (auto &k_v : resolved_nodes)
775 : {
776 : // Loop detection
777 : auto keys_seen = std::set<Usage> ();
778 :
779 : auto result
780 : = find_leaf_definition_inner (k_v.first, resolved_nodes, keys_seen);
781 :
782 : if (!result)
783 : {
784 : // Trigger an ICE if we haven't found a definition because that's
785 : // really weird
786 : rust_assert (result.error () != LookupFinalizeError::NoDefinition);
787 :
788 : // FIXME: This needs to be improved and tested, but later
789 : rust_error_at (UNDEF_LOCATION, "import loop");
790 : continue;
791 : }
792 :
793 : // Replace the Definition for this Usage in the map. This may be a no-op.
794 : k_v.second = result.value ();
795 : }
796 : }
797 : #endif
798 :
799 : // FIXME: Can we add selftests?
800 :
801 : } // namespace Resolver2_0
802 : } // namespace Rust
|
