Implemented modifications Gimd database stored using JGit library.

While this functionality a number of changes to API has been made, mainly:
  * functionality of DatabaseSpi trait has been moved to Database trait
  * code from JGitProvider has been moved to JGitSnapshot as all operations
    should be executed on specific Snapshot of Database

Modifications itself are implemented by taking function that takes Snapshot
and returns DatabaseModification object which carries information about
modifications that should be applied on top of passed Snapshot. Then,
modified Snapshot is tried to be safely merged with latest Snapshot of
Database.

Also, made JGitDatabaseException to store reference to JGit repository
that was in use when exception had been thrown.

Change-Id: I3f1cbcc89559569c831441e87c533627f3a78c10
Signed-off-by: Grzegorz Kossakowski <grek@google.com>

9 files changed, 334 insertions, 40 deletions

diff --git a/src/main/scala/com/google/gimd/Database.scala b/src/main/scala/com/google/gimd/Database.scala
new file mode 100644
index 0000000..9047606
--- /dev/null
+++ b/src/main/scala/com/google/gimd/Database.scala
@@ -0,0 +1,57 @@
+// Copyright (C) 2009 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gimd
+
+import file.FileType
+import modification.DatabaseModification
+import query.Predicate
+
+trait Database {
+
+  /**
+   * Query database for all user objects of type U stored in files of
+   * type FileType[W] satisfying predicate p using latest Snapshot of Database.
+   *
+   * @throws GimdException
+   */
+  @throws(classOf[GimdException])
+  def query[U,W](ft: FileType[W], p: Predicate[U]): Iterator[U] =
+    //this method forgets about handles as this method is not run in context of any Snapshot so they
+    //become invalid immediately
+    latestSnapshot.query(ft, p).map(_._2)
+
+  /**
+   * <p>Method that allows modification of latest Snapshot of Database.</p>
+   *
+   * <p>For single DatabaseModification derived from Snapshot READ COMMITTED level of isolation is
+   * guaranteed. <strong>The level of isolation might be changed in a future but only to level which
+   * provides better isolation.</strong></p>
+   *
+   * @param modification A function <code>Snapshot => DatabaseModification</code> that should
+   *                     follow referential transparency rule as it can be called an arbitrary
+   *                     number of times. Result of this function is an object that specifies what
+   *                     kind of modifications should be performed on top of passed Snapshot.
+   *
+   * @throws GimdException
+   */
+  @throws(classOf[GimdException])
+  def modify(modification: Snapshot => DatabaseModification)
+
+  /**
+   * Factory method returning latest Snapshot of Database.
+   */
+  protected def latestSnapshot: Snapshot
+
+}
diff --git a/src/main/scala/com/google/gimd/DatabaseSpi.scala b/src/main/scala/com/google/gimd/Snapshot.scala
index 05cd146..6ee5208 100644
--- a/src/main/scala/com/google/gimd/DatabaseSpi.scala
+++ b/src/main/scala/com/google/gimd/Snapshot.scala
@@ -17,21 +17,15 @@ package com.google.gimd
 import file.{File, FileType}
 import query.{Predicate, Handle}
 
