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