Iteration order

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
zorg
Party member
Posts: 3436
Joined: Thu Dec 13, 2012 2:55 pm
Location: Absurdistan, Hungary
Contact:

Re: Iteration order

Post by zorg »

BrotSagtMist wrote: Sun May 28, 2023 10:20 pm But order in pairs/next should be consistent until changes to the table are made.
Does the reference state such a guarantee?
Me and my stuff :3True Neutral Aspirant. Why, yes, i do indeed enjoy sarcastically correcting others when they make the most blatant of spelling mistakes. No bullying or trolling the innocent tho.
MrFariator
Party member
Posts: 509
Joined: Wed Oct 05, 2016 11:53 am

Re: Iteration order

Post by MrFariator »

It doesn't. Since the behavior is not codified in any official reference or specification as far as I'm aware, that behavior may be subject to changes between versions of lua/luajit. Can think of it like undefined behavior, that may work for you in the moment, but not necessarily in different environments.
User avatar
BrotSagtMist
Party member
Posts: 607
Joined: Fri Aug 06, 2021 10:30 pm

Re: Iteration order

Post by BrotSagtMist »

'The behavior of next is undefined if, during the traversal, you assign any value to a non-existent field in the table. You may however modify existing fields. In particular, you may clear existing fields.'
Which i would read as, its defined until you add stuff.
obey
User avatar
slime
Solid Snayke
Posts: 3131
Joined: Mon Aug 23, 2010 6:45 am
Location: Nova Scotia, Canada
Contact:

Re: Iteration order

Post by slime »

That's talking about a separate bit of undefined behaviour. Iteration order is not specified to be consistent during any point.
User avatar
BrotSagtMist
Party member
Posts: 607
Joined: Fri Aug 06, 2021 10:30 pm

Re: Iteration order

Post by BrotSagtMist »

You would not be able to iterate at all if that is the case.
obey
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Iteration order

Post by pgimeno »

I think Brot has a point. next(element) must return a value. If pairs() is based on next() then next(element) must be consistent for a certain element, as long as no elements are added to the table, because pairs() isn't expected to keep track of whether next() is visiting an already visited element or a new one. It's hard to devise a scheme where next(element) can change when the table has not been modified, except if designing it on purpose.

The only realistic scheme I can think of, where order can change between calls to pairs() when the table doesn't change, is: hash based on addresses; if a table is unlocked, then it can be freely moved in memory, and since the hashes are address based, the order can change; next(x) locks the table except if it returns nil, in which case it unlocks the table. It's still a quite artificial scenario, and would make next(element) change for a certain element without modifying the table, just because you asked for a different one in between.

That doesn't mean it needs to be consistent between runs though, even if the elements in the table and the order of insertion of the elements are the same. Hashes based on addresses, as mentioned above, are a possibility, and due to ASLR the addresses are random.
User avatar
BrotSagtMist
Party member
Posts: 607
Joined: Fri Aug 06, 2021 10:30 pm

Re: Iteration order

Post by BrotSagtMist »

Booth the lua and the luajit pages state the order changes when elements are added.
To my understanding that must mean it does never change when no elements are added.
Thats my thinking here.
obey
User avatar
slime
Solid Snayke
Posts: 3131
Joined: Mon Aug 23, 2010 6:45 am
Location: Nova Scotia, Canada
Contact:

Re: Iteration order

Post by slime »

It doesn't say that order never changes until an element is added. It does say this:
The order in which the indices are enumerated is not specified, even for numeric indices. (To traverse a table in numeric order, use a numerical for or the ipairs function.)

The behavior of next is undefined if, during the traversal, you assign any value to a non-existent field in the table. You may however modify existing fields. In particular, you may clear existing fields.
This means you can't rely on it guaranteeing any order and also the entire function's behaviour (not just iteration order) becomes undefined if you add a key while iterating. The only guarantee is that it iterates through all key/value pairs in the table, there's absolutely no order guarantees and there's not even a guarantee that order will change if you cause undefined behaviour by adding a key while iterating.

Following "don't rely on behaviour specified to be unreliable" as a rule isn't too hard in this situation, IMO. There are lots of valid ways to iterate through something in a reliable order, they just don't use pairs or next to do it.
User avatar
BrotSagtMist
Party member
Posts: 607
Joined: Fri Aug 06, 2021 10:30 pm

Re: Iteration order

Post by BrotSagtMist »

Well i see it as guaranteed. Thats just my understanding of this text.
obey
Post Reply

Who is online

Users browsing this forum: No registered users and 44 guests