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

Fizzy apply#125

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
wumpz merged 17 commits intojava-diff-utils:masterfromanatawa12:fizzy-apply
Nov 28, 2021
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
Show all changes
17 commits
Select commitHold shift + click to select a range
a52a951
add applyFuzzyTo and restoreFuzzy
anatawa12Jun 10, 2021
8368f28
implement applyFuzzyTo and restoreFuzzy for EqualDelta
anatawa12Jun 10, 2021
56c6898
add verifyChunk with fuzzy and delta
anatawa12Jun 10, 2021
045a3f6
implement fuzzy apply and add tests
anatawa12Jun 12, 2021
857278e
fix style
anatawa12Jun 12, 2021
b135dc2
extract method
anatawa12Jun 12, 2021
65a9e15
fix: assign lastPatchDelta and lastPatchEnd
anatawa12Jun 12, 2021
c1c0a98
fix use explict import
anatawa12Jun 12, 2021
bea97f2
document EqualDelta#applyFuzzyToAt
anatawa12Jun 12, 2021
6ea0e4d
set access modifiers
anatawa12Jun 13, 2021
0487735
change test method name
anatawa12Jun 13, 2021
7ea7f97
document empty method
anatawa12Jun 13, 2021
4a8fa6e
apply from first
anatawa12Jun 13, 2021
f82262f
add more tests
anatawa12Jun 13, 2021
eb38347
Merge remote-tracking branch 'origin/master' into fizzy-apply
anatawa12Nov 23, 2021
fba1509
add more documentation about fuzz parameter
anatawa12Nov 23, 2021
2f10732
fix documentation about fizzy patch
anatawa12Nov 24, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -70,6 +70,19 @@ protected VerifyChunk verifyAntApplyTo(List<T> target) throws PatchFailedExcepti

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

/**
* Apply patch fuzzy.
*
* @param target the list this patch will be applied to
* @param fuzz the number of elements to ignore before/after the patched elements
* @param position the position this patch will be applied to. ignores {@code source.getPosition()}
* @see <a href="https://www.gnu.org/software/diffutils/manual/html_node/Inexact.html">Description of Fuzzy Patch</a> for more information.
*/
@SuppressWarnings("RedundantThrows")
protected void applyFuzzyToAt(List<T> target, int fuzz, int position) throws PatchFailedException {
throw new UnsupportedOperationException(this.getClass().getSimpleName() + " does not supports applying patch fuzzy");
}

/**
* Create a new delta of the actual instance with customized chunk data.
*/
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -66,6 +66,19 @@ protected void restore(List<T> target) {
}
}

protected void applyFuzzyToAt(List<T> target, int fuzz, int position) throws PatchFailedException {
int size = getSource().size();
for (int i = fuzz; i < size - fuzz; i++) {
target.remove(position + fuzz);
}

int i = fuzz;
for (T line : getTarget().getLines().subList(fuzz, getTarget().size() - fuzz)) {
target.add(position + i, line);
i++;
}
}

