Script to explore in which situations tail call elimination can occur in Ruby

tail_positions.rb

require "tco_method"

# Wrap method definitons in a lambda to facilitate recompiling with tail call
# optimization enabled.
tail_calls = lambda do |this|
  def start_tail_call_chain
    implicit_tail_call
  end

  def implicit_tail_call
    explicit_tail_call
  end

  def explicit_tail_call
    return mid_method_explicit_return
  end

  def mid_method_explicit_return
    i = 0
    return and_right_hand_side if true
    i
  end

  def and_right_hand_side
    true && or_right_hand_side
  end

  def or_right_hand_side
    false || if_then_clause_with_hack
  end

  def if_then_clause_with_hack
    if true
      return if_else_clause
    else
      raise "fail"
    end
    :hack
  end

  def if_else_clause
    if false
      raise "fail"
    else
      if_then_clause_without_else_with_hack
    end
  end

  def if_then_clause_without_else_with_hack
    if true
      return if_then_clause_inline_with_hack
    end
    :hack
  end

  def if_then_clause_inline_with_hack
    return ternary_then_clause_with_hack if true
    :hack
  end

  def ternary_then_clause_with_hack
    true ? (return ternary_else_clause) : raise("fail")
    :hack
  end

  def ternary_else_clause
    false ? raise("fail") : while_body_explicit
  end

  def while_body_explicit
    while true
      return tail_call_with_expression_in_arguments
    end
  end

  def tail_call_with_expression_in_arguments
    i = 0
    recursive_tail_call(false ? true : false)
  end

  def recursive_tail_call(is_recursive = false)
    return begin_body_with_rescue if is_recursive
    recursive_tail_call(true)
  end

  def begin_body_with_rescue
    begin
      return begin_rescue_clause
    rescue => e
      raise e.message
    end
  end

  def begin_rescue_clause
    begin
      raise "boom"
    rescue
      return begin_rescue_else_clause_implicit
    end
  end

  def begin_rescue_else_clause_implicit
    begin
      i = 0
    rescue
      raise "boom"
    else
      begin_rescue_else_clause_explicit
    end
  end

  def begin_rescue_else_clause_explicit
    begin
      i = 0
    rescue
      raise "boom"
    else
      return begin_rescue_ensure_clause
    end
  end

  def begin_rescue_ensure_clause
    begin
      raise "boom"
    rescue
    ensure
      return begin_rescue_else_ensure_else_clause
    end
  end

  def begin_rescue_else_ensure_else_clause
    begin
      i = 0
    rescue
      raise "boom"
    else
      return begin_rescue_else_ensure_ensure_clause
    ensure
      i = 1
    end
  end

  def begin_rescue_else_ensure_ensure_clause
    begin
      i = 0
    rescue
      raise "boom"
    else
      i += 1
    ensure
      return define_method_with_proc
    end
  end

  # Define proc in method to ensure its backtrace signiture is consistent.
  def define_method_proc
    proc { define_method_with_lambda }
  end

  # Define lambda in method to ensure its backtrace signiture is consistent.
  def define_method_lambda
    lambda { backtrace }
  end

  define_method(:define_method_with_proc, &define_method_proc)
  define_method(:define_method_with_lambda, &define_method_lambda)

  def backtrace
    caller
  end
end

instance_eval(&tail_calls)

initial_backtrace = start_tail_call_chain
# Initial call cannot be optimized, so pop it off now
initial_start_tail_call_chain_call = initial_backtrace.pop

file, line = tail_calls.source_location
path = File.dirname(file)
tail_calls = TCOMethod.tco_eval(tail_calls.source, file, path, line)

instance_eval(&tail_calls)
optimized_backtrace = start_tail_call_chain

hacked_methods = self.methods.select { |method| /_with_hack/ === method }
hacked_method_matchers = hacked_methods.map { |hacked_method| /#{hacked_method}/ }
hacked_call_sites = initial_backtrace.select do |call_site|
  hacked_method_matchers.any? { |matcher| matcher === call_site }
end

puts "The following call sites could be tail call optimized:"
puts "  #{(initial_backtrace - optimized_backtrace).join("\n  ")}"

puts "\nThe following call sites could be tail call optimized, but required a"
puts "minor hack to ensure the tail call could be optimized:"
puts "  #{hacked_call_sites.join("\n  ")}"

unoptimized = [initial_start_tail_call_chain_call].concat(optimized_backtrace)
puts "\nThe following call sites could not be tail call optimized:"
puts "  #{unoptimized.join("\n  ")}"

# The following call sites could be tail call optimized:
#   tail_positions.rb:160:in `block in define_method_lambda'
#   tail_positions.rb:125:in `begin_rescue_ensure_clause'
#   tail_positions.rb:116:in `begin_rescue_else_clause_explicit'
#   tail_positions.rb:80:in `recursive_tail_call'
#   tail_positions.rb:81:in `recursive_tail_call'
#   tail_positions.rb:76:in `tail_call_with_expression_in_arguments'
#   tail_positions.rb:70:in `while_body_explicit'
#   tail_positions.rb:65:in `ternary_else_clause'
#   tail_positions.rb:60:in `ternary_then_clause_with_hack'
#   tail_positions.rb:55:in `if_then_clause_inline_with_hack'
#   tail_positions.rb:49:in `if_then_clause_without_else_with_hack'
#   tail_positions.rb:43:in `if_else_clause'
#   tail_positions.rb:32:in `if_then_clause_with_hack'
#   tail_positions.rb:27:in `or_right_hand_side'
#   tail_positions.rb:23:in `and_right_hand_side'
#   tail_positions.rb:18:in `mid_method_explicit_return'
#   tail_positions.rb:13:in `explicit_tail_call'
#   tail_positions.rb:9:in `implicit_tail_call'
#   tail_positions.rb:5:in `start_tail_call_chain'
#
# The following call sites could be tail call optimized, but required a
# minor hack to ensure the tail call could be optimized:
#   tail_positions.rb:60:in `ternary_then_clause_with_hack'
#   tail_positions.rb:55:in `if_then_clause_inline_with_hack'
#   tail_positions.rb:49:in `if_then_clause_without_else_with_hack'
#   tail_positions.rb:32:in `if_then_clause_with_hack'
#
# The following call sites could not be tail call optimized:
#   tail_positions.rb:173:in `<main>'
#   tail_positions.rb:155:in `block in define_method_proc'
#   tail_positions.rb:149:in `begin_rescue_else_ensure_ensure_clause'
#   tail_positions.rb:135:in `begin_rescue_else_ensure_else_clause'
#   tail_positions.rb:106:in `begin_rescue_else_clause_implicit'
#   tail_positions.rb:96:in `rescue in begin_rescue_clause'
#   tail_positions.rb:93:in `begin_rescue_clause'
#   tail_positions.rb:86:in `begin_body_with_rescue'
#   tail_positions.rb:182:in `<main>'