By Michael Powell

The IMVU Unity API makes heavy use of promises, to simplify asynchronous operations. Unfortunately, they’re different from the way things are normally done in Unity, and thus many people using our API have been understandably confused by them. The objective of this post is to alleviate that confusion. We first illustrate the problem we face without promises, then we explore a number of partial solutions, and finally we pull them all together to show just how powerful promises are.

Synchronous vs Asynchronous

The IMVU Unity API is focused almost entirely on loading things over the network, which really needs to be done asynchronously. To illustrate, consider this code snippet, which uses a hypothetical naive API:

class MyAvatar: LocalAssetLoader {
    void Start() {
        UserModel user = Imvu.Login();
        Load(user);
        // ... Do stuff to the loaded avatar
    }
}

That looks great! It’s super short, simple, and clean.

But there’s a problem. The call to Imvu.Login() can’t return a UserModel right away. This will, at the very least, require a few network roundtrips, which could easily take a second or two, and it may need to redirect the user to a website to go through the login flow, which could take minutes. The call to LocalAssetLoader.Load() will likewise take some time. It will kick off dozens of network requests, which in the optimistic case will take a few seconds to complete, and 10-20 seconds is pretty common.

The reason this is a problem is because, if we wrote the API this way, the entire program would be frozen waiting for these calls to complete. No frames would render. No user input would be read. It would feel like the program had crashed, because it’s just sitting there waiting for these calls to return.

This is what it means to execute code synchronously. It allows you to specify things in a simple sequence with guaranteed order. This makes it easy to reason about, which is great, and is why we do things synchronously when we can. However, it falls apart with slow operations. If the program is to remain responsive, slow operations need to be executed asynchronously. Unfortunately, asynchronous code is much more difficult to reason about, and it requires a new set of abstractions.

There’s another problem with the above code: It doesn’t handle failure. Both of those calls make network requests, and network requests can fail. So we need to do something like this:

class MyAvatar: LocalAssetLoader {
    void Start() {
        UserModel user = Imvu.Login();
        if (user == null) {
            Debug.LogError("Failed to log in for some unknown reason.");
            return;
        }
        bool loaded = Load(user);
        if (!loaded) {
            Debug.LogError("Failed to load avatar for some unknown reason.");
            return;
        }
        // ... Do stuff to the loaded avatar
    }
}

Well, that just got a lot uglier. Every one of these steps needs an error check after it, and we have no mechanism for getting any information on what actual failure occurred, so they can’t output very useful error messages.

Callback Hell

The most obvious approach to deal with asynchronous programming is to use callbacks, also known as continuation passing style, or CPS. When you call one of these functions that will take a while to complete, you also pass it another function. That function will be called when it’s done, with the result as its argument. For instance:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login(LoginCallback);
    }

    void LoginCallback(UserModel user) {
        Load(user, AvatarLoadedCallback);
    }

    void AvatarLoadedCallback() {
        // ... Do stuff with the loaded avatar
    }
}

Well, that’s a lot more verbose, but it’s still pretty comprehensible, right? Unfortunately, we have the same problem as before: No error handling. Thankfully, CPS provides a fairly straight-forward mechanism for handling errors. Instead of passing in one callback, you pass in two: a success and a failure callback. This also allows us to pass back an error condition, for better error messages. For instance:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login(LoginCallback, LoginErrorCallback);
    }

    void LoginCallback(UserModel user) {
        Load(user, AvatarLoadedCallback, AvatarLoadFailedCallback);
    }

    void LoginErrorCallback(Error error) {
        Debug.LogError("Failed to login: " + error);
    }

    void AvatarLoadedCallback() {
        // ... Do stuff with the loaded avatar
    }

    void AvatarLoadFailedCallback(Error error) {
        Debug.LogError("Failed to load avatar: " + error);
    }
}

It’s starting to get a bit complicated there, and this is one of the simplest possible examples. Now you’re getting a glimpse of what many programmers have come to refer to as “callback hell”. All of your code gets broken into tons of little functions, defined not by what they do but by where they fall in the execution flow. This makes it hard to trace the flow of execution. As you solve complicated, real problems, this quickly gets completely unmanageable. So let’s explore some ways to make this better.

