1 /* 2 * Copyright (c) 2018 Helmut Neemann 3 * Use of this source code is governed by the GPL v3 license 4 * that can be found in the LICENSE file. 5 */ 6 package de.neemann.digital.analyse; 7 8 import de.neemann.digital.core.*; 9 import de.neemann.digital.core.switching.Switch; 10 import de.neemann.digital.core.wiring.bus.CommonBusValue; 11 import de.neemann.digital.draw.elements.PinException; 12 import de.neemann.digital.lang.Lang; 13 14 import java.util.ArrayList; 15 import java.util.Collection; 16 import java.util.HashMap; 17 import java.util.HashSet; 18 19 /** 20 * Helper to check a circuit for cycles. 21 * A cycle is a situation where a gate input depends somehow on one of its outputs. 22 * If a cycle is detected an exception is thrown. 23 * A cycle is no problem during simulation due to the gate delay. 24 * However, when analyzing a circuit with an unbuffered cycle, erroneous truth tables 25 * may result. Therefore, an exception is thrown when such a circuit is analyzed. 26 */ 27 public final class CycleDetector { 28 CycleDetector()29 private CycleDetector() { 30 } 31 32 /** 33 * Checks a circuit for cycles 34 * If a cycle is detected, en exception is thrown. 35 * 36 * @param values the input signals of the circuit 37 * @throws BacktrackException BacktrackException 38 * @throws PinException PinException 39 * @throws CycleException is thrown if a cycle is detected 40 */ checkForCycles(ArrayList<Signal> values)41 public static void checkForCycles(ArrayList<Signal> values) throws BacktrackException, PinException, CycleException { 42 HashMap<NodeInterface, Node> nodes = new HashMap<>(); 43 HashSet<ObservableValue> visited = new HashSet<>(); 44 45 for (Signal s : values) { 46 Node root = new Node(null); 47 root.layer = 1; 48 traverse(root, s.getValue(), nodes, visited); 49 } 50 51 // Turned of for now because if it is used you can build circuits with a state 52 // which are not detected as such. 53 //removeSwitchCycles(nodes.values()); 54 55 checkGraphForCycles(nodes.values()); 56 } 57 traverse(Node parent, ObservableValue val, HashMap<NodeInterface, Node> nodes, HashSet<ObservableValue> visited)58 private static void traverse(Node parent, ObservableValue val, HashMap<NodeInterface, Node> nodes, HashSet<ObservableValue> visited) throws PinException, BacktrackException { 59 visited.add(val); 60 for (Observer o : val.getObservers()) { 61 if ((o instanceof NodeInterface)) { 62 63 NodeInterface no = (NodeInterface) o; 64 Node child = nodes.computeIfAbsent(no, Node::new); 65 child.addParent(parent); 66 67 ObservableValues outputs = ((NodeInterface) o).getOutputs(); 68 for (ObservableValue co : outputs) 69 if (!visited.contains(co)) 70 traverse(child, co, nodes, visited); 71 72 } else 73 throw new BacktrackException(Lang.get("err_backtrackOf_N_isImpossible", o.getClass().getSimpleName())); 74 } 75 } 76 77 78 private static final class Node { 79 private final NodeInterface ni; 80 private final ArrayList<Node> parents; 81 private int layer; 82 Node(NodeInterface ni)83 private Node(NodeInterface ni) { 84 this.parents = new ArrayList<>(); 85 this.ni = ni; 86 } 87 addParent(Node parent)88 private void addParent(Node parent) { 89 parents.add(parent); 90 } 91 92 @Override toString()93 public String toString() { 94 return ni.toString(); 95 } 96 } 97 98 /** 99 * Calling this method allows analysis of nmos/cmos circuits because switch cycles are removed. 100 * But if this method is called, a cycle which contains a switch in the fed back is not 101 * detected anymore. 102 * 103 * @param nodes the node to analyse 104 */ removeSwitchCycles(Collection<Node> nodes)105 private static void removeSwitchCycles(Collection<Node> nodes) { 106 for (Node n : nodes) 107 if (n.ni instanceof CommonBusValue) 108 for (Node p : n.parents) 109 if (p.ni instanceof Switch) 110 p.parents.removeIf(node -> node == n); 111 } 112 checkGraphForCycles(Collection<Node> nodes)113 private static void checkGraphForCycles(Collection<Node> nodes) throws CycleException { 114 ArrayList<Node> remaining = new ArrayList<>(nodes); 115 116 int layer = 1; 117 while (!remaining.isEmpty()) { 118 layer++; 119 ArrayList<Node> ableToPlace = new ArrayList<>(); 120 for (Node node : remaining) { 121 boolean nodeOk = true; 122 for (Node p : node.parents) 123 if (p.layer == 0) { 124 nodeOk = false; 125 break; 126 } 127 if (nodeOk) { 128 ableToPlace.add(node); 129 node.layer = layer; 130 } 131 } 132 133 if (ableToPlace.isEmpty()) 134 throw new CycleException(); 135 136 remaining.removeAll(ableToPlace); 137 } 138 } 139 140 final static class CycleException extends AnalyseException { CycleException()141 private CycleException() { 142 super(Lang.get("err_circuitHasCycles")); 143 } 144 } 145 } 146