std: Add Instant and SystemTime to std::time

This commit is an implementation of [RFC 1288][rfc] which adds two new unstable
types to the `std::time` module. The `Instant` type is used to represent
measurements of a monotonically increasing clock suitable for measuring time
withing a process for operations such as benchmarks or just the elapsed time to
do something. An `Instant` favors panicking when bugs are found as the bugs are
programmer errors rather than typical errors that can be encountered.

[rfc]: https://github.com/rust-lang/rfcs/pull/1288

The `SystemTime` type is used to represent a system timestamp and is not
monotonic. Very few guarantees are provided about this measurement of the system
clock, but a fixed point in time (`UNIX_EPOCH`) is provided to learn about the
relative distance from this point for any particular time stamp.

This PR takes the same implementation strategy as the `time` crate on crates.io,
namely:

|  Platform  |  Instant                 |  SystemTime              |
|------------|--------------------------|--------------------------|
| Windows    | QueryPerformanceCounter  | GetSystemTimeAsFileTime  |
| OSX        | mach_absolute_time       | gettimeofday             |
| Unix       | CLOCK_MONOTONIC          | CLOCK_REALTIME           |

These implementations can perhaps be refined over time, but they currently
satisfy the requirements of the `Instant` and `SystemTime` types while also
being portable across implementations and revisions of each platform.

2 files changed, 158 insertions, 35 deletions

diff --git a/src/libstd/sys/windows/c.rs b/src/libstd/sys/windows/c.rs
index 42f182eb010..7ef504fba81 100644
--- a/src/libstd/sys/windows/c.rs
+++ b/src/libstd/sys/windows/c.rs
@@ -65,6 +65,7 @@ pub type LPWSANETWORKEVENTS = *mut WSANETWORKEVENTS;
 pub type LPWSAPROTOCOLCHAIN = *mut WSAPROTOCOLCHAIN;
 pub type LPWSAPROTOCOL_INFO = *mut WSAPROTOCOL_INFO;
 pub type LPWSTR = *mut WCHAR;
+pub type LPFILETIME = *mut FILETIME;
 
 pub type PCONDITION_VARIABLE = *mut CONDITION_VARIABLE;
 pub type PLARGE_INTEGER = *mut c_longlong;
@@ -1231,6 +1232,7 @@ extern "system" {
                        ReturnValue: LPVOID,
                        OriginalContext: *const CONTEXT,
                        HistoryTable: *const UNWIND_HISTORY_TABLE);
+    pub fn GetSystemTimeAsFileTime(lpSystemTimeAsFileTime: LPFILETIME);
 }
 
 // Functions that aren't available on Windows XP, but we still use them and just
diff --git a/src/libstd/sys/windows/time.rs b/src/libstd/sys/windows/time.rs
index 707e8c05e17..058587b11dc 100644
--- a/src/libstd/sys/windows/time.rs
+++ b/src/libstd/sys/windows/time.rs
@@ -8,62 +8,183 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use ops::Sub;
+use cmp::Ordering;
+use fmt;
+use mem;
 use sync::Once;
 use sys::c;
+use sys::cvt;
+use sys_common::mul_div_u64;
 use time::Duration;
 
 const NANOS_PER_SEC: u64 = 1_000_000_000;
+const INTERVALS_PER_SEC: u64 = NANOS_PER_SEC / 100;
 
