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_FACT_COLLECTOR_H
20 : #define RUST_BIR_FACT_COLLECTOR_H
21 :
22 : #include "rust-bir-visitor.h"
23 : #include "rust-bir.h"
24 : #include "rust-bir-place.h"
25 : #include "polonius/rust-polonius.h"
26 :
27 : namespace Rust {
28 : namespace BIR {
29 :
30 : enum class PointPosition : uint8_t
31 : {
32 : START,
33 : MID
34 : };
35 :
36 : class FactCollector : public Visitor
37 : {
38 : // Output.
39 : Polonius::Facts facts;
40 :
41 : // Read-only context.
42 : const PlaceDB &place_db;
43 : const BasicBlocks &basic_blocks;
44 : const PlaceId first_local;
45 : const location_t location;
46 :
47 : Resolver::TypeCheckContext &tyctx;
48 :
49 : // Collector state.
50 : BasicBlockId current_bb = ENTRY_BASIC_BLOCK;
51 : uint32_t current_stmt = 0;
52 : PlaceId lhs = INVALID_PLACE;
53 :
54 : // PlaceDB is const in this phase, so this is used to generate fresh regions.
55 : FreeRegion next_fresh_region;
56 : RegionBinder region_binder{next_fresh_region};
57 :
58 : std::vector<Polonius::Point> cfg_points_all;
59 :
60 22 : FreeRegions bind_regions (std::vector<TyTy::Region> regions,
61 : FreeRegions parent_free_regions)
62 : {
63 22 : return region_binder.bind_regions (regions, parent_free_regions);
64 : }
65 :
66 11 : FreeRegions make_fresh_regions (size_t size)
67 : {
68 11 : FreeRegions free_regions;
69 23 : for (size_t i = 0; i < size; i++)
70 12 : free_regions.push_back (region_binder.get_next_free_region ());
71 :
72 11 : return free_regions;
73 : }
74 :
75 : public:
76 36 : static Polonius::Facts collect (Function &func)
77 : {
78 36 : FactCollector collector (func);
79 36 : collector.init_universal_regions (func.universal_regions,
80 36 : func.universal_region_bounds);
81 :
82 36 : collector.visit_statemensts ();
83 36 : collector.visit_places (func.arguments);
84 :
85 36 : return std::move (collector.facts);
86 36 : }
87 :
88 : protected: // Constructor and destructor.
89 36 : explicit FactCollector (Function &func)
90 72 : : place_db (func.place_db), basic_blocks (func.basic_blocks),
91 36 : first_local (func.arguments.empty ()
92 36 : ? FIRST_VARIABLE_PLACE
93 9 : : PlaceId{func.arguments.rbegin ()->value + 1}),
94 36 : location (func.location), tyctx (*Resolver::TypeCheckContext::get ()),
95 36 : next_fresh_region (place_db.peek_next_free_region ())
96 36 : {}
97 36 : ~FactCollector () = default;
98 :
99 : protected: // Main collection entry points (for different categories).
100 36 : void init_universal_regions (
101 : const FreeRegions &universal_regions,
102 : const decltype (Function::universal_region_bounds) &universal_region_bounds)
103 : {
104 36 : size_t next_loan = place_db.get_loans ().size ();
105 36 : facts.universal_region.emplace_back (0);
106 36 : facts.placeholder.emplace_back (0, next_loan++);
107 :
108 47 : for (auto ®ion : universal_regions)
109 : {
110 11 : facts.universal_region.emplace_back (region.value);
111 11 : facts.placeholder.emplace_back (region.value, next_loan++);
112 11 : facts.known_placeholder_subset.emplace_back (0, region.value);
113 : }
114 :
115 : // Copy already collected subset facts, that are universally valid.
116 38 : for (auto &bound : universal_region_bounds)
117 2 : facts.known_placeholder_subset.emplace_back (bound.first.value,
118 2 : bound.second.value);
119 36 : }
120 :
121 36 : void visit_places (const std::vector<PlaceId> &args)
122 : {
123 371 : for (PlaceId place_id = INVALID_PLACE; place_id.value < place_db.size ();
124 : ++place_id.value)
125 : {
126 335 : auto &place = place_db[place_id];
127 :
128 335 : switch (place.kind)
129 : {
130 195 : case Place::VARIABLE:
131 195 : case Place::TEMPORARY:
132 195 : facts.path_is_var.emplace_back (place_id.value, place_id.value);
133 303 : for (auto ®ion : place.regions)
134 108 : facts.use_of_var_derefs_origin.emplace_back (place_id.value,
135 108 : region.value);
136 :
137 : // TODO: drop_of_var_derefs_origin
138 : break;
139 5 : case Place::FIELD:
140 5 : sanizite_field (place_id);
141 5 : facts.child_path.emplace_back (place_id.value,
142 5 : place.path.parent.value);
143 5 : break;
144 0 : case Place::INDEX:
145 0 : push_subset_all (place.tyty, place.regions,
146 0 : place_db[place.path.parent].regions);
147 0 : facts.child_path.emplace_back (place_id.value,
148 0 : place.path.parent.value);
149 0 : break;
150 22 : case Place::DEREF:
151 22 : sanitize_deref (place_id);
152 22 : facts.child_path.emplace_back (place_id.value,
153 22 : place.path.parent.value);
154 22 : break;
155 : case Place::CONSTANT:
156 : case Place::INVALID:
157 : break;
158 : }
159 : }
160 :
161 36 : for (PlaceId arg = PlaceId{FIRST_VARIABLE_PLACE.value + 1};
162 54 : arg < first_local; ++arg.value)
163 18 : facts.path_assigned_at_base.emplace_back (
164 18 : arg.value, get_point (ENTRY_BASIC_BLOCK, 0, PointPosition::START));
165 :
166 308 : for (PlaceId place = first_local; place.value < place_db.size ();
167 : ++place.value)
168 : {
169 272 : if (place_db[place].is_var ())
170 168 : facts.path_moved_at_base.emplace_back (
171 : place.value,
172 168 : get_point (ENTRY_BASIC_BLOCK, 0, PointPosition::START));
173 : }
174 36 : }
175 :
176 22 : void sanitize_deref (PlaceId place_id)
177 : {
178 22 : auto &place = place_db[place_id];
179 22 : auto &base = place_db[place.path.parent];
180 :
181 22 : rust_debug ("\tSanitize deref of %s", base.tyty->as_string ().c_str ());
182 :
183 22 : FreeRegions regions;
184 23 : for (auto it = base.regions.begin () + 1; it != base.regions.end (); ++it)
185 : {
186 1 : regions.push_back (*it);
187 : }
188 22 : push_subset_all (place.tyty, regions, place.regions);
189 22 : }
190 5 : void sanizite_field (PlaceId place_id)
191 : {
192 5 : auto &place = place_db[place_id];
193 5 : auto &base = place_db[place.path.parent];
194 :
195 5 : rust_debug ("\tSanitize field .%d of %s", place.variable_or_field_index,
196 : base.tyty->as_string ().c_str ());
197 :
198 5 : if (base.tyty->is<TyTy::TupleType> ())
199 0 : return;
200 5 : auto r = Resolver::TypeCheckContext::get ()
201 5 : ->get_variance_analysis_ctx ()
202 5 : .query_field_regions (base.tyty->as<TyTy::ADTType> (), 0,
203 5 : place.variable_or_field_index,
204 5 : base.regions); // FIXME
205 5 : push_subset_all (place.tyty, r, place.regions);
206 5 : }
207 :
208 36 : void visit_statemensts ()
209 : {
210 36 : rust_debug ("visit_statemensts");
211 :
212 36 : for (current_bb = ENTRY_BASIC_BLOCK;
213 100 : current_bb.value < basic_blocks.size (); ++current_bb.value)
214 : {
215 64 : auto &bb = basic_blocks[current_bb];
216 696 : for (current_stmt = 0; current_stmt < bb.statements.size ();
217 632 : ++current_stmt)
218 : {
219 1264 : cfg_points_all.push_back (get_current_point_start ());
220 1264 : cfg_points_all.push_back (get_current_point_mid ());
221 :
222 632 : add_stmt_to_cfg (current_bb, current_stmt);
223 :
224 632 : visit (bb.statements[current_stmt]);
225 : }
226 : }
227 36 : current_bb = ENTRY_BASIC_BLOCK;
228 36 : current_stmt = 0;
229 36 : }
230 :
231 632 : void visit (const Statement &stmt) override
232 : {
233 632 : switch (stmt.get_kind ())
234 : {
235 185 : case Statement::Kind::ASSIGNMENT:
236 185 : {
237 : // TODO: for unwind, must had hadning for non-panic-only assignements
238 185 : issue_write_deep (stmt.get_place ());
239 185 : visit_assignment_expr (stmt.get_place (), stmt.get_expr ());
240 185 : break;
241 : }
242 7 : case Statement::Kind::SWITCH:
243 7 : {
244 7 : issue_read_move (stmt.get_place ());
245 7 : issue_jumps ();
246 : }
247 7 : break;
248 8 : case Statement::Kind::GOTO:
249 8 : {
250 8 : issue_jumps ();
251 : }
252 8 : break;
253 38 : case Statement::Kind::RETURN:
254 38 : {
255 38 : issue_place_access (RETURN_VALUE_PLACE);
256 38 : issue_locals_dealloc ();
257 38 : break;
258 : }
259 145 : case Statement::Kind::STORAGE_DEAD:
260 145 : {
261 290 : facts.path_moved_at_base.emplace_back (stmt.get_place ().value,
262 290 : get_current_point_mid ());
263 290 : facts.var_defined_at.emplace_back (stmt.get_place ().value,
264 290 : get_current_point_mid ());
265 145 : break;
266 : }
267 159 : case Statement::Kind::STORAGE_LIVE:
268 159 : {
269 159 : issue_write_deep (stmt.get_place (), true);
270 159 : break;
271 : }
272 0 : case Statement::Kind::USER_TYPE_ASCRIPTION:
273 0 : {
274 0 : issue_user_type_constraints (stmt.get_place (), stmt.get_type ());
275 0 : break;
276 : }
277 90 : case Statement::Kind::FAKE_READ:
278 90 : {
279 90 : issue_place_access (stmt.get_place ());
280 90 : break;
281 : }
282 : }
283 632 : }
284 :
285 185 : void visit_assignment_expr (PlaceId lhs, AbstractExpr &expr)
286 : {
287 185 : this->lhs = lhs;
288 185 : expr.accept_vis (*this);
289 185 : this->lhs = INVALID_PLACE;
290 : }
291 :
292 6 : void visit (const InitializerExpr &expr) override
293 : {
294 6 : sanitize_constrains_at_init (lhs);
295 :
296 12 : for (auto init_value : expr.get_values ())
297 6 : issue_read_move (init_value);
298 6 : }
299 :
300 0 : void visit (const Operator<1> &expr) override
301 : {
302 0 : sanitize_constrains_at_init (lhs);
303 0 : issue_read_move (expr.get_operand<0> ());
304 0 : }
305 :
306 0 : void visit (const Operator<2> &expr) override
307 : {
308 0 : sanitize_constrains_at_init (lhs);
309 0 : issue_read_move (expr.get_operand<0> ());
310 0 : issue_read_move (expr.get_operand<1> ());
311 0 : }
312 :
313 55 : void visit (const BorrowExpr &expr) override
314 : {
315 55 : rust_debug ("\t_%u = BorrowExpr(_%u)", lhs.value - 1,
316 : expr.get_place ().value - 1);
317 :
318 55 : auto loan = place_db.get_loan (expr.get_loan_id ());
319 :
320 55 : auto &base_place = place_db[expr.get_place ()];
321 55 : auto &ref_place = place_db[lhs];
322 :
323 55 : issue_place_access (expr.get_place ());
324 :
325 : // See compiler/rustc_borrowck/src/type_check/mod.rs:add_reborrow_constraint
326 55 : if (base_place.kind == Place::DEREF)
327 : {
328 : // Reborrow
329 :
330 22 : auto &main_loan_place = place_db[base_place.path.parent];
331 22 : if (loan.mutability == Mutability::Mut)
332 : {
333 11 : if (!main_loan_place.tyty->as<TyTy::ReferenceType> ()
334 11 : ->is_mutable ())
335 2 : rust_error_at (location,
336 : "Cannot reborrow immutable borrow as mutable");
337 11 : issue_loan (expr.get_origin (), expr.get_loan_id ());
338 : }
339 :
340 22 : push_subset (main_loan_place.regions[0], {expr.get_origin ()});
341 : }
342 : else
343 : {
344 33 : issue_loan (expr.get_origin (), expr.get_loan_id ());
345 : }
346 :
347 55 : auto loan_regions = base_place.regions.prepend ({expr.get_origin ()});
348 55 : push_subset (ref_place.tyty, loan_regions, ref_place.regions);
349 55 : }
350 :
351 113 : void visit (const Assignment &expr) override
352 : {
353 113 : rust_debug ("\t_%u = Assignment(_%u) at %u:%u", lhs.value - 1,
354 : expr.get_rhs ().value - 1, current_bb.value, current_stmt);
355 :
356 113 : issue_read_move (expr.get_rhs ());
357 113 : push_place_subset (lhs, expr.get_rhs ());
358 113 : }
359 :
360 11 : void visit (const CallExpr &expr) override
361 : {
362 11 : rust_debug ("\t_%u = CallExpr(_%u)", lhs.value - 1,
363 : expr.get_callable ().value - 1);
364 :
365 11 : auto &return_place = place_db[lhs];
366 11 : auto &callable_place = place_db[expr.get_callable ()];
367 11 : auto callable_ty = callable_place.tyty->as<TyTy::CallableTypeInterface> ();
368 :
369 11 : issue_read_move (expr.get_callable ());
370 :
371 : // Each call needs unique regions.
372 11 : auto call_regions = make_fresh_regions (callable_place.regions.size ());
373 :
374 22 : for (size_t i = 0; i < expr.get_arguments ().size (); ++i)
375 : {
376 11 : auto arg = expr.get_arguments ().at (i);
377 11 : auto arg_regions
378 22 : = bind_regions (Resolver::TypeCheckContext::get ()
379 11 : ->get_variance_analysis_ctx ()
380 22 : .query_type_regions (
381 11 : callable_ty->get_param_type_at (i)),
382 11 : call_regions);
383 11 : issue_read_move (arg);
384 11 : push_subset (place_db[arg].tyty, place_db[arg].regions, arg_regions);
385 11 : }
386 :
387 : // sanitize return regions
388 11 : sanitize_constrains_at_init (lhs);
389 :
390 11 : auto return_regions
391 22 : = bind_regions (Resolver::TypeCheckContext::get ()
392 11 : ->get_variance_analysis_ctx ()
393 22 : .query_type_regions (
394 11 : callable_ty->as<TyTy::FnType> ()->get_return_type ()),
395 11 : call_regions);
396 11 : push_subset (return_place.tyty, return_regions, return_place.regions);
397 :
398 11 : issue_jumps ();
399 11 : }
400 :
401 : protected: // Statement visitor helpers
402 26 : WARN_UNUSED_RESULT const BasicBlock &get_current_bb () const
403 : {
404 26 : return basic_blocks[current_bb];
405 : }
406 :
407 : WARN_UNUSED_RESULT static Polonius::Point
408 4196 : get_point (BasicBlockId bb, uint32_t stmt, PointPosition pos)
409 : {
410 4196 : Polonius::Point point = 0;
411 4196 : point |= (bb.value << 16);
412 4196 : point |= (stmt << 1);
413 4196 : point |= (static_cast<uint8_t> (pos) & 1);
414 4196 : return point;
415 : }
416 :
417 805 : WARN_UNUSED_RESULT Polonius::Point get_current_point_start () const
418 : {
419 632 : return get_point (current_bb, current_stmt, PointPosition::START);
420 : }
421 :
422 2191 : WARN_UNUSED_RESULT Polonius::Point get_current_point_mid () const
423 : {
424 777 : return get_point (current_bb, current_stmt, PointPosition::MID);
425 : }
426 :
427 632 : void add_stmt_to_cfg (BasicBlockId bb, uint32_t stmt)
428 : {
429 632 : if (stmt != 0)
430 : {
431 1136 : facts.cfg_edge.emplace_back (get_point (bb, stmt - 1,
432 : PointPosition::MID),
433 568 : get_point (bb, stmt,
434 : PointPosition::START));
435 : }
436 :
437 1264 : facts.cfg_edge.emplace_back (get_point (bb, stmt, PointPosition::START),
438 632 : get_point (bb, stmt, PointPosition::MID));
439 632 : }
440 :
441 : protected: // Generic BIR operations.
442 26 : void issue_jumps ()
443 : {
444 59 : for (auto succ : get_current_bb ().successors)
445 66 : facts.cfg_edge.emplace_back (get_current_point_mid (),
446 33 : get_point (succ, 0, PointPosition::START));
447 26 : }
448 :
449 : /* Shallow r/w access */
450 331 : void issue_place_access (PlaceId place_id)
451 : {
452 331 : auto &place = place_db[place_id];
453 :
454 331 : if (place.is_constant ())
455 : return;
456 :
457 233 : if (place_id != RETURN_VALUE_PLACE)
458 194 : facts.path_accessed_at_base.emplace_back (place_id.value,
459 194 : get_current_point_mid ());
460 :
461 233 : if (place.is_var ())
462 209 : facts.var_used_at.emplace_back (place_id.value, get_current_point_mid ());
463 24 : else if (place.is_path ())
464 : {
465 24 : facts.var_used_at.emplace_back (place_db.get_var (place_id).value,
466 48 : get_current_point_mid ());
467 : }
468 : }
469 :
470 : /** Deep read access, which consumes the place. */
471 148 : void issue_read_move (PlaceId place_id)
472 : {
473 148 : auto &place = place_db[place_id];
474 :
475 148 : issue_place_access (place_id);
476 148 : if (place.should_be_moved ())
477 : {
478 46 : issue_move (place_id);
479 : }
480 : else
481 : {
482 102 : check_read_for_conflicts (place_id);
483 : }
484 148 : }
485 :
486 344 : void issue_write_deep (PlaceId place_id, bool is_init = false)
487 : {
488 344 : auto &place = place_db[place_id];
489 459 : rust_assert (place.is_lvalue () || place.is_rvalue ());
490 :
491 344 : if (place.is_var ())
492 343 : facts.var_defined_at.emplace_back (place_id.value,
493 343 : get_current_point_mid ());
494 :
495 344 : if (!is_init)
496 : {
497 185 : facts.path_assigned_at_base.emplace_back (place_id.value,
498 185 : get_current_point_mid ());
499 185 : check_write_for_conflict (place_id);
500 185 : kill_borrows_for_place (place_id);
501 : }
502 344 : }
503 :
504 46 : void issue_move (PlaceId place_id, bool initial = false)
505 : {
506 46 : if (!place_db[place_id].should_be_moved ())
507 : return;
508 :
509 92 : facts.path_moved_at_base.emplace_back (place_id.value,
510 : initial
511 92 : ? get_point (ENTRY_BASIC_BLOCK, 0,
512 : PointPosition::START)
513 46 : : get_current_point_mid ());
514 :
515 46 : check_move_behind_reference (place_id);
516 :
517 46 : if (!initial)
518 : {
519 46 : check_write_for_conflict (place_id);
520 46 : kill_borrows_for_place (place_id);
521 : }
522 : }
523 :
524 44 : void issue_loan (Polonius::Origin origin, LoanId loan_id)
525 : {
526 44 : facts.loan_issued_at.emplace_back (origin, loan_id.value,
527 44 : get_current_point_mid ());
528 :
529 44 : check_for_borrow_conficts (place_db.get_loan (loan_id).place, loan_id,
530 44 : place_db.get_loan (loan_id).mutability);
531 44 : }
532 :
533 38 : void issue_locals_dealloc ()
534 : {
535 99 : for (LoanId loan_id = {0}; loan_id.value < place_db.get_loans ().size ();
536 : ++loan_id.value)
537 : {
538 61 : auto &loan = place_db.get_loan (loan_id);
539 61 : auto loaned_var_id = place_db.get_var (loan.place);
540 61 : if (place_db[loaned_var_id].tyty->is<TyTy::ReferenceType> ())
541 26 : continue;
542 35 : if (loaned_var_id >= first_local)
543 35 : facts.loan_invalidated_at.emplace_back (get_current_point_start (),
544 : loan_id.value);
545 : }
546 38 : }
547 :
548 0 : void issue_user_type_constraints (PlaceId place_id, TyTy::BaseType *type)
549 : {
550 0 : auto user_regions = Resolver::TypeCheckContext::get ()
551 0 : ->get_variance_analysis_ctx ()
552 0 : .query_type_regions (type);
553 0 : push_subset_user (place_db[place_id].tyty, place_db[place_id].regions,
554 : user_regions);
555 0 : }
556 :
557 102 : void check_read_for_conflicts (PlaceId place_id)
558 : {
559 102 : place_db.for_each_path_segment (place_id, [&] (PlaceId id) {
560 105 : for (auto loan : place_db[id].borrowed_by)
561 : {
562 3 : if (place_db.get_loan (loan).mutability == Mutability::Mut)
563 : {
564 3 : facts.loan_invalidated_at.emplace_back (
565 3 : get_current_point_start (), loan.value);
566 : }
567 : }
568 102 : });
569 102 : place_db.for_each_path_from_root (place_id, [&] (PlaceId id) {
570 0 : for (auto loan : place_db[id].borrowed_by)
571 : {
572 0 : if (place_db.get_loan (loan).mutability == Mutability::Mut)
573 : {
574 0 : facts.loan_invalidated_at.emplace_back (
575 0 : get_current_point_start (), loan.value);
576 : }
577 : }
578 0 : });
579 102 : }
580 :
581 231 : void check_write_for_conflict (PlaceId place_id)
582 : {
583 231 : place_db.for_each_path_segment (place_id, [&] (PlaceId id) {
584 294 : for (auto loan : place_db[id].borrowed_by)
585 59 : facts.loan_invalidated_at.emplace_back (get_current_point_start (),
586 : loan.value);
587 235 : });
588 231 : place_db.for_each_path_from_root (place_id, [&] (PlaceId id) {
589 51 : for (auto loan : place_db[id].borrowed_by)
590 24 : facts.loan_invalidated_at.emplace_back (get_current_point_start (),
591 : loan.value);
592 27 : });
593 231 : }
594 :
595 44 : void check_for_borrow_conficts (PlaceId place_id, LoanId loan,
596 : Mutability mutability)
597 : {
598 44 : place_db.for_each_path_segment (place_id, [&] (PlaceId id) {
599 131 : for (auto other_loan : place_db[id].borrowed_by)
600 : {
601 98 : if (mutability == Mutability::Imm
602 75 : && place_db.get_loan (other_loan).mutability == Mutability::Imm)
603 23 : continue;
604 : else
605 52 : facts.loan_invalidated_at.emplace_back (get_current_point_start (),
606 : other_loan.value);
607 : }
608 56 : });
609 :
610 44 : place_db.for_each_path_from_root (place_id, [&] (PlaceId id) {
611 0 : for (auto other_loan : place_db[id].borrowed_by)
612 : {
613 0 : if (mutability == Mutability::Imm
614 0 : && place_db.get_loan (other_loan).mutability == Mutability::Imm)
615 0 : continue;
616 : else
617 0 : facts.loan_invalidated_at.emplace_back (get_current_point_start (),
618 : other_loan.value);
619 : }
620 0 : });
621 44 : }
622 :
623 46 : void check_move_behind_reference (PlaceId place_id)
624 : {
625 46 : place_db.for_each_path_segment (place_id, [&] (PlaceId id) {
626 49 : if (id == place_id)
627 : return;
628 3 : if (place_db[id].kind == Place::DEREF)
629 1 : rust_error_at (location, "Cannot move from behind a reference.");
630 : });
631 46 : }
632 :
633 231 : void kill_borrows_for_place (PlaceId place_id)
634 : {
635 231 : auto &place = place_db[place_id];
636 288 : for (auto loan : place.borrowed_by)
637 : {
638 : // TODO: this is more complicated, see
639 : // compiler/rustc_borrowck/src/constraint_generation.rs:176
640 57 : facts.loan_killed_at.emplace_back (loan.value,
641 57 : get_current_point_mid ());
642 : }
643 231 : }
644 :
645 : protected: // Subset helpers.
646 134 : void push_subset (FreeRegion lhs, FreeRegion rhs)
647 : {
648 134 : rust_debug ("\t\tpush_subset: '?%lu: '?%lu", (unsigned long) lhs.value,
649 : (unsigned long) rhs.value);
650 :
651 134 : facts.subset_base.emplace_back (lhs.value, rhs.value,
652 134 : get_current_point_mid ());
653 134 : }
654 :
655 4 : void push_subset_all (FreeRegion lhs, FreeRegion rhs)
656 : {
657 4 : rust_debug ("\t\tpush_subset_all: '?%lu: '?%lu", (unsigned long) lhs.value,
658 : (unsigned long) rhs.value);
659 :
660 194 : for (auto point : cfg_points_all)
661 190 : facts.subset_base.emplace_back (lhs.value, rhs.value, point);
662 4 : }
663 :
664 111 : void push_subset (Variance variance, FreeRegion lhs, FreeRegion rhs)
665 : {
666 111 : if (variance.is_covariant ())
667 111 : push_subset (lhs, rhs);
668 0 : else if (variance.is_contravariant ())
669 0 : push_subset (rhs, lhs);
670 0 : else if (variance.is_invariant ())
671 : {
672 0 : push_subset (lhs, rhs);
673 0 : push_subset (rhs, lhs);
674 : }
675 111 : }
676 :
677 4 : void push_subset_all (Variance variance, FreeRegion lhs, FreeRegion rhs)
678 : {
679 4 : if (variance.is_covariant ())
680 4 : push_subset_all (lhs, rhs);
681 0 : else if (variance.is_contravariant ())
682 0 : push_subset_all (rhs, lhs);
683 0 : else if (variance.is_invariant ())
684 : {
685 0 : push_subset_all (lhs, rhs);
686 0 : push_subset_all (rhs, lhs);
687 : }
688 4 : }
689 :
690 113 : void push_place_subset (PlaceId lhs, PlaceId rhs)
691 : {
692 113 : auto &lhs_place = place_db[lhs];
693 113 : auto &rhs_place = place_db[rhs];
694 :
695 113 : push_subset (lhs_place.tyty, rhs_place.regions, lhs_place.regions);
696 113 : }
697 :
698 190 : void push_subset (TyTy::BaseType *type, FreeRegions lhs, FreeRegions rhs)
699 : {
700 190 : auto variances = Resolver::TypeCheckContext::get ()
701 190 : ->get_variance_analysis_ctx ()
702 190 : .query_type_variances (type);
703 190 : rust_assert (lhs.size () == rhs.size ());
704 190 : rust_assert (lhs.size () == variances.size ());
705 301 : for (size_t i = 0; i < lhs.size (); ++i)
706 111 : push_subset (variances[i], lhs[i], rhs[i]);
707 190 : }
708 :
709 27 : void push_subset_all (TyTy::BaseType *type, FreeRegions lhs, FreeRegions rhs)
710 : {
711 27 : auto variances = Resolver::TypeCheckContext::get ()
712 27 : ->get_variance_analysis_ctx ()
713 27 : .query_type_variances (type);
714 27 : rust_assert (lhs.size () == rhs.size ());
715 27 : rust_assert (lhs.size () == variances.size ());
716 31 : for (size_t i = 0; i < lhs.size (); ++i)
717 4 : push_subset_all (variances[i], lhs[i], rhs[i]);
718 27 : }
719 :
720 0 : void push_subset_user (TyTy::BaseType *type, FreeRegions free_regions,
721 : std::vector<TyTy::Region> user_regions)
722 : {
723 0 : auto variances = Resolver::TypeCheckContext::get ()
724 0 : ->get_variance_analysis_ctx ()
725 0 : .query_type_variances (type);
726 0 : rust_assert (free_regions.size () == user_regions.size ());
727 0 : rust_assert (free_regions.size () == variances.size ());
728 :
729 0 : for (size_t i = 0; i < free_regions.size (); ++i)
730 : {
731 0 : if (user_regions[i].is_named ())
732 0 : push_subset (variances[i], free_regions[i],
733 0 : {Polonius::Origin (user_regions[i].get_index ())});
734 0 : else if (user_regions[i].is_anonymous ())
735 : {
736 : // IGNORE
737 : }
738 : else
739 0 : rust_internal_error_at (UNKNOWN_LOCATION, "Unexpected region type");
740 : }
741 0 : }
742 :
743 : /**
744 : * Apply type and lifetime bounds
745 : *
746 : * For a place we have a list of fresh regions. We need to apply constraints
747 : * from type definition to it. First `n` regions belong to the lifetime
748 : * parameters of the type. The rest are flatten lifetime parameters of the
749 : * type arguments. We walk the type arguments with a offset
750 : */
751 17 : void sanitize_constrains_at_init (PlaceId place_id)
752 : {
753 17 : auto &place = place_db[place_id];
754 :
755 17 : rust_debug ("\tSanitize constraints of %s",
756 : place.tyty->as_string ().c_str ());
757 :
758 17 : if (auto generic = place.tyty->try_as<TyTy::SubstitutionRef> ())
759 : {
760 16 : auto ®ions = place.regions;
761 16 : auto region_end = sanitize_constraints (*generic, 0, regions);
762 16 : rust_assert (region_end == regions.size ());
763 : }
764 1 : else if (place.tyty->is<TyTy::ReferenceType> ())
765 : {
766 3 : for (auto ®ion : place.regions)
767 : {
768 2 : if (region != place.regions[0])
769 1 : push_subset (region, place.regions[0]);
770 : }
771 : }
772 17 : }
773 :
774 0 : size_t sanitize_constraints (const TyTy::BaseType *type, size_t region_start,
775 : const FreeRegions ®ions)
776 : {
777 0 : switch (type->get_kind ())
778 : {
779 0 : case TyTy::ADT:
780 0 : return sanitize_constraints (type->as<const TyTy::ADTType> (),
781 0 : region_start, regions);
782 : case TyTy::STR:
783 : return region_start;
784 0 : case TyTy::REF:
785 0 : return 1
786 : + sanitize_constraints (
787 0 : type->as<const TyTy::ReferenceType> ()->get_base (),
788 0 : region_start, regions);
789 0 : case TyTy::POINTER:
790 0 : return sanitize_constraints (
791 0 : type->as<const TyTy::PointerType> ()->get_base (), region_start,
792 0 : regions);
793 0 : case TyTy::ARRAY:
794 0 : return sanitize_constraints (
795 0 : type->as<const TyTy::ArrayType> ()->get_element_type (), region_start,
796 0 : regions);
797 0 : case TyTy::SLICE:
798 0 : return sanitize_constraints (
799 0 : type->as<const TyTy::SliceType> ()->get_element_type (), region_start,
800 0 : regions);
801 0 : case TyTy::FNDEF:
802 0 : case TyTy::TUPLE:
803 0 : {
804 0 : for (auto &field : type->as<const TyTy::TupleType> ()->get_fields ())
805 0 : sanitize_constraints (field.get_tyty (), region_start, regions);
806 : }
807 : break;
808 0 : case TyTy::FNPTR:
809 0 : case TyTy::PROJECTION:
810 0 : return sanitize_constraints (*type->as<const TyTy::SubstitutionRef> (),
811 0 : region_start, regions);
812 : case TyTy::BOOL:
813 : case TyTy::CHAR:
814 : case TyTy::INT:
815 : case TyTy::UINT:
816 : case TyTy::FLOAT:
817 : case TyTy::USIZE:
818 : case TyTy::ISIZE:
819 : case TyTy::NEVER:
820 : case TyTy::DYNAMIC:
821 : case TyTy::CLOSURE:
822 : case TyTy::ERROR:
823 : return region_start;
824 0 : case TyTy::PLACEHOLDER:
825 0 : case TyTy::INFER:
826 0 : case TyTy::PARAM:
827 0 : case TyTy::CONST:
828 0 : case TyTy::OPAQUE:
829 0 : rust_unreachable ();
830 : }
831 0 : rust_unreachable ();
832 : }
833 :
834 16 : size_t sanitize_constraints (const TyTy::SubstitutionRef &type,
835 : size_t region_start, const FreeRegions ®ions)
836 : {
837 16 : for (auto constr : type.get_region_constraints ().region_region)
838 : {
839 0 : rust_assert (constr.first.is_early_bound ());
840 0 : rust_assert (constr.second.is_early_bound ());
841 0 : auto lhs = constr.first.get_index () + region_start;
842 0 : auto rhs = constr.second.get_index () + region_start;
843 0 : push_subset (regions[lhs], regions[rhs]);
844 : }
845 :
846 16 : size_t region_end = region_start + type.get_num_lifetime_params ();
847 :
848 : /*
849 : * For type `Foo<'a, T1, T2>`, where `T1 = &'b Vec<&'c i32>` and `T2 = &'d
850 : * i32 the regions are `['a, 'b, 'c, 'd]`. The ranges
851 : */
852 16 : std::vector<size_t> type_param_region_ranges;
853 16 : type_param_region_ranges.push_back (region_end);
854 :
855 16 : for (auto type_param : type.get_substs ())
856 : {
857 0 : TyTy::SubstitutionArg arg = TyTy::SubstitutionArg::error ();
858 0 : bool ok = type.get_used_arguments ().get_argument_for_symbol (
859 0 : type_param.get_param_ty (), &arg);
860 0 : rust_assert (ok);
861 0 : region_end
862 0 : = sanitize_constraints (arg.get_tyty (), region_end, regions);
863 0 : type_param_region_ranges.push_back (region_end);
864 : }
865 :
866 : /*
867 : * For constrain of form: `T: 'a` push outlives with all in range
868 : * `indexof(T)..(indexof(T) + 1)`
869 : */
870 16 : for (auto constr : type.get_region_constraints ().type_region)
871 : {
872 0 : auto type_param_index_opt
873 0 : = type.get_used_arguments ().find_symbol (*constr.first);
874 0 : rust_assert (type_param_index_opt.has_value ());
875 0 : size_t type_param_index = type_param_index_opt.value ();
876 :
877 0 : for (size_t i = type_param_region_ranges[type_param_index];
878 0 : i < type_param_region_ranges[type_param_index + 1]; ++i)
879 : {
880 0 : push_subset (regions[i],
881 0 : regions[constr.second.get_index () + region_start]);
882 : }
883 : }
884 :
885 16 : return region_end;
886 16 : }
887 : };
888 :
889 : } // namespace BIR
890 : } // namespace Rust
891 :
892 : #endif // RUST_BIR_FACT_COLLECTOR_H
|
