From patchwork Thu Aug 1 14:57:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Arthur Cohen X-Patchwork-Id: 1967858 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; unprotected) header.d=embecosm.com header.i=@embecosm.com header.a=rsa-sha256 header.s=google header.b=K5DvZfJe; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=server2.sourceware.org; envelope-from=gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=patchwork.ozlabs.org) Received: from server2.sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4WZY6m2qtJz1ybX for ; Fri, 2 Aug 2024 01:39:28 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9293F384A80C for ; Thu, 1 Aug 2024 15:39:26 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com [IPv6:2a00:1450:4864:20::62b]) by sourceware.org (Postfix) with ESMTPS id E17823861827 for ; Thu, 1 Aug 2024 15:00:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E17823861827 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=embecosm.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=embecosm.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org E17823861827 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::62b ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722524504; cv=none; b=pyTYMRCX38RNEbuuylQgnEyp64IBKW8bCMIE3x2Rvsk0Cer2CONZkpYvJzzeny7GeRBP9hbcGM1uCmMy/Juj8J3/0jM1k8QhyMV+fhNZUuXheMlI4ifNIy+U72KfyipdRYWsCG7CMWnjq/YIDwsoxkmg56nKZszLsDa3m+fW1n8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722524504; c=relaxed/simple; bh=80TeaoUWVoJ4YwvTQeGWNeygfTD+rJ8bmxBOxcjFQVE=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=Zdo7r5Ndg/ZPKNPvxbKCdMvCEmH88K08TpIXvgHZFYoUYZzyzc2BtByqznV+cr7BNYg9AzX+TkXwy/tK8uGPx8RdFx93+Tw7MHCVJsny/Z4E5A0XUHJZyGlNbxknRJE5XdXGgt+j4HmkDCdtx0MIGUkndQQxvzdQ+biKh45M1w4= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ej1-x62b.google.com with SMTP id a640c23a62f3a-a7ab76558a9so386533166b.1 for ; Thu, 01 Aug 2024 08:00:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=embecosm.com; s=google; t=1722524455; x=1723129255; darn=gcc.gnu.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=a5i3OTM6r36lb0vy2nA+ly8nbYJJxJSLxUdImm8ji8Q=; b=K5DvZfJeBGUXgyqcRRZw8zwYXIyv5ANpqCtW9D8qBITRIKFmCk0QjIgnHG5R8xlTBL JZJUk1ykVJmUZ6mmZ12faXBz+QbLn8yChDJ80xTIK7cJShNGbajMxXwrEEwlB2g6k2KD a9Q+4jvyCvfveoX8RrM+5IpU7VKa9h9adD6eqmE9x7wHCMRCz+dmvSHsYQr+KyDR/aha J1jL2bcnGYQgwW+9J/rXGn7q1qGtmF2eVMz29k/Gy7LfT604afH/We+FEbouXsIxp7Cw qAz7oEeFJEqsLtjaJ71JpwJIG4+kcyIanKaGRSM5LzFS2K8v99HEma2h+0ByozhSX/a0 KCkQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722524455; x=1723129255; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=a5i3OTM6r36lb0vy2nA+ly8nbYJJxJSLxUdImm8ji8Q=; b=jXmbutIoVqSsumLE5rofNDDIiBDB2aFr5yb2YdtJ4lFSYmgBMRJX+2xz/SswRQRB1K x/5WmktH2C+jgafcz9ismqzepyZIgL74GRf0E+aofhWf8li8a8sr+aRAvwXsSyCDE1JY i5NSVJFyIxoKApIj28/a5IdEi/ySQcjP0ppoeMXUu4R6UW5BRnEKm7/qf3iP/ghMIfOs YxqCwTRX+qKPJK4j1U6Pque39mLbLxphWr1wB4Kc36EMppisqETr5mPHImv14lnVzjUg uhZ8ko3fVJ5KYYFMYQC2Cn8O+XjFAgvwFvVPeks3qXrqgAPUDMPJPWYbrhyw4Zw3cWpw 9XCA== X-Gm-Message-State: AOJu0Yw7XvMzY/ryNZ/T3/OtdBROQqUFsMs+j912J6T5OHNWXF5GlwCC MrLs9+otnq6AmD4Ku6Fi5fJIdKWGxNF00EsmL/ZfjMJDa1szH+idkpyBgwHps1vcmkT5D7SlXjk RNlBe X-Google-Smtp-Source: AGHT+IFdhiboTOu2Jj7blbfRf9nJPolCcUiYHLaRmJTt4IsXmjagCI0dhfF1ZRXptOYL1bqRQgTQbg== X-Received: by 2002:a17:907:868d:b0:a77:cdae:6a59 with SMTP id a640c23a62f3a-a7dbe6302e4mr150482466b.21.1722524455048; Thu, 01 Aug 2024 08:00:55 -0700 (PDT) Received: from platypus.lan ([2a04:cec2:9:dc84:3622:6733:ff49:ee91]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5ac63590592sm10252456a12.25.2024.08.01.08.00.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Aug 2024 08:00:54 -0700 (PDT) From: Arthur Cohen To: gcc-patches@gcc.gnu.org Cc: gcc-rust@gcc.gnu.org, Jakub Dupak Subject: [PATCH 121/125] gccrs: borrowck: Fact collector Date: Thu, 1 Aug 2024 16:57:57 +0200 Message-ID: <20240801145809.366388-123-arthur.cohen@embecosm.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240801145809.366388-2-arthur.cohen@embecosm.com> References: <20240801145809.366388-2-arthur.cohen@embecosm.com> MIME-Version: 1.0 X-Spam-Status: No, score=-14.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces~incoming=patchwork.ozlabs.org@gcc.gnu.org From: Jakub Dupak This is the main Polonius based logic which creates the information Polonius needs from BIR. It is largly guessed and rever engineered, so some aspects are probably wrong. gcc/rust/ChangeLog: * checks/errors/borrowck/rust-bir-fact-collector.h: New file. * checks/errors/borrowck/rust-borrow-checker.cc (BorrowChecker::go): Enable fact collection. Signed-off-by: Jakub Dupak --- .../errors/borrowck/rust-bir-fact-collector.h | 895 ++++++++++++++++++ .../errors/borrowck/rust-borrow-checker.cc | 3 + 2 files changed, 898 insertions(+) create mode 100644 gcc/rust/checks/errors/borrowck/rust-bir-fact-collector.h diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-fact-collector.h b/gcc/rust/checks/errors/borrowck/rust-bir-fact-collector.h new file mode 100644 index 00000000000..17c198e0fa7 --- /dev/null +++ b/gcc/rust/checks/errors/borrowck/rust-bir-fact-collector.h @@ -0,0 +1,895 @@ +// Copyright (C) 2020-2023 Free Software Foundation, Inc. + +// This file is part of GCC. + +// GCC is free software; you can redistribute it and/or modify it under +// the terms of the GNU General Public License as published by the Free +// Software Foundation; either version 3, or (at your option) any later +// version. + +// GCC is distributed in the hope that it will be useful, but WITHOUT ANY +// WARRANTY; without even the implied warranty of MERCHANTABILITY or +// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +// for more details. + +// You should have received a copy of the GNU General Public License +// along with GCC; see the file COPYING3. If not see +// . + +#ifndef RUST_BIR_FACT_COLLECTOR_H +#define RUST_BIR_FACT_COLLECTOR_H + +#include "rust-bir-visitor.h" +#include "rust-bir.h" +#include "rust-bir-place.h" +#include "polonius/rust-polonius.h" + +namespace Rust { +namespace BIR { + +enum class PointPosition : uint8_t +{ + START, + MID +}; + +class FactCollector : public Visitor +{ + // Output. + Polonius::Facts facts; + + // Read-only context. + const PlaceDB &place_db; + const std::vector &basic_blocks; + const PlaceId first_local; + const location_t location; + + Resolver::TypeCheckContext &tyctx; + + // Collector state. + BasicBlockId current_bb = 0; + uint32_t current_stmt = 0; + PlaceId lhs = INVALID_PLACE; + + // PlaceDB is const in this phase, so this is used to generate fresh regions. + FreeRegion next_fresh_region; + RegionBinder region_binder{next_fresh_region}; + + std::vector cfg_points_all; + + FreeRegions bind_regions (std::vector regions, + FreeRegions parent_free_regions) + { + return region_binder.bind_regions (regions, parent_free_regions); + } + + FreeRegions make_fresh_regions (size_t size) + { + std::vector free_regions; + for (size_t i = 0; i < size; i++) + { + free_regions.push_back (region_binder.get_next_free_region ()); + } + return FreeRegions (std::move (free_regions)); + } + +public: + static Polonius::Facts collect (Function &func) + { + FactCollector collector (func); + collector.init_universal_regions (func.universal_regions, + func.universal_region_bounds); + + collector.visit_statemensts (); + collector.visit_places (func.arguments); + + return std::move (collector.facts); + } + +protected: // Constructor and destructor. + explicit FactCollector (Function &func) + : place_db (func.place_db), basic_blocks (func.basic_blocks), + first_local (func.arguments.empty () ? FIRST_VARIABLE_PLACE + : *func.arguments.rbegin () + 1), + location (func.location), tyctx (*Resolver::TypeCheckContext::get ()), + next_fresh_region (place_db.peek_next_free_region ()) + {} + ~FactCollector () = default; + +protected: // Main collection entry points (for different categories). + void init_universal_regions ( + const FreeRegions &universal_regions, + const decltype (Function::universal_region_bounds) &universal_region_bounds) + { + size_t next_loan = place_db.get_loans ().size (); + facts.universal_region.emplace_back (0); + facts.placeholder.emplace_back (0, next_loan++); + + for (auto ®ion : universal_regions) + { + facts.universal_region.emplace_back (region); + facts.placeholder.emplace_back (region, next_loan++); + facts.known_placeholder_subset.emplace_back (0, region); + } + + // Copy already collected subset facts, that are universally valid. + for (auto &bound : universal_region_bounds) + facts.known_placeholder_subset.emplace_back (bound.first, bound.second); + } + + void visit_places (const std::vector &args) + { + for (PlaceId place_id = 0; place_id < place_db.size (); ++place_id) + { + auto &place = place_db[place_id]; + + switch (place.kind) + { + case Place::VARIABLE: + case Place::TEMPORARY: + facts.path_is_var.emplace_back (place_id, place_id); + for (auto ®ion : place.regions) + { + facts.use_of_var_derefs_origin.emplace_back (place_id, region); + } + // TODO: drop_of_var_derefs_origin + break; + case Place::FIELD: + sanizite_field (place_id); + facts.child_path.emplace_back (place_id, place.path.parent); + break; + case Place::INDEX: + push_subset_all (place.tyty, place.regions, + place_db[place.path.parent].regions); + facts.child_path.emplace_back (place_id, place.path.parent); + break; + case Place::DEREF: + sanitize_deref (place_id); + facts.child_path.emplace_back (place_id, place.path.parent); + break; + case Place::CONSTANT: + case Place::INVALID: + break; + } + } + + for (PlaceId arg = FIRST_VARIABLE_PLACE + 1; arg < first_local; ++arg) + { + facts.path_assigned_at_base.emplace_back ( + arg, get_point (0, 0, PointPosition::START)); + } + for (PlaceId place = first_local; place < place_db.size (); ++place) + { + if (place_db[place].is_var ()) + facts.path_moved_at_base.emplace_back ( + place, get_point (0, 0, PointPosition::START)); + } + } + + void sanitize_deref (PlaceId place_id) + { + auto &place = place_db[place_id]; + auto &base = place_db[place.path.parent]; + + rust_debug ("\tSanitize deref of %s", base.tyty->as_string ().c_str ()); + + std::vector regions; + regions.insert (regions.end (), base.regions.begin () + 1, + base.regions.end ()); + FreeRegions r (std::move (regions)); + push_subset_all (place.tyty, r, place.regions); + } + void sanizite_field (PlaceId place_id) + { + auto &place = place_db[place_id]; + auto &base = place_db[place.path.parent]; + + rust_debug ("\tSanitize field .%d of %s", place.variable_or_field_index, + base.tyty->as_string ().c_str ()); + + if (base.tyty->is ()) + return; + auto r = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_field_regions (base.tyty->as (), 0, + place.variable_or_field_index, + base.regions); // FIXME + FreeRegions f (std::move (r)); + push_subset_all (place.tyty, f, place.regions); + } + + void visit_statemensts () + { + rust_debug ("visit_statemensts"); + + for (current_bb = 0; current_bb < basic_blocks.size (); ++current_bb) + { + auto &bb = basic_blocks[current_bb]; + for (current_stmt = 0; current_stmt < bb.statements.size (); + ++current_stmt) + { + cfg_points_all.push_back (get_current_point_start ()); + cfg_points_all.push_back (get_current_point_mid ()); + + add_stmt_to_cfg (current_bb, current_stmt); + + visit (bb.statements[current_stmt]); + } + } + current_bb = 0; + current_stmt = 0; + } + + void visit (const Statement &stmt) override + { + switch (stmt.get_kind ()) + { + case Statement::Kind::ASSIGNMENT: { + // TODO: for unwind, must had hadning for non-panic-only assignements + issue_write_deep (stmt.get_place ()); + visit_assignment_expr (stmt.get_place (), stmt.get_expr ()); + break; + } + case Statement::Kind::SWITCH: { + issue_read_move (stmt.get_place ()); + issue_jumps (); + } + break; + case Statement::Kind::GOTO: { + issue_jumps (); + } + break; + case Statement::Kind::RETURN: { + issue_place_access (RETURN_VALUE_PLACE); + issue_locals_dealloc (); + break; + } + case Statement::Kind::STORAGE_DEAD: { + facts.path_moved_at_base.emplace_back (stmt.get_place (), + get_current_point_mid ()); + facts.var_defined_at.emplace_back (stmt.get_place (), + get_current_point_mid ()); + break; + } + case Statement::Kind::STORAGE_LIVE: { + issue_write_deep (stmt.get_place (), true); + break; + } + case Statement::Kind::USER_TYPE_ASCRIPTION: { + issue_user_type_constraints (stmt.get_place (), stmt.get_type ()); + break; + } + case Statement::Kind::FAKE_READ: { + issue_place_access (stmt.get_place ()); + break; + } + } + } + + void visit_assignment_expr (PlaceId lhs, AbstractExpr &expr) + { + this->lhs = lhs; + expr.accept_vis (*this); + this->lhs = INVALID_PLACE; + } + + void visit (const InitializerExpr &expr) override + { + sanitize_constrains_at_init (lhs); + + for (auto init_value : expr.get_values ()) + issue_read_move (init_value); + } + + void visit (const Operator<1> &expr) override + { + sanitize_constrains_at_init (lhs); + issue_read_move (expr.get_operand<0> ()); + } + + void visit (const Operator<2> &expr) override + { + sanitize_constrains_at_init (lhs); + issue_read_move (expr.get_operand<0> ()); + issue_read_move (expr.get_operand<1> ()); + } + + void visit (const BorrowExpr &expr) override + { + rust_debug ("\t_%u = BorrowExpr(_%u)", lhs - 1, expr.get_place () - 1); + + auto loan = place_db.get_loans ()[expr.get_loan ()]; + + auto &base_place = place_db[expr.get_place ()]; + auto &ref_place = place_db[lhs]; + + issue_place_access (expr.get_place ()); + + // See compiler/rustc_borrowck/src/type_check/mod.rs:add_reborrow_constraint + if (base_place.kind == Place::DEREF) + { + // Reborrow + + auto &main_loan_place = place_db[base_place.path.parent]; + if (loan.mutability == Mutability::Mut) + { + if (!main_loan_place.tyty->as () + ->is_mutable ()) + rust_error_at (location, + "Cannot reborrow immutable borrow as mutable"); + issue_loan (expr.get_origin (), expr.get_loan ()); + } + + push_subset (main_loan_place.regions[0], expr.get_origin ()); + } + else + { + issue_loan (expr.get_origin (), expr.get_loan ()); + } + + auto loan_regions = base_place.regions.prepend (expr.get_origin ()); + push_subset (ref_place.tyty, loan_regions, ref_place.regions); + } + + void visit (const Assignment &expr) override + { + rust_debug ("\t_%u = Assignment(_%u) at %u:%u", lhs - 1, + expr.get_rhs () - 1, current_bb, current_stmt); + + issue_read_move (expr.get_rhs ()); + push_subset (lhs, expr.get_rhs ()); + } + + void visit (const CallExpr &expr) override + { + rust_debug ("\t_%u = CallExpr(_%u)", lhs - 1, expr.get_callable () - 1); + + auto &return_place = place_db[lhs]; + auto &callable_place = place_db[expr.get_callable ()]; + auto callable_ty = callable_place.tyty->as (); + + issue_read_move (expr.get_callable ()); + + // Each call needs unique regions. + auto call_regions = make_fresh_regions (callable_place.regions.size ()); + + for (size_t i = 0; i < expr.get_arguments ().size (); ++i) + { + auto arg = expr.get_arguments ().at (i); + auto arg_regions + = bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions ( + callable_ty->get_param_type_at (i)), + call_regions); + issue_read_move (arg); + push_subset (place_db[arg].tyty, place_db[arg].regions, arg_regions); + } + + // sanitize return regions + sanitize_constrains_at_init (lhs); + + auto return_regions + = bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions ( + callable_ty->as ()->get_return_type ()), + call_regions); + push_subset (return_place.tyty, return_regions, return_place.regions); + + issue_jumps (); + } + +protected: // Statement visitor helpers + WARN_UNUSED_RESULT const BasicBlock &get_current_bb () const + { + return basic_blocks[current_bb]; + } + + WARN_UNUSED_RESULT static Polonius::Point + get_point (BasicBlockId bb, uint32_t stmt, PointPosition pos) + { + Polonius::Point point = 0; + point |= (bb << 16); + point |= (stmt << 1); + point |= (static_cast (pos) & 1); + return point; + } + + WARN_UNUSED_RESULT Polonius::Point get_current_point_start () const + { + return get_point (current_bb, current_stmt, PointPosition::START); + } + + WARN_UNUSED_RESULT Polonius::Point get_current_point_mid () const + { + return get_point (current_bb, current_stmt, PointPosition::MID); + } + + void add_stmt_to_cfg (BasicBlockId bb, uint32_t stmt) + { + if (stmt != 0) + { + facts.cfg_edge.emplace_back (get_point (bb, stmt - 1, + PointPosition::MID), + get_point (bb, stmt, + PointPosition::START)); + } + + facts.cfg_edge.emplace_back (get_point (bb, stmt, PointPosition::START), + get_point (bb, stmt, PointPosition::MID)); + } + +protected: // Generic BIR operations. + void issue_jumps () + { + for (auto succ : get_current_bb ().successors) + facts.cfg_edge.emplace_back (get_current_point_mid (), + get_point (succ, 0, PointPosition::START)); + } + + /* Shallow r/w access */ + void issue_place_access (PlaceId place_id) + { + auto &place = place_db[place_id]; + + if (place.is_constant ()) + return; + + if (place_id != RETURN_VALUE_PLACE) + facts.path_accessed_at_base.emplace_back (place_id, + get_current_point_mid ()); + + if (place.is_var ()) + facts.var_used_at.emplace_back (place_id, get_current_point_mid ()); + else if (place.is_path ()) + { + facts.var_used_at.emplace_back (place_db.get_var (place_id), + get_current_point_mid ()); + } + } + + /** Deep read access, which consumes the place. */ + void issue_read_move (PlaceId place_id) + { + auto &place = place_db[place_id]; + + issue_place_access (place_id); + if (place.should_be_moved ()) + { + issue_move (place_id); + } + else + { + check_read_for_conflicts (place_id); + } + } + + void issue_write_deep (PlaceId place_id, bool is_init = false) + { + auto &place = place_db[place_id]; + rust_assert (place.is_lvalue () || place.is_rvalue ()); + + if (place.is_var ()) + facts.var_defined_at.emplace_back (place_id, get_current_point_mid ()); + + if (!is_init) + { + facts.path_assigned_at_base.emplace_back (place_id, + get_current_point_mid ()); + check_write_for_conflict (place_id); + kill_borrows_for_place (place_id); + } + } + + void issue_move (PlaceId place_id, bool initial = false) + { + if (!place_db[place_id].should_be_moved ()) + return; + + facts.path_moved_at_base.emplace_back ( + place_id, initial ? get_point (0, 0, PointPosition::START) + : get_current_point_mid ()); + + check_move_behind_reference (place_id); + + if (!initial) + { + check_write_for_conflict (place_id); + kill_borrows_for_place (place_id); + } + } + + void issue_loan (Polonius::Origin origin, LoanId loan_id) + { + facts.loan_issued_at.emplace_back (origin, loan_id, + get_current_point_mid ()); + + check_for_borrow_conficts (place_db.get_loans ()[loan_id].place, loan_id, + place_db.get_loans ()[loan_id].mutability); + } + + void issue_locals_dealloc () + { + for (LoanId loan_id = 0; loan_id < place_db.get_loans ().size (); ++loan_id) + { + auto &loan = place_db.get_loans ()[loan_id]; + auto loaned_var_id = place_db.get_var (loan.place); + if (place_db[loaned_var_id].tyty->is ()) + continue; + if (loaned_var_id >= first_local) + facts.loan_invalidated_at.emplace_back (get_current_point_start (), + loan_id); + } + } + + void issue_user_type_constraints (PlaceId place_id, TyTy::BaseType *type) + { + auto user_regions = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions (type); + push_subset_user (place_db[place_id].tyty, place_db[place_id].regions, + user_regions); + } + + void check_read_for_conflicts (PlaceId place_id) + { + place_db.for_each_path_segment (place_id, [&] (PlaceId id) { + for (auto loan : place_db[id].borrowed_by) + { + if (place_db.get_loans ()[loan].mutability == Mutability::Mut) + { + facts.loan_invalidated_at.emplace_back ( + get_current_point_start (), loan); + } + } + }); + place_db.for_each_path_from_root (place_id, [&] (PlaceId id) { + for (auto loan : place_db[id].borrowed_by) + { + if (place_db.get_loans ()[loan].mutability == Mutability::Mut) + { + facts.loan_invalidated_at.emplace_back ( + get_current_point_start (), loan); + } + } + }); + } + + void check_write_for_conflict (PlaceId place_id) + { + place_db.for_each_path_segment (place_id, [&] (PlaceId id) { + for (auto loan : place_db[id].borrowed_by) + { + facts.loan_invalidated_at.emplace_back (get_current_point_start (), + loan); + } + }); + place_db.for_each_path_from_root (place_id, [&] (PlaceId id) { + for (auto loan : place_db[id].borrowed_by) + { + facts.loan_invalidated_at.emplace_back (get_current_point_start (), + loan); + } + }); + } + + void check_for_borrow_conficts (PlaceId place_id, LoanId loan, + Mutability mutability) + { + place_db.for_each_path_segment (place_id, [&] (PlaceId id) { + for (auto other_loan : place_db[id].borrowed_by) + { + if (mutability == Mutability::Imm + && place_db.get_loans ()[other_loan].mutability + == Mutability::Imm) + { + continue; + } + else + { + facts.loan_invalidated_at.emplace_back ( + get_current_point_start (), other_loan); + } + } + }); + + place_db.for_each_path_from_root (place_id, [&] (PlaceId id) { + for (auto other_loan : place_db[id].borrowed_by) + { + if (mutability == Mutability::Imm + && place_db.get_loans ()[other_loan].mutability + == Mutability::Imm) + { + continue; + } + else + { + facts.loan_invalidated_at.emplace_back ( + get_current_point_start (), other_loan); + } + } + }); + } + + void check_move_behind_reference (PlaceId place_id) + { + place_db.for_each_path_segment (place_id, [&] (PlaceId id) { + if (id == place_id) + return; + if (place_db[id].kind == Place::DEREF) + { + rust_error_at (location, "Cannot move from behind a reference."); + } + }); + } + + void kill_borrows_for_place (PlaceId place_id) + { + auto &place = place_db[place_id]; + for (auto loan : place.borrowed_by) + { + // TODO: this is more complicated, see + // compiler/rustc_borrowck/src/constraint_generation.rs:176 + facts.loan_killed_at.emplace_back (loan, get_current_point_mid ()); + } + } + +protected: // Subset helpers. + void push_subset (FreeRegion lhs, FreeRegion rhs) + { + rust_debug ("\t\tpush_subset: '?%lu: '?%lu", lhs, rhs); + + facts.subset_base.emplace_back (lhs, rhs, get_current_point_mid ()); + } + + void push_subset_all (FreeRegion lhs, FreeRegion rhs) + { + rust_debug ("\t\tpush_subset_all: '?%lu: '?%lu", lhs, rhs); + + for (auto point : cfg_points_all) + facts.subset_base.emplace_back (lhs, rhs, point); + } + + void push_subset (Variance variance, FreeRegion lhs, FreeRegion rhs) + { + if (variance.is_covariant ()) + { + push_subset (lhs, rhs); + } + else if (variance.is_contravariant ()) + { + push_subset (rhs, lhs); + } + else if (variance.is_invariant ()) + { + push_subset (lhs, rhs); + push_subset (rhs, lhs); + } + } + + void push_subset_all (Variance variance, FreeRegion lhs, FreeRegion rhs) + { + if (variance.is_covariant ()) + { + push_subset_all (lhs, rhs); + } + else if (variance.is_contravariant ()) + { + push_subset_all (rhs, lhs); + } + else if (variance.is_invariant ()) + { + push_subset_all (lhs, rhs); + push_subset_all (rhs, lhs); + } + } + + void push_subset (PlaceId lhs, PlaceId rhs) + { + auto &lhs_place = place_db[lhs]; + auto &rhs_place = place_db[rhs]; + + push_subset (lhs_place.tyty, rhs_place.regions, lhs_place.regions); + } + + void push_subset (TyTy::BaseType *type, FreeRegions lhs, FreeRegions rhs) + { + auto variances = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_variances (type); + rust_assert (lhs.size () == rhs.size ()); + rust_assert (lhs.size () == variances.size ()); + for (size_t i = 0; i < lhs.size (); ++i) + { + push_subset (variances[i], lhs[i], rhs[i]); + } + } + + void push_subset_all (TyTy::BaseType *type, FreeRegions lhs, FreeRegions rhs) + { + auto variances = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_variances (type); + rust_assert (lhs.size () == rhs.size ()); + rust_assert (lhs.size () == variances.size ()); + for (size_t i = 0; i < lhs.size (); ++i) + { + push_subset_all (variances[i], lhs[i], rhs[i]); + } + } + + void push_subset_user (TyTy::BaseType *type, FreeRegions free_regions, + std::vector user_regions) + { + auto variances = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_variances (type); + rust_assert (free_regions.size () == user_regions.size ()); + rust_assert (free_regions.size () == variances.size ()); + + for (size_t i = 0; i < free_regions.size (); ++i) + { + if (user_regions[i].is_named ()) + { + push_subset (variances[i], free_regions[i], + {Polonius::Origin (user_regions[i].get_index ())}); + } + else if (user_regions[i].is_anonymous ()) + { + // IGNORE + } + else + { + rust_internal_error_at (UNKNOWN_LOCATION, "Unexpected region type"); + } + } + } + + /** + * Apply type and lifetime bounds + * + * For a place we have a list of fresh regions. We need to apply constraints + * from type definition to it. First `n` regions belong to the lifetime + * parameters of the type. The rest are flatten lifetime parameters of the + * type arguments. We walk the type arguments with a offset + */ + void sanitize_constrains_at_init (PlaceId place_id) + { + auto &place = place_db[place_id]; + + rust_debug ("\tSanitize constraints of %s", + place.tyty->as_string ().c_str ()); + + if (auto generic = place.tyty->try_as ()) + { + auto ®ions = place.regions; + auto region_end = sanitize_constraints (*generic, 0, regions); + rust_assert (region_end == regions.size ()); + } + else if (place.tyty->is ()) + { + for (auto ®ion : place.regions) + { + if (region != place.regions[0]) + push_subset (region, place.regions[0]); + } + } + } + + size_t sanitize_constraints (const TyTy::BaseType *type, size_t region_start, + const FreeRegions ®ions) + { + switch (type->get_kind ()) + { + case TyTy::ADT: + return sanitize_constraints (type->as (), + region_start, regions); + case TyTy::STR: + return region_start; + case TyTy::REF: + return 1 + + sanitize_constraints ( + type->as ()->get_base (), + region_start, regions); + case TyTy::POINTER: + return sanitize_constraints ( + type->as ()->get_base (), region_start, + regions); + case TyTy::ARRAY: + return sanitize_constraints ( + type->as ()->get_element_type (), region_start, + regions); + case TyTy::SLICE: + return sanitize_constraints ( + type->as ()->get_element_type (), region_start, + regions); + case TyTy::FNDEF: + case TyTy::TUPLE: { + for (auto &field : type->as ()->get_fields ()) + sanitize_constraints (field.get_tyty (), region_start, regions); + } + break; + case TyTy::FNPTR: + case TyTy::PROJECTION: + return sanitize_constraints (*type->as (), + region_start, regions); + case TyTy::BOOL: + case TyTy::CHAR: + case TyTy::INT: + case TyTy::UINT: + case TyTy::FLOAT: + case TyTy::USIZE: + case TyTy::ISIZE: + case TyTy::NEVER: + case TyTy::DYNAMIC: + case TyTy::CLOSURE: + case TyTy::ERROR: + return region_start; + case TyTy::PLACEHOLDER: + case TyTy::INFER: + case TyTy::PARAM: + rust_unreachable (); + } + rust_unreachable (); + } + + size_t sanitize_constraints (const TyTy::SubstitutionRef &type, + size_t region_start, const FreeRegions ®ions) + { + for (auto constr : type.get_region_constraints ().region_region) + { + rust_assert (constr.first.is_early_bound ()); + rust_assert (constr.second.is_early_bound ()); + auto lhs = constr.first.get_index () + region_start; + auto rhs = constr.second.get_index () + region_start; + push_subset (regions[lhs], regions[rhs]); + } + + size_t region_end = region_start + type.get_num_lifetime_params (); + + /* + * For type `Foo<'a, T1, T2>`, where `T1 = &'b Vec<&'c i32>` and `T2 = &'d + * i32 the regions are `['a, 'b, 'c, 'd]`. The ranges + */ + std::vector type_param_region_ranges; + type_param_region_ranges.push_back (region_end); + + for (auto type_param : type.get_substs ()) + { + TyTy::SubstitutionArg arg = TyTy::SubstitutionArg::error (); + bool ok = type.get_used_arguments ().get_argument_for_symbol ( + type_param.get_param_ty (), &arg); + rust_assert (ok); + region_end + = sanitize_constraints (arg.get_tyty (), region_end, regions); + type_param_region_ranges.push_back (region_end); + } + + /* + * For constrain of form: `T: 'a` push outlives with all in range + * `indexof(T)..(indexof(T) + 1)` + */ + for (auto constr : type.get_region_constraints ().type_region) + { + auto type_param_index_opt + = type.get_used_arguments ().find_symbol (*constr.first); + rust_assert (type_param_index_opt.has_value ()); + size_t type_param_index = type_param_index_opt.value (); + + for (size_t i = type_param_region_ranges[type_param_index]; + i < type_param_region_ranges[type_param_index + 1]; ++i) + { + push_subset (regions[i], + regions[constr.second.get_index () + region_start]); + } + } + + return region_end; + } +}; // namespace BIR + +} // namespace BIR +} // namespace Rust + +#endif // RUST_BIR_FACT_COLLECTOR_H diff --git a/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc b/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc index 5daa7eb8ded..77726eb1c26 100644 --- a/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc +++ b/gcc/rust/checks/errors/borrowck/rust-borrow-checker.cc @@ -20,6 +20,7 @@ #include "rust-function-collector.h" #include "rust-bir-builder.h" #include "rust-bir-dump.h" +#include "rust-bir-fact-collector.h" namespace Rust { namespace HIR { @@ -86,6 +87,8 @@ BorrowChecker::go (HIR::Crate &crate) dump_function_bir (filename, bir, func->get_function_name ().as_string ()); } + + auto facts = BIR::FactCollector::collect (bir); } for (auto closure ATTRIBUTE_UNUSED : collector.get_closures ())