Felix Abecassis authored May 25, 2010 and Alexandre Duret-Lutz committed Nov 06, 2010

* src/neverclaimparse/: New directory.
* src/neverclaimparse/fmterror.cc: New file.  Print a formatted parse
error on a output stream.
* src/neverclaimparse/neverclaimparse.yy: New file.  Parser declaration
for Bison.
* src/neverclaimparse/neverclaimscan.ll: New file.  Scanner declaration
for Flex.
* src/neverclaimparse/public.hh: New file.  Public header for external
use.
* src/neverclaimparse/parsedecl.hh: New file.  Header file for
Flex-Bison interaction.
* src/neverclaimparse/Makefile.am: New Makefile.
* src/tgbatest/neverclaimread.cc: New file.  Test program for the
never claim parser.
* src/tgbatest/neverclaimread.test: New file.  Test script for the
never claim parser.
* src/tgbatest/Makefile.am: Adjust.
* configure.ac : Adjust.
* README: Adjust.

* src/tgbaparse/tgbaparse.yy (line): Fix computation of line number
for error messages when parsing conditions.
* src/tgbatest/readsave.test: Check the syntax position of syntax errors
in the diagnostics.  Use ltl2tgba instead of readsave.
* src/tgbatest/Makefile.am (check_PROGRAMS): Remove readsave.

We do that because the declaration of this type, which is local to
src/tgba/tgbasafracomplement.cc has a member in an anonymous
namespace, and some versions of g++-4.2 issue a very annoying
warning about this legitimate code.  See Bug 29365 on GCC's
Bugzilla.  Report by Silien Hong <silien.hong@lip6.fr>.

* src/tgba/tgbasafracomplement.hh (safra_tree_automaton): Do not
forward declare.
(tgba_safra_complement): Use void* instead of
safra_tree_automaton*.
* src/tgba/tgbasafracomplement.cc: static_cast void* to
safra_tree_automaton* anywhere needed.

Such changes should not be pushed to master before they are finished
(this doesn't pass distcheck).

This reverts commit 9aaa638b.

* src/neverclaimparse/: New directory.
* src/neverclaimparse/fmterror.cc: New file.  Print a formatted parse
error on a output stream.
* src/neverclaimparse/neverclaimparse.yy: New file.  Parser declaration
for Bison.
* src/neverclaimparse/neverclaimscan.ll: New file.  Scanner declaration
for Flex.
* src/neverclaimparse/public.hh: New file.  Public header for external
use.
* src/neverclaimparse/parsedecl.hh: New file.  Header file for
Flex-Bison interaction.
* src/neverclaimparse/Makefile.am: New Makefile.
* src/tgbatest/neverclaimread.cc: New file.  Test program for the
never claim parser.
* src/tgbatest/neverclaimread.test: New file.  Test script for the
never claim parser.
* src/tgbatest/Makefile.am: Adjust.
* configure.ac : Adjust.
* README: Adjust.

* m4/gccoptim.m4: Add missing AC_LANG_PUSH/AC_LANG_POP around the
C test.  It was using the C++ compiler instead...

* NEWS, configure.ac: Bump version to 0.6.

* src/ltltest/reduccmp.test: Reorder the test added by the
previous patches.  Some are not supposed to be reduced by
reductaustr.

clone for M.

* src/ltlvisit/contain.cc (reduce_tau03_visitor): Remove
the stronger rules for R and M.  They were wrong.
* src/ltltest/reduccmp.test: Test a simpple counterexample.

* src/ltlvisit/reduce.cc (reduce_visitor): Add the following
implication rewriting rules:
a M (b M c) = a M c if a implies b.
a M (b R c) = a M c if a implies b.
a R (b R c) = a R c if a implies b.
a R (b M c) = b M c if b implies a.
a M (b M c) = b M c if b implies a.
The latter rule was fixed from an incorrectly copied&pasted
rule for a M (b R c) = b R c if b implies a (this is wrong).
* src/ltltest/reduccmp.test: Add more tests.

* src/ltlvisit/syntimpl.cc (syntactic_implication): Do not
create visitors if arguments are constant.

* src/ltlvisit/simpfg.cc: Typo.
* src/ltltest/reduccmp.test: Add more tests.

help output.

* src/ltlvisit/basicreduce.cc: Perform the following reductions:
(a R b) | Gb = a R b
(a M b) | Gb = a R b
(a U b) & Fb = a U b
(a W b) & Fb = a U b
* src/ltltest/reduccmp.test: Test them.

* src/ltlvisit/basicreduce.cc: Perform the following reductions:
(a U b) & (c W b) = (a & c) U b
(a W b) & (c W b) = (a & c) W b
(a R b) | (c M b) = (a | c) R b
(a M b) | (c M b) = (a | c) M b
* src/ltltest/reduccmp.test: Test them.

* src/ltlvisit/basicreduce.cc: Perform the following reductions.
a R (b & F(a)) = a M b
a M (b & F(a)) = a M b
a R Fa = Fa
a M Fa = Fa
a R b & Fa = a M b
a R b & a M c = a M (b & c)
a M b & a M c = a M (b & c)
* src/ltltest/reduccmp.test: More tests.

* src/ltlvisit/basicreduce.cc: Perform the following reductions.
a U (b | Ga) = a W b
a W (b | Ga) = a W b
a U b | Ga = a W b
a U b | a W c = a W (b | c)
a W b | a W c = a W (b | c)
a U Ga = Ga
a W Ga = Ga
* src/ltltest/reduccmp.test: More tests.

* src/ltlast/binop.cc, src/ltlast/binop.cc: Add support for
these new operators.
* src/ltlparse/ltlparse.yy, src/ltlparse/ltlscan.ll: Parse them.
* src/ltltest/reduccmp.test: Add new tests for W and M.
* src/ltlvisit/basicreduce.cc, src/ltlvisit/contain.cc,
src/ltlvisit/lunabbrev.cc, src/ltlvisit/nenoform.cc,
src/ltlvisit/randomltl.cc, src/ltlvisit/randomltl.hh,
src/ltlvisit/reduce.cc, src/ltlvisite/simpfg.cc,
src/ltlvisit/simpfg.hh, src/ltlvisit/syntimpl.cc,
src/ltlvisit/tostring.cc, src/tgba/formula2bdd.cc,
src/tgbaalgos/eltl2tgba_lacim.cc, src/tgbaalgos/ltl2taa.cc,
src/tgbaalgos/ltl2tgba_fm.cc, src/tgbaalgos/ltl2tgba_lacim.cc:
Add support for W and M.
* src/tgbatest/ltl2neverclaim.test: Test never claim output
using LBTT, this is more thorough.  Also we cannot use -N
any more in the spotlbtt.test.
* src/tgbatests/ltl2tgba.cc: Define M and W for ELTL.
* src/tgbatest/ltl2neverclaim.test: Test W and M, and use
-DS instead of -N, because lbtt-translate does not want
to translate these operators for tools that masquerade as Spin.

* src/SpotWrapper.cc: Translate W and M operators.

appropriate.

* wrap/python/spot.i (spot::scc_filter): Make it available.
* wrap/python/cgi-bin/ltl2tgba.in (reduce_scc): Call scc_filter.
Use the "full" option unless the show_degen_png or
show_never_claim are set.  Also reduce_scc the default.

* src/ltlparse/ltlparse.yy, src/tgbaparse/tgbaparse.yy,
src/evtgbaparse/evtgbaparse.yy, src/eltlparse/eltlparse.yy: Use
token types for %destructor and %printer.  Remove the yylex hack,
since %name-prefix is now honored by Bison.  Also remove the
useless <token> type.  Suggested by Akim Demaille.

* src/ltlparse/fmterror.cc (format_parse_errors): Count columns
starting at 1.  Older Bison used to start at 0 but changed to
match the GNU Coding Standards.
* src/ltltest/parseerr.test: Add a test case.

* src/ltlvisit/basicreduce.cc (basic_reduce_visitor::recurse):
Disable this rule unconditionally.
* src/ltltest/reduccmp.test: Adjust tests.

degeneralization.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_tba_proxy): Build the
list of acceptance condition in the reverse order.  The order is
still arbitrary, but the bdd_satone() call seems to output the
acceptance conditions that are more used first, and this helps the
degeneralization process.

