Changeset 65660bd for src/Tuples

Timestamp:

Sep 22, 2016, 8:14:56 AM (9 years ago)

Author:

Rob Schluntz <rschlunt@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

ac9ca96

Parents:

1132b62

git-author:

Rob Schluntz <rschlunt@…> (09/21/16 23:43:37)

git-committer:

Rob Schluntz <rschlunt@…> (09/22/16 08:14:56)

Message:

replace multiple-returning functions with tuple-returning functions, implement tuple ctor/dtor, allow N-arg tuple assignment

Location:

src/Tuples

Files:

• TupleAssignment.cc (modified) (11 diffs)
• TupleExpansion.cc (modified) (3 diffs)
• Tuples.h (modified) (3 diffs)

src/Tuples/TupleAssignment.cc

@@ -21 +21 @@
 #include "Tuples.h"
 #include "Common/SemanticError.h"
+#include "InitTweak/InitTweak.h"
 
 #include <functional>
@@ -35 +36 @@
                 // dispatcher for Tuple (multiple and mass) assignment operations
                 TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
-                void spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities );
+                void spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities );
 
           private:
@@ -42 +43 @@
                 struct Matcher {
                   public:
-                        Matcher( TupleAssignSpotter &spotter, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs );
+                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
                         virtual ~Matcher() {}
                         virtual void match( std::list< Expression * > &out ) = 0;
@@ -52 +53 @@
                 struct MassAssignMatcher : public Matcher {
                   public:
-                        MassAssignMatcher( TupleAssignSpotter &spotter, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs );
+                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
                         virtual void match( std::list< Expression * > &out );
                 };
@@ -58 +59 @@
                 struct MultipleAssignMatcher : public Matcher {
                   public:
-                        MultipleAssignMatcher( TupleAssignSpotter &spot, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs );
+                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
                         virtual void match( std::list< Expression * > &out );
                 };
 
                 ResolvExpr::AlternativeFinder &currentFinder;
-                // Expression *rhs, *lhs;
-                Matcher *matcher = nullptr;
+                std::string fname;
+                std::unique_ptr< Matcher > matcher;
         };
 
@@ -74 +75 @@
         }
 
+        template< typename AltIter >
+        bool isMultAssign( AltIter begin, AltIter end ) {
+                // multiple assignment if more than one alternative in the range or if
+                // the alternative is a tuple
+                if ( begin == end ) return false;
+                if ( isTuple( begin->expr ) ) return true;
+                return ++begin != end;
+        }
+
         bool pointsToTuple( Expression *expr ) {
                 // also check for function returning tuple of reference types
-                if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
+                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( expr ) ) {
+                        return pointsToTuple( castExpr->get_arg() );
+                } else if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
                         return isTuple( addr->get_arg() );
                 }
@@ -82 +94 @@
         }
 
-        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
+        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
                 TupleAssignSpotter spotter( currentFinder );
                 spotter.spot( expr, possibilities );
@@ -90 +102 @@
                 : currentFinder(f) {}
 
