Pre-RFC: Array fill syntax

language design
22

A straw proposal:

let arr: [u32; 100] = [42; 100; 11: 1, 22: 2, 33: 3];

That would declare an array where most of the entries are 42, except for 11, 22, and 33; it'd also be unambiguous, since a second ; in a slice declaration would usually be a parse error.

That has the disadvantage of putting the default value at the beginning, whereas struct initializers put the "base struct" at the end. I'm not sure if those two syntaxes are sufficiently analogous as to make them seem like they should use similar syntax, though.

3 Likes
23

How about:

let arr: [u32; 100] = [11: 1, 22: 2, 33: 3; 42];

with syntax [ INDEX: VALUE [INDEX: VALUE [...]]]; DEFAULT ]

24

I'd like something that is more explicit, e.g.

let arr = [default: 4, 11: 1, 22: 2, 33: 3; 42];

However, I think it would be even better to make this a macro:

let arr = array![default: 4, 11: 1, 22: 2, 33: 3; 42];

// desugars to
let arr = {
    let mut arr = [4; 42];
    arr[11] = 1;
    arr[22] = 2;
    arr[33] = 3;
    arr
};

Unless there's evidence that this can't be optimized well enough?

P.S. We have to be careful that the syntax doesn't conflict with type ascription. If it always starts with the default keyword, it should be fine.

4 Likes
25

Small proof of concept [playground]:

macro_rules! arr {
    [default: $fallback:expr; $len:expr; $($ix:literal:$val:expr),* $(,)?] => {{
        const LEN: usize = $len;
        let mut arr = [$fallback; LEN];
        $(arr[$ix] = $val;)*
        arr
    }}
}

#[no_mangle]
#[inline(never)]
fn make_array(fallback: i32) {
    let arr = arr![default: fallback; 42; 11: 1, 22: 2, 33: 3];
    use_array(&arr);
}
Generated Code

MIR:

