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 26167 : 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 26167 : 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 26150 : if (is_start (iterator, segments)
45 26150 : && current_node->rib.kind == Rib::Kind::Module)
46 : return true;
47 :
48 : return false;
49 : }
50 :
51 : template <Namespace N>
52 : tl::optional<Rib::Definition>
53 87063 : 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 87063 : std::reference_wrapper<typename ForeverStack<N>::Node> starting_point
59 : = stack.cursor ();
60 :
61 87063 : return NameResolutionContext::resolve_path (stack, path, mode,
62 : insert_segment_resolution,
63 87063 : collect_errors, starting_point);
64 : }
65 :
66 : template <Namespace N>
67 : tl::optional<Rib::Definition>
68 0 : 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 0 : 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 0 : if (!starting_point)
79 0 : return tl::nullopt;
80 :
81 0 : return NameResolutionContext::resolve_path (stack, path, mode,
82 : insert_segment_resolution,
83 0 : collect_errors, *starting_point);
84 : }
85 :
86 : template <Namespace N>
87 : tl::optional<Rib::Definition>
88 87063 : 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 87063 : bool can_descend = true;
95 :
96 87063 : rust_debug ("resolving %s", path.as_string ().c_str ());
97 :
98 87063 : if (auto lang_item = path.get_lang_prefix ())
99 : {
100 : NodeId seg_id
101 392 : = Analysis::Mappings::get ().get_lang_item_node (lang_item->first);
102 :
103 392 : insert_segment_resolution (Usage (lang_item->second), Definition (seg_id),
104 : N);
105 :
106 392 : if (path.get_segments ().empty ())
107 392 : 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 86671 : 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 0 : case ResolutionMode::FromExtern:
125 0 : starting_point = stack.extern_prelude;
126 0 : break;
127 0 : default:
128 0 : rust_unreachable ();
129 : }
130 : }
131 :
132 86671 : if (path.get_segments ().empty ())
133 2 : return Rib::Definition::NonShadowable (starting_point.get ().id);
134 :
135 86669 : auto &segments = path.get_segments ();
136 :
137 : // if there's only one segment, we just use `get`
138 173338 : if (can_descend && segments.size () == 1)
139 : {
140 72528 : auto &seg = segments.front ();
141 :
142 72528 : tl::optional<Rib::Definition> res
143 290112 : = stack.get (starting_point.get (), seg.name);
144 :
145 72528 : if (!res)
146 52700 : res = stack.get_lang_prelude (seg.name);
147 :
148 55311 : if (N == Namespace::Types && !res)
149 : {
150 193 : if (seg.is_crate_path_seg ())
151 : {
152 53 : insert_segment_resolution (Usage (seg.node_id),
153 53 : Definition (stack.root.id), N);
154 : // TODO: does NonShadowable matter?
155 53 : return Rib::Definition::NonShadowable (stack.root.id);
156 : }
157 140 : 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 135 : else if (seg.is_super_path_seg ())
166 : {
167 : auto &closest_module
168 1 : = stack.find_closest_module (starting_point.get ());
169 1 : 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 1 : NodeId id
177 1 : = stack.find_closest_module (closest_module.parent.value ()).id;
178 1 : insert_segment_resolution (Usage (seg.node_id), Definition (id),
179 : N);
180 : // TODO: does NonShadowable matter?
181 1 : return Rib::Definition::NonShadowable (id);
182 : }
183 : }
184 :
185 : // FIXME: Is the NS to insert_segment_resolution valid?
186 72469 : if (res && !res->is_ambiguous ())
187 71869 : insert_segment_resolution (Usage (seg.node_id),
188 71869 : Definition (res->get_node_id ()), N);
189 72469 : return res;
190 72528 : }
191 :
192 14141 : auto iterator = segments.begin ();
193 14141 : if (can_descend)
194 : {
195 14141 : if (auto res = stack.find_starting_point (segments, starting_point,
196 : insert_segment_resolution,
197 : collect_errors))
198 14139 : iterator = *res;
199 : else
200 2 : return tl::nullopt;
201 : }
202 :
203 : // We do the first part of path resolution exclusively in the types NS - this
204 : // gives us a node in which to resolve the last segment of the path.
205 :
206 : // We take our starting point and then get the equivalent Node from the Types
207 : // NS - since it existed in whatever namespace we are right now, we assume it
208 : // exists in the types NS.
209 : auto types_starting_point
210 14139 : = types.dfs_node (types.root, starting_point.get ().id);
211 :
212 : // TODO: Add a method for converting a node between namespaces? Make all of
213 : // the starting point stuff return a NodeId rather than a Node&? And take a
214 : // NodeId as a starting point rather than a Node?
215 :
216 : auto node
217 14139 : = resolve_segments (types, types_starting_point.value (), segments,
218 : iterator, insert_segment_resolution, collect_errors);
219 :
220 14139 : if (!node)
221 1873 : return tl::nullopt;
222 :
223 : // This node now represents the Node which *should* contain the definition
224 : // used by the last segment. We now get the equivalent Node from this
225 : // namespace after finding it in the types NS.
226 12266 : auto final_node_id = node.value ().id;
227 12266 : auto final_node = stack.dfs_node (stack.root, final_node_id).value ();
228 :
229 : // leave resolution within impl blocks to type checker
230 12266 : if (final_node.rib.kind == Rib::Kind::TraitOrImpl)
231 0 : return tl::nullopt;
232 :
233 12266 : auto &seg = segments.back ();
234 15071 : std::string seg_name = seg.name;
235 :
236 12266 : tl::optional<Rib::Definition> res
237 : = resolve_final_segment (stack, final_node, seg_name,
238 12266 : seg.is_lower_self_seg ());
239 : // Ok we didn't find it in the rib, Lets try the prelude...
240 12266 : if (!res)
241 4237 : res = stack.get_lang_prelude (seg_name);
242 :
243 12266 : if (res && !res->is_ambiguous ())
244 8027 : insert_segment_resolution (Usage (seg.node_id),
245 8027 : Definition (res->get_node_id ()), N);
246 :
247 12266 : return res;
248 12266 : }
249 :
250 : template <Namespace N>
251 : tl::optional<typename ForeverStack<N>::Node &>
252 14139 : NameResolutionContext::resolve_segments (
253 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &starting_point,
254 : const std::vector<ResolutionPath::Segment> &segments,
255 : typename ForeverStack<N>::SegIterator iterator,
256 : std::function<void (Usage, Definition, Namespace)> insert_segment_resolution,
257 : std::vector<Error> &collect_errors)
258 : {
259 14139 : auto *current_node = &starting_point;
260 31653 : for (; !is_last (iterator, segments); iterator++)
261 : {
262 17514 : auto &seg = *iterator;
263 :
264 35028 : std::string str = seg.name;
265 :
266 : // check that we don't encounter *any* leading keywords afterwards
267 17514 : if (check_leading_kw_at_start (collect_errors, seg,
268 17514 : seg.is_crate_path_seg ()
269 17514 : || seg.is_super_path_seg ()
270 35021 : || seg.is_lower_self_seg ()))
271 10 : return tl::nullopt;
272 :
273 17504 : tl::optional<std::reference_wrapper<typename ForeverStack<N>::Node>> child
274 : = tl::nullopt;
275 :
276 : /*
277 : * On every iteration this loop either
278 : *
279 : * 1. terminates
280 : *
281 : * 2. decreases the depth of the node pointed to by current_node until
282 : * current_node reaches the root
283 : *
284 : * 3. If the root node is reached, and we were not able to resolve the
285 : * segment, we search the prelude rib for the segment, by setting
286 : * current_node to point to the prelude, and toggling the
287 : * searched_prelude boolean to true. If current_node is the prelude
288 : * rib, and searched_prelude is true, we will exit.
289 : *
290 : * This ensures termination.
291 : *
292 : */
293 17504 : bool searched_prelude = false;
294 30313 : while (true)
295 : {
296 55916 : if (is_start (iterator, segments)
297 49791 : && current_node->rib.kind == Rib::Kind::TraitOrImpl)
298 : {
299 : // we can't reference associated types/functions like this
300 6125 : current_node = ¤t_node->parent.value ();
301 6144 : continue;
302 : }
303 :
304 : // may set the value of child
305 157371 : for (auto &kv : current_node->children)
306 : {
307 127058 : auto &link = kv.first;
308 :
309 254116 : if (link.path.map_or (
310 60822 : [&str] (Identifier path) {
311 60822 : auto &path_str = path.as_string ();
312 60822 : return str == path_str;
313 : },
314 127058 : false))
315 : {
316 57019 : child = kv.second;
317 : break;
318 : }
319 : }
320 :
321 43666 : if (child.has_value ())
322 : {
323 : break;
324 : }
325 :
326 30313 : auto rib_lookup = current_node->rib.get (seg.name);
327 30313 : if (rib_lookup && !rib_lookup->is_ambiguous ())
328 : {
329 4135 : if (Analysis::Mappings::get ()
330 4135 : .lookup_glob_container (rib_lookup->get_node_id ())
331 4135 : .has_value ())
332 : {
333 2288 : NodeId leaf_module
334 2288 : = stack.find_leaf_definition (rib_lookup->get_node_id ())
335 2288 : .value_or (Definition (rib_lookup->get_node_id ()))
336 : .id;
337 :
338 2288 : if (auto new_child = stack.dfs_node (stack.root, leaf_module))
339 : {
340 2288 : child = new_child.value ();
341 2288 : break;
342 : }
343 : else
344 : {
345 0 : return tl::nullopt;
346 : }
347 : }
348 : else
349 : {
350 : // FIXME: Resolve segments always resolves in the Types NS
351 : // correct? If so, we should remove the template parameter for
352 : // this function - and use NS::Types directly here instead of
353 : // N
354 1847 : insert_segment_resolution (Usage (seg.node_id),
355 1847 : Definition (
356 : rib_lookup->get_node_id ()),
357 : N);
358 :
359 1847 : return tl::nullopt;
360 : }
361 : }
362 :
363 19 : if (!searched_prelude
364 52326 : && should_search_prelude<N> (current_node, iterator, segments))
365 : {
366 19 : searched_prelude = true;
367 19 : current_node = &stack.lang_prelude;
368 : continue;
369 : }
370 :
371 26159 : if (!is_start (iterator, segments)
372 26154 : || current_node->rib.kind == Rib::Kind::Module
373 52313 : || current_node->is_prelude ())
374 : {
375 16 : return tl::nullopt;
376 : }
377 :
378 26143 : current_node = ¤t_node->parent.value ();
379 : }
380 :
381 : // if child didn't point to a value
382 : // the while loop above would have returned or kept looping
383 15641 : current_node = &child->get ();
384 15641 : insert_segment_resolution (Usage (seg.node_id),
385 15641 : Definition (current_node->id), N);
386 : }
387 :
388 12266 : return *current_node;
389 : }
390 :
391 : template <>
392 : inline tl::optional<Rib::Definition>
393 2805 : NameResolutionContext::resolve_final_segment (
394 : ForeverStack<Namespace::Types> &stack,
395 : typename ForeverStack<Namespace::Types>::Node &final_node,
396 : std::string &seg_name, bool is_lower_self)
397 : {
398 2805 : if (is_lower_self)
399 54 : return Rib::Definition::NonShadowable (final_node.id);
400 : else
401 2751 : return final_node.rib.get (seg_name);
402 : }
403 :
404 : template <Namespace N>
405 : tl::optional<Rib::Definition>
406 9461 : NameResolutionContext::resolve_final_segment (
407 : ForeverStack<N> &stack, typename ForeverStack<N>::Node &final_node,
408 : std::string &seg_name, bool is_lower_self)
409 : {
410 9461 : return final_node.rib.get (seg_name);
411 : }
412 :
413 : } // namespace Resolver2_0
414 : } // namespace Rust
|
