//
// 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.
//
// ScopedMap.h --
//
// Author           : Aaron B. Moss
// Created On       : Fri Feb 19 13:55:00 2016
// Last Modified By : Aaron B. Moss
// Last Modified On : Fri Feb 19 13:55:00 2016
// Update Count     : 1
//

#ifndef _TYPEMAP_H
#define _TYPEMAP_H

#include <map>
#include <string>
#include <utility>
#include <vector>

#include "SynTree/Type.h"
#include "SynTree/Visitor.h"

namespace ResolvExpr {

	/// A map from types to some value; lookup is done by structural decomposition on types.
	/// The TypeMap stores its values by reference, so stored objects should be kept alive by the caller.
	/// The scoping mechanism essentially by keeping a list of changes to roll back, then rolling them back
	/// WARNING: This map is only incompletely and approximately consistent with the resolution rules in Unify.cc;
	/// it has potential, if extended, to form the basis of a resolver that is more performant than the current
	/// linear-search-by-unification approach, but is only currently used for finding assignment operators in GenPoly::box.
	template< typename Value >
	class TypeMap {
		/// Map of names to types
		typedef typename std::map< std::string, Value* > ValueMap;
		typedef typename ValueMap::iterator ValueMapIterator;

		Value *voidValue;                                     ///< Value for void type
		Value *basicValue[BasicType::NUMBER_OF_BASIC_TYPES];  ///< Values for basic types
		Value *pointerValue;                                  ///< Value for all pointer types
		Value *voidPointerValue;                              ///< Value for void* types
		Value *functionPointerValue;                          ///< Value for all function pointer types
		ValueMap structValue;                                 ///< Values for struct types, indexed by name
		ValueMap unionValue;                                  ///< Values for struct types, indexed by name
		ValueMap enumValue;                                   ///< Values for struct types, indexed by name

		/// Information needed to roll back one scope change
		struct Rollback {
			/// One scope of pointer rollbacks
			typedef std::vector< std::pair< Value **, Value* > > PointerScope;
			/// One scope of map rollbacks
			typedef std::vector< std::pair< ValueMapIterator, Value* > > MapScope;

			PointerScope pointers;  ///< Value pointers to roll back to their previous state
			MapScope mapNodes;      ///< Value map iterators to roll back to their previous state

			void addRollback( Value **loc, Value *old ) {
				pointers.push_back( std::make_pair( loc, old ) );
			}

			void addRollback( ValueMapIterator loc, Value *old ) {
				mapNodes.push_back( std::make_pair( loc, old ) );
			}
		};

		std::vector< Rollback > scopes;  ///< Scope rollback information

		struct Lookup : public Visitor {
			Lookup( TypeMap<Value> &typeMap ) : typeMap( typeMap ), found( 0 ), toInsert( 0 ) {}

			/// Inserts a new value into the map; returns the old value (if set, NULL otherwise).
			/// key must be non-null.
			Value *insert( Type *key, Value *val ) {
				toInsert = val;
				key->accept( *this );
				return found;
			}

			/// Looks up a value in the map.
			/// key must be non-null.
			Value *find( Type *key ) {
				//toInsert = 0;
				key->accept( *this );
				return found;
			}

			void findAndReplace( Value *&loc ) {
				found = loc;
				if ( toInsert ) {
					typeMap.scopes.back().addRollback( &loc, found );
					loc = toInsert;
				}
			}

			void findAndReplace( ValueMap &map, const std::string &name ) {
				ValueMapIterator loc = map.find( name );
				if ( loc != map.end() ) {
					found = loc->second;
					if ( toInsert ) {
						typeMap.scopes.back().addRollback( loc, found );
						loc->second = toInsert;
					}
				} else if ( toInsert ) {
					loc = map.insert( loc, std::make_pair( name, toInsert ) );
					typeMap.scopes.back().addRollback( loc, found );
				}
			}

			virtual void visit( VoidType *voidType ) {
				findAndReplace( typeMap.voidValue );
			}

			virtual void visit( BasicType *basicType ) {
				findAndReplace( typeMap.basicValue[basicType->get_kind()] );
			}

			virtual void visit( PointerType *pointerType ) {
				// NOTE This is one of the places where the apporoximation of the resolver is (deliberately) poor;
				// A better version would likely not equate all pointer types to a match.
				if ( dynamic_cast< FunctionType* >( pointerType->get_base() ) ) {
					findAndReplace( typeMap.functionPointerValue );
				} else if ( dynamic_cast< VoidType* >( pointerType->get_base() ) ) {
					findAndReplace( typeMap.voidPointerValue );
				} else {
					findAndReplace( typeMap.pointerValue );
				}
			}

			virtual void visit( ArrayType *arrayType ) {
				if ( dynamic_cast< FunctionType* >( arrayType->get_base() ) ) {
					findAndReplace( typeMap.functionPointerValue );
				} else {
					findAndReplace( typeMap.pointerValue );
				}
			}

			virtual void visit( FunctionType *functionType ) {
				findAndReplace( typeMap.functionPointerValue );
			}

			virtual void visit( StructInstType *structType ) {
				findAndReplace( typeMap.structValue, structType->get_name() );
			}

			virtual void visit( UnionInstType *unionType ) {
				findAndReplace( typeMap.unionValue, unionType->get_name() );
			}

			virtual void visit( EnumInstType *enumType ) {
				findAndReplace( typeMap.enumValue, enumType->get_name() );
			}

			TypeMap<Value> &typeMap;  ///< map storage
			Value *found;             ///< Value found (NULL if none yet)
			Value *toInsert;          ///< Value to insert (NULL if a lookup)
		};  // struct Lookup
		friend struct Lookup;

	public:
		/// Starts a new scope
		void beginScope() {
			Rollback scope;
			scopes.push_back(scope);
		}

		/// Ends a scope; rolls back any changes made during that scope
		void endScope() {
			Rollback &scope = scopes.back();
			/// Roll back pointer changes
			for (unsigned i = 0; i < scope.pointers.size(); ++i) {
				*scope.pointers[i].first = scope.pointers[i].second;
			}
			/// Roll back map changes
			for (unsigned i = 0; i < scope.mapNodes.size(); ++i) {
				scope.mapNodes[i].first->second = scope.mapNodes[i].second;
			}
			scopes.pop_back();
		}

		TypeMap() : voidValue( 0 ), pointerValue( 0 ), voidPointerValue( 0 ), functionPointerValue( 0 ), structValue(), unionValue(), enumValue(), scopes() {
			beginScope();
			for (int i = 0; i < BasicType::NUMBER_OF_BASIC_TYPES; ++i) { basicValue[i] = 0; }
		}

		/// Inserts a new value into the map; returns the old value (if set, NULL otherwise).
		/// key, val must be non-null.
		Value *insert( Type *key, Value *val ) {
			Lookup searcher( *this );
			return searcher.insert( key, val );
		}

		/// Looks up a value in the map.
		/// key must be non-null
		Value *find( Type *key ) {
			Lookup searcher( *this );
			return searcher.find( key );
		}

	}; // class TypeMap

}  // namespace ResolvExpr

#endif // _TYPEMAP_H

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