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