Ldap search filter parsing

README.md

Parses a ldap search filter and builds an AST, returns an instance of Node. To further evaluate the filter, one can use a NodeVisitor and call Node::accept(NodeVisitor).

LdapSearchFilter.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Manipule un filtre de recherche au format "filtre de recherche ldap".
 * La spéc a subit quelques modifications pour l'adapter à nos besoins
 * <ul>
 * <li>Pour simplifier le parsing, on ne gère ques des opérateurs sur un caractère</li>
 * <li>Les opérateur AND et OR peuvent avoir de 2 à n opérandes</li>
 * <li>Les variables sont toujours du côté gauche de l'opérateur de comparaison</li>
 * </ul>
 * 
 * @author jay
 * 
 * @see http://msdn.microsoft.com/en-us/library/windows/desktop/aa746475(v=vs.85).aspx
 * @see http://technet.microsoft.com/en-us/library/aa996205(v=exchg.65).aspx
 */
public class LdapSearchFilter {
	
	/*
	 * Inner classes
	 */
	
	/**
	 * Un itérateur sur une chaîne. Permet de parcourir
	 * les caractères un par un, avec possibilité de
	 * retour arrière sur un caractère.
	 * @author jay
	 */
	private static class StringIterator {
		
		private int index = 0;
		private char c = '\0';
		private String str;
		
		public StringIterator(String str) {
			this.str = str;
		}
		
		/**
		 * Permet de savoir s'il reste des caractères
		 * non parcourus dans la chaîne (i.e. l'appel à
		 * {@link #next()} ne provoquera pas d'exception).
		 * @return <code>true</code> si l'itérateur n'est pas
		 *	arrivé à la fin de la chaîne.
		 */
		public boolean hasNext() {
			return (c != 0) || (index < str.length());
		}

		public char next() {
			if(!hasNext())
				throw new IllegalStateException("Fin de chaîne prématurée");
			if(c != 0) {
				char temp = c;
				c = 0;
				return temp;
			}
			return str.charAt(index++);
		}

		public void pushBack(char c) {
			if(this.c != 0)
				throw new IllegalStateException("Impossible de revenir en arrière 2 fois");
			this.c = c;
		}
		
	}
	
	/**
	 * Les opérateurs qui combinent les filtres.
	 * @author jay
	 */
	public static enum CombiningOperator {
		
		AND('&'), OR('|'), NOT('!');
		
		private char op;
		
		private CombiningOperator(char c) {
			this.op = c;
		}
		
		public char value() {
			return op;
		}
		
		public static CombiningOperator fromValue(char c) {
			for(CombiningOperator operator : values()) {
				if(operator.op == c) return operator;
			}
			return null;
		}
		
	}

	/**
	 * Les opérateurs de test de valeur.
	 * @author jay
	 */
	public static enum TestingOperator {
		
		// l'operateur approximatif (~=) n'est pas géré
		// les opérateurs <= et >= sont remplacés par leurs
		// équivalents stricts (pour tenir sur 1 caractère)
		EQ('='), LT('<'), GT('>');
		
		private char op;
		
		private TestingOperator(char c) {
			this.op = c;
		}
		
		public char value() {
			return op;
		}
		
		public static TestingOperator fromValue(char c) {
			for(TestingOperator operator : values()) {
				if(operator.op == c) return operator;
			}
			return null;
		}

	}
	
	/**
	 * Définit l'interface à implémenter par un visiteur.
	 * @author jay
	 */
	public static interface NodeVisitor {
		/**
		 * La méthode appellée pour visiter les noeuds.
		 * @param node Une instance de {@link Filtre} ou de {@link Expression}.
		 */
		void visit(Node node);
	}
	
	/**
	 * Classe de base de tous les noeuds.
	 * @author jay
	 */
	private static abstract class Node {
		
		/**
		 * Génère une représentation textuelle du noeud
		 * et l'ajoute au buffer passé en paramètre.
		 * @param sb Le buffer.
		 * @return Le buffer modifié.
		 */
		protected abstract StringBuilder toString(StringBuilder sb);
		
		/**
		 * Permet de visiter l'arbre.
		 * @param visitor Le visiteur.
		 */
		public abstract void accept(NodeVisitor visitor);
		
	}
	
	/**
	 * Représente une expression « (&lt;attribute&gt;&lt;operator&gt;&lt;value&gt;) ».
	 * La classe est marquée comme finale pour qu'on ne puisse l'instancier que
	 * via le parsing d'un filtre de recherche ({@link LdapSearchFilter#parse(String)}).
	 * L'attribut n'est jamais vide (null ou ""), la valeur peut être "" mais pas null.
	 * @author jay
	 */
	public final static class Expression extends Node {
		protected String variable;
		protected TestingOperator op;
		protected String value;
		
		protected Expression() {
			// pas accessible de l'extérieur
		}
				
		@Override
		public void accept(NodeVisitor visitor) {
			visitor.visit(this);
		}
		
		@Override
		protected StringBuilder toString(StringBuilder sb) {
			sb.append('(').append(variable).append(op.value()).append(value).append(')');
			return sb;
		}
		
		@Override
		public String toString() {
			return toString(new StringBuilder()).toString();
		}
			
	}
	
	/**
	 * Représente une expression « (&lt;operator&gt;&lt;filter1&gt;&lt;filter2&gt;) »
	 * La classe est marquée comme finale pour qu'on ne puisse l'instancier que
	 * via le parsing d'un filtre de recherche ({@link LdapSearchFilter#parse(String)}).
	 * @author jay
	 */
	public final static class Filtre extends Node {
		protected CombiningOperator op;
		protected Node[] nodes;
		
