1 // Copyright 2012 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/date.h" 6 7 #include "src/conversions.h" 8 #include "src/objects-inl.h" 9 #include "src/objects.h" 10 11 #ifdef V8_INTL_SUPPORT 12 #include "src/intl.h" 13 #endif 14 15 namespace v8 { 16 namespace internal { 17 18 19 static const int kDaysIn4Years = 4 * 365 + 1; 20 static const int kDaysIn100Years = 25 * kDaysIn4Years - 1; 21 static const int kDaysIn400Years = 4 * kDaysIn100Years + 1; 22 static const int kDays1970to2000 = 30 * 365 + 7; 23 static const int kDaysOffset = 1000 * kDaysIn400Years + 5 * kDaysIn400Years - 24 kDays1970to2000; 25 static const int kYearsOffset = 400000; 26 static const char kDaysInMonths[] = 27 {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 28 29 DateCache::DateCache() 30 : stamp_(0), 31 tz_cache_( 32 #ifdef V8_INTL_SUPPORT 33 FLAG_icu_timezone_data ? new ICUTimezoneCache() 34 : base::OS::CreateTimezoneCache() 35 #else 36 base::OS::CreateTimezoneCache() 37 #endif 38 ) { 39 ResetDateCache(); 40 } 41 42 void DateCache::ResetDateCache() { 43 static const int kMaxStamp = Smi::kMaxValue; 44 if (stamp_->value() >= kMaxStamp) { 45 stamp_ = Smi::kZero; 46 } else { 47 stamp_ = Smi::FromInt(stamp_->value() + 1); 48 } 49 DCHECK(stamp_ != Smi::FromInt(kInvalidStamp)); 50 for (int i = 0; i < kDSTSize; ++i) { 51 ClearSegment(&dst_[i]); 52 } 53 dst_usage_counter_ = 0; 54 before_ = &dst_[0]; 55 after_ = &dst_[1]; 56 ymd_valid_ = false; 57 #ifdef V8_INTL_SUPPORT 58 if (!FLAG_icu_timezone_data) { 59 #endif 60 local_offset_ms_ = kInvalidLocalOffsetInMs; 61 #ifdef V8_INTL_SUPPORT 62 } 63 #endif 64 tz_cache_->Clear(); 65 tz_name_ = nullptr; 66 dst_tz_name_ = nullptr; 67 } 68 69 // ECMA 262 - ES#sec-timeclip TimeClip (time) 70 double DateCache::TimeClip(double time) { 71 if (-kMaxTimeInMs <= time && time <= kMaxTimeInMs) { 72 return DoubleToInteger(time) + 0.0; 73 } 74 return std::numeric_limits<double>::quiet_NaN(); 75 } 76 77 void DateCache::ClearSegment(DST* segment) { 78 segment->start_sec = kMaxEpochTimeInSec; 79 segment->end_sec = -kMaxEpochTimeInSec; 80 segment->offset_ms = 0; 81 segment->last_used = 0; 82 } 83 84 85 void DateCache::YearMonthDayFromDays( 86 int days, int* year, int* month, int* day) { 87 if (ymd_valid_) { 88 // Check conservatively if the given 'days' has 89 // the same year and month as the cached 'days'. 90 int new_day = ymd_day_ + (days - ymd_days_); 91 if (new_day >= 1 && new_day <= 28) { 92 ymd_day_ = new_day; 93 ymd_days_ = days; 94 *year = ymd_year_; 95 *month = ymd_month_; 96 *day = new_day; 97 return; 98 } 99 } 100 int save_days = days; 101 102 days += kDaysOffset; 103 *year = 400 * (days / kDaysIn400Years) - kYearsOffset; 104 days %= kDaysIn400Years; 105 106 DCHECK_EQ(save_days, DaysFromYearMonth(*year, 0) + days); 107 108 days--; 109 int yd1 = days / kDaysIn100Years; 110 days %= kDaysIn100Years; 111 *year += 100 * yd1; 112 113 days++; 114 int yd2 = days / kDaysIn4Years; 115 days %= kDaysIn4Years; 116 *year += 4 * yd2; 117 118 days--; 119 int yd3 = days / 365; 120 days %= 365; 121 *year += yd3; 122 123 124 bool is_leap = (!yd1 || yd2) && !yd3; 125 126 DCHECK_GE(days, -1); 127 DCHECK(is_leap || (days >= 0)); 128 DCHECK((days < 365) || (is_leap && (days < 366))); 129 DCHECK(is_leap == ((*year % 4 == 0) && (*year % 100 || (*year % 400 == 0)))); 130 DCHECK(is_leap || ((DaysFromYearMonth(*year, 0) + days) == save_days)); 131 DCHECK(!is_leap || ((DaysFromYearMonth(*year, 0) + days + 1) == save_days)); 132 133 days += is_leap; 134 135 // Check if the date is after February. 136 if (days >= 31 + 28 + BoolToInt(is_leap)) { 137 days -= 31 + 28 + BoolToInt(is_leap); 138 // Find the date starting from March. 139 for (int i = 2; i < 12; i++) { 140 if (days < kDaysInMonths[i]) { 141 *month = i; 142 *day = days + 1; 143 break; 144 } 145 days -= kDaysInMonths[i]; 146 } 147 } else { 148 // Check January and February. 149 if (days < 31) { 150 *month = 0; 151 *day = days + 1; 152 } else { 153 *month = 1; 154 *day = days - 31 + 1; 155 } 156 } 157 DCHECK(DaysFromYearMonth(*year, *month) + *day - 1 == save_days); 158 ymd_valid_ = true; 159 ymd_year_ = *year; 160 ymd_month_ = *month; 161 ymd_day_ = *day; 162 ymd_days_ = save_days; 163 } 164 165 166 int DateCache::DaysFromYearMonth(int year, int month) { 167 static const int day_from_month[] = {0, 31, 59, 90, 120, 151, 168 181, 212, 243, 273, 304, 334}; 169 static const int day_from_month_leap[] = {0, 31, 60, 91, 121, 152, 170 182, 213, 244, 274, 305, 335}; 171 172 year += month / 12; 173 month %= 12; 174 if (month < 0) { 175 year--; 176 month += 12; 177 } 178 179 DCHECK_GE(month, 0); 180 DCHECK_LT(month, 12); 181 182 // year_delta is an arbitrary number such that: 183 // a) year_delta = -1 (mod 400) 184 // b) year + year_delta > 0 for years in the range defined by 185 // ECMA 262 - 15.9.1.1, i.e. upto 100,000,000 days on either side of 186 // Jan 1 1970. This is required so that we don't run into integer 187 // division of negative numbers. 188 // c) there shouldn't be an overflow for 32-bit integers in the following 189 // operations. 190 static const int year_delta = 399999; 191 static const int base_day = 365 * (1970 + year_delta) + 192 (1970 + year_delta) / 4 - 193 (1970 + year_delta) / 100 + 194 (1970 + year_delta) / 400; 195 196 int year1 = year + year_delta; 197 int day_from_year = 365 * year1 + 198 year1 / 4 - 199 year1 / 100 + 200 year1 / 400 - 201 base_day; 202 203 if ((year % 4 != 0) || (year % 100 == 0 && year % 400 != 0)) { 204 return day_from_year + day_from_month[month]; 205 } 206 return day_from_year + day_from_month_leap[month]; 207 } 208 209 210 void DateCache::BreakDownTime(int64_t time_ms, int* year, int* month, int* day, 211 int* weekday, int* hour, int* min, int* sec, 212 int* ms) { 213 int const days = DaysFromTime(time_ms); 214 int const time_in_day_ms = TimeInDay(time_ms, days); 215 YearMonthDayFromDays(days, year, month, day); 216 *weekday = Weekday(days); 217 *hour = time_in_day_ms / (60 * 60 * 1000); 218 *min = (time_in_day_ms / (60 * 1000)) % 60; 219 *sec = (time_in_day_ms / 1000) % 60; 220 *ms = time_in_day_ms % 1000; 221 } 222 223 // Implements LocalTimeZonedjustment(t, isUTC) 224 // ECMA 262 - ES#sec-local-time-zone-adjustment 225 int DateCache::GetLocalOffsetFromOS(int64_t time_ms, bool is_utc) { 226 double offset; 227 #ifdef V8_INTL_SUPPORT 228 if (FLAG_icu_timezone_data) { 229 offset = tz_cache_->LocalTimeOffset(static_cast<double>(time_ms), is_utc); 230 } else { 231 #endif 232 // When ICU timezone data is not used, we need to compute the timezone 233 // offset for a given local time. 234 // 235 // The following shows that using DST for (t - LocalTZA - hour) produces 236 // correct conversion where LocalTZA is the timezone offset in winter (no 237 // DST) and the timezone offset is assumed to have no historical change. 238 // Note that it does not work for the past and the future if LocalTZA (no 239 // DST) is different from the current LocalTZA (no DST). For instance, 240 // this will break for Europe/Moscow in 2012 ~ 2013 because LocalTZA was 241 // 4h instead of the current 3h (as of 2018). 242 // 243 // Consider transition to DST at local time L1. 244 // Let L0 = L1 - hour, L2 = L1 + hour, 245 // U1 = UTC time that corresponds to L1, 246 // U0 = U1 - hour. 247 // Transitioning to DST moves local clock one hour forward L1 => L2, so 248 // U0 = UTC time that corresponds to L0 = L0 - LocalTZA, 249 // U1 = UTC time that corresponds to L1 = L1 - LocalTZA, 250 // U1 = UTC time that corresponds to L2 = L2 - LocalTZA - hour. 251 // Note that DST(U0 - hour) = 0, DST(U0) = 0, DST(U1) = 1. 252 // U0 = L0 - LocalTZA - DST(L0 - LocalTZA - hour), 253 // U1 = L1 - LocalTZA - DST(L1 - LocalTZA - hour), 254 // U1 = L2 - LocalTZA - DST(L2 - LocalTZA - hour). 255 // 256 // Consider transition from DST at local time L1. 257 // Let L0 = L1 - hour, 258 // U1 = UTC time that corresponds to L1, 259 // U0 = U1 - hour, U2 = U1 + hour. 260 // Transitioning from DST moves local clock one hour back L1 => L0, so 261 // U0 = UTC time that corresponds to L0 (before transition) 262 // = L0 - LocalTZA - hour. 263 // U1 = UTC time that corresponds to L0 (after transition) 264 // = L0 - LocalTZA = L1 - LocalTZA - hour 265 // U2 = UTC time that corresponds to L1 = L1 - LocalTZA. 266 // Note that DST(U0) = 1, DST(U1) = 0, DST(U2) = 0. 267 // U0 = L0 - LocalTZA - DST(L0 - LocalTZA - hour) = L0 - LocalTZA - DST(U0). 268 // U2 = L1 - LocalTZA - DST(L1 - LocalTZA - hour) = L1 - LocalTZA - DST(U1). 269 // It is impossible to get U1 from local time. 270 if (local_offset_ms_ == kInvalidLocalOffsetInMs) { 271 // This gets the constant LocalTZA (arguments are ignored). 272 local_offset_ms_ = 273 tz_cache_->LocalTimeOffset(static_cast<double>(time_ms), is_utc); 274 } 275 offset = local_offset_ms_; 276 if (!is_utc) { 277 const int kMsPerHour = 3600 * 1000; 278 time_ms -= (offset + kMsPerHour); 279 } 280 offset += DaylightSavingsOffsetInMs(time_ms); 281 #ifdef V8_INTL_SUPPORT 282 } 283 #endif 284 DCHECK_LT(offset, kInvalidLocalOffsetInMs); 285 return static_cast<int>(offset); 286 } 287 288 void DateCache::ExtendTheAfterSegment(int time_sec, int offset_ms) { 289 if (after_->offset_ms == offset_ms && 290 after_->start_sec <= time_sec + kDefaultDSTDeltaInSec && 291 time_sec <= after_->end_sec) { 292 // Extend the after_ segment. 293 after_->start_sec = time_sec; 294 } else { 295 // The after_ segment is either invalid or starts too late. 296 if (after_->start_sec <= after_->end_sec) { 297 // If the after_ segment is valid, replace it with a new segment. 298 after_ = LeastRecentlyUsedDST(before_); 299 } 300 after_->start_sec = time_sec; 301 after_->end_sec = time_sec; 302 after_->offset_ms = offset_ms; 303 after_->last_used = ++dst_usage_counter_; 304 } 305 } 306 307 308 int DateCache::DaylightSavingsOffsetInMs(int64_t time_ms) { 309 int time_sec = (time_ms >= 0 && time_ms <= kMaxEpochTimeInMs) 310 ? static_cast<int>(time_ms / 1000) 311 : static_cast<int>(EquivalentTime(time_ms) / 1000); 312 313 // Invalidate cache if the usage counter is close to overflow. 314 // Note that dst_usage_counter is incremented less than ten times 315 // in this function. 316 if (dst_usage_counter_ >= kMaxInt - 10) { 317 dst_usage_counter_ = 0; 318 for (int i = 0; i < kDSTSize; ++i) { 319 ClearSegment(&dst_[i]); 320 } 321 } 322 323 // Optimistic fast check. 324 if (before_->start_sec <= time_sec && 325 time_sec <= before_->end_sec) { 326 // Cache hit. 327 before_->last_used = ++dst_usage_counter_; 328 return before_->offset_ms; 329 } 330 331 ProbeDST(time_sec); 332 333 DCHECK(InvalidSegment(before_) || before_->start_sec <= time_sec); 334 DCHECK(InvalidSegment(after_) || time_sec < after_->start_sec); 335 336 if (InvalidSegment(before_)) { 337 // Cache miss. 338 before_->start_sec = time_sec; 339 before_->end_sec = time_sec; 340 before_->offset_ms = GetDaylightSavingsOffsetFromOS(time_sec); 341 before_->last_used = ++dst_usage_counter_; 342 return before_->offset_ms; 343 } 344 345 if (time_sec <= before_->end_sec) { 346 // Cache hit. 347 before_->last_used = ++dst_usage_counter_; 348 return before_->offset_ms; 349 } 350 351 if (time_sec > before_->end_sec + kDefaultDSTDeltaInSec) { 352 // If the before_ segment ends too early, then just 353 // query for the offset of the time_sec 354 int offset_ms = GetDaylightSavingsOffsetFromOS(time_sec); 355 ExtendTheAfterSegment(time_sec, offset_ms); 356 // This swap helps the optimistic fast check in subsequent invocations. 357 DST* temp = before_; 358 before_ = after_; 359 after_ = temp; 360 return offset_ms; 361 } 362 363 // Now the time_sec is between 364 // before_->end_sec and before_->end_sec + default DST delta. 365 // Update the usage counter of before_ since it is going to be used. 366 before_->last_used = ++dst_usage_counter_; 367 368 // Check if after_ segment is invalid or starts too late. 369 // Note that start_sec of invalid segments is kMaxEpochTimeInSec. 370 if (before_->end_sec + kDefaultDSTDeltaInSec <= after_->start_sec) { 371 int new_after_start_sec = before_->end_sec + kDefaultDSTDeltaInSec; 372 int new_offset_ms = GetDaylightSavingsOffsetFromOS(new_after_start_sec); 373 ExtendTheAfterSegment(new_after_start_sec, new_offset_ms); 374 } else { 375 DCHECK(!InvalidSegment(after_)); 376 // Update the usage counter of after_ since it is going to be used. 377 after_->last_used = ++dst_usage_counter_; 378 } 379 380 // Now the time_sec is between before_->end_sec and after_->start_sec. 381 // Only one daylight savings offset change can occur in this interval. 382 383 if (before_->offset_ms == after_->offset_ms) { 384 // Merge two segments if they have the same offset. 385 before_->end_sec = after_->end_sec; 386 ClearSegment(after_); 387 return before_->offset_ms; 388 } 389 390 // Binary search for daylight savings offset change point, 391 // but give up if we don't find it in five iterations. 392 for (int i = 4; i >= 0; --i) { 393 int delta = after_->start_sec - before_->end_sec; 394 int middle_sec = (i == 0) ? time_sec : before_->end_sec + delta / 2; 395 int offset_ms = GetDaylightSavingsOffsetFromOS(middle_sec); 396 if (before_->offset_ms == offset_ms) { 397 before_->end_sec = middle_sec; 398 if (time_sec <= before_->end_sec) { 399 return offset_ms; 400 } 401 } else { 402 DCHECK(after_->offset_ms == offset_ms); 403 after_->start_sec = middle_sec; 404 if (time_sec >= after_->start_sec) { 405 // This swap helps the optimistic fast check in subsequent invocations. 406 DST* temp = before_; 407 before_ = after_; 408 after_ = temp; 409 return offset_ms; 410 } 411 } 412 } 413 return 0; 414 } 415 416 417 void DateCache::ProbeDST(int time_sec) { 418 DST* before = nullptr; 419 DST* after = nullptr; 420 DCHECK(before_ != after_); 421 422 for (int i = 0; i < kDSTSize; ++i) { 423 if (dst_[i].start_sec <= time_sec) { 424 if (before == nullptr || before->start_sec < dst_[i].start_sec) { 425 before = &dst_[i]; 426 } 427 } else if (time_sec < dst_[i].end_sec) { 428 if (after == nullptr || after->end_sec > dst_[i].end_sec) { 429 after = &dst_[i]; 430 } 431 } 432 } 433 434 // If before or after segments were not found, 435 // then set them to any invalid segment. 436 if (before == nullptr) { 437 before = InvalidSegment(before_) ? before_ : LeastRecentlyUsedDST(after); 438 } 439 if (after == nullptr) { 440 after = InvalidSegment(after_) && before != after_ 441 ? after_ : LeastRecentlyUsedDST(before); 442 } 443 444 DCHECK_NOT_NULL(before); 445 DCHECK_NOT_NULL(after); 446 DCHECK(before != after); 447 DCHECK(InvalidSegment(before) || before->start_sec <= time_sec); 448 DCHECK(InvalidSegment(after) || time_sec < after->start_sec); 449 DCHECK(InvalidSegment(before) || InvalidSegment(after) || 450 before->end_sec < after->start_sec); 451 452 before_ = before; 453 after_ = after; 454 } 455 456 457 DateCache::DST* DateCache::LeastRecentlyUsedDST(DST* skip) { 458 DST* result = nullptr; 459 for (int i = 0; i < kDSTSize; ++i) { 460 if (&dst_[i] == skip) continue; 461 if (result == nullptr || result->last_used > dst_[i].last_used) { 462 result = &dst_[i]; 463 } 464 } 465 ClearSegment(result); 466 return result; 467 } 468 469 } // namespace internal 470 } // namespace v8 471