Quelle Derivations.gi Sprache: unbekannt

# SPDX-License-Identifier: GPL-2.0-or-later
# CAP: Categories, Algorithms, Programming
#
# Implementations
#
#! @Chapter Managing Derived Methods

BindGlobal( "TheFamilyOfDerivations",
            NewFamily( "TheFamilyOfDerivations" ) );
BindGlobal( "TheFamilyOfDerivationGraphs",
            NewFamily( "TheFamilyOfDerivationGraphs" ) );
BindGlobal( "TheFamilyOfOperationWeightLists",
            NewFamily( "TheFamilyOfOperationWeightLists" ) );

BindGlobal( "TheTypeOfDerivedMethods", NewType( TheFamilyOfDerivations, IsDerivedMethod ) );
BindGlobal( "TheTypeOfDerivationsGraphs", NewType( TheFamilyOfDerivationGraphs, IsDerivedMethodGraph ) );
BindGlobal( "TheTypeOfOperationWeightLists", NewType( TheFamilyOfOperationWeightLists, IsOperationWeightList ) );

InstallGlobalFunction( "ActivateDerivationInfo",
  function( )
    SetInfoLevel( DerivationInfo, 1 );
end );

InstallGlobalFunction( "DeactivateDerivationInfo",
  function( )
    SetInfoLevel( DerivationInfo, 0 );
end );

InstallGlobalFunction( CreateDerivation, function( target_op_name, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters )
  local number_of_proposed_arguments, current_function_argument_number, used_op_names_with_multiples_and_category_getters, collected_list, wrapped_category_filter, derivation, x;

    if target_op_name <> "internal dummy function of a final derivation" then

        if not IsBound( CAP_INTERNAL_METHOD_NAME_RECORD.(target_op_name) ) then

            Error( "trying to create a derviation for a method not in CAP_INTERNAL_METHOD_NAME_RECORD" );

        fi;

        number_of_proposed_arguments := Length( CAP_INTERNAL_METHOD_NAME_RECORD.(target_op_name).filter_list );

        current_function_argument_number := NumberArgumentsFunction( func );

        if current_function_argument_number >= 0 and current_function_argument_number <> number_of_proposed_arguments then

            Error( "while adding a derivation for ", target_op_name, ": given function has ", current_function_argument_number, " arguments but should have ", number_of_proposed_arguments );

        fi;

    fi;

    #= comment for Julia
    if PositionSublist( String( category_filter ), "CanCompute" ) <> fail then

        Print( "WARNING: The CategoryFilter of a derivation for ", target_op_name, " uses `CanCompute`. Please register all preconditions explicitly.\n" );

    fi;
    # =#

    # canonicalize used ops
    used_op_names_with_multiples_and_category_getters := [ ];

    for x in used_ops_with_multiples_and_category_getters do

        if Length( x ) < 2 or not IsFunction( x[1] ) or not IsInt( x[2] ) then

            Error( "preconditions must be of the form `[op, mult, getter]`, where `getter` is optional" );

        fi;

        if (Length( x ) = 2 or (Length( x ) = 3 and x[3] = fail)) and NameFunction( x[1] ) = target_op_name then

            Error( "A derivation for ", target_op_name, " has itself as a precondition. This is not supported because we cannot compute a well-defined weight.\n" );

        fi;

        if Length( x ) = 2 then

            Add( used_op_names_with_multiples_and_category_getters, [ NameFunction( x[1] ), x[2], fail ] );

        elif Length( x ) = 3 then

            if x <> fail and not (IsFunction( x[3] ) and NumberArgumentsFunction( x[3] ) = 1) then

                Error( "the category getter must be a single-argument function" );

            fi;

            Add( used_op_names_with_multiples_and_category_getters, [ NameFunction( x[1] ), x[2], x[3] ] );

        else

            Error( "The list of preconditions must be a list of pairs or triples." );

        fi;

    od;

    #= comment for Julia
    if target_op_name <> "internal dummy function of a final derivation" then

        collected_list := CAP_INTERNAL_FIND_APPEARANCE_OF_SYMBOL_IN_FUNCTION( func, RecNames( CAP_INTERNAL_METHOD_NAME_RECORD ), loop_multiplier, CAP_INTERNAL_METHOD_RECORD_REPLACEMENTS, category_getters );

        if Length( collected_list ) <> Length( used_op_names_with_multiples_and_category_getters ) or not ForAll( collected_list, c -> c in used_op_names_with_multiples_and_category_getters ) then

            SortBy( used_op_names_with_multiples_and_category_getters, x -> x[1] );
            SortBy( collected_list, x -> x[1] );

            Print(
                "WARNING: You have installed a derivation for ", target_op_name, " with preconditions ", used_op_names_with_multiples_and_category_getters,
                " but the automated detection has detected the following list of preconditions: ", collected_list, ".\n",
                "If this is a bug in the automated detection, please report it.\n"
            );

        fi;

    fi;
    # =#

    if NumberArgumentsFunction( category_filter ) = 0 or NumberArgumentsFunction( category_filter ) > 1 then

        Error( "the CategoryFilter of a derivation must accept exactly one argument" );

    fi;

    if ForAny( used_op_names_with_multiples_and_category_getters, x -> x[3] <> fail ) and category_filter = IsCapCategory then

        Print( "WARNING: A derivation for ", target_op_name, " depends on other categories (e.g. RangeCategoryOfHomomorphismStructure) but does no test via the CategoryFilter if the other categories are available (e.g. by testing HasRangeCategoryOfHomomorphismStructure).\n" );

    fi;

    if IsProperty( category_filter ) then

        # for Julia
        wrapped_category_filter := cat -> Tester( category_filter )( cat ) and category_filter( cat );

        #= comment for Julia
        wrapped_category_filter := Tester( category_filter ) and category_filter;
        # =#

    else

        wrapped_category_filter := category_filter;

    fi;

    derivation := CreateGapObjectWithAttributes( TheTypeOfDerivedMethods,
        Description, description,
        AdditionalWeight, weight,
        DerivationFunction, func,
        CategoryFilter, wrapped_category_filter,
        TargetOperation, target_op_name,
        UsedOperationsWithMultiplesAndCategoryGetters, used_op_names_with_multiples_and_category_getters
    );

    return derivation;

end );

