text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

NewRulesFor(TS, rec(
    TS_vect := rec(
        forTransposition := false,
        applicable := t -> t.isTag(1, AVecReg) and IsInt(t.params[1] / t.firstTag().v),
        apply := (t, C, Nonterms) -> let(
            v := t.firstTag().v,
            N := t.params[1],
            VS(N, v)
        )
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

isXchain := (o,dot) ->
    Same(ObjId(o), fTensor) and Same(ObjId(o.child(1)), fId) and
    ForAll(Drop(o.children(),1), c->Same(ObjId(c), fXbase) and Same(dot, c.params[4]));

mergeXchains := function(v, c1, c2)
    local terms, i, t, other;
    terms := [ Copy(c2.child(1)) ];
    for t in Drop(c2.children(),1) do
        Add(terms,
	    fXbase(t.params[1], t.params[2], t.params[3], v));
    od;

    other := c2.child(c2.numChildren());
    for i in [2 .. c1.numChildren()] do
       t := c1.child(i);
       Add(terms,
	   fXbase(t.params[1], t.params[2], t.params[3] + other.params[2] + other.params[3], v));
    od;
    return fTensor(terms);
end;

# ===================================================================
# fXbase and fDot
# ===================================================================
RewriteRules(RulesFuncSimp, rec(
  # fCompose  [[IP, @(1), J], [fTensor, fId, fBase]],
  IP_toXbase := ARule(fCompose,
     [ [ IP, @(1), @(2,J) ], [ fTensor, @(3,fId, e -> e.params[1] = @(1).val / @(2).val.params[1]),
	                                @(4,fBase, e -> e.params[1] = @(2).val.params[1]) ] ],
     e -> let(v:=Ind(),
	 [ fDot(v, fTensor(@(3).val, fXbase(@(2).val.params[1], @(4).val.params[2], 0, v))) ])
  ),

  IP_toYbase := ARule(fCompose,
     [ [ IP, @(1), [@(2,OS), @, -1] ], [ fTensor, @(3,fId, e -> e.params[1] = @(1).val / @(2).val.params[1]),
	                                          @(4,fBase, e -> e.params[1] = @(2).val.params[1]) ] ],
     e -> let(v:=Ind(),
	 [ fDot(v, fTensor(@(3).val, fYbase(@(2).val.params[1], @(4).val.params[2], 0, v))) ])
  ),

 # fCompose, [ fDot, [fTensor, fId, fXbase] ]
 #	     [ fDot, [fTensor, @,   fXbase] ]
 MergeXchains1 := ARule(fCompose,
       [ [ fDot, @(1),
	     [ fTensor, fId, [@(10,fXbase), @, @, zero, @.cond(e->Same(e, @(1).val)) ]]],
	 [ @(30,fDot), @(3),
	     [ fTensor, ..., [@(20,fXbase), @, @,    @, @.cond(e->Same(e, @(3).val)) ]]] ],

 e -> let(v:=IndNR(), f:=@(10).val, g:=@(20).val,
	  dots:=DropLast(@(30).val.params[2].children(), 1),
     [ fDot(v, fTensor(dots,
	               fXbase(g.params[1], g.params[2], g.params[3], v),
		       fXbase(f.params[1], f.params[2], g.params[2] + g.params[3], v))) ])
 ),

 # fDot X fDot -> fDot
 MergeXchains2 := ARule(fCompose,
    [ [ fDot, @(1), @(2).cond(e->isXchain(e,@(1).val)) ],
      [ fDot, @(3), @(4).cond(e->isXchain(e,@(3).val)) ] ],
 e -> let(v:=Ind(),
	 [ fDot(v, fTensor( mergeXchains(v, @(2).val, @(4).val))) ])
 )
));

Class(RulesDot, RuleSet);
RewriteRules(RulesDot, rec(
  IP_toYbase := ARule(fCompose,
     [ [ IP, @(1), [@(2,OS), @, -1] ], [ fTensor, @(3,fId, e -> e.params[1] = @(1).val / @(2).val.params[1]),
	                                          @(4,fBase, e -> e.params[1] = @(2).val.params[1]) ] ],
     e -> let(v:=Ind(),
	 [ fDot(v, fTensor(@(3).val, fYbase(@(2).val.params[1], @(4).val.params[2], 0, v))) ])
  )
));

ext: gi


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

NewRulesFor(TRDiag, rec(
    # TRDiag is a tall matrix.
    # TRDiag.transpose() is a wide matrix
    #
    TRDiag_Vec := rec(
        forTransposition := true,
	requiredFirstTag := [AVecReg, AVecRegCx],
        applicable := t -> not AnySyms(t.params[1], t.params[2]),

        apply := (t, C, Nonterms) -> let(
            v := t.firstTag().v,
            N := t.params[1],
            n := t.params[2],
            nv := _roundup(n, v),

            VScat_zero(N/v, nv/v, v) *
	    VDiag(fStretch(t.params[3], nv, n), v) *
	    VGath_pc(n, n, 0, v)
        )
    ),

    TRDiag_VecN := rec(
        forTransposition := true,
	requiredFirstTag := [AVecReg, AVecRegCx],
        applicable := t -> true, #AnySyms(t.params[1], t.params[2]),

        apply := (t, C, Nonterms) -> let(
            v := t.firstTag().v,
            N := t.params[1],
            n := t.params[2],
            ndiv := idiv(n, v),
	    nmod := imod(n, v),
	    nmodrem := imod(v-nmod, v),
	    j := Ind(ndiv),

	    # * NOTE: redundant zero-padding operations when transposing the below
	    #   VGath_zero/VScat_zero type operations fix this
	    # * Virtual pad seems to be a hack
	    # * O.toloop() should be implemented, VO is missing
	    # * Middle summand is super ugly, use ScatGath?
	    #
	    SUM(
		VirtualPad(N, n,
		    ISum(j, j.range,
			VScat(HH(N/v, ndiv, 0, [1]), v) *
			VDiag(fCompose(t.params[3], fAdd(n, ndiv*v, j*v)), v) *
			VGath(HH(n/v, ndiv, 0, [1]), v))),

		# Below could be simplified, because the block completely disappears
		# when nmod==0
		Scat(HH(N, nmod+nmodrem, ndiv*v, [1])) *
		VStack(
		    Diag(fCompose(t.params[3], fAdd(n, nmod, ndiv*v))).toloop(1),
		    O(nmodrem, nmod) # XXX NOTE: should have O.toloop() here
		) *
		Gath(HH(n, nmod, ndiv*v, [1])),

                VirtualPad(N, n,
		    VScat_zero(idiv(N,v), idiv(N,v)-ndiv, 0, v)) # XXX NOTE: VScat_zero needs to take 4th parameter (here it is 2nd) which is the scatter offset. This code won't work until VScat_zero is patched.
	    )
        )
    )
 ));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

########################################################
#   Machinery for being able to translate
#   vector-sigma-sums into vector code
########################################################

vref := (loc, idx, vlen) -> When(vlen=1,
    nth(loc, idx),
    nth(tcast(TPtr(TVect(loc.t.t, vlen)), loc), idx/vlen));

nth.toPtr := (self, t) >> let(
    exp := When(IsPtrT(self.loc.t), self.loc, tcast(self.loc.t.toPtrType(), self.loc)) + self.idx,
    exp_t := exp.t,
    new_t := When( IsPtrT(exp_t), TPtr(t, exp_t.qualifiers).withAlignment(exp_t), TPtr(t)),
    When(new_t=exp_t, exp, tcast(new_t, exp))
);

DeclareVars := function(code)
    local vars, vects,good;

    vars  := Set(List(Collect(code, [assign, @(1,var), @]),     e->e.loc));
    vects := Set(List(Collect(code, [assign, [vref,@(1,var),@], @]), e->e.loc.loc));
    good:=Set(Flat(List(Collect(code, decl), e->e.vars)));
    SubtractSet(vects, good);
    SubtractSet(vects, Set([X,Y]));
    SubtractSet(vars, good);

    if Length(vars) > 0 then code := decl(vars, code); fi;
    if Length(vects) > 0 then code := decl(vects, code); fi;
    return code;
end;


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#   Debug functions -- where to put?
Import(spl, formgen, code, sigma);
VerifyRuleTreeSPL := rt -> let(t := rt.node, mt := MatSPL(t), mspl := MatSPL(SPLRuleTree(rt)), InfinityNormMat(mt-mspl));
VerifyRuleTreeSigmaSPL := (rt, opts) -> let(t := rt.node, mt := MatSPL(t), ms := MatSPL(SumsRuleTree(rt, opts)), InfinityNormMat(mt-ms));

_THRESHOLD := 1E-5;
_abs := i -> When(IsComplex(i), AbsComplex(i), AbsFloat(i));
ThresholdMat := arg -> MapMat(arg[1], i-> When(_abs(i) > When(Length(arg)=2, arg[2], _THRESHOLD),i , 0));

vm := x -> VisualizeMat(When(IsSPL(x), MatSPL(x), x), "");
vmt := x -> VisualizeMat(ThresholdMat(When(IsSPL(x), MatSPL(x), x)), "");


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# Here I try to be very clean, when defining functions.
# For example, no longer use .size since this often contains info from .params.
# Instead have explicit .domain / .range
# use checkParams instead of def, default def will just set .params
#

#F dLin(<N>, <a>, <b>, <t>) - interval -> diagonal linear scaling function
#F    f: i -> a*i + b,
#F    dom(f) = interval(0..N-1)
#F    range(f) = <t>, must be a type
#F
#F Example:
#F  spiral> dLin(8,1,1/2,TReal).tolist();
#F  [ 1/2, 3/2, 5/2, 7/2, 9/2, 11/2, 13/2, 15/2 ]
#F
Class(dLin, DiagFunc, rec(
    checkParams := (self, params) >> Checked(Length(params)=4,
	IsPosInt0Sym(params[1]), IsType(params[4]), params),
    lambda := self >> let(i:=Ind(self.params[1]), a := self.params[2], b := self.params[3],
	Lambda(i, a*i+b).setRange(self.params[4])),
    range := self >> self.params[4],
    domain := self >> self.params[1]
));

#F dOmega(<N>, <k>) - N-th root of unity diagonal function
#F   f : TInt -> Tcomplex : i -> omega(N, k*i)
#F
Class(dOmega, DiagFunc, rec(
    checkParams := (self, params) >> Checked(Length(params)=2,
	IsPosIntSym(params[1]), IsIntSym(params[2]), params),
    lambda := self >> let(i:=Ind(), Lambda(i, omega(self.params[1], self.params[2]*i)).setRange(TComplex)),
    range := self >> TComplex,
    domain := self >> TInt
));

Class(dOmegaPow, DiagFunc, rec(
    checkParams := (self, params) >> Checked(Length(params)=3,
	IsPosIntSym(params[1]), IsIntSym(params[2]), IsInt(params[3]), params),
    lambda := self >> let(i:=Ind(), Lambda(i, omega(self.params[1], (self.params[2]*i))^self.params[3]).setRange(TComplex)),
    range := self >> TComplex,
    domain := self >> TInt
));


text:
# Copyright 2018-2019, Carnegie Mellon University
# See LICENSE for details

#sin(a+b) = sin(a)cos(b) + cos(a)sin(b)
#cos(a+b) = cos(a)cos(b) - sin(a)sin(b)

# cos(a)x + sin(a)y
# cos(a+b)x + sin(a+b)y
# cos(a)cos(b)x - sin(a)sin(b)x + sin(a)cos(b)y + cos(a)sin(b)y
# cos(a)cos(b)x + sin(a)cos(b)y + cos(a)sin(b)y - sin(a)sin(b)x
# cos(b)[cos(a)x+sin(a)y] + sin(b)[cos(a)y-sin(a)x]

NewRulesFor(HF, rec(
  HF_dummy := rec(
    applicable := (self, nt) >> true,
    forTransposition := false,
    apply := (t, c, nt) ->
     let(
         size := When(IsArrayT(t.params[1].t), t.params[1].t.size, Rows(t.params[1])),
       GathH(8, size, t.params[2]*size, 1)
    )
  )
));

NewRulesFor(TForAllInd, rec(
  TForAllInd_loop := rec(
    forTransposition := false,
    applicable := (self, nt) >> true,
    children := nt -> [ [ nt.params[2].withTags(nt.getTags()) ] ],
    apply := (t, c, nt) ->
      let(i := t.params[1],
          IterVStack(i, i.range,
	    OLCompose(
	      c[1],
	      GathH(Cols(c[1]), Cols(c[1]), Cols(c[1])*i, 1)
	     )
	  )
      )
  )
));

NewRulesFor(TComputeDist, rec(
  TComputeDistBase := rec(
    apply := (t, c, nt) ->
      let(x := var.fresh_t("r", TReal), y:= var.fresh_t("r", TReal),
      OLCompose(
        Reduction(t.params[1], (a,b)->min(a,b), V(1000.0), False),
	BinOp(t.params[1], Lambda([x, y], add(x, y)))
      )
  ))
));

NewRulesFor(TForAnyInd, rec(
    TForAnyInd_loop := rec(
        forTransposition := false,
        applicable := (self, nt) >> true,
        children := nt -> [ [ nt.params[2].withTags(nt.getTags()) ] ],
        apply := (t, c, nt) ->
	   let(iter := t.params[1],
	     OLCompose(
	       Reduction(iter.range, (a,b)->logic_or(a,b), V(false),
	       a->eq(a, V(true))), IterVStack(iter, c[1]))),
    )
));

NewRulesFor(TInsidePoly, rec(
    TInsidePoly_EvalLinSys := rec(
        applicable := (self, nt) >> ObjId(nt.params[1]) = LinearSystem,
        forTransposition := false,
        children := nt -> [ [ TEvalLinSys(nt.params[1]).withTags(nt.getTags()) ] ],
        apply := (t, C, Nonterms) -> let(
            evalsys := C[1],
            i := Ind(Rows(evalsys)), x := var.fresh_t("r", TDouble),
            cmp0 := PointWise(Rows(evalsys), Lambda([x,i], leq(x, V(0)))),
            forall_op := Reduction(Rows(evalsys), (a,b)->logic_and(a,b), V(true), a->eq(a, V(false))),
            OLCompose(forall_op, cmp0, evalsys))
    )
));

NewRulesFor(TEvalLinSys, rec(
    TEvalLinSys_TMatVecProd := rec(
        applicable := (self, nt) >> ObjId(nt.params[1]) = LinearSystem,
        children := nt -> [ [ TMatVecProd(nt.params[1].mat).withTags(nt.getTags()) ] ],
        forTransposition := false,
        apply := (t, C, Nonterms) -> let(linsys := t.params[1], A := linsys.mat, b := linsys.rhs, n :=linsys.dims()[1],
            x := var.fresh_t("r", TDouble), i := Ind(n),
            OLCompose(PointWise(n, Lambda([x,i], sub(x, nth(b, i)))), C[1]))
    )
));

NewRulesFor(TMatVecProd, rec(
    TMatVecProd_Term := rec(
        applicable := (self, nt) >> true,
        forTransposition := false,
        apply := (t, C, Nonterms) -> let(mat := t.params[1], n := mat.dims()[1], m := mat.dims()[2], i := Ind(n),
            IterVStack(i, n, ScalarProd(m, nth(mat, i))))
    )
));

NewRulesFor(TInfinityNorm, rec(
    TInfinityNorm_Base := rec(
        applicable := True,
        forTransposition := false,
        apply := (t, C, Nonterms) -> let(n :=t.dims()[2],
            x := var.fresh_t("r", TDouble), i := Ind(n),
            OLCompose(Reduction(n, (a,b)->max(a,b), V(0.0), False), PointWise(n, Lambda([x,i], abs(x)))))
    )
));

NewRulesFor(TDistance, rec(
    TDistance_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [[nt.params[1]]],
        apply := (t, C, Nonterms) -> let(n :=C[1].dims()[2], x := var.fresh_t("r", TDouble), y := var.fresh_t("r", TDouble),
            OLCompose(C[1], BinOp(n, Lambda([x,y], sub(x,y)))))
    )
));

NewRulesFor(TEvalPolynomial, rec(
    TEvalPolynomial_Base := rec(
        applicable := True,
        forTransposition := false,
        apply := (t, C, Nonterms) -> let(n := t.params[1]+1, x := var.fresh_t("r", TDouble), y := var.fresh_t("r", TDouble),
            OLCompose(ScalarProd(n, t.params[2]), Induction(n, Lambda([x,y], mul(x, y)), V(1.0))))
    )
));

NewRulesFor(TLess, rec(
    TLess_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [nt.params],
        apply := (t, c, Nonterms) -> let(
			n :=t.dims()[1],
			x := var.fresh_t("r", TDouble),
			y := var.fresh_t("r", TDouble),
			OLCompose(
				BinOp(n, Lambda([x,y], lt(x,y))), DirectSum(c[1], c[2]) )
    )
)));

NewRulesFor(TGreater, rec(
    TGreater_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [nt.params],
        apply := (t, c, Nonterms) -> let(
      n :=t.dims()[1],
      x := var.fresh_t("r", TDouble),
      y := var.fresh_t("r", TDouble),
      OLCompose(
        BinOp(n, Lambda([x,y], gt(x,y))), DirectSum(c[1], c[2]) )
    )
)));

