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 : 194311 : ForeverStack<N>::Node::is_root () const
34 : : {
35 : 44713 : 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 : 21536 : ForeverStack<N>::Node::is_leaf () const
48 : : {
49 : 21536 : 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 : 139503 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
65 : : tl::optional<Identifier> path)
66 : : {
67 : 301794 : push_inner (rib_kind, Link (id, path));
68 : 139503 : }
69 : :
70 : : template <Namespace N>
71 : : void
72 : 139503 : ForeverStack<N>::push_inner (Rib rib, Link link)
73 : : {
74 : 139503 : 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 : 2736 : rust_assert (&cursor_reference.get () == &root);
79 : : // Prelude doesn't have an access path
80 : 2736 : rust_assert (!link.path);
81 : 2736 : update_cursor (this->lang_prelude);
82 : 2736 : 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 : 273534 : auto emplace = cursor ().children.emplace (
90 : 136767 : std::make_pair (link, Node (rib, link.id, cursor ())));
91 : :
92 : 136767 : auto it = emplace.first;
93 : 136767 : auto existed = !emplace.second;
94 : :
95 : 159597 : 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 : 136767 : update_cursor (it->second);
102 : : }
103 : :
104 : : template <Namespace N>
105 : : void
106 : 139482 : ForeverStack<N>::pop ()
107 : : {
108 : 139482 : rust_assert (!cursor ().is_root ());
109 : :
110 : 139482 : rust_debug ("popping link");
111 : :
112 : 182004 : for (const auto &kv : cursor ().rib.get_values ())
113 : 42522 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
114 : : kv.second.to_string ().c_str ());
115 : :
116 : 139482 : if (cursor ().parent.has_value ())
117 : 285155 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
118 : 145673 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
119 : : kv.second.to_string ().c_str ());
120 : :
121 : 139482 : update_cursor (cursor ().parent.value ());
122 : 139482 : }
123 : :
124 : : static tl::expected<NodeId, DuplicateNameError>
125 : 35859 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
126 : : {
127 : 35859 : return rib.insert (name, definition);
128 : : }
129 : :
130 : : template <Namespace N>
131 : : tl::expected<NodeId, DuplicateNameError>
132 : 32841 : ForeverStack<N>::insert (Identifier name, NodeId node)
133 : : {
134 : 32841 : 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 : 32841 : return insert_inner (innermost_rib, name.as_string (),
141 : 32841 : Rib::Definition::NonShadowable (node));
142 : : }
143 : :
144 : : template <Namespace N>
145 : : tl::expected<NodeId, DuplicateNameError>
146 : 2497 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
147 : : {
148 : 2497 : auto &innermost_rib = peek ();
149 : :
150 : 2497 : return insert_inner (innermost_rib, name.as_string (),
151 : 2497 : Rib::Definition::Shadowable (node));
152 : : }
153 : :
154 : : template <Namespace N>
155 : : tl::expected<NodeId, DuplicateNameError>
156 : 12 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
157 : : {
158 : 12 : auto &innermost_rib = peek ();
159 : :
160 : 12 : return insert_inner (innermost_rib, name.as_string (),
161 : 12 : 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 : 8 : 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 : 59 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
181 : : {
182 : 59 : return insert_inner (peek (), name.as_string (),
183 : 118 : 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 : 415 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
197 : : {
198 : 415 : return insert_inner (peek (), name.as_string (),
199 : 830 : Rib::Definition::NonShadowable (node, true));
200 : : }
201 : :
202 : : template <Namespace N>
203 : : Rib &
204 : 36018 : ForeverStack<N>::peek ()
205 : : {
206 : 36018 : 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 : 10500 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
219 : : {
220 : 21000 : 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 : 10875 : ForeverStack<N>::reverse_iter (Node &start,
234 : : std::function<KeepGoing (Node &)> lambda)
235 : : {
236 : 10875 : auto *tmp = &start;
237 : :
238 : 13886 : while (true)
239 : : {
240 : 24761 : auto keep_going = lambda (*tmp);
241 : 24761 : if (keep_going == KeepGoing::No)
242 : : return;
243 : :
244 : 17755 : if (tmp->is_root ())
245 : : return;
246 : :
247 : 13886 : tmp = &tmp->parent.value ();
248 : : }
249 : : }
250 : :
251 : : template <Namespace N>
252 : : void
253 : 5214 : ForeverStack<N>::reverse_iter (
254 : : const Node &start, std::function<KeepGoing (const Node &)> lambda) const
255 : : {
256 : 5214 : auto *tmp = &start;
257 : :
258 : 3593 : while (true)
259 : : {
260 : 8807 : auto keep_going = lambda (*tmp);
261 : 8807 : if (keep_going == KeepGoing::No)
262 : : return;
263 : :
264 : 3593 : if (tmp->is_root ())
265 : : return;
266 : :
267 : 3593 : tmp = &tmp->parent.value ();
268 : : }
269 : : }
270 : :
271 : : template <Namespace N>
272 : : typename ForeverStack<N>::Node &
273 : 743271 : ForeverStack<N>::cursor ()
274 : : {
275 : 743271 : 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 : 139503 : ForeverStack<N>::update_cursor (Node &new_cursor)
288 : : {
289 : 139503 : cursor_reference = new_cursor;
290 : : }
291 : :
292 : : template <Namespace N>
293 : : tl::optional<Rib::Definition>
294 : 10486 : ForeverStack<N>::get (const Identifier &name)
295 : : {
296 : 10486 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
297 : :
298 : : // TODO: Can we improve the API? have `reverse_iter` return an optional?
299 : 34833 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
300 : 24347 : auto candidate = current.rib.get (name.as_string ());
301 : :
302 : 24347 : return candidate.map_or (
303 : 55322 : [&resolved_definition] (Rib::Definition found) {
304 : 6628 : 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 : 6625 : resolved_definition = found;
311 : :
312 : 6625 : return KeepGoing::No;
313 : : },
314 : : // if there was no candidate, we keep iterating
315 : 24347 : KeepGoing::Yes);
316 : 24347 : });
317 : :
318 : 10486 : return resolved_definition;
319 : : }
320 : :
321 : : template <Namespace N>
322 : : tl::optional<Rib::Definition>
323 : 10 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
324 : : {
325 : 10 : return lang_prelude.rib.get (name.as_string ());
326 : : }
327 : :
328 : : template <Namespace N>
329 : : tl::optional<Rib::Definition>
330 : 3891 : ForeverStack<N>::get_lang_prelude (const std::string &name)
331 : : {
332 : 3891 : 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 : 6207 : is_last (const I &iterator, const C &collection)
366 : : {
367 : 6207 : 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 : 2596 : is_start (const I &iterator, const C &collection)
374 : : {
375 : 4666 : return iterator == collection.begin ();
376 : : }
377 : :
378 : : template <Namespace N>
379 : : typename ForeverStack<N>::Node &
380 : 375 : ForeverStack<N>::find_closest_module (Node &starting_point)
381 : : {
382 : 375 : auto *closest_module = &starting_point;
383 : :
384 : 775 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
385 : 400 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
386 : : {
387 : 375 : closest_module = ¤t;
388 : 375 : return KeepGoing::No;
389 : : }
390 : :
391 : : return KeepGoing::Yes;
392 : : });
393 : :
394 : 375 : 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 : 4398 : check_leading_kw_at_start (const S &segment, bool condition)
402 : : {
403 : 4398 : if (condition)
404 : 10 : rust_error_at (
405 : : segment.get_locus (), ErrorCode::E0433,
406 : : "leading path segment %qs can only be used at the beginning of a path",
407 : 20 : segment.as_string ().c_str ());
408 : :
409 : 4398 : return condition;
410 : : }
411 : :
412 : : // we first need to handle the "starting" segments - `super`, `self` or
413 : : // `crate`. we don't need to do anything for `self` and can just skip it. for
414 : : // `crate`, we need to go back to the root of the current stack. for each
415 : : // `super` segment, we go back to the cursor's parent until we reach the
416 : : // correct one or the root.
417 : : template <Namespace N>
418 : : template <typename S>
419 : : tl::optional<typename std::vector<S>::const_iterator>
420 : 2058 : ForeverStack<N>::find_starting_point (
421 : : const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point,
422 : : std::function<void (const S &, NodeId)> insert_segment_resolution)
423 : : {
424 : 2058 : auto iterator = segments.begin ();
425 : :
426 : 2235 : for (; !is_last (iterator, segments); iterator++)
427 : : {
428 : 2070 : auto &outer_seg = *iterator;
429 : :
430 : 2070 : if (unwrap_segment_get_lang_item (outer_seg).has_value ())
431 : : break;
432 : :
433 : 2070 : auto &seg = unwrap_type_segment (outer_seg);
434 : 2070 : bool is_self_or_crate
435 : 2070 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
436 : :
437 : : // if we're after the first path segment and meet `self` or `crate`, it's
438 : : // an error - we should only be seeing `super` keywords at this point
439 : 2070 : if (check_leading_kw_at_start (seg, !is_start (iterator, segments)
440 : 2070 : && is_self_or_crate))
441 : 2 : return tl::nullopt;
442 : :
443 : 2068 : if (seg.is_crate_path_seg ())
444 : : {
445 : 277 : starting_point = root;
446 : 277 : insert_segment_resolution (outer_seg, starting_point.get ().id);
447 : 277 : iterator++;
448 : : break;
449 : : }
450 : 1791 : if (seg.is_lower_self_seg ())
451 : : {
452 : : // insert segment resolution and exit
453 : 19 : starting_point = find_closest_module (starting_point);
454 : 19 : insert_segment_resolution (outer_seg, starting_point.get ().id);
455 : 19 : iterator++;
456 : : break;
457 : : }
458 : 1949 : if (seg.is_super_path_seg ())
459 : : {
460 : 179 : starting_point = find_closest_module (starting_point);
461 : 179 : if (starting_point.get ().is_root ())
462 : : {
463 : 2 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
464 : : "too many leading %<super%> keywords");
465 : 2 : return tl::nullopt;
466 : : }
467 : :
468 : 177 : starting_point
469 : 177 : = find_closest_module (starting_point.get ().parent.value ());
470 : :
471 : 177 : insert_segment_resolution (outer_seg, starting_point.get ().id);
472 : : continue;
473 : : }
474 : :
475 : : // now we've gone through the allowed `crate`, `self` or leading `super`
476 : : // segments. we can start resolving each segment itself.
477 : : // if we do see another leading segment, then we can error out.
478 : : break;
479 : : }
480 : :
481 : 2054 : return iterator;
482 : : }
483 : :
484 : : template <Namespace N>
485 : : template <typename S>
486 : : tl::optional<typename ForeverStack<N>::Node &>
487 : 2054 : ForeverStack<N>::resolve_segments (
488 : : Node &starting_point, const std::vector<S> &segments,
489 : : typename std::vector<S>::const_iterator iterator,
490 : : std::function<void (const S &, NodeId)> insert_segment_resolution)
491 : : {
492 : 2054 : Node *current_node = &starting_point;
493 : 4382 : for (; !is_last (iterator, segments); iterator++)
494 : : {
495 : 2328 : auto &outer_seg = *iterator;
496 : :
497 : 2328 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
498 : : {
499 : 0 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
500 : 0 : lang_item.value ());
501 : 0 : current_node = &dfs_node (root, seg_id).value ();
502 : :
503 : 0 : insert_segment_resolution (outer_seg, seg_id);
504 : 0 : continue;
505 : 0 : }
506 : :
507 : 2328 : auto &seg = unwrap_type_segment (outer_seg);
508 : 2328 : std::string str = seg.as_string ();
509 : 2328 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
510 : :
511 : : // check that we don't encounter *any* leading keywords afterwards
512 : 4656 : if (check_leading_kw_at_start (seg, seg.is_crate_path_seg ()
513 : 2328 : || seg.is_super_path_seg ()
514 : 4651 : || seg.is_lower_self_seg ()))
515 : 8 : return tl::nullopt;
516 : :
517 : 2320 : tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt;
518 : :
519 : : /*
520 : : * On every iteration this loop either
521 : : *
522 : : * 1. terminates
523 : : *
524 : : * 2. decreases the depth of the node pointed to by current_node until
525 : : * current_node reaches the root
526 : : *
527 : : * 3. If the root node is reached, and we were not able to resolve the
528 : : * segment, we search the prelude rib for the segment, by setting
529 : : * current_node to point to the prelude, and toggling the
530 : : * searched_prelude boolean to true. If current_node is the prelude
531 : : * rib, and searched_prelude is true, we will exit.
532 : : *
533 : : * This ensures termination.
534 : : *
535 : : */
536 : 2320 : bool searched_prelude = false;
537 : : while (true)
538 : : {
539 : : // may set the value of child
540 : 19830 : for (auto &kv : current_node->children)
541 : : {
542 : 16838 : auto &link = kv.first;
543 : :
544 : 33676 : if (link.path.map_or (
545 : 41028 : [&str] (Identifier path) {
546 : 7352 : auto &path_str = path.as_string ();
547 : 7352 : return str == path_str;
548 : : },
549 : 16838 : false))
550 : : {
551 : 1918 : child = kv.second;
552 : : break;
553 : : }
554 : : }
555 : :
556 : 4910 : if (child.has_value ())
557 : : {
558 : : break;
559 : : }
560 : :
561 : : if (N == Namespace::Types)
562 : : {
563 : 1377 : auto rib_lookup = current_node->rib.get (seg.as_string ());
564 : 1377 : if (rib_lookup && !rib_lookup->is_ambiguous ())
565 : : {
566 : 247 : insert_segment_resolution (outer_seg,
567 : : rib_lookup->get_node_id ());
568 : 247 : return tl::nullopt;
569 : : }
570 : 1377 : }
571 : :
572 : 2745 : if (current_node->is_root () && !searched_prelude)
573 : : {
574 : 149 : searched_prelude = true;
575 : 149 : current_node = &lang_prelude;
576 : 149 : continue;
577 : : }
578 : :
579 : 2596 : if (!is_start (iterator, segments)
580 : 2590 : || current_node->rib.kind == Rib::Kind::Module
581 : 5184 : || current_node->is_prelude ())
582 : : {
583 : 155 : return tl::nullopt;
584 : : }
585 : :
586 : 2441 : current_node = ¤t_node->parent.value ();
587 : : }
588 : :
589 : : // if child didn't contain a value
590 : : // the while loop above should have return'd or kept looping
591 : 1918 : current_node = &child.value ();
592 : 1918 : insert_segment_resolution (outer_seg, current_node->id);
593 : : }
594 : :
595 : 1644 : return *current_node;
596 : : }
597 : :
598 : : template <>
599 : : inline tl::optional<Rib::Definition>
600 : 485 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
601 : : std::string &seg_name,
602 : : bool is_lower_self)
603 : : {
604 : 485 : if (is_lower_self)
605 : 38 : return Rib::Definition::NonShadowable (final_node.id);
606 : : else
607 : 447 : return final_node.rib.get (seg_name);
608 : : }
609 : :
610 : : template <Namespace N>
611 : : tl::optional<Rib::Definition>
612 : 1017 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
613 : : bool is_lower_self)
614 : : {
615 : 1017 : return final_node.rib.get (seg_name);
616 : : }
617 : :
618 : : template <Namespace N>
619 : : template <typename S>
620 : : tl::optional<Rib::Definition>
621 : 9678 : ForeverStack<N>::resolve_path (
622 : : const std::vector<S> &segments, bool has_opening_scope_resolution,
623 : : std::function<void (const S &, NodeId)> insert_segment_resolution)
624 : : {
625 : : // TODO: What to do if segments.empty() ?
626 : :
627 : : // handle paths with opening scopes
628 : 9678 : std::function<void (void)> cleanup_current = [] () {};
629 : 9678 : if (has_opening_scope_resolution)
630 : : {
631 : 40 : Node *last_current = &cursor_reference.get ();
632 : 40 : if (get_rust_edition () == Edition::E2015)
633 : 40 : cursor_reference = root;
634 : : else
635 : 0 : cursor_reference = extern_prelude;
636 : : cleanup_current
637 : 80 : = [this, last_current] () { cursor_reference = *last_current; };
638 : : }
639 : :
640 : : // if there's only one segment, we just use `get`
641 : 9678 : if (segments.size () == 1)
642 : : {
643 : 7620 : auto &seg = segments.front ();
644 : 7620 : if (auto lang_item = unwrap_segment_get_lang_item (seg))
645 : : {
646 : 78 : NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
647 : 39 : lang_item.value ());
648 : :
649 : 39 : insert_segment_resolution (seg, seg_id);
650 : 39 : cleanup_current ();
651 : : // TODO: does NonShadowable matter?
652 : 39 : return Rib::Definition::NonShadowable (seg_id);
653 : : }
654 : :
655 : 7581 : tl::optional<Rib::Definition> res
656 : 15162 : = get (unwrap_type_segment (segments.back ()).as_string ());
657 : :
658 : 7581 : if (!res)
659 : 6275 : res = get_lang_prelude (
660 : 6366 : unwrap_type_segment (segments.back ()).as_string ());
661 : :
662 : 7581 : if (res && !res->is_ambiguous ())
663 : 7489 : insert_segment_resolution (segments.back (), res->get_node_id ());
664 : 7581 : cleanup_current ();
665 : 7581 : return res;
666 : 7581 : }
667 : :
668 : 2058 : std::reference_wrapper<Node> starting_point = cursor ();
669 : :
670 : 2058 : auto res
671 : 2058 : = find_starting_point (segments, starting_point, insert_segment_resolution)
672 : 4116 : .and_then (
673 : 4112 : [this, &segments, &starting_point, &insert_segment_resolution] (
674 : : typename std::vector<S>::const_iterator iterator) {
675 : 2054 : return resolve_segments (starting_point.get (), segments, iterator,
676 : 2054 : insert_segment_resolution);
677 : : })
678 : 3702 : .and_then ([this, &segments, &insert_segment_resolution] (
679 : : Node final_node) -> tl::optional<Rib::Definition> {
680 : : // leave resolution within impl blocks to type checker
681 : 1644 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
682 : 142 : return tl::nullopt;
683 : :
684 : 1502 : auto &seg = unwrap_type_segment (segments.back ());
685 : 1502 : std::string seg_name = seg.as_string ();
686 : :
687 : : // assuming this can't be a lang item segment
688 : 1502 : tl::optional<Rib::Definition> res
689 : : = resolve_final_segment (final_node, seg_name,
690 : 1502 : seg.is_lower_self_seg ());
691 : : // Ok we didn't find it in the rib, Lets try the prelude...
692 : 1502 : if (!res)
693 : 708 : res = get_lang_prelude (seg_name);
694 : :
695 : 1502 : if (res && !res->is_ambiguous ())
696 : 794 : insert_segment_resolution (segments.back (), res->get_node_id ());
697 : :
698 : 1502 : return res;
699 : 1502 : });
700 : 2058 : cleanup_current ();
701 : 2058 : return res;
702 : 2058 : }
703 : :
704 : : template <Namespace N>
705 : : tl::optional<typename ForeverStack<N>::DfsResult>
706 : : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
707 : : {
708 : : auto values = starting_point.rib.get_values ();
709 : :
710 : : for (auto &kv : values)
711 : : {
712 : : for (auto id : kv.second.ids_shadowable)
713 : : if (id == to_find)
714 : : return {{starting_point, kv.first}};
715 : : for (auto id : kv.second.ids_non_shadowable)
716 : : if (id == to_find)
717 : : return {{starting_point, kv.first}};
718 : : for (auto id : kv.second.ids_globbed)
719 : : if (id == to_find)
720 : : return {{starting_point, kv.first}};
721 : : }
722 : :
723 : : for (auto &child : starting_point.children)
724 : : {
725 : : auto candidate = dfs (child.second, to_find);
726 : :
727 : : if (candidate.has_value ())
728 : : return candidate;
729 : : }
730 : :
731 : : return tl::nullopt;
732 : : }
733 : :
734 : : template <Namespace N>
735 : : tl::optional<typename ForeverStack<N>::ConstDfsResult>
736 : 199914 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
737 : : NodeId to_find) const
738 : : {
739 : 199914 : auto values = starting_point.rib.get_values ();
740 : :
741 : 384166 : for (auto &kv : values)
742 : : {
743 : 264788 : for (auto id : kv.second.ids_shadowable)
744 : 75322 : if (id == to_find)
745 : 0 : return {{starting_point, kv.first}};
746 : 300037 : for (auto id : kv.second.ids_non_shadowable)
747 : 115779 : if (id == to_find)
748 : 5208 : return {{starting_point, kv.first}};
749 : 184270 : for (auto id : kv.second.ids_globbed)
750 : 18 : if (id == to_find)
751 : 6 : return {{starting_point, kv.first}};
752 : : }
753 : :
754 : 389400 : for (auto &child : starting_point.children)
755 : : {
756 : 194700 : auto candidate = dfs (child.second, to_find);
757 : :
758 : 194700 : if (candidate.has_value ())
759 : 3593 : return candidate;
760 : : }
761 : :
762 : 191107 : return tl::nullopt;
763 : 199914 : }
764 : :
765 : : template <Namespace N>
766 : : tl::optional<Resolver::CanonicalPath>
767 : 5214 : ForeverStack<N>::to_canonical_path (NodeId id) const
768 : : {
769 : : // find the id in the current forever stack, starting from the root,
770 : : // performing either a BFS or DFS once the Node containing the ID is found, go
771 : : // back up to the root (parent().parent().parent()...) accumulate link
772 : : // segments reverse them that's your canonical path
773 : :
774 : 5674 : return dfs (root, id).map ([this, id] (ConstDfsResult tuple) {
775 : 5214 : auto containing_node = tuple.first;
776 : 5214 : auto name = tuple.second;
777 : :
778 : 5214 : auto segments = std::vector<Resolver::CanonicalPath> ();
779 : :
780 : 14021 : reverse_iter (containing_node, [&segments] (const Node ¤t) {
781 : 8807 : if (current.is_root ())
782 : : return KeepGoing::No;
783 : :
784 : 3593 : auto children = current.parent.value ().children;
785 : 3593 : const Link *outer_link = nullptr;
786 : :
787 : 32287 : for (auto &kv : children)
788 : : {
789 : 32287 : auto &link = kv.first;
790 : 32287 : auto &child = kv.second;
791 : :
792 : 32287 : if (current.id == child.id)
793 : : {
794 : : outer_link = &link;
795 : : break;
796 : : }
797 : : }
798 : :
799 : 3593 : rust_assert (outer_link);
800 : :
801 : 3967 : outer_link->path.map ([&segments, outer_link] (Identifier path) {
802 : 1873 : segments.emplace (segments.begin (),
803 : 1873 : Resolver::CanonicalPath::new_seg (outer_link->id,
804 : : path.as_string ()));
805 : : });
806 : :
807 : 3593 : return KeepGoing::Yes;
808 : 3593 : });
809 : :
810 : 5214 : auto &mappings = Analysis::Mappings::get ();
811 : 5214 : CrateNum crate_num = mappings.lookup_crate_num (root.id).value ();
812 : 5214 : auto path = Resolver::CanonicalPath::new_seg (
813 : 5214 : root.id, mappings.get_crate_name (crate_num).value ());
814 : 5214 : path.set_crate_num (crate_num);
815 : :
816 : 7087 : for (const auto &segment : segments)
817 : 1873 : path = path.append (segment);
818 : :
819 : : // Finally, append the name
820 : 5214 : path = path.append (Resolver::CanonicalPath::new_seg (id, name));
821 : :
822 : 5214 : return path;
823 : 10428 : });
824 : : }
825 : :
826 : : template <Namespace N>
827 : : tl::optional<Rib &>
828 : : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
829 : : {
830 : : return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
831 : : return x.rib;
832 : : });
833 : : }
834 : :
835 : : template <Namespace N>
836 : : tl::optional<const Rib &>
837 : 1 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
838 : : NodeId to_find) const
839 : : {
840 : 1 : return dfs_node (starting_point, to_find)
841 : 1 : .map ([] (const Node &x) -> const Rib & { return x.rib; });
842 : : }
843 : :
844 : : template <Namespace N>
845 : : tl::optional<typename ForeverStack<N>::Node &>
846 : 0 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
847 : : NodeId to_find)
848 : : {
849 : 0 : if (starting_point.id == to_find)
850 : 0 : return starting_point;
851 : :
852 : 0 : for (auto &child : starting_point.children)
853 : : {
854 : 0 : auto candidate = dfs_node (child.second, to_find);
855 : :
856 : 0 : if (candidate.has_value ())
857 : 0 : return candidate;
858 : : }
859 : :
860 : 0 : return tl::nullopt;
861 : : }
862 : :
863 : : template <Namespace N>
864 : : tl::optional<const typename ForeverStack<N>::Node &>
865 : 114 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
866 : : NodeId to_find) const
867 : : {
868 : 114 : if (starting_point.id == to_find)
869 : 15 : return starting_point;
870 : :
871 : 156 : for (auto &child : starting_point.children)
872 : : {
873 : 87 : auto candidate = dfs_node (child.second, to_find);
874 : :
875 : 87 : if (candidate.has_value ())
876 : 30 : return candidate;
877 : : }
878 : :
879 : 69 : return tl::nullopt;
880 : : }
881 : :
882 : : template <Namespace N>
883 : : tl::optional<Rib &>
884 : : ForeverStack<N>::to_rib (NodeId rib_id)
885 : : {
886 : : return dfs_rib (root, rib_id);
887 : : }
888 : :
889 : : template <Namespace N>
890 : : tl::optional<const Rib &>
891 : 1 : ForeverStack<N>::to_rib (NodeId rib_id) const
892 : : {
893 : 1 : return dfs_rib (root, rib_id);
894 : : }
895 : :
896 : : template <Namespace N>
897 : : void
898 : 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
899 : : const std::string &next,
900 : : const std::string &next_next) const
901 : : {
902 : 0 : std::string rib_kind = Rib::kind_to_string (rib.kind);
903 : 0 : stream << next << "rib [" << rib_kind << "]: {";
904 : 0 : if (rib.get_values ().empty ())
905 : : {
906 : 0 : stream << "}\n";
907 : 0 : return;
908 : : }
909 : : else
910 : : {
911 : 0 : stream << "\n";
912 : : }
913 : :
914 : 0 : for (const auto &kv : rib.get_values ())
915 : 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
916 : :
917 : 0 : stream << next << "},\n";
918 : 0 : }
919 : :
920 : : template <Namespace N>
921 : : void
922 : 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
923 : : const ForeverStack<N>::Node &node) const
924 : : {
925 : 0 : auto indent = std::string (indentation, ' ');
926 : 0 : auto next = std::string (indentation + 4, ' ');
927 : 0 : auto next_next = std::string (indentation + 8, ' ');
928 : :
929 : : stream << indent << "Node {\n"
930 : 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
931 : 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
932 : 0 : << ",\n";
933 : :
934 : 0 : stream_rib (stream, node.rib, next, next_next);
935 : :
936 : 0 : stream << indent << "}\n";
937 : :
938 : 0 : for (auto &kv : node.children)
939 : : {
940 : 0 : auto link = kv.first;
941 : 0 : auto child = kv.second;
942 : 0 : stream << indent << "Link (" << link.id << ", "
943 : 0 : << (link.path.has_value () ? link.path.value ().as_string ()
944 : : : "<anon>")
945 : 0 : << "):\n";
946 : :
947 : 0 : stream_node (stream, indentation + 4, child);
948 : :
949 : 0 : stream << '\n';
950 : : }
951 : 0 : }
952 : :
953 : : template <Namespace N>
954 : : std::string
955 : 0 : ForeverStack<N>::as_debug_string () const
956 : : {
957 : 0 : std::stringstream stream;
958 : :
959 : 0 : stream_node (stream, 0, root);
960 : :
961 : 0 : return stream.str ();
962 : 0 : }
963 : :
964 : : template <Namespace N>
965 : : bool
966 : 13 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
967 : : {
968 : 13 : return dfs_node (dfs_node (root, parent).value (), child).has_value ();
969 : : }
970 : :
971 : : // FIXME: Can we add selftests?
972 : :
973 : : } // namespace Resolver2_0
974 : : } // namespace Rust
|
