Allow users to configure a Result Limit on the [Queryable] attribute to limit query results

The result limit applies both to GETs on the action resource and to OData queries on the resource. If the results are limited, we generate a next page link using a skip like this:
http://localhost/Customers?$skip=10
We will consider using $skiptoken for next page links in the future since it is more performant and avoids duplicate entry issues.

10 files changed, 291 insertions, 31 deletions

diff --git a/src/System.Web.Http.OData/OData/Formatter/ODataMediaTypeFormatter.cs b/src/System.Web.Http.OData/OData/Formatter/ODataMediaTypeFormatter.cs
index e85c50fb..9e110e21 100644
--- a/src/System.Web.Http.OData/OData/Formatter/ODataMediaTypeFormatter.cs
+++ b/src/System.Web.Http.OData/OData/Formatter/ODataMediaTypeFormatter.cs
@@ -326,7 +326,8 @@ namespace System.Web.Http.OData.Formatter
                                                                         UrlHelper = urlHelper,
                                                                         RootProjectionNode = rootProjectionNode,
                                                                         CurrentProjectionNode = rootProjectionNode,
-                                                                        ServiceOperationName = operationName
+                                                                        ServiceOperationName = operationName,
+                                                                        Request = Request
                                                                     };
 
                     serializer.WriteObject(value, messageWriter, writeContext);
diff --git a/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataEntityTypeSerializer.cs b/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataEntityTypeSerializer.cs
index 02ac2350..c5d431c9 100644
--- a/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataEntityTypeSerializer.cs
+++ b/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataEntityTypeSerializer.cs
@@ -144,6 +144,7 @@ namespace System.Web.Http.OData.Formatter.Serialization
                         childWriteContext.RootProjectionNode = writeContext.RootProjectionNode;
                         childWriteContext.CurrentProjectionNode = expandNode;
                         childWriteContext.ServiceOperationName = writeContext.ServiceOperationName;
+                        childWriteContext.Request = writeContext.Request;
 
                         serializer.WriteObjectInline(propertyValue, writer, childWriteContext);
                         writer.WriteEnd();
diff --git a/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataFeedSerializer.cs b/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataFeedSerializer.cs
index b0b61729..0439be98 100644
--- a/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataFeedSerializer.cs
+++ b/src/System.Web.Http.OData/OData/Formatter/Serialization/ODataFeedSerializer.cs
@@ -2,9 +2,11 @@
 
 using System.Collections;
 using System.Diagnostics.Contracts;
+using System.Net.Http;
 using System.Runtime.Serialization;
 using System.Web.Http.OData.Builder;
 using System.Web.Http.OData.Properties;
+using System.Web.Http.OData.Query;
 using Microsoft.Data.Edm;
 using Microsoft.Data.OData;
 using Microsoft.Data.OData.Atom;
@@ -92,6 +94,19 @@ namespace System.Web.Http.OData.Formatter.Serialization
                     feed.Count = odataFeedAnnotations.Count;
                     feed.NextPageLink = odataFeedAnnotations.NextPageLink;
                 }
+                else
+                {
+                    object nextPageLinkPropertyValue;
+                    HttpRequestMessage request = writeContext.Request;
+                    if (request != null && request.Properties.TryGetValue(ODataQueryOptions.NextPageLinkPropertyKey, out nextPageLinkPropertyValue))
+                    {
+                        Uri nextPageLink = nextPageLinkPropertyValue as Uri;
+                        if (nextPageLink != null)
+                        {
+                            feed.NextPageLink = nextPageLink;
+                        }
+                    }
+                }
 
                 writer.WriteStart(feed);
 
diff --git a/src/System.Web.Http.OData/OData/Query/ODataQueryOptions.cs b/src/System.Web.Http.OData/OData/Query/ODataQueryOptions.cs
index c9d736a7..73123f41 100644
--- a/src/System.Web.Http.OData/OData/Query/ODataQueryOptions.cs
+++ b/src/System.Web.Http.OData/OData/Query/ODataQueryOptions.cs
@@ -1,9 +1,13 @@
 // Copyright (c) Microsoft Open Technologies, Inc. All rights reserved. See License.txt in the project root for license information.
 
 using System.Collections.Generic;