* src/ltlparse/ltlparse.yy: Change the precedence of "->" and
"<->" so that "a & b -> c" is interpreted as "(a & b) -> c"
instead of "a & (b -> c)".  The new interpretation is more
intuitive, and matches that of LBTT.

original paper by Somenzi and Bloem.  Reported by Ruediger Ehlers.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_sba_proxy): Do not
forget to free the initial state after usage.

by default in scc_filter().

Doing so helps the degeneralization algorithm, because it will
have more opportunity to be in an accepting level when it reaches
the accepting SCCs.

* src/tgbaalgos/sccfilter.cc (filter_iter::filter_iter): Take a
remove_all_useless argument.
(filter_iter::process_link): Use the flag to decide whether to
filter acceptance conditions going to accepting SCCs.
(scc_filter): Take a remove_all_useless argument and pass it to
filter_iter.
* src/tgbaalgos/sccfilter.hh (filter_iter): Add the new argument
and document the function.
* src/tgbatest/tgbatests/ltl2tgba.cc (main): Add option use -R3
for remove_all_useless=false and add -R3f for
remove_all_useless=true.
* src/tgbatest/ltl2tgba.test: Show one case where -R3f makes
the degeneralization worse than -R3.

* src/ltlvisit/basicreduce.cc (basic_reduce_visitor): Replace
the FG(a)|FG(b) == FG(a|b) rule by the above more generic one.
Add the dual rule for G(a)&G(b), as we had none (this one won't
improve anything in the translation, but it is more symmetric
this way).  Also simplify some pointer checks.

* src/tgba/tgbatba.cc (tgba_sba_proxy::tgba_sba_proxy): Set
cycle_start_ to start in the accepting layer of the degeneralized
automaton if the initial state has an accepting self-loop.
Otherwise, starts at the level of the first acceptance condition
as previously.
(tgba_sba_proxy::get_init_state): Use cycle_start_.
* src/tgba/tgbatba.hh (tgba_tba_proxy::a_): Make it protected so
that we can use it in tgba_sba_proxy::tgba_sba_proxy.
(tgba_sba_proxy::cycle_start_, tgba_sba_proxy::get_init_state):
Declare.
* src/tgbatest/ltl2tgba.test: More tests.