-        void TupleAssignSpotter::spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
-                if (  NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
-                        if ( assgnop->get_name() == "?=?" ) {
-                                for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
-                                        if ( ali->size() != 2 ) continue; // what does it mean if an assignment takes >2 arguments? grab args 2-N and group into a TupleExpr, then proceed?
-                                        ResolvExpr::Alternative & alt1 = ali->front(), & alt2 = ali->back();
-
+        void TupleAssignSpotter::spot( UntypedExpr * expr, const std::list<ResolvExpr::AltList> &possibilities ) {
+                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
+                        if ( InitTweak::isCtorDtorAssign( op->get_name() ) ) {
+                                fname = op->get_name();
+                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
+                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
+                                        if ( ali->size() <= 1 && InitTweak::isAssignment( op->get_name() ) ) {
+                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
+                                                continue;
+                                        }
+
+                                        assert( ! ali->empty() );
+                                        // grab args 2-N and group into a TupleExpr
+                                        const ResolvExpr::Alternative & alt1 = ali->front();
+                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
                                         if ( pointsToTuple(alt1.expr) ) {
-                                                MultipleAssignMatcher multiMatcher( *this, alt1, alt2 );
-                                                MassAssignMatcher massMatcher( *this,  alt1, alt2 );
-                                                if ( isTuple( alt2.expr ) ) {
-                                                        matcher = &multiMatcher;
+                                                if ( isMultAssign( begin, end ) ) {
+                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
                                                 } else {
                                                         // mass assignment
-                                                        matcher = &massMatcher;
+                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
                                                 }
                                                 match();
-                                        } else if ( isTuple( alt2.expr ) ) {
-                                                throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr);
                                         }
                                 }
@@ -146 +162 @@
         }
 
-        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs ) : spotter(spotter) {
-                if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs.expr) ) {
-                        // xxx - not every assignment NEEDS to have the first argument as address-taken, e.g. a manual call to assignment. What to do in this case? skip it as a possibility for TupleAssignment, since the type will always be T*, where T can never be a tuple? Is this true?
-
-                        // explode the lhs so that each field of the tuple-valued-expr is assigned.
-                        ResolvExpr::Alternative lhsAlt( addr->get_arg()->clone(), lhs.env, lhs.cost, lhs.cvtCost );
-                        explode( lhsAlt, back_inserter(this->lhs) );
-                }
-        }
-
-        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs ) : Matcher( spotter, lhs, rhs ) {
-                this->rhs.push_back( rhs );
-        }
-
-        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, ResolvExpr::Alternative & lhs, ResolvExpr::Alternative & rhs ) : Matcher( spotter, lhs, rhs ) {
-
+        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter) {
+                assert( ! alts.empty() );
+                ResolvExpr::Alternative lhsAlt = alts.front();
+                // peel off the cast that exists on ctor/dtor expressions
+                bool isCast = false;
+                if ( CastExpr * castExpr = dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
+                        lhsAlt.expr = castExpr->get_arg();
+                        castExpr->set_arg( nullptr );
+                        delete castExpr;
+                        isCast = true;
+                }
+
+                // explode the lhs so that each field of the tuple-valued-expr is assigned.
+                explode( lhsAlt, back_inserter(lhs) );
+                // and finally, re-add the cast to each lhs expr, so that qualified tuple fields can be constructed
+                if ( isCast ) {
+                        for ( ResolvExpr::Alternative & alt : lhs ) {
+                                Expression *& expr = alt.expr;
+                                Type * castType = expr->get_result()->clone();
+                                Type * type = InitTweak::getPointerBase( castType );
+                                assert( type );
+                                type->get_qualifiers() -= Type::Qualifiers(true, true, true, false, true, true);
+                                type->set_isLvalue( true ); // xxx - might not need this
+                                expr = new CastExpr( expr, castType );
+                        }
+                }
+                // }
+        }
+
+        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter,const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
+                assert( alts.size() == 1 || alts.size() == 2 );
+                if ( alts.size() == 2 ) {
+                        rhs.push_back( alts.back() );
+                }
+        }
+
+        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
                 // explode the rhs so that each field of the tuple-valued-expr is assigned.
-                explode( rhs, back_inserter(this->rhs) );
-        }
-
-        UntypedExpr * createAssgn( ObjectDecl *left, ObjectDecl *right ) {
-                assert( left && right );
+                explode( std::next(alts.begin(), 1), alts.end(), back_inserter(rhs) );
+        }
+
+        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
+                assert( left );
                 std::list< Expression * > args;
                 args.push_back( new AddressExpr( new UntypedExpr( new NameExpr("*?"), std::list< Expression * >{ new VariableExpr( left ) } ) ) );
-                args.push_back( new VariableExpr( right ) );
-                return new UntypedExpr( new NameExpr( "?=?" ), args );
+                // args.push_back( new AddressExpr( new VariableExpr( left ) ) );
+                if ( right ) args.push_back( new VariableExpr( right ) );
+                return new UntypedExpr( new NameExpr( fname ), args );
         }
 
@@ -182 +220 @@
                 static UniqueName lhsNamer( "__massassign_L" );
                 static UniqueName rhsNamer( "__massassign_R" );
-                assert ( ! lhs.empty() && rhs.size() == 1);
-
-                ObjectDecl * rtmp = newObject( rhsNamer, rhs.front().expr );
+                assert ( ! lhs.empty() && rhs.size() <= 1);
+
+                ObjectDecl * rtmp = rhs.size() == 1 ? newObject( rhsNamer, rhs.front().expr ) : nullptr;
                 for ( ResolvExpr::Alternative & lhsAlt : lhs ) {
-                        ObjectDecl * ltmp = newObject( lhsNamer, new AddressExpr( lhsAlt.expr ) );
-                        out.push_back( createAssgn( ltmp, rtmp ) );
+                        ObjectDecl * ltmp = newObject( lhsNamer, lhsAlt.expr );
+                        out.push_back( createFunc( spotter.fname, ltmp, rtmp ) );
                         tmpDecls.push_back( ltmp );
                 }
