Rustificar libipuz: conjuntos de caracteres

Translations: en - Tags: crosswords, gnome, rust

Ya son, ¿qué?, unos cuatro años desde que terminamos de portar librsvg a Rust, y ya es hora de mudar otra pieza de infraestructura crítica a un lenguaje seguro.

Me refiero a libipuz, la biblioteca en C basada en GObject que se usa para el fundamento de GNOME Crosswords. Libipuz es una biblioteca que decodifica el formato de archivos ipuz y que puede representar varios tipos de crucigramas.

Las palabras "GNOME CROSSWORDS" puestas adentro de un crucigrama

Libipuz es un bicho interesante. El formato ipuz es JSON muy peludo: tiene que representar la cuadrícula de letras y las soluciones, los números de las casillas, las pistas del crucigrama, y toda la información de estilos que puede tener un crucigrama (¡es más de lo que te imaginas!).

{
    "version": "http://ipuz.org/v2",
    "kind": [ "http://ipuz.org/crossword#1", "https://libipuz.org/barred#1" ],
    "title": "Mephisto No 3228",
    "styles": {
        "L": {"barred": "L" },
        "T": {"barred": "T" },
        "TL": {"barred": "TL" }
    },
    "puzzle":   [ [  1,  2,  0,  3,  4,  {"cell": 5, "style": "L"},  6,  0,  7,  8,  0,  9 ],
                  [  0,  {"cell": 0, "style": "L"}, {"cell": 10, "style": "TL"},  0,  0,  0,  0,  {"cell": 0, "style": "T"},  0,  0,  {"cell": 0, "style": "T"},  0 ]
                # the rest is omitted
    ],
    "clues": {
        "Across": [ {"number":1, "clue":"Having kittens means losing heart for home day", "enumeration":"5", "cells":[[0,0],[1,0],[2,0],[3,0],[4,0]] },
                    {"number":5, "clue":"Mostly allegorical poet on writing companion poem, say", "enumeration":"7", "cells":[[5,0],[6,0],[7,0],[8,0],[9,0],[10,0],[11,0]] },
                ]
        # the rest is omitted
    }
}

Libipuz utiliza json-glib, que funciona bien para decodificar el JSON a la memoria, pero luego es una completa friega destilar los nodos de ese JSON en estructuras de datos en C. Hay que iterar sobre cada uno de los nodos en el árbol de JSON y copiar sus datos a tus propias estructuras.

Dame el nodo siguiente. ¿Ese nodo es un arreglo? ¿Sí? ¿Cuántos elementos tiene? Pidamos memoria para mi propio arreglo. Iterar sobre el arreglo del nodo. ¿Qué hay en este elemento? ¿Es un número? Lo copio a mi arreglo. ¿O es una cadena? ¿Soporto eso, o devuelvo un error? No se te olvide el código para liberar meticulosamente toda la memoria en el objeto que está construido sólo a medias.

Escribir y probar ese código no es precisamente placentero.

El formato ipuz también tiene algunos mini-lenguajes como parte de las propiedades que vienen como cadenas de texto. Parsear eso en C es bastante engorroso.

Diferencias con librsvg

Mientras que librsvg tiene una API muy pequeña basada en GObject, y una biblioteca mediana debajo, libipuz tiene una API grande compuesta de GObjects, tipos boxed, y estructuras opacas y públicas. Al usar libipuz se utilizan muchas funciones desde cargar los crucigramas de disco, hasta accesar cada una de sus propiedades.

Quiero aprovechar esta rustificación como un ejercicio de portar una API en C relativamente grande a Rust. Por fortuna, libipuz sí tiene una suite de pruebas que es útil desde el principio.

