Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit37f9eaf

Browse files
anatawa12cowwoc
andauthored
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 patchCo-authored-by: cowwoc <cowwoc2020@gmail.com>Co-authored-by: cowwoc <cowwoc2020@gmail.com>
1 parent0fd38db commit37f9eaf

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
protectedabstractvoidrestore(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+
protectedvoidapplyFuzzyToAt(List<T>target,intfuzz,intposition)throwsPatchFailedException {
83+
thrownewUnsupportedOperationException(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+
protectedvoidapplyFuzzyToAt(List<T>target,intfuzz,intposition)throwsPatchFailedException {
70+
intsize =getSource().size();
71+
for (inti =fuzz;i <size -fuzz;i++) {
72+
target.remove(position +fuzz);
73+
}
74+
75+
inti =fuzz;
76+
for (Tline :getTarget().getLines().subList(fuzz,getTarget().size() -fuzz)) {
77+
target.add(position +i,line);
78+
i++;
79+
}
80+
}
81+
6982
@Override
7083
publicStringtoString() {
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
publicVerifyChunkverifyChunk(List<T>target)throwsPatchFailedException {
98-
if (position >target.size() ||last() >target.size()) {
98+
returnverifyChunk(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+
publicVerifyChunkverifyChunk(List<T>target,intfuzz,intposition)throwsPatchFailedException {
111+
//noinspection UnnecessaryLocalVariable
112+
intstartIndex =fuzz;
113+
intlastIndex =size() -fuzz;
114+
intlast =position +size() -1;
115+
116+
if (position +fuzz >target.size() ||last -fuzz >target.size()) {
99117
returnVerifyChunk.POSITION_OUT_OF_TARGET;
100118
}
101-
for (inti =0;i <size();i++) {
119+
for (inti =startIndex;i <lastIndex;i++) {
102120
if (!target.get(position +i).equals(lines.get(i))) {
103121
returnVerifyChunk.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
protectedvoidrestore(List<T>target) {
3636
}
3737

38+
/**
39+
* {@inheritDoc}
40+
*/
41+
@Override
42+
protectedvoidapplyFuzzyToAt(List<T>target,intfuzz,intdelta) {
43+
// equals so no operations
44+
}
45+
3846
@Override
3947
publicStringtoString() {
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
returnresult;
6767
}
6868

69+
privatestaticclassPatchApplyingContext<T> {
70+
publicfinalList<T>result;
71+
publicfinalintmaxFuzz;
72+
73+
// the position last patch applied to.
74+
publicintlastPatchEnd = -1;
75+
76+
///// passing values from find to apply
77+
publicintcurrentFuzz =0;
78+
79+
publicintdefaultPosition;
80+
publicbooleanbeforeOutRange =false;
81+
publicbooleanafterOutRange =false;
82+
83+
privatePatchApplyingContext(List<T>result,intmaxFuzz) {
84+
this.result =result;
85+
this.maxFuzz =maxFuzz;
86+
}
87+
}
88+
89+
publicList<T>applyFuzzy(List<T>target,intmaxFuzz)throwsPatchFailedException {
90+
PatchApplyingContext<T>ctx =newPatchApplyingContext<>(newArrayList<>(target),maxFuzz);
91+
92+
// the difference between patch's position and actually applied position
93+
intlastPatchDelta =0;
94+
95+
for (AbstractDelta<T>delta :getDeltas()) {
96+
ctx.defaultPosition =delta.getSource().getPosition() +lastPatchDelta;
97+
intpatchPosition =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+
returnctx.result;
108+
}
109+
110+
// negative for not found
111+
privateintfindPositionFuzzy(PatchApplyingContext<T>ctx,AbstractDelta<T>delta)throwsPatchFailedException {
112+
for (intfuzz =0;fuzz <=ctx.maxFuzz;fuzz++) {
113+
ctx.currentFuzz =fuzz;
114+
intfoundPosition =findPositionWithFuzz(ctx,delta,fuzz);
115+
if (foundPosition >=0) {
116+
returnfoundPosition;
117+
}
118+
}
119+
return -1;
120+
}
121+
122+
// negative for not found
123+
privateintfindPositionWithFuzz(PatchApplyingContext<T>ctx,AbstractDelta<T>delta,intfuzz)throwsPatchFailedException {
124+
if (delta.getSource().verifyChunk(ctx.result,fuzz,ctx.defaultPosition) ==VerifyChunk.OK) {
125+
returnctx.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 (intmoreDelta =0;moreDelta >=0;moreDelta++) {
134+
intpos =findPositionWithFuzzAndMoreDelta(ctx,delta,fuzz,moreDelta);
135+
if (pos >=0) {
136+
returnpos;
137+
}
138+
if (ctx.beforeOutRange &&ctx.afterOutRange) {
139+
break;
140+
}
141+
}
142+
143+
return -1;
144+
}
145+
146+
// negative for not found
147+
privateintfindPositionWithFuzzAndMoreDelta(PatchApplyingContext<T>ctx,AbstractDelta<T>delta,intfuzz,intmoreDelta)throwsPatchFailedException {
148+
// range check: can't apply before end of last patch
149+
if (!ctx.beforeOutRange) {
150+
intbeginAt =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+
intbeginAt =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+
VerifyChunkbefore =delta.getSource().verifyChunk(ctx.result,fuzz,ctx.defaultPosition -moreDelta);
167+
if (before ==VerifyChunk.OK) {
168+
returnctx.defaultPosition -moreDelta;
169+
}
170+
}
171+
if (!ctx.afterOutRange) {
172+
VerifyChunkafter =delta.getSource().verifyChunk(ctx.result,fuzz,ctx.defaultPosition +moreDelta);
173+
if (after ==VerifyChunk.OK) {
174+
returnctx.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)
[8]ページ先頭
©2009-2025 Movatter.jp