NewRulesFor(TLessEqual, rec(
    TLessEqual_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [nt.params],
        apply := (t, c, Nonterms) -> let(
      n :=t.dims()[1],
      x := var.fresh_t("r", TDouble),
      y := var.fresh_t("r", TDouble),
      OLCompose(
        BinOp(n, Lambda([x,y], leq(x,y))), DirectSum(c[1], c[2]) )
    )
)));

NewRulesFor(TGreaterEqual, rec(
    TGreaterEqual_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [nt.params],
        apply := (t, c, Nonterms) -> let(
      n :=t.dims()[1],
      x := var.fresh_t("r", TDouble),
      y := var.fresh_t("r", TDouble),
      OLCompose(
        BinOp(n, Lambda([x,y], geq(x,y))), DirectSum(c[1], c[2]) )
    )
)));

NewRulesFor(TEqual, rec(
    TEqual_Base := rec(
        applicable := True,
        forTransposition := false,
        children := nt -> [nt.params],
        apply := (t, c, Nonterms) -> let(
      n :=t.dims()[1],
      x := var.fresh_t("r", TDouble),
      y := var.fresh_t("r", TDouble),
      OLCompose(
        BinOp(n, Lambda([x,y], eq(x,y))), DirectSum(c[1], c[2]) )
    )
)));

NewRulesFor(TCond, rec(
	Cond_Base := rec(
		applicable := True,
		forTransposition := false,
		children := nt -> [nt.params],
		apply := (t, c, Nonterms) -> let(
			COND(c[1], c[2], c[3])
		)
	)
));

NewRulesFor(TConstant, rec(
    TConstant_Base := rec(
       applicable := True,
       forTransposition := false,
       children := nt -> [nt.params],
       apply := (t, C, Nonterms) -> let(x := var.fresh_t("r", TDouble), i := Ind(1), PointWise(1, Lambda([x, i], x)))
    )
));

max_stars_repo_name: spiral-software/spiral-package-hcol

max_issues_repo_name: spiral-software/spiral-package-hcol

max_forks_repo_name: spiral-software/spiral-package-hcol


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#F Rules
#F =====
#F
#F A rule is a record with the following mandatory fields:
#F
#F   isRule           = "true"         # identifies rules
#F   operations       = RuleOps        # operations record
#F   name             = <string>       # the name of the rule
#F   info             = <string>       # a string with info about the rule
#F   nonTerminal      = <symbol>       # the non-terminal the rule is meant
#F                                       for, given by its symbol (e.g. "WHT")
#F   forTransposition = true/false     # identifies whether the should also
#F                                       be used in its transposed form
#F   switch           = true/false     # allows to switch rules on (true) or off
#F   isApplicable     = func( params ) # rule applicable for params?
#F   allChildren      = func( params ) # returns a list of ordered lists of
#F                                       all possible children for the rule
#F   randomChildren   = func( params ) # returns an ordered list of children
#F                                       for the rule, chosen at random
#F   rule             =                # the actual rule, given as a formula
#F     func( params, children )          combining children
#F
#F The following are optional fields:
#F
#F The function .isDerivable checks whether a given set of children can
#F be derived from a given spl. This can also be decided by using doing
#F   children in .allChildren(spl.params)
#F In some cases, namely when there are to many children configurations,
#F this field should be present. It is only used in the function RuleTree
#F and nowhere during code generation.
#F
#F   isDerivable = func( spl, children )
#F
#F Note that the field "nonTerminal" must contain a symbol known
#F from the NonTerminalTable in spl.g
#F All rules have to be in the global variable RuleTable in order
#F to be used.
#F
#F
#F new rule:
#F    .children := nt -> list of ordered lists of all possible children
#F    .applicable := nt -> true/false
#F    .apply := (nt, children) -> apply the rule
#F    or .apply := (nt, children, child_nonterms) -> apply the rule
#F Functions for Rules
#F -------------------
#F

RuleOps := OperationsRecord("RuleOps");

#F IsRule( <rule> ) - true for breakdown rules (base class = BreakdownRule)
#F
IsRule := R -> IsRec(R) and IsBound(R.isRule) and R.isRule = true;

#F IsNewRule(<rule>) - true for new style rules (base class = NewBreakdownRule)
#F
IsNewRule := R -> IsRec(R) and IsBound(R.isRule) and R.isRule and IsBound(R.isNewRule) and R.isNewRule;

#F IsAlternativeRewriteRule(<rule>) - true for new style rules (base class = AlternativeRewriteRule)
#F
IsAlternativeRewriteRule := R -> IsRec(R) and IsBound(R.isRule) and R.isRule and IsBound(R.isAlternativeRewriteRule) and R.isAlternativeRewriteRule;

#F RuleOps.Print( <rule> ) -  prints the name of <rule>.
#F
RuleOps.Print:= R -> Print(R.name, Cond(IsBound(R.a), R.printA(), ""));

#F RuleOps.\=( <rule1>, <rule2> ) - equality of rules based on names
#F
RuleOps.\= := (R1, R2) -> IsRule(R1) and IsRule(R2) and R1.name = R2.name and
    When(IsBound(R1.a), R1.a = R2.a, true);

#F RuleOps.\<( <rule1>, <rule2> ) - ordering of rules based on their names.
#F
RuleOps.\< := (R1, R2) -> Cond(
    IsRule(R1) and IsRule(R2),
        R1.name < R2.name or (R1.name = R2.name and When(IsBound(R1.a), R1.a < R2.a, true)),
    ObjId(R1) < ObjId(R2));

# Default rule for SPLs which not non-terminals
Declare(@_Base);

_applicable := (R, nt, ruleset) ->
    (not Same(ruleset, ApplicableTable) or R.switch) and
    (R.nonTerminal=@ or R.nonTerminal = ObjId(nt)) and
    ((nt.transposed = R.transposed) or (nt.transpose()=nt)) and
    # R.requiredFirstTag is obsolete
    When(not IsNewRule(R) or not IsBound(R.requiredFirstTag), true,
	When(IsBound(nt.firstTag),
            When(IsList(R.requiredFirstTag),
                 nt.firstTag().kind() in R.requiredFirstTag,
                 nt.firstTag().kind()  = R.requiredFirstTag), false)) and
    # R.a.requiredFirstTag is the better way of setting mandatory tags
    When(not IsNewRule(R) or not IsBound(R.a.requiredFirstTag), true,
	When(IsBound(nt.firstTag),
            When(IsList(R.a.requiredFirstTag),
                 nt.firstTag().kind() in R.a.requiredFirstTag,
                 nt.firstTag().kind()  = R.a.requiredFirstTag), false)) and
    When(IsNewRule(R),
            SReduceSimple(R.applicable(nt)) <> false,
            R.isApplicable(nt.params));

#F _allChildren( <rule>, <non-terminal>[, <opts>])
#F   returns all possible children obtained by applying <rule> to <non-terminal>
#F   Use of opts.restrictSplit and opts.restrictSplitSize
#F      Set opts.restrictSplit:=true and opts.restrictSplitSize to the desired
#F      size.
#F      Can be used to obtain ruletrees with no leaves <= the specified size
#F      If this is used there will be a problem with generating ruletrees
#F      unless opts.baseHashes is set so that small sizes are fetched from the
#F      hash table. Otherwise generating rule trees will return false

 #_allChildren := (R, nt) -> When(IsNewRule(R), R.children(nt), R.allChildren(nt.params));
_allChildren := function( arg )
    local flag, i, R, nt, opts, ch, ch_copy, children;
    R := arg[1];
    nt := arg[2];
    children :=  When(IsNewRule(R), R.children(nt), R.allChildren(nt.params));
    if IsBound(arg[3]) then
        opts := arg[3];
        ch_copy := Copy(children);
        flag := false;
        i := 1;
        if IsBound(opts.restrictSplit) and opts.restrictSplit = true and
                                         IsBound(opts.restrictSplitSize) then
            for ch in ch_copy do
                while flag=false and i<=Length(ch) do
                    if ch[i].params[1] <= opts.restrictSplitSize then
                        flag := true;
                    fi;
                    i := i+1;
                od;
                if flag then
                    RemoveSet(children, ch);
                    flag := false;
                fi;
                i := 1;

            od;
        fi;
    fi;
    return children;
end;
# children[i] could be a complicated SPL expansion of the nonterms[i]
# or children could be same as nonterms, depending on the workflow you are using
#_apply := (R, nt, children, nonterms) -> Checked(IsRule(R), IsSPL(nt),
#    When(IsNewRule(R),
#	 R.apply(nt, children, nonterms),
#	 When(NumGenArgs(R.rule)=2,
#	      R.rule(nt.params, children),
#	      R.rule(nt.params, children, nonterms)))
#);

# Current rule wrap for fftx needs attributes from nt object.
# The wrapper has var. arg. This fact is used here
# to recognize the wrapper and pass nt instead of its params.
_apply := (R, nt, children, nonterms) -> Checked(IsRule(R), IsSPL(nt),
    When(IsNewRule(R),
     R.apply(nt, children, nonterms),
     Cond(NumGenArgs(R.rule)=-1,
            R.rule(nt, children, nonterms),
            NumGenArgs(R.rule)=2,
            R.rule(nt.params, children),
            R.rule(nt.params, children, nonterms)))
);

