Don't send PP_Vars/V8 values with cycles across PostMessage

ppapi/proxy/raw_var_data.cc

Index: ppapi/proxy/raw_var_data.cc
diff --git a/ppapi/proxy/raw_var_data.cc b/ppapi/proxy/raw_var_data.cc
index d4ad2799010d650cb1d3100cd8f757e02d82063d..557fe9756935f3f31e589cc61e1d4b65b0ce1eb3 100644
--- a/ppapi/proxy/raw_var_data.cc
+++ b/ppapi/proxy/raw_var_data.cc
@@ -35,21 +35,29 @@ void DefaultHandleWriter(IPC::Message* m, const SerializedHandle& handle) {
   IPC::ParamTraits<SerializedHandle>::Write(m, handle);
 }
 
+struct StackEntry {
+  StackEntry(PP_Var v, size_t i) : var(v), data_index(i), sentinel(false) {}
+  PP_Var var;
+  size_t data_index;
+  // Used to track parent nodes on the stack while traversing the graph.
+  bool sentinel;
+};
+
 // For a given PP_Var, returns the RawVarData associated with it, or creates a
 // new one if there is no existing one. The data is appended to |data| if it
 // is newly created. The index into |data| pointing to the result is returned.
-// |id_map| keeps track of RawVarDatas that have already been created.
+// |visited_map| keeps track of RawVarDatas that have already been created.
 size_t GetOrCreateRawVarData(const PP_Var& var,
-                             base::hash_map<int64_t, size_t>* id_map,
+                             base::hash_map<int64_t, size_t>* visited_map,
                              ScopedVector<RawVarData>* data) {
   if (VarTracker::IsVarTypeRefcounted(var.type)) {
-    base::hash_map<int64_t, size_t>::iterator it = id_map->find(
+    base::hash_map<int64_t, size_t>::iterator it = visited_map->find(
         var.value.as_id);
-    if (it != id_map->end()) {
+    if (it != visited_map->end()) {
       return it->second;
     } else {
       data->push_back(RawVarData::Create(var.type));
-      (*id_map)[var.value.as_id] = data->size() - 1;
+      (*visited_map)[var.value.as_id] = data->size() - 1;
     }
   } else {
     data->push_back(RawVarData::Create(var.type));
@@ -71,21 +79,33 @@ scoped_ptr<RawVarDataGraph> RawVarDataGraph::Create(const PP_Var& var,
                                                     PP_Instance instance) {
   scoped_ptr<RawVarDataGraph> graph(new RawVarDataGraph);

[dmichael (off chromium), 2013/06/05 17:05:47]

Looking at this algorithm again, it seems like it could be simplified a little
bit. Might lead to a little less code and a little bit better performance (same
complexity, just less revisiting nodes and/or pushing/popping stuff on the
stack)

I sprinkled some comments in below that go together (i.e., some might not make
complete sense without the other suggestions).

Tangentially, you might be able to make the algorithm a little easier to read
and reason about by making the stack slightly more sophisticated:
struct StackFrame {
  size_t parent_index;
  queue<size_t> children;  // stack or vector are fine, too
};
(I think you only need to know index, but you could add PP_Var if it helps with
something).

The idea is you look at the current stack top's children. If it's non-empty, pop
a child from the queue, create a new StackFrame for it, and push it on the
stack. If the queue of children *is* empty, you know you're done with that
StackFrame and can pop it.

I don't know if this will actually be more readable, but it just separates the
"sentinel" values from the non-sentinel ones more explicitly. Feel free to try
it or ignore it.

In either case, a short description of the algorithm somewhere would be helpful.

[raymes, 2013/06/05 22:48:26]

I agree that it's not the easiest to understand. Those changes might improve it
a little, I think it's hard to say without trying it.

I think the biggest way to improve this (in terms of making it easy to
understand/reason about) would be to use the visitor pattern to implement the
algorithm. Basically to pull out the traversal/cycle-detection logic into one
class and the conversion logic into another class. Then we could re-use the
traversal logic for the 3 cases we currently have where we traverse the var
graph and only implement the conversion logic there.

Of course this is at /slight/ odds with making the thing really efficient. For
example, right now we are able to add the children to the ArrayRawVarData during
the traversal (i.e. right before we add them to the stack). If we separated that
logic then we would end up traversing the children during the conversion as
well. I think the tradeoff is worth it though.

I toyed with this idea before I started to write this stuff but thought it might
be overdesigning it a bit. Also, it only helps us in the Var-to-something else
case (e.g. it doesn't help us when going from v8 value back to var unless we
write a visitor for v8 values). But then again there's a bunch of places where
we traverse v8 values and base values so maybe it's just a pattern we should use
more often :)

   // Map of |var.value.as_id| to a RawVarData index in RawVarDataGraph.
-  base::hash_map<int64_t, size_t> id_map;
+  base::hash_map<int64_t, size_t> visited_map;
+  base::hash_set<int64_t> parent_ids;
 
-  std::stack<std::pair<PP_Var, size_t> > stack;
-  stack.push(make_pair(var, GetOrCreateRawVarData(var, &id_map,
-                                                  &graph->data_)));
+  std::stack<StackEntry> stack;
+  stack.push(StackEntry(var, GetOrCreateRawVarData(var, &visited_map,
+                                                   &graph->data_)));
 
   // Traverse the PP_Var graph with DFS.
   while (!stack.empty()) {
-    PP_Var current_var = stack.top().first;
-    RawVarData* current_var_data = graph->data_[stack.top().second];
-    stack.pop();
+    PP_Var current_var = stack.top().var;
+    RawVarData* current_var_data = graph->data_[stack.top().data_index];
+
+    if (stack.top().sentinel) {

[dmichael (off chromium), 2013/06/05 17:05:47]

Can you avoid adding the new "sentinel" thing by just checking whether the item
has been initialized? (This goes along with the comment on 134 below...)

If it's been initialized, its children have already been added, and we can pop
it.

[raymes, 2013/06/05 22:48:26]

Yes, good catch.

+      stack.pop();
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(current_var.type))
+        parent_ids.erase(current_var.value.as_id);

[dmichael (off chromium), 2013/06/05 17:05:47]

Here, if you only put in types that can have children, you don't need to check
if it's ref-counted. Just erase it.

[raymes, 2013/06/05 22:48:26]

But then the base case changes (i.e. you have to make sure the starting node
doesn't have children and initialize it properly which duplicates part of the
body of this loop). I think it's a tradeoff.

+      continue;
+    } else {
+      stack.top().sentinel = true;
+      if (::ppapi::VarTracker::IsVarTypeRefcounted(current_var.type))
+        parent_ids.insert(current_var.value.as_id);
+    }
 
-    // If the node is initialized, it means we have visited it.
-    if (current_var_data->initialized())
+    // If the node is initialized, it means we have visited it already.
+    if (current_var_data->initialized()) {
       continue;
+    }
 
     if (!current_var_data->Init(current_var, instance)) {
       NOTREACHED();
@@ -103,10 +123,15 @@ scoped_ptr<RawVarDataGraph> RawVarDataGraph::Create(const PP_Var& var,
                array_var->elements().begin();
            iter != array_var->elements().end();
            ++iter) {
-        size_t child_id = GetOrCreateRawVarData(iter->get(), &id_map,
+        const PP_Var& child = iter->get();
+        if (::ppapi::VarTracker::IsVarTypeRefcounted(child.type) &&
+            parent_ids.count(child.value.as_id) != 0) {

[dmichael (off chromium), 2013/06/05 17:05:47]

How about an explicit comment here (and below) that this is to detect and
prevent cycles

[raymes, 2013/06/05 22:48:26]

Done.

+          return scoped_ptr<RawVarDataGraph>();
+        }
+        size_t child_id = GetOrCreateRawVarData(child, &visited_map,
                                                 &graph->data_);
         static_cast<ArrayRawVarData*>(current_var_data)->AddChild(child_id);
-        stack.push(make_pair(iter->get(), child_id));
+        stack.push(StackEntry(child, child_id));

[dmichael (off chromium), 2013/06/05 17:05:47]

How about checking at this point whether or not:
1) The type can have children. If not, no need to push it on the stack.
2) Whether the type is initialized. If so, no need to push it on the stack. It's
already been processed.

[raymes, 2013/06/05 22:48:26]

Even if the node doesn't have children, it has to have Init() called on it. So I
could pull that logic down here, but then the sentinel logic changes :P 

       }
     } else if (current_var.type == PP_VARTYPE_DICTIONARY) {
       DictionaryVar* dict_var = DictionaryVar::FromPPVar(current_var);
@@ -118,11 +143,16 @@ scoped_ptr<RawVarDataGraph> RawVarDataGraph::Create(const PP_Var& var,
                dict_var->key_value_map().begin();
            iter != dict_var->key_value_map().end();
            ++iter) {
-        size_t child_id = GetOrCreateRawVarData(iter->second.get(), &id_map,
+        const PP_Var& child = iter->second.get();
+        if (::ppapi::VarTracker::IsVarTypeRefcounted(child.type) &&
+            parent_ids.count(child.value.as_id) != 0) {
+          return scoped_ptr<RawVarDataGraph>();
+        }
+        size_t child_id = GetOrCreateRawVarData(child, &visited_map,
                                                 &graph->data_);
         static_cast<DictionaryRawVarData*>(
             current_var_data)->AddChild(iter->first, child_id);
-        stack.push(make_pair(iter->second.get(), child_id));
+        stack.push(StackEntry(child, child_id));
       }
     }
   }