InstallMethod( String,
               [ IsDerivedMethod ],
function( d )
  return Concatenation( "derivation ", Description( d ),
                        " of operation ", TargetOperation( d ) );
end );

InstallMethod( ViewString,
               [ IsDerivedMethod ],
function( d )
  return Concatenation( "<", String( d ), ">" );
end );

InstallMethod( IsApplicableToCategory,
               [ IsDerivedMethod, IsCapCategory ],
function( d, C )
  return CategoryFilter( d )( C );
end );

InstallMethod( InstallDerivationForCategory,
               [ IsDerivedMethod, IsPosInt, IsCapCategory ],
FunctionWithNamedArguments(
  [
    [ "IsFinalDerivation", false ],
  ],
  function( CAP_NAMED_ARGUMENTS, d, weight, C )
    local method_name, func;

    method_name := TargetOperation( d );
    func := DerivationFunction( d );

    if HasFunctionCalledBeforeInstallation( d ) then

        FunctionCalledBeforeInstallation( d )( C );

    fi;

    AddCapOperation( method_name, C, func, weight : IsDerivation := not(CAP_NAMED_ARGUMENTS.IsFinalDerivation), IsFinalDerivation := CAP_NAMED_ARGUMENTS.IsFinalDerivation );

end ) );

InstallMethod( MakeDerivationGraph,
               [ IsDenseList ],
function( operations )
  local G, op_name;
  G := rec( derivations_by_target := rec(),
              derivations_by_used_ops := rec() );
  G := ObjectifyWithAttributes( G, TheTypeOfDerivationsGraphs );

  SetOperations( G, operations );

  for op_name in operations do
    G!.derivations_by_target.( op_name ) := [];
    G!.derivations_by_used_ops.( op_name ) := [];
  od;

  # derivations not using any operations
  G!.derivations_by_used_ops.none := [];

  return G;
end );

InstallMethod( AddOperationsToDerivationGraph,
               [ IsDerivedMethodGraph, IsDenseList ],

  function( graph, operations )
    local op_name;

    Append( Operations( graph ), operations );

    for op_name in operations do

        graph!.derivations_by_target.( op_name ) := [];
        graph!.derivations_by_used_ops.( op_name ) := [];

    od;

end );

InstallMethod( String,
               [ IsDerivedMethodGraph ],
function( G )
  return "derivation graph";
end );

InstallMethod( ViewString,
               [ IsDerivedMethodGraph ],
function( G )
  return Concatenation( "<", String( G ), ">" );
end );

