Checking Constraints in Grue

In the previous post, I discussed at a high level the idea of some constraints that the Z-Machine specification indicates but that are up to an interpreter author to consider. In this post, I’ll do some considering.

Here I’m going to dive right into some code and implement some checks. These are not checks that are part of my tests for Grue but, rather, they are checks that are part of Grue in terms of how it operates.

From the previous post, we know that the Z-Machine specification directly states that the total of dynamic plus static memory must not exceed 64K. That’s easy enough to check.

def _memory_checks(self) -> None:
    header_size: int = 64

    if len(self.data) < header_size:
        raise RuntimeError("dynamic memory is below required 64 bytes")

This check ensures that the Z-Machine file (which starts with a 64-byte header) is large enough to contain at least the header, which is essential for proper interpretation of the zcode. Since the header contains critical information, like the starting addresses of different memory regions (dynamic, static, and high), it’s reasonable to ensure the file contains at least those 64 bytes.

Here’s another check:

def _memory_checks(self) -> None:
    header_size: int = 64

    if len(self.data) < header_size:
        raise RuntimeError("dynamic memory is below required 64 bytes")

    if self.static < header_size:
        raise RuntimeError("static memory begins before byte 64")

This check ensures that the static memory (read-only memory) does not start before the 64th byte. The header is located in the first 64 bytes of the zcode file, so static memory should not start within or before the header.

There’s yet another check I can add.

def _memory_checks(self) -> None:
    header_size: int = 64

    if len(self.data) < header_size:
        raise RuntimeError("dynamic memory is below required 64 bytes")

    if self.static < header_size:
        raise RuntimeError("static memory begins before byte 64")

    if self.dynamic > self.static:
        raise RuntimeError("dynamic memory overlaps with static memory")

This ensures that the dynamic memory region ends before (or at most, where) the static memory starts. Dynamic memory starts at the beginning of the file (just after the header), so this check is crucial for preventing overlap between dynamic and static regions.

And yet one more!

def _memory_checks(self) -> None:
    header_size: int = 64

    if len(self.data) < header_size:
        raise RuntimeError("dynamic memory is below required 64 bytes")

    if self.static < header_size:
        raise RuntimeError("static memory begins before byte 64")

    if self.dynamic > self.static:
        raise RuntimeError("dynamic memory overlaps with static memory")

    if self.static > self.high:
        raise RuntimeError("static memory overlaps with high memory")

This ensures that the static memory ends before (or at most, where) the high memory starts. Since static memory is read-only, it’s permissible for the end of static memory to overlap with the start of high memory, but static memory should never extend beyond the start of high memory.

While Python doesn’t have a hard distinction between private and public methods, I’m using an underscore with these method names to indicate that they are meant to be considered private to the Memory module.

All of those are checks that Grue, running as an interpreter, will make. But how do I test these checks to make sure Grue is operating as intended. Well, as discussed in a previous post, I do use test oracles, meaning zcode programs. However, those are valid zcode programs. There is a challenge of finding real-world zcode programs that intentionally violate memory constraints.

So what I decided to do was mock the memory layout. My goal was to create small test cases that can simulate various memory issues by modifying self.data, self.static, and self.high directly. This way, I’m not relying on actual zcode programs but rather on manually created memory regions that represent invalid states.

@pytest.fixture
def mocked_zcode_memory():
    class MockedMemory(Memory):
        def __init__(self, dynamic, static, high):
            self.dynamic = dynamic
            self.static = static
            self.high = high
            self.data = bytearray(100)

    return MockedMemory

With this in place I can test specific cases by injecting faulty values into the dynamic, static, and high memory regions. This allows me to target each of the _memory_checks method without needing a real zcode file that violates the rules. As to the tests, here is what I have:

def test_dynamic_memory_below_required_size(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=50, static=100, high=200)
    memory.data = bytearray(50)
    with pytest.raises(RuntimeError, match="dynamic memory is below required 64 bytes"):
        memory._memory_checks()


def test_static_memory_begins_before_byte_64(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=50, static=50, high=200)
    with pytest.raises(RuntimeError, match="static memory begins before byte 64"):
        memory._memory_checks()


def test_static_overlaps_high(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=50, static=200, high=100)
    with pytest.raises(RuntimeError, match="static memory overlaps with high memory"):
        memory._memory_checks()


def test_dynamic_overlaps_static(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=100, static=64, high=200)
    with pytest.raises(
        RuntimeError, match="dynamic memory overlaps with static memory"
    ):
        memory._memory_checks()

It’s also possible use a parametrize feature of Pytest to test multiple cases in a more compact way. I actually found this approach a bit more cumbersome than just writing the tests out.

One other thing the Z-Machine specification mentions is the “maximum permitted length of a story file,” which is stated to depend on the version. The values are provided as such:

V1-3   V4-5   V6-8
128K   256K   512K

This seemed like a good thing to check but technically different from a constraint on memory itself. Thus, I created another private method for this:

def _zcode_size_checks(self) -> None:
    size_limits = {
        1: 128 * 1024,
        2: 128 * 1024,
        3: 128 * 1024,
        4: 256 * 1024,
        5: 256 * 1024,
        6: 512 * 1024,
        7: 512 * 1024,
        8: 512 * 1024,
    }

    total_size: int = len(self.data)

    if self.version not in size_limits:
        raise RuntimeError(
            f"Unsupported Z-Machine version: {self.version}")

    size_limit: int = size_limits[self.version]

    if total_size > size_limit:
        raise RuntimeError(
            f"program exceeds size limit of {
                 size_limit // 1024}KB for version {self.version}"
        )

My tests for this actually require a change to my mock.

@pytest.fixture
def mocked_zcode_memory():
    class MockedMemory(Memory):
        def __init__(self, dynamic, static, high, version=3):
            self.dynamic = dynamic
            self.static = static
            self.high = high
            self.version = version
            self.data = bytearray(100)

    return MockedMemory

Since any tests for this method will depend on the Z-Machine version to determine the size limits, I need to add the version argument to the MockedMemory class so that I can pass different version numbers when testing. Here are some tests for that:

def test_zcode_size_version_too_large(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=50, static=100, high=200, version=3)
    memory.data = bytearray(130 * 1024)
    with pytest.raises(RuntimeError, match="program exceeds size limit of 128KB for version 3"):
        memory._zcode_size_checks()


def test_zcode_invalid_version(mocked_zcode_memory):
    memory = mocked_zcode_memory(dynamic=50, static=100, high=200, version=10)
    with pytest.raises(RuntimeError, match="Unsupported Z-Machine version"):
        memory._zcode_size_checks()

Note that this also allows me to make sure that whatever zcode binary is being read in does indicate one of the valid generations or versions of the Z-Machine that it needs to be interpreted under.

Violation of constraints is one way that an interpreter like Grue can determine if there was a problem with the zcode binary it is reading. The code I put together here is what allows me to make sure that Grue won’t try to process a zcode binary that is egregiously wrong.

If you want to follow along with the implementation of Grue as described in this post, you can do the following if you have cloned the repo:

git checkout v0.0.4

I think I’m at the point where I can start getting into the main focus of writing a Z-Machine emulator and interpreter, which involves processing the zcode binary that’s read in and reading the instructions contained within. The next post will start me down that path.