Stable sort for HashSet #256

streetycat · 2023-05-08T06:50:21Z

Discussed in #253

^{Originally posted by streetycat May 6, 2023}
I am reviewing the encoding format for types. But I find that our encoding process only explicitly sorts the HashMap. Other types(as HashSet/BTreeMap/BTreeSet) depends on the iter in Rust. I have read the documents for those types, The iters for BTreeMap and BTreeSet return elements in ascending order. but I have not found how it is sorted in HashSet.

I am reading the code in raw_types.rs.

I think we have to explicitly define the encoding order of the fields/elements of the composite type, otherwise different results may be encoded.

The text was updated successfully, but these errors were encountered:

lizhihongTest · 2023-05-23T09:42:24Z

@streetycat I conducted a data comparison test after encoding and decoding the Vec/HashMap/HashSet/BTreeMap/BTreeSet data structure in NameObject desc/body, and found the following problems.

The sorting of HashMap/HashSet data in desc after encoding and decoding is inconsistent with the original data
The body data is cleared after encoding and decoding

test source code
test NameObject

Details Logs

[2023-05-23 17:34:08.262820] INFO [ThreadId(2)] [cyfs_base_tool::tool] -----------------------------------  Testcase test_stable_sort_hashset start running ----------------------------------- 
[2023-05-23 17:34:08.264635] INFO [ThreadId(2)] [test_256_hashset::tests] original object desc info id :DvVH86KdKAv4g8bHgXgpk4eRuZ9Ff7RgV8jegWUNtkJt
[2023-05-23 17:34:08.265447] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc name:desc info
[2023-05-23 17:34:08.265803] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc create_time:13329308048263704
[2023-05-23 17:34:08.266143] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc btree_map:
[2023-05-23 17:34:08.266521] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.266929] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.267286] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.267596] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.267917] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.268199] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.268543] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.268855] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.269182] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.269415] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.269651] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc btree_set:
[2023-05-23 17:34:08.269901] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.270134] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.270367] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.270588] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.270797] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.271091] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.271339] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.271567] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.271787] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.272010] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.272290] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc hash_map:
[2023-05-23 17:34:08.272566] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.272874] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.273191] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.273439] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.273693] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.274033] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.274427] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.274743] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.275007] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.275430] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.275786] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc hash_set:
[2023-05-23 17:34:08.276193] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.276497] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.276846] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.277228] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.277620] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.277962] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.278324] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.278661] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.279123] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.279448] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.279790] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc vec_list:
[2023-05-23 17:34:08.280136] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Cat
[2023-05-23 17:34:08.280422] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Dog
[2023-05-23 17:34:08.280723] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Bird
[2023-05-23 17:34:08.281020] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body name:desc info
[2023-05-23 17:34:08.281302] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body create_time:13329308048263704
[2023-05-23 17:34:08.281570] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body btree_map:
[2023-05-23 17:34:08.281858] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.282214] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.282518] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.282781] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.283143] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.283466] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.283765] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.284063] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.284312] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.284563] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.284856] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body btree_set:
[2023-05-23 17:34:08.285164] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.285427] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.285706] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.285939] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.286182] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.286434] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.286709] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.286944] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.287176] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.287398] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.287662] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body hash_map:
[2023-05-23 17:34:08.287928] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.288165] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.288459] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.288708] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.288972] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.289232] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.289462] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.289723] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.290054] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.290394] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.290721] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body hash_set:
[2023-05-23 17:34:08.290996] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.291270] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.291541] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.291798] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.292119] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.292462] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.292805] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.293152] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.293480] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.293761] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.294057] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body vec_list:
[2023-05-23 17:34:08.294424] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Cat
[2023-05-23 17:34:08.294773] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Dog
[2023-05-23 17:34:08.295131] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Bird
[2023-05-23 17:34:08.296486] INFO [ThreadId(2)] [test_256_hashset::tests] decode object desc info id :DvVH86KNs6hnxm3zZQPtCHuvbZGne3LsyhQYtrPj3vjq
[2023-05-23 17:34:08.297071] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc name:desc info
[2023-05-23 17:34:08.297412] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc create_time:13329308048263704
[2023-05-23 17:34:08.297746] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc btree_map:
[2023-05-23 17:34:08.298061] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.298445] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.298784] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.299080] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.299350] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.299637] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.299892] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.300130] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.300417] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.300670] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.300932] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc btree_set:
[2023-05-23 17:34:08.301205] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.301454] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.301726] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.302011] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.302259] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.302493] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.302751] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.303042] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.303327] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.303586] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.303840] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc hash_map:
[2023-05-23 17:34:08.304154] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket0: value0
[2023-05-23 17:34:08.304426] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket3: value3
[2023-05-23 17:34:08.304706] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket7: value7
[2023-05-23 17:34:08.304992] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket6: value6
[2023-05-23 17:34:08.305244] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket2: value2
[2023-05-23 17:34:08.305492] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket4: value4
[2023-05-23 17:34:08.305743] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket9: value9
[2023-05-23 17:34:08.306009] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket5: value5
[2023-05-23 17:34:08.306342] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket8: value8
[2023-05-23 17:34:08.306625] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     ket1: value1
[2023-05-23 17:34:08.306896] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc hash_set:
[2023-05-23 17:34:08.307199] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value7
[2023-05-23 17:34:08.307471] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value2
[2023-05-23 17:34:08.307783] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value8
[2023-05-23 17:34:08.308077] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value3
[2023-05-23 17:34:08.308318] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value4
[2023-05-23 17:34:08.308582] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value1
[2023-05-23 17:34:08.308895] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value0
[2023-05-23 17:34:08.309190] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value5
[2023-05-23 17:34:08.309475] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value6
[2023-05-23 17:34:08.309700] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     value9
[2023-05-23 17:34:08.309936] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Desc vec_list:
[2023-05-23 17:34:08.310201] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Cat
[2023-05-23 17:34:08.310590] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Dog
[2023-05-23 17:34:08.310852] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object]     Bird
[2023-05-23 17:34:08.311236] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body name:
[2023-05-23 17:34:08.311542] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body create_time:0
[2023-05-23 17:34:08.311870] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body btree_map:
[2023-05-23 17:34:08.312171] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body btree_set:
[2023-05-23 17:34:08.312455] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body hash_map:
[2023-05-23 17:34:08.312750] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body hash_set:
[2023-05-23 17:34:08.313067] INFO [ThreadId(2)] [cyfs_base_tool::objects::stable_sort_object] Body vec_list:
[2023-05-23 17:34:08.313457] INFO [ThreadId(2)] [cyfs_base_tool::tool] -----------------------------------  All testcase run finished -----------------------------------

