6673301747

Committed 27 Oct 2023 11:46PM UTC coverage: 91.986% (-1.3%) from 93.327%

Build # 6673301747

Build Type

push

github

Committed by

mtf90

Commit Message

merge the release and sign-artifacts profiles

Run Details

10984 of 11941 relevant lines covered (91.99%)

1.72 hits per line

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

83.12

/filters/reuse/src/main/java/de/learnlib/filter/reuse/ReuseOracle.java

/* Copyright (C) 2013-2023 TU Dortmund
 * This file is part of LearnLib, http://www.learnlib.de/.
 *
 * 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 de.learnlib.filter.reuse;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.Set;
import java.util.function.Function;
import java.util.function.Supplier;

import de.learnlib.api.oracle.SingleQueryOracle.SingleQueryOracleMealy;
import de.learnlib.filter.reuse.ReuseCapableOracle.QueryResult;
import de.learnlib.filter.reuse.tree.BoundedDeque.AccessPolicy;
import de.learnlib.filter.reuse.tree.BoundedDeque.EvictPolicy;
import de.learnlib.filter.reuse.tree.ReuseNode;
import de.learnlib.filter.reuse.tree.ReuseNode.NodeResult;
import de.learnlib.filter.reuse.tree.ReuseTree;
import de.learnlib.filter.reuse.tree.ReuseTree.ReuseTreeBuilder;
import de.learnlib.filter.reuse.tree.SystemStateHandler;
import net.automatalib.alphabet.Alphabet;
import net.automatalib.word.Word;
import net.automatalib.word.WordBuilder;

/**
 * The reuse oracle is a {@link MealyMembershipOracle} that is able to <ul> <li>Cache queries: Each processed query will
 * not be delegated again (instead the answer will be retrieved from the {@link ReuseTree})</li> <li>Pump queries: If
 * the {@link ReuseTree} is configured to know which symbols are model invariant input symbols via {@link
 * ReuseOracleBuilder#withInvariantInputs(Set)} (like a read from a database which does not change the SUL) or
 * configured for failure output symbols via {@link ReuseOracleBuilder#withFailureOutputs(Set)} (e.g. a roll back
 * mechanism exists for the invoked symbol) the oracle could ''pump'' those symbols inside a query once seen.</li>
 * <li>Reuse system states: There are a lot of situations where a prefix of a query is already known and a system state
 * is available. In this situation the oracle is able to reuse the available system state and only process the remaining
 * suffix. Whether a system state will be removed after it is used is decided upon construction (see {@link
 * ReuseOracleBuilder#ReuseOracleBuilder(Alphabet, Supplier)}.</li> </ul> through an internal {@link ReuseTree}.
 * <p>
 * The usage of model invariant input symbols and failure output symbols is disabled by default and can be enabled upon
 * construction (see {@link ReuseOracleBuilder#withFailureOutputs(Set)} and {@link
 * ReuseOracleBuilder#withInvariantInputs(Set)}).
 *
 * @param <S>
 *         system state class
 * @param <I>
 *         input symbol class
 * @param <O>
 *         output symbol class
 */
public final class ReuseOracle<S, I, O> implements SingleQueryOracleMealy<I, O> {

    private final ThreadLocal<ReuseCapableOracle<S, I, O>> executableOracles;

    private final ReuseTree<S, I, O> tree;

    /**
     * Default constructor.
     */
    ReuseOracle(ReuseOracleBuilder<S, I, O> builder) {
        this.executableOracles = ThreadLocal.withInitial(builder.oracleSupplier);
        this.tree = new ReuseTreeBuilder<S, I, O>(builder.alphabet).withSystemStateHandler(builder.systemStateHandler)
                                                                   .withFailureOutputs(builder.failureOutputSymbols)
                                                                   .withInvariantInputs(builder.invariantInputSymbols)
                                                                   .withEnabledSystemstateInvalidation(builder.invalidateSystemStates)
                                                                   .withMaxSystemStates(builder.maxSystemStates)
                                                                   .withAccessPolicy(builder.accessPolicy)
                                                                   .withEvictPolicy(builder.evictPolicy)
                                                                   .build();
    }

    @Override
    public Word<O> answerQuery(Word<I> prefix, Word<I> suffix) {
        return processQuery(prefix.concat(suffix)).suffix(suffix.length());
    }

    @Override
    public Word<O> answerQuery(Word<I> input) {
        return processQuery(input);
    }

