rust Added Complexity annotations for documentation of std::collections::VecDeque

Pull request for https://github.com/rust-lang/rust/issues/100182

Feb 24 '24 10:02 AnthonyZhOon

Thanks for the pull request, and welcome! The Rust team is excited to review your changes, and you should hear from @Mark-Simulacrum (or someone else) some time within the next two weeks.

Please see the contribution instructions for more information. Namely, in order to ensure the minimum review times lag, PR authors and assigned reviewers should ensure that the review label (S-waiting-on-review and S-waiting-on-author) stays updated, invoking these commands when appropriate:

@rustbot author: the review is finished, PR author should check the comments and take action accordingly
@rustbot review: the author is ready for a review, this PR will be queued again in the reviewer's queue

Feb 24 '24 10:02 rustbot

There are merge commits (commits with multiple parents) in your changes. We have a no merge policy so these commits will need to be removed for this pull request to be merged.

You can start a rebase with the following commands:

$ # rebase
$ git rebase -i master
$ # delete any merge commits in the editor that appears
$ git push --force-with-lease

The following commits are merge commits:

0ba11e83fa0fd76dd5c70c32f9983f6786b5ce5d

Feb 24 '24 10:02 rustbot

The job mingw-check-tidy failed! Check out the build log: (web) (plain)

Click to see the possible cause of the failure (guessed by this bot)

Prepare all required actions
Getting action download info
Download action repository 'actions/checkout@v4' (SHA:b4ffde65f46336ab88eb53be808477a3936bae11)
Download action repository 'actions/upload-artifact@v3' (SHA:a8a3f3ad30e3422c9c7b888a15615d19a852ae32)
Complete job name: PR - mingw-check-tidy
git config --global core.autocrlf false
shell: /usr/bin/bash --noprofile --norc -e -o pipefail {0}
---
GITHUB_ACTION=__run_7
GITHUB_ACTIONS=true
GITHUB_ACTION_REF=
GITHUB_ACTION_REPOSITORY=
GITHUB_ACTOR=AnthonyZhOon
GITHUB_API_URL=https://api.github.com
GITHUB_BASE_REF=master
GITHUB_ENV=/home/runner/work/_temp/_runner_file_commands/set_env_5bd7658a-9dba-4ad9-b56e-7d4795211267
GITHUB_EVENT_NAME=pull_request
---
GITHUB_SERVER_URL=https://github.com
GITHUB_SHA=086a759fc14ac1240b25029be7f98630c58feeee
GITHUB_STATE=/home/runner/work/_temp/_runner_file_commands/save_state_5bd7658a-9dba-4ad9-b56e-7d4795211267
GITHUB_STEP_SUMMARY=/home/runner/work/_temp/_runner_file_commands/step_summary_5bd7658a-9dba-4ad9-b56e-7d4795211267
GITHUB_TRIGGERING_ACTOR=AnthonyZhOon
GITHUB_WORKFLOW_REF=rust-lang/rust/.github/workflows/ci.yml@refs/pull/121541/merge
GITHUB_WORKFLOW_SHA=086a759fc14ac1240b25029be7f98630c58feeee
GITHUB_WORKSPACE=/home/runner/work/rust/rust
GOROOT_1_19_X64=/opt/hostedtoolcache/go/1.19.13/x64
---
COPY scripts/sccache.sh /scripts/
RUN sh /scripts/sccache.sh

COPY host-x86_64/mingw-check/reuse-requirements.txt /tmp/
RUN pip3 install --no-deps --no-cache-dir --require-hashes -r /tmp/reuse-requirements.txt \
    && pip3 install virtualenv
COPY host-x86_64/mingw-check/validate-toolstate.sh /scripts/
COPY host-x86_64/mingw-check/validate-error-codes.sh /scripts/

# NOTE: intentionally uses python2 for x.py so we can test it still works.
# NOTE: intentionally uses python2 for x.py so we can test it still works.
# validate-toolstate only runs in our CI, so it's ok for it to only support python3.
ENV SCRIPT TIDY_PRINT_DIFF=1 python2.7 ../x.py test \
           --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
