GN: (HeaderChecker) Allow any chain to forward direct dependent configs.

GN: (HeaderChecker) Allow any chain to forward direct dependent configs.

When finding a dependency chain, the header check will now prefer chains which
forward direct-dependent configs if the target which provides a header has
one. Previously an error would be produced because the chain which was found
did not forward configs, even though another chain did.

A breadth-first search is used instead of a depth-first search because short
chains are more likely to be intended by the author, and make for both less
work and clearer diagnostic messages.

This reduces the size of 'gn check' output on the chromium tree and the time
to execute. (Output directed to 'wc -l' and /dev/null, respectively.)

  Before: 104685 lines, 542.36s user, 35.573s total
  After: 36977 lines, 7.10s user, 1.526s total

Manual inspection reveals that the line reduction appears to be from the
removal of spurious errors when IsDependencyOf selected an indirect chain
which does not forward direct-dependent configs, even though a direct
dependency existed. (About 7 cases were examined manually; sheer volume makes
full manual verification infeasible.)

BUG=391505
TEST=HeaderCheckerTest, manual

Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=288110

[brettw, 2014-07-30 22:26:14]

This looks really cool, sorry I haven't had a chance to do this yet since this
week has been distracting and this type of changes requires some thought. Will
try to get to it tomorrow.

[jbroman, 2014-07-30 23:13:56]

On 2014/07/30 22:26:14, brettw wrote:
> This looks really cool, sorry I haven't had a chance to do this yet since this
> week has been distracting and this type of changes requires some thought. Will
> try to get to it tomorrow.

No problem. There's no real urgency, and I share your desire to be thorough.

[brettw, 2014-07-31 20:50:49]

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker.cc
File tools/gn/header_checker.cc (right):

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker....
tools/gn/header_checker.cc:412: // This maps targets to the target which
receives dependent configs from it.
I'm a bit confused about this function. Rather than have me stare at it some
more, let's try to comment it so I don't have to...

The breadcrumbs maps one target to another target, which I find surprising and
could use some explanation. I also think a quick high-level overview of how the
algorithm works above the work queue declaration might be nice.

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker....
tools/gn/header_checker.cc:416: search_from, static_cast<const Target*>(NULL)));
I see you add this to make the reconstruction step below terminate, but it would
be nice if this was covered in the above comments.

[jbroman, 2014-07-31 22:05:37]

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker.cc
File tools/gn/header_checker.cc (right):

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker....
tools/gn/header_checker.cc:412: // This maps targets to the target which
receives dependent configs from it.
On 2014/07/31 20:50:49, brettw wrote:
> I'm a bit confused about this function. Rather than have me stare at it some
> more, let's try to comment it so I don't have to...
> 
> The breadcrumbs maps one target to another target, which I find surprising and
> could use some explanation. I also think a quick high-level overview of how
the
> algorithm works above the work queue declaration might be nice.

It maps targets to their predecessor in a shortest path from search_from.
e.g. if the entire dependency graph is: search_from -> T1 -> T2 -> search_for

Then breadcrumbs will ultimately be { search_for -> T2,  T2 -> T1, T1 ->
search_from }.

Added a comment which I hope clarifies things. I think working in Blink has
messed up my threshold for commenting. :)

https://codereview.chromium.org/424133002/diff/20001/tools/gn/header_checker....
tools/gn/header_checker.cc:416: search_from, static_cast<const Target*>(NULL)));
On 2014/07/31 20:50:49, brettw wrote:
> I see you add this to make the reconstruction step below terminate, but it
would
> be nice if this was covered in the above comments.

It's unnecessarily clever. I can just make getting back to search_from the loop
exit condition, and then explicitly push search_from at the end. No need for a
sentinel that way. :)

[brettw, 2014-08-06 22:15:38]

lgtm

[jbroman, 2014-08-07 01:24:03]

The CQ bit was checked by jbroman@chromium.org

[commit-bot: I haz the power, 2014-08-07 01:25:09]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/jbroman@chromium.org/424133002/100001

[commit-bot: I haz the power, 2014-08-07 03:39:12]

FYI, CQ is re-trying this CL (attempt #1).
The failing builders are:
  chromium_presubmit on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)
  linux_chromium_chromeos_rel_swarming on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  ios_rel_device_ninja on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_rel_device_ni...)
  mac_chromium_rel_swarming on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)
  win8_chromium_rel on tryserver.chromium.win
(http://build.chromium.org/p/tryserver.chromium.win/builders/win8_chromium_rel...)
  win_chromium_x64_rel on tryserver.chromium.win
(http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)

[commit-bot: I haz the power, 2014-08-07 03:44:00]

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

[commit-bot: I haz the power, 2014-08-07 03:44:02]

Try jobs failed on following builders:
  chromium_presubmit on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)
  linux_chromium_chromeos_rel_swarming on tryserver.chromium.linux
(http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  ios_rel_device_ninja on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_rel_device_ni...)
  mac_chromium_rel_swarming on tryserver.chromium.mac
(http://build.chromium.org/p/tryserver.chromium.mac/builders/mac_chromium_rel_...)
  win8_chromium_rel on tryserver.chromium.win
(http://build.chromium.org/p/tryserver.chromium.win/builders/win8_chromium_rel...)

[jbroman, 2014-08-07 13:41:40]

The CQ bit was checked by jbroman@chromium.org

[commit-bot: I haz the power, 2014-08-07 13:43:16]

CQ is trying da patch. Follow status at
 https://chromium-status.appspot.com/cq/jbroman@chromium.org/424133002/120001

[commit-bot: I haz the power, 2014-08-07 16:28:10]

FYI, CQ is re-trying this CL (attempt #1).
The failing builders are:
  win_chromium_rel on tryserver.chromium.win
(http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel/...)

[commit-bot: I haz the power, 2014-08-07 19:32:07]

Change committed as 288110