From d1f796bf255ea92aad1070293cf41a892a8245bf Mon Sep 17 00:00:00 2001
From: Meik Sievertsen <acydburn@phpbb.com>
Date: Thu, 17 Sep 2009 14:18:57 +0000
Subject: phpBB updater now solves common conflicts on it's own. This further
 reduces the chance of conflicts. (tested with some heavily modified files who
 previously generated a lot of conflicts)

git-svn-id: file:///svn/phpbb/branches/phpBB-3_0_0@10160 89ea8834-ac86-4346-8a33-228a782c2dd0
---
 phpBB/includes/diff/diff.php | 95 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 95 insertions(+)

(limited to 'phpBB/includes/diff/diff.php')

diff --git a/phpBB/includes/diff/diff.php b/phpBB/includes/diff/diff.php
index 2adc3a3e6e..d8ee43feec 100644
--- a/phpBB/includes/diff/diff.php
+++ b/phpBB/includes/diff/diff.php
@@ -727,7 +727,9 @@ class diff3_op
 			}
 			else
 			{
+				// The following tries to aggressively solve conflicts...
 				$this->_merged = false;
+				$this->solve_conflict();
 			}
 		}
 
@@ -738,6 +740,99 @@ class diff3_op
 	{
 		return ($this->merged() === false) ? true : false;
 	}
+
+	/**
+	* Tries to solve conflicts aggressively based on typical "assumptions"
+	* @author acydburn
+	*/
+	function solve_conflict()
+	{
+		$this->_merged = false;
+
+		// CASE ONE: orig changed into final2, but modified/unknown code in final1.
+		// IF orig is found "as is" in final1 we replace the code directly in final1 and populate this as final2/merge
+		if (sizeof($this->orig) && sizeof($this->final2))
+		{
+			// Ok, we basically search for $this->orig in $this->final1 and replace it with $this->final2
+			$compare_seq = sizeof($this->orig);
+
+			// Search for matching code block
+			$merge = array();
+			$merge_found = false;
+
+			// Go through the conflict code
+			for ($i = 0, $j = 0, $size = sizeof($this->final1); $i < $size; $i++, $j = $i)
+			{
+				$line = $this->final1[$i];
+				$skip = 0;
+
+				for ($x = 0; $x < $compare_seq; $x++)
+				{
+					// Try to skip all matching lines
+					if (trim($line) === trim($this->orig[$x]))
+					{
+						$line = (++$j < $size) ? $this->final1[$j] : $line;
+						$skip++;
+					}
+				}
+
+				if ($skip === $compare_seq)
+				{
+					$merge_found = true;
+					$merge = array_merge($merge, $this->final2);
+					$i += ($skip - 1);
+				}
+				else
+				{
+					$merge[] = $line;
+				}
+			}
+
+			if ($merge_found)
+			{
+				$this->final2 = $merge;
+				$this->_merged = &$this->final2;
+			}
+
+			return;
+		}
+
+		// CASE TWO: Added lines from orig to final2 but final1 had added lines too. Just merge them.
+		if (!sizeof($this->orig) && $this->final1 !== $this->final2 && sizeof($this->final1) && sizeof($this->final2))
+		{
+			$this->final2 = array_merge($this->final1, $this->final2);
+			$this->_merged = &$this->final2;
+
+			return;
+		}
+
+		// CASE THREE: Removed lines (orig has the to-remove line(s), but final1 has additional lines which does not need to be removed). Just remove orig from final1 and then use final1 as final2/merge
+		if (!sizeof($this->final2) && sizeof($this->orig) && sizeof($this->final1) && $this->orig !== $this->final1)
+		{
+			$merged = $this->final1;
+
+			foreach ($this->final1 as $i => $line)
+			{
+				foreach ($this->orig as $j => $old_line)
+				{
+					if (trim($line) === trim($old_line))
+					{
+						unset($merged[$i]);
+					}
+				}
+			}
+
+			if (sizeof($merged))
+			{
+				$this->final2 = array_values($merged);
+				$this->_merged = &$this->final2;
+			}
+
+			return;
+		}
+
+		return;
+	}
 }
 
 /**
-- 
cgit v1.2.1


From 38c4bcad55ce1e8203e5507b6db2700120688aae Mon Sep 17 00:00:00 2001
From: Meik Sievertsen <acydburn@phpbb.com>
Date: Fri, 18 Sep 2009 18:18:54 +0000
Subject: Ok, after 20+ hours i think i fixed all grave issues with the updater
 - smaller memory footprint - better checks for already updated files - even
 less conflicts - fixed automatic conflict resolving after successful merges -
 no more conflicts for $Id$ changes - fixed skip_whitespace_changes bug where
 code blocks were added to diff_op_add whereby the previous or next
 diff_op_copy already had the change - correctly display merged files in diff
 view (previously it happened that the old file was used for comparision,
 although the new file was different/newer/merged)

git-svn-id: file:///svn/phpbb/branches/phpBB-3_0_0@10163 89ea8834-ac86-4346-8a33-228a782c2dd0
---
 phpBB/includes/diff/diff.php | 317 +++++++++++++++++++++++++++++++++++--------
 1 file changed, 263 insertions(+), 54 deletions(-)

(limited to 'phpBB/includes/diff/diff.php')

diff --git a/phpBB/includes/diff/diff.php b/phpBB/includes/diff/diff.php
index d8ee43feec..6bda3df43e 100644
--- a/phpBB/includes/diff/diff.php
+++ b/phpBB/includes/diff/diff.php
@@ -71,8 +71,10 @@ class diff
 	{
 		$count = 0;
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if (is_a($edit, 'diff_op_add') || is_a($edit, 'diff_op_change'))
 			{
 				$count += $edit->nfinal();
@@ -92,8 +94,10 @@ class diff
 	{
 		$count = 0;
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_change'))
 			{
 				$count += $edit->norig();
@@ -128,8 +132,9 @@ class diff
 
 		$rev->_edits = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
 			$rev->_edits[] = $edit->reverse();
 		}
 
@@ -143,13 +148,36 @@ class diff
 	*/
 	function is_empty()
 	{
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
-			if (!is_a($edit, 'diff_op_copy'))
+			$edit = $this->_edits[$i];
+
+			// skip diff_op_copy
+			if (is_a($edit, 'diff_op_copy'))
 			{
+				continue;
+			}
+
+			if (is_a($edit, 'diff_op_delete') || is_a($edit, 'diff_op_add'))
+			{
+				$orig = $edit->orig;
+				$final = $edit->final;
+
+				// We can simplify one case where the array is usually supposed to be empty...
+				if (sizeof($orig) == 1 && trim($orig[0]) === '') $orig = array();
+				if (sizeof($final) == 1 && trim($final[0]) === '') $final = array();
+
+				if (!$orig && !$final)
+				{
+					continue;
+				}
+
 				return false;
 			}
+
+			return false;
 		}
