module RubyBreaker::Typing

This module contains subtyping logic used in RubyBreaker. See rubytype.rb for logic related to subclassing which is directly related to pure Ruby types.

Public Class Methods

subtype_rel?(lhs, rhs) click to toggle source

This method determines if one type is a subtype of another. This check is for RubyBreaker defined types. See TypeDefs module for more detail.

lhs

The allegedly “subtype”

rhs

The allegedly “supertype”

# File lib/rubybreaker/typing/subtyping.rb, line 441
def self.subtype_rel?(lhs, rhs)

  # Don't even bother if they are same object or syntactically
  # equivalent. NOTE: would this really help improve performance???
  return true if (lhs.equal?(rhs) || lhs.eql?(rhs))

  # Break down the cases by what LHS is.
  is_subtype = false
  if lhs.instance_of?(NilType)
    is_subtype = rhs.instance_of?(NilType)
  elsif lhs.instance_of?(AnyType)
    is_subtype = true 
  elsif lhs.instance_of?(SelfType)
    is_subtype = self.self_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(NominalType)
    is_subtype = self.nominal_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(FusionType)
    is_subtype = self.fusion_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(DuckType)
    is_subtype = self.duck_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(MethodType)
    is_subtype = self.method_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(OrType)
    is_subtype = self.or_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(BlockType)
    is_subtype = self.proc_subtype_rel?(lhs,rhs)
  elsif lhs.instance_of?(MethodListType)
    is_subtype = self.method_subtype_rel?(lhs,rhs)
  end
  return is_subtype
end

Private Class Methods

duck_has_methods?(duck, meths) click to toggle source

This method checks if the duck type has all the methods specified in meths array

# File lib/rubybreaker/typing/subtyping.rb, line 81
def self.duck_has_methods?(duck, meths)
  has_all = true
  meths.each do |m|
    if !duck.meth_names.include?(m)
      has_all = false
      break
    end 
  end
  return has_all
end
duck_subtype_rel?(lhs,rhs) click to toggle source

This method checks if a duck type (LHS) is a subtype of the other type. There are a few cases to consider:

If RHS is a nominal type, every method in RHS must exist in LHS.
This is because the subtype has the same number of or more methods
than supertype.

If RHS is a duck type OR a fusion type, every method in RHS must
exist in LHS.

If RHS is an "or" type, LHS must be a subtype of one of RHS'es inner
types.

All other cases would not satisfy this subtyping relationship.
# File lib/rubybreaker/typing/subtyping.rb, line 107
def self.duck_subtype_rel?(lhs,rhs)
  return false unless lhs.kind_of?(DuckType)
  if rhs.instance_of?(NominalType) # Don't include self type
    # Ok, this is unlikely but we still do a check
    is_subtype = self.duck_has_methods?(lhs, rhs.mod.instance_methods)
  elsif rhs.kind_of?(DuckType) # duck type and fusion type
    is_subtype = self.duck_has_methods?(lhs, rhs.meth_names)
  elsif rhs.instance_of?(OrType) 
    is_subtype = false
    rhs.types.each {|rhs_inner_t|
      # Only one has to be in subtype relation
      if self.duck_subtype_rel?(lhs,rhs_inner_t)
        is_subtype = true
        break
      end
    }
  else
    is_subtype = false
  end
  return is_subtype
end
fusion_subtype_rel?(lhs,rhs) click to toggle source

This method determines if the fusion type (LHS) is a subtype of the other type (RHS). There are many cases to consider:

If LHS is Broken, there are several cases to consider:

  If RHS is a nominal type, there are a few cases to consider:

    If LHS is a subclass of RHS, then there is a subtype relation

    If RHS is Broken, each method in RHS must be a supertype of the
      counterpart in LHS.

    Otherwise, each in LHS must exist in RHS.

  If RHS is a fusion type, ther eare a few cases to consider:

    If LHS is a subclass of RHS, then LHS is a subtype

    If RHS is Broken, each method in RHS must be a supertype of the
      counterpart in LHS.

    Otherwise, every method in RHS must exist in LHS.

  If RHS is a duck type, then every method in RHS must exist in LHS.

  Otherwise, there is no subtype relation.

