Merging upstream version 1.68.2+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 91 insertions, 23 deletions

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, <LICENSE-APACHE or
-// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
-// http://opensource.org/licenses/MIT>, at your option. This file may not be
+// https://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
+// https://opensource.org/licenses/MIT>, 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<T: Hash + Eq> Dependency<T> {
     }
 }
 
-
-
 /// Performs topological sorting.
 #[derive(Clone)]
 pub struct TopologicalSort<T> {
     top: HashMap<T, Dependency<T>>,
 }
 
+impl<T> Default for TopologicalSort<T> {
+    fn default() -> TopologicalSort<T> {
+        TopologicalSort {
+            top: HashMap::new(),
+        }
+    }
+}
+
 impl<T: Hash + Eq + Clone> TopologicalSort<T> {
     /// Creates new empty `TopologicalSort`.
     ///
@@ -83,9 +85,7 @@ impl<T: Hash + Eq + Clone> TopologicalSort<T> {
     /// ```
     #[inline]
     pub fn new() -> TopologicalSort<T> {
-        TopologicalSort {
-            top: HashMap::new(),
-        }
+        Default::default()
     }
 
     /// Returns the number of elements in the `TopologicalSort`.
@@ -176,13 +176,13 @@ impl<T: Hash + Eq + Clone> TopologicalSort<T> {
         })
     }
 
-
     /// 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<T> {
-        let keys = self.top
+        let keys = self
+            .top
             .iter()
             .filter(|&(_, v)| v.num_prec == 0)
             .map(|(k, _)| k.clone())
@@ -213,7 +213,6 @@ impl<T: Hash + Eq + Clone> TopologicalSort<T> {
             .collect::<Vec<_>>()
     }
 
-
     fn remove(&mut self, prec: &T) -> Option<Dependency<T>> {
         let result = self.top.remove(prec);
         if let Some(ref p) = result {
@@ -298,10 +297,10 @@ impl<T: fmt::Debug + Hash + Eq + Clone> fmt::Debug for TopologicalSort<T> {
     }
 }
 
-
 #[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::<Vec<_>>();
+        let mut deps = HashMap::new();
+        let mut toposort = TopologicalSort::<usize>::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::<HashMap<_, _>>();
+                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)));
+        }
+    }
 }