    /**
     * This method returns the full output to the input query.
     * <p>
     * It is possible that the query is already known (answer provided by {@link ReuseTree#getOutput(Word)}), the query
     * is new and no system state could be found for reuse ({@link ReuseCapableOracle#processQuery(Word)} will be
     * invoked) or there exists a prefix that (maybe epsilon) could be reused so save reset invocation ( {@link
     * ReuseCapableOracle#continueQuery(Word, Object)} will be invoked with remaining suffix and the corresponding
     * {@link ReuseNode} of the {@link ReuseTree}).
     */
    private Word<O> processQuery(Word<I> query) {
        Word<O> knownOutput = tree.getOutput(query);

        if (knownOutput != null) {
            return knownOutput;
        }

        // Search for system state
        final NodeResult<S, I, O> nodeResult = tree.fetchSystemState(query);
        final ReuseCapableOracle<S, I, O> oracle = getReuseCapableOracle();
        final Word<O> output;

        // No system state available
        if (nodeResult == null) {
            final QueryResult<S, O> newResult =
                    filterAndProcessQuery(query, tree.getPartialOutput(query), oracle::processQuery);

            tree.insert(query, newResult);

            output = newResult.output;
        } else { // System state available -> reuse
            final int suffixLen = query.size() - nodeResult.prefixLength;
            final Word<I> suffix = query.suffix(suffixLen);

            final Word<O> partialOutput = tree.getPartialOutput(query);
            final Word<O> partialSuffixOutput = partialOutput.suffix(suffixLen);

            final ReuseNode<S, I, O> reuseNode = nodeResult.reuseNode;
            final S systemState = nodeResult.systemState;

            final QueryResult<S, O> suffixQueryResult = filterAndProcessQuery(suffix,
                                                                              partialSuffixOutput,
                                                                              filteredInput -> oracle.continueQuery(
                                                                                      filteredInput,
                                                                                      systemState));

            this.tree.insert(suffix, reuseNode, suffixQueryResult);

            final Word<O> prefixOutput = tree.getOutput(query.prefix(nodeResult.prefixLength));
            output = new WordBuilder<>(prefixOutput).append(suffixQueryResult.output).toWord();
        }
        return output;
    }

    /**
     * Returns the {@link ReuseCapableOracle} used by this instance.
     */
    public ReuseCapableOracle<S, I, O> getReuseCapableOracle() {
        return executableOracles.get();
    }

    /**
     * Filters all the query elements corresponding to "reflexive" edges in the reuse tree, executes the shorter query,
     * and fills the filtered outputs into the resulting output word.
     *
     * @param query
     *         the input query with "reflexive" symbols (may be a suffix of the original query, if a system state is
     *         reused).
     * @param partialOutput
     *         the output information from the tree with {@code null} entries for all "non-reflexive" edges.
     * @param processQuery
     *         a function that actually processes the (shortened) query.
     *
     * @return the query result including the outputs of the "reflexive" symbol executions.
     */
    private QueryResult<S, O> filterAndProcessQuery(Word<I> query,
                                                    Word<O> partialOutput,
                                                    Function<Word<I>, QueryResult<S, O>> processQuery) {
        final LinkedList<I> filteredQueryList = new LinkedList<>(query.asList());
        final Iterator<I> queryIterator = filteredQueryList.iterator();

        // filter "reflexive" edges
        for (O outputSymbol : partialOutput) {
            queryIterator.next();
            if (outputSymbol != null) {
                queryIterator.remove();
            }
        }

        // process the query
        final QueryResult<S, O> res = processQuery.apply(Word.fromList(filteredQueryList));

        final WordBuilder<O> wordBuilder = new WordBuilder<>();
        final Iterator<O> resultIterator = res.output.iterator();

        // insert back the a priori available outputs of "reflexive" edges
        for (O output : partialOutput) {
            if (output == null) {
                wordBuilder.add(resultIterator.next());
            } else {
                wordBuilder.add(output);
            }
        }

        return new QueryResult<>(wordBuilder.toWord(), res.newState);
    }

    /**
     * Returns the {@link ReuseTree} used by this instance.
     */
    public ReuseTree<S, I, O> getReuseTree() {
        return this.tree;
    }

    public static class ReuseOracleBuilder<S, I, O> {

        private final Alphabet<I> alphabet;
        private final Supplier<? extends ReuseCapableOracle<S, I, O>> oracleSupplier;

