Mozart: Improve internal scene graph representation.

Mozart: Improve internal scene graph representation.

This patch changes the internal scene graph representation into an
immutable data structure which allows for multiple versions to be
maintained simultaneously as well as for the node structure to be
preserved during snapshot operations.

Previously the node structure was traversed once during snapshot
with the intent that all relevant information would be recorded
info an immutable |RenderFrame| object for rasterization and for
hit testing.  However it proved prohibitively expensive to copy
the necessary node structure information into the |RenderFrame|
for hit testing.  So this change does away with all of that.

The compositor now keeps three levels of structural information
to be generated and traversed as required.

1. |SceneDef| which holds a table of immutable |NodeDef| objects
   describing the currently presented state of the scene graph
   and pending updates which have yet to be applied.

2. |SceneContent| which is generated from a |SceneDef| when the
   scene graph is presented.  It consists of an immutable index
   of |NodeDef| objects for a particular version of the scene
   graph as it existed at the time of presentation.  This index
   contains sufficient linkage information to ensure that the
   scene does not contain any internal cross-node cycles and
   that all references resources and nodes are reachable.

3. |Snapshot| which is generated from a collection of |SceneContent|
   objects when the frame is snapshotted.  When producing the
   snapshot, all scene references are resolved and combinator
   rules are evaluated to produce a final description of a single
   frame of graphical content to be rasterized.  The |Snapshot|
   can also be traversed later for hit testing purposes since
   it retains a record of the disposition of each node (whether
   they were blocked).

Altogether, these new representations resolve numerous issues with
the old model such as how we can retain multiple versions of a
scene for as long as required or how we can traverse particular
versions or snapshots of the scene graph to execute queries such
as hit testing.

There are still many optimizations we could apply to the structure
but it's already looking much better overall and there is
significantly less wasted effort during snapshotting when blocked
nodes are discovered.

This also puts us in a nice position to start dealing with
synchronization issues such as applications which publish scenes
referencing textures which have yet to be produced: while walking
the tree we can make a decision of whether to wait or to fallback
on previously published content which may be already be ready with
per-scene granularity.  (To do later.)

(Hit testing itself will be implemented in a later patch.)

BUG=
R=abarth@google.com

Committed: https://chromium.googlesource.com/external/mojo/+/33eb773f692f9df5cf08d3bdc1e9e4569dfd1c67

[jeffbrown, 2016-03-01 08:11:19]

jeffbrown@google.com changed reviewers:
+ abarth@google.com

[jeffbrown, 2016-03-01 08:11:20]

This isn't fully tested yet since I can't run it over remote desktop.  I may try
to write some apptests before submitting so that I can exercise the cycle
detection and fallback logic more thoroughly.

[abarth, 2016-03-01 17:21:26]

LGTM

