# This file is part of NIT ( http://www.nitlanguage.org ).
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

# Table layout builders
# Tables are used to implement objects mecanisms like:
#  * message sending
#  * attribute accessing
#  * typing
#  * resolution (for generic types)
# This module provides various layout for object tables:
#  * coloring
#  * binary matrix
#  * perfect hashing (and & mod operators)
module layout_builders

import abstract_compiler

# Layouts

# A layout is the result of computation by builders
# it contains necessary informations for basic table creation
class Layout[E: Object]
	# Ids or each element
	var ids: Map[E, Int] = new HashMap[E, Int]
	# Fixed positions of each element in all tables
	var pos: Map[E, Int] = new HashMap[E, Int]
end

# A PHLayout is used everywere the builder used perfect hashing
# it adds masks and hashes informations to std layout
class PHLayout[HOLDER: Object, E: Object]
	super Layout[E]
	# Masks used by hash function
	var masks: Map[HOLDER, Int] = new HashMap[HOLDER, Int]
	# Positions of each element for each tables
	var hashes: Map[HOLDER, Map[E, Int]] = new HashMap[HOLDER, Map[E, Int]]
end

# Builders

# TypingLayoutBuilder is used to build a layout for typing tables (by type or by class)
interface TypingLayoutBuilder[E: Object]
	# Build typing table layout
	# elements: the set of elements (classes or types) used in typing tables
	fun build_layout(elements: Set[E]): Layout[E] is abstract
	# Get the poset used for table layout construction
	# REQUIRE: build_layout
	fun poset: nullable POSet[E] is abstract
end

# Layout builder dedicated to vft, attribute & VT tables
interface PropertyLayoutBuilder[E: PropertyLayoutElement]
	# Build table layout for attributes, methods and virtual types
	# elements: the associative map between classes and properties to use in table layout
	fun build_layout(elements: Map[MClass, Set[E]]): Layout[E] is abstract
end

# Used to create a common ancestors to MProperty and MPropDef
# Required for polymorphic calls
# FIXME: there should be a better way
interface PropertyLayoutElement end

redef class MProperty
	super PropertyLayoutElement
end

redef class MPropDef
	super PropertyLayoutElement
end

# For resolution tables (generics)
interface ResolutionLayoutBuilder
	# Build resolution table layout
	# elements: association between classes and resolved types
	fun build_layout(elements: Map[MClassType, Set[MType]]): Layout[MType] is abstract
end

# POSet builders

# A POSet builder build a poset for a set of MType or MClass
# the resulting poset is used by the layout builders
private abstract class POSetBuilder[E: Object]
	private var mmodule: MModule
	init(mmodule: MModule) do self.mmodule = mmodule
	# Build the poset from `elements`
	private fun build_poset(elements: Set[E]): POSet[E] is abstract
end

# A TypingLayoutBuilder used for MType based typing
# such as in separate compilers
private class MTypePOSetBuilder
	super POSetBuilder[MType]
	redef fun build_poset(elements) do
		var poset = new POSet[MType]
		for e in elements do
			poset.add_node(e)
			for o in elements do
				if e == o then continue
				if e.is_subtype(mmodule, null, o) then
					poset.add_edge(e, o)
				end
			end
		end
		return poset
	end
end

# A TypingLayoutBuilder used for MClass based typing
# such as in erased compilers or used in property coloring
private class MClassPOSetBuilder
	super POSetBuilder[MClass]
	redef fun build_poset(elements) do return mmodule.flatten_mclass_hierarchy
end

# Matrice computers

# Abstract layout builder for resolution tables using Binary Matrix (BM)
abstract class TypingBMizer[E: Object]
	super TypingLayoutBuilder[E]

	private var mmodule: MModule
	private var poset_builder: POSetBuilder[E]
	private var poset_cache: nullable POSet[E]

	private init(mmodule: MModule, poset_builder: POSetBuilder[E]) do
		self.mmodule = mmodule
		self.poset_builder = poset_builder
	end

	redef fun poset do return poset_cache

	# Compute mtypes ids and position using BM
	redef fun build_layout(elements: Set[E]): Layout[E] do
		var result = new Layout[E]
		var ids = new HashMap[E, Int]
		poset_cache = poset_builder.build_poset(elements)
		var lin = poset.to_a
		poset.sort(lin)
		for element in lin do
			ids[element] = ids.length
		end
		result.ids = ids
		result.pos = ids
		return result
	end