Achieving Closure

Closures are a feature of C# (and many other languages) which tends to be under-utilized in Unity code. They’re a special case of lambdas, which are functions that are declared as an expression.

In code, lambda values don’t intrinsically have a name — which is why they are sometimes called “anonymous functions” — though they can be given one by assigning them to a variable. They’re usually small, one line functions, though they can be just as elaborate as any other function. In C#, they look like this:

Func<int, int> myLambda = (int a) => { return a*2; };
Debug.Log(myLambda(5));

There are a lot of things to dissect here, so let’s start at the beginning. Func is the type used for storing functions, which includes lambdas or normal methods. The last type parameter to Func is the return type, and the others are the argument types. So Func<string, float, int> can store a function with the signature int function(string, float). Note that if you want a function which returns nothing, you use Action instead. For instance, Action<string, float> can store a function with the signature void function(string, float).

The lambda syntax itself starts with the argument list, in parentheses, followed by =>, followed by the body of the function. Note that I wrote this in the most verbose way, for clarity. When C# already knows the function signature, you can omit the types from the argument list, allowing you to write:

Func<int, int> myLambda = (a) => { return a*2; };

Also, when there is only one argument and its type can be inferred, you can leave off the parentheses:

Func<int, int> myLambda = a => { return a*2; };

And finally, when the body of the function is just a single return statement, you can omit the curly braces and the return, and just provide the expression to be returned:

Func<int, int> myLambda = a => a*2;

Most of the places where lambdas are used meet all of these constraints: a single argument, of a known type, which just returns a single expression. So lambdas tend to be very compact.

Note that when you want to make a lambda which takes no arguments, you use () for the argument list, like this:

Func<int> myLambda = () => 5;

Now it just so happens that C#’s lambdas are actually closures. A closure is a lambda that allows you to access any variables that were in scope when the lambda was declared. For instance:

int num = 5;
Func<int, int> myClosure = a => a*num;
Debug.Log(myClosure(2)); // logs "10"

Notice that the closure uses the variable num in its body. When you do this, it’s said that it “closes over” num.

If you want to read more about C#’s support for lambdas, check out this MSDN article on the subject: https://msdn.microsoft.com/en-us/library/bb397687.aspx

So, let’s try using closures to make the earlier example less verbose:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login(
            user => Load(
                () => { /* ... Do stuff with the loaded avatar */ },
                error => Debug.LogError("Failed to load avatar: " + error)
            ),
            error => Debug.LogError("Failed to login: " + error)
        );
    }
}

This is a lot less verbose than the earlier example, and the flow is more ordered, but the nested closures are a little hard to read. Again, this is the simplest possible example. If we need to do anything much more complicated, this will still get unmanageable quickly, possibly even worse than the callback hell above.

We can do better, though closures will be very important to our solution.

Error Results

Let’s go back to our earlier examples, where we needed to do an explicit error check after each call, and examine a different problem that crops up there. The solution will introduce another class that’s broadly useful to us.

UserModel user = Imvu.Login();
if (user == null) {
    Debug.LogError("Failed to login for ... some unknown reason?");
    return;
}

The trouble is, those error checks are easy to skip. You may not even realize that a given call could fail. And every time you skip a necessary error check, you introduce a potential crash into your program.

But what if we had a type that could be a useful value OR an error, which makes it impossible to access the data without doing a proper error check? Sounds like a pipe dream, I know, but using closures we can simulate what’s known in computer science as a sum type with pattern matching, which gives us exactly what we’re looking for.

The IMVU Unity API provides this type, which we call Result. It’s generic over the type that it can store. So if you want to return a string or an error, you use a Result<string>. The key thing about Result is that you can’t just directly access the value it stores. You need to do so through a function you pass in, which will only run if the value is actually there to be accessed. This makes it impossible to access the value if it’s not present, which is what we mean by making it impossible to access the data without doing a proper error check. The most common way to do this is with the Match() function, which takes two functions as arguments. The first is given the value, if it exists. The second is given the error, if the value doesn’t exist. For example:

result.Match(
    value => Debug.Log("Success! We got: " + value),
    error => Debug.LogError("Error! " + error)
)

