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