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 78452 : NameResolutionContext::should_search_prelude (
34 : const typename ForeverStack<N>::Node *current_node,
35 : const typename ForeverStack<N>::SegIterator &iterator,
36 : const std::vector<ResolutionPath::Segment> &segments)
37 : {
38 : // Check whether the current_node is a root node
39 78452 : 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 78430 : if (is_start (iterator, segments)
45 78430 : && 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 274339 : 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 274339 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point
59 : = stack.cursor ();
60 :
61 274339 : return NameResolutionContext::resolve_path (stack, path, mode,
62 : insert_segment_resolution,
63 274339 : collect_errors, starting_point);
64 : }
65 :
66 : template <Namespace N>
67 : tl::optional<Rib::Definition>
68 25957 : 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 25957 : 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 25957 : if (!starting_point)
79 0 : return tl::nullopt;
80 :
81 25957 : return NameResolutionContext::resolve_path (stack, path, mode,
82 : insert_segment_resolution,
83 25957 : collect_errors, *starting_point);
84 : }
85 :
86 : template <Namespace N>
87 : tl::optional<Rib::Definition>
88 300296 : 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 300296 : bool can_descend = true;
95 :
96 300296 : rust_debug ("resolving %s", path.as_string ().c_str ());
97 :
98 300296 : if (auto lang_item = path.get_lang_prefix ())
99 : {
100 : NodeId seg_id
101 1210 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
102 :
103 1210 : insert_segment_resolution (Usage (lang_item->second), Definition (seg_id),
104 : N);
105 :
106 1210 : if (path.get_segments ().empty ())
107 1210 : 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 299086 : switch (mode)
118 : {
119 : case ResolutionMode::Normal:
120 : break; // default
121 952 : case ResolutionMode::FromRoot:
122 952 : starting_point = stack.root;
123 952 : break;
124 1475 : case ResolutionMode::FromExtern:
125 1475 : starting_point = stack.extern_prelude;
126 1475 : break;
127 0 : default:
128 0 : rust_unreachable ();
129 : }
130 : }
131 :
132 299086 : if (path.get_segments ().empty ())
133 2 : return Rib::Definition::NonShadowable (starting_point.get ().id);
134 :
135 299084 : auto &segments = path.get_segments ();
136 :
137 : // if there's only one segment, we just use `get`
138 598168 : if (can_descend && segments.size () == 1)
139 : {
140 218236 : auto &seg = segments.front ();
141 :
142 218236 : tl::optional<Rib::Definition> res
143 872944 : = stack.get (starting_point.get (), seg.name);
144 :
145 218236 : if (!res)
146 109936 : res = stack.get_lang_prelude (seg.name);
147 :
148 128263 : if (N == Namespace::Types && !res)
149 : {
150 707 : if (seg.is_crate_path_seg ())
151 : {
152 267 : insert_segment_resolution (Usage (seg.node_id),
153 267 : Definition (stack.root.id), N);
154 : // TODO: does NonShadowable matter?
155 267 : return Rib::Definition::NonShadowable (stack.root.id);
156 : }
157 440 : else if (seg.is_lower_self_seg ())
158 : {
159 3 : NodeId id = stack.find_closest_module (starting_point.get ()).id;
160 3 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
161 : N);
162 : // TODO: does NonShadowable matter?
163 3 : return Rib::Definition::NonShadowable (id);
164 : }
165 437 : else if (seg.is_super_path_seg ())
166 : {
167 : auto &closest_module
168 273 : = stack.find_closest_module (starting_point.get ());
169 273 : 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 273 : NodeId id
177 273 : = stack.find_closest_module (closest_module.parent.value ()).id;
178 273 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
179 : N);
180 : // TODO: does NonShadowable matter?
181 273 : return Rib::Definition::NonShadowable (id);
182 : }
183 : }
184 :
185 : // FIXME: Is the NS to insert_segment_resolution valid?
186 217693 : if (res && !res->is_ambiguous ())
187 216551 : insert_segment_resolution (Usage (seg.node_id),
188 216551 : Definition (res->get_node_id ()), N);
189 217693 : return res;
190 218236 : }
191 :
192 80848 : auto iterator = segments.begin ();
193 80848 : if (can_descend)
194 : {
195 80848 : if (auto res = stack.find_starting_point (segments, starting_point,
196 : insert_segment_resolution,
197 : collect_errors))
198 80846 : iterator = *res;
199 : else
200 2 : return tl::nullopt;
201 :
202 : // if find_starting_point used all segments, return early
203 80846 : if (iterator == segments.end ())
204 : {
205 : if (N == Namespace::Types)
206 6 : 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 80840 : auto node
217 80840 : = resolve_segments (types, starting_point.get (), segments, iterator,
218 : insert_segment_resolution, collect_errors);
219 :
220 80840 : if (!node)
221 22569 : return tl::nullopt;
222 :
223 : // This node now represents the Node which *should* contain the definition
224 : // used by the last segment.
225 58271 : auto &final_node = node.value ();
226 :
227 : // leave resolution within impl blocks to type checker
228 58271 : if (final_node.rib (N).kind == Rib::Kind::TraitOrImpl)
229 0 : return tl::nullopt;
230 :
231 58271 : auto &seg = segments.back ();
232 58271 : std::string seg_name = seg.name;
233 :
234 58271 : tl::optional<Rib::Definition> res
235 : = resolve_final_segment (stack, final_node, seg_name,
236 : seg.is_lower_self_seg ());
237 : // Ok we didn't find it in the rib, Lets try the prelude...
238 58271 : if (!res)
239 35077 : res = stack.get_lang_prelude (seg_name);
240 :
241 58271 : if (res && !res->is_ambiguous ())
242 23196 : insert_segment_resolution (Usage (seg.node_id),
243 23196 : Definition (res->get_node_id ()), N);
244 :
245 58271 : return res;
246 58271 : }
247 :
248 : template <Namespace N>
249 : tl::optional<typename ForeverStack<N>::Node &>
250 80840 : NameResolutionContext::resolve_segments (
251 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &starting_point,
252 : const std::vector<ResolutionPath::Segment> &segments,
253 : typename ForeverStack<N>::SegIterator iterator,
254 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
255 : std::vector<Error> &collect_errors)
256 : {
257 80840 : auto *current_node = &starting_point;
258 167311 : for (; !is_last (iterator, segments); iterator++)
259 : {
260 86471 : auto &seg = *iterator;
261 :
262 172942 : std::string str = seg.name;
263 :
264 : // check that we don't encounter *any* leading keywords afterwards
265 86471 : if (check_leading_kw_at_start (collect_errors, seg,
266 86471 : seg.is_crate_path_seg ()
267 86471 : || seg.is_super_path_seg ()
268 86464 : || seg.is_lower_self_seg ()))
269 10 : return tl::nullopt;
270 :
271 86461 : 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 86461 : bool searched_prelude = false;
292 86322 : while (true)
293 : {
294 198423 : if (is_start (iterator, segments)
295 315780 : && current_node->rib (N).kind == Rib::Kind::TraitOrImpl)
296 : {
297 : // we can't reference associated types/functions like this
298 17730 : current_node = ¤t_node->parent.value ();
299 30469 : continue;
300 : }
301 :
302 : // may set the value of child
303 3134996 : for (auto &kv : current_node->children)
304 : {
305 3029856 : auto &link = kv.first;
306 :
307 6059712 : if (link.path.map_or (
308 1004281 : [&str] (Identifier path) {
309 1004281 : auto &path_str = path.as_string ();
310 1004281 : return str == path_str;
311 : },
312 3029856 : false))
313 : {
314 220786 : child = kv.second;
315 : break;
316 : }
317 : }
318 :
319 162963 : if (child.has_value ())
320 : {
321 : break;
322 : }
323 :
324 105140 : auto rib_lookup = current_node->rib (N).get (seg.name);
325 105140 : if (rib_lookup && !rib_lookup->is_ambiguous ())
326 : {
327 14467 : if (Analysis::Mappings::get ()
328 14467 : .lookup_glob_container (rib_lookup->get_node_id ())
329 14467 : .has_value ())
330 : {
331 6079 : NodeId leaf_module
332 6079 : = stack.find_leaf_definition (rib_lookup->get_node_id ())
333 6079 : .value_or (Definition (rib_lookup->get_node_id ()))
334 : .id;
335 :
336 6079 : if (auto new_child = stack.dfs_node (stack.root, leaf_module))
337 : {
338 6079 : child = new_child.value ();
339 6079 : break;
340 : }
341 : else
342 : {
343 0 : return tl::nullopt;
344 : }
345 : }
346 : else
347 : {
348 : // FIXME: Resolve segments always resolves in the Types NS
349 : // correct? If so, we should remove the template parameter for
350 : // this function - and use NS::Types directly here instead of
351 : // N
352 8388 : insert_segment_resolution (Usage (seg.node_id),
353 8388 : Definition (
354 : rib_lookup->get_node_id ()),
355 : N);
356 :
357 8388 : return tl::nullopt;
358 : }
359 : }
360 :
361 12739 : if (!searched_prelude
362 156386 : && should_search_prelude<N> (current_node, iterator, segments))
363 : {
364 12739 : searched_prelude = true;
365 12739 : current_node = &stack.lang_prelude;
366 : continue;
367 : }
368 :
369 77934 : if (!is_start (iterator, segments)
370 75982 : || current_node->rib (N).kind == Rib::Kind::Module
371 153916 : || current_node->is_prelude ())
372 : {
373 14171 : return tl::nullopt;
374 : }
375 :
376 63763 : current_node = ¤t_node->parent.value ();
377 : }
378 :
379 : // if child didn't point to a value
380 : // the while loop above would have returned or kept looping
381 63902 : current_node = &child->get ();
382 63902 : insert_segment_resolution (Usage (seg.node_id),
383 63902 : Definition (current_node->id), N);
384 : }
385 :
386 58271 : return *current_node;
387 : }
388 :
389 : template <>
390 : inline tl::optional<Rib::Definition>
391 23712 : NameResolutionContext::resolve_final_segment (
392 : ForeverStack<Namespace::Types> &stack,
393 : typename ForeverStack<Namespace::Types>::Node &final_node,
394 : std::string &seg_name, bool is_lower_self)
395 : {
396 23712 : if (is_lower_self)
397 99 : return Rib::Definition::NonShadowable (final_node.id);
398 : else
399 23613 : return final_node.rib_types.get (seg_name);
400 : }
401 :
402 : template <Namespace N>
403 : tl::optional<Rib::Definition>
404 34559 : NameResolutionContext::resolve_final_segment (
405 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &final_node,
406 : std::string &seg_name, bool is_lower_self)
407 : {
408 34559 : return final_node.rib (N).get (seg_name);
409 : }
410 :
411 : } // namespace Resolver2_0
412 : } // namespace Rust
|