#F IsApplicableRule( <rule>, <non-terminal>, <ruleset> )
#F   returns true if <rule> can be applied to <non-terminal>
#F   and false else.
#F
IsApplicableRule := (R, nt, ruleset) -> When(IsAlternativeRewriteRule(R),
    Length(Collect(nt, R.pattern))<>0
    ,
    Checked(IsRule(R), IsSPL(nt),
    (not Same(ruleset, ApplicableTable) or R.switch) and
    (
	_applicable(R, nt, ruleset) or
	(R.forTransposition and _applicable(R, nt.transpose(), ruleset)))));

#F ApplyRuleSPL( <rule>, <non-terminal> )
#F   returns result of application of <rule> to <non-terminal>, if
#F   it is non-applicable an error is reported
#F
ApplyRuleSPL := (R, nt) ->
	Checked(IsRule(R), IsSPL(nt),
		let(c := _allChildren(R,nt)[1],	_apply(R, nt, c, c))
	);

AllApplicableRulesDirect := (spl, ruleset) ->
    Concatenation(
		When(not IsBound(ruleset.(spl.__name__)), [ ],
			Filtered(ruleset.(spl.__name__), r -> not r.forTranspositionOnly and _applicable(r, spl, ruleset))),
		Filtered([@_Base], r ->not r.forTranspositionOnly and _applicable(r, spl, ruleset))
	);

#F AllApplicableRules( <non-terminal>, <ruleset> )
#F   returns list of all rules applicable to a non-terminal
#F
AllApplicableRules := (nt, ruleset) ->
	Checked(IsSPL(nt), Set(AllApplicableRulesDirect(nt, ruleset)));

#F RandomChildrenRule( <rule>, <non-terminal>, <ruleset> )
#F   returns a random set of children for <rule> applied to <spl>.
#F   Calls the rule's randomChildren function if available.
#F   Otherwise, calls RandomList on the rule's allChildren function.
#F
RandomChildrenRule := (R, nt, ruleset) -> Checked(IsApplicableRule(R, nt, ruleset),
    When(IsBound(R.randomChildren),
	 R.randomChildren(nt.params),
	 RandomList(_allChildren(R, nt))));

#F Verification of Rules
#F ---------------------
#F

#F VerifyRules(<non-terminal>, <verify-func>)
#F
#F  Expands <non-terminal> using all applicable rules and all
#F  possible children sets (just one expansion step) and runs
#F  <verify-func> on the obtained partial ruletrees and the non
#F  terminal to check correctness.
#F
#F  verify_func = (rt, nt) -> boolean
#F      <rt> is partial ruletree,
#F      <nt> is original non-terminal
#F
#F  Example:
#F   VerifyRulesForSPL := nt ->
#F       VerifyRules(nt, (rt, nt) ->
#F           InfinityNormMat(MatSPL(SPLRuleTree(rt)) - MatSPL(nt)) < 1e-11);
#F
VerifyRules := function ( nt, verify_func, opts )
  local rule, Csets, C, ruletree, res, direct, transp, transp_nt;
  Constraint(IsSPL(nt));
  res := true;

  for ruletree in ExpandSPL(nt, opts) do
      Print("-- ", ruletree, " --\n");
      Print("checking rule ", ruletree.rule, ": ");
      if verify_func(ruletree, nt) then
	  Print(Green("correct\n"));
      else
	  Print(Red("incorrect!\n"));
	  res := false;
      fi;
  od;
  return res;
end;

_checkMatRuleTree := function(rt, nt)
    local me, them, diff;
    me := MatSPL(SPLRuleTree(rt));
    them := MatSPL(nt);
    diff := InfinityNormMat(me-them);
    return diff < 1e-11;
end;

#F VerifyRulesForSPL( <non-terminal>, <opts> )
#F   expands <non-terminal> using all applicable rules and all
#F   possible children sets (just one expansion step) and checks
#F   whether the resulting matrix matches the non-terminal matrix.
#F
#F   Matrices are obtained with MatSPL, and infinity-norm of the
#F   difference is thresholded, with threshold of 1e-11.
#F
#F   See also VerifyRules, it is a more general function.
#F
VerifyRulesForSPL := (S, opts) -> VerifyRules(S, _checkMatRuleTree, opts);

#F Rule switching
#F ----------------
#F

#F AllRules(<non-terminal> | <non-terminal-name>)
#F    Returns a list of all rules for <non-terminal>.
#F
AllRules := nt -> let(
    name := Cond(IsSPL(nt), nt.__name__, IsString(nt), nt,
	Error("<nt> must be a nonterminal or its name (string)")),
    When(IsBound(ApplicableTable.(name)), ApplicableTable.(name),
	Error("No rules exist for '", name, "'")));

#F Adding your own rules
#F ---------------------
#F

#F BreakdownRule - base class for breakdown rules created with RulesFor(...)
#F
Class(BreakdownRule, rec(
    isRule := true,
    operations := RuleOps,
    info             := "-not specified-",
    forTransposition := false,
    forTranspositionOnly := false,
    switch           := true,
    transposed       := false,
    allChildren      := P -> [[ ]],
    isApplicable     := P -> true,
    __call__         := arg >> ApplyFunc(RuleTree, arg)
));

#F NewBreakdownRule - base class for breakdown rules created with NewRulesFor(...)
#F
Class(NewBreakdownRule, AttrMixin, rec(
    isRule := true,
    isNewRule := true,
    operations := RuleOps,
    info             := "-not specified-",
    forTransposition := false,
    forTranspositionOnly := false,
    switch           := true,
    transposed       := false,

    freedoms := (self, nt) >> [],
    child := (self, nt, fr) >> [],

    children := (self, nt) >> let(
	ff := List(_unwrap(self.freedoms(nt)), _unwrap),
	cart := Cartesian(ff),   # Cartesian([])==[[ ]]
	List(cart, f -> self.child(nt, f))
    ),

    applicable       := nt -> true,
    __call__         := arg >> ApplyFunc(RuleTree, arg),

# NOTE: YSV finish this (--parametrization of rules)
#     print := self >> let(rch := self.rChildren(),
#         Print(self.name, Cond(rch<>[], Print(".from_rChildren(", PrintCS(rch), ")"), ""))),

#     operations := RewritableObjectOps,
#     lessThan := RewritableObject.lessThan,
#     equals := RewritableObject.equals,
#     rChildren := self >> [],
#     from_rChildren := (self, rch) >> Error("not supported"),
));

MakeRule := function ( R, name, nt )
    local doc;
    Constraint(IsRec(R) and IsString(name));
    doc := R.__doc__;
    # R.__doc__ is overwritten upon assignment
    R := WithBases(BreakdownRule, R);
    R.__doc__ := doc;
    R.name    := name;
    R.nonTerminal := nt;
    return R;
end;

NewMakeRule := function ( R, name, nt )
    local doc;
    Constraint(IsRec(R) and IsString(name));
    doc := R.__doc__;
    # R.__doc__ is overwritten upon assignment
    R := WithBases(NewBreakdownRule, R);
    R.__doc__ := doc;
    R.name    := name;
    R.nonTerminal := nt;
    return R;
end;

@_Base := NewMakeRule(
    rec(applicable       := nt -> not IsNonTerminal(nt) and not IsBound(ApplicableTable.(nt.__name__)),
	forTransposition := false,
        forTranspositionOnly := false,
	children             := nt -> [nt.children()],
	apply := (nt,ch,nonterms) -> Inherit(nt, rec(_children := ch))),
        "@_Base", @);

#F ApplicableTable - mapping from non-terminal names to applicable rules
#F
ApplicableTable := rec(
    @ := [ @_Base ]
);

_RulesFor := function(nt, rulesRec, makeRuleFunc)
    local rules, r, ntname, fields, nam;
    Constraint(IsSPL(nt));
    if not IsBound(nt.index) then AddNonTerminal(nt); fi;

    if not IsRec(rulesRec)
        then Error("<rulesRec> must be a record containing rule records as elements"); fi;

    fields := Filtered(RecFields(rulesRec), f -> not IsSystemRecField(f));
    if not ForAll(fields, x -> IsRec(rulesRec.(x)))
        then Error("<rulesRec> must be a record containing rule records as elements");
    fi;

    rules := [];
    for nam in fields do
        rulesRec.(nam) := makeRuleFunc(rulesRec.(nam), nam, nt);
	Add(rules, rulesRec.(nam));
    od;

    if IsBound(ApplicableTable.(nt.__name__)) then Append(ApplicableTable.(nt.__name__), rules);
    else ApplicableTable.(nt.__name__) := rules; fi;

    # NOTE: Assign() was here for backwards compatibility
    for r in rules do Assign(r.name, r); od;
end;

#F RulesFor( <nonterm>, <rulesRec> )
#F
RulesFor := (nt, rulesRec) -> _RulesFor(nt, rulesRec, MakeRule);

NewRulesFor := (nt, rulesRec) -> _RulesFor(nt, rulesRec, NewMakeRule);

SimpleRule := (pat, rule) -> rec(
    isApplicable := Subst(P -> PatternMatch(P, $pat, empty_cx())),
    rule := rule
);

BaseRule := (transform, pat) -> let(lpat := When(IsList(pat), pat, [pat]),
    rec(
	isApplicable := DetachFunc(Subst(P -> PatternMatch(P, $(Concatenation([ListClass],lpat)), empty_cx()))),
	rule := DetachFunc(Subst((P,C) -> ApplyFunc($transform, P).terminate()))
    ));

Class(InfoNt, NonTerminal, rec(
    abbrevs := [ arg -> arg ],
    dims := self >> [1,1],
    doNotExpand := true,
    doNotMeasure := true,
    doNotSaveInHashtable := true,
    isReal := True,
    transpose := self >> self
));

NewRulesFor(InfoNt, rec(Info_Base := rec(applicable := True, apply := arg -> I(1))));

############

Class(AlternativeRewriteRule, AttrMixin, rec(
    isRule := true,
    isAlternativeRewriteRule := true,
    operations := RuleOps,
));

MakeAlternativeRewriteRule := function ( R, name)
    local doc;
    Constraint(IsRec(R) and IsString(name));
    doc := R.__doc__;
    # R.__doc__ is overwritten upon assignment
    R := WithBases(AlternativeRewriteRule, R);
    R.__doc__ := doc;
    R.name    := name;
    return R;
end;

AlternativeRewriteRules := function(rulesRec)
    local fields, nam;

    if not IsRec(rulesRec)
        then Error("<rulesRec> must be a record containing rule records as elements"); fi;

    fields := Filtered(RecFields(rulesRec), f -> not IsSystemRecField(f));
    if not ForAll(fields, x -> IsRec(rulesRec.(x)))
        then Error("<rulesRec> must be a record containing rule records as elements");
    fi;

    for nam in fields do
        rulesRec.(nam) := MakeAlternativeRewriteRule(rulesRec.(nam), nam);
        Assign(nam, rulesRec.(nam));
    od;
end;


text:
InstallMethod(MitM_GAPToOMRec,
"for a dihedral perm group",
[IsPermGroup and IsDihedralGroup],
D -> OMA( MitM_SimpleOMS("DihedralGroup")
        , MitM_SimpleOMS("IsPermGroup")
        , MitM_GAPToOMRec(Size(D)) ) );

InstallMethod(MitM_GAPToOMRec,
"for a quaternion perm group",
[IsPermGroup and IsQuaternionGroup],
Q -> OMA( MitM_SimpleOMS("QuaternionGroup"),
          MitM_SimpleOMS("IsPermGroup"),
          MitM_GAPToOMRec(Size(Q))));

InstallMethod(MitM_GAPToOMRec,
"for an integer",
[IsInt],
i -> OMI(i));

InstallMethod(MitM_GAPToOMRec,
"for a float",
[IsFloat],
v -> OMF(v));

InstallMethod(MitM_GAPToOMRec,
"for a string in string representation",
[IsString and IsStringRep],
s -> OMSTR(s));

InstallMethod(MitM_GAPToOMRec,
"for a char",
[IsChar],
c -> OMA( OMS(MitM_cdbase, "prim", "CharConstr")
        , OMSTR( [c] ) ) );

InstallMethod(MitM_GAPToOMRec,
"for a boolean",
[IsBool],
b -> OMA( OMS( MitM_cdbase, "prim", "BoolConstr" )
        , OMSTR( String(b) ) ) );

InstallMethod(MitM_GAPToOMRec,
"for a record",
[IsRecord],
function(r)
    local content, rnam;
    content := [OMS(MitM_cdbase, "prim", "RecConstr")];
    for rnam in Set(RecNames(r)) do
        Add(content, OMSTR(rnam));
        Add(content, MitM_GAPToOMRec(r.(rnam)));
    od;
    return CallFuncList(OMA, content);
end);

InstallMethod(MitM_GAPToOMRec,
              "for an omrec",
              [MitM_OMRec],
              IdFunc);

InstallMethod(MitM_GAPToOMRec,
              "for a permutation",
              [IsPerm],
function(p)
    local content;

    content := [ OMS(MitM_cdbase, "prim", "PermConstr") ];
    Append( content
          , List(ListPerm(p), MitM_GAPToOMRec) );
    return CallFuncList(OMA, content);
end);

InstallMethod(MitM_GAPToOMRec,
"for a polynomial ring",
[IsPolynomialRing],
R -> OMA( MitM_SimpleOMS("PolynomialRing")
        , MitM_GAPToOMRec(LeftActingDomain(R))
        , MitM_GAPToOMRec(List(IndeterminatesOfPolynomialRing(R), String)) ) );

