Repository: tweag/nickel
Pull request #2057 (2024-09-27 15:47:06)

Use a persistent vector instead of an `Rc<[..]>`
This is an experiment regarding array performance. Our current array representation (as essentially a `Rc<[RichTerm]>`) is problematic because it makes many common operations unnecessarily quadratic. This PR replaces it with a `rpds::Vector<RichTerm>` in reverse order, and the initial benchmarks look promising.

In more detail, the current arrays have a few performance characteristics that we might like to keep:
- constant-time random access
- constant-time slicing
- some amount of memory sharing
The main problem is that there's no constant-time "cons" operation, and the concatenation operator `xs @ ys` is `O(xs.len() + ys.len())`. This makes many functional-style list functions (like the stdlib implementations of `reverse` and `filter`) quadratic in the length of their input.

The `Vector` implementation in the `rpds` crate is a "persistent vector" aka "bitmapped vector trie", which offers persistence/sharing, fast random access, and fast appends. We can do the same slicing trick that we're current using for `Rc<[RichTerm]>` to also add fast slicing. Thanks to fast appends, we can do concatenation `xs @ ys` in `O(ys.len())` time (provided that there are no contracts that need to be applied to `xs`; I'm also ignoring logarithmic terms). This is backwards from the more common concatenation pattern in functional languages, so we store arrays backwards in order to get time `O(xs.len())` instead. (We could achieve the minimum of the two by storing an array as *two* `Vectors`, a backwards one followed by a forwards one.)

There are a few ways in which `rpds::Vector` isn't a perfect fit:
- it insists on wrapping the vector elements in `Arc` or `Rc`, which we don't want because `RichTerm` already has a shared pointer
- it doesn't support many of the optimizations we had for arrays with a single reference
- there's no fast iteration over slices (it's linear in the number of elements you skip at the beginning)

Despite these, this PR gives a 35% improvement in `random normal`, and a few other improvements between 10 and 20%. I'd like to also try benchmarking `im` and/or `imbl`. 

github-actions[bot]: <h2><a href="https://bencher.dev/perf/nickel/reports/69059fcd-4224-4e8d-9ef3-733be2bf84fc?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel"><img src="https://bencher.dev/favicon.svg" width="24" height="24" alt="🐰" /> Bencher Report</a></h2><table><tr><td>Branch</td><td><a href="https://bencher.dev/perf/nickel/branches/2057-merge?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">2057/merge</a></td></tr><tr><td>Testbed</td><td><a href="https://bencher.dev/perf/nickel/testbeds/ubuntu-latest?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">ubuntu-latest</a></td></tr></table><blockquote><p><b>⚠️ WARNING:</b> The following Measure does not have a Threshold. Without a Threshold, no Alerts will ever be generated!</p><ul><li><a href="https://bencher.dev/perf/nickel/measures/latency?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">Latency</a></li></ul><p><a href="https://bencher.dev/console/projects/nickel/thresholds/add?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">Click here to create a new Threshold</a><br/>For more information, see <a href="https://bencher.dev/docs/explanation/thresholds/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">the Threshold documentation</a>.<br/>To only post results if a Threshold exists, set <a href="https://bencher.dev/docs/explanation/bencher-run/#--ci-only-thresholds?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">the <code lang="rust">--ci-only-thresholds</code> CLI flag</a>.</p></blockquote><details><summary>Click to view all benchmark results</summary><br/><table><thead><tr><th>Benchmark</th><th><a href="https://bencher.dev/perf/nickel/measures/latency?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">Latency</a></th><th>nanoseconds (ns)</th></tr></thead><tbody><tr><td><a href="https://bencher.dev/perf/nickel/benchmarks/fibonacci-10?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">fibonacci 10</a></td><td>📈 <a href="https://bencher.dev/perf/nickel?branches=6b46a7c8-3d23-4304-bc4b-079574b2eee5&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=3cfaf19e-c9c5-4341-95cd-703456d0fc9f&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1724860556000&end_time=1727452556000&report=69059fcd-4224-4e8d-9ef3-733be2bf84fc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">view plot</a><br/>⚠️ NO THRESHOLD</td><td>484,050.00</td></tr><tr><td><a href="https://bencher.dev/perf/nickel/benchmarks/pidigits-100?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">pidigits 100</a></td><td>📈 <a href="https://bencher.dev/perf/nickel?branches=6b46a7c8-3d23-4304-bc4b-079574b2eee5&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=5be25c57-d46f-4b48-b6f0-dee01b84220a&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1724860556000&end_time=1727452556000&report=69059fcd-4224-4e8d-9ef3-733be2bf84fc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">view plot</a><br/>⚠️ NO THRESHOLD</td><td>3,235,100.00</td></tr><tr><td><a href="https://bencher.dev/perf/nickel/benchmarks/product-30?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">product 30</a></td><td>📈 <a href="https://bencher.dev/perf/nickel?branches=6b46a7c8-3d23-4304-bc4b-079574b2eee5&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=2f5f7f6a-4e54-4542-aa09-da5671953fbb&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1724860556000&end_time=1727452556000&report=69059fcd-4224-4e8d-9ef3-733be2bf84fc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">view plot</a><br/>⚠️ NO THRESHOLD</td><td>762,080.00</td></tr><tr><td><a href="https://bencher.dev/perf/nickel/benchmarks/scalar-10?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">scalar 10</a></td><td>📈 <a href="https://bencher.dev/perf/nickel?branches=6b46a7c8-3d23-4304-bc4b-079574b2eee5&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=211bb66a-58f8-488b-97e4-7ea032870038&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1724860556000&end_time=1727452556000&report=69059fcd-4224-4e8d-9ef3-733be2bf84fc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">view plot</a><br/>⚠️ NO THRESHOLD</td><td>1,436,200.00</td></tr><tr><td><a href="https://bencher.dev/perf/nickel/benchmarks/sum-30?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">sum 30</a></td><td>📈 <a href="https://bencher.dev/perf/nickel?branches=6b46a7c8-3d23-4304-bc4b-079574b2eee5&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=3f1710c5-ce75-4dfb-aadb-1435fed8a093&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1724860556000&end_time=1727452556000&report=69059fcd-4224-4e8d-9ef3-733be2bf84fc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">view plot</a><br/>⚠️ NO THRESHOLD</td><td>755,350.00</td></tr></tbody></table></details><a href="https://bencher.dev/perf/nickel/reports/69059fcd-4224-4e8d-9ef3-733be2bf84fc?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel">🐰 View full continuous benchmarking report in Bencher</a><div id="bencher.dev/projects/nickel/id/2057-merge/ubuntu-latest/rust_criterion"></div>
yannham: I'll see what it gives on the private benchmark
jneem: I tried out imbl, but the performance is worse than rpds.
jneem: The current version uses a custom re-implementation of persistent vectors, and it seems to be a performance win across the board.
jneem: Github CI agrees with my local benchmarking: this gives modest gains in general, and big gains whenever quadratic array behavior is the bottleneck.

I don't see a nice UI for comparing results to master, but [here](https://bencher.dev/perf/nickel/reports/1ce2638e-e26f-4e88-83fd-0c1e040870b5?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=nickel) is the report for this PR and [here](https://bencher.dev/console/projects/nickel/perf?key=true&reports_per_page=4&branches_per_page=8&testbeds_per_page=8&benchmarks_per_page=8&plots_per_page=8&reports_page=5&branches_page=1&testbeds_page=1&benchmarks_page=1&plots_page=1&branches=0cc3f3b8-c7ca-4c64-ae2e-4a8cb0321ae9%2C51cee694-d6d7-4a12-9558-d17d65bbcefc&heads=0cc3f3b8-c7ca-4c64-ae2e-4a8cb0321ae9%2C51cee694-d6d7-4a12-9558-d17d65bbcefc&testbeds=66263ed0-9556-4385-9f30-26466ee26211&benchmarks=3cfaf19e-c9c5-4341-95cd-703456d0fc9f%2C95048806-9bf2-49e4-88f2-dbcd66cbf68a%2C15373c31-496e-4f43-bbb4-466ef49fdd87%2C87746452-c4df-48ea-b5e9-8d66f82ca556%2C7f141ea0-9fbb-4305-bb63-78f163e546d6%2C8c154d79-dc68-4d93-abb3-83183a62f6a2%2C6d0222f6-0b85-4eaf-8c5c-e8957c522ef9%2Cbe0d3f87-d089-4b81-af44-3bbc6e831697%2C2946df33-45e4-4282-b749-040582021fe3%2C5be25c57-d46f-4b48-b6f0-dee01b84220a&measures=2b5b9371-696f-422d-b1a5-262ce8157b6b&start_time=1726334930000&end_time=1728926930000&lower_boundary=false&upper_boundary=false&clear=true&tab=reports&branches_search=master&report=cbb2bf66-e006-406c-9697-00742ff43874) is the report for master.
jneem: Yes, I forgot to mention that. Performance is basically identical on all three sizes.

Patch:
diff --git a/Cargo.lock b/Cargo.lock
index 2c3141a0..f12152ae 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -108,6 +108,33 @@ version = "1.0.80"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "5ad32ce52e4161730f7098c077cd2ed6229b5804ccf99e5366be1ab72a98b4e1"
 
+[[package]]
+name = "arbitrary"
+version = "1.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7d5a26814d8dcb93b0e5a0ff3c6d80a8843bafb21b39e8e18a6f05471870e110"
+dependencies = [
+ "derive_arbitrary",
+]
+
+[[package]]
+name = "arbtest"
+version = "0.3.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "23909d5fb517fac2a8a4c887e847dbe41dd22ec46914586f5727980d0a193fdc"
+dependencies = [
+ "arbitrary",
+]
+
+[[package]]
+name = "archery"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "eae2ed21cd55021f05707a807a5fc85695dafb98832921f6cfa06db67ca5b869"
+dependencies = [
+ "triomphe",
+]
+
 [[package]]
 name = "arrayvec"
 version = "0.5.2"
@@ -252,6 +279,12 @@ version = "2.4.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "ed570934406eb16438a4e976b1b4500774099c13b8cb96eec99f620f05090ddf"
 
+[[package]]
+name = "bitmaps"
+version = "3.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a1d084b0137aaa901caf9f1e8b21daa6aa24d41cd806e111335541eff9683bd6"
+
 [[package]]
 name = "block-buffer"
 version = "0.10.4"
@@ -547,6 +580,32 @@ dependencies = [
  "walkdir",
 ]
 
+[[package]]
+name = "criterion"
+version = "0.5.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f2b12d017a929603d80db1831cd3a24082f8137ce19c69e6447f54f5fc8d692f"
+dependencies = [
+ "anes",
+ "cast",
+ "ciborium",
+ "clap 4.5.2",
+ "criterion-plot",
+ "is-terminal",
+ "itertools 0.10.5",
+ "num-traits",
+ "once_cell",
+ "oorandom",
+ "plotters",
+ "rayon",
+ "regex",
+ "serde",
+ "serde_derive",
+ "serde_json",
+ "tinytemplate",
+ "walkdir",
+]
+
 [[package]]
 name = "criterion-plot"
 version = "0.5.0"
@@ -772,6 +831,17 @@ dependencies = [
  "powerfmt",
 ]
 
+[[package]]
+name = "derive_arbitrary"
+version = "1.3.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "67e77553c4162a157adbf834ebae5b415acbecbeafc7a74b0e886657506a7611"
+dependencies = [
+ "proc-macro2 1.0.78",
+ "quote 1.0.35",
+ "syn 2.0.52",
+]
+
 [[package]]
 name = "derive_builder"
 version = "0.20.0"
@@ -1262,6 +1332,15 @@ dependencies = [
  "unicode-normalization",
 ]
 
+[[package]]
+name = "imbl-sized-chunks"
+version = "0.1.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "144006fb58ed787dcae3f54575ff4349755b00ccc99f4b4873860b654be1ed63"
+dependencies = [
+ "bitmaps",
+]
+
 [[package]]
 name = "indexmap"
 version = "1.9.3"
