date.cc 14.9 KB
Newer Older
1
// Copyright 2012 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

Yang Guo's avatar
Yang Guo committed
5
#include "src/date/date.h"
6

7
#include "src/base/overflowing-math.h"
8
#include "src/numbers/conversions.h"
9
#include "src/objects/objects-inl.h"
10
#ifdef V8_INTL_SUPPORT
Frank Tang's avatar
Frank Tang committed
11
#include "src/objects/intl-objects.h"
12 13
#endif

14 15 16 17 18 19 20
namespace v8 {
namespace internal {

static const int kDaysIn4Years = 4 * 365 + 1;
static const int kDaysIn100Years = 25 * kDaysIn4Years - 1;
static const int kDaysIn400Years = 4 * kDaysIn100Years + 1;
static const int kDays1970to2000 = 30 * 365 + 7;
Yang Guo's avatar
Yang Guo committed
21 22
static const int kDaysOffset =
    1000 * kDaysIn400Years + 5 * kDaysIn400Years - kDays1970to2000;
23
static const int kYearsOffset = 400000;
Yang Guo's avatar
Yang Guo committed
24 25
static const char kDaysInMonths[] = {31, 28, 31, 30, 31, 30,
                                     31, 31, 30, 31, 30, 31};
26

27
DateCache::DateCache()
28
    : stamp_(kNullAddress),
29
      tz_cache_(
30
#ifdef V8_INTL_SUPPORT
Frank Tang's avatar
Frank Tang committed
31
          Intl::CreateTimeZoneCache()
32 33 34
#else
          base::OS::CreateTimezoneCache()
#endif
Yang Guo's avatar
Yang Guo committed
35
      ) {
36
  ResetDateCache(base::TimezoneCache::TimeZoneDetection::kSkip);
37
}
38

39 40
void DateCache::ResetDateCache(
    base::TimezoneCache::TimeZoneDetection time_zone_detection) {
41
  if (stamp_.value() >= Smi::kMaxValue) {
42
    stamp_ = Smi::zero();
43
  } else {
44
    stamp_ = Smi::FromInt(stamp_.value() + 1);
45
  }
46
  DCHECK(stamp_ != Smi::FromInt(kInvalidStamp));
47 48 49 50 51 52 53
  for (int i = 0; i < kDSTSize; ++i) {
    ClearSegment(&dst_[i]);
  }
  dst_usage_counter_ = 0;
  before_ = &dst_[0];
  after_ = &dst_[1];
  ymd_valid_ = false;
54 55 56 57 58 59 60
#ifdef V8_INTL_SUPPORT
  if (!FLAG_icu_timezone_data) {
#endif
    local_offset_ms_ = kInvalidLocalOffsetInMs;
#ifdef V8_INTL_SUPPORT
  }
#endif
61
  tz_cache_->Clear(time_zone_detection);
62 63
  tz_name_ = nullptr;
  dst_tz_name_ = nullptr;
64 65
}

66 67 68
// ECMA 262 - ES#sec-timeclip TimeClip (time)
double DateCache::TimeClip(double time) {
  if (-kMaxTimeInMs <= time && time <= kMaxTimeInMs) {
69
    return DoubleToInteger(time);
70 71 72
  }
  return std::numeric_limits<double>::quiet_NaN();
}
73 74 75 76 77 78 79 80

void DateCache::ClearSegment(DST* segment) {
  segment->start_sec = kMaxEpochTimeInSec;
  segment->end_sec = -kMaxEpochTimeInSec;
  segment->offset_ms = 0;
  segment->last_used = 0;
}

Yang Guo's avatar
Yang Guo committed
81 82
void DateCache::YearMonthDayFromDays(int days, int* year, int* month,
                                     int* day) {
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
  if (ymd_valid_) {
    // Check conservatively if the given 'days' has
    // the same year and month as the cached 'days'.
    int new_day = ymd_day_ + (days - ymd_days_);
    if (new_day >= 1 && new_day <= 28) {
      ymd_day_ = new_day;
      ymd_days_ = days;
      *year = ymd_year_;
      *month = ymd_month_;
      *day = new_day;
      return;
    }
  }
  int save_days = days;

  days += kDaysOffset;
  *year = 400 * (days / kDaysIn400Years) - kYearsOffset;
  days %= kDaysIn400Years;

102
  DCHECK_EQ(save_days, DaysFromYearMonth(*year, 0) + days);
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120

  days--;
  int yd1 = days / kDaysIn100Years;
  days %= kDaysIn100Years;
  *year += 100 * yd1;

  days++;
  int yd2 = days / kDaysIn4Years;
  days %= kDaysIn4Years;
  *year += 4 * yd2;

  days--;
  int yd3 = days / 365;
  days %= 365;
  *year += yd3;

  bool is_leap = (!yd1 || yd2) && !yd3;

121
  DCHECK_GE(days, -1);
122 123 124 125 126
  DCHECK(is_leap || (days >= 0));
  DCHECK((days < 365) || (is_leap && (days < 366)));
  DCHECK(is_leap == ((*year % 4 == 0) && (*year % 100 || (*year % 400 == 0))));
  DCHECK(is_leap || ((DaysFromYearMonth(*year, 0) + days) == save_days));
  DCHECK(!is_leap || ((DaysFromYearMonth(*year, 0) + days + 1) == save_days));
127 128 129 130

  days += is_leap;

  // Check if the date is after February.
131 132
  if (days >= 31 + 28 + (is_leap ? 1 : 0)) {
    days -= 31 + 28 + (is_leap ? 1 : 0);
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
    // Find the date starting from March.
    for (int i = 2; i < 12; i++) {
      if (days < kDaysInMonths[i]) {
        *month = i;
        *day = days + 1;
        break;
      }
      days -= kDaysInMonths[i];
    }
  } else {
    // Check January and February.
    if (days < 31) {
      *month = 0;
      *day = days + 1;
    } else {
      *month = 1;
      *day = days - 31 + 1;
    }
  }
152
  DCHECK(DaysFromYearMonth(*year, *month) + *day - 1 == save_days);
153 154 155 156 157 158 159 160
  ymd_valid_ = true;
  ymd_year_ = *year;
  ymd_month_ = *month;
  ymd_day_ = *day;
  ymd_days_ = save_days;
}

int DateCache::DaysFromYearMonth(int year, int month) {
Yang Guo's avatar
Yang Guo committed
161
  static const int day_from_month[] = {0,   31,  59,  90,  120, 151,
162
                                       181, 212, 243, 273, 304, 334};
Yang Guo's avatar
Yang Guo committed
163
  static const int day_from_month_leap[] = {0,   31,  60,  91,  121, 152,
164 165 166 167 168 169 170 171 172
                                            182, 213, 244, 274, 305, 335};

  year += month / 12;
  month %= 12;
  if (month < 0) {
    year--;
    month += 12;
  }

173 174
  DCHECK_GE(month, 0);
  DCHECK_LT(month, 12);
175 176 177 178 179 180 181 182 183 184

  // year_delta is an arbitrary number such that:
  // a) year_delta = -1 (mod 400)
  // b) year + year_delta > 0 for years in the range defined by
  //    ECMA 262 - 15.9.1.1, i.e. upto 100,000,000 days on either side of
  //    Jan 1 1970. This is required so that we don't run into integer
  //    division of negative numbers.
  // c) there shouldn't be an overflow for 32-bit integers in the following
  //    operations.
  static const int year_delta = 399999;
Yang Guo's avatar
Yang Guo committed
185 186 187
  static const int base_day =
      365 * (1970 + year_delta) + (1970 + year_delta) / 4 -
      (1970 + year_delta) / 100 + (1970 + year_delta) / 400;
188 189

  int year1 = year + year_delta;
Yang Guo's avatar
Yang Guo committed
190 191
  int day_from_year =
      365 * year1 + year1 / 4 - year1 / 100 + year1 / 400 - base_day;
192 193 194 195 196 197 198

  if ((year % 4 != 0) || (year % 100 == 0 && year % 400 != 0)) {
    return day_from_year + day_from_month[month];
  }
  return day_from_year + day_from_month_leap[month];
}

199 200 201 202 203 204 205 206 207 208 209 210 211
void DateCache::BreakDownTime(int64_t time_ms, int* year, int* month, int* day,
                              int* weekday, int* hour, int* min, int* sec,
                              int* ms) {
  int const days = DaysFromTime(time_ms);
  int const time_in_day_ms = TimeInDay(time_ms, days);
  YearMonthDayFromDays(days, year, month, day);
  *weekday = Weekday(days);
  *hour = time_in_day_ms / (60 * 60 * 1000);
  *min = (time_in_day_ms / (60 * 1000)) % 60;
  *sec = (time_in_day_ms / 1000) % 60;
  *ms = time_in_day_ms % 1000;
}

212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
// Implements LocalTimeZonedjustment(t, isUTC)
// ECMA 262 - ES#sec-local-time-zone-adjustment
int DateCache::GetLocalOffsetFromOS(int64_t time_ms, bool is_utc) {
  double offset;
#ifdef V8_INTL_SUPPORT
  if (FLAG_icu_timezone_data) {
    offset = tz_cache_->LocalTimeOffset(static_cast<double>(time_ms), is_utc);
  } else {
#endif
    // When ICU timezone data is not used, we need to compute the timezone
    // offset for a given local time.
    //
    // The following shows that using DST for (t - LocalTZA - hour) produces
    // correct conversion where LocalTZA is the timezone offset in winter (no
    // DST) and the timezone offset is assumed to have no historical change.
    // Note that it does not work for the past and the future if LocalTZA (no
    // DST) is different from the current LocalTZA (no DST). For instance,
    // this will break for Europe/Moscow in 2012 ~ 2013 because LocalTZA was
    // 4h instead of the current 3h (as of 2018).
    //
    // Consider transition to DST at local time L1.
    // Let L0 = L1 - hour, L2 = L1 + hour,
    //     U1 = UTC time that corresponds to L1,
    //     U0 = U1 - hour.
    // Transitioning to DST moves local clock one hour forward L1 => L2, so
    // U0 = UTC time that corresponds to L0 = L0 - LocalTZA,
    // U1 = UTC time that corresponds to L1 = L1 - LocalTZA,
    // U1 = UTC time that corresponds to L2 = L2 - LocalTZA - hour.
    // Note that DST(U0 - hour) = 0, DST(U0) = 0, DST(U1) = 1.
    // U0 = L0 - LocalTZA - DST(L0 - LocalTZA - hour),
    // U1 = L1 - LocalTZA - DST(L1 - LocalTZA - hour),
    // U1 = L2 - LocalTZA - DST(L2 - LocalTZA - hour).
    //
    // Consider transition from DST at local time L1.
    // Let L0 = L1 - hour,
    //     U1 = UTC time that corresponds to L1,
    //     U0 = U1 - hour, U2 = U1 + hour.
    // Transitioning from DST moves local clock one hour back L1 => L0, so
    // U0 = UTC time that corresponds to L0 (before transition)
    //    = L0 - LocalTZA - hour.
    // U1 = UTC time that corresponds to L0 (after transition)
    //    = L0 - LocalTZA = L1 - LocalTZA - hour
    // U2 = UTC time that corresponds to L1 = L1 - LocalTZA.
    // Note that DST(U0) = 1, DST(U1) = 0, DST(U2) = 0.
    // U0 = L0 - LocalTZA - DST(L0 - LocalTZA - hour) = L0 - LocalTZA - DST(U0).
    // U2 = L1 - LocalTZA - DST(L1 - LocalTZA - hour) = L1 - LocalTZA - DST(U1).
    // It is impossible to get U1 from local time.
    if (local_offset_ms_ == kInvalidLocalOffsetInMs) {
      // This gets the constant LocalTZA (arguments are ignored).
      local_offset_ms_ =
          tz_cache_->LocalTimeOffset(static_cast<double>(time_ms), is_utc);
    }
    offset = local_offset_ms_;
    if (!is_utc) {
      const int kMsPerHour = 3600 * 1000;
      time_ms -= (offset + kMsPerHour);
    }
    offset += DaylightSavingsOffsetInMs(time_ms);
#ifdef V8_INTL_SUPPORT
  }
#endif
  DCHECK_LT(offset, kInvalidLocalOffsetInMs);
  return static_cast<int>(offset);
}
276

277 278
void DateCache::ExtendTheAfterSegment(int time_sec, int offset_ms) {
  if (after_->offset_ms == offset_ms &&
279
      after_->start_sec - kDefaultDSTDeltaInSec <= time_sec &&
280 281 282 283 284
      time_sec <= after_->end_sec) {
    // Extend the after_ segment.
    after_->start_sec = time_sec;
  } else {
    // The after_ segment is either invalid or starts too late.
285
    if (!InvalidSegment(after_)) {
286 287 288 289 290 291 292 293 294 295 296 297
      // If the after_ segment is valid, replace it with a new segment.
      after_ = LeastRecentlyUsedDST(before_);
    }
    after_->start_sec = time_sec;
    after_->end_sec = time_sec;
    after_->offset_ms = offset_ms;
    after_->last_used = ++dst_usage_counter_;
  }
}

int DateCache::DaylightSavingsOffsetInMs(int64_t time_ms) {
  int time_sec = (time_ms >= 0 && time_ms <= kMaxEpochTimeInMs)
Yang Guo's avatar
Yang Guo committed
298 299
                     ? static_cast<int>(time_ms / 1000)
                     : static_cast<int>(EquivalentTime(time_ms) / 1000);
300 301 302 303 304 305 306 307 308 309 310 311

  // Invalidate cache if the usage counter is close to overflow.
  // Note that dst_usage_counter is incremented less than ten times
  // in this function.
  if (dst_usage_counter_ >= kMaxInt - 10) {
    dst_usage_counter_ = 0;
    for (int i = 0; i < kDSTSize; ++i) {
      ClearSegment(&dst_[i]);
    }
  }

  // Optimistic fast check.
Yang Guo's avatar
Yang Guo committed
312
  if (before_->start_sec <= time_sec && time_sec <= before_->end_sec) {
313 314 315 316 317 318 319
    // Cache hit.
    before_->last_used = ++dst_usage_counter_;
    return before_->offset_ms;
  }

  ProbeDST(time_sec);

320 321
  DCHECK(InvalidSegment(before_) || before_->start_sec <= time_sec);
  DCHECK(InvalidSegment(after_) || time_sec < after_->start_sec);
322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337

  if (InvalidSegment(before_)) {
    // Cache miss.
    before_->start_sec = time_sec;
    before_->end_sec = time_sec;
    before_->offset_ms = GetDaylightSavingsOffsetFromOS(time_sec);
    before_->last_used = ++dst_usage_counter_;
    return before_->offset_ms;
  }

  if (time_sec <= before_->end_sec) {
    // Cache hit.
    before_->last_used = ++dst_usage_counter_;
    return before_->offset_ms;
  }

338
  if (time_sec - kDefaultDSTDeltaInSec > before_->end_sec) {
339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356
    // If the before_ segment ends too early, then just
    // query for the offset of the time_sec
    int offset_ms = GetDaylightSavingsOffsetFromOS(time_sec);
    ExtendTheAfterSegment(time_sec, offset_ms);
    // This swap helps the optimistic fast check in subsequent invocations.
    DST* temp = before_;
    before_ = after_;
    after_ = temp;
    return offset_ms;
  }

  // Now the time_sec is between
  // before_->end_sec and before_->end_sec + default DST delta.
  // Update the usage counter of before_ since it is going to be used.
  before_->last_used = ++dst_usage_counter_;

  // Check if after_ segment is invalid or starts too late.
  // Note that start_sec of invalid segments is kMaxEpochTimeInSec.
357 358 359 360 361
  int new_after_start_sec =
      before_->end_sec < kMaxEpochTimeInSec - kDefaultDSTDeltaInSec
          ? before_->end_sec + kDefaultDSTDeltaInSec
          : kMaxEpochTimeInSec;
  if (new_after_start_sec <= after_->start_sec) {
362 363 364
    int new_offset_ms = GetDaylightSavingsOffsetFromOS(new_after_start_sec);
    ExtendTheAfterSegment(new_after_start_sec, new_offset_ms);
  } else {
365
    DCHECK(!InvalidSegment(after_));
366 367 368 369 370 371 372 373 374 375 376 377 378 379 380
    // Update the usage counter of after_ since it is going to be used.
    after_->last_used = ++dst_usage_counter_;
  }

  // Now the time_sec is between before_->end_sec and after_->start_sec.
  // Only one daylight savings offset change can occur in this interval.

  if (before_->offset_ms == after_->offset_ms) {
    // Merge two segments if they have the same offset.
    before_->end_sec = after_->end_sec;
    ClearSegment(after_);
    return before_->offset_ms;
  }

  // Binary search for daylight savings offset change point,
381
  // but give up if we don't find it in five iterations.
382 383 384 385 386 387 388 389 390 391
  for (int i = 4; i >= 0; --i) {
    int delta = after_->start_sec - before_->end_sec;
    int middle_sec = (i == 0) ? time_sec : before_->end_sec + delta / 2;
    int offset_ms = GetDaylightSavingsOffsetFromOS(middle_sec);
    if (before_->offset_ms == offset_ms) {
      before_->end_sec = middle_sec;
      if (time_sec <= before_->end_sec) {
        return offset_ms;
      }
    } else {
392
      DCHECK(after_->offset_ms == offset_ms);
393 394 395 396 397 398 399 400 401 402
      after_->start_sec = middle_sec;
      if (time_sec >= after_->start_sec) {
        // This swap helps the optimistic fast check in subsequent invocations.
        DST* temp = before_;
        before_ = after_;
        after_ = temp;
        return offset_ms;
      }
    }
  }
403
  return 0;
404 405 406
}

void DateCache::ProbeDST(int time_sec) {
407 408
  DST* before = nullptr;
  DST* after = nullptr;
409
  DCHECK(before_ != after_);
410 411 412

  for (int i = 0; i < kDSTSize; ++i) {
    if (dst_[i].start_sec <= time_sec) {
413
      if (before == nullptr || before->start_sec < dst_[i].start_sec) {
414 415 416
        before = &dst_[i];
      }
    } else if (time_sec < dst_[i].end_sec) {
417
      if (after == nullptr || after->end_sec > dst_[i].end_sec) {
418 419 420 421 422 423 424
        after = &dst_[i];
      }
    }
  }

  // If before or after segments were not found,
  // then set them to any invalid segment.
425
  if (before == nullptr) {
426 427
    before = InvalidSegment(before_) ? before_ : LeastRecentlyUsedDST(after);
  }
428
  if (after == nullptr) {
429
    after = InvalidSegment(after_) && before != after_
Yang Guo's avatar
Yang Guo committed
430 431
                ? after_
                : LeastRecentlyUsedDST(before);
432 433
  }

434 435
  DCHECK_NOT_NULL(before);
  DCHECK_NOT_NULL(after);
436 437 438 439
  DCHECK(before != after);
  DCHECK(InvalidSegment(before) || before->start_sec <= time_sec);
  DCHECK(InvalidSegment(after) || time_sec < after->start_sec);
  DCHECK(InvalidSegment(before) || InvalidSegment(after) ||
440 441 442 443 444 445 446
         before->end_sec < after->start_sec);

  before_ = before;
  after_ = after;
}

DateCache::DST* DateCache::LeastRecentlyUsedDST(DST* skip) {
447
  DST* result = nullptr;
448 449
  for (int i = 0; i < kDSTSize; ++i) {
    if (&dst_[i] == skip) continue;
450
    if (result == nullptr || result->last_used > dst_[i].last_used) {
451 452 453 454 455 456 457
      result = &dst_[i];
    }
  }
  ClearSegment(result);
  return result;
}

458 459
}  // namespace internal
}  // namespace v8