Branch data Line data Source code
1 : : // Copyright (C) 2020-2025 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 : : #ifndef RUST_NAME_RESOLVER_2_0_H
20 : : #define RUST_NAME_RESOLVER_2_0_H
21 : :
22 : : #include "optional.h"
23 : : #include "rust-forever-stack.h"
24 : : #include "rust-hir-map.h"
25 : : #include "rust-rib.h"
26 : :
27 : : namespace Rust {
28 : : namespace Resolver2_0 {
29 : :
30 : : // TODO: Add missing mappings and data structures
31 : :
32 : : /**
33 : : The data structures we need to develop need to fill in a few roles - like the
34 : : original name resolver, they need to be accessible at multiple points during the
35 : : pipeline to allow compiler passes such as macro expansion or typechecking to
36 : : benefit from them. Unlike the original name resolution, these data structures
37 : : need to be created by multiple compiler passes: Whereas the original name
38 : : resolution of gccrs tries to perform name resolution in a single pass, it fails
39 : : at properly handling more complex name resolution cases such as macro name
40 : : resolution, imports in general, and glob imports in particular. The goal of this
41 : : new name resolution algorithm is to split the name resolution in at least two
42 : : passes - `Early` name resolution, which takes care of macro name resolution and
43 : : import resolution, and `Late` name resolution - your typical name resolution,
44 : : for types, functions, variables...
45 : :
46 : : 1. `Early`
47 : :
48 : : The Early name resolution is tied in snuggly with macro expansion: macro
49 : : expansion cannot happen without some form of name resolution (pointing an
50 : : invocation to its definition) but may also *depend* on name resolution (a macro
51 : : generating another macro... or importing items... and funny other cases like
52 : : these). It needs to work in a fixed-point fashion alongside macro expansion:
53 : : While there are imports to resolve, or macros to expand, we need to keep going
54 : : and resolve them. This is achieved, among other things, by a top-level name
55 : : resolution pass in charge of collection use statements and macro definitions (as
56 : : well as Items, which will be useful for later passes of the name resolution).
57 : :
58 : : This top-level pass exists because Rust enables you to call a function
59 : : before having declared it (at a lexical level, i.e calling `f(15)` at line 3
60 : : while the `f` function is declared at line 1499).
61 : :
62 : : This Early pass needs to build the first part of our "resolution map", which
63 : : will then be used in multiple contexts:
64 : :
65 : : 1. The MacroExpander, in a read-only fashion: fetching macro definitions for
66 : : each invocation and performing the expansion.
67 : : 2. `Late`, which will write more data inside that resolution map, and use it
68 : : to perform its name resolution too.
69 : :
70 : : This is where the first challenge of this data structure lies: The existing
71 : : data structures and name resolution algorithm relies on the name resolution pass
72 : : happening just once. In typical name resolution fashion, when it sees a lexical
73 : : scope (a new module, a function's block, a block expression...), it "pushes" a
74 : : new "Scope" to a stack of these scopes, and "pops" it when exiting said lexical
75 : : scope. However, because we are splitting the name resolution into two passes, we
76 : : would like to avoid re-doing a bunch of work we've already done - which is why
77 : : this data structure needs to allow "re-entrancy", or to at least not keep as
78 : : much state as the existing one, and allow for viewing the same module multiple
79 : : times without throwing a fit.
80 : :
81 : : We will be implementing a "forever stack" of scopes, which allows the user the
82 : : pushing of new scopes onto the stack, but only simulates the popping of a scope:
83 : : When pushing new scopes, more space is allocated on our stack, and we keep
84 : : track of this scope as being the current one - however, when popping this scope,
85 : : we do not actually delete the memory associated with it: we simply mark the
86 : : previous scope (parent) as the current one.
87 : :
88 : : In the example below, each number indicates the "state" of our resolution map,
89 : : and the carret is used to point to the current lexical scope.
90 : :
91 : : ```rust
92 : : // []
93 : : //
94 : : fn main() { // [ `main` scope: {} ]
95 : : // ^
96 : : let a = 15; // [ `main` scope: { Decl(a) } ]
97 : : // ^
98 : : { _PUSH_ // [ `main` scope: { Decl(a) }, anonymous scope: {} ]
99 : : // ^
100 : : let a = 16; // [ `main` scope: { Decl(a) }, anonymous scope: { Decl(a) } ]
101 : : // ^
102 : : f(a); // [ `main` scope: { Decl(a) }, anonymous scope: { Decl(a) } ]
103 : : // ^
104 : : } _POP_ // [ `main` scope: { Decl(a) }, anonymous scope: { Decl(a) } ]
105 : : // ^
106 : : f(a); // [ `main` scope: { Decl(a) }, anonymous scope: { Decl(a) } ]
107 : : // ^
108 : : }
109 : : ```
110 : :
111 : : This allows us to revisit scopes previously visited in later phases of the name
112 : : resolution, and add more information if necessary.
113 : :
114 : : 2. `Late`
115 : :
116 : : `Late` name resolution possesses some unique challenges since Rust's name
117 : : resolution rules are extremely complex - variable shadowing, variable capture in
118 : : closures (but not inner functions!)... You can have a look at a fucked up
119 : : example here:
120 : :
121 : : https://rustc-dev-guide.rust-lang.org/name-resolution.html#scopes-and-ribs
122 : :
123 : : This requires us to think about what exactly to put in our `Scope`s and what to
124 : : do with our `Rib`s - and how it affects our data structures. For example, in the
125 : : above example, `rustc` demonstrates how multiple `Rib`s can be created inside of
126 : : a single lexical scope for variables, as the Rust programming language allows
127 : : shadowing.
128 : :
129 : : TODO: Mention macro hygiene and that it is the same
130 : : TODO: How does this affect our data structures?
131 : : TODO: Last challenge - reuse the same APIs to allow the typechecker to not
132 : : change?
133 : : TODO: Mention that ForeverStack is templated to make sure that behavior is
134 : : correct
135 : : */
136 : :
137 : : // FIXME: Documentation
138 : : class Usage
139 : : {
140 : : public:
141 : 151250 : explicit Usage (NodeId id) : id (id) {}
142 : :
143 : : // TODO: move to name-resolution-ctx.cc
144 : : // storing it as a key in a map
145 : 1794960 : bool operator< (const Usage other) const { return other.id < id; }
146 : :
147 : : NodeId id;
148 : : };
149 : :
150 : : // FIXME: Documentation
151 : : class Definition
152 : : {
153 : : public:
154 : 11347 : explicit Definition (NodeId id) : id (id) {}
155 : :
156 : : NodeId id;
157 : : };
158 : :
159 : : // Now our resolver, which keeps track of all the `ForeverStack`s we could want
160 : : class NameResolutionContext
161 : : {
162 : : public:
163 : : NameResolutionContext ();
164 : :
165 : : /**
166 : : * Insert a new value in the current rib.
167 : : *
168 : : * @param name Name of the value to insert.
169 : : * @param id This value's ID, e.g the function definition's node ID.
170 : : * @param ns Namespace in which to insert the value.
171 : : */
172 : : tl::expected<NodeId, DuplicateNameError> insert (Identifier name, NodeId id,
173 : : Namespace ns);
174 : :
175 : : tl::expected<NodeId, DuplicateNameError> insert_variant (Identifier name,
176 : : NodeId id);
177 : :
178 : : tl::expected<NodeId, DuplicateNameError>
179 : : insert_shadowable (Identifier name, NodeId id, Namespace ns);
180 : :
181 : : tl::expected<NodeId, DuplicateNameError>
182 : : insert_globbed (Identifier name, NodeId id, Namespace ns);
183 : :
184 : : /**
185 : : * Run a lambda in a "scoped" context, meaning that a new `Rib` will be pushed
186 : : * before executing the lambda and then popped. This is useful for all kinds
187 : : * of scope in the language, such as a block expression or when entering a
188 : : * function. This variant of the function enters a new scope in *all*
189 : : * namespaces, while the second variant enters a scope in *one* namespace.
190 : : *
191 : : * @param rib_kind New `Rib` to create when entering this scope. A function
192 : : * `Rib`, or an item `Rib`... etc
193 : : * @param scope_id node ID of the scope we are entering, e.g the block's
194 : : * `NodeId`.
195 : : * @param lambda Function to run within that scope
196 : : * @param path Optional path of the scope. This is useful for scopes which
197 : : * affect path resolution, such as modules. Defaults to an empty
198 : : * option.
199 : : */
200 : : // FIXME: Do we want to handle something in particular for expected within the
201 : : // scoped lambda?
202 : : void scoped (Rib::Kind rib_kind, NodeId scope_id,
203 : : std::function<void (void)> lambda,
204 : : tl::optional<Identifier> path = {});
205 : : void scoped (Rib::Kind rib_kind, Namespace ns, NodeId scope_id,
206 : : std::function<void (void)> lambda,
207 : : tl::optional<Identifier> path = {});
208 : :
209 : : ForeverStack<Namespace::Values> values;
210 : : ForeverStack<Namespace::Types> types;
211 : : ForeverStack<Namespace::Macros> macros;
212 : : ForeverStack<Namespace::Labels> labels;
213 : :
214 : : Analysis::Mappings &mappings;
215 : :
216 : : // TODO: Rename
217 : : // TODO: Use newtype pattern for Usage and Definition
218 : : void map_usage (Usage usage, Definition definition);
219 : :
220 : : tl::optional<NodeId> lookup (NodeId usage) const;
221 : :
222 : : template <typename S>
223 : 9678 : tl::optional<Rib::Definition> resolve_path (const std::vector<S> &segments,
224 : : bool has_opening_scope_resolution,
225 : : Namespace ns)
226 : : {
227 : 9678 : std::function<void (const S &, NodeId)> insert_segment_resolution
228 : 22352 : = [this] (const S &seg, NodeId id) {
229 : 4604 : auto seg_id = unwrap_segment_node_id (seg);
230 : 10960 : if (resolved_nodes.find (Usage (seg_id)) == resolved_nodes.end ())
231 : 9475 : map_usage (Usage (seg_id), Definition (id));
232 : : };
233 : 9678 : switch (ns)
234 : : {
235 : 2228 : case Namespace::Values:
236 : 2228 : return values.resolve_path (segments, has_opening_scope_resolution,
237 : 2228 : insert_segment_resolution);
238 : 7139 : case Namespace::Types:
239 : 7139 : return types.resolve_path (segments, has_opening_scope_resolution,
240 : 7139 : insert_segment_resolution);
241 : 311 : case Namespace::Macros:
242 : 311 : return macros.resolve_path (segments, has_opening_scope_resolution,
243 : 311 : insert_segment_resolution);
244 : 0 : case Namespace::Labels:
245 : 0 : return labels.resolve_path (segments, has_opening_scope_resolution,
246 : 0 : insert_segment_resolution);
247 : 0 : default:
248 : 0 : rust_unreachable ();
249 : : }
250 : 9678 : }
251 : :
252 : : template <typename S, typename... Args>
253 : 1990 : tl::optional<Rib::Definition> resolve_path (const std::vector<S> &segments,
254 : : bool has_opening_scope_resolution,
255 : : Args... ns_args)
256 : : {
257 : 1990 : std::initializer_list<Namespace> namespaces = {ns_args...};
258 : :
259 : 2716 : for (auto ns : namespaces)
260 : : {
261 : 2443 : if (auto ret
262 : : = resolve_path (segments, has_opening_scope_resolution, ns))
263 : : return ret;
264 : : }
265 : :
266 : 273 : return tl::nullopt;
267 : : }
268 : :
269 : : template <typename... Args>
270 : 799 : tl::optional<Rib::Definition> resolve_path (const AST::SimplePath &path,
271 : : Args... ns_args)
272 : : {
273 : : return resolve_path (path.get_segments (),
274 : 799 : path.has_opening_scope_resolution (), ns_args...);
275 : : }
276 : :
277 : : template <typename... Args>
278 : 2142 : tl::optional<Rib::Definition> resolve_path (const AST::PathInExpression &path,
279 : : Args... ns_args)
280 : : {
281 : 2142 : return resolve_path (path.get_segments (), path.opening_scope_resolution (),
282 : 2142 : ns_args...);
283 : : }
284 : :
285 : : template <typename... Args>
286 : 6284 : tl::optional<Rib::Definition> resolve_path (const AST::TypePath &path,
287 : : Args... ns_args)
288 : : {
289 : : return resolve_path (path.get_segments (),
290 : 6284 : path.has_opening_scope_resolution_op (), ns_args...);
291 : : }
292 : :
293 : : private:
294 : : /* Map of "usage" nodes which have been resolved to a "definition" node */
295 : : std::map<Usage, Definition> resolved_nodes;
296 : : };
297 : :
298 : : } // namespace Resolver2_0
299 : : } // namespace Rust
300 : :
301 : : #endif // ! RUST_NAME_RESOLVER_2_0_H
|
