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