timeline.txt

彩信浏览器

Timelines
=========

*Warning*: this document does not describe the SMIL 2.0 scheduler. It describes
the MMS scheduler, which handles a subset of SMIL 1 (as used by MMS documents).

Introduction
------------

This document gives an overview of what is in a timeline object. It is
loosely based on what the old CMIF scheduler looked like. There are some
simplifications, because I think that some of the extra states and transitions
that the CMIF scheduler had are no longer needed because a timeline is only
supposed to schedule self-contained pieces.

Conceptual design
-----------------

The sample SMIL document that I use to clarify this is the following::

	<seq id="outerseq">
		<par id="innerpar">
			<ref id="parchild1"/>
			<ref id="parchild2"/>
		</par>
		<ref id="seqchild2"/>
	</seq>
	
The *states* that a node goes through are ``IDLE``, ``PREROLLING``, ``PLAYING``,
``PLAYED`` and ``DONE``. We may want an extra state ``PREROLLED``, but I don't think
we need it. The interesting thing seems to be that the states an active timeline
object itself goes
through are the same. ``PLAYED`` and ``DONE`` need a bit of explanation. A node
goes from ``PLAYING`` to ``PLAYED`` when its implicit or explicit duration is over,
but its freeze duration not. I.e. the thing is logically finished, but you
can still see it. It goes from ``PLAYED`` to ``DONE`` (or directly from ``PLAYING`` to
``DONE``) when its parent decides to stop it playing.

These states give rise to *state-transitions*, and those are what we are
actually interested in. These are the things
that are often called "events" in other such designs, but I think we are
already overusing that term as-is. 

Here is what the timeline for the section above looks like conceptually. 
The semantics used here are that we wait for the state transitions on the
lefthandside of the colon to happen, and as soon as they have happened
we fire the state transitions on the righthandside. If there is more than one
transition on the LHS we use either the ``&&`` operator to wait for all
of them or ``||`` to wait for the first one::

	START_PREROLL_TIMELINE:
		START_PREROLL(outerseq)
	START_PLAY_TIMELINE:
		START_PLAY(outerseq)
	DONE_PLAY_TIMELINE:
		
	START_PREROLL(outerseq):
		START_PREROLL(innerpar)
	START_PLAY(outerseq):
		START_PLAY(innerpar)
	DONE_PLAY(outerseq):
		DONE_PLAY_TIMELINE
				
	START_PREROLL(innerpar):
		START_PREROLL(parchild1),
		START_PREROLL(parchild2)
	START_PLAY(innerpar): 
		START_PLAY(parchild1), 
		START_PLAY(parchild2),
		START_PREROLL(seqchild2)
	DONE_PLAY(parchild1) && DONE_PLAY(parchild2):
		DONE_PLAY(innerpar)
	DONE_PLAY(innerpar):
		STOP_PLAY(parchild1),
		STOP_PLAY(parchild2),
		START_PLAY(seqchild2)
		
	START_PREROLL(parchild1):
		START_PREROLL_RENDERER(parchild1)
	START_PLAY(parchild1):
		START_PLAY_RENDERER(parchild1)
	STOP_PLAY(parchild1):
		STOP_PLAY_RENDERER(parchild1),
		
	START_PREROLL(parchild2):
		START_PREROLL_RENDERER(parchild2)
	START_PLAY(parchild2):
		START_PLAY_RENDERER(parchild2)
	STOP_PLAY(parchild2):
		STOP_PLAY_RENDERER(parchild2),
	
	START_PREROLL(seqchild2):
		START_PREROLL_RENDERER(seqchild2)
	START_PLAY(seqchild2):
		START_PLAY_RENDERER(seqchild2)
	DONE_PLAY(seqchild2):
		STOP_PLAY_RENDERER(seqchild2),
		DONE_PLAY(outerseq)
		
The ``xxx_TIMELINE`` state-transitions are the communication between this timeline
and the highlevel scheduler: the ``START_PREROLL_TIMELINE`` and ``START_PLAY_TIMELINE``
are injected form above to get the ball rolling, the ``DONE_PLAY_TIMELINE`` is
sent back up to notify that the timeline has finished.

The ``START_PREROLL_RENDERER(xx)``, ``START_PLAY_RENDERER(xx)`` and ``STOP_PLAY_RENDERER(xx)`` are 
"side-effect-only"
transitions: the timeline doesn't use these on the lefthandside, their only effect
is to kick renderers and other objects into motion. The ``DONE_PLAY_RENDERER(xx)`` is the
reverse: for media nodes these are generated by the renderer.

