Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

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

1 files changed, 384 insertions, 0 deletions

diff --git a/third_party/rust/topological-sort/src/lib.rs b/third_party/rust/topological-sort/src/lib.rs
new file mode 100644
index 0000000000..08b04aab15
--- /dev/null
+++ b/third_party/rust/topological-sort/src/lib.rs
@@ -0,0 +1,384 @@
+// 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
+// copied, modified, or distributed except according to those terms.
+
+//! Performs topological sorting.
+
+#![warn(bad_style)]
+#![warn(missing_copy_implementations)]
+#![warn(missing_debug_implementations)]
+#![warn(missing_docs)]
+#![warn(trivial_casts)]
+#![warn(trivial_numeric_casts)]
+#![warn(unused)]
+#![warn(unused_extern_crates)]
+#![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))]
+
+use std::cmp::Ordering;
+use std::collections::{HashMap, HashSet};
+use std::collections::hash_map::Entry;
+use std::fmt;
+use std::hash::Hash;
+use std::iter::FromIterator;
+
+#[derive(Clone)]
+struct Dependency<T> {
+    num_prec: usize,
+    succ: HashSet<T>,
+}
+
+impl<T: Hash + Eq> Dependency<T> {
+    fn new() -> Dependency<T> {
+        Dependency {
+            num_prec: 0,
+            succ: HashSet::new(),
+        }
+    }
+}
+
+
+
+/// Performs topological sorting.
+#[derive(Clone)]
+pub struct TopologicalSort<T> {
+    top: HashMap<T, Dependency<T>>,
+}
+
+impl<T: Hash + Eq + Clone> TopologicalSort<T> {
+    /// Creates new empty `TopologicalSort`.
+    ///
+    /// ```rust
+    /// # extern crate topological_sort;
+    /// # fn main() {
+    /// use topological_sort::TopologicalSort;
+    /// let mut ts = TopologicalSort::<&str>::new();
+    /// ts.add_dependency("hello_world.o", "hello_world");
+    /// ts.add_dependency("hello_world.c", "hello_world");
+    /// ts.add_dependency("stdio.h", "hello_world.o");
+    /// ts.add_dependency("glibc.so", "hello_world");
+    /// assert_eq!(vec!["glibc.so", "hello_world.c", "stdio.h"],
+    ///            { let mut v = ts.pop_all(); v.sort(); v });
+    /// assert_eq!(vec!["hello_world.o"],
+    ///            { let mut v = ts.pop_all(); v.sort(); v });
+    /// assert_eq!(vec!["hello_world"],
+    ///            { let mut v = ts.pop_all(); v.sort(); v });
+    /// assert!(ts.pop_all().is_empty());
+    /// # }
+    /// ```
+    #[inline]
+    pub fn new() -> TopologicalSort<T> {
+        TopologicalSort {
+            top: HashMap::new(),
+        }
+    }
+
+    /// Returns the number of elements in the `TopologicalSort`.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.top.len()
+    }
+
+    /// Returns true if the `TopologicalSort` contains no elements.
+    #[inline]
+    pub fn is_empty(&self) -> bool {
+        self.top.is_empty()
+    }
+
+    /// Registers the two elements' dependency.
+    ///
+    /// # Arguments
+    ///
+    /// * `prec` - The element appears before `succ`. `prec` is depended on by `succ`.
+    /// * `succ` - The element appears after `prec`. `succ` depends on `prec`.
+    pub fn add_dependency<P, S>(&mut self, prec: P, succ: S)
+    where
+        P: Into<T>,
+        S: Into<T>,
+    {
+        self.add_dependency_impl(prec.into(), succ.into())
+    }
+
+    fn add_dependency_impl(&mut self, prec: T, succ: T) {
+        match self.top.entry(prec) {
+            Entry::Vacant(e) => {
+                let mut dep = Dependency::new();
+                let _ = dep.succ.insert(succ.clone());
+                let _ = e.insert(dep);
+            }
+            Entry::Occupied(e) => {
+                if !e.into_mut().succ.insert(succ.clone()) {
+                    // Already registered
+                    return;
+                }
+            }
+        }
+
+        match self.top.entry(succ) {
+            Entry::Vacant(e) => {
+                let mut dep = Dependency::new();
+                dep.num_prec += 1;
+                let _ = e.insert(dep);
+            }
+            Entry::Occupied(e) => {
+                e.into_mut().num_prec += 1;
+            }
+        }
+    }
+
+    /// Registers a dependency link.
+    pub fn add_link(&mut self, link: DependencyLink<T>) {
+        self.add_dependency(link.prec, link.succ)
+    }
+
+    /// Inserts an element, without adding any dependencies from or to it.
+    ///
+    /// If the `TopologicalSort` did not have this element present, `true` is returned.
+    ///
+    /// If the `TopologicalSort` already had this element present, `false` is returned.
+    pub fn insert<U>(&mut self, elt: U) -> bool
+    where
+        U: Into<T>,
+    {
+        match self.top.entry(elt.into()) {
+            Entry::Vacant(e) => {
+                let dep = Dependency::new();
+                let _ = e.insert(dep);
+                true
+            }
+            Entry::Occupied(_) => false,
+        }
+    }
+
+    /// Removes the item that is not depended on by any other items and returns it, or `None` if
+    /// there is no such item.
+    ///
+    /// If `pop` returns `None` and `len` is not 0, there is cyclic dependencies.
+    pub fn pop(&mut self) -> Option<T> {
+        self.peek().map(T::clone).map(|key| {
+            let _ = self.remove(&key);
+            key
+        })
+    }
+
+
+    /// 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
+            .iter()
+            .filter(|&(_, v)| v.num_prec == 0)
+            .map(|(k, _)| k.clone())
+            .collect::<Vec<_>>();
+        for k in &keys {
+            let _ = self.remove(k);
+        }
+        keys
+    }
+
+    /// Return a reference to the first item that does not depend on any other items, or `None` if
+    /// there is no such item.
+    pub fn peek(&self) -> Option<&T> {
+        self.top
+            .iter()
+            .filter(|&(_, v)| v.num_prec == 0)
+            .map(|(k, _)| k)
+            .next()
+    }
+
+    /// Return a vector of references to all items that do not depend on any other items, or an
+    /// empty vector if there are no such items.
+    pub fn peek_all(&self) -> Vec<&T> {
+        self.top
+            .iter()
+            .filter(|&(_, v)| v.num_prec == 0)
+            .map(|(k, _)| k)
+            .collect::<Vec<_>>()
+    }
+
+
+    fn remove(&mut self, prec: &T) -> Option<Dependency<T>> {
+        let result = self.top.remove(prec);
+        if let Some(ref p) = result {
+            for s in &p.succ {
+                if let Some(y) = self.top.get_mut(s) {
+                    y.num_prec -= 1;
+                }
+            }
+        }
+        result
+    }
+}
+
+impl<T: PartialOrd + Eq + Hash + Clone> FromIterator<T> for TopologicalSort<T> {
+    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> TopologicalSort<T> {
+        let mut top = TopologicalSort::new();
+        let mut seen = Vec::<T>::default();
+        for item in iter {
+            let _ = top.insert(item.clone());
+            for seen_item in seen.iter().cloned() {
+                match seen_item.partial_cmp(&item) {
+                    Some(Ordering::Less) => {
+                        top.add_dependency(seen_item, item.clone());
+                    }
+                    Some(Ordering::Greater) => {
+                        top.add_dependency(item.clone(), seen_item);
+                    }
+                    _ => (),
+                }
+            }
+            seen.push(item);
+        }
+        top
+    }
+}
+
+/// A link between two items in a sort.
+#[derive(Copy, Clone, Debug)]
+pub struct DependencyLink<T> {
+    /// The element which is depened upon by `succ`.
+    pub prec: T,
+    /// The element which depends on `prec`.
+    pub succ: T,
+}
+
+impl<T> From<(T, T)> for DependencyLink<T> {
+    fn from(tuple: (T, T)) -> Self {
+        DependencyLink {
+            succ: tuple.0,
+            prec: tuple.1,
+        }
+    }
+}
+
+impl<T: Eq + Hash + Clone> FromIterator<DependencyLink<T>> for TopologicalSort<T> {
+    fn from_iter<I: IntoIterator<Item = DependencyLink<T>>>(iter: I) -> TopologicalSort<T> {
+        let mut top = TopologicalSort::new();
+        for link in iter {
+            top.add_link(link);
+        }
+        top
+    }
+}
+
+impl<T: Hash + Eq + Clone> Iterator for TopologicalSort<T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        self.pop()
+    }
+}
+
+impl<T: fmt::Debug + Hash + Eq> fmt::Debug for Dependency<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "prec={}, succ={:?}", self.num_prec, self.succ)
+    }
+}
+
+impl<T: fmt::Debug + Hash + Eq + Clone> fmt::Debug for TopologicalSort<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{:?}", self.top)
+    }
+}
+
+
+#[cfg(test)]
+mod test {
+    use super::TopologicalSort;
+    use std::iter::FromIterator;
+
+    #[test]
+    fn from_iter() {
+        let t = vec![4, 3, 3, 5, 7, 6, 8];
+        let mut ts = TopologicalSort::<i32>::from_iter(t);
+        assert_eq!(Some(3), ts.next());
+        assert_eq!(Some(4), ts.next());
+        assert_eq!(Some(5), ts.next());
+        assert_eq!(Some(6), ts.next());
+        assert_eq!(Some(7), ts.next());
+        assert_eq!(Some(8), ts.next());
+        assert_eq!(None, ts.next());
+    }
+
+    #[test]
+    fn iter() {
+        let mut ts = TopologicalSort::<i32>::new();
+        ts.add_dependency(1, 2);
+        ts.add_dependency(2, 3);
+        ts.add_dependency(3, 4);
+        assert_eq!(Some(1), ts.next());
+        assert_eq!(Some(2), ts.next());
+        assert_eq!(Some(3), ts.next());
+        assert_eq!(Some(4), ts.next());
+        assert_eq!(None, ts.next());
+    }
+
+    #[test]
+    fn pop_all() {
+        fn check(result: &[i32], ts: &mut TopologicalSort<i32>) {
+            let l = ts.len();
+            let mut v = ts.pop_all();
+            v.sort();
+            assert_eq!(result, &v[..]);
+            assert_eq!(l - result.len(), ts.len());
+        }
+
+        let mut ts = TopologicalSort::new();
+        ts.add_dependency(7, 11);
+        assert_eq!(2, ts.len());
+        ts.add_dependency(7, 8);
+        assert_eq!(3, ts.len());
+        ts.add_dependency(5, 11);
+        assert_eq!(4, ts.len());
+        ts.add_dependency(3, 8);
+        assert_eq!(5, ts.len());
+        ts.add_dependency(3, 10);
+        assert_eq!(6, ts.len());
+        ts.add_dependency(11, 2);
+        assert_eq!(7, ts.len());
+        ts.add_dependency(11, 9);
+        assert_eq!(8, ts.len());
+        ts.add_dependency(11, 10);
+        assert_eq!(8, ts.len());
+        ts.add_dependency(8, 9);
+        assert_eq!(8, ts.len());
+
+        check(&[3, 5, 7], &mut ts);
+        check(&[8, 11], &mut ts);
+        check(&[2, 9, 10], &mut ts);
+        check(&[], &mut ts);
+    }
+
+    #[test]
+    fn cyclic_deadlock() {
+        let mut ts = TopologicalSort::new();
+        ts.add_dependency("stone", "sharp");
+
+        ts.add_dependency("bucket", "hole");
+        ts.add_dependency("hole", "straw");
+        ts.add_dependency("straw", "axe");
+        ts.add_dependency("axe", "sharp");
+        ts.add_dependency("sharp", "water");
+        ts.add_dependency("water", "bucket");
+        assert_eq!(ts.pop(), Some("stone"));
+        assert!(ts.pop().is_none());
+        println!("{:?}", ts);
+    }
+}