Introduce SerializeDictionaryForest for devtools_target_ui

Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

The touched code also seemed to create too many scoped_refptr<DevToolsAgentHost>
instances: in cases where there is already a scoped_refptr holding an object
alive outside of the current context, it is better to use just raw pointers in
for loops and argument passing, to avoid unnecessary churn with AddRef/Release
calls.

Therefore this CL also changed for loops inside of
LocalTargetsUIHandler::SendTargets to use const scoped_refptr& (still avoids
the AddRef/Release churn when raw pointer is not an option) as well as the
argument of DevToolsTargetsUIHandler::Serialize to just a raw pointer.

BUG=712119
Review-Url: https://codereview.chromium.org/2825533002
Cr-Commit-Position: refs/heads/master@{#465948}
Committed: https://chromium.googlesource.com/chromium/src/+/668159776484e722ffaaad38c8201fc49e62b937

[vabr (Chromium), 2017-04-17 18:30:43]

Description was changed from

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

In addition, the CL also changes the code to use raw pointers to
DevToolsAgentHost instead of creating repeatedly scoped_refptrs to it on a
couple of places where the existence of the pointed object is guaranteed by a
scoped_refptr in the context. These places are for-loops inside of
LocalTargetsUIHandler::SendTargets as well as the argument of
DevToolsTargetsUIHandler::Serialize. Creating the scoped_refptrs repeatedly
when the existence of the pointer to object is guaranteed only adds unnecessary
AddRef/Release calls.

BUG=712119
==========

to

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

In addition, the CL also changes the code to use raw pointers to
DevToolsAgentHost instead of creating repeatedly scoped_refptrs to it on a
couple of places where the existence of the pointed object is guaranteed by a
scoped_refptr in the context. These places are for-loops inside of
LocalTargetsUIHandler::SendTargets as well as the argument of
DevToolsTargetsUIHandler::Serialize. Creating the scoped_refptrs repeatedly
when the existence of the pointer to object is guaranteed only adds unnecessary
AddRef/Release calls.

BUG=712119
==========

[vabr (Chromium), 2017-04-17 18:53:12]

Description was changed from

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

In addition, the CL also changes the code to use raw pointers to
DevToolsAgentHost instead of creating repeatedly scoped_refptrs to it on a
couple of places where the existence of the pointed object is guaranteed by a
scoped_refptr in the context. These places are for-loops inside of
LocalTargetsUIHandler::SendTargets as well as the argument of
DevToolsTargetsUIHandler::Serialize. Creating the scoped_refptrs repeatedly
when the existence of the pointer to object is guaranteed only adds unnecessary
AddRef/Release calls.

BUG=712119
==========

to

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

The touched code also seemed to create too many scoped_refptr<DevToolsAgentHost>
instances: in cases where there is already a scoped_refptr holding an object
alive outside of the current context, it is better to use just raw pointers in
for loops and argument passing, to avoid unnecessary churn with AddRef/Release
calls.

Therefore this CL also changed for loops inside of
LocalTargetsUIHandler::SendTargets to use const scoped_refptr& (still avoids
the AddRef/Release churn when raw pointer is not an option) as well as the
argument of DevToolsTargetsUIHandler::Serialize to just a raw pointer.

BUG=712119
==========

[vabr (Chromium), 2017-04-17 18:53:18]

The CQ bit was checked by vabr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-17 18:53:43]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-17 19:58:41]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-17 19:58:42]

Dry run: This issue passed the CQ dry run.

[vabr (Chromium), 2017-04-17 20:16:33]

vabr@chromium.org changed reviewers:
+ dgozman@chromium.org, jdoerrie@chromium.org

[vabr (Chromium), 2017-04-17 20:16:34]

Hi all!

dgozman@ -- could you please review the whole patch?

jdoerrie@ -- could you please check the places where I use std::move that I
don't do anything stupid with base::Values?

Cheers,
Vaclav

