6763327895

Committed 05 Nov 2023 07:29PM UTC coverage: 89.726% (-0.1%) from 89.868%

Build # 6763327895

Build Type

push

github

Committed by

mtf90

Commit Message

fix typo

Run Details

4 of 4 new or added lines in 4 files covered. (100.0%)

99 existing lines in 18 files now uncovered.

15677 of 17472 relevant lines covered (89.73%)

1.66 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.1

/incremental/src/main/java/net/automatalib/incremental/moore/tree/IncrementalMooreTreeBuilder.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of AutomataLib, http://www.automatalib.net/.
 *
 * 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 net.automatalib.incremental.moore.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Objects;

import com.google.common.collect.Iterators;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.alphabet.Alphabets;
import net.automatalib.automaton.graph.TransitionEdge;
import net.automatalib.automaton.transducer.MooreMachine;
import net.automatalib.automaton.transducer.MooreMachine.MooreGraphView;
import net.automatalib.automaton.visualization.MooreVisualizationHelper;
import net.automatalib.common.util.mapping.MapMapping;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.graph.Graph;
import net.automatalib.incremental.ConflictException;
import net.automatalib.incremental.moore.IncrementalMooreBuilder;
import net.automatalib.ts.output.MooreTransitionSystem;
import net.automatalib.util.ts.traversal.TSTraversal;
import net.automatalib.visualization.VisualizationHelper;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Incrementally builds a (tree-based) Moore machine from a set of input and corresponding output words.
 *
 * @param <I>
 *         input symbol class
 * @param <O>
 *         output symbol class
 */
public class IncrementalMooreTreeBuilder<I, O> implements IncrementalMooreBuilder<I, O> {

    private final Alphabet<I> alphabet;
    private int alphabetSize;
    private @Nullable Node<O> root;

    public IncrementalMooreTreeBuilder(Alphabet<I> alphabet) {
        this.alphabet = alphabet;
        this.alphabetSize = alphabet.size();
    }

    @Override
    public void addAlphabetSymbol(I symbol) {
        if (!this.alphabet.containsSymbol(symbol)) {
            Alphabets.toGrowingAlphabetOrThrowException(this.alphabet).addSymbol(symbol);
        }

        final int newAlphabetSize = this.alphabet.size();
        // even if the symbol was already in the alphabet, we need to make sure to be able to store the new symbol
        if (alphabetSize < newAlphabetSize && root != null) {
            ensureInputCapacity(root, alphabetSize, newAlphabetSize);
        }
        alphabetSize = newAlphabetSize;
    }

    private void ensureInputCapacity(Node<O> node, int oldAlphabetSize, int newAlphabetSize) {
        node.ensureInputCapacity(newAlphabetSize);
        for (int i = 0; i < oldAlphabetSize; i++) {
            final Node<O> child = node.getChild(i);
            if (child != null) {
                ensureInputCapacity(child, oldAlphabetSize, newAlphabetSize);
            }
        }
    }

    @Override
    public @Nullable Word<I> findSeparatingWord(MooreMachine<?, I, ?, O> target,
                                                Collection<? extends I> inputs,
                                                boolean omitUndefined) {
        return doFindSeparatingWord(target, inputs, omitUndefined);
    }

