Source code

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