A fuzzy search in C++ with Nitro Modules

In the last post we wrote a fuzzy search in C++ as a Turbo Module. The matcher was one file, but around it sat a file of glue per platform: OnLoad.cpp and CMake on Android, an Objective-C++ provider on iOS. And the module held a single list for the whole app.

Let's write the same search with Nitro Modules. Nitro can implement a spec in C++ on both platforms, and its autolinking registers it, so the glue goes away. A hybrid object is an object, too: each list gets a searcher of its own.

## Create the module

npx nitrogen@latest init react-native-fuzzy

Trimmed to what matters here:

react-native-fuzzy/
  nitro.json
  src/specs/Fuzzy.nitro.ts
  src/index.ts
  cpp/HybridFuzzy.hpp
  cpp/HybridFuzzy.cpp
  nitrogen/generated/

There is no ios/ or android/ code of our own: the template builds cpp/ on both platforms, and nitro.json names the C++ class that implements the spec:

nitro.jsonjson

{
  "cxxNamespace": ["fuzzy"],
  "ios": { "iosModuleName": "NitroFuzzy" },
  "android": {
    "androidNamespace": ["fuzzy"],
    "androidCxxLibName": "NitroFuzzy"
  },
  "autolinking": {
    "Fuzzy": { "cpp": "HybridFuzzy" }
  }
}

## The spec

The same two methods as before. c++ on both platforms tells Nitrogen there is no Swift or Kotlin to generate for:

src/specs/Fuzzy.nitro.tsts

import type { HybridObject } from 'react-native-nitro-modules';

export interface Fuzzy extends HybridObject<{ ios: 'c++'; android: 'c++' }> {
  setItems(items: string[]): void;
  search(query: string, limit: number): number[];
}

npx nitrogen

Nitrogen writes HybridFuzzySpec, a C++ class with a pure virtual method for each one in the spec. The types are plain C++: string[] is a std::vector<std::string>, and number is a double. No jsi::Runtime in sight.

## C++

The class overrides the spec's methods. Its constructor names the object for Nitro's logs, and getExternalMemorySize tells the JavaScript garbage collector how much native memory it holds, so a large list is collected in time once nothing refers to it:

cpp/HybridFuzzy.hppcpp

#pragma once

#include "HybridFuzzySpec.hpp"

#include <string>
#include <vector>

namespace margelo::nitro::fuzzy {

class HybridFuzzy : public HybridFuzzySpec {
 public:
  HybridFuzzy() : HybridObject(TAG) {}

  void setItems(const std::vector<std::string>& items) override;
  std::vector<double> search(const std::string& query, double limit) override;

  size_t getExternalMemorySize() noexcept override;

 private:
  std::vector<std::string> items_;
  size_t bytes_ = 0;
};

} // namespace margelo::nitro::fuzzy

The matcher is the one from the Turbo Module, word for word. Only the edges change: the arguments arrive as const references, and the indexes go back as double:

cpp/HybridFuzzy.cppcpp

#include "HybridFuzzy.hpp"

#include <algorithm>
#include <utility>

namespace margelo::nitro::fuzzy {

namespace {

// ASCII lower case; other bytes pass through, so UTF-8 still matches itself.
char lower(char c) {
  return c >= 'A' && c <= 'Z' ? static_cast<char>(c + ('a' - 'A')) : c;
}

bool startsWord(const std::string& text, size_t i) {
  if (i == 0) return true;
  char before = text[i - 1];
  return before == ' ' || before == '-' || before == '_' || before == '/';
}

// The query's letters in the item, in order: a score, or -1 when one is missing.
int score(const std::string& query, const std::string& item) {
  int total = 0;
  int streak = 0;
  size_t found = 0;
  for (size_t i = 0; i < item.size() && found < query.size(); i++) {
    if (lower(item[i]) != query[found]) {
      streak = 0;
      continue;
    }
    streak++;
    total += 1 + 2 * streak + (startsWord(item, i) ? 8 : 0);
    found++;
  }
  if (found < query.size()) return -1;
  return total - static_cast<int>(item.size() / 8);
}

} // namespace

void HybridFuzzy::setItems(const std::vector<std::string>& items) {
  items_ = items;
  bytes_ = 0;
  for (const auto& item : items_) bytes_ += sizeof(std::string) + item.capacity();
}

std::vector<double> HybridFuzzy::search(const std::string& query, double limit) {
  std::string q;
  q.reserve(query.size());
  for (char c : query) {
    if (c != ' ') q.push_back(lower(c));
  }

  // (score, index) for every item that has all the letters.
  std::vector<std::pair<int, int>> hits;
  hits.reserve(items_.size());
  for (int i = 0; i < static_cast<int>(items_.size()); i++) {
    int s = score(q, items_[i]);
    if (s >= 0) hits.emplace_back(s, i);
  }

  // Only the best `limit` are sorted: a short screen of a long list costs little.
  auto count = std::min(hits.size(), static_cast<size_t>(std::max(limit, 0.0)));
  std::partial_sort(hits.begin(), hits.begin() + count, hits.end(), [](const auto& a, const auto& b) {
    return a.first != b.first ? a.first > b.first : a.second < b.second;
  });

  std::vector<double> best;
  best.reserve(count);
  for (size_t k = 0; k < count; k++) best.push_back(static_cast<double>(hits[k].second));
  return best;
}

size_t HybridFuzzy::getExternalMemorySize() noexcept {
  return bytes_;
}

} // namespace margelo::nitro::fuzzy

Calls still run on the JavaScript thread, synchronously, so items_ needs no lock. For a list so long that one search takes more than a frame, the spec could return a Promise<number[]> instead, and the C++ run it on another thread.

## TypeScript

The module's entry hands out a new searcher on each call:

src/index.tsts

import { NitroModules } from 'react-native-nitro-modules';
import type { Fuzzy } from './specs/Fuzzy.nitro';

export type { Fuzzy };

export function createFuzzy(): Fuzzy {
  return NitroModules.createHybridObject<Fuzzy>('Fuzzy');
}

So the hook keeps one per component. Two screens searching two lists no longer share anything, and a searcher goes away with its component:

useFuzzy.tsts

import { useMemo, useState } from 'react';
import { createFuzzy } from 'react-native-fuzzy';

type Item = { id: string; title: string };

export function useFuzzy(items: Item[], query: string, limit = 50): Item[] {
  const [fuzzy] = useState(createFuzzy);

  // setItems only replaces the list, so running it again for the same items is harmless.
  const loaded = useMemo(() => {
    fuzzy.setItems(items.map((item) => item.title));
    return items;
  }, [fuzzy, items]);

  return useMemo(
    () => (query.trim() ? fuzzy.search(query, limit).map((i) => loaded[i]) : loaded),
    [fuzzy, loaded, query, limit],
  );
}

SearchScreen does not change: useFuzzy(items, state.query) is the same call as with the Turbo Module.

## Run it

npm install react-native-nitro-modules ./react-native-fuzzy
cd ios && bundle exec pod install && cd ..
npx react-native run-ios
npx react-native run-android

## Turbo or Nitro, for C++

Turbo Modules: nothing beyond React Native. In return, each platform needs its glue, the module is one per app, and its methods take the jsi::Runtime.
Nitro Modules: the same C++ with no glue, plain C++ types, an object per list, and a way to tell the garbage collector what it holds. In return, a dependency and a generator to run yourself.

The matcher did not change at all between the two. That is the point of writing it in C++: the logic stays, and only the edges move. The Nitro docs cover more C++ types, including callbacks and Promise.

# A fuzzy search in C++ with Nitro Modules