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 : 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
|
