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 180350 : class ResolutionPath
556 : {
557 : public:
558 : template <typename T>
559 90175 : ResolutionPath (const std::vector<T> &segments_in, NodeId node_id)
560 90175 : : node_id (node_id)
561 : {
562 90175 : segments.clear ();
563 90175 : segments.reserve (segments_in.size ());
564 207918 : for (auto &outer_seg : segments_in)
565 : {
566 117743 : 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 117351 : auto &seg = unwrap_type_segment (outer_seg);
575 :
576 117351 : Segment new_seg;
577 117351 : new_seg.name = seg.as_string ();
578 117351 : new_seg.node_id = unwrap_segment_node_id (outer_seg);
579 117351 : new_seg.locus = seg.get_locus ();
580 117351 : segments.push_back (std::move (new_seg));
581 : }
582 90175 : }
583 :
584 90175 : ResolutionPath () : node_id (UNKNOWN_NODEID) {}
585 :
586 469404 : struct Segment
587 : {
588 : std::string name;
589 : NodeId node_id;
590 : location_t locus;
591 :
592 51115 : bool is_super_path_seg () const { return name.compare ("super") == 0; }
593 75414 : bool is_crate_path_seg () const { return name.compare ("crate") == 0; }
594 80690 : 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 94054 : tl::optional<std::pair<LangItem::Kind, NodeId>> get_lang_prefix () const
599 : {
600 94054 : return lang_prefix;
601 : }
602 :
603 94054 : const std::vector<Segment> &get_segments () const { return segments; }
604 :
605 : NodeId get_node_id () const { return node_id; }
606 :
607 94054 : std::string as_string () const
608 : {
609 94054 : std::string ret;
610 94054 : if (lang_prefix)
611 392 : ret = "#[lang]::";
612 219562 : for (auto &seg : segments)
613 251016 : ret += "::" + seg.name;
614 94054 : 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 : template <Namespace N> class ForeverStack
624 : {
625 : public:
626 18736 : ForeverStack ()
627 18736 : : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)),
628 37472 : lang_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID, root)),
629 18736 : extern_prelude (Node (Rib (Rib::Kind::Prelude), UNKNOWN_NODEID)),
630 18736 : cursor_reference (root)
631 : {
632 18736 : rust_assert (root.is_root ());
633 18736 : rust_assert (root.is_leaf ());
634 :
635 : // TODO: Should we be using the forever stack root as the crate scope?
636 : // TODO: Is this how we should be getting the crate node id?
637 18736 : auto &mappings = Analysis::Mappings::get ();
638 18736 : root.id = *mappings.crate_num_to_nodeid (mappings.get_current_crate ());
639 18736 : }
640 :
641 : /**
642 : * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
643 : * and the stack's cursor is simply moved to this existing Rib.
644 : *
645 : * @param rib The Rib to push
646 : * @param id The NodeId of the node for which the Rib was created. For
647 : * example, if a Rib is created because a lexical scope is entered,
648 : * then `id` is that `BlockExpr`'s NodeId.
649 : * @param path An optional path if the Rib was created due to a "named"
650 : * lexical scope, like a module's.
651 : */
652 : void push (Rib::Kind rib_kind, NodeId id, tl::optional<Identifier> path = {});
653 :
654 : /**
655 : * Pop the innermost Rib from the stack
656 : */
657 : void pop ();
658 :
659 : /**
660 : * Insert a new 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 (Identifier name, NodeId id);
672 :
673 : tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
674 : NodeId id);
675 :
676 : /**
677 : * Insert a new shadowable definition in the innermost `Rib` in this stack
678 : *
679 : * @param name The name of the definition
680 : * @param id Its NodeId
681 : *
682 : * @return `DuplicateNameError` if that node was already present in the Rib,
683 : * the node's `NodeId` otherwise.
684 : *
685 : * @aborts if there are no `Rib`s inserted in the current map, this function
686 : * aborts the program.
687 : */
688 : tl::expected<NodeId, DuplicateNameError> insert_shadowable (Identifier name,
689 : NodeId id);
690 :
691 : /**
692 : * Insert a new glob-originated definition in the innermost `Rib` in this
693 : * stack
694 : *
695 : * @param name The name of the definition
696 : * @param id Its NodeId
697 : *
698 : * @return `DuplicateNameError` if that node was already present in the Rib,
699 : * the node's `NodeId` otherwise.
700 : *
701 : * @aborts if there are no `Rib`s inserted in the current map, this function
702 : * aborts the program.
703 : */
704 : tl::expected<NodeId, DuplicateNameError> insert_globbed (Identifier name,
705 : NodeId id);
706 :
707 : /**
708 : * Insert a new definition at the root of this stack
709 : *
710 : * @param name The name of the definition
711 : * @param id Its NodeId
712 : *
713 : * @return `DuplicateNameError` if that node was already present in the Rib,
714 : * the node's `NodeId` otherwise.
715 : *
716 : * @aborts if there are no `Rib`s inserted in the current map, this function
717 : * aborts the program.
718 : */
719 : tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
720 : NodeId id);
721 :
722 : /**
723 : * Insert an item within the lang prelude
724 : *
725 : * @param name The name of the definition
726 : * @param id Its NodeId
727 : */
728 : void insert_lang_prelude (Identifier name, NodeId id);
729 :
730 : /* Access the innermost `Rib` in this map */
731 : Rib &peek ();
732 : const Rib &peek () const;
733 :
734 : /**
735 : * Reverse iter on all ribs from the innermost one to the outermost one,
736 : * trying to find a name. This is the default algorithm.
737 : * This function gets specialized based on the Rib::Kind
738 : * this way, we ensure a proper resolution algorithm at the type level
739 : *
740 : * @param name Name of the identifier to locate in this scope or an outermore
741 : * scope
742 : *
743 : * @return a valid option with the Definition if the identifier is present in
744 : * the current map, an empty one otherwise.
745 : */
746 : tl::optional<Rib::Definition> get (const Identifier &name);
747 : tl::optional<Rib::Definition> get_lang_prelude (const Identifier &name);
748 : tl::optional<Rib::Definition> get_lang_prelude (const std::string &name);
749 : tl::optional<Rib::Definition> get_from_prelude (NodeId prelude,
750 : const Identifier &name);
751 :
752 : /**
753 : * Resolve a path to its definition in the current `ForeverStack`
754 : *
755 : * // TODO: Add documentation for `segments`
756 : *
757 : * @return a valid option with the Definition if the path is present in the
758 : * current map, an empty one otherwise.
759 : */
760 : tl::optional<Rib::Definition> resolve_path (
761 : const ResolutionPath &path, ResolutionMode mode,
762 : std::function<void (Usage, Definition)> insert_segment_resolution,
763 : std::vector<Error> &collect_errors);
764 : tl::optional<Rib::Definition> resolve_path (
765 : const ResolutionPath &path, ResolutionMode mode,
766 : std::function<void (Usage, Definition)> insert_segment_resolution,
767 : std::vector<Error> &collect_errors, NodeId starting_point_id);
768 :
769 : // FIXME: Documentation
770 : tl::optional<Rib &> to_rib (NodeId rib_id);
771 : tl::optional<const Rib &> to_rib (NodeId rib_id) const;
772 :
773 : std::string as_debug_string () const;
774 :
775 : /**
776 : * Used to check if a module is a descendant of another module
777 : * Intended for use in the privacy checker
778 : */
779 : bool is_module_descendant (NodeId parent, NodeId child) const;
780 :
781 : private:
782 : /**
783 : * A link between two Nodes in our trie data structure. This class represents
784 : * the edges of the graph
785 : */
786 5336733 : class Link
787 : {
788 : public:
789 1596597 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
790 :
791 4490355 : bool compare (const Link &other) const { return id < other.id; }
792 :
793 : NodeId id;
794 : tl::optional<Identifier> path;
795 : };
796 :
797 : /* Link comparison class, which we use in a Node's `children` map */
798 : class LinkCmp
799 : {
800 : public:
801 4490355 : bool operator() (const Link &lhs, const Link &rhs) const
802 : {
803 4490355 : return lhs.compare (rhs);
804 : }
805 : };
806 :
807 : class Node
808 : {
809 : public:
810 37472 : Node (Rib rib, NodeId id) : rib (rib), id (id) {}
811 1601281 : Node (Rib rib, NodeId id, Node &parent)
812 1601281 : : rib (rib), id (id), parent (parent)
813 : {}
814 :
815 : bool is_root () const;
816 : bool is_prelude () const;
817 : bool is_leaf () const;
818 :
819 : void insert_child (Link link, Node child);
820 :
821 : Rib rib; // this is the "value" of the node - the data it keeps.
822 : std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
823 :
824 : NodeId id; // The node id of the Node's scope
825 :
826 : tl::optional<Node &> parent; // `None` only if the node is a root
827 : };
828 :
829 : /**
830 : * Private overloads which allow specifying a starting point
831 : */
832 :
833 : tl::optional<Rib::Definition> get (Node &start, const Identifier &name);
834 :
835 : tl::optional<Rib::Definition> resolve_path (
836 : const ResolutionPath &path, ResolutionMode mode,
837 : std::function<void (Usage, Definition)> insert_segment_resolution,
838 : std::vector<Error> &collect_errors,
839 : std::reference_wrapper<Node> starting_point);
840 :
841 : /* Should we keep going upon seeing a Rib? */
842 : enum class KeepGoing
843 : {
844 : Yes,
845 : No,
846 : };
847 :
848 : /* Add a new Rib to the stack. This is an internal method */
849 : void push_inner (Rib rib, Link link);
850 :
851 : /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
852 : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
853 : void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
854 :
855 : /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
856 : void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
857 : void reverse_iter (const Node &start,
858 : std::function<KeepGoing (const Node &)> lambda) const;
859 :
860 : Node &cursor ();
861 : const Node &cursor () const;
862 : void update_cursor (Node &new_cursor);
863 :
864 : /* The forever stack's actual nodes */
865 : Node root;
866 : /*
867 : * A special prelude node used currently for resolving language builtins
868 : * It has the root node as a parent, and acts as a "special case" for name
869 : * resolution
870 : */
871 : Node lang_prelude;
872 :
873 : /*
874 : * The extern prelude, used for resolving external crates
875 : */
876 : Node extern_prelude;
877 :
878 : std::reference_wrapper<Node> cursor_reference;
879 :
880 : void stream_rib (std::stringstream &stream, const Rib &rib,
881 : const std::string &next, const std::string &next_next) const;
882 : void stream_node (std::stringstream &stream, unsigned indentation,
883 : const Node &node, unsigned depth = 0) const;
884 :
885 : /* Helper types and functions for `resolve_path` */
886 :
887 : using SegIterator =
888 : typename std::vector<ResolutionPath::Segment>::const_iterator;
889 :
890 : Node &find_closest_module (Node &starting_point);
891 :
892 : tl::optional<SegIterator> find_starting_point (
893 : const std::vector<ResolutionPath::Segment> &segments,
894 : std::reference_wrapper<Node> &starting_point,
895 : std::function<void (Usage, Definition)> insert_segment_resolution,
896 : std::vector<Error> &collect_errors);
897 :
898 : tl::optional<Node &> resolve_segments (
899 : Node &starting_point, const std::vector<ResolutionPath::Segment> &segments,
900 : SegIterator iterator,
901 : std::function<void (Usage, Definition)> insert_segment_resolution,
902 : std::vector<Error> &collect_errors);
903 :
904 : tl::optional<Rib::Definition> resolve_final_segment (Node &final_node,
905 : std::string &seg_name,
906 : bool is_lower_self);
907 :
908 : /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
909 : struct DfsResult
910 : {
911 : Node &first;
912 : std::string second;
913 : };
914 : struct ConstDfsResult
915 : {
916 : const Node &first;
917 : std::string second;
918 : };
919 :
920 : // FIXME: Documentation
921 : tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
922 : tl::optional<ConstDfsResult> dfs (const Node &starting_point,
923 : NodeId to_find) const;
924 : // FIXME: Documentation
925 : tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
926 : tl::optional<const Rib &> dfs_rib (const Node &starting_point,
927 : NodeId to_find) const;
928 : // FIXME: Documentation
929 : tl::optional<Node &> dfs_node (Node &starting_point, NodeId to_find);
930 : tl::optional<const Node &> dfs_node (const Node &starting_point,
931 : NodeId to_find) const;
932 :
933 : public:
934 53806 : bool forward_declared (NodeId definition, NodeId usage)
935 : {
936 53806 : if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
937 : return false;
938 :
939 1297 : const auto &definition_rib = dfs_rib (cursor (), definition);
940 :
941 1297 : if (!definition_rib)
942 : return false;
943 :
944 : return (definition_rib
945 1 : && definition_rib.value ().kind == Rib::Kind::ForwardTypeParamBan);
946 : }
947 : };
948 :
949 : } // namespace Resolver2_0
950 : } // namespace Rust
951 :
952 : #include "rust-forever-stack.hxx"
953 :
954 : #endif // !RUST_FOREVER_STACK_H
|