[dgozman, 2017-04-17 21:22:43]

Thank you for fixing this!
I believe we can simplify this a bit, see below.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/devtools_targets_ui.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/devtools_targets_ui.cc:264:
SerializeDictionaryForest(std::move(forest), kGuestList));
Since there could be no more than one parent, I have a feeling this could be
done in less complicated manner by traversing hosts from parent to children.
WDYT?

map<string, vector<host>> children;
map<string, host> roots;
for host: targets
  if host.parent
    children[host.parent.id].push_back(host)
  else
    roots.push_back(host)
for root : roots:
  list_value.append(serialize(root, children))  
SendSerializedTargets(list_value)


serialize(host, children):
  append data to dictionary
  for child : children[host.id]
    children_list.append(serialize(child, children))
  if children_list.length
    dictionary.set(kGuestList, children_list)
  return dictionary

[vabr (Chromium), 2017-04-18 08:52:49]

Thanks for the quick reply!

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/devtools_targets_ui.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/devtools_targets_ui.cc:264:
SerializeDictionaryForest(std::move(forest), kGuestList));
On 2017/04/17 21:22:43, dgozman wrote:
> Since there could be no more than one parent, I have a feeling this could be
> done in less complicated manner by traversing hosts from parent to children.
> WDYT?
> 
> map<string, vector<host>> children;
> map<string, host> roots;
> for host: targets
>   if host.parent
>     children[host.parent.id].push_back(host)
>   else
>     roots.push_back(host)
> for root : roots:
>   list_value.append(serialize(root, children))  
> SendSerializedTargets(list_value)
> 
> 
> serialize(host, children):
>   append data to dictionary
>   for child : children[host.id]
>     children_list.append(serialize(child, children))
>   if children_list.length
>     dictionary.set(kGuestList, children_list)
>   return dictionary

Thanks for the suggestion.

One thing which is less complicated in your suggestion is keeping the whole code
here in LocalTargetsUIHandler::SendTargets and dealing with DevToolsAgentsHost
directly. In my code I pulled that out into SerializeDictionaryForest and used
the DictionaryForestNode abstraction to be able to unittest this properly. I
would like to keep that testability, because I suspect it was the absence of
unittests which let the bug creep in unnoticed.

Another simplification is using the map<..., vector<>> to compute children. In
my current CL I use the ChildrenRepresentation object. The latter is slightly
more complicated, but well encapsulated (i.e., does not interfere with the rest)
and more efficient -- instead of allocating tiny vectors for every parent node,
it uses one big vector to store all children. I'm happy to replace
ChildrenRepresentation with the inlined map and for-loop if you feel that the
clarity win is substantial enough and beats the performance.

A third simplification would be to replace Kahn's algorithm with the recursive
"serialize" function performing the DFS, as you suggest. Both are performing a
topological sort; in the current CL I separate the sorting from the processing
to make it easier to prove correctness of each of them. Avoiding the non-tail
recursion in "serialize" is also better for performance.

I'd like to hear your opinion about the above parts of the suggested change to
the current code. You are the code OWNER, so I will follow your advice, as long
as you considered the known pros and cons and the resulting code is (easily)
unit-tested.

[jdoerrie, 2017-04-18 09:57:45]

Thank you very much for fixing this, vabr@! Usage of std::move + base::Value
LGTM.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/devtools_targets_ui.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/devtools_targets_ui.cc:241: std::map<std::string,
DictionaryForestNode*> id_to_node;
Small suggestion:
Given that you care about performance and don't use the sorted-ness of the map
you could consider replacing std::map with std::unordered_map or base::flat_map.
This applies to the other usages of std::map in serialize_dictionary_forest.cc
as well.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_dictionary_forest.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:79: return
ChildrenRange(first_child, first_child + ol.length);
Nit: 
return {first_child, first_child + ol.length};

