src/locale-root.c

   1 /*
   2  Copyright (C) 2015-2019 "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[];
  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[];
  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 + 1 + 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 = 0, 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                 rc = fstatat(sfd, dent->d_name, &st, 0);
 197                 if (rc == 0 && S_ISDIR(st.st_mode)) {
 198                         /* directory aka folder */
 199                         if (dent->d_name[0] == '.' && (dent->d_name[1] == 0 || (dent->d_name[1] == '.' && dent->d_name[2] == 0))) {
 200                                 /* nothing to do for special directories, basic detection, improves if needed */
 201                         } else {
 202                                 rc = add_folder(container, dent->d_name);
 203                                 if (rc < 0) {
 204                                         closedir(dir);
 205                                         return rc;
 206                                 }
 207                         }
 208                 }
 209         }
 210
 211         /* sort the folders */
 212         if (container->count)
 213                 qsort(container->folders, container->count, sizeof *container->folders, compare_folders_for_qsort);
 214
 215         /* build the parents links */
 216         i = container->count;
 217         while (i != 0) {
 218                 f = container->folders[--i];
 219                 j = strlen(f->name);
 220                 while (j != 0 && f->parent == NULL) {
 221                         if (f->name[--j] == '-')
 222                                 f->parent = search_folder(container, f->name, j);
 223                 }
 224         }
 225
 226         return rc;
 227 }
 228
 229 /*
 230  * Creates a locale root handler and returns it or return NULL
 231  * in case of memory depletion.
 232  */
 233 struct locale_root *locale_root_create(int dirfd)
 234 {
 235         struct locale_root *root;
 236         size_t i;
 237
 238         root = calloc(1, sizeof * root);
 239         if (root == NULL)
 240                 errno = ENOMEM;
 241         else {
 242                 if (init_container(&root->container, dirfd) == 0) {
 243                         root->rootfd = dirfd;
 244                         root->refcount = 1;
 245                         root->intcount = 1;
 246                         for(i = 0 ; i < LRU_COUNT ; i++)
 247                                 root->lru[i] = NULL;
 248                         root->default_search = NULL;
 249                         return root;
 250                 }
 251                 free(root);
 252         }
 253         return NULL;
 254 }
 255
 256 /*
 257  * Creates a locale root handler and returns it or return NULL
 258  * in case of memory depletion.
 259  */
 260 struct locale_root *locale_root_create_at(int dirfd, const char *path)
 261 {
 262         int fd;
 263         struct locale_root *root;
 264
 265         fd = openat(dirfd, path, O_PATH|O_DIRECTORY);
 266         if (fd < 0)
 267                 root =  NULL;
 268         else {
 269                 root = locale_root_create(fd);
 270                 if (root == NULL)
 271                         close(fd);
 272         }
 273         return root;
 274 }
 275
 276 /*
 277  * Adds a reference to 'root'
 278  */
 279 struct locale_root *locale_root_addref(struct locale_root *root)
 280 {
 281         __atomic_add_fetch(&root->refcount, 1, __ATOMIC_RELAXED);
 282         return root;
 283 }
 284
 285 /*
 286  * Drops an internal reference to 'root' and destroys it
 287  * if not more referenced
 288  */
 289 static void internal_unref(struct locale_root *root)
 290 {
 291         if (!__atomic_sub_fetch(&root->intcount, 1, __ATOMIC_RELAXED)) {
 292                 clear_container(&root->container);
 293                 close(root->rootfd);
 294                 free(root);
 295         }
 296 }
 297
 298 /*
 299  * Drops a reference to 'root' and destroys it
 300  * if not more referenced
 301  */
 302 void locale_root_unref(struct locale_root *root)
 303 {
 304         size_t i;
 305
 306         if (root && !__atomic_sub_fetch(&root->refcount, 1, __ATOMIC_RELAXED)) {
 307                 /* clear circular references through searchs */
 308                 for (i = 0 ; i < LRU_COUNT ; i++)
 309                         locale_search_unref(root->lru[i]);
 310                 /* finalize if needed */
 311                 internal_unref(root);
 312         }
 313 }
 314
 315 /*
 316  * Get the filedescriptor for the 'root' directory
 317  */
 318 int locale_root_get_dirfd(struct locale_root *root)
 319 {
 320         return root->rootfd;
 321 }
 322
 323 /*
 324  * append, if needed, a folder to the search
 325  */
 326 static int search_append_folder(struct locale_search *search, struct locale_folder *folder)
 327 {
 328         struct locale_search_node **p, *n;
 329
 330         /* search an existing node */
 331         p = &search->head;
 332         n = search->head;
 333         while(n != NULL) {
 334                 if (n->folder == folder)
 335                         return 0;
 336                 p = &n->next;
 337                 n = n->next;
 338         }
 339
 340         /* allocates a new node */
 341         n = malloc(sizeof *n);
 342         if (n == NULL) {
 343                 errno = ENOMEM;
 344                 return -1;
 345         }
 346
 347         /* init the node */
 348         *p = n;
 349         n->folder = folder;
 350         n->next = NULL;
 351         return 1;
 352 }
 353
 354 /*
 355  * construct a search for the given root and definition of length
 356  */
 357 static struct locale_search *create_search(struct locale_root *root, const char *definition, size_t length, int immediate)
 358 {
 359         struct locale_search *search;
 360         size_t stop, back;
 361         struct locale_folder *folder;
 362         struct locale_search_node *node;
 363
 364         /* allocate the structure */
 365         search = malloc(sizeof *search + 1 + length);
 366         if (search == NULL) {
 367                 errno = ENOMEM;
 368         } else {
 369                 /* init */
 370                 __atomic_add_fetch(&root->intcount, 1, __ATOMIC_RELAXED);
 371                 search->root = root;
 372                 search->head = NULL;
 373                 search->refcount = 1;
 374                 memcpy(search->definition, definition, length);
 375                 search->definition[length] = 0;
 376
 377                 /* build the search from the definition */
 378                 while(length > 0) {
 379                         stop = 0;
 380                         while(stop < length && definition[stop] != ',' && definition[stop] != ';')
 381                                 stop++;
 382                         back = stop;
 383                         while (back > 0 && (definition[back] == ' ' || definition[back] == '\t'))
 384                                 back--;
 385                         while (back > 0) {
 386                                 folder = search_folder(&root->container, definition, back);
 387                                 if (folder) {
 388                                         if (search_append_folder(search, folder) < 0) {
 389                                                 locale_search_unref(search);
 390                                                 return NULL;
 391                                         }
 392                                         if (!immediate)
 393                                                 break;
 394                                 }
 395                                 while(back > 0 && definition[--back] != '-');
 396                                 while(back > 0 && definition[back] == '-' && definition[back-1] == '-') back--;
 397                         }
 398                         while (stop < length && definition[stop] != ',')
 399                                 stop++;
 400                         while (stop < length && (definition[stop] == ',' || definition[stop] == ' ' || definition[stop] == '\t'))
 401                                 stop++;
 402                         definition += stop;
 403                         length -= stop;
 404                 }
 405
 406                 /* fullfills the search */
 407                 node = search->head;
 408                 while(node != NULL) {
 409                         folder = node->folder->parent;
 410                         if (folder != NULL) {
 411                                 if (search_append_folder(search, node->folder->parent) < 0) {
 412                                         locale_search_unref(search);
 413                                         return NULL;
 414                                 }
 415                         }
 416                         node = node->next;
 417                 }
 418         }
 419         return search;
 420 }
 421
 422 /*
 423  * Check if a possibly NUUL search matches the definition of length
 424  */
 425 static inline int search_matches(struct locale_search *search, const char *definition, size_t length)
 426 {
 427         return search != NULL && strncasecmp(search->definition, definition, length) == 0 && search->definition[length] == '\0';
 428 }
 429
 430 /*
 431  * Get an instance of search for the given root and definition
 432  * The flag immediate affects how the search is built.
 433  * For example, if the definition is "en-US,en-GB,en", the result differs depending on
 434  * immediate or not:
 435  *  when immediate==0 the search becomes "en-US,en-GB,en"
 436  *  when immediate==1 the search becomes "en-US,en,en-GB" because en-US is immediately downgraded to en
 437  */
 438 struct locale_search *locale_root_search(struct locale_root *root, const char *definition, int immediate)
 439 {
 440         char c;
 441         size_t i, length;
 442         struct locale_search *search;
 443
 444         /* normalize the definition */
 445         c = definition != NULL ? *definition : 0;
 446         while (c == ' ' || c == '\t' || c == ',')
 447                 c = *++definition;
 448         length = 0;
 449         while (c)
 450                 c = definition[++length];
 451         if (length) {
 452                 c = definition[length - 1];
 453                 while ((c == ' ' || c == '\t' || c == ',') && length)
 454                         c = definition[--length - 1];
 455         }
 456
 457         /* search lru entry */
 458         i = 0;
 459         while (i < LRU_COUNT && !search_matches(root->lru[i], definition, length))
 460                 i++;
 461
 462         /* get the entry */
 463         if (i < LRU_COUNT) {
 464                 /* use an existing one */
 465                 search = root->lru[i];
 466         } else {
 467                 /* create a new one */
 468                 search = create_search(root, definition, length, immediate);
 469                 if (search == NULL)
 470                         return NULL;
 471                 /* drop the oldest reference and update i */
 472                 locale_search_unref(root->lru[--i]);
 473         }
 474
 475         /* manage the LRU */
 476         while (i > 0) {
 477                 root->lru[i] = root->lru[i - 1];
 478                 i = i - 1;
 479         }
 480         root->lru[0] = search;
 481
 482         /* returns a new instance */
 483         return locale_search_addref(search);
 484 }
 485
 486 /*
 487  * Adds a reference to the search
 488  */
 489 struct locale_search *locale_search_addref(struct locale_search *search)
 490 {
 491         __atomic_add_fetch(&search->refcount, 1, __ATOMIC_RELAXED);
 492         return search;
 493 }
 494
 495 /*
 496  * Removes a reference from the search
 497  */
 498 void locale_search_unref(struct locale_search *search)
 499 {
 500         struct locale_search_node *it, *nx;
 501
 502         if (search && !__atomic_sub_fetch(&search->refcount, 1, __ATOMIC_RELAXED)) {
 503                 it = search->head;
 504                 while(it != NULL) {
 505                         nx = it->next;
 506                         free(it);
 507                         it = nx;
 508                 }
 509                 internal_unref(search->root);
 510                 free(search);
 511         }
 512 }
 513
 514 /*
 515  * Set the default search of 'root' to 'search'.
 516  * This search is used as fallback when other search are failing.
 517  */
 518 void locale_root_set_default_search(struct locale_root *root, struct locale_search *search)
 519 {
 520         struct locale_search *older;
 521
 522         assert(search == NULL || search->root == root);
 523
 524         older = root->default_search;
 525         root->default_search = search ? locale_search_addref(search) : NULL;
 526         locale_search_unref(older);
 527 }
 528
 529 /*
 530  * Opens 'filename' for 'search' and 'root'.
 531  *
 532  * Returns the file descriptor as returned by openat
 533  * system call or -1 in case of error.
 534  */
 535 static int do_open(struct locale_search *search, const char *filename, int flags, struct locale_root *root)
 536 {
 537         size_t maxlength, length;
 538         char *buffer, *p;
 539         struct locale_search_node *node;
 540         struct locale_folder *folder;
 541         int rootfd, fd;
 542
 543         /* check the path and normalize it */
 544         filename = subpath_force(filename);
 545         if (filename == NULL)
 546                 goto inval;
 547
 548         /* no creation flags accepted */
 549         if ((flags & O_CREAT) != 0)
 550                 goto inval;
 551
 552         /* search for folders */
 553         rootfd = root->rootfd;
 554         node = search ? search->head : NULL;
 555         if (node != NULL) {
 556                 /* allocates a buffer big enough */
 557                 maxlength = root->container.maxlength;
 558                 length = strlen(filename);
 559                 if (length > PATH_MAX)
 560                         goto inval;
 561
 562                 /* initialise the end of the buffer */
 563                 buffer = alloca(length + maxlength + sizeof locales + 1);
 564                 buffer[maxlength + sizeof locales - 1] = '/';
 565                 memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
 566
 567                 /* iterate the searched folder */
 568                 while (node != NULL) {
 569                         folder = node->folder;
 570                         p = buffer + maxlength - folder->length;
 571                         memcpy(p, locales, sizeof locales - 1);
 572                         memcpy(p + sizeof locales - 1, folder->name, folder->length);
 573                         fd = openat(rootfd, p, flags);
 574                         if (fd >= 0)
 575                                 return fd;
 576                         node = node->next;
 577                         if (node == NULL && search != root->default_search) {
 578                                 search = root->default_search;
 579                                 node = search ? search->head : NULL;
 580                         }
 581                 }
 582         }
 583
 584         /* root search */
 585         return openat(rootfd, filename, flags);
 586
 587 inval:
 588         errno = EINVAL;
 589         return -1;
 590 }
 591
 592 /*
 593  * Opens 'filename' after search.
 594  *
 595  * Returns the file descriptor as returned by openat
 596  * system call or -1 in case of error.
 597  */
 598 int locale_search_open(struct locale_search *search, const char *filename, int flags)
 599 {
 600         return do_open(search, filename, flags, search->root);
 601 }
 602
 603 /*
 604  * Opens 'filename' for root with default search.
 605  *
 606  * Returns the file descriptor as returned by openat
 607  * system call or -1 in case of error.
 608  */
 609 int locale_root_open(struct locale_root *root, const char *filename, int flags, const char *locale)
 610 {
 611         int result;
 612         struct locale_search *search;
 613
 614         search = locale != NULL ? locale_root_search(root, locale, 0) : NULL;
 615         result = do_open(search ? : root->default_search, filename, flags, root);
 616         locale_search_unref(search);
 617         return result;
 618 }
 619
 620 /*
 621  * Resolves 'filename' for 'root' and 'search'.
 622  *
 623  * returns a copy of the filename after search or NULL if not found.
 624  * the returned string MUST be freed by the caller (using free).
 625  */
 626 static char *do_resolve(struct locale_search *search, const char *filename, struct locale_root *root)
 627 {
 628         size_t maxlength, length;
 629         char *buffer, *p;
 630         struct locale_search_node *node;
 631         struct locale_folder *folder;
 632         int rootfd;
 633
 634         /* check the path and normalize it */
 635         filename = subpath_force(filename);
 636         if (filename == NULL)
 637                 goto inval;
 638
 639         /* search for folders */
 640         rootfd = root->rootfd;
 641         node = search ? search->head : NULL;
 642         if (node != NULL) {
 643                 /* allocates a buffer big enough */
 644                 maxlength = root->container.maxlength;
 645                 length = strlen(filename);
 646                 if (length > PATH_MAX)
 647                         goto inval;
 648
 649                 /* initialise the end of the buffer */
 650                 buffer = alloca(length + maxlength + sizeof locales + 1);
 651                 buffer[maxlength + sizeof locales - 1] = '/';
 652                 memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
 653
 654                 /* iterate the searched folder */
 655                 while (node != NULL) {
 656                         folder = node->folder;
 657                         p = buffer + maxlength - folder->length;
 658                         memcpy(p, locales, sizeof locales - 1);
 659                         memcpy(p + sizeof locales - 1, folder->name, folder->length);
 660                         if (0 == faccessat(rootfd, p, F_OK, 0)) {
 661                                 filename = p;
 662                                 goto found;
 663                         }
 664                         node = node->next;
 665                         if (node == NULL && search != root->default_search) {
 666                                 search = root->default_search;
 667                                 node = search ? search->head : NULL;
 668                         }
 669                 }
 670         }
 671
 672         /* root search */
 673         if (0 != faccessat(rootfd, filename, F_OK, 0)) {
 674                 errno = ENOENT;
 675                 return NULL;
 676         }
 677
 678 found:
 679         p = strdup(filename);
 680         if (p == NULL)
 681                 errno = ENOMEM;
 682         return p;
 683
 684 inval:
 685         errno = EINVAL;
 686         return NULL;
 687 }
 688
 689 /*
 690  * Resolves 'filename' at 'root' after default search.
 691  *
 692  * returns a copy of the filename after search or NULL if not found.
 693  * the returned string MUST be freed by the caller (using free).
 694  */
 695 char *locale_root_resolve(struct locale_root *root, const char *filename, const char *locale)
 696 {
 697         char *result;
 698         struct locale_search *search;
 699
 700         search = locale != NULL ? locale_root_search(root, locale, 0) : NULL;
 701         result = do_resolve(search ? : root->default_search, filename, root);
 702         locale_search_unref(search);
 703         return result;
 704 }
 705
 706 /*
 707  * Resolves 'filename' after 'search'.
 708  *
 709  * returns a copy of the filename after search or NULL if not found.
 710  * the returned string MUST be freed by the caller (using free).
 711  */
 712 char *locale_search_resolve(struct locale_search *search, const char *filename)
 713 {
 714         return do_resolve(search, filename, search->root);
 715 }
 716
 717 #if defined(TEST_locale_root)
 718 int main(int ac,char**av)
 719 {
 720         struct locale_root *root = locale_root_create(AT_FDCWD);
 721         struct locale_search *search = NULL;
 722         int fd, rc, i;
 723         char buffer[256];
 724         char *subpath;
 725         while (*++av) {
 726                 if (**av == '@') {
 727                         locale_search_unref(search);
 728                         search = NULL;
 729                         locale_root_unref(root);
 730                         root = locale_root_create(AT_FDCWD, *av + 1);
 731                         if (root == NULL)
 732                                 fprintf(stderr, "can't create root at %s: %m\n", *av + 1);
 733                         else
 734                                 printf("root: %s\n", *av + 1);
 735                 } else {
 736                         if (root == NULL) {
 737                                 fprintf(stderr, "no valid root for %s\n", *av);
 738                         } else if (**av == '-' || **av == '+') {
 739                                 locale_search_unref(search);
 740                                 search = locale_root_search(root, *av + 1, **av == '+');
 741                                 if (search == NULL)
 742                                         fprintf(stderr, "can't create search for %s: %m\n", *av + 1);
 743                                 else
 744                                         printf("search: %s\n", *av + 1);
 745                         } else if (search == NULL) {
 746                                 fprintf(stderr, "no valid search for %s\n", *av);
 747                         } else {
 748                                 fd = locale_search_open(search, *av, O_RDONLY);
 749                                 if (fd < 0)
 750                                         fprintf(stderr, "can't open file %s: %m\n", *av);
 751                                 else {
 752                                         subpath = locale_search_resolve(search, *av);
 753                                         if (subpath == NULL)
 754                                                 fprintf(stderr, "can't resolve file %s: %m\n", *av);
 755                                         else {
 756                                                 rc = (int)read(fd, buffer, sizeof buffer - 1);
 757                                                 if (rc < 0)
 758                                                         fprintf(stderr, "can't read file %s: %m\n", *av);
 759                                                 else {
 760                                                         buffer[rc] = 0;
 761                                                         *strchrnul(buffer, '\n') = 0;
 762                                                         printf("%s -> %s [%s]\n", *av, subpath, buffer);
 763                                                 }
 764                                                 free(subpath);
 765                                         }
 766                                         close(fd);
 767                                 }
 768                         }
 769                 }
 770         }
 771         locale_search_unref(search); search = NULL;
 772         locale_root_unref(root); root = NULL;
 773 }
 774 #endif
 775