InstallGlobalFunction( AddDerivation,

  function( graph, target_op, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, is_with_given_derivation, is_autogenerated_by_CompilerForCAP )
    local target_op_name, derivation, x;

    target_op_name := NameFunction( target_op );

    derivation := CreateDerivation(
        target_op_name,
        description,
        used_ops_with_multiples_and_category_getters,
        func,
        weight,
        category_filter,
        loop_multiplier,
        category_getters
    );

    if function_called_before_installation <> false then

        SetFunctionCalledBeforeInstallation( derivation, function_called_before_installation );

    fi;

    derivation!.is_with_given_derivation := is_with_given_derivation;
    derivation!.is_autogenerated_by_CompilerForCAP := is_autogenerated_by_CompilerForCAP;

    if derivation!.is_with_given_derivation and derivation!.is_autogenerated_by_CompilerForCAP then

        Error( "WithGiven derivations should not be marked as being autogenerated by CompilerForCAP" );

    fi;

    Add( graph!.derivations_by_target.(target_op_name), derivation );
    derivation!.position_in_derivations_by_target := Length( graph!.derivations_by_target.(target_op_name) );

    for x in UsedOperationsWithMultiplesAndCategoryGetters( derivation ) do
        # We add all operations, even those with category getters: In case the category getter
        # returns the category itself, this allows to recursively trigger derivations correctly.
        Add( graph!.derivations_by_used_ops.(x[1]), derivation );
    od;

    if IsEmpty( UsedOperationsWithMultiplesAndCategoryGetters( derivation ) ) then

        Add( graph!.derivations_by_used_ops.none, derivation );

    fi;

end );

BindGlobal( "CAP_INTERNAL_DERIVATION_GRAPH", MakeDerivationGraph( [ ] ) );

InstallGlobalFunction( AddDerivationToCAP, FunctionWithNamedArguments(
  [
    # When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
    # However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
    [ "Weight", 1 ],
    [ "CategoryFilter", IsCapCategory ],
    [ "WeightLoopMultiple", 2 ],
    [ "CategoryGetters", Immutable( rec( ) ) ],
    [ "FunctionCalledBeforeInstallation", false ],
    [ "is_with_given_derivation", false ],
    [ "is_autogenerated_by_CompilerForCAP", false ],
  ],
  function( CAP_NAMED_ARGUMENTS, target_op, description, used_ops_with_multiples_and_category_getters, func )
    local weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, option_is_with_given_derivation, option_is_autogenerated_by_CompilerForCAP;

    weight := CAP_NAMED_ARGUMENTS.Weight;
    category_filter := CAP_NAMED_ARGUMENTS.CategoryFilter;
    loop_multiplier := CAP_NAMED_ARGUMENTS.WeightLoopMultiple;
    category_getters := CAP_NAMED_ARGUMENTS.CategoryGetters;
    function_called_before_installation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation;
    option_is_with_given_derivation := CAP_NAMED_ARGUMENTS.is_with_given_derivation;
    option_is_autogenerated_by_CompilerForCAP := CAP_NAMED_ARGUMENTS.is_autogenerated_by_CompilerForCAP;

    AddDerivation( CAP_INTERNAL_DERIVATION_GRAPH, target_op, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, option_is_with_given_derivation, option_is_autogenerated_by_CompilerForCAP );

end ) );

InstallMethod( DerivationsUsingOperation,
               [ IsDerivedMethodGraph, IsString ],
function( G, op_name )
  return G!.derivations_by_used_ops.( op_name );
end );

InstallMethod( DerivationsOfOperation,
               [ IsDerivedMethodGraph, IsString ],
function( G, op_name )
  return G!.derivations_by_target.( op_name );
end );

InstallMethod( MakeOperationWeightList,
               [ IsCapCategory, IsDerivedMethodGraph ],
function( C, G )
  local operation_weights, operation_derivations, owl, op_name;

    operation_weights := rec( );
    operation_derivations := rec( );

    for op_name in Operations( G ) do
        operation_weights.( op_name ) := infinity;
        operation_derivations.( op_name ) := fail;
    od;

    owl := ObjectifyWithAttributes(
        rec( operation_weights := operation_weights, operation_derivations := operation_derivations ), TheTypeOfOperationWeightLists,
        DerivationGraph, G,
        CategoryOfOperationWeightList, C
    );

    return owl;

end );

InstallMethod( String,
               [ IsOperationWeightList ],
function( owl )
  return Concatenation( "operation weight list for ",
                        String( CategoryOfOperationWeightList( owl ) ) );
end );

InstallMethod( ViewString,
               [ IsOperationWeightList ],
function( owl )
  return Concatenation( "<", String( owl ), ">" );
end );

InstallMethod( CurrentOperationWeight,
               [ IsOperationWeightList, IsString ],
function( owl, op_name )
  return owl!.operation_weights.( op_name );
end );

InstallMethod( OperationWeightUsingDerivation,
               [ IsOperationWeightList, IsDerivedMethod ],
function( owl, d )
  local category, category_operation_weights, weight, operation_weights, operation_weight, x;

    category := CategoryOfOperationWeightList( owl );
    category_operation_weights := owl!.operation_weights;

    weight := AdditionalWeight( d );

    for x in UsedOperationsWithMultiplesAndCategoryGetters( d ) do

        if x[3] = fail then

            operation_weights := category_operation_weights;

        else

            operation_weights := x[3](category)!.derivations_weight_list!.operation_weights;

            # the category `x[3](category)` might have been finalized before the operation `x[1]` was added to CAP
            if not IsBound( operation_weights.(x[1]) ) then

                return infinity;

            fi;

        fi;

        operation_weight := operation_weights.(x[1]);

        if operation_weight = infinity then

            return infinity;

        fi;

        weight := weight + operation_weight * x[2];

    od;

    return weight;

end );

