Changeset 432ce7a

Timestamp:

Jun 11, 2019, 5:52:50 PM (5 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

6625727

Parents:

4b7cce6

Message:

Port CandidateFinder::postvisit for UntypedExpr?, stub dependencies

Location:

src

Files:

• AST/Print.hpp (modified) (2 diffs)
• AST/porting.md (modified) (1 diff)
• Makefile.in (modified) (4 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (5 diffs)
• ResolvExpr/AlternativeFinder.h (modified) (1 diff)
• ResolvExpr/Candidate.hpp (modified) (1 diff)
• ResolvExpr/CandidateFinder.cpp (modified) (5 diffs)
• ResolvExpr/ExplodedActual.cc (modified) (2 diffs)
• ResolvExpr/ExplodedActual.h (modified) (2 diffs)
• ResolvExpr/ExplodedArg.cpp (added)
• ResolvExpr/ExplodedArg.hpp (added)
• ResolvExpr/module.mk (modified) (1 diff)
• Tuples/Explode.h (modified) (2 diffs)
• Tuples/TupleAssignment.cc (modified) (1 diff)
• Tuples/Tuples.h (modified) (2 diffs)

src/AST/Print.hpp

@@ -16 +16 @@
 #pragma once
 
-#include <iosfwd>
-#include <utility> // for forward
+#include <iostream>
+#include <utility>   // for forward
 
 #include "AST/Node.hpp"
@@ -32 +32 @@
 void printShort( std::ostream & os, const ast::Decl * node, Indenter indent = {} );
 
-inline void printShort( std::ostream & os, const ast::Decl * node, unsigned int indent ) {
-    printShort( os, node, Indenter{ indent } );
+/// Print a collection of items
+template< typename Coll >
+void printAll( std::ostream & os, const Coll & c, Indenter indent = {} ) {
+    for ( const auto & i : c ) {
+        if ( ! i ) continue;
+        
+        os << indent;
+        print( os, i, indent );
+        os << std::endl;
+    }
 }
 

src/AST/porting.md

@@ -299 +299 @@
 * `openVars` => `open`
 
+`ExplodedActual` => `ExplodedArg`
+* `ExplodedActual.h` => `ExplodedArg.hpp`
+
 [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes
 

src/Makefile.in

@@ -195 +195 @@
         ResolvExpr/CurrentObject.$(OBJEXT) \
         ResolvExpr/ExplodedActual.$(OBJEXT) \
+        ResolvExpr/ExplodedArg.$(OBJEXT) \
         ResolvExpr/FindOpenVars.$(OBJEXT) ResolvExpr/Occurs.$(OBJEXT) \
         ResolvExpr/PolyCost.$(OBJEXT) \
@@ -633 +634 @@
       ResolvExpr/CurrentObject.cc \
       ResolvExpr/ExplodedActual.cc \
+      ResolvExpr/ExplodedArg.cpp \
       ResolvExpr/FindOpenVars.cc \
       ResolvExpr/Occurs.cc \
@@ -895 +897 @@
 ResolvExpr/ExplodedActual.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
         ResolvExpr/$(DEPDIR)/$(am__dirstamp)
+ResolvExpr/ExplodedArg.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
+        ResolvExpr/$(DEPDIR)/$(am__dirstamp)
 ResolvExpr/FindOpenVars.$(OBJEXT): ResolvExpr/$(am__dirstamp) \
         ResolvExpr/$(DEPDIR)/$(am__dirstamp)
@@ -1277 +1281 @@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/CurrentObject.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/ExplodedActual.Po@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/ExplodedArg.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/FindOpenVars.Po@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@ResolvExpr/$(DEPDIR)/Occurs.Po@am__quote@

src/ResolvExpr/AlternativeFinder.cc

@@ -116 +116 @@
                 /// Finds matching alternatives for a function, given a set of arguments
                 template<typename OutputIterator>
-                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
+                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs_old& args, OutputIterator out );
                 /// Sets up parameter inference for an output alternative
                 template< typename OutputIterator >
@@ -593 +593 @@
 
                 /// Gets the list of exploded alternatives for this pack
-                const ExplodedActual& getExpl( const ExplodedArgs& args ) const {
+                const ExplodedActual& getExpl( const ExplodedArgs_old& args ) const {
                         return args[nextArg-1][explAlt];
                 }
@@ -617 +617 @@
         /// Instantiates an argument to match a formal, returns false if no results left
         bool instantiateArgument( Type* formalType, Initializer* initializer,
-                        const ExplodedArgs& args, std::vector<ArgPack>& results, std::size_t& genStart,
+                        const ExplodedArgs_old& args, std::vector<ArgPack>& results, std::size_t& genStart,
                         const SymTab::Indexer& indexer, unsigned nTuples = 0 ) {
                 if ( TupleType * tupleType = dynamic_cast<TupleType*>( formalType ) ) {
@@ -889 +889 @@
         template<typename OutputIterator>
         void AlternativeFinder::Finder::makeFunctionAlternatives( const Alternative &func,
-                        FunctionType *funcType, const ExplodedArgs &args, OutputIterator out ) {
+                        FunctionType *funcType, const ExplodedArgs_old &args, OutputIterator out ) {
                 OpenVarSet funcOpenVars;
                 AssertionSet funcNeed, funcHave;
@@ -1021 +1021 @@
 
                 // pre-explode arguments
-                ExplodedArgs argExpansions;
+                ExplodedArgs_old argExpansions;
                 argExpansions.reserve( argAlternatives.size() );
 

src/ResolvExpr/AlternativeFinder.h

@@ -37 +37 @@
         /// First index is which argument, second index is which alternative for that argument,
         /// third index is which exploded element of that alternative
-        using ExplodedArgs = std::vector< std::vector< ExplodedActual > >;
+        using ExplodedArgs_old = std::vector< std::vector< ExplodedActual > >;
 
         class AlternativeFinder {

src/ResolvExpr/Candidate.hpp

@@ -70 +70 @@
 using CandidateList = std::vector< CandidateRef >;
 
+/// Splice src after dst, clearing src
+static inline void splice( CandidateList & dst, CandidateList & src ) {
+        dst.reserve( dst.size() + src.size() );
+        for ( CandidateRef & r : src ) { dst.emplace_back( std::move( r ) ); }
+        src.clear();
+}
+
+/// Splice src before dst
+static inline void spliceBegin( CandidateList & dst, CandidateList & src ) {
+        splice( src, dst );
+        dst.swap( src );
+}
+
 /// Sum the cost of a list of candidates
 static inline Cost sumCost( const CandidateList & candidates ) {

src/ResolvExpr/CandidateFinder.cpp

@@ -16 +16 @@
 #include "CandidateFinder.hpp"
 
+#include <deque>
 #include <iterator>               // for back_inserter
 #include <sstream>
 #include <string>
 #include <unordered_map>
+#include <vector>
 
 #include "Candidate.hpp"
 #include "CompilationState.h"
 #include "Cost.h"
+#include "ExplodedArg.hpp"
 #include "Resolver.h"
 #include "SatisfyAssertions.hpp"
@@ -33 +36 @@
 #include "AST/Print.hpp"
 #include "AST/SymbolTable.hpp"
+#include "AST/Type.hpp"
 #include "SymTab/Mangler.h"
+#include "Tuples/Tuples.h"        // for handleTupleAssignment
 
 #define PRINT( text ) if ( resolvep ) { text }
@@ -40 +45 @@
 
 namespace {
+
+        /// First index is which argument, second is which alternative, third is which exploded element
+        using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
+
+        /// Returns a list of alternatives with the minimum cost in the given list
+        CandidateList findMinCost( const CandidateList & candidates ) {
+                CandidateList out;
+                Cost minCost = Cost::infinity;
+                for ( const CandidateRef & r : candidates ) {
+                        if ( r->cost < minCost ) {
+                                minCost = r->cost;
+                                out.clear();
+                                out.emplace_back( r );
+                        } else if ( r->cost == minCost ) {
+                                out.emplace_back( r );
+                        }
+                }
+                return out;
+        }
+
+        /// Computes conversion cost for a given candidate
+        Cost computeApplicationConversionCost( 
+                const CandidateRef & cand, const ast::SymbolTable & symtab 
+        ) {
+                #warning unimplemented
+                (void)cand; (void)symtab;
+                assert(false);
+                return Cost::infinity;
+        }
 
         /// Actually visits expressions to find their candidate interpretations
@@ -65 +99 @@
                 }
 
+                /// Builds a list of candidates for a function, storing them in out
+                void makeFunctionCandidates(
+                        const CandidateRef & func, const ast::FunctionType * funcType, 
+                        const ExplodedArgs_new & args, CandidateList & out
+                ) {
+                        #warning unimplemented
+                        (void)func; (void)funcType; (void)args; (void)out;
+                        assert(false);
+                }
+
+                /// Adds implicit struct-conversions to the alternative list
+                void addAnonConversions( const CandidateRef & cand ) {
+                        #warning unimplemented
+                        (void)cand;
+                        assert(false);
+                }
+
                 void postvisit( const ast::UntypedExpr * untypedExpr ) {
-                        #warning unimplemented
-                        (void)untypedExpr;
-                        assert(false);
+                        CandidateFinder funcFinder{ symtab, tenv };
+                        funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
+                        // short-circuit if no candidates
+                        if ( funcFinder.candidates.empty() ) return;
+
+                        std::vector< CandidateFinder > argCandidates = 
+                                selfFinder.findSubExprs( untypedExpr->args );
+                        
+                        // take care of possible tuple assignments
+                        // if not tuple assignment, handled as normal function call
+                        Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
+
+                        // find function operators
+                        ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
+                        CandidateFinder opFinder{ symtab, tenv };
+                        // okay if there aren't any function operations
+                        opFinder.find( opExpr, ResolvMode::withoutFailFast() );
+                        PRINT(
+                                std::cerr << "known function ops:" << std::endl;
+                                print( std::cerr, opFinder.candidates, 1 );
+                        )
+
+                        // pre-explode arguments
+                        ExplodedArgs_new argExpansions;
+                        for ( const CandidateFinder & args : argCandidates ) {
+                                argExpansions.emplace_back();
+                                auto & argE = argExpansions.back();
+                                for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
+                        }
+
+                        // Find function matches
+                        CandidateList found;
+                        SemanticErrorException errors;
+                        for ( CandidateRef & func : funcFinder ) {
+                                try {
+                                        PRINT(
+                                                std::cerr << "working on alternative:" << std::endl;
+                                                print( std::cerr, *func, 2 );
+                                        )
+
+                                        // check if the type is a pointer to function
+                                        const ast::Type * funcResult = func->expr->result->stripReferences();
+                                        if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
+                                                if ( auto function = pointer->base.as< ast::FunctionType >() ) {
+                                                        CandidateRef newFunc{ new Candidate{ *func } };
+                                                        newFunc->expr = 
+                                                                referenceToRvalueConversion( newFunc->expr, newFunc->cost );
+                                                        makeFunctionCandidates( newFunc, function, argExpansions, found );
+                                                }
+                                        } else if ( 
+                                                auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult ) 
+                                        ) {
+                                                if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
+                                                        if ( auto function = clz->bound.as< ast::FunctionType >() ) {
+                                                                CandidateRef newFunc{ new Candidate{ *func } };
+                                                                newFunc->expr = 
+                                                                        referenceToRvalueConversion( newFunc->expr, newFunc->cost );
+                                                                makeFunctionCandidates( newFunc, function, argExpansions, found );
+                                                        }
+                                                }
+                                        }
+                                } catch ( SemanticErrorException & e ) { errors.append( e ); }
+                        }
+
+                        // Find matches on function operators `?()`
+                        if ( ! opFinder.candidates.empty() ) {
+                                // add exploded function alternatives to front of argument list
+                                std::vector< ExplodedArg > funcE;
+                                funcE.reserve( funcFinder.candidates.size() );
+                                for ( const CandidateRef & func : funcFinder ) { 
+                                        funcE.emplace_back( *func, symtab );
+                                }
+                                argExpansions.emplace_front( std::move( funcE ) );
+
+                                for ( const CandidateRef & op : opFinder ) {
+                                        try {
+                                                // check if type is pointer-to-function
+                                                const ast::Type * opResult = op->expr->result->stripReferences();
+                                                if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
+                                                        if ( auto function = pointer->base.as< ast::FunctionType >() ) {
+                                                                CandidateRef newOp{ new Candidate{ *op} };
+                                                                newOp->expr = 
+                                                                        referenceToRvalueConversion( newOp->expr, newOp->cost );
+                                                                makeFunctionCandidates( newOp, function, argExpansions, found );
+                                                        }
+                                                }
+                                        } catch ( SemanticErrorException & e ) { errors.append( e ); }
+                                }
+                        }
+
+                        // Implement SFINAE; resolution errors are only errors if there aren't any non-error 
+                        // candidates
+                        if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
+
+                        // Compute conversion costs
+                        for ( CandidateRef & withFunc : found ) {
+                                Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
+
+                                PRINT(
+                                        auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
+                                        auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
+                                        auto function = pointer->base.strict_as< ast::FunctionType >();
+                                        
+                                        std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
+                                        std::cerr << "parameters are:" << std::endl;
+                                        ast::printAll( std::cerr, function->params, 2 );
+                                        std::cerr << "arguments are:" << std::endl;
+                                        ast::printAll( std::cerr, appExpr->args, 2 );
+                                        std::cerr << "bindings are:" << std::endl;
+                                        ast::print( std::cerr, withFunc->env, 2 );
+                                        std::cerr << "cost is: " << withFunc->cost << std::endl;
+                                        std::cerr << "cost of conversion is:" << cvtCost << std::endl;
+                                )
+
+                                if ( cvtCost != Cost::infinity ) {
+                                        withFunc->cvtCost = cvtCost;
+                                        candidates.emplace_back( std::move( withFunc ) );
+                                }
+                        }
+                        found = std::move( candidates );
+
+                        // use a new list so that candidates are not examined by addAnonConversions twice
+                        CandidateList winners = findMinCost( found );
+                        promoteCvtCost( winners );
+
+                        // function may return a struct/union value, in which case we need to add candidates 
+                        // for implicit conversions to each of the anonymous members, which must happen after 
+                        // `findMinCost`, since anon conversions are never the cheapest
+                        for ( const CandidateRef & c : winners ) {
+                                addAnonConversions( c );
+                        }
+                        spliceBegin( candidates, winners );
+
+                        if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
+                                // If resolution is unsuccessful with a target type, try again without, since it 
+                                // will sometimes succeed when it wouldn't with a target type binding.
+                                // For example:
+                                //   forall( otype T ) T & ?[]( T *, ptrdiff_t );
+                                //   const char * x = "hello world";
+                                //   unsigned char ch = x[0];
+                                // Fails with simple return type binding (xxx -- check this!) as follows:
+                                // * T is bound to unsigned char
+                                // * (x: const char *) is unified with unsigned char *, which fails
+                                // xxx -- fix this better
+                                targetType = nullptr;
+                                postvisit( untypedExpr );
+                        }
                 }
 
@@ -440 +635 @@
         }
 
-        /// Returns a list of alternatives with the minimum cost in the given list
-        CandidateList findMinCost( const CandidateList & candidates ) {
-                CandidateList out;
-                Cost minCost = Cost::infinity;
-                for ( const CandidateRef & r : candidates ) {
-                        if ( r->cost < minCost ) {
-                                minCost = r->cost;
-                                out.clear();
-                                out.emplace_back( r );
-                        } else if ( r->cost == minCost ) {
-                                out.emplace_back( r );
-                        }
-                }
-                return out;
-        }
-
 } // anonymous namespace
 

src/ResolvExpr/ExplodedActual.cc

@@ -5 +5 @@
 // file "LICENCE" distributed with Cforall.
 //
-// Alternative.h --
+// ExplodedActual.cc --
 //
 // Author           : Aaron B. Moss
@@ -24 +24 @@
         }
 }
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //

