Sunday, 6 May 2018

Improving unit tests with equivalence instead of equality for URLs

Like any good developer I try to ensure that my code is not just covered with unit tests, but that they are meaningful. However I often find that my tests would break because they made too many assumptions about the implementation of the code it was testing. In this post I'm going to be using the example of testing URLs, but this approach can be taken more generally. When working with web services I often find myself writing code that takes an model object and produces a URL request. So naturally I'll write unit tests for this conversion and typically I would have written something like below, were for a given input I check the output URL is equal to what I expect.


For simple cases this works fine, but as things get more complex I would find my tests would become very fragile because the order of the query items could change. This might be because I had used a Dictionary or a Set were the order of the elements is not guaranteed. Indeed even in the simple case above my test makes implicit assumptions about the implementation. The is no reason for firstname to be the first item in the query string, the URL would still be perfectly valid if the order of the items were rearranged or indeed if any of the characters in the URL were percent encoded. My unit test is highly coupled to the specific implementation of my function. Now in this trivial example that may not matter too much, however as things get more complex this coupling leads to unit tests that are brittle. At the root of this brittleness is the equality assertion. When an object (such as a URL) can have multiple alternative but equivalent forms then using equality leads to implementation coupling.


Escaping the tyranny of exact equality

To break this coupling, I've used the concept of Equivalence that will test if two objects are alternative forms of each other. I've created a protocol Equivalent that is modelled after the Equatable protocol in the standard library. Using the triple-bar operator (≡) as the equivalent-to operator. With this we can have types conform to the Equivalent protocol were they have alternative forms.



Equivalence for URLs

Now that we have the Equivalent protocol we apply it to URL. In the below code I use the URLComponents class to do much of the heavy lifting. This implementation will account for the following alternative forms:-

  • Query item order independence.
  • Percent encoding alternative forms.
  • Default port numbers.
  • Relative paths.


Writing equivalent unit tests

For consistency with the rest of the unit tests I wrote a function XCTAssertEquivalent similar to XCTAssertEqual, as it's name implies it uses equivalence rather than equality (see the attached playground for the code). The original unit test changes to the following.

Not much has change with the code of the test, however now the test is far more flexible on testing the output of the function and therefore less coupled to the implementation.

Playground file available here.

Wednesday, 21 March 2018

Tracking down bugs using git bisect with Xcode unit tests

Overview

When working on software projects, fixing bugs is an inevitable fact of life. Sometimes you're lucky and the nature of the issue is obvious, however other times tracking down the source of the issue can be a time consuming and laborious task. If your project is using git for source control, then git bisect can be used to track down the commit that introduced the bug. Hopefully by narrowing the focus of investigation to the changes within a single commit, finding the root cause is significantly easier. This is especially true if commits within your project are small and focused.

Git bisect works on the basis of giving a known bad commit (were the bug is present, such as the current head) and a earlier good commit (were the bug is not present). The command works by switching into a special bisect mode were git will checkout a commit and the user will label that commit as good or bad. Git will then checkout a new commit and the process continues until git has determined the first bad commit. For those interested git uses a binary search of the commits in between the initial good and bad commit. So not every commit in-between the initial starting points will be checked. We enter bisect mode by running the following from the terminal: -

$ git bisect start [bad commit] [good commit]

Once in bisect mode, git will checkout a commit for us that we need to label as either: -
  • good – The bug is not present.
  • bad – The bug is present.
  • skip – It could not be determined if the bug was present, such as the project failed to compile.

$ git bisect good | bad | skip

After labelling the commit git bisect will checkout a new commit and the process continues until the first bad commit is found.

Automating the process

This works, however this requires user interaction to determine if the bug is present within a given commit. Instead let’s consider writing a unit test that will determine that for us. That way we could set the whole process in motion and git bisect could determine the first commit in the range that causes our unit test to fail. Git bisect has a command to run a shell command to automatically label a commit.

$ git bisect run [cmd]

The exit code of the shell command is used to determine the label for the commit.
  • Exit Code 0 - good
  • Exit Codes 1 through 127, excluding 125 - bad
  • Exit Code 125 - skip
Apple has documented the process of running unit tests from the command in Automating The Test Process using the xcodebuild command. For those interested Apple's Building from the Command Line with Xcode FAQ is also a good source of information.

