src/compose/table.c

   1 /*
   2  * Copyright © 2013,2021 Ran Benita <ran234@gmail.com>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include "config.h"
  25
  26 #include "utils.h"
  27 #include "table.h"
  28 #include "parser.h"
  29 #include "paths.h"
  30 #include "xkbcommon/xkbcommon.h"
  31
  32 static struct xkb_compose_table *
  33 xkb_compose_table_new(struct xkb_context *ctx,
  34                       const char *locale,
  35                       enum xkb_compose_format format,
  36                       enum xkb_compose_compile_flags flags)
  37 {
  38     char *resolved_locale;
  39     struct xkb_compose_table *table;
  40     struct compose_node dummy;
  41
  42     resolved_locale = resolve_locale(ctx, locale);
  43     if (!resolved_locale)
  44         return NULL;
  45
  46     table = calloc(1, sizeof(*table));
  47     if (!table) {
  48         free(resolved_locale);
  49         return NULL;
  50     }
  51
  52     table->refcnt = 1;
  53     table->ctx = xkb_context_ref(ctx);
  54
  55     table->locale = resolved_locale;
  56     table->format = format;
  57     table->flags = flags;
  58
  59     darray_init(table->nodes);
  60     darray_init(table->utf8);
  61
  62     dummy.keysym = XKB_KEY_NoSymbol;
  63     dummy.leaf.is_leaf = true;
  64     dummy.leaf.utf8 = 0;
  65     dummy.leaf.keysym = XKB_KEY_NoSymbol;
  66     darray_append(table->nodes, dummy);
  67
  68     darray_append(table->utf8, '\0');
  69
  70     return table;
  71 }
  72
  73 XKB_EXPORT struct xkb_compose_table *
  74 xkb_compose_table_ref(struct xkb_compose_table *table)
  75 {
  76     table->refcnt++;
  77     return table;
  78 }
  79
  80 XKB_EXPORT void
  81 xkb_compose_table_unref(struct xkb_compose_table *table)
  82 {
  83     if (!table || --table->refcnt > 0)
  84         return;
  85     free(table->locale);
  86     darray_free(table->nodes);
  87     darray_free(table->utf8);
  88     xkb_context_unref(table->ctx);
  89     free(table);
  90 }
  91
  92 XKB_EXPORT struct xkb_compose_table *
  93 xkb_compose_table_new_from_file(struct xkb_context *ctx,
  94                                 FILE *file,
  95                                 const char *locale,
  96                                 enum xkb_compose_format format,
  97                                 enum xkb_compose_compile_flags flags)
  98 {
  99     struct xkb_compose_table *table;
 100     bool ok;
 101
 102     if (flags & ~(XKB_COMPOSE_COMPILE_NO_FLAGS)) {
 103         log_err_func(ctx, "unrecognized flags: %#x\n", flags);
 104         return NULL;
 105     }
 106
 107     if (format != XKB_COMPOSE_FORMAT_TEXT_V1) {
 108         log_err_func(ctx, "unsupported compose format: %d\n", format);
 109         return NULL;
 110     }
 111
 112     table = xkb_compose_table_new(ctx, locale, format, flags);
 113     if (!table)
 114         return NULL;
 115
 116     ok = parse_file(table, file, "(unknown file)");
 117     if (!ok) {
 118         xkb_compose_table_unref(table);
 119         return NULL;
 120     }
 121
 122     return table;
 123 }
 124
 125 XKB_EXPORT struct xkb_compose_table *
 126 xkb_compose_table_new_from_buffer(struct xkb_context *ctx,
 127                                   const char *buffer, size_t length,
 128                                   const char *locale,
 129                                   enum xkb_compose_format format,
 130                                   enum xkb_compose_compile_flags flags)
 131 {
 132     struct xkb_compose_table *table;
 133     bool ok;
 134
 135     if (flags & ~(XKB_COMPOSE_COMPILE_NO_FLAGS)) {
 136         log_err_func(ctx, "unrecognized flags: %#x\n", flags);
 137         return NULL;
 138     }
 139
 140     if (format != XKB_COMPOSE_FORMAT_TEXT_V1) {
 141         log_err_func(ctx, "unsupported compose format: %d\n", format);
 142         return NULL;
 143     }
 144
 145     table = xkb_compose_table_new(ctx, locale, format, flags);
 146     if (!table)
 147         return NULL;
 148
 149     ok = parse_string(table, buffer, length, "(input string)");
 150     if (!ok) {
 151         xkb_compose_table_unref(table);
 152         return NULL;
 153     }
 154
 155     return table;
 156 }
 157
 158 XKB_EXPORT struct xkb_compose_table *
 159 xkb_compose_table_new_from_locale(struct xkb_context *ctx,
 160                                   const char *locale,
 161                                   enum xkb_compose_compile_flags flags)
 162 {
 163     struct xkb_compose_table *table;
 164     char *path;
 165     FILE *file;
 166     bool ok;
 167
 168     if (flags & ~(XKB_COMPOSE_COMPILE_NO_FLAGS)) {
 169         log_err_func(ctx, "unrecognized flags: %#x\n", flags);
 170         return NULL;
 171     }
 172
 173     table = xkb_compose_table_new(ctx, locale, XKB_COMPOSE_FORMAT_TEXT_V1,
 174                                   flags);
 175     if (!table)
 176         return NULL;
 177
 178     path = get_xcomposefile_path(ctx);
 179     if (path) {
 180         file = fopen(path, "rb");
 181         if (file)
 182             goto found_path;
 183     }
 184     free(path);
 185
 186     path = get_xdg_xcompose_file_path(ctx);
 187     if (path) {
 188         file = fopen(path, "rb");
 189         if (file)
 190             goto found_path;
 191     }
 192     free(path);
 193
 194     path = get_home_xcompose_file_path(ctx);
 195     if (path) {
 196         file = fopen(path, "rb");
 197         if (file)
 198             goto found_path;
 199     }
 200     free(path);
 201
 202     path = get_locale_compose_file_path(ctx, table->locale);
 203     if (path) {
 204         file = fopen(path, "rb");
 205         if (file)
 206             goto found_path;
 207     }
 208     free(path);
 209
 210     log_err(ctx, XKB_LOG_MESSAGE_NO_ID,
 211             "couldn't find a Compose file for locale \"%s\" (mapped to \"%s\")\n",
 212             locale, table->locale);
 213     xkb_compose_table_unref(table);
 214     return NULL;
 215
 216 found_path:
 217     ok = parse_file(table, file, path);
 218     fclose(file);
 219     if (!ok) {
 220         free(path);
 221         xkb_compose_table_unref(table);
 222         return NULL;
 223     }
 224
 225     log_dbg(ctx, XKB_LOG_MESSAGE_NO_ID,
 226             "created compose table from locale %s with path %s\n",
 227             table->locale, path);
 228
 229     free(path);
 230     return table;
 231 }
 232
 233 XKB_EXPORT const xkb_keysym_t *
 234 xkb_compose_table_entry_sequence(struct xkb_compose_table_entry *entry,
 235                                  size_t *sequence_length)
 236 {
 237     *sequence_length = entry->sequence_length;
 238     return entry->sequence;
 239 }
 240
 241 XKB_EXPORT xkb_keysym_t
 242 xkb_compose_table_entry_keysym(struct xkb_compose_table_entry *entry)
 243 {
 244     return entry->keysym;
 245 }
 246
 247 XKB_EXPORT const char *
 248 xkb_compose_table_entry_utf8(struct xkb_compose_table_entry *entry)
 249 {
 250     return entry->utf8;
 251 }
 252
 253 enum node_direction {
 254     NODE_LEFT = 0,
 255     NODE_DOWN,
 256     NODE_RIGHT,
 257     NODE_UP
 258 };
 259
 260 struct xkb_compose_table_iterator_cursor {
 261     uint32_t node_offset:30; /* WARNING: ensure it fits MAX_COMPOSE_NODES */
 262     uint8_t direction:2;     /* enum node_direction: current direction
 263                               * traversing the tree */
 264 };
 265
 266 struct xkb_compose_table_iterator {
 267     struct xkb_compose_table *table;
 268     /* Current entry */
 269     struct xkb_compose_table_entry entry;
 270     /* Stack of pending nodes to process */
 271     darray(struct xkb_compose_table_iterator_cursor) cursors;
 272 };
 273
 274 XKB_EXPORT struct xkb_compose_table_iterator *
 275 xkb_compose_table_iterator_new(struct xkb_compose_table *table)
 276 {
 277     struct xkb_compose_table_iterator *iter;
 278     struct xkb_compose_table_iterator_cursor cursor;
 279     xkb_keysym_t *sequence;
 280
 281     iter = calloc(1, sizeof(*iter));
 282     if (!iter) {
 283         return NULL;
 284     }
 285     iter->table = xkb_compose_table_ref(table);
 286     sequence = calloc(MAX_LHS_LEN, sizeof(xkb_keysym_t));
 287     if (!sequence) {
 288         free(iter);
 289         return NULL;
 290     }
 291     iter->entry.sequence = sequence;
 292     iter->entry.sequence_length = 0;
 293
 294     darray_init(iter->cursors);
 295     cursor.direction = NODE_LEFT;
 296     /* Offset 0 is a dummy null entry, skip it. */
 297     cursor.node_offset = 1;
 298     darray_append(iter->cursors, cursor);
 299
 300     return iter;
 301 }
 302
 303 XKB_EXPORT void
 304 xkb_compose_table_iterator_free(struct xkb_compose_table_iterator *iter)
 305 {
 306     xkb_compose_table_unref(iter->table);
 307     darray_free(iter->cursors);
 308     free(iter->entry.sequence);
 309     free(iter);
 310 }
 311
 312 XKB_EXPORT struct xkb_compose_table_entry *
 313 xkb_compose_table_iterator_next(struct xkb_compose_table_iterator *iter)
 314 {
 315     /*
 316      * This function takes the following recursive traversal function,
 317      * and makes it non-recursive and resumable. The iter->cursors stack
 318      * is analogous to the call stack, and cursor->direction to the
 319      * instruction pointer of a stack frame.
 320      *
 321      *    traverse(xkb_keysym_t *sequence, size_t sequence_length, uint16_t p) {
 322      *        if (!p) return
 323      *        // cursor->direction == NODE_LEFT
 324      *        node = &darray_item(table->nodes, p)
 325      *        traverse(sequence, sequence_length, node->lokid)
 326      *        // cursor->direction == NODE_DOWN
 327      *        sequence[sequence_length++] = node->keysym
 328      *        if (node->is_leaf)
 329      *            emit(sequence, sequence_length, node->leaf.keysym, table->utf[node->leaf.utf8])
 330      *        else
 331      *            traverse(sequence, sequence_length, node->internal.eqkid)
 332      *        sequence_length--
 333      *        // cursor->direction == NODE_RIGHT
 334      *        traverse(sequence, sequence_length, node->hikid)
 335      *        // cursor->direction == NODE_UP
 336      *    }
 337      */
 338
 339     struct xkb_compose_table_iterator_cursor *cursor;
 340     const struct compose_node *node;
 341
 342     while (!darray_empty(iter->cursors)) {
 343         cursor = &darray_item(iter->cursors, darray_size(iter->cursors) - 1);
 344         node = &darray_item(iter->table->nodes, cursor->node_offset);
 345
 346         switch (cursor->direction) {
 347         case NODE_LEFT:
 348             cursor->direction = NODE_DOWN;
 349             if (node->lokid) {
 350                 struct xkb_compose_table_iterator_cursor new_cursor = {node->lokid, NODE_LEFT};
 351                 darray_append(iter->cursors, new_cursor);
 352             }
 353             break;
 354
 355         case NODE_DOWN:
 356             cursor->direction = NODE_RIGHT;
 357             assert (iter->entry.sequence_length <= MAX_LHS_LEN);
 358             iter->entry.sequence[iter->entry.sequence_length] = node->keysym;
 359             iter->entry.sequence_length++;
 360             if (node->is_leaf) {
 361                 iter->entry.keysym = node->leaf.keysym;
 362                 iter->entry.utf8 = &darray_item(iter->table->utf8, node->leaf.utf8);
 363                 return &iter->entry;
 364             } else {
 365                 struct xkb_compose_table_iterator_cursor new_cursor = {node->internal.eqkid, NODE_LEFT};
 366                 darray_append(iter->cursors, new_cursor);
 367             }
 368             break;
 369
 370         case NODE_RIGHT:
 371             cursor->direction = NODE_UP;
 372             iter->entry.sequence_length--;
 373             if (node->hikid) {
 374                 struct xkb_compose_table_iterator_cursor new_cursor = {node->hikid, NODE_LEFT};
 375                 darray_append(iter->cursors, new_cursor);
 376             }
 377             break;
 378
 379         case NODE_UP:
 380             darray_remove_last(iter->cursors);
 381             break;
 382         }
 383     }
 384
 385     return NULL;
 386 }