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 : 13123993 : ForeverStack<N>::Node::is_root () const
34 : : {
35 : 273394 : 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 : 17796 : ForeverStack<N>::Node::is_leaf () const
48 : : {
49 : 17796 : 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 : 12834429 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : : tl::optional<Identifier> path)
66 : : {
67 : 16663023 : push_inner (rib_kind, Link (id, path));
68 : 12834429 : }
69 : :
70 : : template <Namespace N>
71 : : void
72 : 12834429 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : : {
74 : 12834429 : 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 : 13347 : rust_assert (&cursor_reference.get () == &root);
79 : : // Prelude doesn't have an access path
80 : 13347 : rust_assert (!link.path);
81 : 13347 : update_cursor (this->lang_prelude);
82 : 13347 : 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 : 25642164 : auto emplace = cursor ().children.emplace (
90 : 12821082 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 : :
92 : 12821082 : auto it = emplace.first;
93 : 12821082 : auto existed = !emplace.second;
94 : :
95 : 13211268 : 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 : 12821082 : update_cursor (it->second);
102 : : }
103 : :
104 : : template <Namespace N>
105 : : void
106 : 12834423 : ForeverStack<N>::pop ()
107 : : {
108 : 12834423 : rust_assert (!cursor ().is_root ());
109 : :
110 : 12834423 : rust_debug ("popping link");
111 : :
112 : 15659650 : for (const auto &kv : cursor ().rib.get_values ())
113 : 2825227 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : : kv.second.to_string ().c_str ());
115 : :
116 : 12834423 : if (cursor ().parent.has_value ())
117 : 182067283 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 : 169232860 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : : kv.second.to_string ().c_str ());
120 : :
121 : 12834423 : update_cursor (cursor ().parent.value ());
122 : 12834423 : }
123 : :
124 : : static tl::expected<NodeId, DuplicateNameError>
125 : 1593161 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : : {
127 : 3186322 : return rib.insert (name, definition);
128 : : }
129 : :
130 : : template <Namespace N>
131 : : tl::expected<NodeId, DuplicateNameError>
132 : 1373315 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : : {
134 : 1373315 : 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 : 1373315 : return insert_inner (innermost_rib, name.as_string (),
141 : 2746630 : Rib::Definition::NonShadowable (node));
142 : : }
143 : :
144 : : template <Namespace N>
145 : : tl::expected<NodeId, DuplicateNameError>
146 : 24168 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : : {
148 : 24168 : auto &innermost_rib = peek ();
149 : :
150 : 24168 : return insert_inner (innermost_rib, name.as_string (),
151 : 48336 : Rib::Definition::Shadowable (node));
152 : : }
153 : :
154 : : template <Namespace N>
155 : : tl::expected<NodeId, DuplicateNameError>
156 : 185011 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : : {
158 : 185011 : auto &innermost_rib = peek ();
159 : :
160 : 185011 : return insert_inner (innermost_rib, name.as_string (),
161 : 370022 : Rib::Definition::Globbed (node));
162 : : }
163 : :
164 : : template <Namespace N>
165 : : tl::expected<NodeId, DuplicateNameError>
166 : 1271 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
167 : : {
168 : 1271 : auto &root_rib = root.rib;
169 : :
170 : : // inserting in the root of the crate is never a shadowing operation, even for
171 : : // macros
172 : 1271 : return insert_inner (root_rib, name.as_string (),
173 : 2542 : 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 : 2939 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : : {
182 : 2939 : return insert_inner (peek (), name.as_string (),
183 : 5878 : 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 : 6402 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : : {
198 : 6402 : return insert_inner (peek (), name.as_string (),
199 : 12804 : Rib::Definition::NonShadowable (node, true));
200 : : }
201 : :
202 : : template <Namespace N>
203 : : Rib &
204 : 1673219 : ForeverStack<N>::peek ()
205 : : {
206 : 1673219 : 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 : 156189 : ForeverStack<N>::reverse_iter (Node &start,
234 : : std::function<KeepGoing (Node &)> lambda)
235 : : {
236 : 156189 : auto *tmp = &start;
237 : :
238 : 179498 : while (true)
239 : : {
240 : 335687 : auto keep_going = lambda (*tmp);
241 : 335687 : if (keep_going == KeepGoing::No)
242 : : return;
243 : :
244 : 210538 : if (tmp->is_root ())
245 : : return;
246 : :
247 : 179498 : 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 : 66074836 : ForeverStack<N>::cursor ()
274 : : {
275 : 66045568 : 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 : 12834429 : ForeverStack<N>::update_cursor (Node &new_cursor)
288 : : {
289 : 12834429 : cursor_reference = new_cursor;
290 : : }
291 : :
292 : : template <Namespace N>
293 : : tl::optional<Rib::Definition>
294 : 104783 : ForeverStack<N>::get (Node &start, const Identifier &name)
295 : : {
296 : 104783 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
297 : :
298 : : // TODO: Can we improve the API? have `reverse_iter` return an optional?
299 : 388702 : reverse_iter (start, [&resolved_definition, &name] (Node ¤t) {
300 : : // we can't reference associated types/functions like this
301 : 283919 : if (current.rib.kind == Rib::Kind::TraitOrImpl)
302 : : return KeepGoing::Yes;
303 : :
304 : 261596 : auto candidate = current.rib.get (name.as_string ());
305 : :
306 : 261596 : return candidate.map_or (
307 : 596943 : [&resolved_definition] (Rib::Definition found) {
308 : 73751 : 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 : 73748 : resolved_definition = found;
315 : :
316 : 73748 : return KeepGoing::No;
317 : : },
318 : : // if there was no candidate, we keep iterating
319 : 261596 : KeepGoing::Yes);
320 : 261596 : });
321 : :
322 : 104783 : return resolved_definition;
323 : : }
324 : :
325 : : template <Namespace N>
326 : : tl::optional<Rib::Definition>
327 : 29268 : ForeverStack<N>::get (const Identifier &name)
328 : : {
329 : 29268 : return get (cursor (), name);
330 : : }
331 : :
332 : : template <Namespace N>
333 : : tl::optional<Rib::Definition>
334 : 8 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
335 : : {
336 : 8 : return lang_prelude.rib.get (name.as_string ());
337 : : }
338 : :
339 : : template <Namespace N>
340 : : tl::optional<Rib::Definition>
341 : 114089 : ForeverStack<N>::get_lang_prelude (const std::string &name)
342 : : {
343 : 114089 : 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 : 414622 : is_last (const I &iterator, const C &collection)
377 : : {
378 : 414622 : 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 : 217838 : is_start (const I &iterator, const C &collection)
385 : : {
386 : 361627 : return iterator == collection.begin ();
387 : : }
388 : :
389 : : template <Namespace N>
390 : : typename ForeverStack<N>::Node &
391 : 51384 : ForeverStack<N>::find_closest_module (Node &starting_point)
392 : : {
393 : 51384 : auto *closest_module = &starting_point;
394 : :
395 : 103130 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
396 : 51746 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
397 : : {
398 : 51384 : closest_module = ¤t;
399 : 51384 : return KeepGoing::No;
400 : : }
401 : :
402 : : return KeepGoing::Yes;
403 : : });
404 : :
405 : 51384 : 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 : 271791 : check_leading_kw_at_start (std::vector<Error> &collect_errors, const S &segment,
413 : : bool condition)
414 : : {
415 : 271791 : 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 : 271791 : 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 : 137648 : 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 : 137648 : auto iterator = segments.begin ();
438 : :
439 : 153647 : for (; !is_last (iterator, segments); iterator++)
440 : : {
441 : 143789 : auto &outer_seg = *iterator;
442 : :
443 : 143789 : if (unwrap_segment_get_lang_item (outer_seg).has_value ())
444 : : break;
445 : :
446 : 143789 : auto &seg = unwrap_type_segment (outer_seg);
447 : 143789 : bool is_self_or_crate
448 : 143789 : = 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 : 143789 : if (check_leading_kw_at_start (collect_errors, seg,
453 : 143789 : !is_start (iterator, segments)
454 : 143789 : && is_self_or_crate))
455 : 1 : return tl::nullopt;
456 : :
457 : 143788 : if (seg.is_crate_path_seg ())
458 : : {
459 : 73940 : starting_point = root;
460 : 73940 : insert_segment_resolution (outer_seg, starting_point.get ().id);
461 : 73940 : iterator++;
462 : : break;
463 : : }
464 : 69848 : if (seg.is_lower_self_seg ())
465 : : {
466 : : // insert segment resolution and exit
467 : 18993 : starting_point = find_closest_module (starting_point);
468 : 18993 : insert_segment_resolution (outer_seg, starting_point.get ().id);
469 : 18993 : iterator++;
470 : : break;
471 : : }
472 : 66854 : if (seg.is_super_path_seg ())
473 : : {
474 : 16000 : starting_point = find_closest_module (starting_point);
475 : 16000 : 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 : 15999 : starting_point
484 : 15999 : = find_closest_module (starting_point.get ().parent.value ());
485 : :
486 : 15999 : 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 : 137646 : return iterator;
497 : : }
498 : :
499 : : template <Namespace N>
500 : : template <typename S>
501 : : tl::optional<typename ForeverStack<N>::Node &>
502 : 137646 : 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 : 137646 : Node *current_node = &starting_point;
509 : 265648 : for (; !is_last (iterator, segments); iterator++)
510 : : {
511 : 128002 : auto &outer_seg = *iterator;
512 : :
513 : 128002 : 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 : 128002 : auto &seg = unwrap_type_segment (outer_seg);
524 : 128002 : std::string str = seg.as_string ();
525 : 128002 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
526 : :
527 : : // check that we don't encounter *any* leading keywords afterwards
528 : 128002 : if (check_leading_kw_at_start (collect_errors, seg,
529 : 128002 : seg.is_crate_path_seg ()
530 : 128002 : || seg.is_super_path_seg ()
531 : 255997 : || seg.is_lower_self_seg ()))
532 : 9 : return tl::nullopt;
533 : :
534 : 127993 : tl::optional<std::reference_wrapper<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 : 127993 : bool searched_prelude = false;
554 : 47356 : while (true)
555 : : {
556 : 185519 : if (is_start (iterator, segments)
557 : 176825 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
558 : : {
559 : : // we can't reference associated types/functions like this
560 : 8694 : current_node = ¤t_node->parent.value ();
561 : 11068 : continue;
562 : : }
563 : :
564 : : // may set the value of child
565 : 2468919 : for (auto &kv : current_node->children)
566 : : {
567 : 2421563 : auto &link = kv.first;
568 : :
569 : 4843126 : if (link.path.map_or (
570 : 6818079 : [&str] (Identifier path) {
571 : 1974953 : auto &path_str = path.as_string ();
572 : 1974953 : return str == path_str;
573 : : },
574 : 2421563 : false))
575 : : {
576 : 288906 : child = kv.second;
577 : : break;
578 : : }
579 : : }
580 : :
581 : 168131 : if (child.has_value ())
582 : : {
583 : : break;
584 : : }
585 : :
586 : 92181 : auto rib_lookup = current_node->rib.get (seg.as_string ());
587 : 47356 : if (rib_lookup && !rib_lookup->is_ambiguous ())
588 : : {
589 : 3969 : if (Analysis::Mappings::get ()
590 : 3969 : .lookup_glob_container (rib_lookup->get_node_id ())
591 : 3969 : .has_value ())
592 : : {
593 : 2554 : child = dfs_node (root, rib_lookup->get_node_id ()).value ();
594 : : break;
595 : : }
596 : : else
597 : : {
598 : 1415 : insert_segment_resolution (outer_seg,
599 : : rib_lookup->get_node_id ());
600 : 1415 : return tl::nullopt;
601 : : }
602 : : }
603 : :
604 : 43387 : if (current_node->is_root () && !searched_prelude)
605 : : {
606 : 2374 : searched_prelude = true;
607 : 2374 : current_node = &lang_prelude;
608 : : continue;
609 : : }
610 : :
611 : 41013 : if (!is_start (iterator, segments)
612 : 41008 : || current_node->rib.kind == Rib::Kind::Module
613 : 81148 : || current_node->is_prelude ())
614 : : {
615 : 3249 : return tl::nullopt;
616 : : }
617 : :
618 : 37764 : current_node = ¤t_node->parent.value ();
619 : : }
620 : :
621 : : // if child didn't point to a value
622 : : // the while loop above would have returned or kept looping
623 : 123329 : current_node = &child->get ();
624 : 123329 : insert_segment_resolution (outer_seg, current_node->id);
625 : : }
626 : :
627 : 132973 : return *current_node;
628 : : }
629 : :
630 : : template <>
631 : : inline tl::optional<Rib::Definition>
632 : 48261 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
633 : : std::string &seg_name,
634 : : bool is_lower_self)
635 : : {
636 : 48261 : if (is_lower_self)
637 : 1639 : return Rib::Definition::NonShadowable (final_node.id);
638 : : else
639 : 46622 : return final_node.rib.get (seg_name);
640 : : }
641 : :
642 : : template <Namespace N>
643 : : tl::optional<Rib::Definition>
644 : 84712 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
645 : : bool is_lower_self)
646 : : {
647 : 84712 : return final_node.rib.get (seg_name);
648 : : }
649 : :
650 : : template <Namespace N>
651 : : template <typename S>
652 : : tl::optional<Rib::Definition>
653 : 213553 : ForeverStack<N>::resolve_path (
654 : : const std::vector<S> &segments, ResolutionMode mode,
655 : : std::function<void (const S &, NodeId)> insert_segment_resolution,
656 : : std::vector<Error> &collect_errors)
657 : : {
658 : 213553 : rust_assert (!segments.empty ());
659 : :
660 : 213553 : std::reference_wrapper<Node> starting_point = cursor ();
661 : 213553 : switch (mode)
662 : : {
663 : : case ResolutionMode::Normal:
664 : : break; // default
665 : 1036 : case ResolutionMode::FromRoot:
666 : 1036 : starting_point = root;
667 : 1036 : break;
668 : 0 : case ResolutionMode::FromExtern:
669 : 0 : starting_point = extern_prelude;
670 : 0 : break;
671 : 0 : default:
672 : 0 : rust_unreachable ();
673 : : }
674 : :
675 : : // if there's only one segment, we just use `get`
676 : 213553 : if (segments.size () == 1)
677 : : {
678 : 75905 : auto &outer_seg = segments.front ();
679 : 75905 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
680 : : {
681 : 780 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
682 : 390 : lang_item.value ());
683 : :
684 : 390 : insert_segment_resolution (outer_seg, seg_id);
685 : : // TODO: does NonShadowable matter?
686 : 390 : return Rib::Definition::NonShadowable (seg_id);
687 : : }
688 : :
689 : 75515 : auto &seg = unwrap_type_segment (outer_seg);
690 : :
691 : 75515 : tl::optional<Rib::Definition> res
692 : 226545 : = get (starting_point.get (), seg.as_string ());
693 : :
694 : 75515 : if (!res)
695 : 53095 : res = get_lang_prelude (seg.as_string ());
696 : :
697 : 54666 : if (N == Namespace::Types && !res)
698 : : {
699 : 269 : if (seg.is_crate_path_seg ())
700 : : {
701 : 53 : insert_segment_resolution (outer_seg, root.id);
702 : : // TODO: does NonShadowable matter?
703 : 53 : return Rib::Definition::NonShadowable (root.id);
704 : : }
705 : 216 : else if (seg.is_lower_self_seg ())
706 : : {
707 : 5 : NodeId id = find_closest_module (starting_point.get ()).id;
708 : 5 : insert_segment_resolution (outer_seg, id);
709 : : // TODO: does NonShadowable matter?
710 : 5 : return Rib::Definition::NonShadowable (id);
711 : : }
712 : 211 : else if (seg.is_super_path_seg ())
713 : : {
714 : : Node &closest_module
715 : 176 : = find_closest_module (starting_point.get ());
716 : 176 : if (closest_module.is_root ())
717 : : {
718 : 0 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
719 : : "too many leading %<super%> keywords");
720 : 0 : return tl::nullopt;
721 : : }
722 : :
723 : 176 : NodeId id
724 : 176 : = find_closest_module (closest_module.parent.value ()).id;
725 : 176 : insert_segment_resolution (outer_seg, id);
726 : : // TODO: does NonShadowable matter?
727 : 176 : return Rib::Definition::NonShadowable (id);
728 : : }
729 : : else
730 : : {
731 : : // HACK: check for a module after we check the language prelude
732 : 150 : for (auto &kv :
733 : 35 : find_closest_module (starting_point.get ()).children)
734 : : {
735 : 124 : auto &link = kv.first;
736 : :
737 : 248 : if (link.path.map_or (
738 : 345 : [&seg] (Identifier path) {
739 : 97 : auto &path_str = path.as_string ();
740 : 180 : return path_str == seg.as_string ();
741 : : },
742 : 124 : false))
743 : : {
744 : 9 : insert_segment_resolution (outer_seg, kv.second.id);
745 : 9 : return Rib::Definition::NonShadowable (kv.second.id);
746 : : }
747 : : }
748 : : }
749 : : }
750 : :
751 : 75272 : if (res && !res->is_ambiguous ())
752 : 73285 : insert_segment_resolution (outer_seg, res->get_node_id ());
753 : 75272 : return res;
754 : 75515 : }
755 : :
756 : 137648 : return find_starting_point (segments, starting_point,
757 : : insert_segment_resolution, collect_errors)
758 : 137648 : .and_then (
759 : 275294 : [this, &segments, &starting_point, &insert_segment_resolution,
760 : : &collect_errors] (typename std::vector<S>::const_iterator iterator) {
761 : 137646 : return resolve_segments (starting_point.get (), segments, iterator,
762 : 137646 : insert_segment_resolution, collect_errors);
763 : : })
764 : 270621 : .and_then ([this, &segments, &insert_segment_resolution] (
765 : : Node &final_node) -> tl::optional<Rib::Definition> {
766 : : // leave resolution within impl blocks to type checker
767 : 132973 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
768 : 0 : return tl::nullopt;
769 : :
770 : 132973 : auto &seg = unwrap_type_segment (segments.back ());
771 : 122525 : std::string seg_name = seg.as_string ();
772 : :
773 : : // assuming this can't be a lang item segment
774 : 132973 : tl::optional<Rib::Definition> res
775 : : = resolve_final_segment (final_node, seg_name,
776 : 132973 : seg.is_lower_self_seg ());
777 : : // Ok we didn't find it in the rib, Lets try the prelude...
778 : 132973 : if (!res)
779 : 86742 : res = get_lang_prelude (seg_name);
780 : :
781 : 48261 : if (N == Namespace::Types && !res)
782 : : {
783 : : // HACK: check for a module after we check the language prelude
784 : 400020 : for (auto &kv : final_node.children)
785 : : {
786 : 397363 : auto &link = kv.first;
787 : :
788 : 794726 : if (link.path.map_or (
789 : 367804 : [&seg_name] (Identifier path) {
790 : 367804 : auto &path_str = path.as_string ();
791 : 367804 : return path_str == seg_name;
792 : : },
793 : 397363 : false))
794 : : {
795 : 11804 : insert_segment_resolution (segments.back (), kv.second.id);
796 : 11804 : return Rib::Definition::NonShadowable (kv.second.id);
797 : : }
798 : : }
799 : : }
800 : :
801 : 121169 : if (res && !res->is_ambiguous ())
802 : 46861 : insert_segment_resolution (segments.back (), res->get_node_id ());
803 : :
804 : 121169 : return res;
805 : 270621 : });
806 : : }
807 : :
808 : : template <Namespace N>
809 : : tl::optional<typename ForeverStack<N>::DfsResult>
810 : : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
811 : : {
812 : : auto values = starting_point.rib.get_values ();
813 : :
814 : : for (auto &kv : values)
815 : : {
816 : : for (auto id : kv.second.ids_shadowable)
817 : : if (id == to_find)
818 : : return {{starting_point, kv.first}};
819 : : for (auto id : kv.second.ids_non_shadowable)
820 : : if (id == to_find)
821 : : return {{starting_point, kv.first}};
822 : : for (auto id : kv.second.ids_globbed)
823 : : if (id == to_find)
824 : : return {{starting_point, kv.first}};
825 : : }
826 : :
827 : : for (auto &child : starting_point.children)
828 : : {
829 : : auto candidate = dfs (child.second, to_find);
830 : :
831 : : if (candidate.has_value ())
832 : : return candidate;
833 : : }
834 : :
835 : : return tl::nullopt;
836 : : }
837 : :
838 : : template <Namespace N>
839 : : tl::optional<typename ForeverStack<N>::ConstDfsResult>
840 : : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
841 : : NodeId to_find) const
842 : : {
843 : : auto values = starting_point.rib.get_values ();
844 : :
845 : : for (auto &kv : values)
846 : : {
847 : : for (auto id : kv.second.ids_shadowable)
848 : : if (id == to_find)
849 : : return {{starting_point, kv.first}};
850 : : for (auto id : kv.second.ids_non_shadowable)
851 : : if (id == to_find)
852 : : return {{starting_point, kv.first}};
853 : : for (auto id : kv.second.ids_globbed)
854 : : if (id == to_find)
855 : : return {{starting_point, kv.first}};
856 : : }
857 : :
858 : : for (auto &child : starting_point.children)
859 : : {
860 : : auto candidate = dfs (child.second, to_find);
861 : :
862 : : if (candidate.has_value ())
863 : : return candidate;
864 : : }
865 : :
866 : : return tl::nullopt;
867 : : }
868 : :
869 : : template <Namespace N>
870 : : tl::optional<Rib &>
871 : 1297 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
872 : : {
873 : 1297 : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
874 : 1 : return x.rib;
875 : 1297 : });
876 : : }
877 : :
878 : : template <Namespace N>
879 : : tl::optional<const Rib &>
880 : 52 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
881 : : NodeId to_find) const
882 : : {
883 : 52 : return dfs_node (starting_point, to_find)
884 : 52 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
885 : : }
886 : :
887 : : template <Namespace N>
888 : : tl::optional<typename ForeverStack<N>::Node &>
889 : 3144809 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
890 : : NodeId to_find)
891 : : {
892 : 3144809 : if (starting_point.id == to_find)
893 : 2555 : return starting_point;
894 : :
895 : 6276608 : for (auto &child : starting_point.children)
896 : : {
897 : 3140958 : auto candidate = dfs_node (child.second, to_find);
898 : :
899 : 3140958 : if (candidate.has_value ())
900 : 6604 : return candidate;
901 : : }
902 : :
903 : 3135650 : return tl::nullopt;
904 : : }
905 : :
906 : : template <Namespace N>
907 : : tl::optional<const typename ForeverStack<N>::Node &>
908 : 939 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
909 : : NodeId to_find) const
910 : : {
911 : 939 : if (starting_point.id == to_find)
912 : 68 : return starting_point;
913 : :
914 : 1493 : for (auto &child : starting_point.children)
915 : : {
916 : 859 : auto candidate = dfs_node (child.second, to_find);
917 : :
918 : 859 : if (candidate.has_value ())
919 : 237 : return candidate;
920 : : }
921 : :
922 : 634 : return tl::nullopt;
923 : : }
924 : :
925 : : template <Namespace N>
926 : : tl::optional<Rib &>
927 : : ForeverStack<N>::to_rib (NodeId rib_id)
928 : : {
929 : : return dfs_rib (root, rib_id);
930 : : }
931 : :
932 : : template <Namespace N>
933 : : tl::optional<const Rib &>
934 : 52 : ForeverStack<N>::to_rib (NodeId rib_id) const
935 : : {
936 : 52 : return dfs_rib (root, rib_id);
937 : : }
938 : :
939 : : template <Namespace N>
940 : : void
941 : 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
942 : : const std::string &next,
943 : : const std::string &next_next) const
944 : : {
945 : 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
946 : 0 : stream << next << "rib [" << rib_kind << "]: {";
947 : 0 : if (rib.get_values ().empty ())
948 : : {
949 : 0 : stream << "}\n";
950 : 0 : return;
951 : : }
952 : : else
953 : : {
954 : 0 : stream << "\n";
955 : : }
956 : :
957 : 0 : for (const auto &kv : rib.get_values ())
958 : 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
959 : :
960 : 0 : stream << next << "},\n";
961 : 0 : }
962 : :
963 : : template <Namespace N>
964 : : void
965 : 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
966 : : const ForeverStack<N>::Node &node) const
967 : : {
968 : 0 : auto indent = std::string (indentation, ' ');
969 : 0 : auto next = std::string (indentation + 4, ' ');
970 : 0 : auto next_next = std::string (indentation + 8, ' ');
971 : :
972 : : stream << indent << "Node {\n"
973 : 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
974 : 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
975 : 0 : << ",\n";
976 : :
977 : 0 : stream_rib (stream, node.rib, next, next_next);
978 : :
979 : 0 : stream << indent << "}\n";
980 : :
981 : 0 : for (auto &kv : node.children)
982 : : {
983 : 0 : auto link = kv.first;
984 : 0 : auto child = kv.second;
985 : 0 : stream << indent << "Link (" << link.id << ", "
986 : 0 : << (link.path.has_value () ? link.path.value ().as_string ()
987 : 0 : : "<anon>")
988 : 0 : << "):\n";
989 : :
990 : 0 : stream_node (stream, indentation + 4, child);
991 : :
992 : 0 : stream << '\n';
993 : : }
994 : 0 : }
995 : :
996 : : template <Namespace N>
997 : : std::string
998 : 0 : ForeverStack<N>::as_debug_string () const
999 : : {
1000 : 0 : std::stringstream stream;
1001 : :
1002 : 0 : stream_node (stream, 0, root);
1003 : :
1004 : 0 : return stream.str ();
1005 : 0 : }
1006 : :
1007 : : template <Namespace N>
1008 : : bool
1009 : 14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
1010 : : {
1011 : 14 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
1012 : : }
1013 : :
1014 : : // FIXME: Can we add selftests?
1015 : :
1016 : : } // namespace Resolver2_0
1017 : : } // namespace Rust
|