InstallMethod( DerivationOfOperation,
               [ IsOperationWeightList, IsString ],
function( owl, op_name )
  return owl!.operation_derivations.( op_name );
end );

BindGlobal( "TryToTriggerDerivation", function ( owl, d )
  local new_weight, target, current_weight, current_derivation;

    if not IsApplicableToCategory( d, CategoryOfOperationWeightList( owl ) ) then
        return fail;
    fi;

    new_weight := OperationWeightUsingDerivation( owl, d );

    if new_weight = infinity then
        return fail;
    fi;

    target := TargetOperation( d );

    current_weight := CurrentOperationWeight( owl, target );
    current_derivation := DerivationOfOperation( owl, target );

    if new_weight < current_weight or (new_weight = current_weight and current_derivation <> fail and d!.position_in_derivations_by_target < current_derivation!.position_in_derivations_by_target) then

        Info( DerivationInfo, 1, Concatenation( "derive(",
                                                String( new_weight ),
                                                ") ",
                                                target,
                                                ": ",
                                                Description( d ), "\n" ) );

        owl!.operation_weights.( target ) := new_weight;
        owl!.operation_derivations.( target ) := d;

        # if the weight has not changed, there is no need to re-trigger the chain of derivations
        if new_weight <> current_weight then

            TriggerDerivationsUsingOperation( owl, target );

        fi;

    fi;

end );

InstallMethod( TriggerDerivationsUsingOperation,
               [ IsOperationWeightList, IsString ],
function( owl, op_name )
  local d;

    for d in DerivationsUsingOperation( DerivationGraph( owl ), op_name ) do

        TryToTriggerDerivation( owl, d );

    od;

end );

InstallMethod( Reevaluate,
               [ IsOperationWeightList ],
function( owl )
  local new_weight, op_name, d;

    for op_name in Operations( DerivationGraph( owl ) ) do

        for d in DerivationsOfOperation( DerivationGraph( owl ), op_name ) do

            TryToTriggerDerivation( owl, d );

        od;

    od;

end );

InstallMethod( Saturate,
               [ IsOperationWeightList ],
  function( owl )
    local current_weight_list;

    while true do
        current_weight_list := StructuralCopy( owl!.operation_weights );
        Reevaluate( owl );
        if current_weight_list = owl!.operation_weights then
            break;
        fi;
    od;

end );

InstallMethod( AddPrimitiveOperation,
               [ IsOperationWeightList, IsString, IsInt ],
function( owl, op_name, new_weight )

    owl!.operation_weights.( op_name ) := new_weight;
    Assert( 0, owl!.operation_derivations.( op_name ) = fail );

end );

InstallMethod( PrintDerivationTree,
               [ IsOperationWeightList, IsString ],
function( owl, op_name )
  local print_node, get_children;
  print_node := function( node )
    local w, mult, op, d;
    mult := node[ 2 ];
    op := node[ 1 ];
    if op = fail then
      Print( "  ", mult );
      return;
    fi;
    w := CurrentOperationWeight( owl, op );
    d := DerivationOfOperation( owl, op );
    if mult <> fail then
      Print( "+ ", mult, " * " );
    fi;
    if w = infinity then
      Print( "(not installed)" );
    else
      Print( "(", w, ")" );
    fi;
    Print( " ", op );
    if w <> infinity then
      Print( " " );
      if d = fail then
        Print( "[primitive]" );
      else
        Print( "[derived:", Description( d ), "]" );
      fi;
    fi;
  end;
  get_children := function( node )
    local op, d;
    op := node[ 1 ];
    if op = fail then
      return [];
    fi;
    d := DerivationOfOperation( owl, op );
    if d = fail then
      return [];
    else
      return Concatenation( [ [ fail, AdditionalWeight( d ) ] ],
                            UsedOperationsWithMultiplesAndCategoryGetters( d ) );
    fi;
  end;
  PrintTree( [ op_name, fail ],
             print_node,
             get_children );
end );

InstallMethod( PrintTree,
               [ IsObject, IsFunction, IsFunction ],
function( root, print_node, get_children )
  PrintTreeRec( root, print_node, get_children, 0 );
end );

InstallMethod( PrintTreeRec,
               [ IsObject, IsFunction, IsFunction, IsInt ],
function( node, print_node, get_children, level )
  local i, child;
  for i in [ 1 .. level ] do
    Print( "   " );
  od;
  print_node( node );
  Print( "\n" );
  for child in get_children( node ) do
    PrintTreeRec( child, print_node, get_children, level + 1 );
  od;
end );

