Index: translator/Tuples/TupleAssignment.cc
===================================================================
--- translator/Tuples/TupleAssignment.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
+++ translator/Tuples/TupleAssignment.cc	(revision 51b734528489f81a5af985bfee9aa3b6625b9774)
@@ -0,0 +1,400 @@
+#include "ResolvExpr/AlternativeFinder.h"
+#include "ResolvExpr/Alternative.h"
+#include "ResolvExpr/typeops.h"
+#include "SynTree/Expression.h"
+#include "TupleAssignment.h"
+#include "SemanticError.h"
+
+#include <functional>
+#include <algorithm>
+#include <iterator>
+#include <iostream>
+#include <cassert>
+#include <set>
+
+namespace Tuples {
+  TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 )
+    : currentFinder(f), matcher(0), hasMatched( false ) {}
+
+  bool TupleAssignSpotter::pointsToTuple( Expression *expr ) {
+    // also check for function returning tuple of reference types
+    if(AddressExpr *addr = dynamic_cast<AddressExpr *>(expr) )
+      if( isTuple(addr->get_arg() ) )
+	return true;
+    return false;
+  }
+
+  bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) {
+    if( dynamic_cast<TupleType *>(decl->get_type()) )
+      return true;
+    return false;
+  }
+
+  bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) {
+    // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function
+    if ( !expr ) return false;
+
+    if( dynamic_cast<TupleExpr *>(expr) )
+      return true;
+    else if( VariableExpr *var = dynamic_cast<VariableExpr *>(expr) ) {
+      if( isTupleVar(var->get_var()) )
+	return true;
+    }
+
+    return false;
+  }
+
+  bool TupleAssignSpotter::match() {
+    assert ( matcher != 0 );
+
+    std::list< Expression * > new_assigns;
+    if (! matcher->match(new_assigns) )
+      return false;
+
+    if( new_assigns.empty() ) return false;
+    /*return */matcher->solve( new_assigns );
+    if( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
+      // now resolve new assignments
+      std::list< Expression * > solved_assigns;
+      ResolvExpr::AltList solved_alts;
+      assert( currentFinder != 0 );
+
+      ResolvExpr::AltList current;
+      for( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
+	//try {
+	ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
+	finder.findWithAdjustment(*i);
+	// prune expressions that don't coincide with
+	ResolvExpr::AltList alts = finder.get_alternatives();
+	assert( alts.size() == 1 );
+	assert(alts.front().expr != 0 );
+	current.push_back( finder.get_alternatives().front() );
+	solved_assigns.push_back( alts.front().expr->clone() );
+	//solved_assigns.back()->print(std::cerr);
+	/*} catch( ... ) {
+	  continue; // no reasonable alternative found
+	  }*/
+      }
+      options.add_option( current );
+
+      return true;
+    } else { // mass assignment
+      //if( new_assigns.empty() ) return false;
+      std::list< Expression * > solved_assigns;
+      ResolvExpr::AltList solved_alts;
+      assert( currentFinder != 0 );
+
+      ResolvExpr::AltList current;
+      if ( optMass.empty() ) {
+	for( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
+	  optMass.push_back( ResolvExpr::AltList() );
+      }
+      int cnt = 0;
+      for( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
+
+	ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
+	finder.findWithAdjustment(*i);
+	ResolvExpr::AltList alts = finder.get_alternatives();
+	assert( alts.size() == 1 );
+	assert(alts.front().expr != 0 );
+	current.push_back( finder.get_alternatives().front() );
+	optMass[cnt].push_back( finder.get_alternatives().front() );
+	solved_assigns.push_back( alts.front().expr->clone() );
+      }
+
+      return true;
+    }
+
+    return false;
+  }
+
+  bool TupleAssignSpotter::isMVR( Expression *expr ) {
+    if( expr->get_results().size() > 1 ) {
+      // MVR processing
+      return true;
+    }
+    return false;
+  }
+
+  bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
+    if(  NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
+
+      if( assgnop->get_name() == std::string("?=?") ) {
+
+	for( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
+	  assert( ali->size() == 2 );
+	  ResolvExpr::AltList::iterator opit = ali->begin();
+	  ResolvExpr::Alternative op1 = *opit, op2 = *(++opit);
+
+	  if( pointsToTuple(op1.expr) ) { // also handles tuple vars
+	    if ( isTuple( op2.expr, true ) )
+	      matcher = new MultipleAssignMatcher(op1.expr, op2.expr);
+	    else if( isMVR( op2.expr ) ) {
+	      // handle MVR differently
+	    } else
+	      // mass assignment
+	      matcher = new MassAssignMatcher(op1.expr, op2.expr);
+
+	    std::list< ResolvExpr::AltList > options;
+	    if( match() )
+	      /*
+	      if( hasMatched ) {
+		// throw SemanticError("Ambiguous tuple assignment");
+	      } else {*/
+		// Matched for the first time
+		hasMatched = true;
+		/*} */
+	  } /* else if ( isTuple( op2 ) )
+	    throw SemanticError("Inapplicable tuple assignment.");
+	    */
+	}
+
+	if( hasMatched ) {
+	  if( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
+	    //options.print( std::cerr );
+	    std::list< ResolvExpr::AltList >best = options.get_best();
+	    if( best.size() == 1 ) {
+	      std::list<Expression *> solved_assigns;
+	      for( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ){
+		solved_assigns.push_back( i->expr );
+	      }
+	      /* assigning cost zero? */
+	      currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
+	    }
+	  } else {
+	    assert(! optMass.empty() );
+	    ResolvExpr::AltList winners;
+	    for( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i )
+	      findMinCostAlt( i->begin(), i->end(), back_inserter(winners) );
+
+	    std::list< Expression *> solved_assigns;
+	    for( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i )
+	      solved_assigns.push_back( i->expr );
+	    currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
+	  }
+	}
+      }
+    }
+    return hasMatched;
+  }
+
+  void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) {
+    lhs.clear();
+    if(AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) )
+      if( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
+	std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) );
+
+    rhs.clear();
+  }
+
+  TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{
+    init(_lhs,_rhs);
+  }
+
+  TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{
+    init(_lhs,_rhs);
+
+    if( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) )
+      std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) );
+  }
+
+  UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
+    if ( left && right ) {
+      std::list< Expression * > args;
+      args.push_back(new AddressExpr(left->clone()));  args.push_back(right->clone());
+      return new UntypedExpr(new NameExpr("?=?"), args);
+    } else
+      throw 0; // xxx - diagnose the problem
+  }
+
+  bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
+    if ( lhs.empty() || (rhs.size() != 1) ) return false;
+
+    for( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) {
+      std::list< Expression * > args;
+      args.push_back( new AddressExpr(*l) );
+      args.push_back( rhs.front() );
+      out.push_back( new UntypedExpr(new NameExpr("?=?"), args) );
+    }
+
+    return true;
+  }
+
+  bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
+    /*
+    std::list< Expression * > solved_assigns;
+    ResolvExpr::AltList solved_alts;
+    assert( currentFinder != 0 );
+
+    ResolvExpr::AltList current;
+    if ( optMass.empty() ) {
+      for( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
+	optMass.push_back( ResolvExpr::AltList() );
+    }
+    int cnt = 0;
+    for( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
+
+      ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
+      finder.findWithAdjustment(*i);
+      ResolvExpr::AltList alts = finder.get_alternatives();
+      assert( alts.size() == 1 );
+      assert(alts.front().expr != 0 );
+      current.push_back( finder.get_alternatives().front() );
+      optMass[cnt].push_back( finder.get_alternatives().front() );
+      solved_assigns.push_back( alts.front().expr->clone() );
+    }
+    */
+    return true;
+  }
+
+  bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
+    // need more complicated matching
+    if( lhs.size() == rhs.size() ) {
+      zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
+      return true;
+    } //else
+    //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/
+    return false;
+  }
+
+  bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
+    /*
+    std::list< Expression * > solved_assigns;
+    ResolvExpr::AltList solved_alts;
+    assert( currentFinder != 0 );
+
+    ResolvExpr::AltList current;
+    for( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
+      //try {
+      ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
+      finder.findWithAdjustment(*i);
+      // prune expressions that don't coincide with
+      ResolvExpr::AltList alts = finder.get_alternatives();
+      assert( alts.size() == 1 );
+      assert(alts.front().expr != 0 );
+      current.push_back( finder.get_alternatives().front() );
+      solved_assigns.push_back( alts.front().expr->clone() );
+      //solved_assigns.back()->print(std::cerr);
+      //} catch( ... ) {
+      //continue; // no reasonable alternative found
+      //}
+    }
+    options.add_option( current );
+    */
+
+    return true;
+  }
+
+  void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) {
+    using namespace std;
+
+    options.push_back( opt );
+    /*
+      vector< Cost > costs;
+      costs.reserve( opt.size() );
+      transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) );
+    */
+    // transpose matrix
+    if ( costMatrix.empty() )
+      for( unsigned int i = 0; i< opt.size(); ++i)
+	costMatrix.push_back( vector<ResolvExpr::Cost>() );
+
+    int cnt = 0;
+    for( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ )
+      costMatrix[cnt].push_back( i->cost );
+
+    return;
+  }
+
+  std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
+    using namespace std;
+    using namespace ResolvExpr;
+    list< ResolvExpr::AltList > ret;
+    list< multiset<int> > solns;
+    for( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
+      list<int> current;
+      findMinCost( i->begin(), i->end(), back_inserter(current) );
+      solns.push_back( multiset<int>(current.begin(), current.end()) );
+    }
+    // need to combine
+    multiset<int> result;
+    lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) );
+    if( result.size() != 1 )
+      throw SemanticError("Ambiguous tuple expression");
+    ret.push_back(get_option( *(result.begin() )));
+    return ret;
+  }
+
+  void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
+    using namespace std;
+
+    for( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
+      for( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j )
+	ostr << *j << " " ;
+      ostr << std::endl;
+    }
+    
+    return;
+  }
+
+  ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) {
+    return alt.cost;
+  }
+
+  template< typename InputIterator, typename OutputIterator >
+  void
+  TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out )
+  {
+    using namespace ResolvExpr;
+    std::list<int> alternatives;
+
+    // select the alternatives that have the minimum parameter cost
+    Cost minCost = Cost::infinity;
+    unsigned int index = 0;
+    for( InputIterator i = begin; i != end; ++i, index++ ) {
+      if( *i < minCost ) {
+        minCost = *i;
+        alternatives.clear();
+        alternatives.push_back( index );
+      } else if( *i == minCost ) {
+        alternatives.push_back( index );
+      }
+    }
+    std::copy( alternatives.begin(), alternatives.end(), out );
+  }
+
+  template< class InputIterator, class OutputIterator >
+  void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ){
+    if( begin == end ) return;
+    InputIterator test = begin;
+
+    if(++test == end)
+      { copy(begin->begin(), begin->end(), out); return; }
+
+
+    std::multiset<int> cur; // InputIterator::value_type::value_type
+    copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) );
+
+    while( test != end ) {
+      std::multiset<int> temp;
+      set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) );
+      cur.clear();
+      copy( temp.begin(), temp.end(), inserter(cur,cur.begin()));
+      ++test;
+    }
+
+    copy( cur.begin(), cur.end(), out );
+    return;
+  }
+
+
+  ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) {
+    if( index >= options.size() )
+      throw 0; // XXX
+    std::list< ResolvExpr::AltList >::iterator it = options.begin();
+    for( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it );
+    return *it;
+  }
+
+
+} // namespace Tuples