InstallMethod(MitM_GAPToOMRec,
"for a polynomial",
[IsPolynomial],
function(p)
    local content;
    return OMA( MitM_SimpleOMS("PolynomialByExtRep"),
                OMA(MitM_SimpleOMS("RationalFunctionsFamily"),
                    OMA(MitM_SimpleOMS("FamilyObj"),
                        MitM_GAPToOMRec(1))),
                MitM_GAPToOMRec(ExtRepPolynomialRatFun(p)));
end);

InstallMethod(MitM_GAPToOMRec,
"for the ring of integers",
[IsIntegers],
I -> MitM_SimpleOMS("Integers"));

InstallMethod(MitM_GAPToOMRec,
"for a list",
[IsList],
function(L)
    local content, item;
    content := [ OMS(MitM_cdbase
                     , "prim"
                     , "ListConstr") ];
    for item in L do
        Add(content, MitM_GAPToOMRec(item));
    od;
    return CallFuncList(OMA, content);
end);

InstallMethod(MitM_GAPToOMRec,
"for a finite field element",
[IsFFE],
function(elm)
    local content, char, deg, log, coef;
    content := [];
    Add(content, OMS( MitM_cdbase
                    , "prim"
                    , "FFEConstr"));
    char := Characteristic(elm);
    deg := DegreeFFE(elm);
    Add(content, MitM_GAPToOMRec(char));
    Add(content, MitM_GAPToOMRec(deg));
    if IsInternalRep(elm) then
        log := LogFFE(elm, Z(char, deg));
        elm := FFECONWAY.ZNC(char, deg) ^ log;
    fi;
    for coef in elm![1] do
        Add(content, MitM_GAPToOMRec(IntFFE(coef)));
    od;
    return CallFuncList(OMA, content);
end);

# TODO: This is a hack. We look for functions that create objects using
#       `Objectify` by essentially grepping through their source (so this
#       only works for GAP-level functions) and designating any function
#       a constructor that calls Objectify.
#
#       As a first test we wrap these functions in a constructor-memoiser
MitM_C___Wrapper := function(n, callee)
    return function(args...)
        local obj, omacont, a, m;
        obj := CallFuncList(callee, args);

        omacont := [ OMS(MitM_cdbase, "lib", n) ];
        for a in args do
            m := ApplicableMethod(MitM_GAPToOMRec, [ a ]);
            if m <> fail then
                Add(omacont, m(a));
            else
                # CANT DO
                return obj;
            fi;
        od;
        # This will of course only work with attribute storing objects
        SetMitM_GAPToOMRec(obj, CallFuncList(OMA, omacont) );
        return obj;
    end;
end;

# Under no circumstances should we touch these. It's where madness lies.
MitM_ConstructorBlacklist := [ OMOBJ, OMA, OMS, OMATTR, OMSTR, OMF,
                               OMI, OME, OMV ];
InstallGlobalFunction(MitM_FindConstructors,
function()
    local n, v, j, fun, res, a, meths, mpos, mres;

    res := [];
    for n in NamesGVars() do
        if IsBoundGlobal(n) then
            v := ValueGlobal(n);
            if IsOperation(v) then
                for a in [1..6] do
                    meths := METHODS_OPERATION(v, a);
                    j := 0;
                    while j + a + 2 < Length(meths) do
                        fun := meths[j + a + 2];
                        if PositionSublist(String(fun), "Objectify") <> fail then
                            meths[j + a + 2] := MitM_C___Wrapper(n, fun);
                            CHANGED_METHODS_OPERATION(v, a);
                            Add(res, rec( type := "oper", name := n, value := fun, operation := v ));
                        fi;
                        j := j + (BASE_SIZE_METHODS_OPER_ENTRY + a);
                    od;
                od;
            fi;
            if IsFunction(v) then
                if PositionSublist(String(v), "Objectify") <> fail then
                    if not (v in MitM_ConstructorBlacklist) then
                        Info(InfoMitMConstructors, 15, "Overloading ", n, "." );
                        MakeReadWriteGlobal(n);
                        UnbindGlobal(n);
                        BindGlobal(n, MitM_C___Wrapper(n, v));
                        Add(res, rec( type := "gvar", name := n, value := v ));
                    else
                        Info(InfoMitMConstructors, 15, "Skipping ", n, "." );
                    fi;
                fi;
            fi;
        fi;
    od;
    return res;
end);

max_stars_repo_name: markuspf/MathsInTheMiddle

max_issues_repo_name: markuspf/MathsInTheMiddle

max_forks_repo_name: markuspf/MathsInTheMiddle


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

_DHT_CONST := 2.5;

#F TDHT(<n>, <k>) - RDFT Nonterminal
Class(TDHT, TaggedNonTerminal, rec(
    abbrevs := [ (n) -> Checked(IsPosInt(n),  [n]) ],
    dims := self >> [self.params[1], self.params[1]],
    isReal := True,
    terminate := self >> PkDHT1(self.params[1]).terminate(),
    SmallRandom := () -> Random([2,4,6,8,10,12,16,18,24,30,32]),
    normalizedArithCost := (self) >> let(n := self.params[1], IntDouble(_DHT_CONST * n * d_log(n) / d_log(2)))
));

_DHTtoRDFT := N -> DirectSum(I(2), Tensor(I(N/2-1), F(2)));

#F TXMatDHT(<n>) - X-matrix to translate a RC(DFT(N)) -> DHT(2*N)
Class(TXMatDHT, TaggedNonTerminal, rec(
    abbrevs := [ (n) -> Checked(IsPosIntSym(n), [n]) ],
    dims := self >> [self.params[1], self.params[1]],
    isReal := True,
    terminate := self >>  _DHTtoRDFT(self.params[1]) * TConjEven(self.params[1]).terminate(),
    SmallRandom := () -> Random([2,4,6,8,10,12,16,18,24,30,32]),
    doNotMeasure := true
));

#F  Translate DHT into RDFT
NewRulesFor(TDHT, rec(
    DHT_DFT_tSPL := rec(
        switch := true,
        applicable := (self, t) >> IsEvenInt(t.params[1]), # and t.hasTags(),
        children := (self, t) >> let(N := t.params[1], tags := t.getTags(),
            [[
                TXMatDHT(N).withTags(tags),
                TRC(DFT(N/2)).withTags(tags)
            ]]),
        apply := (self, t, C, Nonterms) >> C[1] * C[2]
    )
));

NewRulesFor(TXMatDHT, rec(
    TXMatDHT_TConjEven := rec(
        switch := true,
        applicable := (self, t) >> IsEvenInt(t.params[1]),
        children := (self, t) >> let(N := t.params[1], tags := t.getTags(),
            [[
                 TConjEven(N).withTags(tags),
           ]]),
        apply := (self, t, C, Nonterms) >> _DHTtoRDFT(t.params[1]) * C[1]
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Class(MACROUnparser, ThreeOpMacroUnparser_Mixin, CMacroUnparserProg, rec(

    data   := (self, o, i, is) >> When(IsVecT(o.var.t),
                                     Print(Blanks(i), self.prefixT("VDECLC", o.var.t, [o.var] :: o.value.v), ";\n", self(o.cmd, i, is)),
                                     Inherited(o, i, is)),

    vpack  := (self, o, i, is) >> self.prefixT("VPK",  o.t, o.args),
    vdup   := (self, o, i, is) >> self.prefixT("VDUP", o.t, o.args[1]),

    assign_cmd := (self, o, i, is) >> Print(Blanks(i), self.(o.exp_op.__name__)(o, i, is), ";\n"),

    vunpacklo_2xf  := (self, o, i, is) >> self.prefix_T("VUNPKLO", o.args),
    vunpacklo_4xf  := ~.vunpacklo_2xf,
    vunpacklo_8xf  := ~.vunpacklo_2xf,

    vunpackhi_2xf  := (self, o, i, is) >> self.prefix_T("VUNPKHI", o.args),
    vunpackhi_4xf  := ~.vunpackhi_2xf,
    vunpackhi_8xf  := ~.vunpackhi_2xf,

    vunpacklo2_4xf := (self, o, i, is) >> self.prefix_T("VUNPKLO2", o.args),
    vunpacklo2_8xf := ~.vunpacklo2_4xf,

    vunpackhi_2xf  := (self, o, i, is) >> self.prefix_T("VUNPKHI", o.args),
    vunpackhi_4xf  := ~.vunpackhi_2xf,
    vunpackhi_8xf  := ~.vunpackhi_2xf,

    vunpackhi2_4xf := (self, o, i, is) >> self.prefix_T("VUNPKHI2", o.args),
    vunpackhi2_8xf := ~.vunpackhi2_4xf,

    vpacklo_2xf  := (self, o, i, is) >> self.prefix_T("VPKLO", o.args),
    vpacklo_4xf  := ~.vpacklo_2xf,
    vpacklo_8xf  := ~.vpacklo_2xf,

    vpackhi_2xf  := (self, o, i, is) >> self.prefix_T("VPKHI", o.args),
    vpackhi_4xf  := ~.vpackhi_2xf,
    vpackhi_8xf  := ~.vpackhi_2xf,

    vpacklo2_4xf := (self, o, i, is) >> self.prefix_T("VPKLO2", o.args),
    vpacklo2_8xf := ~.vpacklo2_4xf,

    vpackhi_2xf  := (self, o, i, is) >> self.prefix_T("VPKHI", o.args),
    vpackhi_4xf  := ~.vpackhi_2xf,
    vpackhi_8xf  := ~.vpackhi_2xf,

    vpackhi2_4xf := (self, o, i, is) >> self.prefix_T("VPKHI2", o.args),
    vpackhi2_8xf := ~.vpackhi2_4xf,

    vtrcx_8xf    := (self, o, i, is) >> self.prefix_T("VTRCX", o.args),

    vmulcx_2xf := (self, o, i, is) >> self.prefix_T("VMULCX", o.args),
    vmulcx_4xf := ~.vmulcx_2xf,
    vmulcx_8xf := ~.vmulcx_2xf,

    vswapcx_2xf := (self, o, i, is) >> self.prefix_T("VSWAPCX", o.args),
    vswapcx_4xf := ~.vswapcx_2xf,
    vswapcx_8xf := ~.vswapcx_2xf,

    fma  := (self, o, i, is) >> self.prefixTTT("FMA", o.args[1].t, o.args[2].t, o.args[3].t, o.args),
    fms  := (self, o, i, is) >> self.prefixTTT("FMS", o.args[1].t, o.args[2].t, o.args[3].t, o.args),
    nfma := (self, o, i, is) >> self.prefixTTT("NFMA", o.args[1].t, o.args[2].t, o.args[3].t, o.args),

    vstore_cmd := (self, o, i, is) >> Print(Blanks(i), self.prefixT("VSTORE", o.args[3].t, o.args), ";\n"),
    vload_cmd  := (self, o, i, is) >> Print(Blanks(i), self.prefixT("VLOAD", o.args[1].t, o.args), ";\n"),
));


text:
myvar := 5;
mycode := function (x)
	   return 2*x;
  end;

ext: gap

max_stars_repo_name: jorants/gap-loader

max_issues_repo_name: jorants/gap-loader

max_forks_repo_name: jorants/gap-loader


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#
#################################
#
# CodegenStrategy Stages
#
# NOTE: these are wrapped in classes because their names are simpler in a list.
#################################

#
## _EnumBlocks
#
# Add a bbnum tag to each BB, enumerating them.
#
# changes the sums INPLACE. Has to appear before _ApplyCodegen
# to be effective.
Class(_EnumBlocks, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        EnumBlocks(sums, opts);

        return code;
    end,
));

#
## Apply Codegen
#
# convert SigmaSPL to Code using opts.codegen
#
Class(_ApplyCodegen, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        local X, Y;

        [X, Y] := _getXY(sums, opts);

        return opts.codegen(sums, StripList(Y), StripList(X), opts);
    end,
));

#
## _BlockSums
#
#
Class(_BlockSums, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        return BlockSums(code, opts);
    end,
));

#
## _ESReduce
#
#
Class(_ESReduce, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        return ESReduce(code, opts);
    end,
));

#
## _RemoveAssignAcc
#
#
Class(_RemoveAssignAcc, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        return RemoveAssignAcc(code);
    end
));

#
## __BlockUnroll
#
#
Class(__BlockUnroll, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        return BlockUnroll(code, opts);
    end,
));

#
## _DeclareHidden
#
#
Class(_DeclareHidden, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        return DeclareHidden(code);
    end,
));

#
## _FixedPointCode
#
#
Class(_FixedPointCode, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        if IsBound(opts.isFixedPoint) and opts.isFixedPoint then
            code := FixedPointCode(code, opts.bits, opts.fracbits);
        fi;

        return code;
    end,
));

#
## new legacy wrap
#
# temporaries on stack
# out of place arrays, global ptrs, malloced on 128b boundary
#
# format is that used in the new type, with all the new functions
#
Class(_NewLegacyWrap, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        local x, y, io, params, datas, sub, initsub, init, compute, alloc, free, timer, data, prog;

        # data from sums
        [x, y] := _getXY(sums, opts);
        io := When(x=y, [x], [y, x]);
        params := Set(Collect(sums, param));
        datas := Collect(sums, FDataOfs);

        # names
        sub := Cond(IsBound(opts.subName), opts.subName, "transform");
        initsub := Cond(IsBound(opts.subName), Concat("init_", opts.subName), "initz");

        #
        # code sections start here:
        #

        # generate the 'init' code.
        if IsBound(opts.generateInitFunc) and opts.generateInitFunc then
            init := func(TVoid, initsub, params, chain(
                List(datas, x -> SReduce(x.var.init, opts))
            ));
        else
            init := func(TVoid, initsub, params, code);
        fi;

        # wrap the 'compute'
        compute := func(TVoid, sub, Concatenation(io, params), code);

        # create the allocs/free
        alloc := skip();
        free := skip();

        # setup timer
        timer := skip();

        # generate data
        data := List(datas, x -> x.var);

        #
        # put pieces together
        #

        prog := program(
            decl(data, chain(
                init,
                compute,
                alloc,
                free,
                timer
            ))
        );

        return prog;
    end,
));

