What is the encoding order of Map and Set elements?

[streetycat]

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.

[lurenpluto]

The stability of the container encoding problem

To be precise, object codec to container encoding, are converted to an array after encoding, so after conversion to an array involves the issue of element order

BTreeMap/BTreeSet itself is traversed in order, sorting depends on the corresponding Ord trait design, custom Object can design their own Ord trait impls, as long as the algorithm to ensure compliance with the container Ord

The elements inside the HashMap/HashSet do not need to support Ord trait, but for the need of stable coding, the default implementation of RawCodec restricts the need to support Ord this trait:

CYFS/src/component/cyfs-base/src/codec/raw/raw_types.rs

Lines 784 to 792 in c7a777d

	impl<K: RawEncode + std::cmp::Ord + std::hash::Hash, V: RawEncode> RawEncode for HashMap<K, V> {
	fn raw_measure(&self, purpose: &Option<RawEncodePurpose>) -> BuckyResult<usize> {
	let ulen = USize(self.len());
	let mut size = ulen.raw_measure(purpose).unwrap();
	for (key, value) in self {
	size += key.raw_measure(purpose)? + value.raw_measure(purpose)?;
	}
	Ok(size)
	}

So the internal sorting based on the elements Ord, now it seems a little strange, if the user's HashMap element type does not support Ord trait, then it will not be able to use the default sort and RawCodec impls, and the user may not need a stable sort itself, and there is a performance waste here itself

HashSet this one should be missed, according to the principle of consistency, should be consistent with the HashMap

Design principles

I think this we should have the following design principles

1. If you need stable sorting and rely on RawCodec's default codec implementation, then please use BTreeMap/BTreeSet
2. If you don't need stable sorting, you can also choose HashMap/HashSet instead
3. If you want to use the implementation of HashMap/HashSet and also want to achieve stable sorting, then please implement the codec of the stable version of the corresponding data structure by yourself.

Introduce the label

Therefore, there should be a label "stable encoding or not" to identify the default data type supported by cyfs-base, so that you can choose the stable or non-stable version of the data structure according to your needs when designing the data structure for object selection.

[streetycat]

I think we should only define a definite arrangement order, we just need to ensure that the encoded content of the same content is exactly the same. For the user, each element is stored in the container after decoding, and how the elements are arranged in it is not important.

[lurenpluto]

I think we should only define a definite arrangement order, we just need to ensure that the encoded content of the same content is exactly the same. For the user, each element is stored in the container after decoding, and how the elements are arranged in it is not important.

I think there are two points to consider

1. The user-defined encoding of the elements, does not necessarily support sorting, that is, elements does not support Ord trait, for this case there is no way to follow our "codec specification" as objectfields
2. Object's body encoding, can not need to be stable (except for the need to sign, otherwise it may lead to failure of verification), such as just in the local NOC storage

However, simply specifying the order of encoding can avoid some potential problems