From a41476ac28083a2d8a54161d4177b3ee5c028525 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Fri, 12 Jan 2024 21:03:25 -0800 Subject: Start tuning the performance of rope. --- Cargo.lock | 555 +++++++++++++++++++++++++++++++++++++++++++++++++++++- Cargo.toml | 9 +- benches/concat.rs | 19 ++ src/lib.rs | 2 + src/main.rs | 10 +- src/rope.rs | 99 +++++----- 6 files changed, 634 insertions(+), 60 deletions(-) create mode 100644 benches/concat.rs create mode 100644 src/lib.rs diff --git a/Cargo.lock b/Cargo.lock index 1f1883e..22ce9a1 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -2,15 +2,566 @@ # It is not intended for manual editing. version = 3 +[[package]] +name = "aho-corasick" +version = "1.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b2969dcb958b36655471fc61f7e416fa76033bdd4bfed0678d8fee1e2d07a1f0" +dependencies = [ + "memchr", +] + +[[package]] +name = "anes" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4b46cbb362ab8752921c97e041f5e366ee6297bd428a31275b9fcf1e380f7299" + +[[package]] +name = "atty" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8" +dependencies = [ + "hermit-abi", + "libc", + "winapi", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "bitflags" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" + +[[package]] +name = "bumpalo" +version = "3.14.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f30e7476521f6f8af1a1c4c0b8cc94f0bee37d91763d0ca2665f299b6cd8aec" + +[[package]] +name = "cast" +version = "0.3.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "37b2a672a2cb129a2e41c10b1224bb368f9f37a2b16b612598138befd7b37eb5" + +[[package]] +name = "cfg-if" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "baf1de4339761588bc0619e3cbc0120ee582ebb74b53b4efbf79117bd2da40fd" + +[[package]] +name = "ciborium" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "effd91f6c78e5a4ace8a5d3c0b6bfaec9e2baaef55f3efc00e45fb2e477ee926" +dependencies = [ + "ciborium-io", + "ciborium-ll", + "serde", +] + +[[package]] +name = "ciborium-io" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cdf919175532b369853f5d5e20b26b43112613fd6fe7aee757e35f7a44642656" + +[[package]] +name = "ciborium-ll" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "defaa24ecc093c77630e6c15e17c51f5e187bf35ee514f4e2d67baaa96dae22b" +dependencies = [ + "ciborium-io", + "half", +] + +[[package]] +name = "clap" +version = "3.2.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4ea181bf566f71cb9a5d17a59e1871af638180a18fb0035c92ae62b705207123" +dependencies = [ + "bitflags", + "clap_lex", + "indexmap", + "textwrap", +] + +[[package]] +name = "clap_lex" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2850f2f5a82cbf437dd5af4d49848fbdfc27c157c3d010345776f952765261c5" +dependencies = [ + "os_str_bytes", +] + +[[package]] +name = "criterion" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e7c76e09c1aae2bc52b3d2f29e13c6572553b30c4aa1b8a49fd70de6412654cb" +dependencies = [ + "anes", + "atty", + "cast", + "ciborium", + "clap", + "criterion-plot", + "itertools", + "lazy_static", + "num-traits", + "oorandom", + "plotters", + "rayon", + "regex", + "serde", + "serde_derive", + "serde_json", + "tinytemplate", + "walkdir", +] + +[[package]] +name = "criterion-plot" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6b50826342786a51a89e2da3a28f1c32b06e387201bc2d19791f622c673706b1" +dependencies = [ + "cast", + "itertools", +] + +[[package]] +name = "crossbeam-deque" +version = "0.8.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "613f8cc01fe9cf1a3eb3d7f488fd2fa8388403e97039e2f73692932e291a770d" +dependencies = [ + "crossbeam-epoch", + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-epoch" +version = "0.9.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5b82ac4a3c2ca9c3460964f020e1402edd5753411d7737aa39c3714ad1b5420e" +dependencies = [ + "crossbeam-utils", +] + +[[package]] +name = "crossbeam-utils" +version = "0.8.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "248e3bacc7dc6baa3b21e405ee045c3047101a49145e7e9eca583ab4c2ca5345" + [[package]] name = "edit" version = "1.0.0" dependencies = [ + "criterion", "libc", ] +[[package]] +name = "either" +version = "1.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07" + +[[package]] +name = "half" +version = "1.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "eabb4a44450da02c90444cf74558da904edde8fb4e9035a9a6a4e15445af0bd7" + +[[package]] +name = "hashbrown" +version = "0.12.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888" + +[[package]] +name = "hermit-abi" +version = "0.1.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62b467343b94ba476dcb2500d242dadbb39557df889310ac77c5d99100aaac33" +dependencies = [ + "libc", +] + +[[package]] +name = "indexmap" +version = "1.9.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99" +dependencies = [ + "autocfg", + "hashbrown", +] + +[[package]] +name = "itertools" +version = "0.10.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b0fd2260e829bddf4cb6ea802289de2f86d6a7a690192fbe91b3f46e0f2c8473" +dependencies = [ + "either", +] + +[[package]] +name = "itoa" +version = "1.0.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1a46d1a171d865aa5f83f92695765caa047a9b4cbae2cbf37dbd613a793fd4c" + +[[package]] +name = "js-sys" +version = "0.3.67" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9a1d36f1235bc969acba30b7f5990b864423a6068a10f7c90ae8f0112e3a59d1" +dependencies = [ + "wasm-bindgen", +] + +[[package]] +name = "lazy_static" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" + [[package]] name = "libc" -version = "0.2.151" +version = "0.2.152" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "13e3bf6590cbc649f4d1a3eefc9d5d6eb746f5200ffb04e5e142700b8faa56e7" + +[[package]] +name = "log" +version = "0.4.20" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5e6163cb8c49088c2c36f57875e58ccd8c87c7427f7fbd50ea6710b2f3f2e8f" + +[[package]] +name = "memchr" +version = "2.7.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "523dc4f511e55ab87b694dc30d0f820d60906ef06413f93d4d7a1385599cc149" + +[[package]] +name = "num-traits" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "39e3200413f237f41ab11ad6d161bc7239c84dcb631773ccd7de3dfe4b5c267c" +dependencies = [ + "autocfg", +] + +[[package]] +name = "once_cell" +version = "1.19.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3fdb12b2476b595f9358c5161aa467c2438859caa136dec86c26fdd2efe17b92" + +[[package]] +name = "oorandom" +version = "11.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0ab1bc2a289d34bd04a330323ac98a1b4bc82c9d9fcb1e66b63caa84da26b575" + +[[package]] +name = "os_str_bytes" +version = "6.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2355d85b9a3786f481747ced0e0ff2ba35213a1f9bd406ed906554d7af805a1" + +[[package]] +name = "plotters" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d2c224ba00d7cadd4d5c660deaf2098e5e80e07846537c51f9cfa4be50c1fd45" +dependencies = [ + "num-traits", + "plotters-backend", + "plotters-svg", + "wasm-bindgen", + "web-sys", +] + +[[package]] +name = "plotters-backend" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9e76628b4d3a7581389a35d5b6e2139607ad7c75b17aed325f210aa91f4a9609" + +[[package]] +name = "plotters-svg" +version = "0.3.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "38f6d39893cca0701371e3c27294f09797214b86f1fb951b89ade8ec04e2abab" +dependencies = [ + "plotters-backend", +] + +[[package]] +name = "proc-macro2" +version = "1.0.76" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "95fc56cda0b5c3325f5fbbd7ff9fda9e02bb00bb3dac51252d2f1bfa1cb8cc8c" +dependencies = [ + "unicode-ident", +] + +[[package]] +name = "quote" +version = "1.0.35" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "291ec9ab5efd934aaf503a6466c5d5251535d108ee747472c3977cc5acc868ef" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rayon" +version = "1.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c27db03db7734835b3f53954b534c91069375ce6ccaa2e065441e07d9b6cdb1" +dependencies = [ + "either", + "rayon-core", +] + +[[package]] +name = "rayon-core" +version = "1.12.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5ce3fb6ad83f861aac485e76e1985cd109d9a3713802152be56c3b1f0e0658ed" +dependencies = [ + "crossbeam-deque", + "crossbeam-utils", +] + +[[package]] +name = "regex" +version = "1.10.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "380b951a9c5e80ddfd6136919eef32310721aa4aacd4889a8d39124b026ab343" +dependencies = [ + "aho-corasick", + "memchr", + "regex-automata", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5f804c7828047e88b2d32e2d7fe5a105da8ee3264f01902f796c8e067dc2483f" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-syntax" +version = "0.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08c74e62047bb2de4ff487b251e4a92e24f48745648451635cec7d591162d9f" + +[[package]] +name = "ryu" +version = "1.0.16" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f98d2aa92eebf49b69786be48e4477826b256916e84a57ff2a4f21923b48eb4c" + +[[package]] +name = "same-file" +version = "1.0.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93fc1dc3aaa9bfed95e02e6eadabb4baf7e3078b0bd1b4d7b6b0b68378900502" +dependencies = [ + "winapi-util", +] + +[[package]] +name = "serde" +version = "1.0.195" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "63261df402c67811e9ac6def069e4786148c4563f4b50fd4bf30aa370d626b02" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.195" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "46fe8f8603d81ba86327b23a2e9cdf49e1255fb94a4c5f297f6ee0547178ea2c" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.111" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "176e46fa42316f18edd598015a5166857fc835ec732f5215eac6b7bdbf0a84f4" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "syn" +version = "2.0.48" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0f3531638e407dfc0814761abb7c00a5b54992b849452a0646b7f65c9f770f3f" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "textwrap" +version = "0.16.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "222a222a5bfe1bba4a77b45ec488a741b3cb8872e5e499451fd7d0129c9c7c3d" + +[[package]] +name = "tinytemplate" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "be4d6b5f19ff7664e8c98d03e2139cb510db9b0a60b55f8e8709b689d939b6bc" +dependencies = [ + "serde", + "serde_json", +] + +[[package]] +name = "unicode-ident" +version = "1.0.12" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" + +[[package]] +name = "walkdir" +version = "2.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d71d857dc86794ca4c280d616f7da00d2dbfd8cd788846559a6813e6aa4b54ee" +dependencies = [ + "same-file", + "winapi-util", +] + +[[package]] +name = "wasm-bindgen" +version = "0.2.90" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1223296a201415c7fad14792dbefaace9bd52b62d33453ade1c5b5f07555406" +dependencies = [ + "cfg-if", + "wasm-bindgen-macro", +] + +[[package]] +name = "wasm-bindgen-backend" +version = "0.2.90" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fcdc935b63408d58a32f8cc9738a0bffd8f05cc7c002086c6ef20b7312ad9dcd" +dependencies = [ + "bumpalo", + "log", + "once_cell", + "proc-macro2", + "quote", + "syn", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-macro" +version = "0.2.90" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3e4c238561b2d428924c49815533a8b9121c664599558a5d9ec51f8a1740a999" +dependencies = [ + "quote", + "wasm-bindgen-macro-support", +] + +[[package]] +name = "wasm-bindgen-macro-support" +version = "0.2.90" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bae1abb6806dc1ad9e560ed242107c0f6c84335f1749dd4e8ddb012ebd5e25a7" +dependencies = [ + "proc-macro2", + "quote", + "syn", + "wasm-bindgen-backend", + "wasm-bindgen-shared", +] + +[[package]] +name = "wasm-bindgen-shared" +version = "0.2.90" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4d91413b1c31d7539ba5ef2451af3f0b833a005eb27a631cec32bc0635a8602b" + +[[package]] +name = "web-sys" +version = "0.3.67" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "58cd2333b6e0be7a39605f0e255892fd7418a682d8da8fe042fe25128794d2ed" +dependencies = [ + "js-sys", + "wasm-bindgen", +] + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-util" +version = "0.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f29e6f9198ba0d26b4c9f07dbe6f9ed633e1f3d5b8b414090084349e46a52596" +dependencies = [ + "winapi", +] + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "302d7ab3130588088d277783b1e2d2e10c9e9e4a16dd9050e6ec93fb3e7048f4" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/Cargo.toml b/Cargo.toml index 4242509..cf6c655 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -6,4 +6,11 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] -"libc" = "0.2" +libc = "0.2" + +[dev-dependencies] +criterion = { version = "0.4", features = ["html_reports"] } + +[[bench]] +name = "concat" +harness = false diff --git a/benches/concat.rs b/benches/concat.rs new file mode 100644 index 0000000..a07f908 --- /dev/null +++ b/benches/concat.rs @@ -0,0 +1,19 @@ +use criterion::{black_box, criterion_group, criterion_main, Criterion}; + +use edit::rope::Rope; + +fn concat(buf: &[u8]) -> Rope { + let mut r = Rope::new(&[]); + for &b in buf.iter() { + r = r.concat(&Rope::new(&[b])); + } + r +} + +fn criterion_benchmark(c: &mut Criterion) { + let bytes = vec![0; 10000]; + c.bench_function("concat asdfasdf", |b| b.iter(|| concat(black_box(&bytes)))); +} + +criterion_group!(benches, criterion_benchmark); +criterion_main!(benches); diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..a382743 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,2 @@ +pub mod rope; +pub mod term; diff --git a/src/main.rs b/src/main.rs index b40d9b1..5b9d2f5 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,14 +1,12 @@ -mod rope; -mod term; - -use rope::Rope; +use edit::rope::Rope; +use edit::term; +use edit::term::Key; +use edit::term::Reader; use std::error::Error; use std::ffi::{OsStr, OsString}; use std::fs::File; use std::io::{stderr, stdout, Write}; use std::path::{Path, PathBuf}; -use term::Key; -use term::Reader; fn open(file: &Path) -> Result { let mut f = File::open(file)?; diff --git a/src/rope.rs b/src/rope.rs index 8bda5af..930c88a 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -9,10 +9,11 @@ enum Insert { } #[derive(Debug, Clone)] -pub struct Leaf { +struct Leaf { unsafe_buf: Option>, start: u16, end: u16, + lines: u16, } impl Leaf { @@ -25,23 +26,16 @@ impl Leaf { } #[derive(Debug, Clone)] -pub struct Branch { - unsafe_children: [Rope; 3], +struct Branch { + children: Rc<[Rope]>, len: usize, lines: usize, - n_children: u8, -} - -impl Branch { - fn children(&self) -> &[Rope] { - &self.unsafe_children[..usize::from(self.n_children)] - } } #[derive(Debug, Clone)] enum Node { Leaf(Leaf), - Branch(Rc), + Branch(Branch), } #[derive(Debug, Clone)] @@ -57,15 +51,7 @@ impl Rope { pub fn lines(&self) -> usize { match self { - Rope(Node::Leaf(l)) => { - let mut lines = 0; - for &b in l.bytes().iter() { - if b == b'\n' { - lines += 1; - } - } - lines - } + Rope(Node::Leaf(l)) => usize::from(l.lines), Rope(Node::Branch(b)) => b.lines, } } @@ -79,12 +65,20 @@ impl Rope { unsafe_buf: None, start: 0, end: 0, + lines: 0, })); } + let mut lines = 0; + for &b in buf.iter() { + if b == b'\n' { + lines += 1; + } + } Rope(Node::Leaf(Leaf { unsafe_buf: Some(Rc::from(buf)), start: 0, end: u16::try_from(buf.len()).expect("buf.len() <= MAX_NODE_SIZE"), + lines, })) } @@ -95,17 +89,11 @@ impl Rope { len += c.len(); lines += c.lines(); } - let mut child_array = [Rope::leaf(&[]), Rope::leaf(&[]), Rope::leaf(&[])]; - for (i, c) in children.iter().enumerate() { - child_array[i] = c.clone(); - } - Rope(Node::Branch(Rc::new(Branch { - unsafe_children: child_array, + Rope(Node::Branch(Branch { + children: Rc::from(children), len, lines, - n_children: u8::try_from(children.len()) - .expect("there should only ever be 2 or 3 children"), - }))) + })) } fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert { @@ -134,26 +122,26 @@ impl Rope { let Rope(Node::Branch(b)) = self else { panic!("self_height is at least 1, so it's a branch"); }; - match b.children()[b.children().len() - 1].concat_height( + match b.children[b.children.len() - 1].concat_height( self_height - 1, other, other_height, ) { Insert::Node(new_child) => { - let mut new_children = b.children().to_vec(); - new_children[b.children().len() - 1] = new_child; + let mut new_children = b.children.to_vec(); + new_children[b.children.len() - 1] = new_child; return Insert::Node(Rope::branch(&new_children)); } Insert::Split(child1, child2) => { - if b.children().len() == 2 { + if b.children.len() == 2 { return Insert::Node(Rope::branch(&[ - b.children()[0].clone(), + b.children[0].clone(), child1, child2, ])); } return Insert::Split( - Rope::branch(&[b.children()[0].clone(), b.children()[1].clone()]), + Rope::branch(&[b.children[0].clone(), b.children[1].clone()]), Rope::branch(&[child1, child2]), ); } @@ -162,19 +150,19 @@ impl Rope { let Rope(Node::Branch(b)) = other else { panic!("other_height is at least 1, so it's a branch"); }; - match self.concat_height(self_height, &b.children()[0], other_height - 1) { + match self.concat_height(self_height, &b.children[0], other_height - 1) { Insert::Node(new_child) => { - let mut new_children = b.children().to_vec(); + let mut new_children = b.children.to_vec(); new_children[0] = new_child; Insert::Node(Rope::branch(&new_children)) } Insert::Split(child1, child2) => { - if b.children().len() == 2 { - return Insert::Node(Rope::branch(&[child1, child2, b.children()[1].clone()])); + if b.children.len() == 2 { + return Insert::Node(Rope::branch(&[child1, child2, b.children[1].clone()])); } Insert::Split( Rope::branch(&[child1, child2]), - Rope::branch(&[b.children()[1].clone(), b.children()[2].clone()]), + Rope::branch(&[b.children[1].clone(), b.children[2].clone()]), ) } } @@ -183,7 +171,7 @@ impl Rope { fn height(&self) -> usize { match self { Rope(Node::Leaf(_)) => 0, - Rope(Node::Branch(b)) => 1 + b.children()[0].height(), + Rope(Node::Branch(b)) => 1 + b.children[0].height(), } } @@ -225,7 +213,7 @@ impl Rope { } Rope(Node::Branch(b)) => { let mut i = i; - for c in b.children().iter() { + for c in b.children.iter() { if i < c.len() { return c.is_char_boundary(i); } @@ -271,7 +259,7 @@ impl Rope { Rope(Node::Branch(b)) => { let mut n = n; let mut offset = 0; - for c in b.children().iter() { + for c in b.children.iter() { if n < c.lines() { return offset + c.line_end(n); } @@ -304,7 +292,7 @@ impl Rope { Ok(()) } Rope(Node::Branch(b)) => { - for c in b.children().iter() { + for c in b.children.iter() { c.print(w)?; } Ok(()) @@ -330,16 +318,25 @@ impl Rope { return self.clone(); } match self { - Rope(Node::Leaf(l)) => Rope(Node::Leaf(Leaf { - unsafe_buf: l.unsafe_buf.clone(), - start: l.start + u16::try_from(start).expect("start <= self.len()"), - end: l.start + u16::try_from(end).expect("end <= self.len()"), - })), + Rope(Node::Leaf(l)) => { + let mut lines = 0; + for &b in l.bytes()[start..end].iter() { + if b == b'\n' { + lines += 1; + } + } + Rope(Node::Leaf(Leaf { + unsafe_buf: l.unsafe_buf.clone(), + start: l.start + u16::try_from(start).expect("start <= self.len()"), + end: l.start + u16::try_from(end).expect("end <= self.len()"), + lines, + })) + } Rope(Node::Branch(b)) => { let mut s = Rope::new(&[]); let mut start = start; let mut end = end; - for c in b.children().iter() { + for c in b.children.iter() { if start >= c.len() { start -= c.len(); end -= c.len(); @@ -365,7 +362,7 @@ impl Rope { Rope(Node::Leaf(l)) => l.bytes()[i], Rope(Node::Branch(b)) => { let mut i = i; - for c in b.children().iter() { + for c in b.children.iter() { if i < c.len() { return c.byte(i); } -- cgit v1.3.1