From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-06-03 07:42:18
On Friday 03 June 2005 15:50, David Abrahams wrote:
> >> Does this finally allow the algorithm of
> >> tools/build/v2/generators_prototype.py to be used?
> > I'd suspect that no. Unless I forgot something, my change is in exactly
> > opposite direction. The generators_prototype.py, IIRC, tries to use A*
> > search, or some other heuristic search to find the "best" transformation.
> > The problem with that, in my opinion, is that it would be very hard to
> > tune those heuristic in a way that always produces results that are
> > intuitive for the user. Of course, I can be wrong.
> That's not what I mean by "allow," and I think you _are_ wrong in this
> case. Right now *you* have a heuristic search that tries to find the
> "best" transformation, for some definition of "best." That can't be
> any more intuitive for the user than what I've proposed, in part
> because IIUC the heuristic still contains arbitrary assymmetries, even
> though you just eliminated one.
I think I've removed all of heuristics. The search now works this way:
1. Find all generators for the requested type
2. Eliminate those which required properties.
3. Based on user-provided generator "overrides", remove some generators.
4. Run the remaining. If they return different results, error out.
> What I meant by "allow" was that the argument you gave for why the
> current heuristic was the right one was based on not having to write
> the explicit WD->CPP generator. To use my heuristic, writing another
> generator was needed.
> No transformation ranking heuristic will be intuitive for all users in
> all cases (you should see some of the problems the CWG has come up
> with in the rules for ordering partial specializations), but at least
> if there's a system that is regular and can be explained, users will
> eventually understand why it's making the choices it is, and will
> understand what transformations they might need to add to get it to
> act the way they want.
I think the above rules are as simple as it can get.
> My system is complicated to implement, but the results it produces are
> simple: it gives you the transformation sequence that produces the
> fewest total number of transformations. That makes it easy to
> understand when the system chooses a particular sequence, and if you
> want a different sequence, it's also easy to do: you just provide a
> "shortcut" transformation that eliminates at least one step in the
> graph, e.g. if the graph contains
> A -> B -> C
> you can just add
> A -> C
Yes, I understand that. What worries me that is fewest *total* number of
transformations might not detect ambiguities at all. Basically, if you want
to create FOOBAR from cpp, and there are two different generators that can
create FOOBAR, then I think this should be reported as ambiguity. Your scheme
can select one of those generators if the transformation chain via it is
> > My change, OTOH, removes quite a bit of smarts from the generator
> > search. Some cases which magically worked before no longer work and
> > require explicit disambiguation. That's extra work, but reduces core
> > algorithm complexity and avoids surprises.
> If you can document it in such a way that a user can understand how it
> works, that's fine.
I'll try to update comments in generators.jam, for a start.
-- Vladimir Prus http://vladimir_prus.blogspot.com Boost.Build V2: http://boost.org/boost-build2
Boost-Build list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk