Happy Families - Project Nesting

2024-04-28 by Pere Lev

As always, my task board is available. I use the Vikunja app to track my work, it's not a static page and requires JS. And sometimes can be a bit buggy and needs a reload.

You know what? Let me just show you.

Tracking my work on project nesting on Vikunja

Nesting

I haven't used GitLab lately, and I don't use GitHub (other than for examining its UI). But unless some huge change happened, that I missed, the following features are probably still there:

On GitLab, projects can be nested, a bit like a folder tree
On GitHub, there's the "organization" concept, which can gather multiple projects and their access rules in one place

One of the federated tools ForgeFed provides, to allow projects to remain organized and efficient as they grow, and to make the familiar nesting available to forges that want to implement federation, is project nesting.

A project, in the ForgeFed sense, is a set of software development tools, called components. The 3 fundamental components ForgeFed currently describes are Repository (for storing code), Ticket Tracker (for opening issues) and Patch Tracker (for opening PRs).

Speaking of components - if you could choose the 4th component ForgeFed will support, what would you choose? Wiki, releases, CI, kanban board... I suppose it would be one of those? I wonder which one would have the most impact! Let me know on the Fediverse? :-) I think right now my tendency is towards CI (it might be the most difficult to implement, but also an extremely useful and common tool projects use, including ForgeFed itself, whose website (this website you're looking at right now) is deployed using Codeberg's CI).

Thanks to federation, project nesting is quite flexible:

Project A can become a parent of another project B
A and B can reside on different servers, and it just works
A project can have more than one parent!
In other words, it's not a folder tree, but more like a directed graph
There's a mechanism for preventing cycles, don't worry (but if you feel like testing it, see below for live demo links!)

I'm really curious if this flexibility can, when the time comes, support a global decentralized network of forges, where projects can belong to multiple contexts simultanously, and where federated access control and collaboration are done really smoothly.

Nesting and Access Control

Like on GitLab and GitHub, gathering projects together under higher-level projects isn't just for visual convenience, it's also a powerful tool for managing access control. If Alice obtains access to a project CoolApp, she now automatically gains access to all the components of CoolApp, and to the child projects of CoolApp, and to their own components and child projects, and so on.

So, when people or teams are given responsibility on a certain group of projects, an easy way to manage access is to put those projects under one big parent project, and assign access through this parent project.

How does this automatic nested access control work?

Like almost everything around here, it uses ForgeFed's federated Object Capability system! Here's an example:

I create a project A
I now receive a Grant activity, giving me access to A
I create a project B
I now receive a Grant activity, giving me access to B
I make project B a child of project A
Project B now passes a special Grant activity to A, and A passes it to me

Now I have 2 authorization paths for manipulating project B:

The Grant that B gave me directly when I created it
The Grant-for-access-B that B passed to A, and A passed to me because of my access to A

Is this confusing already? The story continues:

I now create a ticket tracker TT
I now receive a Grant activity, giving me access to TT
I now add TT to be a component of project B

What happens now?

TT passes a Grant to B
B extends it to me, due to my direct access to B
B also extends it to A, its parent project
A further extends it to me, due to my direct access to A

I now have 3 Grants for accessing TT!

The direct one I got when I just created TT
The one I got through B
The one I got through A

It's now possible to remove me from having direct access to B and to TT, and I'll still be able to manipulate them, because project A is extending me access-to-them.

Here's my (somewhat cryptic) project overview on the grape demo instance. The items on the list are projects I have access to, and the sublists represent Grants that these projects have extended to me.

Items starting with $ are projects. Items starting with = are ticket trackers.

Example of projects and Grants extended through them

Another way to observe my Grants is to browse to some resource, such as a ticket tracker or project or team, and if I have any Grants to access it, a "My access" section will appear, like this:

Example of my access to a ticket tracker

So we're looking at this ticket tracker TTT, to which I have both direct access (which in this case I got when I created it), and I have another Grant that I received via some project CCC, because TTT is a component of CCC and I'm a direct collaborator in CCC.

What's special about both views above is that their data is tracked by the Person actor, not by the projects. It really makes things more convenient, especially as more and more pieces are implemented and the system is getting complex. Obviously this whole UI is just PoC-level (while we're working on an actual frontend application). But I hope you'll see in the demo, how much easier it makes things. Compared to the bare-bones forms and JSON objects I've been playing with until now, this is a major convenience upgrade :P

I implemented those UIs primarily in the following commits:

Nesting implementation

By far the most complicated part of the implementation is the actual logic, i.e. the Server-to-server (S2S) activity handlers that implement the activity sequences that create and remove the links between children and parents. The child-parent link, perhaps like in real life, is the most complex piece of the OCAP system that I've implemented so far.

Here's the update to the specification, which describes both linking and unlinking of parents and children, both for projects and for teams:

Spec: Describe adding/removing parents/children to/from teams and projects

The process of forming a child-parent link involves several activity types: Add, Accept and Grant. And there are 4 different modes:

Child-active: I'm getting a new child, and I'm initiating the process, waiting for the child to approve
Child-passive: I'm getting a new child, but the child is the one initiating, now waiting for me to approve
Parent-active: I'm getting a new parent, and I'm initiating the process, waiting for the parent to approve
Parent-passive: I'm getting a new parent, but the parent is the one initiating, now waiting for me to approve

If I'm in child-active mode, then the child is in parent-passive. And if I'm in child-passive mode, then the child is in parent-active. So these modes must really dance together. Commits:

