Serialize Table

[MrNathanStiles]

When using serde feature to serialize a table keys are coerced to string and data is missing from serialization.

cargo.toml

[package]
name = "mlua_serde_bug"
version = "0.2.0"
edition = "2024"

[dependencies]
mlua = { version = "0.11.1", features = ["luau", "send", "serde"] }
serde = { version = "1.0.219", features = ["serde_derive"]}
serde_json = "1.0.143"
anyhow = { version = "1.0", optional = true }

main.rs

use mlua::{Lua, LuaSerdeExt, Result, Table, Value};
use serde::Deserialize;

fn main() -> Result<()> {
    let lua = Lua::new();
    let value: Value = lua.load(r#"{["1"]="text one",[1]="number one"}"#).eval()?;
    let table: &Table = value.as_table().unwrap();

    let n1 = table.raw_get::<String>(1).unwrap();
    println!("n1 {}", n1);
    let t1 = table.raw_get::<String>("1").unwrap();
    println!("t1 {}", t1);
    assert!(n1 == "number one".to_owned());
    assert!(t1 == "text one".to_owned());

    let serialized = serde_json::to_string(&value).unwrap();
    let deserialized: serde_json::Value = serde_json::from_str(&serialized).unwrap();
    let value: Value = lua.to_value(&deserialized).unwrap();
    let table: Table = value.as_table().unwrap().clone();

    let n1 = table.raw_get::<String>(1).unwrap();
    println!("n1 {}", n1);
    let t1 = table.raw_get::<String>("1").unwrap();
    println!("t1 {}", t1);
    assert!(n1 == "number one".to_owned());
    assert!(t1 == "text one".to_owned());

    Ok(())
}

[khvzak]

In your example Lua table is both map and array. Such state cannot be represented in json. In this case, mlua prefer to encode array part and ignore object part.

[MrNathanStiles]

There is a problem with the serialization in general I think. Even if I use a different format, if a table has a gap in numbers things after the gap are getting skipped.

foo={}
foo[1]="bar"
foo[3]="baz"

this is turned into an array and only "bar" is present

[khvzak]

There is a problem with the serialization in general I think.

It's not a problem with serialization, this is how Lua works. If you try to iterate over the values of foo:

print("foo len is "..rawlen(foo))
for i, n in ipairs(foo) do
  print(i, n)
end

It will print only one value:

foo len is 1
1	bar

If you want to fill the gap with JSON null, setting it to Lua::null can help.

[MrNathanStiles]

Lua does not skip entries when using pairs.

[MrNathanStiles]

No matter it's easy enough to create my own serialization which I have done but I'm running into an issue when cloning the deserialized table. I'm cloning them account for the possibility of a recursive data structure. The code I have is producing a panic.

panicked at .cargo\registry\src\index.crates.io-1949cf8c6b5b557f\mlua-0.11.1\src\state\extra.rs:283:17:
cannot create a Lua reference, out of auxiliary stack space (used 7996 slots)
.cargo\registry\src\index.crates.io-1949cf8c6b5b557f\mlua-0.11.1\src\state\extra.rs:283:17

rust code below if I comment the line with the table clone it's fine.

fn deserialize(&mut self, lua: &mlua::Lua, data: &MySerializedData) -> mlua::Value {
    match data {
        MySerializedData::Bool(e) => lua.to_value(e).unwrap(),
        MySerializedData::Float(e) => lua.to_value(e).unwrap(),
        MySerializedData::Integer(e) => lua.to_value(e).unwrap(),
        MySerializedData::Nil => mlua::Nil,
        MySerializedData::String(e) => lua.to_value(e).unwrap(),
        MySerializedData::RecursiveTable(e) => {
            match self.lookup.get(e) {
                Some(e) => mlua::Value::Table(e.clone()),
                None => {
                    let pairs = self.tables.get_mut(*e).unwrap().take().unwrap();
                    let data = pairs.iter().map(|(k, v)| {
                        (self.deserialize(lua, &k), self.deserialize(lua, &v))
                    });
                    let table = lua.create_table_from(data).unwrap();
                    self.lookup.insert(*e, table.clone()); // ERROR goes away if I don't clone/comment this line
                    mlua::Value::Table(table)
                }
            }
        },
    }
}

Any ideas why this is happening?

[khvzak]

Lua does not skip entries when using pairs.

pairs is not the best way to iterate over an array. Order of returned elements is not guaranteed, you can get any element of array first. serde does not support serialising array elements out of order.

Any ideas why this is happening?

Could you try the latest 0.11.3?

[MrNathanStiles]

I'm not talking about arrays I'm talking about tables in lua. In the context of serialization pairs is the better choice over ipairs it does gather all of the entries in the table which ipairs does not do.

in version 0.11.3 the serialization continues to omit data and my custom implementation continues to panic when keeping many tables in a HashMap

[appgurueu]

It's not a problem with serialization, this is how Lua works.

You seem to have a misconception related to how Lua tables work.

A Lua table is just an associative array. {[1] = true, [3] = true} for example is a completely valid Lua table, and there are very valid reasons to use such a table (for example to represent a sparse set of integer keys; say a small connected component in a larger graph with enumerated node IDs).

Of course, using ipairs with such a table is a bad idea; you would use pairs. But this is what you want: It's just a set, you do not care about the order of elements. Of course, this can not be turned into proper JSON; but there are other serialization formats that can handle it just fine. I've written a few of my own. CBOR supports numeric keys in maps.

Generic serialization for Lua values that can not handle Lua tables is a bug.

[MrNathanStiles]

I'm able to prevent the panic buy using an mlua::Table in place of a HashMap to hold tables during the deserialization.

Here's a shorter reproduction using ciborium

    let lua = Lua::new();
    lua.load(r#"
        foo = {}
        foo[1]="bar"
        foo[3]="baz"
    "#).exec().unwrap();
    let value: Table = lua.globals().raw_get("foo").unwrap();
    let mut data = Vec::new();
    into_writer(&value, &mut data).unwrap();
    let result: ciborium::Value = from_reader(data.as_slice()).unwrap();
    println!("foo {:?}", result);

[khvzak]

You seem to have a misconception related to how Lua tables work.
A Lua table is just an associative array.

I'm afraid it's not that simple. Lua table is a hybrid of vector and hashmap merged into one entity.
We can confirm this directly from the Lua source code and comments:

** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest 'n' such that
** more than half the slots between 1 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.

So for table like {[1] = true, [3] = true} elements are stored in the array part of the table (i.e. no hash overhead).
This is why Lua has a dedicated pairs and ipairs methods to traverse tables. In particular, Lua length operator # or rawlen function return size of array part of the table ignoring the hash one.
See:

> print(#{a=1,b=2,c=3})
0
> print(#{1,2,3})
3

mlua uses some heuristics to check how a table should be traversed and serialized. If array part is set (table length is greater than zero or an array metatable attached) then the table is considered as an array of elements and the index-based traversal is used to access the elements.
The problem is that we don't know the most right index of array part and iteration over the table with gaps stops when the first gap is reached.

Currently there is no specific logic in mlua how to handle sparse array. Switching to pairs/lua_next does not give guaranteed order and non-array elements can appear in results. We don't really want to read non-array part of table when serializing it as an array.

you do not care about the order of elements.

Unfortunately we do care. This is how serde works, it requires elements strictly in order without gaps when serializing a sequence. The API is as simple as calling serialize_element without even an index.

but there are other serialization formats that can handle it just fine. I've written a few of my own. CBOR supports numeric keys in maps.

That is a different story. I probably need to add a metatable to force encoding table as a map even if array part is set. Similar to Lua::array_metatable.

[appgurueu]

I'm afraid it's not that simple. Lua table is a hybrid of vector and hashmap merged into one entity.

It is. That is an implementation detail. You can implement a Lua table as just a hash map. The fact that it may (or may not) store some keys in an array part under the hood to improve performance does not change the fact that Lua tables are conceptually associative arrays. I suggest you consult the Lua reference manual:

The type table implements associative arrays, that is, arrays that can be indexed not only with numbers, but with any value (except nil [and NaN]).

(I linked the 5.1 one here, but almost the same sentence still persists in the 5.4 reference manual.)

So for table like {[1] = true, [3] = true} elements are stored in the array part of the table (i.e. no hash overhead).

This is not true. Lua decides based on density whether to store entries in the array part. You should know this based on the comment you cited:

The actual size of the array is the largest 'n' such that more than half the slots between 1 and n are in use.

So, for {[1] = true, [3] = true} to be stored in the array part, the array part would need to have size 4; but then only exactly half (not more than half) of the slots would be used. Therefore, the array part will have size 1, containing just a single true, and the hash part will have size 1 as well, containing [3] = true, at least for PUC Lua.

This happens to be iterated as 1, 3 by pairs because pairs first iterates the array part. It's easy to check that if you have more entries in the hash part, they will be iterated out of order.

This is why Lua has a dedicated pairs and ipairs methods to traverse tables.

These methods do not care about array and hash part. They would work just as well if there only was a hash map. Again, it's an implementation detail, it's hidden completely from the user (except for performance characteristics). ipairs just iterates t[1], t[2], ..., t[i] until t[i] is nil. It would work just as well if the entire table - or part of it - lived in the hash part, as may be the case when you start with a sparse table, then remove elements to get a sequence (because PUC Lua will not rehash if you only remove elements). pairs just iterates all k-v-pairs. Obviously that works with a hash map just as well.

In particular, Lua length operator # or rawlen function return size of array part of the table ignoring the hash one.

This is patently false. You have not understood the length operator. I suggest you consult the Lua reference manual or my blog post covering this. The gist is that #t is 0 if t[1] is nil; otherwise #t is an integer such that t[#t] ~= nil and t[#t + 1] == nil. That is, for example, #{1, [1e9] = 2} == 1e9 is a valid thing for a Lua implementation to do. (And there are cases where things like this happen.)

#t checks the hash part, because it just tries to find a border; and part of a sequence may live in the hash part.

If array part is set (table length is greater than zero or an array metatable attached) then the table is considered as an array of elements and the index-based traversal is used to access the elements.

Well, that is a flawed oversimplification. What you need to check instead is that the table is, in fact, a sequence: That it has exactly keys 1, ..., n, with non-nil values. Any other keys and you must consider the table a map.

If you don't do this, you will mishandle (1) mixed tables {foo = 1, bar = 2, 3, 4} (which do happen, e.g. if you have DOM-like things some authors like to put children straight in the table) and (2) sparse tables with numeric keys (some of which may also be floats rather than ints).

Switching to pairs/lua_next does not give guaranteed order and non-array elements can appear in results.

They can and they must! Otherwise you're losing data. A mixed/sparse table has no guaranteed order. Again Lua tables are associative arrays.

This is how serde works, it requires elements strictly in order without gaps when serializing a sequence.

But it is not a sequence. It is a map, e.g. it would be better to turn a table with just numeric keys into a hash map from floats to values.

I probably need to add a metatable to force encoding table as a map even if array part is set.

This sounds like a hack.

---

I get that Rust and many other languages draw a clear distinction between array (lists) and hash maps. But Lua does not. If in doubt, map Lua tables that do not map 1:1 to array lists to hash maps instead. This is completely valid. If you're concerned about the performance implications (though it's not that big a deal because you can assume that this is somewhat rare), write yourself a map type with array and hash part as found in Lua.

[appgurueu]

Sorry for digressing a bit in my comment above.

After discussing this with a few developer friends privately, I want to focus on what I think is the main issue. mlua seems to be silently losing data in serialization of tables with holes, sparse tables, mixed tables, whatever they may be conceptually used for, no matter whether a serialization format is used that could handle them (see #640 (comment)).

That is a bug for a serializer-deserializer pair, which should either round-trip values correctly or error when it can't do that (or explicitly state that some things are not round-trippable and will be stripped, but then this should be documented; and not being able to round trip the aforementioned kinds of tables would be a pretty big and unnecessary limitation).

[khvzak]

That is a bug for a serializer-deserializer pair, which should either round-trip values correctly or error when it can't do that (or explicitly state that some things are not round-trippable and will be stripped, but then this should be documented; and not being able to round trip the aforementioned kinds of tables would be a pretty big and unnecessary limitation).

I need to think about it. It's not a bug rather a deliberate decision that Lua->serde->Lua is not always round-trippable. I agree about better documenting this.
Otherwise it would be possible to end up in a situation when data is oddly encoded.
See an example from Lua cjson when encoding a mixed table:

> t = {["1"]=1,2,3}; print(require('cjson').encode(t))
{"1":2,"2":3,"3":4,"1":1}

While the json {"1":2,"2":3,"3":4,"1":1} is technically valid, it can be rejected depending on parser implementation.
Also this is what RFC-8259 mention as well.
You can say that this is a developer problem by providing such data and it's true.

It would be better to raise an error instead but (correct me if I'm wrong) there is no fast way to say if a table has only one border or not. So for the performance reasons only first sequence is taken when presence of sequence is detected using lua_rawlen method.

I may provide an option to opt-out from this behaviour and allow mixed tables, but it may have some performance tradeoffs for some cases.
For example, Lua cjson when calculating array length does a full O(N) scan. And I don't want to do this by default.

[MrNathanStiles]

Better to use pairs or whatever for_each does and store the pairs as an array for example in JSON it would look like.

[[1,"bar"],[3,"baz"],["whatever",6]]

Lua table isn't an array and JSON can handle whatever contents of a Lua table.

[appgurueu]

For example, Lua cjson when calculating array length does a full O(N) scan. And I don't want to do this by default.

Personally I would consider this not that big of a deal because serialization is O(N) anyways; I might prioritize features / correctness here. But I understand if your priorities are different. I think we can still do something interesting though. Let me elaborate:

It would be better to raise an error instead but (correct me if I'm wrong) there is no fast way to say if a table has only one border or not.

You're not wrong per se. Borders can be "hidden" anywhere in the array or hash part, so to find all borders, you'd need to scan the entire table.

However, you could also do the following instead:

1. Determine a border of the table using rawlen(t).
2. Then, serialize t[1], t[2] ... until rawlen(t), or until you hit a nil. If you hit a nil while serializing, raise an error. This should be very close to zero cost; you do not have to do a separate full array scan, you can do it on the fly in the same pass. ¹
3. Finally, call lua_next. If the returned index is not a valid index in the range from 1 to #t, the table is not a valid sequence.

This has some nice properties:

• It is efficient: You're already calling rawlen; checking for nil costs very little. The final call to lua_next should normally also not be that expensive. ²
• It is conservative: It will never falsely claim that a sequence is not a sequence.
• On PUC Lua and LuaJIT, it will usually work, due to implementation details (namely, next walking the array part in order, followed by the hash part). ² (Someone pointed out to me that it might however still fail if #t and some of the list entries live in the hash part.)

It is slightly cursed, but it may just be the right amount of cursed.

Configuration options certainly seem like the way to go forward. It should be possible to preserve some "less standard" kinds of tables, especially if you're willing to pay the performance cost.

Footnotes

1. Might wanna be careful with preallocating things here. If #t is absurdly big, that could cause problems. And for mlua to be robust it'd be better if it didn't. So I'd avoid preallocation. If you do want to avoid most of the allocations, I'd cap preallocations at some reasonable size, say 256 slots. ↩

2. What it will do under the hood is scan the remainder of the array part, and if it finds nothing there it'll walk the hash part until it finds a live entry, but there is no good way around this unless you really assume (because you can't know) you've got a sequence. The former will technically have Lua walking n/4 slots on average, but this should happen super fast because there is virtually no overhead, it all happens inside the well-optimized guts of next (and this can be and hopefully is vectorized and whatnot). The latter should, excepting pathological cases with many deletions, probably be O(1) most of the time. In particular, it's O(1) if the hash part following the first border is empty, as for a sequence it will be - there is only a risk of cost on the unhappy path, where you end up erroring out anyways. ↩ ↩²