#################################
##
## Final derivations
##
#################################

InstallValue( CAP_INTERNAL_FINAL_DERIVATION_LIST, [ ] );

InstallGlobalFunction( AddFinalDerivation, FunctionWithNamedArguments(
  [
    # When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
    # However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
    [ "Weight", 1 ],
    [ "CategoryFilter", IsCapCategory ],
    [ "WeightLoopMultiple", 2 ],
    [ "CategoryGetters", Immutable( rec( ) ) ],
    [ "FunctionCalledBeforeInstallation", false ],
  ],
  function( CAP_NAMED_ARGUMENTS, target_op, description, can_compute, cannot_compute, func )

    AddFinalDerivationBundle(
        description, can_compute, cannot_compute, [ target_op, can_compute, func ] :
        Weight := CAP_NAMED_ARGUMENTS.Weight,
        CategoryFilter := CAP_NAMED_ARGUMENTS.CategoryFilter,
        WeightLoopMultiple := CAP_NAMED_ARGUMENTS.WeightLoopMultiple,
        CategoryGetters := CAP_NAMED_ARGUMENTS.CategoryGetters,
        FunctionCalledBeforeInstallation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation
    );

end ) );

InstallGlobalFunction( AddFinalDerivationBundle, FunctionWithNamedArguments(
  [
    # When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
    # However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
    [ "Weight", 1 ],
    [ "CategoryFilter", IsCapCategory ],
    [ "WeightLoopMultiple", 2 ],
    [ "CategoryGetters", Immutable( rec( ) ) ],
    [ "FunctionCalledBeforeInstallation", false ],
  ],
  function( CAP_NAMED_ARGUMENTS, description, can_compute, cannot_compute, additional_functions... )
    local weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, operations_to_install, union_of_collected_lists, derivations, derivation, used_op_names_with_multiples_and_category_getters, dummy_derivation, final_derivation, i, x, current_additional_func;

    weight := CAP_NAMED_ARGUMENTS.Weight;
    category_filter := CAP_NAMED_ARGUMENTS.CategoryFilter;
    loop_multiplier := CAP_NAMED_ARGUMENTS.WeightLoopMultiple;
    category_getters := CAP_NAMED_ARGUMENTS.CategoryGetters;
    function_called_before_installation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation;

    if IsEmpty( additional_functions ) then

        Error( "trying to add a final derivation without any functions to install" );

    fi;

    for i in [ 1 .. Length( additional_functions ) ] do

        if not (IsList( additional_functions[i] ) and Length( additional_functions[i] ) = 3) then

            Error( "additional functions must be given as triples [ <operation>, <preconditions>, <function> ]" );

        fi;

        if IsList( Last( additional_functions[i] ) ) then

            Error( "passing lists of functions to `AddFinalDerivation` is not supported anymore" );

        fi;

        if not additional_functions[i][1] in cannot_compute then

            Print( "WARNING: A final derivation installs ", NameFunction( additional_functions[i][1] ), " but does not list it in its exclude list.\n" );

        fi;

    od;

    for x in can_compute do

        if Length( x ) < 2 or not IsFunction( x[1] ) or not IsInt( x[2] ) then

            Error( "preconditions must be of the form `[op, mult, getter]`, where `getter` is optional" );

        fi;

        # check that preconditions do not appear in cannot_compute (which in particular includes all operations installed by this final derivation, as checked above)
        if (Length( x ) = 2 or (Length( x ) = 3 and x[3] = fail)) and x[1] in cannot_compute then

            Error( "A final derivation for ", NameFunction( additional_functions[1][1] ), " has precondition ", NameFunction( x[1] ), " which is also in its exclude list.\n" );

        fi;

    od;

    if Length( additional_functions ) = 1 and StartsWith( NameFunction( additional_functions[1][1] ), "IsomorphismFrom" ) then

        Print( "WARNING: You are installing a final derivation for ", NameFunction( additional_functions[1][1] ), " which does not include its inverse. You should probably use a bundled final derivation to also install its inverse.\n" );

    fi;

    ## Find symbols in functions
    operations_to_install := [ ];

    union_of_collected_lists := [ ];

    derivations := [ ];

    for current_additional_func in additional_functions do

        derivation := CreateDerivation(
            NameFunction( current_additional_func[1] ),
            Concatenation( description, " (final derivation)" ),
            current_additional_func[2],
            current_additional_func[3],
            weight,
            category_filter,
            loop_multiplier,
            category_getters
        );

        Add( derivations, derivation );

        used_op_names_with_multiples_and_category_getters := UsedOperationsWithMultiplesAndCategoryGetters( derivation );

        # Operations may use operations from the same final derivation as long as the latter are installed before the former.
        # In this case, the used operations are no preconditions and thus should not go into union_of_collected_lists.
        used_op_names_with_multiples_and_category_getters := Filtered( used_op_names_with_multiples_and_category_getters, x -> not x[1] in operations_to_install );

        Add( operations_to_install, NameFunction( current_additional_func[1] ) );

        union_of_collected_lists := CAP_INTERNAL_MERGE_PRECONDITIONS_LIST( union_of_collected_lists, used_op_names_with_multiples_and_category_getters );

    od;

    # only used to check if we can install all the derivations in `derivations`
    dummy_derivation := CreateDerivation(
        "internal dummy function of a final derivation",
        "dummy derivation",
        can_compute,
        ReturnTrue,
        1,
        category_filter,
        loop_multiplier,
        category_getters
    );

    used_op_names_with_multiples_and_category_getters := UsedOperationsWithMultiplesAndCategoryGetters( dummy_derivation );

    if Length( union_of_collected_lists ) <> Length( used_op_names_with_multiples_and_category_getters ) or not ForAll( union_of_collected_lists, c -> c in used_op_names_with_multiples_and_category_getters ) then

        used_op_names_with_multiples_and_category_getters := ShallowCopy( used_op_names_with_multiples_and_category_getters );

        SortBy( used_op_names_with_multiples_and_category_getters, x -> x[1] );
        SortBy( union_of_collected_lists, x -> x[1] );

        Print(
            "WARNING: You have installed a final derivation for ", TargetOperation( derivations[1] ), " with preconditions ", used_op_names_with_multiples_and_category_getters,
            " but the following list of preconditions was expected: ", union_of_collected_lists, ".\n",
            "If this is a bug in the automated detection, please report it.\n"
        );

    fi;

    final_derivation := rec(
        dummy_derivation := dummy_derivation,
        cannot_compute := List( cannot_compute, x -> NameFunction( x ) ),
        derivations := derivations,
        function_called_before_installation := function_called_before_installation,
    );

    Add( CAP_INTERNAL_FINAL_DERIVATION_LIST, final_derivation );

end ) );

