# Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

8 messages
Open this post in threaded view
|

## Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 How to comprehend "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined". Could somebody explain that in more depth? Best regards Sunshilong
Open this post in threaded view
|

## Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 Hello,"it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order.On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote:How to comprehend "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined". Could somebody explain that in more depth? Best regards Sunshilong
Open this post in threaded view
|

## Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 >>How to comprehend "due to the way that Lua implements tables, the >>order that elements appear in a traversal is undefined". >>Could somebody explain that in more depth? >"it's undefined" means "no guarantees are made about the order." >The hope is that people will not rely on the order, then the >implementation can be changed in the future without anyone's code >breaking, because they did not rely on the order. Thank you for your clarification. Sorry, maybe I mislead you. The sentence aforementioned is quoted from <>(Page 38). Here is the sentence followed [emphasise mine]: The same program can **produce different orders each time it runs**. The only certainty is that each element will appear once during the traversal. Why the same program may produce different orders each time it runs? On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote: > > Hello, > > "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order. > > > On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote: >> >> How to comprehend "due to the way that Lua implements tables, the >> order that elements appear in a traversal is undefined". >> >> Could somebody explain that in more depth? >> >> Best regards >> Sunshilong
Open this post in threaded view
|

## Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 Because the way a table is built may depend on other factors like the allocation of other objects and the actions performed by the garbage collector, which may compact the internal representation separately (This would not invalidate the currently open iterators, but may affect the way a new iterator on the same table could operate, as it may start iterating on another item, or could traverse the internal tree in different branches structured differently; notably because a tree-like representation may contain pages randomly ordered by hashes, the iterators keeping only a "snapshot" of the current pages being traversed).Lua does not formally define how tables are structured, and even the existing implementation does not document the two parts of the table (indexed by integer, or hashed), and these two parts may be restructured at any time by the garbage collector moving some items from one part to another (and it can do that safely when the table has no iterator currently open on it).You may also have background threads or coroutines adding and removing temporary items in the table: if the thread/coroutine is yielded to another, they can change the backing store, the total number of nodes could increase or be reduced only in free nodes, while not changing the number of used nodes. As well a compactor may change the internal hashing functions depending on the fill rate or total size allocated, it could rebuild the collision lists.There's already been multiple implementations of tables in Lua, and the specs allow for new implementations. The only contract is that no items should be iterated twice in the same traversal, and that all items in the table should be iterated (as long as the set of items is not extended or reduced, i.e. the set of distinct keys; note that this last set is unordered, this is just a set).The same could apply to other languages using hash tables for their collections (Java, PHP, standard C++ libraries, Javascript, C#, Python, PostScript, Forth, etc., ... or filesystems for files or subdirectories in a directory). It is important to know how iterators are implemented and what they keep in their current state to respect the contract.Le dim. 11 oct. 2020 à 13:41, 孙世龙 sunshilong <[hidden email]> a écrit :>>How to comprehend "due to the way that Lua implements tables, the >>order that elements appear in a traversal is undefined". >>Could somebody explain that in more depth? >"it's undefined" means "no guarantees are made about the order." >The hope is that people will not rely on the order, then the >implementation can be changed in the future without anyone's code >breaking, because they did not rely on the order. Thank you for your clarification. Sorry, maybe I mislead you. The sentence aforementioned is quoted from <>(Page 38). Here is the sentence followed [emphasise mine]: The same program can **produce different orders each time it runs**. The only certainty is that each element will appear once during the traversal. Why the same program may produce different orders each time it runs? On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote: > > Hello, > > "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order. > > > On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote: >> >> How to comprehend "due to the way that Lua implements tables, the >> order that elements appear in a traversal is undefined". >> >> Could somebody explain that in more depth? >> >> Best regards >> Sunshilong
Open this post in threaded view
|

## Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 In reply to this post by 孙世龙 sunshilong Well, with different Lua version it MAY change the order, as far as I read this. Do not remember the implementation details at the moment thought.On Sun, Oct 11, 2020, 13:41 孙世龙 sunshilong <[hidden email]> wrote:>>How to comprehend "due to the way that Lua implements tables, the >>order that elements appear in a traversal is undefined". >>Could somebody explain that in more depth? >"it's undefined" means "no guarantees are made about the order." >The hope is that people will not rely on the order, then the >implementation can be changed in the future without anyone's code >breaking, because they did not rely on the order. Thank you for your clarification. Sorry, maybe I mislead you. The sentence aforementioned is quoted from <>(Page 38). Here is the sentence followed [emphasise mine]: The same program can **produce different orders each time it runs**. The only certainty is that each element will appear once during the traversal. Why the same program may produce different orders each time it runs? On Sun, Oct 11, 2020 at 6:12 PM Robert Burke <[hidden email]> wrote: > > Hello, > > "it's undefined" means "no guarantees are made about the order." The hope is that people will not rely on the order, then the implementation can be changed in the future without anyone's code breaking, because they did not rely on the order. > > > On Sun, Oct 11, 2020, 17:37 孙世龙 sunshilong <[hidden email]> wrote: >> >> How to comprehend "due to the way that Lua implements tables, the >> order that elements appear in a traversal is undefined". >> >> Could somebody explain that in more depth? >> >> Best regards >> Sunshilong
Open this post in threaded view
|

## Re: Could somebody explain "due to the way that Lua implements tables, the order that elements appear in a traversal is undefined" in more detpth?

 In reply to this post by 孙世龙 sunshilong Sunshilong. On Sun, Oct 11, 2020 at 1:41 PM 孙世龙 sunshilong <[hidden email]> wrote: > The sentence aforementioned is quoted from <>(Page 38). > Here is the sentence followed [emphasise mine]: > The same program can **produce different orders each time it runs**. > The only certainty is that each element will appear once during > the traversal. > > Why the same program may produce different orders each time it runs? I do not have the whole program handy, so I do not know the exact answer. But if all the program does is fill a table and then traverse it it may be due, typically, by randomization of hashes ( you generate a random value at program/lua state start and use it in the generation of hash values, a classical mitigation of denial of service attacks similar to salting passwords ). It may be due to other reasons. In general this hints you on not relying on table enumeration order. Francisco Olarte.