1
/*
2
* This file is part of the diffson project.
3
*
4
* Licensed under the Apache License, Version 2.0 (the "License");
5
* you may not use this file except in compliance with the License.
6
* You may obtain a copy of the License at
7
*
8
* http://www.apache.org/licenses/LICENSE-2.0
9
*
10
* Unless required by applicable law or agreed to in writing, software
11
* distributed under the License is distributed on an "AS IS" BASIS,
12
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
* See the License for the specific language governing permissions and
14
* limitations under the License.
15
*/
16
package diffson
17
package jsonpatch
18

19
import lcs._
20
import jsonpointer._
21

22
import cats.implicits._
23

24
import scala.annotation.tailrec
25

26
class JsonDiff[Json](diffArray: Boolean, rememberOld: Boolean)(implicit J: Jsony[Json], Lcs: Lcs[Json]) extends Diff[Json, JsonPatch[Json]] {
27
  def diff(json1: Json, json2: Json): JsonPatch[Json] =
28 1
    JsonPatch(diff(json1, json2, Pointer.Root))
29

30
  private def diff(json1: Json, json2: Json, pointer: Pointer): List[Operation[Json]] =
31 1
    if (json1 === json2)
32
      // if they are equal, this one is easy...
33 1
      Nil
34 1
    else (json1, json2) match {
35 1
      case (JsObject(fields1), JsObject(fields2))      => fieldsDiff(fields1.toList, fields2.toList, pointer)
36 1
      case (JsArray(arr1), JsArray(arr2)) if diffArray => arraysDiff(arr1.toList, arr2.toList, pointer)
37 1
      case (_, _)                                      => List(Replace(pointer, json2, if (rememberOld) Some(json1) else None))
38
    }
39

40
  private def fieldsDiff(fields1: List[(String, Json)], fields2: List[(String, Json)], path: Pointer): List[Operation[Json]] = {
41
    // sort fields by name in both objects
42 1
    val sorted1 = fields1.sortBy(_._1)
43 1
    val sorted2 = fields2.sortBy(_._1)
44
    @tailrec
45
    def associate(
46
      fields1: List[(String, Json)],
47
      fields2: List[(String, Json)],
48
      acc: List[(Option[(String, Json)], Option[(String, Json)])]): List[(Option[(String, Json)], Option[(String, Json)])] = (fields1, fields2) match {
49 1
      case (f1 :: t1, f2 :: t2) if f1._1 == f2._1 =>
50
        // same name, associate both
51 1
        associate(t1, t2, (Some(f1), Some(f2)) :: acc)
52 1
      case (f1 :: t1, f2 :: _) if f1._1 < f2._1 =>
53
        // the first field is not present in the second object
54 1
        associate(t1, fields2, (Some(f1), None) :: acc)
55
      case (f1 :: _, f2 :: t2) =>
56
        // the second field is not present in the first object
57 1
        associate(fields1, t2, (None, Some(f2)) :: acc)
58
      case (_, Nil) =>
59 1
        fields1.map(Some(_) -> None) ::: acc
60
      case (Nil, _) =>
61 1
        fields2.map(None -> Some(_)) ::: acc
62
    }
63
    @tailrec
64
    def fields(fs: List[(Option[(String, Json)], Option[(String, Json)])], acc: List[Operation[Json]]): List[Operation[Json]] = fs match {
65 1
      case (Some(f1), Some(f2)) :: tl if f1 == f2 =>
66
        // allright, nothing changed
67 1
        fields(tl, acc)
68
      case (Some(f1), Some(f2)) :: tl =>
69
        // same field name, different values
70 1
        fields(tl, diff(f1._2, f2._2, path / f1._1) ::: acc)
71
      case (Some(f1), None) :: tl =>
72
        // the field was deleted
73 1
        fields(tl, Remove[Json](path / f1._1, if (rememberOld) Some(f1._2) else None) :: acc)
74
      case (None, Some(f2)) :: tl =>
75
        // the field was added
76 1
        fields(tl, Add(path / f2._1, f2._2) :: acc)
77
      case _ =>
78
        acc
79
    }
80 1
    fields(associate(sorted1, sorted2, Nil), Nil)
81
  }
82

83
  private def arraysDiff(arr1: List[Json], arr2: List[Json], path: Pointer): List[Operation[Json]] = {
84
    // get the longest common subsequence in the array
85 1
    val lcs = Lcs.lcs(arr1, arr2)
86

87
    // indicates whether the index is in the lcs of the first sequence
88
    def isCommon1(idx1: Int, lcs: List[(Int, Int)]): Boolean = lcs match {
89 1
      case (cidx1, _) :: _ if idx1 == cidx1 => true
90 1
      case _                                => false
91
    }
92

93
    // indicates whether the index is in the lcs of the second sequence
94
    def isCommon2(idx2: Int, lcs: List[(Int, Int)]): Boolean = lcs match {
95 1
      case (_, cidx2) :: _ if idx2 == cidx2 => true
96 1
      case _                                => false
97
    }
98

99
    // add a bunch of values to an array starting at the specified index
100
    @tailrec
101
    def add(arr: List[Json], idx: Int, acc: List[Operation[Json]]): List[Operation[Json]] = arr match {
102 1
      case v :: tl => add(tl, idx + 1, Add(path / idx, v) :: acc)
103 1
      case Nil     => acc.reverse
104
    }
105

106
    // remove a bunch of array elements starting by the last one in the range
107
    def remove(from: Int, until: Int, shift: Int, arr: List[Json]): List[Operation[Json]] =
108 1
      (for (idx <- until to from by -1)
109 1
        yield Remove[Json](path / idx, if (rememberOld) Some(arr(idx - shift)) else None)).toList
110

111
    // now iterate over the first array to computes what was added, what was removed and what was modified
112
    @tailrec
113
    def loop(
114
      arr1: List[Json], // the first array
115
      arr2: List[Json], // the second array
116
      idx1: Int, // current index in the first array
117
      shift1: Int, // current index shift in the first array (due to elements being add or removed)
118
      idx2: Int, // current index in the second array
119
      lcs: List[(Int, Int)], // the list of remaining matching indices
120
      acc: List[Operation[Json]] // the already accumulated result
121
    ): List[Operation[Json]] = (arr1, arr2) match {
122 1
      case (_ :: tl1, _) if isCommon1(idx1, lcs) =>
123
        // all values in arr2 were added until the index of common value
124 1
        val until = lcs.head._2
125 1
        loop(tl1, arr2.drop(until - idx2 + 1), idx1 + 1, shift1 + until - idx2, until + 1, lcs.tail,
126 1
          add(arr2.take(until - idx2), idx1 + shift1, Nil) reverse_::: acc)
127 1
      case (_, _ :: tl2) if isCommon2(idx2, lcs) =>
128
        // all values in arr1 were removed until the index of common value
129 1
        val until = lcs.head._1
130 1
        loop(arr1.drop(until - idx1 + 1), tl2, until + 1, shift1 - (until - idx1), idx2 + 1, lcs.tail,
131 1
          remove(idx1 + shift1, until - 1 + shift1, idx1 + shift1, arr1) reverse_::: acc)
132
      case (v1 :: tl1, v2 :: tl2) =>
133
        // values are different, recursively compute the diff of these values
134 1
        loop(tl1, tl2, idx1 + 1, shift1, idx2 + 1, lcs, diff(v1, v2, path / (idx1 + shift1)) reverse_::: acc)
135
      case (_, Nil) =>
136
        // all subsequent values in arr1 were removed
137 1
        remove(idx1 + shift1, idx1 + arr1.size - 1 + shift1, idx1 + shift1, arr1) reverse_::: acc
138
      case (Nil, _) =>
139
        // all subsequent value in arr2 were added
140 1
        arr2.map(Add(path / "-", _)) reverse_::: acc
141
    }
142

143 1
    loop(arr1, arr2, 0, 0, 0, lcs, Nil).reverse
144
  }
145
}

Read our documentation on viewing source code .

Loading