test-utils: `build_test!()` and `Test::expect_stack()` take opposite stack orders

[Qyriad]

The build_test!() family of macros take an input operand stack:

miden-vm/crates/utils/testing/src/test_builders.rs

Lines 112 to 137 in 469c139

	($in_debug_mode:expr, $source:expr, $stack_inputs:expr) => {{
	use $crate::SourceManager;
	let stack_inputs: Vec<u64> = $stack_inputs.to_vec();
	let stack_inputs = $crate::StackInputs::try_from_ints(stack_inputs).unwrap();
	let advice_inputs = $crate::AdviceInputs::default();
	let name = format!("test{}", line!());
	let source_manager = ::alloc::sync::Arc::new($crate::DefaultSourceManager::default());
	let source = source_manager.load(
	$crate::SourceLanguage::Masm,
	name.into(),
	::alloc::string::String::from($source),
	);
	$crate::Test {
	source_manager,
	source,
	kernel_source: None,
	stack_inputs,
	advice_inputs,
	in_debug_mode: $in_debug_mode,
	libraries: ::alloc::vec::Vec::default(),
	handlers: ::alloc::collections::BTreeMap::default(),
	add_modules: ::alloc::vec::Vec::default(),
	}
	}};

and Test::expect_stack() takes an expected output operand stack:

miden-vm/crates/utils/testing/src/lib.rs

Lines 225 to 232 in 469c139

	/// Builds a final stack from the provided stack-ordered array and asserts that executing the
	/// test will result in the expected final stack state.
	#[track_caller]
	pub fn expect_stack(&self, final_stack: &[u64]) {
	let result = self.get_last_stack_state().as_int_vec();
	let expected = resize_to_min_stack_depth(final_stack);
	assert_eq!(expected, result, "Expected stack to be {:?}, found {:?}", expected, result);
	}

However these two parameters are in opposite order from each other. That is, the following test succeeds:

#[test]
fn test_stack_order() {
    build_test!("begin nop end", &[0, 1, 2, 3]).expect_stack(&[3, 2, 1, 0]);
}

Technically the build_test!() family simply pass the input stack slice as Test { stack_inputs }. stack_inputs is of type StackInputs, which is documented to be in "stack-order":

miden-vm/core/src/stack/inputs.rs

Lines 12 to 17 in 469c139

	/// Defines the initial state of the VM's operand stack.
	///
	/// The values in the struct are stored in the "stack order" - i.e., the last input is at the top
	/// of the stack (in position 0).
	#[derive(Clone, Debug, Default)]
	pub struct StackInputs {

And internally expect_stack() uses StackOutputs, which is documented to be in the opposite order (though this is not called out so explicitly):

miden-vm/core/src/stack/outputs.rs

Lines 12 to 20 in 469c139

	/// Output container for Miden VM programs.
	///
	/// Miden program outputs contain the full state of the stack at the end of execution.
	///
	/// `stack` is expected to be ordered as if the elements were popped off the stack one by one.
	/// Thus, the value at the top of the stack is expected to be in the first position, and the order
	/// of the rest of the output elements will also match the order on the stack.
	#[derive(Debug, Clone, Default, PartialEq, Eq)]
	pub struct StackOutputs {

So upon investigation, this behavior is consistent, but it is very confusing; none of the docs for the testing functions, macros, or structs mention this. In fact, expect_stack() claims that its parameter is in stack order:

Builds a final stack from the provided stack-ordered array and asserts that executing the test will result in the expected final stack state.

[Emphasis mine]

Was expect_stack() intended to take stack-order, or is this purely a docs issue?

[bitwalker]

This is a problem in a lot of places IMO. I think it would make sense to have all macros/abstractions like this take an input array/vec/whatever where the top of the stack is the first item in the collection, to reflect how we document the state of the operand stack in MASM. The inverse only makes sense because IIRC the actual stack implementation uses a Vec and so wants the top of the stack to be the last element, so we end up doing all this reversing nonsense. We could unify things by having our stack implementation use a VecDeque instead of a Vec, but I'm not sure if there are any other places where the inverse order (top is last) is better for whatever reason.

As for whether expect_stack is intended to take "stack order" (which is honestly still ambiguous to me, I guess it means "order in which our specific implementation of a stack data structure stores elements) - I'm not sure, but I'd be in favor of having all stack inputs/outputs be in the same order personally.

[plafer]

Agreed - "stack order" is still unclear to me. We should definitely make this consistent across the codebase (although haven't thought about the specifics yet).

[bobbinth]

I'm in favor of changing the user-facing aspects of this to be in the "normal order" (e.g., changing StackInputs to be in the same order as StackOutputs). The internal handling could for now remain as is, and I think it'll be changed anyways with how the FastProcessor handles the stack anyways.

This will be a pretty large change though (mostly because most tests would need to be updated).