// Copyright (C) 2021-2024 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
// .
#include "rust-hir-type-bounds.h"
#include "rust-hir-trait-resolve.h"
#include "rust-substitution-mapper.h"
#include "rust-type-util.h"
namespace Rust {
namespace Resolver {
TypeBoundsProbe::TypeBoundsProbe (const TyTy::BaseType *receiver)
: TypeCheckBase (), receiver (receiver)
{}
std::vector>
TypeBoundsProbe::Probe (const TyTy::BaseType *receiver)
{
TypeBoundsProbe probe (receiver);
probe.scan ();
return probe.trait_references;
}
bool
TypeBoundsProbe::is_bound_satisfied_for_type (TyTy::BaseType *receiver,
TraitReference *ref)
{
for (auto &bound : receiver->get_specified_bounds ())
{
const TraitReference *b = bound.get ();
if (b->is_equal (*ref))
return true;
}
std::vector> bounds
= Probe (receiver);
for (auto &bound : bounds)
{
const TraitReference *b = bound.first;
if (b->is_equal (*ref))
return true;
}
return false;
}
void
TypeBoundsProbe::scan ()
{
std::vector>
possible_trait_paths;
mappings->iterate_impl_blocks (
[&] (HirId id, HIR::ImplBlock *impl) mutable -> bool {
// we are filtering for trait-impl-blocks
if (!impl->has_trait_ref ())
return true;
HirId impl_ty_id = impl->get_type ()->get_mappings ().get_hirid ();
TyTy::BaseType *impl_type = nullptr;
if (!query_type (impl_ty_id, &impl_type))
return true;
if (!receiver->can_eq (impl_type, false))
{
if (!impl_type->can_eq (receiver, false))
return true;
}
possible_trait_paths.push_back ({impl->get_trait_ref ().get (), impl});
return true;
});
for (auto &path : possible_trait_paths)
{
HIR::TypePath *trait_path = path.first;
TraitReference *trait_ref = TraitResolver::Resolve (*trait_path);
if (!trait_ref->is_error ())
trait_references.push_back ({trait_ref, path.second});
}
// marker traits...
assemble_sized_builtin ();
}
void
TypeBoundsProbe::assemble_sized_builtin ()
{
const TyTy::BaseType *raw = receiver->destructure ();
// https://runrust.miraheze.org/wiki/Dynamically_Sized_Type
// everything is sized except for:
//
// 1. dyn traits
// 2. slices
// 3. str
// 4. ADT's which contain any of the above
// t. tuples which contain any of the above
switch (raw->get_kind ())
{
case TyTy::ARRAY:
case TyTy::REF:
case TyTy::POINTER:
case TyTy::PARAM:
case TyTy::FNDEF:
case TyTy::FNPTR:
case TyTy::BOOL:
case TyTy::CHAR:
case TyTy::INT:
case TyTy::UINT:
case TyTy::FLOAT:
case TyTy::USIZE:
case TyTy::ISIZE:
case TyTy::CLOSURE:
case TyTy::INFER:
case TyTy::NEVER:
case TyTy::PLACEHOLDER:
case TyTy::PROJECTION:
assemble_builtin_candidate (Analysis::RustLangItem::SIZED);
break;
// FIXME str and slice need to be moved and test cases updated
case TyTy::SLICE:
case TyTy::STR:
case TyTy::ADT:
case TyTy::TUPLE:
// FIXME add extra checks
assemble_builtin_candidate (Analysis::RustLangItem::SIZED);
break;
case TyTy::DYNAMIC:
case TyTy::ERROR:
break;
}
}
void
TypeBoundsProbe::assemble_builtin_candidate (
Analysis::RustLangItem::ItemType lang_item)
{
DefId id;
bool found_lang_item = mappings->lookup_lang_item (lang_item, &id);
if (!found_lang_item)
return;
HIR::Item *item = mappings->lookup_defid (id);
if (item == nullptr)
return;
rust_assert (item->get_item_kind () == HIR::Item::ItemKind::Trait);
HIR::Trait *trait = static_cast (item);
const TyTy::BaseType *raw = receiver->destructure ();
// assemble the reference
TraitReference *trait_ref = TraitResolver::Resolve (*trait);
trait_references.push_back ({trait_ref, mappings->lookup_builtin_marker ()});
rust_debug ("Added builtin lang_item: %s for %s",
Analysis::RustLangItem::ToString (lang_item).c_str (),
raw->get_name ().c_str ());
}
TraitReference *
TypeCheckBase::resolve_trait_path (HIR::TypePath &path)
{
return TraitResolver::Resolve (path);
}
TyTy::TypeBoundPredicate
TypeCheckBase::get_predicate_from_bound (HIR::TypePath &type_path,
HIR::Type *associated_self,
BoundPolarity polarity)
{
TyTy::TypeBoundPredicate lookup = TyTy::TypeBoundPredicate::error ();
bool already_resolved
= context->lookup_predicate (type_path.get_mappings ().get_hirid (),
&lookup);
if (already_resolved)
return lookup;
TraitReference *trait = resolve_trait_path (type_path);
if (trait->is_error ())
return TyTy::TypeBoundPredicate::error ();
TyTy::TypeBoundPredicate predicate (*trait, polarity, type_path.get_locus ());
HIR::GenericArgs args
= HIR::GenericArgs::create_empty (type_path.get_locus ());
auto &final_seg = type_path.get_final_segment ();
switch (final_seg->get_type ())
{
case HIR::TypePathSegment::SegmentType::GENERIC: {
auto final_generic_seg
= static_cast (final_seg.get ());
if (final_generic_seg->has_generic_args ())
{
args = final_generic_seg->get_generic_args ();
}
}
break;
case HIR::TypePathSegment::SegmentType::FUNCTION: {
auto final_function_seg
= static_cast (final_seg.get ());
auto &fn = final_function_seg->get_function_path ();
// we need to make implicit generic args which must be an implicit
// Tuple
auto crate_num = mappings->get_current_crate ();
HirId implicit_args_id = mappings->get_next_hir_id ();
Analysis::NodeMapping mapping (crate_num,
final_seg->get_mappings ().get_nodeid (),
implicit_args_id, UNKNOWN_LOCAL_DEFID);
std::vector> params_copy;
for (auto &p : fn.get_params ())
{
params_copy.push_back (p->clone_type ());
}
HIR::TupleType *implicit_tuple
= new HIR::TupleType (mapping, std::move (params_copy),
final_seg->get_locus ());
std::vector> inputs;
inputs.push_back (std::unique_ptr (implicit_tuple));
// resolve the fn_once_output type which assumes there must be an output
// set
rust_assert (fn.has_return_type ());
TypeCheckType::Resolve (fn.get_return_type ().get ());
HIR::TraitItem *trait_item = mappings->lookup_trait_item_lang_item (
Analysis::RustLangItem::ItemType::FN_ONCE_OUTPUT,
final_seg->get_locus ());
std::vector bindings;
location_t output_locus = fn.get_return_type ()->get_locus ();
HIR::GenericArgsBinding binding (Identifier (
trait_item->trait_identifier ()),
fn.get_return_type ()->clone_type (),
output_locus);
bindings.push_back (std::move (binding));
args = HIR::GenericArgs ({} /* lifetimes */,
std::move (inputs) /* type_args*/,
std::move (bindings) /* binding_args*/,
{} /* const_args */, final_seg->get_locus ());
}
break;
default:
/* nothing to do */
break;
}
if (associated_self != nullptr)
{
std::vector> type_args;
type_args.push_back (
std::unique_ptr (associated_self->clone_type ()));
for (auto &arg : args.get_type_args ())
{
type_args.push_back (std::unique_ptr (arg->clone_type ()));
}
args = HIR::GenericArgs (args.get_lifetime_args (), std::move (type_args),
args.get_binding_args (), args.get_const_args (),
args.get_locus ());
}
// we try to apply generic arguments when they are non empty and or when the
// predicate requires them so that we get the relevant Foo expects x number
// arguments but got zero see test case rust/compile/traits12.rs
if (!args.is_empty () || predicate.requires_generic_args ())
{
// this is applying generic arguments to a trait reference
predicate.apply_generic_arguments (&args, associated_self != nullptr);
}
context->insert_resolved_predicate (type_path.get_mappings ().get_hirid (),
predicate);
return predicate;
}
} // namespace Resolver
namespace TyTy {
TypeBoundPredicate::TypeBoundPredicate (
const Resolver::TraitReference &trait_reference, BoundPolarity polarity,
location_t locus)
: SubstitutionRef ({}, SubstitutionArgumentMappings::empty ()),
reference (trait_reference.get_mappings ().get_defid ()), locus (locus),
error_flag (false), polarity (polarity)
{
rust_assert (!trait_reference.get_trait_substs ().empty ());
substitutions.clear ();
for (const auto &p : trait_reference.get_trait_substs ())
substitutions.push_back (p.clone ());
// we setup a dummy implict self argument
SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
used_arguments.get_mappings ().push_back (placeholder_self);
}
TypeBoundPredicate::TypeBoundPredicate (
DefId reference, std::vector subst,
BoundPolarity polarity, location_t locus)
: SubstitutionRef ({}, SubstitutionArgumentMappings::empty ()),
reference (reference), locus (locus), error_flag (false),
polarity (polarity)
{
rust_assert (!subst.empty ());
substitutions.clear ();
for (const auto &p : subst)
substitutions.push_back (p.clone ());
// we setup a dummy implict self argument
SubstitutionArg placeholder_self (&get_substs ().front (), nullptr);
used_arguments.get_mappings ().push_back (placeholder_self);
}
TypeBoundPredicate::TypeBoundPredicate (mark_is_error)
: SubstitutionRef ({}, SubstitutionArgumentMappings::empty ()),
reference (UNKNOWN_DEFID), locus (UNDEF_LOCATION), error_flag (true),
polarity (BoundPolarity::RegularBound)
{}
TypeBoundPredicate::TypeBoundPredicate (const TypeBoundPredicate &other)
: SubstitutionRef ({}, SubstitutionArgumentMappings::empty ()),
reference (other.reference), locus (other.locus),
error_flag (other.error_flag), polarity (other.polarity)
{
substitutions.clear ();
for (const auto &p : other.get_substs ())
substitutions.push_back (p.clone ());
std::vector mappings;
for (size_t i = 0; i < other.used_arguments.get_mappings ().size (); i++)
{
const SubstitutionArg &oa = other.used_arguments.get_mappings ().at (i);
SubstitutionArg arg (oa);
mappings.push_back (std::move (arg));
}
// we need to remap the argument mappings based on this copied constructor
std::vector copied_arg_mappings;
size_t i = 0;
for (const auto &m : other.used_arguments.get_mappings ())
{
TyTy::BaseType *argument
= m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
SubstitutionArg c (&substitutions.at (i++), argument);
copied_arg_mappings.push_back (std::move (c));
}
used_arguments
= SubstitutionArgumentMappings (copied_arg_mappings, {},
other.used_arguments.get_locus ());
}
TypeBoundPredicate &
TypeBoundPredicate::operator= (const TypeBoundPredicate &other)
{
reference = other.reference;
locus = other.locus;
error_flag = other.error_flag;
polarity = other.polarity;
used_arguments = SubstitutionArgumentMappings::empty ();
substitutions.clear ();
for (const auto &p : other.get_substs ())
substitutions.push_back (p.clone ());
if (other.is_error ())
return *this;
std::vector mappings;
for (size_t i = 0; i < other.used_arguments.get_mappings ().size (); i++)
{
const SubstitutionArg &oa = other.used_arguments.get_mappings ().at (i);
SubstitutionArg arg (oa);
mappings.push_back (std::move (arg));
}
// we need to remap the argument mappings based on this copied constructor
std::vector copied_arg_mappings;
size_t i = 0;
for (const auto &m : other.used_arguments.get_mappings ())
{
TyTy::BaseType *argument
= m.get_tyty () == nullptr ? nullptr : m.get_tyty ()->clone ();
SubstitutionArg c (&substitutions.at (i++), argument);
copied_arg_mappings.push_back (std::move (c));
}
used_arguments
= SubstitutionArgumentMappings (copied_arg_mappings, {},
other.used_arguments.get_locus ());
return *this;
}
TypeBoundPredicate
TypeBoundPredicate::error ()
{
return TypeBoundPredicate (mark_is_error ());
}
std::string
TypeBoundPredicate::as_string () const
{
return get ()->as_string () + subst_as_string ();
}
std::string
TypeBoundPredicate::as_name () const
{
return get ()->get_name () + subst_as_string ();
}
const Resolver::TraitReference *
TypeBoundPredicate::get () const
{
auto context = Resolver::TypeCheckContext::get ();
Resolver::TraitReference *ref = nullptr;
bool ok = context->lookup_trait_reference (reference, &ref);
rust_assert (ok);
return ref;
}
std::string
TypeBoundPredicate::get_name () const
{
return get ()->get_name ();
}
bool
TypeBoundPredicate::is_object_safe (bool emit_error, location_t locus) const
{
const Resolver::TraitReference *trait = get ();
rust_assert (trait != nullptr);
return trait->is_object_safe (emit_error, locus);
}
void
TypeBoundPredicate::apply_generic_arguments (HIR::GenericArgs *generic_args,
bool has_associated_self)
{
rust_assert (!substitutions.empty ());
if (has_associated_self)
{
used_arguments = SubstitutionArgumentMappings::empty ();
}
else
{
// we need to get the substitutions argument mappings but also remember
// that we have an implicit Self argument which we must be careful to
// respect
rust_assert (!used_arguments.is_empty ());
}
// now actually perform a substitution
used_arguments = get_mappings_from_generic_args (*generic_args);
error_flag |= used_arguments.is_error ();
auto &subst_mappings = used_arguments;
for (auto &sub : get_substs ())
{
SubstitutionArg arg = SubstitutionArg::error ();
bool ok
= subst_mappings.get_argument_for_symbol (sub.get_param_ty (), &arg);
if (ok && arg.get_tyty () != nullptr)
sub.fill_param_ty (subst_mappings, subst_mappings.get_locus ());
}
// associated argument mappings
for (auto &it : subst_mappings.get_binding_args ())
{
std::string identifier = it.first;
TyTy::BaseType *type = it.second;
TypeBoundPredicateItem item = lookup_associated_item (identifier);
rust_assert (!item.is_error ());
const auto item_ref = item.get_raw_item ();
item_ref->associated_type_set (type);
}
}
bool
TypeBoundPredicate::contains_item (const std::string &search) const
{
auto trait_ref = get ();
const Resolver::TraitItemReference *trait_item_ref = nullptr;
return trait_ref->lookup_trait_item (search, &trait_item_ref);
}
TypeBoundPredicateItem
TypeBoundPredicate::lookup_associated_item (const std::string &search) const
{
auto trait_ref = get ();
const Resolver::TraitItemReference *trait_item_ref = nullptr;
if (!trait_ref->lookup_trait_item (search, &trait_item_ref))
return TypeBoundPredicateItem::error ();
return TypeBoundPredicateItem (this, trait_item_ref);
}
TypeBoundPredicateItem::TypeBoundPredicateItem (
const TypeBoundPredicate *parent,
const Resolver::TraitItemReference *trait_item_ref)
: parent (parent), trait_item_ref (trait_item_ref)
{}
TypeBoundPredicateItem
TypeBoundPredicateItem::error ()
{
return TypeBoundPredicateItem (nullptr, nullptr);
}
bool
TypeBoundPredicateItem::is_error () const
{
return parent == nullptr || trait_item_ref == nullptr;
}
const TypeBoundPredicate *
TypeBoundPredicateItem::get_parent () const
{
return parent;
}
TypeBoundPredicateItem
TypeBoundPredicate::lookup_associated_item (
const Resolver::TraitItemReference *ref) const
{
return lookup_associated_item (ref->get_identifier ());
}
BaseType *
TypeBoundPredicateItem::get_tyty_for_receiver (const TyTy::BaseType *receiver)
{
TyTy::BaseType *trait_item_tyty = get_raw_item ()->get_tyty ();
if (parent->get_substitution_arguments ().is_empty ())
return trait_item_tyty;
const Resolver::TraitItemReference *tref = get_raw_item ();
bool is_associated_type = tref->get_trait_item_type ();
if (is_associated_type)
return trait_item_tyty;
// set up the self mapping
SubstitutionArgumentMappings gargs = parent->get_substitution_arguments ();
rust_assert (!gargs.is_empty ());
// setup the adjusted mappings
std::vector adjusted_mappings;
for (size_t i = 0; i < gargs.get_mappings ().size (); i++)
{
auto &mapping = gargs.get_mappings ().at (i);
bool is_implicit_self = i == 0;
TyTy::BaseType *argument
= is_implicit_self ? receiver->clone () : mapping.get_tyty ();
SubstitutionArg arg (mapping.get_param_mapping (), argument);
adjusted_mappings.push_back (std::move (arg));
}
SubstitutionArgumentMappings adjusted (adjusted_mappings, {},
gargs.get_locus (),
gargs.get_subst_cb (),
true /* trait-mode-flag */);
return Resolver::SubstMapperInternal::Resolve (trait_item_tyty, adjusted);
}
bool
TypeBoundPredicate::is_error () const
{
auto context = Resolver::TypeCheckContext::get ();
Resolver::TraitReference *ref = nullptr;
bool ok = context->lookup_trait_reference (reference, &ref);
return !ok || error_flag;
}
BaseType *
TypeBoundPredicate::handle_substitions (
SubstitutionArgumentMappings &subst_mappings)
{
for (auto &sub : get_substs ())
{
if (sub.get_param_ty () == nullptr)
continue;
ParamType *p = sub.get_param_ty ();
BaseType *r = p->resolve ();
BaseType *s = Resolver::SubstMapperInternal::Resolve (r, subst_mappings);
p->set_ty_ref (s->get_ty_ref ());
}
// associated argument mappings
for (auto &it : subst_mappings.get_binding_args ())
{
std::string identifier = it.first;
TyTy::BaseType *type = it.second;
TypeBoundPredicateItem item = lookup_associated_item (identifier);
if (!item.is_error ())
{
const auto item_ref = item.get_raw_item ();
item_ref->associated_type_set (type);
}
}
// FIXME more error handling at some point
// used_arguments = subst_mappings;
// error_flag |= used_arguments.is_error ();
return nullptr;
}
bool
TypeBoundPredicate::requires_generic_args () const
{
if (is_error ())
return false;
return substitutions.size () > 1;
}
bool
TypeBoundPredicate::contains_associated_types () const
{
return get_num_associated_bindings () > 0;
}
size_t
TypeBoundPredicate::get_num_associated_bindings () const
{
size_t count = 0;
auto trait_ref = get ();
for (const auto &trait_item : trait_ref->get_trait_items ())
{
bool is_associated_type
= trait_item.get_trait_item_type ()
== Resolver::TraitItemReference::TraitItemType::TYPE;
if (is_associated_type)
count++;
}
return count;
}
TypeBoundPredicateItem
TypeBoundPredicate::lookup_associated_type (const std::string &search)
{
TypeBoundPredicateItem item = lookup_associated_item (search);
// only need to check that it is infact an associated type because other
// wise if it was not found it will just be an error node anyway
if (!item.is_error ())
{
const auto raw = item.get_raw_item ();
if (raw->get_trait_item_type ()
!= Resolver::TraitItemReference::TraitItemType::TYPE)
return TypeBoundPredicateItem::error ();
}
return item;
}
std::vector
TypeBoundPredicate::get_associated_type_items ()
{
std::vector items;
auto trait_ref = get ();
for (const auto &trait_item : trait_ref->get_trait_items ())
{
bool is_associated_type
= trait_item.get_trait_item_type ()
== Resolver::TraitItemReference::TraitItemType::TYPE;
if (is_associated_type)
{
TypeBoundPredicateItem item (this, &trait_item);
items.push_back (std::move (item));
}
}
return items;
}
bool
TypeBoundPredicate::is_equal (const TypeBoundPredicate &other) const
{
// check they match the same trait reference
if (reference != other.reference)
return false;
// check that the generics match
if (get_num_substitutions () != other.get_num_substitutions ())
return false;
// then match the generics applied
for (size_t i = 0; i < get_num_substitutions (); i++)
{
const SubstitutionParamMapping &a = substitutions.at (i);
const SubstitutionParamMapping &b = other.substitutions.at (i);
const ParamType *ap = a.get_param_ty ();
const ParamType *bp = b.get_param_ty ();
const BaseType *apd = ap->destructure ();
const BaseType *bpd = bp->destructure ();
// FIXME use the unify_and infer inteface or try coerce
if (!apd->can_eq (bpd, false /*emit_errors*/))
{
if (!bpd->can_eq (apd, false /*emit_errors*/))
return false;
}
}
return true;
}
// trait item reference
const Resolver::TraitItemReference *
TypeBoundPredicateItem::get_raw_item () const
{
return trait_item_ref;
}
bool
TypeBoundPredicateItem::needs_implementation () const
{
return !get_raw_item ()->is_optional ();
}
location_t
TypeBoundPredicateItem::get_locus () const
{
return get_raw_item ()->get_locus ();
}
// TypeBoundsMappings
TypeBoundsMappings::TypeBoundsMappings (
std::vector specified_bounds)
: specified_bounds (specified_bounds)
{}
std::vector &
TypeBoundsMappings::get_specified_bounds ()
{
return specified_bounds;
}
const std::vector &
TypeBoundsMappings::get_specified_bounds () const
{
return specified_bounds;
}
TypeBoundPredicate
TypeBoundsMappings::lookup_predicate (DefId id)
{
for (auto &b : specified_bounds)
{
if (b.get_id () == id)
return b;
}
return TypeBoundPredicate::error ();
}
size_t
TypeBoundsMappings::num_specified_bounds () const
{
return specified_bounds.size ();
}
std::string
TypeBoundsMappings::raw_bounds_as_string () const
{
std::string buf;
for (size_t i = 0; i < specified_bounds.size (); i++)
{
const TypeBoundPredicate &b = specified_bounds.at (i);
bool has_next = (i + 1) < specified_bounds.size ();
buf += b.as_string () + (has_next ? " + " : "");
}
return buf;
}
std::string
TypeBoundsMappings::bounds_as_string () const
{
return "bounds:[" + raw_bounds_as_string () + "]";
}
std::string
TypeBoundsMappings::raw_bounds_as_name () const
{
std::string buf;
for (size_t i = 0; i < specified_bounds.size (); i++)
{
const TypeBoundPredicate &b = specified_bounds.at (i);
bool has_next = (i + 1) < specified_bounds.size ();
buf += b.as_name () + (has_next ? " + " : "");
}
return buf;
}
void
TypeBoundsMappings::add_bound (TypeBoundPredicate predicate)
{
for (auto &bound : specified_bounds)
{
bool same_trait_ref_p = bound.get_id () == predicate.get_id ();
if (same_trait_ref_p)
return;
}
specified_bounds.push_back (predicate);
}
} // namespace TyTy
} // namespace Rust