freya_core/

runner.rs

use std::{
    any::{
        Any,
        TypeId,
    },
    cell::RefCell,
    cmp::Ordering,
    collections::VecDeque,
    fmt::Debug,
    rc::Rc,
    sync::atomic::AtomicU64,
};

use futures_lite::{
    FutureExt,
    StreamExt,
};
use itertools::Itertools;
use pathgraph::PathGraph;
use rustc_hash::{
    FxHashMap,
    FxHashSet,
};
use tiny_diff::DiffNode;

use crate::{
    current_context::CurrentContext,
    diff_key::DiffKey,
    element::{
        Element,
        ElementExt,
        EventHandlerType,
    },
    events::{
        data::{
            Event,
            EventType,
        },
        name::EventName,
    },
    node_id::NodeId,
    path_element::PathElement,
    prelude::{
        Task,
        TaskId,
    },
    reactive_context::ReactiveContext,
    scope::{
        PathNode,
        Scope,
        ScopeStorage,
    },
    scope_id::ScopeId,
    tree::DiffModifies,
};

#[derive(Debug, PartialEq, Eq)]
pub enum MutationRemove {
    /// Because elements always have a different parent we can easily get their position relatively to their parent
    Element { id: NodeId, index: u32 },
    /// In the other hand, roots of Scopes are manually connected to their parent scopes, so getting their index is not worth the effort.
    Scope { id: NodeId },
}

impl PartialOrd for MutationRemove {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for MutationRemove {
    fn cmp(&self, other: &Self) -> Ordering {
        use MutationRemove::*;
        match (self, other) {
            // Order Element removals by index descending (so larger indices come first)
            (Element { index: a, .. }, Element { index: b, .. }) => b.cmp(a),
            // Elements come before Scopes
            (Element { .. }, Scope { .. }) => Ordering::Less,
            (Scope { .. }, Element { .. }) => Ordering::Greater,
            // Order Scopes by id descending as well
            (Scope { id: a }, Scope { id: b }) => b.cmp(a),
        }
    }
}

impl MutationRemove {
    pub fn node_id(&self) -> NodeId {
        match self {
            Self::Element { id, .. } => *id,
            Self::Scope { id } => *id,
        }
    }
}

pub struct MutationAdd {
    pub node_id: NodeId,
    pub parent_id: NodeId,
    pub index: u32,
    pub element: Rc<dyn ElementExt>,
}

pub struct MutationModified {
    pub node_id: NodeId,
    pub element: Rc<dyn ElementExt>,
    pub flags: DiffModifies,
}

#[derive(Default)]
pub struct Mutations {
    /// New elements and their final sibling indices, inserted after removals.
    pub added: Vec<MutationAdd>,
    /// Updated elements and the flags identifying which states need refreshing.
    pub modified: Vec<MutationModified>,
    /// Elements and scope roots to remove before additions and reordering.
    pub removed: Vec<MutationRemove>,
    /// Final child order for reordered parents, applied after removals and additions.
    pub moved: FxHashMap<NodeId, Vec<NodeId>>,
}

impl Mutations {
    pub fn is_empty(&self) -> bool {
        self.added.is_empty()
            && self.modified.is_empty()
            && self.removed.is_empty()
            && self.moved.is_empty()
    }
}

impl Debug for Mutations {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_fmt(format_args!(
            "Added: {:?} Modified: {:?} Removed: {:?} Moved: {:?}",
            self.added
                .iter()
                .map(|m| (m.node_id, m.parent_id, m.index))
                .collect::<Vec<_>>(),
            self.modified.iter().map(|m| m.node_id).collect::<Vec<_>>(),
            self.removed,
            self.moved
        ))
    }
}

pub enum Message {
    MarkScopeAsDirty(ScopeId),
    PollTask(TaskId),
}

/// Reported around every batch of dirty tasks polled by the [Runner].
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum TasksPollStage {
    Started,
    Finished,
}

/// Parents receiving additions, keyed by new tree path, with their lazily found current path.
type AdditionParents = FxHashMap<Box<[u32]>, (NodeId, Option<Vec<u32>>)>;

type ReorderedParents = FxHashMap<NodeId, Box<[u32]>>;

pub struct Runner {
    pub scopes: FxHashMap<ScopeId, Rc<RefCell<Scope>>>,
    pub scopes_storages: Rc<RefCell<FxHashMap<ScopeId, ScopeStorage>>>,

    pub(crate) dirty_scopes: FxHashSet<ScopeId>,
    pub(crate) dirty_tasks: VecDeque<TaskId>,

    pub node_to_scope: FxHashMap<NodeId, ScopeId>,

    pub(crate) node_id_counter: NodeId,
    pub(crate) scope_id_counter: ScopeId,
    pub(crate) task_id_counter: Rc<AtomicU64>,

    pub(crate) tasks: Rc<RefCell<FxHashMap<TaskId, Rc<RefCell<Task>>>>>,

    pub(crate) sender: futures_channel::mpsc::UnboundedSender<Message>,
    pub(crate) receiver: futures_channel::mpsc::UnboundedReceiver<Message>,
}

impl Debug for Runner {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("Runner")
            .field("dirty_scopes", &self.dirty_scopes.len())
            .field("dirty_tasks", &self.dirty_tasks.len())
            .field("node_to_scope", &self.node_to_scope.len())
            .field("scopes", &self.scopes.len())
            .field("scopes_storages", &self.scopes_storages.borrow().len())
            .field("tasks", &self.tasks.borrow().len())
            .finish()
    }
}

