Understanding the lua stack (pt. 4): Tables.

Obligatory links to pt. 1, pt. 2, and pt. 3.

The way lua tables exist on the stack can be confusing.  I looked and looked for documentation explaining exactly what is going on inside the stack with respect to a table, but I couldn’t find what I was looking for, so what I’m sharing is a product solely of my own research.

What is a lua table?

Tables in lua are really nothing more than associative arrays.  That’s a pretty easy concept to understand, so I’m not going to dwell on it much.  That said, the way a table exists on the stack I found to be kind of strange.  First, go ahead and put this piece of code into your C program.
(Using the code tag in WordPress sucks.  It never works, so I’m going to use pastebin instead).

So what did we just do?

Here’s what happens in the code linked above.  We create a new table on the stack using lua_newtable (at index -1 if you have nothing else on the stack).  We then iterate from 1 to 5, adding a key-value pair to the stack for each iteration.

First off, notice that we’re doing lua_pushnumber twice.  The first number we push is the key, the second number is the value.  For now, those are just values on the stack, they have not been added to the table.  The order is very important when we get to the next line though.

So again, the values are on the stack but they’re not part of a table.  When we call lua_rawset, it pops those values from the stack and puts the key-value pairs into the table.  The index parameter set in the lua_rawset function is the index of the table.  Remember how it was -1 when we first created it?  Well now it’s -3, because we’ve added 2 elements on top of it.  Once we execute lua_rawset though, those values are popped from the stack, and the table once again moves up to the position of -1.  The values aren’t gone though, they’ve now become part of the table.

If you’ve run this code, you’ll most likely have noticed one glaring issue.  Running stackTrace after you’ve populated your table shows “table” as the sole item on the stack.  Where the hell is all of our important data?!

Tables occupying the stack, and where the data actually is.

At the beginning of this series I made an analogy to a stack of papers.  To understand how tables work on the stack, let’s extend that analogy a bit.  Imagine that each piece of paper in our stack has something written on it.  So far, every single piece of paper in our stack only ever has ONE thing written on it.  One piece of paper might have a number, another piece might have a single word, but each piece only contains one piece of information each.  Now imagine that we create a spreadsheet with several pieces of information on it, and we print it out on a single sheet of paper and place it on the stack.  As far as we’re concerned, it’s still just one piece of paper, and therefore one item in our stack of papers, but the contents of that one piece of paper is much different than the other pieces.

When we’re viewing a list of items in the stack (here’s the code for that if you haven’t followed the other entries) what we’re going to see is nothing more than the word “table”.  We’re not going to actually see all of the contents of said table.  As far as the raw stack is concerned, “table” is just another piece of paper sitting with all the others.  The thing is, seeing “table” isn’t very useful to us.  We’re using a table because we want the data inside it, so we have to be able to access that data somehow.

So how do we use the data in our table?

We use the data inside of a given table by iterating through the table and copying individual values from the table onto the stack.  Imagine taking that piece of paper with the spreadsheet on it and transcribing the values from each row onto individual sheets of paper, one sheet per value.

Understanding all of that, let’s create a quick example to demonstrate what is actually happening when we access the table.  Add the following code after you’ve created your table, but before the c = getchar();

The most widely accepted way to access the data inside of a table is by using lua_next.  Lua_next iterates through a table and copies a key / value pair from the table onto the stack, which is pretty easy to understand.  It does some other funky stuff though, which requires a bit more abstract thought.

The first thing lua_next does is remove a key from the stack.  It does this before it does anything else.  The problem is, the first time it iterates, it hasn’t yet populated the stack with a key, so it can’t pop one.  Therefore, to use lua_next without error, you must “prime” the stack first by adding a value to the stack right before you call lua_next.  This way, the value you’ve added will be treated as the first key (we’ll call it the zero key) and it will be discarded.

Once it’s discarded a key, it then pulls the next available key / value pair from the table and copies the value, and then the key.  Here’s a look at what exactly happens, it’s a bit tricky.

After we’ve created a table, the stack looks like this:
-1 —-  table

Once we’ve primed the stack it looks like this:
-1 —-  nil (or whatever our primer value is)
-2 —- table

Once we call lua_next, the primed value is discarded and is replaced with the key value pair:
-1 —- “hi there” (value)
-2 —- 1 (key)
-3 —- table

