Merge "Upgrade num-integer to 0.1.45"

8 files changed, 118 insertions, 47 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 14ea4d6..023cb81 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,5 +1,6 @@
 {
   "git": {
-    "sha1": "4d166cbb754244760e28ea4ce826d54fafd3e629"
-  }
-}
+    "sha1": "683903c79f21b196f4ee3a19e7cf0151021cc6c3"
+  },
+  "path_in_vcs": ""
+}
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index 4e731fd..2d4fd2e 100644
--- a/Android.bp
+++ b/Android.bp
@@ -39,11 +39,10 @@ license {
 
 rust_library {
     name: "libnum_integer",
-    // has rustc warnings
     host_supported: true,
     crate_name: "num_integer",
     cargo_env_compat: true,
-    cargo_pkg_version: "0.1.44",
+    cargo_pkg_version: "0.1.45",
     srcs: ["src/lib.rs"],
     edition: "2015",
     features: [
@@ -63,11 +62,10 @@ rust_library {
 
 rust_test {
     name: "num-integer_test_src_lib",
-    // has rustc warnings
     host_supported: true,
     crate_name: "num_integer",
     cargo_env_compat: true,
-    cargo_pkg_version: "0.1.44",
+    cargo_pkg_version: "0.1.45",
     srcs: ["src/lib.rs"],
     test_suites: ["general-tests"],
     auto_gen_config: true,
@@ -89,7 +87,7 @@ rust_defaults {
     name: "num-integer_test_defaults",
     crate_name: "num_integer",
     cargo_env_compat: true,
-    cargo_pkg_version: "0.1.44",
+    cargo_pkg_version: "0.1.45",
     test_suites: ["general-tests"],
     auto_gen_config: true,
     edition: "2015",
@@ -107,7 +105,6 @@ rust_defaults {
 rust_test {
     name: "num-integer_test_tests_average",
     defaults: ["num-integer_test_defaults"],
-    // has rustc warnings
     host_supported: true,
     srcs: ["tests/average.rs"],
     test_options: {
@@ -118,7 +115,6 @@ rust_test {
 rust_test {
     name: "num-integer_test_tests_roots",
     defaults: ["num-integer_test_defaults"],
-    // has rustc warnings
     host_supported: true,
     srcs: ["tests/roots.rs"],
     test_options: {
diff --git a/Cargo.toml b/Cargo.toml
index 8f72e39..51a1a3e 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -3,32 +3,45 @@
 # 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]
 name = "num-integer"
-version = "0.1.44"
+version = "0.1.45"
 authors = ["The Rust Project Developers"]
 build = "build.rs"
-exclude = ["/bors.toml", "/ci/*", "/.github/*"]
+exclude = [
+    "/bors.toml",
+    "/ci/*",
+    "/.github/*",
+]
 description = "Integer traits and functions"
 homepage = "https://github.com/rust-num/num-integer"
 documentation = "https://docs.rs/num-integer"
 readme = "README.md"
-keywords = ["mathematics", "numerics"]
-categories = ["algorithms", "science", "no-std"]
+keywords = [
+    "mathematics",
+    "numerics",
+]
+categories = [
+    "algorithms",
+    "science",
+    "no-std",
+]
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/rust-num/num-integer"
+
 [package.metadata.docs.rs]
 features = ["std"]
+
 [dependencies.num-traits]
 version = "0.2.11"
 default-features = false
+
 [build-dependencies.autocfg]
 version = "1"
 
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index 4ff8291..f5aac54 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -8,7 +8,7 @@ categories = ["algorithms", "science", "no-std"]
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/rust-num/num-integer"
 name = "num-integer"
-version = "0.1.44"
+version = "0.1.45"
 readme = "README.md"
 build = "build.rs"
 exclude = ["/bors.toml", "/ci/*", "/.github/*"]
diff --git a/METADATA b/METADATA
index 16e112f..cf4e458 100644
--- a/METADATA
+++ b/METADATA
@@ -1,3 +1,7 @@
+# This project was upgraded with external_updater.
+# Usage: tools/external_updater/updater.sh update rust/crates/num-integer
+# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md
+
 name: "num-integer"
 description: "Integer traits and functions"
 third_party {
@@ -7,13 +11,13 @@ third_party {
   }
   url {
     type: ARCHIVE
-    value: "https://static.crates.io/crates/num-integer/num-integer-0.1.44.crate"
+    value: "https://static.crates.io/crates/num-integer/num-integer-0.1.45.crate"
   }
-  version: "0.1.44"
+  version: "0.1.45"
   license_type: NOTICE
   last_upgrade_date {
-    year: 2021
-    month: 1
-    day: 28
+    year: 2022
+    month: 12
+    day: 13
   }
 }
diff --git a/RELEASES.md b/RELEASES.md
index 05be073..05c649b 100644
--- a/RELEASES.md
+++ b/RELEASES.md
@@ -1,3 +1,17 @@
+# Release 0.1.45 (2022-04-29)
+
+- [`Integer::next_multiple_of` and `prev_multiple_of` no longer overflow -1][45].
+- [`Integer::is_multiple_of` now handles a 0 argument without panicking][47]
+  for primitive integers.
+- [`ExtendedGcd` no longer has any private fields][46], making it possible for
+  external implementations to customize `Integer::extended_gcd`.
+
+**Contributors**: @ciphergoth, @cuviper, @tspiteri, @WizardOfMenlo
+
+[45]: https://github.com/rust-num/num-integer/pull/45
+[46]: https://github.com/rust-num/num-integer/pull/46
+[47]: https://github.com/rust-num/num-integer/pull/47
+
 # Release 0.1.44 (2020-10-29)
 
 - [The "i128" feature now bypasses compiler probing][35]. The build script
diff --git a/benches/average.rs b/benches/average.rs
index 05d824c..649078c 100644
--- a/benches/average.rs
+++ b/benches/average.rs
@@ -53,28 +53,28 @@ macro_rules! naive_average {
         impl super::NaiveAverage for $T {
             fn naive_average_floor(&self, other: &$T) -> $T {
                 match self.checked_add(*other) {
-                    Some(z) => z.div_floor(&2),
+                    Some(z) => Integer::div_floor(&z, &2),
                     None => {
                         if self > other {
                             let diff = self - other;
-                            other + diff.div_floor(&2)
+                            other + Integer::div_floor(&diff, &2)
                         } else {
                             let diff = other - self;
-                            self + diff.div_floor(&2)
+                            self + Integer::div_floor(&diff, &2)
                         }
                     }
                 }
             }
             fn naive_average_ceil(&self, other: &$T) -> $T {
                 match self.checked_add(*other) {
-                    Some(z) => z.div_ceil(&2),
+                    Some(z) => Integer::div_ceil(&z, &2),
                     None => {
                         if self > other {
                             let diff = self - other;
-                            self - diff.div_floor(&2)
+                            self - Integer::div_floor(&diff, &2)
                         } else {
                             let diff = other - self;
-                            other - diff.div_floor(&2)
+                            other - Integer::div_floor(&diff, &2)
                         }
                     }
                 }
diff --git a/src/lib.rs b/src/lib.rs
index 0281954..5005801 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -187,14 +187,12 @@ pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
                 gcd: r.1,
                 x: s.1,
                 y: t.1,
-                _hidden: (),
             }
         } else {
             ExtendedGcd {
                 gcd: Self::zero() - r.1,
                 x: Self::zero() - s.1,
                 y: Self::zero() - t.1,
-                _hidden: (),
             }
         }
     }
@@ -356,7 +354,6 @@ pub struct ExtendedGcd<A> {
     pub gcd: A,
     pub x: A,
     pub y: A,
-    _hidden: (),
 }
 
 /// Simultaneous integer division and modulus
@@ -386,7 +383,7 @@ pub fn div_ceil<T: Integer>(x: T, y: T) -> T {
 }
 
 /// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The
-/// result is always positive.
+/// result is always non-negative.
 #[inline(always)]
 pub fn gcd<T: Integer>(x: T, y: T) -> T {
     x.gcd(&y)
@@ -457,7 +454,7 @@ macro_rules! impl_integer_for_isize {
             }
 
             /// Calculates the Greatest Common Divisor (GCD) of the number and
-            /// `other`. The result is always positive.
+            /// `other`. The result is always non-negative.
             #[inline]
             fn gcd(&self, other: &Self) -> Self {
                 // Use Stein's algorithm
@@ -543,6 +540,9 @@ macro_rules! impl_integer_for_isize {
             /// Returns `true` if the number is a multiple of `other`.
             #[inline]
             fn is_multiple_of(&self, other: &Self) -> bool {
+                if other.is_zero() {
+                    return self.is_zero();
+                }
                 *self % *other == 0
             }
 
@@ -563,6 +563,29 @@ macro_rules! impl_integer_for_isize {
             fn div_rem(&self, other: &Self) -> (Self, Self) {
                 (*self / *other, *self % *other)
             }
+
+            /// Rounds up to nearest multiple of argument.
+            #[inline]
+            fn next_multiple_of(&self, other: &Self) -> Self {
+                // Avoid the overflow of `MIN % -1`
+                if *other == -1 {
+                    return *self;
+                }
+
+                let m = Integer::mod_floor(self, other);
+                *self + if m == 0 { 0 } else { other - m }
+            }
+
+            /// Rounds down to nearest multiple of argument.
+            #[inline]
+            fn prev_multiple_of(&self, other: &Self) -> Self {
+                // Avoid the overflow of `MIN % -1`
+                if *other == -1 {
+                    return *self;
+                }
+
+                *self - Integer::mod_floor(self, other)
+            }
         }
 
         #[cfg(test)]
@@ -609,8 +632,9 @@ macro_rules! impl_integer_for_isize {
             fn test_div_mod_floor() {
                 fn test_nd_dm(nd: ($T, $T), dm: ($T, $T)) {
                     let (n, d) = nd;
-                    let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
-                    let combined_div_mod_floor = n.div_mod_floor(&d);
+                    let separate_div_mod_floor =
+                        (Integer::div_floor(&n, &d), Integer::mod_floor(&n, &d));
+                    let combined_div_mod_floor = Integer::div_mod_floor(&n, &d);
 
                     assert_eq!(separate_div_mod_floor, dm);
                     assert_eq!(combined_div_mod_floor, dm);
@@ -784,6 +808,16 @@ macro_rules! impl_integer_for_isize {
                 assert_eq!((3 as $T).is_odd(), true);
                 assert_eq!((4 as $T).is_odd(), false);
             }
+
+            #[test]
+            fn test_multiple_of_one_limits() {
+                for x in &[<$T>::min_value(), <$T>::max_value()] {
+                    for one in &[1, -1] {
+                        assert_eq!(Integer::next_multiple_of(x, one), *x);
+                        assert_eq!(Integer::prev_multiple_of(x, one), *x);
+                    }
+                }
+            }
         }
     };
 }
@@ -884,6 +918,9 @@ macro_rules! impl_integer_for_usize {
             /// Returns `true` if the number is a multiple of `other`.
             #[inline]
             fn is_multiple_of(&self, other: &Self) -> bool {
+                if other.is_zero() {
+                    return self.is_zero();
+                }
                 *self % *other == 0
             }
 
@@ -913,15 +950,16 @@ macro_rules! impl_integer_for_usize {
 
             #[test]
             fn test_div_mod_floor() {
-                assert_eq!((10 as $T).div_floor(&(3 as $T)), 3 as $T);
-                assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T);
-                assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T));
-                assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T);
-                assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T);
-                assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T));
-                assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T);
-                assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T);
-                assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (0 as $T, 3 as $T));
+                assert_eq!(<$T as Integer>::div_floor(&10, &3), 3 as $T);
+                assert_eq!(<$T as Integer>::mod_floor(&10, &3), 1 as $T);
+                assert_eq!(<$T as Integer>::div_mod_floor(&10, &3), (3 as $T, 1 as $T));
+                assert_eq!(<$T as Integer>::div_floor(&5, &5), 1 as $T);
+                assert_eq!(<$T as Integer>::mod_floor(&5, &5), 0 as $T);
+                assert_eq!(<$T as Integer>::div_mod_floor(&5, &5), (1 as $T, 0 as $T));
+                assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T);
+                assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T);
+                assert_eq!(<$T as Integer>::mod_floor(&3, &7), 3 as $T);
+                assert_eq!(<$T as Integer>::div_mod_floor(&3, &7), (0 as $T, 3 as $T));
             }
 
             #[test]
@@ -979,9 +1017,14 @@ macro_rules! impl_integer_for_usize {
 
             #[test]
             fn test_is_multiple_of() {
+                assert!((0 as $T).is_multiple_of(&(0 as $T)));
                 assert!((6 as $T).is_multiple_of(&(6 as $T)));
                 assert!((6 as $T).is_multiple_of(&(3 as $T)));
                 assert!((6 as $T).is_multiple_of(&(1 as $T)));
+
+                assert!(!(42 as $T).is_multiple_of(&(5 as $T)));
+                assert!(!(5 as $T).is_multiple_of(&(3 as $T)));
+                assert!(!(42 as $T).is_multiple_of(&(0 as $T)));
             }
 
             #[test]