add algorithm to seek for locale files

Change-Id: Ie4355db29b157b13c4d93011337b15ca3e5d2571

3 files changed, 821 insertions, 0 deletions

diff --git a/src/locale-root.c b/src/locale-root.c
new file mode 100644
index 00000000..c87ffc55
--- /dev/null
+++ b/src/locale-root.c
@@ -0,0 +1,748 @@
+/*
+ Copyright 2015 IoT.bzh
+
+ author: José Bollo <jose.bollo@iot.bzh>
+
+ Licensed under the Apache License, Version 2.0 (the "License");
+ you may not use this file except in compliance with the License.
+ You may obtain a copy of the License at
+
+     http://www.apache.org/licenses/LICENSE-2.0
+
+ Unless required by applicable law or agreed to in writing, software
+ distributed under the License is distributed on an "AS IS" BASIS,
+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ See the License for the specific language governing permissions and
+ limitations under the License.
+*/
+
+#define _GNU_SOURCE
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <assert.h>
+#include <limits.h>
+#include <string.h>
+#include <ctype.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <dirent.h>
+
+#include "locale-root.h"
+
+/*
+ * Implementation of folder based localisation as described here:
+ *
+ *    https://www.w3.org/TR/widgets/#folder-based-localization
+ */
+
+#define LRU_COUNT 3
+
+static const char locales[] = "locales/";
+
+struct locale_folder {
+	struct locale_folder *parent;
+	size_t length;
+	char name[1];
+};
+
+struct locale_container {
+	size_t maxlength;
+	size_t count;
+	struct locale_folder **folders;
+};
+
+struct locale_search_node {
+	struct locale_search_node *next;
+	struct locale_folder *folder;
+};
+
+struct locale_root;
+
+struct locale_search {
+	struct locale_root *root;
+	struct locale_search_node *head;
+	int refcount;
+	char definition[1];
+};
+
+struct locale_root {
+	int refcount;
+	int refcount2;
+	int rootfd;
+	struct locale_container container;
+	struct locale_search *lru[LRU_COUNT];
+};
+
+/* a valid subpath is a relative path not looking deeper than root using .. */
+static int validsubpath(const char *subpath)
+{
+	int l = 0, i = 0;
+
+	/* absolute path is not valid */
+	if (subpath[i] == '/')
+		return 0;
+
+	/* inspect the path */
+	while(subpath[i]) {
+		switch(subpath[i++]) {
+		case '.':
+			if (!subpath[i])
+				break;
+			if (subpath[i] == '/') {
+				i++;
+				break;
+			}
+			if (subpath[i++] == '.') {
+				if (!subpath[i]) {
+					l--;
+					break;
+				}
+				if (subpath[i++] == '/') {
+					l--;
+					break;
+				}
+			}
+		default:
+			while(subpath[i] && subpath[i] != '/')
+				i++;
+			if (l >= 0)
+				l++;
+		case '/':
+			break;
+		}
+	}
+	return l >= 0;
+}
+
+/*
+ * Normalizes and checks the 'subpath'.
+ * Removes any starting '/' and checks that 'subpath'
+ * does not contains sequence of '..' going deeper than
+ * root.
+ * Returns the normalized subpath or NULL in case of
+ * invalid subpath.
+ */
+static const char *normalsubpath(const char *subpath)
+{
+	while(*subpath == '/')
+		subpath++;
+	return validsubpath(subpath) ? subpath : NULL;
+}
+
+/*
+ * Clear a container content
+ */
+static void clear_container(struct locale_container *container)
+{
+	while(container->count)
+		free(container->folders[--container->count]);
+	free(container->folders);
+}
+
+/*
+ * Adds a folder of name for the container
+ */
+static int add_folder(struct locale_container *container, const char *name)
+{
+	size_t count, length;
+	struct locale_folder **folders;
+
+	count = container->count;
+	folders = realloc(container->folders, (1 + count) * sizeof *folders);
+	if (folders != NULL) {
+		container->folders = folders;
+		length = strlen(name);
+		folders[count] = malloc(sizeof **folders + length);
+		if (folders[count] != NULL) {
+			folders[count]->parent = NULL;
+			folders[count]->length = length;
+			memcpy(folders[count]->name, name, 1 + length);
+			container->count = count + 1;
+			if (length > container->maxlength)
+				container->maxlength = length;
+			return 0;
+		}
+	}
+	clear_container(container);
+	errno = ENOMEM;
+	return -1;
+}
+
+/*
+ * Compare two folders for qsort
+ */
+static int compare_folders_for_qsort(const void *a, const void *b)
+{
+	const struct locale_folder * const *fa = a, * const *fb = b;
+	return strcasecmp((*fa)->name, (*fb)->name);
+}
+
+/*
+ * Search for a folder
+ */
+static struct locale_folder *search_folder(struct locale_container *container, const char *name, size_t length)
+{
+	size_t low, high, mid;
+	struct locale_folder *f;
+	int c;
+
+	low = 0;
+	high = container->count;
+	while (low < high) {
+		mid = (low + high) >> 1;
+		f = container->folders[mid];
+		c = strncasecmp(f->name, name, length);
+		if (c == 0 && f->name[length] == 0)
+			return f;
+		if (c >= 0)
+			high = mid;
+		else	
+			low = mid + 1;
+	}
+	return NULL;
+}
+
+/*
+ * Init a container
+ */
+static int init_container(struct locale_container *container, int dirfd)
+{
+	int rc, sfd;
+	DIR *dir;
+	struct dirent dent, *e;
+	struct stat st;
+	size_t i, j;
+	struct locale_folder *f;
+
+	/* init the container */
+	container->maxlength = 0;
+	container->count = 0;
+	container->folders = NULL;
+
+	/* scan the subdirs */
+	sfd = openat(dirfd, locales, O_DIRECTORY|O_RDONLY);
+	if (sfd == -1)
+		return (errno == ENOENT) - 1;
+
+	/* get the directory data */
+	dir = fdopendir(sfd);
+	if (dir == NULL) {
+		close(sfd);
+		return -1;
+	}
+
+	/* enumerate the entries */
+	for(;;) {
+		/* next entry */
+		rc = readdir_r(dir, &dent, &e);
+		if (rc < 0) {
+			/* error */
+			closedir(dir);
+			return rc;
+		}
+		if (e == NULL) {
+			/* end of entries */
+			closedir(dir);
+			break;
+		}
+		if (dent.d_type == DT_DIR || (dent.d_type == DT_UNKNOWN && fstatat(sfd, dent.d_name, &st, 0) == 0 && S_ISDIR(st.st_mode))) {
+			/* directory aka folder */
+			if (dent.d_name[0] == '.' && (dent.d_name[1] == 0 || (dent.d_name[1] == '.' && dent.d_name[2] == 0))) {
+				/* nothing to do for special directories, basic detection, improves if needed */
+			} else {
+				rc = add_folder(container, dent.d_name);
+				if (rc < 0) {
+					closedir(dir);
+					return rc;
+				}
+			}
+		}
+	}
+
+	/* sort the folders */
+	qsort(container->folders, container->count, sizeof *container->folders, compare_folders_for_qsort);
+
+	/* build the parents links */
+	i = container->count;
+	while (i != 0) {
+		f = container->folders[--i];
+		j = strlen(f->name);
+		while (j != 0 && f->parent == NULL) {
+			if (f->name[--j] == '-')
+				f->parent = search_folder(container, f->name, j);
+		}
+	}
+
+	return rc;
+}
+
+/*
+ * Creates a locale root handler and returns it or return NULL
+ * in case of memory depletion.
+ */
+struct locale_root *locale_root_create(int dirfd, const char *pathname)
+{
+	int rfd;
+	struct locale_root *root;
+	size_t i;
+
+	rfd = (pathname && *pathname) ? openat(dirfd, pathname, O_PATH|O_DIRECTORY) : dirfd >= 0 ? dup(dirfd) : dirfd;
+	if (rfd >= 0 || (!(pathname && *pathname) && dirfd < 0)) {
+		root = calloc(1, sizeof * root);
+		if (root == NULL)
+			errno = ENOMEM;
+		else {
+			if (init_container(&root->container, rfd) == 0) {
+				root->rootfd = rfd;
+				root->refcount = 1;
+				root->refcount2 = 1;
+				for(i = 0 ; i < LRU_COUNT ; i++)
+					root->lru[i] = NULL;
+				return root;
+			}
+			free(root);
+		}
+		close(rfd);
+	}
+	return NULL;
+}
+
+/*
+ * Adds a reference to 'root'
+ */
+struct locale_root *locale_root_addref(struct locale_root *root)
+{
+	root->refcount++;
+	return root;
+}
+
+/*
+ * Drops a reference to 'root' and destroys it
+ * if not more referenced
+ */
+static void locale_root_unref2(struct locale_root *root)
+{
+	if (!--root->refcount2) {
+		clear_container(&root->container);
+		close(root->rootfd);
+		free(root);
+	}
+}
+
+/*
+ * Drops a reference to 'root' and destroys it
+ * if not more referenced
+ */
+void locale_root_unref(struct locale_root *root)
+{
+	size_t i;
+
+	if (root != NULL && !--root->refcount) {
+		/* clear circular references through searchs */
+		for (i = 0 ; i < LRU_COUNT ; i++)
+			locale_search_unref(root->lru[i]);
+		/* finalize if needed */
+		locale_root_unref2(root);
+	}
+}
+
+/*
+ * append, if needed, a folder to the search
+ */
+static int search_append_folder(struct locale_search *search, struct locale_folder *folder)
+{
+	struct locale_search_node **p, *n;
+
+	/* search an existing node */
+	p = &search->head;
+	n = search->head;
+	while(n != NULL) {
+		if (n->folder == folder)
+			return 0;
+		p = &n->next;
+		n = n->next;
+	}
+
+	/* allocates a new node */
+	n = malloc(sizeof *n);
+	if (n == NULL) {
+		errno = ENOMEM;
+		return -1;
+	}
+
+	/* init the node */
+	*p = n;
+	n->folder = folder;
+	n->next = NULL;
+	return 1;
+}
+
+/*
+ * construct a search for the given root and definition of length
+ */
+static struct locale_search *create_search(struct locale_root *root, const char *definition, size_t length, int immediate)
+{
+	struct locale_search *search;
+	size_t stop, back;
+	struct locale_folder *folder;
+	struct locale_search_node *node;
+
+	/* allocate the structure */
+	search = malloc(sizeof *search + length);
+	if (search != NULL) {
+		/* init */
+		root->refcount2++;
+		search->root = root;
+		search->head = NULL;
+		search->refcount = 1;
+		memcpy(search->definition, definition, length);
+		search->definition[length] = 0;
+
+		/* build the search from the definition */
+		while(length > 0) {
+			stop = 0;
+			while(stop < length && definition[stop] != ',' && definition[stop] != ';')
+				stop++;
+			back = stop;
+			while (back > 0 && (definition[back] == ' ' || definition[back] == '\t'))
+				back--;
+			while (back > 0) {
+				folder = search_folder(&root->container, definition, back);
+				if (folder) {
+					if (search_append_folder(search, folder) < 0) {
+						locale_search_unref(search);
+						return NULL;
+					}
+					if (!immediate)
+						break;
+				}
+				while(back > 0 && definition[--back] != '-');
+				while(back > 0 && definition[back] == '-' && definition[back-1] == '-') back--;
+			}
+			while (stop < length && definition[stop] != ',')
+				stop++;
+			while (stop < length && (definition[stop] == ',' || definition[stop] == ' ' || definition[stop] == '\t'))
+				stop++;
+			definition += stop;
+			length -= stop;
+		}
+
+		/* fullfills the search */
+		node = search->head;
+		while(node != NULL) {
+			folder = node->folder->parent;
+			if (folder != NULL) {
+				if (search_append_folder(search, node->folder->parent) < 0) {
+					locale_search_unref(search);
+					return NULL;
+				}
+			}
+			node = node->next;
+		}
+	}
+	return search;
+}
+
+/*
+ * Check if a possibly NUUL search matches the definition of length
+ */
+static inline int search_matches(struct locale_search *search, const char *definition, size_t length)
+{
+	return search != NULL && strncasecmp(search->definition, definition, length) == 0 && search->definition[length] == '\0';
+}
+
+/*
+ * Get an instance of search for the given root and definition
+ * The flag immediate affects how the search is built.
+ * For example, if the definition is "en-US,en-GB,en", the result differs depending on
+ * immediate or not:
+ *  when immediate==0 the search becomes "en-US,en-GB,en"
+ *  when immediate==1 the search becomes "en-US,en,en-GB" because en-US is immediately downgraded to en
+ */
+struct locale_search *locale_root_search(struct locale_root *root, const char *definition, int immediate)
+{
+	char c;
+	size_t i, length;
+	struct locale_search *search;
+
+	/* normalize the definition */
+	c = definition != NULL ? *definition : 0;
+	while (c == ' ' || c == '\t' || c == ',')
+		c = *++definition;
+	length = 0;
+	while (c)
+		c = definition[++length];
+	if (length) {
+		c = definition[length - 1];
+		while ((c == ' ' || c == '\t' || c == ',') && length)
+			c = definition[--length - 1];
+	}
+
+	/* search lru entry */
+	i = 0;
+	while (i < LRU_COUNT && !search_matches(root->lru[i], definition, length))
+		i++;
+
+	/* get the entry */
+	if (i < LRU_COUNT) {
+		/* use an existing one */
+		search = root->lru[i];
+	} else {
+		/* create a new one */
+		search = create_search(root, definition, length, immediate);
+		if (search == NULL)
+			return NULL;
+		/* drop the oldest reference and update i */
+		locale_search_unref(root->lru[--i]);
+	}
+
+	/* manage the LRU */
+	while (i > 0) {
+		root->lru[i] = root->lru[i - 1];
+		i = i - 1;
+	}
+	root->lru[0] = search;
+
+	/* returns a new instance */
+	return locale_search_addref(search);
+}
+
+/*
+ * Adds a reference to the search
+ */
+struct locale_search *locale_search_addref(struct locale_search *search)
+{
+	search->refcount++;
+	return search;
+}
+
+/*
+ * Removes a reference from the search
+ */
+void locale_search_unref(struct locale_search *search)
+{
+	struct locale_search_node *it, *nx;
+
+	if (search && !--search->refcount) {
+		it = search->head;
+		while(it != NULL) {
+			nx = it->next;
+			free(it);
+			it = nx;
+		}
+		locale_root_unref2(search->root);
+		free(search);
+	}
+}
+
+/*
+ * Opens 'filename' after search.
+ *
+ * Returns the file descriptor as returned by openat
+ * system call or -1 in case of error.
+ */
+int locale_search_open(struct locale_search *search, const char *filename, int mode)
+{
+	size_t maxlength, length;
+	char *buffer, *p;
+	struct locale_search_node *node;
+	struct locale_folder *folder;
+	int rootfd, fd;
+
+	/* no creation mode accepted */
+	if ((mode & O_CREAT) != 0)
+		goto inval;
+
+	/* check the path and normalize it */
+	filename = normalsubpath(filename);
+	if (filename == NULL)
+		goto inval;
+
+	/* search for folders */
+	rootfd = search->root->rootfd;
+	node = search->head;
+	if (node != NULL) {
+		/* allocates a buffer big enough */
+		maxlength = search->root->container.maxlength;
+		length = strlen(filename);
+		if (length > PATH_MAX)
+			goto inval;
+
+		/* initialise the end of the buffer */
+		buffer = alloca(length + maxlength + sizeof locales + 1);
+		buffer[maxlength + sizeof locales - 1] = '/';
+		memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
+
+		/* iterate the searched folder */
+		while (node != NULL) {
+			folder = node->folder;
+			p = buffer + maxlength - folder->length;
+			memcpy(p, locales, sizeof locales - 1);
+			memcpy(p + sizeof locales - 1, folder->name, folder->length);
+			fd = openat(rootfd, p, mode);
+			if (fd >= 0)
+				return fd;
+			node = node->next;
+		}
+	}
+
+	/* default search */
+	return openat(rootfd, filename, mode);
+
+inval:
+	errno = EINVAL;
+	return -1;
+}
+
+/*
+ * Resolves 'filename' after search.
+ *
+ * returns a copy of the filename after search or NULL if not found.
+ * the returned string MUST be freed by the caller (using free).
+ */
+char *locale_search_resolve(struct locale_search *search, const char *filename)
+{
+	size_t maxlength, length;
+	char *buffer, *p;
+	struct locale_search_node *node;
+	struct locale_folder *folder;
+	int rootfd;
+
+	/* check the path and normalize it */
+	filename = normalsubpath(filename);
+	if (filename == NULL)
+		goto inval;
+
+	/* search for folders */
+	rootfd = search->root->rootfd;
+	node = search->head;
+	if (node != NULL) {
+		/* allocates a buffer big enough */
+		maxlength = search->root->container.maxlength;
+		length = strlen(filename);
+		if (length > PATH_MAX)
+			goto inval;
+
+		/* initialise the end of the buffer */
+		buffer = alloca(length + maxlength + sizeof locales + 1);
+		buffer[maxlength + sizeof locales - 1] = '/';
+		memcpy(buffer + sizeof locales + maxlength, filename, length + 1);
+
+		/* iterate the searched folder */
+		while (node != NULL) {
+			folder = node->folder;
+			p = buffer + maxlength - folder->length;
+			memcpy(p, locales, sizeof locales - 1);
+			memcpy(p + sizeof locales - 1, folder->name, folder->length);
+			if (0 == faccessat(rootfd, p, F_OK, 0)) {
+				filename = p;
+				goto found;
+			}
+			node = node->next;
+		}
+	}
+
+	/* default search */
+	if (0 != faccessat(rootfd, filename, F_OK, 0)) {
+		errno = ENOENT;
+		return NULL;
+	}
+
+found:
+	p = strdup(filename);
+	if (p == NULL)
+		errno = ENOMEM;
+	return p;
+
+inval:
+	errno = EINVAL;
+	return NULL;
+}
+
+#if defined(TEST_locale_root_validsubpath)
+#include <stdio.h>
+void t(const char *subpath, int validity) {
+  printf("%s -> %d = %d, %s\n", subpath, validity, validsubpath(subpath), validsubpath(subpath)==validity ? "ok" : "NOT OK");
+}
+int main() {
+  t("/",0);
+  t("..",0);
+  t(".",1);
+  t("../a",0);
+  t("a/..",1);
+  t("a/../////..",0);
+  t("a/../b/..",1);
+  t("a/b/c/..",1);
+  t("a/b/c/../..",1);
+  t("a/b/c/../../..",1);
+  t("a/b/c/../../../.",1);
+  t("./..a/././..b/..c/./.././.././../.",1);
+  t("./..a/././..b/..c/./.././.././.././..",0);
+  t("./..a//.//./..b/..c/./.././/./././///.././.././a/a/a/a/a",1);
+  return 0;
+}
+#endif
+
+#if defined(TEST_locale_root)
+int main(int ac,char**av)
+{
+	struct locale_root *root = locale_root_create(AT_FDCWD, NULL);
+	struct locale_search *search = NULL;
+	int fd, rc, i;
+	char buffer[256];
+	char *subpath;
+	while (*++av) {
+		if (**av == '@') {
+			locale_search_unref(search);
+			search = NULL;
+			locale_root_unref(root);
+			root = locale_root_create(AT_FDCWD, *av + 1);
+			if (root == NULL)
+				fprintf(stderr, "can't create root at %s: %m\n", *av + 1);
+			else
+				printf("root: %s\n", *av + 1);
+		} else {
+			if (root == NULL) {
+				fprintf(stderr, "no valid root for %s\n", *av);
+			} else if (**av == '-' || **av == '+') {
+				locale_search_unref(search);
+				search = locale_root_search(root, *av + 1, **av == '+');
+				if (search == NULL)
+					fprintf(stderr, "can't create search for %s: %m\n", *av + 1);
+				else
+					printf("search: %s\n", *av + 1);
+			} else if (search == NULL) {
+				fprintf(stderr, "no valid search for %s\n", *av);
+			} else {
+				fd = locale_search_open(search, *av, O_RDONLY);
+				if (fd < 0)
+					fprintf(stderr, "can't open file %s: %m\n", *av);
+				else {
+					subpath = locale_search_resolve(search, *av);
+					if (subpath == NULL)
+						fprintf(stderr, "can't resolve file %s: %m\n", *av);
+					else {
+						rc = (int)read(fd, buffer, sizeof buffer - 1);
+						if (rc < 0)
+							fprintf(stderr, "can't read file %s: %m\n", *av);
+						else {
+							buffer[rc] = 0;
+							*strchrnul(buffer, '\n') = 0;
+							printf("%s -> %s [%s]\n", *av, subpath, buffer);
+						}
+						free(subpath);
+					}
+					close(fd);
+				}
+			}
+		}
+	}
+	locale_search_unref(search); search = NULL;
+	locale_root_unref(root); root = NULL;
+}
+#endif
+
diff --git a/src/locale-root.h b/src/locale-root.h
new file mode 100644
index 00000000..f1df4d7a
--- /dev/null
+++ b/src/locale-root.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2016 "IoT.bzh"
+ * Author: José Bollo <jose.bollo@iot.bzh>
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+struct locale_root;
+struct locale_search;
+
+extern struct locale_root *locale_root_create(int dirfd, const char *pathname);
+extern struct locale_root *locale_root_addref(struct locale_root *root);
+extern void locale_root_unref(struct locale_root *root);
+extern struct locale_search *locale_root_search(struct locale_root *root, const char *definition, int immediate);
+
+extern int locale_search_open(struct locale_search *search, const char *filename, int mode);
+extern char *locale_search_resolve(struct locale_search *search, const char *filename);
+extern struct locale_search *locale_search_addref(struct locale_search *search);
+extern void locale_search_unref(struct locale_search *search);
+
diff --git a/src/tests/test-locale-root.sh b/src/tests/test-locale-root.sh
new file mode 100755
index 00000000..d09b0399
--- /dev/null
+++ b/src/tests/test-locale-root.sh
@@ -0,0 +1,41 @@
+#!/bin/bash
+
+files="
+locales/fr/titi
+locales/fr-FR/titi
+locales/fr-BE/titi
+locales/fr-CA/titi
+locales/en/titi
+locales/en-GB/titi
+locales/en-US/titi
+locales/zh-hans-cn/a.gif
+locales/zh-hans-cn/f.gif
+locales/zh-hans/a.gif
+locales/zh-hans/b.gif
+locales/zh/a.gif
+locales/zh/b.gif
+locales/zh/c.gif
+a.gif
+b.gif
+c.gif
+d.gif
+index.html
+config.xml
+"
+
+
+testdir=testdir$$
+
+rm -rf $testdir
+for f in $files
+do
+	mkdir -p $testdir/$(dirname $f)
+	echo $f > $testdir/$f
+done
+
+cc -o $testdir/lr ../locale-root.c -D TEST_locale_root -g
+valgrind $testdir/lr @$testdir +zh-hans-cn a.gif b.gif c.gif d.gif +en-US a.gif b.gif c.gif d.gif +zh-hans-cn a.gif b.gif c.gif d.gif
+
+
+rm -rf $testdir
+