From f725889aedd5b64141e8f8e9924e4e59f716c225 Mon Sep 17 00:00:00 2001 From: John Hodge Date: Tue, 31 Mar 2015 14:20:18 +0800 Subject: Partial comparisons of types/paths to speed up impl searches --- src/ast/ast.cpp | 24 +++++++++++++++++++++++- src/ast/path.cpp | 25 +++++++++++++++++++++++++ src/ast/path.hpp | 3 +++ src/convert/typecheck_params.cpp | 2 +- src/types.cpp | 24 +++++++++++++++++++++++- src/types.hpp | 3 +++ 6 files changed, 78 insertions(+), 3 deletions(-) diff --git a/src/ast/ast.cpp b/src/ast/ast.cpp index b8e6d381..4c400a47 100644 --- a/src/ast/ast.cpp +++ b/src/ast/ast.cpp @@ -80,7 +80,29 @@ Impl Impl::make_concrete(const ::std::vector& types) const ::rust::option Impl::matches(const Path& trait, const TypeRef& type) { - DEBUG("this = " << *this); + //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(); + DEBUG("Trait " << trait << " matches " << trait_match); + int type_match = m_type.equal_no_generic(type); + if( type_match < 0 ) + return ::rust::option(); + DEBUG("Type " << type << " matches " << type_match); + // 2. If a parameter was seen, do the more expensive generic checks + // > Involves checking that parameters are valid + if( trait_match > 0 ) + { + throw CompileError::Todo("Generic-ised match of impl trait"); + } + if( type_match > 0 ) + { + throw CompileError::Todo("Generic-ised match of impl type"); + } + // 3. Return success if( m_params.ty_params().size() > 0 ) { diff --git a/src/ast/path.cpp b/src/ast/path.cpp index 381685a9..7fa630f9 100644 --- a/src/ast/path.cpp +++ b/src/ast/path.cpp @@ -361,6 +361,31 @@ Path& Path::operator+=(const Path& other) return *this; } +int Path::equal_no_generic(const Path& x) const +{ + if( m_class != x.m_class ) + return -1; + if( m_crate != x.m_crate ) + return -1; + + unsigned int i = 0; + for( const auto &e : m_nodes ) + { + if( i >= x.m_nodes.size() ) + return -1; + const auto& xe = x.m_nodes[i]; + if( e.name() != xe.name() ) + return -1; + + if( e.args().size() || xe.args().size() ) + throw CompileError::Todo("Handle Path::equal_no_generic with generic"); + + i ++; + } + + return 0; +} + Ordering Path::ord(const Path& x) const { Ordering rv; diff --git a/src/ast/path.hpp b/src/ast/path.hpp index 2355c88b..21d2dd51 100644 --- a/src/ast/path.hpp +++ b/src/ast/path.hpp @@ -264,6 +264,9 @@ public: PathNode& operator[](int idx) { if(idx>=0) return m_nodes[idx]; else return m_nodes[size()+idx]; } const PathNode& operator[](int idx) const { if(idx>=0) return m_nodes[idx]; else return m_nodes[size()+idx]; } + /// Returns 0 if paths are identical, 1 if TypeRef::TagArg is present in one, and -1 if a node differs + int equal_no_generic(const Path& x) const; + Ordering ord(const Path& x) const; bool operator==(const Path& x) const { return ord(x) == OrdEqual; } bool operator!=(const Path& x) const { return ord(x) != OrdEqual; } diff --git a/src/convert/typecheck_params.cpp b/src/convert/typecheck_params.cpp index 2e4bc97c..0a7af631 100644 --- a/src/convert/typecheck_params.cpp +++ b/src/convert/typecheck_params.cpp @@ -121,7 +121,7 @@ bool CGenericParamChecker::has_impl(const TypeRef& type, const AST::Path& trait) else { // Search all known impls of this trait (TODO: keep a list at the crate level) for a match to this type - auto i = m_crate.find_impl(trait, trait); + auto i = m_crate.find_impl(trait, type); if( i.is_none() ) { DEBUG("- Nope"); return false; diff --git a/src/types.cpp b/src/types.cpp index a5b6d6ee..c8af093c 100644 --- a/src/types.cpp +++ b/src/types.cpp @@ -315,6 +315,28 @@ bool TypeRef::is_concrete() const throw ::std::runtime_error( FMT("BUGCHECK - Invalid type class on " << *this) ); } +int TypeRef::equal_no_generic(const TypeRef& x) const +{ + if( m_class != x.m_class ) return -1; + switch(m_class) + { + case TypeRef::NONE: + case TypeRef::UNIT: + return 0; + case TypeRef::ANY: + throw CompileError::Todo("TypeRef::equal_no_generic - ANY"); + case TypeRef::PRIMITIVE: + if( m_core_type != x.m_core_type ) return -1; + return 0; + case TypeRef::FUNCTION: + if( m_path[0].name() != x.m_path[0].name() ) return -1; + throw CompileError::Todo("TypeRef::equal_no_generic - FUNCTION"); + case TypeRef::PATH: + return m_path.equal_no_generic( x.m_path ); + default: + throw CompileError::Todo("TypeRef::equal_no_generic"); + } +} Ordering TypeRef::ord(const TypeRef& x) const { Ordering rv; @@ -336,7 +358,7 @@ Ordering TypeRef::ord(const TypeRef& x) const case TypeRef::FUNCTION: rv = ::ord(m_path[0].name(),x.m_path[0].name()); if(rv != OrdEqual) return rv; - return OrdEqual; + return ::ord(m_inner_types, x.m_inner_types); case TypeRef::TUPLE: return ::ord(m_inner_types, x.m_inner_types); //return m_inner_types == x.m_inner_types; diff --git a/src/types.hpp b/src/types.hpp index 38f2b26b..443f9912 100644 --- a/src/types.hpp +++ b/src/types.hpp @@ -188,6 +188,9 @@ public: void add_trait(TypeRef trait) { assert(is_wildcard()); m_inner_types.push_back( ::std::move(trait) ); } const ::std::vector& traits() const { assert(is_wildcard()); return m_inner_types; } + /// Returns 0 if types are identical, 1 if TypeRef::TagArg is present in one, and -1 if form differs + int equal_no_generic(const TypeRef& x) const; + Ordering ord(const TypeRef& x) const; bool operator==(const TypeRef& x) const { return ord(x) == OrdEqual; } bool operator!=(const TypeRef& x) const { return ord(x) != OrdEqual; } -- cgit v1.2.3