Import Subversion-1.10.0vendor/subversion/subversion-1.10.0

1 files changed, 1444 insertions, 789 deletions

diff --git a/subversion/libsvn_repos/authz.c b/subversion/libsvn_repos/authz.c
index 20f9231dc22a..668d78dd5993 100644
--- a/subversion/libsvn_repos/authz.c
+++ b/subversion/libsvn_repos/authz.c
@@ -25,6 +25,7 @@
 
 #include <apr_pools.h>
 #include <apr_file_io.h>
+#include <apr_fnmatch.h>
 
 #include "svn_hash.h"
 #include "svn_pools.h"
@@ -34,946 +35,1592 @@
 #include "svn_repos.h"
 #include "svn_config.h"
 #include "svn_ctype.h"
+#include "private/svn_atomic.h"
 #include "private/svn_fspath.h"
 #include "private/svn_repos_private.h"
+#include "private/svn_sorts_private.h"
+#include "private/svn_subr_private.h"
 #include "repos.h"
+#include "authz.h"
+#include "config_file.h"
 
 
-/*** Structures. ***/
+/*** Access rights. ***/
 
-/* Information for the config enumerators called during authz
-   lookup. */
-struct authz_lookup_baton {
-  /* The authz configuration. */
-  svn_config_t *config;
+/* This structure describes the access rights given to a specific user by
+ * a path rule (actually the rule set specified for a path).  I.e. there is
+ * one instance of this per path rule.
+ */
+typedef struct path_access_t
+{
+  /* Sequence number of the path rule that this struct was derived from.
+   * If multiple rules apply to the same path (only possible with wildcard
+   * matching), the one with the highest SEQUENCE_NUMBER wins, i.e. the latest
+   * one defined in the authz file.
+   *
+   * A value of 0 denotes the default rule at the repository root denying
+   * access to everybody.  User-defined path rules start with ID 1.
+   */
+  int sequence_number;
 
-  /* The user to authorize. */
-  const char *user;
+  /* Access rights of the respective user as defined by the rule set. */
+  authz_access_t rights;
+} path_access_t;
 
-  /* Explicitly granted rights. */
-  svn_repos_authz_access_t allow;
-  /* Explicitly denied rights. */
-  svn_repos_authz_access_t deny;
+/* Use this to indicate that no sequence ID has been assigned.
+ * It will automatically be inferior to (less than) any other sequence ID. */
+#define NO_SEQUENCE_NUMBER (-1)
 
-  /* The rights required by the caller of the lookup. */
-  svn_repos_authz_access_t required_access;
+/* Convenience structure combining the node-local access rights with the
+ * min and max rights granted within the sub-tree. */
+typedef struct limited_rights_t
+{
+  /* Access granted to the current user.  If the SEQUENCE_NUMBER member is
+   * NO_SEQUENCE_NUMBER, there has been no specific path rule for this PATH
+   * but only for some sub-path(s).  There is always a rule at the root node.
+   */
+  path_access_t access;
 
-  /* The following are used exclusively in recursive lookups. */
+  /* Minimal access rights that the user has on this or any other node in 
+   * the sub-tree.  This does not take inherited rights into account. */
+  authz_access_t min_rights;
 
-  /* The path in the repository (an fspath) to authorize. */
-  const char *repos_path;
-  /* repos_path prefixed by the repository name and a colon. */
-  const char *qualified_repos_path;
+  /* Maximal access rights that the user has on this or any other node in 
+   * the sub-tree.  This does not take inherited rights into account. */
+  authz_access_t max_rights;
 
-  /* Whether, at the end of a recursive lookup, access is granted. */
-  svn_boolean_t access;
-};
+} limited_rights_t;
 
-/* Information for the config enumeration functions called during the
-   validation process. */
-struct authz_validate_baton {
-  svn_config_t *config; /* The configuration file being validated. */
-  svn_error_t *err;     /* The error being thrown out of the
-                           enumerator, if any. */
-};
+/* Return TRUE, if RIGHTS has local rights defined in the ACCESS member. */
+static svn_boolean_t
+has_local_rule(const limited_rights_t *rights)
+{
+  return rights->access.sequence_number != NO_SEQUENCE_NUMBER;
+}
 
-/* Currently this structure is just a wrapper around a svn_config_t.
-   Please update authz_pool if you modify this structure. */
-struct svn_authz_t
+/* Aggregate the ACCESS spec of TARGET and RIGHTS into TARGET.  I.e. if both
+ * are specified, pick one in accordance to the precedence rules. */
+static void
+combine_access(limited_rights_t *target,
+               const limited_rights_t *rights)
 {
-  svn_config_t *cfg;
-};
+  /* This implies the check for NO_SEQUENCE_NUMBER, i.e no rights being
+   * specified. */
+  if (target->access.sequence_number < rights->access.sequence_number)
+    target->access = rights->access;
+}
 
+/* Aggregate the min / max access rights of TARGET and RIGHTS into TARGET. */
+static void
+combine_right_limits(limited_rights_t *target,
+                     const limited_rights_t *rights)
+{
+  target->max_rights |= rights->max_rights;
+  target->min_rights &= rights->min_rights;
+}
 
 
-/*** Checking access. ***/
 
-/* Determine whether the REQUIRED access is granted given what authz
- * to ALLOW or DENY.  Return TRUE if the REQUIRED access is
- * granted.
- *
- * Access is granted either when no required access is explicitly
- * denied (implicit grant), or when the required access is explicitly
- * granted, overriding any denials.
+/*** Authz cache access. ***/
+
+/* All authz instances currently in use as well as all filtered authz
+ * instances in use will be cached here.
+ * Both caches will be instantiated at most once. */
+static svn_object_pool__t *authz_pool = NULL;
+static svn_object_pool__t *filtered_pool = NULL;
+static svn_atomic_t authz_pool_initialized = FALSE;
+
+/* Implements svn_atomic__err_init_func_t. */
+static svn_error_t *
+synchronized_authz_initialize(void *baton, apr_pool_t *pool)
+{
+#if APR_HAS_THREADS
+  svn_boolean_t multi_threaded = TRUE;
+#else
+  svn_boolean_t multi_threaded = FALSE;
+#endif
+
+  SVN_ERR(svn_object_pool__create(&authz_pool, multi_threaded, pool));
+  SVN_ERR(svn_object_pool__create(&filtered_pool, multi_threaded, pool));
+
+  return SVN_NO_ERROR;
+}
+
+svn_error_t *
+svn_repos_authz_initialize(apr_pool_t *pool)
+{
+  /* Protect against multiple calls. */
+  return svn_error_trace(svn_atomic__init_once(&authz_pool_initialized,
+                                               synchronized_authz_initialize,
+                                               NULL, pool));
+}
+
+/* Return a combination of AUTHZ_KEY and GROUPS_KEY, allocated in RESULT_POOL.
+ * GROUPS_KEY may be NULL.  This is the key for the AUTHZ_POOL.
  */
-static svn_boolean_t
-authz_access_is_granted(svn_repos_authz_access_t allow,
-                        svn_repos_authz_access_t deny,
-                        svn_repos_authz_access_t required)
+static svn_membuf_t *
+construct_authz_key(const svn_checksum_t *authz_key,
+                    const svn_checksum_t *groups_key,
+                    apr_pool_t *result_pool)
 {
-  svn_repos_authz_access_t stripped_req =
-    required & (svn_authz_read | svn_authz_write);
+  svn_membuf_t *result = apr_pcalloc(result_pool, sizeof(*result));
+  if (groups_key)
+    {
+      apr_size_t authz_size = svn_checksum_size(authz_key);
+      apr_size_t groups_size = svn_checksum_size(groups_key);
 
-  if ((deny & required) == svn_authz_none)
-    return TRUE;
-  else if ((allow & required) == stripped_req)
-    return TRUE;
+      svn_membuf__create(result, authz_size + groups_size, result_pool);
+      result->size = authz_size + groups_size; /* exact length is required! */
+
+      memcpy(result->data, authz_key->digest, authz_size);
+      memcpy((char *)result->data + authz_size,
+             groups_key->digest, groups_size);
+    }
   else
-    return FALSE;
+    {
+      apr_size_t size = svn_checksum_size(authz_key);
+      svn_membuf__create(result, size, result_pool);
+      result->size = size; /* exact length is required! */
+      memcpy(result->data, authz_key->digest, size);
+    }
+
+  return result;
 }
 
+/* Return a combination of REPOS_NAME, USER and AUTHZ_ID, allocated in
+ * RESULT_POOL.  USER may be NULL.  This is the key for the FILTERED_POOL.
+ */
+static svn_membuf_t *
+construct_filtered_key(const char *repos_name,
+                       const char *user,
+                       const svn_membuf_t *authz_id,
+                       apr_pool_t *result_pool)
+{
+  svn_membuf_t *result = apr_pcalloc(result_pool, sizeof(*result));
+  size_t repos_len = strlen(repos_name);
+  size_t user_len = user ? strlen(user) : 1;
+  const char *nullable_user = user ? user : "\0";
+  size_t size = authz_id->size + repos_len + 1 + user_len + 1;
+
+  svn_membuf__create(result, size, result_pool);
+  result->size = size;
+
+  memcpy(result->data, repos_name, repos_len + 1);
+  size = repos_len + 1;
+  memcpy((char *)result->data + size, nullable_user, user_len + 1);
+  size += user_len + 1;
+  memcpy((char *)result->data + size, authz_id->data, authz_id->size);
+
+  return result;
+}
 
-/* Decide whether the REQUIRED access has been conclusively
- * determined.  Return TRUE if the given ALLOW/DENY authz are
- * conclusive regarding the REQUIRED authz.
- *
- * Conclusive determination occurs when any of the REQUIRED authz are
- * granted or denied by ALLOW/DENY.
+
+/*** Constructing the prefix tree. ***/
+
+/* Since prefix arrays may have more than one hit, we need to link them
+ * for fast lookup. */
+typedef struct sorted_pattern_t
+{
+  /* The filtered tree node carrying the prefix. */
+  struct node_t *node;
+
+  /* Entry that is a prefix to this one or NULL. */
+  struct sorted_pattern_t *next;
+} sorted_pattern_t;
+
+/* Substructure of node_t.  It contains all sub-node that use patterns
+ * in the next segment level. We keep it separate to save a bit of memory
+ * and to be able to check for pattern presence in a single operation.
  */
