Re: [jamboost] Building the dependency graph

From: Vladimir Prus (ghost_at_[hidden])
Date: 2002-01-09 11:26:48

[After making several somewhat minor remarks, I'll try to state my overall 
view of the problem -- the most interesting part of this message is in the 
end!]

David Abrahams wrote:
> > 1. Why do we need hierarchy? Aren't all transformation between leaf
> > vertices
> > in it? (I see dotted line from "object" to "LIB" on your graph. Do you
> > really mean that LIBS can be assembled in yet another library)
>
> Yes, absolutely I mean that. It is possible, and it's easy to imagine that
> some people will want to do it. For example, we might build Python, Regex,
> and Threads as separate libraries, then assemble them into a single Boost
> library.

Resonable. 

> More importantly, I was just trying to formalize my mental model for
> targets and their relationship. I usually find that the best approach when
> I don't know how to approach a problem is to code something which
> corresponds to my mental model. Unfortunately, I'm not sure my mental model
> is adequate yet ;-(

Very possible that some form of hierarchy might help. My futher suggestions 
will take hierarchy into account.

> > 2. What is your definition of "toolset"? You say:
> > "build jobs outside the domain of the toolset". For me, toolset is
> > nothing but a named set of transformation rules.
>
> We have a specific feature called "toolset" which refers to an important
> case of a named set of capabilities (usually, compiling, linking, etc.). I
> mean to distinguish that from the more general idea of a named set of
> transformation rules.

I'm not sure which consequences that will have. In any case we'd need to 
insure that other transformations won't become resticted in some aspects.

> > There might be the following transformations available
> >
> > type->type : requirements : rule
> > C++->OBJ : <toolset>gcc : gcc-C++-compile
> > C++->C : <toolset>auc : auc-C++-compile
> > C->OBJ : <toolset>aux : auc-C-compile

> I understand what you're doing here (and I understood your proposal on the
> Wiki). However, I think there are some important issues that it doesn't
> address:
>
> 1. The top-level target specification is something more like (for an exe):
>
> C++*,C*,OBJ*,LIB*->EXE
>
> Some mechanism is needed to decompose that into the individual steps
> (C++->OBJ, OBJ*,LIB*->EXE) which actually form the dependency graph.

Hm, I don't understand. Up till now I thought we had similar approach to the 
decomposing into steps! Transformations that I'm taling about are edges in 
the transformation (or dependency) graph. I don't think that finding the 
sequence of transformation is in any way different from finding 
shortest/unique path.

> 2. I find myself wanting to create new variations on existing target types.
> PYD as a specialization of DLL is one example. I suppose it's possible that
> this is sufficiently rare that it can be handled as a special case, but
> somehow I doubt it (plugins with special requirements are a common idea).
> This causes a significant amount of code repetition in the current system.
> It would be best if these transition rules could choose the "best match",
> so that, e.g., when building a PYD <target-type>PYD and <target-type>DLL
> are both in the property set, and available, but PYD-specific transitions
> will take precedence. That is part of the motivation behind the "shortest
> path" idea.

I'm starting to feel that deriving from exising target types is the idea 
worth implementing.

> 3. I worry a little bit about throwing all of these generators into a big
> "soup" and letting them compete without any opportunity to control the
> process. Will we paint ourselves into a corner where someone wants to
> extend the capabilities of the system but can't get the results they want?

> My current thinking is that:
>
> 1. A target has a large collection of properties, many of which are not
> "relevant" in the sense that we use it, i.e. will not contribute to
> determining a unique subvariant identity. The relevant subset of the
> target's property set is called it's "relevance-set"
>
> 2. Some of the features in the target's property set are "active", in the
> sense that they cause rules to be executed which modify attributes and
> properties of the target.
>
> 3. any of the "active" features of the target has an opportunity to add
> features to its relevance-set.