If LHS is not Broken, subtyping satifies only when LHS has all
methods in RHS
# File lib/rubybreaker/typing/subtyping.rb, line 302
def self.fusion_subtype_rel?(lhs,rhs)
  return false unless lhs.kind_of?(FusionType)
  if self.has_type_map?(lhs.mod)
    if rhs.instance_of?(NominalType) # don't include self type
      if RubyTypeUtils.subclass_rel?(lhs.mod, rhs.mod)
        is_subtype = true
      elsif self.has_type_map?(rhs.mod)
        # then do a type check for each method
        lhs_meths = Inspect.inspect_all(lhs.mod)
        rhs_meths = Inspect.inspect_all(rhs.mod)
        is_subtype = self.methods_subtype_rel?(lhs_meths,rhs_meths)
      else 
        # if not, the only possible way is if lhs has all the rhs' methods
        is_subtype = self.duck_has_methods?(lhs, rhs.mod.instance_methods)
      end
    elsif rhs.instance_of?(FusionType)
      if RubyTypeUtils.subclass_rel?(lhs.mod, rhs.mod)
        is_subtype = true
      elsif self.has_type_map?(rhs.mod)
        # then do a type check for each method
        lhs_meths = Inspect.inspect_all(lhs.mod)
        rhs_meths = Inspect.inspect_meths(rhs.mod, lhs.meths.keys)
        is_subtype = self.methods_subtype_rel?(lhs_meths,rhs_meths)
      else
        is_subtype = self.duck_has_methods?(lhs, rhs.meth_names)
      end            
    elsif rhs.instance_of?(DuckType)
      is_subtype = self.duck_has_methods?(lhs, rhs.meth_names)
    else
      is_subtype = false
    end
  else
    # lhs is not broken, so only thing we can do is method check
    is_subtype = self.duck_subtype_rel?(lhs, rhs)
  end 
  return is_subtype
end
has_type_map?(mod) click to toggle source

This method determins if the module/class has its corresponding

# File lib/rubybreaker/typing/subtyping.rb, line 61
def self.has_type_map?(mod)
  return Runtime::TYPE_MAP[mod] != nil
end
method_subtype_rel?(lhs,rhs) click to toggle source

This method checks the subtype relation between two method types. There are several cases to consider:

Case 1: If RHS is a MethodListType, we give up. It is actually
        difficult to figure out the subtype relation in this case.
Case 2: If LHS is a MethodListType, only one of them has to be in 
        subtype relation to RHS.
Case 3: If both are Methods, then do a typical method subtype
        comparison.

Note: See methodtypelist_subtype_rel? if LHS is a MethodListType.

# File lib/rubybreaker/typing/subtyping.rb, line 218
def self.method_subtype_rel?(lhs,rhs)
  is_subtype = true
  # First check if LHS and RHS are either a method type or a method list
  # type. Otherwise, return false.
  if (!lhs.instance_of?(MethodType) && !lhs.instance_of?(MethodListType)) ||
     (!rhs.instance_of?(MethodType) && !rhs.instance_of?(MethodListType))
    is_subtype = false
  elsif lhs.instance_of?(MethodListType)
    # Every method type in LHS must be a subtype of RHS
    is_subtype = true
    lhs.types.each {|type|
      if !self.method_subtype_rel?(type,rhs)
        is_subtype = false
        break
      end
    }
  elsif rhs.instance_of?(MethodListType)
    # One of the RHS has to be a supertype
    is_subtype = false
    rhs.types.each {|type|
      if self.method_subtype_rel?(lhs,type)
        is_subtype = true
        break
      end
    }
  else # ok, both are MethodType
    # Remember the contra-variance in arguments, co-variance in return
    if lhs.meth_name != rhs.meth_name 
      is_subtype = false
    else
      # re-use block subtype relation check
      is_subtype = self.proc_subtype_rel?(lhs, rhs)
    end
  end
  return is_subtype
end
methods_subtype_rel?(sub_meth_types, super_meth_types) click to toggle source

This method checks if each method in the subtype is indeed a subtype of the counterpart in the supertype.

# File lib/rubybreaker/typing/subtyping.rb, line 257
def self.methods_subtype_rel?(sub_meth_types, super_meth_types)
  # wider means, a fewer number of methods
  return false unless sub_meth_types.size <= super_meth_types 
  is_subtype = true
  sub_meth_types.each_pair { |meth_name, sub_meth_type|
    super_meth_type = super_meth_types[meth_name]
    if super_meth_type == nil || 
       !method_subtype_rel?(sub_meth_type, super_meth_type)
      is_subtype = false
      break
    end
  }      
  return is_subtype
end
module_has_methods?(mod, meths) click to toggle source

Thie method checks if the module has all the methods specified in meths array

# File lib/rubybreaker/typing/subtyping.rb, line 67
def self.module_has_methods?(mod, meths)
  has_all = true
  mod_meths = mod.instance_methods
  meths.each do |m|
    if !mod_meths.include?(m)
      has_all = false
      break
    end
  end
  return has_all
end
nominal_subtype_rel?(lhs,rhs) click to toggle source

This method checks the subtype relation when LHS is a nominal type. There are several cases to consider:

my_class <: your_class  is true only if MyClass and YourClass have
                        (Ruby) subclass relationship.

my_class <: a[foo]      is true if

  (1) MyClass is a subtype of A or
  (2) Both MyClass and A are Broken and every method in MyClass is a
      subtype of the counterpart method in A. (This should be rare).
      Or,
  (3) A are not Broken and MyClass has all methods of A.
