Branch data Line data Source code
1 : : // Copyright (C) 2020-2024 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 : :
29 : : namespace Rust {
30 : : namespace Resolver2_0 {
31 : :
32 : : /**
33 : :
34 : : Let's look at our stack for resolving and traversing the following Rust code:
35 : :
36 : : ```rust
37 : : mod foo {
38 : : mod bar {
39 : : fn outer() {
40 : : fn inner() {}
41 : : }
42 : :
43 : : fn another() {}
44 : : }
45 : : }
46 : : ```
47 : :
48 : : We start by creating the stack, which contains only one rib - the crate's. We
49 : : won't look in details on how different namespaces end up with different stacks,
50 : : and will only consider the "value" namespace for this example. Modules do not
51 : : get added to the value namespace, but functions do:
52 : :
53 : : ```rust
54 : : let _ = foo; // foo is a module, invalid Rust code
55 : : let _ = outer; // outer is a function, ok!
56 : : ```
57 : :
58 : : So passing each module will create a new Rib, but not add that module's node to
59 : : the Rib.
60 : :
61 : : The current cursor of the stack will be denoted with `-->`: an arrow pointing to
62 : : the current rib.
63 : :
64 : : When we start the `TopLevel` pass on the crate we are compiling, we only see the
65 : : top rib, which is empty at first:
66 : :
67 : : ┌───────────────┐
68 : : │ │
69 : : --> │ │
70 : : │ │
71 : : └───────────────┘
72 : :
73 : : We pass through our first module, and emplace another Rib: Another "scope" is
74 : : created, and it impacts name resolution rules.
75 : :
76 : : ┌───────────────┐
77 : : │ │
78 : : │ │
79 : : │ │
80 : : └───────┬───────┘
81 : : │
82 : : foo │
83 : : │
84 : : ▼
85 : : ┌───────────────┐
86 : : │ │
87 : : --> │ │
88 : : │ │
89 : : └───────────────┘
90 : :
91 : : Notice that we have moved the cursor to the newly-created Rib, and that we have
92 : : added a path between the two ribs - this is a `Link`. A link contains
93 : : information such as the scope's NodeId, as well as an optional path - present
94 : : only when the scope is named. This allows us to easily fetch AST nodes based on
95 : : their canonical path, or build a canonical path from a NodeId. It also makes it
96 : : really easy to do complex path name resolution, such as `super::super::<item>`.
97 : : As mentioned earlier, modules are not present in the value namespace, so our new
98 : : rib is also empty. Let's pass through the second module:
99 : :
100 : : ┌───────────────┐
101 : : │ │
102 : : │ │
103 : : │ │
104 : : └───────┬───────┘
105 : : │
106 : : foo │
107 : : │
108 : : ▼
109 : : ┌───────────────┐
110 : : │ │
111 : : │ │
112 : : │ │
113 : : └───────┬───────┘
114 : : │
115 : : bar │
116 : : │
117 : : ▼
118 : : ┌───────────────┐
119 : : │ │
120 : : --> │ │
121 : : │ │
122 : : └───────────────┘
123 : :
124 : : Once again, the new rib is empty, and we have a link with a path. We now go
125 : : through each item in the `bar` module and visit them. The first item is a
126 : : function, `outer` - upon being visited, it adds itself to the current rib.
127 : :
128 : : ┌───────────────┐
129 : : │ │
130 : : │ │
131 : : │ │
132 : : └───────┬───────┘
133 : : │
134 : : foo │
135 : : │
136 : : ▼
137 : : ┌───────────────┐
138 : : │ │
139 : : │ │
140 : : │ │
141 : : └───────┬───────┘
142 : : │
143 : : bar │
144 : : │
145 : : ▼
146 : : ┌───────────────┐
147 : : │outer │
148 : : --> │ │
149 : : │ │
150 : : └───────────────┘
151 : :
152 : : We now visit `outer`'s definition. This creates a new Rib, as functions can have
153 : : arguments, whose declaration only lives for the function's scope.
154 : :
155 : : ┌───────────────┐
156 : : │ │
157 : : │ │
158 : : │ │
159 : : └───────┬───────┘
160 : : │
161 : : foo │
162 : : │
163 : : ▼
164 : : ┌───────────────┐
165 : : │ │
166 : : │ │
167 : : │ │
168 : : └───────┬───────┘
169 : : │
170 : : bar │
171 : : │
172 : : ▼
173 : : ┌───────────────┐
174 : : │outer │
175 : : │ │
176 : : │ │
177 : : └───────┬───────┘
178 : : │
179 : : <anon> │
180 : : │
181 : : ▼
182 : : ┌───────────────┐
183 : : │ │
184 : : --> │ │
185 : : │ │
186 : : └───────────────┘
187 : :
188 : : This rib is anonymous (the link to it does not have a path), because we cannot
189 : : refer to a function's inner items from the outside:
190 : :
191 : : ```rust
192 : : pub mod a {
193 : : pub fn foo() {}
194 : : }
195 : :
196 : : pub fn b() {
197 : : pub fn foo() {}
198 : : }
199 : :
200 : : fn main() {
201 : : a::foo(); // ok
202 : : b::foo(); // ko!
203 : : }
204 : : ```
205 : :
206 : : We visit the function's block, which contain a single declaration, a function
207 : : named `inner`. It adds itself to the current rib.
208 : :
209 : : ┌───────────────┐
210 : : │ │
211 : : │ │
212 : : │ │
213 : : └───────┬───────┘
214 : : │
215 : : foo │
216 : : │
217 : : ▼
218 : : ┌───────────────┐
219 : : │ │
220 : : │ │
221 : : │ │
222 : : └───────┬───────┘
223 : : │
224 : : bar │
225 : : │
226 : : ▼
227 : : ┌───────────────┐
228 : : │outer │
229 : : │ │
230 : : │ │
231 : : └───────┬───────┘
232 : : │
233 : : <anon> │
234 : : │
235 : : ▼
236 : : ┌───────────────┐
237 : : │inner │
238 : : --> │ │
239 : : │ │
240 : : └───────────────┘
241 : :
242 : : We visit `inner`, which yields a rib but no other declaration.
243 : :
244 : : ┌───────────────┐
245 : : │ │
246 : : │ │
247 : : │ │
248 : : └───────┬───────┘
249 : : │
250 : : foo │
251 : : │
252 : : ▼
253 : : ┌───────────────┐
254 : : │ │
255 : : │ │
256 : : │ │
257 : : └───────┬───────┘
258 : : │
259 : : bar │
260 : : │
261 : : ▼
262 : : ┌───────────────┐
263 : : │outer │
264 : : │ │
265 : : │ │
266 : : └───────┬───────┘
267 : : │
268 : : <anon> │
269 : : │
270 : : ▼
271 : : ┌───────────────┐
272 : : │inner │
273 : : │ │
274 : : │ │
275 : : └───────────────┘
276 : : │
277 : : <anon> │
278 : : │
279 : : ▼
280 : : ┌───────────────┐
281 : : │ │
282 : : --> │ │
283 : : │ │
284 : : └───────────────┘
285 : :
286 : : We are now at the end of the `inner` function, and we want to pop the current
287 : : scope. Instead of deleting the current rib, we simply move the cursor backwards.
288 : : This allows us to keep track of the existing information and access it in later
289 : : name resolution passes. We then finish visiting `outer`, then go back to our
290 : : `bar` module. This is what our stack looks like after this. Note how the only
291 : : difference is the cursor's location.
292 : :
293 : : ┌───────────────┐
294 : : │ │
295 : : │ │
296 : : │ │
297 : : └───────┬───────┘
298 : : │
299 : : foo │
300 : : │
301 : : ▼
302 : : ┌───────────────┐
303 : : │ │
304 : : │ │
305 : : │ │
306 : : └───────┬───────┘
307 : : │
308 : : bar │
309 : : │
310 : : ▼
311 : : ┌───────────────┐
312 : : │outer │
313 : : --> │ │
314 : : │ │
315 : : └───────┬───────┘
316 : : │
317 : : <anon> │
318 : : │
319 : : ▼
320 : : ┌───────────────┐
321 : : │inner │
322 : : │ │
323 : : │ │
324 : : └───────────────┘
325 : : │
326 : : <anon> │
327 : : │
328 : : ▼
329 : : ┌───────────────┐
330 : : │ │
331 : : │ │
332 : : │ │
333 : : └───────────────┘
334 : :
335 : : We then visit the remaining `bar` items, which are composed of the `another`
336 : : function. It adds itself to the current rib. This function contains no
337 : : declarations, but it still creates a Rib upon being visited. We then finish our
338 : : visit of `bar`, which marks the end of our visit of `foo`, which marks the end
339 : : of our `TopLevel` name resolution pass.
340 : :
341 : : ┌───────────────┐
342 : : │ │
343 : : --> │ │
344 : : │ │
345 : : └───────┬───────┘
346 : : │
347 : : foo │
348 : : │
349 : : ▼
350 : : ┌───────────────┐
351 : : │ │
352 : : │ │
353 : : │ │
354 : : └───────┬───────┘
355 : : │
356 : : bar │
357 : : │
358 : : ▼
359 : : ┌───────────────┐
360 : : │outer │
361 : : │another │
362 : : │ │
363 : : └───────┬──┬────┘
364 : : │ │ <anon>
365 : : <anon> │ └────────────────────┐
366 : : │ │
367 : : ▼ ▼
368 : : ┌───────────────┐ ┌───────────────┐
369 : : │inner │ │ │
370 : : │ │ │ │
371 : : │ │ │ │
372 : : └───────┬───────┘ └───────────────┘
373 : : │
374 : : <anon> │
375 : : │
376 : : ▼
377 : : ┌───────────────┐
378 : : │ │
379 : : │ │
380 : : │ │
381 : : └───────────────┘
382 : :
383 : : We now have a stack with a lot of ribs, prime for the `Early` and `Late` name
384 : : resolution passes. We will revisit the ribs we created in these passes, and we
385 : : won't need to allocate or create new ones: because they will still be present in
386 : : the stack, we will simply move our cursor to these ribs. In this case, there is
387 : : nothing to do, since there are no uses of our definitions, as the Rust code we
388 : : are name-resolving is not really interesting. You'll also note that our
389 : : `TopLevel` pass did not resolve a whole lot: all it did was create new ribs, and
390 : : empty ones at that. The `Early` pass will not go further, since our code does
391 : : not contain any imports, macro definitions or macro invocations. You can look at
392 : : this pass's documentation for more details on this resolution process.
393 : :
394 : : **/
395 : : template <Namespace N> class ForeverStack
396 : : {
397 : : public:
398 : 21028 : ForeverStack ()
399 : : // FIXME: Is that valid? Do we use the root? If yes, we should give the
400 : : // crate's node id to ForeverStack's constructor
401 : 21028 : : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)),
402 : 21028 : cursor_reference (root)
403 : : {
404 : 21028 : rust_assert (root.is_root ());
405 : 21028 : rust_assert (root.is_leaf ());
406 : 21028 : }
407 : :
408 : : /**
409 : : * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
410 : : * and the stack's cursor is simply moved to this existing Rib.
411 : : *
412 : : * @param rib The Rib to push
413 : : * @param id The NodeId of the node for which the Rib was created. For
414 : : * example, if a Rib is created because a lexical scope is entered,
415 : : * then `id` is that `BlockExpr`'s NodeId.
416 : : * @param path An optional path if the Rib was created due to a "named"
417 : : * lexical scope, like a module's.
418 : : */
419 : : void push (Rib rib, NodeId id, tl::optional<Identifier> path = {});
420 : :
421 : : /**
422 : : * Pop the innermost Rib from the stack
423 : : */
424 : : void pop ();
425 : :
426 : : /**
427 : : * Insert a new definition in the innermost `Rib` in this stack
428 : : *
429 : : * @param name The name of the definition
430 : : * @param id Its NodeId
431 : : *
432 : : * @return `DuplicateNameError` if that node was already present in the Rib,
433 : : * the node's `NodeId` otherwise.
434 : : *
435 : : * @aborts if there are no `Rib`s inserted in the current map, this function
436 : : * aborts the program.
437 : : */
438 : : tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id);
439 : :
440 : : /**
441 : : * Insert a new definition at the root of this stack
442 : : *
443 : : * @param name The name of the definition
444 : : * @param id Its NodeId
445 : : *
446 : : * @return `DuplicateNameError` if that node was already present in the Rib,
447 : : * the node's `NodeId` otherwise.
448 : : *
449 : : * @aborts if there are no `Rib`s inserted in the current map, this function
450 : : * aborts the program.
451 : : */
452 : : tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
453 : : NodeId id);
454 : :
455 : : /* Access the innermost `Rib` in this map */
456 : : Rib &peek ();
457 : : const Rib &peek () const;
458 : :
459 : : /**
460 : : * Reverse iter on all ribs from the innermost one to the outermost one,
461 : : * trying to find a name. This is the default algorithm.
462 : : * This function gets specialized based on the Rib::Kind
463 : : * this way, we ensure a proper resolution algorithm at the type level
464 : : *
465 : : * @param name Name of the identifier to locate in this scope or an outermore
466 : : * scope
467 : : *
468 : : * @return a valid option with the NodeId if the identifier is present in the
469 : : * current map, an empty one otherwise.
470 : : */
471 : : tl::optional<NodeId> get (const Identifier &name);
472 : :
473 : : /**
474 : : * Resolve a path to its definition in the current `ForeverStack`
475 : : *
476 : : * // TODO: Add documentation for `segments`
477 : : *
478 : : * @return a valid option with the NodeId if the path is present in the
479 : : * current map, an empty one otherwise.
480 : : */
481 : : template <typename S>
482 : : tl::optional<NodeId> resolve_path (const std::vector<S> &segments);
483 : :
484 : : // FIXME: Documentation
485 : : tl::optional<Resolver::CanonicalPath> to_canonical_path (NodeId id);
486 : :
487 : : // FIXME: Documentation
488 : : tl::optional<Rib &> to_rib (NodeId rib_id);
489 : :
490 : : std::string as_debug_string ();
491 : :
492 : : private:
493 : : /**
494 : : * A link between two Nodes in our trie data structure. This class represents
495 : : * the edges of the graph
496 : : */
497 : 2573 : class Link
498 : : {
499 : : public:
500 : 744 : Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
501 : :
502 : 1191 : bool compare (const Link &other) const { return id < other.id; }
503 : :
504 : : NodeId id;
505 : : tl::optional<Identifier> path;
506 : : };
507 : :
508 : : /* Link comparison class, which we use in a Node's `children` map */
509 : : class LinkCmp
510 : : {
511 : : public:
512 : 1191 : bool operator() (const Link &lhs, const Link &rhs) const
513 : : {
514 : 1191 : return lhs.compare (rhs);
515 : : }
516 : : };
517 : :
518 : : class Node
519 : : {
520 : : public:
521 : 21028 : Node (Rib rib, NodeId id) : rib (rib), id (id) {}
522 : 744 : Node (Rib rib, NodeId id, Node &parent)
523 : 744 : : rib (rib), id (id), parent (parent)
524 : : {}
525 : :
526 : : bool is_root () const;
527 : : bool is_leaf () const;
528 : :
529 : : void insert_child (Link link, Node child);
530 : :
531 : : Rib rib; // this is the "value" of the node - the data it keeps.
532 : : std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
533 : :
534 : : NodeId id; // The node id of the Node's scope
535 : :
536 : : tl::optional<Node &> parent; // `None` only if the node is a root
537 : : };
538 : :
539 : : /* Should we keep going upon seeing a Rib? */
540 : : enum class KeepGoing
541 : : {
542 : : Yes,
543 : : No,
544 : : };
545 : :
546 : : /* Add a new Rib to the stack. This is an internal method */
547 : : void push_inner (Rib rib, Link link);
548 : :
549 : : /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
550 : : void reverse_iter (std::function<KeepGoing (Node &)> lambda);
551 : :
552 : : /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
553 : : void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
554 : :
555 : : Node &cursor ();
556 : : const Node &cursor () const;
557 : : void update_cursor (Node &new_cursor);
558 : :
559 : : Node root;
560 : : std::reference_wrapper<Node> cursor_reference;
561 : :
562 : : void stream_rib (std::stringstream &stream, const Rib &rib,
563 : : const std::string &next, const std::string &next_next);
564 : : void stream_node (std::stringstream &stream, unsigned indentation,
565 : : const Node &node);
566 : :
567 : : /* Helper types and functions for `resolve_path` */
568 : :
569 : : template <typename S>
570 : : using SegIterator = typename std::vector<S>::const_iterator;
571 : :
572 : : Node &find_closest_module (Node &starting_point);
573 : :
574 : : template <typename S>
575 : : tl::optional<SegIterator<S>>
576 : : find_starting_point (const std::vector<S> &segments, Node &starting_point);
577 : :
578 : : template <typename S>
579 : : tl::optional<Node &> resolve_segments (Node &starting_point,
580 : : const std::vector<S> &segments,
581 : : SegIterator<S> iterator);
582 : :
583 : : /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
584 : :
585 : : // FIXME: Documentation
586 : : tl::optional<std::pair<Node &, std::string>> dfs (Node &starting_point,
587 : : NodeId to_find);
588 : : // FIXME: Documentation
589 : : tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
590 : : };
591 : :
592 : : } // namespace Resolver2_0
593 : : } // namespace Rust
594 : :
595 : : #include "rust-forever-stack.hxx"
596 : :
597 : : #endif // !RUST_FOREVER_STACK_H
|