-                tmpDecls.push_back( rtmp );
+                if ( rtmp ) tmpDecls.push_back( rtmp );
         }
 
@@ -201 +239 @@
                         std::list< ObjectDecl * > rtmp;
                         std::transform( lhs.begin(), lhs.end(), back_inserter( ltmp ), []( ResolvExpr::Alternative & alt ){
-                                return newObject( lhsNamer, new AddressExpr( alt.expr ) );
+                                return newObject( lhsNamer, alt.expr );
                         });
                         std::transform( rhs.begin(), rhs.end(), back_inserter( rtmp ), []( ResolvExpr::Alternative & alt ){
                                 return newObject( rhsNamer, alt.expr );
                         });
-                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), createAssgn );
+                        zipWith( ltmp.begin(), ltmp.end(), rtmp.begin(), rtmp.end(), back_inserter(out), [&](ObjectDecl * obj1, ObjectDecl * obj2 ) { return createFunc(spotter.fname, obj1, obj2); } );
                         tmpDecls.splice( tmpDecls.end(), ltmp );
                         tmpDecls.splice( tmpDecls.end(), rtmp );

src/Tuples/TupleExpansion.cc

@@ -49 +49 @@
 
                         virtual Type * mutate( TupleType * tupleType );
-                        virtual Type * mutate( FunctionType * ftype );
 
                         virtual CompoundStmt * mutate( CompoundStmt * stmt ) {
@@ -119 +118 @@
                 delete assnExpr;
                 return new StmtExpr( compoundStmt );
-        }
-
-        Type * TupleTypeReplacer::mutate( FunctionType * ftype ) {
-                // replace multiple-returning functions with functions which return a tuple
-                if ( ftype->get_returnVals().size() > 1 ) {
-                        TupleType * tupleType = safe_dynamic_cast<TupleType *>( ResolvExpr::extractResultType( ftype ) );
-                        ObjectDecl * retVal = new ObjectDecl( "__tuple_ret", DeclarationNode::NoStorageClass, LinkageSpec::C, nullptr, tupleType, nullptr );
-                        // xxx - replace all uses of return vals with appropriate tuple index expr
-                        deleteAll( ftype->get_returnVals() );
-                        ftype->get_returnVals().clear();
-                        ftype->get_returnVals().push_back( retVal );
-                }
-                return Parent::mutate( ftype );
         }
 
@@ -167 +153 @@
         }
 
+        Expression * replaceTupleExpr( Type * result, const std::list< Expression * > & exprs ) {
+                if ( result->isVoid() ) {
+                        // void result - don't need to produce a value for cascading - just output a chain of comma exprs
+                        assert( ! exprs.empty() );
+                        std::list< Expression * >::const_iterator iter = exprs.begin();
+                        Expression * expr = *iter++;
+                        for ( ; iter != exprs.end(); ++iter ) {
+                                expr = new CommaExpr( expr, *iter );
+                        }
+                        return expr;
+                } else {
+                        // typed tuple expression - produce a compound literal which performs each of the expressions
+                        // as a distinct part of its initializer - the produced compound literal may be used as part of
+                        // another expression
+                        std::list< Initializer * > inits;
+                        for ( Expression * expr : exprs ) {
+                                inits.push_back( new SingleInit( expr ) );
+                        }
+                        return new CompoundLiteralExpr( result, new ListInit( inits ) );
+                }
+        }
+
         Expression * TupleExprExpander::mutate( TupleExpr * tupleExpr ) {
-                assert( tupleExpr->get_result() );
-                std::list< Initializer * > inits;
-                for ( Expression * expr : tupleExpr->get_exprs() ) {
-                        inits.push_back( new SingleInit( expr ) );
-                }
-                return new CompoundLiteralExpr( tupleExpr->get_result(), new ListInit( inits ) );
-        }
-
-        TupleType * makeTupleType( const std::list< Expression * > & exprs ) {
+                Type * result = tupleExpr->get_result();
+                std::list< Expression * > exprs = tupleExpr->get_exprs();
+                assert( result );
+
+                tupleExpr->set_result( nullptr );
+                tupleExpr->get_exprs().clear();
+                delete tupleExpr;
+
+                return replaceTupleExpr( result, exprs );
+        }
+
+        Type * makeTupleType( const std::list< Expression * > & exprs ) {
+                // produce the TupleType which aggregates the types of the exprs
                 TupleType *tupleType = new TupleType( Type::Qualifiers(true, true, true, true, true, false) );
                 Type::Qualifiers &qualifiers = tupleType->get_qualifiers();
                 for ( Expression * expr : exprs ) {
                         assert( expr->get_result() );
+                        if ( expr->get_result()->isVoid() ) {
+                                // if the type of any expr is void, the type of the entire tuple is void
+                                delete tupleType;
+                                return new VoidType( Type::Qualifiers() );
+                        }
                         Type * type = expr->get_result()->clone();
                         tupleType->get_types().push_back( type );
+                        // the qualifiers on the tuple type are the qualifiers that exist on all component types
                         qualifiers &= type->get_qualifiers();
                 } // for
                 return tupleType;
+        }
+
+        namespace {
+                /// determines if impurity (read: side-effects) may exist in a piece of code. Currently gives a very crude approximation, wherein any function call expression means the code may be impure
+                class ImpurityDetector : public Visitor {
+                public:
+                        typedef Visitor Parent;
+                        virtual void visit( ApplicationExpr * appExpr ) { maybeImpure = true;   }
+                        virtual void visit( UntypedExpr * untypedExpr ) { maybeImpure = true; }
+                        bool maybeImpure = false;
+                };
+        } // namespace
+
+        bool maybeImpure( Expression * expr ) {
+                ImpurityDetector detector;
+                expr->accept( detector );
+                return detector.maybeImpure;
         }
 } // namespace Tuples

