Add QCalendar::matchCenturyToWeekday()

This takes a YearMonthDay and a day-of-the-week, returning a QDate
that (if possible, else invalid) has the given day of the week and
differs from the YearMonthDay only in the century. This is useful when
resolving dates with only two-digit year information, which can be
disambiguated by the day of the week. Added tests of the new API.

This adds a new virtual method to QCalendarBackend, for which that
base class does provide a brute force implementation, so derived
classes do not need to add implementations. It is, however, a
binary-incompatible change for any backend plugins that may be in use
to implement custom calendars.

Worked out the details for the Gregorian calendar to make it possible
to compute the right century (and whether any century works) without
trial-and-error searching. Coded that up as its implementation of the
new method.

[ChangeLog][QtCore][QCalendar] Added a matchCenturyToWeekday() method
for use when resolving dates given day, month and last two digits of
the year, along with day of the week. Any custom calendar backend
plugins shall need a recompile and may, optionally, implement the new
virtual method behind this.

Change-Id: I6003c8d9423d6bfb833957bb5120f2d423219c7a
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

6 files changed, 191 insertions, 7 deletions

diff --git a/src/corelib/time/qcalendar.cpp b/src/corelib/time/qcalendar.cpp
index 5eaecedbbd..415203ee17 100644
--- a/src/corelib/time/qcalendar.cpp
+++ b/src/corelib/time/qcalendar.cpp
@@ -853,20 +853,75 @@ int QCalendarBackend::maximumMonthsInYear() const
    already used in QDate::dayOfWeek() to mean an invalid date). The calendar
    should treat the numbers used as an \c enum, whose values need not be
    contiguous, nor need they follow closely from the 1 through 7 of the usual
-   returns. It suffices that weekDayName() can recognize each such number as
-   identifying a distinct name, that it returns to identify the particular
-   intercallary day.
+   returns. It suffices that;
+   \list
+     \li weekDayName() can recognize each such number as identifying a distinct
+         name, that it returns to identify the particular intercallary day; and
+     \li matchCenturyToWeekday() can determine what century adjustment aligns a
+         given date within a century to a given day of the week, where this is
+         relevant and possible.
+   \endlist
 
    This base implementation uses the day-numbering that various calendars have
    borrowed off the Hebrew calendar.
 
-   \sa weekDayName(), standaloneWeekDayName(), QDate::dayOfWeek()
- */
+   \sa weekDayName(), standaloneWeekDayName(), QDate::dayOfWeek(), Qt::DayOfWeek
+*/
 int QCalendarBackend::dayOfWeek(qint64 jd) const
 {
     return QRoundingDown::qMod<7>(jd) + 1;
 }
 