In the above stack, the top element is the value, but lua_next expects the key to be the top value when it performs it’s next iteration, so before we call lua_next again, we have to remove the top element (the value part of the key value pair).  Lua_pop(1), will remove the top value, and our stack will look like this:
-1  —-  1 (key)
-2  —-  table

Lua_next will continue to iterate, and again the first thing it will do is pop the key in element -1 and replace it with a new key / value pair.

Using the values.

In the key / value pair, the value is what we’re really after.  The key is essentially an index (it can be more than that, but that’s a discussion for another day).  Every time we iterate through our table, we’re actively removing the value from the stack though, and that seems counter-intuitive.  Really, it’s not though.  We as the programmers control when that value is removed from the stack or if it’s even removed at all.    We essentially have three options for using the value:  (A) We can populate a C variable with the value and now it’s not tied to the lua stack at all.  (B) Instead of popping it from the stack we can simply move it to another location on the stack, out of the way of our lua_next iterations.  (C) We can decide that we don’t need the value at all, and just pop it.

Putting it all together.

At this point we can create a table, populate it with some data, and then iterate through that table to retrieve the data that we need.  I found the concept of lua tables to be quite tricky to wrap my mind around, but once I really got into the meat and potatoes of the concepts, it proved to be pretty straight-forward.  Hopefully this helps anyone who might be struggling with the same conceptual issues I was.

Understanding the lua stack (pt. 3): Manipulating the stack

Recap

First, here is pt. 1 and pt. 2.  If you used Google to find this post, those links might prove useful to you.  To catch you up quickly though; I’ve demonstrated how the stack works and how to view the contents of it.  Our next example will build on the code we generated in the previous posts.

Ways to manipulate the stack.

Manipulating the stack is actually (somewhat) more straightforward than it might initially seem.  First, understand this…  As far as I can tell, you can only add or remove from the stack, which means that those are the only two actions that will ever actually happen regarding the stack.  Some stack functions might make it seem like other things are going on, but once you understand them, you realize that that they’re just adding and removing.

Adding.

Here, you’ll find the different methods by which you can add elements to the lua stack.  They all follow the same naming structure though; “lua_push” followed by some data type.  You supply the lua_state, and the value you’d like to put on the stack.  That’s really all there is to it.  Values are entered onto the stack based on the order you add them, with the most recent entry being on the top of the stack.

Removing.

Unlike the simplicity of adding to the stack, removing is a bit more convoluted.  I may take some time and separately address the two very different ways of removing items from the lua stack, but for now, let’s simply understand what the two ways are:

lua_pop:  This function removes a specified number of elements from the stack, starting at the top.  If you have 5 elements in the stack, and you want to use lua_pop to remove 3 of them, it’s automatically going to remove the 3 most recent additions.

lua_remove:  This function removes one element from the stack, at a specified index.  The indices are represented negatively in this case, so you’ll need to make sure that you’re using a negative index.  When you remove an element from the stack, it shifts accordingly.  If you had a stack of 5 papers, and you removed the 3rd one, papers 4 and 5 would now be 3 and 4, but papers 1 and 2 would maintain their positions.

Changing the stack.

I’ll now explain how to modify the stack, although to be clear, you’re not really modifying the stack.  Rather, you are simultaneously adding and removing elements.  Here’s the function, with a quick explanation.

lua_replace:  This function takes the top element in the stack and moves it to the position of a specified index, also removing the previous entry there.  As a quick example, let’s say that you had a stack with 4 elements in it, and you wanted to replace the 3rd element with a different value.  You’d first have to push the value you wanted onto the stack, thus making it the top most element, and then you’d have to use lua_replace to move the element you just pushed to the appropriate index.

So, what is lua_pushvalue?

Lua_pushvalue is essentially nothing more than a copy function.  You specify to lua_pushvalue the index of the element that you would like to copy, and it copies it, placing a second copy at the top of the stack.  A quick example:  You have 3 elements in your stack, and the last element is “Bob”.  If you do a lua_pushvalue on that last index, you’ll now have a stack with 4 elements, and the last AND first element will be “Bob”.  Obviously though, these are different elements, different places in memory, etc… so removing or replacing one of them has no affect on the other.

Conclusion.

So, that’s about it for today.  Next time I’m going to get into a more advanced topic, tables.

 

Dev C++ vs. Visual Studio, and my experience switching.