+using System.Diagnostics.CodeAnalysis;
 using System.Diagnostics.Contracts;
+using System.Globalization;
 using System.Linq;
 using System.Net.Http;
+using System.Reflection;
+using System.Text;
 using System.Web.Http.Dispatcher;
 using System.Web.Http.OData.Properties;
 using Microsoft.Data.Edm;
@@ -23,6 +27,9 @@ namespace System.Web.Http.OData.Query
         private const string Linq2SqlQueryProviderNamespace = "System.Data.Linq";
         private const string Linq2ObjectsQueryProviderNamespace = "System.Linq";
 
+        internal const string NextPageLinkPropertyKey = "MS_NextPageLink";
+        private static readonly MethodInfo _limitResultsGenericMethod = typeof(ODataQueryOptions).GetMethod("LimitResults");
+
         private IAssembliesResolver _assembliesResolver;
 
         /// <summary>
@@ -51,8 +58,9 @@ namespace System.Web.Http.OData.Query
             // fallback to the default assemblies resolver if none available.
             _assembliesResolver = _assembliesResolver ?? new DefaultAssembliesResolver();
 
-            // remember the context
+            // remember the context and request
             Context = context;
+            Request = request;
 
             // Parse the query from request Uri
             RawValues = new ODataRawQueryOptions();
@@ -106,6 +114,11 @@ namespace System.Web.Http.OData.Query
         public ODataQueryContext Context { get; private set; }
 
         /// <summary>
+        /// Gets the request message associated with this instance.
+        /// </summary>
+        public HttpRequestMessage Request { get; private set; }
+
+        /// <summary>
         /// Gets the raw string of all the OData query options
         /// </summary>
         public ODataRawQueryOptions RawValues { get; private set; }
@@ -188,9 +201,11 @@ namespace System.Web.Http.OData.Query
             OrderByQueryOption orderBy = OrderBy;
 
             // $skip or $top require a stable sort for predictable results.
+            // Result limits require a stable sort to be able to generate a next page link.
             // If either is present in the query and we have permission,
             // generate an $orderby that will produce a stable sort.
-            if ((Skip != null || Top != null) && querySettings.EnsureStableOrdering && !Context.IsPrimitiveClrType)
+            if (querySettings.EnsureStableOrdering && !Context.IsPrimitiveClrType &&
+                (Skip != null || Top != null || querySettings.ResultLimit.HasValue))
             {
                 // If there is no OrderBy present, we manufacture a default.
                 // If an OrderBy is already present, we add any missing
@@ -217,6 +232,17 @@ namespace System.Web.Http.OData.Query
                 result = Top.ApplyTo(result);
             }
 
+            if (querySettings.ResultLimit.HasValue)
+            {
+                bool resultsLimited;
+                result = LimitResults(result, querySettings.ResultLimit.Value, Context, out resultsLimited);
+                if (resultsLimited && Request.RequestUri != null && Request.RequestUri.IsAbsoluteUri)
+                {
+                    Uri nextPageLink = GetNextPageLink(Request, querySettings.ResultLimit.Value);
+                    Request.Properties.Add(NextPageLinkPropertyKey, nextPageLink);
+                }
+            }
+
             return result;
         }
 
@@ -330,5 +356,111 @@ namespace System.Web.Http.OData.Query
 
             return orderBy;
         }