-static svn_boolean_t
-authz_access_is_determined(svn_repos_authz_access_t allow,
-                           svn_repos_authz_access_t deny,
-                           svn_repos_authz_access_t required)
+typedef struct node_pattern_t
 {
-  if ((deny & required) || (allow & required))
-    return TRUE;
+  /* If not NULL, this represents the "*" follow-segment. */
+  struct node_t *any;
+
+  /* If not NULL, this represents the "**" follow-segment. */
+  struct node_t *any_var;
+
+  /* If not NULL, the segments of all sorted_pattern_t in this array are the
+   * prefix part of "prefix*" patterns.  Sorted by segment prefix. */
+  apr_array_header_t *prefixes;
+
+  /* If not NULL, the segments of all sorted_pattern_t in this array are the
+   * reversed suffix part of "*suffix" patterns.  Sorted by reversed
+   * segment suffix. */
+  apr_array_header_t *suffixes;
+
+  /* If not NULL, the segments of all sorted_pattern_t in this array contain
+   * wildcards and don't fit into any of the above categories.
+   * The NEXT members of the elements will not be used. */
+  apr_array_header_t *complex;
+
+  /* This node itself is a "**" segment and must therefore itself be added
+   * to the matching node list for the next level. */
+  svn_boolean_t repeat;
+} node_pattern_t;
+
+/* The pattern tree.  All relevant path rules are being folded into this
+ * prefix tree, with a single, whole segment stored at each node.  The whole
+ * tree applies to a single user only.
+ */
+typedef struct node_t
+{
+  /* The segment as specified in the path rule.  During the lookup tree walk,
+   * this will compared to the respective segment of the path to check. */
+  svn_string_t segment;
+
+  /* Immediate access rights granted by rules on this node and the min /
+   * max rights on any path in this sub-tree. */
+  limited_rights_t rights;
+
+  /* Map of sub-segment(const char *) to respective node (node_t) for all
+   * sub-segments that have rules on themselves or their respective subtrees.
+   * NULL, if there are no rules for sub-paths relevant to the user. */
+  apr_hash_t *sub_nodes;
+
+  /* If not NULL, this contains the pattern-based segment sub-nodes. */
+  node_pattern_t *pattern_sub_nodes;
+} node_t;
+
+/* Create a new tree node for SEGMENT.
+   Note: SEGMENT->pattern is always interned and therefore does not
+   have to be copied into the result pool. */
+static node_t *
+create_node(authz_rule_segment_t *segment,
+            apr_pool_t *result_pool)
+{
+  node_t *result = apr_pcalloc(result_pool, sizeof(*result));
+  if (segment)
+    result->segment = segment->pattern;
   else
-    return FALSE;
+    {
+      result->segment.data = "";
+      result->segment.len = 0;
+    }
+  result->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
+  return result;
 }
 
-/* Return TRUE is USER equals ALIAS. The alias definitions are in the
-   "aliases" sections of CFG. Use POOL for temporary allocations during
-   the lookup. */
-static svn_boolean_t
-authz_alias_is_user(svn_config_t *cfg,
-                    const char *alias,
-                    const char *user,
-                    apr_pool_t *pool)
+/* Auto-create a node in *NODE, make it apply to SEGMENT and return it. */
+static node_t *
+ensure_node(node_t **node,
+            authz_rule_segment_t *segment,
+            apr_pool_t *result_pool)
 {
-  const char *value;
+  if (!*node)
+    *node = create_node(segment, result_pool);
 
-  svn_config_get(cfg, &value, "aliases", alias, NULL);
-  if (!value)
-    return FALSE;
+  return *node;
+}
 
-  if (strcmp(value, user) == 0)
-    return TRUE;
+/* compare_func comparing segment names. It takes a sorted_pattern_t* as
+ * VOID_LHS and a const authz_rule_segment_t * as VOID_RHS.
+ */
+static int
+compare_node_rule_segment(const void *void_lhs,
+                          const void *void_rhs)
+{
+  const sorted_pattern_t *element = void_lhs;
+  const authz_rule_segment_t *segment = void_rhs;
 
-  return FALSE;
+  return strcmp(element->node->segment.data, segment->pattern.data);
 }
 
+/* compare_func comparing segment names. It takes a sorted_pattern_t* as
+ * VOID_LHS and a const char * as VOID_RHS.
+ */
+static int
+compare_node_path_segment(const void *void_lhs,
+                          const void *void_rhs)
+{
+  const sorted_pattern_t *element = void_lhs;
+  const char *segment = void_rhs;
+
+  return strcmp(element->node->segment.data, segment);
+}
 
-/* Return TRUE if USER is in GROUP.  The group definitions are in the
-   "groups" section of CFG.  Use POOL for temporary allocations during
-   the lookup. */
-static svn_boolean_t
-authz_group_contains_user(svn_config_t *cfg,
-                          const char *group,
-                          const char *user,
-                          apr_pool_t *pool)
+/* Make sure a node_t* for SEGMENT exists in *ARRAY and return it.
+ * Auto-create either if they don't exist.  Entries in *ARRAY are
+ * sorted by their segment strings.
+ */
+static node_t *
+ensure_node_in_array(apr_array_header_t **array,
+                     authz_rule_segment_t *segment,
+                     apr_pool_t *result_pool)
 {
-  const char *value;
-  apr_array_header_t *list;
-  int i;
+  int idx;
+  sorted_pattern_t entry;
+  sorted_pattern_t *entry_ptr;
+
+  /* Auto-create the array. */
+  if (!*array)
+    *array = apr_array_make(result_pool, 4, sizeof(sorted_pattern_t));
+
+  /* Find the node in ARRAY and the IDX at which it were to be inserted.
+   * Initialize IDX such that we won't attempt a hinted lookup (likely
+   * to fail and therefore pure overhead). */
+  idx = (*array)->nelts;
+  entry_ptr = svn_sort__array_lookup(*array, segment, &idx,
+                                     compare_node_rule_segment);
+  if (entry_ptr)
+    return entry_ptr->node;
+
+  /* There is no such node, yet.
+   * Create one and insert it into the sorted array. */
+  entry.node = create_node(segment, result_pool);
+  entry.next = NULL;
+  svn_sort__array_insert(*array, &entry, idx);
+
+  return entry.node;
+}
 
-  svn_config_get(cfg, &value, "groups", group, NULL);
+/* Auto-create the PATTERN_SUB_NODES sub-structure in *NODE and return it. */
+static node_pattern_t *
+ensure_pattern_sub_nodes(node_t *node,
+                         apr_pool_t *result_pool)
+{
+  if (node->pattern_sub_nodes == NULL)
+    node->pattern_sub_nodes = apr_pcalloc(result_pool,
+                                          sizeof(*node->pattern_sub_nodes));
+
+  return node->pattern_sub_nodes;
+}
+
+/* Combine an ACL rule segment with the corresponding node in our filtered
+ * data model. */
+typedef struct node_segment_pair_t
+{
+  authz_rule_segment_t *segment;
+  node_t *node;
+} node_segment_pair_t;
+
+/* Context object to be used with process_acl. It allows us to re-use
+ * information from previous insertions. */
+typedef struct construction_context_t
+{
+  /* Array of node_segment_pair_t.  It contains all segments already
+   * processed of the current insertion together with the respective
+   * nodes in our filtered tree.  Before the next lookup, the tree
+   * walk for the common prefix can be skipped. */
+  apr_array_header_t *path;
+} construction_context_t;
+
+/* Return a new context object allocated in RESULT_POOL. */
+static construction_context_t *
+create_construction_context(apr_pool_t *result_pool)
+{
+  construction_context_t *result = apr_pcalloc(result_pool, sizeof(*result));
+
+  /* Array will be auto-extended but this initial size will make it rarely
+   * ever necessary. */
+  result->path = apr_array_make(result_pool, 32, sizeof(node_segment_pair_t));
 
-  list = svn_cstring_split(value, ",", TRUE, pool);
+  return result;
+}
 
-  for (i = 0; i < list->nelts; i++)
+/* Constructor utility:  Below NODE, recursively insert sub-nodes for the
+ * path given as *SEGMENTS of length SEGMENT_COUNT. If matching nodes
+ * already exist, use those instead of creating new ones.  Set the leave
+ * node's access rights spec to PATH_ACCESS.  Update the context info in CTX.
+ */
+static void
+insert_path(construction_context_t *ctx,
+            node_t *node,
+            path_access_t *path_access,
+            int segment_count,
+            authz_rule_segment_t *segment,
+            apr_pool_t *result_pool,
+            apr_pool_t *scratch_pool)
+{
+  node_t *sub_node;
+  node_segment_pair_t *node_segment;
+
+  /* End of path? */
+  if (segment_count == 0)
     {
-      const char *group_user = APR_ARRAY_IDX(list, i, char *);
+      /* Set access rights.  Note that there might be multiple rules for
+       * the same path due to non-repo-specific rules vs. repo-specific
+       * ones.  Whichever gets defined last wins.
+       */
+      limited_rights_t rights;
+      rights.access = *path_access;
+      rights.max_rights = path_access->rights;
+      rights.min_rights = path_access->rights;
+      combine_access(&node->rights, &rights);
+      return;
+    }
+
+  /* Any wildcards?  They will go into a separate sub-structure. */
+  if (segment->kind != authz_rule_literal)
+    ensure_pattern_sub_nodes(node, result_pool);
 
-      /* If the 'user' is a subgroup, recurse into it. */
-      if (*group_user == '@')
+  switch (segment->kind)
+    {
+      /* A full wildcard segment? */
+    case authz_rule_any_segment:
+      sub_node = ensure_node(&node->pattern_sub_nodes->any,
+                             segment, result_pool);
+      break;
+
+      /* One or more full wildcard segments? */
+    case authz_rule_any_recursive:
+      sub_node = ensure_node(&node->pattern_sub_nodes->any_var,
+                             segment, result_pool);
+      ensure_pattern_sub_nodes(sub_node, result_pool)->repeat = TRUE;
+      break;
+
+      /* A single wildcard at the end of the segment? */
+    case authz_rule_prefix:
+      sub_node = ensure_node_in_array(&node->pattern_sub_nodes->prefixes,
+                                      segment, result_pool);
+      break;
+
+      /* A single wildcard at the start of segments? */
+    case authz_rule_suffix:
+      sub_node = ensure_node_in_array(&node->pattern_sub_nodes->suffixes,
+                                      segment, result_pool);
+      break;
+
+      /* General pattern? */
+    case authz_rule_fnmatch:
+      sub_node = ensure_node_in_array(&node->pattern_sub_nodes->complex,
+                                      segment, result_pool);
+      break;
+
+      /* Then it must be a literal. */
+    default:
+      SVN_ERR_ASSERT_NO_RETURN(segment->kind == authz_rule_literal);
+
+      if (!node->sub_nodes)
         {
-          if (authz_group_contains_user(cfg, &group_user[1],
-                                        user, pool))
-            return TRUE;
+          node->sub_nodes = svn_hash__make(result_pool);
+          sub_node = NULL;
         }
-
-      /* If the 'user' is an alias, verify it. */
-      else if (*group_user == '&')
+      else
         {
-          if (authz_alias_is_user(cfg, &group_user[1],
-                                  user, pool))
-            return TRUE;
+          sub_node = svn_hash_gets(node->sub_nodes, segment->pattern.data);
         }
 
-      /* If the user matches, stop. */
-      else if (strcmp(user, group_user) == 0)
-        return TRUE;
+      /* Auto-insert a sub-node for the current segment. */
+      if (!sub_node)
+        {
+          sub_node = create_node(segment, result_pool);
+          apr_hash_set(node->sub_nodes,
+                       sub_node->segment.data,
+                       sub_node->segment.len,
+                       sub_node);
+        }
     }
 
-  return FALSE;
+  /* Update context. */
+  node_segment = apr_array_push(ctx->path);
+  node_segment->segment = segment;
+  node_segment->node = sub_node;
+
+  /* Continue at the sub-node with the next segment. */
+  insert_path(ctx, sub_node, path_access, segment_count - 1, segment + 1,
+              result_pool, scratch_pool);
 }
 
 
-/* Determines whether an authz rule applies to the current
- * user, given the name part of the rule's name-value pair
- * in RULE_MATCH_STRING and the authz_lookup_baton object
- * B with the username in question.
+/* If the ACL is relevant to the REPOSITORY and user (given as MEMBERSHIPS
+ * plus ANONYMOUS flag), insert the respective nodes into tree starting
+ * at ROOT.  Use the context info of the previous call in CTX to eliminate
+ * repeated lookups.  Allocate new nodes in RESULT_POOL and use SCRATCH_POOL
+ * for temporary allocations.
  */