#
## _LegacyWrap
#
#
Class(_LegacyWrap, CodegenStrat, rec(
    __call__ := function(code, sums, opts)
        local x, y, params, datas, io, sub, initsub, prog;

        [x, y] := _getXY(sums, opts);

        params := Set(Collect(sums, param));
        datas := Collect(sums, FDataOfs);

        io := When(x=y, [x], [y, x]);
        sub := Cond(IsBound(opts.subName), opts.subName, "transform");
        initsub := Cond(IsBound(opts.subName), Concat("init_", opts.subName), "initz");
        code := func(TVoid, sub, Concatenation(io, params), code);

        if IsBound(opts.generateInitFunc) and opts.generateInitFunc then
            prog := program(
                decl(List(datas, x->x.var),
                    chain(
                        func(TVoid, initsub, params, chain(List(datas,
                            x -> SReduce(x.var.init, opts)
                        ))),
                        code
                    )));
        else
            prog := program( func(TVoid, initsub, params, chain()), code);
        fi;

        prog.dimensions := sums.dims();

        return prog;
    end,
));

###
#
#
_BasicCodegenStrat := [
    _EnumBlocks,
    _ApplyCodegen,
    _ESReduce,
    _RemoveAssignAcc,
    __BlockUnroll,
    _DeclareHidden,
    _FixedPointCode
];

# these functions are in cgwrap.gi
_DefaultWrapStrat := [
    _DefaultWrapInitCompute,
    _DefaultWrapData,
    _DefaultWrapAlloc,
    _DefaultWrapTimer,
    _DefaultWrapVerify
];

_SlabWrapStrat := [
    _SlabInitCompute,
    _SlabAlloc,
    _SlabTimer,
    _SlabVerify
];

DefaultCodegenStrat := Concat(_BasicCodegenStrat, _DefaultWrapStrat);
SlabCodegenStrat := Concat(_BasicCodegenStrat, _SlabWrapStrat);

# a version where all sin/cos computation has been removed from the init function
# ::: useful for getting something running on the simulator.
SlabHackedCodegenStrat := Flat([_BasicCodegenStrat, _SlabWrapStrat, _SlabHackInit]);

#
## ApplyCodegenStrat
#
# applies the codegen strategy.
#
ApplyCodegenStrat := function(sums, opts)
    local code, s;

    # some default
    code := skip();

    # apply each function in the strategy in order
    # sums and opts do not change (hopefully), but code does.
    for s in opts.codegenStrat do
        code := s(code, sums, opts);
    od;

    return code;
end;


text:
f:=function (  )
    Print( "f:=", f, ";;\nf();\n" );
    return;
end;;
f();

max_issues_repo_name: seanwallawalla-forks/RosettaCodeData

max_forks_repo_name: seanwallawalla-forks/RosettaCodeData


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# ==========================================================================
# BaseIterative - base class for iterative SPL operators
#
# Subclasses must provide
#    unroll := self >> ...unrolled (non-iterative) spl...
#    dims := self >> ...compute dimensions..
#    transpose := self >> ...transposed spl...
#
# if default implementation below is not applicable, subclasses must redefine
#   arithmeticCost := (self, costMul, costAddMul) >> ...
#
# ==========================================================================

IsIterative := x -> IsRec(x) and IsBound(x.isIterative) and x.isIterative;