impl Drop for Runner {
    fn drop(&mut self) {
        // Drop scopes from deepest to shallowest.
        for (scope_id, _scope) in self
            .scopes
            .drain()
            .sorted_by_key(|s| s.1.borrow().height)
            .rev()
        {
            CurrentContext::run_with_reactive(self.create_context(scope_id), || {
                let mut removed_tasks = Vec::new();

                self.tasks.borrow_mut().retain(|task_id, task| {
                    if task.borrow().scope_id == scope_id {
                        removed_tasks.push((*task_id, task.clone()));
                        false
                    } else {
                        true
                    }
                });
                drop(removed_tasks);
                let _scope = self.scopes_storages.borrow_mut().remove(&scope_id);
            });
        }
    }
}

impl Runner {
    pub fn new(root: impl Fn() -> Element + 'static) -> Self {
        let (sender, receiver) = futures_channel::mpsc::unbounded::<Message>();
        Self {
            scopes: FxHashMap::from_iter([(
                ScopeId::ROOT,
                Rc::new(RefCell::new(Scope {
                    parent_node_id_in_parent: NodeId::ROOT,
                    path_in_parent: Box::from([]),
                    height: 0,
                    parent_id: None,
                    id: ScopeId::ROOT,
                    key: DiffKey::Root,
                    comp: Rc::new(move |_| root()),
                    props: Rc::new(()),
                    element: None,
                    nodes: {
                        let mut map = PathGraph::new();
                        map.insert(
                            &[],
                            PathNode {
                                node_id: NodeId::ROOT,
                                scope_id: None,
                            },
                        );
                        map
                    },
                })),
            )]),
            scopes_storages: Rc::new(RefCell::new(FxHashMap::from_iter([(
                ScopeId::ROOT,
                ScopeStorage::new(None, |writer| {
                    ReactiveContext::new_for_scope(sender.clone(), ScopeId::ROOT, writer)
                }),
            )]))),

            node_to_scope: FxHashMap::from_iter([(NodeId::ROOT, ScopeId::ROOT)]),

            node_id_counter: NodeId::ROOT,
            scope_id_counter: ScopeId::ROOT,
            task_id_counter: Rc::default(),

            dirty_tasks: VecDeque::default(),
            dirty_scopes: FxHashSet::from_iter([ScopeId::ROOT]),

            tasks: Rc::default(),

            sender,
            receiver,
        }
    }

    #[cfg(all(debug_assertions, feature = "debug-integrity"))]
    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub fn verify_scopes_integrity(&self) {
        let mut visited = FxHashSet::default();
        let size = self.scopes.len();
        let mut buffer = vec![ScopeId::ROOT];
        while let Some(scope_id) = buffer.pop() {
            if visited.contains(&scope_id) {
                continue;
            }
            visited.insert(scope_id);
            let scope = self.scopes.get(&scope_id).unwrap();
            let scope = scope.borrow();
            if let Some(parent) = scope.parent_id {
                buffer.push(parent);
            }
            scope.nodes.traverse(&[], |_, &PathNode { scope_id, .. }| {
                if let Some(scope_id) = scope_id {
                    buffer.push(scope_id);
                }
            });
        }
        assert_eq!(size, visited.len())
    }

    fn create_context(&self, scope_id: ScopeId) -> CurrentContext {
        CurrentContext {
            scope_id,
            scopes_storages: self.scopes_storages.clone(),
            tasks: self.tasks.clone(),
            task_id_counter: self.task_id_counter.clone(),
            sender: self.sender.clone(),
        }
    }

    pub fn with_root_context<T>(&self, run: impl FnOnce() -> T) -> T {
        self.run_in(run)
    }

