Implement Calendar.RecurrenceRule.recurrences(of: ) by hristost · Pull Request #464 · swiftlang/swift-foundation

hristost · 2024-03-06T18:40:09Z

This commit implements the Calendar.RecurrenceRule type first pitched in #422.

This type models a subset of RRULE as specified in RFC-5545, section 3.3.10. One
notable difference is that it doesn't support a frequency of "secondly", as that
was not part of the original proposal. It also implements RFC-7529 Non-Gregorian
Recurrence Rules and works with any instance of Calendar.

Recurrences are calculated according to our interpretation of the RFCs. As such,
the resulting dates may differ in certain edge cases when compared to other open
source implementations.

Resolves rdar://120559017&123337748

sarimabbas

LGTM 👍

hristost · 2024-04-02T16:56:56Z

Tests/FoundationInternationalizationTests/CalendarRecurrenceRuleTests.swift

+@available(FoundationPreview 0.4, *)
 final class CalendarRecurrenceRuleTests: XCTestCase {
-
-    func testRoundtripEncoding() throws {


This test was moved to FoundationEssentialsTests

hristost · 2024-04-02T17:01:32Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                    case .weekly:   40 * 53
+                    case .daily:    40 * 366
+                    case .hourly:   40 * 366 * 24
+                    case .minutely: 40 * 366 * 24 * 60


These limits are somewhat arbitrary, but ultimately we wouldn't want RecurrenceRule to be used as a predicate for finding rare dates

parkera · 2024-04-02T19:59:06Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+
+extension Calendar {
+    /// A `Sequence` of `Date`s produced by a given recurrence rule
+    @available(FoundationPreview 0.4, *)


Does this need availability even if it's only returned via some Protocol API?

Possibly not, is there any downside to annotating availability?

At the very least, it's confusing. I would like to know what the correct answer is, though.

@hristost Were you able to remove this? If not, what error did the compiler give?

My bad, I missed this message. I removed the annotation -- we don't need it.

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

parkera · 2024-04-02T20:00:57Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+
+            /// An iterator for a sequence of dates spaced evenly from the start
+            /// date, by the interval specified by the recurrence rule frequency
+            /// This does not include the start date itself.


Style nit, but elsewhere in the project we do not manually wrap these comments.

parkera · 2024-04-02T20:03:51Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                // rdar://124640028
+                // https://github.com/apple/swift-foundation/issues/483
+                // Calendar.dates(byMatching: ...) does not respect repeatedTimePolicy when .nanosecond is set #483
+                let components: Calendar.ComponentSet = switch recurrence.frequency {


Does it even make sense to ever include nanoseconds in these results? It's so sparsely supported in the first place. Maybe it should really just always be set to 0.

@hristost What do you think?

I can't actually imagine a use case of a recurrence rule where we'd care about the nanoseconds, so I can just remove this to keep things simple.

parkera · 2024-04-02T20:04:53Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                let componentsForEnumerating = recurrence.calendar._dateComponents(components, from: start) 
+
+                let rangeForBaseRecurrence: Range<Date>? = nil
+                baseRecurrence = Calendar.DatesByMatching(calendar: recurrence.calendar,


Why create this directly instead of calling the dates(byMatching:...) API on Calendar? There doesn't seem to be much reason to break the abstraction.

We need to store the iterator, since it is used throughout the enumeration and we don't want to reset. We can't use dates(byMatching: ...).makeIterator() because we need to save this in a var the structure, and thus it'd need to be Sendable. any (IteratorProtocol<Date> & Sendable) does not currently compile (rdar://104888113), so we just represent it using the internal type which is known to be Sendable

parkera · 2024-04-02T20:05:42Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                }
+                while let nextDate = next() {
+                    // Skip every few iterations when an interval has been given
+                    if (iterations - 1) % recurrence.interval != 0 {


I don't quite understand what this logic is about. Can you explain a bit more?

Per the RFC: The interval part of a recurrence rule specifies at which
intervals the event repeats. A value of 1 indicates every
interval, and any n > 1 means every n-th interval. E.g, a
recurrence with frequency=.yearly and interval=5 will
repeat every 5 years.

Here, baseRecurrence repeats the date over the specified frequency with interval=1, and we need to skip some matches to compensate

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

parkera · 2024-04-02T20:08:03Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+
+                if case let .afterDate(limit) = recurrence.end._guts {
+                    let hadDates = !dates.isEmpty
+                    dates = dates.filter { $0 <= limit }


I'm not sure if this is actionable, but it seems like a reason to specify a limit is to avoid the cost of finding those dates in the first place - not just to filter them out at the end. Is it possible to do that?

I can't think of a way to do that. Even if we have dates that are past the limit, further expansions may generate dates that are before the limit.

Tests/FoundationEssentialsTests/GregorianCalendarRecurrenceRuleTests.swift

hristost · 2024-04-05T19:22:28Z

Benchmarks/Benchmarks/Calendar/Calendar.swift

+        for _ in rule.recurrences(of: thanksgivingStart) {
+            count += 1
+        }
+        assert(count == 1000)


The assertion is there to make sure the compiler wouldn't optimize anything out.

The benchmarks are a bit flaky right now and may cause the compiler to crash, I am working to figure out which change introduced that. They do run when we pick RecurrenceRule to an older commit of the same branch, and results are as follows:

nextThousandThanksgivings ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Throughput (# / s) (K) │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (μs) * │ 1564 │ 1564 │ 1564 │ 1567 │ 1567 │ 1567 │ 1567 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (μs) * │ 1577 │ 1578 │ 1578 │ 1581 │ 1581 │ 1581 │ 1581 │ 2 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛ nextThousandThanksgivingsSequence ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Throughput (# / s) (K) │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 1 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (μs) * │ 1590 │ 1591 │ 1591 │ 1591 │ 1591 │ 1591 │ 1591 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (μs) * │ 1604 │ 1604 │ 1604 │ 1604 │ 1604 │ 1604 │ 1604 │ 2 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛ nextThousandThanksgivingsUsingRecurrenceRule ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 1 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (ms) * │ 301 │ 301 │ 301 │ 301 │ 301 │ 301 │ 301 │ 1 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (ms) * │ 304 │ 304 │ 304 │ 304 │ 304 │ 304 │ 304 │ 1 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛

~~Somehow we achieve a significant speedup even though RecurrenceRule does component matching under the hood. Perhaps the weekOfMonth component is a bit slow, we don't really use it.~~. RecurrenceRule is currently waay slower than enumerating with just the date components -- 300 vs 1.5ms.

This is amazing but also curious.
rule.weekdays = [.nth(4, .thursday)] still essentially uses .weekOfMonth in _weekdayComponents, doesn't it? (Though I didn't really run the code, so I could read it wrong)

I fixed an obvious performance pitfall (we were enumerating over a wider range than needed), and now we are within <4x runtime of the benchmark that uses enumeration by date components. Since we also own the implementation for matching date components, the next step would be to bypass the public API and use some of the internals to get the runtime even closer.

The original benchmark (nextThousandThanksgivings) does not actually compute Thanksgivings as the name implies. It finds the Thursday in the fourth week of November, which is not necessarily the fourth Thursday in November. Is it permissible to update the benchmark given that the runtime will be slightly different?

Since we also own the implementation for matching date components, the next step would be to bypass the public API and use some of the internals to get the runtime even closer.

I got started on this, but the potential performance improvement does not seem to justify the amount of work it takes to get there. I'd like to merge the implementation as it is now, and revisit performance with a later PR. The benchmarks taken on my machine are as follows:

nextThousandThanksgivings ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 426 │ 426 │ 426 │ 426 │ 426 │ 426 │ 426 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Throughput (# / s) (K) │ 2 │ 2 │ 2 │ 2 │ 2 │ 2 │ 2 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (μs) * │ 580 │ 581 │ 581 │ 583 │ 583 │ 583 │ 583 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (μs) * │ 582 │ 584 │ 584 │ 586 │ 586 │ 586 │ 586 │ 6 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛ nextThousandThanksgivingsSequence ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 426 │ 426 │ 426 │ 426 │ 426 │ 426 │ 426 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Throughput (# / s) (K) │ 2 │ 2 │ 2 │ 2 │ 2 │ 2 │ 2 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (μs) * │ 580 │ 581 │ 581 │ 581 │ 581 │ 581 │ 581 │ 6 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (μs) * │ 582 │ 584 │ 584 │ 585 │ 586 │ 586 │ 586 │ 6 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛ nextThousandThanksgivingsUsingRecurrenceRule ╒═══════════════════════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╤═════════╕ │ Metric │ p0 │ p25 │ p50 │ p75 │ p90 │ p99 │ p100 │ Samples │ ╞═══════════════════════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╪═════════╡ │ Malloc (total) * │ 861 │ 861 │ 861 │ 861 │ 861 │ 861 │ 861 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (total CPU) (μs) * │ 2121 │ 2121 │ 2121 │ 2129 │ 2129 │ 2129 │ 2129 │ 2 │ ├───────────────────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┼─────────┤ │ Time (wall clock) (μs) * │ 2135 │ 2136 │ 2136 │ 2140 │ 2140 │ 2140 │ 2140 │ 2 │ ╘═══════════════════════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╧═════════╛

Ok, that seems reasonable for now. Let's file a follow-up bug just so we don't lose track of the task.

Tracking that in #555 (rdar://126761035)

itingliu · 2024-04-05T20:08:23Z

Benchmarks/Benchmarks/Calendar/Calendar.swift

+        for _ in rule.recurrences(of: thanksgivingStart) {
+            count += 1
+        }
+        assert(count == 1000)


This is amazing but also curious.
rule.weekdays = [.nth(4, .thursday)] still essentially uses .weekOfMonth in _weekdayComponents, doesn't it? (Though I didn't really run the code, so I could read it wrong)

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

itingliu · 2024-04-05T21:46:46Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+            if month.index > 0 {
+                return month
+            } else {
+                let newIndex = monthRange!.upperBound + month.index


Since you're already normalizing negative months, should we also handle months that are greater or equal than monthRange.upperBound?

I wouldn't call that normalization, it's simply so we can address months which are usually counted backwards. We can normalize by filtering the resulting array later, but also we achieve the same results now by leaving invalid months in, and having Calendar APIs return nil

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

itingliu

Super cool to see this in action. I had some comments about mini-optimization but overall looks good

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

itingliu · 2024-04-23T19:14:53Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                // rdar://124640028
+                // https://github.com/apple/swift-foundation/issues/483
+                // Calendar.dates(byMatching: ...) does not respect repeatedTimePolicy when .nanosecond is set #483
+                let components: Calendar.ComponentSet = switch recurrence.frequency {


@hristost What do you think?

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

hristost · 2024-04-24T21:46:45Z

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

+                    if dayOfMonth > 0 {
+                        if dayOfMonth == day { return true }
+                    } else {
+                        if dayRange == nil {


We can't have lazy var inside a closure for some reason, so we store the day range in an optional and calculate it the first time it is assigned.

itingliu

Just one more pending question about availability annotation

hristost · 2024-04-29T20:33:32Z

@swift-ci please test

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift

hristost · 2024-04-30T21:03:29Z

@swift-ci please test

hristost · 2024-04-30T21:21:19Z

@swift-ci please test

This commit implements `Calendar.RecurrenceRule.recurrences(of:in:)` as pitched in swiftlang#422. This type models a subset of RRULE as specified in RFC-5545, section 3.3.10. One notable difference is that it doesn't support a frequency of "secondly", as that was not part of the original proposal. It also implements RFC-7529 Non-Gregorian Recurrence Rules and works with any instance of `Calendar`. Recurrences are calculated according to our interpretation of the RFCs. As such, the resulting dates may differ in certain edge cases when compared to other open source implementations.

Addressed requested changes

hristost force-pushed the hstaykov/calendar-recurrence-rule-impl branch 3 times, most recently from 082f5d8 to fdf028c Compare March 15, 2024 20:21

hristost marked this pull request as ready for review March 15, 2024 20:23

sarimabbas approved these changes Mar 15, 2024

View reviewed changes

itingliu mentioned this pull request Mar 25, 2024

Introduce Calendar.RecurrenceRule #506

Closed

hristost requested a review from iCharlesHu March 25, 2024 18:09

iCharlesHu approved these changes Mar 25, 2024

View reviewed changes

hristost changed the title ~~Implement Calendar.RecurrenceRule~~ Implement Calendar.RecurrenceRule.recurrences(of: ) Mar 26, 2024

hristost force-pushed the hstaykov/calendar-recurrence-rule-impl branch 2 times, most recently from 4e091f3 to 0091100 Compare April 2, 2024 16:53

hristost requested review from itingliu and parkera April 2, 2024 16:57

hristost commented Apr 2, 2024

View reviewed changes

parkera reviewed Apr 2, 2024

View reviewed changes

hristost commented Apr 5, 2024

View reviewed changes

itingliu reviewed Apr 5, 2024

View reviewed changes

hristost requested review from iCharlesHu, itingliu and parkera April 19, 2024 17:38

itingliu reviewed Apr 23, 2024

View reviewed changes

hristost commented Apr 24, 2024

View reviewed changes

itingliu previously requested changes Apr 28, 2024

View reviewed changes

parkera reviewed Apr 30, 2024

View reviewed changes

Sources/FoundationEssentials/Calendar/Calendar_Recurrence.swift Outdated Show resolved Hide resolved

parkera approved these changes Apr 30, 2024

View reviewed changes

hristost force-pushed the hstaykov/calendar-recurrence-rule-impl branch from beeed5b to 1d4ce5e Compare April 30, 2024 20:35

hristost force-pushed the hstaykov/calendar-recurrence-rule-impl branch from 1d4ce5e to e353553 Compare May 1, 2024 19:12

hristost merged commit 12a48a2 into swiftlang:main May 1, 2024

Conversation

hristost commented Mar 6, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sarimabbas left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

hristost Apr 5, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

itingliu left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

hristost commented Mar 6, 2024 •

edited

Loading

hristost Apr 5, 2024 •

edited

Loading

itingliu left a comment •

edited

Loading

itingliu left a comment •

edited

Loading