If we rebuilt our initial error handling example to work with Result, we’d get something like this:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login().Match(
            user => {
                Load(user).Match(
                    _ => { /* ... Do stuff to the loaded avatar */ },
                    error => Debug.LogError("Failed to load avatar: " + error)
                );
            },
            error => Debug.LogError("Failed to login: " + error)
        );
    }
}

That looks a lot like our closure example in the previous section, and it’ll have the same problem. This is one of the simplest possible examples, and it’s already looking kind of complicated. But, there’s something more interesting we can do here to make this better.

Railway Oriented Programming

The functions passed in to Match() can have a return type. Since only one of the two functions will actually be run, whatever that function returns can be returned by Match(). Note that both of them must return the same type for this to work, because Match() itself can only have one return type.

Now, imagine that our functions return another Result. That means we could call Match() on the return value of the previous call to Match(), instead of having to nest them. Let’s see what that looks like:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login().Match(
            user => Load(user),
            error => Result<Unit>.Err(error)
        ).Match(
            _ => { /* ... Do stuff to the loaded avatar */ },
            error => Debug.LogError(error)
        );
    }
}

Note that Unit is a placeholder type. It has no public constructor, and will always be null. It’s used here because Load() doesn’t have any useful data to return. The Result<Unit> in this case is just to represent the fact that Load() can fail, and capture the resulting error.

Anyway, that’s looking a bit cleaner. As we add complexity to this example, it will just add more calls to Match() to the sequence. It won’t increase the indentation, and won’t further separate the error handlers from the code that’s generating the errors. Let’s try something a bit more complicated, like loading the user’s first saved outfit:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login().Match(
            user => user.GetOutfits(),
            error => Result<OutfitCollection>.Err(error)
        ).Match(
            outfits => outfits.info.items[0],
            error => Result<OutfitModel>.Err(error)
        ).Match(
            outfit => Load(outfit),
            error => Result<Unit>.Err(error)
        ).Match(
            _ => { /* ... Do stuff to the loaded avatar */ },
            error => Debug.LogError(error)
        );
    }
}

Note that the error function in the first three calls to Match() just creates a new Result with the same error. This causes Match() to return the error, passing the buck to the next error function. Thus any error, regardless of which step generates it, will be handled by the Debug.LogError() in the last step. Also note that the type of the Result we create must match the type returned by the success lambda.

What you’re seeing here is the beginning of what’s known as Railway Oriented Programming (also referred to as chaining). Imagine you have two parallel railway tracks, which represent the flow of execution. One of them is the success rail, and the other is the failure rail. At each step of execution, we’re either on the success rail or the failure rail, and we can either stay on the same rail or switch rails.

In the example above, the call to Imvu.Login() starts our railway. It can start us out on the success or failure rails. If it’s on the success rail, we call user.GetOutfits(), and what it returns determines whether we stay on the success rail, or move over to the failure rail. If Imvu.Login() put us on the failure rail, then we choose to stay on the failure rail by returning a new Result with the same error. This is the first step along our railway. The next call to Match() is the second step. The second and third steps are similarly structured. If we’re still on the success rail when we arrive at the fourth step, then we’ve succeeded, and it’s time to do whatever we want to do with the avatar. If we’re on the failure rail, then it’s time to log whatever error we hit along the way.

Staying on the success rail can be thought of as the normal flow of execution. Switching to the failure rail is like throwing an exception. Every error callback in the railway can be thought of as catching an exception. When it packs the error into a new Result and returns that, we can think of that as re-throwing the exception.

This is a pretty typical example of a railway, where all steps but the last one do something interesting on the success rail that generates a new Result, but on the failure rail they just pass along the error. So having to always manually pass through the error generates a lot of boilerplate. This is why Result has another set of functions designed specifically for railways like this.

The first of these is Then(), which has overloads that take one or two arguments. The single-argument version takes just a success callback, and passes through errors automatically. The two-argument version takes both success and failure callbacks. The second function is Catch(), which takes a single failure callback. It passes through successes the same way the single-argument Then() passes through errors. Both Then() and Catch() always return a Result, and all of the callbacks passed into them must return a Result, which determines which rail you end up on.

