4

Should I use RegexParsers, StandardTokenParsers or are these suitable at all for parsing this kind of syntax? Example of the syntax can be found from here.

4 Answers 4

5

I'd use regex. It simplifies a few things, and makes the rest standard.

def process(src: scala.io.Source) {
  import scala.util.matching.Regex

  val FilePattern = """(.*) ''(.*)''"""
  val OriginalFile = new Regex("--- "+FilePattern, "path", "timestamp")
  val NewFile = new Regex("+++ "+FilePattern, "path", "timestamp")
  val Chunk = new Regex("""@@ -(\d+),(\d+) +(\d+),(\d+) @@""", "orgStarting", "orgSize", "newStarting", "newSize")
  val AddedLine = """+(.*)""".r
  val RemovedLine = """-(.*)""".r
  val UnchangedLine = """ (.*)""".r

  src.getLines() foreach {
    case OriginalFile(path, timestamp) => println("Original file: "+path)
    case NewFile(path, timestamp) => println("New file: "+path)
    case Chunk(l1, s1, l2, s2) => println("Modifying %d lines at line %d, to %d lines at %d" format (s1, l1, s2, l2))
    case AddedLine(line) => println("Adding line "+line)
    case RemovedLine(line) => println("Removing line "+line)
    case UnchangedLine(line) => println("Keeping line "+line)
  }
}
2
  • I was hoping to be able to use parser combinators to get rid of keeping the state myself. I'm building an object graph out of the patch details something like that I have a Patch that contains FileModifications that contain Chunks. It seems that parser combinators could offer easier way to create objects out of parsed things instead of building the object graph on some variables on the way and tracking the parsing state.
    – JtR
    Aug 24, 2010 at 20:22
  • Btw, I didn't know that regexps can be used in pattern matching like that, very neat!
    – JtR
    Aug 24, 2010 at 20:26
4

This format was designed to be easy to parse, you can do it without any regular expressions and without tokenizing your input. Just go line by line and look at the first couple of characters. The file header and chunks headers will require a little more attention, but it's nothing you can't do with split.

Of course, if you want to learn how to use some parsing libraries, then go for it.

2
  • 2
    Years ago, in my first week of programming, I started creating patches for Nethack. Not knowing about diff, I started writing the damn things by hand. You can imagine my embarrassment when someone in the newsgroup politely informed me that I might be out of my mind. Well, anyway not only are unified diffs easy to parse, they're actually not so hard to write by hand either. :)
    – guns
    Aug 24, 2010 at 19:25
  • I wouldn't want to explicitly keep the state myself and learning to use the parser combinators is also one of my goals. On most of the examples there is some programming language kind of syntax to be parsed, but I was wondering couldn't the parser combinators also be used for parsing diff syntax or even binary formats.
    – JtR
    Aug 24, 2010 at 20:25
3

Here is a solution using RegexParsers.

import scala.util.parsing.combinator.RegexParsers

object UnifiedDiffParser extends RegexParsers {

  // case classes representing the data of the diff
  case class UnifiedDiff(oldFile: File, newFile: File, changeChunks: List[ChangeChunk])
  case class File(name: String, timeStamp: String)
  case class ChangeChunk(rangeInformation: RangeInformation, changeLines: List[String])
  case class RangeInformation(oldOffset: Int, oldLength: Int, newOffset: Int, newLength: Int)

  override def skipWhitespace = false

  def unifiedDiff: Parser[UnifiedDiff] = oldFile ~ newFile ~ rep1(changeChunk) ^^ {
    case of ~ nf ~ l => UnifiedDiff(of, nf, l)
  }   

  def oldFile: Parser[File] = ("--- " ~> filename) ~ ("""\s+""".r ~> timestamp <~ newline) ^^ {
    case f~t => File(f, t)
  }   
  def newFile: Parser[File] = ("+++ " ~> filename) ~ ("""\s+""".r ~> timestamp <~ newline) ^^ {
    case f~t => File(f, t)
  }   
  def filename: Parser[String] = """[\S]+""".r
  def timestamp: Parser[String] = """.*""".r

  def changeChunk: Parser[ChangeChunk] = rangeInformation ~ (newline ~> rep1(lineChange)) ^^ {
    case ri ~ l => ChangeChunk(ri, l)
  }   
  def rangeInformation: Parser[RangeInformation] = ("@@ " ~> "-" ~> number) ~ ("," ~> number) ~ (" +" ~> number) ~ ("," ~> number) <~ " @@" ^^ {
    case a ~ b ~ c ~ d => RangeInformation(a, b, c, d)
  }   

  def lineChange: Parser[String] = contextLine | addedLine | deletedLine
  def contextLine: Parser[String] = """ .*""".r <~ newline
  def addedLine: Parser[String] = """\+.*""".r <~ newline
  def deletedLine: Parser[String] = """-.*""".r <~ newline

  def newline: Parser[String] = """\n""".r
  def number: Parser[Int] = """\d+""".r ^^ {_.toInt}

