{"header":{"message":"Switch from in memory grid to recursive CTE","description":null,"timestamp":"2023-08-22T03:21:59.30284363Z","authors":[{}]},"hash":"VBDR24U4NU2GWBHQE5B3BMJPWOCAXK5Y2WURM5EFZSN77Y6T54HQC","authors":[{"login":"quickdudley","key":"5B8LBcp1Xe7XYwo2o8k8whShcE6RkhkJA4PjbgBQDwKK"}],"deps":{"hashes":[["VBDR24U4NU2GWBHQE5B3BMJPWOCAXK5Y2WURM5EFZSN77Y6T54HQC","Switch from in memory grid to recursive CTE"],["AA",null],["FOUJ5RXTAO6PY6XKGATFZSCQZVCWHGFF4FIY6EEMLL7EE4CWAQ7AC","Further reduce required manual comparisons"],["QEKHTVB7CH754NUMHJ3AKVGRNKW3KOAKMALS7B3ZNKCUEH6GP4HQC","Get most things semi-working except the final sort"],["5Y7ZXB53EMG34VZI5VQIZ77TZKBB4V6BGIILFZ5ZY73QYK4V2YHQC","Start picker UI"],["AV73DYWQ2UVZJYTN3UIW3TDMWNAETLXZRD7VHKTQLFQGHKJ5KI6QC","Initial functions for using sqlite in async environment"],["RNW6D77774CYWWM7JIFXI5TGKBOU6ADJIEZB5N2FXGDCTLUXEQZQC","Minor tidy"],["5OUVESUQDAEU3PEYFDXDMEULBNBJYEEHWV2LWFOOUKCTKRSZQMSAC","Attempt to reduce additional manual comparison upon resume"],["HMOBTVJ4FEPZWMUV2JDPZYH3EFCW6ED5M6KKNKQJQZVKTDAKTVFQC","Initialize crate and add expected dependencies"],["LLFG625ISXV7P2LUOFUMFIM5V5RJDKWCL47XX43X2CGILVAUQPVQC","Should be all the database functions I need"],["KUANIPWFDXDFKJ2LH4FQ6APYOPLNYJ5LVGLSBSC75WUUZPFHILCAC","Add function for adding name to database"],["MFGAW2Q2U6VB7A5H2OIYSX7JGB5FYSSBXWPPC5P5HCXKGWKLUEGQC","Cache preferences in memory"],["YCWYAX6K2DJKT7FO4IAYL6HJOIJLYFKAPGLFJ5XMYSYAS42LP3FQC","Functions for scraping names integrated enough to test (they don't work yet)"],["272LZTVTE66SQ4BYDORDIBSQFKG3357ZYIUNPVOGUC47VFXOAKVQC","Move terminal cleanup to Drop implementation"],["G5YNDTPHPYRZZIGWLX2ZLVFRJ3B2NGAPVESSMTO7YEABDFIIE66AC","Cargo clippy"],["PQ4BG3ZJU5SY6XQDJ3SURLAOWGXGXLONIRZNUJXZVMHLYXWOORXQC","The web scrape functions"],["AOO3FCSGBMVD5YFMP2JO2P7ACWZF7IS6G3EI75GRYOIS4EIKPKHQC","Cargo clippy, tweaks, etc"]],"deps":["FOUJ5RXTAO6PY6XKGATFZSCQZVCWHGFF4FIY6EEMLL7EE4CWAQ7AC"],"known":["HMOBTVJ4FEPZWMUV2JDPZYH3EFCW6ED5M6KKNKQJQZVKTDAKTVFQC","AV73DYWQ2UVZJYTN3UIW3TDMWNAETLXZRD7VHKTQLFQGHKJ5KI6QC","RNW6D77774CYWWM7JIFXI5TGKBOU6ADJIEZB5N2FXGDCTLUXEQZQC","KUANIPWFDXDFKJ2LH4FQ6APYOPLNYJ5LVGLSBSC75WUUZPFHILCAC","PQ4BG3ZJU5SY6XQDJ3SURLAOWGXGXLONIRZNUJXZVMHLYXWOORXQC","YCWYAX6K2DJKT7FO4IAYL6HJOIJLYFKAPGLFJ5XMYSYAS42LP3FQC","5Y7ZXB53EMG34VZI5VQIZ77TZKBB4V6BGIILFZ5ZY73QYK4V2YHQC","G5YNDTPHPYRZZIGWLX2ZLVFRJ3B2NGAPVESSMTO7YEABDFIIE66AC","LLFG625ISXV7P2LUOFUMFIM5V5RJDKWCL47XX43X2CGILVAUQPVQC","QEKHTVB7CH754NUMHJ3AKVGRNKW3KOAKMALS7B3ZNKCUEH6GP4HQC","272LZTVTE66SQ4BYDORDIBSQFKG3357ZYIUNPVOGUC47VFXOAKVQC","MFGAW2Q2U6VB7A5H2OIYSX7JGB5FYSSBXWPPC5P5HCXKGWKLUEGQC","AOO3FCSGBMVD5YFMP2JO2P7ACWZF7IS6G3EI75GRYOIS4EIKPKHQC","5OUVESUQDAEU3PEYFDXDMEULBNBJYEEHWV2LWFOOUKCTKRSZQMSAC"]},"hunks":[{"FileDel":{"deleted_names":[{"basename":"grid.rs","metadata":0}],"del":{"EdgeMap":{"edges":[{"previous":"BLOCK | FOLDER","flag":"BLOCK | FOLDER | DELETED","from":{"change":3,"pos":15},"to":{"change":3,"start":3286,"end":3317},"introduced_by":3},{"previous":"BLOCK | FOLDER","flag":"BLOCK | FOLDER | DELETED","from":{"change":3,"pos":3317},"to":{"change":3,"start":3318,"end":3318},"introduced_by":3}],"inode":{"change":3,"pos":3318}}},"content_edges":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3318},"to":{"change":3,"start":3319,"end":3533},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3533},"to":{"change":3,"start":1558,"end":1613},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1613},"to":{"change":3,"start":3595,"end":3635},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3595},"to":{"change":3,"start":3595,"end":3635},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3635},"to":{"change":3,"start":1614,"end":1663},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1663},"to":{"change":3,"start":3691,"end":10515},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":3691},"to":{"change":3,"start":3691,"end":10515},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10515},"to":{"change":3,"start":1664,"end":1715},"introduced_by":3},{"previous":"","flag":"DELETED","from":{"change":3,"pos":1715},"to":{"change":3,"start":10581,"end":12449},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":10581},"to":{"change":3,"start":10581,"end":12449},"introduced_by":3}],"inode":{"change":3,"pos":3318}},"content":[{"Del":"#[derive(Debug)]\npub struct BoolGrid {\n width: usize,\n content: Vec,\n}\n\nimpl BoolGrid {\n pub fn new() -> Self {\n Self {\n width: 0,\n content: Vec::new(),\n }\n }\n\n"},{"Del":" pub fn column(&self, x: usize) -> BoolColumn<'_> {\n"},{"Del":" BoolColumn::new(self, x)\n }\n\n"},{"Del":" pub fn row(&self, y: usize) -> BoolRow<'_> {\n"},{"Del":" BoolRow::new(self, y)\n }\n\n pub fn set_transitive(\n &mut self,\n x: usize,\n y: usize,\n ) -> Vec<(usize, usize)> {\n use std::collections::VecDeque;\n let mut q = VecDeque::new();\n q.push_back((x, y));\n let mut result = Vec::new();\n while let Some((x, y)) = q.pop_front() {\n let t = &mut self[(x, y)];\n if !*t {\n *t = true;\n result.push((x, y));\n for (c, v) in self.row(x).enumerate() {\n if v {\n q.push_back((c, y));\n }\n }\n for (c, v) in self.column(y).enumerate() {\n if v {\n q.push_back((x, c));\n }\n }\n }\n }\n result\n }\n\n pub fn compare(&self, x: usize, y: usize) -> Option {\n use std::cmp::Ordering::*;\n if x == y {\n Some(Equal)\n } else {\n match (self[(x, y)], self[(y, x)]) {\n (true, true) => Some(Equal),\n (true, false) => Some(Greater),\n (false, true) => Some(Less),\n (false, false) => None,\n }\n }\n }\n}\n\n#[test]\nfn transitive_works() {\n let mut grid = BoolGrid::new();\n grid.set_transitive(1, 2);\n grid.set_transitive(14, 15);\n grid.set_transitive(2, 3);\n grid.set_transitive(10, 11);\n grid.set_transitive(4, 5);\n grid.set_transitive(12, 13);\n grid.set_transitive(15, 16);\n grid.set_transitive(6, 7);\n grid.set_transitive(13, 14);\n grid.set_transitive(5, 6);\n grid.set_transitive(9, 10);\n grid.set_transitive(11, 12);\n grid.set_transitive(8, 9);\n for x in 0..=16 {\n for y in 0..=16 {\n assert_eq!(\n x < y\n && [1..=3, 4..=7, 8..=16]\n .into_iter()\n .any(|i| i.contains(&x) && i.contains(&y)),\n grid[(x, y)]\n );\n }\n }\n}\n\n#[test]\nfn row_iterator() {\n let mut grid = BoolGrid::new();\n grid[(5, 4)] = true;\n let row: Vec<_> = grid.row(4).collect();\n assert_eq!(&row[..], &[false, false, false, false, false, true]);\n assert!(grid.row(5).all(|v| !v));\n}\n\n#[test]\nfn col_iterator() {\n let mut grid = BoolGrid::new();\n grid[(5, 4)] = true;\n let row: Vec<_> = grid.column(5).collect();\n assert_eq!(&row[..], &[false, false, false, false, true]);\n assert!(grid.column(6).all(|v| !v));\n}\n\n#[test]\nfn test_compare() {\n use std::cmp::Ordering::*;\n let mut grid = BoolGrid::new();\n let mut set = Vec::new();\n set.extend(grid.set_transitive(1, 2).into_iter());\n set.extend(grid.set_transitive(2, 3).into_iter());\n assert_eq!(grid.compare(3, 4), None);\n assert_eq!(grid.compare(1, 3), Some(Greater));\n assert_eq!(grid.compare(3, 1), Some(Less));\n assert_eq!(grid.compare(2, 2), Some(Equal));\n assert!(set.iter().all(|(a, b)| a < b));\n}\n\n#[test]\nfn test_transitive_bug() {\n let mut grid = BoolGrid::new();\n let mut set = Vec::new();\n for (a, b) in [(1, 4), (4, 2), (8, 4), (3, 4), (4, 7), (4, 6), (4, 12)] {\n set.extend(grid.set_transitive(a, b));\n }\n for (a, b) in set {\n assert!(a != 11);\n assert!(b != 11);\n }\n for x in 1..=12 {\n assert!(!grid[(11, x)]);\n assert!(!grid[(x, 11)]);\n }\n}\n\n#[test]\nfn test_rows_cols_bug() {\n use std::collections::HashSet;\n let mut grid = BoolGrid::new();\n let mut set = HashSet::new();\n grid.set_transitive(1, 4);\n set.insert((1, 4));\n for x in 0..=5 {\n for y in 0..=5 {\n assert_eq!(grid[(x, y)], (x, y) == (1, 4));\n }\n }\n let c: Vec<_> = grid.column(3).collect();\n println!(\"column 3: {:?}\", c);\n for x in 0..12 {\n for (y, v) in grid.column(x).enumerate() {\n if v != set.contains(&(x, y)) {\n panic!(\"x: {}, y: {}, v: {}\", x, y, v);\n }\n }\n }\n}\n\nstatic OFF_GRID: bool = false;\n\nimpl std::ops::Index<(usize, usize)> for BoolGrid {\n type Output = bool;\n fn index(&self, (x, y): (usize, usize)) -> &bool {\n if x >= self.width {\n return &OFF_GRID;\n }\n let ix = self.width * y + x;\n if ix >= self.content.len() {\n return &OFF_GRID;\n }\n as std::ops::Index>::index(&self.content, ix)\n }\n}\n\nimpl std::ops::IndexMut<(usize, usize)> for BoolGrid {\n fn index_mut(&mut self, (x, y): (usize, usize)) -> &mut bool {\n let height = self.content.len() / self.width.max(1);\n let rq_width = self.width.max(x + 1);\n let rq_height = (y + 1).max(height);\n if (self.width, height) != (rq_width, rq_height) {\n struct Resize {\n old_content: Vec,\n old_width: usize,\n new_width: usize,\n new_height: usize,\n x: usize,\n y: usize,\n }\n impl Resize {\n fn new(\n content: Vec,\n old_width: usize,\n new_width: usize,\n new_height: usize,\n ) -> Self {\n Self {\n old_content: content,\n old_width,\n new_width,\n new_height,\n x: 0,\n y: 0,\n }\n }\n }\n impl Iterator for Resize {\n type Item = bool;\n fn next(&mut self) -> Option {\n if self.y >= self.new_height {\n return None;\n }\n let result = if self.x >= self.old_width {\n Some(false)\n } else {\n let ix = self.y * self.old_width + self.x;\n if ix >= self.old_content.len() {\n Some(false)\n } else {\n Some(self.old_content[ix])\n }\n };\n let z = if self.x < self.new_width - 1 {\n (self.x + 1, self.y)\n } else {\n (0, self.y + 1)\n };\n self.x = z.0;\n self.y = z.1;\n result\n }\n fn size_hint(&self) -> (usize, Option) {\n let r =\n self.new_width * (self.new_height - self.y) - self.x;\n (r, Some(r))\n }\n }\n self.content = Resize::new(\n"},{"Del":" std::mem::take(&mut self.content),\n"},{"Del":" self.width,\n rq_width,\n rq_height,\n )\n .collect();\n self.width = rq_width;\n }\n as std::ops::IndexMut>::index_mut(\n &mut self.content,\n self.width * y + x,\n )\n }\n}\n\npub struct BoolColumn<'a> {\n grid: &'a BoolGrid,\n ix: usize,\n}\n\nimpl<'a> BoolColumn<'a> {\n fn new(grid: &'a BoolGrid, x: usize) -> Self {\n if x < grid.width {\n Self { grid, ix: x }\n } else {\n Self {\n grid,\n ix: usize::MAX,\n }\n }\n }\n}\n\nimpl<'a> Iterator for BoolColumn<'a> {\n type Item = bool;\n fn next(&mut self) -> Option {\n if self.ix < self.grid.content.len() {\n let result = self.grid.content[self.ix];\n self.ix += self.grid.width;\n Some(result)\n } else {\n None\n }\n }\n fn size_hint(&self) -> (usize, Option) {\n let len = self.grid.content.len();\n let result = (len - self.ix) / len;\n (result, Some(result))\n }\n}\n\npub struct BoolRow<'a> {\n grid: &'a BoolGrid,\n ix: usize,\n end: usize,\n}\n\nimpl<'a> BoolRow<'a> {\n fn new(grid: &'a BoolGrid, y: usize) -> Self {\n Self {\n grid,\n ix: y * grid.width,\n end: (y + 1) * grid.width,\n }\n }\n}\n\nimpl<'a> Iterator for BoolRow<'a> {\n type Item = bool;\n fn next(&mut self) -> Option {\n if self.ix < self.end && self.ix < self.grid.content.len() {\n let result = self.grid.content[self.ix];\n self.ix += 1;\n Some(result)\n } else {\n None\n }\n }\n fn size_hint(&self) -> (usize, Option) {\n let result = self.end - self.ix;\n (result, Some(result))\n }\n}\n"}]}},{"Edit":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":3,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":19},"to":{"change":3,"start":0,"end":27},"introduced_by":3}],"inode":{"change":3,"pos":32}}},"contents":[{"Del":"use crate::grid::BoolGrid;\n"}]}},{"Edit":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":162,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":2908},"to":{"change":3,"start":269,"end":290},"introduced_by":3}],"inode":{"change":3,"pos":32}}},"contents":[{"Del":" cache: BoolGrid,\n"}]}},{"Edit":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":176,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":410},"to":{"change":3,"start":410,"end":610},"introduced_by":3}],"inode":{"change":3,"pos":32}}},"contents":[{"Del":" let mut cache = BoolGrid::new();\n for (x, y) in db.list_preferences().await.unwrap_or_else(|_| Vec::new())\n {\n cache.set_transitive(x as usize, y as usize);\n }\n"}]}},{"Edit":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":182,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":605},"to":{"change":3,"start":611,"end":630},"introduced_by":3}],"inode":{"change":3,"pos":32}}},"contents":[{"Del":" cache,\n"}]}},{"Replacement":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":221,"ins":{"up_context":[{"change":2,"pos":606}],"down_context":[{"change":3,"pos":4219}],"flag":"BLOCK","start":0,"end":49,"inode":{"change":3,"pos":32}},"del":{"edges":[{"previous":"","flag":"DELETED","from":{"change":2,"pos":606},"to":{"change":3,"start":980,"end":1043},"introduced_by":2},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":4141},"to":{"change":3,"start":980,"end":1043},"introduced_by":3}],"inode":{"change":3,"pos":32}},"ins_contents":[{"Add":" match self.db.compare(a.1, b.1).await? {"}],"del_contents":[{"Del":" match self.cache.compare(a.1 as usize, b.1 as usize) {\n"}]}},{"Replacement":{"inode":{"change":3,"pos":32},"path":"src/pick.rs","line":265,"ins":{"up_context":[{"change":3,"pos":1157}],"down_context":[{"change":3,"pos":1467}],"flag":"BLOCK","start":50,"end":129,"inode":{"change":3,"pos":32}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":1157},"to":{"change":3,"start":1157,"end":1467},"introduced_by":3}],"inode":{"change":3,"pos":32}},"ins_contents":[{"Add":" self.db.insert_preference(better as i64, worse as i64).await?;"}],"del_contents":[{"Del":" self.cache.set_transitive(better as usize, worse as usize);\n {\n let tdb = self.db.clone();\n tokio::spawn(async move {\n tdb.insert_preference(better as i64, worse as i64).await\n });\n }\n"}]}},{"Replacement":{"inode":{"change":3,"pos":42},"path":"src/names_database.rs","line":78,"ins":{"up_context":[{"change":3,"pos":968}],"down_context":[{"change":3,"pos":2180}],"flag":"BLOCK","start":130,"end":1515,"inode":{"change":3,"pos":42}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":968},"to":{"change":3,"start":1469,"end":2801},"introduced_by":3}],"inode":{"change":3,"pos":42}},"ins_contents":[{"Add":" pub async fn compare("},{"Add":" &self,"},{"Add":" a: i64,"},{"Add":" b: i64,"},{"Add":" ) -> DynResult> {"},{"Add":" if a == b {"},{"Add":" return Ok(Some(std::cmp::Ordering::Equal));"},{"Add":" }"},{"Add":" Ok(self.post(move |conn| -> DynResult> {"},{"Add":" let mut stmnt = conn.prepare(\"WITH RECURSIVE t(better,worse) AS (SELECT better, worse FROM preferences WHERE preferences.worse IN (?,?) UNION SELECT preferences.better, t.worse FROM preferences INNER JOIN t ON preferences.worse = t.better) SELECT t.better, t.worse FROM t WHERE t.better IN (?,?) LIMIT 1\")?;"},{"Add":" stmnt.bind::(1,a)?;"},{"Add":" stmnt.bind::(2,b)?;"},{"Add":" stmnt.bind::(3,a)?;"},{"Add":" stmnt.bind::(4,b)?;"},{"Add":" match stmnt.next()? {"},{"Add":" sqlite::State::Done => Ok(None),"},{"Add":" sqlite::State::Row => {"},{"Add":" let better = stmnt.read::(0)?;"},{"Add":" let worse = stmnt.read::(1)?;"},{"Add":" if better == a && worse == b {"},{"Add":" Ok(Some(std::cmp::Ordering::Greater))"},{"Add":" } else if better == b && worse == a {"},{"Add":" Ok(Some(std::cmp::Ordering::Less))"},{"Add":" } else {"},{"Add":" Ok(Some(std::cmp::Ordering::Equal))"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }).await??)"},{"Add":" }"}],"del_contents":[{"Del":" // pub async fn compare(\n // &self,\n // a: i64,\n // b: i64,\n // ) -> DynResult> {\n // if a == b {\n // return Ok(Some(std::cmp::Ordering::Equal));\n // }\n // Ok(self.post(move |conn| -> DynResult> {\n // let mut stmnt = conn.prepare(\"SELECT better, worse FROM preferences WHERE (better = ? AND worse = ?) OR (better = ? AND worse = ?)\")?;\n // stmnt.bind::(1,a)?;\n // stmnt.bind::(2,b)?;\n // stmnt.bind::(3,b)?;\n // stmnt.bind::(4,a)?;\n // match stmnt.next()? {\n // sqlite::State::Done => Ok(None),\n // sqlite::State::Row => {\n // let better = stmnt.read::(0)?;\n // let worse = stmnt.read::(1)?;\n // if better == a && worse == b {\n // Ok(Some(std::cmp::Ordering::Greater))\n // } else if better == b && worse == a {\n // Ok(Some(std::cmp::Ordering::Less))\n // } else {\n // Ok(Some(std::cmp::Ordering::Equal))\n // }\n // }\n // }\n // }).await??)\n // }\n"}]}},{"Edit":{"inode":{"change":3,"pos":49},"path":"src/main.rs","line":5,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":222},"to":{"change":3,"start":3275,"end":3285},"introduced_by":3}],"inode":{"change":3,"pos":49}}},"contents":[{"Del":"mod grid;\n"}]}}],"owner":"quickdudley","repo":"namepick","token":"yNtZiacEuavHqOcmP4JarfkxCDspIqXMcK1Q/LhVdtY=","login":null}

…

Dependencies

Change contents