Re: Better __index lookup loop detection

[Xmilia Hermit <xmilia.hermit@...>]

> Would you mind explaining this idea more clearly?
I can try.
First of all, this is noting new and based upon 
https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare.

For the following examples {} should denote a Lua table and A->B a 
__index link which can be created in Lua through setmetatable(A, 
{__index = B}).

Then a normal lookup starting in table A would go like:
A->{}->{}
^
I

A->{}->{}
^   ^
L   I

A->{}->{}
^       ^
L       I

A->{}->{}
   ^    ^
   L    I

Here I is the normal iterator looking for the key and L is the slower 
iterator for loop detection only advancing when I did two steps. If the 
key is found or I does not find an __index table the lookup is stopped 
normally.

In case there is a loop the structure would be

A->{}->...->{}->B->{}->...->{}->B

for an example we use

A->{}->B->{}->{}->{}->B
^
I

A->B->{}->{}->{}->{}->B
^  ^
L  I

A->B->{}->{}->{}->{}->B
^      ^
L      I

A->B->{}->{}->{}->{}->B
   ^   ^
   L   I

A->B->{}->{}->{}->{}->B
   ^       ^
   L       I

A->B->{}->{}->{}->{}->B
   ^           ^
   L           I

A->B->{}->{}->{}->{}->B
      ^        ^
      L        I

A->B->{}->{}->{}->{}->B
      ^            ^
      L            I

A->B->{}->{}->{}->{}->B (Note: Iterator jumps back because of the loop)
   ^  ^
   I  L

A->B->{}->{}->{}->{}->B
   ^      ^
   I      L

A->B->{}->{}->{}->{}->B
       ^  ^
       I  L

A->B->{}->{}->{}->{}->B
          ^^
          LI

At some point the iterators I and L will point to the same element wenn 
there is a loop in the __index chain at which point the exception is raised.

Regards,
Xmilia