There is one more bit of functionality: timed events. For each delay needed a delayer
object is instantiated (with the delay time as parameter). This object appears on a 
righthandside rule as ``DELAY(delayobj)``, at which point the timer starts. When the timer
finishes the event ``DELAY(delayobj)`` fires on the lefthandside.

Design issues still to be handled
---------------------------------

A bit that is still incomplete is region control. The ``passive_region`` is implied
by the node, and ``START_PREROLL_RENDERER``  creates the corresponding ``active_region``
that does the rendering. Implications of (SMIL-) transitions and fill behaviour
are still TBD.

Anchors aren't mentioned explicitly, but I think they can be handled analogous
to normal media nodes. In other words: we treat an anchor simply as another kind
of media node, and the only special thing we do is that we don't send it to a
normal renderer but to an "anchor renderer". This makes media nodes behave
similarly as parallel interior nodes, but I don't think the design here has any problems
with that.

Clocks aren't mentioned yet. It could be that they are implicit (i.e. the renderer
picks up the clock to use from the node), but I think they probably need to be
explicit. This would mean that the ``DELAY`` and all the ``xxx_RENDERER`` state transitions 
get a clock parameter.

Objects
-------

The three main objects are ``timeline_builder``, ``passive_timeline`` 
and ``active_timeline``.

``timeline_builder`` is a temporary object you use to build a ``passive_timeline``
from part of a SMIL tree. The current implementation is very simple-minded, and
handles only documents that adhere to the 3GPP MMS 2.0 specification. This basically
means fixed layout with one text and one image region, and a fixed structure
of a sequence of ``<par>`` nodes containing each at most one ``<text>``, one ``<image>``
and one ``<audio>``.  

``Timeline_builder`` currently also creates the ``passive_region``
hierarchy, and is therefore called with the ``window_factory`` object as argument.
This is a temporary situation: the region hierarchy is document-wide and hence
longer lived that timeline objects.

The timeline builder class is declared in ``lib/timeline_builder.h``.

``passive_timeline`` objects first go through a building stage, during which the
timeline builder adds the nodes, adds the delays, and adds the transitions to the nodes.
These are all stored in ``timeline_node``, ``timeline_delay``, ``timeline_node_transitions``,
``timeline_event`` and ``timeline_rhs_event`` objects.

Once these datastructures are complete the builder calls the ``build()`` method
on the passive timeline. This converts the information in the datastructures above
to the form of two arrays, one of ``active_action`` objects and one of ``active_dependency``
objects. An ``active_action`` stores a single RHS of a timeline node transition, and
it has various subclasses to cater for the different actions. Active actions for each
node transition are stored contiguously. An ``active_dependency`` stores the whole
LHS of a timeline node transition, but only in the form of a dependency count and
begin/end pointers into the ``active_action`` array. After calling ``build()`` the
passive timeline is immutable.

The ``active_action`` objects store internal events (the events without side effects)
as indices into the ``active_dependency`` array. It uses an interior object
``dependency_index_generator`` to create and store this mapping.

	Timelines could be optimized pretty aggressively: for any state transition in the RHS
	of a rule that occurs alone in the LHS of another rule we can simply replace
	it's occurrence in the RHS with its own expansion. This does not happen yet in the current implementation.

Calling ``activate()`` on a ``passive_timeline`` will return a new active timeline 
object which can execute the
timeline graph. The ``active_dependency`` array is copied to the active timeline,
as its dependency counts will be updated during execution, but the ``active_action``
array is immutable and hence not copied, multiple ``active_timeline`` objects can
share the copy in the ``passive_timeline``.

Active timelines have ``preroll()`` and ``start()`` methods, similar to nodes.
It is possible to activate and preroll a timeline without any visible effect,
hence this can be used to do branch prediction on hyperlinks, etc.

Handling of internal events is straightforward, their ``fire()`` method is called
which schedules a new dependency. Handling of events with side-effects is a bit
more elaborate: the ``fire()`` method schedules a low-priority callback to 
``ext_dependency_callback()`` which calls the actual external method to do the work.
This roundabout way ensures that all internal events scheduled for a certain point in
time are processed before all external events, which should make the system
snappier.