[gtk/wip/alexl/broadway7: 4/16] broadway: Initial restructuring of node tree diffing
- From: Alexander Larsson <alexl src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/wip/alexl/broadway7: 4/16] broadway: Initial restructuring of node tree diffing
- Date: Fri, 29 Mar 2019 12:41:25 +0000 (UTC)
commit 8a155bb35a09d96e38d3570fc9026e2a3193fa53
Author: Alexander Larsson <alexl redhat com>
Date: Thu Mar 28 16:03:42 2019 +0100
broadway: Initial restructuring of node tree diffing
This goes back to a very naive diff, but that reuses nodes from
previous frames using the node id. This will be a bettter base
to start from.
gdk/broadway/broadway-output.c | 106 +++++++++++++++---------
gdk/broadway/broadway-output.h | 3 +-
gdk/broadway/broadway-protocol.h | 15 ++--
gdk/broadway/broadway-server.c | 46 +++++++----
gdk/broadway/broadway-server.h | 8 ++
gdk/broadway/broadway.js | 169 +++++++++++++++++++++------------------
6 files changed, 211 insertions(+), 136 deletions(-)
---
diff --git a/gdk/broadway/broadway-output.c b/gdk/broadway/broadway-output.c
index 6ee3229933..479a7a48da 100644
--- a/gdk/broadway/broadway-output.c
+++ b/gdk/broadway/broadway-output.c
@@ -326,6 +326,16 @@ append_type (BroadwayOutput *output, guint32 type, BroadwayNode *node)
append_uint32 (output, type);
}
+static BroadwayNode *
+lookup_old_node (GHashTable *old_node_lookup,
+ guint32 id)
+{
+ if (old_node_lookup)
+ return g_hash_table_lookup (old_node_lookup, GINT_TO_POINTER (id));
+
+ return NULL;
+}
+
/***********************************
* This outputs the tree to the client, while at the same time diffing
@@ -347,59 +357,83 @@ append_type (BroadwayOutput *output, guint32 type, BroadwayNode *node)
static void
append_node (BroadwayOutput *output,
BroadwayNode *node,
- BroadwayNode *old_node,
- gboolean all_parents_are_kept)
+ GHashTable *old_node_lookup)
{
guint32 i;
+ BroadwayNode *reused_node;
append_node_depth++;
- if (old_node != NULL && broadway_node_equal (node, old_node))
+ reused_node = lookup_old_node (old_node_lookup, node->id);
+ if (reused_node)
{
- if (broadway_node_deep_equal (node, old_node))
- {
- append_type (output, BROADWAY_NODE_KEEP_ALL, node);
- goto out;
- }
-
- if (all_parents_are_kept)
- {
- append_type (output, BROADWAY_NODE_KEEP_THIS, node);
- append_uint32 (output, node->n_children);
- for (i = 0; i < node->n_children; i++)
- append_node (output, node->children[i],
- i < old_node->n_children ? old_node->children[i] : NULL,
- TRUE);
-
- goto out;
- }
+ append_type (output, BROADWAY_NODE_REUSE, node);
+ append_uint32 (output, node->id);
+ }
+ else
+ {
+ append_type (output, node->type, node);
+ append_uint32 (output, node->id);
+ for (i = 0; i < node->n_data; i++)
+ append_uint32 (output, node->data[i]);
+ for (i = 0; i < node->n_children; i++)
+ append_node (output,
+ node->children[i],
+ old_node_lookup);
}
- append_type (output, node->type, node);
- for (i = 0; i < node->n_data; i++)
- append_uint32 (output, node->data[i]);
- for (i = 0; i < node->n_children; i++)
- append_node (output,
- node->children[i],
- (old_node != NULL && i < old_node->n_children) ? old_node->children[i] : NULL,
- FALSE);
-
- out:
append_node_depth--;
}
+
+static void
+append_node_ops (BroadwayOutput *output,
+ BroadwayNode *node,
+ BroadwayNode *old_node,
+ GHashTable *old_node_lookup)
+{
+ GPtrArray *to_remove = g_ptr_array_new ();
+ guint32 i;
+
+ if (old_node != NULL)
+ g_ptr_array_add (to_remove, old_node);
+
+ append_uint32 (output, BROADWAY_NODE_OP_APPEND_NODE);
+ append_uint32 (output, 0); /* Parent */
+
+ append_node(output, node, old_node_lookup);
+
+ for (i = 0; i < to_remove->len; i++)
+ {
+ BroadwayNode *removed_node = g_ptr_array_index (to_remove, i);
+ if (!removed_node->used)
+ {
+ // TODO: Use an array of nodes instead
+ append_uint32 (output, BROADWAY_NODE_OP_REMOVE_NODE);
+ append_uint32 (output, old_node->id);
+ }
+ }
+ g_ptr_array_unref (to_remove);
+}
+
+
void
broadway_output_surface_set_nodes (BroadwayOutput *output,
int id,
BroadwayNode *root,
- BroadwayNode *old_root)
+ BroadwayNode *old_root,
+ GHashTable *old_node_lookup)
{
gsize size_pos, start, end;
- /* Early return if nothing changed */
- if (old_root != NULL &&
- broadway_node_deep_equal (root, old_root))
- return;
+ /* Mark old nodes as unused, so we can use them once */
+ if (old_root)
+ broadway_node_mark_deep_used (old_root, FALSE);
+ /* Mark new nodes as used, causing any shared nodes to be marked as
+ unused. This way we won't accidentally reuse them for something
+ else. However, this means that is safe to reuse nodes marked as
+ used for the specific case of where the id matches. */
+ broadway_node_mark_deep_used (root, TRUE);
write_header (output, BROADWAY_OP_SET_NODES);
@@ -412,7 +446,7 @@ broadway_output_surface_set_nodes (BroadwayOutput *output,
#ifdef DEBUG_NODE_SENDING
g_print ("====== node tree for %d =======\n", id);
#endif
- append_node (output, root, old_root, TRUE);
+ append_node_ops (output, root, old_root, old_node_lookup);
end = output->buf->len;
patch_uint32 (output, (end - start) / 4, size_pos);
}
diff --git a/gdk/broadway/broadway-output.h b/gdk/broadway/broadway-output.h
index 7270f188cc..036aa05c37 100644
--- a/gdk/broadway/broadway-output.h
+++ b/gdk/broadway/broadway-output.h
@@ -60,7 +60,8 @@ void broadway_output_set_transient_for (BroadwayOutput *output,
void broadway_output_surface_set_nodes (BroadwayOutput *output,
int id,
BroadwayNode *root,
- BroadwayNode *old_root);
+ BroadwayNode *old_root,
+ GHashTable *old_node_lookup);
void broadway_output_upload_texture (BroadwayOutput *output,
guint32 id,
GBytes *texture);
diff --git a/gdk/broadway/broadway-protocol.h b/gdk/broadway/broadway-protocol.h
index a78d09080f..1ea5ff9766 100644
--- a/gdk/broadway/broadway-protocol.h
+++ b/gdk/broadway/broadway-protocol.h
@@ -20,13 +20,16 @@ typedef enum { /* Sync changes with broadway.js */
BROADWAY_NODE_SHADOW = 8,
BROADWAY_NODE_OPACITY = 9,
BROADWAY_NODE_CLIP = 10,
- BROADWAY_NODE_KEEP_ALL = 11,
- BROADWAY_NODE_KEEP_THIS = 12,
- BROADWAY_NODE_TRANSFORM = 13,
- BROADWAY_NODE_DEBUG = 14,
- BROADWAY_NODE_REUSE = 15,
+ BROADWAY_NODE_TRANSFORM = 11,
+ BROADWAY_NODE_DEBUG = 12,
+ BROADWAY_NODE_REUSE = 13,
} BroadwayNodeType;
+typedef enum { /* Sync changes with broadway.js */
+ BROADWAY_NODE_OP_APPEND_NODE = 0,
+ BROADWAY_NODE_OP_REMOVE_NODE = 1,
+} BroadwayNodeOpType;
+
static const char *broadway_node_type_names[] G_GNUC_UNUSED = {
"TEXTURE",
"CONTAINER",
@@ -39,8 +42,6 @@ static const char *broadway_node_type_names[] G_GNUC_UNUSED = {
"SHADOW",
"OPACITY",
"CLIP",
- "KEEP_ALL",
- "KEEP_THIS",
"TRANSFORM",
"DEBUG",
"REUSE",
diff --git a/gdk/broadway/broadway-server.c b/gdk/broadway/broadway-server.c
index 70a236ef46..0d789a660d 100644
--- a/gdk/broadway/broadway-server.c
+++ b/gdk/broadway/broadway-server.c
@@ -183,6 +183,10 @@ broadway_node_equal (BroadwayNode *a,
{
int i;
+ // Early fast return for reused nodes
+ if (a == b)
+ return TRUE;
+
if (a->type != b->type)
return FALSE;
@@ -207,6 +211,10 @@ broadway_node_deep_equal (BroadwayNode *a,
{
int i;
+ // Early fast return for reused nodes
+ if (a == b)
+ return TRUE;
+
if (a->hash != b->hash)
return FALSE;
@@ -224,6 +232,24 @@ broadway_node_deep_equal (BroadwayNode *a,
}
+void
+broadway_node_mark_deep_used (BroadwayNode *node,
+ gboolean used)
+{
+ node->used = used;
+ for (int i = 0; i < node->n_children; i++)
+ broadway_node_mark_deep_used (node->children[i], used);
+}
+
+void
+broadway_node_add_to_lookup (BroadwayNode *node,
+ GHashTable *node_lookup)
+{
+ g_hash_table_insert (node_lookup, GINT_TO_POINTER(node->id), node);
+ for (int i = 0; i < node->n_children; i++)
+ broadway_node_add_to_lookup (node->children[i], node_lookup);
+}
+
static void
broadway_server_init (BroadwayServer *server)
{
@@ -1784,17 +1810,6 @@ decode_nodes (BroadwayServer *server,
return node;
}
-static void
-init_node_lookup (BroadwaySurface *surface,
- BroadwayNode *node)
-{
- int i;
-
- g_hash_table_insert (surface->node_lookup, GINT_TO_POINTER(node->id), node);
- for (i = 0; i < node->n_children; i++)
- init_node_lookup (surface, node->children[i]);
-}
-
/* passes ownership of nodes */
void
broadway_server_surface_update_nodes (BroadwayServer *server,
@@ -1816,7 +1831,8 @@ broadway_server_surface_update_nodes (BroadwayServer *server,
if (server->output != NULL)
broadway_output_surface_set_nodes (server->output, surface->id,
root,
- surface->nodes);
+ surface->nodes,
+ surface->node_lookup);
if (surface->nodes)
broadway_node_unref (server, surface->nodes);
@@ -1824,8 +1840,7 @@ broadway_server_surface_update_nodes (BroadwayServer *server,
surface->nodes = root;
g_hash_table_remove_all (surface->node_lookup);
-
- init_node_lookup (surface, surface->nodes);
+ broadway_node_add_to_lookup (root, surface->node_lookup);
}
guint32
@@ -2097,7 +2112,8 @@ broadway_server_resync_surfaces (BroadwayServer *server)
if (surface->nodes)
broadway_output_surface_set_nodes (server->output, surface->id,
- surface->nodes, NULL);
+ surface->nodes,
+ NULL, NULL);
if (surface->visible)
broadway_output_show_surface (server->output, surface->id);
diff --git a/gdk/broadway/broadway-server.h b/gdk/broadway/broadway-server.h
index 1e125bd065..a5624ff6fa 100644
--- a/gdk/broadway/broadway-server.h
+++ b/gdk/broadway/broadway-server.h
@@ -29,6 +29,10 @@ struct _BroadwayNode {
guint32 n_children;
BroadwayNode **children;
guint32 texture_id;
+
+ /* Scratch stuff used during diff */
+ gboolean used;
+
guint32 n_data;
guint32 data[1];
};
@@ -37,6 +41,10 @@ gboolean broadway_node_equal (BroadwayNode *
BroadwayNode *b);
gboolean broadway_node_deep_equal (BroadwayNode *a,
BroadwayNode *b);
+void broadway_node_mark_deep_used (BroadwayNode *node,
+ gboolean used);
+void broadway_node_add_to_lookup (BroadwayNode *node,
+ GHashTable *node_lookup);
BroadwayServer *broadway_server_new (char *address,
int port,
const char *ssl_cert,
diff --git a/gdk/broadway/broadway.js b/gdk/broadway/broadway.js
index 96ed67ce4f..f5ccd78740 100644
--- a/gdk/broadway/broadway.js
+++ b/gdk/broadway/broadway.js
@@ -11,11 +11,12 @@ const BROADWAY_NODE_LINEAR_GRADIENT = 7;
const BROADWAY_NODE_SHADOW = 8;
const BROADWAY_NODE_OPACITY = 9;
const BROADWAY_NODE_CLIP = 10;
-const BROADWAY_NODE_KEEP_ALL = 11;
-const BROADWAY_NODE_KEEP_THIS = 12;
-const BROADWAY_NODE_TRANSFORM = 13;
-const BROADWAY_NODE_DEBUG = 14;
-const BROADWAY_NODE_REUSE = 15;
+const BROADWAY_NODE_TRANSFORM = 11;
+const BROADWAY_NODE_DEBUG = 12;
+const BROADWAY_NODE_REUSE = 13;
+
+const BROADWAY_NODE_OP_APPEND_NODE = 0;
+const BROADWAY_NODE_OP_REMOVE_NODE = 1;
const BROADWAY_OP_GRAB_POINTER = 'g';
const BROADWAY_OP_UNGRAB_POINTER = 'u';
@@ -56,14 +57,15 @@ const BROADWAY_EVENT_ROUNDTRIP_NOTIFY = 'F';
const DISPLAY_OP_REPLACE_CHILD = 0;
const DISPLAY_OP_APPEND_CHILD = 1;
-const DISPLAY_OP_APPEND_ROOT = 2;
-const DISPLAY_OP_SHOW_SURFACE = 3;
-const DISPLAY_OP_HIDE_SURFACE = 4;
-const DISPLAY_OP_DELETE_NODE = 5;
-const DISPLAY_OP_MOVE_NODE = 6;
-const DISPLAY_OP_RESIZE_NODE = 7;
-const DISPLAY_OP_RESTACK_SURFACES = 8;
-const DISPLAY_OP_DELETE_SURFACE = 9;
+const DISPLAY_OP_INSERT_AFTER_CHILD = 2;
+const DISPLAY_OP_APPEND_ROOT = 3;
+const DISPLAY_OP_SHOW_SURFACE = 4;
+const DISPLAY_OP_HIDE_SURFACE = 5;
+const DISPLAY_OP_DELETE_NODE = 6;
+const DISPLAY_OP_MOVE_NODE = 7;
+const DISPLAY_OP_RESIZE_NODE = 8;
+const DISPLAY_OP_RESTACK_SURFACES = 9;
+const DISPLAY_OP_DELETE_SURFACE = 10;
// GdkCrossingMode
const GDK_CROSSING_NORMAL = 0;
@@ -234,6 +236,7 @@ function cmdCreateSurface(id, x, y, width, height, isTemp)
surface.transientParent = 0;
surface.visible = false;
surface.imageData = null;
+ surface.old_nodes = {};
var div = document.createElement('div');
div.surface = surface;
@@ -296,12 +299,14 @@ function cmdLowerSurface(id)
moveToHelper(surface, 0);
}
-function TransformNodes(node_data, div, display_commands) {
+function TransformNodes(node_data, div, old_nodes, display_commands) {
this.node_data = node_data;
this.display_commands = display_commands;
this.data_pos = 0;
this.div = div;
this.outstanding = 1;
+ this.old_nodes = old_nodes;
+ this.new_nodes = {};
}
TransformNodes.prototype.decode_uint32 = function() {
@@ -474,20 +479,32 @@ function set_rrect_style (div, rrect) {
div.style["border-bottom-left-radius"] = args(px(rrect.sizes[3].width), px(rrect.sizes[3].height));
}
-TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
+function addOldIds(node, node_map) {
+ node_map[node.node_id] = node;
+
+ var child = node.firstChild;
+ while (child) {
+ addOldIds(child, node_map);
+ child = child.nextSibling;
+ }
+}
+
+
+TransformNodes.prototype.insertNode = function(parent, previousSibling, is_toplevel)
{
var type = this.decode_uint32();
+ var id = this.decode_uint32();
var newNode = null;
-
- // We need to dup this because as we reuse children the original order is lost
- var oldChildren = [];
- if (oldNode) {
- for (var i = 0; i < oldNode.children.length; i++)
- oldChildren[i] = oldNode.children[i];
- }
+ var oldNode = null;
switch (type)
{
+ /* Reuse divs from last frame */
+ case BROADWAY_NODE_REUSE:
+ {
+ oldNode = this.old_nodes[id];
+ }
+ break;
/* Leaf nodes */
case BROADWAY_NODE_TEXTURE:
@@ -656,7 +673,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
div.style["transform"] = transform_string;
div.style["transform-origin"] = "0px 0px";
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -668,7 +685,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
div.style["position"] = "absolute";
set_rect_style(div, rect);
div.style["overflow"] = "hidden";
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -680,7 +697,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
div.style["position"] = "absolute";
set_rrect_style(div, rrect);
div.style["overflow"] = "hidden";
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -694,7 +711,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
div.style["top"] = px(0);
div.style["opacity"] = opacity;
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -716,7 +733,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
div.style["top"] = px(0);
div.style["filter"] = filters;
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -726,7 +743,7 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
var str = this.decode_string();
var div = document.createElement('div');
div.setAttribute('debug', str);
- this.insertNode(div, -1, oldChildren[0]);
+ this.insertNode(div, null, false);
newNode = div;
}
break;
@@ -737,71 +754,59 @@ TransformNodes.prototype.insertNode = function(parent, posInParent, oldNode)
{
var div = document.createElement('div');
var len = this.decode_uint32();
+ var lastChild = null;
for (var i = 0; i < len; i++) {
- this.insertNode(div, -1, oldChildren[i]);
+ lastChild = this.insertNode(div, lastChild, false);
}
newNode = div;
}
break;
- case BROADWAY_NODE_KEEP_ALL:
- {
- if (!oldNode)
- alert("KEEP_ALL with no oldNode");
-
- if (oldNode.parentNode != parent)
- newNode = oldNode;
- else
- newNode = null;
- }
- break;
-
- case BROADWAY_NODE_KEEP_THIS:
- {
- if (!oldNode)
- alert("KEEP_THIS with no oldNode ");
-
- /* We only get keep-this if all parents were kept, check this */
- if (oldNode.parentNode != parent)
- alert("Got KEEP_THIS for non-kept parent");
-
- var len = this.decode_uint32();
- var i;
-
- for (i = 0; i < len; i++) {
- this.insertNode(oldNode, i,
- oldChildren[i]);
- }
-
- /* Remove children that are after the new length */
- for (i = oldChildren.length - 1; i > len - 1; i--)
- this.display_commands.push([DISPLAY_OP_DELETE_NODE, oldChildren[i]]);
-
- /* NOTE: No need to modify the parent, we're keeping this node as is */
- newNode = null;
- }
- break;
-
default:
alert("Unexpected node type " + type);
}
if (newNode) {
- if (posInParent >= 0 && parent.children[posInParent])
- this.display_commands.push([DISPLAY_OP_REPLACE_CHILD, parent, newNode,
parent.children[posInParent]]);
- else
+ newNode.node_id = id;
+ this.new_nodes[id] = newNode;
+ if (is_toplevel)
this.display_commands.push([DISPLAY_OP_APPEND_CHILD, parent, newNode]);
+ else // Here it is safe to display directly because we have not added the toplevel to the document
yet
+ parent.appendChild(newNode);
+ return newNode;
+ } else if (oldNode) {
+ addOldIds(oldNode, this.new_nodes);
+ // This must be delayed until display ops, because it will remove from the old parent
+ this.display_commands.push([DISPLAY_OP_INSERT_AFTER_CHILD, parent, previousSibling, oldNode]);
+ return oldNode;
}
}
TransformNodes.prototype.execute = function(display_commands)
{
- var div = this.div;
- this.insertNode(div, 0, div.firstChild, display_commands);
- if (this.data_pos != this.node_data.byteLength)
- alert ("Did not consume entire array (len " + this.node_data.byteLength + ")");
-}
+ var root = this.div;
+ while (this.data_pos < this.node_data.byteLength) {
+ var op = this.decode_uint32();
+
+ switch (op) {
+ case BROADWAY_NODE_OP_APPEND_NODE:
+ var parentId = this.decode_uint32();
+ var parent;
+ if (parentId == 0)
+ parent = root;
+ else
+ parent = this.old_nodes[parentId];
+ this.insertNode(parent, null, true);
+ break;
+ case BROADWAY_NODE_OP_REMOVE_NODE:
+ var removeId = this.decode_uint32();
+ var remove = this.old_nodes[removeId];
+ this.display_commands.push([DISPLAY_OP_DELETE_NODE, remove]);
+ break;
+ }
+ }
+}
function cmdGrabPointer(id, ownerEvents)
{
@@ -818,7 +823,7 @@ function cmdUngrabPointer()
function handleDisplayCommands(display_commands)
{
- var div;
+ var div, parent;
var len = display_commands.length;
for (var i = 0; i < len; i++) {
var cmd = display_commands[i];
@@ -830,6 +835,15 @@ function handleDisplayCommands(display_commands)
case DISPLAY_OP_APPEND_CHILD:
cmd[1].appendChild(cmd[2]);
break;
+ case DISPLAY_OP_INSERT_AFTER_CHILD:
+ parent = cmd[1];
+ var afterThis = cmd[2];
+ div = cmd[3];
+ if (afterThis == null) // First
+ parent.insertBefore(div, parent.firstChild);
+ else
+ parent.insertBefore(div, afterThis.nextSibling);
+ break;
case DISPLAY_OP_APPEND_ROOT:
document.body.appendChild(cmd[1]);
break;
@@ -1014,8 +1028,9 @@ function handleCommands(cmd, display_commands, new_textures, modified_trees)
var node_data = cmd.get_nodes ();
surface = surfaces[id];
- var transform_nodes = new TransformNodes (node_data, surface.div, display_commands);
+ var transform_nodes = new TransformNodes (node_data, surface.div, surface.old_nodes,
display_commands);
transform_nodes.execute();
+ surface.old_nodes = transform_nodes.new_nodes;
}
break;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