src/Tuples/Tuples.h

@@ -15 +15 @@
 
 #ifndef _TUPLES_H_
-#define _TUPLE_H_
+#define _TUPLES_H_
 
 #include <string>
@@ -27 +27 @@
 namespace Tuples {
         // TupleAssignment.cc
-        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, std::list<ResolvExpr::AltList> & possibilities );
+        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, const std::list<ResolvExpr::AltList> & possibilities );
 
         // TupleExpansion.cc
@@ -34 +34 @@
   void expandUniqueExpr( std::list< Declaration * > & translationUnit );
 
-  TupleType * makeTupleType( const std::list< Expression * > & exprs );
+  /// returns VoidType if any of the expressions have Voidtype, otherwise TupleType of the Expression result types
+  Type * makeTupleType( const std::list< Expression * > & exprs );
+
+  bool maybeImpure( Expression * expr );
+
+
+        /// helper function used by explode
+        template< typename OutputIterator >
+        void explodeUnique( Expression * expr, const ResolvExpr::Alternative & alt, OutputIterator out ) {
+                Type * res = expr->get_result();
+                if ( AddressExpr * addrExpr = dynamic_cast< AddressExpr * >( expr ) ) {
+                        ResolvExpr::AltList alts;
+                        explodeUnique( addrExpr->get_arg(), alt, back_inserter( alts ) );
+                        for ( ResolvExpr::Alternative & alt : alts ) {
+                                // distribute '&' over all components
+                                alt.expr = new AddressExpr( alt.expr );
+                                *out++ = alt;
+                        }
+                } else if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) {
+                        if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) {
+                                // can open tuple expr and dump its exploded components
+                                for ( Expression * expr : tupleExpr->get_exprs() ) {
+                                        explodeUnique( expr, alt, out );
+                                }
+                        } else {
+                                // tuple type, but not tuple expr - recursively index into its components
+                                Expression * arg = expr->clone();
+                                if ( Tuples::maybeImpure( arg ) ) {
+                                        // expressions which may contain side effects require a single unique instance of the expression
+                                        arg = new UniqueExpr( arg );
+                                }
+                                for ( unsigned int i = 0; i < tupleType->size(); i++ ) {
+                                        TupleIndexExpr * idx = new TupleIndexExpr( arg->clone(), i );
+                                        explodeUnique( idx, alt, out );
+                                        delete idx;
+                                }
+                                delete arg;
+                        }
+                } else {
+                        // atomic (non-tuple) type - output a clone of the expression in a new alternative
+                        *out++ = ResolvExpr::Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost );
+                }
+        }
+
+        /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type
+        template< typename OutputIterator >
+        void explode( const ResolvExpr::Alternative &alt, OutputIterator out ) {
+                explodeUnique( alt.expr, alt, out );
+        }
+
+        // explode list of alternatives
+        template< typename AltIterator, typename OutputIterator >
+        void explode( AltIterator altBegin, AltIterator altEnd, OutputIterator out ) {
+                for ( ; altBegin != altEnd; ++altBegin ) {
+                        explode( *altBegin, out );
+                }
+        }
+
+        template< typename OutputIterator >
+        void explode( const ResolvExpr::AltList & alts, OutputIterator out ) {
+                explode( alts.begin(), alts.end(), out );
+        }
 } // namespace Tuples