The cycle detection logic looks tricky and I didn't try to verify it.  It might
be a good subject for unit testing.

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/node_def.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/node_def.cc:218: content, snapshot, [=](const
NodeDef* child_node) -> bool {
Is `[=]` permitted by the style guide?

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/scene_content.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/scene_content.cc:67: return it->second.get();  //
found
I'd skip this comment.  It's a common pattern for finding things in a map.

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/scene_content.cc:124:
content_->nodes_[node->node_id()] = node;
There's a pattern for doing this without doing two hash lookups.  It looks like
emplace returns an iterator, which you can hold in a local and then use to set
the slot in the map.

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/snapshot.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/snapshot.cc:99:
snapshot_->node_dispositions_[node] = Snapshot::Disposition::kCycle;
There's also a pattern for doing this with one hash lookup.  I think "insert"
will give you back an iterator and a bool about whether it's a newly inserted
node or a pre-existing node.

[jeffbrown, 2016-03-02 00:32:16]

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/node_def.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/node_def.cc:218: content, snapshot, [=](const
NodeDef* child_node) -> bool {
On 2016/03/01 17:21:26, abarth wrote:
> Is `[=]` permitted by the style guide?

Huh, apparently not.  *sigh*

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/scene_content.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/scene_content.cc:67: return it->second.get();  //
found
On 2016/03/01 17:21:26, abarth wrote:
> I'd skip this comment.  It's a common pattern for finding things in a map.

Done.

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/scene_content.cc:124:
content_->nodes_[node->node_id()] = node;
On 2016/03/01 17:21:26, abarth wrote:
> There's a pattern for doing this without doing two hash lookups.  It looks
like
> emplace returns an iterator, which you can hold in a local and then use to set
> the slot in the map.

You're correct that we can do this but the reasons are subtle.  Note that
|RecordContent| may recurse into |AddNode| to add more nodes.  Ordinarily we
might worry about the iterator being invalidated but we took care to size the
map at creation time to avoid any rehashing, so it's ok.

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
File services/gfx/compositor/graph/snapshot.cc (right):

https://codereview.chromium.org/1749063002/diff/20001/services/gfx/compositor...
services/gfx/compositor/graph/snapshot.cc:99:
snapshot_->node_dispositions_[node] = Snapshot::Disposition::kCycle;
On 2016/03/01 17:21:26, abarth wrote:
> There's also a pattern for doing this with one hash lookup.  I think "insert"
> will give you back an iterator and a bool about whether it's a newly inserted
> node or a pre-existing node.

True.  Note that here rehashing may occur after the call to RecordSnapshot so we
will still need to perform 2 hash lookups, but at least it's not 3.

[jeffbrown, 2016-03-02 19:17:35]

Description was changed from

==========
Mozart: Improve internal scene graph representation.

This patch changes the internal scene graph representation into an
immutable data structure which allows for multiple versions to be
maintained simultaneously as well as for the node structure to be
preserved during snapshot operations.

Previously the node structure was traversed once during snapshot
with the intent that all relevant information would be recorded
info an immutable |RenderFrame| object for rasterization and for
hit testing.  However it proved prohibitively expensive to copy
the necessary node structure information into the |RenderFrame|
for hit testing.  So this change does away with all of that.

The compositor now keeps three levels of structural information
to be generated and traversed as required.

1. |SceneDef| which holds a table of immutable |NodeDef| objects
   describing the currently presented state of the scene graph
   and pending updates which have yet to be applied.

2. |SceneContent| which is generated from a |SceneDef| when the
   scene graph is presented.  It consists of an immutable index
   of |NodeDef| objects for a particular version of the scene
   graph as it existed at the time of presentation.  This index
   contains sufficient linkage information to ensure that the
   scene does not contain any internal cross-node cycles and
   that all references resources and nodes are reachable.

3. |Snapshot| which is generated from a collection of |SceneContent|
   objects when the frame is snapshotted.  When producing the
   snapshot, all scene references are resolved and combinator
   rules are evaluated to produce a final description of a single
   frame of graphical content to be rasterized.  The |Snapshot|
   can also be traversed later for hit testing purposes since
   it retains a record of the disposition of each node (whether
   they were blocked).

Altogether, these new representations resolve numerous issues with
the old model such as how we can retain multiple versions of a
scene for as long as required or how we can traverse particular
versions or snapshots of the scene graph to execute queries such
as hit testing.

There are still many optimizations we could apply to the structure
but it's already looking much better overall and there is
significantly less wasted effort during snapshotting when blocked
nodes are discovered.

This also puts us in a nice position to start dealing with
synchronization issues such as applications which publish scenes
referencing textures which have yet to be produced: while walking
the tree we can make a decision of whether to wait or to fallback
on previously published content which may be already be ready with
per-scene granularity.  (To do later.)

(Hit testing itself will be implemented in a later patch.)

BUG=
==========

to

==========
Mozart: Improve internal scene graph representation.

This patch changes the internal scene graph representation into an
immutable data structure which allows for multiple versions to be
maintained simultaneously as well as for the node structure to be
preserved during snapshot operations.

Previously the node structure was traversed once during snapshot
with the intent that all relevant information would be recorded
info an immutable |RenderFrame| object for rasterization and for
hit testing.  However it proved prohibitively expensive to copy
the necessary node structure information into the |RenderFrame|
for hit testing.  So this change does away with all of that.

The compositor now keeps three levels of structural information
to be generated and traversed as required.

1. |SceneDef| which holds a table of immutable |NodeDef| objects
   describing the currently presented state of the scene graph
   and pending updates which have yet to be applied.

2. |SceneContent| which is generated from a |SceneDef| when the
   scene graph is presented.  It consists of an immutable index
   of |NodeDef| objects for a particular version of the scene
   graph as it existed at the time of presentation.  This index
   contains sufficient linkage information to ensure that the
   scene does not contain any internal cross-node cycles and
   that all references resources and nodes are reachable.

3. |Snapshot| which is generated from a collection of |SceneContent|
   objects when the frame is snapshotted.  When producing the
   snapshot, all scene references are resolved and combinator
   rules are evaluated to produce a final description of a single
   frame of graphical content to be rasterized.  The |Snapshot|
   can also be traversed later for hit testing purposes since
   it retains a record of the disposition of each node (whether
   they were blocked).

Altogether, these new representations resolve numerous issues with
the old model such as how we can retain multiple versions of a
scene for as long as required or how we can traverse particular
versions or snapshots of the scene graph to execute queries such
as hit testing.

There are still many optimizations we could apply to the structure
but it's already looking much better overall and there is
significantly less wasted effort during snapshotting when blocked
nodes are discovered.

This also puts us in a nice position to start dealing with
synchronization issues such as applications which publish scenes
referencing textures which have yet to be produced: while walking
the tree we can make a decision of whether to wait or to fallback
on previously published content which may be already be ready with
per-scene granularity.  (To do later.)

(Hit testing itself will be implemented in a later patch.)

BUG=
R=abarth@google.com

Committed:
https://chromium.googlesource.com/external/mojo/+/33eb773f692f9df5cf08d3bdc1e...
==========

[jeffbrown, 2016-03-02 19:17:36]

Committed patchset #3 (id:40001) manually as
33eb773f692f9df5cf08d3bdc1e9e4569dfd1c67 (presubmit successful).