001: /* ====================================================================
002: * The Jcorporate Apache Style Software License, Version 1.2 05-07-2002
003: *
004: * Copyright (c) 1995-2002 Jcorporate Ltd. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * 2. Redistributions in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * 3. The end-user documentation included with the redistribution,
019: * if any, must include the following acknowledgment:
020: * "This product includes software developed by Jcorporate Ltd.
021: * (http://www.jcorporate.com/)."
022: * Alternately, this acknowledgment may appear in the software itself,
023: * if and wherever such third-party acknowledgments normally appear.
024: *
025: * 4. "Jcorporate" and product names such as "Expresso" must
026: * not be used to endorse or promote products derived from this
027: * software without prior written permission. For written permission,
028: * please contact info@jcorporate.com.
029: *
030: * 5. Products derived from this software may not be called "Expresso",
031: * or other Jcorporate product names; nor may "Expresso" or other
032: * Jcorporate product names appear in their name, without prior
033: * written permission of Jcorporate Ltd.
034: *
035: * 6. No product derived from this software may compete in the same
036: * market space, i.e. framework, without prior written permission
037: * of Jcorporate Ltd. For written permission, please contact
038: * partners@jcorporate.com.
039: *
040: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
041: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
042: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
043: * DISCLAIMED. IN NO EVENT SHALL JCORPORATE LTD OR ITS CONTRIBUTORS
044: * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
045: * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
046: * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
047: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
048: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
049: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
050: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
051: * SUCH DAMAGE.
052: * ====================================================================
053: *
054: * This software consists of voluntary contributions made by many
055: * individuals on behalf of the Jcorporate Ltd. Contributions back
056: * to the project(s) are encouraged when you make modifications.
057: * Please send them to support@jcorporate.com. For more information
058: * on Jcorporate Ltd. and its products, please see
059: * <http://www.jcorporate.com/>.
060: *
061: * Portions of this software are based upon other open source
062: * products and are subject to their respective licenses.
063: */
064:
065: package com.jcorporate.expresso.core.security.filters;
066:
067: import com.jcorporate.expresso.core.misc.ReusableChar;
068: import com.jcorporate.expresso.kernel.util.FastStringBuffer;
069:
070: /**
071: * A filter tree is a data structure that allows for quick matching and replacement
072: * of strings. Use it for a fast 'search and replace' system. Construction
073: * and setup is a fairly expensive operation in comparison to the actual searching,
074: * so use it for static types of filters that are usually instantiated for a long time.
075: *
076: * @author Michael Rimov
077: */
078: public class FilterTree {
079: protected FilterTreeNode root;
080:
081: public FilterTree() {
082: root = new FilterTreeNode();
083: }
084:
085: /**
086: * Insert a filtering string into the parse tree.
087: *
088: * @param specialString the string to look for
089: * @param replacementString the string to replace it with.
090: * @throws Exception if insertNode() or setReplacementstring() fails
091: */
092: public void addFilterString(String specialString,
093: String replacementString) throws Exception {
094: FilterTreeNode insertNode = root;
095:
096: for (int i = 0; i < specialString.length(); i++) {
097:
098: //
099: //We push both upper and lower case versions onto the tree so that
100: //we effectively have case insensitive searches. Note that both
101: //upper and lower case point to the same subnode.
102: //
103: ReusableChar c = new ReusableChar(ReusableChar
104: .toLowerCase(specialString.charAt(i)));
105: ReusableChar uc = new ReusableChar(ReusableChar
106: .toUpperCase(c.charValue()));
107:
108: if (insertNode.subnodeExists(c)
109: || insertNode.subnodeExists(uc)) {
110: insertNode = insertNode.getSubnode(c);
111: } else {
112: FilterTreeNode newNode = new FilterTreeNode();
113: insertNode.setSubnode(c, newNode);
114: insertNode.setSubnode(uc, newNode);
115: insertNode = newNode;
116: }
117: }
118:
119: //Once we get here, we'll insert at the insertnode the appropriate
120: //Replacement String
121: insertNode.setReplacementString(replacementString);
122: }
123:
124: public FilterTreeNode getRootNode() {
125: return root;
126: }
127:
128: /**
129: * Filters a string in a search and replace algorithm. Uses a "greedy" approach
130: * so that it gets the biggest "fitting" string to cut.
131: *
132: * @param input character array to examine.
133: * @return The filtered string
134: */
135: public String replaceFilter(char[] input) {
136: FastStringBuffer fsb = FastStringBuffer.getInstance();
137: String returnValue = null;
138: try {
139: int mark = -1;
140: ReusableChar c = new ReusableChar('a'); //Dummy Value
141: FilterTreeNode insertNode = root;
142: FilterTreeNode lastMatch = null;
143: String s = null;
144:
145: if (input.length == 0) {
146: return ("");
147: }
148: for (int i = 0; i < input.length; i++) {
149: c.setCharValue(input[i]);
150:
151: FilterTreeNode n = pushOntoParseTree(c, insertNode);
152:
153: if (n == null) {
154:
155: //We're at a leaf and we have to do something.
156: if (insertNode == root) {
157: fsb.append(c.charValue());
158:
159: //If this node is root - just dump the character.
160: } else if (s != null) {
161: fsb.append(s);
162: i--;
163:
164: //If there was a match further up the tree.
165: } else if (lastMatch != null) {
166: fsb.append(lastMatch.getReplacementString());
167: i = mark; //We have to rewind to the last match because
168:
169: //what follows may have been in the root of the
170: //tree.
171: //False alarm, append everything that has been in this tree.
172: } else {
173: i = mark; //Rewind to the last marked place
174: fsb.append(input, mark, i - mark + 1);
175: }
176:
177: insertNode = root;
178: mark = -1;
179: lastMatch = null;
180: s = null;
181: } else {
182: insertNode = n;
183:
184: //Check to see if there's any match for what we've got so far.
185: s = insertNode.getReplacementString();
186:
187: if (s != null) {
188: lastMatch = insertNode;
189: mark = i;
190: } else if (mark == -1) {
191: mark = i;
192: }
193: }
194: }
195: //We just ran out of characters. We have to dump any last matches
196: //on the tree and the rest of the characters.
197: if (s != null) {
198: fsb.append(s);
199:
200: //If this node is root - just dump the character.
201: //If there was a match further up the tree.
202: } else if (lastMatch != null) {
203: fsb.append(lastMatch.getReplacementString());
204:
205: if (mark < input.length && mark != -1) {
206: fsb.append(input, mark + 1, input.length
207: - (mark + 1));
208: }
209:
210: //False alarm, append everything that has been in this tree.
211: } else {
212: if (mark != -1) {
213: fsb.append(input, mark, input.length - mark);
214: }
215: }
216:
217: returnValue = fsb.toString();
218: } finally {
219: fsb.release();
220: fsb = null;
221: }
222:
223: return returnValue;
224: }
225:
226: /**
227: * Function moves things into the parse tree, modifying insertNode, etc
228: * Returns true, if able to push anything into tree. false if no subnodes
229: * exist for this particular character. <br />
230: * <p/>
231: * Note that this is case insensitive.
232: */
233: private FilterTreeNode pushOntoParseTree(ReusableChar c,
234: FilterTreeNode insertNode) {
235: if (insertNode.subnodeExists(c)) {
236: return insertNode.getSubnode(c);
237: } else {
238: return null;
239: }
240: }
241: }
|