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

95.45

/util/src/main/java/net/automatalib/util/automaton/conformance/WpMethodTestsIterator.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.util.automaton.conformance;

import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

import net.automatalib.automaton.UniversalDeterministicAutomaton;
import net.automatalib.common.util.HashUtil;
import net.automatalib.common.util.collection.AbstractThreeLevelIterator;
import net.automatalib.common.util.collection.IterableUtil;
import net.automatalib.common.util.collection.IteratorUtil;
import net.automatalib.common.util.mapping.MutableMapping;
import net.automatalib.util.automaton.Automata;
import net.automatalib.util.automaton.cover.Covers;
import net.automatalib.util.automaton.equivalence.CharacterizingSets;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * Iterator that returns test words generated by the partial W method.
 * <p>
 * See "Test selection based on finite state models" by S. Fujiwara et al.
 *
 * @param <I>
 *         input symbol type
 */
public class WpMethodTestsIterator<I> implements Iterator<Word<I>> {

    private final Iterator<Word<I>> wpIterator;

    /**
     * Convenience-constructor for {@link #WpMethodTestsIterator(UniversalDeterministicAutomaton, Collection, int)} that
     * selects {@code 0} as {@code maxDepth}.
     *
     * @param automaton
     *         the automaton for which the testing sequences should be generated
     * @param inputs
     *         the input symbols that should be considered for test sequence generation
     */
    public WpMethodTestsIterator(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
                                 Collection<? extends I> inputs) {
        this(automaton, inputs, 0);
    }

    /**
     * Constructor.
     *
     * @param automaton
     *         the automaton for which the testing sequences should be generated
     * @param inputs
     *         the input symbols that should be considered for test sequence generation
     * @param maxDepth
     *         the maximum number of symbols that are appended to the transition-cover part of the test sequences
     */
    public WpMethodTestsIterator(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
                                 Collection<? extends I> inputs,
                                 int maxDepth) {

        final Set<Word<I>> stateCover = new HashSet<>(HashUtil.capacity(automaton.size()));
        final Set<Word<I>> transitionCover = new HashSet<>(HashUtil.capacity(automaton.size() * inputs.size()));

        Covers.cover(automaton, inputs, stateCover, transitionCover);

        Iterator<Word<I>> characterizingIter = CharacterizingSets.characterizingSetIterator(automaton, inputs);

        // Special case: List of characterizing suffixes may be empty,
        // but in this case we still need to iterate over the prefixes!
        if (!characterizingIter.hasNext()) {
            characterizingIter = IteratorUtil.singleton(Word.epsilon());
        }

        // Phase 1: state cover * middle part * global suffixes
        final Iterator<Word<I>> firstIterator = new FirstPhaseIterator<>(stateCover,
                                                                         IterableUtil.allTuples(inputs, 0, maxDepth),
                                                                         characterizingIter);

        // Phase 2: transitions (not in state cover) * middle part * local suffixes
        transitionCover.removeAll(stateCover);
        final Iterator<Word<I>> secondIterator = new SecondPhaseIterator<>(automaton,
                                                                           inputs,
                                                                           transitionCover,
                                                                           IterableUtil.allTuples(inputs,
                                                                                                  0,
                                                                                                  maxDepth));

        wpIterator = IteratorUtil.concat(firstIterator, secondIterator);
    }

    @Override
    public boolean hasNext() {
        return this.wpIterator.hasNext();
    }

    @Override
    public Word<I> next() {
        return this.wpIterator.next();
    }

    private static class FirstPhaseIterator<I> extends AbstractThreeLevelIterator<Word<I>, List<I>, Word<I>, Word<I>> {

        private final Iterable<Word<I>> prefixes;
        private final Iterable<List<I>> middleParts;

        FirstPhaseIterator(Iterable<Word<I>> prefixes, Iterable<List<I>> middleParts, Iterator<Word<I>> suffixes) {
            super(suffixes);

            this.prefixes = prefixes;
            this.middleParts = middleParts;
        }

        @Override
        protected Iterator<List<I>> l2Iterator(Word<I> suffix) {
            return middleParts.iterator();
        }

        @Override
        protected Iterator<Word<I>> l3Iterator(Word<I> suffix, List<I> middle) {
            return prefixes.iterator();
        }

        @Override
        protected Word<I> combine(Word<I> suffix, List<I> middle, Word<I> prefix) {
            final WordBuilder<I> wb = new WordBuilder<>(prefix.size() + middle.size() + suffix.size());
            return wb.append(prefix).append(middle).append(suffix).toWord();
        }
    }

