Branch data Line data Source code
1 : : // Copyright (C) 2020-2024 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 "expected.h"
20 : : #include "rust-ast.h"
21 : : #include "rust-diagnostics.h"
22 : : #include "rust-forever-stack.h"
23 : : #include "rust-rib.h"
24 : : #include "optional.h"
25 : :
26 : : namespace Rust {
27 : : namespace Resolver2_0 {
28 : :
29 : : template <Namespace N>
30 : : bool
31 : 16629 : ForeverStack<N>::Node::is_root () const
32 : : {
33 : 14890 : return !parent.has_value ();
34 : : }
35 : :
36 : : template <Namespace N>
37 : : bool
38 : 14476 : ForeverStack<N>::Node::is_leaf () const
39 : : {
40 : 14476 : return children.empty ();
41 : : }
42 : :
43 : : template <Namespace N>
44 : : void
45 : : ForeverStack<N>::Node::insert_child (Link link, Node child)
46 : : {
47 : : auto res = children.insert ({link, child});
48 : :
49 : : // Do we want to error if the child already exists? Probably not, right?
50 : : // That's kinda the point, isn't it. So this method always succeeds, right?
51 : : }
52 : :
53 : : template <Namespace N>
54 : : void
55 : 1629 : ForeverStack<N>::push (Rib rib, NodeId id, tl::optional<Identifier> path)
56 : : {
57 : 3612 : push_inner (rib, Link (id, path));
58 : 1629 : }
59 : :
60 : : template <Namespace N>
61 : : void
62 : 1629 : ForeverStack<N>::push_inner (Rib rib, Link link)
63 : : {
64 : : // If the link does not exist, we create it and emplace a new `Node` with the
65 : : // current node as its parent. `unordered_map::emplace` returns a pair with
66 : : // the iterator and a boolean. If the value already exists, the iterator
67 : : // points to it. Otherwise, it points to the newly emplaced value, so we can
68 : : // just update our cursor().
69 : 3258 : auto emplace = cursor ().children.emplace (
70 : 1629 : std::make_pair (link, Node (rib, link.id, cursor ())));
71 : :
72 : 1629 : auto it = emplace.first;
73 : 1629 : auto existed = !emplace.second;
74 : :
75 : 2103 : rust_debug ("inserting link: Link(%d [%s]): existed? %s", link.id,
76 : : link.path.has_value () ? link.path.value ().as_string ().c_str ()
77 : : : "<anon>",
78 : : existed ? "yes" : "no");
79 : :
80 : : // We update the cursor
81 : 1629 : update_cursor (it->second);
82 : 1629 : }
83 : :
84 : : template <Namespace N>
85 : : void
86 : 1629 : ForeverStack<N>::pop ()
87 : : {
88 : 1629 : rust_assert (!cursor ().is_root ());
89 : :
90 : 1629 : rust_debug ("popping link");
91 : :
92 : 1837 : for (const auto &kv : cursor ().rib.get_values ())
93 : 208 : rust_debug ("current_rib: k: %s, v: %s", kv.first.c_str (),
94 : : kv.second.to_string ().c_str ());
95 : :
96 : 1629 : if (cursor ().parent.has_value ())
97 : 3567 : for (const auto &kv : cursor ().parent.value ().rib.get_values ())
98 : 1938 : rust_debug ("new cursor: k: %s, v: %s", kv.first.c_str (),
99 : : kv.second.to_string ().c_str ());
100 : :
101 : 1629 : update_cursor (cursor ().parent.value ());
102 : 1629 : }
103 : :
104 : : static tl::expected<NodeId, DuplicateNameError>
105 : 701 : insert_inner (Rib &rib, std::string name, Rib::Definition definition)
106 : : {
107 : 701 : return rib.insert (name, definition);
108 : : }
109 : :
110 : : template <Namespace N>
111 : : tl::expected<NodeId, DuplicateNameError>
112 : 669 : ForeverStack<N>::insert (Identifier name, NodeId node)
113 : : {
114 : 669 : auto &innermost_rib = peek ();
115 : :
116 : : // So what do we do here - if the Rib has already been pushed in an earlier
117 : : // pass, we might end up in a situation where it is okay to re-add new names.
118 : : // Do we just ignore that here? Do we keep track of if the Rib is new or not?
119 : : // should our cursor have info on the current node like "is it newly pushed"?
120 : 1338 : return insert_inner (innermost_rib, name.as_string (),
121 : 669 : Rib::Definition::NonShadowable (node));
122 : : }
123 : :
124 : : template <Namespace N>
125 : : tl::expected<NodeId, DuplicateNameError>
126 : 6 : ForeverStack<N>::insert_shadowable (Identifier name, NodeId node)
127 : : {
128 : 6 : auto &innermost_rib = peek ();
129 : :
130 : 12 : return insert_inner (innermost_rib, name.as_string (),
131 : 6 : Rib::Definition::Shadowable (node));
132 : : }
133 : :
134 : : template <Namespace N>
135 : : tl::expected<NodeId, DuplicateNameError>
136 : 4 : ForeverStack<N>::insert_at_root (Identifier name, NodeId node)
137 : : {
138 : 4 : auto &root_rib = root.rib;
139 : :
140 : : // inserting in the root of the crate is never a shadowing operation, even for
141 : : // macros
142 : 8 : return insert_inner (root_rib, name.as_string (),
143 : 4 : Rib::Definition::NonShadowable (node));
144 : : }
145 : :
146 : : // Specialization for Macros and Labels - where we are allowed to shadow
147 : : // existing definitions
148 : : template <>
149 : : inline tl::expected<NodeId, DuplicateNameError>
150 : 22 : ForeverStack<Namespace::Macros>::insert (Identifier name, NodeId node)
151 : : {
152 : 44 : return insert_inner (peek (), name.as_string (),
153 : 44 : Rib::Definition::Shadowable (node));
154 : : }
155 : :
156 : : template <>
157 : : inline tl::expected<NodeId, DuplicateNameError>
158 : 0 : ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node)
159 : : {
160 : 0 : return insert_inner (peek (), name.as_string (),
161 : 0 : Rib::Definition::Shadowable (node));
162 : : }
163 : :
164 : : template <Namespace N>
165 : : Rib &
166 : 697 : ForeverStack<N>::peek ()
167 : : {
168 : 697 : return cursor ().rib;
169 : : }
170 : :
171 : : template <Namespace N>
172 : : const Rib &
173 : : ForeverStack<N>::peek () const
174 : : {
175 : : return cursor ().rib;
176 : : }
177 : :
178 : : template <Namespace N>
179 : : void
180 : 163 : ForeverStack<N>::reverse_iter (std::function<KeepGoing (Node &)> lambda)
181 : : {
182 : 326 : return reverse_iter (cursor (), lambda);
183 : : }
184 : :
185 : : template <Namespace N>
186 : : void
187 : 309 : ForeverStack<N>::reverse_iter (Node &start,
188 : : std::function<KeepGoing (Node &)> lambda)
189 : : {
190 : 309 : auto *tmp = &start;
191 : :
192 : 273 : while (true)
193 : : {
194 : 582 : auto keep_going = lambda (*tmp);
195 : 582 : if (keep_going == KeepGoing::No)
196 : : return;
197 : :
198 : 326 : if (tmp->is_root ())
199 : : return;
200 : :
201 : 273 : tmp = &tmp->parent.value ();
202 : : }
203 : : }
204 : :
205 : : template <Namespace N>
206 : : typename ForeverStack<N>::Node &
207 : 9067 : ForeverStack<N>::cursor ()
208 : : {
209 : 9067 : return cursor_reference;
210 : : }
211 : :
212 : : template <Namespace N>
213 : : const typename ForeverStack<N>::Node &
214 : : ForeverStack<N>::cursor () const
215 : : {
216 : : return cursor_reference;
217 : : }
218 : :
219 : : template <Namespace N>
220 : : void
221 : 3258 : ForeverStack<N>::update_cursor (Node &new_cursor)
222 : : {
223 : 3258 : cursor_reference = new_cursor;
224 : : }
225 : :
226 : : template <Namespace N>
227 : : tl::optional<Rib::Definition>
228 : 146 : ForeverStack<N>::get (const Identifier &name)
229 : : {
230 : 146 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
231 : :
232 : : // TODO: Can we improve the API? have `reverse_iter` return an optional?
233 : 511 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
234 : 365 : auto candidate = current.rib.get (name.as_string ());
235 : :
236 : 365 : return candidate.map_or (
237 : 365 : [&resolved_definition] (Rib::Definition found) {
238 : : // for most namespaces, we do not need to care about various ribs - they
239 : : // are available from all contexts if defined in the current scope, or
240 : : // an outermore one. so if we do have a candidate, we can return it
241 : : // directly and stop iterating
242 : 110 : resolved_definition = found;
243 : :
244 : : return KeepGoing::No;
245 : : },
246 : : // if there was no candidate, we keep iterating
247 : 365 : KeepGoing::Yes);
248 : 365 : });
249 : :
250 : 146 : return resolved_definition;
251 : : }
252 : :
253 : : template <>
254 : 17 : tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get (
255 : : const Identifier &name)
256 : : {
257 : 17 : tl::optional<Rib::Definition> resolved_definition = tl::nullopt;
258 : :
259 : 17 : reverse_iter ([&resolved_definition, &name] (Node ¤t) {
260 : : // looking up for labels cannot go through function ribs
261 : : // TODO: What other ribs?
262 : 17 : if (current.rib.kind == Rib::Kind::Function)
263 : : return KeepGoing::No;
264 : :
265 : 17 : auto candidate = current.rib.get (name.as_string ());
266 : :
267 : : // FIXME: Factor this in a function with the generic `get`
268 : 34 : return candidate.map_or (
269 : 17 : [&resolved_definition] (Rib::Definition found) {
270 : 0 : resolved_definition = found;
271 : :
272 : 0 : return KeepGoing::No;
273 : : },
274 : 17 : KeepGoing::Yes);
275 : 17 : });
276 : :
277 : 17 : return resolved_definition;
278 : : }
279 : :
280 : : /* Check if an iterator points to the last element */
281 : : template <typename I, typename C>
282 : : static bool
283 : 193 : is_last (const I &iterator, const C &collection)
284 : : {
285 : 193 : return iterator + 1 == collection.end ();
286 : : }
287 : :
288 : : /* Check if an iterator points to the start of the collection */
289 : : template <typename I, typename C>
290 : : static bool
291 : 68 : is_start (const I &iterator, const C &collection)
292 : : {
293 : 68 : return iterator == collection.begin ();
294 : : }
295 : :
296 : : template <Namespace N>
297 : : typename ForeverStack<N>::Node &
298 : 70 : ForeverStack<N>::find_closest_module (Node &starting_point)
299 : : {
300 : 70 : auto *closest_module = &starting_point;
301 : :
302 : 160 : reverse_iter (starting_point, [&closest_module] (Node ¤t) {
303 : 90 : if (current.rib.kind == Rib::Kind::Module || current.is_root ())
304 : : {
305 : 70 : closest_module = ¤t;
306 : 70 : return KeepGoing::No;
307 : : }
308 : :
309 : : return KeepGoing::Yes;
310 : : });
311 : :
312 : 70 : return *closest_module;
313 : : }
314 : :
315 : : /* If a the given condition is met, emit an error about misused leading path
316 : : * segments */
317 : : template <typename S>
318 : : static inline bool
319 : 132 : check_leading_kw_at_start (const S &segment, bool condition)
320 : : {
321 : 132 : if (condition)
322 : 2 : rust_error_at (
323 : : segment.get_locus (), ErrorCode::E0433,
324 : : "leading path segment %qs can only be used at the beginning of a path",
325 : 4 : segment.as_string ().c_str ());
326 : :
327 : 132 : return condition;
328 : : }
329 : :
330 : : // we first need to handle the "starting" segments - `super`, `self` or
331 : : // `crate`. we don't need to do anything for `self` and can just skip it. for
332 : : // `crate`, we need to go back to the root of the current stack. for each
333 : : // `super` segment, we go back to the cursor's parent until we reach the
334 : : // correct one or the root.
335 : : template <Namespace N>
336 : : template <typename S>
337 : : tl::optional<typename std::vector<S>::const_iterator>
338 : 62 : ForeverStack<N>::find_starting_point (const std::vector<S> &segments,
339 : : Node &starting_point)
340 : : {
341 : 62 : auto iterator = segments.begin ();
342 : :
343 : : // If we need to do path segment resolution, then we start
344 : : // at the closest module. In order to resolve something like `foo::bar!()`, we
345 : : // need to get back to the surrounding module, and look for a child module
346 : : // named `foo`.
347 : 62 : if (segments.size () > 1)
348 : 62 : starting_point = find_closest_module (starting_point);
349 : :
350 : 70 : for (; !is_last (iterator, segments); iterator++)
351 : : {
352 : 68 : auto &seg = *iterator;
353 : 68 : auto is_self_or_crate
354 : 68 : = seg.is_crate_path_seg () || seg.is_lower_self_seg ();
355 : :
356 : : // if we're after the first path segment and meet `self` or `crate`, it's
357 : : // an error - we should only be seeing `super` keywords at this point
358 : 68 : if (check_leading_kw_at_start (seg, !is_start (iterator, segments)
359 : 68 : && is_self_or_crate))
360 : 1 : return tl::nullopt;
361 : :
362 : 67 : if (seg.is_crate_path_seg ())
363 : : {
364 : 5 : starting_point = root;
365 : 5 : iterator++;
366 : : break;
367 : : }
368 : 62 : if (seg.is_lower_self_seg ())
369 : : {
370 : : // do nothing and exit
371 : : iterator++;
372 : : break;
373 : : }
374 : 63 : if (seg.is_super_path_seg ())
375 : : {
376 : 9 : if (starting_point.is_root ())
377 : : {
378 : 1 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
379 : : "too many leading %<super%> keywords");
380 : 1 : return tl::nullopt;
381 : : }
382 : :
383 : 8 : starting_point = find_closest_module (starting_point.parent.value ());
384 : : continue;
385 : : }
386 : :
387 : : // now we've gone through the allowed `crate`, `self` or leading `super`
388 : : // segments. we can start resolving each segment itself.
389 : : // if we do see another leading segment, then we can error out.
390 : : break;
391 : : }
392 : :
393 : 60 : return iterator;
394 : : }
395 : :
396 : : template <Namespace N>
397 : : template <typename S>
398 : : tl::optional<typename ForeverStack<N>::Node &>
399 : 60 : ForeverStack<N>::resolve_segments (
400 : : Node &starting_point, const std::vector<S> &segments,
401 : : typename std::vector<S>::const_iterator iterator)
402 : : {
403 : 60 : auto *current_node = &starting_point;
404 : 124 : for (; !is_last (iterator, segments); iterator++)
405 : : {
406 : 64 : auto &seg = *iterator;
407 : 64 : auto str = seg.as_string ();
408 : 64 : rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ());
409 : :
410 : : // check that we don't encounter *any* leading keywords afterwards
411 : 128 : if (check_leading_kw_at_start (seg, seg.is_crate_path_seg ()
412 : 64 : || seg.is_super_path_seg ()
413 : 127 : || seg.is_lower_self_seg ()))
414 : 1 : return tl::nullopt;
415 : :
416 : 63 : tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt;
417 : :
418 : 63 : for (auto &kv : current_node->children)
419 : : {
420 : 63 : auto &link = kv.first;
421 : :
422 : 126 : if (link.path.map_or (
423 : 189 : [&str] (Identifier path) {
424 : 63 : auto &path_str = path.as_string ();
425 : 63 : return str == path_str;
426 : : },
427 : : false))
428 : : {
429 : 63 : child = kv.second;
430 : : break;
431 : : }
432 : : }
433 : :
434 : 63 : if (!child.has_value ())
435 : : {
436 : 0 : rust_error_at (seg.get_locus (), ErrorCode::E0433,
437 : : "failed to resolve path segment %qs", str.c_str ());
438 : 0 : return tl::nullopt;
439 : : }
440 : :
441 : 63 : current_node = &child.value ();
442 : : }
443 : :
444 : 59 : return *current_node;
445 : : }
446 : :
447 : : template <Namespace N>
448 : : template <typename S>
449 : : tl::optional<Rib::Definition>
450 : 145 : ForeverStack<N>::resolve_path (const std::vector<S> &segments)
451 : : {
452 : : // TODO: What to do if segments.empty() ?
453 : :
454 : : // if there's only one segment, we just use `get`
455 : 145 : if (segments.size () == 1)
456 : 83 : return get (segments.back ().as_string ());
457 : :
458 : 62 : auto starting_point = cursor ();
459 : :
460 : 62 : return find_starting_point (segments, starting_point)
461 : 122 : .and_then ([this, &segments, &starting_point] (
462 : : typename std::vector<S>::const_iterator iterator) {
463 : 60 : return resolve_segments (starting_point, segments, iterator);
464 : : })
465 : 121 : .and_then ([&segments] (Node final_node) {
466 : 59 : return final_node.rib.get (segments.back ().as_string ());
467 : 62 : });
468 : 62 : }
469 : :
470 : : template <Namespace N>
471 : : tl::optional<typename ForeverStack<N>::DfsResult>
472 : 139 : ForeverStack<N>::dfs (ForeverStack<N>::Node &starting_point, NodeId to_find)
473 : : {
474 : 139 : auto values = starting_point.rib.get_values ();
475 : :
476 : 290 : for (auto &kv : values)
477 : 378 : for (auto id : kv.second.ids)
478 : 227 : if (id == to_find)
479 : 76 : return {{starting_point, kv.first}};
480 : :
481 : 126 : for (auto &child : starting_point.children)
482 : : {
483 : 63 : auto candidate = dfs (child.second, to_find);
484 : :
485 : 63 : if (candidate.has_value ())
486 : 34 : return candidate;
487 : : }
488 : :
489 : 29 : return tl::nullopt;
490 : 139 : }
491 : :
492 : : template <Namespace N>
493 : : tl::optional<Resolver::CanonicalPath>
494 : 76 : ForeverStack<N>::to_canonical_path (NodeId id)
495 : : {
496 : : // find the id in the current forever stack, starting from the root,
497 : : // performing either a BFS or DFS once the Node containing the ID is found, go
498 : : // back up to the root (parent().parent().parent()...) accumulate link
499 : : // segments reverse them that's your canonical path
500 : :
501 : 152 : return dfs (root, id).map ([this, id] (DfsResult tuple) {
502 : 76 : auto containing_node = tuple.first;
503 : 76 : auto name = tuple.second;
504 : :
505 : 76 : auto segments = std::vector<Resolver::CanonicalPath> ();
506 : :
507 : 186 : reverse_iter (containing_node, [&segments] (Node ¤t) {
508 : 110 : if (current.is_root ())
509 : : return KeepGoing::No;
510 : :
511 : 34 : auto children = current.parent.value ().children;
512 : 34 : const Link *outer_link = nullptr;
513 : :
514 : 34 : for (auto &kv : children)
515 : : {
516 : 34 : auto &link = kv.first;
517 : 34 : auto &child = kv.second;
518 : :
519 : 34 : if (link.id == child.id)
520 : : {
521 : : outer_link = &link;
522 : : break;
523 : : }
524 : : }
525 : :
526 : 34 : rust_assert (outer_link);
527 : :
528 : 44 : outer_link->path.map ([&segments, outer_link] (Identifier path) {
529 : 5 : segments.emplace (segments.begin (),
530 : 5 : Resolver::CanonicalPath::new_seg (outer_link->id,
531 : : path.as_string ()));
532 : : });
533 : :
534 : 34 : return KeepGoing::Yes;
535 : 34 : });
536 : :
537 : 76 : auto path = Resolver::CanonicalPath::create_empty ();
538 : 81 : for (const auto &segment : segments)
539 : 5 : path = path.append (segment);
540 : :
541 : : // Finally, append the name
542 : 76 : path = path.append (Resolver::CanonicalPath::new_seg (id, name));
543 : :
544 : 76 : return path;
545 : 152 : });
546 : : }
547 : :
548 : : template <Namespace N>
549 : : tl::optional<Rib &>
550 : 0 : ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find)
551 : : {
552 : 0 : if (starting_point.id == to_find)
553 : 0 : return starting_point.rib;
554 : :
555 : 0 : for (auto &child : starting_point.children)
556 : : {
557 : 0 : auto candidate = dfs_rib (child.second, to_find);
558 : :
559 : 0 : if (candidate.has_value ())
560 : 0 : return candidate;
561 : : }
562 : :
563 : 0 : return tl::nullopt;
564 : : }
565 : :
566 : : template <Namespace N>
567 : : tl::optional<Rib &>
568 : 0 : ForeverStack<N>::to_rib (NodeId rib_id)
569 : : {
570 : 0 : return dfs_rib (root, rib_id);
571 : : }
572 : :
573 : : template <Namespace N>
574 : : void
575 : 0 : ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib,
576 : : const std::string &next,
577 : : const std::string &next_next)
578 : : {
579 : 0 : if (rib.get_values ().empty ())
580 : : {
581 : 0 : stream << next << "rib: {},\n";
582 : 0 : return;
583 : : }
584 : :
585 : 0 : stream << next << "rib: {\n";
586 : :
587 : 0 : for (const auto &kv : rib.get_values ())
588 : 0 : stream << next_next << kv.first << ": " << kv.second.to_string () << "\n";
589 : :
590 : 0 : stream << next << "},\n";
591 : : }
592 : :
593 : : template <Namespace N>
594 : : void
595 : 0 : ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation,
596 : : const ForeverStack<N>::Node &node)
597 : : {
598 : 0 : auto indent = std::string (indentation, ' ');
599 : 0 : auto next = std::string (indentation + 4, ' ');
600 : 0 : auto next_next = std::string (indentation + 8, ' ');
601 : :
602 : : stream << indent << "Node {\n"
603 : 0 : << next << "is_root: " << (node.is_root () ? "true" : "false") << ",\n"
604 : 0 : << next << "is_leaf: " << (node.is_leaf () ? "true" : "false")
605 : 0 : << ",\n";
606 : :
607 : 0 : stream_rib (stream, node.rib, next, next_next);
608 : :
609 : 0 : stream << indent << "}\n";
610 : :
611 : 0 : for (auto &kv : node.children)
612 : : {
613 : 0 : auto link = kv.first;
614 : 0 : auto child = kv.second;
615 : 0 : stream << indent << "Link (" << link.id << ", "
616 : 0 : << (link.path.has_value () ? link.path.value ().as_string ()
617 : : : "<anon>")
618 : 0 : << "):\n";
619 : :
620 : 0 : stream_node (stream, indentation + 4, child);
621 : :
622 : 0 : stream << '\n';
623 : : }
624 : 0 : }
625 : :
626 : : template <Namespace N>
627 : : std::string
628 : 0 : ForeverStack<N>::as_debug_string ()
629 : : {
630 : 0 : std::stringstream stream;
631 : :
632 : 0 : stream_node (stream, 0, root);
633 : :
634 : 0 : return stream.str ();
635 : 0 : }
636 : :
637 : : // FIXME: Can we add selftests?
638 : :
639 : : } // namespace Resolver2_0
640 : : } // namespace Rust
|
