# A Solidity Linearization Puzzle

I was playing in remix just to concretize my understanding of Solidity linearization, and got a result I didn't expect and can't rationalize. Why does `AC_BA.go()` return `3`?

(Please scroll to the bottom of the code below.)

``````pragma solidity ^0.4.24;

contract A {
function go() public pure returns (uint out) {
out = 1;
}
}
contract B {
function go() public pure returns (uint out) {
out = 2;
}
}
contract C {
function go() public pure returns (uint out) {
out = 3;
}
}

// returns 2 as expected
contract AB is A, B {
function go() public pure returns (uint out) {
out = super.go();
}
}

// returns 1 as expected
contract BA is B, A {
function go() public pure returns (uint out) {
out = super.go();
}
}

// returns 3 as expected
contract AC is A, C {
function go() public pure returns (uint out) {
out = super.go();
}
}

// refuses to compile, can't linearize, ok
//
// contact AC_A is AC, A {
//     function go() public pure returns (uint out) {
//       out = super.go();
//    }
// }

// compiles, returns 2, from AB
contract AC_AB is AC, AB {
function go() public pure returns (uint out) {
out = super.go();
}
}

// compiles, returns 3, why???
contract AC_BA is AC, BA {
function go() public pure returns (uint out) {
out = super.go();
}
}
``````

Borrowing the notation from C3 linearization on Wikipedia, and keeping in mind that Solidity reverses the typical ordering ("You have to list the direct base contracts in the order from 'most base-like' to 'most derived'. Note that this order is different from the one used in Python."):

``````L(AC) := [AC] + merge(L(C), L(A), [C, A])
= [AC] + merge([C], [A], [C, A])
= [AC, C] + merge([A], [A])
= [AC, C, A]

L(BA) := [BA] + merge(L(A), L(B), [A, B])
= [BA] + merge([A], [B], [A, B])
= [BA, A] + merge([B], [B])
= [BA, A, B]

L(AC_BA) := [AC_BA] + merge(L(BA), L(AC), [BA, AC])
= [AC_BA] + merge([BA, A, B], [AC, C, A], [BA, AC])
= [AC_BA, BA] + merge([A, B], [AC, C, A], [AC])
= [AC_BA, BA, AC] + merge([A, B], [C, A])
= [AC_BA, BA, AC, C] + merge([A, B], [A])
= [AC_BA, BA, AC, C, A] + merge([B])
= [AC_BA, BA, AC, C, A, B]
``````

So calling `AC_BA.go()` ends up calling `C.go()`, which returns 3. I don't have an intuitive explanation for you; this is just the behavior of the C3 linearization algorithm, which Solidity follows.

EDIT

The Solidity compiler can export an AST which includes the linearization of base contracts. A little Python can convert it into a readable form:

``````import json
import sys

symbol_map = {}

for symbol, ids in source['AST']['attributes']['exportedSymbols'].items():
for id in ids:
symbol_map[id] = symbol

for child in source['AST']['children']:
attributes = child['attributes']
if attributes.get('contractKind', None) == 'contract':
print('{}: {}'.format(attributes['name'], ' -> '.join(symbol_map[id] for id in attributes['linearizedBaseContracts'])))
``````

How to run it:

``````solc --combined-json ast test.sol | python3 linearization.py
``````

Output:

``````A: A
B: B
C: C
AB: AB -> B -> A
BA: BA -> A -> B
AC: AC -> C -> A
AC_AB: AC_AB -> AB -> B -> AC -> C -> A
AC_BA: AC_BA -> BA -> AC -> C -> A -> B
``````

When you call `AC_BA.go()`, that calls `BA.go()`, which in turn calls `AC.go()` and finally `C.go()` (returning 3).

EDIT 2

Surya is a handy tool that will show contract inheritance in linearized order.

``````\$ surya dependencies AC_BA test.sol
AC_BA
↖ BA
↖ AC
↖ C
↖ A
↖ B
``````
• Given the potential costs of misunderstanding the linearization of ones contracts, and the not-so-intuitive outcomes, it'd be nice if solc emitted the linearization it settles upon. Is there any way to get that? – Steve Waldman Aug 19 '18 at 20:33
• Edited my answer. The first part was actually wrong (forgot that Solidity reverses the typical order of base classes), and I added the second part which shows how to get the Solidity compiler to tell you the linearization. – user19510 Aug 19 '18 at 21:15
• Thanks! (That makes a lot more sense, I was a bit confused about the prior ordering, but thought it was on me to puzzle that out.) I'll try Surya. – Steve Waldman Aug 19 '18 at 21:25