Thursday, January 27, 2011

Movement in MMORPG games

Typical 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.

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.

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.

First, it is important to note that not all online games have the same requirements when it comes to character movement:
  • 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.
  • MMORPG:s need to handle hundreds of players in the same location, first-player shooters tend to support much fewer.
  • 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.
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.

Here come some of the tricks we currently use for Spaced.

Path compaction

Path compaction is the first step in reducing network traffic.
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.

Same state

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.

Compressed positions

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.

Compressed rotations

Character rotations (the facing) are represented as quaternions, with four double components in the range [-1, 1].
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.

Movement deltas

I think this the most interesting trick of the ones described.
Instead of sending the position each frame, we can just send the delta compared to previous frame!

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.

Start with size = ceil(log_2(max(x, y, z)))
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)

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.

Calculate the actual bytes to send as x_send = x * 127 / 2^size (and the same for y and z)

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).

But wait a second...

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!

That's true, but the solution is quite simple.
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).
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).

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.

Wednesday, January 19, 2011

Subversion and feature branches

I'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.

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.

Usual symptoms were crazy conflicts when merging from files not even touched in the branch.

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.

Basic rules to avoid pain:
  • Always stand in the project root (/trunk/ or /branches/branch/) when doing subversion operations.
  • Update often.
  • Commit often.
  • Sync trunk -> branch often.
  • Merge branch -> trunk only once, and then delete it.
Here are the general operations I use nowadays.

To create a branch:
svn copy TRUNK_URL BRANCH_URL

Start using the branch:
svn switch BRANCH_URL

List existing branches:
svn list BASE_URL/branches

Sync trunk to branch:
svn up
svn merge TRUNK_URL .
svn commit -m "Merged trunk to branch BRANCH"

Reintegrate branch (make sure it's commited and synced recently):
svn switch TRUNK_URL
svn merge --reintegrate BRANCH_URL .
svn commit -m "Reintegrated BRANCH"
svn delete -m "Deleting reintegrated BRANCH" BRANCH_URL

It doesn't look so hard, right?
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.

An annoying thing is all those URL:s you need to enter.
To simplify things for my most common usage, I wrote a simple bash script:

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.

Here's what it looks like:

And here is the actual script if anyone is interested.
#!/bin/bash

ERROR='\033[1;31m'
REPO='\033[1;32m'
CBRANCH='\033[1;33m'
COMMAND='\033[1;34m'
EXECUTE='\033[1;35m'
ENDCOL='\033[0m'

FULLURL=`svn info | grep -E "^URL: "| cut -d " " -f 2`
if [ "$FULLURL" == "" ]; then exit 1; fi
TRUNKURL=$(echo $FULLURL | grep -E -o "^.*/trunk")
BRANCHURL=$(echo $FULLURL | grep -E -o "^.*/branches/[^/]+")

set -e

function error() {
echo -e "${ERROR}$1${ENDCOL}"
exit 1
}

function execute() {
echo -e "> ${EXECUTE}$@${ENDCOL}"
$@
}

if [ "$TRUNKURL" != "" ]; then
if [ "$FULLURL" != "$TRUNKURL" ]; then
error "Please stand in the project root.\n Expected $TRUNKURL\n but was $FULLURL"
fi
BRANCH="trunk"
BASEURL=$(echo $TRUNKURL | sed "s/\\/trunk//")
elif [ "$BRANCHURL" != "" ]; then
if [ "$FULLURL" != "$BRANCHURL" ]; then
error "Please stand in the project root.\n Expected $BRANCHURL\n but was $FULLURL"
fi
BRANCH=$(echo $FULLURL | grep -E -o "[^/]+$")
BASEURL=$(echo $BRANCHURL | sed "s/\\/branches\\/$BRANCH//")
else
error "Could not determine trunk or branch from $FULLURL"
fi

function sync() {
if [ "$BRANCH" == "trunk" ]; then error "Must be on a branch to sync or reintegrate!"; fi
CLEAN=`svn status|grep -v "^\\?"`
if [ "$CLEAN" != "" ]; then error "Working copy is not clean. Revert or commit first!"; fi

execute svn up
execute svn merge $BASEURL/trunk .

UPDATED_FILES=`svn status|grep -E -v "^\\?"|cut -b 9-`
if [ "$UPDATED_FILES" == "" ]; then
echo "Nothing changed, skipping sync."
elif [ "$UPDATED_FILES" == "." ]; then
echo "Only trivial changes merge - reverting merge"
execute svn revert -R .
else
execute svn commit -m "Merged trunk to branch $BRANCH"
fi

}

case $1 in
switch)
if [ "$2" == "" ]; then error "Missing parameter to switch: branch"; fi
execute svn switch $BASEURL/branches/$2
;;
trunk)
execute svn switch $BASEURL/trunk/
;;
list)
echo -e "> ${EXECUTE}svn list $BASEURL/branches${ENDCOL}"
echo "Available branches:"
BRANCHES=`svn list $BASEURL/branches | grep -E -o "^[a-zA-Z]*"`
for b in $BRANCHES; do
echo -e " ${CBRANCH}$b${ENDCOL}"
done
;;
reintegrate|reint)
sync
execute svn switch $BASEURL/trunk
execute svn merge --reintegrate $BASEURL/branches/$BRANCH .
execute svn commit -m "Reintegrated $BRANCH"
execute svn delete -m "Deleting reintegrated $BRANCH" $BASEURL/branches/$BRANCH
;;
sync)
sync
;;
create)
if [ "$2" == "" ]; then error "Missing parameter to create: branch"; fi
execute svn copy $BASEURL/trunk $BASEURL/branches/$2 -m "Creating branch $2 from trunk"
execute svn switch $BASEURL/branches/$2
;;
delete)
if [ "$2" == "" ]; then error "Missing argument to delete: branch"; fi
if [ "$BRANCH" == "$2" ]; then error "Can not delete active branch. Switch first!"; fi
execute svn delete -m "Deleting branch $2" $BASEURL/branches/$2
;;
*)
echo -e "Repository: ${REPO}$BASEURL${ENDCOL}"
echo -e "Active branch: ${CBRANCH}$BRANCH${ENDCOL}"
echo "Usage: ./branch <command> [option]"
echo "Commands:"
echo -e " ${COMMAND}switch${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- switches to the branch"
echo -e " ${COMMAND}trunk${ENDCOL} -- switches to trunk"
echo -e " ${COMMAND}list${ENDCOL} -- list available branches"
echo -e " ${COMMAND}reintegrate${ENDCOL} or ${COMMAND}reint${ENDCOL} -- reintegrate active branch to trunk"
echo -e " ${COMMAND}sync${ENDCOL} -- syncs current branch with trunk"
echo -e " ${COMMAND}create${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- creates a new branch from trunk and switches to it"
echo -e " ${COMMAND}delete${ENDCOL} ${CBRANCH}<branch>${ENDCOL} -- deletes a branch without reintegrating it"
;;
esac

