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