It was a huge piece of work! But it's just the logic, without UI around it, so it was still invisible.

Loop prevention

What if:

Project A becomes a parent of project B
Project B becomes a parent of project C
Project C now becomes a parent of project... A?

Actually, the circular relationship itself isn't the problem. The problem is that once it is formed, these project would start to send and extend Grants. And if they aren't careful, they might end up extendind and extending the same Grant chain infinitely, getting their CPUs and DBs and network connections busy with this empty work. Also known as an accidental (or intentional) DDOS attack. How to prevent this?

My first naive thought was: If I'm a project and about to add a child/parent, What if I loop over the children/parents, and recursively their own children/parents, to make sure I don't find myself somewhere in there? If I do, it's a sign I can't add the child/parent, overwise I'd create a circular situation. Thoughts?

This might work, but:

It's very wasteful because of how it fans out, and can very quickly end up having to traverse tons of projects
It's not really effective at preventine a DDOS attack, because regardless of who a project claims its children and parents are, it might make entirely different choices where to extend the Grant chains
In other words, the chain is what matters here, not the public data of the parent-child links (i.e. a malicious of buggy project's talk and walk might differ)

So I went for a different approach, using the Grant chain itself:

When I'm about to extend a chain, traverse the chain back to the beginning, making sure I don't appear there

Since the chain is a list, there's no fanning out! In computer science speak, while the naive approach was O(n), the new one is O(log n), where n is the amount of projects in the project graph.

But naively traversing the chain also creates a risk of DDOS: What if a malicious (or buggy) project sends me a really, really long chain? Like, with a million items?

The chain length corresponds to the number of Project nesting levels. While theoretically it's arbitary, in practice even the biggest projects probably need just a few levels of nesting. I expect that 4 is really enough for nearly all projects, even the bigger ones. But perhaps really big projects need a bit more. Since the numbers are so small, why don't we give them a comfortable margin, just in case?

So, I added a new settings in the Vervis settings file: The maximal depth that a Grant chain is allowed to have. A chain bigger than this is immediately considered invalid. I set the default limit to 16, which is also what the 3 demo instances are using. But even if it was 100, which is probably more than anyone out there ever needs, it's still way way less than a million.

So, this is the mechanism that prevents loops:

Traverse the chain before extending
Verify the length is below the maximum (default is 16)
Verify none of the Grants in the chain is mine

Commits:

Basic UI

So far, all of this is logic behind the scenes. I started adding the most basic UI, forms that require copying and pasting URIs. I always add them anyway, because I need them for flexibly testing federated interactions, but I usually add the nice buttons first. This time, I started with the forms, so that the behind-the-scenes mechanisms are visible, before I cover them with more convenient UI.

I also added UI for viewing parents and children of a project.

Viewing per project:

A project's children list, listing 2 children

Viewing projects on an instance:

Example of project nesting

Adding a child-parent link:

Empty form for adding a child project

I tested my implementation using this UI, both local and federated. Copying and pasting URIs is of course quite annoying, but it allows to see how things work behind the scenes. See video demo below.

Link removal

Since Vervis has been mostly in PoC stage, and since the code evolves very quickly and it's nice to have flexibility, and since I'm me, so far I've mostly focused on code that creates stuff, and much less on code that deletes stuff. I think I never properly implemented things like deleting a user account, or deleting a ticket tracker. I mean, I did at some point, but then big changes to the code broke those features, and it was really difficult to maintain them, especially considering the low priority.

But now that the Anvil frontend is on its way, and Vervis is getting more and more core features implemented, I really hope to catch up and make it possible to delete things properly, as well as edit, and at some point also freely and easily migrate data between servers (for which I hope to use the F3 specification, on which my Forge Federation colleagues Earl Warren and Loic Dachary have been working for some time now, and I'm excited to integrate with that).

The child-parent link removal process was much easier to implement than the link creation process, but it simiarly involves multiple types of activities: Remove, Accept, Revoke.

Commits that implement the logic:

And UI, a form similar to the ones above:

UI: Removal form: Extend to work on children/parents as well

More convenient UI

With all those pieces in place, I really wanted to feel the ease of just clicking stuff without having to manually choose which Grant activity to use for authorization, and pasting around all these URIs.

What if I browse to project A, and there's a little box where I just paste the URI of project B (since there's no JS-powered search yet, that's the minimum to paste) and click "Add"? And then the other side approves the child-parent link using a button, without any pasting? And what if parent/child removal is a single button click too?

So, I decided to implement these things:

Adding a child:

Adding a child project by URI

Now the project displays the invited child:

Child invite

If we browse to the child's parents page, we can see the invite there too, and since I have admin access to the child, there's an Approve button:

Same invite, from the child's perspective

Voila! The child-parent link is now enabled, and there's a Remove button to disable it:

Child is now enabled

Funding

I really want to thank NLnet for funding this work, and much more to come! My grant (which just expired) is going to be extended, and André's work on the Anvil frontend is going to be funded too.

See It in Action

I recorded a little demo of all this! Watch it on my PeerTube instance.

If you want to play with things yourself, you can create account(s) on the demo instances - fig, grape, walnut - and try the things I've mentioned and done in the video.

If you encounter any bugs, let me know! Or open an issue

Comments

Come chat with us on Matrix!

And we have an account for ForgeFed on the Fediverse: https://floss.social/@forgefed

Right after publishing this post, I'll make a toot there to announce the post, and you can comment there :)