This matches your style in the unit test when you return DictionaryForestNodes.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:180:
no_incoming_edges.push_back(child);
Another small suggestion:
Given that the children for a given node are contiguous in memory by
construction, you could consider dropping the for loop and ChildrenRange struct
in favor of range-based |std::vector::insert| or |std::copy|. For this to work
|For| would need to return an iterator pair. It's up to you, this code is very
clear as it is.

[jdoerrie, 2017-04-19 08:35:00]

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_dictionary_forest.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:137:
base::MakeUnique<base::Value>(std::move(child_description)));
FYI, r465517 just landed, so you could get rid of the unique_ptr now:

children_weak->base::Value::GetList().push_back(std::move(child_description));

Unfortunately, currently you need to fully qualify GetList when invoking it on a
ListValue, because otherwise ListValue's own GetList methods
(https://codesearch.chromium.org/chromium/src/base/values.h?l=437,438) shadow it
and the compiler complains.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:198:
base::MakeUnique<base::Value>(std::move(node->representation)));
Same here, this could be:

roots.base::Value::GetList().push_back(std::move(node->representation));

[vabr (Chromium), 2017-04-19 10:15:05]

The CQ bit was checked by vabr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-19 10:15:27]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vabr (Chromium), 2017-04-19 11:03:17]

@jdoerrie: Thanks for the review. Please see my replies and the updated patch.

@dgozman: Looking forward to hearing your opinions in the discussion started
under your original comment.

Cheers,
Vaclav

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/devtools_targets_ui.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/devtools_targets_ui.cc:241: std::map<std::string,
DictionaryForestNode*> id_to_node;
On 2017/04/18 09:57:44, jdoerrie wrote:
> Small suggestion:
> Given that you care about performance and don't use the sorted-ness of the map
> you could consider replacing std::map with std::unordered_map or
base::flat_map.
> This applies to the other usages of std::map in serialize_dictionary_forest.cc
> as well.

Thanks!

What I'm reading in the description of base::flat_set (which should also apply
to flat_map), is that the continguous storage (vector instead of the search
tree) is beneficial for iteration and copying of such maps. However, what I do
with id_to_node and also locations and free_slots (the only maps in
serialize_dictionary_forest.cc) is mostly insertion and retrieval, for which
having the storage in a search tree seems better to me. Did I misunderstood the
advantages of the flat containers?

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_dictionary_forest.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:79: return
ChildrenRange(first_child, first_child + ol.length);
On 2017/04/18 09:57:44, jdoerrie wrote:
> Nit: 
> return {first_child, first_child + ol.length};
> 
> This matches your style in the unit test when you return
DictionaryForestNodes.

Acknowledged, but changed due to getting rid of ChildrenRange.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:137:
base::MakeUnique<base::Value>(std::move(child_description)));
On 2017/04/19 08:35:00, jdoerrie wrote:
> FYI, r465517 just landed, so you could get rid of the unique_ptr now:
> 
> children_weak->base::Value::GetList().push_back(std::move(child_description));
> 
> Unfortunately, currently you need to fully qualify GetList when invoking it on
a
> ListValue, because otherwise ListValue's own GetList methods
> (https://codesearch.chromium.org/chromium/src/base/values.h?l=437,438) shadow
it
> and the compiler complains.

Cool, thanks!

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:180:
no_incoming_edges.push_back(child);
On 2017/04/18 09:57:44, jdoerrie wrote:
> Another small suggestion:
> Given that the children for a given node are contiguous in memory by
> construction, you could consider dropping the for loop and ChildrenRange
struct
> in favor of range-based |std::vector::insert| or |std::copy|. For this to work
> |For| would need to return an iterator pair. It's up to you, this code is very
> clear as it is.

I like that, ChildrenRange was too much boilerplate.

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:198:
base::MakeUnique<base::Value>(std::move(node->representation)));
On 2017/04/19 08:35:00, jdoerrie wrote:
> Same here, this could be:
> 
> roots.base::Value::GetList().push_back(std::move(node->representation));

