data.hash_map | Mathlib porting status

Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

f0c8bf92

(last sync)

chore(*): removed unneeded imports (#18926)

This is another run of https://github.com/leanprover-community/mathlib/pull/17568, scrubbing unnecessary imports.

Like last time we only remove genuinely unneeded imports, and leave merely transitively redundant imports alone.

(I still disagree with the objectors to removing transitively redundant imports

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

Diff

@@ -6,6 +6,7 @@ Authors: Leonardo de Moura, Mario Carneiro
 import data.array.lemmas
 import data.list.join
 import data.list.range
+import data.list.nodup
 import data.pnat.defs
 
 /-!

4fcbc82d

chore(data/*): Removing unnecessary simp lemmas (#17062)

This PR adds a script that looks for and removes unnecessary lemmas in simp calls.

depends on: #17078

Diff

@@ -262,7 +262,7 @@ section
     { by_cases bidx = i,
       { subst i, rw [bkts', array.read_write, hfl],
         have := @valid.idx _ _ _ v bidx a,
-        simp only [hl, list.mem_append, or_imp_distrib, forall_and_distrib] at this ⊢,
+        simp only [hl, list.mem_append, or_imp_distrib] at this ⊢,
         exact ⟨⟨this.1.1, hal _⟩, this.2⟩ },
       { rw [bkts', array.read_write_of_ne _ _ h], apply v.idx } },
     { by_cases bidx = i,

f7707875

refactor(*): supremum of several recent refactoring PRs (#17381)

This is the supremum of

with imports fixed up to accommodate all the overlapping changes to imports.

Co-authored-by: Yury G. Kudryashov <urkud@urkud.name> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Yaël Dillies <yael.dillies@gmail.com>

Diff

@@ -6,7 +6,7 @@ Authors: Leonardo de Moura, Mario Carneiro
 import data.array.lemmas
 import data.list.join
 import data.list.range
-import data.pnat.basic
+import data.pnat.defs
 
 /-!
 # Hash maps

2220b0cb

(first ported)

Changes in mathlib3port

mathlib3

mathlib3port

2fe465de

bump to nightly-2024-04-25-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

ad7a2212

Diff

@@ -112,7 +112,7 @@ theorem mem_asList {a : Σ a, β a} : a ∈ data.asList ↔ ∃ i, a ∈ Array'.
     (∃ (l : List (Σ a : α, β a)) (i : Fin n.val), a ∈ l ∧ Array'.read data i = l) ↔
       ∃ i : Fin n.val, a ∈ Array'.read data i :=
     by rw [exists_swap] <;> exact exists_congr fun i => by simp
-  simp [as_list] <;> simpa [Array'.Mem.def, and_comm']
+  simp [as_list] <;> simpa [Array'.Mem.def, and_comm]
 #align bucket_array.mem_as_list BucketArray.mem_asList
 
 /-- Fold a function `f` over the key-value pairs in the bucket list -/
@@ -382,7 +382,7 @@ theorem Std.HashMap.Valid.eraseAux (a : α) :
   | ⟨a', b'⟩ :: t => by
     by_cases e : a' = a
     · subst a'
-      simpa [erase_aux, and_comm'] using
+      simpa [erase_aux, and_comm] using
         show ∃ (u w : _) (x : β a), t = u ++ w ∧ Sigma.mk a b' :: t = u ++ ⟨a, x⟩ :: w from
           ⟨[], t, b', by simp⟩
     · simp [erase_aux, e, Ne.symm e]
@@ -522,7 +522,7 @@ theorem Std.HashMap.insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArr
           c.fst ∉ l.map Sigma.fst ∧
             c.fst ∉ (BucketArray.asList t).map Sigma.fst ∧
               (l.map Sigma.fst).Disjoint ((BucketArray.asList t).map Sigma.fst)
-      by simpa [List.nodup_append, not_or, and_comm', and_left_comm] using nd with
+      by simpa [List.nodup_append, not_or, and_comm, and_left_comm] using nd with
     ⟨nd1, nd2, nm1, nm2, dj⟩
   have v' := v.insert _ _ c.2 fun Hc => nm2 <| (v.contains_aux_iff _ c.1).1 Hc
   apply IH _ _ v'
@@ -705,7 +705,7 @@ theorem Std.HashMap.mem_erase :
           Sigma.mk a' b' ∈ u ∨ Sigma.mk a' b' ∈ w ↔
             (¬a = a' ∧ a' = a) ∧ HEq b' b ∨ ¬a = a' ∧ (Sigma.mk a' b' ∈ u ∨ Sigma.mk a' b' ∈ w) :=
           by simp [eq_comm, not_and_self_iff, and_iff_right_of_imp this]
-        simpa [hl, show bkts'.as_list = _ from hfl, and_or_left, and_comm', and_left_comm,
+        simpa [hl, show bkts'.as_list = _ from hfl, and_or_left, and_comm, and_left_comm,
           or_left_comm]
       rintro m rfl; revert m; apply not_or.2
       have nd' := v.as_list_nodup _

2fe465de

bump to nightly-2024-04-06-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

e34029c9

Diff

@@ -7,7 +7,7 @@ import Data.Array.Lemmas
 import Data.List.Join
 import Data.List.Range
 import Data.List.Nodup
-import Data.Pnat.Defs
+import Data.PNat.Defs
 
 #align_import data.hash_map from "leanprover-community/mathlib"@"2fe465deb81bcd7ccafa065bb686888a82f15372"

2fe465de

bump to nightly-2024-03-17-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

22f01ce4

Diff

@@ -167,7 +167,7 @@ theorem Std.HashMap.findAux_iff {a : α} {b : β a} :
       have : a' ∉ t.map Sigma.fst := nd.not_mem
       exact this.elim (List.mem_map_of_mem Sigma.fst m)
     · have : Sigma.mk a b ≠ ⟨a', b'⟩ := by intro e; injection e with e; exact h e.symm
-      simp at nd ; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
+      simp at nd; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
 #align hash_map.find_aux_iff Std.HashMapₓ.findAux_iff
 
 /-- Returns `tt` if the bucket `l` contains the key `a` -/
@@ -181,7 +181,7 @@ theorem Std.HashMap.containsAux_iff {a : α} {l : List (Σ a, β a)} (nd : (l.ma
   unfold contains_aux
   cases' h : find_aux a l with b <;> simp
   · intro (b : β a) (m : Sigma.mk a b ∈ l)
-    rw [(find_aux_iff nd).2 m] at h 
+    rw [(find_aux_iff nd).2 m] at h
     contradiction
   · show ∃ b : β a, Sigma.mk a b ∈ l
     exact ⟨_, (find_aux_iff nd).1 h⟩
@@ -310,7 +310,7 @@ theorem Std.HashMap.Valid.modify {sz : ℕ} (v : valid bkts sz) :
   · by_cases bidx = i
     · subst i; rw [bkts', Array'.read_write, hfl]
       have := @valid.nodup _ _ _ v bidx
-      simp [hl, List.nodup_append] at this 
+      simp [hl, List.nodup_append] at this
       simp [List.nodup_append, this, hvnd, djuv, djwv.symm]
     · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.nodup
 #align hash_map.valid.modify Std.HashMapₓ.Valid.modify
@@ -355,11 +355,11 @@ theorem Std.HashMap.Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz :
   rcases Std.HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
       ((contains_aux_iff nd).1 Hc) with
     ⟨u, w, b', hl, hfl⟩
-  simp [hl, List.nodup_append] at nd 
+  simp [hl, List.nodup_append] at nd
   refine'
       (v.modify hash_fn u [⟨a, b'⟩] [⟨a, b⟩] w hl hfl (List.nodup_singleton _)
-          (fun a' e => by simp at e  <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
-    · revert e1; simp [-Sigma.exists] at e2 ; subst a'; simp [nd]
+          (fun a' e => by simp at e <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
+    · revert e1; simp [-Sigma.exists] at e2; subst a'; simp [nd]
 #align hash_map.valid.replace Std.HashMapₓ.Valid.replace
 
 theorem Std.HashMap.Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
@@ -369,8 +369,8 @@ theorem Std.HashMap.Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : 
   have nd := v.nodup (mk_idx n (hash_fn a))
   refine'
     (v.modify hash_fn [] [] [⟨a, b⟩] (bkts.read hash_fn a) rfl rfl (List.nodup_singleton _)
-        (fun a' e => by simp at e  <;> rw [e]) (fun a' => False.elim) fun a' e1 e2 => _).2
-  simp [-Sigma.exists] at e2 ; subst a'
+        (fun a' e => by simp at e <;> rw [e]) (fun a' => False.elim) fun a' e1 e2 => _).2
+  simp [-Sigma.exists] at e2; subst a'
   exact Hnc ((contains_aux_iff nd).2 e1)
 #align hash_map.valid.insert Std.HashMapₓ.Valid.insert
 
@@ -490,7 +490,7 @@ theorem Std.HashMap.keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β
 theorem Std.HashMap.find_empty (hash_fn : α → Nat) (n a) :
     (@mkHashMap α _ β hash_fn n).find a = none := by
   induction' h : (@mkHashMap α _ β hash_fn n).find a with <;> [rfl;
-    · have := (find_iff _ _ _).1 h; rw [entries_empty] at this ; contradiction]
+    · have := (find_iff _ _ _).1 h; rw [entries_empty] at this; contradiction]
 #align hash_map.find_empty Std.HashMapₓ.find_empty
 
 theorem Std.HashMap.not_contains_empty (hash_fn : α → Nat) (n a) :
@@ -511,7 +511,7 @@ theorem Std.HashMap.insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArr
             (sz + l.length)
     by
     have p := this bkts.as_list _ _ (mk_valid _ _)
-    rw [mk_as_list, List.append_nil, zero_add, v.len] at p 
+    rw [mk_as_list, List.append_nil, zero_add, v.len] at p
     rw [BucketArray.foldl_eq]
     exact p (v.as_list_nodup _)
   intro l; induction' l with c l IH <;> intro t sz v nd; · exact v
@@ -602,9 +602,9 @@ theorem Std.HashMap.mem_insert :
         refine' or_iff_left_of_imp (Not.elim <| not_or.2 _)
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩)
         · have na := (not_congr <| v.contains_aux_iff _ _).1 Hnc
-          simp [hl, not_or] at na ; simp [na]
+          simp [hl, not_or] at na; simp [na]
         · have nd' := v.as_list_nodup _
-          simp [hl, List.nodup_append] at nd' ; simp [nd']
+          simp [hl, List.nodup_append] at nd'; simp [nd']
       · suffices Sigma.mk a' b' ∉ v1 by simp [h, Ne.symm h, this]
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩) <;> simp [Ne.symm h]
     by_cases Hc : (contains_aux a bkt : Prop)
@@ -650,7 +650,7 @@ theorem Std.HashMap.find_insert_ne (m : Std.HashMap α β) (a a' : α) (b : β a
   Option.eq_of_eq_some fun b' =>
     let t := Std.HashMap.mem_insert m a b a' b'
     (Std.HashMap.find_iff _ _ _).trans <|
-      Iff.trans (by rwa [if_neg h] at t ) (Std.HashMap.find_iff _ _ _).symm
+      Iff.trans (by rwa [if_neg h] at t) (Std.HashMap.find_iff _ _ _).symm
 #align hash_map.find_insert_ne Std.HashMapₓ.find_insert_ne
 
 theorem Std.HashMap.find_insert (m : Std.HashMap α β) (a' a : α) (b : β a) :
@@ -709,7 +709,7 @@ theorem Std.HashMap.mem_erase :
           or_left_comm]
       rintro m rfl; revert m; apply not_or.2
       have nd' := v.as_list_nodup _
-      simp [hl, List.nodup_append] at nd' ; simp [nd']
+      simp [hl, List.nodup_append] at nd'; simp [nd']
     · suffices ∀ _ : Sigma.mk a' b' ∈ BucketArray.asList bkts, a ≠ a' by
         simp [erase, @dif_neg (contains_aux a bkt) _ Hc, entries, and_iff_right_of_imp this]
       rintro m rfl

2fe465de

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,11 +3,11 @@ Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Mario Carneiro
 -/
-import Mathbin.Data.Array.Lemmas
-import Mathbin.Data.List.Join
-import Mathbin.Data.List.Range
-import Mathbin.Data.List.Nodup
-import Mathbin.Data.Pnat.Defs
+import Data.Array.Lemmas
+import Data.List.Join
+import Data.List.Range
+import Data.List.Nodup
+import Data.Pnat.Defs
 
 #align_import data.hash_map from "leanprover-community/mathlib"@"2fe465deb81bcd7ccafa065bb686888a82f15372"

2fe465de

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,11 +2,6 @@
 Copyright (c) 2017 Microsoft Corporation. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Mario Carneiro
-
-! This file was ported from Lean 3 source module data.hash_map
-! leanprover-community/mathlib commit 2fe465deb81bcd7ccafa065bb686888a82f15372
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Data.Array.Lemmas
 import Mathbin.Data.List.Join
@@ -14,6 +9,8 @@ import Mathbin.Data.List.Range
 import Mathbin.Data.List.Nodup
 import Mathbin.Data.Pnat.Defs
 
+#align_import data.hash_map from "leanprover-community/mathlib"@"2fe465deb81bcd7ccafa065bb686888a82f15372"
+
 /-!
 # Hash maps

2fe465de

bump to nightly-2023-07-16-17

mathlib commit https://github.com/leanprover-community/mathlib/commit/2fe465deb81bcd7ccafa065bb686888a82f15372

6db63fa6

Diff

@@ -71,9 +71,9 @@ def BucketArray (α : Type u) (β : α → Type v) (n : ℕ+) :=
 #align bucket_array BucketArray
 
 /-- Make a hash_map index from a `nat` hash value and a (positive) buffer size -/
-def HashMap.mkIdx (n : ℕ+) (i : Nat) : Fin n :=
+def Std.HashMap.mkIdx (n : ℕ+) (i : Nat) : Fin n :=
   ⟨i % n, Nat.mod_lt _ n.2⟩
-#align hash_map.mk_idx HashMap.mkIdx
+#align hash_map.mk_idx Std.HashMapₓ.mkIdx
 
 namespace BucketArray
 
@@ -88,19 +88,19 @@ instance : Inhabited (BucketArray α β n) :=
 
 /-- Read the bucket corresponding to an element -/
 def read (a : α) : List (Σ a, β a) :=
-  let bidx := HashMap.mkIdx n (hash_fn a)
+  let bidx := Std.HashMap.mkIdx n (hash_fn a)
   data.read bidx
 #align bucket_array.read BucketArray.read
 
 /-- Write the bucket corresponding to an element -/
 def write (a : α) (l : List (Σ a, β a)) : BucketArray α β n :=
-  let bidx := HashMap.mkIdx n (hash_fn a)
+  let bidx := Std.HashMap.mkIdx n (hash_fn a)
   data.write bidx l
 #align bucket_array.write BucketArray.write
 
 /-- Modify (read, apply `f`, and write) the bucket corresponding to an element -/
 def modify (a : α) (f : List (Σ a, β a) → List (Σ a, β a)) : BucketArray α β n :=
-  let bidx := HashMap.mkIdx n (hash_fn a)
+  let bidx := Std.HashMap.mkIdx n (hash_fn a)
   Array'.write data bidx (f (Array'.read data bidx))
 #align bucket_array.modify BucketArray.modify
 
@@ -132,7 +132,7 @@ end
 
 end BucketArray
 
-namespace HashMap
+namespace Std.HashMap
 
 section
 
@@ -140,25 +140,26 @@ parameter {α : Type u} {β : α → Type v} (hash_fn : α → Nat)
 
 /-- Insert the pair `⟨a, b⟩` into the correct location in the bucket array
   (without checking for duplication) -/
-def reinsertAux {n} (data : BucketArray α β n) (a : α) (b : β a) : BucketArray α β n :=
+def Std.HashMap.reinsertAux {n} (data : BucketArray α β n) (a : α) (b : β a) : BucketArray α β n :=
   data.modify hash_fn a fun l => ⟨a, b⟩ :: l
-#align hash_map.reinsert_aux HashMap.reinsertAux
+#align hash_map.reinsert_aux Std.HashMapₓ.reinsertAux
 
-theorem mk_asList (n : ℕ+) : BucketArray.asList (mkArray' n [] : BucketArray α β n) = [] :=
+theorem Std.HashMap.mk_asList (n : ℕ+) :
+    BucketArray.asList (mkArray' n [] : BucketArray α β n) = [] :=
   List.eq_nil_iff_forall_not_mem.mpr fun x m =>
     let ⟨i, h⟩ := (BucketArray.mem_asList _).1 m
     h
-#align hash_map.mk_as_list HashMap.mk_asList
+#align hash_map.mk_as_list Std.HashMapₓ.mk_asList
 
 parameter [DecidableEq α]
 
 /-- Search a bucket for a key `a` and return the value -/
-def findAux (a : α) : List (Σ a, β a) → Option (β a)
+def Std.HashMap.findAux (a : α) : List (Σ a, β a) → Option (β a)
   | [] => none
   | ⟨a', b⟩ :: t => if h : a' = a then some (Eq.recOn h b) else find_aux t
-#align hash_map.find_aux HashMap.findAux
+#align hash_map.find_aux Std.HashMapₓ.findAux
 
-theorem findAux_iff {a : α} {b : β a} :
+theorem Std.HashMap.findAux_iff {a : α} {b : β a} :
     ∀ {l : List (Σ a, β a)}, (l.map Sigma.fst).Nodup → (find_aux a l = some b ↔ Sigma.mk a b ∈ l)
   | [], nd => ⟨fun n => by injection n, False.elim⟩
   | ⟨a', b'⟩ :: t, nd => by
@@ -170,14 +171,14 @@ theorem findAux_iff {a : α} {b : β a} :
       exact this.elim (List.mem_map_of_mem Sigma.fst m)
     · have : Sigma.mk a b ≠ ⟨a', b'⟩ := by intro e; injection e with e; exact h e.symm
       simp at nd ; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
-#align hash_map.find_aux_iff HashMap.findAux_iff
+#align hash_map.find_aux_iff Std.HashMapₓ.findAux_iff
 
 /-- Returns `tt` if the bucket `l` contains the key `a` -/
-def containsAux (a : α) (l : List (Σ a, β a)) : Bool :=
+def Std.HashMap.containsAux (a : α) (l : List (Σ a, β a)) : Bool :=
   (find_aux a l).isSome
-#align hash_map.contains_aux HashMap.containsAux
+#align hash_map.contains_aux Std.HashMapₓ.containsAux
 
-theorem containsAux_iff {a : α} {l : List (Σ a, β a)} (nd : (l.map Sigma.fst).Nodup) :
+theorem Std.HashMap.containsAux_iff {a : α} {l : List (Σ a, β a)} (nd : (l.map Sigma.fst).Nodup) :
     contains_aux a l ↔ a ∈ l.map Sigma.fst :=
   by
   unfold contains_aux
@@ -187,47 +188,47 @@ theorem containsAux_iff {a : α} {l : List (Σ a, β a)} (nd : (l.map Sigma.fst)
     contradiction
   · show ∃ b : β a, Sigma.mk a b ∈ l
     exact ⟨_, (find_aux_iff nd).1 h⟩
-#align hash_map.contains_aux_iff HashMap.containsAux_iff
+#align hash_map.contains_aux_iff Std.HashMapₓ.containsAux_iff
 
 /-- Modify a bucket to replace a value in the list. Leaves the list
  unchanged if the key is not found. -/
-def replaceAux (a : α) (b : β a) : List (Σ a, β a) → List (Σ a, β a)
+def Std.HashMap.replaceAux (a : α) (b : β a) : List (Σ a, β a) → List (Σ a, β a)
   | [] => []
   | ⟨a', b'⟩ :: t => if a' = a then ⟨a, b⟩ :: t else ⟨a', b'⟩ :: replace_aux t
-#align hash_map.replace_aux HashMap.replaceAux
+#align hash_map.replace_aux Std.HashMapₓ.replaceAux
 
 /-- Modify a bucket to remove a key, if it exists. -/
-def eraseAux (a : α) : List (Σ a, β a) → List (Σ a, β a)
+def Std.HashMap.eraseAux (a : α) : List (Σ a, β a) → List (Σ a, β a)
   | [] => []
   | ⟨a', b'⟩ :: t => if a' = a then t else ⟨a', b'⟩ :: erase_aux t
-#align hash_map.erase_aux HashMap.eraseAux
+#align hash_map.erase_aux Std.HashMapₓ.eraseAux
 
 /-- The predicate `valid bkts sz` means that `bkts` satisfies the `hash_map`
   invariants: There are exactly `sz` elements in it, every pair is in the
   bucket determined by its key and the hash function, and no key appears
   multiple times in the list. -/
-structure Valid {n} (bkts : BucketArray α β n) (sz : Nat) : Prop where
+structure Std.HashMap.Valid {n} (bkts : BucketArray α β n) (sz : Nat) : Prop where
   len : bkts.asList.length = sz
-  idx : ∀ {i} {a : Σ a, β a}, a ∈ Array'.read bkts i → mkIdx n (hash_fn a.1) = i
+  idx : ∀ {i} {a : Σ a, β a}, a ∈ Array'.read bkts i → Std.HashMap.mkIdx n (hash_fn a.1) = i
   Nodup : ∀ i, ((Array'.read bkts i).map Sigma.fst).Nodup
-#align hash_map.valid HashMap.Valid
+#align hash_map.valid Std.HashMapₓ.Valid
 
-theorem Valid.idx_enum {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz) {i l}
-    (he : (i, l) ∈ bkts.toList.enum) {a} {b : β a} (hl : Sigma.mk a b ∈ l) :
-    ∃ h, mkIdx n (hash_fn a) = ⟨i, h⟩ :=
+theorem Std.HashMap.Valid.idx_enum {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz)
+    {i l} (he : (i, l) ∈ bkts.toList.enum) {a} {b : β a} (hl : Sigma.mk a b ∈ l) :
+    ∃ h, Std.HashMap.mkIdx n (hash_fn a) = ⟨i, h⟩ :=
   (Array'.mem_toList_enum.mp he).imp fun h e => by subst e <;> exact v.idx hl
-#align hash_map.valid.idx_enum HashMap.Valid.idx_enum
+#align hash_map.valid.idx_enum Std.HashMapₓ.Valid.idx_enum
 
-theorem Valid.idx_enum_1 {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz) {i l}
-    (he : (i, l) ∈ bkts.toList.enum) {a} {b : β a} (hl : Sigma.mk a b ∈ l) :
-    (mkIdx n (hash_fn a)).1 = i :=
+theorem Std.HashMap.Valid.idx_enum_1 {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz)
+    {i l} (he : (i, l) ∈ bkts.toList.enum) {a} {b : β a} (hl : Sigma.mk a b ∈ l) :
+    (Std.HashMap.mkIdx n (hash_fn a)).1 = i :=
   by
   let ⟨h, e⟩ := v.idx_enum _ he hl
   rw [e] <;> rfl
-#align hash_map.valid.idx_enum_1 HashMap.Valid.idx_enum_1
+#align hash_map.valid.idx_enum_1 Std.HashMapₓ.Valid.idx_enum_1
 
-theorem Valid.asList_nodup {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz) :
-    (bkts.asList.map Sigma.fst).Nodup :=
+theorem Std.HashMap.Valid.asList_nodup {n} {bkts : BucketArray α β n} {sz : Nat}
+    (v : valid bkts sz) : (bkts.asList.map Sigma.fst).Nodup :=
   by
   suffices (bkts.to_list.map (List.map Sigma.fst)).Pairwise List.Disjoint
     by
@@ -242,22 +243,23 @@ theorem Valid.asList_nodup {n} {bkts : BucketArray α β n} {sz : Nat} (v : vali
   rw [Prod.forall]; intro j l₂ me₁ me₂ ij
   simp [List.Disjoint]; intro a b ml₁ b' ml₂
   apply ij; rwa [← v.idx_enum_1 _ me₁ ml₁, ← v.idx_enum_1 _ me₂ ml₂]
-#align hash_map.valid.as_list_nodup HashMap.Valid.asList_nodup
+#align hash_map.valid.as_list_nodup Std.HashMapₓ.Valid.asList_nodup
 
-theorem mk_valid (n : ℕ+) : @valid n (mkArray' n []) 0 :=
+theorem Std.HashMap.mk_valid (n : ℕ+) : @valid n (mkArray' n []) 0 :=
   ⟨by simp [mk_as_list], fun i a h => by cases h, fun i => List.nodup_nil⟩
-#align hash_map.mk_valid HashMap.mk_valid
+#align hash_map.mk_valid Std.HashMapₓ.mk_valid
 
-theorem Valid.findAux_iff {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz) {a : α}
-    {b : β a} : find_aux a (bkts.read hash_fn a) = some b ↔ Sigma.mk a b ∈ bkts.asList :=
+theorem Std.HashMap.Valid.findAux_iff {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz)
+    {a : α} {b : β a} : find_aux a (bkts.read hash_fn a) = some b ↔ Sigma.mk a b ∈ bkts.asList :=
   (find_aux_iff (v.Nodup _)).trans <| by
     rw [bkts.mem_as_list] <;> exact ⟨fun h => ⟨_, h⟩, fun ⟨i, h⟩ => (v.idx h).symm ▸ h⟩
-#align hash_map.valid.find_aux_iff HashMap.Valid.findAux_iff
+#align hash_map.valid.find_aux_iff Std.HashMapₓ.Valid.findAux_iff
 
-theorem Valid.containsAux_iff {n} {bkts : BucketArray α β n} {sz : Nat} (v : valid bkts sz)
-    (a : α) : contains_aux a (bkts.read hash_fn a) ↔ a ∈ bkts.asList.map Sigma.fst := by
+theorem Std.HashMap.Valid.containsAux_iff {n} {bkts : BucketArray α β n} {sz : Nat}
+    (v : valid bkts sz) (a : α) :
+    contains_aux a (bkts.read hash_fn a) ↔ a ∈ bkts.asList.map Sigma.fst := by
   simp [contains_aux, Option.isSome_iff_exists, v.find_aux_iff hash_fn]
-#align hash_map.valid.contains_aux_iff HashMap.Valid.containsAux_iff
+#align hash_map.valid.contains_aux_iff Std.HashMapₓ.Valid.containsAux_iff
 
 section
 
@@ -271,7 +273,8 @@ private def bkts' : BucketArray α β n :=
 
 variable (hl : L = u ++ v1 ++ w) (hfl : f L = u ++ v2 ++ w)
 
-theorem append_of_modify : ∃ u' w', bkts.asList = u' ++ v1 ++ w' ∧ bkts'.asList = u' ++ v2 ++ w' :=
+theorem Std.HashMap.append_of_modify :
+    ∃ u' w', bkts.asList = u' ++ v1 ++ w' ∧ bkts'.asList = u' ++ v2 ++ w' :=
   by
   unfold BucketArray.asList
   have h : (bidx : ℕ) < bkts.to_list.length := by simp only [bidx.is_lt, Array'.toList_length]
@@ -286,14 +289,14 @@ theorem append_of_modify : ∃ u' w', bkts.asList = u' ++ v1 ++ w' ∧ bkts'.asL
       rw [bkts', Array'.write_toList, List.set_eq_take_cons_drop _ h]
       simp [hfl]
     simp
-#align hash_map.append_of_modify HashMap.append_of_modify
+#align hash_map.append_of_modify Std.HashMapₓ.append_of_modify
 
 variable (hvnd : (v2.map Sigma.fst).Nodup)
-  (hal : ∀ a : Σ a, β a, a ∈ v2 → mkIdx n (hash_fn a.1) = bidx)
+  (hal : ∀ a : Σ a, β a, a ∈ v2 → Std.HashMap.mkIdx n (hash_fn a.1) = bidx)
   (djuv : (u.map Sigma.fst).Disjoint (v2.map Sigma.fst))
   (djwv : (w.map Sigma.fst).Disjoint (v2.map Sigma.fst))
 
-theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
+theorem Std.HashMap.Valid.modify {sz : ℕ} (v : valid bkts sz) :
     v1.length ≤ sz + v2.length ∧ valid bkts' (sz + v2.length - v1.length) :=
   by
   rcases append_of_modify u v1 v2 w hl hfl with ⟨u', w', e₁, e₂⟩
@@ -313,11 +316,11 @@ theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
       simp [hl, List.nodup_append] at this 
       simp [List.nodup_append, this, hvnd, djuv, djwv.symm]
     · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.nodup
-#align hash_map.valid.modify HashMap.Valid.modify
+#align hash_map.valid.modify Std.HashMapₓ.Valid.modify
 
 end
 
-theorem Valid.replaceAux (a : α) (b : β a) :
+theorem Std.HashMap.Valid.replaceAux (a : α) (b : β a) :
     ∀ l : List (Σ a, β a),
       a ∈ l.map Sigma.fst →
         ∃ (u w : List (Σ a, β a)) (b' : _),
@@ -345,14 +348,14 @@ theorem Valid.replaceAux (a : α) (b : β a) :
         by simpa using valid.replace_aux t
       rcases IH x m with ⟨u, w, b'', hl, hfl⟩
       exact ⟨⟨a', b'⟩ :: u, w, b'', by simp [hl, hfl.symm, Ne.symm e]⟩
-#align hash_map.valid.replace_aux HashMap.Valid.replaceAux
+#align hash_map.valid.replace_aux Std.HashMapₓ.Valid.replaceAux
 
-theorem Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
+theorem Std.HashMap.Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
     (Hc : contains_aux a (bkts.read hash_fn a)) (v : valid bkts sz) :
     valid (bkts.modify hash_fn a (replace_aux a b)) sz :=
   by
   have nd := v.nodup (mk_idx n (hash_fn a))
-  rcases HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
+  rcases Std.HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
       ((contains_aux_iff nd).1 Hc) with
     ⟨u, w, b', hl, hfl⟩
   simp [hl, List.nodup_append] at nd 
@@ -360,9 +363,9 @@ theorem Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α
       (v.modify hash_fn u [⟨a, b'⟩] [⟨a, b⟩] w hl hfl (List.nodup_singleton _)
           (fun a' e => by simp at e  <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
     · revert e1; simp [-Sigma.exists] at e2 ; subst a'; simp [nd]
-#align hash_map.valid.replace HashMap.Valid.replace
+#align hash_map.valid.replace Std.HashMapₓ.Valid.replace
 
-theorem Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
+theorem Std.HashMap.Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
     (Hnc : ¬contains_aux a (bkts.read hash_fn a)) (v : valid bkts sz) :
     valid (reinsert_aux bkts a b) (sz + 1) :=
   by
@@ -372,9 +375,9 @@ theorem Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α)
         (fun a' e => by simp at e  <;> rw [e]) (fun a' => False.elim) fun a' e1 e2 => _).2
   simp [-Sigma.exists] at e2 ; subst a'
   exact Hnc ((contains_aux_iff nd).2 e1)
-#align hash_map.valid.insert HashMap.Valid.insert
+#align hash_map.valid.insert Std.HashMapₓ.Valid.insert
 
-theorem Valid.eraseAux (a : α) :
+theorem Std.HashMap.Valid.eraseAux (a : α) :
     ∀ l : List (Σ a, β a),
       a ∈ l.map Sigma.fst →
         ∃ (u w : List (Σ a, β a)) (b : _), l = u ++ [⟨a, b⟩] ++ w ∧ erase_aux a l = u ++ [] ++ w
@@ -398,106 +401,110 @@ theorem Valid.eraseAux (a : α) :
         by simpa using valid.erase_aux t
       rcases IH b m with ⟨u, w, b'', hl, hfl⟩
       exact ⟨⟨a', b'⟩ :: u, w, b'', by simp [hl, hfl.symm]⟩
-#align hash_map.valid.erase_aux HashMap.Valid.eraseAux
+#align hash_map.valid.erase_aux Std.HashMapₓ.Valid.eraseAux
 
-theorem Valid.erase {n} {bkts : BucketArray α β n} {sz} (a : α)
+theorem Std.HashMap.Valid.erase {n} {bkts : BucketArray α β n} {sz} (a : α)
     (Hc : contains_aux a (bkts.read hash_fn a)) (v : valid bkts sz) :
     valid (bkts.modify hash_fn a (erase_aux a)) (sz - 1) :=
   by
   have nd := v.nodup (mk_idx n (hash_fn a))
-  rcases HashMap.Valid.eraseAux a (Array'.read bkts (mk_idx n (hash_fn a)))
+  rcases Std.HashMap.Valid.eraseAux a (Array'.read bkts (mk_idx n (hash_fn a)))
       ((contains_aux_iff nd).1 Hc) with
     ⟨u, w, b, hl, hfl⟩
   refine' (v.modify hash_fn u [⟨a, b⟩] [] w hl hfl List.nodup_nil _ _ _).2 <;> simp
-#align hash_map.valid.erase HashMap.Valid.erase
+#align hash_map.valid.erase Std.HashMapₓ.Valid.erase
 
 end
 
-end HashMap
+end Std.HashMap
 
 /-- A hash map data structure, representing a finite key-value map
   with key type `α` and value type `β` (which may depend on `α`). -/
-structure HashMap (α : Type u) [DecidableEq α] (β : α → Type v) where
+structure Std.HashMap (α : Type u) [DecidableEq α] (β : α → Type v) where
   hashFn : α → Nat
   size : ℕ
   nbuckets : ℕ+
   buckets : BucketArray α β nbuckets
-  is_valid : HashMap.Valid hash_fn buckets size
-#align hash_map HashMap
+  is_valid : Std.HashMap.Valid hash_fn buckets size
+#align hash_map Std.HashMapₓ
 
 /-- Construct an empty hash map with buffer size `nbuckets` (default 8). -/
 def mkHashMap {α : Type u} [DecidableEq α] {β : α → Type v} (hash_fn : α → Nat) (nbuckets := 8) :
-    HashMap α β :=
+    Std.HashMap α β :=
   let n := if nbuckets = 0 then 8 else nbuckets
   let nz : n > 0 := by abstract cases nbuckets <;> simp [if_pos, Nat.succ_ne_zero]
   { hashFn
     size := 0
     nbuckets := ⟨n, nz⟩
     buckets := mkArray' n []
-    is_valid := HashMap.mk_valid _ _ }
+    is_valid := Std.HashMap.mk_valid _ _ }
 #align mk_hash_map mkHashMap
 
-namespace HashMap
+namespace Std.HashMap
 
 variable {α : Type u} {β : α → Type v} [DecidableEq α]
 
 /-- Return the value corresponding to a key, or `none` if not found -/
-def find (m : HashMap α β) (a : α) : Option (β a) :=
-  findAux a (m.buckets.read m.hashFn a)
-#align hash_map.find HashMap.find
+def Std.HashMap.find (m : Std.HashMap α β) (a : α) : Option (β a) :=
+  Std.HashMap.findAux a (m.buckets.read m.hashFn a)
+#align hash_map.find Std.HashMapₓ.find
 
 /-- Return `tt` if the key exists in the map -/
-def contains (m : HashMap α β) (a : α) : Bool :=
+def Std.HashMap.contains (m : Std.HashMap α β) (a : α) : Bool :=
   (m.find a).isSome
-#align hash_map.contains HashMap.contains
+#align hash_map.contains Std.HashMapₓ.contains
 
-instance : Membership α (HashMap α β) :=
+instance : Membership α (Std.HashMap α β) :=
   ⟨fun a m => m.contains a⟩
 
 /-- Fold a function over the key-value pairs in the map -/
-def fold {δ : Type w} (m : HashMap α β) (d : δ) (f : δ → ∀ a, β a → δ) : δ :=
+def Std.HashMap.fold {δ : Type w} (m : Std.HashMap α β) (d : δ) (f : δ → ∀ a, β a → δ) : δ :=
   m.buckets.foldl d f
-#align hash_map.fold HashMap.fold
+#align hash_map.fold Std.HashMapₓ.fold
 
 /-- The list of key-value pairs in the map -/
-def entries (m : HashMap α β) : List (Σ a, β a) :=
+def Std.HashMap.entries (m : Std.HashMap α β) : List (Σ a, β a) :=
   m.buckets.asList
-#align hash_map.entries HashMap.entries
+#align hash_map.entries Std.HashMapₓ.entries
 
 /-- The list of keys in the map -/
-def keys (m : HashMap α β) : List α :=
+def Std.HashMap.keys (m : Std.HashMap α β) : List α :=
   m.entries.map Sigma.fst
-#align hash_map.keys HashMap.keys
+#align hash_map.keys Std.HashMapₓ.keys
 
-theorem find_iff (m : HashMap α β) (a : α) (b : β a) :
+theorem Std.HashMap.find_iff (m : Std.HashMap α β) (a : α) (b : β a) :
     m.find a = some b ↔ Sigma.mk a b ∈ m.entries :=
   m.is_valid.findAux_iff _
-#align hash_map.find_iff HashMap.find_iff
+#align hash_map.find_iff Std.HashMapₓ.find_iff
 
-theorem contains_iff (m : HashMap α β) (a : α) : m.contains a ↔ a ∈ m.keys :=
+theorem Std.HashMap.contains_iff (m : Std.HashMap α β) (a : α) : m.contains a ↔ a ∈ m.keys :=
   m.is_valid.containsAux_iff _ _
-#align hash_map.contains_iff HashMap.contains_iff
+#align hash_map.contains_iff Std.HashMapₓ.contains_iff
 
-theorem entries_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).entries = [] :=
-  mk_asList _
-#align hash_map.entries_empty HashMap.entries_empty
+theorem Std.HashMap.entries_empty (hash_fn : α → Nat) (n) :
+    (@mkHashMap α _ β hash_fn n).entries = [] :=
+  Std.HashMap.mk_asList _
+#align hash_map.entries_empty Std.HashMapₓ.entries_empty
 
-theorem keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).keys = [] := by
-  dsimp [keys] <;> rw [entries_empty] <;> rfl
-#align hash_map.keys_empty HashMap.keys_empty
+theorem Std.HashMap.keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).keys = [] :=
+  by dsimp [keys] <;> rw [entries_empty] <;> rfl
+#align hash_map.keys_empty Std.HashMapₓ.keys_empty
 
-theorem find_empty (hash_fn : α → Nat) (n a) : (@mkHashMap α _ β hash_fn n).find a = none := by
+theorem Std.HashMap.find_empty (hash_fn : α → Nat) (n a) :
+    (@mkHashMap α _ β hash_fn n).find a = none := by
   induction' h : (@mkHashMap α _ β hash_fn n).find a with <;> [rfl;
     · have := (find_iff _ _ _).1 h; rw [entries_empty] at this ; contradiction]
-#align hash_map.find_empty HashMap.find_empty
+#align hash_map.find_empty Std.HashMapₓ.find_empty
 
-theorem not_contains_empty (hash_fn : α → Nat) (n a) : ¬(@mkHashMap α _ β hash_fn n).contains a :=
-  by apply Bool.bool_iff_false.2 <;> dsimp [contains] <;> rw [find_empty] <;> rfl
-#align hash_map.not_contains_empty HashMap.not_contains_empty
+theorem Std.HashMap.not_contains_empty (hash_fn : α → Nat) (n a) :
+    ¬(@mkHashMap α _ β hash_fn n).contains a := by
+  apply Bool.bool_iff_false.2 <;> dsimp [contains] <;> rw [find_empty] <;> rfl
+#align hash_map.not_contains_empty Std.HashMapₓ.not_contains_empty
 
-theorem insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n} {sz}
-    (v : Valid hash_fn bkts sz) :
-    Valid hash_fn (bkts.foldl (mkArray' _ [] : BucketArray α β n') (reinsertAux hash_fn)) sz :=
+theorem Std.HashMap.insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n} {sz}
+    (v : Std.HashMap.Valid hash_fn bkts sz) :
+    Std.HashMap.Valid hash_fn
+      (bkts.foldl (mkArray' _ [] : BucketArray α β n') (Std.HashMap.reinsertAux hash_fn)) sz :=
   by
   suffices
     ∀ (l : List (Σ a, β a)) (t : BucketArray α β n') (sz),
@@ -541,17 +548,17 @@ theorem insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n}
     exact nm1.elim (@List.mem_map_of_mem _ _ Sigma.fst _ _ m1)
   · apply this
     simpa [reinsert_aux, BucketArray.modify, Array'.read_write_of_ne _ _ h] using im
-#align hash_map.insert_lemma HashMap.insert_lemma
+#align hash_map.insert_lemma Std.HashMapₓ.insert_lemma
 
 /-- Insert a key-value pair into the map. (Modifies `m` in-place when applicable) -/
-def insert : ∀ (m : HashMap α β) (a : α) (b : β a), HashMap α β
+def Std.HashMap.insert : ∀ (m : Std.HashMap α β) (a : α) (b : β a), Std.HashMap α β
   | ⟨hash_fn, size, n, buckets, v⟩, a, b =>
     let bkt := buckets.read hash_fn a
-    if hc : containsAux a bkt then
+    if hc : Std.HashMap.containsAux a bkt then
       { hashFn
         size
         nbuckets := n
-        buckets := buckets.modify hash_fn a (replaceAux a b)
+        buckets := buckets.modify hash_fn a (Std.HashMap.replaceAux a b)
         is_valid := v.replace _ a b hc }
     else
       let size' := size + 1
@@ -565,16 +572,17 @@ def insert : ∀ (m : HashMap α β) (a : α) (b : β a), HashMap α β
           is_valid := valid' }
       else
         let n' : ℕ+ := ⟨n * 2, mul_pos n.2 (by decide)⟩
-        let buckets'' : BucketArray α β n' := buckets'.foldl (mkArray' _ []) (reinsertAux hash_fn)
+        let buckets'' : BucketArray α β n' :=
+          buckets'.foldl (mkArray' _ []) (Std.HashMap.reinsertAux hash_fn)
         { hashFn
           size := size'
           nbuckets := n'
           buckets := buckets''
-          is_valid := insert_lemma _ valid' }
-#align hash_map.insert HashMap.insert
+          is_valid := Std.HashMap.insert_lemma _ valid' }
+#align hash_map.insert Std.HashMapₓ.insert
 
-theorem mem_insert :
-    ∀ (m : HashMap α β) (a b a' b'),
+theorem Std.HashMap.mem_insert :
+    ∀ (m : Std.HashMap α β) (a b a' b'),
       (Sigma.mk a' b' : Sigma β) ∈ (m.insert a b).entries ↔
         if a = a' then HEq b b' else Sigma.mk a' b' ∈ m.entries
   | ⟨hash_fn, size, n, bkts, v⟩, a, b, a', b' =>
@@ -603,7 +611,7 @@ theorem mem_insert :
       · suffices Sigma.mk a' b' ∉ v1 by simp [h, Ne.symm h, this]
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩) <;> simp [Ne.symm h]
     by_cases Hc : (contains_aux a bkt : Prop)
-    · rcases HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
+    · rcases Std.HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
           ((contains_aux_iff nd).1 Hc) with ⟨u', w', b'', hl', hfl'⟩
       rcases append_of_modify u' [⟨a, b''⟩] [⟨a, b⟩] w' hl' hfl' with ⟨u, w, hl, hfl⟩
       simpa [insert, @dif_pos (contains_aux a bkt) _ Hc] using
@@ -632,20 +640,23 @@ theorem mem_insert :
           rcases append_of_modify [] [] [⟨a'', b''⟩] _ rfl rfl with ⟨u, w, hl, hfl⟩
           simp [IH.symm, or_left_comm, show B.as_list = _ from hl,
             show (reinsert_aux hash_fn B a'' b'').asList = _ from hfl]
-#align hash_map.mem_insert HashMap.mem_insert
+#align hash_map.mem_insert Std.HashMapₓ.mem_insert
 
-theorem find_insert_eq (m : HashMap α β) (a : α) (b : β a) : (m.insert a b).find a = some b :=
-  (find_iff (m.insert a b) a b).2 <| (mem_insert m a b a b).2 <| by rw [if_pos rfl]
-#align hash_map.find_insert_eq HashMap.find_insert_eq
+theorem Std.HashMap.find_insert_eq (m : Std.HashMap α β) (a : α) (b : β a) :
+    (m.insert a b).find a = some b :=
+  (Std.HashMap.find_iff (m.insert a b) a b).2 <|
+    (Std.HashMap.mem_insert m a b a b).2 <| by rw [if_pos rfl]
+#align hash_map.find_insert_eq Std.HashMapₓ.find_insert_eq
 
-theorem find_insert_ne (m : HashMap α β) (a a' : α) (b : β a) (h : a ≠ a') :
+theorem Std.HashMap.find_insert_ne (m : Std.HashMap α β) (a a' : α) (b : β a) (h : a ≠ a') :
     (m.insert a b).find a' = m.find a' :=
   Option.eq_of_eq_some fun b' =>
-    let t := mem_insert m a b a' b'
-    (find_iff _ _ _).trans <| Iff.trans (by rwa [if_neg h] at t ) (find_iff _ _ _).symm
-#align hash_map.find_insert_ne HashMap.find_insert_ne
+    let t := Std.HashMap.mem_insert m a b a' b'
+    (Std.HashMap.find_iff _ _ _).trans <|
+      Iff.trans (by rwa [if_neg h] at t ) (Std.HashMap.find_iff _ _ _).symm
+#align hash_map.find_insert_ne Std.HashMapₓ.find_insert_ne
 
-theorem find_insert (m : HashMap α β) (a' a : α) (b : β a) :
+theorem Std.HashMap.find_insert (m : Std.HashMap α β) (a' a : α) (b : β a) :
     (m.insert a b).find a' = if h : a = a' then some (Eq.recOn h b) else m.find a' :=
   if h : a = a' then by
     rw [dif_pos h] <;>
@@ -653,33 +664,33 @@ theorem find_insert (m : HashMap α β) (a' a : α) (b : β a) :
         match a', h with
         | _, rfl => find_insert_eq m a b
   else by rw [dif_neg h] <;> exact find_insert_ne m a a' b h
-#align hash_map.find_insert HashMap.find_insert
+#align hash_map.find_insert Std.HashMapₓ.find_insert
 
 /-- Insert a list of key-value pairs into the map. (Modifies `m` in-place when applicable) -/
-def insertAll (l : List (Σ a, β a)) (m : HashMap α β) : HashMap α β :=
-  l.foldl (fun m ⟨a, b⟩ => insert m a b) m
-#align hash_map.insert_all HashMap.insertAll
+def Std.HashMap.insertAll (l : List (Σ a, β a)) (m : Std.HashMap α β) : Std.HashMap α β :=
+  l.foldl (fun m ⟨a, b⟩ => Std.HashMap.insert m a b) m
+#align hash_map.insert_all Std.HashMapₓ.insertAll
 
 /-- Construct a hash map from a list of key-value pairs. -/
-def ofList (l : List (Σ a, β a)) (hash_fn) : HashMap α β :=
-  insertAll l (mkHashMap hash_fn (2 * l.length))
-#align hash_map.of_list HashMap.ofList
+def Std.HashMap.ofList (l : List (Σ a, β a)) (hash_fn) : Std.HashMap α β :=
+  Std.HashMap.insertAll l (mkHashMap hash_fn (2 * l.length))
+#align hash_map.of_list Std.HashMapₓ.ofList
 
 /-- Remove a key from the map. (Modifies `m` in-place when applicable) -/
-def erase (m : HashMap α β) (a : α) : HashMap α β :=
+def Std.HashMap.erase (m : Std.HashMap α β) (a : α) : Std.HashMap α β :=
   match m with
   | ⟨hash_fn, size, n, buckets, v⟩ =>
-    if hc : containsAux a (buckets.read hash_fn a) then
+    if hc : Std.HashMap.containsAux a (buckets.read hash_fn a) then
       { hashFn
         size := size - 1
         nbuckets := n
-        buckets := buckets.modify hash_fn a (eraseAux a)
+        buckets := buckets.modify hash_fn a (Std.HashMap.eraseAux a)
         is_valid := v.eraseₓ _ a hc }
     else m
-#align hash_map.erase HashMap.erase
+#align hash_map.erase Std.HashMapₓ.erase
 
-theorem mem_erase :
-    ∀ (m : HashMap α β) (a a' b'),
+theorem Std.HashMap.mem_erase :
+    ∀ (m : Std.HashMap α β) (a a' b'),
       (Sigma.mk a' b' : Sigma β) ∈ (m.eraseₓ a).entries ↔ a ≠ a' ∧ Sigma.mk a' b' ∈ m.entries
   | ⟨hash_fn, size, n, bkts, v⟩, a, a', b' =>
     by
@@ -706,26 +717,27 @@ theorem mem_erase :
         simp [erase, @dif_neg (contains_aux a bkt) _ Hc, entries, and_iff_right_of_imp this]
       rintro m rfl
       exact Hc ((v.contains_aux_iff _ _).2 (List.mem_map_of_mem Sigma.fst m))
-#align hash_map.mem_erase HashMap.mem_erase
+#align hash_map.mem_erase Std.HashMapₓ.mem_erase
 
-theorem find_erase_eq (m : HashMap α β) (a : α) : (m.eraseₓ a).find a = none :=
+theorem Std.HashMap.find_erase_eq (m : Std.HashMap α β) (a : α) : (m.eraseₓ a).find a = none :=
   by
   cases' h : (m.erase a).find a with b; · rfl
   exact absurd rfl ((mem_erase m a a b).1 ((find_iff (m.erase a) a b).1 h)).left
-#align hash_map.find_erase_eq HashMap.find_erase_eq
+#align hash_map.find_erase_eq Std.HashMapₓ.find_erase_eq
 
-theorem find_erase_ne (m : HashMap α β) (a a' : α) (h : a ≠ a') :
+theorem Std.HashMap.find_erase_ne (m : Std.HashMap α β) (a a' : α) (h : a ≠ a') :
     (m.eraseₓ a).find a' = m.find a' :=
   Option.eq_of_eq_some fun b' =>
-    (find_iff _ _ _).trans <|
-      (mem_erase m a a' b').trans <| (and_iff_right h).trans (find_iff _ _ _).symm
-#align hash_map.find_erase_ne HashMap.find_erase_ne
+    (Std.HashMap.find_iff _ _ _).trans <|
+      (Std.HashMap.mem_erase m a a' b').trans <|
+        (and_iff_right h).trans (Std.HashMap.find_iff _ _ _).symm
+#align hash_map.find_erase_ne Std.HashMapₓ.find_erase_ne
 
-theorem find_erase (m : HashMap α β) (a' a : α) :
+theorem Std.HashMap.find_erase (m : Std.HashMap α β) (a' a : α) :
     (m.eraseₓ a).find a' = if a = a' then none else m.find a' :=
   if h : a = a' then by subst a' <;> simp [find_erase_eq m a]
   else by rw [if_neg h] <;> exact find_erase_ne m a a' h
-#align hash_map.find_erase HashMap.find_erase
+#align hash_map.find_erase Std.HashMapₓ.find_erase
 
 section String
 
@@ -736,10 +748,14 @@ open Prod
 private def key_data_to_string (a : α) (b : β a) (first : Bool) : String :=
   (if first then "" else ", ") ++ s! "{a } ← {b}"
 
-private def to_string (m : HashMap α β) : String :=
-  "⟨" ++ fst (fold m ("", true) fun p a b => (fst p ++ keyDataToString a b (snd p), false)) ++ "⟩"
+private def to_string (m : Std.HashMap α β) : String :=
+  "⟨" ++
+      fst
+        (Std.HashMap.fold m ("", true) fun p a b =>
+          (fst p ++ keyDataToString a b (snd p), false)) ++
+    "⟩"
 
-instance : ToString (HashMap α β) :=
+instance : ToString (Std.HashMap α β) :=
   ⟨toString⟩
 
 end String
@@ -754,23 +770,23 @@ private unsafe def format_key_data (a : α) (b : β a) (first : Bool) : format :
   (if first then to_fmt "" else to_fmt "," ++ line) ++ to_fmt a ++ space ++ to_fmt "←" ++ space ++
     to_fmt b
 
-private unsafe def to_format (m : HashMap α β) : format :=
+private unsafe def to_format (m : Std.HashMap α β) : format :=
   Group <|
     to_fmt "⟨" ++
         nest 1
           (fst
-            (fold m (to_fmt "", true) fun p a b =>
+            (Std.HashMap.fold m (to_fmt "", true) fun p a b =>
               (fst p ++ format_key_data a b (snd p), false))) ++
       to_fmt "⟩"
 
-unsafe instance : has_to_format (HashMap α β) :=
+unsafe instance : has_to_format (Std.HashMap α β) :=
   ⟨to_format⟩
 
 end Format
 
 /-- `hash_map` with key type `nat` and value type that may vary. -/
-instance {β : ℕ → Type _} : Inhabited (HashMap ℕ β) :=
+instance {β : ℕ → Type _} : Inhabited (Std.HashMap ℕ β) :=
   ⟨mkHashMap id⟩
 
-end HashMap
+end Std.HashMap

2fe465de

bump to nightly-2023-07-16-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/2fe465deb81bcd7ccafa065bb686888a82f15372

bb547586

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.hash_map
-! leanprover-community/mathlib commit f0c8bf9245297a541f468be517f1bde6195105e9
+! leanprover-community/mathlib commit 2fe465deb81bcd7ccafa065bb686888a82f15372
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -17,6 +17,9 @@ import Mathbin.Data.Pnat.Defs
 /-!
 # Hash maps
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 Defines a hash map data structure, representing a finite key-value map
 with a value type that may depend on the key type.  The structure
 requires a `nat`-valued hash function to associate keys to buckets.

f0c8bf92

bump to nightly-2023-06-13-21

mathlib commit https://github.com/leanprover-community/mathlib/commit/9fb8964792b4237dac6200193a0d533f1b3f7423

829520ac

Diff

@@ -261,7 +261,6 @@ section
 parameter {n : ℕ+} {bkts : BucketArray α β n} {bidx : Fin n} {f : List (Σ a, β a) → List (Σ a, β a)}
   (u v1 v2 w : List (Σ a, β a))
 
--- mathport name: exprL
 local notation "L" => Array'.read bkts bidx
 
 private def bkts' : BucketArray α β n :=
@@ -269,8 +268,6 @@ private def bkts' : BucketArray α β n :=
 
 variable (hl : L = u ++ v1 ++ w) (hfl : f L = u ++ v2 ++ w)
 
-include hl hfl
-
 theorem append_of_modify : ∃ u' w', bkts.asList = u' ++ v1 ++ w' ∧ bkts'.asList = u' ++ v2 ++ w' :=
   by
   unfold BucketArray.asList
@@ -293,8 +290,6 @@ variable (hvnd : (v2.map Sigma.fst).Nodup)
   (djuv : (u.map Sigma.fst).Disjoint (v2.map Sigma.fst))
   (djwv : (w.map Sigma.fst).Disjoint (v2.map Sigma.fst))
 
-include hvnd hal djuv djwv
-
 theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
     v1.length ≤ sz + v2.length ∧ valid bkts' (sz + v2.length - v1.length) :=
   by

f0c8bf92

bump to nightly-2023-06-04-18

mathlib commit https://github.com/leanprover-community/mathlib/commit/5f25c089cb34db4db112556f23c50d12da81b297

3fb4268b

Diff

@@ -76,7 +76,7 @@ namespace BucketArray
 
 section
 
-parameter {α : Type u}{β : α → Type v}(hash_fn : α → Nat)
+parameter {α : Type u} {β : α → Type v} (hash_fn : α → Nat)
 
 variable {n : ℕ+} (data : BucketArray α β n)
 
@@ -133,7 +133,7 @@ namespace HashMap
 
 section
 
-parameter {α : Type u}{β : α → Type v}(hash_fn : α → Nat)
+parameter {α : Type u} {β : α → Type v} (hash_fn : α → Nat)
 
 /-- Insert the pair `⟨a, b⟩` into the correct location in the bucket array
   (without checking for duplication) -/
@@ -258,11 +258,8 @@ theorem Valid.containsAux_iff {n} {bkts : BucketArray α β n} {sz : Nat} (v : v
 
 section
 
-parameter
-  {n :
-    ℕ+}{bkts :
-    BucketArray α β
-      n}{bidx : Fin n}{f : List (Σ a, β a) → List (Σ a, β a)}(u v1 v2 w : List (Σ a, β a))
+parameter {n : ℕ+} {bkts : BucketArray α β n} {bidx : Fin n} {f : List (Σ a, β a) → List (Σ a, β a)}
+  (u v1 v2 w : List (Σ a, β a))
 
 -- mathport name: exprL
 local notation "L" => Array'.read bkts bidx

f0c8bf92

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -64,7 +64,7 @@ universe u v w
 /-- `bucket_array α β` is the underlying data type for `hash_map α β`,
   an array of linked lists of key-value pairs. -/
 def BucketArray (α : Type u) (β : α → Type v) (n : ℕ+) :=
-  Array' n (List (Σa, β a))
+  Array' n (List (Σ a, β a))
 #align bucket_array BucketArray
 
 /-- Make a hash_map index from a `nat` hash value and a (positive) buffer size -/
@@ -84,32 +84,32 @@ instance : Inhabited (BucketArray α β n) :=
   ⟨mkArray' _ []⟩
 
 /-- Read the bucket corresponding to an element -/
-def read (a : α) : List (Σa, β a) :=
+def read (a : α) : List (Σ a, β a) :=
   let bidx := HashMap.mkIdx n (hash_fn a)
   data.read bidx
 #align bucket_array.read BucketArray.read
 
 /-- Write the bucket corresponding to an element -/
-def write (a : α) (l : List (Σa, β a)) : BucketArray α β n :=
+def write (a : α) (l : List (Σ a, β a)) : BucketArray α β n :=
   let bidx := HashMap.mkIdx n (hash_fn a)
   data.write bidx l
 #align bucket_array.write BucketArray.write
 
 /-- Modify (read, apply `f`, and write) the bucket corresponding to an element -/
-def modify (a : α) (f : List (Σa, β a) → List (Σa, β a)) : BucketArray α β n :=
+def modify (a : α) (f : List (Σ a, β a) → List (Σ a, β a)) : BucketArray α β n :=
   let bidx := HashMap.mkIdx n (hash_fn a)
   Array'.write data bidx (f (Array'.read data bidx))
 #align bucket_array.modify BucketArray.modify
 
 /-- The list of all key-value pairs in the bucket list -/
-def asList : List (Σa, β a) :=
+def asList : List (Σ a, β a) :=
   data.toList.join
 #align bucket_array.as_list BucketArray.asList
 
-theorem mem_asList {a : Σa, β a} : a ∈ data.asList ↔ ∃ i, a ∈ Array'.read data i :=
+theorem mem_asList {a : Σ a, β a} : a ∈ data.asList ↔ ∃ i, a ∈ Array'.read data i :=
   by
   have :
-    (∃ (l : List (Σa : α, β a))(i : Fin n.val), a ∈ l ∧ Array'.read data i = l) ↔
+    (∃ (l : List (Σ a : α, β a)) (i : Fin n.val), a ∈ l ∧ Array'.read data i = l) ↔
       ∃ i : Fin n.val, a ∈ Array'.read data i :=
     by rw [exists_swap] <;> exact exists_congr fun i => by simp
   simp [as_list] <;> simpa [Array'.Mem.def, and_comm']
@@ -150,13 +150,13 @@ theorem mk_asList (n : ℕ+) : BucketArray.asList (mkArray' n [] : BucketArray 
 parameter [DecidableEq α]
 
 /-- Search a bucket for a key `a` and return the value -/
-def findAux (a : α) : List (Σa, β a) → Option (β a)
+def findAux (a : α) : List (Σ a, β a) → Option (β a)
   | [] => none
   | ⟨a', b⟩ :: t => if h : a' = a then some (Eq.recOn h b) else find_aux t
 #align hash_map.find_aux HashMap.findAux
 
 theorem findAux_iff {a : α} {b : β a} :
-    ∀ {l : List (Σa, β a)}, (l.map Sigma.fst).Nodup → (find_aux a l = some b ↔ Sigma.mk a b ∈ l)
+    ∀ {l : List (Σ a, β a)}, (l.map Sigma.fst).Nodup → (find_aux a l = some b ↔ Sigma.mk a b ∈ l)
   | [], nd => ⟨fun n => by injection n, False.elim⟩
   | ⟨a', b'⟩ :: t, nd => by
     by_cases a' = a
@@ -166,21 +166,21 @@ theorem findAux_iff {a : α} {b : β a} :
       have : a' ∉ t.map Sigma.fst := nd.not_mem
       exact this.elim (List.mem_map_of_mem Sigma.fst m)
     · have : Sigma.mk a b ≠ ⟨a', b'⟩ := by intro e; injection e with e; exact h e.symm
-      simp at nd; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
+      simp at nd ; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
 #align hash_map.find_aux_iff HashMap.findAux_iff
 
 /-- Returns `tt` if the bucket `l` contains the key `a` -/
-def containsAux (a : α) (l : List (Σa, β a)) : Bool :=
+def containsAux (a : α) (l : List (Σ a, β a)) : Bool :=
   (find_aux a l).isSome
 #align hash_map.contains_aux HashMap.containsAux
 
-theorem containsAux_iff {a : α} {l : List (Σa, β a)} (nd : (l.map Sigma.fst).Nodup) :
+theorem containsAux_iff {a : α} {l : List (Σ a, β a)} (nd : (l.map Sigma.fst).Nodup) :
     contains_aux a l ↔ a ∈ l.map Sigma.fst :=
   by
   unfold contains_aux
   cases' h : find_aux a l with b <;> simp
-  · intro (b : β a)(m : Sigma.mk a b ∈ l)
-    rw [(find_aux_iff nd).2 m] at h
+  · intro (b : β a) (m : Sigma.mk a b ∈ l)
+    rw [(find_aux_iff nd).2 m] at h 
     contradiction
   · show ∃ b : β a, Sigma.mk a b ∈ l
     exact ⟨_, (find_aux_iff nd).1 h⟩
@@ -188,13 +188,13 @@ theorem containsAux_iff {a : α} {l : List (Σa, β a)} (nd : (l.map Sigma.fst).
 
 /-- Modify a bucket to replace a value in the list. Leaves the list
  unchanged if the key is not found. -/
-def replaceAux (a : α) (b : β a) : List (Σa, β a) → List (Σa, β a)
+def replaceAux (a : α) (b : β a) : List (Σ a, β a) → List (Σ a, β a)
   | [] => []
   | ⟨a', b'⟩ :: t => if a' = a then ⟨a, b⟩ :: t else ⟨a', b'⟩ :: replace_aux t
 #align hash_map.replace_aux HashMap.replaceAux
 
 /-- Modify a bucket to remove a key, if it exists. -/
-def eraseAux (a : α) : List (Σa, β a) → List (Σa, β a)
+def eraseAux (a : α) : List (Σ a, β a) → List (Σ a, β a)
   | [] => []
   | ⟨a', b'⟩ :: t => if a' = a then t else ⟨a', b'⟩ :: erase_aux t
 #align hash_map.erase_aux HashMap.eraseAux
@@ -205,7 +205,7 @@ def eraseAux (a : α) : List (Σa, β a) → List (Σa, β a)
   multiple times in the list. -/
 structure Valid {n} (bkts : BucketArray α β n) (sz : Nat) : Prop where
   len : bkts.asList.length = sz
-  idx : ∀ {i} {a : Σa, β a}, a ∈ Array'.read bkts i → mkIdx n (hash_fn a.1) = i
+  idx : ∀ {i} {a : Σ a, β a}, a ∈ Array'.read bkts i → mkIdx n (hash_fn a.1) = i
   Nodup : ∀ i, ((Array'.read bkts i).map Sigma.fst).Nodup
 #align hash_map.valid HashMap.Valid
 
@@ -262,7 +262,7 @@ parameter
   {n :
     ℕ+}{bkts :
     BucketArray α β
-      n}{bidx : Fin n}{f : List (Σa, β a) → List (Σa, β a)}(u v1 v2 w : List (Σa, β a))
+      n}{bidx : Fin n}{f : List (Σ a, β a) → List (Σ a, β a)}(u v1 v2 w : List (Σ a, β a))
 
 -- mathport name: exprL
 local notation "L" => Array'.read bkts bidx
@@ -292,7 +292,7 @@ theorem append_of_modify : ∃ u' w', bkts.asList = u' ++ v1 ++ w' ∧ bkts'.asL
 #align hash_map.append_of_modify HashMap.append_of_modify
 
 variable (hvnd : (v2.map Sigma.fst).Nodup)
-  (hal : ∀ a : Σa, β a, a ∈ v2 → mkIdx n (hash_fn a.1) = bidx)
+  (hal : ∀ a : Σ a, β a, a ∈ v2 → mkIdx n (hash_fn a.1) = bidx)
   (djuv : (u.map Sigma.fst).Disjoint (v2.map Sigma.fst))
   (djwv : (w.map Sigma.fst).Disjoint (v2.map Sigma.fst))
 
@@ -309,13 +309,13 @@ theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
   · by_cases bidx = i
     · subst i; rw [bkts', Array'.read_write, hfl]
       have := @valid.idx _ _ _ v bidx a
-      simp only [hl, List.mem_append, or_imp] at this⊢
+      simp only [hl, List.mem_append, or_imp] at this ⊢
       exact ⟨⟨this.1.1, hal _⟩, this.2⟩
     · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.idx
   · by_cases bidx = i
     · subst i; rw [bkts', Array'.read_write, hfl]
       have := @valid.nodup _ _ _ v bidx
-      simp [hl, List.nodup_append] at this
+      simp [hl, List.nodup_append] at this 
       simp [List.nodup_append, this, hvnd, djuv, djwv.symm]
     · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.nodup
 #align hash_map.valid.modify HashMap.Valid.modify
@@ -323,30 +323,30 @@ theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
 end
 
 theorem Valid.replaceAux (a : α) (b : β a) :
-    ∀ l : List (Σa, β a),
+    ∀ l : List (Σ a, β a),
       a ∈ l.map Sigma.fst →
-        ∃ (u w : List (Σa, β a))(b' : _),
+        ∃ (u w : List (Σ a, β a)) (b' : _),
           l = u ++ [⟨a, b'⟩] ++ w ∧ replace_aux a b l = u ++ [⟨a, b⟩] ++ w
   | [] => False.elim
   | ⟨a', b'⟩ :: t => by
     by_cases e : a' = a
     · subst a'
       suffices
-        ∃ (u w : List (Σa, β a))(b'' : β a),
+        ∃ (u w : List (Σ a, β a)) (b'' : β a),
           Sigma.mk a b' :: t = u ++ ⟨a, b''⟩ :: w ∧
             replace_aux a b (⟨a, b'⟩ :: t) = u ++ ⟨a, b⟩ :: w
         by simpa
       refine' ⟨[], t, b', _⟩; simp [replace_aux]
     · suffices
         ∀ (x : β a) (_ : Sigma.mk a x ∈ t),
-          ∃ (u w : _)(b'' : β a),
+          ∃ (u w : _) (b'' : β a),
             Sigma.mk a' b' :: t = u ++ ⟨a, b''⟩ :: w ∧
               Sigma.mk a' b' :: replace_aux a b t = u ++ ⟨a, b⟩ :: w
         by simpa [replace_aux, Ne.symm e, e]
       intro x m
       have IH :
         ∀ (x : β a) (_ : Sigma.mk a x ∈ t),
-          ∃ (u w : _)(b'' : β a), t = u ++ ⟨a, b''⟩ :: w ∧ replace_aux a b t = u ++ ⟨a, b⟩ :: w :=
+          ∃ (u w : _) (b'' : β a), t = u ++ ⟨a, b''⟩ :: w ∧ replace_aux a b t = u ++ ⟨a, b⟩ :: w :=
         by simpa using valid.replace_aux t
       rcases IH x m with ⟨u, w, b'', hl, hfl⟩
       exact ⟨⟨a', b'⟩ :: u, w, b'', by simp [hl, hfl.symm, Ne.symm e]⟩
@@ -360,11 +360,11 @@ theorem Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α
   rcases HashMap.Valid.replaceAux a b (Array'.read bkts (mk_idx n (hash_fn a)))
       ((contains_aux_iff nd).1 Hc) with
     ⟨u, w, b', hl, hfl⟩
-  simp [hl, List.nodup_append] at nd
+  simp [hl, List.nodup_append] at nd 
   refine'
       (v.modify hash_fn u [⟨a, b'⟩] [⟨a, b⟩] w hl hfl (List.nodup_singleton _)
-          (fun a' e => by simp at e <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
-    · revert e1; simp [-Sigma.exists] at e2; subst a'; simp [nd]
+          (fun a' e => by simp at e  <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
+    · revert e1; simp [-Sigma.exists] at e2 ; subst a'; simp [nd]
 #align hash_map.valid.replace HashMap.Valid.replace
 
 theorem Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
@@ -374,32 +374,32 @@ theorem Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α)
   have nd := v.nodup (mk_idx n (hash_fn a))
   refine'
     (v.modify hash_fn [] [] [⟨a, b⟩] (bkts.read hash_fn a) rfl rfl (List.nodup_singleton _)
-        (fun a' e => by simp at e <;> rw [e]) (fun a' => False.elim) fun a' e1 e2 => _).2
-  simp [-Sigma.exists] at e2; subst a'
+        (fun a' e => by simp at e  <;> rw [e]) (fun a' => False.elim) fun a' e1 e2 => _).2
+  simp [-Sigma.exists] at e2 ; subst a'
   exact Hnc ((contains_aux_iff nd).2 e1)
 #align hash_map.valid.insert HashMap.Valid.insert
 
 theorem Valid.eraseAux (a : α) :
-    ∀ l : List (Σa, β a),
+    ∀ l : List (Σ a, β a),
       a ∈ l.map Sigma.fst →
-        ∃ (u w : List (Σa, β a))(b : _), l = u ++ [⟨a, b⟩] ++ w ∧ erase_aux a l = u ++ [] ++ w
+        ∃ (u w : List (Σ a, β a)) (b : _), l = u ++ [⟨a, b⟩] ++ w ∧ erase_aux a l = u ++ [] ++ w
   | [] => False.elim
   | ⟨a', b'⟩ :: t => by
     by_cases e : a' = a
     · subst a'
       simpa [erase_aux, and_comm'] using
-        show ∃ (u w : _)(x : β a), t = u ++ w ∧ Sigma.mk a b' :: t = u ++ ⟨a, x⟩ :: w from
+        show ∃ (u w : _) (x : β a), t = u ++ w ∧ Sigma.mk a b' :: t = u ++ ⟨a, x⟩ :: w from
           ⟨[], t, b', by simp⟩
     · simp [erase_aux, e, Ne.symm e]
       suffices
         ∀ (b : β a) (_ : Sigma.mk a b ∈ t),
-          ∃ (u w : _)(x : β a),
+          ∃ (u w : _) (x : β a),
             Sigma.mk a' b' :: t = u ++ ⟨a, x⟩ :: w ∧ Sigma.mk a' b' :: erase_aux a t = u ++ w
         by simpa [replace_aux, Ne.symm e, e]
       intro b m
       have IH :
         ∀ (x : β a) (_ : Sigma.mk a x ∈ t),
-          ∃ (u w : _)(x : β a), t = u ++ ⟨a, x⟩ :: w ∧ erase_aux a t = u ++ w :=
+          ∃ (u w : _) (x : β a), t = u ++ ⟨a, x⟩ :: w ∧ erase_aux a t = u ++ w :=
         by simpa using valid.erase_aux t
       rcases IH b m with ⟨u, w, b'', hl, hfl⟩
       exact ⟨⟨a', b'⟩ :: u, w, b'', by simp [hl, hfl.symm]⟩
@@ -465,7 +465,7 @@ def fold {δ : Type w} (m : HashMap α β) (d : δ) (f : δ → ∀ a, β a →
 #align hash_map.fold HashMap.fold
 
 /-- The list of key-value pairs in the map -/
-def entries (m : HashMap α β) : List (Σa, β a) :=
+def entries (m : HashMap α β) : List (Σ a, β a) :=
   m.buckets.asList
 #align hash_map.entries HashMap.entries
 
@@ -492,8 +492,8 @@ theorem keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).k
 #align hash_map.keys_empty HashMap.keys_empty
 
 theorem find_empty (hash_fn : α → Nat) (n a) : (@mkHashMap α _ β hash_fn n).find a = none := by
-  induction' h : (@mkHashMap α _ β hash_fn n).find a with <;>
-    [rfl;· have := (find_iff _ _ _).1 h; rw [entries_empty] at this; contradiction]
+  induction' h : (@mkHashMap α _ β hash_fn n).find a with <;> [rfl;
+    · have := (find_iff _ _ _).1 h; rw [entries_empty] at this ; contradiction]
 #align hash_map.find_empty HashMap.find_empty
 
 theorem not_contains_empty (hash_fn : α → Nat) (n a) : ¬(@mkHashMap α _ β hash_fn n).contains a :=
@@ -505,14 +505,14 @@ theorem insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n}
     Valid hash_fn (bkts.foldl (mkArray' _ [] : BucketArray α β n') (reinsertAux hash_fn)) sz :=
   by
   suffices
-    ∀ (l : List (Σa, β a)) (t : BucketArray α β n') (sz),
+    ∀ (l : List (Σ a, β a)) (t : BucketArray α β n') (sz),
       valid hash_fn t sz →
         ((l ++ t.asList).map Sigma.fst).Nodup →
-          valid hash_fn (l.foldl (fun r (a : Σa, β a) => reinsert_aux hash_fn r a.1 a.2) t)
+          valid hash_fn (l.foldl (fun r (a : Σ a, β a) => reinsert_aux hash_fn r a.1 a.2) t)
             (sz + l.length)
     by
     have p := this bkts.as_list _ _ (mk_valid _ _)
-    rw [mk_as_list, List.append_nil, zero_add, v.len] at p
+    rw [mk_as_list, List.append_nil, zero_add, v.len] at p 
     rw [BucketArray.foldl_eq]
     exact p (v.as_list_nodup _)
   intro l; induction' l with c l IH <;> intro t sz v nd; · exact v
@@ -602,9 +602,9 @@ theorem mem_insert :
         refine' or_iff_left_of_imp (Not.elim <| not_or.2 _)
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩)
         · have na := (not_congr <| v.contains_aux_iff _ _).1 Hnc
-          simp [hl, not_or] at na; simp [na]
+          simp [hl, not_or] at na ; simp [na]
         · have nd' := v.as_list_nodup _
-          simp [hl, List.nodup_append] at nd'; simp [nd']
+          simp [hl, List.nodup_append] at nd' ; simp [nd']
       · suffices Sigma.mk a' b' ∉ v1 by simp [h, Ne.symm h, this]
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩) <;> simp [Ne.symm h]
     by_cases Hc : (contains_aux a bkt : Prop)
@@ -647,7 +647,7 @@ theorem find_insert_ne (m : HashMap α β) (a a' : α) (b : β a) (h : a ≠ a')
     (m.insert a b).find a' = m.find a' :=
   Option.eq_of_eq_some fun b' =>
     let t := mem_insert m a b a' b'
-    (find_iff _ _ _).trans <| Iff.trans (by rwa [if_neg h] at t) (find_iff _ _ _).symm
+    (find_iff _ _ _).trans <| Iff.trans (by rwa [if_neg h] at t ) (find_iff _ _ _).symm
 #align hash_map.find_insert_ne HashMap.find_insert_ne
 
 theorem find_insert (m : HashMap α β) (a' a : α) (b : β a) :
@@ -661,12 +661,12 @@ theorem find_insert (m : HashMap α β) (a' a : α) (b : β a) :
 #align hash_map.find_insert HashMap.find_insert
 
 /-- Insert a list of key-value pairs into the map. (Modifies `m` in-place when applicable) -/
-def insertAll (l : List (Σa, β a)) (m : HashMap α β) : HashMap α β :=
+def insertAll (l : List (Σ a, β a)) (m : HashMap α β) : HashMap α β :=
   l.foldl (fun m ⟨a, b⟩ => insert m a b) m
 #align hash_map.insert_all HashMap.insertAll
 
 /-- Construct a hash map from a list of key-value pairs. -/
-def ofList (l : List (Σa, β a)) (hash_fn) : HashMap α β :=
+def ofList (l : List (Σ a, β a)) (hash_fn) : HashMap α β :=
   insertAll l (mkHashMap hash_fn (2 * l.length))
 #align hash_map.of_list HashMap.ofList
 
@@ -706,7 +706,7 @@ theorem mem_erase :
           or_left_comm]
       rintro m rfl; revert m; apply not_or.2
       have nd' := v.as_list_nodup _
-      simp [hl, List.nodup_append] at nd'; simp [nd']
+      simp [hl, List.nodup_append] at nd' ; simp [nd']
     · suffices ∀ _ : Sigma.mk a' b' ∈ BucketArray.asList bkts, a ≠ a' by
         simp [erase, @dif_neg (contains_aux a bkt) _ Hc, entries, and_iff_right_of_imp this]
       rintro m rfl

f0c8bf92

bump to nightly-2023-05-28-04

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6797a637

Diff

@@ -160,18 +160,13 @@ theorem findAux_iff {a : α} {b : β a} :
   | [], nd => ⟨fun n => by injection n, False.elim⟩
   | ⟨a', b'⟩ :: t, nd => by
     by_cases a' = a
-    · clear find_aux_iff
-      subst h
+    · clear find_aux_iff; subst h
       suffices b' = b ↔ b' = b ∨ Sigma.mk a' b ∈ t by simpa [find_aux, eq_comm]
       refine' (or_iff_left_of_imp fun m => _).symm
       have : a' ∉ t.map Sigma.fst := nd.not_mem
       exact this.elim (List.mem_map_of_mem Sigma.fst m)
-    · have : Sigma.mk a b ≠ ⟨a', b'⟩ := by
-        intro e
-        injection e with e
-        exact h e.symm
-      simp at nd
-      simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
+    · have : Sigma.mk a b ≠ ⟨a', b'⟩ := by intro e; injection e with e; exact h e.symm
+      simp at nd; simp [find_aux, h, Ne.symm h, find_aux_iff, nd]
 #align hash_map.find_aux_iff HashMap.findAux_iff
 
 /-- Returns `tt` if the bucket `l` contains the key `a` -/
@@ -240,14 +235,10 @@ theorem Valid.asList_nodup {n} {bkts : BucketArray α β n} {sz : Nat} (v : vali
   rw [← List.enum_map_snd bkts.to_list, List.pairwise_map', List.pairwise_map']
   have : (bkts.to_list.enum.map Prod.fst).Nodup := by simp [List.nodup_range]
   refine' List.Pairwise.imp_of_mem _ ((List.pairwise_map' _).1 this)
-  rw [Prod.forall]
-  intro i l₁
-  rw [Prod.forall]
-  intro j l₂ me₁ me₂ ij
-  simp [List.Disjoint]
-  intro a b ml₁ b' ml₂
-  apply ij
-  rwa [← v.idx_enum_1 _ me₁ ml₁, ← v.idx_enum_1 _ me₂ ml₂]
+  rw [Prod.forall]; intro i l₁
+  rw [Prod.forall]; intro j l₂ me₁ me₂ ij
+  simp [List.Disjoint]; intro a b ml₁ b' ml₂
+  apply ij; rwa [← v.idx_enum_1 _ me₁ ml₁, ← v.idx_enum_1 _ me₂ ml₂]
 #align hash_map.valid.as_list_nodup HashMap.Valid.asList_nodup
 
 theorem mk_valid (n : ℕ+) : @valid n (mkArray' n []) 0 :=
@@ -316,21 +307,17 @@ theorem Valid.modify {sz : ℕ} (v : valid bkts sz) :
     simpa [GE.ge, add_comm, add_left_comm, Nat.le_add_right, add_tsub_cancel_left]
   refine' ⟨congr_arg _ e₂, fun i a => _, fun i => _⟩
   · by_cases bidx = i
-    · subst i
-      rw [bkts', Array'.read_write, hfl]
+    · subst i; rw [bkts', Array'.read_write, hfl]
       have := @valid.idx _ _ _ v bidx a
       simp only [hl, List.mem_append, or_imp] at this⊢
       exact ⟨⟨this.1.1, hal _⟩, this.2⟩
-    · rw [bkts', Array'.read_write_of_ne _ _ h]
-      apply v.idx
+    · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.idx
   · by_cases bidx = i
-    · subst i
-      rw [bkts', Array'.read_write, hfl]
+    · subst i; rw [bkts', Array'.read_write, hfl]
       have := @valid.nodup _ _ _ v bidx
       simp [hl, List.nodup_append] at this
       simp [List.nodup_append, this, hvnd, djuv, djwv.symm]
-    · rw [bkts', Array'.read_write_of_ne _ _ h]
-      apply v.nodup
+    · rw [bkts', Array'.read_write_of_ne _ _ h]; apply v.nodup
 #align hash_map.valid.modify HashMap.Valid.modify
 
 end
@@ -349,8 +336,7 @@ theorem Valid.replaceAux (a : α) (b : β a) :
           Sigma.mk a b' :: t = u ++ ⟨a, b''⟩ :: w ∧
             replace_aux a b (⟨a, b'⟩ :: t) = u ++ ⟨a, b⟩ :: w
         by simpa
-      refine' ⟨[], t, b', _⟩
-      simp [replace_aux]
+      refine' ⟨[], t, b', _⟩; simp [replace_aux]
     · suffices
         ∀ (x : β a) (_ : Sigma.mk a x ∈ t),
           ∃ (u w : _)(b'' : β a),
@@ -378,10 +364,7 @@ theorem Valid.replace {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α
   refine'
       (v.modify hash_fn u [⟨a, b'⟩] [⟨a, b⟩] w hl hfl (List.nodup_singleton _)
           (fun a' e => by simp at e <;> rw [e]) (fun a' e1 e2 => _) fun a' e1 e2 => _).2 <;>
-    · revert e1
-      simp [-Sigma.exists] at e2
-      subst a'
-      simp [nd]
+    · revert e1; simp [-Sigma.exists] at e2; subst a'; simp [nd]
 #align hash_map.valid.replace HashMap.Valid.replace
 
 theorem Valid.insert {n : ℕ+} {bkts : BucketArray α β n} {sz : ℕ} (a : α) (b : β a)
@@ -510,10 +493,7 @@ theorem keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).k
 
 theorem find_empty (hash_fn : α → Nat) (n a) : (@mkHashMap α _ β hash_fn n).find a = none := by
   induction' h : (@mkHashMap α _ β hash_fn n).find a with <;>
-    [rfl;·
-      have := (find_iff _ _ _).1 h
-      rw [entries_empty] at this
-      contradiction]
+    [rfl;· have := (find_iff _ _ _).1 h; rw [entries_empty] at this; contradiction]
 #align hash_map.find_empty HashMap.find_empty
 
 theorem not_contains_empty (hash_fn : α → Nat) (n a) : ¬(@mkHashMap α _ β hash_fn n).contains a :=
@@ -535,9 +515,7 @@ theorem insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n}
     rw [mk_as_list, List.append_nil, zero_add, v.len] at p
     rw [BucketArray.foldl_eq]
     exact p (v.as_list_nodup _)
-  intro l
-  induction' l with c l IH <;> intro t sz v nd
-  · exact v
+  intro l; induction' l with c l IH <;> intro t sz v nd; · exact v
   rw [show sz + (c :: l).length = sz + 1 + l.length by simp [add_comm, add_assoc]]
   rcases show
       (l.map Sigma.fst).Nodup ∧
@@ -564,8 +542,7 @@ theorem insert_lemma (hash_fn : α → Nat) {n n'} {bkts : BucketArray α β n}
   · subst h
     have e : Sigma.mk a b' = ⟨c.1, c.2⟩ := by
       simpa [reinsert_aux, BucketArray.modify, Array'.read_write, this] using im
-    injection e with e
-    subst a
+    injection e with e; subst a
     exact nm1.elim (@List.mem_map_of_mem _ _ Sigma.fst _ _ m1)
   · apply this
     simpa [reinsert_aux, BucketArray.modify, Array'.read_write_of_ne _ _ h] using im
@@ -625,11 +602,9 @@ theorem mem_insert :
         refine' or_iff_left_of_imp (Not.elim <| not_or.2 _)
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩)
         · have na := (not_congr <| v.contains_aux_iff _ _).1 Hnc
-          simp [hl, not_or] at na
-          simp [na]
+          simp [hl, not_or] at na; simp [na]
         · have nd' := v.as_list_nodup _
-          simp [hl, List.nodup_append] at nd'
-          simp [nd']
+          simp [hl, List.nodup_append] at nd'; simp [nd']
       · suffices Sigma.mk a' b' ∉ v1 by simp [h, Ne.symm h, this]
         rcases veq with (⟨rfl, Hnc⟩ | ⟨b'', rfl⟩) <;> simp [Ne.symm h]
     by_cases Hc : (contains_aux a bkt : Prop)
@@ -729,12 +704,9 @@ theorem mem_erase :
           by simp [eq_comm, not_and_self_iff, and_iff_right_of_imp this]
         simpa [hl, show bkts'.as_list = _ from hfl, and_or_left, and_comm', and_left_comm,
           or_left_comm]
-      rintro m rfl
-      revert m
-      apply not_or.2
+      rintro m rfl; revert m; apply not_or.2
       have nd' := v.as_list_nodup _
-      simp [hl, List.nodup_append] at nd'
-      simp [nd']
+      simp [hl, List.nodup_append] at nd'; simp [nd']
     · suffices ∀ _ : Sigma.mk a' b' ∈ BucketArray.asList bkts, a ≠ a' by
         simp [erase, @dif_neg (contains_aux a bkt) _ Hc, entries, and_iff_right_of_imp this]
       rintro m rfl

f0c8bf92

bump to nightly-2023-05-28-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/917c3c072e487b3cccdbfeff17e75b40e45f66cb

6c6011cf

Diff

@@ -278,7 +278,6 @@ local notation "L" => Array'.read bkts bidx
 
 private def bkts' : BucketArray α β n :=
   Array'.write bkts bidx (f L)
-#align hash_map.bkts' hash_map.bkts'
 
 variable (hl : L = u ++ v1 ++ w) (hfl : f L = u ++ v2 ++ w)
 
@@ -769,11 +768,9 @@ open Prod
 
 private def key_data_to_string (a : α) (b : β a) (first : Bool) : String :=
   (if first then "" else ", ") ++ s! "{a } ← {b}"
-#align hash_map.key_data_to_string hash_map.key_data_to_string
 
 private def to_string (m : HashMap α β) : String :=
   "⟨" ++ fst (fold m ("", true) fun p a b => (fst p ++ keyDataToString a b (snd p), false)) ++ "⟩"
-#align hash_map.to_string hash_map.to_string
 
 instance : ToString (HashMap α β) :=
   ⟨toString⟩
@@ -789,7 +786,6 @@ variable [has_to_format α] [∀ a, has_to_format (β a)]
 private unsafe def format_key_data (a : α) (b : β a) (first : Bool) : format :=
   (if first then to_fmt "" else to_fmt "," ++ line) ++ to_fmt a ++ space ++ to_fmt "←" ++ space ++
     to_fmt b
-#align hash_map.format_key_data hash_map.format_key_data
 
 private unsafe def to_format (m : HashMap α β) : format :=
   Group <|
@@ -799,7 +795,6 @@ private unsafe def to_format (m : HashMap α β) : format :=
             (fold m (to_fmt "", true) fun p a b =>
               (fst p ++ format_key_data a b (snd p), false))) ++
       to_fmt "⟩"
-#align hash_map.to_format hash_map.to_format
 
 unsafe instance : has_to_format (HashMap α β) :=
   ⟨to_format⟩

f0c8bf92

bump to nightly-2023-05-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/8d33f09cd7089ecf074b4791907588245aec5d1b

fbc7b476

Diff

@@ -510,8 +510,9 @@ theorem keys_empty (hash_fn : α → Nat) (n) : (@mkHashMap α _ β hash_fn n).k
 #align hash_map.keys_empty HashMap.keys_empty
 
 theorem find_empty (hash_fn : α → Nat) (n a) : (@mkHashMap α _ β hash_fn n).find a = none := by
-  induction' h : (@mkHashMap α _ β hash_fn n).find a with <;> [rfl,
-    · have := (find_iff _ _ _).1 h
+  induction' h : (@mkHashMap α _ β hash_fn n).find a with <;>
+    [rfl;·
+      have := (find_iff _ _ _).1 h
       rw [entries_empty] at this
       contradiction]
 #align hash_map.find_empty HashMap.find_empty

f0c8bf92

bump to nightly-2023-05-05-03

mathlib commit https://github.com/leanprover-community/mathlib/commit/738054fa93d43512da144ec45ce799d18fd44248

c17f6f14

Diff

@@ -4,13 +4,14 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Leonardo de Moura, Mario Carneiro
 
 ! This file was ported from Lean 3 source module data.hash_map
-! leanprover-community/mathlib commit 4fcbc82dc2257986c03e113f87bc5ce021243a44
+! leanprover-community/mathlib commit f0c8bf9245297a541f468be517f1bde6195105e9
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
 import Mathbin.Data.Array.Lemmas
 import Mathbin.Data.List.Join
 import Mathbin.Data.List.Range
+import Mathbin.Data.List.Nodup
 import Mathbin.Data.Pnat.Defs
 
 /-!

4fcbc82d

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

f0c8bf92

chore: reduce imports (#9830)

This uses the improved shake script from #9772 to reduce imports across mathlib. The corresponding noshake.json file has been added to #9772.

Co-authored-by: Mario Carneiro <di.gama@gmail.com>

f4c4ca61

Diff

@@ -7,9 +7,9 @@ As `HashMap` has been completely reimplemented in `Std`,
 nothing from the mathlib3 file `data.hash_map` is reflected here.
 The porting header is just here to mark that no further work on `data.hash_map` is desired.
 -/
-import Mathlib.Init.Align
 import Std.Data.HashMap.Basic
 import Std.Data.RBMap.Basic
+import Mathlib.Mathport.Rename
 
 #align_import data.hash_map from "leanprover-community/mathlib"@"f0c8bf9245297a541f468be517f1bde6195105e9"

f0c8bf92

chore: fix imports (#8538)

f659b7bb

Diff

@@ -8,8 +8,8 @@ nothing from the mathlib3 file `data.hash_map` is reflected here.
 The porting header is just here to mark that no further work on `data.hash_map` is desired.
 -/
 import Mathlib.Init.Align
-import Std.Data.HashMap
-import Std.Data.RBMap
+import Std.Data.HashMap.Basic
+import Std.Data.RBMap.Basic
 
 #align_import data.hash_map from "leanprover-community/mathlib"@"f0c8bf9245297a541f468be517f1bde6195105e9"

f0c8bf92

fix: disable autoImplicit globally (#6528)

Autoimplicits are highly controversial and also defeat the performance-improving work in #6474.

The intent of this PR is to make autoImplicit opt-in on a per-file basis, by disabling it in the lakefile and enabling it again with set_option autoImplicit true in the few files that rely on it.

That also keeps this PR small, as opposed to attempting to "fix" files to not need it any more.

I claim that many of the uses of autoImplicit in these files are accidental; situations such as:

Assuming variables are in scope, but pasting the lemma in the wrong section
Pasting in a lemma from a scratch file without checking to see if the variable names are consistent with the rest of the file
Making a copy-paste error between lemmas and forgetting to add an explicit arguments.

Having set_option autoImplicit false as the default prevents these types of mistake being made in the 90% of files where autoImplicits are not used at all, and causes them to be caught by CI during review.

I think there were various points during the port where we encouraged porters to delete the universes u v lines; I think having autoparams for universe variables only would cover a lot of the cases we actually use them, while avoiding any real shortcomings.

A Zulip poll (after combining overlapping votes accordingly) was in favor of this change with 5:5:18 as the no:dontcare:yes vote ratio.

While this PR was being reviewed, a handful of files gained some more likely-accidental autoImplicits. In these places, set_option autoImplicit true has been placed locally within a section, rather than at the top of the file.

0c24f831

Diff

@@ -19,6 +19,8 @@ import Std.Data.RBMap
 These should be replaced by proper implementations in Std.
 -/
 
+set_option autoImplicit true
+
 namespace Std.HashMap
 
 -- not an exact match, the Lean3 version was dependently-typed

f0c8bf92

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -3,11 +3,6 @@ Copyright (c) 2022 Scott Morrison. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Scott Morrison
 
-! This file was ported from Lean 3 source module data.hash_map
-! leanprover-community/mathlib commit f0c8bf9245297a541f468be517f1bde6195105e9
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
-
 As `HashMap` has been completely reimplemented in `Std`,
 nothing from the mathlib3 file `data.hash_map` is reflected here.
 The porting header is just here to mark that no further work on `data.hash_map` is desired.
@@ -16,6 +11,8 @@ import Mathlib.Init.Align
 import Std.Data.HashMap
 import Std.Data.RBMap
 
+#align_import data.hash_map from "leanprover-community/mathlib"@"f0c8bf9245297a541f468be517f1bde6195105e9"
+
 /-!
 # Additional API for `HashMap` and `RBSet`.

f0c8bf92

chore: fix SHA in Data.HashMap (#5895)

This file was replaced, not ported: so the SHA is irrelevant anyway.

178de469

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Scott Morrison
 
 ! This file was ported from Lean 3 source module data.hash_map
-! leanprover-community/mathlib commit 2220b0cbab795e73674b8191170b0cc68c6b54a8
+! leanprover-community/mathlib commit f0c8bf9245297a541f468be517f1bde6195105e9
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.

2220b0cb

chore: add porting header to Mathlib.Data.HashMap (#5846)

Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com>

535aca50

Diff

@@ -2,7 +2,17 @@
 Copyright (c) 2022 Scott Morrison. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Scott Morrison
+
+! This file was ported from Lean 3 source module data.hash_map
+! leanprover-community/mathlib commit 2220b0cbab795e73674b8191170b0cc68c6b54a8
+! Please do not edit these lines, except to modify the commit id
+! if you have ported upstream changes.
+
+As `HashMap` has been completely reimplemented in `Std`,
+nothing from the mathlib3 file `data.hash_map` is reflected here.
+The porting header is just here to mark that no further work on `data.hash_map` is desired.
 -/
+import Mathlib.Init.Align
 import Std.Data.HashMap
 import Std.Data.RBMap
 
@@ -14,6 +24,9 @@ These should be replaced by proper implementations in Std.
 
 namespace Std.HashMap
 
+-- not an exact match, the Lean3 version was dependently-typed
+#align hash_map Std.HashMapₓ
+
 variable [BEq α] [Hashable α]
 
 /-- The list of keys in a `HashMap`. -/

`data.hash_map` ⟷ `Mathlib.Data.HashMap`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 124

data.hash_map ⟷ Mathlib.Data.HashMap

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

Dependencies 2 + 124

`data.hash_map` ⟷ `Mathlib.Data.HashMap`