Thursday, November 11, 2010

Deep thoughts about deep mocks

A 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.

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.

Another problem with deep mocks was previously generics.
The following would fail in both Mockachino and Mockito:
static interface ListSet extends List<Set> {}
@Test
public void testDeepMockWithClass() {
ListSet mock = mock(ListSet.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}

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.

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.

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.

It would be much harder to support something like this:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(List<Set>.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}


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.
So we simplify it into this, which is valid Java syntax:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(List.class, RETURNS_DEEP_STUBS);
Set mock2 = mock.get(0);
}

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).

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:
@Test
public void testDeepMockWithClass() {
List<Set> mock = mock(
new TypeLiteral<List<Set>>() {},
fallback(DEEP_MOCK));
Set mock2 = mock.get(0);
}


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.

Friday, August 20, 2010

Random numbers without repetition

The origin of this problem comes from picking K elements from a collection of elements of size N (N >= K, obviously). If K = N, this is the same thing as shuffling, which can be done using the excellent Fisher-Yates algorithm in O(N). This algorithm can be used when K is smaller than N as well, you just have to disregard N - K of the elements. However, if K is very small and N is very large, this algorithm is quite far from optimal.

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 K is much smaller than N, this would work well, but if K was very close to N, you could probably end up doing far too many retries to be reasonable as soon as you start filling up the result.

Instead, you could use the original Fisher-Yates strike-out approach and simply stop after K elements. This could be done in O(K*(log(K) + K)), which can be simplified to O(K^2) with a naive implementation:

public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " +
n + " elements");
}
List<T> result = new ArrayList<T>(k);
SortedSet<Integer> offsets = new TreeSet<Integer>();

for (int i = 0; i < k; i++) { // O(K)
int off = random.nextInt(n - i);

for (int offset : offsets) { // O(K)
if (off >= offset) {
off++;
} else {
break;
}
}
offsets.add(off); // O(log(K))
result.add(source.get(off));
}
return result;
}


if K >= O(sqrt(N)), then the plain shuffle is better, but when K is smaller than sqrt(N), this approach would be the winner.

I wonder if it's possible to do it faster than O(K^2). 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 O(K*log(K)) instead which would be much better.

I experimented a bit by repeatedly running a binary search of the offset until the offset can not be incremented further. If N is large and K 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 O(K) times.

