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;
021import static org.apache.tapestry5.ioc.internal.util.CollectionFactory.newList;
022import org.slf4j.Logger;
023
024import java.util.Collection;
025import java.util.List;
026import 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 */
032public 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}