In Python 3.7, the re module changes the name of its _pattern_type
attribute to "Pattern", this patch handles both versions

The handling of the widget changed in the newest versions of IPython.
Now ipynbdoctest sees some output, but it is not stored in the
notebook.  To handle this, we have to compare the reference dictionary
witht the effective dictionary side-by-side, which we did not do
before.

Take this as an opportunity to clean up various issues.

* tests/bin/test.py: Expose the counts of tests, passes etc.
* tests/bin/ipynbdoctest.py: Use them instead of duplicating them.
(compare_outputs): Rewrite as...
(check_outputs): this.
(run_cell): Rename i and n to n and i, as it is more logical.
Improve the display.
Remove redundant display (we used to display the cell numbers twice).

fixup! tests: improve notebook checkings

Address #113.

* tests/python/lightest.py: Here.
* vcsn/algos/lightest.hh: Here.

* tests/python/divide.py: here.
* tests/bin/test.py: Remove extraneous spaces.

* vcsn/dyn/algos.hh, vcsn/dyn/algos.hxx (make_automaton)
(make_expression, make_label, make_polynomial, make_weight): New.
* build-aux/bin/oodyn-gen: Use them.

* build-aux/bin/tools-gen: Skip these `make_` functions, they are
useless in tools, use -E, -A, etc. instead.
While at it, report the function we ignore.

* build-aux/bin/oodyn-gen, build-aux/bin/tools-gen: Make sure we won't
stick on stdin, as was the case for a precursor of this commit.

Our handling of `&`, modeled after `.`, was dead wrong.  The point is
to capture all the sums that appear at the top-level, so `(a?)[bc]` is
split in `b⊕c⊕a(b+c)`.  This did require to splut `[bc]` because `a?`
is nullable.

However, doing the same with `&` splits `(a?)&[bc]` into
`b⊕c⊕a&(b+c)`, which is obviously wrong (e.g., the latter accepts `b`
but not the former).

Don't try to split extended operators.  Eventually, we might decide to
distribute from the left to the right, in which case `(a?)&[bc]`
should be split in `\e&[bc] ⊕ a&[bc]`, but not what we had currently.

See issue #149 about that.

* vcsn/algos/split.hh: Avoid recreating equivalent expressions:
just reuse the expression itself when there is nothing to do.
* tests/bin/test.py (shortest): New.
* tests/python/split.py (check): Check that the split expression is
equivalent to the expression itself.
Check extended operators.

K Shortest Path algorithm implemented following the Eppstein implementation
described in the article: `Finding the k shortest paths`, David Eppstein (1997).

* tests/python/lightest.py: Test it here.
* vcsn/algos/dijkstra-node.hh: Here.
* vcsn/algos/eppstein.hh: Here.
* vcsn/algos/implicit-path.hh: Here.
* vcsn/algos/lightest.hh: Here.
* vcsn/algos/path.hh: Here.
* vcsn/algos/shortest-path-tree.hh: Here.
* vcsn/local.mk: Here.

* tests/python/is-equivalent.py: Since we move to more `trivial`
identities, this test was weakened, as the expressions were not just
equivalent, but equal.

* tests/python/automaton.py, tests/python/derivation.py,
* tests/python/factory.py, tests/python/standard.py,
* tests/python/automaton.py, tests/python/compose.py,
* tests/python/efsm.py, tests/python/eliminate-state.py,
* tests/python/infiltrate.py, tests/python/ldivide.py,
* tests/python/minimize.py, tests/python/partial-identity.py,
* tests/python/power.py, tests/python/prefix.py,
* tests/python/rdivide.py, tests/python/synchronize.py,
* tests/python/to-expression.py, tests/python/union.py:
here.

* tests/bin/test.py (mefile, metext, meaut): New.
* tests/python/determinize.py: Use them.
* tests/python/standard.py: Use them, and prefer automata in files
instead of inline.

* TODO.txt: Update.
* doc/notebooks/check-notebooks (referenced): Improve regexp.
* tests/bin/test.py (CHECK_EQUIV): Show more shortest.
* tests/python/standard.py: Use better expression conversion routines.

See issue #62: sometimes our error are too terse.  Enrich them.  The
point here is first to look for a pattern that we could deploy
everywhere.

