diff options
Diffstat (limited to 'doc/design')
| -rw-r--r-- | doc/design/architecture.md | 149 | ||||
| -rw-r--r-- | doc/design/bridges/jira.md | 379 | ||||
| -rw-r--r-- | doc/design/cli-convention.md | 13 | ||||
| -rw-r--r-- | doc/design/data-model.md | 215 |
4 files changed, 756 insertions, 0 deletions
diff --git a/doc/design/architecture.md b/doc/design/architecture.md new file mode 100644 index 000000000..b63c149d6 --- /dev/null +++ b/doc/design/architecture.md @@ -0,0 +1,149 @@ +# Internal architecture + +This documentation only provides a bird's-eye view of git-bug's internals. For +more details, you should read the other documentation and the various +comment/documentation scattered in the codebase. + +## Overview + +``` + .--------------. + | | webui | | + | '--------------' | + | .---------------..-----------..------------..--------------. | + | | commands || bridge || termui || graphql | | + | '---------------''-----------''------------''--------------' | + | .----------------------------------------------------------. | + | | cache | | + | |----------------------------------------------------------| | + | | BugCache,BugExcerpt,IdentityCache,IdentityExcerpt | | + | '----------------------------------------------------------' | + | .-----------------------------..---------------------------. | + | | bug || identity | | + | |-----------------------------||---------------------------| | + | | Bug,Operation,Snapshot || Identity,Version | | + | '-----------------------------''---------------------------' | + | .----------------------------------------------------------. | + v | repository | v + '----------------------------------------------------------' +``` + +Here is the internal architecture of git-bug. As you can see, it's a layered +architecture. + +As a general rule of thumb, each layer uses the directly underlying layer to +access and interact with the data. As an example, the `commands` package will +not directly use the `bug` or `repository` package. It will request the data +from the `cache` layer and go from there. Of course, the `commands` package will +ultimately use types defined in the lower level package like `Bug`, but +retrieving and changing the data has to go through the `cache` layer to ensure +that bugs are properly deduplicated in memory. + +## repository + +The package `repository` implement the interaction with the git repository on +disk. + +A series of interfaces (`RepoCommon`, `Repo` and `ClockedRepo`) define +convenient for our usage access and manipulation methods for the data stored in +git. + +Those interfaces are implemented by `GitRepo` as well as a mock for testing. + +## identity + +The package `entities/identity` contains the identity data model and the related +low-level functions. + +In particular, this package contains: + +- `Identity`, the fully-featured identity, holding a series of `Version` stored + in its dedicated structure in git +- `Bare`, the simple legacy identity, stored directly in a bug `Operation` + +## bug + +The package `entities/bug` contains the bug data model and the related low-level +functions. + +In particular, this package contains: + +- `Operation`, the interface to fulfill for an edit operation of a Bug +- `OpBase`, implementing the common code for all operations +- `OperationPack`, an array of `Operation` +- `Bug`, holding all the data of a bug +- `OperationIterator`, allowing to easily iterate over the operation of a bug +- all the existing operations (Create, AddComment, SetTitle ...) +- `Snapshot`, holding a compiled version of a bug + +## cache + +The package `cache` implements a caching layer on top of the low-level `bug` and +`identity`package to provide efficient querying, filtering, sorting. + +This cache main function is to provide some guarantee and features for the upper +layers: + +1. After being loaded, a Bug is kept in memory in the cache, allowing for fast + access later. +2. The cache maintain in memory and on disk a pre-digested excerpt for each bug, + allowing for fast querying the whole set of bugs without having to load them + individually. +3. The cache guarantee that a single instance of a Bug is loaded at once, + avoiding loss of data that we could have with multiple copies in the same + process. +4. The same way, the cache maintain in memory a single copy of the loaded + identities. + +The cache also protect the on-disk data by locking the git repository for its +own usage, by writing a lock file. Of course, normal git operations are not +affected, only git-bug related one. + +In particular, this package contains: + +- `BugCache`, wrapping a `Bug` in a cached version in memory, maintaining + efficiently a `Snapshot` and providing a simplified API +- `BugExcerpt`, holding a small subset of data for each bug, allowing for a very + fast indexing, filtering, sorting and querying +- `IdentityCache`, wrapping an `Identity` in a cached version in memory and + providing a simplified API +- `IdentityExcerpt`, holding a small subset of data for each identity, allowing + for a very fast indexing, filtering, sorting and querying. +- `Query` and a series of `Filter` to implement the query language + +## commands + +The package `commands` contains all the CLI commands and subcommands, +implemented with the [cobra](https://github.com/spf13/cobra) library. Thanks to +this library, bash and zsh completion, manpages and markdown documentation are +automatically generated. + +## termui + +The package `termui` contains the interactive terminal user interface, +implemented with the [gocui](https://github.com/jroimartin/gocui) library. + +## graphql + +The package `graphql` implement the GraphQL API, mapping the data model and +providing read/write access from outside the process. This API is in particular +used by the webUI but could be used to implement other user interfaces or +bridges with other systems. + +## webui + +The package `webui` hold the web based user interface, implemented in both go +and javascript. + +The javascript code is compiled and packaged inside the go binary, allowing for +a single file distribution of git-bug. + +When the webUI is started from the CLI command, a localhost HTTP server is +started to serve the webUI resources (html, js, css), as well as the GraphQL +API. When the webUI is loaded in the browser, it interacts with the git-bug +process through the GraphQL API to load and edit bugs. + +## bridge + +The package `bridge` contains the various bridge implementation with other +external bug trackers. diff --git a/doc/design/bridges/jira.md b/doc/design/bridges/jira.md new file mode 100644 index 000000000..c3a7f29f1 --- /dev/null +++ b/doc/design/bridges/jira.md @@ -0,0 +1,379 @@ +# JIRA Bridge + +## Design Notes + +### One bridge = one project + +There aren't any huge technical barriers requiring this, but since git-bug lacks +a notion of "project" there is no way to know which project to export new bugs +to as issues. Also, JIRA projects are first-class immutable metadata and so we +*must* get it right on export. Therefore the bridge is configured with the `Key` +for the project it is assigned to. It will only import bugs from that project. + +### JIRA fields + +The bridge currently does nothing to import any of the JIRA fields that don't +have `git-bug` equivalents ("Assignee", "sprint", "story points", etc). +Hopefully the bridge will be able to enable synchronization of these soon. + +### Credentials + +JIRA does not support user/personal access tokens. They have experimental +3-legged oauth support but that requires an API token for the app configured by +the server administrator. The only reliable authentication mechanism then is the +username/password and session-token mechanism. We can acquire a session token +programmatically from the username/password but these are very short lived (i.e. +hours or less). As such the bridge currently requires an actual username and +password as user credentials. It supports three options: + +1. Storing both username and password in a separate file referred to by the + `git-config` (I like to use `.git/jira-credentials.json`) +2. Storing the username and password in clear-text in the git config +3. Storing the username only in the git config and asking for the password on + each `push` or `pull`. + +### Issue Creation Defaults + +When a new issues is created in JIRA there are often certain mandatory fields +that require a value or the creation is rejected. In the issue create form on +the JIRA web interface, these are annotated as "required". The `issuetype` is +always required (e.g. "bug", "story", "task", etc). The set of required metadata +is configurable (in JIRA) per `issuetype` so the set might be different between +"bug" and "story", for example. + +For now, the bridge only supports exporting issues as a single `issuetype`. If +no configuration is provided, then the default is `"id": "10001"` which is +`"story"` in the default set of issue types. + +In addition to specifying the `issuetype` of issues created on export, the +bridge will also allow you to specify a constant global set of default values +for any additional required fields. See the configuration section below for the +syntax. + +For longer term goals, see the section below on workflow validation + +### Assign git-bug id to field during issue creation + +JIRA allows for the inclusion of custom "fields" in all of their issues. The +JIRA bridge will store the JIRA issue "id" for any bugs which are synchronized +to JIRA, but it can also assign to a custom JIRA `field` the `git-bug` id. This +way the `git-bug` id can be displayed in the JIRA web interface and certain +integration activities become easier. + +See the configuration section below on how to specify the custom field where the +JIRA bridge should write this information. + +### Workflows and Transitions + +JIRA issue states are subject to customizable "workflows" (project managers +apparently validate themselves by introducing developer friction). In general, +issues can only transition from one state to another if there is an edge between +them in the state graph (a.k.a. "workflow"). JIRA calls these edges +"transitions". Furthermore, each transition may include a set of mandatory +fields which must be set in order for the transition to succeed. For example the +transition of `"status"` from `"In Progress"` to `"Closed"` might required a +`"resolution"` (i.e. `"Fixed"` or `"Working as intended"`). + +Dealing with complex workflows is going to be challenging. Some long-term +aspirations are described in the section below on "Workflow Validation". +Currently the JIRA bridge isn't very smart about transitions though, so you'll +need to tell it what you want it to do when importing and exporting a state +change (i.e. to "close" or "open" a bug). Currently the bridge accepts +configuration options which map the two `git-bug` statuses ("open", "closed") to +two JIRA statuses. On import, the JIRA status is mapped to a `git-bug` status +(if a mapping exists) and the `git-bug` status is assigned. On export, the +`git-bug` status is mapped to a JIRA status and if a mapping exists the bridge +will query the list of available transitions for the issue. If a transition +exists to the desired state the bridge will attempt to execute the transition. +It does not currently support assigning any fields during the transition so if +any fields are required the transition will fail during export and the status +will be out of sync. + +### JIRA Changelog + +Some operations on JIRA issues are visible in a timeline view known as the +`changelog`. The JIRA cloud product provides an +`/issue/{issueIdOrKey}/changelog` endpoint which provides a paginated view but +the JIRA server product does not. The changelog is visible by querying the issue +with the `expand=changelog` query parameter. Unfortunately in this case the +entire changelog is provided without paging. + +Each changelog entry is identified with a unique string `id`, but within a +single changelog entry is a list of multiple fields that are modified. In other +words a single "event" might atomically change multiple fields. As an example, +when an issue is closed the `"status"` might change to `"closed"` and the +`"resolution"` might change to `"fixed'`. + +When a changelog entry is imported by the JIRA bridge, each individual field +that was changed is treated as a separate `git-bug` operation. In other words a +single JIRA change event might create more than one `git-bug` operation. + +However, when a `git-bug` operation is exported to JIRA it will only create a +single changelog entry. Furthermore, when we modify JIRA issues over the REST +API JIRA does not provide any information to associate that modification event +with the changelog. We must, therefore, heuristically match changelog entries +against operations that we performed in order to not import them as duplicate +events. In order to assist in this matching process, the bridge will record the +JIRA server time of the response to the `POST` (as reported by the `"Date"` +response header). During import, we keep an iterator to the list of `git-bug` +operations for the bug mapped to the Jira issue. As we walk the JIRA changelog, +we keep the iterator pointing to the first operation with an annotation which is +*not before* that changelog entry. If the changelog entry is the result of an +exported `git-bug` operation, then this must be that operation. We then scan +through the list of changeitems (changed fields) in the changelog entry, and if +we can match a changed field to the candidate `git-bug` operation then we have +identified the match. + +### Unlogged Changes + +Comments (creation and edition) do not show up in the JIRA changelog. However +JIRA reports both a `created` and `updated` date for each comment. If we import +a comment which has an `updated` and `created` field which do not match, then we +treat that as a new comment edition. If we do not already have the comment +imported, then we import an empty comment followed by a comment edition. + +Because comment editions are not uniquely identified in JIRA we identify them in +`git-bug` by concatenating the JIRA issue `id` with the `updated` time of the +edition. + +### Workflow Validation (future) + +The long-term plan for the JIRA bridge is to download and store the workflow +specifications from the JIRA server. This includes the required metadata for +issue creation, and the status state graph, and the set of required metadata for +status transition. + +When an existing `git-bug` is initially marked for export, the bridge will hook +in and validate the bug state against the required metadata. Then it will prompt +for any missing metadata using a set of UI components appropriate for the field +schema as reported by JIRA. If the user cancels then the bug will not be marked +for export. + +When a bug already marked for JIRA export (including those that were imported) +is modified, the bridge will hook in and validate the modification against the +workflow specifications. It will prompt for any missing metadata as in the +creation process. + +During export, the bridge will validate any export operations and skip them if +we know they will fail due to violation of the cached workflow specification +(i.e. missing required fields for a transition). A list of bugs "blocked for +export" will be available to query. A UI command will allow the user to inspect +and resolve any bugs that are "blocked for export". + +## Configuration + +As mentioned in the notes above, there are a few optional configuration fields +that can be set beyond those that are prompted for during the initial bridge +configuration. You can set these options in your `.git/config` file: + +### Issue Creation Defaults + +The format for this config entry is a JSON object containing fields you wish to +set during issue creation when exporting bugs. If you provide a value for this +configuration option, it must include at least the `"issuetype"` field, or the +bridge will not be able to export any new issues. + +Let's say that we want bugs exported to JIRA to have a default issue type of +"Story" which is `issuetype` with id `10001`. Then we will add the following +entry to our git-config: + +``` +create-issue-defaults = {"issuetype":"10001"} +``` + +If you needed an additional required field `customfield_1234` and you wanted to +provide a default value of `"default"` then you would add the following to your +config: + +``` +create-issue-defaults = {"issuetype":"10001","customfield_1234":"default"} +``` + +Note that the content of this value is merged verbatim to the JSON object that +is `POST`ed to the JIRA rest API, so you can use arbitrary valid JSON. + +### Assign git-bug id to field + +If you want the bridge to fill a JIRA field with the `git-bug` id when exporting +issues, then provide the name of the field: + +``` +create-issue-gitbug-id = "customfield_5678" +``` + +### Status Map + +You can specify the mapping between `git-bug` status and JIRA status id's using +the following: + +``` +bug-id-map = {\"open\": \"1\", \"closed\": \"6\"} +``` + +The format of the map is `<git-bug-status-name>: <jira-status-id>`. In general +your jira instance will have more statuses than `git-bug` will and you may map +more than one jira-status to a git-bug status. You can do this with +`bug-id-revmap`: + +``` +bug-id-revmap = {\"10109\": \"open\", \"10006\": \"open\", \"10814\": \"open\"} +``` + +The reverse map `bug-id-revmap` will automatically include the inverse of the +forward map `bug-id-map`. + +Note that in JIRA each different `issuetype` can have a different set of +statuses. The bridge doesn't currently support more than one mapping, however. +Also, note that the format of the map is JSON and the git config file syntax +requires doublequotes to be escaped (as in the examples above). + +### Full example + +Here is an example configuration with all optional fields set + +``` +[git-bug "bridge.default"] + project = PROJ + credentials-file = .git/jira-credentials.json + target = jira + server = https://jira.example.com + create-issue-defaults = {"issuetype":"10001","customfield_1234":"default"} + create-issue-gitbug-id = "customfield_5678" + bug-open-id = 1 + bug-closed-id = 6 +``` + +## To-Do list + +- \[0cf5c71\] Assign git-bug to jira field on import +- \[8acce9c\] Download and cache workflow representation +- \[95e3d45\] Implement workflow gui +- \[c70e22a\] Implement additional query filters for import +- \[9ecefaa\] Create JIRA mock and add REST unit tests +- \[67bf520\] Create import/export integration tests +- \[1121826\] Add unit tests for utilities +- \[0597088\] Use OS keyring for credentials +- \[d3e8f79\] Don't count on the `Total` value in paginations + +## Using CURL to poke at your JIRA's REST API + +If you need to lookup the `id` for any `status`es or the `schema` for any +creation metadata, you can use CURL to query the API from the command line. Here +are a couple of examples to get you started. + +### Getting a session token + +``` +curl \ + --data '{"username":"<username>", "password":"<password>"}' \ + --header "Content-Type: application/json" \ + --request POST \ + <serverUrl>/rest/auth/1/session +``` + +[!NOTE] +If you have a json pretty printer installed (`sudo apt install jq`), pipe the +output through through that to make things more readable: + +``` +curl --silent \ + --data '{"username":"<username>", "password":"<password>"}' \ + --header "Content-Type: application/json" \ + --request POST + <serverUrl>/rest/auth/1/session | jq . +``` + +example output: + +``` +{ + "session": { + "name": "JSESSIONID", + "value": "{sessionToken}" + }, + "loginInfo": { + "loginCount": 268, + "previousLoginTime": "2019-11-12T08:03:35.300-0800" + } +} +``` + +Make note of the output value. On subsequent invocations of `curl`, append the +following command-line option: + +``` +--cookie "JSESSIONID={sessionToken}" +``` + +Where `{sessionToken}` is the output from the `POST` above. + +### Get a list of issuetype ids + +``` +curl --silent \ + --cookie "JSESSIONID={sessionToken}" \ + --header "Content-Type: application/json" \ + --request GET https://jira.example.com/rest/api/2/issuetype \ + | jq . +``` + +**example output**: + +``` + { + "self": "https://jira.example.com/rest/api/2/issuetype/13105", + "id": "13105", + "description": "", + "iconUrl": "https://jira.example.com/secure/viewavatar?size=xsmall&avatarId=10316&avatarType=issuetype", + "name": "Test Plan Links", + "subtask": true, + "avatarId": 10316 + }, + { + "self": "https://jira.example.com/rest/api/2/issuetype/13106", + "id": "13106", + "description": "", + "iconUrl": "https://jira.example.com/secure/viewavatar?size=xsmall&avatarId=10316&avatarType=issuetype", + "name": "Enable Initiatives on the project", + "subtask": true, + "avatarId": 10316 + }, + ... +``` + +### Get a list of statuses + +``` +curl --silent \ + --cookie "JSESSIONID={sessionToken}" \ + --header "Content-Type: application/json" \ + --request GET https://jira.example.com/rest/api/2/project/{projectIdOrKey}/statuses \ + | jq . +``` + +**example output:** + +``` +[ + { + "self": "https://example.com/rest/api/2/issuetype/3", + "id": "3", + "name": "Task", + "subtask": false, + "statuses": [ + { + "self": "https://example.com/rest/api/2/status/1", + "description": "The issue is open and ready for the assignee to start work on it.", + "iconUrl": "https://example.com/images/icons/statuses/open.png", + "name": "Open", + "id": "1", + "statusCategory": { + "self": "https://example.com/rest/api/2/statuscategory/2", + "id": 2, + "key": "new", + "colorName": "blue-gray", + "name": "To Do" + } + }, +... +``` diff --git a/doc/design/cli-convention.md b/doc/design/cli-convention.md new file mode 100644 index 000000000..d65e48dbf --- /dev/null +++ b/doc/design/cli-convention.md @@ -0,0 +1,13 @@ +## Pattern + +CLI commands should consistently follow this pattern: + +``` +xxx --> list xxx things if list, otherwise show one +xxx new --> create thing +xxx rm --> delete thing +xxx show ID --> show one +xxx show --> show one with "select" implied ID +xxx yyy --> action commands for that thing, or subcommand +xxx select|deselect --> select/deselect implied ID +``` diff --git a/doc/design/data-model.md b/doc/design/data-model.md new file mode 100644 index 000000000..0553ed25d --- /dev/null +++ b/doc/design/data-model.md @@ -0,0 +1,215 @@ +# git-bug's reusable entity data model + +This document explains how git-bug's reusable distributed data structure in git +is working. This data structure is capable of: + +- storing an entity (bug, pull-request, config...) and its complete history in + git +- carry signed authorship of editions +- use git remotes as a medium for synchronisation and collaboration +- merge conflicts +- respect the rules you define as to what edition are possible +- carry attached media + +If you are looking for a different writing format or to see how you can easily +make your own, checkout [the example code](../../entity/dag/example_test.go). + +If you are not familiar with +[git internals](https://git-scm.com/book/en/v2/Git-Internals-Git-Objects), you +might first want to read about them, as the `git-bug` data model is built on top +of them. + +## Entities (bug, author, ...) are a series of edit operations + +As entities are stored and edited in multiple processes at the same time, it's +not possible to store the current state like it would be done in a normal +application. If two processes change the same entity and later try to merge the +states, we wouldn't know which change takes precedence or how to merge those +states. + +To deal with this problem, you need a way to merge these changes in a meaningful +way. Instead of storing the final bug data directly, we store a series of edit +`Operation`s. This is a common idea, notably with +[Operation-based CRDTs](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#Operation-based_CRDTs). + + + +To get the final state of an entity, we apply these `Operation`s in the correct +order on an empty state, to compute (aka "compile") our view. + +## Entities are stored in git objects + +An `Operation` is a piece of data, including: + +- a type identifier +- an author (a reference to another entity) +- a timestamp (there is also one or two [Lamport time](#time-is-unreliable)) +- all the data required by that operation type (a message, a status ...) +- a random [nonce](https://en.wikipedia.org/wiki/Cryptographic_nonce) to ensure + we have enough entropy, as the operation identifier is a hash of that data + (more on that later) + +These `Operation`s are aggregated in an `OperationPack`, a simple array. An +`OperationPack` represents an edit session of the entity. As the operation's +author is the same for all the `OperationPack` we only store it once. + +We store this pack in git as a git `Blob`; that consists of a string containing +a JSON array of operations. One such pack -- here with two operations -- might +look like this: + +```json +{ + "author": { + "id": "04bf6c1a69bb8e9679644874c85f82e337b40d92df9d8d4176f1c5e5c6627058" + }, + "ops": [ + { + "type": 3, + "timestamp": 1647377254, + "nonce": "SRQwUWTJCXAmQBIS+1ctKgOcbF0=", + "message": "Adding a comment", + "files": null + }, + { + "type": 4, + "timestamp": 1647377257, + "nonce": "la/HaRPMvD77/cJSJOUzKWuJdY8=", + "status": 1 + } + ] +} +``` + +To reference our `OperationPack`, we create a git `Tree`; it references our +`OperationPack` `Blob` under `"/ops"`. If any edit operation includes a media +(for instance in a text message), we can store that media as a `Blob` and +reference it here under `"/media"`. + +To complete the picture, we create a git `Commit` that references our `Tree`. +Each time we add more `Operation`s to our bug, we add a new `Commit` with the +same data-structure to form a chain of `Commit`s. + +This chain of `Commit`s is made available as a git `Reference` under +`refs/<namespace>/<id>`. We can later use this reference to push our data to a +git remote. As git will push any data needed as well, everything will be pushed +to the remote, including the media. + +Here is the complete picture: + + + +## Time is unreliable + +Before being able to merge conflicts, let's start with some building blocks. + +It would be very tempting to use the `Operation`'s timestamp to give us the +order to compile the final state. However, you can't rely on the time provided +by other people (their clock might be off) for anything other than just display. +This is a fundamental limitation of distributed system, and even more so when +actors might want to game the system. + +Instead, we are going to use +[Lamport logical clock](https://en.wikipedia.org/wiki/Lamport_timestamps). A +Lamport clock is a simple counter of events. This logical clock gives us a +partial ordering: + +- if L1 \< L2, L1 happened before L2 +- if L1 > L2, L1 happened after L2 +- if L1 == L2, we can't tell which happened first: it's a concurrent edition + +Each time we are appending something to the data (create an `Entity`, add an +`Operation`) a logical time will be attached, with the highest time value we are +aware of, plus one. This declares a causality in the events and allows ordering +entities and operations. + +The first commit of an `Entity` will have both a creation time and edit time +clock, while a later commit will only have an edit time clock. These clocks +value are serialized directly in the `Tree` entry name (for example: +`"create-clock-4"`). As a `Tree` entry needs to reference something, we +reference the git `Blob` with an empty content. As all of these entries will +reference the same `Blob`, no network transfer is needed as long as you already +have any entity in your repository. + +Example of a `Tree` of the first commit of an entity: + +``` +100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 create-clock-14 +100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 edit-clock-137 +100644 blob a020a85baa788e12699a4d83dd735578f0d78c75 ops +``` + +Example of a `Tree` of a later commit of an entity: + +``` +100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 edit-clock-154 +100644 blob 68383346c1a9503f28eec888efd300e9fc179ca0 ops +``` + +## Entities and Operation's ID + +`Operation`s can be referenced - in the data model or by users - with an +identifier. This identifier is computed from the `Operation`'s data itself, with +a hash of that data: `id = hash(json(op))` + +For entities, `git-bug` uses as identifier the hash of the first `Operation` of +the entity, as serialized on disk. + +The same way as git does, this hash is displayed truncated to a 7 characters +string to a human user. Note that when specifying a bug id in a command, you can +enter as few characters as you want, as long as there is no ambiguity. If +multiple entities match your prefix, `git-bug` will complain and display the +potential matches. + +## Entities support conflict resolution + +Now that we have all that, we can finally merge our entities without conflict, +and collaborate with other users. Let's start by getting rid of two simple +scenarios: + +- if we simply pull updates, we move forward our local reference. We get an + update of our graph that we read as usual. +- if we push fast-forward updates, we move forward the remote reference and + other users can update their reference as well. + +The tricky part happens when we have concurrent editions. If we pull updates +while we have local changes (non-straightforward in git term), `git-bug` creates +the equivalent of a merge commit to merge both branches into a DAG. This DAG has +a single root containing the first operation, but can have branches that get +merged back into a single head pointed by the reference. + +As we don't have a purely linear series of commits/`Operations`s, we need a +deterministic ordering to always apply operations in the same order. + +`git-bug` applies the following algorithm: + +1. load and read all the commits and the associated `OperationPack`s +2. make sure that the Lamport clocks respect the DAG structure: a parent + commit/`OperationPack` (that is, towards the head) cannot have a clock that + is higher or equal than its direct child. If such a problem happens, the + commit is refused/discarded. +3. individual `Operation`s are assembled together and ordered given the + following priorities: + 1. the edition's lamport clock if not concurrent + 2. the lexicographic order of the `OperationPack`'s identifier + +Step 2 is providing and enforcing a constraint over the `Operation`'s logical +clocks. What that means, is that **we inherit the implicit ordering given by the +DAG**. Later, logical clocks refine that ordering. This - coupled with signed +commits - has the nice property of limiting how this data model can be abused. + +Here is an example of such an ordering: + + + +We can see that: + +- Lamport clocks respect the DAG structure +- the final `Operation` order is \[A,B,C,D,E,F\], according to those clocks + +When we have concurrent editions, we apply a secondary ordering, based on the +`OperationPack`'s identifier: + + + +This secondary ordering doesn't carry much meaning, but it's unbiased and hard +to abuse. |