Files CCore/inc/StepEval.h CCore/src/StepEval.cpp
StepEval is an execution machine. It executes a set of functional objects in some undetermined order. But you may specify dependencies between these functors, aka evaluation steps. You may also dynamically create new ones during execution.
template <class Ctx> class StepEval : public Ctx { public: class Gate : public NoCopy { .... public: explicit Gate(StepEval *eval); ~Gate(); template <class FuncInit> RetStep<FunctorTypeOf<FuncInit> > createStep(FuncInit func_init,StepId dep={0}); // dep executes after void delay(StepId dep); void open(); void boost(); }; template <class ... SS> explicit StepEval(SS && ... ss) : Ctx( std::forward<SS>(ss)... ) {} ~StepEval(); Gate * createGate(); template <class OpenFuncInit,class FuncInit> Gate * createGate(OpenFuncInit openfunc_init,FuncInit func_init); template <class FuncInit> RetStep<FunctorTypeOf<FuncInit> > createStep(FuncInit func_init,StepId dep={0}); // dep executes after void run(); }; template <class Ctx> using StepGate = typename StepEval<Ctx>::Gate ;
StepEval is a template, it inherits its template parameter — Ctx, which is some execution context. StepEval constructor forwards its arguments to Ctx constructor. The only requirement for Ctx is it must provide the method getAlloc(). This method must return some alloc class object to be used for functor space allocation/deallocation. You may use the default class DefaultHeapAlloc.
class Ctx
{
....
public:
DefaultHeapAlloc getAlloc() { return DefaultHeapAlloc(); }
};
Once you create an instance of the StepEval class, you may create some steps for execution using the method createStep(). The first argument is a functor init object. The optional second argument is an id of the dependent step. StepEval ensures, that the dependent step is executed after, in particular, the correspondent functor exists during the call of the prerequisite step. Each step has an id of the transparent type StepId. The method createStep() returns the object of the type RetStep with two fields: the reference to the created functor obj and the step id id. You may use this id in further calls of the createStep(), you may also use the reference to the functor in prerequisite steps to supply some arguments, for example.
/* struct StepId */ struct StepId { void *ptr; }; /* struct RetStep<T> */ template <class T> struct RetStep { T &obj; StepId id; RetStep(T &obj_,StepId id_) : obj(obj_),id(id_) {} };
The method run() executes steps. Some steps may remain not executed due to cyclic dependencies on gates. A step execution is the call of the correspondent functor. The functor may have one of three forms:
class Functor1
{
public:
....
void operator () ();
};
class Functor2
{
public:
....
void operator () (StepEval<Ctx> &eval);
};
class Functor3
{
public:
....
void operator () (StepEval<Ctx> &eval,StepId dep);
};
In the third case the id of the dependent step is provided as the second argument. You may create additional steps with this id and these steps are executed before the dependent step.
Once step is executed it is destroyed. All remaining steps are destroyed by the StepEval destructor. For such steps the special method final() is called by the method run(), if it is defined in the correspondent class:
class Functor_final
{
public:
....
void operator () ();
void final(StepEval<Ctx> &eval);
};
Gate is an obstacle for the step execution. You may create a gate using methods createGate(). They are destroyed by the the StepEval destructor. The gate is closed right after the creation. You may open it by the method open(). Any gated steps are not executed while the gate is closed.
You may create a gated step using the method createStep() of the gate. You may also delay execution of the existing step by the method delay().
There are two methods createGate(). The first of them has no arguments and creates a normal gate. The second has two arguments. Both are functor initializers. This gate has an associated step, which automatically opens the gate after been executed. The first argument initialize this step. The second argument initializes a prerequisite step. This prerequisite can be "boosted" using the method boost() of the gate. Normally you don't need to do it manually. Gate is boosted automatically once it is closed and a gated step is created.
The test test2053.StepEval.cpp can be used to better understand how to work with StepEval and what is it good for. In this test we create a set of variables and associated expressions and evaluate them. An expression can refer to another variable, so the order of evaluation is hardly determined in general case. And cyclic dependencies can make this task impossible.
An expression is represented by the structure Expr, these structures forms a polymorphic linked set using the AnyPtr.
struct Expr : NoCopy
{
struct Const
{
int value;
explicit Const(int value_) : value(value_) {}
};
struct Var
{
ulen index;
explicit Var(ulen index_) : index(index_) {}
};
struct Neg
{
Expr *arg;
explicit Neg(Expr *arg_) : arg(arg_) {}
};
struct Add
{
Expr *arg1;
Expr *arg2;
Add(Expr *arg1_,Expr *arg2_) : arg1(arg1_),arg2(arg2_) {}
};
struct Mul
{
Expr *arg1;
Expr *arg2;
Mul(Expr *arg1_,Expr *arg2_) : arg1(arg1_),arg2(arg2_) {}
};
AnyPtr<Const,Var,Neg,Add,Mul> ptr;
....
};
The field ptr points to one of the inner structures: Const, Var, Neg, Add and Mul. These structures represents correspondent operations and contains arguments.
The variable set is represented by an array in the class Context. Elements of this array are structure. The field value is the value of the variable and must be evaluated from the expression, pointed by another field expr. The third field gate points to the StepEval gate, this gate is opened once the correspondent variable is evaluated and the value is recorded.
class Context : NoCopy
{
....
using Gate = StepGate<ContextPtr> ;
struct Var : NoCopy , NoThrowFlagsBase
{
int value;
Expr *expr;
Gate *gate;
Var() noexcept : value(0),expr(0),gate(0) {}
};
DynArray<Var> table;
....
private:
using Eval = StepEval<ContextPtr> ;
struct NegStep;
struct AddStep;
struct MulStep;
struct GetVarStep;
struct ExprStep;
struct GateFinalStep;
....
};
The family of inner structures NegStep, ... is used to perform evaluation steps. Each of them contains fields for operation arguments and reference where the result will be stored.
struct Context::NegStep
{
int arg;
int &ret;
explicit NegStep(int &ret_) : ret(ret_) {}
void operator () (Eval &eval)
{
Printf(Trace,"- #;\n",arg);
ret=-arg;
eval->count++;
}
};
struct Context::AddStep
{
int arg1;
int arg2;
int &ret;
explicit AddStep(int &ret_) : ret(ret_) {}
void operator () (Eval &eval)
{
Printf(Trace,"#; + #;\n",arg1,arg2);
ret=arg1+arg2;
eval->count++;
}
};
struct Context::MulStep
{
int arg1;
int arg2;
int &ret;
explicit MulStep(int &ret_) : ret(ret_) {}
void operator () (Eval &eval)
{
Printf(Trace,"#; * #;\n",arg1,arg2);
ret=arg1*arg2;
eval->count++;
}
};
struct Context::GetVarStep
{
const int &var;
int &ret;
GetVarStep(const int &var_,int &ret_) : var(var_),ret(ret_) {}
void operator () (Eval &eval)
{
Printf(Trace,"[] #;\n",var);
ret=var;
eval->count++;
}
};
These steps are simple: they take arguments, perform the required arithmetic operation and store the result (plus some extra actions).
struct Context::ExprStep
{
Expr *expr;
int &ret;
ExprStep(Expr *expr_,int &ret_) : expr(expr_),ret(ret_) {}
void operator () (Eval &,StepId,Expr::Const *ptr)
{
Printf(Trace,"#;\n",ptr->value);
ret=ptr->value;
}
void operator () (Eval &eval,StepId dep,Expr::Var *ptr)
{
ulen index=ptr->index;
Var &var=eval->table[index];
var.gate->createStep(GetVarStep(var.value,ret),dep);
}
void operator () (Eval &eval,StepId dep,Expr::Neg *ptr)
{
auto step=eval.createStep(NegStep(ret),dep);
eval.createStep(ExprStep(ptr->arg,step.obj.arg),step.id);
}
void operator () (Eval &eval,StepId dep,Expr::Add *ptr)
{
auto step=eval.createStep(AddStep(ret),dep);
eval.createStep(ExprStep(ptr->arg1,step.obj.arg1),step.id);
eval.createStep(ExprStep(ptr->arg2,step.obj.arg2),step.id);
}
void operator () (Eval &eval,StepId dep,Expr::Mul *ptr)
{
auto step=eval.createStep(MulStep(ret),dep);
eval.createStep(ExprStep(ptr->arg1,step.obj.arg1),step.id);
eval.createStep(ExprStep(ptr->arg2,step.obj.arg2),step.id);
}
void operator () (Eval &eval,StepId dep)
{
ElaborateAnyPtr(*this,eval,dep,expr->ptr);
eval->count++;
}
};
This step is more complicated. It takes the given expression, determines the exact type of it and creates required substeps to evaluate it. For example, to evaluate the Add expression three steps are created:
void operator () (Eval &eval,StepId dep,Expr::Add *ptr)
{
auto step=eval.createStep(AddStep(ret),dep);
eval.createStep(ExprStep(ptr->arg1,step.obj.arg1),step.id);
eval.createStep(ExprStep(ptr->arg2,step.obj.arg2),step.id);
}
First, the step AddStep is created. The dependent step is propagated to it. Then two steps are created to evaluate arguments. These steps have the AddStep as the dependent step, so they may use the correspondent functor object to store their results.
The GetVarStep step is created gated for the correspondent variable gate, so it is performed after this variable gets a value.
struct Context::GateFinalStep
{
ulen index;
explicit GateFinalStep(ulen index_) : index(index_) {}
void operator () (Eval &eval)
{
Printf(Trace,"[#;]\n",index);
eval->count++;
}
void final(Eval &)
{
Printf(Con,"Cyclic variable dependency #;\n",index);
}
};
This step is created per each variable as the opening gate step. It does nothing particular and contains the method final() to report about cyclic dependency.
void Context::eval()
{
Eval step_eval(this);
ulen len=table.getLen();
DynArray<ulen> order(len);
for(ulen index=0; index<len ;index++) order[index]=index;
for(ulen index=0; index+1<len ;index++)
{
ulen i=random.select_uint<ulen>(index,len-1);
if( i!=index ) Swap(order[index],order[i]);
}
for(ulen index=0; index<len ;index++)
{
ulen i=order[index];
Var &var=table[i];
var.gate=step_eval.createGate(GateFinalStep(i),ExprStep(var.expr,var.value));
}
step_eval.run();
}
And here is the evaluation process. This method creates the StepEval object, then per each variable the gate is created with two associated steps: expression step to evaluate the variable and the GateFinalStep. Then the method run() does the job.