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 88940 : 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 88940 : 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 88359 : if (is_start (iterator, segments)
45 88359 : && 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 303254 : 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 303254 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point
59 : = stack.cursor ();
60 :
61 303254 : return NameResolutionContext::resolve_path (stack, path, mode,
62 : insert_segment_resolution,
63 303254 : collect_errors, starting_point);
64 : }
65 :
66 : template <Namespace N>
67 : tl::optional<Rib::Definition>
68 25804 : 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 25804 : 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 25804 : if (!starting_point)
79 0 : return tl::nullopt;
80 :
81 25804 : return NameResolutionContext::resolve_path (stack, path, mode,
82 : insert_segment_resolution,
83 25804 : collect_errors, *starting_point);
84 : }
85 :
86 : template <Namespace N>
87 : tl::optional<Rib::Definition>
88 329058 : 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 329058 : bool can_descend = true;
95 :
96 329058 : rust_debug ("resolving %s", path.as_string ().c_str ());
97 :
98 329058 : if (auto lang_item = path.get_lang_prefix ())
99 : {
100 : NodeId seg_id
101 1525 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
102 :
103 1525 : insert_segment_resolution (Usage (lang_item->second), Definition (seg_id),
104 : N);
105 :
106 1525 : if (path.get_segments ().empty ())
107 1525 : 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 327533 : switch (mode)
118 : {
119 : case ResolutionMode::Normal:
120 : break; // default
121 966 : case ResolutionMode::FromRoot:
122 966 : starting_point = stack.root;
123 966 : break;
124 2051 : case ResolutionMode::FromExtern:
125 2051 : starting_point = stack.extern_prelude;
126 2051 : break;
127 0 : default:
128 0 : rust_unreachable ();
129 : }
130 : }
131 :
132 327533 : if (path.get_segments ().empty ())
133 2 : return Rib::Definition::NonShadowable (starting_point.get ().id);
134 :
135 327531 : auto &segments = path.get_segments ();
136 :
137 : // if there's only one segment, we just use `get`
138 655062 : if (can_descend && segments.size () == 1)
139 : {
140 238936 : auto &seg = segments.front ();
141 :
142 238936 : tl::optional<Rib::Definition> res
143 955744 : = stack.get (starting_point.get (), seg.name);
144 :
145 238936 : if (!res)
146 117398 : res = stack.get_lang_prelude (seg.name);
147 :
148 144058 : if (N == Namespace::Types && !res)
149 : {
150 792 : if (seg.is_crate_path_seg ())
151 : {
152 280 : insert_segment_resolution (Usage (seg.node_id),
153 280 : Definition (stack.root.id), N);
154 : // TODO: does NonShadowable matter?
155 280 : return Rib::Definition::NonShadowable (stack.root.id);
156 : }
157 512 : 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 510 : else if (seg.is_super_path_seg ())
166 : {
167 : auto &closest_module
168 292 : = stack.find_closest_module (starting_point.get ());
169 292 : 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 292 : NodeId id
177 292 : = stack.find_closest_module (closest_module.parent.value ()).id;
178 292 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
179 : N);
180 : // TODO: does NonShadowable matter?
181 292 : return Rib::Definition::NonShadowable (id);
182 : }
183 : }
184 :
185 : // FIXME: Is the NS to insert_segment_resolution valid?
186 238362 : if (res && !res->is_ambiguous ())
187 236973 : insert_segment_resolution (Usage (seg.node_id),
188 236973 : Definition (res->get_node_id ()), N);
189 238362 : return res;
190 238936 : }
191 :
192 88595 : auto iterator = segments.begin ();
193 88595 : if (can_descend)
194 : {
195 88595 : if (auto res = stack.find_starting_point (segments, starting_point,
196 : insert_segment_resolution,
197 : collect_errors))
198 88593 : iterator = *res;
199 : else
200 2 : return tl::nullopt;
201 :
202 : // if find_starting_point used all segments, return early
203 88593 : 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 88587 : auto node
217 88587 : = resolve_segments (types, starting_point.get (), segments, iterator,
218 : insert_segment_resolution, collect_errors);
219 :
220 88587 : if (!node)
221 24163 : return tl::nullopt;
222 :
223 : // This node now represents the Node which *should* contain the definition
224 : // used by the last segment.
225 64424 : auto &final_node = node.value ();
226 :
227 : // leave resolution within impl blocks to type checker
228 64424 : if (final_node.rib (N).kind == Rib::Kind::TraitOrImpl)
229 0 : return tl::nullopt;
230 :
231 64424 : auto &seg = segments.back ();
232 64424 : std::string seg_name = seg.name;
233 :
234 64424 : 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 64424 : if (!res)
239 37531 : res = stack.get_lang_prelude (seg_name);
240 :
241 64424 : if (res && !res->is_ambiguous ())
242 26895 : insert_segment_resolution (Usage (seg.node_id),
243 26895 : Definition (res->get_node_id ()), N);
244 :
245 64424 : return res;
246 64424 : }
247 :
248 : template <Namespace N>
249 : tl::optional<typename ForeverStack<N>::Node &>
250 88587 : 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 88587 : auto *current_node = &starting_point;
258 184167 : for (; !is_last (iterator, segments); iterator++)
259 : {
260 95580 : auto &seg = *iterator;
261 :
262 191160 : std::string str = seg.name;
263 :
264 : // check that we don't encounter *any* leading keywords afterwards
265 95580 : if (check_leading_kw_at_start (collect_errors, seg,
266 95580 : seg.is_crate_path_seg ()
267 95580 : || seg.is_super_path_seg ()
268 95573 : || seg.is_lower_self_seg ()))
269 10 : return tl::nullopt;
270 :
271 95570 : 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 95570 : bool searched_prelude = false;
292 97936 : while (true)
293 : {
294 223361 : if (is_start (iterator, segments)
295 355608 : && current_node->rib (N).kind == Rib::Kind::TraitOrImpl)
296 : {
297 : // we can't reference associated types/functions like this
298 20409 : current_node = ¤t_node->parent.value ();
299 33599 : continue;
300 : }
301 :
302 : // may set the value of child
303 3493076 : for (auto &kv : current_node->children)
304 : {
305 3373051 : auto &link = kv.first;
306 :
307 6746102 : if (link.path.map_or (
308 946291 : [&str] (Identifier path) {
309 946291 : auto &path_str = path.as_string ();
310 946291 : return str == path_str;
311 : },
312 3373051 : false))
313 : {
314 245061 : child = kv.second;
315 : break;
316 : }
317 : }
318 :
319 182543 : if (child.has_value ())
320 : {
321 : break;
322 : }
323 :
324 120025 : auto rib_lookup = current_node->rib (N).get (seg.name);
325 120025 : if (rib_lookup && !rib_lookup->is_ambiguous ())
326 : {
327 18458 : if (Analysis::Mappings::get ()
328 18458 : .lookup_glob_container (rib_lookup->get_node_id ())
329 18458 : .has_value ())
330 : {
331 8899 : NodeId leaf_module
332 8899 : = stack.find_leaf_definition (rib_lookup->get_node_id ())
333 8899 : .value_or (Definition (rib_lookup->get_node_id ()))
334 : .id;
335 :
336 8899 : if (auto new_child = stack.dfs_node (stack.root, leaf_module))
337 : {
338 8899 : child = new_child.value ();
339 8899 : 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 9559 : insert_segment_resolution (Usage (seg.node_id),
353 9559 : Definition (
354 : rib_lookup->get_node_id ()),
355 : N);
356 :
357 9559 : return tl::nullopt;
358 : }
359 : }
360 :
361 13190 : if (!searched_prelude
362 177317 : && should_search_prelude<N> (current_node, iterator, segments))
363 : {
364 13190 : searched_prelude = true;
365 13190 : current_node = &stack.lang_prelude;
366 : continue;
367 : }
368 :
369 88377 : if (!is_start (iterator, segments)
370 85849 : || current_node->rib (N).kind == Rib::Kind::Module
371 174226 : || current_node->is_prelude ())
372 : {
373 14594 : return tl::nullopt;
374 : }
375 :
376 73783 : 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 71417 : current_node = &child->get ();
382 71417 : insert_segment_resolution (Usage (seg.node_id),
383 71417 : Definition (current_node->id), N);
384 : }
385 :
386 64424 : return *current_node;
387 : }
388 :
389 : template <>
390 : inline tl::optional<Rib::Definition>
391 26179 : 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 26179 : if (is_lower_self)
397 153 : return Rib::Definition::NonShadowable (final_node.id);
398 : else
399 26026 : return final_node.rib_types.get (seg_name);
400 : }
401 :
402 : template <Namespace N>
403 : tl::optional<Rib::Definition>
404 38245 : 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 38245 : return final_node.rib (N).get (seg_name);
409 : }
410 :
411 : } // namespace Resolver2_0
412 : } // namespace Rust
|