-pub struct SteadyTime {
+#[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
+pub struct Instant {
     t: c::LARGE_INTEGER,
 }
 
-impl SteadyTime {
-    pub fn now() -> SteadyTime {
-        let mut t = SteadyTime { t: 0 };
-        unsafe { c::QueryPerformanceCounter(&mut t.t); }
+#[derive(Copy, Clone)]
+pub struct SystemTime {
+    t: c::FILETIME,
+}
+
+const INTERVALS_TO_UNIX_EPOCH: u64 = 11_644_473_600 * INTERVALS_PER_SEC;
+
+pub const UNIX_EPOCH: SystemTime = SystemTime {
+    t: c::FILETIME {
+        dwLowDateTime: INTERVALS_TO_UNIX_EPOCH as u32,
+        dwHighDateTime: (INTERVALS_TO_UNIX_EPOCH >> 32) as u32,
+    },
+};
+
+impl Instant {
+    pub fn now() -> Instant {
+        let mut t = Instant { t: 0 };
+        cvt(unsafe {
+            c::QueryPerformanceCounter(&mut t.t)
+        }).unwrap();
         t
     }
+
+    pub fn sub_instant(&self, other: &Instant) -> Duration {
+        // Values which are +- 1 need to be considered as basically the same
+        // units in time due to various measurement oddities, according to
+        // Windows [1]
+        //
+        // [1]:
+        // https://msdn.microsoft.com/en-us/library/windows/desktop
+        //                           /dn553408%28v=vs.85%29.aspx#guidance
+        if other.t > self.t && other.t - self.t == 1 {
+            return Duration::new(0, 0)
+        }
+        let diff = (self.t as u64).checked_sub(other.t as u64)
+                                  .expect("specified instant was later than \
+                                           self");
+        let nanos = mul_div_u64(diff, NANOS_PER_SEC, frequency() as u64);
+        Duration::new(nanos / NANOS_PER_SEC, (nanos % NANOS_PER_SEC) as u32)
+    }
+
+    pub fn add_duration(&self, other: &Duration) -> Instant {
+        let freq = frequency() as u64;
+        let t = other.as_secs().checked_mul(freq).and_then(|i| {
+            (self.t as u64).checked_add(i)
+        }).and_then(|i| {
+            i.checked_add(mul_div_u64(other.subsec_nanos() as u64, freq,
+                                      NANOS_PER_SEC))
+        }).expect("overflow when adding duration to time");
+        Instant {
+            t: t as c::LARGE_INTEGER,
+        }
+    }
+
+    pub fn sub_duration(&self, other: &Duration) -> Instant {
+        let freq = frequency() as u64;
+        let t = other.as_secs().checked_mul(freq).and_then(|i| {
+            (self.t as u64).checked_sub(i)
+        }).and_then(|i| {
+            i.checked_sub(mul_div_u64(other.subsec_nanos() as u64, freq,
+                                      NANOS_PER_SEC))
+        }).expect("overflow when subtracting duration from time");
+        Instant {
+            t: t as c::LARGE_INTEGER,
+        }
+    }
 }
 
-fn frequency() -> c::LARGE_INTEGER {
-    static mut FREQUENCY: c::LARGE_INTEGER = 0;
-    static ONCE: Once = Once::new();
+impl SystemTime {
+    pub fn now() -> SystemTime {
+        unsafe {
+            let mut t: SystemTime = mem::zeroed();
+            c::GetSystemTimeAsFileTime(&mut t.t);
+            return t
+        }
+    }
 
-    unsafe {
-        ONCE.call_once(|| {
-            c::QueryPerformanceFrequency(&mut FREQUENCY);
-        });
-        FREQUENCY
+    fn from_intervals(intervals: i64) -> SystemTime {
+        SystemTime {
+            t: c::FILETIME {
+                dwLowDateTime: intervals as c::DWORD,
+                dwHighDateTime: (intervals >> 32) as c::DWORD,
+            }
+        }
+    }
+
+    fn intervals(&self) -> i64 {
+        (self.t.dwLowDateTime as i64) | ((self.t.dwHighDateTime as i64) << 32)
+    }
+
+    pub fn sub_time(&self, other: &SystemTime) -> Result<Duration, Duration> {
+        let me = self.intervals();
+        let other = other.intervals();
+        if me >= other {
+            Ok(intervals2dur((me - other) as u64))
+        } else {
+            Err(intervals2dur((other - me) as u64))
+        }
+    }
+
+    pub fn add_duration(&self, other: &Duration) -> SystemTime {
+        let intervals = self.intervals().checked_add(dur2intervals(other))
+                            .expect("overflow when adding duration to time");
+        SystemTime::from_intervals(intervals)
+    }
+
+    pub fn sub_duration(&self, other: &Duration) -> SystemTime {
+        let intervals = self.intervals().checked_sub(dur2intervals(other))
+                            .expect("overflow when subtracting from time");
+        SystemTime::from_intervals(intervals)
     }
 }
 
-#[unstable(feature = "libstd_sys_internals", issue = "0")]
-impl<'a> Sub for &'a SteadyTime {
-    type Output = Duration;
+impl PartialEq for SystemTime {
+    fn eq(&self, other: &SystemTime) -> bool {
+        self.intervals() == other.intervals()
+    }
+}
 
-    fn sub(self, other: &SteadyTime) -> Duration {
-        let diff = self.t as u64 - other.t as u64;
-        let nanos = mul_div_u64(diff, NANOS_PER_SEC, frequency() as u64);
-        Duration::new(nanos / NANOS_PER_SEC, (nanos % NANOS_PER_SEC) as u32)
+impl Eq for SystemTime {}
+
+impl PartialOrd for SystemTime {
+    fn partial_cmp(&self, other: &SystemTime) -> Option<Ordering> {
+        Some(self.cmp(other))
+    }
+}
+
+impl Ord for SystemTime {
+    fn cmp(&self, other: &SystemTime) -> Ordering {
+        self.intervals().cmp(&other.intervals())
     }
 }
 
-// Computes (value*numer)/denom without overflow, as long as both
-// (numer*denom) and the overall result fit into i64 (which is the case
-// for our time conversions).
-fn mul_div_u64(value: u64, numer: u64, denom: u64) -> u64 {
-    let q = value / denom;
-    let r = value % denom;
-    // Decompose value as (value/denom*denom + value%denom),
-    // substitute into (value*numer)/denom and simplify.
-    // r < denom, so (denom*numer) is the upper bound of (r*numer)
-    q * numer + r * numer / denom
+impl fmt::Debug for SystemTime {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("SystemTime")
+         .field("intervals", &self.intervals())
+         .finish()
+    }
 }
 
-#[test]
-fn test_muldiv() {
-    assert_eq!(mul_div_u64( 1_000_000_000_001, 1_000_000_000, 1_000_000),
-               1_000_000_000_001_000);
+fn dur2intervals(d: &Duration) -> i64 {
+    d.as_secs().checked_mul(INTERVALS_PER_SEC).and_then(|i| {
+        i.checked_add(d.subsec_nanos() as u64 / 100)
+    }).expect("overflow when converting duration to intervals") as i64
+}
+
+fn intervals2dur(intervals: u64) -> Duration {
+    Duration::new(intervals / INTERVALS_PER_SEC,
+                  ((intervals % INTERVALS_PER_SEC) * 100) as u32)
+}
+
+fn frequency() -> c::LARGE_INTEGER {
+    static mut FREQUENCY: c::LARGE_INTEGER = 0;
+    static ONCE: Once = Once::new();
+
+    unsafe {
+        ONCE.call_once(|| {
+            cvt(c::QueryPerformanceFrequency(&mut FREQUENCY)).unwrap();
+        });
+        FREQUENCY
+    }
 }