Correct the order in which OutputDirectory and IntermediateDirectory are defined.

Correct the order in which OutputDirectory and IntermediateDirectory are
defined, so that IntDir can use the definition of OutDir by topologically
sorting references to msvs variables.

Moved topological sort to a common location and switched it to a simpler
more general depth first search version.

BUG=http://code.google.com/p/chromium/issues/detail?id=119528
TEST=shared_output
Committed: https://code.google.com/p/gyp/source/detail?r=1377

[scottmg, 2012-05-08 20:25:14]

Instead of documenting this in a test, could we instead maybe add something to
input.py to Validate that '$(OutDir)' doesn't appear in
msvs_settings.IntermediateDir at all?

http://chromiumcodereview.appspot.com/10378042/diff/5005/test/msvs/shared_out...
File test/msvs/shared_output/gyptest-shared_output.py (right):

http://chromiumcodereview.appspot.com/10378042/diff/5005/test/msvs/shared_out...
test/msvs/shared_output/gyptest-shared_output.py:8: Test demonstrating a
difference in the expansion precidence between vcbuild
typo, precedence

http://chromiumcodereview.appspot.com/10378042/diff/5005/test/msvs/shared_out...
test/msvs/shared_output/gyptest-shared_output.py:11: would expand to the value
of OutputDirectory in the project scrope.
typo, scope

http://chromiumcodereview.appspot.com/10378042/diff/5005/test/msvs/shared_out...
test/msvs/shared_output/gyptest-shared_output.py:42: # sensibly used in the
definition of IntermediateDirectory.
probably don't need this same comment 2x

[bradn, 2012-05-09 00:57:22]

Figured out a way to fix it.
(Never trust drivel from the interwebs...)
PTAL

[scottmg, 2012-05-09 02:45:41]

generally looks fine to me.

http://codereview.chromium.org/10378042/diff/7012/test/msvs/shared_output/gyp...
File test/msvs/shared_output/gyptest-shared_output.py (right):

http://codereview.chromium.org/10378042/diff/7012/test/msvs/shared_output/gyp...
test/msvs/shared_output/gyptest-shared_output.py:17: test =
TestGyp.TestGyp(workdir='workarea_shared_output', formats=['msvs'])
if there's things actually relying on this style of expansion, it'll have to
work on ninja too. generally the windows tests look like this now:

if sys.platform == 'win32':
  ... TestGyp(..., formats['msvs', 'ninja'])

[scottmg, 2012-05-09 03:23:01]

On 2012/05/09 02:45:41, scottmg wrote:
> work on ninja too