# This file is autogenerated by pip-compile with Python 3.10
# by the following command:
#
#    pip-compile --allow-unsafe --generate-hashes reuse-requirements.in
---

#10 [5/8] COPY host-x86_64/mingw-check/reuse-requirements.txt /tmp/
#10 DONE 0.0s

#11 [6/8] RUN pip3 install --no-deps --no-cache-dir --require-hashes -r /tmp/reuse-requirements.txt     && pip3 install virtualenv
#11 0.697   Downloading binaryornot-0.4.4-py2.py3-none-any.whl (9.0 kB)
#11 0.708 Collecting boolean-py==4.0
#11 0.713   Downloading boolean.py-4.0-py3-none-any.whl (25 kB)
#11 0.723 Collecting chardet==5.1.0
---
#11 3.701 Building wheels for collected packages: reuse
#11 3.702   Building wheel for reuse (pyproject.toml): started
#11 4.035   Building wheel for reuse (pyproject.toml): finished with status 'done'
#11 4.036   Created wheel for reuse: filename=reuse-1.1.0-cp310-cp310-manylinux_2_35_x86_64.whl size=181117 sha256=f5f58750481f69515c2c0d1d503daf565e2565c370d07fc6aeb95fe3498b4269
#11 4.036   Stored in directory: /tmp/pip-ephem-wheel-cache-kjsxrzw7/wheels/c2/3c/b9/1120c2ab4bd82694f7e6f0537dc5b9a085c13e2c69a8d0c76d
#11 4.039 Installing collected packages: boolean-py, binaryornot, setuptools, reuse, python-debian, markupsafe, license-expression, jinja2, chardet
#11 4.061   Attempting uninstall: setuptools
#11 4.061     Found existing installation: setuptools 59.6.0
#11 4.062     Not uninstalling setuptools at /usr/lib/python3/dist-packages, outside environment /usr
#11 4.062     Not uninstalling setuptools at /usr/lib/python3/dist-packages, outside environment /usr
#11 4.063     Can't uninstall 'setuptools'. No files were found to uninstall.
#11 4.737 Successfully installed binaryornot-0.4.4 boolean-py-4.0 chardet-5.1.0 jinja2-3.1.2 license-expression-30.0.0 markupsafe-2.1.1 python-debian-0.1.49 reuse-1.1.0 setuptools-66.0.0
#11 4.737 WARNING: Running pip as the 'root' user can result in broken permissions and conflicting behaviour with the system package manager. It is recommended to use a virtual environment instead: https://pip.pypa.io/warnings/venv
#11 5.245 Collecting virtualenv
#11 5.282   Downloading virtualenv-20.25.1-py3-none-any.whl (3.8 MB)
#11 5.331      ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 3.8/3.8 MB 80.3 MB/s eta 0:00:00
#11 5.367 Collecting distlib<1,>=0.3.7
#11 5.374   Downloading distlib-0.3.8-py2.py3-none-any.whl (468 kB)
#11 5.380      ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 468.9/468.9 KB 110.4 MB/s eta 0:00:00
#11 5.408 Collecting platformdirs<5,>=3.9.1
#11 5.415   Downloading platformdirs-4.2.0-py3-none-any.whl (17 kB)
#11 5.444 Collecting filelock<4,>=3.12.2
#11 5.447   Downloading filelock-3.13.1-py3-none-any.whl (11 kB)
#11 5.531 Installing collected packages: distlib, platformdirs, filelock, virtualenv
#11 5.693 Successfully installed distlib-0.3.8 filelock-3.13.1 platformdirs-4.2.0 virtualenv-20.25.1
#11 DONE 5.8s

#12 [7/8] COPY host-x86_64/mingw-check/validate-toolstate.sh /scripts/
#12 DONE 0.0s
---
DirectMap4k:      174016 kB
DirectMap2M:     6117376 kB
DirectMap1G:    12582912 kB
##[endgroup]
Executing TIDY_PRINT_DIFF=1 python2.7 ../x.py test            --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
+ TIDY_PRINT_DIFF=1 python2.7 ../x.py test --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
    Finished dev [unoptimized] target(s) in 0.03s
