Source code

001/*
002 * (C) Copyright 2012-2018 Nuxeo (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.lang3.StringUtils;
034import org.apache.commons.lang3.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<>(children.size());
088        nodesById = new HashMap<>();
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<>();
137        Deque<Deque<String>> stack = new LinkedList<>();
138        Deque<String> first = new LinkedList<>();
139        first.add(startNodeId);
140        stack.push(first);
141        Set<String> done = new HashSet<>();
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<>();
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<>();
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<>();
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<>();
245        for (String id : ids) {
246            IdRef idRef = new IdRef(id);
247            if (document.getCoreSession().exists(idRef)) {
248                docRefs.add(idRef);
249            }
250        }
251        return document.getCoreSession().getDocuments(docRefs.toArray(new DocumentRef[0]));
252    }
253
254    @Override
255    public String getAvailabilityFilter() {
256        try {
257            return (String) document.getPropertyValue(PROP_AVAILABILITY_FILTER);
258        } catch (PropertyException e) {
259            return null;
260        }
261    }
262
263    @Override
264    public boolean hasParentRoute() {
265        String parentRouteInstanceId = (String) document.getPropertyValue(PROP_PARENT_ROUTE);
266        return !StringUtils.isEmpty(parentRouteInstanceId);
267    }
268
269    @Override
270    public void resumeParentRoute(CoreSession session) {
271        DocumentRoutingService routing = Framework.getService(DocumentRoutingService.class);
272        String parentRouteInstanceId = (String) document.getPropertyValue(PROP_PARENT_ROUTE);
273        String parentRouteNodeId = (String) document.getPropertyValue(PROP_PARENT_NODE);
274        routing.resumeInstance(parentRouteInstanceId, parentRouteNodeId, null, null, session);
275    }
276
277    @Override
278    public List<GraphNode> getSuspendedNodes() {
279        List<GraphNode> result = new ArrayList<>();
280        for (GraphNode node : getNodes()) {
281            if (State.SUSPENDED.equals(node.getState())) {
282                result.add(node);
283            }
284        }
285        return result;
286    }
287
288}