+/*!
+    \since 6.7
+    Adjusts century of \a parts to match \a dow.
+
+    Preserves parts.month and parts.day while adjusting parts.year by a multiple
+    of 100 (taking the absence of year zero into account, when relevant) to
+    obtain a date for which dayOfWeek() is \a dow. Prefers smaller changes over
+    larger and increases to the century over decreases of the same
+    magnitude. Returns the Julian Day number for the selected date or
+    std::numeric_limits<qint64>::min(), a.k.a. QDate::nullJd(), if there is no
+    date matching these requirements.
+
+    The base-class provides a brute-force implementation that steps outwards
+    from the given date by centures, above and below by up to 14 centuries, in
+    search of a matching date. This is neither computationally efficient nor
+    elegant but should work as advertised for calendars in which every month-day
+    combination does appear on all days of the week, across sufficiently many
+    centuries.
+*/
+qint64 QCalendarBackend::matchCenturyToWeekday(const QCalendar::YearMonthDay &parts, int dow) const
+{
+    Q_ASSERT(parts.isValid());
+    // Brute-force solution as fall-back.
+    const auto checkOffset = [parts, dow, this](int centuries) -> std::optional<qint64> {
+        // Offset parts.year by the given number of centuries:
+        int year = parts.year + centuries * 100;
+        // but take into account the effect of crossing zero, if we did:
+        if (!hasYearZero() && (parts.year > 0) != (year > 0))
+            year += parts.year > 0 ? -1 : +1;
+        qint64 jd;
+        if (isDateValid(year, parts.month, parts.day)
+            && dateToJulianDay(year, parts.month, parts.day, &jd)
+            && dayOfWeek(jd) == dow) {
+            return jd;
+        }
+        return std::nullopt;
+    };
+    // Empirically, aside from Gregorian, each calendar finds every dow within
+    // any 29-century run, so 14 centuries is the biggest offset we ever need.
+    for (int offset = 0; offset < 15; ++offset) {
+        if (auto jd = checkOffset(offset))
+            return *jd;
+        if (offset) {
+            if (auto jd = checkOffset(-offset))
+                return *jd;
+        }
+    }
+    return (std::numeric_limits<qint64>::min)();
+}
+
 // Month and week-day name look-ups (implemented in qlocale.cpp):
 /*!
     \fn QString QCalendarBackend::monthName(const QLocale &locale, int month, int year,
@@ -1425,6 +1480,32 @@ QDate QCalendar::dateFromParts(const QCalendar::YearMonthDay &parts) const
 }
 
 /*!
+    \since 6.7
+    Adjusts the century of a date to match a given day of the week.
+
+    For use when given a date's day of week, day of month, month and last two
+    digits of the year. Returns a QDate instance with the given \a dow as its \l
+    {QDate::}{dayOfWeek()}, matching the given \a parts in month and day of the
+    month. The returned QDate's \l {QDate::}{year()} shall differ from
+    \c{parts.year} by a multiple of 100, preferring small multiples over larger
+    and positive multiples over their negations.
+
+    If no date matches these conditions, an invalid QDate is returned: the day
+    of week is incompatible with the other data given. This arises, for example,
+    with the Gregorian calendar, whose 400-year cycle is a whole number of weeks
+    long, so any given month and day of that month only ever falls, in years
+    with a given last two digits, on four days of the week. (In the special case
+    of February 29th at the turn of a century, when that is a leap year, only
+    one day of the week is possible: Tuesday.)
+*/
+QDate QCalendar::matchCenturyToWeekday(const QCalendar::YearMonthDay &parts, int dow) const
+{
+    SAFE_D();
+    return d && parts.isValid()
+        ? QDate::fromJulianDay(d->matchCenturyToWeekday(parts, dow)) : QDate();
+}
+
+/*!
     Converts a QDate to a year, month, and day of the month.
 
     The returned structure's isValid() shall be false if the calendar is unable
diff --git a/src/corelib/time/qcalendar.h b/src/corelib/time/qcalendar.h
index ce8845f5e6..434f06d67f 100644
--- a/src/corelib/time/qcalendar.h
+++ b/src/corelib/time/qcalendar.h
@@ -144,6 +144,7 @@ public:
     // QDate conversions:
     QDate dateFromParts(int year, int month, int day) const;
     QDate dateFromParts(const YearMonthDay &parts) const;
+    QDate matchCenturyToWeekday(const YearMonthDay &parts, int dow) const;
     YearMonthDay partsFromDate(QDate date) const;
     int dayOfWeek(QDate date) const;
 
diff --git a/src/corelib/time/qcalendarbackend_p.h b/src/corelib/time/qcalendarbackend_p.h
index 6f2782f506..88bb71b22e 100644
--- a/src/corelib/time/qcalendarbackend_p.h
+++ b/src/corelib/time/qcalendarbackend_p.h
@@ -86,8 +86,9 @@ public:
     // Julian Day conversions:
     virtual bool dateToJulianDay(int year, int month, int day, qint64 *jd) const = 0;
     virtual QCalendar::YearMonthDay julianDayToDate(qint64 jd) const = 0;
-    // Day of week and week numbering:
+    // Day of week:
     virtual int dayOfWeek(qint64 jd) const;
+    virtual qint64 matchCenturyToWeekday(const QCalendar::YearMonthDay &parts, int dow) const;
 
     // Names of months and week-days (implemented in qlocale.cpp):
     virtual QString monthName(const QLocale &locale, int month, int year,
diff --git a/src/corelib/time/qgregoriancalendar.cpp b/src/corelib/time/qgregoriancalendar.cpp
index 7db32e4cad..d46d24ac30 100644
--- a/src/corelib/time/qgregoriancalendar.cpp
+++ b/src/corelib/time/qgregoriancalendar.cpp
@@ -109,6 +109,59 @@ QCalendar::YearMonthDay QGregorianCalendar::julianDayToDate(qint64 jd) const
     return partsFromJulian(jd);
 }
 
+qint64
+QGregorianCalendar::matchCenturyToWeekday(const QCalendar::YearMonthDay &parts, int dow) const
+{
+    /* The Gregorian four-century cycle is a whole number of weeks long, so we
+       only need to consider four centuries, from previous through next-but-one.
+       There are thus three days of the week that can't happen, for any given
+       day-of-month, month and year-mod-100. (Exception: '00 Feb 29 has only one
+       option.)
+    */
+    auto maybe = julianFromParts(parts.year, parts.month, parts.day);
+    if (maybe) {
+        int diff = weekDayOfJulian(*maybe) - dow;
+        if (!diff)
+            return *maybe;
+        int year = parts.year < 0 ? parts.year + 1 : parts.year;
+        // What matters is the placement of leap days, so dates before March
+        // effectively belong with the dates since the preceding March:
+        const auto yearSplit = qDivMod<100>(year - (parts.month < 3 ? 1 : 0));
+        const int centuryMod4 = qMod<4>(yearSplit.quotient);
+        // Week-day shift for a century is 5, unless crossing a multiple of 400's Feb 29th.
+        static_assert(qMod<7>(36524) == 5); // and (3 * 5) % 7 = 1
+        // Formulae arrived at by case-by-case analysis of the values of
+        // centuryMod4 and diff (and the above clue to multiply by -3 = 4):
+        if (qMod<7>(diff * 4 + centuryMod4) < 4) {
+            // Century offset maps qMod<7>(diff) in {5, 6} to -1, {3, 4} to +2, and {1, 2} to +1:
+            year += (((qMod<7>(diff) + 3) / 2) % 4 - 1) * 100;
+            maybe = julianFromParts(year > 0 ? year : year - 1, parts.month, parts.day);
+            if (maybe && weekDayOfJulian(*maybe) == dow)
+                return *maybe;
+            Q_ASSERT(parts.month == 2 && parts.day == 29
+                     && dow != int(Qt::Tuesday) && !(year % 100));
+        }
+
+    } else if (parts.month == 2 && parts.day == 29) {
+        int year = parts.year < 0 ? parts.year + 1 : parts.year;
+        // Feb 29th on a century needs to resolve to a multiple of 400 years.
+        const auto yearSplit = qDivMod<100>(year);
+        if (!yearSplit.remainder) {
+            const auto centuryMod4 = qMod<4>(yearSplit.quotient);
+            Q_ASSERT(centuryMod4); // or we'd have got a valid date to begin with.
+            if (centuryMod4 == 1) // round down
+                year -= 100;
+            else // 2 or 3; round up
+                year += (4 - centuryMod4) * 100;
+            maybe = julianFromParts(year > 0 ? year : year - 1, parts.month, parts.day);
+            if (maybe && weekDayOfJulian(*maybe) == dow) // (Can only happen for Tuesday.)
+                return *maybe;
+            Q_ASSERT(dow != int(Qt::Tuesday));
+        }
+    }
+    return (std::numeric_limits<qint64>::min)();
+}
+
 int QGregorianCalendar::yearStartWeekDay(int year)
 {
     // Equivalent to weekDayOfJulian(julianForParts({year, 1, 1})
diff --git a/src/corelib/time/qgregoriancalendar_p.h b/src/corelib/time/qgregoriancalendar_p.h
index 9465581f83..1093a7b9de 100644
--- a/src/corelib/time/qgregoriancalendar_p.h
+++ b/src/corelib/time/qgregoriancalendar_p.h
@@ -34,6 +34,7 @@ public:
     // Julian Day conversions:
     bool dateToJulianDay(int year, int month, int day, qint64 *jd) const override;
     QCalendar::YearMonthDay julianDayToDate(qint64 jd) const override;
+    qint64 matchCenturyToWeekday(const QCalendar::YearMonthDay &parts, int dow) const override;
 
     // Static optimized versions for the benefit of QDate:
     static int weekDayOfJulian(qint64 jd);
diff --git a/tests/auto/corelib/time/qcalendar/tst_qcalendar.cpp b/tests/auto/corelib/time/qcalendar/tst_qcalendar.cpp
index 4eebce6d80..739f9ab1f4 100644
--- a/tests/auto/corelib/time/qcalendar/tst_qcalendar.cpp
+++ b/tests/auto/corelib/time/qcalendar/tst_qcalendar.cpp
@@ -31,6 +31,49 @@ private slots:
     void gregory();
 };
 
