blob: 718524748b46074dead79d9eb15f25e8596bd665 [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Henrik Böving
-/
module
prelude
public import Init.Data.String.Basic
public import Init.Data.Iterators.Basic
set_option doc.verso true
/-!
This module defines the notion of patterns which is central to the {name}`String.Slice` and
{name}`String` API. All functions on {name}`String.Slice` and {name}`String` that
“search for something” are polymorphic over a pattern instead of taking just one particular kind
of pattern such as a {name}`Char`. The key components are:
- {name (scope := "Init.Data.String.Pattern.Basic")}`ToForwardSearcher`
- {name (scope := "Init.Data.String.Pattern.Basic")}`ForwardPattern`
- {name (scope := "Init.Data.String.Pattern.Basic")}`ToBackwardSearcher`
- {name (scope := "Init.Data.String.Pattern.Basic")}`BackwardPattern`
-/
public section
namespace String.Slice.Pattern
/--
A step taken during the traversal of a {name}`Slice` by a forward or backward searcher.
-/
inductive SearchStep (s : Slice) where
/--
The subslice starting at {name}`startPos` and ending at {name}`endPos` did not match the pattern.
-/
| rejected (startPos endPos : s.Pos)
/--
The subslice starting at {name}`startPos` and ending at {name}`endPos` matches the pattern.
-/
| matched (startPos endPos : s.Pos)
deriving Inhabited, BEq
/--
Provides a conversion from a pattern to an iterator of {name}`SearchStep` that searches for matches
of the pattern from the start towards the end of a {name}`Slice`.
-/
class ToForwardSearcher {ρ : Type} (pat : ρ) (σ : outParam (Slice → Type)) where
/--
Builds an iterator of {name}`SearchStep` corresponding to matches of {name}`pat` along the slice
{name}`s`. The {name}`SearchStep`s returned by this iterator must contain ranges that are
adjacent, non-overlapping and cover all of {name}`s`.
-/
toSearcher : (s : Slice) → Std.Iter (α := σ s) (SearchStep s)
/--
Provides simple pattern matching capabilities from the start of a {name}`Slice`.
While these operations can be implemented on top of {name}`ToForwardSearcher` some patterns allow
for more efficient implementations. This class can be used to specialize for them. If there is no
need to specialize in this fashion, then
{name (scope := "Init.Data.String.Pattern.Basic")}`ForwardPattern.defaultImplementation` can be used
to automatically derive an instance.
-/
class ForwardPattern {ρ : Type} (pat : ρ) where
/--
Checks whether the slice starts with the pattern.
-/
startsWith : Slice → Bool
/--
Checks whether the slice starts with the pattern. If it does, the slice is returned with the
prefix removed; otherwise the result is {name}`none`.
-/
dropPrefix? : (s : Slice) → Option s.Pos
namespace Internal
@[extern "lean_string_memcmp"]
def memcmpStr (lhs rhs : @& String) (lstart : @& String.Pos.Raw) (rstart : @& String.Pos.Raw)
(len : @& String.Pos.Raw) (h1 : len.offsetBy lstart ≤ lhs.rawEndPos)
(h2 : len.offsetBy rstart ≤ rhs.rawEndPos) : Bool :=
go 0
where
go (curr : String.Pos.Raw) : Bool :=
if h : curr < len then
have hl := by
simp [Pos.Raw.le_iff, Pos.Raw.lt_iff] at h h1 ⊢
omega
have hr := by
simp [Pos.Raw.le_iff, Pos.Raw.lt_iff] at h h2 ⊢
omega
if lhs.getUTF8Byte (curr.offsetBy lstart) hl == rhs.getUTF8Byte (curr.offsetBy rstart) hr then
go curr.inc
else
false
else
true
termination_by len.byteIdx - curr.byteIdx
decreasing_by
simp [Pos.Raw.lt_iff] at h ⊢
omega
@[inline]
def memcmpSlice (lhs rhs : Slice) (lstart : String.Pos.Raw) (rstart : String.Pos.Raw)
(len : String.Pos.Raw) (h1 : len.offsetBy lstart ≤ lhs.rawEndPos)
(h2 : len.offsetBy rstart ≤ rhs.rawEndPos) : Bool :=
memcmpStr
lhs.str
rhs.str
(lstart.offsetBy lhs.startInclusive.offset)
(rstart.offsetBy rhs.startInclusive.offset)
len
(by
have := lhs.startInclusive_le_endExclusive
have := lhs.endExclusive.isValid.le_utf8ByteSize
simp [ValidPos.le_iff, Pos.Raw.le_iff, Slice.utf8ByteSize_eq] at *
omega)
(by
have := rhs.startInclusive_le_endExclusive
have := rhs.endExclusive.isValid.le_utf8ByteSize
simp [ValidPos.le_iff, Pos.Raw.le_iff, Slice.utf8ByteSize_eq] at *
omega)
end Internal
namespace ForwardPattern
variable {ρ : Type} {σ : Slice → Type}
variable [∀ s, Std.Iterators.Iterator (σ s) Id (SearchStep s)]
variable (pat : ρ) [ToForwardSearcher pat σ]
@[specialize pat]
def defaultStartsWith (s : Slice) : Bool :=
let searcher := ToForwardSearcher.toSearcher pat s
match searcher.step with
| .yield _ (.matched start ..) _ => s.startPos = start
| _ => false
@[specialize pat]
def defaultDropPrefix? (s : Slice) : Option s.Pos :=
let searcher := ToForwardSearcher.toSearcher pat s
match searcher.step with
| .yield _ (.matched _ endPos) _ => some endPos
| _ => none
@[always_inline, inline]
def defaultImplementation {pat : ρ} [ToForwardSearcher pat σ] : ForwardPattern pat where
startsWith := defaultStartsWith pat
dropPrefix? := defaultDropPrefix? pat
end ForwardPattern
/--
Provides a conversion from a pattern to an iterator of {name}`SearchStep` searching for matches of
the pattern from the end towards the start of a {name}`Slice`.
-/
class ToBackwardSearcher {ρ : Type} (pat : ρ) (σ : outParam (Slice → Type)) where
/--
Build an iterator of {name}`SearchStep` corresponding to matches of {lean}`pat` along the slice
{name}`s`. The {name}`SearchStep`s returned by this iterator must contain ranges that are
adjacent, non-overlapping and cover all of {name}`s`.
-/
toSearcher : (s : Slice) → Std.Iter (α := σ s) (SearchStep s)
/--
Provides simple pattern matching capabilities from the end of a {name}`Slice`.
While these operations can be implemented on top of {name}`ToBackwardSearcher`, some patterns allow
for more efficient implementations. This class can be used to specialize for them. If there is no
need to specialize in this fashion, then
{name (scope := "Init.Data.String.Pattern.Basic")}`BackwardPattern.defaultImplementation` can be
used to automatically derive an instance.
-/
class BackwardPattern {ρ : Type} (pat : ρ) where
/--
Checks whether the slice ends with the pattern.
-/
endsWith : Slice → Bool
/--
Checks whether the slice ends with the pattern. If it does, the slice is returned with the
suffix removed; otherwise the result is {name}`none`.
-/
dropSuffix? : (s : Slice) → Option s.Pos
namespace ToBackwardSearcher
variable {ρ : Type} {σ : Slice → Type}
variable [∀ s, Std.Iterators.Iterator (σ s) Id (SearchStep s)]
variable (pat : ρ) [ToBackwardSearcher pat σ]
@[specialize pat]
def defaultEndsWith (s : Slice) : Bool :=
let searcher := ToBackwardSearcher.toSearcher pat s
match searcher.step with
| .yield _ (.matched _ endPos) _ => s.endPos = endPos
| _ => false
@[specialize pat]
def defaultDropSuffix? (s : Slice) : Option s.Pos :=
let searcher := ToBackwardSearcher.toSearcher pat s
match searcher.step with
| .yield _ (.matched startPos _) _ => some startPos
| _ => none
@[always_inline, inline]
def defaultImplementation {pat : ρ} [ToBackwardSearcher pat σ] : BackwardPattern pat where
endsWith := defaultEndsWith pat
dropSuffix? := defaultDropSuffix? pat
end ToBackwardSearcher
end String.Slice.Pattern