Blog

Latest Post

A Fast Fuzzy Search Implementation

In recent episodes of Swift Talk, we’ve been building a fast fuzzy search implementation. Fuzzy search is typically used to search a large list of file names by typing a few relevant characters (like Open Quickly in Xcode). For example, to find a file named Sources/Slides/ContentView.swift, you might type SSCV. The simplest version of a fuzzy search algorithm could be implemented using a regular expression: for the search string SSCV, the regular expression would be something like *S*S*C*V*. In other words, it needs to match the characters SSCV, in that order, but with any number of other characters before, after or in between the characters.

Here’s another simple implementation:

extension String {
    func fuzzyMatch(_ needle: String) -> Bool {
        if needle.isEmpty { return true }
        var remainder = needle[...]
        for char in self {
            if char == remainder[remainder.startIndex] {
                remainder.removeFirst()
                if remainder.isEmpty { return true }
            }
        }
        return false
    }
}

The code works well and is quite fast in an optimized build. We can improve performance by comparing the UTF8View of both strings instead of their characters. This might return some incorrect results if your strings contains things like combining sequences, but is typically not a problem when searching files.

Scoring

The algorithm works very well if all you want to know is whether a filename matches the search string, but in most fuzzy search implementations you’re searching a list of files, and want to rank them by how well they match. Consider the following two file names, which both match string:

source/test/regression/graph.swift
^      ^    ^      ^ ^ ^

source/string.swift
       ^^^^^^

When we search for the word string, we’d like the first file to be ranked below the second file. Although the first file contains the characters string in the right order, they are separated by large gaps. The second file contains them without any gaps. In other words, we don’t just want to match file names, we also want to rank them based on the quality of the match, like the number of gaps and gap sizes.

We can modify our algorithm to compute a score: when we match a character, we remember the position of that match. We then take the distance between the previous match and current match (the gap) and compute a gap penalty. The gap penalty could be very straightforward, such as the length of the gap, or it could be more complicated, for instance as a constant plus the square root of the length. What function you use depends on the exact use case. In addition, you might want to penalize the gap before the first match and the gap after the last match separately (or not at all).

Like before, we can make our algorithm faster by running it on UTF8View instead of on String, but keep in mind that this can change the scoring as well. For example, gap lengths between matches might differ as a character might consist of multiple bytes.

Matching a character isn’t as straightforward as just calling == either. For example, when searching for the character e, we almost certainly want to match both e and E. Likewise, we might want to give bonus points when a matched character comes immediately after a separator such as /, . or _.

In the second episode of the series, we add scoring to the algorithm.

Better Scoring

Unfortunately, the scoring algorithm we described above still isn’t good enough, as it doesn’t calculate the optimal score. It matches characters greedily. For example, if we search for the characters string in source/string.swift, it greedily matches the first s, computes the gap penalty for ource/s and then matches tring. To compute the optimal score we need to consider two cases when we find a match: we need to compute the case in which we accept the match, and the case in which we skip the character and try to find it later in the string. Then we simply take the maximum score of both options.

We can implement that (naively) using a recursive algorithm:

extension Substring {
    func fuzzyMatch2(_ needle: Substring, gap: Int?) -> Score? {
        guard !needle.isEmpty else { return Score() }
        guard !self.isEmpty else { return nil }

        let skipScore = { self.dropFirst().fuzzyMatch2(needle, gap: gap.map { $0 + 1 }) }
        if self.first == needle.first {
            guard let s = dropFirst().fuzzyMatch2(needle.dropFirst(), gap: 0)
                else { return nil }
            var acceptScore = Score()
            if let g = gap, g > 0 {
                acceptScore.add(-g, reason: "Gap \(g)")
            }
            acceptScore.add(1, reason: "Match \(first!)")
            acceptScore.add(s)

            guard let skip = skipScore() else { return acceptScore }
            return Swift.max(skip, acceptScore)
        } else {
            return skipScore()
        }
    }
}

Note that the algorithm above isn’t very fast because it does a lot more work than it needs to. However, the quality of the results is much better than before. Next up, let’s make it fast.

Fast and Correct Scoring

