001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements. See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership. The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License. You may obtain a copy of the License at
009 *
010 * http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied. See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.apache.commons.weaver.utils;
020
021import java.util.ArrayDeque;
022import java.util.Collection;
023import java.util.Collections;
024import java.util.Deque;
025import java.util.HashMap;
026import java.util.HashSet;
027import java.util.LinkedHashSet;
028import java.util.Map;
029import java.util.Set;
030
031import org.apache.commons.collections4.Factory;
032import org.apache.commons.collections4.map.LazyMap;
033import org.apache.commons.lang3.ArrayUtils;
034import org.apache.commons.lang3.Validate;
035import org.apache.commons.weaver.Consumes;
036import org.apache.commons.weaver.Produces;
037import org.apache.commons.weaver.spi.WeaveLifecycleProvider;
038
039/**
040 * Utility for working with {@link WeaveLifecycleProvider} types.
041 */
042public final class Providers {
043    private enum State {
044        VISITING, VISITED;
045    }
046
047    private static class SortWorker<P extends WeaveLifecycleProvider<?>> {
048        /**
049         * Implement {@link Providers#sort(Iterable)}.
050         *
051         * @param providers to sort
052         * @return {@link Iterable} of {@code P}
053         */
054        Iterable<P> sort(final Iterable<P> providers) {
055            Validate.noNullElements(providers);
056
057            final Map<Class<? extends P>, Set<Class<? extends P>>> dependencyMap = toDependencyMap(providers);
058
059            final Collection<Class<? extends P>> order = new LinkedHashSet<Class<? extends P>>();
060
061            final Map<Class<? extends P>, State> stateMap = new HashMap<Class<? extends P>, Providers.State>();
062            final Deque<Class<? extends P>> visiting = new ArrayDeque<Class<? extends P>>();
063
064            for (final Class<? extends P> type : dependencyMap.keySet()) {
065                final State state = stateMap.get(type);
066
067                if (state == null) {
068                    tsort(type, dependencyMap, stateMap, visiting, order);
069                } else if (state == State.VISITING) {
070                    throw new RuntimeException("Unexpected node in visiting state: " + type);
071                }
072            }
073            return imposeOrder(providers, order);
074        }
075
076        /**
077         * Adapted from Apache Ant's target sorting mechanism.
078         *
079         * @param root current provider type
080         * @param dependencyMap {@link Map} of provider type to dependencies
081         * @param stateMap {@link Map} of current visitation state
082         * @param visiting {@link Deque} used as a stack
083         * @param target destination {@link Collection} which must preserve order
084         */
085        private void tsort(final Class<? extends P> root,
086            final Map<Class<? extends P>, Set<Class<? extends P>>> dependencyMap,
087            final Map<Class<? extends P>, State> stateMap, final Deque<Class<? extends P>> visiting,
088            final Collection<Class<? extends P>> target) {
089
090            stateMap.put(root, State.VISITING);
091            visiting.push(root);
092
093            for (final Class<? extends P> dependency : dependencyMap.get(root)) {
094                final State state = stateMap.get(dependency);
095                if (state == State.VISITED) {
096                    continue;
097                }
098                Validate.validState(state == null, "Circular dependency: %s of %s", dependency.getName(),
099                    root.getName());
100                tsort(dependency, dependencyMap, stateMap, visiting, target);
101            }
102            final Class<? extends P> top = visiting.pop();
103            Validate.validState(top == root, "Stack out of balance: expected %s, found %s", root.getName(),
104                top.getName());
105
106            stateMap.put(root, State.VISITED);
107            target.add(root);
108        }
109
110        /**
111         * Read any {@link Produces} annotation associated with {@code providerClass}, designating types before which it
112         * should be invoked.
113         *
114         * @param providerClass
115         * @return {@link Class}[]
116         */
117        private Class<? extends P>[] producedBy(final Class<? extends P> providerClass) {
118            Validate.notNull(providerClass);
119            final Produces produces = providerClass.getAnnotation(Produces.class);
120            if (produces == null || produces.value().length == 0) {
121                @SuppressWarnings("unchecked")
122                final Class<? extends P>[] empty = (Class<? extends P>[]) ArrayUtils.EMPTY_CLASS_ARRAY;
123                return empty;
124            }
125            @SuppressWarnings("unchecked")
126            final Class<? extends P>[] result = (Class<? extends P>[]) produces.value();
127            return result;
128        }
129
130        /**
131         * Read any {@link Consumes} annotation associated with {@code providerClass} as dependencies.
132         *
133         * @param providerClass
134         * @return {@link Class}[]
135         */
136        private Class<? extends P>[] consumedBy(final Class<? extends P> providerClass) {
137            Validate.notNull(providerClass);
138            final Consumes consumes = providerClass.getAnnotation(Consumes.class);
139            if (consumes == null || consumes.value().length == 0) {
140                @SuppressWarnings("unchecked")
141                final Class<? extends P>[] empty = (Class<? extends P>[]) ArrayUtils.EMPTY_CLASS_ARRAY;
142                return empty;
143            }
144            @SuppressWarnings("unchecked")
145            final Class<? extends P>[] result = (Class<? extends P>[]) consumes.value();
146            return result;
147        }
148
149        /**
150         * Create a {@link Map} of provider type to dependency types.
151         *
152         * @param providers to inspect
153         * @return {@link Map}
154         */
155        private Map<Class<? extends P>, Set<Class<? extends P>>> toDependencyMap(final Iterable<P> providers) {
156
157            final Map<Class<? extends P>, Set<Class<? extends P>>> result = LazyMap.lazyMap(
158                new HashMap<Class<? extends P>, Set<Class<? extends P>>>(), new Factory<Set<Class<? extends P>>>() {
159
160                    @Override
161                    public Set<Class<? extends P>> create() {
162                        return new HashSet<Class<? extends P>>();
163                    }
164                });
165
166            for (final WeaveLifecycleProvider<?> provider : providers) {
167                @SuppressWarnings("unchecked")
168                final Class<? extends P> type = (Class<? extends P>) provider.getClass();
169                Collections.addAll(result.get(type), consumedBy(type));
170
171                for (final Class<? extends P> dependent : producedBy(type)) {
172                    result.get(dependent).add(type);
173                }
174            }
175            return result;
176        }
177
178        /**
179         * Order providers.
180         *
181         * @param providers to sort
182         * @param order to respect
183         * @return reordered providers
184         */
185        private Iterable<P> imposeOrder(final Iterable<P> providers, final Iterable<Class<? extends P>> order) {
186
187            final Set<P> result = new LinkedHashSet<P>();
188
189            for (final Class<? extends P> type : order) {
190                for (final P provider : providers) {
191                    if (type.isInstance(provider)) {
192                        result.add(provider);
193                    }
194                }
195            }
196            return Collections.unmodifiableSet(result);
197        }
198
199    }
200
201    private Providers() {
202    }
203
204    /**
205     * Sort the specified providers with respect to declared {@link Consumes} and {@link Produces} annotations.
206     *
207     * @param <P> the {@link WeaveLifecycleProvider} type
208     * @param providers to sort
209     * @return {@link Iterable} of {@code P}
210     */
211    public static <P extends WeaveLifecycleProvider<?>> Iterable<P> sort(final Iterable<P> providers) {
212        return new SortWorker<P>().sort(providers);
213    }
214
215}