Static nested struct with dynamic contents

[computermouth]

Howdy folks,

Old timey C programmer here, I've written a game in C and I'm playing with the idea of writing it in Rust as an exercise.

Background: the engine is vector based, so I have loads and loads of x and y arrays, where the data for all visuals is essentially stored like

sprite->animations[WALK]->frame[WALK0]->polygon[FACE]->x[...]
sprite->animations[WALK]->frame[WALK0]->polygon[FACE]->y[...]

So a sprite is an array of animations, animations are an array of frames, frames are arrays of polygons, and polygons are arrays of ints.

Nothing is loaded from disc, I'm basically transpiling SVGs to C structs, where the result is a macro hell of static arrays and structs in psuedocode:

// mysprite.h
extern sprite MYSPRITE;

// mysprite.c
static sprite MYSPRITE = {
  .animations = animation_t[]{
    {
      .frames = frame_t[]{
        .polygons = polygon_t[]{
          (polygon_t){
            .x = {1, 2, 3},
            .y = {3, 4, 5}
          }
        }
      }
    }
  }
}

etc, etc, but imagine this going on for 1k LOC per sprite.

And thus, all sprites are loaded from .data onto the heap, and persist for the lifetime of the application.

Anyway, I'm trying to figure out a way to essentially reproduce this in Rust. I'd like to have a way to fetch these data chunks from modules in Rust, where the end code looks like

use sprites::{bullet,character,monster};

let local_bullet = new_sprite_from(sprite::bullet);
local_bullet.x = 320;
local_bullet.y = 320;
draw_sprite(local_bullet);

This is essentially how my code functions now, except without the namespacing, everything is just global, so it's a matter of a header inclusion to just get the address.

Finally, the problem:

How do I create const static structs (or what would be a good replacement for them), with dynamic length members to create a similar tree structure?

I've tried:

// const pointers
struct CPolygon {
	x: *const [i16],
	y: *const [i16],
}

static cp: CPolygon = CPolygon {
	x: &[1, 2, 3],
	y: &[4, 5, 6],
};
// *const [i16]` cannot be shared between threads safely

// vectors
struct VPolygon {
	x: Vec<[i16]>,
	y: Vec<[i16]>,
}

static vp: VPolygon = VPolygon {
	x: [1, 2, 3],
	y: [4, 5, 6],
};
// doesn't have a size known at compile-time

// boxes
struct BPolygon {
	x: Box<[i16]>,
	y: Box<[i16]>,
}

static bp: BPolygon = BPolygon {
	x: Box::new([1, 2, 3]),
	y: Box::new([4, 5, 6]),
};
// calls in statics are limited to constant functions, tuple structs and tuple variants

// my least favorite, but seems to work, writing a ::new() function
struct NPolygon {
	x: Box<[i16]>,
	y: Box<[i16]>,
}

struct NFrame {
	polygons: Box<NPolygon>
}

fn gen_fram0() -> NFrame {
	
	let f = NFrame {
		polygons: Box::new(
			NPolygon {
				x:        Box::new([1, 2, 3]),
				y:        Box::new([4, 5, 6]),
			}
		)
	};
	
	return f;
}
//

I suppose I've answered my own question here. The bottom being the solution and just doing

use sprites::{bullet};

let local_bullet = sprites::bullet::new();
local_bullet.x = 320;
local_bullet.y = 320;
draw_sprite(local_bullet);

But as a new goober, would appreciate any feedback or tips. Thanks!

[computermouth]

Part 2 of this question would be, how can I get this data into a single contiguous memory space?

In C, my new_sprite_from function calculates the entire size of the struct, does one monster malloc, and then casts that memory to the sprite type, then sets up all the pointers, and copies in the polygon coordinate data.

With the Box solution above, I don't have contiguous memory, but I'm targeting arm, and have seen much better performance with contiguous memory than without.

I've seen some solutions with bytes and split, but then I'd be left to write out a packing format and code for unpacking.

(double-thanks)

[quinedot]

I don't know that I understand all the parameters (is this data always read-only; how uniform are the number of frames etc), but in general for putting sequences of nested structures in static memory, you can use

• Indirection with slice borrows
  • This is like your *const [i16] attempt, it is actually possible with &'static [i16]
• Arrays with a fixed size
  • E.g. if your Polygons are always triangles, you could use [i16; 3] for x and y
• Array-holding types with a const parameter
  • E.g. if all Animations of each sprite are the same number of frames, maybe you could have

    struct Animation<const FRAMES: usize> { frames: [Frame; FRAMES], }
    

  • This may end up being quite verbose/constraining though, and code monomorphizes over the parameter