##[endgroup]
downloading https://ci-artifacts.rust-lang.org/rustc-builds-alt/8f359beca4e58bc3ae795a666301a8f47023044c/rust-dev-nightly-x86_64-unknown-linux-gnu.tar.xz
extracting /checkout/obj/build/cache/llvm-8f359beca4e58bc3ae795a666301a8f47023044c-true/rust-dev-nightly-x86_64-unknown-linux-gnu.tar.xz to /checkout/obj/build/x86_64-unknown-linux-gnu/ci-llvm
---
   Compiling tidy v0.1.0 (/checkout/src/tools/tidy)
    Finished release [optimized] target(s) in 27.39s
##[endgroup]
fmt check
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 761:
     /// assert!(buf.capacity() >= 11);
     /// # Complexity
-    /// 
+    ///
+    ///
     /// Takes `O(n)` time to resize and copy.
     ///
     /// [`reserve`]: VecDeque::reserve
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 795:
     /// assert!(buf.capacity() >= 11);
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve(&mut self, additional: usize) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 850:
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 901:
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 935:
     /// assert!(buf.capacity() >= 4);
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies values to rotate into smaller size.
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn shrink_to_fit(&mut self) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 961:
     /// assert!(buf.capacity() >= 6);
     /// buf.shrink_to(0);
     /// assert!(buf.capacity() >= 4);
-    /// ``` 
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies values to rotate into smaller size.
     #[stable(feature = "shrink_to", since = "1.56.0")]
     pub fn shrink_to(&mut self, min_capacity: usize) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 1907:
     /// # Complexity
     ///
     /// Takes `O(n)` time to copy elements to fill interior gap.
-    /// For removal from front and back in `O(1)` time 
+    /// For removal from front and back in `O(1)` time
     /// use [`pop_front`] or [`pop_back`].
     ///
     /// [`pop_front`]: VecDeque::pop_front
Running `"/checkout/obj/build/x86_64-unknown-linux-gnu/rustfmt/bin/rustfmt" "--config-path" "/checkout" "--edition" "2021" "--unstable-features" "--skip-children" "--check" "/checkout/library/alloc/src/collections/vec_deque/spec_extend.rs" "/checkout/library/alloc/src/collections/vec_deque/drain.rs" "/checkout/library/alloc/src/collections/vec_deque/spec_from_iter.rs" "/checkout/library/alloc/src/collections/vec_deque/tests.rs" "/checkout/library/alloc/src/collections/vec_deque/into_iter.rs" "/checkout/library/alloc/src/collections/btree/merge_iter.rs" "/checkout/library/alloc/src/collections/btree/set/tests.rs" "/checkout/library/alloc/src/collections/vec_deque/mod.rs"` failed.
If you're running `tidy`, try again with `--bless`. Or, if you just want to format code, run `./x.py fmt` instead.
  local time: Sat Feb 24 10:43:07 UTC 2024
  network time: Sat, 24 Feb 2024 10:43:07 GMT
##[error]Process completed with exit code 1.
Post job cleanup.

Feb 24 '24 10:02 rust-log-analyzer

The job mingw-check-tidy failed! Check out the build log: (web) (plain)

Click to see the possible cause of the failure (guessed by this bot)

