diff options
Diffstat (limited to 'source/blender/functions')
16 files changed, 4709 insertions, 1 deletions
diff --git a/source/blender/functions/CMakeLists.txt b/source/blender/functions/CMakeLists.txt index f8d2acc74a8..3c27e9d5e19 100644 --- a/source/blender/functions/CMakeLists.txt +++ b/source/blender/functions/CMakeLists.txt @@ -28,14 +28,20 @@ set(INC_SYS set(SRC intern/cpp_types.cc + intern/field.cc intern/generic_vector_array.cc intern/generic_virtual_array.cc intern/generic_virtual_vector_array.cc intern/multi_function.cc intern/multi_function_builder.cc + intern/multi_function_procedure.cc + intern/multi_function_procedure_builder.cc + intern/multi_function_procedure_executor.cc FN_cpp_type.hh FN_cpp_type_make.hh + FN_field.hh + FN_field_cpp_type.hh FN_generic_pointer.hh FN_generic_span.hh FN_generic_value_map.hh @@ -48,6 +54,9 @@ set(SRC FN_multi_function_data_type.hh FN_multi_function_param_type.hh FN_multi_function_params.hh + FN_multi_function_procedure.hh + FN_multi_function_procedure_builder.hh + FN_multi_function_procedure_executor.hh FN_multi_function_signature.hh ) @@ -60,8 +69,10 @@ blender_add_lib(bf_functions "${SRC}" "${INC}" "${INC_SYS}" "${LIB}") if(WITH_GTESTS) set(TEST_SRC tests/FN_cpp_type_test.cc + tests/FN_field_test.cc tests/FN_generic_span_test.cc tests/FN_generic_vector_array_test.cc + tests/FN_multi_function_procedure_test.cc tests/FN_multi_function_test.cc ) set(TEST_LIB diff --git a/source/blender/functions/FN_field.hh b/source/blender/functions/FN_field.hh new file mode 100644 index 00000000000..25188531580 --- /dev/null +++ b/source/blender/functions/FN_field.hh @@ -0,0 +1,456 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + * + * A #Field represents a function that outputs a value based on an arbitrary number of inputs. The + * inputs for a specific field evaluation are provided by a #FieldContext. + * + * A typical example is a field that computes a displacement vector for every vertex on a mesh + * based on its position. + * + * Fields can be build, composed and evaluated at run-time. They are stored in a directed tree + * graph data structure, whereby each node is a #FieldNode and edges are dependencies. A #FieldNode + * has an arbitrary number of inputs and at least one output and a #Field references a specific + * output of a #FieldNode. The inputs of a #FieldNode are other fields. + * + * There are two different types of field nodes: + * - #FieldInput: Has no input and exactly one output. It represents an input to the entire field + * when it is evaluated. During evaluation, the value of this input is based on a #FieldContext. + * - #FieldOperation: Has an arbitrary number of field inputs and at least one output. Its main + * use is to compose multiple existing fields into new fields. + * + * When fields are evaluated, they are converted into a multi-function procedure which allows + * efficient compution. In the future, we might support different field evaluation mechanisms for + * e.g. the following scenarios: + * - Latency of a single evaluation is more important than throughput. + * - Evaluation should happen on other hardware like GPUs. + * + * Whenever possible, multiple fields should be evaluated together to avoid duplicate work when + * they share common sub-fields and a common context. + */ + +#include "BLI_string_ref.hh" +#include "BLI_vector.hh" + +#include "FN_generic_virtual_array.hh" +#include "FN_multi_function_builder.hh" +#include "FN_multi_function_procedure.hh" +#include "FN_multi_function_procedure_builder.hh" +#include "FN_multi_function_procedure_executor.hh" + +namespace blender::fn { + +/** + * A node in a field-tree. It has at least one output that can be referenced by fields. + */ +class FieldNode { + private: + bool is_input_; + + public: + FieldNode(bool is_input) : is_input_(is_input) + { + } + + ~FieldNode() = default; + + virtual const CPPType &output_cpp_type(int output_index) const = 0; + + bool is_input() const + { + return is_input_; + } + + bool is_operation() const + { + return !is_input_; + } + + virtual uint64_t hash() const + { + return get_default_hash(this); + } + + friend bool operator==(const FieldNode &a, const FieldNode &b) + { + return a.is_equal_to(b); + } + + virtual bool is_equal_to(const FieldNode &other) const + { + return this == &other; + } +}; + +/** + * Common base class for fields to avoid declaring the same methods for #GField and #GFieldRef. + */ +template<typename NodePtr> class GFieldBase { + protected: + NodePtr node_ = nullptr; + int node_output_index_ = 0; + + GFieldBase(NodePtr node, const int node_output_index) + : node_(std::move(node)), node_output_index_(node_output_index) + { + } + + public: + GFieldBase() = default; + + operator bool() const + { + return node_ != nullptr; + } + + friend bool operator==(const GFieldBase &a, const GFieldBase &b) + { + return &*a.node_ == &*b.node_ && a.node_output_index_ == b.node_output_index_; + } + + uint64_t hash() const + { + return get_default_hash_2(node_, node_output_index_); + } + + const fn::CPPType &cpp_type() const + { + return node_->output_cpp_type(node_output_index_); + } + + const FieldNode &node() const + { + return *node_; + } + + int node_output_index() const + { + return node_output_index_; + } +}; + +/** + * A field whose output type is only known at run-time. + */ +class GField : public GFieldBase<std::shared_ptr<FieldNode>> { + public: + GField() = default; + + GField(std::shared_ptr<FieldNode> node, const int node_output_index = 0) + : GFieldBase<std::shared_ptr<FieldNode>>(std::move(node), node_output_index) + { + } +}; + +/** + * Same as #GField but is cheaper to copy/move around, because it does not contain a + * #std::shared_ptr. + */ +class GFieldRef : public GFieldBase<const FieldNode *> { + public: + GFieldRef() = default; + + GFieldRef(const GField &field) + : GFieldBase<const FieldNode *>(&field.node(), field.node_output_index()) + { + } + + GFieldRef(const FieldNode &node, const int node_output_index = 0) + : GFieldBase<const FieldNode *>(&node, node_output_index) + { + } +}; + +/** + * A typed version of #GField. It has the same memory layout as #GField. + */ +template<typename T> class Field : public GField { + public: + Field() = default; + + Field(GField field) : GField(std::move(field)) + { + BLI_assert(this->cpp_type().template is<T>()); + } + + Field(std::shared_ptr<FieldNode> node, const int node_output_index = 0) + : Field(GField(std::move(node), node_output_index)) + { + } +}; + +/** + * A #FieldNode that allows composing existing fields into new fields. + */ +class FieldOperation : public FieldNode { + /** + * The multi-function used by this node. It is optionally owned. + * Multi-functions with mutable or vector parameters are not supported currently. + */ + std::unique_ptr<const MultiFunction> owned_function_; + const MultiFunction *function_; + + /** Inputs to the operation. */ + blender::Vector<GField> inputs_; + + public: + FieldOperation(std::unique_ptr<const MultiFunction> function, Vector<GField> inputs = {}) + : FieldNode(false), owned_function_(std::move(function)), inputs_(std::move(inputs)) + { + function_ = owned_function_.get(); + } + + FieldOperation(const MultiFunction &function, Vector<GField> inputs = {}) + : FieldNode(false), function_(&function), inputs_(std::move(inputs)) + { + } + + Span<GField> inputs() const + { + return inputs_; + } + + const MultiFunction &multi_function() const + { + return *function_; + } + + const CPPType &output_cpp_type(int output_index) const override + { + int output_counter = 0; + for (const int param_index : function_->param_indices()) { + MFParamType param_type = function_->param_type(param_index); + if (param_type.is_output()) { + if (output_counter == output_index) { + return param_type.data_type().single_type(); + } + output_counter++; + } + } + BLI_assert_unreachable(); + return CPPType::get<float>(); + } +}; + +class FieldContext; + +/** + * A #FieldNode that represents an input to the entire field-tree. + */ +class FieldInput : public FieldNode { + protected: + const CPPType *type_; + std::string debug_name_; + + public: + FieldInput(const CPPType &type, std::string debug_name = "") + : FieldNode(true), type_(&type), debug_name_(std::move(debug_name)) + { + } + + /** + * Get the value of this specific input based on the given context. The returned virtual array, + * should live at least as long as the passed in #scope. May return null. + */ + virtual const GVArray *get_varray_for_context(const FieldContext &context, + IndexMask mask, + ResourceScope &scope) const = 0; + + blender::StringRef debug_name() const + { + return debug_name_; + } + + const CPPType &cpp_type() const + { + return *type_; + } + + const CPPType &output_cpp_type(int output_index) const override + { + BLI_assert(output_index == 0); + UNUSED_VARS_NDEBUG(output_index); + return *type_; + } +}; + +/** + * Provides inputs for a specific field evaluation. + */ +class FieldContext { + public: + ~FieldContext() = default; + + virtual const GVArray *get_varray_for_input(const FieldInput &field_input, + IndexMask mask, + ResourceScope &scope) const; +}; + +/** + * Utility class that makes it easier to evaluate fields. + */ +class FieldEvaluator : NonMovable, NonCopyable { + private: + struct OutputPointerInfo { + void *dst = nullptr; + /* When a destination virtual array is provided for an input, this is + * unnecessary, otherwise this is used to construct the required virtual array. */ + void (*set)(void *dst, const GVArray &varray, ResourceScope &scope) = nullptr; + }; + + ResourceScope scope_; + const FieldContext &context_; + const IndexMask mask_; + Vector<GField> fields_to_evaluate_; + Vector<GVMutableArray *> dst_varrays_; + Vector<const GVArray *> evaluated_varrays_; + Vector<OutputPointerInfo> output_pointer_infos_; + bool is_evaluated_ = false; + + public: + /** Takes #mask by pointer because the mask has to live longer than the evaluator. */ + FieldEvaluator(const FieldContext &context, const IndexMask *mask) + : context_(context), mask_(*mask) + { + } + + /** Construct a field evaluator for all indices less than #size. */ + FieldEvaluator(const FieldContext &context, const int64_t size) : context_(context), mask_(size) + { + } + + ~FieldEvaluator() + { + /* While this assert isn't strictly necessary, and could be replaced with a warning, + * it will catch cases where someone forgets to call #evaluate(). */ + BLI_assert(is_evaluated_); + } + + /** + * \param field: Field to add to the evaluator. + * \param dst: Mutable virtual array that the evaluated result for this field is be written into. + */ + int add_with_destination(GField field, GVMutableArray &dst); + + /** Same as #add_with_destination but typed. */ + template<typename T> int add_with_destination(Field<T> field, VMutableArray<T> &dst) + { + GVMutableArray &varray = scope_.construct<GVMutableArray_For_VMutableArray<T>>(__func__, dst); + return this->add_with_destination(GField(std::move(field)), varray); + } + + /** + * \param field: Field to add to the evaluator. + * \param dst: Mutable span that the evaluated result for this field is be written into. + * \note: When the output may only be used as a single value, the version of this function with + * a virtual array result array should be used. + */ + int add_with_destination(GField field, GMutableSpan dst); + + /** + * \param field: Field to add to the evaluator. + * \param dst: Mutable span that the evaluated result for this field is be written into. + * \note: When the output may only be used as a single value, the version of this function with + * a virtual array result array should be used. + */ + template<typename T> int add_with_destination(Field<T> field, MutableSpan<T> dst) + { + GVMutableArray &varray = scope_.construct<GVMutableArray_For_MutableSpan<T>>(__func__, dst); + return this->add_with_destination(std::move(field), varray); + } + + int add(GField field, const GVArray **varray_ptr); + + /** + * \param field: Field to add to the evaluator. + * \param varray_ptr: Once #evaluate is called, the resulting virtual array will be will be + * assigned to the given position. + * \return Index of the field in the evaluator which can be used in the #get_evaluated methods. + */ + template<typename T> int add(Field<T> field, const VArray<T> **varray_ptr) + { + const int field_index = fields_to_evaluate_.append_and_get_index(std::move(field)); + dst_varrays_.append(nullptr); + output_pointer_infos_.append(OutputPointerInfo{ + varray_ptr, [](void *dst, const GVArray &varray, ResourceScope &scope) { + *(const VArray<T> **)dst = &*scope.construct<GVArray_Typed<T>>(__func__, varray); + }}); + return field_index; + } + + /** + * \return Index of the field in the evaluator which can be used in the #get_evaluated methods. + */ + int add(GField field); + + /** + * Evaluate all fields on the evaluator. This can only be called once. + */ + void evaluate(); + + const GVArray &get_evaluated(const int field_index) const + { + BLI_assert(is_evaluated_); + return *evaluated_varrays_[field_index]; + } + + template<typename T> const VArray<T> &get_evaluated(const int field_index) + { + const GVArray &varray = this->get_evaluated(field_index); + GVArray_Typed<T> &typed_varray = scope_.construct<GVArray_Typed<T>>(__func__, varray); + return *typed_varray; + } + + /** + * Retrieve the output of an evaluated boolean field and convert it to a mask, which can be used + * to avoid calculations for unnecessary elements later on. The evaluator will own the indices in + * some cases, so it must live at least as long as the returned mask. + */ + IndexMask get_evaluated_as_mask(const int field_index); +}; + +Vector<const GVArray *> evaluate_fields(ResourceScope &scope, + Span<GFieldRef> fields_to_evaluate, + IndexMask mask, + const FieldContext &context, + Span<GVMutableArray *> dst_varrays = {}); + +/* -------------------------------------------------------------------- + * Utility functions for simple field creation and evaluation. + */ + +void evaluate_constant_field(const GField &field, void *r_value); + +template<typename T> T evaluate_constant_field(const Field<T> &field) +{ + T value; + value.~T(); + evaluate_constant_field(field, &value); + return value; +} + +template<typename T> Field<T> make_constant_field(T value) +{ + auto constant_fn = std::make_unique<fn::CustomMF_Constant<T>>(std::forward<T>(value)); + auto operation = std::make_shared<FieldOperation>(std::move(constant_fn)); + return Field<T>{GField{std::move(operation), 0}}; +} + +} // namespace blender::fn diff --git a/source/blender/functions/FN_field_cpp_type.hh b/source/blender/functions/FN_field_cpp_type.hh new file mode 100644 index 00000000000..5e6f1b5a585 --- /dev/null +++ b/source/blender/functions/FN_field_cpp_type.hh @@ -0,0 +1,72 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + */ + +#include "FN_cpp_type_make.hh" +#include "FN_field.hh" + +namespace blender::fn { + +template<typename T> struct FieldCPPTypeParam { +}; + +class FieldCPPType : public CPPType { + private: + const CPPType &field_type_; + + public: + template<typename T> + FieldCPPType(FieldCPPTypeParam<Field<T>> /* unused */, StringRef debug_name) + : CPPType(CPPTypeParam<Field<T>, CPPTypeFlags::None>(), debug_name), + field_type_(CPPType::get<T>()) + { + } + + const CPPType &field_type() const + { + return field_type_; + } + + /* Ensure that #GField and #Field<T> have the same layout, to enable casting between the two. */ + static_assert(sizeof(Field<int>) == sizeof(GField)); + static_assert(sizeof(Field<int>) == sizeof(Field<std::string>)); + + const GField &get_gfield(const void *field) const + { + return *(const GField *)field; + } + + void construct_from_gfield(void *r_value, const GField &gfield) const + { + new (r_value) GField(gfield); + } +}; + +} // namespace blender::fn + +#define MAKE_FIELD_CPP_TYPE(DEBUG_NAME, FIELD_TYPE) \ + template<> \ + const blender::fn::CPPType &blender::fn::CPPType::get_impl<blender::fn::Field<FIELD_TYPE>>() \ + { \ + static blender::fn::FieldCPPType cpp_type{ \ + blender::fn::FieldCPPTypeParam<blender::fn::Field<FIELD_TYPE>>(), STRINGIFY(DEBUG_NAME)}; \ + return cpp_type; \ + } diff --git a/source/blender/functions/FN_multi_function_builder.hh b/source/blender/functions/FN_multi_function_builder.hh index 7a526bb640b..d13615ced07 100644 --- a/source/blender/functions/FN_multi_function_builder.hh +++ b/source/blender/functions/FN_multi_function_builder.hh @@ -417,4 +417,13 @@ class CustomMF_DefaultOutput : public MultiFunction { void call(IndexMask mask, MFParams params, MFContext context) const override; }; +class CustomMF_GenericCopy : public MultiFunction { + private: + MFSignature signature_; + + public: + CustomMF_GenericCopy(StringRef name, MFDataType data_type); + void call(IndexMask mask, MFParams params, MFContext context) const override; +}; + } // namespace blender::fn diff --git a/source/blender/functions/FN_multi_function_params.hh b/source/blender/functions/FN_multi_function_params.hh index a480287d578..5af86c7c284 100644 --- a/source/blender/functions/FN_multi_function_params.hh +++ b/source/blender/functions/FN_multi_function_params.hh @@ -195,7 +195,7 @@ class MFParams { template<typename T> const VArray<T> &readonly_single_input(int param_index, StringRef name = "") { const GVArray &array = this->readonly_single_input(param_index, name); - return builder_->scope_.construct<VArray_For_GVArray<T>>(__func__, array); + return builder_->scope_.construct<GVArray_Typed<T>>(__func__, array); } const GVArray &readonly_single_input(int param_index, StringRef name = "") { diff --git a/source/blender/functions/FN_multi_function_procedure.hh b/source/blender/functions/FN_multi_function_procedure.hh new file mode 100644 index 00000000000..62f2292c1d9 --- /dev/null +++ b/source/blender/functions/FN_multi_function_procedure.hh @@ -0,0 +1,452 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + */ + +#include "FN_multi_function.hh" + +namespace blender::fn { + +class MFVariable; +class MFInstruction; +class MFCallInstruction; +class MFBranchInstruction; +class MFDestructInstruction; +class MFDummyInstruction; +class MFReturnInstruction; +class MFProcedure; + +/** Every instruction has exactly one of these types. */ +enum class MFInstructionType { + Call, + Branch, + Destruct, + Dummy, + Return, +}; + +/** + * A variable is similar to a virtual register in other libraries. During evaluation, every is + * either uninitialized or contains a value for every index (remember, a multi-function procedure + * is always evaluated for many indices at the same time). + */ +class MFVariable : NonCopyable, NonMovable { + private: + MFDataType data_type_; + Vector<MFInstruction *> users_; + std::string name_; + int id_; + + friend MFProcedure; + friend MFCallInstruction; + friend MFBranchInstruction; + friend MFDestructInstruction; + + public: + MFDataType data_type() const; + Span<MFInstruction *> users(); + + StringRefNull name() const; + void set_name(std::string name); + + int id() const; +}; + +/** Base class for all instruction types. */ +class MFInstruction : NonCopyable, NonMovable { + protected: + MFInstructionType type_; + Vector<MFInstruction *> prev_; + + friend MFProcedure; + friend MFCallInstruction; + friend MFBranchInstruction; + friend MFDestructInstruction; + friend MFDummyInstruction; + friend MFReturnInstruction; + + public: + MFInstructionType type() const; + + /** + * Other instructions that come before this instruction. There can be multiple previous + * instructions when branching is used in the procedure. + */ + Span<MFInstruction *> prev(); + Span<const MFInstruction *> prev() const; +}; + +/** + * References a multi-function that is evaluated when the instruction is executed. It also + * references the variables whose data will be passed into the multi-function. + */ +class MFCallInstruction : public MFInstruction { + private: + const MultiFunction *fn_ = nullptr; + MFInstruction *next_ = nullptr; + MutableSpan<MFVariable *> params_; + + friend MFProcedure; + + public: + const MultiFunction &fn() const; + + MFInstruction *next(); + const MFInstruction *next() const; + void set_next(MFInstruction *instruction); + + void set_param_variable(int param_index, MFVariable *variable); + void set_params(Span<MFVariable *> variables); + + Span<MFVariable *> params(); + Span<const MFVariable *> params() const; +}; + +/** + * What makes a branch instruction special is that it has two successor instructions. One that will + * be used when a condition variable was true, and one otherwise. + */ +class MFBranchInstruction : public MFInstruction { + private: + MFVariable *condition_ = nullptr; + MFInstruction *branch_true_ = nullptr; + MFInstruction *branch_false_ = nullptr; + + friend MFProcedure; + + public: + MFVariable *condition(); + const MFVariable *condition() const; + void set_condition(MFVariable *variable); + + MFInstruction *branch_true(); + const MFInstruction *branch_true() const; + void set_branch_true(MFInstruction *instruction); + + MFInstruction *branch_false(); + const MFInstruction *branch_false() const; + void set_branch_false(MFInstruction *instruction); +}; + +/** + * A destruct instruction destructs a single variable. So the variable value will be uninitialized + * after this instruction. All variables that are not output variables of the procedure, have to be + * destructed before the procedure ends. Destructing early is generally a good thing, because it + * might help with memory buffer reuse, which decreases memory-usage and increases performance. + */ +class MFDestructInstruction : public MFInstruction { + private: + MFVariable *variable_ = nullptr; + MFInstruction *next_ = nullptr; + + friend MFProcedure; + + public: + MFVariable *variable(); + const MFVariable *variable() const; + void set_variable(MFVariable *variable); + + MFInstruction *next(); + const MFInstruction *next() const; + void set_next(MFInstruction *instruction); +}; + +/** + * This instruction does nothing, it just exists to building a procedure simpler in some cases. + */ +class MFDummyInstruction : public MFInstruction { + private: + MFInstruction *next_ = nullptr; + + friend MFProcedure; + + public: + MFInstruction *next(); + const MFInstruction *next() const; + void set_next(MFInstruction *instruction); +}; + +/** + * This instruction ends the procedure. + */ +class MFReturnInstruction : public MFInstruction { +}; + +/** + * Inputs and outputs of the entire procedure network. + */ +struct MFParameter { + MFParamType::InterfaceType type; + MFVariable *variable; +}; + +struct ConstMFParameter { + MFParamType::InterfaceType type; + const MFVariable *variable; +}; + +/** + * A multi-function procedure allows composing multi-functions in arbitrary ways. It consists of + * variables and instructions that operate on those variables. Branching and looping within the + * procedure is supported as well. + * + * Typically, a #MFProcedure should be constructed using a #MFProcedureBuilder, which has many more + * utility methods for common use cases. + */ +class MFProcedure : NonCopyable, NonMovable { + private: + LinearAllocator<> allocator_; + Vector<MFCallInstruction *> call_instructions_; + Vector<MFBranchInstruction *> branch_instructions_; + Vector<MFDestructInstruction *> destruct_instructions_; + Vector<MFDummyInstruction *> dummy_instructions_; + Vector<MFReturnInstruction *> return_instructions_; + Vector<MFVariable *> variables_; + Vector<MFParameter> params_; + MFInstruction *entry_ = nullptr; + + friend class MFProcedureDotExport; + + public: + MFProcedure() = default; + ~MFProcedure(); + + MFVariable &new_variable(MFDataType data_type, std::string name = ""); + MFCallInstruction &new_call_instruction(const MultiFunction &fn); + MFBranchInstruction &new_branch_instruction(); + MFDestructInstruction &new_destruct_instruction(); + MFDummyInstruction &new_dummy_instruction(); + MFReturnInstruction &new_return_instruction(); + + void add_parameter(MFParamType::InterfaceType interface_type, MFVariable &variable); + + Span<ConstMFParameter> params() const; + + MFInstruction *entry(); + const MFInstruction *entry() const; + void set_entry(MFInstruction &entry); + + Span<MFVariable *> variables(); + Span<const MFVariable *> variables() const; + + std::string to_dot() const; + + bool validate() const; + + private: + bool validate_all_instruction_pointers_set() const; + bool validate_all_params_provided() const; + bool validate_same_variables_in_one_call() const; + bool validate_parameters() const; + bool validate_initialization() const; + + struct InitState { + bool can_be_initialized = false; + bool can_be_uninitialized = false; + }; + + InitState find_initialization_state_before_instruction(const MFInstruction &target_instruction, + const MFVariable &variable) const; +}; + +namespace multi_function_procedure_types { +using MFVariable = fn::MFVariable; +using MFInstruction = fn::MFInstruction; +using MFCallInstruction = fn::MFCallInstruction; +using MFBranchInstruction = fn::MFBranchInstruction; +using MFDestructInstruction = fn::MFDestructInstruction; +using MFProcedure = fn::MFProcedure; +} // namespace multi_function_procedure_types + +/* -------------------------------------------------------------------- + * MFVariable inline methods. + */ + +inline MFDataType MFVariable::data_type() const +{ + return data_type_; +} + +inline Span<MFInstruction *> MFVariable::users() +{ + return users_; +} + +inline StringRefNull MFVariable::name() const +{ + return name_; +} + +inline int MFVariable::id() const +{ + return id_; +} + +/* -------------------------------------------------------------------- + * MFInstruction inline methods. + */ + +inline MFInstructionType MFInstruction::type() const +{ + return type_; +} + +inline Span<MFInstruction *> MFInstruction::prev() +{ + return prev_; +} + +inline Span<const MFInstruction *> MFInstruction::prev() const +{ + return prev_; +} + +/* -------------------------------------------------------------------- + * MFCallInstruction inline methods. + */ + +inline const MultiFunction &MFCallInstruction::fn() const +{ + return *fn_; +} + +inline MFInstruction *MFCallInstruction::next() +{ + return next_; +} + +inline const MFInstruction *MFCallInstruction::next() const +{ + return next_; +} + +inline Span<MFVariable *> MFCallInstruction::params() +{ + return params_; +} + +inline Span<const MFVariable *> MFCallInstruction::params() const +{ + return params_; +} + +/* -------------------------------------------------------------------- + * MFBranchInstruction inline methods. + */ + +inline MFVariable *MFBranchInstruction::condition() +{ + return condition_; +} + +inline const MFVariable *MFBranchInstruction::condition() const +{ + return condition_; +} + +inline MFInstruction *MFBranchInstruction::branch_true() +{ + return branch_true_; +} + +inline const MFInstruction *MFBranchInstruction::branch_true() const +{ + return branch_true_; +} + +inline MFInstruction *MFBranchInstruction::branch_false() +{ + return branch_false_; +} + +inline const MFInstruction *MFBranchInstruction::branch_false() const +{ + return branch_false_; +} + +/* -------------------------------------------------------------------- + * MFDestructInstruction inline methods. + */ + +inline MFVariable *MFDestructInstruction::variable() +{ + return variable_; +} + +inline const MFVariable *MFDestructInstruction::variable() const +{ + return variable_; +} + +inline MFInstruction *MFDestructInstruction::next() +{ + return next_; +} + +inline const MFInstruction *MFDestructInstruction::next() const +{ + return next_; +} + +/* -------------------------------------------------------------------- + * MFDummyInstruction inline methods. + */ + +inline MFInstruction *MFDummyInstruction::next() +{ + return next_; +} + +inline const MFInstruction *MFDummyInstruction::next() const +{ + return next_; +} + +/* -------------------------------------------------------------------- + * MFProcedure inline methods. + */ + +inline Span<ConstMFParameter> MFProcedure::params() const +{ + static_assert(sizeof(MFParameter) == sizeof(ConstMFParameter)); + return params_.as_span().cast<ConstMFParameter>(); +} + +inline MFInstruction *MFProcedure::entry() +{ + return entry_; +} + +inline const MFInstruction *MFProcedure::entry() const +{ + return entry_; +} + +inline Span<MFVariable *> MFProcedure::variables() +{ + return variables_; +} + +inline Span<const MFVariable *> MFProcedure::variables() const +{ + return variables_; +} + +} // namespace blender::fn diff --git a/source/blender/functions/FN_multi_function_procedure_builder.hh b/source/blender/functions/FN_multi_function_procedure_builder.hh new file mode 100644 index 00000000000..d5e45470a0e --- /dev/null +++ b/source/blender/functions/FN_multi_function_procedure_builder.hh @@ -0,0 +1,260 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + */ + +#include "FN_multi_function_procedure.hh" + +namespace blender::fn { + +/** + * An #MFInstructionCursor points to a position in a multi-function procedure, where an instruction + * can be inserted. + */ +class MFInstructionCursor { + private: + MFInstruction *instruction_ = nullptr; + /* Only used when it is a branch instruction. */ + bool branch_output_ = false; + /* Only used when instruction is null. */ + bool is_entry_ = false; + + public: + MFInstructionCursor() = default; + + MFInstructionCursor(MFCallInstruction &instruction); + MFInstructionCursor(MFDestructInstruction &instruction); + MFInstructionCursor(MFBranchInstruction &instruction, bool branch_output); + MFInstructionCursor(MFDummyInstruction &instruction); + + static MFInstructionCursor Entry(); + + void insert(MFProcedure &procedure, MFInstruction *new_instruction); +}; + +/** + * Utility class to build a #MFProcedure. + */ +class MFProcedureBuilder { + private: + /** Procedure that is being build. */ + MFProcedure *procedure_ = nullptr; + /** Cursors where the next instruction should be inserted. */ + Vector<MFInstructionCursor> cursors_; + + public: + struct Branch; + struct Loop; + + MFProcedureBuilder(MFProcedure &procedure, + MFInstructionCursor initial_cursor = MFInstructionCursor::Entry()); + + MFProcedureBuilder(Span<MFProcedureBuilder *> builders); + + MFProcedureBuilder(Branch &branch); + + void set_cursor(const MFInstructionCursor &cursor); + void set_cursor(Span<MFInstructionCursor> cursors); + void set_cursor(Span<MFProcedureBuilder *> builders); + void set_cursor_after_branch(Branch &branch); + void set_cursor_after_loop(Loop &loop); + + void add_destruct(MFVariable &variable); + void add_destruct(Span<MFVariable *> variables); + + MFReturnInstruction &add_return(); + + Branch add_branch(MFVariable &condition); + + Loop add_loop(); + void add_loop_continue(Loop &loop); + void add_loop_break(Loop &loop); + + MFCallInstruction &add_call_with_no_variables(const MultiFunction &fn); + MFCallInstruction &add_call_with_all_variables(const MultiFunction &fn, + Span<MFVariable *> param_variables); + + Vector<MFVariable *> add_call(const MultiFunction &fn, + Span<MFVariable *> input_and_mutable_variables = {}); + + template<int OutputN> + std::array<MFVariable *, OutputN> add_call(const MultiFunction &fn, + Span<MFVariable *> input_and_mutable_variables = {}); + + void add_parameter(MFParamType::InterfaceType interface_type, MFVariable &variable); + MFVariable &add_parameter(MFParamType param_type, std::string name = ""); + + MFVariable &add_input_parameter(MFDataType data_type, std::string name = ""); + template<typename T> MFVariable &add_single_input_parameter(std::string name = ""); + template<typename T> MFVariable &add_single_mutable_parameter(std::string name = ""); + + void add_output_parameter(MFVariable &variable); + + private: + void link_to_cursors(MFInstruction *instruction); +}; + +struct MFProcedureBuilder::Branch { + MFProcedureBuilder branch_true; + MFProcedureBuilder branch_false; +}; + +struct MFProcedureBuilder::Loop { + MFInstruction *begin = nullptr; + MFDummyInstruction *end = nullptr; +}; + +/* -------------------------------------------------------------------- + * MFInstructionCursor inline methods. + */ + +inline MFInstructionCursor::MFInstructionCursor(MFCallInstruction &instruction) + : instruction_(&instruction) +{ +} + +inline MFInstructionCursor::MFInstructionCursor(MFDestructInstruction &instruction) + : instruction_(&instruction) +{ +} + +inline MFInstructionCursor::MFInstructionCursor(MFBranchInstruction &instruction, + bool branch_output) + : instruction_(&instruction), branch_output_(branch_output) +{ +} + +inline MFInstructionCursor::MFInstructionCursor(MFDummyInstruction &instruction) + : instruction_(&instruction) +{ +} + +inline MFInstructionCursor MFInstructionCursor::Entry() +{ + MFInstructionCursor cursor; + cursor.is_entry_ = true; + return cursor; +} + +/* -------------------------------------------------------------------- + * MFProcedureBuilder inline methods. + */ + +inline MFProcedureBuilder::MFProcedureBuilder(Branch &branch) + : MFProcedureBuilder(*branch.branch_true.procedure_) +{ + this->set_cursor_after_branch(branch); +} + +inline MFProcedureBuilder::MFProcedureBuilder(MFProcedure &procedure, + MFInstructionCursor initial_cursor) + : procedure_(&procedure), cursors_({initial_cursor}) +{ +} + +inline MFProcedureBuilder::MFProcedureBuilder(Span<MFProcedureBuilder *> builders) + : MFProcedureBuilder(*builders[0]->procedure_) +{ + this->set_cursor(builders); +} + +inline void MFProcedureBuilder::set_cursor(const MFInstructionCursor &cursor) +{ + cursors_ = {cursor}; +} + +inline void MFProcedureBuilder::set_cursor(Span<MFInstructionCursor> cursors) +{ + cursors_ = cursors; +} + +inline void MFProcedureBuilder::set_cursor_after_branch(Branch &branch) +{ + this->set_cursor({&branch.branch_false, &branch.branch_true}); +} + +inline void MFProcedureBuilder::set_cursor_after_loop(Loop &loop) +{ + this->set_cursor(MFInstructionCursor{*loop.end}); +} + +inline void MFProcedureBuilder::set_cursor(Span<MFProcedureBuilder *> builders) +{ + cursors_.clear(); + for (MFProcedureBuilder *builder : builders) { + cursors_.extend(builder->cursors_); + } +} + +template<int OutputN> +inline std::array<MFVariable *, OutputN> MFProcedureBuilder::add_call( + const MultiFunction &fn, Span<MFVariable *> input_and_mutable_variables) +{ + Vector<MFVariable *> output_variables = this->add_call(fn, input_and_mutable_variables); + BLI_assert(output_variables.size() == OutputN); + + std::array<MFVariable *, OutputN> output_array; + initialized_copy_n(output_variables.data(), OutputN, output_array.data()); + return output_array; +} + +inline void MFProcedureBuilder::add_parameter(MFParamType::InterfaceType interface_type, + MFVariable &variable) +{ + procedure_->add_parameter(interface_type, variable); +} + +inline MFVariable &MFProcedureBuilder::add_parameter(MFParamType param_type, std::string name) +{ + MFVariable &variable = procedure_->new_variable(param_type.data_type(), std::move(name)); + this->add_parameter(param_type.interface_type(), variable); + return variable; +} + +inline MFVariable &MFProcedureBuilder::add_input_parameter(MFDataType data_type, std::string name) +{ + return this->add_parameter(MFParamType(MFParamType::Input, data_type), std::move(name)); +} + +template<typename T> +inline MFVariable &MFProcedureBuilder::add_single_input_parameter(std::string name) +{ + return this->add_parameter(MFParamType::ForSingleInput(CPPType::get<T>()), std::move(name)); +} + +template<typename T> +inline MFVariable &MFProcedureBuilder::add_single_mutable_parameter(std::string name) +{ + return this->add_parameter(MFParamType::ForMutableSingle(CPPType::get<T>()), std::move(name)); +} + +inline void MFProcedureBuilder::add_output_parameter(MFVariable &variable) +{ + this->add_parameter(MFParamType::Output, variable); +} + +inline void MFProcedureBuilder::link_to_cursors(MFInstruction *instruction) +{ + for (MFInstructionCursor &cursor : cursors_) { + cursor.insert(*procedure_, instruction); + } +} + +} // namespace blender::fn diff --git a/source/blender/functions/FN_multi_function_procedure_executor.hh b/source/blender/functions/FN_multi_function_procedure_executor.hh new file mode 100644 index 00000000000..9c8b59739b8 --- /dev/null +++ b/source/blender/functions/FN_multi_function_procedure_executor.hh @@ -0,0 +1,39 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup fn + */ + +#include "FN_multi_function_procedure.hh" + +namespace blender::fn { + +/** A multi-function that executes a procedure internally. */ +class MFProcedureExecutor : public MultiFunction { + private: + MFSignature signature_; + const MFProcedure &procedure_; + + public: + MFProcedureExecutor(std::string name, const MFProcedure &procedure); + + void call(IndexMask mask, MFParams params, MFContext context) const override; +}; + +} // namespace blender::fn diff --git a/source/blender/functions/intern/cpp_types.cc b/source/blender/functions/intern/cpp_types.cc index 7be34d2a1bf..058fb76af2b 100644 --- a/source/blender/functions/intern/cpp_types.cc +++ b/source/blender/functions/intern/cpp_types.cc @@ -15,6 +15,7 @@ */ #include "FN_cpp_type_make.hh" +#include "FN_field_cpp_type.hh" #include "BLI_color.hh" #include "BLI_float2.hh" @@ -39,4 +40,12 @@ MAKE_CPP_TYPE(ColorGeometry4b, blender::ColorGeometry4b, CPPTypeFlags::BasicType MAKE_CPP_TYPE(string, std::string, CPPTypeFlags::BasicType) +MAKE_FIELD_CPP_TYPE(FloatField, float); +MAKE_FIELD_CPP_TYPE(Float2Field, float2); +MAKE_FIELD_CPP_TYPE(Float3Field, float3); +MAKE_FIELD_CPP_TYPE(ColorGeometry4fField, blender::ColorGeometry4f); +MAKE_FIELD_CPP_TYPE(BoolField, bool); +MAKE_FIELD_CPP_TYPE(Int32Field, int32_t); +MAKE_FIELD_CPP_TYPE(StringField, std::string); + } // namespace blender::fn diff --git a/source/blender/functions/intern/field.cc b/source/blender/functions/intern/field.cc new file mode 100644 index 00000000000..fa7dea97b7f --- /dev/null +++ b/source/blender/functions/intern/field.cc @@ -0,0 +1,569 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "BLI_map.hh" +#include "BLI_multi_value_map.hh" +#include "BLI_set.hh" +#include "BLI_stack.hh" +#include "BLI_vector_set.hh" + +#include "FN_field.hh" + +namespace blender::fn { + +/* -------------------------------------------------------------------- + * Field Evaluation. + */ + +struct FieldTreeInfo { + /** + * When fields are built, they only have references to the fields that they depend on. This map + * allows traversal of fields in the opposite direction. So for every field it stores the other + * fields that depend on it directly. + */ + MultiValueMap<GFieldRef, GFieldRef> field_users; + /** + * The same field input may exist in the field tree as as separate nodes due to the way + * the tree is constructed. This set contains every different input only once. + */ + VectorSet<std::reference_wrapper<const FieldInput>> deduplicated_field_inputs; +}; + +/** + * Collects some information from the field tree that is required by later steps. + */ +static FieldTreeInfo preprocess_field_tree(Span<GFieldRef> entry_fields) +{ + FieldTreeInfo field_tree_info; + + Stack<GFieldRef> fields_to_check; + Set<GFieldRef> handled_fields; + + for (GFieldRef field : entry_fields) { + if (handled_fields.add(field)) { + fields_to_check.push(field); + } + } + + while (!fields_to_check.is_empty()) { + GFieldRef field = fields_to_check.pop(); + if (field.node().is_input()) { + const FieldInput &field_input = static_cast<const FieldInput &>(field.node()); + field_tree_info.deduplicated_field_inputs.add(field_input); + continue; + } + BLI_assert(field.node().is_operation()); + const FieldOperation &operation = static_cast<const FieldOperation &>(field.node()); + for (const GFieldRef operation_input : operation.inputs()) { + field_tree_info.field_users.add(operation_input, field); + if (handled_fields.add(operation_input)) { + fields_to_check.push(operation_input); + } + } + } + return field_tree_info; +} + +/** + * Retrieves the data from the context that is passed as input into the field. + */ +static Vector<const GVArray *> get_field_context_inputs( + ResourceScope &scope, + const IndexMask mask, + const FieldContext &context, + const Span<std::reference_wrapper<const FieldInput>> field_inputs) +{ + Vector<const GVArray *> field_context_inputs; + for (const FieldInput &field_input : field_inputs) { + const GVArray *varray = context.get_varray_for_input(field_input, mask, scope); + if (varray == nullptr) { + const CPPType &type = field_input.cpp_type(); + varray = &scope.construct<GVArray_For_SingleValueRef>( + __func__, type, mask.min_array_size(), type.default_value()); + } + field_context_inputs.append(varray); + } + return field_context_inputs; +} + +/** + * \return A set that contains all fields from the field tree that depend on an input that varies + * for different indices. + */ +static Set<GFieldRef> find_varying_fields(const FieldTreeInfo &field_tree_info, + Span<const GVArray *> field_context_inputs) +{ + Set<GFieldRef> found_fields; + Stack<GFieldRef> fields_to_check; + + /* The varying fields are the ones that depend on inputs that are not constant. Therefore we + * start the tree search at the non-constant input fields and traverse through all fields that + * depend on them. */ + for (const int i : field_context_inputs.index_range()) { + const GVArray *varray = field_context_inputs[i]; + if (varray->is_single()) { + continue; + } + const FieldInput &field_input = field_tree_info.deduplicated_field_inputs[i]; + const GFieldRef field_input_field{field_input, 0}; + const Span<GFieldRef> users = field_tree_info.field_users.lookup(field_input_field); + for (const GFieldRef &field : users) { + if (found_fields.add(field)) { + fields_to_check.push(field); + } + } + } + while (!fields_to_check.is_empty()) { + GFieldRef field = fields_to_check.pop(); + const Span<GFieldRef> users = field_tree_info.field_users.lookup(field); + for (GFieldRef field : users) { + if (found_fields.add(field)) { + fields_to_check.push(field); + } + } + } + return found_fields; +} + +/** + * Builds the #procedure so that it computes the the fields. + */ +static void build_multi_function_procedure_for_fields(MFProcedure &procedure, + ResourceScope &scope, + const FieldTreeInfo &field_tree_info, + Span<GFieldRef> output_fields) +{ + MFProcedureBuilder builder{procedure}; + /* Every input, intermediate and output field corresponds to a variable in the procedure. */ + Map<GFieldRef, MFVariable *> variable_by_field; + + /* Start by adding the field inputs as parameters to the procedure. */ + for (const FieldInput &field_input : field_tree_info.deduplicated_field_inputs) { + MFVariable &variable = builder.add_input_parameter( + MFDataType::ForSingle(field_input.cpp_type()), field_input.debug_name()); + variable_by_field.add_new({field_input, 0}, &variable); + } + + /* Utility struct that is used to do proper depth first search traversal of the tree below. */ + struct FieldWithIndex { + GFieldRef field; + int current_input_index = 0; + }; + + for (GFieldRef field : output_fields) { + /* We start a new stack for each output field to make sure that a field pushed later to the + * stack does never depend on a field that was pushed before. */ + Stack<FieldWithIndex> fields_to_check; + fields_to_check.push({field, 0}); + while (!fields_to_check.is_empty()) { + FieldWithIndex &field_with_index = fields_to_check.peek(); + const GFieldRef &field = field_with_index.field; + if (variable_by_field.contains(field)) { + /* The field has been handled already. */ + fields_to_check.pop(); + continue; + } + /* Field inputs should already be handled above. */ + BLI_assert(field.node().is_operation()); + + const FieldOperation &operation = static_cast<const FieldOperation &>(field.node()); + const Span<GField> operation_inputs = operation.inputs(); + + if (field_with_index.current_input_index < operation_inputs.size()) { + /* Not all inputs are handled yet. Push the next input field to the stack and increment the + * input index. */ + fields_to_check.push({operation_inputs[field_with_index.current_input_index]}); + field_with_index.current_input_index++; + } + else { + /* All inputs variables are ready, now add the function call. */ + Vector<MFVariable *> input_variables; + for (const GField &field : operation_inputs) { + input_variables.append(variable_by_field.lookup(field)); + } + const MultiFunction &multi_function = operation.multi_function(); + Vector<MFVariable *> output_variables = builder.add_call(multi_function, input_variables); + /* Add newly created variables to the map. */ + for (const int i : output_variables.index_range()) { + variable_by_field.add_new({operation, i}, output_variables[i]); + } + } + } + } + + /* Add output parameters to the procedure. */ + Set<MFVariable *> already_output_variables; + for (const GFieldRef &field : output_fields) { + MFVariable *variable = variable_by_field.lookup(field); + if (!already_output_variables.add(variable)) { + /* One variable can be output at most once. To output the same value twice, we have to make + * a copy first. */ + const MultiFunction ©_fn = scope.construct<CustomMF_GenericCopy>( + __func__, "copy", variable->data_type()); + variable = builder.add_call<1>(copy_fn, {variable})[0]; + } + builder.add_output_parameter(*variable); + } + + /* Remove the variables that should not be destructed from the map. */ + for (const GFieldRef &field : output_fields) { + variable_by_field.remove(field); + } + /* Add destructor calls for the remaining variables. */ + for (MFVariable *variable : variable_by_field.values()) { + builder.add_destruct(*variable); + } + + builder.add_return(); + + // std::cout << procedure.to_dot() << "\n"; + BLI_assert(procedure.validate()); +} + +/** + * Utility class that destructs elements from a partially initialized array. + */ +struct PartiallyInitializedArray : NonCopyable, NonMovable { + void *buffer; + IndexMask mask; + const CPPType *type; + + ~PartiallyInitializedArray() + { + this->type->destruct_indices(this->buffer, this->mask); + } +}; + +/** + * Evaluate fields in the given context. If possible, multiple fields should be evaluated together, + * because that can be more efficient when they share common sub-fields. + * + * \param scope: The resource scope that owns data that makes up the output virtual arrays. Make + * sure the scope is not destructed when the output virtual arrays are still used. + * \param fields_to_evaluate: The fields that should be evaluated together. + * \param mask: Determines which indices are computed. The mask may be referenced by the returned + * virtual arrays. So the underlying indices (if applicable) should live longer then #scope. + * \param context: The context that the field is evaluated in. Used to retrieve data from each + * #FieldInput in the field network. + * \param dst_varrays: If provided, the computed data will be written into those virtual arrays + * instead of into newly created ones. That allows making the computed data live longer than + * #scope and is more efficient when the data will be written into those virtual arrays + * later anyway. + * \return The computed virtual arrays for each provided field. If #dst_varrays is passed, the + * provided virtual arrays are returned. + */ +Vector<const GVArray *> evaluate_fields(ResourceScope &scope, + Span<GFieldRef> fields_to_evaluate, + IndexMask mask, + const FieldContext &context, + Span<GVMutableArray *> dst_varrays) +{ + Vector<const GVArray *> r_varrays(fields_to_evaluate.size(), nullptr); + const int array_size = mask.min_array_size(); + + /* Destination arrays are optional. Create a small utility method to access them. */ + auto get_dst_varray_if_available = [&](int index) -> GVMutableArray * { + if (dst_varrays.is_empty()) { + return nullptr; + } + BLI_assert(dst_varrays[index] == nullptr || dst_varrays[index]->size() >= array_size); + return dst_varrays[index]; + }; + + /* Traverse the field tree and prepare some data that is used in later steps. */ + FieldTreeInfo field_tree_info = preprocess_field_tree(fields_to_evaluate); + + /* Get inputs that will be passed into the field when evaluated. */ + Vector<const GVArray *> field_context_inputs = get_field_context_inputs( + scope, mask, context, field_tree_info.deduplicated_field_inputs); + + /* Finish fields that output an input varray directly. For those we don't have to do any further + * processing. */ + for (const int out_index : fields_to_evaluate.index_range()) { + const GFieldRef &field = fields_to_evaluate[out_index]; + if (!field.node().is_input()) { + continue; + } + const FieldInput &field_input = static_cast<const FieldInput &>(field.node()); + const int field_input_index = field_tree_info.deduplicated_field_inputs.index_of(field_input); + const GVArray *varray = field_context_inputs[field_input_index]; + r_varrays[out_index] = varray; + } + + Set<GFieldRef> varying_fields = find_varying_fields(field_tree_info, field_context_inputs); + + /* Separate fields into two categories. Those that are constant and need to be evaluated only + * once, and those that need to be evaluated for every index. */ + Vector<GFieldRef> varying_fields_to_evaluate; + Vector<int> varying_field_indices; + Vector<GFieldRef> constant_fields_to_evaluate; + Vector<int> constant_field_indices; + for (const int i : fields_to_evaluate.index_range()) { + if (r_varrays[i] != nullptr) { + /* Already done. */ + continue; + } + GFieldRef field = fields_to_evaluate[i]; + if (varying_fields.contains(field)) { + varying_fields_to_evaluate.append(field); + varying_field_indices.append(i); + } + else { + constant_fields_to_evaluate.append(field); + constant_field_indices.append(i); + } + } + + /* Evaluate varying fields if necessary. */ + if (!varying_fields_to_evaluate.is_empty()) { + /* Build the procedure for those fields. */ + MFProcedure procedure; + build_multi_function_procedure_for_fields( + procedure, scope, field_tree_info, varying_fields_to_evaluate); + MFProcedureExecutor procedure_executor{"Procedure", procedure}; + MFParamsBuilder mf_params{procedure_executor, array_size}; + MFContextBuilder mf_context; + + /* Provide inputs to the procedure executor. */ + for (const GVArray *varray : field_context_inputs) { + mf_params.add_readonly_single_input(*varray); + } + + for (const int i : varying_fields_to_evaluate.index_range()) { + const GFieldRef &field = varying_fields_to_evaluate[i]; + const CPPType &type = field.cpp_type(); + const int out_index = varying_field_indices[i]; + + /* Try to get an existing virtual array that the result should be written into. */ + GVMutableArray *output_varray = get_dst_varray_if_available(out_index); + void *buffer; + if (output_varray == nullptr || !output_varray->is_span()) { + /* Allocate a new buffer for the computed result. */ + buffer = scope.linear_allocator().allocate(type.size() * array_size, type.alignment()); + + /* Make sure that elements in the buffer will be destructed. */ + PartiallyInitializedArray &destruct_helper = scope.construct<PartiallyInitializedArray>( + __func__); + destruct_helper.buffer = buffer; + destruct_helper.mask = mask; + destruct_helper.type = &type; + + r_varrays[out_index] = &scope.construct<GVArray_For_GSpan>( + __func__, GSpan{type, buffer, array_size}); + } + else { + /* Write the result into the existing span. */ + buffer = output_varray->get_internal_span().data(); + + r_varrays[out_index] = output_varray; + } + + /* Pass output buffer to the procedure executor. */ + const GMutableSpan span{type, buffer, array_size}; + mf_params.add_uninitialized_single_output(span); + } + + procedure_executor.call(mask, mf_params, mf_context); + } + + /* Evaluate constant fields if necessary. */ + if (!constant_fields_to_evaluate.is_empty()) { + /* Build the procedure for those fields. */ + MFProcedure procedure; + build_multi_function_procedure_for_fields( + procedure, scope, field_tree_info, constant_fields_to_evaluate); + MFProcedureExecutor procedure_executor{"Procedure", procedure}; + MFParamsBuilder mf_params{procedure_executor, 1}; + MFContextBuilder mf_context; + + /* Provide inputs to the procedure executor. */ + for (const GVArray *varray : field_context_inputs) { + mf_params.add_readonly_single_input(*varray); + } + + for (const int i : constant_fields_to_evaluate.index_range()) { + const GFieldRef &field = constant_fields_to_evaluate[i]; + const CPPType &type = field.cpp_type(); + /* Allocate memory where the computed value will be stored in. */ + void *buffer = scope.linear_allocator().allocate(type.size(), type.alignment()); + + /* Use this to make sure that the value is destructed in the end. */ + PartiallyInitializedArray &destruct_helper = scope.construct<PartiallyInitializedArray>( + __func__); + destruct_helper.buffer = buffer; + destruct_helper.mask = IndexRange(1); + destruct_helper.type = &type; + + /* Pass output buffer to the procedure executor. */ + mf_params.add_uninitialized_single_output({type, buffer, 1}); + + /* Create virtual array that can be used after the procedure has been executed below. */ + const int out_index = constant_field_indices[i]; + r_varrays[out_index] = &scope.construct<GVArray_For_SingleValueRef>( + __func__, type, array_size, buffer); + } + + procedure_executor.call(IndexRange(1), mf_params, mf_context); + } + + /* Copy data to supplied destination arrays if necessary. In some cases the evaluation above has + * written the computed data in the right place already. */ + if (!dst_varrays.is_empty()) { + for (const int out_index : fields_to_evaluate.index_range()) { + GVMutableArray *output_varray = get_dst_varray_if_available(out_index); + if (output_varray == nullptr) { + /* Caller did not provide a destination for this output. */ + continue; + } + const GVArray *computed_varray = r_varrays[out_index]; + BLI_assert(computed_varray->type() == output_varray->type()); + if (output_varray == computed_varray) { + /* The result has been written into the destination provided by the caller already. */ + continue; + } + /* Still have to copy over the data in the destination provided by the caller. */ + if (output_varray->is_span()) { + /* Materialize into a span. */ + computed_varray->materialize_to_uninitialized(output_varray->get_internal_span().data()); + } + else { + /* Slower materialize into a different structure. */ + const CPPType &type = computed_varray->type(); + BUFFER_FOR_CPP_TYPE_VALUE(type, buffer); + for (const int i : mask) { + computed_varray->get_to_uninitialized(i, buffer); + output_varray->set_by_relocate(i, buffer); + } + } + r_varrays[out_index] = output_varray; + } + } + return r_varrays; +} + +void evaluate_constant_field(const GField &field, void *r_value) +{ + ResourceScope scope; + FieldContext context; + Vector<const GVArray *> varrays = evaluate_fields(scope, {field}, IndexRange(1), context); + varrays[0]->get_to_uninitialized(0, r_value); +} + +const GVArray *FieldContext::get_varray_for_input(const FieldInput &field_input, + IndexMask mask, + ResourceScope &scope) const +{ + /* By default ask the field input to create the varray. Another field context might overwrite + * the context here. */ + return field_input.get_varray_for_context(*this, mask, scope); +} + +/* -------------------------------------------------------------------- + * FieldEvaluator. + */ + +static Vector<int64_t> indices_from_selection(const VArray<bool> &selection) +{ + /* If the selection is just a single value, it's best to avoid calling this + * function when constructing an IndexMask and use an IndexRange instead. */ + BLI_assert(!selection.is_single()); + + Vector<int64_t> indices; + if (selection.is_span()) { + Span<bool> span = selection.get_internal_span(); + for (const int64_t i : span.index_range()) { + if (span[i]) { + indices.append(i); + } + } + } + else { + for (const int i : selection.index_range()) { + if (selection[i]) { + indices.append(i); + } + } + } + return indices; +} + +int FieldEvaluator::add_with_destination(GField field, GVMutableArray &dst) +{ + const int field_index = fields_to_evaluate_.append_and_get_index(std::move(field)); + dst_varrays_.append(&dst); + output_pointer_infos_.append({}); + return field_index; +} + +int FieldEvaluator::add_with_destination(GField field, GMutableSpan dst) +{ + GVMutableArray &varray = scope_.construct<GVMutableArray_For_GMutableSpan>(__func__, dst); + return this->add_with_destination(std::move(field), varray); +} + +int FieldEvaluator::add(GField field, const GVArray **varray_ptr) +{ + const int field_index = fields_to_evaluate_.append_and_get_index(std::move(field)); + dst_varrays_.append(nullptr); + output_pointer_infos_.append(OutputPointerInfo{ + varray_ptr, [](void *dst, const GVArray &varray, ResourceScope &UNUSED(scope)) { + *(const GVArray **)dst = &varray; + }}); + return field_index; +} + +int FieldEvaluator::add(GField field) +{ + const int field_index = fields_to_evaluate_.append_and_get_index(std::move(field)); + dst_varrays_.append(nullptr); + output_pointer_infos_.append({}); + return field_index; +} + +void FieldEvaluator::evaluate() +{ + BLI_assert_msg(!is_evaluated_, "Cannot evaluate fields twice."); + Array<GFieldRef> fields(fields_to_evaluate_.size()); + for (const int i : fields_to_evaluate_.index_range()) { + fields[i] = fields_to_evaluate_[i]; + } + evaluated_varrays_ = evaluate_fields(scope_, fields, mask_, context_, dst_varrays_); + BLI_assert(fields_to_evaluate_.size() == evaluated_varrays_.size()); + for (const int i : fields_to_evaluate_.index_range()) { + OutputPointerInfo &info = output_pointer_infos_[i]; + if (info.dst != nullptr) { + info.set(info.dst, *evaluated_varrays_[i], scope_); + } + } + is_evaluated_ = true; +} + +IndexMask FieldEvaluator::get_evaluated_as_mask(const int field_index) +{ + const GVArray &varray = this->get_evaluated(field_index); + GVArray_Typed<bool> typed_varray{varray}; + + if (typed_varray->is_single()) { + if (typed_varray->get_internal_single()) { + return IndexRange(typed_varray.size()); + } + return IndexRange(0); + } + + return scope_.add_value(indices_from_selection(*typed_varray), __func__).as_span(); +} + +} // namespace blender::fn diff --git a/source/blender/functions/intern/multi_function_builder.cc b/source/blender/functions/intern/multi_function_builder.cc index c6b3b808130..180d1f17a54 100644 --- a/source/blender/functions/intern/multi_function_builder.cc +++ b/source/blender/functions/intern/multi_function_builder.cc @@ -123,4 +123,32 @@ void CustomMF_DefaultOutput::call(IndexMask mask, MFParams params, MFContext UNU } } +CustomMF_GenericCopy::CustomMF_GenericCopy(StringRef name, MFDataType data_type) +{ + MFSignatureBuilder signature{name}; + signature.input("Input", data_type); + signature.output("Output", data_type); + signature_ = signature.build(); + this->set_signature(&signature_); +} + +void CustomMF_GenericCopy::call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const +{ + const MFDataType data_type = this->param_type(0).data_type(); + switch (data_type.category()) { + case MFDataType::Single: { + const GVArray &inputs = params.readonly_single_input(0, "Input"); + GMutableSpan outputs = params.uninitialized_single_output(1, "Output"); + inputs.materialize_to_uninitialized(mask, outputs.data()); + break; + } + case MFDataType::Vector: { + const GVVectorArray &inputs = params.readonly_vector_input(0, "Input"); + GVectorArray &outputs = params.vector_output(1, "Output"); + outputs.extend(mask, inputs); + break; + } + } +} + } // namespace blender::fn diff --git a/source/blender/functions/intern/multi_function_procedure.cc b/source/blender/functions/intern/multi_function_procedure.cc new file mode 100644 index 00000000000..6eff7bc09f8 --- /dev/null +++ b/source/blender/functions/intern/multi_function_procedure.cc @@ -0,0 +1,794 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "FN_multi_function_procedure.hh" + +#include "BLI_dot_export.hh" +#include "BLI_stack.hh" + +namespace blender::fn { + +void MFVariable::set_name(std::string name) +{ + name_ = std::move(name); +} + +void MFCallInstruction::set_next(MFInstruction *instruction) +{ + if (next_ != nullptr) { + next_->prev_.remove_first_occurrence_and_reorder(this); + } + if (instruction != nullptr) { + instruction->prev_.append(this); + } + next_ = instruction; +} + +void MFCallInstruction::set_param_variable(int param_index, MFVariable *variable) +{ + if (params_[param_index] != nullptr) { + params_[param_index]->users_.remove_first_occurrence_and_reorder(this); + } + if (variable != nullptr) { + BLI_assert(fn_->param_type(param_index).data_type() == variable->data_type()); + variable->users_.append(this); + } + params_[param_index] = variable; +} + +void MFCallInstruction::set_params(Span<MFVariable *> variables) +{ + BLI_assert(variables.size() == params_.size()); + for (const int i : variables.index_range()) { + this->set_param_variable(i, variables[i]); + } +} + +void MFBranchInstruction::set_condition(MFVariable *variable) +{ + if (condition_ != nullptr) { + condition_->users_.remove_first_occurrence_and_reorder(this); + } + if (variable != nullptr) { + variable->users_.append(this); + } + condition_ = variable; +} + +void MFBranchInstruction::set_branch_true(MFInstruction *instruction) +{ + if (branch_true_ != nullptr) { + branch_true_->prev_.remove_first_occurrence_and_reorder(this); + } + if (instruction != nullptr) { + instruction->prev_.append(this); + } + branch_true_ = instruction; +} + +void MFBranchInstruction::set_branch_false(MFInstruction *instruction) +{ + if (branch_false_ != nullptr) { + branch_false_->prev_.remove_first_occurrence_and_reorder(this); + } + if (instruction != nullptr) { + instruction->prev_.append(this); + } + branch_false_ = instruction; +} + +void MFDestructInstruction::set_variable(MFVariable *variable) +{ + if (variable_ != nullptr) { + variable_->users_.remove_first_occurrence_and_reorder(this); + } + if (variable != nullptr) { + variable->users_.append(this); + } + variable_ = variable; +} + +void MFDestructInstruction::set_next(MFInstruction *instruction) +{ + if (next_ != nullptr) { + next_->prev_.remove_first_occurrence_and_reorder(this); + } + if (instruction != nullptr) { + instruction->prev_.append(this); + } + next_ = instruction; +} + +void MFDummyInstruction::set_next(MFInstruction *instruction) +{ + if (next_ != nullptr) { + next_->prev_.remove_first_occurrence_and_reorder(this); + } + if (instruction != nullptr) { + instruction->prev_.append(this); + } + next_ = instruction; +} + +MFVariable &MFProcedure::new_variable(MFDataType data_type, std::string name) +{ + MFVariable &variable = *allocator_.construct<MFVariable>().release(); + variable.name_ = std::move(name); + variable.data_type_ = data_type; + variable.id_ = variables_.size(); + variables_.append(&variable); + return variable; +} + +MFCallInstruction &MFProcedure::new_call_instruction(const MultiFunction &fn) +{ + MFCallInstruction &instruction = *allocator_.construct<MFCallInstruction>().release(); + instruction.type_ = MFInstructionType::Call; + instruction.fn_ = &fn; + instruction.params_ = allocator_.allocate_array<MFVariable *>(fn.param_amount()); + instruction.params_.fill(nullptr); + call_instructions_.append(&instruction); + return instruction; +} + +MFBranchInstruction &MFProcedure::new_branch_instruction() +{ + MFBranchInstruction &instruction = *allocator_.construct<MFBranchInstruction>().release(); + instruction.type_ = MFInstructionType::Branch; + branch_instructions_.append(&instruction); + return instruction; +} + +MFDestructInstruction &MFProcedure::new_destruct_instruction() +{ + MFDestructInstruction &instruction = *allocator_.construct<MFDestructInstruction>().release(); + instruction.type_ = MFInstructionType::Destruct; + destruct_instructions_.append(&instruction); + return instruction; +} + +MFDummyInstruction &MFProcedure::new_dummy_instruction() +{ + MFDummyInstruction &instruction = *allocator_.construct<MFDummyInstruction>().release(); + instruction.type_ = MFInstructionType::Dummy; + dummy_instructions_.append(&instruction); + return instruction; +} + +MFReturnInstruction &MFProcedure::new_return_instruction() +{ + MFReturnInstruction &instruction = *allocator_.construct<MFReturnInstruction>().release(); + instruction.type_ = MFInstructionType::Return; + return_instructions_.append(&instruction); + return instruction; +} + +void MFProcedure::add_parameter(MFParamType::InterfaceType interface_type, MFVariable &variable) +{ + params_.append({interface_type, &variable}); +} + +void MFProcedure::set_entry(MFInstruction &entry) +{ + entry_ = &entry; +} + +MFProcedure::~MFProcedure() +{ + for (MFCallInstruction *instruction : call_instructions_) { + instruction->~MFCallInstruction(); + } + for (MFBranchInstruction *instruction : branch_instructions_) { + instruction->~MFBranchInstruction(); + } + for (MFDestructInstruction *instruction : destruct_instructions_) { + instruction->~MFDestructInstruction(); + } + for (MFDummyInstruction *instruction : dummy_instructions_) { + instruction->~MFDummyInstruction(); + } + for (MFReturnInstruction *instruction : return_instructions_) { + instruction->~MFReturnInstruction(); + } + for (MFVariable *variable : variables_) { + variable->~MFVariable(); + } +} + +bool MFProcedure::validate() const +{ + if (entry_ == nullptr) { + return false; + } + if (!this->validate_all_instruction_pointers_set()) { + return false; + } + if (!this->validate_all_params_provided()) { + return false; + } + if (!this->validate_same_variables_in_one_call()) { + return false; + } + if (!this->validate_parameters()) { + return false; + } + if (!this->validate_initialization()) { + return false; + } + return true; +} + +bool MFProcedure::validate_all_instruction_pointers_set() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + for (const MFDestructInstruction *instruction : destruct_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + if (instruction->branch_true_ == nullptr) { + return false; + } + if (instruction->branch_false_ == nullptr) { + return false; + } + } + for (const MFDummyInstruction *instruction : dummy_instructions_) { + if (instruction->next_ == nullptr) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_all_params_provided() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + for (const MFVariable *variable : instruction->params_) { + if (variable == nullptr) { + return false; + } + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + if (instruction->condition_ == nullptr) { + return false; + } + } + for (const MFDestructInstruction *instruction : destruct_instructions_) { + if (instruction->variable_ == nullptr) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_same_variables_in_one_call() const +{ + for (const MFCallInstruction *instruction : call_instructions_) { + const MultiFunction &fn = *instruction->fn_; + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + const MFVariable *variable = instruction->params_[param_index]; + for (const int other_param_index : fn.param_indices()) { + if (other_param_index == param_index) { + continue; + } + const MFVariable *other_variable = instruction->params_[other_param_index]; + if (other_variable != variable) { + continue; + } + if (ELEM(param_type.interface_type(), MFParamType::Mutable, MFParamType::Output)) { + /* When a variable is used as mutable or output parameter, it can only be used once. */ + return false; + } + const MFParamType other_param_type = fn.param_type(other_param_index); + /* A variable is allowed to be used as input more than once. */ + if (other_param_type.interface_type() != MFParamType::Input) { + return false; + } + } + } + } + return true; +} + +bool MFProcedure::validate_parameters() const +{ + Set<const MFVariable *> variables; + for (const MFParameter ¶m : params_) { + /* One variable cannot be used as multiple parameters. */ + if (!variables.add(param.variable)) { + return false; + } + } + return true; +} + +bool MFProcedure::validate_initialization() const +{ + /* TODO: Issue warning when it maybe wrongly initialized. */ + for (const MFDestructInstruction *instruction : destruct_instructions_) { + const MFVariable &variable = *instruction->variable_; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + if (!state.can_be_initialized) { + return false; + } + } + for (const MFBranchInstruction *instruction : branch_instructions_) { + const MFVariable &variable = *instruction->condition_; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + if (!state.can_be_initialized) { + return false; + } + } + for (const MFCallInstruction *instruction : call_instructions_) { + const MultiFunction &fn = *instruction->fn_; + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + const MFVariable &variable = *instruction->params_[param_index]; + const InitState state = this->find_initialization_state_before_instruction(*instruction, + variable); + switch (param_type.interface_type()) { + case MFParamType::Input: + case MFParamType::Mutable: { + if (!state.can_be_initialized) { + return false; + } + break; + } + case MFParamType::Output: { + if (!state.can_be_uninitialized) { + return false; + } + break; + } + } + } + } + Set<const MFVariable *> variables_that_should_be_initialized_on_return; + for (const MFParameter ¶m : params_) { + if (ELEM(param.type, MFParamType::Mutable, MFParamType::Output)) { + variables_that_should_be_initialized_on_return.add_new(param.variable); + } + } + for (const MFReturnInstruction *instruction : return_instructions_) { + for (const MFVariable *variable : variables_) { + const InitState init_state = this->find_initialization_state_before_instruction(*instruction, + *variable); + if (variables_that_should_be_initialized_on_return.contains(variable)) { + if (!init_state.can_be_initialized) { + return false; + } + } + else { + if (!init_state.can_be_uninitialized) { + return false; + } + } + } + } + return true; +} + +MFProcedure::InitState MFProcedure::find_initialization_state_before_instruction( + const MFInstruction &target_instruction, const MFVariable &target_variable) const +{ + InitState state; + + auto check_entry_instruction = [&]() { + bool caller_initialized_variable = false; + for (const MFParameter ¶m : params_) { + if (param.variable == &target_variable) { + if (ELEM(param.type, MFParamType::Input, MFParamType::Mutable)) { + caller_initialized_variable = true; + break; + } + } + } + if (caller_initialized_variable) { + state.can_be_initialized = true; + } + else { + state.can_be_uninitialized = true; + } + }; + + if (&target_instruction == entry_) { + check_entry_instruction(); + } + + Set<const MFInstruction *> checked_instructions; + Stack<const MFInstruction *> instructions_to_check; + instructions_to_check.push_multiple(target_instruction.prev_); + + while (!instructions_to_check.is_empty()) { + const MFInstruction &instruction = *instructions_to_check.pop(); + if (!checked_instructions.add(&instruction)) { + /* Skip if the instruction has been checked already. */ + continue; + } + bool state_modified = false; + switch (instruction.type_) { + case MFInstructionType::Call: { + const MFCallInstruction &call_instruction = static_cast<const MFCallInstruction &>( + instruction); + const MultiFunction &fn = *call_instruction.fn_; + for (const int param_index : fn.param_indices()) { + if (call_instruction.params_[param_index] == &target_variable) { + const MFParamType param_type = fn.param_type(param_index); + if (param_type.interface_type() == MFParamType::Output) { + state.can_be_initialized = true; + state_modified = true; + break; + } + } + } + break; + } + case MFInstructionType::Destruct: { + const MFDestructInstruction &destruct_instruction = + static_cast<const MFDestructInstruction &>(instruction); + if (destruct_instruction.variable_ == &target_variable) { + state.can_be_uninitialized = true; + state_modified = true; + } + break; + } + case MFInstructionType::Branch: + case MFInstructionType::Dummy: + case MFInstructionType::Return: { + /* These instruction types don't change the initialization state of variables. */ + break; + } + } + + if (!state_modified) { + if (&instruction == entry_) { + check_entry_instruction(); + } + instructions_to_check.push_multiple(instruction.prev_); + } + } + + return state; +} + +class MFProcedureDotExport { + private: + const MFProcedure &procedure_; + dot::DirectedGraph digraph_; + Map<const MFInstruction *, dot::Node *> dot_nodes_by_begin_; + Map<const MFInstruction *, dot::Node *> dot_nodes_by_end_; + + public: + MFProcedureDotExport(const MFProcedure &procedure) : procedure_(procedure) + { + } + + std::string generate() + { + this->create_nodes(); + this->create_edges(); + return digraph_.to_dot_string(); + } + + void create_nodes() + { + Vector<const MFInstruction *> all_instructions; + auto add_instructions = [&](auto instructions) { + all_instructions.extend(instructions.begin(), instructions.end()); + }; + add_instructions(procedure_.call_instructions_); + add_instructions(procedure_.branch_instructions_); + add_instructions(procedure_.destruct_instructions_); + add_instructions(procedure_.dummy_instructions_); + add_instructions(procedure_.return_instructions_); + + Set<const MFInstruction *> handled_instructions; + + for (const MFInstruction *representative : all_instructions) { + if (handled_instructions.contains(representative)) { + continue; + } + Vector<const MFInstruction *> block_instructions = this->get_instructions_in_block( + *representative); + std::stringstream ss; + ss << "<"; + + for (const MFInstruction *current : block_instructions) { + handled_instructions.add_new(current); + switch (current->type()) { + case MFInstructionType::Call: { + this->instruction_to_string(*static_cast<const MFCallInstruction *>(current), ss); + break; + } + case MFInstructionType::Destruct: { + this->instruction_to_string(*static_cast<const MFDestructInstruction *>(current), ss); + break; + } + case MFInstructionType::Dummy: { + this->instruction_to_string(*static_cast<const MFDummyInstruction *>(current), ss); + break; + } + case MFInstructionType::Return: { + this->instruction_to_string(*static_cast<const MFReturnInstruction *>(current), ss); + break; + } + case MFInstructionType::Branch: { + this->instruction_to_string(*static_cast<const MFBranchInstruction *>(current), ss); + break; + } + } + ss << R"(<br align="left" />)"; + } + ss << ">"; + + dot::Node &dot_node = digraph_.new_node(ss.str()); + dot_node.set_shape(dot::Attr_shape::Rectangle); + dot_nodes_by_begin_.add_new(block_instructions.first(), &dot_node); + dot_nodes_by_end_.add_new(block_instructions.last(), &dot_node); + } + } + + void create_edges() + { + auto create_edge = [&](dot::Node &from_node, + const MFInstruction *to_instruction) -> dot::DirectedEdge & { + if (to_instruction == nullptr) { + dot::Node &to_node = digraph_.new_node("missing"); + to_node.set_shape(dot::Attr_shape::Diamond); + return digraph_.new_edge(from_node, to_node); + } + dot::Node &to_node = *dot_nodes_by_begin_.lookup(to_instruction); + return digraph_.new_edge(from_node, to_node); + }; + + for (auto item : dot_nodes_by_end_.items()) { + const MFInstruction &from_instruction = *item.key; + dot::Node &from_node = *item.value; + switch (from_instruction.type()) { + case MFInstructionType::Call: { + const MFInstruction *to_instruction = + static_cast<const MFCallInstruction &>(from_instruction).next(); + create_edge(from_node, to_instruction); + break; + } + case MFInstructionType::Destruct: { + const MFInstruction *to_instruction = + static_cast<const MFDestructInstruction &>(from_instruction).next(); + create_edge(from_node, to_instruction); + break; + } + case MFInstructionType::Dummy: { + const MFInstruction *to_instruction = + static_cast<const MFDummyInstruction &>(from_instruction).next(); + create_edge(from_node, to_instruction); + break; + } + case MFInstructionType::Return: { + break; + } + case MFInstructionType::Branch: { + const MFBranchInstruction &branch_instruction = static_cast<const MFBranchInstruction &>( + from_instruction); + const MFInstruction *to_true_instruction = branch_instruction.branch_true(); + const MFInstruction *to_false_instruction = branch_instruction.branch_false(); + create_edge(from_node, to_true_instruction).attributes.set("color", "#118811"); + create_edge(from_node, to_false_instruction).attributes.set("color", "#881111"); + break; + } + } + } + + dot::Node &entry_node = this->create_entry_node(); + create_edge(entry_node, procedure_.entry()); + } + + bool has_to_be_block_begin(const MFInstruction &instruction) + { + if (procedure_.entry() == &instruction) { + return true; + } + if (instruction.prev().size() != 1) { + return true; + } + if (instruction.prev()[0]->type() == MFInstructionType::Branch) { + return true; + } + return false; + } + + const MFInstruction &get_first_instruction_in_block(const MFInstruction &representative) + { + const MFInstruction *current = &representative; + while (!this->has_to_be_block_begin(*current)) { + current = current->prev()[0]; + if (current == &representative) { + /* There is a loop without entry or exit, just break it up here. */ + break; + } + } + return *current; + } + + const MFInstruction *get_next_instruction_in_block(const MFInstruction &instruction, + const MFInstruction &block_begin) + { + const MFInstruction *next = nullptr; + switch (instruction.type()) { + case MFInstructionType::Call: { + next = static_cast<const MFCallInstruction &>(instruction).next(); + break; + } + case MFInstructionType::Destruct: { + next = static_cast<const MFDestructInstruction &>(instruction).next(); + break; + } + case MFInstructionType::Dummy: { + next = static_cast<const MFDummyInstruction &>(instruction).next(); + break; + } + case MFInstructionType::Return: + case MFInstructionType::Branch: { + break; + } + } + if (next == nullptr) { + return nullptr; + } + if (next == &block_begin) { + return nullptr; + } + if (this->has_to_be_block_begin(*next)) { + return nullptr; + } + return next; + } + + Vector<const MFInstruction *> get_instructions_in_block(const MFInstruction &representative) + { + Vector<const MFInstruction *> instructions; + const MFInstruction &begin = this->get_first_instruction_in_block(representative); + for (const MFInstruction *current = &begin; current != nullptr; + current = this->get_next_instruction_in_block(*current, begin)) { + instructions.append(current); + } + return instructions; + } + + void variable_to_string(const MFVariable *variable, std::stringstream &ss) + { + if (variable == nullptr) { + ss << "null"; + } + else { + ss << "$" << variable->id(); + if (!variable->name().is_empty()) { + ss << "(" << variable->name() << ")"; + } + } + } + + void instruction_name_format(StringRef name, std::stringstream &ss) + { + ss << name; + } + + void instruction_to_string(const MFCallInstruction &instruction, std::stringstream &ss) + { + const MultiFunction &fn = instruction.fn(); + this->instruction_name_format(fn.name() + ": ", ss); + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + const MFVariable *variable = instruction.params()[param_index]; + ss << R"(<font color="grey30">)"; + switch (param_type.interface_type()) { + case MFParamType::Input: { + ss << "in"; + break; + } + case MFParamType::Mutable: { + ss << "mut"; + break; + } + case MFParamType::Output: { + ss << "out"; + break; + } + } + ss << " </font> "; + variable_to_string(variable, ss); + if (param_index < fn.param_amount() - 1) { + ss << ", "; + } + } + } + + void instruction_to_string(const MFDestructInstruction &instruction, std::stringstream &ss) + { + instruction_name_format("Destruct ", ss); + variable_to_string(instruction.variable(), ss); + } + + void instruction_to_string(const MFDummyInstruction &UNUSED(instruction), std::stringstream &ss) + { + instruction_name_format("Dummy ", ss); + } + + void instruction_to_string(const MFReturnInstruction &UNUSED(instruction), std::stringstream &ss) + { + instruction_name_format("Return ", ss); + + Vector<ConstMFParameter> outgoing_parameters; + for (const ConstMFParameter ¶m : procedure_.params()) { + if (ELEM(param.type, MFParamType::Mutable, MFParamType::Output)) { + outgoing_parameters.append(param); + } + } + for (const int param_index : outgoing_parameters.index_range()) { + const ConstMFParameter ¶m = outgoing_parameters[param_index]; + variable_to_string(param.variable, ss); + if (param_index < outgoing_parameters.size() - 1) { + ss << ", "; + } + } + } + + void instruction_to_string(const MFBranchInstruction &instruction, std::stringstream &ss) + { + instruction_name_format("Branch ", ss); + variable_to_string(instruction.condition(), ss); + } + + dot::Node &create_entry_node() + { + std::stringstream ss; + ss << "Entry: "; + Vector<ConstMFParameter> incoming_parameters; + for (const ConstMFParameter ¶m : procedure_.params()) { + if (ELEM(param.type, MFParamType::Input, MFParamType::Mutable)) { + incoming_parameters.append(param); + } + } + for (const int param_index : incoming_parameters.index_range()) { + const ConstMFParameter ¶m = incoming_parameters[param_index]; + variable_to_string(param.variable, ss); + if (param_index < incoming_parameters.size() - 1) { + ss << ", "; + } + } + + dot::Node &node = digraph_.new_node(ss.str()); + node.set_shape(dot::Attr_shape::Ellipse); + return node; + } +}; + +std::string MFProcedure::to_dot() const +{ + MFProcedureDotExport dot_export{*this}; + return dot_export.generate(); +} + +} // namespace blender::fn diff --git a/source/blender/functions/intern/multi_function_procedure_builder.cc b/source/blender/functions/intern/multi_function_procedure_builder.cc new file mode 100644 index 00000000000..3c088776bea --- /dev/null +++ b/source/blender/functions/intern/multi_function_procedure_builder.cc @@ -0,0 +1,175 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "FN_multi_function_procedure_builder.hh" + +namespace blender::fn { + +void MFInstructionCursor::insert(MFProcedure &procedure, MFInstruction *new_instruction) +{ + if (instruction_ == nullptr) { + if (is_entry_) { + procedure.set_entry(*new_instruction); + } + else { + /* The cursors points at nothing, nothing to do. */ + } + } + else { + switch (instruction_->type()) { + case MFInstructionType::Call: { + static_cast<MFCallInstruction *>(instruction_)->set_next(new_instruction); + break; + } + case MFInstructionType::Branch: { + MFBranchInstruction &branch_instruction = *static_cast<MFBranchInstruction *>( + instruction_); + if (branch_output_) { + branch_instruction.set_branch_true(new_instruction); + } + else { + branch_instruction.set_branch_false(new_instruction); + } + break; + } + case MFInstructionType::Destruct: { + static_cast<MFDestructInstruction *>(instruction_)->set_next(new_instruction); + break; + } + case MFInstructionType::Dummy: { + static_cast<MFDummyInstruction *>(instruction_)->set_next(new_instruction); + break; + } + case MFInstructionType::Return: { + /* It shouldn't be possible to build a cursor that points to a return instruction. */ + BLI_assert_unreachable(); + break; + } + } + } +} + +void MFProcedureBuilder::add_destruct(MFVariable &variable) +{ + MFDestructInstruction &instruction = procedure_->new_destruct_instruction(); + instruction.set_variable(&variable); + this->link_to_cursors(&instruction); + cursors_ = {MFInstructionCursor{instruction}}; +} + +void MFProcedureBuilder::add_destruct(Span<MFVariable *> variables) +{ + for (MFVariable *variable : variables) { + this->add_destruct(*variable); + } +} + +MFReturnInstruction &MFProcedureBuilder::add_return() +{ + MFReturnInstruction &instruction = procedure_->new_return_instruction(); + this->link_to_cursors(&instruction); + cursors_ = {}; + return instruction; +} + +MFCallInstruction &MFProcedureBuilder::add_call_with_no_variables(const MultiFunction &fn) +{ + MFCallInstruction &instruction = procedure_->new_call_instruction(fn); + this->link_to_cursors(&instruction); + cursors_ = {MFInstructionCursor{instruction}}; + return instruction; +} + +MFCallInstruction &MFProcedureBuilder::add_call_with_all_variables( + const MultiFunction &fn, Span<MFVariable *> param_variables) +{ + MFCallInstruction &instruction = this->add_call_with_no_variables(fn); + instruction.set_params(param_variables); + return instruction; +} + +Vector<MFVariable *> MFProcedureBuilder::add_call(const MultiFunction &fn, + Span<MFVariable *> input_and_mutable_variables) +{ + Vector<MFVariable *> output_variables; + MFCallInstruction &instruction = this->add_call_with_no_variables(fn); + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + switch (param_type.interface_type()) { + case MFParamType::Input: + case MFParamType::Mutable: { + MFVariable *variable = input_and_mutable_variables.first(); + instruction.set_param_variable(param_index, variable); + input_and_mutable_variables = input_and_mutable_variables.drop_front(1); + break; + } + case MFParamType::Output: { + MFVariable &variable = procedure_->new_variable(param_type.data_type(), + fn.param_name(param_index)); + instruction.set_param_variable(param_index, &variable); + output_variables.append(&variable); + break; + } + } + } + /* All passed in variables should have been dropped in the loop above. */ + BLI_assert(input_and_mutable_variables.is_empty()); + return output_variables; +} + +MFProcedureBuilder::Branch MFProcedureBuilder::add_branch(MFVariable &condition) +{ + MFBranchInstruction &instruction = procedure_->new_branch_instruction(); + instruction.set_condition(&condition); + this->link_to_cursors(&instruction); + /* Clear cursors because this builder ends here. */ + cursors_.clear(); + + Branch branch{*procedure_, *procedure_}; + branch.branch_true.set_cursor(MFInstructionCursor{instruction, true}); + branch.branch_false.set_cursor(MFInstructionCursor{instruction, false}); + return branch; +} + +MFProcedureBuilder::Loop MFProcedureBuilder::add_loop() +{ + MFDummyInstruction &loop_begin = procedure_->new_dummy_instruction(); + MFDummyInstruction &loop_end = procedure_->new_dummy_instruction(); + this->link_to_cursors(&loop_begin); + cursors_ = {MFInstructionCursor{loop_begin}}; + + Loop loop; + loop.begin = &loop_begin; + loop.end = &loop_end; + + return loop; +} + +void MFProcedureBuilder::add_loop_continue(Loop &loop) +{ + this->link_to_cursors(loop.begin); + /* Clear cursors because this builder ends here. */ + cursors_.clear(); +} + +void MFProcedureBuilder::add_loop_break(Loop &loop) +{ + this->link_to_cursors(loop.end); + /* Clear cursors because this builder ends here. */ + cursors_.clear(); +} + +} // namespace blender::fn diff --git a/source/blender/functions/intern/multi_function_procedure_executor.cc b/source/blender/functions/intern/multi_function_procedure_executor.cc new file mode 100644 index 00000000000..38b26415779 --- /dev/null +++ b/source/blender/functions/intern/multi_function_procedure_executor.cc @@ -0,0 +1,1212 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "FN_multi_function_procedure_executor.hh" + +#include "BLI_stack.hh" + +namespace blender::fn { + +MFProcedureExecutor::MFProcedureExecutor(std::string name, const MFProcedure &procedure) + : procedure_(procedure) +{ + MFSignatureBuilder signature(std::move(name)); + + for (const ConstMFParameter ¶m : procedure.params()) { + signature.add(param.variable->name(), MFParamType(param.type, param.variable->data_type())); + } + + signature_ = signature.build(); + this->set_signature(&signature_); +} + +using IndicesSplitVectors = std::array<Vector<int64_t>, 2>; + +namespace { +enum class ValueType { + GVArray = 0, + Span = 1, + GVVectorArray = 2, + GVectorArray = 3, + OneSingle = 4, + OneVector = 5, +}; +constexpr int tot_variable_value_types = 6; +} // namespace + +/** + * During evaluation, a variable may be stored in various different forms, depending on what + * instructions do with the variables. + */ +struct VariableValue { + ValueType type; + + VariableValue(ValueType type) : type(type) + { + } +}; + +/* This variable is the unmodified virtual array from the caller. */ +struct VariableValue_GVArray : public VariableValue { + static inline constexpr ValueType static_type = ValueType::GVArray; + const GVArray &data; + + VariableValue_GVArray(const GVArray &data) : VariableValue(static_type), data(data) + { + } +}; + +/* This variable has a different value for every index. Some values may be uninitialized. The span + * may be owned by the caller. */ +struct VariableValue_Span : public VariableValue { + static inline constexpr ValueType static_type = ValueType::Span; + void *data; + bool owned; + + VariableValue_Span(void *data, bool owned) : VariableValue(static_type), data(data), owned(owned) + { + } +}; + +/* This variable is the unmodified virtual vector array from the caller. */ +struct VariableValue_GVVectorArray : public VariableValue { + static inline constexpr ValueType static_type = ValueType::GVVectorArray; + const GVVectorArray &data; + + VariableValue_GVVectorArray(const GVVectorArray &data) : VariableValue(static_type), data(data) + { + } +}; + +/* This variable has a different vector for every index. */ +struct VariableValue_GVectorArray : public VariableValue { + static inline constexpr ValueType static_type = ValueType::GVectorArray; + GVectorArray &data; + bool owned; + + VariableValue_GVectorArray(GVectorArray &data, bool owned) + : VariableValue(static_type), data(data), owned(owned) + { + } +}; + +/* This variable has the same value for every index. */ +struct VariableValue_OneSingle : public VariableValue { + static inline constexpr ValueType static_type = ValueType::OneSingle; + void *data; + bool is_initialized = false; + + VariableValue_OneSingle(void *data) : VariableValue(static_type), data(data) + { + } +}; + +/* This variable has the same vector for every index. */ +struct VariableValue_OneVector : public VariableValue { + static inline constexpr ValueType static_type = ValueType::OneVector; + GVectorArray &data; + + VariableValue_OneVector(GVectorArray &data) : VariableValue(static_type), data(data) + { + } +}; + +static_assert(std::is_trivially_destructible_v<VariableValue_GVArray>); +static_assert(std::is_trivially_destructible_v<VariableValue_Span>); +static_assert(std::is_trivially_destructible_v<VariableValue_GVVectorArray>); +static_assert(std::is_trivially_destructible_v<VariableValue_GVectorArray>); +static_assert(std::is_trivially_destructible_v<VariableValue_OneSingle>); +static_assert(std::is_trivially_destructible_v<VariableValue_OneVector>); + +class VariableState; + +/** + * The #ValueAllocator is responsible for providing memory for variables and their values. It also + * manages the reuse of buffers to improve performance. + */ +class ValueAllocator : NonCopyable, NonMovable { + private: + /* Allocate with 64 byte alignment for better reusability of buffers and improved cache + * performance. */ + static constexpr inline int min_alignment = 64; + + /* Use stacks so that the most recently used buffers are reused first. This improves cache + * efficiency. */ + std::array<Stack<VariableValue *>, tot_variable_value_types> values_free_lists_; + /* The integer key is the size of one element (e.g. 4 for an integer buffer). All buffers are + * aligned to #min_alignment bytes. */ + Map<int, Stack<void *>> span_buffers_free_list_; + + public: + ValueAllocator() = default; + + ~ValueAllocator() + { + for (Stack<VariableValue *> &stack : values_free_lists_) { + while (!stack.is_empty()) { + MEM_freeN(stack.pop()); + } + } + for (Stack<void *> &stack : span_buffers_free_list_.values()) { + while (!stack.is_empty()) { + MEM_freeN(stack.pop()); + } + } + } + + template<typename... Args> VariableState *obtain_variable_state(Args &&...args); + + void release_variable_state(VariableState *state); + + VariableValue_GVArray *obtain_GVArray(const GVArray &varray) + { + return this->obtain<VariableValue_GVArray>(varray); + } + + VariableValue_GVVectorArray *obtain_GVVectorArray(const GVVectorArray &varray) + { + return this->obtain<VariableValue_GVVectorArray>(varray); + } + + VariableValue_Span *obtain_Span_not_owned(void *buffer) + { + return this->obtain<VariableValue_Span>(buffer, false); + } + + VariableValue_Span *obtain_Span(const CPPType &type, int size) + { + void *buffer = nullptr; + + const int element_size = type.size(); + const int alignment = type.alignment(); + + if (alignment > min_alignment) { + /* In this rare case we fallback to not reusing existing buffers. */ + buffer = MEM_mallocN_aligned(element_size * size, alignment, __func__); + } + else { + Stack<void *> *stack = span_buffers_free_list_.lookup_ptr(element_size); + if (stack == nullptr || stack->is_empty()) { + buffer = MEM_mallocN_aligned(element_size * size, min_alignment, __func__); + } + else { + /* Reuse existing buffer. */ + buffer = stack->pop(); + } + } + + return this->obtain<VariableValue_Span>(buffer, true); + } + + VariableValue_GVectorArray *obtain_GVectorArray_not_owned(GVectorArray &data) + { + return this->obtain<VariableValue_GVectorArray>(data, false); + } + + VariableValue_GVectorArray *obtain_GVectorArray(const CPPType &type, int size) + { + GVectorArray *vector_array = new GVectorArray(type, size); + return this->obtain<VariableValue_GVectorArray>(*vector_array, true); + } + + VariableValue_OneSingle *obtain_OneSingle(const CPPType &type) + { + void *buffer = MEM_mallocN_aligned(type.size(), type.alignment(), __func__); + return this->obtain<VariableValue_OneSingle>(buffer); + } + + VariableValue_OneVector *obtain_OneVector(const CPPType &type) + { + GVectorArray *vector_array = new GVectorArray(type, 1); + return this->obtain<VariableValue_OneVector>(*vector_array); + } + + void release_value(VariableValue *value, const MFDataType &data_type) + { + switch (value->type) { + case ValueType::GVArray: { + break; + } + case ValueType::Span: { + auto *value_typed = static_cast<VariableValue_Span *>(value); + if (value_typed->owned) { + const CPPType &type = data_type.single_type(); + /* Assumes all values in the buffer are uninitialized already. */ + Stack<void *> &buffers = span_buffers_free_list_.lookup_or_add_default(type.size()); + buffers.push(value_typed->data); + } + break; + } + case ValueType::GVVectorArray: { + break; + } + case ValueType::GVectorArray: { + auto *value_typed = static_cast<VariableValue_GVectorArray *>(value); + if (value_typed->owned) { + delete &value_typed->data; + } + break; + } + case ValueType::OneSingle: { + auto *value_typed = static_cast<VariableValue_OneSingle *>(value); + if (value_typed->is_initialized) { + const CPPType &type = data_type.single_type(); + type.destruct(value_typed->data); + } + MEM_freeN(value_typed->data); + break; + } + case ValueType::OneVector: { + auto *value_typed = static_cast<VariableValue_OneVector *>(value); + delete &value_typed->data; + break; + } + } + + Stack<VariableValue *> &stack = values_free_lists_[(int)value->type]; + stack.push(value); + } + + private: + template<typename T, typename... Args> T *obtain(Args &&...args) + { + static_assert(std::is_base_of_v<VariableValue, T>); + Stack<VariableValue *> &stack = values_free_lists_[(int)T::static_type]; + if (stack.is_empty()) { + void *buffer = MEM_mallocN(sizeof(T), __func__); + return new (buffer) T(std::forward<Args>(args)...); + } + return new (stack.pop()) T(std::forward<Args>(args)...); + } +}; + +/** + * This class keeps track of a single variable during evaluation. + */ +class VariableState : NonCopyable, NonMovable { + private: + /** The current value of the variable. The storage format may change over time. */ + VariableValue *value_; + /** Number of indices that are currently initialized in this variable. */ + int tot_initialized_; + /* This a non-owning pointer to either span buffer or #GVectorArray or null. */ + void *caller_provided_storage_ = nullptr; + + public: + VariableState(VariableValue &value, int tot_initialized, void *caller_provided_storage = nullptr) + : value_(&value), + tot_initialized_(tot_initialized), + caller_provided_storage_(caller_provided_storage) + { + } + + void destruct_self(ValueAllocator &value_allocator, const MFDataType &data_type) + { + value_allocator.release_value(value_, data_type); + value_allocator.release_variable_state(this); + } + + /* True if this contains only one value for all indices, i.e. the value for all indices is + * the same. */ + bool is_one() const + { + switch (value_->type) { + case ValueType::GVArray: + return this->value_as<VariableValue_GVArray>()->data.is_single(); + case ValueType::Span: + return tot_initialized_ == 0; + case ValueType::GVVectorArray: + return this->value_as<VariableValue_GVVectorArray>()->data.is_single_vector(); + case ValueType::GVectorArray: + return tot_initialized_ == 0; + case ValueType::OneSingle: + return true; + case ValueType::OneVector: + return true; + } + BLI_assert_unreachable(); + return false; + } + + bool is_fully_initialized(const IndexMask full_mask) + { + return tot_initialized_ == full_mask.size(); + } + + bool is_fully_uninitialized(const IndexMask full_mask) + { + UNUSED_VARS(full_mask); + return tot_initialized_ == 0; + } + + void add_as_input(MFParamsBuilder ¶ms, IndexMask mask, const MFDataType &data_type) const + { + /* Sanity check to make sure that enough values are initialized. */ + BLI_assert(mask.size() <= tot_initialized_); + + switch (value_->type) { + case ValueType::GVArray: { + params.add_readonly_single_input(this->value_as<VariableValue_GVArray>()->data); + break; + } + case ValueType::Span: { + const void *data = this->value_as<VariableValue_Span>()->data; + const GSpan span{data_type.single_type(), data, mask.min_array_size()}; + params.add_readonly_single_input(span); + break; + } + case ValueType::GVVectorArray: { + params.add_readonly_vector_input(this->value_as<VariableValue_GVVectorArray>()->data); + break; + } + case ValueType::GVectorArray: { + params.add_readonly_vector_input(this->value_as<VariableValue_GVectorArray>()->data); + break; + } + case ValueType::OneSingle: { + const auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(value_typed->is_initialized); + const GPointer gpointer{data_type.single_type(), value_typed->data}; + params.add_readonly_single_input(gpointer); + break; + } + case ValueType::OneVector: { + params.add_readonly_vector_input(this->value_as<VariableValue_OneVector>()->data[0]); + break; + } + } + } + + void ensure_is_mutable(IndexMask full_mask, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + if (ELEM(value_->type, ValueType::Span, ValueType::GVectorArray)) { + return; + } + + const int array_size = full_mask.min_array_size(); + + switch (data_type.category()) { + case MFDataType::Single: { + const CPPType &type = data_type.single_type(); + VariableValue_Span *new_value = nullptr; + if (caller_provided_storage_ == nullptr) { + new_value = value_allocator.obtain_Span(type, array_size); + } + else { + /* Reuse the storage provided caller when possible. */ + new_value = value_allocator.obtain_Span_not_owned(caller_provided_storage_); + } + if (value_->type == ValueType::GVArray) { + /* Fill new buffer with data from virtual array. */ + this->value_as<VariableValue_GVArray>()->data.materialize_to_uninitialized( + full_mask, new_value->data); + } + else if (value_->type == ValueType::OneSingle) { + auto *old_value_typed_ = this->value_as<VariableValue_OneSingle>(); + if (old_value_typed_->is_initialized) { + /* Fill the buffer with a single value. */ + type.fill_construct_indices(old_value_typed_->data, new_value->data, full_mask); + } + } + else { + BLI_assert_unreachable(); + } + value_allocator.release_value(value_, data_type); + value_ = new_value; + break; + } + case MFDataType::Vector: { + const CPPType &type = data_type.vector_base_type(); + VariableValue_GVectorArray *new_value = nullptr; + if (caller_provided_storage_ == nullptr) { + new_value = value_allocator.obtain_GVectorArray(type, array_size); + } + else { + new_value = value_allocator.obtain_GVectorArray_not_owned( + *(GVectorArray *)caller_provided_storage_); + } + if (value_->type == ValueType::GVVectorArray) { + /* Fill new vector array with data from virtual vector array. */ + new_value->data.extend(full_mask, this->value_as<VariableValue_GVVectorArray>()->data); + } + else if (value_->type == ValueType::OneVector) { + /* Fill all indices with the same value. */ + const GSpan vector = this->value_as<VariableValue_OneVector>()->data[0]; + new_value->data.extend(full_mask, GVVectorArray_For_SingleGSpan{vector, array_size}); + } + else { + BLI_assert_unreachable(); + } + value_allocator.release_value(value_, data_type); + value_ = new_value; + break; + } + } + } + + void add_as_mutable(MFParamsBuilder ¶ms, + IndexMask mask, + IndexMask full_mask, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + /* Sanity check to make sure that enough values are initialized. */ + BLI_assert(mask.size() <= tot_initialized_); + + this->ensure_is_mutable(full_mask, data_type, value_allocator); + + switch (value_->type) { + case ValueType::Span: { + void *data = this->value_as<VariableValue_Span>()->data; + const GMutableSpan span{data_type.single_type(), data, mask.min_array_size()}; + params.add_single_mutable(span); + break; + } + case ValueType::GVectorArray: { + params.add_vector_mutable(this->value_as<VariableValue_GVectorArray>()->data); + break; + } + case ValueType::GVArray: + case ValueType::GVVectorArray: + case ValueType::OneSingle: + case ValueType::OneVector: { + BLI_assert_unreachable(); + break; + } + } + } + + void add_as_output(MFParamsBuilder ¶ms, + IndexMask mask, + IndexMask full_mask, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + /* Sanity check to make sure that enough values are not initialized. */ + BLI_assert(mask.size() <= full_mask.size() - tot_initialized_); + this->ensure_is_mutable(full_mask, data_type, value_allocator); + + switch (value_->type) { + case ValueType::Span: { + void *data = this->value_as<VariableValue_Span>()->data; + const GMutableSpan span{data_type.single_type(), data, mask.min_array_size()}; + params.add_uninitialized_single_output(span); + break; + } + case ValueType::GVectorArray: { + params.add_vector_output(this->value_as<VariableValue_GVectorArray>()->data); + break; + } + case ValueType::GVArray: + case ValueType::GVVectorArray: + case ValueType::OneSingle: + case ValueType::OneVector: { + BLI_assert_unreachable(); + break; + } + } + + tot_initialized_ += mask.size(); + } + + void add_as_input__one(MFParamsBuilder ¶ms, const MFDataType &data_type) const + { + BLI_assert(this->is_one()); + + switch (value_->type) { + case ValueType::GVArray: { + params.add_readonly_single_input(this->value_as<VariableValue_GVArray>()->data); + break; + } + case ValueType::GVVectorArray: { + params.add_readonly_vector_input(this->value_as<VariableValue_GVVectorArray>()->data); + break; + } + case ValueType::OneSingle: { + const auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(value_typed->is_initialized); + GPointer ptr{data_type.single_type(), value_typed->data}; + params.add_readonly_single_input(ptr); + break; + } + case ValueType::OneVector: { + params.add_readonly_vector_input(this->value_as<VariableValue_OneVector>()->data); + break; + } + case ValueType::Span: + case ValueType::GVectorArray: { + BLI_assert_unreachable(); + break; + } + } + } + + void ensure_is_mutable__one(const MFDataType &data_type, ValueAllocator &value_allocator) + { + BLI_assert(this->is_one()); + if (ELEM(value_->type, ValueType::OneSingle, ValueType::OneVector)) { + return; + } + + switch (data_type.category()) { + case MFDataType::Single: { + const CPPType &type = data_type.single_type(); + VariableValue_OneSingle *new_value = value_allocator.obtain_OneSingle(type); + if (value_->type == ValueType::GVArray) { + this->value_as<VariableValue_GVArray>()->data.get_internal_single_to_uninitialized( + new_value->data); + new_value->is_initialized = true; + } + else if (value_->type == ValueType::Span) { + BLI_assert(tot_initialized_ == 0); + /* Nothing to do, the single value is uninitialized already. */ + } + else { + BLI_assert_unreachable(); + } + value_allocator.release_value(value_, data_type); + value_ = new_value; + break; + } + case MFDataType::Vector: { + const CPPType &type = data_type.vector_base_type(); + VariableValue_OneVector *new_value = value_allocator.obtain_OneVector(type); + if (value_->type == ValueType::GVVectorArray) { + const GVVectorArray &old_vector_array = + this->value_as<VariableValue_GVVectorArray>()->data; + new_value->data.extend(IndexRange(1), old_vector_array); + } + else if (value_->type == ValueType::GVectorArray) { + BLI_assert(tot_initialized_ == 0); + /* Nothing to do. */ + } + else { + BLI_assert_unreachable(); + } + value_allocator.release_value(value_, data_type); + value_ = new_value; + break; + } + } + } + + void add_as_mutable__one(MFParamsBuilder ¶ms, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + BLI_assert(this->is_one()); + this->ensure_is_mutable__one(data_type, value_allocator); + + switch (value_->type) { + case ValueType::OneSingle: { + auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(value_typed->is_initialized); + params.add_single_mutable(GMutableSpan{data_type.single_type(), value_typed->data, 1}); + break; + } + case ValueType::OneVector: { + params.add_vector_mutable(this->value_as<VariableValue_OneVector>()->data); + break; + } + case ValueType::GVArray: + case ValueType::Span: + case ValueType::GVVectorArray: + case ValueType::GVectorArray: { + BLI_assert_unreachable(); + break; + } + } + } + + void add_as_output__one(MFParamsBuilder ¶ms, + IndexMask mask, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + BLI_assert(this->is_one()); + this->ensure_is_mutable__one(data_type, value_allocator); + + switch (value_->type) { + case ValueType::OneSingle: { + auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(!value_typed->is_initialized); + params.add_uninitialized_single_output( + GMutableSpan{data_type.single_type(), value_typed->data, 1}); + /* It becomes initialized when the multi-function is called. */ + value_typed->is_initialized = true; + break; + } + case ValueType::OneVector: { + auto *value_typed = this->value_as<VariableValue_OneVector>(); + BLI_assert(value_typed->data[0].is_empty()); + params.add_vector_output(value_typed->data); + break; + } + case ValueType::GVArray: + case ValueType::Span: + case ValueType::GVVectorArray: + case ValueType::GVectorArray: { + BLI_assert_unreachable(); + break; + } + } + + tot_initialized_ += mask.size(); + } + + void destruct(IndexMask mask, + IndexMask full_mask, + const MFDataType &data_type, + ValueAllocator &value_allocator) + { + int new_tot_initialized = tot_initialized_ - mask.size(); + + /* Sanity check to make sure that enough indices can be destructed. */ + BLI_assert(new_tot_initialized >= 0); + + switch (value_->type) { + case ValueType::GVArray: { + if (mask.size() == full_mask.size()) { + /* All elements are destructed. The elements are owned by the caller, so we don't + * actually destruct them. */ + value_allocator.release_value(value_, data_type); + value_ = value_allocator.obtain_OneSingle(data_type.single_type()); + } + else { + /* Not all elements are destructed. Since we can't work on the original array, we have to + * create a copy first. */ + this->ensure_is_mutable(full_mask, data_type, value_allocator); + BLI_assert(value_->type == ValueType::Span); + const CPPType &type = data_type.single_type(); + type.destruct_indices(this->value_as<VariableValue_Span>()->data, mask); + } + break; + } + case ValueType::Span: { + const CPPType &type = data_type.single_type(); + type.destruct_indices(this->value_as<VariableValue_Span>()->data, mask); + if (new_tot_initialized == 0) { + /* Release span when all values are initialized. */ + value_allocator.release_value(value_, data_type); + value_ = value_allocator.obtain_OneSingle(data_type.single_type()); + } + break; + } + case ValueType::GVVectorArray: { + if (mask.size() == full_mask.size()) { + /* All elements are cleared. The elements are owned by the caller, so don't actually + * destruct them. */ + value_allocator.release_value(value_, data_type); + value_ = value_allocator.obtain_OneVector(data_type.vector_base_type()); + } + else { + /* Not all elements are cleared. Since we can't work on the original vector array, we + * have to create a copy first. A possible future optimization is to create the partial + * copy directly. */ + this->ensure_is_mutable(full_mask, data_type, value_allocator); + BLI_assert(value_->type == ValueType::GVectorArray); + this->value_as<VariableValue_GVectorArray>()->data.clear(mask); + } + break; + } + case ValueType::GVectorArray: { + this->value_as<VariableValue_GVectorArray>()->data.clear(mask); + break; + } + case ValueType::OneSingle: { + auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(value_typed->is_initialized); + if (mask.size() == tot_initialized_) { + const CPPType &type = data_type.single_type(); + type.destruct(value_typed->data); + value_typed->is_initialized = false; + } + break; + } + case ValueType::OneVector: { + auto *value_typed = this->value_as<VariableValue_OneVector>(); + if (mask.size() == tot_initialized_) { + value_typed->data.clear({0}); + } + break; + } + } + + tot_initialized_ = new_tot_initialized; + } + + void indices_split(IndexMask mask, IndicesSplitVectors &r_indices) + { + BLI_assert(mask.size() <= tot_initialized_); + + switch (value_->type) { + case ValueType::GVArray: { + const GVArray_Typed<bool> varray{this->value_as<VariableValue_GVArray>()->data}; + for (const int i : mask) { + r_indices[varray[i]].append(i); + } + break; + } + case ValueType::Span: { + const Span<bool> span((bool *)this->value_as<VariableValue_Span>()->data, + mask.min_array_size()); + for (const int i : mask) { + r_indices[span[i]].append(i); + } + break; + } + case ValueType::OneSingle: { + auto *value_typed = this->value_as<VariableValue_OneSingle>(); + BLI_assert(value_typed->is_initialized); + const bool condition = *(bool *)value_typed->data; + r_indices[condition].extend(mask); + break; + } + case ValueType::GVVectorArray: + case ValueType::GVectorArray: + case ValueType::OneVector: { + BLI_assert_unreachable(); + break; + } + } + } + + template<typename T> T *value_as() + { + BLI_assert(value_->type == T::static_type); + return static_cast<T *>(value_); + } + + template<typename T> const T *value_as() const + { + BLI_assert(value_->type == T::static_type); + return static_cast<T *>(value_); + } +}; + +template<typename... Args> VariableState *ValueAllocator::obtain_variable_state(Args &&...args) +{ + return new VariableState(std::forward<Args>(args)...); +} + +void ValueAllocator::release_variable_state(VariableState *state) +{ + delete state; +} + +/** Keeps track of the states of all variables during evaluation. */ +class VariableStates { + private: + ValueAllocator value_allocator_; + Map<const MFVariable *, VariableState *> variable_states_; + IndexMask full_mask_; + + public: + VariableStates(IndexMask full_mask) : full_mask_(full_mask) + { + } + + ~VariableStates() + { + for (auto &&item : variable_states_.items()) { + const MFVariable *variable = item.key; + VariableState *state = item.value; + state->destruct_self(value_allocator_, variable->data_type()); + } + } + + ValueAllocator &value_allocator() + { + return value_allocator_; + } + + const IndexMask &full_mask() const + { + return full_mask_; + } + + void add_initial_variable_states(const MFProcedureExecutor &fn, + const MFProcedure &procedure, + MFParams ¶ms) + { + for (const int param_index : fn.param_indices()) { + MFParamType param_type = fn.param_type(param_index); + const MFVariable *variable = procedure.params()[param_index].variable; + + auto add_state = [&](VariableValue *value, + bool input_is_initialized, + void *caller_provided_storage = nullptr) { + const int tot_initialized = input_is_initialized ? full_mask_.size() : 0; + variable_states_.add_new(variable, + value_allocator_.obtain_variable_state( + *value, tot_initialized, caller_provided_storage)); + }; + + switch (param_type.category()) { + case MFParamType::SingleInput: { + const GVArray &data = params.readonly_single_input(param_index); + add_state(value_allocator_.obtain_GVArray(data), true); + break; + } + case MFParamType::VectorInput: { + const GVVectorArray &data = params.readonly_vector_input(param_index); + add_state(value_allocator_.obtain_GVVectorArray(data), true); + break; + } + case MFParamType::SingleOutput: { + GMutableSpan data = params.uninitialized_single_output(param_index); + add_state(value_allocator_.obtain_Span_not_owned(data.data()), false, data.data()); + break; + } + case MFParamType::VectorOutput: { + GVectorArray &data = params.vector_output(param_index); + add_state(value_allocator_.obtain_GVectorArray_not_owned(data), false, &data); + break; + } + case MFParamType::SingleMutable: { + GMutableSpan data = params.single_mutable(param_index); + add_state(value_allocator_.obtain_Span_not_owned(data.data()), true, data.data()); + break; + } + case MFParamType::VectorMutable: { + GVectorArray &data = params.vector_mutable(param_index); + add_state(value_allocator_.obtain_GVectorArray_not_owned(data), true, &data); + break; + } + } + } + } + + void add_as_param(VariableState &variable_state, + MFParamsBuilder ¶ms, + const MFParamType ¶m_type, + const IndexMask &mask) + { + const MFDataType data_type = param_type.data_type(); + switch (param_type.interface_type()) { + case MFParamType::Input: { + variable_state.add_as_input(params, mask, data_type); + break; + } + case MFParamType::Mutable: { + variable_state.add_as_mutable(params, mask, full_mask_, data_type, value_allocator_); + break; + } + case MFParamType::Output: { + variable_state.add_as_output(params, mask, full_mask_, data_type, value_allocator_); + break; + } + } + } + + void add_as_param__one(VariableState &variable_state, + MFParamsBuilder ¶ms, + const MFParamType ¶m_type, + const IndexMask &mask) + { + const MFDataType data_type = param_type.data_type(); + switch (param_type.interface_type()) { + case MFParamType::Input: { + variable_state.add_as_input__one(params, data_type); + break; + } + case MFParamType::Mutable: { + variable_state.add_as_mutable__one(params, data_type, value_allocator_); + break; + } + case MFParamType::Output: { + variable_state.add_as_output__one(params, mask, data_type, value_allocator_); + break; + } + } + } + + void destruct(const MFVariable &variable, const IndexMask &mask) + { + VariableState &variable_state = this->get_variable_state(variable); + variable_state.destruct(mask, full_mask_, variable.data_type(), value_allocator_); + } + + VariableState &get_variable_state(const MFVariable &variable) + { + return *variable_states_.lookup_or_add_cb( + &variable, [&]() { return this->create_new_state_for_variable(variable); }); + } + + VariableState *create_new_state_for_variable(const MFVariable &variable) + { + MFDataType data_type = variable.data_type(); + switch (data_type.category()) { + case MFDataType::Single: { + const CPPType &type = data_type.single_type(); + return value_allocator_.obtain_variable_state(*value_allocator_.obtain_OneSingle(type), 0); + } + case MFDataType::Vector: { + const CPPType &type = data_type.vector_base_type(); + return value_allocator_.obtain_variable_state(*value_allocator_.obtain_OneVector(type), 0); + } + } + BLI_assert_unreachable(); + return nullptr; + } +}; + +static bool evaluate_as_one(const MultiFunction &fn, + Span<VariableState *> param_variable_states, + const IndexMask &mask, + const IndexMask &full_mask) +{ + if (fn.depends_on_context()) { + return false; + } + if (mask.size() < full_mask.size()) { + return false; + } + for (VariableState *state : param_variable_states) { + if (!state->is_one()) { + return false; + } + } + return true; +} + +static void execute_call_instruction(const MFCallInstruction &instruction, + IndexMask mask, + VariableStates &variable_states, + const MFContext &context) +{ + const MultiFunction &fn = instruction.fn(); + + Vector<VariableState *> param_variable_states; + param_variable_states.resize(fn.param_amount()); + + for (const int param_index : fn.param_indices()) { + const MFVariable *variable = instruction.params()[param_index]; + VariableState &variable_state = variable_states.get_variable_state(*variable); + param_variable_states[param_index] = &variable_state; + } + + /* If all inputs to the function are constant, it's enough to call the function only once instead + * of for every index. */ + if (evaluate_as_one(fn, param_variable_states, mask, variable_states.full_mask())) { + MFParamsBuilder params(fn, 1); + + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + VariableState &variable_state = *param_variable_states[param_index]; + variable_states.add_as_param__one(variable_state, params, param_type, mask); + } + + fn.call(IndexRange(1), params, context); + } + else { + MFParamsBuilder params(fn, mask.min_array_size()); + + for (const int param_index : fn.param_indices()) { + const MFParamType param_type = fn.param_type(param_index); + VariableState &variable_state = *param_variable_states[param_index]; + variable_states.add_as_param(variable_state, params, param_type, mask); + } + + fn.call(mask, params, context); + } +} + +/** An index mask, that might own the indices if necessary. */ +struct InstructionIndices { + bool is_owned; + Vector<int64_t> owned_indices; + IndexMask referenced_indices; + + IndexMask mask() const + { + if (this->is_owned) { + return this->owned_indices.as_span(); + } + return this->referenced_indices; + } +}; + +/** Contains information about the next instruction that should be executed. */ +struct NextInstructionInfo { + const MFInstruction *instruction = nullptr; + InstructionIndices indices; + + IndexMask mask() const + { + return this->indices.mask(); + } + + operator bool() const + { + return this->instruction != nullptr; + } +}; + +/** + * Keeps track of the next instruction for all indices and decides in which order instructions are + * evaluated. + */ +class InstructionScheduler { + private: + Map<const MFInstruction *, Vector<InstructionIndices>> indices_by_instruction_; + + public: + InstructionScheduler() = default; + + void add_referenced_indices(const MFInstruction &instruction, IndexMask mask) + { + if (mask.is_empty()) { + return; + } + InstructionIndices new_indices; + new_indices.is_owned = false; + new_indices.referenced_indices = mask; + indices_by_instruction_.lookup_or_add_default(&instruction).append(std::move(new_indices)); + } + + void add_owned_indices(const MFInstruction &instruction, Vector<int64_t> indices) + { + if (indices.is_empty()) { + return; + } + BLI_assert(IndexMask::indices_are_valid_index_mask(indices)); + + InstructionIndices new_indices; + new_indices.is_owned = true; + new_indices.owned_indices = std::move(indices); + indices_by_instruction_.lookup_or_add_default(&instruction).append(std::move(new_indices)); + } + + void add_previous_instruction_indices(const MFInstruction &instruction, + NextInstructionInfo &instr_info) + { + indices_by_instruction_.lookup_or_add_default(&instruction) + .append(std::move(instr_info.indices)); + } + + NextInstructionInfo pop_next() + { + if (indices_by_instruction_.is_empty()) { + return {}; + } + /* TODO: Implement better mechanism to determine next instruction. */ + const MFInstruction *instruction = *indices_by_instruction_.keys().begin(); + + NextInstructionInfo next_instruction_info; + next_instruction_info.instruction = instruction; + next_instruction_info.indices = this->pop_indices_array(instruction); + return next_instruction_info; + } + + private: + InstructionIndices pop_indices_array(const MFInstruction *instruction) + { + Vector<InstructionIndices> *indices = indices_by_instruction_.lookup_ptr(instruction); + if (indices == nullptr) { + return {}; + } + InstructionIndices r_indices = (*indices).pop_last(); + BLI_assert(!r_indices.mask().is_empty()); + if (indices->is_empty()) { + indices_by_instruction_.remove_contained(instruction); + } + return r_indices; + } +}; + +void MFProcedureExecutor::call(IndexMask full_mask, MFParams params, MFContext context) const +{ + BLI_assert(procedure_.validate()); + + LinearAllocator<> allocator; + + VariableStates variable_states{full_mask}; + variable_states.add_initial_variable_states(*this, procedure_, params); + + InstructionScheduler scheduler; + scheduler.add_referenced_indices(*procedure_.entry(), full_mask); + + /* Loop until all indices got to a return instruction. */ + while (NextInstructionInfo instr_info = scheduler.pop_next()) { + const MFInstruction &instruction = *instr_info.instruction; + switch (instruction.type()) { + case MFInstructionType::Call: { + const MFCallInstruction &call_instruction = static_cast<const MFCallInstruction &>( + instruction); + execute_call_instruction(call_instruction, instr_info.mask(), variable_states, context); + scheduler.add_previous_instruction_indices(*call_instruction.next(), instr_info); + break; + } + case MFInstructionType::Branch: { + const MFBranchInstruction &branch_instruction = static_cast<const MFBranchInstruction &>( + instruction); + const MFVariable *condition_var = branch_instruction.condition(); + VariableState &variable_state = variable_states.get_variable_state(*condition_var); + + IndicesSplitVectors new_indices; + variable_state.indices_split(instr_info.mask(), new_indices); + scheduler.add_owned_indices(*branch_instruction.branch_false(), new_indices[false]); + scheduler.add_owned_indices(*branch_instruction.branch_true(), new_indices[true]); + break; + } + case MFInstructionType::Destruct: { + const MFDestructInstruction &destruct_instruction = + static_cast<const MFDestructInstruction &>(instruction); + const MFVariable *variable = destruct_instruction.variable(); + variable_states.destruct(*variable, instr_info.mask()); + scheduler.add_previous_instruction_indices(*destruct_instruction.next(), instr_info); + break; + } + case MFInstructionType::Dummy: { + const MFDummyInstruction &dummy_instruction = static_cast<const MFDummyInstruction &>( + instruction); + scheduler.add_previous_instruction_indices(*dummy_instruction.next(), instr_info); + break; + } + case MFInstructionType::Return: { + /* Don't insert the indices back into the scheduler. */ + break; + } + } + } + + for (const int param_index : this->param_indices()) { + const MFParamType param_type = this->param_type(param_index); + const MFVariable *variable = procedure_.params()[param_index].variable; + VariableState &variable_state = variable_states.get_variable_state(*variable); + switch (param_type.interface_type()) { + case MFParamType::Input: { + /* Input variables must be destructed in the end. */ + BLI_assert(variable_state.is_fully_uninitialized(full_mask)); + break; + } + case MFParamType::Mutable: + case MFParamType::Output: { + /* Mutable and output variables must be initialized in the end. */ + BLI_assert(variable_state.is_fully_initialized(full_mask)); + /* Make sure that the data is in the memory provided by the caller. */ + variable_state.ensure_is_mutable( + full_mask, param_type.data_type(), variable_states.value_allocator()); + break; + } + } + } +} + +} // namespace blender::fn diff --git a/source/blender/functions/tests/FN_field_test.cc b/source/blender/functions/tests/FN_field_test.cc new file mode 100644 index 00000000000..212b79e75d3 --- /dev/null +++ b/source/blender/functions/tests/FN_field_test.cc @@ -0,0 +1,278 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "FN_cpp_type.hh" +#include "FN_field.hh" +#include "FN_multi_function_builder.hh" + +namespace blender::fn::tests { + +TEST(field, ConstantFunction) +{ + /* TODO: Figure out how to not use another "FieldOperation(" inside of std::make_shared. */ + GField constant_field{std::make_shared<FieldOperation>( + FieldOperation(std::make_unique<CustomMF_Constant<int>>(10), {})), + 0}; + + Array<int> result(4); + + FieldContext context; + FieldEvaluator evaluator{context, 4}; + evaluator.add_with_destination(constant_field, result.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result[0], 10); + EXPECT_EQ(result[1], 10); + EXPECT_EQ(result[2], 10); + EXPECT_EQ(result[3], 10); +} + +class IndexFieldInput final : public FieldInput { + public: + IndexFieldInput() : FieldInput(CPPType::get<int>(), "Index") + { + } + + const GVArray *get_varray_for_context(const FieldContext &UNUSED(context), + IndexMask mask, + ResourceScope &scope) const final + { + auto index_func = [](int i) { return i; }; + return &scope.construct< + GVArray_For_EmbeddedVArray<int, VArray_For_Func<int, decltype(index_func)>>>( + __func__, mask.min_array_size(), mask.min_array_size(), index_func); + } +}; + +TEST(field, VArrayInput) +{ + GField index_field{std::make_shared<IndexFieldInput>()}; + + Array<int> result_1(4); + + FieldContext context; + FieldEvaluator evaluator{context, 4}; + evaluator.add_with_destination(index_field, result_1.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result_1[0], 0); + EXPECT_EQ(result_1[1], 1); + EXPECT_EQ(result_1[2], 2); + EXPECT_EQ(result_1[3], 3); + + /* Evaluate a second time, just to test that the first didn't break anything. */ + Array<int> result_2(10); + + const Array<int64_t> indices = {2, 4, 6, 8}; + const IndexMask mask{indices}; + + FieldEvaluator evaluator_2{context, &mask}; + evaluator_2.add_with_destination(index_field, result_2.as_mutable_span()); + evaluator_2.evaluate(); + EXPECT_EQ(result_2[2], 2); + EXPECT_EQ(result_2[4], 4); + EXPECT_EQ(result_2[6], 6); + EXPECT_EQ(result_2[8], 8); +} + +TEST(field, VArrayInputMultipleOutputs) +{ + std::shared_ptr<FieldInput> index_input = std::make_shared<IndexFieldInput>(); + GField field_1{index_input}; + GField field_2{index_input}; + + Array<int> result_1(10); + Array<int> result_2(10); + + const Array<int64_t> indices = {2, 4, 6, 8}; + const IndexMask mask{indices}; + + FieldContext context; + FieldEvaluator evaluator{context, &mask}; + evaluator.add_with_destination(field_1, result_1.as_mutable_span()); + evaluator.add_with_destination(field_2, result_2.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result_1[2], 2); + EXPECT_EQ(result_1[4], 4); + EXPECT_EQ(result_1[6], 6); + EXPECT_EQ(result_1[8], 8); + EXPECT_EQ(result_2[2], 2); + EXPECT_EQ(result_2[4], 4); + EXPECT_EQ(result_2[6], 6); + EXPECT_EQ(result_2[8], 8); +} + +TEST(field, InputAndFunction) +{ + GField index_field{std::make_shared<IndexFieldInput>()}; + + std::unique_ptr<MultiFunction> add_fn = std::make_unique<CustomMF_SI_SI_SO<int, int, int>>( + "add", [](int a, int b) { return a + b; }); + GField output_field{std::make_shared<FieldOperation>( + FieldOperation(std::move(add_fn), {index_field, index_field})), + 0}; + + Array<int> result(10); + + const Array<int64_t> indices = {2, 4, 6, 8}; + const IndexMask mask{indices}; + + FieldContext context; + FieldEvaluator evaluator{context, &mask}; + evaluator.add_with_destination(output_field, result.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result[2], 4); + EXPECT_EQ(result[4], 8); + EXPECT_EQ(result[6], 12); + EXPECT_EQ(result[8], 16); +} + +TEST(field, TwoFunctions) +{ + GField index_field{std::make_shared<IndexFieldInput>()}; + + std::unique_ptr<MultiFunction> add_fn = std::make_unique<CustomMF_SI_SI_SO<int, int, int>>( + "add", [](int a, int b) { return a + b; }); + GField add_field{std::make_shared<FieldOperation>( + FieldOperation(std::move(add_fn), {index_field, index_field})), + 0}; + + std::unique_ptr<MultiFunction> add_10_fn = std::make_unique<CustomMF_SI_SO<int, int>>( + "add_10", [](int a) { return a + 10; }); + GField result_field{ + std::make_shared<FieldOperation>(FieldOperation(std::move(add_10_fn), {add_field})), 0}; + + Array<int> result(10); + + const Array<int64_t> indices = {2, 4, 6, 8}; + const IndexMask mask{indices}; + + FieldContext context; + FieldEvaluator evaluator{context, &mask}; + evaluator.add_with_destination(result_field, result.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result[2], 14); + EXPECT_EQ(result[4], 18); + EXPECT_EQ(result[6], 22); + EXPECT_EQ(result[8], 26); +} + +class TwoOutputFunction : public MultiFunction { + private: + MFSignature signature_; + + public: + TwoOutputFunction(StringRef name) + { + MFSignatureBuilder signature{name}; + signature.single_input<int>("In1"); + signature.single_input<int>("In2"); + signature.single_output<int>("Add"); + signature.single_output<int>("Add10"); + signature_ = signature.build(); + this->set_signature(&signature_); + } + + void call(IndexMask mask, MFParams params, MFContext UNUSED(context)) const override + { + const VArray<int> &in1 = params.readonly_single_input<int>(0, "In1"); + const VArray<int> &in2 = params.readonly_single_input<int>(1, "In2"); + MutableSpan<int> add = params.uninitialized_single_output<int>(2, "Add"); + MutableSpan<int> add_10 = params.uninitialized_single_output<int>(3, "Add10"); + mask.foreach_index([&](const int64_t i) { + add[i] = in1[i] + in2[i]; + add_10[i] = add[i] + 10; + }); + } +}; + +TEST(field, FunctionTwoOutputs) +{ + /* Also use two separate input fields, why not. */ + GField index_field_1{std::make_shared<IndexFieldInput>()}; + GField index_field_2{std::make_shared<IndexFieldInput>()}; + + std::shared_ptr<FieldOperation> fn = std::make_shared<FieldOperation>(FieldOperation( + std::make_unique<TwoOutputFunction>("SI_SI_SO_SO"), {index_field_1, index_field_2})); + + GField result_field_1{fn, 0}; + GField result_field_2{fn, 1}; + + Array<int> result_1(10); + Array<int> result_2(10); + + const Array<int64_t> indices = {2, 4, 6, 8}; + const IndexMask mask{indices}; + + FieldContext context; + FieldEvaluator evaluator{context, &mask}; + evaluator.add_with_destination(result_field_1, result_1.as_mutable_span()); + evaluator.add_with_destination(result_field_2, result_2.as_mutable_span()); + evaluator.evaluate(); + EXPECT_EQ(result_1[2], 4); + EXPECT_EQ(result_1[4], 8); + EXPECT_EQ(result_1[6], 12); + EXPECT_EQ(result_1[8], 16); + EXPECT_EQ(result_2[2], 14); + EXPECT_EQ(result_2[4], 18); + EXPECT_EQ(result_2[6], 22); + EXPECT_EQ(result_2[8], 26); +} + +TEST(field, TwoFunctionsTwoOutputs) +{ + GField index_field{std::make_shared<IndexFieldInput>()}; + + std::shared_ptr<FieldOperation> fn = std::make_shared<FieldOperation>(FieldOperation( + std::make_unique<TwoOutputFunction>("SI_SI_SO_SO"), {index_field, index_field})); + + Array<int64_t> mask_indices = {2, 4, 6, 8}; + IndexMask mask = mask_indices.as_span(); + + Field<int> result_field_1{fn, 0}; + Field<int> intermediate_field{fn, 1}; + + std::unique_ptr<MultiFunction> add_10_fn = std::make_unique<CustomMF_SI_SO<int, int>>( + "add_10", [](int a) { return a + 10; }); + Field<int> result_field_2{ + std::make_shared<FieldOperation>(FieldOperation(std::move(add_10_fn), {intermediate_field})), + 0}; + + FieldContext field_context; + FieldEvaluator field_evaluator{field_context, &mask}; + const VArray<int> *result_1 = nullptr; + const VArray<int> *result_2 = nullptr; + field_evaluator.add(result_field_1, &result_1); + field_evaluator.add(result_field_2, &result_2); + field_evaluator.evaluate(); + + EXPECT_EQ(result_1->get(2), 4); + EXPECT_EQ(result_1->get(4), 8); + EXPECT_EQ(result_1->get(6), 12); + EXPECT_EQ(result_1->get(8), 16); + EXPECT_EQ(result_2->get(2), 24); + EXPECT_EQ(result_2->get(4), 28); + EXPECT_EQ(result_2->get(6), 32); + EXPECT_EQ(result_2->get(8), 36); +} + +TEST(field, SameFieldTwice) +{ + GField constant_field{ + std::make_shared<FieldOperation>(std::make_unique<CustomMF_Constant<int>>(10)), 0}; + + FieldContext field_context; + IndexMask mask{IndexRange(2)}; + ResourceScope scope; + Vector<const GVArray *> results = evaluate_fields( + scope, {constant_field, constant_field}, mask, field_context); + + GVArray_Typed<int> varray1{*results[0]}; + GVArray_Typed<int> varray2{*results[1]}; + + EXPECT_EQ(varray1->get(0), 10); + EXPECT_EQ(varray1->get(1), 10); + EXPECT_EQ(varray2->get(0), 10); + EXPECT_EQ(varray2->get(1), 10); +} + +} // namespace blender::fn::tests diff --git a/source/blender/functions/tests/FN_multi_function_procedure_test.cc b/source/blender/functions/tests/FN_multi_function_procedure_test.cc new file mode 100644 index 00000000000..0b4b88fba3d --- /dev/null +++ b/source/blender/functions/tests/FN_multi_function_procedure_test.cc @@ -0,0 +1,344 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "FN_multi_function_builder.hh" +#include "FN_multi_function_procedure_builder.hh" +#include "FN_multi_function_procedure_executor.hh" +#include "FN_multi_function_test_common.hh" + +namespace blender::fn::tests { + +TEST(multi_function_procedure, SimpleTest) +{ + /** + * procedure(int var1, int var2, int *var4) { + * int var3 = var1 + var2; + * var4 = var2 + var3; + * var4 += 10; + * } + */ + + CustomMF_SI_SI_SO<int, int, int> add_fn{"add", [](int a, int b) { return a + b; }}; + CustomMF_SM<int> add_10_fn{"add_10", [](int &a) { a += 10; }}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var1 = &builder.add_single_input_parameter<int>(); + MFVariable *var2 = &builder.add_single_input_parameter<int>(); + auto [var3] = builder.add_call<1>(add_fn, {var1, var2}); + auto [var4] = builder.add_call<1>(add_fn, {var2, var3}); + builder.add_call(add_10_fn, {var4}); + builder.add_destruct({var1, var2, var3}); + builder.add_return(); + builder.add_output_parameter(*var4); + + EXPECT_TRUE(procedure.validate()); + + MFProcedureExecutor executor{"My Procedure", procedure}; + + MFParamsBuilder params{executor, 3}; + MFContextBuilder context; + + Array<int> input_array = {1, 2, 3}; + params.add_readonly_single_input(input_array.as_span()); + params.add_readonly_single_input_value(3); + + Array<int> output_array(3); + params.add_uninitialized_single_output(output_array.as_mutable_span()); + + executor.call(IndexRange(3), params, context); + + EXPECT_EQ(output_array[0], 17); + EXPECT_EQ(output_array[1], 18); + EXPECT_EQ(output_array[2], 19); +} + +TEST(multi_function_procedure, BranchTest) +{ + /** + * procedure(int &var1, bool var2) { + * if (var2) { + * var1 += 100; + * } + * else { + * var1 += 10; + * } + * var1 += 10; + * } + */ + + CustomMF_SM<int> add_10_fn{"add_10", [](int &a) { a += 10; }}; + CustomMF_SM<int> add_100_fn{"add_100", [](int &a) { a += 100; }}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var1 = &builder.add_single_mutable_parameter<int>(); + MFVariable *var2 = &builder.add_single_input_parameter<bool>(); + + MFProcedureBuilder::Branch branch = builder.add_branch(*var2); + branch.branch_false.add_call(add_10_fn, {var1}); + branch.branch_true.add_call(add_100_fn, {var1}); + builder.set_cursor_after_branch(branch); + builder.add_call(add_10_fn, {var1}); + builder.add_destruct({var2}); + builder.add_return(); + + EXPECT_TRUE(procedure.validate()); + + MFProcedureExecutor procedure_fn{"Condition Test", procedure}; + MFParamsBuilder params(procedure_fn, 5); + + Array<int> values_a = {1, 5, 3, 6, 2}; + Array<bool> values_cond = {true, false, true, true, false}; + + params.add_single_mutable(values_a.as_mutable_span()); + params.add_readonly_single_input(values_cond.as_span()); + + MFContextBuilder context; + procedure_fn.call({1, 2, 3, 4}, params, context); + + EXPECT_EQ(values_a[0], 1); + EXPECT_EQ(values_a[1], 25); + EXPECT_EQ(values_a[2], 113); + EXPECT_EQ(values_a[3], 116); + EXPECT_EQ(values_a[4], 22); +} + +TEST(multi_function_procedure, EvaluateOne) +{ + /** + * procedure(int var1, int *var2) { + * var2 = var1 + 10; + * } + */ + + int tot_evaluations = 0; + CustomMF_SI_SO<int, int> add_10_fn{"add_10", [&](int a) { + tot_evaluations++; + return a + 10; + }}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var1 = &builder.add_single_input_parameter<int>(); + auto [var2] = builder.add_call<1>(add_10_fn, {var1}); + builder.add_destruct(*var1); + builder.add_return(); + builder.add_output_parameter(*var2); + + MFProcedureExecutor procedure_fn{"Evaluate One", procedure}; + MFParamsBuilder params{procedure_fn, 5}; + + Array<int> values_out = {1, 2, 3, 4, 5}; + params.add_readonly_single_input_value(1); + params.add_uninitialized_single_output(values_out.as_mutable_span()); + + MFContextBuilder context; + procedure_fn.call({0, 1, 3, 4}, params, context); + + EXPECT_EQ(values_out[0], 11); + EXPECT_EQ(values_out[1], 11); + EXPECT_EQ(values_out[2], 3); + EXPECT_EQ(values_out[3], 11); + EXPECT_EQ(values_out[4], 11); + /* We expect only one evaluation, because the input is constant. */ + EXPECT_EQ(tot_evaluations, 1); +} + +TEST(multi_function_procedure, SimpleLoop) +{ + /** + * procedure(int count, int *out) { + * out = 1; + * int index = 0' + * loop { + * if (index >= count) { + * break; + * } + * out *= 2; + * index += 1; + * } + * out += 1000; + * } + */ + + CustomMF_Constant<int> const_1_fn{1}; + CustomMF_Constant<int> const_0_fn{0}; + CustomMF_SI_SI_SO<int, int, bool> greater_or_equal_fn{"greater or equal", + [](int a, int b) { return a >= b; }}; + CustomMF_SM<int> double_fn{"double", [](int &a) { a *= 2; }}; + CustomMF_SM<int> add_1000_fn{"add 1000", [](int &a) { a += 1000; }}; + CustomMF_SM<int> add_1_fn{"add 1", [](int &a) { a += 1; }}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var_count = &builder.add_single_input_parameter<int>("count"); + auto [var_out] = builder.add_call<1>(const_1_fn); + var_out->set_name("out"); + auto [var_index] = builder.add_call<1>(const_0_fn); + var_index->set_name("index"); + + MFProcedureBuilder::Loop loop = builder.add_loop(); + auto [var_condition] = builder.add_call<1>(greater_or_equal_fn, {var_index, var_count}); + var_condition->set_name("condition"); + MFProcedureBuilder::Branch branch = builder.add_branch(*var_condition); + branch.branch_true.add_destruct(*var_condition); + branch.branch_true.add_loop_break(loop); + branch.branch_false.add_destruct(*var_condition); + builder.set_cursor_after_branch(branch); + builder.add_call(double_fn, {var_out}); + builder.add_call(add_1_fn, {var_index}); + builder.add_loop_continue(loop); + builder.set_cursor_after_loop(loop); + builder.add_call(add_1000_fn, {var_out}); + builder.add_destruct({var_count, var_index}); + builder.add_return(); + builder.add_output_parameter(*var_out); + + EXPECT_TRUE(procedure.validate()); + + MFProcedureExecutor procedure_fn{"Simple Loop", procedure}; + MFParamsBuilder params{procedure_fn, 5}; + + Array<int> counts = {4, 3, 7, 6, 4}; + Array<int> results(5, -1); + + params.add_readonly_single_input(counts.as_span()); + params.add_uninitialized_single_output(results.as_mutable_span()); + + MFContextBuilder context; + procedure_fn.call({0, 1, 3, 4}, params, context); + + EXPECT_EQ(results[0], 1016); + EXPECT_EQ(results[1], 1008); + EXPECT_EQ(results[2], -1); + EXPECT_EQ(results[3], 1064); + EXPECT_EQ(results[4], 1016); +} + +TEST(multi_function_procedure, Vectors) +{ + /** + * procedure(vector<int> v1, vector<int> &v2, vector<int> *v3) { + * v1.extend(v2); + * int constant = 5; + * v2.append(constant); + * v2.extend(v1); + * int len = sum(v2); + * v3 = range(len); + * } + */ + + CreateRangeFunction create_range_fn; + ConcatVectorsFunction extend_fn; + GenericAppendFunction append_fn{CPPType::get<int>()}; + SumVectorFunction sum_elements_fn; + CustomMF_Constant<int> constant_5_fn{5}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var_v1 = &builder.add_input_parameter(MFDataType::ForVector<int>()); + MFVariable *var_v2 = &builder.add_parameter(MFParamType::ForMutableVector(CPPType::get<int>())); + builder.add_call(extend_fn, {var_v1, var_v2}); + auto [var_constant] = builder.add_call<1>(constant_5_fn); + builder.add_call(append_fn, {var_v2, var_constant}); + builder.add_destruct(*var_constant); + builder.add_call(extend_fn, {var_v2, var_v1}); + auto [var_len] = builder.add_call<1>(sum_elements_fn, {var_v2}); + auto [var_v3] = builder.add_call<1>(create_range_fn, {var_len}); + builder.add_destruct({var_v1, var_len}); + builder.add_return(); + builder.add_output_parameter(*var_v3); + + EXPECT_TRUE(procedure.validate()); + + MFProcedureExecutor procedure_fn{"Vectors", procedure}; + MFParamsBuilder params{procedure_fn, 5}; + + Array<int> v1 = {5, 2, 3}; + GVectorArray v2{CPPType::get<int>(), 5}; + GVectorArray v3{CPPType::get<int>(), 5}; + + int value_10 = 10; + v2.append(0, &value_10); + v2.append(4, &value_10); + + params.add_readonly_vector_input(v1.as_span()); + params.add_vector_mutable(v2); + params.add_vector_output(v3); + + MFContextBuilder context; + procedure_fn.call({0, 1, 3, 4}, params, context); + + EXPECT_EQ(v2[0].size(), 6); + EXPECT_EQ(v2[1].size(), 4); + EXPECT_EQ(v2[2].size(), 0); + EXPECT_EQ(v2[3].size(), 4); + EXPECT_EQ(v2[4].size(), 6); + + EXPECT_EQ(v3[0].size(), 35); + EXPECT_EQ(v3[1].size(), 15); + EXPECT_EQ(v3[2].size(), 0); + EXPECT_EQ(v3[3].size(), 15); + EXPECT_EQ(v3[4].size(), 35); +} + +TEST(multi_function_procedure, BufferReuse) +{ + /** + * procedure(int a, int *out) { + * int b = a + 10; + * int c = c + 10; + * int d = d + 10; + * int e = d + 10; + * out = e + 10; + * } + */ + + CustomMF_SI_SO<int, int> add_10_fn{"add 10", [](int a) { return a + 10; }}; + + MFProcedure procedure; + MFProcedureBuilder builder{procedure}; + + MFVariable *var_a = &builder.add_single_input_parameter<int>(); + auto [var_b] = builder.add_call<1>(add_10_fn, {var_a}); + builder.add_destruct(*var_a); + auto [var_c] = builder.add_call<1>(add_10_fn, {var_b}); + builder.add_destruct(*var_b); + auto [var_d] = builder.add_call<1>(add_10_fn, {var_c}); + builder.add_destruct(*var_c); + auto [var_e] = builder.add_call<1>(add_10_fn, {var_d}); + builder.add_destruct(*var_d); + auto [var_out] = builder.add_call<1>(add_10_fn, {var_e}); + builder.add_destruct(*var_e); + builder.add_return(); + builder.add_output_parameter(*var_out); + + EXPECT_TRUE(procedure.validate()); + + MFProcedureExecutor procedure_fn{"Buffer Reuse", procedure}; + + Array<int> inputs = {4, 1, 6, 2, 3}; + Array<int> results(5, -1); + + MFParamsBuilder params{procedure_fn, 5}; + params.add_readonly_single_input(inputs.as_span()); + params.add_uninitialized_single_output(results.as_mutable_span()); + + MFContextBuilder context; + procedure_fn.call({0, 2, 3, 4}, params, context); + + EXPECT_EQ(results[0], 54); + EXPECT_EQ(results[1], -1); + EXPECT_EQ(results[2], 56); + EXPECT_EQ(results[3], 52); + EXPECT_EQ(results[4], 53); +} + +} // namespace blender::fn::tests |