También, quiero ver qué tipos de patrones aparecen al exportar cosas desde Rust que no son GObjects. Las estructuras opacas y mutables se pueden pasar sencillamente como un puntero a un bloque en la pila, i.e. un Box<T>. Quiero darme la oportunidad de hacer que más cosas en libipuz sean inmutables; ahora tiene un montón de estructuras mutables con cuenta de referencias, que son aceptables en código en C con un solo hilo de ejecución, pero que definitivamente no es lo que prefiere Rust. Para librsvg me sirvió mucho poder distinguir entre las partes de un objeto que se quedan inmutables después de construirlo, y las partes mutables que cambian a lo largo del resto de la vida del objeto.

¡Comencemos!

En el formato ipuz, los crucigramas tienen un conjunto de caracteres o charset (character set): es el conjunto de letras que aparecen en la solución del crucigrama. Las entrañas de GNOME Crosswords usan el charset como un histograma de conteos de letras* para un crucigrama en particular. Esta información es útil para los autores de crucigramas.

Crosswords usa el histograma de conteos de letras en varios algoritmos importantes, por ejemplo, en el que construye una base de datos de palabras para el editor de crucigramas. Esa base de datos tiene un formato especial que permite responder la siguiente pregunta de forma eficiente: qué palabras en la base de datos concuerdan con ?OR?? — van a concordar WORDS y CORES.

IPuzCharset es una de las partes del código en que trabajé primero en Crosswords, y luego se movió a libipuz. Al principio ni siquiera era un histograma de conteos de letras; era nada más un conjunto ordenado de caracteres que podía responder a la pregunta, "¿cuál es el índice el caracter ch dentro del conjunto ordenado?".

Ese conjunto ordenado lo implementé con un GTree, que es un árbol binario balanceado. Las llaves en las parejas llave/valor del árbol eran los caracteres, y los valores simplemente no se usaban.

Tiempo después, el conjunto ordenado se convirtió en un histograma de deveras con conteos de letras: las llaves siguen siendo caracteres, pero ahora los valores son el conteo de cada letra

Con el tiempo, Crosswords fue usando IPuzCharset para otros propósitos. Todavía se usa al construir y accesar la base de datos de palabras, pero ahora también se usa para mostrar estadísticas en el editor de crucigramas, y como parte del generador de acrósticos.

En particular, el generador de acrósticos se ha topado con problemas de desempeño en IPuzCharset. Quiero usar el port a Rust como una oportunidad para cambiar ese algoritmo y hacerlo más rápido.

Refactorizar en etapas mutable e inmutable

IPuzCharset tenía estas operaciones básicas:

/* Construcción y manejo de memoria */
IPuzCharset          *ipuz_charset_new              (void);
IPuzCharset          *ipuz_charset_ref              (IPuzCharset       *charet);
void                  ipuz_charset_unref            (IPuzCharset       *charset);

/* Mutación */
void                  ipuz_charset_add_text         (IPuzCharset       *charset,
                                                     const char        *text);
gboolean              ipuz_charset_remove_text      (IPuzCharset       *charset,
                                                     const char        *text);

/* Preguntas */
gint                  ipuz_charset_get_char_index   (const IPuzCharset *charset,
                                                     gunichar           c);
guint                 ipuz_charset_get_char_count   (const IPuzCharset *charset,
                                                     gunichar           c);
gsize                 ipuz_charset_get_n_chars      (const IPuzCharset *charset);
gsize                 ipuz_charset_get_size         (const IPuzCharset *charset);

Todo eso está implementado en términos del árbol binario con llaves/valores, que guarda un caracter en la llave de cada nodo y el conteo en cada valor.

Me puse a leer el código en Crosswords que usa las funciones ipuz_charset_*() y me di cuenta de que en todos los casos, el código primero construye y alimenta al charset usando ipuz_charset_add_text(), y ya después no lo modifica más — sólo le hace preguntas. El único lugar en donde se usa ipuz_charset_remove_text() es en el generador de acrósticos, pero ese no hace preguntas: sólo usa la operación remove_text() como parte de otro algoritmo, pero nada más.

