class Ikra::TypeInference::Visitor

Attributes

classes[R]

Public Class Methods

new() click to toggle source
# File lib/types/inference/ast_inference.rb, line 155
def initialize
    # Ikra type -> ClassDefNode
    @classes = {}
    @classes.default_proc = proc do |hash, key|
        hash[key] = AST::ClassDefNode.new(
            name: key.cls.name,
            ruby_class: key.cls)
    end

    # Top of stack is the method that is currently processed
    @work_stack = []

    # Block/method definitions that must be processed
    @worklist = Set.new
end

Public Instance Methods

all_methods() click to toggle source
# File lib/types/inference/ast_inference.rb, line 171
def all_methods
    return classes.values.map do |class_|
        class_.instance_methods
    end.flatten
end
assert_singleton_type(union_type, expected_type) click to toggle source
# File lib/types/inference/ast_inference.rb, line 370
def assert_singleton_type(union_type, expected_type)
    if union_type.singleton_type != expected_type
        raise AssertionError.new(
            "Expected type #{expected_type} but found #{union_type.singleton_type}")
    end
end
binding() click to toggle source
# File lib/types/inference/ast_inference.rb, line 181
def binding
    current_method_or_block.binding
end
current_method_or_block() click to toggle source
# File lib/types/inference/ast_inference.rb, line 185
def current_method_or_block
    @work_stack.last
end
process_block(block_def_node) click to toggle source

This is used as an entry point for the visitor

# File lib/types/inference/ast_inference.rb, line 190
def process_block(block_def_node)
    Log.info("Type inference: proceed into block(#{Types::UnionType.parameter_hash_to_s(block_def_node.parameters_names_and_types)})")

    @work_stack.push(block_def_node)
    body_ast = block_def_node.body

    # Variables that are not defined inside the block
    predefined_variables = []

    # Add parameters to symbol table (name -> type)
    block_def_node.parameters_names_and_types.each do |name, type|            
        symbol_table.declare_variable(name, type: type)
        predefined_variables.push(name)
    end

    # Add lexical variables to symbol table (name -> type)
    block_def_node.lexical_variables_names_and_types.each do |name, type|
        # Variable might be shadowed by parameter
        symbol_table.ensure_variable_declared(name, type: type, kind: :lexical)
        predefined_variables.push(name)
    end

    begin
        # Infer types
        body_ast.accept(self)
    rescue RestartTypeInferenceError
        # Reset all type information
        symbol_table.clear!
        block_def_node.accept(ClearTypesVisitor.new)

        # Remove block from stack
        @work_stack.pop

        Log.info("Changed AST during type inference. Restarting type inference.")

        # Restart inference
        return process_block(block_def_node)
    end

    # Get local variable definitons
    for variable_name in symbol_table.read_and_written_variables
        if !predefined_variables.include?(variable_name)
            block_def_node.local_variables_names_and_types[variable_name] =
                symbol_table[variable_name]
        end
    end

    return_value_type = symbol_table.return_type 
    Log.info("Type inference: block return type is #{return_value_type.to_s}")

    @work_stack.pop

    return_type = block_def_node.merge_union_type(return_value_type)

    if block_def_node.types_changed?
        # Types changed, do another pass. This is not efficient and there are better
        # ways to do type inference (e.g., constraint solving), but it works for now.
        block_def_node.reset_types_changed
        return process_block(block_def_node)
    else
        return return_type
    end
end
process_method(method_def_node) click to toggle source

This is used as an entry point for the visitor

# File lib/types/inference/ast_inference.rb, line 255
def process_method(method_def_node)
    Log.info("Type inference: proceed into method #{method_def_node.receiver_type}.#{method_def_node.name}(#{Types::UnionType.parameter_hash_to_s(method_def_node.parameters_names_and_types)})")

    @work_stack.push(method_def_node)
    body_ast = method_def_node.body

    # TODO: handle multiple receiver types
    recv_type = method_def_node.receiver_type

    # Variables that are not defined inside the method
    predefined_variables = []

    # Add parameters to symbol table (name -> type)
    method_def_node.parameters_names_and_types.each do |name, type|
        symbol_table.declare_variable(name, type: type)
        predefined_variables.push(name)
    end

    # Add lexical variables to symbol table (name -> type)
    method_def_node.lexical_variables_names_and_types.each do |name, type|
        # Variable might be shadowed by parameter
        symbol_table.ensure_variable_declared(name, type: type, kind: :lexical)
        predefined_variables.push(name)
    end

    # Add return statements
    body_ast.accept(Translator::LastStatementReturnsVisitor.new)

    # Infer types
    body_ast.accept(self)

    # Get local variable definitons
    for variable_name in symbol_table.read_and_written_variables
        if !predefined_variables.include?(variable_name)
            method_def_node.local_variables_names_and_types[variable_name] =
                symbol_table[variable_name]
        end
    end
    
    return_value_type = symbol_table.return_type 
    Log.info("Type inference: method return type is #{return_value_type.to_s}")

    @work_stack.pop

    return_type = method_def_node.merge_union_type(return_value_type)

    if method_def_node.types_changed?
        # Types changed, do another pass. This is not efficient and there are better
        # ways to do type inference (e.g., constraint solving), but it works for now.
        method_def_node.reset_types_changed
        return process_method(method_def_node)
    else
        return return_type
    end
