Reduce overhead of pushing existing navigation stack (#672)

* Make StackCopy less awkward

* Clean up comment

* Update docs

* Update docs

* Replace SecondToLast with an arbitrarily deep Peek method

* Update docs

* Handle negative depths in Peek()

10 files changed, 181 insertions, 65 deletions

diff --git a/Xamarin.Forms.Core.UnitTests/NavigationUnitTest.cs b/Xamarin.Forms.Core.UnitTests/NavigationUnitTest.cs
index 1cc3ac6a..7118e149 100644
--- a/Xamarin.Forms.Core.UnitTests/NavigationUnitTest.cs
+++ b/Xamarin.Forms.Core.UnitTests/NavigationUnitTest.cs
@@ -213,29 +213,94 @@ namespace Xamarin.Forms.Core.UnitTests
 		}
 
 		[Test]
-		public async Task TestStackCopy ()
+		public async Task PeekOne()
 		{
-			var nav = new NavigationPage ();
+			var nav = new NavigationPage();
 
 			bool signaled = false;
 			nav.PoppedToRoot += (sender, args) => signaled = true;
 
-			var root = new ContentPage {Content = new View ()};
-			var child1 = new ContentPage {Content = new View ()};
-			var child2 = new ContentPage {Content = new View ()};
+			var root = new ContentPage { Content = new View() };
+			var child1 = new ContentPage { Content = new View() };
+			var child2 = new ContentPage { Content = new View() };
 
-			await nav.PushAsync (root);
-			await nav.PushAsync (child1);
-			await nav.PushAsync (child2);
+			await nav.PushAsync(root);
+			await nav.PushAsync(child1);
+			await nav.PushAsync(child2);
+
+			Assert.AreEqual(((INavigationPageController)nav).Peek(1), child1);
+		}
 
-			var copy = ((INavigationPageController)nav).StackCopy;
+		[Test]
+		public async Task PeekZero()
+		{
+			var nav = new NavigationPage();
 
-			Assert.AreEqual (child2, copy.Pop ());
-			Assert.AreEqual (child1, copy.Pop ());
-			Assert.AreEqual (root, copy.Pop ());
+			bool signaled = false;
+			nav.PoppedToRoot += (sender, args) => signaled = true;
+
+			var root = new ContentPage { Content = new View() };
+			var child1 = new ContentPage { Content = new View() };
+			var child2 = new ContentPage { Content = new View() };
+
+			await nav.PushAsync(root);
+			await nav.PushAsync(child1);
+			await nav.PushAsync(child2);
+
+			Assert.AreEqual(((INavigationPageController)nav).Peek(0), child2);
 		}
 
 		[Test]
