| glimmer-cosmic: a libcosmic backend for glimmer (spike) 6a3304d nandi 8d ago | 1 | //! The node arena: what the reconciler patches, and what `view` reads. |
| 2 | //! |
| 3 | //! Plain data with no libcosmic in it, so the edit half of the ABI is testable |
| 4 | //! without a window, a GPU or a display. libvidya and libjolttui keep the same |
| 5 | //! shape; what is different here is who reads it. There, the caller's thread |
| 6 | //! paints the tree; here iced's thread does, so the arena sits behind a mutex |
| 7 | //! and `view` works from a snapshot taken at the last commit. |
| 8 | |
| 9 | use std::collections::BTreeMap; |
| 10 | use std::fmt::Write; |
| 11 | |
| 12 | #[derive(Clone, Debug, PartialEq)] |
| 13 | pub enum Prop { |
| 14 | Str(String), |
| 15 | Num(f64), |
| 16 | Bool(bool), |
| 17 | } |
| 18 | |
| 19 | #[derive(Clone, Debug)] |
| 20 | pub struct Node { |
| 21 | pub tag: String, |
| 22 | pub props: BTreeMap<String, Prop>, |
| 23 | pub children: Vec<i32>, |
| 24 | pub parent: i32, |
| 25 | } |
| 26 | |
| 27 | impl Node { |
| 28 | pub fn str(&self, key: &str) -> &str { |
| 29 | match self.props.get(key) { |
| 30 | Some(Prop::Str(s)) => s, |
| 31 | _ => "", |
| 32 | } |
| 33 | } |
| 34 | |
| 35 | pub fn num(&self, key: &str) -> Option<f64> { |
| 36 | match self.props.get(key) { |
| 37 | Some(Prop::Num(n)) => Some(*n), |
| 38 | _ => None, |
| 39 | } |
| 40 | } |
| 41 | |
| 42 | pub fn bool(&self, key: &str) -> Option<bool> { |
| 43 | match self.props.get(key) { |
| 44 | Some(Prop::Bool(b)) => Some(*b), |
| 45 | _ => None, |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | /// The label a text-shaped widget shows: `label`, or `text` failing that. |
| 50 | pub fn label(&self) -> &str { |
| 51 | match self.str("label") { |
| 52 | "" => self.str("text"), |
| 53 | s => s, |
| 54 | } |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | /// `hbox` and `vbox` are one node here, as in libvidya; the tag only implies |
| 59 | /// an orientation, and the jolt side writes it as a prop. |
| 60 | fn canonical(tag: &str) -> &str { |
| 61 | match tag { |
| 62 | "hbox" | "vbox" => "box", |
| 63 | "checkbox" => "checkbutton", |
| 64 | other => other, |
| 65 | } |
| 66 | } |
| 67 | |
| 68 | #[derive(Clone, Debug, Default)] |
| 69 | pub struct Tree { |
| 70 | /// Slot `i` holds handle `i + 1`; `None` is a freed handle waiting for reuse. |
| 71 | slots: Vec<Option<Node>>, |
| 72 | free: Vec<i32>, |
| 73 | root: i32, |
| 74 | } |
| 75 | |
| 76 | impl Tree { |
| 77 | pub fn get(&self, id: i32) -> Option<&Node> { |
| 78 | if id <= 0 { |
| 79 | return None; |
| 80 | } |
| 81 | self.slots.get(id as usize - 1)?.as_ref() |
| 82 | } |
| 83 | |
| 84 | fn get_mut(&mut self, id: i32) -> Option<&mut Node> { |
| 85 | if id <= 0 { |
| 86 | return None; |
| 87 | } |
| 88 | self.slots.get_mut(id as usize - 1)?.as_mut() |
| 89 | } |
| 90 | |
| 91 | pub fn exists(&self, id: i32) -> bool { |
| 92 | self.get(id).is_some() |
| 93 | } |
| 94 | |
| 95 | pub fn root(&mut self) -> i32 { |
| 96 | if !self.exists(self.root) { |
| 97 | self.root = self.new_node("window"); |
| 98 | } |
| 99 | self.root |
| 100 | } |
| 101 | |
| 102 | /// The root without creating it, for a reader holding a snapshot. |
| 103 | pub fn root_id(&self) -> i32 { |
| 104 | self.root |
| 105 | } |
| 106 | |
| 107 | pub fn new_node(&mut self, tag: &str) -> i32 { |
| 108 | let node = Node { |
| 109 | tag: canonical(tag).to_owned(), |
| 110 | props: BTreeMap::new(), |
| 111 | children: Vec::new(), |
| 112 | parent: 0, |
| 113 | }; |
| 114 | match self.free.pop() { |
| 115 | Some(id) => { |
| 116 | self.slots[id as usize - 1] = Some(node); |
| 117 | id |
| 118 | } |
| 119 | None => { |
| 120 | self.slots.push(Some(node)); |
| 121 | self.slots.len() as i32 |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | /// Free `id` and everything under it, detaching it from its parent first. |
| 127 | pub fn free(&mut self, id: i32) { |
| 128 | let Some(node) = self.get(id) else { return }; |
| 129 | let parent = node.parent; |
| 130 | if let Some(p) = self.get_mut(parent) { |
| 131 | p.children.retain(|c| *c != id); |
| 132 | } |
| 133 | self.free_subtree(id); |
| 134 | } |
| 135 | |
| 136 | fn free_subtree(&mut self, id: i32) { |
| 137 | let Some(node) = self.slots.get_mut(id as usize - 1).and_then(Option::take) else { |
| 138 | return; |
| 139 | }; |
| 140 | for child in node.children { |
| 141 | self.free_subtree(child); |
| 142 | } |
| 143 | if id == self.root { |
| 144 | self.root = 0; |
| 145 | } |
| 146 | self.free.push(id); |
| 147 | } |
| 148 | |
| 149 | pub fn set(&mut self, id: i32, key: &str, value: Prop) { |
| 150 | if let Some(n) = self.get_mut(id) { |
| 151 | n.props.insert(key.to_owned(), value); |
| 152 | } |
| 153 | } |
| 154 | |
| 155 | pub fn clear_props(&mut self, id: i32) { |
| 156 | if let Some(n) = self.get_mut(id) { |
| 157 | n.props.clear(); |
| 158 | } |
| 159 | } |
| 160 | |
| 161 | fn detach(&mut self, child: i32) { |
| 162 | let parent = match self.get(child) { |
| 163 | Some(n) => n.parent, |
| 164 | None => return, |
| 165 | }; |
| 166 | if let Some(p) = self.get_mut(parent) { |
| 167 | p.children.retain(|c| *c != child); |
| 168 | } |
| 169 | if let Some(c) = self.get_mut(child) { |
| 170 | c.parent = 0; |
| 171 | } |
| 172 | } |
| 173 | |
| 174 | /// A node may not become its own ancestor; the reconciler never asks, but |
| 175 | /// a cycle would make `view` recurse forever, so it is refused here. |
| 176 | fn is_ancestor(&self, ancestor: i32, mut id: i32) -> bool { |
| 177 | while id > 0 { |
| 178 | if id == ancestor { |
| 179 | return true; |
| 180 | } |
| 181 | id = self.get(id).map_or(0, |n| n.parent); |
| 182 | } |
| 183 | false |
| 184 | } |
| 185 | |
| 186 | pub fn append(&mut self, parent: i32, child: i32) -> bool { |
| 187 | if !self.exists(parent) || !self.exists(child) || self.is_ancestor(child, parent) { |
| 188 | return false; |
| 189 | } |
| 190 | self.detach(child); |
| 191 | self.get_mut(parent).unwrap().children.push(child); |
| 192 | self.get_mut(child).unwrap().parent = parent; |
| 193 | true |
| 194 | } |
| 195 | |
| 196 | /// Unparents and frees `child`, under `parent` only. |
| 197 | pub fn remove(&mut self, parent: i32, child: i32) { |
| 198 | if self.get(child).is_some_and(|n| n.parent == parent) { |
| 199 | self.free(child); |
| 200 | } |
| 201 | } |
| 202 | |
| 203 | /// Move `child` after `sibling`; `sibling` 0 is the first position. |
| 204 | pub fn insert_after(&mut self, parent: i32, child: i32, sibling: i32) -> bool { |
| 205 | if !self.exists(parent) || !self.exists(child) || self.is_ancestor(child, parent) { |
| 206 | return false; |
| 207 | } |
| 208 | if sibling != 0 && self.get(sibling).is_none_or(|n| n.parent != parent) { |
| 209 | return false; |
| 210 | } |
| 211 | self.detach(child); |
| 212 | let p = self.get_mut(parent).unwrap(); |
| 213 | let at = if sibling == 0 { |
| 214 | 0 |
| 215 | } else { |
| 216 | p.children.iter().position(|c| *c == sibling).unwrap() + 1 |
| 217 | }; |
| 218 | p.children.insert(at, child); |
| 219 | self.get_mut(child).unwrap().parent = parent; |
| 220 | true |
| 221 | } |
| 222 | |
| 223 | /// Put `new` where `old` was under `parent`, and free `old`. |
| 224 | pub fn replace(&mut self, parent: i32, old: i32, new: i32) -> bool { |
| 225 | if !self.exists(new) || self.get(old).is_none_or(|n| n.parent != parent) { |
| 226 | return false; |
| 227 | } |
| 228 | if self.is_ancestor(new, parent) { |
| 229 | return false; |
| 230 | } |
| 231 | self.detach(new); |
| 232 | let p = self.get_mut(parent).unwrap(); |
| 233 | let at = p.children.iter().position(|c| *c == old).unwrap(); |
| 234 | p.children[at] = new; |
| 235 | self.get_mut(new).unwrap().parent = parent; |
| 236 | // `old` is no longer among the parent's children, so free only its subtree. |
| 237 | self.get_mut(old).unwrap().parent = 0; |
| 238 | self.free_subtree(old); |
| 239 | true |
| 240 | } |
| 241 | |
| 242 | /// The subtree at `id` as hiccup, one node to a line, props sorted — so two |
| 243 | /// dumps of the same tree compare as text. |
| 244 | pub fn dump(&self, id: i32) -> String { |
| 245 | let mut out = String::new(); |
| 246 | self.dump_into(id, 0, &mut out); |
| 247 | out |
| 248 | } |
| 249 | |
| 250 | fn dump_into(&self, id: i32, depth: usize, out: &mut String) { |
| 251 | let Some(n) = self.get(id) else { return }; |
| 252 | let _ = write!(out, "{}[:{} {{", " ".repeat(depth), n.tag); |
| 253 | for (i, (k, v)) in n.props.iter().enumerate() { |
| 254 | if i > 0 { |
| 255 | out.push(' '); |
| 256 | } |
| 257 | let _ = match v { |
| 258 | Prop::Str(s) => write!(out, ":{k} {s:?}"), |
| 259 | Prop::Num(x) => write!(out, ":{k} {x}"), |
| 260 | Prop::Bool(b) => write!(out, ":{k} {b}"), |
| 261 | }; |
| 262 | } |
| 263 | out.push('}'); |
| 264 | for child in &n.children { |
| 265 | out.push('\n'); |
| 266 | self.dump_into(*child, depth + 1, out); |
| 267 | } |
| 268 | out.push(']'); |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | #[cfg(test)] |
| 273 | mod tests { |
| 274 | use super::*; |
| 275 | |
| 276 | #[test] |
| 277 | fn a_removed_subtree_frees_every_node_under_it() { |
| 278 | let mut t = Tree::default(); |
| 279 | let root = t.root(); |
| 280 | let card = t.new_node("card"); |
| 281 | let label = t.new_node("label"); |
| 282 | assert!(t.append(root, card)); |
| 283 | assert!(t.append(card, label)); |
| 284 | t.remove(root, card); |
| 285 | assert!(!t.exists(card)); |
| 286 | assert!(!t.exists(label)); |
| 287 | assert!(t.get(root).unwrap().children.is_empty()); |
| 288 | } |
| 289 | |
| 290 | #[test] |
| 291 | fn insert_after_zero_moves_to_the_front() { |
| 292 | let mut t = Tree::default(); |
| 293 | let root = t.root(); |
| 294 | let (a, b, c) = ( |
| 295 | t.new_node("label"), |
| 296 | t.new_node("label"), |
| 297 | t.new_node("label"), |
| 298 | ); |
| 299 | for n in [a, b, c] { |
| 300 | t.append(root, n); |
| 301 | } |
| 302 | assert!(t.insert_after(root, c, 0)); |
| 303 | assert_eq!(t.get(root).unwrap().children, vec![c, a, b]); |
| 304 | assert!(t.insert_after(root, c, b)); |
| 305 | assert_eq!(t.get(root).unwrap().children, vec![a, b, c]); |
| 306 | } |
| 307 | |
| 308 | #[test] |
| 309 | fn replace_keeps_the_position_and_frees_the_old_node() { |
| 310 | let mut t = Tree::default(); |
| 311 | let root = t.root(); |
| 312 | let (a, b, c) = ( |
| 313 | t.new_node("label"), |
| 314 | t.new_node("button"), |
| 315 | t.new_node("label"), |
| 316 | ); |
| 317 | t.append(root, a); |
| 318 | t.append(root, b); |
| 319 | assert!(t.replace(root, a, c)); |
| 320 | assert_eq!(t.get(root).unwrap().children, vec![c, b]); |
| 321 | assert!(!t.exists(a)); |
| 322 | } |
| 323 | |
| 324 | #[test] |
| 325 | fn a_node_cannot_be_appended_under_itself() { |
| 326 | let mut t = Tree::default(); |
| 327 | let root = t.root(); |
| 328 | let card = t.new_node("card"); |
| 329 | t.append(root, card); |
| 330 | assert!(!t.append(card, root)); |
| 331 | } |
| 332 | |
| 333 | #[test] |
| 334 | fn dump_reads_back_as_hiccup() { |
| 335 | let mut t = Tree::default(); |
| 336 | let root = t.root(); |
| 337 | let row = t.new_node("hbox"); |
| 338 | t.set(row, "orientation", Prop::Str("horizontal".into())); |
| 339 | let b = t.new_node("button"); |
| 340 | t.set(b, "label", Prop::Str("+ 1".into())); |
| 341 | t.set(b, "kind", Prop::Str("primary".into())); |
| 342 | t.append(root, row); |
| 343 | t.append(row, b); |
| 344 | assert_eq!( |
| 345 | t.dump(root), |
| 346 | "[:window {}\n [:box {:orientation \"horizontal\"}\n [:button {:kind \"primary\" :label \"+ 1\"}]]]" |
| 347 | ); |
| 348 | } |
| 349 | } |