Added util.matching package that contains extra...

Added util.matching package that contains extractors for regex and bit
fields.

9 files changed, 573 insertions, 0 deletions

diff --git a/src/library/scala/util/matching/BitField.scala b/src/library/scala/util/matching/BitField.scala
new file mode 100644
index 0000000000..c7ec063803
--- /dev/null
+++ b/src/library/scala/util/matching/BitField.scala
@@ -0,0 +1,138 @@
+package util.matching
+
+import scala.collection.immutable._
+
+/** This class provides methods for creating and using BitFields.
+ *  BitFields can easily parse binary data.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 22/12/2007
+ *
+ *  @param fields the list of pair of name and size for each field.
+ */
+class BitField(fields: List[Product2[String, TaintedInt]]) extends FixedBitField {
+  /** Create a BitField
+   *  @param vf pair of name and size for each field.
+   */
+  def this(vf: Product2[String, TaintedInt]*) = this(vf.toList)
+
+  /* Get the position of the first variable-size field */
+  val f = fields.zip(fields.indices) find {p => p._1.isInstanceOf[DelayedPair[_, _]]}
+  val varPos = if (f.isDefined) f.get._2 else fields.size
+
+  /* Split the fixed part and the variable part of fields */
+  val fixedFields = fields.slice(0, varPos)
+  val variableFields = fields.slice(varPos, fields.size)
+
+  /* Create a BitField for the fixed part */
+  val fixedPart = new FixedBitField(fixedFields.map(p => Pair(p._1, p._2.toInt)))
+
+  /** Helper that parses binary data into a MatchData object */
+  private def unapplySeq0(input: Array[Byte]): MatchData[BigInt] = {
+    /* Extract the fixed length and the variable length part of the input */
+    val max = Math.min(fixedPart.size / 8, input.size)
+    val finput = input.subArray(0, max)
+    val vinput = input.subArray(max, input.size)
+
+    /* Parse the fixed length part */
+    val fresult = fixedPart.parse(finput)
+    BitField.setRes(fresult)
+
+    if (varPos == fields.size)
+      fresult
+    else {
+      /* Parse the variable length part */
+      val variablePart = setVariableFields
+      val vresult = variablePart.parse(vinput)
+      new MatchData[BigInt](BigInt(input) :: vresult.getGroups.tail ::: fresult.getGroups.tail,
+                            fresult.getNames ++ vresult.getNames)
+    }
+  }
+
+  /** Performs the matching.
+   *
+   *  @param  a the array to match
+   *  @return   the contents of each field
+   */
+  override def parse(a: Array[Byte]): MatchData[BigInt] = unapplySeq0(a)
+
+  /** Matches an array of bytes or a MatchData[BigInt] instance.
+   *
+   *  @param target  the value to be matched. Has to be an Array[Byte]
+   *                 or an MatchData[BigInt] instance.
+   *  @return        the contents of the fields.
+   */
+  override def unapplySeq(target: Any): Option[List[BigInt]] = {
+    if (target.isInstanceOf[Array[Byte]])
+      Some(unapplySeq0(target.asInstanceOf[Array[Byte]]).getGroups.tail.reverse)
+    else if (target.isInstanceOf[MatchData[_]])
+      Some(unapplySeq0(target.asInstanceOf[MatchData[BigInt]]().toByteArray).getGroups.tail.reverse)
+    else
+      None
+  }
+
+  /** This operator is used in for-comprehensions to iterate over matches.
+   *
+   * @param  a the data to match
+   * @return   the result of the matching
+   */
+  override def ~~ (a: Array[Byte]) = split(a)
+
+  /* Helper that splits up binary data and matches each block one by one */
+  private def split(input: Array[Byte]): List[MatchData[BigInt]] = {
+    def split0(res: List[Array[Byte]], in: Array[Byte]): List[Array[Byte]] = {
+      val fin = input.subArray(0, fixedPart.size / 8)
+      val fres = fixedPart.parse(fin)
+      BitField.setRes(fres)
+      val vp = setVariableFields
+      val totalSize = (vp.size + fixedPart.size) / 8
+      if (in.length <= totalSize)
+        in :: res
+      else
+        split0(in.slice(0, totalSize) :: res, in.slice(totalSize, in.length))
+    }
+    split0(Nil, input).reverse map {a => unapplySeq0(a)}
+  }
+
+  /* Returns a FixedBitField that represents the variable-size fields */
+  private def setVariableFields: FixedBitField = {
+    var fieldsSize: List[(String, Int)] = Nil
+    variableFields.reverse foreach { e => fieldsSize = (e._1, e._2.toInt) :: fieldsSize }
+    new FixedBitField(fieldsSize)
+  }
+}
+
+/** Contains implicit conversions and helper functions */
+object BitField {
+  val fresult = new ThreadLocal[MatchData[BigInt]]
+
+  private def setRes(fresult: MatchData[BigInt]) = this.fresult.set(fresult)
+
+  /** Use this function to reference the contents of a field previously defined when
+   *  defining the size of the current field.
+   *
+   *  @param label the name of field
+   *  @return      the contents of the field when matching
+   */
+  def field(label: String): TaintedInt = {
+    new TaintedInt(fresult.get.asInstanceOf[MatchData[BigInt]].apply(label).intValue)
+  }
+
+  /** Creates a new BitField
+   *
+   *  @param  vf (name, size) pairs for each field
+   *  @return    the new BitField instance.
+   */
+  def apply(vf: Product2[String, TaintedInt]*) = new BitField(vf.toList)
+
+  implicit def int2TaintedInt(x: Int): TaintedInt = new TaintedInt(x)
+
+  implicit def any2DArrowAssoc[A](x: A): DArrowAssoc[A] = new DArrowAssoc(x)
+
+  implicit def IntToMatchableInt(s: Array[Byte]): MatchableBigInt = new MatchableBigInt(s)
+
+  implicit def IntoptionToBoolean(o: Option[MatchData[BigInt]]): Boolean = o match {
+    case None => false
+    case Some(_) => true
+  }
+}
diff --git a/src/library/scala/util/matching/DArrowAssoc.scala b/src/library/scala/util/matching/DArrowAssoc.scala
new file mode 100644
index 0000000000..187f6f98c6
--- /dev/null
+++ b/src/library/scala/util/matching/DArrowAssoc.scala
@@ -0,0 +1,29 @@
+package util.matching
+
+/** Only used by BitFields. This class is similar to ArrowAssoc.
+ *  It defines the --> function that creates a pair if the
+ *  argument is an Int and a DelayedPair if it is a TaintedInt.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 15/12/2007
+ */
+private[matching] class DArrowAssoc[A](x: A) {
+
+  /** Creates a DelayedPair
+   *
+   *  @param  y the TaintedInt
+   *  @return   the DelayedPair
+   */
+  def --> (y: => TaintedInt): DelayedPair[A, TaintedInt] = {
+    new DelayedPair(x, () => y)
+  }
+
+  /** Creates a pair
+   *
+   *  @param  y the Int
+   *  @return   the pair
+   */
+  def --> (y: Int): Product2[A, TaintedInt] = {
+    (x, new TaintedInt(y))
+  }
+}
diff --git a/src/library/scala/util/matching/DelayedPair.scala b/src/library/scala/util/matching/DelayedPair.scala
new file mode 100644
index 0000000000..95b9df8285
--- /dev/null
+++ b/src/library/scala/util/matching/DelayedPair.scala
@@ -0,0 +1,15 @@
+package util.matching
+
+/** A DelayedPair is similar to a pair, except that the second
+ *  argument is delayed.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 15/12/2007
+ *
+ *  @param a the first element
+ *  @param b the second element
+ */
+class DelayedPair[A, B](a: A, b: () => B) extends Product2[A, B] {
+  override def _1: A = a
+  override def _2: B = b()
+}
diff --git a/src/library/scala/util/matching/FixedBitField.scala b/src/library/scala/util/matching/FixedBitField.scala
new file mode 100644
index 0000000000..86200e04de
--- /dev/null
+++ b/src/library/scala/util/matching/FixedBitField.scala
@@ -0,0 +1,87 @@
+package util.matching
+
+/** This class provides methods for creating and using FixedBitFields.
+ *  If you have variable size fields, see @see BitField.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 3/1/2008
+ *
+ *  @param f the list of (name, size) pairs
+ */
+class FixedBitField(f: List[Product2[String, Int]]) {
+
+  /** Create a new FixedBitField.
+   *
+   *  @param groups the sequence of (name, size) pairs
+   */
+  def this(groups: (String, Int)*) = this(groups.toList)
+
+  val fields = f.reverse
+
+  val size = fields.foldLeft(0)((s, p) => s + p._2)
+
+  // works around compiler bug (TODO: which one?)
+  val t = (fields.zip(fields.indices)) map {p => (p._1._1, p._2 + 1)}
+  val groupNames = Map() ++ t
+
+  /** Performs the matching using masks */
+  private def buildSeq(res: List[BigInt], a: BigInt, i: int, j: int): List[BigInt] = {
+    if (i < 0)
+      res
+    else {
+      var mask = BigInt(0)
+      for (k <- List.range(1, fields(i)._2 + 1))
+        mask = mask.setBit(j-k)
+      buildSeq(((a & mask) >> (j - fields(i)._2))::res, a, i - 1, j - fields(i)._2)
+    }
+  }
+
+  /** Match an Array[Byte] or an MatchData[BigInt] instance.
+   *
+   *  @param target the value to be matched. Has to be an Array[Byte]
+   *                or a MatchData[BigInt] instance
+   *  @return       the field contents
+   */
+  def unapplySeq(target: Any): Option[List[BigInt]] = {
+    if (target.isInstanceOf[Array[Byte]])
+      Some(buildSeq(Nil, BigInt(target.asInstanceOf[Array[Byte]]), fields.size - 1, size))
+    else if (target.isInstanceOf[MatchData[_]])
+      Some(buildSeq(Nil, target.asInstanceOf[MatchData[BigInt]](), fields.size - 1, size).reverse)
+    else
+      None
+  }
+
+  /** This operator is used in for-comprehension to iterate over matches.
+   *
+   * @param  a the data to be matched
+   * @return   the result of the matching
+   */
+  def ~~ (a: Array[Byte]) = split(a)
+
+  /* Builds a MatchData object from the raw matching results */
+  private def splitOne(n: BigInt) = {
+    new MatchData(n::buildSeq(Nil, n, fields.size - 1, size), groupNames)
+  }
+
+  /** Performs the matching.
+   *
+   *  @param  the array to be matched
+   *  @return the contents of each field
+   */
+  def parse(a: Array[Byte]): MatchData[BigInt] = splitOne(BigInt(a))
+
+  /** Matches and consumes the same input iteratively */
+  private def split(input: Array[Byte]): List[MatchData[BigInt]] = {
+    def split0(res: List[BigInt], in: Array[Byte]): List[BigInt] = {
+      val bSize = size / 8
+      if (in.length <= bSize)
+        BigInt(in) :: res
+      else {
+        val x = in.slice(0, bSize)
+        val xs = in.slice(bSize, in.length)
+        split0(BigInt(x) :: res, xs)
+      }
+    }
+    split0(Nil, input).reverse map {n => splitOne(n)}
+  }
+}
diff --git a/src/library/scala/util/matching/MatchData.scala b/src/library/scala/util/matching/MatchData.scala
new file mode 100644
index 0000000000..3131aec48f
--- /dev/null
+++ b/src/library/scala/util/matching/MatchData.scala
@@ -0,0 +1,53 @@
+package util.matching
+
+/** This class provides methods to access
+ *  the contents of capture groups.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.1, 29/01/2008
+ */
+class MatchData[A](groups: List[A], groupNames: Map[String, Int]) {
+  def this(groups: List[A]) = this(groups, null)
+
+  /** Returns the i-th group
+   *  @param id The group number
+   *  @return   The i-th group
+   */
+  def apply(id: Int): A = groups(id)
+
+  /** Returns the whole match
+   */
+  def apply(): A = groups(0)
+
+  /** Returns the requested group
+   *
+   *  @param id The group name
+   *  @return   The requested group
+   *  @throws   <code>NoSuchElementException</code> if the requested
+   *            group name is not defined
+   */
+  def apply(id: String): A =
+    if (groupNames == null)
+      throw new NoSuchElementException("no group names defined")
+    else {
+      val index = groupNames.get(id)
+      if (index == None)
+        throw new NoSuchElementException("group name "+id+" not defined")
+      else
+        apply(index.get)
+    }
+
+  /** Returns the list of groups
+   *
+   *  @return The groups
+   */
+  def getGroups: List[A] = groups
+
+  /** Returns the list of group names
+   *
+   *  @return The names
+   */
+  def getNames = groupNames
+
+  override def toString(): String = groups(0).toString
+}
diff --git a/src/library/scala/util/matching/MatchableInt.scala b/src/library/scala/util/matching/MatchableInt.scala
new file mode 100644
index 0000000000..3c89e45e36
--- /dev/null
+++ b/src/library/scala/util/matching/MatchableInt.scala
@@ -0,0 +1,18 @@
+package util.matching
+
+/** This class provides methods to do matching with
+ *  BitFields.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 12/12/2007
+ */
+private[matching] class MatchableBigInt(a: Array[Byte]) {
+
+  /** Returns the first match of this array of Byte with the
+   *  provided BitField.
+   *
+   * @param f the BitField
+   * @return  the first match
+   */
+  def =~ (f: FixedBitField): Option[MatchData[BigInt]] = Some(f.parse(a))
+}
diff --git a/src/library/scala/util/matching/MatchableString.scala b/src/library/scala/util/matching/MatchableString.scala
new file mode 100644
index 0000000000..9c011a12d3
--- /dev/null
+++ b/src/library/scala/util/matching/MatchableString.scala
@@ -0,0 +1,17 @@
+package util.matching
+
+/** This class provides an implicit conversion that allows
+ *  using the matching operator <code>=~</code> on strings.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 15/11/2007
+ */
+class MatchableString(s: String) {
+  /** Returns the first match of this string with the
+   *  provided regular expression.
+   *
+   *  @param regex the regular expression
+   *  @return      the first match
+   */
+  def =~ (regex: Regex): Option[MatchData[String]] = regex.matchFirst(s)
+}
diff --git a/src/library/scala/util/matching/Regex.scala b/src/library/scala/util/matching/Regex.scala
new file mode 100644
index 0000000000..adc98a0991
--- /dev/null
+++ b/src/library/scala/util/matching/Regex.scala
@@ -0,0 +1,169 @@
+package util.matching
+
+import java.util.regex.{Pattern, Matcher}
+
+/** This class provides methods for creating and using regular expressions.
+ *  It is based on the regular expressions of the JDK since 1.4.
+ *
+ *  @author  Thibaud Hottelier
+ *  @author  Philipp Haller
+ *  @version 1.1, 29/01/2008
+ *
+ *  @param regex      A string representing a regular expression
+ *  @param groupNames A mapping from names to indices in capture groups
+ */
+class Regex(regex: String, private var groupNames: Map[String, Int]) {
+  private def buildMap(res: Map[String, Int], groupNames: Seq[String], i: Int): Map[String, Int] =
+    if (i > groupNames.size)
+      res
+    else {
+      val p = (groupNames(i - 1), i)
+      buildMap(res + p, groupNames, i + 1)
+    }
+
+  /** Create a <code>Regex</code> from a string.
+   *
+   *  @param s The regular expression
+   *  @return  A new <code>Regex</code> instance
+   */
+  def this(s: String) = this(s, null: Map[String, Int])
+
+  /** Create a <code>Regex</code> from a string and
+   *  a sequence of group names.
+   *
+   *  @param s      The regular expression
+   *  @param groups The list of group names in the same order
+   *                as the capture groups in the regular expression
+   *  @return       A new <code>Regex</code> instance
+   */
+  def this(s: String, groups: String*) = {
+    this(s)
+    groupNames = buildMap(Map[String, Int](), groups, 1)
+  }
+
+  /* Store the compiled pattern at instantiation time */
+  private val pattern = Pattern.compile(regex)
+
+  /* Builds a MatchData[String] from a Matcher */
+  private def buildSeq(l: List[String], m: Matcher, i: Int): MatchData[String] =
+    if (i == -1)
+      new MatchData(l, groupNames)
+    else
+      buildSeq(m.group(i) :: l, m, i - 1)
+
+  /* Builds a List[MatchData[String]] from a Matcher */
+  private def doMatchAll(res: List[MatchData[String]], m: Matcher): List[MatchData[String]] =
+    if (m.find())
+      doMatchAll(res ::: List(buildSeq(Nil, m, m.groupCount())), m)
+    else
+      res
+
+  /* Builds a List[String] from a Matcher */
+  private def unapplySeq0(target: String): Option[List[String]] = {
+    val m = pattern.matcher(target)
+    if (m.matches())
+      Some(buildSeq(Nil, m, m.groupCount()).getGroups.tail)
+    else
+      None
+  }
+
+  /** Tries to match target (whole match) and returns
+   *  the matches.
+   *
+   *  @param target The string to match
+   *  @return       The matches
+   */
+  def unapplySeq(target: Any): Option[List[String]] =
+    if (target.isInstanceOf[String])
+      unapplySeq0(target.asInstanceOf[String])
+    else if (target.isInstanceOf[MatchData[_]])
+      unapplySeq0(target.asInstanceOf[MatchData[String]]())
+    else
+      None
+
+  /** Creates a <code>MatchData[String]</code> from a string.
+   *  This is used in for-comprehensions to iterate over matches.
+   *
+   *  @param s The string to match
+   *  @return  The MatchData[String] instance
+   */
+  def ~~(s: String) = matchAll(s)
+
+  /** Returns all matches of target string.
+   *
+   *  @param target The string to match
+   *  @return       All matches in a list of <code>MatchData[String]</code>
+   */
+  def matchAll(target: String): List[MatchData[String]] = {
+    val m = pattern.matcher(target)
+    doMatchAll(Nil, m)
+  }
+
+  /** Returns the first match of target string.
+   *
+   *  @param target The string to match
+   *  @return       The first match as <code>MatchData[String]</code>
+   */
+  def matchFirst(target: String): Option[MatchData[String]] = {
+    val m = pattern.matcher(target)
+    if (!m.find())
+      None
+    else
+      Some(buildSeq(Nil, m, m.groupCount()))
+  }
+
+  /** Replaces all matches by a string.
+   *
+   *  @param target      The string to match
+   *  @param replacement The string that will replace each match
+   *  @return            The resulting string
+   */
+  def replaceAll(target: String, replacement: String): String = {
+    val m = pattern.matcher(target)
+    m.replaceAll(replacement)
+  }
+
+  /** Replaces the first match by a string.
+   *
+   *  @param target      The string to match
+   *  @param replacement The string that will replace the match
+   *  @return            The resulting string
+   */
+  def replaceFirst(target: String, replacement: String): String = {
+    val m = pattern.matcher(target)
+    m.replaceFirst(replacement)
+  }
+
+  /** Returns true if the whole string matches.
+   *
+   *  @param target The string to match
+   *  @return       <code>true</code> iff the whole string matches
+   */
+  def matchesAll(target: String): Boolean = {
+    val m = pattern.matcher(target)
+    m.find()
+  }
+
+  /** Returns <code>true</code> iff the string or one of its substrings match.
+   *
+   *  @param target The string to match
+   *  @return       <code>true</code> iff the string matches
+   */
+  def matches(target: String): Boolean = {
+    val m = pattern.matcher(target)
+    m.matches()
+  }
+}
+
+/** Provides implicit conversions for regular expressions.
+ */
+object Regex {
+  /** Promotes a string to <code>MatchableString</code> so that <code>=~</code> can be used */
+  implicit def stringToMatchableString(s: String) = new MatchableString(s)
+
+  /** Allows treating an <code>Option</code> as a Boolean. */
+  implicit def optionToBoolean(o: Option[MatchData[String]]) = o.isDefined
+
+  /** Promotes a string to a <code>Regex</code>. */
+  implicit def stringToRegex(s: String) = new Regex(s)
+}
diff --git a/src/library/scala/util/matching/TaintedInt.scala b/src/library/scala/util/matching/TaintedInt.scala
new file mode 100644
index 0000000000..0858ff9b03
--- /dev/null
+++ b/src/library/scala/util/matching/TaintedInt.scala
@@ -0,0 +1,47 @@
+package util.matching
+
+/** This is a wrapper around integer. Used only by BitFields,
+ *  it makes it possible to differentiate fixed-size fields from
+ *  variable-size ones.
+ *
+ *  @author  Thibaud Hottelier
+ *  @version 1.0, 15/12/2007
+ *
+ *  @param x the wrapped integer
+ */
+private[matching] class TaintedInt(x: Int) {
+
+  /** Converts to Int
+   *
+   *  @return The wrapped integer
+   */
+  def toInt = x
+
+  /** Adds two TaintedInts
+   *
+   *  @param  y The second operand
+   *  @return   The sum
+   */
+  def + (y: TaintedInt) = new TaintedInt(x + y.toInt)
+
+  /** Subtracts two TaintedInts
+   *
+   *  @param  y The second operand
+   *  @return   The difference
+   */
+  def - (y: TaintedInt) = new TaintedInt(x - y.toInt)
+
+  /** Multiplies two TaintedInts
+   *
+   *  @param  y The second operand
+   *  @return   The product
+   */
+  def * (y: TaintedInt) = new TaintedInt(x * y.toInt)
+
+  /** Divides two TaintedInts
+   *
+   *  @param  y The second operand
+   *  @return   The quotient
+   */
+  def / (y: TaintedInt) = new TaintedInt(x / y.toInt)
+}