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

97.54

/algorithms/active/nlstar/src/main/java/de/learnlib/algorithms/nlstar/ObservationTable.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.algorithms.nlstar;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import de.learnlib.api.oracle.MembershipOracle;
import de.learnlib.api.query.DefaultQuery;
import net.automatalib.words.Alphabet;
import net.automatalib.words.Word;
import org.checkerframework.checker.nullness.qual.Nullable;

/**
 * The observation table implementation for the {@link NLStarLearner NL* algorithm}.
 *
 * @param <I>
 *         input symbol type
 */
public class ObservationTable<I> {

    private final Alphabet<I> alphabet;
    private final MembershipOracle<I, Boolean> oracle;

    private final List<Row<I>> upperRows = new ArrayList<>();
    private final List<Row<I>> allRows = new ArrayList<>();

    private final List<Row<I>> newUppers = new ArrayList<>();
    private final List<Row<I>> newRows = new ArrayList<>();

    private final List<Word<I>> suffixes = new ArrayList<>();
    private final Set<Word<I>> suffixSet = new HashSet<>();

    private final List<Row<I>> upperPrimes = new ArrayList<>();

    public ObservationTable(Alphabet<I> alphabet, MembershipOracle<I, Boolean> oracle) {
        this.alphabet = alphabet;
        this.oracle = oracle;
    }

    public List<List<Row<I>>> initialize() {
        if (!suffixes.isEmpty()) {
            throw new IllegalStateException();
        }

        Row<I> row = createRow(Word.epsilon());

        makeUpper(row);

        return addSuffix(Word.epsilon());
    }

    private Row<I> createRow(Word<I> prefix) {
        Row<I> row = new Row<>(prefix);
        allRows.add(row);
        newRows.add(row);
        return row;
    }

    public List<List<Row<I>>> addSuffix(Word<I> suffixToAdd) {
        return addSuffixes(Collections.singletonList(suffixToAdd));
    }

    private void makeUpper(Row<I> row) {
        makeUpper(Collections.singletonList(row));
    }

    public List<List<Row<I>>> makeUpper(List<Row<I>> rows) {
        List<Row<I>> newRows = new ArrayList<>(rows.size() * alphabet.size());
        for (Row<I> row : rows) {
            makeShort(row);
            Word<I> prefix = row.getPrefix();

            for (int i = 0; i < alphabet.size(); i++) {
                I sym = alphabet.getSymbol(i);
                Word<I> newPrefix = prefix.append(sym);
                Row<I> newRow = createRow(newPrefix);
                row.setSuccessorRow(i, newRow);
                newRows.add(newRow);
            }
        }

        if (suffixes.isEmpty()) {
            return Collections.emptyList();
        }

        int numSuffixes = suffixes.size();

        List<DefaultQuery<I, Boolean>> queries = new ArrayList<>(newRows.size() * numSuffixes);

        for (Row<I> newRow : newRows) {
            for (Word<I> suffix : suffixes) {
                queries.add(new DefaultQuery<>(newRow.getPrefix(), suffix));
            }
        }

        oracle.processQueries(queries);

        Iterator<DefaultQuery<I, Boolean>> queryIt = queries.iterator();

        for (Row<I> newRow : newRows) {
            newRow.fetchContents(queryIt, 0, numSuffixes);
        }

        return updateMetadata();

    }

    public List<List<Row<I>>> addSuffixes(List<? extends Word<I>> suffixesToAdd) {
        List<Word<I>> newSuffixes = new ArrayList<>();

        // we change the suffix list afterward
        @SuppressWarnings("PMD.PrematureDeclaration")
        int oldNumSuffixes = suffixes.size();

        for (Word<I> suffix : suffixesToAdd) {
            if (suffixSet.add(suffix)) {
                suffixes.add(suffix);
                newSuffixes.add(suffix);
            }
        }

        if (newSuffixes.isEmpty()) {
            return Collections.emptyList();
        }

        int numNewSuffixes = newSuffixes.size();

        List<DefaultQuery<I, Boolean>> queries = new ArrayList<>(allRows.size() * numNewSuffixes);

        for (Row<I> row : allRows) {
            Word<I> prefix = row.getPrefix();
            for (Word<I> suffix : newSuffixes) {
                queries.add(new DefaultQuery<>(prefix, suffix));
            }
        }

        oracle.processQueries(queries);

        Iterator<DefaultQuery<I, Boolean>> queryIt = queries.iterator();

        for (Row<I> row : allRows) {
            row.fetchContents(queryIt, oldNumSuffixes, numNewSuffixes);
        }

        return updateMetadata();
    }

