Method lookup for modules included in modules

Discussion in 'Ruby' started by Mark Wilden, May 15, 2008.

  1. Mark Wilden

    Mark Wilden Guest

    My question has to do with the diagram on page 12 of "Advanced Rails".
    It arises from the following structure:

    module A; end;
    module B; include A; end
    module C; include A; end
    class D; include B; include C; end

    (This would be a diamond-shaped hierarchy if inheritance were used.)
    Now picture a similar structure, except without a common ancestor:

    module A1; end;
    module A2; end;
    module B; include A1; end
    module C; include A2; end
    class D; include C; include B; end

    d = D.new

    When a message is sent to d, that method is searched for in the
    following order: B, A1, C, A2. My question is how this is implemented
    in terms of 'klass' and 'super' as described in the book.

    First, the klass pointer from d takes us to D, whose m_tbl is
    searched. Then D's super pointer takes us to the proxy for the B
    module. That proxy's m_tbl pointer points to the B methods which are
    searched. Then B's super pointer takes us to B's proxy for the A1
    module, which causes A1's methods to be search.

    Here's my problem. If A1 doesn't contain the method, what causes the
    search to backtrack to the B proxy and follow its super pointer to the
    C proxy? This "backtracking" seems counter to the purported "linear"
    lookup order. (This is just a conceptual problem for me - it's obvious
    what the lookup order is, and it's easy to verify.)

    The best I can come up with is that the process is this:

    1. Look for the method in D
    2. If not found, follow the super and look for the method in the B proxy
    3. If not found, follow the super and look for the method in the C proxy
    4. If not found, follow the super and look for the method in the A2
    proxy
    5. If not found, give up

    However, "look for the method in the B proxy" expands to

    2a. Look for the method in B
    2b. If not found, follow the super and look for the method in the A1
    proxy
    2c. If not found, give up (which takes us back to #3 above

    That sounds right. :)

    But then I'm confused by the use of the klass pointers in the diagram.
    They seem to imply that when the lookup follows the super from D to
    the B proxy, that B is a non-class object and hence its klass pointer
    is used to find its methods. That would imply that the B proxy is an
    object of the B class, which doesn't sound right. Is the klass pointer
    actually used to find the B proxy's methods? Or is it just the case
    that the B proxy class object and the B class object contain the same
    m_tbl pointer? If so, what (if anything) is the klass pointer between
    the proxy and the class object used for?

    I think the best answers to this question will come from people who
    have the "Advanced Rails" book to hand. I've searched pretty far and
    wide and simply haven't found an explanation of how method lookup
    passes from an included module to a module that's included in that one.

    I'm probably making a conceptual mountain of a molehill, but any
    clarification (other than "read the code!") would be appreciated.

    ///ark
    Mark Wilden, May 15, 2008
    #1
    1. Advertising

  2. Mark Wilden

    7stud -- Guest

    Mark Wilden wrote:
    > My question has to do with the diagram on page 12 of "Advanced Rails".


    Then why wouldn't you post your question in a Rails forum??!
    --
    Posted via http://www.ruby-forum.com/.
    7stud --, May 15, 2008
    #2
    1. Advertising

  3. Mark Wilden

    ara.t.howard Guest

    On May 14, 2008, at 8:29 PM, Mark Wilden wrote:

    >
    > Here's my problem. If A1 doesn't contain the method, what causes the
    > search to backtrack to the B proxy and follow its super pointer to
    > the C proxy? This "backtracking" seems counter to the purported
    > "linear" lookup order. (This is just a conceptual problem for me -
    > it's obvious what the lookup order is, and it's easy to verify.)


    as each module in included in the target, it's entire lookup chain is
    added to that target - therefore no 'backtracking' is required, we
    just end up with a long line that, when followed, happens to give the
    appearance if backtracking.

    a @ http://codeforpeople.com/
    --
    we can deny everything, except that we have the possibility of being
    better. simply reflect on that.
    h.h. the 14th dalai lama
    ara.t.howard, May 15, 2008
    #3
  4. On Thu, May 15, 2008 at 12:10 AM, 7stud -- <> wrote:
    > Mark Wilden wrote:
    >> My question has to do with the diagram on page 12 of "Advanced Rails".

    >
    > Then why wouldn't you post your question in a Rails forum??!


    Because, if you read past he first line, you'd realize that it is
    definitely a Ruby and not a Rails question.

    --
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
    Rick DeNatale, May 15, 2008
    #4
  5. Mark Wilden

    Mark Wilden Guest

    On May 14, 2008, at 10:05 PM, ara.t.howard wrote:

    >> Here's my problem. If A1 doesn't contain the method, what causes
    >> the search to backtrack to the B proxy and follow its super pointer
    >> to the C proxy? This "backtracking" seems counter to the purported
    >> "linear" lookup order. (This is just a conceptual problem for me -
    >> it's obvious what the lookup order is, and it's easy to verify.)

    >
    > as each module in included in the target, it's entire lookup chain
    > is added to that target - therefore no 'backtracking' is required,
    > we just end up with a long line that, when followed, happens to give
    > the appearance if backtracking.


    I do understand that that's how it works in practice. I was trying to
    understand the process in terms of its implementation via proxies,
    klass, super and m_tbl. If it were truly implemented as a single long
    chain, then that would require (in my example) that the A2 proxy's
    super points to the B proxy. Hmmm....I wonder if that's indeed the
    case, as you imply?

    ///ark
    Mark Wilden, May 15, 2008
    #5
  6. On Thu, May 15, 2008 at 10:59 AM, Mark Wilden <> wrote:
    > On May 14, 2008, at 10:05 PM, ara.t.howard wrote:
    >
    >>> Here's my problem. If A1 doesn't contain the method, what causes the
    >>> search to backtrack to the B proxy and follow its super pointer to the C
    >>> proxy? This "backtracking" seems counter to the purported "linear" lookup
    >>> order. (This is just a conceptual problem for me - it's obvious what the
    >>> lookup order is, and it's easy to verify.)

    >>
    >> as each module in included in the target, it's entire lookup chain is
    >> added to that target - therefore no 'backtracking' is required, we just end
    >> up with a long line that, when followed, happens to give the appearance if
    >> backtracking.

    >
    > I do understand that that's how it works in practice. I was trying to
    > understand the process in terms of its implementation via proxies, klass,
    > super and m_tbl. If it were truly implemented as a single long chain, then
    > that would require (in my example) that the A2 proxy's super points to the B
    > proxy. Hmmm....I wonder if that's indeed the case, as you imply?


    module A1; end;
    module A2; end;
    module B; include A1; end
    module C; include A2; end
    class D; include C; include B; end

    results in the chains:

    A1
    A1
    B -> proxy1(A1)
    C-> proxy2(A2)
    D->proxy5(B)->proxy6(A1)->proxy3(C)->proxy4(A2)->Object->proxy0(Kernel)

    where proxyn indicates the nth module-proxy in creation order.

    When you include a module in a class, the current chain is searched to
    see if the module is already included and doesn't re-include it, and
    includes in a given class or module executed later are inserted before
    earlier includes in the same class or module, so the chain for the
    original set of modules and classes:

    module A; end;
    module B; include A; end
    module C; include A; end
    class D; include B; include C; end

    The chain for D looks like this:

    D->proxy(C)->proxy(B)->proxy(A)->Object->proxy(Kernel)

    This can lead to some small surprises for some people. Ruby doesn't
    include a proxy to a given module more than once in any inheritance
    chain, because of the way it implements finding overridden methods
    when resolving super. MRI doesn't keep track of the place in the
    chain where it found the currently executing method, so to find the
    method to be invoked for super, it searches again from the start until
    it finds the current METHOD, then searches from the next link in the
    chain. If a module proxy were repeated then this wouldn't work
    because some cases would loop. See the two articles below:

    http://talklikeaduck.denhaven2.com/articles/2007/06/02/chain-chain-chain
    http://talklikeaduck.denhaven2.com/...ss-variable-reversion-and-a-mystery-explained

    --
    Rick DeNatale

    My blog on Ruby
    http://talklikeaduck.denhaven2.com/
    Rick DeNatale, May 15, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Justin Standard
    Replies:
    0
    Views:
    262
    Justin Standard
    Feb 7, 2005
  2. Rich
    Replies:
    2
    Views:
    81
    Eero Saynatkari
    Dec 28, 2005
  3. Martin DeMello
    Replies:
    3
    Views:
    115
    Joel VanderWerf
    Nov 9, 2006
  4. Replies:
    2
    Views:
    97
  5. Dale
    Replies:
    1
    Views:
    109
Loading...

Share This Page