...

1. This proposal is based on utilizing the Trie implementation found in KAFKA-17423.
2. The Trie is based on the resource name, each node contains a set of ACLs that are associated with the name.
3. The string we are searching for is called the TARGET
4. The string we are comparing against is call the CANDIDATE.
5. GLOB characters are "?" and "*".
   1. "?" matches a single character
   2. "*" matches zero or more characters.

Matching

Matching the resource name

It is important to remember that the patterns with GLOBS are the  CANDIDATE stored in the Trie and are not the TARGET being searched for.   

...

The Trie implementation starts at the root node which contains the empty string.  It then begins a recursive descent of the trie by executing the Descent Process on the root node.

Descent process

• Is there a matching DENY ACL on this node?  If so return DENY.
• is there a matching LITERAL ACL on this node?  if so return the result.
• is there a child node that continues the TARGET pattern?  If so recurse in to the Descent process.
• if this point is reached stop descent process and begin Ascent process.

Ascent process

• Is this the root node? if so return NO MATCH.
• Is there a matching GLOB ACL on this node? if so return the result.
• Is there a "?" character child of this node?  if so execute the descent process on the "?" node. 
• Is there a "*" character child of this node?  if so execute the descent process for each potential block of characters. (This handles the multiple character nature of the '*' wildcard)
• if this point is reached move to the parent node and execute the Ascent process again.

The above process will match the resource names and will distribute them through a Trie so that the search will be much faster.

Matching Kafka Principal

We define an GlobPrincipal as

...

For other uses it performs GLOB character detection and will perform proper matching.  This class will need to be used within the Client and Server code to perform matching.  An additional "GlobPrincipals" class may be created to store a collection of glob principals and determine if any of the contained GlobPrincipal instances match a principal or string.

Matching Host

We define an GlobHost as

public class GlobHost {
    final private String pattern;
	final private Predicate<String> matcher;

    public GlobHost(String pattern) {
        this.pattern = pattern;
        this.matcher = globMatcher(pattern);
	}

    private static boolean hasGlob(String s) {
        return StringUtils.isEmpty(s) || s.contains("*") || s.contains("?");
    }

    private static Predicate<String> globMatcher(String pattern) {
     	if (hasGlob(pattern))
		{			
	 	    MatchPattern matchPattern = new MatchPattern(pattern);     
			return matchPattern::matches;
        } else
            return pattern::equals
        }
    }

    @Override
    final public int hash() {
	    return pattern.hash();    
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null) return false;
        if (getClass() != o.getClass()) return false;

        GlobHost that = (GlobHost) o;
		return this.pattern.equals(that.pattern);
    }

    @Override
    public String toString() {
        return pattern;
    }

    public matches(String other) {
        return matcher.test(other);
    }

...

For other uses it performs GLOB character detection and will perform proper matching.  This class will need to be used within the Client and Server code to perform matching.  An additional "GlobHosts" class may be created to store a collection of glob principals and determine if any of the contained GlobHost instances match a principal or string.

...

Pattern Types

A LITERAL match matches all the characters without wildcard expansion.

...

 * Search algorithm would return the LITERAL "HelloWorld" match before the wildcard match was found.

The GLOB pattern can replace both the LITERAL and the PREFIX types as the following rewrite table demonstrates

The current Trie implementation of the Literal "*" is to place the StandardACLs on the root node so they are located before any node that has characters.

Proposed Changes

Main changes include :

...