From 7e5dc9f830bc2cdbc3b8cc8b830adafc61660055 Mon Sep 17 00:00:00 2001
From: Jason Gross
Date: Fri, 26 Mar 2021 09:28:34 -0400
Subject: Fix Ltac2 `Array.init` exponential overhead

Previously, `Array.init` was computing the first element of the array
twice, resulting in exponential overhead in the number of recursive
nestings of `Array.init`.  Notably, since `Array.map` is implemented in
terms of `Array.init`, this exponential blowup shows up in any term
traversal based on `Array.map` over the arguments of application nodes.

Fixes #14011
---
 doc/changelog/04-tactics/14012-ltac2-array-init.rst | 4 ++++
 1 file changed, 4 insertions(+)
 create mode 100644 doc/changelog/04-tactics/14012-ltac2-array-init.rst

(limited to 'doc')

diff --git a/doc/changelog/04-tactics/14012-ltac2-array-init.rst b/doc/changelog/04-tactics/14012-ltac2-array-init.rst
new file mode 100644
index 0000000000..c79fc7e29a
--- /dev/null
+++ b/doc/changelog/04-tactics/14012-ltac2-array-init.rst
@@ -0,0 +1,4 @@
+- **Fixed:**
+  Ltac2 ``Array.init`` no longer incurs exponential overhead when used
+  recursively (`#14012 <https://github.com/coq/coq/pull/14012>`_, fixes `#14011
+  <https://github.com/coq/coq/issues/14011>`_, by Jason Gross).
-- 
cgit v1.2.3