The last piece of the puzzle is how to run a unit test that was not part of the project in the past and therefore when git performs a checkout the test will not be present. The simplest method I found was to create a stash of the changes to add the unit test into the project. That way we can apply the stash after each checkout, but before running the tests.

To make running the unit test easier we'll write a shell script to build and run the test target.


You'll notice that the script separates the steps of building the test target from running the unit test. In an ideal world each commit in your project would compile and run. However the reality is that some commits may break the project and fail to build. In these situations we exit the script with status code 125 which git bisect will interpret as the skip command. This will get us to carry on our search, at the cost of potentially making the end result less focused. Additionally the script uses the -only-testing argument to xcodebuild to only run a specific unit test rather than all of them.

Example

If like me you find a worked example easier to digest. Let's use a small, if somewhat contrived example. You'll need to suspend your sense of disbelief here as the source of the bug will be some what obvious. However the aim of the exercise is working with git bisect not fixing this particular issue. 

Git commit graph showing the main develop branch and 3 feature branches that are split off and later merged back to develop
This demo project can be found on GitHub here. The project is an iOS app, that has a simple slider control for numbers between 0 and 10 and a label that will report the current value as well as the sum and average of all integers between 0 and the current value.

To makes things a little more realistic within the repository I have created a main develop branch and 3 feature branches that are created from develop before being reintegrated.

At some point in the development a bug was introduced such that if the slider is at position zero the app will terminate. This did not occur initially so let's use the technique above to determine the commit that introduced the bug.























We start by writing a unit test that can be run to determine if the bug is present.



Next we stash this change so that it can be applied for each checkout.

$ git stash save "unit test"

We can then start the git bisect session with the given bad and good commits. Then issue the command for git bisect to run the script automatically.

$ git bisect start 08a7cbf 664b6a1
$ git bisect run ./bisect-unittests/BisectDemo/unittest.sh

The process will take off and after awhile the following printed out: -

fb4b22d is the first bad commit
commit fb4b22d
Author: Raymond McCrae
Date:   Tue Mar 20 20:06:39 2018 +0000

    Refactor Utilities.average



bisect run success


Looking at the commit the following method

was changed to

During the refactor a bug was introduced that an empty array will cause a division by zero causing the crash. It is worth pointing out that despite giving the initial range of commits from the develop branch, the commit git bisect identified is on feature/3 branch. Clearly git bisect will follow all paths in between the initial commits not just a simple straight path along the current branch.

Finally we can leave bisect mode by running: -

$ git bisect reset

Since we have a unit test we can include it with any fix that we make to the code to ensure that this type of bug is not made again.

Conclusion

Git bisect is a powerful tool, especially when combined with automation. It is however more suited to finding regressions were we had a previous good state and now things are broken. I have used unit tests in this post, however it would also possible to you UI automation tests instead.

Monday, 12 February 2018

Automatic summarization of articles in Swift

One of the features of Mac OS X that has intrigued me was the Summarize service that has the ability to generate a summary of a larger piece of text. In more recent versions of the OS this needs to be switched on in the System Preferences. This is an example of a technique called Automatic Summarization. I thought it might be fun to try and perform a similar task in Swift. This is not an attempt to perfectly recreate the exact logic Apple used, but instead how similar results can be achieved with some basic NLP processes.


While there are many ways to achieve this goal, to keep it simple I'll use an approach called document summarization. That builds a summary from the k most important sentences within the text without modifying them, where k is an input variable of the user's choosing for controlling the length of the summary. This works on the principal that a few key sentences can get an overview of the text as a whole. Ok, so how do we know which are the most important sentences? Well based on the observation that the most important topics of an article are often the most repeated, we can build a dictionary of the word frequencies (a count of how many times that word appeared within the article text) and from that we can compute a ranking score for each sentence by adding up the frequencies of the words the sentence contains. Finally we can string together the k highest scoring sentences to form our summary.

Let’s take this one step at a time using this article on recent US policy changes to the ISS from the Washington Post as an example. The first step is computing the word frequencies. To do this we need to break up the text into the individual words.  Fortunately, there is a Foundation class to do just that, NSLinguisticTagger which will enumerate all the tokens in a string. Tokens can be words, punctuation or whitespace. However for our purposes we are only interested in the words, so we specify the options omitWhitespace and omitPunctuation to only deal with the words. The joinName option is used to combine names that have multiple words in to a single token, such as treating New York as a single token rather than two separate tokens.


The following table lists the 10 most frequent words found in the article.

