Re: Partial vs. strict weak ordering (was Re: [PATCH] Postinstall script ordering in setup - take 3)

2003-03-16 Thread Igor Pechtchanski 
Rob,

On 17 Mar 2003, Robert Collins wrote:

> On Mon, 2003-03-17 at 06:51, Igor Pechtchanski wrote:
>
> > STL containers won't choke, as they only need a partial order, AFAIU.
> > The "fail" simply means it's not a strict weak ordering.
>
> They can and will do the wrong thing.

You're right, of course.  My statement above was too general.  Let me try
again:

STL containers that require LessThanComparable (i.e., partial ordering)
will not choke.  Sorted Associative Containers that require
StrictWeakOrdering *will* fail (because the relation I defined isn't).

I thought that only LessThanComparable is needed for the "sort()" function
of the list container.  Upon rereading
, however, I realized that the
sort() function does require a strict weak ordering (but doesn't refer to
StrictWeakOrdering, but rather to LessThanComparable).
I'm a bit confused now.

> because it's not a strict weak ordering, if we have:
> [snip]
> This is because your ordering requires direct comparison to all members
>
> I don't have time right now to go into the maths above, will do so
> later.
>
> Rob

I believe I agreed before that the operator I defined is not a strict weak
ordering.  Now it seems that that's what's needed, even for the list's
sort().  I'll need to think on that one some more.
Igor
P.S. FYI, sort() called with my operator< seems to do the right thing,
surprisingly, producing a topologically-ordered list...  Go figure...
-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-16 Thread Igor Pechtchanski 
On 17 Mar 2003, Robert Collins wrote:

> On Mon, [EMAIL PROTECTED]:13, Igor Pechtchanski wrote:
>
> > > And for clarity: my suggested tweak is also not sufficient to provide a
> > > weak ordering.
> > > Rob
> >
> > Rob,
> >
> > Your suggested tweak provides a total ordering.  The "unordered(x,y)"
> > [!(x < y) && !(y < x)] relation is false for any x != y [since either
> > (x < y) or (y < x) always holds].
>
> For my example, yes. The problem is when you introduce z.
>
> >   So all equivalence classes have one
> > element: "unordered(x,x)" is always true.  You get transitivity trivially,
> > as "unordered(x,y) && unordered(y,z)" is only true if x == y == z, and
> > then you also have "unordered(x,z)".
>
> But: we break the ordering transitivity.
> > Transitivity
> > x < y and y < z implies x < z [3]
>
> y:= foo: gam
> x:= gam
> z:= bar: foo
>
> both our operators give
> x < y && y < z && !x < z
> (dep)(dep)(alpha)
>
> which isn't transitive.
> Rob

Umm, I already replied to that in
, but I'll repeat
it here:

My operator< *is* transitive, because of the "propagateDependences"
step...

So is yours (since you only changed mine).  Neither is transitive without
that step.  FYI, I couldn't think of a better (linear complexity) way of
providing transitivity.  Suggestions welcome.
Igor
-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-16 Thread Robert Collins 
On Mon, 2003-03-17 at 07:26, Robert Collins wrote:

> > Transitivity
> > x < y and y < z implies x < z [3]
> 
> y:= foo: gam
> x:= gam
> z:= bar: foo
> 
> both our operators give
> x < y && y < z && !x < z
> (dep)(dep)(alpha)

and !x < z for the dependency only < operator too.

> which isn't transitive.

Rob
-- 
GPG key available at: .


signature.asc
Description: This is a digitally signed message part

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-16 Thread Robert Collins 
On Mon, 2003-03-17 at 07:13, Igor Pechtchanski wrote:

> > And for clarity: my suggested tweak is also not sufficient to provide a
> > weak ordering.
> > Rob
> 
> Rob,
> 
> Your suggested tweak provides a total ordering.  The "unordered(x,y)"
> [!(x < y) && !(y < x)] relation is false for any x != y [since either
> (x < y) or (y < x) always holds].

For my example, yes. The problem is when you introduce z.

>   So all equivalence classes have one
> element: "unordered(x,x)" is always true.  You get transitivity trivially,
> as "unordered(x,y) && unordered(y,z)" is only true if x == y == z, and
> then you also have "unordered(x,z)".

But: we break the ordering transitivity.
> Transitivity
> x < y and y < z implies x < z [3]

y:= foo: gam
x:= gam
z:= bar: foo

both our operators give
x < y && y < z && !x < z
(dep)(dep)(alpha)

which isn't transitive.

Rob

-- 
GPG key available at: .


signature.asc
Description: This is a digitally signed message part

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-16 Thread Robert Collins 
On Mon, 2003-03-17 at 07:13, Igor Pechtchanski wrote:

> > And for clarity: my suggested tweak is also not sufficient to provide a
> > weak ordering.
> > Rob
> 
> Rob,
> 
> Your suggested tweak provides a total ordering.  The "unordered(x,y)"
> [!(x < y) && !(y < x)] relation is false for any x != y [since either
> (x < y) or (y < x) always holds].  So all equivalence classes have one
> element: "unordered(x,x)" is always true.  You get transitivity trivially,
> as "unordered(x,y) && unordered(y,z)" is only true if x == y == z, and
> then you also have "unordered(x,z)".
>   Igor

It doesn't. It fails because it doesn't obey the requirements for an
equivalence class. The ordering it provides is 100% dependent on the
order of the comparisons. Thats fine when two elements are in the same
equivalence class, but this will shuffle elements outside such classes.

Rob

-- 
GPG key available at: .


signature.asc
Description: This is a digitally signed message part

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-16 Thread Igor Pechtchanski 
On 16 Mar 2003, Robert Collins wrote:

> On Sun, [EMAIL PROTECTED]:48, Robert Collins wrote:
> > On Sat, [EMAIL PROTECTED]:33, Igor Pechtchanski wrote:
> > > Rob,
> > > > Your operator > and < appear to have a problem.
> > > >
> > > > foo: bar
> > > > gam: bar
> > > >
> > > > foo > gam= false
> > > > gam < foo= false
> > > > gam == foo   = false.
> > > >
> > > > I'd expect stl associative containers to choke on that.
> >
> > > Not really.  I read up on that specifically.  stl containers only need a
> > > *partial* order.  What you're suggesting will create a total order.  Not
> > > an error, but overkill.  The sort function is supposed to be stable and
> > > keep the original order if the lessThan relation is undefined.  See
> > > 
>
> And for clarity: my suggested tweak is also not sufficient to provide a
> weak ordering.
> Rob

Rob,

Your suggested tweak provides a total ordering.  The "unordered(x,y)"
[!(x < y) && !(y < x)] relation is false for any x != y [since either
(x < y) or (y < x) always holds].  So all equivalence classes have one
element: "unordered(x,x)" is always true.  You get transitivity trivially,
as "unordered(x,y) && unordered(y,z)" is only true if x == y == z, and
then you also have "unordered(x,z)".
Igor
-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune

Partial vs. strict weak ordering (was Re: [PATCH] Postinstall script ordering in setup - take 3)

2003-03-16 Thread Igor Pechtchanski 
On 16 Mar 2003, Robert Collins wrote:

> On Sat, 2003-03-15 at 09:33, Igor Pechtchanski wrote:
> > Rob,
> > > Your operator > and < appear to have a problem.
> > >
> > > foo: bar
> > > gam: bar
> > >
> > > foo > gam= false
> > > gam < foo= false
> > > gam == foo   = false.
> > >
> > > I'd expect stl associative containers to choke on that.
>
> > Not really.  I read up on that specifically.  stl containers only need a
> > *partial* order.  What you're suggesting will create a total order.  Not
> > an error, but overkill.  The sort function is supposed to be stable and
> > keep the original order if the lessThan relation is undefined.  See
> > 
>
> =
>
> Consider the relation !(x < y) && !(y < x). If this relation is
> transitive (that is, if !(x < y) && !(y < x) && !(y < z) && !(z < y)
> implies !(x < z) && !(z < x)), then it satisfies the mathematical
> definition of an equivalence relation. In this case, operator< is a
> strict weak ordering.
>
> If operator< is a strict weak ordering, and if each equivalence class
> has only a single element, then operator< is a total ordering.
>
> Valid expressions
>Name
> Expression
> Type requirements
>Return type
> Less
> x < y
>
> Convertible to
> bool
> Greater
> x > y
>
> Convertible to
> bool
> Less or equal
> x <= y
>
> Convertible to
> bool
> Greater or equal
> x >= y
>
> Convertible to
> bool
> Expression semantics
>  Name
>   Expression
>  Precondition
>   Semantics
> Postcondition
> Less
> x < y
> x and y are in
> the domain of
> <
>
> Greater
> x > y
> x and y are in
> the domain of
> <
> Equivalent to
> y < x [1]
>
> Less or equal
> x <= y
> x and y are in
> the domain of
> <
> Equivalent to
> !(y < x) [1]
>
> Greater or
> equal
> x >= y
> x and y are in
> the domain of
> <
> Equivalent to
> !(x < y) [1]
>
> Complexity guarantees
> Invariants
> Irreflexivity
> x < x must be false.
> Antisymmetry
> x < y implies !(y < x) [2]
> Transitivity
> x < y and y < z implies x < z [3]
> Models
>   * int
>
> Notes
> [1] Only operator< is fundamental; the other inequality operators are
> essentially syntactic sugar.
>
> [2] Antisymmetry is a theorem, not an axiom: it follows from
> irreflexivity and transitivity.
>
> [3] Because of irreflexivity and transitivity, operator< always
> satisfies the definition of a partial ordering. The definition of a
> strict weak ordering is stricter, and the definition of a total ordering
> is stricter still.
> =
> foo: bar
> gam: bar
>
> gives
>
> foo > bar
> gam > bar
> from above:
> Axiom: ! (foo < gam) && (! gam < foo)
> Axiom: ! (foo < gam) && (! gam < foo) && !(gam < z) && !(z < gam)
> is
> !(foo < z) && (!z < foo)
> ever false?
> now, foo is < z when z depends on foo. !(foo < z) means z does not
> depend on foo.
> what do we know about z?
> z does not depend on gam. !(gam < z)
> gam does not depend on z  !(z < gam)
> can z depend on foo and not on gam?
> let z depend on foo:
> so: z > foo.
>
> now, !(gam < z) is still true. !(z < gam) is still true.
> !(foo < z) is false.

Yes.  It reads better this way: !(x < y) && !(y < x) === unordered(x,y)
Reflexivity: unordered(x,x)
Transitivity: unordered(x,y) && unordered(y,z) => unordered(x,z)

And I agree that "unordered(x,y)" defined in terms of my operator< is
*not* transitive.  Thus, my operator< is not a strict weak ordering.  It
*is*, however, a partial ordering (see note [3] above).

> Your operator < is not a equivalence relation.

Now, operator< is *never* an equivalence relation (because it's
irreflexive, rather than reflexive).  My operator< *is* transitive,
because of the "propagateDependences" step...

> STL Containers will choke.
> You fail on transitivity BTW.
> Rob

STL containers won't choke, as they only need a partial order, AFAIU.
The "fail" simply means it's not a strict weak ordering.

Now, what my operator< *does* fail on is irreflexivity (in case there are
circular dependences).  I'll need to fix that (it's a TODO).
Igor
-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-15 Thread Robert Collins 
Robert Collins wrote:
And for clarity: my suggested tweak is also not sufficient to provide a
weak ordering.
And another thing to be clear on: a weak ordering is required for 
correct STL behaviour, and without that, the dependencies logic is 
borken and not ready for merging. (irrespective of short/long term 
solution etc etc)

