Library Approach

[donopj2]

Hey guys, I'm definitely keen to jump in. This is my first foray into OSS, so apologies for any faux pas. I had a look at the project setup that @tlycken put together, and have been giving some thought to the algorithms and task list @forki laid out. I've also been playing around with FSC and reading through the docs, but its new to me (eager to learn though!). I guess my question is, what is the best approach to start? A few thoughts:

• Having looked through the FSC docs, it appears most of the API's require passing different files (.fs, .fsproj, etc), depending on the service. I was thinking the Project Analysis service could be quite useful. It seems to have rich functionality for compiling a full project and exploring errors and symbols.
• To that end it appears we will need a set of utilities like the Utils.fs file in the Paket project to walk the source code directory and build data structures for each project and its contents. This might be a good module to start on?
• As a starting point for the algorithm outline a FSharpCheckProjectResults with an empty Errors array would indicate a correctly ordered project and thus no action. Easy enough ;)

Naturally determining an incorrectly ordered project and finding a correct order will be a bit more involved. I'll continue to explore the FSC APIs and try to devise an approach while working on a files module. Perhaps we could also post thoughts in this thread as they come together that will hopefully serve to flesh out the requirements more broadly?

If this all sounds reasonable I'll crack on, but please do let me know if I'm off base.

[forki]

I think we should start with the following:

1. find an FCS API that allows us to give it a list with .fs files and it should return if the order is valid. we can even start with just creating a temporary fsproj (copy of original fsproj) and call fsc.exe if we don't know where to start
2. Create an algorithm that tries all permutations of the files and filters the permutations by 1)
3. The algorithm in 2) will be used as baseline in tests so that we can always very that better heuristics are still valid
4. Try to find better (= faster) FCS API to improve 1) - I assume we will only need the FCS do NameResolution. I'm not sure if there is already an API that stops after that phase (ping @Krzysztof-Cieslak) - if not then we might PR that into FCS eventually
5. Try to improve the 2) by adding heuristics or graph knowledge

Anyway: I think we should start with the brute force to have some proof of concept. I just merged @tlycken's build infrastructure PR, so please go ahead and try to do something to get us started.

And btw: welcome aboard!

[AnthonyLloyd]

Just poking my nose in...
I think for 2) you could just try one file first until it compiles then add second etc. Its O(n^2) vs O(n!)

[forki]

Good point. Am 03.01.2018 23:09 schrieb "Anthony Lloyd" <[email protected]>: Just poking my nose in... I think for 2) you could just try one file first until it compiles then add second etc. Its O(n^2) vs O(n!) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#10 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AADgNBImktUY_pCzVFiDukk_o8QIhTWNks5tG_qEgaJpZM4RRIRB> .

[jindraivanek]

I volunteer in graph knowledge area :)

If we have all symbols declared and used in all files, then we can create directed graph where A -> B means that file B uses symbol that is declared in file A. Then ordering is question of finding topological sort of graph, which is O(n^2) https://en.wikipedia.org/wiki/Topological_sorting. This alg return valid order or subset of files where is dependency cycle. I think it can be easily altered to respect previous order as much as possible.

I would happily try to implement this. I did some experimenting with getting symbols from FCS with GetAllUsesOfAllSymbolsInFile yesterday, with some success (https://github.com/jindraivanek/AProjectHasNoName/blob/symbol-graph/src/FSharp.Project.FileOrderer/Library.fs), but not sure if that is correct way.

[forki]

Cool. Tbh I have no idea if it will turn out to be the correct way. But it sounds promising Am 04.01.2018 08:22 schrieb "jindraivanek" <[email protected]>:

…

I volunteer in graph knowledge area :) If we have all symbols declared and used in all files, then we can create directed graph where A -> B means that file B uses symbol that is declared in file A. Then ordering is question of finding topological sort of graph, which is O(n^2) https://en.wikipedia.org/wiki/Topological_sorting. This alg return valid order or subset of files where is dependency cycle. I think it can be easily altered to respect previous order as much as possible. I would happily try to implement this. I did some experimenting with getting symbols from FCS with GetAllUsesOfAllSymbolsInFile yesterday, with some success (https://github.com/jindraivanek/ AProjectHasNoName/blob/symbol-graph/src/FSharp.Project. FileOrderer/Library.fs), but not sure if that is correct way. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#10 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AADgNNvE-3wob0g4ofc1kOLOP7IPqhSeks5tHHwfgaJpZM4RRIRB> .

[isaacabraham]

I would like to suggest that we (well, I'm not directly involved, so perhaps "you" is more accurate...) strongly consider ensuring that the algorithm is completely decoupled from the features of FCS and such. There (as far as I can see) should be nothing to stop an algorithm etc. being designed and implemented with no dependency on FCS or anything like that.

FCS -> Mechanic domain model (types like Mechanic.File of Mechanic.Type list etc. etc.) -> Mechanic resolution (new set of Mechanic Files etc.) -> FCS.

The internals can then be tested out to our hearts content without needing a "real" project etc. to do this.

[tomasaschan]

Yes, @isaacabraham's point is crucial to success here.

That also has the additional upside that someone with no knowledge at all can work on the ordering algorithm, while someone with no knowledge of how to write the ordering algorithm can write the FCS integrations.

If we decide to build on top of Forge (see #36, ionide/Forge#104), we probably need two algorithms, with some integrations at either end:

1. Use FCS to determine symbols and their dependencies, and map them to a domain language as suggested above
2. Use that domain language to figure out an order that works (algorithm part 1)
3. Compare that ordering, with the original ordering, and figure out the operations that should be carried out against the project file (also expressed in the domain language) (algorithm part 2)
4. Use Forge (or whatever else) to actually change the project file

In principle, the actual implementation of these steps can be built independently, as long as we agree on the domain language.