======================= Time-awareness in VOS ======================= :author: Lalo Martins :date: 2006-12-01 :status: braindump :abstract: Thoughts and designs on time-aware VOS vObjects
.. For those not familiar with the concept, “braindump” is an early stage of discussion, a writeup that doesn't even deserve to be called a “draft” yet. Many applications that either have already been tried in VOS or that we'd like to have in the future are time-sensitive. The most obvious case here is animation, which typically “travels” an object trough “keyframes” across a timeline. However, another application — and one with ample experience and research we can use — is revision control. While some might argue that revision control, as applied to source code, might be out of the scope of VOS, the kind of revision control commonly found in wikis does fit in our current scope. Peter and I were chatting about this on IRC, and he thinks it might be useful to have time awareness built in to s5, rather than a layer on top of it. (I agree, of course, or I wouldn't be spending time writing this; when I say it was his idea, I only mean to give due credit.) One last important point is that the two applications we're using to draw use cases from aren't mutually exclusive; an animation may be revision controlled. So the time functionality in s5 needs to be orthogonal, or multi-dimensional. Terminology and concepts ======================== The basic unit that is time-aware in our proposed model is the **vObject**. A vObject **state** is what we call each individual point in a timeline. Equivalent terminology is a “keyframe” or “frame” in animation, and a “revision” or “snapshot” in revision control. Every state has an “UID”, a string identifier that's unique within that vObject. (It's not guaranteed unique globally or even within the site, as we may want the ability to “snapshot” multiple objects in a single “meta-state”, and it may be convenient to have all resulting states share the same UID.) It would be useful if an individual state could have arbitrary metadata, such as a message, author id, UIDs of “merged” states, or a signature. I won't approach this point in this stage of the design, but I imagine the most convenient way to achieve that would be to be able to refer to the state itself as a vObject, or maybe optionally create a vObject that represents the state metadata. A reference (handle in s5) to a vObject actually refers to one specific state of that object in a specific timeline (see below). It's still an open question whether this will extend to parent-child relationships. There is one state for each object which is called the **“current state”**. If parent-child relationships are not time-aware, then this is the state you'll get by default when you follow one. If PCRs are time-aware, then the “current state” will be stored in the PCR between the object and its site. For the whole system to work, we need built-in time objects. Two objects are at the core of the design: the **timestamp** represents a given point in *absolute* (real-world) time, and is available for use by other applications; it would have properties and methods similar to other such objects, such as Python's datetime or ECMAScript's Date. Being *absolute* time, they need to be timezone-aware; we'll do that in a system similar to Python's datetime, by having an optional property **timezone**, which is expected to be a timezone object. The mandatory API for timezone implementations is very simple: they provide two methods, ``toUTC`` and ``fromUTC``. Each one takes a timestamp object, and returns another; I hope the semantics are obvious. Different from Python's datetime, however, a timestamp with no timezone object is *not* assumed to be timezone-unaware; rather, it's assumed to be expressed in UTC. Or, in other words, the null timezone object is the UTC timezone. Internally, the time-awareness APIs discussed in this document will use UTC exclusively, and for this reason, it's likely that s5 won't include any timezone objects off the proverbial shelf. The other core object, and one that will actually be used more frequently, is the **timespan**. It represents nothing more than a given length of time, presumably expressed in seconds. You can add and subtract timespans from timestamps, and you get another timestamp. You can also subtract one timestamp from another and get a timespan. A **timeline** is what we call a sequence of states. It corresponds to a branch in revision control terminology, or to an individual animation in a multi-animation object (such as a 3d character). Timelines have “names”, which must be unique within a vObject and dimension (see later); the semantics of timeline names will be intentionally left open to the application, as for each application, it may be more meaningful to have automatically generated names, or names based on some computed information (originating user and timestamp for revision control), or human-readable names. Every timeline has a **“state zero”**, where the UID is the empty string, and the object is completely empty (newly created vObject, with the default types). It also has an optional timestamp attribute, the **“start timestamp”**; if this timeline is anchored in absolute time (as is the case for a revision control timeline, but not for animation), then this is the moment the timeline was “created”, in which the corresponding state is the state zero. In non-absolute timelines, this will be null, and state timespans will be relative to arbitrary time. Similar to the concept of a “current state”, each vObject has a **“current timeline”** for each dimension in which it has timelines. Also like states, it would also be useful to be able to assign arbitrary properties to timelines, such as the bzr concept of a “branch nick”, or the URI of remote timelines to sync with. In the context of a given timeline, each state has an additional attribute, specifying its temporal position in the timeline. In actual implementation, this may be stored either as a timespan from the start timestamp, or from the previous state, or even both; either way, there will be functions in the API to retrieve both values. (It could be implemented by storing state references in an ordered map, like std::map, with timespans as keys.) Note that (inspired by bzr) timelines don't record relationships to each other. If timeline 1 has states (0, A, B, C, D), and you create timeline 2 by “branching off” state 1B, then add states (E, F) to it, then 2 will be (0, A, B, E, F). Branch relationship is calculated at runtime, by looking for the latest common state, in this case B. Revision control operations such as “pull” and “merge” would operate only on the differences after this point. The final concept is a “dimension”. This is just a string identifier that puts timelines in context, such as “a3dl:animation” or “revcontrol:branch”. If a vObject doesn't have any “history” in a given dimension, then it's still meaningful to try to get its current timeline; this will result in an **“implicit timeline”** — one that is created at runtime (not stored in persistence), has the empty string for its name, and is read-only (you can't rename it or add states from it, but you can copy it into a new, “normal” timeline). Apart from all that, but also important, is a **time transform**. Similar to transforms in 2d and 3d graphics programming, these can be applied to a timeline, to make it run faster, slower, with a delay, etc. Possible APIs ============= Dimensions will be represented by VOS strings. Timespans may be an opaque object, if we want it to have any methods, or just a numeric value. Timestamps and timelines will all be new classes in the C++ and Python APIs (and something equivalent in other languages). States aren't explicitly represented in any way; “getting a state” actually refers to getting a handle to the vObject in that state. The syntax used below is pseudo-C++; I'll leave out ``const`` and other useful details to implementation time, and I'll skip important details like vRef and pointers for brevity. Getting time information from a vObject --------------------------------------- ``VOS::String vObject::stateID()`` returns the UID of the state this reference points to. ``vObject vObject::currentState()`` returns the global “current state” of this vObject. ``Timeline vObject::currentTimeline(VOS::String dimension)`` returns the current timeline for this object in that dimension. ``TimelineIterator vObject::getTimelines(VOS::String dimension)`` returns all timelines for this object in that dimension; ``TimelineIterator`` is a STL-style iterator. *(Or should it return a std::map keyed by name?)* ``VOS::String Timeline::getName()`` returns a timeline name, of course. ``void Site::registerTimeDimension(VOS::String dimension)`` registers a new time dimension (duh). ``VOS::StringIterator Site::getTimeDimensions()`` gives you all registered time dimensions (probably not useful except for reflection and debugging). Should ``registerTimeDimension`` fail if you register an already registered dimension, or accept it silently? Should there be a method to check if one is already registered? Time travel ----------- ``vObject Timeline::getState(VOS::String uid)`` and ``vObject Timeline::getState(long ordinal)`` return a state in this timeline, or throw a lookup error. ``vObject Timeline::getStateAt(Timestamp when, TimeTransform transform=NULL)`` and ``vObject Timeline::getStateAt(Timespan offsetFromStart, TimeTransform transform=NULL)`` return the state that was “active” at that point of time, or throw a lookup error if that's before start. Optional ``transform`` is applied to the time from the start, if given. ``long Timeline::getIndex(VOS::String uid)`` returns the ordinal index of the state UID in this timeline, or throws a lookup error. This could be used, for example, to start an animation from “halfway”, or find the next or previous state from a known one. ``long Timeline::getIndexAt(Timestamp when, TimeTransform transform=NULL)`` and ``long Timeline::getIndexAt(Timespan offsetFromStart, TimeTransform transform=NULL)`` return the ordinal index of the state that was “active” at that point of time, or throw a lookup error if that's before start. Optional ``transform`` is applied to the time from the start, if given. ``void vObject::syncState(vObject other)`` changes this object to point to the same state as ``other`` (or more precisely, the state with the same UID). This is where it might be useful to allow different objects to reuse the same UID for states. The point of this function is that, since s5 references are actually handles, all other references everywhere will now “see” the new state, including remote ones. It will throw a lookup error if there's no state with that UID. Timeline manipulation --------------------- ``vObject Timeline::saveState(Timespan timeFromStart)`` saves (“commits”) a new state, and returns a reference with that state. ``vObject Timeline::saveState(Timestamp absTime=NULL)`` saves (“commits”) a new state, and returns a reference with that state. This version requires the timeline to be rooted in absolute time; if the absTime argument is NULL, then it's set to the current time. ``vObject Timeline::addState(vObject other, Timespan timeFromStart)`` is used to copy a state from another timeline. *Time-exploding note: due to the way timelines work, there's no reason for the underlying vObject to be the same. Any two timelines have a common ancestor, the state zero; so you may store a state of object A that is actually a complete copy of object B, maybe even of a different type, and nothing should break. Neat uh?* ``vObject Timeline::addState(vObject other, Timestamp absTime=NULL)`` should be pretty obvious from the functions above. ``void Timeline::rename(VOS::String name)`` changes a timeline name. ``Timeline::Timeline(const Timeline &other, VOS::String name=NULL, vObject object=NULL)`` constructs a new timeline that is an exact copy of ``other``. *Not passing in a name — necessary to use this as a copy constructor — will require mangling the new name somehow, maybe appending an incremental number to the end.* If the optional ``object`` is given, it's used as a “branch point”; that is, the new timeline is an exact copy of ``other``, but only up to the state ``object`` points to. ``Timeline::Timeline(vObject object, VOS::String dimension, VOS::String name)`` constructs a new timeline for ``object``, by copying the current timeline for that object and dimension. It actually corresponds to ``Timeline(object->currentTimeline(dimension), name, object)``. best, Lalo Martins -- So many of our dreams at first seem impossible, then they seem improbable, and then, when we summon the will, they soon become inevitable. -- personal: http://www.laranja.org/ technical: http://lalo.revisioncontrol.net/ GNU: never give up freedom http://www.gnu.org/ _______________________________________________ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d