end

# Layout builder for typing tables based on classes using Binary Matrix (BM)
class MTypeBMizer
	super TypingBMizer[MType]
	init(mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule))
end

# Layout builder for typing tables based on types using Binary Matrix (BM)
class MClassBMizer
	super TypingBMizer[MClass]
	init(mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule))
end

# Layout builder for resolution tables using Binary Matrix (BM)
class ResolutionBMizer
	super ResolutionLayoutBuilder

	init do end

	redef fun build_layout(elements) do
		var result = new Layout[MType]
		var ids = new HashMap[MType, Int]
		var color = 0
		for mclasstype, mclasstypes in elements do
			for element in mclasstypes do
				if ids.has_key(element) then continue
				ids[element] = color
				color += 1
			end
		end
		result.ids = ids
		result.pos = ids
		return result
	end
end

# Abstract Layout builder for mproperties using Binary Matrix (BM)
class MPropertyBMizer[E: PropertyLayoutElement]
	super PropertyLayoutBuilder[E]

	var mmodule: MModule

	init(mmodule: MModule) do self.mmodule = mmodule

	redef fun build_layout(elements) do
		var result = new Layout[E]
		var ids = new HashMap[E, Int]
		var lin = new Array[MClass]
		lin.add_all(elements.keys)
		self.mmodule.linearize_mclasses(lin)
		for mclass in lin do
			for mproperty in elements[mclass] do
				if ids.has_key(mproperty) then continue
				ids[mproperty] = ids.length
			end
		end
		result.pos = ids
		return result
	end
end

# Colorers

# Abstract Layout builder for typing table using coloration (CL)
abstract class TypingColorer[E: Object]
	super TypingLayoutBuilder[E]

	private var core: Set[E] = new HashSet[E]
	private var crown: Set[E] = new HashSet[E]
	private var border: Set[E] = new HashSet[E]
	private var coloration_result: Map[E, Int] = new HashMap[E, Int]

	private var mmodule: MModule
	private var poset_builder: POSetBuilder[E]
	private var poset_cache: nullable POSet[E]

	private init(mmodule: MModule, poset_builder: POSetBuilder[E]) do
		self.mmodule = mmodule
		self.poset_builder = poset_builder
	end

	redef fun poset do return poset_cache

	# Compute the layout with coloring
	redef fun build_layout(elements: Set[E]): Layout[E] do
		poset_cache = poset_builder.build_poset(elements)
		var result = new Layout[E]
		result.ids = compute_ids(elements)
		result.pos = colorize(elements)
		return result
	end

	private fun compute_ids(elements: Set[E]): Map[E, Int] do
		var ids = new HashMap[E, Int]
		for element in reverse_linearize(elements) do
			ids[element] = ids.length
		end
		return ids
	end

	private fun colorize(elements: Set[E]): Map[E, Int] do
		tag_elements(elements)
		build_conflicts_graph
		colorize_elements(core)
		colorize_elements(border)
		colorize_elements(crown)
		return coloration_result
	end

	# Colorize a collection of elements
	private fun colorize_elements(elements: Set[E]) do
		var min_color = 0

		var lin = reverse_linearize(elements)
		for element in lin do
			var color = min_color
			while not self.is_color_free(element, elements, color) do
				color += 1
			end
			coloration_result[element] = color
			color = min_color
		end
	end

	# Check if a related element to the element already use the color
	private fun is_color_free(element: E, elements: Set[E], color: Int): Bool do
		if conflicts_graph.has_key(element) then
			for st in conflicts_graph[element] do
				if coloration_result.has_key(st) and coloration_result[st] == color then return false
			end
		end
		for st in self.poset[element].greaters do
			if st == element then continue
			if coloration_result.has_key(st) and coloration_result[st] == color then return false
		end
		return true
	end

	# Tag elements as core, crown or border
	private fun tag_elements(elements: Set[E]) do
		for element in elements do
			# Check if sub elements are all in single inheritance
			var all_subelements_si = true
			for subelem in self.poset[element].smallers do
				if self.poset[subelem].direct_greaters.length > 1 then
					all_subelements_si = false
					break
				end
			end

			# Tag as core, crown or border
			if self.poset[element].direct_greaters.length > 1 then
				core.add_all(self.poset[element].greaters)
				if all_subelements_si then
					border.add(element)
				end
			else if not all_subelements_si then
				core.add_all(self.poset[element].greaters)
			else
				crown.add(element)
			end
		end
	end

	# Conflicts graph of elements hierarchy (two types are in conflict if they have common subelements)
	private fun build_conflicts_graph do
		self.conflicts_graph = new HashMap[E, HashSet[E]]
		var core = reverse_linearize(self.core)
		for t in core do
			for i in self.linear_extension(t) do
				if t == i then continue

				var lin_i = self.linear_extension(i)

				for j in self.linear_extension(t) do
					if i == j or j == t then continue
					var lin_j = self.linear_extension(j)

					var d_ij = lin_i - lin_j
					var d_ji = lin_j - lin_i

					for ed1 in d_ij do
						if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
						# add ed1 x ed2 to conflicts graph
						for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
					end
					for ed1 in d_ij do
						if not conflicts_graph.has_key(ed1) then conflicts_graph[ed1] = new HashSet[E]
						# add ed1 x ed2 to conflicts graph
						for ed2 in d_ji do conflicts_graph[ed1].add(ed2)
					end
				end
			end
		end
	end

	private var conflicts_graph: nullable HashMap[E, Set[E]]

	# cache for linear_extensions
	private var linear_extensions_cache: Map[E, Array[E]] = new HashMap[E, Array[E]]

	# Return a linear_extension of super_elements of the element
	private fun linear_extension(element: E): Array[E] do
		if not self.linear_extensions_cache.has_key(element) then
			var supers = new HashSet[E]
			supers.add_all(self.poset[element].greaters)
			self.linear_extensions_cache[element] = self.linearize(supers)
		end
		return self.linear_extensions_cache[element]
	end

	private fun reverse_linearize(elements: Set[E]): Array[E] do
		var lin = new Array[E]
		lin.add_all(elements)
		poset.sort(lin)
		return lin
	end
	private fun linearize(elements: Set[E]): Array[E] do return reverse_linearize(elements).reversed
