New Feature: DisplayOrder for IProjectTree nodes

[davkean]

The CPS and .NET Project System team got together to discuss #391, #1875 and #1224.

We came to the following agreement:

We will introduce an ordinal, DisplayOrder to the project tree nodes that represents the order in which the node is displayed in the Solution Tree. IProjectTreePropertiesProvider implementors will be able to set this value on the specified propertyValues argument. By default, CPS will also implement a IProjectTreePropertiesProvider that will set this DisplayOrder if it hasn't already been set based on a predictable order to mimic today's Solution Tree order; BubbleUp Folders -> Folder/VirtualFolder -> BubbleUp Files -> Files. We expect C#/VB to only set the DisplayOrder for special nodes, we expect F# to set them for all nodes.

This will include the following changes:

• New IProjectTreeCustomizablePropertyValues2 interface with int DisplayOrder read-write property, and implement them on appropriate types
• New IProjectTree2 interface with int DisplayOrder read-only property and implement them on appropriate types
• New IProjectTreeItem2 interface with int DisplayOrder read-write property and implementation them on appropriate types (is this required @lifengl)
• Introduce appropriate SetDisplayOrder and SetProperties methods on IProjectTree2/IProjectTreeItem2
• Change ProjectTreeSort to sort based on the DisplayOrder instead of specially handling bubble up, folders and items
• Add IProjectTreePropertiesProvider that runs after everyone to set DisplayOrder based on bubbleup, folder/virtualfolder and file if it hasn't been set
• Add a way for a IProjectTreePropertiesProvider to being able to figure the default DisplayOrder of bubble up, virtual folder, files so that they can insert items before and after them. For example, C#/VB probably wants the project file to be sorted below folders but before all files so that it's in a predictable location regardless of project name.
• Change the PhysicalProjectTree to plumb through the IProjectTreeCustomizablePropertyValues2 and IProjectTree2/IProjectTreeItem2 values

//cc @lifengl @srivatsn @jviau @adrianvmsft

[davkean]

@tannergooding We thought this would be a good meaty feature you to pick up, as it's required for #1224.

[brettfo]

This feels like it will introduce a lot of fiddling around. E.g., say a new C# file a.cs is added. It will appear near the top of the list due to it's name which means every single other item in the tree will have to be renumbered. Won't that kick off a flurry of UI updates with lots of overlap where two items (temporarily) have the same value for DisplayOrder?

[lifengl]

Minor adjustment to the work:

all properties in IProjectTree are readonly. (It is an immutable object), you need a new SetDisplayOrder(...) and an extra SetProperties overloads for the new property, which returns a new tree. An extra overload will be the only reason to define the IProjectItemTree2.

no need to IProjectTreePropertiesProvider that runs after everyone to set DisplayOrder based on bubbleup, folder/virtualfolder and file if it hasn't been set. The conversion can be built into the physical project tree provider code to call IProjectTreePropertiesProvider and covert the result into properties in the ProjectTree.

ProjectTree.TryFindImmediateChild need be changed, because it is currently using all combinations of flags to do binary search to find an item by its name. It doesn't work after switching to the DisplayOrder, and a linear search must be used. The function will change from O(log(n)) to O(n). I searched the physical project tree provider code, and think we can live with the perf impact coming with the change. This is more heavily used in the directory tree to monitor file system changes, and we don't want the perf impact there. There is no reason to support the complex sorting order in the directory tree either. We have already refactored the code to allow the directory tree to have a different sorting, and I will change the code to allow the directory tree to have a different implementation to search child item. Changing the default implementation of the FindImmediatelyChild will still be a part of the work of this feature.

[lifengl]

Also add @AArnott, if he has any concern about the new property in the project tree. Unfortunately, it will be much easier if we have the new data structure. We don't know when we may be able to change that at this point.

@brettfo: we don't expect C# project to use the DisplayOrder much, all normal file items should have the same default DisplayOrder number, and they will be sorted by names. The only place this feature is expected in C# project system is to define order between some virtual tree nodes, because the team wants an exactly order for those trees. The primary usage for the DisplayOrder is in F# project system, and we don't expect those projects to be very large. (Maintaining the order of a thousand items might be more difficult for a developer than the software.) Also, there is no reason to use the number continuously. The provider assigns numbers for files can leave large holes between numbers, and re-balance holes as needed. I will expect inserting a new item will only update the order number for 1 to 2 nodes. This will be interesting to write, but that will be completely independent to this infrastructure work.

