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