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 250824249 : ForeverStackBase::Node::is_root () const
33 : {
34 19219236 : return !parent.has_value ();
35 : }
36 :
37 : bool
38 436098 : ForeverStackBase::Node::is_prelude () const
39 : {
40 436098 : return rib_values.kind == Rib::Kind::Prelude;
41 : }
42 :
43 : bool
44 21336 : ForeverStackBase::Node::is_leaf () const
45 : {
46 21336 : return children.empty ();
47 : }
48 :
49 : void
50 328 : ForeverStackBase::Node::insert_child (Link link, Node child)
51 : {
52 328 : 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 328 : }
57 :
58 : template <Namespace N>
59 : void
60 231573088 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
61 : tl::optional<Identifier> path)
62 : {
63 240059044 : push_inner (rib_kind, Link (id, path));
64 231573088 : }
65 :
66 : template <Namespace N>
67 : void
68 231573088 : ForeverStack<N>::push_inner (Rib::Kind rib_kind, Link link)
69 : {
70 231573088 : 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 21336 : rust_assert (&cursor_reference.get () == &root);
75 : // Prelude doesn't have an access path
76 21336 : rust_assert (!link.path);
77 21336 : update_cursor (this->lang_prelude);
78 21336 : 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 463103504 : auto emplace = cursor ().children.emplace (
86 231551752 : std::make_pair (link, Node (rib_kind, link.id, cursor ())));
87 :
88 231551752 : auto it = emplace.first;
89 231551752 : auto existed = !emplace.second;
90 :
91 231551754 : 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 231551752 : update_cursor (it->second);
98 : }
99 :
100 : template <Namespace N>
101 : void
102 231573052 : ForeverStack<N>::pop ()
103 : {
104 231573052 : rust_assert (!cursor ().is_root ());
105 :
106 231573052 : rust_debug ("popping link");
107 :
108 294212392 : for (const auto &kv : cursor ().rib (N).get_values ())
109 62639340 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
110 : kv.second.to_string ().c_str ());
111 :
112 231573052 : if (cursor ().parent.has_value ())
113 4878099788 : for (const auto &kv : cursor ().parent.value ().rib (N).get_values ())
114 4646526736 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
115 : kv.second.to_string ().c_str ());
116 :
117 231573052 : update_cursor (cursor ().parent.value ());
118 231573052 : }
119 :
120 : static tl::expected<NodeId, DuplicateNameError>
121 9506591 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
122 : {
123 19013182 : return rib.insert (name, definition);
124 : }
125 :
126 : template <Namespace N>
127 : tl::expected<NodeId, DuplicateNameError>
128 9259365 : ForeverStack<N>::insert (Identifier name, NodeId node)
129 : {
130 9259365 : 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 9259365 : return insert_inner (innermost_rib, name.as_string (),
137 18518730 : Rib::Definition::NonShadowable (node));
138 : }
139 :
140 : template <Namespace N>
141 : tl::expected<NodeId, DuplicateNameError>
142 177673 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
143 : {
144 177673 : auto &innermost_rib = peek ();
145 :
146 177673 : return insert_inner (innermost_rib, name.as_string (),
147 355346 : 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 10158 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
163 : {
164 10158 : 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 10158 : return insert_inner (root_rib, name.as_string (),
169 20316 : 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 15474 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
177 : {
178 15474 : return insert_inner (peek (), name.as_string (),
179 30948 : Rib::Definition::Shadowable (node));
180 : }
181 :
182 : template <>
183 : inline tl::expected<NodeId, DuplicateNameError>
184 78 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
185 : {
186 78 : return insert_inner (peek (), name.as_string (),
187 156 : Rib::Definition::Shadowable (node));
188 : }
189 :
190 : template <>
191 : inline tl::expected<NodeId, DuplicateNameError>
192 30784 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
193 : {
194 30784 : return insert_inner (peek (), name.as_string (),
195 61568 : Rib::Definition::NonShadowable (node, true));
196 : }
197 :
198 : template <>
199 : inline tl::expected<NodeId, DuplicateNameError>
200 2103 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
201 : {
202 2103 : return insert_inner (peek (), name.as_string (),
203 4206 : Rib::Definition::NonShadowable (node, true));
204 : }
205 :
206 : template <Namespace N>
207 : void
208 896 : ForeverStack<N>::insert_crate_in_prelude (Identifier crate_name,
209 : NodeId extern_crate_node_id)
210 : {
211 896 : auto &extern_prelude_rib = extern_prelude.rib (N);
212 896 : auto definition = Rib::Definition::NonShadowable (extern_crate_node_id);
213 2380 : insert_inner (extern_prelude_rib, crate_name, definition);
214 896 : }
215 :
216 : template <Namespace N>
217 : inline void
218 10060 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
219 : {
220 30180 : insert_inner (lang_prelude.rib (N), name.as_string (),
221 20120 : Rib::Definition::NonShadowable (id, false));
222 10060 : }
223 :
224 : template <Namespace N>
225 : Rib &
226 11109047 : ForeverStack<N>::peek ()
227 : {
228 10708863 : return cursor ().rib (N);
229 : }
230 :
231 : template <Namespace N>
232 : const Rib &
233 : ForeverStack<N>::peek () const
234 : {
235 : return cursor ().rib (N);
236 : }
237 :
238 : template <Namespace N>
239 : void
240 93 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
241 : {
242 186 : return reverse_iter (cursor (), lambda);
243 : }
244 :
245 : template <Namespace N>
246 : void
247 : ForeverStack<N>::reverse_iter (
248 : std::function<KeepGoing (const Node &)> lambda) const
249 : {
250 : return reverse_iter (cursor (), lambda);
251 : }
252 :
253 : template <Namespace N>
254 : void
255 7810185 : ForeverStack<N>::reverse_iter (Node &start,
256 : std::function<KeepGoing (Node &)> lambda)
257 : {
258 7810185 : auto *tmp = &start;
259 :
260 18646717 : while (true)
261 : {
262 26456902 : auto keep_going = lambda (*tmp);
263 26456902 : if (keep_going == KeepGoing::No)
264 : return;
265 :
266 18733526 : if (tmp->is_root ())
267 : return;
268 :
269 18646717 : tmp = &tmp->parent.value ();
270 : }
271 : }
272 :
273 : template <Namespace N>
274 : void
275 : ForeverStack<N>::reverse_iter (
276 : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
277 : {
278 : auto *tmp = &start;
279 :
280 : while (true)
281 : {
282 : auto keep_going = lambda (*tmp);
283 : if (keep_going == KeepGoing::No)
284 : return;
285 :
286 : if (tmp->is_root ())
287 : return;
288 :
289 : tmp = &tmp->parent.value ();
290 : }
291 : }
292 :
293 : template <Namespace N>
294 : typename ForeverStack<N>::Node &
295 1177003446 : ForeverStack<N>::cursor ()
296 : {
297 1170166162 : return cursor_reference;
298 : }
299 :
300 : template <Namespace N>
301 : const typename ForeverStack<N>::Node &
302 0 : ForeverStack<N>::cursor () const
303 : {
304 0 : return cursor_reference;
305 : }
306 :
307 : template <Namespace N>
308 : void
309 231573088 : ForeverStack<N>::update_cursor (Node &new_cursor)
310 : {
311 231573088 : cursor_reference = new_cursor;
312 : }
313 :
314 : template <Namespace N>
315 : tl::optional<Rib::Definition>
316 7695751 : ForeverStack<N>::get (Node &start, const Identifier &name)
317 : {
318 7695751 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
319 :
320 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
321 34034133 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
322 : // we can't reference associated types/functions like this
323 26338382 : if (current.rib (N).kind == Rib::Kind::TraitOrImpl)
324 : return KeepGoing::Yes;
325 :
326 23064898 : auto candidate = current.rib (N).get (name.as_string ());
327 :
328 23064898 : if (candidate)
329 : {
330 2038832 : if (candidate->is_variant ())
331 : return KeepGoing::Yes;
332 : // for most namespaces, we do not need to care about various ribs -
333 : // they are available from all contexts if defined in the current
334 : // scope, or an outermore one. so if we do have a candidate, we can
335 : // return it directly and stop iterating
336 2038827 : resolved_definition = *candidate;
337 :
338 2038827 : return KeepGoing::No;
339 : }
340 : else
341 : {
342 21026066 : if (current.rib (N).kind == Rib::Kind::Module)
343 : return KeepGoing::No;
344 : else
345 15455951 : return KeepGoing::Yes;
346 : }
347 26338382 : });
348 :
349 7695751 : return resolved_definition;
350 : }
351 :
352 : template <Namespace N>
353 : tl::optional<Rib::Definition>
354 6437152 : ForeverStack<N>::get (const Identifier &name)
355 : {
356 6437152 : return get (cursor (), name);
357 : }
358 :
359 : template <Namespace N>
360 : tl::optional<Rib::Definition>
361 11 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
362 : {
363 11 : return lang_prelude.rib (N).get (name.as_string ());
364 : }
365 :
366 : template <Namespace N>
367 : tl::optional<Rib::Definition>
368 513625 : ForeverStack<N>::get_lang_prelude (const std::string &name)
369 : {
370 513625 : return lang_prelude.rib (N).get (name);
371 : }
372 :
373 : template <Namespace N>
374 : tl::optional<Rib::Definition>
375 : ForeverStack<N>::get_from_prelude (NodeId prelude, const Identifier &name)
376 : {
377 : auto starting_point = dfs_node (root, prelude);
378 : if (!starting_point)
379 : return tl::nullopt;
380 :
381 : return get (*starting_point, name);
382 : }
383 :
384 : template <>
385 93 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
386 : const Identifier &name)
387 : {
388 93 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
389 :
390 93 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
391 : // looking up for labels cannot go through function ribs
392 : // TODO: What other ribs?
393 455 : if (current.rib_labels.kind == Rib::Kind::Function)
394 : return KeepGoing::No;
395 :
396 450 : auto candidate = current.rib_labels.get (name.as_string ());
397 :
398 : // FIXME: Factor this in a function with the generic `get`
399 450 : return candidate.map_or (
400 988 : [&resolved_definition] (Rib::Definition found) {
401 88 : resolved_definition = found;
402 :
403 88 : return KeepGoing::No;
404 : },
405 450 : KeepGoing::Yes);
406 455 : });
407 :
408 93 : return resolved_definition;
409 : }
410 :
411 : /* Check if an iterator points to the last element */
412 : template <typename I, typename C>
413 : static bool
414 973047 : is_last (const I &iterator, const C &collection)
415 : {
416 1604820 : return iterator + 1 == collection.end ();
417 : }
418 :
419 : /* Check if an iterator points to the start of the collection */
420 : template <typename I, typename C>
421 : static bool
422 2022753 : is_start (const I &iterator, const C &collection)
423 : {
424 2022753 : return iterator == collection.begin ();
425 : }
426 :
427 : template <Namespace N>
428 : typename ForeverStack<N>::Node &
429 114341 : ForeverStack<N>::find_closest_module (Node &starting_point)
430 : {
431 114341 : auto *closest_module = &starting_point;
432 :
433 232406 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
434 118065 : if (current.rib (N).kind == Rib::Kind::Module || current.is_root ())
435 : {
436 114341 : closest_module = ¤t;
437 114341 : return KeepGoing::No;
438 : }
439 :
440 : return KeepGoing::Yes;
441 : });
442 :
443 114341 : return *closest_module;
444 : }
445 :
446 : /* If a the given condition is met, emit an error about misused leading path
447 : * segments */
448 : static inline bool
449 1218985 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
450 : const ResolutionPathSegment &segment, bool condition)
451 : {
452 1218985 : if (condition)
453 11 : collect_errors.emplace_back (
454 11 : segment.locus, ErrorCode::E0433,
455 11 : "%qs in paths can only be used in start position", segment.name.c_str ());
456 :
457 1218985 : return condition;
458 : }
459 :
460 : // we first need to handle the "starting" segments - `super`, `self` or
461 : // `crate`. we don't need to do anything for `self` and can just skip it. for
462 : // `crate`, we need to go back to the root of the current stack. for each
463 : // `super` segment, we go back to the cursor's parent until we reach the
464 : // correct one or the root.
465 : template <Namespace N>
466 : tl::optional<typename std::vector<ResolutionPathSegment>::const_iterator>
467 553793 : ForeverStack<N>::find_starting_point (
468 : const RawPath<ResolutionPathSegment> &path,
469 : std::reference_wrapper<Node> &starting_point,
470 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
471 : std::vector<Error> &collect_errors)
472 : {
473 553793 : auto &segments = path.get_segments ();
474 553793 : auto iterator = segments.begin ();
475 :
476 631807 : for (; iterator != segments.end (); iterator++)
477 : {
478 631773 : auto &seg = *iterator;
479 :
480 : // don't include a final self segment
481 631773 : if (is_last (iterator, segments) && seg.is_lower_self_seg ())
482 : break;
483 :
484 631773 : bool is_self_or_crate
485 631773 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
486 :
487 : // if we're after the first path segment and meet `self` or `crate`, it's
488 : // an error - we should only be seeing `super` keywords at this point
489 631773 : if (check_leading_kw_at_start (collect_errors, seg,
490 631773 : !is_start (iterator, segments)
491 : && is_self_or_crate))
492 1 : return tl::nullopt;
493 :
494 631772 : if (seg.is_crate_path_seg ())
495 : {
496 222817 : if (path.has_opening_scope_resolution ())
497 : {
498 6 : collect_errors.emplace_back (seg.locus, ErrorCode::E0433,
499 : "global paths cannot start with %qs",
500 6 : seg.name.c_str ());
501 6 : return tl::nullopt;
502 : }
503 222811 : starting_point = root;
504 222811 : insert_segment_resolution (Usage (seg.node_id),
505 222811 : Definition (starting_point.get ().id), N);
506 222811 : iterator++;
507 222811 : break;
508 : }
509 408955 : if (seg.is_lower_self_seg ())
510 : {
511 : // insert segment resolution
512 46054 : starting_point = find_closest_module (starting_point);
513 46054 : insert_segment_resolution (Usage (seg.node_id),
514 46054 : Definition (starting_point.get ().id), N);
515 : // don't exit -- we could see some "super" segments
516 46054 : continue;
517 : }
518 362901 : if (seg.is_super_path_seg ())
519 : {
520 31961 : starting_point = find_closest_module (starting_point);
521 31961 : if (starting_point.get ().is_root ())
522 : {
523 1 : collect_errors.emplace_back (
524 1 : seg.locus, ErrorCode::E0433,
525 : "too many leading %<super%> keywords");
526 1 : return tl::nullopt;
527 : }
528 :
529 31960 : starting_point
530 31960 : = find_closest_module (starting_point.get ().parent.value ());
531 :
532 31960 : insert_segment_resolution (Usage (seg.node_id),
533 31960 : Definition (starting_point.get ().id), N);
534 31960 : continue;
535 : }
536 :
537 : // now we've gone through the allowed `crate`, `self` or leading `super`
538 : // segments. we can start resolving each segment itself.
539 : // if we do see another leading segment, then we can error out.
540 : break;
541 : }
542 :
543 553785 : return iterator;
544 : }
545 :
546 : template <Namespace N>
547 : tl::optional<typename ForeverStack<N>::DfsResult>
548 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
549 : {
550 : auto values = starting_point.rib (N).get_values ();
551 :
552 : for (auto &kv : values)
553 : {
554 : for (auto id : kv.second.ids_shadowable)
555 : if (id == to_find)
556 : return {{starting_point, kv.first}};
557 : for (auto id : kv.second.ids_non_shadowable)
558 : if (id == to_find)
559 : return {{starting_point, kv.first}};
560 : for (auto id : kv.second.ids_globbed)
561 : if (id == to_find)
562 : return {{starting_point, kv.first}};
563 : }
564 :
565 : for (auto &child : starting_point.children)
566 : {
567 : auto candidate = dfs (child.second, to_find);
568 :
569 : if (candidate.has_value ())
570 : return candidate;
571 : }
572 :
573 : return tl::nullopt;
574 : }
575 :
576 : template <Namespace N>
577 : tl::optional<typename ForeverStack<N>::ConstDfsResult>
578 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
579 : NodeId to_find) const
580 : {
581 : auto values = starting_point.rib (N).get_values ();
582 :
583 : for (auto &kv : values)
584 : {
585 : for (auto id : kv.second.ids_shadowable)
586 : if (id == to_find)
587 : return {{starting_point, kv.first}};
588 : for (auto id : kv.second.ids_non_shadowable)
589 : if (id == to_find)
590 : return {{starting_point, kv.first}};
591 : for (auto id : kv.second.ids_globbed)
592 : if (id == to_find)
593 : return {{starting_point, kv.first}};
594 : }
595 :
596 : for (auto &child : starting_point.children)
597 : {
598 : auto candidate = dfs (child.second, to_find);
599 :
600 : if (candidate.has_value ())
601 : return candidate;
602 : }
603 :
604 : return tl::nullopt;
605 : }
606 :
607 : template <Namespace N>
608 : tl::optional<Rib &>
609 387452 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
610 : {
611 774904 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
612 387452 : return x.rib (N);
613 387452 : });
614 : }
615 :
616 : template <Namespace N>
617 : tl::optional<const Rib &>
618 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
619 : NodeId to_find) const
620 : {
621 : return dfs_node (starting_point, to_find)
622 : .map ([] (const Node &x) -> const Rib & { return x.rib (N); });
623 : }
624 :
625 : template <Namespace N>
626 : tl::optional<typename ForeverStack<N>::Node &>
627 37138171 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
628 : NodeId to_find)
629 : {
630 37138171 : if (auto found = check_cache (to_find))
631 627748 : return found;
632 :
633 36510423 : if (starting_point.id == to_find)
634 : {
635 2934 : cache (to_find, starting_point);
636 :
637 2934 : return starting_point;
638 : }
639 :
640 73007774 : for (auto &child : starting_point.children)
641 : {
642 36507489 : auto candidate = dfs_node (child.second, to_find);
643 :
644 36507489 : if (candidate.has_value ())
645 7204 : return candidate;
646 : }
647 :
648 36500285 : return tl::nullopt;
649 : }
650 :
651 : template <Namespace N>
652 : tl::optional<const typename ForeverStack<N>::Node &>
653 131 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
654 : NodeId to_find) const
655 : {
656 131 : if (starting_point.id == to_find)
657 16 : return starting_point;
658 :
659 189 : for (auto &child : starting_point.children)
660 : {
661 103 : auto candidate = dfs_node (child.second, to_find);
662 :
663 103 : if (candidate.has_value ())
664 29 : return candidate;
665 : }
666 :
667 86 : return tl::nullopt;
668 : }
669 :
670 : template <Namespace N>
671 : tl::optional<typename ForeverStack<N>::Node &>
672 37138171 : ForeverStack<N>::check_cache (NodeId to_find)
673 : {
674 37138171 : auto entry = dfs_cache.find (to_find);
675 :
676 37138171 : if (entry != dfs_cache.end ())
677 627748 : return entry->second;
678 :
679 36510423 : return tl::nullopt;
680 : }
681 :
682 : template <Namespace N>
683 : void
684 2934 : ForeverStack<N>::cache (NodeId found, typename ForeverStack<N>::Node &result)
685 : {
686 2934 : dfs_cache.insert ({found, result});
687 : }
688 :
689 : template <Namespace N>
690 : tl::optional<Rib &>
691 52 : ForeverStack<N>::to_rib (NodeId rib_id)
692 : {
693 52 : return dfs_rib (root, rib_id);
694 : }
695 :
696 : template <Namespace N>
697 : tl::optional<const Rib &>
698 : ForeverStack<N>::to_rib (NodeId rib_id) const
699 : {
700 : return dfs_rib (root, rib_id);
701 : }
702 :
703 : template <Namespace N>
704 : void
705 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
706 : const std::string &next,
707 : const std::string &next_next) const
708 : {
709 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
710 0 : stream << next << "rib [" << rib_kind << "]: {";
711 0 : if (rib.get_values ().empty ())
712 : {
713 0 : stream << "}\n";
714 0 : return;
715 : }
716 : else
717 : {
718 0 : stream << "\n";
719 : }
720 :
721 0 : for (const auto &kv : rib.get_values ())
722 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
723 :
724 0 : stream << next << "},\n";
725 0 : }
726 :
727 : template <Namespace N>
728 : void
729 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
730 : const ForeverStack<N>::Node &node,
731 : unsigned depth) const
732 : {
733 0 : auto indent = std::string (indentation, ' ');
734 0 : auto next = std::string (indentation + 4, ' ');
735 0 : auto next_next = std::string (indentation + 8, ' ');
736 :
737 0 : std::string cursor_text = "";
738 0 : if (node.id == cursor ().id)
739 0 : cursor_text = "(C)";
740 :
741 : stream << indent << "Node " << cursor_text << "{\n"
742 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
743 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
744 0 : << ",\n";
745 :
746 0 : stream_rib (stream, node.rib (N), next, next_next);
747 :
748 0 : stream << indent << "}\n";
749 :
750 0 : for (auto &kv : node.children)
751 : {
752 0 : auto link = kv.first;
753 0 : auto child = kv.second;
754 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
755 0 : << (link.path.has_value () ? link.path.value ().as_string ()
756 0 : : "<anon>")
757 0 : << "):\n";
758 :
759 0 : stream_node (stream, indentation + 4, child, depth + 1);
760 :
761 0 : stream << '\n';
762 : }
763 0 : }
764 :
765 : template <Namespace N>
766 : std::string
767 0 : ForeverStack<N>::as_debug_string () const
768 : {
769 0 : std::stringstream stream;
770 :
771 0 : stream_node (stream, 0, root);
772 0 : stream << "Extern prelude \n";
773 0 : stream_node (stream, 0, extern_prelude);
774 0 : stream << "Lang prelude \n";
775 0 : stream_node (stream, 0, lang_prelude);
776 :
777 0 : return stream.str ();
778 0 : }
779 :
780 : template <Namespace N>
781 : bool
782 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
783 : {
784 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
785 : }
786 :
787 : static tl::expected<Definition, LookupFinalizeError>
788 515453 : find_leaf_definition_inner (const Usage &key,
789 : const std::map<Usage, Definition> &resolved_nodes,
790 : std::set<Usage> &keys_seen)
791 : {
792 515453 : auto original_definition = resolved_nodes.find (key);
793 515453 : auto possible_import = Usage (original_definition->second.id);
794 :
795 515453 : if (original_definition == resolved_nodes.end ())
796 515453 : return tl::make_unexpected (LookupFinalizeError::NoDefinition);
797 :
798 0 : if (!keys_seen.insert (key).second)
799 0 : return tl::make_unexpected (LookupFinalizeError::Loop);
800 :
801 0 : if (resolved_nodes.find (possible_import) == resolved_nodes.end ())
802 0 : return original_definition->second;
803 :
804 : // We're dealing with an import - a reference to another
805 : // definition. Go through the chain and update the original key's
806 : // corresponding definition.
807 0 : return find_leaf_definition_inner (possible_import, resolved_nodes,
808 0 : keys_seen);
809 : }
810 :
811 : template <Namespace N>
812 : tl::expected<Definition, LookupFinalizeError>
813 515453 : ForeverStack<N>::find_leaf_definition (const NodeId &key) const
814 : {
815 515453 : std::set<Usage> keys_seen;
816 :
817 515453 : return find_leaf_definition_inner (Usage (key), resolved_nodes, keys_seen);
818 515453 : }
819 :
820 : #if 0
821 : template <Namespace N>
822 : void
823 : ForeverStack<N>::flatten ()
824 : {
825 : for (auto &k_v : resolved_nodes)
826 : {
827 : // Loop detection
828 : auto keys_seen = std::set<Usage> ();
829 :
830 : auto result
831 : = find_leaf_definition_inner (k_v.first, resolved_nodes, keys_seen);
832 :
833 : if (!result)
834 : {
835 : // Trigger an ICE if we haven't found a definition because that's
836 : // really weird
837 : rust_assert (result.error () != LookupFinalizeError::NoDefinition);
838 :
839 : // FIXME: This needs to be improved and tested, but later
840 : rust_error_at (UNDEF_LOCATION, "import loop");
841 : continue;
842 : }
843 :
844 : // Replace the Definition for this Usage in the map. This may be a no-op.
845 : k_v.second = result.value ();
846 : }
847 : }
848 : #endif
849 :
850 : // FIXME: Can we add selftests?
851 :
852 : } // namespace Resolver2_0
853 : } // namespace Rust
|