Line data Source code
1 : // Copyright (C) 2020-2026 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 : size_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 127 : 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 132 : 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 2433 : 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 425 : 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 : {
476 62 : auto &fields = ty->as<TyTy::TupleType> ()->get_fields ();
477 62 : return std::all_of (fields.begin (), fields.end (),
478 0 : [] (const TyTy::TyVar &field) {
479 0 : return is_type_copy (field.get_tyty ());
480 62 : });
481 : }
482 0 : case TyTy::ARRAY:
483 0 : {
484 0 : return is_type_copy (ty->as<TyTy::ArrayType> ()->get_element_type ());
485 : }
486 0 : case TyTy::INFER:
487 0 : case TyTy::PARAM:
488 0 : case TyTy::ERROR:
489 0 : case TyTy::STR:
490 0 : case TyTy::PLACEHOLDER:
491 0 : rust_unreachable ();
492 36 : case TyTy::ADT: // TODO: check trait
493 36 : case TyTy::PROJECTION: // TODO: DUNNO
494 36 : case TyTy::CLOSURE: // TODO: DUNNO
495 36 : case TyTy::DYNAMIC: // TODO: dunno
496 36 : case TyTy::CONST:
497 36 : case TyTy::OPAQUE:
498 36 : return false;
499 : }
500 0 : rust_unreachable ();
501 : }
502 :
503 : /** Check whether given place is not out-of-scope. */
504 : WARN_UNUSED_RESULT bool is_in_scope (PlaceId place) const
505 : {
506 : for (ScopeId scope = current_scope; scope != INVALID_SCOPE;
507 : scope = scopes[scope].parent)
508 : {
509 : auto &scope_ref = scopes[scope];
510 : if (std::find (scope_ref.locals.begin (), scope_ref.locals.end (),
511 : place)
512 : != scope_ref.locals.end ())
513 : return true;
514 : }
515 : return false;
516 : }
517 : };
518 :
519 : } // namespace BIR
520 : } // namespace Rust
521 :
522 : #endif // RUST_BIR_PLACE_H
|
