1 /*
2 * Copyright (C) 2019 The Android Open Source 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
17 package com.android.tools.metalava
18
19 import com.android.ide.common.process.CachedProcessOutputHandler
20 import com.android.ide.common.process.DefaultProcessExecutor
21 import com.android.ide.common.process.ProcessInfoBuilder
22 import com.android.utils.LineCollector
23 import com.android.utils.StdLogger
24 import java.io.File
25 import kotlin.math.max
26 import kotlin.math.min
27
28 // Copied from lint's test suite: TestUtils.diff in tools/base with
29 // some changes to allow running native diff.
30
31 /** Returns the universal diff for the two given files, or null if not supported or working */
getNativeDiffnull32 fun getNativeDiff(before: File, after: File): String? {
33 if (options.noNativeDiff) {
34 return null
35 }
36
37 // A lot faster for big files:
38 val native = File("/usr/bin/diff")
39 if (native.isFile) {
40 try {
41 val builder = ProcessInfoBuilder()
42 builder.setExecutable(native)
43 builder.addArgs("-u", before.path, after.path)
44 val processOutputHandler = CachedProcessOutputHandler()
45 DefaultProcessExecutor(StdLogger(StdLogger.Level.ERROR))
46 .execute(builder.createProcess(), processOutputHandler)
47 .rethrowFailure()
48
49 val output = processOutputHandler.processOutput
50 val lineCollector = LineCollector()
51 output.processStandardOutputLines(lineCollector)
52
53 return lineCollector.result.joinToString(separator = "\n")
54 } catch (ignore: Throwable) {
55 }
56 }
57
58 return null
59 }
60
getDiffnull61 fun getDiff(before: String, after: String, windowSize: Int): String {
62 return getDiff(
63 before.split("\n".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray(),
64 after.split("\n".toRegex()).dropLastWhile { it.isEmpty() }.toTypedArray(),
65 windowSize
66 )
67 }
68
getDiffnull69 fun getDiff(
70 before: Array<String>,
71 after: Array<String>,
72 windowSize: Int
73 ): String {
74 // Based on the LCS section in http://introcs.cs.princeton.edu/java/96optimization/
75 val sb = StringBuilder()
76 val n = before.size
77 val m = after.size
78
79 // Compute longest common subsequence of x[i..m] and y[j..n] bottom up
80 val lcs = Array(n + 1) { IntArray(m + 1) }
81 for (i in n - 1 downTo 0) {
82 for (j in m - 1 downTo 0) {
83 if (before[i] == after[j]) {
84 lcs[i][j] = lcs[i + 1][j + 1] + 1
85 } else {
86 lcs[i][j] = max(lcs[i + 1][j], lcs[i][j + 1])
87 }
88 }
89 }
90
91 var i = 0
92 var j = 0
93 while (i < n && j < m) {
94 if (before[i] == after[j]) {
95 i++
96 j++
97 } else {
98 sb.append("@@ -")
99 sb.append((i + 1).toString())
100 sb.append(" +")
101 sb.append((j + 1).toString())
102 sb.append('\n')
103
104 if (windowSize > 0) {
105 for (context in max(0, i - windowSize) until i) {
106 sb.append(" ")
107 sb.append(before[context])
108 sb.append("\n")
109 }
110 }
111
112 while (i < n && j < m && before[i] != after[j]) {
113 if (lcs[i + 1][j] >= lcs[i][j + 1]) {
114 sb.append('-')
115 if (before[i].trim().isNotEmpty()) {
116 sb.append(' ')
117 }
118 sb.append(before[i])
119 sb.append('\n')
120 i++
121 } else {
122 sb.append('+')
123 if (after[j].trim().isNotEmpty()) {
124 sb.append(' ')
125 }
126 sb.append(after[j])
127 sb.append('\n')
128 j++
129 }
130 }
131
132 if (windowSize > 0) {
133 for (context in i until min(n, i + windowSize)) {
134 sb.append(" ")
135 sb.append(before[context])
136 sb.append("\n")
137 }
138 }
139 }
140 }
141
142 if (i < n || j < m) {
143 assert(i == n || j == m)
144 sb.append("@@ -")
145 sb.append((i + 1).toString())
146 sb.append(" +")
147 sb.append((j + 1).toString())
148 sb.append('\n')
149 while (i < n) {
150 sb.append('-')
151 if (before[i].trim().isNotEmpty()) {
152 sb.append(' ')
153 }
154 sb.append(before[i])
155 sb.append('\n')
156 i++
157 }
158 while (j < m) {
159 sb.append('+')
160 if (after[j].trim().isNotEmpty()) {
161 sb.append(' ')
162 }
163 sb.append(after[j])
164 sb.append('\n')
165 j++
166 }
167 }
168
169 return sb.toString()
170 }
171