-/**
- * Trait that provides all functionality for Gimd to ask specific storage implementation
- * for needed data in an efficient way.
- */
-trait DatabaseSpi {
-
-  /**
-   * @return iterator over collection of all Files that conform to passed FileType[T].
-   */
-  def all[T](fileType: FileType[T]): Iterator[File[T]]
+trait Snapshot {
 
   /**
    * Query database for all user objects of type U stored in files of
    * type FileType[W] satisfying predicate p.
+   *
+   * @throws GimdException
    */
+  @throws(classOf[GimdException])
   def query[U,W](ft: FileType[W], p: Predicate[U]): Iterator[(Handle[U],U)] = {
     for {
       f <- all(ft)
@@ -39,4 +33,9 @@ trait DatabaseSpi {
     } yield r
   }
 
+  /**
+   * @return iterator over collection of all Files that conform to passed FileType[T].
+   */
+  protected def all[T](fileType: FileType[T]): Iterator[File[T]]
+
 }
diff --git a/src/main/scala/com/google/gimd/jgit/JGitDatabase.scala b/src/main/scala/com/google/gimd/jgit/JGitDatabase.scala
new file mode 100644
index 0000000..0b02a6f
--- /dev/null
+++ b/src/main/scala/com/google/gimd/jgit/JGitDatabase.scala
@@ -0,0 +1,157 @@
+// Copyright (C) 2009 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gimd.jgit
+
+import file.{FileType, File}
+import java.io.{IOException, ByteArrayInputStream}
+import text.Formatter
+import modification.DatabaseModification
+import org.spearce.jgit.lib._
+import org.spearce.jgit.merge.MergeStrategy
+import org.spearce.jgit.lib.RefUpdate.Result
+import org.spearce.jgit.dircache.{DirCache, DirCacheEditor, DirCacheEntry}
+import org.spearce.jgit.revwalk.{RevCommit, RevTree, RevWalk}
+
+final class JGitDatabase(repository: Repository) extends Database {
+
+  /**
+   * The maximal number of merge/transaction rebase retries.
+   *
+   * If this number of retries is reached attempt to apply modifications will be aborted by throwing
+   * an exception.
+   *
+   * This boundary is needed in order to avoid resource starvation, specifically - livelock. It may
+   * happen when there is another process constantly changing latest Snapshot so modification has to
+   * be constantly remerged or even rebased. Proper solution to this problem should be fixing
+   * scheduling algorithm that would assign priority to each modification task which is proportional
+   * to number of retries given task already performed.
+   *
+   * Unfortunately we don't have control over scheduling threads here.
+   */
+  private val MERGE_RETRIES = 10
+
+  def latestSnapshot: JGitSnapshot = {
+    try {
+      val id = repository.resolve(Constants.HEAD)
+      new JGitSnapshot(repository, new RevWalk(repository).parseCommit(id))
+    } catch {
+      case e: IOException => throw new JGitDatabaseException(repository, e)
+    }
+  }
+
+  def modify(modification: Snapshot => DatabaseModification) = {
+    val successful = try {
+      retry(MERGE_RETRIES) {
+        val snapshot = latestSnapshot
+        val dbModification = modification(snapshot)
+        applyModification(dbModification, Constants.HEAD, snapshot.commit)
+      }
+    } catch {
+      case e: IOException => throw new JGitDatabaseException(repository, e)
+    }
+
+    if (!successful)
+      throw new JGitMergeRetriesExceededException(repository, MERGE_RETRIES)
+  }
+
+  def applyModification(modification: DatabaseModification, branch: String, onto: RevCommit):
+    Boolean = {
+    val treeId = writeMessages(modification, onto.getTree)
+    val commitId = createCommit(treeId, onto)
+    val result = updateRef(branch, onto, commitId)
+    result match {
+      //there was no change to database since onto commit so changes were applied cleanly
+      case Result.FAST_FORWARD => true
+      //if there was a change since onto commit update gets rejected. Still it might be that change
+      //did not affected files we are trying to modify. Thus we are trying merging both changes.
+      case Result.REJECTED => tryMerging(branch, commitId)
+      //TODO: There should be a special treatment of LOCK_FAILURE case but it's low-priority task
+      //the idea is to not try merging if just JGit fails to obtain lock for given reference
+      case _ =>
+        throw new JGitDatabaseException(repository,
+                                        "RefUpdate returned unexpected result: %1s.".format(result))
+    }
+  }
+
+  private def updateRef(name: String, oldCommit: ObjectId, newCommit: ObjectId): Result = {
+    val refUpdate = repository.updateRef(name)
+    refUpdate.setExpectedOldObjectId(oldCommit)
+    refUpdate.setNewObjectId(newCommit)
+    refUpdate.update()
+  }
+
+  private def createCommit(treeId: ObjectId, parents: ObjectId*): ObjectId = {
+    //TODO: This identity should be replaced with something more meaningful
+    val ident = new PersonIdent("A U Thor", "author@example.com")
+    val commit = new Commit(repository, Array(parents: _*))
+    commit.setTreeId(treeId)
+    commit.setAuthor(ident)
+    commit.setCommitter(ident)
+    commit.setMessage("Comitted by Gimd.\n")
+    commit.commit()
+    commit.getCommitId
+  }
+
+  private def writeMessages(modification: DatabaseModification, oldTree: RevTree): ObjectId = {
+    val dirCache = DirCache.newInCore
+    val builder = dirCache.builder
+    builder.addTree(new Array[byte](0), 0, repository, oldTree)
+    builder.finish
+
+    val objectWriter = new ObjectWriter(repository)
+    class EditMessage(file: File[_], newMsg: Message) extends DirCacheEditor.PathEdit(file.path) {
+      def apply(entry: DirCacheEntry) {
+        val text = Formatter.format(newMsg)
+        val blobId = objectWriter.writeBlob(text.getBytes(Constants.CHARACTER_ENCODING))
+        entry.setFileMode(FileMode.REGULAR_FILE)
+        entry.setObjectId(blobId)
+      }
+    }
+    val editor = dirCache.editor
+    for ((file, message) <- modification.reduce) {
+      message match {
+        case None => editor.add(new DirCacheEditor.DeletePath(file.path))
+        case Some(x) => editor.add(new EditMessage(file, x))
+      }
+    }
+    editor.finish
+    dirCache.writeTree(objectWriter)
+  }
+
+  private def merge(branch: String, commitToBeMerged: ObjectId): Boolean = {
+    val baseCommit = repository.resolve(branch)
+    val merger = MergeStrategy.SIMPLE_TWO_WAY_IN_CORE.newMerger(repository)
+    if (merger.merge(baseCommit, commitToBeMerged)) {
+      val treeId = merger.getResultTreeId
+      val mergeCommit = createCommit(treeId, baseCommit, commitToBeMerged)
+      val result = updateRef(branch, baseCommit, mergeCommit)
+      Result.FAST_FORWARD == result
+    } else
+      false
+  }
+
+  private def tryMerging(branch: String, commitToBeMerged: ObjectId) =
+    retry(MERGE_RETRIES)(merge(branch, commitToBeMerged))
+
+  private def retry(howManyTimes: Int)(what: => Boolean): Boolean =
+    if (howManyTimes > 0)
+      if (what)
+        true
+      else
+        retry(howManyTimes-1)(what)
+    else
+      false
+
+}
diff --git a/src/main/scala/com/google/gimd/jgit/JGitProviderException.scala b/src/main/scala/com/google/gimd/jgit/JGitDatabaseException.scala
index df0f3d6..1245df9 100644
--- a/src/main/scala/com/google/gimd/jgit/JGitProviderException.scala
+++ b/src/main/scala/com/google/gimd/jgit/JGitDatabaseException.scala
@@ -14,9 +14,14 @@
 
 package com.google.gimd.jgit
 
-class JGitProviderException(message: String, cause: Throwable)
-        extends DatabaseSpiException(message, cause) {
 
-  def this(message: String) = this(message, null)
+import org.spearce.jgit.lib.Repository
 
+class JGitDatabaseException(val repository: Repository,
+                            val msg: String,
+                            val cause: Throwable) extends GimdException(msg, cause) {
+
+  def this(repository: Repository, msg: String) = this(repository, msg, null)
+
+  def this(repository: Repository, cause: Throwable) = this(repository, null, cause)
 }
diff --git a/src/main/scala/com/google/gimd/jgit/JGitFile.scala b/src/main/scala/com/google/gimd/jgit/JGitFile.scala
index 9ff43cd..dd110d5 100644
--- a/src/main/scala/com/google/gimd/jgit/JGitFile.scala
+++ b/src/main/scala/com/google/gimd/jgit/JGitFile.scala
@@ -20,15 +20,15 @@ import org.spearce.jgit.lib.{ObjectId, Repository}
 import text.Parser
 
 final class JGitFile[T](val path: String, val blobId: ObjectId, val fileType: FileType[T],
-                        val jgitRepository: Repository) extends File[T] {
+                        val repository: Repository) extends File[T] {
 
   lazy val message = Parser.parse(new InputStreamReader(blobInputStream, "UTF-8"))
   lazy val userObject = fileType.userType.toUserObject(message)
 
   private lazy val blobInputStream = {
-    val objectLoader = jgitRepository.openBlob(blobId)
+    val objectLoader = repository.openBlob(blobId)
     if (objectLoader == null)
-      throw new JGitProviderException("Blob '" + blobId.name + "' does not exist.")
+      throw new JGitDatabaseException(repository, "Blob '" + blobId.name + "' does not exist.")
 
     new ByteArrayInputStream(objectLoader.getCachedBytes)
   }
diff --git a/src/main/scala/com/google/gimd/jgit/JGitMergeRetriesExceededException.scala b/src/main/scala/com/google/gimd/jgit/JGitMergeRetriesExceededException.scala
new file mode 100644
index 0000000..b982850
--- /dev/null
+++ b/src/main/scala/com/google/gimd/jgit/JGitMergeRetriesExceededException.scala
@@ -0,0 +1,26 @@
+// Copyright (C) 2009 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gimd.jgit
+
+import org.spearce.jgit.lib.Repository
+
+/**
+ * An exception thrown in a case when modifications cannot be applied to JGitDatabase.
+ *
+ * @see JGitDatabase
+ */
+class JGitMergeRetriesExceededException(override val repository: Repository, val retries: Int)
+        extends JGitDatabaseException(repository, ("Tried to rebase transaction %1s times and " +
+                "failed to merge changes successfuly. Aborting.").format(retries))
diff --git a/src/main/scala/com/google/gimd/jgit/JGitProvider.scala b/src/main/scala/com/google/gimd/jgit/JGitSnapshot.scala
index be9f47d..2fd01ef 100644
--- a/src/main/scala/com/google/gimd/jgit/JGitProvider.scala
+++ b/src/main/scala/com/google/gimd/jgit/JGitSnapshot.scala
@@ -14,23 +14,16 @@
 
 package com.google.gimd.jgit
 
-import file.{FileType, File}
-import org.spearce.jgit.lib._
-import org.spearce.jgit.revwalk.{RevCommit, RevWalk}
-import org.spearce.jgit.treewalk.filter.{AndTreeFilter, PathFilter, PathSuffixFilter}
-import org.spearce.jgit.treewalk.filter.TreeFilter
+import file.{File, FileType}
+import org.spearce.jgit.lib.{Repository, FileMode}
+import org.spearce.jgit.revwalk.RevCommit
+import org.spearce.jgit.treewalk.filter.{PathFilter, PathSuffixFilter, AndTreeFilter, TreeFilter}
 import org.spearce.jgit.treewalk.TreeWalk
 
-final class JGitProvider(val jgitRepository: Repository) extends DatabaseSpi {
+final class JGitSnapshot(val repository: Repository, val commit: RevCommit) extends Snapshot {
 
   def all[T](fileType: FileType[T]): Iterator[File[T]] = {
-    val id = jgitRepository.resolve(Constants.HEAD)
-    val rw = new RevWalk(jgitRepository)
-    all(fileType, rw.parseCommit(id))
-  }
-
-  private def all[T](fileType: FileType[T], commit: RevCommit): Iterator[File[T]] = {
-    val treeWalk = new TreeWalk(jgitRepository)
+    val treeWalk = new TreeWalk(repository)
     treeWalk.reset(commit.getTree)
     treeWalk.setRecursive(true)
     treeWalk.setFilter(treeFilter(fileType))
@@ -42,7 +35,7 @@ final class JGitProvider(val jgitRepository: Repository) extends DatabaseSpi {
         if (!hasNext)
           throw new NoSuchElementException
         val result =
-          new JGitFile(treeWalk.getPathString, treeWalk.getObjectId(0), fileType, jgitRepository)
+          new JGitFile(treeWalk.getPathString, treeWalk.getObjectId(0), fileType, repository)
         doesHasNext = treeWalk.next
         result
       }
diff --git a/src/test/scala/com/google/gimd/jgit/JGitProviderTestCase.scala b/src/test/scala/com/google/gimd/jgit/JGitDatabaseTestCase.scala
index 1c32f6e..14ad484 100644
--- a/src/test/scala/com/google/gimd/jgit/JGitProviderTestCase.scala
+++ b/src/test/scala/com/google/gimd/jgit/JGitDatabaseTestCase.scala
@@ -15,11 +15,13 @@
 package com.google.gimd.jgit
 
 import file.{File, FileType}
+import modification.DatabaseModification
 import org.junit.Test
 import org.junit.Assert._
-import org.spearce.jgit.lib.ObjectId
+import org.spearce.jgit.lib.{Constants, ObjectId}
+import query.Predicate
 
-final class JGitProviderTestCase extends AbstractJGitTestCase {
+final class JGitDatabaseTestCase extends AbstractJGitTestCase {
 
   case class SimpleMessage(name: String, value: Int)
 
@@ -50,9 +52,9 @@ final class JGitProviderTestCase extends AbstractJGitTestCase {
     )
     commit(files)
 
-    val db = new JGitProvider(repository)
+    val db = new JGitDatabase(repository)
 
-    val foundFiles = db.all(SimpleMessageFileType).toList
+    val foundFiles = db.latestSnapshot.all(SimpleMessageFileType).toList
 
     val expected = List("sm/first.sm", "sm/second.sm")
     assertEquals(expected, foundFiles.map(_.path))
@@ -70,9 +72,9 @@ final class JGitProviderTestCase extends AbstractJGitTestCase {
     )
     commit(files)
 
-    val db = new JGitProvider(repository)
+    val db = new JGitDatabase(repository)
 
-    val foundFiles = db.all(SimpleMessageFileType).toList
+    val foundFiles = db.latestSnapshot.all(SimpleMessageFileType).toList
 
     val expected = List(first, second)
     assertEquals(expected, foundFiles.map(_.userObject))
@@ -91,12 +93,68 @@ final class JGitProviderTestCase extends AbstractJGitTestCase {
     val commitId = createCommit("Test commit", treeId)
     moveHEAD(commitId)
 
-    val db = new JGitProvider(repository)
+    val db = new JGitDatabase(repository)
 
-    val foundFiles = db.all(SimpleMessageFileType).toList
+    val foundFiles = db.latestSnapshot.all(SimpleMessageFileType).toList
     assertEquals(Nil, foundFiles)
   }
 
+  @Test
+  def modifySimpleMessages {
+    import query.Predicate.functionLiteral2Predicate
+
+    val first = SimpleMessage("first", 1)
+    val second = SimpleMessage("second", 2)
+
+    val files = List(
+      ("sm/first.sm", writeMessage(SimpleMessageType, first)),
+      ("sm/second.sm", writeMessage(SimpleMessageType, second))
+    )
+    commit(files)
+
+    val db = new JGitDatabase(repository)
+
+    db.modify { snapshot =>
+      val sms = snapshot.query(SimpleMessageFileType, (sm: SimpleMessage) => sm.name == "second")
+      sms.foldLeft(DatabaseModification.empty) {
+        case (m, (h, sm)) => m.modify(h, SimpleMessage(sm.name, sm.value+1))
+      }
+    }
+
+    val foundFiles = db.latestSnapshot.all(SimpleMessageFileType).toList
+
+    val expected = List(first, SimpleMessage(second.name, second.value+1))
+    assertEquals(expected, foundFiles.map(_.userObject))
+  }
+
+  @Test
+  def deleteSimpleMessage {
+    import query.Predicate.functionLiteral2Predicate
+
+    val first = SimpleMessage("first", 1)
+    val second = SimpleMessage("second", 2)
+
+    val files = List(
+      ("sm/first.sm", writeMessage(SimpleMessageType, first)),
+      ("sm/second.sm", writeMessage(SimpleMessageType, second))
+    )
+    commit(files)
+
+    val db = new JGitDatabase(repository)
+
+    db.modify { snapshot =>
+      val sms = snapshot.query(SimpleMessageFileType, (sm: SimpleMessage) => sm.name == "second")
+      sms.foldLeft(DatabaseModification.empty) {
+        case (m, (h, sm)) => m.remove(h)
+      }
+    }
+
+    val foundFiles = db.latestSnapshot.all(SimpleMessageFileType).toList
+
+    val expected = List(first)
+    assertEquals(expected, foundFiles.map(_.userObject))
+  }
+
   private def commit(files: List[(String, ObjectId)]) {
     val treeId = addFiles(files)
     val commitId = createCommit("Test", treeId)
diff --git a/src/test/scala/com/google/gimd/jgit/JGitFileTestCase.scala b/src/test/scala/com/google/gimd/jgit/JGitFileTestCase.scala
index 4afd003..ec1a7ee 100644
--- a/src/test/scala/com/google/gimd/jgit/JGitFileTestCase.scala
+++ b/src/test/scala/com/google/gimd/jgit/JGitFileTestCase.scala
@@ -14,7 +14,6 @@
 
 package com.google.gimd.jgit
 
-
 import file.FileType
 import junit.framework.Assert._
 import org.junit.Test
@@ -61,7 +60,7 @@ class JGitFileTestCase extends AbstractJGitTestCase {
     assertEquals(expected, jGitFile.userObject)
   }
 
-  @Test{val expected = classOf[JGitProviderException]}
+  @Test{val expected = classOf[JGitDatabaseException]}
   def testMessageOfNonExistingObject {
     val jGitFile = new JGitFile("test", ObjectId.zeroId, SimpleMessageFileType, repository)
     jGitFile.message