From 60dae965fdb55552d9328356dcfa36c015c6ef83 Mon Sep 17 00:00:00 2001 From: John Hodge Date: Wed, 1 Apr 2015 22:19:24 +0800 Subject: More work on wildcard impls --- src/ast/ast.cpp | 172 ++++++++++++++++++++++++++++---------------- src/ast/ast.hpp | 57 +++++++++------ src/ast/provided_module.cpp | 7 +- src/convert/ast_iterate.cpp | 12 +++- src/convert/ast_iterate.hpp | 4 ++ src/dump_as_rust.cpp | 10 +-- src/parse/common.hpp | 2 +- src/parse/expr.cpp | 2 +- src/parse/root.cpp | 15 ++-- src/types.cpp | 2 +- 10 files changed, 176 insertions(+), 107 deletions(-) (limited to 'src') diff --git a/src/ast/ast.cpp b/src/ast/ast.cpp index 0ebc3e4e..8a598977 100644 --- a/src/ast/ast.cpp +++ b/src/ast/ast.cpp @@ -38,59 +38,17 @@ SERIALISE_TYPE(MetaItem::, "AST_MetaItem", { s.item(m_sub_items); }) - -Impl Impl::make_concrete(const ::std::vector& types) const +bool ImplDef::matches(::std::vector& out_types, const Path& trait, const TypeRef& type) const { - DEBUG("types={" << types << "}"); - throw ParseError::Todo("Impl::make_concrete"); -/* - INDENT(); - - assert(m_params.n_params()); - - Impl ret( TypeParams(), m_trait, m_type ); - - auto resolver = [&](const char *name) { - int idx = m_params.find_name(name); - assert(idx >= 0); - return types[idx]; - }; - - ret.m_trait.resolve_args(resolver); - ret.m_type.resolve_args(resolver); - - for(const auto& fcn : m_functions) - { - TypeParams new_fcn_params = fcn.data.params(); - for( auto& b : new_fcn_params.bounds() ) - b.type().resolve_args(resolver); - TypeRef new_ret_type = fcn.data.rettype(); - new_ret_type.resolve_args(resolver); - Function::Arglist new_args = fcn.data.args(); - for( auto& t : new_args ) - t.second.resolve_args(resolver); - - ret.add_function( fcn.is_pub, fcn.name, Function( ::std::move(new_fcn_params), fcn.data.fcn_class(), ::std::move(new_ret_type), ::std::move(new_args), Expr() ) ); - } - - UNINDENT(); - return ret; -*/ -} - -::rust::option Impl::matches(const Path& trait, const TypeRef& type) -{ - //DEBUG("this = " << *this); - // 1. Check the type/trait counting parameters as wildcards (but flagging if one was seen) // > If that fails, just early return int trait_match = m_trait.equal_no_generic(trait); if( trait_match < 0 ) - return ::rust::option(); + return false; DEBUG("Trait " << trait << " matches " << trait_match); int type_match = m_type.equal_no_generic(type); if( type_match < 0 ) - return ::rust::option(); + return false; DEBUG("Type " << type << " matches " << type_match); // 2. If a parameter was seen, do the more expensive generic checks @@ -100,10 +58,12 @@ Impl Impl::make_concrete(const ::std::vector& types) const if( trait_match == 0 && type_match == 0 ) throw CompileError::Generic( "Unbound generic in impl" ); } - + + // If there was a fuzzy match, then make it less fuzzy. if( !(trait_match == 0 && type_match == 0) ) { - ::std::vector param_types(m_params.ty_params().size()); + out_types.clear(); + out_types.resize(m_params.ty_params().size()); try { auto c = [&](const char* name,const TypeRef& ty) { @@ -114,8 +74,8 @@ Impl Impl::make_concrete(const ::std::vector& types) const } int idx = m_params.find_name(name); assert( idx >= 0 ); - assert( (unsigned)idx < param_types.size() ); - param_types[idx].merge_with( ty ); + assert( (unsigned)idx < out_types.size() ); + out_types[idx].merge_with( ty ); }; m_trait.match_args(trait, c); m_type.match_args(type, c); @@ -123,9 +83,41 @@ Impl Impl::make_concrete(const ::std::vector& types) const catch(const CompileError::Base& e) { DEBUG("No match - " << e.what()); - return ::rust::option(); + return false; } - + + // TODO: Validate params against bounds? + } + + // Perfect match + return true; +} +::std::ostream& operator<<(::std::ostream& os, const ImplDef& impl) +{ + return os << "impl<" << impl.m_params << "> " << impl.m_trait << " for " << impl.m_type << ""; +} +SERIALISE_TYPE(ImplDef::, "AST_ImplDef", { + s << m_params; + s << m_trait; + s << m_type; +},{ + s.item(m_params); + s.item(m_trait); + s.item(m_type); +}) + + +::rust::option Impl::matches(const Path& trait, const TypeRef& type) +{ + //DEBUG("this = " << *this); + ::std::vector param_types; + + if( m_def.matches(param_types, trait, type) == false ) + { + return ::rust::option(); + } + else + { if( param_types.size() > 0 ) { for( auto& i : m_concrete_impls ) @@ -143,19 +135,54 @@ Impl Impl::make_concrete(const ::std::vector& types) const return ::rust::option( *this ); } +Impl Impl::make_concrete(const ::std::vector& types) const +{ + DEBUG("types={" << types << "}"); + throw ParseError::Todo("Impl::make_concrete"); +/* + INDENT(); + + assert(m_params.n_params()); + + Impl ret( TypeParams(), m_trait, m_type ); + + auto resolver = [&](const char *name) { + int idx = m_params.find_name(name); + assert(idx >= 0); + return types[idx]; + }; + + ret.m_trait.resolve_args(resolver); + ret.m_type.resolve_args(resolver); + + for(const auto& fcn : m_functions) + { + TypeParams new_fcn_params = fcn.data.params(); + for( auto& b : new_fcn_params.bounds() ) + b.type().resolve_args(resolver); + TypeRef new_ret_type = fcn.data.rettype(); + new_ret_type.resolve_args(resolver); + Function::Arglist new_args = fcn.data.args(); + for( auto& t : new_args ) + t.second.resolve_args(resolver); + + ret.add_function( fcn.is_pub, fcn.name, Function( ::std::move(new_fcn_params), fcn.data.fcn_class(), ::std::move(new_ret_type), ::std::move(new_args), Expr() ) ); + } + + UNINDENT(); + return ret; +*/ +} + ::std::ostream& operator<<(::std::ostream& os, const Impl& impl) { - return os << "impl<" << impl.m_params << "> " << impl.m_trait << " for " << impl.m_type << ""; + return os << impl.m_def; } SERIALISE_TYPE(Impl::, "AST_Impl", { - s << m_params; - s << m_trait; - s << m_type; + s << m_def; s << m_functions; },{ - s.item(m_params); - s.item(m_trait); - s.item(m_type); + s.item(m_def); s.item(m_functions); }) @@ -201,17 +228,36 @@ const Module& Crate::get_root_module(const ::std::string& name) const { throw ParseError::Generic("crate name unknown"); } +#if 0 +bool Crate::check_impls_wildcard(const Path& trait, const TypeRef& type) +{ + // 1. Look for a negative impl for this type + // 2. Look for a positive impl for this type (i.e. an unsafe impl) + // If none found, destructure the type + // - structs need all fields to impl this trait (cache result) + // - +} +#endif + ::rust::option Crate::find_impl(const Path& trait, const TypeRef& type) { // TODO: Do a sort to allow a binary search DEBUG("trait = " << trait << ", type = " << type); - // TODO: Support autoderef here? NO - if( trait == Path() && !type.is_path() ) + for( auto implptr : m_impl_index ) { - // You can only have 'impl { }' for user-defined types (i.e. paths) - // - Return failure - return ::rust::option(); + Impl& impl = *implptr; + ::rust::option oimpl = impl.matches(trait, TypeRef()); + if( oimpl.is_some() ) + { + // This is a wildcard trait, need to locate either a negative, or check contents + //if( check_impls_wildcard(trait, type) ) + //{ + // return ::rust::option(oimpl); + //} + throw CompileError::Todo("wildcard impls"); + } + } for( auto implptr : m_impl_index ) diff --git a/src/ast/ast.hpp b/src/ast/ast.hpp index 182652cc..ff798fed 100644 --- a/src/ast/ast.hpp +++ b/src/ast/ast.hpp @@ -435,33 +435,48 @@ public: SERIALISABLE_PROTOTYPES(); }; -class Impl: +class ImplDef: public Serialisable { TypeParams m_params; Path m_trait; TypeRef m_type; +public: + ImplDef() {} + ImplDef(TypeParams params, Path trait_type, TypeRef impl_type): + m_params( move(params) ), + m_trait( move(trait_type) ), + m_type( move(impl_type) ) + {} + + // Accessors + const TypeParams& params() const { return m_params; } + const Path& trait() const { return m_trait; } + const TypeRef& type() const { return m_type; } + TypeParams& params() { return m_params; } + Path& trait() { return m_trait; } + TypeRef& type() { return m_type; } + + /// Compare this impl against a trait,type pair + bool matches(::std::vector& types, const Path& trait, const TypeRef& type) const; + + friend ::std::ostream& operator<<(::std::ostream& os, const ImplDef& impl); + SERIALISABLE_PROTOTYPES(); +}; + +class Impl: + public Serialisable +{ + ImplDef m_def; - bool m_is_negative; ItemList m_types; ItemList m_functions; ::std::vector< ::std::pair< ::std::vector, Impl > > m_concrete_impls; public: - Impl(): m_is_negative(false) {} + Impl() {} Impl(TypeParams params, TypeRef impl_type, Path trait_type): - m_params( move(params) ), - m_trait( move(trait_type) ), - m_type( move(impl_type) ), - m_is_negative(true) - {} - - struct TagNegative {}; - Impl(TagNegative, TypeParams params, TypeRef impl_type, Path trait_type): - m_params( move(params) ), - m_trait( move(trait_type) ), - m_type( move(impl_type) ), - m_is_negative(true) + m_def( move(params), move(trait_type), move(impl_type) ) {} void add_function(bool is_public, ::std::string name, Function fcn) { @@ -471,15 +486,11 @@ public: m_types.push_back( Item( ::std::move(name), ::std::move(type), is_public ) ); } - const TypeParams& params() const { return m_params; } - const Path& trait() const { return m_trait; } - const TypeRef& type() const { return m_type; } + const ImplDef& def() const { return m_def; } const ItemList& functions() const { return m_functions; } const ItemList& types() const { return m_types; } - TypeParams& params() { return m_params; } - Path& trait() { return m_trait; } - TypeRef& type() { return m_type; } + ImplDef& def() { return m_def; } ItemList& functions() { return m_functions; } ItemList& types() { return m_types; } @@ -532,6 +543,7 @@ class Module: itemlist_enum_t m_enums; itemlist_struct_t m_structs; ::std::vector m_impls; + ::std::vector m_neg_impls; public: Module() {} Module(::std::string name): @@ -575,6 +587,9 @@ public: void add_impl(Impl impl) { m_impls.push_back( ::std::move(impl) ); } + void add_neg_impl(ImplDef impl) { + m_neg_impls.push_back( ::std::move(impl) ); + } void add_macro(bool is_exported, ::std::string name, MacroRules macro) { m_macros.push_back( Item( move(name), move(macro), is_exported ) ); } diff --git a/src/ast/provided_module.cpp b/src/ast/provided_module.cpp index 7bea81d4..d82f9716 100644 --- a/src/ast/provided_module.cpp +++ b/src/ast/provided_module.cpp @@ -32,11 +32,10 @@ void AST_InitProvidedModule() g_compiler_module.add_impl(AST::Impl(AST::TypeParams(), TypeRef(), copy_marker_path)); AST::TypeParams tps; tps.add_ty_param( AST::TypeParam("T") ); - g_compiler_module.add_impl(AST::Impl( - AST::Impl::TagNegative(), + g_compiler_module.add_neg_impl(AST::ImplDef( ::std::move(tps), - TypeRef(TypeRef::TagUnsizedArray(), TypeRef(TypeRef::TagArg(), "T")), - copy_marker_path + copy_marker_path, + TypeRef(TypeRef::TagUnsizedArray(), TypeRef(TypeRef::TagArg(), "T")) )); } diff --git a/src/convert/ast_iterate.cpp b/src/convert/ast_iterate.cpp index a80b1f7f..35df8904 100644 --- a/src/convert/ast_iterate.cpp +++ b/src/convert/ast_iterate.cpp @@ -276,10 +276,9 @@ void CASTIterator::handle_function(AST::Path path, AST::Function& fcn) end_scope(); } -void CASTIterator::handle_impl(AST::Path modpath, AST::Impl& impl) + +void CASTIterator::handle_impl_def(AST::ImplDef& impl) { - start_scope(); - // First, so that handle_params can use it local_type("Self", impl.type()); @@ -291,6 +290,13 @@ void CASTIterator::handle_impl(AST::Path modpath, AST::Impl& impl) handle_path( impl.trait(), MODE_TYPE ); // Type handle_type( impl.type() ); +} + +void CASTIterator::handle_impl(AST::Path modpath, AST::Impl& impl) +{ + start_scope(); + + handle_impl_def(impl.def()); // Associated types for( auto& at : impl.types() ) diff --git a/src/convert/ast_iterate.hpp b/src/convert/ast_iterate.hpp index 78f6b271..14537b10 100644 --- a/src/convert/ast_iterate.hpp +++ b/src/convert/ast_iterate.hpp @@ -11,6 +11,7 @@ class ExprNode; class Pattern; class TypeParams; class Impl; +class ImplDef; class EnumVariant; template struct Item; @@ -53,6 +54,9 @@ public: virtual void handle_enum(AST::Path path, AST::Enum& enm); virtual void handle_trait(AST::Path path, AST::Trait& trait); virtual void handle_alias(AST::Path path, AST::TypeAlias& alias); + +private: + void handle_impl_def(AST::ImplDef& impl); }; #endif diff --git a/src/dump_as_rust.cpp b/src/dump_as_rust.cpp index 45c5df5d..0aca6685 100644 --- a/src/dump_as_rust.cpp +++ b/src/dump_as_rust.cpp @@ -635,14 +635,14 @@ void RustPrinter::handle_module(const AST::Module& mod) { m_os << "\n"; m_os << indent() << "impl"; - print_params(i.params()); - if( !(i.trait() == AST::Path()) ) + print_params(i.def().params()); + if( i.def().trait() != AST::Path() ) { - m_os << " " << i.trait() << " for"; + m_os << " " << i.def().trait() << " for"; } - m_os << " " << i.type() << "\n"; + m_os << " " << i.def().type() << "\n"; - print_bounds(i.params()); + print_bounds(i.def().params()); m_os << indent() << "{\n"; inc_indent(); for( const auto& t : i.types() ) diff --git a/src/parse/common.hpp b/src/parse/common.hpp index 0ee430af..de81feb3 100644 --- a/src/parse/common.hpp +++ b/src/parse/common.hpp @@ -44,7 +44,7 @@ extern AST::Pattern Parse_Pattern(TokenStream& lex, bool is_refutable); extern void Parse_Use(TokenStream& lex, ::std::function fcn); extern void Parse_Struct(AST::Module& mod, TokenStream& lex, bool is_public, const AST::MetaItems meta_items); -extern AST::Impl Parse_Impl(TokenStream& lex, bool is_unsafe=false); +extern void Parse_Impl(TokenStream& lex, AST::Module& mod, bool is_unsafe=false); extern void Parse_MacroRules(TokenStream& lex, AST::Module& mod, AST::MetaItems meta_items); extern AST::Function Parse_FunctionDef(TokenStream& lex, ::std::string abi, AST::MetaItems attrs, bool allow_self, bool can_be_prototype); diff --git a/src/parse/expr.cpp b/src/parse/expr.cpp index cd449670..88dc2f5e 100644 --- a/src/parse/expr.cpp +++ b/src/parse/expr.cpp @@ -141,7 +141,7 @@ ExprNodeP Parse_ExprBlockNode(TokenStream& lex) // - 'impl' case TOK_RWORD_IMPL: keep_mod = true; - local_mod->add_impl(Parse_Impl(lex, false)); + Parse_Impl(lex, *local_mod, false); break; // - 'fn' case TOK_RWORD_FN: diff --git a/src/parse/root.cpp b/src/parse/root.cpp index 2beac535..94a21179 100644 --- a/src/parse/root.cpp +++ b/src/parse/root.cpp @@ -631,10 +631,10 @@ AST::MetaItem Parse_MetaItem(TokenStream& lex) } } -AST::Impl Parse_Impl(TokenStream& lex, bool is_unsafe/*=false*/); +void Parse_Impl(TokenStream& lex, AST::Module& mod, bool is_unsafe/*=false*/); void Parse_Impl_Item(TokenStream& lex, AST::Impl& impl); -AST::Impl Parse_Impl(TokenStream& lex, bool is_unsafe/*=false*/) +void Parse_Impl(TokenStream& lex, AST::Module& mod, bool is_unsafe/*=false*/) { TRACE_FUNCTION; Token tok; @@ -670,9 +670,8 @@ AST::Impl Parse_Impl(TokenStream& lex, bool is_unsafe/*=false*/) // negative impls can't have any content GET_CHECK_TOK(tok, lex, TOK_BRACE_CLOSE); - return AST::Impl(AST::Impl::TagNegative(), ::std::move(params), - ::std::move(impl_type), ::std::move(trait_path) - ); + mod.add_neg_impl( AST::ImplDef( ::std::move(params), ::std::move(trait_path), ::std::move(impl_type) ) ); + return ; } else { @@ -723,7 +722,7 @@ AST::Impl Parse_Impl(TokenStream& lex, bool is_unsafe/*=false*/) Parse_Impl_Item(lex, impl); } - return impl; + mod.add_impl( ::std::move(impl) ); } void Parse_Impl_Item(TokenStream& lex, AST::Impl& impl) @@ -1348,7 +1347,7 @@ void Parse_ModRoot_Items(TokenStream& lex, AST::Crate& crate, AST::Module& mod, break; } case TOK_RWORD_IMPL: - mod.add_impl(Parse_Impl(lex, true)); + Parse_Impl(lex, mod, true); break; default: throw ParseError::Unexpected(lex, tok); @@ -1374,7 +1373,7 @@ void Parse_ModRoot_Items(TokenStream& lex, AST::Crate& crate, AST::Module& mod, mod.add_enum(is_public, name, Parse_EnumDef(lex, meta_items)); break; } case TOK_RWORD_IMPL: - mod.add_impl(Parse_Impl(lex)); + Parse_Impl(lex, mod); break; case TOK_RWORD_TRAIT: { GET_CHECK_TOK(tok, lex, TOK_IDENT); diff --git a/src/types.cpp b/src/types.cpp index 329e93f8..4286f828 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -305,7 +305,7 @@ int TypeRef::equal_no_generic(const TypeRef& x) const case TypeRef::UNIT: return 0; case TypeRef::ANY: - throw CompileError::Todo("TypeRef::equal_no_generic - ANY"); + return 0; case TypeRef::PRIMITIVE: if( m_core_type != x.m_core_type ) return -1; return 0; -- cgit v1.2.3