end

# Layout builder for typing tables based on types using coloration (CL)
class MTypeColorer
	super TypingColorer[MType]
	init(mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule))
end

# Layout builder for typing tables based on classes using coloration (CL)
class MClassColorer
	super TypingColorer[MClass]
	init(mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule))
end

# Abstract Layout builder for properties tables using coloration (CL)
class MPropertyColorer[E: PropertyLayoutElement]
	super PropertyLayoutBuilder[E]

	private var mmodule: MModule
	private var class_colorer: MClassColorer
	private var coloration_result: Map[E, Int] = new HashMap[E, Int]

	init(mmodule: MModule, class_colorer: MClassColorer) do
		self.mmodule = mmodule
		self.class_colorer = class_colorer
	end

	# Compute mclasses ids and position using BM
	redef fun build_layout(elements: Map[MClass, Set[E]]): Layout[E] do
		var result = new Layout[E]
		result.pos = self.colorize(elements)
		return result
	end

	private fun colorize(elements: Map[MClass, Set[E]]): Map[E, Int] do
		self.colorize_core(elements)
		self.colorize_crown(elements)
		return self.coloration_result
	end

	# Colorize properties of the core hierarchy
	private fun colorize_core(elements: Map[MClass, Set[E]]) do
		var min_color = 0
		for mclass in self.class_colorer.core do
			var color = min_color
			# check last color used by parents
			color = max_color(color, mclass.in_hierarchy(mmodule).direct_greaters, elements)
			# check max color used in conflicts
			if self.class_colorer.conflicts_graph.has_key(mclass) then
				color = max_color(color, self.class_colorer.conflicts_graph[mclass], elements)
			end
			colorize_elements(elements[mclass], color)
		end
	end

	# Colorize properties of the crown hierarchy
	private fun colorize_crown(elements: Map[MClass, Set[E]]) do
		for mclass in self.class_colorer.crown do
			var parents = new HashSet[MClass]
			if mmodule.flatten_mclass_hierarchy.has(mclass) then
				parents.add_all(mclass.in_hierarchy(mmodule).direct_greaters)
			end
			colorize_elements(elements[mclass], max_color(0, parents, elements))
		end
	end

	# Colorize a collection of mproperties given a starting color
	private fun colorize_elements(elements: Collection[E], start_color: Int) do
		for element in elements do
			if self.coloration_result.has_key(element) then continue
			self.coloration_result[element] = start_color
			start_color += 1
		end
	end

	private fun max_color(min_color: Int, mclasses: Collection[MClass], elements: Map[MClass, Set[E]]): Int do
		var max_color = min_color

		for mclass in mclasses do
			for mproperty in elements[mclass] do
				var color = min_color
				if self.coloration_result.has_key(mproperty) then
					color = self.coloration_result[mproperty]
					if color >= max_color then max_color = color + 1
				end
			end
		end
		return max_color
	end
