#  Copyright (C) Vladimir Prus 2002. Permission to copy, use, modify, sell and
#  distribute this software is granted provided this copyright notice appears in
#  all copies. This software is provided "as is" without express or implied
#  warranty, and with no claim as to its suitability for any purpose.

#  Manages 'generators' --- objects which can do transformation between different
#  target types and contain algorithm for finding transformation from sources
#  to targets.
#
#  The main entry point to this module is generators.construct rule. It is given
#  a list of source targets, desired target type and a set of properties.
#  It starts by selecting 'viable generators', which have any chances of producing
#  the desired target type with the required properties. Generators are ranked and
#  a set of most specific ones is selected.
# 
#  The most specific generators have their 'run' methods called, with the properties
#  and list of sources. Each one selects target which can be directly consumed, and
#  tries to convert the remaining ones to the types it can consume. This is done
#  by recursively calling 'construct' with all consumable types.
#
#  If the generator has collected all the targets it needs, it creates targets 
#  corresponding to result, and returns it. When all generators have been run,
#  results of one of them are selected and returned as result.
#
#  It's quite possible that 'construct' returns more targets that it was asked for.
#  For example, it was asked to target type EXE, but the only found generators produces
#  both EXE and TDS (file with debug) information. The extra target will be returned.
#
#  Likewise, when generator tries to convert sources to consumable types, it can get
#  more targets that it was asked for. The question is what to do with extra targets.
#  Boost.Build attempts to convert them to requested types, and attempts as early as
#  possible. Specifically, this is done after invoking each generator. (Later I'll 
#  document the rationale for trying extra target conversion at that point).
#
#  That early conversion is not always desirable. Suppose a generator got a source of
#  type Y and must consume one target of type X_1 and one target of type X_2.
#  When converting Y to X_1 extra target of type Y_2 is created. We should not try to
#  convert it to type X_1, because if we do so, the generator will get two targets
#  of type X_1, and will be at loss as to which one to use. Because of that, the
#  'construct' rule has a parameter, telling if multiple targets can be returned. If
#  the parameter is false, conversion of extra targets is not performed.

import "class" : is-a new ;
import container ;
import utility : str equal ;
import set sequence ;
import assert ;
import virtual-target ;
import property-set ;

if "--debug-generators" in [ modules.peek : ARGV ] 
{    
    .debug = true ;
}

# Outputs a debug message if generators debugging is on.
# Each element of 'message' is checked to see if it's class instance.
# If so, instead of the value, the result of 'str' call is output.
local rule generators.dout ( message * )
{
    if $(.debug)
    {                
        ECHO [ sequence.transform utility.str : $(message) ] ;
    }    
}


local rule indent ( )
{
    return $(.indent:J="") ;
}

local rule increase-indent ( )
{
    .indent += "    " ;
}

local rule decrease-indent ( )
{
    .indent = $(.indent[2-]) ;
}

# Takes a vector of 'virtual-target' instances and makes a normalized
# representation, which is the same for given set of targets,
# regardless of their order.
rule normalize-target-list ( targets )
{
    local v = [ $(targets).get ] ;
    $(targets).set $(v[1]) [ sequence.insertion-sort $(v[2-]) : utility.less ] ;
}

# Creates a generator
class generator 
{
    import generators ;
    import assert ;
    import generators : indent increase-indent decrease-indent generators.dout ;
    import generators ;
    import set ;
    import utility : equal ;
    import feature ;
    import errors : error ;
    import sequence ;
    import type ;
    import virtual-target ;
    import "class" : new ;
    import property ;
   
    EXPORT class@generator : indent increase-indent decrease-indent generators.dout ;
    