+
 		return true;
 	}
 
@@ -164,8 +192,10 @@ class diff
 	{
 		$lcs = 0;
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if (is_a($edit, 'diff_op_copy'))
 			{
 				$lcs += sizeof($edit->orig);
@@ -185,8 +215,10 @@ class diff
 	{
 		$lines = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->orig)
 			{
 				array_splice($lines, sizeof($lines), 0, $edit->orig);
@@ -206,8 +238,10 @@ class diff
 	{
 		$lines = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->final)
 			{
 				array_splice($lines, sizeof($lines), 0, $edit->final);
@@ -258,8 +292,10 @@ class diff
 
 		$prevtype = null;
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($prevtype == get_class($edit))
 			{
 				trigger_error("[diff] Edit sequence is non-optimal", E_USER_ERROR);
@@ -456,14 +492,14 @@ class diff3 extends diff
 	* @param array $final1  The first version to compare to.
 	* @param array $final2  The second version to compare to.
 	*/
-	function diff3(&$orig, &$final1, &$final2)
+	function diff3(&$orig, &$final1, &$final2, $preserve_cr = true)
 	{
 		$diff_engine = new diff_engine();
 
-		$diff_1 = $diff_engine->diff($orig, $final1);
-		$diff_2 = $diff_engine->diff($orig, $final2);
+		$diff_1 = $diff_engine->diff($orig, $final1, $preserve_cr);
+		$diff_2 = $diff_engine->diff($orig, $final2, $preserve_cr);
 
-		unset($engine);
+		unset($diff_engine);
 
 		$this->_edits = $this->_diff3($diff_1, $diff_2);
 	}
@@ -475,8 +511,10 @@ class diff3 extends diff
 	{
 		$conflicts = 0;
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->is_conflict())
 			{
 				$conflicts++;
@@ -506,8 +544,10 @@ class diff3 extends diff
 
 		$lines = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->is_conflict())
 			{
 				// Start conflict label
@@ -544,8 +584,10 @@ class diff3 extends diff
 	{
 		$lines = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->is_conflict())
 			{
 				$lines = array_merge($lines, $edit->final2);
@@ -566,8 +608,10 @@ class diff3 extends diff
 	{
 		$lines = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->is_conflict())
 			{
 				$lines = array_merge($lines, $edit->final1);
@@ -588,8 +632,10 @@ class diff3 extends diff
 	{
 		$conflicts = array();
 
-		foreach ($this->_edits as $edit)
+		for ($i = 0, $size = sizeof($this->_edits); $i < $size; $i++)
 		{
+			$edit = $this->_edits[$i];
+
 			if ($edit->is_conflict())
 			{
 				$conflicts[] = array($edit->final1, $edit->final2);
@@ -713,6 +759,9 @@ class diff3_op
 	{
 		if (!isset($this->_merged))
 		{
+			// Prepare the arrays before we compare them. ;)
+			$this->solve_prepare();
+
 			if ($this->final1 === $this->final2)
 			{
 				$this->_merged = &$this->final1;
@@ -741,6 +790,95 @@ class diff3_op
 		return ($this->merged() === false) ? true : false;
 	}
 
+	/**
+	* Function to prepare the arrays for comparing - we want to skip over newline changes
+	* @author acydburn
+	*/
+	function solve_prepare()
+	{
+		// We can simplify one case where the array is usually supposed to be empty...
+		if (sizeof($this->orig) == 1 && trim($this->orig[0]) === '') $this->orig = array();
+		if (sizeof($this->final1) == 1 && trim($this->final1[0]) === '') $this->final1 = array();
+		if (sizeof($this->final2) == 1 && trim($this->final2[0]) === '') $this->final2 = array();
+
+		// Now we only can have the case where the only difference between arrays are newlines, so compare all cases
+
+		// First, some strings we can compare...
+		$orig = $final1 = $final2 = '';
+
+		foreach ($this->orig as $null => $line) $orig .= trim($line);
+		foreach ($this->final1 as $null => $line) $final1 .= trim($line);
+		foreach ($this->final2 as $null => $line) $final2 .= trim($line);
+
+		// final1 === final2
+		if ($final1 === $final2)
+		{
+			// We preserve the part which will be used in the merge later
+			$this->final2 = $this->final1;
+		}
+		// final1 === orig
+		else if ($final1 === $orig)
+		{
+			// Here it does not really matter what we choose, but we will use the new code
+			$this->orig = $this->final1;
+		}
+		// final2 === orig
+		else if ($final2 === $orig)
+		{
+			// Here it does not really matter too (final1 will be used), but we will use the new code
+			$this->orig = $this->final2;
+		}
+	}
+
+	/**
+	* Find code portions from $orig in $final1 and use $final2 as merged instance if provided
+	* @author acydburn
+	*/
+	function _compare_conflict_seq($orig, $final1, $final2 = false)
+	{
+		$result = array('merge_found' => false, 'merge' => array());
+
+		$_orig = &$this->$orig;
+		$_final1 = &$this->$final1;
+
+		// Ok, we basically search for $orig in $final1
+		$compare_seq = sizeof($_orig);
+
+		// Go through the conflict code
+		for ($i = 0, $j = 0, $size = sizeof($_final1); $i < $size; $i++, $j = $i)
+		{
+			$line = $_final1[$i];
+			$skip = 0;
+
+			for ($x = 0; $x < $compare_seq; $x++)
+			{
+				// Try to skip all matching lines
+				if (trim($line) === trim($_orig[$x]))
+				{
+					$line = (++$j < $size) ? $_final1[$j] : $line;
+					$skip++;
+				}
+			}
+
+			if ($skip === $compare_seq)
+			{
+				$result['merge_found'] = true;
+
+				if ($final2 !== false)
+				{
+					$result['merge'] = array_merge($result['merge'], $this->$final2);
+				}
+				$i += ($skip - 1);
+			}
+			else if ($final2 !== false)
+			{
+				$result['merge'][] = $line;
+			}
+		}
+
+		return $result;
+	}
+
 	/**
 	* Tries to solve conflicts aggressively based on typical "assumptions"
 	* @author acydburn
@@ -753,55 +891,105 @@ class diff3_op
 		// IF orig is found "as is" in final1 we replace the code directly in final1 and populate this as final2/merge
 		if (sizeof($this->orig) && sizeof($this->final2))
 		{
-			// Ok, we basically search for $this->orig in $this->final1 and replace it with $this->final2
-			$compare_seq = sizeof($this->orig);
+			$result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
 
-			// Search for matching code block
-			$merge = array();
-			$merge_found = false;
+			if ($result['merge_found'])
+			{
+				$this->final2 = $result['merge'];
+				$this->_merged = &$this->final2;
+				return;
+			}
+
+			$result = $this->_compare_conflict_seq('final2', 'final1');
 
-			// Go through the conflict code
-			for ($i = 0, $j = 0, $size = sizeof($this->final1); $i < $size; $i++, $j = $i)
+			if ($result['merge_found'])
 			{
-				$line = $this->final1[$i];
-				$skip = 0;
+				$this->_merged = &$this->final1;
+				return;
+			}
 
-				for ($x = 0; $x < $compare_seq; $x++)
+			// Try to solve $Id$ issues. ;)
+			if (sizeof($this->orig) == 1 && sizeof($this->final1) == 1 && sizeof($this->final2) == 1)
+			{
+				$match = '#^' . preg_quote('* @version $Id: ', '#') . '[a-z\._\- ]+[0-9]+ [0-9]{4}-[0-9]{2}-[0-9]{2} [0-9\:Z]+ [a-z0-9_\- ]+\$$#';
+
+				if (preg_match($match, $this->orig[0]) && preg_match($match, $this->final1[0]) && preg_match($match, $this->final2[0]))
 				{
-					// Try to skip all matching lines
-					if (trim($line) === trim($this->orig[$x]))
-					{
-						$line = (++$j < $size) ? $this->final1[$j] : $line;
-						$skip++;
-					}
+					$this->_merged = &$this->final2;
+					return;
 				}
+			}
+
+			$second_run = false;
+
+			// Try to solve issues where the only reason why the above did not work is a newline being removed in the final1 code but exist in the orig/final2 code
+			if (trim($this->orig[0]) === '' && trim($this->final2[0]) === '')
+			{
+				unset($this->orig[0], $this->final2[0]);
+				$this->orig = array_values($this->orig);
+				$this->final2 = array_values($this->final2);
+
+				$second_run = true;
+			}
 
-				if ($skip === $compare_seq)
+			// The same is true for a line at the end. ;)
+			if (sizeof($this->orig) && sizeof($this->final2) && sizeof($this->orig) === sizeof($this->final2) && trim($this->orig[sizeof($this->orig)-1]) === '' && trim($this->final2[sizeof($this->final2)-1]) === '')
+			{
+				unset($this->orig[sizeof($this->orig)-1], $this->final2[sizeof($this->final2)-1]);
+				$this->orig = array_values($this->orig);
+				$this->final2 = array_values($this->final2);
+
+				$second_run = true;
+			}
+
+			if ($second_run)
+			{
+				$result = $this->_compare_conflict_seq('orig', 'final1', 'final2');
+
+				if ($result['merge_found'])
 				{
-					$merge_found = true;
-					$merge = array_merge($merge, $this->final2);
-					$i += ($skip - 1);
+					$this->final2 = $result['merge'];
+					$this->_merged = &$this->final2;
+					return;
 				}
-				else
+
+				$result = $this->_compare_conflict_seq('final2', 'final1');
+
+				if ($result['merge_found'])
 				{
-					$merge[] = $line;
+					$this->_merged = &$this->final1;
+					return;
 				}
 			}
 
-			if ($merge_found)
-			{
-				$this->final2 = $merge;
-				$this->_merged = &$this->final2;
-			}
-
 			return;
 		}
 
 		// CASE TWO: Added lines from orig to final2 but final1 had added lines too. Just merge them.
 		if (!sizeof($this->orig) && $this->final1 !== $this->final2 && sizeof($this->final1) && sizeof($this->final2))
 		{
-			$this->final2 = array_merge($this->final1, $this->final2);
-			$this->_merged = &$this->final2;
+			$result = $this->_compare_conflict_seq('final2', 'final1');
+
+			if ($result['merge_found'])
+			{
+				$this->final2 = $this->final1;
+				$this->_merged = &$this->final1;
+			}
+			else
+			{
+				$result = $this->_compare_conflict_seq('final1', 'final2');
+
+				if (!$result['merge_found'])
+				{
+					$this->final2 = array_merge($this->final1, $this->final2);
+					$this->_merged = &$this->final2;
+				}
+				else
+				{
+					$this->final2 = $this->final1;
+					$this->_merged = &$this->final1;
+				}
+			}
 
 			return;
 		}
@@ -809,22 +997,43 @@ class diff3_op
 		// CASE THREE: Removed lines (orig has the to-remove line(s), but final1 has additional lines which does not need to be removed). Just remove orig from final1 and then use final1 as final2/merge
 		if (!sizeof($this->final2) && sizeof($this->orig) && sizeof($this->final1) && $this->orig !== $this->final1)
 		{
-			$merged = $this->final1;
+			// First of all, try to find the code in orig in final1. ;)
+			$compare_seq = sizeof($this->orig);
+			$begin = -1;
+			$j = $end = 0;
 
 			foreach ($this->final1 as $i => $line)
 			{
-				foreach ($this->orig as $j => $old_line)
+				if (trim($line) === trim($this->orig[$j]))
 				{
-					if (trim($line) === trim($old_line))
+					if ($begin === -1)
 					{
-						unset($merged[$i]);
+						$begin = $i;
+					}
+
+					if (isset($this->orig[$j+1]))
+					{
+						$j++;
 					}
 				}
+
+				if ($begin !== -1)
+				{
+					$end++;
+				}
 			}
 
-			if (sizeof($merged))
+			if ($begin !== -1 && $begin + ($compare_seq - 1) == $end)
 			{
-				$this->final2 = array_values($merged);
+				foreach ($this->final1 as $i => $line)
+				{
+					if ($i < $begin || $i > $end)
+					{
+						$merged[] = $line;
+					}
+				}
+
+				$this->final2 = $merged;
 				$this->_merged = &$this->final2;
 			}
 
-- 
cgit v1.2.1


From 97be42d31c50efb248086c7147e6e768154404a4 Mon Sep 17 00:00:00 2001
From: Meik Sievertsen <acydburn@phpbb.com>
Date: Sun, 20 Sep 2009 16:20:20 +0000
Subject: improve code to detect and solve conflicts for code removed from one
 version to another.

git-svn-id: file:///svn/phpbb/branches/phpBB-3_0_0@10168 89ea8834-ac86-4346-8a33-228a782c2dd0
---
 phpBB/includes/diff/diff.php | 24 ++++++++++++++++--------
 1 file changed, 16 insertions(+), 8 deletions(-)

(limited to 'phpBB/includes/diff/diff.php')

diff --git a/phpBB/includes/diff/diff.php b/phpBB/includes/diff/diff.php
index 6bda3df43e..60af574b78 100644
--- a/phpBB/includes/diff/diff.php
+++ b/phpBB/includes/diff/diff.php
@@ -997,30 +997,38 @@ class diff3_op
 		// CASE THREE: Removed lines (orig has the to-remove line(s), but final1 has additional lines which does not need to be removed). Just remove orig from final1 and then use final1 as final2/merge
 		if (!sizeof($this->final2) && sizeof($this->orig) && sizeof($this->final1) && $this->orig !== $this->final1)
 		{
+			$result = $this->_compare_conflict_seq('orig', 'final1');
+
+			if (!$result['merge_found'])
+			{
+				return;
+			}
+
 			// First of all, try to find the code in orig in final1. ;)
 			$compare_seq = sizeof($this->orig);
-			$begin = -1;
-			$j = $end = 0;
+			$begin = $end = -1;
+			$j = 0;
 
-			foreach ($this->final1 as $i => $line)
+			for ($i = 0, $size = sizeof($this->final1); $i < $size; $i++)
 			{
+				$line = $this->final1[$i];
+
 				if (trim($line) === trim($this->orig[$j]))
 				{
+					// Mark begin
 					if ($begin === -1)
 					{
 						$begin = $i;
 					}
 
+					// End is always $i, the last found line
+					$end = $i;
+
 					if (isset($this->orig[$j+1]))
 					{
 						$j++;
 					}
 				}
-
-				if ($begin !== -1)
-				{
-					$end++;
-				}
 			}
 
 			if ($begin !== -1 && $begin + ($compare_seq - 1) == $end)
-- 
cgit v1.2.1