Entonces, pensé en hacer esto:

  • Separar las etapas en un IPuzCharsetBuilder mutable que tiene las operaciones add_text / remove_text, y que también tiene una función build() que consume el builder y que produce un IPuzCharset inmutable.

  • IPuzCharset es inmutable; sólo se le pueden hacer preguntas.

  • IPuzCharsetBuilder puede utilizar una tabla de hash, que convierte la operación "añadir un caracter" de ser O(log n) a que sea O(1) amortizada.

  • build() es O(n) según el número de caracteres únicos y sólo se ejecuta una vez por charset.

  • Hacer que IPuzCharset funcione con una tabla de hash diferente que también permite operaciones O(1).

Lo principal de IPuzCharsetBuilder

IPuzCharsetBuilder es mutable, y puede vivir en el lado de Rust como un Box<T> para que se presente como un puntero en C.

#[derive(Default)]
pub struct CharsetBuilder {
    histogram: HashMap<char, u32>,
}

// IPuzCharsetBuilder *ipuz_charset_builder_new (void); */
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_builder_new() -> Box<CharsetBuilder> {
    Box::new(CharsetBuilder::default())
}

En las funciones extern "C", Box<T> se exporta como un puntero. Es lo mismo que uno obtendría por parte de malloc().

Siguen unas funciones sencillas para crear el conteo de caracteres:

impl CharsetBuilder {
    /// Añade el conteo de caracteres de `text` al histograma.
    fn add_text(&mut self, text: &str) {
        for ch in text.chars() {
            self.add_character(ch);
        }
    }

    /// Añade un solo caracter al histograma.
    fn add_character(&mut self, ch: char) {
        self.histogram
            .entry(ch)
            .and_modify(|e| *e += 1)
            .or_insert(1);
    }
}

La envoltura para la API en C:

use std::ffi::CStr;

// void ipuz_charset_builder_add_text (IPuzCharsetBuilder *builder, const char *text);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_builder_add_text(
    builder: &mut CharsetBuilder,
    text: *const c_char,
) {
    let text = CStr::from_ptr(text).to_str().unwrap();
    builder.add_text(text);
}

CStr es nuestro viejo amigo que recibe un char * y lo envuelve como un &str de Rust, después de haberlo validado como UTF-8 y de encontrar su longitud. Aquí, el unwrap() se paniquea si el string no es UTF-8, pero eso es lo que queremos; es equivalente a un assert() que revisa que el argumento sí viene en UTF-8.

// void ipuz_charset_builder_add_character (IPuzCharsetBuilder *builder, gunichar ch);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_builder_add_character(builder: &mut CharsetBuilder, ch: u32) {
    let ch = char::from_u32(ch).unwrap();
    builder.add_character(ch);
}

Por alguna razón, el huacal glib-sys no viene con gunichar, que es sencillamente un guint32 para meter un caracter Unicode. Entonces, recibimos un u32, y revisamos que esté adentro del rango de los caracteres Unicode con char::from_u32(). Una vez más, si unwrap() paniquea quiere decir que el número que recibimos está fuera de rango; equivalente a un assert().

Conversión a un IPuzCharset inmutable

pub struct Charset {
    /// Histograma de caracteres y sus conteos, además de valores derivados.
    histogram: HashMap<char, CharsetEntry>,

    /// Todos los caracteres en el histograma, pero en orden.
    ordered: String,

    /// Suma de todos los conteos de todos los caracteres.
    sum_of_counts: usize,
}

/// Datos sobre un caracter en un `Charset`.  El "valor" en una pareja llave/valor donde
/// la "llave" es un caracter.
#[derive(PartialEq)]
struct CharsetEntry {
    /// Índice del caracter dentro de la versión ordenada del `Charset`.
    index: u32,

    /// Cuántas veces aparece este caracter en el histograma.
    count: u32,
}

impl CharsetBuilder {
    fn build(self) -> Charset {
        // Se omite por brevedad; consume `self` y produce un `Charset` mediante
        // el cálculo de la suma de los conteos de caracteres para el campo `sum_of_counts`, 
        // y calcular la versión orenada de los caracteres para el campo `ordered`.
    }
}