To make things faster, we can use dynamic programming. This means we break up our algorithm recursively in such a way that each step depends directly on the previous step, so that we can compute our result step by step. We can take inspiration from the Smith-Waterman algorithm and build a two-dimensional matrix that holds the intermediate results. We build up this matrix row by row, where each row represents a character in the needle, and each column represents a character in the filename we’re looking at.

Matrix representation

For example, when we search for string in the filename str/testing.swift, we start by matching the character s. In our current implementation, we have a zero penalty for starting gaps, and every matching character gets a score of one. That means that the first row in the matrix contains a score of one for each occurrence of s.

The second row matches a t. When see a t we can compute the score by taking the maximum score of all values in the previous row that are to the left of our t. For each of those matches we compute 1 + previousScore - gapPenalty. In this case, the final value in the second row is computed as 1 + 1 - 3.

The score for a filename is the maximum value in the bottom row. For the three filenames above, it’s 6, 6 and 1, respectively.

In episode 4 of the series, we migrate from our recursive algorithm to this matrix-based version. In the sample code we also provide a GUI that visualizes the matrix, which is great for debugging. When you’re playing around with scoring functions this can be very helpful.

Optimizations

The advantage of a fuzzy search is that we can get to our file very quickly without having to type many characters. This means that the algorithm has to be both correct, yielding the best possible results with few characters, and fast. Now that our algorithm is matrix-based with a few loops, we can make it fast. Our unoptimized version searches 20,000 files (the Swift code base) in about 400ms; to make it feel fast we want it to run in under 16ms, which is the time for a display pass when rendering at 60 frames per second.

There are a number of different techniques we show in the series. As a first step, we changed our algorithm to work on UTF8View instead of String, which brought the running time down to about 100ms. Because of Swift’s built-in collections, this change is very simple to make. We further improve efficiency by working on arrays of UTF-8 code units (i.e. bytes) and reached 80ms.

In our algorithm, we loop over the previous row to find the maximum score for the previous character in our needle. Rather than starting at the beginning of that row, we can start at the index of the first match. Caching the index brought it down to 45ms.

Up until this point our algorithm was a generic method that worked on any Collection type as long as the Element was Equatable. Once we changed it to be a method on Array we could make use of the fact that Array has integer indices, which helps us achieve 37ms.

As a final optimization, we parallelized the search by splitting our array of file names into chunks. Matching the number of chunks to processor cores gave us the best results. This lets us search 20,000 files in about 11ms, and comfortably achieve 60 fps. The benchmarks were done while recording our screen, which seems to slow everything down by quite a bit; without screen recording we saw running times of around 6ms. We can even search the ~70,000 files of the Linux kernel code base in under 16ms.

These optimizations are documented in the fifth and sixth episode of the series.

There are probably a number of further optimizations we could attempt, some of which we discuss in the final episode, but for our purposes the algorithm is fast enough.

Conclusion

We optimized our searching algorithm quite heavily by changing it from a recursive algorithm to a dynamic programming algorithm that builds up intermediate results. This allowed us to further optimize by working on different data structures (UTF-8 bytes instead of Unicode characters), doing less work (e.g. caching some values), and doing work in parallel.

You can watch us discuss and implement these optimizations by subscribing to Swift Talk. As always, the first episode is free to watch.

References

There are many open-source implementations of similar already-existing algorithms. Here are a few we found helpful:

Previous Posts

SwiftUI: Running a Mac App Without an Xcode Project

In 2018, we wrote a post about using AppKit from the command line. We can use exactly the same technique to run a SwiftUI app directly from a Swift file.

When you’re writing a quick tool, perhaps to visualize something, or to get user feedback, an Xcode project can feel like overkill. It’s often very useful to have a single file that you just run with swift myfile.swift from Terminal. Likewise, when you’re inside a Swift Package Manager project, you might not want to create an additional Xcode project when you’re just testing things out.

What if you could just do the following?

NSApplication.shared.run {
    VStack {
        Text("Hello, World")
            .padding()
            .background(Capsule().fill(Color.blue))
            .padding()
    }
    .frame(maxWidth: .infinity, maxHeight: .infinity)
}

Fortunately, you can, by pasting in the boilerplate code from this gist. Simply run swift boilerplate.swift in Terminal and you’ll have a macOS app up and running.