Rob

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-15 Thread Robert Collins 
On Sun, 2003-03-16 at 08:48, Robert Collins wrote:
> On Sat, 2003-03-15 at 09:33, Igor Pechtchanski wrote:
> > Rob,
> > > Your operator > and < appear to have a problem.
> > >
> > > foo: bar
> > > gam: bar
> > >
> > > foo > gam= false
> > > gam < foo= false
> > > gam == foo   = false.
> > >
> > > I'd expect stl associative containers to choke on that.
> 
> > Not really.  I read up on that specifically.  stl containers only need a
> > *partial* order.  What you're suggesting will create a total order.  Not
> > an error, but overkill.  The sort function is supposed to be stable and
> > keep the original order if the lessThan relation is undefined.  See
> > 

And for clarity: my suggested tweak is also not sufficient to provide a
weak ordering.

Rob
-- 
Robert Collins <[EMAIL PROTECTED]>


signature.asc
Description: This is a digitally signed message part

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-15 Thread Robert Collins 
On Sat, 2003-03-15 at 09:33, Igor Pechtchanski wrote:
> Rob,
> > Your operator > and < appear to have a problem.
> >
> > foo: bar
> > gam: bar
> >
> > foo > gam= false
> > gam < foo= false
> > gam == foo   = false.
> >
> > I'd expect stl associative containers to choke on that.

