From 3e2f88773c61e2d0020b57161d0e901bec596c96 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sun, 28 Apr 2013 00:33:06 +0200 Subject: Scala : add patmat --- Scala/patmat/.classpath | 12 + Scala/patmat/.project | 12 + .../patmat/.settings/org.scala-ide.sdt.core.prefs | 5 + Scala/patmat/build.sbt | 110 ++++ .../lib_managed/jars/junit/junit/junit-4.10.jar | Bin 0 -> 253160 bytes .../hamcrest-core/hamcrest-core-1.1.jar | Bin 0 -> 76643 bytes .../scala-actors/scala-actors-2.10.0.jar | Bin 0 -> 451307 bytes .../scala-reflect/scala-reflect-2.10.0.jar | Bin 0 -> 3149351 bytes .../scalatest_2.10/scalatest_2.10-1.9.1.jar | Bin 0 -> 3114958 bytes .../scalatest_2.9.2/scalatest_2.9.2-1.8.jar | Bin 0 -> 3053035 bytes Scala/patmat/project/CourseraHttp.scala | 223 +++++++ Scala/patmat/project/GradingFeedback.scala | 218 +++++++ Scala/patmat/project/ProgFunBuild.scala | 646 +++++++++++++++++++++ Scala/patmat/project/RecordingLogger.scala | 35 ++ Scala/patmat/project/RichJsValue.scala | 28 + Scala/patmat/project/ScalaTestRunner.scala | 169 ++++++ Scala/patmat/project/Settings.scala | 48 ++ Scala/patmat/project/StyleChecker.scala | 77 +++ Scala/patmat/project/build.properties | 1 + Scala/patmat/project/buildSettings.sbt | 72 +++ Scala/patmat/project/project/buildPlugins.sbt | 2 + Scala/patmat/project/scalastyle_config.xml | 136 +++++ Scala/patmat/src/main/scala/common/package.scala | 40 ++ Scala/patmat/src/main/scala/patmat/Huffman.scala | 206 +++++++ .../src/test/scala/patmat/HuffmanSuite.scala | 47 ++ 25 files changed, 2087 insertions(+) create mode 100644 Scala/patmat/.classpath create mode 100644 Scala/patmat/.project create mode 100644 Scala/patmat/.settings/org.scala-ide.sdt.core.prefs create mode 100644 Scala/patmat/build.sbt create mode 100644 Scala/patmat/lib_managed/jars/junit/junit/junit-4.10.jar create mode 100644 Scala/patmat/lib_managed/jars/org.hamcrest/hamcrest-core/hamcrest-core-1.1.jar create mode 100644 Scala/patmat/lib_managed/jars/org.scala-lang/scala-actors/scala-actors-2.10.0.jar create mode 100644 Scala/patmat/lib_managed/jars/org.scala-lang/scala-reflect/scala-reflect-2.10.0.jar create mode 100644 Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.10/scalatest_2.10-1.9.1.jar create mode 100644 Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.9.2/scalatest_2.9.2-1.8.jar create mode 100644 Scala/patmat/project/CourseraHttp.scala create mode 100644 Scala/patmat/project/GradingFeedback.scala create mode 100644 Scala/patmat/project/ProgFunBuild.scala create mode 100644 Scala/patmat/project/RecordingLogger.scala create mode 100644 Scala/patmat/project/RichJsValue.scala create mode 100644 Scala/patmat/project/ScalaTestRunner.scala create mode 100644 Scala/patmat/project/Settings.scala create mode 100644 Scala/patmat/project/StyleChecker.scala create mode 100644 Scala/patmat/project/build.properties create mode 100644 Scala/patmat/project/buildSettings.sbt create mode 100644 Scala/patmat/project/project/buildPlugins.sbt create mode 100644 Scala/patmat/project/scalastyle_config.xml create mode 100644 Scala/patmat/src/main/scala/common/package.scala create mode 100644 Scala/patmat/src/main/scala/patmat/Huffman.scala create mode 100644 Scala/patmat/src/test/scala/patmat/HuffmanSuite.scala diff --git a/Scala/patmat/.classpath b/Scala/patmat/.classpath new file mode 100644 index 0000000..572103c --- /dev/null +++ b/Scala/patmat/.classpath @@ -0,0 +1,12 @@ + + + + + + + + + + + + \ No newline at end of file diff --git a/Scala/patmat/.project b/Scala/patmat/.project new file mode 100644 index 0000000..3112916 --- /dev/null +++ b/Scala/patmat/.project @@ -0,0 +1,12 @@ + + progfun-patmat + + + org.scala-ide.sdt.core.scalabuilder + + + + org.scala-ide.sdt.core.scalanature + org.eclipse.jdt.core.javanature + + \ No newline at end of file diff --git a/Scala/patmat/.settings/org.scala-ide.sdt.core.prefs b/Scala/patmat/.settings/org.scala-ide.sdt.core.prefs new file mode 100644 index 0000000..9b452fd --- /dev/null +++ b/Scala/patmat/.settings/org.scala-ide.sdt.core.prefs @@ -0,0 +1,5 @@ +#Generated by sbteclipse +#Mon Apr 15 08:47:12 CEST 2013 +deprecation=true +feature=true +scala.compiler.useProjectSettings=true diff --git a/Scala/patmat/build.sbt b/Scala/patmat/build.sbt new file mode 100644 index 0000000..2d2af82 --- /dev/null +++ b/Scala/patmat/build.sbt @@ -0,0 +1,110 @@ +name <<= submitProjectName(pname => "progfun-"+ pname) + +version := "1.0.0" + +scalaVersion := "2.10.1" + +scalacOptions ++= Seq("-deprecation", "-feature") + +libraryDependencies += "org.scalatest" %% "scalatest" % "1.9.1" % "test" + +libraryDependencies += "junit" % "junit" % "4.10" % "test" + +// This setting defines the project to which a solution is submitted. When creating a +// handout, the 'createHandout' task will make sure that its value is correct. +submitProjectName := "patmat" + +// See documentation in ProgFunBuild.scala +projectDetailsMap := { +val currentCourseId = "progfun-002" +Map( + "example" -> ProjectDetails( + packageName = "example", + assignmentPartId = "fTzFogNl", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "recfun" -> ProjectDetails( + packageName = "recfun", + assignmentPartId = "3Rarn9Ki", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "funsets" -> ProjectDetails( + packageName = "funsets", + assignmentPartId = "fBXOL6Qd", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "objsets" -> ProjectDetails( + packageName = "objsets", + assignmentPartId = "95dMMEz7", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "patmat" -> ProjectDetails( + packageName = "patmat", + assignmentPartId = "3gPmpcif", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "forcomp" -> ProjectDetails( + packageName = "forcomp", + assignmentPartId = "fG1oZGIO", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId), + "streams" -> ProjectDetails( + packageName = "streams", + assignmentPartId = "CWKgCFCi", + maxScore = 10d, + styleScoreRatio = 0.2, + courseId=currentCourseId)//, + // "simulations" -> ProjectDetails( + // packageName = "simulations", + // assignmentPartId = "iYs4GARk", + // maxScore = 10d, + // styleScoreRatio = 0.2, + // courseId="progfun2-001"), + // "interpreter" -> ProjectDetails( + // packageName = "interpreter", + // assignmentPartId = "1SZhe1Ut", + // maxScore = 10d, + // styleScoreRatio = 0.2, + // courseId="progfun2-001") +) +} + +// Files that we hand out to the students +handoutFiles <<= (baseDirectory, projectDetailsMap, commonSourcePackages) map { (basedir, detailsMap, commonSrcs) => + (projectName: String) => { + val details = detailsMap.getOrElse(projectName, sys.error("Unknown project name: "+ projectName)) + val commonFiles = (PathFinder.empty /: commonSrcs)((files, pkg) => + files +++ (basedir / "src" / "main" / "scala" / pkg ** "*.scala") + ) + (basedir / "src" / "main" / "scala" / details.packageName ** "*.scala") +++ + commonFiles +++ + (basedir / "src" / "main" / "resources" / details.packageName ** "*") +++ + (basedir / "src" / "test" / "scala" / details.packageName ** "*.scala") +++ + (basedir / "build.sbt") +++ + (basedir / "project" / "build.properties") +++ + (basedir / "project" ** ("*.scala" || "*.sbt")) +++ + (basedir / "project" / "scalastyle_config.xml") +++ + (basedir / "lib_managed" ** "*.jar") +++ + (basedir * (".classpath" || ".project")) +++ + (basedir / ".settings" / "org.scala-ide.sdt.core.prefs") + } +} + +// This setting allows to restrict the source files that are compiled and tested +// to one specific project. It should be either the empty string, in which case all +// projects are included, or one of the project names from the projectDetailsMap. +currentProject := "" + +// Packages in src/main/scala that are used in every project. Included in every +// handout, submission. +commonSourcePackages += "common" + +// Packages in src/test/scala that are used for grading projects. Always included +// compiling tests, grading a project. +gradingTestPackages += "grading" diff --git a/Scala/patmat/lib_managed/jars/junit/junit/junit-4.10.jar b/Scala/patmat/lib_managed/jars/junit/junit/junit-4.10.jar new file mode 100644 index 0000000..954851e Binary files /dev/null and b/Scala/patmat/lib_managed/jars/junit/junit/junit-4.10.jar differ diff --git a/Scala/patmat/lib_managed/jars/org.hamcrest/hamcrest-core/hamcrest-core-1.1.jar b/Scala/patmat/lib_managed/jars/org.hamcrest/hamcrest-core/hamcrest-core-1.1.jar new file mode 100644 index 0000000..e5149be Binary files /dev/null and b/Scala/patmat/lib_managed/jars/org.hamcrest/hamcrest-core/hamcrest-core-1.1.jar differ diff --git a/Scala/patmat/lib_managed/jars/org.scala-lang/scala-actors/scala-actors-2.10.0.jar b/Scala/patmat/lib_managed/jars/org.scala-lang/scala-actors/scala-actors-2.10.0.jar new file mode 100644 index 0000000..bb4600c Binary files /dev/null and b/Scala/patmat/lib_managed/jars/org.scala-lang/scala-actors/scala-actors-2.10.0.jar differ diff --git a/Scala/patmat/lib_managed/jars/org.scala-lang/scala-reflect/scala-reflect-2.10.0.jar b/Scala/patmat/lib_managed/jars/org.scala-lang/scala-reflect/scala-reflect-2.10.0.jar new file mode 100644 index 0000000..6489599 Binary files /dev/null and b/Scala/patmat/lib_managed/jars/org.scala-lang/scala-reflect/scala-reflect-2.10.0.jar differ diff --git a/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.10/scalatest_2.10-1.9.1.jar b/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.10/scalatest_2.10-1.9.1.jar new file mode 100644 index 0000000..6be20e6 Binary files /dev/null and b/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.10/scalatest_2.10-1.9.1.jar differ diff --git a/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.9.2/scalatest_2.9.2-1.8.jar b/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.9.2/scalatest_2.9.2-1.8.jar new file mode 100644 index 0000000..30445f5 Binary files /dev/null and b/Scala/patmat/lib_managed/jars/org.scalatest/scalatest_2.9.2/scalatest_2.9.2-1.8.jar differ diff --git a/Scala/patmat/project/CourseraHttp.scala b/Scala/patmat/project/CourseraHttp.scala new file mode 100644 index 0000000..5f55b12 --- /dev/null +++ b/Scala/patmat/project/CourseraHttp.scala @@ -0,0 +1,223 @@ +import dispatch.{Request, Http, NoLogging, StatusCode, url} +import cc.spray.json.{JsNull, JsonParser, DefaultJsonProtocol, JsValue} +import RichJsValue._ +import org.apache.commons.codec.digest.DigestUtils +import org.apache.commons.codec.binary.{Hex, Base64} +import java.io.{IOException, File, FileInputStream} +import scalaz.Scalaz.{mkIdentity, ValidationNEL} + +import Settings._ + +case class JsonSubmission(api_state: String, user_info: JsValue, submission_metadata: JsValue, solutions: JsValue, submission_encoding: String, submission: String) +//case class JsonQueueResult(submission: JsonSubmission) +object SubmitJsonProtocol extends DefaultJsonProtocol { + implicit val jsonSubmissionFormat = jsonFormat6(JsonSubmission) +// implicit val jsonQueueResultFormat = jsonFormat1(JsonQueueResult) +} + +object CourseraHttp { + private lazy val http = new Http with NoLogging + + private def executeRequest[T](req: Request)(parse: String => ValidationNEL[String, T]): ValidationNEL[String, T] = { + try { + http(req >- { res => + parse(res) + }) + } catch { + case ex: IOException => + ("Connection failed\n"+ ex.toString()).failNel + case StatusCode(code, message) => + ("HTTP failed with status "+ code +"\n"+ message).failNel + } + } + + + /****************************** + * SUBMITTING + */ + + def getChallenge(email: String, submitProject: ProjectDetails): ValidationNEL[String, Challenge] = { + val baseReq = url(challengeUrl(submitProject.courseId)) + val withArgs = baseReq << Map("email_address" -> email, + "assignment_part_sid" -> submitProject.assignmentPartId, + "response_encoding" -> "delim") + + executeRequest(withArgs) { res => + // example result. there might be an `aux_data` value at the end. + // |email_address|a@b.com|challenge_key|XXYYXXYYXXYY|state|XXYYXXYYXXYY|challenge_aux_data| + val parts = res.split('|').filterNot(_.isEmpty) + if (parts.length < 7) + ("Unexpected challenge format: \n"+ res).failNel + else + Challenge(parts(1), parts(3), parts(5)).successNel + } + } + + def submitSolution(sourcesJar: File, submitProject: ProjectDetails, challenge: Challenge, chResponse: String): ValidationNEL[String, String] = { + val fileLength = sourcesJar.length() + if (!sourcesJar.exists()) { + ("Sources jar archive does not exist\n"+ sourcesJar.getAbsolutePath).failNel + } else if (fileLength == 0l) { + ("Sources jar archive is empty\n"+ sourcesJar.getAbsolutePath).failNel + } else if (fileLength > maxSubmitFileSize) { + ("Sources jar archive is too big. Allowed size: "+ + maxSubmitFileSize +" bytes, found "+ fileLength +" bytes.\n"+ + sourcesJar.getAbsolutePath).failNel + } else { + val bytes = new Array[Byte](fileLength.toInt) + val sizeRead = try { + val is = new FileInputStream(sourcesJar) + val read = is.read(bytes) + is.close() + read + } catch { + case ex: IOException => + ("Failed to read sources jar archive\n"+ ex.toString()).failNel + } + if (sizeRead != bytes.length) { + ("Failed to read the sources jar archive, size read: "+ sizeRead).failNel + } else { + val fileData = encodeBase64(bytes) + val baseReq = url(submitUrl(submitProject.courseId)) + val withArgs = baseReq << Map("assignment_part_sid" -> submitProject.assignmentPartId, + "email_address" -> challenge.email, + "submission" -> fileData, + "submission_aux" -> "", + "challenge_response" -> chResponse, + "state" -> challenge.state) + executeRequest(withArgs) { res => + // the API returns HTTP 200 even if there are failures, how impolite... + if (res.contains("Your submission has been accepted")) + res.successNel + else + res.failNel + } + } + } + } + + def challengeResponse(challenge: Challenge, otPassword: String): String = + shaHexDigest(challenge.challengeKey + otPassword) + + + /******************************** + * DOWNLOADING SUBMISSIONS + */ + + // def downloadFromQueue(queue: String, targetJar: File, apiKey: String): ValidationNEL[String, QueueResult] = { + // val baseReq = url(Settings.submitQueueUrl) + // val withArgsAndHeader = baseReq << Map("queue" -> queue) <:< Map("X-api-key" -> apiKey) + + // executeRequest(withArgsAndHeader) { res => + // extractJson(res, targetJar) + // } + // } + + def readJsonFile(jsonFile: File, targetJar: File): ValidationNEL[String, QueueResult] = { + extractJson(sbt.IO.read(jsonFile), targetJar) + } + + def extractJson(jsonData: String, targetJar: File): ValidationNEL[String, QueueResult] = { + import SubmitJsonProtocol._ + for { + jsonSubmission <- { + try { + val parsed = JsonParser(jsonData) + val submission = parsed \ "submission" + if (submission == JsNull) { + ("Nothing to grade, queue is empty.").failNel + } else { + submission.convertTo[JsonSubmission].successNel + } + } catch { + case e: Exception => + ("Could not parse submission\n"+ jsonData +"\n"+ fullExceptionString(e)).failNel + } + } + queueResult <- { + val encodedFile = jsonSubmission.submission + val jarContent = decodeBase64(encodedFile) + try { + sbt.IO.write(targetJar, jarContent) + QueueResult(jsonSubmission.api_state).successNel + } catch { + case e: IOException => + ("Failed to write jar file to "+ targetJar.getAbsolutePath +"\n"+ e.toString).failNel + } + } + } yield queueResult + } + + def unpackJar(file: File, targetDirectory: File): ValidationNEL[String, Unit] = { + try { + val files = sbt.IO.unzip(file, targetDirectory) + if (files.isEmpty) + ("No files found when unpacking jar file "+ file.getAbsolutePath).failNel + else + ().successNel + } catch { + case e: IOException => + val msg = "Error while unpacking the jar file "+ file.getAbsolutePath +" to "+ targetDirectory.getAbsolutePath +"\n"+ e.toString + if (Settings.offlineMode) { + println("[offline mode] "+ msg) + ().successNel + } else { + msg.failNel + } + } + } + + + /******************************** + * SUBMITTING GRADES + */ + + def submitGrade(feedback: String, score: String, apiState: String, apiKey: String, gradeProject: ProjectDetails): ValidationNEL[String, Unit] = { + import DefaultJsonProtocol._ + val baseReq = url(Settings.uploadFeedbackUrl(gradeProject.courseId)) + val withArgs = baseReq << Map("api_state" -> apiState, "score" -> score, "feedback" -> feedback) <:< Map("X-api-key" -> apiKey) + executeRequest(withArgs) { res => + try { + val js = JsonParser(res) + val status = (js \ "status").convertTo[String] + if (status == "202") + ().successNel + else + ("Unexpected result from submit request: "+ status).failNel + } catch { + case e: Exception => + ("Failed to parse response while submitting grade\n"+ res +"\n"+ fullExceptionString(e)).failNel + } + } + } + + + /********************************* + * TOOLS AND STUFF + */ + + def shaHexDigest(s: String): String = { + val chars = Hex.encodeHex(DigestUtils.sha(s)) + new String(chars) + } + + + def fullExceptionString(e: Throwable) = + e.toString +"\n"+ e.getStackTrace.map(_.toString).mkString("\n") + + + /* Base 64 tools */ + + def encodeBase64(bytes: Array[Byte]): String = + new String(Base64.encodeBase64(bytes)) + + def decodeBase64(str: String): Array[Byte] = { + // codecs 1.4 has a version accepting a string, but not 1.2; jar hell. + Base64.decodeBase64(str.getBytes) + } +} + +case class Challenge(email: String, challengeKey: String, state: String) + +case class QueueResult(apiState: String) + diff --git a/Scala/patmat/project/GradingFeedback.scala b/Scala/patmat/project/GradingFeedback.scala new file mode 100644 index 0000000..5d78c54 --- /dev/null +++ b/Scala/patmat/project/GradingFeedback.scala @@ -0,0 +1,218 @@ +import collection.mutable.ListBuffer +import org.apache.commons.lang3.StringEscapeUtils + +object GradingFeedback { + + private val feedbackSummary = new ListBuffer[String]() + private val feedbackDetails = new ListBuffer[String]() + + private def addSummary(msg: String) { feedbackSummary += msg; feedbackSummary += "\n\n" } + private def addDetails(msg: String) { feedbackDetails += msg; feedbackDetails += "\n\n" } + + /** + * Converts the string to HTML - coursera displays the feedback in an html page. + */ + def feedbackString(html: Boolean = true) = { + val total = totalGradeMessage(totalScore) + "\n\n" + // trim removes the newlines at the end + val s = (total + feedbackSummary.mkString + feedbackDetails.mkString).trim + if (html) + "
"+ StringEscapeUtils.escapeHtml4(s) +"
" + else + s + } + + private var vTestScore: Double = 0d + private var vStyleScore: Double = 0d + def totalScore = vTestScore + vStyleScore + + private var vMaxTestScore: Double = 0d + private var vMaxStyleScore: Double = 0d + def maxTestScore = vMaxTestScore + def maxStyleScore = vMaxStyleScore + + // a string obtained from coursera when downloading an assignment. it has to be + // used again when uploading the grade. + var apiState: String = "" + + /** + * `failed` means that there was an unexpected error during grading. This includes + * - student's code does not compile + * - our tests don't compile (against the student's code) + * - crash while executing ScalaTest (not test failures, but problems trying to run the tests!) + * - crash while executing the style checker (again, not finding style problems!) + * + * When failed is `true`, later grading stages will not be executed: this is handled automatically + * by SBT, tasks depending on a failed one are not run. + * + * However, these dependent tasks still fail (i.e. mapR on them is invoked). The variable below + * allows us to know if something failed before. In this case, we don't add any more things to + * the log. (see `ProgFunBuild.handleFailure`) + */ + private var failed = false + def isFailed = failed + + def initialize() { + feedbackSummary.clear() + feedbackDetails.clear() + vTestScore = 0d + vStyleScore = 0d + apiState = "" + failed = false + } + + def setMaxScore(maxScore: Double, styleScoreRatio: Double) { + vMaxTestScore = maxScore * (1-styleScoreRatio) + vMaxStyleScore = maxScore * styleScoreRatio + } + + + /* Methods to build up the feedback log */ + + def downloadUnpackFailed(log: String) { + failed = true + addSummary(downloadUnpackFailedMessage) + addDetails("======== FAILURES WHILE DOWNLOADING OR EXTRACTING THE SUBMISSION ========") + addDetails(log) + } + + + def compileFailed(log: String) { + failed = true + addSummary(compileFailedMessage) + addDetails("======== COMPILATION FAILURES ========") + addDetails(log) + } + + def testCompileFailed(log: String) { + failed = true + addSummary(testCompileFailedMessage) + addDetails("======== TEST COMPILATION FAILURES ========") + addDetails(log) + } + + + + def allTestsPassed() { + addSummary(allTestsPassedMessage) + vTestScore = maxTestScore + } + + def testsFailed(log: String, score: Double) { + addSummary(testsFailedMessage(score)) + vTestScore = score + addDetails("======== LOG OF FAILED TESTS ========") + addDetails(log) + } + + def testExecutionFailed(log: String) { + failed = true + addSummary(testExecutionFailedMessage) + addDetails("======== ERROR LOG OF TESTING TOOL ========") + addDetails(log) + } + + def testExecutionDebugLog(log: String) { + addDetails("======== DEBUG OUTPUT OF TESTING TOOL ========") + addDetails(log) + } + + + + def perfectStyle() { + addSummary(perfectStyleMessage) + vStyleScore = maxStyleScore + } + + def styleProblems(log: String, score: Double) { + addSummary(styleProblemsMessage(score)) + vStyleScore = score + addDetails("======== CODING STYLE ISSUES ========") + addDetails(log) + } + + + + /* Feedback Messages */ + + private val downloadUnpackFailedMessage = + """We were not able to download your submission from the coursera servers, or extracting the + |archive containing your source code failed. + | + |If you see this error message as your grade feedback, please contact one of the teaching + |assistants. See below for a detailed error log.""".stripMargin + + private val compileFailedMessage = + """We were not able to compile the source code you submitted. This is not expected to happen, + |because the `submit` command in SBT can only be executed if your source code compiles. + | + |Please verify the following points: + | - You should use the `submit` command in SBT to upload your solution + | - You should not perform any changes to the SBT project definition files, i.e. the *.sbt + | files, and the files in the `project/` directory + | + |Take a careful look at the compiler output below - maybe you can find out what the problem is. + | + |If you cannot find a solution, ask for help on the discussion forums on the course website.""".stripMargin + + + private val testCompileFailedMessage = + """We were not able to compile our tests, and therefore we could not correct your submission. + | + |The most likely reason for this problem is that your submitted code uses different names + |for methods, classes, objects or different types than expected. + | + |In principle, this can only arise if you changed some names or types in the code that we + |provide, for instance a method name or a parameter type. + | + |To diagnose your problem, perform the following steps: + | - Run the tests that we provide with our hand-out. These tests verify that all names and + | types are correct. In case these tests pass, but you still see this message, please post + | a report on the forums [1]. + | - Take a careful look at the error messages from the Scala compiler below. They should give + | you a hint where your code has an unexpected shape. + | + |If you cannot find a solution, ask for help on the discussion forums on the course website.""".stripMargin + + + private def testsFailedMessage(score: Double) = + """The code you submitted did not pass all of our tests: your submission achieved a score of + |%.2f out of %.2f in our tests. + | + |In order to find bugs in your code, we advise to perform the following steps: + | - Take a close look at the test output that you can find below: it should point you to + | the part of your code that has bugs. + | - Run the tests that we provide with the handout on your code. + | - The tests we provide do not test your code in depth: they are very incomplete. In order + | to test more aspects of your code, write your own unit tests. + | - Take another very careful look at the assignment description. Try to find out if you + | misunderstood parts of it. While reading through the assignment, write more tests. + | + |Below you can find a short feedback for every individual test that failed.""".stripMargin.format(score, vMaxTestScore) + + // def so that we read the right value of vMaxTestScore (initialize modifies it) + private def allTestsPassedMessage = + """Your solution passed all of our tests, congratulations! You obtained the maximal test + |score of %.2f.""".stripMargin.format(vMaxTestScore) + + private val testExecutionFailedMessage = + """An error occured while running our tests on your submission. This is not expected to + |happen, it means there is a bug in our testing environment. + | + |In order for us to help you, please contact one of the teaching assistants and send + |them the entire feedback message that you recieved.""".stripMargin + + // def so that we read the right value of vMaxStyleScore (initialize modifies it) + private def perfectStyleMessage = + """Our automated style checker tool could not find any issues with your code. You obtained the maximal + |style score of %.2f.""".stripMargin.format(vMaxStyleScore) + + + private def styleProblemsMessage(score: Double) = + """Our automated style checker tool found issues in your code with respect to coding style: it + |computed a style score of %.2f out of %.2f for your submission. See below for detailed feedback.""".stripMargin.format(score, vMaxStyleScore) + + + private def totalGradeMessage(score: Double) = + """Your overall score for this assignment is %.2f out of %.2f""".format(score, vMaxTestScore + vMaxStyleScore) +} diff --git a/Scala/patmat/project/ProgFunBuild.scala b/Scala/patmat/project/ProgFunBuild.scala new file mode 100644 index 0000000..93d4b9d --- /dev/null +++ b/Scala/patmat/project/ProgFunBuild.scala @@ -0,0 +1,646 @@ +import sbt._ +import Keys._ + +import scalaz.Scalaz.mkIdentity +import scalaz.{Success, Failure} +import com.typesafe.sbteclipse.plugin.EclipsePlugin.EclipseKeys + +/** + * See README.md for high-level overview + * + * Libraries Doc Links + * + * Coursera API + * - http://support.coursera.org/customer/portal/articles/573466-programming-assignments + * - the python script 'submit.py' that can be downloaded from the above site + * + * SBT + * - https://github.com/harrah/xsbt/wiki/Getting-Started-Full-Def + * - https://github.com/harrah/xsbt/wiki/Getting-Started-Custom-Settings + * - https://github.com/harrah/xsbt/wiki/Getting-Started-More-About-Settings + * - https://github.com/harrah/xsbt/wiki/Input-Tasks + * - https://github.com/harrah/xsbt/wiki/Tasks + * - http://harrah.github.com/xsbt/latest/api/index.html + * - https://groups.google.com/forum/?fromgroups#!forum/simple-build-tool + * + * Dispatch + * - http://dispatch-classic.databinder.net/Response+Bodies.html + * - http://www.flotsam.nl/dispatch-periodic-table.html + * - http://databinder.net/dispatch-doc/ + * + * Scalaz + * - http://www.lunatech-research.com/archives/2012/03/02/validation-scala + * - http://scalaz.github.com/scalaz/scalaz-2.9.1-6.0.4/doc/index.html#scalaz.Validation + * + * Apache Commons Codec 1.4 + * - http://www.jarvana.com/jarvana/view/commons-codec/commons-codec/1.4/commons-codec-1.4-javadoc.jar!/index.html + * + * Scalatest + * - http://doc.scalatest.org/1.9.1/index.html#org.scalatest.package + */ +object ProgFunBuild extends Build { + + /*********************************************************** + * MAIN PROJECT DEFINITION + */ + + lazy val assignmentProject = Project(id = "assignment", base = file(".")) settings( + // 'submit' depends on 'packageSrc', so needs to be a project-level setting: on build-level, 'packageSrc' is not defined + submitSetting, + createHandoutSetting, + // put all libs in the lib_managed directory, that way we can distribute eclipse project files + retrieveManaged := true, + EclipseKeys.relativizeLibs := true, + // Avoid generating eclipse source entries for the java directories + (unmanagedSourceDirectories in Compile) <<= (scalaSource in Compile)(Seq(_)), + (unmanagedSourceDirectories in Test) <<= (scalaSource in Test)(Seq(_)), + commonSourcePackages := Seq(), // see build.sbt + gradingTestPackages := Seq(), // see build.sbt + selectMainSources, + selectTestSources, + scalaTestSetting, + styleCheckSetting, + setTestPropertiesSetting, + setTestPropertiesHook + ) settings (packageSubmissionFiles: _*) + + + /*********************************************************** + * SETTINGS AND TASKS + */ + + /** The 'submit' task uses this project name (defined in the build.sbt file) to know where to submit the solution */ + val submitProjectName = SettingKey[String]("submitProjectName") + + /** Project-specific settings, see main build.sbt */ + val projectDetailsMap = SettingKey[Map[String, ProjectDetails]]("projectDetailsMap") + + /** + * The files that are handed out to students. Accepts a string denoting the project name for + * which a handout will be generated. + */ + val handoutFiles = TaskKey[String => PathFinder]("handoutFiles") + + /** + * This setting allows to restrict the source files that are compiled and tested + * to one specific project. It should be either the empty string, in which case all + * projects are included, or one of the project names from the projectDetailsMap. + */ + val currentProject = SettingKey[String]("currentProject") + + /** Package names of source packages common for all projects, see comment in build.sbt */ + val commonSourcePackages = SettingKey[Seq[String]]("commonSourcePackages") + + /** Package names of test sources for grading, see comment in build.sbt */ + val gradingTestPackages = SettingKey[Seq[String]]("gradingTestPackages") + + /************************************************************ + * SUBMITTING A SOLUTION TO COURSERA + */ + + val packageSubmission = TaskKey[File]("packageSubmission") + + val packageSubmissionFiles = { + // the packageSrc task uses Defaults.packageSrcMappings, which is defined as concatMappings(resourceMappings, sourceMappings) + // in the packageSubmisson task we only use the sources, not the resources. + inConfig(Compile)(Defaults.packageTaskSettings(packageSubmission, Defaults.sourceMappings)) + } + + /** Task to submit a solution to coursera */ + val submit = InputKey[Unit]("submit") + + lazy val submitSetting = submit <<= inputTask { argTask => + (argTask, compile in Compile, currentProject, (packageSubmission in Compile), submitProjectName, projectDetailsMap, streams) map { (args, _, currentProject, sourcesJar, projectName, detailsMap, s) => + if (currentProject != "") { + val msg = + """The 'currentProject' setting is not empty: '%s' + | + |This error only appears if there are mistakes in the build scripts. Please re-download the assignment + |from the coursera webiste. Make sure that you did not perform any changes to the build files in the + |`project/` directory. If this error persits, ask for help on the course forums.""".format(currentProject).stripMargin +"\n " + s.log.error(msg) + failSubmit() + } else { + lazy val wrongNameMsg = + """Unknown project name: %s + | + |This error only appears if there are mistakes in the build scripts. Please re-download the assignment + |from the coursera webiste. Make sure that you did not perform any changes to the build files in the + |`project/` directory. If this error persits, ask for help on the course forums.""".format(projectName).stripMargin +"\n " + // log strips empty lines at the ond of `msg`. to have one we add "\n " + val details = detailsMap.getOrElse(projectName, {s.log.error(wrongNameMsg); failSubmit()}) + args match { + case email :: otPassword :: Nil => + submitSources(sourcesJar, details, email, otPassword, s.log) + case _ => + val msg = + """No e-mail address and / or submission password provided. The required syntax for `submit` is + | submit + | + |The submission password, which is NOT YOUR LOGIN PASSWORD, can be obtained from the assignment page + | https://class.coursera.org/%s/assignment/index""".format(details.courseId).stripMargin +"\n " + s.log.error(msg) + failSubmit() + } + } + } + } + + + def submitSources(sourcesJar: File, submitProject: ProjectDetails, email: String, otPassword: String, logger: Logger) { + import CourseraHttp._ + logger.info("Connecting to coursera. Obtaining challenge...") + val res = for { + challenge <- getChallenge(email, submitProject) + chResponse <- { + logger.info("Computing challenge response...") + challengeResponse(challenge, otPassword).successNel[String] + } + response <- { + logger.info("Submitting solution...") + submitSolution(sourcesJar, submitProject, challenge, chResponse) + } + } yield response + + res match { + case Failure(msgs) => + for (msg <- msgs.list) logger.error(msg) + failSubmit() + case Success(response) => + logger.success("Your code was successfully submitted: "+ response) + } + } + + + def failSubmit(): Nothing = { + sys.error("Submission failed") + } + + + + /*********************************************************** + * CREATE THE HANDOUT ZIP FILE + */ + + val createHandout = InputKey[File]("createHandout") + + // depends on "compile in Test" to make sure everything compiles. also makes sure that + // all dependencies are downloaded, because we pack the .jar files into the handout. + lazy val createHandoutSetting = createHandout <<= inputTask { argTask => + (argTask, currentProject, baseDirectory, handoutFiles, submitProjectName, target, projectDetailsMap, compile in Test) map { (args, currentProject, basedir, filesFinder, submitProject, targetDir, detailsMap, _) => + if (currentProject != "") + sys.error("\nthe 'currentProject' setting in build.sbt needs to be \"\" in order to create a handout") + else args match { + case handoutProjectName :: eclipseDone :: Nil if eclipseDone == "eclipseWasCalled" => + if (handoutProjectName != submitProject) + sys.error("\nThe `submitProjectName` setting in `build.sbt` must match the project name for which a handout is generated\n ") + val files = filesFinder(handoutProjectName).get + val filesWithRelativeNames = files.x_!(relativeTo(basedir)) map { + case (file, name) => (file, handoutProjectName+"/"+name) + } + val targetZip = targetDir / (handoutProjectName +".zip") + IO.zip(filesWithRelativeNames, targetZip) + targetZip + case _ => + val msg =""" + | + |Failed to create handout. Syntax: `createHandout ` + | + |Valid project names are: %s + | + |The argument needs to be the string "eclipseWasCalled". This is to remind + |you that you **need** to manually run the `eclipse` command before running `createHandout`. + | """.stripMargin.format(detailsMap.keys.mkString(", ")) + sys.error(msg) + } + } + } + + + /************************************************************ + * LIMITING SOURCES TO CURRENT PROJECT + */ + + def filter(basedir: File, packages: Seq[String]) = new FileFilter { + def accept(file: File) = { + basedir.equals(file) || { + IO.relativize(basedir, file) match { + case Some(str) => + packages exists { pkg => + str.startsWith(pkg) + } + case _ => + sys.error("unexpected test file: "+ file +"\nbase dir: "+ basedir) + } + } + } + } + + def projectFiles(allFiles: Seq[File], basedir: File, projectName: String, globalPackages: Seq[String], detailsMap: Map[String, ProjectDetails]) = { + if (projectName == "") allFiles + else detailsMap.get(projectName) match { + case Some(project) => + val finder = allFiles ** filter(basedir, globalPackages :+ project.packageName) + finder.get + case None => + sys.error("currentProject is set to an invalid name: "+ projectName) + } + } + + /** + * Only include source files of 'currentProject', helpful when preparign a specific assignment. + * Also keeps the source packages in 'commonSourcePackages'. + */ + val selectMainSources = { + (unmanagedSources in Compile) <<= (unmanagedSources in Compile, scalaSource in Compile, projectDetailsMap, currentProject, commonSourcePackages) map { (sources, srcMainScalaDir, detailsMap, projectName, commonSrcs) => + projectFiles(sources, srcMainScalaDir, projectName, commonSrcs, detailsMap) + } + } + + /** + * Only include the test files which are defined in the package of the current project. + * Also keeps test sources in packages listed in 'gradingTestPackages'. + */ + val selectTestSources = { + (unmanagedSources in Test) <<= (unmanagedSources in Test, scalaSource in Test, projectDetailsMap, currentProject, gradingTestPackages) map { (sources, srcTestScalaDir, detailsMap, projectName, gradingSrcs) => + projectFiles(sources, srcTestScalaDir, projectName, gradingSrcs, detailsMap) + } + } + + + /************************************************************ + * PARAMETERS FOR RUNNING THE TESTS + * + * Setting some system properties that are parameters for the GradingSuite test + * suite mixin. This is for running the `test` task in SBT's JVM. When running + * the `scalaTest` task, the ScalaTestRunner creates a new JVM and passes the + * same properties. + */ + + val setTestProperties = TaskKey[Unit]("setTestProperties") + val setTestPropertiesSetting = setTestProperties := { + import scala.util.Properties._ + import Settings._ + setProp(scalaTestIndividualTestTimeoutProperty, individualTestTimeout.toString) + setProp(scalaTestDefaultWeigthProperty, scalaTestDefaultWeigth.toString) + } + + val setTestPropertiesHook = (test in Test) <<= (test in Test).dependsOn(setTestProperties) + + + /************************************************************ + * RUNNING WEIGHTED SCALATEST & STYLE CHECKER ON DEVELOPMENT SOURCES + */ + + def copiedResourceFiles(copied: collection.Seq[(java.io.File, java.io.File)]): List[File] = { + copied collect { + case (from, to) if to.isFile => to + } toList + } + + val scalaTest = TaskKey[Unit]("scalaTest") + val scalaTestSetting = scalaTest <<= + (compile in Compile, + compile in Test, + fullClasspath in Test, + copyResources in Compile, + classDirectory in Test, + baseDirectory, + streams) map { (_, _, classpath, resources, testClasses, basedir, s) => + // we use `map`, so this is only executed if all dependencies succeed. no need to check `GradingFeedback.isFailed` + val logger = s.log + val outfile = basedir / Settings.testResultsFileName + val policyFile = basedir / Settings.policyFileName + val (score, maxScore, feedback, runLog) = ScalaTestRunner.runScalaTest(classpath, testClasses, outfile, policyFile, copiedResourceFiles(resources), logger.error(_)) + logger.info(feedback) + logger.info("Test Score: "+ score +" out of "+ maxScore) + if (!runLog.isEmpty) { + logger.info("Console output of ScalaTest process") + logger.info(runLog) + } + } + + val styleCheck = TaskKey[Unit]("styleCheck") + + /** + * depend on compile to make sure the sources pass the compiler + */ + val styleCheckSetting = styleCheck <<= (compile in Compile, sources in Compile, streams) map { (_, sourceFiles, s) => + val logger = s.log + val (feedback, score) = StyleChecker.assess(sourceFiles) + logger.info(feedback) + logger.info("Style Score: "+ score +" out of "+ StyleChecker.maxResult) + } + + + /************************************************************ + * PROJECT DEFINITION FOR GRADING + */ + + lazy val submissionProject = Project(id = "submission", base = file(Settings.submissionDirName)) settings( + /** settings we take over from the assignment project */ + version <<= (version in assignmentProject), + name <<= (name in assignmentProject), + scalaVersion <<= (scalaVersion in assignmentProject), + scalacOptions <<= (scalacOptions in assignmentProject), + libraryDependencies <<= (libraryDependencies in assignmentProject), + + /** settings specific to the grading project */ + initGradingSetting, + // default value, don't change. see comment on `val partIdOfGradingProject` + partIdOfGradingProject := "", + gradeProjectDetailsSetting, + setMaxScoreSetting, + setMaxScoreHook, + // default value, don't change. see comment on `val apiKey` + apiKey := "", + getSubmissionSetting, + getSubmissionHook, + submissionLoggerSetting, + readCompileLog, + readTestCompileLog, + setTestPropertiesSetting, + setTestPropertiesHook, + resourcesFromAssignment, + selectResourcesForProject, + testSourcesFromAssignment, + selectTestsForProject, + scalaTestSubmissionSetting, + styleCheckSubmissionSetting, + gradeSetting, + EclipseKeys.skipProject := true + ) + + /** + * The assignment part id of the project to be graded. Don't hard code this setting in .sbt or .scala, this + * setting should remain a (command-line) parameter of the `submission/grade` task, defined when invoking sbt. + * See also feedback string in "val gradeProjectDetailsSetting". + */ + val partIdOfGradingProject = SettingKey[String]("partIdOfGradingProject") + + /** + * The api key to access non-public api parts on coursera. This key is secret! It's defined in + * 'submission/settings.sbt', which is not part of the handout. + * + * Default value 'apiKey' to make the handout sbt project work + * - In the handout, apiKey needs to be defined, otherwise the build doesn't compile + * - When correcting, we define 'apiKey' in the 'submission/sectrets.sbt' file + * - The value in the .sbt file will take precedence when correcting (settings in .sbt take + * precedence over those in .scala) + */ + val apiKey = SettingKey[String]("apiKey") + + + /************************************************************ + * GRADING INITIALIZATION + */ + + val initGrading = TaskKey[Unit]("initGrading") + lazy val initGradingSetting = initGrading <<= (clean, sourceDirectory, baseDirectory) map { (_, submissionSrcDir, basedir) => + deleteFiles(submissionSrcDir, basedir) + GradingFeedback.initialize() + RecordingLogger.clear() + } + + def deleteFiles(submissionSrcDir: File, basedir: File) { + // don't delete anything in offline mode, useful for us when hacking testing / stylechecking + if (!Settings.offlineMode){ + IO.delete(submissionSrcDir) + IO.delete(basedir / Settings.submissionJarFileName) + IO.delete(basedir / Settings.testResultsFileName) + } + } + + /** ProjectDetails of the project that we are grading */ + val gradeProjectDetails = TaskKey[ProjectDetails]("gradeProjectDetails") + + // here we depend on `initialize` because we already use the GradingFeedback + lazy val gradeProjectDetailsSetting = gradeProjectDetails <<= (initGrading, partIdOfGradingProject, projectDetailsMap in assignmentProject) map { (_, partId, detailsMap) => + detailsMap.find(_._2.assignmentPartId == partId) match { + case Some((_, details)) => + details + case None => + val validIds = detailsMap.map(_._2.assignmentPartId) + val msgRaw = + """Unknown assignment part id: %s + |Valid part ids are: %s + | + |In order to grade a project, the `partIdOfGradingProject` setting has to be defined. If you are running + |interactively in the sbt console, type `set (partIdOfGradingProject in submissionProject) := "idString"`. + |When running the grading task from the command line, add the above `set` command, e.g. execute + | + | sbt 'set (partIdOfGradingProject in submissionProject) := "idString"' submission/grade""" + val msg = msgRaw.stripMargin.format(partId, validIds.mkString(", ")) + "\n " + GradingFeedback.downloadUnpackFailed(msg) + sys.error(msg) + } + } + + val setMaxScore = TaskKey[Unit]("setMaxScore") + val setMaxScoreSetting = setMaxScore <<= (gradeProjectDetails) map { project => + GradingFeedback.setMaxScore(project.maxScore, project.styleScoreRatio) + } + + // set the maximal score before running compile / test / ... + val setMaxScoreHook = (compile in Compile) <<= (compile in Compile).dependsOn(setMaxScore) + + + /************************************************************ + * DOWNLOADING AND EXTRACTING SUBMISSION + */ + + val getSubmission = TaskKey[Unit]("getSubmission") + val getSubmissionSetting = getSubmission <<= (baseDirectory, scalaSource in Compile) map { (baseDir, scalaSrcDir) => + readAndUnpackSubmission(baseDir, scalaSrcDir) + } + + def readAndUnpackSubmission(baseDir: File, targetSourceDir: File) { + try { + val jsonFile = baseDir / Settings.submissionJsonFileName + val targetJar = baseDir / Settings.submissionJarFileName + val res = for { + queueResult <- { + if (Settings.offlineMode) { + println("[not unpacking from json file]") + QueueResult("").successNel + } else { + CourseraHttp.readJsonFile(jsonFile, targetJar) + } + } + _ <- { + GradingFeedback.apiState = queueResult.apiState + CourseraHttp.unpackJar(targetJar, targetSourceDir) + } + } yield () + + res match { + case Failure(msgs) => + GradingFeedback.downloadUnpackFailed(msgs.list.mkString("\n")) + case _ => + () + } + } catch { + case e: Throwable => + // generate some useful feedback in case something fails + GradingFeedback.downloadUnpackFailed(CourseraHttp.fullExceptionString(e)) + throw e + } + if (GradingFeedback.isFailed) failDownloadUnpack() + } + + // dependsOn makes sure that `getSubmission` is executed *before* `unmanagedSources` + val getSubmissionHook = (unmanagedSources in Compile) <<= (unmanagedSources in Compile).dependsOn(getSubmission) + + def failDownloadUnpack(): Nothing = { + sys.error("Download or Unpack failed") + } + + /************************************************************ + * READING COMPILATION AND TEST COMPILATION LOGS + */ + + + // extraLoggers need to be defined globally. (extraLoggers in Compile) does not work - sbt only + // looks at the global extraLoggers when creating the LogManager. + val submissionLoggerSetting = extraLoggers ~= { currentFunction => + (key: ScopedKey[_]) => { + new FullLogger(RecordingLogger) +: currentFunction(key) + } + } + + val readCompileLog = (compile in Compile) <<= (compile in Compile) mapR handleFailure(compileFailed) + val readTestCompileLog = (compile in Test) <<= (compile in Test) mapR handleFailure(compileTestFailed) + + def handleFailure[R](handler: (Incomplete, String) => Unit) = (res: Result[R]) => res match { + case Inc(inc) => + // Only call the handler of the task that actually failed. See comment in GradingFeedback.failed + if (!GradingFeedback.isFailed) + handler(inc, RecordingLogger.readAndClear()) + throw inc + case Value(v) => v + } + + def compileFailed(inc: Incomplete, log: String) { + GradingFeedback.compileFailed(log) + } + + def compileTestFailed(inc: Incomplete, log: String) { + GradingFeedback.testCompileFailed(log) + } + + + /************************************************************ + * RUNNING SCALATEST + */ + + /** The submission project takes resource files from the main (assignment) project */ + val resourcesFromAssignment = { + (resourceDirectory in Compile) <<= (resourceDirectory in (assignmentProject, Compile)) + } + + /** + * Only include the resource files which are defined in the package of the current project. + */ + val selectResourcesForProject = { + (resources in Compile) <<= (resources in Compile, resourceDirectory in (assignmentProject, Compile), gradeProjectDetails) map { (resources, resourceDir, project) => + val finder = resources ** filter(resourceDir, List(project.packageName)) + finder.get + } + } + + /** The submission project takes test files from the main (assignment) project */ + val testSourcesFromAssignment = { + (sourceDirectory in Test) <<= (sourceDirectory in (assignmentProject, Test)) + } + + /** + * Only include the test files which are defined in the package of the current project. + * Also keeps test sources in packages listed in 'gradingTestPackages' + */ + val selectTestsForProject = { + (unmanagedSources in Test) <<= (unmanagedSources in Test, scalaSource in (assignmentProject, Test), gradingTestPackages in assignmentProject, gradeProjectDetails) map { (sources, testSrcScalaDir, gradingSrcs, project) => + val finder = sources ** filter(testSrcScalaDir, gradingSrcs :+ project.packageName) + finder.get + } + } + + val scalaTestSubmission = TaskKey[Unit]("scalaTestSubmission") + val scalaTestSubmissionSetting = scalaTestSubmission <<= + (compile in Compile, + compile in Test, + fullClasspath in Test, + copyResources in Compile, + classDirectory in Test, + baseDirectory) map { (_, _, classpath, resources, testClasses, basedir) => + // we use `map`, so this is only executed if all dependencies succeed. no need to check `GradingFeedback.isFailed` + val outfile = basedir / Settings.testResultsFileName + val policyFile = basedir / ".." / Settings.policyFileName + ScalaTestRunner.scalaTestGrade(classpath, testClasses, outfile, policyFile, copiedResourceFiles(resources)) + } + + + + /************************************************************ + * STYLE CHECKING + */ + + val styleCheckSubmission = TaskKey[Unit]("styleCheckSubmission") + + /** + * - depend on scalaTestSubmission so that test get executed before style checking. the transitive + * dependencies also ensures that the "sources in Compile" don't have compilation errors + * - using `map` makes this task execute only if all its dependencies succeeded. + */ + val styleCheckSubmissionSetting = styleCheckSubmission <<= (sources in Compile, scalaTestSubmission) map { (sourceFiles, _) => + val (feedback, score) = StyleChecker.assess(sourceFiles) + if (score == StyleChecker.maxResult) { + GradingFeedback.perfectStyle() + } else { + val gradeScore = GradingFeedback.maxStyleScore * score / StyleChecker.maxResult + GradingFeedback.styleProblems(feedback, gradeScore) + } + } + + + + /************************************************************ + * SUBMITTING GRADES TO COURSERA + */ + + val grade = TaskKey[Unit]("grade") + + // mapR: submit the grade / feedback in any case, also on failure + val gradeSetting = grade <<= (scalaTestSubmission, styleCheckSubmission, apiKey, gradeProjectDetails, streams) mapR { (_, _, apiKeyR, projectDetailsR, s) => + val logOpt = s match { + case Value(v) => Some(v.log) + case _ => None + } + logOpt.foreach(_.info(GradingFeedback.feedbackString(html = false))) + apiKeyR match { + case Value(apiKey) if (!apiKey.isEmpty) => + // if build failed early, we did not even get the api key from the submission queue + if (!GradingFeedback.apiState.isEmpty && !Settings.offlineMode) { + val scoreString = "%.2f".format(GradingFeedback.totalScore) + val Value(projectDetails) = projectDetailsR + CourseraHttp.submitGrade(GradingFeedback.feedbackString(), scoreString, GradingFeedback.apiState, apiKey, projectDetails) match { + case Failure(msgs) => + sys.error(msgs.list.mkString("\n")) + case _ => + () + } + } else if(Settings.offlineMode) { + logOpt.foreach(_.info(" \nSettings.offlineMode enabled, not uploading the feedback")) + } else { + sys.error("Could not submit feedback - apiState not initialized") + } + case _ => + sys.error("Could not submit feedback - apiKey not defined: "+ apiKeyR) + } + } +} + +case class ProjectDetails(packageName: String, + assignmentPartId: String, + maxScore: Double, + styleScoreRatio: Double, + courseId: String) diff --git a/Scala/patmat/project/RecordingLogger.scala b/Scala/patmat/project/RecordingLogger.scala new file mode 100644 index 0000000..b886768 --- /dev/null +++ b/Scala/patmat/project/RecordingLogger.scala @@ -0,0 +1,35 @@ +import sbt._ +import collection.mutable.ListBuffer + +/** + * Logger to capture compiler output, test output + */ + +object RecordingLogger extends Logger { + private val buffer = ListBuffer[String]() + + def hasErrors = buffer.nonEmpty + + def readAndClear() = { + val res = buffer.mkString("\n") + buffer.clear() + res + } + + def clear() { + buffer.clear() + } + + def log(level: Level.Value, message: => String) = + if (level == Level.Error) { + buffer += message + } + + // we don't log success here + def success(message: => String) = () + + // invoked when a task throws an exception. invoked late, when the exception is logged, i.e. + // just before returning to the prompt. therefore we do nothing: storing the exception in the + // buffer would happen *after* the `handleFailure` reads the buffer. + def trace(t: => Throwable) = () +} diff --git a/Scala/patmat/project/RichJsValue.scala b/Scala/patmat/project/RichJsValue.scala new file mode 100644 index 0000000..ca9ad94 --- /dev/null +++ b/Scala/patmat/project/RichJsValue.scala @@ -0,0 +1,28 @@ +import cc.spray.json._ + +class RichJsValue(js: JsValue) { + def \ (name: String): JsValue = js match { + case JsObject(fields) => + fields(name) + case _ => + throw new IllegalArgumentException("Cannot select field "+ name +" from non-JsObject "+ js) + } + + def hasFieldNamed(name: String) = js match { + case JsObject(fields) => + fields.contains(name) + case _ => + false + } + + def arrayValues: List[JsValue] = js match { + case JsArray(values) => + values + case _ => + throw new IllegalArgumentException("Trying to select values from non-JsArray"+ js) + } +} + +object RichJsValue { + implicit def enrichJsValue(js: JsValue) = new RichJsValue(js) +} diff --git a/Scala/patmat/project/ScalaTestRunner.scala b/Scala/patmat/project/ScalaTestRunner.scala new file mode 100644 index 0000000..af63495 --- /dev/null +++ b/Scala/patmat/project/ScalaTestRunner.scala @@ -0,0 +1,169 @@ +import sbt._ +import Keys._ +import sys.process.{Process => SysProc, ProcessLogger} +import java.util.concurrent._ +import collection.mutable.ListBuffer + +object ScalaTestRunner { + + class LimitedStringBuffer { + val buf = new ListBuffer[String]() + private var lines = 0 + private var lengthCropped = false + + override def toString() = buf.mkString("\n").trim + + def append(s: String) = + if (lines < Settings.maxOutputLines) { + val shortS = + if (s.length > Settings.maxOutputLineLength) { + if (!lengthCropped) { + val msg = + """WARNING: OUTPUT LINES CROPPED + |Your program generates very long lines on the standard (or error) output. Some of + |the lines have been cropped. + |This should not have an impact on your grade or the grading process; however it is + |bad style to leave `print` statements in production code, so consider removing and + |replacing them by proper tests. + |""".stripMargin + buf.prepend(msg) + lengthCropped = true + } + s.substring(0, Settings.maxOutputLineLength) + } else s + buf.append(shortS) + lines += 1 + } else if (lines == Settings.maxOutputLines) { + val msg = + """WARNING: PROGRAM OUTPUT TOO LONG + |Your program generates massive amounts of data on the standard (or error) output. + |You are probably using `print` statements to debug your code. + |This should not have an impact on your grade or the grading process; however it is + |bad style to leave `print` statements in production code, so consider removing and + |replacing them by proper tests. + |""".stripMargin + buf.prepend(msg) + lines += 1 + } + } + + private def forkProcess(proc: SysProc, timeout: Int) { + val executor = Executors.newSingleThreadExecutor() + val future: Future[Unit] = executor.submit(new Callable[Unit] { + def call { proc.exitValue() } + }) + try { + future.get(timeout, TimeUnit.SECONDS) + } catch { + case to: TimeoutException => + future.cancel(true) + throw to + } finally { + executor.shutdown() + } + } + + private def runPathString(file: File) = file.getAbsolutePath().replace(" ", "\\ ") + + private def extractWeights(s: String, logError: String => Unit) = { + try { + val (nums, rest) = s.span(c => c != '\n') + val List(grade, max) = nums.split(';').toList + (grade.toInt, max.toInt, rest.drop(1)) + } catch { + case e: Throwable => + val msg = "Could not extract weight from grading feedback\n"+ s + logError(msg) + throw e + } + } + + + def runScalaTest(classpath: Classpath, testClasses: File, outfile: File, policyFile: File, resourceFiles: List[File], logError: String => Unit) = { + val classpathString = classpath map { + case Attributed(file) => file.getAbsolutePath() + } mkString(":") + + val testRunpath = runPathString(testClasses) + + val outfileStr = outfile.getAbsolutePath + val policyFileStr = policyFile.getAbsolutePath + val resourceFilesString = resourceFiles.map(_.getAbsolutePath).mkString(":") + // Deleting the file is helpful: it makes reading the file below crash in case ScalaTest doesn't + // run as expected. Problem is, it's hard to detect if ScalaTest ran successfully or not: it + // exits with non-zero if there are failed tests, and also if it crashes... + new java.io.File(outfileStr).delete() + + def prop(name: String, value: String) = "-D"+ name +"="+ value + + // we don't specify "-w packageToTest" - the build file only compiles the tests + // for the current project. so we don't need to do it again here. + val cmd = "java" :: + "-Djava.security.manager" :: + prop("java.security.policy", policyFileStr) :: + prop(Settings.scalaTestReportFileProperty, outfileStr) :: + prop(Settings.scalaTestIndividualTestTimeoutProperty, Settings.individualTestTimeout.toString) :: + prop(Settings.scalaTestReadableFilesProperty, resourceFilesString) :: + prop(Settings.scalaTestDefaultWeigthProperty, Settings.scalaTestDefaultWeigth.toString) :: + "-cp" :: classpathString :: + "org.scalatest.tools.Runner" :: + "-R" :: testRunpath :: + "-C" :: "grading.CourseraReporter" :: + Nil + + // process deadlocks in Runner.PassFailReporter.allTestsPassed on runDoneSemaphore.acquire() when + // something is wrong, e.g. when there's an error.. So we have to run it with a timeout. + + val out = new LimitedStringBuffer() + var p: SysProc = null + try { + p = SysProc(cmd).run(ProcessLogger(out.append(_), out.append(_))) + forkProcess(p, Settings.scalaTestTimeout) + } catch { + case e: TimeoutException => + val msg = "Timeout when running ScalaTest\n"+ out.toString() + logError(msg) + p.destroy() + sys.error(msg) + + case e: Throwable => + val msg = "Error occured while running the ScalaTest command\n"+ e.toString +"\n"+ out.toString() + logError(msg) + p.destroy() + throw e + } + + + val feedbackFileContent = try { + io.Source.fromFile(outfileStr).mkString + } catch { + case e: Throwable => + val msg = "Error occured while reading the output file of ScalaTest\n"+ e.toString +"\n"+ out.toString() + logError(msg) + throw e + } + + val (score, maxScore, feedback) = extractWeights(feedbackFileContent, logError) + val runLog = out.toString() + (score, maxScore, feedback, runLog) + } + + def scalaTestGrade(classpath: Classpath, testClasses: File, outfile: File, policyFile: File, resourceFiles: List[File]) { + val (score, maxScore, feedback, runLog) = runScalaTest(classpath, testClasses, outfile, policyFile, resourceFiles, GradingFeedback.testExecutionFailed) + if (score == maxScore) { + GradingFeedback.allTestsPassed() + } else { + val scaledScore = GradingFeedback.maxTestScore * score / maxScore + GradingFeedback.testsFailed(feedback, scaledScore) + } + + // The output `out` should in principle be empty: the reporter we use writes its results to a file. + // however, `out` contains valuable logs in case scalatest fails. We need to put them into the student + // feedback in order to have a chance of debugging problems. + + if (!runLog.isEmpty) { + GradingFeedback.testExecutionDebugLog(runLog) + } + } +} + diff --git a/Scala/patmat/project/Settings.scala b/Scala/patmat/project/Settings.scala new file mode 100644 index 0000000..c8de201 --- /dev/null +++ b/Scala/patmat/project/Settings.scala @@ -0,0 +1,48 @@ +object Settings { + // when changing this, also look at 'scripts/gradingImpl' and the files in s3/settings + // val courseId = "progfun-2012-001" + + def challengeUrl(courseId: String) = "https://class.coursera.org/"+ courseId +"/assignment/challenge" + + def submitUrl(courseId: String) = "https://class.coursera.org/"+ courseId +"/assignment/submit" + + // def forumUrl(courseId: String) = "https://class.coursera.org/"+ courseId +"/forum/index" + + // def submitQueueUrl(courseId: String) = "https://class.coursera.org/"+ courseId +"/assignment/api/pending_submission" + + def uploadFeedbackUrl(courseId: String) = "https://class.coursera.org/"+ courseId +"/assignment/api/score" + + val maxSubmitFileSize = { + val mb = 1024 * 1024 + 10 * mb + } + + val submissionDirName = "submission" + + val testResultsFileName = "scalaTestLog.txt" + val policyFileName = "allowAllPolicy" + val submissionJsonFileName = "submission.json" + val submissionJarFileName = "submittedSrc.jar" + + // time in seconds that we give scalatest for running + val scalaTestTimeout = 240 + val individualTestTimeout = 30 + + // default weight of each test in a GradingSuite, in case no weight is given + val scalaTestDefaultWeigth = 10 + + // when students leave print statements in their code, they end up in the output of the + // system process running ScalaTest (ScalaTestRunner.scala); we need some limits. + val maxOutputLines = 10*1000 + val maxOutputLineLength = 1000 + + val scalaTestReportFileProperty = "scalatest.reportFile" + val scalaTestIndividualTestTimeoutProperty = "scalatest.individualTestTimeout" + val scalaTestReadableFilesProperty = "scalatest.readableFiles" + val scalaTestDefaultWeigthProperty = "scalatest.defaultWeight" + + // debugging / developping options + + // don't decode json and unpack the submission sources, don't upload feedback + val offlineMode = false +} diff --git a/Scala/patmat/project/StyleChecker.scala b/Scala/patmat/project/StyleChecker.scala new file mode 100644 index 0000000..fbc1cdf --- /dev/null +++ b/Scala/patmat/project/StyleChecker.scala @@ -0,0 +1,77 @@ +import sbt.File +import java.io.ByteArrayOutputStream +import java.io.PrintStream +import org.scalastyle._ + +object StyleChecker { + val maxResult = 100 + + class CustomTextOutput[T <: FileSpec]() extends Output[T] { + private val messageHelper = new MessageHelper(this.getClass().getClassLoader()) + + var fileCount: Int = _ + override def message(m: Message[T]): Unit = m match { + case StartWork() => + case EndWork() => + case StartFile(file) => + print("Checking file " + file + "...") + fileCount = 0 + case EndFile(file) => + if (fileCount == 0) println(" OK!") + case StyleError(file, clazz, key, level, args, line, column, customMessage) => + report(line, column, messageHelper.text(level.name), + findMessage(messageHelper, clazz, key, args, customMessage)) + case StyleException(file, clazz, message, stacktrace, line, column) => + report(line, column, "error", message) + } + + private def report(line: Option[Int], column: Option[Int], level: String, message: String) { + if (fileCount == 0) println("") + fileCount += 1 + println(" " + fileCount + ". " + level + pos(line, column) + ":") + println(" " + message) + } + + private def pos(line: Option[Int], column: Option[Int]): String = line match { + case Some(line) => " at line " + line + (column match { + case Some(column) => " character " + column + case None => "" + }) + case None => "" + } + } + + def score(outputResult: OutputResult) = { + val penalties = outputResult.errors + outputResult.warnings + scala.math.max(maxResult - penalties, 0) + } + + def assess(allSources: Seq[File]): (String, Int) = { + val configFile = new File("project/scalastyle_config.xml").getAbsolutePath + + val sources = allSources.filterNot{ f => + val path = f.getAbsolutePath + path.contains("interpreter") || + path.contains("simulations") || + path.contains("fetchtweets") + } + + val messages = new ScalastyleChecker().checkFiles( + ScalastyleConfiguration.readFromXml(configFile), + Directory.getFiles(sources : _*)) + + val output = new ByteArrayOutputStream() + val outputResult = Console.withOut(new PrintStream(output)) { + new CustomTextOutput().output(messages) + } + + val msg = + output.toString + + "Processed " + outputResult.files + " file(s)\n" + + "Found " + outputResult.errors + " errors\n" + + "Found " + outputResult.warnings + " warnings\n" + + (if (outputResult.errors+outputResult.warnings > 0) "Consult the style guide at https://class.coursera.org/progfun-002/wiki/view?page=GradingPolicy" else "") + + (msg, score(outputResult)) + } +} diff --git a/Scala/patmat/project/build.properties b/Scala/patmat/project/build.properties new file mode 100644 index 0000000..4474a03 --- /dev/null +++ b/Scala/patmat/project/build.properties @@ -0,0 +1 @@ +sbt.version=0.12.1 diff --git a/Scala/patmat/project/buildSettings.sbt b/Scala/patmat/project/buildSettings.sbt new file mode 100644 index 0000000..1ed6540 --- /dev/null +++ b/Scala/patmat/project/buildSettings.sbt @@ -0,0 +1,72 @@ +// needed for custom scalastyle package +resolvers += "namin.github.com/maven-repository" at "http://namin.github.com/maven-repository/" + +resolvers += "Spray Repository" at "http://repo.spray.cc/" + +libraryDependencies += "net.databinder" %% "dispatch-http" % "0.8.8" + + libraryDependencies += "org.scalastyle" % "scalastyle_2.9.1" % "0.1.3-SNAPSHOT" + +libraryDependencies += "cc.spray" %% "spray-json" % "1.1.1" + +// need scalatest also as a build dependency: the build implements a custom reporter +libraryDependencies += "org.scalatest" %% "scalatest" % "1.9.1" + +// dispatch uses commons-codec, in version 1.4, so we can't go for 1.6. +// libraryDependencies += "commons-codec" % "commons-codec" % "1.4" + +libraryDependencies += "org.apache.commons" % "commons-lang3" % "3.1" + +// sbteclipse-plugin uses scalaz-core 6.0.3, so we can't go 6.0.4 +// libraryDependencies += "org.scalaz" %% "scalaz-core" % "6.0.3" + +scalacOptions ++= Seq("-deprecation") + +addSbtPlugin("com.typesafe.sbteclipse" % "sbteclipse-plugin" % "2.1.0") + +// for dependency-graph plugin +// net.virtualvoid.sbt.graph.Plugin.graphSettings + + +// [info] default:default-3fdafc_2.9.1:0.1-SNAPSHOT +// [info] +-cc.spray:spray-json_2.9.1:1.1.1 +// [info] | +-org.parboiled:parboiled-scala:1.0.2 +// [info] | | +-org.parboiled:parboiled-core:1.0.2 +// [info] | | +-org.scala-lang:scala-library:2.9.1 +// [info] | | +// [info] | +-org.scala-lang:scala-library:2.9.1 +// [info] | +// [info] +-com.typesafe.sbteclipse:sbteclipse-plugin:2.1.0 +// [info] | +-com.typesafe.sbteclipse:sbteclipse-core:2.1.0 +// [info] | +-org.scalaz:scalaz-core_2.9.1:6.0.3 +// [info] | +-org.scala-lang:scala-library:2.9.1 +// [info] | +// [info] +-net.databinder:dispatch-http_2.9.1:0.8.8 +// [info] | +-net.databinder:dispatch-core_2.9.1:0.8.8 +// [info] | | +-org.apache.httpcomponents:httpclient:4.1.3 +// [info] | | | +-commons-codec:commons-codec:1.4 +// [info] | | | +-commons-logging:commons-logging:1.1.1 +// [info] | | | +-org.apache.httpcomponents:httpcore:4.1.4 +// [info] | | | +// [info] | | +-org.scala-lang:scala-library:2.9.1 +// [info] | | +// [info] | +-net.databinder:dispatch-futures_2.9.1:0.8.8 +// [info] | | +-org.scala-lang:scala-library:2.9.1 +// [info] | | +// [info] | +-org.apache.httpcomponents:httpclient:4.1.3 +// [info] | | +-commons-codec:commons-codec:1.4 +// [info] | | +-commons-logging:commons-logging:1.1.1 +// [info] | | +-org.apache.httpcomponents:httpcore:4.1.4 +// [info] | | +// [info] | +-org.scala-lang:scala-library:2.9.1 +// [info] | +// [info] +-org.scala-lang:scala-library:2.9.1 +// [info] +-org.scalastyle:scalastyle_2.9.1:0.1.3-SNAPSHOT +// [info] | +-com.github.scopt:scopt_2.9.1:2.0.0 +// [info] | | +-org.scala-lang:scala-library:2.9.1 +// [info] | | +// [info] | +-org.scalariform:scalariform_2.9.1:0.1.1 +// [info] | +-org.scala-lang:scala-library:2.9.1 +// [info] | +// [info] +-org.scalatest:scalatest_2.9.1:1.8 +// [info] +-org.scala-lang:scala-library:2.9.1 diff --git a/Scala/patmat/project/project/buildPlugins.sbt b/Scala/patmat/project/project/buildPlugins.sbt new file mode 100644 index 0000000..47557f4 --- /dev/null +++ b/Scala/patmat/project/project/buildPlugins.sbt @@ -0,0 +1,2 @@ +// the dependency-graph plugin +// addSbtPlugin("net.virtual-void" % "sbt-dependency-graph" % "0.6.0") diff --git a/Scala/patmat/project/scalastyle_config.xml b/Scala/patmat/project/scalastyle_config.xml new file mode 100644 index 0000000..9171ed3 --- /dev/null +++ b/Scala/patmat/project/scalastyle_config.xml @@ -0,0 +1,136 @@ + + scalastyle Coursera Configuration + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Avoid isInstanceOf. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + Method name should not start with an upper case letter. + + + + + + + + + + + + + + + Avoid using mutable collections. + + + \ No newline at end of file diff --git a/Scala/patmat/src/main/scala/common/package.scala b/Scala/patmat/src/main/scala/common/package.scala new file mode 100644 index 0000000..f1c74c3 --- /dev/null +++ b/Scala/patmat/src/main/scala/common/package.scala @@ -0,0 +1,40 @@ +import java.io.File + +package object common { + + /** An alias for the `Nothing` type. + * Denotes that the type should be filled in. + */ + type ??? = Nothing + + /** An alias for the `Any` type. + * Denotes that the type should be filled in. + */ + type *** = Any + + + /** + * Get a child of a file. For example, + * + * subFile(homeDir, "b", "c") + * + * corresponds to ~/b/c + */ + def subFile(file: File, children: String*) = { + children.foldLeft(file)((file, child) => new File(file, child)) + } + + /** + * Get a resource from the `src/main/resources` directory. Eclipse does not copy + * resources to the output directory, then the class loader cannot find them. + */ + def resourceAsStreamFromSrc(resourcePath: List[String]): Option[java.io.InputStream] = { + val classesDir = new File(getClass.getResource(".").toURI) + val projectDir = classesDir.getParentFile.getParentFile.getParentFile.getParentFile + val resourceFile = subFile(projectDir, ("src" :: "main" :: "resources" :: resourcePath): _*) + if (resourceFile.exists) + Some(new java.io.FileInputStream(resourceFile)) + else + None + } +} diff --git a/Scala/patmat/src/main/scala/patmat/Huffman.scala b/Scala/patmat/src/main/scala/patmat/Huffman.scala new file mode 100644 index 0000000..a40c212 --- /dev/null +++ b/Scala/patmat/src/main/scala/patmat/Huffman.scala @@ -0,0 +1,206 @@ +package patmat + +import common._ + +/** + * Assignment 4: Huffman coding + * + */ +object Huffman { + + /** + * A huffman code is represented by a binary tree. + * + * Every `Leaf` node of the tree represents one character of the alphabet that the tree can encode. + * The weight of a `Leaf` is the frequency of appearance of the character. + * + * The branches of the huffman tree, the `Fork` nodes, represent a set containing all the characters + * present in the leaves below it. The weight of a `Fork` node is the sum of the weights of these + * leaves. + */ + abstract class CodeTree + case class Fork(left: CodeTree, right: CodeTree, chars: List[Char], weight: Int) extends CodeTree + case class Leaf(char: Char, weight: Int) extends CodeTree + + + + // Part 1: Basics + + def weight(tree: CodeTree): Int = ??? // tree match ... + + def chars(tree: CodeTree): List[Char] = ??? // tree match ... + + def makeCodeTree(left: CodeTree, right: CodeTree) = + Fork(left, right, chars(left) ::: chars(right), weight(left) + weight(right)) + + + + // Part 2: Generating Huffman trees + + /** + * In this assignment, we are working with lists of characters. This function allows + * you to easily create a character list from a given string. + */ + def string2Chars(str: String): List[Char] = str.toList + + /** + * This function computes for each unique character in the list `chars` the number of + * times it occurs. For example, the invocation + * + * times(List('a', 'b', 'a')) + * + * should return the following (the order of the resulting list is not important): + * + * List(('a', 2), ('b', 1)) + * + * The type `List[(Char, Int)]` denotes a list of pairs, where each pair consists of a + * character and an integer. Pairs can be constructed easily using parentheses: + * + * val pair: (Char, Int) = ('c', 1) + * + * In order to access the two elements of a pair, you can use the accessors `_1` and `_2`: + * + * val theChar = pair._1 + * val theInt = pair._2 + * + * Another way to deconstruct a pair is using pattern matching: + * + * pair match { + * case (theChar, theInt) => + * println("character is: "+ theChar) + * println("integer is : "+ theInt) + * } + */ + def times(chars: List[Char]): List[(Char, Int)] = ??? + + /** + * Returns a list of `Leaf` nodes for a given frequency table `freqs`. + * + * The returned list should be ordered by ascending weights (i.e. the + * head of the list should have the smallest weight), where the weight + * of a leaf is the frequency of the character. + */ + def makeOrderedLeafList(freqs: List[(Char, Int)]): List[Leaf] = ??? + + /** + * Checks whether the list `trees` contains only one single code tree. + */ + def singleton(trees: List[CodeTree]): Boolean = ??? + + /** + * The parameter `trees` of this function is a list of code trees ordered + * by ascending weights. + * + * This function takes the first two elements of the list `trees` and combines + * them into a single `Fork` node. This node is then added back into the + * remaining elements of `trees` at a position such that the ordering by weights + * is preserved. + * + * If `trees` is a list of less than two elements, that list should be returned + * unchanged. + */ + def combine(trees: List[CodeTree]): List[CodeTree] = ??? + + /** + * This function will be called in the following way: + * + * until(singleton, combine)(trees) + * + * where `trees` is of type `List[CodeTree]`, `singleton` and `combine` refer to + * the two functions defined above. + * + * In such an invocation, `until` should call the two functions until the list of + * code trees contains only one single tree, and then return that singleton list. + * + * Hint: before writing the implementation, + * - start by defining the parameter types such that the above example invocation + * is valid. The parameter types of `until` should match the argument types of + * the example invocation. Also define the return type of the `until` function. + * - try to find sensible parameter names for `xxx`, `yyy` and `zzz`. + */ + def until(xxx: ???, yyy: ???)(zzz: ???): ??? = ??? + + /** + * This function creates a code tree which is optimal to encode the text `chars`. + * + * The parameter `chars` is an arbitrary text. This function extracts the character + * frequencies from that text and creates a code tree based on them. + */ + def createCodeTree(chars: List[Char]): CodeTree = ??? + + + + // Part 3: Decoding + + type Bit = Int + + /** + * This function decodes the bit sequence `bits` using the code tree `tree` and returns + * the resulting list of characters. + */ + def decode(tree: CodeTree, bits: List[Bit]): List[Char] = ??? + + /** + * A Huffman coding tree for the French language. + * Generated from the data given at + * http://fr.wikipedia.org/wiki/Fr%C3%A9quence_d%27apparition_des_lettres_en_fran%C3%A7ais + */ + val frenchCode: CodeTree = Fork(Fork(Fork(Leaf('s',121895),Fork(Leaf('d',56269),Fork(Fork(Fork(Leaf('x',5928),Leaf('j',8351),List('x','j'),14279),Leaf('f',16351),List('x','j','f'),30630),Fork(Fork(Fork(Fork(Leaf('z',2093),Fork(Leaf('k',745),Leaf('w',1747),List('k','w'),2492),List('z','k','w'),4585),Leaf('y',4725),List('z','k','w','y'),9310),Leaf('h',11298),List('z','k','w','y','h'),20608),Leaf('q',20889),List('z','k','w','y','h','q'),41497),List('x','j','f','z','k','w','y','h','q'),72127),List('d','x','j','f','z','k','w','y','h','q'),128396),List('s','d','x','j','f','z','k','w','y','h','q'),250291),Fork(Fork(Leaf('o',82762),Leaf('l',83668),List('o','l'),166430),Fork(Fork(Leaf('m',45521),Leaf('p',46335),List('m','p'),91856),Leaf('u',96785),List('m','p','u'),188641),List('o','l','m','p','u'),355071),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u'),605362),Fork(Fork(Fork(Leaf('r',100500),Fork(Leaf('c',50003),Fork(Leaf('v',24975),Fork(Leaf('g',13288),Leaf('b',13822),List('g','b'),27110),List('v','g','b'),52085),List('c','v','g','b'),102088),List('r','c','v','g','b'),202588),Fork(Leaf('n',108812),Leaf('t',111103),List('n','t'),219915),List('r','c','v','g','b','n','t'),422503),Fork(Leaf('e',225947),Fork(Leaf('i',115465),Leaf('a',117110),List('i','a'),232575),List('e','i','a'),458522),List('r','c','v','g','b','n','t','e','i','a'),881025),List('s','d','x','j','f','z','k','w','y','h','q','o','l','m','p','u','r','c','v','g','b','n','t','e','i','a'),1486387) + + /** + * What does the secret message say? Can you decode it? + * For the decoding use the `frenchCode' Huffman tree defined above. + */ + val secret: List[Bit] = List(0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,0,0,0,1,0,1,1,1,0,0,1,0,0,1,0,0,0,1,0,0,0,1,0,1) + + /** + * Write a function that returns the decoded secret + */ + def decodedSecret: List[Char] = ??? + + + + // Part 4a: Encoding using Huffman tree + + /** + * This function encodes `text` using the code tree `tree` + * into a sequence of bits. + */ + def encode(tree: CodeTree)(text: List[Char]): List[Bit] = ??? + + + // Part 4b: Encoding using code table + + type CodeTable = List[(Char, List[Bit])] + + /** + * This function returns the bit sequence that represents the character `char` in + * the code table `table`. + */ + def codeBits(table: CodeTable)(char: Char): List[Bit] = ??? + + /** + * Given a code tree, create a code table which contains, for every character in the + * code tree, the sequence of bits representing that character. + * + * Hint: think of a recursive solution: every sub-tree of the code tree `tree` is itself + * a valid code tree that can be represented as a code table. Using the code tables of the + * sub-trees, think of how to build the code table for the entire tree. + */ + def convert(tree: CodeTree): CodeTable = ??? + + /** + * This function takes two code tables and merges them into one. Depending on how you + * use it in the `convert` method above, this merge method might also do some transformations + * on the two parameter code tables. + */ + def mergeCodeTables(a: CodeTable, b: CodeTable): CodeTable = ??? + + /** + * This function encodes `text` according to the code tree `tree`. + * + * To speed up the encoding process, it first converts the code tree to a code table + * and then uses it to perform the actual encoding. + */ + def quickEncode(tree: CodeTree)(text: List[Char]): List[Bit] = ??? +} diff --git a/Scala/patmat/src/test/scala/patmat/HuffmanSuite.scala b/Scala/patmat/src/test/scala/patmat/HuffmanSuite.scala new file mode 100644 index 0000000..3881871 --- /dev/null +++ b/Scala/patmat/src/test/scala/patmat/HuffmanSuite.scala @@ -0,0 +1,47 @@ +package patmat + +import org.scalatest.FunSuite + +import org.junit.runner.RunWith +import org.scalatest.junit.JUnitRunner + +import patmat.Huffman._ + +@RunWith(classOf[JUnitRunner]) +class HuffmanSuite extends FunSuite { + trait TestTrees { + val t1 = Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5) + val t2 = Fork(Fork(Leaf('a',2), Leaf('b',3), List('a','b'), 5), Leaf('d',4), List('a','b','d'), 9) + } + + test("weight of a larger tree") { + new TestTrees { + assert(weight(t1) === 5) + } + } + + test("chars of a larger tree") { + new TestTrees { + assert(chars(t2) === List('a','b','d')) + } + } + + test("string2chars(\"hello, world\")") { + assert(string2Chars("hello, world") === List('h', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd')) + } + + test("makeOrderedLeafList for some frequency table") { + assert(makeOrderedLeafList(List(('t', 2), ('e', 1), ('x', 3))) === List(Leaf('e',1), Leaf('t',2), Leaf('x',3))) + } + + test("combine of some leaf list") { + val leaflist = List(Leaf('e', 1), Leaf('t', 2), Leaf('x', 4)) + assert(combine(leaflist) === List(Fork(Leaf('e',1),Leaf('t',2),List('e', 't'),3), Leaf('x',4))) + } + + test("decode and encode a very short text should be identity") { + new TestTrees { + assert(decode(t1, encode(t1)("ab".toList)) === "ab".toList) + } + } +} -- cgit v1.1-2-g2b99