Boost logo

Boost-Build :

From: David Abrahams (dave_at_[hidden])
Date: 2005-06-03 09:08:31

Vladimir Prus <ghost_at_[hidden]> writes:

> On Friday 03 June 2005 15:50, David Abrahams wrote:
>> >> Does this finally allow the algorithm of
>> >> tools/build/v2/ to be used?
>> >
>> > I'd suspect that no. Unless I forgot something, my change is in exactly
>> > opposite direction. The, 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.

Huh? When do generators that require properties ever get used then?

> 3. Based on user-provided generator "overrides", remove some
> generators.

This is pretty vague. I don't know what this means.

> 4. Run the remaining. If they return different results, error out.

What this means is also not very clear.

>> 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.

Probably to you. Try explaining them so that I can understand them.
Then try explaining them to someone who doesn't have the background of
exposure to BBv2 concepts that I have.

>> 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
> shorter.

Yes, but my scheme also detects ambiguities, because it returns all
the possible paths to the goal in best-to-worst order. I don't happen
to agree that an ambiguity in such a case should always be reported as
a problem. If I have a quickbook document and want it converted to a
PDF, I probably don't care which path the system takes to get there
(e.g. going through LaTeX or FOP), at least not initially. I would at
least want the system to do something "smart" and I might very well be
satisfied with whatever it comes up with. Asking the user to
intervene in such cases is just inconvenient and has no real advantage.

With my scheme, if the user wants to hear about it in all cases where
there is more than one path to the goal, it's easy enough to tell her.
You just ask for the best 2 paths, and if you get a 2nd one, you
report it unconditionally instead of only complaining when the first 2
paths have the same rank. That's a more ambiguous case that I would
always want to report unless the user explicitly asked me to be quiet
about it.

Dave Abrahams
Boost Consulting

Boost-Build list run by bdawes at, david.abrahams at, gregod at, cpdaniel at, john at