Class(BaseIterative, BaseOperation, rec(

    isIterative := true,
    #-----------------------------------------------------------------------
    # Subclasses must provide
    unroll := self >> Error("This method must be provided by the subclass of BaseIterative"),
    dims := self >> Error("This method must be provided by the subclass of BaseIterative"),
    transpose := self >> Error("This method must be provided by the subclass of BaseIterative"),

    free := self >>
        Difference(Union(List(self.children(), x->x.free())), [self.var]),

    from_rChildren := (self, rch) >> CopyFields(self, rec(_children := rch)),

    # if default implementation below is not applicable, subclasses must redefine
    # arithmeticCost := (self, costMul, costAddMul) >> ...
    #
    #-----------------------------------------------------------------------
    abbrevs := [ (v, expr) -> [v, v.range, expr] ],

    new := meth(self, var, domain, expr)
        local res;
        Constraint(IsSPL(expr));
        # if domain is an integer (not symbolic) it must be positive
        Constraint(not IsInt(domain) or domain >= 0);
        var.isLoopIndex := true;
        res := SPL(WithBases(self, rec(_children := [expr], var := var, domain := domain)));
        res.dimensions := res.dims();
        return res;
    end,
    #-----------------------------------------------------------------------
    unrolledChildren := self >> List(listRange(EvalScalar(self.domain)), u -> self.at(TInt.value(u))),

    at := (self, u) >> SubstVars(Copy(self._children[1]), rec((self.var.id):=u)),

    #-----------------------------------------------------------------------
    # .split(m), splits the original loop into two nested loops with m
    #            iterations in the inner loop
    # This operations works with any kind of iterative operator, like ISum,
    # and IDirSum. It requres the operator class to provide .directOper, which
    # is the non-iterative version of the same operator (e.g. SUM for ISum)
    #
    split := (self, m) >> Cond(
	m=1,
	    self,
	let(
            N  := self.domain,      _It := ObjId(self),  _Ch := self.directOper,
            j1 := Ind(idiv(N, m)),  j2  := Ind(m),       j3  := Ind(imod(N, m)),

            is := _It(j1, j1.range, _It(j2, j2.range, self.at(j1*m + j2))),
            When(j3.range = 0, is,
		_Ch(is, _It(j3, j3.range, self.at(m * j1.range + j3)))))
    ),
    #-----------------------------------------------------------------------
    print := (self, i, is) >> Print(
        self.name, "(", self.var, ", ", self.domain, ",\n",
        Blanks(i+is), self._children[1].print(i+is, is), "\n",
        Blanks(i), ")", self.printA(),
        When(IsBound(self._setDims), Print(".overrideDims(", self._setDims, ")"), Print(""))
    ),
    #-----------------------------------------------------------------------
    arithmeticCost := (self, costMul, costAddMul) >>
        self.domain * self._children[1].arithmeticCost(costMul, costAddMul),
    #-----------------------------------------------------------------------
    isPermutation := False,
    isReal := self >> self._children[1].isReal(),
    toAMat := self >> self.unroll().toAMat()
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

#F DHT <size>)
#F Definition: (n x n)-matrix [ cas(2*pi*i*k*l/n) | k,l = 0...n-1 ] or
#F                            [ cos(2*pi*i*k*l/n) + sin(2*pi*i*k*l/n) | k,l = 0...n-1 ]
#F Note:     DHT_n = Re(DFT_n) + Im(DFT_n)
#F Example:  DHT(8)
#F
Class(DHT, NonTerminal, rec(
    abbrevs := [ n -> Checked(IsPosInt(n), [n]) ],
    dims := self >> [self.params[1], self.params[1]],
    terminate := self >> Mat(Sqrt(self.params[1]) * Global.DHT(self.params[1])),
    transpose := self >> Copy(self),
    isReal := self >> true,
    SmallRandom := ( ) -> Random([2, 4, 6, 8, 12, 16, 24, 32]),
    normalizedArithCost := self >> let(n := self.params[1], IntDouble(2.5 * n * d_log(n) / d_log(2)))
));

#F -----------------------------------------------------------------------------
#F XH(size) : represents a matrix used in DHT radix-2 rule (temporary solution)
#F -----------------------------------------------------------------------------
Class(XH, Sym, rec(
    notSupported := true,
    abbrevs := [ n -> Checked(IsInt(n), n >= 4, n mod 4 = 0, n) ],

    def := N -> When(N = 4, I(4),
	DirectSum(
	    I(N/2 + 1),
	    DirectSum(
		I(1),
		List([1..N/4-1], i -> Rot(1/2-2*i/N) * J(2))) ^
	              perm4(N/2-1))),

    transpose := self >> self,

    isReal := True
));

RulesFor(DHT, rec(
    #F DHT_Base: DHT_2 = F_2
    #F
    DHT_Base := rec (
	info             := "DHT_2 -> F_2",
	forTransposition := false,
	isApplicable     := P -> P[1] = 2,
	allChildren := P -> [[ ]],
	rule := (P, C) -> F(2)
    ),

    DHT_toPRDFT := rec(
        isApplicable := P -> P[1] > 2,
        allChildren := P -> [[ PRDFT(P[1]) ]],
        rule := (P, C) -> let(n := P[1], cut := Mat([[1,0]]),
            OS(n,-1) * # or set the rotation to -1
            LIJ(n).transpose() *
            Cond(IsEvenInt(n), DirectSum(cut, Tensor(I(n/2-1), F(2)), cut) * C[1],
                 IsOddInt(n),  DirectSum(cut, Tensor(I((n-1)/2), F(2)))    * C[1]))
    ),

    #F DHT_DCT1andDST1:
    #F
    #F   DHT_n = blocks * (DCT1_(n/2+1) dirsum DST1_(n/2-1)) * blocks
    #F
    #F   Britanak/Rao:
    #F     The fast generalized discrete Fourier transforms: A unified
    #F     approach to the discrete sinusoidal transforms computation.
    #F     Signal Processing 79, 1999, pp. 135--150
    #F
    DHT_DCT1andDST1 := rec (
	info             := "DHT_n -> DCT1_(n/2+1), DST1_(n/2-1)",
	forTransposition := false,
	isApplicable     := P -> P[1] mod 2 = 0 and P[1] > 2,
	allChildren := P -> [[ DCT1(P[1]/2+1), DST1(P[1]/2-1) ]],
	rule := (P, C) -> let(n:=P[1],
	    DirectSum(I(1), blocks1(n - 1)) *
	    DirectSum(C[1], C[2] ^ J(n/2 - 1)) *
	    DirectSum(I(1), blocks1(n - 1)))
    ),

    #F DHT_2:
    #F Radix-2 Cooley-Tukey
    #F
    DHT_Radix2 := rec (
	info             := "DHT_n -> DHT_n/2",
	forTransposition := false,
	isApplicable     := P -> P[1] mod 2 = 0 and IsPrimePowerInt(P[1]) and P[1] > 2,
	allChildren := P -> [[ DHT(P[1]/2) ]],
	rule := (P, C) -> let(n:=P[1],
	    Tensor(F(2), I(n/2)) *
	    XH(n) *
	    Tensor(I(2), C[1]) *
	    L(n, 2))
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

NewRulesFor(GT, rec(
    GT_Par := rec(
        maxSize       := false,
        minSize       := false,
        parEntireLoop := true,    # parallelize entire loop
        splitLoop := true,        # split off <nthreads> iterations

        requiredFirstTag := AParSMP,

    applicable := (self, t) >> let(
        rank := Length(t.params[4]), nthreads := t.firstTag().params[1],
        rank = 1 and let(its := t.params[4][1],
        PatternMatch(t, [GT, @(1), @(2,XChain), @(3,XChain), ...], empty_cx()) and
        IsPosInt(its/nthreads))),

        children := (self, t) >> let(
            spl := t.params[1], g := t.params[2], s := t.params[3], its := t.params[4][1],
            nthreads := t.firstTag().params[1], tags := Drop(t.getTags(), 1),
            Concatenation(
                  When(self.splitLoop,
                      [[ GT(spl, g, s, [its / nthreads]).withTags(tags), InfoNt(nthreads) ]], []),
                  When(self.parEntireLoop,
                      [[ GT(spl, XChain([0]), XChain([0]), []).withTags(tags), InfoNt(its) ]], [])
            )
        ),

        apply := (self, t, C, Nonterms) >> let(
            spl := t.params[1], N := Minimum(spl.dimensions),
            g := t.params[2], s := t.params[3], its := t.params[4][1],
            gg := When(g.params[1]=[0,1], XChain([0,1,2]), XChain([1,2,0])),
            ss := When(s.params[1]=[0,1], XChain([0,1,2]), XChain([1,2,0])),
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],
            par_its := When(IsBound(Nonterms[2]), Nonterms[2].params[1], nthreads), i := Ind(par_its),

            SMPBarrier(nthreads, tid,
                SMPSum(nthreads, tid, i, par_its,
                    Scat(ss.part(1, i, Rows(spl), [par_its, its/par_its])) *
                    C[1] *
                    Gath(gg.part(1, i, Cols(spl), [par_its, its/par_its]))))
        )
    ),

    # Push parallel tag down to preserve locality: smp(I x A) -> (I x smp(A))
    # may be good for MD DFTs
    GT_Par_IxA_Push := rec(
        forTransposition := false,
        requiredFirstTag := AParSMP,
        applicable := t -> t.rank()=1 and t.params[2]=GTPar and t.params[3]=GTPar,
        children := t -> [[ t.params[1].withTags(t.getTags()) ]],
        apply := (t, C, Nonterms) -> Tensor(I(t.params[4][1]), C[1])
    ),

    GT_Par_odd := rec(
        maxSize       := false,
        minSize       := false,
        requiredFirstTag := AParSMP,

    applicable := (self, t) >> let(
        rank := Length(t.params[4]), nthreads := t.firstTag().params[1],
        rank = 1 and let(its := t.params[4][1], not IsInt(its/nthreads) and
        PatternMatch(t, [GT, @(1), @(2,XChain), @(3,XChain), ...], empty_cx()))),

    children := (self, t) >> let(
            spl := t.params[1], g := t.params[2], s := t.params[3], its := t.params[4][1],
            nthreads := t.firstTag().params[1], tags := Drop(t.getTags(), 1),
                      [[ spl.withTags(tags) ]]),

    apply := (t, C, Nonterms) -> let(
            spl := Nonterms[1],
            its := t.params[4][1],
            i := Ind(its),
            g := fTensor(fBase(i), fId(Cols(spl))),
            s := fTensor(fBase(i), fId(Rows(spl))),
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],

            SMPSum(its, i, i, its,
                Scat(s) * C[1] * Gath(g)))
    )
));

NewRulesFor(TTensorInd, rec(
#   base cases
#   I x A
    dsA_base_smp := rec(
        forTransposition := false,
        applicable := nt -> IsParPar(nt.params) and nt.isTag(1, AParSMP) and nt.params[2].range = nt.getTags()[1].params[1],
        children := nt -> let(jp := IndPar(nt.params[2].range),
            [[ SubstVars(Copy(nt.params[1]), rec((nt.params[2].id) := jp)).withTags(Drop(nt.getTags(), 1)), InfoNt(jp) ]]),
        apply := (self, t, C, Nonterms) >> let(
            spl := C[1],
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],
            jp := Nonterms[2].params[1],
            g := fTensor(fBase(jp), fId(Cols(spl))),
            s := fTensor(fBase(jp), fId(Rows(spl))),

            SMPBarrier(nthreads, tid,
                SMPSum(nthreads, tid, jp, nthreads,
                    Scat(s) *
                    C[1] *
                    Gath(g))
        ))
    ),

    dsA_smp := rec(
        forTransposition := false,
        applicable := nt -> IsParPar(nt.params) and nt.isTag(1, AParSMP) and
            let(r := nt.params[2].range/nt.getTags()[1].params[1], IsInt(r) and r > 1),
        children := nt -> let(jp := IndPar(nt.getTags()[1].params[1]), j := Ind(nt.params[2].range/nt.getTags()[1].params[1]),
            [[ TTensorInd(
                SubstVars(Copy(nt.params[1]), rec((nt.params[2].id) := jp * V(j.range) + j)),
                j, APar, APar).withTags(Drop(nt.getTags(), 1)), InfoNt(jp) ]]),
        apply := (self, t, C, Nonterms) >> let(
            spl := C[1],
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],
            jp :=  Nonterms[2].params[1],
            g := fTensor(fBase(jp), fId(Cols(spl))),
            s := fTensor(fBase(jp), fId(Rows(spl))),

            SMPBarrier(nthreads, tid,
                SMPSum(nthreads, tid, jp, nthreads,
                    Scat(s) *
                    C[1] *
                    Gath(g))
            )
        )
    ),
    L_dsA_L_base_smp := rec(
        forTransposition := false,
        applicable := nt -> IsVecVec(nt.params) and nt.isTag(1, AParSMP) and nt.params[2].range = nt.getTags()[1].params[1],
        children := nt -> let(jp := IndPar(nt.getTags()[1].params[1]),
            [[ SubstVars(Copy(nt.params[1]), rec((nt.params[2].id) := jp)).withTags(Drop(nt.getTags(), 1)),
             InfoNt(jp) ]]),
        apply := (self, t, C, Nonterms) >> let(
            spl := C[1],
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],
            jp := Nonterms[2].params[1],
            g := fTensor(fId(Cols(spl)), fBase(jp)),
            s := fTensor(fId(Rows(spl)), fBase(jp)),

            SMPBarrier(nthreads, tid,
                SMPSum(nthreads, tid, jp, nthreads,
                    Scat(s) *
                    C[1] *
                    Gath(g))
        ))
    ),
    L_dsA_L_smp := rec(
        forTransposition := false,
        applicable := nt -> IsVecVec(nt.params) and nt.isTag(1, AParSMP) and
            let(r := nt.params[2].range/nt.getTags()[1].params[1], IsInt(r) and r > 1),
        children := nt -> let(jp := IndPar(nt.getTags()[1].params[1]), j := Ind(nt.params[2].range/nt.getTags()[1].params[1]),
            [[ TTensorInd(
                SubstVars(Copy(nt.params[1]), rec((nt.params[2].id) := jp * V(j.range) + j)),
                j, AVec, AVec).withTags(Drop(nt.getTags(), 1)), InfoNt(jp), InfoNt(j) ]]),

        apply := (self, t, C, Nonterms) >> let(
            spl := C[1],
            kernel := Nonterms[1].params[1],
            nthreads := t.firstTag().params[1],
            tid      := t.firstTag().params[2],
            jp := Nonterms[2].params[1],
            j := Nonterms[3].params[1],
            g := fCompose(fTensor(L(nthreads*Cols(kernel), nthreads), fId(j.range)), fTensor(fBase(jp), fId(Cols(spl)))),
            s := fCompose(fTensor(L(nthreads*Rows(kernel), nthreads), fId(j.range)), fTensor(fBase(jp), fId(Rows(spl)))),

            SMPBarrier(nthreads, tid,
                SMPSum(nthreads, tid, jp, nthreads,
                    Scat(s) *
                    C[1] *
                    Gath(g))
            )
        )
    )
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Class(fma, Exp, rec(
    computeType := self >> UnifyTypesL(self.args),
    toMul := self >> self.args[1] + self.args[2] * self.args[3],
    ev := self >> self.args[1].ev() + self.args[2].ev() * self.args[3].ev()));

Class(fms, Exp, rec(
    computeType := self >> UnifyTypesL(self.args),
    toMul := self >> self.args[1] - self.args[2] * self.args[3],
    ev := self >> self.args[1].ev() - self.args[2].ev() * self.args[3].ev()));

Class(nfma, Exp, rec(
    computeType := self >> UnifyTypesL(self.args),
    toMul := self >> -self.args[1] -+self.args[2] * self.args[3],
    ev := self >> -self.args[1].ev() + self.args[2].ev() * self.args[3].ev()));

RewriteRules(RulesStrengthReduce, rec(
   fma_Xab := Rule([@(0,[fma,fms,nfma]), _vtrivial, @, @], e -> e.toMul()),
   fma_aXb := Rule([@(0,[fma,fms,nfma]), @, _vtrivial, @], e -> e.toMul()),
   fma_abX := Rule([@(0,[fma,fms,nfma]), @, @, _vtrivial], e -> e.toMul()),
));

notMul := e -> ObjId(e)<>mul;

#NOTE - shouldn't have to handle arrays here
_IsAVector  := (var) >> (IsVecT(var.t) or IsArray(var.t));

_isNonZero  := i -> i.ev() <> 0;

_isDivOk    := e -> When(_IsAVector(e), ForAll(e.v, i -> _isNonZero(i)), _isNonZero(e));

_isNotEqual := function(a, b)
   # Why did we check for vectors?
   #if _IsAVector(a) or _IsAVector(b) then
   #   return true;
   #fi;
   return (a<>b);
end;

_divide := function(numerator, denominator)
# Both are scalars
   local type, vLength, nVal, dVal;
   if not (_IsAVector(numerator) or _IsAVector(denominator)) then
      return numerator/denominator;
   fi;

   if _IsAVector(numerator) and not _IsAVector(denominator) then
      type     := numerator.t;
      vLength  := numerator.t.size;
      nVal     := numerator.v;
      return(Value(type, List([1..vLength], i->nVal[i]/denominator.v)));
   fi;

   if not _IsAVector(numerator) and _IsAVector(denominator) then
      type     := denominator.t;
      vLength  := denominator.t.size;
      dVal     := denominator.v;
      return(Value(type, List([1..vLength], i->numerator.v/dVal[i])));
   fi;

# Both are vectors. Assume lengths are same.
   type     := numerator.t;
   vLength  := numerator.t.size;
   nVal     := numerator.v;
   dVal     := denominator.v;
   return(Value(type, List([1..vLength], i->nVal[i]/dVal[i])));
end;

_def := function(list, t, exp)
    local cmd;
    cmd := assign(var.fresh_t("s",t), exp);
    cmd.loc.def := cmd;
    Add(list, cmd);
    return cmd.loc;
end;

FMA := function(code)
    local c, cmds, dd, exp, res, supp, ch;
    res := [];

    cmds := code.cmds;

    for c in cmds do
        # NOTE: needs to check for our FP datatype, not 'uncheck' for TPtr, TInt etc.
        # NOTE: determine how pointer arithmetic works with FMAs on various archs.
        #       For now, avoid FMA'ing index computations.
        if IsBound(c.loc) and not IsPtrT(c.loc.t) and not IsIntT(c.loc.t) then
            dd := DefCollect(c,2); # definition, depth=2

            # ch is like children of DefCollect(c,1)
            if IsBound(c.exp.args) then ch := c.exp.args; else ch := []; fi;
            supp := [];

            exp := MatchSubst(dd, [
                [ [mul, @(1,Value), [mul, @(2,Value), @(3)]],
                    e -> mul(@(1).val*@(2).val, @(3).val), "mul mul" ],

                [ [add, [mul, @(1, Value), @(2)],
                        [mul, @(3, Value, e->_isDivOk(e) or _isDivOk(@1.val)), @(4)]],
                #NOTE: Determine small/large if scalar (we now only determine
                #       zero/nonzero if vector)
                    e -> let(
                        sm := When(_isDivOk(@(1).val), @(1).val, @(3).val),
                        lg := When(_isDivOk(@(1).val), @(3).val, @(1).val),
                        Cond(_isNotEqual(@(1).val, @(3).val),
                            Cond(sm.v=@(1).val.v,
                                # propagate (divide by) the smaller value
                                sm * _def(supp, c.loc.t, fma(@(2).val,
                                    _divide(@(3).val, @(1).val), @(4).val)),
                                sm * _def(supp, c.loc.t, fma(@(4).val,
                                    _divide(@(1).val, @(3).val), @(2).val))
                            ),
                            sm * _def(supp, c.loc.t, add(@(2).val, @(4).val))
                        )),
                    "fma:ab+cd"],

                [ [sub, [mul, @(1, Value), @(2)],
                        [mul, @(3, Value, e->_isDivOk(e) or _isDivOk(@1.val)), @(4)]],
                # NOTE: Determine small/large if scalar (we now only determine
                #        zero/nonzero if vector)
                    e -> let(
                        sm := When(_isDivOk(@(1).val), @(1).val, @(3).val),
                        lg := When(_isDivOk(@(1).val), @(3).val, @(1).val),
                        Cond(_isNotEqual(@(1).val, @(3).val),
                            Cond(sm.v=@(1).val.v,
                                sm * _def(supp, c.loc.t, fms(@(2).val,
                                    _divide(@(3).val, @(1).val), @(4).val)),
                                sm * _def(supp, c.loc.t, nfma(@(4).val,
                                    _divide(@(1).val, @(3).val), @(2).val))
                            ),
                            sm * _def(supp, c.loc.t, sub(@(2).val, @(4).val))
                        )),
                    "fma:ab-cd"],

                [ [add, [mul, @(1), @(2)], @(3)],
                    e -> fma(ch[2], @(1).val, @(2).val), "fma"],
                [ [add, @(3), [mul, @(1), @(2)]],
                    e -> fma(ch[1], @(1).val, @(2).val), "fma2"],

                [ [sub, [mul, @(1), @(2)], @(3)],
                    e -> nfma(ch[2], @(1).val, @(2).val), "nfma" ],
                [ [sub, @(3), [mul, @(1), @(2)]],
                    e -> fms(ch[1], @(1).val, @(2).val), "fms" ],

            ]);

            if not Same(dd, exp) then
                #Print("-----------------------------------------------------\n");
                #Print("c:    ", c  ,  "\n-----\n"); Print("dd:   ", dd ,  "\n-----\n");
                #Print("exp:  ", exp,  "\n-----\n"); Print("supp: ", supp, "\n-----\n");
                #Print("-----------------------------------------------------\n");
                c.exp := exp;
                c.loc.pred := ArgsExp(exp);
                Append(res, supp);
                Add(res, c);
            else
                Add(res, c);
            fi;
        else
            Add(res, c);
        fi;
    od;

    return chain(res);
end;

DoFMA := function(code)
   code := BinSplit(code);
   MarkDefUse(code);
   code := FMA(code);
   MarkDefUse(code);
   #return CopyPropagate(code); # Do this in the compileStrategy
   return(code);
end;


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

RemoveOnes := x -> Filtered(x, i->i<>1);

#F MDDFT(<dims>, [<exp>]) - multi-dimensional DFT non-terminal
#F   dims = [ <n_1>,.., <n_t> ] list of (positive) dimensions
#F   exp = root of unity exponent scaling (see DFT for exact definition)
#F
#F Definition : multidimensional matrix of size NxN, where N=n_1*..*n_t
#F      can also be represented as Tensor(DFT(n_1), ..., DFT(n_t))
#F
#F Example (direct)  : MDDFT([2,4,4])
#F Example (inverse) : MDDFT([2,4,4], -1)
#F
Class(MDDFT, TaggedNonTerminal, rec(
    abbrevs := [
    P     -> Checked(IsList(P), ForAll(P,IsPosInt), Product(P) > 1,
             [ RemoveOnes(P), 1, false ]),
    (P,k) -> Checked(IsList(P), ForAll(P,IsPosInt), IsInt(k), Product(P) > 1,
                     Gcd(Product(P), k)=1,
             [ RemoveOnes(P), k mod Product(P), false ]),
    (P,k,rc) -> Checked(IsList(P), ForAll(P,IsPosInt), IsInt(k), Product(P) > 1,
                     Gcd(Product(P), k)=1,
             [ RemoveOnes(P), k mod Product(P), rc ])
    ],
    dims := self >> let(n := Product(self.params[1]), When(self.isReal(), 2*[n,n], [n, n])),

    terminate := self >> let(t:=Tensor(List(self.params[1],
                                i -> DFT(i, self.params[2]).terminate())),
                            When(self.isReal(), MatAMat(RC(t).toAMat()), t)
                         ),

    transpose := self >> Copy(self),

    isReal := self >> self.params[3],

    setAB := meth(self, ab)
       self.a := ab[1];
       self.b := ab[2];
       return self;
    end,

    normalizedArithCost :=  (self) >> let(n := Product(self.params[1]),
                                        IntDouble(5 * n * d_log(n) / d_log(2)) )

#D    setpv := meth(self, pv)
#D        local s;
#D        s:= Copy(self);
#D        s.params[3] := pv;
#D        return s;
#D    end,

#D    tagpos := 3

));

# check for 1 dimensional MDDFTs and convert them to DFTs
catch1d_mddft := ch ->
    List(ch, x -> List(x, t -> When(Length(t.params[1]) > 1, t,
        DFT(Rows(t), t.params[2], t.params[3], t.params[4]))));

NewRulesFor(MDDFT, rec(
    #F RuleMDDFT_Base:  MDDFT -> DFT
    #F
    MDDFT_Base := rec(
        info := "MDDFT -> DFT",
        applicable     := nt -> Length(nt.params[1])=1,
        children       := nt -> let(P := nt.params, tags := nt.getTags(), [[ DFT(P[1][1], P[2]).withTags(tags) ]]),
        apply          := (nt, C, Nonterms) -> C[1]
    )
));

NewRulesFor(MDDFT, rec(

    #F RuleMDDFT_Tensor: MDDFT(n_1,n_2,...,n_t) = Tensor(DFT_n1, DFT_n2, ..., DFT_nt)
    #F
    MDDFT_Tensor := rec(
        switch := false,
        info :="MDDFT_n -> Tensor(DFT_n1,DFT_n2,...DFT_nt)",
        applicable := nt -> Length(nt.params[1])>1 and not nt.hasTags(),
        children  := nt -> [ List(nt.params[1],i->DFT(i, nt.params[2])) ],
        rule := (nt, C, cnt) -> Tensor(C)
#D        isApplicable := P -> Length(P[1])>1 and Length(P[3]) = 0,
#D        allChildren  := P -> [ List(P[1],i->DFT(i, P[2])) ],
#D        rule := (P,C) -> Tensor(C)
    ),

    #F RuleMDDFT_Dimless
    #F
    #F If N = RxS = n_1xn_2x...n_t and
    #F d1 = n_1* ..*n_(l-1), d2 = n_(l+1)*..*n_t, n_(l) = a*b then,
    #F MDDFT([n_1,..,n_t]) = Tensor(MDDFT([n_1,..,n_(l-1),a]), I(b), I(d2))*
    #F                       Tensor(I(d1), T(n_(l),b), I(d2))*
    #F                       Tensor(I(d1), I(a), MDDFT([b,n_(l+1),..,n_t])) *
    #F                       Tensor(I(d1), L(n_(l),a), I(d2))
    #F
    MDDFT_RowCol := rec (
        info := "MDDFT_n -> MDDFT_n/d, MDDFT_d",
        applicable := nt -> Length(nt.params[1]) > 1 and not nt.hasTags(),

        children := nt -> let(
            dims := nt.params[1],
            len := Length(dims),
            List([1..len-1],
            i -> [ MDDFT(dims{[1..i]}, nt.params[2]), MDDFT(dims{[i+1..len]}, nt.params[2]) ])),

        apply := (nt, C, Nonterms) -> let(
            a := Last(Nonterms[1].params[1]),
            n1 := Rows(Nonterms[1])/a,
            n2 := Rows(Nonterms[2]),
            Tensor(C[1], I(n2)) *
            Tensor(I(n1), Tensor(I(a), C[2]))
        )
#D    isApplicable := P -> Length(P[1]) > 1 and Length(P[3]) = 0,
#D
#D    allChildren := P -> let(
#D        dims := P[1],
#D        len := Length(dims),
#D        List([1..len-1],
#D        i -> [ MDDFT(dims{[1..i]}, P[2]), MDDFT(dims{[i+1..len]}, P[2]) ])),
#D
#D    rule := (P,C,Nonterms) -> let(
#D        a := Last(Nonterms[1].params[1]),
#D        n1 := Rows(Nonterms[1])/a,
#D        n2 := Rows(Nonterms[2]),
#D        Tensor(C[1], I(n2)) *
#D        Tensor(I(n1), Tensor(I(a), C[2])))
    ),

    MDDFT_Dimless := rec (
        info := "MDDFT_n -> MDDFT_n/d, MDDFT_d",
        applicable := nt -> Length(nt.params[1]) > 1 and ForAny(nt.params[1], x->not IsPrime(x)) and not nt.hasTags(),

        children := function(nt)
            local ch, dims, len, simple_splits, div_splits;
            dims := nt.params[1];
            len := Length(dims);
            return Concatenation(List([1..len], i -> let(
               left := dims{[1..i-1]},
               right := dims{[i+1..len]},
               List(DivisorPairs(dims[i]), split ->
                   [ MDDFT(Concatenation(left, [split[1]]), nt.params[2]),
             MDDFT(Concatenation([split[2]], right), nt.params[2]) ]))));
        end,

        apply := (nt, C, Nonterms) -> let(
            a := Last(Nonterms[1].params[1]),
            b := Nonterms[2].params[1][1],
            n1 := Rows(Nonterms[1])/a,
            n2 := Rows(Nonterms[2])/b,

            Tensor(Tensor(C[1], I(b)), I(n2)) *
            Diag(diagTensor(fConst(n1,1), Tw1(a*b,b,nt.params[2]), fConst(n2,1))) *
            Tensor(I(n1), Tensor(I(a), C[2])) *
            Tensor(I(n1), L(a*b,a), I(n2))
        )
#D    isApplicable := P -> Length(P[1]) > 1 and ForAny(P[1], x->not IsPrime(x)) and Length(P[3]) = 0,
#D
#D    allChildren := meth(self,P)
#D        local ch, dims, len, simple_splits, div_splits;
#D        dims := P[1];
#D        len := Length(dims);
#D        return Concatenation(List([1..len], i -> let(
#D           left := dims{[1..i-1]},
#D           right := dims{[i+1..len]},
#D           List(DivisorPairs(dims[i]), split ->
#D               [ MDDFT(Concatenation(left, [split[1]]), P[2]),
#D         MDDFT(Concatenation([split[2]], right), P[2]) ]))));
#D
#D    end,
#D
#D    rule := (P,C,Nonterms) -> let(
#D        a := Last(Nonterms[1].params[1]),
#D        b := Nonterms[2].params[1][1],
#D        n1 := Rows(Nonterms[1])/a,
#D        n2 := Rows(Nonterms[2])/b,
#D
#D        Tensor(Tensor(C[1], I(b)), I(n2)) *
#D        Diag(diagTensor(fConst(n1,1), T(a*b,b), fConst(n2,1))) *
#D        Tensor(I(n1), Tensor(I(a), C[2])) *
#D        Tensor(I(n1), L(a*b,a), I(n2)))
    ),

    #   2D Vector Radix
    #   NOTE: Put citation
    MDDFT_vrdx2D := rec(
        info          := "MDDFT([mn, rs],k) -> MDDFT([m, r], k%mr), MDDFT([n, s], k%ns)",

	switch        := false,
        maxSize       := false,

        applicable := nt -> Length(nt.params[1]) = 2 and ForAll(nt.params[1], x->not IsPrime(x))
                                    and not nt.hasTags(),

        children  := nt -> let(l:=List(nt.params[1], i->DivisorPairs(i)),
            idx:=Cartesian(List([1..Length(l)], i->[1..Length(l[i])])),
            rdx := List(idx, i->List([1..2], j->List([1..2], k->l[k][i[1]][j]))),
            Map2(rdx, (m,n) -> [ MDDFT(m, nt.params[2] mod Product(m)), MDDFT(n, nt.params[2] mod Product(n)) ])
        ),

        apply := (nt, C, cnt) -> let(mn := Product(nt.params[1]), m := Rows(C[1]), n := Rows(C[2]),
            Tensor(C[1], I(n)) *
            Diag(Tw1(mn, n, nt.params[2])) *
            Tensor(I(m), C[2]) *
            L(mn, m)
        )
    )
#D    isApplicable := (self,P) >> Length(P[1]) = 2 and ForAll(P[1], x->not IsPrime(x))
#D                                and Length(P[3]) = 0,
#D
#D    allChildren  := P -> let(l:=List(P[1], i->DivisorPairs(i)),
#D            idx:=Cartesian(List([1..Length(l)], i->[1..Length(l[i])])),
#D            rdx := List(idx, i->List([1..2], j->List([1..2], k->l[k][i[1]][j]))),
#D            Map2(rdx, (m,n) -> [ MDDFT(m, P[2] mod Product(m)), MDDFT(n, P[2] mod Product(n)) ])
#D        ),
#D
#D    rule := (P,C) -> let(mn := P[1], m := Rows(C[1]), n := Rows(C[2]),
#D        Tensor(C[1], I(n)) *
#D        T(mn, n, P[2]) *
#D        Tensor(I(m), C[2]) *
#D        L(mn, m))
#D    )

));


text:
"GameInfo"
{
	//
	// gameinfo.gi is the non-branch-varying content and can be integrated between branches.
	// Branch-varying info, such as the game/title and app IDs, is in gameinfo_branchspecific.gi.
	//

	gamelogo 1
	type		multiplayer_only

	nomodels 1
	nohimodel 1
	nocrosshair 0
	GameData	"dota.fgd"
	SupportsDX8	0
	nodegraph 0
	tonemapping 0 // Hide tonemapping ui in tools mode

	FileSystem
	{
		//
		// The code that loads this file automatically does a few things here:
		//
		// 1. For each "Game" search path, it adds a "GameBin" path, in <dir>\bin
		// 2. For each "Game" search path, it adds another "Game" path in front of it with _<langage> at the end.
		//    For example: c:\hl2\cstrike on a french machine would get a c:\hl2\cstrike_french path added to it.
		// 3. For the first "Game" search path, it adds a search path called "MOD".
		// 4. For the first "Game" search path, it adds a search path called "DEFAULT_WRITE_PATH".
		//

		//
		// Search paths are relative to the exe directory\..\
		//
		SearchPaths
		{
			// These are optional language paths. They must be mounted first, which is why there are first in the list.
			// *LANGUAGE* will be replaced with the actual language name. If not running a specific language, these paths will not be mounted
			Game				solyanka
			Game_Language		dota_*LANGUAGE*

			// These are optional low-violence paths. They will only get mounted if you're in a low-violence mode.
			Game_LowViolence	dota_lv

			Game				solyanka
			Game				dota
			Game				core

			Mod					solyanka
			Mod					dota

			Write				dota

			// These are optional language paths. They must be mounted first, which is why there are first in the list.
			// *LANGUAGE* will be replaced with the actual language name. If not running a specific language, these paths will not be mounted
			AddonRoot_Language	dota_*LANGUAGE*_addons

			AddonRoot			dota_addons

			// Note: addon content is included in publiccontent by default.
			PublicContent		dota_core
			PublicContent		core
		}

		AddonsChangeDefaultWritePath 0
	}

	MaterialSystem2
	{
		RenderModes
		{
			"game" "Default"
			"game" "DotaDeferred"
			"game" "DotaForward"
			"game" "Depth"

			"tools" "ToolsVis" // Visualization modes for all shaders (lighting only, normal maps only, etc.)
			"tools" "ToolsWireframe" // This should use the ToolsVis mode above instead of being its own mode
			"tools" "ToolsUtil" // Meant to be used to render tools sceneobjects that are mod-independent, like the origin grid
		}
	}

	Engine2
	{
		"HasModAppSystems" "1"
		"Capable64Bit" "1"
		"UsesVGui" "0"
		"UsesPanorama" "1"
		"PanoramaUIClientFromClient" "1" // IPanoramaUIClient is implemented by client.dll
		"HasGameUI" "1" // dota uses gameui
		"GameUIFromClient" "1"  // AND that gameui comes from client.dll
		"URLName" "dota2"
		"MsaaOverrideType" "0"
		"UsesBink" "0"
        "MaxNetworkableEntities" "10000"
        "MaxNonNetworkableEntities" "10000"
        "DefaultDXVersion" "11"
        // The shader binary cache on Linux can be over 100MB so
        // we have to allow very large allocations.
		"AllocWarnMB_linuxsteamrt64" "200"
		// Also currently demo files are loaded entirely into
		// memory for 64-bit binaries so they can use well
		// over 100MB at load time.  Zoid is looking at
		// converting that to streaming.
		"AllocWarnMB_osx64" "200"
		"AllocWarnMB_pc64" "200"
		"AllocWarnMB" "100"
		// There are some known large virtual reservations, such as the SBH, which
		// bypass this limit so we can be fairly conservative.
		"ReserveWarnMB" "64"

		"DefaultRenderSystem"					"-vulkan" [ $LINUX || $OSX ] // macOS/Linux default to Vulkan
		"SupportsVulkanParticleOptimizations"	"1"

		"RenderingPipeline"
		{
			"SkipPostProcessing" "1"
			"SupportsMSAA" "0"
		}

		"BugBait"
		{
			// Used by 'bug:' in chat to normalize report settings during playtests
			"Owner" "triage*"
			"Severity" "high"
			"Priority" "none"
			"Category" "---"
			"Product" "dota"
			"Component" "dota"
		}
	}

	SceneFileCache
	{
		"ServerUsesSceneImageFile" "0"
	}

	SceneSystem
	{
		"SunLightManagerCount" "0"
		"TransformTextureRowCount" "256"
		"CMTAtlasWidth" "1024"
		"CMTAtlasHeight" "512"
		"CMTAtlasChunkSize" "128"
		"DrawParticleChildrenSeparateFromParents" "1"
		"MaxAutoPartitions" "8"
		"LayerBatchThreshold" "512" [ $OSX && $CPU_EMULATED ] // Apple M1 - increase sc_layer_batch_threshold from 128 -> 512. Reduces TBDR memory bandwidth.
	}

	SoundSystem
	{
		"SteamAudioEnabled" "0"
		"DefaultWindowsXAudio" "1"
	}

	ToolsEnvironment
	{
		"Engine"	"Source 2"
		"ToolsDir"	"../sdktools"	// NOTE: Default Tools path. This is relative to the mod path.
		"DeveloperHelpURL" "https://developer.valvesoftware.com/wiki/Dota_2_Workshop_Tools"
		"ToolsProductName" "Dota2 Workshop Tools"
		"HideCoreMod"	"1"
	}

	Hammer
	{
		"fgd"						"dota.fgd"	// NOTE: This is relative to the 'mod' path.
		"GameFeatureSet"			"Dota"
		"LoadScriptEntities"		"0"
		"DefaultTextureScale"		"0.250000"
		"DefaultSolidEntity"		"trigger_dota"
		"DefaultPointEntity"		"info_player_start_dota"
		"NavMarkupEntity"			"func_nav_markup"
		"EnableDotaTools"			"1"
		"DefaultGridTileSet"		"/maps/tilesets/radiant_basic.vmap"
		"DefaultGridTileSet2"		"/maps/tilesets/dire_basic.vmap"
		"DotaMaxTrees"				"8000"
		"AddonMapCommand"			"dota_launch_custom_game"
		"PostMapLoadCommands"		"jointeam good" // Commands sent to the console by hammer after it finishes building a map and loads it
		"RequiredGameEntities"		"info_player_start_goodguys|info_player_start_dota; info_player_start_badguys|info_player_start_dota; env_global_light; ent_dota_game_events"
		"UnitsFiles"				"scripts/npc/npc_units.txt; scripts/npc/npc_units_staging.txt; scripts/npc/npc_units_custom.txt; scripts/npc/npc_heroes.txt; scripts/npc/npc_heroes_staging.txt"
		"ItemsFiles"				"scripts/npc/items.txt; scripts/npc/items_staging.txt; scripts/npc/npc_items_custom.txt"
		"OverlayBoxSize"			"16"
		"TileGridBlendOrderBGRA"	"1"
		"TileGridBlendDefaultColor"	"0 255 0"
	}

	MaterialEditor
	{
		"DefaultShader"			"global_lit_simple"
		"ExpressionHelpUrl"		"https://intranet.valvesoftware.com/index.php/Source_2.0/Shader_Format#Shader.2FMaterial_Expression_Syntax"
	}

	ModelCompile
	{
		"UseShadowFastPathHeuristic"	"1"
	}

	ModelDoc
	{
		"models_gamedata"			"models_gamedata.fgd"
		"export_modeldoc"			"0"
		"features"					"econitems;editorconfig"
	}

	ResourceCompiler
	{
		// Overrides of the default builders as specified in code, this controls which map builder steps
		// will be run when resource compiler is run for a map without specifiying any specific map builder
		// steps. Additionally this controls which builders are displayed in the hammer build dialog.
		DefaultMapBuilders
		{
			"light"		"0"	// Dota does not use baked lighting
			"envmap"	"0"	// Dota doesn't generate environment maps from the map
			"gridnav"	"1"	// Dota generates its grid navigation data by default
		}
		"DotaTileGrid"	"1"
	}

	RenderPipelineAliases
	{
		"Tools"			"Dota:Forward"
		"EnvMapBake"	"Dota"
	}

	AnimationSystem
	{
		NumDecodeCaches "16"
		DecodeCacheMemoryKB "512"
	}

	Particles
	{
		"GameSupportsLegacyShaders"	"1"
	}

	Panorama
	{
		"UsesSvg" "1"
	}

	RenderSystem
	{
		SwapChainSampleableDepth 1
		"VulkanUseSecondaryCommandBuffers"	"1" // Use secondary command buffers for more efficiency on tiled based renderers. All platforms to limit configurations.
		"VulkanSteamShaderCache"			"1"
		"OpenGLForceSM30"					"1"
	}
}


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

Class(LinearModel, rec(
    __call__ := (self, k, d) >> CopyFields(self, rec(k := k, d := d)),
    d := 0,
    k := 1,
    eval := (self, x) >> self.d + self.k * x
));

Class(ExpModel, rec(
    __call__ := (self, alpha, tau) >> CopyFields(self, rec(alpha := alpha, tau := tau)),
    alpha := 0.1,
    tau := 5,
    eval := (self, x) >> (self.alpha + (1 - d_exp(-self.tau * x))) / (1+self.alpha)
));

Class(ScratchModel, rec(
    config := rec(
        loadModel := (numPkts, pktSize) -> numPkts * pktSize / (0.2 * ExpModel(0.1, 0.2).eval(pktSize)),
        storeModel := (numPkts, pktSize) -> 1.1 * numPkts * pktSize / (0.2 * ExpModel(0.1, 0.2).eval(pktSize)),
        computeModel := x->LinearModel(1.1, 5).eval(x)
    ),
    getKernels := (self, spl) >>  List(Collect(self.updateInfo(spl), LSKernel), i->i.info),
    updateInfo := (self, spl) >>  SubstTopDown(spl, [@(1, Compose), @(2, DMAScat), @(3, LSKernel), @(4, DMAGath)],
        (e,cx) -> @(2).val *
            LSKernel(@(3).val.child(1), rec(
                opcount := @(3).val.info.opcount,
                loadFunc := @(4).val.func,
                storeFunc := @(2).val.func,
                free := When(IsBound(cx.ISum), Set(Concat(List(cx.ISum, i->i.var))), Set([])))) *
            @(4).val),

    getPacketData := meth(self, func)
        local domain, pktSize, numPkts;

        domain := func.domain();
        pktSize := 1;
        if ObjId(func) = fTensor and ObjId(Last(func.children())) = fId then
            pktSize := Last(func.children()).domain();
        fi;
        numPkts := domain / pktSize;

        return [pktSize, numPkts];
    end,

    modelStat := meth(self, spl)
        local kernels, stat, numPkts, pktSize, kernel, iter, func, n,
            flops, bw, loadcycles, storecycles, cpucycles, cycles;

        kernels := self.getKernels(spl);
        stat := [];

        for kernel in kernels do
            flops := kernel.opcount;
            cpucycles := self.config.computeModel(flops);

            n := kernel.loadFunc.domain();
            [pktSize, numPkts] := self.getPacketData(kernel.loadFunc);
            loadcycles := self.config.loadModel(numPkts, pktSize);
            [pktSize, numPkts] := self.getPacketData(kernel.storeFunc);
            storecycles := self.config.storeModel(numPkts, pktSize);
            iter := Product(List(kernel.free, i->i.range));
            Add(stat, rec(
                iter := iter,
                kernelcycles := Maximum(loadcycles, storecycles, cpucycles),
                loadcycles := loadcycles,
                storecycles := storecycles,
                cpucycles := cpucycles,
                balance := cpucycles / Maximum(loadcycles, storecycles)
            ));

        od;
        return stat;
    end,

    modelRuntime := meth(self, spl)
        local stat, s, runtime, cycles;

        runtime := 0;
        stat := self.modelStat(spl);

        for s in stat do
            cycles := s.loadcycles + s.storecycles + s.iter * s.kernelcycles;
            runtime := runtime + cycles;
        od;
        return When(IsInt(runtime), runtime, IntDouble(runtime));
    end,

    measureFunction := (rt, opts) -> let(s := SumsRuleTree(rt, opts),  paradigms.scratchpad.ScratchModel.modelRuntime(s))
));


text:
# Copyright (c) 2018-2021, Carnegie Mellon University
# See LICENSE for details

# Base change for DST-3
#    def := (mn, n) -> Let(m=>mn/n,
#                  Conjugate(DirectSum(Tensor(I(n-1), S(m)), I(m)),
#	                        L(mn, n) * IP(mn, DirectSum(J(n-1), I(1))))),
Class(B_DST3_U, Sym, rec(
    def := (mn, m) -> let(n := mn/m,
	DoNotReorder(SUMAcc(
		Mon(fId(mn),
		    II(mn),
		    II(mn)),
		Mon(fTensor(Z(m,1), fDirsum(J(n-1), fId(1))),
		    II(mn),
		    diagTensor(II(m, 1, m), II(n,n-1))))))));
#B_DST3_U := (mn,m) -> I(mn);

Class(B_DST4_U, Sym, rec(
    def := (mn, m) -> let(n := mn/m,
	DoNotReorder(SUMAcc(
		Mon(fId(mn),
		    II(mn),
		    II(mn)),
		Mon(fTensor(Z(m,1), J(n)),
		    II(mn),
		    diagTensor(II(m, 1, m), II(n))))))));

Class(B_DCT4_U, Sym, rec(
    def := (mn, m) -> let(n := mn/m,
	DoNotReorder(SUMAcc(
		Mon(fId(mn),
		    II(mn),
		    II(mn)),
		Mon(fTensor(Z(m,1), J(n)),
		    fConst(mn, -1),
		    diagTensor(II(m, 1, m), II(n))))))));

Class(B_DCT3_U, Sym, rec(
    def := (mn, m) -> let(n := mn/m,
	DoNotReorder(SUMAcc(
		Mon(fId(mn), II(mn),          diagTensor(II(m,0,1), II(n,0,1))),
		Mon(fId(mn), fConst(mn, 1/2), diagTensor(II(m,1,m), II(n,0,1))),
		Mon(fId(mn), II(mn),          diagTensor(II(m,0,m), II(n,1,n))),

		Mon(fTensor(Z(m,1), fDirsum(fId(1), J(n-1))),
		    II(mn),
		    diagTensor(II(m, 1, m), II(n,1,n))),

		Mon(fTensor(Z(m,2), fId(n)),
		    fConst(mn, -1/2),
		    diagTensor(II(m, 2, m), II(n,0,1))))))));

# inverse-transpose T-basis for DCT3
Class(B_DCT3_T_IT, Sym, rec(
    def := (mn, m) -> let(n := mn/m,
	DoNotReorder(SUMAcc(
		Mon(fId(mn),
		    II(mn),
		    II(mn)),
		Mon(fTensor(Z(m,m-1), fDirsum(fId(1), J(n-1))),
		    II(mn),
		    diagTensor(II(m, 0, m-1), II(n,1,n))))))));

Class(B_DCT3_T_Radix2, Sym, rec(
    def := (mn, r) -> let(n := mn/2,
	DoNotReorder(SUMAcc(
		Mon(fId(mn), II(mn),               diagTensor(II(2,0,1), II(n,0,n))),
		Mon(fId(mn), fConst(mn, cos(r)),   diagTensor(II(2,1,2), II(n,0,1))),
		Mon(fId(mn), fConst(mn, 2*cos(r)), diagTensor(II(2,1,2), II(n,1,n))),

		Mon(fTensor(Z(2,1), fDirsum(fId(1), J(n-1))),
		    fConst(mn, -1),
		    diagTensor(II(2, 1, 2), II(n,1,n))))))));


text:
mode := function(v)
  local c, m;
  c := Collected(SortedList(v));
  m := Maximum(List(c, x -> x[2]));
  return List(Filtered(c, x -> x[2] = m), y -> y[1]);
end;

mode([ 7, 5, 6, 1, 5, 5, 7, 12, 17, 6, 6, 5, 12, 3, 6 ]);
# [ 5, 6 ]


text:
for p in AlternatingGroup(4) do
    Print(p, "\n");
od;

()
(1,3,2)
(1,2,3)
(1,4,3)
(2,4,3)
(1,3)(2,4)
(1,2,4)
(1,4)(2,3)
(2,3,4)
(1,3,4)
(1,2)(3,4)
(1,4,2)