    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
    015    package org.apache.tapestry5.ioc.internal.util;
    016
    017    import org.apache.tapestry5.ioc.IdMatcher;
    018    import org.apache.tapestry5.ioc.Orderable;
    019    import org.apache.tapestry5.ioc.internal.IdMatcherImpl;
    020    import org.apache.tapestry5.ioc.internal.OrIdMatcher;
    021    import static org.apache.tapestry5.ioc.internal.util.CollectionFactory.newList;
    022    import org.slf4j.Logger;
    023
    024    import java.util.Collection;
    025    import java.util.List;
    026    import 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     */
    032    public 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    }