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 589672 : class ResolutionPath
406 : {
407 : public:
408 : template <typename T>
409 294836 : ResolutionPath (const std::vector<T> &segments_in, NodeId node_id)
410 294836 : : node_id (node_id)
411 : {
412 294836 : segments.clear ();
413 294836 : segments.reserve (segments_in.size ());
414 676457 : for (auto &outer_seg : segments_in)
415 : {
416 381621 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
417 : {
418 1525 : rust_assert (!lang_prefix.has_value ());
419 1525 : lang_prefix = std::make_pair (lang_item.value (),
420 1525 : unwrap_segment_node_id (outer_seg));
421 1525 : continue;
422 : }
423 :
424 380096 : auto &seg = unwrap_type_segment (outer_seg);
425 :
426 380096 : Segment new_seg;
427 380096 : new_seg.name = seg.as_string ();
428 380096 : new_seg.node_id = unwrap_segment_node_id (outer_seg);
429 380096 : new_seg.locus = seg.get_locus ();
430 380096 : segments.push_back (std::move (new_seg));
431 : }
432 294836 : }
433 :
434 294836 : ResolutionPath () : node_id (UNKNOWN_NODEID) {}
435 :
436 1520384 : struct Segment
437 : {
438 : std::string name;
439 : NodeId node_id;
440 : location_t locus;
441 :
442 157869 : bool is_super_path_seg () const { return name.compare ("super") == 0; }
443 295687 : bool is_crate_path_seg () const { return name.compare ("crate") == 0; }
444 262472 : bool is_lower_self_seg () const { return name.compare ("self") == 0; }
445 : bool is_big_self_seg () const { return name.compare ("Self") == 0; }
446 : };
447 :
448 329058 : tl::optional<std::pair<LangItem::Kind, NodeId>> get_lang_prefix () const
449 : {
450 329058 : return lang_prefix;
451 : }
452 :
453 329058 : const std::vector<Segment> &get_segments () const { return segments; }
454 :
455 : NodeId get_node_id () const { return node_id; }
456 :
457 0 : std::string as_string () const
458 : {
459 0 : std::string ret;
460 0 : if (lang_prefix)
461 0 : ret = "#[lang]::";
462 0 : for (auto &seg : segments)
463 0 : ret += "::" + seg.name;
464 0 : return ret;
465 : }
466 :
467 : private:
468 : tl::optional<std::pair<LangItem::Kind, NodeId>> lang_prefix;
469 : std::vector<Segment> segments;
470 : NodeId node_id;
471 : };
472 :
473 : /**
474 : * Error enum for finding leaf definitions in the resolved_nodes map
475 : */
476 : enum class LookupFinalizeError
477 : {
478 : // Impossible - we did not find any definition corresponding to a Usage.
479 : // This is an internal compiler error
480 : NoDefinition,
481 : // There was a loop in the map, such as an import resolving to another
482 : // import which eventually resolved to the original import. Report the
483 : // error and stop the pipeline
484 : Loop,
485 : };
486 :
487 : class ForeverStackBase
488 : {
489 : public:
490 : /**
491 : * A link between two Nodes in our trie data structure. This class represents
492 : * the edges of the graph
493 : */
494 95483924 : class Link
495 : {
496 : public:
497 31395752 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
498 :
499 172836862 : bool compare (const Link &other) const { return id < other.id; }
500 :
501 : NodeId id;
502 : tl::optional<Identifier> path;
503 : };
504 :
505 : /* Link comparison class, which we use in a Node's `children` map */
506 : class LinkCmp
507 : {
508 : public:
509 172836862 : bool operator() (const Link &lhs, const Link &rhs) const
510 : {
511 172836862 : return lhs.compare (rhs);
512 : }
513 : };
514 :
515 : class Node
516 : {
517 : public:
518 10196 : Node (Rib::Kind rib_kind, NodeId id)
519 10196 : : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
520 10196 : rib_macros (rib_kind), id (id)
521 10196 : {}
522 31380458 : Node (Rib::Kind rib_kind, NodeId id, Node &parent)
523 31380458 : : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
524 31380458 : rib_macros (rib_kind), id (id), parent (parent)
525 31380458 : {}
526 :
527 75475092 : const Rib &rib (Namespace n) const
528 : {
529 75388700 : switch (n)
530 : {
531 25527531 : case Namespace::Values:
532 25527531 : return rib_values;
533 18372981 : case Namespace::Types:
534 18372981 : return rib_types;
535 15722626 : case Namespace::Labels:
536 15722626 : return rib_labels;
537 15851954 : case Namespace::Macros:
538 15851954 : return rib_macros;
539 0 : default:
540 0 : rust_unreachable ();
541 : }
542 : }
543 :
544 75388700 : Rib &rib (Namespace n)
545 : {
546 75329857 : return const_cast<Rib &> (const_cast<const Node *> (this)->rib (n));
547 : }
548 :
549 : inline bool is_root () const;
550 : inline bool is_prelude () const;
551 : inline bool is_leaf () const;
552 :
553 : inline void insert_child (Link link, Node child);
554 :
555 : // these are the "values" of the node - the data it keeps.
556 : Rib rib_values;
557 : Rib rib_types;
558 : Rib rib_labels;
559 : Rib rib_macros;
560 :
561 : std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
562 :
563 : NodeId id; // The node id of the Node's scope
564 :
565 : tl::optional<Node &> parent; // `None` only if the node is a root
566 : };
567 :
568 20392 : ForeverStackBase (Node &root, Node &lang_prelude, Node &extern_prelude)
569 20392 : : root (root), lang_prelude (lang_prelude), extern_prelude (extern_prelude)
570 : {}
571 :
572 : /* The forever stack's actual nodes */
573 : Node &root;
574 :
575 : /*
576 : * A special prelude node used currently for resolving language builtins
577 : * It has the root node as a parent, and acts as a "special case" for name
578 : * resolution
579 : */
580 : Node &lang_prelude;
581 :
582 : /*
583 : * The extern prelude, used for resolving external crates
584 : */
585 : Node &extern_prelude;
586 : };
587 :
588 : template <Namespace N> class ForeverStack : public ForeverStackBase
589 : {
590 : public:
591 20392 : ForeverStack (Node &root, Node &lang_prelude, Node &extern_prelude)
592 : : ForeverStackBase (root, lang_prelude, extern_prelude),
593 20392 : cursor_reference (root)
594 : {
595 20392 : rust_assert (root.is_root ());
596 20392 : rust_assert (root.is_leaf ());
597 :
598 : // TODO: Should we be using the forever stack root as the crate scope?
599 : // TODO: Is this how we should be getting the crate node id?
600 20392 : auto &crate_mappings = Analysis::Mappings::get ().crate;
601 20392 : root.id = *crate_mappings.crate_num_to_nodeid (
602 20392 : crate_mappings.get_current_crate ());
603 20392 : }
604 :
605 : /**
606 : * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
607 : * and the stack's cursor is simply moved to this existing Rib.
608 : *
609 : * @param rib The Rib to push
610 : * @param id The NodeId of the node for which the Rib was created. For
611 : * example, if a Rib is created because a lexical scope is entered,
612 : * then `id` is that `BlockExpr`'s NodeId.
613 : * @param path An optional path if the Rib was created due to a "named"
614 : * lexical scope, like a module's.
615 : */
616 : void push (Rib::Kind rib_kind, NodeId id, tl::optional<Identifier> path = {});
617 :
618 : /**
619 : * Pop the innermost Rib from the stack
620 : */
621 : void pop ();
622 :
623 : /**
624 : * Insert a new definition in the innermost `Rib` in this stack
625 : *
626 : * @param name The name of the definition
627 : * @param id Its NodeId
628 : *
629 : * @return `DuplicateNameError` if that node was already present in the Rib,
630 : * the node's `NodeId` otherwise.
631 : *
632 : * @aborts if there are no `Rib`s inserted in the current map, this function
633 : * aborts the program.
634 : */
635 : tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id);
636 :
637 : tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
638 : NodeId id);
639 :
640 : /**
641 : * Insert a new shadowable 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_shadowable (Identifier name,
653 : NodeId id);
654 :
655 : /**
656 : * Insert a new glob-originated definition in the innermost `Rib` in this
657 : * stack
658 : *
659 : * @param name The name of the definition
660 : * @param id Its NodeId
661 : *
662 : * @return `DuplicateNameError` if that node was already present in the Rib,
663 : * the node's `NodeId` otherwise.
664 : *
665 : * @aborts if there are no `Rib`s inserted in the current map, this function
666 : * aborts the program.
667 : */
668 : tl::expected<NodeId, DuplicateNameError> insert_globbed (Identifier name,
669 : NodeId id);
670 :
671 : /**
672 : * Insert a new definition at the root of this stack
673 : *
674 : * @param name The name of the definition
675 : * @param id Its NodeId
676 : *
677 : * @return `DuplicateNameError` if that node was already present in the Rib,
678 : * the node's `NodeId` otherwise.
679 : *
680 : * @aborts if there are no `Rib`s inserted in the current map, this function
681 : * aborts the program.
682 : */
683 : tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
684 : NodeId id);
685 :
686 : /**
687 : * Insert an item within the lang prelude
688 : *
689 : * @param name The name of the definition
690 : * @param id Its NodeId
691 : */
692 : void insert_lang_prelude (Identifier name, NodeId id);
693 :
694 : /* Access the innermost `Rib` in this map */
695 : Rib &peek ();
696 : const Rib &peek () const;
697 :
698 : /**
699 : * Reverse iter on all ribs from the innermost one to the outermost one,
700 : * trying to find a name. This is the default algorithm.
701 : * This function gets specialized based on the Rib::Kind
702 : * this way, we ensure a proper resolution algorithm at the type level
703 : *
704 : * @param name Name of the identifier to locate in this scope or an outermore
705 : * scope
706 : *
707 : * @return a valid option with the Definition if the identifier is present in
708 : * the current map, an empty one otherwise.
709 : */
710 : tl::optional<Rib::Definition> get (const Identifier &name);
711 : tl::optional<Rib::Definition> get_lang_prelude (const Identifier &name);
712 : tl::optional<Rib::Definition> get_lang_prelude (const std::string &name);
713 : tl::optional<Rib::Definition> get_from_prelude (NodeId prelude,
714 : const Identifier &name);
715 :
716 : // FIXME: Documentation
717 : tl::optional<Rib &> to_rib (NodeId rib_id);
718 : tl::optional<const Rib &> to_rib (NodeId rib_id) const;
719 :
720 : std::string as_debug_string () const;
721 :
722 : /**
723 : * Used to check if a module is a descendant of another module
724 : * Intended for use in the privacy checker
725 : */
726 : bool is_module_descendant (NodeId parent, NodeId child) const;
727 :
728 : tl::optional<Rib::Definition> get (Node &start, const Identifier &name);
729 :
730 : /* Should we keep going upon seeing a Rib? */
731 : enum class KeepGoing
732 : {
733 : Yes,
734 : No,
735 : };
736 :
737 : /* Add a new Rib to the stack. This is an internal method */
738 : void push_inner (Rib::Kind rib, Link link);
739 :
740 : /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
741 : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
742 : void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
743 :
744 : /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
745 : void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
746 : void reverse_iter (const Node &start,
747 : std::function<KeepGoing (const Node &)> lambda) const;
748 :
749 : Node &cursor ();
750 : const Node &cursor () const;
751 :
752 : void update_cursor (Node &new_cursor);
753 :
754 : std::reference_wrapper<Node> cursor_reference;
755 :
756 : void stream_rib (std::stringstream &stream, const Rib &rib,
757 : const std::string &next, const std::string &next_next) const;
758 : void stream_node (std::stringstream &stream, unsigned indentation,
759 : const Node &node, unsigned depth = 0) const;
760 :
761 : /* Helper types and functions for `resolve_path` */
762 :
763 : using SegIterator =
764 : typename std::vector<ResolutionPath::Segment>::const_iterator;
765 :
766 : Node &find_closest_module (Node &starting_point);
767 :
768 : tl::optional<SegIterator>
769 : find_starting_point (const std::vector<ResolutionPath::Segment> &segments,
770 : std::reference_wrapper<Node> &starting_point,
771 : std::function<void (Usage, Definition, Namespace)>
772 : insert_segment_resolution,
773 : std::vector<Error> &collect_errors);
774 :
775 : /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
776 : struct DfsResult
777 : {
778 : Node &first;
779 : std::string second;
780 : };
781 : struct ConstDfsResult
782 : {
783 : const Node &first;
784 : std::string second;
785 : };
786 :
787 : // FIXME: Documentation
788 : tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
789 : tl::optional<ConstDfsResult> dfs (const Node &starting_point,
790 : NodeId to_find) const;
791 : // FIXME: Documentation
792 : tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
793 : tl::optional<const Rib &> dfs_rib (const Node &starting_point,
794 : NodeId to_find) const;
795 : // FIXME: Documentation
796 : tl::optional<Node &> dfs_node (Node &starting_point, NodeId to_find);
797 : tl::optional<const Node &> dfs_node (const Node &starting_point,
798 : NodeId to_find) const;
799 :
800 : std::unordered_map<NodeId, Node &> dfs_cache;
801 : tl::optional<Node &> check_cache (NodeId to_find);
802 : void cache (NodeId found, Node &result);
803 :
804 133729 : bool forward_declared (NodeId definition, NodeId usage)
805 : {
806 133729 : if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
807 : return false;
808 :
809 : // Each type param has a ban rib keyed by its NodeId, and those ribs are
810 : // siblings ordered by NodeId, i.e. by declaration order. A default may
811 : // only use params declared before its own.
812 45 : auto ¤t = cursor ();
813 45 : if (definition == current.id)
814 : return true;
815 44 : if (!current.parent)
816 : return false;
817 :
818 75 : for (auto &child : current.parent.value ().children)
819 49 : if (child.second.id == definition)
820 : return definition > current.id
821 18 : && child.second.rib (N).kind == Rib::Kind::ForwardTypeParamBan;
822 :
823 : return false;
824 : }
825 :
826 812811 : void map_usage (Usage usage, Definition definition)
827 : {
828 812811 : resolved_nodes.emplace (usage, definition);
829 :
830 : // auto inserted = resolved_nodes.emplace (usage, definition);
831 :
832 : // is that valid?
833 : // FIXME: Yikes
834 : // rust_assert (inserted.first->first.id == definition.id);
835 : }
836 :
837 921293 : tl::optional<NodeId> lookup (NodeId usage) const
838 : {
839 921293 : auto it = resolved_nodes.find (Usage (usage));
840 :
841 921293 : if (it == resolved_nodes.end ())
842 100502 : return tl::nullopt;
843 :
844 820791 : return it->second.id;
845 : }
846 :
847 : tl::expected<Definition, LookupFinalizeError>
848 : find_leaf_definition (const NodeId &key) const;
849 :
850 : // Flattening is not needed for now but should be used later?
851 : #if 0
852 : /**
853 : * Look at NameResolutionContext::flatten - This is the inner working function
854 : * which works on one specific namespace, while NameResolutionContext::flatten
855 : * calls flatten for every namespace
856 : */
857 : void flatten ();
858 : #endif
859 :
860 : /* Map of "usage" nodes which have been resolved to a "definition" node */
861 : std::map<Usage, Definition> resolved_nodes;
862 : };
863 :
864 : } // namespace Resolver2_0
865 : } // namespace Rust
866 :
867 : #include "rust-forever-stack.hxx"
868 :
869 : #endif // !RUST_FOREVER_STACK_H
|
