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}