//
// 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.
//
// DeclStats.cpp -- Print statistics about a translation unit's declarations.
//
// Author           : Andrew Beach
// Created On       : Fri Oct  1 14:26:00 2021
// Last Modified By : Andrew Beach
// Last Modified On : Wed Oct  8 11:24:00 2021
// Update Count     : 0
//

#include "DeclStats.hpp"

#include "AST/LinkageSpec.hpp"
#include "AST/Pass.hpp"
#include "AST/Print.hpp"
#include "Common/VectorMap.h"

#include <iostream>
#include <map>
#include <unordered_map>
#include <unordered_set>

// Everything but printDeclStats at the bottom is hidden.
namespace {

template<typename T>
void sum( T & l, const T & r ) { l += r; }

void sum( VectorMap<unsigned> & l, const VectorMap<unsigned> & r ) {
	l.reserve( r.size() );
	for ( unsigned i = 0 ; i < r.size() ; ++i ) {
		l[i] += r[i];
	}
}

template<typename KeyT>
void sum( std::map<KeyT, unsigned> & l, const std::map<KeyT, unsigned> & r ) {
	for ( const auto & entry : r ) {
		l[ entry.first ] += entry.second;
	}
}

template<typename KeyT>
void sum( std::unordered_map<KeyT, unsigned> & l,
		const std::unordered_map<KeyT, unsigned> & r ) {
	for ( const auto & entry : r ) {
		l[ entry.first ] += entry.second;
	}
}

/// Stores statistics on a single group of arguments or return values.
struct ArgPackStats {
	/// Count of decls with each number of elements.
	VectorMap<unsigned> n;
	/// Count of decls with each number of basic type elements.
	VectorMap<unsigned> n_basic;
	/// Count of decls with each number of generic type elements.
	VectorMap<unsigned> n_generic;
	/// Count of decls with each number of polymorphic elements.
	VectorMap<unsigned> n_poly;
	/// Count of decls with each number of non-generic compound types.
	VectorMap<unsigned> n_compound;
	/// Count of decls with each percentage of basic type elements.
	std::map<unsigned, unsigned> p_basic;
	/// Count of decls with each percentage of generic type elements.
	std::map<unsigned, unsigned> p_generic;
	/// Count of decls with each percentage of polymorphic elements.
	std::map<unsigned, unsigned> p_poly;
	/// Count of decls with each percentage of non-generic compound type elements.
	std::map<unsigned, unsigned> p_compound;
	/// Count of decls with each number of distinct types in the pack.
	VectorMap<unsigned> n_types;
	/// Count of decls with each percentage of new types in lists.
	/// Types used in the parameter list that recur in the return list are not considered to be new.
	std::map<unsigned, unsigned> p_new;

	ArgPackStats& operator+=( const ArgPackStats& other ) {
		sum(n, other.n);
		sum(n_basic, other.n_basic);
		sum(n_generic, other.n_generic);
		sum(n_poly, other.n_poly);
		sum(n_compound, other.n_compound);
		sum(p_basic, other.p_basic);
		sum(p_generic, other.p_generic);
		sum(p_poly, other.p_poly);
		sum(p_compound, other.p_compound);
		sum(n_types, other.n_types);
		sum(p_new, other.p_new);

		return *this;
	}
};

/// Collected statistics on a group of declarations.
struct Stats {
	/// Total number of declarations in these statistics.
	unsigned n_decls;
	/// Count of declarations with each number of assertion parameters.
	VectorMap<unsigned> n_type_params;
	/// Count of generic types with each number of type parameters.
	VectorMap<unsigned> n_generic_params;
	/// Count of maximum nesting depth of types.
	VectorMap<unsigned> n_generic_nesting;
	/// Count of declarations with each name.
	std::unordered_map<std::string, unsigned> by_name;
	/// Count of uses of each basic type.
	std::unordered_map<std::string, unsigned> basic_type_names;
	/// Count of uses of each generic type name (includes "*", "[]", "(*)", "[,]").
	std::unordered_map<std::string, unsigned> generic_type_names;
	/// Count of uses of each non-generic aggregate type.
	std::unordered_map<std::string, unsigned> compound_type_names;
	/// Count of decls using each basic type.
	std::unordered_map<std::string, unsigned> basic_type_decls;
	/// Count of decls using each generic type (includes "*", "[]", "(*)", "[,]").
	std::unordered_map<std::string, unsigned> generic_type_decls;
	/// Count of decls using each compound type.
	std::unordered_map<std::string, unsigned> compound_type_decls;
	/// Stats for the parameter lists.
	ArgPackStats params;
	/// Stats for the return lists.
	ArgPackStats returns;

