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}