12651580329

Committed 07 Jan 2025 12:29PM UTC coverage: 91.569% (+0.03%) from 91.542%

Build # 12651580329

Build Type

push

github

Committed by

web-flow

Commit Message

Update dependencies (#85)

* bump basic dependency versions

* bump checkstyle + cleanups

* bump spotbugs + cleanups

* bump pmd + cleanups

* bump checkerframework + cleanups

* some more cleanups

* ExceptionUtil: support nulls

* improve comments

* cleanup naming + formatting

* formatting

* formatting

* do not fail on javadoc warnings

completness of documentation is now checked by checkstyle and we would have to disable failing anyways when moving on to JDK 17

Run Details

192 of 217 new or added lines in 63 files covered. (88.48%)

4 existing lines in 4 files now uncovered.

16573 of 18099 relevant lines covered (91.57%)

1.69 hits per line

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

96.15

/incremental/src/main/java/net/automatalib/incremental/dfa/dag/IncrementalPCDFADAGBuilder.java

/* Copyright (C) 2013-2024 TU Dortmund University
 * This file is part of AutomataLib, http://www.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.incremental.dfa.dag;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;

import net.automatalib.alphabet.Alphabet;
import net.automatalib.incremental.ConflictException;
import net.automatalib.incremental.dfa.Acceptance;
import net.automatalib.word.Word;

/**
 * The prefix-closed version of {@link IncrementalDFADAGBuilder}. Contrary to the regular lookup semantics, where an
 * exact response to a lookup can only be given, if the exact word has been observed before, the prefix-closed semantics
 * behave as follows:
 *
 * <ul>
 * <li>prefixes of previously observed accepted words will result in a {@link Acceptance#TRUE} response as well.</li>
 * <li>continuations of previously observed rejected words will result in a {@link Acceptance#FALSE} response as
 * well.</li>
 * </ul>
 *
 * @param <I>
 *         input symbol class
 */
public class IncrementalPCDFADAGBuilder<I> extends AbstractIncrementalDFADAGBuilder<I> {

    public IncrementalPCDFADAGBuilder(Alphabet<I> inputAlphabet) {
        super(inputAlphabet);
    }

    @Override
    public Acceptance lookup(Word<? extends I> word) {
        State s = getState(word);
        if (s == null) {
            return Acceptance.DONT_KNOW;
        }
        return s == sink ? Acceptance.FALSE : s.getAcceptance();
    }

    @Override
    State getState(Word<? extends I> word) {

        if (init.getAcceptance() == Acceptance.FALSE) {
            return sink;
        }

        State s = init;
        for (I sym : word) {
            int idx = inputAlphabet.getSymbolIndex(sym);
            s = s.getSuccessor(idx);
            if (s == null || s == sink) {
                return s;
            }
        }
        return s;
    }

    @Override
    public void insert(Word<? extends I> word, boolean accepting) {

        State curr = init;
        State conf = null;

        Deque<Transition> path = new ArrayDeque<>();

        for (I sym : word) {
            if (curr.getAcceptance() == Acceptance.FALSE) {
                if (accepting) {
                    throw new ConflictException("Conflict");
                }
                return;
            }

            if (conf == null && curr.isConfluence()) {
                conf = curr;
            }

            int idx = inputAlphabet.getSymbolIndex(sym);

            State succ = curr.getSuccessor(idx);
            if (succ == null) {
                break;
            }
            path.push(new Transition(curr, idx));
            curr = succ;
        }

        int len = word.length();
        Acceptance acc = Acceptance.fromBoolean(accepting);
        int prefixLen = path.size();

        State last = curr;

        if (prefixLen == len) {
            Acceptance currAcc = curr.getAcceptance();
            if (currAcc == acc) {
                return;
            }
            if (currAcc != Acceptance.DONT_KNOW) {
                throw new ConflictException("Incompatible acceptances: " + currAcc + " vs " + acc);
            }
            if (accepting) {
                if (conf != null || last.isConfluence()) {
                    last = clone(last, Acceptance.TRUE);
                } else if (last == init) {
                    updateInitSignature(Acceptance.TRUE);
                    return;
                } else {
                    last = updateSignature(last, acc);
                }
            } else {
                // once we insert a rejected word, we need a sink
                if (sink == null) {
                    sink = State.SINK;
                }
                if (conf == null && !last.isConfluence()) {
                    purge(last);
                }
                if (last == init) {
                    updateInitSignature(Acceptance.FALSE);
                    return;
                }
                last = sink;
            }
        } else {
            if (conf != null) {
                if (conf == last) {
                    conf = null;
                }
                last = hiddenClone(last);
                if (conf == null) {
                    Transition peek = path.peek();
                    assert peek != null;
                    State prev = peek.state;
                    if (prev == init) {
                        updateInitSignature(peek.transIdx, last);
                    } else {
                        updateSignature(prev, peek.transIdx, last);
                    }
                }
            } else if (last != init) {
                hide(last);
            }

            Word<? extends I> suffix = word.subWord(prefixLen);
            I sym = suffix.firstSymbol();
            int suffTransIdx = inputAlphabet.getSymbolIndex(sym);
            State suffixState = createSuffix(suffix.subWord(1), accepting);

            if (last == init) {
                if (accepting) {
                    updateInitSignature(Acceptance.TRUE, suffTransIdx, suffixState);
                } else {
                    updateInitSignature(suffTransIdx, suffixState);
                }
            } else {
                if (accepting) {
                    last = unhide(last, Acceptance.TRUE, suffTransIdx, suffixState);
                } else {
                    last = unhide(last, suffTransIdx, suffixState);
                }

                if (conf != null) {
                    // in case of a cyclic structure, the suffix may make predecessors of 'conf' confluent due to un-hiding
                    // update the reference with whatever confluent state comes first
                    final Iterator<Transition> iter = path.descendingIterator();
                    while (iter.hasNext()) {
                        final State s = iter.next().state;
                        if (s.isConfluence()) {
                            conf = s;
                            break;
                        }
                    }
                }
            }
        }

        if (path.isEmpty()) {
            return;
        }

        if (conf != null) {
            Transition next;
            do {
                next = path.pop();
                State state = next.state;
                int idx = next.transIdx;
                if (accepting) {
                    state = clone(state, Acceptance.TRUE, idx, last);
                } else {
                    state = clone(state, idx, last);
                }
                last = state;
            } while (next.state != conf);
        }

        while (path.size() > 1) {
            Transition next = path.pop();
            State state = next.state;
            int idx = next.transIdx;

            // when extending the path we previously traversed (i.e. expanding the suffix), it may happen that we end up
            // adding a cyclic transition. If this is the case, simply clone the current state and update the parent in
            // the next iteration
            if (state == last) {
                last = clone(state, idx, last);
                continue;
            }

            State updated;
            Acceptance oldAcc = state.getAcceptance();
            if (accepting) {
                updated = updateSignature(state, Acceptance.TRUE, idx, last);
            } else {
                updated = updateSignature(state, idx, last);
            }
            if (state == updated && oldAcc == updated.getAcceptance()) {
                return;
            }
            last = updated;
        }

        int finalIdx = path.pop().transIdx;

        if (accepting) {
            updateInitSignature(Acceptance.TRUE, finalIdx, last);
        } else {
            updateInitSignature(finalIdx, last);
        }
    }

    /**
     * Removes a state and all of its (non-confluent) successors from the register.
     *
     * @param state
     *         the state to purge
     */
    private void purge(State state) {
        StateSignature sig = state.getSignature();
        if (sig == null) {
            return;
        }
        if (state.getAcceptance() == Acceptance.TRUE) {
            throw new IllegalStateException("Attempting to purge accepting state");
        }
        if (register.remove(sig) == null) {
            return;
        }
        sig.acceptance = Acceptance.FALSE;
        for (int i = 0; i < alphabetSize; i++) {
            State succ = sig.successors.array[i];
            if (succ != null) {
                if (succ.isConfluence()) {
                    succ.decreaseIncoming();
                } else {
                    purge(succ);
                }
            }
        }
    }

    /**
     * Creates a suffix state sequence, i.e., a linear sequence of states connected by transitions labeled by the
     * letters of the given suffix word.
     *
     * @param suffix
     *         the suffix word
     * @param accepting
     *         whether the final state should be accepting
     *
     * @return the first state in the sequence
     */
    private State createSuffix(Word<? extends I> suffix, boolean accepting) {
        State last;
        Acceptance intermediate;
        if (accepting) {
            StateSignature sig = new StateSignature(alphabetSize, Acceptance.TRUE);
            last = replaceOrRegister(sig);
            intermediate = Acceptance.TRUE;
        } else {
            if (sink == null) {
                sink = State.SINK;
            }
            last = sink;
            intermediate = Acceptance.DONT_KNOW;
        }

        int len = suffix.length();
        for (int i = len - 1; i >= 0; i--) {
            StateSignature sig = new StateSignature(alphabetSize, intermediate);
            I sym = suffix.getSymbol(i);
            int idx = inputAlphabet.getSymbolIndex(sym);
            sig.successors.array[idx] = last;
            last = replaceOrRegister(sig);
        }

        return last;
    }

}

1	/* Copyright (C) 2013-2024 TU Dortmund University
2	* This file is part of AutomataLib, http://www.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.incremental.dfa.dag;
17
18	import java.util.ArrayDeque;
19	import java.util.Deque;
20	import java.util.Iterator;
21
22	import net.automatalib.alphabet.Alphabet;
23	import net.automatalib.incremental.ConflictException;
24	import net.automatalib.incremental.dfa.Acceptance;
25	import net.automatalib.word.Word;
26
27	/**
28	* The prefix-closed version of {@link IncrementalDFADAGBuilder}. Contrary to the regular lookup semantics, where an
29	* exact response to a lookup can only be given, if the exact word has been observed before, the prefix-closed semantics
30	* behave as follows:
31	*
32	* <ul>
33	* <li>prefixes of previously observed accepted words will result in a {@link Acceptance#TRUE} response as well.</li>
34	* <li>continuations of previously observed rejected words will result in a {@link Acceptance#FALSE} response as
35	* well.</li>
36	* </ul>
37	*
38	* @param <I>
39	* input symbol class
40	*/
41	public class IncrementalPCDFADAGBuilder<I> extends AbstractIncrementalDFADAGBuilder<I> {	2✔
42
43	public IncrementalPCDFADAGBuilder(Alphabet<I> inputAlphabet) {
44	super(inputAlphabet);	2✔
45	}	2✔
46
47	@Override
48	public Acceptance lookup(Word<? extends I> word) {
49	State s = getState(word);	2✔
50	if (s == null) {	2✔
51	return Acceptance.DONT_KNOW;	2✔
52	}
53	return s == sink ? Acceptance.FALSE : s.getAcceptance();	2✔
54	}
55
56	@Override
57	State getState(Word<? extends I> word) {
58
59	if (init.getAcceptance() == Acceptance.FALSE) {	2✔
60	return sink;	2✔
61	}
62
63	State s = init;	2✔
64	for (I sym : word) {	2✔
65	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
66	s = s.getSuccessor(idx);	2✔
67	if (s == null \|\| s == sink) {	2✔
68	return s;	2✔
69	}
70	}	2✔
71	return s;	2✔
72	}
73
74	@Override
75	public void insert(Word<? extends I> word, boolean accepting) {
76
77	State curr = init;	2✔
78	State conf = null;	2✔
79
80	Deque<Transition> path = new ArrayDeque<>();	2✔
81
82	for (I sym : word) {	2✔
83	if (curr.getAcceptance() == Acceptance.FALSE) {	2✔
84	if (accepting) {	2✔
85	throw new ConflictException("Conflict");	2✔
86	}
87	return;	2✔
88	}
89
90	if (conf == null && curr.isConfluence()) {	2✔
91	conf = curr;	2✔
92	}
93
94	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
95
96	State succ = curr.getSuccessor(idx);	2✔
97	if (succ == null) {	2✔
98	break;	2✔
99	}
100	path.push(new Transition(curr, idx));	2✔
101	curr = succ;	2✔
102	}	2✔
103
104	int len = word.length();	2✔
105	Acceptance acc = Acceptance.fromBoolean(accepting);	2✔
106	int prefixLen = path.size();	2✔
107
108	State last = curr;	2✔
109
110	if (prefixLen == len) {	2✔
111	Acceptance currAcc = curr.getAcceptance();	2✔
112	if (currAcc == acc) {	2✔
113	return;	2✔
114	}
115	if (currAcc != Acceptance.DONT_KNOW) {	2✔
116	throw new ConflictException("Incompatible acceptances: " + currAcc + " vs " + acc);	2✔
117	}
118	if (accepting) {	2✔
119	if (conf != null \|\| last.isConfluence()) {	2✔
120	last = clone(last, Acceptance.TRUE);	2✔
121	} else if (last == init) {	2✔
122	updateInitSignature(Acceptance.TRUE);	2✔
123	return;	2✔
124	} else {
125	last = updateSignature(last, acc);	2✔
126	}
127	} else {
128	// once we insert a rejected word, we need a sink
129	if (sink == null) {	2✔
130	sink = State.SINK;	2✔
131	}
132	if (conf == null && !last.isConfluence()) {	2✔
133	purge(last);	2✔
134	}
135	if (last == init) {	2✔
136	updateInitSignature(Acceptance.FALSE);	2✔
137	return;	2✔
138	}
139	last = sink;	2✔
140	}
141	} else {	2✔
142	if (conf != null) {	2✔
143	if (conf == last) {	2✔
144	conf = null;	2✔
145	}
146	last = hiddenClone(last);	2✔
147	if (conf == null) {	2✔
148	Transition peek = path.peek();	2✔
149	assert peek != null;	2✔
150	State prev = peek.state;	2✔
151	if (prev == init) {	2✔
UNCOV 152	updateInitSignature(peek.transIdx, last);	×
153	} else {
154	updateSignature(prev, peek.transIdx, last);	2✔
155	}
156	}	2✔
157	} else if (last != init) {	2✔
158	hide(last);	2✔
159	}
160
161	Word<? extends I> suffix = word.subWord(prefixLen);	2✔
162	I sym = suffix.firstSymbol();	2✔
163	int suffTransIdx = inputAlphabet.getSymbolIndex(sym);	2✔
164	State suffixState = createSuffix(suffix.subWord(1), accepting);	2✔
165
166	if (last == init) {	2✔
167	if (accepting) {	2✔
168	updateInitSignature(Acceptance.TRUE, suffTransIdx, suffixState);	2✔
169	} else {
170	updateInitSignature(suffTransIdx, suffixState);	2✔
171	}
172	} else {
173	if (accepting) {	2✔
174	last = unhide(last, Acceptance.TRUE, suffTransIdx, suffixState);	2✔
175	} else {
176	last = unhide(last, suffTransIdx, suffixState);	2✔
177	}
178
179	if (conf != null) {	2✔
180	// in case of a cyclic structure, the suffix may make predecessors of 'conf' confluent due to un-hiding
181	// update the reference with whatever confluent state comes first
182	final Iterator<Transition> iter = path.descendingIterator();	2✔
183	while (iter.hasNext()) {	2✔
184	final State s = iter.next().state;	2✔
185	if (s.isConfluence()) {	2✔
186	conf = s;	2✔
187	break;	2✔
188	}
189	}	2✔
190	}
191	}
192	}
193
194	if (path.isEmpty()) {	2✔
195	return;	2✔
196	}
197
198	if (conf != null) {	2✔
199	Transition next;
200	do {
201	next = path.pop();	2✔
202	State state = next.state;	2✔
203	int idx = next.transIdx;	2✔
204	if (accepting) {	2✔
205	state = clone(state, Acceptance.TRUE, idx, last);	2✔
206	} else {
207	state = clone(state, idx, last);	2✔
208	}
209	last = state;	2✔
210	} while (next.state != conf);	2✔
211	}
212
213	while (path.size() > 1) {	2✔
214	Transition next = path.pop();	2✔
215	State state = next.state;	2✔
216	int idx = next.transIdx;	2✔
217
218	// when extending the path we previously traversed (i.e. expanding the suffix), it may happen that we end up
219	// adding a cyclic transition. If this is the case, simply clone the current state and update the parent in
220	// the next iteration
221	if (state == last) {	2✔
222	last = clone(state, idx, last);	×
223	continue;	×
224	}
225
226	State updated;
227	Acceptance oldAcc = state.getAcceptance();	2✔
228	if (accepting) {	2✔
229	updated = updateSignature(state, Acceptance.TRUE, idx, last);	2✔
230	} else {
231	updated = updateSignature(state, idx, last);	2✔
232	}
233	if (state == updated && oldAcc == updated.getAcceptance()) {	2✔
234	return;	2✔
235	}
236	last = updated;	2✔
237	}	2✔
238
239	int finalIdx = path.pop().transIdx;	2✔
240
241	if (accepting) {	2✔
242	updateInitSignature(Acceptance.TRUE, finalIdx, last);	2✔
243	} else {
244	updateInitSignature(finalIdx, last);	2✔
245	}
246	}	2✔
247
248	/**
249	* Removes a state and all of its (non-confluent) successors from the register.
250	*
251	* @param state
252	* the state to purge
253	*/
254	private void purge(State state) {
255	StateSignature sig = state.getSignature();	2✔
256	if (sig == null) {	2✔
257	return;	×
258	}
259	if (state.getAcceptance() == Acceptance.TRUE) {	2✔
260	throw new IllegalStateException("Attempting to purge accepting state");	×
261	}
262	if (register.remove(sig) == null) {	2✔
263	return;	×
264	}
265	sig.acceptance = Acceptance.FALSE;	2✔
266	for (int i = 0; i < alphabetSize; i++) {	2✔
267	State succ = sig.successors.array[i];	2✔
268	if (succ != null) {	2✔
269	if (succ.isConfluence()) {	2✔
270	succ.decreaseIncoming();	2✔
271	} else {
272	purge(succ);	2✔
273	}
274	}
275	}
276	}	2✔
277
278	/**
279	* Creates a suffix state sequence, i.e., a linear sequence of states connected by transitions labeled by the
280	* letters of the given suffix word.
281	*
282	* @param suffix
283	* the suffix word
284	* @param accepting
285	* whether the final state should be accepting
286	*
287	* @return the first state in the sequence
288	*/
289	private State createSuffix(Word<? extends I> suffix, boolean accepting) {
290	State last;
291	Acceptance intermediate;
292	if (accepting) {	2✔
293	StateSignature sig = new StateSignature(alphabetSize, Acceptance.TRUE);	2✔
294	last = replaceOrRegister(sig);	2✔
295	intermediate = Acceptance.TRUE;	2✔
296	} else {	2✔
297	if (sink == null) {	2✔
298	sink = State.SINK;	2✔
299	}
300	last = sink;	2✔
301	intermediate = Acceptance.DONT_KNOW;	2✔
302	}
303
304	int len = suffix.length();	2✔
305	for (int i = len - 1; i >= 0; i--) {	2✔
306	StateSignature sig = new StateSignature(alphabetSize, intermediate);	2✔
307	I sym = suffix.getSymbol(i);	2✔
308	int idx = inputAlphabet.getSymbolIndex(sym);	2✔
309	sig.successors.array[idx] = last;	2✔
310	last = replaceOrRegister(sig);	2✔
311	}
312
313	return last;	2✔
314	}
315
316	}

LearnLib / automatalib / 12651580329

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