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