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 78402 : 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 78402 : 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 78383 : if (is_start (iterator, segments)
45 78383 : && 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 303209 : 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 303209 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point
59 : = stack.cursor ();
60 :
61 303209 : return NameResolutionContext::resolve_path (stack, path, mode,
62 : insert_segment_resolution,
63 303209 : 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 329166 : 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 329166 : bool can_descend = true;
95 :
96 329166 : rust_debug ("resolving %s", path.as_string ().c_str ());
97 :
98 329166 : if (auto lang_item = path.get_lang_prefix ())
99 : {
100 : NodeId seg_id
101 1208 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
102 :
103 1208 : insert_segment_resolution (Usage (lang_item->second), Definition (seg_id),
104 : N);
105 :
106 1208 : if (path.get_segments ().empty ())
107 1208 : 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 327958 : 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 327958 : if (path.get_segments ().empty ())
133 2 : return Rib::Definition::NonShadowable (starting_point.get ().id);
134 :
135 327956 : auto &segments = path.get_segments ();
136 :
137 : // if there's only one segment, we just use `get`
138 655912 : if (can_descend && segments.size () == 1)
139 : {
140 247161 : auto &seg = segments.front ();
141 :
142 247161 : tl::optional<Rib::Definition> res
143 988644 : = stack.get (starting_point.get (), seg.name);
144 :
145 247161 : if (!res)
146 109358 : res = stack.get_lang_prelude (seg.name);
147 :
148 127600 : if (N == Namespace::Types && !res)
149 : {
150 708 : if (seg.is_crate_path_seg ())
151 : {
152 266 : insert_segment_resolution (Usage (seg.node_id),
153 266 : Definition (stack.root.id), N);
154 : // TODO: does NonShadowable matter?
155 266 : return Rib::Definition::NonShadowable (stack.root.id);
156 : }
157 442 : else if (seg.is_lower_self_seg ())
158 : {
159 5 : NodeId id = stack.find_closest_module (starting_point.get ()).id;
160 5 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
161 : N);
162 : // TODO: does NonShadowable matter?
163 5 : 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 246617 : if (res && !res->is_ambiguous ())
187 245472 : insert_segment_resolution (Usage (seg.node_id),
188 245472 : Definition (res->get_node_id ()), N);
189 246617 : return res;
190 247161 : }
191 :
192 80795 : auto iterator = segments.begin ();
193 80795 : if (can_descend)
194 : {
195 80795 : if (auto res = stack.find_starting_point (segments, starting_point,
196 : insert_segment_resolution,
197 : collect_errors))
198 80793 : iterator = *res;
199 : else
200 2 : return tl::nullopt;
201 :
202 : // if find_starting_point used all segments, return early
203 80793 : 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 80787 : auto node
217 80787 : = resolve_segments (types, starting_point.get (), segments, iterator,
218 : insert_segment_resolution, collect_errors);
219 :
220 80787 : if (!node)
221 22564 : return tl::nullopt;
222 :
223 : // This node now represents the Node which *should* contain the definition
224 : // used by the last segment.
225 58223 : auto &final_node = node.value ();
226 :
227 : // leave resolution within impl blocks to type checker
228 58223 : if (final_node.rib (N).kind == Rib::Kind::TraitOrImpl)
229 0 : return tl::nullopt;
230 :
231 58223 : auto &seg = segments.back ();
232 58223 : std::string seg_name = seg.name;
233 :
234 58223 : 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 58223 : if (!res)
239 35045 : res = stack.get_lang_prelude (seg_name);
240 :
241 58223 : if (res && !res->is_ambiguous ())
242 23180 : insert_segment_resolution (Usage (seg.node_id),
243 23180 : Definition (res->get_node_id ()), N);
244 :
245 58223 : return res;
246 58223 : }
247 :
248 : template <Namespace N>
249 : tl::optional<typename ForeverStack<N>::Node &>
250 80787 : 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 80787 : auto *current_node = &starting_point;
258 167195 : for (; !is_last (iterator, segments); iterator++)
259 : {
260 86408 : auto &seg = *iterator;
261 :
262 172816 : std::string str = seg.name;
263 :
264 : // check that we don't encounter *any* leading keywords afterwards
265 86408 : if (check_leading_kw_at_start (collect_errors, seg,
266 86408 : seg.is_crate_path_seg ()
267 86408 : || seg.is_super_path_seg ()
268 86401 : || seg.is_lower_self_seg ()))
269 10 : return tl::nullopt;
270 :
271 86398 : 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 86398 : bool searched_prelude = false;
292 86270 : while (true)
293 : {
294 198306 : if (is_start (iterator, segments)
295 315588 : && current_node->rib (N).kind == Rib::Kind::TraitOrImpl)
296 : {
297 : // we can't reference associated types/functions like this
298 17728 : current_node = ¤t_node->parent.value ();
299 30464 : continue;
300 : }
301 :
302 : // may set the value of child
303 3134703 : for (auto &kv : current_node->children)
304 : {
305 3029620 : auto &link = kv.first;
306 :
307 6059240 : if (link.path.map_or (
308 1004144 : [&str] (Identifier path) {
309 1004144 : auto &path_str = path.as_string ();
310 1004144 : return str == path_str;
311 : },
312 3029620 : false))
313 : {
314 220617 : child = kv.second;
315 : break;
316 : }
317 : }
318 :
319 162850 : if (child.has_value ())
320 : {
321 : break;
322 : }
323 :
324 105083 : auto rib_lookup = current_node->rib (N).get (seg.name);
325 105083 : if (rib_lookup && !rib_lookup->is_ambiguous ())
326 : {
327 14461 : if (Analysis::Mappings::get ()
328 14461 : .lookup_glob_container (rib_lookup->get_node_id ())
329 14461 : .has_value ())
330 : {
331 6077 : NodeId leaf_module
332 6077 : = stack.find_leaf_definition (rib_lookup->get_node_id ())
333 6077 : .value_or (Definition (rib_lookup->get_node_id ()))
334 : .id;
335 :
336 6077 : if (auto new_child = stack.dfs_node (stack.root, leaf_module))
337 : {
338 6077 : child = new_child.value ();
339 6077 : 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 8384 : insert_segment_resolution (Usage (seg.node_id),
353 8384 : Definition (
354 : rib_lookup->get_node_id ()),
355 : N);
356 :
357 8384 : return tl::nullopt;
358 : }
359 : }
360 :
361 12736 : if (!searched_prelude
362 156288 : && should_search_prelude<N> (current_node, iterator, segments))
363 : {
364 12736 : searched_prelude = true;
365 12736 : current_node = &stack.lang_prelude;
366 : continue;
367 : }
368 :
369 77886 : if (!is_start (iterator, segments)
370 75934 : || current_node->rib (N).kind == Rib::Kind::Module
371 153820 : || current_node->is_prelude ())
372 : {
373 14170 : return tl::nullopt;
374 : }
375 :
376 63716 : 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 63844 : current_node = &child->get ();
382 63844 : insert_segment_resolution (Usage (seg.node_id),
383 63844 : Definition (current_node->id), N);
384 : }
385 :
386 58223 : return *current_node;
387 : }
388 :
389 : template <>
390 : inline tl::optional<Rib::Definition>
391 23691 : 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 23691 : if (is_lower_self)
397 95 : return Rib::Definition::NonShadowable (final_node.id);
398 : else
399 23596 : return final_node.rib_types.get (seg_name);
400 : }
401 :
402 : template <Namespace N>
403 : tl::optional<Rib::Definition>
404 34532 : 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 34532 : return final_node.rib (N).get (seg_name);
409 : }
410 :
411 : } // namespace Resolver2_0
412 : } // namespace Rust
|