        private boolean invalidateSystemStates = true;
        private SystemStateHandler<S> systemStateHandler;
        private Set<I> invariantInputSymbols;
        private Set<O> failureOutputSymbols;
        private int maxSystemStates = -1;
        private AccessPolicy accessPolicy = AccessPolicy.LIFO;
        private EvictPolicy evictPolicy = EvictPolicy.EVICT_OLDEST;

        public ReuseOracleBuilder(Alphabet<I> alphabet,
                                  Supplier<? extends ReuseCapableOracle<S, I, O>> oracleSupplier) {
            this.alphabet = alphabet;
            this.oracleSupplier = oracleSupplier;
        }

        public ReuseOracleBuilder<S, I, O> withSystemStateHandler(SystemStateHandler<S> systemStateHandler) {
            this.systemStateHandler = systemStateHandler;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withEnabledSystemStateInvalidation(boolean invalidate) {
            this.invalidateSystemStates = invalidate;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withInvariantInputs(Set<I> inputs) {
            this.invariantInputSymbols = inputs;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withFailureOutputs(Set<O> outputs) {
            this.failureOutputSymbols = outputs;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withMaxSystemStates(int maxSystemStates) {
            this.maxSystemStates = maxSystemStates;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withAccessPolicy(AccessPolicy accessPolicy) {
            this.accessPolicy = accessPolicy;
            return this;
        }

        public ReuseOracleBuilder<S, I, O> withEvictPolicy(EvictPolicy evictPolicy) {
            this.evictPolicy = evictPolicy;
            return this;
        }

        public ReuseOracle<S, I, O> build() {
            return new ReuseOracle<>(this);
        }
    }

}

1	/* Copyright (C) 2013-2023 TU Dortmund
2	* This file is part of LearnLib, http://www.learnlib.de/.
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 de.learnlib.filter.reuse;
17
18	import java.util.Iterator;
19	import java.util.LinkedList;
20	import java.util.Set;
21	import java.util.function.Function;
22	import java.util.function.Supplier;
23
24	import de.learnlib.api.oracle.SingleQueryOracle.SingleQueryOracleMealy;
25	import de.learnlib.filter.reuse.ReuseCapableOracle.QueryResult;
26	import de.learnlib.filter.reuse.tree.BoundedDeque.AccessPolicy;
27	import de.learnlib.filter.reuse.tree.BoundedDeque.EvictPolicy;
28	import de.learnlib.filter.reuse.tree.ReuseNode;
29	import de.learnlib.filter.reuse.tree.ReuseNode.NodeResult;
30	import de.learnlib.filter.reuse.tree.ReuseTree;
31	import de.learnlib.filter.reuse.tree.ReuseTree.ReuseTreeBuilder;
32	import de.learnlib.filter.reuse.tree.SystemStateHandler;
33	import net.automatalib.alphabet.Alphabet;
34	import net.automatalib.word.Word;
35	import net.automatalib.word.WordBuilder;
36
37	/**
38	* The reuse oracle is a {@link MealyMembershipOracle} that is able to <ul> <li>Cache queries: Each processed query will
39	* not be delegated again (instead the answer will be retrieved from the {@link ReuseTree})</li> <li>Pump queries: If
40	* the {@link ReuseTree} is configured to know which symbols are model invariant input symbols via {@link
41	* ReuseOracleBuilder#withInvariantInputs(Set)} (like a read from a database which does not change the SUL) or
42	* configured for failure output symbols via {@link ReuseOracleBuilder#withFailureOutputs(Set)} (e.g. a roll back
43	* mechanism exists for the invoked symbol) the oracle could ''pump'' those symbols inside a query once seen.</li>
44	* <li>Reuse system states: There are a lot of situations where a prefix of a query is already known and a system state
45	* is available. In this situation the oracle is able to reuse the available system state and only process the remaining
46	* suffix. Whether a system state will be removed after it is used is decided upon construction (see {@link
47	* ReuseOracleBuilder#ReuseOracleBuilder(Alphabet, Supplier)}.</li> </ul> through an internal {@link ReuseTree}.
48	* <p>
49	* The usage of model invariant input symbols and failure output symbols is disabled by default and can be enabled upon
50	* construction (see {@link ReuseOracleBuilder#withFailureOutputs(Set)} and {@link
51	* ReuseOracleBuilder#withInvariantInputs(Set)}).
52	*
53	* @param <S>
54	* system state class
55	* @param <I>
56	* input symbol class
57	* @param <O>
58	* output symbol class
59	*/
60	public final class ReuseOracle<S, I, O> implements SingleQueryOracleMealy<I, O> {
61
62	private final ThreadLocal<ReuseCapableOracle<S, I, O>> executableOracles;
63
64	private final ReuseTree<S, I, O> tree;
65
66	/**
67	* Default constructor.
68	*/
69	ReuseOracle(ReuseOracleBuilder<S, I, O> builder) {	2✔
70	this.executableOracles = ThreadLocal.withInitial(builder.oracleSupplier);	2✔
71	this.tree = new ReuseTreeBuilder<S, I, O>(builder.alphabet).withSystemStateHandler(builder.systemStateHandler)	2✔
72	.withFailureOutputs(builder.failureOutputSymbols)	2✔
73	.withInvariantInputs(builder.invariantInputSymbols)	2✔
74	.withEnabledSystemstateInvalidation(builder.invalidateSystemStates)	2✔
75	.withMaxSystemStates(builder.maxSystemStates)	2✔
76	.withAccessPolicy(builder.accessPolicy)	2✔
77	.withEvictPolicy(builder.evictPolicy)	2✔
78	.build();	2✔
79	}	2✔
80
81	@Override
82	public Word<O> answerQuery(Word<I> prefix, Word<I> suffix) {
83	return processQuery(prefix.concat(suffix)).suffix(suffix.length());	2✔
84	}
85
86	@Override
87	public Word<O> answerQuery(Word<I> input) {
88	return processQuery(input);	×
89	}
90
91	/**
92	* This method returns the full output to the input query.
93	* <p>
94	* It is possible that the query is already known (answer provided by {@link ReuseTree#getOutput(Word)}), the query
95	* is new and no system state could be found for reuse ({@link ReuseCapableOracle#processQuery(Word)} will be
96	* invoked) or there exists a prefix that (maybe epsilon) could be reused so save reset invocation ( {@link
97	* ReuseCapableOracle#continueQuery(Word, Object)} will be invoked with remaining suffix and the corresponding
98	* {@link ReuseNode} of the {@link ReuseTree}).
99	*/
100	private Word<O> processQuery(Word<I> query) {
101	Word<O> knownOutput = tree.getOutput(query);	2✔
102
103	if (knownOutput != null) {	2✔
104	return knownOutput;	2✔
105	}
106
107	// Search for system state
108	final NodeResult<S, I, O> nodeResult = tree.fetchSystemState(query);	2✔
109	final ReuseCapableOracle<S, I, O> oracle = getReuseCapableOracle();	2✔
110	final Word<O> output;
111
112	// No system state available
113	if (nodeResult == null) {	2✔
114	final QueryResult<S, O> newResult =	2✔
115	filterAndProcessQuery(query, tree.getPartialOutput(query), oracle::processQuery);	2✔
116
117	tree.insert(query, newResult);	2✔
118
119	output = newResult.output;	2✔
120	} else { // System state available -> reuse	2✔
121	final int suffixLen = query.size() - nodeResult.prefixLength;	2✔
122	final Word<I> suffix = query.suffix(suffixLen);	2✔
123
124	final Word<O> partialOutput = tree.getPartialOutput(query);	2✔
125	final Word<O> partialSuffixOutput = partialOutput.suffix(suffixLen);	2✔
126
127	final ReuseNode<S, I, O> reuseNode = nodeResult.reuseNode;	2✔
128	final S systemState = nodeResult.systemState;	2✔
129
130	final QueryResult<S, O> suffixQueryResult = filterAndProcessQuery(suffix,	2✔
131	partialSuffixOutput,
132	filteredInput -> oracle.continueQuery(	2✔
133	filteredInput,
134	systemState));
135
136	this.tree.insert(suffix, reuseNode, suffixQueryResult);	2✔
137
138	final Word<O> prefixOutput = tree.getOutput(query.prefix(nodeResult.prefixLength));	2✔
139	output = new WordBuilder<>(prefixOutput).append(suffixQueryResult.output).toWord();	2✔
140	}
141	return output;	2✔
142	}
143
144	/**
145	* Returns the {@link ReuseCapableOracle} used by this instance.
146	*/
147	public ReuseCapableOracle<S, I, O> getReuseCapableOracle() {
148	return executableOracles.get();	2✔
149	}
150
151	/**
152	* Filters all the query elements corresponding to "reflexive" edges in the reuse tree, executes the shorter query,
153	* and fills the filtered outputs into the resulting output word.
154	*
155	* @param query
156	* the input query with "reflexive" symbols (may be a suffix of the original query, if a system state is
157	* reused).
158	* @param partialOutput
159	* the output information from the tree with {@code null} entries for all "non-reflexive" edges.
160	* @param processQuery
161	* a function that actually processes the (shortened) query.
162	*
163	* @return the query result including the outputs of the "reflexive" symbol executions.
164	*/
165	private QueryResult<S, O> filterAndProcessQuery(Word<I> query,
166	Word<O> partialOutput,
167	Function<Word<I>, QueryResult<S, O>> processQuery) {
168	final LinkedList<I> filteredQueryList = new LinkedList<>(query.asList());	2✔
169	final Iterator<I> queryIterator = filteredQueryList.iterator();	2✔
170
171	// filter "reflexive" edges
172	for (O outputSymbol : partialOutput) {	2✔
173	queryIterator.next();	2✔
174	if (outputSymbol != null) {	2✔
175	queryIterator.remove();	×
176	}
177	}	2✔
178
179	// process the query
180	final QueryResult<S, O> res = processQuery.apply(Word.fromList(filteredQueryList));	2✔
181
182	final WordBuilder<O> wordBuilder = new WordBuilder<>();	2✔
183	final Iterator<O> resultIterator = res.output.iterator();	2✔
184
185	// insert back the a priori available outputs of "reflexive" edges
186	for (O output : partialOutput) {	2✔
187	if (output == null) {	2✔
188	wordBuilder.add(resultIterator.next());	2✔
189	} else {
190	wordBuilder.add(output);	×
191	}
192	}	2✔
193
194	return new QueryResult<>(wordBuilder.toWord(), res.newState);	2✔
195	}
196
197	/**
198	* Returns the {@link ReuseTree} used by this instance.
199	*/
200	public ReuseTree<S, I, O> getReuseTree() {
201	return this.tree;	2✔
202	}
203
204	public static class ReuseOracleBuilder<S, I, O> {
205
206	private final Alphabet<I> alphabet;
207	private final Supplier<? extends ReuseCapableOracle<S, I, O>> oracleSupplier;
208
209	private boolean invalidateSystemStates = true;	2✔
210	private SystemStateHandler<S> systemStateHandler;
211	private Set<I> invariantInputSymbols;
212	private Set<O> failureOutputSymbols;
213	private int maxSystemStates = -1;	2✔
214	private AccessPolicy accessPolicy = AccessPolicy.LIFO;	2✔
215	private EvictPolicy evictPolicy = EvictPolicy.EVICT_OLDEST;	2✔
216
217	public ReuseOracleBuilder(Alphabet<I> alphabet,
218	Supplier<? extends ReuseCapableOracle<S, I, O>> oracleSupplier) {	2✔
219	this.alphabet = alphabet;	2✔
220	this.oracleSupplier = oracleSupplier;	2✔
221	}	2✔
222
223	public ReuseOracleBuilder<S, I, O> withSystemStateHandler(SystemStateHandler<S> systemStateHandler) {
224	this.systemStateHandler = systemStateHandler;	×
225	return this;	×
226	}
227
228	public ReuseOracleBuilder<S, I, O> withEnabledSystemStateInvalidation(boolean invalidate) {
229	this.invalidateSystemStates = invalidate;	×
230	return this;	×
231	}
232
233	public ReuseOracleBuilder<S, I, O> withInvariantInputs(Set<I> inputs) {
234	this.invariantInputSymbols = inputs;	2✔
235	return this;	2✔
236	}
237
238	public ReuseOracleBuilder<S, I, O> withFailureOutputs(Set<O> outputs) {
239	this.failureOutputSymbols = outputs;	2✔
240	return this;	2✔
241	}
242
243	public ReuseOracleBuilder<S, I, O> withMaxSystemStates(int maxSystemStates) {
244	this.maxSystemStates = maxSystemStates;	×
245	return this;	×
246	}
247
248	public ReuseOracleBuilder<S, I, O> withAccessPolicy(AccessPolicy accessPolicy) {
249	this.accessPolicy = accessPolicy;	×
250	return this;	×
251	}
252
253	public ReuseOracleBuilder<S, I, O> withEvictPolicy(EvictPolicy evictPolicy) {
254	this.evictPolicy = evictPolicy;	×
255	return this;	×
256	}
257
258	public ReuseOracle<S, I, O> build() {
259	return new ReuseOracle<>(this);	2✔
260	}
261	}
262
263	}

LearnLib / learnlib / 6673301747

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