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 : 1721398 : ForeverStack<N>::Node::is_root () const
34 : : {
35 : 225115 : 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 : 17160 : ForeverStack<N>::Node::is_leaf () const
48 : : {
49 : 17160 : 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 : 1477758 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : : tl::optional<Identifier> path)
66 : : {
67 : 2030607 : push_inner (rib_kind, Link (id, path));
68 : 1477758 : }
69 : :
70 : : template <Namespace N>
71 : : void
72 : 1477758 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : : {
74 : 1477758 : 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 : 12858 : rust_assert (&cursor_reference.get () == &root);
79 : : // Prelude doesn't have an access path
80 : 12858 : rust_assert (!link.path);
81 : 12858 : update_cursor (this->lang_prelude);
82 : 12858 : 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 : 2929800 : auto emplace = cursor ().children.emplace (
90 : 1464900 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 : :
92 : 1464900 : auto it = emplace.first;
93 : 1464900 : auto existed = !emplace.second;
94 : :
95 : 1683030 : 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 : 1464900 : update_cursor (it->second);
102 : : }
103 : :
104 : : template <Namespace N>
105 : : void
106 : 1477752 : ForeverStack<N>::pop ()
107 : : {
108 : 1477752 : rust_assert (!cursor ().is_root ());
109 : :
110 : 1477752 : rust_debug ("popping link");
111 : :
112 : 1788767 : for (const auto &kv : cursor ().rib.get_values ())
113 : 311015 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : : kv.second.to_string ().c_str ());
115 : :
116 : 1477752 : if (cursor ().parent.has_value ())
117 : 2852423 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 : 1374671 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : : kv.second.to_string ().c_str ());
120 : :
121 : 1477752 : update_cursor (cursor ().parent.value ());
122 : 1477752 : }
123 : :
124 : : static tl::expected<NodeId, DuplicateNameError>
125 : 259057 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : : {
127 : 518114 : return rib.insert (name, definition);
128 : : }
129 : :
130 : : template <Namespace N>
131 : : tl::expected<NodeId, DuplicateNameError>
132 : 231733 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : : {
134 : 231733 : 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 : 231733 : return insert_inner (innermost_rib, name.as_string (),
141 : 463466 : Rib::Definition::NonShadowable (node));
142 : : }
143 : :
144 : : template <Namespace N>
145 : : tl::expected<NodeId, DuplicateNameError>
146 : 23786 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : : {
148 : 23786 : auto &innermost_rib = peek ();
149 : :
150 : 23786 : return insert_inner (innermost_rib, name.as_string (),
151 : 47572 : Rib::Definition::Shadowable (node));
152 : : }
153 : :
154 : : template <Namespace N>
155 : : tl::expected<NodeId, DuplicateNameError>
156 : 28 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : : {
158 : 28 : auto &innermost_rib = peek ();
159 : :
160 : 28 : return insert_inner (innermost_rib, name.as_string (),
161 : 56 : Rib::Definition::Globbed (node));
162 : : }
163 : :
164 : : template <Namespace N>
165 : : tl::expected<NodeId, DuplicateNameError>
166 : 8 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : : {
168 : 8 : auto &root_rib = root.rib;
169 : :
170 : : // inserting in the root of the crate is never a shadowing operation, even for
171 : : // macros
172 : 8 : return insert_inner (root_rib, name.as_string (),
173 : 16 : 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 : 55 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
189 : : {
190 : 55 : return insert_inner (peek (), name.as_string (),
191 : 110 : Rib::Definition::Shadowable (node));
192 : : }
193 : :
194 : : template <>
195 : : inline tl::expected<NodeId, DuplicateNameError>
196 : 3280 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : : {
198 : 3280 : return insert_inner (peek (), name.as_string (),
199 : 6560 : Rib::Definition::NonShadowable (node, true));
200 : : }
201 : :
202 : : template <Namespace N>
203 : : Rib &
204 : 313816 : ForeverStack<N>::peek ()
205 : : {
206 : 313816 : 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 : 22 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
219 : : {
220 : 44 : 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 : 102026 : ForeverStack<N>::reverse_iter (Node &start,
234 : : std::function<KeepGoing (Node &)> lambda)
235 : : {
236 : 102026 : auto *tmp = &start;
237 : :
238 : 153028 : while (true)
239 : : {
240 : 255054 : auto keep_going = lambda (*tmp);
241 : 255054 : if (keep_going == KeepGoing::No)
242 : : return;
243 : :
244 : 181629 : if (tmp->is_root ())
245 : : return;
246 : :
247 : 153028 : tmp = &tmp->parent.value ();
248 : : }
249 : : }
250 : :
251 : : template <Namespace N>
252 : : void
253 : : ForeverStack<N>::reverse_iter (
254 : : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
255 : : {
256 : : auto *tmp = &start;
257 : :
258 : : while (true)
259 : : {
260 : : auto keep_going = lambda (*tmp);
261 : : if (keep_going == KeepGoing::No)
262 : : return;
263 : :
264 : : if (tmp->is_root ())
265 : : return;
266 : :
267 : : tmp = &tmp->parent.value ();
268 : : }
269 : : }
270 : :
271 : : template <Namespace N>
272 : : typename ForeverStack<N>::Node &
273 : 7810457 : ForeverStack<N>::cursor ()
274 : : {
275 : 7781692 : 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 : 1477758 : ForeverStack<N>::update_cursor (Node &new_cursor)
288 : : {
289 : 1477758 : cursor_reference = new_cursor;
290 : : }
291 : :
292 : : template <Namespace N>
293 : : tl::optional<Rib::Definition>
294 : 96939 : ForeverStack<N>::get (Node &start, const Identifier &name)
295 : : {
296 : 96939 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
297 : :
298 : : // TODO: Can we improve the API? have `reverse_iter` return an optional?
299 : 346836 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
300 : : // we can't reference associated types/functions like this
301 : 249897 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
302 : : return KeepGoing::Yes;
303 : :
304 : 228862 : auto candidate = current.rib.get (name.as_string ());
305 : :
306 : 228862 : return candidate.map_or (
307 : 526070 : [&resolved_definition] (Rib::Definition found) {
308 : 68346 : if (found.is_variant ())
309 : : return KeepGoing::Yes;
310 : : // for most namespaces, we do not need to care about various ribs -
311 : : // they are available from all contexts if defined in the current
312 : : // scope, or an outermore one. so if we do have a candidate, we can
313 : : // return it directly and stop iterating
314 : 68343 : resolved_definition = found;
315 : :
316 : 68343 : return KeepGoing::No;
317 : : },
318 : : // if there was no candidate, we keep iterating
319 : 228862 : KeepGoing::Yes);
320 : 228862 : });
321 : :
322 : 96939 : return resolved_definition;
323 : : }
324 : :
325 : : template <Namespace N>
326 : : tl::optional<Rib::Definition>
327 : 28765 : ForeverStack<N>::get (const Identifier &name)
328 : : {
329 : 28765 : return get (cursor (), name);
330 : : }
331 : :
332 : : template <Namespace N>
333 : : tl::optional<Rib::Definition>
334 : 9 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
335 : : {
336 : 9 : return lang_prelude.rib.get (name.as_string ());
337 : : }
338 : :
339 : : template <Namespace N>
340 : : tl::optional<Rib::Definition>
341 : 34866 : ForeverStack<N>::get_lang_prelude (const std::string &name)
342 : : {
343 : 34866 : return lang_prelude.rib.get (name);
344 : : }
345 : :
346 : : template <>
347 : 22 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
348 : : const Identifier &name)
349 : : {
350 : 22 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
351 : :
352 : 22 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
353 : : // looking up for labels cannot go through function ribs
354 : : // TODO: What other ribs?
355 : 22 : if (current.rib.kind == Rib::Kind::Function)
356 : : return KeepGoing::No;
357 : :
358 : 22 : auto candidate = current.rib.get (name.as_string ());
359 : :
360 : : // FIXME: Factor this in a function with the generic `get`
361 : 22 : return candidate.map_or (
362 : 61 : [&resolved_definition] (Rib::Definition found) {
363 : 17 : resolved_definition = found;
364 : :
365 : 17 : return KeepGoing::No;
366 : : },
367 : 22 : KeepGoing::Yes);
368 : 22 : });
369 : :
370 : 22 : return resolved_definition;
371 : : }
372 : :
373 : : /* Check if an iterator points to the last element */
374 : : template <typename I, typename C>
375 : : static bool
376 : 72925 : is_last (const I &iterator, const C &collection)
377 : : {
378 : 72925 : return iterator + 1 == collection.end ();
379 : : }
380 : :
381 : : /* Check if an iterator points to the start of the collection */
382 : : template <typename I, typename C>
383 : : static bool
384 : 115593 : is_start (const I &iterator, const C &collection)
385 : : {
386 : 140242 : return iterator == collection.begin ();
387 : : }
388 : :
389 : : template <Namespace N>
390 : : typename ForeverStack<N>::Node &
391 : 5065 : ForeverStack<N>::find_closest_module (Node &starting_point)
392 : : {
393 : 5065 : auto *closest_module = &starting_point;
394 : :
395 : 10200 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
396 : 5135 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
397 : : {
398 : 5065 : closest_module = ¤t;
399 : 5065 : return KeepGoing::No;
400 : : }
401 : :
402 : : return KeepGoing::Yes;
403 : : });
404 : :
405 : 5065 : return *closest_module;
406 : : }
407 : :
408 : : /* If a the given condition is met, emit an error about misused leading path
409 : : * segments */
410 : : template <typename S>
411 : : static inline bool
412 : 54669 : check_leading_kw_at_start (std::vector<Error> &collect_errors, const S &segment,
413 : : bool condition)
414 : : {
415 : 54669 : if (condition)
416 : 10 : collect_errors.emplace_back (
417 : 10 : segment.get_locus (), ErrorCode::E0433,
418 : : "%qs in paths can only be used in start position",
419 : 20 : segment.as_string ().c_str ());
420 : :
421 : 54669 : return condition;
422 : : }
423 : :
424 : : // we first need to handle the "starting" segments - `super`, `self` or
425 : : // `crate`. we don't need to do anything for `self` and can just skip it. for
426 : : // `crate`, we need to go back to the root of the current stack. for each
427 : : // `super` segment, we go back to the cursor's parent until we reach the
428 : : // correct one or the root.
429 : : template <Namespace N>
430 : : template <typename S>
431 : : tl::optional<typename std::vector<S>::const_iterator>
432 : 23392 : ForeverStack<N>::find_starting_point (
433 : : const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point,
434 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
435 : : std::vector<Error> &collect_errors)
436 : : {
437 : 23392 : auto iterator = segments.begin ();
438 : :
439 : 25897 : for (; !is_last (iterator, segments); iterator++)
440 : : {
441 : 24649 : auto &outer_seg = *iterator;
442 : :
443 : 24649 : if (unwrap_segment_get_lang_item (outer_seg).has_value ())
444 : : break;
445 : :
446 : 24649 : auto &seg = unwrap_type_segment (outer_seg);
447 : 24649 : bool is_self_or_crate
448 : 24649 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
449 : :
450 : : // if we're after the first path segment and meet `self` or `crate`, it's
451 : : // an error - we should only be seeing `super` keywords at this point
452 : 24649 : if (check_leading_kw_at_start (collect_errors, seg,
453 : 24649 : !is_start (iterator, segments)
454 : 24649 : && is_self_or_crate))
455 : 1 : return tl::nullopt;
456 : :
457 : 24648 : if (seg.is_crate_path_seg ())
458 : : {
459 : 690 : starting_point = root;
460 : 690 : insert_segment_resolution (outer_seg, starting_point.get ().id);
461 : 690 : iterator++;
462 : : break;
463 : : }
464 : 23958 : if (seg.is_lower_self_seg ())
465 : : {
466 : : // insert segment resolution and exit
467 : 23 : starting_point = find_closest_module (starting_point);
468 : 23 : insert_segment_resolution (outer_seg, starting_point.get ().id);
469 : 23 : iterator++;
470 : : break;
471 : : }
472 : 26440 : if (seg.is_super_path_seg ())
473 : : {
474 : 2506 : starting_point = find_closest_module (starting_point);
475 : 2506 : if (starting_point.get ().is_root ())
476 : : {
477 : 1 : collect_errors.emplace_back (
478 : 1 : seg.get_locus (), ErrorCode::E0433,
479 : : "too many leading %<super%> keywords");
480 : 1 : return tl::nullopt;
481 : : }
482 : :
483 : 2505 : starting_point
484 : 2505 : = find_closest_module (starting_point.get ().parent.value ());
485 : :
486 : 2505 : insert_segment_resolution (outer_seg, starting_point.get ().id);
487 : : continue;
488 : : }
489 : :
490 : : // now we've gone through the allowed `crate`, `self` or leading `super`
491 : : // segments. we can start resolving each segment itself.
492 : : // if we do see another leading segment, then we can error out.
493 : : break;
494 : : }
495 : :
496 : 23390 : return iterator;
497 : : }
498 : :
499 : : template <Namespace N>
500 : : template <typename S>
501 : : tl::optional<typename ForeverStack<N>::Node &>
502 : 23390 : ForeverStack<N>::resolve_segments (
503 : : Node &starting_point, const std::vector<S> &segments,
504 : : typename std::vector<S>::const_iterator iterator,
505 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
506 : : std::vector<Error> &collect_errors)
507 : : {
508 : 23390 : Node *current_node = &starting_point;
509 : 53410 : for (; !is_last (iterator, segments); iterator++)
510 : : {
511 : 30020 : auto &outer_seg = *iterator;
512 : :
513 : 30020 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
514 : : {
515 : 0 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
516 : 0 : lang_item.value ());
517 : 0 : current_node = &dfs_node (root, seg_id).value ();
518 : :
519 : 0 : insert_segment_resolution (outer_seg, seg_id);
520 : 0 : continue;
521 : 0 : }
522 : :
523 : 30020 : auto &seg = unwrap_type_segment (outer_seg);
524 : 30020 : std::string str = seg.as_string ();
525 : 30020 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
526 : :
527 : : // check that we don't encounter *any* leading keywords afterwards
528 : 30020 : if (check_leading_kw_at_start (collect_errors, seg,
529 : 30020 : seg.is_crate_path_seg ()
530 : 30020 : || seg.is_super_path_seg ()
531 : 60033 : || seg.is_lower_self_seg ()))
532 : 9 : return tl::nullopt;
533 : :
534 : 30011 : tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt;
535 : :
536 : : /*
537 : : * On every iteration this loop either
538 : : *
539 : : * 1. terminates
540 : : *
541 : : * 2. decreases the depth of the node pointed to by current_node until
542 : : * current_node reaches the root
543 : : *
544 : : * 3. If the root node is reached, and we were not able to resolve the
545 : : * segment, we search the prelude rib for the segment, by setting
546 : : * current_node to point to the prelude, and toggling the
547 : : * searched_prelude boolean to true. If current_node is the prelude
548 : : * rib, and searched_prelude is true, we will exit.
549 : : *
550 : : * This ensures termination.
551 : : *
552 : : */
553 : 30011 : bool searched_prelude = false;
554 : : while (true)
555 : : {
556 : 85671 : if (is_start (iterator, segments)
557 : 76987 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
558 : : {
559 : : // we can't reference associated types/functions like this
560 : 8684 : current_node = ¤t_node->parent.value ();
561 : 8684 : continue;
562 : : }
563 : :
564 : : // may set the value of child
565 : 257618 : for (auto &kv : current_node->children)
566 : : {
567 : 212953 : auto &link = kv.first;
568 : :
569 : 425906 : if (link.path.map_or (
570 : 531044 : [&str] (Identifier path) {
571 : 105138 : auto &path_str = path.as_string ();
572 : 105138 : return str == path_str;
573 : : },
574 : 212953 : false))
575 : : {
576 : 23638 : child = kv.second;
577 : : break;
578 : : }
579 : : }
580 : :
581 : 68303 : if (child.has_value ())
582 : : {
583 : : break;
584 : : }
585 : :
586 : : if (N == Namespace::Types)
587 : : {
588 : 39413 : auto rib_lookup = current_node->rib.get (seg.as_string ());
589 : 19709 : if (rib_lookup && !rib_lookup->is_ambiguous ())
590 : : {
591 : 3685 : insert_segment_resolution (outer_seg,
592 : : rib_lookup->get_node_id ());
593 : 3685 : return tl::nullopt;
594 : : }
595 : 19709 : }
596 : :
597 : 40980 : if (current_node->is_root () && !searched_prelude)
598 : : {
599 : 2374 : searched_prelude = true;
600 : 2374 : current_node = &lang_prelude;
601 : 2374 : continue;
602 : : }
603 : :
604 : 38606 : if (!is_start (iterator, segments)
605 : 38601 : || current_node->rib.kind == Rib::Kind::Module
606 : 76895 : || current_node->is_prelude ())
607 : : {
608 : 2688 : return tl::nullopt;
609 : : }
610 : :
611 : 35918 : current_node = ¤t_node->parent.value ();
612 : : }
613 : :
614 : : // if child didn't contain a value
615 : : // the while loop above should have return'd or kept looping
616 : 23638 : current_node = &child.value ();
617 : 23638 : insert_segment_resolution (outer_seg, current_node->id);
618 : : }
619 : :
620 : 17008 : return *current_node;
621 : : }
622 : :
623 : : template <>
624 : : inline tl::optional<Rib::Definition>
625 : 6217 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
626 : : std::string &seg_name,
627 : : bool is_lower_self)
628 : : {
629 : 6217 : if (is_lower_self)
630 : 204 : return Rib::Definition::NonShadowable (final_node.id);
631 : : else
632 : 6013 : return final_node.rib.get (seg_name);
633 : : }
634 : :
635 : : template <Namespace N>
636 : : tl::optional<Rib::Definition>
637 : 10791 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
638 : : bool is_lower_self)
639 : : {
640 : 10791 : return final_node.rib.get (seg_name);
641 : : }
642 : :
643 : : template <Namespace N>
644 : : template <typename S>
645 : : tl::optional<Rib::Definition>
646 : 91946 : ForeverStack<N>::resolve_path (
647 : : const std::vector<S> &segments, ResolutionMode mode,
648 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
649 : : std::vector<Error> &collect_errors)
650 : : {
651 : 91946 : rust_assert (!segments.empty ());
652 : :
653 : 91946 : std::reference_wrapper<Node> starting_point = cursor ();
654 : 91946 : switch (mode)
655 : : {
656 : : case ResolutionMode::Normal:
657 : : break; // default
658 : 1032 : case ResolutionMode::FromRoot:
659 : 1032 : starting_point = root;
660 : 1032 : break;
661 : 0 : case ResolutionMode::FromExtern:
662 : 0 : starting_point = extern_prelude;
663 : 0 : break;
664 : 0 : default:
665 : 0 : rust_unreachable ();
666 : : }
667 : :
668 : : // if there's only one segment, we just use `get`
669 : 91946 : if (segments.size () == 1)
670 : : {
671 : 68554 : auto &outer_seg = segments.front ();
672 : 68554 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
673 : : {
674 : 760 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
675 : 380 : lang_item.value ());
676 : :
677 : 380 : insert_segment_resolution (outer_seg, seg_id);
678 : : // TODO: does NonShadowable matter?
679 : 380 : return Rib::Definition::NonShadowable (seg_id);
680 : : }
681 : :
682 : 68174 : auto &seg = unwrap_type_segment (outer_seg);
683 : :
684 : 68174 : tl::optional<Rib::Definition> res
685 : 204522 : = get (starting_point.get (), seg.as_string ());
686 : :
687 : 68174 : if (!res)
688 : 50042 : res = get_lang_prelude (seg.as_string ());
689 : :
690 : 53060 : if (N == Namespace::Types && !res)
691 : : {
692 : 83 : if (seg.is_crate_path_seg ())
693 : : {
694 : 53 : insert_segment_resolution (outer_seg, root.id);
695 : : // TODO: does NonShadowable matter?
696 : 53 : return Rib::Definition::NonShadowable (root.id);
697 : : }
698 : 30 : else if (seg.is_lower_self_seg ())
699 : : {
700 : 0 : NodeId id = find_closest_module (starting_point.get ()).id;
701 : 0 : insert_segment_resolution (outer_seg, id);
702 : : // TODO: does NonShadowable matter?
703 : 0 : return Rib::Definition::NonShadowable (id);
704 : : }
705 : 30 : else if (seg.is_super_path_seg ())
706 : : {
707 : : Node &closest_module
708 : 1 : = find_closest_module (starting_point.get ());
709 : 1 : if (closest_module.is_root ())
710 : : {
711 : 0 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
712 : : "too many leading %<super%> keywords");
713 : 0 : return tl::nullopt;
714 : : }
715 : :
716 : 1 : NodeId id
717 : 1 : = find_closest_module (closest_module.parent.value ()).id;
718 : 1 : insert_segment_resolution (outer_seg, id);
719 : : // TODO: does NonShadowable matter?
720 : 1 : return Rib::Definition::NonShadowable (id);
721 : : }
722 : : else
723 : : {
724 : : // HACK: check for a module after we check the language prelude
725 : 140 : for (auto &kv :
726 : 29 : find_closest_module (starting_point.get ()).children)
727 : : {
728 : 116 : auto &link = kv.first;
729 : :
730 : 232 : if (link.path.map_or (
731 : 323 : [&seg] (Identifier path) {
732 : 91 : auto &path_str = path.as_string ();
733 : 174 : return path_str == seg.as_string ();
734 : : },
735 : 116 : false))
736 : : {
737 : 5 : insert_segment_resolution (outer_seg, kv.second.id);
738 : 5 : return Rib::Definition::NonShadowable (kv.second.id);
739 : : }
740 : : }
741 : : }
742 : : }
743 : :
744 : 68115 : if (res && !res->is_ambiguous ())
745 : 67671 : insert_segment_resolution (outer_seg, res->get_node_id ());
746 : 68115 : return res;
747 : 68174 : }
748 : :
749 : 23392 : return find_starting_point (segments, starting_point,
750 : : insert_segment_resolution, collect_errors)
751 : 23392 : .and_then (
752 : 46782 : [this, &segments, &starting_point, &insert_segment_resolution,
753 : : &collect_errors] (typename std::vector<S>::const_iterator iterator) {
754 : 23390 : return resolve_segments (starting_point.get (), segments, iterator,
755 : 23390 : insert_segment_resolution, collect_errors);
756 : : })
757 : 40400 : .and_then ([this, &segments, &insert_segment_resolution] (
758 : : Node &final_node) -> tl::optional<Rib::Definition> {
759 : : // leave resolution within impl blocks to type checker
760 : 17008 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
761 : 0 : return tl::nullopt;
762 : :
763 : 17008 : auto &seg = unwrap_type_segment (segments.back ());
764 : 8918 : std::string seg_name = seg.as_string ();
765 : :
766 : : // assuming this can't be a lang item segment
767 : 17008 : tl::optional<Rib::Definition> res
768 : : = resolve_final_segment (final_node, seg_name,
769 : 17008 : seg.is_lower_self_seg ());
770 : : // Ok we didn't find it in the rib, Lets try the prelude...
771 : 17008 : if (!res)
772 : 9594 : res = get_lang_prelude (seg_name);
773 : :
774 : 6217 : if (N == Namespace::Types && !res)
775 : : {
776 : : // HACK: check for a module after we check the language prelude
777 : 2281 : for (auto &kv : final_node.children)
778 : : {
779 : 1312 : auto &link = kv.first;
780 : :
781 : 2624 : if (link.path.map_or (
782 : 77 : [&seg_name] (Identifier path) {
783 : 77 : auto &path_str = path.as_string ();
784 : 77 : return path_str == seg_name;
785 : : },
786 : 1312 : false))
787 : : {
788 : 49 : insert_segment_resolution (segments.back (), kv.second.id);
789 : 49 : return Rib::Definition::NonShadowable (kv.second.id);
790 : : }
791 : : }
792 : : }
793 : :
794 : 16959 : if (res && !res->is_ambiguous ())
795 : 7414 : insert_segment_resolution (segments.back (), res->get_node_id ());
796 : :
797 : 16959 : return res;
798 : 40400 : });
799 : : }
800 : :
801 : : template <Namespace N>
802 : : tl::optional<typename ForeverStack<N>::DfsResult>
803 : : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
804 : : {
805 : : auto values = starting_point.rib.get_values ();
806 : :
807 : : for (auto &kv : values)
808 : : {
809 : : for (auto id : kv.second.ids_shadowable)
810 : : if (id == to_find)
811 : : return {{starting_point, kv.first}};
812 : : for (auto id : kv.second.ids_non_shadowable)
813 : : if (id == to_find)
814 : : return {{starting_point, kv.first}};
815 : : for (auto id : kv.second.ids_globbed)
816 : : if (id == to_find)
817 : : return {{starting_point, kv.first}};
818 : : }
819 : :
820 : : for (auto &child : starting_point.children)
821 : : {
822 : : auto candidate = dfs (child.second, to_find);
823 : :
824 : : if (candidate.has_value ())
825 : : return candidate;
826 : : }
827 : :
828 : : return tl::nullopt;
829 : : }
830 : :
831 : : template <Namespace N>
832 : : tl::optional<typename ForeverStack<N>::ConstDfsResult>
833 : : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
834 : : NodeId to_find) const
835 : : {
836 : : auto values = starting_point.rib.get_values ();
837 : :
838 : : for (auto &kv : values)
839 : : {
840 : : for (auto id : kv.second.ids_shadowable)
841 : : if (id == to_find)
842 : : return {{starting_point, kv.first}};
843 : : for (auto id : kv.second.ids_non_shadowable)
844 : : if (id == to_find)
845 : : return {{starting_point, kv.first}};
846 : : for (auto id : kv.second.ids_globbed)
847 : : if (id == to_find)
848 : : return {{starting_point, kv.first}};
849 : : }
850 : :
851 : : for (auto &child : starting_point.children)
852 : : {
853 : : auto candidate = dfs (child.second, to_find);
854 : :
855 : : if (candidate.has_value ())
856 : : return candidate;
857 : : }
858 : :
859 : : return tl::nullopt;
860 : : }
861 : :
862 : : template <Namespace N>
863 : : tl::optional<Rib &>
864 : 1285 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
865 : : {
866 : 1285 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
867 : 1 : return x.rib;
868 : 1285 : });
869 : : }
870 : :
871 : : template <Namespace N>
872 : : tl::optional<const Rib &>
873 : 51 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
874 : : NodeId to_find) const
875 : : {
876 : 51 : return dfs_node (starting_point, to_find)
877 : 51 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
878 : : }
879 : :
880 : : template <Namespace N>
881 : : tl::optional<typename ForeverStack<N>::Node &>
882 : 1285 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
883 : : NodeId to_find)
884 : : {
885 : 1285 : if (starting_point.id == to_find)
886 : 1 : return starting_point;
887 : :
888 : 1284 : for (auto &child : starting_point.children)
889 : : {
890 : 0 : auto candidate = dfs_node (child.second, to_find);
891 : :
892 : 0 : if (candidate.has_value ())
893 : 0 : return candidate;
894 : : }
895 : :
896 : 1284 : return tl::nullopt;
897 : : }
898 : :
899 : : template <Namespace N>
900 : : tl::optional<const typename ForeverStack<N>::Node &>
901 : 926 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
902 : : NodeId to_find) const
903 : : {
904 : 926 : if (starting_point.id == to_find)
905 : 67 : return starting_point;
906 : :
907 : 1473 : for (auto &child : starting_point.children)
908 : : {
909 : 847 : auto candidate = dfs_node (child.second, to_find);
910 : :
911 : 847 : if (candidate.has_value ())
912 : 233 : return candidate;
913 : : }
914 : :
915 : 626 : return tl::nullopt;
916 : : }
917 : :
918 : : template <Namespace N>
919 : : tl::optional<Rib &>
920 : : ForeverStack<N>::to_rib (NodeId rib_id)
921 : : {
922 : : return dfs_rib (root, rib_id);
923 : : }
924 : :
925 : : template <Namespace N>
926 : : tl::optional<const Rib &>
927 : 51 : ForeverStack<N>::to_rib (NodeId rib_id) const
928 : : {
929 : 51 : return dfs_rib (root, rib_id);
930 : : }
931 : :
932 : : template <Namespace N>
933 : : void
934 : 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
935 : : const std::string &next,
936 : : const std::string &next_next) const
937 : : {
938 : 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
939 : 0 : stream << next << "rib [" << rib_kind << "]: {";
940 : 0 : if (rib.get_values ().empty ())
941 : : {
942 : 0 : stream << "}\n";
943 : 0 : return;
944 : : }
945 : : else
946 : : {
947 : 0 : stream << "\n";
948 : : }
949 : :
950 : 0 : for (const auto &kv : rib.get_values ())
951 : 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
952 : :
953 : 0 : stream << next << "},\n";
954 : 0 : }
955 : :
956 : : template <Namespace N>
957 : : void
958 : 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
959 : : const ForeverStack<N>::Node &node) const
960 : : {
961 : 0 : auto indent = std::string (indentation, ' ');
962 : 0 : auto next = std::string (indentation + 4, ' ');
963 : 0 : auto next_next = std::string (indentation + 8, ' ');
964 : :
965 : : stream << indent << "Node {\n"
966 : 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
967 : 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
968 : 0 : << ",\n";
969 : :
970 : 0 : stream_rib (stream, node.rib, next, next_next);
971 : :
972 : 0 : stream << indent << "}\n";
973 : :
974 : 0 : for (auto &kv : node.children)
975 : : {
976 : 0 : auto link = kv.first;
977 : 0 : auto child = kv.second;
978 : 0 : stream << indent << "Link (" << link.id << ", "
979 : 0 : << (link.path.has_value () ? link.path.value ().as_string ()
980 : 0 : : "<anon>")
981 : 0 : << "):\n";
982 : :
983 : 0 : stream_node (stream, indentation + 4, child);
984 : :
985 : 0 : stream << '\n';
986 : : }
987 : 0 : }
988 : :
989 : : template <Namespace N>
990 : : std::string
991 : 0 : ForeverStack<N>::as_debug_string () const
992 : : {
993 : 0 : std::stringstream stream;
994 : :
995 : 0 : stream_node (stream, 0, root);
996 : :
997 : 0 : return stream.str ();
998 : 0 : }
999 : :
1000 : : template <Namespace N>
1001 : : bool
1002 : 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
1003 : : {
1004 : 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
1005 : : }
1006 : :
1007 : : // FIXME: Can we add selftests?
1008 : :
1009 : : } // namespace Resolver2_0
1010 : : } // namespace Rust
|