Does anyone know any good articles / papers / blogs about algorithms for picking K distinct random numbers in the range 1..N?

Update:

After having eaten lunch, I figured out how to make it run in O(K):

public <T> List<T> take(List<T> source, int k) {
int n = source.size();
if (k > n) {
throw new IllegalStateException(
"Can not take " + k +
" elements from a list with " + n +
" elements");
}
List<T> result = new ArrayList<T>(k);
Map<Integer,Integer> used = new HashMap<Integer,Integer>();
int metric = 0;
for (int i = 0; i < k; i++) {
int off = random.nextInt(n - i);
while (true) {
metric++;
Integer redirect = used.put(off, n - i - 1);
if (redirect == null) {
break;
}
off = redirect;
}
result.add(source.get(off));
}
assert metric <= 2*k;
return result;
}
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.

The while loop make look bad, but it never runs more than 2*K times in total.
(I haven't proven this formally, I just ran a lot of benchmarks on random input.)

If I were to prove it though, my general strategy would be that the loop is entered exactly K times, and you will follow at most K links, since only K links will be constructed and no link is followed more than once.

Update 2:
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).
public <T> List<T> take(List<T> source, int k) {
int n = source.size();
List<T> result = new ArrayList<T>(k);
Set<Integer> used = new HashSet<Integer>();
for (int i = n - k; i < n; i++) {
int off = random.nextInt(i + 1);
if (!used.add(off)) {
off = i;
used.add(off);
}
result.add(source.get(off));
}
return result;
}
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.

I see two significant differences with this approach.

The first (which is of the least relevance) is the amount of entropy used.
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.

Robery Floyd with an additional plain shuffle uses:
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.

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).
My algorithm on the other hand can be run partially and resumed without knowing the value of k at all.

Friday, August 6, 2010

Python annoyances - generators

Another annoyance in Python is generators. Since Python 2.5, the generator concept was extended to include coroutine support. (See http://www.python.org/dev/peps/pep-0342/ )
I for one think it's an odd design of coroutines.
Note that this comes from someone who is used to (and spoiled by) Lua's coroutines.

I have two problems with coroutines/generators in Python:

First of all, "def" gets multiple meanings. It's not just a function definition anymore.
It could also be a generator definition! And the only way to notice this is to
scan the entire function definition for a yield statement.

I would not have a problem with this if it wasn't for the case that generator
definitions and function definitions behave completely differently.
def gen():
return 123
I can call this with gen() and get 123 back. Simple!
def gen():
yield 123
If I call gen() now, I don't get 123 back, I get a generator object.
So I have to do this instead:
g = gen()
value = g()
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).

Let's compare it to Lua, which was the language that introduced me to coroutines:
-- Simple function call
function gen()
return 123
end
value = gen()

-- Using a generator / coroutine
function gen()
coroutine.yield(123)
end
c = coroutine.wrap(gen)
value = c()
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.

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.

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.
function resume(entity)
if not entity.coroutine then
entity.coroutine = coroutine.create(function()
return entity:runAI()
end)
end
coroutine.resume(entity.coroutine)
end

function Entity:moveTowards(x, y)
local dx = sign(x - self.x)
local dy = sign(y - self.y)
local dir = getDirection(dx, dy)
if dir ~= -1 then
TryMove(self.entity, dir)
coroutine.yield()
end
end

function Entity:moveTo(x, y)
while self.x ~= x or self.y ~= y do
self:moveTowards(x, y)
end
end

function Entity:attack(dx, dy)
local dir = getDirection(dx, dy)
if dir ~= -1 then
TryAttack(self.entity, dir)
coroutine.yield()
end
end

function Entity:chasePlayer()
while true do
local distance = self:distanceToPlayer()
if distance > 8 then
break
end
if distance <= 2 then
local dx = px - self.x
local dy = py - self.y
self:attack(dx, dy)
else
self:moveTowards(px, py)
end
end
end

function Entity:patrolTo(x, y)
while self.x ~= x or self.y ~= y do
local distance = self:distanceToPlayer()
if distance <= 5 then
self:chasePlayer()
else
self:moveTowards(x, y)
end
end
end

-- Populate world with deadly enemies
local entity = Entity:new(20, 10)
function entity:runAI()
while true do
self:moveTo(20, 8)
self:moveTo(20, 12)
end
end
addEntity(entity)

local entity = Entity:new(15, 15)
function entity:runAI()
while true do
self:patrolTo(15, 15)
self:patrolTo(15, 10)
self:patrolTo(10, 10)
self:patrolTo(10, 15)
end
end
addEntity(entity)