+		public async Task PeekPastStackDepth()
+		{
+			var nav = new NavigationPage();
+
+			bool signaled = false;
+			nav.PoppedToRoot += (sender, args) => signaled = true;
+
+			var root = new ContentPage { Content = new View() };
+			var child1 = new ContentPage { Content = new View() };
+			var child2 = new ContentPage { Content = new View() };
+
+			await nav.PushAsync(root);
+			await nav.PushAsync(child1);
+			await nav.PushAsync(child2);
+
+			Assert.AreEqual(((INavigationPageController)nav).Peek(3), null);
+		}
+
+		[Test]
+		public async Task PeekShallow()
+		{
+			var nav = new NavigationPage();
+
+			bool signaled = false;
+			nav.PoppedToRoot += (sender, args) => signaled = true;
+
+			var root = new ContentPage { Content = new View() };
+			var child1 = new ContentPage { Content = new View() };
+			var child2 = new ContentPage { Content = new View() };
+
+			await nav.PushAsync(root);
+			await nav.PushAsync(child1);
+			await nav.PushAsync(child2);
+
+			Assert.AreEqual(((INavigationPageController)nav).Peek(-1), null);
+		}
+
+		[Test]
+		public async Task PeekEmpty([Range(0, 3)] int depth)
+		{
+			var nav = new NavigationPage();
+
+			bool signaled = false;
+			nav.PoppedToRoot += (sender, args) => signaled = true;
+
+			Assert.AreEqual(((INavigationPageController)nav).Peek(depth), null);
+		}
+
+
+		[Test]
 		public void ConstructWithRoot ()
 		{
 			var root = new ContentPage ();
diff --git a/Xamarin.Forms.Core/INavigationPageController.cs b/Xamarin.Forms.Core/INavigationPageController.cs
index eddbe750..d4ae8675 100644
--- a/Xamarin.Forms.Core/INavigationPageController.cs
+++ b/Xamarin.Forms.Core/INavigationPageController.cs
@@ -7,7 +7,9 @@ namespace Xamarin.Forms
 {
 	public interface INavigationPageController
 	{
-		Stack<Page> StackCopy { get; }
+		Page Peek(int depth);
+
+		IEnumerable<Page> Pages { get; }
 
 		int StackDepth { get; }
 
diff --git a/Xamarin.Forms.Core/NavigationPage.cs b/Xamarin.Forms.Core/NavigationPage.cs
index 7b393b9c..fdafec06 100644
--- a/Xamarin.Forms.Core/NavigationPage.cs
+++ b/Xamarin.Forms.Core/NavigationPage.cs
@@ -1,5 +1,6 @@
 using System;
 using System.Collections.Generic;
+using System.Collections.ObjectModel;
 using System.Linq;
 using System.Threading.Tasks;
 using Xamarin.Forms.Internals;
@@ -61,17 +62,23 @@ namespace Xamarin.Forms
 
 		internal Task CurrentNavigationTask { get; set; }
 
-		Stack<Page> INavigationPageController.StackCopy
+		Page INavigationPageController.Peek(int depth)
 		{
-			get
+			if (depth < 0)
 			{
-				var result = new Stack<Page>(PageController.InternalChildren.Count);
-				foreach (Page page in PageController.InternalChildren)
-					result.Push(page);
-				return result;
+				return null;
 			}
+
+			if (PageController.InternalChildren.Count <= depth)
+			{
+				return null;
+			}
+
+			return (Page)PageController.InternalChildren[PageController.InternalChildren.Count - depth - 1];
 		}
 
+		IEnumerable<Page> INavigationPageController.Pages => PageController.InternalChildren.Cast<Page>();
+
 		int INavigationPageController.StackDepth
 		{
 			get { return PageController.InternalChildren.Count; }
diff --git a/Xamarin.Forms.Platform.Android/AppCompat/NavigationPageRenderer.cs b/Xamarin.Forms.Platform.Android/AppCompat/NavigationPageRenderer.cs
index cab4d561..cc474293 100644
--- a/Xamarin.Forms.Platform.Android/AppCompat/NavigationPageRenderer.cs
+++ b/Xamarin.Forms.Platform.Android/AppCompat/NavigationPageRenderer.cs
@@ -268,7 +268,7 @@ namespace Xamarin.Forms.Platform.Android.AppCompat
 				navController.RemovePageRequested += OnRemovePageRequested;
 
 				// If there is already stuff on the stack we need to push it
-				foreach (Page page in navController.StackCopy.Reverse())
+				foreach (Page page in navController.Pages)
 				{
 					PushViewAsync(page, false);
 				}
@@ -461,7 +461,7 @@ namespace Xamarin.Forms.Platform.Android.AppCompat
 
 		Task<bool> OnPopViewAsync(Page page, bool animated)
 		{
-			Page pageToShow = ((INavigationPageController)Element).StackCopy.Skip(1).FirstOrDefault();
+			Page pageToShow = ((INavigationPageController)Element).Peek(1);
 			if (pageToShow == null)
 				return Task.FromResult(false);
 
diff --git a/Xamarin.Forms.Platform.Android/Renderers/NavigationRenderer.cs b/Xamarin.Forms.Platform.Android/Renderers/NavigationRenderer.cs
index c02dc42b..bf6540b9 100644
--- a/Xamarin.Forms.Platform.Android/Renderers/NavigationRenderer.cs
+++ b/Xamarin.Forms.Platform.Android/Renderers/NavigationRenderer.cs
@@ -109,7 +109,7 @@ namespace Xamarin.Forms.Platform.Android
 			newNavController.RemovePageRequested += OnRemovePageRequested;
 
 			// If there is already stuff on the stack we need to push it
-			foreach(Page page in newNavController.StackCopy.Reverse())
+			foreach (Page page in newNavController.Pages)
 			{
 				PushViewAsync(page, false);
 			}
@@ -130,7 +130,7 @@ namespace Xamarin.Forms.Platform.Android
 
 		protected virtual Task<bool> OnPopViewAsync(Page page, bool animated)
 		{
-			Page pageToShow = ((INavigationPageController)Element).StackCopy.Skip(1).FirstOrDefault();
+			Page pageToShow = ((INavigationPageController)Element).Peek(1);
 			if (pageToShow == null)
 				return Task.FromResult(false);
 
diff --git a/Xamarin.Forms.Platform.WP8/NavigationPageRenderer.cs b/Xamarin.Forms.Platform.WP8/NavigationPageRenderer.cs
index 1637b1d0..e2837f05 100644
--- a/Xamarin.Forms.Platform.WP8/NavigationPageRenderer.cs
+++ b/Xamarin.Forms.Platform.WP8/NavigationPageRenderer.cs
@@ -139,7 +139,7 @@ namespace Xamarin.Forms.Platform.WinPhone
 			var platform = Element.Platform as Platform;
 			if (platform != null)
 			{
-				if (e.Page == ((INavigationPageController)Element).StackCopy.LastOrDefault())
+				if (e.Page == ((INavigationPageController)Element).Pages.FirstOrDefault()) 
 					((IPageController)e.Page).IgnoresContainerArea = true;
 				e.Task = platform.PushCore(e.Page, Element, e.Animated, e.Realize).ContinueWith((t, o) => true, null);
 			}
diff --git a/Xamarin.Forms.Platform.WinRT/NavigationPageRenderer.cs b/Xamarin.Forms.Platform.WinRT/NavigationPageRenderer.cs
index 593a6747..d1fdee0a 100644
--- a/Xamarin.Forms.Platform.WinRT/NavigationPageRenderer.cs
+++ b/Xamarin.Forms.Platform.WinRT/NavigationPageRenderer.cs
@@ -397,7 +397,7 @@ namespace Xamarin.Forms.Platform.WinRT
 
 		void OnPopRequested(object sender, NavigationRequestedEventArgs e)
 		{
-			var newCurrent = (Page)PageController.InternalChildren[PageController.InternalChildren.Count - 2];
+			var newCurrent = ((INavigationPageController)Element).Peek(1);
 			SetPage(newCurrent, e.Animated, true);
 		}
 
@@ -418,8 +418,10 @@ namespace Xamarin.Forms.Platform.WinRT
 
 		void PushExistingNavigationStack()
 		{
-			for (int i = ((INavigationPageController)Element).StackCopy.Count - 1; i >= 0; i--)
-				SetPage(((INavigationPageController)Element).StackCopy.ElementAt(i), false, false);
+			foreach (var page in ((INavigationPageController)Element).Pages)
+			{
+				SetPage(page, false, false);
+			}
 		}
 
 		void SetPage(Page page, bool isAnimated, bool isPopping)
diff --git a/Xamarin.Forms.Platform.iOS/Renderers/NavigationRenderer.cs b/Xamarin.Forms.Platform.iOS/Renderers/NavigationRenderer.cs
index 6b698f22..1465b8dc 100644
--- a/Xamarin.Forms.Platform.iOS/Renderers/NavigationRenderer.cs
+++ b/Xamarin.Forms.Platform.iOS/Renderers/NavigationRenderer.cs
@@ -211,7 +211,7 @@ namespace Xamarin.Forms.Platform.iOS
 			UpdateBarTextColor();
 
 			// If there is already stuff on the stack we need to push it
-			((INavigationPageController)navPage).StackCopy.Reverse().ForEach(async p => await PushPageAsync(p, false));
+			((INavigationPageController)navPage).Pages.ForEach(async p => await PushPageAsync(p, false));
 
 			_tracker = new VisualElementTracker(this);
 
@@ -617,7 +617,7 @@ namespace Xamarin.Forms.Platform.iOS
 			if (containerController == null)
 				return;
 			var currentChild = containerController.Child;
-			var firstPage = ((INavigationPageController)Element).StackCopy.LastOrDefault();
+			var firstPage = ((INavigationPageController)Element).Pages.FirstOrDefault(); 
 			if ((firstPage != pageBeingRemoved && currentChild != firstPage && NavigationPage.GetHasBackButton(currentChild)) || _parentMasterDetailPage == null)
 				return;
 
diff --git a/docs/Xamarin.Forms.Core/Xamarin.Forms/INavigationPageController.xml b/docs/Xamarin.Forms.Core/Xamarin.Forms/INavigationPageController.xml
index b72feb0b..95aeae7e 100644
--- a/docs/Xamarin.Forms.Core/Xamarin.Forms/INavigationPageController.xml
+++ b/docs/Xamarin.Forms.Core/Xamarin.Forms/INavigationPageController.xml
@@ -26,6 +26,42 @@
         <remarks>To be added.</remarks>
       </Docs>
     </Member>
+    <Member MemberName="Pages">
+      <MemberSignature Language="C#" Value="public System.Collections.Generic.IEnumerable&lt;Xamarin.Forms.Page&gt; Pages { get; }" />
+      <MemberSignature Language="ILAsm" Value=".property instance class System.Collections.Generic.IEnumerable`1&lt;class Xamarin.Forms.Page&gt; Pages" />
+      <MemberType>Property</MemberType>
+      <AssemblyInfo>
+        <AssemblyVersion>2.0.0.0</AssemblyVersion>
+      </AssemblyInfo>
+      <ReturnValue>
+        <ReturnType>System.Collections.Generic.IEnumerable&lt;Xamarin.Forms.Page&gt;</ReturnType>
+      </ReturnValue>
+      <Docs>
+        <summary>To be added.</summary>
+        <value>To be added.</value>
+        <remarks>To be added.</remarks>
+      </Docs>
+    </Member>
+    <Member MemberName="Peek">
+      <MemberSignature Language="C#" Value="public Xamarin.Forms.Page Peek (int depth);" />
+      <MemberSignature Language="ILAsm" Value=".method public hidebysig newslot virtual instance class Xamarin.Forms.Page Peek(int32 depth) cil managed" />
+      <MemberType>Method</MemberType>
+      <AssemblyInfo>
+        <AssemblyVersion>2.0.0.0</AssemblyVersion>
+      </AssemblyInfo>
+      <ReturnValue>
+        <ReturnType>Xamarin.Forms.Page</ReturnType>
+      </ReturnValue>
+      <Parameters>
+        <Parameter Name="depth" Type="System.Int32" />
+      </Parameters>
+      <Docs>
+        <param name="depth">To be added.</param>
+        <summary>To be added.</summary>
+        <returns>To be added.</returns>
+        <remarks>To be added.</remarks>
+      </Docs>
+    </Member>
     <Member MemberName="PopAsyncInner">
       <MemberSignature Language="C#" Value="public System.Threading.Tasks.Task&lt;Xamarin.Forms.Page&gt; PopAsyncInner (bool animated, bool fast = false);" />
       <MemberSignature Language="ILAsm" Value=".method public hidebysig newslot virtual instance class System.Threading.Tasks.Task`1&lt;class Xamarin.Forms.Page&gt; PopAsyncInner(bool animated, bool fast) cil managed" />
@@ -108,22 +144,6 @@
         <remarks>To be added.</remarks>
       </Docs>
     </Member>
-    <Member MemberName="StackCopy">
-      <MemberSignature Language="C#" Value="public System.Collections.Generic.Stack&lt;Xamarin.Forms.Page&gt; StackCopy { get; }" />
-      <MemberSignature Language="ILAsm" Value=".property instance class System.Collections.Generic.Stack`1&lt;class Xamarin.Forms.Page&gt; StackCopy" />
-      <MemberType>Property</MemberType>
-      <AssemblyInfo>
-        <AssemblyVersion>2.0.0.0</AssemblyVersion>
-      </AssemblyInfo>
-      <ReturnValue>
-        <ReturnType>System.Collections.Generic.Stack&lt;Xamarin.Forms.Page&gt;</ReturnType>
-      </ReturnValue>
-      <Docs>
-        <summary>For internal use by platform renderers.</summary>
-        <value>To be added.</value>
-        <remarks>To be added.</remarks>
-      </Docs>
-    </Member>
     <Member MemberName="StackDepth">
       <MemberSignature Language="C#" Value="public int StackDepth { get; }" />
       <MemberSignature Language="ILAsm" Value=".property instance int32 StackDepth" />
diff --git a/docs/Xamarin.Forms.Core/Xamarin.Forms/NavigationPage.xml b/docs/Xamarin.Forms.Core/Xamarin.Forms/NavigationPage.xml
index 77e203f5..1094d154 100644
--- a/docs/Xamarin.Forms.Core/Xamarin.Forms/NavigationPage.xml
+++ b/docs/Xamarin.Forms.Core/Xamarin.Forms/NavigationPage.xml
@@ -450,7 +450,7 @@
           <AttributeName>System.Diagnostics.DebuggerStepThrough</AttributeName>
         </Attribute>
         <Attribute>
-          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PopAsync&gt;d__38))</AttributeName>
+          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PopAsync&gt;d__39))</AttributeName>
         </Attribute>
       </Attributes>
       <ReturnValue>
@@ -548,7 +548,7 @@
           <AttributeName>System.Diagnostics.DebuggerStepThrough</AttributeName>
         </Attribute>
         <Attribute>
-          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PopToRootAsync&gt;d__46))</AttributeName>
+          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PopToRootAsync&gt;d__47))</AttributeName>
         </Attribute>
       </Attributes>
       <ReturnValue>
