Sitelet https://github.com/starkware-libs/cairo/commit/9df5995b259a7c876199ce1c7d20552783ecfb9f
Skip to content

Commit 9df5995

Browse files
ilyalesokhin-starkwareclaude
ilyalesokhin-starkware
and
claude
committed
feature(cairo): Support Span<T> destructuring via fixed-size array patterns
Add support for `let [a, b] = span else { ... }` syntax by introducing a SliceDestructure flow control node that calls tuple_from_span to convert Span<T> to [T; N] at runtime. Co-Authored-By: Claude Opus 4.6 (1M context) <noreply@anthropic.com>
1 parent e2c8f33 commit 9df5995

7 files changed

Lines changed: 963 additions & 22 deletions

File tree

‎corelib/src/test/language_features/match_test.cairo‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,29 @@ fn test_match_multienum_binding() {
1212
panic!("Match expression did not return - this should be unreachable");
1313
}
1414

15+
#[test]
16+
fn test_match_span_to_fixed_size_array() {
17+
let span: Span<u32> = array![10, 20, 30].span();
18+
19+
match span {
20+
[_a, _b, _c, _d] => { panic!("Expected 3 elements, but got 4"); },
21+
[_a, _b] => { panic!("Expected 3 elements, but got 2"); },
22+
[a, b, c] => { assert_eq!((*a, *b, *c), (10, 20, 30)); },
23+
_ => panic!("Expected 3 elements, but got a different pattern"),
24+
}
25+
}
26+
27+
#[test]
28+
fn test_match_span_empty_pattern() {
29+
let span: Span<u32> = array![].span();
30+
31+
match span {
32+
[_a] => { panic!("Expected 0 elements, but got 1"); },
33+
[] => {},
34+
_ => panic!("Expected 0 elements, but got a different count"),
35+
}
36+
}
37+
1538
#[test]
1639
fn test_match_extern_multilevel() {
1740
if true {
@@ -24,3 +47,17 @@ fn test_match_extern_multilevel() {
2447
}
2548
panic!("Match expression did not return - this should be unreachable");
2649
}
50+
51+
52+
#[test]
53+
fn test_match_span_inner_pattern_mismatch() {
54+
let matcher = |s: Array<Option<felt252>>| match s.span() {
55+
[Some(_)] => 1,
56+
[None] => 2,
57+
_ => 0,
58+
};
59+
60+
assert_eq!(matcher(array![Some(42)]), 1);
61+
assert_eq!(matcher(array![None]), 2);
62+
assert_eq!(matcher(array![Some(1), Some(2)]), 0);
63+
}

‎crates/cairo-lang-lowering/src/lower/flow_control/create_graph/patterns.rs‎

Lines changed: 184 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -2,14 +2,16 @@ use cairo_lang_debug::DebugWithDb;
22
use cairo_lang_defs::ids::NamedLanguageElementId;
33
use cairo_lang_diagnostics::{DiagnosticNote, Maybe};
44
use cairo_lang_filesystem::flag::FlagsGroup;
5-
use cairo_lang_semantic::corelib::{CorelibSemantic, validate_literal};
5+
use cairo_lang_filesystem::ids::SmolStrId;
6+
use cairo_lang_semantic::corelib::{CorelibSemantic, try_get_core_ty_by_name, validate_literal};
67
use cairo_lang_semantic::expr::compute::unwrap_pattern_type;
78
use cairo_lang_semantic::items::enm::SemanticEnumEx;
89
use cairo_lang_semantic::items::structure::StructSemantic;
10+
use cairo_lang_semantic::types::wrap_in_snapshots;
911
use cairo_lang_semantic::{
1012
self as semantic, ConcreteEnumId, ConcreteStructId, ConcreteTypeId, ExprNumericLiteral,
11-
PatternEnumVariant, PatternLiteral, PatternStruct, PatternTuple, PatternWrappingInfo, TypeId,
12-
TypeLongId, corelib,
13+
GenericArgumentId, PatternEnumVariant, PatternLiteral, PatternStruct, PatternTuple,
14+
PatternWrappingInfo, TypeId, TypeLongId, corelib,
1315
};
1416
use cairo_lang_syntax::node::TypedStablePtr;
1517
use cairo_lang_syntax::node::ast::ExprPtr;
@@ -26,7 +28,9 @@ use super::filtered_patterns::{Bindings, FilteredPatterns};
2628
use crate::diagnostic::{LoweringDiagnosticKind, MatchDiagnostic, MatchError};
2729
use crate::ids::LocationId;
2830
use crate::lower::context::LoweringContext;
29-
use crate::lower::flow_control::graph::{Downcast, EqualsLiteral, Upcast, ValueMatch};
31+
use crate::lower::flow_control::graph::{
32+
Downcast, EqualsLiteral, SliceDestructure, Upcast, ValueMatch,
33+
};
3034

3135
/// A callback that gets a [FilteredPatterns] and constructs a node that continues the pattern
3236
/// matching restricted to the filtered patterns.
@@ -150,21 +154,6 @@ pub fn create_node_for_patterns<'db>(
150154
create_node_for_enum(params, input_var, concrete_enum_id, wrapping_info)
151155
}
152156
TypeLongId::Concrete(ConcreteTypeId::Struct(concrete_struct_id)) => {
153-
// Check if any non-any pattern is a FixedSizeArray (i.e. Span destructure).
154-
// Span destructuring in match/if-let is not yet supported in lowering.
155-
let has_fixed_size_array_pattern = patterns
156-
.iter()
157-
.flatten()
158-
.any(|p| matches!(p, semantic::Pattern::FixedSizeArray(..)));
159-
if has_fixed_size_array_pattern {
160-
return graph.report_with_missing_node(
161-
first_non_any_pattern.stable_ptr(),
162-
LoweringDiagnosticKind::MatchError(MatchError {
163-
kind: graph.kind(),
164-
error: MatchDiagnostic::UnsupportedMatchedType(long_ty.format(ctx.db)),
165-
}),
166-
);
167-
}
168157
create_node_for_struct(params, input_var, concrete_struct_id, wrapping_info)
169158
}
170159
TypeLongId::Tuple(types) => create_node_for_tuple(params, input_var, &types, wrapping_info),
@@ -354,6 +343,19 @@ fn create_node_for_struct<'db>(
354343
) -> NodeId {
355344
let CreateNodeParams { ctx, graph, patterns, build_node_callback, location } = params;
356345

346+
if let Some(node) = try_create_slice_destructure_chain(
347+
ctx,
348+
graph,
349+
patterns,
350+
build_node_callback,
351+
location,
352+
input_var,
353+
concrete_struct_id,
354+
wrapping_info,
355+
) {
356+
return node;
357+
}
358+
357359
let members = match ctx.db.concrete_struct_members(concrete_struct_id) {
358360
Ok(members) => members,
359361
Err(diag_added) => return graph.add_node(FlowControlNode::Missing(diag_added)),
@@ -390,6 +392,162 @@ fn create_node_for_struct<'db>(
390392
}))
391393
}
392394

