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}