A way to resize a stack (or other dynamically resizable types)

Question

First off, I've read this question:

What's the right way to make a stack (or other dynamically resizable vector-like thing) in Rust?

The problem

The selected answer just tells the question asker to use the standard library instead of explaining the implementation, which is fine if my goal was to build something. Except I'm trying to learn about the implementation of a stack, while following a data structure textbook written for Java (Algorithms by Robert Sedgwick & Kevin Wayne), where they implement a stack via resizing an array (Page 136).

I'm in the process of implementing the resize method, and it turns out the size of the array needs to be a constant expression.

meta: are arrays in rust called slices?

use std::mem;

struct DynamicStack<T> {
  length: uint,
  internal: Box<[T]>,
}

impl<T> DynamicStack<T> {
  fn new() -> DynamicStack<T> {
    DynamicStack {
      length: 0,
      internal: box [],
    }
  }

  fn resize(&mut self, new_size: uint) {
    let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };

    // ^^ error: expected constant expr for array 
    // length: non-constant path in constant expr

    // code for copying elements from self.internal

    self.internal = temp;
  }
}

For brevity the compiler error was this

.../src/lib.rs:51:23: 51:38 error: expected constant expr for array length: non-constant path in constant expr
.../src/lib.rs:51     let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };
                                        ^~~~~~~~~~~~~~~
.../src/lib.rs:51:23: 51:38 error: expected constant expr for array length: non-constant path in constant expr
.../src/lib.rs:51     let mut temp: Box<[T, ..new_size]> = box unsafe { mem::uninitialized() };
                                        ^~~~~~~~~~~~~~~

The Question

Surely there is a way in rust to initialize an array with it's size determined at runtime (even if it's unsafe)? Could you also provide an explanation of what's going on in your answer?

Other attempts

I've considered it's probably possible to implement the stack in terms of

struct DynamicStack<T> {
  length: uint,
  internal: Box<Optional<T>>
}

But I don't want the overhead of matching optional value to remove the unsafe memory operations, but this still doesn't resolve the issue of unknown array sizes.

I also tried this (which doesn't even compile)

fn resize(&mut self, new_size: uint) {
  let mut temp: Box<[T]> = box [];
  let current_size = self.internal.len();

  for i in range(0, current_size) {
    temp[i] = self.internal[i];
  }
  for i in range(current_size, new_size) {
    temp[i] = unsafe { mem::uninitialized() };
  }

  self.internal = temp;
}

And I got this compiler error

.../src/lib.rs:55:17: 55:21 error: cannot move out of dereference of `&mut`-pointer
.../src/lib.rs:55       temp[i] = self.internal[i];
                                  ^~~~
.../src/lib.rs:71:19: 71:30 error: cannot use `self.length` because it was mutably borrowed
.../src/lib.rs:71       self.resize(self.length * 2);
                                    ^~~~~~~~~~~
.../src/lib.rs:71:7: 71:11 note: borrow of `*self` occurs here
.../src/lib.rs:71       self.resize(self.length * 2);
                        ^~~~
.../src/lib.rs:79:18: 79:22 error: cannot move out of dereference of `&mut`-pointer
.../src/lib.rs:79     let result = self.internal[self.length];
                                   ^~~~
.../src/lib.rs:79:9: 79:15 note: attempting to move value to here
.../src/lib.rs:79     let result = self.internal[self.length];
                          ^~~~~~
.../src/lib.rs:79:9: 79:15 help: to prevent the move, use `ref result` or `ref mut result` to capture value by reference
.../src/lib.rs:79     let result = self.internal[self.length];

I also had a look at this, but it's been awhile since I've done any C/C++

How should you do pointer arithmetic in rust?

For your meta question, I'd suggest reading the appropriate section of the Rust Guide. — Shepmaster
If you want to create dynamically sized arrays without going using Vec, you might want to look into how Vec itself is implemented. It's done in the typical C-like fashion with a pointer and calls to heap::{allocate,deallocate} (malloc/free) inside unsafe blocks. — Gustav Larsson

Shepmaster Shepmaster · Accepted Answer · 2014-12-14T03:44:42

Surely there is a way in Rust to initialize an array with it's size determined at runtime?

No, Rust arrays are only able to be created with a size known at compile time. In fact, each tuple of type and size constitutes a new type! The Rust compiler uses that information to make optimizations.

Once you need a set of things determined at runtime, you have to add runtime checks to ensure that Rust's safety guarantees are always valid. For example, you can't access uninitialized memory (such as by walking off the beginning or end of a set of items).

If you truly want to go down this path, I expect that you are going to have to get your hands dirty with some direct memory allocation and unsafe code. In essence, you will be building a smaller version of Vec itself! To that end, you can check out the source of Vec.

At a high level, you will need to allocate chunks of memory big enough to hold N objects of some type. Then you can provide ways of accessing those elements, using pointer arithmetic under the hood. When you add more elements, you can allocate more space and move old values around. There are lots of nuanced things that may or may not come up, but it sounds like you are on the beginning of a fun journey!

Edit

Of course, you could choose to pretend that most of the methods of Vec don't even exist, and just use the ones that are analogs of Java's array. You'll still need to use Option to avoid uninitialized values though.

A way to resize a stack (or other dynamically resizable types)

The problem

The Question

Other attempts

1 Answers