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_BIR_PLACE_H
20 : : #define RUST_BIR_PLACE_H
21 : :
22 : : #include "rust-mapping-common.h"
23 : : #include "rust-system.h"
24 : : #include "rust-tyty.h"
25 : : #include "rust-bir-free-region.h"
26 : :
27 : : #include "rust-tyty-variance-analysis.h"
28 : : #include "polonius/rust-polonius-ffi.h"
29 : : #include "rust-hir-type-check.h"
30 : :
31 : : namespace Rust {
32 : : namespace BIR {
33 : :
34 : : /** A unique identifier for a place in the BIR. */
35 : : using PlaceId = uint32_t;
36 : :
37 : : static constexpr PlaceId INVALID_PLACE = 0;
38 : : static constexpr PlaceId RETURN_VALUE_PLACE = 1;
39 : : static constexpr PlaceId FIRST_VARIABLE_PLACE = RETURN_VALUE_PLACE;
40 : :
41 : : using Variance = TyTy::VarianceAnalysis::Variance;
42 : : using LoanId = uint32_t;
43 : :
44 : : /**
45 : : * Representation of lvalues and constants in BIR.
46 : : * See bir bir design notes (in this directory) and the Polonius book.
47 : : */
48 : 0 : struct Place
49 : : {
50 : : enum Kind
51 : : {
52 : : INVALID,
53 : : VARIABLE,
54 : : TEMPORARY,
55 : : CONSTANT,
56 : : FIELD,
57 : : INDEX,
58 : : DEREF,
59 : : };
60 : :
61 : : Kind kind;
62 : : uint32_t variable_or_field_index; // NodeId for VARIABLE
63 : : /** Data for traversing paths in the PlaceDB. */
64 : : struct Path
65 : : {
66 : : PlaceId parent = INVALID_PLACE;
67 : : PlaceId first_child = INVALID_PLACE;
68 : : PlaceId next_sibling = INVALID_PLACE;
69 : :
70 : 0 : Path (PlaceId parent, PlaceId first_child, PlaceId next_sibling)
71 : 0 : : parent (parent), first_child (first_child), next_sibling (next_sibling)
72 : : {}
73 : 0 : Path () = default;
74 : : } path;
75 : : /** Copy trait */
76 : : bool is_copy;
77 : : bool has_drop = false;
78 : : TyTy::BaseType *tyty;
79 : : FreeRegions regions{{}};
80 : : std::vector<LoanId> borrowed_by{};
81 : :
82 : : public:
83 : 0 : Place (Kind kind, uint32_t variable_or_field_index, const Path &path,
84 : : bool is_copy, TyTy::BaseType *tyty)
85 : 0 : : kind (kind), variable_or_field_index (variable_or_field_index),
86 : 0 : path (path), is_copy (is_copy), tyty (tyty)
87 : 0 : {}
88 : :
89 : : // Place can only be stored in PlaceDB and used via reference. Turn all
90 : : // accidental copies into errors.
91 : : Place (const Place &) = delete;
92 : 0 : Place (Place &&) = default;
93 : :
94 : : public:
95 : 0 : WARN_UNUSED_RESULT bool is_lvalue () const
96 : : {
97 : 0 : return kind == VARIABLE || is_path ();
98 : : }
99 : :
100 : 0 : WARN_UNUSED_RESULT bool is_rvalue () const { return kind == TEMPORARY; }
101 : :
102 : 0 : bool is_constant () const { return kind == CONSTANT; }
103 : :
104 : 0 : WARN_UNUSED_RESULT bool is_var () const
105 : : {
106 : 0 : return kind == VARIABLE || kind == TEMPORARY;
107 : : }
108 : :
109 : 0 : WARN_UNUSED_RESULT bool is_path () const
110 : : {
111 : 0 : return kind == FIELD || kind == INDEX || kind == DEREF;
112 : : }
113 : :
114 : : WARN_UNUSED_RESULT TyTy::BaseType *get_fn_return_ty () const
115 : : {
116 : : switch (tyty->get_kind ())
117 : : {
118 : : case TyTy::FNPTR:
119 : : return tyty->as<TyTy::FnPtr> ()->get_return_type ();
120 : : case TyTy::FNDEF:
121 : : return tyty->as<TyTy::FnType> ()->get_return_type ();
122 : : default:
123 : : rust_assert (false);
124 : : }
125 : : }
126 : :
127 : : WARN_UNUSED_RESULT bool is_indirect () const
128 : : {
129 : : // TODO: probably incomplete, check other projections
130 : : switch (tyty->get_kind ())
131 : : {
132 : : case TyTy::REF:
133 : : case TyTy::POINTER:
134 : : return true;
135 : : default:
136 : : return false;
137 : : }
138 : : }
139 : :
140 : 0 : WARN_UNUSED_RESULT bool should_be_moved () const
141 : : {
142 : 0 : return kind == TEMPORARY || (!is_copy && kind != CONSTANT);
143 : : }
144 : : };
145 : :
146 : : using ScopeId = uint32_t;
147 : :
148 : : static constexpr ScopeId INVALID_SCOPE = std::numeric_limits<ScopeId>::max ();
149 : : /** Arguments and return value are in the root scope. */
150 : : static constexpr ScopeId ROOT_SCOPE = 0;
151 : : /** Top-level local variables are in the top-level scope. */
152 : : static constexpr ScopeId TOP_LEVEL_SCOPE = 1;
153 : :
154 : 0 : struct Scope
155 : : {
156 : : ScopeId parent = INVALID_SCOPE;
157 : : std::vector<ScopeId> children;
158 : : std::vector<PlaceId> locals;
159 : : };
160 : :
161 : : struct Loan
162 : : {
163 : : Mutability mutability;
164 : : PlaceId place;
165 : : };
166 : :
167 : : /** Allocated places and keeps track of paths. */
168 : : class PlaceDB
169 : : {
170 : : private:
171 : : // Possible optimizations: separate variables to speedup lookup.
172 : : std::vector<Place> places;
173 : : std::unordered_map<TyTy::BaseType *, PlaceId> constants_lookup;
174 : : std::vector<Scope> scopes;
175 : : ScopeId current_scope = 0;
176 : :
177 : : std::vector<Loan> loans;
178 : :
179 : : Polonius::Origin next_free_region = 1;
180 : :
181 : : public:
182 : 0 : PlaceDB ()
183 : 0 : {
184 : : // Reserved index for invalid place.
185 : 0 : places.push_back ({Place::INVALID, 0, {}, false, nullptr});
186 : :
187 : 0 : scopes.emplace_back (); // Root scope.
188 : 0 : }
189 : :
190 : 0 : Place &operator[] (PlaceId id) { return places.at (id); }
191 : 0 : const Place &operator[] (PlaceId id) const { return places.at (id); }
192 : :
193 : : decltype (places)::const_iterator begin () const { return places.begin (); }
194 : : decltype (places)::const_iterator end () const { return places.end (); }
195 : :
196 : 0 : size_t size () const { return places.size (); }
197 : :
198 : 0 : const std::vector<Loan> &get_loans () const { return loans; }
199 : :
200 : 0 : ScopeId get_current_scope_id () const { return current_scope; }
201 : :
202 : : const std::vector<Scope> &get_scopes () const { return scopes; }
203 : :
204 : 0 : const Scope &get_current_scope () const { return scopes[current_scope]; }
205 : :
206 : 0 : const Scope &get_scope (ScopeId id) const { return scopes[id]; }
207 : :
208 : 0 : FreeRegion get_next_free_region () { return next_free_region++; }
209 : :
210 : 0 : FreeRegion peek_next_free_region () const { return next_free_region; }
211 : :
212 : 0 : FreeRegion &expose_next_free_region () { return next_free_region; }
213 : :
214 : 0 : ScopeId push_new_scope ()
215 : : {
216 : 0 : ScopeId new_scope = scopes.size ();
217 : 0 : scopes.emplace_back ();
218 : 0 : scopes[new_scope].parent = current_scope;
219 : 0 : scopes[current_scope].children.push_back (new_scope);
220 : 0 : current_scope = new_scope;
221 : 0 : return new_scope;
222 : : }
223 : :
224 : 0 : ScopeId pop_scope ()
225 : : {
226 : 0 : current_scope = scopes[current_scope].parent;
227 : 0 : return current_scope;
228 : : }
229 : :
230 : 0 : PlaceId add_place (Place &&place, PlaceId last_sibling = 0)
231 : : {
232 : 0 : places.emplace_back (std::forward<Place &&> (place));
233 : 0 : PlaceId new_place = places.size () - 1;
234 : 0 : Place &new_place_ref = places[new_place]; // Intentional shadowing.
235 : 0 : if (last_sibling == 0)
236 : 0 : places[new_place_ref.path.parent].path.first_child = new_place;
237 : : else
238 : 0 : places[last_sibling].path.next_sibling = new_place;
239 : :
240 : 0 : if (new_place_ref.kind == Place::VARIABLE
241 : 0 : || new_place_ref.kind == Place::TEMPORARY)
242 : 0 : scopes[current_scope].locals.push_back (new_place);
243 : :
244 : 0 : auto variances = Resolver::TypeCheckContext::get ()
245 : 0 : ->get_variance_analysis_ctx ()
246 : 0 : .query_type_variances (new_place_ref.tyty);
247 : 0 : std::vector<Polonius::Origin> regions;
248 : 0 : for (size_t i = 0; i < variances.size (); i++)
249 : 0 : regions.push_back (next_free_region++);
250 : :
251 : 0 : new_place_ref.regions.set_from (std::move (regions));
252 : :
253 : 0 : return new_place;
254 : 0 : }
255 : :
256 : 0 : PlaceId add_variable (NodeId id, TyTy::BaseType *tyty)
257 : : {
258 : 0 : return add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty}, 0);
259 : : }
260 : :
261 : 0 : WARN_UNUSED_RESULT PlaceId lookup_or_add_path (Place::Kind kind,
262 : : TyTy::BaseType *tyty,
263 : : PlaceId parent, size_t id = 0)
264 : : {
265 : 0 : PlaceId current = 0;
266 : 0 : if (parent < places.size ())
267 : : {
268 : 0 : current = places[parent].path.first_child;
269 : 0 : while (current != 0)
270 : : {
271 : 0 : if (places[current].kind == kind
272 : 0 : && places[current].variable_or_field_index == id)
273 : : {
274 : 0 : rust_assert (places[current].tyty->is_equal (*tyty));
275 : : return current;
276 : : }
277 : 0 : current = places[current].path.next_sibling;
278 : : }
279 : : }
280 : 0 : return add_place ({kind, (uint32_t) id, Place::Path{parent, 0, 0},
281 : 0 : is_type_copy (tyty), tyty},
282 : : current);
283 : : }
284 : :
285 : 0 : PlaceId add_temporary (TyTy::BaseType *tyty)
286 : : {
287 : 0 : return add_place ({Place::TEMPORARY, 0, {}, is_type_copy (tyty), tyty}, 0);
288 : : }
289 : :
290 : 0 : PlaceId get_constant (TyTy::BaseType *tyty)
291 : : {
292 : 0 : auto lookup = constants_lookup.find (tyty);
293 : 0 : if (lookup != constants_lookup.end ())
294 : 0 : return lookup->second;
295 : 0 : return add_place ({Place::CONSTANT, 0, {}, is_type_copy (tyty), tyty});
296 : : }
297 : :
298 : 0 : PlaceId lookup_variable (NodeId id)
299 : : {
300 : 0 : PlaceId current = FIRST_VARIABLE_PLACE;
301 : :
302 : 0 : while (current != places.size ())
303 : : {
304 : 0 : if (places[current].kind == Place::VARIABLE
305 : 0 : && places[current].variable_or_field_index == id)
306 : 0 : return current;
307 : 0 : current++;
308 : : }
309 : : return INVALID_PLACE;
310 : : }
311 : :
312 : 0 : LoanId add_loan (Loan &&loan)
313 : : {
314 : 0 : LoanId id = loans.size ();
315 : 0 : loans.push_back (std::forward<Loan &&> (loan));
316 : 0 : PlaceId borrowed_place = loans.rbegin ()->place;
317 : 0 : places[loans.rbegin ()->place].borrowed_by.push_back (id);
318 : 0 : if (places[borrowed_place].kind == Place::DEREF)
319 : : {
320 : 0 : places[places[borrowed_place].path.parent].borrowed_by.push_back (id);
321 : : }
322 : 0 : return id;
323 : : }
324 : :
325 : 0 : PlaceId get_var (PlaceId id) const
326 : : {
327 : 0 : if (places[id].is_var ())
328 : : return id;
329 : 0 : rust_assert (places[id].is_path ());
330 : : PlaceId current = id;
331 : 0 : while (!places[current].is_var ())
332 : : {
333 : 0 : current = places[current].path.parent;
334 : : }
335 : : return current;
336 : : }
337 : :
338 : : void set_next_free_region (Polonius::Origin next_free_region)
339 : : {
340 : : this->next_free_region = next_free_region;
341 : : }
342 : :
343 : 0 : PlaceId lookup_or_add_variable (NodeId id, TyTy::BaseType *tyty)
344 : : {
345 : 0 : auto lookup = lookup_variable (id);
346 : 0 : if (lookup != INVALID_PLACE)
347 : : return lookup;
348 : :
349 : 0 : add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty});
350 : 0 : return places.size () - 1;
351 : : };
352 : :
353 : 0 : template <typename FN> void for_each_path_from_root (PlaceId var, FN fn) const
354 : : {
355 : 0 : PlaceId current = var;
356 : 0 : current = places[current].path.first_child;
357 : 0 : while (current != INVALID_PLACE)
358 : : {
359 : 0 : fn (current);
360 : 0 : for_each_path_from_root (current, fn);
361 : 0 : current = places[current].path.next_sibling;
362 : : }
363 : 0 : }
364 : :
365 : : template <typename FN>
366 : 0 : void for_each_path_segment (PlaceId place_id, FN fn) const
367 : : {
368 : 0 : PlaceId current = place_id;
369 : 0 : while (current != INVALID_PLACE)
370 : : {
371 : 0 : fn (current);
372 : 0 : current = places[current].path.parent;
373 : : }
374 : 0 : }
375 : :
376 : : private:
377 : 0 : static bool is_type_copy (TyTy::BaseType *ty)
378 : : {
379 : 0 : switch (ty->get_kind ())
380 : : {
381 : 0 : case TyTy::REF:
382 : 0 : return ty->as<TyTy::ReferenceType> ()->mutability () == Mutability::Imm;
383 : : case TyTy::POINTER:
384 : : case TyTy::SLICE:
385 : : case TyTy::BOOL:
386 : : case TyTy::CHAR:
387 : : case TyTy::INT:
388 : : case TyTy::UINT:
389 : : case TyTy::FLOAT:
390 : : case TyTy::USIZE:
391 : : case TyTy::ISIZE:
392 : : case TyTy::FNPTR:
393 : : case TyTy::FNDEF:
394 : : case TyTy::NEVER:
395 : : return true;
396 : 0 : case TyTy::TUPLE: {
397 : 0 : auto &fields = ty->as<TyTy::TupleType> ()->get_fields ();
398 : 0 : return std::all_of (fields.begin (), fields.end (),
399 : 0 : [] (const TyTy::TyVar &field) {
400 : 0 : return is_type_copy (field.get_tyty ());
401 : 0 : });
402 : : }
403 : 0 : case TyTy::ARRAY: {
404 : 0 : return is_type_copy (ty->as<TyTy::ArrayType> ()->get_element_type ());
405 : : }
406 : 0 : case TyTy::INFER:
407 : 0 : case TyTy::PARAM:
408 : 0 : case TyTy::ERROR:
409 : 0 : case TyTy::STR:
410 : 0 : case TyTy::PLACEHOLDER:
411 : 0 : rust_unreachable ();
412 : 0 : case TyTy::ADT: // TODO: check trait
413 : 0 : case TyTy::PROJECTION: // TODO: DUNNO
414 : 0 : case TyTy::CLOSURE: // TODO: DUNNO
415 : 0 : case TyTy::DYNAMIC: // TODO: dunno
416 : 0 : return false;
417 : : }
418 : 0 : rust_unreachable ();
419 : : }
420 : :
421 : : /** Check whether given place is not out-of-scope. */
422 : : WARN_UNUSED_RESULT bool is_in_scope (PlaceId place) const
423 : : {
424 : : for (ScopeId scope = current_scope; scope != INVALID_SCOPE;
425 : : scope = scopes[scope].parent)
426 : : {
427 : : auto &scope_ref = scopes[scope];
428 : : if (std::find (scope_ref.locals.begin (), scope_ref.locals.end (),
429 : : place)
430 : : != scope_ref.locals.end ())
431 : : return true;
432 : : }
433 : : return false;
434 : : }
435 : : };
436 : :
437 : : } // namespace BIR
438 : : } // namespace Rust
439 : :
440 : : #endif // RUST_BIR_PLACE_H
|