Done.

[commit-bot: I haz the power, 2017-04-19 11:28:21]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-19 11:28:22]

Dry run: This issue passed the CQ dry run.

[jdoerrie, 2017-04-19 11:45:51]

Still LGTM :) TIL about base::Reversed, thanks!

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
File chrome/browser/devtools/devtools_targets_ui.cc (right):

https://codereview.chromium.org/2825533002/diff/20001/chrome/browser/devtools...
chrome/browser/devtools/devtools_targets_ui.cc:241: std::map<std::string,
DictionaryForestNode*> id_to_node;
On 2017/04/19 11:03:17, vabr (Chromium) wrote:
> On 2017/04/18 09:57:44, jdoerrie wrote:
> > Small suggestion:
> > Given that you care about performance and don't use the sorted-ness of the
map
> > you could consider replacing std::map with std::unordered_map or
> base::flat_map.
> > This applies to the other usages of std::map in
serialize_dictionary_forest.cc
> > as well.
> 
> Thanks!
> 
> What I'm reading in the description of base::flat_set (which should also apply
> to flat_map), is that the continguous storage (vector instead of the search
> tree) is beneficial for iteration and copying of such maps. However, what I do
> with id_to_node and also locations and free_slots (the only maps in
> serialize_dictionary_forest.cc) is mostly insertion and retrieval, for which
> having the storage in a search tree seems better to me. Did I misunderstood
the
> advantages of the flat containers?

No, you are right, the main advantages of flat containers do not apply here.
Nevertheless, std::unordered_map should be better (at least asymptotically), but
I never actually checked whether there is a significant difference in practice.
So leaving std::map is definitely fine.

https://codereview.chromium.org/2825533002/diff/40001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_dictionary_forest.cc (right):

https://codereview.chromium.org/2825533002/diff/40001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:21: using ChildIter =
std::vector<DictionaryForestNode*>::iterator;
nit: This could be a const_iterator.

Also some pointers in the code below could be const, but I'm not sure whether
this is worth the effort in this case.

[vabr (Chromium), 2017-04-19 13:35:05]

@dgozman -- just a quick heads-up: I did some benchmarking and based on the
result will rewrite the CL to follow most of your comments.
I will post the details on the bug and ping this review once the patch is
updated.

[vabr (Chromium), 2017-04-19 14:33:49]

The CQ bit was checked by vabr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-19 14:34:12]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-19 15:46:14]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-19 15:46:15]

Dry run: This issue passed the CQ dry run.

[vabr (Chromium), 2017-04-19 16:22:50]

The CQ bit was checked by vabr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-19 16:23:26]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vabr (Chromium), 2017-04-19 16:25:49]

Hi dgozman@,

Thanks for bearing with me!

The benchmark discussion is in https://crbug.com/712119#c6 with a correction in
https://crbug.com/712119#c7.

Based on that, your suggestion with DFS and recursion is the most efficient (as
long as the benchmark is realistic, which I would like you to check). It is also
the easiest to read, so I switched to that in patch set 4.

I still kept the separate helper in the separate file, for the sake of easy
testability. I even extended the helper with computing the "children" map, to
keep the harder-to-test callsite LocalTargetsUIHandler::SendTargets as
straightforward as possible.

Please review the current patch set (5).

Thanks!
Vaclav

https://codereview.chromium.org/2825533002/diff/40001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_dictionary_forest.cc (right):

https://codereview.chromium.org/2825533002/diff/40001/chrome/browser/devtools...
chrome/browser/devtools/serialize_dictionary_forest.cc:21: using ChildIter =
std::vector<DictionaryForestNode*>::iterator;
On 2017/04/19 11:45:51, jdoerrie wrote:
> nit: This could be a const_iterator.
> 
> Also some pointers in the code below could be const, but I'm not sure whether
> this is worth the effort in this case.

