blob: 67e824d22ea647ab79a536279f7abec0bbad5a75 [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.Pattern.Basic
public import Init.Data.Iterators.Internal.Termination
public import Init.Data.Iterators.Consumers.Monadic.Loop
import Init.Data.String.Termination
set_option doc.verso true
/-!
This module defines the necessary instances to register {name}`Char` with the pattern framework.
-/
public section
namespace String.Slice.Pattern
structure ForwardCharSearcher (s : Slice) where
currPos : s.Pos
needle : Char
deriving Inhabited
namespace ForwardCharSearcher
@[inline]
def iter (c : Char) (s : Slice) : Std.Iter (α := ForwardCharSearcher s) (SearchStep s) :=
{ internalState := { currPos := s.startPos, needle := c }}
instance (s : Slice) : Std.Iterators.Iterator (ForwardCharSearcher s) Id (SearchStep s) where
IsPlausibleStep it
| .yield it' out =>
it.internalState.needle = it'.internalState.needle ∧
∃ h1 : it.internalState.currPos ≠ s.endPos,
it'.internalState.currPos = it.internalState.currPos.next h1 ∧
match out with
| .matched startPos endPos =>
it.internalState.currPos = startPos ∧
it'.internalState.currPos = endPos ∧
it.internalState.currPos.get h1 = it.internalState.needle
| .rejected startPos endPos =>
it.internalState.currPos = startPos ∧
it'.internalState.currPos = endPos ∧
it.internalState.currPos.get h1 ≠ it.internalState.needle
| .skip _ => False
| .done => it.internalState.currPos = s.endPos
step := fun ⟨currPos, needle⟩ =>
if h1 : currPos = s.endPos then
pure (.deflate ⟨.done, by simp [h1]⟩)
else
let nextPos := currPos.next h1
let nextIt := ⟨nextPos, needle⟩
if h2 : currPos.get h1 = needle then
pure (.deflate ⟨.yield nextIt (.matched currPos nextPos), by simp [h1, h2, nextIt, nextPos]⟩)
else
pure (.deflate ⟨.yield nextIt (.rejected currPos nextPos), by simp [h1, h2, nextIt, nextPos]⟩)
def finitenessRelation : Std.Iterators.FinitenessRelation (ForwardCharSearcher s) Id where
rel := InvImage WellFoundedRelation.rel (fun it => it.internalState.currPos)
wf := InvImage.wf _ WellFoundedRelation.wf
subrelation {it it'} h := by
simp_wf
obtain ⟨step, h, h'⟩ := h
cases step
· cases h
obtain ⟨_, h1, h2, _⟩ := h'
simp [h2]
· cases h'
· cases h
instance : Std.Iterators.Finite (ForwardCharSearcher s) Id :=
.of_finitenessRelation finitenessRelation
instance : Std.Iterators.IteratorLoop (ForwardCharSearcher s) Id Id :=
.defaultImplementation
instance {c : Char} : ToForwardSearcher c ForwardCharSearcher where
toSearcher := iter c
instance {c : Char} : ForwardPattern c := .defaultImplementation
end ForwardCharSearcher
structure BackwardCharSearcher (s : Slice) where
currPos : s.Pos
needle : Char
deriving Inhabited
namespace BackwardCharSearcher
@[inline]
def iter (c : Char) (s : Slice) : Std.Iter (α := BackwardCharSearcher s) (SearchStep s) :=
{ internalState := { currPos := s.endPos, needle := c }}
instance (s : Slice) : Std.Iterators.Iterator (BackwardCharSearcher s) Id (SearchStep s) where
IsPlausibleStep it
| .yield it' out =>
it.internalState.needle = it'.internalState.needle ∧
∃ h1 : it.internalState.currPos ≠ s.startPos,
it'.internalState.currPos = it.internalState.currPos.prev h1 ∧
match out with
| .matched startPos endPos =>
it.internalState.currPos = endPos ∧
it'.internalState.currPos = startPos ∧
(it.internalState.currPos.prev h1).get Pos.prev_ne_endPos = it.internalState.needle
| .rejected startPos endPos =>
it.internalState.currPos = endPos ∧
it'.internalState.currPos = startPos ∧
(it.internalState.currPos.prev h1).get Pos.prev_ne_endPos ≠ it.internalState.needle
| .skip _ => False
| .done => it.internalState.currPos = s.startPos
step := fun ⟨currPos, needle⟩ =>
if h1 : currPos = s.startPos then
pure (.deflate ⟨.done, by simp [h1]⟩)
else
let nextPos := currPos.prev h1
let nextIt := ⟨nextPos, needle⟩
if h2 : nextPos.get Pos.prev_ne_endPos = needle then
pure (.deflate ⟨.yield nextIt (.matched nextPos currPos), by simp [h1, h2, nextIt, nextPos]⟩)
else
pure (.deflate ⟨.yield nextIt (.rejected nextPos currPos), by simp [h1, h2, nextIt, nextPos]⟩)
def finitenessRelation : Std.Iterators.FinitenessRelation (BackwardCharSearcher s) Id where
rel := InvImage WellFoundedRelation.rel (fun it => it.internalState.currPos.down)
wf := InvImage.wf _ WellFoundedRelation.wf
subrelation {it it'} h := by
simp_wf
obtain ⟨step, h, h'⟩ := h
cases step
· cases h
obtain ⟨_, h1, h2, _⟩ := h'
simp [h2]
· cases h'
· cases h
instance : Std.Iterators.Finite (BackwardCharSearcher s) Id :=
.of_finitenessRelation finitenessRelation
instance : Std.Iterators.IteratorLoop (BackwardCharSearcher s) Id Id :=
.defaultImplementation
instance {c : Char} : ToBackwardSearcher c BackwardCharSearcher where
toSearcher := iter c
instance {c : Char} : BackwardPattern c := ToBackwardSearcher.defaultImplementation
end BackwardCharSearcher
end String.Slice.Pattern