So you can clean up the above example a bit using these functions:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login().Then(
            user => user.GetOutfits()
        ).Then(
            outfits => outfits.info.items[0]
        ).Then(
            outfit => Load(outfit)
        ).Match(
            _ => { /* ... Do stuff to the loaded avatar */ },
            error => Debug.LogError(error)
        );
    }
}

Well that’s now looking pretty nice. It’s very easy to follow the sequence of actions we take, and we don’t even have to think about error handling beyond having the single log statement at the bottom.

Note that the last step in the chain uses Match() instead of Then(). This is because Then() requires the lambdas to return a Result, so that Then() can itself return a Result. However, our lambdas in that last step don’t return anything. So we need to use Match().

Going Asynchronous

The problem is, Result is still synchronous. It’s given a value or an error in its constructor, and then when Match() or Then() are called, the appropriate callback is immediately called. There’s still no opportunity for slow network requests.

However, everything is being handled through callbacks, so it should be possible to build something similar to Result, but which allows for asynchronous behavior, right? Well, yes, in fact. That’s exactly what Promise is!

A Promise is like a Result, except the value it represents may not exist yet. It’s a promise to deliver that value. When it’s given a value, the promise is said to be accepted. If it fails, it’s said to be rejected. Either accepting or rejecting the promise is considered to be resolving it, and when it’s resolved the appropriate callbacks will be called. If the Promise is already resolved when the callbacks are registered, then they’re called immediately.

The API for using a Promise is nearly identical to Result. In fact, the actual API, which uses promises, looks like this:

class MyAvatar: LocalAssetLoader {
    void Start() {
        Imvu.Login().Then(
            user => user.GetOutfits()
        ).Then(
            outfits => outfits.info.items[0]
        ).Then(
            outfit => Load(outfit)
        ).Match(
            _ => { /* ... Do stuff to the loaded avatar */ },
            error => Debug.LogError(error)
        );
    }
}

That is character-for-character identical to our last example.

There are some differences between Promise and Result, though. The callbacks passed to Then() or Catch() on a Promise can return either another Promise, or a Result. If they return a Result, it will be converted into an equivalent Promise. Also, Match() on Promise can’t return anything, because the callbacks passed into it may not run immediately, so it doesn’t necessarily have a value to return. If you wish to return something from a Match() on a Promise, use Then() instead, which will allow you to return it in another Promise.

Also, and this is possibly the most important difference, you must account for the fact that the callbacks do not run synchronously. For instance, consider this broken code:

class MyAvatar: LocalAssetLoader {
    void Start() {
        UserModel userModel = null;
        Imvu.Login().MatchValue(
            user => userModel = user
        );
        string name = userModel.info.name;
    }
}

If the user isn’t already logged in, this would generate a null reference exception. This is because the lambda passed in to Imvu.Login().Then() doesn’t run right away. We’re setting it up to run later, when the login completes. So when we try to access a field on the userModel immediately after we set that up, it’s still null.

Conclusion

When designing this API, we considered many different options that we dismissed:

• Continuation Passing Style – We dismissed this because it turned into callback hell.
• Coroutines – We examined Unity’s coroutines, which are specifically designed to handle asynchronous cases cleanly. They’re quite nice. Unfortunately, they’re only usable within a MonoBehaviour, and we needed to be able to run asynchronous code from anywhere. We considered implementing our own version of coroutines using roughly the same syntax, but that was too large an undertaking.
• async/await – C#’s async and await keywords bake an even better version of coroutines into the language. They look great, but it turns out Unity’s version of C# doesn’t support them yet.
• Threads – This would allow you to write something like the synchronous example at the top of this article. However, it has some major problems. First, threading doesn’t translate to WebGL at all, so if we relied on threading it would fall apart on one of the major platforms we’re targeting. Second, developers using the API would be forced to write code that goes into threads, and threading is infamously error prone and difficult to get right. We’d rather not put that burden on our developers. Third, it would be difficult to load an avatar on a thread, because only the main thread can interact with the GPU. There are ways of working around this, but combined with the other problems it wouldn’t be worth it.

So given all of this, promises are the best way we could come up with for handling the heavily asynchronous code our API demands. We understand that they’re confusing at first, particularly to programmers unaccustomed to working with lambdas and asynchronous code. However, hopefully you now have a stronger understanding of how they work, and why they’re necessary.

