Re: [Boost-build] Effect of usage requirements vs. default values of a feature

Subject: Re: [Boost-build] Effect of usage requirements vs. default values of a feature
From: Gevorg Voskanyan (v_gevorg_at_[hidden])
Date: 2011-04-17 10:21:08

Vladimir Prus wrote:
> Well, the biggest problem is that if you have metatarget T, which depends on
> metatargets A and B, and you build A first, and then build B, and it returns
> some non-free features as usage requirements, it means that potentially 
>generation
> of A must be redone, recursively.

Yes. And redoing A's generation may produce a different set of usage 
requirements, meaning now B's generation must be redone, which if generates 
different usage requirements this time, will render A's original regeneration 
flawed.

> I don't have a formal proof, but I think that the problem of determining right
> set of build properties for all metatarget, if non-free usage requirements is
> allowed, would be essentially as complex as SAT. And while we can use SAT 
>solvers,
> I am very sceptical about using such complicated machinery -- we might arrive
> at answer that is correct, but totally opaque to the user.

I see.

> So, I suspect that if we're to allow non-free features in usage requirements,
> we need to invent some heuristics that would work in practical cases without
> requiring exponential iteration over all metatargets.

I have an idea that might work. It is based on an agreement that some properties 
can't ever change once they are assigned to a target. Let's call them 'hard' 
properties.
Formally, a property <F>V on a target [1] T is hard if:
1. F is a non-free feature
2. There can be no property on T of the form <F>U such that U != V, after <F>V 
is declared a hard property on T
Let's also call a feature F 'hard' on a target T iff there is a hard property on 
T of the form <F>V. By definition there can be only one property with a given 
hard feature on a target.

[Initial refining of requirements]
A target's hard properties are refined by its own conditional requirements, but 
only those where all the features conditioned upon are hard features on the 
target and the produced property is of non-free feature.
If evaluating such a conditional requirement is satisfied and a property P with 
feature F is produced, then P is applied to T as a hard property as follows:
   [applying a hard property]
   1. If there is a hard property Q with feature F on T, then
        1.1. If P == Q, P is ignored
        1.2. Else a descriptive error message is reported and build is aborted 
[2]
   2. Else P is declared as a hard property on T, replacing existing (non-hard) 
property having feature F on T, if any
   [/applying a hard property]
If there was an amendment to hard properties (Step 2. above was executed), 
refining is restarted to recheck conditional requirements which weren't 
previously satisfied (recursion to [Initial refining of requirements]).
Indirect conditional requirements are not evaluated here [3].

[Generating sources]
Then we can state that usage requirements are not considered at this stage 
unless forced by hard properties only. Specifically, a usage requirement R 
induced by source S of target T is applied to T iff all of the following holds:
1. If S is an alternative, let W be the set of the features of all requirements 
specified for selection in all the alternatives S was selected from. Then, every 
feature in W is hard on S
2. If R is a direct [4] conditional requirement, all the features conditioned 
upon are hard features on S
3. R is not an indirect conditional requirement
4. R's induced property's feature is non-free
All properties collected from S this way are applied to T as follows - for every 
induced property P (of feature F):
see [applying a hard property]
If hard properties were refined after collecting usage requirements of S (Step 
2. of [applying a hard property] was executed for some property), then again go 
to [Initial refining of requirements], then redo [Generating sources].

[Evaluating free properties]
Note: Requirements producing properties with free features, as well as all 
indirect conditional requirements were ignored until now.
Conditional requirements and sources' usage requirements are evaluated for free 
properties in the normal way - without making a distinction for hard properties. 
If a usage requirement or evaluating a conditional requirement (indirect or not) 
produces a property with non-free feature, a descriptive error is reported and 
build is aborted. Otherwise all produced free properties are added to the 
target.

After this the build process can move on to produce concrete targets with the 
resulting property set.

Now let's define which properties are declared to be hard properties. Formally, 
a property P with (non-free) feature F is declared to be a hard property on 
target T, if:
1. <F> is one of <os>, <host-os>; or
2. P is an unconditional requirement in T's requirements list; or
3. P is an unconditional project requirement in T's project's project 
requirements list and was not removed using -<F>V syntax; or
4. P is among the set of properties T was requested with:
4.1. comes from user's build request; or
4.2. P is in the target reference T was produced after ( MetaT//O/P/Q ); or
4.3. F is a propagated feature and P is a hard property on the target that T is 
produced as a source for; or
5. A direct conditional requirement depending only on T's hard features produces 
P (see [Initial refining of requirements]); or
6. A usage requirement depending only on T's and the used target's hard 
properties produces P (see [Generating sources]); or
7. F is a feature, such that a target specifying a value for it in its usage 
requirements doesn't make much sense, yet it is very common to check for them in 
conditional requirements. Practically this means <F> is one of <target-os>, 
<toolset>, <toolset-xxx:version>, <architecture>, <address-model>, 
<instruction-set> [5]

[Special hard properties]
If F satisfies 7., a corresponding property is declared hard in the following 
fashion: if F satisfies one of 2., 3. or 4.2., then the corresponding property P 
is declared hard on T. In any case, one-shot evaluation of direct conditional 
requirements based on only existing hard properties is done for T, but the 
produced results are discarded except for a property with feature F. If a 
property of form <F>V (either one or all the same value) was indeed produced, 
<F>V is applied as a hard property (an error is emitted and build is aborted if 
there was <F>U hard property on T already such that U != V [6]). Otherwise if no 
<F>V property was produced, and F satisfies 4.1. or first-time 4.3. (4.3. might 
have effect on T more that once), the produced property is declared hard on T. 
Otherwise <F>V is declared hard on T where V is the default value for F. This is 
done for each 7. feature separately, in the same order as written in 7. [7]

Unless I'm missing something, this scheme has the potential to work well in 
practice. The complexity is at most quadratic on the number of sources, and 
actually much-much better in average in real-world use cases.

[1] I don't know if there is a more appropriate term for that. By 'target' here 
I mean the intermediate result of calling a metatarget with a set of properties 
but which is not a concrete target yet, as its properties aren't yet finalized. 
It's in the process of refining its properties, and will become a concrete 
target once that process is over.

[2] This is an attempt from a conditional requirement (or from a source via 
usage requirements) to modify a target's hard property. We declare that is not 
allowed
[3] I'm not very happy with that, but otherwise it doesn't seem possible to 
avoid exponential complexity. We could advise users not to return properties 
with non-free features from indirect conditional requirement rules, and perhaps 
give an error or warning whenever such a property is produced from evaluating an 
indirect conditional requirement.

[4] It's practically impossible to this validation for indirect conditional 
requirements, as it can be arbitrary Jam code. The advice would be not to return 
requirements with non-free features from indirect conditional requirement rules

[5] Assuming the last three are non-optional by then, according to the existing 
plan

[6] e.g.   obj x : x.cpp <target-os>windows:<address-model>32 ; lib y : 
x//<address-model>64 ; # error when target-os is windows

[7] This allows crucial features such as <target-os> and <toolset> to always be 
hard w.r.t. usage requirements, and still allows 
<target-os>darwin:<toolset>clang in requirements to work

> I'd be thrilled to have real discussion about this problem.

Hope the above makes some sense. In any case I think before we get to lift this 
limitation, as usage requirements with non-free features don't currently work 
anyway, for now we can detect such cases and report an appropriate error or a 
warning, plus indicate clearly in documentation that this isn't supported yet. 
Thoughts?

> - Volodya

Sorry for the length of the message, and thanks for reading thus far!

Best Regards,
Gevorg