-static svn_boolean_t
-authz_line_applies_to_user(const char *rule_match_string,
-                           struct authz_lookup_baton *b,
-                           apr_pool_t *pool)
+static void
+process_acl(construction_context_t *ctx,
+            const authz_acl_t *acl,
+            node_t *root,
+            const char *repository,
+            const char *user,
+            apr_pool_t *result_pool,
+            apr_pool_t *scratch_pool)
 {
-  /* If the rule has an inversion, recurse and invert the result. */
-  if (rule_match_string[0] == '~')
-    return !authz_line_applies_to_user(&rule_match_string[1], b, pool);
-
-  /* Check for special tokens. */
-  if (strcmp(rule_match_string, "$anonymous") == 0)
-    return (b->user == NULL);
-  if (strcmp(rule_match_string, "$authenticated") == 0)
-    return (b->user != NULL);
-
-  /* Check for a wildcard rule. */
-  if (strcmp(rule_match_string, "*") == 0)
-    return TRUE;
+  path_access_t path_access;
+  int i;
+  node_t *node;
 
-  /* If we get here, then the rule is:
-   *  - Not an inversion rule.
-   *  - Not an authz token rule.
-   *  - Not a wildcard rule.
-   *
-   * All that's left over is regular user or group specifications.
-   */
+  /* Skip ACLs that don't say anything about the current user
+     and/or repository. */
+  if (!svn_authz__get_acl_access(&path_access.rights, acl, user, repository))
+    return;
 
-  /* If the session is anonymous, then a user/group
-   * rule definitely won't match.
-   */
-  if (b->user == NULL)
-    return FALSE;
+  /* Insert the rule into the filtered tree. */
+  path_access.sequence_number = acl->sequence_number;
 
-  /* Process the rule depending on whether it is
-   * a user, alias or group rule.
-   */
-  if (rule_match_string[0] == '@')
-    return authz_group_contains_user(
-      b->config, &rule_match_string[1], b->user, pool);
-  else if (rule_match_string[0] == '&')
-    return authz_alias_is_user(
-      b->config, &rule_match_string[1], b->user, pool);
-  else
-    return (strcmp(b->user, rule_match_string) == 0);
-}
+  /* Try to reuse results from previous runs.
+   * Basically, skip the common prefix. */
+  node = root;
+  for (i = 0; i < ctx->path->nelts; ++i)
+    {
+      const node_segment_pair_t *step
+        = &APR_ARRAY_IDX(ctx->path, i, const node_segment_pair_t);
+
+      /* Exploit the fact that all strings in the authz model are unique /
+       * internized and can be identified by address alone. */
+      if (   !step->node
+          || i >= acl->rule.len
+          || step->segment->kind != acl->rule.path[i].kind
+          || step->segment->pattern.data != acl->rule.path[i].pattern.data)
+        {
+          ctx->path->nelts = i;
+          break;
+        }
+      else
+        {
+          node = step->node;
+        }
+    }
 
+  /* Insert the path rule into the filtered tree. */
+  insert_path(ctx, node, &path_access,
+              acl->rule.len - i, acl->rule.path + i,
+              result_pool, scratch_pool);
+}
 
-/* Callback to parse one line of an authz file and update the
- * authz_baton accordingly.
+/* Forward declaration ... */
+static svn_boolean_t
+trim_tree(node_t *node,
+          int latest_any_var,
+          apr_pool_t *scratch_pool);
+
+/* Call trim_tree() with LATEST_ANY_VAR on all elements in the *HASH of
+ * node_t * and remove empty nodes from.  *HASH may be NULL.  If all nodes
+ * could be removed, set *HASH to NULL and return TRUE.  Allocate temporary
+ * data in SCRATCH_POOL.
  */
 static svn_boolean_t
-authz_parse_line(const char *name, const char *value,
-                 void *baton, apr_pool_t *pool)
+trim_subnode_hash(apr_hash_t **hash,
+                  int latest_any_var,
+                  apr_pool_t *scratch_pool)
 {
-  struct authz_lookup_baton *b = baton;
+  if (*hash)
+    {
+      apr_array_header_t *to_remove = apr_array_make(scratch_pool, 0,
+                                                     sizeof(node_t *));
 
-  /* Stop if the rule doesn't apply to this user. */
-  if (!authz_line_applies_to_user(name, b, pool))
-    return TRUE;
+      apr_hash_index_t *hi;
+      for (hi = apr_hash_first(scratch_pool, *hash);
+           hi;
+           hi = apr_hash_next(hi))
+        {
+          node_t *node = apr_hash_this_val(hi);
+          if (trim_tree(node, latest_any_var, scratch_pool))
+            APR_ARRAY_PUSH(to_remove, node_t *) = node;
+        }
 
-  /* Set the access grants for the rule. */
-  if (strchr(value, 'r'))
-    b->allow |= svn_authz_read;
-  else
-    b->deny |= svn_authz_read;
+      /* Are some nodes left? */
+      if (to_remove->nelts < apr_hash_count(*hash))
+        {
+          /* Remove empty nodes (if any). */
+          int i;
+          for (i = 0; i < to_remove->nelts; ++i)
+            {
+              node_t *node = APR_ARRAY_IDX(to_remove, i, node_t *);
+              apr_hash_set(*hash, node->segment.data, node->segment.len,
+                           NULL);
+            }
 
-  if (strchr(value, 'w'))
-    b->allow |= svn_authz_write;
-  else
-    b->deny |= svn_authz_write;
+          return FALSE;
+        }
+
+      /* No nodes left.  A NULL hash is more efficient than an empty one. */
+      *hash = NULL;
+    }
 
   return TRUE;
 }
 
-
-/* Return TRUE iff the access rules in SECTION_NAME apply to PATH_SPEC
- * (which is a repository name, colon, and repository fspath, such as
- * "myrepos:/trunk/foo").
+/* Call trim_tree() with LATEST_ANY_VAR on all elements in the *ARRAY of
+ * node_t * and remove empty nodes from.  *ARRAY may be NULL.  If all nodes
+ * could be removed, set *ARRAY to NULL and return TRUE.  Allocate
+ * temporary data in SCRATCH_POOL.
  */
 static svn_boolean_t
-is_applicable_section(const char *path_spec,
-                      const char *section_name)
+trim_subnode_array(apr_array_header_t **array,
+                   int latest_any_var,
+                   apr_pool_t *scratch_pool)
 {
-  apr_size_t path_spec_len = strlen(path_spec);
+  if (*array)
+    {
+      int i, dest;
+      for (i = 0, dest = 0; i < (*array)->nelts; ++i)
+        {
+          node_t *node = APR_ARRAY_IDX(*array, i, sorted_pattern_t).node;
+          if (!trim_tree(node, latest_any_var, scratch_pool))
+            {
+              if (i != dest)
+                APR_ARRAY_IDX(*array, dest, sorted_pattern_t)
+                  = APR_ARRAY_IDX(*array, i, sorted_pattern_t);
+              ++dest;
+            }
+        }
 
-  return ((strncmp(path_spec, section_name, path_spec_len) == 0)
-          && (path_spec[path_spec_len - 1] == '/'
-              || section_name[path_spec_len] == '/'
-              || section_name[path_spec_len] == '\0'));
-}
+      /* Are some nodes left? */
+      if (dest)
+        {
+          /* Trim it to the number of valid entries. */
+          (*array)->nelts = dest;
+          return FALSE;
+        }
+
+      /* No nodes left.  A NULL array is more efficient than an empty one. */
+      *array = NULL;
+    }
 
+  return TRUE;
+}
 
-/* Callback to parse a section and update the authz_baton if the
- * section denies access to the subtree the baton describes.
+/* Remove all rules and sub-nodes from NODE that are fully eclipsed by the
+ * "any-var" rule with sequence number LATEST_ANY_VAR.  Return TRUE, if
+ * there are no rules left in the sub-tree, including NODE.
+ * Allocate temporary data in SCRATCH_POOL.
  */
 static svn_boolean_t
-authz_parse_section(const char *section_name, void *baton, apr_pool_t *pool)
+trim_tree(node_t *node,
+          int latest_any_var,
+          apr_pool_t *scratch_pool)
 {
-  struct authz_lookup_baton *b = baton;
-  svn_boolean_t conclusive;
+  svn_boolean_t removed_all = TRUE;
 
-  /* Does the section apply to us? */
-  if (!is_applicable_section(b->qualified_repos_path, section_name)
-      && !is_applicable_section(b->repos_path, section_name))
+  /* For convenience, we allow NODE to be NULL: */
+  if (!node)
     return TRUE;
 
-  /* Work out what this section grants. */
-  b->allow = b->deny = 0;
-  svn_config_enumerate2(b->config, section_name,
-                        authz_parse_line, b, pool);
+  /* Do we have a later "any_var" rule at this node. */
+  if (   node->pattern_sub_nodes
+      && node->pattern_sub_nodes->any_var
+      &&   node->pattern_sub_nodes->any_var->rights.access.sequence_number
+         > latest_any_var)
+    {
+      latest_any_var
+        = node->pattern_sub_nodes->any_var->rights.access.sequence_number;
+    }
+
+  /* Is there a local rule at this node that is not eclipsed by any_var? */
+  if (has_local_rule(&node->rights))
+    {
+      /* Remove the local rule, if it got eclipsed.
+       * Note that for the latest any_var node, the sequence number is equal. */
+      if (node->rights.access.sequence_number >= latest_any_var)
+        removed_all = FALSE;
+      else
+         node->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
+    }
+
+  /* Process all sub-nodes. */
+  removed_all &= trim_subnode_hash(&node->sub_nodes, latest_any_var,
+                                   scratch_pool);
 
-  /* Has the section explicitly determined an access? */
-  conclusive = authz_access_is_determined(b->allow, b->deny,
-                                          b->required_access);
+  if (node->pattern_sub_nodes)
+    {
+      if (trim_tree(node->pattern_sub_nodes->any, latest_any_var,
+                    scratch_pool))
+        node->pattern_sub_nodes->any = NULL;
+      else
+        removed_all = FALSE;
 
-  /* Is access granted OR inconclusive? */
-  b->access = authz_access_is_granted(b->allow, b->deny,
-                                      b->required_access)
-    || !conclusive;
+      if (trim_tree(node->pattern_sub_nodes->any_var, latest_any_var,
+                    scratch_pool))
+        node->pattern_sub_nodes->any_var = NULL;
+      else
+        removed_all = FALSE;
+
+      removed_all &= trim_subnode_array(&node->pattern_sub_nodes->prefixes,
+                                        latest_any_var, scratch_pool);
+      removed_all &= trim_subnode_array(&node->pattern_sub_nodes->suffixes,
+                                        latest_any_var, scratch_pool);
+      removed_all &= trim_subnode_array(&node->pattern_sub_nodes->complex,
+                                        latest_any_var, scratch_pool);
+
+      /* Trim the tree as much as possible to speed up lookup(). */
+      if (removed_all)
+        node->pattern_sub_nodes = NULL;
+    }
 
-  /* As long as access isn't conclusively denied, carry on. */
-  return b->access;
+  return removed_all;
 }
 
+/* Forward declaration ... */
+static void
+finalize_tree(node_t *node,
+              limited_rights_t *sum,
+              apr_pool_t *scratch_pool);
 
-/* Validate access to the given user for the given path.  This
- * function checks rules for exactly the given path, and first tries
- * to access a section specific to the given repository before falling
- * back to pan-repository rules.
- *
- * Update *access_granted to inform the caller of the outcome of the
- * lookup.  Return a boolean indicating whether the access rights were
- * successfully determined.
+/* Call finalize_tree() on all elements in the HASH of node_t *, passing
+ * SUM along. HASH may be NULL. Use SCRATCH_POOL for temporary allocations.
  */
