tikhomirov@551: /*
tikhomirov@551:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@551:  *  
tikhomirov@551:  * This program is free software; you can redistribute it and/or modify
tikhomirov@551:  * it under the terms of the GNU General Public License as published by
tikhomirov@551:  * the Free Software Foundation; version 2 of the License.
tikhomirov@551:  *
tikhomirov@551:  * This program is distributed in the hope that it will be useful,
tikhomirov@551:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@551:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@551:  * GNU General Public License for more details.
tikhomirov@551:  *
tikhomirov@551:  * For information on how to redistribute this software under
tikhomirov@551:  * the terms of a license other than GNU General Public License
tikhomirov@551:  * contact TMate Software at support@hg4j.com
tikhomirov@551:  */
tikhomirov@551: package org.tmatesoft.hg.test;
tikhomirov@551: 
tikhomirov@551: import static org.junit.Assert.*;
tikhomirov@551: import static org.tmatesoft.hg.internal.DiffHelper.LineSequence.newlines;
tikhomirov@551: 
tikhomirov@551: import org.junit.Test;
tikhomirov@551: import org.tmatesoft.hg.internal.DiffHelper;
tikhomirov@551: import org.tmatesoft.hg.internal.DiffHelper.ChunkSequence;
tikhomirov@551: import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
tikhomirov@551: import org.tmatesoft.hg.internal.IntVector;
tikhomirov@551: 
tikhomirov@551: /**
tikhomirov@551:  * Testing DiffHelper (foundation for facilities like commit and annotate) directly
tikhomirov@551:  * 
tikhomirov@551:  * @author Artem Tikhomirov
tikhomirov@551:  * @author TMate Software Ltd.
tikhomirov@551:  */
tikhomirov@551: public class TestDiffHelper {
tikhomirov@551: 
tikhomirov@551: 	@Test
tikhomirov@551: 	public void testSimple() {
tikhomirov@551: 		DiffHelper<LineSequence> diffHelper = new DiffHelper<LineSequence>();
tikhomirov@551: 		MatchCollector<LineSequence> mc; DeltaCollector dc;
tikhomirov@551: 
tikhomirov@551: 		// single change
tikhomirov@551: 		diffHelper.init(newlines("hello\nabc".getBytes()), newlines("hello\nworld".getBytes()));
tikhomirov@551: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@551: 		assertEquals(1, mc.matchCount());
tikhomirov@551: 		assertTrue(mc.originLineMatched(0));
tikhomirov@551: 		assertTrue(mc.targetLineMatched(0));
tikhomirov@551: 		assertFalse(mc.originLineMatched(1));
tikhomirov@551: 		assertFalse(mc.targetLineMatched(1));
tikhomirov@551: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@551: 		assertEquals(1, dc.unchangedCount());
tikhomirov@551: 		assertEquals(1, dc.deletedCount());
tikhomirov@551: 		assertEquals(1, dc.addedCount());
tikhomirov@551: 
tikhomirov@551: 		// boundary case, additions to an empty origin
tikhomirov@551: 		diffHelper.init(newlines("".getBytes()), newlines("hello\nworld".getBytes()));
tikhomirov@551: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@551: 		assertEquals(0, mc.matchCount());
tikhomirov@551: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@551: 		assertEquals(0, dc.unchangedCount());
tikhomirov@551: 		assertEquals(0, dc.deletedCount());
tikhomirov@551: 		assertEquals(1, dc.addedCount()); // two lines added, but 1 range
tikhomirov@551: 
tikhomirov@551: 		// boundary case, complete deletion
tikhomirov@551: 		diffHelper.init(newlines("hello\nworld".getBytes()), newlines("".getBytes()));
tikhomirov@551: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@551: 		assertEquals(0, mc.matchCount());
tikhomirov@551: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@551: 		assertEquals(0, dc.unchangedCount());
tikhomirov@551: 		assertEquals(1, dc.deletedCount());
tikhomirov@551: 		assertEquals(0, dc.addedCount());
tikhomirov@551: 
tikhomirov@551: 		// regular case, few changes
tikhomirov@551: 		String s1 = "line 1\nline 2\r\nline 3\n\nline 1\nline 2";
tikhomirov@551: 		String s2 = "abc\ncdef\r\nline 2\r\nline 3\nline 2";
tikhomirov@551: 		diffHelper.init(newlines(s1.getBytes()), newlines(s2.getBytes()));
tikhomirov@551: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@551: 		assertEquals(2, mc.matchCount());
tikhomirov@551: 		assertFalse(mc.originLineMatched(0));
tikhomirov@551: 		assertTrue(mc.originLineMatched(1));
tikhomirov@551: 		assertTrue(mc.originLineMatched(2));
tikhomirov@551: 		assertFalse(mc.originLineMatched(3));
tikhomirov@551: 		assertFalse(mc.originLineMatched(4));
tikhomirov@551: 		assertTrue(mc.originLineMatched(5));
tikhomirov@551: 		assertFalse(mc.targetLineMatched(0));
tikhomirov@551: 		assertFalse(mc.targetLineMatched(1));
tikhomirov@551: 		assertTrue(mc.targetLineMatched(2));
tikhomirov@551: 		assertTrue(mc.targetLineMatched(3));
tikhomirov@551: 		assertTrue(mc.targetLineMatched(4));
tikhomirov@551: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@551: 		assertEquals(2, dc.unchangedCount()); // 3 lines but 2 ranges
tikhomirov@551: 		assertEquals(2, dc.deletedCount());
tikhomirov@551: 		assertEquals(1, dc.addedCount());
tikhomirov@551: 		assertTrue(dc.deletedLine(0));
tikhomirov@551: 		assertTrue(dc.deletedLine(3));
tikhomirov@551: 		assertTrue(dc.deletedLine(4));
tikhomirov@551: 		assertTrue(dc.addedLine(0));
tikhomirov@551: 		assertTrue(dc.addedLine(1));
tikhomirov@551: 	}
tikhomirov@551: 	
tikhomirov@551: 	@Test
tikhomirov@551: 	public void testOtherSequence() {
tikhomirov@551: 		class CharSequence implements DiffHelper.ChunkSequence<Character> {
tikhomirov@551: 			private final char[] chunks;
tikhomirov@551: 
tikhomirov@551: 			CharSequence(String s) {
tikhomirov@551: 				chunks = s.toCharArray();
tikhomirov@551: 			}
tikhomirov@551: 			public Character chunk(int index) {
tikhomirov@551: 				return chunks[index];
tikhomirov@551: 			}
tikhomirov@551: 			public int chunkCount() {
tikhomirov@551: 				return chunks.length;
tikhomirov@551: 			}
tikhomirov@551: 		}
tikhomirov@551: 		DiffHelper<CharSequence> diff = new DiffHelper<CharSequence>();
tikhomirov@551: 		diff.init(new CharSequence("abcefg"), new CharSequence("bcdegh"));
tikhomirov@551: 		MatchCollector<CharSequence> mc;
tikhomirov@551: 		diff.findMatchingBlocks(mc = new MatchCollector<CharSequence>());
tikhomirov@551: 		assertEquals(3, mc.matchCount()); // bc, e, g
tikhomirov@551: 	}
tikhomirov@624: 
tikhomirov@624: 	@Test
tikhomirov@624: 	public void testChangedEOL() {
tikhomirov@624: 		DiffHelper<LineSequence> diffHelper = new DiffHelper<LineSequence>();
tikhomirov@624: 		MatchCollector<LineSequence> mc; DeltaCollector dc;
tikhomirov@624: 		// all lines changed
tikhomirov@624: 		diffHelper.init(newlines("one\ntwo\nthree\n".getBytes()), newlines("one\r\ntwo\r\nthree\r\n".getBytes()));
tikhomirov@624: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@624: 		assertEquals(0, mc.matchCount());
tikhomirov@624: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@624: 		assertEquals(0, dc.unchangedCount());
tikhomirov@624: 		assertEquals(1, dc.deletedCount());
tikhomirov@624: 		assertTrue(dc.deletedLine(0));
tikhomirov@624: 		assertTrue(dc.deletedLine(1));
tikhomirov@624: 		assertTrue(dc.deletedLine(2));
tikhomirov@624: 		assertEquals(1, dc.addedCount());
tikhomirov@624: 		assertTrue(dc.addedLine(0));
tikhomirov@624: 		assertTrue(dc.addedLine(1));
tikhomirov@624: 		assertTrue(dc.addedLine(2));
tikhomirov@624: 		// one line changed
tikhomirov@624: 		diffHelper.init(newlines("one\ntwo\nthree\n".getBytes()), newlines("one\ntwo\r\nthree\n".getBytes()));
tikhomirov@624: 		diffHelper.findMatchingBlocks(mc = new MatchCollector<LineSequence>());
tikhomirov@624: 		assertEquals(2, mc.matchCount());
tikhomirov@624: 		assertTrue(mc.originLineMatched(0));
tikhomirov@624: 		assertTrue(mc.targetLineMatched(0));
tikhomirov@624: 		assertFalse(mc.originLineMatched(1));
tikhomirov@624: 		assertFalse(mc.targetLineMatched(1));
tikhomirov@624: 		assertTrue(mc.originLineMatched(2));
tikhomirov@624: 		assertTrue(mc.targetLineMatched(2));
tikhomirov@624: 		diffHelper.findMatchingBlocks(dc = new DeltaCollector());
tikhomirov@624: 		assertEquals(2, dc.unchangedCount());
tikhomirov@624: 		assertEquals(1, dc.deletedCount());
tikhomirov@624: 		assertTrue(dc.deletedLine(1));
tikhomirov@624: 		assertEquals(1, dc.addedCount());
tikhomirov@624: 		assertTrue(dc.addedLine(1));
tikhomirov@624: 	}
tikhomirov@551: 	
tikhomirov@551: 	// range is comprised of 3 values, range length always last, range start comes at index o (either 0 or 1)
tikhomirov@551: 	static boolean includes(IntVector ranges, int o, int ln) {
tikhomirov@551: 		assert ranges.size() % 3 == 0;
tikhomirov@551: 		for (int i = 2; i < ranges.size(); o += 3, i+=3) {
tikhomirov@551: 			int rangeStart = ranges.get(o);
tikhomirov@551: 			if (rangeStart > ln) {
tikhomirov@551: 				return false;
tikhomirov@551: 			}
tikhomirov@551: 			int rangeLen = ranges.get(i);
tikhomirov@551: 			if (rangeStart + rangeLen > ln) {
tikhomirov@551: 				return true;
tikhomirov@551: 			}
tikhomirov@551: 		}
tikhomirov@551: 		return false;
tikhomirov@551: 	}
tikhomirov@551: 
tikhomirov@551: 	static class MatchCollector<T extends ChunkSequence<?>> implements DiffHelper.MatchInspector<T> {
tikhomirov@551: 		private IntVector matched = new IntVector(10 * 3, 5 * 3);
tikhomirov@551: 
tikhomirov@551: 		public void begin(T s1, T s2) {
tikhomirov@551: 		}
tikhomirov@551: 
tikhomirov@551: 		public void match(int startSeq1, int startSeq2, int matchLength) {
tikhomirov@551: 			matched.add(startSeq1, startSeq2, matchLength);
tikhomirov@551: 		}
tikhomirov@551: 
tikhomirov@551: 		public void end() {
tikhomirov@551: 		}
tikhomirov@551: 		
tikhomirov@551: 		int matchCount() {
tikhomirov@551: 			return matched.size() / 3;
tikhomirov@551: 		}
tikhomirov@551: 		
tikhomirov@551: 		// true if zero-based line matches any "same" block in the origin
tikhomirov@551: 		boolean originLineMatched(int ln) {
tikhomirov@551: 			return includes(matched, 0, ln);
tikhomirov@551: 		}
tikhomirov@551: 		
tikhomirov@551: 		boolean targetLineMatched(int ln) {
tikhomirov@551: 			return includes(matched, 1, ln);
tikhomirov@551: 		}
tikhomirov@551: 	}
tikhomirov@551: 	
tikhomirov@551: 	static class DeltaCollector extends DiffHelper.DeltaInspector<LineSequence> {
tikhomirov@551: 		private IntVector added, deleted, same;
tikhomirov@551: 		public DeltaCollector() {
tikhomirov@551: 			final int x = 10 * 3, y = 5 * 3;
tikhomirov@551: 			added = new IntVector(x, y);
tikhomirov@551: 			deleted = new IntVector(x, y);
tikhomirov@551: 			same = new IntVector(x, y);
tikhomirov@551: 		}
tikhomirov@551: 		@Override
tikhomirov@551: 		protected void added(int s1InsertPoint, int s2From, int s2To) {
tikhomirov@551: 			added.add(s1InsertPoint, s2From, s2To - s2From);
tikhomirov@551: 		}
tikhomirov@551: 		@Override
tikhomirov@551: 		protected void changed(int s1From, int s1To, int s2From, int s2To) {
tikhomirov@551: 			deleted(s2From, s1From, s1To);
tikhomirov@551: 			added(s1From, s2From, s2To);
tikhomirov@551: 		}
tikhomirov@551: 		@Override
tikhomirov@551: 		protected void deleted(int s2DeletePoint, int s1From, int s1To) {
tikhomirov@551: 			deleted.add(s2DeletePoint, s1From, s1To - s1From);
tikhomirov@551: 		}
tikhomirov@551: 		@Override
tikhomirov@551: 		protected void unchanged(int s1From, int s2From, int length) {
tikhomirov@551: 			same.add(s1From, s2From, length);
tikhomirov@551: 		}
tikhomirov@551: 
tikhomirov@624: 		// return number of regions that didn't change
tikhomirov@551: 		int unchangedCount() {
tikhomirov@551: 			return same.size() / 3;
tikhomirov@551: 		}
tikhomirov@551: 
tikhomirov@624: 		// return number of added regions
tikhomirov@551: 		int addedCount() {
tikhomirov@551: 			return added.size() / 3;
tikhomirov@551: 		}
tikhomirov@624: 		// return number of deleted regions
tikhomirov@551: 		int deletedCount() {
tikhomirov@551: 			return deleted.size() / 3;
tikhomirov@551: 		}
tikhomirov@624: 		// answer if 0-based line is marked as added
tikhomirov@551: 		boolean addedLine(int ln) {
tikhomirov@551: 			return includes(added, 1, ln);
tikhomirov@551: 		}
tikhomirov@624: 		// answer if 0-based line is marked as deleted
tikhomirov@551: 		boolean deletedLine(int ln) {
tikhomirov@551: 			return includes(deleted, 1, ln);
tikhomirov@551: 		}
tikhomirov@551: 	}
tikhomirov@551: }