6433387082

Committed 06 Oct 2023 03:10PM UTC coverage: 92.296% (-0.007%) from 92.303%

Build # 6433387082

Build Type

push

github

Committed by

mtf90

Commit Message

update Falk's developer id

Run Details

11573 of 12539 relevant lines covered (92.3%)

1.67 hits per line

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

95.83

/oracles/filters/cache/src/main/java/de/learnlib/filter/cache/mealy/SymbolQueryCache.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.cache.mealy;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Objects;

import de.learnlib.api.Resumable;
import de.learnlib.api.oracle.EquivalenceOracle;
import de.learnlib.api.oracle.SymbolQueryOracle;
import de.learnlib.api.query.DefaultQuery;
import de.learnlib.filter.cache.LearningCacheOracle.MealyLearningCacheOracle;
import de.learnlib.filter.cache.mealy.SymbolQueryCache.SymbolQueryCacheState;
import net.automatalib.automata.transducers.MealyMachine;
import net.automatalib.automata.transducers.impl.compact.CompactMealy;
import net.automatalib.util.automata.equivalence.NearLinearEquivalenceTest;
import net.automatalib.words.Alphabet;
import net.automatalib.words.Word;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * A cache for a {@link SymbolQueryOracle}. Upon construction, it is provided with a delegate oracle. Queries that can
 * be answered from the cache are answered directly, others are forwarded to the delegate oracle. Queried symbols that
 * have to be delegated are incorporated into the cache directly.
 * <p>
 * Internally, an incrementally growing tree (in form of a mealy automaton) is used for caching.
 *
 * @param <I>
 *         input alphabet type
 * @param <O>
 *         output alphabet type
 */