@@ -1765,7 +1844,7 @@ dependencies = [
  "codespan",
  "codespan-reporting",
  "comrak",
- "criterion",
+ "criterion 0.4.0",
  "cxx",
  "cxx-build",
  "indexmap 1.9.3",
@@ -1779,6 +1858,7 @@ dependencies = [
  "md-5",
  "metrics",
  "nickel-lang-utils",
+ "nickel-lang-vector",
  "once_cell",
  "pkg-config",
  "pretty",
@@ -1822,7 +1902,7 @@ dependencies = [
  "clap 4.5.2",
  "codespan",
  "codespan-reporting",
- "criterion",
+ "criterion 0.4.0",
  "crossbeam",
  "csv",
  "derive_more",
@@ -1853,13 +1933,25 @@ name = "nickel-lang-utils"
 version = "0.1.0"
 dependencies = [
  "codespan",
- "criterion",
+ "criterion 0.4.0",
  "nickel-lang-core",
  "pprof",
  "serde",
  "toml",
 ]
 
+[[package]]
+name = "nickel-lang-vector"
+version = "0.1.0"
+dependencies = [
+ "arbitrary",
+ "arbtest",
+ "criterion 0.5.1",
+ "imbl-sized-chunks",
+ "rpds",
+ "serde",
+]
+
 [[package]]
 name = "nickel-wasm-repl"
 version = "0.9.0"
@@ -2114,7 +2206,7 @@ checksum = "196ded5d4be535690899a4631cc9f18cdc41b7ebf24a79400f46f48e49a11059"
 dependencies = [
  "backtrace",
  "cfg-if",
- "criterion",
+ "criterion 0.4.0",
  "findshlibs",
  "inferno",
  "libc",
@@ -2436,6 +2528,15 @@ dependencies = [
  "bytemuck",
 ]
 
+[[package]]
+name = "rpds"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a0e15515d3ce3313324d842629ea4905c25a13f81953eadb88f85516f59290a4"
+dependencies = [
+ "archery",
+]
+
 [[package]]
 name = "rustc-demangle"
 version = "0.1.23"
@@ -3194,6 +3295,12 @@ dependencies = [
  "tree-sitter",
 ]
 
+[[package]]
+name = "triomphe"
+version = "0.1.13"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6631e42e10b40c0690bf92f404ebcfe6e1fdb480391d15f17cc8e96eeed5369"
+
 [[package]]
 name = "typed-arena"
 version = "2.0.2"
diff --git a/Cargo.toml b/Cargo.toml
index d1771546..0c0026ef 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -2,6 +2,7 @@
 members = [
     "core",
     "cli",
+    "vector",
     "lsp/nls",
     "lsp/lsp-harness",
     "utils",
@@ -22,6 +23,7 @@ readme = "README.md"
 
 [workspace.dependencies]
 nickel-lang-core = { version = "0.9.0", path = "./core", default-features = false }
+nickel-lang-vector = { version = "0.1.0", path = "./vector" }
 nickel-lang-utils = { version = "0.1.0", path = "./utils" }
 lsp-harness = { version = "0.1.0", path = "./lsp/lsp-harness" }
 
diff --git a/core/Cargo.toml b/core/Cargo.toml
index 3b91f853..eb3a7915 100644
--- a/core/Cargo.toml
+++ b/core/Cargo.toml
@@ -44,6 +44,7 @@ codespan.workspace = true
 codespan-reporting.workspace = true
 cxx = { workspace = true, optional = true }
 logos.workspace = true
+nickel-lang-vector.workspace = true
 smallvec.workspace = true
 serde = { workspace = true, features = ["derive"] }
 serde_json.workspace = true
diff --git a/core/benches/arrays.rs b/core/benches/arrays.rs
index 6634f48e..ec5f6980 100644
--- a/core/benches/arrays.rs
+++ b/core/benches/arrays.rs
@@ -1,12 +1,7 @@
 #![cfg_attr(feature = "benchmark-ci", allow(unused_imports))]
 
-use std::rc::Rc;
-
 use criterion::criterion_main;
-use nickel_lang_core::term::{
-    array::{Array, ArrayAttrs},
-    Number, RichTerm, Term,
-};
+use nickel_lang_core::term::{array::ArrayAttrs, Number, RichTerm, Term};
 use nickel_lang_utils::{bench::criterion_config, bench::EvalMode, ncl_bench_group};
 use pretty::{BoxAllocator, DocBuilder, Pretty};
 
@@ -26,7 +21,7 @@ fn ncl_random_array(len: usize) -> String {
     }
 
     let xs = RichTerm::from(Term::Array(
-        Array::new(Rc::from(numbers)),
+        numbers.into_iter().collect(),
         ArrayAttrs::default(),
     ));
     let doc: DocBuilder<_, ()> = xs.pretty(&BoxAllocator);
diff --git a/core/src/cache.rs b/core/src/cache.rs
index 9d213b8e..e52e4e3e 100644
--- a/core/src/cache.rs
+++ b/core/src/cache.rs
@@ -10,7 +10,6 @@ use crate::parser::{lexer::Lexer, ErrorTolerantParser};
 use crate::position::TermPos;
 use crate::program::FieldPath;
 use crate::stdlib::{self as nickel_stdlib, StdlibModule};
-use crate::term::array::Array;
 use crate::term::record::{Field, RecordData};
 use crate::term::{RichTerm, SharedTerm, Term};
 use crate::transform::import_resolution;
@@ -27,7 +26,6 @@ use std::ffi::{OsStr, OsString};
 use std::fs;
 use std::io;
 use std::path::{Path, PathBuf};
-use std::rc::Rc;
 use std::result::Result;
 use std::time::SystemTime;
 use void::Void;
@@ -607,11 +605,7 @@ impl Cache {
                 } else {
                     Ok((
                         attach_pos(
-                            Term::Array(
-                                Array::new(Rc::from(terms.into_boxed_slice())),
-                                Default::default(),
-                            )
-                            .into(),
+                            Term::Array(terms.into_iter().collect(), Default::default()).into(),
                         ),
                         ParseErrors::default(),
                     ))
diff --git a/core/src/deserialize.rs b/core/src/deserialize.rs
index e86a963b..3feef79d 100644
--- a/core/src/deserialize.rs
+++ b/core/src/deserialize.rs
@@ -9,7 +9,7 @@ use serde::de::{
 };
 
 use crate::identifier::LocIdent;
-use crate::term::array::{self, Array};
+use crate::term::array::Array;
 use crate::term::record::Field;
 use crate::term::{IndexMap, RichTerm, Term};
 
@@ -329,7 +329,7 @@ impl<'de> serde::Deserializer<'de> for RichTerm {
 }
 
 struct ArrayDeserializer {
-    iter: array::IntoIter,
+    iter: <Array as IntoIterator>::IntoIter,
 }
 
 impl ArrayDeserializer {
@@ -377,8 +377,7 @@ where
     let len = array.len();
     let mut deserializer = ArrayDeserializer::new(array);
     let seq = visitor.visit_seq(&mut deserializer)?;
-    let remaining = deserializer.iter.len();
-    if remaining == 0 {
+    if deserializer.iter.next().is_none() {
         Ok(seq)
     } else {
         Err(RustDeserializationError::InvalidArrayLength(len))
diff --git a/core/src/eval/operation.rs b/core/src/eval/operation.rs
index 2efc7ead..c5a7b5f5 100644
--- a/core/src/eval/operation.rs
+++ b/core/src/eval/operation.rs
@@ -30,7 +30,7 @@ use crate::{
     serialize::ExportFormat,
     stdlib::internals,
     term::{
-        array::{Array, ArrayAttrs, OutOfBoundError},
+        array::{Array, ArrayAttrs},
         make as mk_term,
         record::*,
         string::NickelString,
@@ -56,7 +56,7 @@ use md5::digest::Digest;
 use simple_counter::*;
 use unicode_segmentation::UnicodeSegmentation;
 
-use std::{convert::TryFrom, iter::Extend, rc::Rc};
+use std::{convert::TryFrom, iter::Extend};
 
 generate_counter!(FreshVariableCounter, usize);
 
@@ -2332,6 +2332,7 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
             BinaryOp::ArrayConcat => match_sharedterm!(match (t1) {
                 Term::Array(ts1, attrs1) => match_sharedterm!(match (t2) {
                     Term::Array(ts2, attrs2) => {
+                        let mut ts1 = ts1;
                         // NOTE: the [eval_closure] function in [eval] should've made sure
                         // that the array is closurized. We leave a debug_assert! here just
                         // in case something goes wrong in the future. If the assert failed,
@@ -2345,19 +2346,6 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                             "the right-hand side of ArrayConcat (@) is not closurized."
                         );
 
-                        // NOTE: To avoid the extra Vec allocation, we could use
-                        // Rc<[T]>::new_uninit_slice() and fill up the slice manually, but
-                        // that's a nightly-only experimental API. Note that collecting into
-                        // an Rc<[T]> will also allocate a intermediate vector, unless the
-                        // input iterator implements the nightly-only API TrustedLen, and
-                        // Array's iterator currently doesn't. Even if we could implement
-                        // TrustedLen we would have to contend with the fact that .chain(..)
-                        // tends to be slow.
-                        // - Rc<[T]>::from_iter docs:
-                        //   https://doc.rust-lang.org/std/rc/struct.Rc.html#impl-FromIterator%3CT%3E
-                        // - chain issue: https://github.com/rust-lang/rust/issues/63340
-                        let mut ts: Vec<RichTerm> = Vec::with_capacity(ts1.len() + ts2.len());
-
                         // We have two sets of contracts from the LHS and RHS arrays.
                         // - Common contracts between the two sides can be put into
                         // `pending_contracts` of the resulting concatenation as they're
@@ -2418,17 +2406,35 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                             })
                             .collect();
 
+                        let ctrs_right_empty = ctrs_right_sieve.iter().all(Option::is_none);
                         let ctrs_right_dedup = ctrs_right_sieve.into_iter().flatten();
 
-                        ts.extend(ts1.into_iter().map(|t| {
-                            RuntimeContract::apply_all(t, ctrs_left_dedup.iter().cloned(), pos1)
-                                .closurize(&mut self.cache, env1.clone())
-                        }));
+                        let ctrs_left_empty = ctrs_left_dedup.is_empty();
+
+                        let arr = if ctrs_right_empty && ctrs_left_empty {
+                            ts1.extend(ts2);
+                            ts1
+                        } else if ctrs_left_empty {
+                            ts1.extend(ts2.into_iter().map(|t| {
+                                RuntimeContract::apply_all(t, ctrs_right_dedup.clone(), pos1)
+                                    .closurize(&mut self.cache, env1.clone())
+                            }));
+                            ts1
+                        } else {
+                            let mut ts = Array::default();
+
+                            ts.extend(ts1.into_iter().map(|t| {
+                                RuntimeContract::apply_all(t, ctrs_left_dedup.iter().cloned(), pos1)
+                                    .closurize(&mut self.cache, env1.clone())
+                            }));
 
-                        ts.extend(ts2.into_iter().map(|t| {
-                            RuntimeContract::apply_all(t, ctrs_right_dedup.clone(), pos2)
-                                .closurize(&mut self.cache, env2.clone())
-                        }));
+                            ts.extend(ts2.into_iter().map(|t| {
+                                RuntimeContract::apply_all(t, ctrs_right_dedup.clone(), pos2)
+                                    .closurize(&mut self.cache, env2.clone())
+                            }));
+
+                            ts
+                        };
 
                         let attrs = ArrayAttrs {
                             closurized: true,
@@ -2436,10 +2442,7 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                         };
 
                         Ok(Closure {
-                            body: RichTerm::new(
-                                Term::Array(Array::new(Rc::from(ts)), attrs),
-                                pos_op_inh,
-                            ),
+                            body: RichTerm::new(Term::Array(arr, attrs), pos_op_inh),
                             env: Environment::new(),
                         })
                     }
@@ -3410,9 +3413,7 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                     ));
                 };
 
-                let result = array.slice(start_as_usize, end_as_usize);
-
-                if let Err(OutOfBoundError) = result {
+                if end_as_usize < start_as_usize || end_as_usize > array.len() {
                     return Err(EvalError::Other(
                         format!(
                             "array/slice: index out of bounds. Expected `start <= end <= {}`, but \
@@ -3421,8 +3422,9 @@ impl<R: ImportResolver, C: Cache> VirtualMachine<R, C> {
                         ),
                         pos_op,
                     ));
-                };
+                }
 
+                array.slice(start_as_usize, end_as_usize);
                 Ok(Closure {
                     body: RichTerm::new(Term::Array(array, attrs), pos_op_inh),
                     env: env3,
diff --git a/core/src/serialize.rs b/core/src/serialize.rs
index aa0b3043..f00dcfcb 100644
--- a/core/src/serialize.rs
+++ b/core/src/serialize.rs
@@ -23,7 +23,7 @@ use malachite::{
 };
 use once_cell::sync::Lazy;
 
-use std::{fmt, io, rc::Rc};
+use std::{fmt, io};
 
 /// Available export formats.
 #[derive(Copy, Clone, Eq, PartialEq, Debug, Default, clap::ValueEnum)]
@@ -198,7 +198,7 @@ pub fn deserialize_array<'de, D>(deserializer: D) -> Result<(Array, ArrayAttrs),
 where
     D: Deserializer<'de>,
 {
-    let terms = Array::new(Rc::from(Vec::deserialize(deserializer)?));
+    let terms = Array::deserialize(deserializer)?;
     Ok((terms, Default::default()))
 }
 
diff --git a/core/src/term/array.rs b/core/src/term/array.rs
index 9facb72f..5d8fdd32 100644
--- a/core/src/term/array.rs
+++ b/core/src/term/array.rs
@@ -1,5 +1,4 @@
-use std::mem::transmute;
-use std::mem::ManuallyDrop;
+use nickel_lang_vector::Slice;
 
 use super::*;
 
@@ -41,208 +40,4 @@ impl ArrayAttrs {
     }
 }
 
-/// A Nickel array, represented as a view (slice) into a shared backing array. The view is
-/// delimited by `start` (included) and `end` (excluded). This allows to take the tail of an array,
-/// or an arbitrary slice, in constant time, providing actual linear time iteration when
-/// imlementing recursive functions, such as folds, for example.
-#[derive(Debug, Clone, PartialEq)]
-pub struct Array {
-    inner: Rc<[RichTerm]>,
-    start: usize,
-    end: usize,
-}
-
-pub struct OutOfBoundError;
-
-impl Array {
-    /// Creates a Nickel array from reference-counted slice.
-    pub fn new(inner: Rc<[RichTerm]>) -> Self {
-        let start = 0;
-        let end = inner.len();
-
-        Self { inner, start, end }
-    }
-
-    /// Resize the view to be a a sub-view of the current one, by considering a slice `start`
-    /// (included) to `end` (excluded).
-    ///
-    /// The parameters must satisfy `0 <= start <= end <= self.end - self.start`. Otherwise,
-    /// `Err(..)` is returned.
-    pub fn slice(&mut self, start: usize, end: usize) -> Result<(), OutOfBoundError> {
-        if start > end || end > self.len() {
-            return Err(OutOfBoundError);
-        }
-
-        let prev_start = self.start;
-        self.start = prev_start + start;
-        self.end = prev_start + end;
-
-        Ok(())
-    }
-
-    /// Returns the effective length of the array.
-    pub fn len(&self) -> usize {
-        self.end - self.start
-    }
-
-    /// Returns `true` if the array is empty.
-    pub fn is_empty(&self) -> bool {
-        self.end == self.start
-    }
-
-    /// Returns a reference to the term at the given index.
-    pub fn get(&self, idx: usize) -> Option<&RichTerm> {
-        self.inner.get(self.start + idx)
-    }
-
-    /// Discards the first `diff` terms of the array.
-    pub fn advance_by(mut self, diff: usize) -> Self {
-        self.start += usize::min(diff, self.len());
-        self
-    }
-
-    /// Makes a mutable slice into the given `Array`.
-    pub fn make_mut(&mut self) -> &mut [RichTerm] {
-        // NOTE: trying to use `Rc::make_mut` will result in the following compiler error:
-        // > the trait `Clone` is not implemented for `[term::RichTerm]`
-        // This seems to be an edge-case in the standard library.
-        // As a workaround, if `get_mut` fails we recollect the array into a new `Rc` by cloning all
-        // terms.
-        // Thus we make sure that the second call to `get_mut` won't fail.
-
-        // This condition is the same as `!Rc::is_unique(&mut self.inner)`, but that function
-        // is not public.
-        if Rc::strong_count(&self.inner) != 1 || Rc::weak_count(&self.inner) != 0 {
-            self.inner = self.iter().cloned().collect::<Rc<[_]>>();
-        }
-
-        Rc::get_mut(&mut self.inner).expect("non-unique Rc after deep-cloning Array")
-    }
-
-    /// Returns an iterator of references over the array.
-    pub fn iter(&self) -> std::slice::Iter<'_, RichTerm> {
-        self.as_ref().iter()
-    }
-}
-
-impl Default for Array {
-    fn default() -> Self {
-        Self::new(Rc::new([]))
-    }
-}
-
-impl FromIterator<RichTerm> for Array {
-    fn from_iter<T: IntoIterator<Item = RichTerm>>(iter: T) -> Self {
-        let inner = iter.into_iter().collect::<Rc<[_]>>();
-        let start = 0;
-        let end = inner.len();
-
-        Self { inner, start, end }
-    }
-}
-
-impl AsRef<[RichTerm]> for Array {
-    fn as_ref(&self) -> &[RichTerm] {
-        &self.inner[self.start..self.end]
-    }
-}
-
-impl IntoIterator for Array {
-    type Item = RichTerm;
-
-    type IntoIter = IntoIter;
-
-    fn into_iter(self) -> Self::IntoIter {
-        // SAFETY: If there are no other strong or weak references
-        // to the inner slice, then we can:
-        // - Drop the elements outside our inner view,
-        // - Move out the elements inside out inner view.
-        // - Drop the rest of the elements when we're dropped
-        // Otherwise, we clone everything.
-
-        let inner = if Rc::strong_count(&self.inner) != 1 || Rc::weak_count(&self.inner) != 0 {
-            IntoIterInner::Shared(self.inner)
-        } else {
-            unsafe {
-                let mut inner =
-                    transmute::<Rc<[RichTerm]>, Rc<[ManuallyDrop<RichTerm>]>>(self.inner);
-                let slice =
-                    Rc::get_mut(&mut inner).expect("non-unique Rc after checking for uniqueness");
-                for term in &mut slice[..self.start] {
-                    ManuallyDrop::drop(term)
-                }
-                for term in &mut slice[self.end..] {
-                    ManuallyDrop::drop(term)
-                }
-
-                IntoIterInner::Owned(inner)
-            }
-        };
-        IntoIter {
-            inner,
-            idx: self.start,
-            end: self.end,
-        }
-    }
-}
-
-enum IntoIterInner {
-    Shared(Rc<[RichTerm]>),
-    // This shouldn't really be an Rc. It should only ever have one reference.
-    // There may be a way to rewrite this once unsized locals are stabilized.
-    // But for now, there is no good way to repackage the inner array, so we
-    // keep it in an Rc.
-    Owned(Rc<[ManuallyDrop<RichTerm>]>),
-}
-pub struct IntoIter {
-    inner: IntoIterInner,
-    idx: usize,
-    end: usize,
-}
-
-impl Iterator for IntoIter {
-    type Item = RichTerm;
-
-    fn next(&mut self) -> Option<Self::Item> {
-        if self.idx == self.end {
-            None
-        } else {
-            let term = match &mut self.inner {
-                IntoIterInner::Shared(inner) => inner.get(self.idx).cloned(),
-                IntoIterInner::Owned(inner) => Rc::get_mut(inner)
-                    .expect("non-unique Rc after checking for uniqueness")
-                    .get_mut(self.idx)
-                    // SAFETY: We already checcked that we have the only
-                    // reference to inner, and after this we increment idx, and
-                    // we never access elements with indexes less than idx
-                    .map(|t| unsafe { ManuallyDrop::take(t) }),
-            };
-            self.idx += 1;
-            term
-        }
-    }
-}
-
-impl Drop for IntoIter {
-    fn drop(&mut self) {
-        // drop the rest of the items we haven't iterated through
-        if let IntoIterInner::Owned(inner) = &mut self.inner {
-            let inner = Rc::get_mut(inner).expect("non-unique Rc after checking for uniqueness");
-            for term in &mut inner[self.idx..self.end] {
-                // SAFETY: Wwe already checked that we have the only reference
-                // to inner, and once we are done dropping the remaining
-                // elements, `inner` will get dropped and there will be no
-                // remaining references.
-                unsafe {
-                    let _ = ManuallyDrop::take(term);
-                }
-            }
-        }
-    }
-}
-
-impl ExactSizeIterator for IntoIter {
-    fn len(&self) -> usize {
-        self.end - self.idx
-    }
-}
+pub type Array = Slice<RichTerm, 32>;
diff --git a/core/src/term/mod.rs b/core/src/term/mod.rs
index 7a7b69e7..974239bb 100644
--- a/core/src/term/mod.rs
+++ b/core/src/term/mod.rs
@@ -2353,11 +2353,10 @@ impl Traverse<RichTerm> for RichTerm {
                 )
             }
             Term::Array(ts, attrs) => {
-                let ts_res = Array::new(
-                    ts.into_iter()
-                        .map(|t| t.traverse(f, order))
-                        .collect::<Result<Rc<[_]>, _>>()?,
-                );
+                let ts_res = ts
+                    .into_iter()
+                    .map(|t| t.traverse(f, order))
+                    .collect::<Result<Array, _>>()?;
 
                 RichTerm::new(Term::Array(ts_res, attrs), pos)
             }
@@ -2731,16 +2730,14 @@ pub mod make {
         ( $( $terms:expr ),* ; $attrs:expr ) => {
             {
                 let ts = $crate::term::array::Array::new(
-                    std::rc::Rc::new([$( $crate::term::RichTerm::from($terms) ),*])
+                    [$( $crate::term::RichTerm::from($terms) ),*]
                 );
                 $crate::term::RichTerm::from($crate::term::Term::Array(ts, $attrs))
             }
         };
         ( $( $terms:expr ),* ) => {
             {
-                let ts = $crate::term::array::Array::new(
-                    std::rc::Rc::new([$( $crate::term::RichTerm::from($terms) ),*])
-                );
+                let ts = [$( $crate::term::RichTerm::from($terms) ),*].into_iter().collect();
                 $crate::term::RichTerm::from(Term::Array(ts, ArrayAttrs::default()))
             }
         };
diff --git a/core/src/transform/free_vars.rs b/core/src/transform/free_vars.rs
index b91395a9..cecf9ca8 100644
--- a/core/src/transform/free_vars.rs
+++ b/core/src/transform/free_vars.rs
@@ -175,7 +175,7 @@ impl CollectFreeVars for RichTerm {
                 *deps = Some(new_deps);
             }
             Term::Array(ts, _) => {
-                for t in ts.make_mut().iter_mut() {
+                for t in ts {
                     t.collect_free_vars(free_vars);
                 }
             }
diff --git a/core/stdlib/std.ncl b/core/stdlib/std.ncl
index aee41af5..dc963457 100644
--- a/core/stdlib/std.ncl
+++ b/core/stdlib/std.ncl
@@ -425,7 +425,7 @@
           # => [ 3, 2, 1 ]
           ```
         "%
-      = fun l => fold_left (fun acc e => [e] @ acc) [] l,
+      = fun l => fold_right (fun e acc => acc @ [e]) [] l,
 
     filter
       : forall a. (a -> Bool) -> Array a -> Array a
@@ -453,7 +453,7 @@
           # => [1, 2, 3, 4]
           ```
         "%
-      = fun l => fold_right (fun l acc => l @ acc) [] l,
+      = fun l => fold_left (fun acc l => acc @ l) [] l,
 
     all
       : forall a. (a -> Bool) -> Array a -> Bool
diff --git a/lsp/nls/src/analysis.rs b/lsp/nls/src/analysis.rs
index aec91434..080d81d1 100644
--- a/lsp/nls/src/analysis.rs
+++ b/lsp/nls/src/analysis.rs
@@ -22,8 +22,8 @@ use crate::{
 
 #[derive(Clone, Debug)]
 pub struct Parent {
-    term: RichTerm,
-    child_name: Option<EltId>,
+    pub term: RichTerm,
+    pub child_name: Option<EltId>,
 }
 
 impl From<RichTerm> for Parent {
@@ -72,6 +72,25 @@ impl ParentLookup {
                             );
                         }
                     }
+
+                    if let Term::RecRecord(_, dynamic, _) = rt.as_ref() {
+                        let parent = Parent {
+                            term: rt.clone(),
+                            child_name: None,
+                        };
+                        for (name_term, field) in dynamic {
+                            name_term.traverse_ref(
+                                &mut |rt, parent| traversal(rt, parent, acc),
+                                &Some(parent.clone()),
+                            );
+                            if let Some(child) = &field.value {
+                                child.traverse_ref(
+                                    &mut |rt, parent| traversal(rt, parent, acc),
+                                    &Some(parent.clone()),
+                                );
+                            }
+                        }
+                    }
                     TraverseControl::SkipBranch
                 }
                 Term::Array(arr, _) => {
@@ -337,6 +356,11 @@ impl AnalysisRegistry {
         Some(self.analysis.get(&file)?.parent_lookup.parent_chain(rt))
     }
 
+    pub fn get_parent<'a>(&'a self, rt: &RichTerm) -> Option<&'a Parent> {
+        let file = rt.pos.as_opt_ref()?.src_id;
+        self.analysis.get(&file)?.parent_lookup.parent(rt)
+    }
+
     pub fn get_static_accesses(&self, id: Ident) -> Vec<RichTerm> {
         self.analysis
             .values()
@@ -410,11 +434,16 @@ impl TypeCollector {
 #[cfg(test)]
 mod tests {
     use assert_matches::assert_matches;
-    use nickel_lang_core::{identifier::Ident, term::Term};
+    use codespan::{ByteIndex, Files};
+    use nickel_lang_core::{
+        identifier::Ident,
+        parser::{grammar, lexer, ErrorTolerantParser as _},
+        term::Term,
+    };
 
     use crate::{
         field_walker::EltId,
-        position::tests::parse,
+        position::{tests::parse, PositionLookup},
         usage::{tests::locced, Environment, UsageLookup},
     };
 
@@ -442,4 +471,25 @@ mod tests {
         assert_matches!(ggp.child_name, Some(EltId::Ident(_)));
         assert_matches!(ggp.term.as_ref(), Term::RecRecord(..));
     }
+
+    #[test]
+    fn parse_error_parent() {
+        // The field that fails to parse should have a record as its parent.
+        let s = "{ field. }";
+        let file = Files::new().add("<test>", s.to_owned());
+
+        let (rt, _errors) = grammar::TermParser::new()
+            .parse_tolerant(file, lexer::Lexer::new(s))
+            .unwrap();
+
+        let parent = ParentLookup::new(&rt);
+        let positions = PositionLookup::new(&rt);
+        let err = positions.get(ByteIndex(5)).unwrap();
+
+        dbg!(&rt, err);
+
+        let p = parent.parent(err).unwrap();
+        assert!(p.child_name.is_none());
+        assert_matches!(p.term.as_ref(), Term::RecRecord(..));
+    }
 }
diff --git a/lsp/nls/src/field_walker.rs b/lsp/nls/src/field_walker.rs
index a8359ad9..0b0eecf6 100644
--- a/lsp/nls/src/field_walker.rs
+++ b/lsp/nls/src/field_walker.rs
@@ -89,6 +89,15 @@ impl TryFrom<Container> for Record {
     }
 }
 
+impl From<Record> for Container {
+    fn from(r: Record) -> Self {
+        match r {
+            Record::RecordTerm(rt) => Container::RecordTerm(rt),
+            Record::RecordType(rt) => Container::RecordType(rt),
+        }
+    }
+}
+
 /// A `Container` is something that has elements.
 ///
 /// The elements could have names (e.g. in a record) or not (e.g. in an array).
@@ -96,7 +105,7 @@ impl TryFrom<Container> for Record {
 /// variants (see [`Record`]), but our internal resolution functions also need
 /// to be transparent to other types of containers.
 #[derive(Clone, Debug, PartialEq)]
-enum Container {
+pub enum Container {
     RecordTerm(RecordData),
     RecordType(RecordRows),
     Dict(Type),
@@ -290,31 +299,45 @@ impl<'a> FieldResolver<'a> {
         rt: &RichTerm,
         path: impl Iterator<Item = impl Into<EltId>>,
     ) -> Vec<Container> {
-        let mut fields = self.resolve_container(rt);
+        let fields = self.resolve_container(rt);
+        self.resolve_containers_at_path(fields.into_iter(), path)
+    }
 
+    /// Finds all the containers that are descended from any of the provided containers at the given path.
+    ///
+    /// The path can mix field access and array "accesses". The array accesses are only used
+    /// in array types -- we never actually index an array value -- but they can be used,
+    /// for example, to see that `{ foo | Array { bar | { baz | Number } } }` evaluated
+    /// at the path `["foo", EltId::ArrayElt, "bar"]` is the record `{ baz | Number }`.
+    pub fn resolve_containers_at_path(
+        &self,
+        containers: impl Iterator<Item = impl Into<Container>>,
+        path: impl Iterator<Item = impl Into<EltId>>,
+    ) -> Vec<Container> {
+        let mut containers: Vec<_> = containers.map(|c| c.into()).collect();
         for id in path.map(Into::into) {
-            let values = fields
+            let values = containers
                 .iter()
                 .filter_map(|container| container.get(id))
                 .collect::<Vec<_>>();
-            fields.clear();
+            containers.clear();
 
             for value in values {
                 match value {
                     FieldContent::RecordField(field) => {
                         if let Some(val) = &field.value {
-                            fields.extend_from_slice(&self.resolve_container(val))
+                            containers.extend_from_slice(&self.resolve_container(val))
                         }
-                        fields.extend(self.resolve_annot(&field.metadata.annotation));
+                        containers.extend(self.resolve_annot(&field.metadata.annotation));
                     }
                     FieldContent::Type(ty) => {
-                        fields.extend_from_slice(&self.resolve_type(&ty));
+                        containers.extend_from_slice(&self.resolve_type(&ty));
                     }
                 }
             }
         }
 
-        fields
+        containers
     }
 
     /// Find the "cousins" of this definition.
diff --git a/lsp/nls/src/requests/completion.rs b/lsp/nls/src/requests/completion.rs
index e1a748a5..00109c0d 100644
--- a/lsp/nls/src/requests/completion.rs
+++ b/lsp/nls/src/requests/completion.rs
@@ -70,8 +70,10 @@ fn extract_static_path(mut rt: RichTerm) -> (RichTerm, Vec<Ident>) {
     }
 }
 
-// Try to interpret `term` as a record path to offer completions for.
-fn sanitize_record_path_for_completion(
+/// If `term` is a `Term::ParseError`, see if we can find something in it to complete.
+/// The situation to keep in mind is something like `{ foo = blah.sub `, in which case
+/// this function should return a term representing the static path "blah.sub".
+fn parse_term_from_incomplete_input(
     term: &RichTerm,
     cursor: RawPos,
     world: &mut World,
@@ -89,7 +91,14 @@ fn sanitize_record_path_for_completion(
 
         range.end = cursor.index;
         incomplete::parse_path_from_incomplete_input(range, &env, world)
-    } else if let Term::Op1(UnaryOp::RecordAccess(_), parent) = term.term.as_ref() {
+    } else {
+        None
+    }
+}
+
+// Try to interpret `term` as a record path to offer completions for.
+fn sanitize_record_path_for_completion(term: &RichTerm) -> Option<RichTerm> {
+    if let Term::Op1(UnaryOp::RecordAccess(_), parent) = term.term.as_ref() {
         // For completing record paths, we discard the last path element: if we're
         // completing `foo.bar.bla`, we only look at `foo.bar` to find the completions.
         Some(parent.clone())
@@ -166,20 +175,40 @@ fn record_path_completion(term: RichTerm, world: &World) -> Vec<CompletionItem>
     defs.iter().flat_map(Record::completion_items).collect()
 }
 
-// Try to complete a field name in a record, like in
-// ```
-// { bar = 1, foo }
-//               ^cursor
-// ```
-// In this situation we don't care about the environment, but we do care about
-// contracts and merged records.
-fn field_completion(rt: &RichTerm, world: &World) -> Vec<CompletionItem> {
+/// Try to complete a field name in a record, like in
+///
+/// ```
+/// { bar = 1, foo }
+///               ^cursor
+/// ```
+///
+/// In this situation we don't care about the environment, but we do care about
+/// contracts and merged records.
+///
+/// If `path` is non-empty, instead of completing fields of `rt` we complete
+/// the fields of `rt.<path>`. You might think we'd want to do this in a situation like
+///
+/// ```
+/// { bar = 1, foo.blah.ba }
+///                       ^cursor
+/// ```
+///
+/// but in fact the nickel parser has already expanded this to
+///
+/// ```
+/// { bar = 1, foo = { blah = { ba } } }
+/// ```
+///
+/// so we don't encounter the path in this case. Instead, the non-empty path only comes
+/// into play when the input fails to parse completely, like in (note the trailing dot)
+///
+/// ```
+/// { bar = 1, foo.blah.ba. }
+///                        ^cursor
+/// ```
+fn field_completion(rt: &RichTerm, world: &World, path: &[Ident]) -> Vec<CompletionItem> {
     let resolver = FieldResolver::new(world);
-    let mut items: Vec<_> = resolver
-        .resolve_record(rt)
-        .iter()
-        .flat_map(Record::completion_items)
-        .collect();
+    let mut records = resolver.resolve_record(rt);
 
     // Look for identifiers that are "in scope" because they're in a cousin that gets merged
     // into us. For example, when completing
@@ -187,10 +216,21 @@ fn field_completion(rt: &RichTerm, world: &World) -> Vec<CompletionItem> {
     // { child = { } } | { child | { foo | Number } }
     //            ^
     // here, we want to offer "foo" as a completion.
-    let cousins = resolver.cousin_records(rt);
-    items.extend(cousins.iter().flat_map(Record::completion_items));
+    records.extend(resolver.cousin_records(rt));
 
-    items
+    if path.is_empty() {
+        // Avoid some work and allocations if there's no path to resolve further.
+        records.iter().flat_map(Record::completion_items).collect()
+    } else {
+        let containers =
+            resolver.resolve_containers_at_path(records.into_iter(), path.iter().copied());
+
+        containers
+            .into_iter()
+            .filter_map(|c| Record::try_from(c).ok())
+            .flat_map(|r| r.completion_items())
+            .collect()
+    }
 }
 
 fn env_completion(rt: &RichTerm, world: &World) -> Vec<CompletionItem> {
@@ -200,6 +240,18 @@ fn env_completion(rt: &RichTerm, world: &World) -> Vec<CompletionItem> {
         .collect()
 }
 
+// Is `rt` a dynamic key of `parent`?
+//
+// If `rt` is a parse error, it will be a dynamic key of `parent` if it's in the
+// syntactic position of a field name.
+fn is_dynamic_key_of(rt: &RichTerm, parent: &RichTerm) -> bool {
+    if let Term::RecRecord(_, dynamic, _) = parent.as_ref() {
+        dynamic.iter().any(|(key, _value)| key == rt)
+    } else {
+        false
+    }
+}
+
 pub fn handle_completion(
     params: CompletionParams,
     id: RequestId,
@@ -239,15 +291,37 @@ pub fn handle_completion(
         return Ok(());
     }
 
-    let path_term = term
-        .as_ref()
-        .and_then(|rt| sanitize_record_path_for_completion(rt, cursor, &mut server.world));
+    let path_term = term.as_ref().and_then(sanitize_record_path_for_completion);
 
     let completions = if let Some(path_term) = path_term {
         record_path_completion(path_term, &server.world)
     } else if let Some(term) = term {
-        if matches!(term.as_ref(), Term::RecRecord(..) | Term::Record(..)) && ident.is_some() {
-            field_completion(&term, &server.world)
+        if let Some(incomplete_term) =
+            parse_term_from_incomplete_input(&term, cursor, &mut server.world)
+        {
+            // A term coming from incomplete input could be either a record path, as in
+            // { foo = bar.‸ }
+            // or a record field, as in
+            // { foo.bar.‸ }
+            // We distinguish the two cases by looking at the the parent of `term` (which,
+            // if we end up here, is a `Term::ParseError`).
+
+            let parent = server.world.analysis.get_parent(&term).map(|p| &p.term);
+
+            if parent.map_or(false, |p| is_dynamic_key_of(&term, p)) {
+                let (incomplete_term, mut path) = extract_static_path(incomplete_term);
+                if let Term::Var(id) = incomplete_term.as_ref() {
+                    path.insert(0, id.ident());
+                    field_completion(&term, &server.world, &path)
+                } else {
+                    record_path_completion(incomplete_term, &server.world)
+                }
+            } else {
+                record_path_completion(incomplete_term, &server.world)
+            }
+        } else if matches!(term.as_ref(), Term::RecRecord(..) | Term::Record(..)) && ident.is_some()
+        {
+            field_completion(&term, &server.world, &[])
         } else {
             env_completion(&term, &server.world)
         }
diff --git a/vector/Cargo.toml b/vector/Cargo.toml
new file mode 100644
index 00000000..a19205c3
--- /dev/null
+++ b/vector/Cargo.toml
@@ -0,0 +1,23 @@
+[package]
+name = "nickel-lang-vector"
+version = "0.1.0"
+description = "Persistent vectors for Nickel"
+edition = "2021"
+
+[dependencies]
+imbl-sized-chunks = "0.1.2"
+serde.workspace = true
+
+[dev-dependencies]
+arbitrary = { version = "1.3.2", features = ["derive"] }
+arbtest = "0.3.1"
+criterion = "0.5.1"
+rpds = "1.1.0"
+
+[[bench]]
+name = "rpds_comparison"
+harness = false
+
+[[bench]]
+name = "slice"
+harness = false
diff --git a/vector/benches/array.rs b/vector/benches/array.rs
new file mode 100644
index 00000000..6157a863
--- /dev/null
+++ b/vector/benches/array.rs
@@ -0,0 +1,34 @@
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
+use nickel_lang_vector::Slice;
+
+pub fn iter_slice(c: &mut Criterion) {
+    let input = [0; 10000];
+    let mut group = c.benchmark_group("collect");
+
+    group.bench_function("slice 100 out of 1k, N=8", |b| {
+        let mut arr: Slice<_, 8> = input[..1000].iter().copied().collect();
+        arr.slice(500, 600);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 10k, N=8", |b| {
+        let mut arr: Slice<_, 8> = input.iter().copied().collect();
+        arr.slice(5000, 5100);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 1k, N=64", |b| {
+        let mut arr: Slice<_, 64> = input[..1000].iter().copied().collect();
+        arr.slice(500, 600);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 10k, N=64", |b| {
+        let mut arr: Slice<_, 64> = input.iter().copied().collect();
+        arr.slice(5000, 5100);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+}
+
+criterion_group!(benches, iter_slice);
+criterion_main!(benches);
diff --git a/vector/benches/rpds_comparison.rs b/vector/benches/rpds_comparison.rs
new file mode 100644
index 00000000..064911ed
--- /dev/null
+++ b/vector/benches/rpds_comparison.rs
@@ -0,0 +1,92 @@
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
+use nickel_lang_vector::Vector;
+
+pub fn collect(c: &mut Criterion) {
+    let input = vec![0; 10000];
+    let mut group = c.benchmark_group("collect");
+
+    group.bench_function("ours 10000, N=8", |b| {
+        b.iter(|| black_box(input.iter().copied().collect::<Vector<i32, 8>>()))
+    });
+
+    group.bench_function("ours 10000, N=32", |b| {
+        b.iter(|| black_box(input.iter().copied().collect::<Vector<i32, 16>>()))
+    });
+
+    group.bench_function("ours 10000, N=64", |b| {
+        b.iter(|| black_box(input.iter().copied().collect::<Vector<i32, 64>>()))
+    });
+
+    group.bench_function("rpds 10000", |b| {
+        b.iter(|| black_box(input.iter().copied().collect::<rpds::Vector<i32>>()))
+    });
+}
+
+pub fn count(c: &mut Criterion) {
+    let input = vec![0; 10000];
+    let vec8: Vector<u32, 8> = input.iter().copied().collect();
+    let vec32: Vector<u32, 32> = input.iter().copied().collect();
+    let vec64: Vector<u32, 64> = input.iter().copied().collect();
+    let rpds: rpds::Vector<u32> = input.iter().copied().collect();
+    let mut group = c.benchmark_group("iter");
+
+    group.bench_function("ours 10000, N=8", |b| {
+        b.iter(|| black_box(vec8.iter().count()));
+    });
+
+    group.bench_function("ours 10000, N=32", |b| {
+        b.iter(|| black_box(vec32.iter().count()));
+    });
+
+    group.bench_function("ours 10000, N=64", |b| {
+        b.iter(|| black_box(vec64.iter().count()));
+    });
+
+    group.bench_function("rpds 10000", |b| {
+        b.iter(|| black_box(rpds.iter().count()));
+    });
+}
+
+pub fn get(c: &mut Criterion) {
+    let input = vec![0; 10000];
+    let vec8: Vector<u32, 8> = input.iter().copied().collect();
+    let vec32: Vector<u32, 32> = input.iter().copied().collect();
+    let vec64: Vector<u32, 64> = input.iter().copied().collect();
+    let rpds: rpds::Vector<u32> = input.iter().copied().collect();
+    let mut group = c.benchmark_group("get");
+
+    group.bench_function("ours 10000, N=8", |b| {
+        b.iter(|| {
+            for i in 0..10000 {
+                black_box(vec8.get(i));
+            }
+        });
+    });
+
+    group.bench_function("ours 10000, N=32", |b| {
+        b.iter(|| {
+            for i in 0..10000 {
+                black_box(vec32.get(i));
+            }
+        });
+    });
+
+    group.bench_function("ours 10000, N=64", |b| {
+        b.iter(|| {
+            for i in 0..10000 {
+                black_box(vec64.get(i));
+            }
+        });
+    });
+
+    group.bench_function("rpds 10000", |b| {
+        b.iter(|| {
+            for i in 0..10000 {
+                black_box(rpds.get(i));
+            }
+        });
+    });
+}
+
+criterion_group!(benches, collect, count, get);
+criterion_main!(benches);
diff --git a/vector/benches/slice.rs b/vector/benches/slice.rs
new file mode 100644
index 00000000..6157a863
--- /dev/null
+++ b/vector/benches/slice.rs
@@ -0,0 +1,34 @@
+use criterion::{black_box, criterion_group, criterion_main, Criterion};
+use nickel_lang_vector::Slice;
+
+pub fn iter_slice(c: &mut Criterion) {
+    let input = [0; 10000];
+    let mut group = c.benchmark_group("collect");
+
+    group.bench_function("slice 100 out of 1k, N=8", |b| {
+        let mut arr: Slice<_, 8> = input[..1000].iter().copied().collect();
+        arr.slice(500, 600);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 10k, N=8", |b| {
+        let mut arr: Slice<_, 8> = input.iter().copied().collect();
+        arr.slice(5000, 5100);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 1k, N=64", |b| {
+        let mut arr: Slice<_, 64> = input[..1000].iter().copied().collect();
+        arr.slice(500, 600);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+
+    group.bench_function("slice 100 out of 10k, N=64", |b| {
+        let mut arr: Slice<_, 64> = input.iter().copied().collect();
+        arr.slice(5000, 5100);
+        b.iter(|| black_box(arr.iter().count()));
+    });
+}
+
+criterion_group!(benches, iter_slice);
+criterion_main!(benches);
diff --git a/vector/src/lib.rs b/vector/src/lib.rs
new file mode 100644
index 00000000..dfb8b5dd
--- /dev/null
+++ b/vector/src/lib.rs
@@ -0,0 +1,29 @@
+//! This crate provides persistent data structures tailored to Nickel's needs.
+//!
+//! [`Vector`] is a persistent vector (also known as a "bitmapped vector trie")
+//! with cheap clones and efficient copy-on-write modifications. [`Slice`]
+//! backs the implementation of arrays in Nickel. It's basically a [`Vector`]
+//! with support for slicing.
+
+// Not yet implemented (do we need them?)
+// - deletion
+// - mutable indexing
+
+pub mod slice;
+pub mod vector;
+
+/// [`Vector`] takes a "branching factor" parameter, which must be a
+/// reasonably-sized power of two. We use this trait to enforce that.
+pub trait ValidBranchingConstant {}
+pub struct Const<const N: usize> {}
+
+impl ValidBranchingConstant for Const<2> {}
+impl ValidBranchingConstant for Const<4> {}
+impl ValidBranchingConstant for Const<8> {}
+impl ValidBranchingConstant for Const<16> {}
+impl ValidBranchingConstant for Const<32> {}
+impl ValidBranchingConstant for Const<64> {}
+impl ValidBranchingConstant for Const<128> {}
+
+pub use slice::Slice;
+pub use vector::Vector;
diff --git a/vector/src/slice.rs b/vector/src/slice.rs
new file mode 100644
index 00000000..510e730d
--- /dev/null
+++ b/vector/src/slice.rs
@@ -0,0 +1,275 @@
+use std::ops::Index;
+
+use crate::{
+    vector::{IntoIter, Iter, IterMut},
+    Const, ValidBranchingConstant,
+};
+
+use super::Vector;
+
+/// A sliced [`Vector`].
+///
+/// This is implemented internally as a tree, and the parameter `N` controls its
+/// branching factor. For performance, it should always be a power of 2. Values
+/// between `8` and `64` are pretty reasonable; see [`Vector`] for more details.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct Slice<T, const N: usize>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    vec: Vector<T, N>,
+    // Our slice involves the range of indices [start, end), like most slicing.
+    // But since we work in reverse, our "first" element is at `end - 1`.
+    start: usize,
+    end: usize,
+}
+
+impl<T, const N: usize> Default for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn default() -> Self {
+        Slice {
+            vec: Default::default(),
+            start: 0,
+            end: 0,
+        }
+    }
+}
+
+impl<T: Clone + serde::Serialize, const N: usize> serde::Serialize for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+    where
+        S: serde::Serializer,
+    {
+        use serde::ser::SerializeSeq;
+
+        let mut seq = serializer.serialize_seq(Some(self.len()))?;
+        for elt in self.iter() {
+            seq.serialize_element(elt)?;
+        }
+        seq.end()
+    }
+}
+
+impl<'de, T: Clone + serde::Deserialize<'de>, const N: usize> serde::Deserialize<'de>
+    for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
+    where
+        D: serde::Deserializer<'de>,
+    {
+        let vec: Vec<T> = Vec::deserialize(deserializer)?;
+        Ok(vec.into_iter().collect())
+    }
+}
+
+impl<T: Clone, const N: usize> Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    /// The number of elements in this array.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// assert_eq!(arr.len(), 6);
+    /// ```
+    pub fn len(&self) -> usize {
+        self.end - self.start
+    }
+
+    /// Returns `true` if the length is zero.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// assert!(!arr.is_empty());
+    /// assert!(Slice::<i32, 32>::default().is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool {
+        self.end == self.start
+    }
+
+    /// Gets an element at a given index, or `None` if `idx` is out-of-bounds.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// assert_eq!(arr.get(2), Some(&2));
+    /// assert_eq!(arr.get(6), None);
+    /// ```
+    pub fn get(&self, idx: usize) -> Option<&T> {
+        self.start.checked_add(idx).and_then(|i| self.vec.get(i))
+    }
+
+    /// Adds an element to the end of this array.
+    ///
+    /// Morally runs in time `O(log self.len())`, but see [`Slice::slice`]
+    /// because there may be some deferred clean-up costs from a previous
+    /// `slice`.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let mut arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// arr.push(6);
+    /// assert_eq!(arr.into_iter().collect::<Vec<_>>(), vec![0, 1, 2, 3, 4, 5, 6]);
+    /// ```
+    pub fn push(&mut self, elt: T) {
+        // If `end` is already at the end of `vec` then this is a cheap no-op.
+        self.vec.truncate(self.end);
+        self.vec.push(elt);
+        self.end += 1;
+    }
+
+    /// Removes and returns the element at the end of this array, or
+    /// `None` if we're empty.
+    ///
+    /// Morally runs in time `O(log self.len())`, but see [`Slice::slice`]
+    /// because there may be some deferred clean-up costs from a previous
+    /// `slice`.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let mut arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// assert_eq!(arr.pop(), Some(5));
+    /// assert_eq!(arr.into_iter().collect::<Vec<_>>(), vec![0, 1, 2, 3, 4]);
+    /// ```
+    pub fn pop(&mut self) -> Option<T> {
+        if self.is_empty() {
+            None
+        } else {
+            self.vec.truncate(self.end);
+            self.end -= 1;
+            self.vec.pop()
+        }
+    }
+
+    /// Returns an iterator over references to array elements.
+    pub fn iter(&self) -> impl Iterator<Item = &'_ T> {
+        self.into_iter()
+    }
+
+    /// Returns an iterator over mutable references to array elements.
+    pub fn iter_mut(&mut self) -> impl Iterator<Item = &'_ mut T> {
+        self.into_iter()
+    }
+
+    /// Replace this array by the subslice from index `from` (inclusive) to
+    /// index `to` (exclusive).
+    ///
+    /// This method is fast, but only because it defers some de-allocation
+    /// costs until later. If you have a slice of length `n` and you `slice` it
+    /// from `0` to `1`, there are `n-1` elements (along with `O(n)` interior
+    /// nodes) that need to be deallocated. This method doesn't de-allocate them
+    /// immediately; it waits until either the whole `Slice` is dropped or the
+    /// end of the `Slice` gets modified with `push` or `pop`.
+    ///
+    /// # Examples
+    ///
+    /// ```rust
+    /// # use nickel_lang_vector::Slice;
+    /// let mut arr = Slice::<_, 32>::from_iter([0, 1, 2, 3, 4, 5]);
+    /// arr.slice(1, 5);
+    /// assert_eq!(arr.clone().into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 4]);
+    /// arr.slice(1, 3);
+    /// assert_eq!(arr.into_iter().collect::<Vec<_>>(), vec![2, 3]);
+    /// ```
+    // We can't use the index trait here, because we'd have to return a &Self.
+    pub fn slice(&mut self, from: usize, to: usize) {
+        assert!(from <= to);
+        assert!(to <= self.len());
+        self.end = self.start + to;
+        self.start += from;
+    }
+}
+
+impl<T: Clone, const N: usize> IntoIterator for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = T;
+    type IntoIter = std::iter::Take<IntoIter<T, N>>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let len = self.len();
+        self.vec.into_iter_starting_at(self.start).take(len)
+    }
+}
+
+impl<'a, T: Clone, const N: usize> IntoIterator for &'a Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = &'a T;
+    type IntoIter = std::iter::Take<Iter<'a, T, N>>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let len = self.len();
+        self.vec.iter_starting_at(self.start).take(len)
+    }
+}
+
+impl<'a, T: Clone, const N: usize> IntoIterator for &'a mut Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = &'a mut T;
+    type IntoIter = std::iter::Take<IterMut<'a, T, N>>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let len = self.len();
+        self.vec.iter_mut_starting_at(self.start).take(len)
+    }
+}
+
+impl<T: Clone, const N: usize> Extend<T> for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
+        self.vec.truncate(self.end);
+        self.vec.extend(iter);
+        self.end = self.vec.len();
+    }
+}
+
+impl<T: Clone, const N: usize> Index<usize> for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Output = T;
+
+    fn index(&self, index: usize) -> &Self::Output {
+        self.get(index).expect("index out of bounds")
+    }
+}
+
+impl<T: Clone, const N: usize> FromIterator<T> for Slice<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
+        let vec: Vector<_, N> = iter.into_iter().collect();
+        Self {
+            start: 0,
+            end: vec.len(),
+            vec,
+        }
+    }
+}
diff --git a/vector/src/vector.rs b/vector/src/vector.rs
new file mode 100644
index 00000000..78b1b2a5
--- /dev/null
+++ b/vector/src/vector.rs
@@ -0,0 +1,1052 @@
+//! [`Vector`] is a persistent vector (also known as a "bitmapped vector trie").
+//!
+//! Most of the operations on `Vector` have similar asymptotic (but
+//! with a slower constant-factor) run-time to the same operations on the
+//! standard-library `Vec`. For example, you can quickly push an element to
+//! the back, or pop one from the back; random-access indexing is also fast.
+//! On the other hand, pushing/popping from the front or insertion/deletion in
+//! the middle are both slow. (Actually, we haven't even implemented these slow
+//! operations because we don't need them.)
+//!
+//! The main advantage that [`Vector`] has over [`std::vec::Vec`] is *persistence*:
+//! you can cheaply clone a `Vector` and then modify the clone. The clone and the
+//! original will share most of their storage.
+//!
+//! There's a good explanation of the data structure
+//! [here](https://hypirion.com/musings/understanding-persistent-vector-pt-1).
+//! Very briefly, a vector is stored as a tree with a fixed branching factor, where
+//! all leaves are the same distance from the root.
+//! Unlike most tree data-structures, it isn't balanced. Instead, it's "packed left"
+//! as much as possible.
+//!
+//! Persistence is achieved by cloning the path leading down
+//! to the node you want to modify: say you want to push a new element, and the're
+//! room for it in the right-most leaf. Then you clone the right-most leaf and
+//! add your new element. Then you clone the leaf's parent and populate it with
+//! pointers to the leaf's (unmodified) siblings, plus the leaf's new clone. Then
+//! you clone the leaf's grandparent and populate it with pointers to the leaf's
+//! (unmodified) uncles, plus the leaf's parent's new clone. You contine up the
+//! tree like this, and you end up with a tree where the path from the leaf to
+//! the root is new but everything else is shared with the previous version of
+//! the vector.
+//!
+//! In this implementation, the pointers in the tree are `Rc` pointers, and we
+//! use `Rc::make_mut` to clone-on-write: when a tree node is only present in
+//! the tree that we're modifying, the clones in the description above
+//! are replaced by direct modification.
+//!
+//! ## Branching factor `N`.
+//!
+//! `Vector` stores its data in a tree, and you get to choose the branching factor
+//! `N`. It must be a power of 2 between 2 and 128 (inclusive), and something like
+//! 32 seems to be reasonable. There is a trade-off involved, of course. Large
+//! values of `N` make traditional array operations -- like random access, pushing,
+//! and popping -- fast because the tree becomes very flat. On the other hand, the
+//! copy-on-write operations suffer when `N` is large because blocks of size `N`
+//! are the smallest units of shareable data.
+//!
+//! For example, if `N` is 128 and you have a vector of less than 128 entries,
+//! it will be stored in a single flat array of capacity 128. If you then clone
+//! the `Vector` and modify the clone, the whole length-128 array will be
+//! cloned. If the vector is stored as a taller tree, only the blocks on the
+//! path from the root to the modified entry will be duplicated. That is, modifying
+//! an entry in a `Vector` of length `n` and branching factor `N` has
+//! cost `O(N * log_N n)`.
+//!
+//! ## Comparison to `rpds`
+//!
+//! The same structure is implemented in [rpds](https://crates.io/crates/rpds),
+//! but our implementation is faster for Nickel's use-cases:
+//! - rpds's internal nodes are implemented with `Vec`, meaning that there's a
+//!   double pointer indirection. We store our internal nodes inline.
+//! - rpds wraps its leaves in `Rc` pointers, but we are mainly interested in
+//!   storing things that are already reference-counted under the hood. We store
+//!   our leaves inline, and require that they be `Clone`.
+//! - we have optimized implementations of `Extend`, and support fast iteration
+//!   over subslices.
+//! - we have better support for "consuming" operations, such as an
+//!   implementation of `into_iter` that avoids cloning the data unless
+//!   necessary for persistence.
+
+use std::{iter::Peekable, ops::Index, rc::Rc};
+
+use imbl_sized_chunks::Chunk;
+
+use crate::{Const, ValidBranchingConstant};
+
+// In principle we could decouple the size of the interior nodes from the size of the leaves.
+// This might make sense when `T` is large, because the interior nodes are always pointer-sized.
+type Interior<T, const N: usize> = Chunk<Rc<Node<T, N>>, N>;
+type ChunkIter<T, const N: usize> = imbl_sized_chunks::sized_chunk::Iter<T, N>;
+type InteriorChunkIter<T, const N: usize> = ChunkIter<Rc<Node<T, N>>, N>;
+
+// Can we improve the memory layout? We like N to be a power of 2 for
+// performance (because it allows adjusting the indices using just bitwise
+// operations), but it would also be cool if the total size of the node were a
+// nice round number (so it would exactly fit in a small integer number of cache
+// lines). The discriminant makes it hard to have both of these at once.
+// Since we always know (based on the tree height) which type we *expect* a node
+// to have, we could use a `union` instead of an `enum` (at the cost of lots of
+// unsafe code).
+//
+// `N` must be a power of 2; this is important for efficiency because it allows
+// the use of bitwise operations for a lot of things. I tried allowing `N` to
+// be arbitrary, hoping that the compiler would be smart enough to do the fast
+// thing when `N` is a power of 2. It wasn't.
+//
+// It would be nice to encode the power-of-2 restriction more efficiently (for
+// example, by parametrizing with `B` and setting `N = 1 << B`). This sort of
+// needs the `generic_const_exprs` feature to work, though.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+enum Node<T, const N: usize> {
+    Leaf { data: Chunk<T, N> },
+    Interior { children: Interior<T, N> },
+}
+
+/// `idx` is the global index into the root node, and we are some
+/// possibly-intermediate node at height `height` (where the leaf is at height
+/// zero). Which of our children does the global index belong to?
+fn extract_index<const N: usize>(idx: usize, height: u8) -> usize {
+    let shifted: usize = idx >> (N.ilog2() * u32::from(height));
+    shifted & (N - 1)
+}
+
+impl<T: Clone, const N: usize> Node<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    /// An inefficient but correct (and simple) method for computing the length
+    /// of this subtree. We cache the length in the top-level vector, so this is
+    /// only used for sanity-checks.
+    fn len(&self) -> usize {
+        match self {
+            Node::Leaf { data } => data.len(),
+            Node::Interior { children } => {
+                // This could be faster if we used the tree height to compute
+                // the size of the packed part of the tree. But this function is
+                // only used for checking invariants, so speed isn't important.
+                children.iter().map(|c| c.len()).sum()
+            }
+        }
+    }
+
+    /// If this node is at height `height`, try to get the element at the given
+    /// index.
+    fn get(&self, height: u8, idx: usize) -> Option<&T> {
+        match self {
+            Node::Leaf { data } => {
+                debug_assert_eq!(height, 0);
+                data.get(idx & (N - 1))
+            }
+            Node::Interior { children } => {
+                let bucket_idx = extract_index::<N>(idx, height);
+                children
+                    .get(bucket_idx)
+                    .and_then(|child| child.get(height - 1, idx))
+            }
+        }
+    }
+
+    /// Set the element at the given index.
+    ///
+    /// The index is allowed to point to the uninitialized slot just past the
+    /// end of the initialized part, but it must point to a valid index within
+    /// this node (i.e. if this node is full then it can't point past the end).
+    ///
+    /// Panics if the index is invalid.
+    fn set(&mut self, height: u8, idx: usize, elt: T) {
+        match self {
+            Node::Leaf { data } => {
+                let idx = idx & (N - 1);
+                debug_assert_eq!(height, 0);
+                debug_assert!(idx <= data.len());
+                if idx < data.len() {
+                    data.set(idx, elt);
+                } else {
+                    data.push_back(elt);
+                }
+            }
+            Node::Interior { children } => {
+                let bucket_idx = extract_index::<N>(idx, height);
+                assert!(height >= 1);
+                assert!(bucket_idx <= children.len());
+                if bucket_idx < children.len() {
+                    Rc::make_mut(&mut children[bucket_idx]).set(height - 1, idx, elt);
+                } else {
+                    let mut leaf = Chunk::new();
+                    leaf.push_back(elt);
+
+                    let mut child = Node::Leaf { data: leaf };
+                    for _ in 1..height {
+                        let mut children = Chunk::new();
+                        children.push_back(Rc::new(child));
+                        child = Node::Interior { children };
+                    }
+                    children.push_back(Rc::new(child));
+                }
+            }
+        }
+    }
+
+    /// Deletes and returns the last element of this subtree (which is assumed to be non-empty).
+    ///
+    /// Returns true if popping made this subtree empty.
+    fn pop(&mut self) -> (T, bool) {
+        match self {
+            Node::Leaf { data } => {
+                debug_assert!(!data.is_empty());
+                let ret = data.pop_back();
+                (ret, data.is_empty())
+            }
+            Node::Interior { children } => {
+                let (ret, child_empty) =
+                    Rc::make_mut(children.last_mut().expect("empty interior node")).pop();
+                if child_empty {
+                    children.pop_back();
+                }
+                (ret, children.is_empty())
+            }
+        }
+    }
+
+    /// Shrinks the length of this subtree to `len`.
+    ///
+    /// Assumes that the length is less than this node's current length.
+    fn truncate(&mut self, height: u8, len: usize) {
+        match self {
+            Node::Leaf { data } => {
+                debug_assert!(height == 0);
+                data.drop_right(len);
+            }
+            Node::Interior { children } => {
+                // If `len` is small enough, we may just want to drop some children
+                // and their entire subtrees.
+                let max_child_len = N.pow(u32::from(height));
+                let num_full_children = len / max_child_len;
+                let extra = len % max_child_len;
+                if extra > 0 {
+                    children.drop_right(num_full_children + 1);
+                    Rc::make_mut(&mut children[num_full_children]).truncate(height - 1, extra);
+                } else {
+                    children.drop_right(num_full_children);
+                }
+            }
+        }
+    }
+}
+
+/// A persistent vector.
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct Vector<T, const N: usize>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    root: Option<Rc<Node<T, N>>>,
+    length: usize,
+    // TODO: could save some space by taking 8 bits out of length
+    height: u8,
+}
+
+/// A borrowed iterator over a [`Vector`].
+#[derive(Debug, Clone)]
+pub struct Iter<'a, T, const N: usize>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    stack: Vec<std::slice::Iter<'a, Rc<Node<T, N>>>>,
+    leaf: std::slice::Iter<'a, T>,
+}
+
+impl<'a, T, const N: usize> Iterator for Iter<'a, T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(ret) = self.leaf.next() {
+            Some(ret)
+        } else {
+            let height = self.stack.len();
+            let mut next = loop {
+                match self.stack.last_mut() {
+                    Some(iter) => {
+                        if let Some(next) = iter.next() {
+                            break next;
+                        } else {
+                            self.stack.pop();
+                        }
+                    }
+                    None => {
+                        return None;
+                    }
+                }
+            };
+
+            let cur_len = self.stack.len();
+            for _ in cur_len..height {
+                let Node::Interior { children } = next.as_ref() else {
+                    unreachable!();
+                };
+                let mut children_iter = children.iter();
+                next = children_iter.next().expect("empty interior node");
+                self.stack.push(children_iter);
+            }
+
+            let Node::Leaf { data } = next.as_ref() else {
+                unreachable!();
+            };
+            debug_assert!(!data.is_empty());
+            self.leaf = data.iter();
+            self.leaf.next()
+        }
+    }
+}
+
+/// A mutable iterator over a [`Vector`].
+#[derive(Debug)]
+pub struct IterMut<'a, T, const N: usize>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    stack: Vec<std::slice::IterMut<'a, Rc<Node<T, N>>>>,
+    leaf: std::slice::IterMut<'a, T>,
+}
+
+impl<'a, T, const N: usize> Iterator for IterMut<'a, T, N>
+where
+    Const<N>: ValidBranchingConstant,
+    T: Clone,
+{
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(ret) = self.leaf.next() {
+            Some(ret)
+        } else {
+            let height = self.stack.len();
+            let mut next = loop {
+                match self.stack.last_mut() {
+                    Some(iter) => {
+                        if let Some(next) = iter.next() {
+                            break next;
+                        } else {
+                            self.stack.pop();
+                        }
+                    }
+                    None => {
+                        return None;
+                    }
+                }
+            };
+
+            let cur_len = self.stack.len();
+            for _ in cur_len..height {
+                let Node::Interior { children } = Rc::make_mut(next) else {
+                    unreachable!();
+                };
+                let mut children_iter = children.iter_mut();
+                next = children_iter.next().expect("empty interior node");
+                self.stack.push(children_iter);
+            }
+
+            let Node::Leaf { data } = Rc::make_mut(next) else {
+                unreachable!();
+            };
+            debug_assert!(!data.is_empty());
+            self.leaf = data.iter_mut();
+            self.leaf.next()
+        }
+    }
+}
+
+/// An owned iterator over a [`Vector`].
+//
+// `IntoIter` and `Iter` share a bunch of almost-identical code, and if we
+// ever want an `IterMut` then it will also be similar. I tried to make a
+// common implementation by defining something like
+//
+// ```rust
+// struct GenericIter<InteriorIter, LeafIter>
+// where InteriorIter: Iterator<Item = Either<InteriorIter, LeafIter>>,
+// {
+//     stack: Vec<InteriorIter>,
+//     leaf: LeafIter,
+// }
+// ```
+//
+// but it came with a massive 500% performance penalty. I didn't look carefully
+// into why.
+pub struct IntoIter<T, const N: usize> {
+    stack: Vec<InteriorChunkIter<T, N>>,
+    leaf: ChunkIter<T, N>,
+}
+
+impl<T: Clone, const N: usize> Iterator for IntoIter<T, N> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if let Some(ret) = self.leaf.next() {
+            Some(ret)
+        } else {
+            let height = self.stack.len();
+            let mut next = loop {
+                match self.stack.last_mut() {
+                    Some(iter) => {
+                        if let Some(next) = iter.next() {
+                            break next;
+                        } else {
+                            self.stack.pop();
+                        }
+                    }
+                    None => {
+                        return None;
+                    }
+                }
+            };
+
+            let cur_len = self.stack.len();
+            for _ in cur_len..height {
+                let Node::Interior { children } = Rc::unwrap_or_clone(next) else {
+                    unreachable!();
+                };
+                let mut children_iter = children.into_iter();
+                next = children_iter.next().expect("empty interior node");
+                self.stack.push(children_iter);
+            }
+
+            let Node::Leaf { data } = Rc::unwrap_or_clone(next) else {
+                unreachable!();
+            };
+            debug_assert!(!data.is_empty());
+            self.leaf = data.into_iter();
+            self.leaf.next()
+        }
+    }
+}
+
+impl<T: Clone, const N: usize> Extend<T> for Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
+        // Make the iterator peekable, because we need to check if there's an
+        // element remaining before we mutate the tree to make room for it.
+        let mut iter = iter.into_iter().peekable();
+
+        // Extends a node from an iterator, but does not increase the height of
+        // the node. If the node fills up, the iterator may not be fully consumed.
+        //
+        // Returns the number of elements consumed from the iterator.
+        fn extend_rec<T: Clone, I: Iterator<Item = T>, const N: usize>(
+            iter: &mut Peekable<I>,
+            node: &mut Interior<T, N>,
+            height: u8,
+        ) -> usize {
+            debug_assert!(height >= 1);
+            let mut consumed = 0;
+
+            if height == 1 {
+                // If there's a leaf that isn't filled, fill it.
+                if let Some(last_child) = node.last_mut() {
+                    // Usually, we assert that there's a last child because the
+                    // interior nodes are guaranteed to be non-empty. But within
+                    // this function we sometimes create empty interior nodes to
+                    // be filled later.
+                    // TODO: can avoid the clone if it's already full
+                    let Node::Leaf { data } = Rc::make_mut(last_child) else {
+                        unreachable!();
+                    };
+                    let old_len = data.len();
+                    data.extend(iter.take(N - data.len()));
+                    consumed += data.len() - old_len;
+                }
+
+                while !node.is_full() && iter.peek().is_some() {
+                    let data: Chunk<T, N> = iter.take(N).collect();
+                    consumed += data.len();
+                    node.push_back(Rc::new(Node::Leaf { data }));
+                }
+            } else {
+                if let Some(child) = node.last_mut() {
+                    let Node::Interior { children } = Rc::make_mut(child) else {
+                        unreachable!();
+                    };
+
+                    consumed += extend_rec(iter, children, height - 1);
+                }
+
+                while !node.is_full() && iter.peek().is_some() {
+                    let mut new_child: Interior<T, N> = Chunk::new();
+                    consumed += extend_rec(iter, &mut new_child, height - 1);
+                    node.push_back(Rc::new(Node::Interior {
+                        children: new_child,
+                    }));
+                }
+            }
+
+            consumed
+        }
+
+        if iter.peek().is_some() && self.root.is_none() {
+            self.root = Some(Rc::new(Node::Leaf {
+                data: Chunk::default(),
+            }));
+        }
+        while iter.peek().is_some() {
+            // Unwrap: we ensured that if the iterator has anything, the root is present.
+            let consumed = match Rc::make_mut(self.root.as_mut().unwrap()) {
+                Node::Leaf { data } => {
+                    let old_len = data.len();
+                    data.extend((&mut iter).take(N - data.len()));
+                    data.len() - old_len
+                }
+                Node::Interior { children } => extend_rec(&mut iter, children, self.height),
+            };
+            self.length += consumed;
+
+            // Check if there's more left in the iterator, and add a level if there is.
+            if iter.peek().is_some() {
+                self.add_level();
+            }
+        }
+    }
+}
+
+fn height_for_length<const N: usize>(length: usize) -> u8 {
+    // Length zero through N has height zero, length N + 1 through N^2 has height 1, etc.
+    // The unwrap is fine unless someone has a usize that's more than 256 bits.
+    length.saturating_sub(1).max(1).ilog(N).try_into().unwrap()
+}
+
+impl<T, const N: usize> Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    /// Create a new, empty, vector.
+    pub fn new() -> Self {
+        Self {
+            root: None,
+            length: 0,
+            height: 0,
+        }
+    }
+
+    /// The number of elements in this vector.
+    pub fn len(&self) -> usize {
+        self.length
+    }
+
+    /// Returns `true` if the length is zero.
+    pub fn is_empty(&self) -> bool {
+        self.length == 0
+    }
+}
+
+impl<T: Clone, const N: usize> Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    // Vectors must always be "packed to the left": every child that isn't the
+    // right-most child of its parent must have a complete subtree.
+    //
+    // This function checks that invariant. It's only used in tests.
+    fn is_packed(&self) -> bool {
+        fn is_packed_rec<T: Clone, const N: usize>(n: &Node<T, N>, right_most: bool) -> bool {
+            match n {
+                Node::Leaf { data } => data.is_full() || right_most,
+                Node::Interior { children } => {
+                    if let Some((tail, others)) = children.split_last() {
+                        others.iter().all(|n| is_packed_rec(n, false)) && is_packed_rec(tail, true)
+                    } else {
+                        debug_assert!(false, "empty node");
+                        false
+                    }
+                }
+            }
+        }
+
+        match &self.root {
+            None => true,
+            Some(root) => is_packed_rec(root, true),
+        }
+    }
+
+    /// Checks our internal invariants.
+    ///
+    /// It's public so that it can be used in out-of-crate tests.
+    #[doc(hidden)]
+    pub fn check_invariants(&self) {
+        assert!(self.is_packed());
+        assert_eq!(self.length, self.root.as_ref().map_or(0, |root| root.len()));
+        if let Some(root) = self.root.as_ref() {
+            if let Node::Interior { children } = root.as_ref() {
+                assert!(children.len() > 1);
+            }
+        }
+        assert_eq!(self.height, height_for_length::<N>(self.len()));
+    }
+
+    // Is this vector as full as it can be without increasing the height?
+    fn is_full(&self) -> bool {
+        self.root.is_none() || self.length == N.pow(u32::from(self.height) + 1)
+    }
+
+    /// Gets an element at a given index, or `None` if `idx` is out-of-bounds.
+    pub fn get(&self, idx: usize) -> Option<&T> {
+        self.root.as_ref().and_then(|r| r.get(self.height, idx))
+    }
+
+    // Increases the height of the tree by one, temporarily breaking the invariant that
+    // the root must have at least two children.
+    fn add_level(&mut self) {
+        match &mut self.root {
+            None => {
+                // We don't increment height in this case: height zero is used for both
+                // the empty vector and a vector with just one leaf.
+                // (Maybe we should use height 1 in the latter case?)
+                self.root = Some(Rc::new(Node::Leaf { data: Chunk::new() }));
+            }
+            Some(root) => {
+                let old_root = std::mem::replace(
+                    root,
+                    Rc::new(Node::Interior {
+                        children: Chunk::new(),
+                    }),
+                );
+
+                // TODO: maybe we can avoid the make_mut and the fallible destructuring?
+                // It seems a little tricky to do so without increasing some ref-counts.
+                let Node::Interior { children } = Rc::make_mut(root) else {
+                    unreachable!();
+                };
+                children.push_back(old_root);
+                self.height += 1;
+            }
+        }
+    }
+
+    /// Adds an element to the end of this array.
+    ///
+    /// Runs in time complexity `O(log n)` where `n` is the array length.
+    pub fn push(&mut self, elt: T) {
+        if self.is_full() {
+            self.add_level();
+        }
+        let idx = self.len();
+        // unwrap: self.add_level ensures that the root is non-empty
+        Rc::make_mut(self.root.as_mut().unwrap()).set(self.height, idx, elt);
+        self.length += 1;
+    }
+
+    /// Removes and returns the element at the end of this array, or
+    /// `None` if we're empty.
+    ///
+    /// Runs in time complexity `O(log self.len())`.
+    pub fn pop(&mut self) -> Option<T> {
+        if self.is_empty() {
+            None
+        } else {
+            // Unwrap: if we aren't empty, we have a root.
+            let root_mut = Rc::make_mut(self.root.as_mut().unwrap());
+            let (ret, _empty) = root_mut.pop();
+            self.length -= 1;
+
+            // If we've shrunk the root down to a single child, reduce the tree height by 1.
+            if let Node::Interior { children } = root_mut {
+                if children.len() == 1 {
+                    self.root = Some(children.pop_back());
+                    self.height -= 1;
+                }
+            }
+            Some(ret)
+        }
+    }
+
+    /// If `len` is less than our length, shortens this vector to length `len`.
+    ///
+    /// If `len` is greater than or equal to our length, does nothing.
+    ///
+    /// The running time is `O(log self.len() + (len - self.len()))`. That
+    /// is, it is linear in the number of elements to be discarded. Even if
+    /// the elements to be discarded have trivial destructors, we still need
+    /// to destroy (and potentially de-allocate) a linear number of internal
+    /// nodes. However, the constant factor in this linear term should be quite
+    /// small; you can expect that `truncate` is much faster than multiple calls
+    /// to `pop`.
+    pub fn truncate(&mut self, len: usize) {
+        if len >= self.length {
+            return;
+        }
+
+        let new_height = height_for_length::<N>(len);
+        if new_height < self.height {
+            // unwrap: if we were empty, we would have returned at the `len >= self.length` check.
+            let mut new_root = self.root.as_ref().unwrap();
+            for _ in new_height..self.height {
+                let Node::Interior { children } = new_root.as_ref() else {
+                    unreachable!();
+                };
+                new_root = children.first().expect("empty interior node");
+            }
+            self.root = Some(Rc::clone(new_root));
+            self.height = new_height;
+        }
+
+        // unwrap: if we were empty, we would have returned at the `len >= self.length` check.
+        Rc::make_mut(self.root.as_mut().unwrap()).truncate(self.height, len);
+
+        self.length = len;
+    }
+
+    /// Returns an iterator over all elements in this vector.
+    ///
+    /// Iterator construction runs in `O(log self.len())` time. Each step
+    /// of the iteration runs in amortized constant time, worst-case `O(log
+    /// self.len())` time.
+    pub fn iter(&self) -> Iter<'_, T, N> {
+        self.into_iter()
+    }
+
+    /// Returns a mutable iterator over all elements in this vector.
+    ///
+    /// Iterator construction runs in `O(log self.len())` time. Each step
+    /// of the iteration runs in amortized constant time, worst-case `O(log
+    /// self.len())` time.
+    pub fn iter_mut(&mut self) -> IterMut<'_, T, N> {
+        self.into_iter()
+    }
+
+    /// Returns an iterator over borrowed elements in this vector, starting at a
+    /// specific index.
+    ///
+    /// Iterator construction runs in `O(log self.len())` time. Each step
+    /// of the iteration runs in amortized constant time, worst-case
+    /// `O(log self.len())` time. In particular, if `idx` is large then this is
+    /// much more efficient than calling `iter` and then advancing past `idx`
+    /// elements.
+    pub fn iter_starting_at(&self, idx: usize) -> Iter<'_, T, N> {
+        if idx == self.len() {
+            return Iter {
+                stack: Vec::new(),
+                leaf: [].iter(),
+            };
+        }
+        if idx > self.len() {
+            panic!("out of bounds");
+        }
+
+        let mut stack = Vec::with_capacity(self.height.into());
+        // unwrap: if we got past the initial tests on `idx`, we must be non-empty
+        // and so we have a root
+        let mut node = self.root.as_ref().unwrap().as_ref();
+        let mut height = self.height;
+
+        while let Node::Interior { children } = node {
+            let bucket_idx = extract_index::<N>(idx, height);
+            let mut node_iter = children[bucket_idx..].iter();
+
+            // expect: we've checked that `idx` is strictly less than the length,
+            // so this interior iterator should be non-empty also.
+            node = node_iter.next().expect("empty interior node");
+            stack.push(node_iter);
+
+            height = height.checked_sub(1).expect("invalid height");
+        }
+
+        let Node::Leaf { data } = node else {
+            unreachable!();
+        };
+        Iter {
+            stack,
+            leaf: data[(idx & (N - 1))..].iter(),
+        }
+    }
+
+    /// Returns an iterator over mutable elements in this vector, starting at a
+    /// specific index.
+    ///
+    /// Iterator construction runs in `O(log self.len())` time. Each step
+    /// of the iteration runs in amortized constant time, worst-case
+    /// `O(log self.len())` time. In particular, if `idx` is large then this is
+    /// much more efficient than calling `iter` and then advancing past `idx`
+    /// elements.
+    pub fn iter_mut_starting_at(&mut self, idx: usize) -> IterMut<'_, T, N> {
+        if idx == self.len() {
+            return IterMut {
+                stack: Vec::new(),
+                leaf: [].iter_mut(),
+            };
+        }
+        if idx > self.len() {
+            panic!("out of bounds");
+        }
+
+        let mut stack = Vec::with_capacity(self.height.into());
+        // unwrap: if we got past the initial tests on `idx`, we must be non-empty
+        // and so we have a root
+        let mut node = self.root.as_mut().unwrap();
+        let mut height = self.height;
+
+        while let Node::Interior { .. } = node.as_ref() {
+            let Node::Interior { children } = Rc::make_mut(node) else {
+                unreachable!("but we just checked it");
+            };
+
+            let bucket_idx = extract_index::<N>(idx, height);
+            let mut node_iter = children[bucket_idx..].iter_mut();
+
+            // expect: we've checked that `idx` is strictly less than the length,
+            // so this interior iterator should be non-empty also.
+            node = node_iter.next().expect("empty interior node");
+            stack.push(node_iter);
+
+            height = height.checked_sub(1).expect("invalid height");
+        }
+
+        let Node::Leaf { data } = Rc::make_mut(node) else {
+            unreachable!();
+        };
+        IterMut {
+            stack,
+            leaf: data[(idx & (N - 1))..].iter_mut(),
+        }
+    }
+
+    /// Returns an iterator over borrowed elements in this vector, starting at a
+    /// specific index.
+    ///
+    /// Iterator construction runs in `O(log self.len() + idx)` time. Each step
+    /// of the iteration runs in amortized constant time, worst-case
+    /// `O(log self.len())` time. Unlike the borrowed `iter_starting_at`, this is
+    /// not asymptotically faster than calling `into_iter` and then advancing
+    /// past `idx` elements, because we need to destruct and then potentially
+    /// de-allocate a linear (in `idx`) number of things. However, this method
+    /// should be faster in practice than iterating over `idx` elements.
+    pub fn into_iter_starting_at(self, mut idx: usize) -> IntoIter<T, N> {
+        if idx == self.len() {
+            return IntoIter {
+                stack: Vec::new(),
+                leaf: Chunk::new().into_iter(),
+            };
+        }
+        if idx > self.len() {
+            panic!("out of bounds");
+        }
+
+        let mut stack = Vec::with_capacity(self.height.into());
+        // unwrap: if we got past the initial tests on `idx`, we must be non-empty
+        // and so we have a root
+        let mut node = Rc::unwrap_or_clone(self.root.unwrap());
+        let mut height = self.height;
+
+        while let Node::Interior { mut children } = node {
+            let bucket_idx = extract_index::<N>(idx, height);
+            children.drop_left(bucket_idx);
+            let mut node_iter = children.into_iter();
+            node = Rc::unwrap_or_clone(node_iter.next().expect("empty interior node"));
+            stack.push(node_iter);
+
+            height = height.checked_sub(1).expect("invalid height");
+        }
+
+        let Node::Leaf { mut data } = node else {
+            unreachable!();
+        };
+        idx &= N - 1;
+        data.drop_left(idx);
+        IntoIter {
+            stack,
+            leaf: data.into_iter(),
+        }
+    }
+}
+
+impl<'a, T, const N: usize> IntoIterator for &'a Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = &'a T;
+    type IntoIter = Iter<'a, T, N>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let mut stack = Vec::with_capacity(self.height.into());
+        let Some(root) = &self.root else {
+            return Iter {
+                stack,
+                leaf: [].iter(),
+            };
+        };
+
+        let mut node = root.as_ref();
+        while let Node::Interior { children } = node {
+            let mut node_iter = children.iter();
+            node = node_iter.next().expect("empty interior node");
+            stack.push(node_iter);
+        }
+
+        let Node::Leaf { data } = node else {
+            unreachable!();
+        };
+        Iter {
+            stack,
+            leaf: data.iter(),
+        }
+    }
+}
+
+impl<'a, T, const N: usize> IntoIterator for &'a mut Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+    T: Clone,
+{
+    type Item = &'a mut T;
+    type IntoIter = IterMut<'a, T, N>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let mut stack = Vec::with_capacity(self.height.into());
+        let Some(root) = &mut self.root else {
+            return IterMut {
+                stack,
+                leaf: [].iter_mut(),
+            };
+        };
+
+        let mut node = root;
+        while let Node::Interior { .. } = node.as_ref() {
+            let Node::Interior { children } = Rc::make_mut(node) else {
+                unreachable!("but we just checked it");
+            };
+            let mut node_iter = children.iter_mut();
+            node = node_iter.next().expect("empty interior node");
+            stack.push(node_iter);
+        }
+
+        let Node::Leaf { data } = Rc::make_mut(node) else {
+            unreachable!();
+        };
+        IterMut {
+            stack,
+            leaf: data.iter_mut(),
+        }
+    }
+}
+
+impl<T: Clone, const N: usize> IntoIterator for Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Item = T;
+    type IntoIter = IntoIter<T, N>;
+
+    fn into_iter(self) -> Self::IntoIter {
+        let mut stack = Vec::with_capacity(self.height.into());
+        let Some(root) = self.root else {
+            return IntoIter {
+                stack,
+                leaf: Chunk::new().into_iter(),
+            };
+        };
+
+        let mut node = Rc::unwrap_or_clone(root);
+        while let Node::Interior { children } = node {
+            let mut node_iter = children.into_iter();
+            node = Rc::unwrap_or_clone(node_iter.next().expect("empty interior node"));
+            stack.push(node_iter);
+        }
+
+        let Node::Leaf { data } = node else {
+            unreachable!();
+        };
+        IntoIter {
+            stack,
+            leaf: data.into_iter(),
+        }
+    }
+}
+
+impl<T, const N: usize> Default for Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl<T: Clone, const N: usize> FromIterator<T> for Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
+        let mut ret = Vector::default();
+        ret.extend(iter);
+        ret
+    }
+}
+
+impl<T: Clone, const N: usize> Index<usize> for Vector<T, N>
+where
+    Const<N>: ValidBranchingConstant,
+{
+    type Output = T;
+
+    fn index(&self, index: usize) -> &Self::Output {
+        self.get(index).expect("index out of range")
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn basic() {
+        let mut vec = Vector::<u32, 2>::new();
+        vec.check_invariants();
+        vec.push(1);
+        assert_eq!(vec.get(0), Some(&1));
+        assert_eq!(vec.get(1), None);
+        vec.check_invariants();
+
+        vec.push(2);
+        vec.check_invariants();
+        vec.push(3);
+        vec.check_invariants();
+        assert_eq!(vec.get(0), Some(&1));
+        assert_eq!(vec.get(1), Some(&2));
+        assert_eq!(vec.get(2), Some(&3));
+        assert_eq!(vec.get(3), None);
+
+        let mut iter = vec.iter();
+        assert_eq!(iter.next(), Some(&1));
+        assert_eq!(iter.next(), Some(&2));
+        assert_eq!(iter.next(), Some(&3));
+        assert_eq!(iter.next(), None);
+
+        assert_eq!(vec.iter().copied().collect::<Vec<_>>(), vec![1, 2, 3]);
+
+        assert_eq!(vec.pop(), Some(3));
+        vec.check_invariants();
+        vec.push(3);
+        vec.check_invariants();
+
+        vec.extend([1, 2, 3]);
+        vec.check_invariants();
+        let mut iter = vec.iter();
+        assert_eq!(iter.next(), Some(&1));
+        assert_eq!(iter.next(), Some(&2));
+        assert_eq!(iter.next(), Some(&3));
+        assert_eq!(iter.next(), Some(&1));
+        assert_eq!(iter.next(), Some(&2));
+        assert_eq!(iter.next(), Some(&3));
+        assert_eq!(iter.next(), None);
+
+        assert_eq!(6, vec.len());
+        assert_eq!(
+            vec.iter().copied().collect::<Vec<_>>(),
+            vec![1, 2, 3, 1, 2, 3]
+        );
+        assert_eq!(vec.into_iter().collect::<Vec<_>>(), vec![1, 2, 3, 1, 2, 3]);
+    }
+}


Test patch:
diff --git a/core/src/parser/tests.rs b/core/src/parser/tests.rs
index ef1e8270..c0ec48fc 100644
--- a/core/src/parser/tests.rs
+++ b/core/src/parser/tests.rs
@@ -1,11 +1,8 @@
-use std::rc::Rc;
-
 use super::lexer::{Lexer, MultiStringToken, NormalToken, StringToken, SymbolicStringStart, Token};
 use super::utils::{build_record, FieldPathElem};
 use crate::error::ParseError;
 use crate::identifier::LocIdent;
 use crate::parser::{error::ParseError as InternalParseError, ErrorTolerantParser};
-use crate::term::array::Array;
 use crate::term::Number;
 use crate::term::Term::*;
 use crate::term::{make as mk_term, Term};
@@ -56,7 +53,7 @@ fn mk_symbolic_single_chunk(prefix: &str, s: &str) -> RichTerm {
             (
                 FieldPathElem::Ident("fragments".into()),
                 Field::from(RichTerm::from(Array(
-                    Array::new(Rc::new([mk_single_chunk(s)])),
+                    std::iter::once(mk_single_chunk(s)).collect(),
                     Default::default(),
                 ))),
             ),
diff --git a/lsp/nls/tests/inputs/completion-incomplete-record-field-nested.ncl b/lsp/nls/tests/inputs/completion-incomplete-record-field-nested.ncl
new file mode 100644
index 00000000..d96c821c
--- /dev/null
+++ b/lsp/nls/tests/inputs/completion-incomplete-record-field-nested.ncl
@@ -0,0 +1,9 @@
+### /main.ncl
+{
+  field.foo.
+} | { field = { foo = { bar } } }
+### [[request]]
+### type = "Completion"
+### textDocument.uri = "file:///main.ncl"
+### position = { line = 1, character = 12 }
+### context = { triggerKind = 2, triggerCharacter = "." }
diff --git a/lsp/nls/tests/inputs/completion-incomplete-record-field.ncl b/lsp/nls/tests/inputs/completion-incomplete-record-field.ncl
new file mode 100644
index 00000000..3213742b
--- /dev/null
+++ b/lsp/nls/tests/inputs/completion-incomplete-record-field.ncl
@@ -0,0 +1,9 @@
+### /main.ncl
+{
+  field.
+} | { field = { foo } }
+### [[request]]
+### type = "Completion"
+### textDocument.uri = "file:///main.ncl"
+### position = { line = 1, character = 8 }
+### context = { triggerKind = 2, triggerCharacter = "." }
diff --git a/lsp/nls/tests/inputs/completion-incomplete-record-value.ncl b/lsp/nls/tests/inputs/completion-incomplete-record-value.ncl
new file mode 100644
index 00000000..344b6642
--- /dev/null
+++ b/lsp/nls/tests/inputs/completion-incomplete-record-value.ncl
@@ -0,0 +1,10 @@
+### /main.ncl
+let baz = { bar = 1 } in
+{
+  field.foo = baz.
+} | { field = { foo } }
+### [[request]]
+### type = "Completion"
+### textDocument.uri = "file:///main.ncl"
+### position = { line = 2, character = 18 }
+### context = { triggerKind = 2, triggerCharacter = "." }
diff --git a/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field-nested.ncl.snap b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field-nested.ncl.snap
new file mode 100644
index 00000000..e022c45a
--- /dev/null
+++ b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field-nested.ncl.snap
@@ -0,0 +1,5 @@
+---
+source: lsp/nls/tests/main.rs
+expression: output
+---
+[bar]
diff --git a/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field.ncl.snap b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field.ncl.snap
new file mode 100644
index 00000000..4623ebf9
--- /dev/null
+++ b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-field.ncl.snap
@@ -0,0 +1,5 @@
+---
+source: lsp/nls/tests/main.rs
+expression: output
+---
+[foo]
diff --git a/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-value.ncl.snap b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-value.ncl.snap
new file mode 100644
index 00000000..e022c45a
--- /dev/null
+++ b/lsp/nls/tests/snapshots/main__lsp__nls__tests__inputs__completion-incomplete-record-value.ncl.snap
@@ -0,0 +1,5 @@
+---
+source: lsp/nls/tests/main.rs
+expression: output
+---
+[bar]
diff --git a/vector/tests/arbtest.rs b/vector/tests/arbtest.rs
new file mode 100644
index 00000000..9f4e6e68
--- /dev/null
+++ b/vector/tests/arbtest.rs
@@ -0,0 +1,228 @@
+use arbitrary::Unstructured;
+use arbtest::{arbitrary, arbtest};
+use nickel_lang_vector::{Const, Slice, ValidBranchingConstant, Vector};
+
+#[derive(arbitrary::Arbitrary, Debug)]
+enum Op {
+    Push(u32),
+    Pop,
+    Extend(Vec<u32>),
+    Clone,
+    Truncate(u32),
+}
+
+impl Op {
+    fn apply_to_vec(&self, vec: &mut Vec<u32>) {
+        match self {
+            Op::Push(x) => vec.push(*x),
+            Op::Pop => {
+                vec.pop();
+            }
+            Op::Extend(xs) => vec.extend_from_slice(xs),
+            Op::Clone => {}
+            Op::Truncate(len) => {
+                if !vec.is_empty() {
+                    vec.truncate(*len as usize % vec.len())
+                }
+            }
+        }
+    }
+
+    fn apply_to_vector<const N: usize>(
+        &self,
+        vec: &mut Vector<u32, N>,
+        arena: &mut Vec<Vector<u32, N>>,
+    ) where
+        Const<N>: ValidBranchingConstant,
+    {
+        match self {
+            Op::Push(x) => vec.push(*x),
+            Op::Pop => {
+                vec.pop();
+            }
+            Op::Extend(xs) => vec.extend(xs.iter().copied()),
+            Op::Clone => {
+                arena.push(vec.clone());
+            }
+            Op::Truncate(len) => {
+                if !vec.is_empty() {
+                    vec.truncate(*len as usize % vec.len())
+                }
+            }
+        }
+    }
+}
+
+#[derive(arbitrary::Arbitrary, Debug)]
+enum ArrayOp {
+    Push(u32),
+    Pop,
+    Extend(Vec<u32>),
+    Slice(u32, usize),
+    // Overwrite(v, len) overwrites the first `len` entries
+    // with the value v.
+    Overwrite(u32, usize),
+}
+
+impl ArrayOp {
+    fn apply_to_vec(&self, vec: &mut Vec<u32>) {
+        match self {
+            ArrayOp::Push(x) => vec.push(*x),
+            ArrayOp::Pop => {
+                vec.pop();
+            }
+            ArrayOp::Extend(xs) => {
+                vec.extend(xs.iter().copied());
+            }
+            ArrayOp::Slice(start, len) => {
+                if !vec.is_empty() {
+                    let start = *start as usize % vec.len();
+                    vec.drain(0..start);
+                    vec.truncate(*len);
+                }
+            }
+            ArrayOp::Overwrite(v, len) => {
+                let len = len % vec.len();
+                for elt in vec.iter_mut().take(len) {
+                    *elt = *v;
+                }
+            }
+        }
+    }
+
+    fn apply_to_slice<const N: usize>(&self, vec: &mut Slice<u32, N>)
+    where
+        Const<N>: ValidBranchingConstant,
+    {
+        match self {
+            ArrayOp::Push(x) => vec.push(*x),
+            ArrayOp::Pop => {
+                vec.pop();
+            }
+            ArrayOp::Extend(xs) => {
+                vec.extend(xs.iter().copied());
+            }
+            ArrayOp::Slice(start, len) => {
+                if !vec.is_empty() {
+                    let start = *start as usize % vec.len();
+                    let start = start.min(vec.len());
+                    let end = (start + len).min(vec.len());
+                    vec.slice(start, end);
+                }
+            }
+            ArrayOp::Overwrite(v, len) => {
+                let len = len % vec.len();
+                for elt in vec.iter_mut().take(len) {
+                    *elt = *v;
+                }
+            }
+        }
+    }
+}
+
+// u.arbitrary() generates very short vecs by default:
+// https://github.com/matklad/arbtest/issues/8
+fn arb_vec(u: &mut Unstructured<'_>) -> arbitrary::Result<Vec<u32>> {
+    let len = u.arbitrary_len::<u32>()?;
+    std::iter::from_fn(|| Some(u.arbitrary::<u32>()))
+        .take(len)
+        .collect()
+}
+
+#[test]
+fn mutations() {
+    arbtest(|u| {
+        let mut vec: Vec<u32> = arb_vec(u)?;
+        let mut vector: Vector<u32, 4> = vec.iter().copied().collect();
+        let mut arena = Vec::new();
+        let ops: Vec<Op> = u.arbitrary()?;
+
+        for op in ops {
+            op.apply_to_vec(&mut vec);
+            op.apply_to_vector(&mut vector, &mut arena);
+
+            vector.check_invariants();
+
+            assert_eq!(vec, vector.iter().cloned().collect::<Vec<_>>());
+        }
+
+        Ok(())
+    });
+}
+
+#[test]
+fn iter_starting_at() {
+    arbtest(|u| {
+        let mut vec: Vec<u32> = arb_vec(u)?;
+        if !vec.is_empty() {
+            let vector: Vector<u32, 4> = vec.iter().copied().collect();
+            let idx: usize = u.arbitrary()?;
+            let idx = idx % vec.len();
+
+            let result: Vec<u32> = vector.iter_starting_at(idx).copied().collect();
+            let into_result: Vec<u32> = vector.into_iter_starting_at(idx).collect();
+            vec.drain(..idx);
+            assert_eq!(result, vec);
+            assert_eq!(into_result, vec);
+        }
+
+        Ok(())
+    });
+}
+
+#[test]
+fn into_iter() {
+    arbtest(|u| {
+        let vec: Vec<u32> = arb_vec(u)?;
+        let vector: Vector<u32, 4> = vec.iter().copied().collect();
+
+        let result: Vec<u32> = vector.into_iter().collect();
+        assert_eq!(result, vec);
+
+        Ok(())
+    });
+}
+
+#[test]
+fn array_mutations() {
+    arbtest(|u| {
+        let vec: Vec<u32> = arb_vec(u)?;
+        let mut vec: Vec<u32> = vec.into_iter().collect();
+        let mut slice: Slice<u32, 4> = vec.iter().copied().collect();
+        let ops: Vec<ArrayOp> = u.arbitrary()?;
+
+        assert_eq!(vec, slice.iter().cloned().collect::<Vec<_>>());
+
+        for op in ops {
+            op.apply_to_vec(&mut vec);
+            op.apply_to_slice(&mut slice);
+
+            assert_eq!(vec, slice.iter().cloned().collect::<Vec<_>>());
+            assert_eq!(vec, slice.clone().into_iter().collect::<Vec<_>>());
+        }
+
+        Ok(())
+    });
+}
+
+#[test]
+fn iter_mut() {
+    arbtest(|u| {
+        let mut vec: Vec<u32> = arb_vec(u)?;
+        let other_vec: Vec<u32> = arb_vec(u)?;
+
+        let mut vector: Vector<_, 32> = vec.iter().copied().collect();
+        let len = u.arbitrary::<usize>()? % vec.len().max(1);
+
+        for (place, val) in vec.iter_mut().take(len).zip(&other_vec) {
+            *place = *val;
+        }
+        for (place, val) in vector.iter_mut().take(len).zip(&other_vec) {
+            *place = *val;
+        }
+
+        assert_eq!(vec, vector.iter().cloned().collect::<Vec<_>>());
+
+        Ok(())
+    });
+}