/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.ranger.plugin.policyengine;


import org.apache.commons.collections.CollectionUtils;
import org.apache.commons.lang.StringUtils;
import org.apache.hadoop.conf.Configuration;
import org.apache.ranger.plugin.model.RangerPolicy.RangerPolicyResource;
import org.apache.ranger.plugin.model.RangerServiceDef.RangerResourceDef;
import org.apache.ranger.plugin.policyengine.RangerAccessRequest.ResourceElementMatchingScope;
import org.apache.ranger.plugin.policyevaluator.RangerPolicyEvaluator;
import org.apache.ranger.plugin.policyresourcematcher.RangerResourceEvaluator;
import org.apache.ranger.plugin.resourcematcher.RangerAbstractResourceMatcher;
import org.apache.ranger.plugin.resourcematcher.RangerResourceMatcher;
import org.apache.ranger.plugin.util.RangerPerfTracer;
import org.apache.ranger.plugin.util.RangerRequestExprResolver;
import org.apache.ranger.plugin.util.ServiceDefUtil;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

import static org.apache.ranger.plugin.resourcematcher.RangerPathResourceMatcher.DEFAULT_PATH_SEPARATOR_CHAR;
import static org.apache.ranger.plugin.resourcematcher.RangerPathResourceMatcher.OPTION_PATH_SEPARATOR;

public class RangerResourceTrie<T extends RangerResourceEvaluator> {
    private static final Logger LOG                = LoggerFactory.getLogger(RangerResourceTrie.class);
    private static final Logger TRACE_LOG          = RangerPerfTracer.getPerfLogger("resourcetrie.trace");
    private static final Logger PERF_TRIE_INIT_LOG = RangerPerfTracer.getPerfLogger("resourcetrie.init");
    private static final Logger PERF_TRIE_OP_LOG   = RangerPerfTracer.getPerfLogger("resourcetrie.op");

    private static final String DEFAULT_WILDCARD_CHARS    = "*?";
    private static final String TRIE_BUILDER_THREAD_COUNT = "ranger.policyengine.trie.builder.thread.count";

    private final RangerResourceDef resourceDef;
    private final boolean           optIgnoreCase;
    private final boolean           optWildcard;
    private final String            wildcardChars;
    private final boolean           isOptimizedForRetrieval;
    private final boolean           isOptimizedForSpace;
    private final Character         separatorChar;
    private       Set<T>            inheritedEvaluators;
    private final TrieNode<T>       root;

    public RangerResourceTrie(RangerResourceDef resourceDef, List<T> evaluators) {
        this(resourceDef, evaluators, true, null);
    }

    public RangerResourceTrie(RangerResourceTrie<T> other) {
        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.copyTrie(name=" + other.resourceDef.getName() + ")");
        }

        this.resourceDef             = other.resourceDef;
        this.optIgnoreCase           = other.optIgnoreCase;
        this.optWildcard             = other.optWildcard;
        this.wildcardChars           = other.wildcardChars;
        this.isOptimizedForSpace     = other.isOptimizedForSpace;
        this.isOptimizedForRetrieval = other.isOptimizedForRetrieval;
        this.separatorChar           = other.separatorChar;
        this.inheritedEvaluators     = other.inheritedEvaluators != null ? new HashSet<>(other.inheritedEvaluators) : null;
        this.root                    = copyTrieSubtree(other.root, null);

        wrapUpUpdate();

        if (!isOptimizedForRetrieval) {
            if (LOG.isDebugEnabled()) {
                LOG.debug("Trie for " + this.resourceDef.getName() + " is not optimized for retrieval. Resetting isSetup flag by calling undoSetup() on the root");
            }
            root.undoSetup();
        }

        RangerPerfTracer.logAlways(perf);

        if (PERF_TRIE_INIT_LOG.isDebugEnabled()) {
            PERF_TRIE_INIT_LOG.debug(toString());
        }