> Not really.  I read up on that specifically.  stl containers only need a
> *partial* order.  What you're suggesting will create a total order.  Not
> an error, but overkill.  The sort function is supposed to be stable and
> keep the original order if the lessThan relation is undefined.  See
> 

=

Consider the relation !(x < y) && !(y < x). If this relation is
transitive (that is, if !(x < y) && !(y < x) && !(y < z) && !(z < y)
implies !(x < z) && !(z < x)), then it satisfies the mathematical
definition of an equivalence relation. In this case, operator< is a
strict weak ordering. 

If operator< is a strict weak ordering, and if each equivalence class
has only a single element, then operator< is a total ordering.


Valid expressions
   Name
Expression
Type requirements
   Return type
Less
x < y
 
Convertible to
bool
Greater
x > y
 
Convertible to
bool
Less or equal
x <= y
 
Convertible to
bool
Greater or equal
x >= y
 
Convertible to
bool
Expression semantics
 Name
  Expression
 Precondition
  Semantics
Postcondition
Less
x < y
x and y are in
the domain of
<
 
 
Greater
x > y
x and y are in
the domain of
<
Equivalent to
y < x [1]
 
Less or equal
x <= y
x and y are in
the domain of
<
Equivalent to
!(y < x) [1]
 
Greater or
equal
x >= y
x and y are in
the domain of
<
Equivalent to
!(x < y) [1]
 
