Index: uspace/lib/posix/source/fnmatch.c
===================================================================
--- uspace/lib/posix/source/fnmatch.c	(revision a3da2b2ee2ac5f4fadec2282a5f5974b52b2a6f3)
+++ uspace/lib/posix/source/fnmatch.c	(revision a3da2b2ee2ac5f4fadec2282a5f5974b52b2a6f3)
@@ -0,0 +1,716 @@
+/*
+ * Copyright (c) 2011 Jiri Zarevucky
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/** @addtogroup libposix
+ * @{
+ */
+/** @file Filename-matching.
+ */
+
+/* This file contains an implementation of the fnmatch() pattern matching
+ * function. There is more code than necessary to account for the possibility
+ * of adding POSIX-like locale support to the system in the future. Functions
+ * that are only necessary for locale support currently simply use single
+ * characters for "collation elements". 
+ * When (or if) locales are properly implemented, extending this implementation
+ * will be fairly straightforward.
+ */
+
+#include "posix/stdbool.h"
+#include "posix/ctype.h"
+#include "posix/string.h"
+#include "posix/stdlib.h"
+#include "posix/assert.h"
+
+#define LIBPOSIX_INTERNAL
+
+#include "internal/common.h"
+#include "posix/fnmatch.h"
+
+/* Returned by _match... functions. */
+#define INVALID_PATTERN -1
+
+/* Type for collating element, simple identity with characters now,
+ * but may be extended for better locale support.
+ */
+typedef int coll_elm_t;
+
+/** Return value indicating that the element in question
+ * is not valid in the current locale. (That is, if locales are supported.)
+ */
+#define COLL_ELM_INVALID -1
+
+/**
+ * Get collating element matching a string.
+ *
+ * @param str String representation of the element.
+ * @return Matching collating element or COLL_ELM_INVALID.
+ */
+static coll_elm_t _coll_elm_get(const char* str)
+{
+	if (str[0] == '\0' || str[1] != '\0') {
+		return COLL_ELM_INVALID;
+	}
+	return str[0];
+}
+
+/**
+ * Get collating element matching a single character.
+ *
+ * @param c Character representation of the element.
+ * @return Matching collating element.
+ */
+static coll_elm_t _coll_elm_char(int c)
+{
+	return c;
+}
+
+/**
+ * Match collating element with a beginning of a string.
+ *
+ * @param elm Collating element to match.
+ * @param str String which beginning should match the element.
+ * @return 0 if the element doesn't match, or the number of characters matched.
+ */
+static int _coll_elm_match(coll_elm_t elm, const char *str)
+{
+	return elm == *str;
+}
+
+/**
+ * Checks whether a string begins with a collating element in the given range.
+ * Ordering depends on the locale (if locales are supported).
+ *
+ * @param first First element of the range.
+ * @param second Last element of the range.
+ * @param str String to match.
+ * @return 0 if there is no match, or the number of characters matched.
+ */
+static int _coll_elm_between(coll_elm_t first, coll_elm_t second,
+    const char *str)
+{
+	return *str >= first && *str <= second;
+}
+
+/**
+ * Read a string delimited by [? and ?].
+ *
+ * @param pattern Pointer to the string to read from. Its position is moved
+ *    to the first character after the closing ].
+ * @param seq The character on the inside of brackets.
+ * @param buf Read buffer.
+ * @param buf_sz Read buffer's size. If the buffer is not large enough for
+ *    the entire string, the string is cut with no error indication.
+ * @param flags Flags modifying the behavior.
+ * @return True on success, false if the pattern is invalid.
+ */
+static bool _get_delimited(
+    const char **pattern, int seq,
+    char *buf, size_t buf_sz, int flags)
+{
+	const bool noescape = (flags & FNM_NOESCAPE) != 0;
+	const bool pathname = (flags & FNM_PATHNAME) != 0;
+
+	const char *p = *pattern;
+	assert(p[0] == '[' && p[1] == seq /* Caller should ensure this. */);
+	p += 2;
+
+	while (true) {
+		if (*p == seq && *(p + 1) == ']') {
+			/* String properly ended, return. */
+			*pattern = p + 2;
+			*buf = '\0';
+			return true;
+		}
+		if (!noescape && *p == '\\') {
+			p++;
+		}
+		if (*p == '\0') {
+			/* String not ended properly, invalid pattern. */
+			return false;
+		}
+		if (pathname && *p == '/') {
+			/* Slash in a pathname pattern is invalid. */
+			return false;
+		}
+		if (buf_sz > 1) {
+			/* Only add to the buffer if there is space. */
+			*buf = *p;
+			buf++;
+			buf_sz--;
+		}
+		p++;
+	}
+}
+
+/************** CHARACTER CLASSES ****************/
+
+#define MAX_CLASS_OR_COLL_LEN 6
+
+struct _char_class {
+	const char *name;
+	int (*func) (int);
+};
+
+/* List of supported character classes. */
+static const struct _char_class _char_classes[] = {
+	{ "alnum", isalnum },
+	{ "alpha", isalpha },
+	{ "blank", isblank },
+	{ "cntrl", iscntrl },
+	{ "digit", isdigit },
+	{ "graph", isgraph },
+	{ "lower", islower },
+	{ "print", isprint },
+	{ "punct", ispunct },
+	{ "space", isspace },
+	{ "upper", isupper },
+	{ "xdigit", isxdigit }
+};
+
+/**
+ * Compare function for binary search in the _char_classes array.
+ * 
+ * @param key Key of the searched element.
+ * @param elem Element of _char_classes array.
+ * @return Ordering indicator (-1 less than, 0 equal, 1 greater than).
+ */
+static int _class_compare(const void *key, const void *elem)
+{
+	const struct _char_class *class = elem;
+	return strcmp((const char *) key, class->name);
+}
+
+/**
+ * Returns whether the given character belongs to the specified character class.
+ * 
+ * @param cname Name of the character class.
+ * @param c Character.
+ * @return True if the character belongs to the class, false otherwise.
+ */
+static bool _is_in_class (const char *cname, int c)
+{
+	/* Search for class in the array of supported character classes. */
+	const struct _char_class *class = bsearch(cname, _char_classes,
+	    sizeof(_char_classes) / sizeof(struct _char_class),
+	    sizeof(struct _char_class), _class_compare);
+
+	if (class == NULL) {
+		/* No such class supported - treat as an empty class. */
+		return false;
+	} else {
+		/* Class matched. */
+		return class->func(c);
+	}
+}
+
+/**
+ * Tries to parse an initial part of the pattern as a character class pattern,
+ * and if successful, matches the beginning of the given string against the class.
+ * 
+ * @param pattern Pointer to the pattern to match. Must begin with a class
+ *    specifier and is repositioned to the first character after the specifier
+ *    if successful.
+ * @param str String to match.
+ * @param flags Flags modifying the behavior (see fnmatch()).
+ * @return INVALID_PATTERN if the pattern doesn't start with a valid class
+ *    specifier, 0 if the beginning of the matched string doesn't belong
+ *    to the class, or positive number of characters matched.
+ */
+static int _match_char_class(const char **pattern, const char *str, int flags)
+{
+	char class[MAX_CLASS_OR_COLL_LEN + 1];
+
+	if (!_get_delimited(pattern, ':', class, sizeof(class), flags)) {
+		return INVALID_PATTERN;
+	}
+
+	return _is_in_class(class, *str);
+}
+
+/************** END CHARACTER CLASSES ****************/
+
+/**
+ * Reads the next collating element in the pattern, taking into account
+ * locale (if supported) and flags (see fnmatch()).
+ * 
+ * @param pattern Pattern.
+ * @param flags Flags given to fnmatch().
+ * @return Collating element on success,
+ *     or COLL_ELM_INVALID if the pattern is invalid.
+ */
+static coll_elm_t _next_coll_elm(const char **pattern, int flags)
+{
+	assert(pattern != NULL);
+	assert(*pattern != NULL);
+	assert(**pattern != '\0');
+
+	const char *p = *pattern;
+	const bool noescape = (flags & FNM_NOESCAPE) != 0;
+	const bool pathname = (flags & FNM_PATHNAME) != 0;
+
+	if (*p == '[') {
+		if (*(p + 1) == '.') {
+			char buf[MAX_CLASS_OR_COLL_LEN + 1];
+			if (!_get_delimited(pattern, '.', buf, sizeof(buf), flags)) {
+				return COLL_ELM_INVALID;
+			}
+			return _coll_elm_get(buf);
+		}
+
+		if (*(p + 1) == '=') {
+			char buf[MAX_CLASS_OR_COLL_LEN + 1];
+			if (!_get_delimited(pattern, '=', buf, sizeof(buf), flags)) {
+				return COLL_ELM_INVALID;
+			}
+			return _coll_elm_get(buf);
+		}
+	}
+
+	if (!noescape && *p == '\\') {
+		p++;
+		if (*p == '\0') {
+			*pattern = p;
+			return COLL_ELM_INVALID;
+		}
+	}
+	if (pathname && *p == '/') {
+		return COLL_ELM_INVALID;
+	}
+	
+	*pattern = p + 1;
+	return _coll_elm_char(*p);
+}
+
+/**
+ * Matches the beginning of the given string against a bracket expression
+ * the pattern begins with.
+ * 
+ * @param pattern Pointer to the beginning of a bracket expression in a pattern.
+ *     On success, the pointer is moved to the first character after the
+ *     bracket expression.
+ * @param str Unmatched part of the string.
+ * @param flags Flags given to fnmatch().
+ * @return INVALID_PATTERN if the pattern is invalid, 0 if there is no match
+ *     or the number of matched characters on success.
+ */
+static int _match_bracket_expr(const char **pattern, const char *str, int flags)
+{
+	const bool pathname = (flags & FNM_PATHNAME) != 0;
+	const bool special_period = (flags & FNM_PERIOD) != 0;
+	const char *p = *pattern;
+	bool negative = false;
+	int matched = 0;
+
+	#define _matched(match) { \
+		int _match = match; \
+		if (_match < 0) { \
+			/* Invalid pattern */ \
+			return _match; \
+		} else if (matched == 0 && _match > 0) { \
+			/* First match */ \
+			matched = _match; \
+		} \
+	}
+
+	assert(*p == '[');  /* calling code should ensure this */
+	p++;
+
+	if (*str == '\0' || (pathname && *str == '/') ||
+	    (pathname && special_period && *str == '.' && *(str - 1) == '/')) {
+		/* No bracket expression matches end of string,
+		 * slash in pathname match or initial period with FNM_PERIOD
+		 * option.
+		 */
+		return 0;
+	}
+
+	if (*p == '^' || *p == '!') {
+		negative = true;
+		p++;
+	}
+
+	if (*p == ']') {
+		/* When ']' is first, treat it as a normal character. */
+		_matched(*str == ']');
+		p++;
+	}
+	
+	coll_elm_t current_elm = COLL_ELM_INVALID;
+	
+	while (*p != ']') {
+		if (*p == '-' && *(p + 1) != ']' &&
+		    current_elm != COLL_ELM_INVALID) {
+			/* Range expression. */
+			p++;
+			coll_elm_t end_elm = _next_coll_elm(&p, flags);
+			if (end_elm == COLL_ELM_INVALID) {
+				return INVALID_PATTERN;
+			}
+			_matched(_coll_elm_between(current_elm, end_elm, str));
+			continue;
+		}
+	
+		if (*p == '[' && *(p + 1) == ':') {
+			current_elm = COLL_ELM_INVALID;
+			_matched(_match_char_class(&p, str, flags));
+			continue;
+		}
+		
+		current_elm = _next_coll_elm(&p, flags);
+		if (current_elm == COLL_ELM_INVALID) {
+			return INVALID_PATTERN;
+		}
+		_matched(_coll_elm_match(current_elm, str));
+	}
+
+	/* No error occured - update pattern pointer. */
+	*pattern = p + 1;
+
+	if (matched == 0) {
+		/* No match found */
+		return negative;
+	} else {
+		/* Matched 'match' characters. */
+		return negative ? 0 : matched;
+	}
+
+	#undef _matched
+}
+
+/**
+ * Matches a portion of the pattern containing no asterisks (*) against
+ * the given string.
+ * 
+ * @param pattern Pointer to the unmatched portion of the pattern.
+ *     On success, the pointer is moved to the first asterisk, or to the
+ *     terminating nul character, whichever occurs first.
+ * @param string Pointer to the input string. On success, the pointer is moved
+ *     to the first character that wasn't explicitly matched.
+ * @param flags Flags given to fnmatch().
+ * @return True if the entire subpattern matched. False otherwise.
+ */
+static bool _partial_match(const char **pattern, const char **string, int flags)
+{
+	/* Only a single *-delimited subpattern is matched here.
+	 * So in this function, '*' is understood as the end of pattern.
+	 */
+
+	const bool pathname = (flags & FNM_PATHNAME) != 0;
+	const bool special_period = (flags & FNM_PERIOD) != 0;
+	const bool noescape = (flags & FNM_NOESCAPE) != 0;
+	const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;
+
+	const char *s = *string;
+	const char *p = *pattern;
+
+	while (*p != '*') {
+		/* Bracket expression. */
+		if (*p == '[') {
+			int matched = _match_bracket_expr(&p, s, flags);
+			if (matched == 0) {
+				/* Doesn't match. */
+				return false;
+			}
+			if (matched != INVALID_PATTERN) {
+				s += matched;
+				continue;
+			}
+
+			assert(matched == INVALID_PATTERN);
+			/* Fall through to match [ as an ordinary character. */
+		}
+
+		/* Wildcard match. */
+		if (*p == '?') {
+			if (*s == '\0') {
+				/* No character to match. */
+				return false;
+			}
+			if (pathname && *s == '/') {
+				/* Slash must be matched explicitly. */
+				return false;
+			}
+			if (special_period && pathname &&
+			    *s == '.' && *(s - 1) == '/') {
+				/* Initial period must be matched explicitly. */
+				return false;
+			}
+			
+			/* None of the above, match anything else. */
+			p++;
+			s++;
+			continue;
+		}
+
+		if (!noescape && *p == '\\') {
+			/* Escaped character. */
+			p++;
+		}
+
+		if (*p == '\0') {
+			/* End of pattern, must match end of string or
+			 * an end of subdirectory name (optional).
+			 */
+
+			if (*s == '\0' || (leading_dir && *s == '/')) {
+				break;
+			}
+
+			return false;
+		}
+
+		if (*p == *s) {
+			/* Exact match. */
+			p++;
+			s++;
+			continue;
+		}
+
+		/* Nothing matched. */
+		return false;
+	}
+
+	/* Entire sub-pattern matched. */
+	
+	/* postconditions */
+	assert(*p == '\0' || *p == '*');
+	assert(*p != '\0' || *s == '\0' || (leading_dir && *s == '/'));
+	
+	*pattern = p;
+	*string = s;
+	return true;
+}
+
+/**
+ * Match string against a pattern.
+ * 
+ * @param pattern Pattern.
+ * @param string String to match.
+ * @param flags Flags given to fnmatch().
+ * @return True if the string matched the pattern, false otherwise.
+ */
+static bool _full_match(const char *pattern, const char *string, int flags)
+{
+	const bool pathname = (flags & FNM_PATHNAME) != 0;
+	const bool special_period = (flags & FNM_PERIOD) != 0;
+	const bool leading_dir = (flags & FNM_LEADING_DIR) != 0;
+
+	if (special_period && *string == '.') {
+		/* Initial dot must be matched by an explicit dot in pattern. */
+		if (*pattern != '.') {
+			return false;
+		}
+		pattern++;
+		string++;
+	}
+
+	if (*pattern != '*') {
+		if (!_partial_match(&pattern, &string, flags)) {
+			/* The initial match must succeed. */
+			return false;
+		}
+	}
+
+	while (*pattern != '\0') {
+		assert(*pattern == '*');
+		pattern++;
+
+		bool matched = false;
+
+		const char *end;
+		if (pathname && special_period &&
+		    *string == '.' && *(string - 1) == '/') {
+			end = string;
+		} else {
+			end = strchrnul(string, pathname ? '/' : '\0');
+		}
+
+		/* Try to match every possible offset. */
+		while (string <= end) {
+			if (_partial_match(&pattern, &string, flags)) {
+				matched = true;
+				break;
+			}
+			string++;
+		}
+
+		if (matched) {
+			continue;
+		}
+
+		return false;
+	}
+
+	return *string == '\0' || (leading_dir && *string == '/');
+}
+
+/**
+ * Transform the entire string to lowercase.
+ * 
+ * @param s Input string.
+ * @return Newly allocated copy of the input string with all uppercase
+ *     characters folded to their lowercase variants.
+ */
+static char *_casefold(const char *s)
+{
+	assert(s != NULL);
+	char *result = strdup(s);
+	for (char *i = result; *i != '\0'; ++i) {
+		*i = tolower(*i);
+	}
+	return result;
+}
+
+/**
+ * Filename pattern matching.
+ *
+ * @param pattern Pattern to match the string against.
+ * @param string Matched string.
+ * @param flags Flags altering the matching of special characters
+ *     (mainly for dot and slash).
+ * @return Zero if the string matches the pattern, FNM_NOMATCH otherwise.
+ */
+int posix_fnmatch(const char *pattern, const char *string, int flags)
+{
+	assert(pattern != NULL);
+	assert(string != NULL);
+
+	// TODO: don't fold everything in advance, but only when needed
+
+	if ((flags & FNM_CASEFOLD) != 0) {
+		/* Just fold the entire pattern and string. */
+		pattern = _casefold(pattern);
+		string = _casefold(string);
+	}
+
+	bool result = _full_match(pattern, string, flags);
+
+	if ((flags & FNM_CASEFOLD) != 0) {
+		if (pattern) {
+			free((char *) pattern);
+		}
+		if (string) {
+			free((char *) string);
+		}
+	}
+
+	return result ? 0 : FNM_NOMATCH;
+}
+
+// FIXME: put the testcases to the app/tester after fnmatch is included into libc
+
+#if 0
+
+#include <stdio.h>
+
+void __posix_fnmatch_test()
+{
+	int fail = 0;
+
+	#undef assert
+	#define assert(x) { if (x) printf("SUCCESS: "#x"\n"); else { printf("FAILED: "#x"\n"); fail++; } }
+	#define match(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == 0)
+	#define nomatch(s1, s2, flags) assert(posix_fnmatch(s1, s2, flags) == FNM_NOMATCH)
+
+	assert(FNM_PATHNAME == FNM_FILE_NAME);
+	match("", "", 0);
+	match("*", "hello", 0);
+	match("hello", "hello", 0);
+	match("hello*", "hello", 0);
+	nomatch("hello?", "hello", 0);
+	match("*hello", "prdel hello", 0);
+	match("he[sl]lo", "hello", 0);
+	match("he[sl]lo", "heslo", 0);
+	nomatch("he[sl]lo", "heblo", 0);
+	nomatch("he[^sl]lo", "hello", 0);
+	nomatch("he[^sl]lo", "heslo", 0);
+	match("he[^sl]lo", "heblo", 0);
+	nomatch("he[!sl]lo", "hello", 0);
+	nomatch("he[!sl]lo", "heslo", 0);
+	match("he[!sl]lo", "heblo", 0);
+	match("al*[c-t]a*vis*ta", "alheimer talir jehovista", 0);
+	match("al*[c-t]a*vis*ta", "alfons had jehovista", 0);
+	match("[a-ce-z]", "a", 0);
+	match("[a-ce-z]", "c", 0);
+	nomatch("[a-ce-z]", "d", 0);
+	match("[a-ce-z]", "e", 0);
+	match("[a-ce-z]", "z", 0);
+	nomatch("[^a-ce-z]", "a", 0);
+	nomatch("[^a-ce-z]", "c", 0);
+	match("[^a-ce-z]", "d", 0);
+	nomatch("[^a-ce-z]", "e", 0);
+	nomatch("[^a-ce-z]", "z", 0);
+	match("helen??", "helenos", 0);
+	match("****booo****", "booo", 0);
+	
+	match("hello[[:space:]]world", "hello world", 0);
+	nomatch("hello[[:alpha:]]world", "hello world", 0);
+	
+	match("/hoooo*", "/hooooooo/hooo", 0);
+	nomatch("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME);
+	nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME);
+	match("/hoooo*/*", "/hooooooo/hooo", FNM_PATHNAME);
+	match("/hoooo*/hooo", "/hooooooo/hooo", FNM_PATHNAME);
+	match("/hoooo*", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
+	nomatch("/hoooo*/", "/hooooooo/hooo", FNM_PATHNAME | FNM_LEADING_DIR);
+	nomatch("/hoooo", "/hooooooo/hooo", FNM_LEADING_DIR);
+	match("/hooooooo", "/hooooooo/hooo", FNM_LEADING_DIR);
+	
+	match("*", "hell", 0);
+	match("*?", "hell", 0);
+	match("?*?", "hell", 0);
+	match("?*??", "hell", 0);
+	match("??*??", "hell", 0);
+	nomatch("???*??", "hell", 0);
+	
+	nomatch("", "hell", 0);
+	nomatch("?", "hell", 0);
+	nomatch("??", "hell", 0);
+	nomatch("???", "hell", 0);
+	match("????", "hell", 0);
+	
+	match("*", "h.ello", FNM_PERIOD);
+	match("*", "h.ello", FNM_PATHNAME | FNM_PERIOD);
+	nomatch("*", ".hello", FNM_PERIOD);
+	match("h?ello", "h.ello", FNM_PERIOD);
+	nomatch("?hello", ".hello", FNM_PERIOD);
+	match("/home/user/.*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);
+	match("/home/user/*", "/home/user/.hello", FNM_PERIOD);
+	nomatch("/home/user/*", "/home/user/.hello", FNM_PATHNAME | FNM_PERIOD);
+
+	nomatch("HeLlO", "hello", 0);
+	match("HeLlO", "hello", FNM_CASEFOLD);
+
+	printf("Failed: %d\n", fail);
+}
+
+#endif
+
+/** @}
+ */
