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