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 : /**
399 : * Intended for use by ForeverStack to store Nodes
400 : * Unlike ForeverStack, does not store a cursor reference
401 : * Intended to make path resolution in multiple namespaces simpler
402 : **/
403 : class ForeverStackStore
404 : {
405 : public:
406 : ForeverStackStore (NodeId crate_id) : root (Rib::Kind::Normal, crate_id)
407 : {
408 : rust_assert (root.is_root ());
409 : rust_assert (root.is_leaf ());
410 : }
411 :
412 : private:
413 : /**
414 : * A link between two Nodes in our trie data structure. This class represents
415 : * the edges of the graph
416 : */
417 0 : class Link
418 : {
419 : public:
420 0 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
421 :
422 0 : bool compare (const Link &other) const { return id < other.id; }
423 :
424 : NodeId id;
425 : tl::optional<Identifier> path;
426 : };
427 :
428 : /* Link comparison class, which we use in a Node's `children` map */
429 : class LinkCmp
430 : {
431 : public:
432 0 : bool operator() (const Link &lhs, const Link &rhs) const
433 : {
434 0 : return lhs.compare (rhs);
435 : }
436 : };
437 :
438 : public:
439 : class Node;
440 :
441 : struct DfsResult
442 : {
443 : Node &first;
444 : std::string second;
445 : };
446 :
447 : struct ConstDfsResult
448 : {
449 : const Node &first;
450 : std::string second;
451 : };
452 :
453 : /* Should we keep going upon seeing a Rib? */
454 : enum class KeepGoing
455 : {
456 : Yes,
457 : No,
458 : };
459 :
460 : class Node
461 : {
462 : private:
463 : friend class ForeverStackStore::ForeverStackStore;
464 :
465 0 : Node (Rib::Kind rib_kind, NodeId id, tl::optional<Node &> parent)
466 0 : : value_rib (rib_kind), type_rib (rib_kind), label_rib (rib_kind),
467 0 : macro_rib (rib_kind), id (id), parent (parent)
468 0 : {}
469 : Node (Rib::Kind rib_kind, NodeId id) : Node (rib_kind, id, tl::nullopt) {}
470 0 : Node (Rib::Kind rib_kind, NodeId id, Node &parent)
471 0 : : Node (rib_kind, id, tl::optional<Node &> (parent))
472 : {}
473 :
474 : public:
475 : Node (const Node &) = default;
476 0 : Node (Node &&) = default;
477 : Node &operator= (const Node &) = delete;
478 : Node &operator= (Node &&) = default;
479 :
480 : bool is_root () const;
481 : bool is_leaf () const;
482 :
483 : NodeId get_id () const;
484 :
485 : Node &insert_child (NodeId id, tl::optional<Identifier> path,
486 : Rib::Kind kind);
487 :
488 : tl::optional<Node &> get_child (const Identifier &path);
489 : tl::optional<const Node &> get_child (const Identifier &path) const;
490 :
491 : tl::optional<Node &> get_parent ();
492 : tl::optional<const Node &> get_parent () const;
493 :
494 : // finds the identifier, if any, used to link
495 : // this node's parent to this node
496 : tl::optional<const Identifier &> get_parent_path () const;
497 :
498 : Rib &get_rib (Namespace ns);
499 : const Rib &get_rib (Namespace ns) const;
500 :
501 : tl::expected<NodeId, DuplicateNameError> insert (const Identifier &name,
502 : NodeId node, Namespace ns);
503 : tl::expected<NodeId, DuplicateNameError>
504 : insert_shadowable (const Identifier &name, NodeId node, Namespace ns);
505 : tl::expected<NodeId, DuplicateNameError>
506 : insert_globbed (const Identifier &name, NodeId node, Namespace ns);
507 :
508 : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
509 : void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
510 :
511 : void child_iter (std::function<KeepGoing (
512 : NodeId, tl::optional<const Identifier &>, Node &)>
513 : lambda);
514 : void child_iter (std::function<KeepGoing (
515 : NodeId, tl::optional<const Identifier &>, const Node &)>
516 : lambda) const;
517 :
518 : Node &find_closest_module ();
519 : const Node &find_closest_module () const;
520 :
521 : tl::optional<Node &> dfs_node (NodeId to_find);
522 : tl::optional<const Node &> dfs_node (NodeId to_find) const;
523 :
524 : private:
525 : // per-namespace ribs
526 : Rib value_rib;
527 : Rib type_rib;
528 : Rib label_rib;
529 : Rib macro_rib;
530 : // all linked nodes
531 : std::map<Link, Node, LinkCmp> children;
532 :
533 : NodeId id; // The node id of the Node's scope
534 :
535 : tl::optional<Node &> parent; // `None` only if the node is a root
536 : };
537 :
538 : Node &get_root ();
539 : const Node &get_root () const;
540 :
541 : tl::optional<Node &> get_node (NodeId node_id);
542 : tl::optional<const Node &> get_node (NodeId node_id) const;
543 :
544 : private:
545 : Node root;
546 : };
547 :
548 : enum class ResolutionMode
549 : {
550 : Normal,
551 : FromRoot,
552 : FromExtern, // extern prelude
553 : };
554 :
555 170890 : class ResolutionPath
556 : {
557 : public:
558 : template <typename T>
559 85445 : ResolutionPath (const std::vector<T> &segments_in, NodeId node_id)
560 85445 : : node_id (node_id)
561 : {
562 85445 : segments.clear ();
563 85445 : segments.reserve (segments_in.size ());
564 188088 : for (auto &outer_seg : segments_in)
565 : {
566 102643 : if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
567 : {
568 392 : rust_assert (!lang_prefix.has_value ());
569 392 : lang_prefix = std::make_pair (lang_item.value (),
570 392 : unwrap_segment_node_id (outer_seg));
571 392 : continue;
572 : }
573 :
574 102251 : auto &seg = unwrap_type_segment (outer_seg);
575 :
576 102251 : Segment new_seg;
577 102251 : new_seg.name = seg.as_string ();
578 102251 : new_seg.node_id = unwrap_segment_node_id (outer_seg);
579 102251 : new_seg.locus = seg.get_locus ();
580 102251 : segments.push_back (std::move (new_seg));
581 : }
582 85445 : }
583 :
584 85445 : ResolutionPath () : node_id (UNKNOWN_NODEID) {}
585 :
586 409004 : struct Segment
587 : {
588 : std::string name;
589 : NodeId node_id;
590 : location_t locus;
591 :
592 31551 : bool is_super_path_seg () const { return name.compare ("super") == 0; }
593 47044 : bool is_crate_path_seg () const { return name.compare ("crate") == 0; }
594 48304 : bool is_lower_self_seg () const { return name.compare ("self") == 0; }
595 : bool is_big_self_seg () const { return name.compare ("Self") == 0; }
596 : };
597 :
598 87063 : tl::optional<std::pair<LangItem::Kind, NodeId>> get_lang_prefix () const
599 : {
600 87063 : return lang_prefix;
601 : }
602 :
603 87063 : const std::vector<Segment> &get_segments () const { return segments; }
604 :
605 : NodeId get_node_id () const { return node_id; }
606 :
607 87063 : std::string as_string () const
608 : {
609 87063 : std::string ret;
610 87063 : if (lang_prefix)
611 392 : ret = "#[lang]::";
612 192945 : for (auto &seg : segments)
613 211764 : ret += "::" + seg.name;
614 87063 : return ret;
615 : }
616 :
617 : private:
618 : tl::optional<std::pair<LangItem::Kind, NodeId>> lang_prefix;
619 : std::vector<Segment> segments;
620 : NodeId node_id;
621 : };
622 :
623 : /**
624 : * Error enum for finding leaf definitions in the resolved_nodes map
625 : */
626 : enum class LookupFinalizeError
627 : {
628 : // Impossible - we did not find any definition corresponding to a Usage.
629 : // This is an internal compiler error
630 : NoDefinition,
631 : // There was a loop in the map, such as an import resolving to another
632 : // import which eventually resolved to the original import. Report the
633 : // error and stop the pipeline
634 : Loop,
635 : };
636 :
637 : template <Namespace N> class ForeverStack
638 : {
639 : public:
640 19084 : ForeverStack ()
641 19084 : : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)),
642 38168 : lang_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID, root)),
643 19084 : extern_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID)),
644 19084 : cursor_reference (root)
645 : {
646 19084 : rust_assert (root.is_root ());
647 19084 : rust_assert (root.is_leaf ());
648 :
649 : // TODO: Should we be using the forever stack root as the crate scope?
650 : // TODO: Is this how we should be getting the crate node id?
651 19084 : auto &mappings = Analysis::Mappings::get ();
652 19084 : root.id = *mappings.crate_num_to_nodeid (mappings.get_current_crate ());
653 19084 : }
654 :
655 : /**
656 : * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
657 : * and the stack's cursor is simply moved to this existing Rib.
658 : *
659 : * @param rib The Rib to push
660 : * @param id The NodeId of the node for which the Rib was created. For
661 : * example, if a Rib is created because a lexical scope is entered,
662 : * then `id` is that `BlockExpr`'s NodeId.
663 : * @param path An optional path if the Rib was created due to a "named"
664 : * lexical scope, like a module's.
665 : */
666 : void push (Rib::Kind rib_kind, NodeId id, tl::optional<Identifier> path = {});
667 :
668 : /**
669 : * Pop the innermost Rib from the stack
670 : */
671 : void pop ();
672 :
673 : /**
674 : * Insert a new definition in the innermost `Rib` in this stack
675 : *
676 : * @param name The name of the definition
677 : * @param id Its NodeId
678 : *
679 : * @return `DuplicateNameError` if that node was already present in the Rib,
680 : * the node's `NodeId` otherwise.
681 : *
682 : * @aborts if there are no `Rib`s inserted in the current map, this function
683 : * aborts the program.
684 : */
685 : tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id);
686 :
687 : tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
688 : NodeId id);
689 :
690 : /**
691 : * Insert a new shadowable definition in the innermost `Rib` in 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_shadowable (Identifier name,
703 : NodeId id);
704 :
705 : /**
706 : * Insert a new glob-originated definition in the innermost `Rib` in this
707 : * stack
708 : *
709 : * @param name The name of the definition
710 : * @param id Its NodeId
711 : *
712 : * @return `DuplicateNameError` if that node was already present in the Rib,
713 : * the node's `NodeId` otherwise.
714 : *
715 : * @aborts if there are no `Rib`s inserted in the current map, this function
716 : * aborts the program.
717 : */
718 : tl::expected<NodeId, DuplicateNameError> insert_globbed (Identifier name,
719 : NodeId id);
720 :
721 : /**
722 : * Insert a new definition at the root of this stack
723 : *
724 : * @param name The name of the definition
725 : * @param id Its NodeId
726 : *
727 : * @return `DuplicateNameError` if that node was already present in the Rib,
728 : * the node's `NodeId` otherwise.
729 : *
730 : * @aborts if there are no `Rib`s inserted in the current map, this function
731 : * aborts the program.
732 : */
733 : tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
734 : NodeId id);
735 :
736 : /**
737 : * Insert an item within the lang prelude
738 : *
739 : * @param name The name of the definition
740 : * @param id Its NodeId
741 : */
742 : void insert_lang_prelude (Identifier name, NodeId id);
743 :
744 : /* Access the innermost `Rib` in this map */
745 : Rib &peek ();
746 : const Rib &peek () const;
747 :
748 : /**
749 : * Reverse iter on all ribs from the innermost one to the outermost one,
750 : * trying to find a name. This is the default algorithm.
751 : * This function gets specialized based on the Rib::Kind
752 : * this way, we ensure a proper resolution algorithm at the type level
753 : *
754 : * @param name Name of the identifier to locate in this scope or an outermore
755 : * scope
756 : *
757 : * @return a valid option with the Definition if the identifier is present in
758 : * the current map, an empty one otherwise.
759 : */
760 : tl::optional<Rib::Definition> get (const Identifier &name);
761 : tl::optional<Rib::Definition> get_lang_prelude (const Identifier &name);
762 : tl::optional<Rib::Definition> get_lang_prelude (const std::string &name);
763 : tl::optional<Rib::Definition> get_from_prelude (NodeId prelude,
764 : const Identifier &name);
765 :
766 : // FIXME: Documentation
767 : tl::optional<Rib &> to_rib (NodeId rib_id);
768 : tl::optional<const Rib &> to_rib (NodeId rib_id) const;
769 :
770 : std::string as_debug_string () const;
771 :
772 : /**
773 : * Used to check if a module is a descendant of another module
774 : * Intended for use in the privacy checker
775 : */
776 : bool is_module_descendant (NodeId parent, NodeId child) const;
777 :
778 : /**
779 : * A link between two Nodes in our trie data structure. This class represents
780 : * the edges of the graph
781 : */
782 5557925 : class Link
783 : {
784 : public:
785 1620462 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
786 :
787 4556211 : bool compare (const Link &other) const { return id < other.id; }
788 :
789 : NodeId id;
790 : tl::optional<Identifier> path;
791 : };
792 :
793 : /* Link comparison class, which we use in a Node's `children` map */
794 : class LinkCmp
795 : {
796 : public:
797 4556211 : bool operator() (const Link &lhs, const Link &rhs) const
798 : {
799 4556211 : return lhs.compare (rhs);
800 : }
801 : };
802 :
803 : class Node
804 : {
805 : public:
806 38168 : Node (Rib rib, NodeId id) : rib (rib), id (id) {}
807 1625233 : Node (Rib rib, NodeId id, Node &parent)
808 1625233 : : rib (rib), id (id), parent (parent)
809 : {}
810 :
811 : bool is_root () const;
812 : bool is_prelude () const;
813 : bool is_leaf () const;
814 :
815 : void insert_child (Link link, Node child);
816 :
817 : Rib rib; // this is the "value" of the node - the data it keeps.
818 : std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
819 :
820 : NodeId id; // The node id of the Node's scope
821 :
822 : tl::optional<Node &> parent; // `None` only if the node is a root
823 : };
824 :
825 : tl::optional<Rib::Definition> get (Node &start, const Identifier &name);
826 :
827 : /* Should we keep going upon seeing a Rib? */
828 : enum class KeepGoing
829 : {
830 : Yes,
831 : No,
832 : };
833 :
834 : /* Add a new Rib to the stack. This is an internal method */
835 : void push_inner (Rib rib, Link link);
836 :
837 : /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
838 : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
839 : void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
840 :
841 : /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
842 : void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
843 : void reverse_iter (const Node &start,
844 : std::function<KeepGoing (const Node &)> lambda) const;
845 :
846 : Node &cursor ();
847 : const Node &cursor () const;
848 :
849 : void update_cursor (Node &new_cursor);
850 :
851 : /* The forever stack's actual nodes */
852 : Node root;
853 : /*
854 : * A special prelude node used currently for resolving language builtins
855 : * It has the root node as a parent, and acts as a "special case" for name
856 : * resolution
857 : */
858 : Node lang_prelude;
859 :
860 : /*
861 : * The extern prelude, used for resolving external crates
862 : */
863 : Node extern_prelude;
864 :
865 : std::reference_wrapper<Node> cursor_reference;
866 :
867 : void stream_rib (std::stringstream &stream, const Rib &rib,
868 : const std::string &next, const std::string &next_next) const;
869 : void stream_node (std::stringstream &stream, unsigned indentation,
870 : const Node &node, unsigned depth = 0) const;
871 :
872 : /* Helper types and functions for `resolve_path` */
873 :
874 : using SegIterator =
875 : typename std::vector<ResolutionPath::Segment>::const_iterator;
876 :
877 : Node &find_closest_module (Node &starting_point);
878 :
879 : tl::optional<SegIterator>
880 : find_starting_point (const std::vector<ResolutionPath::Segment> &segments,
881 : std::reference_wrapper<Node> &starting_point,
882 : std::function<void (Usage, Definition, Namespace)>
883 : insert_segment_resolution,
884 : std::vector<Error> &collect_errors);
885 :
886 : /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
887 : struct DfsResult
888 : {
889 : Node &first;
890 : std::string second;
891 : };
892 : struct ConstDfsResult
893 : {
894 : const Node &first;
895 : std::string second;
896 : };
897 :
898 : // FIXME: Documentation
899 : tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
900 : tl::optional<ConstDfsResult> dfs (const Node &starting_point,
901 : NodeId to_find) const;
902 : // FIXME: Documentation
903 : tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
904 : tl::optional<const Rib &> dfs_rib (const Node &starting_point,
905 : NodeId to_find) const;
906 : // FIXME: Documentation
907 : tl::optional<Node &> dfs_node (Node &starting_point, NodeId to_find);
908 : tl::optional<const Node &> dfs_node (const Node &starting_point,
909 : NodeId to_find) const;
910 :
911 54570 : bool forward_declared (NodeId definition, NodeId usage)
912 : {
913 54570 : if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
914 : return false;
915 :
916 1308 : const auto &definition_rib = dfs_rib (cursor (), definition);
917 :
918 1308 : if (!definition_rib)
919 : return false;
920 :
921 : return (definition_rib
922 1 : && definition_rib.value ().kind == Rib::Kind::ForwardTypeParamBan);
923 : }
924 :
925 214779 : void map_usage (Usage usage, Definition definition)
926 : {
927 214779 : resolved_nodes.emplace (usage, definition);
928 :
929 : // auto inserted = resolved_nodes.emplace (usage, definition);
930 :
931 : // is that valid?
932 : // FIXME: Yikes
933 : // rust_assert (inserted.first->first.id == definition.id);
934 : }
935 :
936 3207152 : tl::optional<NodeId> lookup (NodeId usage) const
937 : {
938 3207152 : auto it = resolved_nodes.find (Usage (usage));
939 :
940 3207152 : if (it == resolved_nodes.end ())
941 77734 : return tl::nullopt;
942 :
943 3129418 : return it->second.id;
944 : }
945 :
946 : tl::expected<Definition, LookupFinalizeError>
947 : find_leaf_definition (const NodeId &key) const;
948 :
949 : // Flattening is not needed for now but should be used later?
950 : #if 0
951 : /**
952 : * Look at NameResolutionContext::flatten - This is the inner working function
953 : * which works on one specific namespace, while NameResolutionContext::flatten
954 : * calls flatten for every namespace
955 : */
956 : void flatten ();
957 : #endif
958 :
959 : /* Map of "usage" nodes which have been resolved to a "definition" node */
960 : std::map<Usage, Definition> resolved_nodes;
961 : };
962 :
963 : } // namespace Resolver2_0
964 : } // namespace Rust
965 :
966 : #include "rust-forever-stack.hxx"
967 :
968 : #endif // !RUST_FOREVER_STACK_H
|