Complexity guarantees
Invariants
Irreflexivity
x < x must be false.
Antisymmetry
x < y implies !(y < x) [2]
Transitivity
x < y and y < z implies x < z [3]
Models
  * int

Notes
[1] Only operator< is fundamental; the other inequality operators are
essentially syntactic sugar.

[2] Antisymmetry is a theorem, not an axiom: it follows from
irreflexivity and transitivity.

[3] Because of irreflexivity and transitivity, operator< always
satisfies the definition of a partial ordering. The definition of a
strict weak ordering is stricter, and the definition of a total ordering
is stricter still.
=
foo: bar
gam: bar

gives
 
foo > bar
gam > bar
from above:
Axiom: ! (foo < gam) && (! gam < foo)
Axiom: ! (foo < gam) && (! gam < foo) && !(gam < z) && !(z < gam)

is  
!(foo < z) && (!z < foo)
ever false?
now, foo is < z when z depends on foo. !(foo < z) means z does not
depend on foo.
what do we know about z?
z does not depend on gam. !(gam < z)
gam does not depend on z  !(z < gam)
can z depend on foo and not on gam?
let z depend on foo:
so: z > foo.

now, !(gam < z) is still true. !(z < gam) is still true.
!(foo < z) is false.

Your operator  < is not a equivalence relation.

STL Containers will choke.

You fail on transitivity BTW.

Rob

-- 
Robert Collins <[EMAIL PROTECTED]>



signature.asc
Description: This is a digitally signed message part

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-14 Thread Igor Pechtchanski 
Rob,

I have to run now, so I'll reply in more detail tomorrow.  One quick
comment below.

On 15 Mar 2003, Robert Collins wrote:

> The logic in here looks almost identical to that in
> packageversion::set_requirements. I don't want to add near-duplicate
> code if we can avoid it. Perhaps extracting the core for both to a
> convenience class?
>
> Your operator > and < appear to have a problem.
>
> foo: bar
> gam: bar
>
> foo > gam= false
> gam < foo= false
> gam == foo   = false.
>
> I'd expect stl associative containers to choke on that.
>
> I suggest you do
> {
>   /* we are greater than any dependency of ours */
>   if (_dependencies.find(&f) != _dependencies.end())
> return true;
>   return _path > f._path;
> }