    private static class SecondPhaseIterator<S, I>
            extends AbstractThreeLevelIterator<Word<I>, List<I>, Word<I>, Word<I>> {

        private final UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton;
        private final Collection<? extends I> inputs;

        private final MutableMapping<S, List<Word<I>>> localSuffixSets;
        private final Iterable<List<I>> middleParts;

        SecondPhaseIterator(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
                            Collection<? extends I> inputs,
                            Iterable<Word<I>> prefixes,
                            Iterable<List<I>> middleParts) {
            super(prefixes.iterator());

            this.automaton = automaton;
            this.inputs = inputs;
            this.localSuffixSets = automaton.createStaticStateMapping();
            this.middleParts = middleParts;
        }

        @Override
        protected Iterator<List<I>> l2Iterator(Word<I> prefix) {
            return middleParts.iterator();
        }

        @Override
        protected Iterator<Word<I>> l3Iterator(Word<I> prefix, List<I> middle) {

            @SuppressWarnings("nullness") // input sequences have been computed on defined transitions
            final @NonNull S tmp = automaton.getState(prefix);
            @SuppressWarnings("nullness") // input sequences have been computed on defined transitions
            final @NonNull S state = automaton.getSuccessor(tmp, middle);

            @Nullable List<Word<I>> localSuffixes = localSuffixSets.get(state);

            if (localSuffixes == null) {
                localSuffixes = Automata.stateCharacterizingSet(automaton, inputs, state);
                if (localSuffixes.isEmpty()) {
                    localSuffixes = Collections.singletonList(Word.epsilon());
                }
                localSuffixSets.put(state, localSuffixes);
            }

            return localSuffixes.iterator();
        }

        @Override
        protected Word<I> combine(Word<I> prefix, List<I> middle, Word<I> suffix) {
            final WordBuilder<I> wb = new WordBuilder<>(prefix.size() + middle.size() + suffix.size());
            return wb.append(prefix).append(middle).append(suffix).toWord();
        }
    }
}

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.util.automaton.conformance;
17
18	import java.util.Collection;
19	import java.util.Collections;
20	import java.util.HashSet;
21	import java.util.Iterator;
22	import java.util.List;
23	import java.util.Set;
24
25	import net.automatalib.automaton.UniversalDeterministicAutomaton;
26	import net.automatalib.common.util.HashUtil;
27	import net.automatalib.common.util.collection.AbstractThreeLevelIterator;
28	import net.automatalib.common.util.collection.IterableUtil;
29	import net.automatalib.common.util.collection.IteratorUtil;
30	import net.automatalib.common.util.mapping.MutableMapping;
31	import net.automatalib.util.automaton.Automata;
32	import net.automatalib.util.automaton.cover.Covers;
33	import net.automatalib.util.automaton.equivalence.CharacterizingSets;
34	import net.automatalib.word.Word;
35	import net.automatalib.word.WordBuilder;
36	import org.checkerframework.checker.nullness.qual.NonNull;
37	import org.checkerframework.checker.nullness.qual.Nullable;
38
39	/**
40	* Iterator that returns test words generated by the partial W method.
41	* <p>
42	* See "Test selection based on finite state models" by S. Fujiwara et al.
43	*
44	* @param <I>
45	* input symbol type
46	*/
47	public class WpMethodTestsIterator<I> implements Iterator<Word<I>> {
48
49	private final Iterator<Word<I>> wpIterator;
50
51	/**
52	* Convenience-constructor for {@link #WpMethodTestsIterator(UniversalDeterministicAutomaton, Collection, int)} that
53	* selects {@code 0} as {@code maxDepth}.
54	*
55	* @param automaton
56	* the automaton for which the testing sequences should be generated
57	* @param inputs
58	* the input symbols that should be considered for test sequence generation
59	*/
60	public WpMethodTestsIterator(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
61	Collection<? extends I> inputs) {
62	this(automaton, inputs, 0);	2✔
63	}	2✔
64
65	/**
66	* Constructor.
67	*
68	* @param automaton
69	* the automaton for which the testing sequences should be generated
70	* @param inputs
71	* the input symbols that should be considered for test sequence generation
72	* @param maxDepth
73	* the maximum number of symbols that are appended to the transition-cover part of the test sequences
74	*/
75	public WpMethodTestsIterator(UniversalDeterministicAutomaton<?, I, ?, ?, ?> automaton,
76	Collection<? extends I> inputs,
77	int maxDepth) {	2✔
78
79	final Set<Word<I>> stateCover = new HashSet<>(HashUtil.capacity(automaton.size()));	2✔
80	final Set<Word<I>> transitionCover = new HashSet<>(HashUtil.capacity(automaton.size() * inputs.size()));	2✔
81
82	Covers.cover(automaton, inputs, stateCover, transitionCover);	2✔
83
84	Iterator<Word<I>> characterizingIter = CharacterizingSets.characterizingSetIterator(automaton, inputs);	2✔
85
86	// Special case: List of characterizing suffixes may be empty,
87	// but in this case we still need to iterate over the prefixes!
88	if (!characterizingIter.hasNext()) {	2✔
89	characterizingIter = IteratorUtil.singleton(Word.epsilon());	×
90	}
91
92	// Phase 1: state cover * middle part * global suffixes
93	final Iterator<Word<I>> firstIterator = new FirstPhaseIterator<>(stateCover,	2✔
94	IterableUtil.allTuples(inputs, 0, maxDepth),	2✔
95	characterizingIter);
96
97	// Phase 2: transitions (not in state cover) * middle part * local suffixes
98	transitionCover.removeAll(stateCover);	2✔
99	final Iterator<Word<I>> secondIterator = new SecondPhaseIterator<>(automaton,	2✔
100	inputs,
101	transitionCover,
102	IterableUtil.allTuples(inputs,	2✔
103	0,
104	maxDepth));
105
106	wpIterator = IteratorUtil.concat(firstIterator, secondIterator);	2✔
107	}	2✔
108
109	@Override
110	public boolean hasNext() {
111	return this.wpIterator.hasNext();	2✔
112	}
113
114	@Override
115	public Word<I> next() {
116	return this.wpIterator.next();	2✔
117	}
118
119	private static class FirstPhaseIterator<I> extends AbstractThreeLevelIterator<Word<I>, List<I>, Word<I>, Word<I>> {
120
121	private final Iterable<Word<I>> prefixes;
122	private final Iterable<List<I>> middleParts;
123
124	FirstPhaseIterator(Iterable<Word<I>> prefixes, Iterable<List<I>> middleParts, Iterator<Word<I>> suffixes) {
125	super(suffixes);	2✔
126
127	this.prefixes = prefixes;	2✔
128	this.middleParts = middleParts;	2✔
129	}	2✔
130
131	@Override
132	protected Iterator<List<I>> l2Iterator(Word<I> suffix) {
133	return middleParts.iterator();	2✔
134	}
135
136	@Override
137	protected Iterator<Word<I>> l3Iterator(Word<I> suffix, List<I> middle) {
138	return prefixes.iterator();	2✔
139	}
140
141	@Override
142	protected Word<I> combine(Word<I> suffix, List<I> middle, Word<I> prefix) {
143	final WordBuilder<I> wb = new WordBuilder<>(prefix.size() + middle.size() + suffix.size());	2✔
144	return wb.append(prefix).append(middle).append(suffix).toWord();	2✔
145	}
146	}
147
148	private static class SecondPhaseIterator<S, I>
149	extends AbstractThreeLevelIterator<Word<I>, List<I>, Word<I>, Word<I>> {
150
151	private final UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton;
152	private final Collection<? extends I> inputs;
153
154	private final MutableMapping<S, List<Word<I>>> localSuffixSets;
155	private final Iterable<List<I>> middleParts;
156
157	SecondPhaseIterator(UniversalDeterministicAutomaton<S, I, ?, ?, ?> automaton,
158	Collection<? extends I> inputs,
159	Iterable<Word<I>> prefixes,
160	Iterable<List<I>> middleParts) {
161	super(prefixes.iterator());	2✔
162
163	this.automaton = automaton;	2✔
164	this.inputs = inputs;	2✔
165	this.localSuffixSets = automaton.createStaticStateMapping();	2✔
166	this.middleParts = middleParts;	2✔
167	}	2✔
168
169	@Override
170	protected Iterator<List<I>> l2Iterator(Word<I> prefix) {
171	return middleParts.iterator();	2✔
172	}
173
174	@Override
175	protected Iterator<Word<I>> l3Iterator(Word<I> prefix, List<I> middle) {
176
177	@SuppressWarnings("nullness") // input sequences have been computed on defined transitions
178	final @NonNull S tmp = automaton.getState(prefix);	2✔
179	@SuppressWarnings("nullness") // input sequences have been computed on defined transitions
180	final @NonNull S state = automaton.getSuccessor(tmp, middle);	2✔
181
182	@Nullable List<Word<I>> localSuffixes = localSuffixSets.get(state);	2✔
183
184	if (localSuffixes == null) {	2✔
185	localSuffixes = Automata.stateCharacterizingSet(automaton, inputs, state);	2✔
186	if (localSuffixes.isEmpty()) {	2✔
187	localSuffixes = Collections.singletonList(Word.epsilon());	×
188	}
189	localSuffixSets.put(state, localSuffixes);	2✔
190	}
191
192	return localSuffixes.iterator();	2✔
193	}
194
195	@Override
196	protected Word<I> combine(Word<I> prefix, List<I> middle, Word<I> suffix) {
197	final WordBuilder<I> wb = new WordBuilder<>(prefix.size() + middle.size() + suffix.size());	2✔
198	return wb.append(prefix).append(middle).append(suffix).toWord();	2✔
199	}
200	}
201	}

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