Repository: paritytech/ink
Pull request #836 (2021-07-01 14:43:21)

Implement binary_search for `collections::Vec`
This ports the binary_search implementation from `core`. I've removed the use of `get_unchecked` as that is not present in `LazyIndexMap`.  There's 2 tests added to verify that it works with a full vector and an empty vector. 

related to #834 

KaiserKarel: I think that the spellcheck failure is a false alarm, as the documentation is taken from core.
KaiserKarel: > All in all LGTM so far. Will take another more detailed look into the actual implementation. We could use a bit more tests for this to cover some edge cases. Maybe pull some tests over from the `core` implementation?

I originally was unable to find them, but now realize they resided in a different crate. I've added the core tests as well now, and removed my own tests.
KaiserKarel: Also @Robbepop, sinc binary_search and partition are quite closely related, should I add that one too? Or perhaps create another issue and another PR?
Robbepop: > Also @Robbepop, sinc binary_search and partition are quite closely related, should I add that one too? Or perhaps create another issue and another PR?

Another API should be done in another PR. :)
KaiserKarel: > Doc comments for the functions need to be adjusted to fit ink! instead of Rust standard library. It currently contains dead links and invalid docs or docs that just does not fit. Please rework docs in this regard and we are good to go. Also we might be in need of a `sort` function for `storage::Vec` in the near future. Although sorting efficiently will be a major endavour and might probably be a bad idea.

For sorting it would probably be for efficient to read the storage vec into a normal vec, sort that, and write the result back? That should minimize the amount of gas fees I think.
Robbepop: > For sorting it would probably be for efficient to read the storage vec into a normal vec, sort that, and write the result back? That should minimize the amount of gas fees I think.

Maybe yes, however due to caching in the `LazyIndexMap` layer this might not be needed. Benchmarks are required here instead of assumptions about performance.
KaiserKarel: Alright, so a PR involving adding sorting would require benchmarks of the two competing implementations?
KaiserKarel: > We should leave the first part of the comment ("it is ok to break...") here, it's just the crater part that's not relevant

Actually now that I think about it, wasn't binary_search implementation specific behaviour the reason that polkadot had an outage? Perhaps it is not okay for this test to break, as contracts may rely on the specific behaviour? 
HCastano: > Actually now that I think about it, wasn't binary_search implementation specific behaviour the reason that polkadot had an outage? Perhaps it is not okay for this test to break, as contracts may rely on the specific behaviour?