streetycat · 2023-05-23T10:46:20Z

I reviewed your test case, there are some errors:

You sort the fields of Vec/HashMap/HashSet/BTreeMap/BTreeSet yourself, you should encode them with the method provided in cyfs_base for test the methods:

field.to_vec();

or

field.raw_encode(...);

and decode them as follow:

${TypeName}::raw_decode(...);

I think, you are not understand this issue:

The traversal order of HashMap/HashSet is unstable, it's the feature of HashMap and HashSet.

This feature will result in different binary results encoded each time, so the Hash(or ObjectId) calculated with the binary will be different.

Therefore, we need to sort it in a fixed order. It will only affect binary results, the usage and features of the object will be same as itself.

For example:

let obj_origin: ObjectType = ...;
let obj_origin_buf = obj_origin.raw_encode(...);
let obj_decoded = ObjectType::raw_decode(obj_orgin_buf);
let obj_decoded_buf = obj_decoded.raw_encode(...);

assert_eq!(obj_decoded_buf, obj_origin_buf, "the encode buffer must be same no matter how many times it is encoded or decoded");

let obj_origin_vec = obj_origin.iter().collect::<Vec<_>>::();
let obj_decoded_vec = obj_decoded.iter().collect::<Vec<_>>::();

// There are maybe some differences between `obj_origin_vec` and `obj_decoded_vec`. It's the features of the `ObjectType`.

lizhihongTest · 2023-05-24T04:12:11Z

