/**
* Sync 2.1
* Copyright 2007 Zach Scrivena
* 2007-12-09
* zachscrivena@gmail.com
* http://syncdir.sourceforge.net/
*
* Sync performs one-way directory or file synchronization.
*
* TERMS AND CONDITIONS:
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
package sync;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.regex.Pattern;
import java.util.regex.PatternSyntaxException;
/**
* Represent a node in the filter tree.
*/
class FilterNode
{
/** this node's children, if any */
private final List<FilterNode> children;
/** enum type: logic applied to this node's children (AND, NAND, OR, NOR) */
static enum LogicType
{
AND,
NAND,
OR,
NOR;
}
/** logic applied to this node's children (AND, NAND, OR, NOR) */
private final FilterNode.LogicType logic;
/** enum type: type of filter pattern for this leaf node (REGEX, GLOB) */
static enum FilterType
{
REGEX,
GLOB;
}
/** compiled Java regex Pattern for this leaf node */
private final Pattern pattern;
/** true if the match result for this leaf node is inverted; false otherwise */
private final boolean inverted;
/** string description of the filter represented by this leaf node */
private final String stringValue;
/**
* Constructor for a non-leaf node with children.
*
* @param logic
* Logic applied to this node's children (AND, NAND, OR, NOR)
*/
FilterNode(
final FilterNode.LogicType logic)
{
this.logic = logic;
this.children = new ArrayList<FilterNode>();
this.pattern = null;
this.inverted = false;
this.stringValue = null;
}
/**
* Constructor for a leaf node.
*
* @param type
* Type of filter pattern for this leaf node (REGEX, GLOB)
* @param inverted
* true if the match result for this leaf node is inverted; false otherwise
* @param expression
* Regex/glob expression to be compiled to an equivalent Java regex pattern
*/
FilterNode(
final FilterType type,
final boolean inverted,
final String expression)
throws PatternSyntaxException
{
this.logic = null;
this.children = null;
this.inverted = inverted;
String s = null;
/* compile specified expression to an equivalent regex pattern */
Pattern p = null;
switch (type)
{
case REGEX:
p = Pattern.compile(expression);
s = inverted ? "regexnot" : "regex";
break;
case GLOB:
p = globToRegexPattern(expression);
s = inverted ? "globnot" : "glob";
break;
}
this.pattern = p;
this.stringValue = s + "(\"" + expression + "\")";
}
/**
* Add a child node to this non-leaf node.
*
* @param child
* Child node to be added
*/
public void addFilter(
final FilterNode child)
{
this.children.add(child);
}
/**
* Return true if the specified string matches this filter node.
* If this node is a leaf, then the string must match the specified pattern;
* if this node has children, then the string must satisfy the specified logic.
*
* @param s
* String to be matched against this filter
* @return
* true if the specified string matches this filter; false otherwise
*/
public boolean matches(
final String s)
{
if (this.children == null)
{
/* this is a leaf node; match the specified pattern */
return (this.pattern.matcher(s).matches() != this.inverted);
}
else
{
/* this node has children; check if specified logic is satisfied */
if (this.children.isEmpty())
throw new RuntimeException("FilterNode object is a non-leaf node without any children");
switch (this.logic)
{
case AND:
/* return true unless a child is false */
for (FilterNode n : this.children)
{
if (!n.matches(s))
return false;
}
return true;
case NAND:
/* return false unless a child is false */
for (FilterNode n : this.children)
{
if (!n.matches(s))
return true;
}
return false;
case OR:
/* return false unless a child is true */
for (FilterNode n : this.children)
{
if (n.matches(s))
return true;
}
return false;
case NOR:
/* return true unless a child is true */
for (FilterNode n : this.children)
{
if (n.matches(s))
return false;
}
return true;
}
}
return false; // should never be reached
}
/**
* Return the compiled Java regex Pattern equivalent to the specified GLOB expression.
*
* @param glob
* GLOB expression to be compiled
* @return
* Equivalent compiled Java regex Pattern
*/
private static Pattern globToRegexPattern(
final String glob)
throws PatternSyntaxException
{
/* Stack to keep track of the parser mode: */
/* "--" : Base mode (first on the stack) */
/* "[]" : Square brackets mode "[...]" */
/* "{}" : Curly braces mode "{...}" */
final Deque<String> parserMode = new ArrayDeque<String>();
parserMode.push("--"); // base mode
final int globLength = glob.length();
int index = 0; // index in glob
/* equivalent REGEX expression to be compiled */
final StringBuilder t = new StringBuilder();
while (index < globLength)
{
char c = glob.charAt(index++);
if (c == '\\')
{
/***********************
* (1) ESCAPE SEQUENCE *
***********************/
if (index == globLength)
{
/* no characters left, so treat '\' as literal char */
t.append(Pattern.quote("\\"));
}
else
{
/* read next character */
c = glob.charAt(index);
final String s = c + "";
if (("--".equals(parserMode.peek()) && "\\[]{}?*".contains(s)) ||
("[]".equals(parserMode.peek()) && "\\[]{}?*!-".contains(s)) ||
("{}".equals(parserMode.peek()) && "\\[]{}?*,".contains(s)))
{
/* escape the construct char */
index++;
t.append(Pattern.quote(s));
}
else
{
/* treat '\' as literal char */
t.append(Pattern.quote("\\"));
}
}
}
else if (c == '*')
{
/************************
* (2) GLOB PATTERN '*' *
************************/
/* create non-capturing group to match zero or more characters */
t.append(".*");
}
else if (c == '?')
{
/************************
* (3) GLOB PATTERN '?' *
************************/
/* create non-capturing group to match exactly one character */
t.append('.');
}
else if (c == '[')
{
/****************************
* (4) GLOB PATTERN "[...]" *
****************************/
/* opening square bracket '[' */
/* create non-capturing group to match exactly one character */
/* inside the sequence */
t.append('[');
parserMode.push("[]");
/* check for negation character '!' immediately after */
/* the opening bracket '[' */
if ((index < globLength) &&
(glob.charAt(index) == '!'))
{
index++;
t.append('^');
}
}
else if ((c == ']') && "[]".equals(parserMode.peek()))
{
/* closing square bracket ']' */
t.append(']');
parserMode.pop();
}
else if ((c == '-') && "[]".equals(parserMode.peek()))
{
/* character range '-' in "[...]" */
t.append('-');
}
else if (c == '{')
{
/****************************
* (5) GLOB PATTERN "{...}" *
****************************/
/* opening curly brace '{' */
/* create non-capturing group to match one of the */
/* strings inside the sequence */
t.append("(?:(?:");
parserMode.push("{}");
}
else if ((c == '}') && "{}".equals(parserMode.peek()))
{
/* closing curly brace '}' */
t.append("))");
parserMode.pop();
}
else if ((c == ',') && "{}".equals(parserMode.peek()))
{
/* comma between strings in "{...}" */
t.append(")|(?:");
}
else
{
/*************************
* (6) LITERAL CHARACTER *
*************************/
/* convert literal character to a regex string */
t.append(Pattern.quote(c + ""));
}
}
/* done parsing all chars of the source pattern string */
/* check for mismatched [...] or {...} */
if ("[]".equals(parserMode.peek()))
throw new PatternSyntaxException("Cannot find matching closing square bracket ] in GLOB expression", glob, -1);
if ("{}".equals(parserMode.peek()))
throw new PatternSyntaxException("Cannot find matching closing curly brace } in GLOB expression", glob, -1);
return Pattern.compile(t.toString());
}
/**
* Return a string description of the filter represented by this subtree.
*/
@Override
public String toString()
{
final StringBuilder s = new StringBuilder();
if (this.children == null)
{
/* this is a leaf node */
s.append(this.stringValue);
}
else
{
/* this node has children */
if (this.children.isEmpty())
throw new RuntimeException("FilterNode object is a non-leaf node without any children");
String delimiter = null;
switch (this.logic)
{
case AND:
delimiter = " AND ";
break;
case NAND:
s.append("NOT ");
delimiter = " AND ";
break;
case OR:
delimiter = " OR ";
break;
case NOR:
s.append("NOT ");
delimiter = " OR ";
break;
}
final int n = this.children.size();
if (n > 1)
s.append("{");
for (int i = 0; i < n - 1; i++)
{
s.append(this.children.get(i).toString());
s.append(delimiter);
}
s.append(this.children.get(n - 1).toString());
if (n > 1)
s.append("}");
}
return s.toString();
}
}