-static svn_boolean_t
-authz_get_path_access(svn_config_t *cfg, const char *repos_name,
-                      const char *path, const char *user,
-                      svn_repos_authz_access_t required_access,
-                      svn_boolean_t *access_granted,
-                      apr_pool_t *pool)
+static void
+finalize_subnode_hash(apr_hash_t *hash,
+                      limited_rights_t *sum,
+                      apr_pool_t *scratch_pool)
 {
-  const char *qualified_path;
-  struct authz_lookup_baton baton = { 0 };
-
-  baton.config = cfg;
-  baton.user = user;
-
-  /* Try to locate a repository-specific block first. */
-  qualified_path = apr_pstrcat(pool, repos_name, ":", path, SVN_VA_NULL);
-  svn_config_enumerate2(cfg, qualified_path,
-                        authz_parse_line, &baton, pool);
-
-  *access_granted = authz_access_is_granted(baton.allow, baton.deny,
-                                            required_access);
+  if (hash)
+    {
+      apr_hash_index_t *hi;
+      for (hi = apr_hash_first(scratch_pool, hash);
+           hi;
+           hi = apr_hash_next(hi))
+        finalize_tree(apr_hash_this_val(hi), sum, scratch_pool);
+    }
+}
 
-  /* If the first test has determined access, stop now. */
-  if (authz_access_is_determined(baton.allow, baton.deny,
-                                 required_access))
-    return TRUE;
+/* Call finalize_up_tree() on all elements in the ARRAY of node_t *,
+ * passing SUM along.  ARRAY may be NULL.  Use SCRATCH_POOL for temporary
+ * allocations.
+ */
+static void
+finalize_subnode_array(apr_array_header_t *array,
+                       limited_rights_t *sum,
+                       apr_pool_t *scratch_pool)
+{
+  if (array)
+    {
+      int i;
+      for (i = 0; i < array->nelts; ++i)
+        finalize_tree(APR_ARRAY_IDX(array, i, sorted_pattern_t).node, sum,
+                      scratch_pool);
+    }
+}
 
-  /* No repository specific rule, try pan-repository rules. */
-  svn_config_enumerate2(cfg, path, authz_parse_line, &baton, pool);
+/* Link prefixes within the sorted ARRAY. */
+static void
+link_prefix_patterns(apr_array_header_t *array)
+{
+  int i;
+  if (!array)
+    return;
 
-  *access_granted = authz_access_is_granted(baton.allow, baton.deny,
-                                            required_access);
-  return authz_access_is_determined(baton.allow, baton.deny,
-                                    required_access);
+  for (i = 1; i < array->nelts; ++i)
+    {
+      sorted_pattern_t *prev
+        = &APR_ARRAY_IDX(array, i - 1, sorted_pattern_t);
+      sorted_pattern_t *pattern
+        = &APR_ARRAY_IDX(array, i, sorted_pattern_t);
+
+      /* Does PATTERN potentially have a prefix in ARRAY?
+       * If so, at least the first char must match with the predecessor's
+       * because the array is sorted by that string. */
+      if (prev->node->segment.data[0] != pattern->node->segment.data[0])
+        continue;
+
+      /* Only the predecessor or any of its prefixes can be the closest
+       * prefix to PATTERN. */
+      for ( ; prev; prev = prev->next)
+        if (   prev->node->segment.len < pattern->node->segment.len
+            && !memcmp(prev->node->segment.data,
+                       pattern->node->segment.data,
+                       prev->node->segment.len))
+          {
+            pattern->next = prev;
+            break;
+          }
+    }
 }
 
-
-/* Validate access to the given user for the subtree starting at the
- * given path.  This function walks the whole authz file in search of
- * rules applying to paths in the requested subtree which deny the
- * requested access.
- *
- * As soon as one is found, or else when the whole ACL file has been
- * searched, return the updated authorization status.
+/* Recursively finalization the tree node properties for NODE.  Update SUM
+ * (of NODE's parent) by combining it with the recursive access rights info
+ * on NODE.  Use SCRATCH_POOL for temporary allocations.
  */
-static svn_boolean_t
-authz_get_tree_access(svn_config_t *cfg, const char *repos_name,
-                      const char *path, const char *user,
-                      svn_repos_authz_access_t required_access,
-                      apr_pool_t *pool)
+static void
+finalize_tree(node_t *node,
+              limited_rights_t *sum,
+              apr_pool_t *scratch_pool)
 {
-  struct authz_lookup_baton baton = { 0 };
+  limited_rights_t *local_sum = &node->rights;
 
-  baton.config = cfg;
-  baton.user = user;
-  baton.required_access = required_access;
-  baton.repos_path = path;
-  baton.qualified_repos_path = apr_pstrcat(pool, repos_name,
-                                           ":", path, SVN_VA_NULL);
-  /* Default to access granted if no rules say otherwise. */
-  baton.access = TRUE;
+  /* For convenience, we allow NODE to be NULL: */
+  if (!node)
+    return;
 
-  svn_config_enumerate_sections2(cfg, authz_parse_section,
-                                 &baton, pool);
+  /* Sum of rights at NODE - so far. */
+  if (has_local_rule(local_sum))
+    {
+      local_sum->max_rights = local_sum->access.rights;
+      local_sum->min_rights = local_sum->access.rights;
+    }
+  else
+    {
+      local_sum->min_rights = authz_access_write;
+      local_sum->max_rights = authz_access_none;
+    }
 
-  return baton.access;
-}
+  /* Process all sub-nodes. */
+  finalize_subnode_hash(node->sub_nodes, local_sum, scratch_pool);
 
+  if (node->pattern_sub_nodes)
+    {
+      finalize_tree(node->pattern_sub_nodes->any, local_sum, scratch_pool);
+      finalize_tree(node->pattern_sub_nodes->any_var, local_sum, scratch_pool);
+
+      finalize_subnode_array(node->pattern_sub_nodes->prefixes, local_sum,
+                             scratch_pool);
+      finalize_subnode_array(node->pattern_sub_nodes->suffixes, local_sum,
+                             scratch_pool);
+      finalize_subnode_array(node->pattern_sub_nodes->complex, local_sum,
+                             scratch_pool);
+
+      /* Link up the prefixes / suffixes. */
+      link_prefix_patterns(node->pattern_sub_nodes->prefixes);
+      link_prefix_patterns(node->pattern_sub_nodes->suffixes);
+    }
 
-/* Callback to parse sections of the configuration file, looking for
-   any kind of granted access.  Implements the
-   svn_config_section_enumerator2_t interface. */
-static svn_boolean_t
-authz_get_any_access_parser_cb(const char *section_name, void *baton,
-                               apr_pool_t *pool)
-{
-  struct authz_lookup_baton *b = baton;
+  /* Add our min / max info to the parent's info.
+   * Idempotent for parent == node (happens at root). */
+  combine_right_limits(sum, local_sum);
+}
 
-  /* Does the section apply to the query? */
-  if (section_name[0] == '/'
-      || strncmp(section_name, b->qualified_repos_path,
-                 strlen(b->qualified_repos_path)) == 0)
+/* From the authz CONFIG, extract the parts relevant to USER and REPOSITORY.
+ * Return the filtered rule tree.
+ */
+static node_t *
+create_user_authz(authz_full_t *authz,
+                  const char *repository,
+                  const char *user,
+                  apr_pool_t *result_pool,
+                  apr_pool_t *scratch_pool)
+{
+  int i;
+  node_t *root = create_node(NULL, result_pool);
+  construction_context_t *ctx = create_construction_context(scratch_pool);
+
+  /* Use a separate sub-pool to keep memory usage tight. */
+  apr_pool_t *subpool = svn_pool_create(scratch_pool);
+
+  /* Find all ACLs for REPOSITORY. 
+   * Note that repo-specific rules replace global rules,
+   * even if they don't apply to the current user. */
+  apr_array_header_t *acls = apr_array_make(subpool, authz->acls->nelts,
+                                            sizeof(authz_acl_t *));
+  for (i = 0; i < authz->acls->nelts; ++i)
     {
-      b->allow = b->deny = svn_authz_none;
+      const authz_acl_t *acl = &APR_ARRAY_IDX(authz->acls, i, authz_acl_t);
+      if (svn_authz__acl_applies_to_repo(acl, repository))
+        {
+          /* ACLs in the AUTHZ are sorted by path and repository.
+           * So, if there is a rule for the repo and a global rule for the
+           * same path, we will detect them here. */
+          if (acls->nelts)
+            {
+              const authz_acl_t *prev_acl
+                = APR_ARRAY_IDX(acls, acls->nelts - 1, const authz_acl_t *);
+              if (svn_authz__compare_paths(&prev_acl->rule, &acl->rule) == 0)
+                {
+                  SVN_ERR_ASSERT_NO_RETURN(!strcmp(prev_acl->rule.repos,
+                                                   AUTHZ_ANY_REPOSITORY));
+                  SVN_ERR_ASSERT_NO_RETURN(strcmp(acl->rule.repos,
+                                                  AUTHZ_ANY_REPOSITORY));
+                  apr_array_pop(acls);
+                }
+            }
+
+          APR_ARRAY_PUSH(acls, const authz_acl_t *) = acl;
+        }
+    }
 
-      svn_config_enumerate2(b->config, section_name,
-                            authz_parse_line, baton, pool);
-      b->access = authz_access_is_granted(b->allow, b->deny,
-                                          b->required_access);
+  /* Filtering and tree construction. */
+  for (i = 0; i < acls->nelts; ++i)
+    process_acl(ctx, APR_ARRAY_IDX(acls, i, const authz_acl_t *),
+                root, repository, user, result_pool, subpool);
 
-      /* Continue as long as we don't find a determined, granted access. */
-      return !(b->access
-               && authz_access_is_determined(b->allow, b->deny,
-                                             b->required_access));
+  /* If there is no relevant rule at the root node, the "no access" default
+   * applies. Give it a SEQUENCE_NUMBER that will never overrule others. */
+  if (!has_local_rule(&root->rights))
+    {
+      root->rights.access.sequence_number = 0;
+      root->rights.access.rights = authz_access_none;
     }
 
-  return TRUE;
-}
-
+  /* Trim the tree.
+   *
+   * We can't do pattern comparison, so for most pattern rules we cannot
+   * say that a set of rules "eclipses" / overrides a given other set of
+   * rules for all possible paths.  That limits the accuracy of our check
+   * for recursive access in similar ways than for non-pattern rules.
+   *
+   * However, the user expects a rule ending with "**" to eclipse any older
+   * rule in that sub-tree recursively.  So, this trim function removes
+   * eclipsed nodes from the tree.
+   */
+  svn_pool_clear(subpool);
+  trim_tree(root, NO_SEQUENCE_NUMBER, subpool);
 
-/* Walk through the authz CFG to check if USER has the REQUIRED_ACCESS
- * to any path within the REPOSITORY.  Return TRUE if so.  Use POOL
- * for temporary allocations. */
-static svn_boolean_t
-authz_get_any_access(svn_config_t *cfg, const char *repos_name,
-                     const char *user,
-                     svn_repos_authz_access_t required_access,
-                     apr_pool_t *pool)
-{
-  struct authz_lookup_baton baton = { 0 };
-
-  baton.config = cfg;
-  baton.user = user;
-  baton.required_access = required_access;
-  baton.access = FALSE; /* Deny access by default. */
-  baton.repos_path = "/";
-  baton.qualified_repos_path = apr_pstrcat(pool, repos_name,
-                                           ":/", SVN_VA_NULL);
-
-  /* We could have used svn_config_enumerate2 for "repos_name:/".
-   * However, this requires access for root explicitly (which the user
-   * may not always have). So we end up enumerating the sections in
-   * the authz CFG and stop on the first match with some access for
-   * this user. */
-  svn_config_enumerate_sections2(cfg, authz_get_any_access_parser_cb,
-                                 &baton, pool);
-
-  /* If walking the configuration was inconclusive, deny access. */
-  if (!authz_access_is_determined(baton.allow,
-                                  baton.deny, baton.required_access))
-    return FALSE;
+  /* Calculate recursive rights. 
+   *
+   * This is a bottom-up calculation of the range of access rights
+   * specified anywhere in  the respective sub-tree, including the base
+   * node itself.
+   *
+   * To prevent additional finalization passes, we piggy-back the addition
+   * of the ordering links of the prefix and suffix sub-node rules.
+   */
+  svn_pool_clear(subpool);
+  finalize_tree(root, &root->rights, subpool);
 
-  return baton.access;
+  /* Done. */
+  svn_pool_destroy(subpool);
+  return root;
 }
 
