    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.commons.util.CollectionFactory;
    018import org.apache.tapestry5.ioc.IdMatcher;
    019import org.apache.tapestry5.ioc.Orderable;
    020import org.apache.tapestry5.ioc.internal.IdMatcherImpl;
    021import org.apache.tapestry5.ioc.internal.OrIdMatcher;
    022import org.slf4j.Logger;
    023
    024import static org.apache.tapestry5.commons.util.CollectionFactory.newList;
    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}