Unpacking syntax (#532)

Closes #341

9 files changed, 374 insertions, 100 deletions

diff --git a/src/eval/array.rs b/src/eval/array.rs
index 8dcbd5a9..394191ea 100644
--- a/src/eval/array.rs
+++ b/src/eval/array.rs
@@ -322,6 +322,17 @@ impl Array {
         usize::try_from(if index >= 0 { index } else { self.len().checked_add(index)? })
             .ok()
     }
+
+    /// Enumerate all items in the array.
+    pub fn enumerate(&self) -> Self {
+        let v = self
+            .iter()
+            .enumerate()
+            .map(|(i, value)| array![i, value.clone()])
+            .map(Value::Array)
+            .collect();
+        Self::from_vec(v)
+    }
 }
 
 impl Debug for Array {
diff --git a/src/eval/func.rs b/src/eval/func.rs
index e6402e87..93da6d7b 100644
--- a/src/eval/func.rs
+++ b/src/eval/func.rs
@@ -441,7 +441,10 @@ impl<'a> CapturesVisitor<'a> {
                 if let Some(init) = expr.init() {
                     self.visit(init.as_untyped());
                 }
-                self.bind(expr.binding());
+
+                for ident in expr.kind().idents() {
+                    self.bind(ident);
+                }
             }
 
             // A for loop contains one or two bindings in its pattern. These are
@@ -450,11 +453,12 @@ impl<'a> CapturesVisitor<'a> {
             Some(ast::Expr::For(expr)) => {
                 self.visit(expr.iter().as_untyped());
                 self.internal.enter();
+
                 let pattern = expr.pattern();
-                if let Some(key) = pattern.key() {
-                    self.bind(key);
+                for ident in pattern.idents() {
+                    self.bind(ident);
                 }
-                self.bind(pattern.value());
+
                 self.visit(expr.body().as_untyped());
                 self.internal.exit();
             }
@@ -550,7 +554,7 @@ mod tests {
 
         // For loop.
         test("#for x in y { x + z }", &["y", "z"]);
-        test("#for x, y in y { x + y }", &["y"]);
+        test("#for (x, y) in y { x + y }", &["y"]);
         test("#for x in y {} #x", &["x", "y"]);
 
         // Import.
diff --git a/src/eval/methods.rs b/src/eval/methods.rs
index b88bca50..8b364fcb 100644
--- a/src/eval/methods.rs
+++ b/src/eval/methods.rs
@@ -116,6 +116,7 @@ pub fn call(
                 array.join(sep, last).at(span)?
             }
             "sorted" => Value::Array(array.sorted().at(span)?),
+            "enumerate" => Value::Array(array.enumerate()),
             _ => return missing(),
         },
 
@@ -297,6 +298,7 @@ pub fn methods_on(type_name: &str) -> &[(&'static str, bool)] {
             ("rev", false),
             ("slice", true),
             ("sorted", false),
+            ("enumerate", false),
         ],
         "dictionary" => &[
             ("at", true),
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index e278d787..ca69b2d8 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -37,7 +37,7 @@ pub use self::value::*;
 
 pub(crate) use self::methods::methods_on;
 
-use std::collections::BTreeMap;
+use std::collections::{BTreeMap, HashSet};
 use std::mem;
 use std::path::{Path, PathBuf};
 
@@ -1184,6 +1184,97 @@ impl Eval for ast::Closure {
     }
 }
 
+impl ast::Pattern {
+    // Destruct the given value into the pattern.
+    pub fn define(&self, vm: &mut Vm, value: Value) -> SourceResult<Value> {
+        match self.kind() {
+            ast::PatternKind::Ident(ident) => {
+                vm.define(ident, value);
+                Ok(Value::None)
+            }
+            ast::PatternKind::Destructure(pattern) => {
+                match value {
+                    Value::Array(value) => {
+                        let mut i = 0;
+                        for p in &pattern {
+                            match p {
+                                ast::DestructuringKind::Ident(ident) => {
+                                    let Ok(v) = value.at(i) else {
+                                        bail!(ident.span(), "not enough elements to destructure");
+                                    };
+                                    vm.define(ident.clone(), v.clone());
+                                    i += 1;
+                                }
+                                ast::DestructuringKind::Sink(ident) => {
+                                    (1 + value.len() as usize).checked_sub(pattern.len()).and_then(|sink_size| {
+                                        let Ok(sink) = value.slice(i, Some(i + sink_size as i64)) else {
+                                            return None;
+                                        };
+                                        if let Some(ident) = ident {
+                                            vm.define(ident.clone(), sink.clone());
+                                        }
+                                        i += sink_size as i64;
+                                        Some(())
+                                    }).ok_or("not enough elements to destructure").at(self.span())?;
+                                }
+                                ast::DestructuringKind::Named(key, _) => {
+                                    bail!(
+                                        key.span(),
+                                        "cannot destructure named elements from an array"
+                                    )
+                                }
+                            }
+                        }
+                        if i < value.len() as i64 {
+                            bail!(self.span(), "too many elements to destructure");
+                        }
+                    }
+                    Value::Dict(value) => {
+                        let mut sink = None;
+                        let mut used = HashSet::new();
+                        for p in &pattern {
+                            match p {
+                                ast::DestructuringKind::Ident(ident) => {
+                                    let Ok(v) = value.at(ident) else {
+                                        bail!(ident.span(), "destructuring key not found in dictionary");
+                                    };
+                                    vm.define(ident.clone(), v.clone());
+                                    used.insert(ident.clone().take());
+                                }
+                                ast::DestructuringKind::Sink(ident) => {
+                                    sink = ident.clone()
+                                }
+                                ast::DestructuringKind::Named(key, ident) => {
+                                    let Ok(v) = value.at(key) else {
+                                        bail!(ident.span(), "destructuring key not found in dictionary");
+                                    };
+                                    vm.define(ident.clone(), v.clone());
+                                    used.insert(key.clone().take());
+                                }
+                            }
+                        }
+
+                        if let Some(ident) = sink {
+                            let mut sink = Dict::new();
+                            for (key, value) in value {
+                                if !used.contains(key.as_str()) {
+                                    sink.insert(key, value);
+                                }
+                            }
+                            vm.define(ident, Value::Dict(sink));
+                        }
+                    }
+                    _ => {
+                        bail!(self.span(), "cannot destructure {}", value.type_name());
+                    }
+                }
+
+                Ok(Value::None)
+            }
+        }
+    }
+}
+
 impl Eval for ast::LetBinding {
     type Output = Value;
 
@@ -1192,8 +1283,14 @@ impl Eval for ast::LetBinding {
             Some(expr) => expr.eval(vm)?,
             None => Value::None,
         };
-        vm.define(self.binding(), value);
-        Ok(Value::None)
+
+        match self.kind() {
+            ast::LetBindingKind::Normal(pattern) => pattern.define(vm, value),
+            ast::LetBindingKind::Closure(ident) => {
+                vm.define(ident, value);
+                Ok(Value::None)
+            }
+        }
     }
 }
 
@@ -1333,12 +1430,12 @@ impl Eval for ast::ForLoop {
         let mut output = Value::None;
 
         macro_rules! iter {
-            (for ($($binding:ident => $value:ident),*) in $iter:expr) => {{
+            (for $pat:ident in $iter:expr) => {{
                 vm.scopes.enter();
 
                 #[allow(unused_parens)]
-                for ($($value),*) in $iter {
-                    $(vm.define($binding.clone(), $value);)*
+                for value in $iter {
+                    $pat.define(vm, Value::from(value))?;
 
                     let body = self.body();
                     let value = body.eval(vm)?;
@@ -1361,40 +1458,26 @@ impl Eval for ast::ForLoop {
 
         let iter = self.iter().eval(vm)?;
         let pattern = self.pattern();
-        let key = pattern.key();
-        let value = pattern.value();
 
-        match (key, value, iter) {
-            (None, v, Value::Str(string)) => {
-                iter!(for (v => value) in string.as_str().graphemes(true));
+        match (pattern.kind(), iter.clone()) {
+            (ast::PatternKind::Ident(_), Value::Str(string)) => {
+                // iterate over characters of string
+                iter!(for pattern in string.as_str().graphemes(true));
             }
-            (None, v, Value::Array(array)) => {
-                iter!(for (v => value) in array.into_iter());
+            (_, Value::Dict(dict)) => {
+                // iterate over keys of dict
+                iter!(for pattern in dict.pairs());
             }
-            (Some(i), v, Value::Array(array)) => {
-                iter!(for (i => idx, v => value) in array.into_iter().enumerate());
+            (_, Value::Array(array)) => {
+                // iterate over values of array and allow destructuring
+                iter!(for pattern in array.into_iter());
             }
-            (None, v, Value::Dict(dict)) => {
-                iter!(for (v => value) in dict.into_iter().map(|p| p.1));
-            }
-            (Some(k), v, Value::Dict(dict)) => {
-                iter!(for (k => key, v => value) in dict.into_iter());
-            }
-            (None, v, Value::Args(args)) => {
-                iter!(for (v => value) in args.items.into_iter()
-                    .filter(|arg| arg.name.is_none())
-                    .map(|arg| arg.value.v));
-            }
-            (Some(k), v, Value::Args(args)) => {
-                iter!(for (k => key, v => value) in args.items.into_iter()
-                    .map(|arg| (arg.name.map_or(Value::None, Value::Str), arg.value.v)));
-            }
-            (_, _, Value::Str(_)) => {
-                bail!(pattern.span(), "mismatched pattern");
-            }
-            (_, _, iter) => {
+            (ast::PatternKind::Ident(_), _) => {
                 bail!(self.iter().span(), "cannot loop over {}", iter.type_name());
             }
+            (_, _) => {
+                bail!(pattern.span(), "cannot destructure values of {}", iter.type_name())
+            }
         }
 
         if flow.is_some() {
diff --git a/src/ide/complete.rs b/src/ide/complete.rs
index da9e0725..0c80c8df 100644
--- a/src/ide/complete.rs
+++ b/src/ide/complete.rs
@@ -1096,7 +1096,9 @@ impl<'a> CompletionContext<'a> {
             let mut sibling = Some(node.clone());
             while let Some(node) = &sibling {
                 if let Some(v) = node.cast::<ast::LetBinding>() {
-                    defined.insert(v.binding().take());
+                    for ident in v.kind().idents() {
+                        defined.insert(ident.take());
+                    }
                 }
                 sibling = node.prev_sibling();
             }
@@ -1105,10 +1107,9 @@ impl<'a> CompletionContext<'a> {
                 if let Some(v) = parent.cast::<ast::ForLoop>() {
                     if node.prev_sibling_kind() != Some(SyntaxKind::In) {
                         let pattern = v.pattern();
-                        if let Some(key) = pattern.key() {
-                            defined.insert(key.take());
+                        for ident in pattern.idents() {
+                            defined.insert(ident.take());
                         }
-                        defined.insert(pattern.value().take());
                     }
                 }
 
diff --git a/src/ide/highlight.rs b/src/ide/highlight.rs
index e948975b..cf8fdd10 100644
--- a/src/ide/highlight.rs
+++ b/src/ide/highlight.rs
@@ -246,6 +246,7 @@ pub fn highlight(node: &LinkedNode) -> Option<Tag> {
         SyntaxKind::LoopBreak => None,
         SyntaxKind::LoopContinue => None,
         SyntaxKind::FuncReturn => None,
+        SyntaxKind::Pattern => None,
 
         SyntaxKind::LineComment => Some(Tag::Comment),
         SyntaxKind::BlockComment => Some(Tag::Comment),
diff --git a/src/syntax/ast.rs b/src/syntax/ast.rs
index 780c6164..94114958 100644
--- a/src/syntax/ast.rs
+++ b/src/syntax/ast.rs
@@ -1533,7 +1533,10 @@ impl Closure {
     ///
     /// This only exists if you use the function syntax sugar: `let f(x) = y`.
     pub fn name(&self) -> Option<Ident> {
-        self.0.children().next()?.cast()
+        match self.0.cast_first_match::<Pattern>()?.kind() {
+            PatternKind::Ident(ident) => Some(ident),
+            _ => Option::None,
+        }
     }
 
     /// The parameter bindings.
@@ -1590,28 +1593,121 @@ impl AstNode for Param {
 }
 
 node! {
+    /// A destructuring pattern: `x` or `(x, _, ..y)`.
+    Pattern
+}
+
+/// The kind of a pattern.
+#[derive(Debug, Clone, Hash)]
+pub enum PatternKind {
+    /// A single identifier: `x`.
+    Ident(Ident),
+    /// A destructuring pattern: `(x, _, ..y)`.
+    Destructure(Vec<DestructuringKind>),
+}
+
+/// The kind of an element in a destructuring pattern.
+#[derive(Debug, Clone, Hash)]
+pub enum DestructuringKind {
+    /// An identifier: `x`.
+    Ident(Ident),
+    /// An argument sink: `..y`.
+    Sink(Option<Ident>),
+    /// Named arguments: `x: 1`.
+    Named(Ident, Ident),
+}
+
+impl Pattern {
+    /// The kind of the pattern.
+    pub fn kind(&self) -> PatternKind {
+        if self.0.children().len() <= 1 {
+            return PatternKind::Ident(self.0.cast_first_match().unwrap_or_default());
+        }
+
+        let mut bindings = Vec::new();
+        for child in self.0.children() {
+            match child.kind() {
+                SyntaxKind::Ident => {
+                    bindings
+                        .push(DestructuringKind::Ident(child.cast().unwrap_or_default()));
+                }
+                SyntaxKind::Spread => {
+                    bindings.push(DestructuringKind::Sink(child.cast_first_match()));
+                }
+                SyntaxKind::Named => {
+                    let mut filtered = child.children().filter_map(SyntaxNode::cast);
+                    let key = filtered.next().unwrap_or_default();
+                    let ident = filtered.next().unwrap_or_default();
+                    bindings.push(DestructuringKind::Named(key, ident));
+                }
+                _ => (),
+            }
+        }
+
+        PatternKind::Destructure(bindings)
+    }
+
+    // Returns a list of all identifiers in the pattern.
+    pub fn idents(&self) -> Vec<Ident> {
+        match self.kind() {
+            PatternKind::Ident(ident) => vec![ident],
+            PatternKind::Destructure(bindings) => bindings
+                .into_iter()
+                .filter_map(|binding| match binding {
+                    DestructuringKind::Ident(ident) => Some(ident),
+                    DestructuringKind::Sink(ident) => ident,
+                    DestructuringKind::Named(_, ident) => Some(ident),
+                })
+                .collect(),
+        }
+    }
+}
+
+node! {
     /// A let binding: `let x = 1`.
     LetBinding
 }
 
+pub enum LetBindingKind {
+    /// A normal binding: `let x = 1`.
+    Normal(Pattern),
+    /// A closure binding: `let f(x) = 1`.
+    Closure(Ident),
+}
+
+impl LetBindingKind {
+    // Returns a list of all identifiers in the pattern.
+    pub fn idents(&self) -> Vec<Ident> {
+        match self {
+            LetBindingKind::Normal(pattern) => pattern.idents(),
+            LetBindingKind::Closure(ident) => {
+                vec![ident.clone()]
+            }
+        }
+    }
+}
+
 impl LetBinding {
-    /// The binding to assign to.
-    pub fn binding(&self) -> Ident {
-        match self.0.cast_first_match() {
-            Some(Expr::Ident(binding)) => binding,
-            Some(Expr::Closure(closure)) => closure.name().unwrap_or_default(),
-            _ => Ident::default(),
+    /// The kind of the let binding.
+    pub fn kind(&self) -> LetBindingKind {
+        if let Some(pattern) = self.0.cast_first_match::<Pattern>() {
+            LetBindingKind::Normal(pattern)
+        } else {
+            LetBindingKind::Closure(
+                self.0
+                    .cast_first_match::<Closure>()
+                    .unwrap_or_default()
+                    .name()
+                    .unwrap_or_default(),
+            )
         }
     }
 
     /// The expression the binding is initialized with.
     pub fn init(&self) -> Option<Expr> {
-        if self.0.cast_first_match::<Ident>().is_some() {
-            // This is a normal binding like `let x = 1`.
-            self.0.children().filter_map(SyntaxNode::cast).nth(1)
-        } else {
-            // This is a closure binding like `let f(x) = 1`.
-            self.0.cast_first_match()
+        match self.kind() {
+            LetBindingKind::Normal(_) => self.0.cast_last_match(),
+            LetBindingKind::Closure(_) => self.0.cast_first_match(),
         }
     }
 }
@@ -1712,7 +1808,7 @@ node! {
 
 impl ForLoop {
     /// The pattern to assign to.
-    pub fn pattern(&self) -> ForPattern {
+    pub fn pattern(&self) -> Pattern {
         self.0.cast_first_match().unwrap_or_default()
     }
 
@@ -1728,29 +1824,6 @@ impl ForLoop {
 }
 
 node! {
-    /// A for loop's destructuring pattern: `x` or `x, y`.
-    ForPattern
-}
-
-impl ForPattern {
-    /// The key part of the pattern: index for arrays, name for dictionaries.
-    pub fn key(&self) -> Option<Ident> {
-        let mut children = self.0.children().filter_map(SyntaxNode::cast);
-        let key = children.next();
-        if children.next().is_some() {
-            key
-        } else {
-            Option::None
-        }
-    }
-
-    /// The value part of the pattern.
-    pub fn value(&self) -> Ident {
-        self.0.cast_last_match().unwrap_or_default()
-    }
-}
-
-node! {
     /// A module import: `import "utils.typ": a, b, c`.
     ModuleImport
 }
diff --git a/src/syntax/kind.rs b/src/syntax/kind.rs
index b0d934d1..fcde2bb4 100644
--- a/src/syntax/kind.rs
+++ b/src/syntax/kind.rs
@@ -244,6 +244,8 @@ pub enum SyntaxKind {
     LoopContinue,
     /// A return from a function: `return`, `return x + 1`.
     FuncReturn,
+    /// A destructuring pattern: `x`, `(x, _, ..y)`.
+    Pattern,
 
     /// A line comment: `// ...`.
     LineComment,
@@ -430,6 +432,7 @@ impl SyntaxKind {
             Self::LoopBreak => "`break` expression",
             Self::LoopContinue => "`continue` expression",
             Self::FuncReturn => "`return` expression",
+            Self::Pattern => "destructuring pattern",
             Self::LineComment => "line comment",
             Self::BlockComment => "block comment",
             Self::Error => "syntax error",
diff --git a/src/syntax/parser.rs b/src/syntax/parser.rs
index e95da4af..83d9ae46 100644
--- a/src/syntax/parser.rs
+++ b/src/syntax/parser.rs
@@ -777,6 +777,11 @@ fn item(p: &mut Parser, keyed: bool) -> SyntaxKind {
     let m = p.marker();
 
     if p.eat_if(SyntaxKind::Dots) {
+        if p.at(SyntaxKind::Comma) || p.at(SyntaxKind::RightParen) {
+            p.wrap(m, SyntaxKind::Spread);
+            return SyntaxKind::Spread;
+        }
+
         code_expr(p);
         p.wrap(m, SyntaxKind::Spread);
         return SyntaxKind::Spread;
@@ -833,22 +838,56 @@ fn args(p: &mut Parser) {
     p.wrap(m, SyntaxKind::Args);
 }
 
+enum PatternKind {
+    Normal,
+    Destructuring,
+}
+
+fn pattern(p: &mut Parser) -> PatternKind {
+    let m = p.marker();
+
+    if p.at(SyntaxKind::LeftParen) {
+        collection(p, false);
+        validate_destruct_pattern(p, m);
+        p.wrap(m, SyntaxKind::Pattern);
+
+        PatternKind::Destructuring
+    } else {
+        let success = p.expect(SyntaxKind::Ident);
+        if p.at(SyntaxKind::Comma) {
+            // TODO: this should only be a warning instead
+            p.expected("keyword `in`. did you mean to use a destructuring pattern?");
+        }
+
+        if success {
+            p.wrap(m, SyntaxKind::Pattern);
+        }
+
+        PatternKind::Normal
+    }
+}
+
 fn let_binding(p: &mut Parser) {
     let m = p.marker();
     p.assert(SyntaxKind::Let);
 
     let m2 = p.marker();
-    p.expect(SyntaxKind::Ident);
-
-    let closure = p.directly_at(SyntaxKind::LeftParen);
-    if closure {
-        let m3 = p.marker();
-        collection(p, false);
-        validate_params(p, m3);
-        p.wrap(m3, SyntaxKind::Params);
+    let mut closure = false;
+    let mut destructuring = false;
+    match pattern(p) {
+        PatternKind::Normal => {
+            closure = p.directly_at(SyntaxKind::LeftParen);
+            if closure {
+                let m3 = p.marker();
+                collection(p, false);
+                validate_params(p, m3);
+                p.wrap(m3, SyntaxKind::Params);
+            }
+        }
+        PatternKind::Destructuring => destructuring = true,
     }
 
-    let f = if closure { Parser::expect } else { Parser::eat_if };
+    let f = if closure || destructuring { Parser::expect } else { Parser::eat_if };
     if f(p, SyntaxKind::Eq) {
         code_expr(p);
     }
@@ -924,23 +963,13 @@ fn while_loop(p: &mut Parser) {
 fn for_loop(p: &mut Parser) {
     let m = p.marker();
     p.assert(SyntaxKind::For);
-    for_pattern(p);
+    pattern(p);
     p.expect(SyntaxKind::In);
     code_expr(p);
     block(p);
     p.wrap(m, SyntaxKind::ForLoop);
 }
 
-fn for_pattern(p: &mut Parser) {
-    let m = p.marker();
-    if p.expect(SyntaxKind::Ident) {
-        if p.eat_if(SyntaxKind::Comma) {
-            p.expect(SyntaxKind::Ident);
-        }
-        p.wrap(m, SyntaxKind::ForPattern);
-    }
-}
-
 fn module_import(p: &mut Parser) {
     let m = p.marker();
     p.assert(SyntaxKind::Import);
@@ -1086,6 +1115,73 @@ fn validate_args(p: &mut Parser, m: Marker) {
     }
 }
 
+fn validate_destruct_pattern(p: &mut Parser, m: Marker) {
+    let mut used_spread = false;
+    let mut used = HashSet::new();
+    for child in p.post_process(m) {
+        match child.kind() {
+            SyntaxKind::Ident => {
+                if child.text() != "_" && !used.insert(child.text().clone()) {
+                    child.convert_to_error(
+                        "at most one binding per identifier is allowed",
+                    );
+                }
+            }
+            SyntaxKind::Spread => {
+                let Some(within) = child.children_mut().last_mut() else { continue };
+                if used_spread {
+                    child.convert_to_error("at most one destructuring sink is allowed");
+                    continue;
+                }
+                used_spread = true;
+
+                if within.kind() == SyntaxKind::Dots {
+                    continue;
+                } else if within.kind() != SyntaxKind::Ident {
+                    within.convert_to_error(eco_format!(
+                        "expected identifier, found {}",
+                        within.kind().name(),
+                    ));
+                    child.make_erroneous();
+                    continue;
+                }
+
+                if within.text() != "_" && !used.insert(within.text().clone()) {
+                    within.convert_to_error(
+                        "at most one binding per identifier is allowed",
+                    );
+                    child.make_erroneous();
+                }
+            }
+            SyntaxKind::Named => {
+                let Some(within) = child.children_mut().first_mut() else { return };
+                if !used.insert(within.text().clone()) {
+                    within.convert_to_error(
+                        "at most one binding per identifier is allowed",
+                    );
+                    child.make_erroneous();
+                }
+
+                let Some(within) = child.children_mut().last_mut() else { return };
+                if within.kind() != SyntaxKind::Ident {
+                    within.convert_to_error(eco_format!(
+                        "expected identifier, found {}",
+                        within.kind().name(),
+                    ));
+                    child.make_erroneous();
+                }
+            }
+            SyntaxKind::LeftParen | SyntaxKind::RightParen | SyntaxKind::Comma => {}
+            kind => {
+                child.convert_to_error(eco_format!(
+                    "expected identifier or destructuring sink, found {}",
+                    kind.name()
+                ));
+            }
+        }
+    }
+}
+
 /// Manages parsing of a stream of tokens.
 struct Parser<'s> {
     text: &'s str,