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..0d4e111eb9bddaf14e4afd3c83bb40f5bdf19b12 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 as traversing the graph. |
dmichael (off chromium)
2013/06/04 16:59:10
nit: as->while
raymes
2013/06/04 19:36:06
Done.
|
+ 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)); |
@@ -68,24 +76,37 @@ RawVarDataGraph::~RawVarDataGraph() { |
// static |
scoped_ptr<RawVarDataGraph> RawVarDataGraph::Create(const PP_Var& var, |
- PP_Instance instance) { |
+ PP_Instance instance, |
+ bool allow_cycles) { |
scoped_ptr<RawVarDataGraph> graph(new RawVarDataGraph); |
// 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) { |
+ stack.pop(); |
+ if (::ppapi::VarTracker::IsVarTypeRefcounted(var.type)) |
dmichael (off chromium)
2013/06/04 16:59:10
I don't understand why you're looking at the type
raymes
2013/06/04 19:36:06
Yes...good catch. Thanks
|
+ parent_ids.erase(current_var.value.as_id); |
+ continue; |
+ } else { |
+ stack.top().sentinel = true; |
+ if (::ppapi::VarTracker::IsVarTypeRefcounted(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 +124,16 @@ 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 (!allow_cycles && |
+ ::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<ArrayRawVarData*>(current_var_data)->AddChild(child_id); |
- stack.push(make_pair(iter->get(), child_id)); |
+ stack.push(StackEntry(child, child_id)); |
} |
} else if (current_var.type == PP_VARTYPE_DICTIONARY) { |
DictionaryVar* dict_var = DictionaryVar::FromPPVar(current_var); |
@@ -118,11 +145,17 @@ 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 (!allow_cycles && |
+ ::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)); |
} |
} |
} |