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