Not really.  I read up on that specifically.  stl containers only need a
*partial* order.  What you're suggesting will create a total order.  Not
an error, but overkill.  The sort function is supposed to be stable and
keep the original order if the lessThan relation is undefined.  See


> Thanks again for all the work you've put into this.
>
> I've actually got some time today (gasp!), so I'm going to review the
> current install script ordering - I'd like to apply your work to the
> package dependency script ordering, which is currently not implemented.
>
> Rob

Go ahead.  If you need my input, feel free to send chunks of design/code
to the list; I'll reply to them and to the rest of this message tomorrow.
Igor
-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune

Re: [PATCH] Postinstall script ordering in setup - take 3

2003-03-14 Thread Robert Collins 
On Sat, 2003-03-15 at 05:06, Igor Pechtchanski wrote:

> Ok.  Here's that alternative, more reasonably implemented, and *tested*
> this time :-) (at least as far as reading files, sorting them, and
> executing scripts is concerned).  The dependence-extraction mechanism
> still needs to be verified, though.  Comments and suggestions for
> improvement are welcome.
>   Igor
> ==
> ChangeLog:
> 2003-03-03  Igor Pechtchanski <[EMAIL PROTECTED]>

I'd like you do keep the class declaration free of code. It's fine to
have it in the .cc file if it's really trivial an private, but even then
can you put the implementations outside the class declaration. (With one
exception: one-liners.

>   * postinstall.cc (RunFindVisitor::executeAll): New
>   member function that propagates script dependencies,
>   topologically sorts the script list, and then executes
>   the scripts (via other calls).
>   (RunFindVisitor::visitFile): Change to add script to
>   list instead of running it immediately.
>   (RunFindVisitor::files): New member variable.
>   (RunFindVisitor::checkAndLogMissingDependencies): New
>   member function.
>   (FileDesc): New class that extracts and stores
>   dependencies from a script file.

The logic in here looks almost identical to that in
packageversion::set_requirements. I don't want to add near-duplicate
code if we can avoid it. Perhaps extracting the core for both to a
convenience class?

Your operator > and < appear to have a problem.

foo: bar
gam: bar

foo > gam= false
gam < foo= false
gam == foo   = false.

I'd expect stl associative containers to choke on that.

I suggest you do
{
  /* we are greater than any dependency of ours */
  if (_dependencies.find(&f) != _dependencies.end())
return true;
  return _path > f._path;
}

this
+  const char *err = strerror (errno);
+  if (!err)
+   err = "(unknown error)";

could be usefull extracted so that we can do
  String const errorString ( StringError(errno)); 
and always get back a string.


>   (DEPEND_STR): New #define.

BUFLEN should be a static const member of the class.

>   (do_postinstall): Add executeAll() call.

Thanks again for all the work you've put into this.

I've actually got some time today (gasp!), so I'm going to review the
current install script ordering - I'd like to apply your work to the
package dependency script ordering, which is currently not implemented.

Rob

-- 
GPG key available at: .


signature.asc
Description: This is a digitally signed message part

[PATCH] Postinstall script ordering in setup - take 3

2003-03-14 Thread Igor Pechtchanski 
On 5 Mar 2003, Robert Collins wrote:

> [snip]
> Any, as I don't have time to complete implementing the dpkg or rpm
> behaviour in this regard for setup until the end of the current ice age,
> it would be silly to not let in a reasonably implemented alternative.
>
> Thus - I think this is a short term bandaid, because it increases work,
> not decreases it, and there is a better solution out there, as shown by
> the other package managers.
>
> Rob

Ok.  Here's that alternative, more reasonably implemented, and *tested*
this time :-) (at least as far as reading files, sorting them, and
executing scripts is concerned).  The dependence-extraction mechanism
still needs to be verified, though.  Comments and suggestions for
improvement are welcome.
Igor
==
ChangeLog:
2003-03-03  Igor Pechtchanski <[EMAIL PROTECTED]>

* postinstall.cc (RunFindVisitor::executeAll): New
member function that propagates script dependencies,
topologically sorts the script list, and then executes
the scripts (via other calls).
(RunFindVisitor::visitFile): Change to add script to
list instead of running it immediately.
(RunFindVisitor::files): New member variable.
(RunFindVisitor::checkAndLogMissingDependencies): New
member function.
(FileDesc): New class that extracts and stores
dependencies from a script file.
(DEPEND_STR): New #define.
(do_postinstall): Add executeAll() call.

