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