    private void makeShort(Row<I> row) {
        row.makeShort(upperRows.size(), alphabet.size());
        upperRows.add(row);
        newUppers.add(row);
    }

    private List<List<Row<I>>> updateMetadata() {

        // Update coverage information
        for (Row<I> row : allRows) {
            if (row.isShortPrefixRow()) {
                if (row.isNew()) {
                    row.updateCovered(upperRows);
                } else {
                    row.updateCovered(newUppers);
                }
            } else {
                if (row.isNew()) {
                    row.updateCovered(allRows);
                } else {
                    row.updateCovered(newRows);
                }
            }
        }

        newRows.clear();
        newUppers.clear();

        upperPrimes.clear();

        Map<BitSet, List<Row<I>>> primeContents = new HashMap<>();
        List<List<Row<I>>> allUnclosed = new ArrayList<>();

        for (Row<I> row : allRows) {
            boolean prime = row.checkPrime();

            if (prime) {
                if (row.isShortPrefixRow()) {
                    upperPrimes.add(row);
                } else {
                    List<Row<I>> unclosedClass = primeContents.get(row.getContents());
                    if (unclosedClass == null) {
                        unclosedClass = new ArrayList<>();
                        allUnclosed.add(unclosedClass);
                        primeContents.put(row.getContents(), unclosedClass);
                    }
                    unclosedClass.add(row);
                }
            }
        }

        return allUnclosed;
    }

    public Word<I> getSuffix(int suffixIdx) {
        return suffixes.get(suffixIdx);
    }

    public List<Row<I>> getCoveredRows(Row<I> coveringRow) {
        return coveringRow.getCoveredRows();
    }

    public Row<I> getUpperRow(int index) {
        return upperRows.get(index);
    }

    public List<Row<I>> getUpperRows() {
        return upperRows;
    }

    public List<Row<I>> getUpperPrimes() {
        return upperPrimes;
    }

    public int getNumUpperRows() {
        return upperRows.size();
    }