Umm kinda. The problem with Polkadot was that the Wasm runtime and native runtime had different sorting behaviours which caused a failure in consensus. You can read more about it [here](https://polkadot.network/a-polkadot-postmortem-24-05-2021/). 

In our case once a contract is deployed that's the only instance of it. There is no need for a network of people with potentially different versions of the contract to come to consensus on the behaviour - they only need to run what's already on chain.

Whether or not we want to make any guarantees around sorting behaviour is an interesting topic. I'm not sure what the answer is here though. @cmichi @Robbepop what do you guys think?

Patch:
diff --git a/.config/cargo_spellcheck.dic b/.config/cargo_spellcheck.dic
index d001711c7c..e93a999382 100644
--- a/.config/cargo_spellcheck.dic
+++ b/.config/cargo_spellcheck.dic
@@ -12,6 +12,7 @@ Polkadot
 RPC
 SHA
 UI
+URI
 Wasm
 Wasm32
 WebAssembly
@@ -20,6 +21,7 @@ bitvector
 bitwise
 callee
 codegen
+comparator
 const
 crypto
 cryptographic
@@ -57,6 +59,9 @@ unordered
 untyped
 validator
 variadic
+metadata
+timestamp
+prepend
 
 Django/S
 IP/S
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml
index 14b7b0aa03..2ec0289f38 100644
--- a/.gitlab-ci.yml
+++ b/.gitlab-ci.yml
@@ -9,6 +9,7 @@ stages:
   - check
   - workspace
   - examples
+  - ink-waterfall
   - fuzz
   - publish
 
@@ -38,15 +39,15 @@ workflow:
     paths:
       - artifacts/
 
-.docker-env:                       &docker-env
-  image:                           "${CI_IMAGE}"
-  before_script:
-    - cargo -vV
-    - rustc -vV
-    - rustup show
-    - bash --version
-    - ./scripts/pre_cache.sh
-    - sccache -s
+.rust-info-script:                 &rust-info-script
+  - rustup show
+  - cargo --version
+  - rustup +nightly show
+  - cargo +nightly --version
+  - bash --version
+  - sccache -s
+
+.test-refs:                        &test-refs
   rules:
     - if: $CI_PIPELINE_SOURCE == "web"
     - if: $CI_PIPELINE_SOURCE == "schedule"
@@ -54,6 +55,13 @@ workflow:
     - if: $CI_COMMIT_REF_NAME == "tags"
     - if: $CI_COMMIT_REF_NAME =~ /^[0-9]+$/                         # PRs
     - if: $CI_COMMIT_REF_NAME =~ /^v[0-9]+\.[0-9]+.*$/              # i.e. v1.0, v2.1rc1
+
+.docker-env:                       &docker-env
+  image:                           "${CI_IMAGE}"
+  before_script:
+    - *rust-info-script
+    - ./scripts/.ci/pre_cache.sh
+    - sccache -s
   interruptible:                   true
   retry:
     max: 2
@@ -64,12 +72,23 @@ workflow:
   tags:
     - linux-docker
 
+.kubernetes-env:                   &kubernetes-env
+  interruptible:                   true
+  retry:
+    max: 2
+    when:
+      - runner_system_failure
+      - unknown_failure
+      - api_failure
+  tags:
+    - kubernetes-parity-build
 
 #### stage:                        check
 
 check-std:
   stage:                           check
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - for crate in ${ALL_CRATES}; do
         cargo check --verbose --all-features --manifest-path crates/${crate}/Cargo.toml;
@@ -78,6 +97,7 @@ check-std:
 check-wasm:
   stage:                           check
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - for crate in ${ALSO_WASM_CRATES}; do
         cargo check --verbose --no-default-features --target wasm32-unknown-unknown --manifest-path crates/${crate}/Cargo.toml;
@@ -89,6 +109,7 @@ check-wasm:
 build-std:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-std
       artifacts:                   false
@@ -100,6 +121,7 @@ build-std:
 build-wasm:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-wasm
       artifacts:                   false
@@ -111,6 +133,7 @@ build-wasm:
 test:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-std
       artifacts:                   false
@@ -133,6 +156,7 @@ test:
 docs:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   variables:
     RUSTDOCFLAGS: -Dwarnings
   artifacts:
@@ -150,20 +174,22 @@ docs:
     - mv ${CARGO_TARGET_DIR}/doc ./crate-docs
 
 spellcheck:
-    stage:                           workspace
-    <<:                              *docker-env
-    script:
-        - cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1
-        - for example in examples/*/; do
-            cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1 ${example};
-          done
-        - for contract in ${DELEGATOR_SUBCONTRACTS}; do
-            cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1 examples/delegator/${contract}/;
-          done
+  stage:                           workspace
+  <<:                              *docker-env
+  <<:                              *test-refs
+  script:
+    - cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1
+    - for example in examples/*/; do
+        cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1 ${example};
+      done
+    - for contract in ${DELEGATOR_SUBCONTRACTS}; do
+        cargo spellcheck check -vvv --cfg=.config/cargo_spellcheck.toml --checkers hunspell --code 1 examples/delegator/${contract}/;
+      done
 
 codecov:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-std
       artifacts:                   false
@@ -178,10 +204,7 @@ codecov:
     # produces better results for Rust codebases in general. However, unlike `grcov` it requires
     # running docker with `--security-opt seccomp=unconfined` which is why we use `grcov` instead.
   before_script:
-    - cargo -vV
-    - rustc -vV
-    - rustup show
-    - bash --version
+    - *rust-info-script
     - unset "CARGO_TARGET_DIR"
     - cargo clean
   script:
@@ -211,6 +234,7 @@ codecov:
 clippy-std:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-std
       artifacts:                   false
@@ -222,6 +246,7 @@ clippy-std:
 clippy-wasm:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         check-wasm
       artifacts:                   false
@@ -233,9 +258,9 @@ clippy-wasm:
 fmt:
   stage:                           workspace
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - cargo fmt --verbose --all -- --check
-
     # For the UI tests we need to disable the license check
     - cargo fmt --verbose --all -- --check --config=license_template_path="" crates/lang/macro/tests/ui/{pass,fail}/*.rs
 
@@ -245,6 +270,7 @@ fmt:
 examples-test:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         clippy-std
       artifacts:                   false
@@ -259,6 +285,7 @@ examples-test:
 examples-test-experimental-engine:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         clippy-std
       artifacts:                   false
@@ -266,12 +293,14 @@ examples-test-experimental-engine:
     # We test only the examples for which the tests have already been migrated to
     # use the experimental engine.
     - cargo test --no-default-features --features std, ink-experimental-engine --verbose --manifest-path examples/erc20/Cargo.toml
+    - cargo test --no-default-features --features std, ink-experimental-engine --verbose --manifest-path examples/erc1155/Cargo.toml
     - cargo test --no-default-features --features std, ink-experimental-engine --verbose --manifest-path examples/contract-terminate/Cargo.toml
     - cargo test --no-default-features --features std, ink-experimental-engine --verbose --manifest-path examples/contract-transfer/Cargo.toml
 
 examples-fmt:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - for example in examples/*/; do
         cargo fmt --verbose --manifest-path ${example}/Cargo.toml -- --check;
@@ -283,6 +312,7 @@ examples-fmt:
 examples-clippy-std:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
     - job:                         clippy-std
       artifacts:                   false
@@ -297,6 +327,7 @@ examples-clippy-std:
 examples-clippy-wasm:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - for example in examples/*/; do
         cargo clippy --verbose --manifest-path ${example}/Cargo.toml --no-default-features --target wasm32-unknown-unknown -- -D warnings;
@@ -308,6 +339,7 @@ examples-clippy-wasm:
 examples-contract-build:
   stage:                           examples
   <<:                              *docker-env
+  <<:                              *test-refs
   script:
     - cargo contract -V
     - for example in examples/*/; do
@@ -322,47 +354,69 @@ examples-contract-build:
       done
 
 examples-contract-build-delegator:
-    stage:                           examples
-    <<:                              *docker-env
+    stage:                         examples
+    <<:                            *docker-env
+    <<:                            *test-refs
     script:
         - cargo contract -V
         - cd examples/delegator/ && ./build-all.sh
 
 examples-docs:
-    stage:                           examples
-    <<:                              *docker-env
-    variables:
-        RUSTDOCFLAGS: -Dwarnings
-    script:
-        # `--document-private-items` needs to be in here because currently our contract macro
-        # puts the contract functions in a private module.
-        # Once https://github.com/paritytech/ink/issues/336 has been implemented we can get rid
-        # of this flag.
-        - for example in examples/*/; do
-            cargo doc --manifest-path ${example}/Cargo.toml --document-private-items --verbose --no-deps;
-          done
-        - for contract in ${DELEGATOR_SUBCONTRACTS}; do
-            cargo doc --manifest-path examples/delegator/${contract}/Cargo.toml --document-private-items --verbose --no-deps;
-          done
+  stage:                           examples
+  <<:                              *docker-env
+  <<:                              *test-refs
+  variables:
+    RUSTDOCFLAGS: -Dwarnings
+  script:
+    # `--document-private-items` needs to be in here because currently our contract macro
+    # puts the contract functions in a private module.
+    # Once https://github.com/paritytech/ink/issues/336 has been implemented we can get rid
+    # of this flag.
+    - for example in examples/*/; do
+        cargo doc --manifest-path ${example}/Cargo.toml --document-private-items --verbose --no-deps;
+      done
+    - for contract in ${DELEGATOR_SUBCONTRACTS}; do
+        cargo doc --manifest-path examples/delegator/${contract}/Cargo.toml --document-private-items --verbose --no-deps;
+      done
+
+
+#### stage:                        ink-waterfall
+
+ink-waterfall:
+  stage:                           ink-waterfall
+  image:                           paritytech/tools:latest
+  <<:                              *kubernetes-env
+  <<:                              *test-refs
+  variables:
+    TRGR_PROJECT:                  ${CI_PROJECT_NAME}
+    TRGR_REF:                      ${CI_COMMIT_REF_NAME}
+    # The `ink-waterfall` project id in GitLab
+    DWNSTRM_ID:                    409
+  script:
+    - ./scripts/.ci/trigger_pipeline.sh
+  allow_failure:                   true
+
 
 #### stage:                        publish
 
 publish-docs:
   stage:                           publish
   <<:                              *docker-env
+  <<:                              *test-refs
   needs:
-    - job:                       docs
-      artifacts:                 true
+    - job:                         docs
+      artifacts:                   true
   variables:
-    GIT_DEPTH:                   100
+    GIT_DEPTH:                     100
   rules:
     - if: $CI_PIPELINE_SOURCE == "web"
     - if: $CI_PIPELINE_SOURCE == "schedule"
     - if: $CI_COMMIT_REF_NAME == "master"
     - if: $CI_COMMIT_REF_NAME == "tags"
   # need to overwrite `before_script` from `*docker-env` here,
-  # this branch does not have a `./scripts/pre_cache.sh`
+  # this branch does not have a `./scripts/.ci/pre_cache.sh`
   before_script:
+    - *rust-info-script
     - unset CARGO_TARGET_DIR
   script:
     - rm -rf /tmp/*
@@ -400,36 +454,37 @@ publish-docs:
 #### stage:                        fuzz
 
 fuzz-tests:
-    stage:                           fuzz
-    <<:                              *docker-env
-    variables:
-        # The QUICKCHECK_TESTS default is 100
-        QUICKCHECK_TESTS:            20000
-    rules:
-        - if: $CI_PIPELINE_SOURCE == "schedule"
-        - if: $CI_COMMIT_REF_NAME == "master"
-    script:
-        # We fuzz-test only crates which possess the `ink-fuzz-tests` feature
-        - all_tests_passed=0
-        - for crate in ${ALL_CRATES}; do
-            if grep "ink-fuzz-tests =" crates/${crate}/Cargo.toml;
-            then
-                cargo test --verbose --features ink-fuzz-tests --manifest-path crates/${crate}/Cargo.toml --no-fail-fast -- fuzz_ || exit_code=$?;
-                all_tests_passed=$(( all_tests_passed | exit_code ));
-            fi
-          done
-        - if [ $all_tests_passed -eq 0 ]; then exit 0; fi
-        - |
-             curl -X "POST" "https://api.github.com/repos/paritytech/ink/issues" \
-                -H "Cookie: logged_in=no" \
-                -H "Authorization: token ${GITHUB_TOKEN}" \
-                -H "Content-Type: application/json; charset=utf-8" \
-                -d $'{
-                    "title": "[ci] Failing fuzz tests on master ('"$( date +"%d %b %Y" )"')",
-                    "body": "The CI job ['"${CI_JOB_ID}"']('"${CI_JOB_URL}"') just failed.\n\nThe offending commit is ['"${CI_COMMIT_TITLE}"'](https://github.com/paritytech/ink/commit/'"${CI_COMMIT_SHA}"').",
-                    "assignees": [],
-                    "labels": [
-                        "P-high"
-                    ]
-                }'
-        - exit ${all_tests_passed}
+  stage:                           fuzz
+  <<:                              *docker-env
+  <<:                              *test-refs
+  variables:
+    # The QUICKCHECK_TESTS default is 100
+    QUICKCHECK_TESTS:              20000
+  rules:
+    - if: $CI_PIPELINE_SOURCE == "schedule"
+    - if: $CI_COMMIT_REF_NAME == "master"
+  script:
+    # We fuzz-test only crates which possess the `ink-fuzz-tests` feature
+    - all_tests_passed=0
+    - for crate in ${ALL_CRATES}; do
+        if grep "ink-fuzz-tests =" crates/${crate}/Cargo.toml;
+        then
+          cargo test --verbose --features ink-fuzz-tests --manifest-path crates/${crate}/Cargo.toml --no-fail-fast -- fuzz_ || exit_code=$?;
+          all_tests_passed=$(( all_tests_passed | exit_code ));
+        fi
+      done
+    - if [ $all_tests_passed -eq 0 ]; then exit 0; fi
+    - |
+      curl -X "POST" "https://api.github.com/repos/paritytech/ink/issues" \
+        -H "Cookie: logged_in=no" \
+        -H "Authorization: token ${GITHUB_TOKEN}" \
+        -H "Content-Type: application/json; charset=utf-8" \
+        -d $'{
+            "title": "[ci] Failing fuzz tests on master ('"$( date +"%d %b %Y" )"')",
+            "body": "The CI job ['"${CI_JOB_ID}"']('"${CI_JOB_URL}"') just failed.\n\nThe offending commit is ['"${CI_COMMIT_TITLE}"'](https://github.com/paritytech/ink/commit/'"${CI_COMMIT_SHA}"').",
+            "assignees": [],
+            "labels": [
+                "P-high"
+            ]
+        }'
+    - exit ${all_tests_passed}
diff --git a/README.md b/README.md
index 00729f23b2..d34e57aaa0 100644
--- a/README.md
+++ b/README.md
@@ -25,7 +25,7 @@
 [k1]: https://img.shields.io/badge/matrix-chat-brightgreen.svg?style=flat
 [k2]: https://riot.im/app/#/room/#ink:matrix.parity.io
 [l1]: https://img.shields.io/discord/722223075629727774?style=flat-square&label=discord
-[l2]: https://discord.gg/j2DKRRbSJr
+[l2]: https://discord.com/invite/wGUDt2p
 
 > <img src="./.images/ink-squid.svg" alt="squink, the ink! mascot" style="vertical-align: middle" align="left" height="60" />ink! is an [eDSL](https://wiki.haskell.org/Embedded_domain_specific_language) to write smart contracts in Rust for blockchains built on the [Substrate](https://github.com/paritytech/substrate) framework. ink! contracts are compiled to WebAssembly.
 
@@ -38,7 +38,8 @@
 </div>
 
 More relevant links:
-* Talk to us on [Element][k2] or [Discord][l2]
+* Talk to us on [Element][k2] or in [Discord][l2]
+  on the [`ink_smart-contracts`](https://discord.com/channels/722223075629727774/765280480609828864) channel
 * [`cargo-contract`](https://github.com/paritytech/cargo-contract) ‒ CLI tool for ink! contracts
 * [Canvas UI](https://paritytech.github.io/canvas-ui/#/upload) ‒ Frontend for contract deployment and interaction
 * [Canvas Node](https://github.com/paritytech/canvas-node) ‒ Simple Substrate blockchain which includes smart contract functionality
diff --git a/crates/env/src/types.rs b/crates/env/src/types.rs
index 7b358ffd68..12fd6e53b5 100644
--- a/crates/env/src/types.rs
+++ b/crates/env/src/types.rs
@@ -77,7 +77,7 @@ pub trait Environment {
         + AsRef<[u8]>
         + AsMut<[u8]>;
 
-    /// The type of timestamps.
+    /// The type of a timestamp.
     type Timestamp: 'static
         + scale::Codec
         + Copy
diff --git a/crates/lang/ir/src/ir/config.rs b/crates/lang/ir/src/ir/config.rs
index 52cd4d80cc..a6fdb6449c 100644
--- a/crates/lang/ir/src/ir/config.rs
+++ b/crates/lang/ir/src/ir/config.rs
@@ -48,12 +48,12 @@ where
 {
     format_err!(
         snd.span(),
-        "encountered duplicate ink! `{}` config argument",
+        "encountered duplicate ink! `{}` configuration argument",
         name,
     )
     .into_combine(format_err!(
         fst.span(),
-        "first `{}` config argument here",
+        "first `{}` configuration argument here",
         name
     ))
 }
@@ -170,7 +170,7 @@ impl Default for Environment {
 mod tests {
     use super::*;
 
-    /// Asserts that the given input config attribute argument are converted
+    /// Asserts that the given input configuration attribute argument are converted
     /// into the expected ink! configuration or yields the expected error message.
     fn assert_try_from(
         input: ast::AttributeArgs,
@@ -273,7 +273,7 @@ mod tests {
                 env = ::my::env::Types,
                 env = ::my::other::env::Types,
             },
-            Err("encountered duplicate ink! `env` config argument"),
+            Err("encountered duplicate ink! `env` configuration argument"),
         );
     }
 }
diff --git a/crates/lang/ir/src/ir/item_impl/callable.rs b/crates/lang/ir/src/ir/item_impl/callable.rs
index bd7d88522d..32f3fa2694 100644
--- a/crates/lang/ir/src/ir/item_impl/callable.rs
+++ b/crates/lang/ir/src/ir/item_impl/callable.rs
@@ -417,6 +417,19 @@ pub(super) fn ensure_callable_invariants(
             kind,
         ))
     }
+
+    if let Some(arg) = method_item.sig.inputs.iter().find(|input| {
+        match input {
+            syn::FnArg::Typed(pat) => !matches!(*pat.pat, syn::Pat::Ident(_)),
+            _ => false,
+        }
+    }) {
+        return Err(format_err_spanned!(
+            arg,
+            "ink! {} arguments must have an identifier",
+            kind
+        ))
+    }
     Ok(())
 }
 
diff --git a/crates/storage/src/collections/vec/mod.rs b/crates/storage/src/collections/vec/mod.rs
index 7dc53fa23c..c260cdbe50 100644
--- a/crates/storage/src/collections/vec/mod.rs
+++ b/crates/storage/src/collections/vec/mod.rs
@@ -200,6 +200,182 @@ where
         *self.len += 1;
         self.elems.put(last_index, Some(value));
     }
+
+    /// Binary searches this sorted vector for a given element.
+    ///
+    /// If the value is found then [`Result::Ok`] is returned, containing the
+    /// index of the matching element. If there are multiple matches, then any
+    /// one of the matches could be returned. If the value is not found then
+    /// [`Result::Err`] is returned, containing the index where a matching
+    /// element could be inserted while maintaining sorted order.
+    ///
+    /// See also [`binary_search_by`], [`binary_search_by_key`].
+    ///
+    /// [`binary_search_by`]: Vec::binary_search_by
+    /// [`binary_search_by_key`]: Vec::binary_search_by_key
+    ///
+    /// # Examples
+    ///
+    /// Looks up a series of four elements. The first is found, with a
+    /// uniquely determined position; the second and third are not
+    /// found; the fourth could match any position in `[1, 4]`.
+    ///
+    /// ```
+    /// use ink_storage::Vec as StorageVec;
+    ///
+    /// let s: StorageVec<i32> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
+    ///     .into_iter()
+    ///     .copied()
+    ///     .collect();
+    ///
+    /// assert_eq!(s.binary_search(&13),  Ok(9));
+    /// assert_eq!(s.binary_search(&4),   Err(7));
+    /// assert_eq!(s.binary_search(&100), Err(13));
+    /// let r = s.binary_search(&1);
+    /// assert!(match r { Ok(1..=4) => true, _ => false, });
+    /// ```
+    #[inline]
+    pub fn binary_search(&self, x: &T) -> Result<u32, u32>
+    where
+        T: Ord,
+    {
+        self.binary_search_by(|p| p.cmp(x))
+    }
+
+    /// Binary searches this sorted vector with a comparator function.
+    ///
+    /// The comparator function should implement an order consistent
+    /// with the sort order of the underlying vector, returning an
+    /// order code that indicates whether its argument is `Less`,
+    /// `Equal` or `Greater` the desired target.
+    ///
+    /// If the value is found then [`Result::Ok`] is returned, containing the
+    /// index of the matching element. If there are multiple matches, then any
+    /// one of the matches could be returned. If the value is not found then
+    /// [`Result::Err`] is returned, containing the index where a matching
+    /// element could be inserted while maintaining sorted order.
+    ///
+    /// See also [`binary_search`], [`binary_search_by_key`].
+    ///
+    /// [`binary_search`]: Vec::binary_search
+    /// [`binary_search_by_key`]: Vec::binary_search_by_key
+    ///
+    /// # Examples
+    ///
+    /// Looks up a series of four elements. The first is found, with a
+    /// uniquely determined position; the second and third are not
+    /// found; the fourth could match any position in `[1, 4]`.
+    ///
+    /// ```
+    /// use ink_storage::Vec as StorageVec;
+    ///
+    /// let s: StorageVec<i32> = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
+    ///     .into_iter()
+    ///     .copied()
+    ///     .collect();
+    ///
+    /// let seek = 13;
+    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
+    /// let seek = 4;
+    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
+    /// let seek = 100;
+    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
+    /// let seek = 1;
+    /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
+    /// assert!(match r { Ok(1..=4) => true, _ => false, });
+    /// ```
+    // The binary_search implementation is ported from
+    // https://github.com/rust-lang/rust/blob/c5e344f7747dbd7e7d4b209e3c480deb5979a56f/library/core/src/slice/mod.rs#L2191
+    // and attempts to remain as close to the source as possible.
+    #[inline]
+    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<u32, u32>
+    where
+        F: FnMut(&'a T) -> core::cmp::Ordering,
+    {
+        use core::cmp::Ordering::*;
+
+        let mut size = self.len();
+        let mut left = 0;
+        let mut right = size;
+        while left < right {
+            let mid = left + size / 2;
+
+            // the call is made safe by the following invariants:
+            // - `mid >= 0`
+            // - `mid < size`: `mid` is limited by `[left; right)` bound.
+            let cmp = f(&self[mid]);
+
+            // The reason why we use if/else control flow rather than match
+            // is because match reorders comparison operations, which is perf sensitive.
+            if cmp == Less {
+                left = mid + 1;
+            } else if cmp == Greater {
+                right = mid;
+            } else {
+                return Ok(mid)
+            }
+
+            size = right - left;
+        }
+        Err(left)
+    }
+
+    /// Binary searches this sorted vector with a key extraction function.
+    ///
+    /// If the value is found then [`Result::Ok`] is returned, containing the
+    /// index of the matching element. If there are multiple matches, then any
+    /// one of the matches could be returned. If the value is not found then
+    /// [`Result::Err`] is returned, containing the index where a matching
+    /// element could be inserted while maintaining sorted order.
+    ///
+    /// See also [`binary_search`], [`binary_search_by`].
+    ///
+    /// [`binary_search`]: Vec::binary_search
+    /// [`binary_search_by`]: Vec::binary_search_by
+    ///
+    /// # Examples
+    ///
+    /// Looks up a series of four elements in a vector of pairs sorted by
+    /// their second elements. The first is found, with a uniquely
+    /// determined position; the second and third are not found; the
+    /// fourth could match any position in `[1, 4]`.
+    ///
+    /// ```
+    /// use ink_storage::Vec as StorageVec;
+    ///
+    /// let s: StorageVec<(i32, i32)> = [
+    ///     (0, 0),
+    ///     (2, 1),
+    ///     (4, 1),
+    ///     (5, 1),
+    ///     (3, 1),
+    ///     (1, 2),
+    ///     (2, 3),
+    ///     (4, 5),
+    ///     (5, 8),
+    ///     (3, 13),
+    ///     (1, 21),
+    ///     (2, 34),
+    ///     (4, 55),
+    /// ]
+    /// .into_iter()
+    /// .copied()
+    /// .collect();
+    ///
+    /// assert_eq!(s.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
+    /// assert_eq!(s.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
+    /// assert_eq!(s.binary_search_by_key(&100, |&(a, b)| b), Err(13));
+    /// let r = s.binary_search_by_key(&1, |&(a, b)| b);
+    /// assert!(match r { Ok(1..=4) => true, _ => false, });
+    /// ```
+    #[inline]
+    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<u32, u32>
+    where
+        F: FnMut(&'a T) -> B,
+        B: Ord,
+    {
+        self.binary_search_by(|k| f(k).cmp(b))
+    }
 }
 
 impl<T> Vec<T>
diff --git a/examples/erc1155/.gitignore b/examples/erc1155/.gitignore
new file mode 100644
index 0000000000..bf910de10a
--- /dev/null
+++ b/examples/erc1155/.gitignore
@@ -0,0 +1,9 @@
+# Ignore build artifacts from the local tests sub-crate.
+/target/
+
+# Ignore backup files creates by cargo fmt.
+**/*.rs.bk
+
+# Remove Cargo.lock when creating an executable, leave it for libraries
+# More information here http://doc.crates.io/guide.html#cargotoml-vs-cargolock
+Cargo.lock
\ No newline at end of file
diff --git a/examples/erc1155/Cargo.toml b/examples/erc1155/Cargo.toml
new file mode 100644
index 0000000000..87a0a4abee
--- /dev/null
+++ b/examples/erc1155/Cargo.toml
@@ -0,0 +1,38 @@
+[package]
+name = "erc1155"
+version = "3.0.0-rc3"
+authors = ["Parity Technologies <admin@parity.io>"]
+edition = "2018"
+
+[dependencies]
+ink_primitives = { version = "3.0.0-rc3", path = "../../crates/primitives", default-features = false }
+ink_metadata = { version = "3.0.0-rc3", path = "../../crates/metadata", default-features = false, features = ["derive"], optional = true }
+ink_env = { version = "3.0.0-rc3", path = "../../crates/env", default-features = false, features = ["ink-debug"] }
+ink_storage = { version = "3.0.0-rc3", path = "../../crates/storage", default-features = false }
+ink_lang = { version = "3.0.0-rc3", path = "../../crates/lang", default-features = false }
+ink_prelude = { version = "3.0.0-rc3", path = "../../crates/prelude", default-features = false }
+
+scale = { package = "parity-scale-codec", version = "2.1", default-features = false, features = ["derive"] }
+scale-info = { version = "0.6", default-features = false, features = ["derive"], optional = true }
+
+[lib]
+name = "erc1155"
+path = "lib.rs"
+crate-type = ["cdylib"]
+
+[features]
+default = ["std"]
+std = [
+    "ink_primitives/std",
+    "ink_metadata",
+    "ink_metadata/std",
+    "ink_env/std",
+    "ink_storage/std",
+    "ink_lang/std",
+    "ink_prelude/std",
+    "scale/std",
+    "scale-info",
+    "scale-info/std",
+]
+ink-as-dependency = []
+ink-experimental-engine = ["ink_env/ink-experimental-engine"]
diff --git a/examples/erc1155/lib.rs b/examples/erc1155/lib.rs
new file mode 100644
index 0000000000..7ced21add2
--- /dev/null
+++ b/examples/erc1155/lib.rs
@@ -0,0 +1,827 @@
+// Copyright 2018-2021 Parity Technologies (UK) Ltd.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#![cfg_attr(not(feature = "std"), no_std)]
+
+use ink_env::AccountId;
+use ink_lang as ink;
+use ink_prelude::vec::Vec;
+
+// This is the return value that we expect if a smart contract supports receiving ERC-1155
+// tokens.
+//
+// It is calculated with
+// `bytes4(keccak256("onERC1155Received(address,address,uint256,uint256,bytes)"))`, and corresponds
+// to 0xf23a6e61.
+#[cfg_attr(test, allow(dead_code))]
+const ON_ERC_1155_RECEIVED_SELECTOR: [u8; 4] = [0xF2, 0x3A, 0x6E, 0x61];
+
+// This is the return value that we expect if a smart contract supports batch receiving ERC-1155
+// tokens.
+//
+// It is calculated with
+// `bytes4(keccak256("onERC1155BatchReceived(address,address,uint256[],uint256[],bytes)"))`, and
+// corresponds to 0xbc197c81.
+const _ON_ERC_1155_BATCH_RECEIVED_SELECTOR: [u8; 4] = [0xBC, 0x19, 0x7C, 0x81];
+
+/// A type representing the unique IDs of tokens managed by this contract.
+pub type TokenId = u128;
+
+type Balance = <ink_env::DefaultEnvironment as ink_env::Environment>::Balance;
+
+// The ERC-1155 error types.
+#[derive(Debug, PartialEq, scale::Encode, scale::Decode)]
+#[cfg_attr(feature = "std", derive(scale_info::TypeInfo))]
+pub enum Error {
+    /// This token ID has not yet been created by the contract.
+    UnexistentToken,
+    /// The caller tried to sending tokens to the zero-address (`0x00`).
+    ZeroAddressTransfer,
+    /// The caller is not approved to transfer tokens on behalf of the account.
+    NotApproved,
+    /// The account does not have enough funds to complete the transfer.
+    InsufficientBalance,
+    /// An account does not need to approve themselves to transfer tokens.
+    SelfApproval,
+    /// The number of tokens being transferred does not match the specified number of transfers.
+    BatchTransferMismatch,
+}
+
+// The ERC-1155 result types.
+pub type Result<T> = core::result::Result<T, Error>;
+
+/// Evaluate `$x:expr` and if not true return `Err($y:expr)`.
+///
+/// Used as `ensure!(expression_to_ensure, expression_to_return_on_false)`.
+macro_rules! ensure {
+    ( $condition:expr, $error:expr $(,)? ) => {{
+        if !$condition {
+            return ::core::result::Result::Err(::core::convert::Into::into($error))
+        }
+    }};
+}
+
+/// The interface for an ERC-1155 compliant contract.
+///
+/// The interface is defined here: <https://eips.ethereum.org/EIPS/eip-1155>.
+///
+/// The goal of ERC-1155 is to allow a single deployed contract to manage a variety of assets.
+/// These assets can be fungible, non-fungible, or a combination.
+///
+/// By tracking multiple assets the ERC-1155 standard is able to support batch transfers, which
+/// make it easy to transfer a mix of multiple tokens at once.
+#[ink::trait_definition]
+pub trait Erc1155 {
+    /// Transfer a `value` amount of `token_id` tokens to the `to` account from the `from`
+    /// account.
+    ///
+    /// Note that the call does not have to originate from the `from` account, and may originate
+    /// from any account which is approved to transfer `from`'s tokens.
+    #[ink(message)]
+    fn safe_transfer_from(
+        &mut self,
+        from: AccountId,
+        to: AccountId,
+        token_id: TokenId,
+        value: Balance,
+        data: Vec<u8>,
+    ) -> Result<()>;
+
+    /// Perform a batch transfer of `token_ids` to the `to` account from the `from` account.
+    ///
+    /// The number of `values` specified to be transfer must match the number of `token_ids`,
+    /// otherwise this call will revert.
+    ///
+    /// Note that the call does not have to originate from the `from` account, and may originate
+    /// from any account which is approved to transfer `from`'s tokens.
+    #[ink(message)]
+    fn safe_batch_transfer_from(
+        &mut self,
+        from: AccountId,
+        to: AccountId,
+        token_ids: Vec<TokenId>,
+        values: Vec<Balance>,
+        data: Vec<u8>,
+    ) -> Result<()>;
+
+    /// Query the balance of a specific token for the provided account.
+    #[ink(message)]
+    fn balance_of(&self, owner: AccountId, token_id: TokenId) -> Balance;
+
+    /// Query the balances for a set of tokens for a set of accounts.
+    ///
+    /// E.g use this call if you want to query what Alice and Bob's balances are for Tokens ID 1 and
+    /// ID 2.
+    ///
+    /// This will return all the balances for a given owner before moving on to the next owner. In
+    /// the example above this means that the return value should look like:
+    ///
+    /// [Alice Balance of Token ID 1, Alice Balance of Token ID 2, Bob Balance of Token ID 1, Bob Balance of Token ID 2]
+    #[ink(message)]
+    fn balance_of_batch(
+        &self,
+        owners: Vec<AccountId>,
+        token_ids: Vec<TokenId>,
+    ) -> Vec<Balance>;
+
+    /// Enable or disable a third party, known as an `operator`, to control all tokens on behalf of
+    /// the caller.
+    #[ink(message)]
+    fn set_approval_for_all(&mut self, operator: AccountId, approved: bool)
+        -> Result<()>;
+
+    /// Query if the given `operator` is allowed to control all of `owner`'s tokens.
+    #[ink(message)]
+    fn is_approved_for_all(&self, owner: AccountId, operator: AccountId) -> bool;
+}
+
+/// The interface for an ERC-1155 Token Receiver contract.
+///
+/// The interface is defined here: <https://eips.ethereum.org/EIPS/eip-1155>.
+///
+/// Smart contracts which want to accept token transfers must implement this interface. By default
+/// if a contract does not support this interface any transactions originating from an ERC-1155
+/// compliant contract which attempt to transfer tokens directly to the contract's address must be
+/// reverted.
+#[ink::trait_definition]
+pub trait Erc1155TokenReceiver {
+    /// Handle the receipt of a single ERC-1155 token.
+    ///
+    /// This should be called by a compliant ERC-1155 contract if the intended recipient is a smart
+    /// contract.
+    ///
+    /// If the smart contract implementing this interface accepts token transfers then it must
+    /// return `ON_ERC_1155_RECEIVED_SELECTOR` from this function. To reject a transfer it must revert.
+    ///
+    /// Any callers must revert if they receive anything other than `ON_ERC_1155_RECEIVED_SELECTOR` as a return
+    /// value.
+    #[ink(message)]
+    fn on_received(
+        &mut self,
+        operator: AccountId,
+        from: AccountId,
+        token_id: TokenId,
+        value: Balance,
+        data: Vec<u8>,
+    ) -> Vec<u8>;
+
+    /// Handle the receipt of multiple ERC-1155 tokens.
+    ///
+    /// This should be called by a compliant ERC-1155 contract if the intended recipient is a smart
+    /// contract.
+    ///
+    /// If the smart contract implementing this interface accepts token transfers then it must
+    /// return `BATCH_ON_ERC_1155_RECEIVED_SELECTOR` from this function. To reject a transfer it must revert.
+    ///
+    /// Any callers must revert if they receive anything other than `BATCH_ON_ERC_1155_RECEIVED_SELECTOR` as a return
+    /// value.
+    #[ink(message)]
+    fn on_batch_received(
+        &mut self,
+        operator: AccountId,
+        from: AccountId,
+        token_ids: Vec<TokenId>,
+        values: Vec<Balance>,
+        data: Vec<u8>,
+    ) -> Vec<u8>;
+}
+
+#[ink::contract]
+mod erc1155 {
+    use super::*;
+
+    use ink_prelude::collections::BTreeMap;
+    use ink_storage::traits::{
+        PackedLayout,
+        SpreadLayout,
+    };
+
+    /// Indicate that a token transfer has occured.
+    ///
+    /// This must be emitted even if a zero value transfer occurs.
+    #[ink(event)]
+    pub struct TransferSingle {
+        #[ink(topic)]
+        operator: Option<AccountId>,
+        #[ink(topic)]
+        from: Option<AccountId>,
+        #[ink(topic)]
+        to: Option<AccountId>,
+        token_id: TokenId,
+        value: Balance,
+    }
+
+    /// Indicate that an approval event has happened.
+    #[ink(event)]
+    pub struct ApprovalForAll {
+        #[ink(topic)]
+        owner: AccountId,
+        #[ink(topic)]
+        operator: AccountId,
+        approved: bool,
+    }
+
+    /// Indicate that a token's URI has been updated.
+    #[ink(event)]
+    pub struct Uri {
+        value: ink_prelude::string::String,
+        #[ink(topic)]
+        token_id: TokenId,
+    }
+
+    /// Represents an (Owner, Operator) pair, in which the operator is allowed to spend funds on
+    /// behalf of the operator.
+    #[derive(
+        Copy,
+        Clone,
+        Debug,
+        Ord,
+        PartialOrd,
+        Eq,
+        PartialEq,
+        PackedLayout,
+        SpreadLayout,
+        scale::Encode,
+        scale::Decode,
+    )]
+    #[cfg_attr(feature = "std", derive(scale_info::TypeInfo))]
+    struct Approval {
+        owner: AccountId,
+        operator: AccountId,
+    }
+
+    /// An ERC-1155 contract.
+    #[ink(storage)]
+    #[derive(Default)]
+    pub struct Contract {
+        /// Tracks the balances of accounts across the different tokens that they might be holding.
+        balances: BTreeMap<(AccountId, TokenId), Balance>,
+        /// Which accounts (called operators) have been approved to spend funds on behalf of an owner.
+        approvals: BTreeMap<Approval, ()>,
+        /// A unique identifier for the tokens which have been minted (and are therefore supported)
+        /// by this contract.
+        token_id_nonce: TokenId,
+    }
+
+    impl Contract {
+        /// Initialize a default instance of this ERC-1155 implementation.
+        #[ink(constructor)]
+        pub fn new() -> Self {
+            Default::default()
+        }
+
+        /// Create the initial supply for a token.
+        ///
+        /// The initial supply will be provided to the caller (a.k.a the minter), and the
+        /// `token_id` will be assigned by the smart contract.
+        ///
+        /// Note that as implemented anyone can create tokens. If you were to deploy this to a
+        /// production environment you'd probably want to lock down the addresses that are allowed
+        /// to create tokens.
+        #[ink(message)]
+        pub fn create(&mut self, value: Balance) -> TokenId {
+            let caller = self.env().caller();
+
+            // Given that TokenId is a `u128` the likelihood of this overflowing is pretty slim.
+            self.token_id_nonce += 1;
+            self.balances.insert((caller, self.token_id_nonce), value);
+
+            // Emit transfer event but with mint semantics
+            self.env().emit_event(TransferSingle {
+                operator: Some(caller),
+                from: None,
+                to: if value == 0 { None } else { Some(caller) },
+                token_id: self.token_id_nonce,
+                value,
+            });
+
+            self.token_id_nonce
+        }
+
+        /// Mint a `value` amount of `token_id` tokens.
+        ///
+        /// It is assumed that the token has already been `create`-ed. The newly minted supply will
+        /// be assigned to the caller (a.k.a the minter).
+        ///
+        /// Note that as implemented anyone can mint tokens. If you were to deploy this to a
+        /// production environment you'd probably want to lock down the addresses that are allowed
+        /// to mint tokens.
+        #[ink(message)]
+        pub fn mint(&mut self, token_id: TokenId, value: Balance) -> Result<()> {
+            ensure!(token_id <= self.token_id_nonce, Error::UnexistentToken);
+
+            let caller = self.env().caller();
+            self.balances.insert((caller, token_id), value);
+
+            // Emit transfer event but with mint semantics
+            self.env().emit_event(TransferSingle {
+                operator: Some(caller),
+                from: None,
+                to: Some(caller),
+                token_id,
+                value,
+            });
+
+            Ok(())
+        }
+
+        // Helper function for performing single token transfers.
+        //
+        // Should not be used directly since it's missing certain checks which are important to the
+        // ERC-1155 standard (it is expected that the caller has already performed these).
+        fn perform_transfer(
+            &mut self,
+            from: AccountId,
+            to: AccountId,
+            token_id: TokenId,
+            value: Balance,
+        ) {
+            self.balances
+                .entry((from, token_id))
+                .and_modify(|b| *b -= value);
+
+            self.balances
+                .entry((to, token_id))
+                .and_modify(|b| *b += value)
+                .or_insert(value);
+
+            let caller = self.env().caller();
+            self.env().emit_event(TransferSingle {
+                operator: Some(caller),
+                from: Some(from),
+                to: Some(from),
+                token_id,
+                value,
+            });
+        }
+
+        // Check if the address at `to` is a smart contract which accepts ERC-1155 token transfers.
+        //
+        // If they're a smart contract which **doesn't** accept tokens transfers this call will
+        // revert. Otherwise we risk locking user funds at in that contract with no chance of
+        // recovery.
+        #[cfg_attr(test, allow(unused_variables))]
+        fn transfer_acceptance_check(
+            &mut self,
+            caller: AccountId,
+            from: AccountId,
+            to: AccountId,
+            token_id: TokenId,
+            value: Balance,
+            data: Vec<u8>,
+        ) {
+            // This is disabled during tests due to the use of `eval_contract()` not being
+            // supported (tests end up panicking).
+            #[cfg(not(test))]
+            {
+                use ink_env::call::{
+                    build_call,
+                    utils::ReturnType,
+                    ExecutionInput,
+                    Selector,
+                };
+
+                // If our recipient is a smart contract we need to see if they accept or
+                // reject this transfer. If they reject it we need to revert the call.
+                let params = build_call::<Environment>()
+                    .callee(to)
+                    .gas_limit(5000)
+                    .exec_input(
+                        ExecutionInput::new(Selector::new(ON_ERC_1155_RECEIVED_SELECTOR))
+                            .push_arg(caller)
+                            .push_arg(from)
+                            .push_arg(token_id)
+                            .push_arg(value)
+                            .push_arg(data),
+                    )
+                    .returns::<ReturnType<Vec<u8>>>()
+                    .params();
+
+                match ink_env::eval_contract(&params) {
+                    Ok(v) => {
+                        ink_env::debug_println!(
+                            "Received return value \"{:?}\" from contract {:?}",
+                            v,
+                            from
+                        );
+                        assert_eq!(
+                            v,
+                            &ON_ERC_1155_RECEIVED_SELECTOR[..],
+                            "The recipient contract at {:?} does not accept token transfers.\n
+                            Expected: {:?}, Got {:?}", to, ON_ERC_1155_RECEIVED_SELECTOR, v
+                        )
+                    }
+                    Err(e) => {
+                        match e {
+                            ink_env::Error::CodeNotFound
+                            | ink_env::Error::NotCallable => {
+                                // Our recipient wasn't a smart contract, so there's nothing more for
+                                // us to do
+                                ink_env::debug_println!("Recipient at {:?} from is not a smart contract ({:?})", from, e);
+                            }
+                            _ => {
+                                // We got some sort of error from the call to our recipient smart
+                                // contract, and as such we must revert this call
+                                let msg = ink_prelude::format!(
+                                    "Got error \"{:?}\" while trying to call {:?}",
+                                    e,
+                                    from
+                                );
+                                ink_env::debug_println!("{}", &msg);
+                                panic!("{}", &msg)
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    impl super::Erc1155 for Contract {
+        #[ink(message)]
+        fn safe_transfer_from(
+            &mut self,
+            from: AccountId,
+            to: AccountId,
+            token_id: TokenId,
+            value: Balance,
+            data: Vec<u8>,
+        ) -> Result<()> {
+            let caller = self.env().caller();
+            if caller != from {
+                ensure!(self.is_approved_for_all(from, caller), Error::NotApproved);
+            }
+
+            ensure!(to != AccountId::default(), Error::ZeroAddressTransfer);
+
+            let balance = self.balance_of(from, token_id);
+            ensure!(balance >= value, Error::InsufficientBalance);
+
+            self.perform_transfer(from, to, token_id, value);
+            self.transfer_acceptance_check(caller, from, to, token_id, value, data);
+
+            Ok(())
+        }
+
+        #[ink(message)]
+        fn safe_batch_transfer_from(
+            &mut self,
+            from: AccountId,
+            to: AccountId,
+            token_ids: Vec<TokenId>,
+            values: Vec<Balance>,
+            data: Vec<u8>,
+        ) -> Result<()> {
+            let caller = self.env().caller();
+            if caller != from {
+                ensure!(self.is_approved_for_all(from, caller), Error::NotApproved);
+            }
+
+            ensure!(to != AccountId::default(), Error::ZeroAddressTransfer);
+            ensure!(!token_ids.is_empty(), Error::BatchTransferMismatch);
+            ensure!(
+                token_ids.len() == values.len(),
+                Error::BatchTransferMismatch,
+            );
+
+            let transfers = token_ids.iter().zip(values.iter());
+            for (&id, &v) in transfers.clone() {
+                let balance = self.balance_of(from, id);
+                ensure!(balance >= v, Error::InsufficientBalance);
+            }
+
+            for (&id, &v) in transfers {
+                self.perform_transfer(from, to, id, v);
+            }
+
+            // Can use the any token ID/value here, we really just care about knowing if `to` is a
+            // smart contract which accepts transfers
+            self.transfer_acceptance_check(
+                caller,
+                from,
+                to,
+                token_ids[0],
+                values[0],
+                data,
+            );
+
+            Ok(())
+        }
+
+        #[ink(message)]
+        fn balance_of(&self, owner: AccountId, token_id: TokenId) -> Balance {
+            *self.balances.get(&(owner, token_id)).unwrap_or(&0)
+        }
+
+        #[ink(message)]
+        fn balance_of_batch(
+            &self,
+            owners: Vec<AccountId>,
+            token_ids: Vec<TokenId>,
+        ) -> Vec<Balance> {
+            let mut output = Vec::new();
+            for o in &owners {
+                for t in &token_ids {
+                    let amount = self.balance_of(*o, *t);
+                    output.push(amount);
+                }
+            }
+            output
+        }
+
+        #[ink(message)]
+        fn set_approval_for_all(
+            &mut self,
+            operator: AccountId,
+            approved: bool,
+        ) -> Result<()> {
+            let caller = self.env().caller();
+            ensure!(operator != caller, Error::SelfApproval);
+
+            let approval = Approval {
+                owner: caller,
+                operator,
+            };
+
+            if approved {
+                self.approvals.insert(approval, ());
+            } else {
+                self.approvals.remove(&approval);
+            }
+
+            self.env().emit_event(ApprovalForAll {
+                owner: approval.owner,
+                operator,
+                approved,
+            });
+
+            Ok(())
+        }
+
+        #[ink(message)]
+        fn is_approved_for_all(&self, owner: AccountId, operator: AccountId) -> bool {
+            self.approvals.get(&Approval { owner, operator }).is_some()
+        }
+    }
+
+    impl super::Erc1155TokenReceiver for Contract {
+        #[ink(message, selector = "0xF23A6E61")]
+        fn on_received(
+            &mut self,
+            _operator: AccountId,
+            _from: AccountId,
+            _token_id: TokenId,
+            _value: Balance,
+            _data: Vec<u8>,
+        ) -> Vec<u8> {
+            // The ERC-1155 standard dictates that if a contract does not accept token transfers
+            // directly to the contract, then the contract must revert.
+            //
+            // This prevents a user from unintentionally transferring tokens to a smart contract
+            // and getting their funds stuck without any sort of recovery mechanism.
+            //
+            // Note that the choice of whether or not to accept tokens is implementation specific,
+            // and we've decided to not accept them in this implementation.
+            unimplemented!("This smart contract does not accept token transfer.")
+        }
+
+        #[ink(message, selector = "0xBC197C81")]
+        fn on_batch_received(
+            &mut self,
+            _operator: AccountId,
+            _from: AccountId,
+            _token_ids: Vec<TokenId>,
+            _values: Vec<Balance>,
+            _data: Vec<u8>,
+        ) -> Vec<u8> {
+            // The ERC-1155 standard dictates that if a contract does not accept token transfers
+            // directly to the contract, then the contract must revert.
+            //
+            // This prevents a user from unintentionally transferring tokens to a smart contract
+            // and getting their funds stuck without any sort of recovery mechanism.
+            //
+            // Note that the choice of whether or not to accept tokens is implementation specific,
+            // and we've decided to not accept them in this implementation.
+            unimplemented!("This smart contract does not accept batch token transfers.")
+        }
+    }
+
+    #[cfg(test)]
+    mod tests {
+        /// Imports all the definitions from the outer scope so we can use them here.
+        use super::*;
+        use crate::Erc1155;
+
+        use ink_lang as ink;
+
+        #[cfg(feature = "ink-experimental-engine")]
+        fn set_sender(sender: AccountId) {
+            ink_env::test::set_caller::<Environment>(sender);
+        }
+
+        #[cfg(not(feature = "ink-experimental-engine"))]
+        fn set_sender(sender: AccountId) {
+            const WALLET: [u8; 32] = [7; 32];
+            ink_env::test::push_execution_context::<Environment>(
+                sender,
+                WALLET.into(),
+                1000000,
+                1000000,
+                ink_env::test::CallData::new(ink_env::call::Selector::new([0x00; 4])), /* dummy */
+            );
+        }
+
+        #[cfg(feature = "ink-experimental-engine")]
+        fn default_accounts() -> ink_env::test::DefaultAccounts<Environment> {
+            ink_env::test::default_accounts::<Environment>()
+        }
+
+        #[cfg(not(feature = "ink-experimental-engine"))]
+        fn default_accounts() -> ink_env::test::DefaultAccounts<Environment> {
+            ink_env::test::default_accounts::<Environment>()
+                .expect("off-chain environment should have been initialized already")
+        }
+
+        fn alice() -> AccountId {
+            default_accounts().alice
+        }
+
+        fn bob() -> AccountId {
+            default_accounts().bob
+        }
+
+        fn charlie() -> AccountId {
+            default_accounts().charlie
+        }
+
+        fn init_contract() -> Contract {
+            let mut erc = Contract::new();
+            erc.balances.insert((alice(), 1), 10);
+            erc.balances.insert((alice(), 2), 20);
+            erc.balances.insert((bob(), 1), 10);
+
+            erc
+        }
+
+        #[ink::test]
+        fn can_get_correct_balance_of() {
+            let erc = init_contract();
+
+            assert_eq!(erc.balance_of(alice(), 1), 10);
+            assert_eq!(erc.balance_of(alice(), 2), 20);
+            assert_eq!(erc.balance_of(alice(), 3), 0);
+            assert_eq!(erc.balance_of(bob(), 2), 0);
+        }
+
+        #[ink::test]
+        fn can_get_correct_batch_balance_of() {
+            let erc = init_contract();
+
+            assert_eq!(
+                erc.balance_of_batch(vec![alice()], vec![1, 2, 3]),
+                vec![10, 20, 0]
+            );
+            assert_eq!(
+                erc.balance_of_batch(vec![alice(), bob()], vec![1]),
+                vec![10, 10]
+            );
+
+            assert_eq!(
+                erc.balance_of_batch(vec![alice(), bob(), charlie()], vec![1, 2]),
+                vec![10, 20, 10, 0, 0, 0]
+            );
+        }
+
+        #[ink::test]
+        fn can_send_tokens_between_accounts() {
+            let mut erc = init_contract();
+
+            assert!(erc.safe_transfer_from(alice(), bob(), 1, 5, vec![]).is_ok());
+            assert_eq!(erc.balance_of(alice(), 1), 5);
+            assert_eq!(erc.balance_of(bob(), 1), 15);
+
+            assert!(erc.safe_transfer_from(alice(), bob(), 2, 5, vec![]).is_ok());
+            assert_eq!(erc.balance_of(alice(), 2), 15);
+            assert_eq!(erc.balance_of(bob(), 2), 5);
+        }
+
+        #[ink::test]
+        fn sending_too_many_tokens_fails() {
+            let mut erc = init_contract();
+            let res = erc.safe_transfer_from(alice(), bob(), 1, 99, vec![]);
+            assert_eq!(res.unwrap_err(), Error::InsufficientBalance);
+        }
+
+        #[ink::test]
+        fn sending_tokens_to_zero_address_fails() {
+            let burn: AccountId = [0; 32].into();
+
+            let mut erc = init_contract();
+            let res = erc.safe_transfer_from(alice(), burn, 1, 10, vec![]);
+            assert_eq!(res.unwrap_err(), Error::ZeroAddressTransfer);
+        }
+
+        #[ink::test]
+        fn can_send_batch_tokens() {
+            let mut erc = init_contract();
+            assert!(erc
+                .safe_batch_transfer_from(alice(), bob(), vec![1, 2], vec![5, 10], vec![])
+                .is_ok());
+
+            let balances = erc.balance_of_batch(vec![alice(), bob()], vec![1, 2]);
+            assert_eq!(balances, vec![5, 10, 15, 10])
+        }
+
+        #[ink::test]
+        fn rejects_batch_if_lengths_dont_match() {
+            let mut erc = init_contract();
+            let res = erc.safe_batch_transfer_from(
+                alice(),
+                bob(),
+                vec![1, 2, 3],
+                vec![5],
+                vec![],
+            );
+            assert_eq!(res.unwrap_err(), Error::BatchTransferMismatch);
+        }
+
+        #[ink::test]
+        fn batch_transfers_fail_if_len_is_zero() {
+            let mut erc = init_contract();
+            let res =
+                erc.safe_batch_transfer_from(alice(), bob(), vec![], vec![], vec![]);
+            assert_eq!(res.unwrap_err(), Error::BatchTransferMismatch);
+        }
+
+        #[ink::test]
+        fn operator_can_send_tokens() {
+            let mut erc = init_contract();
+
+            let owner = alice();
+            let operator = bob();
+
+            set_sender(owner);
+            assert!(erc.set_approval_for_all(operator, true).is_ok());
+
+            set_sender(operator);
+            assert!(erc
+                .safe_transfer_from(owner, charlie(), 1, 5, vec![])
+                .is_ok());
+            assert_eq!(erc.balance_of(alice(), 1), 5);
+            assert_eq!(erc.balance_of(charlie(), 1), 5);
+        }
+
+        #[ink::test]
+        fn approvals_work() {
+            let mut erc = init_contract();
+            let owner = alice();
+            let operator = bob();
+            let another_operator = charlie();
+
+            // Note: All of these tests are from the context of the owner who is either allowing or
+            // disallowing an operator to control their funds.
+            set_sender(owner);
+            assert!(erc.is_approved_for_all(owner, operator) == false);
+
+            assert!(erc.set_approval_for_all(operator, true).is_ok());
+            assert!(erc.is_approved_for_all(owner, operator));
+
+            assert!(erc.set_approval_for_all(another_operator, true).is_ok());
+            assert!(erc.is_approved_for_all(owner, another_operator));
+
+            assert!(erc.set_approval_for_all(operator, false).is_ok());
+            assert!(erc.is_approved_for_all(owner, operator) == false);
+        }
+
+        #[ink::test]
+        fn minting_tokens_works() {
+            let mut erc = Contract::new();
+
+            set_sender(alice());
+            assert_eq!(erc.create(0), 1);
+            assert_eq!(erc.balance_of(alice(), 1), 0);
+
+            assert!(erc.mint(1, 123).is_ok());
+            assert_eq!(erc.balance_of(alice(), 1), 123);
+        }
+
+        #[ink::test]
+        fn minting_not_allowed_for_nonexistent_tokens() {
+            let mut erc = Contract::new();
+
+            let res = erc.mint(1, 123);
+            assert_eq!(res.unwrap_err(), Error::UnexistentToken);
+        }
+    }
+}
diff --git a/scripts/pre_cache.sh b/scripts/.ci/pre_cache.sh
similarity index 100%
rename from scripts/pre_cache.sh
rename to scripts/.ci/pre_cache.sh
diff --git a/scripts/.ci/trigger_pipeline.sh b/scripts/.ci/trigger_pipeline.sh
new file mode 100755
index 0000000000..7580c01d5d
--- /dev/null
+++ b/scripts/.ci/trigger_pipeline.sh
@@ -0,0 +1,59 @@
+#!/bin/bash
+
+# This script is mostly copied from here:
+# https://github.com/paritytech/polkadot/blob/d822565487bdb41a9e8d73615877a8ea31ae0f6c/scripts/gitlab/trigger_pipeline.sh
+
+set -eu
+
+if [ ! -n "$PIPELINE_TOKEN" ]; then
+    echo "PIPELINE_TOKEN is missing!"
+    exit 1
+fi
+
+# API trigger another project's pipeline
+echo "Triggering ink-waterfall pipeline."
+
+echo "https://${CI_SERVER_HOST}/api/v4/projects/${DWNSTRM_ID}/trigger/pipeline"
+
+curl --silent \
+    -X POST \
+    -F "token=${CI_JOB_TOKEN}" \
+    -F "ref=master" \
+    -F "variables[TRGR_PROJECT]=${TRGR_PROJECT}" \
+    -F "variables[TRGR_REF]=${TRGR_REF}" \
+    "https://${CI_SERVER_HOST}/api/v4/projects/${DWNSTRM_ID}/trigger/pipeline" | \
+        tee pipeline;
+
+PIPELINE_ID=$(cat pipeline | jq ".id")
+PIPELINE_URL=$(cat pipeline | jq ".web_url")
+echo
+echo "ink-waterfall pipeline ${PIPELINE_URL} was successfully triggered."
+echo "Now we're polling it to obtain the distinguished status."
+
+# This is a workaround for a Gitlab bug, waits here until
+# https://gitlab.com/gitlab-org/gitlab/-/issues/326137 gets fixed.
+# The timeout is 360 curls with 8 sec interval, roughly an hour.
+
+function get_status() {
+    curl --silent \
+        --header "PRIVATE-TOKEN: ${PIPELINE_TOKEN}" \
+        "https://${CI_SERVER_HOST}/api/v4/projects/${DWNSTRM_ID}/pipelines/${PIPELINE_ID}" | \
+            jq --raw-output ".status";
+}
+
+echo "Waiting on ${PIPELINE_ID} status..."
+
+for i in $(seq 1 360); do
+    STATUS=$(get_status);
+    echo "Triggered pipeline status is ${STATUS}";
+    if [[ ${STATUS} =~ ^(pending|running|created)$ ]]; then
+        echo;
+    elif [[ ${STATUS} =~ ^(failed|canceled|skipped|manual)$ ]]; then
+        echo "Something's broken in: ${PIPELINE_URL}"; exit 1;
+    elif [[ ${STATUS} =~ ^(success)$ ]]; then
+        echo "Look how green it is: ${PIPELINE_URL}"; exit 0;
+    else
+        echo "Something else has happened in ${PIPELINE_URL}"; exit 1;
+    fi
+sleep 5;
+done


Test patch:
diff --git a/crates/lang/macro/tests/compile_tests.rs b/crates/lang/macro/tests/compile_tests.rs
index adf9ef1cc1..ed2d792c42 100644
--- a/crates/lang/macro/tests/compile_tests.rs
+++ b/crates/lang/macro/tests/compile_tests.rs
@@ -38,6 +38,7 @@ fn compile_tests() {
     t.compile_fail("tests/ui/fail/C-13-abi-constructor.rs");
     t.compile_fail("tests/ui/fail/C-14-payable-constructor.rs");
     t.compile_fail("tests/ui/fail/C-15-payable-trait-constructor.rs");
+    t.compile_fail("tests/ui/fail/C-16-function-arg-struct-destructuring.rs");
 
     t.compile_fail("tests/ui/fail/H-01-invalid-dyn-alloc.rs");
     t.compile_fail("tests/ui/fail/H-02-invalid-as-dependency.rs");
diff --git a/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.rs b/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.rs
new file mode 100644
index 0000000000..b811c1f226
--- /dev/null
+++ b/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.rs
@@ -0,0 +1,24 @@
+use ink_lang as ink;
+
+#[ink::contract]
+mod noop {
+
+    struct Args {
+        foo: (),
+    }
+
+    #[ink(storage)]
+    pub struct Noop {}
+
+    impl Noop {
+        #[ink(constructor)]
+        pub fn new() -> Self {
+            Self {}
+        }
+
+        #[ink(message)]
+        pub fn noop(&self, Foo { foo }: Foo) {}
+    }
+}
+
+fn main() {}
diff --git a/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.stderr b/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.stderr
new file mode 100644
index 0000000000..33ada0340d
--- /dev/null
+++ b/crates/lang/macro/tests/ui/fail/C-16-function-arg-struct-destructuring.stderr
@@ -0,0 +1,5 @@
+error: ink! message arguments must have an identifier
+  --> $DIR/C-16-function-arg-struct-destructuring.rs:20:28
+   |
+20 |         pub fn noop(&self, Foo { foo }: Foo) {}
+   |                            ^^^^^^^^^^^^^^^^
diff --git a/crates/storage/src/collections/vec/tests.rs b/crates/storage/src/collections/vec/tests.rs
index c1cbdaab40..89c9f23a65 100644
--- a/crates/storage/src/collections/vec/tests.rs
+++ b/crates/storage/src/collections/vec/tests.rs
@@ -11,16 +11,17 @@
 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 // See the License for the specific language governing permissions and
 // limitations under the License.
-
 use super::Vec as StorageVec;
 use crate::{
     collections::vec::IndexOutOfBounds,
     traits::{
         KeyPtr,
+        PackedLayout,
         SpreadLayout,
     },
     Lazy,
 };
+use core::cmp::Ordering;
 use ink_primitives::Key;
 
 #[test]
@@ -276,8 +277,8 @@ fn assert_eq_slice(vec: &StorageVec<u8>, slice: &[u8]) {
 }
 
 /// Creates a storage vector from the given slice.
-fn vec_from_slice(slice: &[u8]) -> StorageVec<u8> {
-    slice.iter().copied().collect::<StorageVec<u8>>()
+fn vec_from_slice<T: Copy + PackedLayout>(slice: &[T]) -> StorageVec<T> {
+    slice.iter().copied().collect::<StorageVec<T>>()
 }
 
 #[test]
@@ -422,11 +423,87 @@ fn clear_works_on_filled_vec() {
 
 #[test]
 fn clear_works_on_empty_vec() {
-    let mut vec = vec_from_slice(&[]);
+    let mut vec: StorageVec<()> = vec_from_slice(&[]);
     vec.clear();
     assert!(vec.is_empty());
 }
 
+#[test]
+fn test_binary_search() {
+    let b: StorageVec<i32> = StorageVec::new();
+    assert_eq!(b.binary_search(&5), Err(0));
+
+    let b = vec_from_slice(&[4]);
+    assert_eq!(b.binary_search(&3), Err(0));
+    assert_eq!(b.binary_search(&4), Ok(0));
+    assert_eq!(b.binary_search(&5), Err(1));
+
+    let b = vec_from_slice(&[1, 2, 4, 6, 8, 9]);
+    assert_eq!(b.binary_search(&5), Err(3));
+    assert_eq!(b.binary_search(&6), Ok(3));
+    assert_eq!(b.binary_search(&7), Err(4));
+    assert_eq!(b.binary_search(&8), Ok(4));
+
+    let b = vec_from_slice(&[1, 2, 4, 5, 6, 8]);
+    assert_eq!(b.binary_search(&9), Err(6));
+
+    let b = vec_from_slice(&[1, 2, 4, 6, 7, 8, 9]);
+    assert_eq!(b.binary_search(&6), Ok(3));
+    assert_eq!(b.binary_search(&5), Err(3));
+    assert_eq!(b.binary_search(&8), Ok(5));
+
+    let b = vec_from_slice(&[1, 2, 4, 5, 6, 8, 9]);
+    assert_eq!(b.binary_search(&7), Err(5));
+    assert_eq!(b.binary_search(&0), Err(0));
+
+    let b = vec_from_slice(&[1, 3, 3, 3, 7]);
+    assert_eq!(b.binary_search(&0), Err(0));
+    assert_eq!(b.binary_search(&1), Ok(0));
+    assert_eq!(b.binary_search(&2), Err(1));
+    assert!(match b.binary_search(&3) {
+        Ok(1..=3) => true,
+        _ => false,
+    });
+    assert!(match b.binary_search(&3) {
+        Ok(1..=3) => true,
+        _ => false,
+    });
+    assert_eq!(b.binary_search(&4), Err(4));
+    assert_eq!(b.binary_search(&5), Err(4));
+    assert_eq!(b.binary_search(&6), Err(4));
+    assert_eq!(b.binary_search(&7), Ok(4));
+    assert_eq!(b.binary_search(&8), Err(5));
+
+    let b = vec_from_slice(&[(); u8::MAX as usize]);
+    assert_eq!(b.binary_search(&()), Ok(u8::MAX as u32 / 2));
+}
+
+#[test]
+fn test_binary_search_by_overflow() {
+    let b = vec_from_slice(&[(); u8::MAX as usize]);
+    assert_eq!(
+        b.binary_search_by(|_| Ordering::Equal),
+        Ok(u8::MAX as u32 / 2)
+    );
+    assert_eq!(b.binary_search_by(|_| Ordering::Greater), Err(0));
+    assert_eq!(b.binary_search_by(|_| Ordering::Less), Err(u8::MAX as u32));
+}
+
+#[test]
+// Test implementation specific behavior when finding equivalent elements.
+fn test_binary_search_implementation_details() {
+    let b = vec_from_slice(&[1, 1, 2, 2, 3, 3, 3]);
+    assert_eq!(b.binary_search(&1), Ok(1));
+    assert_eq!(b.binary_search(&2), Ok(3));
+    assert_eq!(b.binary_search(&3), Ok(5));
+    let b = vec_from_slice(&[1, 1, 1, 1, 1, 3, 3, 3, 3]);
+    assert_eq!(b.binary_search(&1), Ok(4));
+    assert_eq!(b.binary_search(&3), Ok(7));
+    let b = vec_from_slice(&[1, 1, 1, 1, 3, 3, 3, 3, 3]);
+    assert_eq!(b.binary_search(&1), Ok(2));
+    assert_eq!(b.binary_search(&3), Ok(4));
+}
+
 #[test]
 #[should_panic(expected = "encountered empty storage cell")]
 #[cfg(not(feature = "ink-experimental-engine"))]