	/// Count of declarations with each number of assertions.
	std::map<unsigned, unsigned> n_assns;
	/// Stats for the assertions' parameters.
	ArgPackStats assn_params;
	/// Stats for the assertions' return types.
	ArgPackStats assn_returns;

	Stats& operator+=( const Stats& other ) {
		sum( n_decls, other.n_decls );
		sum( n_type_params, other.n_type_params );
		sum( n_generic_params, other.n_generic_params );
		sum( n_generic_nesting, other.n_generic_nesting );
		sum( by_name, other.by_name );
		sum( basic_type_names, other.basic_type_names );
		sum( generic_type_names, other.generic_type_names );
		sum( compound_type_names, other.compound_type_names );
		sum( basic_type_decls, other.basic_type_decls );
		sum( generic_type_decls, other.generic_type_decls );
		sum( compound_type_decls, other.compound_type_decls );
		sum( params, other.params );
		sum( returns, other.returns );
		sum( n_assns, other.n_assns );
		sum( assn_params, other.assn_params );
		sum( assn_returns, other.assn_returns );

		return *this;
	}

};

void update_max( unsigned & max, unsigned value ) {
	if ( max < value ) max = value;
}

// Where all unnamed specs are counted as one named spec group.
constexpr unsigned num_named_specs = 8;

unsigned linkage_index( ast::Linkage::Spec spec ) {
	switch ( spec.val ) {
	case ast::Linkage::Intrinsic.val:  return 0;
	case ast::Linkage::C.val:          return 1;
	case ast::Linkage::Cforall.val:    return 2;
	case ast::Linkage::AutoGen.val:    return 3;
	case ast::Linkage::Compiler.val:   return 4;
	case ast::Linkage::BuiltinCFA.val: return 5;
	case ast::Linkage::BuiltinC.val:   return 6;
	default:                           return 7;
	}
}

struct DeclStats : public ast::WithShortCircuiting {
	/// Stores separate stats per linkage.
	Stats by_linkage[num_named_specs];
	/// Stores manglenames already seen to avoid double-counting.
	std::unordered_set<std::string> seen_names;
	/// Overall stats.
	Stats total;
	/// Count of expressions with (depth, fanout)
	std::map<std::pair<unsigned, unsigned>, unsigned> exprs_by_fanout_at_depth;

	/// Count that we have seen a named type.
	void countType(
			const std::string & name, unsigned & n,
			std::unordered_map<std::string, unsigned> & names,
			std::unordered_map<std::string, unsigned> & decls,
			std::unordered_set<std::string> & elSeen ) {
		++n;
		++names[ name ];
		if ( elSeen.insert( name ).second ) {
			++decls[ name ];
		}
	}

	/// Perform type analysis on a subtype.
	void analyzeSubtype( const ast::Type * type, Stats & stats,
			std::unordered_set<std::string> & elSeen, unsigned & n_poly,
			bool & seen_poly, unsigned & max_depth, unsigned depth ) {
		// This kind of gets in the way of grouping arguments.
		unsigned ignored = 0;
		analyzeType(
			type, stats, elSeen, ignored, ignored, n_poly, ignored,
			seen_poly, max_depth, depth + 1 );
	}

