001 // Copyright 2004, 2005 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.hivemind.order;
016
017 import java.util.ArrayList;
018 import java.util.Collections;
019 import java.util.HashMap;
020 import java.util.Iterator;
021 import java.util.List;
022 import java.util.Map;
023
024 import org.apache.commons.logging.Log;
025 import org.apache.commons.logging.LogFactory;
026 import org.apache.hivemind.ApplicationRuntimeException;
027 import org.apache.hivemind.ErrorHandler;
028 import org.apache.hivemind.ErrorLog;
029 import org.apache.hivemind.HiveMind;
030 import org.apache.hivemind.impl.ErrorLogImpl;
031 import org.apache.hivemind.util.Defense;
032 import org.apache.hivemind.util.StringUtils;
033
034 /**
035 * Used to order objects into an "execution" order. Each object must have a name. It may specify a
036 * list of pre-requisites and a list of post-requisites.
037 *
038 * @author Howard Lewis Ship
039 */
040 public class Orderer
041 {
042 private final ErrorLog _errorLog;
043
044 private final String _objectType;
045
046 private List _orderingsList = null;
047
048 private Map _orderingsMap = null;
049
050 private Map _nodeMap = null;
051
052 private Node _leader;
053
054 private Node _trailer;
055
056 /**
057 * Creates an instance using <code>org.apache.hivemind.order.Orderer</code> as the Log.
058 */
059 public Orderer(ErrorHandler errorHandler, String objectType)
060 {
061 this(LogFactory.getLog(Orderer.class), errorHandler, objectType);
062 }
063
064 /**
065 * Creates a new instance, but directs all debug and error logging output to the provided log.
066 *
067 * @param log
068 * Used for logging any errors
069 * @param objectType
070 * user presentable name for the type of object to be ordered; used in some error
071 * messages
072 */
073 public Orderer(Log log, ErrorHandler errorHandler, String objectType)
074 {
075 this(new ErrorLogImpl(errorHandler, log), objectType);
076 }
077
078 /**
079 * Creates a new instance.
080 *
081 * @param errorLog
082 * Used for log any recoverable errors.
083 * @param objectType
084 * user presentable name for the type of object to be ordered; used in some error
085 * messages
086 */
087 public Orderer(ErrorLog errorLog, String objectType)
088 {
089 Defense.notNull(errorLog, "errorLog");
090 Defense.notNull(objectType, "objectType");
091
092 _errorLog = errorLog;
093 _objectType = objectType;
094 }
095
096 /**
097 * Adds a new object. All invocations of {@link #add(Object, String, String, String)} should
098 * occur before invoking {@link #getOrderedObjects()}.
099 *
100 * @param object
101 * an object to be sorted into order based on prereqs and postreqs
102 * @param name
103 * a unique name for the
104 * @param prereqs
105 * a comma-separated list of the names of objects that should precede this object in
106 * the list (or null)
107 * @param postreqs
108 * a comma-separated list of the names of objects that should follow this object in
109 * the list (or null)
110 */
111 public void add(Object object, String name, String prereqs, String postreqs)
112 {
113 if (_orderingsMap == null)
114 {
115 _orderingsMap = new HashMap();
116 _orderingsList = new ArrayList();
117 }
118
119 ObjectOrdering o = getOrderable(name);
120
121 if (o != null)
122 {
123 _errorLog.error(
124 OrdererMessages.duplicateName(_objectType, name, object, o.getObject()),
125 HiveMind.getLocation(object),
126 null);
127
128 return;
129 }
130
131 o = new ObjectOrdering(object, name, prereqs, postreqs);
132
133 _orderingsMap.put(name, o);
134 _orderingsList.add(o);
135 }
136
137 private ObjectOrdering getOrderable(String name)
138 {
139 return (ObjectOrdering) _orderingsMap.get(name);
140 }
141
142 /**
143 * Uses the information provided by {@link #add(Object, String, String, String)} to order the
144 * objects into an appropriate order based on the pre- and post-reqts provided. Errors such as
145 * cyclic dependencies or unrecognized names are logged and ignored.
146 */
147 public List getOrderedObjects()
148 {
149 if (_orderingsMap == null)
150 return Collections.EMPTY_LIST;
151
152 try
153 {
154 _nodeMap = new HashMap();
155
156 initializeGraph();
157
158 return _trailer.getOrder();
159 }
160 finally
161 {
162 _nodeMap = null;
163 _leader = null;
164 _trailer = null;
165 }
166 }
167
168 private void initializeGraph()
169 {
170 addNodes();
171
172 if (_leader == null)
173 _leader = new Node(null, "*-leader-*");
174
175 if (_trailer == null)
176 _trailer = new Node(null, "*-trailer-*");
177
178 addDependencies();
179 }
180
181 private Node getNode(String name)
182 {
183 return (Node) _nodeMap.get(getOrderable(name));
184 }
185
186 private void addNodes()
187 {
188 Iterator i = _orderingsList.iterator();
189
190 while (i.hasNext())
191 {
192 ObjectOrdering o = (ObjectOrdering) i.next();
193
194 Node node = new Node(o.getObject(), o.getName());
195
196 _nodeMap.put(o, node);
197
198 if ("*".equals(o.getPostreqs()))
199 {
200 if (_leader == null)
201 _leader = node;
202 else
203 _errorLog.error(OrdererMessages.dupeLeader(_objectType, o, getOrderable(_leader
204 .getName())), HiveMind.getLocation(o.getObject()), null);
205 }
206
207 if ("*".equals(o.getPrereqs()))
208 {
209 if (_trailer == null)
210 _trailer = node;
211 else
212 _errorLog.error(
213 OrdererMessages.dupeTrailer(_objectType, o, getOrderable(_trailer
214 .getName())),
215 HiveMind.getLocation(o.getObject()),
216 null);
217 }
218
219 }
220 }
221
222 private void addDependencies()
223 {
224 Iterator i = _orderingsList.iterator();
225
226 while (i.hasNext())
227 {
228 ObjectOrdering o = (ObjectOrdering) i.next();
229
230 addDependencies(o, getNode(o.getName()));
231 }
232 }
233
234 private void addDependencies(ObjectOrdering orderable, Node node)
235 {
236 addPreRequisites(orderable, node);
237 addPostRequisites(orderable, node);
238
239 try
240 {
241 if (node != _leader)
242 node.addDependency(_leader);
243
244 if (node != _trailer)
245 _trailer.addDependency(node);
246 }
247 catch (ApplicationRuntimeException ex)
248 {
249 // This code is unreachable ... but nonetheless.
250
251 String name = node.getName();
252 ObjectOrdering trigger = getOrderable(name);
253
254 _errorLog.error(OrdererMessages.dependencyCycle(_objectType, orderable, ex), HiveMind
255 .getLocation(trigger.getObject()), ex);
256 }
257 }
258
259 private void addPreRequisites(ObjectOrdering ordering, Node node)
260 {
261 String prereqs = ordering.getPrereqs();
262
263 if ("*".equals(prereqs))
264 return;
265
266 String[] names = StringUtils.split(prereqs);
267
268 for (int i = 0; i < names.length; i++)
269 {
270 String prename = names[i];
271
272 Node prenode = getNode(prename);
273
274 if (prenode == null)
275 {
276 _errorLog.error(
277 OrdererMessages.badDependency(_objectType, prename, ordering),
278 HiveMind.getLocation(ordering.getObject()),
279 null);
280 continue;
281 }
282
283 try
284 {
285 node.addDependency(prenode);
286 }
287 catch (ApplicationRuntimeException ex)
288 {
289 _errorLog.error(
290 OrdererMessages.dependencyCycle(_objectType, ordering, ex),
291 HiveMind.getLocation(ordering.getObject()),
292 ex);
293 }
294
295 }
296 }
297
298 private void addPostRequisites(ObjectOrdering ordering, Node node)
299 {
300 String postreqs = ordering.getPostreqs();
301
302 if ("*".equals(postreqs))
303 return;
304
305 String[] names = StringUtils.split(postreqs);
306
307 for (int i = 0; i < names.length; i++)
308 {
309 String postname = names[i];
310
311 Node postnode = getNode(postname);
312
313 if (postnode == null)
314 {
315 _errorLog.error(
316 OrdererMessages.badDependency(_objectType, postname, ordering),
317 HiveMind.getLocation(ordering.getObject()),
318 null);
319 }
320 else
321 {
322 try
323 {
324 postnode.addDependency(node);
325 }
326 catch (ApplicationRuntimeException ex)
327 {
328 _errorLog.error(
329 OrdererMessages.dependencyCycle(_objectType, ordering, ex),
330 HiveMind.getLocation(ordering.getObject()),
331 ex);
332 }
333 }
334 }
335 }
336
337 private static class Node
338 {
339 private Object _object;
340
341 private String _name;
342
343 private List _dependencies;
344
345 public Node(Object o, String name)
346 {
347 _object = o;
348 _name = name;
349 _dependencies = new ArrayList();
350 }
351
352 public String getName()
353 {
354 return _name;
355 }
356
357 public void addDependency(Node n)
358 {
359 if (n.isReachable(this))
360 throw new ApplicationRuntimeException(
361 "A cycle has been detected from the initial object [" + _name + "]",
362 HiveMind.getLocation(_object), null);
363
364 _dependencies.add(n);
365 }
366
367 private boolean isReachable(Node n)
368 {
369 boolean reachable = (n == this);
370 Iterator i = _dependencies.iterator();
371
372 while (i.hasNext() && !reachable)
373 {
374 Node dep = (Node) i.next();
375 reachable = (dep == n) ? true : dep.isReachable(n);
376 }
377
378 return reachable;
379 }
380
381 public List getOrder()
382 {
383 List result = new ArrayList();
384 fillOrder(result);
385
386 return result;
387 }
388
389 private void fillOrder(List result)
390 {
391 if (result.contains(_object))
392 return;
393
394 Iterator i = _dependencies.iterator();
395
396 while (i.hasNext())
397 {
398 Node dep = (Node) i.next();
399 dep.fillOrder(result);
400 }
401
402 if (_object != null)
403 result.add(_object);
404 }
405 }
406
407 }