Bug 493385 - Update to latest resolver code

FELIX-5254: Improve structure of permutations to use unmodifiable
capability lists

Change-Id: Ia7934d56198c6f0486acb3ded60ef7620d84ef20
Signed-off-by: Thomas Watson <tjwatson@us.ibm.com>

6 files changed, 212 insertions, 403 deletions

diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java
index 9dcf5a89e..8e2b9bb1f 100755
--- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java
+++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/Candidates.java
@@ -20,6 +20,8 @@ package org.apache.felix.resolver;
 
 import java.util.*;
 import java.util.Map.Entry;
+import java.util.concurrent.atomic.AtomicBoolean;
+
 import org.apache.felix.resolver.ResolverImpl.PermutationType;
 import org.apache.felix.resolver.ResolverImpl.ResolveSession;
 import org.apache.felix.resolver.util.*;
@@ -47,7 +49,7 @@ class Candidates
     // Maps a capability to requirements that match it.
     private final OpenHashMapSet<Capability, Requirement> m_dependentMap;
     // Maps a requirement to the capability it matches.
-    private final OpenHashMapList<Requirement, Capability> m_candidateMap;
+    private final OpenHashMapList m_candidateMap;
     // Maps a bundle revision to its associated wrapped revision; this only happens
     // when a revision being resolved has fragments to attach to it.
     private final Map<Resource, WrappedResource> m_allWrappedHosts;
@@ -57,20 +59,23 @@ class Candidates
     private final Map<Capability, Requirement> m_subtitutableMap;
 
     private final OpenHashMapSet<Requirement, Capability> m_delta;