> > With all said, I don't think we should look for shortest path to find
> > transformation sequence -- we should look for unique one.
>
> I'm a little concerned about how that would affect the extensibility of the
> system. Here's one simple example: when in "user mode" we might well want
> to enable an executable to be generated directly from source files, without
> intermediate .obj files when the toolset supports it. It would be nice if
> simply enabling those transitions could do the job.

At this point we'd need to go back, I guess. 

1. What is the semantic of build request and subvariants? I'm not sure we 
agree on this point. 

One alternative is that build request for a main target specify all the 
variants (property-sets) of that targets that we want to build. Initially, 
not all subvariants are known -- e.g. <runtime-link> might not be relevant. 
By providing "active" features it's possible to change relevance-set &c.

Another alternative is that build request constrains possible transformation.
For example, cpp may be compiled in obj by many toolsets, but <toolset>gcc in 
build request would allow only those compilations which use gcc as toolset. 
All found allowed transformation pathes create a new subvariant. E.g. we have 
cpp->obj transformation with two possible prorerty-sets:
<toolset>gcc <runtime-link>dynamic
<toolset>gcc <runtime-link>static
As a result, we have two subvariants for each object file, and two 
subvariants for exe.

For me, the second alternative is more attractive. 
I don't like the idea of determining subvariants prior to finding all the 
transformation pathes. I'm not sure this is feasible at all -- some tool in 
the middle of the path might have two ways of working, resuling in two 
subvariants, and we'll never know that unless the path is found. After 
tranformations are found, I see no obvious need to use active features in 
order to find subvariants -- each transformation might well list features 
relevant to it.

Note that I don't mean that active features are not needed, but that's below.

2. How all those transformation pathes are found?

This is hard question. In Jambase, everything is simple -- for each source 
type, the sequence of transformations to make an object of that type is 
hardcoded. We'd like to support more elaborated method.

i) How precisely is the sequence of transformation is found?
ii) Which support is needed for target type hierarchy?
iii) Which hooks will allow tools to do something special?
iv) Do we need to support make style implicit transformation sequences?

i) When there's no toolsets and subvariants, just shortest path will do. With 
toolsets, I think we can gather a set of shortest pathes with unique set of 
properties that are required on that path. I'm yet to consider how such a 
search can be implemented. The idea is that toolset A might support 
C++->OBJ; OBJ*,C++*->EXE, and B might support
C++->OBJ; OBJ*->EXE
Naive seach for shortest path will give C++*->EXE, that toolset B does not 
support. 

ii) Let's start will the following question: is it okay to have a semantic 
where: 
- each derived target type initially inherits all the transformation that 
it's parent has
- it's possible to define new transformation that apply to the derived type.
All the transformations with the same (or compatible?) set of required 
properties are the overrided.
What I mean here that we would be able to change transformation rules for 
particular derived target type on a particular compiler without trashing 
transformations for other compiles.
If such a semantics is okay, then we've agreed. Of cause, we'll probably want 
some optimization, but that's not a design issue.

iii) 
First level of hook is that new top-level rule can be written to do some 
special processing of its sources. 
Second, we might have toolset-specific rules that computed transformation 
from source type to target type. I think that graph based approach is better 
for general use, but probably in some cases it makes sense to bypass it, or 
use it in a odd way.
Third, there might be active features: they cause some rules to be executed 
before pathes are computed.
Last, set of relevant features for a transformation might be optionally 
computed via a rule invocation. Artifical example: some tool might happen to 
provide two very different modes of operation starting with certain version, 
and a rule can take that into account.

However, I'm not sure all those hooks are either needed or enough. So, I 
think we need to write down a set of use cases for source transformation. 
I've started doing it, maybe other can do. I think we're mostly interested in 
corner cases -- the more bizarre transformations you can imagine -- the 
better!

iv) Make uses completely different approach to computing transformation: you 
give the target file of a transformation chain. Whether this is usefull is 
moot. I was thinking about a case where it might help to hint the type of an 
intermidiate file, but so far have no concrete example.

- Volodya