Word Frequency
the 66
to 33
of 24
and 18
station 15
that 15
a 13
in 12
said 11
it 10

There is a problem here. The table is dominated by words that are unimportant to the meaning of the the article. Languages like English often have many words like "the" and "a" which are important for the grammar of a sentence, but are not important to picking out the main themes of an article. If left in the word frequency values then they would dominate the rankings, skewing the score of sentences. Such words are called stop words and we can filter them out. There is no standard list of stop words, so I will use Google's stop word list for English. Let’s update the approach to filter out the stop words from being counted in the word frequencies. We store the stop words as a Set of Strings and check for a given word that it is not contained in the set before incrementing the word frequency.


The following table lists the 10 most frequent non-stop words in the article.

Word Frequency
station 15
nasa 10
commercial 8
space 7
iss 6
private 6
will 5
international 4
document 4
transition 4

This looks much better with more of the words representing important terms and themes in the article. Next we need to identify the sentences, here again NSLinguisticTagger comes to the rescue. In addition to receiving the token range, the closure passed to enumerateTags also gets passed the range of the containing sentence. We can track the sentences as we enumerate the tokens.


Then we can compute the ranking score for each sentence by summing the word frequencies of each word in the sentence.

The following table lists the 3 highest ranked sentences for the article.

Sentence Ranking Index
Last month, as reports circulated about NASA pulling the plug on the station, Mark Mulqueen, Boeing’s space station program manager, said “walking away from the International Space Station now would be a mistake, threatening American leadership and hurting the commercial market as well as the scientific community.” 80 20
The transition of the station would mark another bold step for NASA in turning over access to what’s known as low Earth orbit to the private sector so that the space agency could focus its resources on exploring deep space. 72 23
In its budget request, to be released Monday, the administration would request $150 million in fiscal year 2019, with more in additional years “to enable the development and maturation of commercial entities and capabilities which will ensure that commercial successors to the ISS — potentially including elements of the ISS — are operational when they are needed.” 72 7

Having found our most important sentences we string the k most important sentences together in the order they appeared within the original text. It is important to keep the original order of the sentences when reforming the summary. Otherwise the result can look disjointed.

For our example article and for a value of k equal to 3, the following summary is generated.
In its budget request, to be released Monday, the administration would request $150 million in fiscal year 2019, with more in additional years “to enable the development and maturation of commercial entities and capabilities which will ensure that commercial successors to the ISS — potentially including elements of the ISS — are operational when they are needed.” Last month, as reports circulated about NASA pulling the plug on the station, Mark Mulqueen, Boeing’s space station program manager, said “walking away from the International Space Station now would be a mistake, threatening American leadership and hurting the commercial market as well as the scientific community.” The transition of the station would mark another bold step for NASA in turning over access to what’s known as low Earth orbit to the private sector so that the space agency could focus its resources on exploring deep space.
The full source for this post can be found on Github as a swift playground. There are many methods of performing automatic summarization, this approach was chosen primarily on simplicity, however there are many other approaches that can give more optimal results.

Saturday, 13 January 2018

Using sqlite3_analyzer to identify space usage with Core Data

When using SQLite as the backing store for your Core Data persistence store it's easy to take a hands off approach. However lifting the lid on that abstraction can provide useful insights on its effectivness. If you are wondering why the database file seems to have grown beyond your expectations or just have a general interest in digging deeper then this post is for you.

Analysing the database

One of the tools the SQLite project develops is sqlite3_analyzer to measure the efficiency of space used by individual tables and indexes within an SQLite database file. There are precompiled binary versions of the sqlite-tools available for the mac on their download page.

Update - The precompiled binary available from the SQLite web site works on macOS Sierra, but fails on High Sierra with the following error:-
dyld: Library not loaded: /System/Library/Frameworks/Tcl.framework/Versions/8.4/Tcl
  Referenced from: /Users/raymond/Downloads/sqlite-tools-osx-x86-3210000/./sqlite3_analyzer
  Reason: image not found
Abort trap: 6
This is because High Sierra ships with version 8.5 of the Tcl framework. Of course you could compile your own version of the tool from source to resolve this, but for simplicity we can update the executables rpath with the following command:-
install_name_tool -change "/System/Library/Frameworks/Tcl.framework/Versions/8.4/Tcl" "/System/Library/Frameworks/Tcl.framework/Versions/8.5/Tcl" sqlite3_analyzer


