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