-- 
http://cs.nyu.edu/~pechtcha/
  |\  _,,,---,,_[EMAIL PROTECTED]
ZZZzz /,`.-'`'-.  ;-;;,_[EMAIL PROTECTED]
 |,4-  ) )-,_. ,\ (  `'-'   Igor Pechtchanski
'---''(_/--'  `-'\_) fL a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

Oh, boy, virtual memory! Now I'm gonna make myself a really *big* RAMdisk!
  -- /usr/games/fortune
Index: postinstall.cc
===
RCS file: /cvs/cygwin-apps/setup/postinstall.cc,v
retrieving revision 2.9
diff -u -p -r2.9 postinstall.cc
--- postinstall.cc  19 May 2002 03:07:51 -  2.9
+++ postinstall.cc  14 Mar 2003 17:40:09 -
@@ -26,6 +26,144 @@ static const char *cvsid =
 #include "mount.h"
 #include "script.h"
 #include "FindVisitor.h"
+#include "io_stream.h"
+#include "resource.h"
+#include "msg.h"
+#include "log.h"
+#include 
+#include 
+#include 
+
+#define DEPEND_STR "depends on: "
+#define BUFLEN 500
+
+class FileDesc
+{
+public:
+  FileDesc(String const &filename);
+  String const &path() { return _path; }
+  std::set const & dependencies() { return _dependencies; }
+  bool addDependency(FileDesc *dep) {
+return _dependencies.insert(dep).second;
+  }
+  bool addDependency(String const &deps) {
+// TODO: free unused map entries
+return addDependency(create(deps));
+  }
+  void propagateDependencies() {
+// TODO: detect circular dependencies
+if (_mark) return;
+_mark = true;
+for (std::set::iterator i = _dependencies.begin();
+i != _dependencies.end();
+++i)
+  {
+   (*i)->propagateDependencies();
+   for (std::set::iterator d = (*i)->_dependencies.begin();
+d != (*i)->_dependencies.end();
+++d)
+ addDependency(*d);
+  }
+  }
+  bool operator == (FileDesc const &f) const {
+return _path == f._path && _dependencies == f._dependencies;
+  }
+  bool operator > (FileDesc &f) {
+return (_dependencies.find(&f) != _dependencies.end());
+  }
+  bool operator < (FileDesc &f) {
+return (f > *this);
+  }
+
+  static FileDesc *create(String const &path) {
+FileDesc *&fd = fdmap[path];
+if (fd == NULL) fd = new FileDesc(path);
+return fd;
+  }
+private:
+  String _path;
+  std::set _dependencies;
+  bool _mark;
+  char _buf[BUFLEN];
+  char const *commentString();
+  char *readDependencyLine();
+
+  static std::map fdmap;
+};
+
+char const *FileDesc::commentString()
+{
+  char const *ext = strrchr (_path.cstr_oneuse(), '.');
+  char const *cmt = NULL;
+  if (strcasecmp(ext, ".sh") == 0)
+cmt = "#";
+  else if (strcasecmp(ext, ".bat") == 0)
+cmt = "rem";
+  return cmt;
+}
+
+#define WHITESPACE " \t"
+
+char *FileDesc::readDependencyLine()
+{
+  io_stream *f = io_stream::open(String("cygfile://") + _path, "rt");
+  if (!f)
+{
+  const char *err = strerror (errno);
+  if (!err)
+   err = "(unknown error)";
+  log (LOG_TIMESTAMP, String("error: unable to open script ") +
+  _path + " for reading: " + err);
+  return NULL;
+}
+
+  // Read first line after shbang (if any)
+  f->gets(_buf, BUFLEN);
+  if (*_buf == '#')
+{
+  char *bang = strtok(_buf+1, WHITESPACE);
+  if (bang != NULL && *bang == '!')
+   f->gets(_buf, BUFLEN);
+  else
+*(bang+strlen(bang)) = ' ';
+}
+
+  delete f;
+
+  // Check if a dependency line
+  char