src/locale-root.c

   1 /*
   2  Copyright 2015 IoT.bzh
   3
   4  author: José Bollo <jose.bollo@iot.bzh>
   5
   6  Licensed under the Apache License, Version 2.0 (the "License");
   7  you may not use this file except in compliance with the License.
   8  You may obtain a copy of the License at
   9
  10      http://www.apache.org/licenses/LICENSE-2.0
  11
  12  Unless required by applicable law or agreed to in writing, software
  13  distributed under the License is distributed on an "AS IS" BASIS,
  14  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  See the License for the specific language governing permissions and
  16  limitations under the License.
  17 */
  18
  19 #define _GNU_SOURCE
  20
  21 #include <stdlib.h>
  22 #include <stdio.h>
  23 #include <unistd.h>
  24 #include <fcntl.h>
  25 #include <errno.h>
  26 #include <assert.h>
  27 #include <limits.h>
  28 #include <string.h>
  29 #include <ctype.h>
  30 #include <sys/types.h>
  31 #include <sys/stat.h>
  32 #include <dirent.h>
  33
  34 #include "locale-root.h"
  35 #include "subpath.h"
  36
  37 /*
  38  * Implementation of folder based localisation as described here:
  39  *
  40  *    https://www.w3.org/TR/widgets/#folder-based-localization
  41  */
  42
  43 #define LRU_COUNT 3
  44
  45 static const char locales[] = "locales/";
  46
  47 struct locale_folder {
  48         struct locale_folder *parent;
  49         size_t length;
  50         char name[1];
  51 };
  52
  53 struct locale_container {
  54         size_t maxlength;
  55         size_t count;
  56         struct locale_folder **folders;
  57 };
  58
  59 struct locale_search_node {
  60         struct locale_search_node *next;
  61         struct locale_folder *folder;
  62 };
  63
  64 struct locale_root;
  65
  66 struct locale_search {
  67         struct locale_root *root;
  68         struct locale_search_node *head;
  69         int refcount;
  70         char definition[1];
  71 };
  72
  73 struct locale_root {
  74         int refcount;
  75         int intcount;
  76         int rootfd;
  77         struct locale_container container;
  78         struct locale_search *lru[LRU_COUNT];
  79         struct locale_search *default_search;
  80 };
  81
  82 /*
  83  * Clear a container content
  84  */
  85 static void clear_container(struct locale_container *container)
  86 {
  87         while(container->count)
  88                 free(container->folders[--container->count]);
  89         free(container->folders);
  90 }
  91
  92 /*
  93  * Adds a folder of name for the container
  94  */
  95 static int add_folder(struct locale_container *container, const char *name)
  96 {
  97         size_t count, length;
  98         struct locale_folder **folders;
  99
 100         count = container->count;
 101         folders = realloc(container->folders, (1 + count) * sizeof *folders);
 102         if (folders != NULL) {
 103                 container->folders = folders;
 104                 length = strlen(name);
 105                 folders[count] = malloc(sizeof **folders + length);
 106                 if (folders[count] != NULL) {
 107                         folders[count]->parent = NULL;
 108                         folders[count]->length = length;
 109                         memcpy(folders[count]->name, name, 1 + length);
 110                         container->count = count + 1;
 111                         if (length > container->maxlength)
 112                                 container->maxlength = length;
 113                         return 0;
 114                 }
 115         }
 116         clear_container(container);
 117         errno = ENOMEM;
 118         return -1;
 119 }
 120
 121 /*
 122  * Compare two folders for qsort
 123  */
 124 static int compare_folders_for_qsort(const void *a, const void *b)
 125 {
 126         const struct locale_folder * const *fa = a, * const *fb = b;
 127         return strcasecmp((*fa)->name, (*fb)->name);
 128 }
 129
 130 /*
 131  * Search for a folder
 132  */
 133 static struct locale_folder *search_folder(struct locale_container *container, const char *name, size_t length)
 134 {
 135         size_t low, high, mid;
 136         struct locale_folder *f;
 137         int c;
 138
 139         low = 0;
 140         high = container->count;
 141         while (low < high) {
 142                 mid = (low + high) >> 1;
 143                 f = container->folders[mid];
 144                 c = strncasecmp(f->name, name, length);
 145                 if (c == 0 && f->name[length] == 0)
 146                         return f;
 147                 if (c >= 0)
 148                         high = mid;
 149                 else
 150                         low = mid + 1;
 151         }
 152         return NULL;
 153 }
 154
 155 /*
 156  * Init a container
 157  */
 158 static int init_container(struct locale_container *container, int dirfd)
 159 {
 160         int rc, sfd;
 161         DIR *dir;
 162         struct dirent *dent;
 163         struct stat st;
 164         size_t i, j;
 165         struct locale_folder *f;
 166
 167         /* init the container */
 168         container->maxlength = 0;
 169         container->count = 0;
 170         container->folders = NULL;
 171
 172         /* scan the subdirs */
 173         sfd = openat(dirfd, locales, O_DIRECTORY|O_RDONLY);
 174         if (sfd == -1)
 175                 return (errno == ENOENT) - 1;
 176
 177         /* get the directory data */
 178         dir = fdopendir(sfd);
 179         if (dir == NULL) {
 180                 close(sfd);
 181                 return -1;
 182         }
 183
 184         /* enumerate the entries */
 185         for(;;) {
 186                 /* next entry */
 187                 errno = 0;
 188                 dent = readdir(dir);
 189                 if (dent == NULL) {
 190                         /* end of entries */
 191                         closedir(dir);
 192                         if (errno != 0)
 193                                 return -1;
 194                         break;
 195                 }
 196                 if (dent->d_type == DT_DIR || (dent->d_type == DT_UNKNOWN && fstatat(sfd, dent->d_name, &st, 0) == 0 && S_ISDIR(st.st_mode))) {
 197                         /* directory aka folder */
 198                         if (dent->d_name[0] == '.' && (dent->d_name[1] == 0 || (dent->d_name[1] == '.' && dent->d_name[2] == 0))) {
 199                                 /* nothing to do for special directories, basic detection, improves if needed */
 200                         } else {
 201                                 rc = add_folder(container, dent->d_name);
 202                                 if (rc < 0) {
 203                                         closedir(dir);
 204                                         return rc;
 205                                 }
 206                         }
 207                 }
 208         }
 209
 210         /* sort the folders */
 211         if (container->count)
 212                 qsort(container->folders, container->count, sizeof *container->folders, compare_folders_for_qsort);
 213
 214         /* build the parents links */
 215         i = container->count;
 216         while (i != 0) {
 217                 f = container->folders[--i];
 218                 j = strlen(f->name);
 219                 while (j != 0 && f->parent == NULL) {
 220                         if (f->name[--j] == '-')
 221                                 f->parent = search_folder(container, f->name, j);
 222                 }
 223         }
 224
 225         return rc;
 226 }
 227
 228 /*
 229  * Creates a locale root handler and returns it or return NULL
 230  * in case of memory depletion.
 231  */
 232 struct locale_root *locale_root_create(int dirfd)
 233 {
 234         struct locale_root *root;
 235         size_t i;
 236
 237         root = calloc(1, sizeof * root);
 238         if (root == NULL)
 239                 errno = ENOMEM;
 240         else {
 241                 if (init_container(&root->container, dirfd) == 0) {
 242                         root->rootfd = dirfd;
 243                         root->refcount = 1;
 244                         root->intcount = 1;
 245                         for(i = 0 ; i < LRU_COUNT ; i++)
 246                                 root->lru[i] = NULL;
 247                         root->default_search = NULL;
 248                         return root;
 249                 }
 250                 free(root);
 251         }
 252         return NULL;
 253 }
 254
 255 /*
 256  * Creates a locale root handler and returns it or return NULL
 257  * in case of memory depletion.
 258  */
 259 struct locale_root *locale_root_create_at(int dirfd, const char *path)
 260 {
 261         int fd;
 262         struct locale_root *root;
 263
 264         fd = openat(dirfd, path, O_PATH|O_DIRECTORY);
 265         if (fd < 0)
 266                 root =  NULL;
 267         else {
 268                 root = locale_root_create(fd);
 269                 if (root == NULL)
 270                         close(fd);
 271         }
 272         return root;
 273 }
 274
 275 /*
 276  * Adds a reference to 'root'
 277  */
 278 struct locale_root *locale_root_addref(struct locale_root *root)
 279 {
 280         __atomic_add_fetch(&root->refcount, 1, __ATOMIC_RELAXED);
 281         return root;
 282 }
 283
 284 /*
 285  * Drops an internal reference to 'root' and destroys it
 286  * if not more referenced
 287  */
 288 static void internal_unref(struct locale_root *root)
 289 {
 290         if (!__atomic_sub_fetch(&root->intcount, 1, __ATOMIC_RELAXED)) {
 291                 clear_container(&root->container);
 292                 close(root->rootfd);
 293                 free(root);
 294         }
 295 }
 296
 297 /*
 298  * Drops a reference to 'root' and destroys it
 299  * if not more referenced
 300  */
 301 void locale_root_unref(struct locale_root *root)
 302 {
 303         size_t i;
 304
 305         if (root && !__atomic_sub_fetch(&root->refcount, 1, __ATOMIC_RELAXED)) {
 306                 /* clear circular references through searchs */
 307                 for (i = 0 ; i < LRU_COUNT ; i++)
 308                         locale_search_unref(root->lru[i]);
 309                 /* finalize if needed */
 310                 internal_unref(root);
 311         }
 312 }
 313
 314 /*
 315  * Get the filedescriptor for the 'root' directory
 316  */
 317 int locale_root_get_dirfd(struct locale_root *root)
 318 {
 319         return root->rootfd;
 320 }
 321
 322 /*
 323  * append, if needed, a folder to the search
 324  */
 325 static int search_append_folder(struct locale_search *search, struct locale_folder *folder)
 326 {
 327         struct locale_search_node **p, *n;
 328
 329         /* search an existing node */
 330         p = &search->head;
 331         n = search->head;
 332         while(n != NULL) {
 333                 if (n->folder == folder)
 334                         return 0;
 335                 p = &n->next;
 336                 n = n->next;
 337         }
 338
 339         /* allocates a new node */
 340         n = malloc(sizeof *n);
 341         if (n == NULL) {
 342                 errno = ENOMEM;
 343                 return -1;
 344         }
 345
 346         /* init the node */
 347         *p = n;
 348         n->folder = folder;
 349         n->next = NULL;
 350         return 1;
 351 }
 352
 353 /*
 354  * construct a search for the given root and definition of length
 355  */
 356 static struct locale_search *create_search(struct locale_root *root, const char *definition, size_t length, int immediate)
 357 {
 358         struct locale_search *search;
 359         size_t stop, back;
 360         struct locale_folder *folder;
 361         struct locale_search_node *node;
 362
 363         /* allocate the structure */
 364         search = malloc(sizeof *search + length);
 365         if (search == NULL) {
 366                 errno = ENOMEM;
 367         } else {
 368                 /* init */
 369                 __atomic_add_fetch(&root->intcount, 1, __ATOMIC_RELAXED);
 370                 search->root = root;
 371                 search->head = NULL;
 372                 search->refcount = 1;
 373                 memcpy(search->definition, definition, length);
 374                 search->definition[length] = 0;
 375
 376                 /* build the search from the definition */
 377                 while(length > 0) {
 378                         stop = 0;
 379                         while(stop < length && definition[stop] != ',' && definition[stop] != ';')
 380                                 stop++;
 381                         back = stop;
 382                         while (back > 0 && (definition[back] == ' ' || definition[back] == '\t'))
 383                                 back--;
 384                         while (back > 0) {
 385                                 folder = search_folder(&root->container, definition, back);
 386                                 if (folder) {
 387                                         if (search_append_folder(search, folder) < 0) {
 388                                                 locale_search_unref(search);
 389                                                 return NULL;
 390                                         }
 391                                         if (!immediate)
 392                                                 break;
 393                                 }
 394                                 while(back > 0 && definition[--back] != '-');
 395                                 while(back > 0 && definition[back] == '-' && definition[back-1] == '-') back--;
 396                         }
 397                         while (stop < length && definition[stop] != ',')
 398                                 stop++;
 399                         while (stop < length && (definition[stop] == ',' || definition[stop] == ' ' || definition[stop] == '\t'))
 400                                 stop++;
 401                         definition += stop;
 402                         length -= stop;
 403                 }
 404
 405                 /* fullfills the search */
 406                 node = search->head;
 407                 while(node != NULL) {
 408                         folder = node->folder->parent;
 409                         if (folder != NULL) {
 410                                 if (search_append_folder(search, node->folder->parent) < 0) {
 411                                         locale_search_unref(search);
 412                                         return NULL;
 413                                 }
 414                         }
 415                         node = node->next;
 416                 }
 417         }
 418         return search;
 419 }
 420
 421 /*
 422  * Check if a possibly NUUL search matches the definition of length
 423  */
 424 static inline int search_matches(struct locale_search *search, const char *definition, size_t length)
 425 {
 426         return search != NULL && strncasecmp(search->definition, definition, length) == 0 && search->definition[length] == '\0';
 427 }
 428
 429 /*
 430  * Get an instance of search for the given root and definition
 431  * The flag immediate affects how the search is built.
 432  * For example, if the definition is "en-US,en-GB,en", the result differs depending on
 433  * immediate or not:
 434  *  when immediate==0 the search becomes "en-US,en-GB,en"
 435  *  when immediate==1 the search becomes "en-US,en,en-GB" because en-US is immediately downgraded to en
 436  */
 437 struct locale_search *locale_root_search(struct locale_root *root, const char *definition, int immediate)
 438 {
 439         char c;
 440         size_t i, length;
 441         struct locale_search *search;
 442
 443         /* normalize the definition */
 444         c = definition != NULL ? *definition : 0;
 445         while (c == ' ' || c == '\t' || c == ',')
 446                 c = *++definition;
 447         length = 0;
 448         while (c)
 449                 c = definition[++length];
 450         if (length) {
 451                 c = definition[length - 1];
 452                 while ((c == ' ' || c == '\t' || c == ',') && length)
 453                         c = definition[--length - 1];
 454         }
 455
 456         /* search lru entry */
 457         i = 0;
 458         while (i < LRU_COUNT && !search_matches(root->lru[i], definition, length))
 459                 i++;
 460
 461         /* get the entry */
 462         if (i < LRU_COUNT) {
 463                 /* use an existing one */
 464                 search = root->lru[i];
 465         } else {
 466                 /* create a new one */
 467                 search = create_search(root, definition, length, immediate);
 468                 if (search == NULL)
 469                         return NULL;
 470                 /* drop the oldest reference and update i */
 471                 locale_search_unref(root->lru[--i]);
 472         }
 473
 474         /* manage the LRU */
 475         while (i > 0) {
 476                 root->lru[i] = root->lru[i - 1];
 477                 i = i - 1;
 478         }
 479         root->lru[0] = search;
 480
 481         /* returns a new instance */
 482         return locale_search_addref(search);
 483 }
 484
 485 /*
 486  * Adds a reference to the search
 487  */
 488 struct locale_search *locale_search_addref(struct locale_search *search)
 489 {
 490         __atomic_add_fetch(&search->refcount, 1, __ATOMIC_RELAXED);
 491         return search;
 492 }
 493
 494 /*
 495  * Removes a reference from the search
 496  */
 497 void locale_search_unref(struct locale_search *search)
 498 {
 499         struct locale_search_node *it, *nx;
 500
 501         if (search && !__atomic_sub_fetch(&search->refcount, 1, __ATOMIC_RELAXED)) {
 502                 it = search->head;
 503                 while(it != NULL) {
 504                         nx = it->next;
 505                         free(it);
 506                         it = nx;
 507                 }
 508                 internal_unref(search->root);
 509                 free(search);
 510         }
 511 }
 512
 513 /*
 514  * Set the default search of 'root' to 'search'.
 515  * This search is used as fallback when other search are failing.
 516  */
 517 void locale_root_set_default_search(struct locale_root *root, struct locale_search *search)
 518 {
 519         struct locale_search *older;
 520
 521         assert(search == NULL || search->root == root);
 522
 523         older = root->default_search;
 524         root->default_search = search ? locale_search_addref(search) : NULL;
 525         locale_search_unref(older);
 526 }
 527
 528 /*
 529  * Opens 'filename' for 'search' and 'root'.
 530  *
 531  * Returns the file descriptor as returned by openat
 532  * system call or -1 in case of error.
 533  */
 534 static int do_open(struct locale_search *search, const char *filename, int flags, struct locale_root *root)
 535 {
 536         size_t maxlength, length;
 537         char *buffer, *p;
 538         struct locale_search_node *node;
 539         struct locale_folder *folder;
 540         int rootfd, fd;
 541
 542         /* check the path and normalize it */
 543         filename = subpath_force(filename);
 544         if (filename == NULL)
 545                 goto inval;
 546
 547         /* no creation flags accepted */
 548         if ((flags & O_CREAT) != 0)
 549                 goto inval;
 550
 551         /* search for folders */
 552         rootfd = root->rootfd;
 553         node = search ? search->head : NULL;
 554         if (node != NULL) {
 555                 /* allocates a buffer big enough */
 556                 maxlength = root->container.maxlength;
 557                 length = strlen(filename);
 558                 if (length > PATH_MAX)
 559                         goto inval;
 560
 561                 /* initialise the end of the buffer */
 562                 buffer = alloca(length + maxlength + sizeof locales + 1);
 563                 buffer[maxlength + sizeof locales - 1] = '/';
 564                 memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
 565
 566                 /* iterate the searched folder */
 567                 while (node != NULL) {
 568                         folder = node->folder;
 569                         p = buffer + maxlength - folder->length;
 570                         memcpy(p, locales, sizeof locales - 1);
 571                         memcpy(p + sizeof locales - 1, folder->name, folder->length);
 572                         fd = openat(rootfd, p, flags);
 573                         if (fd >= 0)
 574                                 return fd;
 575                         node = node->next;
 576                         if (node == NULL && search != root->default_search) {
 577                                 search = root->default_search;
 578                                 node = search ? search->head : NULL;
 579                         }
 580                 }
 581         }
 582
 583         /* root search */
 584         return openat(rootfd, filename, flags);
 585
 586 inval:
 587         errno = EINVAL;
 588         return -1;
 589 }
 590
 591 /*
 592  * Opens 'filename' after search.
 593  *
 594  * Returns the file descriptor as returned by openat
 595  * system call or -1 in case of error.
 596  */
 597 int locale_search_open(struct locale_search *search, const char *filename, int flags)
 598 {
 599         return do_open(search, filename, flags, search->root);
 600 }
 601
 602 /*
 603  * Opens 'filename' for root with default search.
 604  *
 605  * Returns the file descriptor as returned by openat
 606  * system call or -1 in case of error.
 607  */
 608 int locale_root_open(struct locale_root *root, const char *filename, int flags, const char *locale)
 609 {
 610         int result;
 611         struct locale_search *search;
 612
 613         search = locale != NULL ? locale_root_search(root, locale, 0) : NULL;
 614         result = do_open(search ? : root->default_search, filename, flags, root);
 615         locale_search_unref(search);
 616         return result;
 617 }
 618
 619 /*
 620  * Resolves 'filename' for 'root' and 'search'.
 621  *
 622  * returns a copy of the filename after search or NULL if not found.
 623  * the returned string MUST be freed by the caller (using free).
 624  */
 625 static char *do_resolve(struct locale_search *search, const char *filename, struct locale_root *root)
 626 {
 627         size_t maxlength, length;
 628         char *buffer, *p;
 629         struct locale_search_node *node;
 630         struct locale_folder *folder;
 631         int rootfd;
 632
 633         /* check the path and normalize it */
 634         filename = subpath_force(filename);
 635         if (filename == NULL)
 636                 goto inval;
 637
 638         /* search for folders */
 639         rootfd = root->rootfd;
 640         node = search ? search->head : NULL;
 641         if (node != NULL) {
 642                 /* allocates a buffer big enough */
 643                 maxlength = root->container.maxlength;
 644                 length = strlen(filename);
 645                 if (length > PATH_MAX)
 646                         goto inval;
 647
 648                 /* initialise the end of the buffer */
 649                 buffer = alloca(length + maxlength + sizeof locales + 1);
 650                 buffer[maxlength + sizeof locales - 1] = '/';
 651                 memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
 652
 653                 /* iterate the searched folder */
 654                 while (node != NULL) {
 655                         folder = node->folder;
 656                         p = buffer + maxlength - folder->length;
 657                         memcpy(p, locales, sizeof locales - 1);
 658                         memcpy(p + sizeof locales - 1, folder->name, folder->length);
 659                         if (0 == faccessat(rootfd, p, F_OK, 0)) {
 660                                 filename = p;
 661                                 goto found;
 662                         }
 663                         node = node->next;
 664                         if (node == NULL && search != root->default_search) {
 665                                 search = root->default_search;
 666                                 node = search ? search->head : NULL;
 667                         }
 668                 }
 669         }
 670
 671         /* root search */
 672         if (0 != faccessat(rootfd, filename, F_OK, 0)) {
 673                 errno = ENOENT;
 674                 return NULL;
 675         }
 676
 677 found:
 678         p = strdup(filename);
 679         if (p == NULL)
 680                 errno = ENOMEM;
 681         return p;
 682
 683 inval:
 684         errno = EINVAL;
 685         return NULL;
 686 }
 687
 688 /*
 689  * Resolves 'filename' at 'root' after default search.
 690  *
 691  * returns a copy of the filename after search or NULL if not found.
 692  * the returned string MUST be freed by the caller (using free).
 693  */
 694 char *locale_root_resolve(struct locale_root *root, const char *filename, const char *locale)
 695 {
 696         char *result;
 697         struct locale_search *search;
 698
 699         search = locale != NULL ? locale_root_search(root, locale, 0) : NULL;
 700         result = do_resolve(search ? : root->default_search, filename, root);
 701         locale_search_unref(search);
 702         return result;
 703 }
 704
 705 /*
 706  * Resolves 'filename' after 'search'.
 707  *
 708  * returns a copy of the filename after search or NULL if not found.
 709  * the returned string MUST be freed by the caller (using free).
 710  */
 711 char *locale_search_resolve(struct locale_search *search, const char *filename)
 712 {
 713         return do_resolve(search, filename, search->root);
 714 }
 715
 716 #if defined(TEST_locale_root)
 717 int main(int ac,char**av)
 718 {
 719         struct locale_root *root = locale_root_create(AT_FDCWD);
 720         struct locale_search *search = NULL;
 721         int fd, rc, i;
 722         char buffer[256];
 723         char *subpath;
 724         while (*++av) {
 725                 if (**av == '@') {
 726                         locale_search_unref(search);
 727                         search = NULL;
 728                         locale_root_unref(root);
 729                         root = locale_root_create(AT_FDCWD, *av + 1);
 730                         if (root == NULL)
 731                                 fprintf(stderr, "can't create root at %s: %m\n", *av + 1);
 732                         else
 733                                 printf("root: %s\n", *av + 1);
 734                 } else {
 735                         if (root == NULL) {
 736                                 fprintf(stderr, "no valid root for %s\n", *av);
 737                         } else if (**av == '-' || **av == '+') {
 738                                 locale_search_unref(search);
 739                                 search = locale_root_search(root, *av + 1, **av == '+');
 740                                 if (search == NULL)
 741                                         fprintf(stderr, "can't create search for %s: %m\n", *av + 1);
 742                                 else
 743                                         printf("search: %s\n", *av + 1);
 744                         } else if (search == NULL) {
 745                                 fprintf(stderr, "no valid search for %s\n", *av);
 746                         } else {
 747                                 fd = locale_search_open(search, *av, O_RDONLY);
 748                                 if (fd < 0)
 749                                         fprintf(stderr, "can't open file %s: %m\n", *av);
 750                                 else {
 751                                         subpath = locale_search_resolve(search, *av);
 752                                         if (subpath == NULL)
 753                                                 fprintf(stderr, "can't resolve file %s: %m\n", *av);
 754                                         else {
 755                                                 rc = (int)read(fd, buffer, sizeof buffer - 1);
 756                                                 if (rc < 0)
 757                                                         fprintf(stderr, "can't read file %s: %m\n", *av);
 758                                                 else {
 759                                                         buffer[rc] = 0;
 760                                                         *strchrnul(buffer, '\n') = 0;
 761                                                         printf("%s -> %s [%s]\n", *av, subpath, buffer);
 762                                                 }
 763                                                 free(subpath);
 764                                         }
 765                                         close(fd);
 766                                 }
 767                         }
 768                 }
 769         }
 770         locale_search_unref(search); search = NULL;
 771         locale_root_unref(root); root = NULL;
 772 }
 773 #endif
 774