If you’re building a complex app, you’ll almost certainly want to move to a “real” application, but for one-off tools and prototyping we’ve found this shortcut very useful.

Screenshot

In Swift Talk Episode #145, which is free to watch, we use the same technique to create an AppKit app using Swift Package Manager.

SwiftUI: Showing an Alert with a Text Field

In Swift Talk Episode 198, we made a wrapper around UIKit alerts.

SwiftUI provides a built-in API just for this: the alert method on View allows us to present an alert to the user, and under the hood it almost certainly uses a UIAlertController.

For our purposes, we wanted an alert controller with a text field. UIAlertController supports this, but so far, SwiftUI’s built-in Alert struct does not. To route around this limitation, we’ve found a hack that seems to work — for us at least! (we haven’t tested this in a project other than our own).

We’ll start by defining an API similar to SwiftUI’s builtin alert API. It will have the usual properties, and an action parameter that gets called whenever the user presses either the OK or Cancel button.

public struct TextAlert {
    public var title: String
    public var placeholder: String = ""
    public var accept: String = "OK"
    public var cancel: String = "Cancel"
    public var action: (String?) -> ()
}

extension View {
    public func alert(isPresented: Binding<Bool>, _ alert: TextAlert) -> some View {
        // ...
    }
}

Now for the hacky part. When we call alert on a view, we wrap that view inside a custom UIViewControllerRepresentable. Inside, we create a UIHostingController for the view, so that we can call .present on it.

struct AlertWrapper<Content: View>: UIViewControllerRepresentable {
    @Binding var isPresented: Bool
    let alert: TextAlert
    let content: Content

    func makeUIViewController(context: UIViewControllerRepresentableContext<AlertWrapper>) -> UIHostingController<Content> {
        UIHostingController(rootView: content)
    }

    // ...
}

To store the current alert controller we need to create a coordinator:

struct AlertWrapper<Content: View>: UIViewControllerRepresentable {
    // ...

    final class Coordinator {
        var alertController: UIAlertController?
        init(_ controller: UIAlertController? = nil) {
            self.alertController = controller
        }
    }

    func makeCoordinator() -> Coordinator {
        return Coordinator()
    }
}

Finally, we need to show and hide the alert whenever our binding changes. SwiftUI will automatically observe the binding and call updateUIViewController(_:context:) each time that happens. Inside, there are two code paths: when the binding’s value is true but we’re not yet presenting the alert controller, we need to present it; when the binding’s value is false but we are presenting the alert controller, we need to dismiss it.

func updateUIViewController(_ uiViewController: UIHostingController<Content>, context: UIViewControllerRepresentableContext<AlertWrapper>) {
    uiViewController.rootView = content
    if isPresented && uiViewController.presentedViewController == nil {
        var alert = self.alert
        alert.action = {
            self.isPresented = false
            self.alert.action($0)
        }
        context.coordinator.alertController = UIAlertController(alert: alert)
        uiViewController.present(context.coordinator.alertController!, animated: true)
    }
    if !isPresented && uiViewController.presentedViewController == context.coordinator.alertController {
        uiViewController.dismiss(animated: true)
    }
}

Note that we’re setting the hosting controller’s root view in the first line of the updateViewController method. This method will be called if our isPresented binding for the alert changes, but also when something changes that affects the content of the alert wrapper. If we omit this first line, SwiftUI will no longer update the view inside the hosting controller.

Now we can use our text alert:

struct ContentView: View {
    @State var showsAlert = false
    var body: some View {
        VStack {
            Text("Hello, World!")
            Button("alert") {
                self.showsAlert = true               
            }
        }
        .alert(isPresented: $showsAlert, TextAlert(title: "Title", action: {
            print("Callback \($0 ?? "<cancel>")")
        }))
    }
}

We hope that SwiftUI will catch up with UIAlertController, making these kinds of hacks unnecessary. In the meantime, if anyone knows of a simpler way to do this, do let us know and we’ll update this post!

Here’s the full code.

Our SwiftUI Collection has 33 episodes and growing, with 8 public episodes. In our latest series, we port App Architecture‘s sample app from MVC to SwiftUI — the first episode is free to watch.

Our New Book: Thinking in SwiftUI

We’re very happy to announce that our latest book, Thinking in SwiftUI, is complete and available today — our thanks to all the early access readers!

