| /- | |
| Copyright (c) 2019 Gabriel Ebner. All rights reserved. | |
| Released under Apache 2.0 license as described in the file LICENSE. | |
| Authors: Gabriel Ebner, Marc Huisinga | |
| -/ | |
| module | |
| prelude | |
| public import Init.Data.Range | |
| public import Init.Data.OfScientific | |
| public import Init.Data.Hashable | |
| public import Std.Data.TreeMap.Raw.Basic | |
| public import Init.Data.Ord.String | |
| import Init.Data.Range.Polymorphic.Iterators | |
| import Init.Data.Range.Polymorphic.Nat | |
| import Init.Data.String.Substring | |
| import Init.Data.ToString.Macro | |
| public section | |
| namespace Lean | |
| -- mantissa * 10^-exponent | |
| structure JsonNumber where | |
| mantissa : Int | |
| exponent : Nat | |
| deriving DecidableEq, Hashable | |
| namespace JsonNumber | |
| @[expose] protected def fromNat (n : Nat) : JsonNumber := ⟨n, 0⟩ | |
| @[expose] protected def fromInt (n : Int) : JsonNumber := ⟨n, 0⟩ | |
| instance : Coe Nat JsonNumber := ⟨JsonNumber.fromNat⟩ | |
| instance : Coe Int JsonNumber := ⟨JsonNumber.fromInt⟩ | |
| instance : OfNat JsonNumber n := ⟨JsonNumber.fromNat n⟩ | |
| private partial def countDigits (n : Nat) : Nat := | |
| let rec loop (n digits : Nat) : Nat := | |
| if n ≤ 9 then | |
| digits | |
| else | |
| loop (n/10) (digits+1) | |
| loop n 1 | |
| -- convert mantissa * 10^-exponent to 0.mantissa * 10^exponent | |
| protected def normalize : JsonNumber → Int × Nat × Int | |
| | ⟨m, e⟩ => Id.run do | |
| if m = 0 then (0, 0, 0) | |
| else | |
| let sign : Int := if m > 0 then 1 else -1 | |
| let mut mAbs := m.natAbs | |
| let nDigits := countDigits mAbs | |
| -- eliminate trailing zeros | |
| for _ in *...nDigits do | |
| if mAbs % 10 = 0 then | |
| mAbs := mAbs / 10 | |
| else | |
| break | |
| (sign, mAbs, -(e : Int) + nDigits) | |
| -- todo (Dany): We should have an Ordering version of this. | |
| def lt (a b : JsonNumber) : Bool := | |
| let (as, am, ae) := a.normalize | |
| let (bs, bm, be) := b.normalize | |
| match (as, bs) with | |
| | (-1, 1) => true | |
| | (1, -1) => false | |
| | _ => | |
| let ((am, ae), (bm, be)) := | |
| if as = -1 && bs = -1 then | |
| ((bm, be), (am, ae)) | |
| else | |
| ((am, ae), (bm, be)) | |
| let amDigits := countDigits am | |
| let bmDigits := countDigits bm | |
| -- align the mantissas | |
| let (am, bm) := | |
| if amDigits < bmDigits then | |
| (am * 10^(bmDigits - amDigits), bm) | |
| else | |
| (am, bm * 10^(amDigits - bmDigits)) | |
| if ae < be then true | |
| else if ae > be then false | |
| else am < bm | |
| instance ltProp : LT JsonNumber := | |
| ⟨fun a b => lt a b = true⟩ | |
| instance (a b : JsonNumber) : Decidable (a < b) := | |
| inferInstanceAs (Decidable (lt a b = true)) | |
| instance : Ord JsonNumber where | |
| compare x y := | |
| if x < y then Ordering.lt | |
| else if x > y then Ordering.gt | |
| else Ordering.eq | |
| protected def toString : JsonNumber → String | |
| | ⟨m, 0⟩ => m.repr | |
| | ⟨m, e⟩ => | |
| let sign := if m ≥ 0 then "" else "-" | |
| let m := m.natAbs | |
| -- if there are too many zeroes after the decimal, we | |
| -- use exponents to compress the representation. | |
| -- this is mostly done for memory usage reasons: | |
| -- the size of the representation would otherwise | |
| -- grow exponentially in the value of exponent. | |
| let exp : Int := 9 + countDigits m - (e : Int) | |
| let exp := if exp < 0 then exp else 0 | |
| let e' := 10 ^ (e - exp.natAbs) | |
| let left := (m / e').repr | |
| if m % e' = 0 && exp = 0 then | |
| s!"{sign}{left}" | |
| else | |
| let right := e' + m % e' | |
| |>.repr.toRawSubstring.drop 1 | |
| |>.dropRightWhile (fun c => c = '0') | |
| |>.toString | |
| let exp := if exp = 0 then "" else "e" ++ exp.repr | |
| s!"{sign}{left}.{right}{exp}" | |
| -- shift a JsonNumber by a specified amount of places to the left | |
| protected def shiftl : JsonNumber → Nat → JsonNumber | |
| -- if s ≤ e, then 10 ^ (s - e) = 1, and hence the mantissa remains unchanged. | |
| -- otherwise, the expression pads the mantissa with zeroes | |
| -- to accommodate for the remaining places to shift. | |
| | ⟨m, e⟩, s => ⟨m * (10 ^ (s - e) : Nat), e - s⟩ | |
| -- shift a JsonNumber by a specified amount of places to the right | |
| protected def shiftr : JsonNumber → Nat → JsonNumber | |
| | ⟨m, e⟩, s => ⟨m, e + s⟩ | |
| instance : ToString JsonNumber := ⟨JsonNumber.toString⟩ | |
| instance : Repr JsonNumber where | |
| reprPrec | ⟨m, e⟩, _ => Std.Format.bracket "⟨" (repr m ++ "," ++ repr e) "⟩" | |
| instance : OfScientific JsonNumber where | |
| ofScientific mantissa exponentSign decimalExponent := | |
| if exponentSign then | |
| {mantissa := mantissa, exponent := decimalExponent} | |
| else | |
| {mantissa := (mantissa * 10 ^ decimalExponent : Nat), exponent := 0} | |
| instance : Neg JsonNumber where | |
| neg jn := ⟨- jn.mantissa, jn.exponent⟩ | |
| instance : Inhabited JsonNumber := ⟨0⟩ | |
| def toFloat : JsonNumber → Float | |
| | ⟨m, e⟩ => (if m >= 0 then 1.0 else -1.0) * OfScientific.ofScientific m.natAbs true e | |
| /-- Creates a json number from a positive float, panicking if it isn't. | |
| [todo]EdAyers: Currently goes via a string representation, when more float primitives are available | |
| should switch to using those. -/ | |
| private def fromPositiveFloat! (x : Float) : JsonNumber := | |
| match Lean.Syntax.decodeScientificLitVal? (toString x) with | |
| | none => panic! s!"Failed to parse {toString x}" | |
| | some (m, sign, e) => OfScientific.ofScientific m sign e | |
| /-- Attempts to convert a float to a JsonNumber, if the number isn't finite returns | |
| the appropriate string from "NaN", "Infinity", "-Infinity". -/ | |
| def fromFloat? (x : Float): Sum String JsonNumber := | |
| if x.isNaN then Sum.inl "NaN" | |
| else if x.isInf then | |
| Sum.inl <| if x > 0 then "Infinity" else "-Infinity" | |
| else if x == 0.0 then | |
| Sum.inr 0 -- special case to avoid -0.0 | |
| else if x < 0.0 then | |
| Sum.inr <| Neg.neg <| fromPositiveFloat! <| Neg.neg <| x | |
| else | |
| Sum.inr <| fromPositiveFloat! <| x | |
| end JsonNumber | |
| def strLt (a b : String) := Decidable.decide (a < b) | |
| inductive Json where | |
| | null | |
| | bool (b : Bool) | |
| | num (n : JsonNumber) | |
| | str (s : String) | |
| | arr (elems : Array Json) | |
| | obj (kvPairs : Std.TreeMap.Raw String Json) | |
| deriving Inhabited | |
| namespace Json | |
| private partial def beq' : Json → Json → Bool | |
| | null, null => true | |
| | bool a, bool b => a == b | |
| | num a, num b => a == b | |
| | str a, str b => a == b | |
| | arr a, arr b => | |
| let _ : BEq Json := ⟨beq'⟩ | |
| a == b | |
| | obj a, obj b => | |
| let _ : BEq Json := ⟨beq'⟩ | |
| let szA := a.foldl (init := 0) (fun a _ _ => a + 1) | |
| let szB := b.foldl (init := 0) (fun a _ _ => a + 1) | |
| szA == szB && a.all fun field fa => | |
| match b.get? field with | |
| | none => false | |
| | some fb => fa == fb | |
| | _, _ => false | |
| instance : BEq Json where | |
| beq := private beq' | |
| private partial def hash' : Json → UInt64 | |
| | null => 11 | |
| | bool b => mixHash 13 <| hash b | |
| | num n => mixHash 17 <| hash n | |
| | str s => mixHash 19 <| hash s | |
| | arr elems => | |
| mixHash 23 <| elems.foldl (init := 7) fun r a => mixHash r (hash' a) | |
| | obj kvPairs => | |
| mixHash 29 <| kvPairs.foldl (init := 7) fun r k v => mixHash r <| mixHash (hash k) (hash' v) | |
| instance : Hashable Json where | |
| hash := private hash' | |
| def mkObj (o : List (String × Json)) : Json := | |
| obj <| Std.TreeMap.Raw.ofList o | |
| instance : Coe Nat Json := ⟨fun n => Json.num n⟩ | |
| instance : Coe Int Json := ⟨fun n => Json.num n⟩ | |
| instance : Coe String Json := ⟨Json.str⟩ | |
| instance : Coe Bool Json := ⟨Json.bool⟩ | |
| instance : OfNat Json n := ⟨Json.num n⟩ | |
| def isNull : Json -> Bool | |
| | null => true | |
| | _ => false | |
| def getObj? : Json → Except String (Std.TreeMap.Raw String Json compare) | |
| | obj kvs => return kvs | |
| | _ => throw "object expected" | |
| def getArr? : Json → Except String (Array Json) | |
| | arr a => return a | |
| | _ => throw "array expected" | |
| def getStr? : Json → Except String String | |
| | str s => return s | |
| | _ => throw "String expected" | |
| def getNat? : Json → Except String Nat | |
| | (n : Nat) => return n | |
| | _ => throw "Natural number expected" | |
| def getInt? : Json → Except String Int | |
| | (i : Int) => return i | |
| | _ => throw "Integer expected" | |
| def getBool? : Json → Except String Bool | |
| | (b : Bool) => return b | |
| | _ => throw "Bool expected" | |
| def getNum? : Json → Except String JsonNumber | |
| | num n => return n | |
| | _ => throw "number expected" | |
| def getObjVal? : Json → String → Except String Json | |
| | obj kvs, k => | |
| match kvs.get? k with | |
| | some v => return v | |
| | none => throw s!"property not found: {k}" | |
| | _ , _ => throw "object expected" | |
| def getArrVal? : Json → Nat → Except String Json | |
| | arr a, i => | |
| match a[i]? with | |
| | some v => return v | |
| | none => throw s!"index out of bounds: {i}" | |
| | _ , _ => throw "array expected" | |
| def getObjValD (j : Json) (k : String) : Json := | |
| (j.getObjVal? k).toOption.getD null | |
| def setObjVal! : Json → String → Json → Json | |
| | obj kvs, k, v => obj <| kvs.insert k v | |
| | _ , _, _ => panic! "Json.setObjVal!: not an object: {j}" | |
| /-- Assuming both inputs `o₁, o₂` are json objects, will compute `{...o₁, ...o₂}`. | |
| If `o₁` is not a json object, `o₂` will be returned. | |
| -/ | |
| def mergeObj : Json → Json → Json | |
| | obj kvs₁, obj kvs₂ => | |
| obj <| kvs₂.foldl Std.TreeMap.Raw.insert kvs₁ | |
| | _, j₂ => j₂ | |
| inductive Structured where | |
| | arr (elems : Array Json) | |
| | obj (kvPairs : Std.TreeMap.Raw String Json compare) | |
| instance : Coe (Array Json) Structured := ⟨Structured.arr⟩ | |
| instance : Coe (Std.TreeMap.Raw String Json) Structured := ⟨Structured.obj⟩ | |
| end Json | |
| end Lean |