-
 
-/*** Validating the authz file. ***/
+/*** Lookup. ***/
 
-/* Check for errors in GROUP's definition of CFG.  The errors
- * detected are references to non-existent groups and circular
- * dependencies between groups.  If an error is found, return
- * SVN_ERR_AUTHZ_INVALID_CONFIG.  Use POOL for temporary
- * allocations only.
- *
- * CHECKED_GROUPS should be an empty (it is used for recursive calls).
- */
-static svn_error_t *
-authz_group_walk(svn_config_t *cfg,
-                 const char *group,
-                 apr_hash_t *checked_groups,
-                 apr_pool_t *pool)
+/* Reusable lookup state object. It is easy to pass to functions and
+ * recycling it between lookups saves significant setup costs. */
+typedef struct lookup_state_t
 {
-  const char *value;
-  apr_array_header_t *list;
-  int i;
+  /* Rights immediately applying to this node and limits to the rights to
+   * any sub-path. */
+  limited_rights_t rights;
 
-  svn_config_get(cfg, &value, "groups", group, NULL);
-  /* Having a non-existent group in the ACL configuration might be the
-     sign of a typo.  Refuse to perform authz on uncertain rules. */
-  if (!value)
-    return svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                             "An authz rule refers to group '%s', "
-                             "which is undefined",
-                             group);
+  /* Nodes applying to the path followed so far. */
+  apr_array_header_t *current;
 
-  list = svn_cstring_split(value, ",", TRUE, pool);
+  /* Temporary array containing the nodes applying to the next path
+   * segment (used to build up the next contents of CURRENT). */
+  apr_array_header_t *next;
 
-  for (i = 0; i < list->nelts; i++)
-    {
-      const char *group_user = APR_ARRAY_IDX(list, i, char *);
+  /* Scratch pad for path operations. */
+  svn_stringbuf_t *scratch_pad;
 
-      /* If the 'user' is a subgroup, recurse into it. */
-      if (*group_user == '@')
-        {
-          /* A circular dependency between groups is a Bad Thing.  We
-             don't do authz with invalid ACL files. */
-          if (svn_hash_gets(checked_groups, &group_user[1]))
-            return svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG,
-                                     NULL,
-                                     "Circular dependency between "
-                                     "groups '%s' and '%s'",
-                                     &group_user[1], group);
-
-          /* Add group to hash of checked groups. */
-          svn_hash_sets(checked_groups, &group_user[1], "");
-
-          /* Recurse on that group. */
-          SVN_ERR(authz_group_walk(cfg, &group_user[1],
-                                   checked_groups, pool));
-
-          /* Remove group from hash of checked groups, so that we don't
-             incorrectly report an error if we see it again as part of
-             another group. */
-          svn_hash_sets(checked_groups, &group_user[1], NULL);
-        }
-      else if (*group_user == '&')
-        {
-          const char *alias;
-
-          svn_config_get(cfg, &alias, "aliases", &group_user[1], NULL);
-          /* Having a non-existent alias in the ACL configuration might be the
-             sign of a typo.  Refuse to perform authz on uncertain rules. */
-          if (!alias)
-            return svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "An authz rule refers to alias '%s', "
-                                     "which is undefined",
-                                     &group_user[1]);
-        }
-    }
+  /* After each lookup iteration, CURRENT and PARENT_RIGHTS will
+   * apply to this path. */
+  svn_stringbuf_t *parent_path;
 
-  return SVN_NO_ERROR;
-}
+  /* Rights that apply at PARENT_PATH, if PARENT_PATH is not empty. */
+  limited_rights_t parent_rights;
 
+} lookup_state_t;
 
-/* Callback to perform some simple sanity checks on an authz rule.
- *
- * - If RULE_MATCH_STRING references a group or an alias, verify that
- *   the group or alias definition exists.
- * - If RULE_MATCH_STRING specifies a token (starts with $), verify
- *   that the token name is valid.
- * - If RULE_MATCH_STRING is using inversion, verify that it isn't
- *   doing it more than once within the one rule, and that it isn't
- *   "~*", as that would never match.
- * - Check that VALUE part of the rule specifies only allowed rule
- *   flag characters ('r' and 'w').
- *
- * Return TRUE if the rule has no errors. Use BATON for context and
- * error reporting.
- */
-static svn_boolean_t authz_validate_rule(const char *rule_match_string,
-                                         const char *value,
-                                         void *baton,
-                                         apr_pool_t *pool)
+/* Constructor for lookup_state_t. */
+static lookup_state_t *
+create_lookup_state(apr_pool_t *result_pool)
 {
-  const char *val;
-  const char *match = rule_match_string;
-  struct authz_validate_baton *b = baton;
+  lookup_state_t *state = apr_pcalloc(result_pool, sizeof(*state));
+ 
+  state->next = apr_array_make(result_pool, 4, sizeof(node_t *));
+  state->current = apr_array_make(result_pool, 4, sizeof(node_t *));
 
-  /* Make sure the user isn't using double-negatives. */
-  if (match[0] == '~')
-    {
-      /* Bump the pointer past the inversion for the other checks. */
-      match++;
+  /* Virtually all path segments should fit into this buffer.  If they
+   * don't, the buffer gets automatically reallocated.
+   *
+   * Using a smaller initial size would be fine as well but does not
+   * buy us much for the increased risk of being expanded anyway - at
+   * some extra cost. */
+  state->scratch_pad = svn_stringbuf_create_ensure(200, result_pool);
 
-      /* Another inversion is a double negative; we can't not stop. */
-      if (match[0] == '~')
-        {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "Rule '%s' has more than one "
-                                     "inversion; double negatives are "
-                                     "not permitted.",
-                                     rule_match_string);
-          return FALSE;
-        }
+  /* Most paths should fit into this buffer.  The same rationale as
+   * above applies. */
+  state->parent_path = svn_stringbuf_create_ensure(200, result_pool);
 
-      /* Make sure that the rule isn't "~*", which won't ever match. */
-      if (strcmp(match, "*") == 0)
-        {
-          b->err = svn_error_create(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                    "Authz rules with match string '~*' "
-                                    "are not allowed, because they never "
-                                    "match anyone.");
-          return FALSE;
-        }
-    }
+  return state;
+}
 
-  /* If the rule applies to a group, check its existence. */
-  if (match[0] == '@')
+/* Clear the current contents of STATE and re-initialize it for ROOT.
+ * Check whether we can reuse a previous parent path lookup to shorten
+ * the current PATH walk.  Return the full or remaining portion of
+ * PATH, respectively.  PATH must not be NULL. */
+static const char *
+init_lockup_state(lookup_state_t *state,
+                  node_t *root,
+                  const char *path)
+{
+  apr_size_t len = strlen(path);
+  if (   (len > state->parent_path->len)
+      && state->parent_path->len
+      && (path[state->parent_path->len] == '/')
+      && !memcmp(path, state->parent_path->data, state->parent_path->len))
     {
-      const char *group = &match[1];
+      /* The PARENT_PATH of the previous lookup is actually a parent path
+       * of PATH.  The CURRENT node list already matches the parent path
+       * and we only have to set the correct rights info. */
+      state->rights = state->parent_rights;
 
-      svn_config_get(b->config, &val, "groups", group, NULL);
-
-      /* Having a non-existent group in the ACL configuration might be
-         the sign of a typo.  Refuse to perform authz on uncertain
-         rules. */
-      if (!val)
-        {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "An authz rule refers to group "
-                                     "'%s', which is undefined",
-                                     rule_match_string);
-          return FALSE;
-        }
+      /* Tell the caller where to proceed. */
+      return path + state->parent_path->len;
     }
 
-  /* If the rule applies to an alias, check its existence. */
-  if (match[0] == '&')
-    {
-      const char *alias = &match[1];
+  /* Start lookup at ROOT for the full PATH. */
+  state->rights = root->rights;
+  state->parent_rights = root->rights;
 
-      svn_config_get(b->config, &val, "aliases", alias, NULL);
+  apr_array_clear(state->next);
+  apr_array_clear(state->current);
+  APR_ARRAY_PUSH(state->current, node_t *) = root;
 
-      if (!val)
-        {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "An authz rule refers to alias "
-                                     "'%s', which is undefined",
-                                     rule_match_string);
-          return FALSE;
-        }
-     }
+  /* Var-segment rules match empty segments as well */
+  if (root->pattern_sub_nodes && root->pattern_sub_nodes->any_var)
+   {
+      node_t *node = root->pattern_sub_nodes->any_var;
 
-  /* If the rule specifies a token, check its validity. */
-  if (match[0] == '$')
-    {
-      const char *token_name = &match[1];
+      /* This is non-recursive due to ACL normalization. */
+      combine_access(&state->rights, &node->rights);
+      combine_right_limits(&state->rights, &node->rights);
+      APR_ARRAY_PUSH(state->current, node_t *) = node;
+   }
+
+  svn_stringbuf_setempty(state->parent_path);
+  svn_stringbuf_setempty(state->scratch_pad);
 
-      if ((strcmp(token_name, "anonymous") != 0)
-       && (strcmp(token_name, "authenticated") != 0))
+  return path;
+}
+
+/* Add NODE to the list of NEXT nodes in STATE.  NODE may be NULL in which
+ * case this is a no-op.  Also update and aggregate the access rights data
+ * for the next path segment.
+ */
+static void
+add_next_node(lookup_state_t *state,
+              node_t *node)
+{
+  /* Allowing NULL nodes simplifies the caller. */
+  if (node)
+    {
+      /* The rule with the highest sequence number is the one that applies.
+       * Not all nodes that we are following have rules that apply directly
+       * to this path but are mere intermediates that may only have some
+       * matching deep sub-node. */
+      combine_access(&state->rights, &node->rights);
+
+      /* The rule tree node can be seen as an overlay of all the nodes that
+       * we are following.  Any of them _may_ match eventually, so the min/
+       * max possible access rights are a combination of all these sub-trees.
+       */
+      combine_right_limits(&state->rights, &node->rights);
+
+      /* NODE is now enlisted as a (potential) match for the next segment. */
+      APR_ARRAY_PUSH(state->next, node_t *) = node;
+
+      /* Variable length sub-segment sequences apply to the same node as
+       * they match empty sequences as well. */
+      if (node->pattern_sub_nodes && node->pattern_sub_nodes->any_var)
         {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "Unrecognized authz token '%s'.",
-                                     rule_match_string);
-          return FALSE;
+          node = node->pattern_sub_nodes->any_var;
+
+          /* This is non-recursive due to ACL normalization. */
+          combine_access(&state->rights, &node->rights);
+          combine_right_limits(&state->rights, &node->rights);
+          APR_ARRAY_PUSH(state->next, node_t *) = node;
         }
     }
+}
 
-  val = value;
+/* If PREFIX is indeed a prefix (or exact match) or SEGMENT, add the
+ * node in PREFIX to STATE. */
+static void
+add_if_prefix_matches(lookup_state_t *state,
+                      const sorted_pattern_t *prefix,
+                      const svn_stringbuf_t *segment)
+{
+  node_t *node = prefix->node;
+  if (   node->segment.len <= segment->len
+      && !memcmp(node->segment.data, segment->data, node->segment.len))
+    add_next_node(state, node);
+}
 