Before:

    In [2]: vcsn.Q.expression('a**').derivation('a')
    RuntimeError: q: star: invalid value: 1

    In [3]: vcsn.Q.expression('a**').constant_term()
    RuntimeError: q: star: invalid value: 1

    In [4]: vcsn.Q.expression('a**').derived_term('expansion')
    RuntimeError: q: star: invalid value: 1

    In [5]: vcsn.Q.expression('a**').derived_term('derivation')
    RuntimeError: q: star: invalid value: 1

After:

    In [2]: vcsn.Q.expression('a**').derivation('a')
    RuntimeError: q: star: invalid value: 1
      while computing derivative of: a**
                    with respect to: a

    In [3]: vcsn.Q.expression('a**').constant_term()
    RuntimeError: q: star: invalid value: 1
      while computing constant-term of: a**

    In [4]: vcsn.Q.expression('a**').derived_term('expansion')
    RuntimeError: q: star: invalid value: 1
      while computing expansion of: a**
      while computing derived-term of: a**

    In [5]: vcsn.Q.expression('a**').derived_term('derivation')
    RuntimeError: q: star: invalid value: 1
      while computing constant-term of: a**
      while computing derived-term of: a**

* vcsn/algos/constant-term.hh: Keep the expressionset, not
just the weightset.
Improve error messages.
Simplify tuple handling.
* vcsn/algos/derivation.hh: Improve error messages.
* vcsn/algos/derived-term.hh: Ditto.
(make_derived_term_automaton): Ditto.
* vcsn/algos/to-expansion.hh: Ditto.

* tests/bin/test.py (XFAIL): Also accept re patterns.
* tests/python/constant-term.py, tests/python/derivation.py,
* tests/python/expansion.py: Check error messages.

Clément Gillard authored Jun 02, 2016 and Akim Demaille committed Jun 07, 2016

See #61. Refactor Python scripts in tests/bin
to comply with `pylint`.

* tests/bin/bench-power: Reorder imports.
* tests/bin/rat.py: Fix string escapes.
* tests/bin/test.py: Reorder and remove duplicate imports.
* tests/bin/update-test: Remove unused imports and useless `global`s.
* python/pylintrc: Add new entries to ignore.

Currently to check if an expression is invalid, we compute its
constant-term and catch errors: indeed `1*` will fail.

Unfortunately constant-term can also fail because of operators
it does not support, such as @ and {\}.  We must tell the difference.

See issue #60.

* vcsn/algos/constant-term.hh: Report errors for compose too.
* vcsn/algos/is-valid-expression.hh: Improve error messages.

* tests/bin/test.py: Improve error messages.
* tests/python/constant-term.py:
* tests/python/is-valid.py: Prefer q to r.
Check more cases.

See #44 and #57.

* vcsn/core/automatonset.hh, vcsn/algos/inductive.hh: Support tuple.
(complement): We don't know how to complement on a multitape automata,
so disable for the time being.
* tests/python/standard.py: Check it.
* bin/vcsn.in, libexec/vcsn-tafkit.cc (inductive): Bind it.
* tests/bin/test.py (can_check_equivalence): We can't on tuples.

Avoid errors on tests.

* tests/bin/test.py: Here.

* tests/bin/test.py (CHECK_EQ): here.

* tests/bin/test.py: here.

Issue #36.

* vcsn/algos/multiply.hh: When determinizing, use the result...
* vcsn/algos/sum.hh: Provide a functional version.
* tests/python/multiply.py (check_mult_deter): Remove.
Instead of duplicating code, make it more generic.
Check that the result is deterministic when it should be.
While at it, check that the result is standard when the input
is.

* vcsn/algos/derived-term.hh: Implement lazy support.

* lib/vcsn/dyn/context-parser.cc, lib/vcsn/dyn/context-printer.cc:
Add support for derived_term_automaton.

* tests/bin/test.py (CHECK_NE): New.
* tests/python/derivation.py: Check lazy construction.

* libexec/vcsn-score: Bench lazy construction.

Clarify the `text` format.  Currently it serves two purposes:

- to present the user with a readable definition of the valueset.
  This is a failure: `lal_char(abc), b` is unpleasant to read.
  We would prefer `{abc} → 𝔹`.

- to build the snames.  This is a failure too, as we had to introduce
  a specific format (format::generators) to print generators, instead
  of `text`.

So rename `generators` as `sname`, and use the latter name instead of
`text` to build signatures.  Let's make `text` produce a human
readable result, using UTF-8.

* vcsn/misc/format.hh, lib/vcsn/misc/format.cc (generators): Rename as...
(sname): this.

* vcsn/alphabets/char.hh, vcsn/alphabets/setalpha.hh,
* vcsn/alphabets/string.hh, vcsn/core/rat/expansionset.hh,
* vcsn/core/rat/expressionset.hxx, vcsn/ctx/context.hh,
* vcsn/labelset/letterset.hh, vcsn/labelset/nullableset.hh,
* vcsn/labelset/oneset.hh, vcsn/labelset/tupleset.hh,
* vcsn/labelset/wordset.hh, vcsn/weightset/b.hh,
* vcsn/weightset/log.hh, vcsn/weightset/nmin.hh,
* vcsn/weightset/polynomialset.hh, vcsn/weightset/q.hh,
* vcsn/weightset/qmp.hh, vcsn/weightset/r.hh,
* vcsn/weightset/rmin.hh, vcsn/weightset/z.hh,
* vcsn/weightset/zmin.hh
(print_set): Be consistent in the support of `latex`, `sname`
and `text`.

* vcsn/algos/dot.hh: Adjust: ask for `sname`.
* tests/python/context.py: Likewise.

Do not try is_equivalent on automata with expressionset weightset.

* tests/bin/test.py: Here.

Some expansions require special contexts: \e|a for instance must be
translated into '\e|a.[\e|\e]', where '\e|a' is a label: hence we need
lan here.

* vcsn/core/rat/expansionset.hh: Make sure that the denormalization
succeeded.
* tests/python/to-expansion.py: Check.

* tests/bin/test.py (SKIP): Comply with the syntax of TAP.
* tests/python/to-expansion.py: Remove unused argument.

We require Python 3, there is no point in using __future__.

* bin/vcsn-score, bin/vcsn-score-compare, build-aux/bin/registers-gen,
* python/vcsn/d3Widget.py, python/vcsn/ipython.py,
* python/vcsn/score.py, tests/bin/bench-power, tests/bin/rat.py,
* tests/bin/test.py, tests/bin/update-test, tests/python/automaton.py,
* tests/python/derivation.py, tests/python/efsm.py,
* tests/python/proper.py, tests/python/transpose.py:
here.

* tests/bin/test.py: Beware that sometimes algorithms used in here
can fail.  In that case, report the error properly.

Instead of `E \mid F`, whose size does not depend on the size of its
argument, use `\left. E \middle| \right.`.
Suggested by Alexandre Duret-Lutz.

* vcsn/core/rat/printer.hh, vcsn/core/rat/printer.hxx: here.

* tests/bin/test.py: Always print the expected/effective paragraphs.
Even if they are redundant for single line changes, they enable the
use of update-tests.

* tests/python/transducer.py: Update expectations.

* share/vcsn/lal_char_zmin/minab.gv,
* share/vcsn/lal_char_zmin/minblocka.gv,
* share/vcsn/lal_char_zmin/slowgrow.gv: Fix comments.
* lib/vcsn/algos/edit-automaton.cc: Sort.
* tests/bin/test.py: Fix the display of failures.

* vcsn/algos/are-equivalent.hh: Here.
* doc/notebooks/automaton.is_equivalent.ipynb: Update.
* tests/bin/test.py (CHECK_EQUIV): No longer call normalize.
(normalize): Use realtime instead of proper().
* tests/python/efsm.py (check): Use normalize: we have a case
where we compare lan x lan against lal x lal, and since we
don't have synchronize yet, it fails.

* tests/python/push-weights.py: Use CHECK_EQUIV instead of
checking the equality of the valuation for some words.

Nicolas Barray authored Feb 10, 2015 and Akim Demaille committed Feb 16, 2015

Add the CHECK_IS_ACYCLIC function to check zpc post-construction property.

* tests/bin/test.py: Here.

We do have dyn::are_equivalent for expression, but not on the
templated level.

* vcsn/algos/are-equivalent.hh: Do it.
Use derived-term, instead of standard, as what the case before.
* vcsn/dyn/algos.hh, lib/vcsn/algos/are-equivalent.cc: Adjust.
* tests/python/is-equivalent.py: Check a weighted case.