    pub fn provide_root_context<T: 'static + Clone>(&mut self, context: impl FnOnce() -> T) -> T {
        self.run_in(|| {
            let context = context();
            let mut scopes_storages = self.scopes_storages.borrow_mut();
            let root_scope_storage = scopes_storages.get_mut(&ScopeId::ROOT).unwrap();
            root_scope_storage
                .contexts
                .insert(TypeId::of::<T>(), Rc::new(context.clone()));

            context
        })
    }

    /// Dispatches an event, returning whether its default action remains enabled.
    /// Missing nodes are ignored without cancelling other queued events.
    pub fn handle_event(
        &mut self,
        node_id: impl Into<NodeId>,
        event_name: EventName,
        event_type: EventType,
        bubbles: bool,
    ) -> bool {
        let node_id = node_id.into();
        #[cfg(debug_assertions)]
        tracing::info!("Handling event {event_name:?} for {node_id:?}");
        let propagate = Rc::new(RefCell::new(bubbles));
        let default = Rc::new(RefCell::new(true));

        let Some(scope_id) = self.node_to_scope.get(&node_id) else {
            return true;
        };
        let Some(path) = self
            .scopes
            .get(scope_id)
            .unwrap()
            .borrow()
            .nodes
            .find_path(|value| {
                value
                    == Some(&PathNode {
                        node_id,
                        scope_id: None,
                    })
            })
        else {
            return true;
        };

        let mut current_target = Some((path, *scope_id));
        while let Some((path, scope_id)) = current_target.take() {
            let scope = self.scopes.get(&scope_id).cloned().unwrap();
            scope.borrow().with_element(&path, |element| {
                match element {
                    PathElement::Component { .. } => {
                        unreachable!()
                    }
                    PathElement::Element { element, .. } => {
                        CurrentContext::run(self.create_context(scope_id), || {
                            match &event_type {
                                EventType::AccessibilityAction(data) => {
                                    if let Some(event_handlers) = element.events_handlers()
                                        && let Some(EventHandlerType::AccessibilityAction(handler)) =
                                            event_handlers.get(&event_name)
                                    {
                                        handler.call(Event {
                                            data: data.clone(),
                                            propagate: propagate.clone(),
                                            default: default.clone(),
                                        });
                                    }
                                }
                                EventType::Mouse(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Mouse(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Keyboard(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Keyboard(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Sized(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Sized(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Visible(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Visible(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Styled(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Styled(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Wheel(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Wheel(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Touch(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Touch(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::Pointer(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::Pointer(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::File(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::File(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                                EventType::ImePreedit(data) => {
                                    let event_handlers = element.events_handlers();
                                    if let Some(event_handlers) = event_handlers {
                                        match event_handlers.get(&event_name) {
                                            Some(EventHandlerType::ImePreedit(handler)) => {
                                                handler.call(Event {
                                                    data: data.clone(),
                                                    propagate: propagate.clone(),
                                                    default: default.clone(),
                                                });
                                            }
                                            Some(_) => unreachable!(),
                                            _ => {}
                                        }
                                    }
                                }
                            }

                            // Bubble up if desired
                            if *propagate.borrow() {
                                if path.len() > 1 {
                                    // Change the target to this element parent (still in the same Scope)
                                    current_target
                                        .replace((path[..path.len() - 1].to_vec(), scope_id));
                                } else {
                                    let mut parent_scope_id = scope.borrow().parent_id;
                                    // Otherwise change the target to this element parent in the parent Scope
                                    loop {
                                        if let Some(parent_id) = parent_scope_id.take() {
                                            let parent_scope = self.scopes.get(&parent_id).unwrap();
                                            let path =
                                                parent_scope.borrow().nodes.find_path(|value| {
                                                    value
                                                        == Some(&PathNode {
                                                            node_id: scope
                                                                .borrow()
                                                                .parent_node_id_in_parent,
                                                            scope_id: None,
                                                        })
                                                });
                                            if let Some(path) = path {
                                                current_target.replace((path, parent_id));
                                                break;
                                            } else {
                                                parent_scope_id = parent_scope.borrow().parent_id;
                                            }
                                        } else {
                                            return;
                                        }
                                    }
                                }
                            }
                        })
                    }
                }
            });
        }
        *default.borrow()
    }

    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub async fn handle_events(&mut self) {
        self.handle_events_with(&mut |_| {}).await
    }

    /// Like [Self::handle_events], notifying the observer around every tasks polling batch.
    pub async fn handle_events_with(&mut self, observer: &mut dyn FnMut(TasksPollStage)) {
        loop {
            while let Ok(msg) = self.receiver.try_recv() {
                match msg {
                    Message::MarkScopeAsDirty(scope_id) => {
                        self.dirty_scopes.insert(scope_id);
                    }
                    Message::PollTask(task_id) => {
                        self.dirty_tasks.push_back(task_id);
                    }
                }
            }

            if !self.dirty_scopes.is_empty() {
                return;
            }

            self.poll_dirty_tasks(observer);

            if !self.dirty_scopes.is_empty() {
                return;
            }

            let Some(msg) = self.receiver.next().await else {
                return;
            };
            match msg {
                Message::MarkScopeAsDirty(scope_id) => {
                    self.dirty_scopes.insert(scope_id);
                }
                Message::PollTask(task_id) => {
                    self.dirty_tasks.push_back(task_id);
                }
            }
        }
    }

    /// Like [Self::handle_events], but returns instead of waiting for more work.
    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub fn handle_events_immediately(&mut self) {
        self.handle_events_immediately_with(&mut |_| {})
    }

    /// Like [Self::handle_events_immediately], notifying the observer around every tasks polling
    /// batch.
    ///
    /// Tasks are polled even when there are dirty scopes, otherwise a constant flow of events
    /// would starve them.
    pub fn handle_events_immediately_with(&mut self, observer: &mut dyn FnMut(TasksPollStage)) {
        while let Ok(msg) = self.receiver.try_recv() {
            match msg {
                Message::MarkScopeAsDirty(scope_id) => {
                    self.dirty_scopes.insert(scope_id);
                }
                Message::PollTask(task_id) => {
                    self.dirty_tasks.push_back(task_id);
                }
            }
        }

        self.poll_dirty_tasks(observer);
    }

    /// Poll the dirty tasks, notifying the observer around the batch.
    fn poll_dirty_tasks(&mut self, observer: &mut dyn FnMut(TasksPollStage)) {
        if self.dirty_tasks.is_empty() {
            return;
        }

        observer(TasksPollStage::Started);

        while let Some(task_id) = self.dirty_tasks.pop_front() {
            let Some(task) = self.tasks.borrow().get(&task_id).cloned() else {
                continue;
            };
            let mut task = task.borrow_mut();
            let waker = task.waker.clone();

            let mut cx = std::task::Context::from_waker(&waker);

            CurrentContext::run(
                {
                    let Some(scope) = self.scopes.get(&task.scope_id) else {
                        continue;
                    };
                    self.create_context(scope.borrow().id)
                },
                || {
                    let poll_result = task.future.poll(&mut cx);
                    if poll_result.is_ready() {
                        let _ = self.tasks.borrow_mut().remove(&task_id);
                    }
                },
            );
        }

        observer(TasksPollStage::Finished);
    }

    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    pub fn sync_and_update(&mut self) -> Mutations {
        self.handle_events_immediately();
        use itertools::Itertools;

        // No need to check anything
        if self.dirty_scopes.is_empty() {
            return Mutations::default();
        }

        #[cfg(all(debug_assertions, feature = "debug-integrity"))]
        self.verify_scopes_integrity();

        let mut mutations = Mutations::default();
        let mut pending_reorders = FxHashMap::default();

        let dirty_scopes = self
            .dirty_scopes
            .drain()
            .filter_map(|id| self.scopes.get(&id).cloned())
            .sorted_by_key(|s| s.borrow().height)
            .map(|s| s.borrow().id)
            .collect::<Box<[_]>>();

        let mut visited_scopes = FxHashSet::default();

        for scope_id in dirty_scopes {
            // No need to run scopes more than once
            if visited_scopes.contains(&scope_id) {
                continue;
            }

            let Some(scope_rc) = self.scopes.get(&scope_id).cloned() else {
                continue;
            };

            let scope_id = scope_rc.borrow().id;

            let element = CurrentContext::run_with_reactive(self.create_context(scope_id), || {
                let scope = scope_rc.borrow();
                #[cfg(feature = "hotreload")]
                {
                    subsecond::call(|| (scope.comp)(scope.props.clone()))
                }
                #[cfg(not(feature = "hotreload"))]
                {
                    (scope.comp)(scope.props.clone())
                }
            });

            let path_element = PathElement::from_element(vec![0], element);
            let mut diff = Diff::default();
            path_element.diff(scope_rc.borrow().element.as_ref(), &mut diff);

            self.apply_diff(
                &scope_rc,
                diff,
                &mut mutations,
                &path_element,
                &mut pending_reorders,
            );

            self.run_scope(
                &scope_rc,
                &path_element,
                &mut mutations,
                &mut visited_scopes,
                &mut pending_reorders,
            );

            let mut scopes_storages = self.scopes_storages.borrow_mut();
            let scope_storage = scopes_storages.get_mut(&scope_rc.borrow().id).unwrap();
            scope_storage.current_value = 0;
            scope_storage.current_run += 1;

            scope_rc.borrow_mut().element = Some(path_element);
        }

        // Collect final child orders after all scopes render, including replaced component roots.
        for (parent_node_id, path) in pending_reorders {
            let Some(scope_id) = self.node_to_scope.get(&parent_node_id) else {
                continue;
            };
            let scope = self.scopes[scope_id].borrow();
            let mut children = Vec::with_capacity(scope.nodes.len(&path).unwrap_or_default());
            scope.nodes.traverse_1_level(&path, |_, node| {
                children.push(match node.scope_id {
                    Some(scope_id) => self.find_scope_root_node_id(scope_id),
                    None => node.node_id,
                });
            });
            mutations.moved.insert(parent_node_id, children);
        }

        mutations
    }

    pub fn run_in<T>(&self, run: impl FnOnce() -> T) -> T {
        CurrentContext::run(self.create_context(ScopeId::ROOT), run)
    }

    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    fn run_scope(
        &mut self,
        scope: &Rc<RefCell<Scope>>,
        element: &PathElement,
        mutations: &mut Mutations,
        visited_scopes: &mut FxHashSet<ScopeId>,
        pending_reorders: &mut ReorderedParents,
    ) {
        visited_scopes.insert(scope.borrow().id);
        match element {
            PathElement::Component {
                comp,
                props,
                key,
                path,
            } => {
                // Safe to unwrap because this is a component
                let assigned_scope_id = scope
                    .borrow()
                    .nodes
                    .get(path)
                    .and_then(|path_node| path_node.scope_id)
                    .unwrap();

                let parent_node_id = if path.as_ref() == [0] {
                    scope.borrow().parent_node_id_in_parent
                } else {
                    scope
                        .borrow()
                        .nodes
                        .get(&path[..path.len() - 1])
                        .unwrap()
                        .node_id
                };

                if let Some(Ok(mut existing_scope)) = self
                    .scopes
                    .get(&assigned_scope_id)
                    .map(|s| s.try_borrow_mut())
                {
                    let key_changed = existing_scope.key != *key;
                    // Colliding keys can pair components of different types, which requires a full reset
                    let type_changed = (existing_scope.props.as_ref() as &dyn Any).type_id()
                        != (props.as_ref() as &dyn Any).type_id();
                    if key_changed || type_changed || existing_scope.props.changed(props.as_ref()) {
                        self.dirty_scopes.insert(assigned_scope_id);
                        existing_scope.props = props.clone();

                        if key_changed || type_changed {
                            existing_scope.key = key.clone();
                            existing_scope.comp = comp.clone();
                            self.scopes_storages
                                .borrow_mut()
                                .get_mut(&assigned_scope_id)
                                .unwrap()
                                .reset();
                        }
                    }
                } else {
                    self.scopes.insert(
                        assigned_scope_id,
                        Rc::new(RefCell::new(Scope {
                            parent_node_id_in_parent: parent_node_id,
                            path_in_parent: path.clone(),
                            height: scope.borrow().height + 1,
                            parent_id: Some(scope.borrow().id),
                            id: assigned_scope_id,
                            key: key.clone(),
                            comp: comp.clone(),
                            props: props.clone(),
                            element: None,
                            nodes: PathGraph::default(),
                        })),
                    );
                    self.scopes_storages.borrow_mut().insert(
                        assigned_scope_id,
                        ScopeStorage::new(Some(scope.borrow().id), |writer| {
                            ReactiveContext::new_for_scope(
                                self.sender.clone(),
                                assigned_scope_id,
                                writer,
                            )
                        }),
                    );
                    self.dirty_scopes.insert(assigned_scope_id);
                }

                let was_dirty = self.dirty_scopes.remove(&assigned_scope_id);

                if !was_dirty {
                    // No need to rerun scope if it is not dirty
                    return;
                }

                let scope_rc = self.scopes.get(&assigned_scope_id).cloned().unwrap();

                let element = hotpath::measure_block!("Scope Rendering", {
                    CurrentContext::run_with_reactive(
                        self.create_context(assigned_scope_id),
                        || {
                            let scope = scope_rc.borrow();
                            #[cfg(feature = "hotreload")]
                            {
                                subsecond::call(|| (scope.comp)(scope.props.clone()))
                            }
                            #[cfg(not(feature = "hotreload"))]
                            {
                                (scope.comp)(scope.props.clone())
                            }
                        },
                    )
                });

                let path_element = PathElement::from_element(vec![0], element);
                let mut diff = Diff::default();
                path_element.diff(scope_rc.borrow().element.as_ref(), &mut diff);

                self.apply_diff(&scope_rc, diff, mutations, &path_element, pending_reorders);

                self.run_scope(
                    &scope_rc,
                    &path_element,
                    mutations,
                    visited_scopes,
                    pending_reorders,
                );
                let mut scopes_storages = self.scopes_storages.borrow_mut();
                let scope_storage = scopes_storages.get_mut(&assigned_scope_id).unwrap();
                scope_storage.current_value = 0;
                scope_storage.current_run += 1;

                scope_rc.borrow_mut().element = Some(path_element);
            }
            PathElement::Element { elements, .. } => {
                for element in elements.iter() {
                    self.run_scope(scope, element, mutations, visited_scopes, pending_reorders);
                }
            }
        }
    }

    /// Recursively traverse up in the scopes tree until a suitable (non-root) slot is found to put an element.
    /// Returns a parent node id and a slot index pointing to one of its children.
    fn find_scope_root_parent_info(
        &self,
        parent_id: Option<ScopeId>,
        parent_node_id: NodeId,
        scope_id: ScopeId,
    ) -> (NodeId, u32) {
        let mut index_inside_parent = 0;

        if let Some(parent_id) = parent_id {
            let mut buffer = Some((parent_id, parent_node_id, scope_id));
            while let Some((parent_id, parent_node_id, scope_id)) = buffer.take() {
                let parent_scope = self.scopes.get(&parent_id).unwrap();
                let parent_scope = parent_scope.borrow();

                let scope = self.scopes.get(&scope_id).unwrap();
                let scope = scope.borrow();

                let path_node_parent = parent_scope.nodes.find(|v| {
                    if let Some(v) = v {
                        v.node_id == parent_node_id
                    } else {
                        false
                    }
                });

                if let Some(path_node_parent) = path_node_parent {
                    if let Some(scope_id) = path_node_parent.scope_id {
                        if let Some(parent_id) = parent_scope.parent_id {
                            // The found element turns out to be a component so go to it to continue looking
                            buffer.replace((
                                parent_id,
                                parent_scope.parent_node_id_in_parent,
                                scope_id,
                            ));
                        } else {
                            assert_eq!(scope_id, ScopeId::ROOT);
                        }
                    } else {
                        // Found an Element parent so we get the index from the path
                        index_inside_parent = *scope.path_in_parent.last().unwrap();
                        return (parent_node_id, index_inside_parent);
                    }
                } else if let Some(new_parent_id) = parent_scope.parent_id {
                    // If no element was found we go to the parent scope
                    buffer.replace((
                        new_parent_id,
                        parent_scope.parent_node_id_in_parent,
                        parent_id,
                    ));
                }
            }
        } else {
            assert_eq!(scope_id, ScopeId::ROOT);
        }

        (parent_node_id, index_inside_parent)
    }

    /// Recursively finds the root element [NodeId] of a scope.
    /// When a scope's first child is another component (scope), this follows
    /// the chain until it finds the first actual element.
    fn find_scope_root_node_id(&self, scope_id: ScopeId) -> NodeId {
        let scope_rc = self.scopes.get(&scope_id).unwrap();
        let scope = scope_rc.borrow();
        let path_node = scope.nodes.get(&[0]).unwrap();
        if let Some(child_scope_id) = path_node.scope_id {
            self.find_scope_root_node_id(child_scope_id)
        } else {
            path_node.node_id
        }
    }

    /// Inserts an added node in `scope.nodes` and emits the matching mutation. Parents are
    /// resolved by identity because paths in `scope.nodes` shift while a diff is applied.
    fn process_addition(
        &mut self,
        scope: &Rc<RefCell<Scope>>,
        added: &[u32],
        path_element: &PathElement,
        mutations: &mut Mutations,
        parents_to_resync_scopes: &mut FxHashSet<Box<[u32]>>,
        addition_parents: &mut AdditionParents,
    ) {
        let (parent_node_id, index_inside_parent, insertion_path) = if added == [0] {
            let parent_id = scope.borrow().parent_id;
            let scope_id = scope.borrow().id;
            let parent_node_id = scope.borrow().parent_node_id_in_parent;
            let (parent_node_id, index_inside_parent) =
                self.find_scope_root_parent_info(parent_id, parent_node_id, scope_id);
            (parent_node_id, index_inside_parent, vec![0])
        } else {
            let parent_path = &added[..added.len() - 1];
            parents_to_resync_scopes.insert(Box::from(parent_path));

            let (parent_node_id, cached_path) = addition_parents.get_mut(parent_path).unwrap();
            let parent_node_id = *parent_node_id;

            // Pre existing parents are found once and cached, added parents get cached on insertion
            let mut insertion_path = cached_path
                .get_or_insert_with(|| {
                    // The parent usually already sits at its new path, search only if it shifted
                    let is_at_new_path = scope
                        .borrow()
                        .nodes
                        .get(parent_path)
                        .is_some_and(|node| node.node_id == parent_node_id);
                    if is_at_new_path {
                        parent_path.to_vec()
                    } else {
                        scope
                            .borrow()
                            .nodes
                            .find_path(|v| v.is_some_and(|node| node.node_id == parent_node_id))
                            .unwrap()
                    }
                })
                .clone();
            insertion_path.push(added[added.len() - 1]);
            (parent_node_id, added[added.len() - 1], insertion_path)
        };

        self.node_id_counter += 1;

        path_element.with_element(added, |element| {
            let scope_id = match element {
                PathElement::Component { .. } => {
                    self.scope_id_counter += 1;
                    Some(self.scope_id_counter)
                }
                PathElement::Element { element, .. } => {
                    mutations.added.push(MutationAdd {
                        node_id: self.node_id_counter,
                        parent_id: parent_node_id,
                        index: index_inside_parent,
                        element: element.clone(),
                    });
                    self.node_to_scope
                        .insert(self.node_id_counter, scope.borrow().id);
                    None
                }
            };

            scope.borrow_mut().nodes.insert(
                &insertion_path,
                PathNode {
                    node_id: self.node_id_counter,
                    scope_id,
                },
            );
            addition_parents.insert(
                Box::from(added),
                (self.node_id_counter, Some(insertion_path)),
            );
        });
    }

    #[cfg_attr(feature = "hotpath", hotpath::measure)]
    fn apply_diff(
        &mut self,
        scope: &Rc<RefCell<Scope>>,
        diff: Diff,
        mutations: &mut Mutations,
        path_element: &PathElement,
        pending_reorders: &mut ReorderedParents,
    ) {
        let mut moved_nodes = FxHashMap::<Box<[u32]>, Vec<Option<NodeId>>>::default();
        let mut parents_to_resync_scopes = FxHashSet::default();

        // Children of each reordered parent, by old index
        for parent in diff.moved.keys() {
            parents_to_resync_scopes.insert(parent.clone());
            // `parent` is a new-tree path. If the parent itself was moved, its path in the
            // old nodes tree will differ, so resolve it before any lookup.
            let old_parent = resolve_old_path(parent, &diff.moved);
            let parent_node_id = scope.borrow().nodes.get(&old_parent).unwrap().node_id;
            let mut children =
                vec![None; scope.borrow().nodes.len(&old_parent).unwrap_or_default()];
            scope
                .borrow()
                .nodes
                .traverse_1_level(&old_parent, |path, node| {
                    children[path[path.len() - 1] as usize] = Some(node.node_id);
                });
            pending_reorders.insert(parent_node_id, parent.clone());
            moved_nodes.insert(parent.clone(), children);
        }

        // Capture the identity of addition parents while their old tree paths are still valid
        let mut addition_parents = FxHashMap::default();
        for added in &diff.added {
            if added.len() <= 1 {
                continue;
            }
            let parent = &added[..added.len() - 1];
            if addition_parents.contains_key(parent) {
                continue;
            }
            let old_parent = resolve_old_path(parent, &diff.moved);
            if let Some(node) = scope.borrow().nodes.get(&old_parent) {
                addition_parents.insert(Box::from(parent), (node.node_id, None));
            }
        }

        // Collect a set of branches to remove in cascade
        let mut selected_roots: FxHashMap<&[u32], FxHashSet<&[u32]>> = FxHashMap::default();
        let mut scope_removal_buffer = vec![];

        // Given some removals like:
        // [
        //     [0,2],
        //     [0,1,0,1],
        //     [0,1,0,2],
        //     [0,3],
        //     [0,1,5,8],
        // ]
        //
        // We want them ordered like:
        // [
        //     [0,3],
        //     [0,2],
        //     [0,1,5,8],
        //     [0,1,0,2],
        //     [0,1,0,1],
        // ]
        //
        // This way any removal does not move the next removals
        'remove: for removed in diff.removed.iter().sorted_by(|a, b| {
            for (x, y) in a.iter().zip(b.iter()) {
                match x.cmp(y) {
                    Ordering::Equal => continue,
                    non_eq => return non_eq.reverse(),
                }
            }
            b.len().cmp(&a.len())
        }) {
            parents_to_resync_scopes.insert(Box::from(&removed[..removed.len() - 1]));

            let path_node = scope.borrow().nodes.get(removed).cloned();
            if let Some(PathNode { node_id, scope_id }) = path_node {
                if scope_id.is_none() {
                    let removal = if removed.as_ref() == [0] {
                        MutationRemove::Scope { id: node_id }
                    } else {
                        MutationRemove::Element {
                            id: node_id,
                            index: removed[removed.len() - 1],
                        }
                    };
                    mutations.removed.push(removal);
                }

                // Skip if this removed path is already covered by a previously selected root
                for (root, inner) in &mut selected_roots {
                    if is_descendant(removed, root) {
                        inner.insert(removed);
                        continue 'remove;
                    }
                }

                // Remove any previously selected roots that are descendants of this new (higher) removed path
                selected_roots.retain(|root, _| !is_descendant(root, removed));

                selected_roots
                    .entry(&removed[..removed.len() - 1])
                    .or_default()
                    .insert(removed);
            } else {
                unreachable!()
            }
        }

        // Traverse each chosen branch root and queue nested scopes
        for (root, removed) in selected_roots.iter().sorted_by(|(a, _), (b, _)| {
            for (x, y) in a.iter().zip(b.iter()) {
                match x.cmp(y) {
                    Ordering::Equal => continue,
                    non_eq => return non_eq.reverse(),
                }
            }
            b.len().cmp(&a.len())
        }) {
            scope.borrow_mut().nodes.retain(
                root,
                |p, _| !removed.contains(p),
                |_, &PathNode { scope_id, node_id }| {
                    if let Some(scope_id) = scope_id {
                        // Queue scope to be removed
                        scope_removal_buffer.push(self.scopes.get(&scope_id).cloned().unwrap());
                    } else {
                        self.node_to_scope.remove(&node_id).unwrap();
                    }
                },
            );
        }

        let mut scope_removal_queue = VecDeque::new();

        while let Some(scope_rc) = scope_removal_buffer.pop() {
            // Push the scopes to a queue that will remove
            // them starting from the deepest to the highest ones
            scope_removal_queue.push_front(scope_rc.clone());

            let scope = scope_rc.borrow_mut();

            let mut scope_root_node_id = None;

            // Queue nested scopes to be removed
            scope
                .nodes
                .traverse(&[], |path, &PathNode { scope_id, node_id }| {
                    if let Some(scope_id) = scope_id {
                        scope_removal_buffer.push(self.scopes.get(&scope_id).cloned().unwrap());
                    } else {
                        self.node_to_scope.remove(&node_id).unwrap();
                    }
                    if path == [0] {
                        scope_root_node_id = Some(node_id);
                    }
                });

            // Nodes that have a scope id are components, so no need to mark those as removed in the tree
            // Instead we get their root node id and remove it
            mutations.removed.push(MutationRemove::Scope {
                id: scope_root_node_id.unwrap(),
            });
        }

        // Finally drops the scopes and their storage
        for scope_rc in scope_removal_queue {
            let scope = scope_rc.borrow_mut();

            self.scopes.remove(&scope.id);

            // Dropped hooks might e.g spawn forever tasks, so they need access to the context
            CurrentContext::run_with_reactive(self.create_context(scope.id), || {
                // TODO: Scopes could also maintain its own registry of assigned tasks
                let mut _removed_tasks = Vec::new();

                self.tasks.borrow_mut().retain(|task_id, task| {
                    if task.borrow().scope_id == scope.id {
                        _removed_tasks.push((*task_id, task.clone()));
                        false
                    } else {
                        true
                    }
                });
                drop(_removed_tasks);
                // This is very important, the scope storage must be dropped after the borrow in `scopes_storages` has been released
                let _scope = self.scopes_storages.borrow_mut().remove(&scope.id);
            });
        }

        // Given some additions like:
        // [
        //     [0,2],
        //     [0,1,0,1],
        //     [0,1,0,2],
        //     [0,3],
        //     [0,1,5,8],
        // ]
        //
        // We want them ordered like:
        // [
        //     [0,1,0,1],
        //     [0,1,0,2],
        //     [0,1,5,8],
        //     [0,2],
        //     [0,3],
        // ]
        //
        // This way, no addition offsets the next additions in line.
        for added in diff
            .added
            .iter()
            .sorted_by(|a, b| {
                for (x, y) in a.iter().zip(b.iter()) {
                    match x.cmp(y) {
                        Ordering::Equal => continue,
                        non_eq => return non_eq.reverse(),
                    }
                }
                b.len().cmp(&a.len())
            })
            .rev()
        {
            self.process_addition(
                scope,
                added,
                path_element,
                mutations,
                &mut parents_to_resync_scopes,
                &mut addition_parents,
            );
        }

        let added = if diff.moved.is_empty() {
            FxHashSet::default()
        } else {
            diff.added.iter().map(|path| path.as_ref()).collect()
        };

        for (parent, movements) in diff.moved.into_iter().sorted_by(|(a, _), (b, _)| {
            for (x, y) in a.iter().zip(b.iter()) {
                match x.cmp(y) {
                    Ordering::Equal => continue,
                    non_eq => return non_eq.reverse(),
                }
            }
            a.len().cmp(&b.len())
        }) {
            let old_children = moved_nodes.remove(&parent).unwrap();
            // New index to old index
            let sources = movements
                .into_iter()
                .map(|(from, to)| (to, from))
                .collect::<FxHashMap<_, _>>();

            // Child count of the new render
            let mut child_count = 0;
            path_element.with_element(&parent, |element| {
                if let PathElement::Element { elements, .. } = element {
                    child_count = elements.len() as u32;
                }
            });

            let mut to_path = Vec::with_capacity(parent.len() + 1);
            to_path.extend_from_slice(&parent);
            to_path.push(0);

            // Walk the final order, move only what is out of place
            for to in 0..child_count {
                to_path[parent.len()] = to;

                let is_added = added.contains(to_path.as_slice());
                let node_id = if is_added {
                    addition_parents.get(to_path.as_slice()).unwrap().0
                } else {
                    // Unmoved children keep their index
                    let from = sources.get(&to).copied().unwrap_or(to);
                    old_children[from as usize].expect("surviving child must have an old node")
                };

                if scope
                    .borrow()
                    .nodes
                    .get(&to_path)
                    .is_some_and(|node| node.node_id == node_id)
                {
                    continue;
                }

                let current_path = scope
                    .borrow()
                    .nodes
                    .find_child_path(&parent, |v| v.is_some_and(|v| v.node_id == node_id))
                    .unwrap();

                // Everything before `to` is already final
                let path_entry = scope.borrow_mut().nodes.remove(&current_path).unwrap();
                scope.borrow_mut().nodes.insert_entry(&to_path, path_entry);
            }
        }

        for (modified, flags) in diff.modified {
            path_element.with_element(&modified, |element| match element {
                PathElement::Component { .. } => {
                    // Components never change when being diffed
                    unreachable!()
                }
                PathElement::Element { element, .. } => {
                    let node_id = scope
                        .borrow()
                        .nodes
                        .get(&modified)
                        .map(|path_node| path_node.node_id)
                        .unwrap();
                    mutations.modified.push(MutationModified {
                        node_id,
                        element: element.clone(),
                        flags,
                    });
                }
            });
        }

        // When a parent gets a new child, or a child is removed or moved we
        // resync its 1 level children scopes with their new path
        for parent in parents_to_resync_scopes {
            // But only if the parent already existed before otherwise its pointless
            // as Scopes will be created with the latest path already
            if diff.added.contains(&parent) {
                // TODO: Maybe do this check before inserting
                continue;
            }

            // Update all the nested scopes in this Scope with their up to date paths
            scope
                .borrow_mut()
                .nodes
                .traverse_1_level(&parent, |p, path_node| {
                    if let Some(scope_id) = path_node.scope_id
                        && let Some(scope_rc) = self.scopes.get(&scope_id)
                    {
                        let mut scope = scope_rc.borrow_mut();
                        scope.path_in_parent = Box::from(p);
                    }
                });
        }
    }

    /// Reloads the runner for a hot-reload: cancels tasks, reloads every scope's hooks
    /// (contexts are preserved), and marks every scope dirty. Task cancellation must
    /// happen first so stale wakers can't fire [`Message::PollTask`] against
    /// freshly-reloaded scopes.
    pub fn reload(&mut self) {
        self.tasks.borrow_mut().clear();
        self.dirty_tasks.clear();
        while self.receiver.try_recv().is_ok() {}

        let scopes = self
            .scopes
            .iter()
            .sorted_by_key(|(_, s)| s.borrow().height)
            .map(|(_, s)| s.borrow().id)
            .collect::<Vec<_>>();

        for scope_id in scopes {
            CurrentContext::run(self.create_context(scope_id), || {
                let _hooks = self
                    .scopes_storages
                    .borrow_mut()
                    .get_mut(&scope_id)
                    .map(|storage| storage.reset_hooks());
            });
        }

        self.dirty_scopes.extend(self.scopes.keys());
        let _ = self
            .sender
            .unbounded_send(Message::MarkScopeAsDirty(ScopeId::ROOT));
    }
}

pub type Diff = tiny_diff::Diff<DiffModifies>;

/// Converts a new-tree path to its corresponding old-tree path by checking, for each
/// segment, whether that position was the destination of a movement in `moved`. If so,
/// the original (`from`) index is substituted so the result can be used to look up nodes
/// in the pre-diff nodes tree.
fn resolve_old_path(new_path: &[u32], moved: &FxHashMap<Box<[u32]>, Vec<(u32, u32)>>) -> Vec<u32> {
    let mut old_path = Vec::with_capacity(new_path.len());
    for i in 0..new_path.len() {
        let new_parent = &new_path[..i];
        let new_index = new_path[i];
        if let Some(movements) = moved.get(new_parent)
            && let Some(&(from, _)) = movements.iter().find(|(_, to)| *to == new_index)
        {
            old_path.push(from);
            continue;
        }
        old_path.push(new_index);
    }
    old_path
}

fn is_descendant(candidate: &[u32], ancestor: &[u32]) -> bool {
    if ancestor.len() > candidate.len() {
        return false;
    }
    candidate[..ancestor.len()] == *ancestor
}