@@ -605,7 +605,7 @@
           <AttributeName>System.Diagnostics.DebuggerStepThrough</AttributeName>
         </Attribute>
         <Attribute>
-          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PushAsync&gt;d__48))</AttributeName>
+          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;PushAsync&gt;d__49))</AttributeName>
         </Attribute>
       </Attributes>
       <ReturnValue>
@@ -844,6 +844,42 @@ public class MyPage : NavigationPage
         <remarks>To be added.</remarks>
       </Docs>
     </Member>
+    <Member MemberName="Xamarin.Forms.INavigationPageController.Pages">
+      <MemberSignature Language="C#" Value="System.Collections.Generic.IEnumerable&lt;Xamarin.Forms.Page&gt; Xamarin.Forms.INavigationPageController.Pages { get; }" />
+      <MemberSignature Language="ILAsm" Value=".property instance class System.Collections.Generic.IEnumerable`1&lt;class Xamarin.Forms.Page&gt; Xamarin.Forms.INavigationPageController.Pages" />
+      <MemberType>Property</MemberType>
+      <AssemblyInfo>
+        <AssemblyVersion>2.0.0.0</AssemblyVersion>
+      </AssemblyInfo>
+      <ReturnValue>
+        <ReturnType>System.Collections.Generic.IEnumerable&lt;Xamarin.Forms.Page&gt;</ReturnType>
+      </ReturnValue>
+      <Docs>
+        <summary>To be added.</summary>
+        <value>To be added.</value>
+        <remarks>To be added.</remarks>
+      </Docs>
+    </Member>
+    <Member MemberName="Xamarin.Forms.INavigationPageController.Peek">
+      <MemberSignature Language="C#" Value="Xamarin.Forms.Page INavigationPageController.Peek (int depth);" />
+      <MemberSignature Language="ILAsm" Value=".method hidebysig newslot virtual instance class Xamarin.Forms.Page Xamarin.Forms.INavigationPageController.Peek(int32 depth) cil managed" />
+      <MemberType>Method</MemberType>
+      <AssemblyInfo>
+        <AssemblyVersion>2.0.0.0</AssemblyVersion>
+      </AssemblyInfo>
+      <ReturnValue>
+        <ReturnType>Xamarin.Forms.Page</ReturnType>
+      </ReturnValue>
+      <Parameters>
+        <Parameter Name="depth" Type="System.Int32" />
+      </Parameters>
+      <Docs>
+        <param name="depth">To be added.</param>
+        <summary>To be added.</summary>
+        <returns>To be added.</returns>
+        <remarks>To be added.</remarks>
+      </Docs>
+    </Member>
     <Member MemberName="Xamarin.Forms.INavigationPageController.PopAsyncInner">
       <MemberSignature Language="C#" Value="System.Threading.Tasks.Task&lt;Xamarin.Forms.Page&gt; INavigationPageController.PopAsyncInner (bool animated, bool fast);" />
       <MemberSignature Language="ILAsm" Value=".method hidebysig newslot virtual instance class System.Threading.Tasks.Task`1&lt;class Xamarin.Forms.Page&gt; Xamarin.Forms.INavigationPageController.PopAsyncInner(bool animated, bool fast) cil managed" />