Further Reading

• Railway Oriented Programming – This is a slide deck that introduces the railway metaphor in a lot more detail, from the perspective of F#.
• How do Promises Work? – This is a deep dive into the underlying mechanics of promises, as they’re implemented in JavaScript. Our promises are very similar in principle, but have a slightly different API.
• You’re Missing the Point of Promises – A critique of some promise polyfills common in JavaScript, which goes into detail on some often-missed points about what makes promises really useful.
• Promises are the Monad of Asynchronous Programming – This is a more advanced article discussing the relationship between promises and monads. This provides an alternate viewpoint on promises for those familiar with monads.

By Llorens Marti Garcia

We’ve been actively working for almost 3 years on IMVU’s new 3D engine called Northstar, which is written in C++ for performance and portability, and compiled to many platforms, including the web using Emscripten.

Because Test Driven Development (TDD) has demonstrated over the years that we can write software in a more robust and efficient manner as well as with higher quality, our 3D engine has a lot of unit tests trying to cover as many features as possible over more than 100K lines of code.

Problem with Unit tests

With this scenario we recently noticed something interesting about TDD. What happens if after hundreds of thousands of lines of code and thousands of unit tests the rhythm of adding those test for new code decreases? The Answer is simple, the quality of the code decays, the probability of future bugs increases or worse, the ability to re-factor some code ends up being more challenging.

IMVU tried to solve the problem in the past with code coverage tools. These tools help, but they do not give the full picture in some scenarios, such as when a test calls one function that executes big portions of the code in one test. Here I want to explain how we attacked the problem from another point of view.

While looking at some source files of our 3D engine, our initial question for testing the quality of our tests was: If we remove this line from this source file, will the tests yell at us because it is missing?

We found this initial idea very interesting. First, we are not testing if the tests cover the code but if there was any test testing a feature related with this removed line of code. And second, the process can end up giving us a list of lines to look at, which is very handy to detect missing tested features. We can find more about Mutation testing and how it help us to find these deficiencies here.

Overview of the solution

We use Git for a source control. C++ is the main language of the project. We use Python for the framework that drives code testing. Additionally, our commit history is as linear as possible inside our repository.

This is a quick overview of the solution we implemented:

1.- Git pull 3D engine code
2.- Checkout commit with hash X
3.- Git submodule update
4.- Get the diff text between commit X~1 and X
5.- Parse the diff and extract all the added lines in commit X
6.- For every line from the step 5:
6.1.- Decide which kind of mutation we will attempt.

// for a normal line we select:  // —  (a commented line)

// for an if (…) line we select if (true) {  and if (false) {

// for a for (…;…;…) we select for (…; false; …) {

// for a for (… : …) (explained below)

7.- For every line and its substitution line/lines:

7.1.- Find the the original line in the code

7.2.- Substitute the original line with the substitution line

7.3.- Build Northstar

7.3.1.- If the build fails, we return because this line was necessary.

7.4.- Build Run Northstar tests

7.4.1.- If at least one of the tests fail, we return because this line was necessary.

7.4.2.- If the tests hung, we treat it as if the tests failed. (see later)

7.5.- If both 7.3 and 7.4 finished with OK then the original line was not covered by any test

8.- Compute % between all the lines tested and all the lines not covered.

Details of the solution and some tips

Many parts of the algorithm above can be tricky:

1.- Git diff (step 4)

What we want is to know is the exact diff between commit X and the commit before it. With this in mind, it is important to have a commit history as linear as possible. Using git rebase often may do the job (we default git pull to use the -r option). In case we don’t have a linear history, then the operation ‘git diff X~1 X’ will give us inaccurate code to test. This can happen when, for example, we are asking for a diff between a normal commit and a merge commit.

2.- Line substitution (step 6.1)

Here comes one of the trickiest part in this project: trying to parse C++, understanding it, and replacing the code by one specially crafted for the occasion.