[EDIT: This is now obsolete, the code has changed.]

You are right, the compiler is fine with this being const_iterator.

With the const pointers, if you meant switching to const DictionaryForstNode*,
I'm not so sure -- ultimately they end up being passed to |sorted|, from where
the nodes are indeed modified.

[commit-bot: I haz the power, 2017-04-19 17:59:34]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-19 17:59:35]

Dry run: This issue passed the CQ dry run.

[dgozman, 2017-04-19 22:05:14]

This looks very nice, thank you! A couple of nits below.

lgtm

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_host_descriptions.cc (right):

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions.cc:95:
CreateDictionaryForest(std::move(hosts));
It's usually less typing to use output params rather than return a tuple.

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions.cc:99:
list_value.base::Value::GetList().push_back(
I'm curious why do you have to specify the full name through the base class?

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_host_descriptions_unittest.cc (right):

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions_unittest.cc:52: // Test
serializing a small forest, of this structure:
I'd suggest less linear test to check the topological sort, if you are
interested:

5 -- 2 -- 4
0 -- 6
  \ 1
  \ 3

[vabr (Chromium), 2017-04-20 07:29:39]

Thanks for the review!

I addressed the comments and will send this to CQ now.

Cheers,
Vaclav

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_host_descriptions.cc (right):

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions.cc:95:
CreateDictionaryForest(std::move(hosts));
On 2017/04/19 22:05:14, dgozman wrote:
> It's usually less typing to use output params rather than return a tuple.

I thought about that, but even with output params the map and three vectors
looked pretty horrible, and on the callsite it's roughly the same.

I considered three approaches here:
(1) output params
  Pros: only mentioning the types once (instead of twice) in
        CreateDictionaryForest; also no need to explain what parts of the
        tuple do what in a comment
  Cons: the need to .clear() the arguments on call (or have long comments
        about contracts)
(2) returning a tuple
  Pros: clear semantics of a return typ (no .clear(), no need to point out this
        is output param, etc.)
  Cons: repeating the types twice in CreateDictionaryForest
(3) encapsulating in a class/struct
  Pros: one-liner on the callsite
  Cons: too much boilerplate, the most verbose, and also having a class with
        no real methods apart from a heavy constructor is strange


To me, (3) seemed like the worst solution, and I liked the clear concept
involved in (2), which is what I favoured.

But I have no strong opposition to (1), and I will to switch to that, given that
you favour it.

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions.cc:99:
list_value.base::Value::GetList().push_back(
On 2017/04/19 22:05:14, dgozman wrote:
> I'm curious why do you have to specify the full name through the base class?

Currenty, both Value and ListValue define GetList. The former takes 0 arguments
and returns the underlying vector storing things in case the said Value is in
fact a ListValue. That's a new method added as a part of moving to value
semantics for base::Value. The latter is just an old convenience accessor in
ListValue, taking 2 arguments and returning a particular sub-value and
converting it to ListValue.

The compiler fails to find the correct GetList and just complains that calling
GetList on ListValue with no arguments is wrong. So I needed to be explicit
about which GetList I wanted.

This is only temporary. As the refactoring of base::Value progresses, all the
subclasses, including ListValue, will be merged into Value (such as already all
except for ListValue and DictionaryValue were merged). At that point, this
problem will disappear and this code will get the unnecessary base::Value::
specifier deleted.

More details about the base::Value refactoring can be found in
https://crbug.com/646113.

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
File chrome/browser/devtools/serialize_host_descriptions_unittest.cc (right):

https://codereview.chromium.org/2825533002/diff/80001/chrome/browser/devtools...
chrome/browser/devtools/serialize_host_descriptions_unittest.cc:52: // Test
serializing a small forest, of this structure:
On 2017/04/19 22:05:14, dgozman wrote:
> I'd suggest less linear test to check the topological sort, if you are
> interested:
> 
> 5 -- 2 -- 4
> 0 -- 6
>   \ 1
>   \ 3

Done.

[vabr (Chromium), 2017-04-20 07:29:44]

The CQ bit was checked by vabr@chromium.org

[vabr (Chromium), 2017-04-20 07:29:44]

The patchset sent to the CQ was uploaded after l-g-t-m from
jdoerrie@chromium.org, dgozman@chromium.org
Link to the patchset: https://codereview.chromium.org/2825533002/#ps100001
(title: "non-pre-ordered test and out params")

[commit-bot: I haz the power, 2017-04-20 07:30:02]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-20 08:27:10]

CQ is committing da patch.

Bot data: {"patchset_id": 100001, "attempt_start_ts": 1492673384245380,
"parent_rev": "2cab8929074f911590ef5a1da345b5519dfc1c81", "commit_rev":
"668159776484e722ffaaad38c8201fc49e62b937"}

[commit-bot: I haz the power, 2017-04-20 08:27:18]

Description was changed from

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

The touched code also seemed to create too many scoped_refptr<DevToolsAgentHost>
instances: in cases where there is already a scoped_refptr holding an object
alive outside of the current context, it is better to use just raw pointers in
for loops and argument passing, to avoid unnecessary churn with AddRef/Release
calls.

Therefore this CL also changed for loops inside of
LocalTargetsUIHandler::SendTargets to use const scoped_refptr& (still avoids
the AddRef/Release churn when raw pointer is not an option) as well as the
argument of DevToolsTargetsUIHandler::Serialize to just a raw pointer.

BUG=712119
==========

to

==========
Introduce SerializeDictionaryForest for devtools_target_ui

Currently, LocalTargetsUIHandler::SendTargets contains a very succinct code to
create a base::Value description of a forest of DevToolsAgentHost instances.
One property of base::ListValue which made this code possible was that Values
were stored in unique_ptrs inside ListValue. In particular, passing a value to
ListValue::Append left the previously owning pointer still useful as a weak
pointer.

That property no longer holds true, because ListValue has been converted to
store Values directly in
https://crrev.com/a5676c607e107238b2d0cdd55e626c93669a92f1. This results in use
of values which have been std::moved, i.e., a kind of use-after-free. What's
worse -- this code is not tested enough for sanitizers to have caught this, and
was already seen in the wild by users of Chrome 59 and 60 as crashes.

This CL wants to achieve these goals:
* Fix the code to not to rely on implementation details of ListValue.
* Increase unit test coverage of the new code.
* Make the code more explicit and clearer.

The CL does the following to achieve the above goals:
* It introduces an explicit topological sort of the forest of
  DevToolsAgentHosts. This allows to do changes to base::Values before passing
  them inside a ListValue, so after calling ListValue::Append it does not
  matter what happens to the passed Values.
* The CL also separates the topological sort into a helper function, and adds a
  unit test for that.

The touched code also seemed to create too many scoped_refptr<DevToolsAgentHost>
instances: in cases where there is already a scoped_refptr holding an object
alive outside of the current context, it is better to use just raw pointers in
for loops and argument passing, to avoid unnecessary churn with AddRef/Release
calls.

Therefore this CL also changed for loops inside of
LocalTargetsUIHandler::SendTargets to use const scoped_refptr& (still avoids
the AddRef/Release churn when raw pointer is not an option) as well as the
argument of DevToolsTargetsUIHandler::Serialize to just a raw pointer.

BUG=712119

Review-Url: https://codereview.chromium.org/2825533002
Cr-Commit-Position: refs/heads/master@{#465948}
Committed:
https://chromium.googlesource.com/chromium/src/+/668159776484e722ffaaad38c820...
==========

[commit-bot: I haz the power, 2017-04-20 08:27:19]

Committed patchset #6 (id:100001) as
https://chromium.googlesource.com/chromium/src/+/668159776484e722ffaaad38c820...