Subject: Re: RECAP & Questions of CPL RECUR Issues.

From: [email-masked]
Date: Thu, 26 Jul 2001 15:36:23 -0400

Graham wrote:
>                                                               How many
>vCalendar (1.0) implementations exist out there simply because iCalendar
>was seen as too hard to implement?

  Just now getting back to CalSched backlog so excuse the lag here...

  vCalendar is very simple to do BECAUSE it has no workflow.  Standalone 
PIM Calendaring (no Scheduling) IS very well understood and easily done. 
When you add the complexity of workflow (ie: Scheduling) then it is no 
longer easy to manage, especially if you want to do it in a heterogenous 
environment.  If there were one clear, concise Calendaring and Scheduling model then we would not need to have this WG still arguing 
over trivial stuff like RSVP or very odd boundary cases for repeat 
grammars.

  This is partly why we still have pending questions on the table like 
Delegation chains, etc.  You do not have to worry about that w/the much 
simpler Calendaring world.  But we digress from the issue which I think 
(hope) should be resolved by now.  I had asked Tom (Robert) Ransdell to 
take over the BYSETPOS thread for me when I got yanked off by mgmt...

Bruce
===========================================================================
Bruce Kahn                                INet: [email-masked]
Iris Associates                          Phone: 978.392.5335
Westford, MA, USA 01886                    FAX: and nothing but the FAX...
Standard disclaimers apply, even where prohibited by law...

---

From: Jonathan Lennox <[email-masked]>
Date: Thu, 26 Jul 2001 17:16:32 -0400 (EDT)

>   Just now getting back to CalSched backlog so excuse the lag here...

I've been ignoring things too.  I apologize.

> But we digress from the issue which I think 

It should have been resolved, but I don't think it has been.   We digressed
pretty badly from the discussion.

There are, I think, a few rather independent issues that came up.

1.  The RECUR spec is confusingly-written, and has a lot of under-specified
    corner cases.  This probably results in a fairly large amount of
    interoperability difficulty.  I think there's consensus that this is a
    bad thing, but not much commitment to do anything about it; nor is there
    necessarily consensus on what the proper interpretation of all the
    corner cases should *be*.

2.  The RECUR spec is general enough that it can give rise to "paradoxical"
    event descriptions -- that is, ones that can never occur.  There was
    some effort to modify the spec to forbid certain "easy" paradoxical
    descriptions, but it's not clear that this will be sufficient.  There
    was also some counter-pressure with the opinion that paradoxical
    recurrence descriptions shouldn't be forbidden, since their semantics
    are clear -- "this never happens" -- and they may add additional
    complexity to code to forbid them.  I'm agnostic on this point.

3.  Finally, the big point.  There was a lot of concern over the fact that
    recurrence descriptions, in their full glorious generality, can require
    (nearly) arbitrarily large amounts of computing power to resolve.  (Note
    that there were a few different definitions of "resolve" in play here.)
    This is directly contradictory to the requirements for CPL, which
    require that processing requirements for a CPL script to be predictable
    and bounded.

    There were a number of proposals for what to do about this, which turned
    out to be dependent on the resolution to point 1 (thus the digression).

    The classes of solutions could be summarized as follows:

    A. Re-define RECUR in the successor to RFC 2445, eliminating the
       problematic constructs.  This will break backward compatibility, in
       theory (though it's not clear how much the problematic constructs are
       used in practice).

    B. Allow CPL, and other "consumers" of the iCalendar spec, to define
       subsets of the full RECUR specification.  This will break
       interoperability between subset-consumers, which can no longer import
       full CPL RECUR statements.

    C. Declare that implementations of RECUR are free to implement as much
       or as little of the specification as they choose to, so long as they
       have some way to detect and report that a RECUR specification exceeds
       their implementation limits.  This will make interoperability
       effectively entirely unpredictable.

    D. Define limits, at SHOULD strength, parameterizing the items that a
       RECUR interpreter ought to support.  Similarly, say that RECUR
       generators SHOULD NOT exceed these limits unless they know through
       some out-of-band means that their interpreter will be able to process
       them correctly.  This is effectively a version of option A which
       "walls off" the problematic constructs without removing them
       entirely.

    I'd also like to review what I saw as the problematic constructs in
    question.  Since, as I mentioned before, the definition of "resolve"
    depends on what people are trying to do, I'll give one, the one that CPL
    needs: "Given a recurrence rule, and an instant in time, does the
    instant fall within some repetition of the recurrence rule?"  (This is,
    incidentally, equivalent to the question "Given a recurrence rule, and
    an instant in time, is there a start time of the rule that falls in the
    period (instant - DURATION, instant)?"  Thus, the general problem is
    roughly the "is there a start time that falls within this time period.)

    Most aspects of RECUR can be resolved using an amount of processing
    linearly proportional to the textual length of the rule.  However, there
    are three exceptions to this:

    I.   COUNT statements.  It does not appear to be possible to resolve
         these other than by enumerating every instance of an event starting
         from DTSTART, until you satisfy the count.  However, since this can
         be done off-line, and only needs to be done once, consensus was
         that this wasn't a huge problem.  However, some sort of sanity
         bound on COUNT might still be helpful.

    II.  Long DURATIONs.  As I mentioned in my brief summary above, to find
         out if an instant falls within a repetition of a recurrence, you
         need to search for start times in a period of time that is DURATION
         before the instant.  If DURATION is large, then this can be
         inefficient in most algorithms.  (Specifically, it seems to be
         proportional to the duration divided by the smallest time unit
         mentioned; so a three-year DURATION in a YEARLY rule without
         expanding BY*rules is no problem, but a one-week DURATION in a
         SECONDLY rule with complex contracting BY*rules is.)

    III. BYSETPOS.  In order to resolve a BYSETPOS, you (obviously) need to
         have some way of deteriming the set position of an otherwise-valid
         start time.  I have not found any way of doing this other than by
         fully enumerating a set repetition.  (This led to some huge amounts
         of digression about what a set repetition is.)  A sufficiently
         complex rule can have up to 31 million set repetitions, which is
         too many for CPL's requirements.

         This is complicated additionally by the fact that RFC 2445 requires
         that BYSETPOS values be in the range -366 .. 366.  It seems to have
         been the original intention that BYSETPOS would only be used with
         rules discussing periods of a day or more.

    There is not, I believe, any consensus on this point.

    My proposal for this point would be to go with my solution "D" above.
    Specifically, I'd say that calendaring clients SHOULD NOT generate rules
    with long COUNT values, long DURATION values, or BYSETPOS rules that mix
    with sub-day parameters of any sort, unless they know, through some
    out-of-band means, that the calendaring server they are communicating
    with is able and willing to interpret such things.

