state_tree.hpp

Go to the documentation of this file.

#pragma once
 
// StateTree — reactive hierarchical key-value store.
// A tree of named properties with typed access, change listeners, RAII
// transactions (coalesced notifications, abort, nesting) and undo recording:
// a transaction begun with an UndoManager becomes one named undo/redo step.
// Alternative to flat StateStore for complex nested state (presets, UI layout, etc.)
 
#include <algorithm>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <map>
#include <memory>
#include <mutex>
#include <optional>
#include <string>
#include <string_view>
#include <variant>
#include <vector>
 
#include <pulp/runtime/result.hpp>
 
namespace pulp::state {

struct PropertyArray;
struct PropertyObject;
 
struct PropertyArrayValue {
    std::shared_ptr<const PropertyArray> storage;
 
    PropertyArrayValue() = default;
    explicit PropertyArrayValue(std::shared_ptr<const PropertyArray> s)
        : storage(std::move(s)) {}
 
    const PropertyArray* get() const noexcept { return storage.get(); }
    explicit operator bool() const noexcept { return static_cast<bool>(storage); }
};
 
struct PropertyObjectValue {
    std::shared_ptr<const PropertyObject> storage;
 
    PropertyObjectValue() = default;
    explicit PropertyObjectValue(std::shared_ptr<const PropertyObject> s)
        : storage(std::move(s)) {}
 
    const PropertyObject* get() const noexcept { return storage.get(); }
    explicit operator bool() const noexcept { return static_cast<bool>(storage); }
};
 
bool operator==(const PropertyArrayValue& a, const PropertyArrayValue& b);
bool operator!=(const PropertyArrayValue& a, const PropertyArrayValue& b);
bool operator==(const PropertyObjectValue& a, const PropertyObjectValue& b);
bool operator!=(const PropertyObjectValue& a, const PropertyObjectValue& b);

using PropertyValue = std::variant<
    std::monostate,  // null/unset
    bool,
    int64_t,
    double,
    std::string,
    PropertyArrayValue,
    PropertyObjectValue
>;
 
struct PropertyArray {
    std::vector<PropertyValue> values;
 
    PropertyArray() = default;
    explicit PropertyArray(std::vector<PropertyValue> v) : values(std::move(v)) {}
    PropertyArray(std::initializer_list<PropertyValue> v) : values(v) {}
};
 
struct PropertyObject {
    using Member = std::pair<std::string, PropertyValue>;
 
    std::map<std::string, PropertyValue, std::less<>> values;
 
    PropertyObject() = default;
    explicit PropertyObject(std::map<std::string, PropertyValue, std::less<>> v)
        : values(std::move(v)) {}
    PropertyObject(std::initializer_list<Member> v) {
        for (const auto& [key, value] : v)
            values.emplace(key, value);
    }
};
 
inline bool operator==(const PropertyArray& a, const PropertyArray& b) {
    return a.values == b.values;
}
 
inline bool operator!=(const PropertyArray& a, const PropertyArray& b) {
    return !(a == b);
}
 
inline bool operator==(const PropertyObject& a, const PropertyObject& b) {
    return a.values == b.values;
}
 
inline bool operator!=(const PropertyObject& a, const PropertyObject& b) {
    return !(a == b);
}
 
inline bool operator==(const PropertyArrayValue& a, const PropertyArrayValue& b) {
    if (a.storage == b.storage) return true;
    if (!a.storage || !b.storage) return false;
    return *a.storage == *b.storage;
}
 
inline bool operator!=(const PropertyArrayValue& a, const PropertyArrayValue& b) {
    return !(a == b);
}
 
inline bool operator==(const PropertyObjectValue& a, const PropertyObjectValue& b) {
    if (a.storage == b.storage) return true;
    if (!a.storage || !b.storage) return false;
    return *a.storage == *b.storage;
}
 
inline bool operator!=(const PropertyObjectValue& a, const PropertyObjectValue& b) {
    return !(a == b);
}
 
inline PropertyValue make_property_array(std::vector<PropertyValue> values) {
    return PropertyArrayValue{
        std::make_shared<const PropertyArray>(PropertyArray{std::move(values)})};
}
 
inline PropertyValue make_property_array(std::initializer_list<PropertyValue> values) {
    return PropertyArrayValue{
        std::make_shared<const PropertyArray>(PropertyArray{values})};
}
 
inline PropertyValue make_property_object(std::map<std::string, PropertyValue, std::less<>> values) {
    return PropertyObjectValue{
        std::make_shared<const PropertyObject>(PropertyObject{std::move(values)})};
}
 
inline PropertyValue make_property_object(
    std::initializer_list<PropertyObject::Member> values) {
    return PropertyObjectValue{
        std::make_shared<const PropertyObject>(PropertyObject{values})};
}
 
inline const PropertyArray* get_property_array(const PropertyValue& value) {
    if (auto* ptr = std::get_if<PropertyArrayValue>(&value))
        return ptr->get();
    return nullptr;
}
 
inline const PropertyObject* get_property_object(const PropertyValue& value) {
    if (auto* ptr = std::get_if<PropertyObjectValue>(&value))
        return ptr->get();
    return nullptr;
}
 
class StateTree;
class UndoManager;

using TreeListener = std::function<void(StateTree& node, std::string_view property,
                                        const PropertyValue& old_val, const PropertyValue& new_val)>;

using ChildListener = std::function<void(StateTree& parent, StateTree& child, int index)>;

using ChildMovedListener =
    std::function<void(StateTree& parent, StateTree& child, int old_index, int new_index)>;

using ParentChangedListener = std::function<void(StateTree& node, StateTree* old_parent)>;

using AncestorChangedListener = std::function<void(StateTree& node)>;

enum class ListenerDelivery {
    kCoalesced,
    kImmediate,
};

enum class TreeEditErrorCode {
    kInvalidName,          
    kMissingProperty,      
    kNullChild,            
    kIndexOutOfRange,      
    kWouldCreateCycle,     
    kTransactionConflict,  
    kRejectedByValidator,  
    kNotInTransaction,     
    kReentrantTransaction, 
    kTransactionClosed,    
};

struct TreeEditError {
    TreeEditErrorCode code;
    std::string message;
};

using TreeEditResult = runtime::Result<std::monostate, TreeEditError>;

using PropertyValidator = std::function<std::optional<std::string>(
    const StateTree& node, std::string_view name, const PropertyValue& value)>;

class StateTree : public std::enable_shared_from_this<StateTree> {
public:
    using Ptr = std::shared_ptr<StateTree>;
 