fn make_array(_1: i32) -> () {
    debug fallback => _1;                // in scope 0 at src/main.rs:19:15: 19:23
    let mut _0: ();                      // return place in scope 0 at src/main.rs:19:30: 19:30
    let _2: [i32; 42];                   // in scope 0 at src/main.rs:20:9: 20:12
    let mut _3: [i32; 42];               // in scope 0 at src/main.rs:4:13: 4:20
    let mut _4: i32;                     // in scope 0 at src/main.rs:20:29: 20:37
    let _5: usize;                       // in scope 0 at src/main.rs:20:43: 20:45
    let _6: usize;                       // in scope 0 at src/main.rs:20:50: 20:52
    let _7: usize;                       // in scope 0 at src/main.rs:20:57: 20:59
    let _8: ();                          // in scope 0 at src/main.rs:21:5: 21:20
    let mut _9: &[i32];                  // in scope 0 at src/main.rs:21:15: 21:19
    let mut _10: &[i32; 42];             // in scope 0 at src/main.rs:21:15: 21:19
    let _11: &[i32; 42];                 // in scope 0 at src/main.rs:21:15: 21:19
    scope 1 {
        debug arr => _2;                 // in scope 1 at src/main.rs:20:9: 20:12
    }
    scope 2 {
        debug arr => _3;                 // in scope 2 at src/main.rs:4:13: 4:20
    }

    bb0: {
        StorageLive(_2);                 // scope 0 at src/main.rs:20:9: 20:12
        StorageLive(_3);                 // scope 0 at src/main.rs:4:13: 4:20
        StorageLive(_4);                 // scope 0 at src/main.rs:20:29: 20:37
        _4 = _1;                         // scope 0 at src/main.rs:20:29: 20:37
        _3 = [move _4; LEN];             // scope 0 at src/main.rs:4:23: 4:39
        StorageDead(_4);                 // scope 0 at src/main.rs:4:38: 4:39
        StorageLive(_5);                 // scope 2 at src/main.rs:20:43: 20:45
        _5 = const 11usize;              // scope 2 at src/main.rs:20:43: 20:45
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Value(Scalar(0x000000000000000b))
                                         // mir::Constant
                                         // + span: src/main.rs:20:43: 20:45
                                         // + literal: Const { ty: usize, val: Value(Scalar(0x000000000000000b)) }
        _3[_5] = const 1i32;             // scope 2 at src/main.rs:5:11: 5:19
                                         // ty::Const
                                         // + ty: i32
                                         // + val: Value(Scalar(0x00000001))
                                         // mir::Constant
                                         // + span: src/main.rs:20:47: 20:48
                                         // + literal: Const { ty: i32, val: Value(Scalar(0x00000001)) }
        StorageDead(_5);                 // scope 2 at src/main.rs:5:26: 5:27
        StorageLive(_6);                 // scope 2 at src/main.rs:20:50: 20:52
        _6 = const 22usize;              // scope 2 at src/main.rs:20:50: 20:52
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Value(Scalar(0x0000000000000016))
                                         // mir::Constant
                                         // + span: src/main.rs:20:50: 20:52
                                         // + literal: Const { ty: usize, val: Value(Scalar(0x0000000000000016)) }
        _3[_6] = const 2i32;             // scope 2 at src/main.rs:5:11: 5:19
                                         // ty::Const
                                         // + ty: i32
                                         // + val: Value(Scalar(0x00000002))
                                         // mir::Constant
                                         // + span: src/main.rs:20:54: 20:55
                                         // + literal: Const { ty: i32, val: Value(Scalar(0x00000002)) }
        StorageDead(_6);                 // scope 2 at src/main.rs:5:26: 5:27
        StorageLive(_7);                 // scope 2 at src/main.rs:20:57: 20:59
        _7 = const 33usize;              // scope 2 at src/main.rs:20:57: 20:59
                                         // ty::Const
                                         // + ty: usize
                                         // + val: Value(Scalar(0x0000000000000021))
                                         // mir::Constant
                                         // + span: src/main.rs:20:57: 20:59
                                         // + literal: Const { ty: usize, val: Value(Scalar(0x0000000000000021)) }
        _3[_7] = const 3i32;             // scope 2 at src/main.rs:5:11: 5:19
                                         // ty::Const
                                         // + ty: i32
                                         // + val: Value(Scalar(0x00000003))
                                         // mir::Constant
                                         // + span: src/main.rs:20:61: 20:62
                                         // + literal: Const { ty: i32, val: Value(Scalar(0x00000003)) }
        StorageDead(_7);                 // scope 2 at src/main.rs:5:26: 5:27
        _2 = _3;                         // scope 2 at src/main.rs:6:9: 6:12
        StorageDead(_3);                 // scope 0 at src/main.rs:7:5: 7:6
        StorageLive(_8);                 // scope 1 at src/main.rs:21:5: 21:20
        StorageLive(_9);                 // scope 1 at src/main.rs:21:15: 21:19
        StorageLive(_10);                // scope 1 at src/main.rs:21:15: 21:19
        StorageLive(_11);                // scope 1 at src/main.rs:21:15: 21:19
        _11 = &_2;                       // scope 1 at src/main.rs:21:15: 21:19
        _10 = _11;                       // scope 1 at src/main.rs:21:15: 21:19
        _9 = move _10 as &[i32] (Pointer(Unsize)); // scope 1 at src/main.rs:21:15: 21:19
        StorageDead(_10);                // scope 1 at src/main.rs:21:18: 21:19
        _8 = const use_array(move _9) -> bb1; // scope 1 at src/main.rs:21:5: 21:20
                                         // ty::Const
                                         // + ty: for<'r> fn(&'r [i32]) {use_array}
                                         // + val: Value(Scalar(<ZST>))
                                         // mir::Constant
                                         // + span: src/main.rs:21:5: 21:14
                                         // + literal: Const { ty: for<'r> fn(&'r [i32]) {use_array}, val: Value(Scalar(<ZST>)) }
    }

    bb1: {
        StorageDead(_9);                 // scope 1 at src/main.rs:21:19: 21:20
        StorageDead(_11);                // scope 1 at src/main.rs:21:20: 21:21
        StorageDead(_8);                 // scope 1 at src/main.rs:21:20: 21:21
        _0 = const ();                   // scope 0 at src/main.rs:19:30: 22:2
                                         // ty::Const
                                         // + ty: ()
                                         // + val: Value(Scalar(<ZST>))
                                         // mir::Constant
                                         // + span: src/main.rs:19:30: 22:2
                                         // + literal: Const { ty: (), val: Value(Scalar(<ZST>)) }
        StorageDead(_2);                 // scope 0 at src/main.rs:22:1: 22:2
        return;                          // scope 0 at src/main.rs:22:2: 22:2
    }
}

