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

Commit e748528

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 37e76f1 commit e748528

7 files changed

Lines changed: 873 additions & 21 deletions

File tree

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

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,33 @@ 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] => {
23+
assert_eq!(a, @10);
24+
assert_eq!(b, @20);
25+
assert_eq!(c, @30);
26+
},
27+
_ => panic!("Expected 3 elements, but got a different pattern"),
28+
}
29+
}
30+
31+
#[test]
32+
fn test_match_span_empty_pattern() {
33+
let span: Span<u32> = array![].span();
34+
35+
match span {
36+
[_a] => { panic!("Expected 0 elements, but got 1"); },
37+
[] => {},
38+
_ => panic!("Expected 0 elements, but got a different count"),
39+
}
40+
}
41+
1542
#[test]
1643
fn test_match_extern_multilevel() {
1744
if true {
@@ -24,3 +51,17 @@ fn test_match_extern_multilevel() {
2451
}
2552
panic!("Match expression did not return - this should be unreachable");
2653
}
54+
55+
56+
#[test]
57+
fn test_match_span_inner_pattern_mismatch() {
58+
let matcher = |s: Array<Option<felt252>>| match s.span() {
59+
[Some(_)] => 1,
60+
[None] => 2,
61+
_ => 0,
62+
};
63+
64+
assert_eq!(matcher(array![Some(42)]), 1);
65+
assert_eq!(matcher(array![None]), 2);
66+
assert_eq!(matcher(array![Some(1), Some(2)]), 0);
67+
}

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

Lines changed: 178 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -2,17 +2,23 @@ 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::{
7+
CorelibSemantic, get_usize_ty, try_get_core_ty_by_name, validate_literal,
8+
};
69
use cairo_lang_semantic::expr::compute::unwrap_pattern_type;
10+
use cairo_lang_semantic::items::constant::ConstValue;
711
use cairo_lang_semantic::items::enm::SemanticEnumEx;
812
use cairo_lang_semantic::items::structure::StructSemantic;
13+
use cairo_lang_semantic::types::wrap_in_snapshots;
914
use cairo_lang_semantic::{
1015
self as semantic, ConcreteEnumId, ConcreteStructId, ConcreteTypeId, ExprNumericLiteral,
11-
PatternEnumVariant, PatternLiteral, PatternStruct, PatternTuple, PatternWrappingInfo, TypeId,
12-
TypeLongId, corelib,
16+
GenericArgumentId, PatternEnumVariant, PatternLiteral, PatternStruct, PatternTuple,
17+
PatternWrappingInfo, TypeId, TypeLongId, corelib,
1318
};
1419
use cairo_lang_syntax::node::TypedStablePtr;
1520
use cairo_lang_syntax::node::ast::ExprPtr;
21+
use cairo_lang_utils::Intern;
1622
use cairo_lang_utils::ordered_hash_map::OrderedHashMap;
1723
use itertools::{Itertools, zip_eq};
1824
use num_bigint::BigInt;
@@ -26,7 +32,9 @@ use super::filtered_patterns::{Bindings, FilteredPatterns};
2632
use crate::diagnostic::{LoweringDiagnosticKind, MatchDiagnostic, MatchError};
2733
use crate::ids::LocationId;
2834
use crate::lower::context::LoweringContext;
29-
use crate::lower::flow_control::graph::{Downcast, EqualsLiteral, Upcast, ValueMatch};
35+
use crate::lower::flow_control::graph::{
36+
Downcast, EqualsLiteral, SliceDestructure, Upcast, ValueMatch,
37+
};
3038

3139
/// A callback that gets a [FilteredPatterns] and constructs a node that continues the pattern
3240
/// matching restricted to the filtered patterns.
@@ -150,21 +158,6 @@ pub fn create_node_for_patterns<'db>(
150158
create_node_for_enum(params, input_var, concrete_enum_id, wrapping_info)
151159
}
152160
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-
}
168161
create_node_for_struct(params, input_var, concrete_struct_id, wrapping_info)
169162
}
170163
TypeLongId::Tuple(types) => create_node_for_tuple(params, input_var, &types, wrapping_info),
@@ -354,6 +347,19 @@ fn create_node_for_struct<'db>(
354347
) -> NodeId {
355348
let CreateNodeParams { ctx, graph, patterns, build_node_callback, location } = params;
356349

350+
if let Some(node) = try_create_slice_destructure_chain(
351+
ctx,
352+
graph,
353+
patterns,
354+
build_node_callback,
355+
location,
356+
input_var,
357+
concrete_struct_id,
358+
wrapping_info,
359+
) {
360+
return node;
361+
}
362+
357363
let members = match ctx.db.concrete_struct_members(concrete_struct_id) {
358364
Ok(members) => members,
359365
Err(diag_added) => return graph.add_node(FlowControlNode::Missing(diag_added)),
@@ -390,6 +396,152 @@ fn create_node_for_struct<'db>(
390396
}))
391397
}
392398

