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