13138848026

Committed 04 Feb 2025 02:53PM UTC coverage: 92.108% (+2.2%) from 89.877%

Build # 13138848026

Build Type

push

github

Committed by

mtf90

Commit Message

[maven-release-plugin] prepare release automatalib-0.12.0

Run Details

16609 of 18032 relevant lines covered (92.11%)

1.7 hits per line

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

98.06

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

/* Copyright (C) 2013-2025 TU Dortmund University
 * This file is part of AutomataLib <https://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.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Objects;

import net.automatalib.alphabet.Alphabet;
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.collection.IteratorUtil;
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)) {
            this.alphabet.asGrowingAlphabetOrThrowException().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 final 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() {
            return IteratorUtil.list(TSTraversal.breadthFirstIterator(this, alphabet));
        }

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

LearnLib / automatalib / 13138848026

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