end
symbol_table() click to toggle source
# File lib/types/inference/ast_inference.rb, line 177
def symbol_table
    current_method_or_block.symbol_table
end
visit_begin_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 491
def visit_begin_node(node)
    node.body_stmts[0...-1].each do |stmt|
        stmt.accept(self)
    end

    if node.body_stmts.empty?
        type = Types::UnionType.new
    else
        type = node.body_stmts.last.accept(self)
    end

    node.merge_union_type(type)
end
visit_bool_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 429
def visit_bool_node(node)
    node.merge_union_type(Types::UnionType.create_bool)
end
visit_break_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 462
def visit_break_node(node)
    Types::UnionType.create_void
end
visit_const_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 377
def visit_const_node(node)
    if not binding
        raise AssertionError.new("Unable to resolve constants without Binding")
    end

    constant = binding.eval(node.identifier.to_s)
    node.merge_union_type(constant.ikra_type.to_union_type)
end
visit_float_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 425
def visit_float_node(node)
    node.merge_union_type(Types::UnionType.create_float)
end
visit_for_node(node) click to toggle source
Calls superclass method Ikra::AST::Visitor#visit_for_node
# File lib/types/inference/ast_inference.rb, line 448
def visit_for_node(node)
    assert_singleton_type(node.range_from.accept(self), Types::PrimitiveType::Int)
    assert_singleton_type(node.range_to.accept(self), Types::PrimitiveType::Int)

    changed = symbol_table.ensure_variable_declared(node.iterator_identifier, type: Types::UnionType.create_int)
    symbol_table.written!(node.iterator_identifier)
    
    super(node)
    
    # TODO: Should return range

    node.merge_union_type(Types::UnionType.create_int)
end
visit_hash_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 443
def visit_hash_node(node)
    # Use [Types::ClassType] for the moment
    return Hash.to_ikra_type.to_union_type
end
visit_if_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 466
def visit_if_node(node)
    assert_singleton_type(node.condition.accept(self), Types::PrimitiveType::Bool)
    
    type = Types::UnionType.new
    type.expand(node.true_body_stmts.accept(self))       # Begin always has type of last stmt

    if node.false_body_stmts == nil
        type.expand(Types::UnionType.create_void)
    else
        type.expand(node.false_body_stmts.accept(self))
    end

    node.merge_union_type(type)
end
visit_int_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 417
def visit_int_node(node)
    node.merge_union_type(Types::UnionType.create_int)
end
visit_ivar_read_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 411
def visit_ivar_read_node(node)
    cls_type = node.enclosing_class.ruby_class.to_ikra_type
    cls_type.inst_var_read!(node.identifier)
    cls_type.inst_vars_types[node.identifier]
end
visit_lvar_read_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 390
def visit_lvar_read_node(node)
    symbol_table.read!(node.identifier)

    # Extend type of variable
    return node.merge_union_type(symbol_table[node.identifier])
end
visit_lvar_write_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 397
def visit_lvar_write_node(node)
    type = node.value.accept(self)

    # Declare/extend type in symbol table
    symbol_table.ensure_variable_declared(node.identifier, type: type)
    symbol_table.written!(node.identifier)

    node.variable_type = symbol_table[node.identifier]

    # Extend type of variable
    # Note: Return value of this expression != type of the variable
    node.merge_union_type(type)
end
visit_method_call(send_node, recv_singleton_type) click to toggle source

This is not an actual Visitor method. It is called from visit_send_node.