	/// Perform type analysis on each subtype.
	void analyzeSubtypes(
			const std::vector<ast::ptr<ast::Type>> & types, Stats & stats,
			std::unordered_set<std::string> & elSeen, unsigned & n_poly,
			bool & seen_poly, unsigned & max_depth, unsigned depth ) {
		for ( const auto & type : types ) {
			analyzeSubtype( type, stats, elSeen, n_poly, seen_poly, max_depth, depth );
		}
	}

	/// Perform sub-type analysis on each subtype in an argument pack.
	void analyzeSubPack(
			const std::vector<ast::ptr<ast::Type>> & types, Stats & stats,
			std::unordered_set<std::string> & elSeen, unsigned & n_poly,
			bool & seen_poly, unsigned & max_depth, unsigned depth,
			unsigned & n_subs ) {
		// ... and count voids?
		for ( const auto & type : types ) {
			if ( type.as<ast::VoidType>() ) {
				++n_subs;
			}
			// Could this be in `else`?
			analyzeSubtype( type, stats, elSeen, n_poly, seen_poly, max_depth, depth );
		}
	}

	/// Analyze and gather stats from a single type.
	void analyzeType( const ast::ptr<ast::Type> & type, Stats & stats,
			std::unordered_set<std::string> & elSeen,
			unsigned & n_basic, unsigned & n_generic, unsigned & n_poly,
			unsigned & n_agg, bool & seen_poly,
			unsigned & max_depth, unsigned depth ) {
		// Almost a visit, except it is only types.
		if ( const ast::BasicType * t = type.as<ast::BasicType>() ) {
			const std::string name = ast::BasicType::typeNames[ t->kind ];
			countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen );
			update_max( max_depth, depth );
		} else if ( auto t = type.as<ast::PointerType>() ) {
			static const std::string name = "*";
			countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen );
			analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth );
			++stats.n_generic_params.at( 1 );
		} else if ( auto t = type.as<ast::ArrayType>() ) {
			static const std::string name = "[]";
			countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen );
			analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth );
			++stats.n_generic_params.at( 1 );
		} else if ( auto t = type.as<ast::ReferenceType>() ) {
			static const std::string name = "&";
			countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen );
			analyzeSubtype( t->base, stats, elSeen, n_poly, seen_poly, max_depth, depth );
			++stats.n_generic_params.at( 1 );
		} else if ( auto t = type.as<ast::FunctionType>() ) {
			static const std::string name = "(*)";
			countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen );
			unsigned n_subs = 0;
			analyzeSubPack( t->returns, stats, elSeen, n_poly, seen_poly, max_depth, depth, n_subs );
			analyzeSubPack( t->params, stats, elSeen, n_poly, seen_poly, max_depth, depth, n_subs );
			++stats.n_generic_params.at( n_subs );
		} else if ( auto t = type.as<ast::TypeInstType>() ) {
			if ( !seen_poly ) {
				++n_poly;
				seen_poly = true;
			}
			countType( t->name, n_agg, stats.compound_type_names,
					stats.compound_type_decls, elSeen );
			update_max( max_depth, depth );
		} else if ( auto t = type.as<ast::BaseInstType>() ) {
			auto & params = t->params;
			if ( params.empty() ) {
				countType( t->name, n_agg, stats.compound_type_names,
						stats.compound_type_decls, elSeen );
				update_max( max_depth, depth );
			} else {
				countType( t->name, n_generic, stats.generic_type_names,
						stats.generic_type_decls, elSeen );
				++stats.n_generic_params.at( params.size() );
			}
		} else if ( auto t = type.as<ast::TupleType>() ) {
			static const std::string name = "[,]";
			countType( name, n_generic, stats.generic_type_names, stats.generic_type_decls, elSeen);
			analyzeSubtypes( t->types, stats, elSeen, n_poly, seen_poly, max_depth, depth );
			++stats.n_generic_params.at( t->size() );
		} else if ( type.as<ast::VarArgsType>() ) {
			static const std::string name = "...";
			countType( name, n_agg, stats.compound_type_names, stats.compound_type_decls, elSeen );
			update_max( max_depth, depth );
		} else if ( type.as<ast::ZeroType>() ) {
			static const std::string name = "0";
			countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen );
			update_max( max_depth, depth );
		} else if ( type.as<ast::OneType>() ) {
			static const std::string name = "1";
			countType( name, n_basic, stats.basic_type_names, stats.basic_type_decls, elSeen );
			update_max( max_depth, depth );
		}
	}

	/// Update an ArgPackStats based on the list of types it repersents.
	void analyzeArgPack(
			const std::vector<ast::ptr<ast::Type>> & types,
			Stats & stats,
			ArgPackStats & packStats,
			// What are these two used for?
			std::unordered_set<std::string> & seen,
			std::unordered_set<std::string> & elSeen ) {
		std::unordered_set<std::string> type_names;
		unsigned n = 0;
		unsigned n_basic = 0;
		unsigned n_generic = 0;
		unsigned n_poly = 0;
		unsigned n_compound = 0;
		unsigned n_new = 0;

		for ( auto & type : types ) {
			n += type->size();

			std::stringstream ss;
			ast::print( ss, type );
			type_names.insert( ss.str() );
			if ( seen.insert( ss.str() ).second ) {
				++n_new;
			}

			bool seen_poly = false;
			unsigned max_depth = 0;
			analyzeType(
				type, stats, elSeen, n_basic, n_generic, n_poly, n_compound,
				seen_poly, max_depth, 0
			);
			++stats.n_generic_nesting.at( max_depth );
		}

		++packStats.n.at( n );
		++packStats.n_basic.at( n_basic );
		++packStats.n_generic.at( n_generic );
		++packStats.n_poly.at( n_poly );
		++packStats.n_compound.at( n_compound );
		if ( n > 0 ) {
			++packStats.p_basic[ n_basic * 100 / n ];
			++packStats.p_generic[ n_generic * 100 / n ];
			++packStats.p_poly[ n_poly * 100 / n ];
			++packStats.p_compound[ n_compound * 100 / n ];
			if ( n > 1 ) {
				++packStats.p_new[ (n_new - 1) * 100 / (n - 1) ];
			}
		}
		++packStats.n_types.at( types.size() );
	}

	/// Perform type analysis on a function type, storing information in the
	/// given ArgPackStats.
	void analyzeFunctionType( const ast::FunctionType * type, Stats& stats,
			ArgPackStats Stats::* param_pack,
			ArgPackStats Stats::* return_pack ) {
		// I still don't know what these are for.
		std::unordered_set<std::string> seen;
		std::unordered_set<std::string> elSeen;
		analyzeArgPack( type->params, stats, stats.*param_pack, seen, elSeen );
		analyzeArgPack( type->returns, stats, stats.*return_pack, seen, elSeen );
	}

	/// If the assertion is a function, return the function type.
	static const ast::FunctionType * getAssertionFunctionType(
			const ast::ptr<ast::DeclWithType> & assertion ) {
		if ( auto * assertionObject = assertion.as<ast::ObjectDecl>() ) {
			if ( auto * ptrTy = assertionObject->type.as<ast::PointerType>() ) {
				return ptrTy->base.as<ast::FunctionType>();
			} else {
				return assertionObject->type.as<ast::FunctionType>();
			}
		} else if ( auto * assertionDecl = assertion.as<ast::FunctionDecl>() ) {
			return assertionDecl->type;
		}
		return nullptr;
	}

	void analyzeFunctionDecl( const ast::FunctionDecl * decl ) {
		Stats & stats = by_linkage[ linkage_index( decl->linkage ) ];

		++stats.n_decls;
		const ast::FunctionType * type = decl->type.get();
		const ast::FunctionType::ForallList & forall = type->forall;
		++stats.n_type_params.at( forall.size() );
		unsigned num_assertions = 0;
		for ( const ast::ptr<ast::TypeInstType> & instType : forall ) {
			num_assertions += instType->base->assertions.size();
			for ( const auto & assertion : instType->base->assertions ) {
				if ( auto assertionType = getAssertionFunctionType( assertion ) ) {
					analyzeFunctionType( assertionType, stats,
							&Stats::assn_params, &Stats::assn_returns );
				}
			}
		}
		++stats.n_assns[ num_assertions ];
		++stats.by_name[ decl->name ];
		analyzeFunctionType( type, stats, &Stats::params, &Stats::returns );
	}

	void analyzeUntypedExpr( const ast::UntypedExpr * expr, unsigned depth ) {
		unsigned fanout = expr->args.size();
		++exprs_by_fanout_at_depth[ std::make_pair( depth, fanout ) ];

		for ( const ast::ptr<ast::Expr> & arg : expr->args ) {
			if ( const auto * untyped = arg.as<ast::UntypedExpr>() ) {
				analyzeUntypedExpr( untyped, depth + 1 );
			}
		}
	}