[davkean]

@brettfo Yes just to reiterate @lifengl we expect all nodes of the same type to have same display order. For example, all bubble up folders could be 1000, all folders could be 900, all bubble up files could be 800, and so on. Those with the same order would be alphabetized.

[AArnott]

Given you will share DisplayOrder values across many nodes, the risk of having to reallocate the entire tree for a reorder event is low -- for C#. But for F#, if you insert a node into the "list", every single node either before or after it will have to be updated as well, potentially. But given the immutable nature of the object tree, that means a very large number of allocations because each individual node update will reallocate the whole spine, only to go onto the next node to be updated. In short, I think a design where a simple change to the tree forces reallocation of the entire tree many times to be a worrisome design.

I think if the goal includes supporting scenarios where the entire order must be tightly controlled (e.g. F#) then we must use an ImmutableList instead of an ImmutableHashSet to store the children of a node, thereby ensuring an efficient modification algorithm.

I'm not sure if what @lifengl was alluding to was the ImmutableObjectGraph, but I designed it to fulfill the project tree data structure requirements as well. You can see what's already supported here: https://github.com/AArnott/ImmutableObjectGraph/blob/master/src/ImmutableObjectGraph.Generation.Tests/TestSources/ProjectTree.cs. There is also a ProjectTreeWork branch with some more work in that area. It is based on ImmutableList in order to support F#. The idea included an optional IComparer so that the list could be easily sorted and efficiently searched for those project types that should be sorted, while still allowing F# to do its work as efficiently as possible.

Something to consider anyway.

[lifengl]

The new data structure is nice, but doesn't fit into 15.3 schedule, while the work is currently budgeted as one to two dev weeks. Considering the original F# project doesn't support folder structure, so all files are inside one flat list (as the project root), the depth of the spin is one. I doubt anyone can really manage a large sorted file list, so I guess most of them have a small list of files, likely below 100. The performance issue should not be a very big deal for F# projects. I also don't think we should assign order numbers continually like 1, 2, 3... but should come with large gaps like 1000, 2000, 3000, 4000... When a new file added to the beginning of the list, it becomes 700, 1400, 2000, 3000, 4000... so the majority of items keeps the current value. A large reallocation can happen, but only in a very rare case.

…

Sent from my phone On Mar 30, 2017, at 6:55 PM, Andrew Arnott <[email protected]<mailto:[email protected]>> wrote: Given you will share DisplayOrder values across many nodes, the risk of having to reallocate the entire tree for a reorder event is low -- for C#. But for F#, if you insert a node into the "list", every single node either before or after it will have to be updated as well, potentially. But given the immutable nature of the object tree, that means a very large number of allocations because each individual node update will reallocate the whole spine, only to go onto the next node to be updated. In short, I think a design where a simple change to the tree forces reallocation of the entire tree many times to be a worrisome design. I think if the goal includes supporting scenarios where the entire order must be tightly controlled (e.g. F#) then we must use an ImmutableList instead of an ImmutableHashSet to store the children of a node, thereby ensuring an efficient modification algorithm. I'm not sure if what @lifengl<https://github.com/lifengl> was alluding to was the ImmutableObjectGraph, but I designed it to fulfill the project tree data structure requirements as well. You can see what's already supported here: https://github.com/AArnott/ImmutableObjectGraph/blob/master/src/ImmutableObjectGraph.Generation.Tests/TestSources/ProjectTree.cs. There is also a ProjectTreeWork branch with some more work in that area. It is based on ImmutableList in order to support F#. The idea included an optional IComparer so that the list could be easily sorted and efficiently searched for those project types that should be sorted, while still allowing F# to do its work as efficiently as possible. Something to consider anyway. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#1896 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ALGWwvmC06kZrOUz83WCSI99FqykACTkks5rrF0igaJpZM4MtvHZ>.

[AArnott]

Writing the code to space out the numbers like that: easy. Writing and testing and debugging the code that handles the corner cases when you run low on numbers between other numbers: IMO probably quite hard. I would recommend numbering them all consecutively if for no other reason than to just make sure you code isn't hiding corner cases that it fails at.
That said, your suggestion about the size of F# projects would largely mitigate the concern if it's true.

[lifengl]

I agree. We don't need get into the extra complexity until the performance becomes an issue. One concern is the temporarily duplicated numbers causing the temporarily reordering between neighbors. The spine of the children collection does get extra updates.

…

Sent from my phone On Mar 30, 2017, at 10:37 PM, Andrew Arnott <[email protected]<mailto:[email protected]>> wrote: Writing the code to space out the numbers like that: easy. Writing and testing and debugging the code that handles the corner cases when you run low on numbers between other numbers: IMO probably quite hard. I would recommend numbering them all consecutively if for no other reason than to just make sure you code isn't hiding corner cases that it fails at. That said, your suggestion about the size of F# projects would largely mitigate the concern if it's true. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#1896 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ALGWwqGSJw3s5IWpIV783MzbfUs6e1jNks5rrJEPgaJpZM4MtvHZ>.

[adrianvmsft]

Alternatively, we could use floating point values for order. This way we will never run out of interim numbers.
If you want to insert between 1 and 2 we could use 1.5. If you want to insert between 1.5 and 2 you can use 1.75, and so on.

[brettfo]

If the tree is readonly/immutable and the UI update only happens when the entire tree is replaced, then integer IDs should be fine, and as mentioned above, even re-generating an entire tree of 1000 source files really doesn't take that long.

[AArnott]

we could use floating point values for order. This way we will never run out of interim numbers.

Two potential issues with that:

1. floating point numbers are much slower than integers in the CPU. So sorting might actually take much longer. I'm not sure at the scale we're talking about it would make any difference -- probably not.
2. floating point has a limited resolution and has rounding errors without warning. So if you're trying to fit between 1.2125125 and 1.2125124, you can do the math to get something between that, but then when it is cast to a single or double you end up with the same as one of the existing numbers. So you can actually run out of numbers.

even re-generating an entire tree of 1000 source files really doesn't take that long.

My concern was that it could be as long as regenerating a tree 1000 times. Generating a single tree is generally pretty fast. But mutating a tree, when each mutation has to recreate the tree, would be potentially n^2, which is pretty bad. Consider, for example, if the CPS red tree reallocates all children when one child has to be realized, and that the tree has one really big folder and not much else. Then each mutation on one child has to recreate the entire tree. If you have 1000 children to update, then that's 1000 recreations of 1000 children, or one million allocations just to make an insertion into a list of 1000. Yikes.

[cloudRoutine]

Considering the original F# project doesn't support folder structure, so all files are inside one flat list (as the project root), the depth of the spin is one. I doubt anyone can really manage a large sorted file list, so I guess most of them have a small list of files, likely below 100.

@lifengl most F# projects make pretty extensive use of a combination of concrete folders that match the file path relative to the directory of the .fsproj and virtual folders containing only links to source files.

For F# folders are supported in vs2015(poorly)

and are supported in vs2017 (still poorly)

[lifengl]

Yeah, just like Andrew said, the floating number inside computer is not a continuous space, and you can easily run into those resolution holes and much harder to control that. Because the height of the balance tree is O(log(n)), I think refreshing the entire tree is O(n*log(n)). Because the entire process is in a tight loop, only the spine of it would be realized in each step (plus the next node), so the cost would be on the same scale. Of course, if we introduce lots of shuffling, it would leave a large change log.

…

Sent from my phone On Mar 31, 2017, at 12:13 PM, Andrew Arnott <[email protected]<mailto:[email protected]>> wrote: we could use floating point values for order. This way we will never run out of interim numbers. Two potential issues with that: 1. floating point numbers are much slower than integers in the CPU. So sorting might actually take much longer. I'm not sure at the scale we're talking about it would make any difference -- probably not. 2. floating point has a limited resolution and has rounding errors without warning. So if you're trying to fit between 1.2125125 and 1.2125124, you can do the math to get something between that, but then when it is cast to a single or double you end up with the same as one of the existing numbers. So you can actually run out of numbers. even re-generating an entire tree of 1000 source files really doesn't take that long. My concern was that it could be as long as regenerating a tree 1000 times. Generating a single tree is generally pretty fast. But mutating a tree, when each mutation has to recreate the tree, would be potentially n^2, which is pretty bad. Consider, for example, if the CPS red tree reallocates all children when one child has to be realized, and that the tree has one really big folder and not much else. Then each mutation on one child has to recreate the entire tree. If you have 1000 children to update, then that's 1000 recreations of 1000 children, or one million allocations just to make an insertion into a list of 1000. Yikes. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#1896 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ALGWwh2xlRjTGVPOF9cNvJXu8nKfytGmks5rrVA1gaJpZM4MtvHZ>.

[AArnott]

@lifengl are you confident then that the red tree does not realize all children when one child is queried for? If you were to write a loop that enumerated all children in order to shift them all down by one, are you certain it would only realize the spine at each step and not all the children as well?

[lifengl]

Yeah, the red tree is lazily created. The typical process for this code is that the code enumerates through the original tree (where the entire tree will be realized and find the same node in the current tree to update it, and then goes to the next node.) If change happens in each step, the temporarily middle tree should have two leave nodes. One clear overhead of the red tree is in this FindById process. It finds the green node through a lookup table and then maps it to the red tree. The mapping requires to get the index of green nodes of the spine on each level to look at the children array of the red tree. This IndexOf thing is expensive because it requires O(log(n)) culture related string comparisons. For a large project, when some code enumerates the entire tree with vs hierarchy API, this process is repeated for each item and turns out to be expensive. This is less issue for the F#, because of less string comparisons.

…

Sent from my phone On Mar 31, 2017, at 9:52 PM, Andrew Arnott <[email protected]<mailto:[email protected]>> wrote: @lifengl<https://github.com/lifengl> are you confident then that the red tree does not realize all children when one child is queried for? If you were to write a loop that enumerated all children in order to shift them all down by one, are you certain it would only realize the spine at each step and not all the children as well? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#1896 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ALGWwgl14-HoTw26nzDvduMiUbFy2a3Iks5rrdfzgaJpZM4MtvHZ>.

[tannergooding]

The work required to support projects with a small number of files was done to support F#. The remaining work here is blocked pending a CPS refactoring.

We should probably move this out of 15.5. @Pilchie, @davkean

[lifengl]

I think the work is finished and we should close it. As we discussed, F# project typically has no more than 20 files, so perf is not a major concern for now. For the future, I remember the F# team wants dual view in the solution explorer. One folder view would work just like other projects, and another flattened ordered compile items view. We need discuss that in a future release.

…

Sent from my phone On Sep 12, 2017, at 12:40 PM, Tanner Gooding <[email protected]<mailto:[email protected]>> wrote: The work required to support projects with a small number of files was done to support F#. The remaining work here is blocked pending a CPS refactoring. We should probably move this out of 15.5. @Pilchie<https://github.com/pilchie>, @davkean<https://github.com/davkean> — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<#1896 (comment)>, or mute the thread<https://github.com/notifications/unsubscribe-auth/ALGWwrdsO90wtar6WaxO399owLX_VJvsks5sht4_gaJpZM4MtvHZ>.

[davkean]

I'd like to control the order of bubble up folders, can I do that?

[aodl]

I see that DisplayOrder can currently be set on CoreProjectTreeProviderBases factory methods for IProjectItemTree2, and in a bunch of other ways such as directly on ReferencesProjectTreeCustomizablePropertyValues, or via a properties provider like this. Despite having tried this, the DisplayOrder that I've set for my tree nodes doesn't seem to have any affect on how Visual Studio orders them. Is that because this issue hasn't been completed yet, or should this work (meaning I'm probably missing something)?

