LCOV - code coverage report
Current view: top level - gcc/rust/resolve - rust-forever-stack.hxx (source / functions) Coverage Total Hit
Test: gcc.info Lines: 79.8 % 267 213
Test Date: 2026-11-14 16:39:50 Functions: 75.5 % 98 74
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              : #include "expected.h"
      20              : #include "rust-ast.h"
      21              : #include "rust-diagnostics.h"
      22              : #include "rust-forever-stack.h"
      23              : #include "rust-edition.h"
      24              : #include "rust-rib.h"
      25              : #include "rust-unwrap-segment.h"
      26              : #include "optional.h"
      27              : 
      28              : namespace Rust {
      29              : namespace Resolver2_0 {
      30              : 
      31              : bool
      32    250824249 : ForeverStackBase::Node::is_root () const
      33              : {
      34     19219236 :   return !parent.has_value ();
      35              : }
      36              : 
      37              : bool
      38       436098 : ForeverStackBase::Node::is_prelude () const
      39              : {
      40       436098 :   return rib_values.kind == Rib::Kind::Prelude;
      41              : }
      42              : 
      43              : bool
      44        21336 : ForeverStackBase::Node::is_leaf () const
      45              : {
      46        21336 :   return children.empty ();
      47              : }
      48              : 
      49              : void
      50          328 : ForeverStackBase::Node::insert_child (Link link, Node child)
      51              : {
      52          328 :   children.insert ({link, child});
      53              : 
      54              :   // Do we want to error if the child already exists? Probably not, right?
      55              :   // That's kinda the point, isn't it. So this method always succeeds, right?
      56          328 : }
      57              : 
      58              : template <Namespace N>
      59              : void
      60    231573088 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
      61              :                        tl::optional<Identifier> path)
      62              : {
      63    240059044 :   push_inner (rib_kind, Link (id, path));
      64    231573088 : }
      65              : 
      66              : template <Namespace N>
      67              : void
      68    231573088 : ForeverStack<N>::push_inner (Rib::Kind rib_kind, Link link)
      69              : {
      70    231573088 :   if (rib_kind == Rib::Kind::Prelude)
      71              :     {
      72              :       // If you push_inner into the prelude from outside the root, you will pop
      73              :       // back into the root, which could screw up a traversal.
      74        21336 :       rust_assert (&cursor_reference.get () == &root);
      75              :       // Prelude doesn't have an access path
      76        21336 :       rust_assert (!link.path);
      77        21336 :       update_cursor (this->lang_prelude);
      78        21336 :       return;
      79              :     }
      80              :   // If the link does not exist, we create it and emplace a new `Node` with the
      81              :   // current node as its parent. `unordered_map::emplace` returns a pair with
      82              :   // the iterator and a boolean. If the value already exists, the iterator
      83              :   // points to it. Otherwise, it points to the newly emplaced value, so we can
      84              :   // just update our cursor().
      85    463103504 :   auto emplace = cursor ().children.emplace (
      86    231551752 :     std::make_pair (link, Node (rib_kind, link.id, cursor ())));
      87              : 
      88    231551752 :   auto it = emplace.first;
      89    231551752 :   auto existed = !emplace.second;
      90              : 
      91    231551754 :   rust_debug ("inserting link: Link(%d [%s]): existed? %s", link.id,
      92              :               link.path.has_value () ? link.path.value ().as_string ().c_str ()
      93              :                                      : "<anon>",
      94              :               existed ? "yes" : "no");
      95              : 
      96              :   // We update the cursor
      97    231551752 :   update_cursor (it->second);
      98              : }
      99              : 
     100              : template <Namespace N>
     101              : void
     102    231573052 : ForeverStack<N>::pop ()
     103              : {
     104    231573052 :   rust_assert (!cursor ().is_root ());
     105              : 
     106    231573052 :   rust_debug ("popping link");
     107              : 
     108    294212392 :   for (const auto &kv : cursor ().rib (N).get_values ())
     109     62639340 :     rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
     110              :                 kv.second.to_string ().c_str ());
     111              : 
     112    231573052 :   if (cursor ().parent.has_value ())
     113   4878099788 :     for (const auto &kv : cursor ().parent.value ().rib (N).get_values ())
     114   4646526736 :       rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
     115              :                   kv.second.to_string ().c_str ());
     116              : 
     117    231573052 :   update_cursor (cursor ().parent.value ());
     118    231573052 : }
     119              : 
     120              : static tl::expected<NodeId, DuplicateNameError>
     121      9506591 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
     122              : {
     123     19013182 :   return rib.insert (name, definition);
     124              : }
     125              : 
     126              : template <Namespace N>
     127              : tl::expected<NodeId, DuplicateNameError>
     128      9259365 : ForeverStack<N>::insert (Identifier name, NodeId node)
     129              : {
     130      9259365 :   auto &innermost_rib = peek ();
     131              : 
     132              :   // So what do we do here - if the Rib has already been pushed in an earlier
     133              :   // pass, we might end up in a situation where it is okay to re-add new names.
     134              :   // Do we just ignore that here? Do we keep track of if the Rib is new or not?
     135              :   // should our cursor have info on the current node like "is it newly pushed"?
     136      9259365 :   return insert_inner (innermost_rib, name.as_string (),
     137     18518730 :                        Rib::Definition::NonShadowable (node));
     138              : }
     139              : 
     140              : template <Namespace N>
     141              : tl::expected<NodeId, DuplicateNameError>
     142       177673 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
     143              : {
     144       177673 :   auto &innermost_rib = peek ();
     145              : 
     146       177673 :   return insert_inner (innermost_rib, name.as_string (),
     147       355346 :                        Rib::Definition::Shadowable (node));
     148              : }
     149              : 
     150              : template <Namespace N>
     151              : tl::expected<NodeId, DuplicateNameError>
     152            0 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
     153              : {
     154            0 :   auto &innermost_rib = peek ();
     155              : 
     156            0 :   return insert_inner (innermost_rib, name.as_string (),
     157            0 :                        Rib::Definition::Globbed (node));
     158              : }
     159              : 
     160              : template <Namespace N>
     161              : tl::expected<NodeId, DuplicateNameError>
     162        10158 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
     163              : {
     164        10158 :   auto &root_rib = root.rib (N);
     165              : 
     166              :   // inserting in the root of the crate is never a shadowing operation, even for
     167              :   // macros
     168        10158 :   return insert_inner (root_rib, name.as_string (),
     169        20316 :                        Rib::Definition::NonShadowable (node));
     170              : }
     171              : 
     172              : // Specialization for Macros and Labels - where we are allowed to shadow
     173              : // existing definitions
     174              : template <>
     175              : inline tl::expected<NodeId, DuplicateNameError>
     176        15474 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
     177              : {
     178        15474 :   return insert_inner (peek (), name.as_string (),
     179        30948 :                        Rib::Definition::Shadowable (node));
     180              : }
     181              : 
     182              : template <>
     183              : inline tl::expected<NodeId, DuplicateNameError>
     184           78 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
     185              : {
     186           78 :   return insert_inner (peek (), name.as_string (),
     187          156 :                        Rib::Definition::Shadowable (node));
     188              : }
     189              : 
     190              : template <>
     191              : inline tl::expected<NodeId, DuplicateNameError>
     192        30784 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
     193              : {
     194        30784 :   return insert_inner (peek (), name.as_string (),
     195        61568 :                        Rib::Definition::NonShadowable (node, true));
     196              : }
     197              : 
     198              : template <>
     199              : inline tl::expected<NodeId, DuplicateNameError>
     200         2103 : ForeverStack<Namespace::Values>::insert_variant (Identifier name, NodeId node)
     201              : {
     202         2103 :   return insert_inner (peek (), name.as_string (),
     203         4206 :                        Rib::Definition::NonShadowable (node, true));
     204              : }
     205              : 
     206              : template <Namespace N>
     207              : void
     208          896 : ForeverStack<N>::insert_crate_in_prelude (Identifier crate_name,
     209              :                                           NodeId extern_crate_node_id)
     210              : {
     211          896 :   auto &extern_prelude_rib = extern_prelude.rib (N);
     212          896 :   auto definition = Rib::Definition::NonShadowable (extern_crate_node_id);
     213         2380 :   insert_inner (extern_prelude_rib, crate_name, definition);
     214          896 : }
     215              : 
     216              : template <Namespace N>
     217              : inline void
     218        10060 : ForeverStack<N>::insert_lang_prelude (Identifier name, NodeId id)
     219              : {
     220        30180 :   insert_inner (lang_prelude.rib (N), name.as_string (),
     221        20120 :                 Rib::Definition::NonShadowable (id, false));
     222        10060 : }
     223              : 
     224              : template <Namespace N>
     225              : Rib &
     226     11109047 : ForeverStack<N>::peek ()
     227              : {
     228     10708863 :   return cursor ().rib (N);
     229              : }
     230              : 
     231              : template <Namespace N>
     232              : const Rib &
     233              : ForeverStack<N>::peek () const
     234              : {
     235              :   return cursor ().rib (N);
     236              : }
     237              : 
     238              : template <Namespace N>
     239              : void
     240           93 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
     241              : {
     242          186 :   return reverse_iter (cursor (), lambda);
     243              : }
     244              : 
     245              : template <Namespace N>
     246              : void
     247              : ForeverStack<N>::reverse_iter (
     248              :   std::function<KeepGoing (const Node &)> lambda) const
     249              : {
     250              :   return reverse_iter (cursor (), lambda);
     251              : }
     252              : 
     253              : template <Namespace N>
     254              : void
     255      7810185 : ForeverStack<N>::reverse_iter (Node &start,
     256              :                                std::function<KeepGoing (Node &)> lambda)
     257              : {
     258      7810185 :   auto *tmp = &start;
     259              : 
     260     18646717 :   while (true)
     261              :     {
     262     26456902 :       auto keep_going = lambda (*tmp);
     263     26456902 :       if (keep_going == KeepGoing::No)
     264              :         return;
     265              : 
     266     18733526 :       if (tmp->is_root ())
     267              :         return;
     268              : 
     269     18646717 :       tmp = &tmp->parent.value ();
     270              :     }
     271              : }
     272              : 
     273              : template <Namespace N>
     274              : void
     275              : ForeverStack<N>::reverse_iter (
     276              :   const Node &start, std::function<KeepGoing (const Node &)> lambda) const
     277              : {
     278              :   auto *tmp = &start;
     279              : 
     280              :   while (true)
     281              :     {
     282              :       auto keep_going = lambda (*tmp);
     283              :       if (keep_going == KeepGoing::No)
     284              :         return;
     285              : 
     286              :       if (tmp->is_root ())
     287              :         return;
     288              : 
     289              :       tmp = &tmp->parent.value ();
     290              :     }
     291              : }
     292              : 
     293              : template <Namespace N>
     294              : typename ForeverStack<N>::Node &
     295   1177003446 : ForeverStack<N>::cursor ()
     296              : {
     297   1170166162 :   return cursor_reference;
     298              : }
     299              : 
     300              : template <Namespace N>
     301              : const typename ForeverStack<N>::Node &
     302            0 : ForeverStack<N>::cursor () const
     303              : {
     304            0 :   return cursor_reference;
     305              : }
     306              : 
     307              : template <Namespace N>
     308              : void
     309    231573088 : ForeverStack<N>::update_cursor (Node &new_cursor)
     310              : {
     311    231573088 :   cursor_reference = new_cursor;
     312              : }
     313              : 
     314              : template <Namespace N>
     315              : tl::optional<Rib::Definition>
     316      7695751 : ForeverStack<N>::get (Node &start, const Identifier &name)
     317              : {
     318      7695751 :   tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
     319              : 
     320              :   // TODO: Can we improve the API? have `reverse_iter` return an optional?
     321     34034133 :   reverse_iter (start, [&resolved_definition, &name] (Node &current) {
     322              :     // we can't reference associated types/functions like this
     323     26338382 :     if (current.rib (N).kind == Rib::Kind::TraitOrImpl)
     324              :       return KeepGoing::Yes;
     325              : 
     326     23064898 :     auto candidate = current.rib (N).get (name.as_string ());
     327              : 
     328     23064898 :     if (candidate)
     329              :       {
     330      2038832 :         if (candidate->is_variant ())
     331              :           return KeepGoing::Yes;
     332              :         // for most namespaces, we do not need to care about various ribs -
     333              :         // they are available from all contexts if defined in the current
     334              :         // scope, or an outermore one. so if we do have a candidate, we can
     335              :         // return it directly and stop iterating
     336      2038827 :         resolved_definition = *candidate;
     337              : 
     338      2038827 :         return KeepGoing::No;
     339              :       }
     340              :     else
     341              :       {
     342     21026066 :         if (current.rib (N).kind == Rib::Kind::Module)
     343              :           return KeepGoing::No;
     344              :         else
     345     15455951 :           return KeepGoing::Yes;
     346              :       }
     347     26338382 :   });
     348              : 
     349      7695751 :   return resolved_definition;
     350              : }
     351              : 
     352              : template <Namespace N>
     353              : tl::optional<Rib::Definition>
     354      6437152 : ForeverStack<N>::get (const Identifier &name)
     355              : {
     356      6437152 :   return get (cursor (), name);
     357              : }
     358              : 
     359              : template <Namespace N>
     360              : tl::optional<Rib::Definition>
     361           11 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
     362              : {
     363           11 :   return lang_prelude.rib (N).get (name.as_string ());
     364              : }
     365              : 
     366              : template <Namespace N>
     367              : tl::optional<Rib::Definition>
     368       513625 : ForeverStack<N>::get_lang_prelude (const std::string &name)
     369              : {
     370       513625 :   return lang_prelude.rib (N).get (name);
     371              : }
     372              : 
     373              : template <Namespace N>
     374              : tl::optional<Rib::Definition>
     375              : ForeverStack<N>::get_from_prelude (NodeId prelude, const Identifier &name)
     376              : {
     377              :   auto starting_point = dfs_node (root, prelude);
     378              :   if (!starting_point)
     379              :     return tl::nullopt;
     380              : 
     381              :   return get (*starting_point, name);
     382              : }
     383              : 
     384              : template <>
     385           93 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
     386              :   const Identifier &name)
     387              : {
     388           93 :   tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
     389              : 
     390           93 :   reverse_iter ([&resolved_definition, &name] (Node &current) {
     391              :     // looking up for labels cannot go through function ribs
     392              :     // TODO: What other ribs?
     393          455 :     if (current.rib_labels.kind == Rib::Kind::Function)
     394              :       return KeepGoing::No;
     395              : 
     396          450 :     auto candidate = current.rib_labels.get (name.as_string ());
     397              : 
     398              :     // FIXME: Factor this in a function with the generic `get`
     399          450 :     return candidate.map_or (
     400          988 :       [&resolved_definition] (Rib::Definition found) {
     401           88 :         resolved_definition = found;
     402              : 
     403           88 :         return KeepGoing::No;
     404              :       },
     405          450 :       KeepGoing::Yes);
     406          455 :   });
     407              : 
     408           93 :   return resolved_definition;
     409              : }
     410              : 
     411              : /* Check if an iterator points to the last element */
     412              : template <typename I, typename C>
     413              : static bool
     414       973047 : is_last (const I &iterator, const C &collection)
     415              : {
     416      1604820 :   return iterator + 1 == collection.end ();
     417              : }
     418              : 
     419              : /* Check if an iterator points to the start of the collection */
     420              : template <typename I, typename C>
     421              : static bool
     422      2022753 : is_start (const I &iterator, const C &collection)
     423              : {
     424      2022753 :   return iterator == collection.begin ();
     425              : }
     426              : 
     427              : template <Namespace N>
     428              : typename ForeverStack<N>::Node &
     429       114341 : ForeverStack<N>::find_closest_module (Node &starting_point)
     430              : {
     431       114341 :   auto *closest_module = &starting_point;
     432              : 
     433       232406 :   reverse_iter (starting_point, [&closest_module] (Node &current) {
     434       118065 :     if (current.rib (N).kind == Rib::Kind::Module || current.is_root ())
     435              :       {
     436       114341 :         closest_module = &current;
     437       114341 :         return KeepGoing::No;
     438              :       }
     439              : 
     440              :     return KeepGoing::Yes;
     441              :   });
     442              : 
     443       114341 :   return *closest_module;
     444              : }
     445              : 
     446              : /* If a the given condition is met, emit an error about misused leading path
     447              :  * segments */
     448              : static inline bool
     449      1218985 : check_leading_kw_at_start (std::vector<Error> &collect_errors,
     450              :                            const ResolutionPathSegment &segment, bool condition)
     451              : {
     452      1218985 :   if (condition)
     453           11 :     collect_errors.emplace_back (
     454           11 :       segment.locus, ErrorCode::E0433,
     455           11 :       "%qs in paths can only be used in start position", segment.name.c_str ());
     456              : 
     457      1218985 :   return condition;
     458              : }
     459              : 
     460              : // we first need to handle the "starting" segments - `super`, `self` or
     461              : // `crate`. we don't need to do anything for `self` and can just skip it. for
     462              : // `crate`, we need to go back to the root of the current stack. for each
     463              : // `super` segment, we go back to the cursor's parent until we reach the
     464              : // correct one or the root.
     465              : template <Namespace N>
     466              : tl::optional<typename std::vector<ResolutionPathSegment>::const_iterator>
     467       553793 : ForeverStack<N>::find_starting_point (
     468              :   const RawPath<ResolutionPathSegment> &path,
     469              :   std::reference_wrapper<Node> &starting_point,
     470              :   std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
     471              :   std::vector<Error> &collect_errors)
     472              : {
     473       553793 :   auto &segments = path.get_segments ();
     474       553793 :   auto iterator = segments.begin ();
     475              : 
     476       631807 :   for (; iterator != segments.end (); iterator++)
     477              :     {
     478       631773 :       auto &seg = *iterator;
     479              : 
     480              :       // don't include a final self segment
     481       631773 :       if (is_last (iterator, segments) && seg.is_lower_self_seg ())
     482              :         break;
     483              : 
     484       631773 :       bool is_self_or_crate
     485       631773 :         = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
     486              : 
     487              :       // if we're after the first path segment and meet `self` or `crate`, it's
     488              :       // an error - we should only be seeing `super` keywords at this point
     489       631773 :       if (check_leading_kw_at_start (collect_errors, seg,
     490       631773 :                                      !is_start (iterator, segments)
     491              :                                        && is_self_or_crate))
     492            1 :         return tl::nullopt;
     493              : 
     494       631772 :       if (seg.is_crate_path_seg ())
     495              :         {
     496       222817 :           if (path.has_opening_scope_resolution ())
     497              :             {
     498            6 :               collect_errors.emplace_back (seg.locus, ErrorCode::E0433,
     499              :                                            "global paths cannot start with %qs",
     500            6 :                                            seg.name.c_str ());
     501            6 :               return tl::nullopt;
     502              :             }
     503       222811 :           starting_point = root;
     504       222811 :           insert_segment_resolution (Usage (seg.node_id),
     505       222811 :                                      Definition (starting_point.get ().id), N);
     506       222811 :           iterator++;
     507       222811 :           break;
     508              :         }
     509       408955 :       if (seg.is_lower_self_seg ())
     510              :         {
     511              :           // insert segment resolution
     512        46054 :           starting_point = find_closest_module (starting_point);
     513        46054 :           insert_segment_resolution (Usage (seg.node_id),
     514        46054 :                                      Definition (starting_point.get ().id), N);
     515              :           // don't exit -- we could see some "super" segments
     516        46054 :           continue;
     517              :         }
     518       362901 :       if (seg.is_super_path_seg ())
     519              :         {
     520        31961 :           starting_point = find_closest_module (starting_point);
     521        31961 :           if (starting_point.get ().is_root ())
     522              :             {
     523            1 :               collect_errors.emplace_back (
     524            1 :                 seg.locus, ErrorCode::E0433,
     525              :                 "too many leading %<super%> keywords");
     526            1 :               return tl::nullopt;
     527              :             }
     528              : 
     529        31960 :           starting_point
     530        31960 :             = find_closest_module (starting_point.get ().parent.value ());
     531              : 
     532        31960 :           insert_segment_resolution (Usage (seg.node_id),
     533        31960 :                                      Definition (starting_point.get ().id), N);
     534        31960 :           continue;
     535              :         }
     536              : 
     537              :       // now we've gone through the allowed `crate`, `self` or leading `super`
     538              :       // segments. we can start resolving each segment itself.
     539              :       // if we do see another leading segment, then we can error out.
     540              :       break;
     541              :     }
     542              : 
     543       553785 :   return iterator;
     544              : }
     545              : 
     546              : template <Namespace N>
     547              : tl::optional<typename ForeverStack<N>::DfsResult>
     548              : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
     549              : {
     550              :   auto values = starting_point.rib (N).get_values ();
     551              : 
     552              :   for (auto &kv : values)
     553              :     {
     554              :       for (auto id : kv.second.ids_shadowable)
     555              :         if (id == to_find)
     556              :           return {{starting_point, kv.first}};
     557              :       for (auto id : kv.second.ids_non_shadowable)
     558              :         if (id == to_find)
     559              :           return {{starting_point, kv.first}};
     560              :       for (auto id : kv.second.ids_globbed)
     561              :         if (id == to_find)
     562              :           return {{starting_point, kv.first}};
     563              :     }
     564              : 
     565              :   for (auto &child : starting_point.children)
     566              :     {
     567              :       auto candidate = dfs (child.second, to_find);
     568              : 
     569              :       if (candidate.has_value ())
     570              :         return candidate;
     571              :     }
     572              : 
     573              :   return tl::nullopt;
     574              : }
     575              : 
     576              : template <Namespace N>
     577              : tl::optional<typename ForeverStack<N>::ConstDfsResult>
     578              : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
     579              :                       NodeId to_find) const
     580              : {
     581              :   auto values = starting_point.rib (N).get_values ();
     582              : 
     583              :   for (auto &kv : values)
     584              :     {
     585              :       for (auto id : kv.second.ids_shadowable)
     586              :         if (id == to_find)
     587              :           return {{starting_point, kv.first}};
     588              :       for (auto id : kv.second.ids_non_shadowable)
     589              :         if (id == to_find)
     590              :           return {{starting_point, kv.first}};
     591              :       for (auto id : kv.second.ids_globbed)
     592              :         if (id == to_find)
     593              :           return {{starting_point, kv.first}};
     594              :     }
     595              : 
     596              :   for (auto &child : starting_point.children)
     597              :     {
     598              :       auto candidate = dfs (child.second, to_find);
     599              : 
     600              :       if (candidate.has_value ())
     601              :         return candidate;
     602              :     }
     603              : 
     604              :   return tl::nullopt;
     605              : }
     606              : 
     607              : template <Namespace N>
     608              : tl::optional<Rib &>
     609       387452 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
     610              : {
     611       774904 :   return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
     612       387452 :     return x.rib (N);
     613       387452 :   });
     614              : }
     615              : 
     616              : template <Namespace N>
     617              : tl::optional<const Rib &>
     618              : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
     619              :                           NodeId to_find) const
     620              : {
     621              :   return dfs_node (starting_point, to_find)
     622              :     .map ([] (const Node &x) -> const Rib & { return x.rib (N); });
     623              : }
     624              : 
     625              : template <Namespace N>
     626              : tl::optional<typename ForeverStack<N>::Node &>
     627     37138171 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
     628              :                            NodeId to_find)
     629              : {
     630     37138171 :   if (auto found = check_cache (to_find))
     631       627748 :     return found;
     632              : 
     633     36510423 :   if (starting_point.id == to_find)
     634              :     {
     635         2934 :       cache (to_find, starting_point);
     636              : 
     637         2934 :       return starting_point;
     638              :     }
     639              : 
     640     73007774 :   for (auto &child : starting_point.children)
     641              :     {
     642     36507489 :       auto candidate = dfs_node (child.second, to_find);
     643              : 
     644     36507489 :       if (candidate.has_value ())
     645         7204 :         return candidate;
     646              :     }
     647              : 
     648     36500285 :   return tl::nullopt;
     649              : }
     650              : 
     651              : template <Namespace N>
     652              : tl::optional<const typename ForeverStack<N>::Node &>
     653          131 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
     654              :                            NodeId to_find) const
     655              : {
     656          131 :   if (starting_point.id == to_find)
     657           16 :     return starting_point;
     658              : 
     659          189 :   for (auto &child : starting_point.children)
     660              :     {
     661          103 :       auto candidate = dfs_node (child.second, to_find);
     662              : 
     663          103 :       if (candidate.has_value ())
     664           29 :         return candidate;
     665              :     }
     666              : 
     667           86 :   return tl::nullopt;
     668              : }
     669              : 
     670              : template <Namespace N>
     671              : tl::optional<typename ForeverStack<N>::Node &>
     672     37138171 : ForeverStack<N>::check_cache (NodeId to_find)
     673              : {
     674     37138171 :   auto entry = dfs_cache.find (to_find);
     675              : 
     676     37138171 :   if (entry != dfs_cache.end ())
     677       627748 :     return entry->second;
     678              : 
     679     36510423 :   return tl::nullopt;
     680              : }
     681              : 
     682              : template <Namespace N>
     683              : void
     684         2934 : ForeverStack<N>::cache (NodeId found, typename ForeverStack<N>::Node &result)
     685              : {
     686         2934 :   dfs_cache.insert ({found, result});
     687              : }
     688              : 
     689              : template <Namespace N>
     690              : tl::optional<Rib &>
     691           52 : ForeverStack<N>::to_rib (NodeId rib_id)
     692              : {
     693           52 :   return dfs_rib (root, rib_id);
     694              : }
     695              : 
     696              : template <Namespace N>
     697              : tl::optional<const Rib &>
     698              : ForeverStack<N>::to_rib (NodeId rib_id) const
     699              : {
     700              :   return dfs_rib (root, rib_id);
     701              : }
     702              : 
     703              : template <Namespace N>
     704              : void
     705            0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
     706              :                              const std::string &next,
     707              :                              const std::string &next_next) const
     708              : {
     709            0 :   std::string rib_kind = Rib::kind_to_string (rib.kind);
     710            0 :   stream << next << "rib [" << rib_kind << "]: {";
     711            0 :   if (rib.get_values ().empty ())
     712              :     {
     713            0 :       stream << "}\n";
     714            0 :       return;
     715              :     }
     716              :   else
     717              :     {
     718            0 :       stream << "\n";
     719              :     }
     720              : 
     721            0 :   for (const auto &kv : rib.get_values ())
     722            0 :     stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
     723              : 
     724            0 :   stream << next << "},\n";
     725            0 : }
     726              : 
     727              : template <Namespace N>
     728              : void
     729            0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
     730              :                               const ForeverStack<N>::Node &node,
     731              :                               unsigned depth) const
     732              : {
     733            0 :   auto indent = std::string (indentation, ' ');
     734            0 :   auto next = std::string (indentation + 4, ' ');
     735            0 :   auto next_next = std::string (indentation + 8, ' ');
     736              : 
     737            0 :   std::string cursor_text = "";
     738            0 :   if (node.id == cursor ().id)
     739            0 :     cursor_text = "(C)";
     740              : 
     741              :   stream << indent << "Node " << cursor_text << "{\n"
     742            0 :          << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
     743            0 :          << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
     744            0 :          << ",\n";
     745              : 
     746            0 :   stream_rib (stream, node.rib (N), next, next_next);
     747              : 
     748            0 :   stream << indent << "}\n";
     749              : 
     750            0 :   for (auto &kv : node.children)
     751              :     {
     752            0 :       auto link = kv.first;
     753            0 :       auto child = kv.second;
     754            0 :       stream << indent << "Link " << depth << " (" << link.id << ", "
     755            0 :              << (link.path.has_value () ? link.path.value ().as_string ()
     756            0 :                                         : "<anon>")
     757            0 :              << "):\n";
     758              : 
     759            0 :       stream_node (stream, indentation + 4, child, depth + 1);
     760              : 
     761            0 :       stream << '\n';
     762              :     }
     763            0 : }
     764              : 
     765              : template <Namespace N>
     766              : std::string
     767            0 : ForeverStack<N>::as_debug_string () const
     768              : {
     769            0 :   std::stringstream stream;
     770              : 
     771            0 :   stream_node (stream, 0, root);
     772            0 :   stream << "Extern prelude \n";
     773            0 :   stream_node (stream, 0, extern_prelude);
     774            0 :   stream << "Lang prelude \n";
     775            0 :   stream_node (stream, 0, lang_prelude);
     776              : 
     777            0 :   return stream.str ();
     778            0 : }
     779              : 
     780              : template <Namespace N>
     781              : bool
     782           14 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
     783              : {
     784           14 :   return dfs_node (dfs_node (root, parent).value (), child).has_value ();
     785              : }
     786              : 
     787              : static tl::expected<Definition, LookupFinalizeError>
     788       515453 : find_leaf_definition_inner (const Usage &key,
     789              :                             const std::map<Usage, Definition> &resolved_nodes,
     790              :                             std::set<Usage> &keys_seen)
     791              : {
     792       515453 :   auto original_definition = resolved_nodes.find (key);
     793       515453 :   auto possible_import = Usage (original_definition->second.id);
     794              : 
     795       515453 :   if (original_definition == resolved_nodes.end ())
     796       515453 :     return tl::make_unexpected (LookupFinalizeError::NoDefinition);
     797              : 
     798            0 :   if (!keys_seen.insert (key).second)
     799            0 :     return tl::make_unexpected (LookupFinalizeError::Loop);
     800              : 
     801            0 :   if (resolved_nodes.find (possible_import) == resolved_nodes.end ())
     802            0 :     return original_definition->second;
     803              : 
     804              :   // We're dealing with an import - a reference to another
     805              :   // definition. Go through the chain and update the original key's
     806              :   // corresponding definition.
     807            0 :   return find_leaf_definition_inner (possible_import, resolved_nodes,
     808            0 :                                      keys_seen);
     809              : }
     810              : 
     811              : template <Namespace N>
     812              : tl::expected<Definition, LookupFinalizeError>
     813       515453 : ForeverStack<N>::find_leaf_definition (const NodeId &key) const
     814              : {
     815       515453 :   std::set<Usage> keys_seen;
     816              : 
     817       515453 :   return find_leaf_definition_inner (Usage (key), resolved_nodes, keys_seen);
     818       515453 : }
     819              : 
     820              : #if 0
     821              : template <Namespace N>
     822              : void
     823              : ForeverStack<N>::flatten ()
     824              : {
     825              :   for (auto &k_v : resolved_nodes)
     826              :     {
     827              :       // Loop detection
     828              :       auto keys_seen = std::set<Usage> ();
     829              : 
     830              :       auto result
     831              :         = find_leaf_definition_inner (k_v.first, resolved_nodes, keys_seen);
     832              : 
     833              :       if (!result)
     834              :         {
     835              :           // Trigger an ICE if we haven't found a definition because that's
     836              :           // really weird
     837              :           rust_assert (result.error () != LookupFinalizeError::NoDefinition);
     838              : 
     839              :           // FIXME: This needs to be improved and tested, but later
     840              :           rust_error_at (UNDEF_LOCATION, "import loop");
     841              :           continue;
     842              :         }
     843              : 
     844              :       // Replace the Definition for this Usage in the map. This may be a no-op.
     845              :       k_v.second = result.value ();
     846              :     }
     847              : }
     848              : #endif
     849              : 
     850              : // FIXME: Can we add selftests?
     851              : 
     852              : } // namespace Resolver2_0
     853              : } // namespace Rust
        

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.