The implementation so far is able to handle only single nonlinear variable.

The algorithm, taken from BI-AAG course @ FIT CTU did not work
correctly when first automaton accepts a word of length 1.

There are two bugs. First, the set of final states was wrong. This was
the easy part to spot.
Second, we sometimes miss some transitions.

Consider these two automata:
 DFA a b
 ><A B -
  <B - -

 DFA a b
 ><C - -

The algorithm would result in this:
 DFA a   b
 ><S B   C
   A B|C -
   B -   -
  <C -   C

Which is of course wrong because the first automaton accepts "a + #E"
and the second one accepts a language of "b*". However, the result
doesn't accept words from neither "a" nor "ab*" which is in language
"(a+#E)b*".

The problem is that for every transition in the first automaton that
leads to a final state we create a new transition to an initial state of
the second automaton. This effectively says that "ok, we are done with
first automaton, we would accept. Let's continue from the initial state
of the second automaton".
Also, when we create a new initial state, we *only* copy transitions from
both initial states there. But if the word is of length 1 and is to be
accepted by the first automaton, we are missing this "transition to second
automaton".
In our example above, we need to add a transition (S, a) -> C and it's
fine.

Jan Trávníček authored 3 years ago and Jan Trávníček committed 3 years ago

breaking change!

Jan Trávníček authored 3 years ago and Tomáš Pecka committed 3 years ago

MP algorithm was always resetting the pattern index to 0 whereas it should be
reused. This revealed that Spos should also take into account node wildcards
otherwise the presumed not-necessary-to-be-parsed part of the pattern does not
have to be matching the pattern. Which caused the computation of what does not
need to be matched to underflow.

In recent Arch Linux builds we encountered some timeouts in tests.
Interestingly, the 30s timeouts were encountered not after 30s but
right-away. See the ctest output attached at the end of the message.

I remembered that Arch switched to glibc=2.33 recently. And by stracing
the test process I have noticed that indeed, the select in waitSignalTimeout
function timeouted early.
It seemed that the timeval struct is the problem and indeed it was. It
didn't like setting the 30s timeout as {.tv_sec = 0, .tv_usec = 30 *
1000 * 1000}. However, I can't find in any manpage why this is wrong...

It seems to be fixed by limiting tv_usec to be from [0; 1000*1000)
range and transfer the whole seconds into the tv_sec field.
And the glibc docs [1] says it so explicitely:

> When struct timeval values are produced by GNU C Library functions,
> the value in this field will always be greater than or equal to zero,
> and less than 1,000,000. When struct timeval values are supplied to GNU
> C Library functions, the value in this field must be in the same range.

[1] https://www.gnu.org/software/libc/manual/html_mono/libc.html#Time-Types

 -------------------------------------------------------------------------------
 aql/AutomatonIteration.aql
 -------------------------------------------------------------------------------
 /builds/algorithms-library-toolkit/infrastructure/cd-release/src/algorithms-library-snapshot/build/tests/AutomatonIteration.cpp:17
 ...............................................................................

 /builds/algorithms-library-toolkit/infrastructure/cd-release/src/algorithms-library-snapshot/tests/testing/TimeoutAqlTest.cpp:206: warning:
   AqlTest: timeout (30000000 us) reached
   Trying to execute testfile /builds/algorithms-library-toolkit/infrastructure/cd-release/src/algorithms-library-snapshot/tests/aql/AutomatonIteration.aql

 Seed was: 1053288110
   Child aqlout was: ><
   Child stdout was: ><
   Child stderr was: ><

 /builds/algorithms-library-toolkit/infrastructure/cd-release/src/algorithms-library-snapshot/tests/testing/TimeoutAqlTest.cpp:208: FAILED:

 ===============================================================================
 test cases: 1 | 1 failed
 assertions: 3 | 2 passed | 1 failed

... because most developers were copy-pasting the preambule anyway and
did not pay any attention to change it.

Also, I think that git does better job in managing that.

This test generates a random automaton, runs both iteration algorithms on
it and then tests that both these automata accept equal language.

This is first of the aql integration tests (which support was added in
commit d79fe028). This should serve as
an example how to write aql integration tests.
Also, this is something that should not be in the unit tests (and it
was removed in the previous commits).

Tomáš Pecka authored 4 years ago and Jan Trávníček committed 4 years ago

Although #pragma once is not a standard, compilers nowadays usually
support it. We don't have any tricky build system so we should be OK.

This also fixes many errors regarding using reserved identifiers (names
starting with double underscore).

removal of an unnecessary recursion, addition of forgotten move, removal of
unnecessary const qualifier, change int to -> size_t

This reverts commit dcf2c79a.

Added support for testing aql files (tests/aql).
Removed alib2integrationtests/ in favour of tests/ directory.

Sorry for a messy commit.
Closes #198.

It really makes no sense to have it inside alib2std component. Moved
into separate tests/ folder.