time code progress

[Rich Felker <dalias@aerifal.cx>]

Hi all,

I've been working, as promised, on the time code overhaul for the next
release of musl. The main issues it's intended to address are:

- complete lack of overflow handling in the present code
- lack of support for zoneinfo time zones

After trying various things, the design I think I've settled on has
the following properties:

- Internally, all POSIX times (seconds since epoch) are passed around
  as long long. This ensures that values derived from struct tm,
  timezone rules, etc. can never overflow, and allows overflow
  checking to be deferred until it's time to convert the value back
  into time_t. Without this design, handling the "partial years" at
  the edge of time_t overflow range is very difficult, as is handling
  the denormalized struct tm forms mktime is required to support and
  normalize (for instance, overflowing the year range by using a very
  large month number).

- Instead of converting back and forth to broken-down struct tm for
  applying timezone rules, the new code simply converts the
  combination of year and TZ rule string to a POSIX time within the
  given year at which the transition occurs. This value has type long
  long so that it cannot overflow even at the boundary years.
  Determining whether DST is in effect at a given time is simply a
  range comparison, just like the comparison that will be used for
  processing zoneinfo-format timezone rules.

- For years within the currently-reasonable range/32-bit time_t, the
  hot path for converting a year to seconds since the epoch involves
  no division. We can get away with >>2 and %3 since in the range
  [1901,2099] the leap year rule is simply that multiple-of-4 years
  are leap years. I would like it be able to have the compiler throw
  away the larger, slower, general-case code on 32-bit-time_t targets,
  but unfortunately the need to use long long internally to avoid
  difficult corner cases is precluding that.

- Any representable struct tm will successfully convert to time_t if
  and only if it represents a value of seconds-since-the-epoch that
  fits in time_t. Any representable time_t will successfully convert
  to struct tm if and only if it represents a (normalized) date and
  time representable in struct tm. The relevant functions will avoid
  setting errno except on error so that a caller can distinguish
  between a time_t value of -1 as a valid result and as an error.

I'm not yet sure whether the new code will be larger or smaller than
the old code. It should be considerably faster, and most importantly,
more correct.

Rich