diff options
author | Philipp Haller <hallerp@gmail.com> | 2006-07-13 13:08:58 +0000 |
---|---|---|
committer | Philipp Haller <hallerp@gmail.com> | 2006-07-13 13:08:58 +0000 |
commit | 5e37103071da917781ba59c571ecb97558a5b582 (patch) | |
tree | 4e98fe98a98f941f905a2c15a56038369f07cf82 /src | |
parent | 5c97c9e85cf8991226fe351e2a0ca8b8d393f60b (diff) | |
download | scala-5e37103071da917781ba59c571ecb97558a5b582.tar.gz scala-5e37103071da917781ba59c571ecb97558a5b582.tar.bz2 scala-5e37103071da917781ba59c571ecb97558a5b582.zip |
Added pickler combinators to scala.io
Diffstat (limited to 'src')
-rw-r--r-- | src/library/scala/io/BytePickle.scala | 314 |
1 files changed, 314 insertions, 0 deletions
diff --git a/src/library/scala/io/BytePickle.scala b/src/library/scala/io/BytePickle.scala new file mode 100644 index 0000000000..8b0df3d487 --- /dev/null +++ b/src/library/scala/io/BytePickle.scala @@ -0,0 +1,314 @@ +package scala.io + +import scala.collection.mutable.{HashMap,ArrayBuffer} +import scala.tools.util.UTF8Codec + +/** + Pickler combinators. + Based on a Haskell library by Andrew Kennedy, see http://research.microsoft.com/~akenn/fun/index.html. + + Author: Philipp Haller <philipp.haller@epfl.ch> + */ + +object BytePickle { + abstract class SPU[t] { + def appP(a: t, state: PicklerState): PicklerState; + def appU(state: UnPicklerState): Pair[t, UnPicklerState]; + } + + def pickle[t](p: SPU[t], a: t): Array[byte] = + p.appP(a, new PicklerState(new Array[byte](0), new PicklerEnv)).stream; + + def unpickle[t](p: SPU[t], stream: Array[byte]): t = + p.appU(new UnPicklerState(stream, new UnPicklerEnv))._1; + + abstract class PU[t] { + def appP(a: t, state: Array[byte]): Array[byte]; + def appU(state: Array[byte]): Pair[t, Array[byte]]; + } + + def upickle[t](p: PU[t], a: t): Array[byte] = + p.appP(a, new Array[byte](0)); + + def uunpickle[t](p: PU[t], stream: Array[byte]): t = + p.appU(stream)._1; + + class PicklerEnv extends HashMap[Any, int] { + private var cnt: int = 64; + def nextLoc() = { cnt = cnt + 1; cnt }; + } + + class UnPicklerEnv extends HashMap[int, Any] { + private var cnt: int = 64; + def nextLoc() = { cnt = cnt + 1; cnt }; + } + + class PicklerState(val stream: Array[byte], val dict: PicklerEnv) {} + class UnPicklerState(val stream: Array[byte], val dict: UnPicklerEnv) {} + + abstract class RefDef; + case class Ref() extends RefDef; + case class Def() extends RefDef; + + def refDef: PU[RefDef] = new PU[RefDef] { + def appP(b: RefDef, s: Array[byte]): Array[byte] = + b match { + case Ref() => Array.concat(s, (List[byte](0)).toArray) + case Def() => Array.concat(s, (List[byte](1)).toArray) + }; + def appU(s: Array[byte]): Pair[RefDef, Array[byte]] = + if (s(0) == 0) Pair(Ref(), s.subArray(1, s.length)) + else Pair(Def(), s.subArray(1, s.length)); + } + + val REF = 0 + val DEF = 1 + + def unat: PU[int] = new PU[int] { + def appP(n: int, s: Array[byte]): Array[byte] = + Array.concat(s, nat2Bytes(n)); + def appU(s: Array[byte]): Pair[int, Array[byte]] = { + var num = 0 + def readNat: int = { + var b = 0; + var x = 0; + do { + b = s(num) + num = num + 1 + x = (x << 7) + (b & 0x7f); + } while ((b & 0x80) != 0); + x + } + Pair(readNat, s.subArray(num, s.length)) + } + } + + def share[a](pa: SPU[a]): SPU[a] = new SPU[a] { + def appP(v: a, state: PicklerState): PicklerState = { + /* + - is there some value equal to v associated with a location l in the pickle environment? + - yes: write REF-tag to outstream together with l + - no: + write DEF-tag to outstream + record current location l of outstream + --> serialize value + add entry to pickle environment, mapping v onto l + */ + val pe = state.dict + pe.get(v) match { + case None => + //Console.println("" + v + " is new") + //Console.println("writing DEF...") + val sPrime = refDef.appP(Def(), state.stream) + val l = pe.nextLoc() + + //Console.println("applying pickler to state " + sPrime) + val sPrimePrime = pa.appP(v, new PicklerState(sPrime, pe)) + + //Console.println("updating dict (" + l + ") for " + v) + pe.update(v, l) + + return sPrimePrime + case Some(l) => + //Console.println("writing REF...") + val sPrime = refDef.appP(Ref(), state.stream) + + //Console.println("writing location to state " + sPrime) + return new PicklerState(unat.appP(l, sPrime), pe) + } + } + def appU(state: UnPicklerState): Pair[a, UnPicklerState] = { + /* + - first, read tag (i.e. DEF or REF) + - if REF: + read location l + look up resulting value in unpickler environment + - if DEF: + record location l of input stream + --> deserialize value v with argument deserializer + add entry to unpickler environment, mapping l onto v + */ + val upe = state.dict + val res = refDef.appU(state.stream) + res._1 match { + case Def() => + val l = upe.nextLoc + val res2 = pa.appU(new UnPicklerState(res._2, upe)) + upe.update(l, res2._1) + return res2 + case Ref() => + val res2 = unat.appU(res._2) // read location + upe.get(res2._1) match { // lookup value in unpickler env + case None => error("invalid unpickler environment"); return null + case Some(v) => return Pair(v.asInstanceOf[a], new UnPicklerState(res2._2, upe)) + } + } + } + } + + def ulift[t](x: t): PU[t] = new PU[t] { + def appP(a: t, state: Array[byte]): Array[byte] = + if (x != a) { error("value to be pickled (" + a + ") != " + x); state } + else state; + def appU(state: Array[byte]) = Pair(x, state); + } + + def lift[t](x: t): SPU[t] = new SPU[t] { + def appP(a: t, state: PicklerState): PicklerState = + if (x != a) { /*error("value to be pickled (" + a + ") != " + x);*/ state } + else state; + def appU(state: UnPicklerState) = Pair(x, state); + } + + def usequ[t,u](f: u => t, pa: PU[t], k: t => PU[u]): PU[u] = new PU[u] { + def appP(b: u, s: Array[byte]): Array[byte] = { + val a = f(b) + val sPrime = pa.appP(a, s) + val pb = k(a) + val sPrimePrime = pb.appP(b, sPrime) + sPrimePrime + } + def appU(s: Array[byte]): Pair[u, Array[byte]] = { + val resPa = pa.appU(s) + val a = resPa._1 + val sPrime = resPa._2 + val pb = k(a) + pb.appU(sPrime) + } + } + + def sequ[t,u](f: u => t, pa: SPU[t], k: t => SPU[u]): SPU[u] = new SPU[u] { + def appP(b: u, s: PicklerState): PicklerState = { + val a = f(b) + //Console.println("pickling " + a + ", s: " + s.stream) + val sPrime = pa.appP(a, s) + val pb = k(a) + //Console.println("pickling " + b + ", s: " + s.stream) + pb.appP(b, sPrime) + } + def appU(s: UnPicklerState): Pair[u, UnPicklerState] = { + val resPa = pa.appU(s) + val a = resPa._1 + val sPrime = resPa._2 + val pb = k(a) + pb.appU(sPrime) + } + } + + def upair[a,b](pa: PU[a], pb: PU[b]): PU[Pair[a,b]] = { + def fst(p: Pair[a,b]): a = p._1; + def snd(p: Pair[a,b]): b = p._2; + usequ(fst, pa, (x: a) => usequ(snd, pb, (y: b) => ulift(Pair(x, y)))) + } + + def pair[a,b](pa: SPU[a], pb: SPU[b]): SPU[Pair[a,b]] = { + def fst(p: Pair[a,b]): a = p._1; + def snd(p: Pair[a,b]): b = p._2; + sequ(fst, pa, (x: a) => sequ(snd, pb, (y: b) => lift(Pair(x, y)))) + } + + def triple[a,b,c](pa: SPU[a], pb: SPU[b], pc: SPU[c]): SPU[Triple[a,b,c]] = { + def fst(p: Triple[a,b,c]): a = p._1; + def snd(p: Triple[a,b,c]): b = p._2; + def trd(p: Triple[a,b,c]): c = p._3; + + sequ(fst, pa, + (x: a) => sequ(snd, pb, + (y: b) => sequ(trd, pc, + (z: c) => lift(Triple(x, y, z))))) + } + + def uwrap[a,b](i: a => b, j: b => a, pa: PU[a]): PU[b] = + usequ(j, pa, (x: a) => ulift(i(x))); + + def wrap[a,b](i: a => b, j: b => a, pa: SPU[a]): SPU[b] = + sequ(j, pa, (x: a) => lift(i(x))); + + def appendByte(a: Array[byte], b: int): Array[byte] = { + Array.concat(a, (List[byte](b.asInstanceOf[byte])).toArray) + } + + def nat2Bytes(x: int): Array[byte] = { + val buf = new ArrayBuffer[byte] + def writeNatPrefix(x: int): unit = { + val y = x >>> 7; + if (y != 0) writeNatPrefix(y); + buf += ((x & 0x7f) | 0x80).asInstanceOf[byte]; + } + val y = x >>> 7; + if (y != 0) writeNatPrefix(y); + buf += (x & 0x7f).asInstanceOf[byte]; + buf.toArray + } + + def nat: SPU[int] = new SPU[int] { + def appP(n: int, s: PicklerState): PicklerState = { + new PicklerState(Array.concat(s.stream, nat2Bytes(n)), s.dict); + } + def appU(s: UnPicklerState): Pair[int,UnPicklerState] = { + var num = 0 + def readNat: int = { + var b = 0; + var x = 0; + do { + b = s.stream(num) + num = num + 1 + x = (x << 7) + (b & 0x7f); + } while ((b & 0x80) != 0); + x + } + Pair(readNat, new UnPicklerState(s.stream.subArray(num, s.stream.length), s.dict)) + } + } + + def byte: SPU[byte] = new SPU[byte] { + def appP(b: byte, s: PicklerState): PicklerState = + new PicklerState(Array.concat(s.stream, (List[byte](b)).toArray), s.dict); + def appU(s: UnPicklerState): Pair[byte, UnPicklerState] = + Pair(s.stream(0), new UnPicklerState(s.stream.subArray(1, s.stream.length), s.dict)); + } + + def string: SPU[String] = + share(wrap((a:Array[byte]) => UTF8Codec.decode(a, 0, a.length), (s:String) => UTF8Codec.encode(s), bytearray)); + + def bytearray: SPU[Array[byte]] = { + wrap((l:List[byte]) => l.toArray, .toList, list(byte)) + } + + def bool: SPU[boolean] = { + def toEnum(b: boolean) = if (b) 1 else 0; + def fromEnum(n: int) = if (n == 0) false else true; + wrap(fromEnum, toEnum, nat) + } + + def ufixedList[a](pa: PU[a])(n: int): PU[List[a]] = { + def pairToList(p: Pair[a,List[a]]): List[a] = + p._1 :: p._2; + def listToPair(l: List[a]): Pair[a,List[a]] = + l match { case x :: xs => Pair(x, xs) } + + if (n == 0) ulift(Nil) + else + uwrap(pairToList, listToPair, upair(pa, ufixedList(pa)(n-1))) + } + + def fixedList[a](pa: SPU[a])(n: int): SPU[List[a]] = { + def pairToList(p: Pair[a,List[a]]): List[a] = + p._1 :: p._2; + def listToPair(l: List[a]): Pair[a,List[a]] = + l match { case x :: xs => Pair(x, xs) } + + if (n == 0) lift(Nil) + else + wrap(pairToList, listToPair, pair(pa, fixedList(pa)(n-1))) + } + + def list[a](pa: SPU[a]): SPU[List[a]] = + sequ((l: List[a])=>l.length, nat, fixedList(pa)); + + def ulist[a](pa: PU[a]): PU[List[a]] = + usequ((l:List[a]) => l.length, unat, ufixedList(pa)); + + def data[a](tag: a => int, ps: List[()=>SPU[a]]): SPU[a] = + sequ(tag, nat, (x: int)=> ps.apply(x)()); +} |