#################################
##
## Installing derivations
##
#################################

InstallGlobalFunction( InstallDerivations, function( category )
  local weight_list, derivation_list, current_install, current_final_derivation, op_name, new_weight, current_weight, i, derivation, operation;

    weight_list := MakeOperationWeightList( category, CAP_INTERNAL_DERIVATION_GRAPH );

    category!.derivations_weight_list := weight_list;

    for op_name in RecNames( category!.operations ) do

        Assert( 0, category!.operations.(op_name).type in [ "primitive_installation", "precompiled_derivation" ] );

        AddPrimitiveOperation( weight_list, op_name, category!.operations.(op_name).weight );

    od;

    # Trigger ordinary derivations, but do not install them yet:
    # While triggering derivations, cheaper derivations can become available, but we do not want to overwrite methods.

    TriggerDerivationsUsingOperation( weight_list, "none" );

    for op_name in SortedList( RecNames( weight_list!.operation_weights ) ) do

        if weight_list!.operation_weights.(op_name) <> infinity and weight_list!.operation_derivations.(op_name) = fail then

            Info( DerivationInfo, 1, Concatenation( "add(",
                                                    String( weight_list!.operation_weights.(op_name) ),
                                                    ") ",
                                                    op_name,
                                                    ": primitive installation\n" ) );

            TriggerDerivationsUsingOperation( weight_list, op_name );

        fi;

    od;

    # Trigger and install final derivations

    derivation_list := ShallowCopy( CAP_INTERNAL_FINAL_DERIVATION_LIST );

    while true do

        current_install := fail;

        for i in [ 1 .. Length( derivation_list ) ] do

            current_final_derivation := derivation_list[ i ];

            # check if all conditions for installing the final derivation are met

            if not IsApplicableToCategory( current_final_derivation.dummy_derivation, category ) then

                continue;

            fi;

            if ForAny( current_final_derivation.cannot_compute, operation_name -> CurrentOperationWeight( weight_list, operation_name ) < infinity ) then

                continue;

            fi;

            if OperationWeightUsingDerivation( weight_list, current_final_derivation.dummy_derivation ) = infinity then

                continue;

            fi;

            # if we get here, everything matched
            current_install := i;
            break;

        od;

        if current_install = fail then

            break;

        else

            current_final_derivation := Remove( derivation_list, current_install );

            ## call function before adding the method

            if current_final_derivation.function_called_before_installation <> false then

                current_final_derivation.function_called_before_installation( category );

            fi;

            for derivation in current_final_derivation.derivations do

                op_name := TargetOperation( derivation );
                new_weight := OperationWeightUsingDerivation( weight_list, derivation );
                current_weight := CurrentOperationWeight( weight_list, op_name );

                Assert( 0, new_weight <> infinity );

                # When installing a final derivation bundle, the installation of the first operations in the bundle
                # might trigger (normal) derivations of later operations it the bundle, which might be cheaper then
                # the derivations provided in the bundle.
                if new_weight <= current_weight then

                    Info( DerivationInfo, 1, Concatenation( "derive(",
                                                            String( new_weight ),
                                                            ") ",
                                                            op_name,
                                                            ": ",
                                                            Description( derivation ), "\n" ) );

                    weight_list!.operation_weights.( op_name ) := new_weight;
                    weight_list!.operation_derivations.( op_name ) := fail;

                    InstallDerivationForCategory( derivation, new_weight, category : IsFinalDerivation := true );

                    # if the weight has not changed, there is no need to re-trigger the chain of derivations
                    if new_weight <> current_weight then

                        TriggerDerivationsUsingOperation( weight_list, op_name );

                    fi;

                fi;

            od;

        fi;

    od;

    # Actually install ordinary derivations

    for operation in Operations( DerivationGraph( weight_list ) ) do

        if DerivationOfOperation( weight_list, operation ) <> fail then

            InstallDerivationForCategory( DerivationOfOperation( weight_list, operation ), CurrentOperationWeight( weight_list, operation ), category );

        fi;

    od;

end );