public:
	void previsit( const ast::UntypedExpr * expr ) {
		visit_children = false;
		analyzeUntypedExpr( expr, 0 );
	}

	void previsit( const ast::FunctionDecl * decl ) {
		const std::string & mangleName = decl->mangleName;
		const std::string & indexName = mangleName.empty() ? decl->name : mangleName;
		if ( seen_names.insert( indexName ).second ) {
			analyzeFunctionDecl( decl );
		}
	}

private:

	// Trying to avoid duplication by templates.
	// I couldn't do it in all cases.
	template<typename T, typename U>
	using getter = std::function<U(T const &)>;

	/// Print a single role, for every linkage and the totals.
	void printRow( const std::string & name, getter<Stats, unsigned> extract ) {
		std::cout << "\"" << name << "\",";
		for ( const Stats & stats : by_linkage ) {
			std::cout << "," << extract( stats );
		}
		std::cout << "," << extract( total ) << std::endl;
	}

	/// Print every row in a group of maps.
	template<typename Func>
	void printAllMap( const std::string & name, Func && extract ) {
		// Get all rows from the total stats.
		for ( auto & entry : extract( total ) ) {
			auto & key = entry.first;
			std::cout << "\"" << name << "\"," << key;
			for ( const auto & stats : by_linkage ) {
				const auto & map = extract( stats );
				auto it = map.find( key );
				if ( map.end() == it ) {
					std::cout << ",0";
				} else {
					std::cout << "," << it->second;
				}
			}
			std::cout << "," << entry.second << std::endl;
		}
	}

	/// Accumalate information, then print every row in the remaining maps.
	template<typename Func>
	void printAllSparseHisto( const std::string & name, Func && extract ) {
		std::map<unsigned, unsigned> histos[num_named_specs];
		std::map<unsigned, unsigned> histo_total;

		// Collect all data into the histograms.
		for ( const auto & entry : extract( total ) ) {
			++histo_total[ entry.second ];
		}

		for ( unsigned i = 0 ; i < num_named_specs ; ++i ) {
			for ( const auto & entry : extract( by_linkage[i] ) ) {
				++histos[ i ][ entry.second ];
			}
		}

		// Get all rows from the total stats.
		for ( const auto & entry : histo_total ) {
			const unsigned & key = entry.first;
			std::cout << "\"" << name << "\"," << key;
			for ( unsigned i = 0 ; i < num_named_specs ; ++i ) {
				auto it = histos[i].find( key );
				if ( histos[i].end() == it ) {
					std::cout << ",0";
				} else {
					std::cout << "," << it->second;
				}
			}
			std::cout << "," << entry.second << std::endl;
		}
	}

	void printAllPack( const std::string & name, ArgPackStats Stats::* field ) {
		printAllMap("n_basic_" + name, [&field](const Stats& stats) { return (stats.*field).n_basic; });
		printAllMap("n_generic_" + name, [&field](const Stats& stats) { return (stats.*field).n_generic; });
		printAllMap("n_poly_" + name, [&field](const Stats& stats) { return (stats.*field).n_poly; });
		printAllMap("n_compound_" + name, [&field](const Stats& stats) { return (stats.*field).n_compound; });
		printAllMap("n_" + name, [&field](const Stats& stats) { return (stats.*field).n; });
		printAllMap("%_basic_" + name, [&field](const Stats& stats) { return (stats.*field).p_basic; });
		printAllMap("%_generic_" + name, [&field](const Stats& stats) { return (stats.*field).p_generic; });
		printAllMap("%_poly_" + name, [&field](const Stats& stats) { return (stats.*field).p_poly; });
		printAllMap("%_compound_" + name, [&field](const Stats& stats) { return (stats.*field).p_compound; });
		printAllMap("n_distinct_types_" + name, [&field](const Stats& stats) { return (stats.*field).n_types; });
		printAllMap("%_new_types_in_" + name, [&field](const Stats& stats) { return (stats.*field).p_new; });
	}

	static void printPairMap (
			const std::string & name,
			const std::map<std::pair<unsigned, unsigned>, unsigned> & map ) {
		for ( const auto & entry : map ) {
			const auto & key = entry.first;
			std::cout << "\"" << name << "\"," << key.first << ','
				<< key.second << ',' << entry.second << std::endl;
		}
	}

