Prefix finding issue with FormValueProvider

[Jonno12345]

This one was a very, very painful edge case, which I will solve in the mean time by changing some of our input field names. I appreciate it might cover such a tiny amount of specific cases, but I thought I should raise it all the same in case anyone else suffers my fate in the future.

TL;dr - The prefix binary sort does not handle the case of landing on an item with the same prefix name but followed by a hyphen, when the next half of the list contains a field with the prefix at the start of the name followed by an alphanumeric character.

The issue:

We have a page which posts back a variable amount of data, and unfortunately the naming conventions over time have lost their consistency. Additionally, the form is highly dynamic, and between submissions may have more or less form values returned. The following is a simpler abstraction of the form value keys we are talking about, and an example of the failure.

Address
Company
Delta
Name-Test-1
Name.First
NameAtBirth
Yankee
Zulu

As you would imagine, the viewmodel in use would consist of mostly simple properties, with one complex property called "Name" with a class containing a property of "First". This is a very very simplified example, and of course our data structures are much more sprawling than this, this is just the minimum I can think of that spawns the issue.

The problem comes when trying to run ContainsPrefix across the FormValueProvider. We receive every field, and it's all available in the request inputstream, however the Name property didn't get mapped at all, for no obvious reason. Even more confusing was, when adding more fields into the request, suddenly it mapped perfectly again.

Upon digging through the source, it appears to be an issue with the binary sorting being performed. Initially, the sort tries to look at the middle value of the list, against the prefix it's looking for. As such, the first search is performed against "Name-Test-1" and we're looking for a prefix of Name. We match 'Name', however, we are then checking the proceeding char matches against '.' or '['. It does not. As we're binary searching for 'Name', we then look before it for anything matching name, which of course does not exist in the above sorted example.

After this, another search is performed, this time for "Name[". The same is performed, we find "Name-Test-1", and determine it is not a match proceeded with a '.' or '['. Because we're now looking for "Name[", we correctly look at the second half of the list.

This is where the problem arises. The next result picked up by the binary search is "NameAtBirth". This is not a match followed by '.' or '[', so we need to look for the next. But unfortunately, in this search, 'Name[' is considered to come later than 'NameAtBirth'. As such, we now search the second half of the second list, and completely miss the entire section of 'Name.' which would be an instant match. Instead, we make no match at all and return, told that the prefix does not exist, and as such, we the property is not populated.

I appreciate this bug requires a 'perfect storm' of fields to occur, however the bug itself was a very confusing one for us.

I haven't considered the full ramifications of the change and all it's possible permutations, however, '.' comes earlier in the ascii table than '[' and crucially before alphanumeric characters. I can see in fact there are some comments around this currently, here System.Web.Mvc\Common\PrefixContainer.cs : 44

// If there's something in the search boundary that starts with the same name
                // as the collection prefix that we're trying to find, the binary search would actually fail.
                // For example, let's say we have foo.a, foo.bE and foo.b[0]. Calling Array.BinarySearch
                // will fail to find foo.b because it will land on foo.bE, then look at foo.a and finally
                // failing to find the prefix which is actually present in the container (foo.b[0]).
                // Here we're doing another pass looking specifically for collection prefix.
                containsPrefix = Array.BinarySearch(_sortedValues, prefix + "[", prefixComparer) > -1;

The primary solution I can think to resolve this would be a third binary search, explicitly on prefix + ".", however this could of course add some additional performance overhead in the cases where the prefix doesn't exist. I initially thought that it could be handled by replacing "[" with ".", however this would then break the above example I believe.

Please let me know if you would like any further information.

[mkArtakMSFT]

Thanks for contacting us.
If you have a proposal for a quick fix, we will consider a PR. Otherwise, we would park this in the backlog as not many customers have faced this so this doesn't meet the bar to be patched.