Sorry, scratch that, the ninja generator ignores IntermediateDirectory anyway.
(I'd rather use a RULE_xxx than these VS macros if possible, personally)

pylib/gyp/xcode_emulation.py does a topological sort of environment variables to
order the references properly. Would that be better than the adhoc ordering
defined here?

[gab, 2012-05-09 15:27:11]

The idea lg, see comments below.

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py
File pylib/gyp/generator/msvs.py (right):

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py...
pylib/gyp/generator/msvs.py:2638: MSBUILD_PROPERTY_ORDER = [
Does this mean we will need to add each new property a gyp user wants to add to
their build here?

i.e. I'm currently adding a new property to PropertyGroup as part of this
upcoming CL:
http://codereview.chromium.org/9701050/diff/8002/build/common.gypi

From _MSBuildPropertyRank() below it looks like any unknown property is just
sorted at the end, which is fine, but I just want to make sure this is the
intended behavior.

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py...
pylib/gyp/generator/msvs.py:2640: 'IntDir',  # IntDir is usually defined is
terms of OutDir so put it later.
typo: is => in

[bradn, 2012-05-10 01:48:52]

Ok, switched to topological sort.
PTAL

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py
File pylib/gyp/generator/msvs.py (right):

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py...
pylib/gyp/generator/msvs.py:2638: MSBUILD_PROPERTY_ORDER = [
On 2012/05/09 15:27:11, gab wrote:
> Does this mean we will need to add each new property a gyp user wants to add
to
> their build here?
> 
> i.e. I'm currently adding a new property to PropertyGroup as part of this
> upcoming CL:
> http://codereview.chromium.org/9701050/diff/8002/build/common.gypi
> 
> From _MSBuildPropertyRank() below it looks like any unknown property is just
> sorted at the end, which is fine, but I just want to make sure this is the
> intended behavior.
So I'm gonna swap this all out for the topological sort, which is the right
thing.

http://codereview.chromium.org/10378042/diff/7012/pylib/gyp/generator/msvs.py...
pylib/gyp/generator/msvs.py:2640: 'IntDir',  # IntDir is usually defined is
terms of OutDir so put it later.
On 2012/05/09 15:27:11, gab wrote:
> typo: is => in

Done.

http://codereview.chromium.org/10378042/diff/7012/test/msvs/shared_output/gyp...
File test/msvs/shared_output/gyptest-shared_output.py (right):

http://codereview.chromium.org/10378042/diff/7012/test/msvs/shared_output/gyp...
test/msvs/shared_output/gyptest-shared_output.py:17: test =
TestGyp.TestGyp(workdir='workarea_shared_output', formats=['msvs'])
On 2012/05/09 02:45:41, scottmg wrote:
> if there's things actually relying on this style of expansion, it'll have to
> work on ninja too. generally the windows tests look like this now:
> 
> if sys.platform == 'win32':
>   ... TestGyp(..., formats['msvs', 'ninja'])

So this test is assuming that output goes in msvs style locations. My
understanding from you is that ninja on windows uses a ninja style output layout
instead of reproducing msvs's layout. So I believe we don't want to run this
test under ninja on windows. I've updated the comments.

[gab, 2012-05-10 13:57:07]

lg, see comment below

http://codereview.chromium.org/10378042/diff/9005/pylib/gyp/generator/msvs.py
File pylib/gyp/generator/msvs.py (right):

http://codereview.chromium.org/10378042/diff/9005/pylib/gyp/generator/msvs.py...
pylib/gyp/generator/msvs.py:2660: if v in properties and v != node]))
It took me a little while to figure out how this works, i.e. that the edges of a
node (i.e. a property) are defined to be the properties used as variables in the
value of the given property.

This is really neat, but I think a comment would help :)!

I would also consider moving the MSVS_VARIABLE_REFERENCE regex closer to the
body of this function given it's only used locally and I had to look up and down
the file to understand what it does. I don't know much about python style though
so it's your call.

Also, is it even possible that "v == node"?! That would mean that a variable is
defined with a reference to itself... shouldn't this throw an exception rather
than simply not put an edge, it would be a nice to way to detect
self-references:
e.g. myvar = hello$(myvar)
is wrong imo

[scottmg, 2012-05-10 17:33:57]

Adding Nico as he wrote the xcode topological sort that looks like it's changed
a lot.

The VS-specific parts lgtm.

[Nico, 2012-05-10 19:20:23]

If the tests pass, I'm happy. (rsesek wrote the toposort, I just moved it from
the make generator to xcode_emulation.)

Why the implementation change? Did you benchmark the old and new implementation
and compare run times? (I don't remember toposort showing up in profiles, but I
haven't profiled in a while.)

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/generator/...
File pylib/gyp/generator/msvs.py (right):

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/generator/...
pylib/gyp/generator/msvs.py:2664: properties_ordered.reverse()
Here too you're reversing twice

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
File pylib/gyp/xcode_emulation.py (right):

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
pylib/gyp/xcode_emulation.py:982: (This is really reversed topological order).
Remove useless comment addition

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
pylib/gyp/xcode_emulation.py:999: order.reverse()
Err g.c.TS also reverses last thing. Maybe it shouldn't do that then?

[bradn, 2012-05-10 20:17:56]

I've switched to the normal definition of topological order everywhere (nodes
appear before the nodes they point to).