[davkean]

The general feature is not finished. To opt into what F# are using you need to use the "SortByDisplayOrder" capability. Be warned, the current design doesn't scale to large projects - its designed very specifically for F#-sized projects.

[lifengl]

One option is to turn it on on the folder level, so you can use it on the root folder. As long as you don’t have huge numbers of files there. The perf hit will be limited, and it will be enough for you virtual node issue. We don’t support that, but it is relatively cheap to do.

…

Sent from my phone On Jun 18, 2019, at 9:12 PM, David Kean <[email protected]<mailto:[email protected]>> wrote: The general feature is not finished. To opt into what F# are using you need to use the "SortByDisplayOrder" capability. Be warned, the current design doesn't scale to large projects - its designed very specifically for F#-sized projects. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub<https://eur04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fdotnet%2Fproject-system%2Fissues%2F1896%3Femail_source%3Dnotifications%26email_token%3DACYZNQXGSWSWBBP4S2XHYVTP3GW2LA5CNFSM4DFW6HM2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODYAUBPY%23issuecomment-503398591&data=02%7C01%7C%7C5f636879f7a44becb67008d6f46c53c7%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636965143425710399&sdata=8O6RjHqVZPaaeh%2Fi5eXX%2F%2FA%2BR6CNWMYPlGklW8sesGg%3D&reserved=0>, or mute the thread<https://eur04.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fnotifications%2Funsubscribe-auth%2FACYZNQWLKBPZWG6XEOEQHFLP3GW2LANCNFSM4DFW6HMQ&data=02%7C01%7C%7C5f636879f7a44becb67008d6f46c53c7%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636965143425720407&sdata=kJjoZCuEVKzIz2oFC9AAM4PlJyWJDHMpfxyE4Z1eyZE%3D&reserved=0>.

