diff options
Diffstat (limited to 'source/blender/functions/FN_lazy_function.hh')
-rw-r--r-- | source/blender/functions/FN_lazy_function.hh | 384 |
1 files changed, 384 insertions, 0 deletions
diff --git a/source/blender/functions/FN_lazy_function.hh b/source/blender/functions/FN_lazy_function.hh new file mode 100644 index 00000000000..59a3a90b0b0 --- /dev/null +++ b/source/blender/functions/FN_lazy_function.hh @@ -0,0 +1,384 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ + +#pragma once + +/** \file + * \ingroup fn + * + * A `LazyFunction` encapsulates a computation which has inputs, outputs and potentially side + * effects. Most importantly, a `LazyFunction` supports laziness in its inputs and outputs: + * - Only outputs that are actually used have to be computed. + * - Inputs can be requested lazily based on which outputs are used or what side effects the + * function has. + * + * A lazy-function that uses laziness may be executed more than once. The most common example is + * the geometry nodes switch node. Depending on a condition input, it decides which one of the + * other inputs is actually used. From the perspective of the switch node, its execution works as + * follows: + * 1. The switch node is first executed. It sees that the output is used. Now it requests the + * condition input from the caller and exits. + * 2. Once the caller is able to provide the condition input the switch node is executed again. + * This time it retrieves the condition and requests one of the other inputs. Then the node + * exits again, giving back control to the caller. + * 3. When the caller computed the second requested input the switch node executes a last time. + * This time it retrieves the new input and forwards it to the output. + * + * In some sense, a lazy-function can be thought of like a state machine. Every time it is + * executed, it advances its state until all required outputs are ready. + * + * The lazy-function interface is designed to support composition of many such functions into a new + * lazy-functions, all while keeping the laziness working. For example, in geometry nodes a switch + * node in a node group should still be able to decide whether a node in the parent group will be + * executed or not. This is essential to avoid doing unnecessary work. + * + * The lazy-function system consists of multiple core components: + * - The interface of a lazy-function itself including its calling convention. + * - A graph data structure that allows composing many lazy-functions by connecting their inputs + * and outputs. + * - An executor that allows multi-threaded execution or such a graph. + */ + +#include "BLI_cpp_type.hh" +#include "BLI_generic_pointer.hh" +#include "BLI_linear_allocator.hh" +#include "BLI_vector.hh" + +namespace blender::fn::lazy_function { + +enum class ValueUsage { + /** + * The value is definitely used and therefore has to be computed. + */ + Used, + /** + * It's unknown whether this value will be used or not. Computing it is ok but the result may be + * discarded. + */ + Maybe, + /** + * The value will definitely not be used. It can still be computed but the result will be + * discarded in all cases. + */ + Unused, +}; + +class LazyFunction; + +/** + * This allows passing arbitrary data into a lazy-function during execution. For that, #UserData + * has to be subclassed. This mainly exists because it's more type safe than passing a `void *` + * with no type information attached. + * + * Some lazy-functions may expect to find a certain type of user data when executed. + */ +class UserData { + public: + virtual ~UserData() = default; +}; + +/** + * Passed to the lazy-function when it is executed. + */ +struct Context { + /** + * If the lazy-function has some state (which only makes sense when it is executed more than once + * to finish its job), the state is stored here. This points to memory returned from + * #LazyFunction::init_storage. + */ + void *storage; + /** + * Custom user data that can be used in the function. + */ + UserData *user_data; +}; + +/** + * Defines the calling convention for a lazy-function. During execution, a lazy-function retrieves + * its inputs and sets the outputs through #Params. + */ +class Params { + public: + /** + * The lazy-function this #Params has been prepared for. + */ + const LazyFunction &fn_; + + public: + Params(const LazyFunction &fn); + + /** + * Get a pointer to an input value if the value is available already. Otherwise null is returned. + * + * The #LazyFunction must leave returned object in an initialized state, but can move from it. + */ + void *try_get_input_data_ptr(int index) const; + + /** + * Same as #try_get_input_data_ptr, but if the data is not yet available, request it. This makes + * sure that the data will be available in a future execution of the #LazyFunction. + */ + void *try_get_input_data_ptr_or_request(int index); + + /** + * Get a pointer to where the output value should be stored. + * The value at the pointer is in an uninitialized state at first. + * The #LazyFunction is responsible for initializing the value. + * After the output has been initialized to its final value, #output_set has to be called. + */ + void *get_output_data_ptr(int index); + + /** + * Call this after the output value is initialized. After this is called, the value must not be + * touched anymore. It may be moved or destructed immediately. + */ + void output_set(int index); + + /** + * Allows the #LazyFunction to check whether an output was computed already without keeping + * track of it itself. + */ + bool output_was_set(int index) const; + + /** + * Can be used to detect which outputs have to be computed. + */ + ValueUsage get_output_usage(int index) const; + + /** + * Tell the caller of the #LazyFunction that a specific input will definitely not be used. + * Only an input that was not #ValueUsage::Used can become unused. + */ + void set_input_unused(int index); + + /** + * Typed utility methods that wrap the methods above. + */ + template<typename T> T extract_input(int index); + template<typename T> const T &get_input(int index); + template<typename T> T *try_get_input_data_ptr_or_request(int index); + template<typename T> void set_output(int index, T &&value); + + /** + * Utility to initialize all outputs that haven't been set yet. + */ + void set_default_remaining_outputs(); + + private: + /** + * Methods that need to be implemented by subclasses. Those are separate from the non-virtual + * methods above to make it easy to insert additional debugging logic on top of the + * implementations. + */ + virtual void *try_get_input_data_ptr_impl(int index) const = 0; + virtual void *try_get_input_data_ptr_or_request_impl(int index) = 0; + virtual void *get_output_data_ptr_impl(int index) = 0; + virtual void output_set_impl(int index) = 0; + virtual bool output_was_set_impl(int index) const = 0; + virtual ValueUsage get_output_usage_impl(int index) const = 0; + virtual void set_input_unused_impl(int index) = 0; +}; + +/** + * Describes an input of a #LazyFunction. + */ +struct Input { + /** + * Name used for debugging purposes. The string has to be static or has to be owned by something + * else. + */ + const char *debug_name; + /** + * Data type of this input. + */ + const CPPType *type; + /** + * Can be used to indicate a caller or this function if this input is used statically before + * executing it the first time. This is technically not needed but can improve efficiency because + * a round-trip through the `execute` method can be avoided. + * + * When this is #ValueUsage::Used, the caller has to ensure that the input is definitely + * available when the #execute method is first called. The #execute method does not have to check + * whether the value is actually available. + */ + ValueUsage usage; + + Input(const char *debug_name, const CPPType &type, const ValueUsage usage = ValueUsage::Used) + : debug_name(debug_name), type(&type), usage(usage) + { + } +}; + +struct Output { + /** + * Name used for debugging purposes. The string has to be static or has to be owned by something + * else. + */ + const char *debug_name; + /** + * Data type of this output. + */ + const CPPType *type = nullptr; + + Output(const char *debug_name, const CPPType &type) : debug_name(debug_name), type(&type) + { + } +}; + +/** + * A function that can compute outputs and request inputs lazily. For more details see the comment + * at the top of the file. + */ +class LazyFunction { + protected: + const char *debug_name_ = "<unknown>"; + Vector<Input> inputs_; + Vector<Output> outputs_; + + public: + virtual ~LazyFunction() = default; + + /** + * Get a name of the function or an input or output. This is mainly used for debugging. + * These are virtual functions because the names are often not used outside of debugging + * workflows. This way the names are only generated when they are actually needed. + */ + virtual std::string name() const; + virtual std::string input_name(int index) const; + virtual std::string output_name(int index) const; + + /** + * Allocates storage for this function. The storage will be passed to every call to #execute. + * If the function does not keep track of any state, this does not have to be implemented. + */ + virtual void *init_storage(LinearAllocator<> &allocator) const; + + /** + * Destruct the storage created in #init_storage. + */ + virtual void destruct_storage(void *storage) const; + + /** + * Inputs of the function. + */ + Span<Input> inputs() const; + /** + * Outputs of the function. + */ + Span<Output> outputs() const; + + /** + * During execution the function retrieves inputs and sets outputs in #params. For some + * functions, this method is called more than once. After execution, the function either has + * computed all required outputs or is waiting for more inputs. + */ + void execute(Params ¶ms, const Context &context) const; + + /** + * Utility to check that the guarantee by #Input::usage is followed. + */ + bool always_used_inputs_available(const Params ¶ms) const; + + private: + /** + * Needs to be implemented by subclasses. This is separate from #execute so that additional + * debugging logic can be implemented in #execute. + */ + virtual void execute_impl(Params ¶ms, const Context &context) const = 0; +}; + +/* -------------------------------------------------------------------- */ +/** \name #LazyFunction Inline Methods + * \{ */ + +inline Span<Input> LazyFunction::inputs() const +{ + return inputs_; +} + +inline Span<Output> LazyFunction::outputs() const +{ + return outputs_; +} + +inline void LazyFunction::execute(Params ¶ms, const Context &context) const +{ + BLI_assert(this->always_used_inputs_available(params)); + this->execute_impl(params, context); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name #Params Inline Methods + * \{ */ + +inline Params::Params(const LazyFunction &fn) : fn_(fn) +{ +} + +inline void *Params::try_get_input_data_ptr(const int index) const +{ + return this->try_get_input_data_ptr_impl(index); +} + +inline void *Params::try_get_input_data_ptr_or_request(const int index) +{ + return this->try_get_input_data_ptr_or_request_impl(index); +} + +inline void *Params::get_output_data_ptr(const int index) +{ + return this->get_output_data_ptr_impl(index); +} + +inline void Params::output_set(const int index) +{ + this->output_set_impl(index); +} + +inline bool Params::output_was_set(const int index) const +{ + return this->output_was_set_impl(index); +} + +inline ValueUsage Params::get_output_usage(const int index) const +{ + return this->get_output_usage_impl(index); +} + +inline void Params::set_input_unused(const int index) +{ + this->set_input_unused_impl(index); +} + +template<typename T> inline T Params::extract_input(const int index) +{ + void *data = this->try_get_input_data_ptr(index); + BLI_assert(data != nullptr); + T return_value = std::move(*static_cast<T *>(data)); + return return_value; +} + +template<typename T> inline const T &Params::get_input(const int index) +{ + const void *data = this->try_get_input_data_ptr(index); + BLI_assert(data != nullptr); + return *static_cast<const T *>(data); +} + +template<typename T> inline T *Params::try_get_input_data_ptr_or_request(const int index) +{ + return static_cast<T *>(this->try_get_input_data_ptr_or_request(index)); +} + +template<typename T> inline void Params::set_output(const int index, T &&value) +{ + using DecayT = std::decay_t<T>; + void *data = this->get_output_data_ptr(index); + new (data) DecayT(std::forward<T>(value)); + this->output_set(index); +} + +/** \} */ + +} // namespace blender::fn::lazy_function |