Repository: CosmWasm/cosmwasm
Pull request #991 (2021-07-05 18:13:44)

Clarify MockApi::canonical_length code
This aims to make clear that the number of shuffles and the value of canonical_length need to work hand-in-hand. Given the complexity behind that, it makes no sense to allow devs to manually set `canonical_length`.


Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 9ed9ea481..03ee47b30 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -12,6 +12,8 @@ and this project adheres to
   `Into<String>` rather than `ToString`.
 - cosmwasm-std, cosmwasm-vm, cosmwasm-storage: The `iterator` feature is now
   enabled by default.
+- cosmwasm-std: Make `MockApi::canonical_length` private.
+- cosmwasm-vm: Make `MockApi::canonical_length` private.
 
 ## [0.15.0] - 2021-06-24
 
diff --git a/packages/std/src/mock.rs b/packages/std/src/mock.rs
index cf076fe3c..2a34126b0 100644
--- a/packages/std/src/mock.rs
+++ b/packages/std/src/mock.rs
@@ -55,6 +55,14 @@ pub fn mock_dependencies_with_balances(
 // We can later make simplifications here if needed
 pub type MockStorage = MemoryStorage;
 
+/// Length of canonical addresses created with this API. Contracts should not make any assumtions
+/// what this value is.
+/// The value here must be restorable with `SHUFFLES_ENCODE` + `SHUFFLES_DECODE` in-shuffles.
+const CANONICAL_LENGTH: usize = 24;
+
+const SHUFFLES_ENCODE: usize = 18;
+const SHUFFLES_DECODE: usize = 2;
+
 // MockPrecompiles zero pads all human addresses to make them fit the canonical_length
 // it trims off zeros for the reverse operation.
 // not really smart, but allows us to see a difference (and consistent length for canonical adddresses)
@@ -62,13 +70,13 @@ pub type MockStorage = MemoryStorage;
 pub struct MockApi {
     /// Length of canonical addresses created with this API. Contracts should not make any assumtions
     /// what this value is.
-    pub canonical_length: usize,
+    canonical_length: usize,
 }
 
 impl Default for MockApi {
     fn default() -> Self {
         MockApi {
-            canonical_length: 24,
+            canonical_length: CANONICAL_LENGTH,
         }
     }
 }
@@ -100,7 +108,7 @@ impl Api for MockApi {
         // the most obvious structure (https://github.com/CosmWasm/cosmwasm/issues/552)
         let rotate_by = digit_sum(&out) % self.canonical_length;
         out.rotate_left(rotate_by);
-        for _ in 0..18 {
+        for _ in 0..SHUFFLES_ENCODE {
             out = riffle_shuffle(&out);
         }
         Ok(out.into())
@@ -115,7 +123,7 @@ impl Api for MockApi {
 
         let mut tmp: Vec<u8> = canonical.clone().into();
         // Shuffle two more times which restored the original value (24 elements are back to original after 20 rounds)
-        for _ in 0..2 {
+        for _ in 0..SHUFFLES_DECODE {
             tmp = riffle_shuffle(&tmp);
         }
         // Rotate back
@@ -508,6 +516,49 @@ impl StakingQuerier {
 ///
 /// https://en.wikipedia.org/wiki/Riffle_shuffle_permutation#Perfect_shuffles
 /// https://en.wikipedia.org/wiki/In_shuffle
+///
+/// The number of shuffles required to restore the original order are listed in
+/// https://oeis.org/A002326, e.g.:
+///
+/// ```ignore
+/// 2: 2
+/// 4: 4
+/// 6: 3
+/// 8: 6
+/// 10: 10
+/// 12: 12
+/// 14: 4
+/// 16: 8
+/// 18: 18
+/// 20: 6
+/// 22: 11
+/// 24: 20
+/// 26: 18
+/// 28: 28
+/// 30: 5
+/// 32: 10
+/// 34: 12
+/// 36: 36
+/// 38: 12
+/// 40: 20
+/// 42: 14
+/// 44: 12
+/// 46: 23
+/// 48: 21
+/// 50: 8
+/// 52: 52
+/// 54: 20
+/// 56: 18
+/// 58: 58
+/// 60: 60
+/// 62: 6
+/// 64: 12
+/// 66: 66
+/// 68: 22
+/// 70: 35
+/// 72: 9
+/// 74: 20
+/// ```
 pub fn riffle_shuffle<T: Clone>(input: &[T]) -> Vec<T> {
     assert!(
         input.len() % 2 == 0,
diff --git a/packages/vm/src/imports.rs b/packages/vm/src/imports.rs
index 45fcd1c98..84c0fbfa7 100644
--- a/packages/vm/src/imports.rs
+++ b/packages/vm/src/imports.rs
@@ -1021,7 +1021,7 @@ mod tests {
         let api = MockApi::default();
 
         let source_ptr = write_data(&env, b"foo");
-        let dest_ptr = create_empty(&mut instance, api.canonical_length as u32);
+        let dest_ptr = create_empty(&mut instance, api.canonical_length() as u32);
 
         leave_default_data(&env);
 
@@ -1029,7 +1029,7 @@ mod tests {
         let res = do_addr_canonicalize(&env, source_ptr, dest_ptr).unwrap();
         assert_eq!(res, 0);
         let data = force_read(&env, dest_ptr);
-        assert_eq!(data.len(), api.canonical_length);
+        assert_eq!(data.len(), api.canonical_length());
     }
 
     #[test]
@@ -1125,7 +1125,7 @@ mod tests {
                 ..
             } => {
                 assert_eq!(size, 7);
-                assert_eq!(required, api.canonical_length);
+                assert_eq!(required, api.canonical_length());
             }
             err => panic!("Incorrect error returned: {:?}", err),
         }
@@ -1137,7 +1137,7 @@ mod tests {
         let (env, mut instance) = make_instance(api);
         let api = MockApi::default();
 
-        let source_data = vec![0x22; api.canonical_length];
+        let source_data = vec![0x22; api.canonical_length()];
         let source_ptr = write_data(&env, &source_data);
         let dest_ptr = create_empty(&mut instance, 50);
 
@@ -1216,7 +1216,7 @@ mod tests {
         let (env, mut instance) = make_instance(api);
         let api = MockApi::default();
 
-        let source_data = vec![0x22; api.canonical_length];
+        let source_data = vec![0x22; api.canonical_length()];
         let source_ptr = write_data(&env, &source_data);
         let dest_ptr = create_empty(&mut instance, 2);
 
@@ -1229,7 +1229,7 @@ mod tests {
                 ..
             } => {
                 assert_eq!(size, 2);
-                assert_eq!(required, api.canonical_length);
+                assert_eq!(required, api.canonical_length());
             }
             err => panic!("Incorrect error returned: {:?}", err),
         }


Test patch:
diff --git a/packages/vm/src/testing/mock.rs b/packages/vm/src/testing/mock.rs
index d0d8f85d5..8966417f2 100644
--- a/packages/vm/src/testing/mock.rs
+++ b/packages/vm/src/testing/mock.rs
@@ -31,6 +31,14 @@ pub fn mock_backend_with_balances(
     }
 }
 
+/// Length of canonical addresses created with this API. Contracts should not make any assumtions
+/// what this value is.
+/// The value here must be restorable with `SHUFFLES_ENCODE` + `SHUFFLES_DECODE` in-shuffles.
+const CANONICAL_LENGTH: usize = 24;
+
+const SHUFFLES_ENCODE: usize = 18;
+const SHUFFLES_DECODE: usize = 2;
+
 /// Zero-pads all human addresses to make them fit the canonical_length and
 /// trims off zeros for the reverse operation.
 /// This is not really smart, but allows us to see a difference (and consistent length for canonical adddresses).
@@ -38,12 +46,17 @@ pub fn mock_backend_with_balances(
 pub struct MockApi {
     /// Length of canonical addresses created with this API. Contracts should not make any assumtions
     /// what this value is.
-    pub canonical_length: usize,
+    canonical_length: usize,
     /// When set, all calls to the API fail with BackendError::Unknown containing this message
     backend_error: Option<&'static str>,
 }
 
 impl MockApi {
+    /// Read-only getter for `canonical_length`, which must not be changed by the caller.
+    pub fn canonical_length(&self) -> usize {
+        self.canonical_length
+    }
+
     pub fn new_failing(backend_error: &'static str) -> Self {
         MockApi {
             backend_error: Some(backend_error),
@@ -55,7 +68,7 @@ impl MockApi {
 impl Default for MockApi {
     fn default() -> Self {
         MockApi {
-            canonical_length: 24,
+            canonical_length: CANONICAL_LENGTH,
             backend_error: None,
         }
     }
@@ -94,7 +107,7 @@ impl BackendApi for MockApi {
         // the most obvious structure (https://github.com/CosmWasm/cosmwasm/issues/552)
         let rotate_by = digit_sum(&out) % self.canonical_length;
         out.rotate_left(rotate_by);
-        for _ in 0..18 {
+        for _ in 0..SHUFFLES_ENCODE {
             out = riffle_shuffle(&out);
         }
         (Ok(out), gas_info)
@@ -118,7 +131,7 @@ impl BackendApi for MockApi {
 
         let mut tmp: Vec<u8> = canonical.into();
         // Shuffle two more times which restored the original value (24 elements are back to original after 20 rounds)
-        for _ in 0..2 {
+        for _ in 0..SHUFFLES_DECODE {
             tmp = riffle_shuffle(&tmp);
         }
         // Rotate back