Thinking in swiftui hero original

The book

When SwiftUI came out, we immediately started exploring the framework. It quickly became clear that SwiftUI was a radically different pattern from any we had encountered before. When you’re coming from UIKit, you really do have to rethink how to structure your applications.

While Apple provided tutorials and WWDC talks, many things remained undocumented or unclear. Rather than attempting to document fast-changing APIs, our new book focuses on clarity of thought. We take you through the fundamental concepts behind SwiftUI, and emphasise the differences, for experienced UIKit programmers who already know Swift.

In short, you will learn to think in SwiftUI.

We start by explaining the view-update cycle: SwiftUI is a declarative system which doesn’t let you update views in place; instead, you change the state, and let the framework re-render the necessary views. We look into the environment and preference system, which is an essential part of SwiftUI. We also look at how the layout system works, and how to build advanced layouts using geometry readers, overlays, alignment guides and preferences. The final chapter is about animations, both the built-in animations, and completely custom animations.

Our book is filled with examples, but we believe that the best way to learn is to build things yourself. We are including exercises at the end of each chapter so that you can practice the techniques on real problems. Of course, at the end of the book, we include all solutions.

Here’s what one of our reviewers had to say about them:

The exercises are a lot of fun! I love when a book includes the solutions to the exercise. After looking at your solution, it was immediately clear what I had forgotten.

Ole Begemann

With video

The book also comes with an optional video package. In the videos, we use pair programming to implement the solutions to the exercises. We also build an angle dial control (you may recognise this from the built-in angle adjustment in Photos for Mac), and a view to display and animate trees — we use the same code to generate the trees in our book:

This edition won’t be covering (many) platform-specific views, such as scroll views and navigation views. At the time of writing, these still require significant workarounds to perform well. However, once you have worked through the chapters, you’ll be very prepared to start writing a SwiftUI app today.

We’d like to thank all the people that helped us during the writing: Ole, Javier, Matt, Natalye, Morgan, and everyone who sent feedback during the pre-release phase.

Enjoy the book! 😊

Best from Berlin, Florian and Chris.

SwiftUI Line Graph Animation

In the sixth of our Thinking in SwiftUI challenges, we asked you to animate a line graph.

As a first step, we’ll create a shape for the line graph. This shape takes an array of data points (normalized to 0...1). Any points that are outside this range are drawn outside of the proposed rectangle rect. For clarity, we pulled out the function that computes a CGPoint for a given data point.

struct LineGraph: Shape {
    var dataPoints: [CGFloat]

    func path(in rect: CGRect) -> Path {
        func point(at ix: Int) -> CGPoint {
            let point = dataPoints[ix]
            let x = rect.width * CGFloat(ix) / CGFloat(dataPoints.count - 1)
            let y = (1-point) * rect.height
            return CGPoint(x: x, y: y)
        }

        return Path { p in
            guard dataPoints.count > 1 else { return }
            let start = dataPoints[0]
            p.move(to: CGPoint(x: 0, y: (1-start) * rect.height))
            for idx in dataPoints.indices {
                p.addLine(to: point(at: idx))
            }
        }
    }
}

SwiftUI has built-in support for trimming shapes using the .trim modifier: this trims the path of the shape to the specified start and end points. We keep a constant starting point, 0, but vary the end point during the animation (from 0 to 1). Since the trim modifier has built-in support for animating the start and end points, we can animate the graph simply by animating between a to value of 0 and 1. Because the graph is defined as a Shape, we can use the built in modifiers to style it: stroke it with a red color, fix it to an aspect ratio, add a border, and apply some padding:

struct ContentView: View {
    @State var on = true

    var body: some View {
        VStack {
            LineGraph(dataPoints: sampleData)
                .trim(to: on ? 1 : 0)
                .stroke(Color.red, lineWidth: 2)
                .aspectRatio(16/9, contentMode: .fit)
                .border(Color.gray, width: 1)
                .padding()
            Button("Animate") {
                withAnimation(.easeInOut(duration: 2)) {
                    self.on.toggle()
                }
            }
        }
    }
}

That’s all we need for our line graph — or any shape, really — to animate:

Our new book, Thinking in SwiftUI, discusses the animation system in more detail in chapter six. You can buy it here.