    private <S, T> @Nullable Word<I> doFindSeparatingWord(MooreMachine<S, I, T, O> target,
                                                          Collection<? extends I> inputs,
                                                          boolean omitUndefined) {
        S init2 = target.getInitialState();

        if (root == null && init2 == null) {
            return null;
        } else if (root == null || init2 == null) {
            return omitUndefined ? null : Word.epsilon();
        }

        if (!Objects.equals(root.getOutput(), target.getStateOutput(init2))) {
            return Word.epsilon();
        }

        // incomingInput can be null here, because we will always skip the bottom stack element below
        @SuppressWarnings("nullness")
        Record<@Nullable S, I, O> init = new Record<>(init2, root, null, inputs.iterator());

        Deque<Record<@Nullable S, I, O>> dfsStack = new ArrayDeque<>();
        dfsStack.push(init);

        while (!dfsStack.isEmpty()) {
            @SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
            @NonNull Record<@Nullable S, I, O> rec = dfsStack.peek();
            if (!rec.inputIt.hasNext()) {
                dfsStack.pop();
                continue;
            }
            I input = rec.inputIt.next();
            int inputIdx = alphabet.getSymbolIndex(input);

            Node<O> succ = rec.treeNode.getChild(inputIdx);
            if (succ == null) {
                continue;
            }

            @Nullable S state = rec.automatonState;
            @Nullable S automatonSucc = state == null ? null : target.getSuccessor(state, input);
            if (automatonSucc == null && omitUndefined) {
                continue;
            }

            if (automatonSucc == null || !Objects.equals(target.getStateOutput(automatonSucc), succ.getOutput())) {
                WordBuilder<I> wb = new WordBuilder<>(dfsStack.size());
                wb.append(input);

                dfsStack.pop();
                while (!dfsStack.isEmpty()) {
                    wb.append(rec.incomingInput);
                    rec = dfsStack.pop();
                }
                return wb.reverse().toWord();
            }

            dfsStack.push(new Record<>(automatonSucc, succ, input, inputs.iterator()));
        }

        return null;
    }

    @Override
    public boolean lookup(Word<? extends I> inputWord, List<? super O> output) {
        Node<O> curr = root;

        if (curr == null) {
            return false;
        }

        output.add(curr.getOutput());

        for (I sym : inputWord) {
            int symIdx = alphabet.getSymbolIndex(sym);
            Node<O> succ = curr.getChild(symIdx);
            if (succ == null) {
                return false;
            }
            output.add(succ.getOutput());
            curr = succ;
        }
        return true;
    }

    @Override
    public void insert(Word<? extends I> word, Word<? extends O> output) {
        assert word.size() + 1 == output.size();

        final Iterator<? extends O> outIter = output.iterator();
        final O rootOut = outIter.next();

        if (root == null) {
            root = new Node<>(rootOut);
        }

        Node<O> curr = root;
        for (I sym : word) {
            int inputIdx = alphabet.getSymbolIndex(sym);
            Node<O> succ = curr.getChild(inputIdx);
            if (succ == null) {
                succ = new Node<>(outIter.next());
                curr.setChild(inputIdx, alphabetSize, succ);
            } else if (!Objects.equals(succ.getOutput(), outIter.next())) {
                throw new ConflictException();
            }
            curr = succ;
        }
    }

    @Override
    public MooreTransitionSystem<?, I, ?, O> asTransitionSystem() {
        return new TransitionSystemView();
    }

    @Override
    public Graph<?, ?> asGraph() {
        return new MooreGraphView<Node<O>, I, Node<O>, O, TransitionSystemView>(new TransitionSystemView(), alphabet) {

            @Override
            public VisualizationHelper<Node<O>, TransitionEdge<I, Node<O>>> getVisualizationHelper() {
                return new MooreVisualizationHelper<Node<O>, I, Node<O>, O>(automaton) {

                    @Override
                    public boolean getNodeProperties(Node<O> node, Map<String, String> properties) {
                        super.getNodeProperties(node, properties);
                        properties.put(NodeAttrs.LABEL, String.valueOf(node.getOutput()));
                        return true;
                    }
                };
            }
        };
    }

    private static final class Record<S, I, O> {

        public final S automatonState;
        public final Node<O> treeNode;
        public final I incomingInput;
        public final Iterator<? extends I> inputIt;

        Record(S automatonState, Node<O> treeNode, I incomingInput, Iterator<? extends I> inputIt) {
            this.automatonState = automatonState;
            this.treeNode = treeNode;
            this.incomingInput = incomingInput;
            this.inputIt = inputIt;
        }
    }

    private class TransitionSystemView implements MooreMachine<Node<O>, I, Node<O>, O> {

        @Override
        public @Nullable Node<O> getInitialState() {
            return root;
        }

        @Override
        public O getStateOutput(Node<O> state) {
            return state.getOutput();
        }

