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
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