end

# Layout builder for resolution tables using coloration (CL)
class ResolutionColorer
	super ResolutionLayoutBuilder

	private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]

	init do end

	# Compute resolved types colors
	redef fun build_layout(elements) do
		self.build_conflicts_graph(elements)
		var result = new Layout[MType]
		result.ids = self.compute_ids(elements)
		result.pos = self.colorize_elements(elements)
		return result
	end

	private fun compute_ids(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
		var ids = new HashMap[MType, Int]
		var color = 0
		for mclasstype, mclasstypes in elements do
			for element in mclasstypes do
				if ids.has_key(element) then continue
				ids[element] = color
				color += 1
			end
		end
		return ids
	end

	# Colorize a collection of elements
	private fun colorize_elements(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
		var min_color = 0
		for mclasstype, mclasstypes in elements do
			for element in mclasstypes do
				if self.coloration_result.has_key(element) then continue
				var color = min_color
				while not self.is_color_free(element, color) do
					color += 1
				end
				coloration_result[element] = color
				color = min_color
			end
		end
		return self.coloration_result
	end

	# Check if a related element to the element already use the color
	private fun is_color_free(element: MType, color: Int): Bool do
		if conflicts_graph.has_key(element) then
			for st in conflicts_graph[element] do
				if coloration_result.has_key(st) and coloration_result[st] == color then return false
			end
		end
		return true
	end

	# look for unanchored types generated by the same type
	private fun build_conflicts_graph(elements: Map[MClassType, Set[MType]]) do
		for mclasstype, mtypes in elements do
			for mtype in mtypes do
				for otype in mtypes do
					if otype == mtype then continue
					self.add_conflict(mtype, otype)
				end
			end
		end
	end

	private var conflicts_graph: Map[MType, Set[MType]] = new HashMap[MType, Set[MType]]

	private fun add_conflict(mtype: MType, otype: MType) do
		if mtype == otype then return
		if not self.conflicts_graph.has_key(mtype) then  self.conflicts_graph[mtype] = new HashSet[MType]
		self.conflicts_graph[mtype].add(otype)
		if not self.conflicts_graph.has_key(otype) then  self.conflicts_graph[otype] = new HashSet[MType]
		self.conflicts_graph[otype].add(mtype)
	end
end

# Perfect Hashing (PH)
# T = type of holder
# U = type of elements to hash
private class PerfectHasher[T: Object, U: Object]

	var operator: PHOperator

	init do end

	# Compute mask for each holders
	fun compute_masks(conflicts: Map[T, Set[U]], ids: Map[U, Int]): Map[T, Int] do
		var masks = new HashMap[T, Int]
		for mclasstype, mtypes in conflicts do
			masks[mclasstype] = compute_mask(mtypes, ids)
		end
		return masks
	end

	private fun compute_mask(mtypes: Set[U], ids: Map[U, Int]): Int do
		var mask = 0
		loop
			var used = new List[Int]
			for mtype in mtypes do
				var res = operator.op(mask, ids[mtype])
				if used.has(res) then
					break
				else
					used.add(res)
				end
			end
			if used.length == mtypes.length then break
			mask += 1
		end
		return mask
	end

	# Compute hash for each element in each holder
	fun compute_hashes(elements: Map[T, Set[U]], ids: Map[U, Int], masks: Map[T, Int]): Map[T, Map[U, Int]] do
		var hashes = new HashMap[T, Map[U, Int]]
		for mclasstype, mtypes in elements do
			var mask = masks[mclasstype]
			var inhashes = new HashMap[U, Int]
			for mtype in mtypes do
				inhashes[mtype] = operator.op(mask, ids[mtype])
			end
			hashes[mclasstype] = inhashes
		end
		return hashes
	end
end

# Abstract operator used for perfect hashing
abstract class PHOperator
	# hash `id` using `mask`
	fun op(mask: Int, id:Int): Int is abstract
end

# Hashing using modulo (MOD) operator
# slower but compact
class PHModOperator
	super PHOperator
	init do end
	redef fun op(mask, id) do return mask % id
end

# Hashing using binary and (AND) operator
# faster but sparse
class PHAndOperator
	super PHOperator
	init do end
	redef fun op(mask, id) do return mask.bin_and(id)
end

# Layout builder for typing tables using perfect hashing (PH)
class TypingHasher[E: Object]
	super PerfectHasher[E, E]
	super TypingLayoutBuilder[E]

	private var mmodule: MModule
	private var poset_builder: POSetBuilder[E]
	private var poset_cache: nullable POSet[E]

	private init(mmodule: MModule, poset_builder: POSetBuilder[E], operator: PHOperator) do
		self.operator = operator
		self.mmodule = mmodule
		self.poset_builder = poset_builder
	end

	redef fun build_layout(elements: Set[E]): PHLayout[E, E] do
		poset_cache = poset_builder.build_poset(elements)
		var result = new PHLayout[E, E]
		var conflicts = self.build_conflicts(elements)
		result.ids = self.compute_ids
		result.masks = self.compute_masks(conflicts, result.ids)
		result.hashes = self.compute_hashes(conflicts, result.ids, result.masks)
		return result
	end

	# Ids start from 1 instead of 0
	private fun compute_ids: Map[E, Int] do
		var ids = new HashMap[E, Int]
		var lin = poset.to_a
		poset.sort(lin)
		for e in lin do
			ids[e] = ids.length + 1
		end
		return ids
	end

	private fun build_conflicts(elements: Set[E]): Map[E, Set[E]] do
		var conflicts = new HashMap[E, Set[E]]
		for e in elements do
			var supers = new HashSet[E]
			supers.add_all(self.poset[e].greaters)
			supers.add(e)
			conflicts[e] = supers
		end
		return conflicts
	end
end

# Layout builder for typing tables with types using perfect hashing (PH)
class MTypeHasher
	super TypingHasher[MType]
	init(operator: PHOperator, mmodule: MModule) do super(mmodule, new MTypePOSetBuilder(mmodule), operator)
end

# Layout builder for typing tables with classes using perfect hashing (PH)
class MClassHasher
	super TypingHasher[MClass]
	init(operator: PHOperator, mmodule: MModule) do super(mmodule, new MClassPOSetBuilder(mmodule), operator)
end

# Abstract layout builder for properties tables using perfect hashing (PH)
class MPropertyHasher[E: PropertyLayoutElement]
	super PerfectHasher[MClass, E]
	super PropertyLayoutBuilder[E]

	var mmodule: MModule

	init(operator: PHOperator, mmodule: MModule) do
		self.operator = operator
		self.mmodule = mmodule
	end

	fun build_poset(mclasses: Set[MClass]): POSet[MClass] do
		var poset = new POSet[MClass]
		for e in mclasses do
			poset.add_node(e)
			for o in mclasses do
				if e == o or not mmodule.flatten_mclass_hierarchy.has(e) then continue
				if e.in_hierarchy(mmodule) < o then poset.add_edge(e, o)
			end
		end
		return poset
	end

	redef fun build_layout(elements) do
		var result = new PHLayout[MClass, E]
		var ids = new HashMap[E, Int]
		var mclasses = new HashSet[MClass]
		mclasses.add_all(elements.keys)
		var poset = build_poset(mclasses)
		var lin = poset.to_a
		poset.sort(lin)
		for mclass in lin.reversed do
			for mproperty in elements[mclass] do
				if ids.has_key(mproperty) then continue
				ids[mproperty] = ids.length + 1
			end
		end
		result.ids = ids
		result.pos = ids
		result.masks = self.compute_masks(elements, ids)
		result.hashes = self.compute_hashes(elements, ids, result.masks)
		return result
	end
end

# Layout builder for resolution tables using perfect hashing (PH)
class ResolutionHasher
	super PerfectHasher[MClassType, MType]
	super ResolutionLayoutBuilder

	init(operator: PHOperator) do self.operator = operator

	# Compute resolved types masks and hashes
	redef fun build_layout(elements) do
		var result = new PHLayout[MClassType, MType]
		var ids = new HashMap[MType, Int]
		var color = 1
		for mclasstype, mclasstypes in elements do
			for element in mclasstypes do
				if ids.has_key(element) then continue
				ids[element] = color
				color += 1
			end
		end
		result.ids = ids
		result.pos = ids
		result.masks = self.compute_masks(elements, ids)
		result.hashes = self.compute_hashes(elements, ids, result.masks)
		return result
	end
end