Line data Source code
1 : // Copyright (C) 2020-2026 Free Software Foundation, Inc.
2 :
3 : // This file is part of GCC.
4 :
5 : // GCC is free software; you can redistribute it and/or modify it under
6 : // the terms of the GNU General Public License as published by the Free
7 : // Software Foundation; either version 3, or (at your option) any later
8 : // version.
9 :
10 : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
11 : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 : // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 : // for more details.
14 :
15 : // You should have received a copy of the GNU General Public License
16 : // along with GCC; see the file COPYING3. If not see
17 : // <http://www.gnu.org/licenses/>.
18 :
19 : #ifndef RUST_FOREVER_STACK_H
20 : #define RUST_FOREVER_STACK_H
21 :
22 : #include "rust-system.h"
23 : #include "rust-rib.h"
24 : #include "rust-ast.h"
25 : #include "rust-path.h"
26 : #include "optional.h"
27 : #include "expected.h"
28 : #include "rust-name-resolution.h"
29 : #include "rust-unwrap-segment.h"
30 :
31 : namespace Rust {
32 : namespace Resolver2_0 {
33 :
34 : /**
35 :
36 : Let's look at our stack for resolving and traversing the following Rust code:
37 :
38 : ```rust
39 : mod foo {
40 : mod bar {
41 : fn outer() {
42 : fn inner() {}
43 : }
44 :
45 : fn another() {}
46 : }
47 : }
48 : ```
49 :
50 : We start by creating the stack, which contains only one rib - the crate's. We
51 : won't look in details on how different namespaces end up with different stacks,
52 : and will only consider the "value" namespace for this example. Modules do not
53 : get added to the value namespace, but functions do:
54 :
55 : ```rust
56 : let _ = foo; // foo is a module, invalid Rust code
57 : let _ = outer; // outer is a function, ok!
58 : ```
59 :
60 : So passing each module will create a new Rib, but not add that module's node to
61 : the Rib.
62 :
63 : The current cursor of the stack will be denoted with `-->`: an arrow pointing to
64 : the current rib.
65 :
66 : When we start the `TopLevel` pass on the crate we are compiling, we only see the
67 : top rib, which is empty at first:
68 :
69 : ┌───────────────┐
70 : │ │
71 : --> │ │
72 : │ │
73 : └───────────────┘
74 :
75 : We pass through our first module, and emplace another Rib: Another "scope" is
76 : created, and it impacts name resolution rules.
77 :
78 : ┌───────────────┐
79 : │ │
80 : │ │
81 : │ │
82 : └───────┬───────┘
83 : │
84 : foo │
85 : │
86 : ▼
87 : ┌───────────────┐
88 : │ │
89 : --> │ │
90 : │ │
91 : └───────────────┘
92 :
93 : Notice that we have moved the cursor to the newly-created Rib, and that we have
94 : added a path between the two ribs - this is a `Link`. A link contains
95 : information such as the scope's NodeId, as well as an optional path - present
96 : only when the scope is named. This allows us to easily fetch AST nodes based on
97 : their canonical path, or build a canonical path from a NodeId. It also makes it
98 : really easy to do complex path name resolution, such as `super::super::<item>`.
99 : As mentioned earlier, modules are not present in the value namespace, so our new
100 : rib is also empty. Let's pass through the second module:
101 :
102 : ┌───────────────┐
103 : │ │
104 : │ │
105 : │ │
106 : └───────┬───────┘
107 : │
108 : foo │
109 : │
110 : ▼
111 : ┌───────────────┐
112 : │ │
113 : │ │
114 : │ │
115 : └───────┬───────┘
116 : │
117 : bar │
118 : │
119 : ▼
120 : ┌───────────────┐
121 : │ │
122 : --> │ │
123 : │ │
124 : └───────────────┘
125 :
126 : Once again, the new rib is empty, and we have a link with a path. We now go
127 : through each item in the `bar` module and visit them. The first item is a
128 : function, `outer` - upon being visited, it adds itself to the current rib.
129 :
130 : ┌───────────────┐
131 : │ │
132 : │ │
133 : │ │
134 : └───────┬───────┘
135 : │
136 : foo │
137 : │
138 : ▼
139 : ┌───────────────┐
140 : │ │
141 : │ │
142 : │ │
143 : └───────┬───────┘
144 : │
145 : bar │
146 : │
147 : ▼
148 : ┌───────────────┐
149 : │outer │
150 : --> │ │
151 : │ │
152 : └───────────────┘
153 :
154 : We now visit `outer`'s definition. This creates a new Rib, as functions can have
155 : arguments, whose declaration only lives for the function's scope.
156 :
157 : ┌───────────────┐
158 : │ │
159 : │ │
160 : │ │
161 : └───────┬───────┘
162 : │
163 : foo │
164 : │
165 : ▼
166 : ┌───────────────┐
167 : │ │
168 : │ │
169 : │ │
170 : └───────┬───────┘
171 : │
172 : bar │
173 : │
174 : ▼
175 : ┌───────────────┐
176 : │outer │
177 : │ │
178 : │ │
179 : └───────┬───────┘
180 : │
181 : <anon> │
182 : │
183 : ▼
184 : ┌───────────────┐
185 : │ │
186 : --> │ │
187 : │ │
188 : └───────────────┘
189 :
190 : This rib is anonymous (the link to it does not have a path), because we cannot
191 : refer to a function's inner items from the outside:
192 :
193 : ```rust
194 : pub mod a {
195 : pub fn foo() {}
196 : }
197 :
198 : pub fn b() {
199 : pub fn foo() {}
200 : }
201 :
202 : fn main() {
203 : a::foo(); // ok
204 : b::foo(); // ko!
205 : }
206 : ```
207 :
208 : We visit the function's block, which contain a single declaration, a function
209 : named `inner`. It adds itself to the current rib.
210 :
211 : ┌───────────────┐
212 : │ │
213 : │ │
214 : │ │
215 : └───────┬───────┘
216 : │
217 : foo │
218 : │
219 : ▼
220 : ┌───────────────┐
221 : │ │
222 : │ │
223 : │ │
224 : └───────┬───────┘
225 : │
226 : bar │
227 : │
228 : ▼
229 : ┌───────────────┐
230 : │outer │
231 : │ │
232 : │ │
233 : └───────┬───────┘
234 : │
235 : <anon> │
236 : │
237 : ▼
238 : ┌───────────────┐
239 : │inner │
240 : --> │ │
241 : │ │
242 : └───────────────┘
243 :
244 : We visit `inner`, which yields a rib but no other declaration.
245 :
246 : ┌───────────────┐
247 : │ │
248 : │ │
249 : │ │
250 : └───────┬───────┘
251 : │
252 : foo │
253 : │
254 : ▼
255 : ┌───────────────┐
256 : │ │
257 : │ │
258 : │ │
259 : └───────┬───────┘
260 : │
261 : bar │
262 : │
263 : ▼
264 : ┌───────────────┐
265 : │outer │
266 : │ │
267 : │ │
268 : └───────┬───────┘
269 : │
270 : <anon> │
271 : │
272 : ▼
273 : ┌───────────────┐
274 : │inner │
275 : │ │
276 : │ │
277 : └───────────────┘
278 : │
279 : <anon> │
280 : │
281 : ▼
282 : ┌───────────────┐
283 : │ │
284 : --> │ │
285 : │ │
286 : └───────────────┘
287 :
288 : We are now at the end of the `inner` function, and we want to pop the current
289 : scope. Instead of deleting the current rib, we simply move the cursor backwards.
290 : This allows us to keep track of the existing information and access it in later
291 : name resolution passes. We then finish visiting `outer`, then go back to our
292 : `bar` module. This is what our stack looks like after this. Note how the only
293 : difference is the cursor's location.
294 :
295 : ┌───────────────┐
296 : │ │
297 : │ │
298 : │ │
299 : └───────┬───────┘
300 : │
301 : foo │
302 : │
303 : ▼
304 : ┌───────────────┐
305 : │ │
306 : │ │
307 : │ │
308 : └───────┬───────┘
309 : │
310 : bar │
311 : │
312 : ▼
313 : ┌───────────────┐
314 : │outer │
315 : --> │ │
316 : │ │
317 : └───────┬───────┘
318 : │
319 : <anon> │
320 : │
321 : ▼
322 : ┌───────────────┐
323 : │inner │
324 : │ │
325 : │ │
326 : └───────────────┘
327 : │
328 : <anon> │
329 : │
330 : ▼
331 : ┌───────────────┐
332 : │ │
333 : │ │
334 : │ │
335 : └───────────────┘
336 :
337 : We then visit the remaining `bar` items, which are composed of the `another`
338 : function. It adds itself to the current rib. This function contains no
339 : declarations, but it still creates a Rib upon being visited. We then finish our
340 : visit of `bar`, which marks the end of our visit of `foo`, which marks the end
341 : of our `TopLevel` name resolution pass.
342 :
343 : ┌───────────────┐
344 : │ │
345 : --> │ │
346 : │ │
347 : └───────┬───────┘
348 : │
349 : foo │
350 : │
351 : ▼
352 : ┌───────────────┐
353 : │ │
354 : │ │
355 : │ │
356 : └───────┬───────┘
357 : │
358 : bar │
359 : │
360 : ▼
361 : ┌───────────────┐
362 : │outer │
363 : │another │
364 : │ │
365 : └───────┬──┬────┘
366 : │ │ <anon>
367 : <anon> │ └────────────────────┐
368 : │ │
369 : ▼ ▼
370 : ┌───────────────┐ ┌───────────────┐
371 : │inner │ │ │
372 : │ │ │ │
373 : │ │ │ │
374 : └───────┬───────┘ └───────────────┘
375 : │
376 : <anon> │
377 : │
378 : ▼
379 : ┌───────────────┐
380 : │ │
381 : │ │
382 : │ │
383 : └───────────────┘
384 :
385 : We now have a stack with a lot of ribs, prime for the `Early` and `Late` name
386 : resolution passes. We will revisit the ribs we created in these passes, and we
387 : won't need to allocate or create new ones: because they will still be present in
388 : the stack, we will simply move our cursor to these ribs. In this case, there is
389 : nothing to do, since there are no uses of our definitions, as the Rust code we
390 : are name-resolving is not really interesting. You'll also note that our
391 : `TopLevel` pass did not resolve a whole lot: all it did was create new ribs, and
392 : empty ones at that. The `Early` pass will not go further, since our code does
393 : not contain any imports, macro definitions or macro invocations. You can look at
394 : this pass's documentation for more details on this resolution process.
395 :
396 : **/
397 :
398 : enum class ResolutionMode
399 : {
400 : Normal,
401 : FromRoot,
402 : FromExtern, // extern prelude
403 : };
404 :
405 4105614 : struct ResolutionPathSegment
406 : {
407 : std::string name;
408 : NodeId node_id;
409 : location_t locus;
410 :
411 952686 : bool is_super_path_seg () const { return name.compare ("super") == 0; }
412 1855103 : bool is_crate_path_seg () const { return name.compare ("crate") == 0; }
413 1615476 : bool is_lower_self_seg () const { return name.compare ("self") == 0; }
414 : bool is_big_self_seg () const { return name.compare ("Self") == 0; }
415 : };
416 :
417 3129096 : class ResolutionPath : public RawPath<ResolutionPathSegment>
418 : {
419 : public:
420 : template <typename T>
421 1564548 : ResolutionPath (const RawPath<T> &path, NodeId node_id)
422 1564548 : : RawPath ({}, path.has_opening_scope_resolution ()), node_id (node_id)
423 : {
424 1564548 : segments.clear ();
425 1564548 : segments.reserve (path.get_segments ().size ());
426 3624585 : for (auto &outer_seg : path.get_segments ())
427 : {
428 2060037 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
429 : {
430 7230 : rust_assert (!lang_prefix.has_value ());
431 7230 : lang_prefix = std::make_pair (lang_item.value (),
432 7230 : unwrap_segment_node_id (outer_seg));
433 7230 : continue;
434 : }
435 :
436 2052807 : auto &seg = unwrap_type_segment (outer_seg);
437 :
438 2052807 : ResolutionPathSegment new_seg;
439 2052807 : new_seg.name = seg.as_string ();
440 2052807 : new_seg.node_id = unwrap_segment_node_id (outer_seg);
441 2052807 : new_seg.locus = seg.get_locus ();
442 2052807 : segments.push_back (std::move (new_seg));
443 : }
444 1564548 : }
445 :
446 1564548 : ResolutionPath () : RawPath ({}, false), node_id (UNKNOWN_NODEID) {}
447 :
448 1819626 : tl::optional<std::pair<LangItem::Kind, NodeId>> get_lang_prefix () const
449 : {
450 1819626 : return lang_prefix;
451 : }
452 :
453 : const std::vector<ResolutionPathSegment> &get_segments () const
454 : {
455 1819626 : return segments;
456 : }
457 :
458 : bool has_opening_scope_resolution () const
459 : {
460 : return opening_scope_resolution;
461 : }
462 :
463 : NodeId get_node_id () const { return node_id; }
464 :
465 0 : std::string as_string () const
466 : {
467 0 : std::string ret;
468 0 : auto it = segments.cbegin ();
469 0 : if (lang_prefix)
470 0 : ret = "#[lang]";
471 : else
472 : {
473 0 : ret += it->name;
474 0 : it++;
475 : }
476 :
477 0 : for (; it != segments.cend (); it++)
478 0 : ret += "::" + it->name;
479 0 : return ret;
480 : }
481 :
482 : private:
483 : tl::optional<std::pair<LangItem::Kind, NodeId>> lang_prefix;
484 : NodeId node_id;
485 : };
486 :
487 : /**
488 : * Error enum for finding leaf definitions in the resolved_nodes map
489 : */
490 : enum class LookupFinalizeError
491 : {
492 : // Impossible - we did not find any definition corresponding to a Usage.
493 : // This is an internal compiler error
494 : NoDefinition,
495 : // There was a loop in the map, such as an import resolving to another
496 : // import which eventually resolved to the original import. Report the
497 : // error and stop the pipeline
498 : Loop,
499 : };
500 :
501 : class ForeverStackBase
502 : {
503 : public:
504 : /**
505 : * A link between two Nodes in our trie data structure. This class represents
506 : * the edges of the graph
507 : */
508 703167606 : class Link
509 : {
510 : public:
511 231573088 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
512 :
513 1323833102 : bool compare (const Link &other) const { return id < other.id; }
514 :
515 : NodeId id;
516 : tl::optional<Identifier> path;
517 : };
518 :
519 : /* Link comparison class, which we use in a Node's `children` map */
520 : class LinkCmp
521 : {
522 : public:
523 1323833102 : bool operator() (const Link &lhs, const Link &rhs) const
524 : {
525 1323833102 : return lhs.compare (rhs);
526 : }
527 : };
528 :
529 : class Node
530 : {
531 : public:
532 10668 : Node (Rib::Kind rib_kind, NodeId id)
533 10668 : : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
534 10668 : rib_macros (rib_kind), id (id)
535 10668 : {}
536 231557086 : Node (Rib::Kind rib_kind, NodeId id, Node &parent)
537 231557086 : : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
538 231557086 : rib_macros (rib_kind), id (id), parent (parent)
539 231557086 : {}
540 :
541 548644020 : const Rib &rib (Namespace n) const
542 : {
543 548203823 : switch (n)
544 : {
545 185632961 : case Namespace::Values:
546 185632961 : return rib_values;
547 130150234 : case Namespace::Types:
548 130150234 : return rib_types;
549 115980597 : case Namespace::Labels:
550 115980597 : return rib_labels;
551 116880228 : case Namespace::Macros:
552 116880228 : return rib_macros;
553 0 : default:
554 0 : rust_unreachable ();
555 : }
556 : }
557 :
558 548203823 : Rib &rib (Namespace n)
559 : {
560 547803638 : return const_cast<Rib &> (const_cast<const Node *> (this)->rib (n));
561 : }
562 :
563 : inline bool is_root () const;
564 : inline bool is_prelude () const;
565 : inline bool is_leaf () const;
566 :
567 : inline void insert_child (Link link, Node child);
568 :
569 : // these are the "values" of the node - the data it keeps.
570 : Rib rib_values;
571 : Rib rib_types;
572 : Rib rib_labels;
573 : Rib rib_macros;
574 :
575 : std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
576 :
577 : NodeId id; // The node id of the Node's scope
578 :
579 : tl::optional<Node &> parent; // `None` only if the node is a root
580 : };
581 :
582 21336 : ForeverStackBase (Node &root, Node &lang_prelude, Node &extern_prelude)
583 21336 : : root (root), lang_prelude (lang_prelude), extern_prelude (extern_prelude)
584 : {}
585 :
586 : /* The forever stack's actual nodes */
587 : Node &root;
588 :
589 : /*
590 : * A special prelude node used currently for resolving language builtins
591 : * It has the root node as a parent, and acts as a "special case" for name
592 : * resolution
593 : */
594 : Node &lang_prelude;
595 :
596 : /*
597 : * The extern prelude, used for resolving external crates
598 : */
599 : Node &extern_prelude;
600 : };
601 :
602 : template <Namespace N> class ForeverStack : public ForeverStackBase
603 : {
604 : public:
605 21336 : ForeverStack (Node &root, Node &lang_prelude, Node &extern_prelude)
606 : : ForeverStackBase (root, lang_prelude, extern_prelude),
607 21336 : cursor_reference (root)
608 : {
609 21336 : rust_assert (root.is_root ());
610 21336 : rust_assert (root.is_leaf ());
611 :
612 : // TODO: Should we be using the forever stack root as the crate scope?
613 : // TODO: Is this how we should be getting the crate node id?
614 21336 : auto &mappings = Analysis::Mappings::get ();
615 21336 : auto &crate_mappings = mappings.crate;
616 21336 : root.id = *crate_mappings.crate_num_to_nodeid (
617 21336 : crate_mappings.get_current_crate ());
618 21336 : extern_prelude.id = mappings.get_next_node_id ();
619 21336 : lang_prelude.id = mappings.get_next_node_id ();
620 21336 : }
621 :
622 : /**
623 : * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
624 : * and the stack's cursor is simply moved to this existing Rib.
625 : *
626 : * @param rib The Rib to push
627 : * @param id The NodeId of the node for which the Rib was created. For
628 : * example, if a Rib is created because a lexical scope is entered,
629 : * then `id` is that `BlockExpr`'s NodeId.
630 : * @param path An optional path if the Rib was created due to a "named"
631 : * lexical scope, like a module's.
632 : */
633 : void push (Rib::Kind rib_kind, NodeId id, tl::optional<Identifier> path = {});
634 :
635 : /**
636 : * Pop the innermost Rib from the stack
637 : */
638 : void pop ();
639 :
640 : /**
641 : * Insert a new definition in the innermost `Rib` in this stack
642 : *
643 : * @param name The name of the definition
644 : * @param id Its NodeId
645 : *
646 : * @return `DuplicateNameError` if that node was already present in the Rib,
647 : * the node's `NodeId` otherwise.
648 : *
649 : * @aborts if there are no `Rib`s inserted in the current map, this function
650 : * aborts the program.
651 : */
652 : tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id);
653 :
654 : tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
655 : NodeId id);
656 :
657 : void insert_crate_in_prelude (Identifier crate_name, NodeId crate_id);
658 :
659 : /**
660 : * Insert a new shadowable definition in the innermost `Rib` in this stack
661 : *
662 : * @param name The name of the definition
663 : * @param id Its NodeId
664 : *
665 : * @return `DuplicateNameError` if that node was already present in the Rib,
666 : * the node's `NodeId` otherwise.
667 : *
668 : * @aborts if there are no `Rib`s inserted in the current map, this function
669 : * aborts the program.
670 : */
671 : tl::expected<NodeId, DuplicateNameError> insert_shadowable (Identifier name,
672 : NodeId id);
673 :
674 : /**
675 : * Insert a new glob-originated definition in the innermost `Rib` in this
676 : * stack
677 : *
678 : * @param name The name of the definition
679 : * @param id Its NodeId
680 : *
681 : * @return `DuplicateNameError` if that node was already present in the Rib,
682 : * the node's `NodeId` otherwise.
683 : *
684 : * @aborts if there are no `Rib`s inserted in the current map, this function
685 : * aborts the program.
686 : */
687 : tl::expected<NodeId, DuplicateNameError> insert_globbed (Identifier name,
688 : NodeId id);
689 :
690 : /**
691 : * Insert a new definition at the root of this stack
692 : *
693 : * @param name The name of the definition
694 : * @param id Its NodeId
695 : *
696 : * @return `DuplicateNameError` if that node was already present in the Rib,
697 : * the node's `NodeId` otherwise.
698 : *
699 : * @aborts if there are no `Rib`s inserted in the current map, this function
700 : * aborts the program.
701 : */
702 : tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
703 : NodeId id);
704 :
705 : /**
706 : * Insert an item within the lang prelude
707 : *
708 : * @param name The name of the definition
709 : * @param id Its NodeId
710 : */
711 : void insert_lang_prelude (Identifier name, NodeId id);
712 :
713 : /* Access the innermost `Rib` in this map */
714 : Rib &peek ();
715 : const Rib &peek () const;
716 :
717 : /**
718 : * Reverse iter on all ribs from the innermost one to the outermost one,
719 : * trying to find a name. This is the default algorithm.
720 : * This function gets specialized based on the Rib::Kind
721 : * this way, we ensure a proper resolution algorithm at the type level
722 : *
723 : * @param name Name of the identifier to locate in this scope or an outermore
724 : * scope
725 : *
726 : * @return a valid option with the Definition if the identifier is present in
727 : * the current map, an empty one otherwise.
728 : */
729 : tl::optional<Rib::Definition> get (const Identifier &name);
730 : tl::optional<Rib::Definition> get_lang_prelude (const Identifier &name);
731 : tl::optional<Rib::Definition> get_lang_prelude (const std::string &name);
732 : tl::optional<Rib::Definition> get_from_prelude (NodeId prelude,
733 : const Identifier &name);
734 :
735 : // FIXME: Documentation
736 : tl::optional<Rib &> to_rib (NodeId rib_id);
737 : tl::optional<const Rib &> to_rib (NodeId rib_id) const;
738 :
739 : std::string as_debug_string () const;
740 :
741 : /**
742 : * Used to check if a module is a descendant of another module
743 : * Intended for use in the privacy checker
744 : */
745 : bool is_module_descendant (NodeId parent, NodeId child) const;
746 :
747 : tl::optional<Rib::Definition> get (Node &start, const Identifier &name);
748 :
749 : /* Should we keep going upon seeing a Rib? */
750 : enum class KeepGoing
751 : {
752 : Yes,
753 : No,
754 : };
755 :
756 : /* Add a new Rib to the stack. This is an internal method */
757 : void push_inner (Rib::Kind rib, Link link);
758 :
759 : /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
760 : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
761 : void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
762 :
763 : /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
764 : void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
765 : void reverse_iter (const Node &start,
766 : std::function<KeepGoing (const Node &)> lambda) const;
767 :
768 : Node &cursor ();
769 : const Node &cursor () const;
770 :
771 : void update_cursor (Node &new_cursor);
772 :
773 : std::reference_wrapper<Node> cursor_reference;
774 :
775 : void stream_rib (std::stringstream &stream, const Rib &rib,
776 : const std::string &next, const std::string &next_next) const;
777 : void stream_node (std::stringstream &stream, unsigned indentation,
778 : const Node &node, unsigned depth = 0) const;
779 :
780 : /* Helper types and functions for `resolve_path` */
781 :
782 : using SegIterator =
783 : typename std::vector<ResolutionPathSegment>::const_iterator;
784 :
785 : Node &find_closest_module (Node &starting_point);
786 :
787 : tl::optional<SegIterator>
788 : find_starting_point (const RawPath<ResolutionPathSegment> &path,
789 : std::reference_wrapper<Node> &starting_point,
790 : std::function<void (Usage, Definition, Namespace)>
791 : insert_segment_resolution,
792 : std::vector<Error> &collect_errors);
793 :
794 : /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
795 : struct DfsResult
796 : {
797 : Node &first;
798 : std::string second;
799 : };
800 : struct ConstDfsResult
801 : {
802 : const Node &first;
803 : std::string second;
804 : };
805 :
806 : // FIXME: Documentation
807 : tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
808 : tl::optional<ConstDfsResult> dfs (const Node &starting_point,
809 : NodeId to_find) const;
810 : // FIXME: Documentation
811 : tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
812 : tl::optional<const Rib &> dfs_rib (const Node &starting_point,
813 : NodeId to_find) const;
814 : // FIXME: Documentation
815 : tl::optional<Node &> dfs_node (Node &starting_point, NodeId to_find);
816 : tl::optional<const Node &> dfs_node (const Node &starting_point,
817 : NodeId to_find) const;
818 :
819 : std::unordered_map<NodeId, Node &> dfs_cache;
820 : tl::optional<Node &> check_cache (NodeId to_find);
821 : void cache (NodeId found, Node &result);
822 :
823 633262 : bool forward_declared (NodeId definition, NodeId usage)
824 : {
825 633262 : if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
826 : return false;
827 :
828 : // Each type param has a ban rib keyed by its NodeId, and those ribs are
829 : // siblings ordered by NodeId, i.e. by declaration order. A default may
830 : // only use params declared before its own.
831 52 : auto ¤t = cursor ();
832 52 : if (definition == current.id)
833 : return true;
834 51 : if (!current.parent)
835 : return false;
836 :
837 82 : for (auto &child : current.parent.value ().children)
838 56 : if (child.second.id == definition)
839 : return definition > current.id
840 25 : && child.second.rib (N).kind == Rib::Kind::ForwardTypeParamBan;
841 :
842 : return false;
843 : }
844 :
845 4520732 : void map_usage (Usage usage, Definition definition)
846 : {
847 4520732 : resolved_nodes.emplace (usage, definition);
848 :
849 : // auto inserted = resolved_nodes.emplace (usage, definition);
850 :
851 : // is that valid?
852 : // FIXME: Yikes
853 : // rust_assert (inserted.first->first.id == definition.id);
854 : }
855 :
856 6478515 : tl::optional<NodeId> lookup (NodeId usage) const
857 : {
858 6478515 : auto it = resolved_nodes.find (Usage (usage));
859 :
860 6478515 : if (it == resolved_nodes.end ())
861 222407 : return tl::nullopt;
862 :
863 6256108 : return it->second.id;
864 : }
865 :
866 : tl::expected<Definition, LookupFinalizeError>
867 : find_leaf_definition (const NodeId &key) const;
868 :
869 : // Flattening is not needed for now but should be used later?
870 : #if 0
871 : /**
872 : * Look at NameResolutionContext::flatten - This is the inner working function
873 : * which works on one specific namespace, while NameResolutionContext::flatten
874 : * calls flatten for every namespace
875 : */
876 : void flatten ();
877 : #endif
878 :
879 : /* Map of "usage" nodes which have been resolved to a "definition" node */
880 : std::map<Usage, Definition> resolved_nodes;
881 : };
882 :
883 : } // namespace Resolver2_0
884 : } // namespace Rust
885 :
886 : #include "rust-forever-stack.hxx"
887 :
888 : #endif // !RUST_FOREVER_STACK_H
|