//
// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// TypeEnvironment.h --
//
// Author           : Richard C. Bilson
// Created On       : Sun May 17 12:24:58 2015
// Last Modified By : Aaron B. Moss
// Last Modified On : Mon Jun 18 11:58:00 2018
// Update Count     : 4
//

#pragma once

#include <iostream>                    // for ostream
#include <list>                        // for list, list<>::iterator, list<>...
#include <map>                         // for map, map<>::value_compare
#include <set>                         // for set
#include <string>                      // for string
#include <utility>                     // for move, swap

#include "WidenMode.h"                 // for WidenMode

#include "SynTree/Declaration.h"       // for TypeDecl::Data, DeclarationWit...
#include "SynTree/SynTree.h"           // for UniqueId
#include "SynTree/Type.h"              // for Type, Type::ForallList
#include "SynTree/TypeSubstitution.h"  // for TypeSubstitution

namespace ResolvExpr {
	// adding this comparison operator significantly improves assertion resolution run time for
	// some cases. The current resolution algorithm's speed partially depends on the order of
	// assertions. Assertions which have fewer possible matches should appear before
	// assertions which have more possible matches. This seems to imply that this could
	// be further improved by providing an indexer as an additional argument and ordering based
	// on the number of matches of the same kind (object, function) for the names of the
	// declarations.
	//
	// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this comparator.
	//
	// Note: since this compares pointers for position, minor changes in the source file that affect
	// memory layout can alter compilation time in unpredictable ways. For example, the placement
	// of a line directive can reorder type pointers with respect to each other so that assertions
	// are seen in different orders, causing a potentially different number of unification calls when
	// resolving assertions. I've seen a TU go from 36 seconds to 27 seconds by reordering line directives
	// alone, so it would be nice to fix this comparison so that assertions compare more consistently.
	// I've tried to modify this to compare on mangle name instead of type as the second comparator, but
	// this causes some assertions to never be recorded. More investigation is needed.
	struct AssertCompare {
		bool operator()( DeclarationWithType * d1, DeclarationWithType * d2 ) const {
			int cmp = d1->get_name().compare( d2->get_name() );
			return cmp < 0 ||
				( cmp == 0 && d1->get_type() < d2->get_type() );
		}
	};
	struct AssertionSetValue {
		bool isUsed;
		// chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID of an assertion on the current type,
		// with each successive ID being the ID of an assertion pulled in by the previous ID. The last ID in the chain is
		// the ID of the assertion that pulled in the current assertion.
		std::list< UniqueId > idChain;
	};
	typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
	typedef std::map< std::string, TypeDecl::Data > OpenVarSet;

	void printAssertionSet( const AssertionSet &, std::ostream &, int indent = 0 );
	void printOpenVarSet( const OpenVarSet &, std::ostream &, int indent = 0 );

	struct EqvClass {
		std::set< std::string > vars;
		Type *type;
		bool allowWidening;
		TypeDecl::Data data;

		void initialize( const EqvClass &src, EqvClass &dest );
		void initialize( const EqvClass &src, EqvClass &dest, const Type *ty );
		EqvClass();
		EqvClass( const EqvClass &other );
		EqvClass( const EqvClass &other, const Type *ty );
		EqvClass( EqvClass &&other );
		EqvClass &operator=( const EqvClass &other );
		EqvClass &operator=( EqvClass &&other );
		~EqvClass();
		void print( std::ostream &os, Indenter indent = {} ) const;

		/// Takes ownership of `ty`, freeing old `type`
		void set_type(Type* ty);
	};

	class TypeEnvironment {
	  public:
		const EqvClass* lookup( const std::string &var ) const;
	  private:
		void add( EqvClass &&eqvClass  );
	  public:
		void add( const Type::ForallList &tyDecls );
		void add( const TypeSubstitution & sub );
		template< typename SynTreeClass > int apply( SynTreeClass *&type ) const;
		template< typename SynTreeClass > int applyFree( SynTreeClass *&type ) const;
		void makeSubstitution( TypeSubstitution &result ) const;
		bool isEmpty() const { return env.empty(); }
		void print( std::ostream &os, Indenter indent = {} ) const;
		// void combine( const TypeEnvironment &second, Type *(*combineFunc)( Type*, Type* ) );
		void simpleCombine( const TypeEnvironment &second );
		void extractOpenVars( OpenVarSet &openVars ) const;
		TypeEnvironment *clone() const { return new TypeEnvironment( *this ); }

		/// Iteratively adds the environment of a new actual (with allowWidening = false),
		/// and extracts open variables.
		void addActual( const TypeEnvironment& actualEnv, OpenVarSet& openVars );

		/// Binds the type class represented by `typeInst` to the type `bindTo`; will add 
		/// the class if needed. Returns false on failure.
		bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );
		
		/// Binds the type classes represented by `var1` and `var2` together; will add 
		/// one or both classes if needed. Returns false on failure.
		bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer );

		/// Disallows widening for all bindings in the environment
		void forbidWidening();

		using iterator = std::list< EqvClass >::const_iterator;
		iterator begin() const { return env.begin(); }
		iterator end() const { return env.end(); }

	  private:
		std::list< EqvClass > env;
		
		std::list< EqvClass >::iterator internal_lookup( const std::string &var );
	};

	template< typename SynTreeClass >
	int TypeEnvironment::apply( SynTreeClass *&type ) const {
		TypeSubstitution sub;
		makeSubstitution( sub );
		return sub.apply( type );
	}

	template< typename SynTreeClass >
	int TypeEnvironment::applyFree( SynTreeClass *&type ) const {
		TypeSubstitution sub;
		makeSubstitution( sub );
		return sub.applyFree( type );
	}

	std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env );
} // namespace ResolvExpr

// Local Variables: //
// tab-width: 4 //
// mode: c++ //
// compile-command: "make install" //
// End: //