Added: ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/CapabilitySet.java URL: http://svn.apache.org/viewvc/ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/CapabilitySet.java?rev=1464402&view=auto ============================================================================== --- ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/CapabilitySet.java (added) +++ ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/CapabilitySet.java Thu Apr 4 09:43:34 2013 @@ -0,0 +1,602 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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.felix.framework.capabilityset; + +import java.lang.reflect.Array; +import java.lang.reflect.Constructor; +import java.util.ArrayList; +import java.util.Collection; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import java.util.Set; +import java.util.TreeMap; +import org.apache.felix.framework.util.SecureAction; +import org.apache.felix.framework.util.StringComparator; +import org.apache.felix.framework.wiring.BundleCapabilityImpl; +import org.osgi.framework.wiring.BundleCapability; + +public class CapabilitySet +{ + private final Map<String, Map<Object, Set<BundleCapability>>> m_indices; + private final Set<BundleCapability> m_capSet = new HashSet<BundleCapability>(); + private final static SecureAction m_secureAction = new SecureAction(); + +public void dump() +{ + for (Entry<String, Map<Object, Set<BundleCapability>>> entry : m_indices.entrySet()) + { + boolean header1 = false; + for (Entry<Object, Set<BundleCapability>> entry2 : entry.getValue().entrySet()) + { + boolean header2 = false; + for (BundleCapability cap : entry2.getValue()) + { + if (cap.getRevision().getBundle().getBundleId() != 0) + { + if (!header1) + { + System.out.println(entry.getKey() + ":"); + header1 = true; + } + if (!header2) + { + System.out.println(" " + entry2.getKey()); + header2 = true; + } + System.out.println(" " + cap); + } + } + } + } +} + + public CapabilitySet(List<String> indexProps, boolean caseSensitive) + { + m_indices = (caseSensitive) + ? new TreeMap<String, Map<Object, Set<BundleCapability>>>() + : new TreeMap<String, Map<Object, Set<BundleCapability>>>( + new StringComparator(false)); + for (int i = 0; (indexProps != null) && (i < indexProps.size()); i++) + { + m_indices.put( + indexProps.get(i), new HashMap<Object, Set<BundleCapability>>()); + } + } + + public void addCapability(BundleCapability cap) + { + m_capSet.add(cap); + + // Index capability. + for (Entry<String, Map<Object, Set<BundleCapability>>> entry : m_indices.entrySet()) + { + Object value = cap.getAttributes().get(entry.getKey()); + if (value != null) + { + if (value.getClass().isArray()) + { + value = convertArrayToList(value); + } + + Map<Object, Set<BundleCapability>> index = entry.getValue(); + + if (value instanceof Collection) + { + Collection c = (Collection) value; + for (Object o : c) + { + indexCapability(index, cap, o); + } + } + else + { + indexCapability(index, cap, value); + } + } + } + } + + private void indexCapability( + Map<Object, Set<BundleCapability>> index, BundleCapability cap, Object capValue) + { + Set<BundleCapability> caps = index.get(capValue); + if (caps == null) + { + caps = new HashSet<BundleCapability>(); + index.put(capValue, caps); + } + caps.add(cap); + } + + public void removeCapability(BundleCapability cap) + { + if (m_capSet.remove(cap)) + { + for (Entry<String, Map<Object, Set<BundleCapability>>> entry : m_indices.entrySet()) + { + Object value = cap.getAttributes().get(entry.getKey()); + if (value != null) + { + if (value.getClass().isArray()) + { + value = convertArrayToList(value); + } + + Map<Object, Set<BundleCapability>> index = entry.getValue(); + + if (value instanceof Collection) + { + Collection c = (Collection) value; + for (Object o : c) + { + deindexCapability(index, cap, o); + } + } + else + { + deindexCapability(index, cap, value); + } + } + } + } + } + + private void deindexCapability( + Map<Object, Set<BundleCapability>> index, BundleCapability cap, Object value) + { + Set<BundleCapability> caps = index.get(value); + if (caps != null) + { + caps.remove(cap); + if (caps.isEmpty()) + { + index.remove(value); + } + } + } + + public Set<BundleCapability> match(SimpleFilter sf, boolean obeyMandatory) + { + Set<BundleCapability> matches = match(m_capSet, sf); + return (obeyMandatory) + ? matchMandatory(matches, sf) + : matches; + } + + private Set<BundleCapability> match(Set<BundleCapability> caps, SimpleFilter sf) + { + Set<BundleCapability> matches = new HashSet<BundleCapability>(); + + if (sf.getOperation() == SimpleFilter.MATCH_ALL) + { + matches.addAll(caps); + } + else if (sf.getOperation() == SimpleFilter.AND) + { + // Evaluate each subfilter against the remaining capabilities. + // For AND we calculate the intersection of each subfilter. + // We can short-circuit the AND operation if there are no + // remaining capabilities. + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; (caps.size() > 0) && (i < sfs.size()); i++) + { + matches = match(caps, sfs.get(i)); + caps = matches; + } + } + else if (sf.getOperation() == SimpleFilter.OR) + { + // Evaluate each subfilter against the remaining capabilities. + // For OR we calculate the union of each subfilter. + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; i < sfs.size(); i++) + { + matches.addAll(match(caps, sfs.get(i))); + } + } + else if (sf.getOperation() == SimpleFilter.NOT) + { + // Evaluate each subfilter against the remaining capabilities. + // For OR we calculate the union of each subfilter. + matches.addAll(caps); + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; i < sfs.size(); i++) + { + matches.removeAll(match(caps, sfs.get(i))); + } + } + else + { + Map<Object, Set<BundleCapability>> index = m_indices.get(sf.getName()); + if ((sf.getOperation() == SimpleFilter.EQ) && (index != null)) + { + Set<BundleCapability> existingCaps = index.get(sf.getValue()); + if (existingCaps != null) + { + matches.addAll(existingCaps); + matches.retainAll(caps); + } + } + else + { + for (Iterator<BundleCapability> it = caps.iterator(); it.hasNext(); ) + { + BundleCapability cap = it.next(); + Object lhs = cap.getAttributes().get(sf.getName()); + if (lhs != null) + { + if (compare(lhs, sf.getValue(), sf.getOperation())) + { + matches.add(cap); + } + } + } + } + } + + return matches; + } + + public static boolean matches(BundleCapability cap, SimpleFilter sf) + { + return matchesInternal(cap, sf) && matchMandatory(cap, sf); + } + + private static boolean matchesInternal(BundleCapability cap, SimpleFilter sf) + { + boolean matched = true; + + if (sf.getOperation() == SimpleFilter.MATCH_ALL) + { + matched = true; + } + else if (sf.getOperation() == SimpleFilter.AND) + { + // Evaluate each subfilter against the remaining capabilities. + // For AND we calculate the intersection of each subfilter. + // We can short-circuit the AND operation if there are no + // remaining capabilities. + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; matched && (i < sfs.size()); i++) + { + matched = matchesInternal(cap, sfs.get(i)); + } + } + else if (sf.getOperation() == SimpleFilter.OR) + { + // Evaluate each subfilter against the remaining capabilities. + // For OR we calculate the union of each subfilter. + matched = false; + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; !matched && (i < sfs.size()); i++) + { + matched = matchesInternal(cap, sfs.get(i)); + } + } + else if (sf.getOperation() == SimpleFilter.NOT) + { + // Evaluate each subfilter against the remaining capabilities. + // For OR we calculate the union of each subfilter. + List<SimpleFilter> sfs = (List<SimpleFilter>) sf.getValue(); + for (int i = 0; i < sfs.size(); i++) + { + matched = !(matchesInternal(cap, sfs.get(i))); + } + } + else + { + matched = false; + Object lhs = cap.getAttributes().get(sf.getName()); + if (lhs != null) + { + matched = compare(lhs, sf.getValue(), sf.getOperation()); + } + } + + return matched; + } + + private static Set<BundleCapability> matchMandatory( + Set<BundleCapability> caps, SimpleFilter sf) + { + for (Iterator<BundleCapability> it = caps.iterator(); it.hasNext(); ) + { + BundleCapability cap = it.next(); + if (!matchMandatory(cap, sf)) + { + it.remove(); + } + } + return caps; + } + + private static boolean matchMandatory(BundleCapability cap, SimpleFilter sf) + { + Map<String, Object> attrs = cap.getAttributes(); + for (Entry<String, Object> entry : attrs.entrySet()) + { + if (((BundleCapabilityImpl) cap).isAttributeMandatory(entry.getKey()) + && !matchMandatoryAttrbute(entry.getKey(), sf)) + { + return false; + } + } + return true; + } + + private static boolean matchMandatoryAttrbute(String attrName, SimpleFilter sf) + { + if ((sf.getName() != null) && sf.getName().equals(attrName)) + { + return true; + } + else if (sf.getOperation() == SimpleFilter.AND) + { + List list = (List) sf.getValue(); + for (int i = 0; i < list.size(); i++) + { + SimpleFilter sf2 = (SimpleFilter) list.get(i); + if ((sf2.getName() != null) + && sf2.getName().equals(attrName)) + { + return true; + } + } + } + return false; + } + + private static final Class[] STRING_CLASS = new Class[] { String.class }; + + private static boolean compare(Object lhs, Object rhsUnknown, int op) + { + // If this is a PRESENT operation, then just return true immediately + // since we wouldn't be here if the attribute wasn't present. + if (op == SimpleFilter.PRESENT) + { + return true; + } + + // If the type is comparable, then we can just return the + // result immediately. + if (lhs instanceof Comparable) + { + // Spec says SUBSTRING is false for all types other than string. + if ((op == SimpleFilter.SUBSTRING) && !(lhs instanceof String)) + { + return false; + } + + Object rhs; + if (op == SimpleFilter.SUBSTRING) + { + rhs = rhsUnknown; + } + else + { + try + { + rhs = coerceType(lhs, (String) rhsUnknown); + } + catch (Exception ex) + { + return false; + } + } + + switch (op) + { + case SimpleFilter.EQ : + try + { + return (((Comparable) lhs).compareTo(rhs) == 0); + } + catch (Exception ex) + { + return false; + } + case SimpleFilter.GTE : + try + { + return (((Comparable) lhs).compareTo(rhs) >= 0); + } + catch (Exception ex) + { + return false; + } + case SimpleFilter.LTE : + try + { + return (((Comparable) lhs).compareTo(rhs) <= 0); + } + catch (Exception ex) + { + return false; + } + case SimpleFilter.APPROX : + return compareApproximate(((Comparable) lhs), rhs); + case SimpleFilter.SUBSTRING : + return SimpleFilter.compareSubstring((List<String>) rhs, (String) lhs); + default: + throw new RuntimeException( + "Unknown comparison operator: " + op); + } + } + // Booleans do not implement comparable, so special case them. + else if (lhs instanceof Boolean) + { + Object rhs; + try + { + rhs = coerceType(lhs, (String) rhsUnknown); + } + catch (Exception ex) + { + return false; + } + + switch (op) + { + case SimpleFilter.EQ : + case SimpleFilter.GTE : + case SimpleFilter.LTE : + case SimpleFilter.APPROX : + return (lhs.equals(rhs)); + default: + throw new RuntimeException( + "Unknown comparison operator: " + op); + } + } + + // If the LHS is not a comparable or boolean, check if it is an + // array. If so, convert it to a list so we can treat it as a + // collection. + if (lhs.getClass().isArray()) + { + lhs = convertArrayToList(lhs); + } + + // If LHS is a collection, then call compare() on each element + // of the collection until a match is found. + if (lhs instanceof Collection) + { + for (Iterator iter = ((Collection) lhs).iterator(); iter.hasNext(); ) + { + if (compare(iter.next(), rhsUnknown, op)) + { + return true; + } + } + + return false; + } + + // Spec says SUBSTRING is false for all types other than string. + if ((op == SimpleFilter.SUBSTRING) && !(lhs instanceof String)) + { + return false; + } + + // Since we cannot identify the LHS type, then we can only perform + // equality comparison. + try + { + return lhs.equals(coerceType(lhs, (String) rhsUnknown)); + } + catch (Exception ex) + { + return false; + } + } + + private static boolean compareApproximate(Object lhs, Object rhs) + { + if (rhs instanceof String) + { + return removeWhitespace((String) lhs) + .equalsIgnoreCase(removeWhitespace((String) rhs)); + } + else if (rhs instanceof Character) + { + return Character.toLowerCase(((Character) lhs)) + == Character.toLowerCase(((Character) rhs)); + } + return lhs.equals(rhs); + } + + private static String removeWhitespace(String s) + { + StringBuffer sb = new StringBuffer(s.length()); + for (int i = 0; i < s.length(); i++) + { + if (!Character.isWhitespace(s.charAt(i))) + { + sb.append(s.charAt(i)); + } + } + return sb.toString(); + } + + private static Object coerceType(Object lhs, String rhsString) throws Exception + { + // If the LHS expects a string, then we can just return + // the RHS since it is a string. + if (lhs.getClass() == rhsString.getClass()) + { + return rhsString; + } + + // Try to convert the RHS type to the LHS type by using + // the string constructor of the LHS class, if it has one. + Object rhs = null; + try + { + // The Character class is a special case, since its constructor + // does not take a string, so handle it separately. + if (lhs instanceof Character) + { + rhs = new Character(rhsString.charAt(0)); + } + else + { + // Spec says we should trim number types. + if ((lhs instanceof Number) || (lhs instanceof Boolean)) + { + rhsString = rhsString.trim(); + } + Constructor ctor = m_secureAction.getConstructor(lhs.getClass(), STRING_CLASS); + m_secureAction.setAccesssible(ctor); + rhs = ctor.newInstance(new Object[] { rhsString }); + } + } + catch (Exception ex) + { + throw new Exception( + "Could not instantiate class " + + lhs.getClass().getName() + + " from string constructor with argument '" + + rhsString + "' because " + ex); + } + + return rhs; + } + + /** + * This is an ugly utility method to convert an array of primitives + * to an array of primitive wrapper objects. This method simplifies + * processing LDAP filters since the special case of primitive arrays + * can be ignored. + * @param array An array of primitive types. + * @return An corresponding array using pritive wrapper objects. + **/ + private static List convertArrayToList(Object array) + { + int len = Array.getLength(array); + List list = new ArrayList(len); + for (int i = 0; i < len; i++) + { + list.add(Array.get(array, i)); + } + return list; + } +} \ No newline at end of file
Added: ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/SimpleFilter.java URL: http://svn.apache.org/viewvc/ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/SimpleFilter.java?rev=1464402&view=auto ============================================================================== --- ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/SimpleFilter.java (added) +++ ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/capabilityset/SimpleFilter.java Thu Apr 4 09:43:34 2013 @@ -0,0 +1,651 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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.felix.framework.capabilityset; + +import java.util.ArrayList; +import java.util.List; +import java.util.Map; +import java.util.Map.Entry; +import org.apache.felix.framework.util.VersionRange; + +public class SimpleFilter +{ + public static final int MATCH_ALL = 0; + public static final int AND = 1; + public static final int OR = 2; + public static final int NOT = 3; + public static final int EQ = 4; + public static final int LTE = 5; + public static final int GTE = 6; + public static final int SUBSTRING = 7; + public static final int PRESENT = 8; + public static final int APPROX = 9; + + private final String m_name; + private final Object m_value; + private final int m_op; + + public SimpleFilter(String attr, Object value, int op) + { + m_name = attr; + m_value = value; + m_op = op; + } + + public String getName() + { + return m_name; + } + + public Object getValue() + { + return m_value; + } + + public int getOperation() + { + return m_op; + } + + public String toString() + { + String s = null; + switch (m_op) + { + case AND: + s = "(&" + toString((List) m_value) + ")"; + break; + case OR: + s = "(|" + toString((List) m_value) + ")"; + break; + case NOT: + s = "(!" + toString((List) m_value) + ")"; + break; + case EQ: + s = "(" + m_name + "=" + toEncodedString(m_value) + ")"; + break; + case LTE: + s = "(" + m_name + "<=" + toEncodedString(m_value) + ")"; + break; + case GTE: + s = "(" + m_name + ">=" + toEncodedString(m_value) + ")"; + break; + case SUBSTRING: + s = "(" + m_name + "=" + unparseSubstring((List<String>) m_value) + ")"; + break; + case PRESENT: + s = "(" + m_name + "=*)"; + break; + case APPROX: + s = "(" + m_name + "~=" + toEncodedString(m_value) + ")"; + break; + case MATCH_ALL: + s = "(*)"; + break; + } + return s; + } + + private static String toString(List list) + { + StringBuffer sb = new StringBuffer(); + for (int i = 0; i < list.size(); i++) + { + sb.append(list.get(i).toString()); + } + return sb.toString(); + } + + private static String toDecodedString(String s, int startIdx, int endIdx) + { + StringBuffer sb = new StringBuffer(endIdx - startIdx); + boolean escaped = false; + for (int i = 0; i < (endIdx - startIdx); i++) + { + char c = s.charAt(startIdx + i); + if (!escaped && (c == '\\')) + { + escaped = true; + } + else + { + escaped = false; + sb.append(c); + } + } + + return sb.toString(); + } + + private static String toEncodedString(Object o) + { + if (o instanceof String) + { + String s = (String) o; + StringBuffer sb = new StringBuffer(); + for (int i = 0; i < s.length(); i++) + { + char c = s.charAt(i); + if ((c == '\\') || (c == '(') || (c == ')') || (c == '*')) + { + sb.append('\\'); + } + sb.append(c); + } + + o = sb.toString(); + } + + return o.toString(); + } + + public static SimpleFilter parse(String filter) + { + int idx = skipWhitespace(filter, 0); + + if ((filter == null) || (filter.length() == 0) || (idx >= filter.length())) + { + throw new IllegalArgumentException("Null or empty filter."); + } + else if (filter.charAt(idx) != '(') + { + throw new IllegalArgumentException("Missing opening parenthesis: " + filter); + } + + SimpleFilter sf = null; + List stack = new ArrayList(); + boolean isEscaped = false; + while (idx < filter.length()) + { + if (sf != null) + { + throw new IllegalArgumentException( + "Only one top-level operation allowed: " + filter); + } + + if (!isEscaped && (filter.charAt(idx) == '(')) + { + // Skip paren and following whitespace. + idx = skipWhitespace(filter, idx + 1); + + if (filter.charAt(idx) == '&') + { + int peek = skipWhitespace(filter, idx + 1); + if (filter.charAt(peek) == '(') + { + idx = peek - 1; + stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.AND)); + } + else + { + stack.add(0, new Integer(idx)); + } + } + else if (filter.charAt(idx) == '|') + { + int peek = skipWhitespace(filter, idx + 1); + if (filter.charAt(peek) == '(') + { + idx = peek - 1; + stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.OR)); + } + else + { + stack.add(0, new Integer(idx)); + } + } + else if (filter.charAt(idx) == '!') + { + int peek = skipWhitespace(filter, idx + 1); + if (filter.charAt(peek) == '(') + { + idx = peek - 1; + stack.add(0, new SimpleFilter(null, new ArrayList(), SimpleFilter.NOT)); + } + else + { + stack.add(0, new Integer(idx)); + } + } + else + { + stack.add(0, new Integer(idx)); + } + } + else if (!isEscaped && (filter.charAt(idx) == ')')) + { + Object top = stack.remove(0); + if (top instanceof SimpleFilter) + { + if (!stack.isEmpty() && (stack.get(0) instanceof SimpleFilter)) + { + ((List) ((SimpleFilter) stack.get(0)).m_value).add(top); + } + else + { + sf = (SimpleFilter) top; + } + } + else if (!stack.isEmpty() && (stack.get(0) instanceof SimpleFilter)) + { + ((List) ((SimpleFilter) stack.get(0)).m_value).add( + SimpleFilter.subfilter(filter, ((Integer) top).intValue(), idx)); + } + else + { + sf = SimpleFilter.subfilter(filter, ((Integer) top).intValue(), idx); + } + } + else if (!isEscaped && (filter.charAt(idx) == '\\')) + { + isEscaped = true; + } + else + { + isEscaped = false; + } + + idx = skipWhitespace(filter, idx + 1); + } + + if (sf == null) + { + throw new IllegalArgumentException("Missing closing parenthesis: " + filter); + } + + return sf; + } + + private static SimpleFilter subfilter(String filter, int startIdx, int endIdx) + { + final String opChars = "=<>~"; + + // Determine the ending index of the attribute name. + int attrEndIdx = startIdx; + for (int i = 0; i < (endIdx - startIdx); i++) + { + char c = filter.charAt(startIdx + i); + if (opChars.indexOf(c) >= 0) + { + break; + } + else if (!Character.isWhitespace(c)) + { + attrEndIdx = startIdx + i + 1; + } + } + if (attrEndIdx == startIdx) + { + throw new IllegalArgumentException( + "Missing attribute name: " + filter.substring(startIdx, endIdx)); + } + String attr = filter.substring(startIdx, attrEndIdx); + + // Skip the attribute name and any following whitespace. + startIdx = skipWhitespace(filter, attrEndIdx); + + // Determine the operator type. + int op = -1; + switch (filter.charAt(startIdx)) + { + case '=': + op = EQ; + startIdx++; + break; + case '<': + if (filter.charAt(startIdx + 1) != '=') + { + throw new IllegalArgumentException( + "Unknown operator: " + filter.substring(startIdx, endIdx)); + } + op = LTE; + startIdx += 2; + break; + case '>': + if (filter.charAt(startIdx + 1) != '=') + { + throw new IllegalArgumentException( + "Unknown operator: " + filter.substring(startIdx, endIdx)); + } + op = GTE; + startIdx += 2; + break; + case '~': + if (filter.charAt(startIdx + 1) != '=') + { + throw new IllegalArgumentException( + "Unknown operator: " + filter.substring(startIdx, endIdx)); + } + op = APPROX; + startIdx += 2; + break; + default: + throw new IllegalArgumentException( + "Unknown operator: " + filter.substring(startIdx, endIdx)); + } + + // Parse value. + Object value = toDecodedString(filter, startIdx, endIdx); + + // Check if the equality comparison is actually a substring + // or present operation. + if (op == EQ) + { + String valueStr = filter.substring(startIdx, endIdx); + List<String> values = parseSubstring(valueStr); + if ((values.size() == 2) + && (values.get(0).length() == 0) + && (values.get(1).length() == 0)) + { + op = PRESENT; + } + else if (values.size() > 1) + { + op = SUBSTRING; + value = values; + } + } + + return new SimpleFilter(attr, value, op); + } + + public static List<String> parseSubstring(String value) + { + List<String> pieces = new ArrayList(); + StringBuffer ss = new StringBuffer(); + // int kind = SIMPLE; // assume until proven otherwise + boolean wasStar = false; // indicates last piece was a star + boolean leftstar = false; // track if the initial piece is a star + boolean rightstar = false; // track if the final piece is a star + + int idx = 0; + + // We assume (sub)strings can contain leading and trailing blanks + boolean escaped = false; +loop: for (;;) + { + if (idx >= value.length()) + { + if (wasStar) + { + // insert last piece as "" to handle trailing star + rightstar = true; + } + else + { + pieces.add(ss.toString()); + // accumulate the last piece + // note that in the case of + // (cn=); this might be + // the string "" (!=null) + } + ss.setLength(0); + break loop; + } + + // Read the next character and account for escapes. + char c = value.charAt(idx++); + if (!escaped && (c == '*')) + { + if (wasStar) + { + // encountered two successive stars; + // I assume this is illegal + throw new IllegalArgumentException("Invalid filter string: " + value); + } + if (ss.length() > 0) + { + pieces.add(ss.toString()); // accumulate the pieces + // between '*' occurrences + } + ss.setLength(0); + // if this is a leading star, then track it + if (pieces.isEmpty()) + { + leftstar = true; + } + wasStar = true; + } + else if (!escaped && (c == '\\')) + { + escaped = true; + } + else + { + escaped = false; + wasStar = false; + ss.append(c); + } + } + if (leftstar || rightstar || pieces.size() > 1) + { + // insert leading and/or trailing "" to anchor ends + if (rightstar) + { + pieces.add(""); + } + if (leftstar) + { + pieces.add(0, ""); + } + } + return pieces; + } + + public static String unparseSubstring(List<String> pieces) + { + StringBuffer sb = new StringBuffer(); + for (int i = 0; i < pieces.size(); i++) + { + if (i > 0) + { + sb.append("*"); + } + sb.append(toEncodedString(pieces.get(i))); + } + return sb.toString(); + } + + public static boolean compareSubstring(List<String> pieces, String s) + { + // Walk the pieces to match the string + // There are implicit stars between each piece, + // and the first and last pieces might be "" to anchor the match. + // assert (pieces.length > 1) + // minimal case is <string>*<string> + + boolean result = true; + int len = pieces.size(); + + // Special case, if there is only one piece, then + // we must perform an equality test. + if (len == 1) + { + return s.equals(pieces.get(0)); + } + + // Otherwise, check whether the pieces match + // the specified string. + + int index = 0; + +loop: for (int i = 0; i < len; i++) + { + String piece = pieces.get(i); + + // If this is the first piece, then make sure the + // string starts with it. + if (i == 0) + { + if (!s.startsWith(piece)) + { + result = false; + break loop; + } + } + + // If this is the last piece, then make sure the + // string ends with it. + if (i == len - 1) + { + if (s.endsWith(piece)) + { + result = true; + } + else + { + result = false; + } + break loop; + } + + // If this is neither the first or last piece, then + // make sure the string contains it. + if ((i > 0) && (i < (len - 1))) + { + index = s.indexOf(piece, index); + if (index < 0) + { + result = false; + break loop; + } + } + + // Move string index beyond the matching piece. + index += piece.length(); + } + + return result; + } + + private static int skipWhitespace(String s, int startIdx) + { + int len = s.length(); + while ((startIdx < len) && Character.isWhitespace(s.charAt(startIdx))) + { + startIdx++; + } + return startIdx; + } + + /** + * Converts a attribute map to a filter. The filter is created by iterating + * over the map's entry set. If ordering of attributes is important (e.g., + * for hitting attribute indices), then the map's entry set should iterate + * in the desired order. Equality testing is assumed for all attribute types + * other than version ranges, which are handled appropriated. If the attribute + * map is empty, then a filter that matches anything is returned. + * @param attrs Map of attributes to convert to a filter. + * @return A filter corresponding to the attributes. + */ + public static SimpleFilter convert(Map<String, Object> attrs) + { + // Rather than building a filter string to be parsed into a SimpleFilter, + // we will just create the parsed SimpleFilter directly. + + List<SimpleFilter> filters = new ArrayList<SimpleFilter>(); + + for (Entry<String, Object> entry : attrs.entrySet()) + { + if (entry.getValue() instanceof VersionRange) + { + VersionRange vr = (VersionRange) entry.getValue(); + if (vr.isFloorInclusive()) + { + filters.add( + new SimpleFilter( + entry.getKey(), + vr.getFloor().toString(), + SimpleFilter.GTE)); + } + else + { + SimpleFilter not = + new SimpleFilter(null, new ArrayList(), SimpleFilter.NOT); + ((List) not.getValue()).add( + new SimpleFilter( + entry.getKey(), + vr.getFloor().toString(), + SimpleFilter.LTE)); + filters.add(not); + } + + if (vr.getCeiling() != null) + { + if (vr.isCeilingInclusive()) + { + filters.add( + new SimpleFilter( + entry.getKey(), + vr.getCeiling().toString(), + SimpleFilter.LTE)); + } + else + { + SimpleFilter not = + new SimpleFilter(null, new ArrayList(), SimpleFilter.NOT); + ((List) not.getValue()).add( + new SimpleFilter( + entry.getKey(), + vr.getCeiling().toString(), + SimpleFilter.GTE)); + filters.add(not); + } + } + } + else + { + List<String> values = SimpleFilter.parseSubstring(entry.getValue().toString()); + if (values.size() > 1) + { + filters.add( + new SimpleFilter( + entry.getKey(), + values, + SimpleFilter.SUBSTRING)); + } + else + { + filters.add( + new SimpleFilter( + entry.getKey(), + values.get(0), + SimpleFilter.EQ)); + } + } + } + + SimpleFilter sf = null; + + if (filters.size() == 1) + { + sf = filters.get(0); + } + else if (attrs.size() > 1) + { + sf = new SimpleFilter(null, filters, SimpleFilter.AND); + } + else if (filters.isEmpty()) + { + sf = new SimpleFilter(null, null, SimpleFilter.MATCH_ALL); + } + + return sf; + } +} \ No newline at end of file Added: ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/resolver/CandidateComparator.java URL: http://svn.apache.org/viewvc/ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/resolver/CandidateComparator.java?rev=1464402&view=auto ============================================================================== --- ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/resolver/CandidateComparator.java (added) +++ ace/trunk/org.apache.ace.verifier/src/org/apache/felix/framework/resolver/CandidateComparator.java Thu Apr 4 09:43:34 2013 @@ -0,0 +1,130 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you 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.felix.framework.resolver; + +import java.util.Comparator; +import org.apache.felix.framework.wiring.BundleCapabilityImpl; +import org.osgi.framework.Constants; +import org.osgi.framework.Version; +import org.osgi.framework.wiring.BundleCapability; +import org.osgi.framework.wiring.BundleRevision; + +public class CandidateComparator implements Comparator<BundleCapability> +{ + public int compare(BundleCapability cap1, BundleCapability cap2) + { + // First check resolved state, since resolved capabilities have priority + // over unresolved ones. Compare in reverse order since we want to sort + // in descending order. + int c = 0; + if ((cap1.getRevision().getWiring() != null) + && (cap2.getRevision().getWiring() == null)) + { + c = -1; + } + else if ((cap1.getRevision().getWiring() == null) + && (cap2.getRevision().getWiring() != null)) + { + c = 1; + } + + // Compare revision capabilities. + if ((c == 0) && cap1.getNamespace().equals(BundleRevision.BUNDLE_NAMESPACE)) + { + c = ((Comparable) cap1.getAttributes().get(BundleRevision.BUNDLE_NAMESPACE)) + .compareTo(cap2.getAttributes().get(BundleRevision.BUNDLE_NAMESPACE)); + if (c == 0) + { + Version v1 = (!cap1.getAttributes().containsKey(Constants.BUNDLE_VERSION_ATTRIBUTE)) + ? Version.emptyVersion + : (Version) cap1.getAttributes().get(Constants.BUNDLE_VERSION_ATTRIBUTE); + Version v2 = (!cap2.getAttributes().containsKey(Constants.BUNDLE_VERSION_ATTRIBUTE)) + ? Version.emptyVersion + : (Version) cap2.getAttributes().get(Constants.BUNDLE_VERSION_ATTRIBUTE); + // Compare these in reverse order, since we want + // highest version to have priority. + c = compare(v2,v1); + } + } + // Compare package capabilities. + else if ((c == 0) && cap1.getNamespace().equals(BundleRevision.PACKAGE_NAMESPACE)) + { + c = ((Comparable) cap1.getAttributes().get(BundleRevision.PACKAGE_NAMESPACE)) + .compareTo(cap2.getAttributes().get(BundleRevision.PACKAGE_NAMESPACE)); + if (c == 0) + { + Version v1 = (!cap1.getAttributes().containsKey(BundleCapabilityImpl.VERSION_ATTR)) + ? Version.emptyVersion + : (Version) cap1.getAttributes().get(BundleCapabilityImpl.VERSION_ATTR); + Version v2 = (!cap2.getAttributes().containsKey(BundleCapabilityImpl.VERSION_ATTR)) + ? Version.emptyVersion + : (Version) cap2.getAttributes().get(BundleCapabilityImpl.VERSION_ATTR); + // Compare these in reverse order, since we want + // highest version to have priority. + c = compare(v2, v1); + } + } + + // Finally, compare bundle identity. + if (c == 0) + { + if (cap1.getRevision().getBundle().getBundleId() < + cap2.getRevision().getBundle().getBundleId()) + { + c = -1; + } + else if (cap1.getRevision().getBundle().getBundleId() > + cap2.getRevision().getBundle().getBundleId()) + { + c = 1; + } + } + + return c; + } + + private int compare(Version v1, Version v2) { + if (v1 instanceof Comparable) + { + return ((Comparable) v1).compareTo(v2); + } + int diff = v1.getMajor() - v2.getMajor(); + if (diff > 0) { + return 1; + } + if (diff < 0) { + return -1; + } + diff = v1.getMinor() - v2.getMinor(); + if (diff > 0) { + return 1; + } + if (diff < 0) { + return -1; + } + diff = v1.getMicro() - v2.getMicro(); + if (diff > 0) { + return 1; + } + if (diff < 0) { + return -1; + } + return v1.getQualifier().compareTo(v2.getQualifier()); + } +} \ No newline at end of file
