LCOV - code coverage report
Current view: top level - gcc/rust/resolve - rust-forever-stack.hxx (source / functions) Coverage Total Hit
Test: gcc.info Lines: 87.4 % 364 318
Test Date: 2025-07-12 13:27:34 Functions: 62.3 % 146 91
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : // Copyright (C) 2020-2025 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                 :             : template <Namespace N>
      32                 :             : bool
      33                 :      223951 : ForeverStack<N>::Node::is_root () const
      34                 :             : {
      35                 :       44446 :   return !parent.has_value ();
      36                 :             : }
      37                 :             : 
      38                 :             : template <Namespace N>
      39                 :             : bool
      40                 :             : ForeverStack<N>::Node::is_prelude () const
      41                 :             : {
      42                 :             :   return rib.kind == Rib::Kind::Prelude;
      43                 :             : }
      44                 :             : 
      45                 :             : template <Namespace N>
      46                 :             : bool
      47                 :       19756 : ForeverStack<N>::Node::is_leaf () const
      48                 :             : {
      49                 :       19756 :   return children.empty ();
      50                 :             : }
      51                 :             : 
      52                 :             : template <Namespace N>
      53                 :             : void
      54                 :             : ForeverStack<N>::Node::insert_child (Link link, Node child)
      55                 :             : {
      56                 :             :   auto res = children.insert ({link, child});
      57                 :             : 
      58                 :             :   // Do we want to error if the child already exists? Probably not, right?
      59                 :             :   // That's kinda the point, isn't it. So this method always succeeds, right?
      60                 :             : }
      61                 :             : 
      62                 :             : template <Namespace N>
      63                 :             : void
      64                 :      168582 : ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id,
      65                 :             :                        tl::optional<Identifier> path)
      66                 :             : {
      67                 :      193560 :   push_inner (rib_kind, Link (id, path));
      68                 :      168582 : }
      69                 :             : 
      70                 :             : template <Namespace N>
      71                 :             : void
      72                 :      168582 : ForeverStack<N>::push_inner (Rib rib, Link link)
      73                 :             : {
      74                 :      168582 :   if (rib.kind == Rib::Kind::Prelude)
      75                 :             :     {
      76                 :             :       // If you push_inner into the prelude from outside the root, you will pop
      77                 :             :       // back into the root, which could screw up a traversal.
      78                 :        3006 :       rust_assert (&cursor_reference.get () == &root);
      79                 :             :       // Prelude doesn't have an access path
      80                 :        3006 :       rust_assert (!link.path);
      81                 :        3006 :       update_cursor (this->lang_prelude);
      82                 :        3006 :       return;
      83                 :             :     }
      84                 :             :   // If the link does not exist, we create it and emplace a new `Node` with the
      85                 :             :   // current node as its parent. `unordered_map::emplace` returns a pair with
      86                 :             :   // the iterator and a boolean. If the value already exists, the iterator
      87                 :             :   // points to it. Otherwise, it points to the newly emplaced value, so we can
      88                 :             :   // just update our cursor().
      89                 :      331152 :   auto emplace = cursor ().children.emplace (
      90                 :      165576 :     std::make_pair (link, Node (rib, link.id, cursor ())));
      91                 :             : 
      92                 :      165576 :   auto it = emplace.first;
      93                 :      165576 :   auto existed = !emplace.second;
      94                 :             : 
      95                 :      193647 :   rust_debug ("inserting link: Link(%d [%s]): existed? %s", link.id,
      96                 :             :               link.path.has_value () ? link.path.value ().as_string ().c_str ()
      97                 :             :                                      : "<anon>",
      98                 :             :               existed ? "yes" : "no");
      99                 :             : 
     100                 :             :   // We update the cursor
     101                 :      165576 :   update_cursor (it->second);
     102                 :             : }
     103                 :             : 
     104                 :             : template <Namespace N>
     105                 :             : void
     106                 :      168570 : ForeverStack<N>::pop ()
     107                 :             : {
     108                 :      168570 :   rust_assert (!cursor ().is_root ());
     109                 :             : 
     110                 :      168570 :   rust_debug ("popping link");
     111                 :             : 
     112                 :      214491 :   for (const auto &kv : cursor ().rib.get_values ())
     113                 :       45921 :     rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
     114                 :             :                 kv.second.to_string ().c_str ());
     115                 :             : 
     116                 :      168570 :   if (cursor ().parent.has_value ())
     117                 :      334863 :     for (const auto &kv : cursor ().parent.value ().rib.get_values ())
     118                 :      166293 :       rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
     119                 :             :                   kv.second.to_string ().c_str ());
     120                 :             : 
     121                 :      168570 :   update_cursor (cursor ().parent.value ());
     122                 :      168570 : }
     123                 :             : 
     124                 :             : static tl::expected<NodeId, DuplicateNameError>
     125                 :       38854 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
     126                 :             : {
     127                 :       77708 :   return rib.insert (name, definition);
     128                 :             : }
     129                 :             : 
     130                 :             : template <Namespace N>
     131                 :             : tl::expected<NodeId, DuplicateNameError>
     132                 :       35704 : ForeverStack<N>::insert (Identifier name, NodeId node)
     133                 :             : {
     134                 :       35704 :   auto &innermost_rib = peek ();
     135                 :             : 
     136                 :             :   // So what do we do here - if the Rib has already been pushed in an earlier
     137                 :             :   // pass, we might end up in a situation where it is okay to re-add new names.
     138                 :             :   // Do we just ignore that here? Do we keep track of if the Rib is new or not?
     139                 :             :   // should our cursor have info on the current node like "is it newly pushed"?
     140                 :       35704 :   return insert_inner (innermost_rib, name.as_string (),
     141                 :       71408 :                        Rib::Definition::NonShadowable (node));
     142                 :             : }
     143                 :             : 
     144                 :             : template <Namespace N>
     145                 :             : tl::expected<NodeId, DuplicateNameError>
     146                 :        2591 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
     147                 :             : {
     148                 :        2591 :   auto &innermost_rib = peek ();
     149                 :             : 
     150                 :        2591 :   return insert_inner (innermost_rib, name.as_string (),
     151                 :        5182 :                        Rib::Definition::Shadowable (node));
     152                 :             : }
     153                 :             : 
     154                 :             : template <Namespace N>
     155                 :             : tl::expected<NodeId, DuplicateNameError>
     156                 :          24 : ForeverStack<N>::insert_globbed (Identifier name, NodeId node)
     157                 :             : {
     158                 :          24 :   auto &innermost_rib = peek ();
     159                 :             : 
     160                 :          24 :   return insert_inner (innermost_rib, name.as_string (),
     161                 :          48 :                        Rib::Definition::Globbed (node));
     162                 :             : }
     163                 :             : 
     164                 :             : template <Namespace N>
     165                 :             : tl::expected<NodeId, DuplicateNameError>
     166                 :          10 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
     167                 :             : {
     168                 :          10 :   auto &root_rib = root.rib;
     169                 :             : 
     170                 :             :   // inserting in the root of the crate is never a shadowing operation, even for
     171                 :             :   // macros
     172                 :          10 :   return insert_inner (root_rib, name.as_string (),
     173                 :          20 :                        Rib::Definition::NonShadowable (node));
     174                 :             : }
     175                 :             : 
     176                 :             : // Specialization for Macros and Labels - where we are allowed to shadow
     177                 :             : // existing definitions
     178                 :             : template <>
     179                 :             : inline tl::expected<NodeId, DuplicateNameError>
     180                 :          63 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
     181                 :             : {
     182                 :          63 :   return insert_inner (peek (), name.as_string (),
     183                 :         126 :                        Rib::Definition::Shadowable (node));
     184                 :             : }
     185                 :             : 
     186                 :             : template <>
     187                 :             : inline tl::expected<NodeId, DuplicateNameError>
     188                 :          27 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
     189                 :             : {
     190                 :          27 :   return insert_inner (peek (), name.as_string (),
     191                 :          54 :                        Rib::Definition::Shadowable (node));
     192                 :             : }
     193                 :             : 
     194                 :             : template <>
     195                 :             : inline tl::expected<NodeId, DuplicateNameError>
     196                 :         435 : ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node)
     197                 :             : {
     198                 :         435 :   return insert_inner (peek (), name.as_string (),
     199                 :         870 :                        Rib::Definition::NonShadowable (node, true));
     200                 :             : }
     201                 :             : 
     202                 :             : template <Namespace N>
     203                 :             : Rib &
     204                 :       45546 : ForeverStack<N>::peek ()
     205                 :             : {
     206                 :       45546 :   return cursor ().rib;
     207                 :             : }
     208                 :             : 
     209                 :             : template <Namespace N>
     210                 :             : const Rib &
     211                 :             : ForeverStack<N>::peek () const
     212                 :             : {
     213                 :             :   return cursor ().rib;
     214                 :             : }
     215                 :             : 
     216                 :             : template <Namespace N>
     217                 :             : void
     218                 :       11062 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
     219                 :             : {
     220                 :       22124 :   return reverse_iter (cursor (), lambda);
     221                 :             : }
     222                 :             : 
     223                 :             : template <Namespace N>
     224                 :             : void
     225                 :             : ForeverStack<N>::reverse_iter (
     226                 :             :   std::function<KeepGoing (const Node &)> lambda) const
     227                 :             : {
     228                 :             :   return reverse_iter (cursor (), lambda);
     229                 :             : }
     230                 :             : 
     231                 :             : template <Namespace N>
     232                 :             : void
     233                 :       11447 : ForeverStack<N>::reverse_iter (Node &start,
     234                 :             :                                std::function<KeepGoing (Node &)> lambda)
     235                 :             : {
     236                 :       11447 :   auto *tmp = &start;
     237                 :             : 
     238                 :       14746 :   while (true)
     239                 :             :     {
     240                 :       26193 :       auto keep_going = lambda (*tmp);
     241                 :       26193 :       if (keep_going == KeepGoing::No)
     242                 :             :         return;
     243                 :             : 
     244                 :       18842 :       if (tmp->is_root ())
     245                 :             :         return;
     246                 :             : 
     247                 :       14746 :       tmp = &tmp->parent.value ();
     248                 :             :     }
     249                 :             : }
     250                 :             : 
     251                 :             : template <Namespace N>
     252                 :             : void
     253                 :        5601 : ForeverStack<N>::reverse_iter (
     254                 :             :   const Node &start, std::function<KeepGoing (const Node &)> lambda) const
     255                 :             : {
     256                 :        5601 :   auto *tmp = &start;
     257                 :             : 
     258                 :        3940 :   while (true)
     259                 :             :     {
     260                 :        9541 :       auto keep_going = lambda (*tmp);
     261                 :        9541 :       if (keep_going == KeepGoing::No)
     262                 :             :         return;
     263                 :             : 
     264                 :        3940 :       if (tmp->is_root ())
     265                 :             :         return;
     266                 :             : 
     267                 :        3940 :       tmp = &tmp->parent.value ();
     268                 :             :     }
     269                 :             : }
     270                 :             : 
     271                 :             : template <Namespace N>
     272                 :             : typename ForeverStack<N>::Node &
     273                 :      898651 : ForeverStack<N>::cursor ()
     274                 :             : {
     275                 :      898651 :   return cursor_reference;
     276                 :             : }
     277                 :             : 
     278                 :             : template <Namespace N>
     279                 :             : const typename ForeverStack<N>::Node &
     280                 :             : ForeverStack<N>::cursor () const
     281                 :             : {
     282                 :             :   return cursor_reference;
     283                 :             : }
     284                 :             : 
     285                 :             : template <Namespace N>
     286                 :             : void
     287                 :      168582 : ForeverStack<N>::update_cursor (Node &new_cursor)
     288                 :             : {
     289                 :      168582 :   cursor_reference = new_cursor;
     290                 :             : }
     291                 :             : 
     292                 :             : template <Namespace N>
     293                 :             : tl::optional<Rib::Definition>
     294                 :       11048 : ForeverStack<N>::get (const Identifier &name)
     295                 :             : {
     296                 :       11048 :   tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
     297                 :             : 
     298                 :             :   // TODO: Can we improve the API? have `reverse_iter` return an optional?
     299                 :       36813 :   reverse_iter ([&resolved_definition, &name] (Node &current) {
     300                 :       25765 :     auto candidate = current.rib.get (name.as_string ());
     301                 :             : 
     302                 :       25765 :     return candidate.map_or (
     303                 :       58493 :       [&resolved_definition] (Rib::Definition found) {
     304                 :        6963 :         if (found.is_variant ())
     305                 :             :           return KeepGoing::Yes;
     306                 :             :         // for most namespaces, we do not need to care about various ribs -
     307                 :             :         // they are available from all contexts if defined in the current
     308                 :             :         // scope, or an outermore one. so if we do have a candidate, we can
     309                 :             :         // return it directly and stop iterating
     310                 :        6960 :         resolved_definition = found;
     311                 :             : 
     312                 :        6960 :         return KeepGoing::No;
     313                 :             :       },
     314                 :             :       // if there was no candidate, we keep iterating
     315                 :       25765 :       KeepGoing::Yes);
     316                 :       25765 :   });
     317                 :             : 
     318                 :       11048 :   return resolved_definition;
     319                 :             : }
     320                 :             : 
     321                 :             : template <Namespace N>
     322                 :             : tl::optional<Rib::Definition>
     323                 :           9 : ForeverStack<N>::get_lang_prelude (const Identifier &name)
     324                 :             : {
     325                 :           9 :   return lang_prelude.rib.get (name.as_string ());
     326                 :             : }
     327                 :             : 
     328                 :             : template <Namespace N>
     329                 :             : tl::optional<Rib::Definition>
     330                 :        4110 : ForeverStack<N>::get_lang_prelude (const std::string &name)
     331                 :             : {
     332                 :        4110 :   return lang_prelude.rib.get (name);
     333                 :             : }
     334                 :             : 
     335                 :             : template <>
     336                 :          14 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
     337                 :             :   const Identifier &name)
     338                 :             : {
     339                 :          14 :   tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
     340                 :             : 
     341                 :          14 :   reverse_iter ([&resolved_definition, &name] (Node &current) {
     342                 :             :     // looking up for labels cannot go through function ribs
     343                 :             :     // TODO: What other ribs?
     344                 :          14 :     if (current.rib.kind == Rib::Kind::Function)
     345                 :             :       return KeepGoing::No;
     346                 :             : 
     347                 :          14 :     auto candidate = current.rib.get (name.as_string ());
     348                 :             : 
     349                 :             :     // FIXME: Factor this in a function with the generic `get`
     350                 :          14 :     return candidate.map_or (
     351                 :          34 :       [&resolved_definition] (Rib::Definition found) {
     352                 :           6 :         resolved_definition = found;
     353                 :             : 
     354                 :           6 :         return KeepGoing::No;
     355                 :             :       },
     356                 :          14 :       KeepGoing::Yes);
     357                 :          14 :   });
     358                 :             : 
     359                 :          14 :   return resolved_definition;
     360                 :             : }
     361                 :             : 
     362                 :             : /* Check if an iterator points to the last element */
     363                 :             : template <typename I, typename C>
     364                 :             : static bool
     365                 :        6610 : is_last (const I &iterator, const C &collection)
     366                 :             : {
     367                 :        6610 :   return iterator + 1 == collection.end ();
     368                 :             : }
     369                 :             : 
     370                 :             : /* Check if an iterator points to the start of the collection */
     371                 :             : template <typename I, typename C>
     372                 :             : static bool
     373                 :        2737 : is_start (const I &iterator, const C &collection)
     374                 :             : {
     375                 :        4937 :   return iterator == collection.begin ();
     376                 :             : }
     377                 :             : 
     378                 :             : template <Namespace N>
     379                 :             : typename ForeverStack<N>::Node &
     380                 :         385 : ForeverStack<N>::find_closest_module (Node &starting_point)
     381                 :             : {
     382                 :         385 :   auto *closest_module = &starting_point;
     383                 :             : 
     384                 :         799 :   reverse_iter (starting_point, [&closest_module] (Node &current) {
     385                 :         414 :     if (current.rib.kind == Rib::Kind::Module || current.is_root ())
     386                 :             :       {
     387                 :         385 :         closest_module = &current;
     388                 :         385 :         return KeepGoing::No;
     389                 :             :       }
     390                 :             : 
     391                 :             :     return KeepGoing::Yes;
     392                 :             :   });
     393                 :             : 
     394                 :         385 :   return *closest_module;
     395                 :             : }
     396                 :             : 
     397                 :             : /* If a the given condition is met, emit an error about misused leading path
     398                 :             :  * segments */
     399                 :             : template <typename S>
     400                 :             : static inline bool
     401                 :        4701 : check_leading_kw_at_start (std::vector<Error> &collect_errors, const S &segment,
     402                 :             :                            bool condition)
     403                 :             : {
     404                 :        4701 :   if (condition)
     405                 :          12 :     collect_errors.emplace_back (
     406                 :          12 :       segment.get_locus (), ErrorCode::E0433,
     407                 :             :       "%qs in paths can only be used in start position",
     408                 :          24 :       segment.as_string ().c_str ());
     409                 :             : 
     410                 :        4701 :   return condition;
     411                 :             : }
     412                 :             : 
     413                 :             : // we first need to handle the "starting" segments - `super`, `self` or
     414                 :             : // `crate`. we don't need to do anything for `self` and can just skip it. for
     415                 :             : // `crate`, we need to go back to the root of the current stack. for each
     416                 :             : // `super` segment, we go back to the cursor's parent until we reach the
     417                 :             : // correct one or the root.
     418                 :             : template <Namespace N>
     419                 :             : template <typename S>
     420                 :             : tl::optional<typename std::vector<S>::const_iterator>
     421                 :        2187 : ForeverStack<N>::find_starting_point (
     422                 :             :   const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point,
     423                 :             :   std::function<void (const S &, NodeId)> insert_segment_resolution,
     424                 :             :   std::vector<Error> &collect_errors)
     425                 :             : {
     426                 :        2187 :   auto iterator = segments.begin ();
     427                 :             : 
     428                 :        2369 :   for (; !is_last (iterator, segments); iterator++)
     429                 :             :     {
     430                 :        2200 :       auto &outer_seg = *iterator;
     431                 :             : 
     432                 :        2200 :       if (unwrap_segment_get_lang_item (outer_seg).has_value ())
     433                 :             :         break;
     434                 :             : 
     435                 :        2200 :       auto &seg = unwrap_type_segment (outer_seg);
     436                 :        2200 :       bool is_self_or_crate
     437                 :        2200 :         = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
     438                 :             : 
     439                 :             :       // if we're after the first path segment and meet `self` or `crate`, it's
     440                 :             :       // an error - we should only be seeing `super` keywords at this point
     441                 :        2200 :       if (check_leading_kw_at_start (collect_errors, seg,
     442                 :        2200 :                                      !is_start (iterator, segments)
     443                 :        2200 :                                        && is_self_or_crate))
     444                 :           2 :         return tl::nullopt;
     445                 :             : 
     446                 :        2198 :       if (seg.is_crate_path_seg ())
     447                 :             :         {
     448                 :         278 :           starting_point = root;
     449                 :         278 :           insert_segment_resolution (outer_seg, starting_point.get ().id);
     450                 :         278 :           iterator++;
     451                 :             :           break;
     452                 :             :         }
     453                 :        1920 :       if (seg.is_lower_self_seg ())
     454                 :             :         {
     455                 :             :           // insert segment resolution and exit
     456                 :          19 :           starting_point = find_closest_module (starting_point);
     457                 :          19 :           insert_segment_resolution (outer_seg, starting_point.get ().id);
     458                 :          19 :           iterator++;
     459                 :             :           break;
     460                 :             :         }
     461                 :        2083 :       if (seg.is_super_path_seg ())
     462                 :             :         {
     463                 :         184 :           starting_point = find_closest_module (starting_point);
     464                 :         184 :           if (starting_point.get ().is_root ())
     465                 :             :             {
     466                 :           2 :               collect_errors.emplace_back (
     467                 :           2 :                 seg.get_locus (), ErrorCode::E0433,
     468                 :             :                 "too many leading %<super%> keywords");
     469                 :           2 :               return tl::nullopt;
     470                 :             :             }
     471                 :             : 
     472                 :         182 :           starting_point
     473                 :         182 :             = find_closest_module (starting_point.get ().parent.value ());
     474                 :             : 
     475                 :         182 :           insert_segment_resolution (outer_seg, starting_point.get ().id);
     476                 :             :           continue;
     477                 :             :         }
     478                 :             : 
     479                 :             :       // now we've gone through the allowed `crate`, `self` or leading `super`
     480                 :             :       // segments. we can start resolving each segment itself.
     481                 :             :       // if we do see another leading segment, then we can error out.
     482                 :             :       break;
     483                 :             :     }
     484                 :             : 
     485                 :        2183 :   return iterator;
     486                 :             : }
     487                 :             : 
     488                 :             : template <Namespace N>
     489                 :             : template <typename S>
     490                 :             : tl::optional<typename ForeverStack<N>::Node &>
     491                 :        2183 : ForeverStack<N>::resolve_segments (
     492                 :             :   Node &starting_point, const std::vector<S> &segments,
     493                 :             :   typename std::vector<S>::const_iterator iterator,
     494                 :             :   std::function<void (const S &, NodeId)> insert_segment_resolution,
     495                 :             :   std::vector<Error> &collect_errors)
     496                 :             : {
     497                 :        2183 :   Node *current_node = &starting_point;
     498                 :        4684 :   for (; !is_last (iterator, segments); iterator++)
     499                 :             :     {
     500                 :        2501 :       auto &outer_seg = *iterator;
     501                 :             : 
     502                 :        2501 :       if (auto lang_item = unwrap_segment_get_lang_item (outer_seg))
     503                 :             :         {
     504                 :           0 :           NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
     505                 :           0 :             lang_item.value ());
     506                 :           0 :           current_node = &dfs_node (root, seg_id).value ();
     507                 :             : 
     508                 :           0 :           insert_segment_resolution (outer_seg, seg_id);
     509                 :           0 :           continue;
     510                 :           0 :         }
     511                 :             : 
     512                 :        2501 :       auto &seg = unwrap_type_segment (outer_seg);
     513                 :        2501 :       std::string str = seg.as_string ();
     514                 :        2501 :       rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
     515                 :             : 
     516                 :             :       // check that we don't encounter *any* leading keywords afterwards
     517                 :        2501 :       if (check_leading_kw_at_start (collect_errors, seg,
     518                 :        2501 :                                      seg.is_crate_path_seg ()
     519                 :        2501 :                                        || seg.is_super_path_seg ()
     520                 :        4994 :                                        || seg.is_lower_self_seg ()))
     521                 :          10 :         return tl::nullopt;
     522                 :             : 
     523                 :        2491 :       tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt;
     524                 :             : 
     525                 :             :       /*
     526                 :             :        * On every iteration this loop either
     527                 :             :        *
     528                 :             :        * 1. terminates
     529                 :             :        *
     530                 :             :        * 2. decreases the depth of the node pointed to by current_node until
     531                 :             :        *    current_node reaches the root
     532                 :             :        *
     533                 :             :        * 3. If the root node is reached, and we were not able to resolve the
     534                 :             :        *    segment, we search the prelude rib for the segment, by setting
     535                 :             :        *    current_node to point to the prelude, and toggling the
     536                 :             :        *    searched_prelude boolean to true. If current_node is the prelude
     537                 :             :        *    rib, and searched_prelude is true, we will exit.
     538                 :             :        *
     539                 :             :        * This ensures termination.
     540                 :             :        *
     541                 :             :        */
     542                 :        2491 :       bool searched_prelude = false;
     543                 :             :       while (true)
     544                 :             :         {
     545                 :             :           // may set the value of child
     546                 :       20747 :           for (auto &kv : current_node->children)
     547                 :             :             {
     548                 :       17586 :               auto &link = kv.first;
     549                 :             : 
     550                 :       35172 :               if (link.path.map_or (
     551                 :       42768 :                     [&str] (Identifier path) {
     552                 :        7596 :                       auto &path_str = path.as_string ();
     553                 :        7596 :                       return str == path_str;
     554                 :             :                     },
     555                 :       17586 :                     false))
     556                 :             :                 {
     557                 :        2058 :                   child = kv.second;
     558                 :             :                   break;
     559                 :             :                 }
     560                 :             :             }
     561                 :             : 
     562                 :        5219 :           if (child.has_value ())
     563                 :             :             {
     564                 :             :               break;
     565                 :             :             }
     566                 :             : 
     567                 :             :           if (N == Namespace::Types)
     568                 :             :             {
     569                 :        2942 :               auto rib_lookup = current_node->rib.get (seg.as_string ());
     570                 :        1475 :               if (rib_lookup && !rib_lookup->is_ambiguous ())
     571                 :             :                 {
     572                 :         265 :                   insert_segment_resolution (outer_seg,
     573                 :             :                                              rib_lookup->get_node_id ());
     574                 :         265 :                   return tl::nullopt;
     575                 :             :                 }
     576                 :        1475 :             }
     577                 :             : 
     578                 :        2896 :           if (current_node->is_root () && !searched_prelude)
     579                 :             :             {
     580                 :         159 :               searched_prelude = true;
     581                 :         159 :               current_node = &lang_prelude;
     582                 :         159 :               continue;
     583                 :             :             }
     584                 :             : 
     585                 :        2737 :           if (!is_start (iterator, segments)
     586                 :        2726 :               || current_node->rib.kind == Rib::Kind::Module
     587                 :        5462 :               || current_node->is_prelude ())
     588                 :             :             {
     589                 :         168 :               return tl::nullopt;
     590                 :             :             }
     591                 :             : 
     592                 :        2569 :           current_node = &current_node->parent.value ();
     593                 :             :         }
     594                 :             : 
     595                 :             :       // if child didn't contain a value
     596                 :             :       // the while loop above should have return'd or kept looping
     597                 :        2058 :       current_node = &child.value ();
     598                 :        2058 :       insert_segment_resolution (outer_seg, current_node->id);
     599                 :             :     }
     600                 :             : 
     601                 :        1740 :   return *current_node;
     602                 :             : }
     603                 :             : 
     604                 :             : template <>
     605                 :             : inline tl::optional<Rib::Definition>
     606                 :         520 : ForeverStack<Namespace::Types>::resolve_final_segment (Node &final_node,
     607                 :             :                                                        std::string &seg_name,
     608                 :             :                                                        bool is_lower_self)
     609                 :             : {
     610                 :         520 :   if (is_lower_self)
     611                 :          38 :     return Rib::Definition::NonShadowable (final_node.id);
     612                 :             :   else
     613                 :         482 :     return final_node.rib.get (seg_name);
     614                 :             : }
     615                 :             : 
     616                 :             : template <Namespace N>
     617                 :             : tl::optional<Rib::Definition>
     618                 :        1058 : ForeverStack<N>::resolve_final_segment (Node &final_node, std::string &seg_name,
     619                 :             :                                         bool is_lower_self)
     620                 :             : {
     621                 :        1058 :   return final_node.rib.get (seg_name);
     622                 :             : }
     623                 :             : 
     624                 :             : template <Namespace N>
     625                 :             : template <typename S>
     626                 :             : tl::optional<Rib::Definition>
     627                 :       10213 : ForeverStack<N>::resolve_path (
     628                 :             :   const std::vector<S> &segments, bool has_opening_scope_resolution,
     629                 :             :   std::function<void (const S &, NodeId)> insert_segment_resolution,
     630                 :             :   std::vector<Error> &collect_errors)
     631                 :             : {
     632                 :             :   // TODO: What to do if segments.empty() ?
     633                 :             : 
     634                 :             :   // handle paths with opening scopes
     635                 :       10213 :   std::function<void (void)> cleanup_current = [] () {};
     636                 :       10213 :   if (has_opening_scope_resolution)
     637                 :             :     {
     638                 :          42 :       Node *last_current = &cursor_reference.get ();
     639                 :          42 :       if (get_rust_edition () == Edition::E2015)
     640                 :          42 :         cursor_reference = root;
     641                 :             :       else
     642                 :           0 :         cursor_reference = extern_prelude;
     643                 :             :       cleanup_current
     644                 :          84 :         = [this, last_current] () { cursor_reference = *last_current; };
     645                 :             :     }
     646                 :             : 
     647                 :             :   // if there's only one segment, we just use `get`
     648                 :       10213 :   if (segments.size () == 1)
     649                 :             :     {
     650                 :        8026 :       auto &seg = segments.front ();
     651                 :        8026 :       if (auto lang_item = unwrap_segment_get_lang_item (seg))
     652                 :             :         {
     653                 :          78 :           NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node (
     654                 :          39 :             lang_item.value ());
     655                 :             : 
     656                 :          39 :           insert_segment_resolution (seg, seg_id);
     657                 :          39 :           cleanup_current ();
     658                 :             :           // TODO: does NonShadowable matter?
     659                 :          39 :           return Rib::Definition::NonShadowable (seg_id);
     660                 :             :         }
     661                 :             : 
     662                 :        7987 :       tl::optional<Rib::Definition> res
     663                 :       31888 :         = get (unwrap_type_segment (segments.back ()).as_string ());
     664                 :             : 
     665                 :        7987 :       if (!res)
     666                 :        6610 :         res = get_lang_prelude (
     667                 :       10036 :           unwrap_type_segment (segments.back ()).as_string ());
     668                 :             : 
     669                 :        7987 :       if (res && !res->is_ambiguous ())
     670                 :        7877 :         insert_segment_resolution (segments.back (), res->get_node_id ());
     671                 :        7987 :       cleanup_current ();
     672                 :        7987 :       return res;
     673                 :        7987 :     }
     674                 :             : 
     675                 :        2187 :   std::reference_wrapper<Node> starting_point = cursor ();
     676                 :             : 
     677                 :        2187 :   auto res
     678                 :        2187 :     = find_starting_point (segments, starting_point, insert_segment_resolution,
     679                 :             :                            collect_errors)
     680                 :        4374 :         .and_then (
     681                 :        4370 :           [this, &segments, &starting_point, &insert_segment_resolution,
     682                 :             :            &collect_errors] (typename std::vector<S>::const_iterator iterator) {
     683                 :        2183 :             return resolve_segments (starting_point.get (), segments, iterator,
     684                 :        2183 :                                      insert_segment_resolution, collect_errors);
     685                 :             :           })
     686                 :        3927 :         .and_then ([this, &segments, &insert_segment_resolution] (
     687                 :             :                      Node &final_node) -> tl::optional<Rib::Definition> {
     688                 :             :           // leave resolution within impl blocks to type checker
     689                 :        1740 :           if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
     690                 :         162 :             return tl::nullopt;
     691                 :             : 
     692                 :        1578 :           auto &seg = unwrap_type_segment (segments.back ());
     693                 :        1578 :           std::string seg_name = seg.as_string ();
     694                 :             : 
     695                 :             :           // assuming this can't be a lang item segment
     696                 :        1578 :           tl::optional<Rib::Definition> res
     697                 :             :             = resolve_final_segment (final_node, seg_name,
     698                 :        1578 :                                      seg.is_lower_self_seg ());
     699                 :             :           // Ok we didn't find it in the rib, Lets try the prelude...
     700                 :        1578 :           if (!res)
     701                 :         751 :             res = get_lang_prelude (seg_name);
     702                 :             : 
     703                 :        1578 :           if (res && !res->is_ambiguous ())
     704                 :         827 :             insert_segment_resolution (segments.back (), res->get_node_id ());
     705                 :             : 
     706                 :        1578 :           return res;
     707                 :        1578 :         });
     708                 :        2187 :   cleanup_current ();
     709                 :        2187 :   return res;
     710                 :        2187 : }
     711                 :             : 
     712                 :             : template <Namespace N>
     713                 :             : tl::optional<typename ForeverStack<N>::DfsResult>
     714                 :             : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
     715                 :             : {
     716                 :             :   auto values = starting_point.rib.get_values ();
     717                 :             : 
     718                 :             :   for (auto &kv : values)
     719                 :             :     {
     720                 :             :       for (auto id : kv.second.ids_shadowable)
     721                 :             :         if (id == to_find)
     722                 :             :           return {{starting_point, kv.first}};
     723                 :             :       for (auto id : kv.second.ids_non_shadowable)
     724                 :             :         if (id == to_find)
     725                 :             :           return {{starting_point, kv.first}};
     726                 :             :       for (auto id : kv.second.ids_globbed)
     727                 :             :         if (id == to_find)
     728                 :             :           return {{starting_point, kv.first}};
     729                 :             :     }
     730                 :             : 
     731                 :             :   for (auto &child : starting_point.children)
     732                 :             :     {
     733                 :             :       auto candidate = dfs (child.second, to_find);
     734                 :             : 
     735                 :             :       if (candidate.has_value ())
     736                 :             :         return candidate;
     737                 :             :     }
     738                 :             : 
     739                 :             :   return tl::nullopt;
     740                 :             : }
     741                 :             : 
     742                 :             : template <Namespace N>
     743                 :             : tl::optional<typename ForeverStack<N>::ConstDfsResult>
     744                 :      238940 : ForeverStack<N>::dfs (const ForeverStack<N>::Node &starting_point,
     745                 :             :                       NodeId to_find) const
     746                 :             : {
     747                 :      238940 :   auto values = starting_point.rib.get_values ();
     748                 :             : 
     749                 :      424214 :   for (auto &kv : values)
     750                 :             :     {
     751                 :      266251 :       for (auto id : kv.second.ids_shadowable)
     752                 :       75376 :         if (id == to_find)
     753                 :           0 :           return {{starting_point, kv.first}};
     754                 :      302400 :       for (auto id : kv.second.ids_non_shadowable)
     755                 :      117114 :         if (id == to_find)
     756                 :       11178 :           return {{starting_point, kv.first}};
     757                 :      185310 :       for (auto id : kv.second.ids_globbed)
     758                 :          36 :         if (id == to_find)
     759                 :          24 :           return {{starting_point, kv.first}};
     760                 :             :     }
     761                 :             : 
     762                 :      466678 :   for (auto &child : starting_point.children)
     763                 :             :     {
     764                 :      233339 :       auto candidate = dfs (child.second, to_find);
     765                 :             : 
     766                 :      233339 :       if (candidate.has_value ())
     767                 :        3940 :         return candidate;
     768                 :             :     }
     769                 :             : 
     770                 :      229399 :   return tl::nullopt;
     771                 :      238940 : }
     772                 :             : 
     773                 :             : template <Namespace N>
     774                 :             : tl::optional<Resolver::CanonicalPath>
     775                 :        5601 : ForeverStack<N>::to_canonical_path (NodeId id) const
     776                 :             : {
     777                 :             :   // find the id in the current forever stack, starting from the root,
     778                 :             :   // performing either a BFS or DFS once the Node containing the ID is found, go
     779                 :             :   // back up to the root (parent().parent().parent()...) accumulate link
     780                 :             :   // segments reverse them that's your canonical path
     781                 :             : 
     782                 :        6136 :   return dfs (root, id).map ([this, id] (ConstDfsResult tuple) {
     783                 :        5601 :     auto containing_node = tuple.first;
     784                 :        5601 :     auto name = tuple.second;
     785                 :             : 
     786                 :        5601 :     auto segments = std::vector<Resolver::CanonicalPath> ();
     787                 :             : 
     788                 :       15142 :     reverse_iter (containing_node, [&segments] (const Node &current) {
     789                 :        9541 :       if (current.is_root ())
     790                 :             :         return KeepGoing::No;
     791                 :             : 
     792                 :        3940 :       auto children = current.parent.value ().children;
     793                 :        3940 :       const Link *outer_link = nullptr;
     794                 :             : 
     795                 :       33160 :       for (auto &kv : children)
     796                 :             :         {
     797                 :       33160 :           auto &link = kv.first;
     798                 :       33160 :           auto &child = kv.second;
     799                 :             : 
     800                 :       33160 :           if (current.id == child.id)
     801                 :             :             {
     802                 :             :               outer_link = &link;
     803                 :             :               break;
     804                 :             :             }
     805                 :             :         }
     806                 :             : 
     807                 :        3940 :       rust_assert (outer_link);
     808                 :             : 
     809                 :        4420 :       outer_link->path.map ([&segments, outer_link] (Identifier path) {
     810                 :        2124 :         segments.emplace (segments.begin (),
     811                 :        2124 :                           Resolver::CanonicalPath::new_seg (outer_link->id,
     812                 :             :                                                             path.as_string ()));
     813                 :             :       });
     814                 :             : 
     815                 :        3940 :       return KeepGoing::Yes;
     816                 :        3940 :     });
     817                 :             : 
     818                 :        5601 :     auto &mappings = Analysis::Mappings::get ();
     819                 :        5601 :     CrateNum crate_num = mappings.lookup_crate_num (root.id).value ();
     820                 :        5601 :     auto path = Resolver::CanonicalPath::new_seg (
     821                 :        5601 :       root.id, mappings.get_crate_name (crate_num).value ());
     822                 :        5601 :     path.set_crate_num (crate_num);
     823                 :             : 
     824                 :        7725 :     for (const auto &segment : segments)
     825                 :        2124 :       path = path.append (segment);
     826                 :             : 
     827                 :             :     // Finally, append the name
     828                 :        5601 :     path = path.append (Resolver::CanonicalPath::new_seg (id, name));
     829                 :             : 
     830                 :        5601 :     return path;
     831                 :       11202 :   });
     832                 :             : }
     833                 :             : 
     834                 :             : template <Namespace N>
     835                 :             : tl::optional<Rib &>
     836                 :         127 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
     837                 :             : {
     838                 :         127 :   return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & {
     839                 :           2 :     return x.rib;
     840                 :         127 :   });
     841                 :             : }
     842                 :             : 
     843                 :             : template <Namespace N>
     844                 :             : tl::optional<const Rib &>
     845                 :           2 : ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point,
     846                 :             :                           NodeId to_find) const
     847                 :             : {
     848                 :           2 :   return dfs_node (starting_point, to_find)
     849                 :           2 :     .map ([] (const Node &x) -> const Rib & { return x.rib; });
     850                 :             : }
     851                 :             : 
     852                 :             : template <Namespace N>
     853                 :             : tl::optional<typename ForeverStack<N>::Node &>
     854                 :         127 : ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point,
     855                 :             :                            NodeId to_find)
     856                 :             : {
     857                 :         127 :   if (starting_point.id == to_find)
     858                 :           2 :     return starting_point;
     859                 :             : 
     860                 :         125 :   for (auto &child : starting_point.children)
     861                 :             :     {
     862                 :           0 :       auto candidate = dfs_node (child.second, to_find);
     863                 :             : 
     864                 :           0 :       if (candidate.has_value ())
     865                 :           0 :         return candidate;
     866                 :             :     }
     867                 :             : 
     868                 :         125 :   return tl::nullopt;
     869                 :             : }
     870                 :             : 
     871                 :             : template <Namespace N>
     872                 :             : tl::optional<const typename ForeverStack<N>::Node &>
     873                 :         139 : ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point,
     874                 :             :                            NodeId to_find) const
     875                 :             : {
     876                 :         139 :   if (starting_point.id == to_find)
     877                 :          16 :     return starting_point;
     878                 :             : 
     879                 :         201 :   for (auto &child : starting_point.children)
     880                 :             :     {
     881                 :         111 :       auto candidate = dfs_node (child.second, to_find);
     882                 :             : 
     883                 :         111 :       if (candidate.has_value ())
     884                 :          33 :         return candidate;
     885                 :             :     }
     886                 :             : 
     887                 :          90 :   return tl::nullopt;
     888                 :             : }
     889                 :             : 
     890                 :             : template <Namespace N>
     891                 :             : tl::optional<Rib &>
     892                 :             : ForeverStack<N>::to_rib (NodeId rib_id)
     893                 :             : {
     894                 :             :   return dfs_rib (root, rib_id);
     895                 :             : }
     896                 :             : 
     897                 :             : template <Namespace N>
     898                 :             : tl::optional<const Rib &>
     899                 :           2 : ForeverStack<N>::to_rib (NodeId rib_id) const
     900                 :             : {
     901                 :           2 :   return dfs_rib (root, rib_id);
     902                 :             : }
     903                 :             : 
     904                 :             : template <Namespace N>
     905                 :             : void
     906                 :           0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
     907                 :             :                              const std::string &next,
     908                 :             :                              const std::string &next_next) const
     909                 :             : {
     910                 :           0 :   std::string rib_kind = Rib::kind_to_string (rib.kind);
     911                 :           0 :   stream << next << "rib [" << rib_kind << "]: {";
     912                 :           0 :   if (rib.get_values ().empty ())
     913                 :             :     {
     914                 :           0 :       stream << "}\n";
     915                 :           0 :       return;
     916                 :             :     }
     917                 :             :   else
     918                 :             :     {
     919                 :           0 :       stream << "\n";
     920                 :             :     }
     921                 :             : 
     922                 :           0 :   for (const auto &kv : rib.get_values ())
     923                 :           0 :     stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
     924                 :             : 
     925                 :           0 :   stream << next << "},\n";
     926                 :           0 : }
     927                 :             : 
     928                 :             : template <Namespace N>
     929                 :             : void
     930                 :           0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
     931                 :             :                               const ForeverStack<N>::Node &node) const
     932                 :             : {
     933                 :           0 :   auto indent = std::string (indentation, ' ');
     934                 :           0 :   auto next = std::string (indentation + 4, ' ');
     935                 :           0 :   auto next_next = std::string (indentation + 8, ' ');
     936                 :             : 
     937                 :             :   stream << indent << "Node {\n"
     938                 :           0 :          << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
     939                 :           0 :          << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
     940                 :           0 :          << ",\n";
     941                 :             : 
     942                 :           0 :   stream_rib (stream, node.rib, next, next_next);
     943                 :             : 
     944                 :           0 :   stream << indent << "}\n";
     945                 :             : 
     946                 :           0 :   for (auto &kv : node.children)
     947                 :             :     {
     948                 :           0 :       auto link = kv.first;
     949                 :           0 :       auto child = kv.second;
     950                 :           0 :       stream << indent << "Link (" << link.id << ", "
     951                 :           0 :              << (link.path.has_value () ? link.path.value ().as_string ()
     952                 :           0 :                                         : "<anon>")
     953                 :           0 :              << "):\n";
     954                 :             : 
     955                 :           0 :       stream_node (stream, indentation + 4, child);
     956                 :             : 
     957                 :           0 :       stream << '\n';
     958                 :             :     }
     959                 :           0 : }
     960                 :             : 
     961                 :             : template <Namespace N>
     962                 :             : std::string
     963                 :           0 : ForeverStack<N>::as_debug_string () const
     964                 :             : {
     965                 :           0 :   std::stringstream stream;
     966                 :             : 
     967                 :           0 :   stream_node (stream, 0, root);
     968                 :             : 
     969                 :           0 :   return stream.str ();
     970                 :           0 : }
     971                 :             : 
     972                 :             : template <Namespace N>
     973                 :             : bool
     974                 :          13 : ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const
     975                 :             : {
     976                 :          13 :   return dfs_node (dfs_node (root, parent).value (), child).has_value ();
     977                 :             : }
     978                 :             : 
     979                 :             : // FIXME: Can we add selftests?
     980                 :             : 
     981                 :             : } // namespace Resolver2_0
     982                 :             : } // namespace Rust
        

Generated by: LCOV version 2.1-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.