    public @Nullable Inconsistency<I> findInconsistency() {
        for (Row<I> row1 : upperRows) {
            for (Row<I> row2 : row1.getCoveredRows()) {
                assert row2.isShortPrefixRow();

                for (int i = 0; i < alphabet.size(); i++) {
                    Row<I> row1succ = row1.getSuccessorRow(i);
                    Row<I> row2succ = row2.getSuccessorRow(i);

                    for (int j = 0; j < suffixes.size(); j++) {
                        if (!row1succ.getContent(j) && row2succ.getContent(j)) {
                            return new Inconsistency<>(row1, row2, i, j);
                        }
                    }
                }
            }
        }

        return null;
    }
}

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.algorithms.nlstar;
17
18	import java.util.ArrayList;
19	import java.util.BitSet;
20	import java.util.Collections;
21	import java.util.HashMap;
22	import java.util.HashSet;
23	import java.util.Iterator;
24	import java.util.List;
25	import java.util.Map;
26	import java.util.Set;
27
28	import de.learnlib.api.oracle.MembershipOracle;
29	import de.learnlib.api.query.DefaultQuery;
30	import net.automatalib.words.Alphabet;
31	import net.automatalib.words.Word;
32	import org.checkerframework.checker.nullness.qual.Nullable;
33
34	/**
35	* The observation table implementation for the {@link NLStarLearner NL* algorithm}.
36	*
37	* @param <I>
38	* input symbol type
39	*/
40	public class ObservationTable<I> {	2✔
41
42	private final Alphabet<I> alphabet;
43	private final MembershipOracle<I, Boolean> oracle;
44
45	private final List<Row<I>> upperRows = new ArrayList<>();	2✔
46	private final List<Row<I>> allRows = new ArrayList<>();	2✔
47
48	private final List<Row<I>> newUppers = new ArrayList<>();	2✔
49	private final List<Row<I>> newRows = new ArrayList<>();	2✔
50
51	private final List<Word<I>> suffixes = new ArrayList<>();	2✔
52	private final Set<Word<I>> suffixSet = new HashSet<>();	2✔
53
54	private final List<Row<I>> upperPrimes = new ArrayList<>();	2✔
55
56	public ObservationTable(Alphabet<I> alphabet, MembershipOracle<I, Boolean> oracle) {	2✔
57	this.alphabet = alphabet;	2✔
58	this.oracle = oracle;	2✔
59	}	2✔
60
61	public List<List<Row<I>>> initialize() {
62	if (!suffixes.isEmpty()) {	2✔
63	throw new IllegalStateException();	×
64	}
65
66	Row<I> row = createRow(Word.epsilon());	2✔
67
68	makeUpper(row);	2✔
69
70	return addSuffix(Word.epsilon());	2✔
71	}
72
73	private Row<I> createRow(Word<I> prefix) {
74	Row<I> row = new Row<>(prefix);	2✔
75	allRows.add(row);	2✔
76	newRows.add(row);	2✔
77	return row;	2✔
78	}
79
80	public List<List<Row<I>>> addSuffix(Word<I> suffixToAdd) {
81	return addSuffixes(Collections.singletonList(suffixToAdd));	2✔
82	}
83
84	private void makeUpper(Row<I> row) {
85	makeUpper(Collections.singletonList(row));	2✔
86	}	2✔
87
88	public List<List<Row<I>>> makeUpper(List<Row<I>> rows) {
89	List<Row<I>> newRows = new ArrayList<>(rows.size() * alphabet.size());	2✔
90	for (Row<I> row : rows) {	2✔
91	makeShort(row);	2✔
92	Word<I> prefix = row.getPrefix();	2✔
93
94	for (int i = 0; i < alphabet.size(); i++) {	2✔
95	I sym = alphabet.getSymbol(i);	2✔
96	Word<I> newPrefix = prefix.append(sym);	2✔
97	Row<I> newRow = createRow(newPrefix);	2✔
98	row.setSuccessorRow(i, newRow);	2✔
99	newRows.add(newRow);	2✔
100	}
101	}	2✔
102
103	if (suffixes.isEmpty()) {	2✔
104	return Collections.emptyList();	2✔
105	}
106
107	int numSuffixes = suffixes.size();	2✔
108
109	List<DefaultQuery<I, Boolean>> queries = new ArrayList<>(newRows.size() * numSuffixes);	2✔
110
111	for (Row<I> newRow : newRows) {	2✔
112	for (Word<I> suffix : suffixes) {	2✔
113	queries.add(new DefaultQuery<>(newRow.getPrefix(), suffix));	2✔
114	}	2✔
115	}	2✔
116
117	oracle.processQueries(queries);	2✔
118
119	Iterator<DefaultQuery<I, Boolean>> queryIt = queries.iterator();	2✔
120
121	for (Row<I> newRow : newRows) {	2✔
122	newRow.fetchContents(queryIt, 0, numSuffixes);	2✔
123	}	2✔
124
125	return updateMetadata();	2✔
126
127	}
128
129	public List<List<Row<I>>> addSuffixes(List<? extends Word<I>> suffixesToAdd) {
130	List<Word<I>> newSuffixes = new ArrayList<>();	2✔
131
132	// we change the suffix list afterward
133	@SuppressWarnings("PMD.PrematureDeclaration")
134	int oldNumSuffixes = suffixes.size();	2✔
135
136	for (Word<I> suffix : suffixesToAdd) {	2✔
137	if (suffixSet.add(suffix)) {	2✔
138	suffixes.add(suffix);	2✔
139	newSuffixes.add(suffix);	2✔
140	}
141	}	2✔
142
143	if (newSuffixes.isEmpty()) {	2✔
144	return Collections.emptyList();	×
145	}
146
147	int numNewSuffixes = newSuffixes.size();	2✔
148
149	List<DefaultQuery<I, Boolean>> queries = new ArrayList<>(allRows.size() * numNewSuffixes);	2✔
150
151	for (Row<I> row : allRows) {	2✔
152	Word<I> prefix = row.getPrefix();	2✔
153	for (Word<I> suffix : newSuffixes) {	2✔
154	queries.add(new DefaultQuery<>(prefix, suffix));	2✔
155	}	2✔
156	}	2✔
157
158	oracle.processQueries(queries);	2✔
159
160	Iterator<DefaultQuery<I, Boolean>> queryIt = queries.iterator();	2✔
161
162	for (Row<I> row : allRows) {	2✔
163	row.fetchContents(queryIt, oldNumSuffixes, numNewSuffixes);	2✔
164	}	2✔
165
166	return updateMetadata();	2✔
167	}
168
169	private void makeShort(Row<I> row) {
170	row.makeShort(upperRows.size(), alphabet.size());	2✔
171	upperRows.add(row);	2✔
172	newUppers.add(row);	2✔
173	}	2✔
174
175	private List<List<Row<I>>> updateMetadata() {
176
177	// Update coverage information
178	for (Row<I> row : allRows) {	2✔
179	if (row.isShortPrefixRow()) {	2✔
180	if (row.isNew()) {	2✔
181	row.updateCovered(upperRows);	2✔
182	} else {
183	row.updateCovered(newUppers);	2✔
184	}
185	} else {
186	if (row.isNew()) {	2✔
187	row.updateCovered(allRows);	2✔
188	} else {
189	row.updateCovered(newRows);	2✔
190	}
191	}
192	}	2✔
193
194	newRows.clear();	2✔
195	newUppers.clear();	2✔
196
197	upperPrimes.clear();	2✔
198
199	Map<BitSet, List<Row<I>>> primeContents = new HashMap<>();	2✔
200	List<List<Row<I>>> allUnclosed = new ArrayList<>();	2✔
201
202	for (Row<I> row : allRows) {	2✔
203	boolean prime = row.checkPrime();	2✔
204
205	if (prime) {	2✔
206	if (row.isShortPrefixRow()) {	2✔
207	upperPrimes.add(row);	2✔
208	} else {
209	List<Row<I>> unclosedClass = primeContents.get(row.getContents());	2✔
210	if (unclosedClass == null) {	2✔
211	unclosedClass = new ArrayList<>();	2✔
212	allUnclosed.add(unclosedClass);	2✔
213	primeContents.put(row.getContents(), unclosedClass);	2✔
214	}
215	unclosedClass.add(row);	2✔
216	}
217	}
218	}	2✔
219
220	return allUnclosed;	2✔
221	}
222
223	public Word<I> getSuffix(int suffixIdx) {
224	return suffixes.get(suffixIdx);	2✔
225	}
226
227	public List<Row<I>> getCoveredRows(Row<I> coveringRow) {
228	return coveringRow.getCoveredRows();	2✔
229	}
230
231	public Row<I> getUpperRow(int index) {
232	return upperRows.get(index);	2✔
233	}
234
235	public List<Row<I>> getUpperRows() {
236	return upperRows;	×
237	}
238
239	public List<Row<I>> getUpperPrimes() {
240	return upperPrimes;	2✔
241	}
242
243	public int getNumUpperRows() {
244	return upperRows.size();	2✔
245	}
246
247	public @Nullable Inconsistency<I> findInconsistency() {
248	for (Row<I> row1 : upperRows) {	2✔
249	for (Row<I> row2 : row1.getCoveredRows()) {	2✔
250	assert row2.isShortPrefixRow();	2✔
251
252	for (int i = 0; i < alphabet.size(); i++) {	2✔
253	Row<I> row1succ = row1.getSuccessorRow(i);	2✔
254	Row<I> row2succ = row2.getSuccessorRow(i);	2✔
255
256	for (int j = 0; j < suffixes.size(); j++) {	2✔
257	if (!row1succ.getContent(j) && row2succ.getContent(j)) {	2✔
258	return new Inconsistency<>(row1, row2, i, j);	2✔
259	}
260	}
261	}
262	}	2✔
263	}	2✔
264
265	return null;	2✔
266	}
267	}

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