Skip to content

Commit 37f9eaf

Browse files
anatawa12cowwoc
anatawa12
and
cowwoc
authored
Fizzy apply (#125)
* add applyFuzzyTo and restoreFuzzy * implement applyFuzzyTo and restoreFuzzy for EqualDelta * add verifyChunk with fuzzy and delta * implement fuzzy apply and add tests * fix style * extract method * fix: assign lastPatchDelta and lastPatchEnd * fix use explict import * document EqualDelta#applyFuzzyToAt * set access modifiers * change test method name * document empty method * apply from first * add more tests * add more documentation about fuzz parameter * fix documentation about fizzy patch Co-authored-by: cowwoc <cowwoc2020@gmail.com> Co-authored-by: cowwoc <cowwoc2020@gmail.com>
1 parent 0fd38db commit 37f9eaf

File tree

7 files changed

+498
-2
lines changed

7 files changed

+498
-2
lines changed

‎java-diff-utils/src/main/java/com/github/difflib/patch/AbstractDelta.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,19 @@ protected VerifyChunk verifyAntApplyTo(List<T> target) throws PatchFailedExcepti
7070

7171
protected abstract void restore(List<T> target);
7272

73+
/**
74+
* Apply patch fuzzy.
75+
*
76+
* @param target the list this patch will be applied to
77+
* @param fuzz the number of elements to ignore before/after the patched elements
78+
* @param position the position this patch will be applied to. ignores {@code source.getPosition()}
79+
* @see <a href="https://www.gnu.org/software/diffutils/manual/html_node/Inexact.html">Description of Fuzzy Patch</a> for more information.
80+
*/
81+
@SuppressWarnings("RedundantThrows")
82+
protected void applyFuzzyToAt(List<T> target, int fuzz, int position) throws PatchFailedException {
83+
throw new UnsupportedOperationException(this.getClass().getSimpleName() + " does not supports applying patch fuzzy");
84+
}
85+
7386
/**
7487
* Create a new delta of the actual instance with customized chunk data.
7588
*/

‎java-diff-utils/src/main/java/com/github/difflib/patch/ChangeDelta.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,19 @@ protected void restore(List<T> target) {
6666
}
6767
}
6868