src/ResolvExpr/ExplodedActual.h

@@ -5 +5 @@
 // file "LICENCE" distributed with Cforall.
 //
-// Alternative.h --
+// ExplodedActual.h --
 //
 // Author           : Aaron B. Moss
@@ -37 +37 @@
         };
 }
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //

src/ResolvExpr/module.mk

@@ -26 +26 @@
       ResolvExpr/CurrentObject.cc \
       ResolvExpr/ExplodedActual.cc \
+      ResolvExpr/ExplodedArg.cpp \
       ResolvExpr/FindOpenVars.cc \
       ResolvExpr/Occurs.cc \

src/Tuples/Explode.h

@@ -19 +19 @@
 #include <utility>                      // for forward
 
+#include "AST/Expr.hpp"
 #include "ResolvExpr/Alternative.h"     // for Alternative, AltList
+#include "ResolvExpr/Candidate.hpp"     // for Candidate, CandidateList
 #include "ResolvExpr/ExplodedActual.h"  // for ExplodedActual
+#include "ResolvExpr/ExplodedArg.hpp"   // for ExplodedArg
 #include "SynTree/Expression.h"         // for Expression, UniqueExpr, AddressExpr
 #include "SynTree/Type.h"               // for TupleType, Type
 #include "Tuples.h"                     // for maybeImpure
