tag:blogger.com,1999:blog-32649409276344085172024-03-18T04:03:22.403+01:00Kristofer Karlsson's development blogTopics include: Java, Lua, general development thoughts, my projectsKristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.comBlogger27125tag:blogger.com,1999:blog-3264940927634408517.post-21822146163318795102011-01-27T10:57:00.008+01:002011-01-27T14:15:29.475+01:00Movement in MMORPG gamesTypical for MMORPG games is that there are a lot of players running around, and they usually want to interact with each other in some way - to the very least extent they want to see that other people are there.<br /><br />This can of course be a potential problem, due to the massive amount of data that needs to be sent over the internet. The amount of character data to send grows quadratically with the number of players in crowded locations.<br /><br />There are some tricks you can use to at the very least reduce the constant factor in order to increase the number of players supported.<br /><br />First, it is important to note that not all online games have the same requirements when it comes to character movement:<br /><ul><li>In first-player shooters, it is important that all other players are always displayed in the correct locations, in order to be able to aim and fire accurately. This is not true for most MMORPG games.</li><li>MMORPG:s need to handle hundreds of players in the same location, first-player shooters tend to support much fewer.</li><li>Smooth movement and high fidelity of small movements is important in MMORPGs for the social interactions to feel more natural, whereas in first-player shooters it's much more important to fast forward movements to always be up to date - it's also preferable to do dead reckoning in order to account for latency.</li></ul>This leads me to the conclusion that we should design the movement system to be more like a VCR (if anyone still remembers those). Clients record their movements and sends compiled packages to other players for playback. This makes it easy to support smooth movement. It also makes it easier to compress the data sent. The tradeoff is course slightly more cpu and memory usage for reduced network traffic.<br /><br />Here come some of the tricks we currently use for <a href="http://www.fearlessgames.se/">Spaced</a>.<br /><br /><span style="font-weight: bold;">Path compaction</span><br /><br />Path compaction is the first step in reducing network traffic.<br />Basically we compact movement paths to a straight line if the distance from the start to the end is close enough to the sum of the distance of each path segment. This can easily be done in constant time for each added path segment, so it's a simple choice.<br /><br /><span style="font-weight: bold;">Same state</span><br /><br />Send a bitfield with one bit for each type of movement data (position, rotation, animation state). Then simply don't send the actual data if it hasn't changed since last frame. This by itself reduces our network usage to about 40 bytes per second and character, with sending frames at least ten times per second, when the character is idling.<br /><br /><span style="font-weight: bold;">Compressed positions</span><br /><br />Position vectors are stored clientside with very high precision (64 bits per component), which is useful for local calculations, but is probably a bit silly for sending it over the network, so we just convert it to floats instead.<br /><br /><span style="font-weight: bold;">Compressed rotations</span><br /><br />Character rotations (the facing) are represented as quaternions, with four double components in the range [-1, 1].<br />Since we don't really need that high resolution for the rotation for movement playback, we simply encode each component as a signed byte, with -127 mapping to -1 and 127 mapping to 1.<br /><br /><span style="font-weight: bold;">Movement deltas</span><br /><br />I think this the most interesting trick of the ones described.<br />Instead of sending the position each frame, we can just send the delta compared to previous frame!<br /><br />With a naive encoding, this will be as expensive to send as the actual position, but we can take advantage of the fact that most movements will be very small vectors.<br /><br />Start with size = ceil(log_2(max(x, y, z)))<br />size will hopefulle be an int in the range [-128, 127] because then we can store it in a byte (otherwise we'll just revert to sending a full position instead)<br /><br />Now we know that x / 2^size must be in the range [-1, 1] which is great, since we can store it in a byte with some (a lot!) lost precision.<br /><br />Calculate the actual bytes to send as x_send = x * 127 / 2^size (and the same for y and z)<br /><br />By sending size along with these three bytes, we can send a compressed vector in just four bytes. It can be decompressed as: (x * 2^size / 127, y * 2^size / 127, z * 2^size / 127).<br /><br /><span style="font-weight: bold;">But wait a second...</span><br /><br />You're probably thinking that this won't work, because you lose to much data when you compress it, and when you add up all those delta vectors, you'll get more and more value drift!<br /><br />That's true, but the solution is quite simple.<br />Instead of calculating the deltas as Delta(n) = compress(P(n) - P(n - 1)), we calculate it as Delta(n) = compress(P(n) - Q(n-1)), where Q(n) is defined as Q(n-1) + Delta(n).<br />This means that all the drift errors that we generate at P(n) will be accounted for when we generate P(n+1). The total drift error at P(n) will thus never be greater than 1/127 of the size of the movement at P(n).<br /><br />This has been stress tested by a scenario test which measures the actual drift for millions of updates, and it never increases more than 0.1.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com11tag:blogger.com,1999:blog-3264940927634408517.post-60110694973805610662011-01-19T16:20:00.006+01:002011-01-19T16:41:38.818+01:00Subversion and feature branchesI've used subversion for a long time (probably around five or six years), but it's only recently I've started to use feature branches actively.<br /><br />Mostly it was because it was a huge pain to do. You used to have to manually track revisions for all merges for it to work at all. Fortunately that was greatly improved with subversion 1.6, but it was still quite possible to mess it up.<br /><br />Usual symptoms were crazy conflicts when merging from files not even touched in the branch.<br /><br />These days, I happily use feature branches, because I finally figured out how to manage them properly. I can't remember exactly who I got this from, it was quite possibly several different people independently from each other.<br /><br />Basic rules to avoid pain:<br /><ul><li>Always stand in the project root (/trunk/ or /branches/branch/) when doing subversion operations.</li><li>Update often.</li><li>Commit often.</li><li>Sync trunk -> branch often.</li><li>Merge branch -> trunk only once, and then delete it.<br /></li></ul>Here are the general operations I use nowadays.<br /><br />To create a branch: <pre class="brush: bash">svn copy TRUNK_URL BRANCH_URL</pre><br />Start using the branch: <pre class="brush: bash">svn switch BRANCH_URL</pre><br />List existing branches: <pre class="brush: bash">svn list BASE_URL/branches</pre><br />Sync trunk to branch: <pre class="brush: bash">svn up<br />svn merge TRUNK_URL .<br />svn commit -m "Merged trunk to branch BRANCH"</pre><br />Reintegrate branch (make sure it's commited and synced recently):<pre class="brush: bash">svn switch TRUNK_URL<br />svn merge --reintegrate BRANCH_URL .<br />svn commit -m "Reintegrated BRANCH"<br />svn delete -m "Deleting reintegrated BRANCH" BRANCH_URL</pre><br />It doesn't look so hard, right?<br />The trick is that if you do something else at some point, like cherry picking revisions into the branch, subversion tends to get confused. I am not sure if it's subversions fault or the users fault, but in either case, cleaning it up usually gets messy.<br /><br />An annoying thing is all those URL:s you need to enter.<br />To simplify things for my most common usage, I wrote a simple bash script:<br /><br />It mostly just ensures that I don't forget any steps, does some basic error checking, and most importantly, it lets me skip writing the full URL all the time.<br /><br />Here's what it looks like:<br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgy0WutJBVvgQkyc-MUikOR6hOqUGKRv5vjuFNoSpEWNYGZUO0f1QKIghnsMU-AMluJXgL9oXDtZvyUWHjZSrEuH9w7Z4Dx9lXZV0FLhqALYcFIQxzdcJTvkX4nwI774HZ1xWWEzzXo7wSP/s1600/scriptscreenshot.png"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer; width: 400px; height: 185px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgy0WutJBVvgQkyc-MUikOR6hOqUGKRv5vjuFNoSpEWNYGZUO0f1QKIghnsMU-AMluJXgL9oXDtZvyUWHjZSrEuH9w7Z4Dx9lXZV0FLhqALYcFIQxzdcJTvkX4nwI774HZ1xWWEzzXo7wSP/s400/scriptscreenshot.png" alt="" id="BLOGGER_PHOTO_ID_5563922585257578898" border="0" /></a><br />And here is the actual script if anyone is interested.<br /><pre class="brush: bash">#!/bin/bash<br /><br />ERROR='\033[1;31m'<br />REPO='\033[1;32m'<br />CBRANCH='\033[1;33m'<br />COMMAND='\033[1;34m'<br />EXECUTE='\033[1;35m'<br />ENDCOL='\033[0m'<br /><br />FULLURL=`svn info | grep -E "^URL: "| cut -d " " -f 2`<br />if [ "$FULLURL" == "" ]; then exit 1; fi<br />TRUNKURL=$(echo $FULLURL | grep -E -o "^.*/trunk")<br />BRANCHURL=$(echo $FULLURL | grep -E -o "^.*/branches/[^/]+")<br /><br />set -e<br /><br />function error() {<br />echo -e "${ERROR}$1${ENDCOL}"<br />exit 1<br />}<br /><br />function execute() {<br />echo -e "> ${EXECUTE}$@${ENDCOL}"<br />$@<br />}<br /><br />if [ "$TRUNKURL" != "" ]; then<br />if [ "$FULLURL" != "$TRUNKURL" ]; then<br /> error "Please stand in the project root.\n Expected $TRUNKURL\n but was $FULLURL"<br />fi<br />BRANCH="trunk"<br />BASEURL=$(echo $TRUNKURL | sed "s/\\/trunk//")<br />elif [ "$BRANCHURL" != "" ]; then<br />if [ "$FULLURL" != "$BRANCHURL" ]; then<br /> error "Please stand in the project root.\n Expected $BRANCHURL\n but was $FULLURL"<br />fi<br />BRANCH=$(echo $FULLURL | grep -E -o "[^/]+$")<br />BASEURL=$(echo $BRANCHURL | sed "s/\\/branches\\/$BRANCH//")<br />else<br />error "Could not determine trunk or branch from $FULLURL"<br />fi<br /><br />function sync() {<br />if [ "$BRANCH" == "trunk" ]; then error "Must be on a branch to sync or reintegrate!"; fi<br />CLEAN=`svn status|grep -v "^\\?"`<br />if [ "$CLEAN" != "" ]; then error "Working copy is not clean. Revert or commit first!"; fi<br /><br />execute svn up<br />execute svn merge $BASEURL/trunk .<br /><br />UPDATED_FILES=`svn status|grep -E -v "^\\?"|cut -b 9-`<br />if [ "$UPDATED_FILES" == "" ]; then<br /> echo "Nothing changed, skipping sync."<br />elif [ "$UPDATED_FILES" == "." ]; then<br /> echo "Only trivial changes merge - reverting merge"<br /> execute svn revert -R .<br />else<br /> execute svn commit -m "Merged trunk to branch $BRANCH"<br />fi<br /><br />}<br /><br />case $1 in<br />switch)<br />if [ "$2" == "" ]; then error "Missing parameter to switch: branch"; fi<br />execute svn switch $BASEURL/branches/$2<br />;;<br />trunk)<br />execute svn switch $BASEURL/trunk/<br />;;<br />list)<br />echo -e "> ${EXECUTE}svn list $BASEURL/branches${ENDCOL}"<br />echo "Available branches:"<br />BRANCHES=`svn list $BASEURL/branches | grep -E -o "^[a-zA-Z]*"`<br />for b in $BRANCHES; do<br /> echo -e " ${CBRANCH}$b${ENDCOL}"<br />done<br />;;<br />reintegrate|reint)<br />sync<br />execute svn switch $BASEURL/trunk<br />execute svn merge --reintegrate $BASEURL/branches/$BRANCH .<br />execute svn commit -m "Reintegrated $BRANCH"<br />execute svn delete -m "Deleting reintegrated $BRANCH" $BASEURL/branches/$BRANCH<br />;;<br />sync)<br />sync<br />;;<br />create)<br />if [ "$2" == "" ]; then error "Missing parameter to create: branch"; fi<br />execute svn copy $BASEURL/trunk $BASEURL/branches/$2 -m "Creating branch $2 from trunk"<br />execute svn switch $BASEURL/branches/$2<br />;;<br />delete)<br />if [ "$2" == "" ]; then error "Missing argument to delete: branch"; fi<br />if [ "$BRANCH" == "$2" ]; then error "Can not delete active branch. Switch first!"; fi<br />execute svn delete -m "Deleting branch $2" $BASEURL/branches/$2<br />;;<br />*)<br />echo -e "Repository: ${REPO}$BASEURL${ENDCOL}"<br />echo -e "Active branch: ${CBRANCH}$BRANCH${ENDCOL}"<br />echo "Usage: ./branch <command> [option]"<br />echo "Commands:"<br />echo -e " ${COMMAND}switch${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- switches to the branch"<br />echo -e " ${COMMAND}trunk${ENDCOL} -- switches to trunk"<br />echo -e " ${COMMAND}list${ENDCOL} -- list available branches"<br />echo -e " ${COMMAND}reintegrate${ENDCOL} or ${COMMAND}reint${ENDCOL} -- reintegrate active branch to trunk"<br />echo -e " ${COMMAND}sync${ENDCOL} -- syncs current branch with trunk"<br />echo -e " ${COMMAND}create${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- creates a new branch from trunk and switches to it"<br />echo -e " ${COMMAND}delete${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- deletes a branch without reintegrating it"<br />;;<br />esac<br /><br /></pre>Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com4tag:blogger.com,1999:blog-3264940927634408517.post-34061038194045377252010-11-11T11:52:00.005+01:002010-11-11T12:26:09.487+01:00Deep thoughts about deep mocksA deep mock is a mock that has methods that also return mocks. In theory, you could follow a chain of mocks for as long as you wanted.<br /><br />Deep mocks are supported by both Mockachino and Mockito, with the exception that a method from a mock can't return a mock if the return type is primitive or final.<br /><br />Another problem with deep mocks was previously generics.<br />The following would fail in both Mockachino and Mockito:<br /><pre class="brush: java">static interface ListSet extends List<Set> {}<br />@Test<br />public void testDeepMockWithClass() {<br /> ListSet mock = mock(ListSet.class, RETURNS_DEEP_STUBS);<br /> Set mock2 = mock.get(0);<br />}</pre><br />This would fail on the last line, because the mocking frameworks wouldn't understand that the return type of get(int) should be Set instead of Object.<br /><br />This has been fixed in Mockachino 0.5.0 (with a fairly small patch, I'm happy to say!) but it is still broken in Mockito 1.8.5.<br /><br />Now, this particular example takes advantage of the fact that the class we're dealing with has no open generic types. The type is fully bound.<br /><br />It would be much harder to support something like this:<br /><pre class="brush: java">@Test<br />public void testDeepMockWithClass() {<br /> List<Set> mock = mock(List<Set>.class, RETURNS_DEEP_STUBS);<br /> Set mock2 = mock.get(0);<br />}</pre><br /><br />This is in fact not even legal Java syntax. It's also not valid Java semantics, since the runtime doesn't maintain type information except for some special cases.<br />So we simplify it into this, which is valid Java syntax:<br /><pre class="brush: java">@Test<br />public void testDeepMockWithClass() {<br /> List<Set> mock = mock(List.class, RETURNS_DEEP_STUBS);<br /> Set mock2 = mock.get(0);<br />}</pre><br />Unfortunately, at the time of the call to mock, we only know about List.class, not that it should have Set as its generic type parameter, so it would be impossible to deduce which type it should create at mock.get(0).<br /><br />This has two possible solutions. Either create a specific sub interface/class, like we did with ListSet. The other solution is to use the TypeLiteral concept, found in Google Guice:<br /><pre class="brush: java">@Test<br />public void testDeepMockWithClass() { <br /> List<Set> mock = mock(<br /> new TypeLiteral<List<Set>>() {},<br /> fallback(DEEP_MOCK));<br /> Set mock2 = mock.get(0);<br />}</pre><br /><br />Since we're actually creating a new anonymous class here, Java manages to retain the type information. It's unfortunately a bit verbose, but it should still come in handy in the few times you'd need to use deep mocks with generics.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1tag:blogger.com,1999:blog-3264940927634408517.post-18033201462734015622010-08-20T10:38:00.013+02:002010-09-26T21:54:49.065+02:00Random numbers without repetitionThe origin of this problem comes from picking <span style="font-style: italic;">K</span> elements from a collection of elements of size <span style="font-style: italic;">N</span> (<span style="font-style: italic;">N</span> >= <span style="font-style: italic;">K</span>, obviously). If <span style="font-style: italic;">K</span> = <span style="font-style: italic;">N</span>, this is the same thing as shuffling, which can be done using the excellent Fisher-Yates algorithm in <span style="font-style: italic;">O(N)</span>. This algorithm can be used when <span style="font-style: italic;">K</span> is smaller than <span style="font-style: italic;">N</span> as well, you just have to disregard <span style="font-style: italic;">N - K</span> of the elements. However, if <span style="font-style: italic;">K</span> is very small and <span style="font-style: italic;">N</span> is very large, this algorithm is quite far from optimal.<br /><br />Another approach is to simply pick elements randomly from the collection and keep track of which elements have already been picked. If you hit the same element again, you simply pick another one. This would work if the entropy source was good enough to ensure that would always pick numbers in a range with equal probability, to avoid getting stuck picking numbers already used. If <span style="font-style: italic;">K</span> is much smaller than <span style="font-style: italic;">N</span>, this would work well, but if <span style="font-style: italic;">K</span> was very close to <span style="font-style: italic;">N</span>, you could probably end up doing far too many retries to be reasonable as soon as you start filling up the result.<br /><br />Instead, you could use the original Fisher-Yates strike-out approach and simply stop after <span style="font-style: italic;">K</span> elements. This could be done in <span style="font-style: italic;">O(K*(log(K) + K))</span>, which can be simplified to <span style="font-style: italic;">O(K^2)</span> with a naive implementation:<br /><pre class="brush:java"><br />public <T> List<T> take(List<T> source, int k) {<br />int n = source.size();<br />if (k > n) {<br />throw new IllegalStateException(<br />"Can not take " + k +<br />" elements from a list with " +<br />n + " elements");<br />}<br />List<T> result = new ArrayList<T>(k);<br />SortedSet<Integer> offsets = new TreeSet<Integer>();<br /><br />for (int i = 0; i < k; i++) { // O(K)<br />int off = random.nextInt(n - i);<br /><br />for (int offset : offsets) { // O(K)<br />if (off >= offset) {<br />off++;<br />} else {<br />break;<br />}<br />}<br />offsets.add(off); // O(log(K))<br />result.add(source.get(off));<br />}<br />return result;<br />}<br /></pre><br /><br />if <span style="font-style: italic;">K >= O(sqrt(N))</span>, then the plain shuffle is better, but when <span style="font-style: italic;">K</span> is smaller than <span style="font-style: italic;">sqrt(N)</span>, this approach would be the winner.<br /><br />I wonder if it's possible to do it faster than <span style="font-style: italic;">O(K^2)</span>. One idea is to use some sort of binary search to quicker find the actual offset without having to iterate the list of offsets. This would make the algorithm <span style="font-style: italic;">O(K*log(K))</span> instead which would be much better.<br /><br />I experimented a bit by repeatedly running a binary search of the offset until the offset can not be incremented further. If <span style="font-style: italic;">N</span> is large and <span style="font-style: italic;">K</span> is small, this would often stop after the first iteration since it's sparse between findings, but you can still easily construct worst case scenarios which would need to iterate <span style="font-style: italic;">O(K)</span> times.<br /><br />Does anyone know any good articles / papers / blogs about algorithms for picking <span style="font-style: italic;">K</span> distinct random numbers in the range <span style="font-style: italic;">1..N</span>?<br /><br /><span style="font-weight: bold;">Update:</span><br /><br />After having eaten lunch, I figured out how to make it run in <span style="font-style: italic;">O(K)</span>:<br /><pre class="brush:java"><br />public <T> List<T> take(List<T> source, int k) {<br />int n = source.size();<br />if (k > n) {<br />throw new IllegalStateException(<br />"Can not take " + k +<br />" elements from a list with " + n +<br />" elements");<br />}<br />List<T> result = new ArrayList<T>(k);<br />Map<Integer,Integer> used = new HashMap<Integer,Integer>();<br />int metric = 0;<br />for (int i = 0; i < k; i++) {<br />int off = random.nextInt(n - i);<br />while (true) {<br />metric++;<br />Integer redirect = used.put(off, n - i - 1);<br />if (redirect == null) {<br /> break;<br />}<br />off = redirect;<br />}<br />result.add(source.get(off));<br />}<br />assert metric <= 2*k;<br />return result;<br />}<br /></pre>The idea here is to instead of recalculating off to the actual position, as in Fisher-Yates, just assume that the random index is correct. Then, use the map to check if the index has already been used, and if so, use another guaranteed free index instead.<br /><br />The while loop make look bad, but it never runs more than <span style="font-style: italic;">2*K</span> times in total.<br />(I haven't proven this formally, I just ran a lot of benchmarks on random input.)<br /><br />If I were to prove it though, my general strategy would be that the loop is entered exactly <span style="font-style: italic;">K</span> times, and you will follow at most <span style="font-style: italic;">K</span> links, since only <span style="font-style: italic;">K</span> links will be constructed and no link is followed more than once.<br /><br /><span style="font-weight: bold;">Update 2:</span><br />Apparently Robert Floyd already invented this algorithm (well, it's very similar at least) (published in Communications of the ACM, September 1987, Volume 30, Number 9).<br /><pre class="brush:java">public <T> List<T> take(List<T> source, int k) {<br /> int n = source.size();<br /> List<T> result = new ArrayList<T>(k);<br /> Set<Integer> used = new HashSet<Integer>();<br /> for (int i = n - k; i < n; i++) {<br /> int off = random.nextInt(i + 1);<br /> if (!used.add(off)) {<br /> off = i;<br /> used.add(off);<br /> }<br /> result.add(source.get(off));<br /> }<br /> return result;<br />}<br /></pre>The only problem with this is that the ordering of result is not random, only which elements have been chosen. This is easily fixed by running Collections.shuffle(result, random) though.<br /><br />I see two significant differences with this approach.<br /><br />The first (which is of the least relevance) is the amount of entropy used.<br />If we assume that calling random.nextInt(n) consumes log_2(n) bits of entropy then my algorithm uses: log_2(n) + log_2(n-1) + log_2(n-2) + ... + log_2(n - k + 1) = log_2(n! / (n - k)!) = log_2(n!) - log_2((n - k)!) bits of entropy.<br /><br />Robery Floyd with an additional plain shuffle uses:<br />log_2(n!) - log_2((n - k)!) + log_2(k!) bits of entropy which may be significant if k is large compared to n, and if entropy is expensive where the algorithm is used.<br /><br />The second difference is much more important. The Robert Floyd-algorithm can't be run interactively, picking one or more numbers at a time. You need to know the value of k (or an upper bound of k) before requesting a random number, since the first number chosen by the algorithm will be in the range [0, n - k).<br />My algorithm on the other hand can be run partially and resumed without knowing the value of k at all.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-43535166098921920372010-08-06T21:46:00.004+02:002010-08-06T22:05:23.576+02:00Python annoyances - generatorsAnother annoyance in Python is generators. Since Python 2.5, the generator concept was extended to include coroutine support. (See <a href="http://www.python.org/dev/peps/pep-0342/">http://www.python.org/dev/peps/pep-0342/</a> )<br />I for one think it's an odd design of coroutines.<br /><span style="font-style: italic;">Note that this comes from someone who is used to (and spoiled by) Lua's coroutines</span>.<br /><br />I have two problems with coroutines/generators in Python:<br /><br />First of all, "def" gets multiple meanings. It's not just a function definition anymore.<br />It could also be a generator definition! And the only way to notice this is to<br />scan the entire function definition for a yield statement.<br /><br />I would not have a problem with this if it wasn't for the case that generator<br />definitions and function definitions behave completely differently.<br /><pre class="brush:python">def gen():<br /> return 123</pre>I can call this with gen() and get 123 back. Simple!<br /><pre class="brush:python">def gen():<br /> yield 123</pre>If I call gen() now, I don't get 123 back, I get a generator object.<br />So I have to do this instead:<br /><pre class="brush:python">g = gen()<br />value = g()</pre>That by itself isn't much trickier, but it's hard to know by just looking at the code if it's a generator. It's completely invisible at the call site, and at the definition it could be anywhere in the function. This is probably why most generators I've seen in Python have been fairly short and simple (which is a good thing for function design over all anyway).<br /><br />Let's compare it to Lua, which was the language that introduced me to coroutines:<br /><pre class="brush:lua">-- Simple function call<br />function gen()<br /> return 123<br />end<br />value = gen()<br /><br />-- Using a generator / coroutine<br />function gen()<br /> coroutine.yield(123)<br />end<br />c = coroutine.wrap(gen)<br />value = c()</pre>Here it's quite clear at the call site that we're dealing with a coroutine. And if we were to call gen as a regular function, we'd get a runtime error unless we were actually running in a coroutine already.<br /><br />That gets us into the second annoyance. Python only supports yield in the generator definition. If you were to build a more complex generator, you'd have to write it as one long function instead of splitting it up into many small functions.<br /><br />As it happens, I have a good example to use. The following is actual code I have for a hobby project. It's an AI implemented with Lua coroutines. To keep it small, not all functions have been defined, but I've kept everything that deals with coroutines.<br /><pre class="brush:lua">function resume(entity)<br /> if not entity.coroutine then<br /> entity.coroutine = coroutine.create(function()<br /> return entity:runAI()<br /> end)<br /> end<br /> coroutine.resume(entity.coroutine)<br />end<br /><br />function Entity:moveTowards(x, y)<br /> local dx = sign(x - self.x)<br /> local dy = sign(y - self.y)<br /> local dir = getDirection(dx, dy)<br /> if dir ~= -1 then<br /> TryMove(self.entity, dir)<br /> coroutine.yield()<br /> end<br />end<br /><br />function Entity:moveTo(x, y)<br /> while self.x ~= x or self.y ~= y do<br /> self:moveTowards(x, y)<br /> end<br />end<br /><br />function Entity:attack(dx, dy)<br /> local dir = getDirection(dx, dy)<br /> if dir ~= -1 then<br /> TryAttack(self.entity, dir)<br /> coroutine.yield()<br /> end<br />end<br /><br />function Entity:chasePlayer()<br /> while true do<br /> local distance = self:distanceToPlayer()<br /> if distance > 8 then<br /> break<br /> end<br /> if distance <= 2 then<br /> local dx = px - self.x<br /> local dy = py - self.y<br /> self:attack(dx, dy)<br /> else<br /> self:moveTowards(px, py)<br /> end<br /> end<br />end<br /><br />function Entity:patrolTo(x, y)<br /> while self.x ~= x or self.y ~= y do<br /> local distance = self:distanceToPlayer()<br /> if distance <= 5 then<br /> self:chasePlayer()<br /> else<br /> self:moveTowards(x, y)<br /> end<br /> end<br />end<br /><br />-- Populate world with deadly enemies<br />local entity = Entity:new(20, 10)<br />function entity:runAI()<br /> while true do<br /> self:moveTo(20, 8)<br /> self:moveTo(20, 12)<br /> end<br />end<br />addEntity(entity)<br /><br />local entity = Entity:new(15, 15)<br />function entity:runAI()<br /> while true do<br /> self:patrolTo(15, 15)<br /> self:patrolTo(15, 10)<br /> self:patrolTo(10, 10)<br /> self:patrolTo(10, 15)<br /> end<br />end<br />addEntity(entity)<br /></pre><br />As you can see, each entity type can be written by using very high level<br />constructs, which themselves are defined by simple logic and calls to lower level<br />functions. This lets you write an AI as if it was running in its own thread,<br />but in reality, the game engine only calls the resume-function for each entity<br />on its main thread.<br /><br />Without coroutines, you'd have to resort to writing a state machine instead,<br />which can be more painful to write and maintain.<br /><br />Now, I've tried converting this to Python to see what it would look like.<br />This was my first iteration, which won't run because the generators itself<br />don't contain the actual yield-call.<br /><pre class="brush:python">def resume(entity):<br /> if entity.coroutine == None:<br /> entity.coroutine = entity.runAI()<br /> return entity.coroutine()<br /><br />class Entity:<br /> def __init__(self, x, y):<br /> self.x = x<br /> self.y = y<br /><br /> def moveTowards(self, x, y):<br /> dx = sign(x - self.x)<br /> dy = sign(y - self.y)<br /> dir = getDirection(dx, dy)<br /> if dir != -1:<br /> TryMove(self.entity, dir)<br /> yield<br /><br /> def moveTo(self, x, y):<br /> while self.x != x or self.y != y:<br /> self.moveTowards(x, y)<br /><br /> def attack(self, dx, dy):<br /> dir = getDirection(dx, dy)<br /> if dir != -1:<br /> TryAttack(self.entity, dir)<br /> yield<br /><br /> def chasePlayer(self):<br /> while True:<br /> distance = self.distanceToPlayer()<br /> if distance > 8:<br /> break<br /> if distance <= 2:<br /> dx = px - self.x<br /> dy = py - self.y<br /> self.attack(dx, dy)<br /> else:<br /> self.moveTowards(px, py)<br /><br /> def patrolTo(self, x, y):<br /> while self.x != x or self.y != y:<br /> distance = self.distanceToPlayer()<br /> if distance <= 5:<br /> self.chasePlayer()<br /> else:<br /> self.moveTowards(x, y)<br /><br /># Populate world with deadly enemies<br />class Runner(Entity):<br /> def runAi(self):<br /> while True:<br /> self.moveTo(20, 8)<br /> self.moveTo(20, 12)<br />entity = Runner(20, 10)<br />addEntity(entity)<br /><br />class Patroller(Entity):<br /> def runAi(self):<br /> while True:<br /> self.patrolTo(15, 15)<br /> self.patrolTo(15, 10)<br /> self.patrolTo(10, 10)<br /> self.patrolTo(10, 15)<br /><br />entity = Patroller(15, 15)<br />addEntity(entity)</pre>Now, let's try refactoring until all yields are in the actual generator.<br />To do this, we could either simply inline all the functions that would yield,<br />until they're all in the runAi-method. The problem with this is a lot of<br />duplicated code, so that's not a good option.<br /><br />Another way would be to only have the yields in the runAi, and let the currently<br />yielding functions return some value instead. The problem with that is that we<br />lose the knowledge of where to resume from, and thus we have to build some sort<br />of state maching to remember it, which would remove the point of having<br />coroutines in the first place.<br /><br />If anyone can see a good way of refactoring that Python code (I am fairly new<br />to Python after all) to work as a coroutine, please let me know!<br /><br />Until then, I'll just assume that python coroutines are inferior to Lua's. ;-)<br /><br />[Here's an interesting article about coroutines: <a href="http://www.inf.puc-rio.br/%7Eroberto/docs/MCC15-04.pdf">http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf</a> ]Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com49tag:blogger.com,1999:blog-3264940927634408517.post-70458672687335138822010-08-06T10:34:00.008+02:002010-08-06T23:11:00.705+02:00Python annoyance - scopingI recently tried writing a small program in Python, and I have to give it credit here - it was pretty easy to get started, using the online language reference and standard library reference for help.<br /><br />One thing I stumbled over was a subtlety in the scoping that I didn't expect. Here's an example:<br /><pre class="brush:python">foo = 123<br />def fun():<br /> print(foo)<br />fun()<br />print(foo)<br /></pre>This prints 123 and 123, as you would expect. This implies that function blocks can access variables in outer blocks. Let's try another example:<br /><pre class="brush:python">foo = 123<br />def fun():<br /> foo = 456<br /> print(foo)<br />fun()<br />print(foo)<br /></pre>This prints 456 and 123. This means that assignment of a variable in a function doesn't assign the outer variable. Instead it creates a new variable local to the function block. Let's look at the final example:<br /><pre class="brush:python">foo = 123<br />def fun():<br /> print(foo)<br /> foo = 456<br /> print(foo)<br />fun()<br />print(foo)<br /></pre>I can think of two reasonable ways to interpret this:<br /><ol><li>First print 123 (from the outer block), then 456 (creating a new variable in the function block), then 123 (outer block variable unchanged)</li><li>First print 123 (from the outer block), then 456 (modifying the outer variable), then 456.</li></ol>Instead, Python throws an error:<br /><pre>UnboundLocalError: local variable 'foo' referenced before assignment<br /></pre>This means that Python actually inspects the entire function and searches for assignment operations. If it finds any, it creates a new local variable. If it doesn't, it refers to the outer.<br /><br />You can override this behaviour by doing this:<br /><pre class="brush:python">foo = 123<br />def fun():<br /> global foo<br /> print(foo)<br /> foo = 456<br /> print(foo)<br />fun()<br />print(foo)<br /></pre>This forces python to only refer to the outer variable instead of creating a new. This outputs 123, 456, 456.<br /><br />The annoyance is that Pythons automatic choice between "read outer" and "create new local" comes from inspecting the entire function, which means that an assignment at the end of the function can create an error at the first line of the function, which can be very confusing for a beginner.<br /><br />I think a better solution would have been to always have outer by default, except for in loops and function parameter definitions. You could then add the keyword "local, my, var or val" for when you really want to create a new local variable (like lua, perl, javascript, scala et.c. does).Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-83903194013359823162010-06-18T21:23:00.001+02:002010-08-06T11:15:27.246+02:00Symmetric getters and settersUsing getters and setters is a very common pattern for classes in Java projects. In general, I think they should be avoided, especially since setters eliminates the possibility of having final fields. Also, blindly adding getters to your classes is a bad idea since you expose implementation details to the outside world. Of course, some times you do no need them, and the rest of this post assumes that you do.<br /><br />Sometimes you want to do some preprocessing on the inputs to the setters, to support cases where the input is out of range or other things of that nature. For instance, your domain objects may have a requirement that the values of the field should be in a specific range. You can then either:<br /><ul><li>Throw an illegal argument exception - if the ranges are clearly defined and the caller should know them, this is a valid approach.</li><li>Silently clamp the input value to be inside the range. This can sometimes be the desired approach, but it ultimately depends on the system.</li><li>Accept the value as it is, and just hope that the callers behave nicely. This is usually not a good idea, and should only be done if you control all the callers and its in a cpu critical section of the code.<br /></li></ul>There is a symmetry law which I think should hold for pairs of getters and setters.<br />Note that is a completely personal opinion. I don't expect everyone to agree with it. It's a good thing this blog is also completely personal!<br /><br />Anyway, here is the law:<br />Values provided from a getter should be legal values when calling the setter, and if you run the following code, then x and y should be equal:<br /><pre class="brush: java"><br />x = obj.getFoo();<br />obj.setFoo(x);<br />y = obj.getFoo();<br />assert x.equals(y);<br /></pre><br /><br />For simple getters and setters that just uses a single field, this obviously always holds, even if the setters throws exceptions on bad values, or clamps the values out of range. This probably one of the reasons that many people assume that this symmetry usually holds.<br /><br />However, sometimes the getters and setters don't really correspond to a specific field, but instead triggers other code to be modified. In this case, it's not clear that the symmetry holds.<br /><br />for instance, you may have something like this:<br /><pre class="brush: java"><br />public class Foo {<br />private final Bar bar;<br />public void setValue(int value) {<br /> bar.setValue(value);<br />}<br /><br />public int getValue() {<br /> return offset + bar.getValue();<br />}<br />}<br /></pre><br />This is clearly asymmetric, so how do you fix it?<br />You could try something like this, but it's very prone to error, depending on how bar.setValue is implemented:<br /><pre class="brush: java"><br />public void setBar(int value) {<br /> bar.setValue(value - offset);<br />}<br /></pre><br /><br />A better option is to remove the setter entirely and expose the bar object directly. I don't think anyone would take for granted that foo.getBar().setValue(...) needs to be symmetric with foo.getValue()<br /><br />Yet another variant is simply renaming setValue to setBarValue (or setBaseValue or setDelegateValue, or something else, depending on the context) - this simple transformation also makes it clear that it's not symmetric.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-61776694205952091812010-06-18T14:58:00.003+02:002010-06-18T21:10:00.909+02:00Kahlua on AndroidYes, that's right, Kahlua supports Android (or Android supports Kahlua, depending on how you see it). And it worked surprisingly easy. All in all, I spent two hours installing the Android SDK, reading the Android documentation and creating an example program that used Kahlua. I even managed to create a very simple interpreter. And it didn't just load the Kahlua core, it also supports the J2SE extensions. It was almost out of the box, and I'll expand on that later.<br /><br />This was a great success, and I attribute it to the following reasons:<br /><ul><li>The Android SDK is really polished. It was easy to install, easy to get started, and the documentation was pretty good!</li><li>Kahlua (core and J2SE) is compatible with the same subset of Java 5 that Android supports.<br /></li></ul>As far as I can tell, the classes in Android are fully compatible with Suns Java classes; at least I haven't found any bugs in Kahlua on Android yet.<br /><br />The only problem I had was that I got a NoSuchMethodError when invoking Arrays.copyOfRange. It turns out that this method was introduced in Java 6, which explains why Android didn't support it. I simply converted the code into using the old and trusted System.arrayCopy and the code worked!<br /><br />The Android interpreter even supported the reflection- and annotation-based exposing of Java methods, which I demonstrated by exposing a method that called Thread.sleep. (This was also useful for testing that the UI components in Android worked correctly while executing a script.)<br /><br />The Android Kahlua interpreter is checked in to the git repository for Kahlua2, if anyone is interested in seeing it. It is basically a single Java file in 148 lines of code.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com26tag:blogger.com,1999:blog-3264940927634408517.post-34319601356473577412010-06-06T10:49:00.004+02:002010-06-06T11:28:04.550+02:00Automated tests for contentGames are generally considered to consist of code and content.<br /><ul><li>The code is the game engine that defines all the rules of the game, input handling, network, graphics rendering, and so on.</li><li>Content in a game includes a lot of things: textures, sounds, level designs, ai, animations, meshes, dialogues and more.</li></ul>Another (less formal) way of looking at it is that code is the part of the game produced by the programmers, and content is the part of the game produced by artists, game designers or level designers.<br /><br />Programmers are used to writing tests for their code (if they're using TDD, they're even writing some, if not all, tests before they write the code), but content creators generally are not. They instead rely on manual testing, both by themselves and by gameplay testers.<br /><br /><span style="font-weight: bold;">Why is code tested and not content?<br /></span>I think the code is what makes the game robust, coherent and logical. It's easy to detect broken code - broken code either crashes or behaves incorrectly. This makes it feasable to write tests for the code.<br /><br />Content on the other hand is harder to verify automatically. How can a machine decide that a texture is broken? We could certainly verify that the texture has the correct dimensions and correct color depth, and other properties needed for the game engine to support it. We should have tests to verify the integrity of the content to as large extent as possible, and I think we do.<br /><br />The things we can't verify automatically is the fun and the user experience.<br /><br /><span style="font-weight: bold;">The corner case</span><br />This was just the setup. Now for one of the corner cases, the parts that can be considered both code and content: AI!<br /><br />AI is definitely a part of the content. Meeting unique non-player characters (NPC) with custom AI adds a new user experience that is something unknown, and therefore possibly exciting. The AI however is also expressed in some sort of code, either as a script in some embedded language, as a behaviour tree or behaviour stack.<br /><br />The problem with AI as code, is that it tends to mutate at a much faster pace than game engine code. AI is driven by the content around it, not technical demands, and so it must change often.<br /><br />Writing tests for each individual AI is expensive, since fully testing all the possible code paths can require a lot of manual setup, and verifying correctness is also tricky for a suffiently complex AI. What's worse, the test is bound to be very fragile, since content makers like to tweak and redo AIs if it's too easy, too difficult or simply not fun enough.<br /><br />Should content like this be covered by automated tests? To some extent, definitely! I am not convinced that content should be tested individually, but testing the content by type is quite useful to detect errors.<br /><br />For AIs this could mean:<br /><ul><li>Running automated smoke tests that run the AI characters for a long time (game time, not real time) to increase the chance of running many code paths (possibly with the AI opponent doing random moves) and simply checking that it doesn't crash. This type of test could apply to most if not all AI. It would be cheap to implement, and probably be fairly stable.</li><li>Smoke testing the AI with measurements of key values, such as damage output, movement speed, actions per minute, et.c. and check that the values are in a sane range. If some of the values are zero, this would indicate that the AI is blocked somewhere and one of the code paths is never run, and extremely high values would indicate that the AI is stuck in one of the code path loops.</li></ul><span style="font-weight: bold;">Conclusion</span><br />You should always consider the cost versus the gain of writing tests. For game engine code, the gain is almost always greater than the cost, but for content it's not as clear.<br />You should also consider how to test something. A small unit test is suitable for many parts of code development, but it's probably overkill for content (which tends to change a lot).<br />If you can write one or a few tests that can verify something about a specific content type, and apply the test to all the content, the gain will quickly become large, since you can scale up the size of the content without scaling up the number of tests.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-6276035013302253342010-06-04T20:01:00.003+02:002010-06-04T21:14:25.175+02:00More details of the exposerAs I said before, there is more to the exposer than I wrote before.<br /><br />Lua is, as you already know, a language that supports multiple return values. Java however does not, and that makes integration slightly less straightforward.<br /><br />It is not obvious how to do it, but it is possible to expose Java methods and have them return multiple values.<br /><br /><span style="font-weight: bold;">Exposing multiple return values</span><br />The workaround is to create your java method like this:<br /><pre class="brush: java">@LuaMethod<br />public void getUnitLocation(ReturnValues rv, String unitName) {<br /> Unit unit = service.getUnit(unitName);<br /> rv.push(unit.getX());<br /> rv.push(unit.getY());<br />}<br /></pre>You can then use the function like this:<br /><pre class="brush: lua">local x, y = getUnitLocation("theUnit")<br /></pre>This looks a lot like how it's done using a raw JavaFunction, you might exclaim! This is not by coincidence. In fact, ReturnValues is just a thin layer on top of the original LuaCallFrame.<br /><br />In order for this to work, the exposer mechanism performs special handling if the first parameter of the method is of the type ReturnValues.<br /><br /><span style="font-weight: bold;">Varargs</span><br />If the java method is a vararg method, i.e. defined like this:<br /><pre class="brush: java">public String concat(String... strings) {<br />return Arrays.toString(strings);<br />}<br /></pre>then Lua scripts can call it with concat("a", "b", "c") and get "[a, b, c]" back. This may seem obvious and it should be, but I'll mention it anyway.<br /><br /><span style="font-weight: bold;">Error handling</span><br />What if you do something wrong, such as calling getUnitLocation(), thus not passing in the name? The exposer will detect an incorrect number of arguments and throw an error message at you.<br /><br />This however, is ok: getUnitLocation("theName", "something else"). The exposer will simply disregard the extra parameter. You may expect it to similarly throw an error, but this is in fact in line with how Lua generally handles too many arguments.<br /><br />If you supply the incorrect type, you'll also get an error (unless the type can be converted to the Java type of course). If you supply nil, it'll go through into the method - so you have to add the null checks yourself.<br /><br /><span style="font-weight: bold;">Method overloading</span><br />I mentioned method overloading earlier, and that the exposer can handle it to some extent. I'll clarify that here.<br /><br />Assume you have the following class:<br /><pre class="brush: java">public class Example {<br /> public void myMethod() {<br /> }<br /> public void myMethod(Object a, Object b, Object c) {<br /> }<br /> public void myMethod(String a, String b) {<br /> }<br /> public void myMethod(int a, int b) {<br /> }<br />}<br /></pre>If all these methods are exposed, the exposer will detect that it's already been exposed, and will convert the generated JavaFunction to a dispatching JavaFunction.<br />This dispatcher will inspect the arguments passed in the call to try to determine which method to call. The actual algorithm for selecting is very naive, but most likely good enough for almost all cases. In any case, you shouldn't use overloading too much - that's bound to confuse your users.<br /><br />The dispatcher first sorts the list of matching methods by decreasing parameter count. Varargs count as zero. In our case, this means the following ordering:<br /><pre class="brush: java">public void myMethod(Object a, Object b, Object c);<br />public void myMethod(String a, String b);<br />public void myMethod(int a, int b);<br />public void myMethod();<br /></pre>The middle two have the same number of parameters, and thus can occur in any order.<br />When getting a call, it simply goes through the list in order and tries to call it. If it can't be called, it simply tries the next.<br />A call like myMethod("a", "b") will fail the first method, since it doesn't have enough arguments, but it will match the second.<br />myMethod("a", 123) won't match 1, 2 or 3, but it could be reduced to the 4th.<br />myMethod(nil, nil, nil) will match the first (since nil matches all types).<br /><br /><span style="font-weight: bold;">Methods and functions</span><br />What is a method? What is a function?<br /><br />I'd like to define method as a function that's associated with an object. In Java, all instance methods falls under that definition of method. Static methods in Java can be considered functions, since they are not associated with specific objects.<br /><br />Real methods don't really exist in Lua - all functions are plain functions. However, you can simulate methods easily. There is a simple syntactic sugar in Lua for this:<br /><br />Sugar for a method definition:<br /><pre class="brush: lua">function obj:method(args...)<br />end<br /></pre>is equivalent to:<br /><pre class="brush: lua">function obj.method(self, args...)<br />end<br /></pre>That means that in the first case, it simply injects a new local variabel "self" assigned to the first argument.<br /><br />Similarly, there is sugar for a method call:<br /><pre class="brush: lua">obj:method(args...)<br /></pre>is equivalent to:<br /><pre class="brush: lua">obj.method(obj, args...)<br /></pre>which of course is a regular function call.<br /><br />This also how the exposer differentiates between methods and functions. If it's annoted with @LuaMethod(global = true) or is static, it's a function, and arguments are passed straight through from Lua to Java.<br /><br />If global = false (which is the default), the first argument is consumed by the exposer and used to find the actual object to invoke the method on, and it's not passed along to the method.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-72631182197404510832010-06-03T22:23:00.002+02:002010-06-03T22:28:35.304+02:00Differences between Kahlua2 and Lua 5.1There are some noticable differences between Lua 5.1 and Kahlua2, and it may be good to know what they are.<br /><br /><span style="font-weight: bold;">Tables</span><br />Tables in Kahlua2 are implemented using a backing Hashtable or ConcurrentHashMap and as a result, implementing "next" properly would be inefficient and instead of implementing "next", it was removed. The function "pairs" still works, so use that instead. One common idiom using next in Lua 5.1 was checking if a table is empty:<br /><pre class="brush: lua">function isempty(t) return next(t) == nil end</pre><br /><br />An alternative implementation of that in Kahlua2 would be:<br /><pre class="brush: lua">function isempty(t) return pairs(t)() == nil end</pre><br />but it would be inefficient, since it would create an iterator for each call to isempty.<br /><br />Instead, you can use the method table.isempty(t) in Kahlua2.<br /><br />Another side effect of using Java maps to implement tables, is that key equality is slightly different between Lua 5.1 and Kahlua2. In Lua 5.1, keys are equal in a table if they refer to the same object while in Kahlua2 they are equal if their hashcodes are equal and their equals()-methods return true. For strings, it works just as in Lua 5.1, but for numbers it's slightly different. Java treats -0 and +0 as different keys while Lua treats them as the same.<br /><br /><span style="font-weight: bold;">tostring</span><br />When converting things to strings in Kahlua2 (for example when calling tostring(obj)), it will not just return "userdata" if it doesn't have a better guess, it will instead use the toString() method for the object.<br /><br /><span style="font-weight: bold;">Weak tables</span><br />Kahlua2 doesn't support the __mode = "[k][v]" metatable magic to create weak tables. If you need weak tables, consider exposing a new method for creating a KahluaTable backed by a WeakHashMap or something similar.<br /><br />Kahlua2 doesn't support the __gc feature for metatables, since there is no good way in Java to get notified when an object is about to get garbage collected. If you need this functionality, consider putting the object in a SoftReference to manually check when it's collected.<br /><br /><span style="font-weight: bold;">Libraries</span><br />Kahlua2 does not include any io or debug library. Some parts of the debug library may be added in the future, but the io library is better left added as a custom extension if necessary. The same thing goes for the os library, which is only partially implemented.<br /><br /><span style="font-weight: bold;">xpcall</span><br />Kahlua2 doesn't implement xpcall yet, but it might come in the future.<br /><br /><span style="font-weight: bold;">random and randomseed</span><br />random and randomseed in Lua uses a mutable global state, which is undesirable in Kahlua2.<br />Instead, use the following:<br /><pre class="brush: lua">local myrandom = newrandom()<br />myrandom:random() -- real number in the range 0 to 1<br />myrandom:random(max) -- integer number in the range 1 to max<br />myrandom:random(min, max) -- integer number in the range min to max<br />myrandom:seed(obj) -- seeds the random instance with the hashcode of the object.</pre>Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-36777601316932459422010-06-02T20:47:00.003+02:002010-06-02T21:23:00.096+02:00Kahlua - the J2SE goodiesIn this post, Lua will generally refer to the language specification, whereas Kahlua will refer to this actual implementation so don't be confused when I talk about Lua scripts running under Kahlua.<br /><br /><span style="font-weight: bold;">The goodies</span><br />Kahlua has a couple of useful extensions that makes your life as a developer easier when integrating Kahlua into your applications. Some of them depend on each other, so I'll go through them in dependency order to make the reading more digestible.<br /><br /><span style="font-weight: bold;">Converting objects</span><br />Since Lua only has a few built in types (String, Double, Boolean, KahluaTable) and Java has many many more types, it's sometimes useful to automatically convert types when going back and forth between Lua and Java.<br /><br />For instance, if Java were to send an Integer object to Kahlua, that object would just be an opaque reference, without any operations. If we instead convert it to a Double, Kahlua can work with it without any problems. This is the rationale for introducing the first J2SE goodie - the KahluaConverterManager.<br /><br />This is a class that can help you convert types back and forth between Lua and Kahlua. By itself, it can't convert anything at all, but you can register actual converters with it. For convenience, a couple of generic converters are bundled with Kahlua and you can also write custom converters if you need to.<br /><br />The converter manager has two conversion methods: fromLuaToJava and fromJavaToLua.<br />Converting from Lua to Java takes an object and a Java class.<br />The converter manager then uses the type of the object and the Java class to determine which converter best matches the conversion. If nothing matches it returns null instead.<br /><br />Converting from Java to Lua is different - it doesn't have a target type, since Lua is dynamically typed. Instead the converter just looks at the Java type to choose converter. If no suitable converter is found, it returns the object as it is.<br /><br />Here are the already existing converters:<br /><br /><span style="font-weight: bold;">The number converter</span><br />Registering the number converter allows you to automatically convert Lua numbers (which are implemented as Double) to the numeric types in Java (int, long, char, byte, short, float, double).<br /><br />It also works the other way around, converting the numeric types in Java to Double.<br /><br /><span style="font-weight: bold;">The table converter</span><br />This one also converts both ways. KahluaTable instances can be converted both to List and Map, and Lists and Maps can be converted back to KahluaTable. It also converts maps recursively, so be careful to avoid converting cyclic structures.<br /><br /><span style="font-weight: bold;">The enum converter</span><br />You can also convert enums to their string representations (enum.name()) and back, which means that you can<br />call Java methods that takes an enum just by passing in a string that matches one of the enums.<br /><br /><span style="font-weight: bold;">Calling Lua from Java</span><br />LuaCaller.protectedCall is a utility method that simplifies the usage of thread.pcall. Instead of returning a raw array where the first return value always is true or false, it returns an abstraction that hides the details: the LuaReturn class.<br /><br />LuaReturn has the methods isSuccess(), getErrorMessage(), getStacktrace(), getJavaException() which makes it easier to use than extracting result[0] (and 1, 2, 3, respectively).<br /><br />LuaCaller.protectedCall additionally applies the installed converters to the inputs before the call. It doesn't apply it to the return values, because it doesn't know which types it wants.<br /><br /><span style="font-weight: bold;">Calling Java from Lua</span><br />Be prepared - here comes the most advanced, the most useful and simply best feature of the J2SE goodies.<br /><br />The LuaJavaClassExposer is a class that eliminates the need to manually define JavaFunction implementations for things that you want to expose to Lua.<br /><br />Imaging writing a simple game, which is scriptable with Kahlua, and you want to be able to query a game units health from the Lua script.<br />Without the exposer, you'd have to write something like this:<br /><pre class="brush: java"><br />public class GetUnitHealth implements JavaFunction {<br />public int call(LuaCallFrame callFrame, int nArguments) {<br /> if (nArguments < 1) {<br /> throw new IllegalArgumentException("Expected at least one argument");<br /> }<br /> Object arg = callFrame.get(0);<br /> if (arg == null || !(arg instanceof String)) {<br /> throw new IllegalArgumentException("Expected a string argument but got " + arg);<br /> }<br /> String s = (String) arg;<br /> Unit unit = unitService.getUnit(s);<br /> callFrame.push(unit.getHealth());<br /> return 1;<br />}<br />}<br /></pre><br />Using the exposer instead, you can write something like this:<br /><pre class="brush: java"><br />public class UnitFunctions {<br />@LuaMethod<br />public int getUnitHealth(String unitName) {<br /> Unit unit = unitService.getUnit(unitName);<br /> return unit.getHealth();<br />}<br />}<br /></pre><br />It removes a lot of the boilerplate right? The exposer takes care of all the conversions and argument matchings for us!<br /><br />Instead, you can write an ordinary method in any class, and let the exposer expose that class. One JavaFunction per method will be created, and the method will be available in Lua. The generated JavaFunction will automatically use the installed converters which makes it really easy to integrate the Java and Lua code.<br /><br />There are basically two different styles available when exposing:<br /><br /><span style="font-weight: bold;">Exposing like java</span><br />The first style is exposing things to work almost the same as in Java.<br />You simply call exposer.exposeLikeJava(yourClass, staticBase).<br />After that, a Lua script may call obj:yourMethod(arg1, arg2, ...) if obj is of type yourClass and yourMethod is a method in yourClass.<br /><br />You may be wondering what staticBase means (and if not, you're not paying enough attention). A method are only available for the object if it's a regular java method.<br />Static methods and constructors can't be used this way. Instead, Kahlua uses the staticBase argument, which is a KahluaTable, to fill up with methods that don't belong to specific objects. If you expose the class java.util.Date, then the constructors will be available as:<br />staticBase.java.util.Date.new<br />and static methods such as parse are available as:<br />staticBase.java.util.Date.parse<br /><br />If the class name is unique enough, it is also available directly from the staticBase root, such as staticBase.Date<br /><br />These static methods and functions are what I call functions instead of methods.<br />Instead of invoking them with obj:method, do it like this:<br /><pre class="brush: lua"><br />local unixTimeStamp = 123<br />local dateObject = staticBase.java.util.Date.new(unixTimeStamp)<br />local dateObject = staticBase.Date.new(unixTimeStamp)<br />local NewDate = staticBase.Date.new<br />local dateObject = NewDate(unixTimeStamp)<br /></pre><br />Any of those would work.<br /><br />You can also use exposer.exposeLikeJavaRecursively(yourClass) which works the sam but additionally it also exposes all other classes that yourClass interacts with in any way. This can be useful if you want to avoid manually setting up a lot of exposing, but don't use it when dealing with untrusted code.<br /><br /><span style="font-weight: bold;">Annotation based exposing</span><br />For untrusted code, or simply when you need more custom configuration, consider using the annotation based exposing instead.<br /><br />Use one of these methods to expose a class or objects by using annotations:<br />exposer.exposeGlobalFunctions(object) and exposer.exposeClass(class),<br /><br />Exposing global function takes an actual Java objects and scans it for method annotations. All methods which are marked as global will be exported to Lua as functions, implicitly bound to the object. This means that you should not use the obj:method() notation of invoking them, just use method().<br /><br />Exposing a class instead creates Lua methods for objects of the class, and also exposes static methods as function, if they're marked as global.<br /><br />The available annotations are: @LuaMethod and @LuaConstructor.<br /><br />@LuaMethod has two optional parameters. "name" gives you the option to expose<br />the method with a different name. If this is left out, it uses the method name. The second parameter is "global" which can be true or false. True means that the method will be exposed as a function, and false means that it will be an object method. False is the default.<br /><br />@LuaConstructor similarly takes a "name" parameter.<br />Note that it doesn't take a "global" , since constructors are never bound to an object; they are always implicitly global.<br /><br /><span style="font-weight: bold;">Overloading</span><br />Java supports method overloading based on parameter types, but since functions are first class objects in Lua, it can't support overloading. However, the Kahlua exposer can detect overloaded Java methods and create a limited form av overloading by creating a function that can call any of the overloaded Java methods.<br />Kahlua then uses the parameter types to try to invoke the method that best matches the supplied arguments.<br /><br />Here are some concrete usage examples:<br /><pre class="brush: java"><br />public class Vector {<br /> private final double x, y, z;<br /> @LuaConstructor(name = "newvector")<br /> public Vector(double x, double y, double z) {<br /> this.x = x;<br /> this.y = y;<br /> this.z = z;<br /> }<br /> <br /> @LuaMethod(name = "length")<br /> public double length() {<br /> return Math.sqrt(x*x + y*y + z*z);<br /> }<br />}<br /></pre><br /><br />If this class were exposed by exposer.exposeClass(Vector.class), then Lua scripts could use it like this:<br /><pre class="brush: lua"><br />local v = newvector(3, 4, 0)<br />local len = v:length()<br />assert(len == 5)<br /></pre><br />The other method is mostly useful for service-type features:<br /><pre class="brush: java"><br />public class NetworkService {<br /> private final Pinger pinger;<br /> <br /> @LuaMethod(name = "ping", global = true)<br /> public int ping(String host) {<br /> return pinger.ping(host);<br /> }<br />}<br />exposer.exposeGlobalFunctions(new NetworkService());<br /></pre><br />Used as:<br /><pre class="brush: lua"><br />local pingTime = ping("localhost")<br /></pre>That's it for this time! I could probably go on more in depth with the advanced features in the exposer, but this should already be enough for you to digest.<br /><br />Time for you get started with embedding Kahlua in your Java application, and let me know how it works out! Feedback is always appreciated.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-14615409966735599652010-05-28T22:21:00.012+02:002010-05-28T23:07:42.038+02:00Getting started with Kahlua2This post contains some words and acronyms that are good to know about.<br /><ul><li>J2SE - <span style="font-style: italic;">Java 2 Standard Edition</span> - is the Java version that is available on desktops. Kahlua core depends on J2SE 1.4 or higher, while the J2SE extensions require J2SE 1.5 or higher.</li><li>CLDC - <span style="font-style: italic;">Connected Limited Device Configuration</span> - is a slimmed down version of Java, with many features removed. Kahlua requires CLDC 1.1 or higher to work.</li><li>Midlet - Application for mobile devices using CLDC (and MIDP, but let's not go too deep).<br /></li></ul><br />Kahlua2 is built with a modular design.<br />This means you can configure your system the way you want it but it also means that there are some basic things that need to be set up to get started.<br /><br /><span style="font-weight: bold;">The platform</span><br />First of all, you need a Platform.<br /><br />The core of Kahlua2 has some dependencies that are platform specific. For instance, Kahlua2 needs to be able to create tables, and the table implementations are different for J2SE and CLDC 1.1. They are backed by <span style="font-family:courier new;">ConcurrentHashMap</span> and <span style="font-family:courier new;">Hashtable</span> respectively.<br />For that reason, <span style="font-family:courier new;">Platform</span> has the method:<br /><pre class="brush: java">KahluaTable newTable();<br /></pre><br /><br />Fortunately for you, getting hold of a platform is easy!<br />Just call <span style="font-family:courier new;">J2SEPlatform.getInstance()</span> or <span style="font-family:courier new;">CLDC11Platform.getInstance()</span>.<br />These platform implementations are immutable, so don't worry about sharing the platform with others.<br /><br />Typically you want to use <span style="font-family:courier new;">CLDC11Platform</span> for writing midlets and <span style="font-family:courier new;">J2SEPlatform</span> for everything else. If for some reason, neither of these platforms suit your purposes, you can simply create your own.<br /><br /><span style="font-weight: bold;">An environment</span><br />The global scope in Kahlua (as well as in Lua) is just a regular table. The compiler makes sure to translate any variable that isn't declared as a local to a lookup in the environment table.<br /><br />If the environment is just a regular table, can we simply create one by calling <span style="font-family:courier new;">platform.newTable()</span>? Yes! That works perfectly well.<br /><br />However, this environment will be empty, so you can't find the standard library functions in it, and most of the scripts you want to run probably needs a couple<br />of standard functions to do anything interesting.<br /><br />An alternative way of creating an environment is to call <span style="font-family:courier new;">platform.newEnvironment();</span> This creates a new table, but also populates it with useful stuff. <span style="font-family:courier new;">J2SEPlatform</span> for instance loads the environment with BaseLib, MathLib, RandomLib, StringLib, CoroutineLib, OsLib, TableLib and the compiler.<br /><br />If you're curious, take a look inside <span style="font-family:courier new;">J2SEPlatform</span>, it should be easy to follow.<br /><br /><span style="font-weight: bold;">Compiling scripts</span><br />Having an environment is not very exciting in itself, you probably also want to run some scripts! Kahlua has two ways of creating closures (or functions) for these scripts. The easiest and best way is to use one of the static methods in <span style="font-family:courier new;">LuaCompiler</span>; use <span style="font-family:courier new;">loadstring</span> if you have the input as a string, and <span style="font-family:courier new;">loadis</span> if you have an inputstream or reader. All closures needs environments, so you need to pass in your environment as the last parameter (or another environment if you prefer).<br /><br />Note that the compiler will throw a <span style="font-family:courier new;">KahluaException</span> (which is a <span style="font-family:courier new;">RuntimeException</span>) if the script is malformed. You should be prepared to handle it.<br /><br />The other option is to load the bytecode directly. This is mostly useful on devices where you dont want to bundle the full compiler, such as limited mobile devices. The solution is to compile the scripts offline, either with the standard luac bundled with Lua, or with Kahluas own Java class called LuaC. The resulting binary file can then be loaded with <span style="font-family:courier new;">KahluaUtil.loadByteCodeFromResource</span>.<br /><br /><span style="font-weight: bold;">The thread</span><br />With a platform, an environment and some closures, you're almost set to start running your scripts, but there is one more thing needed - a thread to run them in.<br /><pre class="brush: java">KahluaThread t = new KahluaThread(platform, env)<br /></pre><br />is all you need to create a thread.<br /><br />Kahlua is concurrent in the way that you can create multiple threads that reference the same environment, but don't try to run scripts on the same <span style="font-family:courier new;">KahluaThread</span> from different Java threads! Things would blow up in mysterious and unexpected ways.<br /><br />The most basic way of invoking your closure is by using <span style="font-family:courier new;">thread.call(closure, args...)</span>. However, if the closure invocation should throw an error, a <span style="font-family:courier new;">RuntimeException</span> will propagate out to the Java code. A safer option is to use <span style="font-family:courier new;">thread.pcall(closure, args...)</span> which traps all Lua errors and returns the error information as part of the return values.<br /><br />For J2SE, there are few more ways of invoking closures, but more on that in a later post.<br /><br /><span style="font-weight: bold;">Java functions</span><br />Most applications that use an embedded script engine have a need for the scripts to access domain specific functions. If I were to write a game engine, then my AI scripts might need a way to execute orders. So the opposite of Java invoking Lua scripts is needed; we need to be able to call Java methods from Lua.<br /><br />There are several ways of doing this in Kahlua, but they all boil down to this core functionality:<br /><br /><pre class="brush: java">interface JavaFunction {<br /> int call(LuaCallFrame callFrame, int nArguments);<br />}<br /></pre><br /><br />Kahlua can call any object that implements this interface. This is how all of the standard library in Kahlua is implemented. This is also the only way to do it in CLDC 1.1, due to lack of a reflection API.<br /><br />The parameters to call is a callframe, which contain the arguments passed to the function, and the number of arguments. The return value of call should be the number of return values, since Lua supports multiple return values. The return values themselves need to be pushed on the Kahlua stack, and there are convenience methods for that in the <span style="font-family:courier new;">LuaCallFrame</span> object.<br /><br />Here is a simple example a JavaFunction implementation intended to be used like this:<br /><br /><pre class="brush: lua">local x, y = GetUnitLocation("The unit name")</pre><br /><pre class="brush: java"><br />public class GetUnitLocation implements JavaFunction {<br /> public int call(LuaCallFrame callFrame, int nArguments) {<br /> if (nArguments < 1) {<br /> throw new IllegalArgumentException("Expected at least one argument");<br /> }<br /> Object arg = callFrame.get(0);<br /> if (arg == null || !(arg instanceof String)) {<br /> throw new IllegalArgumentException("Expected a string argument but got " + arg);<br /> }<br /> String s = (String) arg;<br /> Unit unit = unitService.getUnit(s);<br /> callFrame.push(unit.getX());<br /> callFrame.push(unit.getY());<br /> return 2;<br /> }<br />}<br /></pre><br />Due to the dynamic nature of Kahlua, there needs to be a lot of boilerplate error checking, but the rest of the implementation is straight forward.<br /><br /><span style="font-weight: bold;">Exposing things</span><br />Just having a JavaFunction implementation is not enough - it needs to reach the lua scripts in order to be useful. This can be done in several ways. The first, and most obvious, is to put it in the environment:<br /><br /><pre class="brush: java">environment.rawset("GetUnitLocation", new GetUnitLocation());<br /></pre><br /><br />The lua script can then call it by just doing:<br /><pre class="brush: lua">GetUnitLocation("the unit name")</pre><br /><br />The lua script can also copy it somewhere, redefine it - "GetUnitLocation" is just a key in a table, and can be manipulated like any other object, so you can do things like this:<br /><pre class="brush: lua">fun = GetUnitLocation<br />fun("the unit name")<br /></pre><br />or<br /><pre class="brush: lua">local oldfun = GetUnitLocation<br />function GetUnitLocation(s)<br /> print("calling GetUnitLocation here")<br /> return oldfun(s)<br />end<br /></pre><br /><span style="font-weight: bold;">Conclusion</span><br />That's all you need to know to get started with Kahlua. It may seem like there was a lot of steps involved, but each step is really very simple.<br /><br />For mobile platform targets, there isn't much more to add but for J2SE users there are additional goodies available, which I'll go over some time in the near future.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com6tag:blogger.com,1999:blog-3264940927634408517.post-16242790304652827222010-05-25T09:12:00.003+02:002010-05-25T10:17:18.876+02:00Half baked objectsA half baked object is an object that after construction is still not ready to use.<br />Using it will either just silently behave badly (that's bad) or throw a usage exception (that's less bad).<br /><br />This is a really irritating code smell, because it makes it much too easy to introduce bugs. The best APIs I've used have made it impossible (or atleast very difficult) to use it incorrectly because once they've given me an object to work with, they've guaranteed that they're set up properly and are ready for action.<br /><br />There are some generic rules you can use to avoid having half baked objects:<br /><ol><li>Set up everything in the constructor. This is not always possible, but when it is, do it.<br /></li><li>Use final fields - they enforce you set up everything in the constructor, which reduces the risk for bugs. Note that final fields in itself doesn't make the object immutable, you can still have final lists, maps and sets in your object, which themselves are mutable.</li><li>Use builders - and don't allow creating the real object until the builder has all the necessary requirements.</li><li>Be suspicious of methods named things like "init", "postconstruct", "setup" or similar. They could be indicators of a half baked object.<br /></li></ol>However, I have found one case of needing half baked objects, and I currently don't have any workaround for it.<br />This is a new feature in Mockachino, where I want to create an alias for a combination of a mock object and a method signature.<br />Since I can't pass a method signature as a parameter in Java (without using icky reflection) my only choice is to capture the method invocation and record it in the Alias.<br /><br /><pre class="brush:java"><br />interface Foo {<br /> foo(int n);<br />}<br /></pre><br /><pre class="brush:java"><br />Foo mock = mock(Foo.class);<br /><br />mock.foo(123);<br /><br />SimpleAlias alias = newAlias(); // alias is half baked here - it's not bound to any mock<br /><br />alias.bind(mock).foo(anyInt()); // now alias is fully setup<br /><br />alias.verifyOnce();<br /></pre><br /><br />This is one of few cases where half baked objects is hard to avoid, but if anyone has any clever suggestions, I'm all ears.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com3tag:blogger.com,1999:blog-3264940927634408517.post-70960425475289115232010-05-25T09:11:00.005+02:002010-05-25T09:36:42.870+02:00Temporal testable codeA lot of code is time dependent. Code either needs to wait or timeout for a specific amount of time, or it needs to fetch the current system time for some reason.<br /><br />If the code uses Thread.sleep(), System.currentTimeMillis(), new Date(), or anything like that, it has a hidden and implicit dependency. This can be a problem when you're trying to write tests for such code.<br /><br />The tests usually end up with a lot of:<br /><pre class="brush:java"><br />Thread.sleep(1000); // wait for code to finish doing its job.<br /></pre><br />This will make your test suite unnecessarily slow to run, and you want your tests to finish almost instantly.<br /><br />The solution is to convert this implicit dependency to an explicit!<br />This is done by creating the following interface:<br /><pre class="brush:java"><br />public interface TimeProvider {<br />long now(); // Replaces System.currentTimeMillis();<br />sleep(long timeInMilliSeconds) throws InterruptedException; // Replaces Thread.sleep<br />}<br /></pre><br /><br />All the code that is time dependent in any way should inject an object of this interface.<br />Now, you need two implementations of this interface, one for real usage and one for testing. Fortunately, these are trivial to write:<br /><br /><pre class="brush:java"><br />public class SystemTimeProvider implements TimeProvider {<br /> @Override<br /> public long now() {<br /> return System.currentTimeMillis();<br /> }<br /><br /> @Override<br /> public void sleep(long timeInMilliSeconds) throws InterruptedException {<br /> Thread.sleep(timeInMilliSeconds);<br /> }<br />}<br /><br />public class MockTimeProvider implements TimeProvider {<br /><br /> private long now;<br /><br /> public void setNow(long now) {<br /> this.now = now;<br /> }<br /><br /> public void advanceTime(long amountInMillis) {<br /> now += amountInMillis;<br /> }<br /><br /> @Override<br /> public long now() {<br /> return now;<br /> }<br /><br /> @Override<br /> public void sleep(long timeInMilliSeconds) {<br /> now += timeInMilliSeconds;<br /> }<br />}<br /></pre><br /><br />For the real application, everything will behave the same.<br />For testing purposes, just inject the MockTimeProvider instead, and manually manipulate the time.<br /><br />Here's simple example to illustrate how this works in practice.<br />Basically we want to ensure that when we generate UUIDs, a specific part of the UUID remains the same if two UUIDs are generated close enough temporally, but different if there's a small time difference:<br /><br /><pre class="brush:java"><br />public class UUIDTest {<br /> private final MockTimeProvider mockTimeProvider = new MockTimeProvider();<br /> private final UUIDFactory factory = new UUIDFactoryImpl(mockTimeProvider, new SecureRandom());<br /><br /> @Test<br /> public void combTest() throws InterruptedException {<br /><br /> mockTimeProvider.setNow(0);<br /> UUID firstUuid = factory.combUUID();<br /> UUID secondUuid = factory.combUUID();<br /><br /> assertFalse(firstUuid.equals(secondUuid));<br /> long combPart1 = getCombPart(firstUuid);<br /> long combPart2 = getCombPart(secondUuid);<br /> assertEquals(combPart1, combPart2);<br /><br /> mockTimeProvider.advanceTime(20);<br /><br /> UUID thirdUuid = factory.combUUID();<br /> long combPart3 = getCombPart(thirdUuid);<br /> assertFalse(combPart1 == combPart3);<br /><br /> }<br /><br /> private long getCombPart(UUID uuid) {<br /> String combString = "0x" + uuid.toString().substring(24, 36);<br /> return Long.decode(combString);<br /> }<br />}<br /></pre>Stop using static ways of using time in your code!<br />Using an injected TimeProvider works almost identically if it's a SystemTimeProvider, so the only cost is a slightly more costly method invocation since it's through an additional abstraction layer.<br />But the benefits are huge! Your code will be more testable, and the dependency on time is no longer hidden.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-73134287599608045412010-05-21T20:28:00.002+02:002010-05-21T20:53:46.247+02:00The history of KahluaIn 2007, there was really only one alternative if you wanted to run Lua on Java.<br />LuaJava implements a native binding from Java to the real Lua,<br />which requires you to bundle a platform specific library with your Java application.<br /><br />This meant that the integration with Java wasn't as easy to use as it could have been - the memory spaces were completely separated, just like the memory space of regular Lua is separated from C.<br />It also meant that Lua on J2ME devices was complete out of the questions - you're not allowed to bundle native libraries in J2ME applications, and even if you did,<br />they would probably be much too large.<br /><br />So I thought it would be a fun idea to implement a pure Java implementation of Lua to see how similar it would be. I figured that it wouldn't be too much work, since several data types in Lua would be easily mapped by existing classes in Java:<ul><li>strings, numbers and booleans in Lua could be implemented by the String class, Double class and Boolean class respectively in Java. These types are immutable in both languages and have the same behaviour, which<br />makes it a good fit. </li><li>the special value nil was trivially mapped to null in Java.</li><li>tables can be implemented as a plain Java class.</li><li>java functions (a Java object implementing a specific interface).<br /></li></ul><br />Regular Lua implements sophisticated memory management with garbage collection. This is completely avoided in Java by just using the same memory space and taking advantage of the built in garbage collector in the JVM.<br /><br />Error handling in Lua were adapted similarly, by simply mapping Lua errors to Java RuntimeException.<br /><br />Kahlua was originally written with the goal of implementing the basic virtual machine for running Lua bytecode. There were no plans for having a compiler or supporting advanced features such as coroutines. It was aimed at both J2ME and J2SE, and thus only supported the common subset between the two - CLDC 1.1.<br />Since the project goals were fairly modest, and the actual virtual machine can be written fairly simple and straightforward, it didn't take long until Kahlua could load bytecode compiled from the regular Lua and run it with a limited implementation of the base library.<br /><br />After the success of having the toy project actually work, I set out to implement more of the advanced features of Lua - Upvalues, coroutines, weak metatables and the complete string library. Getting all this to work took some time, but it ended up quite compatible with Lua.<br /><br />Soon after that, I started working on a hobby J2SE game project, and thought it would be fun to start using Kahlua as a scripting language there. Kahlua worked nicely there, but it relied on external compilation so we had to either precompile scripts with the commandline luac or make a JNI binding to the lua library. We started with the precompiling, but once we realized that we needed hot reloads,<br />doing the second approach was unavoidable.<br /><br />Within the next couple of years after the initial release of Kahlua, several other pure Lua implementations emerged.<br />First after Kahlua, I think, was Mochalua which was also aimed at J2ME and had more core functionality for directly interacting with MIDP instead of just CLDC, which unfortunately made it harder to use in J2SE. Mochalua was more of a direct port of the original C code than a reimplementation but just like Kahlua, it lacked a compiler.<br /><br />Not long after Mochalua, LuaJ appeared, which also was based on a port of Lua.<br />LuaJ had however also implemented/ported a compiler and had a coroutine implementation based on Java threads. This was a quite sophisticated project, with a very modular design. It had a clever solution for supporting both J2ME and J2SE based on a platform interface that both J2ME and J2SE implemented, which I ended up getting inspiration from later on.<br /><br />It also turned out that LuaJ's compiler could, with a little bit of refactoring, be adapted to fit in with Kahlua, so I forked it and put it into Kahlua and seemingly over night, Kahlua had its own compiler and the JNI solution could be dropped. Thanks LuaJ!<br /><br />A while after this project, yet another Lua project in Java appeared. JILL, or Java Implementation of the Lua Language wasn't really a new project - Nokia had funded it and it had just recently been open sourced. I haven't really looked into it much, but it seemed to use a similar approach as Kahlua, adapting the implementation to Java instead of doing a straight port.<br /><br />Now, back to the game project!<br /><br />We were writing our entire UI system in Lua, with gui and game logic methods implemented in Java and made available to Kahlua. Creating the raw JavaFunction's needed for Kahlua required a lot of low level operations, such as verifying correct number of arguments and the types of the arguments as well as pushing return values, so we decided to implement an easier mechanism for exposing methods.<br /><br />This ended up as a contrib-library in Kahlua that supported exposing Java classes annotated with @LuaMethod. It handled all of the problems above, which made our lives much easier. In time, this library grew to also include conversion between Lua and Java types. Since Lua only used Double as a numeric type, we needed conversions from the other numeric types in Java. Lists and Maps in Java were converted to KahluaTable.<br /><br />This was pretty much the last real development for Kahlua, but I started getting other ideas for the further development of Kahlua.<br /><br /><span style="font-weight: bold;">The birth of Kahlua2</span><br />I started getting a lot of ideas for how to modernize Kahlua which meant departing from many of the original design decisions, and introducing big incompatibilities with the original Kahlua. So, Kahlua2 was born, this time on github instead of Google Code. The reason for this was unrelated to the actual development of Kahlua - I just wanted to learn git, and investigate if its workflow and features had any real life benefits over Subversion.<br /><br />I've identified three main categories of design changes.<br /><br /><span style="font-weight: bold;">Modularity</span><br />Kahlua didn't differentiate the versions for J2SE and J2ME, which meant that J2SE had to suffer a bit (not much, but a bit). The most significant effect was that most of the math operations were implemented in software, which is both slower and less precise than the built in operations in J2SE.<br /><br />The solution in Kahlua2 was to introduce a platform interface implemented for both J2SE and J2ME, and creating two separate math libraries, similar to the solution used in LuaJ.<br /><br /><span style="font-weight: bold;">Compatibility</span><br />Keeping compatibility with Lua was one of the original goals of Kahlua, and it reached pretty far. Tables in Kahlua had the same behaviour as tables in Lua.<br />This was done with a complete low level implementation of tables and special handling of doubles (0 and -0 are the same key in lua tables, but in Java they are distinct). The low level implementation was required to achieve a reasonably fast implementation of next().<br /><br />I meant for Kahlua to be primarily a way of extending Java with a good script language and thus compatibility with Java is more important than compatibility with Lua. Also, keeping the code simple and efficient should have a high priority.<br />The handcoded table implementation in Kahlua is likely not as a good as the built in maps in Java, so Kahlua2 simply drops compatibility on table keys, removes the next function, and removes support for weak tables. I hope no one will miss these features too much.<br /><br /><span style="font-weight: bold;">Concurrency</span><br />Kahlua, and all other Lua implementations I knew of were inheritly single threaded.<br />Each lua state could only be run by one thread at a time, and states couldn't really share data.<br />With the loosening of compatibility, Kahlua2 can instead implement tables as a simple facade to either Hashtable (for J2ME) or ConcurrentHashMap (for J2SE),<br />which means that Kahlua2 suddenly becomes concurrent.<br /><br />All native datatypes in Kahlua (and Lua) are immutable except for tables, upvalues and the stack itself. The stack concurrency is solved by not letting multiple Java threads use the same KahluaThread at the same time. Upvalues are solved by simply making the set and get-methods be synchronized.<br /><br />Unlike Kahlua, Kahlua2 separates the script environment and thread. Multiple KahluaThreads can share the same environment, which is the key to concurrency.<br />The threads are not to be confused with Coroutines, which still work just like in Lua.<br />Many KahluaThreads can share Coroutines, but only one thread can run a coroutine at a time.<br /><br /><span style="font-weight: bold;">Present day</span><br />You can currently find Kahlua2 on github and it's still evolving, although the core ideas for Kahlua2 described above are already implemented. The changes at the point in time mostly consist of bug fixes, refactoring of the compiler (it's still mostly a C port, which fits badly with Java).<br /><br />That's it for now!<br />Stay tuned for The History of Kahlua part 2, expected somewhere around 2013 perhaps.<br /><br />Relevant links:<br /><a href="http://www.keplerproject.org/luajava/">LuaJava</a><br /><a href="http://code.google.com/p/mochalua/">Mochalua</a><br /><a href="http://sourceforge.net/projects/luaj/">LuaJ</a><br /><a href="http://code.google.com/p/jillcode/">JILL</a><br /><br /><a href="http://code.google.com/p/kahlua/">Kahlua</a><br /><a href="http://github.com/krka/kahlua2/">Kahlua2</a><br /><br />The hobby game, with working title <a href="http://fearlessgames.se/">Spaced</a>Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com2tag:blogger.com,1999:blog-3264940927634408517.post-37549950730123688372010-05-18T10:41:00.005+02:002010-05-18T11:14:25.588+02:00What's up with String.formatI noticed a while back that Javas own String.format() is slower than I expected it to be. I compared it to the handbuilt version in Kahlua which is built with a naive approach using only Java 1.4 features.<br /><br />To follow up on this, I wrote a benchmark to see if I can really be sure that it is in fact slower. Writing benchmarks is always tricky and is easy to get wrong. Here's my approach of writing a test.<br /><br /><pre class="brush: java"><br />public class StringFormatTest {<br /> static interface Runner {<br /> String run(String format, Double x, Double y);<br /> String name();<br /> }<br /><br /> static class JavaRunner implements Runner {<br /><br /> @Override<br /> public String run(String format, Double x, Double y) {<br /> return String.format(format, x, y);<br /> }<br /><br /> @Override<br /> public String name() {<br /> return "Java String.format";<br /> }<br /> }<br /><br /> static class LuaRunner implements Runner {<br /> private final KahluaThread thread;<br /> private final LuaClosure closure;<br /><br /> public LuaRunner(KahluaThread thread, LuaClosure closure) {<br /> this.thread = thread;<br /> this.closure = closure;<br /> }<br /><br /> @Override<br /> public String run(String format, Double x, Double y) {<br /> return (String) thread.call(closure, format, x, y);<br /> }<br /><br /> @Override<br /> public String name() {<br /> return "Lua string.format";<br /> }<br /> }<br /><br /> @Test<br /> public void testFormat() throws IOException {<br /> String format = "Hello %3.2f world %13.2f";<br /> Double x = 123.0;<br /> Double y = 456.0;<br /><br /><br /> Platform platform = new J2SEPlatform();<br /> KahluaTable env = platform.newEnvironment();<br /> KahluaThread thread = new KahluaThread(platform, env);<br /> LuaClosure closure1 = LuaCompiler.loadstring("" +<br /> "local stringformat = string.format;" +<br /> "return function(format, x, y)" +<br /> "return stringformat(format, x, y)" +<br /> "end", null, env);<br /> LuaClosure closure = (LuaClosure) thread.call(closure1, null, null, null);<br /><br /> Runner luaRunner = new LuaRunner(thread, closure);<br /> Runner javaRunner = new JavaRunner();<br /><br /> List<Runner> list = new ArrayList<Runner>();<br /> for (int i = 0; i < 20; i++) {<br /> list.add(luaRunner);<br /> list.add(javaRunner);<br /> }<br /> Collections.shuffle(list);<br /><br /> for (Runner runner : list) {<br /> int count = 0;<br /> long t1 = System.currentTimeMillis();<br /> long t2;<br /><br /> while (true) {<br /> t2 = System.currentTimeMillis();<br /> if (t2 - t1 > 1000) {<br /> break;<br /> }<br /> runner.run(format, x, y);<br /> count++;<br /> }<br /> double performance = (double) count / (t2 - t1);<br /> System.out.println(String.format(<br /> "%30s %10.2f invocations/ms",<br /> runner.name(),<br /> performance));<br /> }<br /> }<br />}<br /><br /></pre><br /><br />I've done my best to make this test be fair. The obvious first thing to do is to run each test many times, to ensure that cache misses, JIT optimizations, warmups, et.c. are all taken into account. The second obvious thing is to shuffle the ordering of tests to avoid introducing accumulating interference.<br />For instance, if I were to run the tests as A, B, A, B, ... then any garbage being produced at the end of A would punish B when it ran its garbage collector.<br /><br />Having run this test suite for a bit, I consistently get these results:<br /><pre><br /> Lua string.format 232.71 invocations/ms<br /> Java String.format 170.07 invocations/ms<br /> Lua string.format 231.61 invocations/ms<br /> Java String.format 170.34 invocations/ms<br /> Lua string.format 232.73 invocations/ms<br /> Java String.format 170.10 invocations/ms<br /> Java String.format 170.11 invocations/ms<br /> Java String.format 171.23 invocations/ms<br /></pre><br /><br />Why is the Lua version faster? It should be much slower considering:<br /><ol><li>The Lua version has to go into its interpreter loop as additional overhead.</li><li>The Lua implementation of string.format is a naive and short implementation, and not built by the elite development team of Sun.</li></ol>Perhaps the difference is that the default Java implementation handles a lot of additional use cases such as locale, but that still doesn't really explain it.<br /><br />Does anyone have any ideas why Javas String.format is slow?Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1tag:blogger.com,1999:blog-3264940927634408517.post-72604446208418925202010-05-17T08:33:00.007+02:002010-05-18T10:40:51.830+02:00TDD - levels of insight<span style="font-size:100%;">Test Driven Development (or Design) is a method of developing code where you first write small tests that express the requirements, it can either be requirements from the customer or product owner, or requirements the developers themselves deduce are needed of the product.<br /><br />The idea is that by writing the tests first, the design of the code improves, because it will automatically become modular (writing tests for code that's not modular is much harder, if not impossible). The tests also increase your development speed, since running your suite of tests takes a much shorter time than starting up the application and manually testing everything. If you make a mistake somewhere when refactoring the code or writing a new feature, it will become obvious directly, since the tests will expose it, if it breaks any of the requirements.<br /></span><span style="font-size:100%;"></span><br /><span style="font-size:100%;">But let's not go into the details of TDD, there are plenty of other sources that describe TDD much better than I ever could.<br /><br /></span><span style="font-size:100%;">Instead, this blog post will be about a hypothesis I have.<br /></span><span style="font-size:100%;">I don't believe you can really study TDD and just get it. You have to try it out for yourself and become convinced by experiencing the benefits. You will notice that you can keep maintaining a project without losing speed and your code will be extendable.<br /></span><br />So what is the hypothesis? Glad you asked!<br /><span style="font-size:100%;"><blockquote>Every developer will go through a series of levels of insight, with each level being closer to being a TDD master.<br /></blockquote><br />And here are the levels I've identified, based on anecdotal evidence consisting of my personal experience, and what I've observed in others.<br /><br /></span><span style="font-weight: bold;font-size:100%;" >#1 Obliviousness</span><br />As a fresh developer, it's obvious that at some point in your life, you didn't know about TDD. I'd also take a guess that it's common to start programming before starting to write tests. From the various educations I've been to and talked to others about, testing is not something that's introduced early in programming training.<br /><br />Obliviousness simply means that you're unaware of TDD is a practice and its usefulness. I was unfortunately in this category for much too long, which I suspect is true for a lot of developers.<br /><br /><span style="font-weight: bold;font-size:100%;" >#2 Disregard</span><br />The next step is hearing about TDD and getting the initial thought: "Writing tests first? That sounds backwards!". Not only that, you may also think that is seems like a waste of time to spend a lot of time writing tests that will soon be obsolete anyway, or tests for things that have obvious failures "I'll obviously notice immediately when starting up if this breaks".<br /><br /><span style="font-weight: bold;font-size:100%;" >#3 Awareness</span><br />Level 3 is being aware of TDD and that it can be a useful tool, and not just a stupid overhead designed as support for bad developers.<br /><br />The easiest way to get past level 2 onto level 3 is to work with someone who's already past it, who seems to be using it successfully.<br /><br />"Hmm, that guy produces clean code and doesn't seem to introduce as many bugs as I do, I wonder why..." Deeper investigation may lead to the introduction of TDD.<br /><br />This may inspire you to try out writing tests first (or just writing tests at all), but since you're unfamiliar with TDD to begin with, your code will be hard to test, and it will be a pain to write the tests. You'll spend a long time to write the test, and you'll become irritated. "Do I really gain anything from spending so much time writing tests instead of producing code? QA will find any bugs I produce anyway, better to spend the time later to bugfix it instead."<br /><br />Unfortunately, this is a typical setback that some people fail to get past.<br /><br /><span style="font-weight: bold;font-size:100%;" >#4 Empirical</span><br />Level 4 is when you've tried TDD for such a long time that you're really convinced that it's the best way to develop.<br />To reach this level, you need to really have used for such a long time that you have started to reap the benefits.<br /><br />You have may have done a simple refactoring or introduced a new feature when one of your oldest tests break, and you look into it. "Aha, of course I needed to consider <span style="font-style: italic;">that</span> before I did <span style="font-style: italic;">this</span>, no wonder it broke!".<br /><br />This is when you'll start building up the confidence in your code. If you introduce some code change that will break something, your tests will catch it.<br /><br />Writing good tests, and writing them before the code is hard, as is writing clean and modular code. Becoming good at TDD takes time and effort, but it also makes you a better developer and better designer. Suddenly all your code will have at least two use cases - the test code and the runtime code.<br /><br /><span style="font-weight: bold;font-size:100%;" >#5 Mastery</span><br />After having been in level 4 long enough, TDD will become second nature to you.<br />You would use TDD for all development with the insight that it drives good design and saves time. No aspect of code is too hard to write test driven for a master, not even the typical<span style="font-size:100%;"> daunting tasks intimidates the TDD master: UI, database, network, et.c.<br /><br /></span><span style="font-size:100%;"> <span style="font-weight: bold;">Conclusion</span></span><br />I personally am stuck in level 4 at the moment. Perhaps I'll stay there forever, but even so it's probably a good idea to keep striving to reach level 5. I do this by trying to embrace TDD in my development as much as I can, but how can I be sure that's enough? Perhaps some other insight is needed to step up to the next level.<br /><br />If I find any answers to that, You can expect a follow up post.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1tag:blogger.com,1999:blog-3264940927634408517.post-13576722710253438822010-03-13T22:22:00.004+01:002010-03-13T22:28:44.808+01:00Followup on Mockito thread safetyIn a previous blog post, I wrote that Mockito could not share mocks in a thread safe way, but I didn't motivate it in much detail.<br /><br />Here's the sample code that fails:<br /><pre class="brush:java"><br />import org.junit.Test;<br />import org.mockito.InOrder;<br />import org.mockito.Mockito;<br /><br />import java.util.List;<br />import java.util.concurrent.CountDownLatch;<br /><br />import static org.junit.Assert.assertEquals;<br />import static org.mockito.Mockito.*;<br /><br />public class TestMulti {<br /> private static interface TestInterface {<br /> int foo(String threadName, int count);<br /> }<br /><br /> @Test<br /> public void testSharedMock() throws InterruptedException {<br /> final CountDownLatch start = new CountDownLatch(1);<br /> final CountDownLatch stop = new CountDownLatch(1);<br /><br /> final int numThreads = 2;<br /> final long TIMEOUT = 2000;<br /><br /> final TestInterface mock = Mockito.mock(TestInterface.class);<br /><br /> Thread[] threads = new Thread[numThreads];<br /> final int[] counts = new int[numThreads];<br /> for (int i = 0; i < numThreads; i++) {<br /> final String name = "Thread:" + i;<br /> final int finalI = i;<br /> Thread t = new Thread(name) {<br /> @Override<br /> public void run() {<br /> try {<br /> start.await();<br /> long t1 = System.currentTimeMillis();<br /> int count = 0;<br /> while (System.currentTimeMillis() - t1 < TIMEOUT) {<br /> count++;<br /> doReturn(count).when(mock).foo(name, count);<br /> verify(mock, never()).foo(name, count);<br /> assertEquals(count, mock.foo(name, count));<br /> verify(mock).foo(name, count);<br /> }<br /> counts[finalI] = count;<br /> System.out.println(name + " did " + count + " iterations");<br /> } catch (InterruptedException e) {<br /> throw new RuntimeException(e);<br /> } finally {<br /> stop.countDown();<br /> }<br /> }<br /> };<br /> threads[i] = t;<br /> t.start();<br /> }<br /><br /><br /> start.countDown();<br /> stop.await();<br /> int totalCount = 0;<br /> for (int i = 0; i < numThreads; i++) {<br /> final String name = "Thread:" + i;<br /> int count = counts[i];<br /> totalCount += count;<br /> InOrder order = inOrder(mock);<br /> for (int j = 0; j < count; j++) {<br /> order.verify(mock).foo(name, 1 + j);<br /> }<br /> verify(mock, times(count)).foo(eq(name), anyInt());<br /> }<br /> System.out.println("Total count: " + totalCount);<br /> }<br />}<br /><br /></pre><br /><br />Due to the undeterministic behaviour, this can error with multiple problems, including:<br /><ol><li>Exception in thread "Thread:1" java.lang.NullPointerException<br />at org.mockito.internal.stubbing.MockitoStubber.findAnswerFor(MockitoStubber.java:63)</li><li>Exception in thread "Thread:1" java.lang.AssertionError: expected:<1> but was:<0><br /></li><li>Exception in thread "Thread:1" org.mockito.exceptions.misusing.UnfinishedVerificationException:<br />Missing method call for verify(mock) here:<br /></li><li>Exception in thread "Thread:0" org.mockito.exceptions.misusing.UnfinishedStubbingException:<br />Unfinished stubbing detected here:<br />-> at TestMulti$1.run(TestMulti.java:43)<br /></li><li>Exception in thread "Thread:0" java.util.ConcurrentModificationException<br />at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)<br />at java.util.LinkedList$ListItr.next(LinkedList.java:696)<br />at org.mockito.internal.stubbing.MockitoStubber.findAnswerFor(MockitoStubber.java:62)<br /></li><li>Exception in thread "Thread:0" java.util.ConcurrentModificationException<br />at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:761)<br />at java.util.LinkedList$ListItr.next(LinkedList.java:696)<br />at org.mockito.internal.stubbing.MockitoStubber.findAnswerFor(MockitoStubber.java:62)<br /></li><li>Exception in thread "Thread:0" java.lang.NullPointerException<br /> at java.util.concurrent.ConcurrentLinkedQueue.offer(ConcurrentLinkedQueue.java:190)<br /> at java.util.concurrent.ConcurrentLinkedQueue.add(ConcurrentLinkedQueue.java:180)<br /> at org.mockito.internal.stubbing.StubbedInvocationMatcher.addAnswer(StubbedInvocationMatcher.java:34)<br /><br /></li></ol>Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-68945086986864315242010-02-21T12:50:00.004+01:002010-11-29T16:43:58.537+01:00Mockito vs MockachinoI wrote down some differences between <a href="http://code.google.com/p/mockito/">Mockito</a> and <a href="http://code.google.com/p/mockachino/">Mockachino</a>, ordered by how important they are for actual mock usage.<br /><br />Note that I am quite biased since I actually wrote Mockachino, but I'm also a great fan of Mockito and I still prefer Mockito over all other java mocking frameworks. I have tried to be as objective as possible, but if I have missed some important aspect to compare, please let me know, and I'll add it.<br /><br /><span style="font-weight: bold;">The basic syntax</span><br />The syntax is definitely one of the most important aspect of mocking, especially when comparing frameworks that are similar in most other regards.<br />Mockito and Mockachino have slight differences in syntax, with the biggest difference being when stubbing a mock method:<br /><pre class="brush: java"><br />// Mockito<br />when(mock.theMethod(eq(value1), eq(value2), same(value3))<br />.thenReturn(theReturnValue);<br />// Mockachino<br />stubReturn(theReturnValue).on(mock).theMetod(value1, value2, same(value3));<br /></pre><br />Mockito has a better flow here: you first type what you want to match on and then what you want to return. Mockito also has a type safe return value, since the compiler will enforce that theReturnValue is of the same type as the return type of mock.theMethod().<br /><br />There are a couple of disadvantages of this approach:<br /><ol><li>It actually needs to invoke the mock first, and then undo the side effect it produces. This is actually impossible to do if the mock is actually a spy. What Mockito actually does here is remove the invocation from the mocks call history so it won't be a false match in any later verification.</li><li>The mock invocation might actually throw an exception, which will kill the test. The workaround for this is to use Mockitos alternative syntax, which is more similar to Mockachinos. More in this problem later.<br /></li><li>It's not possible to use mocks inlined here, since that will confuse the stubbing mechanism, which basically just remembers the latest invoked mock when adding the stubbing.<br /></li></ol>Mockachino's approach may seem a bit backwards at first but it's generally not much more difficult to grasp than the difference between these sentences:<br /><ol><li>When you call my by the phone number 08-123 456, I will send a fax reply back.</li><li>I will send a fax reply back when you call me by the phone number 08-123 456.</li></ol>Mockachino is a bit more consistent in its syntax here. Every kind of interaction with the mock (stubbing, adding observers, verifying behaviour) has the same syntax:<br /><pre class="brush: java"><br />// Stubbing<br />stubReturn(theReturnValue)<br />.on(mock).theMetod(value1, value2, same(value3));<br />// Observing<br />observeWith(observer)<br />.on(mock).theMetod(value1, value2, same(value3));<br />// Verifying<br />verifyOnce()<br />.on(mock).theMetod(value1, value2, same(value3));<br /></pre>As you can see, they all end with<br /><pre class="brush: java">on(mock).theMetod(value1, value2, same(value3));</pre>which is quite consistent. It also keeps the mock object close to the method call.<br />Compare it with Mockito, which breaks up this pattern by having additional parameters between the mock and the method call when verifying:<br /><pre class="brush: java">verify(mock, times(1)).theMetod(value1, value2, same(value3));</pre><br /><span style="font-weight: bold;font-size:100%;" >Clean stacktrace<br /><span style="font-weight: bold;"><span style="font-weight: bold;"></span></span></span><span style="font-size:100%;">Both Mockito and Mockachino clean up stacktraces upon errors, which means that the stacktrace will exclude all Mockito/Mockachino stack elements<br /></span><span style="font-weight: bold;font-size:100%;" ><span style="font-weight: bold;"><span style="font-weight: bold;"><br /></span></span></span><span style="font-weight: bold;">Mixing argument matchers and plain arguments</span><br />When stubbing or verifying a method in Mockito, you may choose to use argument matchers instead of values, which gives you great flexibility. However, you can not mix them. The solution is simple: just add the eq()-matchers for everything that you don't want to match explicitly.<br /><br />Mockachino has a slightly more friendly approach. It allows mixing plain values with matchers, as long as the plain values are not the default values for their type (i.e. null, false, 0, '\0').<br /><br /><span style="font-weight: bold;">In order verification</span><br />Mockito has a couple of bugs (or design choices) when trying to verify things in order. Here is one:<br /><pre class="brush: java"><br />@Test<br />public void testInOrder() {<br /> List mock = Mockito.mock(List.class);<br /> mock.add("Foo");<br /> mock.add("Bar");<br /> mock.add("Foo");<br /><br /> InOrder order = Mockito.inOrder(mock);<br /> order.verify(mock, Mockito.atLeast(1)).add("Foo");<br /> order.verify(mock, Mockito.atLeast(1)).add("Bar");<br /> order.verify(mock, Mockito.atLeast(1)).add("Foo");<br />}<br /></pre><br />This fails, even though it's clear that it shouldn't.<br />Compare with the Mockachino example below. This works as expected.<br /><pre class="brush: java"><br />@Test<br />public void testMockachinoInOrder() {<br /> List mock = Mockachino.mock(List.class);<br /> mock.add("Foo");<br /> mock.add("Bar");<br /> mock.add("Foo");<br /><br /> InOrder order = Mockachino.verifyOrder();<br /> order.verifyAtLeast(1).on(mock).add("Foo");<br /> order.verifyAtLeast(1).on(mock).add("Bar");<br /> order.verifyAtLeast(1).on(mock).add("Foo");<br />}<br /></pre><span style="font-weight: bold;">Singleton ordering per mock object</span><br />In Mockito, one mock object can only have one ordering-object. This means that the following does not work:<br /><pre class="brush: java"><br />@Test<br />public void testMockito() {<br /> List mock = Mockito.mock(List.class);<br /><br /> mock.add("Foo");<br /><br /> InOrder order1 = Mockito.inOrder(mock);<br /> order1.verify(mock).add("Foo");<br /><br /> InOrder order2 = Mockito.inOrder(mock);<br /> order2.verify(mock).add("Foo");<br />}<br /></pre><br />In Mockachino, each ordering object is different and holds its own verification state. This works as expected:<br /><pre class="brush: java"><br />@Test<br />public void testMockachino() {<br /> List mock = Mockachino.mock(List.class);<br /><br /> mock.add("Foo");<br /><br /> OrderingContext order1 = Mockachino.newOrdering();<br /> order1.verify().on(mock).add("Foo");<br /><br /> OrderingContext order2 = Mockachino.newOrdering();<br /> order2.verify().on(mock).add("Foo");<br />}<br /></pre><br /><span style="font-weight: bold;font-size:100%;" >Multithreading</span><br />Mockito fails with incorrect error messages when trying to use the same mock in multiple threads.<br />With Mockachino, multithreading is not a problem. You can share mock contexts and even mocks between threads<br /><br /><span style="font-weight: bold;">equals, hashCode and toString<br /></span><span>These three methods can be tricky, since they are base methods used</span><span> a lot by Java standard libraries (Sets, Maps, Lists, et.c.). Mockachino supports stubbing of all these methods, Mockito only supports stubbing toString. Stubbing these methods can be very useful at times, such as using mocks as keys in maps where a correct equals and hashCode are essential.<br /><br />When it comes to verifying, all these are possible to verify with Mockachino, but it's not always a good idea, since these methods can be called almost anywhere. Also, the correctness of your code should probably not depend on specific calls to these methods.<br /></span><span style="font-weight: bold;"><br />API that never lies</span><br />Mockito uses a generic VerificationMode parameter to the verify methods, but all verification modes do not work for InOrder verification. This is very unclear in the API.<br />Mockachino instead hides its unsupported modes in the ordering API.<br /><br /><span style="font-weight: bold;">Support for inline mocking</span><br />Since Mockito does a lot of dark magic to enable its terse syntax, it's quite frail when you interrupt its expected flow of constructs. Inline mocking is a perfect example of this.<br />I have on several occasions had the need to let a mock return another mock.<br /><br />This, and similar constructs fails in Mockito:<br /><pre class="brush: java"><br />@Test<br />public void testInlineMockito() {<br /> List mock = Mockito.mock(List.class);<br /> Mockito.when(mock.get(0)).thenReturn(Mockito.mock(List.class));<br />}<br /></pre><br />The workaround is at least simple:<br /><pre class="brush: java"><br />@Test<br />public void testInlineMockitoWorkaround() {<br /> List mock = Mockito.mock(List.class);<br /> List secondMock = Mockito.mock(List.class);<br /> Mockito.when(mock.get(0)).thenReturn(secondMock);<br />}<br /></pre><br />No workarounds are necessary with Mockachino since it does not rely on ordering of calls.<br />Thus, the equivalent in Mockachino works fine:<br /><pre class="brush: java"><br />@Test<br />public void testInlineMockachino() {<br /> List mock = Mockachino.mock(List.class);<br /> Mockachino.stubReturn(Mockachino.mock(List.class)).on(mock).get(0);<br />}<br /></pre><span style="font-weight: bold;">Calling mock methods when verifying</span><br />Another interesting case is this. Due to Mockitos design choice of letting calls to verify and stub apply to the most recently invoked mock method, the following case breaks, since verify will actually try to verify mock.size() instead of mock.add()<br /><pre class="brush: java"><br />@Test<br />public void testMockito() {<br /> List mock = Mockito.mock(List.class);<br /> mock.add(0);<br /> Mockito.verify(mock).add(mock.size());<br />}<br /></pre><br />It works fine in Mockachino, due to a different design choice:<br /><pre class="brush: java"><br />@Test<br />public void testMockachino() {<br /> List mock = Mockachino.mock(List.class);<br /> mock.add(0);<br /> Mockachino.verifyOnce().on(mock).add(mock.size());<br />}<br /></pre><br /><span style="font-weight: bold;">Deep mocks</span><br />Update 2010-03-13 - Both the latest Mockito and Mockachino have deep mock handlers that behave in the same way.<br /><br /><span style="font-weight: bold;">Time ranges</span> Mockachino supports verifying that interactions with a mock happened in a specific time range.<br />See <a href="http://krkadev.blogspot.com/2010/02/additional-features-of-mockachino.html">additional-features-of-mockachino</a> for a more detailed explanation.<br />Mockito does not include this feature.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com7tag:blogger.com,1999:blog-3264940927634408517.post-80040307887845906072010-02-13T23:33:00.004+01:002010-02-14T00:34:46.511+01:00Additional features of MockachinoMockachino is making good progress!<br />Apart from generic refactorings, I've added a few nifty features:<br /><br /><span style="font-weight: bold;">Support for equals, hashCode and toString</span><br />Unlike EasyMock and Mockito, Mockachino now supports stubbing, verifying of all these methods. The other mocking frameworks probaby have good reasons for not supporting those. I at least know that Mockachino used to have good reasons. If you're not interested in the technical details, you can skip the next two paragraphs.<br /><br />All mocks need some sort of data storage for their metadata. The metadata is basically just a memory of all invocations and a list of all stubbing definitions. This metadata needs to either be stored in the mock itself or use some sort of mapping strategy. I used to have a WeakHashMap that mapped the mocks to their metadata, and for that to work I required a fixed equals and hashCode.<br /><br />My new approach is instead to let all my mocks implement a secondary interface which has a secret method for retrieving the metadata. The invocation handler for the mock simply listens for this method call and returns its reference to the metadata. It's really quite simple, and as with all simple ideas, you start to wonder why you didn't think of it before.<br /><br /><span style="font-weight: bold;">The problem with in order verification</span><br />One problem I had was in order verification of this sort:<br /><pre class="brush: java"><br />@Test<br />public void test() {<br />List mock = mock(List.class);<br />mock.add(100);<br />mock.add(200);<br />mock.add(100);<br /><br />OrderingContext ordering = newOrdering();<br />ordering.verifyAtMost(1).on(mock).add(100);<br />ordering.verifyAtLeast(1).on(mock).add(200);<br />}<br /></pre><br />By reading the entire ordering part, it seems that the test would pass, since there is only one call to add(100) before the call to add(200). But at the time of the first verification, it doesn't know when it should stop looking for more matches. This is easy to see when considering the next example:<br /><pre class="brush: java"><br />@Test<br />public void test() {<br />List mock = mock(List.class);<br />mock.add(100);<br />mock.add(100);<br /><br />OrderingContext ordering = newOrdering();<br />ordering.verifyAtMost(1).on(mock).add(100);<br />}<br /></pre><br />Here you obviously expect a failure since there were in fact two calls to add(100) when you expected at most one. For this reason, Mockachino doesn't support "at most"-matching for in order verifications.<br /><br />So I started thinking about different approaches.<br />You could do something like this instead:<br /><pre class="brush: java"><br />@Test<br />public void test() {<br />List mock = mock(List.class);<br />mock.add(100);<br />mock.add(200);<br />mock.add(100);<br /><br />OrderingContext ordering = newOrdering();<br />ordering.verifyAtMost(1).on(mock).add(100);<br />ordering.verifyAtLeast(1).on(mock).add(200);<br />ordering.verifyOrdering();<br />}<br /></pre><br />Simply change the ordering concept to not verify anything at all until the call to verifyOrdering() is called. At this point you do have all the information you need.<br />The problem with this is that it adds a lot of complexity, both to the code base and to the tests. It's similar to solving a complex regular expression - it would need to backtrack on failures until it can be sure that it's impossible to satisfy the conditions.<br /><br />It's simply not a clean solution. In practice such an ordering tests would be frail and be far to dependent on the internal state.<br /><br /><span style="font-weight: bold;">Adding "points in time" and time range verification.</span><br />Another way of supporting these kind of use cases is to add two new very simple constructs, that should rarely be needed, but be very useful and powerful in the few cases that you do.<br /><br />The first construct is the <span style="font-style: italic;">MockPoint</span>. This is simply a point in time that you can get in two different ways:<br /><pre class="brush: java"><br />// 1<br />MockPoint point = Mockachino.getCurrentPoint();<br /><br />// 2<br />OrderingContext order = Mockachino.newOrdering();<br />order.verifyOnce().on(mock).add();<br />MockPoint point = order.afterLastCall();<br /></pre><br />With these points, you can take advantage of the second construct: <span style="font-style: italic;">between</span>, <span style="font-style: italic;">after</span> and <span style="font-style: italic;">before</span><br />Simply add between(point1, point2) before your verification line to limit your matches to calls done between those points in time.<br /><br />So instead of checking that something happened at most a certain number of times in order, grab the time points and verify it normally with between instead:<br /><br /><pre class="brush: java"><br />@Test<br />public void test() {<br />List mock = mock(List.class);<br />mock.add(100);<br />mock.add(200);<br />mock.add(100);<br /><br />// Get the points<br />OrderingContext ordering = newOrdering();<br />MockPoint p1 = ordering.atLastCall();<br />ordering.verifyAtLeast(1).on(mock).add(200);<br />MockPoint p2 = ordering.beforeLastCall();<br /><br />between(p1, p2).verifyAtMost(1).on(mock).add(100);<br />}<br /></pre><br />It's not as pretty as in the first example, but it works and is conceptually simple.<br />I don't recommend overusing this feature since it's probably in most cases a warning sign that your code is frail and makes too many assumptions.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1tag:blogger.com,1999:blog-3264940927634408517.post-34883219717565589162010-02-12T16:08:00.004+01:002010-02-12T22:23:21.142+01:00The different types of testsThere is a huge number of examples of types of tests in the development community and they can be categorized in many different ways<br /><br />I am going to focus on splitting tests by their intention here.<br />I guess people generally think of tests as a tool for reducing bugs and keeping robustness. Tests give us the courage to dare perform large refactorings and introduce new features while being relatively confident that we aren't breaking things.<br /><br />That's a very important part of writing tests but I'll argue that there's another side to it:<br />Tests help us design. Tests help us write clean code. Tests help us split code into isolated modules.<br /><br />With these two in mind, consider the following two test strategys: Unit Testing and Blackbox Testing.<br /><br /><span style="font-weight: bold;">Blackbox tests</span><br /><blockquote></blockquote><blockquote><span style="font-style: italic;">my definition:</span><br />A blackbox test looks at the code as if it were a black box, i.e. the internals of the system are unknown and irrelevant. You use your knowledge of the system requirements to provide the inputs and verify that the outputs are correct.<br /></blockquote><br />I really like writing blackbox tests because they are fairly immune to internal refactorings and can usually quite easily capture the requirements on a high level. Blackbox tests have the additional benefit of being able to test a lot of code at once, and only testing code that will actually be used by real users.<br /><br />However, writing blackbox tests on a too high level doesn't force you to write clean and modularized code.<br /><br /><span style="font-weight: bold;">Unit tests</span><br /><blockquote><span style="font-style: italic;">my definition:</span><br />A unit test verifies the correctness of individual components of the system (hence the name unit). If the component (or unit) needs some collaborators, you typically mock them, and let them provide the inputs you want for your specific test. Unlike black box testing, you want to limit the scope of testing as much as possible per test.<br /></blockquote><br />Unit tests on the other hand usually have to be rewritten every time you perform refactorings and they can usually only capture requirements that are contained within a single class. The advantage of unit tests is that they force you to write your classes to be testable individually, which greatly helps you write good code.<br /><br /><span style="font-weight: bold;">Coverage</span><br />Some people like to measure the coverage of their codebase, and diligently write unit tests until they're at an acceptable level. I think that writing unit tests for the sake of increasing coverage is wrong.<br /><br />The problem is that you're potentially testing dead code, and our only way of detecting dead code is by looking at coverage reports.<br /><br />Instead, consider measuring coverage from blackbox tests and unit tests separately.<br />The blackbox tests should reflect the overall system requirements so run coverage for those tests. Then by looking at the coverage report you can spot dead code - Code that isn't used by any requirement.<br /><br />If you spot any particular dead code section, you have two options:<br /><ol><li>Remove the code - it isn't used! Dead code bloats down your codebase.</li><li>If the code can't be removed, it must be a part of some requirement, so formalize the requirement as a blackbox test and try it again.</li></ol>If you try writing a unit test just to exercise that code, you haven't gained anything, just a false sense of code coverage.<br /><br /><span style="font-weight: bold;">Conclusion</span><br />When developing according to TDD practices, should you write blackbox tests or unit tests?<br />The answer is both! I like to start with writing blackbox tests that cover all the requirements I can come up with. Then continue iteratively with unit tests and code in the usual TDD cycle until both the blackbox tests and unit tests are happy.<br /><br />This should mean that you both capture the necessary requirement while maintaining a healthy code base.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1tag:blogger.com,1999:blog-3264940927634408517.post-28988575228417848582010-02-12T11:11:00.007+01:002010-02-12T13:51:32.351+01:00When mocks failA mocking framework has three fundamental features:<br /><ol><li>Makes it easy to <span style="font-weight: bold;">stub</span> behaviour to make your test code work.</li><li>Makes it easy to <span style="font-weight: bold;">verify</span> that some behaviour has taken place.</li><li>Makes it easy to <span style="font-weight: bold;">debug</span> a broken test.</li></ol>Today I'll focus on the third part.<br /><br />When a test fails, it either means that your code is wrong or your test is wrong.<br />Either way, you want to find the cause of the problem as quickly as possible.<br /><br />To assist with this, mocking frameworks try to give you as much relevant information as possible when a verification fails.<br /><br />EasyMock usually says something like:<br /><pre class="brush: java">@Test<br />public void testFailEasymock() {<br /> List mock = createNiceMock(List.class);<br /> expect(mock.add("Hello")).andReturn(true);<br /> replay(mock);<br /> mock.remove("World");<br /> mock.remove("Hello");<br /> mock.add(null);<br /> mock.add("World");<br /> verify(mock);<br />}</pre><br /><pre>java.lang.AssertionError:<br />Expectation failure on verify:<br /> add("Hello"): expected: 1, actual: 0</pre><br /><br />which tells you that add was expected, but never called.<br /><br />Mockito is a bit nicer and shows what was actually called instead:<br /><pre class="brush: java">@Test<br />public void testFailMockito() {<br /> List mock = mock(List.class);<br /> mock.remove("World");<br /> mock.remove("Hello");<br /> mock.add(null);<br /> mock.add("World");<br /> verify(mock, atLeastOnce()).add("Hello");<br />}</pre><br /><pre>Argument(s) are different! Wanted:<br />list.add("Hello");<br />-> at ordering.MixedOrderTest.testFailMockito(MixedOrderTest.java:95)<br />Actual invocation has different arguments:<br />list.add(null);<br />-> at ordering.MixedOrderTest.testFailMockito(MixedOrderTest.java:93)<br /><br />Expected :list.add("Hello");<br />Actual :list.add(null);</pre><br />Which is more helpful than EasyMock.<br /><br />However, Mockito only suggests the first invocation of list.add as the actual invocation instead of the best matching.<br /><br />Mockachino goes a step further and suggests the three best matching calls, sorted by how well it was matched:<br /><pre class="brush: java">@Test<br />public void testFailMockachino() {<br /> List mock = mock(List.class);<br /> mock.remove("World");<br /> mock.remove("Hello");<br /> mock.add(null);<br /> mock.add("World");<br /> verifyAtLeast(1).on(mock).add("Hello");<br />}</pre><br /><pre>se.mockachino.exceptions.VerificationError: Expected at least 1 call but got no calls<br />Method pattern:<br />add("Hello")<br /><br />Near matches:<br />add("World")<br /> at se.mockachino.order.InOrderTest.testFailMockito(InOrderTest.java:116)<br />add(null)<br /> at se.mockachino.order.InOrderTest.testFailMockito(InOrderTest.java:115)<br />remove("Hello")<br /> at se.mockachino.order.InOrderTest.testFailMockito(InOrderTest.java:114)<br />... skipping 1 calls<br /><br /> at se.mockachino.order.InOrderTest.testFailMockito(InOrderTest.java:117)</pre><br />As you can see, both Mockito and Mockachino show where the verification call was made,<br />and where the actual matches were made. This is really helpful if you run the tests in an IDE, just click on the lines to jump to the corresponding line in the code.<br /><br />It's clear that EasyMock shows too little information here, but how much is too much?<br /><br />Is the simple approach of Mockito to just show the first partially matching method call sufficient? Yes, it probably does cover most of the cases but I think it would be improved without adding any noise if it tried to do some smarter matching.<br /><br />I think it's equally likely that a mock called the wrong method but with the correct parameters compared to calling the correct method but with the wrong parameters. I think the approach of showing multiple suggestions is a good one.<br /><br />In conclusion I think that both Mockito and Mockachino do a good job of reporting failed verifications, and that Mockachino may have an advantage in debugging some use cases where the mockito suggestion is the wrong one.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-41068185824503383762010-02-09T16:04:00.003+01:002010-02-10T08:23:38.627+01:00Injection and cyclic dependenciesCyclic dependencies are bad, and they are usually a sign that one on more classes have too many responsibilities. Cyclic dependencies make your design rigid.<br /><br /><span style="font-weight: bold;">Finding the cycle</span><br />There are basically two ways cyclic dependencies can appear:<br /><ol><li>You're using an injection framework such as Guice or Spring that automatically resolves cyclical dependencies without you knowing you even had them.</li><li>You're using setters instead of constructors to initialize your classes.</li></ol>The first case is easily exposed if you have suitable unit or scenario tests that are manually wired up.<br />The second case is simply bad practice. I really really advice you to use final fields and set them in the constructor. I can't begin to count the number of runtime issues I've had due to uninitialized fields.<br /><br /><span style="font-weight: bold;">So how do you resolve a cyclic dependency?</span><br />Resolving it is a much harder problem. You need to analyze your code and figure out what the cycle looks like, and what the root problem is.<br />Usually the problem is that one or more classes have too much responsibility and thus need many collaborators. Split up the classes in distinct responsibilities and remove dependencies you don't actually need.<br /><br />Another option is to move some fields to methods instead and just pass along the collaborator you need. It's not always a good idea, but neither is keeping a large state inside a class.Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com0tag:blogger.com,1999:blog-3264940927634408517.post-77484288623610597942010-02-06T21:47:00.004+01:002010-02-06T22:12:53.786+01:00Followup on mocking frameworks for JavaSo, a week has passed and my mocking framework is fairly complete for a first release. All the information can be found on <a href="http://code.google.com/p/mockachino/">http://code.google.com/p/mockachino/</a> I expect some slight API changes in the near future, adding a few more (but not many) features and fixing some bugs (though I have no known at this time).<br /><br />I'd like to think that my experiment was a success, but how can I know how good it really is unless I get real users for it. It's a tricky situation. I personally think it has a better overall design than Mockito and mostly the same featureset, but generally you need to be significantly better for users to switch. I can't say I'm any different myself, why would I replace a library I use for a slightly better, if it would cost me time and effort to do so?<br /><br />So there are a couple of issues I need to work on before I can have an actual userbase:<br /><br /><ol><li>Make it better than Mockito. This is by itself hard, since Mockito is already a very good mocking framework. Of all the mocking frameworks I've seen, it's by far superior. So I need to have all the features that Mockito has, plus a lot more.</li><li>Figure out any realistic test usecases where Mockachino is better than Mockito. Given my knowledge of my own design and the design of Mockito, this should be doable to some extent at least.</li><li>Make converting from Mockito to Mockachino easy. If you have a large codebase you don't want to manually rewrite all your tests to change framework. Maybe it is possible to write a small application that can convert existing java tests to use Mockachino instead of other frameworks (EasyMock, Mockito).</li><li>Let people know it exists. This is hard. Word of mouth only goes so far. Some loose ideas include trying to make google rank the project site higher for relevant search terms, such as mocking and java. Also, I could inform tech bloggers that it exists so it can mentioned in articles that compare mocking frameworks.</li></ol><br />Of course, the technical challenge is by itself worth something, and I definitely feel I have learned from it.<br /><br />I guess I can sum up this entire entry in a single sentence.<br />If a code project falls in the internet forest and no one hears it, does it make a sound?Kristoferhttp://www.blogger.com/profile/09142743792457593145noreply@blogger.com1