Here's a quick example for illustration of the approaches, with a const parameter at the top level only (where it's the least meaningful to be honest), then slices down to the bottom level, which uses arrays. I'm guessing it all ends up in the same place .data-wise, but I didn't check and it's not guaranteed outside of individual slices.

Slices are most convenient, arrays often optimize better, const parameters may end up with a lot of similar code being generated. I would default to the slices, unless perhaps I had a layer that was always the same size across all sprites.

This may be all you're asking for, I'm not sure.

---

@computermouth

Part 2 of this question would be, how can I get this data into a single contiguous memory space?

I assume you mean the i16 at the bottom? You could perhaps do something with the bytemuck crate here^[1], but if you're generating these anyway, it's possible but ugly to do it completely at compile time. The main source of ugliness is matching on the entire slice of data to pull out individual x and y slices, due to the current const (compile-time) limitations. It would be a lot of generated code and I have no idea how slow the compilation would be. Maybe someone else on the forum knows a better way.

static SPRITE_INTS: [i16; 12] = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, ];
static SPRITE: SpriteData = SpriteData {
// ... nesting ...
            x: match &SPRITE_INTS {
                // Ugh, can't use `x: &SPRITE_INTS[6..9]`
                [_, _, _, _, _, _, this @ .., _, _, _] => this,
            },

Playground. I'd probably first see if building the slices into the SpriteData static itself resulted in "contiguous-enough" data, personally.

---

If you need to mutate this data, you're going to need owned and presumably allocated versions at run-time, which I didn't handle here. If so, perhaps provide more details (are things added to the lists or are just the integers at the bottom modified, etc.)

---

1. although non-uniform lengths may pose a challenge ↩︎

[computermouth]

Woah, wicked, ok. First, thank you!

@quinedot

Arrays with a fixed size

• E.g. if your Polygon s are always triangles, you could use [i16; 3] for x and y

Actually all elements are of a variable size. As the number of each aspect depends entirely on what the sprite is and what it's doing.

@quinedot

Array-holding types with a const parameter

• E.g. if all Animation s of each sprite are the same number of frames, maybe you could have

struct Animation { frames: [Frame; FRAMES], }

* This may end up being quite verbose/constraining though, and code monomorphizes over the parameter

This is pretty neat, and a new concept to me, structs that take parameters. IsThisTemplating.jpg

Here's what I landed on: Rust Playground

I removed the const parameter, just for testing, and expected to see it work, but suspected that the parameterized struct might yield more contiguous memory, whereas the non-parameterized would be more fragmented. But I seem to be incorrect! Maybe the compiler tries to keep it contiguous by default, which is lovely.

I do modify some other unlisted members of the structs later on, but the ones shown here ought to be const. The scaled_x in the playground link is multiplied by a factor of default_window_size / current_window_size, a la

    println!("scaled_x {:?}", SPRITE.animations[0].frames[0].polygons[0].scaled_x);
    for i in SPRITE.animations[0].frames[0].polygons[0].scaled_x {
		println!("i: {}", i);
		/* TODO, scale each int in the array
		let fi: f32 = *i as f32 * 2.5;
		i = &(fi as i16);
		*/
	}
    println!("scaled_x {:?}", SPRITE.animations[0].frames[0].polygons[0].scaled_x);

This, but actually changing the values in the array. Which I guess I'll need to look up how to actually do mapping or something. But this is a solid start!

I am a bit curious as to what the parameterized sizing offers, versus automatic sizing. Is it just author preference? Or are there times when it would prove necessary later on?

[quinedot]

@computermouth

I am a bit curious as to what the parameterized sizing offers, versus automatic sizing. Is it just author preference? Or are there times when it would prove necessary later on?

When the paramater is a compile-time constant, this is known as const generics. It's pretty new on stable and exactly what you can do at compile time is still being expanded, so sometimes it's a little constricting. It's useful when you want to be generic over all arrays, like the blog talks about. It can also be useful in a "generics as macros" sense, if you have a lot of code that would make sense with a small number of different constants (RGB and RGBA perhaps).

One thing to keep in mind for data structures in Rust is that if you have a reference, like a slice reference,

• if it's not static data, you'll be dealing with lifetimes
• the owner of the data you're referencing has to be "alive" somewhere
• being self-referencial with plain references doesn't work, so that owner will be stored separately

And this can make a large practical difference between using arrays or Vecs instead of slice references. const generics makes arrays a more practical alternative to Vec in more situations, but it's a tradeoff as always.

It crossed my mind when I was pondering how one might deal with building the structured version of your sprites at run time, but I think things would need to be way more uniform than is practical for it to be useful. If it were practical, you could have a Sprite<ANI, FRM, PLY> or whatever that didn't need indirection/separate allocations (Vec or slice references), because it would be one big chunk of arrays that you could allocate at once, say. But every animation having the same number of frames is unrealistic for even a single sprite, I'm sure.

(Even the "all my i32 are in one Vec" approach would require separate allocations to hold the intermediate data structures somewhere.)

[computermouth]

Pretty neat!

@quinedot

• if it's not static data, you'll be dealing with lifetimes
• the owner of the data you're referencing has to be "alive" somewhere

So these aren't entirely alien to me, as the same is true in C, with the exception being the lifetime of the pointer, regardless of malloc'd memory still living. So that's easy enough.

@quinedot

being self-referencial with plain references doesn't work, so that owner will be stored separately

@quinedot

And this can make a large practical difference between using arrays or Vec s instead of slice references. const generics makes arrays a more practical alternative to Vec in more situations, but it's a tradeoff as always.

These are the parts that are new. I was hoping to take an approach to Rust like people used to when adopting C++ as "C with Classes". But I think this might turn out to be a bit naive.

@quinedot

If it were practical, you could have a Sprite<ANI, FRM, PLY> or whatever that didn't need indirection/separate allocations ( Vec or slice references), because it would be one big chunk of arrays that you could allocate at once, say. But every animation having the same number of frames is unrealistic for even a single sprite, I'm sure.

Right, it's not practical, but I imagine that I can also nest those parameters to be something like:

static SPRITE: SpriteData<2> = SpriteData {
    animations: [
        Animation<4> {
            ...
        },
    ],
};

I have yet to test this, but that might be an interesting solution.

In my C code, I use these structs as a reference type, and call an initializing function that does something like

malloc(sizeof(animation_t) * num_animations + sizeof(frame_t) * num_frames)

And then just basically nested casts, and setting pointers and copy in data. But I imagine that's firmly in unsafe{} territory. But I wonder if calling a function that can do clone/copy of this struct, but into Vec or something might be more ergonomic down the road.

[quinedot]

@computermouth

In my C code, I use these structs as a reference type, and call an initializing function that does something like

malloc(sizeof(animation_t) * num_animations + sizeof(frame_t) * num_frames)

And then just basically nested casts, and setting pointers and copy in data. But I imagine that's firmly in unsafe{} territory.

I got completely sniped into thinking about how to do this in Rust with minimal unsafe, and managed a version with no unsafe at all. Now, I don't know that I really recommend using it for various reasons. For one, it's relying heavily on the optimizer to avoid a lot of copying (e.g. to infer emplacement) and pre-initialization, which feels pretty fragile.

But perhaps the main downside is that by putting everything in the same struct (for a single safe allocation), the struct becomes self-referential once you adjust all the references. I know, I said that wasn't possible -- it is possible, but you end up with a struct that is exclusively borrowed for the rest of it's lifetime. This makes the underlying struct unusable afterwards, which sometimes makes it impossible to satisfy the borrow checker at all, and is almost always too constricting. In fact, I think this is the first arguably practical use I've personally come up with.

In this case, it means the backing data is pinned to its stack location once you create the borrow, and is unusable after that (modulo using unsafe to erase lifetimes or the like). There's a bunch of comments in the code too.

Mostly not commented in the code, naturally, is how unsafe was avoided:

• Not allocating ourselves by having a struct for any size via const generics
• Going through Vec to construct an array dynamically (at an increased risk of a lot of unnecessary copying); this will be avoidable in the future as const becomes more powerful
• Being able to construct empty &mut [] out of thin air, and overwriting them later
• More generally, pre-initializing everything to default values
• Lots of split_at_mut

But I wonder if calling a function that can do clone/copy of this struct, but into Vec or something might be more ergonomic down the road.

After playing with this for awhile, I'm getting the feeling it could be somewhat more dynamic. As it is, you can't get to a given polygon non-dynamically anyway -- you have to follow the tree down from the root. So probably it wouldn't be too bad to just store the ints and offsets in a blob somehow and construct/traverse the structure by producing slices on the fly. Then you could avoid constructing a reference-heavy structure when cloning, and dealing with all the restrictions this entails; you could also carry a Vec around and re-use its allocation more easily.

After writing that out, I guess this is just an extended version of the typical Rust advice, "use indices, not references".

[computermouth]

Oh holy cow, that's awesome haha.

This code is quite beyond my fledgling understanding of Rust, but I think we've landed at the same conclusion with your last line.

I did some more digging into why these static arrays were ever contiguous in the first place, and it looks like an optimization from the jemalloc implementation. So I think I'll just ignore the contiguous memory portion, as it seems likely to happen on it's own!

Thanks for sharing your experiments!