NEWS, EDITORIALS, REFERENCE
Recursion and C64 OS's Menu UI (3/3)
This is the third and final part of a series of posts discussing Pointers, Structures and Recursion in assembly on the 6502. If you haven't already read the first two parts, I recommend that you do.
Although this post is nominally about recursion in general, it is also a post about how the menu UI system in C64 OS works. This blog is about the development progress of C64 OS, I want to focus on writing about the code I'm developing and I try to keep the posts in sync with the actual development stage I'm at. It just so happens that the menu system, how to parse the data files, allocate and free memory, and convert the flat file into an in memory network of connected structs, is a big topic. And it involves the use of pointers, structs and recursion.
The menu system in C64 OS is as you would expect. It's a menu bar that sits at the top of the screen. Clicking on a top level menu entry will open up the child menu below. The child menu will have several entries. Some of those may represent actions that can be taken by the user to do something in the application. Some entries will be spacers, these are merely for visual presentation so entries can be grouped to be more easily found. And some entries are the headers that lead to another child menu.
Recursion is the process whereby a unit of code invokes itself, but with a nested set of data to work on. This invocation can then call itself again on a further nesting. There is no theoretical limit to how deeply nested the recursion can be. But in practice the code cannot keep going deeper too many times before the computer runs out of stack space. You'll see exactly why stack space is used for each level of depth as we get into the code. You should also be able to see how parsing a hierarchical menu system is a perfect candidate for recursive code. Each child menu is structured exactly the same as any other menu. So there is only one set of code that creates the linked node structure for a menu, whether that menu is at the top most level or several sub-menus deep.
What a menu should have
The goal of the menu system in C64 OS is two-fold. From the programmers point of view, I want creating the menus to be as easy and expressive as possible. When I write a new application for C64 OS, I do not want to worry about the basic framework of the UI. I just want to worry about the meat and potatoes of what the particular app is meant to do. From the user's perspective, I want the menu system to present a consistent user experience so that different apps for C64 OS feel like they belong to the same system. I also want it to be easy for the end user to be able to customize the menus. How great would it be for the user to be able to easily reorder the menu commands, or change the keyboard shortcuts, or assign shortcuts to menu actions that the original programmer didn't think would need a shortcut. Or even to remove menu entries for features that are never used.
In order to accomplish these goals, I decided that the menus should be loadable from a text file. An application will consist of multiple files. At a minimum there will be the main code file, which is an assembled object, plus one menu description text file. There may also be an icon file, and a metadata description file, etc. But those are a discussion for another post. When an application is launched by the user, C64 OS's application loader will automatically load in both the code and its associated menu description file.
Memory is at a premium. And the memory manager is simple. So, another design goal was to have the format of the text file fill two criteria: A) be human editable in a standard text editor, and B) be structured such that a minimum amount of data needs to be moved about in memory when parsing. I thought a lot about what flags and properties will be necessary in a given menu entry to make it rich enough to do what we want. And then I thought about the minimalist way those flags and properties can be represented and still remain human editable.
A menu entry must have a title, the readable text you see on screen. If the menu introduces another menu then it doesn't perform any other action besides opening the child menu. If a menu entry is an action then it should have an optional keyboard shortcut, which consists of one printable key character and a set of flags for the modifier key combination that invokes it. In other words, the keyboard shortcut must be able to be matched against a key command event, as is outlined in my the post on The Event Model.
Further, the menu entries should be only abstractly related to the code they will cause to execute. To do this, each action-based menu entry should have an action code. When the menu entry is either clicked with the mouse or triggered by the the keyboard command, its action code is sent to a standard dispatch routine in the application. If the action code is just one byte, then there could be up to 256 possible action menu entries. However, because we have to be able to read and type the action codes in the text editor, they will likely be limited to the set of upper and lower case letters, numbers, symbols, and petscii graphics for a total of around 96 actions.1 I believe that for the complexity of applications likely to ever be written for a breadbox C64, 90 to 100 selectable actions, distributed throughout a menu hierarchy, will be more than enough.
There is one other neat benefit to the menus being loadable from a user editable text description. Features of the application that are buggy, or in beta, or are just nerdy and advanced, can be left out of the menu description file. Then, information about the existence of the additional action codes could be published on the web. Daring users can then edit the menu description file, adding in new commands, and gaining access to these advanced or beta features. Really cool.
The UI of other programs
I've surveyed a number of common C64 programs, tools, utilities and applications. It is very common for them to have some sort of onscreen menu that outlines keyboard access. And occasionally, if there are lots of menu options, the list of available options will either be on a special help screen, or not listed at all except in external documentation. Let's look at a couple of these as examples.
Disk Cracker is an example of a utility that has an on screen menu which fits in the lower half of the screen while other display elements occupy the top half of the screen. Each letter in the menu is highlighted, but there are no key combinations. Every key stroke is a possible command. 15 commands in total.
Nova-Text is an example of an application, a text editor. Its menu has too many options to be displayed on screen at the same time as editing text, so it has an optional screen to show the key commands. The commands are all performed with the Control key as the modifier, or the F-keys without a modifier. 30 commands in total.
Novaterm 9.6, made by the same person who made Nova-Text, has a similar philosophy. Shows a separate screen with the menu of commands. This time the command modifier is the Commodore key. That's because the Control key is used to send control sequences to the remote machine. 28 commands in total.
D64it is a very simple utility for decoding a D64 file to a 1541 disk or CMD partition. Its menu dominates the UI, this is not uncommon for this time of utility. Like Disk Cracker, each key stroke is a potential command, no modifiers needed. 14 commands in total.
Ah the program I've become intimately familiar with. The native assembler, Turbo Macro Pro. It has no on screen menu for the most part. You have to just learn the commands by reading the documentation available on the web. Triggering the key commands is also quite odd. First you press the back-arrow key once and release. Then you press another key to trigger the command. In some rare cases the first level command will expose a tiny menu of sub-commands on the program's status line. Then you press one more corresponding letter to trigger the sub-command. This program has lots of commands. According to the docs, 83 commands in total.
And, let's not forget about GEOS. The menus in GEOS are philosophically the most modern. They are accessible with a mouse, they pull down when you need them and disappear when you click off of them. They are consistent between applications. The most common options include a keyboard shortcut. The problem with GEOS is that rendering as a bitmap is, in my opinion, unacceptably slow. Have you actually tried to use either GEOS or Wheels, without a SuperCPU? It is unusably slow. The menus in a GEOS app were hard coded, so they were not user customizable. But an app could support a lot of commands by tucking them into menus.
The problem with this mélange of user interfaces is that they are all terribly inconsistent. This mishmash of UIs and menu presentations is the furthest thing from a modern computing experience. Now, if what you want to do is decompress a D64 image, fine, use D64it. If you want to edit your disk sectors by hand, fine, use Disk Cracker. If you want to code in assembly, yes, use TMP. No one is going to reimplement most of those things for an OS. Not in the year 2017. However, what about what C64 programs we could write today? What about an FTP client? An IRC client? An Email client, a twitter client, a web browser, a podcast player, a blog editor, an RSS feed reader or a network-based chess game? The list goes on. Would I like to write these? YES! I would. But am not going to write a one-off ad hoc menu system for each and every one of these. Or I'd never bother to start because it's so much work.
The Menu system in C64 OS is meant to be a consistent way to interact with a host of modern apps, but it is also just so darned practical because I won't have to re-write all this code to get a decent Menu UI in each of these applications. Why not write for GEOS? It has a menu system. Yeah, but GEOS is too slow. The Menus have to be snappy. You have to be able to move and click and click and boom you're on your way. The C64 was not meant to have to draw its whole UI one pixel at a time. Furthermore, GEOS's rendering engine and other priorities eat into the precious memory requirements that, in this modern world, are needed for things like a persistent TCP/IP stack. Did you notice what all the theoretical applications listed above share in common? They are all internet oriented. C64 OS is about getting apps written that can take advantage of the net. GEOS is too bloated to tack on a networking layer on top of it.
That was a tangent. Now let's get back to how we can build our menus in C64 OS.
The menu definition file
The first thing to remember, the loader will load in the SEQ file using the KERNAL's LOAD routine. Therefore, the first two bytes will not be loaded. They are completely ignored but they have to be represented in the text file. The easiest way to do this is put one character on the first line and the data starts on the second line. The carriage return character is the 2nd byte skipped.
Every subsequent line is a new menu entry. No blank lines permitted, as these would just represent carriage return characters that have to be loaded into memory and leave fragmented holes in memory between the relevant data. The first X-number of characters is the menu entry's label text. The label text can vary in length. The end marker for the label text is either a colon or a semi colon. No spaces around the end marker either. This means you cannot have either a colon or semi colon in the actual label text of the menu entry. I believe this is acceptable.
The colon and semi colon also double as indicating the type of menu entry this line is. A header, that is a menu entry that opens a child menu, uses the semi colon. Following the semi colon is one byte that represents the number of entries in this entry's immediate child menu. A menu is able to have up to 24 entries. This is because the screen has 25 text rows, but the topmost row is always occupied by the root level menu bar. Because 24 exceeds the single digit numbers 0 through 9, and using 2 bytes is an unacceptable waste, instead the length is measured using the lowercase letters "a" through "x", where a means 1, b means 2... and x means 24. This byte must be the last byte on the line of a header entry.
The lines that follow a header entry are the lines that make up the entries of the child menu. If the header indicates there should be, say, 5 entries in the child menu, at a MINIMUM the next 5 lines will all be part of the child menu. However, and here's where the recursive data nesting comes in, if one of those child entries is itself a header, then that header can specify some number of its own child entries. Those children then follow that header line on the lines below it. Note though, that a header entry's child count doesn't include all the sub menu entries and sub-sub- and sub-sub-sub entries, etc. A header entry ONLY counts the number of its own immediate children. You'll see how this works in a moment in a sample file.
If following the label text of a menu entry there is a colon, rather than a semi colon, then this entry is not a header, but an action entry. Following the colon there must come exactly three bytes. Modifier key flags, key command, and action code. The modifier key flags are exactly as is stored by the KERNAL at $028d in the key scanning routines and event model.
The low 3 bits are used to represent the three modifier keys. Shift, Commodore Key, and Control. The bits can be combined together to represent combinations of modifier keys. These mirror the format of key command events produced by C64 OS's event model. 0, which represents no modifier keys, is used to indicate that this menu entry has no keyboard shortcut. In the text file description, this byte should be entered as the PETSCII value 0 through 7, not the absolute byte value 0 through 7.
The next byte is the keyboard command byte. It should be a printable character, a letter, a number, a symbol. Ideally it should be pnemonic for the what the action's label text is. As in "o" for open, "g" for go, "l" for list, etc. The pnemonics can be helped out by using combinations of modifier keys. If you have two actions, load and list, one could be C= l the other could be C= Shift l. That sort of thing. If the modifier keys byte is 0, then this key command byte is completely irrelevant. It has to be there, but it doesn't do anything.
And the final byte of the line is the action code. Even if an entry has no keyboard shortcut, it must have a unique action code. Because that's the code that will be dispatched to the program when the user clicks this menu entry with the mouse.
There is only one other type of menu entry. The spacer. To make a spacer entry, an asterisk must appear as the first and only character on its own line. Header and other action menu entries may have an asterisk in the label, as long as it is not the first character. And that is the complete file format. Here is a summary of that file format from my notes.
Now let's take a quick look at a sample menu definitions file. The next screen shot is a sample being typed up in NovaText.
As you can see, the only character of the first line is just the meaningless back arrow character. Line 2 is: "System;c". The label is "System", the semi colon means this is a header entry and "c" means this menu has a child menu containing 3 entries.
Line 3 is: "C64 Info:2ii". The colon indicates this is an action entry, and it's the first child of the header at line 2. The text label is "C64 Info". "2" is the Commodore key modifier, and "i" is the key command, for a keyboard short cut, "C= i". When this menu is triggered, it will send the action code which is that second "i".
Line 4 contains just an asterisk. This is therefore a spacer entry, and it is also the second child entry of the header at line 2. Line 5 is: "Quit to Basic:6qq". Another action, and the 3rd child of the header at line 2. The keyboard command will be "Control C= q", slightly more difficult to trigger so it doesn't get triggered by mistake. It'll send the "q" action code into the program.
Line 6 is "Utilities;d". This is a header entry, indicated by the semi colon. And, it is a root level entry, because the three children of the first header entry have been accounted for already. "d" indicates it has four children. The four lines following are an action, a spacer and two more actions. These are the four children of the header at line 6.
Line 11 is: "View;d" This is therefore the 3rd top level header entry and it has 4 children. Two actions, a spacer and an action. Their keyboard modifers are all 2 which is the Commodore key. The final two lines are two blank lines. The two blank lines in a row indicate the end of the menu definitions.
This is pretty cool. We can easily change any keyboard shortcut, remove a keyboard shortcut, or rearrange any of the menus or submenus as we please. We can also insert or remove spacers as we please to bring some grouping and clarity to the visual display. The other pretty cool thing about this file is that one could easily translate the text labels into another language. Doing so is an intentional feature. As long as the action code is kept the same and is conceptually associated with the meaning of the label text, the program itself will have no idea that the menu definitions file has been modified. Multiple language support, baby! That's cool! And it's modern.
The menu structures
Let's now look at how the menus will be structured in memory. Here is an image of my notes in a sort of C-like pseudo code.
The first question is, why have structs at all? What is the purpose of the structs? We have a text file on disk that is a tightly packed representation of all data necessary to produce the menus, draw and interact with them. We load the file into memory and we know where that memory location starts. The problem is that the individual pieces of data are at unknown offsets from the start of the file. Initially we want to draw just the header entry titles from the root level menu. Looking at our file above, the very first so many bytes are the string of the first root level menu entry. But after that, where do we go? Where is the title of the next root level menu header? If I count the bytes, it looks like it comes about 37 bytes after the end of the first title. But what about the third menu header title? It looks like it comes about 58 bytes after the end of the second title. As you can see, the problem is that in order to find the relevant data for any given thing, either rendering, or matching a key command, or whatever, we essentially have to parse the file from the beginning anew. This is incredible inefficient and way to slow.
Instead, what we want is structs that are a consistent size, that contain pointers to each other, that can very very quickly be traversed, to say count the entries in a menu, or find an entry that matches a keyboard command event, or know where the next entry to be drawn is even though other child entries are crammed physically between them in memory. What we want to do is parse the data, which is a slow and laborious process, only once. Building the network or structs and linking them together as we go. After that, all the rendering, measuring and searching will be performed by navigating the tree-like network of structs.
The main struct we'll be using is a menu entry struct. It consists of 4 pointers. A pointer to the next menu entry in this menu, aka the next sibling of this entry, a pointer to the struct which is the child of a header and the first of a set of siblings that make up a submenu. And finally, it has a pointer to the label string for the entry, and a pointer to the extra codes, the bytes that follow either the colon or semi colon in the text file. The eventual tree will end up looking something like this:
Each menu entry struct is made of four 2-byte pointers to be exactly 8 bytes total. It is very convenient and intentional that 8 bytes divides evenly 32 times into a 256 byte page of memory. This makes memory allocation—and eventually memory freeing—very straight forward. The 8-byte structs themselves will sit in memory one after the next. In the diagram above you can see that each struct is the outer square containing 4 rectangles each. The rectangles represent the four 2-byte pointers of each struct. The arrows show how each struct's pointer points to the memory address of the related struct. The root menu entries are the three down the left side. Their first pointers form a chain leading from the first to the last top level menu entry. However, each of these top level entries has their second pointer (the child ptr) point to another struct. And each of these structs has their first pointer (the sibling ptr) point to the next sibling moving rightward along those chains.
I didn't draw the pointers from the structs to the title text and to the code struct, because there was no clean way to visualize it. But you can imagine that every one of those struct's 3rd and 4th pointers point directly at the memory location of the start of the title string and the start of the codes.
Once the structs are in this arrangment, you can see how easy it will be to draw the root menu. One simply starts at the first, top leftmost, struct. Renders its title text and then follows its next sibling pointer. This leads directly to the leftmost middle struct. Then you render its title and follow its next sibling pointer to the leftmost bottom struct to render its title. And so on.
The code to parse and assemble the structs
The question is, how much code is it going to take to parse that file and allocate and build those structs? The answer is, with recursion and about 6 handy macros, a surprisingly little amount of code.
When switching between apps, quitting one and launching another, I do not want C64 OS to have to be restarted. It's common with C64 apps that when you're done you just power cycle the machine and start up a new app. In C64 OS, though, if we are going to launch a new app, we will need some way to tell the memory manager to free the memory that was allocated by the first app. This includes the ability to free all the memory that was allocated to load the menu definitions file and the memory allocated to make room for the structs. However, I'm going to show the code for doing this after going through the code showing how they are allocated and built. I think it will be easier to understand at that point. Just note that, before a new menu deinitions fill ever gets loaded, deallocating the old one is the very first step.
Let's give an overview of what has to happen first. There is the main control code that organizes the steps that have to be taken. There is the code to free the old menus. Code to parse a header entry, code to parse an action entry, and code to allocate a new struct. Plus there are 6 macros that are designed to make pointer manipulation easier. Let's look at allocating structs first. I'll just dive right in and show the code first. Then I'll talk about how it works.
There is a pointer, referenced above as ptr, which is not shown here. It's a location in zero page that points to the current struct. Whenever a new struct is needed we simply "JSR salloc", and the above routine will update ptr to point to the address a new struct, and of course manage the memory allocation along the way. Remember, a new struct is just a chunk of allocated memory sufficiently large to hold the data of the struct.
There are two variables at the bottom: Page and Offset. These together are 16-bits, enough to hold an address anywhere in memory. Memory is allocated in pages. Therefore, page is the 1-byte address of a page that has been allocated. While offset is the offset into that page where the next struct will go. The idea is that whenever offset is zero, we know we need to allocate a new page. Page and offset are initialized to zero, so the first time salloc is called, the first thing it does is allocate a new page. Then we set the pointer (ptr) to use that page as the MSB and set the LSB to offset, which begins as $00. Next, we increment offset by the size of the struct. It now points to where the next one should go, which as it happens will be further inside the page we just allocated.
It should start to become clear why it is so useful that the struct size divides evenly into a page size. I toyed with having 9-byte or even 10-byte structs, but I worked hard to get the struct size down to exactly 8 bytes. What happens is that each time you allocate space for a new struct the offset increments by 8. Until you've allocated exactly 32 structs, at which point offset rolls over to become exactly 0 again. When salloc is called to allocate a 33rd struct, seeing that offset is zero, it allocates a whole new page. Brilliant. The only other thing to mention is that after allocating a new page with JSR pgalloc, I'm also zeroing it out with a JSR memset.
Some useful Macros
Next, let's look at some of the macros that I've set up to make working with pointers reasonably sane.
Ptr is used to point at a struct, and the struct contains 4 pointers. moveptr is used to cause ptr to point at a struct that is pointed to be one of the pointers in the current struct. It does that simply by reading the lo byte of a pointer from the current struct, pushing it onto the stack, then reading the hi byte of that pointer, the updating ptr itself to that hi byte. Then pulls the lo byte off the stack and sets that on the ptr. Using this allows you to navigate through a tree of structs following their pointers from one struct to the next.
writeptr allows you to take a pointer, stored elsewhere in zero page, and write it to one of the pointer members of the current struct. This is very handy because you will see that there is a pointer that will be moved through the text file as it is parsing the file. When that text pointer happens to be at the start of a text string, boom, that pointer can be written to the current struct's titleptr.
Saveptr and fetchptr are a pair of macros that backup a zero page pointer by copying it to the stack. And then restore it by pulling a pointer off the stack and writing it back to a zero page location. This, as we will soon see, is critically important to being able to do recursion on the 6502. Since, pointers must reside in zero page to be usable by the indirect addressing mode of the various instructions.
Copyptr is used to copy the address of one pointer and store it at the address pointed to by another pointer. It'll come in handy when linking sibling structs, and linking a child to its parent.
Lastly, incptr is used to increment a pointer. In C, incrementing a pointer adds the size of the kind of pointer to the pointer value. So, for example, if you declare that the pointer is a pointer to an 8-byte struct. And then you say myPtr++, the address of myPtr will be set equal to itself plus 8. This incptr, however, just increments the address by one byte. It's used to move the text pointer through the text one character at a time.
Putting things together
Now let's put things together. The next chunk of code is complicated. It involves parsing the text file, allocating the structs, and linking them together. When it comes to parsing out the header menu entry types, it becomes possible to encounter nested data, so that's where the recursion occurs. Here we go.
Here's a good place to stop and analyze. There are three zero page pointers configured, ptr, tptr and lptr. Their locations in ZP are chosen just by what is generally unused by the KERNAL. Load is called by an earlier routine that handles setting up the filename string, and freeing the old menu. When load is called, .X and .Y point to a null terminated string containing the filename of the menu definitions file to load.
jsr loadseq is the call to C64 OS's relocatable SEQ file loader as described here. It returns the address the start page allocated for the file in .Y, and returns the number of allocated pages in .X. These are saved in defpage and defpgcnt. They are used to free memory, but we don't need to worry about them yet.
tptr is a pointer that will be walked through the loaded text file in the process of parsing the data. It is therefore initialized to the start of the first page as returned by loadseq, that's the start of the text data just loaded. lptr is used to point to the previous sibling struct, so the structs can link themselves together. It is here initialized to $0000.
The jsr parserow kicks off the process of parsing the rows. Each call to parserow will parse and configure a menu entry struct for one row of the data file. Parserow calls itself until all the data has been processed. When this first call of parserow finally returns, the entire menu will have been parsed and all structs configured.
This is another good place to stop and do an analysis. The first thing checked is if the first byte of the line is a carriage return. If it is, this indicates we've reached the end of the data file. All the preceding rows have already been parsed, and so we just return.
Otherwise, since there is data in this row, we allocate a new struct, as discussed earlier. This sets ptr to the address of the struct for this row. The title string for this menu entry begins at the start of the row, so tptr currently points at this title. Therefore, we can immediately use our writeptr macro to write the tptr to the struct at ptr, at offset titleptr. That's pretty cool.
Next, we check to see if lptr actually points to a previous sibling, or if it's null. If it's not null, we write this struct ptr to the last sibling struct at offset nextptr. You see how that works, it causes the previous sibling to point forward so its next sibling is the struct we're currently working on. This is pretty cool too!
Spacer rows are the simplest kind, and the easiest to detect. So we do that by checking if the first character of the title is an asterisk. If it is, we overwrite the asterisk with a #0 which produces an empty null terminated string. Incrementing tptr twice caues it to point to the start of the next row. Then we jump to the end of this routine to get ready to process the next node, which we'll see later.
Given that the first character was not an asterisk, we loop over the characters of the title string searching for one of two terminators, colon or semi colon. tptr is being incremented on each loop to move through the text. And depending on which terminator is found, we branch to process that kind of row either header row or action row. (And of course the branch is out of range so it needs a bit of finagling.) Now we'll look at how a header row is parsed. This is the one that needs to recurse.
There it is! That's the magic! Now let's breakdown how this works. First thing we do is null terminate the title string by replacing the semi colon with #0. Incrementing tptr causes it to point to the one byte that represents the number of entries in the child menu of this header.
Before loading the child count of this header, remember, we could already be a nested level deep, and children may already be set to the count of the children of the header that's the level above where we are. Mind twisty, but we have to back up whatever the current child count is, by pushing it to the stack. Pushing to the stack is a critical step in recursion, because it is a relative storage location. Only after backing up the current child count do we read this header row's child count into the children variable. And because the child count is stored in the text file as "a" through "x", we subtract $40 to convert the petscii a -> x to integer values 1 -> 24.
Note that tptr is pointing at the child count byte of this row. So we copy this pointer to the codeptr offset of the current struct. Now, here's an interesting thing. In the text file description we specified one byte following the semi colon before the next row. But, in order to get to a next row we have to press return. So there is an extra byte in memory where that carriage return was loaded in. If you noticed in the picture of my notes showing the structure definitions besides menuentry, there were also actioncode and headercode. These apply structure to the the series of code bytes that follow the colon/semi colon title terminator. Headercode you will also notice has two bytes. The first is where the child count was loaded and the second is where the carriage return was loaded.
However, the child count only needs to be used when parsing. It doesn't need to be conserved by the structs themselves. So headercode redefines the first byte as "width" and the second as "open". Using the newly terminated title string and the fact we're written a pointer to it into this struct, we load that pointer into .X and .Y and call C64 OS's strlen routine. This returns the length of the string in .Y. However, this is a header entry that introduces a child menu. So we want to also have an extra space and a greater than sign to indicate this entry opens a child. So we increment .Y twice to account for this, and write this to the "width" byte of our code.
Knowing the width of an entry a head of time is very useful when it comes time to render the menu. The rendering code will need to loop over the entries in a menu (maximum of 24, so it's very fast) and find the widest entry. All the others will be fitted to that maximum width, such that the title appears left aligned, and the ">" and any keyboard shortcut symbols will appear right aligned.
Then there is the "open" code byte. A header entry introduces a child menu. This child menu can either be open or closed. This byte holds its open status and is initialized to #0.
Finally, we are ready to recurse. Recursion is usually mind twisty so bear with me. We have to backup our current state to the stack. Using the saveptr macro we save lptr, child and ptr. Wait, what is child? Child is a non-zero-page pointer that points to the first struct in a series of linked struct siblings, which could be assigned to the childptr of its parent. We haven't encountered setting the child pointer yet, but we'll get there. It is initialized to zero.
Note that the tptr now points to the start of the row that is the first child entry of the header row we just finished parsing. And so we jsr alloc. This is the essential recursive step. We are already in the flow of execution that started at alloc, and yet we just jsr'd to alloc again, so the call to alloc is nested inside a call to alloc. Note that alloc is the parserow routine, it's just a few instructions further down that skips the check to see if this is the end of the data. We can safely skip that check because our header entry has just told us that there is at a minimum one child row.
The jsr to alloc simply repeats doing everything that I just described above, but it's one nested level into the data deeper. This is why we had to back up the child count. Eventually this new jsr to alloc will return to here, and when it does we must restore everything that was backed up. This is done in reverse order, because of how the data is on the stack. Push on A, B, C, pull off C, B, A. In this case we use the fetchptr macro to pull ptr, child and lptr and then manually pull the children (child count) off the stack, it is a 1-byte number not a pointer.
But notice what happens between fetching ptr and fetching child. Before fetching child, child has been set by the nested call to alloc that just returned, to be the first child of the series of structs it just finished assembling. But, we haven't actually seen the implementation of that code yet! Rest assured though, child has been set to a valid struct. Therefore, after fetching ptr, which is the pointer to this struct, we set the childptr of this struct to point to child. So, super mind twisty. Then we fetch child from the stack, but this is the child that will be passed up to the level above where we are right now.
And lastly we jmp nextnode to get read to move to the next sibling. We already saw this jump earlier when we found a row to be a menu spacer. Before we get into what happens at nextnode, let's first see what we would do if this row had been an action entry instead of a header entry.
Handling an action entry is much simpler than handling a header entry, because action's don't need to recurse. They don't have any children. As before, we terminate the title string by converting to colon (action rows are identified by the colon remember) to a #0. Increment tptr such that it points at the code bytes and write that pointer to the codeptr of this action entry struct.
As we saw before with the code bytes of a header entry, we actually get one extra byte, the byte where the carriage return was loaded in that separates the rows in the text file. The actioncode struct defines a structure for the set of action code bytes. These are defined as width, petvalue, actioncode, modkeys. Notice though that in the text file, the modkeys value is declared first. I opted to have the modkeys byte get moved to overwrite the carriage return's spot, leaving the first spot open to be used by the computed width. The reason I did this is because widths have to be looked up when rendering a menu. I wanted the offset for width to be the same between the headercode and the actioncode structs. This way, if a menu is made up of headers and actions, finding their widths does not require first determining which type we are on and adjusting the index offset back and forth.
The extra width required to render the keyboard shortcuts also varies with the number of bits represented in the modkeys bit flags. For example the int 3 is represented by two bits, which means we'll show two symbols that represent those two modifier keys. The easiest way to figure out how wide each value will be is with a simple lookup table, which is at modlens. The title string length is then measured as discussed before, it's added to the modifier keys length and written to the width offset of the action codes. The tptr is advanced to point to the start of the next row, and the action entry is done. This code will fall through directly to the "nextnode" code the others were branching to.
We have just processed a row. Ptr points to the current struct for this row. Lptr points either to $0000 (we say it's null) or to the last sibling struct. If lptr is null that means that this struct is the first entry in its menu. And that means that it will also be the struct pointed to as the child of its parent. And so here we use the macro copyptr to copy ptr to the child pointer. "child" is a pointer, but it doesn't need to be in zero-page because it is never used with any indirect addressing instructions. It is merely held until the processing of this menu is complete and the recursion returns up one level of nesting. At which point this child pointer will be copied onto that parent struct.
Next, we need to figure out how many more entries there ought to be at this level, or in other words in this menu. If children is currently zero, that's means we're already in the root menu and children isn't being used because the root menu entries are not the children of any parent header entry. In this case we move ahead to nextrow to see if there actually is a next row to parse. Otherwise, if children isn't zero, then we are in a sub-menu. Decrementing children leaves us with how many more children there are to parse in this menu. If after decrementing children it becomes zero then there are no more rows to parse at this level and the RTS will return us one level up in the recursion.
If after decrementing children it is still greater than zero, then there are more rows to parse in this menu. And we proceed to nextrow. Next row uses the macro copyptr to copy the ptr, which points to the current struct to lptr. This, as we saw before will allow the next structure to refer back to this one to link itself as this struct's next sibling. Then we jump to parserow which continues to parse the next row but doesn't recurse deeper than it is right now.
And, almost magically, this all comes together to recursively parse out and build the entire menu struct tree. It supports an unlimited depth of menu nesting. However, each time parserow calls itself with the jsr alloc, it must first backup to the stack: children, lptr, child, ptr AND the return address to here that JSR does automatically. That's 9 bytes. Each time a recursive level returns, those 9 bytes are removed from the stack. But since the stack is only 256 bytes big, it is only possible to recurse 28 levels deep. Many more than how many sub menus any app might realistically want to use.
One note on this code, I'm still working my way through debugging it. So I can't guarantee that it behaves exactly as I believe it does. But, barring a few bugs, this is pretty much how it works. Recursion is really hard to show. This is a very practical and real example where I had to use it in C64 OS.
Freeing Memory, Recursively
All of the above shows how the menu is built, recursively, and how memory is allocated to handle the creation of new structs. But I promised at the beginning that I would come back to showing how memory is deallocated, or freed. It is a much simpler process than parsing, allocating and linking the structs in the first place. But, it still requires recursion. So if you are confused by the above code, maybe this simpler example will give you another perspective on recursion.
In the routine "salloc", used for allocating a new struct, there were a couple of lines right in the middle that check to see if rootpg is null. It does this check just after allocating a new page of memory. If rootpg is null, it assigns the allocated page to rootpg. This is where the first struct is, and from it, its pointers can be recursively followed to find all the other structs.
When mnuload is first called, it checks to see if rootpg is null. If it is, then this is the first set of menus to be loaded and there are no old menus to free. Otherwise, it needs to free the old menus first. If there are old menus, then there are actually two things to free: The pages that hold the loaded menu definitions data, and the pages allocated to hold the allocated menu entry structs.
Loading defpg and defpgcnt into .A and .Y and then calling C64 OS's pgfree routine causes the memory manager to free .Y number of pages starting at the page number in .A. That part is super easy. It then loads rootpg into the hi byte of ptr, and sets the lo byte of ptr to #0. And makes the first jsr into freemenu. Freemenu will recursively call itself until everything is freed, before returning here to carry on with the load.
The very first check is if not equal to zero. Just prior to calling this, ptr's lo byte was set to zero by the accumulator. The zero flag will be set. So, what happens is that the hi byte of rootpg is loaded into .A. If it's zero, then we're done. But if it's not zero, then we have a page that needs to be freed. .Y is loaded with #1 to indicate just one page to free with the call to pgfree. Next, it checks the child pointer's hi byte to see if it's null. If the child pointer is null, there are no children structs to recurse into and it branches to process the next sibling. The next sibling is found by using the macro moveptr to move the pointer to the pointer stored in this struct's next sibling property. Then it jumps back to free menu.
But, on this second call to free menu, moveptr has just set ptr's lo byte to something other than zero. This means the pointer is not aligned with a page boundary, but rather is within an allocated page. There is nothing to free in this case. And it just proceeds to check the child pointer of this struct. Now let's imagine that this struct does have a child. We use the macro saveptr to push the current struct's address to the stack. Then we moveptr to shift the pointer to point at its child, and recurse!
Ah, but we're back to our friend that checks to see if we're in the middle of page or at a page boundary again. If this new child struct happens to be at the boundary of a page, then we free this page and follow its pointers either to its own child, or to its next sibling, or if there are neither we return. After returning from one recursive level, fetchptr is used to restore the the ptr to the struct we were at before recursing. And we move to its next sibling, or if there are none, return.
This code essentially walks the entire tree following each struct's child pointer first, and then if no child pointer, its next sibling. Until we have visited every single struct in the whole network. Along the way, if any one of those structs is found to be at the start of a page, that page is freed. And that, is all there is to it!
The end result
After all that work, let's take a look at a mockup I've made of what it might end up looking like when it all comes together.
You might think, hey that shouldn't need recursion, there is only one menu! Actually, there are two. The horizontal one at the top is just a horizontal rendering. The struct for the Edit menu entry has a next sibling that points to Go, and it has a child pointer that points to the menu entry struct for the Cut entry. Cut's next sibling is "Copy", whose next sibling is "Paste", whose next sibling is "a Spacer", whose next sibling is "Snip", whose next sibling is "Insert", whose next sibling pointer is null. Here's another mockup example that might be more exciting.
Perhaps this is more like what you were imagining. This is a three level deep menu. And it shows how the sub menu's header entry has a ">" to serve as a chevron indicating that another menu can emerge from it. In this example, the headercodes structs of the menu entry structs for both "Edit" and "To Disk" have their "open" property set to #1.
I'm still playing with the colors. I'm not sure how I'll end up actually rendering them. Maybe the colors will be user customizable. Their may be a highlight on the open menu entries, I'm not sure yet. You may also notice that the symbols used to indicate the modifier keys look unfamiliar. An asterisk, a front slash, and the Petscii up arrow. There are three modifier keys, and I want to symbolize each with just a single character. I haven't settled on these assignments with 100% certainty, but I think I'm close. The asterisk indicates the Commodore Key. It's the most common one that will be used, in my estimation. The up arrow means Control, which makes sense because the up arrow is petscii's version of ascii's carret symbol which is used in the unix world to mean Control. And the slash therefore is used to mean Shift. There isn't enough room on the screen to display the full word "Shift", and I don't even like the idea of using "C=" for the Commodore key. Using "C" alone feels very strange. So, using three single character symbols seems to be the least bad. At least all of the apps in C64 OS will share the same three symbols for those keys. I don't think it'll be to hard to get used to.
Summary
I love recursion. I've written recursive code in C, Objective-C, Javascript, PHP, I've even received huge applause, many years ago, from my fellow co-workers when I wrote recursive ColdFusion custom tags. But this is the first time I've ever written recursive code in 6502 asm. And I'm quite pleased without clean it turned out. Macros are, in my opinion, essential. If the internal implementation of a macro had to be exposed every time you wanted to copy a pointer or shove a pointer onto the stack, the code would quickly become so messy it would be very difficult to follow. It also probably be very error prone.
This has been a pretty long post. But it was a pretty big topic. If you are still confused about how this code is supposed to work, feel free to leave a comment in the comments section. And if I've got a bug, please point it out to me, the fix may make it into C64 OS's source code!
UPDATE: March 9, 2017
I switched the large blocks of assembly code from being just inside pre tags, to being hosted by gist.github.com. It automatically syntax highlights. It doesn't do a perfect job with 6502, but it's adequate and better than none at all. If you have a problem seeing the code, let me know in the comments. I'll probably start using Gist for all my future code snippet hosting.
- See this list of Petscii codes. I'm counting from 32 to 127. These can easily be typed in a standard text editor like NovaText, and have a distinct visual appearance. [↩]
Do you like what you see?
You've just read one of my high-quality, long-form, weblog posts, for free! First, thank you for your interest, it makes producing this content feel worthwhile. I love to hear your input and feedback in the forums below. And I do my best to answer every question.
I'm creating C64 OS and documenting my progress along the way, to give something to you and contribute to the Commodore community. Please consider purchasing one of the items I am currently offering or making a small donation, to help me continue to bring you updates, in-depth technical discussions and programming reference. Your generous support is greatly appreciated.
Greg Naçu — C64OS.com