    rule __init__ (  
      id # identifies the generator - should be name of the rule which
         # sets up build actions
      composing ? # whether generator processes each source target in
                  # turn, converting it to required types.
                  # Ordinary generators pass all sources together to
                  # recusrive generators.construct-types call.
    
    : source-types *  # types that this generator can handle.  If
                      # empty, the generator can consume anything.
    
    : target-types-and-names +   
      # types the generator will create and, optionally, names for
      # created targets. Each element should have the form
      #    type["(" name-pattern ")"]
      # for example, obj(%_x). Name of generated target will be found
      # by replacing % with the name of source, provided explicit name
      # was not specified.
    
    : requirements *
                )
    {                    
        self.id = $(id) ;
        self.composing = $(composing) ;
        self.source-types = $(source-types) ;
        self.target-types-and-names = $(target-types-and-names) ;
        self.requirements = $(requirements) ;
        
        for local e in $(target-types-and-names)
        {        
            # Create three parallel lists: one with the list of target types,
            # and two other with prefixes and postfixes to be added to target 
            # name. We use parallel lists for prefix and postfix (as opposed
            # to mapping), because given target type might occur several times,
            # for example "H H(%_symbols)".
            local m = [ MATCH ([^\\(]*)(\\((.*)%(.*)\\))? : $(e) ] ;
            self.target-types += $(m[1]) ;
            self.name-prefix += $(m[3]:E="") ;
            self.name-postfix += $(m[4]:E="") ;
        }
                                    
        # Note that 'transform' here, is the same as 'for_each'.
        sequence.transform type.validate : $(self.source-types) ;
        sequence.transform type.validate : $(self.target-types) ;
    }
                            
    ############## End of constructor #################
    
    rule id ( )
    {
        return $(self.id) ;
    }

    # Returns the list of target type the generator accepts.
    rule source-types ( )
    {
        return $(self.source-types) ;
    }

    # Returns the list of target types that this generator produces.
    # It is assumed to be always the same -- i.e. it cannot change depending
    # list of sources.    
    rule target-types ( )
    {
        return $(self.target-types) ;
    }
    
    # Returns the required properties for this generator. Properties
    # in returned set must be present in build properties if this 
    # generator is to be used. If result has grist-only element,
    # that build properties must include some value of that feature.
    # XXX: remove this method?
    rule requirements ( )
    {
        return $(self.requirements) ;
    }
    
    # Returns a true value if the generator can be run with the specified 
    # properties.
    rule match-rank ( property-set-to-match )
    {
        # See if generator's requirements are satisfied by
        # 'properties'.  Treat a feature name in requirements
        # (i.e. grist-only element), as matching any value of the
        # feature.
        local all-requirements = [ requirements ] ;
        
        local property-requirements feature-requirements ;
        for local r in $(all-requirements)
        {
            if $(r:G=)
            {
                property-requirements += $(r) ;
            }
            else
            {
                feature-requirements += $(r) ;
            }                      
        }

        local properties-to-match = [ $(property-set-to-match).raw ] ;
        if $(property-requirements) in $(properties-to-match) 
           && $(feature-requirements) in $(properties-to-match:G)
        {
            return true ;
        }
        else
        {
            return ;
        }
    }
        
    # Returns another generator which differers from $(self) in
    # - id
    # - value to <toolset> feature in properties
    rule clone ( new-id : new-toolset-properties + )
    {
        return [ new $(__class__) $(new-id) $(self.composing)
                 : $(self.source-types)
                 : $(self.target-types-and-names) 
                 # Note: this does not remove any subfeatures of <toolset>
                 # which might cause problems
                 : [ property.change $(self.requirements) : <toolset> ]
                   $(new-toolset-properties)
               ] ;
    }
    
    # Creates another generator that is the same as $(self), except that
    # if 'base' is in target types of $(self), 'type' will in target types
    # of the new generator.
    rule clone-and-change-target-type ( base : type )
    {
        local target-types ;
        for local t in $(self.target-types-and-names)
        {
            local m = [ MATCH ([^\\(]*)(\\(.*\\))? : $(t) ] ;
            if $(m) = $(base)
            {
                target-types += $(type)$(m[2]:E="") ;
            }
            else
            {
                target-types += $(t) ;
            }                                        
        }
                
        return [ new $(__class__) $(self.id) $(self.composing)
                 : $(self.source-types)
                 : $(target-types) 
                 : $(self.requirements)
               ] ;
    }

    
    # Tries to invoke this generator on the given sources. Returns a
    # list of generated targets (instances of 'virtual-target').
    rule run ( project  # Project for which the targets are generated
               name ?   # Determines the name of 'name' attribute for 
                        # all generated targets. See 'generated-targets' method.
               : property-set # Desired properties for generated targets.
               : sources +  # Source targets.
            )
    {       
        generators.dout [ indent ] "  ** generator" $(self.id) ;
        generators.dout [ indent ] "  multiple:" $(mutliple) ;
        generators.dout [ indent ] "  composing:" $(self.composing) ;        
        
        if ! $(self.composing) && $(sources[2]) && $(self.source-types[2])
        {
            errors.error "Unsupported source/source-type combination" ;
        }
               
        # We don't run composing generators if no name is specified. The reason
        # is that composing generator combines several targets, which can have
        # different names, and it cannot decide which name to give for produced
        # target. Therefore, the name must be passed.
        #
        # This in effect, means that composing generators are runnable only
        # at top-level of transofrmation graph, or if name is passed explicitly.
        # Thus, we dissallow composing generators in the middle. For example, the
        # transofrmation CPP -> OBJ -> STATIC_LIB -> RSP -> EXE won't be allowed 
        # (the OBJ -> STATIC_LIB generator is composing)
        if ! $(self.composing) || $(name)
        {            
            run-really $(project) $(name) : $(property-set) : $(sources) ;
        }        
    }
    
    
    rule run-really ( project name ? : property-set : sources + )
    {
        # Targets that this generator will consume directly.
        local consumed = ;
        # Targets that can't be consumed and will be returned as-is.
        local bypassed = ;
        
        if $(self.composing)
        {
            convert-multiple-sources-to-consumable-types $(project)
              : $(property-set) : $(sources) : consumed bypassed ;            
        }
        else
        {               
            convert-to-consumable-types $(project) $(name) : 
              $(property-set) : $(sources) 
                :
                : consumed bypassed ;
        }
                
        local result ;
        if $(consumed)  
        {            
            result = [ construct-result $(consumed) : $(project) $(name) 
                     : $(property-set) ] ;
        }
                            
                
        if $(result)
        {
           generators.dout [ indent ] "  SUCCESS: " $(result) ;
        }
        else
        {
            generators.dout [ indent ] "  FAILURE" ;
        }
        generators.dout ;
        return $(result) ;        
    }

    # Constructs the dependency graph that will be returned by this 
    # generator
    rule construct-result ( 
        consumed + # Already prepared list of consumable targets
                   # If generator requires several source files will contain 
                   # exactly len $(self.source-types) targets with matching types
                   # Otherwise, might contain several targets with the type of 
                   # $(self.source-types[1])                               
        : project name ? 
        : property-set  # Properties to be used for all actions create here
    )
    {
        local result ;
        # If this is 1->1 transformation, apply it to all consumed targets in order.
        if ! $(self.source-types[2]) && ! $(self.composing)
        {
            for local r in $(consumed)
            {                
                result += [ generated-targets $(r) : $(property-set) : $(project) $(name) ] ; #(targets) ;
            }
        }
        else
        {
            if $(consumed) 
            {
                result += [ generated-targets $(consumed) : $(property-set) 
                            : $(project) $(name) ] ;
            }                        
        }
        return $(result) ;
    }   
    
    # Constructs targets that are created after consuming 'sources'.
    # The result will be the list of virtual-target, which the same length
    # as 'target-types' attribute and with corresponding types.
    # 
    # When 'name' is empty, all source targets must have the same value of 
    # the 'name' attribute, which will be used instead of the 'name' argument.
    #
    # The value of 'name' attribute for each generated target will be equal to
    # the 'name' parameter if there's no name pattern for this type. Otherwise,
    # the '%' symbol in the name pattern will be replaced with the 'name' parameter 
    # to obtain the 'name' attribute.
    #
    # For example, if targets types are T1 and T2(with name pattern "%_x"), suffixes
    # for T1 and T2 are .t1 and t2, and source if foo.z, then created files would
    # be "foo.t1" and "foo_x.t2". The 'name' attribute actually determined the
    # basename of a file.
    #
    # Note that this pattern mechanism has nothing to do with implicit patterns
    # in make. It's a way to produce target which name is different for name of 
    # source.
    rule generated-targets ( sources + : property-set : project name ? )
    {
        if ! $(name)
        {
            # Determine the name of the produced target from the
            # names of the sources. The simple case if when a name
            # of source has single dot. Then, we take the part before
            # dot. Several dots can be caused by:
            # - Using source file like a.host.cpp
            # - A type which suffix has a dot. Say, we can
            #   type 'host_cpp' with extension 'host.cpp'.
            # In the first case, we want to take the part till the last
            # dot. In the second case -- no sure, but for now take
            # the part till the last dot too.
            name = [ utility.basename [ $(sources[1]).name ] ] ;
                        
            for local s in $(sources[2])
            {
                local n2 = [ utility.basename [ $(s).name ] ] ;
                if $(n2) != $(name)
                {
                    error "$(self.id): source targets have different names: cannot determine target name" ;
                }
            }

            # Names of sources might include directory. We should strip it.
            name = $(name:D=) ;
        }
        
        # Assign an action for each target
        local action = [ action-class ] ;
        local a = [ class.new $(action) $(sources) : $(self.id) : 
                    $(property-set) ] ;
                
        # Create generated target for each target type.
        local targets ;
        local pre = $(self.name-prefix) ;
        local post = $(self.name-postfix) ;
        for local t in $(self.target-types)                 
        {      
            local generated-name = $(pre[1])$(name)$(post[1]) ;
            pre = $(pre[2-]) ;
            post = $(post[2-]) ;
            
            targets += [ class.new file-target $(generated-name) 
              : $(t) : $(project) : $(a) ] ;
        }                 
        
        return [ sequence.transform virtual-target.register : $(targets) ] ;
    }    
    
    # Attempts to convert 'source' to the types that this generator can
    # handle. The intention is to produce the set of targets can should be
    # used when generator is run.
    rule convert-to-consumable-types ( project name ? : 
        property-set : sources +  
        : only-one ? # convert 'source' to only one of source types
                     # if there's more that one possibility, report an
                     # error 
        : consumed-var # name of variable which recieves all targets which 
                       # can be consumed. 
          bypassed-var # name variable which recieves all targets which 
                       # cannot be consumed  
    )
    {        
        # We're likely to be passed 'consumed' and 'bypassed'
        # var names. Use "_" to avoid name conflicts.
        local _consumed ;
        local _bypassed ;
        local missing-types ; 

        if $(sources[2])
        {
            # Don't know how to handle several sources yet. Just try 
            # to pass the request to other generator
            missing-types = $(self.source-types) ;
        }
        else
        {            
            consume-directly $(sources) : _consumed : missing-types ;
        }
        
        # No need to search for transformation if
        # some source type has consumed source and
        # no more source types are needed.
        if $(only-one) && $(_consumed) 
        {
            missing-types = ;
        }
            
        #TODO: we should check that only one source type
        #if create of 'only-one' is true.
        # TODO: consider if consuned/bypassed separation should
        # be done by 'construct-types'.
                    
        if $(missing-types)
        {            
            local transformed = [ generators.construct-types $(project) $(name)
              : $(missing-types) : $(property-set) : $(sources) ] ;
                                
            # Add targets of right type to 'consumed'. Add others to
            # 'bypassed'. The 'generators.construct' rule has done
            # its best to convert everything to the required type.
            # There's no need to rerun it on targets of different types.
                
            # NOTE: ignoring usage requirements
            for local t in $(transformed[2-])
            {
                if [ $(t).type ] in $(missing-types)
                {
                    _consumed += $(t) ;
                }
                else
                {
                    _bypassed += $(t) ;
                }
            }               
        }   
        
        _consumed = [ sequence.unique $(_consumed) ] ;        
        _bypassed = [ sequence.unique $(_bypassed) ] ;
        
        # remove elements of '_bypassed' that are in '_consumed'
        
        # Suppose the target type of current generator, X is produced from 
        # X_1 and X_2, which are produced from Y by one generator.
        # When creating X_1 from Y, X_2 will be added to 'bypassed'
        # Likewise, when creating X_2 from Y, X_1 will be added to 'bypassed'
        # But they are also in 'consumed'. We have to remove them from
        # bypassed, so that generators up the call stack don't try to convert
        # them. 
            
        # In this particular case, X_1 instance in 'consumed' and X_1 instance
        # in 'bypassed' will be the same: because they have the same source and
        # action name, and 'virtual-target.register' won't allow two different
        # instances. Therefore, it's OK to use 'set.difference'.
        
        _bypassed = [ set.difference $(_bypassed) : $(_consumed) ] ;
        
                
        $(consumed-var) += $(_consumed) ;
        $(bypassed-var) += $(_bypassed) ;
    }
    
    # Converts several files to consumable types.
    rule convert-multiple-sources-to-consumable-types
      ( project : property-set : sources * : consumed-var bypassed-var )
    {
        # We process each source one-by-one, trying to convert it to
        # a usable type.
        for local source in $(sources)
        {
            local _c ;
            local _b ;
            # TODO: need to check for failure on each source.
            convert-to-consumable-types $(project) : $(property-set)
              : $(source) : true : _c _b ;
            if ! $(_c)
            {
                generators.dout [ indent ] " failed to convert " $(source) ;
            }
            $(consumed-var) += $(_c) ;            
            $(bypassed-var) += $(_b) ;
        }           
    }
        
    rule consume-directly ( source : consumed-var : missing-types-var )
    {
        local real-source-type = [ $(source).type ] ;
        
        # If there are no source types, we can consume anything
        local source-types = $(self.source-types) ;
        source-types ?= $(real-source-type) ;
        
        for local st in $(source-types)
        {
            # The 'source' if of right type already)
            if $(real-source-type) = $(st) || 
              [ type.is-derived $(real-source-type) $(st) ]
            {
                $(consumed-var) += $(source) ;
            }
            else
            {
               $(missing-types-var) += $(st) ;
            }
        }        
    }
    
    
    # Returns the class to be used to actions. Default implementation 
    # returns "action".
    rule action-class ( )
    {
        return "action" ;
    }        
}

import errors : error ;

.generators = ;

# Registers new generator instance 'g'.
rule register ( g )
{
    .generators += $(g) ;
                   
    # A generator can produce several targets of the
    # same type. We want unique occurence of that generator
    # in .generators.$(t) in that case, otherwise, it will
    # be tried twice and we'll get false ambiguity.
    for local t in [ sequence.unique [ $(g).target-types ] ]
    {            
        .generators.$(t) += $(g) ;
    }    
    
    # Update the set of generators for toolset
    
    # TODO: should we check that generator with this id
    # is not already registered. For example, the fop.jam
    # module intentionally declared two generators with the
    # same id, so such check will break it.
    local id = [ $(g).id ] ;
        
    # Some generators have multiple periods in their name, so the
    # normal $(id:S=) won't generate the right toolset name.
    # e.g. if id = gcc.compile.c++, then
    # .generators-for-toolset.$(id:S=) will append to
    # .generators-for-toolset.gcc.compile, which is a separate
    # value from .generators-for-toolset.gcc. Correcting this
    # makes generator inheritance work properly.
    # See also inherit-generators in module toolset
    local base = $(id) ;
    while $(base:S)
    {
        base = $(base:B) ;
    }
    .generators-for-toolset.$(base) += $(g) ;
}
    
# Creates new instance of the 'generator' class and registers it.
# Retursn the creates instance.
# Rationale: the instance is returned so that it's possible to first register
# a generator and then call 'run' method on that generator, bypassing all
# generator selection.
rule register-standard ( id : source-types * : target-types + : requirements * )

{
    local g = [ new generator $(id) : $(source-types) : $(target-types)
      : $(requirements) ] ;
    register $(g) ;   
    return $(g) ;
}

# Creates new instance of the 'composing-generator' class and
# registers it.
rule register-composing ( id : source-types * : target-types + : requirements * )
{
    local g = [ new generator $(id) true : $(source-types) 
                : $(target-types) : $(requirements) ] ;
    register $(g) ;
    return $(g) ;
}

# Returns all generators which belong to 'toolset', i.e. which
# ids are $(toolset).<something>
rule generators-for-toolset ( toolset )
{
    return $(.generators-for-toolset.$(toolset)) ;
}

rule override ( overrider-id : overridee-id )
{
    .override.$(overrider-id) += $(overridee-id) ;    
}



    
# Set if results of the current generators search are going to be cached
# This means no futher attempts to cache generators search should be
# made.
.caching = ;

# Returns a list of source type which can possibly be converted
# to 'target-type' by some chain of generator invocation.
#
# More formally, takes all generators for 'target-type' and
# returns union of source types for those generators and result
# of calling itself recusrively on source types.
local rule viable-source-types-real ( target-type )
{
    local generators ;

    local t = [ type.all-bases $(target-type) ] ;
    
    local result ;
    # 't' is the list of types which are not yet processed    
    while $(t)
    {
        # Find all generators for current type. 
        # Unlike 'find-viable-generators' we don't care about property-set.
        local generators = $(.generators.$(t[1])) ;
        t = $(t[2-]) ;
        

        
        while $(generators)
        {
            local g = $(generators[1]) ;
            generators = $(generators[2-]) ;
            
            if ! [ $(g).source-types ]
            {
                # Empty source types -- everything can be accepted
                result = * ;
                # This will terminate this loop.
                generators = ;
                # This will terminate outer loop.
                t = ;
            }
              
            for local source-type in [ $(g).source-types ] 
            {
                if ! $(source-type) in $(result) 
                {
                    # If generator accepts 'source-type' it
                    # will happily accept any type derived from it
                    local all = [ type.all-derived $(source-type) ] ;
                    for local n in $(all)
                    {
                        if ! $(n) in $(result)
                        {   
                            t += $(n) ;
                            result += $(n) ;
                        }    
                    }                    
                }                
            }            
        }        
    }          
        
    result = [ sequence.unique $(result) ] ;
    
    return $(result) ;                
}

# Helper rule, caches the result of 'viable-source-types-real'.
rule viable-source-types ( target-type )
{
    local key = .vst.$(target-type) ;
    if ! $($(key))
    {
        local v = [ viable-source-types-real $(target-type) ] ;
        if ! $(v)
        {
            v = none ;
        }
        $(key) = $(v) ;
    }
    
    if $($(key)) != none
    {
        return $($(key)) ;
    }        
}

# Returns the list of source types, which, when passed to 'run'
# method of 'generator', has some change of being eventually used
# (probably after conversion by other generators)
rule viable-source-types-for-generator-real ( generator ) 
{        
    local source-types = [ $(generator).source-types ] ;
    if ! $(source-types)
    {
        # If generator does not specify any source types,
        # it might be special generator like builtin.lib-generator
        # which just relays to other generators. Return '*' to
        # indicate that any source type is possibly OK, since we don't
        # know for sure.
        return * ;
    }
    else
    {            
        local result ;
        for local s in $(source-types)
        {
            result += [ type.all-derived $(s) ] 
              [ generators.viable-source-types $(s) ] ;
        }
        result = [ sequence.unique $(result) ] ;        
        if * in $(result)
        {
            result = * ;
        }        
        return $(result) ;
    }        
}    

# Helper rule, caches the result of 'viable-source-types-for-genrator'.
local rule viable-source-types-for-generator ( generator )
{
    local key = .vstg.$(generator) ;
    if ! $($(key))
    {
        local v = [ viable-source-types-for-generator-real $(generator) ] ;
        if ! $(v)
        {
            v = none ;
        }
        $(key) = $(v) ;        
    }
    
    if $($(key)) != none
    {
        return $($(key)) ;
    }        
}



# Returns usage requirements + list of created targets
local rule try-one-generator-really ( project name ? : generator : 
    target-type : property-set : sources * )
{
    local targets =
      [ $(generator).run $(project) $(name)
                       : $(property-set)
                       : $(sources)
      ] ;
            
    local usage-requirements ;
    if $(targets) && [ class.is-a $(targets[1]) : property-set ]
    {
        usage-requirements = $(targets[1]) ;
        targets = $(targets[2-]) ;
    }
    else
    {
        usage-requirements = [ property-set.empty ] ;
    }
    
    generators.dout [ indent ] "  generator" [ $(generator).id ] " spawned " ;
    generators.dout [ indent ] " " $(targets) ; 
    if $(targets)
    {
        return $(usage-requirements) $(targets) ;
    }    
}

# Checks if generator invocation can be pruned, because it's guaranteed
# to fail. If so, quickly returns empty list. Otherwise, calls
# try-one-generator-really.
local rule try-one-generator ( project name ? : generator : 
    target-type : property-set : sources * )
{    
    local source-types ;
    for local s in $(sources)
    {
        source-types += [ $(s).type ] ;
    }
    local viable-source-types = 
      [ viable-source-types-for-generator $(generator) ] ;
    
    if  $(source-types) && $(viable-source-types) != * && 
      ! [ set.intersection $(source-types) : $(viable-source-types) ] 
    {
        local id = [ $(generator).id ] ;
        generators.dout [ indent ] "  ** generator '$(id)' pruned" ;
        #generators.dout [ indent ] "source-types" '$(source-types)' ;
        #generators.dout [ indent ] "viable-source-types" '$(viable-source-types)' ;
    }          
    else {
        return [ try-one-generator-really $(project) $(name)
          : $(generator)
            : $(target-type) : $(property-set) : $(sources) ] ;
    }       
}



rule construct-types ( project name ? : target-types + :
    property-set : sources + )
{
    local result ;
    local matched-types ; 
    local usage-requirements = [ property-set.empty ] ;
    for local t in $(target-types)
    {
        local r = [ construct $(project) $(name) : $(t) : $(property-set) :
          $(sources) ] ;
        if $(r)
        {
            usage-requirements = [ $(usage-requirements).add $(r[1]) ] ;
            result += $(r[2-]) ;
            matched-types += $(t) ;
        }
    }
    # TODO: have to introduce parameter controlling if
    # several types can be matches and add appropriate
    # checks 

    # TODO: need to review the documentation for
    # 'construct' to see if it should return $(source) even
    # if nothing can be done with it. Currents docs seem to
    # imply that, contrary to the behaviour.
    if $(result)
    {
        return $(usage-requirements) $(result) ;
    }
    else
    {
        return $(usage-requirements) $(sources) ;
    }
}

# Ensures all 'targets' have types. If this is not so, exists with 
# error.
local rule ensure-type ( targets * )
{
    for local t in $(targets)
    {
        if ! [ $(t).type ]
        {
            errors.error "target" [ $(t).str ] "has no type" ;
        }        
    }    
}
    
# Returns generators which can be used to construct target of specified type
# with specified properties. Uses the following algorithm:
# - iterates over requested target-type and all it's bases (in the order returned bt
#   type.all-bases.
# - for each type find all generators that generate that type and which requirements
#   are satisfied by properties.
# - if the set of generators is not empty, returns that set.
#
# Note: this algorithm explicitly ignores generators for base classes if there's
# at least one generator for requested target-type.
local rule find-viable-generators-aux ( target-type : property-set )
{
    # Select generators that can create the required target type.
    local viable-generators = ;
    local generator-rank = ;

    import type ;
    local t = [ type.all-bases $(target-type) ] ;
    
    generators.dout  [ indent ] find-viable-generators target-type= $(target-type) 
      property-set= [ $(property-set).as-path ]
          ;
    
    # Get the lit of generators for the requested type.
    # If no generator is registered, try base type, and so on.
    local generators ;
    while $(t[1])
    {
        generators.dout  [ indent ] "trying type" $(t[1]) ;    
        if $(.generators.$(t[1]))
        {
            generators.dout [ indent ] "there are generators for this type" ;
            generators = $(.generators.$(t[1])) ;
            
            if $(t[1]) != $(target-type)
            {
                # We're here, when no generators for target-type are found,
                # but there are some generators for a base type.
                # We'll try to use them, but they will produce targets of
                # base type, not of 'target-type'. So, we clone the generators
                # and modify the list of target types.
                local generators2 ;
                for local g in $(generators)
                {
                    # generators.register adds generator to the list of generators
                    # for toolsets, which is a bit strange, but should work.
                    # That list is only used when inheriting toolset, which
                    # should have being done before generators are run.
                    generators2 += [ 
                      $(g).clone-and-change-target-type $(t[1]) : $(target-type) ] ;
                    generators.register $(generators2[-1]) ;
                }                
                generators = $(generators2) ;
            }                        
            t = ;
        }        
        t = $(t[2-]) ;            
    }
    
    
    for local g in $(generators)
    {
        generators.dout [ indent ] "trying generator" [ $(g).id ] "(" [ $(g).source-types ] -> [ $(g).target-types ] ")" ;
            
        local m = [ $(g).match-rank $(property-set) ] ;
        if $(m) 
        {
            generators.dout [ indent ] "  is viable" ;
            viable-generators += $(g) ;
        }                                    
    }
                            
    return $(viable-generators) ;
}

rule find-viable-generators ( target-type : property-set )
{
    local key = $(target-type).$(property-set) ;
    local l = $(.fv.$(key)) ;
    if ! $(l)
    {
        l = [ find-viable-generators-aux $(target-type) : $(property-set) ] ;
        if ! $(l)
        {
            l = none ;
        }        
        .fv.$(key) = $(l) ;
    }
    
    if $(l) = none
    {
        l = ;
    }
                    
    local viable-generators ;
    for local g in $(l)
    {
        # Avoid trying the same generator twice on different levels.        
        if ! $(g) in $(.active-generators) 
        {
            viable-generators += $(g) ;
        }        
    }
    
    # Generators which override 'all'.
    local all-overrides ;
    # Generators which are overriden
    local overriden-ids ;    
    for local g in $(viable-generators)
    {
        local id = [ $(g).id ] ;
        local this-overrides = $(.override.$(id)) ;
        overriden-ids += $(this-overrides) ;
        if all in $(this-overrides)
        {
            all-overrides += $(g) ;
        }        
    }         
    if $(all-overrides)
    {
        viable-generators = $(all-overrides) ;
    }
    local result ;
    for local g in $(viable-generators)
    {
        if ! [ $(g).id ] in $(overriden-ids)
        {
            result += $(g) ;
        }        
    }
        
    return $(result) ;
}    
        
.construct-stack = ;

# Attempts to construct target by finding viable generators, running them
# and selecting the dependency graph
local rule construct-really (
   project name ? : target-type : property-set : sources * )
{
    viable-generators = [ find-viable-generators $(target-type) : $(property-set) ] ;
                        
    generators.dout [ indent ] "*** " [ sequence.length $(viable-generators) ] 
      " viable generators" ;
    
    local result ;
    local generators-that-succeeded ;
    for local g in $(viable-generators)
    {
        # This variable will be restored on exit from this scope.
        local .active-generators = $(g) $(.active-generators) ;
        
        local r = [ try-one-generator $(project) $(name) : $(g) : $(target-type) :
          $(property-set) : $(sources) ] ;
        
        if $(r)
        {
            generators-that-succeeded += $(g) ;
            if $(result)
            {
                ECHO "Error: ambiguity found when searching for best transformation" ;
                ECHO "Trying to produce type '$(target-type)' from: " ;
                for local s in $(sources)
                {
                    ECHO " - " [ $(s).str ] ;
                }
                ECHO "Generators that succeeded:" ;
                for local g in $(generators-that-succeeded)
                {
                    ECHO " - " [ $(g).id ] ;
                }
                ECHO "First generator produced: " ;
                for local t in $(result[2-])
                {
                    ECHO " - " [ $(t).str ] ;
                }
                ECHO "Second generator produced: " ;
                for local t in $(r[2-])
                {
                    ECHO " - " [ $(t).str ] ;
                }
                EXIT ;
            }
            else
            {
                result = $(r) ;
            }            
        }
    }
    
    return $(result) ;
}       
    
        
# Attempts to create target of 'target-type' with 'properties'
# from 'sources'. The 'sources' are treated as a collection of
# *possible* ingridients -- i.e. it is not required to consume
# them all. If 'multiple' is true, the rule is allowed to return
# several targets of 'target-type'.          
#
#
# Returns a list of target. When this invocation is first instance of
# 'construct' in stack, returns only targets of requested 'target-type',
# otherwise, returns also unused sources and additionally generated
# targets.    
#
# Does not return target which are not of 'allowed-type' or of type derived from
# it. If 'allowed-type' is not specified, it's defaulted to 'target-type'.
# See lib-target-class for use case of this.
rule construct ( project name ? : target-type : property-set * : sources * 
   : allowed-type * )
{
    if (.construct-stack)
    {
        ensure-type $(sources) ;
    }
        
    .construct-stack += 1 ;

    increase-indent ;

    if $(.debug)
    {        
        generators.dout [ indent ] "*** construct" $(target-type) ;
    
        for local s in $(sources)
        {
            generators.dout [ indent ] "    from" $(s) ;
        }
        generators.dout [ indent ] "    properties:" [ $(property-set).raw ] ;        
    }
    
               
    local result = [ construct-really $(project) $(name)  
      : $(target-type) : $(property-set) : $(sources) ] ;
                    
    decrease-indent ;
        
    .construct-stack = $(.construct-stack[2-]) ;
                
    
    return $(result) ;        
}