blob: f44d583830cec4f237b70c5c3a9a759c92ffa9b0 [file]
/-
Copyright (c) 2018 Microsoft Corporation. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Author: Sebastian Ullrich, Leonardo de Moura, Joachim Breitner
A string trie data structure, used for tokenizing the Lean language
-/
prelude
import Lean.Data.Format
namespace Lean
namespace Data
/-
## Implementation notes
Tries have typically many nodes with small degree, where a linear scan
through the (compact) `ByteArray` is faster than using binary search or
search trees like `RBTree`.
Moreover, many nodes have degree 1, which justifies the special case `Node1`
constructor.
The code would be a bit less repetitive if we used something like the following
```
mutual
def Trie α := Option α × ByteAssoc α
inductive ByteAssoc α where
| leaf : Trie α
| node1 : UInt8 → Trie α → Trie α
| node : ByteArray → Array (Trie α) → Trie α
end
```
but that would come at the cost of extra indirections.
-/
/-- A Trie is a key-value store where the keys are of type `String`,
and the internal structure is a tree that branches on the bytes of the string. -/
inductive Trie (α : Type) where
| leaf : Option α → Trie α
| node1 : Option α → UInt8 → Trie α → Trie α
| node : Option α → ByteArray → Array (Trie α) → Trie α
namespace Trie
variable {α : Type}
/-- The empty `Trie` -/
def empty : Trie α := leaf none
instance : EmptyCollection (Trie α) :=
⟨empty⟩
instance : Inhabited (Trie α) where
default := empty
/-- Insert or update the value at a the given key `s`. -/
partial def upsert (t : Trie α) (s : String) (f : Option α → α) : Trie α :=
let rec insertEmpty (i : Nat) : Trie α :=
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
let t := insertEmpty (i + 1)
node1 none c t
else
leaf (f .none)
let rec loop
| i, leaf v =>
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
let t := insertEmpty (i + 1)
node1 v c t
else
leaf (f v)
| i, node1 v c' t' =>
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
if c == c'
then node1 v c' (loop (i + 1) t')
else
let t := insertEmpty (i + 1)
node v (.mk #[c, c']) #[t, t']
else
node1 (f v) c' t'
| i, node v cs ts =>
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
match cs.findIdx? (· == c) with
| none =>
let t := insertEmpty (i + 1)
node v (cs.push c) (ts.push t)
| some idx =>
node v cs (ts.modify idx (loop (i + 1)))
else
node (f v) cs ts
loop 0 t
/-- Inserts a value at a the given key `s`, overriding an existing value if present. -/
partial def insert (t : Trie α) (s : String) (val : α) : Trie α :=
upsert t s (fun _ => val)
/-- Looks up a value at the given key `s`. -/
partial def find? (t : Trie α) (s : String) : Option α :=
let rec loop
| i, leaf val =>
if i < s.utf8ByteSize then
none
else
val
| i, node1 val c' t' =>
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
if c == c'
then loop (i + 1) t'
else none
else
val
| i, node val cs ts =>
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
match cs.findIdx? (· == c) with
| none => none
| some idx => loop (i + 1) (ts.get! idx)
else
val
loop 0 t
/-- Returns an `Array` of all values in the trie, in no particular order. -/
partial def values (t : Trie α) : Array α := go t |>.run #[] |>.2
where
go : Trie α → StateM (Array α) Unit
| leaf a? => do
if let some a := a? then
modify (·.push a)
| node1 a? _ t' => do
if let some a := a? then
modify (·.push a)
go t'
| node a? _ ts => do
if let some a := a? then
modify (·.push a)
ts.forM fun t' => go t'
/-- Returns all values whose key have the given string `pre` as a prefix, in no particular order. -/
partial def findPrefix (t : Trie α) (pre : String) : Array α := go t 0
where
go (t : Trie α) (i : Nat) : Array α :=
if h : i < pre.utf8ByteSize then
let c := pre.getUtf8Byte i h
match t with
| leaf _val => .empty
| node1 _val c' t' =>
if c == c'
then go t' (i + 1)
else .empty
| node _val cs ts =>
match cs.findIdx? (· == c) with
| none => .empty
| some idx => go (ts.get! idx) (i + 1)
else
t.values
/-- Find the longest _key_ in the trie that is contained in the given string `s` at position `i`,
and return the associated value. -/
partial def matchPrefix (s : String) (t : Trie α) (i : String.Pos) : Option α :=
let rec loop
| leaf v, _, res =>
if v.isSome then v else res
| node1 v c' t', i, res =>
let res := if v.isSome then v else res
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
if c == c'
then loop t' (i + 1) res
else res
else
res
| node v cs ts, i, res =>
let res := if v.isSome then v else res
if h : i < s.utf8ByteSize then
let c := s.getUtf8Byte i h
match cs.findIdx? (· == c) with
| none => res
| some idx => loop (ts.get! idx) (i + 1) res
else
res
loop t i.byteIdx none
private partial def toStringAux {α : Type} : Trie α → List Format
| leaf _ => []
| node1 _ c t =>
[ format (repr c), Format.group $ Format.nest 4 $ flip Format.joinSep Format.line $ toStringAux t ]
| node _ cs ts =>
List.join $ List.zipWith (fun c t =>
[ format (repr c), (Format.group $ Format.nest 4 $ flip Format.joinSep Format.line $ toStringAux t) ]
) cs.toList ts.toList
instance {α : Type} : ToString (Trie α) :=
⟨fun t => (flip Format.joinSep Format.line $ toStringAux t).pretty⟩
end Trie
end Data
end Lean