The Method Lookup Chain

The previous lesson ended by leaving a question: the Safe class and the mixed-in Lock module both have a method named unlock, and in the call Safe.new.unlock which one runs? The previous three lessons answered the parts of this question separately: a class writes its own definition, a superclass is inherited, a module is mixed in. All of them sit inside the same lookup order.

The author of this lesson is the ancestor author, but this time it does not matter whether the ancestor is a superclass or a module. In M13/K01 we measured the author through the author of the definition; here the question of the author stays the same and the lookup order itself is measured. Whether the definition stands in a superclass or in a module is not separated: the two are a single category, ancestor.

A Prepended Module

include places the module above the class, so the class wins. prepend, on the other hand, places the module in front of the class; a message that reaches the receiver goes first to the module. The file below adds a Lock module to Safe with prepend.

# author.rb — a helper that classifies who wrote a method

# Classification asks in order: is there a definition in the receiver's chain at all,
# then does the receiver's own class carry it, then how was the definition produced.
def author(receiver, name)
  chain = receiver.singleton_class
  unless chain.method_defined?(name) || chain.private_method_defined?(name)
    return ["nobody", "no definition"]
  end

  definition = chain.instance_method(name)
  owner = definition.owner
  place = owner == chain ? "singleton class" : owner.to_s
  return ["ancestor", place] unless owner == receiver.class || owner == chain

  iseq = RubyVM::InstructionSequence.of(definition)
  return ["code", "#{place}, no ruby body"] if iseq.nil?
  return ["code", "#{place}, block body"] if iseq.label.start_with?("block")

  ["programmer", "#{place}, def body"]
end

# prepended.rb — with prepend the module goes in front of the class
require_relative "author"

module Lock
  def unlock = "lock opened, #{super}"
end

class Safe
  prepend Lock

  def unlock = "safe opened"
end

safe = Safe.new
puts safe.unlock
p author(safe, :unlock)
p Safe.ancestors.take(3)
p safe.method(:unlock).owner
p safe.method(:unlock).super_method.owner

lock opened, safe opened
["ancestor", "Lock"]
[Lock, Safe, Object]
Lock
Safe

Safe.new.unlock combined two parts: first the prefix of Lock, then, with super, the class’s own definition of Safe. author gave the ancestor author with Lock as the evidence: the first definition found in the chain is in Lock, because in the Safe.ancestors list Lock stands in front of Safe. method(:unlock).owner came out Lock and super_method.owner Safe. The lookup walks from left to right, the first match runs, and super advances one step in the chain from that point.

CM11. In this lesson “method lookup” means that when a message reaches the receiver, Ruby walks the receiver’s ancestor chain from left to right in the ancestors order and finds the first definition whose name matches. “To prepend” means placing a module in front of a class with prepend; include, in contrast, places the module behind the class.

include and prepend Side by Side

The difference between the two keywords shows when the same module and the same class are set up twice and the chains are compared. The file below adds Lock to one class with include and to the other with prepend; then it tests the order as well by prepending two modules one after the other.

# include_prepend.rb — the place of the two keywords in the chain
module Lock
  def unlock = "lock opened"
end

module Alarm
  def unlock = "alarm, #{super}"
end

class SafeInclude
  include Lock

  def unlock = "safe opened"
end

class SafePrepend
  prepend Lock

  def unlock = "safe opened"
end

class SafeTwice
  prepend Lock
  prepend Alarm

  def unlock = "safe opened"
end

p SafeInclude.ancestors.take(3)
puts SafeInclude.new.unlock
p SafePrepend.ancestors.take(3)
puts SafePrepend.new.unlock
p SafeTwice.ancestors.take(4)
puts SafeTwice.new.unlock

[SafeInclude, Lock, Object]
safe opened
[Lock, SafePrepend, Object]
lock opened
[Alarm, Lock, SafeTwice, Object]
alarm, lock opened

With include, the class came first in the chain of SafeInclude and Lock fell behind it; the call to unlock stopped at the class’s own definition and never reached the definition of the module. With prepend, in the chain of SafePrepend Lock went in front of the class, but because Lock#unlock did not call super, this time the definition of the class did not run. So a prepended module shadows the class completely if it does not write super. In the chain of SafeTwice the second prepend went in front of the first: the one added later stands closest to the receiver, just as in the order of include. The rule is the same in all three classes; only whether the link enters in front of or behind the class changes.

To walk the chain to its end, super_method can also be used in a loop. The file below stacks a singleton method, a prepended module and a class on top of one another and collects the owner of each link in order. Because the name of the singleton class carries a memory address, the owner is written to the output not by its name but with the label :singleton.

# walk_chain.rb — counting the links with super_method
module Lock
  def unlock = "lock opened, #{super}"
end

class Safe
  prepend Lock

  def unlock = "safe opened"
end

k = Safe.new
def k.unlock = "singleton, #{super}"

owners = []
current = k.method(:unlock)
while current
  owner = current.owner
  owners << (owner == k.singleton_class ? :singleton : owner)
  current = current.super_method
end

p owners
puts k.unlock
p Safe.new.method(:unlock).super_method.super_method