I'd previously written about finding the underlying sqlite database file here.

So what does sqlite3_analyzer give us, let's use an example by creating a database via Core Data, with a entity Person and add 1 million entries into the database. sqlite3_analyzer gives a lot of information, so i've included only an extract of the overall output here.


The report starts with statistics for the overall database file and then breaks down in to sections for each table and index. For this discussion let us constrain ourselves to the top level information of the overall database. The report contains a handy definitions section at the bottom in case you require a more verbose description of each term in the report.

The section "Page counts for all tables with their indices" is very useful to see which tables are using most of the space within the file. In this example we can see the ZPERSON table is consuming 99.84% of the overall file. The other tables prefixed with Z_ are used by Core Data to store metadata. Therefore things are looking pretty healthy in this database.

Vacuuming the clutter

One of the aspects of SQLite when deleting data is that the file size of the database does not reduce. Instead the released space is marked as been available for reuse. This makes sense as the general case of application use will cause the growth to plateau, as the inserts and deletes reach a state of equilibrium. However under special use cases where large fluctuations in the quantity of data occur, the database can be left consuming significantly more space than required. To resolve this problem SQLite has the VACUUM command. This will cause the database to be repacked to used the smallest possible space required. It is worth noting that during the process of vacuuming SQLite will temporarily copy the database, therefore as much as twice the size of the original database file is required in free space in storage.

Let's demonstrate this by deleting 30% of the data from Person in our demo database. Notice "Size of the file in bytes" remains unchanged, however "Pages on the freelist" has jumped to 29.7%.


So far we've talk purely at the SQLite level, inevitably the next question becomes how can we use the vacuum command via Core Data within our applications. Fortunately Apple has us cover in the form of the persistent store option NSSQLiteManualVacuumOption. When specified as part of the options on the NSPersistentStoreDescription will cause a full database vacuum operation to be perform when opening the persistent store.




Finally we run the sqlite3_analyzer report again after the vacuum operation. We can see the file size is now 29155328, a reduction of 36% from the original size. Additionally the values for "Pages on the freelist" are now back to zero indicting all the space within the file is in use.

Thursday, 28 December 2017

Exploring Core Data database with sqlite3 on command line

Core Data abstracts a lot of the low level details of storage away for programmers, and that’s a good thing however sometimes it’s useful to lift the lid and see what’s happening beneath. For this post I’ll be specifically looking at the SQLite persistent store, I’ll assume you already have an app using Core Data and want to glean more insight into the inner workings. Fortunately the mac comes with a command utility to open and explore sqlite databases (sqlite3), but before we can delve into the database file, we must first find the file.

Finding the database file for an iOS App
The easiest way to look inside the database file is by running your app within the iOS Simulator for Xcode. The simulator stores all of its file structure within a directory on your mac. The trick is finding it. By default the simulator will store its files in Home Directory ▷ Library ▷ Developer ▷ CoreSimulator ▷ Devices. Normally the Library folder is hidden to prevent users mucking things up, however you can access Library from the Go menu in Finder by holding the option key down while displaying the menu.



However since we’re starting to perform some advanced techniques it may be easier to perform these actions on the command line, therefore open Terminal and type the following to perform a search of all the simulator devices for a file with a given name (you can substitute the file name for your own):
find ~/Library/Developer/CoreSimulator/Devices -name CoreDataDemo.sqlite

This will print a list of all the files found with the given name. However if you have been running your app on multiple simulators then multiple files will be displayed. It may not be obvious which file is for which simulator as the folders are named after the device identifier rather than a human readable name, additionally the files are not sorted therefore the first file may not be the most recent one.


To find out the Identifier for the simulated device, we can get it in Xcode by going to the Windows menu and selecting Devices and Simulators. This will open a new window, switch tabs to Simulators and select the simulator that your interested in. The Identifier will be displayed along with the summary information.


Since this can be rather painstaking, I've written as script that will search for a given database file and display the top 5 most recently modified files and the ability to directly open them. As well as listing a human understandable version of the simulator. The findcoredata.py script can be found on GitHub.


You’ll notice that the sqlite database file may not be alone. You may also have a file with ‘wal’ suffix, this is the Write-ahead log and a file with ‘shm’ for the Shared-Memory file. If you intend to copy the database then it is important that you copy these files also.

Look, but don’t touch
It is important to remember that you should avoid making modifications to the sqlite data file as Core Data will manage that. The sqlite3 command line tool can be used to execute commands against the database.


