blob: 1717c3d4d73817c8093a5760a2c93e4e24979366 [file]
/-
Copyright (c) 2016 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Leonardo de Moura, Mario Carneiro
-/
module
prelude
public import Init.Data.ByteArray.Basic
import Init.Data.Nat.Simproc
/-!
# Arithmetic of `String.Pos.Raw`
This file contains basic theory about which does not actually need to know anything about strings
and therefore does not depend on `Init.Data.String.Decode`.
-/
public section
namespace String
attribute [ext] String.Pos.Raw
instance : HSub String.Pos.Raw String String.Pos.Raw where
hSub p s := { byteIdx := p.byteIdx - s.utf8ByteSize }
instance : HSub String.Pos.Raw Char String.Pos.Raw where
hSub p c := { byteIdx := p.byteIdx - c.utf8Size }
@[export lean_string_pos_sub]
def Pos.Internal.subImpl : String.Pos.Raw → String.Pos.Raw → String.Pos.Raw :=
fun p₁ p₂ => ⟨p₁.byteIdx - p₂.byteIdx⟩
instance : HAdd String.Pos.Raw Char String.Pos.Raw where
hAdd p c := { byteIdx := p.byteIdx + c.utf8Size }
instance : HAdd Char String.Pos.Raw String.Pos.Raw where
hAdd c p := { byteIdx := c.utf8Size + p.byteIdx }
instance : HAdd String String.Pos.Raw String.Pos.Raw where
hAdd s p := { byteIdx := s.utf8ByteSize + p.byteIdx }
instance : HAdd String.Pos.Raw String String.Pos.Raw where
hAdd p s := { byteIdx := p.byteIdx + s.utf8ByteSize }
instance : LE String.Pos.Raw where
le p₁ p₂ := p₁.byteIdx ≤ p₂.byteIdx
instance : LT String.Pos.Raw where
lt p₁ p₂ := p₁.byteIdx < p₂.byteIdx
instance (p₁ p₂ : String.Pos.Raw) : Decidable (p₁ ≤ p₂) :=
inferInstanceAs (Decidable (p₁.byteIdx ≤ p₂.byteIdx))
instance (p₁ p₂ : String.Pos.Raw) : Decidable (p₁ < p₂) :=
inferInstanceAs (Decidable (p₁.byteIdx < p₂.byteIdx))
instance : Min String.Pos.Raw := minOfLe
instance : Max String.Pos.Raw := maxOfLe
@[simp]
theorem Pos.Raw.byteIdx_sub_char {p : Pos.Raw} {c : Char} : (p - c).byteIdx = p.byteIdx - c.utf8Size := rfl
@[simp]
theorem Pos.Raw.byteIdx_sub_string {p : Pos.Raw} {s : String} : (p - s).byteIdx = p.byteIdx - s.utf8ByteSize := rfl
@[simp]
theorem Pos.Raw.byteIdx_add_string {p : Pos.Raw} {s : String} : (p + s).byteIdx = p.byteIdx + s.utf8ByteSize := rfl
@[simp]
theorem Pos.Raw.byteIdx_string_add {s : String} {p : Pos.Raw} : (s + p).byteIdx = s.utf8ByteSize + p.byteIdx := rfl
@[simp]
theorem Pos.Raw.byteIdx_add_char {p : Pos.Raw} {c : Char} : (p + c).byteIdx = p.byteIdx + c.utf8Size := rfl
@[simp]
theorem Pos.Raw.byteIdx_char_add {c : Char} {p : Pos.Raw} : (c + p).byteIdx = c.utf8Size + p.byteIdx := rfl
theorem Pos.Raw.le_iff {i₁ i₂ : Pos.Raw} : i₁ ≤ i₂ ↔ i₁.byteIdx ≤ i₂.byteIdx := .rfl
theorem Pos.Raw.lt_iff {i₁ i₂ : Pos.Raw} : i₁ < i₂ ↔ i₁.byteIdx < i₂.byteIdx := .rfl
@[simp]
theorem Pos.Raw.byteIdx_zero : (0 : Pos.Raw).byteIdx = 0 := rfl
/--
Returns the size of the byte slice delineated by the positions `lo` and `hi`.
-/
@[expose, inline]
def Pos.Raw.byteDistance (lo hi : Pos.Raw) : Nat :=
hi.byteIdx - lo.byteIdx
theorem Pos.Raw.byteDistance_eq {lo hi : Pos.Raw} : lo.byteDistance hi = hi.byteIdx - lo.byteIdx :=
(rfl)
@[simp]
theorem rawEndPos_empty : "".rawEndPos = 0 := rfl
@[deprecated rawEndPos_empty (since := "2025-10-20")]
theorem endPos_empty : "".rawEndPos = 0 := rfl
/--
Accesses the indicated byte in the UTF-8 encoding of a string.
At runtime, this function is implemented by efficient, constant-time code.
-/
@[extern "lean_string_get_byte_fast", expose]
def getUTF8Byte (s : @& String) (p : Pos.Raw) (h : p < s.rawEndPos) : UInt8 :=
s.toByteArray[p.byteIdx]
@[deprecated getUTF8Byte (since := "2025-10-01"), extern "lean_string_get_byte_fast", expose]
abbrev getUtf8Byte (s : String) (p : Pos.Raw) (h : p < s.rawEndPos) : UInt8 :=
s.getUTF8Byte p h
protected theorem Pos.Raw.le_trans {a b c : Pos.Raw} : a ≤ b → b ≤ c → a ≤ c := by
simpa [le_iff] using Nat.le_trans
protected theorem Pos.Raw.lt_of_lt_of_le {a b c : Pos.Raw} : a < b → b ≤ c → a < c := by
simpa [le_iff, lt_iff] using Nat.lt_of_lt_of_le
/--
Offsets `p` by `offset` on the left. This is not an `HAdd` instance because it should be a
relatively rare operation, so we use a name to make accidental use less likely. To offset a position
by the size of a character character `c` or string `s`, you can use `c + p` resp. `s + p`.
This should be seen as an operation that converts relative positions into absolute positions.
See also `Pos.Raw.increaseBy`, which is an "advancing" operation.
-/
@[expose, inline]
def Pos.Raw.offsetBy (p : Pos.Raw) (offset : Pos.Raw) : Pos.Raw where
byteIdx := offset.byteIdx + p.byteIdx
@[simp]
theorem Pos.Raw.byteIdx_offsetBy {p : Pos.Raw} {offset : Pos.Raw} :
(p.offsetBy offset).byteIdx = offset.byteIdx + p.byteIdx := (rfl)
theorem Pos.Raw.offsetBy_assoc {p q r : Pos.Raw} :
(p.offsetBy q).offsetBy r = p.offsetBy (q.offsetBy r) := by
ext
simp [Nat.add_assoc]
@[simp]
theorem Pos.Raw.offsetBy_zero_left {p : Pos.Raw} : (0 : Pos.Raw).offsetBy p = p := by
simp [Pos.Raw.ext_iff]
@[simp]
theorem Pos.Raw.offsetBy_zero {p : Pos.Raw} : p.offsetBy 0 = p := by
simp [Pos.Raw.ext_iff]
/--
Decreases `p` by `offset`. This is not an `HSub` instance because it should be a relatively
rare operation, so we use a name to make accidental use less likely. To unoffset a position
by the size of a character `c` or string `s`, you can use `p - c` resp. `p - s`.
This should be seen as an operation that converts absolute positions into relative positions.
See also `Pos.Raw.decreaseBy`, which is an "unadvancing" operation.
-/
@[expose, inline]
def Pos.Raw.unoffsetBy (p : Pos.Raw) (offset : Pos.Raw) : Pos.Raw where
byteIdx := p.byteIdx - offset.byteIdx
@[simp]
theorem Pos.Raw.byteIdx_unoffsetBy {p : Pos.Raw} {offset : Pos.Raw} :
(p.unoffsetBy offset).byteIdx = p.byteIdx - offset.byteIdx := (rfl)
theorem Pos.Raw.offsetBy_unoffsetBy_of_le {p : Pos.Raw} {q : Pos.Raw} (h : q ≤ p) :
(p.unoffsetBy q).offsetBy q = p := by
ext
simp_all [le_iff]
@[simp]
theorem Pos.Raw.unoffsetBy_offsetBy {p q : Pos.Raw} : (p.offsetBy q).unoffsetBy q = p := by
ext
simp
@[simp]
theorem Pos.Raw.unoffsetBy_zero {p : Pos.Raw} : p.unoffsetBy 0 = p := by
simp [Pos.Raw.ext_iff]
@[simp]
theorem Pos.Raw.unoffsetBy_le_self {p q : Pos.Raw} : p.unoffsetBy q ≤ p := by
simp [Pos.Raw.le_iff]
@[simp]
theorem Pos.Raw.eq_zero_iff {p : Pos.Raw} : p = 0 ↔ p.byteIdx = 0 :=
Pos.Raw.ext_iff
/--
Advances `p` by `n` bytes. This is not an `HAdd` instance because it should be a relatively
rare operation, so we use a name to make accidental use less likely. To add the size of a
character `c` or string `s` to a raw position `p`, you can use `p + c` resp. `p + s`.
This should be seen as an "advance" or "skip".
See also `Pos.Raw.offsetBy`, which turns relative positions into absolute positions.
-/
@[expose, inline]
def Pos.Raw.increaseBy (p : Pos.Raw) (n : Nat) : Pos.Raw where
byteIdx := p.byteIdx + n
@[simp]
theorem Pos.Raw.byteIdx_increaseBy {p : Pos.Raw} {n : Nat} :
(p.increaseBy n).byteIdx = p.byteIdx + n := (rfl)
@[simp]
theorem Pos.Raw.increaseBy_zero {p : Pos.Raw} : p.increaseBy 0 = p := by
simp [Pos.Raw.ext_iff]
/--
Move the position `p` back by `n` bytes. This is not an `HSub` instance because it should be a
relatively rare operation, so we use a name to make accidental use less likely. To remove the size
of a character `c` or string `s` from a raw position `p`, you can use `p - c` resp. `p - s`.
This should be seen as the inverse of an "advance" or "skip".
See also `Pos.Raw.unoffsetBy`, which turns absolute positions into relative positions.
-/
@[expose, inline]
def Pos.Raw.decreaseBy (p : Pos.Raw) (n : Nat) : Pos.Raw where
byteIdx := p.byteIdx - n
@[simp]
theorem Pos.Raw.byteIdx_decreaseBy {p : Pos.Raw} {n : Nat} :
(p.decreaseBy n).byteIdx = p.byteIdx - n := (rfl)
@[simp]
theorem Pos.Raw.decreaseBy_zero {p : Pos.Raw} : p.decreaseBy 0 = p := by
simp [Pos.Raw.ext_iff]
theorem Pos.Raw.increaseBy_charUtf8Size {p : Pos.Raw} {c : Char} :
p.increaseBy c.utf8Size = p + c := by
simp [Pos.Raw.ext_iff]
/-- Increases the byte offset of the position by `1`. Not to be confused with `Pos.next`. -/
@[inline, expose]
def Pos.Raw.inc (p : Pos.Raw) : Pos.Raw :=
⟨p.byteIdx + 1⟩
@[simp]
theorem Pos.Raw.byteIdx_inc {p : Pos.Raw} : p.inc.byteIdx = p.byteIdx + 1 := (rfl)
@[simp]
theorem Pos.Raw.inc_unoffsetBy_inc {p q : Pos.Raw} : p.inc.unoffsetBy q.inc = p.unoffsetBy q := by
simp [Pos.Raw.ext_iff]
/-- Decreases the byte offset of the position by `1`. Not to be confused with `Pos.prev`. -/
@[inline, expose]
def Pos.Raw.dec (p : Pos.Raw) : Pos.Raw :=
⟨p.byteIdx - 1⟩
@[simp]
theorem Pos.Raw.byteIdx_dec {p : Pos.Raw} : p.dec.byteIdx = p.byteIdx - 1 := (rfl)
@[simp]
theorem Pos.Raw.le_refl {p : Pos.Raw} : p ≤ p := by simp [le_iff]
@[simp]
theorem Pos.Raw.lt_inc {p : Pos.Raw} : p < p.inc := by simp [lt_iff]
theorem Pos.Raw.le_of_lt {p q : Pos.Raw} : p < q → p ≤ q := by simpa [lt_iff, le_iff] using Nat.le_of_lt
@[simp]
theorem Pos.Raw.inc_le {p q : Pos.Raw} : p.inc ≤ q ↔ p < q := by simpa [lt_iff, le_iff] using Nat.succ_le_iff
@[simp]
theorem Pos.Raw.lt_inc_iff {p q : Pos.Raw} : p < q.inc ↔ p ≤ q := by simpa [lt_iff, le_iff] using Nat.lt_add_one_iff
theorem Pos.Raw.lt_of_le_of_lt {a b c : Pos.Raw} : a ≤ b → b < c → a < c := by
simpa [le_iff, lt_iff] using Nat.lt_of_le_of_lt
theorem Pos.Raw.ne_of_lt {a b : Pos.Raw} : a < b → a ≠ b := by
simpa [lt_iff, Pos.Raw.ext_iff] using Nat.ne_of_lt
@[deprecated Pos.Raw.lt_iff (since := "2025-10-10")]
theorem pos_lt_eq (p₁ p₂ : Pos.Raw) : (p₁ < p₂) = (p₁.1 < p₂.1) :=
propext Pos.Raw.lt_iff
@[deprecated Pos.Raw.byteIdx_add_char (since := "2025-10-10")]
theorem pos_add_char (p : Pos.Raw) (c : Char) : (p + c).byteIdx = p.byteIdx + c.utf8Size :=
Pos.Raw.byteIdx_add_char
protected theorem Pos.Raw.ne_zero_of_lt : {a b : Pos.Raw} → a < b → b ≠ 0
| _, _, hlt, rfl => Nat.not_lt_zero _ hlt
/--
Returns either `p₁` or `p₂`, whichever has the least byte index.
-/
protected abbrev Pos.Raw.min (p₁ p₂ : Pos.Raw) : Pos.Raw :=
{ byteIdx := p₁.byteIdx.min p₂.byteIdx }
@[export lean_string_pos_min]
def Pos.Raw.Internal.minImpl (p₁ p₂ : Pos.Raw) : Pos.Raw :=
Pos.Raw.min p₁ p₂
namespace Pos.Raw
theorem byteIdx_mk (n : Nat) : byteIdx ⟨n⟩ = n := rfl
@[simp] theorem mk_zero : ⟨0⟩ = (0 : Pos.Raw) := rfl
@[simp] theorem mk_byteIdx (p : Pos.Raw) : ⟨p.byteIdx⟩ = p := rfl
@[deprecated byteIdx_offsetBy (since := "2025-10-08")]
theorem add_byteIdx {p₁ p₂ : Pos.Raw} : (p₂.offsetBy p₁).byteIdx = p₁.byteIdx + p₂.byteIdx := by
simp
@[deprecated byteIdx_offsetBy (since := "2025-10-08")]
theorem add_eq {p₁ p₂ : Pos.Raw} : p₂.offsetBy p₁ = ⟨p₁.byteIdx + p₂.byteIdx⟩ := rfl
@[deprecated byteIdx_unoffsetBy (since := "2025-10-08")]
theorem sub_byteIdx (p₁ p₂ : Pos.Raw) : (p₁.unoffsetBy p₂).byteIdx = p₁.byteIdx - p₂.byteIdx := rfl
@[deprecated byteIdx_add_char (since := "2025-10-10")]
theorem addChar_byteIdx (p : Pos.Raw) (c : Char) : (p + c).byteIdx = p.byteIdx + c.utf8Size :=
byteIdx_add_char
theorem add_char_eq (p : Pos.Raw) (c : Char) : p + c = ⟨p.byteIdx + c.utf8Size⟩ := rfl
@[deprecated add_char_eq (since := "2025-10-10")]
theorem addChar_eq (p : Pos.Raw) (c : Char) : p + c = ⟨p.byteIdx + c.utf8Size⟩ :=
add_char_eq p c
theorem byteIdx_zero_add_char (c : Char) : ((0 : Pos.Raw) + c).byteIdx = c.utf8Size := by
simp only [byteIdx_add_char, byteIdx_zero, Nat.zero_add]
@[deprecated byteIdx_zero_add_char (since := "2025-10-10")]
theorem zero_addChar_byteIdx (c : Char) : ((0 : Pos.Raw) + c).byteIdx = c.utf8Size :=
byteIdx_zero_add_char c
theorem zero_add_char_eq (c : Char) : (0 : Pos.Raw) + c = ⟨c.utf8Size⟩ := by rw [← byteIdx_zero_add_char]
@[deprecated zero_add_char_eq (since := "2025-10-10")]
theorem zero_addChar_eq (c : Char) : (0 : Pos.Raw) + c = ⟨c.utf8Size⟩ :=
zero_add_char_eq c
theorem add_char_right_comm (p : Pos.Raw) (c₁ c₂ : Char) : p + c₁ + c₂ = p + c₂ + c₁ := by
simpa [Pos.Raw.ext_iff] using Nat.add_right_comm ..
@[deprecated add_char_right_comm (since := "2025-10-10")]
theorem addChar_right_comm (p : Pos.Raw) (c₁ c₂ : Char) : p + c₁ + c₂ = p + c₂ + c₁ :=
add_char_right_comm p c₁ c₂
theorem ne_of_gt {i₁ i₂ : Pos.Raw} (h : i₁ < i₂) : i₂ ≠ i₁ := (ne_of_lt h).symm
@[deprecated byteIdx_add_string (since := "2025-10-10")]
theorem byteIdx_addString (p : Pos.Raw) (s : String) :
(p + s).byteIdx = p.byteIdx + s.utf8ByteSize := byteIdx_add_string
theorem addString_eq (p : Pos.Raw) (s : String) : p + s = ⟨p.byteIdx + s.utf8ByteSize⟩ := rfl
theorem byteIdx_zero_add_string (s : String) : ((0 : Pos.Raw) + s).byteIdx = s.utf8ByteSize := by
simp only [byteIdx_add_string, byteIdx_zero, Nat.zero_add]
@[deprecated byteIdx_zero_add_string (since := "2025-10-10")]
theorem byteIdx_zero_addString (s : String) : ((0 : Pos.Raw) + s).byteIdx = s.utf8ByteSize :=
byteIdx_zero_add_string s
theorem zero_add_string_eq (s : String) : (0 : Pos.Raw) + s = ⟨s.utf8ByteSize⟩ := by
rw [← byteIdx_zero_add_string]
@[deprecated zero_add_string_eq (since := "2025-10-10")]
theorem zero_addString_eq (s : String) : (0 : Pos.Raw) + s = ⟨s.utf8ByteSize⟩ :=
zero_add_string_eq s
@[simp] theorem mk_le_mk {i₁ i₂ : Nat} : Pos.Raw.mk i₁ ≤ Pos.Raw.mk i₂ ↔ i₁ ≤ i₂ := .rfl
@[simp] theorem mk_lt_mk {i₁ i₂ : Nat} : Pos.Raw.mk i₁ < Pos.Raw.mk i₂ ↔ i₁ < i₂ := .rfl
end Pos.Raw
end String