Uma busca fuzzy em C++ com Turbo Modules

Na lista pesquisável filtramos com includes e usamos debounce na digitação para não filtrar a cada tecla. Vamos trocar os dois por uma busca fuzzy escrita em C++, como um C++ Turbo Module: srchlst encontra "Searchable list", e os resultados chegam no mesmo quadro da tecla.

## Por que C++ aqui

O módulo de bateria não combinava com C++: ele chama APIs da plataforma, então o código era diferente em cada lado de qualquer jeito. Uma busca fuzzy é o oposto:

É computação pura: nenhuma API da plataforma, então um só arquivo serve iOS e Android.
É um laço apertado sobre milhares de strings, rodado a cada tecla. Compilado antes, ele não aloca nada por caractere e não dá trabalho ao garbage collector.
Um C++ Turbo Module é chamado pelo JSI, de forma síncrona. search devolve um array, não uma promise, então não há quadro a esperar.

O JavaScript também é rápido. Meça antes, com a sua lista e o seu aparelho mais lento; se o filter dá conta, fique com ele.

## A forma

Num app React Native, reduzido ao que importa aqui:

specs/NativeFuzzy.ts
package.json
shared/NativeFuzzy.h
shared/NativeFuzzy.cpp
android/app/build.gradle
android/app/src/main/jni/CMakeLists.txt
android/app/src/main/jni/OnLoad.cpp
ios/NativeFuzzyProvider.h
ios/NativeFuzzyProvider.mm

## A spec

A lista passa para o C++ uma vez, com setItems. Depois, cada tecla envia só a consulta e recebe de volta os índices dos melhores resultados:

specs/NativeFuzzy.tsts

import type { TurboModule } from 'react-native';
import { TurboModuleRegistry } from 'react-native';

export interface Spec extends TurboModule {
  readonly setItems: (items: string[]) => void;
  readonly search: (query: string, limit: number) => number[];
}

export default TurboModuleRegistry.getEnforcing<Spec>('NativeFuzzy');

package.jsonjson

{
  "codegenConfig": {
    "name": "AppSpecs",
    "type": "modules",
    "jsSrcsDir": "specs",
    "android": { "javaPackageName": "com.fuzzyapp.specs" },
    "ios": { "modulesProvider": { "NativeFuzzy": "NativeFuzzyProvider" } }
  }
}

## C++

O Codegen escreve o NativeFuzzyCxxSpec, um template que o módulo estende. Os métodos recebem primeiro o runtime do JavaScript e depois os argumentos da spec como tipos C++: string[] chega como std::vector<std::string>, e um std::vector<int> volta como um array de números:

shared/NativeFuzzy.hcpp

#pragma once

#include <AppSpecsJSI.h>

#include <memory>
#include <string>
#include <vector>

namespace facebook::react {

class NativeFuzzy : public NativeFuzzyCxxSpec<NativeFuzzy> {
 public:
  explicit NativeFuzzy(std::shared_ptr<CallInvoker> jsInvoker);

  void setItems(jsi::Runtime& rt, std::vector<std::string> items);
  std::vector<int> search(jsi::Runtime& rt, std::string query, int limit);

 private:
  std::vector<std::string> items_;
};

} // namespace facebook::react

O matcher percorre cada item uma vez, procurando as letras da consulta em ordem. Uma letra vale mais quando vem logo depois da anterior, e mais ainda no começo de uma palavra; um item longo perde um pouco, então "List" vence "A long list of settings":

shared/NativeFuzzy.cppcpp

#include "NativeFuzzy.h"

#include <algorithm>
#include <utility>

namespace facebook::react {

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

NativeFuzzy::NativeFuzzy(std::shared_ptr<CallInvoker> jsInvoker)
    : NativeFuzzyCxxSpec(std::move(jsInvoker)) {}

void NativeFuzzy::setItems(jsi::Runtime&, std::vector<std::string> items) {
  items_ = std::move(items);
}

std::vector<int> NativeFuzzy::search(jsi::Runtime&, std::string query, int 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)));
  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<int> best;
  best.reserve(count);
  for (size_t k = 0; k < count; k++) best.push_back(hits[k].second);
  return best;
}

} // namespace facebook::react