        if (TRACE_LOG.isTraceEnabled()) {
            TRACE_LOG.trace("Trie Dump from RangerResourceTrie.copyTrie(name=" + other.resourceDef.getName() + "):\n[" + dumpTrie() + "]");
        }
    }

    public RangerResourceTrie(RangerResourceDef resourceDef, List<T> evaluators, boolean isOptimizedForRetrieval, RangerPluginContext pluginContext) {
        this(resourceDef, evaluators, isOptimizedForRetrieval, false, pluginContext);
    }

    public <E> RangerResourceTrie(RangerResourceDef resourceDef, List<E> evaluators, boolean isOptimizedForRetrieval, boolean isOptimizedForSpace, RangerPluginContext pluginContext) {
        if(LOG.isDebugEnabled()) {
            LOG.debug("==> RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ", isOptimizedForRetrieval=" + isOptimizedForRetrieval + ", isOptimizedForSpace=" + isOptimizedForSpace + ")");
        }

        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.init(name=" + resourceDef.getName() + ")");
        }

        Configuration config             = pluginContext != null ? pluginContext.getConfig() : null;
        int           builderThreadCount = config != null ? config.getInt(TRIE_BUILDER_THREAD_COUNT, 1) : 1;

        if (builderThreadCount < 1) {
            builderThreadCount = 1;
        }

        if (TRACE_LOG.isTraceEnabled()) {
            TRACE_LOG.trace("builderThreadCount is set to [" + builderThreadCount + "]");
        }

        Map<String, String> matcherOptions           = resourceDef.getMatcherOptions();
        boolean             optReplaceTokens         = RangerAbstractResourceMatcher.getOptionReplaceTokens(matcherOptions);
        boolean             optReplaceReqExpressions = RangerAbstractResourceMatcher.getOptionReplaceReqExpressions(matcherOptions);
        String              tokenReplaceSpecialChars = "";

        if(optReplaceTokens) {
            char delimiterStart  = RangerAbstractResourceMatcher.getOptionDelimiterStart(matcherOptions);
            char delimiterEnd    = RangerAbstractResourceMatcher.getOptionDelimiterEnd(matcherOptions);
            char delimiterEscape = RangerAbstractResourceMatcher.getOptionDelimiterEscape(matcherOptions);

            tokenReplaceSpecialChars += delimiterStart;
            tokenReplaceSpecialChars += delimiterEnd;
            tokenReplaceSpecialChars += delimiterEscape;
        }

        if (optReplaceReqExpressions) {
            tokenReplaceSpecialChars += RangerRequestExprResolver.EXPRESSION_START.charAt(0);
        }

        this.resourceDef             = resourceDef;
        this.optIgnoreCase           = RangerAbstractResourceMatcher.getOptionIgnoreCase(matcherOptions);
        this.optWildcard             = RangerAbstractResourceMatcher.getOptionWildCard(matcherOptions);
        this.wildcardChars           = optWildcard ? DEFAULT_WILDCARD_CHARS + tokenReplaceSpecialChars : "" + tokenReplaceSpecialChars;
        this.isOptimizedForSpace     = isOptimizedForSpace;
        this.isOptimizedForRetrieval = !isOptimizedForSpace && isOptimizedForRetrieval;  // isOptimizedForSpace takes precedence
        this.separatorChar           = ServiceDefUtil.getCharOption(matcherOptions, OPTION_PATH_SEPARATOR, DEFAULT_PATH_SEPARATOR_CHAR);

        final TrieNode<T> tmpRoot = buildTrie(resourceDef, evaluators, builderThreadCount);

        if (builderThreadCount > 1 && tmpRoot == null) { // if multithreaded trie-creation failed, build using a single thread
            this.root = buildTrie(resourceDef, evaluators, 1);
        } else {
            this.root = tmpRoot;
        }

        wrapUpUpdate();

        RangerPerfTracer.logAlways(perf);

        if (PERF_TRIE_INIT_LOG.isDebugEnabled()) {
            PERF_TRIE_INIT_LOG.debug(toString());
        }

        if (TRACE_LOG.isTraceEnabled()) {
            TRACE_LOG.trace("Trie Dump from RangerResourceTrie.init(name=" + resourceDef.getName() + "):\n[" + dumpTrie() + "]");
        }

        if(LOG.isDebugEnabled()) {
            LOG.debug("<== RangerResourceTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ", isOptimizedForRetrieval=" + this.isOptimizedForRetrieval + ", isOptimizedForSpace=" + this.isOptimizedForSpace + "): " + this);
        }
    }

    public Set<T> getInheritedEvaluators() {
        return inheritedEvaluators;
    }

    public Set<T> getEvaluatorsForResource(Object resource) {
        return getEvaluatorsForResource(resource, ResourceElementMatchingScope.SELF);
    }

    @SuppressWarnings("unchecked")
    public Set<T> getEvaluatorsForResource(Object resource, ResourceElementMatchingScope scope) {
        if (resource instanceof String) {
            return getEvaluatorsForResource((String) resource, scope);
        } else if (resource instanceof Collection) {
            Collection<String> resources = (Collection<String>) resource;

            if (CollectionUtils.isEmpty(resources)) {  // treat empty collection same as empty-string
                return getEvaluatorsForResource("", scope);
            } else {
                return getEvaluatorsForResources(resources, scope);
            }
        }

        return null;
    }

    public void add(RangerPolicyResource resource, T evaluator) {
        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.add(name=" + resource + ")");
        }

        if (resource == null) {
            if (evaluator.isAncestorOf(resourceDef)) {
                addInheritedEvaluator(evaluator);
            }
        } else {
            if (resource.getIsExcludes()) {
                addInheritedEvaluator(evaluator);
            } else {
                if (CollectionUtils.isNotEmpty(resource.getValues())) {
                    for (String value : resource.getValues()) {
                        insert(root, value, resource.getIsRecursive(), evaluator);
                    }
                }
            }
        }

        RangerPerfTracer.logAlways(perf);

        if (TRACE_LOG.isTraceEnabled()) {
            TRACE_LOG.trace("Trie Dump from RangerResourceTrie.add(name=" + resource + "):\n[" + dumpTrie() + "]");
        }
    }

    public void delete(RangerPolicyResource resource, T evaluator) {
        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.delete(name=" + resource + ")");
        }

        if (resource == null) {
            if (evaluator.isAncestorOf(resourceDef)) {
                removeInheritedEvaluator(evaluator);
            }
        } else if (resource.getIsExcludes()) {
            removeInheritedEvaluator(evaluator);
        } else {
            for (String value : resource.getValues()) {
                TrieNode<T> node = getNodeForResource(value);
                if (node != null) {
                    node.removeEvaluatorFromSubtree(evaluator);
                }
            }
        }

        RangerPerfTracer.logAlways(perf);

        if (TRACE_LOG.isTraceEnabled()) {
            TRACE_LOG.trace("Trie Dump from RangerResourceTrie.delete(name=" + resource + "):\n[" + dumpTrie()+ "]");
        }
    }

    public void wrapUpUpdate() {
        if (root != null) {
            root.wrapUpUpdate();
            if (TRACE_LOG.isTraceEnabled()) {
                TRACE_LOG.trace("Trie Dump from RangerResourceTrie.wrapUpUpdate(name=" + resourceDef.getName() + "):\n[" + dumpTrie() + "]");
            }
        }
    }

    public StringBuilder dumpTrie() {
        StringBuilder sb = new StringBuilder();
        if (root != null) {
            root.toString("", sb);
        }
        return sb;
    }

    TrieNode<T> getRoot() {
        return root;
    }

    private void addInheritedEvaluator(T evaluator) {
        if (inheritedEvaluators == null) {
            inheritedEvaluators = new HashSet<>();
        }

        inheritedEvaluators.add(evaluator);
    }

    private void removeInheritedEvaluator(T evaluator) {
        if (CollectionUtils.isNotEmpty(inheritedEvaluators) && inheritedEvaluators.contains(evaluator)) {
            inheritedEvaluators.remove(evaluator);
            if (CollectionUtils.isEmpty(inheritedEvaluators)) {
                inheritedEvaluators = null;
            }
        }
    }

    private TrieNode<T> copyTrieSubtree(final TrieNode<T> source, final TrieNode<T> parent) {
        if (TRACE_LOG.isTraceEnabled()) {
            StringBuilder sb = new StringBuilder();
            source.toString(sb);
            TRACE_LOG.trace("==> copyTrieSubtree(" + sb + ")");
        }

        TrieNode<T> dest = new TrieNode<>(source.str);

        if (parent != null) {
            parent.addChild(dest);
        }

        synchronized (source.children) {
            dest.isSetup                           = source.isSetup;
            dest.isSharingParentWildcardEvaluators = source.isSharingParentWildcardEvaluators;

            if (source.isSharingParentWildcardEvaluators) {
                if (dest.getParent() != null) {
                    dest.wildcardEvaluators = dest.getParent().getWildcardEvaluators();
                } else {
                    dest.wildcardEvaluators = null;
                }
            } else {
                if (source.wildcardEvaluators != null) {
                    dest.wildcardEvaluators = new HashSet<>(source.wildcardEvaluators);
                } else {
                    dest.wildcardEvaluators = null;
                }
            }

            if (source.evaluators != null) {
                if (source.evaluators == source.wildcardEvaluators) {
                    dest.evaluators = dest.wildcardEvaluators;
                } else {
                    dest.evaluators = new HashSet<>(source.evaluators);
                }
            } else {
                dest.evaluators = null;
            }
        }

        Map<Character, TrieNode<T>> children = source.getChildren();

        for (Map.Entry<Character, TrieNode<T>> entry : children.entrySet()) {
            copyTrieSubtree(entry.getValue(), dest);
        }

        if (TRACE_LOG.isTraceEnabled()) {
            StringBuilder sourceAsString = new StringBuilder(), destAsString = new StringBuilder();
            source.toString(sourceAsString);
            dest.toString(destAsString);

            TRACE_LOG.trace("<== copyTrieSubtree(" + sourceAsString + ") : " + destAsString);
        }

        return dest;
    }

    private <E> TrieNode<T> buildTrie(RangerResourceDef resourceDef, List<E> evaluators, int builderThreadCount) {
        if(LOG.isDebugEnabled()) {
            LOG.debug("==> buildTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ", isMultiThreaded=" + (builderThreadCount > 1) + ")");
        }

        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.init(resourceDef=" + resourceDef.getName() + ")");
        }

        TrieNode<T>                           ret             = new TrieNode<>(null);
        final boolean                         isMultiThreaded = builderThreadCount > 1;
        final List<ResourceTrieBuilderThread> builderThreads;
        final Map<Character, Integer>         builderThreadMap;
        final String                          resourceName        = resourceDef.getName();
        int                                   lastUsedThreadIndex = 0;

        if (isMultiThreaded) {
            builderThreads = new ArrayList<>();

            for (int i = 0; i < builderThreadCount; i++) {
                ResourceTrieBuilderThread t = new ResourceTrieBuilderThread();

                t.setDaemon(true);
                builderThreads.add(t);
                t.start();
            }

            builderThreadMap = new HashMap<>();
        } else {
            builderThreads   = null;
            builderThreadMap = null;
        }

        for (E evaluator : evaluators) {
            final List<T> resourceEvaluators;

            if (evaluator instanceof RangerPolicyEvaluator) {
                resourceEvaluators = (List<T>) ((RangerPolicyEvaluator) evaluator).getResourceEvaluators();
            } else if (evaluator instanceof RangerResourceEvaluator) {
                resourceEvaluators = Collections.singletonList((T) evaluator);
            } else {
                LOG.error("buildTrie(): unexpected evaluator class " + evaluator.getClass().getCanonicalName());

                resourceEvaluators = Collections.emptyList();
            }

            for (T resourceEvaluator : resourceEvaluators) {
                Map<String, RangerPolicyResource> policyResources = resourceEvaluator.getPolicyResource();
                RangerPolicyResource              policyResource  = policyResources != null ? policyResources.get(resourceName) : null;

                if (policyResource == null) {
                    if (resourceEvaluator.isAncestorOf(resourceDef)) {
                        addInheritedEvaluator(resourceEvaluator);
                    }

                    continue;
                }

                if (policyResource.getIsExcludes()) {
                    addInheritedEvaluator(resourceEvaluator);
                } else {
                    RangerResourceMatcher resourceMatcher = resourceEvaluator.getResourceMatcher(resourceName);

                    if (resourceMatcher != null && (resourceMatcher.isMatchAny())) {
                        ret.addWildcardEvaluator(resourceEvaluator);
                    } else {
                        if (CollectionUtils.isNotEmpty(policyResource.getValues())) {
                            for (String resource : policyResource.getValues()) {
                                if (!isMultiThreaded) {
                                    insert(ret, resource, policyResource.getIsRecursive(), resourceEvaluator);
                                } else {
                                    try {
                                        lastUsedThreadIndex = insert(ret, resource, policyResource.getIsRecursive(), resourceEvaluator, builderThreadMap, builderThreads, lastUsedThreadIndex);
                                    } catch (InterruptedException ex) {
                                        LOG.error("Failed to dispatch " + resource + " to " + builderThreads.get(lastUsedThreadIndex));
                                        LOG.error("Failing and retrying with one thread");

                                        ret = null;

                                        break;
                                    }
                                }
                            }

                            if (ret == null) {
                                break;
                            }
                        }
                    }
                }
            }
            if (ret == null) {
                break;
            }
        }

        if (ret != null) {
            if (isMultiThreaded) {
                for (ResourceTrieBuilderThread t : builderThreads) {
                    try {
                        // Send termination signal to each thread
                        t.add("", false, null);
                        // Wait for threads to finish work
                        t.join();
                        ret.getChildren().putAll(t.getSubtrees());
                    } catch (InterruptedException ex) {
                        LOG.error("BuilderThread " + t + " was interrupted:", ex);
                        LOG.error("Failing and retrying with one thread");

                        ret = null;

                        break;
                    }
                }

                cleanUpThreads(builderThreads);
            }
        }

        RangerPerfTracer.logAlways(perf);

        if(LOG.isDebugEnabled()) {
            LOG.debug("<== buildTrie(" + resourceDef.getName() + ", evaluatorCount=" + evaluators.size() + ", isMultiThreaded=" + isMultiThreaded + ") :" +  ret);
        }

        return ret;
    }

    private void cleanUpThreads(List<ResourceTrieBuilderThread> builderThreads) {
        if (CollectionUtils.isNotEmpty(builderThreads)) {
            for (ResourceTrieBuilderThread t : builderThreads) {
                try {
                    if (t.isAlive()) {
                        t.interrupt();
                        t.join();
                    }
                } catch (InterruptedException ex) {
                    LOG.error("Could not terminate thread " + t);
                }
            }
        }
    }

    private TrieData getTrieData() {
        TrieData ret = new TrieData();

        root.populateTrieData(ret);

        ret.maxDepth = getMaxDepth();

        return ret;
    }

    private int getMaxDepth() {
        return root.getMaxDepth();
    }

    private Character getLookupChar(char ch) {
        return optIgnoreCase ? Character.toLowerCase(ch) : ch;
    }

    private Character getLookupChar(String str, int index) {
        return getLookupChar(str.charAt(index));
    }

    private int insert(TrieNode<T> currentRoot, String resource, boolean isRecursive, T evaluator, Map<Character, Integer> builderThreadMap, List<ResourceTrieBuilderThread> builderThreads, int lastUsedThreadIndex) throws InterruptedException {
        int          ret    = lastUsedThreadIndex;
        final String prefix = getNonWildcardPrefix(resource);

        if (StringUtils.isNotEmpty(prefix)) {
            char    c     = getLookupChar(prefix.charAt(0));
            Integer index = builderThreadMap.get(c);

            if (index == null) {
                ret = index = (lastUsedThreadIndex + 1) % builderThreads.size();
                builderThreadMap.put(c, index);
            }

            builderThreads.get(index).add(resource, isRecursive, evaluator);
        } else {
            currentRoot.addWildcardEvaluator(evaluator);
        }

        return ret;
    }

    private void insert(TrieNode<T> currentRoot, String resource, boolean isRecursive, T evaluator) {
        TrieNode<T>   curr       = currentRoot;
        final String  prefix     = getNonWildcardPrefix(resource);
        final boolean isWildcard = prefix.length() != resource.length();

        if (StringUtils.isNotEmpty(prefix)) {
            curr = curr.getOrCreateChild(prefix);
        }

        if(isWildcard || isRecursive) {
            curr.addWildcardEvaluator(evaluator);
        } else {
            curr.addEvaluator(evaluator);
        }

    }

    private int getNonWildcardPrefixLength(String str) {
        int minIndex = str.length();

        for (int i = 0; i < wildcardChars.length(); i++) {
            int index = str.indexOf(wildcardChars.charAt(i));

            if (index != -1 && index < minIndex) {
                minIndex = index;
            }
        }

        return minIndex;
    }

    private String getNonWildcardPrefix(String str) {
        int prefixLen = getNonWildcardPrefixLength(str);

        return (prefixLen < str.length()) ? str.substring(0, prefixLen) : str;
    }


    private Set<T> getEvaluatorsForResource(String resource, ResourceElementMatchingScope scope) {
        if(LOG.isDebugEnabled()) {
            LOG.debug("==> RangerResourceTrie.getEvaluatorsForResource(" + resource + ", " + scope + ")");
        }

        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerResourceTrie.getEvaluatorsForResource(resource=" + resource + ")");
        }

        TrieNode<T> curr   = root;
        TrieNode<T> parent = null;
        TrieNode<T> child  = null;
        final int   len    = resource.length();
        int         i      = 0;

        Set<T>      accumulatedEvaluators = new HashSet<>();

        while (i < len) {
            if (!isOptimizedForSpace) {
                curr.setupIfNeeded(parent);
            } else {
                if (curr.getWildcardEvaluators() != null) {
                    accumulatedEvaluators.addAll(curr.getWildcardEvaluators());
                }
            }

            child = curr.getChild(getLookupChar(resource, i));

            if (child == null) {
                break;
            }

            final String childStr = child.getStr();

            if (!resource.regionMatches(optIgnoreCase, i, childStr, 0, childStr.length())) {
                break;
            }

            parent = curr;
            curr   = child;
            i      += childStr.length();
        }

        if (!isOptimizedForSpace) {
            curr.setupIfNeeded(parent);
        } else {
            if (curr.getWildcardEvaluators() != null) {
                accumulatedEvaluators.addAll(curr.getWildcardEvaluators());
            }
        }

        boolean isSelfMatch = (i == len);
        Set<T>  ret;

        if (!isOptimizedForSpace) {
            ret = isSelfMatch ? curr.getEvaluators() : curr.getWildcardEvaluators();
        } else {
            if (isSelfMatch) {
                if (curr.getEvaluators() != null) {
                    accumulatedEvaluators.addAll(curr.getEvaluators());
                }
            }
            ret = accumulatedEvaluators;
        }

        final boolean includeChildEvaluators = scope == ResourceElementMatchingScope.SELF_OR_CHILD || scope == ResourceElementMatchingScope.SELF_OR_PREFIX;
        final Set<T>  childEvaluators        = includeChildEvaluators ? new HashSet<>() : null;

        if (scope == ResourceElementMatchingScope.SELF_OR_CHILD) {
            final boolean resourceEndsWithSep = resource.charAt(resource.length() - 1) == separatorChar;

            if (isSelfMatch) { // resource == path(curr)
                if (resourceEndsWithSep) { // ex: resource=/tmp/
                    curr.getChildren().values().stream().forEach(c -> c.collectChildEvaluators(separatorChar, 0, childEvaluators));
                } else { // ex: resource=/tmp
                    curr = curr.getChild(separatorChar);

                    if (curr != null) {
                        curr.collectChildEvaluators(separatorChar, 1, childEvaluators);
                    }
                }
            } else if (child != null) { // resource != path(child) ex: (resource=/tmp, path(child)=/tmp/test.txt or path(child)=/tmpdir)
                int     remainingLen  = len - i;
                boolean isPrefixMatch = child.getStr().regionMatches(optIgnoreCase, 0, resource, i, remainingLen);

                if (isPrefixMatch) {
                    if (resourceEndsWithSep) { // ex: resource=/tmp/
                        child.collectChildEvaluators(separatorChar, remainingLen, childEvaluators);
                    } else if (child.getStr().charAt(remainingLen) == separatorChar) { //  ex: resource=/tmp
                        child.collectChildEvaluators(separatorChar, remainingLen + 1, childEvaluators);
                    }
                }
            }
        } else if (scope == ResourceElementMatchingScope.SELF_OR_PREFIX) {
            curr.collectChildEvaluators(resource, i, childEvaluators);
        }

        if (CollectionUtils.isNotEmpty(childEvaluators)) {
            if (CollectionUtils.isNotEmpty(ret)) {
                childEvaluators.addAll(ret);
            }

            ret = childEvaluators;
        }

        RangerPerfTracer.logAlways(perf);

        if(LOG.isDebugEnabled()) {
            LOG.debug("<== RangerResourceTrie.getEvaluatorsForResource(" + resource + ", " + scope + "): evaluators=" + (ret == null ? null : Arrays.deepToString(ret.toArray())));
        }

        return ret;
    }

    private TrieNode<T> getNodeForResource(String resource) {
        if(LOG.isDebugEnabled()) {
            LOG.debug("==> RangerResourceTrie.getNodeForResource(" + resource + ")");
        }

        RangerPerfTracer perf = null;

        if(RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_OP_LOG)) {
            perf = RangerPerfTracer.getPerfTracer(PERF_TRIE_OP_LOG, "RangerResourceTrie.getNodeForResource(resource=" + resource + ")");
        }

        TrieNode<T> curr = root;
        final int   len  = getNonWildcardPrefixLength(resource);
        int         i    = 0;

        while (i < len) {
            final TrieNode<T> child = curr.getChild(getLookupChar(resource, i));

            if (child == null) {
                break;
            }

            final String childStr = child.getStr();

            if (!resource.regionMatches(optIgnoreCase, i, childStr, 0, childStr.length())) {
                break;
            }

            curr = child;
            i    += childStr.length();
        }

        curr = (i == len) ? curr : null;

        RangerPerfTracer.logAlways(perf);

        if(LOG.isDebugEnabled()) {
            LOG.debug("<== RangerResourceTrie.getNodeForResource(" + resource + ")");
        }

        return curr;
    }

    private Set<T> getEvaluatorsForResources(Collection<String> resources, ResourceElementMatchingScope scope) {
        if(LOG.isDebugEnabled()) {
            LOG.debug("==> RangerResourceTrie.getEvaluatorsForResources(" + resources + ")");
        }

        Set<T>       ret           = null;
        Map<Long, T> evaluatorsMap = null;

        for (String resource : resources) {
            Set<T> resourceEvaluators = getEvaluatorsForResource(resource, scope);

            if (CollectionUtils.isEmpty(resourceEvaluators)) {
                continue;
            }

            if (evaluatorsMap == null) {
                if (ret == null) { // first resource: don't create map yet
                    ret = resourceEvaluators;
                } else if (ret != resourceEvaluators) { // if evaluator list is same as earlier resources, retain the list, else create a map
                    evaluatorsMap = new HashMap<>();

                    for (T evaluator : ret) {
                        evaluatorsMap.put(evaluator.getId(), evaluator);
                    }

                    ret = null;
                }
            }

            if (evaluatorsMap != null) {
                for (T evaluator : resourceEvaluators) {
                    evaluatorsMap.put(evaluator.getId(), evaluator);
                }
            }
        }

        if (ret == null && evaluatorsMap != null) {
            ret = new HashSet<>(evaluatorsMap.values());
        }

        if(LOG.isDebugEnabled()) {
            LOG.debug("<== RangerResourceTrie.getEvaluatorsForResources(" + resources + "): evaluatorCount=" + (ret == null ? 0 : ret.size()));
        }

        return ret;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        TrieData trieData = getTrieData();

        sb.append("resourceName=").append(resourceDef.getName());
        sb.append("; optIgnoreCase=").append(optIgnoreCase);
        sb.append("; optWildcard=").append(optWildcard);
        sb.append("; wildcardChars=").append(wildcardChars);
        sb.append("; nodeCount=").append(trieData.nodeCount);
        sb.append("; leafNodeCount=").append(trieData.leafNodeCount);
        sb.append("; singleChildNodeCount=").append(trieData.singleChildNodeCount);
        sb.append("; maxDepth=").append(trieData.maxDepth);
        sb.append("; evaluatorListCount=").append(trieData.evaluatorListCount);
        sb.append("; wildcardEvaluatorListCount=").append(trieData.wildcardEvaluatorListCount);
        sb.append("; evaluatorListRefCount=").append(trieData.evaluatorListRefCount);
        sb.append("; wildcardEvaluatorListRefCount=").append(trieData.wildcardEvaluatorListRefCount);

        return sb.toString();
    }

    class ResourceTrieBuilderThread extends Thread {

        class WorkItem {
            final String  resourceName;
            final boolean isRecursive;
            final T       evaluator;

            WorkItem(String resourceName, boolean isRecursive, T evaluator) {
                this.resourceName = resourceName;
                this.isRecursive  = isRecursive;
                this.evaluator    = evaluator;
            }

            @Override
            public String toString() {
                return
                "resourceName=" + resourceName +
                "isRecursive=" + isRecursive +
                "evaluator=" + (evaluator != null? evaluator.getId() : null);
            }
        }

        private final TrieNode<T>             thisRoot  = new TrieNode<>(null);
        private final BlockingQueue<WorkItem> workQueue = new LinkedBlockingQueue<>();

        ResourceTrieBuilderThread() {
        }

        void add(String resourceName, boolean isRecursive, T evaluator) throws InterruptedException {
            workQueue.put(new WorkItem(resourceName, isRecursive, evaluator));
        }

        Map<Character, TrieNode<T>> getSubtrees() { return thisRoot.getChildren(); }

        @Override
        public void run() {
            if (LOG.isDebugEnabled()) {
                LOG.debug("Running " + this);
            }

            while (true) {
                final WorkItem workItem;

                try {
                    workItem = workQueue.take();
                } catch (InterruptedException exception) {
                    LOG.error("Thread=" + this + " is interrupted", exception);

                    break;
                }

                if (workItem.evaluator != null) {
                    insert(thisRoot, workItem.resourceName, workItem.isRecursive, workItem.evaluator);
                } else {
                    if (LOG.isDebugEnabled()) {
                        LOG.debug("Received termination signal. " + workItem);
                    }

                    break;
                }
            }

            if (LOG.isDebugEnabled()) {
                LOG.debug("Exiting " + this);
            }
        }
    }

    static class TrieData {
        int nodeCount;
        int leafNodeCount;
        int singleChildNodeCount;
        int maxDepth;
        int evaluatorListCount;
        int wildcardEvaluatorListCount;
        int evaluatorListRefCount;
        int wildcardEvaluatorListRefCount;
    }

    class TrieNode<U extends T> {
        private          String                      str;
        private          TrieNode<U>                 parent;
        private final    Map<Character, TrieNode<U>> children = new HashMap<>();
        private volatile Set<U>                      evaluators;
        private volatile Set<U>                      wildcardEvaluators;
        private          boolean                     isSharingParentWildcardEvaluators;
        private volatile boolean                     isSetup = false;

        TrieNode(String str) {
            this.str = str;
        }

        String getStr() {
            return str;
        }

        void setStr(String str) {
            this.str = str;
        }

        TrieNode<U> getParent() {
            return parent;
        }

        void setParent(TrieNode<U> parent) {
            this.parent = parent;
        }

        Map<Character, TrieNode<U>> getChildren() {
            return children;
        }

        Set<U> getEvaluators() {
            return evaluators;
        }

        Set<U> getWildcardEvaluators() {
            return wildcardEvaluators;
        }

        TrieNode<U> getChild(Character ch) {
            return children.get(ch);
        }

        void populateTrieData(RangerResourceTrie.TrieData trieData) {
            trieData.nodeCount++;

            if (wildcardEvaluators != null) {
                if (isSharingParentWildcardEvaluators) {
                    trieData.wildcardEvaluatorListRefCount++;
                } else {
                    trieData.wildcardEvaluatorListCount++;
                }
            }

            if (evaluators != null) {
                if (evaluators == wildcardEvaluators) {
                    trieData.evaluatorListRefCount++;
                } else {
                    trieData.evaluatorListCount++;
                }
            }

            if (!children.isEmpty()) {
                if (children.size() == 1) {
                    trieData.singleChildNodeCount++;
                }

                for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) {
                    TrieNode<U> child = entry.getValue();

                    child.populateTrieData(trieData);
                }
            } else {
                trieData.leafNodeCount++;
            }
        }

        int getMaxDepth() {
            int ret = 0;

            for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) {
                TrieNode<U> child = entry.getValue();

                int maxChildDepth = child.getMaxDepth();

                if (maxChildDepth > ret) {
                    ret = maxChildDepth;
                }
            }

            return ret + 1;
        }

        TrieNode<U> getOrCreateChild(String str) {
            int         len   = str.length();
            TrieNode<U> child = children.get(getLookupChar(str, 0));

            if (child == null) {
                child = new TrieNode<>(str);

                addChild(child);
            } else {
                final String  childStr     = child.getStr();
                final int     childStrLen  = childStr.length();
                final boolean isExactMatch = optIgnoreCase ? StringUtils.equalsIgnoreCase(childStr, str) : StringUtils.equals(childStr, str);

                if (!isExactMatch) {
                    final int numOfCharactersToMatch = Math.min(childStrLen, len);
                    int       index                  = 1;

                    for (; index < numOfCharactersToMatch; index++) {
                        if (getLookupChar(childStr, index) != getLookupChar(str, index)) {
                            break;
                        }
                    }

                    if (index == numOfCharactersToMatch) {
                        // Matched all
                        if (childStrLen > len) {
                            // Existing node has longer string, need to break up this node
                            TrieNode<U> newChild = new TrieNode<>(str);

                            this.addChild(newChild);
                            child.setStr(childStr.substring(index));
                            newChild.addChild(child);

                            child = newChild;
                        } else {
                            // This is a longer string, build a child with leftover string
                            child = child.getOrCreateChild(str.substring(index));
                        }
                    } else {
                        // Partial match for both; both have leftovers
                        String      matchedPart = str.substring(0, index);
                        TrieNode<U> newChild    = new TrieNode<>(matchedPart);

                        this.addChild(newChild);
                        child.setStr(childStr.substring(index));
                        newChild.addChild(child);

                        child = newChild.getOrCreateChild(str.substring(index));
                    }
                }
            }

            return child;
        }

        private void addChild(TrieNode<U> child) {
            children.put(getLookupChar(child.getStr(), 0), child);
            child.setParent(this);
        }

        void addEvaluator(U evaluator) {
            if (evaluators == null) {
                evaluators = new HashSet<>();
            }

            evaluators.add(evaluator);
        }

        void addWildcardEvaluator(U evaluator) {
            if (wildcardEvaluators == null) {
                wildcardEvaluators = new HashSet<>();
            }

            wildcardEvaluators.add(evaluator);
        }

        void removeEvaluator(U evaluator) {
            if (CollectionUtils.isNotEmpty(evaluators)) {
                evaluators.remove(evaluator);

                if (CollectionUtils.isEmpty(evaluators)) {
                    evaluators = null;
                }
            }
        }

        void removeWildcardEvaluator(U evaluator) {
            if (CollectionUtils.isNotEmpty(wildcardEvaluators)) {
                wildcardEvaluators.remove(evaluator);

                if (CollectionUtils.isEmpty(wildcardEvaluators)) {
                    wildcardEvaluators = null;
                }
            }
        }

        void undoSetup() {
            for (TrieNode<U> child : children.values()) {
                child.undoSetup();
            }

            if (isSetup) {
                if (evaluators != null) {
                    if (evaluators == wildcardEvaluators) {
                        evaluators = null;
                    } else {
                        if (wildcardEvaluators != null) {
                            evaluators.removeAll(wildcardEvaluators);

                            if (CollectionUtils.isEmpty(evaluators)) {
                                evaluators = null;
                            }
                        }
                    }
                }

                if (wildcardEvaluators != null) {
                    if (isSharingParentWildcardEvaluators) {
                        wildcardEvaluators = null;
                    } else {
                        Set<U> parentWildcardEvaluators = getParent() == null ? null : getParent().getWildcardEvaluators();

                        if (parentWildcardEvaluators != null) {
                            wildcardEvaluators.removeAll(parentWildcardEvaluators);

                            if (CollectionUtils.isEmpty(wildcardEvaluators)) {
                                wildcardEvaluators = null;
                            }
                        }
                    }
                }

                isSharingParentWildcardEvaluators = false;
                isSetup                           = false;
            }
        }

        void removeSelfFromTrie() {
            if (LOG.isDebugEnabled()) {
                LOG.debug("==> removeSelfFromTrie(" + this + ")");
            }
            if (evaluators == null && children.size() == 0) {
                TrieNode<U> parent = getParent();
                if (parent != null) {
                    parent.children.remove(str.charAt(0));
                }
            } else {
                if (LOG.isDebugEnabled()) {
                    LOG.debug("removeSelfFromTrie(" + this + ") could not remove self from Trie");
                }
            }
            if (LOG.isDebugEnabled()) {
                LOG.debug("<== removeSelfFromTrie(" + this + ")");
            }
        }

        void wrapUpUpdate() {
            if (isOptimizedForRetrieval) {
                RangerPerfTracer postSetupPerf = null;

                if (RangerPerfTracer.isPerfTraceEnabled(PERF_TRIE_INIT_LOG)) {
                    postSetupPerf = RangerPerfTracer.getPerfTracer(PERF_TRIE_INIT_LOG, "RangerResourceTrie.init(name=" + resourceDef.getName() + "-postSetup)");
                }

                postSetup(null);

                RangerPerfTracer.logAlways(postSetupPerf);
            }
        }

        void postSetup(Set<U> parentWildcardEvaluators) {
            setup(parentWildcardEvaluators);

            for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) {
                TrieNode<U> child = entry.getValue();

                child.postSetup(wildcardEvaluators);
            }
        }

        void setupIfNeeded(TrieNode<U> parent) {
            boolean setupNeeded = !isSetup;

            if (setupNeeded) {
                synchronized (this.children) {
                    setupNeeded = !isSetup;

                    if (setupNeeded) {
                        setup(parent == null ? null : parent.getWildcardEvaluators());

                        if (TRACE_LOG.isTraceEnabled()) {
                            StringBuilder sb = new StringBuilder();
                            this.toString(sb);
                            TRACE_LOG.trace("Set up is completed for this TriNode as a part of access evaluation : [" + sb + "]");
                        }
                    }
                }
            }
        }

        void setup(Set<U> parentWildcardEvaluators) {
            if (!isSetup) {
                // finalize wildcard-evaluators list by including parent's wildcard evaluators
                if (parentWildcardEvaluators != null) {
                    if (CollectionUtils.isEmpty(this.wildcardEvaluators)) {
                        this.wildcardEvaluators = parentWildcardEvaluators;
                    } else {
                        for (U evaluator : parentWildcardEvaluators) {
                            addWildcardEvaluator(evaluator);
                        }
                    }
                }

                this.isSharingParentWildcardEvaluators = wildcardEvaluators == parentWildcardEvaluators;

                // finalize evaluators list by including wildcard evaluators
                if (wildcardEvaluators != null) {
                    if (CollectionUtils.isEmpty(this.evaluators)) {
                        this.evaluators = wildcardEvaluators;
                    } else {
                        for (U evaluator : wildcardEvaluators) {
                            addEvaluator(evaluator);
                        }
                    }
                }
                isSetup = true;
            }
        }

        void collectChildEvaluators(Character sep, int startIdx, Set<U> childEvaluators) {
            if (!isOptimizedForSpace) {
                setupIfNeeded(getParent());
            }

            final int sepPos = startIdx < str.length() ? str.indexOf(sep, startIdx) : -1;

            if (sepPos == -1) { // ex: startIdx=5, path(str)=/tmp/test, path(a child) could be: /tmp/test.txt, /tmp/test/, /tmp/test/a, /tmp/test/a/b
                if (isOptimizedForSpace) {
                    if (this.wildcardEvaluators != null) {
                        childEvaluators.addAll(this.wildcardEvaluators);
                    }
                }
                if (this.evaluators != null) {
                    childEvaluators.addAll(this.evaluators);
                }

                children.values().stream().forEach(c -> c.collectChildEvaluators(sep, 0, childEvaluators));
            } else if (sepPos == (str.length() - 1)) { // ex: str=/tmp/test/, startIdx=5
                if (isOptimizedForSpace) {
                    if (this.wildcardEvaluators != null) {
                        childEvaluators.addAll(this.wildcardEvaluators);
                    }
                }
                if (this.evaluators != null) {
                    childEvaluators.addAll(this.evaluators);
                }
            }
        }

        void collectChildEvaluators(String resource, int startIndex, Set<U> childEvaluators) {
            if (startIndex == resource.length()) {
                collectChildEvaluators(childEvaluators);
            } else if (startIndex < resource.length()) {
                Character   startChar = getLookupChar(resource, startIndex);
                TrieNode<U> childNode = children.get(startChar);

                if (childNode != null) {
                    if (!isOptimizedForSpace) {
                        childNode.setupIfNeeded(childNode.getParent());
                    }

                    String childStr = childNode.getStr();
                    int lenToMatch = Math.min(resource.length() - startIndex, childStr.length());

                    if (resource.regionMatches(optIgnoreCase, startIndex, childStr, 0, lenToMatch)) {
                        if (childNode.wildcardEvaluators != null) {
                            childEvaluators.addAll(childNode.wildcardEvaluators);
                        }

                        if (childNode.evaluators != null) {
                            childEvaluators.addAll(childNode.evaluators);
                        }

                        if (resource.length() == (startIndex + lenToMatch)) {
                            childNode.collectChildEvaluators(childEvaluators);
                        } else {
                            childNode.children.values().stream().forEach(c -> c.collectChildEvaluators(resource, startIndex + childStr.length(), childEvaluators));
                        }
                    }
                }
            }
        }

        private void collectChildEvaluators(Set<U> childEvaluators) {
            Stack<TrieNode<U>> nodes = new Stack<>();

            nodes.addAll(children.values());

            while (!nodes.isEmpty()) {
                TrieNode<U> childNode = nodes.pop();

                if (!isOptimizedForSpace) {
                    childNode.setupIfNeeded(childNode.getParent());
                }

                if (childNode.wildcardEvaluators != null) {
                    childEvaluators.addAll(childNode.wildcardEvaluators);
                }

                if (childNode.evaluators != null) {
                    childEvaluators.addAll(childNode.evaluators);
                }

                nodes.addAll(childNode.children.values());
            }
        }

        private void removeEvaluatorFromSubtree(U evaluator) {
            if (LOG.isDebugEnabled()) {
                LOG.debug("==> removeEvaluatorFromSubtree(" + evaluator.getId() + ")");
            }
            if (CollectionUtils.isNotEmpty(wildcardEvaluators) && wildcardEvaluators.contains(evaluator)) {
                removeWildcardEvaluator(evaluator);
            } else {
                removeEvaluator(evaluator);
            }
            removeSelfFromTrie();
            if (LOG.isDebugEnabled()) {
                LOG.debug("<== removeEvaluatorFromSubtree(" + evaluator.getId() + ")");
            }
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            toString(sb);
            return sb.toString();
        }

        void toString(StringBuilder sb) {
            String nodeValue = this.str;

            sb.append("nodeValue=").append(nodeValue == null ? "ROOT" : nodeValue);
            sb.append("; isSetup=").append(isSetup);
            sb.append("; isSharingParentWildcardEvaluators=").append(isSharingParentWildcardEvaluators);
            sb.append("; childCount=").append(children.size());
            sb.append("; evaluators=[");
            if (evaluators != null) {
                for (U evaluator : evaluators) {
                    sb.append(evaluator.getId()).append("|,|");
                }
            }
            sb.append("]");

            sb.append("; wildcardEvaluators=[ ");
            if (wildcardEvaluators != null) {
                for (U evaluator : wildcardEvaluators) {
                    sb.append(evaluator.getId()).append("|,|");
                }
            }
            sb.append("]");
        }

        void toString(String prefix, StringBuilder sb) {
            String nodeValue = prefix + (str != null ? str : "");

            if (!nodeValue.equals(prefix)) {
                prefix = prefix + "|";
            }

            sb.append(prefix);
            toString(sb);
            sb.append("]\n");

            for (Map.Entry<Character, TrieNode<U>> entry : children.entrySet()) {
                TrieNode<U> child = entry.getValue();

                child.toString(nodeValue, sb);
            }
        }
    }
}