From a4b7ed7a42c716ab9f05e351f003d589124fd55d Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:18:58 +0200 Subject: Adding upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- vendor/topological-sort/.cargo-checksum.json | 2 +- vendor/topological-sort/Cargo.toml | 29 +++++-- vendor/topological-sort/README.md | 28 ++++--- vendor/topological-sort/rustfmt.toml | 2 - vendor/topological-sort/src/lib.rs | 114 +++++++++++++++++++++------ 5 files changed, 131 insertions(+), 44 deletions(-) delete mode 100644 vendor/topological-sort/rustfmt.toml (limited to 'vendor/topological-sort') diff --git a/vendor/topological-sort/.cargo-checksum.json b/vendor/topological-sort/.cargo-checksum.json index 705676c22..ad6a9d20d 100644 --- a/vendor/topological-sort/.cargo-checksum.json +++ b/vendor/topological-sort/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"b4bfbe31191f3e86445d277cf036bc7b2318baf853e8b2b0c7fcca5d61f7a089","LICENSE-APACHE":"c6596eb7be8581c18be736c846fb9173b69eccf6ef94c5135893ec56bd92ba08","LICENSE-MIT":"bf04ecfb8f9aec247301556319593dd528886f67bb9ad81654025d12b20d9e01","README.md":"fb45c72e0317c713589e90b028324c0b7320b6eb7aebbbefd31ade38aaf7e1e2","rustfmt.toml":"785022765c76126d4a9954f880c30cc651b3895857ffcfed55ce8a4f8cf3f61a","src/lib.rs":"aaa8b5ff915f1c6e3132bef12afacede4fc91216fe0711efbd1ead7ab106e82e"},"package":"aa7c7f42dea4b1b99439786f5633aeb9c14c1b53f75e282803c2ec2ad545873c"} \ No newline at end of file +{"files":{"Cargo.toml":"1a1195f769925a98778e458ca53f305818ab4f0dd339386ec80f50a2f333fc96","LICENSE-APACHE":"c6596eb7be8581c18be736c846fb9173b69eccf6ef94c5135893ec56bd92ba08","LICENSE-MIT":"bf04ecfb8f9aec247301556319593dd528886f67bb9ad81654025d12b20d9e01","README.md":"49604355f516cc2d4a9088f95f7531daba8abba411b81795c4ded2e38033dea7","src/lib.rs":"539c8d3b3d827c49add1588e32a77ffa4a011d161c310c605bcdf3c02349e387"},"package":"ea68304e134ecd095ac6c3574494fc62b909f416c4fca77e440530221e549d3d"} \ No newline at end of file diff --git a/vendor/topological-sort/Cargo.toml b/vendor/topological-sort/Cargo.toml index 1526eb8c6..988faf850 100644 --- a/vendor/topological-sort/Cargo.toml +++ b/vendor/topological-sort/Cargo.toml @@ -3,19 +3,34 @@ # 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 +# to registry (e.g., crates.io) dependencies. # -# If you believe there's an error in this file please file an -# issue against the rust-lang/cargo repository. If you're -# editing this file be aware that the upstream Cargo.toml -# will likely look very different (and much more reasonable) +# 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 = "2018" +rust-version = "1.43.1" name = "topological-sort" -version = "0.1.0" +version = "0.2.2" authors = ["gifnksm "] description = "Performs topological sorting." -documentation = "https://docs.rs/topological-sort/~0.0" +documentation = "https://docs.rs/topological-sort" readme = "README.md" license = "MIT OR Apache-2.0" repository = "https://github.com/gifnksm/topological-sort-rs" + +[[package.metadata.release.pre-release-replacements]] +file = "README.md" +search = 'topological-sort = "[0-9\.]+"' +replace = "{{crate_name}} = \"{{version}}\"" + +[dev-dependencies.quickcheck] +version = "1.0.3" + +[dev-dependencies.quickcheck_macros] +version = "1.0.0" + +[badges.maintenance] +status = "passively-maintained" diff --git a/vendor/topological-sort/README.md b/vendor/topological-sort/README.md index 87dd7bea5..d20cc360f 100644 --- a/vendor/topological-sort/README.md +++ b/vendor/topological-sort/README.md @@ -1,12 +1,16 @@ # topological-sort-rs -[![Build Status](https://travis-ci.org/gifnksm/topological-sort-rs.svg)](https://travis-ci.org/gifnksm/topological-sort-rs) -[![Coverage Status](https://coveralls.io/repos/gifnksm/topological-sort-rs/badge.svg?branch=master&service=github)](https://coveralls.io/github/gifnksm/topological-sort-rs?branch=master) -[![crates.io](http://meritbadge.herokuapp.com/topological-sort)](https://crates.io/crates/topological-sort) +[![maintenance status: passively-maintained](https://img.shields.io/badge/maintenance-passively--maintained-yellowgreen.svg)](https://doc.rust-lang.org/cargo/reference/manifest.html#the-badges-section) +[![license](https://img.shields.io/crates/l/topological-sort.svg)](#license) +[![crates.io](https://img.shields.io/crates/v/topological-sort.svg)](https://crates.io/crates/topological-sort) +[![docs.rs](https://img.shields.io/docsrs/topological-sort/latest)](https://docs.rs/topological-sort/latest/) +[![rust 1.43.1+ badge](https://img.shields.io/badge/rust-1.43.1+-93450a.svg)](https://doc.rust-lang.org/cargo/reference/manifest.html#the-rust-version-field) +[![Rust CI](https://github.com/gifnksm/topological-sort-rs/actions/workflows/rust-ci.yml/badge.svg)](https://github.com/gifnksm/topological-sort-rs/actions/workflows/rust-ci.yml) +[![Codecov](https://codecov.io/gh/gifnksm/topological-sort-rs/branch/master/graph/badge.svg?token=VreVOoM3Yb)](https://codecov.io/gh/gifnksm/topological-sort-rs) Performs topological sorting. -[Documentation](https://docs.rs/topological-sort/~0.0) +[Documentation](https://docs.rs/topological-sort) ## How to use? @@ -14,21 +18,23 @@ Add this to your `Cargo.toml`: ```toml [dependencies] -topological-sort = "0.0" +topological-sort = "0.2.2" ``` -and this to your crate root: +## Minimum supported Rust version (MSRV) -```rust -extern crate topological_sort; -``` +The minimum supported Rust version is **Rust 1.43.1**. +At least the last 3 versions of stable Rust are supported at any given time. + +While a crate is pre-release status (0.x.x) it may have its MSRV bumped in a patch release. +Once a crate has reached 1.x, any MSRV bump will be accompanied with a new minor version. ## License Licensed under either of - * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0) - * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) +* Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or ) +* MIT license ([LICENSE-MIT](LICENSE-MIT) or ) at your option. diff --git a/vendor/topological-sort/rustfmt.toml b/vendor/topological-sort/rustfmt.toml deleted file mode 100644 index 0468aa587..000000000 --- a/vendor/topological-sort/rustfmt.toml +++ /dev/null @@ -1,2 +0,0 @@ -reorder_imports = true -reorder_imported_names = true diff --git a/vendor/topological-sort/src/lib.rs b/vendor/topological-sort/src/lib.rs index 08b04aab1..625aef0f8 100644 --- a/vendor/topological-sort/src/lib.rs +++ b/vendor/topological-sort/src/lib.rs @@ -1,8 +1,8 @@ // Copyright 2016 oauth-client-rs Developers // // Licensed under the Apache License, Version 2.0, or the MIT license , at your option. This file may not be +// https://apache.org/licenses/LICENSE-2.0> or the MIT license , at your option. This file may not be // copied, modified, or distributed except according to those terms. //! Performs topological sorting. @@ -18,21 +18,17 @@ #![warn(unused_import_braces)] #![warn(unused_qualifications)] #![warn(unused_results)] -#![cfg_attr(feature = "cargo-clippy", warn(if_not_else))] -#![cfg_attr(feature = "cargo-clippy", warn(invalid_upcast_comparisons))] -#![cfg_attr(feature = "cargo-clippy", warn(items_after_statements))] -#![cfg_attr(feature = "cargo-clippy", warn(mut_mut))] -#![cfg_attr(feature = "cargo-clippy", warn(never_loop))] -#![cfg_attr(feature = "cargo-clippy", warn(nonminimal_bool))] -#![cfg_attr(feature = "cargo-clippy", warn(option_map_unwrap_or))] -#![cfg_attr(feature = "cargo-clippy", warn(option_map_unwrap_or_else))] -#![cfg_attr(feature = "cargo-clippy", warn(option_unwrap_used))] -#![cfg_attr(feature = "cargo-clippy", warn(result_unwrap_used))] -#![cfg_attr(feature = "cargo-clippy", warn(used_underscore_binding))] +#![warn(clippy::if_not_else)] +#![warn(clippy::invalid_upcast_comparisons)] +#![warn(clippy::items_after_statements)] +#![warn(clippy::mut_mut)] +#![warn(clippy::never_loop)] +#![warn(clippy::nonminimal_bool)] +#![warn(clippy::used_underscore_binding)] use std::cmp::Ordering; -use std::collections::{HashMap, HashSet}; use std::collections::hash_map::Entry; +use std::collections::{HashMap, HashSet}; use std::fmt; use std::hash::Hash; use std::iter::FromIterator; @@ -52,14 +48,20 @@ impl Dependency { } } - - /// Performs topological sorting. #[derive(Clone)] pub struct TopologicalSort { top: HashMap>, } +impl Default for TopologicalSort { + fn default() -> TopologicalSort { + TopologicalSort { + top: HashMap::new(), + } + } +} + impl TopologicalSort { /// Creates new empty `TopologicalSort`. /// @@ -83,9 +85,7 @@ impl TopologicalSort { /// ``` #[inline] pub fn new() -> TopologicalSort { - TopologicalSort { - top: HashMap::new(), - } + Default::default() } /// Returns the number of elements in the `TopologicalSort`. @@ -176,13 +176,13 @@ impl TopologicalSort { }) } - /// Removes all items that are not depended on by any other items and returns it, or empty /// vector if there are no such items. /// /// If `pop_all` returns an empty vector and `len` is not 0, there is cyclic dependencies. pub fn pop_all(&mut self) -> Vec { - let keys = self.top + let keys = self + .top .iter() .filter(|&(_, v)| v.num_prec == 0) .map(|(k, _)| k.clone()) @@ -213,7 +213,6 @@ impl TopologicalSort { .collect::>() } - fn remove(&mut self, prec: &T) -> Option> { let result = self.top.remove(prec); if let Some(ref p) = result { @@ -298,10 +297,10 @@ impl fmt::Debug for TopologicalSort { } } - #[cfg(test)] mod test { use super::TopologicalSort; + use quickcheck_macros::quickcheck; use std::iter::FromIterator; #[test] @@ -381,4 +380,73 @@ mod test { assert!(ts.pop().is_none()); println!("{:?}", ts); } + + #[quickcheck] + fn topo_test_quickcheck(n: usize, edges: Vec<(usize, usize)>) { + use std::collections::{HashMap, HashSet}; + + let n = n.max(1).min(1000); + let mut marked = vec![false; n]; + let edges = edges + .into_iter() + .map(|(x, y)| (x % n, y % n)) + .collect::>(); + let mut deps = HashMap::new(); + let mut toposort = TopologicalSort::::new(); + + for i in 0..n { + let _ = deps.insert(i, HashSet::new()); + assert!(toposort.insert(i)); + } + + for (op, inp) in edges.iter().map(|(x, y)| (y, x)) { + let inps = deps.get_mut(op).unwrap(); + let _ = inps.insert(*inp); + } + + let deps = deps; + for (inp, op) in edges { + toposort.add_dependency(inp, op); + } + while let Some(x) = toposort.pop() { + for dep in deps.get(&x).unwrap().iter() { + assert!(marked[*dep]); + } + marked[x] = true; + } + + if toposort.is_empty() { + assert!(marked.into_iter().all(|x| x)); + } else { + let dep_fixed = { + let mut ret = (0..n) + .map(|i| (i, HashSet::new())) + .collect::>(); + let mut new_to_add = deps; + + while !new_to_add.is_empty() { + for (k, v) in new_to_add.drain() { + let inps = ret.get_mut(&k).unwrap(); + inps.extend(v.into_iter()); + } + for (k, vs) in ret.iter() { + for k2 in vs.iter() { + for v2 in ret.get(k2).unwrap().iter() { + if !vs.contains(v2) { + let _ = new_to_add + .entry(*k) + .or_insert_with(HashSet::new) + .insert(*v2); + } + } + } + } + } + + ret + }; + + assert!(dep_fixed.into_iter().any(|(op, deps)| deps.contains(&op))); + } + } } -- cgit v1.2.3