=======================
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