[aodl]

Okay, thanks. Out of interest, what is it about F# projects that mitigates performance issues with DisplayOrder? It would be nice to be able to specify a SortByDisplayOrder ProjectTreeFlag (at the tree level instead of folder level, as the tree might not be based on file system folders), instead of opting in for all the trees in the project.

[aodl]

Great, adding SortByDisplayOrder capability to the project causes the nodes to take order I've set for DisplayOrder. However I've noticed this also provides 'Move Up', 'Move Down', 'Add Above', 'Add below' commands when right-clicking on project items. These commands seem to work only in F# projects, although the commands are visible in C# projects that have been assigned the SortByDisplayOrder capability. Is there some additional flag/switch/capability or something that I need to specify so that these commands work?

[davkean]

Do you want the commands to work or disable? It sounds like we have a bug here, can you file a new issue and describe the behavior?

[aodl]

I didn't expect to see the commands (I was intending on implementing something similar myself). Rather than disabling them for C# projects, it would be great if they could just work. The command definitions are decorated with this attribute (MoveDown command example):
[ProjectCommand(CommandGroup.FSharpProject, FSharpProjectCommandId.MoveDown)]
As the FSharpProject project type is explicitly mentioned here, I guess the commands weren't intended for C# projects (even those given SortByDisplayOrder capability)? However the commands are displayed in C# projects. It would be great if they could stay, and just be made project type agnostic (only concerned with project capability).

[aodl]

I eventually realised that the issue was down to None items being declared as globs in an imported targets file, rather than directly in the csproj file itself. It makes sense that these couldn't be reordered, so not really a bug (I've updated the issue that I raised).

---

On a different note, @davkean would it be possible to pick your brain a little bit about how IProjectTreePropertiesProviderDataSource should be used. I can't find any code examples that are importing and using it. My main question is why TreeItemOrderPropertyProvider isn't being exported as an IProjectTreePropertiesProvider? It appears that you can only access it (given that it's internal) by importing IProjectTreePropertiesProviderDataSource, but I don't really understand what this is or how to use it correctly.

I expected to be able to enumerate all of the imported IProjectTreePropertiesProviders, call CalculatePropertyValues, and then use the resulting values.DisplayOrder for establishing the order for my tree nodes, but TreeItemOrderPropertyProvider isn't contained in the imported IProjectTreePropertiesProvider list.

[davkean]

We're done with display ordering and do not plan to do anymore around this, the last change was to have ProjectTreeProviderBase provide the ability to opt in project tree providers into specific ordering, which we're making use of in the new (MSBuild) imports tree.