So I’ve used Visual Studio 2010 Express for a while now, and it’s a fine dev environment, but I wanted to branch out a bit, and try using something that at least felt less Microsoft oriented.  Also, the project size of Dev C++ projects are miniscule compared to what VS2010 creates.  So this blog will be pretty short, and honestly, there is only one real tip I’d like to share, because it’s the only one that I think is really relevant to the learning that I’m personally doing.

Linking Libraries.

The main dev environment of Dev C++ isn’t much different from Visual Studio, other than Visual Studio looks a lot more polished (but who really gives a shit, honestly).  The main difference seems to be in how you link a library that you’re going to use in your code.  To be clear, what I mean by linking a library is this:

Let’s say you want to use sqlite (a very easy to implement library).  You have sqlite.h and sqlite.lib.  To include the .h file, you just to an #include and you’re fine, but to include the .lib you have to do a bit more fancy footwork.  In Visual Studio, you go to the project properties, and add the folder that your .lib file is in to the Library Folders section.  In Dev C++ it’s slightly different, and it took me a while to find the right place.

In Dev C++, in order to link that .lib file, you have to open project options, and go to the Parameters tab.  There, under the section called Linker, you’ll have a button to add a folder.  That’s where you need to add the folder containing your .lib file.

I only mention this because there are a few other places where you could potentially try and add those folders.  Don’t worry about any of those spots for the purpose of linking a .lib file.  The only place it has to be linked is in the spot described above.  That’s all there is to it!  Now, you can easily switch between dev environments if you’d like, and there is one less stupid, non-programming thing you have to worry about.

Understanding the lua stack (pt. 2): Viewing the stack

Preface

In pt. 1 I explained a bit about the inner workings of the stack.  Now, let’s take a look at the actual stack, from inside a program (ooooooooh!).

(NOTE: I’m using lua version 5.2.2 which has some syntactical differences from its predecessors.  Please be aware of that if you’re going to cut and paste code from here.)

Let’s create a lua_State

Here is the most basic version of creating a lua state.

#include <stdio.h>

extern "C"
{
#include <lua.h>
#include <lauxlib.h>
#include <lualib.h>
}

#pragma comment(lib, "lua.lib")

int main()
{
lua_State *L;
L = luaL_newstate();

return 0;
}

So, now we have an active lua_State. Obviously our program doesn’t really do anything, but we’ve got all we need to run a few small experiments.

A simple way to view the stack.

Here, you’ll find a function called stackDump.  I’ve taken that function and changed it a bit, to represent the stack in a way that makes a bit more sense to me personally.  First, I iterate through the stack in the reverse order from the original function.  To me, having the most recent addition on the top makes more sense as the stack is LIFO.  Secondly, I’ve added a bit of code that keeps track of the negative representation as well as the positive one.  I discussed this briefly in my last post, but I’ll talk more about the importance of that later.  Last, I renamed it from stackDump to stackTrace.  I don’t know why really, I just liked it better.

Here is my code:


void stackTrace(lua_State *L)
{
int i;
int top = lua_gettop(L);
printf("---- Begin Stack ----\n");
printf("Stack size: %i\n\n", top);
for (i = top; i >= 1; i--)
{
int t = lua_type(L, i);
switch (t)
{
case LUA_TSTRING:
printf("%i -- (%i) ---- `%s'", i, i - (top + 1), lua_tostring(L, i));
break;

case LUA_TBOOLEAN:
printf("%i -- (%i) ---- %s", i, i - (top + 1), lua_toboolean(L, i) ? "true" : "false");
break;

case LUA_TNUMBER:
printf("%i -- (%i) ---- %g", i, i - (top + 1), lua_tonumber(L, i));
break;

default:
printf("%i -- (%i) ---- %s", i, i - (top + 1), lua_typename(L, t));
break;
}
printf("\n");
}
printf("---- End Stack ----\n");
printf("\n");
}


So now we have a function to visually display what is in the stack.  Let’s discuss for a second.  The first interesting thing that we do is use lua_gettop to find the stack element with the largest positive representation (the most recent addition).  If there are 5 elements in the stack, lua_gettop will return a value of 5.  Once we have the stack size, we now iterate through the stack using i, but we do so in the reverse order.  We’ll start at 5 and go down from there, rather than starting at 1 and going up.