[:singleton, Lock, Safe]
singleton, lock opened, safe opened
nil

The loop found three links: the singleton class, Lock and Safe; this order coincides exactly with the reading of ancestors. puts k.unlock combined the part of each link in the same order. In a Safe object without a singleton method the chain is two links, and super_method.super_method gives nil: after Safe there is no other link in the chain that defines unlock.

The End of the Chain

The chain is not endless. The chain of every class that descends from Object ends with Object, Kernel and BasicObject. The file below reads the chain of the Account class to its end and asks about a private method at the last stop.

# chain_end.rb — the chain ends with BasicObject
class Account
end

p Account.ancestors
p Account.ancestors.last
p Account.ancestors.size
p BasicObject.private_method_defined?(:method_missing)
p Kernel.private_method_defined?(:puts)

[Account, Object, Kernel, BasicObject]
BasicObject
4
true
true

The chain of an empty Account class is the array [Account, Object, Kernel, BasicObject], and ancestors.size gave four; with a mixed-in module it would be five. BasicObject is the last stop of the chain. method_missing is defined there as private: if the name is not found in the chain, this method is called as a last resort, and its default behavior is to raise NoMethodError. puts, on the other hand, stands in Kernel as private; that is why it can be called without a receiver from inside any object, but "x".puts cannot be written.

What happens when the end of the chain is reached and the name is not found depends on the private method_missing definition of BasicObject. If a class redefines this method in its own body, the unmatched message falls to it. The file below compares the answer two classes give to the same unmatched call.

# last_resort.rb — a name not found in the chain falls to method_missing
class Account
end

class Account2
  def method_missing(name, *) = "missing: #{name}"
  def respond_to_missing?(name, include_private = false) = false
end

begin
  Account.new.other_name
rescue NoMethodError => e
  puts e.class
end

puts Account2.new.other_name
p Account2.new.respond_to?(:other_name)
p Account2.instance_method(:method_missing).owner
p Account.instance_method(:method_missing).owner

NoMethodError
missing: other_name
false
Account2
BasicObject

For Account the name was not found along the chain, BasicObject#method_missing received the message and raised NoMethodError. Because Account2 wrote its own method_missing, the message did not go down to the end of the chain and fell to the class’s own definition. respond_to? gave false; an object responding in this way does not mean that it has defined a method. The owner comparison pointed at the class itself for Account2 and at BasicObject for Account. So the end of the chain is a default behavior, and a class can change it at any link of the chain.

CM16. In this lesson “the end of the chain” means the method_missing call that receives the message when the name is not found in the receiver’s chain. Its default definition is in BasicObject and it raises NoMethodError; a closer link in the chain can redefine it.

The Chain of Class Methods

The new in the call Account.new is a method, and its receiver is the Account class itself. A class too has a chain. This chain is built over the singleton class particular to the class.

# class_chain.rb — the class's own chain
class Account
end

p Account.method(:new).owner
p Account.singleton_class
p Account.singleton_class.ancestors.take(4)

