001// Copyright 2006, 2007, 2009 The Apache Software Foundation 002// 003// Licensed under the Apache License, Version 2.0 (the "License"); 004// you may not use this file except in compliance with the License. 005// You may obtain a copy of the License at 006// 007// http://www.apache.org/licenses/LICENSE-2.0 008// 009// Unless required by applicable law or agreed to in writing, software 010// distributed under the License is distributed on an "AS IS" BASIS, 011// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 012// See the License for the specific language governing permissions and 013// limitations under the License. 014 015package org.apache.tapestry5.ioc.internal.util; 016 017import org.apache.tapestry5.ioc.IdMatcher; 018import org.apache.tapestry5.ioc.Orderable; 019import org.apache.tapestry5.ioc.internal.IdMatcherImpl; 020import org.apache.tapestry5.ioc.internal.OrIdMatcher; 021 022import static org.apache.tapestry5.ioc.internal.util.CollectionFactory.newList; 023 024import org.slf4j.Logger; 025 026import java.util.Collection; 027import java.util.List; 028import java.util.Map; 029 030/** 031 * Used to order objects into an "execution" order. Each object must have a unique id. It may specify a list of 032 * constraints which identify the ordering of the objects. 033 */ 034public class Orderer<T> 035{ 036 private final OneShotLock lock = new OneShotLock(); 037 038 private final Logger logger; 039 040 private final boolean exceptionWhenDuplicateId; 041 042 private final List<Orderable> orderables = CollectionFactory.newList(); 043 044 private final Map<String, Orderable<T>> idToOrderable = CollectionFactory.newCaseInsensitiveMap(); 045 046 private final Map<String, DependencyNode<T>> dependencyNodesById = CollectionFactory.newCaseInsensitiveMap(); 047 048 // Special node that is always dead last: all other nodes are a dependency 049 // of the trailer. 050 051 private DependencyNode<T> trailer; 052 053 interface DependencyLinker<T> 054 { 055 void link(DependencyNode<T> source, DependencyNode<T> target); 056 } 057 058 // before: source is added as a dependency of target, so source will 059 // appear before target. 060 061 final DependencyLinker<T> _before = new DependencyLinker<T>() 062 { 063 @Override 064 public void link(DependencyNode<T> source, DependencyNode<T> target) 065 { 066 target.addDependency(source); 067 } 068 }; 069 070 // after: target is added as a dependency of source, so source will appear 071 // after target. 072 073 final DependencyLinker<T> _after = new DependencyLinker<T>() 074 { 075 @Override 076 public void link(DependencyNode<T> source, DependencyNode<T> target) 077 { 078 source.addDependency(target); 079 } 080 }; 081 082 public Orderer(Logger logger) 083 { 084 this(logger, false); 085 } 086 087 public Orderer(Logger logger, boolean exceptionWhenDuplicateId) 088 { 089 this.logger = logger; 090 this.exceptionWhenDuplicateId = exceptionWhenDuplicateId; 091 } 092 093 /** 094 * Adds an object to be ordered. 095 * 096 * @param orderable 097 */ 098 public void add(Orderable<T> orderable) 099 { 100 lock.check(); 101 102 String id = orderable.getId(); 103 104 if (idToOrderable.containsKey(id)) 105 { 106 final String message = UtilMessages.duplicateOrderer(id); 107 if (exceptionWhenDuplicateId) { 108 throw new IllegalArgumentException(message); 109 } 110 else { 111 logger.warn(message); 112 return; 113 } 114 } 115 116 orderables.add(orderable); 117 118 idToOrderable.put(id, orderable); 119 } 120 121 public void override(Orderable<T> orderable) 122 { 123 lock.check(); 124 125 String id = orderable.getId(); 126 127 Orderable<T> existing = idToOrderable.get(id); 128 129 if (existing == null) 130 throw new IllegalArgumentException( 131 String.format("Override for object '%s' is invalid as it does not match an existing object.", id)); 132 133 orderables.remove(existing); 134 orderables.add(orderable); 135 136 idToOrderable.put(id, orderable); 137 } 138 139 /** 140 * Adds an object to be ordered. 141 * 142 * @param id unique, qualified id for the target 143 * @param target the object to be ordered (or null as a placeholder) 144 * @param constraints optional, variable constraints 145 * @see #add(Orderable) 146 */ 147 148 public void add(String id, T target, String... constraints) 149 { 150 lock.check(); 151 152 add(new Orderable<T>(id, target, constraints)); 153 } 154 155 public void override(String id, T target, String... constraints) 156 { 157 lock.check(); 158 159 override(new Orderable<T>(id, target, constraints)); 160 } 161 162 public List<T> getOrdered() 163 { 164 lock.lock(); 165 166 initializeGraph(); 167 168 List<T> result = newList(); 169 170 for (Orderable<T> orderable : trailer.getOrdered()) 171 { 172 T target = orderable.getTarget(); 173 174 // Nulls are placeholders that are skipped. 175 176 if (target != null) result.add(target); 177 } 178 179 return result; 180 } 181 182 private void initializeGraph() 183 { 184 trailer = new DependencyNode<T>(logger, new Orderable<T>("*-trailer-*", null)); 185 186 addNodes(); 187 188 addDependencies(); 189 } 190 191 private void addNodes() 192 { 193 for (Orderable<T> orderable : orderables) 194 { 195 DependencyNode<T> node = new DependencyNode<T>(logger, orderable); 196 197 dependencyNodesById.put(orderable.getId(), node); 198 199 trailer.addDependency(node); 200 } 201 } 202 203 private void addDependencies() 204 { 205 for (Orderable<T> orderable : orderables) 206 { 207 addDependencies(orderable); 208 } 209 } 210 211 private void addDependencies(Orderable<T> orderable) 212 { 213 String sourceId = orderable.getId(); 214 215 for (String constraint : orderable.getConstraints()) 216 { 217 addDependencies(sourceId, constraint); 218 } 219 } 220 221 private void addDependencies(String sourceId, String constraint) 222 { 223 int colonx = constraint.indexOf(':'); 224 225 String type = colonx > 0 ? constraint.substring(0, colonx) : null; 226 227 DependencyLinker<T> linker = null; 228 229 if ("after".equals(type)) 230 linker = _after; 231 else if ("before".equals(type)) linker = _before; 232 233 if (linker == null) 234 { 235 logger.warn(UtilMessages.constraintFormat(constraint, sourceId)); 236 return; 237 } 238 239 String patternList = constraint.substring(colonx + 1); 240 241 linkNodes(sourceId, patternList, linker); 242 } 243 244 private void linkNodes(String sourceId, String patternList, DependencyLinker<T> linker) 245 { 246 Collection<DependencyNode<T>> nodes = findDependencies(sourceId, patternList); 247 248 DependencyNode<T> source = dependencyNodesById.get(sourceId); 249 250 for (DependencyNode<T> target : nodes) 251 { 252 linker.link(source, target); 253 } 254 } 255 256 private Collection<DependencyNode<T>> findDependencies(String sourceId, String patternList) 257 { 258 IdMatcher matcher = buildMatcherForPattern(patternList); 259 260 Collection<DependencyNode<T>> result = newList(); 261 262 for (String id : dependencyNodesById.keySet()) 263 { 264 if (sourceId.equals(id)) continue; 265 266 if (matcher.matches(id)) result.add(dependencyNodesById.get(id)); 267 } 268 269 return result; 270 } 271 272 private IdMatcher buildMatcherForPattern(String patternList) 273 { 274 List<IdMatcher> matchers = newList(); 275 276 for (String pattern : patternList.split(",")) 277 { 278 IdMatcher matcher = new IdMatcherImpl(pattern.trim()); 279 280 matchers.add(matcher); 281 } 282 283 return matchers.size() == 1 ? matchers.get(0) : new OrIdMatcher(matchers); 284 } 285}