New implementation of times.between (#10523)

* Refactor ttimes

* New implementation of times.between

* Deprecate times.toTimeInterval

2 files changed, 232 insertions, 116 deletions

diff --git a/lib/pure/times.nim b/lib/pure/times.nim
index 20941fcc2..260850a0e 100644
--- a/lib/pure/times.nim
+++ b/lib/pure/times.nim
@@ -1462,97 +1462,108 @@ proc evaluateStaticInterval(interval: TimeInterval): Duration =
 
 proc between*(startDt, endDt: DateTime): TimeInterval =
   ## Gives the difference between ``startDt`` and ``endDt`` as a
-  ## ``TimeInterval``.
+  ## ``TimeInterval``. The following guarantees about the result is given:
   ##
-  ## **Warning:** This proc currently gives very few guarantees about the
-  ## result. ``a + between(a, b) == b`` is **not** true in general
-  ## (it's always true when UTC is used however). Neither is it guaranteed that
-  ## all components in the result will have the same sign. The behavior of this
-  ## proc might change in the future.
+  ## - All fields will have the same sign.
+  ## - If `startDt.timezone == endDt.timezone`, it is guaranteed that
+  ##   `startDt + between(startDt, endDt) == endDt`.
+  ## - If `startDt.timezone != endDt.timezone`, then the result will be
+  ##   equivalent to `between(startDt.utc, endDt.utc)`.
   runnableExamples:
     var a = initDateTime(25, mMar, 2015, 12, 0, 0, utc())
     var b = initDateTime(1, mApr, 2017, 15, 0, 15, utc())
-    var ti = initTimeInterval(years = 2, days = 7, hours = 3, seconds = 15)
+    var ti = initTimeInterval(years = 2, weeks = 1, hours = 3, seconds = 15)
     doAssert between(a, b) == ti
     doAssert between(a, b) == -between(b, a)
 
-  var startDt = startDt.utc()
-  var endDt = endDt.utc()
-
-  if endDt == startDt:
-    return initTimeInterval()
+  if startDt.timezone != endDt.timezone:
+    return between(startDt.utc, endDt.utc)
   elif endDt < startDt:
     return -between(endDt, startDt)
 
-  var coeffs: array[FixedTimeUnit, int64] = unitWeights
-  var timeParts: array[FixedTimeUnit, int]
-  for unit in Nanoseconds..Weeks:
-    timeParts[unit] = 0
-
-  for unit in Seconds..Days:
-    coeffs[unit] = coeffs[unit] div unitWeights[Seconds]
-
-  var startTimepart = initTime(
-    nanosecond = startDt.nanosecond,
-    unix = startDt.hour * coeffs[Hours] + startDt.minute * coeffs[Minutes] +
-    startDt.second
-  )
-  var endTimepart = initTime(
-    nanosecond = endDt.nanosecond,
-    unix = endDt.hour * coeffs[Hours] + endDt.minute * coeffs[Minutes] +
-    endDt.second
-  )
-  # We wand timeParts for Seconds..Hours be positive, so we'll borrow one day
-  if endTimepart < startTimepart:
-    timeParts[Days] = -1
-
-  let diffTime = endTimepart - startTimepart
-  timeParts[Seconds] = diffTime.seconds.int()
-  #Nanoseconds - preliminary count
-  timeParts[Nanoseconds] = diffTime.nanoseconds
-  for unit in countdown(Milliseconds, Microseconds):
-    timeParts[unit] += timeParts[Nanoseconds] div coeffs[unit].int()
-    timeParts[Nanoseconds] -= timeParts[unit] * coeffs[unit].int()
-
-  #Counting Seconds .. Hours - final, Days - preliminary
-  for unit in countdown(Days, Minutes):
-    timeParts[unit] += timeParts[Seconds] div coeffs[unit].int()
-    # Here is accounted the borrowed day
-    timeParts[Seconds] -= timeParts[unit] * coeffs[unit].int()
-
-  # Set Nanoseconds .. Hours in result
-  result.nanoseconds = timeParts[Nanoseconds]
-  result.microseconds = timeParts[Microseconds]
-  result.milliseconds = timeParts[Milliseconds]
-  result.seconds = timeParts[Seconds]
-  result.minutes = timeParts[Minutes]
-  result.hours = timeParts[Hours]
-
-  #Days
-  if endDt.monthday.int + timeParts[Days] < startDt.monthday.int():
-    if endDt.month > 1.Month:
-      endDt.month -= 1.Month
+  type Date = tuple[year, month, monthday: int]
+  var startDate: Date = (startDt.year, startDt.month.ord, startDt.monthday)
+  var endDate: Date = (endDt.year, endDt.month.ord, endDt.monthday)
+
+  # Subtract one day from endDate if time of day is earlier than startDay
+  # The subtracted day will be counted by fixed units (hour and lower)
+  # at the end of this proc
+  if (endDt.hour, endDt.minute, endDt.second, endDt.nanosecond) <
+      (startDt.hour, startDt.minute, startDt.second, startDt.nanosecond):
+    if endDate.month == 1 and endDate.monthday == 1:
+      endDate.year.dec
+      endDate.monthday = 31
+      endDate.month = 12
+    elif endDate.monthday == 1:
+      endDate.month.dec
+      endDate.monthday = getDaysInMonth(endDate.month.Month, endDate.year)
     else:
-      endDt.month = 12.Month
-      endDt.year -= 1
-    timeParts[Days] += endDt.monthday.int() + getDaysInMonth(
-      endDt.month, endDt.year) - startDt.monthday.int()
-  else:
-    timeParts[Days] += endDt.monthday.int() -
-      startDt.monthday.int()
-
-  result.days = timeParts[Days]
-
-  #Months
-  if endDt.month < startDt.month:
-    result.months = endDt.month.int() + 12 - startDt.month.int()
-    endDt.year -= 1
-  else:
-    result.months = endDt.month.int() -
-      startDt.month.int()
+      endDate.monthday.dec
 
   # Years
-  result.years = endDt.year - startDt.year
+  result.years.inc endDate.year - startDate.year - 1
+  if (startDate.month, startDate.monthday) <= (endDate.month, endDate.monthday):
+    result.years.inc
+  startDate.year.inc result.years
+
+  # Months
+  if startDate.year < endDate.year:
+    result.months.inc 12 - startDate.month # Move to dec
+    if endDate.month != 1 or (startDate.monthday <= endDate.monthday):
+      result.months.inc
+      startDate.year = endDate.year
+      startDate.month = 1
+    else:
+      startDate.month = 12
+  if startDate.year == endDate.year:
+    if (startDate.monthday <= endDate.monthday):
+      result.months.inc endDate.month - startDate.month
+      startDate.month = endDate.month
+    elif endDate.month != 1:
+      let month = endDate.month - 1
+      let daysInMonth = getDaysInMonth(month.Month, startDate.year)
+      if daysInMonth < startDate.monthday:
+        if startDate.monthday - daysInMonth < endDate.monthday:
+          result.months.inc endDate.month - startDate.month - 1
+          startDate.month = endDate.month
+          startDate.monthday = startDate.monthday - daysInMonth
+        else:
+          result.months.inc endDate.month - startDate.month - 2
+          startDate.month = endDate.month - 2
+      else:
+        result.months.inc endDate.month - startDate.month - 1
+        startDate.month = endDate.month - 1
+
+  # Days
+  # This means that start = dec and end = jan
+  if startDate.year < endDate.year:
+    result.days.inc 31 - startDate.monthday + endDate.monthday
+    startDate = endDate
+  else:
+    while startDate.month < endDate.month:
+      let daysInMonth = getDaysInMonth(startDate.month.Month, startDate.year)
+      result.days.inc daysInMonth - startDate.monthday + 1
+      startDate.month.inc
+      startDate.monthday = 1
+    result.days.inc endDate.monthday - startDate.monthday
+    result.weeks = result.days div 7
+    result.days = result.days mod 7
+    startDate = endDate
+
+  # Handle hours, minutes, seconds, milliseconds, microseconds and nanoseconds
+  let newStartDt = initDateTime(startDate.monthday, startDate.month.Month,
+    startDate.year, startDt.hour, startDt.minute, startDt.second,
+    startDt.nanosecond, startDt.timezone)
+  let dur = endDt - newStartDt
+  let parts = toParts(dur)
+  # There can still be a full day in `parts` since `Duration` and `TimeInterval`
+  # models days differently.
+  result.hours = parts[Hours].int + parts[Days].int * 24
+  result.minutes = parts[Minutes].int
+  result.seconds = parts[Seconds].int
+  result.milliseconds = parts[Milliseconds].int
+  result.microseconds = parts[Microseconds].int
+  result.nanoseconds = parts[Nanoseconds].int
 
 proc `+`*(time: Time, interval: TimeInterval): Time =
   ## Adds `interval` to `time`.
@@ -2405,10 +2416,12 @@ proc countYearsAndDays*(daySpan: int): tuple[years: int, days: int]
   result.years = days div 365
   result.days = days mod 365
 
-proc toTimeInterval*(time: Time): TimeInterval =
-  ## Converts a Time to a TimeInterval.
+proc toTimeInterval*(time: Time): TimeInterval
+    {.deprecated: "Use `between` instead".} =
+  ## Converts a Time to a TimeInterval. To be used when diffing times.
   ##
-  ## To be used when diffing times. Consider using `between` instead.
+  ## **Deprecated since version 0.20.0:** Use the `between proc
+  ## <#between,DateTime,DateTime>`_ instead.
   runnableExamples:
     let a = fromUnix(10)
     let b = fromUnix(1_500_000_000)
diff --git a/tests/stdlib/ttimes.nim b/tests/stdlib/ttimes.nim
index 3999c968f..456ff6315 100644
--- a/tests/stdlib/ttimes.nim
+++ b/tests/stdlib/ttimes.nim
@@ -115,6 +115,13 @@ template runTimezoneTests() =
     check toTime(parsedJan).toUnix == 1451962800
     check toTime(parsedJul).toUnix == 1467342000
 
+template usingTimezone(tz: string, body: untyped) =
+  when defined(linux) or defined(macosx):
+    let oldZone = getEnv("TZ")
+    putEnv("TZ", tz)
+    body
+    putEnv("TZ", oldZone)
+
 suite "ttimes":
 
   # Generate tests for multiple timezone files where available
@@ -123,37 +130,47 @@ suite "ttimes":
     let tz_dir = getEnv("TZDIR", "/usr/share/zoneinfo")
     const f = "yyyy-MM-dd HH:mm zzz"
 
-    let orig_tz = getEnv("TZ")
     var tz_cnt = 0
-    for tz_fn in walkFiles(tz_dir & "/**/*"):
-      if symlinkExists(tz_fn) or tz_fn.endsWith(".tab") or
-          tz_fn.endsWith(".list"):
+    for timezone in walkFiles(tz_dir & "/**/*"):
+      if symlinkExists(timezone) or timezone.endsWith(".tab") or
+          timezone.endsWith(".list"):
         continue
 
-      test "test for " & tz_fn:
-        tz_cnt.inc
-        putEnv("TZ", tz_fn)
-        runTimezoneTests()
+      usingTimezone(timezone):
+        test "test for " & timezone:
+          tz_cnt.inc
+          runTimezoneTests()
 
     test "enough timezone files tested":
       check tz_cnt > 10
 
-    test "dst handling":
-      putEnv("TZ", "Europe/Stockholm")
-      # In case of an impossible time, the time is moved to after the impossible time period
-      check initDateTime(26, mMar, 2017, 02, 30, 00).format(f) == "2017-03-26 03:30 +02:00"
+  else:
+    # not on Linux or macosx: run in the local timezone only
+    test "parseTest":
+      runTimezoneTests()
+
+  test "dst handling":
+    usingTimezone("Europe/Stockholm"):
+      # In case of an impossible time, the time is moved to after the
+      # impossible time period
+      check initDateTime(26, mMar, 2017, 02, 30, 00).format(f) ==
+        "2017-03-26 03:30 +02:00"
       # In case of an ambiguous time, the earlier time is choosen
-      check initDateTime(29, mOct, 2017, 02, 00, 00).format(f) == "2017-10-29 02:00 +02:00"
+      check initDateTime(29, mOct, 2017, 02, 00, 00).format(f) ==
+        "2017-10-29 02:00 +02:00"
       # These are just dates on either side of the dst switch
-      check initDateTime(29, mOct, 2017, 01, 00, 00).format(f) == "2017-10-29 01:00 +02:00"
+      check initDateTime(29, mOct, 2017, 01, 00, 00).format(f) ==
+        "2017-10-29 01:00 +02:00"
       check initDateTime(29, mOct, 2017, 01, 00, 00).isDst
-      check initDateTime(29, mOct, 2017, 03, 01, 00).format(f) == "2017-10-29 03:01 +01:00"
+      check initDateTime(29, mOct, 2017, 03, 01, 00).format(f) ==
+        "2017-10-29 03:01 +01:00"
       check (not initDateTime(29, mOct, 2017, 03, 01, 00).isDst)
 
-      check initDateTime(21, mOct, 2017, 01, 00, 00).format(f) == "2017-10-21 01:00 +02:00"
+      check initDateTime(21, mOct, 2017, 01, 00, 00).format(f) ==
+        "2017-10-21 01:00 +02:00"
 
-    test "issue #6520":
-      putEnv("TZ", "Europe/Stockholm")
+  test "issue #6520":
+    usingTimezone("Europe/Stockholm"):
       var local = fromUnix(1469275200).local
       var utc = fromUnix(1469275200).utc
 
@@ -161,35 +178,28 @@ suite "ttimes":
       local.utcOffset = 0
       check claimedOffset == utc.toTime - local.toTime
 
-    test "issue #5704":
-      putEnv("TZ", "Asia/Seoul")
-      let diff = parse("19700101-000000", "yyyyMMdd-hhmmss").toTime - parse("19000101-000000", "yyyyMMdd-hhmmss").toTime
+  test "issue #5704":
+    usingTimezone("Asia/Seoul"):
+      let diff = parse("19700101-000000", "yyyyMMdd-hhmmss").toTime -
+        parse("19000101-000000", "yyyyMMdd-hhmmss").toTime
       check diff == initDuration(seconds = 2208986872)
 
-    test "issue #6465":
-      putEnv("TZ", "Europe/Stockholm")
+  test "issue #6465":
+    usingTimezone("Europe/Stockholm"):
       let dt = parse("2017-03-25 12:00", "yyyy-MM-dd hh:mm")
       check $(dt + initTimeInterval(days = 1)) == "2017-03-26T12:00:00+02:00"
       check $(dt + initDuration(days = 1)) == "2017-03-26T13:00:00+02:00"
 
-    test "datetime before epoch":
-      check $fromUnix(-2147483648).utc == "1901-12-13T20:45:52Z"
-
-    test "adding/subtracting time across dst":
-      putenv("TZ", "Europe/Stockholm")
-
+  test "adding/subtracting time across dst":
+    usingTimezone("Europe/Stockholm"):
       let dt1 = initDateTime(26, mMar, 2017, 03, 00, 00)
       check $(dt1 - 1.seconds) == "2017-03-26T01:59:59+01:00"
 
       var dt2 = initDateTime(29, mOct, 2017, 02, 59, 59)
       check  $(dt2 + 1.seconds) == "2017-10-29T02:00:00+01:00"
 
-    putEnv("TZ", orig_tz)
-
-  else:
-    # not on Linux or macosx: run in the local timezone only
-    test "parseTest":
-      runTimezoneTests()
+  test "datetime before epoch":
+    check $fromUnix(-2147483648).utc == "1901-12-13T20:45:52Z"
 
   test "incorrect inputs: empty string":
     parseTestExcp("", "yyyy-MM-dd")
@@ -485,3 +495,96 @@ suite "ttimes":
     check getDayOfWeek(21, mSep, 1970) == dMon
     check getDayOfWeek(01, mJan, 2000) == dSat
     check getDayOfWeek(01, mJan, 2021) == dFri
+
+  test "between - simple":
+    let x = initDateTime(10, mJan, 2018, 13, 00, 00)
+    let y = initDateTime(11, mJan, 2018, 12, 00, 00)
+    doAssert x + between(x, y) == y
+
+  test "between - dst start":
+    usingTimezone("Europe/Stockholm"):
+      let x = initDateTime(25, mMar, 2018, 00, 00, 00)
+      let y = initDateTime(25, mMar, 2018, 04, 00, 00)
+      doAssert x + between(x, y) == y
+
+  test "between - empty interval":
+    let x = now()
+    let y = x
+    doAssert x + between(x, y) == y
+
+  test "between - dst end":
+    usingTimezone("Europe/Stockholm"):
+      let x = initDateTime(27, mOct, 2018, 02, 00, 00)
+      let y = initDateTime(28, mOct, 2018, 01, 00, 00)
+      doAssert x + between(x, y) == y
+
+  test "between - long day":
+    usingTimezone("Europe/Stockholm"):
+      # This day is 25 hours long in Europe/Stockholm
+      let x = initDateTime(28, mOct, 2018, 00, 30, 00)
+      let y = initDateTime(29, mOct, 2018, 00, 00, 00)
+      doAssert between(x, y) == 24.hours + 30.minutes
+      doAssert x + between(x, y) == y
+
+  test "between - offset change edge case":
+    # This test case is important because in this case
+    # `x + between(x.utc, y.utc) == y` is not true, which is very rare.
+    usingTimezone("America/Belem"):
+      let x = initDateTime(24, mOct, 1987, 00, 00, 00)
+      let y = initDateTime(26, mOct, 1987, 23, 00, 00)
+      doAssert x + between(x, y) == y
+      doAssert y + between(y, x) == x
+
+  test "between - all units":
+    let x = initDateTime(1, mJan, 2000, 00, 00, 00, utc())
+    let ti = initTimeInterval(1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
+    let y = x + ti
+    doAssert between(x, y) == ti
+    doAssert between(y, x) == -ti
+
+  test "between - monthday overflow":
+      let x = initDateTime(31, mJan, 2001, 00, 00, 00, utc())
+      let y = initDateTime(1, mMar, 2001, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+
+  test "between - misc":
+    block:
+      let x = initDateTime(31, mDec, 2000, 12, 00, 00, utc())
+      let y = initDateTime(01, mJan, 2001, 00, 00, 00, utc())
+      doAssert between(x, y) == 12.hours
+
+    block:
+      let x = initDateTime(31, mDec, 2000, 12, 00, 00, utc())
+      let y = initDateTime(02, mJan, 2001, 00, 00, 00, utc())
+      doAssert between(x, y) == 1.days + 12.hours
+
+    block:
+      let x = initDateTime(31, mDec, 1995, 00, 00, 00, utc())
+      let y = initDateTime(01, mFeb, 2000, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+
+    block:
+      let x = initDateTime(01, mDec, 1995, 00, 00, 00, utc())
+      let y = initDateTime(31, mJan, 2000, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+
+    block:
+      let x = initDateTime(31, mJan, 2000, 00, 00, 00, utc())
+      let y = initDateTime(01, mFeb, 2000, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+
+    block:
+      let x = initDateTime(01, mJan, 1995, 12, 00, 00, utc())
+      let y = initDateTime(01, mFeb, 1995, 00, 00, 00, utc())
+      doAssert between(x, y) == 4.weeks + 2.days + 12.hours
+
+    block:
+      let x = initDateTime(31, mJan, 1995, 00, 00, 00, utc())
+      let y = initDateTime(10, mFeb, 1995, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+
+    block:
+      let x = initDateTime(31, mJan, 1995, 00, 00, 00, utc())
+      let y = initDateTime(10, mMar, 1995, 00, 00, 00, utc())
+      doAssert x + between(x, y) == y
+      doAssert between(x, y) == 1.months + 1.weeks