#################################
##
## Some print functions
##
#################################

##
InstallGlobalFunction( InstalledMethodsOfCategory,

  function( cell )
    local weight_list, list_of_methods, i, current_weight, can_compute, cannot_compute;

    if IsCapCategory( cell ) then
        weight_list := cell!.derivations_weight_list;
    elif IsCapCategoryCell( cell ) then
        weight_list := CapCategory( cell )!.derivations_weight_list;
    else
        Error( "Input must be a category or a cell" );
    fi;

    list_of_methods := Operations( CAP_INTERNAL_DERIVATION_GRAPH );

    list_of_methods := AsSortedList( list_of_methods );

    can_compute := [ ];
    cannot_compute := [ ];

    for i in list_of_methods do

        current_weight := CurrentOperationWeight( weight_list, i );

        if current_weight < infinity then
            Add( can_compute, [ i, current_weight ] );
        else
            Add( cannot_compute, i );
        fi;

    od;

    Print( "Can do the following basic methods at the moment:\n" );

    for i in can_compute do
        Print( "+ ", i[ 1 ], ", weight ", String( i[ 2 ] ), "\n" );
    od;

    Print( "\nThe following is still missing:\n" );

    for i in cannot_compute do
        Print( "- ", i, "\n" );
    od;

    Print( "\nPlease use DerivationsOfMethodByCategory( <category>, <name> ) to get\n",
           "information about how to add the missing methods\n" );

end );

