带 key 的列表

    pub(crate) fn diff_non_empty_fragment(
        &mut self,
        to: Option<&mut impl WriteMutations>,
        old: &[VNode],
        new: &[VNode],
        parent: Option<ElementRef>,
    ) {
        let new_is_keyed = new[0].key.is_some();
        let old_is_keyed = old[0].key.is_some();
        debug_assert!(
            new.iter().all(|n| n.key.is_some() == new_is_keyed),
            "all siblings must be keyed or all siblings must be non-keyed"
        );
        debug_assert!(
            old.iter().all(|o| o.key.is_some() == old_is_keyed),
            "all siblings must be keyed or all siblings must be non-keyed"
        );

        if new_is_keyed && old_is_keyed {
            self.diff_keyed_children(to, old, new, parent);
        } else {
            self.diff_non_keyed_children(to, old, new, parent);
        }
    }

    fn diff_non_keyed_children(
        &mut self,
        mut to: Option<&mut impl WriteMutations>,
        old: &[VNode],
        new: &[VNode],
        parent: Option<ElementRef>,
    ) {
        use std::cmp::Ordering;

        // Handled these cases in `diff_children` before calling this function.
        debug_assert!(!new.is_empty());
        debug_assert!(!old.is_empty());

        match old.len().cmp(&new.len()) {
            Ordering::Greater => self.remove_nodes(to.as_deref_mut(), &old[new.len()..], None),
            Ordering::Less => self.create_and_insert_after(
                to.as_deref_mut(),
                &new[old.len()..],
                old.last().unwrap(),
                parent,
            ),
            Ordering::Equal => {}
        }

        for (new, old) in new.iter().zip(old.iter()) {
            old.diff_node(new, self, to.as_deref_mut());
        }
    }

fn app() -> Element {
  let items = items();
  match MODE.with(|m| m.get()) {
    0 => rsx! {
      ul {
        for (_id, label) in items {
          li { "{label}" }
        }
      }
    },
    1 => rsx! {
      ul {
        for (id, label) in items {
          li { key: "{id}", "{label}" }
        }
      }
    },
    2 => rsx! {
      ul {
        for (_id, label) in items {
          Row { label }
        }
      }
    },
    _ => rsx! {
      ul {
        for (id, label) in items {
          Row { key: "{id}", label }
        }
      }
    },
  }
}

/// Each row keeps a piece of local state, created from the label of its first render.
#[component]
fn Row(label: String) -> Element {
  ROW_RUNS.with(|c| c.set(c.get() + 1));
  let state = use_signal(|| format!("state of {label}"));
  rsx! { li { "{label} | {state}" } }
}

fn main() {
  let abc = [(1, "A"), (2, "B"), (3, "C")];
  let axbc = [(1, "A"), (9, "X"), (2, "B"), (3, "C")];
  run("elements, no key, insert X at index 1", 0, &abc, &axbc);
  run("elements, key, insert X at index 1", 1, &abc, &axbc);
  run("components with state, no key, insert X at index 1", 2, &abc, &axbc);
  run("components with state, key, insert X at index 1", 3, &abc, &axbc);
  // ...
}

===== elements, no key, insert X at index 1
--- rebuild: 12 edits
  LoadTemplate <ul> index=0 id=1
  LoadTemplate <li> index=0 id=2
  CreateTextNode "A" id=3
  ReplacePlaceholder path=[0] m=1
  LoadTemplate <li> index=0 id=4
  CreateTextNode "B" id=5
  ReplacePlaceholder path=[0] m=1
  LoadTemplate <li> index=0 id=6
  CreateTextNode "C" id=7
  ReplacePlaceholder path=[0] m=1
  ReplacePlaceholder path=[0] m=3
  AppendChildren id=0 m=1
  before: <ul><li>A</li><li>B</li><li>C</li></ul>
--- update: 6 edits
  LoadTemplate <li> index=0 id=8
  CreateTextNode "C" id=9
  ReplacePlaceholder path=[0] m=1
  InsertAfter id=6 m=1
  SetText "X" id=5
  SetText "B" id=7
  after:  <ul><li>A</li><li>X</li><li>B</li><li>C</li></ul>
===== elements, key, insert X at index 1
  before: <ul><li>A</li><li>B</li><li>C</li></ul>
--- update: 4 edits
  LoadTemplate <li> index=0 id=8
  CreateTextNode "X" id=9
  ReplacePlaceholder path=[0] m=1
  InsertBefore id=4 m=1
  after:  <ul><li>A</li><li>X</li><li>B</li><li>C</li></ul>
===== components with state, no key, insert X at index 1
  before: <ul><li>A | state of A</li><li>B | state of B</li><li>C | state of C</li></ul>
--- update: 6 edits
  LoadTemplate <li> index=0 id=8
  CreateTextNode "C | state of C" id=9
  ReplacePlaceholder path=[0] m=1
  InsertAfter id=6 m=1
  SetText "X | state of B" id=5
  SetText "B | state of C" id=7
  Row ran 3 times during the update
  after:  <ul><li>A | state of A</li><li>X | state of B</li><li>B | state of C</li><li>C | state of C</li></ul>
===== components with state, key, insert X at index 1
  before: <ul><li>A | state of A</li><li>B | state of B</li><li>C | state of C</li></ul>
