Line data Source code
1 : // Copyright (C) 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 "optional.h"
20 : #include "rust-forever-stack.h"
21 : #include "rust-name-resolution-context.h"
22 :
23 : /**
24 : * Split the actual path resolution logic in its own file because it's a lot,
25 : * and it could get even worse for certain edge cases.
26 : */
27 :
28 : namespace Rust {
29 : namespace Resolver2_0 {
30 :
31 : template <Namespace N>
32 : bool
33 456360 : NameResolutionContext::should_search_prelude (
34 : const typename ForeverStack<N>::Node *current_node,
35 : const typename ForeverStack<N>::SegIterator &iterator,
36 : const std::vector<ResolutionPathSegment> &segments)
37 : {
38 : // Check whether the current_node is a root node
39 456360 : if (current_node->is_root ())
40 : return true;
41 :
42 : // Check whether we're at the start of a module (we can't travel elsewhere
43 : // from the start of a module)
44 455779 : if (is_start (iterator, segments)
45 455779 : && current_node->rib (N).kind == Rib::Kind::Module)
46 : return true;
47 :
48 : return false;
49 : }
50 :
51 : template <Namespace N>
52 : tl::optional<Rib::Definition>
53 1613194 : NameResolutionContext::resolve_path (
54 : ForeverStack<N> &stack, const ResolutionPath &path, ResolutionMode mode,
55 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
56 : std::vector<Error> &collect_errors)
57 : {
58 1613194 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point
59 : = stack.cursor ();
60 :
61 1613194 : return NameResolutionContext::resolve_path (stack, path, mode,
62 : insert_segment_resolution,
63 1613194 : collect_errors, starting_point);
64 : }
65 :
66 : template <Namespace N>
67 : tl::optional<Rib::Definition>
68 206432 : NameResolutionContext::resolve_path (
69 : ForeverStack<N> &stack, const ResolutionPath &path, ResolutionMode mode,
70 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
71 : std::vector<Error> &collect_errors, NodeId starting_point_id)
72 :
73 : {
74 206432 : auto starting_point = stack.dfs_node (stack.root, starting_point_id);
75 :
76 : // We may have a prelude, but haven't visited it yet and thus it's not in
77 : // our nodes
78 206432 : if (!starting_point)
79 0 : return tl::nullopt;
80 :
81 206432 : return NameResolutionContext::resolve_path (stack, path, mode,
82 : insert_segment_resolution,
83 206432 : collect_errors, *starting_point);
84 : }
85 :
86 : template <Namespace N>
87 : tl::optional<Rib::Definition>
88 1819626 : NameResolutionContext::resolve_path (
89 : ForeverStack<N> &stack, const ResolutionPath &path, ResolutionMode mode,
90 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
91 : std::vector<Error> &collect_errors,
92 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point)
93 : {
94 1819626 : bool can_descend = true;
95 :
96 1819626 : rust_debug ("resolving %s", path.as_string ().c_str ());
97 :
98 1819626 : if (auto lang_item = path.get_lang_prefix ())
99 : {
100 : NodeId seg_id
101 7230 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
102 :
103 7230 : insert_segment_resolution (Usage (lang_item->second), Definition (seg_id),
104 : N);
105 :
106 7230 : if (path.get_segments ().empty ())
107 7230 : return Rib::Definition::NonShadowable (seg_id);
108 :
109 0 : auto new_start = stack.dfs_node (stack.root, seg_id);
110 0 : rust_assert (new_start.has_value ());
111 0 : starting_point = new_start.value ();
112 :
113 0 : can_descend = false;
114 : }
115 : else
116 : {
117 1812396 : switch (mode)
118 : {
119 : case ResolutionMode::Normal:
120 : break; // default
121 2890 : case ResolutionMode::FromRoot:
122 2890 : starting_point = stack.root;
123 2890 : break;
124 28 : case ResolutionMode::FromExtern:
125 28 : starting_point = stack.extern_prelude;
126 28 : break;
127 0 : default:
128 0 : rust_unreachable ();
129 : }
130 : }
131 :
132 1812396 : if (path.get_segments ().empty ())
133 4 : return Rib::Definition::NonShadowable (starting_point.get ().id);
134 :
135 1812392 : auto &segments = path.get_segments ();
136 :
137 : // if there's only one segment, we just use `get`
138 3624784 : if (can_descend && segments.size () == 1)
139 : {
140 1258599 : auto &seg = segments.front ();
141 :
142 1258599 : tl::optional<Rib::Definition> res
143 5034396 : = stack.get (starting_point.get (), seg.name);
144 :
145 1258599 : if (!res)
146 514740 : res = stack.get_lang_prelude (seg.name);
147 :
148 654465 : if (N == Namespace::Types && !res)
149 : {
150 4346 : if (seg.is_crate_path_seg ())
151 : {
152 1771 : insert_segment_resolution (Usage (seg.node_id),
153 1771 : Definition (stack.root.id), N);
154 : // TODO: does NonShadowable matter?
155 1771 : return Rib::Definition::NonShadowable (stack.root.id);
156 : }
157 2575 : else if (seg.is_lower_self_seg ())
158 : {
159 2 : NodeId id = stack.find_closest_module (starting_point.get ()).id;
160 2 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
161 : N);
162 : // TODO: does NonShadowable matter?
163 2 : return Rib::Definition::NonShadowable (id);
164 : }
165 2573 : else if (seg.is_super_path_seg ())
166 : {
167 : auto &closest_module
168 2182 : = stack.find_closest_module (starting_point.get ());
169 2182 : if (closest_module.is_root ())
170 : {
171 0 : rust_error_at (seg.locus, ErrorCode::E0433,
172 : "too many leading %<super%> keywords");
173 0 : return tl::nullopt;
174 : }
175 :
176 2182 : NodeId id
177 2182 : = stack.find_closest_module (closest_module.parent.value ()).id;
178 2182 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
179 : N);
180 : // TODO: does NonShadowable matter?
181 2182 : return Rib::Definition::NonShadowable (id);
182 : }
183 : }
184 :
185 : // FIXME: Is the NS to insert_segment_resolution valid?
186 1254644 : if (res && !res->is_ambiguous ())
187 1249754 : insert_segment_resolution (Usage (seg.node_id),
188 1249754 : Definition (res->get_node_id ()), N);
189 1254644 : return res;
190 1258599 : }
191 :
192 553793 : auto iterator = segments.begin ();
193 553793 : if (can_descend)
194 : {
195 553793 : if (auto res = stack.find_starting_point (path, starting_point,
196 : insert_segment_resolution,
197 : collect_errors))
198 553785 : iterator = *res;
199 : else
200 8 : return tl::nullopt;
201 :
202 : // if find_starting_point used all segments, return early
203 553785 : if (iterator == segments.end ())
204 : {
205 : if (N == Namespace::Types)
206 34 : return Rib::Definition::NonShadowable (starting_point.get ().id);
207 : else
208 0 : return tl::nullopt;
209 : }
210 : }
211 :
212 : // We do the first part of path resolution exclusively in the types NS - this
213 : // gives us a node in which to resolve the last segment of the path.
214 :
215 : // nodes are shared between stacks
216 553751 : auto node = resolve_segments (types, starting_point.get (), path, iterator,
217 : insert_segment_resolution, collect_errors);
218 :
219 553751 : if (!node)
220 167916 : return tl::nullopt;
221 :
222 : // This node now represents the Node which *should* contain the definition
223 : // used by the last segment.
224 385835 : auto &final_node = node.value ();
225 :
226 : // leave resolution within impl blocks to type checker
227 385835 : if (final_node.rib (N).kind == Rib::Kind::TraitOrImpl)
228 0 : return tl::nullopt;
229 :
230 385835 : auto &seg = segments.back ();
231 385835 : std::string seg_name = seg.name;
232 :
233 385835 : tl::optional<Rib::Definition> res
234 : = resolve_final_segment (stack, final_node, seg_name,
235 : seg.is_lower_self_seg ());
236 : // Ok we didn't find it in the rib, Lets try the prelude...
237 385835 : if (!res)
238 251849 : res = stack.get_lang_prelude (seg_name);
239 :
240 385835 : if (res && !res->is_ambiguous ())
241 134016 : insert_segment_resolution (Usage (seg.node_id),
242 134016 : Definition (res->get_node_id ()), N);
243 :
244 385835 : return res;
245 385835 : }
246 :
247 : template <Namespace N>
248 : tl::optional<typename ForeverStack<N>::Node &>
249 553751 : NameResolutionContext::resolve_segments (
250 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &starting_point,
251 : const RawPath<ResolutionPathSegment> &path,
252 : typename ForeverStack<N>::SegIterator iterator,
253 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
254 : std::vector<Error> &collect_errors)
255 : {
256 553751 : auto *current_node = &starting_point;
257 553751 : auto &segments = path.get_segments ();
258 1140963 : for (; !is_last (iterator, segments); iterator++)
259 : {
260 587212 : auto &seg = *iterator;
261 :
262 1174424 : std::string str = seg.name;
263 :
264 : // check that we don't encounter *any* leading keywords afterwards
265 587212 : if (check_leading_kw_at_start (collect_errors, seg,
266 587212 : seg.is_crate_path_seg ()
267 587212 : || seg.is_super_path_seg ()
268 587205 : || seg.is_lower_self_seg ()))
269 10 : return tl::nullopt;
270 :
271 587202 : tl::optional<std::reference_wrapper<typename ForeverStack<N>::Node>> child
272 : = tl::nullopt;
273 :
274 : /*
275 : * On every iteration this loop either
276 : *
277 : * 1. terminates
278 : *
279 : * 2. decreases the depth of the node pointed to by current_node until
280 : * current_node reaches the root
281 : *
282 : * 3. If the root node is reached, and we were not able to resolve the
283 : * segment, we search the prelude rib for the segment, by setting
284 : * current_node to point to the prelude, and toggling the
285 : * searched_prelude boolean to true. If current_node is the prelude
286 : * rib, and searched_prelude is true, we will exit.
287 : *
288 : * This ensures termination.
289 : *
290 : */
291 587202 : bool searched_prelude = false;
292 507560 : while (true)
293 : {
294 1232650 : if (is_start (iterator, segments)
295 1928283 : && current_node->rib (N).kind == Rib::Kind::TraitOrImpl)
296 : {
297 : // we can't reference associated types/functions like this
298 102335 : current_node = ¤t_node->parent.value ();
299 203459 : continue;
300 : }
301 :
302 : // may set the value of child
303 24899523 : for (auto &kv : current_node->children)
304 : {
305 24254317 : auto &link = kv.first;
306 :
307 48508634 : if (link.path.map_or (
308 6725861 : [&str] (Identifier path) {
309 6725861 : auto &path_str = path.as_string ();
310 6725861 : return str == path_str;
311 : },
312 24254317 : false))
313 : {
314 1410754 : child = kv.second;
315 : break;
316 : }
317 : }
318 :
319 1027980 : if (child.has_value ())
320 : {
321 : break;
322 : }
323 :
324 645206 : auto rib_lookup = current_node->rib (N).get (seg.name);
325 645206 : if (rib_lookup && !rib_lookup->is_ambiguous ())
326 : {
327 91841 : if (Analysis::Mappings::get ()
328 91841 : .lookup_glob_container (rib_lookup->get_node_id ())
329 91841 : .has_value ())
330 : {
331 36522 : NodeId leaf_module
332 36522 : = stack.find_leaf_definition (rib_lookup->get_node_id ())
333 36522 : .value_or (Definition (rib_lookup->get_node_id ()))
334 : .id;
335 :
336 36522 : if (auto new_child = stack.dfs_node (stack.root, leaf_module))
337 : {
338 36522 : child = new_child.value ();
339 36522 : break;
340 : }
341 : else
342 : {
343 0 : return tl::nullopt;
344 : }
345 : }
346 : else
347 : {
348 : // Non glob containers such as structures, we insert the
349 : // segment but we let the type checker handle the rest since
350 : // it has to resolve methode resolution & cie
351 :
352 : // FIXME: Resolve segments always resolves in the Types NS
353 : // correct? If so, we should remove the template parameter for
354 : // this function - and use NS::Types directly here instead of
355 : // N
356 55319 : insert_segment_resolution (Usage (seg.node_id),
357 55319 : Definition (
358 : rib_lookup->get_node_id ()),
359 : N);
360 :
361 55319 : return tl::nullopt;
362 : }
363 : }
364 :
365 101124 : if (!searched_prelude
366 908601 : && should_search_prelude<N> (current_node, iterator, segments))
367 : {
368 101124 : searched_prelude = true;
369 101124 : current_node = &stack.lang_prelude;
370 : continue;
371 : }
372 :
373 452241 : if (!is_start (iterator, segments)
374 436098 : || current_node->rib (N).kind == Rib::Kind::Module
375 888339 : || current_node->is_prelude ())
376 : {
377 112587 : return tl::nullopt;
378 : }
379 :
380 339654 : current_node = ¤t_node->parent.value ();
381 : }
382 :
383 : // if child didn't point to a value
384 : // the while loop above would have returned or kept looping
385 419296 : current_node = &child->get ();
386 419296 : insert_segment_resolution (Usage (seg.node_id),
387 419296 : Definition (current_node->id), N);
388 : }
389 :
390 385835 : return *current_node;
391 : }
392 :
393 : template <>
394 : inline tl::optional<Rib::Definition>
395 172249 : NameResolutionContext::resolve_final_segment (
396 : ForeverStack<Namespace::Types> &stack,
397 : typename ForeverStack<Namespace::Types>::Node &final_node,
398 : std::string &seg_name, bool is_lower_self)
399 : {
400 172249 : if (is_lower_self)
401 440 : return Rib::Definition::NonShadowable (final_node.id);
402 : else
403 171809 : return final_node.rib_types.get (seg_name);
404 : }
405 :
406 : template <Namespace N>
407 : tl::optional<Rib::Definition>
408 213586 : NameResolutionContext::resolve_final_segment (
409 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &final_node,
410 : std::string &seg_name, bool is_lower_self)
411 : {
412 213586 : return final_node.rib (N).get (seg_name);
413 : }
414 :
415 : } // namespace Resolver2_0
416 : } // namespace Rust
|