		protected Filtre() {
			// pas accessible de l'extérieur
		}
		
		@Override
		public void accept(NodeVisitor visitor) {
			if(CombiningOperator.NOT.equals(op)) {
				nodes[0].accept(visitor);
			} else {
				for(Node node : nodes)
					node.accept(visitor);
			}
			visitor.visit(this);
		}
				
		@Override
		protected StringBuilder toString(StringBuilder sb) {
			sb.append('(').append(op.value());
			for(Node node : nodes)
				node.toString(sb);
			sb.append(')');
			return sb;
		}

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

	}
	
	/*
	 * Helpers
	 */
		
	/**
	 * Effectue le parsing.
	 * @param filter Le filtre de recherche.
	 * @return Le noeud racine.
	 * @throws IllegalArgumentException Si le filtre est incorrect.
	 */
	protected static Node doProcess(StringIterator iterator) throws IllegalArgumentException {
		if(!iterator.hasNext() || iterator.next() != '(')
			throw new IllegalArgumentException("Un filtre de recherche doit commencer par '('");
		
		Node result = null;
		char c = iterator.next();
		
		CombiningOperator operator = CombiningOperator.fromValue(c);
		if(operator == null) {
			
			iterator.pushBack(c);
			
			StringBuilder sb = new StringBuilder();
			Expression expr = new Expression();
			
			while(iterator.hasNext()) {
				c = iterator.next();
				TestingOperator test = TestingOperator.fromValue(c);
				if(test != null) {
					expr.op = test;
					if(sb.length() == 0)
						throw new IllegalArgumentException("Il manque la variable pour le test");
					expr.variable = sb.toString();					
					sb.setLength(0);
					break;
				} else {
					sb.append(c);
				}
			}
			
			while(iterator.hasNext()) {
				c = iterator.next();
				if(c == ')') {
					iterator.pushBack(c);
					break;
				}
				sb.append(c);
			}
			
			expr.value = sb.toString();
						
			result = expr;
		
		} else {
			
			Filtre filter = new Filtre();			
			filter.op = operator;
			
			List<Node> nodes = new ArrayList<Node>();
			nodes.add(doProcess(iterator));
			if(!CombiningOperator.NOT.equals(operator)) {
				while((c = iterator.next()) != ')') {
					iterator.pushBack(c);
					nodes.add(doProcess(iterator));
				};
				iterator.pushBack(c);
			}
			filter.nodes = nodes.toArray(new Node[nodes.size()]); 
			
			if(!CombiningOperator.NOT.equals(operator)) {
				if(filter.nodes.length < 2)
					throw new IllegalArgumentException("Pas assez d'opérandes pour l'opérateur '" + operator.value() + "'");
			}
			
			result = filter;
		}
		
		if(!iterator.hasNext() || iterator.next() != ')')
			throw new IllegalArgumentException("Un filtre de recherche doit se terminer par ')'");
		
		return result;

	}
	
	/*
	 * API
	 */
	
	/**
	 * Vérifie la validité d'un filtre de recherche. Les valeurs
	 * <code>null</code>, "" et [\s]+ sont considérées comme valides.
	 * Appelle {@link #parse(String)} et catch l'exception.
	 * @param filter Le filtre de recherche.
	 * @return <code>true</code> si l'expression est valide.
	 */
	public static boolean isValid(String filter) throws IllegalArgumentException {
		boolean valid = true;
		try {
			parse(filter);
		} catch(IllegalArgumentException e) {
			valid = false;
		}
		return valid;
	}
	
	/**
	 * Parse un filtre de recherche et renvoie
	 * le noeud racine de l'expression.
	 * @param filter Le filtre de recherche.
	 * @return Le noeud racine ou <code>null</code> si le filtre est "vide".
	 * @throws IllegalArgumentException Si le filtre est incorrect.
	 */
	public static Node parse(String filter) throws IllegalArgumentException {
		if(filter == null || (filter = filter.trim()).length() == 0)
			return null;
		
		StringIterator iterator = new StringIterator(filter);
		Node result = doProcess(iterator);
		if(iterator.hasNext())
			throw new IllegalArgumentException("Caractères en trop après la dernière ')'");
		return result;
	}
	
	/**
	 * Parcourt l'arbre pour en extraire les identifiants de variable.
	 * @param root Le noeud racine.
	 * @return La liste des identifiants trouvés, jamais <code>null</code>.
	 */	
	public static Set<String> findIdentifiers(Node root) {
		final Set<String> result = new HashSet<String>();
		root.accept(new NodeVisitor() {
			@Override
			public void visit(Node node) {
				if(node instanceof Expression) {
					Expression expr = (Expression)node;
					result.add(expr.variable);
				}
			}
		});
		return result;
	}
	
	public static void main(String[] args) throws Exception {
		
		String filter1 = "(&(guid=1001)(uid=jay))";
		Node filtre = LdapSearchFilter.parse(filter1);
		System.out.println(filtre.toString());
		
		Set<String> identifiers = LdapSearchFilter.findIdentifiers(filtre);
		System.out.println(identifiers);
		
		String filtre2 = "(&(variable=value))";
		System.out.println(LdapSearchFilter.isValid(filtre2));
		try {
			LdapSearchFilter.parse(filtre2);
		} catch(IllegalArgumentException e) {
			System.err.println(e.getMessage());
		}
		
	}
		
}