var hashes: Map[HOLDER, Map[E, Int]] = new HashMap[HOLDER, Map[E, Int]]
end
-class PropertyLayout[E: Object]
- # Fixed positions of each element in all tables
- var pos: Map[E, Int] = new HashMap[E, Int]
-end
-
# Builders
-abstract class TypingLayoutBuilder[E: Object]
-
- type LAYOUT: Layout[E]
-
- # Compute elements ids and position
- fun build_layout(elements: Set[E]): LAYOUT is abstract
+interface TypingLayoutBuilder[E: Object]
+ # Build typing table layout
+ fun build_layout(elements: Set[E]): Layout[E] is abstract
end
-# Typing Layout builder using binary matrix (BM)
-class BMTypingLayoutBuilder[E: Object]
- super TypingLayoutBuilder[E]
-
- private var bmizer: TypingBMizer[E]
-
- init(bmizer: TypingBMizer[E]) do self.bmizer = bmizer
-
- redef fun build_layout(elements) do return bmizer.build_layout(elements)
+interface PropertyLayoutBuilder[E: MProperty]
+ # Build table layout for attributes, methods and virtual types
+ fun build_layout(elements: Set[MClass]): Layout[E] is abstract
end
-# Typing Layout builder using Coloring (CL)
-class CLTypingLayoutBuilder[E: Object]
- super TypingLayoutBuilder[E]
-
- private var colorer: TypingColorer[E]
-
- init(colorer: TypingColorer[E]) do self.colorer = colorer
-
- redef fun build_layout(elements) do return colorer.build_layout(elements)
+interface ResolutionLayoutBuilder
+ # Build resolution table layout
+ fun build_layout(elements: Map[MClassType, Set[MType]]): Layout[MType] is abstract
end
-# Layout builder for MType using Perfect Hashing (PH)
-class PHTypeLayoutBuilder
- super TypingLayoutBuilder[MType]
+# Matrice computers
- redef type LAYOUT: PHLayout[MType, MType]
+abstract class TypingBMizer[E: Object]
+ super TypingLayoutBuilder[E]
- private var hasher: PerfectHasher[MType, MType]
- private var mmodule: MModule
+ var mmodule: MModule
- init(mmodule: MModule, operator: PHOperator) do
+ init(mmodule: MModule) do
self.mmodule = mmodule
- self.hasher = new PerfectHasher[MType, MType](operator)
- end
-
- private fun build_conflicts(mtypes: Set[MType]): Map[MType, Set[MType]] do
- var conflicts = new HashMap[MType, Set[MType]]
- for mtype in mtypes do
- var supers = self.mmodule.super_mtypes(mtype, mtypes)
- supers.add(mtype)
- conflicts[mtype] = supers
- end
- return conflicts
end
# Compute mtypes ids and position using BM
- redef fun build_layout(mtypes) do
- var result = new PHLayout[MType, MType]
- var conflicts = build_conflicts(mtypes)
- result.ids = self.compute_ids(mtypes)
- result.masks = self.hasher.compute_masks(conflicts, result.ids)
- result.hashes = self.hasher.compute_hashes(conflicts, result.ids, result.masks)
- return result
- end
-
- # Ids start from 1 instead of 0
- private fun compute_ids(mtypes: Set[MType]): Map[MType, Int] do
- var ids = new HashMap[MType, Int]
- var lin = self.mmodule.reverse_linearize_mtypes(mtypes)
- for mtype in lin do
- ids[mtype] = ids.length + 1
- end
- return ids
- end
-end
-
-# Layout builder for MClass using Perfect Hashing (PH)
-class PHClassLayoutBuilder
- super TypingLayoutBuilder[MClass]
-
- redef type LAYOUT: PHLayout[MClass, MClass]
-
- private var hasher: PerfectHasher[MClass, MClass]
- private var mmodule: MModule
-
- init(mmodule: MModule, operator: PHOperator) do
- self.mmodule = mmodule
- self.hasher = new PerfectHasher[MClass, MClass](operator)
- end
-
- private fun build_conflicts(mclasses: Set[MClass]): Map[MClass, Set[MClass]] do
- var conflicts = new HashMap[MClass, Set[MClass]]
- for mclass in mclasses do
- var supers = self.mmodule.super_mclasses(mclass)
- supers.add(mclass)
- conflicts[mclass] = supers
- end
- return conflicts
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new PHLayout[MClass, MClass]
- var conflicts = build_conflicts(mclasses)
- result.ids = self.compute_ids(mclasses)
- result.masks = self.hasher.compute_masks(conflicts, result.ids)
- result.hashes = self.hasher.compute_hashes(conflicts, result.ids, result.masks)
- return result
- end
-
- # Ids start from 1 instead of 0
- private fun compute_ids(mclasses: Set[MClass]): Map[MClass, Int] do
- var ids = new HashMap[MClass, Int]
- var lin = self.mmodule.reverse_linearize_mclasses(mclasses)
- for mclass in lin do
- ids[mclass] = ids.length + 1
+ redef fun build_layout(elements: Set[E]): Layout[E] do
+ var result = new Layout[E]
+ var ids = new HashMap[E, Int]
+ var lin = self.reverse_linearize(elements)
+ for element in lin do
+ ids[element] = ids.length
end
- return ids
- end
-end
-
-abstract class PropertyLayoutBuilder[E: MProperty]
-
- type LAYOUT: PropertyLayout[E]
-
- # Compute properties ids and position
- fun build_layout(mclasses: Set[MClass]): LAYOUT is abstract
-end
-
-# Layout builder for MProperty using Coloring (CL)
-class CLPropertyLayoutBuilder[E: MProperty]
- super PropertyLayoutBuilder[E]
-
- private var colorer: MPropertyColorer[E]
-
- init(colorer: MPropertyColorer[E]) do
- self.colorer = colorer
- end
-
- # Compute mclasses ids and position using BM
- redef fun build_layout(mclasses) do
- var result = new PropertyLayout[E]
- result.pos = self.colorer.colorize(mclasses)
+ result.ids = ids
+ result.pos = ids
return result
end
-end
-# Layout builder for MProperty using Perfect Hashing (PH)
-# TODO implement this class without sublcassing CL builder
-class PHPropertyLayoutBuilder[E: MProperty]
- super CLPropertyLayoutBuilder[E]
+ private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
end
-abstract class ResolutionLayoutBuilder
-
- type LAYOUT: Layout[MType]
-
- init do end
+class MTypeBMizer
+ super TypingBMizer[MType]
- fun build_layout(elements: Map[MClassType, Set[MType]]): LAYOUT is abstract
+ init(mmodule: MModule) do super(mmodule)
- 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
+ redef fun reverse_linearize(elements) do
+ return self.mmodule.reverse_linearize_mtypes(elements)
end
end
-# Layout builder for MClass using Binary Matrix (BM)
-class BMResolutionLayoutBuilder
- super ResolutionLayoutBuilder
+class MClassBMizer
+ super TypingBMizer[MClass]
- init do super
+ init(mmodule: MModule) do super(mmodule)
- # Compute resolved types position using BM
- redef fun build_layout(elements) do
- var result = new Layout[MType]
- result.ids = self.compute_ids(elements)
- result.pos = result.ids
- return result
+ redef fun reverse_linearize(elements) do
+ return self.mmodule.reverse_linearize_mclasses(elements)
end
end
-# Layout builder for resolution tables using Coloring (CL)
-class CLResolutionLayoutBuilder
+# Layout builder for resolution tables using Binary Matrix (BM)
+class ResolutionBMizer
super ResolutionLayoutBuilder
- private var colorer: ResolutionColorer = new ResolutionColorer
-
- init do super
+ init do end
- # Compute resolved types colors
redef fun build_layout(elements) do
var result = new Layout[MType]
- result.ids = self.compute_ids(elements)
- result.pos = self.colorer.colorize(elements)
- return result
- end
-end
-
-# Layout builder for resolution table using Perfect Hashing (PH)
-class PHResolutionLayoutBuilder
- super ResolutionLayoutBuilder
-
- redef type LAYOUT: PHLayout[MClassType, MType]
-
- private var hasher: PerfectHasher[MClassType, MType]
-
- init(operator: PHOperator) do self.hasher = new PerfectHasher[MClassType, MType](operator)
-
- # Compute resolved types masks and hashes
- redef fun build_layout(elements) do
- var result = new PHLayout[MClassType, MType]
- result.ids = self.compute_ids(elements)
- result.pos = result.ids
- result.masks = self.hasher.compute_masks(elements, result.ids)
- result.hashes = self.hasher.compute_hashes(elements, result.ids, result.masks)
- return result
- end
-
- redef fun compute_ids(elements) do
var ids = new HashMap[MType, Int]
- var color = 1
+ var color = 0
for mclasstype, mclasstypes in elements do
for element in mclasstypes do
if ids.has_key(element) then continue
color += 1
end
end
- return ids
+ result.ids = ids
+ result.pos = ids
+ return result
end
end
-# Matrice computers
+# Abstract BMizing for MProperties
+abstract class MPropertyBMizer[E: MProperty]
+ super PropertyLayoutBuilder[E]
-abstract class TypingBMizer[E: Object]
+ type MPROP: MProperty
var mmodule: MModule
- init(mmodule: MModule) do
- self.mmodule = mmodule
- end
+ init(mmodule: MModule) do self.mmodule = mmodule
- # Compute mtypes ids and position using BM
- fun build_layout(elements: Set[E]): Layout[E] do
+ redef fun build_layout(elements) do
var result = new Layout[E]
var ids = new HashMap[E, Int]
- var lin = self.reverse_linearize(elements)
- for element in lin do
- ids[element] = ids.length
+ var lin = linearize_mclasses(elements)
+ for mclass in lin do
+ for mproperty in properties(mclass) do
+ if ids.has_key(mproperty) then continue
+ ids[mproperty] = ids.length
+ end
end
- result.ids = ids
result.pos = ids
return result
end
- private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
+ private fun properties(mclass: MClass): Set[E] do
+ var properties = new HashSet[E]
+ for mprop in self.mmodule.properties(mclass) do
+ if mprop isa MPROP then properties.add(mprop)
+ end
+ return properties
+ end
+
+ private fun linearize_mclasses(mclasses: Set[MClass]): Array[MClass] is abstract
end
-class MTypeBMizer
- super TypingBMizer[MType]
+# BMizing for MMethods
+class MMethodBMizer
+ super MPropertyBMizer[MMethod]
+ redef type MPROP: MMethod
init(mmodule: MModule) do super(mmodule)
-
- redef fun reverse_linearize(elements) do
- return self.mmodule.reverse_linearize_mtypes(elements)
- end
+ # Less holes in tables with reverse linearization for method tables
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.reverse_linearize_mclasses(mclasses)
end
-class MClassBMizer
- super TypingBMizer[MClass]
+# BMizing for MMAttributes
+class MAttributeBMizer
+ super MPropertyBMizer[MAttribute]
+ redef type MPROP: MAttribute
init(mmodule: MModule) do super(mmodule)
+ # Less holes in tables with linearization for attribute tables
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.linearize_mclasses_2(mclasses)
+end
- redef fun reverse_linearize(elements) do
- return self.mmodule.reverse_linearize_mclasses(elements)
- end
+# BMizing for MVirtualTypeProps
+class MVirtualTypePropBMizer
+ super MPropertyBMizer[MVirtualTypeProp]
+
+ redef type MPROP: MVirtualTypeProp
+ init(mmodule: MModule) do super(mmodule)
+ # Less holes in tables with reverse linearization for method tables
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.reverse_linearize_mclasses(mclasses)
end
# Colorers
abstract class TypingColorer[E: Object]
+ super TypingLayoutBuilder[E]
private var core: Set[E] = new HashSet[E]
private var crown: Set[E] = new HashSet[E]
init do end
# Compute the layout with coloring
- fun build_layout(elements: Set[E]): Layout[E] do
+ redef fun build_layout(elements: Set[E]): Layout[E] do
var result = new Layout[E]
result.ids = compute_ids(elements)
result.pos = colorize(elements)
fun parent_elements(element: MClass): Set[MClass] do return self.mmodule.parent_mclasses(element)
redef fun is_element_mi(element, elements) do return self.parent_elements(element).length > 1
redef fun sub_elements(element, elements) do do return self.mmodule.sub_mclasses(element)
- redef fun linearize(elements) do return self.mmodule.linearize_mclasses(elements)
+ redef fun linearize(elements) do return self.mmodule.linearize_mclasses_2(elements)
redef fun reverse_linearize(elements) do return self.mmodule.reverse_linearize_mclasses(elements)
end
# MProperty coloring
abstract class MPropertyColorer[E: MProperty]
+ super PropertyLayoutBuilder[E]
+
+ type MPROP: MProperty
private var mmodule: MModule
private var class_colorer: MClassColorer
self.class_colorer = new MClassColorer(mmodule)
end
- fun colorize(mclasses: Set[MClass]): Map[E, Int] do
+ # Compute mclasses ids and position using BM
+ redef fun build_layout(mclasses: Set[MClass]): Layout[E] do
+ var result = new Layout[E]
+ result.pos = self.colorize(mclasses)
+ return result
+ end
+
+ private fun colorize(mclasses: Set[MClass]): Map[E, Int] do
self.class_colorer.tag_elements(mclasses)
self.class_colorer.build_conflicts_graph(mclasses)
self.colorize_core(self.class_colorer.core)
end
# Filter properties
- private fun properties(mclass: MClass): Set[E] is abstract
+ private fun properties(mclass: MClass): Set[E] do
+ var properties = new HashSet[E]
+ for mprop in self.mmodule.properties(mclass) do
+ if mprop isa MPROP then properties.add(mprop)
+ end
+ return properties
+ end
end
# Coloring for MMethods
class MMethodColorer
super MPropertyColorer[MMethod]
+ redef type MPROP: MMethod
init(mmodule: MModule) do super
-
- redef fun properties(mclass) do
- var properties = new HashSet[MMethod]
- for mprop in self.mmodule.properties(mclass) do
- if mprop isa MMethod then properties.add(mprop)
- end
- return properties
- end
end
# Coloring for MMAttributes
class MAttributeColorer
super MPropertyColorer[MAttribute]
+ redef type MPROP: MAttribute
init(mmodule: MModule) do super
-
- redef fun properties(mclass) do
- var properties = new HashSet[MAttribute]
- for mprop in self.mmodule.properties(mclass) do
- if mprop isa MAttribute then properties.add(mprop)
- end
- return properties
- end
end
# Coloring for MVirtualTypeProps
class MVirtualTypePropColorer
super MPropertyColorer[MVirtualTypeProp]
+ redef type MPROP: MVirtualTypeProp
init(mmodule: MModule) do super
-
- redef fun properties(mclass) do
- var properties = new HashSet[MVirtualTypeProp]
- for mprop in self.mmodule.properties(mclass) do
- if mprop isa MVirtualTypeProp then properties.add(mprop)
- end
- return properties
- end
end
# Colorer for type resolution table
class ResolutionColorer
+ super ResolutionLayoutBuilder
private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
init do end
- fun colorize(elements: Map[MClassType, Set[MType]]): Map[MType, Int] do
+ # Compute resolved types colors
+ redef fun build_layout(elements) do
self.build_conflicts_graph(elements)
- self.colorize_elements(elements)
- return coloration_result
+ 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
- fun colorize_elements(elements: Map[MClassType, Set[MType]]) do
+ 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
color = min_color
end
end
+ return self.coloration_result
end
# Check if a related element to the element already use the color
init do end
redef fun op(mask, id) do return mask.bin_and(id)
end
+
+class TypingHasher[E: Object]
+ super PerfectHasher[E, E]
+ super TypingLayoutBuilder[E]
+
+ var mmodule: MModule
+
+ init(operator: PHOperator, mmodule: MModule) do
+ super(operator)
+ self.mmodule = mmodule
+ end
+
+ redef fun build_layout(elements: Set[E]): PHLayout[E, E] do
+ var result = new PHLayout[E, E]
+ var conflicts = self.build_conflicts(elements)
+ result.ids = self.compute_ids(elements)
+ 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(elements: Set[E]): Map[E, Int] do
+ var ids = new HashMap[E, Int]
+ var lin = self.reverse_linearize(elements)
+ 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 = self.super_elements(e, elements)
+ supers.add(e)
+ conflicts[e] = supers
+ end
+ return conflicts
+ end
+
+ private fun super_elements(element: E, elements: Set[E]): Set[E] is abstract
+ private fun reverse_linearize(elements: Set[E]): Array[E] is abstract
+end
+
+class MTypeHasher
+ super TypingHasher[MType]
+
+ init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+
+ redef fun super_elements(element, elements) do
+ return self.mmodule.super_mtypes(element, elements)
+ end
+
+ redef fun reverse_linearize(elements) do
+ return self.mmodule.reverse_linearize_mtypes(elements)
+ end
+end
+
+class MClassHasher
+ super TypingHasher[MClass]
+
+ init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+
+ redef fun super_elements(element, elements) do
+ return self.mmodule.super_mclasses(element)
+ end
+
+ redef fun reverse_linearize(elements) do
+ return self.mmodule.reverse_linearize_mclasses(elements)
+ end
+end
+
+# Abstract perfect hasher for MProperties
+class MPropertyHasher[E: MProperty]
+ super PerfectHasher[MClass, E]
+ super PropertyLayoutBuilder[E]
+
+ type MPROP: MProperty
+
+ var mmodule: MModule
+
+ init(operator: PHOperator, mmodule: MModule) do
+ super(operator)
+ self.mmodule = mmodule
+ end
+
+ redef fun build_layout(mclasses) do
+ var result = new PHLayout[MClass, E]
+ var ids = new HashMap[E, Int]
+ var elements = new HashMap[MClass, Set[E]]
+ var lin = linearize_mclasses(mclasses)
+ for mclass in lin do
+ var mproperties = properties(mclass)
+ for mproperty in mproperties do
+ if ids.has_key(mproperty) then continue
+ ids[mproperty] = ids.length + 1
+ end
+ elements[mclass] = mproperties
+ 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
+
+ private fun properties(mclass: MClass): Set[E] do
+ var properties = new HashSet[E]
+ for mprop in self.mmodule.properties(mclass) do
+ if mprop isa MPROP then properties.add(mprop)
+ end
+ return properties
+ end
+
+ private fun linearize_mclasses(mclasses: Set[MClass]): Array[MClass] is abstract
+end
+
+# Perfect hashing for MMethods
+class MMethodHasher
+ super MPropertyHasher[MMethod]
+
+ redef type MPROP: MMethod
+ init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.reverse_linearize_mclasses(mclasses)
+end
+
+# Perfect hashing for MMAttributes
+class MAttributeHasher
+ super MPropertyHasher[MAttribute]
+
+ redef type MPROP: MAttribute
+ init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.linearize_mclasses_2(mclasses)
+end
+
+# Perfect hashing for MVirtualTypeProps
+class MVirtualTypePropHasher
+ super MPropertyHasher[MVirtualTypeProp]
+
+ redef type MPROP: MVirtualTypeProp
+ init(operator: PHOperator, mmodule: MModule) do super(operator, mmodule)
+ redef fun linearize_mclasses(mclasses) do return self.mmodule.reverse_linearize_mclasses(mclasses)
+end
+
+class ResolutionHasher
+ super PerfectHasher[MClassType, MType]
+ super ResolutionLayoutBuilder
+
+ init(operator: PHOperator) do super(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
nitlanguage / nit.git / blobdiff