Class
#<Class:Account>
[#<Class:Account>, #<Class:Object>, #<Class:BasicObject>, Class]

For Account.new the owner of the method new came out Class: class methods are found by the same lookup rule, only the receiver is a class and the chain starts from its singleton class. The singleton class of a class is printed under the name #<Class:Account>. The chain walks from this singleton class to the singleton class of Object, to the singleton class of BasicObject and finally to Class. So a class method defined in a superclass is found when called from a subclass as well.

Why the chain connects to Class after the singleton classes, and how a subclass finds the class method of its superclass, are two separate questions. The file below measures both; the comparisons are made not with the name in the output but with the question of equality, so that the result rests on the objects themselves and not on the spelling of a name.

# class_chain_more.rb — a class method is found from the subclass
class Account
  def self.default_account = new("-", 0)

  def initialize(owner, balance)
    @owner = owner
    @balance = balance
  end
end

class TermDeposit < Account
end

p TermDeposit.default_account.class
p TermDeposit.method(:default_account).owner == Account.singleton_class
p TermDeposit.singleton_class.superclass == Account.singleton_class
p TermDeposit.singleton_methods
p TermDeposit.singleton_methods(false)
p BasicObject.singleton_class.superclass
p Account.singleton_class.ancestors.drop(3)

TermDeposit
true
true
[:default_account]
[]
Class
[Class, Module, Object, Kernel, BasicObject]

TermDeposit.default_account produced a TermDeposit object: although the method is written in the singleton class of Account, the receiver is TermDeposit, so new was applied to it. The owner comparison showed that the definition stands in the singleton class of Account, and the superclass comparison showed that the singleton class of TermDeposit is tied to the singleton class of Account. singleton_methods counted the class method coming from the superclass as well, whereas singleton_methods(false) stayed empty. The reason the chain passes to Class after the singleton classes can be read from here too: the superclass of the singleton class of BasicObject is Class, and from that point on the chain merges into the ordinary class chain with Module, Object, Kernel and BasicObject.

The Bounding Measurement

Until now the chains were built from classes and modules. The chain of an object can also carry a link particular to that object: the singleton class. The file below adds a singleton method to a single Safe object and extends a module.

# singleton.rb — a link particular to a single object
require_relative "author"

module Extra
  def unlock = "extra, #{super}"
end

module Lock
  def unlock = "lock opened, #{super}"
end

class Safe
  prepend Lock

  def unlock = "safe opened"
end

k = Safe.new
def k.unlock = "singleton, #{super}"

puts k.unlock
puts Safe.new.unlock
p author(k, :unlock)
p k.singleton_methods

j = Safe.new
j.extend(Extra)
p j.singleton_class.ancestors.drop(1).take(4)
puts j.unlock

singleton, lock opened, safe opened
lock opened, safe opened
["programmer", "singleton class, def body"]
[:unlock]
[Extra, Lock, Safe, Object]
extra, lock opened, safe opened

def k.unlock added a singleton method to a single object. k.unlock gave its own prefix first, then the rest of the chain; a newly produced Safe was not affected. The author came out as the programmer, with singleton class, def body as the evidence: in the language of the rule the owner of the definition is the singleton class of the object. k.singleton_methods gave only [:unlock]. j.extend(Extra), in turn, mixed the Extra module into the singleton class of the object j, and the list j.singleton_class.ancestors.drop(1) began with Extra and continued with Lock, Safe, Object. The name of the singleton class at the head of the chain was not written to the output, because that name carries a memory address.

CM12. In this lesson the “singleton class” is the hidden class particular to a single object or to a class, added at the very head of the ancestor chain. A “singleton method” is a method defined in that class. Other objects do not share this chain.

Asking Who Provided the Method

A distinction often made when reading the chain is between method and instance_method. The first asks the object, the second asks the class; that is why only the first sees a singleton method. The file below puts the two and a method coming from Kernel side by side.

# who_gave.rb — the difference between method and instance_method
module Lock
  def unlock = "lock opened"
end

class Safe
  prepend Lock

  def unlock = "safe opened"
end

k = Safe.new
def k.unlock = "singleton opened"

p k.method(:unlock).owner == k.singleton_class
p Safe.instance_method(:unlock).owner
p Safe.new.method(:unlock).owner
p k.method(:puts).owner
p k.method(:class).owner
p Safe.instance_method(:unlock).super_method.owner

true
Lock
Lock
Kernel
Kernel
Safe

Because method asks the object, the first line showed that the singleton class claimed ownership. instance_method looked only at the chain of the class; since the singleton method is not in that chain, the answer was Lock, that is, because the prepended module stands in front of the class, it appeared as the owner. On a Safe.new object without a singleton method, method gave the same answer. For puts and class the owner came out Kernel: the author of these two methods is neither the programmer nor the class; it is the Kernel module mixed into the Object chain. The last line asks about the link one below Lock#unlock and finds Safe#unlock; even a prepend of a single link can be read as a two-link chain with super_method.

All of these questions come down to the same habit: which definition a method runs with is decided not by where the definition is written in the text but by which link comes first in the receiver’s chain. The owner question gives the name of that link.

Three Rules for Reading the Lookup

Three rules for the lookup come out of the measurements above. The first: the order comes from the receiver’s chain; what counts is not the class in which the method is written but the chain the receiver has. The second: the lookup takes the first match in the chain, and the other definitions run only if they are called again with super. The third: super does not return to the head of the chain; it advances one step to the right from the link it is in. The super inside Lock#unlock therefore descends not to Lock but to Safe.

These rules also say that include, prepend and a singleton method are three views of a single mechanism. All three add a link to the chain; the difference is where the link enters. include puts the link behind the class, prepend in front of it, and the singleton class at the very head of the object’s own chain. To understand which link wins, no guessing is needed: reading the ancestors array from left to right is enough. The singleton class does not appear in that list, but if asked with singleton_class.ancestors it stands at the head of the chain.

A readable chain is useful in debugging as well. When a method gives an unexpected result, the first question is which definition ran. The answer is the line method(:name).owner. The second question is whether there is another definition behind that one; the answer is taken by asking one link further with super_method, and repeating until nil returns. super_method gives the next definition in the chain; whether a definition calls super is shown by the body of the method. With these two methods the chain is not guessed, it is read.

Summary

• Method lookup walks the receiver’s ancestors chain from left to right and runs the first definition whose name matches.
• prepend puts the module in front of the class; Safe.new.unlock runs Lock first and then, with super, Safe.
• method(:unlock).owner gives the owner of the first definition, super_method.owner the next one in the chain.
• The chain of a class that descends from Object ends with BasicObject; method_missing stands there, and puts stands in Kernel, both as private.
• Class methods come from the singleton class chain of the class: for Account.new the owner of the method new is Class.
• The author of this lesson is the ancestor; a singleton method added to a single object enters the head of the chain and makes the author the programmer.

Next Step

In a Struct class named Point the method x was never written with def, yet point.x works and author gives its author as code. Is it possible to ask an object about its methods at run time, and to have the object tell who wrote x? The next lesson, Reflection, measures asking the object these questions.