-  while (*val)
+/* Scan the PREFIXES array of node_t* for all entries whose SEGMENT members
+ * are prefixes of SEGMENT.  Add these to STATE for the next tree level. */
+static void
+add_prefix_matches(lookup_state_t *state,
+                   const svn_stringbuf_t *segment,
+                   apr_array_header_t *prefixes)
+{
+  /* Index of the first node that might be a match.  All matches will
+   * be at this and the immediately following indexes. */
+  int i = svn_sort__bsearch_lower_bound(prefixes, segment->data,
+                                        compare_node_path_segment);
+
+  /* The entry we found may be an exact match (but not a true prefix).
+   * The prefix matching test will still work. */
+  if (i < prefixes->nelts)
+    add_if_prefix_matches(state,
+                          &APR_ARRAY_IDX(prefixes, i, sorted_pattern_t),
+                          segment);
+
+  /* The immediate predecessor may be a true prefix and all potential
+   * prefixes can be found following the NEXT links between the array
+   * indexes. */
+  if (i > 0)
     {
-      if (*val != 'r' && *val != 'w' && ! svn_ctype_isspace(*val))
+      sorted_pattern_t *pattern;
+      for (pattern = &APR_ARRAY_IDX(prefixes, i - 1, sorted_pattern_t);
+           pattern;
+           pattern = pattern->next)
         {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "The character '%c' in rule '%s' is not "
-                                     "allowed in authz rules", *val,
-                                     rule_match_string);
-          return FALSE;
+          add_if_prefix_matches(state, pattern, segment);
         }
-
-      ++val;
     }
-
-  return TRUE;
 }
 
-/* Callback to check ALIAS's definition for validity.  Use
-   BATON for context and error reporting. */
-static svn_boolean_t authz_validate_alias(const char *alias,
-                                          const char *value,
-                                          void *baton,
-                                          apr_pool_t *pool)
+/* Scan the PATTERNS array of node_t* for all entries whose SEGMENT members
+ * (usually containing wildcards) match SEGMENT.  Add these to STATE for the
+ * next tree level. */
+static void
+add_complex_matches(lookup_state_t *state,
+                    const svn_stringbuf_t *segment,
+                    apr_array_header_t *patterns)
 {
-  /* No checking at the moment, every alias is valid */
-  return TRUE;
+  int i;
+  for (i = 0; i < patterns->nelts; ++i)
+    {
+      node_t *node = APR_ARRAY_IDX(patterns, i, sorted_pattern_t).node;
+      if (0 == apr_fnmatch(node->segment.data, segment->data, 0))
+        add_next_node(state, node);
+    }
 }
 
-
-/* Callback to check GROUP's definition for cyclic dependancies.  Use
-   BATON for context and error reporting. */
-static svn_boolean_t authz_validate_group(const char *group,
-                                          const char *value,
-                                          void *baton,
-                                          apr_pool_t *pool)
+/* Extract the next segment from PATH and copy it into SEGMENT, whose current
+ * contents get overwritten.  Empty paths ("") are supported and leading '/'
+ * segment separators will be interpreted as an empty segment ("").  Non-
+ * normalizes parts, i.e. sequences of '/', will be treated as a single '/'.
+ *
+ * Return the start of the next segment within PATH, skipping the '/'
+ * separator(s).  Return NULL, if there are no further segments.
+ *
+ * The caller (only called by lookup(), ATM) must ensure that SEGMENT has
+ * enough room to store all of PATH.
+ */
+static const char *
+next_segment(svn_stringbuf_t *segment,
+             const char *path)
 {
-  struct authz_validate_baton *b = baton;
+  apr_size_t len;
+  char c;
+
+  /* Read and scan PATH for NUL and '/' -- whichever comes first. */
+  for (len = 0, c = *path; c; c = path[++len])
+    if (c == '/')
+      {
+        /* End of segment. */
+        segment->data[len] = 0;
+        segment->len = len;
+
+        /* If PATH is not normalized, this is where we skip whole sequences
+         * of separators. */
+        while (path[++len] == '/')
+          ;
+
+        /* Continue behind the last separator in the sequence.  We will
+         * treat trailing '/' as indicating an empty trailing segment.
+         * Therefore, we never have to return NULL here. */
+        return path + len;
+      }
+    else
+      {
+        /* Copy segment contents directly into the result buffer.
+         * On many architectures, this is almost or entirely for free. */
+        segment->data[len] = c;
+      }
+
+  /* No separator found, so all of PATH has been the last segment. */
+  segment->data[len] = 0;
+  segment->len = len;
+
+  /* Tell the caller that this has been the last segment. */
+  return NULL;
+}
 
-  b->err = authz_group_walk(b->config, group, apr_hash_make(pool), pool);
-  if (b->err)
-    return FALSE;
+/* Starting at the respective user's authz root node provided with STATE,
+ * follow PATH and return TRUE, iff the REQUIRED access has been granted to
+ * that user for this PATH.  REQUIRED must not contain svn_authz_recursive.
+ * If RECURSIVE is set, all paths in the sub-tree at and below PATH must
+ * have REQUIRED access.  PATH does not need to be normalized, may be empty
+ * but must not be NULL.
+ */
+static svn_boolean_t
+lookup(lookup_state_t *state,
+       const char *path,
+       authz_access_t required,
+       svn_boolean_t recursive,
+       apr_pool_t *scratch_pool)
+{
+  /* Create a scratch pad large enough to hold any of PATH's segments. */
+  apr_size_t path_len = strlen(path);
+  svn_stringbuf_ensure(state->scratch_pad, path_len);
 
-  return TRUE;
-}
+  /* Normalize start and end of PATH.  Most paths will be fully normalized,
+   * so keep the overhead as low as possible. */
+  if (path_len && path[path_len-1] == '/')
+    {
+      do
+      {
+        --path_len;
+      }
+      while (path_len && path[path_len-1] == '/');
+      path = apr_pstrmemdup(scratch_pool, path, path_len);
+    }
 
+  while (path[0] == '/')
+    ++path;     /* Don't update PATH_LEN as we won't need it anymore. */
 
-/* Callback to check the contents of the configuration section given
-   by NAME.  Use BATON for context and error reporting. */
-static svn_boolean_t authz_validate_section(const char *name,
-                                            void *baton,
-                                            apr_pool_t *pool)
-{
-  struct authz_validate_baton *b = baton;
-
-  /* Use the group checking callback for the "groups" section... */
-  if (strcmp(name, "groups") == 0)
-    svn_config_enumerate2(b->config, name, authz_validate_group,
-                          baton, pool);
-  /* ...and the alias checking callback for "aliases"... */
-  else if (strcmp(name, "aliases") == 0)
-    svn_config_enumerate2(b->config, name, authz_validate_alias,
-                          baton, pool);
-  /* ...but for everything else use the rule checking callback. */
-  else
+  /* Actually walk the path rule tree following PATH until we run out of
+   * either tree or PATH. */
+  while (state->current->nelts && path)
     {
-      /* Validate the section's name. Skip the optional REPOS_NAME. */
-      const char *fspath = strchr(name, ':');
-      if (fspath)
-        fspath++;
-      else
-        fspath = name;
-      if (! svn_fspath__is_canonical(fspath))
+      apr_array_header_t *temp;
+      int i;
+      svn_stringbuf_t *segment = state->scratch_pad;
+
+      /* Shortcut 1: We could nowhere find enough rights in this sub-tree. */
+      if ((state->rights.max_rights & required) != required)
+        return FALSE;
+
+      /* Shortcut 2: We will find enough rights everywhere in this sub-tree. */
+      if ((state->rights.min_rights & required) == required)
+        return TRUE;
+
+      /* Extract the next segment. */
+      path = next_segment(segment, path);
+
+      /* Initial state for this segment. */
+      apr_array_clear(state->next);
+      state->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
+      state->rights.access.rights = authz_access_none;
+
+      /* These init values ensure that the first node's value will be used
+       * when combined with them.  If there is no first node,
+       * state->access.sequence_number remains unchanged and we will use
+       * the parent's (i.e. inherited) access rights. */
+      state->rights.min_rights = authz_access_write;
+      state->rights.max_rights = authz_access_none;
+
+      /* Update the PARENT_PATH member in STATE to match the nodes in
+       * CURRENT at the end of this iteration, i.e. if and when NEXT
+       * has become CURRENT. */
+      if (path)
         {
-          b->err = svn_error_createf(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                                     "Section name '%s' contains non-canonical "
-                                     "fspath '%s'",
-                                     name, fspath);
-          return FALSE;
+          svn_stringbuf_appendbyte(state->parent_path, '/');
+          svn_stringbuf_appendbytes(state->parent_path, segment->data,
+                                    segment->len);
         }
 
-      svn_config_enumerate2(b->config, name, authz_validate_rule,
-                            baton, pool);
+      /* Scan follow all alternative routes to the next level. */
+      for (i = 0; i < state->current->nelts; ++i)
+        {
+          node_t *node = APR_ARRAY_IDX(state->current, i, node_t *);
+          if (node->sub_nodes)
+            add_next_node(state, apr_hash_get(node->sub_nodes, segment->data,
+                                              segment->len));
+
+          /* Process alternative, wildcard-based sub-nodes. */
+          if (node->pattern_sub_nodes)
+            {
+              add_next_node(state, node->pattern_sub_nodes->any);
+
+              /* If the current node represents a "**" pattern, it matches
+               * to all levels. So, add it to the list for the NEXT level. */
+              if (node->pattern_sub_nodes->repeat)
+                add_next_node(state, node);
+
+              /* Find all prefix pattern matches. */
+              if (node->pattern_sub_nodes->prefixes)
+                add_prefix_matches(state, segment,
+                                   node->pattern_sub_nodes->prefixes);
+
+              if (node->pattern_sub_nodes->complex)
+                add_complex_matches(state, segment,
+                                    node->pattern_sub_nodes->complex);
+
+              /* Find all suffux pattern matches.
+               * This must be the last check as it destroys SEGMENT. */
+              if (node->pattern_sub_nodes->suffixes)
+                {
+                  /* Suffixes behave like reversed prefixes. */
+                  svn_authz__reverse_string(segment->data, segment->len);
+                  add_prefix_matches(state, segment,
+                                     node->pattern_sub_nodes->suffixes);
+                }
+            }
+        }
+
+      /* If no rule applied to this SEGMENT directly, the parent rights
+       * will apply to at least the SEGMENT node itself and possibly
+       * other parts deeper in it's subtree. */
+      if (!has_local_rule(&state->rights))
+        {
+          state->rights.access = state->parent_rights.access;
+          state->rights.min_rights &= state->parent_rights.access.rights;
+          state->rights.max_rights |= state->parent_rights.access.rights;
+        }
+
+      /* The list of nodes for SEGMENT is now complete.  If we need to
+       * continue, make it the current and put the old one into the recycler.
+       *
+       * If this is the end of the path, keep the parent path and rights in
+       * STATE as are such that sibling lookups will benefit from it.
+       */
+      if (path)
+        {
+          temp = state->current;
+          state->current = state->next;
+          state->next = temp;
+
+          /* In STATE, PARENT_PATH, PARENT_RIGHTS and CURRENT are now in sync. */
+          state->parent_rights = state->rights;
+        }
     }
 
-  if (b->err)
-    return FALSE;
+  /* If we check recursively, none of the (potential) sub-paths must have
+   * less than the REQUIRED access rights.  "Potential" because we don't
+   * verify that the respective paths actually exist in the repository.
+   */
+  if (recursive)
+    return (state->rights.min_rights & required) == required;
 
-  return TRUE;
+  /* Return whether the access rights on PATH fully include REQUIRED. */
+  return (state->rights.access.rights & required) == required;
 }
 