+static void checkCenturyResolution(const QCalendar &cal, const QCalendar::YearMonthDay &base)
+{
+    quint8 weekDayMask = 0;
+    for (int offset = -7; offset < 8; ++offset) {
+        const auto probe = QDate(base.year, base.month, base.day, cal).addYears(100 * offset, cal);
+        const int dow = cal.dayOfWeek(probe);
+        if (probe.isValid() && dow > 0 && dow < 8)
+            weekDayMask |= 1 << quint8(dow - 1);
+    }
+    for (int j = 1; j < 8; ++j) {
+        const bool seen = weekDayMask & (1 << quint8(j - 1));
+        const QDate check = cal.matchCenturyToWeekday(base, j);
+        if (check.isValid()) {
+            const auto parts = cal.partsFromDate(check);
+            const int dow = cal.dayOfWeek(check);
+            QCOMPARE(dow, j);
+            QCOMPARE(parts.day, base.day);
+            QCOMPARE(parts.month, base.month);
+            int gap = parts.year - base.year;
+            if (!cal.hasYearZero() && (parts.year > 0) != (base.year > 0))
+                gap += parts.year > 0 ? -1 : +1;
+            auto report = qScopeGuard([parts, base]() {
+                qDebug("Wrongly matched year: %d replaced %d", parts.year, base.year);
+            });
+            QCOMPARE(gap % 100, 0);
+            // We searched 7 centuries each side of base.
+            if (seen) {
+                QCOMPARE_LT(gap / 100, 8);
+                QCOMPARE_GT(gap / 100, -8);
+            } else {
+                QVERIFY(gap / 100 >= 8 || gap / 100 <= -8);
+            }
+            report.dismiss();
+        } else {
+            auto report = qScopeGuard([j, base]() {
+                qDebug("Missed dow[%d] for %d/%d/%d", j, base.year, base.month, base.day);
+            });
+            QVERIFY(!seen);
+            report.dismiss();
+        }
+    }
+}
+
 // Support for basic():
 void tst_QCalendar::checkYear(const QCalendar &cal, int year, bool normal)
 {
@@ -49,7 +92,7 @@ void tst_QCalendar::checkYear(const QCalendar &cal, int year, bool normal)
 
     int sum = 0;
     const int longest = cal.maximumDaysInMonth();
-    for (int i = moons; i > 0; i--) {
+    for (int i = moons; i > 0; --i) {
         const int last = cal.daysInMonth(i, year);
         sum += last;
         // Valid month has some days and no more than max:
@@ -62,6 +105,10 @@ void tst_QCalendar::checkYear(const QCalendar &cal, int year, bool normal)
         QVERIFY(!cal.isDateValid(year, i, last + 1));
         if (normal) // Unspecified year gets same daysInMonth():
             QCOMPARE(cal.daysInMonth(i), last);
+
+        checkCenturyResolution(cal, {year, i, (last + 1) / 2});
+        if (QTest::currentTestFailed())
+            return;
     }
     // Months add up to the whole year:
     QCOMPARE(sum, days);