@Override
public String toString() {
return "[ChangeDelta, position: " + getSource().getPosition() + ", lines: "
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -95,10 +95,28 @@ public Chunk(int position, T[] lines) {
* @throws com.github.difflib.patch.PatchFailedException
*/
public VerifyChunk verifyChunk(List<T> target) throws PatchFailedException {
if (position > target.size() || last() > target.size()) {
return verifyChunk(target, 0, getPosition());
}

/**
* Verifies that this chunk's saved text matches the corresponding text in
* the given sequence.
*
* @param target the sequence to verify against.
* @param fuzz the count of ignored prefix/suffix
* @param position the position of target
* @throws com.github.difflib.patch.PatchFailedException
*/
public VerifyChunk verifyChunk(List<T> target, int fuzz, int position) throws PatchFailedException {
//noinspection UnnecessaryLocalVariable
int startIndex = fuzz;
int lastIndex = size() - fuzz;
int last = position + size() - 1;

if (position + fuzz > target.size() || last - fuzz > target.size()) {
return VerifyChunk.POSITION_OUT_OF_TARGET;
}
for (int i =0; i <size(); i++) {
for (int i =startIndex; i <lastIndex; i++) {
if (!target.get(position + i).equals(lines.get(i))) {
return VerifyChunk.CONTENT_DOES_NOT_MATCH_TARGET;
}
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -35,6 +35,14 @@ protected void applyTo(List<T> target) throws PatchFailedException {
protected void restore(List<T> target) {
}

/**
* {@inheritDoc}
*/
@Override
protected void applyFuzzyToAt(List<T> target, int fuzz, int delta) {
// equals so no operations
}

@Override
public String toString() {
return "[EqualDelta, position: " + getSource().getPosition() + ", lines: "
Expand Down
111 changes: 111 additions & 0 deletionsjava-diff-utils/src/main/java/com/github/difflib/patch/Patch.java
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -66,6 +66,117 @@ public List<T> applyTo(List<T> target) throws PatchFailedException {
return result;
}

private static class PatchApplyingContext<T> {
public final List<T> result;
public final int maxFuzz;

// the position last patch applied to.
public int lastPatchEnd = -1;

///// passing values from find to apply
public int currentFuzz = 0;

public int defaultPosition;
public boolean beforeOutRange = false;
public boolean afterOutRange = false;

private PatchApplyingContext(List<T> result, int maxFuzz) {
this.result = result;
this.maxFuzz = maxFuzz;
}
}

public List<T> applyFuzzy(List<T> target, int maxFuzz) throws PatchFailedException {
PatchApplyingContext<T> ctx = new PatchApplyingContext<>(new ArrayList<>(target), maxFuzz);

// the difference between patch's position and actually applied position
int lastPatchDelta = 0;

for (AbstractDelta<T> delta : getDeltas()) {
ctx.defaultPosition = delta.getSource().getPosition() + lastPatchDelta;
int patchPosition = findPositionFuzzy(ctx, delta);
if (0 <= patchPosition) {
delta.applyFuzzyToAt(ctx.result, ctx.currentFuzz, patchPosition);
lastPatchDelta = patchPosition - delta.getSource().getPosition();
ctx.lastPatchEnd = delta.getSource().last() + lastPatchDelta;
} else {
conflictOutput.processConflict(VerifyChunk.CONTENT_DOES_NOT_MATCH_TARGET, delta, ctx.result);
}
}

return ctx.result;
}

// negative for not found
private int findPositionFuzzy(PatchApplyingContext<T> ctx, AbstractDelta<T> delta) throws PatchFailedException {
for (int fuzz = 0; fuzz <= ctx.maxFuzz; fuzz++) {
ctx.currentFuzz = fuzz;
int foundPosition = findPositionWithFuzz(ctx, delta, fuzz);
if (foundPosition >= 0) {
return foundPosition;
}
}
return -1;
}

// negative for not found
private int findPositionWithFuzz(PatchApplyingContext<T> ctx, AbstractDelta<T> delta, int fuzz) throws PatchFailedException {
if (delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition) == VerifyChunk.OK) {
return ctx.defaultPosition;
}

ctx.beforeOutRange = false;
ctx.afterOutRange = false;

// moreDelta >= 0: just for overflow guard, not a normal condition
//noinspection OverflowingLoopIndex
for (int moreDelta = 0; moreDelta >= 0; moreDelta++) {
int pos = findPositionWithFuzzAndMoreDelta(ctx, delta, fuzz, moreDelta);
if (pos >= 0) {
return pos;
}
if (ctx.beforeOutRange && ctx.afterOutRange) {
break;
}
}

return -1;
}

// negative for not found
private int findPositionWithFuzzAndMoreDelta(PatchApplyingContext<T> ctx, AbstractDelta<T> delta, int fuzz, int moreDelta) throws PatchFailedException {
// range check: can't apply before end of last patch
if (!ctx.beforeOutRange) {
int beginAt = ctx.defaultPosition - moreDelta + fuzz;
// We can't apply patch before end of last patch.
if (beginAt <= ctx.lastPatchEnd) {
ctx.beforeOutRange = true;
}
}
// range check: can't apply after end of result
if (!ctx.afterOutRange) {
int beginAt = ctx.defaultPosition + moreDelta + delta.getSource().size() - fuzz;
// We can't apply patch before end of last patch.
if (ctx.result.size() < beginAt) {
ctx.afterOutRange = true;
}
}

if (!ctx.beforeOutRange) {
VerifyChunk before = delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition - moreDelta);
if (before == VerifyChunk.OK) {
return ctx.defaultPosition - moreDelta;
}
}
if (!ctx.afterOutRange) {
VerifyChunk after = delta.getSource().verifyChunk(ctx.result, fuzz, ctx.defaultPosition + moreDelta);
if (after == VerifyChunk.OK) {
return ctx.defaultPosition + moreDelta;
}
}
return -1;
}

/**
* Standard Patch behaviour to throw an exception for pathching conflicts.
*/
Expand Down
Loading
[8]ページ先頭
©2009-2025 Movatter.jp