Flexible String tokenization in Swift

Question

I want a flexible and fast way to break a string up into strongly typed tokens so that I can do things like the following:

let sampleText = "~~~hello12.34\n\n100,000.00~~~world~~~"

let tokens = Tokenizer<NumberOrWord>.tokens(from: sampleText)
// tokens => (pseudo output)
// [(word   'hello' at range 3, 8),
//  (number 12.34   at range 8, 13),
//  (number 100000  at range 15, 25),
//  (word   'world' at range 28, 33)]

I started out using Foundation's Scanner but found some limitations with some erratic behaviour dealing with excluding characters (and Scanner doesn't give me ranges which is also important).

So I've ended up creating a generic Tokenizer type that works with a TokenType to figure out how to split up some example text:

protocol TokenType {
    // create a token from a string
    init?(from firstCharacter: UnicodeScalar)

    // return valid characters for this token type
    var characters: CharacterSet { get }
}

struct Tokenizer<Token: TokenType> {

    typealias Match = (type: Token, text: String, range: Range<String.Index>)

    static func tokens(from text: String) -> [Match] {

        var matches: [Match] = []

        // tokenizer moves through text by adjusting lower and upper bounds,
        // start by setting lower bound to the start of the text
        var lowerBound = text.startIndex

        while lowerBound < text.endIndex {

            // get the character at the lower bounds, and the type of token to start matching
            // based on that character
            guard let firstCharacter = text[lowerBound...lowerBound].unicodeScalars.first,
                let tokenType = Token(from: firstCharacter) else {

                    // if the character doesn't match a token, then skip ahead to next character
                    lowerBound = text.index(after: lowerBound)
                    continue
            }

            // start by setting upper bound to the lower bound position...
            var upperBound = lowerBound
            while upperBound <= text.endIndex {

                // if there is a next character in the text
                // and the next character is a valid character for the current token type \
                // then extend the upper bounds by one position
                if upperBound < text.endIndex, let nextCharacter = text[upperBound...upperBound].unicodeScalars.first,
                    tokenType.characters.contains(nextCharacter) {

                    upperBound = text.index(after: upperBound)
                }
                    // otherwise we've hit a boundary, so add the token in the current range
                else {
                    matches.append((type: tokenType,
                                    text: text[lowerBound..<upperBound],
                                    range: lowerBound..<upperBound))
                    break
                }
            }
            // increment the lower bounds to the upper bounds
            lowerBound = upperBound
        }
        return matches
    }
}

Here's an example implementation of a NumberOrWord token type:

func ~= (pattern: CharacterSet, value: UnicodeScalar) -> Bool {
    return pattern.contains(value)
}

enum NumberOrWord: TokenType {

    case number
    case word

    static let numberCharacters = CharacterSet.decimalDigits.union(CharacterSet(charactersIn: ".,"))
    static let wordCharacters = CharacterSet.letters.union(.punctuationCharacters)

    var characters: CharacterSet {
        switch self {
        case .number: return NumberOrWord.numberCharacters
        case .word: return NumberOrWord.wordCharacters
        }
    }

    // using `~=` for pattern matching of charater set to character
    // using more limited character sets for first match (slightly faster?)
    // also has consequence of being stricter match e.g. to represent 0.5 as number need to have the leading zero
    init?(from firstCharacter: UnicodeScalar) {
        switch firstCharacter {
        case CharacterSet.decimalDigits: self = .number
        case CharacterSet.letters: self = .word
        default: return nil
        }
    }
}

Which works as expected to separate words from numbers, and return the bounds of each token:

let sampleText = "~~~hello12.34\n\n100,000.00~~~world~~~"

let tokens = Tokenizer<NumberOrWord>.tokens(from: sampleText)
// tokens =>
// [(type: word,   text: "hello",      range: Range<String.Index>(3, 8)),
//  (type: number, text: "12.34"       range: Range<String.Index>(8, 13),
//  (type: number, text: "100,000.00", range: Range<String.Index>(15, 25),
//  (type: word,   text: "world",      range: Range<String.Index>(28, 33)]

I've tried to make this fast by exploring the text by adjusting string indexes, but would be great to get a second (or third) pair of eyes and would be great to hear anyone's opinion on this approach, or ideas to improve that I can learn from!

Answer 1

After spending more time looking at this I've realized that my sample code wasn't even working for all cases.

I've switched from iterating over characters to iterating over scalars, so instead of:

var lowerBound = text.startIndex
//...
let firstCharacter = text[lowerBound...lowerBound].unicodeScalars.first

I not just access from the scalar view directly:

var lowerBound = text.unicodeScalars.startIndex
//...
let firstScalar = text.unicodeScalars[lowerBound]

For the first time I'm also experimenting with labelling the inner and outer loop statements so that I can write continue advanceTokenStart which in my case (I ended up with three nested loops) I think improves readability a lot.

I also realized that the general approach I was using by setting up Tokenizer to work with generic a TokenType didn't really make sense so I've ended up taking a different approach.

If anyone's still interested I have updates available at http://github.com/mathewsanders/Mustard where any feedback would still always be appreciated!