O matcher é guloso: ele pega a primeira ocorrência de cada letra, o que é rápido e bom o bastante para uma lista de nomes. Toda chamada roda na thread do JavaScript, então items_ não precisa de lock.

## Android

O Gradle compila o C++ pelo CMake. O build.gradle aponta para o arquivo do CMake:

android/app/build.gradlegroovy

android {
  externalNativeBuild {
    cmake {
      path "src/main/jni/CMakeLists.txt"
    }
  }
}

O arquivo do CMake acrescenta shared/ à biblioteca que o React Native já compila para o app:

android/app/src/main/jni/CMakeLists.txtcmake

cmake_minimum_required(VERSION 3.13)
project(appmodules)

include(${REACT_ANDROID_DIR}/cmake-utils/ReactNative-application.cmake)

target_sources(${CMAKE_PROJECT_NAME} PRIVATE ../../../../../shared/NativeFuzzy.cpp)
target_include_directories(${CMAKE_PROJECT_NAME} PUBLIC ../../../../../shared)

O OnLoad.cpp é copiado do template do React Native da sua versão. Só o provedor de módulos C++ muda, para entregar o módulo pelo nome:

android/app/src/main/jni/OnLoad.cppcpp

#include <NativeFuzzy.h>

std::shared_ptr<TurboModule> cxxModuleProvider(
    const std::string& name,
    const std::shared_ptr<CallInvoker>& jsInvoker) {
  if (name == NativeFuzzy::kModuleName) {
    return std::make_shared<NativeFuzzy>(jsInvoker);
  }
  return autolinking_cxxModuleProvider(name, jsInvoker);
}

Nada de Kotlin.

## iOS

O Xcode compila shared/ depois que a pasta é adicionada ao target do app. Um provider pequeno, citado no package.json, cria o módulo:

ios/NativeFuzzyProvider.hobjective-c

#import <Foundation/Foundation.h>
#import <ReactCommon/RCTTurboModule.h>

NS_ASSUME_NONNULL_BEGIN

@interface NativeFuzzyProvider : NSObject <RCTModuleProvider>
@end

NS_ASSUME_NONNULL_END

ios/NativeFuzzyProvider.mmobjective-cpp

#import "NativeFuzzyProvider.h"
#import <ReactCommon/CallInvoker.h>
#import <ReactCommon/TurboModule.h>
#import "NativeFuzzy.h"

@implementation NativeFuzzyProvider

- (std::shared_ptr<facebook::react::TurboModule>)getTurboModule:
    (const facebook::react::ObjCTurboModule::InitParams &)params {
  return std::make_shared<facebook::react::NativeFuzzy>(params.jsInvoker);
}

@end

Nem de Swift: os dois arquivos são cola, e a busca é o mesmo C++ nas duas plataformas.

## TypeScript

O hook entrega os títulos quando a lista muda e busca durante o render. search é síncrono, então o debounce da lista pesquisável pode sair:

useFuzzy.tsts

import { useMemo } from 'react';
import NativeFuzzy from './specs/NativeFuzzy';

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

export function useFuzzy(items: Item[], query: string, limit = 50): Item[] {
  // setItems só substitui a lista, então rodá-lo de novo com os mesmos itens não faz mal.
  const loaded = useMemo(() => {
    NativeFuzzy.setItems(items.map((item) => item.title));
    return items;
  }, [items]);

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

O módulo guarda uma lista. É tudo de que esta tela precisa; duas telas buscando ao mesmo tempo pediriam uma lista por id.

No SearchScreen, as linhas do useDebounced e do useMemo viram uma só:

SearchScreen.tsxtsx

const visible = useFuzzy(items, state.query);

## Rode

O Codegen roda no pod install e no Gradle, então o header da spec em C++ existe antes de o C++ ser compilado:

cd ios && bundle exec pod install && cd ..
npx react-native run-ios
npx react-native run-android

O C++ merece o lugar quando o trabalho é computação, igual em toda plataforma, e chamado com frequência suficiente para que um quadro importe. Para o que conversa com a plataforma, Swift e Kotlin continuam as melhores ferramentas. A documentação do React Native sobre C++ Turbo Native Modules cobre mais tipos, incluindo os seus próprios.

# Uma busca fuzzy em C++ com Turbo Modules