+
+
+/*** The authz data structure. ***/
 
-svn_error_t *
-svn_repos__authz_validate(svn_authz_t *authz, apr_pool_t *pool)
+/* An entry in svn_authz_t's USER_RULES cache.  All members must be
+ * allocated in the POOL and the latter has to be cleared / destroyed
+ * before overwriting the entries' contents.
+ */
+struct authz_user_rules_t
 {
-  struct authz_validate_baton baton = { 0 };
+  /* User name for which we filtered the rules.
+   * User NULL for the anonymous user. */
+  const char *user;
 
-  baton.err = SVN_NO_ERROR;
-  baton.config = authz->cfg;
+  /* Repository name for which we filtered the rules.
+   * May be empty but never NULL for used entries. */
+  const char *repository;
 
-  /* Step through the entire rule file stopping on error. */
-  svn_config_enumerate_sections2(authz->cfg, authz_validate_section,
-                                 &baton, pool);
-  SVN_ERR(baton.err);
+  /* The combined min/max rights USER has on REPOSITORY. */
+  authz_rights_t global_rights;
 
-  return SVN_NO_ERROR;
-}
+  /* Root of the filtered path rule tree.
+   * Will remain NULL until the first usage. */
+  node_t *root;
 
+  /* Reusable lookup state instance. */
+  lookup_state_t *lookup_state;
 
-/* Retrieve the file at DIRENT (contained in a repo) then parse it as a config
- * file placing the result into CFG_P allocated in POOL.
- *
- * If DIRENT cannot be parsed as a config file then an error is returned.  The
- * contents of CFG_P is then undefined.  If MUST_EXIST is TRUE, a missing
- * authz file is also an error.  The CASE_SENSITIVE controls the lookup
- * behavior for section and option names alike.
- *
- * SCRATCH_POOL will be used for temporary allocations. */
-static svn_error_t *
-authz_retrieve_config_repo(svn_config_t **cfg_p,
-                           const char *dirent,
-                           svn_boolean_t must_exist,
-                           svn_boolean_t case_sensitive,
-                           apr_pool_t *result_pool,
-                           apr_pool_t *scratch_pool)
+  /* Pool from which all data within this struct got allocated.
+   * Can be destroyed or cleaned up with no further side-effects. */
+  apr_pool_t *pool;
+};
+
+/* Return TRUE, iff AUTHZ matches the pair of REPOS_NAME and USER.
+ * Note that USER may be NULL.
+ */
+static svn_boolean_t
+matches_filtered_tree(const authz_user_rules_t *authz,
+                      const char *repos_name,
+                      const char *user)
 {
-  svn_error_t *err;
-  svn_repos_t *repos;
-  const char *repos_root_dirent;
-  const char *fs_path;
-  svn_fs_t *fs;
-  svn_fs_root_t *root;
-  svn_revnum_t youngest_rev;
-  svn_node_kind_t node_kind;
-  svn_stream_t *contents;
-
-  /* Search for a repository in the full path. */
-  repos_root_dirent = svn_repos_find_root_path(dirent, scratch_pool);
-  if (!repos_root_dirent)
-    return svn_error_createf(SVN_ERR_RA_LOCAL_REPOS_NOT_FOUND, NULL,
-                             "Unable to find repository at '%s'", dirent);
-
-  /* Attempt to open a repository at repos_root_dirent. */
-  SVN_ERR(svn_repos_open3(&repos, repos_root_dirent, NULL, scratch_pool,
-                          scratch_pool));
-
-  fs_path = &dirent[strlen(repos_root_dirent)];
-
-  /* Root path is always a directory so no reason to go any further */
-  if (*fs_path == '\0')
-    return svn_error_createf(SVN_ERR_ILLEGAL_TARGET, NULL,
-                             "'/' is not a file in repo '%s'",
-                             repos_root_dirent);
-
-  /* We skip some things that are non-important for how we're going to use
-   * this repo connection.  We do not set any capabilities since none of
-   * the current ones are important for what we're doing.  We also do not
-   * setup the environment that repos hooks would run under since we won't
-   * be triggering any. */
-
-  /* Get the filesystem. */
-  fs = svn_repos_fs(repos);
-
-  /* Find HEAD and the revision root */
-  SVN_ERR(svn_fs_youngest_rev(&youngest_rev, fs, scratch_pool));
-  SVN_ERR(svn_fs_revision_root(&root, fs, youngest_rev, scratch_pool));
-
-  SVN_ERR(svn_fs_check_path(&node_kind, root, fs_path, scratch_pool));
-  if (node_kind == svn_node_none)
+  /* Does the user match? */
+  if (user)
     {
-      if (!must_exist)
-        {
-          SVN_ERR(svn_config_create2(cfg_p, case_sensitive, case_sensitive,
-                                     result_pool));
-          return SVN_NO_ERROR;
-        }
-      else
-        {
-          return svn_error_createf(SVN_ERR_ILLEGAL_TARGET, NULL,
-                                   "'%s' path not found in repo '%s'", fs_path,
-                                   repos_root_dirent);
-        }
+      if (authz->user == NULL || strcmp(user, authz->user))
+        return FALSE;
     }
-  else if (node_kind != svn_node_file)
-    {
-      return svn_error_createf(SVN_ERR_ILLEGAL_TARGET, NULL,
-                               "'%s' is not a file in repo '%s'", fs_path,
-                               repos_root_dirent);
-    }
-
-  SVN_ERR(svn_fs_file_contents(&contents, root, fs_path, scratch_pool));
-  err = svn_config_parse(cfg_p, contents, case_sensitive, case_sensitive,
-                         result_pool);
-
-  /* Add the URL to the error stack since the parser doesn't have it. */
-  if (err != SVN_NO_ERROR)
-    return svn_error_createf(err->apr_err, err,
-                             "Error while parsing config file: '%s' in repo '%s':",
-                             fs_path, repos_root_dirent);
+  else if (authz->user != NULL)
+    return FALSE;
 
-  return SVN_NO_ERROR;
+  /* Does the repository match as well? */
+  return strcmp(repos_name, authz->repository) == 0;
 }
 
-svn_error_t *
-svn_repos__retrieve_config(svn_config_t **cfg_p,
-                           const char *path,
-                           svn_boolean_t must_exist,
-                           svn_boolean_t case_sensitive,
-                           apr_pool_t *pool)
+/* Check if AUTHZ's already contains a path rule tree filtered for this
+ * USER, REPOS_NAME combination.  If that does not exist, yet, create one
+ * but don't construct the actual filtered tree, yet.
+ */
+static authz_user_rules_t *
+get_user_rules(svn_authz_t *authz,
+               const char *repos_name,
+               const char *user)
 {
-  if (svn_path_is_url(path))
+  apr_pool_t *pool;
+
+  /* Search our cache for a suitable previously filtered tree. */
+  if (authz->filtered)
     {
-      const char *dirent;
-      svn_error_t *err;
-      apr_pool_t *scratch_pool = svn_pool_create(pool);
+      /* Is this a suitable filtered tree? */
+      if (matches_filtered_tree(authz->filtered, repos_name, user))
+        return authz->filtered;
 
-      err = svn_uri_get_dirent_from_file_url(&dirent, path, scratch_pool);
+      /* Drop the old filtered tree before creating a new one. */
+      svn_pool_destroy(authz->filtered->pool);
+      authz->filtered = NULL;
+    }
 
-      if (err == SVN_NO_ERROR)
-        err = authz_retrieve_config_repo(cfg_p, dirent, must_exist,
-                                         case_sensitive, pool, scratch_pool);
+  /* Global cache lookup.  Filter the full model only if necessary. */
+  pool = svn_pool_create(authz->pool);
 
-      /* Close the repos and streams we opened. */
-      svn_pool_destroy(scratch_pool);
+  /* Write a new entry. */
+  authz->filtered = apr_palloc(pool, sizeof(*authz->filtered));
+  authz->filtered->pool = pool;
+  authz->filtered->repository = apr_pstrdup(pool, repos_name);
+  authz->filtered->user = user ? apr_pstrdup(pool, user) : NULL;
+  authz->filtered->lookup_state = create_lookup_state(pool);
+  authz->filtered->root = NULL;
 
-      return err;
-    }
-  else
-    {
-      /* Outside of repo file or Windows registry*/
-      SVN_ERR(svn_config_read3(cfg_p, path, must_exist, case_sensitive,
-                               case_sensitive, pool));
-    }
+  svn_authz__get_global_rights(&authz->filtered->global_rights,
+                               authz->full, user, repos_name);
 
-  return SVN_NO_ERROR;
+  return authz->filtered;
 }
 
-
-/* Callback to copy (name, value) group into the "groups" section
-   of another configuration. */
-static svn_boolean_t
-authz_copy_group(const char *name, const char *value,
-                 void *baton, apr_pool_t *pool)
+/* In AUTHZ's user rules, construct the actual filtered tree.
+ * Use SCRATCH_POOL for temporary allocations.
+ */
+static svn_error_t *
+filter_tree(svn_authz_t *authz,
+            apr_pool_t *scratch_pool)
 {
-  svn_config_t *authz_cfg = baton;
+  apr_pool_t *pool = authz->filtered->pool;
+  const char *repos_name = authz->filtered->repository;
+  const char *user = authz->filtered->user;
+  node_t *root;
 
-  svn_config_set(authz_cfg, SVN_CONFIG_SECTION_GROUPS, name, value);
+  if (filtered_pool)
+    {
+      svn_membuf_t *key = construct_filtered_key(repos_name, user,
+                                                 authz->authz_id,
+                                                 scratch_pool);
 
-  return TRUE;
-}
+      /* Cache lookup. */
+      SVN_ERR(svn_object_pool__lookup((void **)&root, filtered_pool, key,
+                                      pool));
 
-/* Copy group definitions from GROUPS_CFG to the resulting AUTHZ.
- * If AUTHZ already contains any group definition, report an error.
- * Use POOL for temporary allocations. */
-static svn_error_t *
-authz_copy_groups(svn_authz_t *authz, svn_config_t *groups_cfg,
-                  apr_pool_t *pool)
-{
-  /* Easy out: we prohibit local groups in the authz file when global
-     groups are being used. */
-  if (svn_config_has_section(authz->cfg, SVN_CONFIG_SECTION_GROUPS))
+      if (!root)
+        {
+          apr_pool_t *item_pool = svn_object_pool__new_item_pool(authz_pool);
+          authz_full_t *add_ref = NULL;
+
+          /* Make sure the underlying full authz object lives as long as the
+           * filtered one that we are about to create.  We do this by adding
+           * a reference to it in ITEM_POOL (which may live longer than AUTHZ).
+           *
+           * Note that we already have a reference to that full authz in
+           * AUTHZ->FULL. Assert that we actually don't created multiple
+           * instances of the same full model.
+           */
+          svn_error_clear(svn_object_pool__lookup((void **)&add_ref,
+                                                  authz_pool, authz->authz_id,
+                                                  item_pool));
+          SVN_ERR_ASSERT(add_ref == authz->full);
+
+          /* Now construct the new filtered tree and cache it. */
+          root = create_user_authz(authz->full, repos_name, user, item_pool,
+                                   scratch_pool);
+          svn_error_clear(svn_object_pool__insert((void **)&root,
+                                                  filtered_pool, key, root,
+                                                  item_pool, pool));
+        }
+     }
+  else
     {
-      return svn_error_create(SVN_ERR_AUTHZ_INVALID_CONFIG, NULL,
-                              "Authz file cannot contain any groups "
-                              "when global groups are being used.");
+      root = create_user_authz(authz->full, repos_name, user, pool,
+                               scratch_pool);
     }
 
-  svn_config_enumerate2(groups_cfg, SVN_CONFIG_SECTION_GROUPS,
-                        authz_copy_group, authz->cfg, pool);
+  /* Write a new entry. */
+  authz->filtered->root = root;
 
   return SVN_NO_ERROR;
 }
 
