20242050438

Committed 15 Dec 2025 05:50PM UTC coverage: 92.934% (+0.1%) from 92.834%

Build # 20242050438

Build Type

Pull #99

github

Committed by

web-flow

Commit Message

Merge 68218e55f into 4ed436ef7

Pull Request Pull Request #99: Add conformance test generators based on k-way state/transition coverage

Coverage Stats

289 of 291 new or added lines in 10 files covered. (99.31%)

17439 of 18765 relevant lines covered (92.93%)

1.72 hits per line

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

99.22

/util/src/main/java/net/automatalib/util/automaton/conformance/KWayTransitionCoverTestsIterator.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.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
import java.util.Random;
import java.util.Set;
import java.util.stream.Stream;

import net.automatalib.automaton.DeterministicAutomaton;
import net.automatalib.common.util.HashUtil;
import net.automatalib.common.util.collection.AbstractSimplifiedIterator;
import net.automatalib.common.util.collection.AbstractTwoLevelIterator;
import net.automatalib.common.util.collection.CollectionUtil;
import net.automatalib.common.util.collection.IterableUtil;
import net.automatalib.common.util.collection.IteratorUtil;
import net.automatalib.common.util.mapping.Mapping;
import net.automatalib.common.util.random.RandomUtil;
import net.automatalib.util.automaton.cover.Covers;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A randomized transition cover test generator based on the concepts of mutation testing as described in the paper <a
 * href="https://doi.org/10.1007/978-3-319-57288-8_2">Learning from Faults: Mutation Testing in Active Automata
 * Learning</a> by Bernhard K. Aichernig and Martin Tappler.
 * <p>
 * This iterator selects test cases based on k-way transitions coverage. It does that by generating random test words
 * and finding the smallest subset with the highest coverage. In other words, this iterator generates test words by
 * running random paths that cover all pairwise / k-way transitions.
 * <p>
 * <b>Implementation detail:</b> Note that this test generator heavily relies on the sampling of states. If the given
 * automaton has very few or very many states, the number of generated test cases may be very low or high, respectively.
 * As a result, it may be advisable to {@link IteratorUtil#concat(Iterator[]) combine} this generator with other
 * generators or {@link Stream#limit(long) limit} the number of generated test cases.
 *
 * @param <S>
 *         automaton state type
 * @param <I>
 *         input symbol type
 * @param <A>
 *         automaton type
 */
public class KWayTransitionCoverTestsIterator<S, I, A extends DeterministicAutomaton<S, I, ?>>
        implements Iterator<Word<I>> {

    /**
     * The default value of k used in the k-way computations.
     */
    public static final int DEFAULT_K = 2;

    /**
     * The default for the maximum step size of {@link GenerationMethod#RANDOM randomly}-generated paths.
     */
    public static final int DEFAULT_MAX_PATH_LENGTH = 50;

    /**
     * The default (unlimited) threshold for the number of steps after which no more new test words will be generated.
     */
    public static final int DEFAULT_MAX_NUM_STEPS = 0;

    /**
     * The default number of {@link GenerationMethod#RANDOM randomly}-generated tests used to find the optimal subset.
     */
    public static final int DEFAULT_NUM_GEN_PATHS = 1_000;

    /**
     * The default number of steps that are appended to {@link GenerationMethod#PREFIX prefix}-generated paths.
     */
    public static final int DEFAULT_R_WALK_LEN = 10;

    private final A automaton;
    private final List<? extends I> alphabet;
    private final Random random;
    private final int randomWalkLen;
    private final int numGeneratePaths;
    private final int maxPathLen;
    private final int maxNumberOfSteps;
    private final int k;
    private final OptimizationMetric optimizationMetric;

    private final Iterator<Word<I>> iterator;

    /**
     * Convenience constructor which uses a fresh {@code random} object.
     *
     * @param automaton
     *         the automaton for which to generate test cases
     * @param inputs
     *         the inputs to consider for test case generation
     *
     * @see #KWayTransitionCoverTestsIterator(DeterministicAutomaton, Collection, Random)
     */
    public KWayTransitionCoverTestsIterator(A automaton, Collection<? extends I> inputs) {
        this(automaton, inputs, new Random());
    }

    /**
     * Convenience constructor. Uses <code>randomWalkLen = {@value #DEFAULT_R_WALK_LEN}</code>, <code>numGeneratePaths =
     * {@value #DEFAULT_NUM_GEN_PATHS}</code>, <code>maxPathLen = {@value #DEFAULT_MAX_PATH_LENGTH}</code>,
     * <code>maxNumberOfSteps = {@value #DEFAULT_MAX_NUM_STEPS}</code>, <code>k = {@value DEFAULT_K}</code>,
     * <code>optimizationMetric = {@link OptimizationMetric#STEPS STEPS}</code>, and <code>generationMethod =
     * {@link GenerationMethod#RANDOM RANDOM}</code>.
     *
     * @param automaton
     *         the automaton for which to generate test cases
     * @param inputs
     *         the inputs to consider for test case generation
     * @param random
     *         the random number generator to use
     *
     * @see #KWayTransitionCoverTestsIterator(DeterministicAutomaton, Collection, Random, int, int, int, int, int,
     * OptimizationMetric, GenerationMethod)
     */
    public KWayTransitionCoverTestsIterator(A automaton, Collection<? extends I> inputs, Random random) {
        this(automaton,
             inputs,
             random,
             DEFAULT_R_WALK_LEN,
             DEFAULT_NUM_GEN_PATHS,
             DEFAULT_MAX_PATH_LENGTH,
             DEFAULT_MAX_NUM_STEPS,
             DEFAULT_K,
             OptimizationMetric.STEPS,
             GenerationMethod.RANDOM);
    }

    /**
     * Constructor.
     *
     * @param automaton
     *         the automaton for which to generate test cases
     * @param inputs
     *         the inputs to consider for test case generation
     * @param random
     *         the random number generator to use
     * @param randomWalkLen
     *         the number of steps that are appended to {@link GenerationMethod#PREFIX prefix}-generated paths
     * @param numGeneratePaths
     *         number of {@link GenerationMethod#RANDOM randomly}-generated tests used to find the optimal subset
     * @param maxPathLen
     *         the maximum step size of {@link GenerationMethod#RANDOM randomly}-generated paths
     * @param maxNumberOfSteps
     *         threshold for the number of steps after which no more new test words will be generated (a value less than
     *         zero means no limit)
     * @param k
     *         k value used for K-Way transitions, i.e.,the number of steps between the start and the end of a
     *         transition
     * @param optimizationMetric
     *         the metric after which test cases are minimized
     * @param generationMethod
     *         defines how the tests are generated
     */
    public KWayTransitionCoverTestsIterator(A automaton,
                                            Collection<? extends I> inputs,
                                            Random random,
                                            int randomWalkLen,
                                            int numGeneratePaths,
                                            int maxPathLen,
                                            int maxNumberOfSteps,
                                            int k,
                                            OptimizationMetric optimizationMetric,
                                            GenerationMethod generationMethod) {
        this.automaton = automaton;
        this.alphabet = CollectionUtil.randomAccessList(inputs);
        this.random = random;

        this.randomWalkLen = randomWalkLen;
        this.numGeneratePaths = numGeneratePaths;
        this.maxPathLen = maxPathLen;
        this.maxNumberOfSteps = maxNumberOfSteps;
        this.k = Math.min(k, automaton.size());
        this.optimizationMetric = optimizationMetric;

        final S initial = automaton.getInitialState();

        if (automaton.size() == 0 || initial == null) {
            this.iterator = Collections.emptyIterator();
        } else {
            this.iterator = generationMethod.getIterator(this, initial);
        }

    }

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

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

    private Set<Path<S, I>> generateRandomPaths(A hypothesis, S initial) {
        final Set<Path<S, I>> result = new HashSet<>(HashUtil.capacity(numGeneratePaths));

        for (int i = 0; i < numGeneratePaths; i++) {
            final int randomLength = random.nextInt(maxPathLen - k + 1) + k; // Ensuring length is at least `k`
            final Word<I> steps = Word.fromList(RandomUtil.sample(random, alphabet, randomLength));
            final Path<S, I> path = createPath(hypothesis, initial, steps);
            result.add(path);
        }

        return result;
    }

    private Path<S, I> createPath(A hypothesis, S initial, Word<I> steps) {
        final Set<KWayTransition<S, I>> transitions = new HashSet<>();

        final List<@Nullable S> prevStates = new ArrayList<>(steps.size());
        final List<@Nullable S> endStates = new ArrayList<>(steps.size());

        S iter = initial;

        for (I i : steps) {
            prevStates.add(iter);
            iter = iter == null ? null : hypothesis.getSuccessor(iter, i);
            endStates.add(iter);
        }

        for (int i = 0; i < steps.size() - k + 1; i++) {
            final @Nullable S prevState = prevStates.get(i);
            final @Nullable S endState = endStates.get(i + k - 1);
            final Word<I> chunk = steps.subWord(i, i + k);

            final KWayTransition<S, I> transition = new KWayTransition<>(prevState, endState, chunk);

            transitions.add(transition);
        }

        return new Path<>(steps, transitions);
    }

    private Iterator<Word<I>> generatePrefixSteps(A hypothesis, S initial) {
        final List<S> states = new ArrayList<>(hypothesis.getStates());
        Collections.reverse(states);
        return new PrefixStepsIterator(states.iterator(), initial);
    }

    private @Nullable Path<S, I> selectOptimalPath(Set<KWayTransition<S, I>> covered, Set<Path<S, I>> paths) {
        final Path<S, I> max = Collections.max(paths, optimizationMetric.getPathComparator(covered));
        return sizeOfSetDifference(max.kWayTransitions, covered) > 0 ? max : null;
    }

    static <T> int sizeOfSetDifference(Set<T> minuend, Set<T> subtrahend) {
        /*
         * This method is performance-critical so we do a little bit more involved computation.
         */
        final Set<T> smaller, bigger;
        if (minuend.size() < subtrahend.size()) {
            smaller = minuend;
            bigger = subtrahend;
        } else {
            smaller = subtrahend;
            bigger = minuend;
        }

        int size = minuend.size();
        for (T t : smaller) {
            if (bigger.contains(t)) {
                size--;
            }
        }
        return size;
    }

    private class GreedySetCoverIterator extends AbstractSimplifiedIterator<Word<I>> {

        private final S initial;
        private final Set<Path<S, I>> paths;
        private final Set<KWayTransition<S, I>> covered;
        private final int sizeOfUniverse;

        private int stepCount;

        GreedySetCoverIterator(S initial) {
            this.initial = initial;
            this.paths = generateRandomPaths(automaton, initial);
            this.covered = new HashSet<>();
            this.stepCount = 0;
            this.sizeOfUniverse = Math.multiplyExact(automaton.getStates().size(), (int) Math.pow(alphabet.size(), k));
        }

        @Override
        protected boolean calculateNext() {
            while (sizeOfUniverse > covered.size() && (maxNumberOfSteps == 0 || stepCount <= maxNumberOfSteps)) {
                final Path<S, I> path = selectOptimalPath(covered, paths);

                if (path != null) {
                    covered.addAll(path.kWayTransitions);
                    paths.remove(path);
                    stepCount += path.steps.size();
                    super.nextValue = path.steps;

                    if (paths.isEmpty()) {
                        computeNewPaths();
                    }
                    return true;
                } else {
                    computeNewPaths();
                }
            }
            return false;
        }

        private void computeNewPaths() {
            final Iterator<Word<I>> prefixIterator = generatePrefixSteps(automaton, initial);
            while (prefixIterator.hasNext()) {
                final Word<I> generatePrefixStep = prefixIterator.next();
                paths.add(createPath(automaton, initial, generatePrefixStep));
            }
        }
    }

    private class PrefixStepsIterator extends AbstractTwoLevelIterator<S, List<I>, Word<I>> {

        private final Mapping<S, @Nullable Word<I>> accessSequences;

        PrefixStepsIterator(Iterator<S> iterator, S initial) {
            super(iterator);
            this.accessSequences = Covers.cover(automaton, alphabet, initial, w -> {}, w -> {});
        }

        @Override
        protected Iterator<List<I>> l2Iterator(S state) {
            /*
             * The original code shuffles all tuples globally. Since we can't do this lazily, we approximate this
             * behavior by at least shuffling the input symbols for a randomized tuple order.
             */
            final List<I> inputs = new ArrayList<>(alphabet);
            Collections.shuffle(inputs, random);
            final Iterable<List<I>> lists = IterableUtil.allTuples(inputs, k);
            return lists.iterator();
        }

        @Override
        protected Word<I> combine(S state, List<I> steps) {
            final Word<I> prefix = accessSequences.get(state);
            if (prefix == null) {
                return Word.epsilon();
            }

            final WordBuilder<I> wb = new WordBuilder<>(prefix.length() + steps.size() + randomWalkLen);

            wb.append(prefix);
            wb.append(steps);
            wb.append(RandomUtil.sample(random, alphabet, randomWalkLen));

            return wb.toWord();
        }
    }

    private static final class KWayTransition<S, I> {

        private final @Nullable S startState;
        private final @Nullable S endState;
        private final Word<I> steps;

        /**
         * Since we need to compute the hash code quite often, cache it since we're immutable.
         */
        private final int hashCode;

        KWayTransition(@Nullable S startState, @Nullable S endState, Word<I> steps) {
            this.startState = startState;
            this.endState = endState;
            this.steps = steps;

            this.hashCode = computeHashCode(startState, endState, steps);
        }

        private int computeHashCode(@Nullable S startState, @Nullable S endState, Word<I> steps) {
            final int prime = 31;
            int result = 1;
            result = prime * result + Objects.hashCode(startState);
            result = prime * result + Objects.hashCode(endState);
            result = prime * result + Objects.hashCode(steps);
            return result;
        }

        @Override
        public boolean equals(@Nullable Object o) {
            return o == this || o instanceof KWayTransition<?, ?> that && Objects.equals(startState, that.startState) &&
                                Objects.equals(endState, that.endState) && steps.equals(that.steps);
        }

        @Override
        public int hashCode() {
            return hashCode;
        }
    }

    private record Path<S, I>(Word<I> steps, Set<KWayTransition<S, I>> kWayTransitions) {}

    /**
     * Method by which the prefixes of test words should be generated.
     */
    public enum GenerationMethod {
        /**
         * Generate prefixes randomly.
         */
        RANDOM {
            @Override
            <S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
                    KWayTransitionCoverTestsIterator<S, I, A> self,
                    S initial) {
                return self.new GreedySetCoverIterator(initial);
            }
        },
        /**
         * Generate prefixes based on access sequences.
         */
        PREFIX {
            @Override
            <S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
                    KWayTransitionCoverTestsIterator<S, I, A> self,
                    S initial) {
                return self.generatePrefixSteps(self.automaton, initial);
            }
        };

        abstract <S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
                KWayTransitionCoverTestsIterator<S, I, A> self,
                S initial);
    }

    /**
     * The metric by which to optimize path selection.
     */
    public enum OptimizationMetric {
        /**
         * Selects the paths maximum coverage per step, thus reducing the number of total steps.
         */
        STEPS {
            @Override
            <S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered) {
                return Comparator.comparingDouble(p -> ((double) sizeOfSetDifference(p.kWayTransitions, covered)) /
                                                       p.steps.size());
            }
        },
        /**
         * Selects the paths with maximum coverage, thus reducing number of test words.
         */
        QUERIES {
            @Override
            <S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered) {
                return Comparator.comparingInt(p -> sizeOfSetDifference(p.kWayTransitions, covered));
            }
        };

        abstract <S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered);
    }
}

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.ArrayList;
19	import java.util.Collection;
20	import java.util.Collections;
21	import java.util.Comparator;
22	import java.util.HashSet;
23	import java.util.Iterator;
24	import java.util.List;
25	import java.util.Objects;
26	import java.util.Random;
27	import java.util.Set;
28	import java.util.stream.Stream;
29
30	import net.automatalib.automaton.DeterministicAutomaton;
31	import net.automatalib.common.util.HashUtil;
32	import net.automatalib.common.util.collection.AbstractSimplifiedIterator;
33	import net.automatalib.common.util.collection.AbstractTwoLevelIterator;
34	import net.automatalib.common.util.collection.CollectionUtil;
35	import net.automatalib.common.util.collection.IterableUtil;
36	import net.automatalib.common.util.collection.IteratorUtil;
37	import net.automatalib.common.util.mapping.Mapping;
38	import net.automatalib.common.util.random.RandomUtil;
39	import net.automatalib.util.automaton.cover.Covers;
40	import net.automatalib.word.Word;
41	import net.automatalib.word.WordBuilder;
42	import org.checkerframework.checker.nullness.qual.Nullable;
43
44	/**
45	* A randomized transition cover test generator based on the concepts of mutation testing as described in the paper <a
46	* href="https://doi.org/10.1007/978-3-319-57288-8_2">Learning from Faults: Mutation Testing in Active Automata
47	* Learning</a> by Bernhard K. Aichernig and Martin Tappler.
48	* <p>
49	* This iterator selects test cases based on k-way transitions coverage. It does that by generating random test words
50	* and finding the smallest subset with the highest coverage. In other words, this iterator generates test words by
51	* running random paths that cover all pairwise / k-way transitions.
52	* <p>
53	* <b>Implementation detail:</b> Note that this test generator heavily relies on the sampling of states. If the given
54	* automaton has very few or very many states, the number of generated test cases may be very low or high, respectively.
55	* As a result, it may be advisable to {@link IteratorUtil#concat(Iterator[]) combine} this generator with other
56	* generators or {@link Stream#limit(long) limit} the number of generated test cases.
57	*
58	* @param <S>
59	* automaton state type
60	* @param <I>
61	* input symbol type
62	* @param <A>
63	* automaton type
64	*/
65	public class KWayTransitionCoverTestsIterator<S, I, A extends DeterministicAutomaton<S, I, ?>>
66	implements Iterator<Word<I>> {
67
68	/**
69	* The default value of k used in the k-way computations.
70	*/
71	public static final int DEFAULT_K = 2;
72
73	/**
74	* The default for the maximum step size of {@link GenerationMethod#RANDOM randomly}-generated paths.
75	*/
76	public static final int DEFAULT_MAX_PATH_LENGTH = 50;
77
78	/**
79	* The default (unlimited) threshold for the number of steps after which no more new test words will be generated.
80	*/
81	public static final int DEFAULT_MAX_NUM_STEPS = 0;
82
83	/**
84	* The default number of {@link GenerationMethod#RANDOM randomly}-generated tests used to find the optimal subset.
85	*/
86	public static final int DEFAULT_NUM_GEN_PATHS = 1_000;
87
88	/**
89	* The default number of steps that are appended to {@link GenerationMethod#PREFIX prefix}-generated paths.
90	*/
91	public static final int DEFAULT_R_WALK_LEN = 10;
92
93	private final A automaton;
94	private final List<? extends I> alphabet;
95	private final Random random;
96	private final int randomWalkLen;
97	private final int numGeneratePaths;
98	private final int maxPathLen;
99	private final int maxNumberOfSteps;
100	private final int k;
101	private final OptimizationMetric optimizationMetric;
102
103	private final Iterator<Word<I>> iterator;
104
105	/**
106	* Convenience constructor which uses a fresh {@code random} object.
107	*
108	* @param automaton
109	* the automaton for which to generate test cases
110	* @param inputs
111	* the inputs to consider for test case generation
112	*
113	* @see #KWayTransitionCoverTestsIterator(DeterministicAutomaton, Collection, Random)
114	*/
115	public KWayTransitionCoverTestsIterator(A automaton, Collection<? extends I> inputs) {
116	this(automaton, inputs, new Random());	2✔
117	}	2✔
118
119	/**
120	* Convenience constructor. Uses <code>randomWalkLen = {@value #DEFAULT_R_WALK_LEN}</code>, <code>numGeneratePaths =
121	* {@value #DEFAULT_NUM_GEN_PATHS}</code>, <code>maxPathLen = {@value #DEFAULT_MAX_PATH_LENGTH}</code>,
122	* <code>maxNumberOfSteps = {@value #DEFAULT_MAX_NUM_STEPS}</code>, <code>k = {@value DEFAULT_K}</code>,
123	* <code>optimizationMetric = {@link OptimizationMetric#STEPS STEPS}</code>, and <code>generationMethod =
124	* {@link GenerationMethod#RANDOM RANDOM}</code>.
125	*
126	* @param automaton
127	* the automaton for which to generate test cases
128	* @param inputs
129	* the inputs to consider for test case generation
130	* @param random
131	* the random number generator to use
132	*
133	* @see #KWayTransitionCoverTestsIterator(DeterministicAutomaton, Collection, Random, int, int, int, int, int,
134	* OptimizationMetric, GenerationMethod)
135	*/
136	public KWayTransitionCoverTestsIterator(A automaton, Collection<? extends I> inputs, Random random) {
137	this(automaton,	2✔
138	inputs,
139	random,
140	DEFAULT_R_WALK_LEN,
141	DEFAULT_NUM_GEN_PATHS,
142	DEFAULT_MAX_PATH_LENGTH,
143	DEFAULT_MAX_NUM_STEPS,
144	DEFAULT_K,
145	OptimizationMetric.STEPS,
146	GenerationMethod.RANDOM);
147	}	2✔
148
149	/**
150	* Constructor.
151	*
152	* @param automaton
153	* the automaton for which to generate test cases
154	* @param inputs
155	* the inputs to consider for test case generation
156	* @param random
157	* the random number generator to use
158	* @param randomWalkLen
159	* the number of steps that are appended to {@link GenerationMethod#PREFIX prefix}-generated paths
160	* @param numGeneratePaths
161	* number of {@link GenerationMethod#RANDOM randomly}-generated tests used to find the optimal subset
162	* @param maxPathLen
163	* the maximum step size of {@link GenerationMethod#RANDOM randomly}-generated paths
164	* @param maxNumberOfSteps
165	* threshold for the number of steps after which no more new test words will be generated (a value less than
166	* zero means no limit)
167	* @param k
168	* k value used for K-Way transitions, i.e.,the number of steps between the start and the end of a
169	* transition
170	* @param optimizationMetric
171	* the metric after which test cases are minimized
172	* @param generationMethod
173	* defines how the tests are generated
174	*/
175	public KWayTransitionCoverTestsIterator(A automaton,
176	Collection<? extends I> inputs,
177	Random random,
178	int randomWalkLen,
179	int numGeneratePaths,
180	int maxPathLen,
181	int maxNumberOfSteps,
182	int k,
183	OptimizationMetric optimizationMetric,
184	GenerationMethod generationMethod) {	2✔
185	this.automaton = automaton;	2✔
186	this.alphabet = CollectionUtil.randomAccessList(inputs);	2✔
187	this.random = random;	2✔
188
189	this.randomWalkLen = randomWalkLen;	2✔
190	this.numGeneratePaths = numGeneratePaths;	2✔
191	this.maxPathLen = maxPathLen;	2✔
192	this.maxNumberOfSteps = maxNumberOfSteps;	2✔
193	this.k = Math.min(k, automaton.size());	2✔
194	this.optimizationMetric = optimizationMetric;	2✔
195
196	final S initial = automaton.getInitialState();	2✔
197
198	if (automaton.size() == 0 \|\| initial == null) {	2✔
199	this.iterator = Collections.emptyIterator();	2✔
200	} else {
201	this.iterator = generationMethod.getIterator(this, initial);	2✔
202	}
203
204	}	2✔
205
206	@Override
207	public boolean hasNext() {
208	return iterator.hasNext();	2✔
209	}
210
211	@Override
212	public Word<I> next() {
213	return iterator.next();	2✔
214	}
215
216	private Set<Path<S, I>> generateRandomPaths(A hypothesis, S initial) {
217	final Set<Path<S, I>> result = new HashSet<>(HashUtil.capacity(numGeneratePaths));	2✔
218
219	for (int i = 0; i < numGeneratePaths; i++) {	2✔
220	final int randomLength = random.nextInt(maxPathLen - k + 1) + k; // Ensuring length is at least `k`	2✔
221	final Word<I> steps = Word.fromList(RandomUtil.sample(random, alphabet, randomLength));	2✔
222	final Path<S, I> path = createPath(hypothesis, initial, steps);	2✔
223	result.add(path);	2✔
224	}
225
226	return result;	2✔
227	}
228
229	private Path<S, I> createPath(A hypothesis, S initial, Word<I> steps) {
230	final Set<KWayTransition<S, I>> transitions = new HashSet<>();	2✔
231
232	final List<@Nullable S> prevStates = new ArrayList<>(steps.size());	2✔
233	final List<@Nullable S> endStates = new ArrayList<>(steps.size());	2✔
234
235	S iter = initial;	2✔
236
237	for (I i : steps) {	2✔
238	prevStates.add(iter);	2✔
239	iter = iter == null ? null : hypothesis.getSuccessor(iter, i);	2✔
240	endStates.add(iter);	2✔
241	}	2✔
242
243	for (int i = 0; i < steps.size() - k + 1; i++) {	2✔
244	final @Nullable S prevState = prevStates.get(i);	2✔
245	final @Nullable S endState = endStates.get(i + k - 1);	2✔
246	final Word<I> chunk = steps.subWord(i, i + k);	2✔
247
248	final KWayTransition<S, I> transition = new KWayTransition<>(prevState, endState, chunk);	2✔
249
250	transitions.add(transition);	2✔
251	}
252
253	return new Path<>(steps, transitions);	2✔
254	}
255
256	private Iterator<Word<I>> generatePrefixSteps(A hypothesis, S initial) {
257	final List<S> states = new ArrayList<>(hypothesis.getStates());	2✔
258	Collections.reverse(states);	2✔
259	return new PrefixStepsIterator(states.iterator(), initial);	2✔
260	}
261
262	private @Nullable Path<S, I> selectOptimalPath(Set<KWayTransition<S, I>> covered, Set<Path<S, I>> paths) {
263	final Path<S, I> max = Collections.max(paths, optimizationMetric.getPathComparator(covered));	2✔
264	return sizeOfSetDifference(max.kWayTransitions, covered) > 0 ? max : null;	2✔
265	}
266
267	static <T> int sizeOfSetDifference(Set<T> minuend, Set<T> subtrahend) {
268	/*
269	* This method is performance-critical so we do a little bit more involved computation.
270	*/
271	final Set<T> smaller, bigger;
272	if (minuend.size() < subtrahend.size()) {	2✔
273	smaller = minuend;	2✔
274	bigger = subtrahend;	2✔
275	} else {
276	smaller = subtrahend;	2✔
277	bigger = minuend;	2✔
278	}
279
280	int size = minuend.size();	2✔
281	for (T t : smaller) {	2✔
282	if (bigger.contains(t)) {	2✔
283	size--;	2✔
284	}
285	}	2✔
286	return size;	2✔
287	}
288
289	private class GreedySetCoverIterator extends AbstractSimplifiedIterator<Word<I>> {
290
291	private final S initial;
292	private final Set<Path<S, I>> paths;
293	private final Set<KWayTransition<S, I>> covered;
294	private final int sizeOfUniverse;
295
296	private int stepCount;
297
298	GreedySetCoverIterator(S initial) {	2✔
299	this.initial = initial;	2✔
300	this.paths = generateRandomPaths(automaton, initial);	2✔
301	this.covered = new HashSet<>();	2✔
302	this.stepCount = 0;	2✔
303	this.sizeOfUniverse = Math.multiplyExact(automaton.getStates().size(), (int) Math.pow(alphabet.size(), k));	2✔
304	}	2✔
305
306	@Override
307	protected boolean calculateNext() {
308	while (sizeOfUniverse > covered.size() && (maxNumberOfSteps == 0 \|\| stepCount <= maxNumberOfSteps)) {	2✔
309	final Path<S, I> path = selectOptimalPath(covered, paths);	2✔
310
311	if (path != null) {	2✔
312	covered.addAll(path.kWayTransitions);	2✔
313	paths.remove(path);	2✔
314	stepCount += path.steps.size();	2✔
315	super.nextValue = path.steps;	2✔
316
317	if (paths.isEmpty()) {	2✔
NEW 318	computeNewPaths();	×
319	}
320	return true;	2✔
321	} else {
322	computeNewPaths();	2✔
323	}
324	}	2✔
325	return false;	2✔
326	}
327
328	private void computeNewPaths() {
329	final Iterator<Word<I>> prefixIterator = generatePrefixSteps(automaton, initial);	2✔
330	while (prefixIterator.hasNext()) {	2✔
331	final Word<I> generatePrefixStep = prefixIterator.next();	2✔
332	paths.add(createPath(automaton, initial, generatePrefixStep));	2✔
333	}	2✔
334	}	2✔
335	}
336
337	private class PrefixStepsIterator extends AbstractTwoLevelIterator<S, List<I>, Word<I>> {
338
339	private final Mapping<S, @Nullable Word<I>> accessSequences;
340
341	PrefixStepsIterator(Iterator<S> iterator, S initial) {	2✔
342	super(iterator);	2✔
343	this.accessSequences = Covers.cover(automaton, alphabet, initial, w -> {}, w -> {});	2✔
344	}	2✔
345
346	@Override
347	protected Iterator<List<I>> l2Iterator(S state) {
348	/*
349	* The original code shuffles all tuples globally. Since we can't do this lazily, we approximate this
350	* behavior by at least shuffling the input symbols for a randomized tuple order.
351	*/
352	final List<I> inputs = new ArrayList<>(alphabet);	2✔
353	Collections.shuffle(inputs, random);	2✔
354	final Iterable<List<I>> lists = IterableUtil.allTuples(inputs, k);	2✔
355	return lists.iterator();	2✔
356	}
357
358	@Override
359	protected Word<I> combine(S state, List<I> steps) {
360	final Word<I> prefix = accessSequences.get(state);	2✔
361	if (prefix == null) {	2✔
362	return Word.epsilon();	2✔
363	}
364
365	final WordBuilder<I> wb = new WordBuilder<>(prefix.length() + steps.size() + randomWalkLen);	2✔
366
367	wb.append(prefix);	2✔
368	wb.append(steps);	2✔
369	wb.append(RandomUtil.sample(random, alphabet, randomWalkLen));	2✔
370
371	return wb.toWord();	2✔
372	}
373	}
374
375	private static final class KWayTransition<S, I> {
376
377	private final @Nullable S startState;
378	private final @Nullable S endState;
379	private final Word<I> steps;
380
381	/**
382	* Since we need to compute the hash code quite often, cache it since we're immutable.
383	*/
384	private final int hashCode;
385
386	KWayTransition(@Nullable S startState, @Nullable S endState, Word<I> steps) {	2✔
387	this.startState = startState;	2✔
388	this.endState = endState;	2✔
389	this.steps = steps;	2✔
390
391	this.hashCode = computeHashCode(startState, endState, steps);	2✔
392	}	2✔
393
394	private int computeHashCode(@Nullable S startState, @Nullable S endState, Word<I> steps) {
395	final int prime = 31;	2✔
396	int result = 1;	2✔
397	result = prime * result + Objects.hashCode(startState);	2✔
398	result = prime * result + Objects.hashCode(endState);	2✔
399	result = prime * result + Objects.hashCode(steps);	2✔
400	return result;	2✔
401	}
402
403	@Override
404	public boolean equals(@Nullable Object o) {
405	return o == this \|\| o instanceof KWayTransition<?, ?> that && Objects.equals(startState, that.startState) &&	2✔
406	Objects.equals(endState, that.endState) && steps.equals(that.steps);	2✔
407	}
408
409	@Override
410	public int hashCode() {
411	return hashCode;	2✔
412	}
413	}
414
415	private record Path<S, I>(Word<I> steps, Set<KWayTransition<S, I>> kWayTransitions) {}	2✔
416
417	/**
418	* Method by which the prefixes of test words should be generated.
419	*/
420	public enum GenerationMethod {	2✔
421	/**
422	* Generate prefixes randomly.
423	*/
424	RANDOM {	2✔
425	@Override
426	<S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
427	KWayTransitionCoverTestsIterator<S, I, A> self,
428	S initial) {
429	return self.new GreedySetCoverIterator(initial);	2✔
430	}
431	},
432	/**
433	* Generate prefixes based on access sequences.
434	*/
435	PREFIX {	2✔
436	@Override
437	<S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
438	KWayTransitionCoverTestsIterator<S, I, A> self,
439	S initial) {
440	return self.generatePrefixSteps(self.automaton, initial);	2✔
441	}
442	};
443
444	abstract <S, I, A extends DeterministicAutomaton<S, I, ?>> Iterator<Word<I>> getIterator(
445	KWayTransitionCoverTestsIterator<S, I, A> self,
446	S initial);
447	}
448
449	/**
450	* The metric by which to optimize path selection.
451	*/
452	public enum OptimizationMetric {	2✔
453	/**
454	* Selects the paths maximum coverage per step, thus reducing the number of total steps.
455	*/
456	STEPS {	2✔
457	@Override
458	<S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered) {
459	return Comparator.comparingDouble(p -> ((double) sizeOfSetDifference(p.kWayTransitions, covered)) /	2✔
460	p.steps.size());	2✔
461	}
462	},
463	/**
464	* Selects the paths with maximum coverage, thus reducing number of test words.
465	*/
466	QUERIES {	2✔
467	@Override
468	<S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered) {
469	return Comparator.comparingInt(p -> sizeOfSetDifference(p.kWayTransitions, covered));	2✔
470	}
471	};
472
473	abstract <S, I> Comparator<Path<S, I>> getPathComparator(Set<KWayTransition<S, I>> covered);
474	}
475	}

LearnLib / automatalib / 20242050438

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