# File lib/types/inference/ast_inference.rb, line 312
def visit_method_call(send_node, recv_singleton_type)
    selector = send_node.selector

    if recv_singleton_type.is_primitive?
        raise NotImplementedError.new("#{recv_singleton_type}.#{selector} not implemented (#{send_node.to_s})")
    end

    parameter_names = recv_singleton_type.method_parameters(selector)
    arg_types = send_node.arguments.map do |arg| arg.get_type end
    ast = recv_singleton_type.method_ast(selector)
    method_visited_before = nil

    if not @classes[recv_singleton_type].has_instance_method?(selector)
        # This method was never visited before
        method_def_node = AST::MethDefNode.new_with_types(
            name: selector,
            body: ast,
            parameters_names_and_types: Hash[*parameter_names.zip(
                Array.new(arg_types.size) do |arg_index|
                    Types::UnionType.new
                end).flatten],
            ruby_method: nil,
            receiver_type: recv_singleton_type,
            method_binding: recv_singleton_type.method_binding(selector))
        @classes[recv_singleton_type].add_instance_method(method_def_node)
        method_visited_before = false
    else
        method_visited_before = true
    end

    method_def_node = @classes[recv_singleton_type].instance_method(selector)

    parameter_types_expanded = parameter_names.map.with_index do |name, index|
        # returns true if expanded
        method_def_node.parameters_names_and_types[name].expand(arg_types[index])
    end.reduce(:|)

    # Method needs processing if any parameter is expanded (or method was never visited before)
    needs_processing = !method_visited_before or parameter_types_expanded

    # Return value type from the last pass
    # TODO: Have to make a copy here?
    last_return_type = method_def_node.get_type
    
    if needs_processing
        process_method(method_def_node)
    end

    if not last_return_type.include_all?(method_def_node.get_type)
        # Return type was expanded during this pass, reprocess all callers (except for current method)
        @worklist += (method_def_node.callers - [current_method_or_block])
    end

    method_def_node.callers.push(current_method_or_block)

    return method_def_node.get_type
end
visit_nil_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 421
def visit_nil_node(node)
    node.merge_union_type(Types::UnionType.create_nil)
end
visit_return_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 505
def visit_return_node(node)
    type = node.value.accept(self)
    symbol_table.expand_return_type(type)
    node.merge_union_type(type)
end
visit_root_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 386
def visit_root_node(node)
    node.merge_union_type(node.single_child.accept(self))
end
visit_send_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 565
def visit_send_node(node)
    # TODO: handle self sends
    receiver_type = nil

    if node.receiver == nil
        Logger.warn("No receiver given for node #{node.to_s}")
        receiver_type = Types::UnionType.create_int
    else
        receiver_type = node.receiver.accept(self)
    end

    node.arguments.each do |arg|
        arg.accept(self)
    end
    
    visit_send_node_union_type(receiver_type, node)

    return node.get_type
end
visit_send_node_singleton_receiver(sing_type, node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 517
def visit_send_node_singleton_receiver(sing_type, node)
    if RubyIntegration.is_interpreter_only?(sing_type)
        return Types::InterpreterOnlyType.new.to_union_type
    elsif RubyIntegration.has_implementation?(sing_type, node.selector)
        arg_types = node.arguments.map do |arg| arg.get_type end

        begin
            return_type = RubyIntegration.get_return_type(
                sing_type, node.selector, *arg_types, send_node: node)
            return return_type
        rescue RubyIntegration::CycleDetectedError => cycle_error
            # Cannot do further symbolic execution, i.e., kernel fusion here,
            # because we are in a loop.

            # Invoke parallel section: change to `RECV` to `RECV.__call__.to_command`
            node.replace_child(
                node.receiver, 
                AST::SendNode.new(
                    receiver: AST::SendNode.new(
                        receiver: node.receiver, selector: :__call__),
                    selector: :to_command))

            # Start fresh
            raise RestartTypeInferenceError.new
        end
    elsif sing_type.is_a?(Types::StructType)
        # This is a struct type, special type inference rules apply
        return sing_type.get_return_type(node.selector, *node.arguments)
    else
        Log.info("Translate call to ordinary Ruby method #{sing_type}.#{node.selector}")
        return visit_method_call(node, sing_type)
    end
end
visit_send_node_union_type(receiver_type, node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 551
def visit_send_node_union_type(receiver_type, node)
    type = Types::UnionType.new

    for sing_type in receiver_type
        return_type = visit_send_node_singleton_receiver(sing_type, node)
        node.return_type_by_recv_type[sing_type] = return_type
        type.expand(return_type)
    end

    node.merge_union_type(type)

    return type
end
visit_source_code_expr_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 511
def visit_source_code_expr_node(node)
    # This is a synthetic node. No type inference. Return the type that was set
    # manually before (if any).
    return node.get_type
end
visit_string_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 433
def visit_string_node(node)
    # Use [Types::ClassType] for the moment
    return node.value.ikra_type.to_union_type
end
visit_symbol_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 438
def visit_symbol_node(node)
    # Use [Types::ClassType] for the moment
    return node.value.ikra_type.to_union_type
end
visit_ternary_node(node) click to toggle source
# File lib/types/inference/ast_inference.rb, line 481
def visit_ternary_node(node)
    assert_singleton_type(node.condition.accept(self), Types::PrimitiveType::Bool)
    
    type = Types::UnionType.new
    type.expand(node.true_val.accept(self))
    type.expand(node.false_val.accept(self))

    node.merge_union_type(type)
end