# File lib/rubybreaker/typing/subtyping.rb, line 373
def self.nominal_subtype_rel?(lhs,rhs)
  return false unless lhs.kind_of?(NominalType) # Self type is a nominal type
  if rhs.instance_of?(SelfType)
    is_subtype = lhs.instance_of?(SelfType)
  elsif rhs.instance_of?(NominalType) # don't include self type
    is_subtype = RubyTypeUtils.subclass_rel?(lhs.mod, rhs.mod)
  elsif rhs.instance_of?(FusionType)
    # If RHS is a superclass or included module then true
    # If both LHS and RHS are Broken, do a subtype check on each method
    # If only RHS is broken, look at each method's type
    # If RHS is not broken, sorry no subtype relationship
    if RubyTypeUtils.subclass_rel?(lhs.mod, rhs.mod)
      is_subtype = true
    elsif self.has_type_map?(lhs.mod) && self.has_type_map?(rhs.mod)
      is_subtype = true
      lhs_methods = lhs.mod.instance_methods
      rhs.meth_names.each {|m| 
        lhs_m = Inspector.inspect_meth(lhs, m)
        rhs_m = Inspector.inspect_meth(rhs, m)
        if !meth_subtype_rel?(lhs_m, rhs_m)
          is_subtype = false
          break
        end
      }
    else
      is_subtype = self.module_has_methods?(lhs.mod, rhs.meth_names)
    end 
  elsif rhs.instance_of?(DuckType)
    # Do simple method existence check since there is no nominal type to
    # inspect.
    is_subtype = self.module_has_methods?(lhs.mod, rhs.meth_names)
  else
    # No other possibility of subtype relation
    is_subtype = false
  end 
  return is_subtype
end
or_subtype_rel?(lhs,rhs) click to toggle source

If OrType is on the LHS, the only possible subtype relation is if each child type in OrType is a subtype of RHS. For example,

numeric or string <: object

is true only if numeric is subype of object and string is subtype of object.

# File lib/rubybreaker/typing/subtyping.rb, line 419
def self.or_subtype_rel?(lhs,rhs)
  return false if !lhs.kind_of?(OrType)
  is_subtype = true
  # Each type in LHS has to be a subtype of RHS
  lhs.types.each do |t|
    if !self.subtype_rel?(t,rhs)
      is_subtype = false
      break
    end
  end
  return is_subtype
end
proc_subtype_rel?(lhs, rhs) click to toggle source

Procedure subtype relation check is for both methods and blocks. A typical “method” subtype is satified if

- Each argument in RHS is a subtype of its counterpart in LHS. This
  includes the block argument. It's called contra-variance.
- The return in LHS is a subtype of its counterpart in RHS. It's
  called co-variance.

Here is the explanation to why we do this:

Assume m1 <: m2 (i.e, m1 is a subtype of m2)

Then, any place where m2 is used, m1 should be able to replace m2.
In other words, m1's arguments should accept more types than m2's
arguments. On the other hand, m1's return should be more restrictive
than m2's return to make sure it would work after the call. There it
is, you just received a mini type systems class without paying
thousands of dollars.

This method also takes care of optional argument and variable length argument. This method is the ONLY one that should handle those types.

# File lib/rubybreaker/typing/subtyping.rb, line 151
def self.proc_subtype_rel?(lhs, rhs)

  # use kind_of? because method_subtype_rel? calls this method
  return false unless lhs.kind_of?(BlockType) & rhs.kind_of?(BlockType)

  is_subtype = true

  if lhs.arg_types.length != rhs.arg_types.length
    is_subtype = false
  # elsif !self.subtype_rel?(rhs.blk_type, lhs.blk_type)
  #   is_subtype = false
  elsif !self.subtype_rel?(lhs.ret_type, rhs.ret_type)
    is_subtype = false
  else

    # Subtyping with optional type and variable length type works as
    # follows:
    #
    # (x?) <: (x) since optional argument can replace original
    #             argument
    #
    # (x*) <: (x) for the same reason
    #
    # (x*) <: (x?) since LHS can have more arguments
    #

    is_subtype = true
    # check arguments
    rhs.arg_types.each_with_index {|rhs_arg,i|
      lhs_arg = lhs.arg_types[i]
      if lhs_arg.kind_of?(OptionalType) 
        lhs_arg = lhs_arg.type
        if rhs_arg.kind_of?(OptionalType)
          rhs_arg = rhs_arg.type
        elsif rhs_arg.kind_of?(VarLengthType)
          is_subtype = false
          break
        end
      elsif lhs_arg.kind_of?(VarLengthType)
        lhs_arg = lhs_arg.type
        if rhs_arg.kind_of?(OptionalType) ||
           rhs_arg.kind_of?(VarLengthType) 
          rhs_arg = rhs_arg.type
        end
      end
      # Remember, the contra-variance
      if !self.subtype_rel?(rhs_arg, lhs_arg)
        is_subtype = false
        break
      end
    }
  end
  return is_subtype
end
self_subtype_rel?(lhs,rhs) click to toggle source

Self type works exactly like nominal type except that, if RHS is a self type, then only self type is allowed in LHS.

For example, consider you are inside Fixnum

self <: Fixnum
self <: Numeric
self <: Object
self <: self

but,

Fixnum !<: self
# File lib/rubybreaker/typing/subtyping.rb, line 354
def self.self_subtype_rel?(lhs,rhs)
  self.nominal_subtype_rel?(lhs,rhs)
end