diff options
Diffstat (limited to 'vendor/gix-negotiate')
| -rw-r--r-- | vendor/gix-negotiate/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | vendor/gix-negotiate/CHANGELOG.md | 118 | ||||
| -rw-r--r-- | vendor/gix-negotiate/Cargo.toml | 47 | ||||
| -rw-r--r-- | vendor/gix-negotiate/LICENSE-APACHE | 191 | ||||
| -rw-r--r-- | vendor/gix-negotiate/LICENSE-MIT | 21 | ||||
| -rw-r--r-- | vendor/gix-negotiate/src/consecutive.rs | 167 | ||||
| -rw-r--r-- | vendor/gix-negotiate/src/lib.rs | 144 | ||||
| -rw-r--r-- | vendor/gix-negotiate/src/noop.rs | 23 | ||||
| -rw-r--r-- | vendor/gix-negotiate/src/skipping.rs | 182 | ||||
| -rw-r--r-- | vendor/gix-negotiate/tests/baseline/mod.rs | 226 | ||||
| -rw-r--r-- | vendor/gix-negotiate/tests/fixtures/generated-archives/make_repos.tar.xz | bin | 0 -> 92828 bytes | |||
| -rw-r--r-- | vendor/gix-negotiate/tests/fixtures/make_repos.sh | 146 | ||||
| -rw-r--r-- | vendor/gix-negotiate/tests/negotiate.rs | 46 |
13 files changed, 1312 insertions, 0 deletions
diff --git a/vendor/gix-negotiate/.cargo-checksum.json b/vendor/gix-negotiate/.cargo-checksum.json new file mode 100644 index 000000000..8bd77c543 --- /dev/null +++ b/vendor/gix-negotiate/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"CHANGELOG.md":"ab923240f4d5aa26cf260633f5a80b451260e9e3225ec46153993ad6cb05f3be","Cargo.toml":"4c3fda273b7bade0583cc6134767f7650cb51656271e842b2b2af51afbedc7f0","LICENSE-APACHE":"cb4780590812826851ba250f90bed0ed19506ec98f6865a0e2e20bbf62391ff9","LICENSE-MIT":"49df47913ab2beafe8dc45607877ae64198bf0eee64aaad3e82ed9e4d27424e8","src/consecutive.rs":"fc11ce75e38d19f5c0edaf0794b437bc8eaf5ea7780e75c2f06decc9d2205950","src/lib.rs":"fd9a02db845a4984f7d12a96207ba70756bb495f35fb17cd12f71d8fcac0d318","src/noop.rs":"448f0ee6e34eec63037009bdfcaf6e50cd3c0139540899e3e004d7825af7139a","src/skipping.rs":"9dea5b75955ef1c1e4a7dd726839354b187ffba31177c517eddc6c12f03ffee8","tests/baseline/mod.rs":"3d1dc9bec5fbdfa0ad46bc9e7a891813390e09d96e981b8f65f3e7ab51ce97c1","tests/fixtures/generated-archives/make_repos.tar.xz":"dcfe215bf6f1db2f757b9201c5c3682ddc4340a627832a03a70d5768fe192beb","tests/fixtures/make_repos.sh":"03145c0e92e14f55b9d4b3500de8736f77ab4cfb04184aa6b87dc043e16a44fb","tests/negotiate.rs":"2cfd9d5aea1894e28f622672ecbfdd169984ac16c8ab7751e7862d47ca940450"},"package":"945c3ef1e912e44a5f405fc9e924edf42000566a1b257ed52cb1293300f6f08c"}
\ No newline at end of file diff --git a/vendor/gix-negotiate/CHANGELOG.md b/vendor/gix-negotiate/CHANGELOG.md new file mode 100644 index 000000000..ec5acd933 --- /dev/null +++ b/vendor/gix-negotiate/CHANGELOG.md @@ -0,0 +1,118 @@ +# Changelog + +All notable changes to this project will be documented in this file. + +The format is based on [Keep a Changelog](https://keepachangelog.com/en/1.0.0/), +and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.html). + +## 0.2.1 (2023-06-10) + +A maintenance release without user-facing changes. + +### Commit Statistics + +<csr-read-only-do-not-edit/> + + - 3 commits contributed to the release. + - 3 days passed between releases. + - 0 commits were understood as [conventional](https://www.conventionalcommits.org). + - 0 issues like '(#ID)' were seen in commit messages + +### Commit Details + +<csr-read-only-do-not-edit/> + +<details><summary>view details</summary> + + * **Uncategorized** + - Prepare changelogs prior to release ([`298f3d7`](https://github.com/Byron/gitoxide/commit/298f3d7359c5b183314d8c584e45dcdd559d88b3)) + - Merge branch 'walk-with-commitgraph' ([`fdee9a2`](https://github.com/Byron/gitoxide/commit/fdee9a22873a13ae644d3dc92f8fe93f8f0266c0)) + - Adapt to changes in `gix-revwalk` ([`f7d95d1`](https://github.com/Byron/gitoxide/commit/f7d95d189af1422a7ba48db1857452e32e1d9db9)) +</details> + +## 0.2.0 (2023-06-06) + +<csr-id-1571528f8779330aa1d077b1452aa00d9b419033/> + +### New Features + + - <csr-id-1bd93bedd2f184510239c50c345d3dbc41d7d13b/> allow graph sharing by unifying `Flags` type. + This makes the graph used in `gix-negotiate` shareable by callers, which can + do their own traversal and store their own flags. The knowlege of this traversal + can be kept using such shared flags, like the `PARSED` bit which should be set whenever + parents are traversed. + + That way we are able to emulate the algorithms git uses perfectly, as we keep exactly the + same state. + - <csr-id-4aad40d6b6ddee0bc01b222cc2426c61c61d0b1a/> implement `skipping` negotiation algorithm + - <csr-id-01aba9e92941240eefa898890f1b8b8d824db509/> implement `consecutive` algorithm. + This is the default negotiation algorithm. + - <csr-id-1f6e6d8aeb512b2afcd1911cf32e4f7e622bf73d/> introduce the `noop` negotiator to establish a basic trait for negotiators. + +### Other + + - <csr-id-1571528f8779330aa1d077b1452aa00d9b419033/> try to change test-suite from --negotiate-only to the more realistic fetch with --dry-run. + This means we will have to reproduce what git does naturally, to fill in common refs + and also provide tips. + + Unfortunately this doesn't work as it's apparently not really dry-running, but modifying + the repository underneath. This means it's not idempotent when running it multiple times. + +### Commit Statistics + +<csr-read-only-do-not-edit/> + + - 17 commits contributed to the release over the course of 17 calendar days. + - 18 days passed between releases. + - 5 commits were understood as [conventional](https://www.conventionalcommits.org). + - 0 issues like '(#ID)' were seen in commit messages + +### Commit Details + +<csr-read-only-do-not-edit/> + +<details><summary>view details</summary> + + * **Uncategorized** + - Release gix-date v0.5.1, gix-hash v0.11.2, gix-features v0.30.0, gix-actor v0.21.0, gix-path v0.8.1, gix-glob v0.8.0, gix-quote v0.4.4, gix-attributes v0.13.0, gix-chunk v0.4.2, gix-commitgraph v0.16.0, gix-config-value v0.12.1, gix-fs v0.2.0, gix-tempfile v6.0.0, gix-utils v0.1.2, gix-lock v6.0.0, gix-validate v0.7.5, gix-object v0.30.0, gix-ref v0.30.0, gix-sec v0.8.1, gix-config v0.23.0, gix-command v0.2.5, gix-prompt v0.5.1, gix-url v0.19.0, gix-credentials v0.15.0, gix-diff v0.30.0, gix-discover v0.19.0, gix-hashtable v0.2.1, gix-ignore v0.3.0, gix-bitmap v0.2.4, gix-traverse v0.26.0, gix-index v0.17.0, gix-mailmap v0.13.0, gix-revision v0.15.0, gix-negotiate v0.2.0, gix-pack v0.36.0, gix-odb v0.46.0, gix-packetline v0.16.2, gix-transport v0.32.0, gix-protocol v0.33.0, gix-refspec v0.11.0, gix-worktree v0.18.0, gix v0.45.0, safety bump 29 crates ([`9a9fa96`](https://github.com/Byron/gitoxide/commit/9a9fa96fa8a722bddc5c3b2270b0edf8f6615141)) + - `just fmt` ([`ffc1276`](https://github.com/Byron/gitoxide/commit/ffc1276e0c991ac33ce842f5dca0b45ac69680c0)) + - Prepare changelogs prior to release ([`8f15cec`](https://github.com/Byron/gitoxide/commit/8f15cec1ec7d5a9d56bb158f155011ef2bb3539b)) + - Merge branch 'integrate-gix-negotiate' ([`ae845de`](https://github.com/Byron/gitoxide/commit/ae845dea6cee6523c88a23d7a14293589cf8092f)) + - Allow graph sharing by unifying `Flags` type. ([`1bd93be`](https://github.com/Byron/gitoxide/commit/1bd93bedd2f184510239c50c345d3dbc41d7d13b)) + - Merge branch 'main' into auto-clippy ([`3ef5c90`](https://github.com/Byron/gitoxide/commit/3ef5c90aebce23385815f1df674c1d28d58b4b0d)) + - Merge branch 'blinxen/main' ([`9375cd7`](https://github.com/Byron/gitoxide/commit/9375cd75b01aa22a0e2eed6305fe45fabfd6c1ac)) + - Include license files in all crates ([`facaaf6`](https://github.com/Byron/gitoxide/commit/facaaf633f01c857dcf2572c6dbe0a92b7105c1c)) + - Merge branch 'consecutive-negotiation' ([`97b3f7e`](https://github.com/Byron/gitoxide/commit/97b3f7e2eaddea20c98f2f7ab6a0d2e2117b0793)) + - Try to change test-suite from --negotiate-only to the more realistic fetch with --dry-run. ([`1571528`](https://github.com/Byron/gitoxide/commit/1571528f8779330aa1d077b1452aa00d9b419033)) + - Add a test to also validate interaction with known_common/remote refs ([`5bdd071`](https://github.com/Byron/gitoxide/commit/5bdd0716f359683060bab0f0695245a653bb6775)) + - Figure out what's wrong with 'skipping' and fix it ([`1b19ab1`](https://github.com/Byron/gitoxide/commit/1b19ab11c0928f26443d22ecfb6f211f4cdb5946)) + - Attempt to figure out what 'consecutive' needs to pass the tests ([`1809a99`](https://github.com/Byron/gitoxide/commit/1809a994c9d8a50bc73d283fd20ac825bfa6e92d)) + - Implement `skipping` negotiation algorithm ([`4aad40d`](https://github.com/Byron/gitoxide/commit/4aad40d6b6ddee0bc01b222cc2426c61c61d0b1a)) + - Implement `consecutive` algorithm. ([`01aba9e`](https://github.com/Byron/gitoxide/commit/01aba9e92941240eefa898890f1b8b8d824db509)) + - A baseline test for the noop negotiator ([`5cd7748`](https://github.com/Byron/gitoxide/commit/5cd7748279fd502f3651e37150f60a785f972a48)) + - Introduce the `noop` negotiator to establish a basic trait for negotiators. ([`1f6e6d8`](https://github.com/Byron/gitoxide/commit/1f6e6d8aeb512b2afcd1911cf32e4f7e622bf73d)) +</details> + +## v0.1.0 (2023-05-19) + +Initial release with a single function to calculate the window size for `HAVE` lines. + +### Commit Statistics + +<csr-read-only-do-not-edit/> + + - 2 commits contributed to the release. + - 0 commits were understood as [conventional](https://www.conventionalcommits.org). + - 0 issues like '(#ID)' were seen in commit messages + +### Commit Details + +<csr-read-only-do-not-edit/> + +<details><summary>view details</summary> + + * **Uncategorized** + - Release gix-commitgraph v0.15.0, gix-revision v0.14.0, gix-negotiate v0.1.0, safety bump 7 crates ([`92832ca`](https://github.com/Byron/gitoxide/commit/92832ca2899cd2f222f4c7b1cc9e766178f55806)) + - Add new crate for implementing and testing git negotiation logic. ([`372ba09`](https://github.com/Byron/gitoxide/commit/372ba09bb00e3fab674f0251f697aab11c5559f8)) +</details> + diff --git a/vendor/gix-negotiate/Cargo.toml b/vendor/gix-negotiate/Cargo.toml new file mode 100644 index 000000000..8ae3b7ee6 --- /dev/null +++ b/vendor/gix-negotiate/Cargo.toml @@ -0,0 +1,47 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +edition = "2021" +rust-version = "1.64" +name = "gix-negotiate" +version = "0.2.1" +authors = ["Sebastian Thiel <sebastian.thiel@icloud.com>"] +description = "A crate of the gitoxide project implementing negotiation algorithms" +license = "MIT/Apache-2.0" +repository = "https://github.com/Byron/gitoxide" + +[lib] +test = false +doctest = false + +[dependencies.bitflags] +version = "2" + +[dependencies.gix-commitgraph] +version = "^0.16.0" + +[dependencies.gix-hash] +version = "^0.11.2" + +[dependencies.gix-object] +version = "^0.30.0" + +[dependencies.gix-revision] +version = "^0.15.2" + +[dependencies.smallvec] +version = "1.10.0" + +[dependencies.thiserror] +version = "1.0.40" + +[dev-dependencies] diff --git a/vendor/gix-negotiate/LICENSE-APACHE b/vendor/gix-negotiate/LICENSE-APACHE new file mode 100644 index 000000000..a51f59a06 --- /dev/null +++ b/vendor/gix-negotiate/LICENSE-APACHE @@ -0,0 +1,191 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + Copyright 2018-2021 Sebastian Thiel, and [contributors](https://github.com/byron/gitoxide/contributors) + + 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. diff --git a/vendor/gix-negotiate/LICENSE-MIT b/vendor/gix-negotiate/LICENSE-MIT new file mode 100644 index 000000000..b58e818f1 --- /dev/null +++ b/vendor/gix-negotiate/LICENSE-MIT @@ -0,0 +1,21 @@ +MIT License + +Copyright (c) 2018-2021 Sebastian Thiel, and [contributors](https://github.com/byron/gitoxide/contributors). + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE +SOFTWARE. diff --git a/vendor/gix-negotiate/src/consecutive.rs b/vendor/gix-negotiate/src/consecutive.rs new file mode 100644 index 000000000..f213cd949 --- /dev/null +++ b/vendor/gix-negotiate/src/consecutive.rs @@ -0,0 +1,167 @@ +use gix_hash::ObjectId; +use gix_revision::graph::CommitterTimestamp; + +use crate::{Error, Flags, Negotiator}; + +pub(crate) struct Algorithm { + revs: gix_revision::PriorityQueue<CommitterTimestamp, ObjectId>, + non_common_revs: usize, +} + +impl Default for Algorithm { + fn default() -> Self { + Self { + revs: gix_revision::PriorityQueue::new(), + non_common_revs: 0, + } + } +} + +impl Algorithm { + /// Add `id` to our priority queue and *add* `flags` to it. + fn add_to_queue(&mut self, id: ObjectId, mark: Flags, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + let mut is_common = false; + let mut has_mark = false; + if let Some(commit) = graph + .try_lookup_or_insert_commit(id, |data| { + has_mark = data.flags.intersects(mark); + data.flags |= mark; + is_common = data.flags.contains(Flags::COMMON); + })? + .filter(|_| !has_mark) + { + self.revs.insert(commit.commit_time, id); + if !is_common { + self.non_common_revs += 1; + } + } + Ok(()) + } + + fn mark_common( + &mut self, + id: ObjectId, + mode: Mark, + ancestors: Ancestors, + graph: &mut crate::Graph<'_>, + ) -> Result<(), Error> { + let mut is_common = false; + if let Some(commit) = graph + .try_lookup_or_insert_commit(id, |data| is_common = data.flags.contains(Flags::COMMON))? + .filter(|_| !is_common) + { + let mut queue = gix_revision::PriorityQueue::from_iter(Some((commit.commit_time, (id, 0_usize)))); + if let Mark::ThisCommitAndAncestors = mode { + commit.data.flags |= Flags::COMMON; + if commit.data.flags.contains(Flags::SEEN) && !commit.data.flags.contains(Flags::POPPED) { + self.non_common_revs -= 1; + } + } + while let Some((id, generation)) = queue.pop_value() { + if graph + .get(&id) + .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN)) + { + self.add_to_queue(id, Flags::SEEN, graph)?; + } else if matches!(ancestors, Ancestors::AllUnseen) || generation < 2 { + if let Some(commit) = graph.try_lookup_or_insert_commit(id, |_| {})? { + for parent_id in commit.parents.clone() { + let mut prev_flags = Flags::default(); + if let Some(parent) = graph + .try_lookup_or_insert_commit(parent_id, |data| { + prev_flags = data.flags; + data.flags |= Flags::COMMON; + })? + .filter(|_| !prev_flags.contains(Flags::COMMON)) + { + if prev_flags.contains(Flags::SEEN) && !prev_flags.contains(Flags::POPPED) { + self.non_common_revs -= 1; + } + queue.insert(parent.commit_time, (parent_id, generation + 1)) + } + } + } + } + } + } + Ok(()) + } +} + +impl Negotiator for Algorithm { + fn known_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + if graph + .get(&id) + .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN)) + { + self.add_to_queue(id, Flags::COMMON_REF | Flags::SEEN, graph)?; + self.mark_common(id, Mark::AncestorsOnly, Ancestors::DirectUnseen, graph)?; + } + Ok(()) + } + + fn add_tip(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + self.add_to_queue(id, Flags::SEEN, graph) + } + + fn next_have(&mut self, graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> { + loop { + let id = self.revs.pop_value().filter(|_| self.non_common_revs != 0)?; + let commit = graph.get_mut(&id).expect("it was added to the graph by now"); + let flags = &mut commit.data.flags; + *flags |= Flags::POPPED; + + if !flags.contains(Flags::COMMON) { + self.non_common_revs -= 1; + } + + let (res, mark) = if flags.contains(Flags::COMMON) { + (None, Flags::COMMON | Flags::SEEN) + } else if flags.contains(Flags::COMMON_REF) { + (Some(id), Flags::COMMON | Flags::SEEN) + } else { + (Some(id), Flags::SEEN) + }; + + for parent_id in commit.parents.clone() { + if graph + .get(&parent_id) + .map_or(true, |commit| !commit.data.flags.contains(Flags::SEEN)) + { + if let Err(err) = self.add_to_queue(parent_id, mark, graph) { + return Some(Err(err)); + } + } + if mark.contains(Flags::COMMON) { + if let Err(err) = self.mark_common(parent_id, Mark::AncestorsOnly, Ancestors::AllUnseen, graph) { + return Some(Err(err)); + } + } + } + + if let Some(id) = res { + return Some(Ok(id)); + } + } + } + + fn in_common_with_remote(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<bool, Error> { + let known_to_be_common = graph + .get(&id) + .map_or(false, |commit| commit.data.flags.contains(Flags::COMMON)); + self.mark_common(id, Mark::ThisCommitAndAncestors, Ancestors::DirectUnseen, graph)?; + Ok(known_to_be_common) + } +} + +enum Mark { + AncestorsOnly, + ThisCommitAndAncestors, +} + +enum Ancestors { + /// Traverse only the parents of a commit. + DirectUnseen, + /// Traverse all ancestors that weren't yet seen. + AllUnseen, +} diff --git a/vendor/gix-negotiate/src/lib.rs b/vendor/gix-negotiate/src/lib.rs new file mode 100644 index 000000000..b05f944f8 --- /dev/null +++ b/vendor/gix-negotiate/src/lib.rs @@ -0,0 +1,144 @@ +//! An implementation of negotiation algorithms to help the server figure out what we have in common so it can optimize +//! the pack it sends to only contain what we don't have. +#![deny(rust_2018_idioms, missing_docs)] +#![forbid(unsafe_code)] +mod consecutive; +mod noop; +mod skipping; + +bitflags::bitflags! { + /// Multi purpose, shared flags that are used by negotiation algorithms and by the caller as well + /// + /// However, in this crate we can't implement the calling side, so we marry this type to whatever is needed in downstream crates. + #[derive(Debug, Default, Copy, Clone)] + pub struct Flags: u8 { + /// The object is already available locally and doesn't need to be fetched by the remote. + const COMPLETE = 1 << 0; + /// A commit from an alternate object database. + const ALTERNATE = 1 << 1; + + /// The revision is known to be in common with the remote. + /// + /// Used by `consecutive` and `skipping`. + const COMMON = 1 << 2; + /// The revision has entered the priority queue. + /// + /// Used by `consecutive` and `skipping`. + const SEEN = 1 << 3; + /// The revision was popped off our primary priority queue, used to avoid double-counting of `non_common_revs` + /// + /// Used by `consecutive` and `skipping`. + const POPPED = 1 << 4; + + /// The revision is common and was set by merit of a remote tracking ref (e.g. `refs/heads/origin/main`). + /// + /// Used by `consecutive`. + const COMMON_REF = 1 << 5; + + /// The remote let us know it has the object. We still have to tell the server we have this object or one of its descendants. + /// We won't tell the server about its ancestors. + /// + /// Used by `skipping`. + const ADVERTISED = 1 << 6; + } +} + +/// Additional data to store with each commit when used by any of our algorithms. +/// +/// It's shared among those who use the [`Negotiator`] trait, and all implementations of it. +#[derive(Default, Copy, Clone)] +pub struct Metadata { + /// Used by `skipping`. + /// Only used if commit is not COMMON + pub original_ttl: u16, + /// Used by `skipping`. + pub ttl: u16, + /// Additional information about each commit + pub flags: Flags, +} + +/// The graph our callers use to store traversal information, for (re-)use in the negotiation implementation. +pub type Graph<'find> = gix_revision::Graph<'find, gix_revision::graph::Commit<Metadata>>; + +/// The way the negotiation is performed. +#[derive(Default, Debug, Copy, Clone, Eq, PartialEq)] +pub enum Algorithm { + /// Do not send any information at all, which typically leads to complete packs to be sent. + Noop, + /// Walk over consecutive commits and check each one. This can be costly be assures packs are exactly the size they need to be. + #[default] + Consecutive, + /// Like `Consecutive`, but skips commits to converge faster, at the cost of receiving packs that are larger than they have to be. + Skipping, +} + +impl std::fmt::Display for Algorithm { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Algorithm::Noop => "noop", + Algorithm::Consecutive => "consecutive", + Algorithm::Skipping => "skipping", + } + .fmt(f) + } +} + +/// Calculate how many `HAVE` lines we may send in one round, with variation depending on whether the `transport_is_stateless` or not. +/// `window_size` is the previous (or initial) value of the window size. +pub fn window_size(transport_is_stateless: bool, window_size: impl Into<Option<usize>>) -> usize { + let current_size = match window_size.into() { + None => return 16, + Some(cs) => cs, + }; + const PIPESAFE_FLUSH: usize = 32; + const LARGE_FLUSH: usize = 16384; + + if transport_is_stateless { + if current_size < LARGE_FLUSH { + current_size * 2 + } else { + current_size * 11 / 10 + } + } else if current_size < PIPESAFE_FLUSH { + current_size * 2 + } else { + current_size + PIPESAFE_FLUSH + } +} + +impl Algorithm { + /// Create an instance of a negotiator which implements this algorithm. + pub fn into_negotiator(self) -> Box<dyn Negotiator> { + match &self { + Algorithm::Noop => Box::new(noop::Noop) as Box<dyn Negotiator>, + Algorithm::Consecutive => Box::<consecutive::Algorithm>::default(), + Algorithm::Skipping => Box::<skipping::Algorithm>::default(), + } + } +} + +/// A delegate to implement a negotiation algorithm. +pub trait Negotiator { + /// Mark `id` as common between the remote and us. + /// + /// These ids are typically the local tips of remote tracking branches. + fn known_common(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<(), Error>; + + /// Add `id` as starting point of a traversal across commits that aren't necessarily common between the remote and us. + /// + /// These tips are usually the commits of local references whose tips should lead to objects that we have in common with the remote. + fn add_tip(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<(), Error>; + + /// Produce the next id of an object that we want the server to know we have. It's an object we don't know we have in common or not. + /// + /// Returns `None` if we have exhausted all options, which might mean we have traversed the entire commit graph. + fn next_have(&mut self, graph: &mut Graph<'_>) -> Option<Result<gix_hash::ObjectId, Error>>; + + /// Mark `id` as being common with the remote (as informed by the remote itself) and return `true` if we knew it was common already. + /// + /// We can assume to have already seen `id` as we were the one to inform the remote in a prior `have`. + fn in_common_with_remote(&mut self, id: gix_hash::ObjectId, graph: &mut Graph<'_>) -> Result<bool, Error>; +} + +/// An error that happened during any of the methods on a [`Negotiator`]. +pub type Error = gix_revision::graph::lookup::commit::Error; diff --git a/vendor/gix-negotiate/src/noop.rs b/vendor/gix-negotiate/src/noop.rs new file mode 100644 index 000000000..5eabbb9e4 --- /dev/null +++ b/vendor/gix-negotiate/src/noop.rs @@ -0,0 +1,23 @@ +use gix_hash::ObjectId; + +use crate::{Error, Negotiator}; + +pub(crate) struct Noop; + +impl Negotiator for Noop { + fn known_common(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<(), Error> { + Ok(()) + } + + fn add_tip(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<(), Error> { + Ok(()) + } + + fn next_have(&mut self, _graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> { + None + } + + fn in_common_with_remote(&mut self, _id: ObjectId, _graph: &mut crate::Graph<'_>) -> Result<bool, Error> { + Ok(false) + } +} diff --git a/vendor/gix-negotiate/src/skipping.rs b/vendor/gix-negotiate/src/skipping.rs new file mode 100644 index 000000000..06841b687 --- /dev/null +++ b/vendor/gix-negotiate/src/skipping.rs @@ -0,0 +1,182 @@ +use gix_hash::ObjectId; +use gix_revision::graph::CommitterTimestamp; + +use crate::{Error, Flags, Metadata, Negotiator}; + +pub(crate) struct Algorithm { + revs: gix_revision::PriorityQueue<CommitterTimestamp, ObjectId>, + non_common_revs: usize, +} + +impl Default for Algorithm { + fn default() -> Self { + Self { + revs: gix_revision::PriorityQueue::new(), + non_common_revs: 0, + } + } +} + +impl Algorithm { + /// Add `id` to our priority queue and *add* `flags` to it. + fn add_to_queue(&mut self, id: ObjectId, mark: Flags, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + let commit = graph.try_lookup_or_insert_commit(id, |entry| { + entry.flags |= mark | Flags::SEEN; + })?; + if let Some(timestamp) = commit.map(|c| c.commit_time) { + self.revs.insert(timestamp, id); + if !mark.contains(Flags::COMMON) { + self.non_common_revs += 1; + } + } + Ok(()) + } + + fn mark_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + let mut is_common = false; + if let Some(commit) = graph + .try_lookup_or_insert_commit(id, |entry| { + is_common = entry.flags.contains(Flags::COMMON); + entry.flags |= Flags::COMMON; + })? + .filter(|_| !is_common) + { + let mut queue = gix_revision::PriorityQueue::from_iter(Some((commit.commit_time, id))); + while let Some(id) = queue.pop_value() { + if let Some(commit) = graph.try_lookup_or_insert_commit(id, |entry| { + if !entry.flags.contains(Flags::POPPED) { + self.non_common_revs -= 1; + } + })? { + for parent_id in commit.parents.clone() { + // This is a bit of a problem as there is no representation of the `parsed` based skip. However, + // We assume that parents that aren't in the graph yet haven't been seen, and that's all we need. + if !graph.contains(&parent_id) { + continue; + } + let mut was_unseen_or_common = false; + if let Some(parent) = graph + .try_lookup_or_insert_commit(parent_id, |entry| { + was_unseen_or_common = + !entry.flags.contains(Flags::SEEN) || entry.flags.contains(Flags::COMMON); + entry.flags |= Flags::COMMON + })? + .filter(|_| !was_unseen_or_common) + { + queue.insert(parent.commit_time, parent_id); + } + } + } + } + } + Ok(()) + } + + fn push_parent( + &mut self, + entry: Metadata, + parent_id: ObjectId, + graph: &mut crate::Graph<'_>, + ) -> Result<bool, Error> { + let mut was_seen = false; + if let Some(parent) = graph + .get(&parent_id) + .map(|parent| { + was_seen = parent.data.flags.contains(Flags::SEEN); + parent + }) + .filter(|_| was_seen) + { + if parent.data.flags.contains(Flags::POPPED) { + return Ok(false); + } + } else { + self.add_to_queue(parent_id, Flags::default(), graph)?; + } + if entry.flags.intersects(Flags::COMMON | Flags::ADVERTISED) { + self.mark_common(parent_id, graph)?; + } else { + let new_original_ttl = if entry.ttl > 0 { + entry.original_ttl + } else { + entry.original_ttl * 3 / 2 + 1 + }; + let new_ttl = if entry.ttl > 0 { entry.ttl - 1 } else { new_original_ttl }; + let parent = graph.get_mut(&parent_id).expect("present or inserted"); + if parent.data.original_ttl < new_original_ttl { + parent.data.original_ttl = new_original_ttl; + parent.data.ttl = new_ttl; + } + } + Ok(true) + } +} + +impl Negotiator for Algorithm { + fn known_common(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + if graph + .get(&id) + .map_or(false, |commit| commit.data.flags.contains(Flags::SEEN)) + { + return Ok(()); + } + self.add_to_queue(id, Flags::ADVERTISED, graph) + } + + fn add_tip(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<(), Error> { + if graph + .get(&id) + .map_or(false, |commit| commit.data.flags.contains(Flags::SEEN)) + { + return Ok(()); + } + self.add_to_queue(id, Flags::default(), graph) + } + + fn next_have(&mut self, graph: &mut crate::Graph<'_>) -> Option<Result<ObjectId, Error>> { + loop { + let id = self.revs.pop_value().filter(|_| self.non_common_revs != 0)?; + let commit = graph.get_mut(&id).expect("it was added to the graph by now"); + commit.data.flags |= Flags::POPPED; + + if !commit.data.flags.contains(Flags::COMMON) { + self.non_common_revs -= 1; + } + let mut to_send = None; + if !commit.data.flags.contains(Flags::COMMON) && commit.data.ttl == 0 { + to_send = Some(id); + } + + let data = commit.data; + let mut parent_pushed = false; + for parent_id in commit.parents.clone() { + parent_pushed |= match self.push_parent(data, parent_id, graph) { + Ok(r) => r, + Err(err) => return Some(Err(err)), + } + } + + if !data.flags.contains(Flags::COMMON) && !parent_pushed { + to_send = Some(id); + } + + if let Some(to_send) = to_send { + return Some(Ok(to_send)); + } + } + } + + fn in_common_with_remote(&mut self, id: ObjectId, graph: &mut crate::Graph<'_>) -> Result<bool, Error> { + let mut was_seen = false; + let known_to_be_common = graph.get(&id).map_or(false, |commit| { + was_seen = commit.data.flags.contains(Flags::SEEN); + commit.data.flags.contains(Flags::COMMON) + }); + assert!( + was_seen, + "Cannot receive ACK for commit we didn't send a HAVE for: {id}" + ); + self.mark_common(id, graph)?; + Ok(known_to_be_common) + } +} diff --git a/vendor/gix-negotiate/tests/baseline/mod.rs b/vendor/gix-negotiate/tests/baseline/mod.rs new file mode 100644 index 000000000..e3e209bab --- /dev/null +++ b/vendor/gix-negotiate/tests/baseline/mod.rs @@ -0,0 +1,226 @@ +use std::cell::RefCell; + +use gix_negotiate::Algorithm; +use gix_object::{bstr, bstr::ByteSlice}; +use gix_odb::{Find, FindExt}; +use gix_ref::{file::ReferenceExt, store::WriteReflog}; + +#[test] +fn run() -> crate::Result { + let root = gix_testtools::scripted_fixture_read_only("make_repos.sh")?; + for case in [ + "no_parents", + "clock_skew", + "two_colliding_skips", + "multi_round", + "advertisement_as_filter", + ] { + let base = root.join(case); + + for (algo_name, algo) in [ + ("noop", Algorithm::Noop), + ("consecutive", Algorithm::Consecutive), + ("skipping", Algorithm::Skipping), + ] { + let obj_buf = RefCell::new(Vec::new()); + let buf = std::fs::read(base.join(format!("baseline.{algo_name}")))?; + let store = gix_odb::at(base.join("client").join(".git/objects"))?; + let refs = gix_ref::file::Store::at( + base.join("client").join(".git"), + WriteReflog::Disable, + gix_hash::Kind::Sha1, + ); + let lookup_names = |names: &[&str]| -> Vec<gix_hash::ObjectId> { + names + .iter() + .filter_map(|name| { + refs.try_find(*name).expect("one tag per commit").map(|mut r| { + r.peel_to_id_in_place(&refs, |id, buf| { + store.try_find(id, buf).map(|d| d.map(|d| (d.kind, d.data))) + }) + .expect("works"); + r.target.into_id() + }) + }) + .collect() + }; + let message = |id| { + store + .find_commit(id, obj_buf.borrow_mut().as_mut()) + .expect("present") + .message + .trim() + .as_bstr() + .to_owned() + }; + + let debug = false; + for use_cache in [false, true] { + let cache = use_cache + .then(|| gix_commitgraph::at(store.store_ref().path().join("info")).ok()) + .flatten(); + let mut graph = gix_revision::Graph::new( + |id, buf| { + store + .try_find(id, buf) + .map(|r| r.and_then(|d| d.try_into_commit_iter())) + }, + cache, + ); + let mut negotiator = algo.into_negotiator(); + if debug { + eprintln!("ALGO {algo_name} CASE {case}"); + } + // // In --negotiate-only mode, which seems to be the only thing that's working after trying --dry-run, we unfortunately + // // don't get to see what happens if known-common commits are added as git itself doesn't do that in this mode + // // for some reason. + // for common in lookup_names(&["origin/main"]) { + // eprintln!("COMMON {name} {common}", name = message(common)); + // negotiator.known_common(common)?; + // } + for tip in lookup_names(&["HEAD"]).into_iter().chain( + refs.iter()? + .prefixed("refs/heads")? + .filter_map(Result::ok) + .map(|r| r.target.into_id()), + ) { + if debug { + eprintln!("TIP {name} {tip}", name = message(tip)); + } + negotiator.add_tip(tip, &mut graph)?; + } + for (round, Round { mut haves, common }) in ParseRounds::new(buf.lines()).enumerate() { + if algo == Algorithm::Skipping { + if case == "clock_skew" { + // Here for some reason the prio-queue of git manages to not sort the parent of C2, which is in the future, to be + // ahead of old4 that is in the past. In the git version of this test, they say to expect exactly this sequence + // as well even though it's not actually happening (but that they can't see due to the way they are testing). + haves = lookup_names(&["c2", "c1", "old4", "old2", "old1"]); + } else if case == "two_colliding_skips" { + // The same thing, we actually get exactly the right order, whereas git for some reason doesn't. + // This is the order expected in the git tests. + haves = lookup_names(&["c5side", "c11", "c9", "c6", "c1"]); + } else if case == "multi_round" && round == 1 { + // Here, probably also because of priority queue quirks, `git` emits the commits out of order, with only one + // branch, b5 I think, being out of place. This list puts the expectation in the right order, which is ordered + // by commit date. + haves = lookup_names(&[ + "b8.c14", "b7.c14", "b6.c14", "b5.c14", "b4.c14", "b3.c14", "b2.c14", "b8.c9", "b7.c9", + "b6.c9", "b5.c9", "b4.c9", "b3.c9", "b2.c9", "b8.c1", "b7.c1", "b6.c1", "b5.c1", + "b4.c1", "b3.c1", "b2.c1", "b8.c0", "b7.c0", "b6.c0", "b5.c0", "b4.c0", "b3.c0", + "b2.c0", + ]); + } else if case == "advertisement_as_filter" { + haves = lookup_names(&["c2side", "c5", "origin/main"]) + .into_iter() + .chain(Some( + gix_hash::ObjectId::from_hex(b"f36cefa0be2ac180d360a54b1cc4214985cea60a").unwrap(), + )) + .collect(); + } + } + for have in haves { + let actual = negotiator.next_have(&mut graph).unwrap_or_else(|| { + panic!("{algo_name}:cache={use_cache}: one have per baseline: {have} missing or in wrong order", have = message(have)) + })?; + assert_eq!( + actual, + have, + "{algo_name}:cache={use_cache}: order and commit matches exactly, wanted {expected}, got {actual}, commits left: {:?}", + std::iter::from_fn(|| negotiator.next_have(&mut graph)).map(|id| message(id.unwrap())).collect::<Vec<_>>(), + actual = message(actual), + expected = message(have) + ); + if debug { + eprintln!("have {}", message(actual)); + } + } + for common_revision in common { + if debug { + eprintln!("ACK {}", message(common_revision)); + } + negotiator.in_common_with_remote(common_revision, &mut graph)?; + } + } + assert!( + negotiator.next_have(&mut graph).is_none(), + "{algo_name}:cache={use_cache}: negotiator should be depleted after all recorded baseline rounds" + ); + } + } + } + Ok(()) +} + +struct ParseRounds<'a> { + lines: bstr::Lines<'a>, +} + +impl<'a> ParseRounds<'a> { + pub fn new(mut lines: bstr::Lines<'a>) -> Self { + parse::command(&mut lines, parse::Command::Incoming).expect("handshake"); + Self { lines } + } +} + +impl<'a> Iterator for ParseRounds<'a> { + type Item = Round; + + fn next(&mut self) -> Option<Self::Item> { + let haves = parse::object_ids("have", parse::command(&mut self.lines, parse::Command::Outgoing)?); + let common = parse::object_ids("ACK", parse::command(&mut self.lines, parse::Command::Incoming)?); + if haves.is_empty() { + assert!(common.is_empty(), "cannot ack what's not there"); + return None; + } + Round { haves, common }.into() + } +} + +struct Round { + pub haves: Vec<gix_hash::ObjectId>, + pub common: Vec<gix_hash::ObjectId>, +} + +mod parse { + use gix_object::{ + bstr, + bstr::{BStr, ByteSlice}, + }; + + #[derive(Debug, Eq, PartialEq, Copy, Clone)] + pub enum Command { + Incoming, + Outgoing, + } + + pub fn object_ids(prefix: &str, lines: impl IntoIterator<Item = impl AsRef<[u8]>>) -> Vec<gix_hash::ObjectId> { + lines + .into_iter() + .filter_map(|line| { + line.as_ref() + .strip_prefix(prefix.as_bytes()) + .map(|id| gix_hash::ObjectId::from_hex(id.trim()).expect("valid hash")) + }) + .collect() + } + + pub fn command<'a>(lines: &mut bstr::Lines<'a>, wanted: Command) -> Option<Vec<&'a BStr>> { + let mut out = Vec::new(); + for line in lines { + let pos = line.find(b"fetch").expect("fetch token"); + let line_mode = match &line[pos + 5..][..2] { + b"< " => Command::Incoming, + b"> " => Command::Outgoing, + invalid => unreachable!("invalid fetch token: {:?}", invalid.as_bstr()), + }; + assert_eq!(line_mode, wanted, "command with unexpected mode"); + let line = line[pos + 7..].as_bstr(); + if line == "0000" { + break; + } + out.push(line); + } + (!out.is_empty()).then_some(out) + } +} diff --git a/vendor/gix-negotiate/tests/fixtures/generated-archives/make_repos.tar.xz b/vendor/gix-negotiate/tests/fixtures/generated-archives/make_repos.tar.xz Binary files differnew file mode 100644 index 000000000..93e836931 --- /dev/null +++ b/vendor/gix-negotiate/tests/fixtures/generated-archives/make_repos.tar.xz diff --git a/vendor/gix-negotiate/tests/fixtures/make_repos.sh b/vendor/gix-negotiate/tests/fixtures/make_repos.sh new file mode 100644 index 000000000..b1b96527d --- /dev/null +++ b/vendor/gix-negotiate/tests/fixtures/make_repos.sh @@ -0,0 +1,146 @@ +#!/bin/bash +set -eu -o pipefail + +function tick () { + if test -z "${tick+set}" + then + tick=1112911993 + else + tick=$(($tick + 60)) + fi + GIT_COMMITTER_DATE="$tick -0700" + GIT_AUTHOR_DATE="$tick -0700" + export GIT_COMMITTER_DATE GIT_AUTHOR_DATE +} + +tick +function commit() { + local message=${1:?first argument is the commit message} + local file="$message.t" + echo "$1" > "$file" + git add -- "$file" + tick + git commit -m "$message" + git tag "$message" +} + +function negotiation_tips () { + local tips="" + for arg in "$@"; do + tips+=" --negotiation-tip=$arg" + done + echo "$tips" +} + +function trace_fetch_baseline () { + local remote="${1:?need remote url}"; shift + git -C client commit-graph write --no-progress --reachable + git -C client repack -adq + + for algo in noop consecutive skipping; do + GIT_TRACE_PACKET="$PWD/baseline.$algo" \ + git -C client -c fetch.negotiationAlgorithm="$algo" fetch --negotiate-only $(negotiation_tips "$@") \ + --upload-pack 'unset GIT_TRACE_PACKET; git-upload-pack' \ + "$remote" || : + done +} + + +(mkdir no_parents && cd no_parents + git init -q server && cd server + commit to_fetch + cd .. + + (git init -q client && cd client + for i in $(seq 7); do + commit c$i + done + ) + + trace_fetch_baseline file://$PWD/server main +) + +(mkdir two_colliding_skips && cd two_colliding_skips + git init -q server && cd server + commit to_fetch + cd .. + + (git init -q client && cd client + for i in $(seq 11); do + commit c$i + done + git checkout c5 + commit c5side + ) + + trace_fetch_baseline file://$PWD/server HEAD main +) + +(mkdir advertisement_as_filter && cd advertisement_as_filter + git init -q server && cd server + commit c1 + commit c2 + commit c3 + git tag -d c1 c2 c3 + cd .. + git clone server client && cd client + commit c4 + commit c5 + git checkout c4^^ + commit c2side + cd .. + (cd server + git checkout --orphan anotherbranch + commit to_fetch + ) + + trace_fetch_baseline origin HEAD main +) + + +(mkdir multi_round && cd multi_round + git init -q server && cd server + commit to_fetch + cd .. + + git init -q client && cd client + for i in $(seq 8); do + git checkout --orphan b$i && + commit b$i.c0 + done + + for j in $(seq 19); do + for i in $(seq 8); do + git checkout b$i && + commit b$i.c$j + done + done + cd .. + (cd server + git fetch --no-tags "$PWD/../client" b1:refs/heads/b1 + git checkout b1 + commit commit-on-b1 + ) + trace_fetch_baseline file://$PWD/server $(ls client/.git/refs/heads | sort) +) + +(mkdir clock_skew && cd clock_skew + git init -q server && cd server + commit to_fetch + cd .. + + (git init -q client && cd client + tick=2000000000 + commit c1 + commit c2 + + tick=1000000000 + git checkout c1 + commit old1 + commit old2 + commit old3 + commit old4 + ) + + trace_fetch_baseline file://$PWD/server HEAD main +) diff --git a/vendor/gix-negotiate/tests/negotiate.rs b/vendor/gix-negotiate/tests/negotiate.rs new file mode 100644 index 000000000..357b54d61 --- /dev/null +++ b/vendor/gix-negotiate/tests/negotiate.rs @@ -0,0 +1,46 @@ +use gix_testtools::Result; + +mod window_size { + use gix_negotiate::window_size; + + #[test] + fn initial_value_without_previous_window_size() { + assert_eq!(window_size(false, None), 16); + assert_eq!(window_size(true, None), 16); + } + + #[test] + fn transport_is_stateless() { + let mut ws = window_size(true, None); + for expected in [32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 18022, 19824] { + ws = window_size(true, ws); + assert_eq!(ws, expected); + } + } + + #[test] + fn transport_is_not_stateless() { + let mut ws = window_size(false, None); + for expected in [32, 64, 96] { + ws = window_size(false, ws); + assert_eq!(ws, expected); + } + + let mut ws = 4; + for expected in [8, 16, 32, 64, 96] { + ws = window_size(false, ws); + assert_eq!(ws, expected); + } + } +} + +mod baseline; + +#[test] +fn size_of_entry() { + assert_eq!( + std::mem::size_of::<gix_revision::graph::Commit<gix_negotiate::Metadata>>(), + 56, + "we may keep a lot of these, so let's not let them grow unnoticed" + ); +} |