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 2028573 : ForeverStack<N>::Node::is_root () const
34 : {
35 429409 : 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 18736 : ForeverStack<N>::Node::is_leaf () const
48 : {
49 18736 : 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 1596597 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : tl::optional<Identifier> path)
66 : {
67 2171643 : push_inner (rib_kind, Link (id, path));
68 1596597 : }
69 :
70 : template <Namespace N>
71 : void
72 1596597 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : {
74 1596597 : 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 14052 : rust_assert (&cursor_reference.get () == &root);
79 : // Prelude doesn't have an access path
80 14052 : rust_assert (!link.path);
81 14052 : update_cursor (this->lang_prelude);
82 14052 : 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 3165090 : auto emplace = cursor ().children.emplace (
90 1582545 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 :
92 1582545 : auto it = emplace.first;
93 1582545 : auto existed = !emplace.second;
94 :
95 1819641 : 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 1582545 : update_cursor (it->second);
102 : }
103 :
104 : template <Namespace N>
105 : void
106 1596591 : ForeverStack<N>::pop ()
107 : {
108 1596591 : rust_assert (!cursor ().is_root ());
109 :
110 1596591 : rust_debug ("popping link");
111 :
112 1928898 : for (const auto &kv : cursor ().rib.get_values ())
113 332307 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : kv.second.to_string ().c_str ());
115 :
116 1596591 : if (cursor ().parent.has_value ())
117 3033829 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 1437238 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : kv.second.to_string ().c_str ());
120 :
121 1596591 : update_cursor (cursor ().parent.value ());
122 1596591 : }
123 :
124 : static tl::expected<NodeId, DuplicateNameError>
125 274979 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : {
127 549958 : return rib.insert (name, definition);
128 : }
129 :
130 : template <Namespace N>
131 : tl::expected<NodeId, DuplicateNameError>
132 244521 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : {
134 244521 : 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 244521 : return insert_inner (innermost_rib, name.as_string (),
141 489042 : Rib::Definition::NonShadowable (node));
142 : }
143 :
144 : template <Namespace N>
145 : tl::expected<NodeId, DuplicateNameError>
146 24384 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : {
148 24384 : auto &innermost_rib = peek ();
149 :
150 24384 : return insert_inner (innermost_rib, name.as_string (),
151 48768 : Rib::Definition::Shadowable (node));
152 : }
153 :
154 : template <Namespace N>
155 : tl::expected<NodeId, DuplicateNameError>
156 63 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : {
158 63 : auto &innermost_rib = peek ();
159 :
160 63 : return insert_inner (innermost_rib, name.as_string (),
161 126 : Rib::Definition::Globbed (node));
162 : }
163 :
164 : template <Namespace N>
165 : tl::expected<NodeId, DuplicateNameError>
166 13 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : {
168 13 : auto &root_rib = root.rib;
169 :
170 : // inserting in the root of the crate is never a shadowing operation, even for
171 : // macros
172 13 : return insert_inner (root_rib, name.as_string (),
173 26 : Rib::Definition::NonShadowable (node));
174 : }
175 :
176 : // Specialization for Macros and Labels - where we are allowed to shadow
177 : // existing definitions
178 : template <>
179 : inline tl::expected<NodeId, DuplicateNameError>
180 167 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : {
182 167 : return insert_inner (peek (), name.as_string (),
183 334 : Rib::Definition::Shadowable (node));
184 : }
185 :
186 : template <>
187 : inline tl::expected<NodeId, DuplicateNameError>
188 63 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
189 : {
190 63 : return insert_inner (peek (), name.as_string (),
191 126 : Rib::Definition::Shadowable (node));
192 : }
193 :
194 : template <>
195 : inline tl::expected<NodeId, DuplicateNameError>
196 4324 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : {
198 4324 : return insert_inner (peek (), name.as_string (),
199 8648 : Rib::Definition::NonShadowable (node, true));
200 : }
201 :
202 : template <>
203 : inline tl::expected<NodeId, DuplicateNameError>
204 1186 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
205 : {
206 1186 : return insert_inner (peek (), name.as_string (),
207 2372 : Rib::Definition::NonShadowable (node, true));
208 : }
209 :
210 : template <Namespace N>
211 : inline void
212 258 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
213 : {
214 774 : insert_inner (lang_prelude.rib, name.as_string (),
215 516 : Rib::Definition::NonShadowable (id, false));
216 258 : }
217 :
218 : template <Namespace N>
219 : Rib &
220 331089 : ForeverStack<N>::peek ()
221 : {
222 331089 : 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 26 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
235 : {
236 52 : 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 160622 : ForeverStack<N>::reverse_iter (Node &start,
250 : std::function<KeepGoing (Node &)> lambda)
251 : {
252 160622 : auto *tmp = &start;
253 :
254 295423 : while (true)
255 : {
256 456045 : auto keep_going = lambda (*tmp);
257 456045 : if (keep_going == KeepGoing::No)
258 : return;
259 :
260 368499 : if (tmp->is_root ())
261 : return;
262 :
263 295423 : 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 8477780 : ForeverStack<N>::cursor ()
290 : {
291 8448377 : 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 1596597 : ForeverStack<N>::update_cursor (Node &new_cursor)
304 : {
305 1596597 : cursor_reference = new_cursor;
306 : }
307 :
308 : template <Namespace N>
309 : tl::optional<Rib::Definition>
310 155282 : ForeverStack<N>::get (Node &start, const Identifier &name)
311 : {
312 155282 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
313 :
314 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
315 605573 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
316 : // we can't reference associated types/functions like this
317 450291 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
318 : return KeepGoing::Yes;
319 :
320 407891 : auto candidate = current.rib.get (name.as_string ());
321 :
322 407891 : if (candidate)
323 : {
324 71256 : 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 71251 : resolved_definition = *candidate;
331 :
332 71251 : return KeepGoing::No;
333 : }
334 : else
335 : {
336 336635 : if (current.rib.kind == Rib::Kind::Module)
337 : return KeepGoing::No;
338 : else
339 : return KeepGoing::Yes;
340 : }
341 407891 : });
342 :
343 155282 : return resolved_definition;
344 : }
345 :
346 : template <Namespace N>
347 : tl::optional<Rib::Definition>
348 83702 : ForeverStack<N>::get (const Identifier &name)
349 : {
350 83702 : 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 34194 : ForeverStack<N>::get_lang_prelude (const std::string &name)
363 : {
364 34194 : 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 26 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
380 : const Identifier &name)
381 : {
382 26 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
383 :
384 26 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
385 : // looking up for labels cannot go through function ribs
386 : // TODO: What other ribs?
387 26 : if (current.rib.kind == Rib::Kind::Function)
388 : return KeepGoing::No;
389 :
390 26 : auto candidate = current.rib.get (name.as_string ());
391 :
392 : // FIXME: Factor this in a function with the generic `get`
393 26 : return candidate.map_or (
394 73 : [&resolved_definition] (Rib::Definition found) {
395 21 : resolved_definition = found;
396 :
397 21 : return KeepGoing::No;
398 : },
399 26 : KeepGoing::Yes);
400 26 : });
401 :
402 26 : 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 71036 : is_last (const I &iterator, const C &collection)
409 : {
410 71036 : 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 112046 : is_start (const I &iterator, const C &collection)
417 : {
418 135444 : return iterator == collection.begin ();
419 : }
420 :
421 : template <Namespace N>
422 : typename ForeverStack<N>::Node &
423 5314 : ForeverStack<N>::find_closest_module (Node &starting_point)
424 : {
425 5314 : auto *closest_module = &starting_point;
426 :
427 11042 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
428 5728 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
429 : {
430 5314 : closest_module = ¤t;
431 5314 : return KeepGoing::No;
432 : }
433 :
434 : return KeepGoing::Yes;
435 : });
436 :
437 5314 : 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 51819 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
444 : const ResolutionPath::Segment &segment,
445 : bool condition)
446 : {
447 51819 : 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 51819 : 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 22081 : ForeverStack<N>::find_starting_point (
463 : const std::vector<ResolutionPath::Segment> &segments,
464 : std::reference_wrapper<Node> &starting_point,
465 : std::function<void (Usage, Definition)> insert_segment_resolution,
466 : std::vector<Error> &collect_errors)
467 : {
468 22081 : auto iterator = segments.begin ();
469 :
470 24652 : for (; !is_last (iterator, segments); iterator++)
471 : {
472 23398 : auto &seg = *iterator;
473 :
474 23398 : bool is_self_or_crate
475 23398 : = 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 23398 : if (check_leading_kw_at_start (collect_errors, seg,
480 23398 : !is_start (iterator, segments)
481 23398 : && is_self_or_crate))
482 1 : return tl::nullopt;
483 :
484 23397 : if (seg.is_crate_path_seg ())
485 : {
486 818 : starting_point = root;
487 818 : insert_segment_resolution (Usage (seg.node_id),
488 818 : Definition (starting_point.get ().id));
489 818 : iterator++;
490 : break;
491 : }
492 22579 : if (seg.is_lower_self_seg ())
493 : {
494 : // insert segment resolution and exit
495 25 : starting_point = find_closest_module (starting_point);
496 25 : insert_segment_resolution (Usage (seg.node_id),
497 25 : Definition (starting_point.get ().id));
498 25 : iterator++;
499 : break;
500 : }
501 22554 : if (seg.is_super_path_seg ())
502 : {
503 2572 : starting_point = find_closest_module (starting_point);
504 2572 : if (starting_point.get ().is_root ())
505 : {
506 1 : collect_errors.emplace_back (
507 1 : seg.locus, ErrorCode::E0433,
508 : "too many leading %<super%> keywords");
509 1 : return tl::nullopt;
510 : }
511 :
512 2571 : starting_point
513 2571 : = find_closest_module (starting_point.get ().parent.value ());
514 :
515 2571 : insert_segment_resolution (Usage (seg.node_id),
516 2571 : Definition (starting_point.get ().id));
517 : continue;
518 : }
519 :
520 : // now we've gone through the allowed `crate`, `self` or leading `super`
521 : // segments. we can start resolving each segment itself.
522 : // if we do see another leading segment, then we can error out.
523 : break;
524 : }
525 :
526 22079 : return iterator;
527 : }
528 :
529 : template <Namespace N>
530 : tl::optional<typename ForeverStack<N>::Node &>
531 22079 : ForeverStack<N>::resolve_segments (
532 : Node &starting_point, const std::vector<ResolutionPath::Segment> &segments,
533 : typename std::vector<ResolutionPath::Segment>::const_iterator iterator,
534 : std::function<void (Usage, Definition)> insert_segment_resolution,
535 : std::vector<Error> &collect_errors)
536 : {
537 22079 : Node *current_node = &starting_point;
538 50500 : for (; !is_last (iterator, segments); iterator++)
539 : {
540 28421 : auto &seg = *iterator;
541 :
542 56842 : std::string str = seg.name;
543 28421 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
544 :
545 : // check that we don't encounter *any* leading keywords afterwards
546 28421 : if (check_leading_kw_at_start (collect_errors, seg,
547 28421 : seg.is_crate_path_seg ()
548 28421 : || seg.is_super_path_seg ()
549 56835 : || seg.is_lower_self_seg ()))
550 10 : return tl::nullopt;
551 :
552 28411 : tl::optional<std::reference_wrapper<Node>> child = tl::nullopt;
553 :
554 : /*
555 : * On every iteration this loop either
556 : *
557 : * 1. terminates
558 : *
559 : * 2. decreases the depth of the node pointed to by current_node until
560 : * current_node reaches the root
561 : *
562 : * 3. If the root node is reached, and we were not able to resolve the
563 : * segment, we search the prelude rib for the segment, by setting
564 : * current_node to point to the prelude, and toggling the
565 : * searched_prelude boolean to true. If current_node is the prelude
566 : * rib, and searched_prelude is true, we will exit.
567 : *
568 : * This ensures termination.
569 : *
570 : */
571 28411 : bool searched_prelude = false;
572 44037 : while (true)
573 : {
574 82080 : if (is_start (iterator, segments)
575 74074 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
576 : {
577 : // we can't reference associated types/functions like this
578 8006 : current_node = ¤t_node->parent.value ();
579 10380 : continue;
580 : }
581 :
582 : // may set the value of child
583 262722 : for (auto &kv : current_node->children)
584 : {
585 218685 : auto &link = kv.first;
586 :
587 437370 : if (link.path.map_or (
588 539487 : [&str] (Identifier path) {
589 102117 : auto &path_str = path.as_string ();
590 102117 : return str == path_str;
591 : },
592 218685 : false))
593 : {
594 88099 : child = kv.second;
595 : break;
596 : }
597 : }
598 :
599 66068 : if (child.has_value ())
600 : {
601 : break;
602 : }
603 :
604 44037 : auto rib_lookup = current_node->rib.get (seg.name);
605 44037 : if (rib_lookup && !rib_lookup->is_ambiguous ())
606 : {
607 3691 : if (Analysis::Mappings::get ()
608 3691 : .lookup_glob_container (rib_lookup->get_node_id ())
609 3691 : .has_value ())
610 : {
611 2274 : child = dfs_node (root, rib_lookup->get_node_id ()).value ();
612 : break;
613 : }
614 : else
615 : {
616 1417 : insert_segment_resolution (Usage (seg.node_id),
617 1417 : Definition (
618 : rib_lookup->get_node_id ()));
619 1417 : return tl::nullopt;
620 : }
621 : }
622 :
623 40346 : if (current_node->is_root () && !searched_prelude)
624 : {
625 2374 : searched_prelude = true;
626 2374 : current_node = &lang_prelude;
627 : continue;
628 : }
629 :
630 37972 : if (!is_start (iterator, segments)
631 37967 : || current_node->rib.kind == Rib::Kind::Module
632 75626 : || current_node->is_prelude ())
633 : {
634 2689 : return tl::nullopt;
635 : }
636 :
637 35283 : current_node = ¤t_node->parent.value ();
638 : }
639 :
640 : // if child didn't point to a value
641 : // the while loop above would have returned or kept looping
642 24305 : current_node = &child->get ();
643 24305 : insert_segment_resolution (Usage (seg.node_id),
644 24305 : Definition (current_node->id));
645 : }
646 :
647 17963 : return *current_node;
648 : }
649 :
650 : template <>
651 : inline tl::optional<Rib::Definition>
652 6973 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
653 : std::string &seg_name,
654 : bool is_lower_self)
655 : {
656 6973 : if (is_lower_self)
657 204 : return Rib::Definition::NonShadowable (final_node.id);
658 : else
659 6769 : return final_node.rib.get (seg_name);
660 : }
661 :
662 : template <Namespace N>
663 : tl::optional<Rib::Definition>
664 10990 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
665 : bool is_lower_self)
666 : {
667 10990 : return final_node.rib.get (seg_name);
668 : }
669 :
670 : template <Namespace N>
671 : tl::optional<Rib::Definition>
672 0 : ForeverStack<N>::resolve_path (
673 : const ResolutionPath &path, ResolutionMode mode,
674 : std::function<void (Usage, Definition)> insert_segment_resolution,
675 : std::vector<Error> &collect_errors, NodeId starting_point_id)
676 : {
677 0 : auto starting_point = dfs_node (root, starting_point_id);
678 :
679 : // We may have a prelude, but haven't visited it yet and thus it's not in our
680 : // nodes
681 0 : if (!starting_point)
682 0 : return tl::nullopt;
683 :
684 0 : return resolve_path (path, mode, insert_segment_resolution, collect_errors,
685 0 : *starting_point);
686 : }
687 :
688 : template <Namespace N>
689 : tl::optional<Rib::Definition>
690 94054 : ForeverStack<N>::resolve_path (
691 : const ResolutionPath &path, ResolutionMode mode,
692 : std::function<void (Usage, Definition)> insert_segment_resolution,
693 : std::vector<Error> &collect_errors)
694 : {
695 94054 : std::reference_wrapper<Node> starting_point = cursor ();
696 :
697 94054 : return resolve_path (path, mode, insert_segment_resolution, collect_errors,
698 94054 : starting_point);
699 : }
700 :
701 : template <Namespace N>
702 : tl::optional<Rib::Definition>
703 94054 : ForeverStack<N>::resolve_path (
704 : const ResolutionPath &path, ResolutionMode mode,
705 : std::function<void (Usage, Definition)> insert_segment_resolution,
706 : std::vector<Error> &collect_errors,
707 : std::reference_wrapper<Node> starting_point)
708 : {
709 94054 : bool can_descend = true;
710 :
711 94054 : rust_debug ("resolving %s", path.as_string ().c_str ());
712 :
713 94054 : if (auto lang_item = path.get_lang_prefix ())
714 : {
715 : NodeId seg_id
716 392 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
717 :
718 392 : insert_segment_resolution (Usage (lang_item->second),
719 392 : Definition (seg_id));
720 :
721 392 : if (path.get_segments ().empty ())
722 392 : return Rib::Definition::NonShadowable (seg_id);
723 :
724 0 : auto new_start = dfs_node (root, seg_id);
725 0 : rust_assert (new_start.has_value ());
726 0 : starting_point = new_start.value ();
727 :
728 0 : can_descend = false;
729 : }
730 : else
731 : {
732 93662 : switch (mode)
733 : {
734 : case ResolutionMode::Normal:
735 : break; // default
736 951 : case ResolutionMode::FromRoot:
737 951 : starting_point = root;
738 951 : break;
739 0 : case ResolutionMode::FromExtern:
740 0 : starting_point = extern_prelude;
741 0 : break;
742 0 : default:
743 0 : rust_unreachable ();
744 : }
745 : }
746 :
747 93662 : if (path.get_segments ().empty ())
748 : {
749 1 : return Rib::Definition::NonShadowable (starting_point.get ().id);
750 : }
751 :
752 93661 : auto &segments = path.get_segments ();
753 :
754 : // if there's only one segment, we just use `get`
755 187322 : if (can_descend && segments.size () == 1)
756 : {
757 71580 : auto &seg = segments.front ();
758 :
759 214740 : tl::optional<Rib::Definition> res = get (starting_point.get (), seg.name);
760 :
761 71580 : if (!res)
762 52284 : res = get_lang_prelude (seg.name);
763 :
764 54508 : if (N == Namespace::Types && !res)
765 : {
766 198 : if (seg.is_crate_path_seg ())
767 : {
768 53 : insert_segment_resolution (Usage (seg.node_id),
769 53 : Definition (root.id));
770 : // TODO: does NonShadowable matter?
771 53 : return Rib::Definition::NonShadowable (root.id);
772 : }
773 145 : else if (seg.is_lower_self_seg ())
774 : {
775 5 : NodeId id = find_closest_module (starting_point.get ()).id;
776 5 : insert_segment_resolution (Usage (seg.node_id), Definition (id));
777 : // TODO: does NonShadowable matter?
778 5 : return Rib::Definition::NonShadowable (id);
779 : }
780 140 : else if (seg.is_super_path_seg ())
781 : {
782 : Node &closest_module
783 1 : = find_closest_module (starting_point.get ());
784 1 : if (closest_module.is_root ())
785 : {
786 0 : rust_error_at (seg.locus, ErrorCode::E0433,
787 : "too many leading %<super%> keywords");
788 0 : return tl::nullopt;
789 : }
790 :
791 1 : NodeId id
792 1 : = find_closest_module (closest_module.parent.value ()).id;
793 1 : insert_segment_resolution (Usage (seg.node_id), Definition (id));
794 : // TODO: does NonShadowable matter?
795 1 : return Rib::Definition::NonShadowable (id);
796 : }
797 : else
798 : {
799 : // HACK: check for a module after we check the language prelude
800 624 : for (auto &kv :
801 139 : find_closest_module (starting_point.get ()).children)
802 : {
803 494 : auto &link = kv.first;
804 :
805 988 : if (link.path.map_or (
806 1412 : [&seg] (Identifier path) {
807 424 : auto &path_str = path.as_string ();
808 424 : return path_str == seg.name;
809 : },
810 494 : false))
811 : {
812 9 : insert_segment_resolution (Usage (seg.node_id),
813 9 : Definition (kv.second.id));
814 9 : return Rib::Definition::NonShadowable (kv.second.id);
815 : }
816 : }
817 : }
818 : }
819 :
820 71512 : if (res && !res->is_ambiguous ())
821 70921 : insert_segment_resolution (Usage (seg.node_id),
822 70921 : Definition (res->get_node_id ()));
823 71512 : return res;
824 71580 : }
825 :
826 22081 : auto iterator = segments.begin ();
827 22081 : if (can_descend)
828 : {
829 22081 : if (auto res
830 22081 : = find_starting_point (segments, starting_point,
831 : insert_segment_resolution, collect_errors))
832 22079 : iterator = *res;
833 : else
834 2 : return tl::nullopt;
835 : }
836 :
837 44158 : return resolve_segments (starting_point.get (), segments, iterator,
838 : insert_segment_resolution, collect_errors)
839 40042 : .and_then ([this, &segments, &insert_segment_resolution] (
840 : Node &final_node) -> tl::optional<Rib::Definition> {
841 : // leave resolution within impl blocks to type checker
842 17963 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
843 0 : return tl::nullopt;
844 :
845 17963 : auto &seg = segments.back ();
846 17963 : std::string seg_name = seg.name;
847 :
848 17963 : tl::optional<Rib::Definition> res
849 : = resolve_final_segment (final_node, seg_name,
850 17963 : seg.is_lower_self_seg ());
851 : // Ok we didn't find it in the rib, Lets try the prelude...
852 17963 : if (!res)
853 7723 : res = get_lang_prelude (seg_name);
854 :
855 6973 : if (N == Namespace::Types && !res)
856 : {
857 : // HACK: check for a module after we check the language prelude
858 2340 : for (auto &kv : final_node.children)
859 : {
860 1339 : auto &link = kv.first;
861 :
862 2678 : if (link.path.map_or (
863 95 : [&seg_name] (Identifier path) {
864 95 : auto &path_str = path.as_string ();
865 95 : return path_str == seg_name;
866 : },
867 1339 : false))
868 : {
869 120 : insert_segment_resolution (Usage (seg.node_id),
870 60 : Definition (kv.second.id));
871 60 : return Rib::Definition::NonShadowable (kv.second.id);
872 : }
873 : }
874 : }
875 :
876 17903 : if (res && !res->is_ambiguous ())
877 10238 : insert_segment_resolution (Usage (seg.node_id),
878 10238 : Definition (res->get_node_id ()));
879 :
880 17903 : return res;
881 40042 : });
882 : }
883 :
884 : template <Namespace N>
885 : tl::optional<typename ForeverStack<N>::DfsResult>
886 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
887 : {
888 : auto values = starting_point.rib.get_values ();
889 :
890 : for (auto &kv : values)
891 : {
892 : for (auto id : kv.second.ids_shadowable)
893 : if (id == to_find)
894 : return {{starting_point, kv.first}};
895 : for (auto id : kv.second.ids_non_shadowable)
896 : if (id == to_find)
897 : return {{starting_point, kv.first}};
898 : for (auto id : kv.second.ids_globbed)
899 : if (id == to_find)
900 : return {{starting_point, kv.first}};
901 : }
902 :
903 : for (auto &child : starting_point.children)
904 : {
905 : auto candidate = dfs (child.second, to_find);
906 :
907 : if (candidate.has_value ())
908 : return candidate;
909 : }
910 :
911 : return tl::nullopt;
912 : }
913 :
914 : template <Namespace N>
915 : tl::optional<typename ForeverStack<N>::ConstDfsResult>
916 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
917 : NodeId to_find) const
918 : {
919 : auto values = starting_point.rib.get_values ();
920 :
921 : for (auto &kv : values)
922 : {
923 : for (auto id : kv.second.ids_shadowable)
924 : if (id == to_find)
925 : return {{starting_point, kv.first}};
926 : for (auto id : kv.second.ids_non_shadowable)
927 : if (id == to_find)
928 : return {{starting_point, kv.first}};
929 : for (auto id : kv.second.ids_globbed)
930 : if (id == to_find)
931 : return {{starting_point, kv.first}};
932 : }
933 :
934 : for (auto &child : starting_point.children)
935 : {
936 : auto candidate = dfs (child.second, to_find);
937 :
938 : if (candidate.has_value ())
939 : return candidate;
940 : }
941 :
942 : return tl::nullopt;
943 : }
944 :
945 : template <Namespace N>
946 : tl::optional<Rib &>
947 1297 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
948 : {
949 1297 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
950 1 : return x.rib;
951 1297 : });
952 : }
953 :
954 : template <Namespace N>
955 : tl::optional<const Rib &>
956 52 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
957 : NodeId to_find) const
958 : {
959 52 : return dfs_node (starting_point, to_find)
960 52 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
961 : }
962 :
963 : template <Namespace N>
964 : tl::optional<typename ForeverStack<N>::Node &>
965 23313 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
966 : NodeId to_find)
967 : {
968 23313 : if (starting_point.id == to_find)
969 2275 : return starting_point;
970 :
971 34456 : for (auto &child : starting_point.children)
972 : {
973 19742 : auto candidate = dfs_node (child.second, to_find);
974 :
975 19742 : if (candidate.has_value ())
976 6324 : return candidate;
977 : }
978 :
979 14714 : return tl::nullopt;
980 : }
981 :
982 : template <Namespace N>
983 : tl::optional<const typename ForeverStack<N>::Node &>
984 939 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
985 : NodeId to_find) const
986 : {
987 939 : if (starting_point.id == to_find)
988 68 : return starting_point;
989 :
990 1493 : for (auto &child : starting_point.children)
991 : {
992 859 : auto candidate = dfs_node (child.second, to_find);
993 :
994 859 : if (candidate.has_value ())
995 237 : return candidate;
996 : }
997 :
998 634 : return tl::nullopt;
999 : }
1000 :
1001 : template <Namespace N>
1002 : tl::optional<Rib &>
1003 : ForeverStack<N>::to_rib (NodeId rib_id)
1004 : {
1005 : return dfs_rib (root, rib_id);
1006 : }
1007 :
1008 : template <Namespace N>
1009 : tl::optional<const Rib &>
1010 52 : ForeverStack<N>::to_rib (NodeId rib_id) const
1011 : {
1012 52 : return dfs_rib (root, rib_id);
1013 : }
1014 :
1015 : template <Namespace N>
1016 : void
1017 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
1018 : const std::string &next,
1019 : const std::string &next_next) const
1020 : {
1021 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
1022 0 : stream << next << "rib [" << rib_kind << "]: {";
1023 0 : if (rib.get_values ().empty ())
1024 : {
1025 0 : stream << "}\n";
1026 0 : return;
1027 : }
1028 : else
1029 : {
1030 0 : stream << "\n";
1031 : }
1032 :
1033 0 : for (const auto &kv : rib.get_values ())
1034 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
1035 :
1036 0 : stream << next << "},\n";
1037 0 : }
1038 :
1039 : template <Namespace N>
1040 : void
1041 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
1042 : const ForeverStack<N>::Node &node,
1043 : unsigned depth) const
1044 : {
1045 0 : auto indent = std::string (indentation, ' ');
1046 0 : auto next = std::string (indentation + 4, ' ');
1047 0 : auto next_next = std::string (indentation + 8, ' ');
1048 :
1049 : stream << indent << "Node {\n"
1050 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
1051 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
1052 0 : << ",\n";
1053 :
1054 0 : stream_rib (stream, node.rib, next, next_next);
1055 :
1056 0 : stream << indent << "}\n";
1057 :
1058 0 : for (auto &kv : node.children)
1059 : {
1060 0 : auto link = kv.first;
1061 0 : auto child = kv.second;
1062 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
1063 0 : << (link.path.has_value () ? link.path.value ().as_string ()
1064 0 : : "<anon>")
1065 0 : << "):\n";
1066 :
1067 0 : stream_node (stream, indentation + 4, child, depth + 1);
1068 :
1069 0 : stream << '\n';
1070 : }
1071 0 : }
1072 :
1073 : template <Namespace N>
1074 : std::string
1075 0 : ForeverStack<N>::as_debug_string () const
1076 : {
1077 0 : std::stringstream stream;
1078 :
1079 0 : stream_node (stream, 0, root);
1080 :
1081 0 : return stream.str ();
1082 0 : }
1083 :
1084 : template <Namespace N>
1085 : bool
1086 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
1087 : {
1088 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
1089 : }
1090 :
1091 : // FIXME: Can we add selftests?
1092 :
1093 : } // namespace Resolver2_0
1094 : } // namespace Rust
|
