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 shadowable definition in the innermost `Rib` in 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_shadowable (Identifier name,
 453                                                               NodeId id);
 454
 455   /**
 456    * Insert a new definition at the root of this stack
 457    *
 458    * @param name The name of the definition
 459    * @param id Its NodeId
 460    *
 461    * @return `DuplicateNameError` if that node was already present in the Rib,
 462    * the node's `NodeId` otherwise.
 463    *
 464    * @aborts if there are no `Rib`s inserted in the current map, this function
 465    *         aborts the program.
 466    */
 467   tl::expected<NodeId, DuplicateNameError> insert_at_root (Identifier name,
 468                                                            NodeId id);
 469
 470   /* Access the innermost `Rib` in this map */
 471   Rib &peek ();
 472   const Rib &peek () const;
 473
 474   /**
 475    * Reverse iter on all ribs from the innermost one to the outermost one,
 476    * trying to find a name. This is the default algorithm.
 477    * This function gets specialized based on the Rib::Kind
 478    * this way, we ensure a proper resolution algorithm at the type level
 479    *
 480    * @param name Name of the identifier to locate in this scope or an outermore
 481    *        scope
 482    *
 483    * @return a valid option with the Definition if the identifier is present in
 484    * the current map, an empty one otherwise.
 485    */
 486   tl::optional<Rib::Definition> get (const Identifier &name);
 487
 488   /**
 489    * Resolve a path to its definition in the current `ForeverStack`
 490    *
 491    * // TODO: Add documentation for `segments`
 492    *
 493    * @return a valid option with the Definition if the path is present in the
 494    *         current map, an empty one otherwise.
 495    */
 496   template <typename S>
 497   tl::optional<Rib::Definition> resolve_path (const std::vector<S> &segments);
 498
 499   // FIXME: Documentation
 500   tl::optional<Resolver::CanonicalPath> to_canonical_path (NodeId id);
 501
 502   // FIXME: Documentation
 503   tl::optional<Rib &> to_rib (NodeId rib_id);
 504
 505   std::string as_debug_string ();
 506
 507 private:
 508   /**
 509    * A link between two Nodes in our trie data structure. This class represents
 510    * the edges of the graph
 511    */
 512   class Link
 513   {
 514   public:
 515     Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
 516
 517     bool compare (const Link &other) const { return id < other.id; }
 518
 519     NodeId id;
 520     tl::optional<Identifier> path;
 521   };
 522
 523   /* Link comparison class, which we use in a Node's `children` map */
 524   class LinkCmp
 525   {
 526   public:
 527     bool operator() (const Link &lhs, const Link &rhs) const
 528     {
 529       return lhs.compare (rhs);
 530     }
 531   };
 532
 533   class Node
 534   {
 535   public:
 536     Node (Rib rib, NodeId id) : rib (rib), id (id) {}
 537     Node (Rib rib, NodeId id, Node &parent)
 538       : rib (rib), id (id), parent (parent)
 539     {}
 540
 541     bool is_root () const;
 542     bool is_leaf () const;
 543
 544     void insert_child (Link link, Node child);
 545
 546     Rib rib; // this is the "value" of the node - the data it keeps.
 547     std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
 548
 549     NodeId id; // The node id of the Node's scope
 550
 551     tl::optional<Node &> parent; // `None` only if the node is a root
 552   };
 553
 554   /* Should we keep going upon seeing a Rib? */
 555   enum class KeepGoing
 556   {
 557     Yes,
 558     No,
 559   };
 560
 561   /* Add a new Rib to the stack. This is an internal method */
 562   void push_inner (Rib rib, Link link);
 563
 564   /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
 565   void reverse_iter (std::function<KeepGoing (Node &)> lambda);
 566
 567   /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
 568   void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
 569
 570   Node &cursor ();
 571   const Node &cursor () const;
 572   void update_cursor (Node &new_cursor);
 573
 574   Node root;
 575   std::reference_wrapper<Node> cursor_reference;
 576
 577   void stream_rib (std::stringstream &stream, const Rib &rib,
 578                    const std::string &next, const std::string &next_next);
 579   void stream_node (std::stringstream &stream, unsigned indentation,
 580                     const Node &node);
 581
 582   /* Helper types and functions for `resolve_path` */
 583
 584   template <typename S>
 585   using SegIterator = typename std::vector<S>::const_iterator;
 586
 587   Node &find_closest_module (Node &starting_point);
 588
 589   template <typename S>
 590   tl::optional<SegIterator<S>>
 591   find_starting_point (const std::vector<S> &segments, Node &starting_point);
 592
 593   template <typename S>
 594   tl::optional<Node &> resolve_segments (Node &starting_point,
 595                                          const std::vector<S> &segments,
 596                                          SegIterator<S> iterator);
 597
 598   /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
 599   struct DfsResult
 600   {
 601     Node &first;
 602     std::string second;
 603   };
 604
 605   // FIXME: Documentation
 606   tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
 607   // FIXME: Documentation
 608   tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
 609 };
 610
 611 } // namespace Resolver2_0
 612 } // namespace Rust
 613
 614 #include "rust-forever-stack.hxx"
 615
 616 #endif // !RUST_FOREVER_STACK_H