The most common case is replacing a normal C++ line of code with a blank line (or a comment line ‘//—’ in case we are debugging). The problem with this approximation is that it does not work everywhere. For example, what happens if the statement line is split across multiple lines? In our solution, we use a combination of regex helpers and more complex C++ parsers.

With conditionals, what we want to do is force them to be active or inactive, this is why when we find an IF statement, we replace them with two possible lines: ‘if (true) {‘ and ‘if (false) {‘

This two scenarios tell us if there is any ‘test’ exercising the opposite of the line we are mutating.  For example, if we substitute ‘if (true) {‘ and after compiling the project and running the tests everything is reported as OK, then we can be sure that no ‘test’ covers the feature that is represented in code by this IF statement.

In the same way, when we find a FOR statement, we replace it depending on the type:

A normal FOR statement will be replaced by:

     for(;false;) {

A C++11 FOR statement with the form for(<variable> : <container>) will be replaced by:

for(<variable> = *(<container>.begin()); false; ) {

These are some methods of replacing IF and FOR statements to force them to be disabled or not. Again, keep in mind that parsing C++ is very difficult, and this code can be improved in many different ways.

A special point about FOR statements: There is the possibility that we will replace a line of code inside the body that will make it loop forever. This is why we have a timeout while running the tests, because they may hang forever. If this is the case, wes hould treat this scenarios as if the tests failed when run.

3.- Removing lines (inside step 6.1)

There are many lines we can ignore testing; this is because we know that the code will fail to compile if we remove them. For example, rules like:

• Line only contains ‘{‘ or ‘}’
• Line starts with a common type: int, float, double, char, etc.
• Line starts with ‘class’ and ends with ‘{‘
• Line starts with #include
• …

As we can see, we can improve the time of testing a given commit by not testing those lines that will make the compilation to fail or their value is not interesting for us, like ‘#include’.

4.- Parallelization

Due to the nature of these code testing, the process is highly parallelizable. For a given project and a given commit of that project, given N lines we want to test, each of those lines can be tested on a separate machine.

Examples

1.- Simple function

Fig 1: Function onDetach examined

If we look at Fig 1, we can see some interesting output:

Line 107: If we mutate that line to a comment line, any test will fail.
Line 109: Not tested IF statement.
Line 115: Not tested FOR statement.
Line 117: Not tested IF statement.
Line 118: Line mutated to a comment, any test fail.
Line 121: Line mutated to a comment, any test fail.
Line 124: Line mutated to a comment, any test fail.

The main idea behind this output about onDetach() function is that we are lacking tests for the behaviour of this function. We are not testing the reset of the mesh component. We are neither testing what happens if bonesAsGameObjects is empty. Also we are not testing that when calling onDetach(), we reassign GameObject children.

In the images below, we can see how the algorithm changes the original code (Fig 2) with some mutations (Fig 3 and 4).

Fig 2: Original file.

In Fig 3 we can see how line 107 mutated to a commented line. After this change, the source code is compiled without any errors and all the tests finish without any problem. Because of this, line 107 is detected as a line that needs to be tested, and is marked on Fig 1.

Fig 3: Line 107 mutated to a comment.

meshComponent_ is a weak pointer to a mesh component, and when we detach the skeleton component, we want to reset this weak pointer.

By not doing it, we will end up with a skeleton component already detached from a Game Object that still can have access to a mesh component. The meaning of this line is to prevent detached components to have access to previous neighbour components. If we don’t test that line and someone remove it, we can have weird scenarios where detached components still affects current components.

In Fig 4 we can see how line 109 mutated to a if (false) {. After this change, the source code is compiled without any errors and all the tests finish without any problem. Line 109 mutation denotes there is no test exercising that if bonesAsGameObjects_ is empty, we remove the first child. Because of this it is marked with red on Fig 1.

Fig 4: Line 109 mutated to if (false) {

2.- False Negatives

While testing with this tool, we can have false negatives scenarios, and here is an example:

Fig 5: False negative

In figure 5,  we can see a DomainBase object that appears to be completely tested. The problem here is that we don’t have any test for that class. What happens is that because DomainBase is used by other classes on the project, if we mutate any line, other tests will fail because of the mutation.

This does not means that DomainBase is robust, it only means that the code that is using DomainBase is not exercising any exploit on it.

3.- False positive

Fig 6: False positive

Normally we can find false positives iin these lines of code that tries to optimize memory for some algorithm. A good example is reserve() from a std::vector. These lines can be removed, and build and testing processes will not become affected. This is because reserve() makes memory access more performant but in any case it change the behavior of the algorithm. To prevent these kind of false positives we can add filters to avoid any mutation in these lines.

Conclusion

The most important idea of this project is the ability to spot areas in the source code that need mutation testing. This project has already found many bugs in our source code, including dead code and code that was forgotten and not compiled.

The way we found that some code was not compiled at all was because our tool was marking the constructor declaration line of one class as a discardable one. Here we can see the affected class:

Fig 7: Not compiled code.

If we think about it, how can this class be compiled if we mutate the line 11 with an empty line. After some investigation we discovered that this class was removed from the build process script.

We also noticed that in large code bases, some files are tested not by its own tests but by the code that it is exercising it. This means that the code is safely tested only while it remains in the actual project and with no major changes. A good move to solve this problem is to not compile the whole project for testing a line but instead to compile only the tests associated with the file we are modifying.

Something that still requires work is the speed of getting the test results. Currently it takes minutes to get feedback about one given commit, and this disrupts the development iteration cycle. This can be fixed by,for example, parallelizing the process with more build machines.

We find mutation testing to be highly valuable, and I hope this idea can help other engineers deliver solid, well-tested code.

In this 3-part series, IMVU senior engineer Bill Welden describes the means and technology behind IMVU’s web services.

Part 2: Nodes and Edges

The Uniform Contract constraint of the REST discipline means that IMVU web applications are able to provide functionality to many different web applications in a robust and reusable manner.

There are, of course, many different ways of implementing a uniform contract. At IMVU, we have chosen a structured network model – a graph consisting of nodes, which represent the objects of interest to our users, and edges representing the relationships among those objects. The functionality of our web services is then framed in terms of inspecting and manipulating this graph.

For example, here is a network diagram showing some high school enrollment data.

Two students, Jan and Chris are each enrolled in two classes. They are both in the same Algebra class, but in different English classes.

Each of the students, and each of the classes are represented by nodes, shown here as circles. The relationship between the students and the classes are represented by edges, shown here as lines connecting the circles.

Nodes come in different types. In this diagram we have student nodes and class nodes connected by edges representing course selections.

Nodes have properties, and the type of the node determines the properties. Each student, for example, has a name and an age. Each class has a starting time.

All of the nodes of a given type constitute a node group. This example has two node groups so far, one for students and one for classes. The node group determines the properties of the nodes in the group.

Node groups are important — they distinguish a structured network model from an unstructured one. Network models are usually assumed to be unstructured, where any sort of data can be associated with any node. In fact, data and links are often intermixed, as in a hyperlinked network of text documents.

IMVU REST services are built on a network model, but a structured one, where every node belongs to a node group, and it is the node group – not the node – that determines the specific properties found in each node. In this way, a structured network model is like a relational data model.

Let’s add some teachers.

Janos teaches the 10 AM Algebra class and Mariska teaches both of the English classes. It is useful to group the edges, as they attach to the node, into edge groups:

All of the edges in an edge group attach, at the opposite end, to the same type of node. Each class node, for example, has two edge groups: one for students and one for teachers.

Because edges create relationships between nodes, the edge groups are sometimes named according to the role that the links play. Here we call the edge group listing the students in the class the “roster”, and the symmetrical view the student’s “schedule”. More often, though, edge groups are named simply by the type of node they link to, as with “teachers” here.

We will see later that edges are implemented using directional links – but the edges themselves are not directional, and can be viewed from either end. Jan is enrolled in Algebra and Algebra has Jan as a student.

Nodes have properties, but edges can also have properties. The number of times the student has been late to class is a property of the edge between the student and the class. It is not a property of the student, because the student will have many classes and may not be late to all of them, nor is it a property of the class, because many students will be enrolled in the class, and not all of them will be late.

The edge group determines what kind of node is at the other edge, whether the node has properties, and if so what the properties are.

We model node groups, nodes, edge groups and edges using JSON documents served over HTTPS, and link them using URLs. In my next post, I will go into detail on the structure of these URLs and documents, and follow through on the high school enrollment example.

Up next: Part 3 — Documents and Links