+
+        internal static IQueryable LimitResults(IQueryable queryable, int limit, ODataQueryContext context, out bool resultsLimited)
+        {
+            MethodInfo genericMethod = _limitResultsGenericMethod.MakeGenericMethod(context.EntityClrType);
+            object[] args = new object[] { queryable, limit, null };
+            IQueryable results = genericMethod.Invoke(null, args) as IQueryable;
+            resultsLimited = (bool)args[2];
+            return results;
+        }
+
+        /// <summary>
+        /// Limits the query results to a maximum number of results.
+        /// </summary>
+        /// <typeparam name="T">The entity CLR type</typeparam>
+        /// <param name="queryable">The queryable to limit.</param>
+        /// <param name="limit">The query result limit.</param>
+        /// <param name="resultsLimited"><c>true</c> if the query results were limited; <c>false</c> otherwise</param>
+        /// <returns>The limited query results.</returns>
+        [SuppressMessage("Microsoft.Design", "CA1021:AvoidOutParameters", Justification = "Not intended for public use, only public to enable invokation without security issues.")]
+        public static IQueryable<T> LimitResults<T>(IQueryable<T> queryable, int limit, out bool resultsLimited)
+        {
+            List<T> list = new List<T>();
+            resultsLimited = false;
+            using (IEnumerator<T> enumerator = queryable.GetEnumerator())
+            {
+                while (enumerator.MoveNext())
+                {
+                    list.Add(enumerator.Current);
+                    if (list.Count == limit)
+                    {
+                        // If there are more results on the enumerator, we are limiting the results
+                        if (enumerator.MoveNext())
+                        {
+                            resultsLimited = true;
+                        }
+                        break;
+                    }
+                }
+            }
+            return list.AsQueryable();
+        }
+
+        internal static Uri GetNextPageLink(HttpRequestMessage request, int resultLimit)
+        {
+            Contract.Assert(request != null);
+            Contract.Assert(request.RequestUri != null);
+            Contract.Assert(request.RequestUri.IsAbsoluteUri);
+
+            StringBuilder queryBuilder = new StringBuilder();
+
+            int nextPageSkip = resultLimit;
+
+            IEnumerable<KeyValuePair<string, string>> queryParameters = request.GetQueryNameValuePairs();
+            foreach (KeyValuePair<string, string> kvp in queryParameters)
+            {
+                string key = kvp.Key;
+                string value = kvp.Value;
+                switch (key)
+                {
+                    case "$top":
+                        int top;
+                        if (Int32.TryParse(value, out top))
+                        {
+                            // There is no next page if the $top query option's value is less than or equal to the result limit.
+                            Contract.Assert(top > resultLimit);
+                            // We decrease top by the resultLimit because that's the number of results we're returning in the current page
+                            value = (top - resultLimit).ToString(CultureInfo.InvariantCulture);
+                        }
+                        break;
+                    case "$skip":
+                        int skip;
+                        if (Int32.TryParse(value, out skip))
+                        {
+                            // We increase skip by the resultLimit because that's the number of results we're returning in the current page
+                            nextPageSkip += skip;
+                        }
+                        continue;
+                    default:
+                        break;
+                }
+
+                if (key.Length > 0 && key[0] == '$')
+                {
+                    // $ is a legal first character in query keys
+                    key = '$' + Uri.EscapeDataString(key.Substring(1));
+                }
+                else
+                {
+                    key = Uri.EscapeDataString(key);
+                }
+                value = Uri.EscapeDataString(value);
+
+                queryBuilder.Append(key);
+                queryBuilder.Append('=');
+                queryBuilder.Append(value);
+                queryBuilder.Append('&');
+            }
+
+            queryBuilder.AppendFormat("$skip={0}", nextPageSkip);
+
+            UriBuilder uriBuilder = new UriBuilder(request.RequestUri)
+            {
+                Query = queryBuilder.ToString()
+            };
+            return uriBuilder.Uri;
+        }
     }
 }
diff --git a/src/System.Web.Http.OData/OData/Query/ODataQuerySettings.cs b/src/System.Web.Http.OData/OData/Query/ODataQuerySettings.cs
index f84481a3..88a5efc1 100644
--- a/src/System.Web.Http.OData/OData/Query/ODataQuerySettings.cs
+++ b/src/System.Web.Http.OData/OData/Query/ODataQuerySettings.cs
@@ -49,5 +49,13 @@ namespace System.Web.Http.OData.Query
                 _handleNullPropagationOption = value;
             }
         }
+
+        /// <summary>
+        /// Gets or sets the maximum number of query results to return.
+        /// </summary>
+        /// <value>
+        /// The maximum number of query results to to return, or <c>null</c> if there is no limit.
+        /// </value>
+        public int? ResultLimit { get; set; }
     }
 }