; Function Attrs: noinline nonlazybind uwtable
define void @make_array(i32 %fallback) unnamed_addr #2 {
start:
  %arr1 = alloca [42 x i32], align 16
  %arr = alloca [42 x i32], align 4
  %0 = bitcast [42 x i32]* %arr to i8*
  call void @llvm.lifetime.start.p0i8(i64 168, i8* nonnull %0)
  %1 = bitcast [42 x i32]* %arr1 to i8*
  call void @llvm.lifetime.start.p0i8(i64 168, i8* nonnull %1)
  %2 = insertelement <4 x i32> undef, i32 %fallback, i32 0
  %3 = shufflevector <4 x i32> %2, <4 x i32> undef, <4 x i32> zeroinitializer
  %4 = bitcast [42 x i32]* %arr1 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %4, align 16
  %5 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 4
  %6 = bitcast i32* %5 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %6, align 16
  %7 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 8
  store i32 %fallback, i32* %7, align 16
  %8 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 9
  store i32 %fallback, i32* %8, align 4
  %9 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 10
  store i32 %fallback, i32* %9, align 8
  %10 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 12
  %11 = bitcast i32* %10 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %11, align 16
  %12 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 16
  store i32 %fallback, i32* %12, align 16
  %13 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 17
  %14 = bitcast i32* %13 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %14, align 4
  %15 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 21
  store i32 %fallback, i32* %15, align 4
  %16 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 23
  %17 = bitcast i32* %16 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %17, align 4
  %18 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 27
  %19 = bitcast i32* %18 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %19, align 4
  %20 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 31
  store i32 %fallback, i32* %20, align 4
  %21 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 32
  store i32 %fallback, i32* %21, align 16
  %22 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 34
  store i32 %fallback, i32* %22, align 8
  %23 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 35
  %24 = bitcast i32* %23 to <4 x i32>*
  store <4 x i32> %3, <4 x i32>* %24, align 4
  %25 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 39
  store i32 %fallback, i32* %25, align 4
  %26 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 40
  store i32 %fallback, i32* %26, align 16
  %27 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 41
  store i32 %fallback, i32* %27, align 4
  %28 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 11
  store i32 1, i32* %28, align 4
  %29 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 22
  store i32 2, i32* %29, align 8
  %30 = getelementptr inbounds [42 x i32], [42 x i32]* %arr1, i64 0, i64 33
  store i32 3, i32* %30, align 4
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 4 %0, i8* nonnull align 16 %1, i64 168, i1 false)
  call void @llvm.lifetime.end.p0i8(i64 168, i8* nonnull %1)
  %_9.0 = bitcast [42 x i32]* %arr to [0 x i32]*
  call void @use_array([0 x i32]* noalias nonnull readonly align 4 %_9.0, i64 42)
  call void @llvm.lifetime.end.p0i8(i64 168, i8* nonnull %0)
  ret void
}

Generated ASM (on the playground)

make_array:                             # @make_array
# %bb.0:
	pushq	%rbx
	subq	$336, %rsp              # imm = 0x150
	movd	%edi, %xmm0
	pshufd	$0, %xmm0, %xmm0        # xmm0 = xmm0[0,0,0,0]
	movdqa	%xmm0, (%rsp)
	movdqa	%xmm0, 16(%rsp)
	movl	%edi, 32(%rsp)
	movl	%edi, 36(%rsp)
	movl	%edi, 40(%rsp)
	movdqa	%xmm0, 48(%rsp)
	movl	%edi, 64(%rsp)
	movdqu	%xmm0, 68(%rsp)
	movl	%edi, 84(%rsp)
	movdqu	%xmm0, 92(%rsp)
	movdqu	%xmm0, 108(%rsp)
	movl	%edi, 124(%rsp)
	movl	%edi, 128(%rsp)
	movl	%edi, 136(%rsp)
	movdqu	%xmm0, 140(%rsp)
	movl	%edi, 156(%rsp)
	movl	%edi, 160(%rsp)
	movl	%edi, 164(%rsp)
	movl	$1, 44(%rsp)
	movl	$2, 88(%rsp)
	movl	$3, 132(%rsp)
	leaq	168(%rsp), %rbx
	movq	%rsp, %rsi
	movl	$168, %edx
	movq	%rbx, %rdi
	callq	*memcpy@GOTPCREL(%rip)
	movl	$42, %esi
	movq	%rbx, %rdi
	callq	use_array
	addq	$336, %rsp              # imm = 0x150
	popq	%rbx
	retq
                                        # -- End function

