Branch data Line data Source code
1 : : // Copyright (C) 2020-2025 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 : 223951 : ForeverStack<N>::Node::is_root () const
34 : : {
35 : 44446 : 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 : 19756 : ForeverStack<N>::Node::is_leaf () const
48 : : {
49 : 19756 : 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 : 168582 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : : tl::optional<Identifier> path)
66 : : {
67 : 193560 : push_inner (rib_kind, Link (id, path));
68 : 168582 : }
69 : :
70 : : template <Namespace N>
71 : : void
72 : 168582 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : : {
74 : 168582 : 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 : 3006 : rust_assert (&cursor_reference.get () == &root);
79 : : // Prelude doesn't have an access path
80 : 3006 : rust_assert (!link.path);
81 : 3006 : update_cursor (this->lang_prelude);
82 : 3006 : 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 : 331152 : auto emplace = cursor ().children.emplace (
90 : 165576 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 : :
92 : 165576 : auto it = emplace.first;
93 : 165576 : auto existed = !emplace.second;
94 : :
95 : 193647 : 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 : 165576 : update_cursor (it->second);
102 : : }
103 : :
104 : : template <Namespace N>
105 : : void
106 : 168570 : ForeverStack<N>::pop ()
107 : : {
108 : 168570 : rust_assert (!cursor ().is_root ());
109 : :
110 : 168570 : rust_debug ("popping link");
111 : :
112 : 214491 : for (const auto &kv : cursor ().rib.get_values ())
113 : 45921 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : : kv.second.to_string ().c_str ());
115 : :
116 : 168570 : if (cursor ().parent.has_value ())
117 : 334863 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 : 166293 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : : kv.second.to_string ().c_str ());
120 : :
121 : 168570 : update_cursor (cursor ().parent.value ());
122 : 168570 : }
123 : :
124 : : static tl::expected<NodeId, DuplicateNameError>
125 : 38854 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : : {
127 : 77708 : return rib.insert (name, definition);
128 : : }
129 : :
130 : : template <Namespace N>
131 : : tl::expected<NodeId, DuplicateNameError>
132 : 35704 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : : {
134 : 35704 : 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 : 35704 : return insert_inner (innermost_rib, name.as_string (),
141 : 71408 : Rib::Definition::NonShadowable (node));
142 : : }
143 : :
144 : : template <Namespace N>
145 : : tl::expected<NodeId, DuplicateNameError>
146 : 2591 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : : {
148 : 2591 : auto &innermost_rib = peek ();
149 : :
150 : 2591 : return insert_inner (innermost_rib, name.as_string (),
151 : 5182 : Rib::Definition::Shadowable (node));
152 : : }
153 : :
154 : : template <Namespace N>
155 : : tl::expected<NodeId, DuplicateNameError>
156 : 24 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : : {
158 : 24 : auto &innermost_rib = peek ();
159 : :
160 : 24 : return insert_inner (innermost_rib, name.as_string (),
161 : 48 : Rib::Definition::Globbed (node));
162 : : }
163 : :
164 : : template <Namespace N>
165 : : tl::expected<NodeId, DuplicateNameError>
166 : 10 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : : {
168 : 10 : auto &root_rib = root.rib;
169 : :
170 : : // inserting in the root of the crate is never a shadowing operation, even for
171 : : // macros
172 : 10 : return insert_inner (root_rib, name.as_string (),
173 : 20 : 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 : 63 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : : {
182 : 63 : return insert_inner (peek (), name.as_string (),
183 : 126 : Rib::Definition::Shadowable (node));
184 : : }
185 : :
186 : : template <>
187 : : inline tl::expected<NodeId, DuplicateNameError>
188 : 27 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
189 : : {
190 : 27 : return insert_inner (peek (), name.as_string (),
191 : 54 : Rib::Definition::Shadowable (node));
192 : : }
193 : :
194 : : template <>
195 : : inline tl::expected<NodeId, DuplicateNameError>
196 : 435 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : : {
198 : 435 : return insert_inner (peek (), name.as_string (),
199 : 870 : Rib::Definition::NonShadowable (node, true));
200 : : }
201 : :
202 : : template <Namespace N>
203 : : Rib &
204 : 45546 : ForeverStack<N>::peek ()
205 : : {
206 : 45546 : return cursor ().rib;
207 : : }
208 : :
209 : : template <Namespace N>
210 : : const Rib &
211 : : ForeverStack<N>::peek () const
212 : : {
213 : : return cursor ().rib;
214 : : }
215 : :
216 : : template <Namespace N>
217 : : void
218 : 11062 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
219 : : {
220 : 22124 : return reverse_iter (cursor (), lambda);
221 : : }
222 : :
223 : : template <Namespace N>
224 : : void
225 : : ForeverStack<N>::reverse_iter (
226 : : std::function<KeepGoing (const Node &)> lambda) const
227 : : {
228 : : return reverse_iter (cursor (), lambda);
229 : : }
230 : :
231 : : template <Namespace N>
232 : : void
233 : 11447 : ForeverStack<N>::reverse_iter (Node &start,
234 : : std::function<KeepGoing (Node &)> lambda)
235 : : {
236 : 11447 : auto *tmp = &start;
237 : :
238 : 14746 : while (true)
239 : : {
240 : 26193 : auto keep_going = lambda (*tmp);
241 : 26193 : if (keep_going == KeepGoing::No)
242 : : return;
243 : :
244 : 18842 : if (tmp->is_root ())
245 : : return;
246 : :
247 : 14746 : tmp = &tmp->parent.value ();
248 : : }
249 : : }
250 : :
251 : : template <Namespace N>
252 : : void
253 : 5601 : ForeverStack<N>::reverse_iter (
254 : : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
255 : : {
256 : 5601 : auto *tmp = &start;
257 : :
258 : 3940 : while (true)
259 : : {
260 : 9541 : auto keep_going = lambda (*tmp);
261 : 9541 : if (keep_going == KeepGoing::No)
262 : : return;
263 : :
264 : 3940 : if (tmp->is_root ())
265 : : return;
266 : :
267 : 3940 : tmp = &tmp->parent.value ();
268 : : }
269 : : }
270 : :
271 : : template <Namespace N>
272 : : typename ForeverStack<N>::Node &
273 : 898651 : ForeverStack<N>::cursor ()
274 : : {
275 : 898651 : return cursor_reference;
276 : : }
277 : :
278 : : template <Namespace N>
279 : : const typename ForeverStack<N>::Node &
280 : : ForeverStack<N>::cursor () const
281 : : {
282 : : return cursor_reference;
283 : : }
284 : :
285 : : template <Namespace N>
286 : : void
287 : 168582 : ForeverStack<N>::update_cursor (Node &new_cursor)
288 : : {
289 : 168582 : cursor_reference = new_cursor;
290 : : }
291 : :
292 : : template <Namespace N>
293 : : tl::optional<Rib::Definition>
294 : 11048 : ForeverStack<N>::get (const Identifier &name)
295 : : {
296 : 11048 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
297 : :
298 : : // TODO: Can we improve the API? have `reverse_iter` return an optional?
299 : 36813 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
300 : 25765 : auto candidate = current.rib.get (name.as_string ());
301 : :
302 : 25765 : return candidate.map_or (
303 : 58493 : [&resolved_definition] (Rib::Definition found) {
304 : 6963 : if (found.is_variant ())
305 : : return KeepGoing::Yes;
306 : : // for most namespaces, we do not need to care about various ribs -
307 : : // they are available from all contexts if defined in the current
308 : : // scope, or an outermore one. so if we do have a candidate, we can
309 : : // return it directly and stop iterating
310 : 6960 : resolved_definition = found;
311 : :
312 : 6960 : return KeepGoing::No;
313 : : },
314 : : // if there was no candidate, we keep iterating
315 : 25765 : KeepGoing::Yes);
316 : 25765 : });
317 : :
318 : 11048 : return resolved_definition;
319 : : }
320 : :
321 : : template <Namespace N>
322 : : tl::optional<Rib::Definition>
323 : 9 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
324 : : {
325 : 9 : return lang_prelude.rib.get (name.as_string ());
326 : : }
327 : :
328 : : template <Namespace N>
329 : : tl::optional<Rib::Definition>
330 : 4110 : ForeverStack<N>::get_lang_prelude (const std::string &name)
331 : : {
332 : 4110 : return lang_prelude.rib.get (name);
333 : : }
334 : :
335 : : template <>
336 : 14 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
337 : : const Identifier &name)
338 : : {
339 : 14 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
340 : :
341 : 14 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
342 : : // looking up for labels cannot go through function ribs
343 : : // TODO: What other ribs?
344 : 14 : if (current.rib.kind == Rib::Kind::Function)
345 : : return KeepGoing::No;
346 : :
347 : 14 : auto candidate = current.rib.get (name.as_string ());
348 : :
349 : : // FIXME: Factor this in a function with the generic `get`
350 : 14 : return candidate.map_or (
351 : 34 : [&resolved_definition] (Rib::Definition found) {
352 : 6 : resolved_definition = found;
353 : :
354 : 6 : return KeepGoing::No;
355 : : },
356 : 14 : KeepGoing::Yes);
357 : 14 : });
358 : :
359 : 14 : return resolved_definition;
360 : : }
361 : :
362 : : /* Check if an iterator points to the last element */
363 : : template <typename I, typename C>
364 : : static bool
365 : 6610 : is_last (const I &iterator, const C &collection)
366 : : {
367 : 6610 : return iterator + 1 == collection.end ();
368 : : }
369 : :
370 : : /* Check if an iterator points to the start of the collection */
371 : : template <typename I, typename C>
372 : : static bool
373 : 2737 : is_start (const I &iterator, const C &collection)
374 : : {
375 : 4937 : return iterator == collection.begin ();
376 : : }
377 : :
378 : : template <Namespace N>
379 : : typename ForeverStack<N>::Node &
380 : 385 : ForeverStack<N>::find_closest_module (Node &starting_point)
381 : : {
382 : 385 : auto *closest_module = &starting_point;
383 : :
384 : 799 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
385 : 414 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
386 : : {
387 : 385 : closest_module = ¤t;
388 : 385 : return KeepGoing::No;
389 : : }
390 : :
391 : : return KeepGoing::Yes;
392 : : });
393 : :
394 : 385 : return *closest_module;
395 : : }
396 : :
397 : : /* If a the given condition is met, emit an error about misused leading path
398 : : * segments */
399 : : template <typename S>
400 : : static inline bool
401 : 4701 : check_leading_kw_at_start (std::vector<Error> &collect_errors, const S &segment,
402 : : bool condition)
403 : : {
404 : 4701 : if (condition)
405 : 12 : collect_errors.emplace_back (
406 : 12 : segment.get_locus (), ErrorCode::E0433,
407 : : "%qs in paths can only be used in start position",
408 : 24 : segment.as_string ().c_str ());
409 : :
410 : 4701 : return condition;
411 : : }
412 : :
413 : : // we first need to handle the "starting" segments - `super`, `self` or
414 : : // `crate`. we don't need to do anything for `self` and can just skip it. for
415 : : // `crate`, we need to go back to the root of the current stack. for each
416 : : // `super` segment, we go back to the cursor's parent until we reach the
417 : : // correct one or the root.
418 : : template <Namespace N>
419 : : template <typename S>
420 : : tl::optional<typename std::vector<S>::const_iterator>
421 : 2187 : ForeverStack<N>::find_starting_point (
422 : : const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point,
423 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
424 : : std::vector<Error> &collect_errors)
425 : : {
426 : 2187 : auto iterator = segments.begin ();
427 : :
428 : 2369 : for (; !is_last (iterator, segments); iterator++)
429 : : {
430 : 2200 : auto &outer_seg = *iterator;
431 : :
432 : 2200 : if (unwrap_segment_get_lang_item (outer_seg).has_value ())
433 : : break;
434 : :
435 : 2200 : auto &seg = unwrap_type_segment (outer_seg);
436 : 2200 : bool is_self_or_crate
437 : 2200 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
438 : :
439 : : // if we're after the first path segment and meet `self` or `crate`, it's
440 : : // an error - we should only be seeing `super` keywords at this point
441 : 2200 : if (check_leading_kw_at_start (collect_errors, seg,
442 : 2200 : !is_start (iterator, segments)
443 : 2200 : && is_self_or_crate))
444 : 2 : return tl::nullopt;
445 : :
446 : 2198 : if (seg.is_crate_path_seg ())
447 : : {
448 : 278 : starting_point = root;
449 : 278 : insert_segment_resolution (outer_seg, starting_point.get ().id);
450 : 278 : iterator++;
451 : : break;
452 : : }
453 : 1920 : if (seg.is_lower_self_seg ())
454 : : {
455 : : // insert segment resolution and exit
456 : 19 : starting_point = find_closest_module (starting_point);
457 : 19 : insert_segment_resolution (outer_seg, starting_point.get ().id);
458 : 19 : iterator++;
459 : : break;
460 : : }
461 : 2083 : if (seg.is_super_path_seg ())
462 : : {
463 : 184 : starting_point = find_closest_module (starting_point);
464 : 184 : if (starting_point.get ().is_root ())
465 : : {
466 : 2 : collect_errors.emplace_back (
467 : 2 : seg.get_locus (), ErrorCode::E0433,
468 : : "too many leading %<super%> keywords");
469 : 2 : return tl::nullopt;
470 : : }
471 : :
472 : 182 : starting_point
473 : 182 : = find_closest_module (starting_point.get ().parent.value ());
474 : :
475 : 182 : insert_segment_resolution (outer_seg, starting_point.get ().id);
476 : : continue;
477 : : }
478 : :
479 : : // now we've gone through the allowed `crate`, `self` or leading `super`
480 : : // segments. we can start resolving each segment itself.
481 : : // if we do see another leading segment, then we can error out.
482 : : break;
483 : : }
484 : :
485 : 2183 : return iterator;
486 : : }
487 : :
488 : : template <Namespace N>
489 : : template <typename S>
490 : : tl::optional<typename ForeverStack<N>::Node &>
491 : 2183 : ForeverStack<N>::resolve_segments (
492 : : Node &starting_point, const std::vector<S> &segments,
493 : : typename std::vector<S>::const_iterator iterator,
494 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
495 : : std::vector<Error> &collect_errors)
496 : : {
497 : 2183 : Node *current_node = &starting_point;
498 : 4684 : for (; !is_last (iterator, segments); iterator++)
499 : : {
500 : 2501 : auto &outer_seg = *iterator;
501 : :
502 : 2501 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
503 : : {
504 : 0 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
505 : 0 : lang_item.value ());
506 : 0 : current_node = &dfs_node (root, seg_id).value ();
507 : :
508 : 0 : insert_segment_resolution (outer_seg, seg_id);
509 : 0 : continue;
510 : 0 : }
511 : :
512 : 2501 : auto &seg = unwrap_type_segment (outer_seg);
513 : 2501 : std::string str = seg.as_string ();
514 : 2501 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
515 : :
516 : : // check that we don't encounter *any* leading keywords afterwards
517 : 2501 : if (check_leading_kw_at_start (collect_errors, seg,
518 : 2501 : seg.is_crate_path_seg ()
519 : 2501 : || seg.is_super_path_seg ()
520 : 4994 : || seg.is_lower_self_seg ()))
521 : 10 : return tl::nullopt;
522 : :
523 : 2491 : tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt;
524 : :
525 : : /*
526 : : * On every iteration this loop either
527 : : *
528 : : * 1. terminates
529 : : *
530 : : * 2. decreases the depth of the node pointed to by current_node until
531 : : * current_node reaches the root
532 : : *
533 : : * 3. If the root node is reached, and we were not able to resolve the
534 : : * segment, we search the prelude rib for the segment, by setting
535 : : * current_node to point to the prelude, and toggling the
536 : : * searched_prelude boolean to true. If current_node is the prelude
537 : : * rib, and searched_prelude is true, we will exit.
538 : : *
539 : : * This ensures termination.
540 : : *
541 : : */
542 : 2491 : bool searched_prelude = false;
543 : : while (true)
544 : : {
545 : : // may set the value of child
546 : 20747 : for (auto &kv : current_node->children)
547 : : {
548 : 17586 : auto &link = kv.first;
549 : :
550 : 35172 : if (link.path.map_or (
551 : 42768 : [&str] (Identifier path) {
552 : 7596 : auto &path_str = path.as_string ();
553 : 7596 : return str == path_str;
554 : : },
555 : 17586 : false))
556 : : {
557 : 2058 : child = kv.second;
558 : : break;
559 : : }
560 : : }
561 : :
562 : 5219 : if (child.has_value ())
563 : : {
564 : : break;
565 : : }
566 : :
567 : : if (N == Namespace::Types)
568 : : {
569 : 2942 : auto rib_lookup = current_node->rib.get (seg.as_string ());
570 : 1475 : if (rib_lookup && !rib_lookup->is_ambiguous ())
571 : : {
572 : 265 : insert_segment_resolution (outer_seg,
573 : : rib_lookup->get_node_id ());
574 : 265 : return tl::nullopt;
575 : : }
576 : 1475 : }
577 : :
578 : 2896 : if (current_node->is_root () && !searched_prelude)
579 : : {
580 : 159 : searched_prelude = true;
581 : 159 : current_node = &lang_prelude;
582 : 159 : continue;
583 : : }
584 : :
585 : 2737 : if (!is_start (iterator, segments)
586 : 2726 : || current_node->rib.kind == Rib::Kind::Module
587 : 5462 : || current_node->is_prelude ())
588 : : {
589 : 168 : return tl::nullopt;
590 : : }
591 : :
592 : 2569 : current_node = ¤t_node->parent.value ();
593 : : }
594 : :
595 : : // if child didn't contain a value
596 : : // the while loop above should have return'd or kept looping
597 : 2058 : current_node = &child.value ();
598 : 2058 : insert_segment_resolution (outer_seg, current_node->id);
599 : : }
600 : :
601 : 1740 : return *current_node;
602 : : }
603 : :
604 : : template <>
605 : : inline tl::optional<Rib::Definition>
606 : 520 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
607 : : std::string &seg_name,
608 : : bool is_lower_self)
609 : : {
610 : 520 : if (is_lower_self)
611 : 38 : return Rib::Definition::NonShadowable (final_node.id);
612 : : else
613 : 482 : return final_node.rib.get (seg_name);
614 : : }
615 : :
616 : : template <Namespace N>
617 : : tl::optional<Rib::Definition>
618 : 1058 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
619 : : bool is_lower_self)
620 : : {
621 : 1058 : return final_node.rib.get (seg_name);
622 : : }
623 : :
624 : : template <Namespace N>
625 : : template <typename S>
626 : : tl::optional<Rib::Definition>
627 : 10213 : ForeverStack<N>::resolve_path (
628 : : const std::vector<S> &segments, bool has_opening_scope_resolution,
629 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
630 : : std::vector<Error> &collect_errors)
631 : : {
632 : : // TODO: What to do if segments.empty() ?
633 : :
634 : : // handle paths with opening scopes
635 : 10213 : std::function<void (void)> cleanup_current = [] () {};
636 : 10213 : if (has_opening_scope_resolution)
637 : : {
638 : 42 : Node *last_current = &cursor_reference.get ();
639 : 42 : if (get_rust_edition () == Edition::E2015)
640 : 42 : cursor_reference = root;
641 : : else
642 : 0 : cursor_reference = extern_prelude;
643 : : cleanup_current
644 : 84 : = [this, last_current] () { cursor_reference = *last_current; };
645 : : }
646 : :
647 : : // if there's only one segment, we just use `get`
648 : 10213 : if (segments.size () == 1)
649 : : {
650 : 8026 : auto &seg = segments.front ();
651 : 8026 : if (auto lang_item = unwrap_segment_get_lang_item (seg))
652 : : {
653 : 78 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
654 : 39 : lang_item.value ());
655 : :
656 : 39 : insert_segment_resolution (seg, seg_id);
657 : 39 : cleanup_current ();
658 : : // TODO: does NonShadowable matter?
659 : 39 : return Rib::Definition::NonShadowable (seg_id);
660 : : }
661 : :
662 : 7987 : tl::optional<Rib::Definition> res
663 : 31888 : = get (unwrap_type_segment (segments.back ()).as_string ());
664 : :
665 : 7987 : if (!res)
666 : 6610 : res = get_lang_prelude (
667 : 10036 : unwrap_type_segment (segments.back ()).as_string ());
668 : :
669 : 7987 : if (res && !res->is_ambiguous ())
670 : 7877 : insert_segment_resolution (segments.back (), res->get_node_id ());
671 : 7987 : cleanup_current ();
672 : 7987 : return res;
673 : 7987 : }
674 : :
675 : 2187 : std::reference_wrapper<Node> starting_point = cursor ();
676 : :
677 : 2187 : auto res
678 : 2187 : = find_starting_point (segments, starting_point, insert_segment_resolution,
679 : : collect_errors)
680 : 4374 : .and_then (
681 : 4370 : [this, &segments, &starting_point, &insert_segment_resolution,
682 : : &collect_errors] (typename std::vector<S>::const_iterator iterator) {
683 : 2183 : return resolve_segments (starting_point.get (), segments, iterator,
684 : 2183 : insert_segment_resolution, collect_errors);
685 : : })
686 : 3927 : .and_then ([this, &segments, &insert_segment_resolution] (
687 : : Node &final_node) -> tl::optional<Rib::Definition> {
688 : : // leave resolution within impl blocks to type checker
689 : 1740 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
690 : 162 : return tl::nullopt;
691 : :
692 : 1578 : auto &seg = unwrap_type_segment (segments.back ());
693 : 1578 : std::string seg_name = seg.as_string ();
694 : :
695 : : // assuming this can't be a lang item segment
696 : 1578 : tl::optional<Rib::Definition> res
697 : : = resolve_final_segment (final_node, seg_name,
698 : 1578 : seg.is_lower_self_seg ());
699 : : // Ok we didn't find it in the rib, Lets try the prelude...
700 : 1578 : if (!res)
701 : 751 : res = get_lang_prelude (seg_name);
702 : :
703 : 1578 : if (res && !res->is_ambiguous ())
704 : 827 : insert_segment_resolution (segments.back (), res->get_node_id ());
705 : :
706 : 1578 : return res;
707 : 1578 : });
708 : 2187 : cleanup_current ();
709 : 2187 : return res;
710 : 2187 : }
711 : :
712 : : template <Namespace N>
713 : : tl::optional<typename ForeverStack<N>::DfsResult>
714 : : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
715 : : {
716 : : auto values = starting_point.rib.get_values ();
717 : :
718 : : for (auto &kv : values)
719 : : {
720 : : for (auto id : kv.second.ids_shadowable)
721 : : if (id == to_find)
722 : : return {{starting_point, kv.first}};
723 : : for (auto id : kv.second.ids_non_shadowable)
724 : : if (id == to_find)
725 : : return {{starting_point, kv.first}};
726 : : for (auto id : kv.second.ids_globbed)
727 : : if (id == to_find)
728 : : return {{starting_point, kv.first}};
729 : : }
730 : :
731 : : for (auto &child : starting_point.children)
732 : : {
733 : : auto candidate = dfs (child.second, to_find);
734 : :
735 : : if (candidate.has_value ())
736 : : return candidate;
737 : : }
738 : :
739 : : return tl::nullopt;
740 : : }
741 : :
742 : : template <Namespace N>
743 : : tl::optional<typename ForeverStack<N>::ConstDfsResult>
744 : 238940 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
745 : : NodeId to_find) const
746 : : {
747 : 238940 : auto values = starting_point.rib.get_values ();
748 : :
749 : 424214 : for (auto &kv : values)
750 : : {
751 : 266251 : for (auto id : kv.second.ids_shadowable)
752 : 75376 : if (id == to_find)
753 : 0 : return {{starting_point, kv.first}};
754 : 302400 : for (auto id : kv.second.ids_non_shadowable)
755 : 117114 : if (id == to_find)
756 : 11178 : return {{starting_point, kv.first}};
757 : 185310 : for (auto id : kv.second.ids_globbed)
758 : 36 : if (id == to_find)
759 : 24 : return {{starting_point, kv.first}};
760 : : }
761 : :
762 : 466678 : for (auto &child : starting_point.children)
763 : : {
764 : 233339 : auto candidate = dfs (child.second, to_find);
765 : :
766 : 233339 : if (candidate.has_value ())
767 : 3940 : return candidate;
768 : : }
769 : :
770 : 229399 : return tl::nullopt;
771 : 238940 : }
772 : :
773 : : template <Namespace N>
774 : : tl::optional<Resolver::CanonicalPath>
775 : 5601 : ForeverStack<N>::to_canonical_path (NodeId id) const
776 : : {
777 : : // find the id in the current forever stack, starting from the root,
778 : : // performing either a BFS or DFS once the Node containing the ID is found, go
779 : : // back up to the root (parent().parent().parent()...) accumulate link
780 : : // segments reverse them that's your canonical path
781 : :
782 : 6136 : return dfs (root, id).map ([this, id] (ConstDfsResult tuple) {
783 : 5601 : auto containing_node = tuple.first;
784 : 5601 : auto name = tuple.second;
785 : :
786 : 5601 : auto segments = std::vector<Resolver::CanonicalPath> ();
787 : :
788 : 15142 : reverse_iter (containing_node, [&segments] (const Node ¤t) {
789 : 9541 : if (current.is_root ())
790 : : return KeepGoing::No;
791 : :
792 : 3940 : auto children = current.parent.value ().children;
793 : 3940 : const Link *outer_link = nullptr;
794 : :
795 : 33160 : for (auto &kv : children)
796 : : {
797 : 33160 : auto &link = kv.first;
798 : 33160 : auto &child = kv.second;
799 : :
800 : 33160 : if (current.id == child.id)
801 : : {
802 : : outer_link = &link;
803 : : break;
804 : : }
805 : : }
806 : :
807 : 3940 : rust_assert (outer_link);
808 : :
809 : 4420 : outer_link->path.map ([&segments, outer_link] (Identifier path) {
810 : 2124 : segments.emplace (segments.begin (),
811 : 2124 : Resolver::CanonicalPath::new_seg (outer_link->id,
812 : : path.as_string ()));
813 : : });
814 : :
815 : 3940 : return KeepGoing::Yes;
816 : 3940 : });
817 : :
818 : 5601 : auto &mappings = Analysis::Mappings::get ();
819 : 5601 : CrateNum crate_num = mappings.lookup_crate_num (root.id).value ();
820 : 5601 : auto path = Resolver::CanonicalPath::new_seg (
821 : 5601 : root.id, mappings.get_crate_name (crate_num).value ());
822 : 5601 : path.set_crate_num (crate_num);
823 : :
824 : 7725 : for (const auto &segment : segments)
825 : 2124 : path = path.append (segment);
826 : :
827 : : // Finally, append the name
828 : 5601 : path = path.append (Resolver::CanonicalPath::new_seg (id, name));
829 : :
830 : 5601 : return path;
831 : 11202 : });
832 : : }
833 : :
834 : : template <Namespace N>
835 : : tl::optional<Rib &>
836 : 127 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
837 : : {
838 : 127 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
839 : 2 : return x.rib;
840 : 127 : });
841 : : }
842 : :
843 : : template <Namespace N>
844 : : tl::optional<const Rib &>
845 : 2 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
846 : : NodeId to_find) const
847 : : {
848 : 2 : return dfs_node (starting_point, to_find)
849 : 2 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
850 : : }
851 : :
852 : : template <Namespace N>
853 : : tl::optional<typename ForeverStack<N>::Node &>
854 : 127 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
855 : : NodeId to_find)
856 : : {
857 : 127 : if (starting_point.id == to_find)
858 : 2 : return starting_point;
859 : :
860 : 125 : for (auto &child : starting_point.children)
861 : : {
862 : 0 : auto candidate = dfs_node (child.second, to_find);
863 : :
864 : 0 : if (candidate.has_value ())
865 : 0 : return candidate;
866 : : }
867 : :
868 : 125 : return tl::nullopt;
869 : : }
870 : :
871 : : template <Namespace N>
872 : : tl::optional<const typename ForeverStack<N>::Node &>
873 : 139 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
874 : : NodeId to_find) const
875 : : {
876 : 139 : if (starting_point.id == to_find)
877 : 16 : return starting_point;
878 : :
879 : 201 : for (auto &child : starting_point.children)
880 : : {
881 : 111 : auto candidate = dfs_node (child.second, to_find);
882 : :
883 : 111 : if (candidate.has_value ())
884 : 33 : return candidate;
885 : : }
886 : :
887 : 90 : return tl::nullopt;
888 : : }
889 : :
890 : : template <Namespace N>
891 : : tl::optional<Rib &>
892 : : ForeverStack<N>::to_rib (NodeId rib_id)
893 : : {
894 : : return dfs_rib (root, rib_id);
895 : : }
896 : :
897 : : template <Namespace N>
898 : : tl::optional<const Rib &>
899 : 2 : ForeverStack<N>::to_rib (NodeId rib_id) const
900 : : {
901 : 2 : return dfs_rib (root, rib_id);
902 : : }
903 : :
904 : : template <Namespace N>
905 : : void
906 : 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
907 : : const std::string &next,
908 : : const std::string &next_next) const
909 : : {
910 : 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
911 : 0 : stream << next << "rib [" << rib_kind << "]: {";
912 : 0 : if (rib.get_values ().empty ())
913 : : {
914 : 0 : stream << "}\n";
915 : 0 : return;
916 : : }
917 : : else
918 : : {
919 : 0 : stream << "\n";
920 : : }
921 : :
922 : 0 : for (const auto &kv : rib.get_values ())
923 : 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
924 : :
925 : 0 : stream << next << "},\n";
926 : 0 : }
927 : :
928 : : template <Namespace N>
929 : : void
930 : 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
931 : : const ForeverStack<N>::Node &node) const
932 : : {
933 : 0 : auto indent = std::string (indentation, ' ');
934 : 0 : auto next = std::string (indentation + 4, ' ');
935 : 0 : auto next_next = std::string (indentation + 8, ' ');
936 : :
937 : : stream << indent << "Node {\n"
938 : 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
939 : 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
940 : 0 : << ",\n";
941 : :
942 : 0 : stream_rib (stream, node.rib, next, next_next);
943 : :
944 : 0 : stream << indent << "}\n";
945 : :
946 : 0 : for (auto &kv : node.children)
947 : : {
948 : 0 : auto link = kv.first;
949 : 0 : auto child = kv.second;
950 : 0 : stream << indent << "Link (" << link.id << ", "
951 : 0 : << (link.path.has_value () ? link.path.value ().as_string ()
952 : 0 : : "<anon>")
953 : 0 : << "):\n";
954 : :
955 : 0 : stream_node (stream, indentation + 4, child);
956 : :
957 : 0 : stream << '\n';
958 : : }
959 : 0 : }
960 : :
961 : : template <Namespace N>
962 : : std::string
963 : 0 : ForeverStack<N>::as_debug_string () const
964 : : {
965 : 0 : std::stringstream stream;
966 : :
967 : 0 : stream_node (stream, 0, root);
968 : :
969 : 0 : return stream.str ();
970 : 0 : }
971 : :
972 : : template <Namespace N>
973 : : bool
974 : 13 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
975 : : {
976 : 13 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
977 : : }
978 : :
979 : : // FIXME: Can we add selftests?
980 : :
981 : : } // namespace Resolver2_0
982 : : } // namespace Rust
|