Prepare all required actions
Getting action download info
Download action repository 'actions/checkout@v4' (SHA:b4ffde65f46336ab88eb53be808477a3936bae11)
Download action repository 'actions/upload-artifact@v3' (SHA:a8a3f3ad30e3422c9c7b888a15615d19a852ae32)
Complete job name: PR - mingw-check-tidy
git config --global core.autocrlf false
shell: /usr/bin/bash --noprofile --norc -e -o pipefail {0}
---
GITHUB_ACTION=__run_7
GITHUB_ACTIONS=true
GITHUB_ACTION_REF=
GITHUB_ACTION_REPOSITORY=
GITHUB_ACTOR=AnthonyZhOon
GITHUB_API_URL=https://api.github.com
GITHUB_BASE_REF=master
GITHUB_ENV=/home/runner/work/_temp/_runner_file_commands/set_env_f21112d2-aec4-4a73-8dfa-4ecbbaaa4105
GITHUB_EVENT_NAME=pull_request
---
GITHUB_SERVER_URL=https://github.com
GITHUB_SHA=fdfd17b281f809a30d4718f727400958969ccfd3
GITHUB_STATE=/home/runner/work/_temp/_runner_file_commands/save_state_f21112d2-aec4-4a73-8dfa-4ecbbaaa4105
GITHUB_STEP_SUMMARY=/home/runner/work/_temp/_runner_file_commands/step_summary_f21112d2-aec4-4a73-8dfa-4ecbbaaa4105
GITHUB_TRIGGERING_ACTOR=AnthonyZhOon
GITHUB_WORKFLOW_REF=rust-lang/rust/.github/workflows/ci.yml@refs/pull/121541/merge
GITHUB_WORKFLOW_SHA=fdfd17b281f809a30d4718f727400958969ccfd3
GITHUB_WORKSPACE=/home/runner/work/rust/rust
GOROOT_1_19_X64=/opt/hostedtoolcache/go/1.19.13/x64
---
COPY scripts/sccache.sh /scripts/
RUN sh /scripts/sccache.sh

COPY host-x86_64/mingw-check/reuse-requirements.txt /tmp/
RUN pip3 install --no-deps --no-cache-dir --require-hashes -r /tmp/reuse-requirements.txt \
    && pip3 install virtualenv
COPY host-x86_64/mingw-check/validate-toolstate.sh /scripts/
COPY host-x86_64/mingw-check/validate-error-codes.sh /scripts/

# NOTE: intentionally uses python2 for x.py so we can test it still works.
# NOTE: intentionally uses python2 for x.py so we can test it still works.
# validate-toolstate only runs in our CI, so it's ok for it to only support python3.
ENV SCRIPT TIDY_PRINT_DIFF=1 python2.7 ../x.py test \
           --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
# This file is autogenerated by pip-compile with Python 3.10
# by the following command:
#
#    pip-compile --allow-unsafe --generate-hashes reuse-requirements.in
---

#10 [5/8] COPY host-x86_64/mingw-check/reuse-requirements.txt /tmp/
#10 DONE 0.0s

