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
015package org.apache.hivemind.order;
016
017import java.util.ArrayList;
018import java.util.Collections;
019import java.util.HashMap;
020import java.util.Iterator;
021import java.util.List;
022import java.util.Map;
023
024import org.apache.commons.logging.Log;
025import org.apache.commons.logging.LogFactory;
026import org.apache.hivemind.ApplicationRuntimeException;
027import org.apache.hivemind.ErrorHandler;
028import org.apache.hivemind.ErrorLog;
029import org.apache.hivemind.HiveMind;
030import org.apache.hivemind.impl.ErrorLogImpl;
031import org.apache.hivemind.util.Defense;
032import 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 */
040public 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}