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

webkit/plugins/ppapi/v8_var_converter.cc

Index: webkit/plugins/ppapi/v8_var_converter.cc
diff --git a/webkit/plugins/ppapi/v8_var_converter.cc b/webkit/plugins/ppapi/v8_var_converter.cc
index c895ca0c47f1138bc7cba9f512c2e5ed5b662fb0..dddb9d19a9b25e965fb3b1e339d3f88e905a8068 100644
--- a/webkit/plugins/ppapi/v8_var_converter.cc
+++ b/webkit/plugins/ppapi/v8_var_converter.cc
@@ -27,6 +27,14 @@ using std::make_pair;
 
 namespace {
 
+template <class T>
+struct StackEntry {
+  StackEntry(T v) : val(v), sentinel(false) {}
+  T val;
+  // Used to track parent nodes on the stack while traversing the graph.
+  bool sentinel;
+};
+
 struct HashedHandle {
   HashedHandle(v8::Handle<v8::Object> h) : handle(h) {}
   size_t hash() const { return handle->GetIdentityHash(); }
@@ -54,14 +62,17 @@ inline size_t hash_value(const HashedHandle& handle) {
 
 namespace webkit {
 namespace ppapi {
+namespace V8VarConverter {
 
 namespace {
 
 // Maps PP_Var IDs to the V8 value handle they correspond to.
 typedef base::hash_map<int64_t, v8::Handle<v8::Value> > VarHandleMap;
+typedef base::hash_set<int64_t> ParentVarSet;
 
 // Maps V8 value handles to the PP_Var they correspond to.
 typedef base::hash_map<HashedHandle, ScopedPPVar> HandleVarMap;
+typedef base::hash_set<HashedHandle> ParentHandleSet;
 
 // Returns a V8 value which corresponds to a given PP_Var. If |var| is a
 // reference counted PP_Var type, and it exists in |visited_ids|, the V8 value
@@ -71,10 +82,13 @@ typedef base::hash_map<HashedHandle, ScopedPPVar> HandleVarMap;
 bool GetOrCreateV8Value(const PP_Var& var,
                         v8::Handle<v8::Value>* result,
                         bool* did_create,
-                        VarHandleMap* visited_ids) {
+                        VarHandleMap* visited_ids,
+                        ParentVarSet* parent_ids) {
   *did_create = false;
 
   if (::ppapi::VarTracker::IsVarTypeRefcounted(var.type)) {
+    if (parent_ids->count(var.value.as_id) != 0)
+      return false;
     VarHandleMap::iterator it = visited_ids->find(var.value.as_id);
     if (it != visited_ids->end()) {
       *result = it->second;
@@ -151,7 +165,8 @@ bool GetOrCreateV8Value(const PP_Var& var,
 bool GetOrCreateVar(v8::Handle<v8::Value> val,
                     PP_Var* result,
                     bool* did_create,
-                    HandleVarMap* visited_handles) {
+                    HandleVarMap* visited_handles,
+                    ParentHandleSet* parent_handles) {
   CHECK(!val.IsEmpty());
   *did_create = false;
 
@@ -159,6 +174,9 @@ bool GetOrCreateVar(v8::Handle<v8::Value> val,
   // we still add them to |visited_handles| so that the corresponding string
   // PP_Var created will be properly refcounted.
   if (val->IsObject() || val->IsString()) {
+    if (parent_handles->count(HashedHandle(val->ToObject())) != 0)
+      return false;
+
     HandleVarMap::const_iterator it = visited_handles->find(
         HashedHandle(val->ToObject()));
     if (it != visited_handles->end()) {
@@ -193,8 +211,10 @@ bool GetOrCreateVar(v8::Handle<v8::Value> val,
       *result = (new DictionaryVar())->GetPPVar();
     }
   } else {
-    NOTREACHED();
-    return false;
+    // Silently ignore the case where we can't convert to a Var as we may
+    // be trying to convert a type that doesn't have a corresponding
+    // PP_Var type.
+    return true;
   }
 
   *did_create = true;
@@ -206,31 +226,52 @@ bool GetOrCreateVar(v8::Handle<v8::Value> val,
   return true;
 }
 
-}  // namespace
-
-V8VarConverter::V8VarConverter() {
+bool CanHaveChildren(PP_Var var) {
+  return var.type == PP_VARTYPE_ARRAY || var.type == PP_VARTYPE_DICTIONARY;
 }
 
-bool V8VarConverter::ToV8Value(const PP_Var& var,
-                               v8::Handle<v8::Context> context,
-                               v8::Handle<v8::Value>* result) const {
+}  // namespace
+
+// To/FromV8Value use a stack-based DFS search to traverse V8/Var graph. Each
+// iteration, the top node on the stack examined. If the node has not been
+// visited yet (i.e. sentinel == false) then it is added to the list of parents
+// which contains all of the nodes on the path from the start node to the
+// current node. Each of the current nodes children are examined. If they appear
+// in the list of parents it means we have a cycle and we return NULL.
+// Otherwise, if they can have children, we add them to the stack. If the
+// node at the top of the stack has already been visited, then we pop it off the
+// stack and erase it from the list of parents.
+// static
+bool ToV8Value(const PP_Var& var,
+               v8::Handle<v8::Context> context,
+               v8::Handle<v8::Value>* result) {
   v8::Context::Scope context_scope(context);
   v8::HandleScope handle_scope;
 
   VarHandleMap visited_ids;
+  ParentVarSet parent_ids;
 
-  std::stack<PP_Var> stack;
-  stack.push(var);
+  std::stack<StackEntry<PP_Var> > stack;
+  stack.push(StackEntry<PP_Var>(var));
   v8::Handle<v8::Value> root;
   bool is_root = true;
 
   while (!stack.empty()) {
-    const PP_Var& current_var = stack.top();
+    const PP_Var& current_var = stack.top().val;
     v8::Handle<v8::Value> current_v8;
-    stack.pop();
+
+    if (stack.top().sentinel) {
+      stack.pop();
+      if (CanHaveChildren(current_var))
+        parent_ids.erase(current_var.value.as_id);
+      continue;
+    } else {
+      stack.top().sentinel = true;
+    }
+
     bool did_create = false;
     if (!GetOrCreateV8Value(current_var, &current_v8, &did_create,
-                            &visited_ids)) {
+                            &visited_ids, &parent_ids)) {
       return false;
     }
 
@@ -241,6 +282,7 @@ bool V8VarConverter::ToV8Value(const PP_Var& var,
 
     // Add child nodes to the stack.
     if (current_var.type == PP_VARTYPE_ARRAY) {
+      parent_ids.insert(current_var.value.as_id);
       ArrayVar* array_var = ArrayVar::FromPPVar(current_var);
       if (!array_var) {
         NOTREACHED();
@@ -253,14 +295,11 @@ bool V8VarConverter::ToV8Value(const PP_Var& var,
         const PP_Var& child_var = array_var->elements()[i].get();
         v8::Handle<v8::Value> child_v8;
         if (!GetOrCreateV8Value(child_var, &child_v8, &did_create,
-                                &visited_ids)) {
+                                &visited_ids, &parent_ids)) {
           return false;
         }
-        if (did_create &&
-            (child_var.type == PP_VARTYPE_DICTIONARY ||
-             child_var.type == PP_VARTYPE_ARRAY)) {
+        if (did_create && CanHaveChildren(child_var))
           stack.push(child_var);
-        }
         v8::TryCatch try_catch;
         v8_array->Set(static_cast<uint32>(i), child_v8);
         if (try_catch.HasCaught()) {
@@ -269,6 +308,7 @@ bool V8VarConverter::ToV8Value(const PP_Var& var,
         }
       }
     } else if (current_var.type == PP_VARTYPE_DICTIONARY) {
+      parent_ids.insert(current_var.value.as_id);
       DictionaryVar* dict_var = DictionaryVar::FromPPVar(current_var);
       if (!dict_var) {
         NOTREACHED();
@@ -285,14 +325,11 @@ bool V8VarConverter::ToV8Value(const PP_Var& var,
         const PP_Var& child_var = iter->second.get();
         v8::Handle<v8::Value> child_v8;
         if (!GetOrCreateV8Value(child_var, &child_v8, &did_create,
-                                &visited_ids)) {
+                                &visited_ids, &parent_ids)) {
           return false;
         }
-        if (did_create &&
-            (child_var.type == PP_VARTYPE_DICTIONARY ||
-             child_var.type == PP_VARTYPE_ARRAY)) {
+        if (did_create && CanHaveChildren(child_var))
           stack.push(child_var);
-        }
         v8::TryCatch try_catch;
         v8_object->Set(v8::String::New(key.c_str(), key.length()), child_v8);
         if (try_catch.HasCaught()) {
@@ -308,26 +345,36 @@ bool V8VarConverter::ToV8Value(const PP_Var& var,
   return true;
 }
 
-bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
-                                 v8::Handle<v8::Context> context,
-                                 PP_Var* result) const {
+bool FromV8Value(v8::Handle<v8::Value> val,
+                 v8::Handle<v8::Context> context,
+                 PP_Var* result) {
   v8::Context::Scope context_scope(context);
   v8::HandleScope handle_scope;
 
   HandleVarMap visited_handles;
+  ParentHandleSet parent_handles;
 
-  std::stack<v8::Handle<v8::Value> > stack;
-  stack.push(val);
+  std::stack<StackEntry<v8::Handle<v8::Value> > > stack;
+  stack.push(StackEntry<v8::Handle<v8::Value> >(val));
   ScopedPPVar root;
   bool is_root = true;
 
   while (!stack.empty()) {
-    v8::Handle<v8::Value> current_v8 = stack.top();
+    v8::Handle<v8::Value> current_v8 = stack.top().val;
     PP_Var current_var;
-    stack.pop();
+
+    if (stack.top().sentinel) {
+      stack.pop();
+      if (current_v8->IsObject())
+        parent_handles.erase(HashedHandle(current_v8->ToObject()));
+      continue;
+    } else {
+      stack.top().sentinel = true;
+    }
+
     bool did_create = false;
     if (!GetOrCreateVar(current_v8, &current_var, &did_create,
-                        &visited_handles)) {
+                        &visited_handles, &parent_handles)) {
       return false;
     }
 
@@ -340,6 +387,7 @@ bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
     if (current_var.type == PP_VARTYPE_ARRAY) {
       DCHECK(current_v8->IsArray());
       v8::Handle<v8::Array> v8_array = current_v8.As<v8::Array>();
+      parent_handles.insert(HashedHandle(v8_array));
 
       ArrayVar* array_var = ArrayVar::FromPPVar(current_var);
       if (!array_var) {
@@ -358,11 +406,8 @@ bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
 
         PP_Var child_var;
         if (!GetOrCreateVar(child_v8, &child_var, &did_create,
-                            &visited_handles)) {
-          // Silently ignore the case where we can't convert to a Var as we may
-          // be trying to convert a type that doesn't have a corresponding
-          // PP_Var type.
-          continue;
+                            &visited_handles, &parent_handles)) {
+          return false;
         }
         if (did_create && child_v8->IsObject())
           stack.push(child_v8);
@@ -372,6 +417,7 @@ bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
     } else if (current_var.type == PP_VARTYPE_DICTIONARY) {
       DCHECK(current_v8->IsObject());
       v8::Handle<v8::Object> v8_object = current_v8->ToObject();
+      parent_handles.insert(HashedHandle(v8_object));
 
       DictionaryVar* dict_var = DictionaryVar::FromPPVar(current_var);
       if (!dict_var) {
@@ -403,8 +449,8 @@ bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
 
         PP_Var child_var;
         if (!GetOrCreateVar(child_v8, &child_var, &did_create,
-                            &visited_handles)) {
-          continue;
+                            &visited_handles, &parent_handles)) {
+          return false;
         }
         if (did_create && child_v8->IsObject())
           stack.push(child_v8);
@@ -419,5 +465,6 @@ bool V8VarConverter::FromV8Value(v8::Handle<v8::Value> val,
   return true;
 }
 
+}  // namespace V8VarConverter
 }  // namespace ppapi
 }  // namespace webkit