Remember how I mentioned in the last blog that the lua stack doesn’t really care what type of value you put in it?  While it is true that it doesn’t care what type of data you put in it, it still remembers what type of data you put in it.  In our loop, we check to see what data type each element is, and then we call the proper lua_to function on it.  Each lua_to function converts the data to a C++ data type.

Let’s see what it does.

Insert these lines into the main function, after you create the lua_State, but before return 0.


stackTrace(L);

char c;
c = getchar();


Your result should be a stack with 0 elements in it (since we haven’t done anything to the stack yet).  We know that stackTrace is indeed working though, so let’s actually add something to the stack.

Under your first stackTrace call, add these lines:


lua_pushnumber(L, 17);
lua_pushstring(L, "hi there");
lua_pushnil(L);
lua_pushboolean(L, 1);

stackTrace(L);


What we have now is 2 stackTrace calls.  The first one shows us the empty stack, the second shows us a stack populated with 4 elements.  The 4 lines we added above the second stackTrace call are functions to “push” different data types onto the stack.  As you look at the output of the program compared to your code, notice that the very first item in the output is the value “true”.  This represents the boolean value pushed from lua_pushboolean(L,1), which is the last thing we pushed to the stack.  So again, the last thing we put onto the stack (the most recent thing) goes on top.

Nice.  What next?

As of now we can view the stack, which is incredibly useful for debugging.  Keep in mind that obviously you don’t have to print this to the screen.  You could potentially call stackTrace every single time you manipulate the stack and put the results into a log file.  From there, it would be relatively easy to retrace your steps through the stack, if certain pieces of data are not interchanging between the programming language and lua.

Next time, I’ll go more into manipulating the stack, including removing, replacing, and inserting.  For now you can clearly see how to push data onto the stack, which is obviously integral for utilizing lua in any practical manner.

Understanding the Lua stack (pt. 1): The basics.

Preface:

I’ve been doing a lot of work to understand the best way to use the lua scripting language in my game, so I’m going to share my findings regarding the usage of the lua stack.  Keep in mind that these are MY findings, so if something here is incorrect, I apologize.  If it’s brought to my attention via comments, I’ll be happy to edit this blog.

What exactly is the lua stack?

Some quick facts about the stack:

• The lua stack is the primary way (the only way, as far as I know) to move data between a lua script and programming code.
• The stack is LIFO.
• Pairs in the stack cannot be directly modified.  Instead, they must be removed and replaced.
• Pairs in the stack are data-type indifferent.  The first pair might contain a string value, while pairs 2-5 might contain integers.
• The stack is script and function independent.  Once a lua state is created, the stack can be accessed.  The stack does not require a script file to be loaded or a function to be used in order to be accessed.

What is the lua stack for?

Primarily, the lua stack is used to exchange data between a programming language and a lua script.  When you call function from a lua script and it has a return value, that value is placed in the stack.  When you call a function from a lua script that requires input values, those input values are pushed to the stack before the function is called.  The stack acts as the primary interchange between the programming language and lua.

The lua stack order annoys me.

For some reason which I have yet to comprehend, some lua stack functions treat the stack order as positive numbers, and some treat the stack order as negative numbers. Here is a quick example of how the stack is represented both ways:

Positive Representation	Negative Representation	Value
1	-4	“hi there”
2	-3	17
3	-2	true
4	-1	“foobar”

If you wanted to manipulate the member of the stack with the value “foobar”, some functions will require you to reference it as 4, while others will require you to reference it as -1. In the documentation it mentions that both negative and positive representation feel natural, depending on the function’s context. Maybe that’s true for some, but to me, this is the most confusing part of understanding the stack. Perhaps someone in the comments can make sense of this for me, but until then, I have simply taken to understanding that elements in the stack are represented both ways. When in doubt, this page uses examples to illustrate which stack operations represent the stack order in negative terms, and which use positive terms (I’ll also do so in this blog).

Why is understanding the stack important?

As the stack is the primary method of data interchange between the programming language and lua, it seems like the easiest point of failure in your lua implementation.  Using the stack is made more complicated by the twin positive-negative representation of it’s order, so understanding the stack’s purpose and usage goes a long way to being able to quickly debug any issues you have with it.

What’s next?

Hopefully the purpose and implementation of the stack is a bit clearer now, although if you’re like me, you want to see some actual code.  In the next part of this series, I’ll post some code that shows the contents of the stack on screen, pushes some values onto the stack, removes some values from the stack, and moves values around on the stack.