I haven't profiled, but the old one actually had several O(n^2) scans thru the
whole edge set. I originally was going to move it with minimal modifications.
But started making changes as I at least wanted to remove baked in assumptions
about skipping unknown nodes (make it a generic topsort). Once I started adding
the extra dicts/sets needed to fix the scans thru the edge set, mseaborn pointed
out to me that the recursive depth first version is much shorter, so I switched
to that. It's all likely moot in terms of performance as there are actually very
few edges in the cases this is being used.

PTAL

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/generator/...
File pylib/gyp/generator/msvs.py (right):

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/generator/...
pylib/gyp/generator/msvs.py:2660: if v in properties and v != node]))
On 2012/05/10 13:57:07, gab wrote:
> It took me a little while to figure out how this works, i.e. that the edges of
a
> node (i.e. a property) are defined to be the properties used as variables in
the
> value of the given property.
> 
> This is really neat, but I think a comment would help :)!
> 
Done

> I would also consider moving the MSVS_VARIABLE_REFERENCE regex closer to the
> body of this function given it's only used locally and I had to look up and
down
> the file to understand what it does. I don't know much about python style
though
> so it's your call.
> 
I see nothing in the style guide to preclude moving it closer at module scope,
so I've done that. Putting it in the function would cause it to be regenerated
each time, so I left it outside the function.

> Also, is it even possible that "v == node"?! That would mean that a variable
is
> defined with a reference to itself... shouldn't this throw an exception rather
> than simply not put an edge, it would be a nice to way to detect
> self-references:
> e.g. myvar = hello$(myvar)
> is wrong imo
I've added a comment.
There are some cases where variables are defined in terms of themselves as a way
to "append", things like PATH=$(PATH);more_paths

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/generator/...
pylib/gyp/generator/msvs.py:2664: properties_ordered.reverse()
On 2012/05/10 19:20:23, Nico wrote:
> Here too you're reversing twice
So I've moved to normal topological order everywhere called Topological (just
for sanity). But I believe I've eliminated all the double reversing.

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
File pylib/gyp/xcode_emulation.py (right):

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
pylib/gyp/xcode_emulation.py:982: (This is really reversed topological order).
On 2012/05/10 19:20:23, Nico wrote:
> Remove useless comment addition

Yeah the double reversing thing seems goofy.
I had been wary of changing return values of these functions (as there are some
other callers), but consistency would be good.
Changing..

http://chromiumcodereview.appspot.com/10378042/diff/9005/pylib/gyp/xcode_emul...
pylib/gyp/xcode_emulation.py:999: order.reverse()
On 2012/05/10 19:20:23, Nico wrote:
> Err g.c.TS also reverses last thing. Maybe it shouldn't do that then?

Yeah, I think I'll just move to forward topological order everywhere.

[gab, 2012-05-10 20:45:30]

Haven't thoroughly reviewed the new logic with forward vs reverse topo sort, but
thanks for addressing my comments.

lgtm

[Nico, 2012-05-11 14:53:44]

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/generator/make.py
File pylib/gyp/generator/make.py (right):

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/generator/make.p...
pylib/gyp/generator/make.py:1799: for k in
reversed(gyp.xcode_emulation.TopologicallySortedEnvVarKeys(env)):
When refactoring a function (gyp.xcode_emu.TopSortEnvVarKeys), try not to change
its interface. Then you don't need to change this file (and any of the other
calling sites you changed).

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/xcode_emulation.py
File pylib/gyp/xcode_emulation.py (right):

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:989: def GetEdges(node):
This function is the wrong way round. We want an edge from a to b if a is needed
to define b (i.e. "b = $a"), not when a is defined in terms of b (i.e. "a =
$b"). This function builds the reverse of the DAG that was previously used.

I have convinced myself that reverse(toposort(graph)) is the same as
toposort(revert_dag(graph)), so be reverting the result of gyp.common.TopoSort
you will get the correct result. But I think that's not obvious, so either:

1.) Change GetEdges() to build the graph the right way round

