    001    // Copyright 2006, 2007 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 IdToDependencyNode<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>> idToDependencyNode = 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 IdToDependencyNode(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      /**
    104       * Adds an object to be ordered.
    105       *
    106       * @param id          unique, qualified id for the target
    107       * @param target      the object to be ordered (or null as a placeholder)
    108       * @param constraints optional, variable constraints
    109       * @see #add(org.apache.tapestry5.ioc.Orderable)
    110       */
    111
    112      public void add(String id, T target, String... constraints)
    113      {
    114        lock.check();
    115
    116        add(new Orderable<T>(id, target, constraints));
    117      }
    118
    119      public List<T> getOrdered()
    120      {
    121        lock.lock();
    122
    123        initializeGraph();
    124
    125        List<T> result = newList();
    126
    127        for (Orderable<T> orderable : trailer.getOrdered())
    128        {
    129          T target = orderable.getTarget();
    130
    131          // Nulls are placeholders that are skipped.
    132
    133          if (target != null) result.add(target);
    134        }
    135
    136        return result;
    137      }
    138
    139      private void initializeGraph()
    140      {
    141        trailer = new DependencyNode<T>(logger, new Orderable<T>("*-trailer-*", null));
    142
    143        addNodes();
    144
    145        addDependencies();
    146      }
    147
    148      private void addNodes()
    149      {
    150        for (Orderable<T> orderable : orderables)
    151        {
    152          DependencyNode<T> node = new DependencyNode<T>(logger, orderable);
    153
    154          idToDependencyNode.put(orderable.getId(), node);
    155
    156          trailer.addDependency(node);
    157        }
    158      }
    159
    160      private void addDependencies()
    161      {
    162        for (Orderable<T> orderable : orderables)
    163        {
    164          addDependencies(orderable);
    165        }
    166      }
    167
    168      private void addDependencies(Orderable<T> orderable)
    169      {
    170        String sourceId = orderable.getId();
    171
    172        for (String constraint : orderable.getConstraints())
    173        {
    174          addDependencies(sourceId, constraint);
    175        }
    176      }
    177
    178      private void addDependencies(String sourceId, String constraint)
    179      {
    180        int colonx = constraint.indexOf(':');
    181
    182        String type = colonx > 0 ? constraint.substring(0, colonx) : null;
    183
    184        DependencyLinker<T> linker = null;
    185
    186        if ("after".equals(type))
    187          linker = after;
    188        else if ("before".equals(type)) linker = before;
    189
    190        if (linker == null)
    191        {
    192          logger.warn(UtilMessages.constraintFormat(constraint, sourceId));
    193          return;
    194        }
    195
    196        String patternList = constraint.substring(colonx + 1);
    197
    198        linkNodes(sourceId, patternList, linker);
    199      }
    200
    201      private void linkNodes(String sourceId, String patternList, DependencyLinker<T> linker)
    202      {
    203        Collection<DependencyNode<T>> nodes = findDependencies(sourceId, patternList);
    204
    205        DependencyNode<T> source = idToDependencyNode.get(sourceId);
    206
    207        for (DependencyNode<T> target : nodes)
    208        {
    209          linker.link(source, target);
    210        }
    211      }
    212
    213      private Collection<DependencyNode<T>> findDependencies(String sourceId, String patternList)
    214      {
    215        IdMatcher matcher = buildMatcherForPattern(patternList);
    216
    217        Collection<DependencyNode<T>> result = newList();
    218
    219        for (String id : idToDependencyNode.keySet())
    220        {
    221          if (sourceId.equals(id)) continue;
    222
    223          if (matcher.matches(id)) result.add(idToDependencyNode.get(id));
    224        }
    225
    226        return result;
    227      }
    228
    229      private IdMatcher buildMatcherForPattern(String patternList)
    230      {
    231        List<IdMatcher> matchers = newList();
    232
    233        for (String pattern : patternList.split(","))
    234        {
    235          IdMatcher matcher = new IdMatcherImpl(pattern.trim());
    236
    237          matchers.add(matcher);
    238        }
    239
    240        return matchers.size() == 1 ? matchers.get(0) : new OrIdMatcher(matchers);
    241      }
    242    }