Ahora bien, en el lado de C, IPuzCharset también debe presentarse como inmutable y con conteo de referencias. Para eso vamos a usar Arc<T>. No se puede devolver un Arc<T> al código en C; primero hay que convertirlo a un puntero con Arc::into_raw():

// IPuzCharset *ipuz_charset_builder_build (IPuzCharsetBuilder *builder);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_builder_build(
    builder: *mut CharsetBuilder,
) -> *const Charset {
    let builder = Box::from_raw(builder); // reconstruir el Box de su puntero
    let charset = builder.build();        // consumir el builder y liberarlo
    Arc::into_raw(Arc::new(charset))      // Envolver el charset en Arc y sacarle un puntero
}

Luego, implementamos ref() y unref():

// IPuzCharset *ipuz_charset_ref (IPuzCharset *charet);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_ref(charset: *const Charset) -> *const Charset {
    Arc::increment_strong_count(charset);
    charset
}

// void ipuz_charset_unref (IPuzCharset *charset);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_unref(charset: *const Charset) {
    Arc::decrement_strong_count(charset);
}

Las funciones para hacerle preguntas al charset en realidad quieren recibir un Arc<Charset> del lado de Rust. Primero tienen que reconstruir el Arc con Arc::from_raw(), y luego tienen que envolverlo en un ManuallyDrop para que el Arc no pierda una referencia cuando termine la ejecución de la función:

// gsize ipuz_charset_get_n_chars (const IPuzCharset *charset);
#[no_mangle]
pub unsafe extern "C" fn ipuz_charset_get_n_chars(charset: *const Charset) -> usize {
    let charset = ManuallyDrop::new(Arc::from_raw(charset));
    charset.get_n_chars()
}

Pruebas

Las pruebas en C permancecen intactas; esas nos permiten probar todas las envolturas que son #[no_mangle].

Del lado de Rust, podemos escribir pruebas sólo para la implementación, algo así:

    #[test]
    fn supports_histogram() {
        let mut builder = CharsetBuilder::default();

        let the_string = "ABBCCCDDDDEEEEEFFFFFFGGGGGGG";
        builder.add_text(the_string);
        let charset = builder.build();

        assert_eq!(charset.get_size(), the_string.len());

        assert_eq!(charset.get_char_count('A').unwrap(), 1);
        assert_eq!(charset.get_char_count('B').unwrap(), 2);
        assert_eq!(charset.get_char_count('C').unwrap(), 3);
        assert_eq!(charset.get_char_count('D').unwrap(), 4);
        assert_eq!(charset.get_char_count('E').unwrap(), 5);
        assert_eq!(charset.get_char_count('F').unwrap(), 6);
        assert_eq!(charset.get_char_count('G').unwrap(), 7);

        assert!(charset.get_char_count('H').is_none());
    }

Integrar al sistema de compilación

Libipuz usa meson, que no se lleva muy bien con cargo. De todas formas, cargo se puede usar desde meson con un script de envoltura y un par de hacks sencillos. Puedes ver los detalles en el merge request.

Trabajo pendiente

Dejé el archivo de encabezado en C ipuz-charset.h intacto, pero al final de cuentas me gustaría generarlo automáticamente desde Rust con la herramienta cbindgen. Hacerlo así me permite revisar que mis suposiciones sobre el ABI de extern "C" son correctas ("¿En efecto foo: &mut Foo aparece como Foo *foo en la versión en C?"), y sería un cacho en C adicional que no habría que escribirse a mano. Tengo que ver qué hacer con la documentación en línea; gi-docgen puede recibir encabezados en C perfectamente bien, pero no sé todavía cómo hacerlo funcionar con encabezados generados por cbindgen.

Aun necesito modificar los scripts de cobertura de pruebas en el CI para que soporten código mezclado en C y Rust. Por fortuna, puedo copiar los encantamientos de librsvg.

¿Y es más rápido?

¡Tal vez! Todavía no le tomo tiempos al generador de acrósticos.