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