gcc/rust/resolve/rust-forever-stack.h

   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   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     : root (Node (Rib (Rib::Kind::Normal), UNKNOWN_NODEID)),
 402       cursor_reference (root)
 403   {
 404     rust_assert (root.is_root ());
 405     rust_assert (root.is_leaf ());
 406   }
 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   class Link
 498   {
 499   public:
 500     Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
 501
 502     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     bool operator() (const Link &lhs, const Link &rhs) const
 513     {
 514       return lhs.compare (rhs);
 515     }
 516   };
 517
 518   class Node
 519   {
 520   public:
 521     Node (Rib rib, NodeId id) : rib (rib), id (id) {}
 522     Node (Rib rib, NodeId id, Node &parent)
 523       : 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