Stable sort for HashSet

streetycat commented 1 year ago

Discussed in https://github.com/buckyos/CYFS/discussions/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](https://github.com/buckyos/CYFS/blob/main/src/component/cyfs-base/src/codec/raw/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.

lizhihongTest commented 1 year ago

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

streetycat commented 1 year ago

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 commented 1 year ago

@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 commented 1 year ago

@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(...);

buckyos / CYFS

Stable sort for HashSet #256

Discussed in https://github.com/buckyos/CYFS/discussions/253