--- update: 4 edits
  LoadTemplate <li> index=0 id=8
  CreateTextNode "X | state of X" id=9
  ReplacePlaceholder path=[0] m=1
  InsertBefore id=4 m=1
  Row ran 1 times during the update
  after:  <ul><li>A | state of A</li><li>X | state of X</li><li>B | state of B</li><li>C | state of C</li></ul>

    fn diff_keyed_ends(
        &mut self,
        mut to: Option<&mut impl WriteMutations>,
        old: &[VNode],
        new: &[VNode],
        parent: Option<ElementRef>,
    ) -> Option<(usize, usize)> {
        let mut left_offset = 0;

        for (old, new) in old.iter().zip(new.iter()) {
            // abort early if we finally run into nodes with different keys
            if old.key != new.key {
                break;
            }
            old.diff_node(new, self, to.as_deref_mut());
            left_offset += 1;
        }

        // If that was all of the old children, then create and append the remaining
        // new children and we're finished.
        if left_offset == old.len() {
            self.create_and_insert_after(to, &new[left_offset..], &new[left_offset - 1], parent);
            return None;
        }

        // if the shared prefix is less than either length, then we need to walk backwards
        let mut right_offset = 0;
        for (old, new) in old.iter().rev().zip(new.iter().rev()) {
            // abort early if we finally run into nodes with different keys
            if old.key != new.key {
                break;
            }
            old.diff_node(new, self, to.as_deref_mut());
            right_offset += 1;
        }

        // If that was all of the old children, then create and prepend the remaining
        // new children and we're finished.
        if right_offset == old.len() {
            self.create_and_insert_before(
                to,
                &new[..new.len() - right_offset],
                &new[new.len() - right_offset],
                parent,
            );
            return None;
        }

        // If the right offset + the left offset is the same as the new length, then we just need to remove the old nodes
        if right_offset + left_offset == new.len() {
            self.remove_nodes(to, &old[left_offset..old.len() - right_offset], None);
            return None;
        }

        // If the right offset + the left offset is the same as the old length, then we just need to add the new nodes
        if right_offset + left_offset == old.len() {
            self.create_and_insert_before(
                to,
                &new[left_offset..new.len() - right_offset],
                &new[new.len() - right_offset],
                parent,
            );
            return None;
        }

        Some((left_offset, right_offset))
    }

        /*
        1. Map the old keys into a numerical ordering based on indices.
        2. Create a map of old key to its index
        3. Map each new key to the old key, carrying over the old index.
            - IE if we have ABCD becomes BACD, our sequence would be 1,0,2,3
            - if we have ABCD to ABDE, our sequence would be 0,1,3,MAX because E doesn't exist

        now, we should have a list of integers that indicates where in the old list the new items map to.

        4. Compute the LIS of this list
            - this indicates the longest list of new children that won't need to be moved.

        5. Identify which nodes need to be removed
        6. Identify which nodes will need to be diffed

        7. Going along each item in the new list, create it and insert it before the next closest item in the LIS.
            - if the item already existed, just move it to the right place.

        8. Finally, generate instructions to remove any old children.
        9. Generate instructions to finally diff children that are the same between both
        */

        // 4. Compute the LIS of this list
        let mut lis_sequence = Vec::with_capacity(new_index_to_old_index.len());

        let mut allocation = vec![0; new_index_to_old_index.len() * 2];
        let (predecessors, starts) = allocation.split_at_mut(new_index_to_old_index.len());

        longest_increasing_subsequence::lis_with(
            &new_index_to_old_index,
            &mut lis_sequence,
            |a, b| a < b,
            predecessors,
            starts,
        );

        // if a new node gets u32 max and is at the end, then it might be part of our LIS (because u32 max is a valid LIS)
        if lis_sequence.first().map(|f| new_index_to_old_index[*f]) == Some(usize::MAX) {
            lis_sequence.remove(0);
        }

        // Diff each nod in the LIS
        for idx in &lis_sequence {
            old[new_index_to_old_index[*idx]].diff_node(&new[*idx], self, to.as_deref_mut());
        }

===== elements, key, move D before B
...
--- update: 2 edits
  PushRoot id=8
  InsertBefore id=4 m=1
  after:  <ul><li>A</li><li>D</li><li>B</li><li>C</li><li>E</li></ul>

fn main() {
  // key 2 appears twice
  ITEMS.with(|i| *i.borrow_mut() = vec![(1, "A"), (2, "B"), (2, "B2"), (3, "C")]);
  let mut dom = VirtualDom::new(app);
  dom.rebuild_in_place();
  println!("rebuild ok: {}", dioxus_ssr::render(&dom));

  ITEMS.with(|i| *i.borrow_mut() = vec![(3, "C"), (2, "B2"), (2, "B"), (1, "A")]);
  dom.mark_dirty(ScopeId::APP);
  let mut log = core1_exp::Log::default();
  dom.render_immediate(&mut log);
  log.print("update");
  println!("{}", dioxus_ssr::render(&dom));
}

rebuild ok: <ul><li>A</li><li>B</li><li>B2</li><li>C</li></ul>

thread 'main' (979066) panicked at ~/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/dioxus-core-0.7.10/src/diff/iterator.rs:107:17:
assertion `left == right` failed: keyed siblings must each have a unique key
  left: 4
 right: 3
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

rebuild ok: <ul><li>A</li><li>B</li><li>B2</li><li>C</li></ul>

thread 'main' (977236) panicked at ~/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/dioxus-core-0.7.10/src/diff/mod.rs:44:15:
invalid key
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

===== elements, key, remove D, add F, move B
...
--- update: 6 edits
  Remove id=8
  LoadTemplate <li> index=0 id=8
  CreateTextNode "F" id=9
  ReplacePlaceholder path=[0] m=1
  PushRoot id=4
  InsertAfter id=6 m=2
  after:  <ul><li>A</li><li>C</li><li>F</li><li>B</li><li>E</li></ul>