    class Transaction;
    class ValidatedTransaction;

    static Ptr create(std::string type_name) {
        return Ptr(new StateTree(std::move(type_name)));
    }

    const std::string& type_name() const { return type_name_; }
 
    // ── Properties ──────────────────────────────────────────────────────

    void set(std::string_view name, PropertyValue value);

    TreeEditResult set_checked(std::string_view name, PropertyValue value,
                               const PropertyValidator& validator = {});

    PropertyValue get(std::string_view name) const;

    bool get_bool(std::string_view name, bool default_val = false) const;
    int64_t get_int(std::string_view name, int64_t default_val = 0) const;
    double get_double(std::string_view name, double default_val = 0.0) const;
    std::string get_string(std::string_view name, std::string_view default_val = "") const;

    bool has(std::string_view name) const;

    void remove(std::string_view name);

    TreeEditResult remove_checked(std::string_view name);

    std::vector<std::string> property_names() const;
 
    // ── Children ────────────────────────────────────────────────────────

    void add_child(Ptr child);

    TreeEditResult add_child_checked(Ptr child);

    void insert_child(int index, Ptr child);

    TreeEditResult insert_child_checked(int index, Ptr child);

    void remove_child(int index);

    TreeEditResult remove_child_checked(int index);

    void remove_child(StateTree* child);

    void remove_all_children();

    static bool move_child(StateTree& from_parent, int from_index, StateTree& to_parent,
                           int to_index);

    static TreeEditResult move_child_checked(StateTree& from_parent, int from_index,
                                             StateTree& to_parent, int to_index);

    int child_count() const { return static_cast<int>(children_.size()); }

    Ptr child(int index) const;

    int index_of(const StateTree* node) const;

    Ptr find_child(std::string_view type_name) const;

    std::vector<Ptr> find_children(std::string_view type_name) const;

    void for_each_descendant(const std::function<void(StateTree&)>& fn);

    Ptr find_descendant(const std::function<bool(const StateTree&)>& predicate) const;

    bool is_equivalent_to(const StateTree& other) const;

    StateTree* parent() const { return parent_; }
 
    // ── Transactions ────────────────────────────────────────────────────

    [[nodiscard]] Transaction begin_transaction();

    [[nodiscard]] Transaction begin_transaction(UndoManager* undo, std::string_view name);

    [[nodiscard]] ValidatedTransaction begin_validated_transaction(PropertyValidator validator = {},
                                                                   UndoManager* undo = nullptr,
                                                                   std::string_view name = {});

    bool in_transaction() const;
 
    // ── Listeners ───────────────────────────────────────────────────────