69+
protected void applyFuzzyToAt(List<T> target, int fuzz, int position) throws PatchFailedException {
70+
int size = getSource().size();
71+
for (int i = fuzz; i < size - fuzz; i++) {
72+
target.remove(position + fuzz);
73+
}
74+
75+
int i = fuzz;
76+
for (T line : getTarget().getLines().subList(fuzz, getTarget().size() - fuzz)) {
77+
target.add(position + i, line);
78+
i++;
79+
}
80+
}
81+
6982
@Override
7083
public String toString() {
7184
return "[ChangeDelta, position: " + getSource().getPosition() + ", lines: "

‎java-diff-utils/src/main/java/com/github/difflib/patch/Chunk.java

Lines changed: 20 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -95,10 +95,28 @@ public Chunk(int position, T[] lines) {
9595
* @throws com.github.difflib.patch.PatchFailedException
9696
*/
9797
public VerifyChunk verifyChunk(List<T> target) throws PatchFailedException {
98-
if (position > target.size() || last() > target.size()) {
98+
return verifyChunk(target, 0, getPosition());
99+
}
100+
101+
/**
102+
* Verifies that this chunk's saved text matches the corresponding text in
103+
* the given sequence.
104+
*
105+
* @param target the sequence to verify against.
106+
* @param fuzz the count of ignored prefix/suffix
107+
* @param position the position of target
108+
* @throws com.github.difflib.patch.PatchFailedException
109+
*/
110+
public VerifyChunk verifyChunk(List<T> target, int fuzz, int position) throws PatchFailedException {
111+
//noinspection UnnecessaryLocalVariable
112+
int startIndex = fuzz;
113+
int lastIndex = size() - fuzz;
114+
int last = position + size() - 1;
115+
116+
if (position + fuzz > target.size() || last - fuzz > target.size()) {
99117
return VerifyChunk.POSITION_OUT_OF_TARGET;
100118
}
101-
for (int i = 0; i < size(); i++) {
119+
for (int i = startIndex; i < lastIndex; i++) {
102120
if (!target.get(position + i).equals(lines.get(i))) {
103121
return VerifyChunk.CONTENT_DOES_NOT_MATCH_TARGET;
104122
}

‎java-diff-utils/src/main/java/com/github/difflib/patch/EqualDelta.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,14 @@ protected void applyTo(List<T> target) throws PatchFailedException {
3535
protected void restore(List<T> target) {
3636
}
3737

38+
/**
39+
* {@inheritDoc}
40+
*/
41+
@Override
42+
protected void applyFuzzyToAt(List<T> target, int fuzz, int delta) {
43+
// equals so no operations
44+
}
45+
3846
@Override
3947
public String toString() {
4048
return "[EqualDelta, position: " + getSource().getPosition() + ", lines: "

‎java-diff-utils/src/main/java/com/github/difflib/patch/Patch.java

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,117 @@ public List<T> applyTo(List<T> target) throws PatchFailedException {
6666
return result;
6767
}
6868

69+
private static class PatchApplyingContext<T> {
70+
public final List<T> result;
71+
public final int maxFuzz;
72+
73+
// the position last patch applied to.
74+
public int lastPatchEnd = -1;
75+
76+
///// passing values from find to apply
77+
public int currentFuzz = 0;
78+
79+
public int defaultPosition;
80+
public boolean beforeOutRange = false;
81+
public boolean afterOutRange = false;
82+
83+
private PatchApplyingContext(List<T> result, int maxFuzz) {
84+
this.result = result;
85+
this.maxFuzz = maxFuzz;
86+
}
87+
}
88+
89+
public List<T> applyFuzzy(List<T> target, int maxFuzz) throws PatchFailedException {
90+
PatchApplyingContext<T> ctx = new PatchApplyingContext<>(new ArrayList<>(target), maxFuzz);
91+
92+
// the difference between patch's position and actually applied position
93+
int lastPatchDelta = 0;
94+
95+
for (AbstractDelta<T> delta : getDeltas()) {
96+
ctx.defaultPosition = delta.getSource().getPosition() + lastPatchDelta;
97+
int patchPosition = findPositionFuzzy(ctx, delta);
98+
if (0 <= patchPosition) {
99+
delta.applyFuzzyToAt(ctx.result, ctx.currentFuzz, patchPosition);
100+
lastPatchDelta = patchPosition - delta.getSource().getPosition();
101+
ctx.lastPatchEnd = delta.getSource().last() + lastPatchDelta;
102+
} else {
103+
conflictOutput.processConflict(VerifyChunk.CONTENT_DOES_NOT_MATCH_TARGET, delta, ctx.result);
104+
}
105+
}
106+
107+
return ctx.result;
108+
}
109+
110+
// negative for not found
111+
private int findPositionFuzzy(PatchApplyingContext<T> ctx, AbstractDelta<T> delta) throws PatchFailedException {
112+
for (int fuzz = 0; fuzz <= ctx.maxFuzz; fuzz++) {
113+
ctx.currentFuzz = fuzz;
114+
int foundPosition = findPositionWithFuzz(ctx, delta, fuzz);
115+
if (foundPosition >= 0) {
116+
return foundPosition;
117+
}
118+
}
119+
return -1;
120+
}
121+
122+
// negative for not found
123+
private int findPositionWithFuzz(PatchApplyingContext<T> ctx, AbstractDelta<T> delta, int fuzz) throws PatchFailedException {
124+
if (delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition) == VerifyChunk.OK) {
125+
return ctx.defaultPosition;
126+
}
127+
128+
ctx.beforeOutRange = false;
129+
ctx.afterOutRange = false;
130+
131+
// moreDelta >= 0: just for overflow guard, not a normal condition
132+
//noinspection OverflowingLoopIndex
133+
for (int moreDelta = 0; moreDelta >= 0; moreDelta++) {
134+
int pos = findPositionWithFuzzAndMoreDelta(ctx, delta, fuzz, moreDelta);
135+
if (pos >= 0) {
136+
return pos;
137+
}
138+
if (ctx.beforeOutRange && ctx.afterOutRange) {
139+
break;
140+
}
141+
}
142+
143+
return -1;
144+
}
145+
146+
// negative for not found
147+
private int findPositionWithFuzzAndMoreDelta(PatchApplyingContext<T> ctx, AbstractDelta<T> delta, int fuzz, int moreDelta) throws PatchFailedException {
148+
// range check: can't apply before end of last patch
149+
if (!ctx.beforeOutRange) {
150+
int beginAt = ctx.defaultPosition - moreDelta + fuzz;
151+
// We can't apply patch before end of last patch.
152+
if (beginAt <= ctx.lastPatchEnd) {
153+
ctx.beforeOutRange = true;
154+
}
155+
}
156+
// range check: can't apply after end of result
157+
if (!ctx.afterOutRange) {
158+
int beginAt = ctx.defaultPosition + moreDelta + delta.getSource().size() - fuzz;
159+
// We can't apply patch before end of last patch.
160+
if (ctx.result.size() < beginAt) {
161+
ctx.afterOutRange = true;
162+
}
163+
}
164+
165+
if (!ctx.beforeOutRange) {
166+
VerifyChunk before = delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition - moreDelta);
167+
if (before == VerifyChunk.OK) {
168+
return ctx.defaultPosition - moreDelta;
169+
}
170+
}
171+
if (!ctx.afterOutRange) {
172+
VerifyChunk after = delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition + moreDelta);
173+
if (after == VerifyChunk.OK) {
174+
return ctx.defaultPosition + moreDelta;
175+
}
176+
}
177+
return -1;
178+
}
179+
69180
/**
70181
* Standard Patch behaviour to throw an exception for pathching conflicts.
71182
*/

0 commit comments

Comments
 (0)