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 1750851 : ForeverStack<N>::Node::is_root () const
34 : {
35 239851 : 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 18040 : ForeverStack<N>::Node::is_leaf () const
48 : {
49 18040 : 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 1508433 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : tl::optional<Identifier> path)
66 : {
67 2071530 : push_inner (rib_kind, Link (id, path));
68 1508433 : }
69 :
70 : template <Namespace N>
71 : void
72 1508433 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : {
74 1508433 : 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 13530 : rust_assert (&cursor_reference.get () == &root);
79 : // Prelude doesn't have an access path
80 13530 : rust_assert (!link.path);
81 13530 : update_cursor (this->lang_prelude);
82 13530 : 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 2989806 : auto emplace = cursor ().children.emplace (
90 1494903 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 :
92 1494903 : auto it = emplace.first;
93 1494903 : auto existed = !emplace.second;
94 :
95 1718043 : 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 1494903 : update_cursor (it->second);
102 : }
103 :
104 : template <Namespace N>
105 : void
106 1508427 : ForeverStack<N>::pop ()
107 : {
108 1508427 : rust_assert (!cursor ().is_root ());
109 :
110 1508427 : rust_debug ("popping link");
111 :
112 1827228 : for (const auto &kv : cursor ().rib.get_values ())
113 318801 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : kv.second.to_string ().c_str ());
115 :
116 1508427 : if (cursor ().parent.has_value ())
117 2884044 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 1375617 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : kv.second.to_string ().c_str ());
120 :
121 1508427 : update_cursor (cursor ().parent.value ());
122 1508427 : }
123 :
124 : static tl::expected<NodeId, DuplicateNameError>
125 266959 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : {
127 533918 : return rib.insert (name, definition);
128 : }
129 :
130 : template <Namespace N>
131 : tl::expected<NodeId, DuplicateNameError>
132 238868 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : {
134 238868 : 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 238868 : return insert_inner (innermost_rib, name.as_string (),
141 477736 : Rib::Definition::NonShadowable (node));
142 : }
143 :
144 : template <Namespace N>
145 : tl::expected<NodeId, DuplicateNameError>
146 24230 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : {
148 24230 : auto &innermost_rib = peek ();
149 :
150 24230 : return insert_inner (innermost_rib, name.as_string (),
151 48460 : Rib::Definition::Shadowable (node));
152 : }
153 :
154 : template <Namespace N>
155 : tl::expected<NodeId, DuplicateNameError>
156 30 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : {
158 30 : auto &innermost_rib = peek ();
159 :
160 30 : return insert_inner (innermost_rib, name.as_string (),
161 60 : Rib::Definition::Globbed (node));
162 : }
163 :
164 : template <Namespace N>
165 : tl::expected<NodeId, DuplicateNameError>
166 11 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : {
168 11 : auto &root_rib = root.rib;
169 :
170 : // inserting in the root of the crate is never a shadowing operation, even for
171 : // macros
172 11 : return insert_inner (root_rib, name.as_string (),
173 22 : 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 3332 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : {
198 3332 : return insert_inner (peek (), name.as_string (),
199 6664 : Rib::Definition::NonShadowable (node, true));
200 : }
201 :
202 : template <Namespace N>
203 : inline void
204 258 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
205 : {
206 774 : insert_inner (lang_prelude.rib, name.as_string (),
207 516 : Rib::Definition::NonShadowable (id, false));
208 258 : }
209 :
210 : template <Namespace N>
211 : Rib &
212 322584 : ForeverStack<N>::peek ()
213 : {
214 322584 : return cursor ().rib;
215 : }
216 :
217 : template <Namespace N>
218 : const Rib &
219 : ForeverStack<N>::peek () const
220 : {
221 : return cursor ().rib;
222 : }
223 :
224 : template <Namespace N>
225 : void
226 26 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
227 : {
228 52 : return reverse_iter (cursor (), lambda);
229 : }
230 :
231 : template <Namespace N>
232 : void
233 : ForeverStack<N>::reverse_iter (
234 : std::function<KeepGoing (const Node &)> lambda) const
235 : {
236 : return reverse_iter (cursor (), lambda);
237 : }
238 :
239 : template <Namespace N>
240 : void
241 104273 : ForeverStack<N>::reverse_iter (Node &start,
242 : std::function<KeepGoing (Node &)> lambda)
243 : {
244 104273 : auto *tmp = &start;
245 :
246 152701 : while (true)
247 : {
248 256974 : auto keep_going = lambda (*tmp);
249 256974 : if (keep_going == KeepGoing::No)
250 : return;
251 :
252 178924 : if (tmp->is_root ())
253 : return;
254 :
255 152701 : tmp = &tmp->parent.value ();
256 : }
257 : }
258 :
259 : template <Namespace N>
260 : void
261 : ForeverStack<N>::reverse_iter (
262 : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
263 : {
264 : auto *tmp = &start;
265 :
266 : while (true)
267 : {
268 : auto keep_going = lambda (*tmp);
269 : if (keep_going == KeepGoing::No)
270 : return;
271 :
272 : if (tmp->is_root ())
273 : return;
274 :
275 : tmp = &tmp->parent.value ();
276 : }
277 : }
278 :
279 : template <Namespace N>
280 : typename ForeverStack<N>::Node &
281 7974250 : ForeverStack<N>::cursor ()
282 : {
283 7860815 : return cursor_reference;
284 : }
285 :
286 : template <Namespace N>
287 : const typename ForeverStack<N>::Node &
288 : ForeverStack<N>::cursor () const
289 : {
290 : return cursor_reference;
291 : }
292 :
293 : template <Namespace N>
294 : void
295 1508433 : ForeverStack<N>::update_cursor (Node &new_cursor)
296 : {
297 1508433 : cursor_reference = new_cursor;
298 : }
299 :
300 : template <Namespace N>
301 : tl::optional<Rib::Definition>
302 98936 : ForeverStack<N>::get (Node &start, const Identifier &name)
303 : {
304 98936 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
305 :
306 : // TODO: Can we improve the API? have `reverse_iter` return an optional?
307 350262 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
308 : // we can't reference associated types/functions like this
309 251326 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
310 : return KeepGoing::Yes;
311 :
312 230108 : auto candidate = current.rib.get (name.as_string ());
313 :
314 230108 : if (candidate)
315 : {
316 69384 : if (candidate->is_variant ())
317 : return KeepGoing::Yes;
318 : // for most namespaces, we do not need to care about various ribs -
319 : // they are available from all contexts if defined in the current
320 : // scope, or an outermore one. so if we do have a candidate, we can
321 : // return it directly and stop iterating
322 69381 : resolved_definition = *candidate;
323 :
324 69381 : return KeepGoing::No;
325 : }
326 : else
327 : {
328 160724 : if (current.rib.kind == Rib::Kind::Module)
329 : return KeepGoing::No;
330 : else
331 : return KeepGoing::Yes;
332 : }
333 230108 : });
334 :
335 98936 : return resolved_definition;
336 : }
337 :
338 : template <Namespace N>
339 : tl::optional<Rib::Definition>
340 29331 : ForeverStack<N>::get (const Identifier &name)
341 : {
342 29331 : return get (cursor (), name);
343 : }
344 :
345 : template <Namespace N>
346 : tl::optional<Rib::Definition>
347 8 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
348 : {
349 8 : return lang_prelude.rib.get (name.as_string ());
350 : }
351 :
352 : template <Namespace N>
353 : tl::optional<Rib::Definition>
354 35974 : ForeverStack<N>::get_lang_prelude (const std::string &name)
355 : {
356 35974 : return lang_prelude.rib.get (name);
357 : }
358 :
359 : template <Namespace N>
360 : tl::optional<Rib::Definition>
361 0 : ForeverStack<N>::get_from_prelude (NodeId prelude, const Identifier &name)
362 : {
363 0 : auto starting_point = dfs_node (root, prelude);
364 0 : if (!starting_point)
365 0 : return tl::nullopt;
366 :
367 0 : return get (*starting_point, name);
368 : }
369 :
370 : template <>
371 26 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
372 : const Identifier &name)
373 : {
374 26 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
375 :
376 26 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
377 : // looking up for labels cannot go through function ribs
378 : // TODO: What other ribs?
379 26 : if (current.rib.kind == Rib::Kind::Function)
380 : return KeepGoing::No;
381 :
382 26 : auto candidate = current.rib.get (name.as_string ());
383 :
384 : // FIXME: Factor this in a function with the generic `get`
385 26 : return candidate.map_or (
386 73 : [&resolved_definition] (Rib::Definition found) {
387 21 : resolved_definition = found;
388 :
389 21 : return KeepGoing::No;
390 : },
391 26 : KeepGoing::Yes);
392 26 : });
393 :
394 26 : return resolved_definition;
395 : }
396 :
397 : /* Check if an iterator points to the last element */
398 : template <typename I, typename C>
399 : static bool
400 76078 : is_last (const I &iterator, const C &collection)
401 : {
402 76078 : return iterator + 1 == collection.end ();
403 : }
404 :
405 : /* Check if an iterator points to the start of the collection */
406 : template <typename I, typename C>
407 : static bool
408 116168 : is_start (const I &iterator, const C &collection)
409 : {
410 141188 : return iterator == collection.begin ();
411 : }
412 :
413 : template <Namespace N>
414 : typename ForeverStack<N>::Node &
415 5311 : ForeverStack<N>::find_closest_module (Node &starting_point)
416 : {
417 5311 : auto *closest_module = &starting_point;
418 :
419 10933 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
420 5622 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
421 : {
422 5311 : closest_module = ¤t;
423 5311 : return KeepGoing::No;
424 : }
425 :
426 : return KeepGoing::Yes;
427 : });
428 :
429 5311 : return *closest_module;
430 : }
431 :
432 : /* If a the given condition is met, emit an error about misused leading path
433 : * segments */
434 : template <typename S>
435 : static inline bool
436 55238 : check_leading_kw_at_start (std::vector<Error> &collect_errors, const S &segment,
437 : bool condition)
438 : {
439 55238 : if (condition)
440 10 : collect_errors.emplace_back (
441 10 : segment.get_locus (), ErrorCode::E0433,
442 : "%qs in paths can only be used in start position",
443 20 : segment.as_string ().c_str ());
444 :
445 55238 : return condition;
446 : }
447 :
448 : // we first need to handle the "starting" segments - `super`, `self` or
449 : // `crate`. we don't need to do anything for `self` and can just skip it. for
450 : // `crate`, we need to go back to the root of the current stack. for each
451 : // `super` segment, we go back to the cursor's parent until we reach the
452 : // correct one or the root.
453 : template <Namespace N>
454 : template <typename S>
455 : tl::optional<typename std::vector<S>::const_iterator>
456 23703 : ForeverStack<N>::find_starting_point (
457 : const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point,
458 : std::function<void (const S &, NodeId)> insert_segment_resolution,
459 : std::vector<Error> &collect_errors)
460 : {
461 23703 : auto iterator = segments.begin ();
462 :
463 26274 : for (; !is_last (iterator, segments); iterator++)
464 : {
465 25020 : auto &outer_seg = *iterator;
466 :
467 25020 : if (unwrap_segment_get_lang_item (outer_seg).has_value ())
468 : break;
469 :
470 25020 : auto &seg = unwrap_type_segment (outer_seg);
471 25020 : bool is_self_or_crate
472 25020 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
473 :
474 : // if we're after the first path segment and meet `self` or `crate`, it's
475 : // an error - we should only be seeing `super` keywords at this point
476 25020 : if (check_leading_kw_at_start (collect_errors, seg,
477 25020 : !is_start (iterator, segments)
478 25020 : && is_self_or_crate))
479 1 : return tl::nullopt;
480 :
481 25019 : if (seg.is_crate_path_seg ())
482 : {
483 813 : starting_point = root;
484 813 : insert_segment_resolution (outer_seg, starting_point.get ().id);
485 813 : iterator++;
486 : break;
487 : }
488 24206 : if (seg.is_lower_self_seg ())
489 : {
490 : // insert segment resolution and exit
491 23 : starting_point = find_closest_module (starting_point);
492 23 : insert_segment_resolution (outer_seg, starting_point.get ().id);
493 23 : iterator++;
494 : break;
495 : }
496 26754 : if (seg.is_super_path_seg ())
497 : {
498 2572 : starting_point = find_closest_module (starting_point);
499 2572 : if (starting_point.get ().is_root ())
500 : {
501 1 : collect_errors.emplace_back (
502 1 : seg.get_locus (), ErrorCode::E0433,
503 : "too many leading %<super%> keywords");
504 1 : return tl::nullopt;
505 : }
506 :
507 2571 : starting_point
508 2571 : = find_closest_module (starting_point.get ().parent.value ());
509 :
510 2571 : insert_segment_resolution (outer_seg, starting_point.get ().id);
511 : continue;
512 : }
513 :
514 : // now we've gone through the allowed `crate`, `self` or leading `super`
515 : // segments. we can start resolving each segment itself.
516 : // if we do see another leading segment, then we can error out.
517 : break;
518 : }
519 :
520 23701 : return iterator;
521 : }
522 :
523 : template <Namespace N>
524 : template <typename S>
525 : tl::optional<typename ForeverStack<N>::Node &>
526 23701 : ForeverStack<N>::resolve_segments (
527 : Node &starting_point, const std::vector<S> &segments,
528 : typename std::vector<S>::const_iterator iterator,
529 : std::function<void (const S &, NodeId)> insert_segment_resolution,
530 : std::vector<Error> &collect_errors)
531 : {
532 23701 : Node *current_node = &starting_point;
533 53919 : for (; !is_last (iterator, segments); iterator++)
534 : {
535 30218 : auto &outer_seg = *iterator;
536 :
537 30218 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
538 : {
539 0 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
540 0 : lang_item.value ());
541 0 : current_node = &dfs_node (root, seg_id).value ();
542 :
543 0 : insert_segment_resolution (outer_seg, seg_id);
544 0 : continue;
545 0 : }
546 :
547 30218 : auto &seg = unwrap_type_segment (outer_seg);
548 30218 : std::string str = seg.as_string ();
549 30218 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
550 :
551 : // check that we don't encounter *any* leading keywords afterwards
552 30218 : if (check_leading_kw_at_start (collect_errors, seg,
553 30218 : seg.is_crate_path_seg ()
554 30218 : || seg.is_super_path_seg ()
555 60429 : || seg.is_lower_self_seg ()))
556 9 : return tl::nullopt;
557 :
558 30209 : tl::optional<std::reference_wrapper<Node>> child = tl::nullopt;
559 :
560 : /*
561 : * On every iteration this loop either
562 : *
563 : * 1. terminates
564 : *
565 : * 2. decreases the depth of the node pointed to by current_node until
566 : * current_node reaches the root
567 : *
568 : * 3. If the root node is reached, and we were not able to resolve the
569 : * segment, we search the prelude rib for the segment, by setting
570 : * current_node to point to the prelude, and toggling the
571 : * searched_prelude boolean to true. If current_node is the prelude
572 : * rib, and searched_prelude is true, we will exit.
573 : *
574 : * This ensures termination.
575 : *
576 : */
577 30209 : bool searched_prelude = false;
578 44854 : while (true)
579 : {
580 86075 : if (is_start (iterator, segments)
581 77379 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
582 : {
583 : // we can't reference associated types/functions like this
584 8696 : current_node = ¤t_node->parent.value ();
585 11070 : continue;
586 : }
587 :
588 : // may set the value of child
589 258290 : for (auto &kv : current_node->children)
590 : {
591 213436 : auto &link = kv.first;
592 :
593 426872 : if (link.path.map_or (
594 532363 : [&str] (Identifier path) {
595 105491 : auto &path_str = path.as_string ();
596 105491 : return str == path_str;
597 : },
598 213436 : false))
599 : {
600 92512 : child = kv.second;
601 : break;
602 : }
603 : }
604 :
605 68683 : if (child.has_value ())
606 : {
607 : break;
608 : }
609 :
610 89697 : auto rib_lookup = current_node->rib.get (seg.as_string ());
611 44854 : if (rib_lookup && !rib_lookup->is_ambiguous ())
612 : {
613 3691 : if (Analysis::Mappings::get ()
614 3691 : .lookup_glob_container (rib_lookup->get_node_id ())
615 3691 : .has_value ())
616 : {
617 2274 : child = dfs_node (root, rib_lookup->get_node_id ()).value ();
618 : break;
619 : }
620 : else
621 : {
622 1417 : insert_segment_resolution (outer_seg,
623 : rib_lookup->get_node_id ());
624 1417 : return tl::nullopt;
625 : }
626 : }
627 :
628 41163 : if (current_node->is_root () && !searched_prelude)
629 : {
630 2374 : searched_prelude = true;
631 2374 : current_node = &lang_prelude;
632 : continue;
633 : }
634 :
635 38789 : if (!is_start (iterator, segments)
636 38784 : || current_node->rib.kind == Rib::Kind::Module
637 77260 : || current_node->is_prelude ())
638 : {
639 2689 : return tl::nullopt;
640 : }
641 :
642 36100 : current_node = ¤t_node->parent.value ();
643 : }
644 :
645 : // if child didn't point to a value
646 : // the while loop above would have returned or kept looping
647 26103 : current_node = &child->get ();
648 26103 : insert_segment_resolution (outer_seg, current_node->id);
649 : }
650 :
651 19586 : return *current_node;
652 : }
653 :
654 : template <>
655 : inline tl::optional<Rib::Definition>
656 8608 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
657 : std::string &seg_name,
658 : bool is_lower_self)
659 : {
660 8608 : if (is_lower_self)
661 204 : return Rib::Definition::NonShadowable (final_node.id);
662 : else
663 8404 : return final_node.rib.get (seg_name);
664 : }
665 :
666 : template <Namespace N>
667 : tl::optional<Rib::Definition>
668 10978 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
669 : bool is_lower_self)
670 : {
671 10978 : return final_node.rib.get (seg_name);
672 : }
673 :
674 : template <Namespace N>
675 : template <typename S>
676 : tl::optional<Rib::Definition>
677 0 : ForeverStack<N>::resolve_path (
678 : const std::vector<S> &segments, ResolutionMode mode,
679 : std::function<void (const S &, NodeId)> insert_segment_resolution,
680 : std::vector<Error> &collect_errors, NodeId starting_point_id)
681 : {
682 0 : auto starting_point = dfs_node (root, starting_point_id);
683 :
684 : // We may have a prelude, but haven't visited it yet and thus it's not in our
685 : // nodes
686 0 : if (!starting_point)
687 0 : return tl::nullopt;
688 :
689 0 : return resolve_path (segments, mode, insert_segment_resolution,
690 0 : collect_errors, *starting_point);
691 : }
692 :
693 : template <Namespace N>
694 : template <typename S>
695 : tl::optional<Rib::Definition>
696 93698 : ForeverStack<N>::resolve_path (
697 : const std::vector<S> &segments, ResolutionMode mode,
698 : std::function<void (const S &, NodeId)> insert_segment_resolution,
699 : std::vector<Error> &collect_errors)
700 : {
701 93698 : std::reference_wrapper<Node> starting_point = cursor ();
702 :
703 93698 : return resolve_path (segments, mode, insert_segment_resolution,
704 93698 : collect_errors, starting_point);
705 : }
706 :
707 : template <Namespace N>
708 : template <typename S>
709 : tl::optional<Rib::Definition>
710 93698 : ForeverStack<N>::resolve_path (
711 : const std::vector<S> &segments, ResolutionMode mode,
712 : std::function<void (const S &, NodeId)> insert_segment_resolution,
713 : std::vector<Error> &collect_errors,
714 : std::reference_wrapper<Node> starting_point)
715 : {
716 93698 : rust_assert (!segments.empty ());
717 :
718 93698 : switch (mode)
719 : {
720 : case ResolutionMode::Normal:
721 : break; // default
722 1036 : case ResolutionMode::FromRoot:
723 1036 : starting_point = root;
724 1036 : break;
725 0 : case ResolutionMode::FromExtern:
726 0 : starting_point = extern_prelude;
727 0 : break;
728 0 : default:
729 0 : rust_unreachable ();
730 : }
731 :
732 : // if there's only one segment, we just use `get`
733 93698 : if (segments.size () == 1)
734 : {
735 69995 : auto &outer_seg = segments.front ();
736 69995 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
737 : {
738 780 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
739 390 : lang_item.value ());
740 :
741 390 : insert_segment_resolution (outer_seg, seg_id);
742 : // TODO: does NonShadowable matter?
743 390 : return Rib::Definition::NonShadowable (seg_id);
744 : }
745 :
746 69605 : auto &seg = unwrap_type_segment (outer_seg);
747 :
748 69605 : tl::optional<Rib::Definition> res
749 208815 : = get (starting_point.get (), seg.as_string ());
750 :
751 69605 : if (!res)
752 51668 : res = get_lang_prelude (seg.as_string ());
753 :
754 54140 : if (N == Namespace::Types && !res)
755 : {
756 197 : if (seg.is_crate_path_seg ())
757 : {
758 53 : insert_segment_resolution (outer_seg, root.id);
759 : // TODO: does NonShadowable matter?
760 53 : return Rib::Definition::NonShadowable (root.id);
761 : }
762 144 : else if (seg.is_lower_self_seg ())
763 : {
764 5 : NodeId id = find_closest_module (starting_point.get ()).id;
765 5 : insert_segment_resolution (outer_seg, id);
766 : // TODO: does NonShadowable matter?
767 5 : return Rib::Definition::NonShadowable (id);
768 : }
769 139 : else if (seg.is_super_path_seg ())
770 : {
771 : Node &closest_module
772 1 : = find_closest_module (starting_point.get ());
773 1 : if (closest_module.is_root ())
774 : {
775 0 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
776 : "too many leading %<super%> keywords");
777 0 : return tl::nullopt;
778 : }
779 :
780 1 : NodeId id
781 1 : = find_closest_module (closest_module.parent.value ()).id;
782 1 : insert_segment_resolution (outer_seg, id);
783 : // TODO: does NonShadowable matter?
784 1 : return Rib::Definition::NonShadowable (id);
785 : }
786 : else
787 : {
788 : // HACK: check for a module after we check the language prelude
789 616 : for (auto &kv :
790 138 : find_closest_module (starting_point.get ()).children)
791 : {
792 487 : auto &link = kv.first;
793 :
794 974 : if (link.path.map_or (
795 1392 : [&seg] (Identifier path) {
796 418 : auto &path_str = path.as_string ();
797 506 : return path_str == seg.as_string ();
798 : },
799 487 : false))
800 : {
801 9 : insert_segment_resolution (outer_seg, kv.second.id);
802 9 : return Rib::Definition::NonShadowable (kv.second.id);
803 : }
804 : }
805 : }
806 : }
807 :
808 69537 : if (res && !res->is_ambiguous ())
809 68936 : insert_segment_resolution (outer_seg, res->get_node_id ());
810 69537 : return res;
811 69605 : }
812 :
813 23703 : return find_starting_point (segments, starting_point,
814 : insert_segment_resolution, collect_errors)
815 23703 : .and_then (
816 47404 : [this, &segments, &starting_point, &insert_segment_resolution,
817 : &collect_errors] (typename std::vector<S>::const_iterator iterator) {
818 23701 : return resolve_segments (starting_point.get (), segments, iterator,
819 23701 : insert_segment_resolution, collect_errors);
820 : })
821 43289 : .and_then ([this, &segments, &insert_segment_resolution] (
822 : Node &final_node) -> tl::optional<Rib::Definition> {
823 : // leave resolution within impl blocks to type checker
824 19586 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
825 0 : return tl::nullopt;
826 :
827 19586 : auto &seg = unwrap_type_segment (segments.back ());
828 9131 : std::string seg_name = seg.as_string ();
829 :
830 : // assuming this can't be a lang item segment
831 19586 : tl::optional<Rib::Definition> res
832 : = resolve_final_segment (final_node, seg_name,
833 19586 : seg.is_lower_self_seg ());
834 : // Ok we didn't find it in the rib, Lets try the prelude...
835 19586 : if (!res)
836 9806 : res = get_lang_prelude (seg_name);
837 :
838 8608 : if (N == Namespace::Types && !res)
839 : {
840 : // HACK: check for a module after we check the language prelude
841 2337 : for (auto &kv : final_node.children)
842 : {
843 1336 : auto &link = kv.first;
844 :
845 2672 : if (link.path.map_or (
846 92 : [&seg_name] (Identifier path) {
847 92 : auto &path_str = path.as_string ();
848 92 : return path_str == seg_name;
849 : },
850 1336 : false))
851 : {
852 58 : insert_segment_resolution (segments.back (), kv.second.id);
853 58 : return Rib::Definition::NonShadowable (kv.second.id);
854 : }
855 : }
856 : }
857 :
858 19528 : if (res && !res->is_ambiguous ())
859 9780 : insert_segment_resolution (segments.back (), res->get_node_id ());
860 :
861 19528 : return res;
862 43289 : });
863 : }
864 :
865 : template <Namespace N>
866 : tl::optional<typename ForeverStack<N>::DfsResult>
867 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
868 : {
869 : auto values = starting_point.rib.get_values ();
870 :
871 : for (auto &kv : values)
872 : {
873 : for (auto id : kv.second.ids_shadowable)
874 : if (id == to_find)
875 : return {{starting_point, kv.first}};
876 : for (auto id : kv.second.ids_non_shadowable)
877 : if (id == to_find)
878 : return {{starting_point, kv.first}};
879 : for (auto id : kv.second.ids_globbed)
880 : if (id == to_find)
881 : return {{starting_point, kv.first}};
882 : }
883 :
884 : for (auto &child : starting_point.children)
885 : {
886 : auto candidate = dfs (child.second, to_find);
887 :
888 : if (candidate.has_value ())
889 : return candidate;
890 : }
891 :
892 : return tl::nullopt;
893 : }
894 :
895 : template <Namespace N>
896 : tl::optional<typename ForeverStack<N>::ConstDfsResult>
897 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
898 : NodeId to_find) const
899 : {
900 : auto values = starting_point.rib.get_values ();
901 :
902 : for (auto &kv : values)
903 : {
904 : for (auto id : kv.second.ids_shadowable)
905 : if (id == to_find)
906 : return {{starting_point, kv.first}};
907 : for (auto id : kv.second.ids_non_shadowable)
908 : if (id == to_find)
909 : return {{starting_point, kv.first}};
910 : for (auto id : kv.second.ids_globbed)
911 : if (id == to_find)
912 : return {{starting_point, kv.first}};
913 : }
914 :
915 : for (auto &child : starting_point.children)
916 : {
917 : auto candidate = dfs (child.second, to_find);
918 :
919 : if (candidate.has_value ())
920 : return candidate;
921 : }
922 :
923 : return tl::nullopt;
924 : }
925 :
926 : template <Namespace N>
927 : tl::optional<Rib &>
928 1297 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
929 : {
930 1297 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
931 1 : return x.rib;
932 1297 : });
933 : }
934 :
935 : template <Namespace N>
936 : tl::optional<const Rib &>
937 52 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
938 : NodeId to_find) const
939 : {
940 52 : return dfs_node (starting_point, to_find)
941 52 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
942 : }
943 :
944 : template <Namespace N>
945 : tl::optional<typename ForeverStack<N>::Node &>
946 23313 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
947 : NodeId to_find)
948 : {
949 23313 : if (starting_point.id == to_find)
950 2275 : return starting_point;
951 :
952 34456 : for (auto &child : starting_point.children)
953 : {
954 19742 : auto candidate = dfs_node (child.second, to_find);
955 :
956 19742 : if (candidate.has_value ())
957 6324 : return candidate;
958 : }
959 :
960 14714 : return tl::nullopt;
961 : }
962 :
963 : template <Namespace N>
964 : tl::optional<const typename ForeverStack<N>::Node &>
965 939 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
966 : NodeId to_find) const
967 : {
968 939 : if (starting_point.id == to_find)
969 68 : return starting_point;
970 :
971 1493 : for (auto &child : starting_point.children)
972 : {
973 859 : auto candidate = dfs_node (child.second, to_find);
974 :
975 859 : if (candidate.has_value ())
976 237 : return candidate;
977 : }
978 :
979 634 : return tl::nullopt;
980 : }
981 :
982 : template <Namespace N>
983 : tl::optional<Rib &>
984 : ForeverStack<N>::to_rib (NodeId rib_id)
985 : {
986 : return dfs_rib (root, rib_id);
987 : }
988 :
989 : template <Namespace N>
990 : tl::optional<const Rib &>
991 52 : ForeverStack<N>::to_rib (NodeId rib_id) const
992 : {
993 52 : return dfs_rib (root, rib_id);
994 : }
995 :
996 : template <Namespace N>
997 : void
998 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
999 : const std::string &next,
1000 : const std::string &next_next) const
1001 : {
1002 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
1003 0 : stream << next << "rib [" << rib_kind << "]: {";
1004 0 : if (rib.get_values ().empty ())
1005 : {
1006 0 : stream << "}\n";
1007 0 : return;
1008 : }
1009 : else
1010 : {
1011 0 : stream << "\n";
1012 : }
1013 :
1014 0 : for (const auto &kv : rib.get_values ())
1015 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
1016 :
1017 0 : stream << next << "},\n";
1018 0 : }
1019 :
1020 : template <Namespace N>
1021 : void
1022 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
1023 : const ForeverStack<N>::Node &node,
1024 : unsigned depth) const
1025 : {
1026 0 : auto indent = std::string (indentation, ' ');
1027 0 : auto next = std::string (indentation + 4, ' ');
1028 0 : auto next_next = std::string (indentation + 8, ' ');
1029 :
1030 : stream << indent << "Node {\n"
1031 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
1032 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
1033 0 : << ",\n";
1034 :
1035 0 : stream_rib (stream, node.rib, next, next_next);
1036 :
1037 0 : stream << indent << "}\n";
1038 :
1039 0 : for (auto &kv : node.children)
1040 : {
1041 0 : auto link = kv.first;
1042 0 : auto child = kv.second;
1043 0 : stream << indent << "Link " << depth << " (" << link.id << ", "
1044 0 : << (link.path.has_value () ? link.path.value ().as_string ()
1045 0 : : "<anon>")
1046 0 : << "):\n";
1047 :
1048 0 : stream_node (stream, indentation + 4, child, depth + 1);
1049 :
1050 0 : stream << '\n';
1051 : }
1052 0 : }
1053 :
1054 : template <Namespace N>
1055 : std::string
1056 0 : ForeverStack<N>::as_debug_string () const
1057 : {
1058 0 : std::stringstream stream;
1059 :
1060 0 : stream_node (stream, 0, root);
1061 :
1062 0 : return stream.str ();
1063 0 : }
1064 :
1065 : template <Namespace N>
1066 : bool
1067 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
1068 : {
1069 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
1070 : }
1071 :
1072 : // FIXME: Can we add selftests?
1073 :
1074 : } // namespace Resolver2_0
1075 : } // namespace Rust
|