That's probably a bit more dumped low level representation than necessary, but the important note is one specific line of asm:

	callq	*memcpy@GOTPCREL(%rip)

This is also visible in the MIR as

let _2: [i32; 42];
let mut _3: [i32; 42];
// ...
        _2 = _3;

and (optimized) LLIR as

  %arr1 = alloca [42 x i32], align 16
  %arr = alloca [42 x i32], align 4
  %0 = bitcast [42 x i32]* %arr to i8*
  ; ...
  %1 = bitcast [42 x i32]* %arr1 to i8*
  ; ...
  call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 4 %0, i8* nonnull align 16 %1, i64 168, i1 false)

This is proof that the temporary is not getting optimized out with this specific macro and invocation, and that the compiler could do better here. (Either by the language providing a way of writing this inplace, or just by optimizing this better (NRVO for the scope).)

1 Like
26

This feels like a good time to plug the Placement-by-return RFC.

2 Likes
27

I think the arrayvec crate provides the most idiomatic approach here.

We only really need const { } blocks for this:

let x: [i32; 6] = const {
    [1,2,3].iter().cloned().chain(repeat(0)).take(6)
    .collect::<ArrayVec<[i32; 6]>>.into_inner().unwrap()
}

If const iterators and collect work then maybe enough arrayvec methods being const suffices too, like ArrayVec::into_inner and ArrayVec<A>: FromIterator<<A as Array>::Item>.

As for sugar, we could simply add this function to the arrayvec crate

const fn array_from_iter<A,I>(ii: I) -> A 
where A: Array, I: IntoIterator<<A as Array>::Item>
{
    const { ii.into_iter().collect::<ArrayVec<A>>.into_inner().unwrap() }
}

An extension trait for Iterator works too:

pub trait ToArray<A: Array> {
    const fn to_array<A>(self) -> A;
}
impl<A,I> ToArray<A> for I
where A: Array, I: Iterator<<A as Array>::Item>
{
    const fn to_array<A>(self) -> A {
        const { iter.collect::<ArrayVec<A>>.into_inner().unwrap() }
    }
}

We could even add arrayvec to core and make ToArray part of Iterator.

1 Like
28

I don't honestly know. I've written a few programs that had big static arrays in them, but the contents of those arrays were machine-generated, and for that it's easiest to dump out the entire array including all the zeroes.

I can say, though, that I can imagine interesting use cases of this feature that involve large arrays (tens to hundreds of kB), large enough to cause a serious performance penalty if they had to be initialized at runtime, possibly on every call to a hot function. I think people would be much more likely to use the feature if it came with a guarantee that the array would still make it into .rodata.

1 Like
29

Wouldn't that bloat the binary size? I'm not an expert, but I think that if you need a large array with most of the values set to a default, initializing it at runtime is more efficient. Unless you just need an immutable slice.

1 Like
30

Potentially yes, but if you have to allocate a large array, blank it, and initialize a few entries every time a routine is called, that may well be worse, if only because it pollutes the RAM cache.

Also, I don't have a reference to hand, but I recall a GCC bug report circa 2005, involving a C++ object containing a very large (probably tens of megabytes) data array with something like 25% of the entries initialized. The code emitted for the constructor was larger than a preinitialized array in .rodata would have been, and -- being thousands of independent stores to memory -- it hit the worst case of a quadratic algorithm in the scheduler and took several minutes to compile.

31

You can of course assign the macro call to a static (which means that the initialization only happens once) or a const (which will force const evaluation, so the whole array is inlined in the binary).

But if you want a mutable array, it must to be copied onto the stack, so the difference in performance is probably marginal.

32

I just published the array-lit crate :tada:

It offers two macros, arr! and vec!, which have the same syntax:

use array_lit::arr;

const ARRAY1: [i32; 8] = arr![1, 2, 3; default: 5; 8];
const ARRAY2: [i32; 8] = arr![default: 5, 7: 0; 8];

assert_eq!(ARRAY1, [1, 2, 3, 5, 5, 5, 5, 5]);
assert_eq!(ARRAY2, [5, 5, 5, 5, 5, 5, 5, 0]);

