You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@cocoon.apache.org by gi...@apache.org on 2006/06/21 21:40:06 UTC
svn commit: r416087 - in /cocoon/trunk/core/cocoon-core/src:
main/java/org/apache/cocoon/util/WildcardMatcherHelper.java
test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java
Author: giacomo
Date: Wed Jun 21 12:40:06 2006
New Revision: 416087
URL: http://svn.apache.org/viewvc?rev=416087&view=rev
Log:
Added new WildcardMatcherHelper. Feel free to check it, Carsten ;-)
Added:
cocoon/trunk/core/cocoon-core/src/main/java/org/apache/cocoon/util/WildcardMatcherHelper.java
cocoon/trunk/core/cocoon-core/src/test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java
Added: cocoon/trunk/core/cocoon-core/src/main/java/org/apache/cocoon/util/WildcardMatcherHelper.java
URL: http://svn.apache.org/viewvc/cocoon/trunk/core/cocoon-core/src/main/java/org/apache/cocoon/util/WildcardMatcherHelper.java?rev=416087&view=auto
==============================================================================
--- cocoon/trunk/core/cocoon-core/src/main/java/org/apache/cocoon/util/WildcardMatcherHelper.java (added)
+++ cocoon/trunk/core/cocoon-core/src/main/java/org/apache/cocoon/util/WildcardMatcherHelper.java Wed Jun 21 12:40:06 2006
@@ -0,0 +1,360 @@
+/*
+ * Copyright 1999-2006 The Apache Software Foundation.
+ *
+ * Licensed 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.cocoon.util;
+
+import java.util.HashMap;
+import java.util.Map;
+
+
+/**
+ * This class is an utility class that perform wilcard-patterns matching and isolation.
+ *
+ * @version $Id$
+ */
+public class WildcardMatcherHelper {
+ //~ Static fields/initializers -----------------------------------------------------------------
+
+ /** Default path separator: "/" */
+ public static final char ESC = '\\';
+
+ /** Default path separator: "/" */
+ public static final char PATHSEP = '/';
+
+ /** Default path separator: "/" */
+ public static final char STAR = '*';
+
+ //~ Methods ------------------------------------------------------------------------------------
+
+ /**
+ * Match a pattern agains a string and isolates wildcard replacement into a <code>Map</code>.
+ * <br>
+ * Here is how the matching algorithm works:
+ *
+ * <ul>
+ * <li>
+ * The '*' character, meaning that zero or more characters (excluding the path separator '/')
+ * are to be matched.
+ * </li>
+ * <li>
+ * The '**' sequence, meaning that zero or more characters (including the path separator '/')
+ * are to be matched.
+ * </li>
+ * <li>
+ * The '\*' sequence is honored as a litteral '*' character, not a wildcard
+ * </li>
+ * </ul>
+ *
+ * When more than two '*' characters, not separated by another character, are found their value is
+ * considered as '**'.
+ *
+ * @param pat The pattern string.
+ * @param str The string to math agains the pattern
+ *
+ * @return a <code>Map</code> containing the representation of the extracted pattern. The extracted patterns are
+ * keys in the <code>Map</code> from left to right beginning with "1" for te left most, "2" for the next,
+ * a.s.o. The key "0" is the string itself. If the return value is null, string does not match to the
+ * pattern .
+ */
+ public static Map match(final String pat,
+ final String str) {
+ final Matcher map = new Matcher(pat, str);
+
+ if(map.isMatch()) {
+ return map.getMap();
+ }
+
+ return null;
+ }
+
+ //~ Inner Classes ------------------------------------------------------------------------------
+
+ /**
+ * The private matcher class
+ */
+ private static class Matcher {
+ //~ Instance fields ------------------------------------------------------------------------
+
+ /** The character array of the pattern */
+ private final char[] apat;
+
+ /** The character array of the string */
+ private final char[] astr;
+
+ /** The <code>Map</code> to be filled */
+ private Map map = new HashMap();
+
+ /** The pattern */
+ private final String pat;
+
+ /**The string */
+ private final String str;
+
+ /** Whether string matched to pattern */
+ private final boolean matched;
+
+ /** map index */
+ private int idx = 0;
+
+ /** index into pattern */
+ private int ipat;
+
+ /** index into string */
+ private int istr;
+
+ //~ Constructors ---------------------------------------------------------------------------
+
+ /**
+ * Creates a new Matcher object.
+ *
+ * @param aPat The pattern
+ * @param aStr The string
+ */
+ public Matcher(final String aPat,
+ final String aStr) {
+ this.str = aStr;
+ this.pat = aPat;
+ ipat = pat.length() - 1;
+ istr = str.length() - 1;
+ apat = pat.toCharArray();
+ astr = str.toCharArray();
+ add(str);
+ matched = match();
+ }
+
+ //~ Methods --------------------------------------------------------------------------------
+
+ /**
+ * DOCUMENT ME!
+ *
+ * @return DOCUMENT ME!
+ */
+ public Map getMap() {
+ // reverse the map
+ final Map newmap = new HashMap();
+ int j = map.size() - 1;
+ newmap.put("0", map.get("0"));
+
+ for(int i = 1; i < map.size(); i++) {
+ final Object o = map.get("" + i);
+ newmap.put("" + j, o);
+ j--;
+ }
+
+ return newmap;
+ }
+
+ /**
+ * Has it matched?
+ *
+ * @return whether it has matched
+ */
+ public boolean isMatch() {
+ return matched;
+ }
+
+ /**
+ * Add a etracted substring to the map
+ *
+ * @param aStr The extracted substring
+ */
+ private void add(final String aStr) {
+ map.put("" + idx++, aStr);
+ }
+
+ /**
+ * Scans the pattern and the search string from the end toward the start
+ *
+ * @return wether the pstring matches the pattern
+ */
+ private boolean match() {
+ // scan a common literal suffix
+ scanLiteralSuffix();
+
+ // if we are already at the start of both strings
+ // than the pattern matched
+ if((ipat < 0) && (istr < 0)) return true;
+
+ // if hole string has matched the pattern so far and the rest of the pattern only has wildcard(s)
+ // we match too otherwise we clearly don't match
+ if((ipat >= 0) && (istr < 0)) {
+ while((ipat >= 0) && (apat[ipat] == STAR)) ipat--;
+
+ if(ipat < 0) {
+ add("");
+
+ return true;
+ } else {
+ return false;
+ }
+ }
+
+ // if hole pattern has matched the string so far but the string has more characters left
+ // we don't match
+ if((ipat < 0) && (istr >= 0)) return false;
+
+ // if we have not stopped at a wildcard character
+ // a character doesn't match and thus we do not match at all
+ if(apat[ipat] != STAR) return false;
+
+ // if it is a double (or more) wildcard pattern
+ if((ipat > 0) && (apat[ipat - 1] == STAR)) {
+ // skip to first non star charater in the pattern
+ while((--ipat >= 0) && (apat[ipat] == STAR));
+
+ // if we are at the start of the pattern we've matched and are finish scanning
+ if(ipat < 0) {
+ add(str.substring(0, istr + 1));
+
+ return true;
+ }
+
+ // Now we need to scan for the start of the literal characters in the pattern
+ final int eipat = ipat + 1; // end position of a literal character used for substring operations
+
+ while((ipat >= 0) && ((apat[ipat] != STAR) || ((ipat > 0) && (apat[ipat - 1] == ESC)))) ipat--;
+
+ // if we reached the start of the pattern just do a string compare with the corresponding part from
+ // the start of the string
+ if(ipat < 0) {
+ // if the remaining length of the string isn't the same as that found in the pattern
+ // we do not match
+ if(strncmp(apat, 0, astr, 0, eipat)) {
+ add(str.substring(eipat, istr + 1));
+
+ return true;
+ }
+
+ // otherwise we do not match
+ return false;
+ }
+
+ // Now we need to check whether the litteral substring of the pattern
+ // is contained in the string somewhere
+ final int l = eipat - ipat - 1;
+ final int eistr = istr + 1;
+
+ while(((istr - l) >= 0) && ! strncmp(apat, ipat + 1, astr, istr - l + 1, l)) istr--;
+
+ if((istr - l) < 0) return false;
+
+ add(str.substring(istr + 1, eistr));
+ istr -= l;
+ } else // if it is a single star pattern
+ {
+ // skip the star
+ --ipat;
+
+ // if we are at the beginning of the pattern we have to check there is not PATH_SEP in string
+ if(ipat < 0) {
+ final int eistr = istr + 1;
+
+ while((istr >= 0) && (astr[istr] != PATHSEP)) istr--;
+
+ if(istr < 0) {
+ add(str.substring(0, eistr));
+
+ return true;
+ }
+
+ // otherwise we do not match
+ return false;
+ }
+
+ // Now we need to search for the start of either a path sparator or another wildcard characters
+ // in the pattern
+ final int eipat = ipat + 1;
+
+ while((ipat >= 0) &&
+ ((apat[ipat] != STAR) || ((ipat > 0) && (apat[ipat - 1] == ESC))) &&
+ (apat[ipat] != PATHSEP)) {
+ ipat--;
+ }
+
+ // if we reached the beginning of the pattern just do a String compare with the corresponding part from
+ // the beginning of the string
+ if(ipat < 0) {
+ if(strncmp(apat, 0, astr, 0, eipat)) {
+ add(str.substring(eipat, istr + 1));
+
+ return true;
+ }
+
+ // otherwise we do not match
+ return false;
+ }
+
+ // Now we need to check whether the litteral substring of the pattern
+ // is contained in the string somewhere
+ if(apat[ipat] != PATHSEP) {
+ ipat++;
+ }
+
+ final int l = eipat - ipat;
+ final int eistr = ++istr; // move one up over the end
+
+ while(((istr - l) >= 0) && ! strncmp(apat, ipat, astr, istr - l, l)) istr--;
+
+ if((istr - l) < 0) return false;
+
+ add(str.substring(istr, eistr)); // TODO check this asd
+ istr -= (l + 1);
+ --ipat;
+ }
+
+ return match();
+ }
+
+ /**
+ * Scan a possible common suffix
+ */
+ private void scanLiteralSuffix() {
+ // scan a common literal suffix
+ while((ipat >= 0) &&
+ (istr >= 0) &&
+ ((apat[ipat] != STAR) || ((ipat > 0) && (apat[ipat - 1] == ESC))) &&
+ (apat[ipat] == astr[istr])) {
+ ipat--;
+
+ if((ipat >= 0) && (apat[ipat] == ESC)) ipat--;
+
+ istr--;
+ }
+ }
+
+ /**
+ * Compare two charater array from individual offsets
+ *
+ * @param a1 The first character array
+ * @param o1 The offset into the first character array
+ * @param a2 The second character array
+ * @param o2 The offset into the second character array
+ * @param l The length to compare
+ *
+ * @return Whether the all the mentioned characters match each other
+ */
+ private boolean strncmp(final char[] a1,
+ final int o1,
+ final char[] a2,
+ final int o2,
+ final int l) {
+ int i = 0;
+
+ for(i = 0; (i < l) && (a1[o1 + i] == a2[o2 + i]); i++);
+
+ return i == l;
+ }
+ }
+}
Added: cocoon/trunk/core/cocoon-core/src/test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java
URL: http://svn.apache.org/viewvc/cocoon/trunk/core/cocoon-core/src/test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java?rev=416087&view=auto
==============================================================================
--- cocoon/trunk/core/cocoon-core/src/test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java (added)
+++ cocoon/trunk/core/cocoon-core/src/test/java/org/apache/cocoon/util/WildcardMatcherHelperTestCase.java Wed Jun 21 12:40:06 2006
@@ -0,0 +1,175 @@
+/*
+ * Copyright 1999-2006 The Apache Software Foundation.
+ *
+ * Licensed 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.cocoon.util;
+
+import java.util.Map;
+
+import junit.framework.TestCase;
+
+
+/**
+ * @version $Id$
+ */
+public class WildcardMatcherHelperTestCase
+ extends TestCase {
+
+ //~ Methods ------------------------------------------------------------------------------------
+
+ public void test01WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("test", "test");
+ assertNotNull(result);
+ assertEquals("test", result.get("0"));
+ }
+
+ public void test02WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("end", "enp");
+ assertNull(result);
+ }
+
+ public void test03WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/t\\*d", "/t*d");
+ assertNotNull(result);
+ assertEquals("/t*d", result.get("0"));
+ }
+
+ public void test04WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("\\*d", "*d");
+ assertNotNull(result);
+ assertEquals("*d", result.get("0"));
+ }
+
+ public void test05WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("**", "*d");
+ assertNotNull(result);
+ assertEquals("*d", result.get("0"));
+ assertEquals("*d", result.get("1"));
+ }
+
+ public void test06WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("foo**", "foo*d");
+ assertNotNull(result);
+ assertEquals("foo*d", result.get("0"));
+ assertEquals("*d", result.get("1"));
+ }
+
+ public void test07WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("end", "en");
+ assertNull(result);
+ }
+
+ public void test08WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("en", "end");
+ assertNull(result);
+ }
+
+ public void test09WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("end**", "end");
+ assertNotNull(result);
+ assertEquals("", result.get("1"));
+ }
+
+ public void test10WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("end**end", "endendend");
+ assertNotNull(result);
+ assertEquals("end", result.get("1"));
+ }
+
+ public void test11WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("end**end", "endxxend");
+ assertNotNull(result);
+ assertEquals("xx", result.get("1"));
+ }
+
+ public void test12WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("*/end", "xx/end");
+ assertNotNull(result);
+ assertEquals("xx", result.get("1"));
+ }
+
+ public void test13WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/ab/cd*/end", "/ab/cdxx/end");
+ assertNotNull(result);
+ assertEquals("xx", result.get("1"));
+ }
+
+ public void test14WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/a*/cd*/end", "/ab/cdxx/end");
+ assertNotNull(result);
+ assertEquals("b", result.get("1"));
+ assertEquals("xx", result.get("2"));
+ }
+
+ public void test15WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/a**/cd*/end", "/ab/yy/cdxx/end");
+ assertNotNull(result);
+ assertEquals("b/yy", result.get("1"));
+ assertEquals("xx", result.get("2"));
+ }
+
+ public void test16WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/a**/cd*/end/*", "/ab/yy/cdxx/end/foobar/ii");
+ assertNull(result);
+ }
+
+ public void test17WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/a**/cd*/end/**", "/ab/yy/cdxx/end/foobar/ii");
+ assertNotNull(result);
+ assertEquals("b/yy", result.get("1"));
+ assertEquals("xx", result.get("2"));
+ assertEquals("foobar/ii", result.get("3"));
+ }
+
+ public void test18WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/a**cd*/end/**", "/ab/yy/cdxx/end/foobar/ii");
+ assertNotNull(result);
+ assertEquals("b/yy/", result.get("1"));
+ assertEquals("xx", result.get("2"));
+ assertEquals("foobar/ii", result.get("3"));
+ }
+
+ public void test19WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/*/*.xml", "/test/something.xmlbla.xml");
+ assertNotNull(result);
+ assertEquals("test", result.get("1"));
+ assertEquals("something.xmlbla", result.get("2"));
+ }
+
+ public void test20WildcardURIMatch()
+ throws Exception {
+ Map result = WildcardMatcherHelper.match("/ab/cd*/end", "/ab/cd/end");
+ assertNotNull(result);
+ assertEquals("", result.get("1"));
+ }
+}