diff --git a/src/System.Web.Http.OData/Properties/SRResources.Designer.cs b/src/System.Web.Http.OData/Properties/SRResources.Designer.cs
index 0fbec7aa..16269bdf 100644
--- a/src/System.Web.Http.OData/Properties/SRResources.Designer.cs
+++ b/src/System.Web.Http.OData/Properties/SRResources.Designer.cs
@@ -1,7 +1,7 @@
 //------------------------------------------------------------------------------
 // <auto-generated>
 //     This code was generated by a tool.
-//     Runtime Version:4.0.30319.18003
+//     Runtime Version:4.0.30319.18010
 //
 //     Changes to this file may cause incorrect behavior and will be lost if
 //     the code is regenerated.
@@ -871,6 +871,15 @@ namespace System.Web.Http.OData.Properties {
         }
         
         /// <summary>
+        ///   Looks up a localized string similar to The result limit must be a positive number..
+        /// </summary>
+        internal static string ResultLimitMustBePositive {
+            get {
+                return ResourceManager.GetString("ResultLimitMustBePositive", resourceCulture);
+            }
+        }
+        
+        /// <summary>
         ///   Looks up a localized string similar to The type &apos;{0}&apos; cannot be configured as a ComplexType. It was previously configured as an EntityType..
         /// </summary>
         internal static string TypeCannotBeComplexWasEntity {
diff --git a/src/System.Web.Http.OData/Properties/SRResources.resx b/src/System.Web.Http.OData/Properties/SRResources.resx
index d6a69098..462b533f 100644
--- a/src/System.Web.Http.OData/Properties/SRResources.resx
+++ b/src/System.Web.Http.OData/Properties/SRResources.resx
@@ -420,4 +420,7 @@
   <data name="NoODataMediaTypeFormatterFound" xml:space="preserve">
     <value>The ODataParameterBindingAttribute requires that an ODataMediaTypeFormatter be registered with the HttpConfiguration.</value>
   </data>
+  <data name="ResultLimitMustBePositive" xml:space="preserve">
+    <value>The result limit must be a positive number.</value>
+  </data>
 </root>
\ No newline at end of file
diff --git a/src/System.Web.Http.OData/QueryableAttribute.cs b/src/System.Web.Http.OData/QueryableAttribute.cs
index de3f4c41..f61809a2 100644
--- a/src/System.Web.Http.OData/QueryableAttribute.cs
+++ b/src/System.Web.Http.OData/QueryableAttribute.cs
@@ -22,6 +22,7 @@ namespace System.Web.Http
     public class QueryableAttribute : ActionFilterAttribute
     {
         private HandleNullPropagationOption _handleNullPropagationOption = HandleNullPropagationOption.Default;
+        private int? _resultLimit;
 
         /// <summary>
         /// Enables a controller action to support OData query parameters.
@@ -63,6 +64,28 @@ namespace System.Web.Http
             }
         }
 