##
InstallGlobalFunction( DerivationsOfMethodByCategory,

  function( category, name )
    local current_derivation, currently_installed_func, weight_list, category_getter_string, possible_derivations, category_filter, weight, found, x, final_derivation;

    if IsFunction( name ) then
        name := NameFunction( name );
    fi;

    if not IsString( name ) then
        Error( "Usage is <category>,<string> or <category>,<CAP operation>\n" );
        return;
    fi;

    if not IsBound( CAP_INTERNAL_METHOD_NAME_RECORD.(name) ) then
        Error( name, " is not the name of a CAP operation." );
        return;
    fi;

    if CanCompute( category, name ) then

        Print( Name( category ), " can already compute ", TextAttr.b4, name, TextAttr.reset, " with weight " , OperationWeight( category, name ), ".\n" );

        if category!.operations.( name ).type = "primitive_installation" then

            Print( "It was installed primitively.\n" );

        elif category!.operations.( name ).type = "final_derivation" then

            Print( "It was installed as a final derivation.\n" );

        elif category!.operations.( name ).type = "precompiled_derivation" then

            Print( "It was installed as a precompiled derivation.\n" );

        elif category!.operations.( name ).type = "ordinary_derivation" then

            current_derivation := DerivationOfOperation( category!.derivations_weight_list, name );

            Print( "It was derived by ", TextAttr.b3, Description( current_derivation ), TextAttr.reset, " using \n" );

            for x in UsedOperationsWithMultiplesAndCategoryGetters( current_derivation ) do

                if x[3] = fail then

                    weight_list := category!.derivations_weight_list;
                    category_getter_string := "";

                else

                    weight_list := x[3](category)!.derivations_weight_list;
                    category_getter_string := Concatenation( " in category obtained by applying ", String( x[3] ) );

                fi;

                Print( "* ", TextAttr.b2, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string );
                Print( " installed with weight ", String( CurrentOperationWeight( weight_list, x[1] ) ) );
                Print( "\n" );

            od;

            Assert( 0, IsIdenticalObj( category!.operations.( name ).func, DerivationFunction( current_derivation ) ) );

        else

            Error( "this should never happen" );

        fi;

        currently_installed_func := category!.operations.( name ).func;

        Print( "\nThe following function was installed for this operation:\n\n" );
        Display( currently_installed_func );
        Print( "\n" );
        Print( "Source: ", FilenameFunc( currently_installed_func ), ":", StartlineFunc( currently_installed_func ), "\n" );
        Print( "\n" );
        Print( "#######\n\n" );

    else

        Print( TextAttr.b4, name, TextAttr.reset, " is currently not installed for ", Name( category ), ".\n\n" );

    fi;

    Print( "Possible derivations are:\n\n" );

    possible_derivations := List( DerivationsOfOperation( CAP_INTERNAL_DERIVATION_GRAPH, name ), d -> rec( derivation := d ) );

    for final_derivation in CAP_INTERNAL_FINAL_DERIVATION_LIST do

        for current_derivation in final_derivation.derivations do

            if TargetOperation( current_derivation ) = name then

                Add( possible_derivations, rec(
                    derivation := current_derivation,
                    can_compute := UsedOperationsWithMultiplesAndCategoryGetters( final_derivation.dummy_derivation ),
                    cannot_compute := final_derivation.cannot_compute,
                ) );

            fi;

        od;

    od;

    for current_derivation in possible_derivations do

        category_filter := CategoryFilter( current_derivation.derivation );

        # `SizeScreen()[1] - 3` is taken from the code for package banners
        Print( ListWithIdenticalEntries( SizeScreen()[1] - 3, '-' ), "\n" );
        if category_filter( category ) then
            Print( TextAttr.b4, name, TextAttr.reset, " can be derived by\n" );
        else
            if IsFilter( category_filter ) then
                Print( "If ", Name( category ), " would be ", JoinStringsWithSeparator( Filtered( NamesFilter( category_filter ), name -> not StartsWith( name, "Has" ) ), " and " ) );
            else
                Print( "If ", Name( category ), " would fulfill the conditions given by\n\n" );
                Display( category_filter );
            fi;
            Print( "\nthen ", TextAttr.b4, name, TextAttr.reset, " could be derived by\n" );
        fi;

        for x in UsedOperationsWithMultiplesAndCategoryGetters( current_derivation.derivation ) do

            if x[3] = fail then

                if CanCompute( category, x[1] ) then

                    weight := OperationWeight( category, x[1] );

                else

                    weight := infinity;

                fi;

                category_getter_string := "";

            else

                if category_filter( category ) and CanCompute( x[3](category), x[1] ) then

                    weight := OperationWeight( x[3](category), x[1] );

                else

                    weight := infinity;

                fi;

                category_getter_string := Concatenation( " in the category obtained by applying ", String( x[3] ) );

            fi;

            if weight < infinity then
                Print( "* ", TextAttr.b2, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string, ", (already installed with weight ", weight,")" );
            else
                Print( "* ", TextAttr.b1, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string );
            fi;

            Print( "\n" );

        od;

        Print( "with additional weight ", AdditionalWeight( current_derivation.derivation ) );

        Assert( 0, IsBound( current_derivation.can_compute ) = IsBound( current_derivation.cannot_compute ) );

        if IsBound( current_derivation.can_compute ) then

            Print( "\n\nas a final derivation\nif the following additional operations could be computed\n" );

            found := false;

            for x in current_derivation.can_compute do

                if x[3] = fail then

                    if CanCompute( category, x[1] ) then

                        weight := OperationWeight( category, x[1] );

                    else

                        weight := infinity;

                    fi;

                    category_getter_string := "";

                else

                    if category_filter( category ) and CanCompute( x[3](category), x[1] ) then

                        weight := OperationWeight( x[3](category), x[1] );

                    else

                        weight := infinity;

                    fi;

                    category_getter_string := Concatenation( " in the category obtained by applying ", String( x[3] ) );

                fi;

                if weight = infinity then

                    Print( "* ", x[1], category_getter_string, "\n" );
                    found := true;

                fi;

            od;

            if not found then

                Print( "(none)\n" );

            fi;

            Print( "\nand the following additional operations could not be computed\n" );

            found := false;

            for x in current_derivation.cannot_compute do

                if CanCompute( category, x ) then

                    Print( "* ", x, "\n" );
                    found := true;

                fi;

            od;

            if not found then

                Print( "(none)\n" );

            fi;

        else

            Print( ".\n" );

        fi;

        Print( "\n" );

    od;

end );

Quelle Derivations.gi Sprache: unbekannt

[ Dauer der Verarbeitung: 0.21 Sekunden (vorverarbeitet) ]