001/* 002 * (C) Copyright 2012 Nuxeo SA (http://nuxeo.com/) and others. 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 * 016 * Contributors: 017 * Florent Guillaume 018 */ 019package org.nuxeo.ecm.platform.routing.core.impl; 020 021import java.io.Serializable; 022import java.util.ArrayList; 023import java.util.Collection; 024import java.util.Collections; 025import java.util.Deque; 026import java.util.HashMap; 027import java.util.HashSet; 028import java.util.LinkedList; 029import java.util.List; 030import java.util.Map; 031import java.util.Set; 032 033import org.apache.commons.lang.StringUtils; 034import org.apache.commons.lang.builder.ToStringBuilder; 035import org.nuxeo.ecm.core.api.CoreSession; 036import org.nuxeo.ecm.core.api.DocumentModel; 037import org.nuxeo.ecm.core.api.DocumentModelList; 038import org.nuxeo.ecm.core.api.DocumentRef; 039import org.nuxeo.ecm.core.api.IdRef; 040import org.nuxeo.ecm.core.api.PropertyException; 041import org.nuxeo.ecm.platform.routing.api.DocumentRoutingConstants; 042import org.nuxeo.ecm.platform.routing.api.DocumentRoutingService; 043import org.nuxeo.ecm.platform.routing.api.exception.DocumentRouteException; 044import org.nuxeo.ecm.platform.routing.core.impl.GraphNode.State; 045import org.nuxeo.ecm.platform.routing.core.impl.GraphNode.Transition; 046import org.nuxeo.runtime.api.Framework; 047 048/** 049 * @since 5.6 050 */ 051public class GraphRouteImpl extends DocumentRouteImpl implements GraphRoute { 052 053 private static final long serialVersionUID = 1L; 054 055 /** To be used through getter. */ 056 protected List<GraphNode> nodes; 057 058 /** To be used through getter. */ 059 protected Map<String, GraphNode> nodesById; 060 061 public GraphRouteImpl(DocumentModel doc) { 062 super(doc, new GraphRunner()); 063 } 064 065 @Override 066 public String toString() { 067 return new ToStringBuilder(this).append(getName()).toString(); 068 } 069 070 @Override 071 public Collection<GraphNode> getNodes() { 072 if (nodes == null) { 073 compute(); 074 } 075 return nodes; 076 } 077 078 protected void compute() { 079 String startNodeId = computeNodes(); 080 computeTransitions(); 081 computeLoopTransitions(startNodeId); 082 } 083 084 protected String computeNodes() { 085 CoreSession session = document.getCoreSession(); 086 DocumentModelList children = session.getChildren(document.getRef()); 087 nodes = new ArrayList<GraphNode>(children.size()); 088 nodesById = new HashMap<String, GraphNode>(); 089 String startNodeId = null; 090 for (DocumentModel doc : children) { 091 // TODO use adapters 092 if (doc.getType().equals("RouteNode")) { 093 GraphNode node = new GraphNodeImpl(doc, this); 094 String id = node.getId(); 095 if (nodesById.put(id, node) != null) { 096 throw new DocumentRouteException("Duplicate nodes with id: " + id); 097 } 098 nodes.add(node); 099 if (node.isStart()) { 100 if (startNodeId != null) { 101 throw new DocumentRouteException("Duplicate start nodes: " + startNodeId + " and " + id); 102 } 103 startNodeId = id; 104 } 105 } 106 } 107 return startNodeId; 108 } 109 110 /** 111 * Deduce input transitions from output transitions. 112 */ 113 protected void computeTransitions() throws DocumentRouteException { 114 for (GraphNode node : nodes) { 115 List<Transition> tt = node.getOutputTransitions(); 116 for (Transition t : tt) { 117 GraphNode target = getNode(t.target); 118 target.initAddInputTransition(t); 119 } 120 } 121 } 122 123 /** 124 * Finds which transitions are re-looping (feedback arc set). 125 */ 126 protected void computeLoopTransitions(String startNodeId) throws DocumentRouteException { 127 if (startNodeId == null) { 128 // incomplete graph 129 return; 130 } 131 /* 132 * Depth-first search. In the todo stack, each element records a list of the siblings left to visit at that 133 * depth. After visiting the last sibling, we go back to the parent and at this point mark it as visited in 134 * post-traversal order. 135 */ 136 List<String> postOrder = new LinkedList<String>(); 137 Deque<Deque<String>> stack = new LinkedList<Deque<String>>(); 138 Deque<String> first = new LinkedList<String>(); 139 first.add(startNodeId); 140 stack.push(first); 141 Set<String> done = new HashSet<String>(); 142 for (;;) { 143 // find next sibling 144 String nodeId = stack.peek().peek(); 145 if (nodeId == null) { 146 // last sibling done 147 // go back up one level and mark post-traversal order 148 stack.pop(); // pop empty children 149 if (stack.isEmpty()) { 150 // we are done 151 break; 152 } 153 nodeId = stack.peek().pop(); // pop parent 154 postOrder.add(nodeId); // mark post-traversal order 155 } else if (done.add(nodeId)) { 156 // traverse the next sibling 157 Deque<String> children = new LinkedList<String>(); 158 for (Transition t : getNode(nodeId).getOutputTransitions()) { 159 children.add(t.target); 160 } 161 // add children to stack and recurse 162 stack.push(children); 163 } else { 164 // already traversed 165 stack.peek().pop(); // skip it 166 } 167 } 168 169 // reverse the post-order to find the topological ordering 170 Collections.reverse(postOrder); 171 Map<String, Integer> ordering = new HashMap<String, Integer>(); 172 int i = 1; 173 for (String nodeId : postOrder) { 174 ordering.put(nodeId, Integer.valueOf(i++)); 175 } 176 177 // walk the graph and all transitions again 178 // and mark as looping the transitions pointing to a node 179 // with a smaller order that the source 180 done.clear(); 181 Deque<String> todo = new LinkedList<String>(); 182 todo.add(startNodeId); 183 while (!todo.isEmpty()) { 184 String nodeId = todo.pop(); 185 if (done.add(nodeId)) { 186 int source = ordering.get(nodeId).intValue(); 187 for (Transition t : getNode(nodeId).getOutputTransitions()) { 188 todo.push(t.target); 189 // compare orders to detected feeback arcs 190 int target = ordering.get(t.target).intValue(); 191 if (target <= source) { 192 t.loop = true; 193 } 194 } 195 } 196 } 197 } 198 199 @Override 200 public GraphNode getStartNode() throws DocumentRouteException { 201 for (GraphNode node : getNodes()) { 202 if (node.isStart()) { 203 return node; 204 } 205 } 206 throw new DocumentRouteException("No start node for graph: " + getName()); 207 } 208 209 @Override 210 public GraphNode getNode(String id) { 211 getNodes(); // compute 212 GraphNode node = nodesById.get(id); 213 if (node != null) { 214 return node; 215 } 216 throw new IllegalArgumentException("No node with id: " + id + " in graph: " + this); 217 } 218 219 @Override 220 public Map<String, Serializable> getVariables() { 221 return GraphVariablesUtil.getVariables(document, PROP_VARIABLES_FACET); 222 } 223 224 @Override 225 public Map<String, Serializable> getJsonVariables() { 226 return GraphVariablesUtil.getVariables(document, PROP_VARIABLES_FACET, true); 227 } 228 229 @Override 230 public void setVariables(Map<String, Serializable> map) { 231 GraphVariablesUtil.setVariables(document, PROP_VARIABLES_FACET, map); 232 } 233 234 @Override 235 public void setJSONVariables(Map<String, String> map) { 236 GraphVariablesUtil.setJSONVariables(document, PROP_VARIABLES_FACET, map); 237 } 238 239 @Override 240 public DocumentModelList getAttachedDocumentModels() { 241 @SuppressWarnings("unchecked") 242 List<String> ids = (List<String>) document.getPropertyValue( 243 DocumentRoutingConstants.ATTACHED_DOCUMENTS_PROPERTY_NAME); 244 ArrayList<DocumentRef> docRefs = new ArrayList<DocumentRef>(); 245 for (String id : ids) { 246 docRefs.add(new IdRef(id)); 247 } 248 return document.getCoreSession().getDocuments(docRefs.toArray(new DocumentRef[0])); 249 } 250 251 @Override 252 public String getAvailabilityFilter() { 253 try { 254 return (String) document.getPropertyValue(PROP_AVAILABILITY_FILTER); 255 } catch (PropertyException e) { 256 return null; 257 } 258 } 259 260 @Override 261 public boolean hasParentRoute() { 262 String parentRouteInstanceId = (String) document.getPropertyValue(PROP_PARENT_ROUTE); 263 return !StringUtils.isEmpty(parentRouteInstanceId); 264 } 265 266 @Override 267 public void resumeParentRoute(CoreSession session) { 268 DocumentRoutingService routing = Framework.getLocalService(DocumentRoutingService.class); 269 String parentRouteInstanceId = (String) document.getPropertyValue(PROP_PARENT_ROUTE); 270 String parentRouteNodeId = (String) document.getPropertyValue(PROP_PARENT_NODE); 271 routing.resumeInstance(parentRouteInstanceId, parentRouteNodeId, null, null, session); 272 } 273 274 @Override 275 public List<GraphNode> getSuspendedNodes() { 276 List<GraphNode> result = new ArrayList<GraphNode>(); 277 for (GraphNode node : getNodes()) { 278 if (State.SUSPENDED.equals(node.getState())) { 279 result.add(node); 280 } 281 } 282 return result; 283 } 284 285}