class TypedRb::Types::Polymorphism::Topography
Keeps a graph of the var types according to the subsumption order relationship.
Attributes
groups[R]
mapping[R]
Public Class Methods
new(constraints)
click to toggle source
Create the graph based on the provided constraints as unlinked nodes.
# File lib/typed/types/polymorphism/unification.rb, line 149 def initialize(constraints) vars = constraints.reduce([]) do |acc, (l, _t, r)| vals = [l] if r.is_a?(Hash) vals << r[:return] else vals << r end acc + vals.select { |v| v.is_a?(TypeVariable) } end.uniq @groups = vars.each_with_object({}) do |var, groups| # lower_type, and upper_type can come from a bubbled up :send constraint type variable groups[var] = make_group(var => true) end end
Public Instance Methods
[](var)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 171 def [](var) found = if var.is_a?(TypeVariable) groups[var] else var end if found.nil? var_key = groups.keys.detect{ |key| key.name == var.name } found = groups[var_key] found || raise(TypedRb::Types::Polymorphism::UnificationError.new("Unification error, cannot find type variable #{var}")) else found end end
check_bindings()
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 256 def check_bindings groups.values.each do |group| next if group[:upper_type].nil? && group[:lower_type].nil? final_lower_type = find_type(group[:lower_type], :lower_type) final_upper_type = find_type(group[:upper_type], :upper_type) if final_lower_type && final_upper_type && final_lower_type != final_upper_type # final lower <= final upper compatible_lt_type?(final_upper_type, final_lower_type) end end end
do_bindings!()
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 203 def do_bindings! text = StringIO.new text << "Doing bindings:\n" num_bindings = 0 groups.values.uniq.each do |group| next if group [:upper_type].nil? && group[:lower_type].nil? group[:vars].keys.each do |var| final_lower_type = find_type(group[:lower_type], :lower_type) var.upper_bound = final_lower_type final_upper_type = find_type(group[:upper_type], :upper_type) var.lower_bound = final_upper_type # if var.wildcard? # final_binding_type = if final_lower_type == final_upper_type # final_upper_type # elsif final_lower_type && final_upper_type # final_lower_type # #elsif final_lower_type && final_upper_type.nil? # # final_lower_type # #else # # final_upper_type # end # binding_string = "[#{var.lower_bound ? var.lower_bound : '?'},#{var.upper_bound ? var.upper_bound : '?'}]" # if final_binding_type # num_bindings += 1 # text << "Final binding: #{var.variable} -> #{binding_string} : #{final_binding_type}\n" # var.bind(final_binding_type) # else # text << "Final binding: #{var.variable} -> #{binding_string} : UNKNOWN\n" # end # else final_binding_type = if final_lower_type == final_upper_type final_upper_type elsif final_lower_type && final_upper_type.nil? final_lower_type else final_upper_type end binding_string = "[#{var.lower_bound ? var.lower_bound : '?'},#{var.upper_bound ? var.upper_bound : '?'}]" if final_binding_type num_bindings += 1 text << "Final binding: #{var.variable} -> #{binding_string} : #{final_binding_type}\n" var.bind(final_binding_type) else text << "Final binding: #{var.variable} -> #{binding_string} : UNKNOWN\n" end # end end end text << "Found #{num_bindings} bindings" TypedRb.log(binding, :debug, text.string) end
find_type(value, type)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 268 def find_type(value, type) # type variable if value.is_a?(TypeVariable) value = if type == :lower_type value.upper_bound else value.lower_bound end find_type(value, type) # group elsif value.is_a?(Hash) && value[type] find_type(value[type], type) # type elsif value.is_a?(Type) value # nil else value # fail UnificationError, 'Cannot find type in type_variable binding' if value.nil? end end
grouped?(var)
click to toggle source
Is the variable in a group of variables?
# File lib/typed/types/polymorphism/unification.rb, line 167 def grouped?(var) groups[var][:grouped] end
merge(l, r)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 190 def merge(l, r) merge_groups(groups[l], groups[r]) end
print_groups()
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 290 def print_groups TypedRb.log(binding, :debug, 'Variable groups:') groups.values.uniq.each do |group| vars = group[:vars].keys.map(&:to_s).join(',') lower_type = group[:lower_type] ? group[:lower_type].to_s : '?' upper_type = group[:upper_type] ? group[:upper_type].to_s : '?' TypedRb.log(binding, :debug, "#{vars}:[#{lower_type},#{upper_type}]") end end
replace_groups(constraints)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 194 def replace_groups(constraints) groups.values.each do |group| group[:vars].keys.each do |l| constraints = replace(constraints, l, group) end end constraints end
vars()
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 186 def vars groups.keys end
Protected Instance Methods
make_group(vars)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 302 def make_group(vars) { vars: vars, grouped: vars.keys.size > 1, lower_type: nil, upper_type: nil } end
max_type(type_a, type_b)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 319 def max_type(type_a, type_b) if type_a.nil? || type_b.nil? type_a || type_b else compatible_type?(type_a, :gt, type_b) end end
merge_groups(group_l, group_r)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 309 def merge_groups(group_l, group_r) vars_common = group_l[:vars].merge(group_r[:vars]) group_common = make_group(vars_common) group_common[:grouped] = true # TODO: types??? group_common[:lower_type] = max_type(group_l[:lower_type], group_r[:lower_type]) group_common[:upper_type] = min_type(group_l[:upper_type], group_r[:upper_type]) vars_common.keys.each { |var| groups[var] = group_common } end
min_type(type_a, type_b)
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 327 def min_type(type_a, type_b) if type_a.nil? || type_b.nil? type_a || type_b else compatible_type?(type_a, :lt, type_b) end end
replace(rest, l, r, acc = [])
click to toggle source
# File lib/typed/types/polymorphism/unification.rb, line 335 def replace(rest, l, r, acc = []) if rest.empty? acc else a, t, b = rest.first acc << [a == l ? r : a, t, b == l ? r : b] replace(rest.drop(1), l, r, acc) end end