public class SymbolQueryCache<I, O>
        implements SymbolQueryOracle<I, O>, MealyLearningCacheOracle<I, O>, Resumable<SymbolQueryCacheState<I, O>> {

    private CompactMealy<I, O> cache;
    private final SymbolQueryOracle<I, O> delegate;

    private final List<I> currentTrace;
    private Integer currentState;
    private boolean currentTraceValid;

    SymbolQueryCache(SymbolQueryOracle<I, O> delegate, Alphabet<I> alphabet) {
        this.delegate = delegate;
        this.cache = new CompactMealy<>(alphabet);
        this.currentState = this.cache.addInitialState();

        this.currentTrace = new ArrayList<>();
        this.currentTraceValid = false;
    }

    @Override
    public O query(I i) {

        if (this.currentTraceValid) {
            final Integer succ = this.cache.getSuccessor(this.currentState, i);

            if (succ != null) {
                final O output = this.cache.getOutput(this.currentState, i);
                assert output != null;
                this.currentTrace.add(i);
                this.currentState = succ;
                return output;
            } else {
                this.currentTraceValid = false;
                this.delegate.reset();

                this.currentTrace.forEach(this.delegate::query);
            }
        }

        final O output = this.delegate.query(i);

        final Integer nextState;
        final Integer succ = this.cache.getSuccessor(this.currentState, i);

        if (succ == null) {
            final Integer newState = this.cache.addState();
            this.cache.addTransition(this.currentState, i, newState, output);
            nextState = newState;
        } else {
            assert Objects.equals(this.cache.getOutput(this.currentState, i), output);
            nextState = succ;
        }

        this.currentState = nextState;

        return output;
    }

    @Override
    public void reset() {
        Integer init = this.cache.getInitialState();
        assert init != null;
        this.currentState = init;
        this.currentTrace.clear();
        this.currentTraceValid = true;
    }

    @Override
    public EquivalenceOracle<MealyMachine<?, I, ?, O>, I, Word<O>> createCacheConsistencyTest() {
        return this::findCounterexample;
    }

    private @Nullable DefaultQuery<I, Word<O>> findCounterexample(MealyMachine<?, I, ?, O> hypothesis,
                                                                  Collection<? extends I> alphabet) {
        /*
        TODO: potential optimization: If the hypothesis has undefined transitions, but the cache doesn't, it is a clear
        counterexample!
         */
        final Word<I> sepWord = NearLinearEquivalenceTest.findSeparatingWord(cache, hypothesis, alphabet, true);

        if (sepWord != null) {
            return new DefaultQuery<>(sepWord, cache.computeOutput(sepWord));
        }

        return null;
    }

    @Override
    public SymbolQueryCacheState<I, O> suspend() {
        return new SymbolQueryCacheState<>(cache);
    }

    @Override
    public void resume(SymbolQueryCacheState<I, O> state) {
        this.cache = state.getCache();
    }

    public static class SymbolQueryCacheState<I, O> {

        private final CompactMealy<I, O> cache;

        SymbolQueryCacheState(CompactMealy<I, O> cache) {
            this.cache = cache;
        }

        CompactMealy<I, O> getCache() {
            return cache;
        }
    }
}

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.cache.mealy;
17
18	import java.util.ArrayList;
19	import java.util.Collection;
20	import java.util.List;
21	import java.util.Objects;
22
23	import de.learnlib.api.Resumable;
24	import de.learnlib.api.oracle.EquivalenceOracle;
25	import de.learnlib.api.oracle.SymbolQueryOracle;
26	import de.learnlib.api.query.DefaultQuery;
27	import de.learnlib.filter.cache.LearningCacheOracle.MealyLearningCacheOracle;
28	import de.learnlib.filter.cache.mealy.SymbolQueryCache.SymbolQueryCacheState;
29	import net.automatalib.automata.transducers.MealyMachine;
30	import net.automatalib.automata.transducers.impl.compact.CompactMealy;
31	import net.automatalib.util.automata.equivalence.NearLinearEquivalenceTest;
32	import net.automatalib.words.Alphabet;
33	import net.automatalib.words.Word;
34	import org.checkerframework.checker.nullness.qual.Nullable;
35
36	/**
37	* A cache for a {@link SymbolQueryOracle}. Upon construction, it is provided with a delegate oracle. Queries that can
38	* be answered from the cache are answered directly, others are forwarded to the delegate oracle. Queried symbols that
39	* have to be delegated are incorporated into the cache directly.
40	* <p>
41	* Internally, an incrementally growing tree (in form of a mealy automaton) is used for caching.
42	*
43	* @param <I>
44	* input alphabet type
45	* @param <O>
46	* output alphabet type
47	*/
48	public class SymbolQueryCache<I, O>	2✔
49	implements SymbolQueryOracle<I, O>, MealyLearningCacheOracle<I, O>, Resumable<SymbolQueryCacheState<I, O>> {
50
51	private CompactMealy<I, O> cache;
52	private final SymbolQueryOracle<I, O> delegate;
53
54	private final List<I> currentTrace;
55	private Integer currentState;
56	private boolean currentTraceValid;
57
58	SymbolQueryCache(SymbolQueryOracle<I, O> delegate, Alphabet<I> alphabet) {	2✔
59	this.delegate = delegate;	2✔
60	this.cache = new CompactMealy<>(alphabet);	2✔
61	this.currentState = this.cache.addInitialState();	2✔
62
63	this.currentTrace = new ArrayList<>();	2✔
64	this.currentTraceValid = false;	2✔
65	}	2✔
66
67	@Override
68	public O query(I i) {
69
70	if (this.currentTraceValid) {	2✔
71	final Integer succ = this.cache.getSuccessor(this.currentState, i);	2✔
72
73	if (succ != null) {	2✔
74	final O output = this.cache.getOutput(this.currentState, i);	2✔
75	assert output != null;	2✔
76	this.currentTrace.add(i);	2✔
77	this.currentState = succ;	2✔
78	return output;	2✔
79	} else {
80	this.currentTraceValid = false;	2✔
81	this.delegate.reset();	2✔
82
83	this.currentTrace.forEach(this.delegate::query);	2✔
84	}
85	}
86
87	final O output = this.delegate.query(i);	2✔
88
89	final Integer nextState;
90	final Integer succ = this.cache.getSuccessor(this.currentState, i);	2✔
91
92	if (succ == null) {	2✔
93	final Integer newState = this.cache.addState();	2✔
94	this.cache.addTransition(this.currentState, i, newState, output);	2✔
95	nextState = newState;	2✔
96	} else {	2✔
97	assert Objects.equals(this.cache.getOutput(this.currentState, i), output);	×
98	nextState = succ;	×
99	}
100
101	this.currentState = nextState;	2✔
102
103	return output;	2✔
104	}
105
106	@Override
107	public void reset() {
108	Integer init = this.cache.getInitialState();	2✔
109	assert init != null;	2✔
110	this.currentState = init;	2✔
111	this.currentTrace.clear();	2✔
112	this.currentTraceValid = true;	2✔
113	}	2✔
114
115	@Override
116	public EquivalenceOracle<MealyMachine<?, I, ?, O>, I, Word<O>> createCacheConsistencyTest() {
117	return this::findCounterexample;	2✔
118	}
119
120	private @Nullable DefaultQuery<I, Word<O>> findCounterexample(MealyMachine<?, I, ?, O> hypothesis,
121	Collection<? extends I> alphabet) {
122	/*
123	TODO: potential optimization: If the hypothesis has undefined transitions, but the cache doesn't, it is a clear
124	counterexample!
125	*/
126	final Word<I> sepWord = NearLinearEquivalenceTest.findSeparatingWord(cache, hypothesis, alphabet, true);	2✔
127
128	if (sepWord != null) {	2✔
129	return new DefaultQuery<>(sepWord, cache.computeOutput(sepWord));	2✔
130	}
131
132	return null;	2✔
133	}
134
135	@Override
136	public SymbolQueryCacheState<I, O> suspend() {
137	return new SymbolQueryCacheState<>(cache);	2✔
138	}
139
140	@Override
141	public void resume(SymbolQueryCacheState<I, O> state) {
142	this.cache = state.getCache();	2✔
143	}	2✔
144
145	public static class SymbolQueryCacheState<I, O> {
146
147	private final CompactMealy<I, O> cache;
148
149	SymbolQueryCacheState(CompactMealy<I, O> cache) {	2✔
150	this.cache = cache;	2✔
151	}	2✔
152
153	CompactMealy<I, O> getCache() {
154	return cache;	2✔
155	}
156	}
157	}

LearnLib / learnlib / 6433387082

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