+        /// <summary>
+        /// Gets or sets the maximum number of query results to send back to clients.
+        /// </summary>
+        /// <value>
+        /// The maximum number of query results to send back to clients.
+        /// </value>
+        public int ResultLimit
+        {
+            get
+            {
+                return _resultLimit ?? default(int);
+            }
+            set
+            {
+                if (value <= 0)
+                {
+                    throw Error.Argument(SRResources.ResultLimitMustBePositive);
+                }
+                _resultLimit = value;
+            }
+        }
+
         public override void OnActionExecuted(HttpActionExecutedContext actionExecutedContext)
         {
             if (actionExecutedContext == null)
@@ -99,14 +122,13 @@ namespace System.Web.Http
             IQueryable queryable = null;
             if (response != null && response.IsSuccessStatusCode && response.TryGetContentValue(out query))
             {
-                if (request.RequestUri != null && !String.IsNullOrWhiteSpace(request.RequestUri.Query))
+                // Apply the query if there are any query options or if there is a result limit set
+                if (request.RequestUri != null && (!String.IsNullOrWhiteSpace(request.RequestUri.Query) || _resultLimit.HasValue))
                 {
                     ValidateQuery(request);
 
                     try
                     {
-                        ODataQueryContext queryContext;
-
                         Type originalQueryType = query.GetType();
                         Type entityClrType = TypeHelper.GetImplementedIEnumerableType(originalQueryType);
 
@@ -122,28 +144,7 @@ namespace System.Web.Http
                                 originalQueryType.FullName);
                         }
 
-                        // Primitive types do not construct an EDM model and deal only with the CLR Type
-                        if (TypeHelper.IsQueryPrimitiveType(entityClrType))
-                        {
-                            queryContext = new ODataQueryContext(entityClrType);
-                        }
-                        else
-                        {
-                            // Get model for the entire app
-                            IEdmModel model = configuration.GetEdmModel();
-
-                            if (model == null)
-                            {
-                                // user has not configured anything, now let's create one just for this type
-                                // and cache it in the action descriptor
-                                model = actionDescriptor.GetEdmModel(entityClrType);
-                                Contract.Assert(model != null);
-                            }
-
-                            // parses the query from request uri
-                            queryContext = new ODataQueryContext(model, entityClrType);
-                        }
-
+                        ODataQueryContext queryContext = CreateQueryContext(entityClrType, configuration, actionDescriptor);
                         ODataQueryOptions queryOptions = new ODataQueryOptions(queryContext, request);
 
                         // Filter and OrderBy require entity sets.  Top and Skip may accept primitives.
@@ -167,13 +168,13 @@ namespace System.Web.Http
                         ODataQuerySettings querySettings = new ODataQuerySettings
                         {
                             EnsureStableOrdering = EnsureStableOrdering,
-                            HandleNullPropagation = HandleNullPropagation
+                            HandleNullPropagation = HandleNullPropagation,
+                            ResultLimit = _resultLimit
                         };
 
                         queryable = queryOptions.ApplyTo(queryable, querySettings);
 
                         Contract.Assert(queryable != null);
-
                         // we don't support shape changing query composition
                         ((ObjectContent)response.Content).Value = queryable;
                     }
@@ -189,6 +190,31 @@ namespace System.Web.Http
             }
         }
 
+        private static ODataQueryContext CreateQueryContext(Type entityClrType, HttpConfiguration configuration, HttpActionDescriptor actionDescriptor)
+        {
+            // Primitive types do not construct an EDM model and deal only with the CLR Type
+            if (TypeHelper.IsQueryPrimitiveType(entityClrType))
+            {
+                return new ODataQueryContext(entityClrType);
+            }
+            else
+            {
+                // Get model for the entire app
+                IEdmModel model = configuration.GetEdmModel();
+
+                if (model == null)
+                {
+                    // user has not configured anything, now let's create one just for this type
+                    // and cache it in the action descriptor
+                    model = actionDescriptor.GetEdmModel(entityClrType);
+                    Contract.Assert(model != null);
+                }
+
+                // parses the query from request uri
+                return new ODataQueryContext(model, entityClrType);
+            }
+        }
+
         /// <summary>
         /// Validates that the OData query parameters of the incoming request are supported.
         /// </summary>
diff --git a/test/System.Web.Http.OData.Test/OData/Formatter/Serialization/ODataFeedSerializerTests.cs b/test/System.Web.Http.OData.Test/OData/Formatter/Serialization/ODataFeedSerializerTests.cs
index 0ad96dcd..85bdb597 100644
--- a/test/System.Web.Http.OData.Test/OData/Formatter/Serialization/ODataFeedSerializerTests.cs
+++ b/test/System.Web.Http.OData.Test/OData/Formatter/Serialization/ODataFeedSerializerTests.cs
@@ -128,5 +128,31 @@ namespace System.Web.Http.OData.Formatter.Serialization
             mockCustomerSerializer.Verify();
             mockWriter.Verify();
         }