399+
/// Tries to create a chain of [`SliceDestructure`] nodes for matching a `Span<T>` against
400+
/// fixed-size array patterns with different sizes.
401+
///
402+
/// Returns `None` if no `FixedSizeArray` patterns are present or the struct is not a `Span`.
403+
/// Each size is tried in order. On failure, the next size is attempted. If all sizes fail,
404+
/// the wildcard/otherwise patterns are used.
405+
#[allow(clippy::too_many_arguments)]
406+
fn try_create_slice_destructure_chain<'db>(
407+
ctx: &LoweringContext<'db, '_>,
408+
graph: &mut FlowControlGraphBuilder<'db>,
409+
patterns: &[PatternOption<'_, 'db>],
410+
build_node_callback: BuildNodeCallback<'db, '_>,
411+
location: LocationId<'db>,
412+
input_var: FlowControlVar,
413+
concrete_struct_id: ConcreteStructId<'db>,
414+
wrapping_info: PatternWrappingInfo,
415+
) -> Option<NodeId> {
416+
if !patterns.iter().any(|p| matches!(p, Some(semantic::Pattern::FixedSizeArray(..)))) {
417+
return None;
418+
}
419+
let [GenericArgumentId::Type(elem_ty)] = concrete_struct_id.long(ctx.db).generic_args[..]
420+
else {
421+
return None;
422+
};
423+
if try_get_core_ty_by_name(
424+
ctx.db,
425+
SmolStrId::from(ctx.db, "Span"),
426+
vec![GenericArgumentId::Type(elem_ty)],
427+
)
428+
.is_err()
429+
{
430+
// Not a Span - report error on the first FixedSizeArray pattern.
431+
let first_fsa = patterns.iter().find_map(|p| match p {
432+
Some(semantic::Pattern::FixedSizeArray(p)) => Some(p),
433+
_ => None,
434+
});
435+
return Some(graph.report_with_missing_node(
436+
first_fsa.unwrap().stable_ptr.untyped(),
437+
LoweringDiagnosticKind::UnexpectedError,
438+
));
439+
}
440+
// Deconstruct Span<T> to get its single member @Array<T>.
441+
let members = ctx.db.concrete_struct_members(concrete_struct_id).ok()?;
442+
let snapshot_array_ty = members.iter().next().unwrap().1.ty;
443+
let snapshot_array_var = graph.new_var(snapshot_array_ty, location);
444+
445+
// Group patterns by array size. Wildcards/otherwise are added to all groups.
446+
// Use an OrderedHashMap to preserve insertion order (first-seen size first).
447+
let mut size_groups: OrderedHashMap<usize, SizeGroupInfo<'_, '_>> = OrderedHashMap::default();
448+
let mut wildcard_filter = FilteredPatterns::default();
449+
450+
for (idx, pattern) in patterns.iter().enumerate() {
451+
match pattern {
452+
Some(semantic::Pattern::FixedSizeArray(p)) => {
453+
let n = p.elements_patterns.len();
454+
let group = size_groups.entry(n).or_default();
455+
456+
group.filter.add(idx);
457+
group.patterns.push(*pattern);
458+
}
459+
Some(semantic::Pattern::Otherwise(..)) | None => {
460+
wildcard_filter.add(idx);
461+
for group in size_groups.values_mut() {
462+
group.filter.add(idx);
463+
group.patterns.push(None);
464+
}
465+
break;
466+
}
467+
Some(pattern) => {
468+
// This should not be reachable without getting a semantic error.
469+
return Some(graph.report_with_missing_node(
470+
pattern.stable_ptr().untyped(),
471+
LoweringDiagnosticKind::UnexpectedError,
472+
));
473+
}
474+
}
475+
}
476+
477+
let sizes: Vec<usize> = size_groups.keys().copied().collect();
478+
479+
// Build the chain from back to front. The final fallback is the wildcard-only callback.
480+
let mut failure_node = build_node_callback(graph, wildcard_filter, "[slice_no_match]".into());
481+
482+
for &size in sizes.iter().rev() {
483+
let group = size_groups.swap_remove(&size).unwrap();
484+
let n = size;
485+
let types = vec![wrap_in_snapshots(ctx.db, elem_ty, 1); n];
486+
let inner_vars = types
487+
.iter()
488+
.map(|ty| graph.new_var(wrapping_info.wrap(ctx.db, *ty), location))
489+
.collect_vec();
490+
491+
// Build the success path: process element patterns within this size group.
492+
let group_filter = group.filter;
493+
let group_patterns: Vec<PatternOption<'_, 'db>> = group.patterns;
494+
let success = create_node_for_tuple_inner(
495+
CreateNodeParams {
496+
ctx,
497+
graph,
498+
patterns: &group_patterns,
499+
build_node_callback: &mut |graph, pattern_indices, path| {
500+
build_node_callback(
501+
graph,
502+
pattern_indices.lift(&group_filter),
503+
format!("[{path}]"),
504+
)
505+
},
506+
location,
507+
},
508+
&inner_vars,
509+
&types,
510+
0,
511+
None,
512+
);
513+
514+
let fixed_array_ty = TypeLongId::FixedSizeArray {
515+
type_id: elem_ty,
516+
size: ConstValue::Int(n.into(), get_usize_ty(ctx.db)).intern(ctx.db),
517+
}
518+
.intern(ctx.db);
519+
520+
failure_node = graph.add_node(FlowControlNode::SliceDestructure(SliceDestructure {
521+
input: snapshot_array_var,
522+
fixed_array_ty,
523+
outputs: inner_vars,
524+
success,
525+
failure: failure_node,
526+
}));
527+
}
528+
529+
// Wrap in a Deconstruct to extract @Array<T> from Span<T> once.
530+
let chain = graph.add_node(FlowControlNode::Deconstruct(Deconstruct {
531+
input: input_var,
532+
outputs: vec![snapshot_array_var],
533+
next: failure_node,
534+
}));
535+
536+
Some(chain)
537+
}
538+
539+
#[derive(Default)]
540+
struct SizeGroupInfo<'a, 'db> {
541+
filter: FilteredPatterns,
542+
patterns: Vec<PatternOption<'a, 'db>>,
543+
}
544+
393545
/// Helper function for [create_node_for_tuple].
394546
///
395547
/// `item_idx` is the index of the current member that is being processed in the tuple.
@@ -444,6 +596,13 @@ fn create_node_for_tuple_inner<'db>(
444596
patterns_on_current_item.push(Some(inner_pattern))
445597
}
446598
}
599+
Some(semantic::Pattern::FixedSizeArray(semantic::PatternFixedSizeArray {
600+
elements_patterns,
601+
..
602+
})) if current_member.is_none() => {
603+
patterns_on_current_item
604+
.push(Some(get_pattern(ctx, elements_patterns[item_idx]).clone()));
605+
}
447606
Some(
448607
pattern @ (semantic::Pattern::StringLiteral(..)
449608
| semantic::Pattern::EnumVariant(..)

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

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -224,6 +224,35 @@ 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+
pub struct SliceDestructure<'db> {
233+
/// The input `@Array<T>` variable (already extracted from the Span).
234+
pub input: FlowControlVar,
235+
/// The fixed-size array type `[T; N]`.
236+
pub fixed_array_ty: semantic::TypeId<'db>,
237+
/// The output element variables (if the slice has the right size).
238+
pub outputs: Vec<FlowControlVar>,
239+
/// The next node if the slice has the right number of elements.
240+
pub success: NodeId,
241+
/// The next node if the slice doesn't have the right number of elements.
242+
pub failure: NodeId,
243+
}
244+
impl Debug for SliceDestructure<'_> {
245+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
246+
f.debug_struct("SliceDestructure")
247+
.field("input", &self.input)
248+
.field("n_elements", &self.outputs.len())
249+
.field("outputs", &self.outputs)
250+
.field("success", &self.success)
251+
.field("failure", &self.failure)
252+
.finish()
253+
}
254+
}
255+
227256
/// An arm (final node) that returns a tuple of bound variables for the let-else success arm.
228257
///
229258
/// See [crate::lower::lower_let_else::lower_let_else] for more details.
@@ -257,6 +286,8 @@ pub enum FlowControlNode<'db> {
257286
Upcast(Upcast),
258287
/// Downcasts a value to a smaller type.
259288
Downcast(Downcast),
289+
/// Unpacks a `Span<T>` into a fixed-size array `[T; N]`.
290+
SliceDestructure(SliceDestructure<'db>),
260291
/// An arm (final node) that returns a tuple of bound variables for the let-else success arm.
261292
LetElseSuccess(LetElseSuccess<'db>),
262293
/// An arm (final node) that returns a unit value - `()`.
@@ -285,6 +316,7 @@ impl<'db> FlowControlNode<'db> {
285316
FlowControlNode::BindVar(node) => Some(node.input),
286317
FlowControlNode::Upcast(node) => Some(node.input),
287318
FlowControlNode::Downcast(node) => Some(node.input),
319+
FlowControlNode::SliceDestructure(node) => Some(node.input),
288320
FlowControlNode::LetElseSuccess(..) => None,
289321
FlowControlNode::UnitResult => None,
290322
FlowControlNode::Missing(_) => None,
@@ -306,6 +338,7 @@ impl<'db> Debug for FlowControlNode<'db> {
306338
FlowControlNode::BindVar(node) => node.fmt(f),
307339
FlowControlNode::Upcast(node) => node.fmt(f),
308340
FlowControlNode::Downcast(node) => node.fmt(f),
341+
FlowControlNode::SliceDestructure(node) => node.fmt(f),
309342
FlowControlNode::LetElseSuccess(node) => node.fmt(f),
310343
FlowControlNode::UnitResult => write!(f, "UnitResult"),
311344
FlowControlNode::Missing(_) => write!(f, "Missing"),

0 commit comments

Comments
 (0)