+    private final AtomicBoolean m_candidateSelectorsUnmodifiable;
 
     /**
      * Private copy constructor used by the copy() method.
      */
     private Candidates(
         ResolveSession session,
+        AtomicBoolean candidateSelectorsUnmodifiable,
         OpenHashMapSet<Capability, Requirement> dependentMap,
-        OpenHashMapList<Requirement, Capability> candidateMap,
+        OpenHashMapList candidateMap,
         Map<Resource, WrappedResource> wrappedHosts,
         OpenHashMap<Resource, PopulateResult> populateResultCache,
         Map<Capability, Requirement> substitutableMap,
         OpenHashMapSet<Requirement, Capability> delta)
     {
         m_session = session;
+        m_candidateSelectorsUnmodifiable = candidateSelectorsUnmodifiable;
         m_dependentMap = dependentMap;
         m_candidateMap = candidateMap;
         m_allWrappedHosts = wrappedHosts;
@@ -85,8 +90,9 @@ class Candidates
     public Candidates(ResolveSession session)
     {
         m_session = session;
+        m_candidateSelectorsUnmodifiable = new AtomicBoolean(false);
         m_dependentMap = new OpenHashMapSet<Capability, Requirement>();
-        m_candidateMap = new OpenHashMapList<Requirement, Capability>();
+        m_candidateMap = new OpenHashMapList();
         m_allWrappedHosts = new HashMap<Resource, WrappedResource>();
         m_populateResultCache = new OpenHashMap<Resource, PopulateResult>();
         m_subtitutableMap = new OpenHashMap<Capability, Requirement>();
@@ -301,16 +307,16 @@ class Candidates
             {
                 continue;
             }
-            List<Capability> substitutes = m_candidateMap.get(req);
+            CandidateSelector substitutes = m_candidateMap.get(req);
             if (substitutes != null && !substitutes.isEmpty())
             {
-                String packageName = (String) substitutes.get(0).getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE);
+                String packageName = (String) substitutes.getCurrentCandidate().getAttributes().get(PackageNamespace.PACKAGE_NAMESPACE);
                 List<Capability> exportedPackages = exportNames.get(packageName);
                 if (exportedPackages != null)
                 {
                     // The package is exported;
                     // Check if the requirement only has the bundle's own export as candidates
-                    if (!exportedPackages.containsAll(substitutes))
+                    if (!exportedPackages.containsAll(substitutes.getRemainingCandidates()))
                     {
                         for (Capability exportedPackage : exportedPackages)
                         {
@@ -355,13 +361,13 @@ class Candidates
             {
                 for (Requirement dependent : dependents)
                 {
-                    List<Capability> candidates = m_candidateMap.get(dependent);
+                    CandidateSelector candidates = m_candidateMap.get(dependent);
                     if (candidates != null)
                     {
                         candidates:
-                        for (Iterator<Capability> iCandidates = candidates.iterator(); iCandidates.hasNext();)
+                        while (!candidates.isEmpty())
                         {
-                            Capability candidate = iCandidates.next();
+                            Capability candidate = candidates.getCurrentCandidate();
                             Integer candidateStatus = substituteStatuses.get(candidate);
                             if (candidateStatus == null)
                             {
@@ -375,7 +381,7 @@ class Candidates
                                 case SUBSTITUTED:
                                 default:
                                     // Need to remove any substituted that comes before an exported candidate
-                                    iCandidates.remove();
+                                    candidates.removeCurrentCandidate();
                                     // continue to next candidate
                                     break;
                             }
@@ -429,10 +435,10 @@ class Candidates
         // mark as processing to detect cycles
         substituteStatuses.put(substitutableCap, PROCESSING);
         // discover possible substitutes
-        List<Capability> substitutes = m_candidateMap.get(substitutableReq);
+        CandidateSelector substitutes = m_candidateMap.get(substitutableReq);
         if (substitutes != null)
         {
-            for (Capability substituteCandidate : substitutes)
+            for (Capability substituteCandidate : substitutes.getRemainingCandidates())
             {
                 if (substituteCandidate.getResource().equals(substitutableCap.getResource()))
                 {
@@ -468,10 +474,10 @@ class Candidates
 
         populate(toPopulate);
 
-        CopyOnWriteList<Capability> caps = m_candidateMap.get(m_session.getDynamicRequirement());
+        CandidateSelector caps = m_candidateMap.get(m_session.getDynamicRequirement());
         if (caps != null)
         {
-            m_session.getDynamicCandidates().retainAll(caps);
+            m_session.getDynamicCandidates().retainAll(caps.getRemainingCandidates());
         }
         else
         {
@@ -653,7 +659,7 @@ class Candidates
     private void addCandidates(Requirement req, List<Capability> candidates)
     {
         // Record the candidates.
-        m_candidateMap.put(req, new CopyOnWriteList<Capability>(candidates));
+        m_candidateMap.put(req, new CandidateSelector(candidates, m_candidateSelectorsUnmodifiable));
         for (Capability cap : candidates)
         {
             m_dependentMap.getOrCompute(cap).add(req);
@@ -699,29 +705,29 @@ class Candidates
      */
     public List<Capability> getCandidates(Requirement req)
     {
-        List<Capability> candidates = m_candidateMap.get(req);
+        CandidateSelector candidates = m_candidateMap.get(req);
         if (candidates != null)
         {
-            return Collections.unmodifiableList(candidates);
+            return candidates.getRemainingCandidates();
         }
         return null;
     }
 
     public Capability getFirstCandidate(Requirement req)
     {
-        List<Capability> candidates = m_candidateMap.get(req);
+        CandidateSelector candidates = m_candidateMap.get(req);
         if (candidates != null && !candidates.isEmpty())
         {
-            return candidates.get(0);
+            return candidates.getCurrentCandidate();
         }
         return null;
     }
 
     public void removeFirstCandidate(Requirement req)
     {
-        List<Capability> candidates = m_candidateMap.get(req);
+        CandidateSelector candidates = m_candidateMap.get(req);
         // Remove the conflicting candidate.
-        Capability cap = candidates.remove(0);
+        Capability cap = candidates.removeCurrentCandidate();
         if (candidates.isEmpty())
         {
             m_candidateMap.remove(req);
@@ -731,14 +737,16 @@ class Candidates
         capPath.add(cap);
     }
 
-    public List<Capability> clearCandidates(Requirement req, Collection<Capability> caps)
+    public CandidateSelector clearMultipleCardinalityCandidates(Requirement req, Collection<Capability> caps)
     {
-        List<Capability> l = m_candidateMap.get(req);
-        l.removeAll(caps);
-        // Update candidates delta with the removed capabilities.
-        CopyOnWriteSet<Capability> capPath = m_delta.getOrCompute(req);
-        capPath.addAll(caps);
-        return l;
+        // this is a special case where we need to completely replace the CandidateSelector
+    	// this method should never be called from normal Candidates permutations
+        CandidateSelector candidates = m_candidateMap.get(req);
+        List<Capability> remaining = new ArrayList<Capability>(candidates.getRemainingCandidates());
+        remaining.removeAll(caps);
+        candidates = new CandidateSelector(remaining, m_candidateSelectorsUnmodifiable);
+        m_candidateMap.put(req, candidates);
+        return candidates;
     }
 
     /**
@@ -815,8 +823,7 @@ class Candidates
                         else
                         {
                             m_dependentMap.get(hostCap).remove(hostReq);
-                            List<Capability> hosts = m_candidateMap.get(hostReq);
-                            hosts.remove(hostCap);
+                            CandidateSelector hosts = removeCandidate(hostReq, hostCap);
                             if (hosts.isEmpty())
                             {
                                 unselectedFragments.add(hostReq.getResource());
@@ -889,39 +896,36 @@ class Candidates
                             // matter if they come from the host or fragment,
                             // since we are completing replacing the declaring
                             // host and fragments with the wrapped host.
-                            List<Capability> cands = m_candidateMap.get(r);
+                            CandidateSelector cands = m_candidateMap.get(r);
+                            ShadowList shadow;
                             if (!(cands instanceof ShadowList))
                             {
-                                ShadowList<Capability> shadow = new ShadowList<Capability>(cands);
+                                shadow = ShadowList.createShadowList(cands);
                                 m_candidateMap.put(r, shadow);
                                 cands = shadow;
                             }
+                            else
+                            {
+                                shadow = (ShadowList) cands;
+                            }
 
                             // If the original capability is from a fragment, then
                             // ask the ResolveContext to insert it and update the
                             // shadow copy of the list accordingly.
                             if (!origCap.getResource().equals(hostResource.getDeclaredResource()))
                             {
-                                List<Capability> original = ((ShadowList<Capability>) cands).getOriginal();
-                                int removeIdx = original.indexOf(origCap);
-                                if (removeIdx != -1)
-                                {
-                                    original.remove(removeIdx);
-                                    cands.remove(removeIdx);
-                                }
-                                int insertIdx = m_session.getContext().insertHostedCapability(
-                                    original,
-                                    new SimpleHostedCapability(
-                                        hostResource.getDeclaredResource(),
-                                        origCap));
-                                cands.add(insertIdx, c);
+                                shadow.insertHostedCapability(
+                                        m_session.getContext(),
+                                        (HostedCapability) c,
+                                        new SimpleHostedCapability(
+                                                hostResource.getDeclaredResource(),
+                                                origCap));
                             }
                             // If the original capability is from the host, then
                             // we just need to replace it in the shadow list.
                             else
                             {
-                                int idx = cands.indexOf(origCap);
-                                cands.set(idx, c);
+                                shadow.replace(origCap, c);
                             }
                         }
                     }
@@ -932,11 +936,11 @@ class Candidates
             for (Requirement r : hostResource.getRequirements(null))
             {
                 Requirement origReq = ((WrappedRequirement) r).getDeclaredRequirement();
-                List<Capability> cands = m_candidateMap.get(origReq);
+                CandidateSelector cands = m_candidateMap.get(origReq);
                 if (cands != null)
                 {
-                    m_candidateMap.put(r, new CopyOnWriteList<Capability>(cands));
-                    for (Capability cand : cands)
+                    m_candidateMap.put(r, cands.copy());
+                    for (Capability cand : cands.getRemainingCandidates())
                     {
                         Set<Requirement> dependents = m_dependentMap.get(cand);
                         dependents.remove(origReq);
@@ -962,6 +966,8 @@ class Candidates
         m_candidateMap.trim();
         m_dependentMap.trim();
 
+        // mark the selectors as unmodifiable now
+        m_candidateSelectorsUnmodifiable.set(true);
         return null;
     }
 
@@ -973,11 +979,11 @@ class Candidates
     {
         Map<Capability, Map<String, Map<Version, List<Requirement>>>> hostFragments =
             new HashMap<Capability, Map<String, Map<Version, List<Requirement>>>>();
-        for (Entry<Requirement, CopyOnWriteList<Capability>> entry : m_candidateMap.fast())
+        for (Entry<Requirement, CandidateSelector> entry : m_candidateMap.fast())
         {
             Requirement req = entry.getKey();
-            List<Capability> caps = entry.getValue();
-            for (Capability cap : caps)
+            CandidateSelector caps = entry.getValue();
+            for (Capability cap : caps.getRemainingCandidates())
             {
                 // Keep track of hosts and associated fragments.
                 if (req.getNamespace().equals(HostNamespace.HOST_NAMESPACE))
@@ -1072,10 +1078,10 @@ class Candidates
      */
     private void remove(Requirement req)
     {
-        List<Capability> candidates = m_candidateMap.remove(req);
+        CandidateSelector candidates = m_candidateMap.remove(req);
         if (candidates != null)
         {
-            for (Capability cap : candidates)
+            for (Capability cap : candidates.getRemainingCandidates())
             {
                 Set<Requirement> dependents = m_dependentMap.get(cap);
                 if (dependents != null)
@@ -1102,8 +1108,7 @@ class Candidates
         {
             for (Requirement r : dependents)
             {
-                List<Capability> candidates = m_candidateMap.get(r);
-                candidates.remove(c);
+                CandidateSelector candidates = removeCandidate(r, c);
                 if (candidates.isEmpty())
                 {
                     m_candidateMap.remove(r);
@@ -1123,6 +1128,12 @@ class Candidates
         }
     }
 
+    private CandidateSelector removeCandidate(Requirement req, Capability cap) {
+        CandidateSelector candidates = m_candidateMap.get(req);
+        candidates.remove(cap);
+        return candidates;
+    }
+
     /**
      * Creates a copy of the Candidates object. This is used for creating
      * permutations when package space conflicts are discovered.
@@ -1133,7 +1144,8 @@ class Candidates
     {
         return new Candidates(
                 m_session,
-                m_dependentMap.deepClone(),
+                m_candidateSelectorsUnmodifiable,
+                m_dependentMap,
                 m_candidateMap.deepClone(),
                 m_allWrappedHosts,
                 m_populateResultCache,
@@ -1145,7 +1157,7 @@ class Candidates
     {
         // Create set of all revisions from requirements.
         Set<Resource> resources = new CopyOnWriteSet<Resource>();
-        for (Entry<Requirement, CopyOnWriteList<Capability>> entry
+        for (Entry<Requirement, CandidateSelector> entry
             : m_candidateMap.entrySet())
         {
             resources.add(entry.getKey().getResource());
@@ -1162,8 +1174,8 @@ class Candidates
                 : resource.getRequirements(null);
             for (Requirement req : reqs)
             {
-                List<Capability> candidates = m_candidateMap.get(req);
-                if ((candidates != null) && (candidates.size() > 0))
+                CandidateSelector candidates = m_candidateMap.get(req);
+                if ((candidates != null) && (!candidates.isEmpty()))
                 {
                     System.out.println("    " + req + ": " + candidates);
                 }
@@ -1173,8 +1185,8 @@ class Candidates
                 : Util.getDynamicRequirements(resource.getRequirements(null));
             for (Requirement req : reqs)
             {
-                List<Capability> candidates = m_candidateMap.get(req);
-                if ((candidates != null) && (candidates.size() > 0))
+                CandidateSelector candidates = m_candidateMap.get(req);
+                if ((candidates != null) && (!candidates.isEmpty()))
                 {
                     System.out.println("    " + req + ": " + candidates);
                 }
@@ -1196,8 +1208,8 @@ class Candidates
 
     public boolean canRemoveCandidate(Requirement req)
     {
-        List<Capability> candidates = m_candidateMap.get(req);
-        return ((candidates != null) && (candidates.size() > 1 || Util.isOptional(req)));
+        CandidateSelector candidates = m_candidateMap.get(req);
+        return ((candidates != null) && (candidates.getRemainingCandidateCount() > 1 || Util.isOptional(req)));
     }
 
     static class DynamicImportFailed extends ResolutionError {
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java
index b435aabae..1d6f9acd0 100755
--- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java
+++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/ResolverImpl.java
@@ -24,6 +24,7 @@ import java.util.Map.Entry;
 import java.util.concurrent.*;
 import java.util.concurrent.atomic.AtomicInteger;
 import org.apache.felix.resolver.util.ArrayMap;
+import org.apache.felix.resolver.util.CandidateSelector;
 import org.apache.felix.resolver.util.OpenHashMap;
 import org.osgi.framework.namespace.*;
 import org.osgi.resource.*;
@@ -219,7 +220,7 @@ public class ResolverImpl implements Resolver
         {
             // Check the root requirement to see if it is a multiple cardinality
             // requirement.
-            List<Capability> candidates = null;
+            CandidateSelector candidates = null;
             Requirement req = usedBlame.m_reqs.get(0);
             if (Util.isMultiple(req))
             {
@@ -231,7 +232,7 @@ public class ResolverImpl implements Resolver
                 }
                 // Get the current candidate list and remove all the offending root
                 // cause candidates from a copy of the current permutation.
-                candidates = m_multipleCardCandidates.clearCandidates(req, usedBlames.getRootCauses(req));
+                candidates = m_multipleCardCandidates.clearMultipleCardinalityCandidates(req, usedBlames.getRootCauses(req));
             }
             // We only are successful if there is at least one candidate left
             // for the requirement
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CandidateSelector.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CandidateSelector.java
new file mode 100755
index 000000000..0014bf037
--- /dev/null
+++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CandidateSelector.java
@@ -0,0 +1,90 @@
+/*
+ * 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.resolver.util;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+import org.osgi.resource.Capability;
+
+public class CandidateSelector {
+    private final AtomicBoolean isUnmodifiable;
+    protected final List<Capability> unmodifiable;
+    private int currentIndex = 0;
+
+    public CandidateSelector(List<Capability> candidates, AtomicBoolean isUnmodifiable) {
+        this.isUnmodifiable = isUnmodifiable;
+        this.unmodifiable = new ArrayList<Capability>(candidates);
+    }
+
+    protected CandidateSelector(CandidateSelector candidateSelector) {
+        this.isUnmodifiable = candidateSelector.isUnmodifiable;
+        this.unmodifiable = candidateSelector.unmodifiable;
+        this.currentIndex = candidateSelector.currentIndex;
+    }
+
+    public CandidateSelector copy() {
+        return new CandidateSelector(this);
+    }
+
+    public int getRemainingCandidateCount() {
+        return unmodifiable.size() - currentIndex;
+    }
+
+    public Capability getCurrentCandidate() {
+        return currentIndex < unmodifiable.size() ? unmodifiable.get(currentIndex) : null;
+    }
+
+    public List<Capability> getRemainingCandidates() {
+        return Collections.unmodifiableList(unmodifiable.subList(currentIndex, unmodifiable.size()));
+    }
+
+    public boolean isEmpty() {
+        return unmodifiable.size() <= currentIndex;
+    }
+
+    public Capability removeCurrentCandidate() {
+        Capability current = getCurrentCandidate();
+        if (current != null) {
+            currentIndex += 1;
+        }
+        return current;
+    }
+
+    public String toString() {
+        return getRemainingCandidates().toString();
+    }
+
+    public int remove(Capability cap) {
+        checkModifiable();
+        int index = unmodifiable.indexOf(cap);
+        if (index != -1) {
+            unmodifiable.remove(index);
+        }
+        return index;
+    }
+
+    protected void checkModifiable() {
+        if (isUnmodifiable.get()) {
+            throw new IllegalStateException("Trying to mutate after candidates have been prepared.");
+        }
+    }
+}
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CopyOnWriteList.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CopyOnWriteList.java
deleted file mode 100755
index 50eeb421f..000000000
--- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/CopyOnWriteList.java
+++ /dev/null
@@ -1,319 +0,0 @@
-/*
- * 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.resolver.util;
-
-import java.lang.reflect.Array;
-import java.util.*;
-
-@SuppressWarnings("NullableProblems")
-public class CopyOnWriteList<E> implements List<E>, Cloneable, RandomAccess {
-
-    Object[] data;
-
-    public CopyOnWriteList() {
-        data = new Object[0];
-    }
-
-    public CopyOnWriteList(CopyOnWriteList<? extends E> col) {
-        data = col.data;
-    }
-
-    public CopyOnWriteList(Collection<? extends E> col) {
-        data = col.toArray(new Object[col.size()]);
-    }
-
-    public int size() {
-        return data.length;
-    }
-
-    @SuppressWarnings("unchecked")
-    public E get(int index) {
-        return (E) data[index];
-    }
-
-    @SuppressWarnings("unchecked")
-    public E set(int index, E element) {
-        data = CopyOnWriteSet.copyOf(data, data.length);
-        E prev = (E) data[index];
-        data[index] = element;
-        return prev;
-    }
-
-    public void add(int index, E element) {
-        Object[] elements = data;
-        int len = elements.length;
-        Object[] newElements = new Object[len + 1];
-        int numMoved = len - index;
-        if (index > 0) {
-            System.arraycopy(elements, 0, newElements, 0, index);
-        }
-        if (numMoved > 0) {
-            System.arraycopy(elements, index, newElements, index + 1, numMoved);
-        }
-        newElements[index] = element;
-        data = newElements;
-    }
-
-    @SuppressWarnings("unchecked")
-    public E remove(int index) {
-        Object[] elements = data;
-        int len = elements.length;
-        E oldValue = (E) elements[index];
-        Object[] newElements = new Object[len - 1];
-        int numMoved = len - index - 1;
-        if (index > 0) {
-            System.arraycopy(elements, 0, newElements, 0, index);
-        }
-        if (numMoved > 0) {
-            System.arraycopy(elements, index + 1, newElements, index, numMoved);
-        }
-        data = newElements;
-        return oldValue;
-    }
-
-    public boolean isEmpty() {
-        return size() == 0;
-    }
-
-    public boolean contains(Object o) {
-        return indexOf(o) >= 0;
-    }
-
-    public Iterator<E> iterator() {
-        return new CopyOnWriteListIterator(0);
-    }
-
-    class CopyOnWriteListIterator implements ListIterator<E> {
-        int idx;
-        CopyOnWriteListIterator(int idx) {
-            this.idx = idx;
-        }
-
-        @Override
-        public boolean hasNext() {
-            return idx < data.length;
-        }
-
-        @Override
-        public E next() {
-            if (!hasNext()) {
-                throw new NoSuchElementException();
-            }
-            return (E) data[idx++];
-        }
-
-        @Override
-        public boolean hasPrevious() {
-            return idx >= 0;
-        }
-
-        @Override
-        public E previous() {
-            if (!hasPrevious()) {
-                throw new NoSuchElementException();
-            }
-            return (E) data[idx--];
-        }
-
-        @Override
-        public int nextIndex() {
-            return idx;
-        }
-
-        @Override
-        public int previousIndex() {
-            return idx - 1;
-        }
-
-        @Override
-        public void remove() {
-            CopyOnWriteList.this.remove(--idx);
-        }
-
-        @Override
-        public void set(E e) {
-            new UnsupportedOperationException();
-        }
-
-        @Override
-        public void add(E e) {
-            CopyOnWriteList.this.add(idx, e);
-        }
-    }
-
-    public Object[] toArray() {
-        return data.clone();
-    }
-
-    @SuppressWarnings("unchecked")
-    public <T> T[] toArray(T[] a) {
-        int size = data.length;
-        if (a.length < size)
-            // Make a new array of a's runtime type, but my contents:
-            return (T[]) CopyOnWriteSet.copyOf(data, size, a.getClass());
-        System.arraycopy(data, 0, a, 0, size);
-        if (a.length > size)
-            a[size] = null;
-        return a;
-    }
-
-    public boolean add(E e) {
-        add(size(), e);
-        return true;
-    }
-
-    public boolean remove(Object o) {
-        int index;
-        if ((index = indexOf(o)) >= 0) {
-            remove(index);
-            return true;
-        }
-        return false;
-    }
-
-    public boolean containsAll(Collection<?> c) {
-        Object[] elements = data;
-        int len = elements.length;
-        for (Object e : c) {
-            if (indexOf(e, elements, len) < 0)
-                return false;
-        }
-        return true;
-    }
-
-    private static int indexOf(Object o, Object[] d, int len) {
-        if (o == null) {
-            for (int i = len; i-- > 0;) {
-                if (d[i] == null)
-                    return i;
-            }
-        } else {
-            for (int i = len; i-- > 0;) {
-                if (o.equals(d[i]))
-                    return i;
-            }
-        }
-        return -1;
-    }
-
-    public boolean addAll(Collection<? extends E> c) {
-        return addAll(size(), c);
-    }
-
-    public boolean addAll(int index, Collection<? extends E> c) {
-        for (E e : c) {
-            add(index++, e);
-        }
-        return !(c.isEmpty());
-    }
-
-    public boolean removeAll(Collection<?> c) {
-        boolean modified = false;
-        Object[] d = data, o = data;
-        int idx = 0;
-        for (int i = 0, l = o.length; i < l; i++) {
-            if (c.contains(o[i])) {
-                if (!modified) {
-                    d = o.clone();
-                    idx = i;
-                    modified = true;
-                }
-            } else if (modified) {
-                d[idx++] = o[i];
-            }
-        }
-        if (modified) {
-            data = CopyOnWriteSet.copyOf(d, idx);
-        }
-        return modified;
-    }
-
-    public boolean retainAll(Collection<?> c) {
-        throw new UnsupportedOperationException();
-    }
-
-    public void clear() {
-        data = new Object[0];
-    }
-
-    public int indexOf(Object o) {
-        return indexOf(o, data, data.length);
-    }
-
-    public int lastIndexOf(Object o) {
-        throw new UnsupportedOperationException();
-    }
-
-    public ListIterator<E> listIterator() {
-        return new CopyOnWriteListIterator(0);
-    }
-
-    public ListIterator<E> listIterator(int index) {
-        return new CopyOnWriteListIterator(index);
-    }
-
-    public List<E> subList(int fromIndex, int toIndex) {
-        throw new UnsupportedOperationException();
-    }
-
-    /**
-     * Clone this object
-     *
-     * @return a cloned object.
-     */
-    @Override
-    @SuppressWarnings("unchecked")
-    public CopyOnWriteList<E> clone() {
-        try {
-            return (CopyOnWriteList<E>) super.clone();
-        } catch (CloneNotSupportedException exc) {
-            InternalError e = new InternalError();
-            e.initCause(exc);
-            throw e; //should never happen since we are cloneable
-        }
-    }
-
-    @Override
-    public int hashCode() {
-        return Arrays.hashCode(data);
-    }
-
-    @Override
-    public boolean equals(Object o) {
-        if (!(o instanceof CopyOnWriteList)) {
-            return false;
-        }
-        Object[] o1 = data;
-        Object[] o2 = ((CopyOnWriteList) o).data;
-        if (o1 == o2) {
-            return true;
-        }
-        int i;
-        if ((i = o1.length) != o2.length) {
-            return false;
-        }
-        while (i-- > 0) {
-            Object v1 = o1[i];
-            Object v2 = o2[i];
-            if (!(v1 == null ? v2 == null : v1.equals(v2)))
-                return false;
-        }
-        return true;
-    }
-}
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/OpenHashMapList.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/OpenHashMapList.java
index f314ed59a..ececcba03 100755
--- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/OpenHashMapList.java
+++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/OpenHashMapList.java
@@ -18,7 +18,9 @@
  */
 package org.apache.felix.resolver.util;
 
-public class OpenHashMapList<K, V> extends OpenHashMap<K, CopyOnWriteList<V>> {
+import org.osgi.resource.Requirement;
+
+public class OpenHashMapList extends OpenHashMap<Requirement, CandidateSelector> {
 
     public OpenHashMapList() {
         super();
@@ -28,21 +30,15 @@ public class OpenHashMapList<K, V> extends OpenHashMap<K, CopyOnWriteList<V>> {
         super(initialCapacity);
     }
 
-    @SuppressWarnings("unchecked")
-    public OpenHashMapList<K, V> deepClone() {
-        OpenHashMapList<K, V> copy = (OpenHashMapList<K, V>) super.clone();
+    public OpenHashMapList deepClone() {
+        OpenHashMapList copy = (OpenHashMapList) super.clone();
         Object[] values = copy.value;
         for (int i = values.length; i-- > 0;) {
             if (values[i] != null) {
-                values[i] = new CopyOnWriteList<V>((CopyOnWriteList<V>) values[i]);
+                values[i] = ((CandidateSelector) values[i]).copy();
             }
         }
         return copy;
     }
 
-    @Override
-    protected CopyOnWriteList<V> compute(K key) {
-        return new CopyOnWriteList<V>();
-    }
-
 }
diff --git a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/ShadowList.java b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/ShadowList.java
index 52335fa25..bb052a893 100755
--- a/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/ShadowList.java
+++ b/bundles/org.eclipse.osgi/felix/src/org/apache/felix/resolver/util/ShadowList.java
@@ -18,23 +18,52 @@
  */
 package org.apache.felix.resolver.util;
 
+import java.util.ArrayList;
 import java.util.List;
 
-import org.apache.felix.resolver.util.CopyOnWriteList;
+import org.osgi.resource.Capability;
+import org.osgi.service.resolver.HostedCapability;
+import org.osgi.service.resolver.ResolveContext;
 
-public class ShadowList<T> extends CopyOnWriteList<T>
+public class ShadowList extends CandidateSelector
 {
-    private final List<T> m_original;
+    public static  ShadowList createShadowList(CandidateSelector original) {
+        return new ShadowList(original);
+    }
+
+    private final List<Capability> m_original;
 
-    public ShadowList(List<T> original)
+    private ShadowList(CandidateSelector original)
     {
         super(original);
-        m_original = original;
+        m_original = new ArrayList<Capability>(original.getRemainingCandidates());
     }
 
-    public List<T> getOriginal()
+    private ShadowList(CandidateSelector shadow, List<Capability> original)
     {
-        return m_original;
+        super(shadow);
+        m_original = original;
     }
 
+    public ShadowList copy() {
+        return new ShadowList(this, m_original);
+    }
+
+    public void insertHostedCapability(ResolveContext context, HostedCapability wrappedCapability, HostedCapability toInsertCapability) {
+        checkModifiable();
+        int removeIdx = m_original.indexOf(toInsertCapability.getDeclaredCapability());
+        if (removeIdx != -1)
+        {
+            m_original.remove(removeIdx);
+            unmodifiable.remove(removeIdx);
+        }
+        int insertIdx = context.insertHostedCapability(m_original, toInsertCapability);
+        unmodifiable.add(insertIdx, wrappedCapability);
+    }
+
+    public void replace(Capability origCap, Capability c) {
+        checkModifiable();
+        int idx = unmodifiable.indexOf(origCap);
+        unmodifiable.set(idx, c);
+    }
 }
\ No newline at end of file