Today I Learned

For the past two years, I’ve been working at one of the best educational technology companies in the world: Duolingo. I want to start writing about the things I’m learing about educational technology and I needed a space to do so. So here it is.

  1. August 30, 2022

    Nevermind! The previous bug about clipping images in a SwiftUI-optimized-for-Mac toolbar is fixed in Mac Ventura Beta 6.

    I thought I had been up-to-date on my Beta builds when I wrote the prior post. Here’s how I discovered I wasn’t:

    1. I wanted to see if this problem reproduces on MacOS Monterey. When I did this, I discovered that on Monterey, there’s no attempt to create a Mac-style toolbar at all from SwiftUI Catalyst. Note this is different from the .borderedProminent bug I wrote about yesterday — that bug also happens on Monterey.
    2. Filing a Radar on bugs in new functionality seems more valuable than filing a Radar on bugs that Apple already decided is OK to ship. So, I prepared to file a Radar…
    3. And that’s what made me think, “Let’s make sure I’m up-to-date first.” And I wasn’t. (In my defense, System Settings said I was up-to-date, but it also said it hadn’t checked in over a week. I saw on the Downloads page that there was a new version after Settings had checked. I forget what I had to jiggle to get System Settings to properly refresh.)

    Anyway, it’s awesome seeing bugs get fixed in Beta builds. Feels like receiving a gift.

  2. August 29, 2022

    I’ve had so much fun creating a Mac version of Library Notes in Catalyst that I’ve started a couple of other multi-platform projects. Along the way I’ve encountered some bugs and come up with at least one workaround that I will now share with you, Gentle Reader.

    Developing for the Mac: So many choices

    If you’re an iOS engineer, like me, venturing into Mac land for the first time, be aware that there are at least three ways to make this journey without going full AppKit.

    1. SwiftUI targeting the Mac SDK: In this mode, you write SwiftUI code, and under the hood that SwiftUI code will create native Mac (AppKit) controls. This route works if your UI is 100% SwiftUI. You don’t get the escape route of creating a UIViewRepresentable to manage a UIView with SwiftUI, because your app doesn’t have access to UIKit at all.
    2. SwiftUI targeting Mac Catalyst, “optimize for Mac” mode: In this mode, you’re writing SwiftUI, but under the hood your app is using the iOS SDK and will use Mac Catalyst to run on the Mac. Catalyst will try to make your UI controls look more Mac-like.
    3. SwiftUI targeting Mac Catalyst, “scaled to match iPad” mode: In this mode, you’re writing SwiftUI, it uses the iOS SDK, it uses Mac Catalyst to run on the mac, but the controls will look like iOS controls. (This is most noticeable with buttons and navigation bars.)
    4. UIKit, not SwiftUI, with the different Catalyst modes: Replay options (2) and (3) above, but this time substitute “UIKit” for “SwiftUI.”

    I’ve outlined the different modes because many of the issues I’ve run into only affect one of them: SwiftUI code that uses Mac Catalyst to run on the Mac in “optimize for Mac” mode. You’d think that this would be the easiest way for an iOS Engineer to write apps that look like native Mac apps, but beware these sharp edges.

    Bug: .borderedProminent doesn’t work in “optimize for Mac”

    Mac “push buttons” have borders. According to the Human Interface Guidelines, you should use a filled button for the primary action in a view. SwiftUI provides an easy way to get this: Apply the .borderedProminent style.

    The problem? This works for SwiftUI-targeting-iOS apps, and SwiftUI-targeting-Mac apps, and SwiftUI-targeting-Catalyst-in-iOS-mode apps, but not SwiftUI-targeting-Catalyst-in-optimized-mode apps. For just that mode, the button doesn’t get filled in.

    This seems to be a SwiftUI bug and not a Catalyst bug. If you write UIKit code, and create a UIButton and use UIButton.Configuration.borderedProminent() to create a button configuration, you’ll get a button that shows up in your “optimize for Mac” Catalyst app appropriately filled in.

    That, then, is the workaround for this bug. If you’re writing a Mac app, using Mac Catalyst, choose “optimize for Mac” for your UI mode, you cannot use the SwiftUI Button View for any button you want to display in the prominent “filled” style. Instead, you need to use UIViewRepresentable to create a UIButton and explicitly give it the UIButton.Configuration.borderedProminent() configuration.

    Bug: Toolbars clip their toolbar buttons

    Update: This was a bug in MacOS Ventura that was fixed in Beta 6.

    This is another one that appears to be SwiftUI + Mac Catalyst + “optimize for Mac” specific. In this mode, the toolbar clips its buttons. Instead of this:

    A sample app with a proper Mac toobar

    you get this:

    A sample app with a broken Mac toobar

    Note that the top & bottom of the toolbar icon are clipped.

    While I haven’t coded this yet, I suspect the answer is going to be the same as above: Use UIKit to manage your toolbars if you want a Mac-style toolbar in your Catalyst app.

  3. August 21, 2022

    Today I learned that a UISplitViewController behaves differently in a Mac Catalyst app when it is the root of a window versus if it is wrapped in a window. If you want Mac-style toolbar behaviors, make it the root of a window.

    Library Notes uses a UISplitViewController for its main screen. When I first wrote this app, I was deep into the “composition instead of inheritance” philosophy, and I used view controller containment to avoid subclassing UISplitViewController. I created a class called NotebookViewController to manage the UISplitViewController. NotebookViewController creates the split view controller & adds it as a child view controller that completely fills its view.

    Running on iOS, it looks like a normal UISplitViewController fills the whole screen.

    Now that I’m working on porting Library Notes to the Mac using Catalyst, though, I noticed something: Even when I tell Xcode that I want to optimize for the Mac interface, I still get iOS-style bar button items displayed in the navigation bar instead of Mac-style buttons displayed in the toolbar. My UI looked like this:

    UISplitViewController with iOS-style buttons

    I suspected that Mac Catalyst did something different if the window’s rootViewController is a UISplitViewController, so I rewrote NotebookViewController to be a UISplitViewController rather than contain a UISplitViewController. Sure enough, after that simple change, my UI looked like this:

    UISplitViewController with a Mac-style toolbar

    In retrospect, this makes perfect sense. Mac Catalyst will adapt iOS components to a Mac interface based upon what those components are. Something to keep in mind if, like me, you are an iOS developer venturing into Mac-land for the first time.

  4. August 14, 2022

    tl;dr: If you’re trying to use UIDocumentPickerViewController or UIDocumentBrowserViewController from a Mac Catalyst app and always get stopped in the debugger with the message “this class is not key value coding-compliant for the key cell”, just temporarily disable breakpoints and continue. Everything will work.

    I’m embarrassed how much time I lost on this problem.

    When I first worked on getting Library Notes ready to submit to the App Store, I figured I should also try this new-fangled “Mac Catalyst” technology and get a version of the app that runs on the Mac, too.

    In my notes at the time, I wrote:

    Update Jan 14, 2021 — The Catalyst app crashes on launch with an error about an NSView not being key-coding compliant for “cell”, and I have no idea how to debug further. So, I’m just going to ignore making a Mac app for now.

    I didn’t pursue the Mac version of this project because, at the time, it worked just as well for me as an iPad / iPhone app.

    Fast forward 18 months, and I’m getting ready to go on a long series of back-to-back business and personal trips, and I didn’t want to bring both my iPad Pro and Mac. Suddenly it really bothered me that I didn’t have a Mac version of Library Notes that I could use to continue to update my reading notes while on my trip. There was also a brand-new version of Xcode, and a lot of hubbub about “desktop-class iPad apps” at WWDC. Surely, this problem about an NSView not being key-coding compliant for “cell” is fixed in with the new developer tools, right?

    Wrong.

    I fire up the Xcode project, set it to target Mac Catalyst, hit Run in Xcode, and almost immediately hit the error message:

    Thread 1: ”[<NSView 0x14363e4f0> valueForUndefinedKey:]: this class is not key value coding-compliant for the key cell.”

    The frustrating this was this error doesn’t originate in my code. As near as I can tell, it comes from using UIDocumentBrowserViewController in a Catalyst app on a Mac with a Touch Bar. I only found one other person on Twitter who had this problem. Google searches turned up nothing. I tried:

    • Refactoring my code to use UIDocumentPickerViewController instead of UIDocumentBrowserViewController. Same problem as soon as I bring up the picker.
    • I created a custom UIDocumentPickerViewController subclass and used that instead. I tried manipulating every Touch Bar hook in UIViewController to see if I could make the problem go away. No luck.
    • Creating a new sample app that just brought up a UIDocumentBrowserViewController. This one worked, so I systematically started looking for differences between Library Notes and the test app. I changed random Info.plist properties, target SDK versions; really, anything I could think of. This took about a day.
    • Finally, I decided to run my broken Catalyst app in Instruments to see if there’s any code running at app start that I’ve forgotten about. “Maybe,” I thought to myself, “something running at app start is putting things in a funny state?” Imagine my shock when the app worked when connected to Instruments.
    • This is what lead me to discover that everything works when I run the Release build. Something related to optimizations?
    • No! Even dumber. Everything works if I don’t have breakpoints enabled when running the app in the debugger. It’s not enough to just hit “continue” when you run into this problem. It will just happen again. However, if you get this message in the debugger, just disable breakpoints then click Continue. The document picker will work.

    This one problem set back the Mac version of Library Notes by over a year. (Facepalm.)

  5. July 23, 2022

    Recently I’ve been exploring using “files in a Git repository” as the main storage for iOS and Mac apps. I’ve got two little projects using this.

    The key technology that enables this approach is libgit2, which is a C language implementation of the core git methods. There are at least two popular ways to use libgit2 from iOS / Mac. The first, ObjectiveGit, is Objective-C bindings to the C API. The second, SwiftGit2, is a set of Swift bindings.

    Being me, I wound up going with neither of these libraries. Things that made me shy away:

    1. Neither project use Swift Package Manager, which I use exclusively in my personal projects.
    2. Neither project has been updated recently. SwiftGit2 links against version 1.1 of libgit2 (the library is now, at the time of this writing, at version 1.5). ObjectiveGit is worse, linking against version 0.28.1!

    So I’ve approached git integration to Swift iOS/Mac apps from first principles and created two projects:

    1. static-libgit2 is a Swift package that exposes the libgit2 C API through the Clibgit2 module. This project is a modification of LibGit2-On-iOS and follows the same basic strategy:

      1. Use build scripts to build libgit2 and its dependencies (libssh, openssl) and create a single xcframework for all of the necessary SDK and architecture variations.
      2. Create a Package.swift file to let projects include the xcframework through Swift Package Manager.

      static-libgit2 is pretty stable, and if you want to just use the C APIs in a Swift app, it gives you want you want. It’s ready for public consumption now.

      import Clibgit2
      import SwiftUI
      
      struct ContentView: View {
          var body: some View {
              Text(LIBGIT2_VERSION)
                  .padding()
          }
      }
    2. AsyncSwiftGit is much more experimental and much less stable. It’s my attempt to write Swift wrappers around the C API that uses the new concurrency features of Swift 5.5. For example, instead of passing in C-compatible callback functions when fetching changes from a remote repository, I can write:

      for try await progress in repository.fetchProgressStream(remote: "origin", credentials: credentials) {
          // do something with `progress` here
      }

      This is “more experimental and less stable” because I’m still figuring out the right way to use Swift concurrency, the best way to design wrappers around a C API, etc. This one is not yet ready for public consumption.

    Overall, though, I’ve been really impressed with how fun and reliable it is to use git as the main storage system for personal programming projects! I predict I’ll be using it more and more.

  6. October 22, 2021

    …the lesson is clear: a central challenge to improving the way we learn is finding a way to interrupt the process of forgetting.

    (Make it Stick: Brown & Roediger)

    I started my love affair with books in elementary school. By the time I entered high school, though, I noticed I was forgetting most of what I’d read. Sometimes I couldn’t even remember that I had read a book at all, much less remember what the book was about. This started a mild obsession of figuring out ways to remember more of what I’ve read. I wrote about books in my journal; I kept a running bibliography of books for a few years; I cataloged and reviewed books on LibraryThing.

    My Library Notes app my current system to help me remember what I’ve read. While the app has only been on the App Store for a few weeks, I’ve been using this app for about three years. I’ve noticed that I use Library Notes differently for different kinds of books. Basically, there are four “levels” to how involved I am with a book, and I can use Library Notes for all four levels:

    1. For hundreds of books, I just use Library Notes as a book cataloging app. I just want a record that the book is in (or has been in) my personal library. (Alas, I buy more books than I read!) Title, author, cover image: That’s all I want. Because Library Notes can scan the book’s ISBN barcode and look up bibliographic information & cover images from the Internet, the cataloging process is fairly streamlined.
    2. For a lot of fiction books I read for fun, I add a little more information: A quick blurb about the book and a star rating. There’s no formula for how much I write about each book, but recently I’ve been happy with the following pattern: I write the names of the main characters and the rough plot arc. I’ll probably forget everything else about the book within a year, but this is enough to help me recommend books to friends: I sort my library by star rating, and then I can say, “Oh yeah! Have you read anything by Tana French? She’s great…” It doesn’t matter that I can’t remember the plot of In the Woods — I remember that I loved the book and that my friends will probably love it, too.
    3. For books I really want to remember, I use a technique I first learned from The Well-Educated Mind, by Susan Wise Bauer: I write down an outline of the book in my notes. This is much more intensive than writing a quick blurb when I’m done with the book. When I’m in this mode, I’m going back-and-forth between the book and Library Notes after each chapter, creating a chapter-by-chapter summary of what I’ve read. However, I’ve noticed two things: First, probably because of the work I’ve put into creating the outline, these books remain much more firmly lodged in my brain in the first place. Second, if I do need a refresher on what’s in the book, rereading the outline brings back a lot more detail than reading my quick “character-and-plot-arc” blurb. I save this for “serious” reading.
    4. Outlines are great. However, the science is clear: If you really want to cement something in your brain, the best techniques are active recall and spaced repetition. For the most interesting & challenging works I read, I spend time to create active recall prompts in my notes (either question & answer prompts, or fill-in-the blank prompts). I can then use Library Notes’ review mode to quiz myself on the prompts.

    Library Notes isn’t an app for everyone, but I’m really happy with how it scales from “simple cataloging” to “advanced memory tool with active recall and spaced repetition.” It’s been a great companion on my reading journey. If you think it’s something that would help you, you can get it on the App Store now. It’s software made for the love of books, not to be a business, and is now and will always be free.

  7. August 21, 2021

    I’ve recently extracted another module out of Grail Diary: KeyValueCRDT.

    It turns out designing a file format that works in an era of cloud document storage is hard! Cloud documents and mobile devices make it really easy for people to make conflicting changes to the same document. It’d be nice to provide a better experience for people than a “pick which version of the file to keep” dialog box.

    The key to avoiding the “pick the version of the file to keep” dialog is making your file format a Conflict-Free Replicated Data Type (CRDT). With a CRDT, you can reliably merge changes made from multiple devices rather than forcing a person to pick which file version to keep.

    My goal with KeyValueCRDT is to provide a CRDT implementation that can work as a file format for a wide range of applications. There are more details about the API the GitHub page, but here’s the bullet-point summary:

    • KeyValueCRDT uses SQLite for its storage, for all of the reasons listed in SQLite As An Application File Format.
    • The data model is a key-value store.
    • Values can be text, JSON, or arbitrary data blobs. Text values are indexed using FTS5 for fast full-text search.
    • At its core, KeyValueCRDT is an observed-remove set and provides multi-value register semantics. When you read a key from the database, you may get multiple values returned if there were conflicting updates to that key.
    • In addition to the underlying database operations, the module provides a UIDocument subclass that lets you integrate with the iOS document ecosystem (including iCloud documents). The module also provides a command-line tool (kvcrdt) to allow you to inspect and manipulate the database from scripts.

    Currently I use KeyValueCRDT for the document format for Grail Diary, and I hope it will be a useful format for other applications as well.

  8. June 28, 2021

    Yes, async / await is going to be great. However, Xcode 13’s DocC documentation compiler is currently the most inspiring feature for me. For the past several days I’ve been pulling out the building blocks of Grail Diary into separate packages and revamping the documentation. Often, when trying to write the documentation, I’ve realized that the APIs themselves are awkward, so I’ve refactored those as well. While this work hasn’t done much to make Grail Diary feel different when using it, I’m feeling awesome because the foundation of the program is getting more solid.

    Since the new documentation toolchain is in beta, I’m isolating this work in an xcode13 branch across the following repositories:

    • SpacedRepetitionScheduler for recommending times to review prompts in a spaced-repetition system
    • BookKit for utility routines for dealing with different book web services, like Google Books, Open Library, Goodreads, and LibraryThing.
    • TextMarkupKit for parsing and formatting text as you type.

  9. June 23, 2021

    Yesterday, I released TextMarkupKit. This is the core text processing code that I use for Grail Diary — it handles all of the text parsing, formatting, etc.

    If you’ve ever wanted to build an iOS app that does automatic formatting of plain text as you type, check out TextMarkupKit. It might be exactly what you need.

  10. May 22, 2021

    In my quest to make Grail Diary a great app for book lovers, I’ve just finished adding a feature I’ve wanted for a while. In a stroke of marketing genius, I’m calling it Random Quotes. It does exactly what it says: It scans through your book notes for five random quotes and shows them, nicely formatted, on a single page. Want to see a different selection of quotes? Just hit the Shuffle button.

    The goal here is perusability. When you flip through your book notes, you get to revisit the books in your mind. It’s like dropping in on old friends. Random Quotes tries to make this easy and fun.

    The feature’s only a few hours old but I’ve gotten a lot of joy from hitting the Shuffle button!

    Random Quote Screenshot

  11. May 12, 2021

    Once upon a time, I was going to take what I learned writing the custom syntax-highlighting editing component of Grail Diary and turn it into a stand-alone tutorial on text editing. I ran out of time to work on that after writing one item: An overview of how you can take a custom data structure for text editing (a piece table) and give it a natural API by conforming to Swift Collection. I don’t want this material to die, so I’ve moved it over here.

    The Theory

    What’s so hard about editing text? Let’s ignore for the moment the problems with even storing Unicode text, with its encodings, multi-byte characters, etc. If you put those considerations aside, the abstract model for a text file is an array of characters. An array is about as simple a data structure as you can get. What’s the problem?

    The answer, of course, is that changing things in an array can be expensive. Appending to or removing from the end of an array is cheap. Any other operation, though, means copying elements to make room for the new element (or to remove existing elements). And of course in a text editor, you want to make changes all throughout the text, not just at the end. That’s kind of the point. If your editor’s main data structure for text is “an array of characters”, it’s doing a ton of memory copying on every keystroke whenever the cursor is anywhere but the very end of the file.

    So we need something better. But what?

    One option is to store the file as a linked list of lines, and each line is an array of characters. You still need to do copying as you insert and remove characters, but you’re now only copying characters on the same line instead of all characters to the end of the file. If you’re implementing a source code editor, where you can assume that lines are all of a reasonable maximum length, you can get far with this approach.

    lines

    Next up in sophistication is a data structure known as a gap buffer. The main idea behind a gap buffer is that edits to a text file aren’t randomly distributed throughout the text file — they exhibit a lot of locality. If you insert a character at offset 42 in the file, the next insertion is much more likely to be at offset 43 than any other location, and the next deletion is likely to be at offset 42 than any other location. Basically, where the cursor is is where edits are likely to be. A gap buffer makes edits at the cursor really cheap, but you pay a cost to move the cursor.

    A gap buffer does this by storing the text in an array that’s much larger than what’s needed to store the text. This gives you a lot of free space inside the array (the “gap”), and the key insight is you can pay a cost to move the gap to the location of the cursor to make insertions and deletions at the cursor really cheap.

    gap

    While you can implement world-class editors with a gap buffer, for Scrap Paper we’re going to use a third approach, called a Piece Table. Remember how we said that appending to the end of an array is cheap? The piece table exploits that by keeping two arrays. One read-only array contains the original file contents. The second append-only array contains all characters inserted at any time during the editing session. Finally, the piece table tells you how to build the file as a sequence of “pieces” from the different arrays.

    piece2

    Just as with the gap buffer, a piece table works efficiently because most edits to a text file are localized. When you insert character after character into the same spot, you’ll end up with a pretty compact representation of the “pieces” constructed from the two arrays. For example, I edited this file in a version of Scrap Paper that recorded all of the changes that I made to the text file (backspaces and all). At the end of my editing session of 2276 individual edits, I had 48 pieces representing the contents of the file.

    One more bit of theory: String, NSString, and unicode

    I glossed over the challenges of representing text earlier. It’s now time to pay a little attention to that.

    1. The Swift String struct and the Objective-C NSString class made different engineering choices about how to store and model strings. Swift models its strings as an array of “characters” and encodes those characters in UTF-8. The NSString class, in contrast, does not expose individual Unicode characters, and it uses UTF-16 encoding internally.
    2. The TextKit classes are from the NSString era.
    3. Since we will be interfacing a lot with TextKit, we’re going to use the NSString convention and model our text as an array of UTF-16 code points.

    Let’s build a Piece Table!

    With the theory out of the way, it’s time to do some building.

    /// A piece table is a range-replaceable collection of UTF-16 values. At the storage layer, it uses two arrays to store the values:
    ///
    /// 1. Read-only *original contents*
    /// 2. Append-only *addedContents*
    ///
    /// It constructs a logical view of the contents from an array of slices of contents from the two arrays.
    public struct PieceTable {
      /// The original, unedited contents
      private let originalContents: [unichar]
    
      /// All new characters added to the collection.
      private var addedContents: [unichar]
    
      /// Identifies which of the two arrays holds the contents of the piece
      private enum PieceSource {
        case original
        case added
      }
    
      /// A contiguous range of text stored in one of the two contents arrays.
      private struct Piece {
        /// Which array holds the text.
        let source: PieceSource
    
        /// Start index of the text inside the contents array.
        var startIndex: Int
    
        /// End index of the text inside the contents array.
        var endIndex: Int
      }
    
      /// The logical contents of the collection, expressed as an array of pieces from either `originalContents` or `newContents`
      private var pieces: [Piece]
    
      /// Initialize a piece table with the contents of a string.
      public init(_ string: String) {
        self.originalContents = Array(string.utf16)
        self.addedContents = []
        self.pieces = [Piece(source: .original, startIndex: 0, endIndex: originalContents.count)]
      }
    }

    This code defines the stored properties we need for a piece table:

    • originalContents is the read-only copy of the characters from the file we are trying to edit.
    • addedContents is an append-only array of all characters added during an edit session.
    • pieces describes the logical contents of the file as a series of contiguous characters from either originalContents or addedContents.

    Conforming to Collection

    To make PieceTable feel Swift-y, we’re going to make it conform to a few standard protocols. First: Collection — this will let users read characters from a piece table as easily reading characters from an array. In Swift, a Collection is a data structure that contains elements that can be accessed by an index. If you’ve used arrays in Swift, you’ve used a collection.

    The Collection protocol is big. While it contains over 30 methods, most of those have default implementations. To create a custom Collection, this is all you need to implement:

    // The core methods of a Collection.
    // Everything here should have O(1) complexity.
    protocol Collection {
      associatedtype Element
      associatedtype Index: Comparable
      var startIndex: { get }
      var endIndex: { get }
      func index(after position: Index) -> Index
      subscript(position: Index) -> Element
    }

    If your only exposure to Collection has been through arrays, you may have assumed that the index needs to be an integer. Not so! The Collection protocol gives implementations a ton of flexibility about the index type. You can use any type so long as:

    1. You can efficiently return the index of the first element of the collection
    2. You can efficiently return the index that means “you’ve moved past the last element of the collection”
    3. Given an index, you can efficiently return the next index in the collection.

    For our piece table, we are going to need a custom index type. To find a character in the piece table, we will use two values: The index of the piece in the pieces table, and then the index of the character within the contents array. With this information, we can easily figure out the character at an index (use the piece index find the correct contents array, then return the character at the correct character index). It’s a tiny bit more complicated to figure out the index that comes after the next index, because you have to consider two cases: If the current index represents a character at the end of a piece, you have to move to the next piece; otherwise you move to the next character in the current piece.

    With this overview, here is the minimal code to have a piece table conform to Collection:

    extension PieceTable: Collection {
      public struct Index: Comparable {
        let pieceIndex: Int
        let contentIndex: Int
    
        public static func < (lhs: PieceTable.Index, rhs: PieceTable.Index) -> Bool {
          if lhs.pieceIndex != rhs.pieceIndex {
            return lhs.pieceIndex < rhs.pieceIndex
          }
          return lhs.contentIndex < rhs.contentIndex
        }
      }
    
      public var startIndex: Index { Index(pieceIndex: 0, contentIndex: pieces.first?.startIndex ?? 0) }
      public var endIndex: Index { Index(pieceIndex: pieces.endIndex, contentIndex: 0) }
    
      public func index(after i: Index) -> Index {
        let piece = pieces[i.pieceIndex]
    
        // Check if the next content index is within the bounds of this piece...
        if i.contentIndex + 1 < piece.endIndex {
          return Index(pieceIndex: i.pieceIndex, contentIndex: i.contentIndex + 1)
        }
    
        // Otherwise, construct an index that refers to the beginning of the next piece.
        let nextPieceIndex = i.pieceIndex + 1
        if nextPieceIndex < pieces.endIndex {
          return Index(pieceIndex: nextPieceIndex, contentIndex: pieces[nextPieceIndex].startIndex)
        } else {
          return Index(pieceIndex: nextPieceIndex, contentIndex: 0)
        }
      }
    
      /// Gets the array for a source.
      private func sourceArray(for source: PieceSource) -> [unichar] {
        switch source {
        case .original:
          return originalContents
        case .added:
          return addedContents
        }
      }
    
      public subscript(position: Index) -> unichar {
        let sourceArray = self.sourceArray(for: pieces[position.pieceIndex].source)
        return sourceArray[position.contentIndex]
      }
    }

    Conforming to RangeReplaceableCollection

    We can now iterate through the contents of a PieceTable. However, we don’t have a way to modify the contents of the PieceTable. To add this capability, we are going to make PieceTable conform to RangeReplaceableCollection. This protocol has a single required method, replaceSubrange(_:with:). If you implement this method, you get a ton of other APIs for free.

    For our implementation of replaceSubrange, we have to do two high-level jobs:

    1. Append the new characters to the end of addedContents. Remember, in a piece table, we only ever add characters — never delete — and they always get added to the end of the array. This is the easy part.
    2. The hard part: Update pieces to reflect the new contents of the file. The performance of the piece table will depend on how many entries are in pieces, so we need to take care to avoid creating unneeded items.

    This implementation manages the complexity of updating the pieces array by creating a stand-alone change description that contains the new piece table entries. When constructing the change description, the implementation adheres to two rules to minimize the size of the pieces array:

    1. No empty pieces! If an edit creates a Piece with no characters, it’s removed.
    2. If it is possible to coalesce two neighboring pieces into one, do it.

    Here is the code that adds conformance to RangeReplaceableCollection:

    extension PieceTable: RangeReplaceableCollection {
      /// This structure holds all of the information needed to change the pieces in a piece table.
      ///
      /// To create the most compact final `pieces` array as possible, we use the following rules when appending pieces:
      ///
      /// 1. No empty pieces -- if you try to insert something empty, we just omit it.
      /// 2. No consecutive adjoining pieces (where replacement[n].endIndex == replacement[n+1].startIndex). If we're about to store
      ///   something like this, we just "extend" replacement[n] to encompass the new range.
      private struct ChangeDescription {
    
        private(set) var values: [Piece] = []
    
        /// The smallest index of an existing piece added to `values`
        var lowerBound: Int?
    
        /// The largest index of an existing piece added to `values`
        var upperBound: Int?
    
        /// Adds a piece to the description.
        mutating func appendPiece(_ piece: Piece) {
          // No empty pieces in our replacements array.
          guard !piece.isEmpty else { return }
    
          // If `piece` starts were `replacements` ends, just extend the end of `replacements`
          if let last = values.last, last.source == piece.source, last.endIndex == piece.startIndex {
            values[values.count - 1].endIndex = piece.endIndex
          } else {
            // Otherwise, stick our new piece into the replacements.
            values.append(piece)
          }
        }
      }
    
      /// If `index` is valid, then retrieve the piece at that index, modify it, and append it to the change description.
      private func safelyAddToDescription(
        _ description: inout ChangeDescription,
        modifyPieceAt index: Int,
        modificationBlock: (inout Piece) -> Void
      ) {
        guard pieces.indices.contains(index) else { return }
        var piece = pieces[index]
        modificationBlock(&piece)
        description.lowerBound = description.lowerBound.map { Swift.min($0, index) } ?? index
        description.upperBound = description.upperBound.map { Swift.max($0, index) } ?? index
        description.appendPiece(piece)
      }
    
      /// Update the piece table with the changes contained in `changeDescription`
      mutating private func applyChangeDescription(_ changeDescription: ChangeDescription) {
        let range: Range<Int>
        if let minIndex = changeDescription.lowerBound, let maxIndex = changeDescription.upperBound {
          range = minIndex ..< maxIndex + 1
        } else {
          range = pieces.endIndex ..< pieces.endIndex
        }
        pieces.replaceSubrange(range, with: changeDescription.values)
      }
    
      /// Replace a range of characters with `newElements`. Note that `subrange` can be empty (in which case it's just an insert point).
      /// Similarly `newElements` can be empty (expressing deletion).
      ///
      /// Also remember that characters are never really deleted.
      public mutating func replaceSubrange<C, R>(
        _ subrange: R,
        with newElements: C
      ) where C: Collection, R: RangeExpression, unichar == C.Element, Index == R.Bound {
        let range = subrange.relative(to: self)
    
        // The (possibly) mutated copies of entries in the piece table
        var changeDescription = ChangeDescription()
    
        safelyAddToDescription(&changeDescription, modifyPieceAt: range.lowerBound.pieceIndex - 1) { _ in
          // No modification
          //
          // We might need to coalesce the contents we are inserting with the piece *before* this in the
          // piece table. Allow for this by inserting the unmodified piece table entry that comes before
          // the edit.
        }
        safelyAddToDescription(&changeDescription, modifyPieceAt: range.lowerBound.pieceIndex) { piece in
          piece.endIndex = range.lowerBound.contentIndex
        }
    
        if !newElements.isEmpty {
          // Append `newElements` to `addedContents`, build a piece to hold the new characters, and
          // insert that into the change description.
          let index = addedContents.endIndex
          addedContents.append(contentsOf: newElements)
          let addedPiece = Piece(source: .added, startIndex: index, endIndex: addedContents.endIndex)
          changeDescription.appendPiece(addedPiece)
        }
    
        safelyAddToDescription(&changeDescription, modifyPieceAt: range.upperBound.pieceIndex) { piece in
          piece.startIndex = range.upperBound.contentIndex
        }
    
        applyChangeDescription(changeDescription)
      }
    }

    Does it make a difference?

    For large file sizes, yes!

    I gathered a trace of all of the edits I made to a text buffer for a couple of minutes of editing a file. I then replayed that trace on an NSTextStorage object and on a PieceTable, timing how long it took to perform all of the edits on files of different sizes. This is the result:

    DDDB752B EBA1 4DD0 84AA 36D78CA12529

    For the NSTextStorage, the time to perform the edits increases linearly with the file size. For PieceTable, however, the time to perform the edits is independent of file size; PieceTable operations will get slower as the complexity of the edit history increases.

  12. May 09, 2021

    Since deciding to focus Grail Diary on book notes, I’ve changed the app’s navigation model to be reading-focused instead of notes-focused.

    screenshot

    Next up is extending the Review Mode. Currently review mode is all about spaced repetition and active recall. However, part of the value of having your book notes all in one place is perusability — I want a review mode that makes it easy to revisit your favorite quotes. What I implemented is a mode that quizzes you on the material you are likely to forget. (I still want a spaced repetition mode! I just also want another one that’s about revisiting your favorite quotes.)

    Finally, it’s time to look for an audience for Grail Diary. I’ve long been conflicted about if I should put Grail Diary on the App Store. I don’t want to turn Grail Diary into a side hustle. That doesn’t sit right with me for some reason. However, this past week I re-read a post by Brent Simmons where he writes, “This is the age of writing iOS apps for love.” That struck a chord. I’ve been working on this app for years because I love books, I love writing apps, and Grail Diary makes my experience of reading better. Writing an app for love why I’ve decided it’s worth the work of finding an audience for Grail Diary and putting it on the app store. I know there won’t be a huge audience for this app, but I also know there is a niche somewhere. And just like my writing gets better when I get feedback, Grail Diary will become better when I find the right audience and start getting feedback. That’s my goal.

  13. April 30, 2021

    I last wrote:

    When I was working on Grail Diary, I was confused on if I was writing a digital Commonplace Book (specifically designed for storing quotes and other things you want to remember about the books you read) or if I was writing a general-purpose notes app with a spaced-repetition feature…

    I’ve been thinking about this a lot for the past few days, and I’ve made a decision: Grail Diary is going to be an app for taking notes about the books you read. That’s currently what I use it for, and I want to start evolving the app to make it as great as possible for any other book lover.

    Book notes are important enough to deserve a dedicated application! For a book lover, your book notes will be among the most important things you create in your life. Your notes help books become a part of you.

    I designed Grail Diary around three factors that make book notes different:

    • Permanent value: If you are a book lover, you can build up a reading log and notes over the course of decades. My log and notes go back over twenty years. Grail Diary uses simple plain-text markup so your notes will be readable forever, by almost any application.
    • Personal ownership: Your book notes are yours. You shouldn’t lose them when a software company goes out of business. Grail Diary works with simple files! No account, no sign-up, and you can move or copy your files wherever you want. You can use file synchronization services like iCloud Drive or Dropbox to keep your content in sync across multiple devices.
    • Perusability: The joy of writing book notes is rereading them! It’s like meeting old friends again. Grail Diary already has features to help you get reacquainted with what you’ve put in your notes, and I’ve got ideas for many more.

    Even if Grail Diary never makes it beyond “personal project,” I feel better with focus. I’m trying to decide if I want to really polish the app and put it on the app store, or if I just want to keep it as an open-source app for the motivated techies to benefit from. On the one hand, getting my own app back on the app store would be a good ultralearning project. On the other hand, I’m kind of scared to take that step. If I release the app to the app store and people don’t like it… can my ego handle it?

    That’s a decision for another day.

  14. April 25, 2021

    Three years ago today, I was reading the book Factfulness by Hans Rosling, and I wrote in my journal that I’d like a program that would add Anki-like spaced repetition to the notes I was making about the book. I wrote:

    I’m thinking of maintaining a simple text file with Markdown syntax, one bulleted line per “fact” I want to remember from a book. Markdown-underline something like this and it becomes a phrase that gets elided for an Anki card.

    That idea turned into Grail Diary, which I still use today to take notes about the books I read. The project has been a huge personal success. I write personal programs as a way to teach myself things, and by working on Grail Diary I cemented knowledge into my brain about piece tables, incremental packrat parsing, spaced repetition, sqlite, and iCloud document storage. I also have 760 prompts about the 66 books I’ve read in the past 3 years, and by regularly reviewing those cards I’ve remembered the material I’ve read these past three years way better than what I’d read for the prior 44. It was also the start of my journey into educational technology, which lead me to leave Facebook and join Duolingo.

    Of all of my side projects, Grail Diary feels like it’s got the most potential to be useful for someone other than myself. However, it’s got one huge problem at its core: When I was working on Grail Diary, I was confused on if I was writing a digital Commonplace Book (specifically designed for storing quotes and other things you want to remember about the books you read) or if I was writing a general-purpose notes app with a spaced-repetition feature. As a result, it’s this strange mishmash of features. I doubt anyone else would understand why the software in its current form behaves the way it does.

    Who knows… maybe by the time Grail Diary turns 5, I’ll have picked “Commonplace Book” or “General-purpose notes app” as the primary identity for the project and it will have another user. Time will tell!

  15. April 24, 2021

    I’m awed by Scott Young’s MIT Challenge for its simplicity and audacity. In 2011, he gave himself one year to complete the full four-year curriculum in Computer Science from MIT. MIT made most of its course material available for free online, including the tests and the answer keys, so Young could work at his own pace, at his own home, and not spend any tuition money on this experiment. He successfully finished this project in 2012. In 2019, he published the book Ultralearning, a book that helps people plan big learning projects of their own.

    Young writes that for any ultralearning project, you should budget about 10% of your time on metalearning — making a plan to identify what you need to learn and how you will go about learning it. Furthermore, he advises you to break down the what you need to learn into three buckets:

    1. New concepts that you need to understand
    2. New facts that you need to memorize
    3. New skills that you need to practice and acquire

    You do this because the techniques to efficiently learn things are different for the different categories. I’m shocked I’d never thought about this before! After reading this, I understand my own learning shortcomings much better than I did before. I love love love learning that falls in “understanding new concepts” category. I gravitated to subjects like math, physics, and computer science that are rich in first-principles conceptual understanding. However, the learning tools that help me pick up new concepts don’t help me pick up new skills or memorize things, so I struggled in subjects like foreign languages and art. I wish I’d had this book back in my high school years to know that I needed to use different tools to learn different things.

    Ultralearning also makes another important argument. As much as possible, you should structure your learning project around doing the thing you’re trying to learn how to do and you need a way to get feedback on how you are doing. Do you want to learn a language so you can speak to locals when you travel? Then you should be speaking to locals as much as you can as early as you can. (The reaction of the native speakers gives you real-time feedback!) If you want to learn jazz guitar, you need to spend a lot of time playing guitar.

    The book devotes a few pages arguing against the effectiveness of my employer, Duolingo, because it is a very indirect way to learn a language. At the same time, though, Young writes of the importance of using drills to isolate and improve specific skills for your learning project. Someone trying to improve at tennis will do more than play games; forehand / backhand / serving drills will help you isolate and improve the building block skills for the game faster than you can just from games. Duolingo plays a similar role for serious language learners. It’s not a substitute for talking to native speakers, but the app does help you drill on vocabulary and grammar. (Also! Duolingo provides way more than app-based translation exercises. You can use https://events.duolingo.com to find groups to practice speaking and listening. You can use Duolingo Podcasts for practice understanding native speakers. And perhaps most importantly, Duolingo offers learners of all levels motivation to keep learning — the hardest part of learning a new language.)

    Anyone who is interested in learning, and in particular anyone who is interested in self-directed learning, should read Ultralearning. You’ll find a ton of helpful material. For those interested in educational technology, Ultralearning suggests two things where technology seems uniquely positioned to help people learn faster and better: In providing material to practice and in feedback. All of the influential educational software I can think of — from Duolingo to Anki to Kahn Academy to experimental efforts like the “mnemonic medium” — deliver in both of these dimensions. However, I think because Ultralearning already assumes its reader is highly motivated to learn, it doesn’t say much about one of the most interesting contributions of educational technology. Successful technology makes learning fun and contains mechanisms to help sustain motivation over time.

  16. April 21, 2021

    Since I lamented about the black-box nature of performance engineering in SwiftUI two days ago, I spent some time familiarizing myself with the SwiftUI tools inside of Instruments. While I’ve made some headway, I’ve also hit a wall.

    First, some context. As I mentioned earlier, Captain’s Log is a simple habit-tracking app that I want to use as a playground for experimenting with streaks, streak freezes, and the psychology of motivation. It’s currently a document-based app that stores its data in a plain text file. Right now there are only two screens. The main screen shows a day’s status on each habit and a calendar to help visualize how each streak is going. Then, there’s a second screen to tweak any additional details for completing a habit. (For example, to prepare for exiting quarantine, I’m trying to ride my bike at least a little every day. When I record a bike ride in Captain’s Log, I track how long and how far I ride.)

    Streak Visualization

    While performance isn’t terrible, there are noticeable lags in several interactions. For the past two evenings, I wanted to eliminate one of the lags: There is a noticeable delay processing keystrokes in the edit form, with the first keystroke being the worst.

    Here’s what I learned after a few days poking around with the SwiftUI tools in Instruments.

    1. My pre-SwiftUI Instruments workflow of just looking at heaviest stack frame in Time Profiler and optimizing that doesn’t work in this case. The heaviest stacks are all deep in SwiftUI library code that I don’t understand.
    2. When debugging UI glitches, the Core Animation tool is really helpful. All of the places where I noticed that the UI was lagging, like typing characters, were visible in the Core Animation track as “long transaction commits.” For instance, before any performance optimizing, there’d be a 135ms core animation commit when processing the first keystroke in my edit form. Having these sections called out in the track let me focus specifically on what was happening at this problematic times.
    3. Paul Hudson pointed out that you can use the Hide System Libraries option in Time Profiler to quickly find bottlenecks in your code instead of the SwiftUI code. This helped! I found a couple of places where I was doing excessive calendar math when drawing the streak visualization view. However, unnecessary calendar math was only about 25% of the CPU use during the long transaction commits — the rest is SwiftUI library code. With my optimizations I got the long commit down to 100ms. Better, but still way too long for processing a keystroke.
    4. The SwiftUI View Body tool showed that my view bodies aren’t that heavy. Most compute in 2-4 microseconds. In the span of a 100ms core animation commit, I spend 0.6ms computing view bodies for my own views and a total of 2ms computing all view bodies. 98% of the time is spent somewhere else.
    5. But here’s what I don’t understand. The SwiftUI View Properties tool shows that my main FileDocument struct changes on each keystroke. And I assume because the FileDocument changes, SwiftUI recomputes everything that depends on that document (basically, all the UI in the app). On every keystroke. I don’t understand this at all. Inspecting my code, it doesn’t look like the file document should be changing on each keystroke (the text fields are backed by a separate String binding independent of the FileDocument until you tap Done). I wrote some custom Binding code and set breakpoints everywhere I could think to validate that the document is not changing on each keystroke. In spite of that, SwiftUI is convinced that it needs to recompute everything that depends on this document every time I enter a new character in a text field.

    I don’t know how to debug this further. This is exactly what I meant when I wrote earlier about the inherent tension between declarative UI frameworks and performance tuning. I’ve described what I want in my UI (“a monthly calendar with line segments showing how long I’ve maintained different streaks”). There are probably things I can do to make that “what” even more efficient. However, code I don’t understand and has don’t have access to has decided the “how” of making my app work involves recomputing that calendar on each keystroke. I don’t know how I can make the app responsive without having the ability to influence that “how.”

    Since Captain’s Log is a toy app meant for me to learn, I’m just going to leave things as is and hope that Apple provides better performance guidance and tools at WWDC 2021.

  17. April 19, 2021

    Yesterday, I wrote about streaks and motivation. To let me experiment with streaks and streak freezes, I’ve started work on a simple habit-tracking app. One of my personal goals is to become proficient in SwiftUI, so I used SwiftUI for this project.

    The good news: My project, Captain’s Log, is done “enough” for me to use it. It’s also pleasingly compact (1200 lines of code). However, I’m now wrestling with performance. This is the slowest app I’ve written in a long time, and in spite of working as an iOS performance engineer at Facebook for years, I have no idea how to make this simple program faster. The time profiler tool in Instruments shows me deep, incomprehensible stacks that have nothing obvious to do with my SwiftUI code. The new View Body and View Properties tools are a little more helpful. For instance, one performance problem I have is the app takes too long to process keystrokes. Using the new tools, it looks like my central document property updates on each keystroke, and this causes most of the app to redraw. However, I can’t figure out why this property is updating on each keystroke, nor can I tell if I’ve broken some intelligent View diffing that’s supposed to be happening. I feel stuck.

    When Apple introduced SwiftUI, they explained the difference between imperative and declarative programming with a sandwich shop metaphor. If you walk into a sandwich shop and say, “I’d like an avocado toast,” that’s like declarative programming. You’re describing what you want and you let the server figure out how to make it. To get an avocado toast imperative-style, you’d need to tell the server individual steps instead. (“First, I want you to get a slice of bread. Next, toast it for 2 minutes. Then, get a properly ripe avocado. Mush some avocado and spread it on the toast…“)

    I love this metaphor! It shows the promise of declarative frameworks — and also hints at why performance problems might be inherently harder to solve with them. Suppose I order an avocado toast at brunch, and the server disappears. 20 minutes pass. 30 minutes. Where’s my food? Since I don’t know the steps that the server takes to fulfill my order, there’s no way to figure out why things are taking so long. This seems to be the state of performance tuning in SwiftUI: You, sitting at a table, alone & hungry, wondering where your food is.

    Clearly, if I’m going to become proficient with SwiftUI, I’m going to need to learn some new performance skills. Paul Hudson has the best performance tuning guide I’ve found so far, and my next project is to see if I can use this to make Captain’s Log pleasantly snappy.

    Always new skills to learn!

  18. April 18, 2021

    Inside Duolingo, we have a saying: The hardest part about learning a new language is staying motivated. I didn’t appreciate this aspect of effective educational technology before I started working here. The best educational software will not only have great content: It will have mechanisms that help learners stay motivated to keep learning.

    Streaks are one of the most important mechanisms that Duolingo uses to keep people motivated. Streaks encourage people to do an activity a little bit every day by counting the number of consecutive days you’ve done something you care about (spent time studying a language, got some exercise, wrote in your journal, etc). Skipped a day? Your streak counter resets.

    While tons of apps use streaks, Duolingo adds one twist that, as far as I know, is unique: The streak freeze. As you use the app, you earn the ability to buy streak freezes. Each streak freeze protects your streak for one full day of inactivity. Imagine: You’ve been studying Spanish dutifully every morning before breakfast for a month. But then one day you wake up feeling a little sick, sleep in a bit to recover… and since your routine was disrupted, you forget to practice Spanish that day. Most apps will say that you broke your 30-day streak, and the streak counter will reset the next time you practice. With Duolingo, though, if you had a streak freeze active for your account, your sick day would use up that streak freeze but your streak continues.

    Streak freezes dramatically increase the length of the streak you can build. Suppose you’ve got a 99% success rate at remembering to practice on Duolingo each day. Without streak freezes, you could expect your streaks to average around 100 days before they get broken. Impressive, yes! However, if you keep your account equipped with two streak freezes, you have to miss three days in a row to break your streak. With just a little bit of care, you can keep that streak going indefinitely. (If you didn’t take care and let chance dictate your streak length: that same 1% chance of forgetting gave you 100-day streaks in a world with no streak freezes. With streak freezes, left entirely to chance, you could expect your streak to last almost 30 years.)

    Longer streak lengths tap into two motivation centers in learner’s brains.

    1. Loss aversion It just hurts so much to lose something you “own.” If you have a long streak you’ll want to keep it. Each day your streak gets longer, your brain realizes it gets harder to replace if it breaks… so you care that much more about keeping it going.
    2. Identity At some point, after practicing a language and caring for a long streak, it stops being something you do and starts being part of who you are. “I’m a person who practices languages at least a little every day.” As Angela Duckworth writes in Grit, once you make an activity part of your sense of identity it makes it much easier to stick with it because your brain stops doing cost-benefit calculations.

    I’m not surprised that so many apps try to use streaks as a motivational tool — it’s a simple concept that’s simple to implement in almost any program. Streak freezes, on the other hand, require much more design and programming work.