Multi-level multi-inheritance realization

["Ivan Smirnov" <i.s.smirnov@...>]

Hello everyone, I've come up to the problem of 'true' inheritance realization in Lua recently. Being correctly implemented, this can give you a full control over data inheritance and storage.

Let me first give some examples.

1) 'Vanilla' classes - those massively described in wiki and PiL 

// let 'class' be some class constructing function, and 'inherits' field - a table listing parents

X = class { a = 1 }
Y = class { inherits = {X}}
print(Y.a) --> 1

2) 'Vanilla' multi-inheritance:

X = class { a = 1 }
Y = class { a = 2 }
A = class { inherits = { X, Y }}
B = class { inherits = {Y} }
C = class { a = 3, inherits = {X}}
print(A.a, B.a, C.a) --> 1  2  3

3) Major problem about both methods:

X = class { a = {b = 1, c = 2}}
Y = class { inherits = {X}, a = {b = 3}}
print(Y.a.b, Y.a.c) --> 3, nil 

However, we MIGHT expect the result to be 3, 2.

A bit more complicated:

A = class {a = 1, b = 2 }
B = class {b = 3, c = 4 }
C = class {c = 5, d = 6 }

D = class { N = class {inherits = {B}} }
E = class { N = class {inherits = {A}} }

X = class { inherits = {D, E}, N = class {inherits = {C}}}

print(X.N.a, X.N.b, X.N.c) --> nil, nil, 5

However, we might expect it to be 1, 3, 5.

4) A closer look:

The thing is, it's easy to make 1-level inheritance (which simply tracks indexing at the 'root' of the class), but for multi-level multi-parent inheritance we need to dig deep.

Let's take a closer look at the example given above. For X.N.a to result in 3, we need the following:

- X[N] looks for "N" in classes D and E in case "N" doesn't exist in X; however it exists, step 1 is passed
- now X.N[a] looks for field "a" in X.N, it does not exist at all, but there is inheritance with parent C
- we find, that C is one of "owners" of a and look for field "a" in it, however, we don't find it
- now an ESSENTIAL step: we move backwards to the root of X and search for path "N.a" in both classes D and E
- we look for "N" in D, it exists, ok; now we find that "a" doesn't exist in 
D.N, but there is parent B, so we look for B.a and get the desired result of 3

That's a rough of sketch of "todo". It's easy to say on words, but seems not to easy to implement.

5) Implementation.

The way I implemented this kind of inheritance (not going very deep in details):

- Initially, the root of class is endowed with a metatable containing __index, __newindex and __owner, holding itself in owner field.
- New index function: in case we feed a class field with a table (i.e., we write X.N = {a = 1}), it parses the table and puts it into proxy (i.e., X.__data.N.__data.a = 1), setting metatables recurrently for all nested subtables.
- In case new index function meets another class to become a field of some subtable belonging to class, it looks for "shared" field
- In case a subtable is another class with shared field omitted or false, or it is a table with shared set to false, subtable is no further parsed and just saved as pointer (with no metatables set)
- In case there is a "shared" class, new index function digs in and modifies "__owner" field in subtables of this class, addding owners of the table which triggered the new index
- As well, relative paths are stored inside tables, for each owner (
i.e., if we write X.N.a = 1, table N will have a metatable with two owners, N and X, and N.a will have two relative paths, {"a"} and {"N.a"})
- index function looks for all owners of target, then goes over all parents of the owner, using the associated relative path

6) Problems.

I didn't optimize the code heavily (because it would become completely uneditable), however I think it won't work VERY fast. I wonder if my vision of implementation of those classes is wrong, or just the implementation itself is far from perfect. Perhaps, another, more effective approach can be used.

Possible tweaks: instead of creating numerous proxies, it is possible to add __write and __read metatables events in Lua source (not so hard, indeed).

7) Source:

http://aldanor.vladna.com/lua/class-published.lua

This is some pre-alpha-version, non-optimized, may contain NUMEROUS bugs, just given to illustrate my message. Several examples are attached.

------------------------------------------------
I will be glad to hear ANY response on the subject.
------------------------------------------------

Regards,
Ivan