  def main(args: Array[String]) {
    val reader = { 
      if (args.length == 0) {
        // read from stdin
        Console.in
      } else {
        new java.io.FileReader(args(0))
      }   
    }   
    println(parseAll(unifiedDiff, reader))
  }   
}   
0
1

Stumbled onto this while looking to build a Scala parser for a git diff, as generated by running git diff-tree. This is very similar to unified diff, but it does have a few interesting variants.

I heavily relied on an answer above, and ended up writing the parser included here. It's not strictly what the original poster was after of course, but I figured it could be useful to others.

import util.parsing.combinator._

object GitDiff {
  // file names have "a/" or "b/" as prefix, need to drop that to compare
  def apply (files: (String,String), op: FileOperation, chunks: List[ChangeChunk]) = {
    def strip(s: String) = s.dropWhile(_ != '/').drop(1)
    new GitDiff( strip( files._1 ), strip( files._2 ), op, chunks )
  }
}

case class GitDiff(oldFile: String, newFile: String, op: FileOperation, chunks: List[ChangeChunk]) {
  val isRename = oldFile != newFile
}

sealed trait FileOperation
case class NewFile(mode: Int) extends FileOperation
case class DeletedFile(mode: Int) extends FileOperation
case object UpdatedFile extends FileOperation

sealed trait LineChange { def line: String }
case class ContextLine(line: String) extends LineChange
case class LineRemoved(line: String) extends LineChange
case class LineAdded(line: String) extends LineChange
case class RangeInformation(oldOffset: Int, oldLength: Int, newOffset: Int, newLength: Int)
case class ChangeChunk(rangeInformation: RangeInformation, changeLines: List[LineChange])

// Code taken from http://stackoverflow.com/questions/3560073/how-to-write-parser-for-unified-diff-syntax
object GitDiffParser extends RegexParsers {

  override def skipWhitespace = false

  def allDiffs: Parser[List[GitDiff]] = rep1(gitDiff)

  def gitDiff: Parser[GitDiff] = filesChanged ~ fileOperation ~ diffChunks ^^ {
    case files ~ op ~ chunks => GitDiff(files, op, chunks)
  }

  def filesChanged: Parser[(String, String)] =
    "diff --git " ~> filename ~ (" " ~> filename) <~ newline ^^ { case f1 ~ f2 => (f1,f2) }

  def fileOperation: Parser[FileOperation] =
    opt(deletedFileMode | newFileMode) <~ index ^^ { _ getOrElse UpdatedFile }

  def index: Parser[Any] = ( "index " ~ hash ~ ".." ~ hash ) ~> opt(" " ~> mode) <~ newline
  def deletedFileMode: Parser[DeletedFile] = "deleted file mode " ~> mode <~ newline ^^ { m => DeletedFile(m) }
  def newFileMode: Parser[NewFile] = "new file mode " ~> mode <~ newline ^^ { m => NewFile(m) }
  def hash: Parser[String] = """[0-9a-f]{7}""".r
  def mode: Parser[Int] = """\d{6}""".r ^^ { _.toInt }

  def diffChunks: Parser[List[ChangeChunk]] = (oldFile ~ newFile) ~> rep1(changeChunk)

  def oldFile: Parser[String] = "--- " ~> filename <~ newline
  def newFile: Parser[String] = "+++ " ~> filename <~ newline
  def filename: Parser[String] = """[\S]+""".r

  def changeChunk: Parser[ChangeChunk] = rangeInformation ~ opt(contextLine) ~ (opt(newline) ~> rep1(lineChange)) ^^ {
    case ri ~ opCtx ~ lines => ChangeChunk(ri, opCtx map (_ :: lines) getOrElse (lines))
  }
  def rangeInformation: Parser[RangeInformation] =
    ("@@ " ~> "-" ~> number) ~ opt("," ~> number) ~ (" +" ~> number) ~ opt("," ~> number) <~ " @@" ^^ {
      case a ~ b ~ c ~ d => RangeInformation(a, b getOrElse 0, c, d getOrElse 0)
    }

  def lineChange: Parser[LineChange] = contextLine | addedLine | deletedLine
  def contextLine: Parser[ContextLine] = " " ~> """.*""".r <~ newline ^^ { l => ContextLine(l) }
  def addedLine: Parser[LineAdded] = "+" ~> """.*""".r <~ newline ^^ { l => LineAdded(l) }
  def deletedLine: Parser[LineRemoved] = "-" ~> """.*""".r <~ newline ^^ { l => LineRemoved(l) }

  def newline: Parser[String] = """\n""".r
  def number: Parser[Int] = """\d+""".r ^^ { _.toInt }

  def parse(str: String) = parseAll(allDiffs, str)

  def main(args: Array[String]) {
    val reader = {
      if (args.length == 0) {
        // read from stdin
        Console.in
      } else {
        new java.io.FileReader(args(0))
      }
    }
    parseAll(allDiffs, reader) match {
      case Success(s,_) => println( s )
      case NoSuccess(msg,_) => sys.error("ERROR: " + msg)
    }
  }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.