#11 [6/8] RUN pip3 install --no-deps --no-cache-dir --require-hashes -r /tmp/reuse-requirements.txt     && pip3 install virtualenv
#11 0.582   Downloading binaryornot-0.4.4-py2.py3-none-any.whl (9.0 kB)
#11 0.595 Collecting boolean-py==4.0
#11 0.600   Downloading boolean.py-4.0-py3-none-any.whl (25 kB)
#11 0.613 Collecting chardet==5.1.0
---
#11 3.646 Building wheels for collected packages: reuse
#11 3.647   Building wheel for reuse (pyproject.toml): started
#11 3.981   Building wheel for reuse (pyproject.toml): finished with status 'done'
#11 3.982   Created wheel for reuse: filename=reuse-1.1.0-cp310-cp310-manylinux_2_35_x86_64.whl size=181117 sha256=f5f58750481f69515c2c0d1d503daf565e2565c370d07fc6aeb95fe3498b4269
#11 3.982   Stored in directory: /tmp/pip-ephem-wheel-cache-f2r21dh_/wheels/c2/3c/b9/1120c2ab4bd82694f7e6f0537dc5b9a085c13e2c69a8d0c76d
#11 3.985 Installing collected packages: boolean-py, binaryornot, setuptools, reuse, python-debian, markupsafe, license-expression, jinja2, chardet
#11 4.008   Attempting uninstall: setuptools
#11 4.009     Found existing installation: setuptools 59.6.0
#11 4.010     Not uninstalling setuptools at /usr/lib/python3/dist-packages, outside environment /usr
#11 4.010     Not uninstalling setuptools at /usr/lib/python3/dist-packages, outside environment /usr
#11 4.010     Can't uninstall 'setuptools'. No files were found to uninstall.
#11 4.696 Successfully installed binaryornot-0.4.4 boolean-py-4.0 chardet-5.1.0 jinja2-3.1.2 license-expression-30.0.0 markupsafe-2.1.1 python-debian-0.1.49 reuse-1.1.0 setuptools-66.0.0
#11 4.696 WARNING: Running pip as the 'root' user can result in broken permissions and conflicting behaviour with the system package manager. It is recommended to use a virtual environment instead: https://pip.pypa.io/warnings/venv
#11 5.206 Collecting virtualenv
#11 5.245   Downloading virtualenv-20.25.1-py3-none-any.whl (3.8 MB)
#11 5.314      ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 3.8/3.8 MB 56.7 MB/s eta 0:00:00
#11 5.351 Collecting distlib<1,>=0.3.7
#11 5.359   Downloading distlib-0.3.8-py2.py3-none-any.whl (468 kB)
#11 5.366      ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 468.9/468.9 KB 94.4 MB/s eta 0:00:00
#11 5.393 Collecting platformdirs<5,>=3.9.1
#11 5.397   Downloading platformdirs-4.2.0-py3-none-any.whl (17 kB)
#11 5.436 Collecting filelock<4,>=3.12.2
#11 5.440   Downloading filelock-3.13.1-py3-none-any.whl (11 kB)
#11 5.524 Installing collected packages: distlib, platformdirs, filelock, virtualenv
#11 5.692 Successfully installed distlib-0.3.8 filelock-3.13.1 platformdirs-4.2.0 virtualenv-20.25.1
#11 DONE 5.8s

#12 [7/8] COPY host-x86_64/mingw-check/validate-toolstate.sh /scripts/
#12 DONE 0.0s
---
cache_alignment : 64
address sizes : 48 bits physical, 48 bits virtual
power management:

+ TIDY_PRINT_DIFF=1 python2.7 ../x.py test --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
MemFree:         6604100 kB
MemAvailable:   15007412 kB
Buffers:          255012 kB
Cached:          7825768 kB
---
DirectMap4k:      184256 kB
DirectMap2M:     5058560 kB
DirectMap1G:    13631488 kB
##[endgroup]
Executing TIDY_PRINT_DIFF=1 python2.7 ../x.py test            --stage 0 src/tools/tidy tidyselftest --extra-checks=py:lint
    Finished dev [unoptimized] target(s) in 0.03s
##[endgroup]
downloading https://ci-artifacts.rust-lang.org/rustc-builds-alt/8f359beca4e58bc3ae795a666301a8f47023044c/rust-dev-nightly-x86_64-unknown-linux-gnu.tar.xz
extracting /checkout/obj/build/cache/llvm-8f359beca4e58bc3ae795a666301a8f47023044c-true/rust-dev-nightly-x86_64-unknown-linux-gnu.tar.xz to /checkout/obj/build/x86_64-unknown-linux-gnu/ci-llvm
---
   Compiling tidy v0.1.0 (/checkout/src/tools/tidy)
    Finished release [optimized] target(s) in 28.95s
##[endgroup]
fmt check
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 761:
     /// assert!(buf.capacity() >= 11);
     /// # Complexity
-    /// 
+    ///
+    ///
     /// Takes `O(n)` time to resize and copy.
     ///
     /// [`reserve`]: VecDeque::reserve
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 795:
     /// assert!(buf.capacity() >= 11);
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn reserve(&mut self, additional: usize) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 850:
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 901:
     /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?");
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies array to new location.
     #[stable(feature = "try_reserve", since = "1.57.0")]
     pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 935:
     /// assert!(buf.capacity() >= 4);
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies values to rotate into smaller size.
     #[stable(feature = "deque_extras_15", since = "1.5.0")]
     pub fn shrink_to_fit(&mut self) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 961:
     /// assert!(buf.capacity() >= 6);
     /// buf.shrink_to(0);
     /// assert!(buf.capacity() >= 4);