+
+namespace ast {
+        class SymbolTable;
+}
 
 namespace SymTab {
@@ -130 +137 @@
                 explode( alts.begin(), alts.end(), indexer, std::forward<Output>(out), isTupleAssign );
         }
+
+/// helper function used by explode
+template< typename Output >
+void explodeUnique( 
+        const ast::Expr * expr, const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, 
+        Output && out, bool isTupleAssign
+) {
+        #warning unimplemented
+        (void)expr; (void)arg; (void)symtab; (void)out; (void)isTupleAssign;
+        assert(false);
+}
+
+/// expands a tuple-valued candidate into multiple candidates, each with a non-tuple type
+template< typename Output >
+void explode( 
+        const ResolvExpr::Candidate & arg, const ast::SymbolTable & symtab, Output && out, 
+        bool isTupleAssign = false
+) {
+        explodeUnique( arg.expr, arg, symtab, std::forward< Output >( out ), isTupleAssign );
+}
+
 } // namespace Tuples
 

src/Tuples/TupleAssignment.cc

@@ -377 +377 @@
                 }
         }
+
+        void handleTupleAssignment( 
+                ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, 
+                std::vector< ResolvExpr::CandidateFinder > & args
+        ) {
+                #warning unimplmented
+                (void)finder; (void)assign; (void)args;
+                assert(false);
+        }
 } // namespace Tuples
 

src/Tuples/Tuples.h

@@ -26 +26 @@
 
 #include "ResolvExpr/AlternativeFinder.h"
+#include "ResolvExpr/CandidateFinder.hpp"
 
 namespace Tuples {
@@ -31 +32 @@
         void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign,
                 std::vector< ResolvExpr::AlternativeFinder >& args );
+        void handleTupleAssignment( 
+                ResolvExpr::CandidateFinder & finder, const ast::UntypedExpr * assign, 
+                std::vector< ResolvExpr::CandidateFinder > & args );
 
         // TupleExpansion.cc