395+
/// Tries to create a chain of [`SliceDestructure`] nodes for matching a `Span<T>` against
396+
/// fixed-size array patterns with different sizes.
397+
///
398+
/// Returns `None` if no `FixedSizeArray` patterns are present or the struct is not a `Span`.
399+
/// Each size is tried in order. On failure, the next size is attempted. If all sizes fail,
400+
/// the wildcard/otherwise patterns are used.
401+
#[allow(clippy::too_many_arguments)]
402+
fn try_create_slice_destructure_chain<'db>(
403+
ctx: &LoweringContext<'db, '_>,
404+
graph: &mut FlowControlGraphBuilder<'db>,
405+
patterns: &[PatternOption<'_, 'db>],
406+
build_node_callback: BuildNodeCallback<'db, '_>,
407+
location: LocationId<'db>,
408+
input_var: FlowControlVar,
409+
concrete_struct_id: ConcreteStructId<'db>,
410+
wrapping_info: PatternWrappingInfo,
411+
) -> Option<NodeId> {
412+
if !patterns.iter().any(|p| matches!(p, Some(semantic::Pattern::FixedSizeArray(..)))) {
413+
return None;
414+
}
415+
let [GenericArgumentId::Type(elem_ty)] = concrete_struct_id.long(ctx.db).generic_args[..]
416+
else {
417+
return None;
418+
};
419+
if try_get_core_ty_by_name(
420+
ctx.db,
421+
SmolStrId::from(ctx.db, "Span"),
422+
vec![GenericArgumentId::Type(elem_ty)],
423+
)
424+
.is_err()
425+
{
426+
// Not a Span - report error on the first FixedSizeArray pattern.
427+
let first_fsa = patterns.iter().find_map(|p| match p {
428+
Some(semantic::Pattern::FixedSizeArray(p)) => Some(p),
429+
_ => None,
430+
});
431+
return Some(graph.report_with_missing_node(
432+
first_fsa.unwrap().stable_ptr.untyped(),
433+
LoweringDiagnosticKind::UnexpectedError,
434+
));
435+
}
436+
// Deconstruct Span<T> to get its single member @Array<T>.
437+
let members = ctx.db.concrete_struct_members(concrete_struct_id).ok()?;
438+
let snapshot_array_ty = members.iter().next().unwrap().1.ty;
439+
let snapshot_array_var = graph.new_var(snapshot_array_ty, location);
440+
441+
// Group patterns by array size. Wildcards/otherwise are added to all groups.
442+
// Use an OrderedHashMap to preserve insertion order (first-seen size first).
443+
let mut size_groups: OrderedHashMap<usize, SizeGroupInfo<'_, '_>> = OrderedHashMap::default();
444+
let mut wildcard_filter = FilteredPatterns::default();
445+
446+
for (idx, pattern) in patterns.iter().enumerate() {
447+
match pattern {
448+
Some(semantic::Pattern::FixedSizeArray(p)) => {
449+
let n = p.elements_patterns.len();
450+
let group = size_groups.entry(n).or_default();
451+
452+
group.filter.add(idx);
453+
group.patterns.push(*pattern);
454+
}
455+
Some(semantic::Pattern::Otherwise(..)) | None => {
456+
wildcard_filter.add(idx);
457+
for group in size_groups.values_mut() {
458+
group.filter.add(idx);
459+
group.patterns.push(None);
460+
}
461+
break;
462+
}
463+
Some(pattern) => {
464+
// This should not be reachable without getting a semantic error.
465+
return Some(graph.report_with_missing_node(
466+
pattern.stable_ptr().untyped(),
467+
LoweringDiagnosticKind::UnexpectedError,
468+
));
469+
}
470+
}
471+
}
472+
473+
// Build the chain from back to front, since we need the fallback node before we can create a
474+
// node. The final fallback is the wildcard-only callback.
475+
// Note: `"_"` is used as the pattern for the non-exhaustive diagnostic, as there is no `[..]`
476+
// pattern.
477+
let mut failure_node = build_node_callback(graph, wildcard_filter, "_".into());
478+
479+
for (size, group) in size_groups.into_iter().rev() {
480+
let types = vec![wrap_in_snapshots(ctx.db, elem_ty, 1); size];
481+
let inner_vars = types
482+
.iter()
483+
.map(|ty| graph.new_var(wrapping_info.wrap(ctx.db, *ty), location))
484+
.collect_vec();
485+
486+
// Build the success path: process element patterns within this size group.
487+
let group_filter = group.filter;
488+
let group_patterns: Vec<PatternOption<'_, 'db>> = group.patterns;
489+
let success = create_node_for_tuple_inner(
490+
CreateNodeParams {
491+
ctx,
492+
graph,
493+
patterns: &group_patterns,
494+
build_node_callback: &mut |graph, pattern_indices, path| {
495+
build_node_callback(
496+
graph,
497+
pattern_indices.lift(&group_filter),
498+
format!("[{path}]"),
499+
)
500+
},
501+
location,
502+
},
503+
&inner_vars,
504+
&types,
505+
0,
506+
None,
507+
);
508+
509+
failure_node = graph.add_node(FlowControlNode::SliceDestructure(SliceDestructure {
510+
input: snapshot_array_var,
511+
element_ty: elem_ty,
512+
outputs: inner_vars,
513+
success,
514+
failure: failure_node,
515+
}));
516+
}
517+
518+
// Wrap in a Deconstruct to extract @Array<T> from Span<T> once.
519+
let chain = graph.add_node(FlowControlNode::Deconstruct(Deconstruct {
520+
input: input_var,
521+
outputs: vec![snapshot_array_var],
522+
next: failure_node,
523+
}));
524+
525+
Some(chain)
526+
}
527+
528+
/// Information accumulated for a single array-size group while lowering a `Span<T>` match.
529+
///
530+
/// When matching a `Span<T>` against multiple fixed-size array patterns (e.g. `[a, b]`,
531+
/// `[a, b, c]`), the patterns are partitioned by their length. Each distinct length gets its
532+
/// own `SizeGroupInfo`.
533+
#[derive(Default)]
534+
struct SizeGroupInfo<'a, 'db> {
535+
/// The indices (into the original list of match arms) of the patterns that belong to this
536+
/// size group — including any trailing wildcard/`_` patterns, which apply to every group.
537+
filter: FilteredPatterns,
538+
/// The per-arm patterns to dispatch on once the span has been destructured into a
539+
/// fixed-size array of this length. Wildcards appear as `None`.
540+
///
541+
/// Note: unlike [VariantInfo], which stores the inner pattern of each `EnumVariant` arm,
542+
/// here we store the whole `FixedSizeArray` pattern. The next stage —
543+
/// [create_node_for_tuple_inner] — walks elements by index and extracts
544+
/// `elements_patterns[item_idx]` itself (see the `FixedSizeArray` arm in that function), so
545+
/// pre-unpacking would just force us to duplicate or undo that logic. Enum variants have a
546+
/// single inner pattern and feed into [create_node_for_patterns], which wants it already
547+
/// unwrapped, hence the asymmetry.
548+
patterns: Vec<PatternOption<'a, 'db>>,
549+
}
550+
393551
/// Helper function for [create_node_for_tuple].
394552
///
395553
/// `item_idx` is the index of the current member that is being processed in the tuple.
@@ -444,6 +602,13 @@ fn create_node_for_tuple_inner<'db>(
444602
patterns_on_current_item.push(Some(inner_pattern))
445603
}
446604
}
605+
Some(semantic::Pattern::FixedSizeArray(semantic::PatternFixedSizeArray {
606+
elements_patterns,
607+
..
608+
})) if current_member.is_none() => {
609+
patterns_on_current_item
610+
.push(Some(get_pattern(ctx, elements_patterns[item_idx]).clone()));
611+
}
447612
Some(
448613
pattern @ (semantic::Pattern::StringLiteral(..)
449614
| semantic::Pattern::EnumVariant(..)

‎crates/cairo-lang-lowering/src/lower/flow_control/graph.rs‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -224,6 +224,25 @@ pub struct Downcast {
224224
pub out_of_range: NodeId,
225225
}
226226

227+
/// Destructures a `@Array<T>` into a fixed-size array `[T; N]` via `TryInto<Span<T>, @Box<[T;
228+
/// N]>>`.
229+
///
230+
/// On success, the array has exactly `N` elements and the output variables are bound to them.
231+
/// On failure (wrong number of elements), execution continues to the `failure` node.
232+
#[derive(Debug)]
233+
pub struct SliceDestructure<'db> {
234+
/// The input `@Array<T>` variable (already extracted from the Span).
235+
pub input: FlowControlVar,
236+
/// The element type `T`. The array size `N` is `outputs.len()`.
237+
pub element_ty: semantic::TypeId<'db>,
238+
/// The output element variables (if the slice has the right size).
239+
pub outputs: Vec<FlowControlVar>,
240+
/// The next node if the slice has the right number of elements.
241+
pub success: NodeId,
242+
/// The next node if the slice doesn't have the right number of elements.
243+
pub failure: NodeId,
244+
}
245+
227246
/// An arm (final node) that returns a tuple of bound variables for the let-else success arm.
228247
///
229248
/// See [crate::lower::lower_let_else::lower_let_else] for more details.
@@ -257,6 +276,9 @@ pub enum FlowControlNode<'db> {
257276
Upcast(Upcast),
258277
/// Downcasts a value to a smaller type.
259278
Downcast(Downcast),
279+
/// Unpacks an `@Array<T>` (already extracted from a `Span<T>`) into a fixed-size array
280+
/// `[T; N]`.
281+
SliceDestructure(SliceDestructure<'db>),
260282
/// An arm (final node) that returns a tuple of bound variables for the let-else success arm.
261283
LetElseSuccess(LetElseSuccess<'db>),
262284
/// An arm (final node) that returns a unit value - `()`.
@@ -285,6 +307,7 @@ impl<'db> FlowControlNode<'db> {
285307
FlowControlNode::BindVar(node) => Some(node.input),
286308
FlowControlNode::Upcast(node) => Some(node.input),
287309
FlowControlNode::Downcast(node) => Some(node.input),
310+
FlowControlNode::SliceDestructure(node) => Some(node.input),
288311
FlowControlNode::LetElseSuccess(..) => None,
289312
FlowControlNode::UnitResult => None,
290313
FlowControlNode::Missing(_) => None,
@@ -306,6 +329,7 @@ impl<'db> Debug for FlowControlNode<'db> {
306329
FlowControlNode::BindVar(node) => node.fmt(f),
307330
FlowControlNode::Upcast(node) => node.fmt(f),
308331
FlowControlNode::Downcast(node) => node.fmt(f),
332+
FlowControlNode::SliceDestructure(node) => node.fmt(f),
309333
FlowControlNode::LetElseSuccess(node) => node.fmt(f),
310334
FlowControlNode::UnitResult => write!(f, "UnitResult"),
311335
FlowControlNode::Missing(_) => write!(f, "Missing"),

0 commit comments

Comments
 (0)