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 243 : bool operator== (const PlaceId &rhs) const { return value == rhs.value; }
40 576 : bool operator!= (const PlaceId &rhs) const { return !(operator== (rhs)); }
41 68 : 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 1255 : 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 405 : Place (Kind kind, uint32_t variable_or_field_index, const Path &path,
106 : bool is_copy, TyTy::BaseType *tyty)
107 405 : : kind (kind), variable_or_field_index (variable_or_field_index),
108 405 : path (path), is_copy (is_copy), tyty (tyty)
109 405 : {}
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 850 : Place (Place &&) = default;
115 :
116 : public:
117 381 : WARN_UNUSED_RESULT bool is_lvalue () const
118 : {
119 381 : return kind == VARIABLE || is_path ();
120 : }
121 :
122 21 : WARN_UNUSED_RESULT bool is_rvalue () const { return kind == TEMPORARY; }
123 :
124 698 : bool is_constant () const { return kind == CONSTANT; }
125 :
126 1161 : WARN_UNUSED_RESULT bool is_var () const
127 : {
128 1161 : return kind == VARIABLE || kind == TEMPORARY;
129 : }
130 :
131 223 : WARN_UNUSED_RESULT bool is_path () const
132 : {
133 171 : 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 280 : WARN_UNUSED_RESULT bool should_be_moved () const
163 : {
164 280 : 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 121 : bool operator== (const ScopeId &rhs) const { return value == rhs.value; }
174 61 : 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 273 : 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 47 : 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 47 : IndexVec () = default;
212 : // Creates `size` elements, instead of only reserving space.
213 4 : IndexVec (size_t size) : internal_vector (size) {}
214 :
215 739 : T &at (I pid) { return internal_vector[pid.value]; }
216 3014 : const T &at (I pid) const { return internal_vector[pid.value]; }
217 1353 : T &operator[] (I pid) { return internal_vector[pid.value]; }
218 208 : const T &operator[] (I pid) const { return internal_vector[pid.value]; }
219 :
220 204 : void push_back (T &¶m) { internal_vector.push_back (std::move (param)); }
221 542 : template <typename... Args> void emplace_back (Args &&...args)
222 : {
223 80 : internal_vector.emplace_back (std::forward<Args> (args)...);
224 : }
225 :
226 2663 : size_type size () const
227 : {
228 2875 : rust_assert (internal_vector.size () < MAX_INDEX);
229 2663 : return static_cast<size_type> (internal_vector.size ());
230 : }
231 :
232 55 : std::vector<T> &get_vector () { return internal_vector; }
233 : };
234 :
235 : using Scopes = IndexVec<ScopeId, Scope>;
236 : using Loans = IndexVec<LoanId, Loan>;
237 : using Places = IndexVec<PlaceId, Place>;
238 :
239 : /** Allocated places and keeps track of paths. */
240 : class PlaceDB
241 : {
242 : private:
243 : // Possible optimizations: separate variables to speedup lookup.
244 : Places places;
245 : std::unordered_map<TyTy::BaseType *, PlaceId> constants_lookup;
246 : Scopes scopes;
247 : ScopeId current_scope = ROOT_SCOPE;
248 :
249 : Loans loans;
250 :
251 : FreeRegion next_free_region = {1};
252 :
253 : public:
254 47 : PlaceDB ()
255 47 : {
256 : // Reserved index for invalid place.
257 47 : places.push_back ({Place::INVALID, 0, {}, false, nullptr});
258 :
259 47 : scopes.emplace_back (); // Root scope.
260 47 : }
261 :
262 739 : Place &operator[] (PlaceId id) { return places.at (id); }
263 2866 : const Place &operator[] (PlaceId id) const { return places.at (id); }
264 :
265 870 : size_t size () const { return places.size (); }
266 :
267 173 : const Loans &get_loans () const { return loans; }
268 190 : const Loan &get_loan (LoanId loan_id) const { return loans.at (loan_id); }
269 :
270 117 : ScopeId get_current_scope_id () const { return current_scope; }
271 :
272 : const Scopes &get_scopes () const { return scopes; }
273 :
274 55 : const Scope &get_current_scope () const { return scopes[current_scope]; }
275 :
276 12 : const Scope &get_scope (ScopeId id) const { return scopes[id]; }
277 :
278 68 : FreeRegion get_next_free_region ()
279 : {
280 68 : ++next_free_region.value;
281 68 : return {next_free_region.value - 1};
282 : }
283 :
284 47 : FreeRegion peek_next_free_region () const { return next_free_region; }
285 :
286 47 : FreeRegion &expose_next_free_region () { return next_free_region; }
287 :
288 57 : ScopeId push_new_scope ()
289 : {
290 57 : ScopeId new_scope = {scopes.size ()};
291 57 : scopes.emplace_back ();
292 57 : scopes[new_scope].parent = current_scope;
293 57 : scopes[current_scope].children.push_back (new_scope);
294 57 : current_scope = new_scope;
295 57 : return new_scope;
296 : }
297 :
298 57 : ScopeId pop_scope ()
299 : {
300 2 : current_scope = scopes[current_scope].parent;
301 2 : return current_scope;
302 : }
303 :
304 358 : PlaceId add_place (Place &&place, PlaceId last_sibling = INVALID_PLACE)
305 : {
306 358 : places.emplace_back (std::forward<Place &&> (place));
307 358 : PlaceId new_place = {places.size () - 1};
308 358 : Place &new_place_ref = places[new_place]; // Intentional shadowing.
309 358 : if (last_sibling == INVALID_PLACE)
310 358 : places[new_place_ref.path.parent].path.first_child = new_place;
311 : else
312 0 : places[last_sibling].path.next_sibling = new_place;
313 :
314 358 : if (new_place_ref.kind == Place::VARIABLE
315 358 : || new_place_ref.kind == Place::TEMPORARY)
316 231 : scopes[current_scope].locals.push_back (new_place);
317 :
318 358 : auto variances = Resolver::TypeCheckContext::get ()
319 358 : ->get_variance_analysis_ctx ()
320 358 : .query_type_variances (new_place_ref.tyty);
321 358 : FreeRegions regions;
322 482 : for (size_t i = 0; i < variances.size (); ++i)
323 : {
324 124 : regions.push_back (next_free_region);
325 124 : ++next_free_region.value;
326 : }
327 :
328 358 : new_place_ref.regions = regions;
329 :
330 358 : return new_place;
331 358 : }
332 :
333 136 : PlaceId add_variable (NodeId id, TyTy::BaseType *tyty)
334 : {
335 136 : return add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty},
336 136 : INVALID_PLACE);
337 : }
338 :
339 29 : WARN_UNUSED_RESULT PlaceId lookup_or_add_path (Place::Kind kind,
340 : TyTy::BaseType *tyty,
341 : PlaceId parent, size_t id = 0)
342 : {
343 29 : PlaceId current = INVALID_PLACE;
344 29 : if (parent.value < places.size ())
345 : {
346 29 : current = places[parent].path.first_child;
347 29 : while (current != INVALID_PLACE)
348 : {
349 2 : if (places[current].kind == kind
350 2 : && places[current].variable_or_field_index == id)
351 : {
352 2 : rust_assert (places[current].tyty->is_equal (*tyty));
353 2 : return current;
354 : }
355 0 : current = places[current].path.next_sibling;
356 : }
357 : }
358 27 : return add_place ({kind, (uint32_t) id,
359 54 : Place::Path{parent, INVALID_PLACE, INVALID_PLACE},
360 : is_type_copy (tyty), tyty},
361 : current);
362 : }
363 :
364 95 : PlaceId add_temporary (TyTy::BaseType *tyty)
365 : {
366 95 : return add_place ({Place::TEMPORARY, 0, {}, is_type_copy (tyty), tyty},
367 95 : INVALID_PLACE);
368 : }
369 :
370 100 : PlaceId get_constant (TyTy::BaseType *tyty)
371 : {
372 100 : auto lookup = constants_lookup.find (tyty);
373 100 : if (lookup != constants_lookup.end ())
374 0 : return lookup->second;
375 200 : return add_place ({Place::CONSTANT, 0, {}, is_type_copy (tyty), tyty});
376 : }
377 :
378 241 : PlaceId lookup_variable (NodeId id)
379 : {
380 241 : PlaceId current = FIRST_VARIABLE_PLACE;
381 :
382 902 : while (current.value != places.size ())
383 : {
384 766 : if (places[current].kind == Place::VARIABLE
385 766 : && places[current].variable_or_field_index == id)
386 105 : return current;
387 661 : ++current.value;
388 : }
389 136 : return INVALID_PLACE;
390 : }
391 :
392 55 : LoanId add_loan (Loan &&loan)
393 : {
394 55 : LoanId id = {loans.size ()};
395 55 : loans.push_back (std::forward<Loan &&> (loan));
396 55 : PlaceId borrowed_place = loans.get_vector ().rbegin ()->place;
397 55 : places[loans.get_vector ().rbegin ()->place].borrowed_by.push_back (id);
398 55 : if (places[borrowed_place].kind == Place::DEREF)
399 : {
400 22 : places[places[borrowed_place].path.parent].borrowed_by.push_back (id);
401 : }
402 55 : return id;
403 : }
404 :
405 85 : PlaceId get_var (PlaceId id) const
406 : {
407 85 : if (places[id].is_var ())
408 33 : return id;
409 52 : rust_assert (places[id].is_path ());
410 : PlaceId current = id;
411 111 : while (!places[current].is_var ())
412 : {
413 59 : current = places[current].path.parent;
414 : }
415 52 : return current;
416 : }
417 :
418 : void set_next_free_region (Polonius::Origin next_free_region)
419 : {
420 : this->next_free_region.value = next_free_region;
421 : }
422 :
423 103 : PlaceId lookup_or_add_variable (NodeId id, TyTy::BaseType *tyty)
424 : {
425 103 : auto lookup = lookup_variable (id);
426 103 : if (lookup != INVALID_PLACE)
427 103 : return lookup;
428 :
429 0 : return add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty});
430 : };
431 :
432 472 : template <typename FN> void for_each_path_from_root (PlaceId var, FN fn) const
433 : {
434 472 : PlaceId current = var;
435 472 : current = places[current].path.first_child;
436 499 : while (current != INVALID_PLACE)
437 : {
438 27 : fn (current);
439 27 : for_each_path_from_root (current, fn);
440 27 : current = places[current].path.next_sibling;
441 : }
442 472 : }
443 :
444 : template <typename FN>
445 502 : void for_each_path_segment (PlaceId place_id, FN fn) const
446 : {
447 502 : PlaceId current = place_id;
448 1023 : while (current != INVALID_PLACE)
449 : {
450 521 : fn (current);
451 521 : current = places[current].path.parent;
452 : }
453 502 : }
454 :
455 : private:
456 358 : static bool is_type_copy (TyTy::BaseType *ty)
457 : {
458 358 : switch (ty->get_kind ())
459 : {
460 89 : case TyTy::REF:
461 89 : return ty->as<TyTy::ReferenceType> ()->mutability () == Mutability::Imm;
462 : case TyTy::POINTER:
463 : case TyTy::SLICE:
464 : case TyTy::BOOL:
465 : case TyTy::CHAR:
466 : case TyTy::INT:
467 : case TyTy::UINT:
468 : case TyTy::FLOAT:
469 : case TyTy::USIZE:
470 : case TyTy::ISIZE:
471 : case TyTy::FNPTR:
472 : case TyTy::FNDEF:
473 : case TyTy::NEVER:
474 : return true;
475 86 : case TyTy::TUPLE:
476 86 : {
477 86 : auto &fields = ty->as<TyTy::TupleType> ()->get_fields ();
478 86 : return std::all_of (fields.begin (), fields.end (),
479 0 : [] (const TyTy::TyVar &field) {
480 0 : return is_type_copy (field.get_tyty ());
481 86 : });
482 : }
483 0 : case TyTy::ARRAY:
484 0 : {
485 0 : return is_type_copy (ty->as<TyTy::ArrayType> ()->get_element_type ());
486 : }
487 0 : case TyTy::INFER:
488 0 : case TyTy::PARAM:
489 0 : case TyTy::ERROR:
490 0 : case TyTy::STR:
491 0 : case TyTy::PLACEHOLDER:
492 0 : rust_unreachable ();
493 51 : case TyTy::ADT: // TODO: check trait
494 51 : case TyTy::PROJECTION: // TODO: DUNNO
495 51 : case TyTy::CLOSURE: // TODO: DUNNO
496 51 : case TyTy::DYNAMIC: // TODO: dunno
497 51 : case TyTy::CONST:
498 51 : case TyTy::OPAQUE:
499 51 : return false;
500 : }
501 0 : rust_unreachable ();
502 : }
503 :
504 : /** Check whether given place is not out-of-scope. */
505 : WARN_UNUSED_RESULT bool is_in_scope (PlaceId place) const
506 : {
507 : for (ScopeId scope = current_scope; scope != INVALID_SCOPE;
508 : scope = scopes[scope].parent)
509 : {
510 : auto &scope_ref = scopes[scope];
511 : if (std::find (scope_ref.locals.begin (), scope_ref.locals.end (),
512 : place)
513 : != scope_ref.locals.end ())
514 : return true;
515 : }
516 : return false;
517 : }
518 : };
519 :
520 : } // namespace BIR
521 : } // namespace Rust
522 :
523 : #endif // RUST_BIR_PLACE_H
|
