From 335da67693fb03f384b8d10dbba795de255ad3b3 Mon Sep 17 00:00:00 2001 From: "Daniel C. Sobral" Date: Thu, 1 Dec 2011 16:56:32 -0200 Subject: Example in scala.sys.process didn't match the text that describes it. Fixed. --- src/library/scala/sys/process/package.scala | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/library/scala/sys/process/package.scala b/src/library/scala/sys/process/package.scala index 17636c4c87..3eb0e5bb89 100644 --- a/src/library/scala/sys/process/package.scala +++ b/src/library/scala/sys/process/package.scala @@ -47,8 +47,9 @@ package scala.sys { * * {{{ * import java.io.File + * import java.net.URL * import scala.sys.process._ - * new File("About.html") #> new File("About_copy.html") ! + * new URL("http://www.scala-lang.org/") #> new File("scala-lang.html") ! * }}} * * One may use a `Process` directly through `ProcessBuilder`'s `run` method, which starts the process in -- cgit v1.2.3 From e21c0581937c7fb6dc995e3c9f62c278db88ae64 Mon Sep 17 00:00:00 2001 From: "Daniel C. Sobral" Date: Fri, 14 Oct 2011 18:01:32 -0300 Subject: Fix typo on Regex documentation. --- src/library/scala/util/matching/Regex.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/library/scala/util/matching/Regex.scala b/src/library/scala/util/matching/Regex.scala index 28ba226324..ca97515e23 100644 --- a/src/library/scala/util/matching/Regex.scala +++ b/src/library/scala/util/matching/Regex.scala @@ -104,7 +104,7 @@ import java.util.regex.{ Pattern, Matcher } * } * }}} * - * The are also methods that can be used to replace the patterns + * There are also methods that can be used to replace the patterns * on a text. The substitutions can be simple replacements, or more * complex functions. For example: * -- cgit v1.2.3 From 5d7da746b083a5fb436550c56ebd811fe024c315 Mon Sep 17 00:00:00 2001 From: "Daniel C. Sobral" Date: Thu, 1 Dec 2011 17:30:50 -0200 Subject: Re-enable RedBlack's ScalaCheck test, which was disabled at r21829. I haven't been able to find any reason for that reversal, but this version is an improved version provided with SI-3796, which never got committed along with the patch. This version generates trees directly instead of using the methods under test. It also puts an upper bound on tree size and, therefore, execution time. --- test/disabled/scalacheck/redblack.scala | 157 ----------------------- test/files/scalacheck/redblack.scala | 213 ++++++++++++++++++++++++++++++++ 2 files changed, 213 insertions(+), 157 deletions(-) delete mode 100644 test/disabled/scalacheck/redblack.scala create mode 100644 test/files/scalacheck/redblack.scala diff --git a/test/disabled/scalacheck/redblack.scala b/test/disabled/scalacheck/redblack.scala deleted file mode 100644 index 0334c1218d..0000000000 --- a/test/disabled/scalacheck/redblack.scala +++ /dev/null @@ -1,157 +0,0 @@ -import org.scalacheck._ -import Prop._ -import Gen._ - -/* -Properties of a Red & Black Tree: - -A node is either red or black. -The root is black. (This rule is used in some definitions and not others. Since the -root can always be changed from red to black but not necessarily vice-versa this -rule has little effect on analysis.) -All leaves are black. -Both children of every red node are black. -Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. -*/ - -abstract class RedBlackTest extends Properties("RedBlack") { - object RedBlackTest extends scala.collection.immutable.RedBlack[Int] { - def isSmaller(x: Int, y: Int) = x < y - } - - import RedBlackTest._ - - def rootIsBlack[A](t: Tree[A]) = t.isBlack - - def areAllLeavesBlack[A](t: Tree[A]): Boolean = t match { - case Empty => t.isBlack - case ne: NonEmpty[_] => List(ne.left, ne.right) forall areAllLeavesBlack - } - - def areRedNodeChildrenBlack[A](t: Tree[A]): Boolean = t match { - case RedTree(_, _, left, right) => List(left, right) forall (t => t.isBlack && areRedNodeChildrenBlack(t)) - case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack - case Empty => true - } - - def blackNodesToLeaves[A](t: Tree[A]): List[Int] = t match { - case Empty => List(1) - case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1) - case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves - } - - def areBlackNodesToLeavesEqual[A](t: Tree[A]): Boolean = t match { - case Empty => true - case ne: NonEmpty[_] => - ( - blackNodesToLeaves(ne).removeDuplicates.size == 1 - && areBlackNodesToLeavesEqual(ne.left) - && areBlackNodesToLeavesEqual(ne.right) - ) - } - - def orderIsPreserved[A](t: Tree[A]): Boolean = t match { - case Empty => true - case ne: NonEmpty[_] => - ( - (ne.left.iterator map (_._1) forall (isSmaller(_, ne.key))) - && (ne.right.iterator map (_._1) forall (isSmaller(ne.key, _))) - && (List(ne.left, ne.right) forall orderIsPreserved) - ) - } - - def setup(l: List[Int], invariant: Tree[Unit] => Boolean): (Boolean, Tree[Unit]) - - def listNoRepetitions(size: Int) = for { - s <- Gen.choose(1, size) - l <- Gen.listOfN(size, Gen.choose(0, Int.MaxValue)) suchThat (l => l.size == l.removeDuplicates.size) - } yield l - def listFewRepetitions(size: Int) = for { - s <- Gen.choose(1, size) - l <- Gen.listOfN(s, Gen.choose(0, size * 4)) suchThat (l => l.size != l.removeDuplicates.size) - } yield l - def listManyRepetitions(size: Int) = for { - s <- Gen.choose(1, size) - l <- Gen.listOfN(s, Gen.choose(0, size)) suchThat (l => l.size != l.removeDuplicates.size) - } yield l - def listEvenRepetitions(size: Int) = listFewRepetitions(size) map (x => - scala.util.Random.shuffle(x zip x flatMap { case (a, b) => List(a, b) }) - ) - - // Arbitrarily weighted list distribution types - val seqType: Gen[Int => Gen[List[Int]]] - - def myGen(sized: Int) = for { - size <- Gen.choose(0, sized) - seq <- seqType - list <- seq(size) - } yield list - - property("root is black") = forAll(myGen(10)) { l => - setup(l, rootIsBlack)._1 :| setup(l, rootIsBlack)._2.toString - } - property("all leaves are black") = forAll(myGen(50)) { l => - setup(l, areAllLeavesBlack)._1 :| setup(l, areAllLeavesBlack)._2.toString - } - property("children of red nodes are black") = forAll(myGen(50)) { l => - setup(l, areRedNodeChildrenBlack)._1 :| setup(l, areRedNodeChildrenBlack)._2.toString - } - property("Every path from a node to its descendant leaves contains the same number of black nodes") = forAll(myGen(50)) { l => - setup(l, areBlackNodesToLeavesEqual)._1 :| setup(l, areBlackNodesToLeavesEqual)._2.toString - } - property("Ordering of keys is preserved") = forAll(myGen(50)) { l => - setup(l, orderIsPreserved)._1 :| setup(l, orderIsPreserved)._2.toString - } -} - -object TestInsertion extends RedBlackTest { - import RedBlackTest._ - override val seqType = Gen.frequency( - (1, listNoRepetitions _), - (1, listManyRepetitions _) - ) - - property("update adds elements") = forAll(myGen(50)) { l => - val tree = l.foldLeft(Empty: Tree[Unit])((acc, n) => acc update (n, ())) - forAll(Gen.pick(1, l)) ( n => !(tree lookup n.head isEmpty) :| "Tree: "+tree+" N: "+n.head ) - } - - override def setup(l: List[Int], invariant: Tree[Unit] => Boolean) = l.foldLeft((true, Empty: Tree[Unit])) { - case ((true, acc), n) => - val newRoot = acc update (n, ()) - (invariant(newRoot), newRoot) - case (failed, _) => failed - } -} - -object TestDeletion extends RedBlackTest { - import RedBlackTest._ - override val seqType = Gen.frequency( - (2, listFewRepetitions _), - (3, listManyRepetitions _), - (1, listEvenRepetitions _) - ) - - property("delete removes elements") = forAll(myGen(50)) { l => - val tree = l.foldLeft(Empty: Tree[Unit])((acc, n) => acc update (n, ())) - forAll(Gen.choose(1, l.size)) { numberOfElementsToRemove => - forAll(Gen.pick(numberOfElementsToRemove, l)) { elementsToRemove => - val newTree = elementsToRemove.foldLeft(tree)((acc, n) => acc delete n) - (elementsToRemove forall (n => newTree lookup n isEmpty)) :| "Tree: "+tree+"New Tree: "+newTree+" Elements to Remove: "+elementsToRemove - } - } - } - - override def setup(l: List[Int], invariant: Tree[Unit] => Boolean) = l.foldLeft((true, Empty: Tree[Unit])) { - case ((true, acc), n) => - val newRoot = if (acc lookup n isEmpty) acc update (n, ()) else acc delete n - (invariant(newRoot), newRoot) - case (failed, _) => failed - } -} - -object Test extends Properties("RedBlack") { - include(TestInsertion) - include(TestDeletion) -} - diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala new file mode 100644 index 0000000000..1fcaa46f0e --- /dev/null +++ b/test/files/scalacheck/redblack.scala @@ -0,0 +1,213 @@ +import org.scalacheck._ +import Prop._ +import Gen._ + +/* +Properties of a Red & Black Tree: + +A node is either red or black. +The root is black. (This rule is used in some definitions and not others. Since the +root can always be changed from red to black but not necessarily vice-versa this +rule has little effect on analysis.) +All leaves are black. +Both children of every red node are black. +Every simple path from a given node to any of its descendant leaves contains the same number of black nodes. +*/ + +abstract class RedBlackTest extends Properties("RedBlack") { + def minimumSize = 0 + def maximumSize = 5 + + object RedBlackTest extends scala.collection.immutable.RedBlack[String] { + def isSmaller(x: String, y: String) = x < y + } + + import RedBlackTest._ + + def nodeAt[A](tree: Tree[A], n: Int): Option[(String, A)] = if (n < tree.iterator.size && n >= 0) + Some(tree.iterator.drop(n).next) + else + None + + def treeContains[A](tree: Tree[A], key: String) = tree.iterator.map(_._1) contains key + + def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[Int]] = + if (level == 0) { + value(Empty) + } else { + for { + oddOrEven <- choose(0, 2) + tryRed = oddOrEven.sample.get % 2 == 0 // work around arbitrary[Boolean] bug + isRed = parentIsBlack && tryRed + nextLevel = if (isRed) level else level - 1 + left <- mkTree(nextLevel, !isRed, label + "L") + right <- mkTree(nextLevel, !isRed, label + "R") + } yield { + if (isRed) + RedTree(label + "N", 0, left, right) + else + BlackTree(label + "N", 0, left, right) + } + } + + def genTree = for { + depth <- choose(minimumSize, maximumSize + 1) + tree <- mkTree(depth) + } yield tree + + type ModifyParm + def genParm(tree: Tree[Int]): Gen[ModifyParm] + def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] + + def genInput: Gen[(Tree[Int], ModifyParm, Tree[Int])] = for { + tree <- genTree + parm <- genParm(tree) + } yield (tree, parm, modify(tree, parm)) +} + +trait RedBlackInvariants { + self: RedBlackTest => + + import RedBlackTest._ + + def rootIsBlack[A](t: Tree[A]) = t.isBlack + + def areAllLeavesBlack[A](t: Tree[A]): Boolean = t match { + case Empty => t.isBlack + case ne: NonEmpty[_] => List(ne.left, ne.right) forall areAllLeavesBlack + } + + def areRedNodeChildrenBlack[A](t: Tree[A]): Boolean = t match { + case RedTree(_, _, left, right) => List(left, right) forall (t => t.isBlack && areRedNodeChildrenBlack(t)) + case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack + case Empty => true + } + + def blackNodesToLeaves[A](t: Tree[A]): List[Int] = t match { + case Empty => List(1) + case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1) + case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves + } + + def areBlackNodesToLeavesEqual[A](t: Tree[A]): Boolean = t match { + case Empty => true + case ne: NonEmpty[_] => + ( + blackNodesToLeaves(ne).distinct.size == 1 + && areBlackNodesToLeavesEqual(ne.left) + && areBlackNodesToLeavesEqual(ne.right) + ) + } + + def orderIsPreserved[A](t: Tree[A]): Boolean = + t.iterator zip t.iterator.drop(1) forall { case (x, y) => isSmaller(x._1, y._1) } + + def setup(invariant: Tree[Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) => + invariant(newTree) + } + + property("root is black") = setup(rootIsBlack) + property("all leaves are black") = setup(areAllLeavesBlack) + property("children of red nodes are black") = setup(areRedNodeChildrenBlack) + property("black nodes are balanced") = setup(areBlackNodesToLeavesEqual) + property("ordering of keys is preserved") = setup(orderIsPreserved) +} + +object TestInsert extends RedBlackTest with RedBlackInvariants { + import RedBlackTest._ + + override type ModifyParm = Int + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size + 1) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = tree update (generateKey(tree, parm), 0) + + def generateKey(tree: Tree[Int], parm: ModifyParm): String = nodeAt(tree, parm) match { + case Some((key, _)) => key.init.mkString + "MN" + case None => nodeAt(tree, parm - 1) match { + case Some((key, _)) => key.init.mkString + "RN" + case None => "N" + } + } + + property("update adds elements") = forAll(genInput) { case (tree, parm, newTree) => + treeContains(newTree, generateKey(tree, parm)) + } +} + +object TestModify extends RedBlackTest { + import RedBlackTest._ + + def newValue = 1 + override def minimumSize = 1 + override type ModifyParm = Int + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = nodeAt(tree, parm) map { + case (key, _) => tree update (key, newValue) + } getOrElse tree + + property("update modifies values") = forAll(genInput) { case (tree, parm, newTree) => + nodeAt(tree,parm) forall { case (key, _) => + newTree.iterator contains (key, newValue) + } + } +} + +object TestDelete extends RedBlackTest with RedBlackInvariants { + import RedBlackTest._ + + override def minimumSize = 1 + override type ModifyParm = Int + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = choose(0, tree.iterator.size) + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = nodeAt(tree, parm) map { + case (key, _) => tree delete key + } getOrElse tree + + property("delete removes elements") = forAll(genInput) { case (tree, parm, newTree) => + nodeAt(tree, parm) forall { case (key, _) => + !treeContains(newTree, key) + } + } +} + +object TestRange extends RedBlackTest with RedBlackInvariants { + import RedBlackTest._ + + override type ModifyParm = (Option[Int], Option[Int]) + override def genParm(tree: Tree[Int]): Gen[ModifyParm] = for { + from <- choose(0, tree.iterator.size) + to <- choose(0, tree.iterator.size) suchThat (from <=) + optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug + optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug + } yield (optionalFrom, optionalTo) + + override def modify(tree: Tree[Int], parm: ModifyParm): Tree[Int] = { + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + tree range (from, to) + } + + property("range boundaries respected") = forAll(genInput) { case (tree, parm, newTree) => + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + ("lower boundary" |: (from forall ( key => newTree.iterator.map(_._1) forall (key <=)))) && + ("upper boundary" |: (to forall ( key => newTree.iterator.map(_._1) forall (key >)))) + } + + property("range returns all elements") = forAll(genInput) { case (tree, parm, newTree) => + val from = parm._1 flatMap (nodeAt(tree, _) map (_._1)) + val to = parm._2 flatMap (nodeAt(tree, _) map (_._1)) + val filteredTree = (tree.iterator + .map(_._1) + .filter(key => from forall (key >=)) + .filter(key => to forall (key <)) + .toList) + filteredTree == newTree.iterator.map(_._1).toList + } +} + +object Test extends Properties("RedBlack") { + include(TestInsert) + include(TestModify) + include(TestDelete) + include(TestRange) +} + -- cgit v1.2.3 From 8b8ed9980b9f35a16cd55744937e67cff02ea6f1 Mon Sep 17 00:00:00 2001 From: "Daniel C. Sobral" Date: Wed, 14 Sep 2011 18:45:48 -0300 Subject: Makes it possible to use env(1) to run scala scripts, by dropping the requirement of a !# line when using it. This is how some other languages, such as ruby, are run. Typical usage: #!/usr/bin/env scala println("Hello, "+args(0)+"!") Contributed by: Daniel C. Sobral --- src/compiler/scala/tools/nsc/util/SourceFile.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/compiler/scala/tools/nsc/util/SourceFile.scala b/src/compiler/scala/tools/nsc/util/SourceFile.scala index 22820806be..4405b3457b 100644 --- a/src/compiler/scala/tools/nsc/util/SourceFile.scala +++ b/src/compiler/scala/tools/nsc/util/SourceFile.scala @@ -72,7 +72,7 @@ object ScriptSourceFile { * with "!#" or "::!#". */ def headerLength(cs: Array[Char]): Int = { - val headerPattern = Pattern.compile("""^(::)?!#.*(\r|\n|\r\n)""", Pattern.MULTILINE) + val headerPattern = Pattern.compile("""((?m)^(::)?!#.*|^.*/env .*)(\r|\n|\r\n)""") val headerStarts = List("#!", "::#!") if (headerStarts exists (cs startsWith _)) { -- cgit v1.2.3