LCOV - code coverage report
Current view: top level - gcc/rust/resolve - rust-forever-stack.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 86.8 % 91 79
Test Date: 2026-11-14 16:39:50 Functions: 88.2 % 17 15
Legend: Lines:     hit not hit

            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              : enum class ResolutionMode
     399              : {
     400              :   Normal,
     401              :   FromRoot,
     402              :   FromExtern, // extern prelude
     403              : };
     404              : 
     405      4105614 : struct ResolutionPathSegment
     406              : {
     407              :   std::string name;
     408              :   NodeId node_id;
     409              :   location_t locus;
     410              : 
     411       952686 :   bool is_super_path_seg () const { return name.compare ("super") == 0; }
     412      1855103 :   bool is_crate_path_seg () const { return name.compare ("crate") == 0; }
     413      1615476 :   bool is_lower_self_seg () const { return name.compare ("self") == 0; }
     414              :   bool is_big_self_seg () const { return name.compare ("Self") == 0; }
     415              : };
     416              : 
     417      3129096 : class ResolutionPath : public RawPath<ResolutionPathSegment>
     418              : {
     419              : public:
     420              :   template <typename T>
     421      1564548 :   ResolutionPath (const RawPath<T> &path, NodeId node_id)
     422      1564548 :     : RawPath ({}, path.has_opening_scope_resolution ()), node_id (node_id)
     423              :   {
     424      1564548 :     segments.clear ();
     425      1564548 :     segments.reserve (path.get_segments ().size ());
     426      3624585 :     for (auto &outer_seg : path.get_segments ())
     427              :       {
     428      2060037 :         if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
     429              :           {
     430         7230 :             rust_assert (!lang_prefix.has_value ());
     431         7230 :             lang_prefix = std::make_pair (lang_item.value (),
     432         7230 :                                           unwrap_segment_node_id (outer_seg));
     433         7230 :             continue;
     434              :           }
     435              : 
     436      2052807 :         auto &seg = unwrap_type_segment (outer_seg);
     437              : 
     438      2052807 :         ResolutionPathSegment new_seg;
     439      2052807 :         new_seg.name = seg.as_string ();
     440      2052807 :         new_seg.node_id = unwrap_segment_node_id (outer_seg);
     441      2052807 :         new_seg.locus = seg.get_locus ();
     442      2052807 :         segments.push_back (std::move (new_seg));
     443              :       }
     444      1564548 :   }
     445              : 
     446      1564548 :   ResolutionPath () : RawPath ({}, false), node_id (UNKNOWN_NODEID) {}
     447              : 
     448      1819626 :   tl::optional<std::pair<LangItem::Kind, NodeId>> get_lang_prefix () const
     449              :   {
     450      1819626 :     return lang_prefix;
     451              :   }
     452              : 
     453              :   const std::vector<ResolutionPathSegment> &get_segments () const
     454              :   {
     455      1819626 :     return segments;
     456              :   }
     457              : 
     458              :   bool has_opening_scope_resolution () const
     459              :   {
     460              :     return opening_scope_resolution;
     461              :   }
     462              : 
     463              :   NodeId get_node_id () const { return node_id; }
     464              : 
     465            0 :   std::string as_string () const
     466              :   {
     467            0 :     std::string ret;
     468            0 :     auto it = segments.cbegin ();
     469            0 :     if (lang_prefix)
     470            0 :       ret = "#[lang]";
     471              :     else
     472              :       {
     473            0 :         ret += it->name;
     474            0 :         it++;
     475              :       }
     476              : 
     477            0 :     for (; it != segments.cend (); it++)
     478            0 :       ret += "::" + it->name;
     479            0 :     return ret;
     480              :   }
     481              : 
     482              : private:
     483              :   tl::optional<std::pair<LangItem::Kind, NodeId>> lang_prefix;
     484              :   NodeId node_id;
     485              : };
     486              : 
     487              : /**
     488              :  * Error enum for finding leaf definitions in the resolved_nodes map
     489              :  */
     490              : enum class LookupFinalizeError
     491              : {
     492              :   // Impossible - we did not find any definition corresponding to a Usage.
     493              :   // This is an internal compiler error
     494              :   NoDefinition,
     495              :   // There was a loop in the map, such as an import resolving to another
     496              :   // import which eventually resolved to the original import. Report the
     497              :   // error and stop the pipeline
     498              :   Loop,
     499              : };
     500              : 
     501              : class ForeverStackBase
     502              : {
     503              : public:
     504              :   /**
     505              :    * A link between two Nodes in our trie data structure. This class represents
     506              :    * the edges of the graph
     507              :    */
     508    703167606 :   class Link
     509              :   {
     510              :   public:
     511    231573088 :     Link (NodeId id, tl::optional<Identifier> path) : id (id), path (path) {}
     512              : 
     513   1323833102 :     bool compare (const Link &other) const { return id < other.id; }
     514              : 
     515              :     NodeId id;
     516              :     tl::optional<Identifier> path;
     517              :   };
     518              : 
     519              :   /* Link comparison class, which we use in a Node's `children` map */
     520              :   class LinkCmp
     521              :   {
     522              :   public:
     523   1323833102 :     bool operator() (const Link &lhs, const Link &rhs) const
     524              :     {
     525   1323833102 :       return lhs.compare (rhs);
     526              :     }
     527              :   };
     528              : 
     529              :   class Node
     530              :   {
     531              :   public:
     532        10668 :     Node (Rib::Kind rib_kind, NodeId id)
     533        10668 :       : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
     534        10668 :         rib_macros (rib_kind), id (id)
     535        10668 :     {}
     536    231557086 :     Node (Rib::Kind rib_kind, NodeId id, Node &parent)
     537    231557086 :       : rib_values (rib_kind), rib_types (rib_kind), rib_labels (rib_kind),
     538    231557086 :         rib_macros (rib_kind), id (id), parent (parent)
     539    231557086 :     {}
     540              : 
     541    548644020 :     const Rib &rib (Namespace n) const
     542              :     {
     543    548203823 :       switch (n)
     544              :         {
     545    185632961 :         case Namespace::Values:
     546    185632961 :           return rib_values;
     547    130150234 :         case Namespace::Types:
     548    130150234 :           return rib_types;
     549    115980597 :         case Namespace::Labels:
     550    115980597 :           return rib_labels;
     551    116880228 :         case Namespace::Macros:
     552    116880228 :           return rib_macros;
     553            0 :         default:
     554            0 :           rust_unreachable ();
     555              :         }
     556              :     }
     557              : 
     558    548203823 :     Rib &rib (Namespace n)
     559              :     {
     560    547803638 :       return const_cast<Rib &> (const_cast<const Node *> (this)->rib (n));
     561              :     }
     562              : 
     563              :     inline bool is_root () const;
     564              :     inline bool is_prelude () const;
     565              :     inline bool is_leaf () const;
     566              : 
     567              :     inline void insert_child (Link link, Node child);
     568              : 
     569              :     // these are the "values" of the node - the data it keeps.
     570              :     Rib rib_values;
     571              :     Rib rib_types;
     572              :     Rib rib_labels;
     573              :     Rib rib_macros;
     574              : 
     575              :     std::map<Link, Node, LinkCmp> children; // all the other nodes it links to
     576              : 
     577              :     NodeId id; // The node id of the Node's scope
     578              : 
     579              :     tl::optional<Node &> parent; // `None` only if the node is a root
     580              :   };
     581              : 
     582        21336 :   ForeverStackBase (Node &root, Node &lang_prelude, Node &extern_prelude)
     583        21336 :     : root (root), lang_prelude (lang_prelude), extern_prelude (extern_prelude)
     584              :   {}
     585              : 
     586              :   /* The forever stack's actual nodes */
     587              :   Node &root;
     588              : 
     589              :   /*
     590              :    * A special prelude node used currently for resolving language builtins
     591              :    * It has the root node as a parent, and acts as a "special case" for name
     592              :    * resolution
     593              :    */
     594              :   Node &lang_prelude;
     595              : 
     596              :   /*
     597              :    * The extern prelude, used for resolving external crates
     598              :    */
     599              :   Node &extern_prelude;
     600              : };
     601              : 
     602              : template <Namespace N> class ForeverStack : public ForeverStackBase
     603              : {
     604              : public:
     605        21336 :   ForeverStack (Node &root, Node &lang_prelude, Node &extern_prelude)
     606              :     : ForeverStackBase (root, lang_prelude, extern_prelude),
     607        21336 :       cursor_reference (root)
     608              :   {
     609        21336 :     rust_assert (root.is_root ());
     610        21336 :     rust_assert (root.is_leaf ());
     611              : 
     612              :     // TODO: Should we be using the forever stack root as the crate scope?
     613              :     // TODO: Is this how we should be getting the crate node id?
     614        21336 :     auto &mappings = Analysis::Mappings::get ();
     615        21336 :     auto &crate_mappings = mappings.crate;
     616        21336 :     root.id = *crate_mappings.crate_num_to_nodeid (
     617        21336 :       crate_mappings.get_current_crate ());
     618        21336 :     extern_prelude.id = mappings.get_next_node_id ();
     619        21336 :     lang_prelude.id = mappings.get_next_node_id ();
     620        21336 :   }
     621              : 
     622              :   /**
     623              :    * Add a new Rib to the stack. If the Rib already exists, nothing is pushed
     624              :    * and the stack's cursor is simply moved to this existing Rib.
     625              :    *
     626              :    * @param rib The Rib to push
     627              :    * @param id The NodeId of the node for which the Rib was created. For
     628              :    *        example, if a Rib is created because a lexical scope is entered,
     629              :    *        then `id` is that `BlockExpr`'s NodeId.
     630              :    * @param path An optional path if the Rib was created due to a "named"
     631              :    *        lexical scope, like a module's.
     632              :    */
     633              :   void push (Rib::Kind rib_kind, NodeId id, tl::optional<Identifier> path = {});
     634              : 
     635              :   /**
     636              :    * Pop the innermost Rib from the stack
     637              :    */
     638              :   void pop ();
     639              : 
     640              :   /**
     641              :    * Insert a new definition in the innermost `Rib` in this stack
     642              :    *
     643              :    * @param name The name of the definition
     644              :    * @param id Its NodeId
     645              :    *
     646              :    * @return `DuplicateNameError` if that node was already present in the Rib,
     647              :    * the node's `NodeId` otherwise.
     648              :    *
     649              :    * @aborts if there are no `Rib`s inserted in the current map, this function
     650              :    *         aborts the program.
     651              :    */
     652              :   tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id);
     653              : 
     654              :   tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
     655              :                                                            NodeId id);
     656              : 
     657              :   void insert_crate_in_prelude (Identifier crate_name, NodeId crate_id);
     658              : 
     659              :   /**
     660              :    * Insert a new shadowable 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_shadowable (Identifier name,
     672              :                                                               NodeId id);
     673              : 
     674              :   /**
     675              :    * Insert a new glob-originated definition in the innermost `Rib` in this
     676              :    * stack
     677              :    *
     678              :    * @param name The name of the definition
     679              :    * @param id Its NodeId
     680              :    *
     681              :    * @return `DuplicateNameError` if that node was already present in the Rib,
     682              :    * the node's `NodeId` otherwise.
     683              :    *
     684              :    * @aborts if there are no `Rib`s inserted in the current map, this function
     685              :    *         aborts the program.
     686              :    */
     687              :   tl::expected<NodeId, DuplicateNameError> insert_globbed (Identifier name,
     688              :                                                            NodeId id);
     689              : 
     690              :   /**
     691              :    * Insert a new definition at the root of 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_at_root (Identifier name,
     703              :                                                            NodeId id);
     704              : 
     705              :   /**
     706              :    * Insert an item within the lang prelude
     707              :    *
     708              :    * @param name The name of the definition
     709              :    * @param id Its NodeId
     710              :    */
     711              :   void insert_lang_prelude (Identifier name, NodeId id);
     712              : 
     713              :   /* Access the innermost `Rib` in this map */
     714              :   Rib &peek ();
     715              :   const Rib &peek () const;
     716              : 
     717              :   /**
     718              :    * Reverse iter on all ribs from the innermost one to the outermost one,
     719              :    * trying to find a name. This is the default algorithm.
     720              :    * This function gets specialized based on the Rib::Kind
     721              :    * this way, we ensure a proper resolution algorithm at the type level
     722              :    *
     723              :    * @param name Name of the identifier to locate in this scope or an outermore
     724              :    *        scope
     725              :    *
     726              :    * @return a valid option with the Definition if the identifier is present in
     727              :    * the current map, an empty one otherwise.
     728              :    */
     729              :   tl::optional<Rib::Definition> get (const Identifier &name);
     730              :   tl::optional<Rib::Definition> get_lang_prelude (const Identifier &name);
     731              :   tl::optional<Rib::Definition> get_lang_prelude (const std::string &name);
     732              :   tl::optional<Rib::Definition> get_from_prelude (NodeId prelude,
     733              :                                                   const Identifier &name);
     734              : 
     735              :   // FIXME: Documentation
     736              :   tl::optional<Rib &> to_rib (NodeId rib_id);
     737              :   tl::optional<const Rib &> to_rib (NodeId rib_id) const;
     738              : 
     739              :   std::string as_debug_string () const;
     740              : 
     741              :   /**
     742              :    * Used to check if a module is a descendant of another module
     743              :    * Intended for use in the privacy checker
     744              :    */
     745              :   bool is_module_descendant (NodeId parent, NodeId child) const;
     746              : 
     747              :   tl::optional<Rib::Definition> get (Node &start, const Identifier &name);
     748              : 
     749              :   /* Should we keep going upon seeing a Rib? */
     750              :   enum class KeepGoing
     751              :   {
     752              :     Yes,
     753              :     No,
     754              :   };
     755              : 
     756              :   /* Add a new Rib to the stack. This is an internal method */
     757              :   void push_inner (Rib::Kind rib, Link link);
     758              : 
     759              :   /* Reverse iterate on `Node`s from the cursor, in an outwards fashion */
     760              :   void reverse_iter (std::function<KeepGoing (Node &)> lambda);
     761              :   void reverse_iter (std::function<KeepGoing (const Node &)> lambda) const;
     762              : 
     763              :   /* Reverse iterate on `Node`s from a specified one, in an outwards fashion */
     764              :   void reverse_iter (Node &start, std::function<KeepGoing (Node &)> lambda);
     765              :   void reverse_iter (const Node &start,
     766              :                      std::function<KeepGoing (const Node &)> lambda) const;
     767              : 
     768              :   Node &cursor ();
     769              :   const Node &cursor () const;
     770              : 
     771              :   void update_cursor (Node &new_cursor);
     772              : 
     773              :   std::reference_wrapper<Node> cursor_reference;
     774              : 
     775              :   void stream_rib (std::stringstream &stream, const Rib &rib,
     776              :                    const std::string &next, const std::string &next_next) const;
     777              :   void stream_node (std::stringstream &stream, unsigned indentation,
     778              :                     const Node &node, unsigned depth = 0) const;
     779              : 
     780              :   /* Helper types and functions for `resolve_path` */
     781              : 
     782              :   using SegIterator =
     783              :     typename std::vector<ResolutionPathSegment>::const_iterator;
     784              : 
     785              :   Node &find_closest_module (Node &starting_point);
     786              : 
     787              :   tl::optional<SegIterator>
     788              :   find_starting_point (const RawPath<ResolutionPathSegment> &path,
     789              :                        std::reference_wrapper<Node> &starting_point,
     790              :                        std::function<void (Usage, Definition, Namespace)>
     791              :                          insert_segment_resolution,
     792              :                        std::vector<Error> &collect_errors);
     793              : 
     794              :   /* Helper functions for forward resolution (to_canonical_path, to_rib...) */
     795              :   struct DfsResult
     796              :   {
     797              :     Node &first;
     798              :     std::string second;
     799              :   };
     800              :   struct ConstDfsResult
     801              :   {
     802              :     const Node &first;
     803              :     std::string second;
     804              :   };
     805              : 
     806              :   // FIXME: Documentation
     807              :   tl::optional<DfsResult> dfs (Node &starting_point, NodeId to_find);
     808              :   tl::optional<ConstDfsResult> dfs (const Node &starting_point,
     809              :                                     NodeId to_find) const;
     810              :   // FIXME: Documentation
     811              :   tl::optional<Rib &> dfs_rib (Node &starting_point, NodeId to_find);
     812              :   tl::optional<const Rib &> dfs_rib (const Node &starting_point,
     813              :                                      NodeId to_find) const;
     814              :   // FIXME: Documentation
     815              :   tl::optional<Node &> dfs_node (Node &starting_point, NodeId to_find);
     816              :   tl::optional<const Node &> dfs_node (const Node &starting_point,
     817              :                                        NodeId to_find) const;
     818              : 
     819              :   std::unordered_map<NodeId, Node &> dfs_cache;
     820              :   tl::optional<Node &> check_cache (NodeId to_find);
     821              :   void cache (NodeId found, Node &result);
     822              : 
     823       633262 :   bool forward_declared (NodeId definition, NodeId usage)
     824              :   {
     825       633262 :     if (peek ().kind != Rib::Kind::ForwardTypeParamBan)
     826              :       return false;
     827              : 
     828              :     // Each type param has a ban rib keyed by its NodeId, and those ribs are
     829              :     // siblings ordered by NodeId, i.e. by declaration order. A default may
     830              :     // only use params declared before its own.
     831           52 :     auto &current = cursor ();
     832           52 :     if (definition == current.id)
     833              :       return true;
     834           51 :     if (!current.parent)
     835              :       return false;
     836              : 
     837           82 :     for (auto &child : current.parent.value ().children)
     838           56 :       if (child.second.id == definition)
     839              :         return definition > current.id
     840           25 :                && child.second.rib (N).kind == Rib::Kind::ForwardTypeParamBan;
     841              : 
     842              :     return false;
     843              :   }
     844              : 
     845      4520732 :   void map_usage (Usage usage, Definition definition)
     846              :   {
     847      4520732 :     resolved_nodes.emplace (usage, definition);
     848              : 
     849              :     // auto inserted = resolved_nodes.emplace (usage, definition);
     850              : 
     851              :     // is that valid?
     852              :     // FIXME: Yikes
     853              :     // rust_assert (inserted.first->first.id == definition.id);
     854              :   }
     855              : 
     856      6478515 :   tl::optional<NodeId> lookup (NodeId usage) const
     857              :   {
     858      6478515 :     auto it = resolved_nodes.find (Usage (usage));
     859              : 
     860      6478515 :     if (it == resolved_nodes.end ())
     861       222407 :       return tl::nullopt;
     862              : 
     863      6256108 :     return it->second.id;
     864              :   }
     865              : 
     866              :   tl::expected<Definition, LookupFinalizeError>
     867              :   find_leaf_definition (const NodeId &key) const;
     868              : 
     869              :   // Flattening is not needed for now but should be used later?
     870              : #if 0
     871              :   /**
     872              :    * Look at NameResolutionContext::flatten - This is the inner working function
     873              :    * which works on one specific namespace, while NameResolutionContext::flatten
     874              :    * calls flatten for every namespace
     875              :    */
     876              :   void flatten ();
     877              : #endif
     878              : 
     879              :   /* Map of "usage" nodes which have been resolved to a "definition" node */
     880              :   std::map<Usage, Definition> resolved_nodes;
     881              : };
     882              : 
     883              : } // namespace Resolver2_0
     884              : } // namespace Rust
     885              : 
     886              : #include "rust-forever-stack.hxx"
     887              : 
     888              : #endif // !RUST_FOREVER_STACK_H
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.