public:
	void print() {
		for ( auto & stats : by_linkage ) {
			total += stats;
		}

		std::cout << ",,\"intrinsic\",\"Cforall\",\"C\",\"autogen\",\"compiler\",\"builtinCFA\",\"builtinC\",\"other\",\"TOTAL\"" << std::endl;

		printAllMap("n_type_params", [](const Stats& stats) { return stats.n_type_params; });
		printAllMap("n_generic_params", [](const Stats& stats) { return stats.n_generic_params; });
		printAllMap("n_generic_nesting", [](const Stats& stats) { return stats.n_generic_nesting; });
		printRow("n_decls", [](const Stats& stats) { return stats.n_decls; });
		printRow("unique_names", [](const Stats& stats) { return stats.by_name.size(); });
		printAllSparseHisto("overloads", [](const Stats& stats) { return stats.by_name; });
		printRow("basic_type_names", [](const Stats& stats) { return stats.basic_type_names.size(); });
		printAllSparseHisto("basic_type_uses", [](const Stats& stats) { return stats.basic_type_names; });
		printAllSparseHisto("decls_using_basic_type", [](const Stats& stats) { return stats.basic_type_decls; });
		printRow("generic_type_names", [](const Stats& stats) { return stats.generic_type_names.size(); });
		printAllSparseHisto("generic_type_uses", [](const Stats& stats) { return stats.generic_type_names; });
		printAllSparseHisto("decls_using_generic_type", [](const Stats& stats) { return stats.generic_type_decls; });
		printRow("compound_type_names", [](const Stats& stats) { return stats.compound_type_names.size(); });
		printAllSparseHisto("compound_type_uses", [](const Stats& stats) { return stats.compound_type_names; });
		printAllSparseHisto("decls_using_compound_type", [](const Stats& stats) { return stats.compound_type_decls; });
		printAllPack("params", &Stats::params);
		printAllPack("returns", &Stats::returns);
		printAllMap("n_assns", [](const Stats& stats) { return stats.n_assns; });
		printAllPack("assn_params", &Stats::assn_params);
		printAllPack("assn_returns", &Stats::assn_returns);
		std::cout << std::endl;

		printPairMap( "exprs by depth+fanout", exprs_by_fanout_at_depth );
	}
};

} // namespace

void printDeclStats( ast::TranslationUnit & translationUnit ) {
	ast::Pass<DeclStats> stats;
	accept_all( translationUnit, stats );
	stats.core.print();
}

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