StateDescriptorGraph.java
- /**
- *
- * Copyright 2018-2021 Florian Schmaus
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
- package org.jivesoftware.smack.fsm;
- import java.io.PrintWriter;
- import java.lang.reflect.Constructor;
- import java.lang.reflect.InvocationTargetException;
- import java.util.ArrayList;
- import java.util.Collection;
- import java.util.Collections;
- import java.util.HashMap;
- import java.util.HashSet;
- import java.util.Iterator;
- import java.util.List;
- import java.util.Map;
- import java.util.Set;
- import org.jivesoftware.smack.c2s.ModularXmppClientToServerConnection.DisconnectedStateDescriptor;
- import org.jivesoftware.smack.c2s.internal.ModularXmppClientToServerConnectionInternal;
- import org.jivesoftware.smack.util.Consumer;
- import org.jivesoftware.smack.util.MultiMap;
- /**
- * Smack's utility API for Finite State Machines (FSM).
- *
- * <p>
- * Thanks to Andreas Fried for the fun and successful bug hunting session.
- * </p>
- *
- * @author Florian Schmaus
- *
- */
- public class StateDescriptorGraph {
- private static GraphVertex<StateDescriptor> addNewStateDescriptorGraphVertex(
- Class<? extends StateDescriptor> stateDescriptorClass,
- Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes)
- throws InstantiationException, IllegalAccessException, IllegalArgumentException,
- InvocationTargetException, NoSuchMethodException, SecurityException {
- Constructor<? extends StateDescriptor> stateDescriptorConstructor = stateDescriptorClass.getDeclaredConstructor();
- stateDescriptorConstructor.setAccessible(true);
- StateDescriptor stateDescriptor = stateDescriptorConstructor.newInstance();
- GraphVertex<StateDescriptor> graphVertexStateDescriptor = new GraphVertex<>(stateDescriptor);
- GraphVertex<StateDescriptor> previous = graphVertexes.put(stateDescriptorClass, graphVertexStateDescriptor);
- assert previous == null;
- return graphVertexStateDescriptor;
- }
- private static final class HandleStateDescriptorGraphVertexContext {
- private final Set<Class<? extends StateDescriptor>> handledStateDescriptors = new HashSet<>();
- Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes;
- MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges;
- private HandleStateDescriptorGraphVertexContext(
- Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes,
- MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges) {
- this.graphVertexes = graphVertexes;
- this.inferredForwardEdges = inferredForwardEdges;
- }
- private boolean recurseInto(Class<? extends StateDescriptor> stateDescriptorClass) {
- boolean wasAdded = handledStateDescriptors.add(stateDescriptorClass);
- boolean alreadyHandled = !wasAdded;
- return alreadyHandled;
- }
- private GraphVertex<StateDescriptor> getOrConstruct(Class<? extends StateDescriptor> stateDescriptorClass)
- throws InstantiationException, IllegalAccessException, IllegalArgumentException,
- InvocationTargetException, NoSuchMethodException, SecurityException {
- GraphVertex<StateDescriptor> graphVertexStateDescriptor = graphVertexes.get(stateDescriptorClass);
- if (graphVertexStateDescriptor == null) {
- graphVertexStateDescriptor = addNewStateDescriptorGraphVertex(stateDescriptorClass, graphVertexes);
- for (Class<? extends StateDescriptor> inferredSuccessor : inferredForwardEdges.getAll(
- stateDescriptorClass)) {
- graphVertexStateDescriptor.getElement().addSuccessor(inferredSuccessor);
- }
- }
- return graphVertexStateDescriptor;
- }
- }
- private static void handleStateDescriptorGraphVertex(GraphVertex<StateDescriptor> node,
- HandleStateDescriptorGraphVertexContext context,
- boolean failOnUnknownStates)
- throws InstantiationException, IllegalAccessException, IllegalArgumentException, InvocationTargetException, NoSuchMethodException, SecurityException {
- Class<? extends StateDescriptor> stateDescriptorClass = node.element.getClass();
- boolean alreadyHandled = context.recurseInto(stateDescriptorClass);
- if (alreadyHandled) {
- return;
- }
- Set<Class<? extends StateDescriptor>> successorClasses = node.element.getSuccessors();
- int numSuccessors = successorClasses.size();
- Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> successorStateDescriptors = new HashMap<>(
- numSuccessors);
- for (Class<? extends StateDescriptor> successorClass : successorClasses) {
- GraphVertex<StateDescriptor> successorGraphNode = context.getOrConstruct(successorClass);
- successorStateDescriptors.put(successorClass, successorGraphNode);
- }
- switch (numSuccessors) {
- case 0:
- throw new IllegalStateException("State " + stateDescriptorClass + " has no successor");
- case 1:
- GraphVertex<StateDescriptor> soleSuccessorNode = successorStateDescriptors.values().iterator().next();
- node.addOutgoingEdge(soleSuccessorNode);
- handleStateDescriptorGraphVertex(soleSuccessorNode, context, failOnUnknownStates);
- return;
- }
- // We hit a state with multiple successors, perform a topological sort on the successors first.
- // Process the information regarding subordinates and superiors states.
- // The preference graph is the graph where the precedence information of all successors is stored, which we will
- // topologically sort to find out which successor we should try first. It is a further new graph we use solely in
- // this step for every node. The graph is represented as map. There is no special marker for the initial node
- // as it is not required for the topological sort performed later.
- Map<Class<? extends StateDescriptor>, GraphVertex<Class<? extends StateDescriptor>>> preferenceGraph = new HashMap<>(numSuccessors);
- // Iterate over all successor states of the current state.
- for (GraphVertex<StateDescriptor> successorStateDescriptorGraphNode : successorStateDescriptors.values()) {
- StateDescriptor successorStateDescriptor = successorStateDescriptorGraphNode.element;
- Class<? extends StateDescriptor> successorStateDescriptorClass = successorStateDescriptor.getClass();
- for (Class<? extends StateDescriptor> subordinateClass : successorStateDescriptor.getSubordinates()) {
- if (failOnUnknownStates && !successorClasses.contains(subordinateClass)) {
- throw new IllegalStateException(successorStateDescriptor + " points to a subordinate '" + subordinateClass + "' which is not part of the successor set");
- }
- GraphVertex<Class<? extends StateDescriptor>> superiorClassNode = lookupAndCreateIfRequired(
- preferenceGraph, successorStateDescriptorClass);
- GraphVertex<Class<? extends StateDescriptor>> subordinateClassNode = lookupAndCreateIfRequired(
- preferenceGraph, subordinateClass);
- superiorClassNode.addOutgoingEdge(subordinateClassNode);
- }
- for (Class<? extends StateDescriptor> superiorClass : successorStateDescriptor.getSuperiors()) {
- if (failOnUnknownStates && !successorClasses.contains(superiorClass)) {
- throw new IllegalStateException(successorStateDescriptor + " points to a superior '" + superiorClass
- + "' which is not part of the successor set");
- }
- GraphVertex<Class<? extends StateDescriptor>> subordinateClassNode = lookupAndCreateIfRequired(
- preferenceGraph, successorStateDescriptorClass);
- GraphVertex<Class<? extends StateDescriptor>> superiorClassNode = lookupAndCreateIfRequired(
- preferenceGraph, superiorClass);
- superiorClassNode.addOutgoingEdge(subordinateClassNode);
- }
- }
- // Perform a topological sort which returns the state descriptor classes sorted by their priority. Highest
- // priority state descriptors first.
- List<GraphVertex<Class<? extends StateDescriptor>>> sortedSuccessors = topologicalSort(preferenceGraph.values());
- // Handle the successor nodes which have not preference information available. Simply append them to the end of
- // the sorted successor list.
- outerloop: for (Class<? extends StateDescriptor> successorStateDescriptor : successorClasses) {
- for (GraphVertex<Class<? extends StateDescriptor>> sortedSuccessor : sortedSuccessors) {
- if (sortedSuccessor.getElement() == successorStateDescriptor) {
- continue outerloop;
- }
- }
- sortedSuccessors.add(new GraphVertex<>(successorStateDescriptor));
- }
- for (GraphVertex<Class<? extends StateDescriptor>> successor : sortedSuccessors) {
- GraphVertex<StateDescriptor> successorVertex = successorStateDescriptors.get(successor.element);
- if (successorVertex == null) {
- // The successor does not exist, probably because its module was not enabled.
- continue;
- }
- node.addOutgoingEdge(successorVertex);
- // Recurse further.
- handleStateDescriptorGraphVertex(successorVertex, context, failOnUnknownStates);
- }
- }
- public static GraphVertex<StateDescriptor> constructStateDescriptorGraph(
- Set<Class<? extends StateDescriptor>> backwardEdgeStateDescriptors,
- boolean failOnUnknownStates)
- throws InstantiationException, IllegalAccessException, IllegalArgumentException,
- InvocationTargetException, NoSuchMethodException, SecurityException {
- Map<Class<? extends StateDescriptor>, GraphVertex<StateDescriptor>> graphVertexes = new HashMap<>();
- final Class<? extends StateDescriptor> initialStatedescriptorClass = DisconnectedStateDescriptor.class;
- GraphVertex<StateDescriptor> initialNode = addNewStateDescriptorGraphVertex(initialStatedescriptorClass, graphVertexes);
- MultiMap<Class<? extends StateDescriptor>, Class<? extends StateDescriptor>> inferredForwardEdges = new MultiMap<>();
- for (Class<? extends StateDescriptor> backwardsEdge : backwardEdgeStateDescriptors) {
- GraphVertex<StateDescriptor> graphVertexStateDescriptor = addNewStateDescriptorGraphVertex(backwardsEdge, graphVertexes);
- for (Class<? extends StateDescriptor> predecessor : graphVertexStateDescriptor.getElement().getPredeccessors()) {
- inferredForwardEdges.put(predecessor, backwardsEdge);
- }
- }
- // Ensure that the initial node has their successors inferred.
- for (Class<? extends StateDescriptor> inferredSuccessorOfInitialStateDescriptor : inferredForwardEdges.getAll(initialStatedescriptorClass)) {
- initialNode.getElement().addSuccessor(inferredSuccessorOfInitialStateDescriptor);
- }
- HandleStateDescriptorGraphVertexContext context = new HandleStateDescriptorGraphVertexContext(graphVertexes, inferredForwardEdges);
- handleStateDescriptorGraphVertex(initialNode, context, failOnUnknownStates);
- return initialNode;
- }
- private static GraphVertex<State> convertToStateGraph(GraphVertex<StateDescriptor> stateDescriptorVertex,
- ModularXmppClientToServerConnectionInternal connectionInternal, Map<StateDescriptor, GraphVertex<State>> handledStateDescriptors) {
- StateDescriptor stateDescriptor = stateDescriptorVertex.getElement();
- GraphVertex<State> stateVertex = handledStateDescriptors.get(stateDescriptor);
- if (stateVertex != null) {
- return stateVertex;
- }
- State state = stateDescriptor.constructState(connectionInternal);
- stateVertex = new GraphVertex<>(state);
- handledStateDescriptors.put(stateDescriptor, stateVertex);
- for (GraphVertex<StateDescriptor> successorStateDescriptorVertex : stateDescriptorVertex.getOutgoingEdges()) {
- GraphVertex<State> successorStateVertex = convertToStateGraph(successorStateDescriptorVertex, connectionInternal, handledStateDescriptors);
- // It is important that we keep the order of the edges. This should do it.
- stateVertex.addOutgoingEdge(successorStateVertex);
- }
- return stateVertex;
- }
- public static GraphVertex<State> convertToStateGraph(GraphVertex<StateDescriptor> initialStateDescriptor,
- ModularXmppClientToServerConnectionInternal connectionInternal) {
- Map<StateDescriptor, GraphVertex<State>> handledStateDescriptors = new HashMap<>();
- GraphVertex<State> initialState = convertToStateGraph(initialStateDescriptor, connectionInternal,
- handledStateDescriptors);
- return initialState;
- }
- // Graph API after here.
- // This API could possibly factored out into an extra package/class, but then we will probably need a builder for
- // the graph vertex in order to keep it immutable.
- public static final class GraphVertex<E> {
- private final E element;
- private final List<GraphVertex<E>> outgoingEdges = new ArrayList<>();
- private VertexColor color = VertexColor.white;
- private GraphVertex(E element) {
- this.element = element;
- }
- private void addOutgoingEdge(GraphVertex<E> vertex) {
- assert vertex != null;
- if (outgoingEdges.contains(vertex)) {
- throw new IllegalArgumentException("This " + this + " already has an outgoing edge to " + vertex);
- }
- outgoingEdges.add(vertex);
- }
- public E getElement() {
- return element;
- }
- public List<GraphVertex<E>> getOutgoingEdges() {
- return Collections.unmodifiableList(outgoingEdges);
- }
- private enum VertexColor {
- white,
- grey,
- black,
- }
- @Override
- public String toString() {
- return toString(true);
- }
- public String toString(boolean includeOutgoingEdges) {
- StringBuilder sb = new StringBuilder();
- sb.append("GraphVertex " + element + " [color=" + color
- + ", identityHashCode=" + System.identityHashCode(this)
- + ", outgoingEdgeCount=" + outgoingEdges.size());
- if (includeOutgoingEdges) {
- sb.append(", outgoingEdges={");
- for (Iterator<GraphVertex<E>> it = outgoingEdges.iterator(); it.hasNext();) {
- GraphVertex<E> outgoingEdgeVertex = it.next();
- sb.append(outgoingEdgeVertex.toString(false));
- if (it.hasNext()) {
- sb.append(", ");
- }
- }
- sb.append('}');
- }
- sb.append(']');
- return sb.toString();
- }
- }
- private static GraphVertex<Class<? extends StateDescriptor>> lookupAndCreateIfRequired(
- Map<Class<? extends StateDescriptor>, GraphVertex<Class<? extends StateDescriptor>>> map,
- Class<? extends StateDescriptor> clazz) {
- GraphVertex<Class<? extends StateDescriptor>> vertex = map.get(clazz);
- if (vertex == null) {
- vertex = new GraphVertex<>(clazz);
- map.put(clazz, vertex);
- }
- return vertex;
- }
- private static <E> List<GraphVertex<E>> topologicalSort(Collection<GraphVertex<E>> vertexes) {
- List<GraphVertex<E>> res = new ArrayList<>();
- dfs(vertexes, vertex -> res.add(0, vertex), null);
- return res;
- }
- private static <E> void dfsVisit(GraphVertex<E> vertex, Consumer<GraphVertex<E>> dfsFinishedVertex,
- DfsEdgeFound<E> dfsEdgeFound) {
- vertex.color = GraphVertex.VertexColor.grey;
- final int totalEdgeCount = vertex.getOutgoingEdges().size();
- int edgeCount = 0;
- for (GraphVertex<E> successorVertex : vertex.getOutgoingEdges()) {
- edgeCount++;
- if (dfsEdgeFound != null) {
- dfsEdgeFound.onEdgeFound(vertex, successorVertex, edgeCount, totalEdgeCount);
- }
- if (successorVertex.color == GraphVertex.VertexColor.white) {
- dfsVisit(successorVertex, dfsFinishedVertex, dfsEdgeFound);
- }
- }
- vertex.color = GraphVertex.VertexColor.black;
- if (dfsFinishedVertex != null) {
- dfsFinishedVertex.accept(vertex);
- }
- }
- private static <E> void dfs(Collection<GraphVertex<E>> vertexes, Consumer<GraphVertex<E>> dfsFinishedVertex,
- DfsEdgeFound<E> dfsEdgeFound) {
- for (GraphVertex<E> vertex : vertexes) {
- if (vertex.color == GraphVertex.VertexColor.white) {
- dfsVisit(vertex, dfsFinishedVertex, dfsEdgeFound);
- }
- }
- }
- public static <E> void stateDescriptorGraphToDot(Collection<GraphVertex<StateDescriptor>> vertexes,
- PrintWriter dotOut, boolean breakStateName) {
- dotOut.append("digraph {\n");
- dfs(vertexes,
- finishedVertex -> {
- boolean isMultiVisitState = finishedVertex.element.isMultiVisitState();
- boolean isFinalState = finishedVertex.element.isFinalState();
- boolean isNotImplemented = finishedVertex.element.isNotImplemented();
- String style = null;
- if (isMultiVisitState) {
- style = "bold";
- } else if (isFinalState) {
- style = "filled";
- } else if (isNotImplemented) {
- style = "dashed";
- }
- if (style == null) {
- return;
- }
- dotOut.append('"')
- .append(finishedVertex.element.getFullStateName(breakStateName))
- .append("\" [ ")
- .append("style=")
- .append(style)
- .append(" ]\n");
- },
- (from, to, edgeId, totalEdgeCount) -> {
- dotOut.append(" \"")
- .append(from.element.getFullStateName(breakStateName))
- .append("\" -> \"")
- .append(to.element.getFullStateName(breakStateName))
- .append('"');
- if (totalEdgeCount > 1) {
- // Note that 'dot' requires *double* quotes to enclose the value.
- dotOut.append(" [xlabel=\"")
- .append(Integer.toString(edgeId))
- .append("\"]");
- }
- dotOut.append(";\n");
- });
- dotOut.append("}\n");
- }
- private interface DfsEdgeFound<E> {
- void onEdgeFound(GraphVertex<E> from, GraphVertex<E> to, int edgeId, int totalEdgeCount);
- }
- }