Perhaps I'll blog more on the internal structure of the database, but for now since you know how to find and open the database happy exploration.

Tuesday, 19 December 2017

Consistent property attribute formatting in Objective-C

For those of us that care about consistent code formatting there are a few tools out there, including Objective-C support in uncrustify. However, one aspect of formatting  I have not found is to provide a consistent order for the property attributes. Often I'll see code such as the following:-

@interface ViewController()

@property (weak, nonatomic) IBOutlet UIButton *button1;
@property (weak, nonatomic) IBOutlet UIButton *button2;
@property (null_resettable, nonatomic) UIColor *highlightColor;
@property (nonatomic, copy) NSArray *names;
@property (getter=isActive, assign) BOOL active;

@end

This can be a bit of a jumble as there is no consistency in the ordering which causes a lot of cognitive work when reading as I need to read the full list of attributes on each line to see any patterns. To that end I've created a python script that will re-order these source files for me. In this example it would produce: -

@interface ViewController()

@property (nonatomic, weak) IBOutlet UIButton *button1;
@property (nonatomic, weak) IBOutlet UIButton *button2;
@property (nonatomic, null_resettable) UIColor *highlightColor;
@property (nonatomic, copy) NSArray *names;
@property (atomic, assign, getter=isActive) BOOL active;

@end

Now all the nonatomic attributes are move to the front as this is the most common attribute. You'll also notice that for the active property we added the atomic attribute that was not in the original source code. This is because atomic is the default unless nonatomic is specified, however atomic is rarely needed unless dealing with multiple threads, more often than not people simply forget to add nonatomic. By adding it, it makes the behaviour more explicit.

To run the script you simply supply a list of source files. It will work with both header and source files. The script will create a copy of the original source file prior to modifying it, this will have the same name as the original but with .orig suffixed on the name.

sort_prop_attrs.py <sourcefile1> <sourcefile2> <sourcefile3> ...

Monday, 18 December 2017

Named capture groups with NSRegularExpression in iOS11 / High Sierra

After years of no change, Apple slipped a small improvement to NSRegularExpression into iOS 11 / High Sierra. The macOS 10.13 and iOS 11 Release Notes Cocoa Foundation Framework mentioned the updates to NSRegularExpression, but little was given in terms of detail. So lets explore and see if we can find out more. We’ve always had the ability to use index capture groups. However as the complexity of a regular expression grows using numbered indexes can grow unmanageable, as well as making the indices fagile to changes in the pattern can throw the numbering system out of kilter.

Apple’s class reference for NSRegularExpression links to the ICU user guide, which lists the syntax for named groups as (?<name>pattern). So let experiment to see it in action.

Since NSRegularExpression is still very much an API that works with objective-c NSString and its UTF-16 code point model. I’ll use a simple extension on String to make life easier.


Consider a regex pattern for matching formatted U.S. domestic telephone numbers, such as (123) 456-7890.
\(\d{3}\)\s\d{3}-\d{4}
This is chosen for simplicity for demonsating the point rather than the most flexible pattern for general purpose matching. The pattern matches the following: -
  1. an opening parenthesis
  2. three digits
  3. a closing parenthesis
  4. a single whitespace character
  5. three digits
  6. a hyphen
  7. four digits
Let’s say that we’re in particular interested in the area code, which is number 2 on the above list. While the pattern will match the whole telephone number, we can create a capture group around sections of interest, in this case the area code by adding parenthesis around it.
\((\d{3})\)\s\d{3}-\d{4}
This is what we’ve always been able to do, and we’d access this capture group at index 1, using the method range(at:) on NSTextCheckingResult. Index zero is reserved for matching the whole pattern.
let areaCodeRange = match.range(at: 1)
With named capture groups however rather than thinking about it as the capture group at index 1. We can name the capture group like so:
\((?<areacode>\d{3})\)\s\d{3}-\d{4}
This allows us to extract the area code using the new method range(withName:) on NSTextCheckingResult
let areaCodeRange = match.range(withName: "areacode")
  

  
Named back references
Named capture groups are not just for extraction, they can be used in back references. Using the syntax \k<name>. For example, if we wanted to match a balenced set of HTML tags, we can use a named capture group for the tag name and then use that name as a back reference to match the closing tag.

<(?<tag>\w+)[^>]*>(?<content>.*?)</\k<tag>>