That's my summary of the current situation.

I will not be at the London IETF.  It'd be good if we could have some
discussion on this list, before that, so as to work out what should be done
about this whole issue.

-- 
Jonathan Lennox
[email-masked]

---

From: "David L. Nicol" <[email-masked]>
Date: Thu, 26 Jul 2001 17:29:36 -0500

Jonathan Lennox wrote:
...
>        theory (though it's not clear how much the problematic constructs are

I hope I'm not alone in thinking that delivering a document with known
weaknesses you are Hoping Will Get Rewritten In A Future Release stinks.

(this also goes for anonymous delegation.)

A possible solution which was not included in Mr. Lennox's list which
comes to my mind would be to exchange a RECUR language for the ability
to link to an event from multiple dates/times/locations, and have the CUA
interpret its own implementation-specific RECUR language and tell the
CS something like

	ALSOON
		August 4, 2001
		September 4, 2001
		October 5, 2001
		January 4, 2002
	.

without the CS needing to make any overall sense of the logic of the dates
listed at all.

At that point, it would make sense to defer fully specifying a RECUR
language
that might get uploaded to the CS to future, since there would be
experience
with these various impl-specif client-side RECUR languages.

in other words,

	CS MUST support list of dates/times/locations
	CS SHOULD support minimal subset of RECUR language
	CS MAY support arbitrary RECUR vendor-extensions
		(with a way for vendors to optionally register them written in.)

-- 
                                           David Nicol 816.235.1187

---

From: "Shannon J. Clark" <[email-masked]>
Date: Thu, 26 Jul 2001 18:22:24 -0500

Since I have in the past spoken up on this issue - a few comments and
thoughts.

One - the concept of a "simple" list of the other occurrences of an event -
while seemingly simple - gets really really ugly fast if you have to deal
with any of the following - events that recur "forever" (the Monday morning
conference call); events that are LOCAL and REOCCURRING - thus the "time" of
each reoccurrence might be dependant on a user's timezone settings (and
further complicated by Daylight savings shifts that result in the possible
case of events "reoccurring" on a non-existent time; Events with a large
reoccurrence set - for a simple example an entry on a calendar intended to
define my "work days" for the year - could be entered easily as an event
that reoccurs from 9-5pm Mon-Fri having a set of exceptions mapped to my
client's holidays - even bound to one year - this event could have a simple
RRULE w/10 Exceptions - or if enumerated will over 200+ dates in a list -
probably increasing the size considerably.

Two - on the related concept of removing RRULES to a degree from RFC2445 - I
think this is a GOOD idea - my suggestion would be to define the RRULES in a
SEPARATE standards track - one that is very much tied to RFC2445 (but no
solely defined therein) - this allows the RRULES to be applied in a clean
fashion to other programs requiring Temporal Reoccurrences (such as
Caches) - without adding the scheduling/meeting infrastructure and overhead
of iCalendar. Furthermore - by increasing the number of applications
utilizing the RRULE syntax - and by involving more applications (like CPL)
that require near-realtime resolution of the RRULEs into a useful form - I
suspect that the development of reference algorithms for efficient and
accuracy expansion (or algorithms for programmatic resolution of questions
of overlap/occurrence - will be sped up and developed more quickly.

Anyway - just my quick thoughts on the subject

Shannon

Shannon J. Clark
CEO - JigZaw, Inc
1.800.4.JIGZAW (454.4929)
[email-masked]
www.jigzaw.com

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of David L. Nicol
Sent: Thursday, July 26, 2001 5:30 PM
To: Jonathan Lennox
Cc: [email-masked]; Graham Gilmore; [email-masked];
[email-masked]; [email-masked]
Subject: Re: Additional RECAP and status of CPL RECUR Issues.

Jonathan Lennox wrote:
...

	ALSOON
		August 4, 2001
		September 4, 2001
		October 5, 2001
		January 4, 2002
	.

in other words,

--
                                           David Nicol 816.235.1187

---

From: "David L. Nicol" <[email-masked]>
Date: Thu, 26 Jul 2001 19:05:25 -0500

> probably increasing the size considerably.

If you are going to be connecting to the CS regularly with the same CUA,
or even with a cron job, you could do the forever thing client-side. 

Disk is cheap.  With a lot of recurrence things happening, they just
get exapnded to static entries anyway, so why not do it all client-side.

> of iCalendar.

Does "cron" have an RFC?

>  Furthermore - by increasing the number of applications

Well said!

---

From: "Shannon J. Clark" <[email-masked]>
Date: Fri, 27 Jul 2001 11:46:52 -0500

Well a few points about doing it all client-side OR via an outside scheduler
(like cron).

1. - this does not resolve how my SERVER should handle incoming events in
the future - i.e. say I expand a "forever" event for the next 100 instances
(or any other arbitrary number) - if my FREEBUSY status is queried (which is
a feature CS can and should - but not must - support) for a time past that
arbitrary number then my server will return incorrect information.
Admittedly this probably is far in the future - and may get corrected after
my rule is expanded - but it changes the order of things in a strange (and
probably confusing to an end user) manner.

2. - many CUA's will NOT have access to tools like cron - sure unix clients
have cron access easily - but such tools are confusing even for
sophisticated users - and do not help CUA cases for mobile devices,
notebooks, etc. Furthermore - if the client application is responsible for
expanding events - and then entering them into a calendar store - there
still is a requirement for a method of DEFINING how to expand events - the
purpose of a set of RRULES is to define a set of ALGORITHMS that can
generate a set of future events - thus avoiding the requirement that a HUMAN
"figure it out"

Even simple cases if required to be entered by hand are cumbersome (imagine
hand entering the future birthdays of all of the people in your address
book - at some point you will make a typo and drop someone's birthday for a
given year...)

Now imagine a case of something that repeats every 25 hours - even given a
small set of reoccurrences this would be obnoxious to generate by hand - and
requires some form of algorithm to define.

My point is that shifting from RRULES on the server - to RRULES on the
client feels like a step backwards. Yes Disk space is "cheap" - BUT this is
not true in all use cases - DISKs can be cheap on a server (but imagine a
server designed to handle 1,000,000+ people) but in cases like mobile
phones, PDAs etc storage can be a severely limiting factor.

Finally not all systems expand recurrences to static entries - indeed came
to this discussion because CPL and other systems were not planning on doing
that - and there are many cases where it doesn't make much sense.

(note on above, in the systems my company is designing we are indeed looking
carefully at this issue - but still plan on having server side knowledge of
the RRULES - even if we do some expansion of them in advance and cache it
for performance)

Shannon

-----Original Message-----
From: [email-masked]
[mailto:[email-masked]]On Behalf Of David L. Nicol
Sent: Thursday, July 26, 2001 7:05 PM
To: Shannon J. Clark
Cc: [email-masked]
Subject: Re: Additional RECAP and status of CPL RECUR Issues.

Does "cron" have an RFC?

Well said!

---

From: "David L. Nicol" <[email-masked]>
Date: Fri, 27 Jul 2001 12:56:20 -0500

> probably confusing to an end user) manner.

If your server supports this extended functionality, that's a good server!

> notebooks, etc.

Tools like cron are very simple to write.  My wristwatch has a tool like
cron: I
can program it to beep at a specified time in the future.

> Furthermore - if the client application is responsible for

The problem is interoperabioty, and complete specification of corner cases.
By delegating solving that problem explicitly outside the scope of the
standard, the interoperability problem goes away. Recurring language is
reclassified to MAY status, and a way to specify which dialect you are
speaking is provided.  The world might wind up with only one dialect,
but it might wind up with many: by delegating the detail the standard
can support any possibility.

> Even simple cases if required to be entered by hand
> [...] shifting from RRULES on the server - to RRULES on the
> client feels like a step backwards.

Shifting functionality from the server to the client does not
mean entering by hand.  The client will still be a complex piece
of software.  Allowing variety in the client means more rocust
competition, to argue from a free-market perspective.

> the RRULES - even if we do some expansion of them in advance and cache it

I'll stand by what I recall my reccomendation here was, which, with
very slight improvement, was:

CS MUST accept multiple dates/times/locations for same event
CS MUST list what RRULES languages it knows in its CAPABILITY responses
CS SHOULD accept a minimal standard RRULES language which is fully defined
CS MAY accept an extended RRULES language, which the definition of
	which is beyond the scope of this document.