From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x529.google.com (mail-ed1-x529.google.com [IPv6:2a00:1450:4864:20::529]) by sourceware.org (Postfix) with ESMTPS id 6DC31386183B for ; Thu, 1 Aug 2024 15:00:56 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 6DC31386183B 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 6DC31386183B Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2a00:1450:4864:20::529 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722524509; cv=none; b=WYQSroazCihMxoxVM3wYxKmrBeHWxtAvEUSEf8OzNlA8tF405mCsV3OAURWkjESYPLMXxk+6ahLaO38lM6/E+br9BDmih44xDHnS6xhrhKEHLKzOD9ImAFANJzONLUSAsxMvAYNSQg1SS4Z+pwyzqUYFqxw7FzG1FHPB17Z2+5g= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1722524509; c=relaxed/simple; bh=lokKc3tIdBzBbNdJaM7IVCjbdVGu+txiyugbOCfzIGg=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=xBqBzHC59D7T1IxV3sJvq0FI+AUonlwZt5anOsqNqEN1p5/H2Ih4o7EMiWRZT+/CVCn2rl606+XWmAP+ybEZjM8Lai5qfJdEdx+jlEtuJldFIVQt9qgznOH5i8igfctdYmpbbzimLEVyVjtnJNwYeRaVUn3fowpBwmBpBoaCO+8= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-ed1-x529.google.com with SMTP id 4fb4d7f45d1cf-5a2ffc34431so5447441a12.0 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=9/F0yYQFCGskOcWJyvM6K4pIB2Ai++2YZPdyzAuMnzk=; b=hwFDMQRzZjjVdtF3DP1N61IYV4XIluWqPOz7piwvj3VACTnEO1U/w7NzslZGWfpE0p xoQYHV9PmksxaML3RsJCAFyNk4xXMbPEIId0HDHa4y6taXg/tO7dpu2qT7Zqv2ouw0ej JqCXp+91vphw/I9d/Y90N/xL6QR83r0bIAbVqwutrYvZihnEDAQ8YR8iEtO8O2yhbKq/ vZBc+UAGUllDuMFn3CugA6x0f4oz2c6B2Judgt657kpvPVAB7RylXQ5q0dv+dhicIg/0 Q6AQohUpFECj0Ez5/wWYYMxPl7B01J/TkSs+83kGDxIqQn6WuUuvkefHN12icK2S/OU5 rLTA== 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=9/F0yYQFCGskOcWJyvM6K4pIB2Ai++2YZPdyzAuMnzk=; b=bz1saD8ilCNNf9Pv+y3ayFGAKeQuxBJ4C9Ab2CCXASK2kJFE/rO8wKAl+mtdjjmnEl bHXYqaSBch1UWUz2Mj21FAUzKqeNYFP4RVs7YVvchfWndmNPVxQW9VGikQcwCTUmUd+9 Xb2ZNqg2VxzO7AYvFga6zSIFn5uoFRqb3jb5ttd9sGttSxUBqrCtfL8TDy5FUVSR6c8d J2oAtYeKz7HAVa1lFfpZWju5XJSvBfG2U69pJo8mGkb9qlkTaYe8x5m5p34LGb+CI6YK kq9BxD1SpklD6h/+a87/8CJTJBxQfONV19O3G9quZEjDUAic8gtsEy+CeyEnncOH7is9 TVEA== X-Gm-Message-State: AOJu0Yyj+uNgL+hjQKxgqpQPoAbGGnfuw2nyIqFH1X4ck5sz6LPVxwJj +UF6lECecT6RMhmRWsZuaJ3z43/3ttZaCE15zJdiSoMi0pjl3ElzBoUAgFmcIT8zPDG79E7AoCy 8j4Np X-Google-Smtp-Source: AGHT+IHXkgo4fln2BG1PJAXgVnECEO48VpE2kClnz35cLgFTCA7C8Bgr3YgogYdRz+AgqASCOwMPwQ== X-Received: by 2002:aa7:c510:0:b0:57d:669:caf2 with SMTP id 4fb4d7f45d1cf-5b7f521e086mr542532a12.25.1722524454128; Thu, 01 Aug 2024 08:00:54 -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.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 01 Aug 2024 08:00:53 -0700 (PDT) From: Arthur Cohen To: gcc-patches@gcc.gnu.org Cc: gcc-rust@gcc.gnu.org, Jakub Dupak Subject: [PATCH 120/125] gccrs: borrowck: Regions in BIR Date: Thu, 1 Aug 2024 16:57:56 +0200 Message-ID: <20240801145809.366388-122-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 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-14.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_FILL_THIS_FORM_SHORT autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: From: Jakub Dupak gcc/rust/ChangeLog: * checks/errors/borrowck/rust-bir-place.h (struct Lifetime): Extended regions and loans. (struct Loan): Representation of loan (result of borrowing) * checks/errors/borrowck/rust-bir-builder-expr-stmt.cc (ExprStmtBuilder::visit): Fix let stmt handling. * checks/errors/borrowck/rust-bir-builder-pattern.h: improved pattern translation * checks/errors/borrowck/rust-bir-builder-internal.h: region binding * checks/errors/borrowck/rust-bir-builder-expr-stmt.h (class ExprStmtBuilder): Region support. (class RenumberCtx): Region support. * checks/errors/borrowck/rust-bir-builder.h (class Builder): Region support. * checks/errors/borrowck/rust-bir-dump.cc (get_lifetime_name): Region support. (renumber_places): Region support. (Dump::go): Region support. (Dump::visit): Region support. (Dump::visit_lifetime): Region support. (Dump::visit_scope): Region support. * checks/errors/borrowck/rust-bir.h (class AbstractExpr): Region support. (struct Function): Region support. (class BorrowExpr): Region support. (class CallExpr): Region support. Signed-off-by: Jakub Dupak --- .../borrowck/rust-bir-builder-expr-stmt.cc | 73 +++--- .../borrowck/rust-bir-builder-expr-stmt.h | 7 +- .../borrowck/rust-bir-builder-internal.h | 234 ++++++++++++------ .../borrowck/rust-bir-builder-pattern.h | 154 +++++++----- .../checks/errors/borrowck/rust-bir-builder.h | 120 +++++++-- .../checks/errors/borrowck/rust-bir-dump.cc | 46 ++-- .../checks/errors/borrowck/rust-bir-place.h | 202 +++++++++++---- gcc/rust/checks/errors/borrowck/rust-bir.h | 49 +++- 8 files changed, 610 insertions(+), 275 deletions(-) diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc index 922894cc5d5..d64641177d0 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.cc @@ -93,8 +93,8 @@ ExprStmtBuilder::visit (HIR::ClosureExpr &expr) void ExprStmtBuilder::visit (HIR::StructExprStructFields &fields) { - auto struct_ty - = lookup_type (fields)->as ()->get_variants ().at (0); + auto *p_adt_type = lookup_type (fields)->as (); + auto struct_ty = p_adt_type->get_variants ().at (0); auto init_values = StructBuilder (ctx, struct_ty).build (fields); move_all (init_values); return_expr (new InitializerExpr (std::move (init_values)), @@ -119,7 +119,15 @@ void ExprStmtBuilder::visit (HIR::BorrowExpr &expr) { auto operand = visit_expr (*expr.get_expr ()); - return_expr (new BorrowExpr (operand), lookup_type (expr)); + if (ctx.place_db[operand].is_constant ()) + { + // Cannot borrow a constant, must create a temporary copy. + push_tmp_assignment (operand); + operand = translated; + } + + // BorrowExpr cannot be annotated with lifetime. + return_borrowed (operand, lookup_type (expr)); } void @@ -183,6 +191,7 @@ ExprStmtBuilder::visit (HIR::AssignmentExpr &expr) auto lhs = visit_expr (*expr.get_lhs ()); auto rhs = visit_expr (*expr.get_rhs ()); push_assignment (lhs, rhs); + translated = INVALID_PLACE; } void @@ -265,6 +274,7 @@ ExprStmtBuilder::visit (HIR::CallExpr &expr) } move_all (arguments); + return_expr (new CallExpr (fn, std::move (arguments)), lookup_type (expr), true); } @@ -346,7 +356,10 @@ ExprStmtBuilder::visit (HIR::BlockExpr &block) lookup_type (*block.get_final_expr ())))); } - pop_scope (); + if (!unreachable) + pop_scope (); + else + ctx.place_db.pop_scope (); } void @@ -422,10 +435,12 @@ ExprStmtBuilder::visit (HIR::ReturnExpr &ret) { if (ret.has_return_expr ()) { - push_assignment (RETURN_VALUE_PLACE, visit_expr (*ret.get_expr ())); + push_assignment (RETURN_VALUE_PLACE, + move_place (visit_expr (*ret.get_expr ()))); } unwind_until (ROOT_SCOPE); ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN); + translated = INVALID_PLACE; } void @@ -538,16 +553,19 @@ ExprStmtBuilder::visit (HIR::IfExprConseqElse &expr) if (else_bb.is_goto_terminated () && else_bb.successors.empty ()) add_jump (else_end_bb, final_start_bb); } + void ExprStmtBuilder::visit (HIR::IfLetExpr &expr) { rust_sorry_at (expr.get_locus (), "if let expressions are not supported"); } + void ExprStmtBuilder::visit (HIR::IfLetExprConseqElse &expr) { rust_sorry_at (expr.get_locus (), "if let expressions are not supported"); } + void ExprStmtBuilder::visit (HIR::MatchExpr &expr) { @@ -608,8 +626,7 @@ void ExprStmtBuilder::visit (HIR::QualifiedPathInExpression &expr) { // Note: Type is only stored for the expr, not the segment. - PlaceId result - = resolve_variable_or_fn (expr.get_final_segment (), lookup_type (expr)); + PlaceId result = resolve_variable_or_fn (expr, lookup_type (expr)); return_place (result); } @@ -617,14 +634,19 @@ void ExprStmtBuilder::visit (HIR::PathInExpression &expr) { // Note: Type is only stored for the expr, not the segment. - PlaceId result - = resolve_variable_or_fn (expr.get_final_segment (), lookup_type (expr)); + PlaceId result = resolve_variable_or_fn (expr, lookup_type (expr)); return_place (result); } void ExprStmtBuilder::visit (HIR::LetStmt &stmt) { + tl::optional init; + tl::optional type_annotation; + + if (stmt.has_type ()) + type_annotation = lookup_type (*stmt.get_type ()); + if (stmt.get_pattern ()->get_pattern_type () == HIR::Pattern::IDENTIFIER) { // Only if a pattern is just an identifier, no destructuring is needed. @@ -632,35 +654,30 @@ ExprStmtBuilder::visit (HIR::LetStmt &stmt) // (init expr is evaluated before pattern binding) into a // variable, so it would emit extra assignment. auto var = declare_variable (stmt.get_pattern ()->get_mappings ()); - auto &var_place = ctx.place_db[var]; - if (var_place.tyty->get_kind () == TyTy::REF) - { - var_place.lifetime = ctx.lookup_lifetime ( - optional_from_ptr ( - static_cast (stmt.get_type ().get ())) - .map (&HIR::ReferenceType::get_lifetime)); - } + if (stmt.has_type ()) + push_user_type_ascription (var, lookup_type (*stmt.get_type ())); + if (stmt.has_init_expr ()) (void) visit_expr (*stmt.get_init_expr (), var); } - else if (stmt.has_init_expr ()) - { - auto init = visit_expr (*stmt.get_init_expr ()); - PatternBindingBuilder (ctx, init, stmt.get_type ().get ()) - .go (*stmt.get_pattern ()); - } else { - rust_sorry_at (stmt.get_locus (), "pattern matching in let statements " - "without initializer is not supported"); + if (stmt.has_init_expr ()) + init = visit_expr (*stmt.get_init_expr ()); + + PatternBindingBuilder (ctx, init, type_annotation) + .go (*stmt.get_pattern ()); } } void ExprStmtBuilder::visit (HIR::ExprStmt &stmt) { - (void) visit_expr (*stmt.get_expr ()); + PlaceId result = visit_expr (*stmt.get_expr ()); + // We must read the value for current liveness and we must not store it into + // the same place. + if (result != INVALID_PLACE) + push_tmp_assignment (result); } - } // namespace BIR -} // namespace Rust \ No newline at end of file +} // namespace Rust diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h index 0654bcc27b0..1597ff291b0 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-expr-stmt.h @@ -30,15 +30,16 @@ namespace BIR { * See AbstractExprBuilder for API usage docs (mainly `return_place` and * `return_expr`). */ -class ExprStmtBuilder : public AbstractExprBuilder, public HIR::HIRStmtVisitor +class ExprStmtBuilder final : public AbstractExprBuilder, + public HIR::HIRStmtVisitor { public: explicit ExprStmtBuilder (BuilderContext &ctx) : AbstractExprBuilder (ctx) {} /** Entry point. */ - PlaceId build (HIR::Expr &expr, PlaceId place = INVALID_PLACE) + PlaceId build (HIR::Expr &expr, PlaceId destination = INVALID_PLACE) { - return visit_expr (expr, place); + return visit_expr (expr, destination); } private: diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h index b421ba43fba..2e2a7e2970a 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-internal.h @@ -26,39 +26,30 @@ #include "rust-hir-visitor.h" #include "rust-name-resolver.h" #include "rust-bir.h" +#include "rust-bir-free-region.h" namespace Rust { -namespace BIR { +namespace TyTy { -/** Holds the context of BIR building so that it can be shared/passed between - * different builders. */ -struct BuilderContext +using Variance = VarianceAnalysis::Variance; + +class RenumberCtx { - class LifetimeResolver - { - using Index = uint32_t; - using Value = std::string; + Polonius::Origin next_region = 0; - Index next_index = FIRST_NORMAL_LIFETIME_ID; - std::unordered_map value_to_index; +public: + Polonius::Origin get_next_region () { return next_region++; } +}; - public: - Index resolve (const Value &value) - { - auto found = value_to_index.find (value); - if (found != value_to_index.end ()) - { - return found->second; - } - value_to_index.emplace (value, next_index); - return next_index++; - } +} // namespace TyTy - /** Returns a new anonymous lifetime. */ - Index get_anonymous () { return next_index++; } - }; +namespace BIR { +/** Holds the context of BIR building so that it can be shared/passed between + * different builders. */ +struct BuilderContext +{ struct LoopAndLabelCtx { bool is_loop; // Loop or labelled block @@ -93,7 +84,8 @@ struct BuilderContext * constants) */ PlaceDB place_db; - LifetimeResolver lifetime_interner; + RegionBinder region_binder{place_db.expose_next_free_region ()}; + // Used for cleaner dump. std::vector arguments; /** @@ -105,6 +97,8 @@ struct BuilderContext /** Context for current situation (loop, label, etc.) */ std::vector loop_and_label_stack; + FreeRegions fn_free_regions{{}}; + public: BuilderContext () : tyctx (*Resolver::TypeCheckContext::get ()), @@ -115,27 +109,6 @@ public: BasicBlock &get_current_bb () { return basic_blocks[current_bb]; } - Lifetime lookup_lifetime (const tl::optional &lifetime) - { - if (!lifetime.has_value ()) - return {lifetime_interner.get_anonymous ()}; - switch (lifetime->get_lifetime_type ()) - { - case AST::Lifetime::NAMED: { - return {lifetime_interner.resolve (lifetime->get_name ())}; - } - case AST::Lifetime::STATIC: { - return STATIC_LIFETIME; - } - case AST::Lifetime::WILDCARD: { - rust_sorry_at (lifetime->get_locus (), - "lifetime elision is not yet implemented"); - return NO_LIFETIME; - } - } - rust_unreachable (); - }; - const LoopAndLabelCtx &lookup_label (NodeId label) { auto label_match = [label] (const LoopAndLabelCtx &info) { @@ -165,25 +138,31 @@ protected: protected: explicit AbstractBuilder (BuilderContext &ctx) : ctx (ctx) {} - PlaceId declare_variable (const Analysis::NodeMapping &node) + PlaceId declare_variable (const Analysis::NodeMapping &node, + bool user_type_annotation = false) { - return declare_variable (node, lookup_type (node.get_hirid ())); + return declare_variable (node, lookup_type (node.get_hirid ()), + user_type_annotation); } PlaceId declare_variable (const Analysis::NodeMapping &node, - TyTy::BaseType *ty) + TyTy::BaseType *ty, + bool user_type_annotation = false) { const NodeId nodeid = node.get_nodeid (); // In debug mode, check that the variable is not already declared. rust_assert (ctx.place_db.lookup_variable (nodeid) == INVALID_PLACE); - auto place = ctx.place_db.add_variable (nodeid, ty); + auto place_id = ctx.place_db.add_variable (nodeid, ty); if (ctx.place_db.get_current_scope_id () != 0) - push_storage_live (place); + push_storage_live (place_id); + + if (user_type_annotation) + push_user_type_ascription (place_id, ty); - return place; + return place_id; } void push_new_scope () { ctx.place_db.push_new_scope (); } @@ -199,18 +178,64 @@ protected: ctx.place_db.pop_scope (); } + bool intersection_empty (std::vector &a, std::vector &b) + { + for (auto &place : a) + { + if (std::find (b.begin (), b.end (), place) != b.end ()) + return false; + } + return true; + } + void unwind_until (ScopeId final_scope) { auto current_scope_id = ctx.place_db.get_current_scope_id (); while (current_scope_id != final_scope) { auto &scope = ctx.place_db.get_scope (current_scope_id); + + // TODO: Perform stable toposort based on `borrowed_by`. + std::for_each (scope.locals.rbegin (), scope.locals.rend (), [&] (PlaceId place) { push_storage_dead (place); }); current_scope_id = scope.parent; } } + FreeRegions bind_regions (std::vector regions, + FreeRegions parent_free_regions) + { + std::vector free_regions; + for (auto ®ion : regions) + { + if (region.is_early_bound ()) + { + free_regions.push_back (parent_free_regions[region.get_index ()]); + } + else if (region.is_static ()) + { + free_regions.push_back (0); + } + else if (region.is_anonymous ()) + { + free_regions.push_back (ctx.place_db.get_next_free_region ()); + } + else if (region.is_named ()) + { + rust_unreachable (); // FIXME + } + else + { + rust_sorry_at (UNKNOWN_LOCATION, "Unimplemented"); + rust_unreachable (); + } + } + // This is necesarry because of clash of current gcc and gcc4.8. + FreeRegions free_regions_final{std::move (free_regions)}; + return free_regions_final; + } + protected: // Helpers to add BIR statements void push_assignment (PlaceId lhs, AbstractExpr *rhs) { @@ -264,15 +289,51 @@ protected: // Helpers to add BIR statements Statement::Kind::STORAGE_DEAD, place); } + void push_user_type_ascription (PlaceId place, TyTy::BaseType *ty) + { + ctx.get_current_bb ().statements.emplace_back ( + Statement::Kind::USER_TYPE_ASCRIPTION, place, ty); + } + + void push_fake_read (PlaceId place) + { + ctx.get_current_bb ().statements.emplace_back (Statement::Kind::FAKE_READ, + place); + } + + PlaceId borrow_place (PlaceId place_id, TyTy::BaseType *ty) + { + auto mutability = ty->as ()->mutability (); + auto loan = ctx.place_db.add_loan ({mutability, place_id}); + push_tmp_assignment (new BorrowExpr (place_id, loan, + ctx.place_db.get_next_free_region ()), + ty); + return translated; + } + PlaceId move_place (PlaceId arg) { - if (ctx.place_db[arg].is_lvalue ()) - { - push_tmp_assignment (arg); - arg = translated; - } + auto &place = ctx.place_db[arg]; + + if (place.is_constant ()) + return arg; + + if (place.tyty->is ()) + return reborrow_place (arg); + + if (place.is_rvalue ()) + return arg; - return arg; + push_tmp_assignment (arg); + return translated; + } + + PlaceId reborrow_place (PlaceId arg) + { + auto ty = ctx.place_db[arg].tyty->as (); + return borrow_place (ctx.place_db.lookup_or_add_path (Place::DEREF, + ty->get_base (), arg), + ty); } template void move_all (T &args) @@ -348,15 +409,17 @@ protected: // HIR resolution helpers template PlaceId resolve_variable_or_fn (T &variable, TyTy::BaseType *ty) { + ty = (ty) ? ty : lookup_type (variable); // Unlike variables, // functions do not have to be declared in PlaceDB before use. NodeId variable_id; bool ok = ctx.resolver.lookup_resolved_name ( variable.get_mappings ().get_nodeid (), &variable_id); rust_assert (ok); - return ctx.place_db.lookup_or_add_variable (variable_id, - (ty) ? ty - : lookup_type (variable)); + if (ty->is ()) + return ctx.place_db.get_constant (ty); + else + return ctx.place_db.lookup_or_add_variable (variable_id, ty); } protected: // Implicit conversions. @@ -415,10 +478,11 @@ protected: // Implicit conversions. if (ctx.place_db[translated].tyty->get_kind () != TyTy::REF) { auto ty = ctx.place_db[translated].tyty; - push_tmp_assignment ( - new BorrowExpr (translated), - new TyTy::ReferenceType (ty->get_ref (), TyTy::TyVar (ty->get_ref ()), - Mutability::Imm)); + translated + = borrow_place (translated, + new TyTy::ReferenceType (ty->get_ref (), + TyTy::TyVar (ty->get_ref ()), + Mutability::Imm)); } } }; @@ -441,8 +505,8 @@ protected: {} /** - * Wrapper that provides return value based API inside a visitor which has to - * use global state to pass the data around. + * Wrapper that provides return value based API inside a visitor which has + * to use global state to pass the data around. * @param dst_place Place to assign the produced value to, optionally * allocated by the caller. * */ @@ -461,10 +525,11 @@ protected: /** * Create a return value of a subexpression, which produces an expression. - * Use `return_place` for subexpression that only produce a place (look it up) - * to avoid needless assignments. + * Use `return_place` for subexpression that only produce a place (look it + * up) to avoid needless assignments. * - * @param can_panic mark that expression can panic to insert jump to cleanup. + * @param can_panic mark that expression can panic to insert jump to + * cleanup. */ void return_expr (AbstractExpr *expr, TyTy::BaseType *ty, bool can_panic = false) @@ -482,10 +547,16 @@ protected: { start_new_consecutive_bb (); } + + if (ty->is () + || ctx.place_db[translated].is_constant ()) + { + push_fake_read (translated); + } } /** Mark place to be a result of processed subexpression. */ - void return_place (PlaceId place) + void return_place (PlaceId place, bool can_panic = false) { if (expr_return_place != INVALID_PLACE) { @@ -496,6 +567,16 @@ protected: { translated = place; } + + if (can_panic) + { + start_new_consecutive_bb (); + } + + if (ctx.place_db[place].is_constant ()) + { + push_fake_read (translated); + } } /** Explicitly return a unit value. Expression produces no value. */ @@ -504,6 +585,17 @@ protected: translated = ctx.place_db.get_constant (lookup_type (expr)); } + PlaceId return_borrowed (PlaceId place_id, TyTy::BaseType *ty) + { + // TODO: deduplicate with borrow_place + auto loan = ctx.place_db.add_loan ( + {ty->as ()->mutability (), place_id}); + return_expr (new BorrowExpr (place_id, loan, + ctx.place_db.get_next_free_region ()), + ty); + return translated; + } + PlaceId take_or_create_return_place (TyTy::BaseType *type) { PlaceId result = INVALID_PLACE; diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h index 76943ff1b04..8b5adabcb6e 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder-pattern.h @@ -20,6 +20,8 @@ #define RUST_BIR_BUILDER_PATTERN_H #include "rust-bir-builder-internal.h" +#include "rust-bir-free-region.h" +#include "rust-tyty-variance-analysis.h" namespace Rust { namespace BIR { @@ -32,9 +34,9 @@ class PatternBindingBuilder : protected AbstractBuilder, public HIR::HIRPatternVisitor { /** Value of initialization expression. */ - PlaceId init; - /** This is where lifetime annotations are stored. */ - tl::optional type; + tl::optional init; + tl::optional type_annotation; + tl::optional regions; /** Emulates recursive stack saving and restoring inside a visitor. */ class SavedState @@ -42,24 +44,22 @@ class PatternBindingBuilder : protected AbstractBuilder, PatternBindingBuilder *builder; public: - const PlaceId init; - const tl::optional type; + const tl::optional init; + const tl::optional regions; public: explicit SavedState (PatternBindingBuilder *builder) - : builder (builder), init (builder->init), type (builder->type) + : builder (builder), init (builder->init), regions (builder->regions) {} - ~SavedState () - { - builder->init = init; - builder->type = type; - } + ~SavedState () { builder->init = init; } }; public: - PatternBindingBuilder (BuilderContext &ctx, PlaceId init, HIR::Type *type) - : AbstractBuilder (ctx), init (init), type (optional_from_ptr (type)) + PatternBindingBuilder (BuilderContext &ctx, tl::optional init, + tl::optional type_annotation) + : AbstractBuilder (ctx), init (init), type_annotation (type_annotation), + regions (tl::nullopt) {} void go (HIR::Pattern &pattern) { pattern.accept_vis (*this); } @@ -74,21 +74,15 @@ public: TyTy::TyVar (node.get_hirid ()), (is_mut) ? Mutability::Mut : Mutability::Imm)); - push_assignment (translated, new BorrowExpr (init)); } else { translated = declare_variable (node); - push_assignment (translated, init); } - auto &init_place = ctx.place_db[init]; - auto &translated_place = ctx.place_db[translated]; - if (init_place.tyty->get_kind () == TyTy::REF) + + if (init.has_value ()) { - init_place.lifetime = ctx.lookup_lifetime (type.map ([] (HIR::Type *t) { - return static_cast (t)->get_lifetime (); - })); - translated_place.lifetime = init_place.lifetime; + push_assignment (translated, init.value ()); } } @@ -104,15 +98,15 @@ public: { SavedState saved (this); - auto ref_type = type.map ( - [] (HIR::Type *t) { return static_cast (t); }); + init = init.map ([&] (PlaceId id) { + return ctx.place_db.lookup_or_add_path (Place::DEREF, + lookup_type (pattern), id); + }); + + type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) { + return ty->as ()->get_base (); + }); - type = ref_type.map ( - [] (HIR::ReferenceType *r) { return r->get_base_type ().get (); }); - init = ctx.place_db.lookup_or_add_path (Place::DEREF, lookup_type (pattern), - saved.init); - ctx.place_db[init].lifetime - = ctx.lookup_lifetime (ref_type.map (&HIR::ReferenceType::get_lifetime)); pattern.get_referenced_pattern ()->accept_vis (*this); } @@ -120,12 +114,20 @@ public: { SavedState saved (this); - type = type.map ([] (HIR::Type *t) { - return static_cast (t)->get_element_type ().get (); - }); // All indexes are supposed to point to the same place for borrow-checking. - init = ctx.place_db.lookup_or_add_path (Place::INDEX, lookup_type (pattern), - saved.init); + // init = ctx.place_db.lookup_or_add_path (Place::INDEX, lookup_type + // (pattern), saved.init); + init = init.map ([&] (PlaceId id) { + return ctx.place_db.lookup_or_add_path (Place::INDEX, + lookup_type (pattern), id); + }); + + type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) { + return ty->as ()->get_element_type (); + }); + + // Regions are unchnaged. + for (auto &item : pattern.get_items ()) { item->accept_vis (*this); @@ -142,15 +144,12 @@ public: { SavedState saved (this); - auto tyty = ctx.place_db[init].tyty; + auto tyty = ctx.place_db[init.value ()].tyty; rust_assert (tyty->get_kind () == TyTy::ADT); auto adt_ty = static_cast (tyty); rust_assert (adt_ty->is_struct_struct ()); auto struct_ty = adt_ty->get_variants ().at (0); - auto struct_type = type.map ([] (HIR::Type *t) { - return static_cast (t)->get_final_segment ().get (); - }); for (auto &field : pattern.get_struct_pattern_elems ().get_struct_pattern_fields ()) { @@ -159,9 +158,22 @@ public: case HIR::StructPatternField::TUPLE_PAT: { auto tuple = static_cast (field.get ()); - init = ctx.place_db.lookup_or_add_path ( - Place::FIELD, lookup_type (*tuple->get_tuple_pattern ()), - saved.init, tuple->get_index ()); + + init = init.map ([&] (PlaceId id) { + return ctx.place_db.lookup_or_add_path ( + Place::FIELD, lookup_type (*tuple->get_tuple_pattern ()), id, + tuple->get_index ()); + }); + + type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) { + return ty->as () + ->get_variants () + .at (0) + ->get_fields () + .at (tuple->get_index ()) + ->get_field_type (); + }); + tuple->get_tuple_pattern ()->accept_vis (*this); break; } @@ -177,7 +189,8 @@ public: init = ctx.place_db.lookup_or_add_path (Place::FIELD, field_ty->get_field_type (), - saved.init, field_index); + saved.init.value (), + field_index); ident_field->get_pattern ()->accept_vis (*this); break; } @@ -193,7 +206,8 @@ public: init = ctx.place_db.lookup_or_add_path (Place::FIELD, field_ty->get_field_type (), - saved.init, field_index); + saved.init.value (), + field_index); visit_identifier (ident_field->get_mappings (), ident_field->get_has_ref (), ident_field->is_mut ()); @@ -208,19 +222,32 @@ public: { for (auto &item : fields) { - type = saved.type.map ([&] (HIR::Type *t) { - return static_cast (t) - ->get_elems () + auto type = lookup_type (*item); + + init = init.map ([&] (PlaceId id) { + return ctx.place_db.lookup_or_add_path (Place::FIELD, type, id, + index); + }); + + type_annotation = type_annotation.map ([&] (TyTy::BaseType *ty) { + return ty->as () + ->get_fields () .at (index) - .get (); + .get_tyty (); + }); + + regions = regions.map ([&] (FreeRegions regs) { + return bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions (type), + regs); }); - init - = ctx.place_db.lookup_or_add_path (Place::FIELD, lookup_type (*item), - saved.init, index); + item->accept_vis (*this); index++; } } + void visit (HIR::TuplePattern &pattern) override { SavedState saved (this); @@ -238,7 +265,7 @@ public: auto &items = static_cast ( *pattern.get_items ()); - auto tyty = ctx.place_db[init].tyty; + auto tyty = ctx.place_db[init.value ()].tyty; rust_assert (tyty->get_kind () == TyTy::TUPLE); auto skipped = (static_cast (tyty))->num_fields () @@ -253,10 +280,22 @@ public: } init = saved.init; } + void visit (HIR::TupleStructPattern &pattern) override { SavedState saved (this); + type_annotation = tl::nullopt; + + auto type = lookup_type (pattern); + + regions = regions.map ([&] (FreeRegions regs) { + return bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions (type), + regs); + }); + size_t index = 0; switch (pattern.get_items ()->get_item_type ()) { @@ -264,9 +303,8 @@ public: auto &items = static_cast (*pattern.get_items ()); - auto tyty = ctx.place_db[init].tyty; - rust_assert (tyty->get_kind () == TyTy::ADT); - auto adt_ty = static_cast (tyty); + rust_assert (type->get_kind () == TyTy::ADT); + auto adt_ty = static_cast (type); rust_assert (adt_ty->is_tuple_struct ()); auto skipped = adt_ty->get_variants ().at (0)->get_fields ().size () @@ -293,12 +331,6 @@ public: void visit (HIR::PathInExpression &expression) override {} void visit (HIR::QualifiedPathInExpression &expression) override {} void visit (HIR::RangePattern &pattern) override {} - -private: - template tl::optional *get_type () - { - return static_cast (type); - } }; } // namespace BIR } // namespace Rust diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-builder.h b/gcc/rust/checks/errors/borrowck/rust-bir-builder.h index 9bed96c660f..e9108703be1 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-builder.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-builder.h @@ -20,72 +20,142 @@ #define RUST_BIR_BUILDER_H #include "rust-bir-builder-internal.h" -#include "rust-hir-visitor.h" #include "rust-bir-builder-pattern.h" -#include "rust-bir-builder-struct.h" #include "rust-bir-builder-expr-stmt.h" namespace Rust { namespace BIR { /** Top-level builder, which compiles a HIR function into a BIR function. */ -class Builder : public AbstractBuilder +class Builder final : public AbstractBuilder { + std::vector> universal_region_bounds; + public: explicit Builder (BuilderContext &ctx) : AbstractBuilder (ctx) {} Function build (HIR::Function &function) { - PlaceId return_place - = ctx.place_db.add_temporary (lookup_type (*function.get_definition ())); - rust_assert (return_place == RETURN_VALUE_PLACE); + rust_debug ("BIR::Builder::build function={%s}", + function.get_function_name ().as_string ().c_str ()); + + auto fn_ty = lookup_type (function)->as (); + + handle_lifetime_params (fn_ty->get_num_lifetime_params ()); + handle_lifetime_param_constraints (fn_ty->get_region_constraints ()); + + handle_return (fn_ty); for (auto ¶m : function.get_function_params ()) - { - handle_param (param); - } + handle_param (param); handle_body (*function.get_definition ()); - return Function{std::move (ctx.place_db), std::move (ctx.arguments), - std::move (ctx.basic_blocks)}; - }; + return Function{ + std::move (ctx.place_db), + std::move (ctx.arguments), + std::move (ctx.basic_blocks), + std::move (ctx.fn_free_regions), + std::move (universal_region_bounds), + function.get_locus (), + }; + } private: + /** Instantiate `num_lifetime_params` free regions. */ + void handle_lifetime_params (size_t num_lifetime_params) + { + std::vector function_free_regions; + for (size_t i = 0; i < num_lifetime_params; i++) + { + function_free_regions.push_back (ctx.place_db.get_next_free_region ()); + } + + rust_debug ("\tctx.fn_free_region={%s}", + ctx.fn_free_regions.to_string ().c_str ()); + ctx.fn_free_regions.set_from (std::move (function_free_regions)); + } + + void handle_lifetime_param_constraints ( + const TyTy::RegionConstraints ®ion_constraints) + { + rust_debug ("\thandle_lifetime_param_constraints"); + + for (auto bound : region_constraints.region_region) + { + rust_assert (bound.first.is_early_bound ()); + rust_assert (bound.second.is_early_bound ()); + + universal_region_bounds.emplace_back ( + ctx.fn_free_regions[bound.first.get_index ()], + ctx.fn_free_regions[bound.second.get_index ()]); + + auto last_bound = universal_region_bounds.back (); + rust_debug ("\t\t %ld: %ld", last_bound.first, last_bound.second); + } + + // TODO: handle type_region constraints + } + + void handle_return (TyTy::FnType *fn_ty) + { + TyTy::BaseType *return_ty = fn_ty->get_return_type (); + + PlaceId return_place = ctx.place_db.add_temporary (return_ty); + rust_assert (return_place == RETURN_VALUE_PLACE); + + // Set return place to use functions regions, not the fresh ones. + ctx.place_db[return_place].regions + = bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions (fn_ty->get_return_type ()), + ctx.fn_free_regions); + } + void handle_param (HIR::FunctionParam ¶m) { + auto param_type = lookup_type (*param.get_param_name ()); + auto &pattern = param.get_param_name (); if (pattern->get_pattern_type () == HIR::Pattern::IDENTIFIER && !static_cast (*pattern).get_is_ref ()) { - // Avoid useless temporary variable for parameter. + // Avoid useless temporary variable for parameter to look like MIR. translated = declare_variable (pattern->get_mappings ()); ctx.arguments.push_back (translated); } else { - translated = ctx.place_db.add_temporary (lookup_type (*pattern)); + translated = ctx.place_db.add_temporary (param_type); ctx.arguments.push_back (translated); - PatternBindingBuilder (ctx, translated, param.get_type ().get ()) + PatternBindingBuilder (ctx, translated, tl::nullopt) .go (*param.get_param_name ()); } + + rust_assert (param.get_type () != nullptr); + + // Set parameter place to use functions regions, not the fresh ones. + ctx.place_db[translated].regions + = bind_regions (Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_regions (param_type), + ctx.fn_free_regions); } void handle_body (HIR::BlockExpr &body) { - translated = ExprStmtBuilder (ctx).build (body); - if (body.has_expr () && !lookup_type (body)->is_unit ()) + translated = ExprStmtBuilder (ctx).build (body, RETURN_VALUE_PLACE); + if (!ctx.get_current_bb ().is_terminated ()) { - push_assignment (RETURN_VALUE_PLACE, translated); + if (ctx.place_db[RETURN_VALUE_PLACE].tyty->is_unit ()) + { + push_assignment (RETURN_VALUE_PLACE, + ctx.place_db.get_constant ( + ctx.place_db[RETURN_VALUE_PLACE].tyty)); + } ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN); } - else if (!ctx.get_current_bb ().is_terminated ()) - { - push_assignment (RETURN_VALUE_PLACE, - ctx.place_db.get_constant (lookup_type (body))); - ctx.get_current_bb ().statements.emplace_back (Statement::Kind::RETURN); - } - }; + } }; } // namespace BIR diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc index 6f1579df1d9..51dd1436350 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc +++ b/gcc/rust/checks/errors/borrowck/rust-bir-dump.cc @@ -7,14 +7,6 @@ namespace BIR { constexpr auto indentation = " "; -uint32_t -get_lifetime_name (Lifetime lifetime_id) -{ - rust_assert (lifetime_id.id >= FIRST_NORMAL_LIFETIME_ID); - // Start from 1 as rustc does. - return lifetime_id.id - FIRST_NORMAL_LIFETIME_ID + 1; -} - std::string get_tyty_name (TyTy::BaseType *tyty) { @@ -42,7 +34,7 @@ void renumber_places (const Function &func, std::vector &place_map) { // Renumbering places to avoid gaps in the place id space. - // This is needed to match MIR shape. + // This is needed to match MIR's shape. size_t next_out_id = 0; for (size_t in_id = FIRST_VARIABLE_PLACE; in_id < func.place_db.size (); @@ -116,8 +108,8 @@ Dump::go (bool enable_simplify_cfg) stream << "_" << place_map[place_id] << ": " << get_tyty_name (func.place_db[place_id].tyty); }); - stream << ") -> " << get_tyty_name (func.place_db[RETURN_VALUE_PLACE].tyty) - << " {\n"; + stream << ") -> " << get_tyty_name (func.place_db[RETURN_VALUE_PLACE].tyty); + stream << " {\n"; // Print locals declaration. visit_scope (0); @@ -138,16 +130,17 @@ Dump::go (bool enable_simplify_cfg) BasicBlock &bb = func.basic_blocks[statement_bb]; stream << "\n"; stream << indentation << "bb" << bb_fold_map[statement_bb] << ": {\n"; + size_t i = 0; for (auto &stmt : bb.statements) { - stream << indentation << indentation; + stream << indentation << i++ << indentation; visit (stmt); stream << ";\n"; } if (!bb_terminated) { stream << indentation << indentation << "goto -> bb" - << bb_fold_map[bb.successors.at (0)] << ";\n"; + << bb_fold_map[bb.successors.at (0)] << ";\t\t" << i++ << "\n"; } stream << indentation << "}\n"; } @@ -196,6 +189,18 @@ Dump::visit (const Statement &stmt) visit_place (stmt.get_place ()); stream << ")"; break; + case Statement::Kind::USER_TYPE_ASCRIPTION: + visit_place (stmt.get_place ()); + stream << " = "; + stream << "UserTypeAscription("; + stream << get_tyty_name (func.place_db[stmt.get_place ()].tyty); + stream << ")"; + break; + case Statement::Kind::FAKE_READ: + stream << "FakeRead("; + visit_place (stmt.get_place ()); + stream << ")"; + break; } statement_place = INVALID_PLACE; } @@ -250,22 +255,12 @@ void Dump::visit (const BorrowExpr &expr) { stream << "&"; - visit_lifetime (statement_place); visit_place (expr.get_place ()); } void Dump::visit_lifetime (PlaceId place_id) -{ - const Place &place = func.place_db[place_id]; - if (place.lifetime.has_lifetime ()) - { - if (place.lifetime.id == STATIC_LIFETIME_ID) - stream << "'static "; - else - stream << "'#" << get_lifetime_name (place.lifetime) << " "; - } -} +{} void Dump::visit (const InitializerExpr &expr) @@ -358,7 +353,8 @@ Dump::visit_scope (ScopeId id, size_t depth) { indent (depth + 1) << "let _"; stream << place_map[local] << ": " - << get_tyty_name (func.place_db[local].tyty) << ";\n"; + << get_tyty_name (func.place_db[local].tyty); + stream << ";\n"; } for (auto &child : scope.children) { diff --git a/gcc/rust/checks/errors/borrowck/rust-bir-place.h b/gcc/rust/checks/errors/borrowck/rust-bir-place.h index 546890d797c..f22ab112b3e 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir-place.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir-place.h @@ -22,6 +22,11 @@ #include "rust-mapping-common.h" #include "rust-system.h" #include "rust-tyty.h" +#include "rust-bir-free-region.h" + +#include "rust-tyty-variance-analysis.h" +#include "polonius/rust-polonius-ffi.h" +#include "rust-hir-type-check.h" namespace Rust { namespace BIR { @@ -33,30 +38,8 @@ static constexpr PlaceId INVALID_PLACE = 0; static constexpr PlaceId RETURN_VALUE_PLACE = 1; static constexpr PlaceId FIRST_VARIABLE_PLACE = RETURN_VALUE_PLACE; -/** - * A unique identifier for a lifetime in the BIR. Only to be used INTERNALLY. - */ -using LifetimeID = uint32_t; - -constexpr LifetimeID INVALID_LIFETIME_ID = 0; -constexpr LifetimeID STATIC_LIFETIME_ID = 1; -constexpr LifetimeID FIRST_NORMAL_LIFETIME_ID = 2; - -/** Representation of lifetimes in BIR. */ -struct Lifetime -{ - LifetimeID id = INVALID_LIFETIME_ID; - - constexpr Lifetime (LifetimeID id) : id (id) {} - constexpr Lifetime (const Lifetime &) = default; - WARN_UNUSED_RESULT bool has_lifetime () const - { - return id != INVALID_LIFETIME_ID; - } - LifetimeID operator() () const { return id; } -}; -constexpr Lifetime NO_LIFETIME = {INVALID_LIFETIME_ID}; -constexpr Lifetime STATIC_LIFETIME = {STATIC_LIFETIME_ID}; +using Variance = TyTy::VarianceAnalysis::Variance; +using LoanId = uint32_t; /** * Representation of lvalues and constants in BIR. @@ -92,25 +75,72 @@ struct Place /** Copy trait */ bool is_copy; bool has_drop = false; - Lifetime lifetime; TyTy::BaseType *tyty; + FreeRegions regions{{}}; + std::vector borrowed_by{}; public: Place (Kind kind, uint32_t variable_or_field_index, const Path &path, - bool is_copy, const Lifetime &lifetime, TyTy::BaseType *tyty) + bool is_copy, TyTy::BaseType *tyty) : kind (kind), variable_or_field_index (variable_or_field_index), - path (path), is_copy (is_copy), lifetime (lifetime), tyty (tyty) + path (path), is_copy (is_copy), tyty (tyty) {} + // Place can only be stored in PlaceDB and used via reference. Turn all + // accidental copies into errors. + Place (const Place &) = delete; + Place (Place &&) = default; + public: - [[nodiscard]] bool is_lvalue () const + WARN_UNUSED_RESULT bool is_lvalue () const { - return kind == VARIABLE || kind == FIELD || kind == INDEX || kind == DEREF; + return kind == VARIABLE || is_path (); } - [[nodiscard]] bool is_rvalue () const { return kind == TEMPORARY; } + WARN_UNUSED_RESULT bool is_rvalue () const { return kind == TEMPORARY; } bool is_constant () const { return kind == CONSTANT; } + + WARN_UNUSED_RESULT bool is_var () const + { + return kind == VARIABLE || kind == TEMPORARY; + } + + WARN_UNUSED_RESULT bool is_path () const + { + return kind == FIELD || kind == INDEX || kind == DEREF; + } + + WARN_UNUSED_RESULT TyTy::BaseType *get_fn_return_ty () const + { + switch (tyty->get_kind ()) + { + case TyTy::FNPTR: + return tyty->as ()->get_return_type (); + case TyTy::FNDEF: + return tyty->as ()->get_return_type (); + default: + rust_assert (false); + } + } + + WARN_UNUSED_RESULT bool is_indirect () const + { + // TODO: probably incomplete, check other projections + switch (tyty->get_kind ()) + { + case TyTy::REF: + case TyTy::POINTER: + return true; + default: + return false; + } + } + + WARN_UNUSED_RESULT bool should_be_moved () const + { + return kind == TEMPORARY || (!is_copy && kind != CONSTANT); + } }; using ScopeId = uint32_t; @@ -128,6 +158,12 @@ struct Scope std::vector locals; }; +struct Loan +{ + Mutability mutability; + PlaceId place; +}; + /** Allocated places and keeps track of paths. */ class PlaceDB { @@ -138,11 +174,15 @@ private: std::vector scopes; ScopeId current_scope = 0; + std::vector loans; + + Polonius::Origin next_free_region = 1; + public: PlaceDB () { // Reserved index for invalid place. - places.push_back ({Place::INVALID, 0, {}, false, NO_LIFETIME, nullptr}); + places.push_back ({Place::INVALID, 0, {}, false, nullptr}); scopes.emplace_back (); // Root scope. } @@ -150,8 +190,13 @@ public: Place &operator[] (PlaceId id) { return places.at (id); } const Place &operator[] (PlaceId id) const { return places.at (id); } + decltype (places)::const_iterator begin () const { return places.begin (); } + decltype (places)::const_iterator end () const { return places.end (); } + size_t size () const { return places.size (); } + const std::vector &get_loans () const { return loans; } + ScopeId get_current_scope_id () const { return current_scope; } const std::vector &get_scopes () const { return scopes; } @@ -160,6 +205,12 @@ public: const Scope &get_scope (ScopeId id) const { return scopes[id]; } + FreeRegion get_next_free_region () { return next_free_region++; } + + FreeRegion peek_next_free_region () const { return next_free_region; } + + FreeRegion &expose_next_free_region () { return next_free_region; } + ScopeId push_new_scope () { ScopeId new_scope = scopes.size (); @@ -176,31 +227,42 @@ public: return current_scope; } - PlaceId add_place (Place place, PlaceId last_sibling = 0) + PlaceId add_place (Place &&place, PlaceId last_sibling = 0) { - places.push_back (place); + places.emplace_back (std::forward (place)); PlaceId new_place = places.size () - 1; + Place &new_place_ref = places[new_place]; // Intentional shadowing. if (last_sibling == 0) { - places[place.path.parent].path.first_child = new_place; + places[new_place_ref.path.parent].path.first_child = new_place; } else { places[last_sibling].path.next_sibling = new_place; } - if (place.kind == Place::VARIABLE || place.kind == Place::TEMPORARY) + if (new_place_ref.kind == Place::VARIABLE + || new_place_ref.kind == Place::TEMPORARY) { scopes[current_scope].locals.push_back (new_place); } + auto variances = Resolver::TypeCheckContext::get () + ->get_variance_analysis_ctx () + .query_type_variances (new_place_ref.tyty); + std::vector regions; + for (size_t i = 0; i < variances.size (); i++) + { + regions.push_back (next_free_region++); + } + new_place_ref.regions.set_from (std::move (regions)); + return new_place; } PlaceId add_variable (NodeId id, TyTy::BaseType *tyty) { - return add_place ( - {Place::VARIABLE, id, {}, is_type_copy (tyty), NO_LIFETIME, tyty}, 0); + return add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty}, 0); } WARN_UNUSED_RESULT PlaceId lookup_or_add_path (Place::Kind kind, @@ -222,15 +284,14 @@ public: current = places[current].path.next_sibling; } } - return add_place ({kind, id, Place::Path{parent, 0, 0}, is_type_copy (tyty), - NO_LIFETIME, tyty}, + return add_place ({kind, (uint32_t) id, Place::Path{parent, 0, 0}, + is_type_copy (tyty), tyty}, current); } PlaceId add_temporary (TyTy::BaseType *tyty) { - return add_place ( - {Place::TEMPORARY, 0, {}, is_type_copy (tyty), NO_LIFETIME, tyty}, 0); + return add_place ({Place::TEMPORARY, 0, {}, is_type_copy (tyty), tyty}, 0); } PlaceId get_constant (TyTy::BaseType *tyty) @@ -238,11 +299,7 @@ public: auto lookup = constants_lookup.find (tyty); if (lookup != constants_lookup.end ()) return lookup->second; - Lifetime lifetime - = tyty->get_kind () == TyTy::REF ? STATIC_LIFETIME : NO_LIFETIME; - Place place = {Place::CONSTANT, 0, {}, is_type_copy (tyty), lifetime, tyty}; - places.push_back (place); - return places.size () - 1; + return add_place ({Place::CONSTANT, 0, {}, is_type_copy (tyty), tyty}); } PlaceId lookup_variable (NodeId id) @@ -257,15 +314,46 @@ public: current++; } return INVALID_PLACE; - }; + } + + LoanId add_loan (Loan &&loan) + { + LoanId id = loans.size (); + loans.push_back (std::forward (loan)); + PlaceId borrowed_place = loans.rbegin ()->place; + places[loans.rbegin ()->place].borrowed_by.push_back (id); + if (places[borrowed_place].kind == Place::DEREF) + { + places[places[borrowed_place].path.parent].borrowed_by.push_back (id); + } + return id; + } + + PlaceId get_var (PlaceId id) const + { + if (places[id].is_var ()) + return id; + rust_assert (places[id].is_path ()); + PlaceId current = id; + while (!places[current].is_var ()) + { + current = places[current].path.parent; + } + return current; + } + + void set_next_free_region (Polonius::Origin next_free_region) + { + this->next_free_region = next_free_region; + } PlaceId lookup_or_add_variable (NodeId id, TyTy::BaseType *tyty) { auto lookup = lookup_variable (id); if (lookup != INVALID_PLACE) return lookup; - add_place ( - {Place::VARIABLE, id, {}, is_type_copy (tyty), NO_LIFETIME, tyty}); + + add_place ({Place::VARIABLE, id, {}, is_type_copy (tyty), tyty}); return places.size () - 1; }; @@ -298,6 +386,7 @@ private: switch (ty->get_kind ()) { case TyTy::REF: + return ty->as ()->mutability () == Mutability::Imm; case TyTy::POINTER: case TyTy::SLICE: case TyTy::BOOL: @@ -335,6 +424,21 @@ private: } rust_unreachable (); } + + /** Check whether given place is not out-of-scope. */ + WARN_UNUSED_RESULT bool is_in_scope (PlaceId place) const + { + for (ScopeId scope = current_scope; scope != INVALID_SCOPE; + scope = scopes[scope].parent) + { + auto &scope_ref = scopes[scope]; + if (std::find (scope_ref.locals.begin (), scope_ref.locals.end (), + place) + != scope_ref.locals.end ()) + return true; + } + return false; + } }; } // namespace BIR diff --git a/gcc/rust/checks/errors/borrowck/rust-bir.h b/gcc/rust/checks/errors/borrowck/rust-bir.h index d21cb90abf5..4c298f14773 100644 --- a/gcc/rust/checks/errors/borrowck/rust-bir.h +++ b/gcc/rust/checks/errors/borrowck/rust-bir.h @@ -22,6 +22,9 @@ #include "rust-bir-place.h" #include "rust-bir-visitor.h" +#include "polonius/rust-polonius-ffi.h" +#include "rust-tyty-variance-analysis.h" + namespace Rust { namespace BIR { @@ -30,6 +33,8 @@ struct BasicBlock; class Statement; class AbstractExpr; +using LoanId = uint32_t; + /** * Top-level entity of the Borrow-checker IR (BIR). * It represents a single function (method, closure, etc.), which is the @@ -40,6 +45,9 @@ struct Function PlaceDB place_db; std::vector arguments; std::vector basic_blocks; + FreeRegions universal_regions; + std::vector> universal_region_bounds; + location_t location; }; /** Single statement of BIR. */ @@ -48,12 +56,14 @@ class Statement public: enum class Kind { - ASSIGNMENT, // = - SWITCH, // switch - RETURN, // return - GOTO, // goto - STORAGE_DEAD, // StorageDead() - STORAGE_LIVE, // StorageLive() + ASSIGNMENT, // = + SWITCH, // switch + RETURN, // return + GOTO, // goto + STORAGE_DEAD, // StorageDead() + STORAGE_LIVE, // StorageLive() + USER_TYPE_ASCRIPTION, // UserTypeAscription(, ) + FAKE_READ, }; private: @@ -66,6 +76,7 @@ private: // ASSIGNMENT: rhs // otherwise: std::unique_ptr expr; + TyTy::BaseType *type; public: Statement (PlaceId lhs, AbstractExpr *rhs) @@ -77,10 +88,15 @@ public: : kind (kind), place (place), expr (expr) {} + explicit Statement (Kind kind, PlaceId place, TyTy::BaseType *type) + : kind (kind), place (place), type (type) + {} + public: WARN_UNUSED_RESULT Kind get_kind () const { return kind; } WARN_UNUSED_RESULT PlaceId get_place () const { return place; } WARN_UNUSED_RESULT AbstractExpr &get_expr () const { return *expr; } + WARN_UNUSED_RESULT TyTy::BaseType *get_type () const { return type; } }; /** Unique identifier for a basic block in the BIR. */ @@ -122,7 +138,7 @@ class AbstractExpr : public Visitable public: explicit AbstractExpr (ExprKind kind) : kind (kind) {} - [[nodiscard]] ExprKind get_kind () const { return kind; } + WARN_UNUSED_RESULT ExprKind get_kind () const { return kind; } }; class InitializerExpr : public VisitableImpl @@ -165,12 +181,17 @@ public: class BorrowExpr : public VisitableImpl { PlaceId place; + LoanId loan; + Polonius::Origin origin; public: - explicit BorrowExpr (PlaceId place) - : VisitableImpl (ExprKind::BORROW), place (place) + explicit BorrowExpr (PlaceId place, LoanId loan_id, Polonius::Origin lifetime) + : VisitableImpl (ExprKind::BORROW), place (place), + loan (loan_id), origin (lifetime) {} WARN_UNUSED_RESULT PlaceId get_place () const { return place; } + WARN_UNUSED_RESULT LoanId get_loan () const { return loan; } + WARN_UNUSED_RESULT Polonius::Origin get_origin () const { return origin; } }; /** @@ -191,19 +212,21 @@ public: WARN_UNUSED_RESULT PlaceId get_rhs () const { return rhs; } }; -class CallExpr : public VisitableImpl +class CallExpr final : public VisitableImpl { std::vector arguments; PlaceId callable; public: explicit CallExpr (PlaceId callable, std::vector &&arguments) - : VisitableImpl (ExprKind::CALL), - arguments (arguments), callable (callable) + : VisitableImpl (ExprKind::CALL), arguments (arguments), callable (callable) {} public: - const std::vector &get_arguments () const { return arguments; } + WARN_UNUSED_RESULT const std::vector &get_arguments () const + { + return arguments; + } WARN_UNUSED_RESULT PlaceId get_callable () const { return callable; } }; -- 2.45.2