diff options
Diffstat (limited to 'gcc/rust/resolve/rust-forever-stack.hxx')
| -rw-r--r-- | gcc/rust/resolve/rust-forever-stack.hxx | 314 |
1 files changed, 252 insertions, 62 deletions
diff --git a/gcc/rust/resolve/rust-forever-stack.hxx b/gcc/rust/resolve/rust-forever-stack.hxx index 5a5a7c7..a6e0b30 100644 --- a/gcc/rust/resolve/rust-forever-stack.hxx +++ b/gcc/rust/resolve/rust-forever-stack.hxx @@ -21,6 +21,7 @@ #include "rust-diagnostics.h" #include "rust-forever-stack.h" #include "rust-rib.h" +#include "rust-unwrap-segment.h" #include "optional.h" namespace Rust { @@ -35,6 +36,13 @@ ForeverStack<N>::Node::is_root () const template <Namespace N> bool +ForeverStack<N>::Node::is_prelude () const +{ + return rib.kind == Rib::Kind::Prelude; +} + +template <Namespace N> +bool ForeverStack<N>::Node::is_leaf () const { return children.empty (); @@ -52,15 +60,26 @@ ForeverStack<N>::Node::insert_child (Link link, Node child) template <Namespace N> void -ForeverStack<N>::push (Rib rib, NodeId id, tl::optional<Identifier> path) +ForeverStack<N>::push (Rib::Kind rib_kind, NodeId id, + tl::optional<Identifier> path) { - push_inner (rib, Link (id, path)); + push_inner (rib_kind, Link (id, path)); } template <Namespace N> void ForeverStack<N>::push_inner (Rib rib, Link link) { + if (rib.kind == Rib::Kind::Prelude) + { + // If you push_inner into the prelude from outside the root, you will pop + // back into the root, which could screw up a traversal. + rust_assert (&cursor_reference.get () == &root); + // Prelude doesn't have an access path + rust_assert (!link.path); + update_cursor (this->prelude); + return; + } // If the link does not exist, we create it and emplace a new `Node` with the // current node as its parent. `unordered_map::emplace` returns a pair with // the iterator and a boolean. If the value already exists, the iterator @@ -171,6 +190,14 @@ ForeverStack<Namespace::Labels>::insert (Identifier name, NodeId node) Rib::Definition::Shadowable (node)); } +template <> +inline tl::expected<NodeId, DuplicateNameError> +ForeverStack<Namespace::Types>::insert_variant (Identifier name, NodeId node) +{ + return insert_inner (peek (), name.as_string (), + Rib::Definition::NonShadowable (node, true)); +} + template <Namespace N> Rib & ForeverStack<N>::peek () @@ -273,10 +300,12 @@ ForeverStack<N>::get (const Identifier &name) return candidate.map_or ( [&resolved_definition] (Rib::Definition found) { - // for most namespaces, we do not need to care about various ribs - they - // are available from all contexts if defined in the current scope, or - // an outermore one. so if we do have a candidate, we can return it - // directly and stop iterating + if (found.is_variant ()) + return KeepGoing::Yes; + // for most namespaces, we do not need to care about various ribs - + // they are available from all contexts if defined in the current + // scope, or an outermore one. so if we do have a candidate, we can + // return it directly and stop iterating resolved_definition = found; return KeepGoing::No; @@ -288,6 +317,20 @@ ForeverStack<N>::get (const Identifier &name) return resolved_definition; } +template <Namespace N> +tl::optional<Rib::Definition> +ForeverStack<N>::get_prelude (const Identifier &name) +{ + return prelude.rib.get (name.as_string ()); +} + +template <Namespace N> +tl::optional<Rib::Definition> +ForeverStack<N>::get_prelude (const std::string &name) +{ + return prelude.rib.get (name); +} + template <> tl::optional<Rib::Definition> inline ForeverStack<Namespace::Labels>::get ( const Identifier &name) @@ -373,22 +416,21 @@ check_leading_kw_at_start (const S &segment, bool condition) template <Namespace N> template <typename S> tl::optional<typename std::vector<S>::const_iterator> -ForeverStack<N>::find_starting_point (const std::vector<S> &segments, - Node &starting_point) +ForeverStack<N>::find_starting_point ( + const std::vector<S> &segments, std::reference_wrapper<Node> &starting_point, + std::function<void (const S &, NodeId)> insert_segment_resolution) { auto iterator = segments.begin (); - // If we need to do path segment resolution, then we start - // at the closest module. In order to resolve something like `foo::bar!()`, we - // need to get back to the surrounding module, and look for a child module - // named `foo`. - if (segments.size () > 1) - starting_point = find_closest_module (starting_point); - for (; !is_last (iterator, segments); iterator++) { - auto &seg = *iterator; - auto is_self_or_crate + auto &outer_seg = *iterator; + + if (unwrap_segment_get_lang_item (outer_seg).has_value ()) + break; + + auto &seg = unwrap_type_segment (outer_seg); + bool is_self_or_crate = seg.is_crate_path_seg () || seg.is_lower_self_seg (); // if we're after the first path segment and meet `self` or `crate`, it's @@ -400,25 +442,32 @@ ForeverStack<N>::find_starting_point (const std::vector<S> &segments, if (seg.is_crate_path_seg ()) { starting_point = root; + insert_segment_resolution (outer_seg, starting_point.get ().id); iterator++; break; } if (seg.is_lower_self_seg ()) { - // do nothing and exit + // insert segment resolution and exit + starting_point = find_closest_module (starting_point); + insert_segment_resolution (outer_seg, starting_point.get ().id); iterator++; break; } if (seg.is_super_path_seg ()) { - if (starting_point.is_root ()) + starting_point = find_closest_module (starting_point); + if (starting_point.get ().is_root ()) { rust_error_at (seg.get_locus (), ErrorCode::E0433, "too many leading %<super%> keywords"); return tl::nullopt; } - starting_point = find_closest_module (starting_point.parent.value ()); + starting_point + = find_closest_module (starting_point.get ().parent.value ()); + + insert_segment_resolution (outer_seg, starting_point.get ().id); continue; } @@ -436,13 +485,26 @@ template <typename S> tl::optional<typename ForeverStack<N>::Node &> ForeverStack<N>::resolve_segments ( Node &starting_point, const std::vector<S> &segments, - typename std::vector<S>::const_iterator iterator) + typename std::vector<S>::const_iterator iterator, + std::function<void (const S &, NodeId)> insert_segment_resolution) { - auto *current_node = &starting_point; + Node *current_node = &starting_point; for (; !is_last (iterator, segments); iterator++) { - auto &seg = *iterator; - auto str = seg.as_string (); + auto &outer_seg = *iterator; + + if (auto lang_item = unwrap_segment_get_lang_item (outer_seg)) + { + NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node ( + lang_item.value ()); + current_node = &dfs_node (root, seg_id).value (); + + insert_segment_resolution (outer_seg, seg_id); + continue; + } + + auto &seg = unwrap_type_segment (outer_seg); + std::string str = seg.as_string (); rust_debug ("[ARTHUR]: resolving segment part: %s", str.c_str ()); // check that we don't encounter *any* leading keywords afterwards @@ -453,30 +515,80 @@ ForeverStack<N>::resolve_segments ( tl::optional<typename ForeverStack<N>::Node &> child = tl::nullopt; - for (auto &kv : current_node->children) + /* + * On every iteration this loop either + * + * 1. terminates + * + * 2. decreases the depth of the node pointed to by current_node until + * current_node reaches the root + * + * 3. If the root node is reached, and we were not able to resolve the + * segment, we search the prelude rib for the segment, by setting + * current_node to point to the prelude, and toggling the + * searched_prelude boolean to true. If current_node is the prelude + * rib, and searched_prelude is true, we will exit. + * + * This ensures termination. + * + */ + bool searched_prelude = false; + while (true) { - auto &link = kv.first; + // may set the value of child + for (auto &kv : current_node->children) + { + auto &link = kv.first; + + if (link.path.map_or ( + [&str] (Identifier path) { + auto &path_str = path.as_string (); + return str == path_str; + }, + false)) + { + child = kv.second; + break; + } + } - if (link.path.map_or ( - [&str] (Identifier path) { - auto &path_str = path.as_string (); - return str == path_str; - }, - false)) + if (child.has_value ()) { - child = kv.second; break; } - } - if (!child.has_value ()) - { - rust_error_at (seg.get_locus (), ErrorCode::E0433, - "failed to resolve path segment %qs", str.c_str ()); - return tl::nullopt; + if (N == Namespace::Types) + { + auto rib_lookup = current_node->rib.get (seg.as_string ()); + if (rib_lookup && !rib_lookup->is_ambiguous ()) + { + insert_segment_resolution (outer_seg, + rib_lookup->get_node_id ()); + return tl::nullopt; + } + } + + if (current_node->is_root () && !searched_prelude) + { + searched_prelude = true; + current_node = &prelude; + continue; + } + + if (!is_start (iterator, segments) + || current_node->rib.kind == Rib::Kind::Module + || current_node->is_prelude ()) + { + return tl::nullopt; + } + + current_node = ¤t_node->parent.value (); } + // if child didn't contain a value + // the while loop above should have return'd or kept looping current_node = &child.value (); + insert_segment_resolution (outer_seg, current_node->id); } return *current_node; @@ -485,23 +597,66 @@ ForeverStack<N>::resolve_segments ( template <Namespace N> template <typename S> tl::optional<Rib::Definition> -ForeverStack<N>::resolve_path (const std::vector<S> &segments) +ForeverStack<N>::resolve_path ( + const std::vector<S> &segments, + std::function<void (const S &, NodeId)> insert_segment_resolution) { // TODO: What to do if segments.empty() ? // if there's only one segment, we just use `get` if (segments.size () == 1) - return get (segments.back ().as_string ()); + { + auto &seg = segments.front (); + if (auto lang_item = unwrap_segment_get_lang_item (seg)) + { + NodeId seg_id = Analysis::Mappings::get ().get_lang_item_node ( + lang_item.value ()); + + insert_segment_resolution (seg, seg_id); + // TODO: does NonShadowable matter? + return Rib::Definition::NonShadowable (seg_id); + } + + tl::optional<Rib::Definition> res + = get (unwrap_type_segment (segments.back ()).as_string ()); + + if (!res) + res = get_prelude (unwrap_type_segment (segments.back ()).as_string ()); - auto starting_point = cursor (); + if (res && !res->is_ambiguous ()) + insert_segment_resolution (segments.back (), res->get_node_id ()); + return res; + } + + std::reference_wrapper<Node> starting_point = cursor (); - return find_starting_point (segments, starting_point) - .and_then ([this, &segments, &starting_point] ( + return find_starting_point (segments, starting_point, + insert_segment_resolution) + .and_then ([this, &segments, &starting_point, &insert_segment_resolution] ( typename std::vector<S>::const_iterator iterator) { - return resolve_segments (starting_point, segments, iterator); + return resolve_segments (starting_point.get (), segments, iterator, + insert_segment_resolution); }) - .and_then ([&segments] (Node final_node) { - return final_node.rib.get (segments.back ().as_string ()); + .and_then ([this, &segments, &insert_segment_resolution] ( + Node final_node) -> tl::optional<Rib::Definition> { + // leave resolution within impl blocks to type checker + if (final_node.rib.kind == Rib::Kind::TraitOrImpl) + return tl::nullopt; + + std::string seg_name + = unwrap_type_segment (segments.back ()).as_string (); + + // assuming this can't be a lang item segment + tl::optional<Rib::Definition> res = final_node.rib.get (seg_name); + + // Ok we didn't find it in the rib, Lets try the prelude... + if (!res) + res = get_prelude (seg_name); + + if (res && !res->is_ambiguous ()) + insert_segment_resolution (segments.back (), res->get_node_id ()); + + return res; }); } @@ -593,7 +748,7 @@ ForeverStack<N>::to_canonical_path (NodeId id) const auto &link = kv.first; auto &child = kv.second; - if (link.id == child.id) + if (current.id == child.id) { outer_link = &link; break; @@ -611,7 +766,12 @@ ForeverStack<N>::to_canonical_path (NodeId id) const return KeepGoing::Yes; }); - auto path = Resolver::CanonicalPath::create_empty (); + auto &mappings = Analysis::Mappings::get (); + CrateNum crate_num = mappings.lookup_crate_num (root.id).value (); + auto path = Resolver::CanonicalPath::new_seg ( + root.id, mappings.get_crate_name (crate_num).value ()); + path.set_crate_num (crate_num); + for (const auto &segment : segments) path = path.append (segment); @@ -626,12 +786,31 @@ template <Namespace N> tl::optional<Rib &> ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find) { + return dfs_node (starting_point, to_find).map ([] (Node &x) -> Rib & { + return x.rib; + }); +} + +template <Namespace N> +tl::optional<const Rib &> +ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point, + NodeId to_find) const +{ + return dfs_node (starting_point, to_find) + .map ([] (const Node &x) -> const Rib & { return x.rib; }); +} + +template <Namespace N> +tl::optional<typename ForeverStack<N>::Node &> +ForeverStack<N>::dfs_node (ForeverStack<N>::Node &starting_point, + NodeId to_find) +{ if (starting_point.id == to_find) - return starting_point.rib; + return starting_point; for (auto &child : starting_point.children) { - auto candidate = dfs_rib (child.second, to_find); + auto candidate = dfs_node (child.second, to_find); if (candidate.has_value ()) return candidate; @@ -641,16 +820,16 @@ ForeverStack<N>::dfs_rib (ForeverStack<N>::Node &starting_point, NodeId to_find) } template <Namespace N> -tl::optional<const Rib &> -ForeverStack<N>::dfs_rib (const ForeverStack<N>::Node &starting_point, - NodeId to_find) const +tl::optional<const typename ForeverStack<N>::Node &> +ForeverStack<N>::dfs_node (const ForeverStack<N>::Node &starting_point, + NodeId to_find) const { if (starting_point.id == to_find) - return starting_point.rib; + return starting_point; for (auto &child : starting_point.children) { - auto candidate = dfs_rib (child.second, to_find); + auto candidate = dfs_node (child.second, to_find); if (candidate.has_value ()) return candidate; @@ -677,15 +856,19 @@ template <Namespace N> void ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib, const std::string &next, - const std::string &next_next) + const std::string &next_next) const { + std::string rib_kind = Rib::kind_to_string (rib.kind); + stream << next << "rib [" << rib_kind << "]: {"; if (rib.get_values ().empty ()) { - stream << next << "rib: {},\n"; + stream << "}\n"; return; } - - stream << next << "rib: {\n"; + else + { + stream << "\n"; + } for (const auto &kv : rib.get_values ()) stream << next_next << kv.first << ": " << kv.second.to_string () << "\n"; @@ -696,7 +879,7 @@ ForeverStack<N>::stream_rib (std::stringstream &stream, const Rib &rib, template <Namespace N> void ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation, - const ForeverStack<N>::Node &node) + const ForeverStack<N>::Node &node) const { auto indent = std::string (indentation, ' '); auto next = std::string (indentation + 4, ' '); @@ -728,7 +911,7 @@ ForeverStack<N>::stream_node (std::stringstream &stream, unsigned indentation, template <Namespace N> std::string -ForeverStack<N>::as_debug_string () +ForeverStack<N>::as_debug_string () const { std::stringstream stream; @@ -737,6 +920,13 @@ ForeverStack<N>::as_debug_string () return stream.str (); } +template <Namespace N> +bool +ForeverStack<N>::is_module_descendant (NodeId parent, NodeId child) const +{ + return dfs_node (dfs_node (root, parent).value (), child).has_value (); +} + // FIXME: Can we add selftests? } // namespace Resolver2_0 |