001/**
002 *
003 * Copyright 2018 Florian Schmaus
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *     http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.jivesoftware.smack.fsm;
018
019import java.io.PrintWriter;
020import java.lang.reflect.Constructor;
021import java.lang.reflect.InvocationTargetException;
022import java.util.ArrayList;
023import java.util.Collection;
024import java.util.Collections;
025import java.util.HashMap;
026import java.util.HashSet;
027import java.util.Iterator;
028import java.util.List;
029import java.util.Map;
030import java.util.Set;
031import java.util.logging.Logger;
032
033import org.jivesoftware.smack.c2s.ModularXmppClientToServerConnection.DisconnectedStateDescriptor;
034import org.jivesoftware.smack.c2s.internal.ModularXmppClientToServerConnectionInternal;
035import org.jivesoftware.smack.util.Consumer;
036import org.jivesoftware.smack.util.MultiMap;
037
038/**
039 * Smack's utility API for Finite State Machines (FSM).
040 *
041 * <p>
042 * Thanks to Andreas Fried for the fun and successful bug hunting session.
043 * </p>
044 *
045 * @author Florian Schmaus
046 *
047 */
048public class StateDescriptorGraph {
049
050    private static final Logger LOGGER = Logger.getLogger(StateDescriptorGraph.class.getName());
051
052    private static GraphVertex<StateDescriptor> addNewStateDescriptorGraphVertex(
053                    Class<? extends StateDescriptor> stateDescriptorClass,
054                    Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes)
055                    throws InstantiationException, IllegalAccessException, IllegalArgumentException,
056                    InvocationTargetException, NoSuchMethodException, SecurityException {
057        Constructor<? extends StateDescriptor> stateDescriptorConstructor = stateDescriptorClass.getDeclaredConstructor();
058        stateDescriptorConstructor.setAccessible(true);
059        StateDescriptor stateDescriptor = stateDescriptorConstructor.newInstance();
060        GraphVertex<StateDescriptor> graphVertexStateDescriptor = new GraphVertex<>(stateDescriptor);
061
062        GraphVertex<StateDescriptor> previous = graphVertexes.put(stateDescriptorClass, graphVertexStateDescriptor);
063        assert previous == null;
064
065        return graphVertexStateDescriptor;
066    }
067
068    private static final class HandleStateDescriptorGraphVertexContext {
069        private final Set<Class<? extends StateDescriptor>> handledStateDescriptors = new HashSet<>();
070        Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes;
071        MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges;
072
073        private HandleStateDescriptorGraphVertexContext(
074                        Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes,
075                        MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges) {
076            this.graphVertexes = graphVertexes;
077            this.inferredForwardEdges = inferredForwardEdges;
078        }
079
080        private boolean recurseInto(Class<? extends StateDescriptor> stateDescriptorClass) {
081            boolean wasAdded = handledStateDescriptors.add(stateDescriptorClass);
082            boolean alreadyHandled = !wasAdded;
083            return alreadyHandled;
084        }
085
086        private GraphVertex<StateDescriptor> getOrConstruct(Class<? extends StateDescriptor> stateDescriptorClass)
087                        throws InstantiationException, IllegalAccessException, IllegalArgumentException,
088                        InvocationTargetException, NoSuchMethodException, SecurityException {
089            GraphVertex<StateDescriptor> graphVertexStateDescriptor = graphVertexes.get(stateDescriptorClass);
090
091            if (graphVertexStateDescriptor == null) {
092                graphVertexStateDescriptor = addNewStateDescriptorGraphVertex(stateDescriptorClass, graphVertexes);
093
094                for (Class<? extends StateDescriptor> inferredSuccessor : inferredForwardEdges.getAll(
095                                stateDescriptorClass)) {
096                    graphVertexStateDescriptor.getElement().addSuccessor(inferredSuccessor);
097                }
098            }
099
100            return graphVertexStateDescriptor;
101        }
102    }
103
104    private static void handleStateDescriptorGraphVertex(GraphVertex<StateDescriptor> node,
105                    HandleStateDescriptorGraphVertexContext context)
106                    throws InstantiationException, IllegalAccessException, IllegalArgumentException, InvocationTargetException, NoSuchMethodException, SecurityException {
107        Class<? extends StateDescriptor> stateDescriptorClass = node.element.getClass();
108        boolean alreadyHandled = context.recurseInto(stateDescriptorClass);
109        if (alreadyHandled) {
110            return;
111        }
112
113        Set<Class<? extends StateDescriptor>> successorClasses = node.element.getSuccessors();
114        int numSuccessors = successorClasses.size();
115
116        Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> successorStateDescriptors = new HashMap<>(
117                        numSuccessors);
118        for (Class<? extends StateDescriptor> successorClass : successorClasses) {
119            GraphVertex<StateDescriptor> successorGraphNode = context.getOrConstruct(successorClass);
120            successorStateDescriptors.put(successorClass, successorGraphNode);
121        }
122
123        switch (numSuccessors) {
124        case 0:
125            throw new IllegalStateException("State " + stateDescriptorClass + " has no successor");
126        case 1:
127            GraphVertex<StateDescriptor> soleSuccessorNode = successorStateDescriptors.values().iterator().next();
128            node.addOutgoingEdge(soleSuccessorNode);
129            handleStateDescriptorGraphVertex(soleSuccessorNode, context);
130            return;
131        }
132
133        // We hit a state with multiple successors, perform a topological sort on the successors first.
134        // Process the information regarding subordinates and superiors states.
135
136        // The preference graph is the graph where the precedence information of all successors is stored, which we will
137        // topologically sort to find out which successor we should try first. It is a further new graph we use solely in
138        // this step for every node. The graph is represented as map. There is no special marker for the initial node
139        // as it is not required for the topological sort performed later.
140        Map<Class<? extends StateDescriptor>, GraphVertex<Class<? extends StateDescriptor>>> preferenceGraph = new HashMap<>(numSuccessors);
141
142        // Iterate over all successor states of the current state.
143        for (GraphVertex<StateDescriptor> successorStateDescriptorGraphNode : successorStateDescriptors.values()) {
144            StateDescriptor successorStateDescriptor = successorStateDescriptorGraphNode.element;
145            Class<? extends StateDescriptor> successorStateDescriptorClass = successorStateDescriptor.getClass();
146            for (Class<? extends StateDescriptor> subordinateClass : successorStateDescriptor.getSubordinates()) {
147                if (!successorClasses.contains(subordinateClass)) {
148                    LOGGER.severe(successorStateDescriptor + " points to a subordinate '" + subordinateClass + "' which is not part of the successor set");
149                    continue;
150                }
151
152                GraphVertex<Class<? extends StateDescriptor>> superiorClassNode = lookupAndCreateIfRequired(
153                                preferenceGraph, successorStateDescriptorClass);
154                GraphVertex<Class<? extends StateDescriptor>> subordinateClassNode = lookupAndCreateIfRequired(
155                                preferenceGraph, subordinateClass);
156
157                superiorClassNode.addOutgoingEdge(subordinateClassNode);
158            }
159            for (Class<? extends StateDescriptor> superiorClass : successorStateDescriptor.getSuperiors()) {
160                if (!successorClasses.contains(superiorClass)) {
161                    LOGGER.severe(successorStateDescriptor + " points to a superior '" + superiorClass
162                                    + "' which is not part of the successor set");
163                    continue;
164                }
165
166                GraphVertex<Class<? extends StateDescriptor>> subordinateClassNode = lookupAndCreateIfRequired(
167                                preferenceGraph, successorStateDescriptorClass);
168                GraphVertex<Class<? extends StateDescriptor>> superiorClassNode = lookupAndCreateIfRequired(
169                                preferenceGraph, superiorClass);
170
171                superiorClassNode.addOutgoingEdge(subordinateClassNode);
172            }
173        }
174
175        // Perform a topological sort which returns the state descriptor classes sorted by their priority. Highest
176        // priority state descriptors first.
177        List<GraphVertex<Class<? extends StateDescriptor>>> sortedSuccessors = topologicalSort(preferenceGraph.values());
178
179        // Handle the successor nodes which have not preference information available. Simply append them to the end of
180        // the sorted successor list.
181        outerloop: for (Class<? extends StateDescriptor> successorStateDescriptor : successorClasses) {
182            for (GraphVertex<Class<? extends StateDescriptor>> sortedSuccessor : sortedSuccessors) {
183                if (sortedSuccessor.getElement() == successorStateDescriptor) {
184                    continue outerloop;
185                }
186            }
187
188            sortedSuccessors.add(new GraphVertex<>(successorStateDescriptor));
189        }
190
191        for (GraphVertex<Class<? extends StateDescriptor>> successor : sortedSuccessors) {
192            GraphVertex<StateDescriptor> successorVertex = successorStateDescriptors.get(successor.element);
193            node.addOutgoingEdge(successorVertex);
194
195            // Recurse further.
196            handleStateDescriptorGraphVertex(successorVertex, context);
197        }
198    }
199
200    public static GraphVertex<StateDescriptor> constructStateDescriptorGraph(Set<Class<? extends StateDescriptor>> backwardEdgeStateDescriptors)
201                    throws InstantiationException, IllegalAccessException, IllegalArgumentException,
202                    InvocationTargetException, NoSuchMethodException, SecurityException {
203        Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes = new HashMap<>();
204
205        final Class<? extends StateDescriptor> initialStatedescriptorClass = DisconnectedStateDescriptor.class;
206        GraphVertex<StateDescriptor> initialNode = addNewStateDescriptorGraphVertex(initialStatedescriptorClass, graphVertexes);
207
208        MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges = new MultiMap<>();
209        for (Class<? extends StateDescriptor> backwardsEdge : backwardEdgeStateDescriptors) {
210            GraphVertex<StateDescriptor> graphVertexStateDescriptor = addNewStateDescriptorGraphVertex(backwardsEdge, graphVertexes);
211
212            for (Class<? extends StateDescriptor> predecessor : graphVertexStateDescriptor.getElement().getPredeccessors()) {
213                inferredForwardEdges.put(predecessor, backwardsEdge);
214            }
215        }
216        // Ensure that the intial node has their successors inferred.
217        for (Class<? extends StateDescriptor> inferredSuccessorOfInitialStateDescriptor : inferredForwardEdges.getAll(initialStatedescriptorClass)) {
218            initialNode.getElement().addSuccessor(inferredSuccessorOfInitialStateDescriptor);
219        }
220
221        HandleStateDescriptorGraphVertexContext context = new HandleStateDescriptorGraphVertexContext(graphVertexes, inferredForwardEdges);
222        handleStateDescriptorGraphVertex(initialNode, context);
223
224        return initialNode;
225    }
226
227    private static GraphVertex<State> convertToStateGraph(GraphVertex<StateDescriptor> stateDescriptorVertex,
228                    ModularXmppClientToServerConnectionInternal connectionInternal, Map<StateDescriptor, GraphVertex<State>> handledStateDescriptors) {
229        StateDescriptor stateDescriptor = stateDescriptorVertex.getElement();
230        GraphVertex<State> stateVertex = handledStateDescriptors.get(stateDescriptor);
231        if (stateVertex != null) {
232            return stateVertex;
233        }
234
235        State state = stateDescriptor.constructState(connectionInternal);
236        stateVertex = new GraphVertex<>(state);
237        handledStateDescriptors.put(stateDescriptor, stateVertex);
238        for (GraphVertex<StateDescriptor> successorStateDescriptorVertex : stateDescriptorVertex.getOutgoingEdges()) {
239            GraphVertex<State> successorStateVertex = convertToStateGraph(successorStateDescriptorVertex, connectionInternal, handledStateDescriptors);
240            // It is important that we keep the order of the edges. This should do it.
241            stateVertex.addOutgoingEdge(successorStateVertex);
242        }
243
244        return stateVertex;
245    }
246
247    public static GraphVertex<State> convertToStateGraph(GraphVertex<StateDescriptor> initialStateDescriptor,
248                    ModularXmppClientToServerConnectionInternal connectionInternal) {
249        Map<StateDescriptor, GraphVertex<State>> handledStateDescriptors = new HashMap<>();
250        GraphVertex<State> initialState = convertToStateGraph(initialStateDescriptor, connectionInternal,
251                        handledStateDescriptors);
252        return initialState;
253    }
254
255    // Graph API after here.
256    // This API could possibly factored out into an extra package/class, but then we will probably need a builder for
257    // the graph vertex in order to keep it immutable.
258    public static final class GraphVertex<E> {
259        private final E element;
260        private final List<GraphVertex<E>> outgoingEdges = new ArrayList<>();
261
262        private VertexColor color = VertexColor.white;
263
264        private GraphVertex(E element) {
265            this.element = element;
266        }
267
268        private void addOutgoingEdge(GraphVertex<E> vertex) {
269            assert vertex != null;
270            if (outgoingEdges.contains(vertex)) {
271                throw new IllegalArgumentException("This " + this + " already has an outgoing edge to " + vertex);
272            }
273            outgoingEdges.add(vertex);
274        }
275
276        public E getElement() {
277            return element;
278        }
279
280        public List<GraphVertex<E>> getOutgoingEdges() {
281            return Collections.unmodifiableList(outgoingEdges);
282        }
283
284        private enum VertexColor {
285            white,
286            grey,
287            black,
288        }
289
290        @Override
291        public String toString() {
292            return toString(true);
293        }
294
295        public String toString(boolean includeOutgoingEdges) {
296            StringBuilder sb = new StringBuilder();
297            sb.append("GraphVertex " + element + " [color=" + color
298                            + ", identityHashCode=" + System.identityHashCode(this)
299                            + ", outgoingEdgeCount=" + outgoingEdges.size());
300
301            if (includeOutgoingEdges) {
302                sb.append(", outgoingEdges={");
303
304                for (Iterator<GraphVertex<E>> it = outgoingEdges.iterator(); it.hasNext();) {
305                    GraphVertex<E> outgoingEdgeVertex = it.next();
306                    sb.append(outgoingEdgeVertex.toString(false));
307                    if (it.hasNext()) {
308                        sb.append(", ");
309                    }
310                }
311                sb.append('}');
312            }
313
314            sb.append(']');
315            return sb.toString();
316        }
317    }
318
319    private static GraphVertex<Class<? extends StateDescriptor>> lookupAndCreateIfRequired(
320                    Map<Class<? extends StateDescriptor>, GraphVertex<Class<? extends StateDescriptor>>> map,
321                    Class<? extends StateDescriptor> clazz) {
322        GraphVertex<Class<? extends StateDescriptor>> vertex = map.get(clazz);
323        if (vertex == null) {
324            vertex = new GraphVertex<>(clazz);
325            map.put(clazz, vertex);
326        }
327        return vertex;
328    }
329
330    private static <E> List<GraphVertex<E>> topologicalSort(Collection<GraphVertex<E>> vertexes) {
331        List<GraphVertex<E>> res = new ArrayList<>();
332        dfs(vertexes, vertex -> res.add(0, vertex), null);
333        return res;
334    }
335
336    private static <E> void dfsVisit(GraphVertex<E> vertex, Consumer<GraphVertex<E>> dfsFinishedVertex,
337                    DfsEdgeFound<E> dfsEdgeFound) {
338        vertex.color = GraphVertex.VertexColor.grey;
339
340        final int totalEdgeCount = vertex.getOutgoingEdges().size();
341
342        int edgeCount = 0;
343
344        for (GraphVertex<E> successorVertex : vertex.getOutgoingEdges()) {
345            edgeCount++;
346            if (dfsEdgeFound != null) {
347                dfsEdgeFound.onEdgeFound(vertex, successorVertex, edgeCount, totalEdgeCount);
348            }
349            if (successorVertex.color == GraphVertex.VertexColor.white) {
350                dfsVisit(successorVertex, dfsFinishedVertex, dfsEdgeFound);
351            }
352        }
353
354        vertex.color = GraphVertex.VertexColor.black;
355        if (dfsFinishedVertex != null) {
356            dfsFinishedVertex.accept(vertex);
357        }
358    }
359
360    private static <E> void dfs(Collection<GraphVertex<E>> vertexes, Consumer<GraphVertex<E>> dfsFinishedVertex,
361                    DfsEdgeFound<E> dfsEdgeFound) {
362        for (GraphVertex<E> vertex : vertexes) {
363            if (vertex.color == GraphVertex.VertexColor.white) {
364                dfsVisit(vertex, dfsFinishedVertex, dfsEdgeFound);
365            }
366        }
367    }
368
369    public static <E> void stateDescriptorGraphToDot(Collection<GraphVertex<StateDescriptor>> vertexes,
370                    PrintWriter dotOut, boolean breakStateName) {
371        dotOut.append("digraph {\n");
372        dfs(vertexes,
373                finishedVertex -> {
374                   boolean isMultiVisitState = finishedVertex.element.isMultiVisitState();
375                   boolean isFinalState = finishedVertex.element.isFinalState();
376                   boolean isNotImplemented = finishedVertex.element.isNotImplemented();
377
378                   String style = null;
379                   if (isMultiVisitState) {
380                       style = "bold";
381                   } else if (isFinalState) {
382                       style = "filled";
383                   } else if (isNotImplemented) {
384                       style = "dashed";
385                   }
386
387                   if (style == null) {
388                       return;
389                   }
390
391                   dotOut.append('"')
392                       .append(finishedVertex.element.getFullStateName(breakStateName))
393                       .append("\" [ ")
394                       .append("style=")
395                       .append(style)
396                       .append(" ]\n");
397               },
398               (from, to, edgeId, totalEdgeCount) -> {
399                   dotOut.append("  \"")
400                       .append(from.element.getFullStateName(breakStateName))
401                       .append("\" -> \"")
402                       .append(to.element.getFullStateName(breakStateName))
403                       .append('"');
404                   if (totalEdgeCount > 1) {
405                       // Note that 'dot' requires *double* quotes to enclose the value.
406                       dotOut.append(" [xlabel=\"")
407                       .append(Integer.toString(edgeId))
408                       .append("\"]");
409                   }
410                   dotOut.append(";\n");
411               });
412        dotOut.append("}\n");
413    }
414
415    private interface DfsEdgeFound<E> {
416        void onEdgeFound(GraphVertex<E> from, GraphVertex<E> to, int edgeId, int totalEdgeCount);
417    }
418}