        @Override
        public @Nullable Node<O> getTransition(Node<O> state, I input) {
            return state.getChild(alphabet.getSymbolIndex(input));
        }

        @Override
        public Node<O> getSuccessor(Node<O> transition) {
            return transition;
        }

        @Override
        public Collection<Node<O>> getStates() {
            List<Node<O>> result = new ArrayList<>();
            Iterators.addAll(result, TSTraversal.breadthFirstIterator(this, alphabet));
            return result;
        }

        /*
         * We need to override the default MooreMachine mapping, because its StateIDStaticMapping class requires our
         * nodeIDs, which requires our states, which requires our nodeIDs, which requires ... infinite loop!
         */
        @Override
        public <V> MutableMapping<Node<O>, V> createStaticStateMapping() {
            return new MapMapping<>();
        }
    }
}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of AutomataLib, http://www.automatalib.net/.
3	*
4	* Licensed under the Apache License, Version 2.0 (the "License");
5	* you may not use this file except in compliance with the License.
6	* You may obtain a copy of the License at
7	*
8	* http://www.apache.org/licenses/LICENSE-2.0
9	*
10	* Unless required by applicable law or agreed to in writing, software
11	* distributed under the License is distributed on an "AS IS" BASIS,
12	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	* See the License for the specific language governing permissions and
14	* limitations under the License.
15	*/
16	package net.automatalib.incremental.moore.tree;
17
18	import java.util.ArrayDeque;
19	import java.util.ArrayList;
20	import java.util.Collection;
21	import java.util.Deque;
22	import java.util.Iterator;
23	import java.util.List;
24	import java.util.Map;
25	import java.util.Objects;
26
27	import com.google.common.collect.Iterators;
28	import net.automatalib.alphabet.Alphabet;
29	import net.automatalib.alphabet.Alphabets;
30	import net.automatalib.automaton.graph.TransitionEdge;
31	import net.automatalib.automaton.transducer.MooreMachine;
32	import net.automatalib.automaton.transducer.MooreMachine.MooreGraphView;
33	import net.automatalib.automaton.visualization.MooreVisualizationHelper;
34	import net.automatalib.common.util.mapping.MapMapping;
35	import net.automatalib.common.util.mapping.MutableMapping;
36	import net.automatalib.graph.Graph;
37	import net.automatalib.incremental.ConflictException;
38	import net.automatalib.incremental.moore.IncrementalMooreBuilder;
39	import net.automatalib.ts.output.MooreTransitionSystem;
40	import net.automatalib.util.ts.traversal.TSTraversal;
41	import net.automatalib.visualization.VisualizationHelper;
42	import net.automatalib.word.Word;
43	import net.automatalib.word.WordBuilder;
44	import org.checkerframework.checker.nullness.qual.NonNull;
45	import org.checkerframework.checker.nullness.qual.Nullable;
46
47	/**
48	* Incrementally builds a (tree-based) Moore machine from a set of input and corresponding output words.
49	*
50	* @param <I>
51	* input symbol class
52	* @param <O>
53	* output symbol class
54	*/
55	public class IncrementalMooreTreeBuilder<I, O> implements IncrementalMooreBuilder<I, O> {	2✔
56
57	private final Alphabet<I> alphabet;
58	private int alphabetSize;
59	private @Nullable Node<O> root;
60
61	public IncrementalMooreTreeBuilder(Alphabet<I> alphabet) {	2✔
62	this.alphabet = alphabet;	2✔
63	this.alphabetSize = alphabet.size();	2✔
64	}	2✔
65
66	@Override
67	public void addAlphabetSymbol(I symbol) {
68	if (!this.alphabet.containsSymbol(symbol)) {	2✔
69	Alphabets.toGrowingAlphabetOrThrowException(this.alphabet).addSymbol(symbol);	2✔
70	}
71
72	final int newAlphabetSize = this.alphabet.size();	2✔
73	// even if the symbol was already in the alphabet, we need to make sure to be able to store the new symbol
74	if (alphabetSize < newAlphabetSize && root != null) {	2✔
75	ensureInputCapacity(root, alphabetSize, newAlphabetSize);	2✔
76	}
77	alphabetSize = newAlphabetSize;	2✔
78	}	2✔
79
80	private void ensureInputCapacity(Node<O> node, int oldAlphabetSize, int newAlphabetSize) {
81	node.ensureInputCapacity(newAlphabetSize);	2✔
82	for (int i = 0; i < oldAlphabetSize; i++) {	2✔
83	final Node<O> child = node.getChild(i);	2✔
84	if (child != null) {	2✔
85	ensureInputCapacity(child, oldAlphabetSize, newAlphabetSize);	2✔
86	}
87	}
88	}	2✔
89
90	@Override
91	public @Nullable Word<I> findSeparatingWord(MooreMachine<?, I, ?, O> target,
92	Collection<? extends I> inputs,
93	boolean omitUndefined) {
94	return doFindSeparatingWord(target, inputs, omitUndefined);	2✔
95	}
96
97	private <S, T> @Nullable Word<I> doFindSeparatingWord(MooreMachine<S, I, T, O> target,
98	Collection<? extends I> inputs,
99	boolean omitUndefined) {
100	S init2 = target.getInitialState();	2✔
101
102	if (root == null && init2 == null) {	2✔
UNCOV 103	return null;	×
104	} else if (root == null \|\| init2 == null) {	2✔
105	return omitUndefined ? null : Word.epsilon();	2✔
106	}
107
108	if (!Objects.equals(root.getOutput(), target.getStateOutput(init2))) {	2✔
UNCOV 109	return Word.epsilon();	×
110	}
111
112	// incomingInput can be null here, because we will always skip the bottom stack element below
113	@SuppressWarnings("nullness")
114	Record<@Nullable S, I, O> init = new Record<>(init2, root, null, inputs.iterator());	2✔
115
116	Deque<Record<@Nullable S, I, O>> dfsStack = new ArrayDeque<>();	2✔
117	dfsStack.push(init);	2✔
118
119	while (!dfsStack.isEmpty()) {	2✔
120	@SuppressWarnings("nullness") // false positive https://github.com/typetools/checker-framework/issues/399
121	@NonNull Record<@Nullable S, I, O> rec = dfsStack.peek();	2✔
122	if (!rec.inputIt.hasNext()) {	2✔
123	dfsStack.pop();	2✔
124	continue;	2✔
125	}
126	I input = rec.inputIt.next();	2✔
127	int inputIdx = alphabet.getSymbolIndex(input);	2✔
128
129	Node<O> succ = rec.treeNode.getChild(inputIdx);	2✔
130	if (succ == null) {	2✔
131	continue;	2✔
132	}
133
134	@Nullable S state = rec.automatonState;	2✔
135	@Nullable S automatonSucc = state == null ? null : target.getSuccessor(state, input);	2✔
136	if (automatonSucc == null && omitUndefined) {	2✔
137	continue;	2✔
138	}
139
140	if (automatonSucc == null \|\| !Objects.equals(target.getStateOutput(automatonSucc), succ.getOutput())) {	2✔
141	WordBuilder<I> wb = new WordBuilder<>(dfsStack.size());	2✔
142	wb.append(input);	2✔
143
144	dfsStack.pop();	2✔
145	while (!dfsStack.isEmpty()) {	2✔
146	wb.append(rec.incomingInput);	2✔
147	rec = dfsStack.pop();	2✔
148	}
149	return wb.reverse().toWord();	2✔
150	}
151
152	dfsStack.push(new Record<>(automatonSucc, succ, input, inputs.iterator()));	2✔
153	}	2✔
154
155	return null;	2✔
156	}
157
158	@Override
159	public boolean lookup(Word<? extends I> inputWord, List<? super O> output) {
160	Node<O> curr = root;	2✔
161
162	if (curr == null) {	2✔
163	return false;	2✔
164	}
165
166	output.add(curr.getOutput());	2✔
167
168	for (I sym : inputWord) {	2✔
169	int symIdx = alphabet.getSymbolIndex(sym);	2✔
170	Node<O> succ = curr.getChild(symIdx);	2✔
171	if (succ == null) {	2✔
172	return false;	2✔
173	}
174	output.add(succ.getOutput());	2✔
175	curr = succ;	2✔
176	}	2✔
177	return true;	2✔
178	}
179
180	@Override
181	public void insert(Word<? extends I> word, Word<? extends O> output) {
182	assert word.size() + 1 == output.size();	2✔
183
184	final Iterator<? extends O> outIter = output.iterator();	2✔
185	final O rootOut = outIter.next();	2✔
186
187	if (root == null) {	2✔
188	root = new Node<>(rootOut);	2✔
189	}
190
191	Node<O> curr = root;	2✔
192	for (I sym : word) {	2✔
193	int inputIdx = alphabet.getSymbolIndex(sym);	2✔
194	Node<O> succ = curr.getChild(inputIdx);	2✔
195	if (succ == null) {	2✔
196	succ = new Node<>(outIter.next());	2✔
197	curr.setChild(inputIdx, alphabetSize, succ);	2✔
198	} else if (!Objects.equals(succ.getOutput(), outIter.next())) {	2✔
199	throw new ConflictException();	2✔
200	}
201	curr = succ;	2✔
202	}	2✔
203	}	2✔
204
205	@Override
206	public MooreTransitionSystem<?, I, ?, O> asTransitionSystem() {
207	return new TransitionSystemView();	2✔
208	}
209
210	@Override
211	public Graph<?, ?> asGraph() {
212	return new MooreGraphView<Node<O>, I, Node<O>, O, TransitionSystemView>(new TransitionSystemView(), alphabet) {	2✔
213
214	@Override
215	public VisualizationHelper<Node<O>, TransitionEdge<I, Node<O>>> getVisualizationHelper() {
216	return new MooreVisualizationHelper<Node<O>, I, Node<O>, O>(automaton) {	2✔
217
218	@Override
219	public boolean getNodeProperties(Node<O> node, Map<String, String> properties) {
220	super.getNodeProperties(node, properties);	2✔
221	properties.put(NodeAttrs.LABEL, String.valueOf(node.getOutput()));	2✔
222	return true;	2✔
223	}
224	};
225	}
226	};
227	}
228
229	private static final class Record<S, I, O> {
230
231	public final S automatonState;
232	public final Node<O> treeNode;
233	public final I incomingInput;
234	public final Iterator<? extends I> inputIt;
235
236	Record(S automatonState, Node<O> treeNode, I incomingInput, Iterator<? extends I> inputIt) {	2✔
237	this.automatonState = automatonState;	2✔
238	this.treeNode = treeNode;	2✔
239	this.incomingInput = incomingInput;	2✔
240	this.inputIt = inputIt;	2✔
241	}	2✔
242	}
243
244	private class TransitionSystemView implements MooreMachine<Node<O>, I, Node<O>, O> {	2✔
245
246	@Override
247	public @Nullable Node<O> getInitialState() {
248	return root;	2✔
249	}
250
251	@Override
252	public O getStateOutput(Node<O> state) {
253	return state.getOutput();	2✔
254	}
255
256	@Override
257	public @Nullable Node<O> getTransition(Node<O> state, I input) {
258	return state.getChild(alphabet.getSymbolIndex(input));	2✔
259	}
260
261	@Override
262	public Node<O> getSuccessor(Node<O> transition) {
263	return transition;	2✔
264	}
265
266	@Override
267	public Collection<Node<O>> getStates() {
268	List<Node<O>> result = new ArrayList<>();	2✔
269	Iterators.addAll(result, TSTraversal.breadthFirstIterator(this, alphabet));	2✔
270	return result;	2✔
271	}
272
273	/*
274	* We need to override the default MooreMachine mapping, because its StateIDStaticMapping class requires our
275	* nodeIDs, which requires our states, which requires our nodeIDs, which requires ... infinite loop!
276	*/
277	@Override
278	public <V> MutableMapping<Node<O>, V> createStaticStateMapping() {
279	return new MapMapping<>();	2✔
280	}
281	}
282	}

LearnLib / automatalib / 6763327895

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous