diff options
38 files changed, 641 insertions, 383 deletions
diff --git a/.gitlab-ci.yml b/.gitlab-ci.yml index 00ccc9f137..4a053ec03f 100644 --- a/.gitlab-ci.yml +++ b/.gitlab-ci.yml @@ -18,7 +18,7 @@ stages: variables: # Format: $IMAGE-V$DATE [Cache is not used as of today but kept here # for reference] - CACHEKEY: "bionic_coq-V2019-03-18-V93" + CACHEKEY: "bionic_coq-V2020-03-19-V29" IMAGE: "$CI_REGISTRY_IMAGE:$CACHEKEY" # By default, jobs run in the base switch; override to select another switch OPAM_SWITCH: "base" @@ -69,6 +69,7 @@ before_script: - _install_ci - config/Makefile - config/coq_config.py + - config/coq_config.ml - test-suite/misc/universes/all_stdlib.v expire_in: 1 week script: @@ -172,7 +173,7 @@ before_script: - BIN=$(readlink -f ../_install_ci/bin)/ - LIB=$(readlink -f ../_install_ci/lib/coq)/ - export OCAMLPATH=$(readlink -f ../_install_ci/lib/):"$OCAMLPATH" - - make -j "$NJOBS" BIN="$BIN" COQLIB="$LIB" COQFLAGS="${COQFLAGS}" all + - COQEXTRAFLAGS="${COQEXTRAFLAGS}" make -j "$NJOBS" BIN="$BIN" COQLIB="$LIB" all artifacts: name: "$CI_JOB_NAME.logs" when: on_failure @@ -531,7 +532,7 @@ test-suite:base+async: needs: - build:base variables: - COQFLAGS: "-async-proofs on -async-proofs-cache force" + COQEXTRAFLAGS: "-async-proofs on -async-proofs-cache force" timeout: 100m allow_failure: true only: diff --git a/.ocamlformat b/.ocamlformat index 59883180e5..d5608839fb 100644 --- a/.ocamlformat +++ b/.ocamlformat @@ -1,3 +1,4 @@ +version=0.13.0 profile=ocamlformat module-item-spacing=compact sequence-style=terminator diff --git a/Makefile.dune b/Makefile.dune index b433ed1b94..499ad0d16b 100644 --- a/Makefile.dune +++ b/Makefile.dune @@ -102,7 +102,7 @@ release: voboot dune build $(DUNEOPT) -p coq fmt: voboot - dune build @fmt + dune build @fmt --auto-promote ocheck: voboot dune build $(DUNEOPT) @install --workspace=dev/dune-workspace.all diff --git a/dev/ci/docker/bionic_coq/Dockerfile b/dev/ci/docker/bionic_coq/Dockerfile index 4e229bb777..e56e4d38ea 100644 --- a/dev/ci/docker/bionic_coq/Dockerfile +++ b/dev/ci/docker/bionic_coq/Dockerfile @@ -1,4 +1,4 @@ -# CACHEKEY: "bionic_coq-V2019-03-18-V93" +# CACHEKEY: "bionic_coq-V2020-03-19-V29" # ^^ Update when modifying this file. FROM ubuntu:bionic @@ -18,7 +18,7 @@ RUN apt-get update -qq && apt-get install --no-install-recommends -y -qq \ texlive-science tipa # More dependencies of the sphinx doc -RUN pip3 install sphinx==1.7.8 sphinx_rtd_theme==0.2.5b2 \ +RUN pip3 install sphinx==1.8.0 sphinx_rtd_theme==0.2.5b2 \ antlr4-python3-runtime==4.7.1 sphinxcontrib-bibtex==0.4.0 # We need to install OPAM 2.0 manually for now. @@ -57,7 +57,7 @@ RUN opam switch create "${COMPILER}+32bit" && eval $(opam env) && \ # EDGE switch ENV COMPILER_EDGE="4.09.1" \ - BASE_OPAM_EDGE="dune-release.1.3.3 ocamlformat.0.12" + BASE_OPAM_EDGE="dune-release.1.3.3 ocamlformat.0.13.0" # EDGE+flambda switch, we install CI_OPAM as to be able to use # `ci-template-flambda` with everything. diff --git a/dev/doc/changes.md b/dev/doc/changes.md index 9088df6856..b82388675c 100644 --- a/dev/doc/changes.md +++ b/dev/doc/changes.md @@ -1,19 +1,19 @@ ## Changes between Coq 8.11 and Coq 8.12 -### ML API +### Code formatting -Refiner.catchable_exception is deprecated, use instead -CErrors.noncritical in try-with block. Note that nothing is needed in -tclORELSE block since the exceptions there are supposed to be -non-critical by construction. +- The automatic code formatting tool `ocamlformat` is enabled now for + the micromega codebase. Version 0.13.0 is required. See + `ocalmformat`'s documentation for more details on integration with + your editor. ### ML API -Types `precedence`, `parenRelation`, `tolerability` in -`notgram_ops.ml` have been reworked. See `entry_level` and -`entry_relative_level` in `constrexpr.ml`. +Notations: -### ML API +- Types `precedence`, `parenRelation`, `tolerability` in + `notgram_ops.ml` have been reworked. See `entry_level` and + `entry_relative_level` in `constrexpr.ml`. Exception handling: @@ -28,6 +28,11 @@ Exception handling: + printers are of type `exn -> Pp.t option` [`None` == not handled] + it is forbidden for exception printers to raise. +- Refiner.catchable_exception is deprecated, use instead + CErrors.noncritical in try-with block. Note that nothing is needed in + tclORELSE block since the exceptions there are supposed to be + non-critical by construction. + Printers: - Functions such as Printer.pr_lconstr_goal_style_env have been diff --git a/doc/README.md b/doc/README.md index 7fa6f5cf3d..e749bcf5d1 100644 --- a/doc/README.md +++ b/doc/README.md @@ -30,7 +30,7 @@ To produce the complete documentation in HTML, you will need Coq dependencies listed in [`INSTALL.md`](../INSTALL.md). Additionally, the Sphinx-based reference manual requires Python 3, and the following Python packages: - - sphinx >= 1.7.8 + - sphinx >= 1.8.0 - sphinx_rtd_theme >= 0.2.5b2 - beautifulsoup4 >= 4.0.6 - antlr4-python3-runtime >= 4.7.1 diff --git a/doc/sphinx/addendum/extraction.rst b/doc/sphinx/addendum/extraction.rst index d909f98956..41b726b069 100644 --- a/doc/sphinx/addendum/extraction.rst +++ b/doc/sphinx/addendum/extraction.rst @@ -1,7 +1,7 @@ .. _extraction: -Extraction of programs in |OCaml| and Haskell -============================================= +Program extraction +================== :Authors: Jean-Christophe Filliâtre and Pierre Letouzey diff --git a/doc/sphinx/addendum/miscellaneous-extensions.rst b/doc/sphinx/addendum/miscellaneous-extensions.rst index db8c09d88f..0e8660cb0e 100644 --- a/doc/sphinx/addendum/miscellaneous-extensions.rst +++ b/doc/sphinx/addendum/miscellaneous-extensions.rst @@ -1,10 +1,5 @@ -.. _miscellaneousextensions: - -Miscellaneous extensions -======================== - Program derivation ------------------- +================== |Coq| comes with an extension called ``Derive``, which supports program derivation. Typically in the style of Bird and Meertens or derivations diff --git a/doc/sphinx/appendix/history-and-changes/index.rst b/doc/sphinx/appendix/history-and-changes/index.rst new file mode 100644 index 0000000000..50ffec8e3f --- /dev/null +++ b/doc/sphinx/appendix/history-and-changes/index.rst @@ -0,0 +1,21 @@ +.. _history-and-changes: + +========================== +History and recent changes +========================== + +This chapter is divided in two parts. The first one is about the +:ref:`early history of Coq <history>` and is presented in +chronological order. The second one provides :ref:`release notes +about recent versions of Coq <changes>` and is presented in reverse +chronological order. When updating your copy of Coq to a new version +(especially a new major version), it is strongly recommended that you +read the corresponding release notes. They may contain advice that +will help you understand the differences with the previous version and +upgrade your projects. + +.. toctree:: + :maxdepth: 1 + + ../../history + ../../changes diff --git a/doc/sphinx/appendix/indexes/index.rst b/doc/sphinx/appendix/indexes/index.rst new file mode 100644 index 0000000000..a5032ff822 --- /dev/null +++ b/doc/sphinx/appendix/indexes/index.rst @@ -0,0 +1,24 @@ +:orphan: + +.. _indexes: + +======== +Indexes +======== + +We provide various specialized indexes that are helpful to quickly +find what you are looking for. + +.. toctree:: + + ../../genindex + ../../coq-cmdindex + ../../coq-tacindex + ../../coq-optindex + ../../coq-exnindex + +For reference, here are direct links to the documentation of: + +- :ref:`flags, options and tables <flags-options-tables>`; +- controlling the display of warning messages with the :opt:`Warnings` + option. diff --git a/doc/sphinx/changes.rst b/doc/sphinx/changes.rst index 8855b54f5b..a0cf9730a9 100644 --- a/doc/sphinx/changes.rst +++ b/doc/sphinx/changes.rst @@ -1,3 +1,5 @@ +.. _changes: + -------------- Recent changes -------------- diff --git a/doc/sphinx/conf.py b/doc/sphinx/conf.py index 9857ece077..c2c1c68f5c 100755 --- a/doc/sphinx/conf.py +++ b/doc/sphinx/conf.py @@ -46,7 +46,7 @@ with open("refman-preamble.rst") as s: # -- General configuration ------------------------------------------------ # If your documentation needs a minimal Sphinx version, state it here. -needs_sphinx = '1.7.8' +needs_sphinx = '1.8.0' # Add any Sphinx extension module names here, as strings. They can be # extensions coming with Sphinx (named 'sphinx.ext.*') or your custom diff --git a/doc/sphinx/genindex.rst b/doc/sphinx/genindex.rst index 29f792b3aa..e3a27fd7c4 100644 --- a/doc/sphinx/genindex.rst +++ b/doc/sphinx/genindex.rst @@ -2,6 +2,6 @@ .. hack to get index in TOC ------ -Index ------ +------------- +General index +------------- diff --git a/doc/sphinx/history.rst b/doc/sphinx/history.rst index c4a48d6985..153dc1f368 100644 --- a/doc/sphinx/history.rst +++ b/doc/sphinx/history.rst @@ -1,3 +1,5 @@ +.. _history: + -------------------- Early history of Coq -------------------- diff --git a/doc/sphinx/index.html.rst b/doc/sphinx/index.html.rst index 0a20d1c47b..6069ed42fe 100644 --- a/doc/sphinx/index.html.rst +++ b/doc/sphinx/index.html.rst @@ -8,84 +8,37 @@ Contents -------- .. toctree:: - :caption: Indexes - - genindex - coq-cmdindex - coq-tacindex - coq-optindex - coq-exnindex - -.. No entries yet - * :index:`thmindex` - -.. toctree:: - :caption: Preamble self - history - changes .. toctree:: - :caption: The language + :caption: Specification language - language/gallina-specification-language - language/gallina-extensions - language/coq-library - language/cic - language/module-system + language/core/index + language/extensions/index .. toctree:: - :caption: The proof engine + :caption: Proofs - proof-engine/vernacular-commands - proof-engine/proof-handling - proof-engine/tactics - proof-engine/ltac - proof-engine/ltac2 - proof-engine/detailed-tactic-examples - proof-engine/ssreflect-proof-language + proofs/writing-proofs/index + proofs/automatic-tactics/index + proofs/creating-tactics/index .. toctree:: - :caption: User extensions + :caption: Using Coq - user-extensions/syntax-extensions - user-extensions/proof-schemes + using/libraries/index + using/tools/index .. toctree:: - :caption: Practical tools + :caption: Appendix - practical-tools/coq-commands - practical-tools/utilities - practical-tools/coqide - -.. toctree:: - :caption: Addendum - - addendum/extended-pattern-matching - addendum/implicit-coercions - addendum/canonical-structures - addendum/type-classes - addendum/omega - addendum/micromega - addendum/extraction - addendum/program - addendum/ring - addendum/nsatz - addendum/generalized-rewriting - addendum/parallel-proof-processing - addendum/miscellaneous-extensions - addendum/universe-polymorphism - addendum/sprop + appendix/history-and-changes/index + appendix/indexes/index + zebibliography -.. toctree:: - :caption: Reference +.. No entries yet + * :index:`thmindex` - zebibliography .. include:: license.rst - -.. [#PG] Proof-General is available at https://proofgeneral.github.io/. - Optionally, you can enhance it with the minor mode - Company-Coq :cite:`Pit16` - (see https://github.com/cpitclaudel/company-coq). diff --git a/doc/sphinx/index.latex.rst b/doc/sphinx/index.latex.rst index 5562736997..62d9525194 100644 --- a/doc/sphinx/index.latex.rst +++ b/doc/sphinx/index.latex.rst @@ -10,81 +10,39 @@ Introduction .. include:: license.rst -.. [#PG] Proof-General is available at https://proofgeneral.github.io/. - Optionally, you can enhance it with the minor mode - Company-Coq :cite:`Pit16` - (see https://github.com/cpitclaudel/company-coq). - -.. include:: history.rst - -.. include:: changes.rst - ------------- -The language ------------- +---------------------- +Specification language +---------------------- .. toctree:: - language/gallina-specification-language - language/gallina-extensions - language/coq-library - language/cic - language/module-system + language/core/index + language/extensions/index ----------------- -The proof engine ----------------- +------ +Proofs +------ .. toctree:: - proof-engine/vernacular-commands - proof-engine/proof-handling - proof-engine/tactics - proof-engine/ltac - proof-engine/ltac2 - proof-engine/detailed-tactic-examples - proof-engine/ssreflect-proof-language + proofs/writing-proofs/index + proofs/automatic-tactics/index + proofs/creating-tactics/index ---------------- -User extensions ---------------- +--------- +Using Coq +--------- .. toctree:: - user-extensions/syntax-extensions - user-extensions/proof-schemes - ---------------- -Practical tools ---------------- - -.. toctree:: - - practical-tools/coq-commands - practical-tools/utilities - practical-tools/coqide + using/libraries/index + using/tools/index -------- -Addendum +Appendix -------- .. toctree:: - addendum/extended-pattern-matching - addendum/implicit-coercions - addendum/canonical-structures - addendum/type-classes - addendum/omega - addendum/micromega - addendum/extraction - addendum/program - addendum/ring - addendum/nsatz - addendum/generalized-rewriting - addendum/parallel-proof-processing - addendum/miscellaneous-extensions - addendum/universe-polymorphism - addendum/sprop - -.. toctree:: + appendix/history-and-changes/index zebibliography diff --git a/doc/sphinx/introduction.rst b/doc/sphinx/introduction.rst index 1424b4f3e1..b059fb4069 100644 --- a/doc/sphinx/introduction.rst +++ b/doc/sphinx/introduction.rst @@ -1,107 +1,68 @@ -This document is the Reference Manual of the |Coq| proof assistant. -To start using Coq, it is advised to first read a tutorial. -Links to several tutorials can be found at -https://coq.inria.fr/documentation and -https://github.com/coq/coq/wiki#coq-tutorials - -The |Coq| system is designed to develop mathematical proofs, and -especially to write formal specifications, programs and to verify that -programs are correct with respect to their specifications. It provides a -specification language named |Gallina|. Terms of |Gallina| can represent -programs as well as properties of these programs and proofs of these -properties. Using the so-called *Curry-Howard isomorphism*, programs, -properties and proofs are formalized in the same language called -*Calculus of Inductive Constructions*, that is a -:math:`\lambda`-calculus with a rich type system. All logical judgments -in |Coq| are typing judgments. The very heart of the |Coq| system is the -type checking algorithm that checks the correctness of proofs, in other -words that checks that a program complies to its specification. |Coq| also -provides an interactive proof assistant to build proofs using specific -programs called *tactics*. - -All services of the |Coq| proof assistant are accessible by interpretation -of a command language called *the vernacular*. - -Coq has an interactive mode in which commands are interpreted as the -user types them in from the keyboard and a compiled mode where commands -are processed from a file. - -- In interactive mode, users can develop their theories and proofs step by - step, and query the system for available theorems and definitions. The - interactive mode is generally run with the help of an IDE, such - as CoqIDE, documented in :ref:`coqintegrateddevelopmentenvironment`, - Emacs with Proof-General :cite:`Asp00` [#PG]_, - or jsCoq to run Coq in your browser (see https://github.com/ejgallego/jscoq). - The `coqtop` read-eval-print-loop can also be used directly, for debugging - purposes. - -- The compiled mode acts as a proof checker taking a file containing a - whole development in order to ensure its correctness. Moreover, - |Coq|’s compiler provides an output file containing a compact - representation of its input. The compiled mode is run with the `coqc` - command. - -.. seealso:: :ref:`thecoqcommands`. - -How to read this book ---------------------- - -This is a Reference Manual, so it is not intended for continuous reading. -We recommend using the various indexes to quickly locate the documentation -you are looking for. There is a global index, and a number of specific indexes -for tactics, vernacular commands, and error messages and warnings. -Nonetheless, the manual has some structure that is explained below. - -- The first part describes the specification language, |Gallina|. - Chapters :ref:`gallinaspecificationlanguage` and :ref:`extensionsofgallina` describe the concrete - syntax as well as the meaning of programs, theorems and proofs in the - Calculus of Inductive Constructions. Chapter :ref:`thecoqlibrary` describes the - standard library of |Coq|. Chapter :ref:`calculusofinductiveconstructions` is a mathematical description - of the formalism. Chapter :ref:`themodulesystem` describes the module - system. - -- The second part describes the proof engine. It is divided into several - chapters. Chapter :ref:`vernacularcommands` presents all commands (we - call them *vernacular commands*) that are not directly related to - interactive proving: requests to the environment, complete or partial - evaluation, loading and compiling files. How to start and stop - proofs, do multiple proofs in parallel is explained in - Chapter :ref:`proofhandling`. In Chapter :ref:`tactics`, all commands that - realize one or more steps of the proof are presented: we call them - *tactics*. The legacy language to combine these tactics into complex proof - strategies is given in Chapter :ref:`ltac`. The currently experimental - language that will eventually replace Ltac is presented in - Chapter :ref:`ltac2`. Examples of tactics - are described in Chapter :ref:`detailedexamplesoftactics`. - Finally, the |SSR| proof language is presented in - Chapter :ref:`thessreflectprooflanguage`. - -- The third part describes how to extend the syntax of |Coq| in - Chapter :ref:`syntaxextensionsandinterpretationscopes` and how to define - new induction principles in Chapter :ref:`proofschemes`. - -- In the fourth part more practical tools are documented. First in - Chapter :ref:`thecoqcommands`, the usage of `coqc` (batch mode) and - `coqtop` (interactive mode) with their options is described. Then, - in Chapter :ref:`utilities`, various utilities that come with the - |Coq| distribution are presented. Finally, Chapter :ref:`coqintegrateddevelopmentenvironment` - describes CoqIDE. - -- The fifth part documents a number of advanced features, including coercions, - canonical structures, typeclasses, program extraction, and specialized - solvers and tactics. See the table of contents for a complete list. - -List of additional documentation --------------------------------- - -This manual does not contain all the documentation the user may need -about |Coq|. Various informations can be found in the following documents: - -Installation - A text file `INSTALL` that comes with the sources explains how to - install |Coq|. - -The |Coq| standard library - A commented version of sources of the |Coq| standard library - (including only the specifications, the proofs are removed) is - available at https://coq.inria.fr/stdlib/. +This is the reference manual of |Coq|. Coq is an interactive theorem +prover. It lets you formalize mathematical concepts and then helps +you interactively generate machine-checked proofs of theorems. +Machine checking gives users much more confidence that the proofs are +correct compared to human-generated and -checked proofs. Coq has been +used in a number of flagship verification projects, including the +`CompCert verified C compiler <http://compcert.inria.fr/>`_, and has +served to verify the proof of the `four color theorem +<https://github.com/math-comp/fourcolor>`_ (among many other +mathematical formalizations). + +Users generate proofs by entering a series of tactics that constitute +steps in the proof. There are many built-in tactics, some of which +are elementary, while others implement complex decision procedures +(such as :tacn:`lia`, a decision procedure for linear integer +arithmetic). :ref:`Ltac <ltac>` and its planned replacement, +:ref:`Ltac2 <ltac2>`, provide languages to define new tactics by +combining existing tactics with looping and conditional constructs. +These permit automation of large parts of proofs and sometimes entire +proofs. Furthermore, users can add novel tactics or functionality by +creating Coq plugins using OCaml. + +The Coq kernel, a small part of Coq, does the final verification that +the tactic-generated proof is valid. Usually the tactic-generated +proof is indeed correct, but delegating proof verification to the +kernel means that even if a tactic is buggy, it won't be able to +introduce an incorrect proof into the system. + +Finally, Coq also supports extraction of verified programs to +programming languages such as OCaml and Haskell. This provides a way +of executing Coq code efficiently and can be used to create verified +software libraries. + +To learn Coq, beginners are advised to first start with a tutorial / +book. Several such tutorials / books are listed at +https://coq.inria.fr/documentation. + +This manual is organized in three main parts, plus an appendix: + +- **The first part presents the specification language of Coq**, that + allows to define programs and state mathematical theorems. + :ref:`core-language` presents the language that the kernel of Coq + understands. :ref:`extensions` presents the richer language, with + notations, implicits, etc. that a user can use and which is + translated down to the language of the kernel by means of an + "elaboration process". + +- **The second part presents the interactive proof mode**, the central + feature of Coq. :ref:`writing-proofs` introduces this interactive + proof mode and the available proof languages. + :ref:`automatic-tactics` presents some more advanced tactics, while + :ref:`writing-tactics` is about the languages that allow a user to + combine tactics together and develop new ones. + +- **The third part shows how to use Coq in practice.** + :ref:`libraries` presents some of the essential reusable blocks from + the ecosystem and some particularly important extensions such as the + program extraction mechanism. :ref:`tools` documents important + tools that a user needs to build a Coq project. + +- In the appendix, :ref:`history-and-changes` presents the history of + Coq and changes in recent releases. This is an important reference + if you upgrade the version of Coq that you use. The various + :ref:`indexes <indexes>` are very useful to **quickly browse the + manual and find what you are looking for.** They are often the main + entry point to the manual. + +The full table of contents is presented below: diff --git a/doc/sphinx/language/core/index.rst b/doc/sphinx/language/core/index.rst new file mode 100644 index 0000000000..07dcfff444 --- /dev/null +++ b/doc/sphinx/language/core/index.rst @@ -0,0 +1,37 @@ +.. _core-language: + +============= +Core language +============= + +At the heart of the Coq proof assistant is the Coq kernel. While +users have access to a language with many convenient features such as +notations, implicit arguments, etc. (that are presented in the +:ref:`next chapter <extensions>`), such complex terms get translated +down to a core language (the Calculus of Inductive Constructions) that +the kernel understands, and which we present here. Furthermore, while +users can build proofs interactively using tactics (see Chapter +:ref:`writing-proofs`), the role of these tactics is to incrementally +build a "proof term" which the kernel will verify. More precisely, a +proof term is a term of the Calculus of Inductive Constructions whose +type corresponds to a theorem statement. The kernel is a type checker +which verifies that terms have their expected type. + +This separation between the kernel on the one hand and the elaboration +engine and tactics on the other hand follows what is known as the "de +Bruijn criterion" (keeping a small and well delimited trusted code +base within a proof assistant which can be much more complex). This +separation makes it possible to reduce the trust in the whole system +to trusting a smaller, critical component: the kernel. In particular, +users may rely on external plugins that provide advanced and complex +tactics without fear of these tactics being buggy, because the kernel +will have to check their output. + +.. toctree:: + :maxdepth: 1 + + ../gallina-specification-language + ../cic + ../../addendum/universe-polymorphism + ../../addendum/sprop + ../module-system diff --git a/doc/sphinx/language/extensions/index.rst b/doc/sphinx/language/extensions/index.rst new file mode 100644 index 0000000000..f22927d627 --- /dev/null +++ b/doc/sphinx/language/extensions/index.rst @@ -0,0 +1,26 @@ +.. _extensions: + +=================== +Language extensions +=================== + +Elaboration extends the language accepted by the Coq kernel to make it +easier to use. For example, this lets the user omit most type +annotations because they can be inferred, call functions with implicit +arguments which will be inferred as well, extend the syntax with +notations, factorize branches when pattern-matching, etc. In this +chapter, we present these language extensions and we give some +explanations on how this language is translated down to the core +language presented in the :ref:`previous chapter <core-language>`. + +.. toctree:: + :maxdepth: 1 + + ../gallina-extensions + ../../addendum/extended-pattern-matching + ../../user-extensions/syntax-extensions + ../../addendum/implicit-coercions + ../../addendum/type-classes + ../../addendum/canonical-structures + ../../addendum/program + ../../proof-engine/vernacular-commands diff --git a/doc/sphinx/license.rst b/doc/sphinx/license.rst index 55c6d988f0..35837f8407 100644 --- a/doc/sphinx/license.rst +++ b/doc/sphinx/license.rst @@ -1,7 +1,7 @@ -License -------- +.. note:: **License** -This material (the Coq Reference Manual) may be distributed only subject to the -terms and conditions set forth in the Open Publication License, v1.0 or later -(the latest version is presently available at -http://www.opencontent.org/openpub). Options A and B are not elected. + This material (the Coq Reference Manual) may be distributed only + subject to the terms and conditions set forth in the Open + Publication License, v1.0 or later (the latest version is presently + available at http://www.opencontent.org/openpub). Options A and B + are not elected. diff --git a/doc/sphinx/practical-tools/utilities.rst b/doc/sphinx/practical-tools/utilities.rst index 514353e39b..e5ff26520a 100644 --- a/doc/sphinx/practical-tools/utilities.rst +++ b/doc/sphinx/practical-tools/utilities.rst @@ -499,6 +499,40 @@ To build, say, two targets foo.vo and bar.vo in parallel one can use (``.PHONY`` or not) please use ``CoqMakefile.local``. +Precompiling for ``native_compute`` ++++++++++++++++++++++++++++++++++++ + +To compile files for ``native_compute``, one can use the +``-native-compiler yes`` option of |Coq|, for instance by putting the +following in a :ref:`coqmakefilelocal` file: + +:: + + COQEXTRAFLAGS += -native-compiler yes + +The generated ``CoqMakefile`` installation target will then take care +of installing the extra ``.coq-native`` directories. + +.. note:: + + As an alternative to modifying any file, one can set the + environment variable when calling ``make``: + + :: + + COQEXTRAFLAGS="-native-compiler yes" make + + This can be useful when files cannot be modified, for instance when + installing via OPAM a package built with ``coq_makefile``: + + :: + + COQEXTRAFLAGS="-native-compiler yes" opam install coq-package + +.. note:: + + This requires all dependencies to be themselves compiled with + ``-native-compiler yes``. Building a |Coq| project with Dune ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ diff --git a/doc/sphinx/proofs/automatic-tactics/index.rst b/doc/sphinx/proofs/automatic-tactics/index.rst new file mode 100644 index 0000000000..a219770c69 --- /dev/null +++ b/doc/sphinx/proofs/automatic-tactics/index.rst @@ -0,0 +1,20 @@ +.. _automatic-tactics: + +===================================================== +Built-in decision procedures and programmable tactics +===================================================== + +Some tactics are largely automated and are able to solve complex +goals. This chapter presents both some decision procedures that can +be used to solve some specific categories of goals, and some +programmable tactics, that the user can instrument to handle some +complex goals in new domains. + +.. toctree:: + :maxdepth: 1 + + ../../addendum/omega + ../../addendum/micromega + ../../addendum/ring + ../../addendum/nsatz + ../../addendum/generalized-rewriting diff --git a/doc/sphinx/proofs/creating-tactics/index.rst b/doc/sphinx/proofs/creating-tactics/index.rst new file mode 100644 index 0000000000..1af1b0b726 --- /dev/null +++ b/doc/sphinx/proofs/creating-tactics/index.rst @@ -0,0 +1,34 @@ +.. _writing-tactics: + +==================== +Creating new tactics +==================== + +The languages presented in this chapter allow one to build complex +tactics by combining existing ones with constructs such as +conditionals and looping. While :ref:`Ltac <ltac>` was initially +thought of as a language for doing some basic combinations, it has +been used successfully to build highly complex tactics as well, but +this has also highlighted its limits and fragility. The experimental +language :ref:`Ltac2 <ltac2>` is a typed and more principled variant +which is more adapted to building complex tactics. + +There are other solutions beyond these two tactic languages to write +new tactics: + +- `Mtac2 <https://github.com/Mtac2/Mtac2>`_ is an external plugin + which provides another typed tactic language. While Ltac2 belongs + to the ML language family, Mtac2 reuses the language of Coq itself + as the language to build Coq tactics. + +- The most traditional way of building new complex tactics is to write + a Coq plugin in OCaml. Beware that this also requires much more + effort and commitment. A tutorial for writing Coq plugins is + available in the Coq repository in `doc/plugin_tutorial + <https://github.com/coq/coq/tree/master/doc/plugin_tutorial>`_. + +.. toctree:: + :maxdepth: 1 + + ../../proof-engine/ltac + ../../proof-engine/ltac2 diff --git a/doc/sphinx/proofs/writing-proofs/index.rst b/doc/sphinx/proofs/writing-proofs/index.rst new file mode 100644 index 0000000000..a279a5957f --- /dev/null +++ b/doc/sphinx/proofs/writing-proofs/index.rst @@ -0,0 +1,34 @@ +.. _writing-proofs: + +============== +Writing proofs +============== + +Coq is an interactive theorem prover, or proof assistant, which means +that proofs can be constructed interactively through a dialog between +the user and the assistant. The building blocks for this dialog are +tactics which the user will use to represent steps in the proof of a +theorem. + +Incomplete proofs have one or more open (unproven) sub-goals. Each +goal has its own context (a set of assumptions that can be used to +prove the goal). Tactics can transform goals and contexts. +Internally, the incomplete proof is represented as a partial proof +term, with holes for the unproven sub-goals. + +When a proof is complete, the user leaves the proof mode and defers +the verification of the resulting proof term to the :ref:`kernel +<core-language>`. + +This chapter is divided in several parts, describing the basic ideas +of the proof mode (during which tactics can be used), and several +flavors of tactics, including the SSReflect proof language. + +.. toctree:: + :maxdepth: 1 + + ../../proof-engine/proof-handling + ../../proof-engine/tactics + ../../proof-engine/ssreflect-proof-language + ../../proof-engine/detailed-tactic-examples + ../../user-extensions/proof-schemes diff --git a/doc/sphinx/using/libraries/index.rst b/doc/sphinx/using/libraries/index.rst new file mode 100644 index 0000000000..d0848e6c3f --- /dev/null +++ b/doc/sphinx/using/libraries/index.rst @@ -0,0 +1,24 @@ +.. _libraries: + +===================== +Libraries and plugins +===================== + +Coq is distributed with a standard library and a set of internal +plugins (most of which provide tactics that have already been +presented in :ref:`writing-proofs`). This chapter presents this +standard library and some of these internal plugins which provide +features that are not tactics. + +In addition, Coq has a rich ecosystem of external libraries and +plugins. These libraries and plugins can be browsed online through +the `Coq Package Index <https://coq.inria.fr/opam/www/>`_ and +installed with the `opam package manager +<https://coq.inria.fr/opam-using.html>`_. + +.. toctree:: + :maxdepth: 1 + + ../../language/coq-library + ../../addendum/extraction + ../../addendum/miscellaneous-extensions diff --git a/doc/sphinx/using/tools/index.rst b/doc/sphinx/using/tools/index.rst new file mode 100644 index 0000000000..4381c4d63d --- /dev/null +++ b/doc/sphinx/using/tools/index.rst @@ -0,0 +1,20 @@ +.. _tools: + +================================ +Command-line and graphical tools +================================ + +This chapter presents the command-line tools that users will need to +build their Coq project, the documentation of the CoqIDE standalone +user interface and the documentation of the parallel proof processing +feature that is supported by CoqIDE and several other user interfaces. +A list of available user interfaces to interact with Coq is available +on the `Coq website <https://coq.inria.fr/user-interfaces.html>`_. + +.. toctree:: + :maxdepth: 1 + + ../../practical-tools/coq-commands + ../../practical-tools/utilities + ../../practical-tools/coqide + ../../addendum/parallel-proof-processing diff --git a/doc/tools/coqrst/coqdomain.py b/doc/tools/coqrst/coqdomain.py index b92c94fe2c..84f32e187b 100644 --- a/doc/tools/coqrst/coqdomain.py +++ b/doc/tools/coqrst/coqdomain.py @@ -34,7 +34,6 @@ from sphinx.util.logging import getLogger, get_node_location from sphinx.directives import ObjectDescription from sphinx.domains import Domain, ObjType, Index from sphinx.domains.std import token_xrefs -from sphinx.ext import mathbase from . import coqdoc from .repl import ansicolors @@ -74,8 +73,7 @@ def make_target(objtype, targetid): return "coq:{}.{}".format(objtype, targetid) def make_math_node(latex, docname, nowrap): - node = mathbase.displaymath() - node['latex'] = latex + node = nodes.math_block(latex, latex) node['label'] = None # Otherwise equations are numbered node['nowrap'] = nowrap node['docname'] = docname @@ -493,9 +491,7 @@ class ProductionObject(CoqObject): pass def _target_id(self, name): - # Use `name[1]` instead of ``nodes.make_id(name[1])`` to work around - # https://github.com/sphinx-doc/sphinx/issues/4983 - return 'grammar-token-{}'.format(name[1]) + return 'grammar-token-{}'.format(nodes.make_id(name[1])) def _record_name(self, name, targetid): env = self.state.document.settings.env diff --git a/ide/default_bindings_src.ml b/ide/default_bindings_src.ml index 85a635a50f..a69a7c2aba 100644 --- a/ide/default_bindings_src.ml +++ b/ide/default_bindings_src.ml @@ -545,7 +545,7 @@ let bindings_set_1 = [ ["\\Hopf"; "\\quaternions" ], "ℍ", [letter]; ["\\planckh" ], "ℎ", [letter]; ["\\hslash"; "\\plankv" ], "ℏ", [letter]; - ["\\hbar"; "\\planck" ], "ℏ︀", [letter]; + ["\\hbar"; "\\planck" ], "ℏ", [letter]; ["\\Iscr"; "\\imagline" ], "ℐ", [letter]; ["\\Im"; "\\Ifr"; "\\image"; "\\imagpart" ], "ℑ", [letter]; ["\\Lscr"; "\\lagran"; "\\Laplacetrf" ], "ℒ", [letter]; @@ -1108,7 +1108,7 @@ let bindings_set_1 = [ ["\\isins" ], "⋴", [set]; ["\\isindot" ], "⋵", [set]; ["\\notinvc" ], "⋶", [set]; - ["\\notindot" ], "⋶︀", [set]; + ["\\notindot" ], "⋶", [set]; ["\\notinvb" ], "⋷", [set]; ["\\isinE" ], "⋹", [set]; ["\\nisd" ], "⋺", [set]; @@ -1192,40 +1192,40 @@ let bindings_set_1 = [ (* }}} *) (* {{{ Missing font *) - ["\\NegativeThickSpace" ], " ︀", [miscellanea]; - ["\\NegativeThinSpace" ], " ︀", [miscellanea]; - ["\\NegativeVeryThinSpace" ], " ︀", [miscellanea]; - ["\\NegativeMediumSpace" ], " ︀", [miscellanea]; - ["\\slarr"; "\\ShortLeftArrow" ], "←︀", [miscellanea]; - ["\\srarr"; "\\ShortRightArrow" ], "→︀", [miscellanea]; - ["\\empty"; "\\emptyset" ], "∅︀", [miscellanea]; - ["\\ssetmn"; "\\smallsetminus" ], "∖︀", [miscellanea]; - ["\\smid"; "\\shortmid" ], "∣︀", [miscellanea]; - ["\\nsmid"; "\\nshortmid" ], "∤︀", [miscellanea]; - ["\\spar"; "\\parsl"; "\\shortparallel" ], "∥︀", [miscellanea]; - ["\\nparsl" ], "∥︀⃥", [miscellanea]; - ["\\nspar"; "\\nshortparallel" ], "∦︀", [miscellanea]; - ["\\caps" ], "∩︀", [miscellanea]; - ["\\cups" ], "∪︀", [miscellanea]; - ["\\thksim"; "\\thicksim" ], "∼︀", [miscellanea]; - ["\\thkap"; "\\thickapprox" ], "≈︀", [miscellanea]; - ["\\nedot" ], "≠︀", [miscellanea]; + ["\\NegativeThickSpace" ], " ", [miscellanea]; + ["\\NegativeThinSpace" ], " ", [miscellanea]; + ["\\NegativeVeryThinSpace" ], " ", [miscellanea]; + ["\\NegativeMediumSpace" ], " ", [miscellanea]; + ["\\slarr"; "\\ShortLeftArrow" ], "←", [miscellanea]; + ["\\srarr"; "\\ShortRightArrow" ], "→", [miscellanea]; + ["\\empty"; "\\emptyset" ], "∅", [miscellanea]; + ["\\ssetmn"; "\\smallsetminus" ], "∖", [miscellanea]; + ["\\smid"; "\\shortmid" ], "∣", [miscellanea]; + ["\\nsmid"; "\\nshortmid" ], "∤", [miscellanea]; + ["\\spar"; "\\parsl"; "\\shortparallel" ], "∥", [miscellanea]; + ["\\nparsl" ], "∥⃥", [miscellanea]; + ["\\nspar"; "\\nshortparallel" ], "∦", [miscellanea]; + ["\\caps" ], "∩", [miscellanea]; + ["\\cups" ], "∪", [miscellanea]; + ["\\thksim"; "\\thicksim" ], "∼", [miscellanea]; + ["\\thkap"; "\\thickapprox" ], "≈", [miscellanea]; + ["\\nedot" ], "≠", [miscellanea]; ["\\bnequiv" ], "≡⃥", [miscellanea]; - ["\\lvnE"; "\\lvertneqq" ], "≨︀", [miscellanea]; - ["\\gvnE"; "\\gvertneqq" ], "≩︀", [miscellanea]; - ["\\nLtv"; "\\NotLessLess" ], "≪̸︀", [miscellanea]; - ["\\nGtv"; "\\NotGreaterGreater" ], "≫̸︀", [miscellanea]; + ["\\lvnE"; "\\lvertneqq" ], "≨", [miscellanea]; + ["\\gvnE"; "\\gvertneqq" ], "≩", [miscellanea]; + ["\\nLtv"; "\\NotLessLess" ], "≪̸", [miscellanea]; + ["\\nGtv"; "\\NotGreaterGreater" ], "≫̸", [miscellanea]; ["\\nle"; "\\NotLessEqual" ], "≰⃥", [miscellanea]; ["\\nge"; "\\NotGreaterEqual" ], "≱⃥", [miscellanea]; - ["\\vsubnE"; "\\vsubne"; "\\varsubsetneq"; "\\varsubsetneqq" ], "⊊︀", [miscellanea]; - ["\\vsupne"; "\\vsupnE"; "\\varsupsetneq"; "\\varsupsetneqq" ], "⊋︀", [miscellanea]; - ["\\sqcaps" ], "⊓︀", [miscellanea]; - ["\\sqcups" ], "⊔︀", [miscellanea]; + ["\\vsubnE"; "\\vsubne"; "\\varsubsetneq"; "\\varsubsetneqq" ], "⊊", [miscellanea]; + ["\\vsupne"; "\\vsupnE"; "\\varsupsetneq"; "\\varsupsetneqq" ], "⊋", [miscellanea]; + ["\\sqcaps" ], "⊓", [miscellanea]; + ["\\sqcups" ], "⊔", [miscellanea]; ["\\prurel" ], "⊰", [miscellanea]; - ["\\lesg" ], "⋚︀", [miscellanea]; - ["\\gesl" ], "⋛︀", [miscellanea]; - ["\\ShortUpArrow" ], "⌃︀", [miscellanea]; - ["\\ShortDownArrow" ], "⌄︀", [miscellanea]; + ["\\lesg" ], "⋚", [miscellanea]; + ["\\gesl" ], "⋛", [miscellanea]; + ["\\ShortUpArrow" ], "⌃", [miscellanea]; + ["\\ShortDownArrow" ], "⌄", [miscellanea]; ["\\target" ], "⌖", [miscellanea]; ["\\cylcty" ], "⌭", [miscellanea]; ["\\profalar" ], "⌮", [miscellanea]; @@ -1248,7 +1248,7 @@ let bindings_set_1 = [ ["\\ltrPar" ], "⦖", [miscellanea]; ["\\vzigzag" ], "⦚", [miscellanea]; ["\\angrtvbd" ], "⦝", [miscellanea]; - ["\\angrtvb" ], "⦝︀", [miscellanea]; + ["\\angrtvb" ], "⦝", [miscellanea]; ["\\ange" ], "⦤", [miscellanea]; ["\\range" ], "⦥", [miscellanea]; ["\\dwangle" ], "⦦", [miscellanea]; @@ -1367,9 +1367,9 @@ let bindings_set_1 = [ ["\\smt" ], "⪪", [miscellanea]; ["\\lat" ], "⪫", [miscellanea]; ["\\smte" ], "⪬", [miscellanea]; - ["\\smtes" ], "⪬︀", [miscellanea]; + ["\\smtes" ], "⪬", [miscellanea]; ["\\late" ], "⪭", [miscellanea]; - ["\\lates" ], "⪭︀", [miscellanea]; + ["\\lates" ], "⪭", [miscellanea]; ["\\Sc" ], "⪼", [miscellanea]; ["\\subdot" ], "⪽", [miscellanea]; ["\\supdot" ], "⪾", [miscellanea]; diff --git a/plugins/funind/functional_principles_types.ml b/plugins/funind/functional_principles_types.ml index 275468ad3d..163645b719 100644 --- a/plugins/funind/functional_principles_types.ml +++ b/plugins/funind/functional_principles_types.ml @@ -63,14 +63,14 @@ let compute_new_princ_type_from_rel rel_to_fun sorts princ_type = (* observe (str "princ_infos : " ++ pr_elim_scheme princ_type_info); *) let change_predicate_sort i decl = let new_sort = sorts.(i) in - let args,_ = decompose_prod (EConstr.Unsafe.to_constr (RelDecl.get_type decl)) in + let args,_ = decompose_prod_assum (EConstr.Unsafe.to_constr (RelDecl.get_type decl)) in let real_args = if princ_type_info.indarg_in_concl then List.tl args else args in Context.Named.Declaration.LocalAssum (map_annot Nameops.Name.get_id (Context.Rel.Declaration.get_annot decl), - Term.compose_prod real_args (mkSort new_sort)) + Term.it_mkProd_or_LetIn (mkSort new_sort) real_args) in let new_predicates = List.map_i diff --git a/plugins/micromega/coq_micromega.ml b/plugins/micromega/coq_micromega.ml index 87778f7f7b..82f8b5b3e2 100644 --- a/plugins/micromega/coq_micromega.ml +++ b/plugins/micromega/coq_micromega.ml @@ -1279,7 +1279,8 @@ module M = struct let dump_expr i e = let rec dump_expr = function | Mc.PEX n -> - EConstr.mkRel (i + List.assoc (CoqToCaml.positive n) vars_idx) + EConstr.mkRel + (i + CList.assoc_f Int.equal (CoqToCaml.positive n) vars_idx) | Mc.PEc z -> dexpr.dump_cst z | Mc.PEadd (e1, e2) -> EConstr.mkApp (dexpr.dump_add, [|dump_expr e1; dump_expr e2|]) @@ -1294,7 +1295,9 @@ module M = struct dump_expr e in let mkop op e1 e2 = - try EConstr.mkApp (List.assoc op dexpr.dump_op, [|e1; e2|]) + try + EConstr.mkApp + (CList.assoc_f Mutils.Hash.eq_op2 op dexpr.dump_op, [|e1; e2|]) with Not_found -> EConstr.mkApp (Lazy.force coq_Eq, [|dexpr.interp_typ; e1; e2|]) in @@ -1480,7 +1483,8 @@ type ('synt_c, 'prf) domain_spec = ; (* is the type of the syntactic coeffs - Z , Q , Rcst *) dump_coeff : 'synt_c -> EConstr.constr ; proof_typ : EConstr.constr - ; dump_proof : 'prf -> EConstr.constr } + ; dump_proof : 'prf -> EConstr.constr + ; coeff_eq : 'synt_c -> 'synt_c -> bool } (** * The datastructures that aggregate theory-dependent proof values. *) @@ -1491,7 +1495,8 @@ let zz_domain_spec = ; coeff = Lazy.force coq_Z ; dump_coeff = dump_z ; proof_typ = Lazy.force coq_proofTerm - ; dump_proof = dump_proof_term } + ; dump_proof = dump_proof_term + ; coeff_eq = Mc.zeq_bool } let qq_domain_spec = lazy @@ -1499,7 +1504,8 @@ let qq_domain_spec = ; coeff = Lazy.force coq_Q ; dump_coeff = dump_q ; proof_typ = Lazy.force coq_QWitness - ; dump_proof = dump_psatz coq_Q dump_q } + ; dump_proof = dump_psatz coq_Q dump_q + ; coeff_eq = Mc.qeq_bool } let max_tag f = 1 + Tag.to_int (Mc.foldA (fun t1 (t2, _) -> Tag.max t1 t2) f (Tag.from 0)) @@ -1603,7 +1609,12 @@ let witness_list_tags p g = witness_list p g * Prune the proof object, according to the 'diff' between two cnf formulas. *) -let compact_proofs (cnf_ff : 'cst cnf) res (cnf_ff' : 'cst cnf) = +let compact_proofs (eq_cst : 'cst -> 'cst -> bool) (cnf_ff : 'cst cnf) res + (cnf_ff' : 'cst cnf) = + let eq_formula (p1, o1) (p2, o2) = + let open Mutils.Hash in + eq_pol eq_cst p1 p2 && eq_op1 o1 o2 + in let compact_proof (old_cl : 'cst clause) (prf, prover) (new_cl : 'cst clause) = let new_cl = List.mapi (fun i (f, _) -> (f, i)) new_cl in @@ -1611,7 +1622,7 @@ let compact_proofs (cnf_ff : 'cst cnf) res (cnf_ff' : 'cst cnf) = let formula = try fst (List.nth old_cl i) with Failure _ -> failwith "bad old index" in - List.assoc formula new_cl + CList.assoc_f eq_formula formula new_cl in (* if debug then begin @@ -1641,7 +1652,13 @@ let compact_proofs (cnf_ff : 'cst cnf) res (cnf_ff' : 'cst cnf) = (new_cl : 'cst clause) = let hyps_idx = prover.hyps prf in let hyps = selecti hyps_idx old_cl in - is_sublist ( = ) hyps new_cl + let eq (f1, (t1, e1)) (f2, (t2, e2)) = + Int.equal (Tag.compare t1 t2) 0 + && eq_formula f1 f2 + && (e1 : EConstr.t) = (e2 : EConstr.t) + (* FIXME: what equality should we use here? *) + in + is_sublist eq hyps new_cl in let cnf_res = List.combine cnf_ff res in (* we get pairs clause * proof *) @@ -1798,7 +1815,7 @@ let micromega_tauto pre_process cnf spec prover env | None -> failwith "abstraction is wrong" | Some res -> () end ; *) - let res' = compact_proofs cnf_ff res cnf_ff' in + let res' = compact_proofs spec.coeff_eq cnf_ff res cnf_ff' in let ff', res', ids = (ff', res', Mc.ids_of_formula ff') in let res' = dump_list spec.proof_typ spec.dump_proof res' in Prf (ids, ff', res') @@ -1946,7 +1963,8 @@ let micromega_genr prover tac = ; coeff = Lazy.force coq_Rcst ; dump_coeff = dump_q ; proof_typ = Lazy.force coq_QWitness - ; dump_proof = dump_psatz coq_Q dump_q } + ; dump_proof = dump_psatz coq_Q dump_q + ; coeff_eq = Mc.qeq_bool } in Proofview.Goal.enter (fun gl -> let sigma = Tacmach.New.project gl in @@ -1979,7 +1997,7 @@ let micromega_genr prover tac = | Prf (ids, ff', res') -> let ff, ids = formula_hyps_concl - (List.filter (fun (n, _) -> List.mem n ids) hyps) + (List.filter (fun (n, _) -> CList.mem_f Id.equal n ids) hyps) concl in let ff' = abstract_wrt_formula ff' ff in diff --git a/plugins/micromega/mutils.ml b/plugins/micromega/mutils.ml index f9a23751bf..27b917383b 100644 --- a/plugins/micromega/mutils.ml +++ b/plugins/micromega/mutils.ml @@ -385,7 +385,13 @@ module Hash = struct let int_of_eq_op1 = Mc.(function Equal -> 0 | NonEqual -> 1 | Strict -> 2 | NonStrict -> 3) - let eq_op1 o1 o2 = int_of_eq_op1 o1 = int_of_eq_op1 o2 + let int_of_eq_op2 = + Mc.( + function + | OpEq -> 0 | OpNEq -> 1 | OpLe -> 2 | OpGe -> 3 | OpLt -> 4 | OpGt -> 5) + + let eq_op1 o1 o2 = Int.equal (int_of_eq_op1 o1) (int_of_eq_op1 o2) + let eq_op2 o1 o2 = Int.equal (int_of_eq_op2 o1) (int_of_eq_op2 o2) let hash_op1 h o = combine h (int_of_eq_op1 o) let rec eq_positive p1 p2 = diff --git a/plugins/micromega/mutils.mli b/plugins/micromega/mutils.mli index 5e0c913996..146860ca00 100644 --- a/plugins/micromega/mutils.mli +++ b/plugins/micromega/mutils.mli @@ -43,6 +43,7 @@ module Tag : sig val max : t -> t -> t val from : int -> t val to_int : t -> int + val compare : t -> t -> int end module TagSet : CSig.SetS with type elt = Tag.t @@ -73,6 +74,7 @@ end module Hash : sig val eq_op1 : Micromega.op1 -> Micromega.op1 -> bool + val eq_op2 : Micromega.op2 -> Micromega.op2 -> bool val eq_positive : Micromega.positive -> Micromega.positive -> bool val eq_z : Micromega.z -> Micromega.z -> bool val eq_q : Micromega.q -> Micromega.q -> bool diff --git a/plugins/micromega/vect.ml b/plugins/micromega/vect.ml index 1742f81b34..15f37868f7 100644 --- a/plugins/micromega/vect.ml +++ b/plugins/micromega/vect.ml @@ -19,7 +19,8 @@ type var = int - values are all non-zero *) -type t = (var * Q.t) list +type mono = {var : var; coe : Q.t} +type t = mono list type vector = t (** [equal v1 v2 = true] if the vectors are syntactically equal. *) @@ -29,21 +30,25 @@ let rec equal v1 v2 = | [], [] -> true | [], _ -> false | _ :: _, [] -> false - | (i1, n1) :: v1, (i2, n2) :: v2 -> Int.equal i1 i2 && n1 =/ n2 && equal v1 v2 + | {var = i1; coe = n1} :: v1, {var = i2; coe = n2} :: v2 -> + Int.equal i1 i2 && n1 =/ n2 && equal v1 v2 let hash v = let rec hash i = function | [] -> i - | (vr, vl) :: l -> hash (i + Hashtbl.hash (vr, Q.to_float vl)) l + | {var = vr; coe = vl} :: l -> hash (i + Hashtbl.hash (vr, Q.to_float vl)) l in Hashtbl.hash (hash 0 v) let null = [] let is_null v = - match v with [] -> true | [(0, x)] when Q.zero =/ x -> true | _ -> false + match v with + | [] -> true + | [{var = 0; coe = x}] when Q.zero =/ x -> true + | _ -> false -let pp_var_num pp_var o (v, n) = +let pp_var_num pp_var o {var = v; coe = n} = if Int.equal v 0 then if Q.zero =/ n then () else Printf.fprintf o "%s" (Q.to_string n) else if Q.one =/ n then pp_var o v @@ -51,7 +56,7 @@ let pp_var_num pp_var o (v, n) = else if Q.zero =/ n then () else Printf.fprintf o "%s*%a" (Q.to_string n) pp_var v -let pp_var_num_smt pp_var o (v, n) = +let pp_var_num_smt pp_var o {var = v; coe = n} = if Int.equal v 0 then if Q.zero =/ n then () else Printf.fprintf o "%s" (Q.to_string n) else if Q.one =/ n then pp_var o v @@ -79,7 +84,7 @@ let from_list (l : Q.t list) = match l with | [] -> [] | e :: l -> - if e <>/ Q.zero then (i, e) :: xfrom_list (i + 1) l + if e <>/ Q.zero then {var = i; coe = e} :: xfrom_list (i + 1) l else xfrom_list (i + 1) l in xfrom_list 0 l @@ -88,68 +93,71 @@ let to_list m = let rec xto_list i l = match l with | [] -> [] - | (x, v) :: l' -> - if i = x then v :: xto_list (i + 1) l' else Q.zero :: xto_list (i + 1) l + | {var = x; coe = v} :: l' -> + if Int.equal i x then v :: xto_list (i + 1) l' + else Q.zero :: xto_list (i + 1) l in xto_list 0 m -let cons i v rst = if v =/ Q.zero then rst else (i, v) :: rst +let cons i v rst = if v =/ Q.zero then rst else {var = i; coe = v} :: rst let rec update i f t = match t with | [] -> cons i (f Q.zero) [] - | (k, v) :: l -> ( - match Int.compare i k with - | 0 -> cons k (f v) l + | x :: l -> ( + match Int.compare i x.var with + | 0 -> cons x.var (f x.coe) l | -1 -> cons i (f Q.zero) t - | 1 -> (k, v) :: update i f l + | 1 -> x :: update i f l | _ -> failwith "compare_num" ) let rec set i n t = match t with | [] -> cons i n [] - | (k, v) :: l -> ( - match Int.compare i k with - | 0 -> cons k n l + | x :: l -> ( + match Int.compare i x.var with + | 0 -> cons x.var n l | -1 -> cons i n t - | 1 -> (k, v) :: set i n l + | 1 -> x :: set i n l | _ -> failwith "compare_num" ) -let cst n = if n =/ Q.zero then [] else [(0, n)] +let cst n = if n =/ Q.zero then [] else [{var = 0; coe = n}] let mul z t = if z =/ Q.zero then [] else if z =/ Q.one then t - else List.map (fun (i, n) -> (i, z */ n)) t + else List.map (fun {var = i; coe = n} -> {var = i; coe = z */ n}) t let div z t = - if z <>/ Q.one then List.map (fun (x, nx) -> (x, nx // z)) t else t + if z <>/ Q.one then + List.map (fun {var = x; coe = nx} -> {var = x; coe = nx // z}) t + else t -let uminus t = List.map (fun (i, n) -> (i, Q.neg n)) t +let uminus t = List.map (fun {var = i; coe = n} -> {var = i; coe = Q.neg n}) t let rec add (ve1 : t) (ve2 : t) = match (ve1, ve2) with | [], v | v, [] -> v - | (v1, c1) :: l1, (v2, c2) :: l2 -> + | {var = v1; coe = c1} :: l1, {var = v2; coe = c2} :: l2 -> let cmp = Int.compare v1 v2 in if cmp == 0 then let s = c1 +/ c2 in - if Q.zero =/ s then add l1 l2 else (v1, s) :: add l1 l2 - else if cmp < 0 then (v1, c1) :: add l1 ve2 - else (v2, c2) :: add l2 ve1 + if Q.zero =/ s then add l1 l2 else {var = v1; coe = s} :: add l1 l2 + else if cmp < 0 then {var = v1; coe = c1} :: add l1 ve2 + else {var = v2; coe = c2} :: add l2 ve1 let rec xmul_add (n1 : Q.t) (ve1 : t) (n2 : Q.t) (ve2 : t) = match (ve1, ve2) with | [], _ -> mul n2 ve2 | _, [] -> mul n1 ve1 - | (v1, c1) :: l1, (v2, c2) :: l2 -> + | {var = v1; coe = c1} :: l1, {var = v2; coe = c2} :: l2 -> let cmp = Int.compare v1 v2 in if cmp == 0 then let s = (n1 */ c1) +/ (n2 */ c2) in if Q.zero =/ s then xmul_add n1 l1 n2 l2 - else (v1, s) :: xmul_add n1 l1 n2 l2 - else if cmp < 0 then (v1, n1 */ c1) :: xmul_add n1 l1 n2 ve2 - else (v2, n2 */ c2) :: xmul_add n1 ve1 n2 l2 + else {var = v1; coe = s} :: xmul_add n1 l1 n2 l2 + else if cmp < 0 then {var = v1; coe = n1 */ c1} :: xmul_add n1 l1 n2 ve2 + else {var = v2; coe = n2 */ c2} :: xmul_add n1 ve1 n2 l2 let mul_add n1 ve1 n2 ve2 = if n1 =/ Q.one && n2 =/ Q.one then add ve1 ve2 else xmul_add n1 ve1 n2 ve2 @@ -157,8 +165,7 @@ let mul_add n1 ve1 n2 ve2 = let compare : t -> t -> int = Mutils.Cmp.compare_list (fun x y -> Mutils.Cmp.compare_lexical - [ (fun () -> Int.compare (fst x) (fst y)) - ; (fun () -> Q.compare (snd x) (snd y)) ]) + [(fun () -> Int.compare x.var y.var); (fun () -> Q.compare x.coe y.coe)]) (** [tail v vect] returns - [None] if [v] is not a variable of the vector [vect] @@ -169,7 +176,7 @@ let compare : t -> t -> int = let rec tail (v : var) (vect : t) = match vect with | [] -> None - | (v', vl) :: vect' -> ( + | {var = v'; coe = vl} :: vect' -> ( match Int.compare v' v with | 0 -> Some (vl, vect) (* Ok, found *) | -1 -> tail v vect' (* Might be in the tail *) @@ -178,38 +185,49 @@ let rec tail (v : var) (vect : t) = (* Hopeless *) let get v vect = match tail v vect with None -> Q.zero | Some (vl, _) -> vl -let is_constant v = match v with [] | [(0, _)] -> true | _ -> false -let get_cst vect = match vect with (0, v) :: _ -> v | _ -> Q.zero -let choose v = match v with [] -> None | (vr, vl) :: rst -> Some (vr, vl, rst) -let rec fresh v = match v with [] -> 1 | [(v, _)] -> v + 1 | _ :: v -> fresh v -let variables v = List.fold_left (fun acc (x, _) -> ISet.add x acc) ISet.empty v -let decomp_cst v = match v with (0, vl) :: v -> (vl, v) | _ -> (Q.zero, v) +let is_constant v = match v with [] | [{var = 0}] -> true | _ -> false +let get_cst vect = match vect with {var = 0; coe = v} :: _ -> v | _ -> Q.zero + +let choose v = + match v with [] -> None | {var = vr; coe = vl} :: rst -> Some (vr, vl, rst) + +let rec fresh v = + match v with [] -> 1 | [{var = v}] -> v + 1 | _ :: v -> fresh v + +let variables v = + List.fold_left (fun acc {var = x} -> ISet.add x acc) ISet.empty v + +let decomp_cst v = + match v with {var = 0; coe = vl} :: v -> (vl, v) | _ -> (Q.zero, v) let rec decomp_at i v = match v with | [] -> (Q.zero, null) - | (vr, vl) :: r -> - if i = vr then (vl, r) else if i < vr then (Q.zero, v) else decomp_at i r + | {var = vr; coe = vl} :: r -> + if Int.equal i vr then (vl, r) + else if i < vr then (Q.zero, v) + else decomp_at i r -let decomp_fst v = match v with [] -> ((0, Q.zero), []) | x :: v -> (x, v) +let decomp_fst v = + match v with [] -> ((0, Q.zero), []) | x :: v -> ((x.var, x.coe), v) let rec subst (vr : int) (e : t) (v : t) = match v with | [] -> [] - | (x, n) :: v' -> ( + | {var = x; coe = n} :: v' -> ( match Int.compare vr x with | 0 -> mul_add n e Q.one v' | -1 -> v - | 1 -> add [(x, n)] (subst vr e v') + | 1 -> add [{var = x; coe = n}] (subst vr e v') | _ -> assert false ) -let fold f acc v = List.fold_left (fun acc (v, i) -> f acc v i) acc v +let fold f acc v = List.fold_left (fun acc x -> f acc x.var x.coe) acc v let fold_error f acc v = let rec fold acc v = match v with | [] -> Some acc - | (x, i) :: v' -> ( + | {var = x; coe = i} :: v' -> ( match f acc x i with None -> None | Some acc' -> fold acc' v' ) in fold acc v @@ -217,11 +235,12 @@ let fold_error f acc v = let rec find p v = match v with | [] -> None - | (v, n) :: v' -> ( match p v n with None -> find p v' | Some r -> Some r ) + | {var = v; coe = n} :: v' -> ( + match p v n with None -> find p v' | Some r -> Some r ) -let for_all p l = List.for_all (fun (v, n) -> p v n) l -let decr_var i v = List.map (fun (v, n) -> (v - i, n)) v -let incr_var i v = List.map (fun (v, n) -> (v + i, n)) v +let for_all p l = List.for_all (fun {var = v; coe = n} -> p v n) l +let decr_var i v = List.map (fun x -> {x with var = x.var - i}) v +let incr_var i v = List.map (fun x -> {x with var = x.var + i}) v let gcd v = let res = @@ -239,12 +258,15 @@ let normalise v = let gcd = fold (fun c _ n -> Z.gcd c (Q.num n)) Z.zero v in if Int.equal (Z.compare gcd Z.zero) 0 then Z.one else gcd in - List.map (fun (x, v) -> (x, v */ Q.of_bigint ppcm // Q.of_bigint gcd)) v + List.map + (fun {var = x; coe = v} -> + {var = x; coe = v */ Q.of_bigint ppcm // Q.of_bigint gcd}) + v let rec exists2 p vect1 vect2 = match (vect1, vect2) with | _, [] | [], _ -> None - | (v1, n1) :: vect1', (v2, n2) :: vect2' -> + | {var = v1; coe = n1} :: vect1', {var = v2; coe = n2} :: vect2' -> if Int.equal v1 v2 then if p n1 n2 then Some (v1, n1, n2) else exists2 p vect1' vect2' else if v1 < v2 then exists2 p vect1' vect2 @@ -254,26 +276,26 @@ let dotproduct v1 v2 = let rec dot acc v1 v2 = match (v1, v2) with | [], _ | _, [] -> acc - | (x1, n1) :: v1', (x2, n2) :: v2' -> - if x1 == x2 then dot (acc +/ (n1 */ n2)) v1' v2' + | {var = x1; coe = n1} :: v1', {var = x2; coe = n2} :: v2' -> + if Int.equal x1 x2 then dot (acc +/ (n1 */ n2)) v1' v2' else if x1 < x2 then dot acc v1' v2 else dot acc v1 v2' in dot Q.zero v1 v2 -let map f v = List.map (fun (x, v) -> f x v) v +let map f v = List.map (fun {var = x; coe = v} -> f x v) v let abs_min_elt v = match v with | [] -> None - | (v, vl) :: r -> + | {var = v; coe = vl} :: r -> Some (List.fold_left - (fun (v1, vl1) (v2, vl2) -> + (fun (v1, vl1) {var = v2; coe = vl2} -> if Q.abs vl1 </ Q.abs vl2 then (v1, vl1) else (v2, vl2)) (v, vl) r) -let partition p = List.partition (fun (vr, vl) -> p vr vl) +let partition p = List.partition (fun {var = vr; coe = vl} -> p vr vl) let mkvar x = set x Q.one null module Bound = struct @@ -281,7 +303,9 @@ module Bound = struct let of_vect (v : vector) = match v with - | [(x, v)] -> if x = 0 then None else Some {cst = Q.zero; var = x; coeff = v} - | [(0, v); (x, v')] -> Some {cst = v; var = x; coeff = v'} + | [{var = x; coe = v}] -> + if Int.equal x 0 then None else Some {cst = Q.zero; var = x; coeff = v} + | [{var = 0; coe = v}; {var = x; coe = v'}] -> + Some {cst = v; var = x; coeff = v'} | _ -> None end diff --git a/test-suite/Makefile b/test-suite/Makefile index aca7ab0b28..6696f1431e 100644 --- a/test-suite/Makefile +++ b/test-suite/Makefile @@ -49,7 +49,8 @@ endif endif # exists ../_build export COQLIB -COQFLAGS?= +COQEXTRAFLAGS?= +COQFLAGS?=$(COQEXTRAFLAGS) coqc := $(BIN)coqc -q -R prerequisite TestSuite $(COQFLAGS) coqchk := $(BIN)coqchk -R prerequisite TestSuite diff --git a/test-suite/bugs/closed/bug_11846.v b/test-suite/bugs/closed/bug_11846.v new file mode 100644 index 0000000000..53517e7703 --- /dev/null +++ b/test-suite/bugs/closed/bug_11846.v @@ -0,0 +1,16 @@ +Require Import FunInd. + +Inductive tree : Type := +| Node : unit -> tree. + +Definition height (s : tree) : unit := +match s with +| Node h => h +end. + +Definition bal : forall l, let h := height l in tree := fun l => + let h := height l in + Node h. + +Set Warnings "+all". +Functional Scheme bal_ind := Induction for bal Sort Prop. diff --git a/test-suite/coq-makefile/native1/run.sh b/test-suite/coq-makefile/native1/run.sh index 8f9ab9a711..3ffe831b3c 100755 --- a/test-suite/coq-makefile/native1/run.sh +++ b/test-suite/coq-makefile/native1/run.sh @@ -1,7 +1,7 @@ #!/usr/bin/env bash -NATIVECOMP=$(grep "let no_native_compiler = false" ../../../config/coq_config.ml)||true -if [[ $(which ocamlopt) && $NATIVECOMP ]]; then +NONATIVECOMP=$(grep "let native_compiler = false" ../../../config/coq_config.ml)||true +if [[ $(which ocamlopt) && ! $NONATIVECOMP ]]; then . ../template/init.sh diff --git a/test-suite/coq-makefile/native2/_CoqProject b/test-suite/coq-makefile/native2/_CoqProject new file mode 100644 index 0000000000..61136e82f0 --- /dev/null +++ b/test-suite/coq-makefile/native2/_CoqProject @@ -0,0 +1,10 @@ +-R src test +-R theories test +-I src + +src/test_plugin.mlpack +src/test.mlg +src/test.mli +src/test_aux.ml +src/test_aux.mli +theories/test.v diff --git a/test-suite/coq-makefile/native2/run.sh b/test-suite/coq-makefile/native2/run.sh new file mode 100755 index 0000000000..857f70fdff --- /dev/null +++ b/test-suite/coq-makefile/native2/run.sh @@ -0,0 +1,33 @@ +#!/usr/bin/env bash + +NONATIVECOMP=$(grep "let native_compiler = false" ../../../config/coq_config.ml)||true +if [[ $(which ocamlopt) && ! $NONATIVECOMP ]]; then + +. ../template/init.sh + +coq_makefile -f _CoqProject -o Makefile +cat Makefile.conf +COQEXTRAFLAGS="-native-compiler yes" make +make html mlihtml +make install DSTROOT="$PWD/tmp" +#make debug +(cd "$(find tmp -name user-contrib)" && find .) | sort > actual +sort > desired <<EOT +. +./test +./test/test.glob +./test/test_plugin.cmi +./test/test_plugin.cmx +./test/test_plugin.cmxa +./test/test_plugin.cmxs +./test/test.v +./test/test.vo +./test/.coq-native +./test/.coq-native/Ntest_test.cmi +./test/.coq-native/Ntest_test.cmx +./test/.coq-native/Ntest_test.cmxs +EOT +exec diff -u desired actual + +fi +exit 0 # test skipped |