-    /// ``` 
     /// # Complexity
-    // 
+    //
+    //
     /// Takes `O(n)` time as it copies values to rotate into smaller size.
     #[stable(feature = "shrink_to", since = "1.56.0")]
     pub fn shrink_to(&mut self, min_capacity: usize) {
##[error]Diff in /checkout/library/alloc/src/collections/vec_deque/mod.rs at line 1907:
     /// # Complexity
     ///
     /// Takes `O(n)` time to copy elements to fill interior gap.
-    /// For removal from front and back in `O(1)` time 
+    /// For removal from front and back in `O(1)` time
     /// use [`pop_front`] or [`pop_back`].
     ///
     /// [`pop_front`]: VecDeque::pop_front
Running `"/checkout/obj/build/x86_64-unknown-linux-gnu/rustfmt/bin/rustfmt" "--config-path" "/checkout" "--edition" "2021" "--unstable-features" "--skip-children" "--check" "/checkout/library/alloc/src/collections/vec_deque/spec_extend.rs" "/checkout/library/alloc/src/collections/vec_deque/drain.rs" "/checkout/library/alloc/src/collections/vec_deque/spec_from_iter.rs" "/checkout/library/alloc/src/collections/vec_deque/tests.rs" "/checkout/library/alloc/src/collections/vec_deque/into_iter.rs" "/checkout/library/alloc/src/collections/btree/merge_iter.rs" "/checkout/library/alloc/src/collections/btree/set/tests.rs" "/checkout/library/alloc/src/collections/vec_deque/mod.rs"` failed.
If you're running `tidy`, try again with `--bless`. Or, if you just want to format code, run `./x.py fmt` instead.
  local time: Sat Feb 24 11:19:41 UTC 2024
  network time: Sat, 24 Feb 2024 11:19:41 GMT
##[error]Process completed with exit code 1.
Post job cleanup.

Feb 24 '24 11:02 rust-log-analyzer

@rustbot review

Feb 25 '24 03:02 AnthonyZhOon

I think having these listed as a Complexity section individually on each method is not how I would want this documentation added. What do people think of having the complexity documentation centralized in VecDeque's struct-level documentation?

There are 2 use cases for complexity documentation on standard library collections:

Comparing complexity of a few key methods such as insert and get across data structures in order to choose a data structure. This is intended to be covered by the std::collections doc: https://doc.rust-lang.org/1.76.0/std/collections/index.html#performance
Forming a mental model of a specific collection in greater depth.

In order to serve the latter, it's necessary for the struct-level documentation to give an overview of what data structure this struct implements. In VecDeque's case, a geometrically growable ring buffer. It makes sense to augment this explanation with a rundown of the complexities of the operations. The point would not be to cover every method exhaustively. For example individually specifying front and front_mut is redundant. The point would be to lean on complexity as a way to explain the implementation and role of the data structure. That we can get in constant time, pop from either end in constant time, and push on either end in amortized constant time.

In contrast, consuming complexity documentation sprinkled across the entire suite of methods is not an efficient way to form a mental model of the data structure. Too much of the documentation added in this PR is either too noisy for this purpose (front_mut) or too oversimplified (push_back).

It's still fair to have method-level complexity documentation in a few places, but I would focus that where the whole point of a method is its particular complexity, such as swap_remove.

Mar 12 '24 16:03 dtolnay

@AnthonyZhOon Any updates on this? I see that you've reacted to dtolnays review. Are you planning on addressing the reviews?

Jul 11 '24 14:07 oskgo

Closing this as inactive. Feel free to reöpen this pr or create a new pr if you get the time to work on this. Thanks

Aug 09 '24 09:08 Dylan-DPC

rust rust copied to clipboard

Added Complexity annotations for documentation of std::collections::VecDeque

rust
rust copied to clipboard