-svn_error_t *
-svn_repos__authz_read(svn_authz_t **authz_p, const char *path,
-                      const char *groups_path, svn_boolean_t must_exist,
-                      svn_boolean_t accept_urls, apr_pool_t *pool)
+
+
+/* Read authz configuration data from PATH into *AUTHZ_P, allocated in
+   RESULT_POOL.  Return the cache key in *AUTHZ_ID.  If GROUPS_PATH is set,
+   use the global groups parsed from it.  Use SCRATCH_POOL for temporary
+   allocations.
+
+   PATH and GROUPS_PATH may be a dirent or an absolute file url.  REPOS_HINT
+   may be specified to speed up access to in-repo authz files.
+
+   If PATH or GROUPS_PATH is not a valid authz rule file, then return
+   SVN_AUTHZ_INVALID_CONFIG.  The contents of *AUTHZ_P is then
+   undefined.  If MUST_EXIST is TRUE, a missing authz or global groups file
+   is also an error. */
+static svn_error_t *
+authz_read(authz_full_t **authz_p,
+           svn_membuf_t **authz_id,
+           const char *path,
+           const char *groups_path,
+           svn_boolean_t must_exist,
+           svn_repos_t *repos_hint,
+           apr_pool_t *result_pool,
+           apr_pool_t *scratch_pool)
 {
-  svn_authz_t *authz = apr_palloc(pool, sizeof(*authz));
+  svn_error_t* err = NULL;
+  svn_stream_t *rules_stream = NULL;
+  svn_stream_t *groups_stream = NULL;
+  svn_checksum_t *rules_checksum = NULL;
+  svn_checksum_t *groups_checksum = NULL;
 
-  /* Load the authz file */
-  if (accept_urls)
-    SVN_ERR(svn_repos__retrieve_config(&authz->cfg, path, must_exist, TRUE,
-                                       pool));
-  else
-    SVN_ERR(svn_config_read3(&authz->cfg, path, must_exist, TRUE, TRUE,
-                             pool));
+  config_access_t *config_access =
+    svn_repos__create_config_access(repos_hint, scratch_pool);
 
+  /* Open the main authz file */
+  SVN_ERR(svn_repos__get_config(&rules_stream, &rules_checksum, config_access,
+                                path, must_exist, scratch_pool));
+
+  /* Open the optional groups file */
   if (groups_path)
+    SVN_ERR(svn_repos__get_config(&groups_stream, &groups_checksum,
+                                  config_access, groups_path, must_exist,
+                                  scratch_pool));
+
+  /* The authz cache is optional. */
+  *authz_id = construct_authz_key(rules_checksum, groups_checksum,
+                                  result_pool);
+  if (authz_pool)
     {
-      svn_config_t *groups_cfg;
-      svn_error_t *err;
+      /* Cache lookup. */
+      SVN_ERR(svn_object_pool__lookup((void **)authz_p, authz_pool,
+                                      *authz_id, result_pool));
 
-      /* Load the groups file */
-      if (accept_urls)
-        SVN_ERR(svn_repos__retrieve_config(&groups_cfg, groups_path,
-                                           must_exist, TRUE, pool));
-      else
-        SVN_ERR(svn_config_read3(&groups_cfg, groups_path, must_exist,
-                                 TRUE, TRUE, pool));
-
-      /* Copy the groups from groups_cfg into authz. */
-      err = authz_copy_groups(authz, groups_cfg, pool);
-
-      /* Add the paths to the error stack since the authz_copy_groups
-         routine knows nothing about them. */
-      if (err != SVN_NO_ERROR)
-        return svn_error_createf(err->apr_err, err,
-                                 "Error reading authz file '%s' with "
-                                 "groups file '%s':", path, groups_path);
+      /* If not found, parse and add to cache. */
+      if (!*authz_p)
+        {
+          apr_pool_t *item_pool = svn_object_pool__new_item_pool(authz_pool);
+
+          /* Parse the configuration(s) and construct the full authz model
+           * from it. */
+          err = svn_authz__parse(authz_p, rules_stream, groups_stream,
+                                item_pool, scratch_pool);
+          if (err != SVN_NO_ERROR)
+            {
+              /* That pool would otherwise never get destroyed. */
+              svn_pool_destroy(item_pool);
+
+              /* Add the URL / file name to the error stack since the parser
+               * doesn't have it. */
+              err = svn_error_quick_wrapf(err,
+                                   "Error while parsing config file: '%s':",
+                                   path);
+            }
+          else
+            {
+              SVN_ERR(svn_object_pool__insert((void **)authz_p, authz_pool,
+                                              *authz_id, *authz_p,
+                                              item_pool, result_pool));
+            }
+        }
+    }
+  else
+    {
+      /* Parse the configuration(s) and construct the full authz model from
+       * it. */
+      err = svn_error_quick_wrapf(svn_authz__parse(authz_p, rules_stream,
+                                                   groups_stream,
+                                                   result_pool, scratch_pool),
+                                  "Error while parsing authz file: '%s':",
+                                  path);
     }
 
-  /* Make sure there are no errors in the configuration. */
-  SVN_ERR(svn_repos__authz_validate(authz, pool));
+  svn_repos__destroy_config_access(config_access);
 
-  *authz_p = authz;
-  return SVN_NO_ERROR;
+  return err;
 }
 
 
@@ -981,12 +1628,22 @@ svn_repos__authz_read(svn_authz_t **authz_p, const char *path,
 /*** Public functions. ***/
 
 svn_error_t *
-svn_repos_authz_read2(svn_authz_t **authz_p, const char *path,
-                      const char *groups_path, svn_boolean_t must_exist,
-                      apr_pool_t *pool)
+svn_repos_authz_read3(svn_authz_t **authz_p,
+                      const char *path,
+                      const char *groups_path,
+                      svn_boolean_t must_exist,
+                      svn_repos_t *repos_hint,
+                      apr_pool_t *result_pool,
+                      apr_pool_t *scratch_pool)
 {
-  return svn_repos__authz_read(authz_p, path, groups_path, must_exist,
-                               TRUE, pool);
+  svn_authz_t *authz = apr_pcalloc(result_pool, sizeof(*authz));
+  authz->pool = result_pool;
+
+  SVN_ERR(authz_read(&authz->full, &authz->authz_id, path, groups_path,
+                     must_exist, repos_hint, result_pool, scratch_pool));
+
+  *authz_p = authz;
+  return SVN_NO_ERROR;
 }
 
 
@@ -994,29 +1651,20 @@ svn_error_t *
 svn_repos_authz_parse(svn_authz_t **authz_p, svn_stream_t *stream,
                       svn_stream_t *groups_stream, apr_pool_t *pool)
 {
-  svn_authz_t *authz = apr_palloc(pool, sizeof(*authz));
-
-  /* Parse the authz stream */
-  SVN_ERR(svn_config_parse(&authz->cfg, stream, TRUE, TRUE, pool));
-
-  if (groups_stream)
-    {
-      svn_config_t *groups_cfg;
-
-      /* Parse the groups stream */
-      SVN_ERR(svn_config_parse(&groups_cfg, groups_stream, TRUE, TRUE, pool));
+  apr_pool_t *scratch_pool = svn_pool_create(pool);
+  svn_authz_t *authz = apr_pcalloc(pool, sizeof(*authz));
+  authz->pool = pool;
 
-      SVN_ERR(authz_copy_groups(authz, groups_cfg, pool));
-    }
+  /* Parse the configuration and construct the full authz model from it. */
+  SVN_ERR(svn_authz__parse(&authz->full, stream, groups_stream, pool,
+                           scratch_pool));
 
-  /* Make sure there are no errors in the configuration. */
-  SVN_ERR(svn_repos__authz_validate(authz, pool));
+  svn_pool_destroy(scratch_pool);
 
   *authz_p = authz;
   return SVN_NO_ERROR;
 }
 
-
 svn_error_t *
 svn_repos_authz_check_access(svn_authz_t *authz, const char *repos_name,
                              const char *path, const char *user,
@@ -1024,51 +1672,58 @@ svn_repos_authz_check_access(svn_authz_t *authz, const char *repos_name,
                              svn_boolean_t *access_granted,
                              apr_pool_t *pool)
 {
-  const char *current_path;
+  const authz_access_t required =
+    ((required_access & svn_authz_read ? authz_access_read_flag : 0)
+     | (required_access & svn_authz_write ? authz_access_write_flag : 0));
+
+  /* Pick or create the suitable pre-filtered path rule tree. */
+  authz_user_rules_t *rules = get_user_rules(
+      authz,
+      (repos_name ? repos_name : AUTHZ_ANY_REPOSITORY),
+      user);
+
+  /* In many scenarios, users have uniform access to a repository
+   * (blanket access or no access at all).
+   *
+   * In these cases, don't bother creating or consulting the filtered tree.
+   */
+  if ((rules->global_rights.min_access & required) == required)
+    {
+      *access_granted = TRUE;
+      return SVN_NO_ERROR;
+    }
 
-  if (!repos_name)
-    repos_name = "";
+  if ((rules->global_rights.max_access & required) != required)
+    {
+      *access_granted = FALSE;
+      return SVN_NO_ERROR;
+    }
 
-  /* If PATH is NULL, check if the user has *any* access. */
+  /* No specific path given, i.e. looking for anywhere in the tree? */
   if (!path)
     {
-      *access_granted = authz_get_any_access(authz->cfg, repos_name,
-                                             user, required_access, pool);
+      *access_granted =
+        ((rules->global_rights.max_access & required) == required);
       return SVN_NO_ERROR;
     }
 
-  /* Sanity check. */
-  SVN_ERR_ASSERT(path[0] == '/');
+  /* Rules tree lookup */
 
-  /* Determine the granted access for the requested path. */
-  path = svn_fspath__canonicalize(path, pool);
-  current_path = path;
+  /* Did we already filter the data model? */
+  if (!rules->root)
+    SVN_ERR(filter_tree(authz, pool));
 
-  while (!authz_get_path_access(authz->cfg, repos_name,
-                                current_path, user,
-                                required_access,
-                                access_granted,
-                                pool))
-    {
-      /* Stop if the loop hits the repository root with no
-         results. */
-      if (current_path[0] == '/' && current_path[1] == '\0')
-        {
-          /* Deny access by default. */
-          *access_granted = FALSE;
-          return SVN_NO_ERROR;
-        }
+  /* Re-use previous lookup results, if possible. */
+  path = init_lockup_state(authz->filtered->lookup_state,
+                           authz->filtered->root, path);
 
-      /* Work back to the parent path. */
-      current_path = svn_fspath__dirname(current_path, pool);
-    }
+  /* Sanity check. */
+  SVN_ERR_ASSERT(path[0] == '/');
 
-  /* If the caller requested recursive access, we need to walk through
-     the entire authz config to see whether any child paths are denied
-     to the requested user. */
-  if (*access_granted && (required_access & svn_authz_recursive))
-    *access_granted = authz_get_tree_access(authz->cfg, repos_name, path,
-                                            user, required_access, pool);
+  /* Determine the granted access for the requested path.
+   * PATH does not need to be normalized for lockup(). */
+  *access_granted = lookup(rules->lookup_state, path, required,
+                           !!(required_access & svn_authz_recursive), pool);
 
   return SVN_NO_ERROR;
 }