Playground

5 Likes
33

Won't the vec! macro potentially clash with std's vec!?

34

Yes. It can do everything that std::vec! can, so I thought it's fine to shadow it. Also I didn't come up with a better name. You can rename it with use array_lit::vec as ... if you want.

35

To me proposals that mix ,, : and ; are very difficult to read. I'm already unhappy about similarity of [a, b] and [a; b].

The syntax of array-lit is cryptic to me. I've re-read this 10 times, and still don't get it:

let a = arr![1, 2; default: 3, 6: 0; 8];

I know usually "unreadable" is just very subjective and mostly side-effect of what one is being used to, but I really find this hard to read. It's a very dense syntax: every separator is different, and has huge implications. I don't see what is a value, what is a size, and there's no visual grouping.

OTOH C99 syntax is much clearer (there's a separate construct for assignment to an index, not merely difference of one dot), and it's more self-explanatory.

17 Likes
36

I wasn't aware that it's that hard to understand. The idea is that arguments before the default are inserted at the beginning of the array. Arguments after the default are inserted at specific indices. In practice, you probably never need both.

EDIT: I came up with a different syntax, is this easier to read?

// specify first 2 elements:
arr![0; 5; [1, 2]] == [1, 2, 0, 0, 0]
// specify index 4:
arr![0; 5; { 4: 4 }] == [0, 0, 0, 0, 4]
// specify first 2 elements and index 4:
arr![0; 5; [1, 2]; { 4: 4 }] == [1, 2, 0, 0, 4]

It has this grammar:

MACRO ::= Default ";" Length
          (";" "[" PositionalArgs "]")?
          (";" "{" IndexArgs "}")?
1 Like
37

Unfortunately I have to very strongly and emphatically agree with the readability complaint. Even after having the meaning spelled out to me in perfectly unambiguous detail, I still struggle to parse the simplest examples of it.

I do think macro libraries are the way to go for this. My first thought for a human-readable syntax would be this:

// most of these args are optional, and you'd never use them all at once
let arr = arr!([u32; 100],
    default = 0,
    start = [1, 2, 3],
    5 = 42,
    8 = 123,
    10-20 = 7,
    21-23 = [1, 2, 3],
    end = [99, 100]
);

That would make it easy to gather data on which of these various options are actually useful in practice. So we don't need to keep playing the whole "who would use this?" "no one until it's in std" ping-pong game.

If we really want some builtin syntax for this (which IMO is unlikely, but still), I'd suggest taking our existing default syntax of [val; count] and extending it with the far more comprehensible C99 syntax for initializing specific members. Here's one strawman in that vein:

let arr: [u32; 10] = [0; 10; {
    [5] = 42,
    [8] = 123,
}];
// [0, 0, 0, 0, 0, 42, 0, 0, 123, 0]

I don't exactly like it, but honestly the part I dislike is just the well-known complaint about [x, y] vs [x; y] being too similar. Adding a new syntax for default values would only make that situation worse. And anything more elaborate than this should clearly be in a crate.

6 Likes
38

As a "minor" extension to that syntax:

let arr: [u32; 100] = [0; 100; {
    [0..3]: [1, 2, 3],
    [5] = 42,
    [8] = 123,
    [10..20]: 7,
    [21..=23]: [1, 2, 3],
    [98..100]: [99, 100]
}];
2 Likes
39

Maybe this is overthinking the strawman, but would we really want to use = for single values and : for multiple values, rather than one or the other sigil for both? (but allowing ranges definitely makes sense)

4 Likes
40

I think there are some error-detection and clarity advantages to using different sigils for single-index assignment vs subrange assignment. I'd also like to see an optional initial default that could precede assignments to overlapping indices, as in

let arr: [u32; 100] = [0; 100; {
    [..]: 0xDEADBEEF,
    [0..3]: [1, 2, 3],
    [5] = 42,
    [8] = 123,
    [10..20]: 7,
    [21..=23]: [1, 2, 3],
    [98..100]: [99, 100],
}];
3 Likes
41

I think you're onto something with the [..]: syntax there. If we're going to support ranges anyway, we could support specifying the default using a complete range, and not need to combine it with anything else. Then the compiler can error if you haven't specified a value for every element.

That seems cleaner than having a special syntax for the default element.

5 Likes