    int add_listener(TreeListener listener,
                     ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    void remove_listener(int id);

    int add_child_added_listener(ChildListener listener,
                                 ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    int add_child_removed_listener(ChildListener listener,
                                   ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    void remove_child_added_listener(int id);
    void remove_child_removed_listener(int id);

    int add_child_moved_listener(ChildMovedListener listener,
                                 ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    void remove_child_moved_listener(int id);

    int add_parent_changed_listener(ParentChangedListener listener,
                                    ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    void remove_parent_changed_listener(int id);

    int add_ancestor_changed_listener(AncestorChangedListener listener,
                                      ListenerDelivery delivery = ListenerDelivery::kCoalesced);
    void remove_ancestor_changed_listener(int id);
 
    // ── Serialization ───────────────────────────────────────────────────

    std::string to_json() const;

    static Ptr from_json(std::string_view json);
 
    // ── Deep copy ───────────────────────────────────────────────────────

    Ptr deep_copy() const;
 
    // ── Synchronized clone (single-process) ─────────────────────────────

    class SyncedClone;
    SyncedClone clone_synced();
 
private:
    explicit StateTree(std::string type_name) : type_name_(std::move(type_name)) {}
 
    struct TxState;
    struct Edit;
    struct Pending;
    enum class Pass { kAll, kImmediate, kCoalesced };
 
    template <typename Fn> struct Slot {
        int id;
        Fn fn;
        ListenerDelivery delivery;
    };
 
    std::string type_name_;
    std::map<std::string, PropertyValue, std::less<>> properties_;
    std::vector<Ptr> children_;
    StateTree* parent_ = nullptr;
 
    std::vector<Slot<TreeListener>> listeners_;
    std::vector<Slot<ChildListener>> child_added_listeners_;
    std::vector<Slot<ChildListener>> child_removed_listeners_;
    std::vector<Slot<ChildMovedListener>> child_moved_listeners_;
    std::vector<Slot<ParentChangedListener>> parent_changed_listeners_;
    std::vector<Slot<AncestorChangedListener>> ancestor_changed_listeners_;
    int next_listener_id_ = 0;
 
    // Open transaction owned by this node (when it is the tree it was begun
    // on) or held by it (when it was detached while a transaction was open).
    std::shared_ptr<TxState> tx_;
    // Non-zero while this node's transaction is delivering its commit burst.
    int flushing_ = 0;
 
    template <typename Fn>
    int add_slot(std::vector<Slot<Fn>>& slots, Fn fn, ListenerDelivery delivery);
    template <typename Fn> static void remove_slot(std::vector<Slot<Fn>>& slots, int id);
    template <typename Fn, typename... Args>
    static void dispatch(std::vector<Slot<Fn>>& slots, Pass pass, Args&... args);
 
    std::shared_ptr<TxState> active_tx() const;
    bool flush_in_progress() const;
    static TreeEditResult check_tx(const StateTree* a, const StateTree* b);
 
    void apply_property(std::string_view name, std::optional<PropertyValue> value);
    static void relocate(const Ptr& child, StateTree* to, int to_index, bool reorder_event);
    static void place(const Ptr& child, StateTree* to, int to_index);
    static void replay(const Edit& edit, bool forward);
    static void replay_log(const std::vector<Edit>& log, const Ptr& owner, bool forward);
    static void emit(Pending pending, TxState* tx);
    static void deliver(const Pending& pending, Pass pass);
    static void finish(std::shared_ptr<TxState> state);
 
    // True if this node is `node` or one of its ancestors (walks `node`'s
    // parent chain upward). Used by add_child / insert_child / move_child to
    // reject parent/child cycles before they can form.
    bool is_ancestor_of(const StateTree* node) const;
};

class StateTree::Transaction {
  public:
    Transaction() = default;
    Transaction(Transaction&& other) noexcept;
    Transaction& operator=(Transaction&& other) noexcept;
    Transaction(const Transaction&) = delete;
    Transaction& operator=(const Transaction&) = delete;
    ~Transaction();

    void commit();

    bool abort();

    bool is_active() const {
        return active_;
    }
 
  private:
    friend class StateTree;
    friend class StateTree::ValidatedTransaction;
    Transaction(std::shared_ptr<TxState> state, size_t edit_mark, size_t pending_mark)
        : state_(std::move(state)), edit_mark_(edit_mark), pending_mark_(pending_mark),
          active_(true) {}
    void end();
 
    std::shared_ptr<TxState> state_;
    size_t edit_mark_ = 0;
    size_t pending_mark_ = 0;
    bool active_ = false;
};

class StateTree::ValidatedTransaction {
  public:
    ValidatedTransaction(ValidatedTransaction&& other) noexcept = default;
    ValidatedTransaction& operator=(ValidatedTransaction&& other) noexcept;
    ValidatedTransaction(const ValidatedTransaction&) = delete;
    ValidatedTransaction& operator=(const ValidatedTransaction&) = delete;
    ~ValidatedTransaction();
 
    TreeEditResult set(StateTree& node, std::string_view name, PropertyValue value);
    TreeEditResult remove(StateTree& node, std::string_view name);
    TreeEditResult add_child(StateTree& parent, Ptr child);
    TreeEditResult insert_child(StateTree& parent, int index, Ptr child);
    TreeEditResult remove_child(StateTree& parent, int index);
    TreeEditResult move_child(StateTree& from_parent, int from_index, StateTree& to_parent,
                              int to_index);

    TreeEditResult commit();

    bool abort();
 
    bool is_active() const {
        return tx_.is_active();
    }
    bool has_error() const {
        return first_error_.has_value();
    }
    const std::optional<TreeEditError>& first_error() const {
        return first_error_;
    }
 
  private:
    friend class StateTree;
    ValidatedTransaction(Transaction tx, PropertyValidator validator, bool reentrant)
        : tx_(std::move(tx)), validator_(std::move(validator)), reentrant_(reentrant) {}
 
    TreeEditResult guard(std::initializer_list<const StateTree*> nodes) const;
    TreeEditResult note(TreeEditResult result);
 
    Transaction tx_;
    PropertyValidator validator_;
    std::optional<TreeEditError> first_error_;
    bool reentrant_ = false;
};

class StateTree::SyncedClone {
public:
    SyncedClone(SyncedClone&&) noexcept;
    SyncedClone& operator=(SyncedClone&&) noexcept;
    SyncedClone(const SyncedClone&) = delete;
    SyncedClone& operator=(const SyncedClone&) = delete;
    ~SyncedClone();

    const StateTree::Ptr& clone() const { return clone_; }

    void detach();

    bool is_attached() const { return attached_; }
 
private:
    friend class StateTree;
 
    SyncedClone(StateTree::Ptr source, StateTree::Ptr cloned);
 
    void attach_recursive(StateTree& src, StateTree& dst);
    void detach_recursive(StateTree& src);
 
    // Weak handle to the source node. When the source subtree is
    // removed via `remove_child` and no other shared_ptr keeps it
    // alive, `lock()` returns null so `detach()` skips deregistration
    // safely instead of dereferencing a dangling raw pointer.
    // Pinned by the SyncedClone destructor-safety regression test.
    struct WiringEntry {
        std::weak_ptr<StateTree> source;
        int prop_listener_id;
        int child_added_listener_id;
        int child_removed_listener_id;
        int child_moved_listener_id;
    };
 
    StateTree::Ptr source_;
    StateTree::Ptr clone_;
    std::vector<WiringEntry> wiring_;
    bool attached_ = true;
};

template<typename T>
class ObservableValue {
public:
    ObservableValue() = default;
    explicit ObservableValue(T initial) : value_(std::move(initial)) {}
 
    const T& get() const { return value_; }
    operator const T&() const { return value_; }
 
    void set(T new_value) {
        if (value_ != new_value) {
            T old = std::move(value_);
            value_ = std::move(new_value);
            // Snapshot-then-dispatch with a liveness recheck, mirroring
            // StateTree's listener fan-out: a callback may add or remove
            // listeners on this same value while it runs, which would
            // invalidate iterators into the live vector. A listener removed
            // earlier in the same dispatch is skipped; one added during the
            // dispatch is not invoked for the in-flight set. The single-
            // listener fast path copies the callable before invoking so a
            // self-removing sole listener can't free its own executing body.
            if (listeners_.size() == 1) {
                auto fn = listeners_.front().second;
                if (fn) fn(old, value_);
                return;
            }
            auto snapshot = listeners_;
            for (auto& [id, fn] : snapshot) {
                if (!fn) continue;
                bool still_registered = std::any_of(
                    listeners_.begin(), listeners_.end(),
                    [id = id](const auto& e) { return e.first == id; });
                if (still_registered) fn(old, value_);
            }
        }
    }
 
    ObservableValue& operator=(T new_value) {
        set(std::move(new_value));
        return *this;
    }
 
    using ChangeListener = std::function<void(const T& old_val, const T& new_val)>;
 
    int add_listener(ChangeListener fn) {
        int id = next_id_++;
        listeners_.push_back({id, std::move(fn)});
        return id;
    }
 
    void remove_listener(int id) {
        listeners_.erase(
            std::remove_if(listeners_.begin(), listeners_.end(),
                          [id](auto& p) { return p.first == id; }),
            listeners_.end());
    }
 
private:
    T value_{};
    std::vector<std::pair<int, ChangeListener>> listeners_;
    int next_id_ = 0;
};
 
}  // namespace pulp::state