+
+        [Fact]
+        public void WriteObjectInline_Writes_RequestNextPageLink()
+        {
+            // Arrange
+            var mockSerializerProvider = new Mock<ODataSerializerProvider>(_model);
+            var mockCustomerSerializer = new Mock<ODataSerializer>(ODataPayloadKind.Entry);
+            var mockWriter = new Mock<ODataWriter>();
+
+            Uri expectedNextLink = new Uri("http://nextlink.com");
+            _writeContext.Request = new HttpRequestMessage();
+            _writeContext.Request.Properties.Add("MS_NextPageLink", expectedNextLink);
+
+            mockSerializerProvider
+                .Setup(p => p.GetODataPayloadSerializer(typeof(Customer)))
+                .Returns(mockCustomerSerializer.Object);
+            mockWriter
+                .Setup(m => m.WriteStart(It.IsAny<ODataFeed>()))
+                .Callback((ODataFeed feed) =>
+                {
+                    Assert.Equal(expectedNextLink, feed.NextPageLink);
+                });
+            _serializer = new ODataFeedSerializer(_customersType, mockSerializerProvider.Object);
+
+            _serializer.WriteObjectInline(_customers, mockWriter.Object, _writeContext);
+        }
     }
 }
diff --git a/test/System.Web.Http.OData.Test/OData/Query/ODataQueryOptionTest.cs b/test/System.Web.Http.OData.Test/OData/Query/ODataQueryOptionTest.cs
index 883c98e0..a0041358 100644
--- a/test/System.Web.Http.OData.Test/OData/Query/ODataQueryOptionTest.cs
+++ b/test/System.Web.Http.OData.Test/OData/Query/ODataQueryOptionTest.cs
@@ -650,6 +650,45 @@ namespace System.Web.Http.OData.Query
             // Arrange & Act & Assert
             Assert.False(ODataQueryOptions.IsSupported("$invalidqueryname"));
         }
+
+        [Theory]
+        [InlineData(1, true)]
+        [InlineData(2, true)]
+        [InlineData(4, false)]
+        [InlineData(8, false)]
+        public void LimitResults_LimitsResults(int limit, bool resultsLimitedExpected)
+        {
+            IQueryable<Customer> queryable = new List<Customer>() {
+                new Customer() { CustomerId = 0 }, 
+                new Customer() { CustomerId = 1 },
+                new Customer() { CustomerId = 2 },
+                new Customer() { CustomerId = 3 }
+            }.AsQueryable();
+            var model = new ODataModelBuilder().Add_Customer_EntityType().Add_Customers_EntitySet().GetEdmModel();
+            var context = new ODataQueryContext(model, typeof(Customer), "Customers");
+
+            bool resultsLimited;
+            IQueryable<Customer> result = ODataQueryOptions.LimitResults(queryable, limit, out resultsLimited);
+
+            Assert.Equal(Math.Min(limit, 4), result.Count());
+            Assert.Equal(resultsLimitedExpected, resultsLimited);
+        }
+
+        [Theory]
+        [InlineData("http://localhost/Customers", 10, "http://localhost/Customers?$skip=10")]
+        [InlineData("http://localhost/Customers?$filter=Name eq 'Steve'", 10, "http://localhost/Customers?$filter=Name eq 'Steve'&$skip=10")]
+        [InlineData("http://localhost/Customers?$top=20", 10, "http://localhost/Customers?$top=10&$skip=10")]
+        [InlineData("http://localhost/Customers?$skip=5&$top=10", 2, "http://localhost/Customers?$top=8&$skip=7")]
+        [InlineData("http://localhost/Customers?$filter=Name eq 'Steve'&$orderby=Age&$top=11&$skip=6", 10, "http://localhost/Customers?$filter=Name eq 'Steve'&$orderby=Age&$top=1&$skip=16")]
+        [InlineData("http://localhost/Customers?testkey%23%2B%3D%3F%26=testvalue%23%2B%3D%3F%26", 10, "http://localhost/Customers?testkey%23%2B%3D%3F%26=testvalue%23%2B%3D%3F%26&$skip=10")]
+        public void GetNextPageLink_GetsNextPageLink(string requestUri, int resultLimit, string nextPageUri)
+        {
+            HttpRequestMessage request = new HttpRequestMessage(HttpMethod.Get, requestUri);
+
+            Uri nextPageLink = ODataQueryOptions.GetNextPageLink(request, resultLimit);
+
+            Assert.Equal(nextPageUri, nextPageLink.ToString());
+        }
     }
 
     public class ODataQueryOptionTest_ComplexModel