As you can see, each entity type can be written by using very high level
constructs, which themselves are defined by simple logic and calls to lower level
functions. This lets you write an AI as if it was running in its own thread,
but in reality, the game engine only calls the resume-function for each entity
on its main thread.

Without coroutines, you'd have to resort to writing a state machine instead,
which can be more painful to write and maintain.

Now, I've tried converting this to Python to see what it would look like.
This was my first iteration, which won't run because the generators itself
don't contain the actual yield-call.
def resume(entity):
if entity.coroutine == None:
entity.coroutine = entity.runAI()
return entity.coroutine()

class Entity:
def __init__(self, x, y):
self.x = x
self.y = y

def moveTowards(self, x, y):
dx = sign(x - self.x)
dy = sign(y - self.y)
dir = getDirection(dx, dy)
if dir != -1:
TryMove(self.entity, dir)
yield

def moveTo(self, x, y):
while self.x != x or self.y != y:
self.moveTowards(x, y)

def attack(self, dx, dy):
dir = getDirection(dx, dy)
if dir != -1:
TryAttack(self.entity, dir)
yield

def chasePlayer(self):
while True:
distance = self.distanceToPlayer()
if distance > 8:
break
if distance <= 2:
dx = px - self.x
dy = py - self.y
self.attack(dx, dy)
else:
self.moveTowards(px, py)

def patrolTo(self, x, y):
while self.x != x or self.y != y:
distance = self.distanceToPlayer()
if distance <= 5:
self.chasePlayer()
else:
self.moveTowards(x, y)

# Populate world with deadly enemies
class Runner(Entity):
def runAi(self):
while True:
self.moveTo(20, 8)
self.moveTo(20, 12)
entity = Runner(20, 10)
addEntity(entity)

class Patroller(Entity):
def runAi(self):
while True:
self.patrolTo(15, 15)
self.patrolTo(15, 10)
self.patrolTo(10, 10)
self.patrolTo(10, 15)

entity = Patroller(15, 15)
addEntity(entity)
Now, let's try refactoring until all yields are in the actual generator.
To do this, we could either simply inline all the functions that would yield,
until they're all in the runAi-method. The problem with this is a lot of
duplicated code, so that's not a good option.

Another way would be to only have the yields in the runAi, and let the currently
yielding functions return some value instead. The problem with that is that we
lose the knowledge of where to resume from, and thus we have to build some sort
of state maching to remember it, which would remove the point of having
coroutines in the first place.

If anyone can see a good way of refactoring that Python code (I am fairly new
to Python after all) to work as a coroutine, please let me know!

Until then, I'll just assume that python coroutines are inferior to Lua's. ;-)

[Here's an interesting article about coroutines: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf ]

Python annoyance - scoping

I 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.

One thing I stumbled over was a subtlety in the scoping that I didn't expect. Here's an example:
foo = 123
def fun():
print(foo)
fun()
print(foo)
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:
foo = 123
def fun():
foo = 456
print(foo)
fun()
print(foo)
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:
foo = 123
def fun():
print(foo)
foo = 456
print(foo)
fun()
print(foo)
I can think of two reasonable ways to interpret this:
  1. First print 123 (from the outer block), then 456 (creating a new variable in the function block), then 123 (outer block variable unchanged)
  2. First print 123 (from the outer block), then 456 (modifying the outer variable), then 456.
Instead, Python throws an error:
UnboundLocalError: local variable 'foo' referenced before assignment
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.

You can override this behaviour by doing this:
foo = 123
def fun():
global foo
print(foo)
foo = 456
print(foo)
fun()
print(foo)
This forces python to only refer to the outer variable instead of creating a new. This outputs 123, 456, 456.

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.

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).

Friday, June 18, 2010

Symmetric getters and setters

Using 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.

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:
  • Throw an illegal argument exception - if the ranges are clearly defined and the caller should know them, this is a valid approach.
  • Silently clamp the input value to be inside the range. This can sometimes be the desired approach, but it ultimately depends on the system.
  • 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.
There is a symmetry law which I think should hold for pairs of getters and setters.
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!

Anyway, here is the law:
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:

x = obj.getFoo();
obj.setFoo(x);
y = obj.getFoo();
assert x.equals(y);


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.

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.

for instance, you may have something like this:

public class Foo {
private final Bar bar;
public void setValue(int value) {
bar.setValue(value);
}

public int getValue() {
return offset + bar.getValue();
}
}

This is clearly asymmetric, so how do you fix it?
You could try something like this, but it's very prone to error, depending on how bar.setValue is implemented:

public void setBar(int value) {
bar.setValue(value - offset);
}


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()

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.