@streetycat This problem is because I use protobuf to implement NameObject, but what you optimize is caused by the codec sorting problem in raw form. CYFS official recommendation for DEC APP development is to implement Object in the form of protobuf. This form does not seem to be well compatible with data in HashSet/HashMap format. Developers can be forced to use BTreeMap/BTreeSet data in official documents.

streetycat · 2023-05-24T07:17:04Z

@streetycat This problem is because I use protobuf to implement NameObject, but what you optimize is caused by the codec sorting problem in raw form. CYFS official recommendation for DEC APP development is to implement Object in the form of protobuf. This form does not seem to be well compatible with data in HashSet/HashMap format. Developers can be forced to use BTreeMap/BTreeSet data in official documents.

Protobuf is recommended for its good scalability. But it is independent of the specific field type, and the type of each field is immutable.

Actually, for Vec/HashMap/HashSet/BTreeMap/BTreeSet we don't care about their types during the coding process, we know that they are containers of an encodable type, which is sufficient.

In ProtoBuf3 there are 2 container types:

repeated, for Array<u32>:

message MsgName {
    reqpeated uint32 field = 1;
}

Map, for Map<uint32, String>:

message MsgName {
    map<uint32, string> field = 1;
}

But the Map in Protobuf is unordered, so we can only select the repeated as container for Object, but we must order the elements in the container ourself for encoding. As you have do it in your test case for HashSet, but you have not do it for HashMap, so the ObjectId is changed after it's decoded from the encoded buffer.

As I mentioned earlier, we can add or remove field in the Protobuf, but we cannot modify the field type in 'Protobuf' unless the type of this field is explicitly defined as another 'Protobuf' type:

message FieldTypeName {
    uint32 field1 = 1;
    string field2 = 2;
}

message MsgName {
    FieldTypeName mutable_field_type = 1; // but the container is not a `Message` in `Protobuf`.
}

So how to encode each fields is not important.

Therefore, we can also encode each fields as a buffer, and combine all fields into Protobuf:

message MsgName {
    bytes field = 1; // any type
}

And, we can encode the container field to a binary buffer:

let container: HashSet = ...;
container.to_vec();

let container: HashMap = ...;
container.raw_encode(...);

streetycat added a commit to streetycat/CYFS that referenced this issue May 8, 2023

Issue buckyos#256: Stable sort for HashSet

1dd34c7

streetycat added the bug Something isn't working label May 8, 2023

streetycat self-assigned this May 8, 2023

lurenpluto added Object Object design, codec and usage cyfs-base Functions and components in cyfs-base project Codec Encode & Decode for the Object labels May 8, 2023

lurenpluto modified the milestones: Restore Service and Dynamic permission Release, GC-supported Release May 9, 2023

lurenpluto mentioned this issue May 10, 2023

Issue #199: Put the closure in heap to avoid the stack overflowed in Debug #200

Closed

streetycat added a commit to streetycat/CYFS that referenced this issue May 12, 2023

Issue buckyos#256: Stable sort for HashSet

b5e461b

streetycat added a commit to streetycat/CYFS that referenced this issue May 12, 2023

Issue buckyos#256: Stable sort for HashSet

77ffd19

lurenpluto pushed a commit that referenced this issue May 12, 2023

Issue #256: Stable sort for HashSet

d5e5930

lurenpluto modified the milestones: GC-supported Release, Group-supported Release May 13, 2023

lizhihongTest mentioned this issue May 15, 2023

Test schedule for 84 Release #268

Open

3 tasks

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Stable sort for HashSet #256

Stable sort for HashSet #256

streetycat commented May 8, 2023

lizhihongTest commented May 23, 2023 •

edited

Loading

streetycat commented May 23, 2023

lizhihongTest commented May 24, 2023

streetycat commented May 24, 2023

Stable sort for HashSet #256

Stable sort for HashSet #256

Comments

streetycat commented May 8, 2023

Discussed in #253

lizhihongTest commented May 23, 2023 • edited Loading

streetycat commented May 23, 2023

lizhihongTest commented May 24, 2023

streetycat commented May 24, 2023

lizhihongTest commented May 23, 2023 •

edited

Loading