@@ -856,7 +892,7 @@ public class MyPage : NavigationPage
           <AttributeName>System.Diagnostics.DebuggerStepThrough</AttributeName>
         </Attribute>
         <Attribute>
-          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;Xamarin-Forms-INavigationPageController-PopAsyncInner&gt;d__63))</AttributeName>
+          <AttributeName>System.Runtime.CompilerServices.AsyncStateMachine(typeof(Xamarin.Forms.NavigationPage/&lt;Xamarin-Forms-INavigationPageController-PopAsyncInner&gt;d__64))</AttributeName>
         </Attribute>
       </Attributes>
       <ReturnValue>
@@ -874,22 +910,6 @@ public class MyPage : NavigationPage
         <remarks>To be added.</remarks>
       </Docs>
     </Member>
-    <Member MemberName="Xamarin.Forms.INavigationPageController.StackCopy">
-      <MemberSignature Language="C#" Value="System.Collections.Generic.Stack&lt;Xamarin.Forms.Page&gt; Xamarin.Forms.INavigationPageController.StackCopy { get; }" />
-      <MemberSignature Language="ILAsm" Value=".property instance class System.Collections.Generic.Stack`1&lt;class Xamarin.Forms.Page&gt; Xamarin.Forms.INavigationPageController.StackCopy" />
-      <MemberType>Property</MemberType>
-      <AssemblyInfo>
-        <AssemblyVersion>2.0.0.0</AssemblyVersion>
-      </AssemblyInfo>
-      <ReturnValue>
-        <ReturnType>System.Collections.Generic.Stack&lt;Xamarin.Forms.Page&gt;</ReturnType>
-      </ReturnValue>
-      <Docs>
-        <summary>Internal</summary>
-        <value>To be added.</value>
-        <remarks>To be added.</remarks>
-      </Docs>
-    </Member>
     <Member MemberName="Xamarin.Forms.INavigationPageController.StackDepth">
       <MemberSignature Language="C#" Value="int Xamarin.Forms.INavigationPageController.StackDepth { get; }" />
       <MemberSignature Language="ILAsm" Value=".property instance int32 Xamarin.Forms.INavigationPageController.StackDepth" />