2.) Put the reverse() call into this function instead of at the various call
sites, and add a comment that points out that the the reverse of the topological
sorting on a reversed DAG is equivalent to a topological sorting on the original
DAG

[bradn, 2012-05-11 18:57:23]

PTAL

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/generator/make.py
File pylib/gyp/generator/make.py (right):

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/generator/make.p...
pylib/gyp/generator/make.py:1799: for k in
reversed(gyp.xcode_emulation.TopologicallySortedEnvVarKeys(env)):
On 2012/05/11 14:53:44, Nico wrote:
> When refactoring a function (gyp.xcode_emu.TopSortEnvVarKeys), try not to
change
> its interface. Then you don't need to change this file (and any of the other
> calling sites you changed).

So I had been "correcting" what I had perceived as an inversion of "canonical"
definitions of the directionality of edges for variable dependencies.
Some informal polling of folks around me, that my sense of  is in fact
non-universal (its about a 50% 50% split :-).
Sorry for the confusion.
As such, keeping the current function signatures makes sense.
I've switched to that and added more clarifying comments.
I've ended up keeping the edge directions flipped from before (but hid
internally with a reverse) as its easier to find all variable references in a
one string.

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/xcode_emulation.py
File pylib/gyp/xcode_emulation.py (right):

http://codereview.chromium.org/10378042/diff/10014/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:989: def GetEdges(node):
On 2012/05/11 14:53:44, Nico wrote:
> This function is the wrong way round. We want an edge from a to b if a is
needed
> to define b (i.e. "b = $a"), not when a is defined in terms of b (i.e. "a =
> $b"). This function builds the reverse of the DAG that was previously used.
> 
> I have convinced myself that reverse(toposort(graph)) is the same as
> toposort(revert_dag(graph)), so be reverting the result of gyp.common.TopoSort
> you will get the correct result. But I think that's not obvious, so either:
> 
> 1.) Change GetEdges() to build the graph the right way round
> 
> 2.) Put the reverse() call into this function instead of at the various call
> sites, and add a comment that points out that the the reverse of the
topological
> sorting on a reversed DAG is equivalent to a topological sorting on the
original
> DAG

Done.

[Nico, 2012-05-11 19:03:34]

Nit is optional. The comment might be why the mac try result is red.

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation.py
File pylib/gyp/xcode_emulation.py (right):

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:964: for k in
TopologicallySortedEnvVarKeys(expansions):
You removed a reversed() here. That should probably return?

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:974: env such that key2 is after key1 in L if
env[key2] refers to env[key1].
Undo comment change

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:997: order =
gyp.common.TopologicallySorted(env.keys(), GetEdges)
nit: i'd just write `return reversed(gyp.common.TopoSort...`

[bradn, 2012-05-11 20:10:31]

PTAL

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation.py
File pylib/gyp/xcode_emulation.py (right):

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:964: for k in
TopologicallySortedEnvVarKeys(expansions):
On 2012/05/11 19:03:34, Nico wrote:
> You removed a reversed() here. That should probably return?

Done.
Ah yes, that's likely it.

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:974: env such that key2 is after key1 in L if
env[key2] refers to env[key1].
On 2012/05/11 19:03:34, Nico wrote:
> Undo comment change

? this has no diff now?

http://codereview.chromium.org/10378042/diff/14025/pylib/gyp/xcode_emulation....
pylib/gyp/xcode_emulation.py:997: order =
gyp.common.TopologicallySorted(env.keys(), GetEdges)
On 2012/05/11 19:03:34, Nico wrote:
> nit: i'd just write `return reversed(gyp.common.TopoSort...`

So I'm generally avoiding reversed() when its stuffed away because unfortunately
reversed(reversed(x)) gives an error because reversed() returns an iterator
(which itself cannot be reversed). (Also the above reintroduction of reversed
precludes this.)

[Nico, 2012-05-11 20:16:23]

Lgtm if tests pass.

Thanks for humoring me :-)