This should help getting better feedback _while_ running the test
suite.

* tests/bin/test.py (PASS, FAIL): here.

* vcsn/algos/is-partial-identity.hh: New, extracted from...
* vcsn/algos/is-functional.hh: here.
(is_identity): Rename as...
(is_partial_identity): this.
* lib/vcsn/algos/is-functional.cc, vcsn/dyn/algos.hh, vcsn/local.mk: Adjust.

* lib/vcsn/dyn/context-parser.cc, lib/vcsn/dyn/signature-printer.cc,
* vcsn/dyn/context-parser.hh, vcsn/labelset/nullableset.hh: Now
the displayed name for nullableset _is_ nullableset, no longer lan.
'lan' is still accepted in input though.

* tests/python/automaton.dir/lan_char_z.daut,
* tests/python/automaton.dir/lan_char_z.out.gv,
* tests/python/automaton.dir/lan_char_z.tex.gv,
* tests/python/automaton.py,
* tests/python/compose.dir/result.gv,
* tests/python/compose.py,
* tests/python/context.py,
* tests/python/insplit.py,
* tests/python/prefix.dir/aut1-subword.gv,
* tests/python/prefix.dir/aut2-subword.gv,
* tests/python/prefix.dir/aut3-subword.gv,
* tests/python/prefix.dir/aut4-subword.gv,
* tests/python/product.py,
* tests/python/proper.py,
* tests/python/thompson.py:
Adjust.

Currently we still support names such as "lal_char, b" internally,
although "lal" does not make much sense (but "letterset" does), and
"_char" is absurd, as it actually parameterize the "lal" part.

So instead of "lal_char(abc)", work with "letterset<char(abc)>", which
make more sense.  It is (still) unfortunate that we don't have a nice
concrete syntax for our types, but it was a mistake to design a broken
syntax which pleases neither the user, nor the implementation.

So now accept "lal_char(abc)" as a backward compatibility feature, but
record "letterset<char(abc)>" instead.

* vcsn/alphabets/char.hh (sname): Your name is "char_letter", not "char".
* vcsn/alphabets/setalpha.hh: Honor the basic letter type name.
* vcsn/labelset/letterset.hh: Your name is "letterset".
Use use the name of the letter type we use instead of hard coding it again
here.
* vcsn/labelset/wordset.hh: Likewise.

Improve the dyn support.

* vcsn/dyn/type-ast.hh (letterset, wordset): Rename their "alphabet" into
"generators".
Provide them with a "letter_type".
* lib/vcsn/dyn/context-parser.cc, lib/vcsn/dyn/context-printer.cc,
* lib/vcsn/dyn/signature-printer.cc: Adjust.

Adjust the test suite.

Our (current) implementation of `proper` is in-place, and as a
consequence, the result features the same context as the input
automaton: a nullable labelset.

Now it return a labelset un-nullabled _if possible_.

To this end, `proper` now performs two copies: the initial one to be
able to modify the working copy of the input automaton, and a final
one to rewrite the automaton in the context with removed support for
spontaneous transitions.

There is no real noted performance regression:

   before  after
    2.39    2.41  a.proper()           # a = thompson(a?{1200})

* vcsn/algos/proper.hh (proper): Do that.
* vcsn/labelset/nullableset.hh: .
* python/vcsn/automaton.py (_lan_to_lal, proper): Remove, now useless.
* python/vcsn_cxx.cc (proper): Bind under its real name.
* vcsn/labelset/tupleset.hh (conv): Add support to strip an outter
nullableset.

* tests/bin/test.py (normalize): New.
(CHECK_EQUIV): Use it.
* tests/python/compose.py, tests/python/proper.py, bin/vcsn-score: Adjust.

* tests/python/efsm.py, tests/python/product.py: So don't do it.

Well, it took me a while to figure out the proper use of Boost.Python
(these pages were useful:
http://stackoverflow.com/questions/16660049/,
http://www.boost.org/doc/libs/1_55_0/libs/python/doc/v2/init.html),
but it does work.

* python/vcsn_cxx.cc (automaton): Support automaton(filename = ...).
* python/vcsn/automaton.py (automaton.load): Remove.
Adjust dependencies.

git s '"""' "'''"