Giter Club home page Giter Club logo

hgit's Introduction

HGIT

This repo implements a full git-like data structure (commits, dirs, blob trees, blobs) using recursion schemes and uses it to implement a minimal proof-of concept version control tool that supports functionality including lazy diffing of merkle dirs and lazy merging of branches. Many of the techniques (hash pointer based store, lazy deref, etc) used are applicable to any recursive data structure that uses Merkle-type hash pointer based indirection, eg merkle lists (blockchains), merkle trees (git, mercurial), merkle DAGs (IPFS) and merkle AST's (unison, if I understand it correctly).

Demo using the provided dockerfile:

> docker build -t pkinsky/hgit:demo .
> docker run -it pkinsky/hgit:demo bash

let's create an empty repo:

bash:/# mkdir repo
bash:/# cd repo
bash:/repo# hgit init
bash:/repo# tree .hgit
.hgit
|-- state
`-- store
bash:/repo# cat .hgit/state.json
{"branches":{"default":"z"},"currentBranch":"default"}

hgit init creates a .hgit directory with a store subdir that will be used to store various hash-identified objects (commits, dir trees, file blobs, etc) and a state file used to track repo state, which consists of the current branch and a map of branch names to commit pointers.

Repos start with the 'default' branch, which is initialized as pointer to the null commit (z (or zero) is used as a pointer to the null commit)

Ok, cool. Let's add some files to the repo.

bash:/repo# echo "totally a real project" > README.md
bash:/repo# echo "pls no infringe" > LICENSE

bash:/repo# hgit status
current branch: default
diffs:
	EntityCreated at LICENSE
	EntityCreated at README.md
bash:/repo# hgit commit "initial demo project"
bash:/repo# cat .hgit/state.json
{"branches":{"default":"xE9cQhCc0Vvk"},"substantiated":[],"currentBranch":"default"}

We've created a few simple files and commited them, updating the 'default' branch's commit pointer to xE9cQhCc0Vvk. Let's take a look at the contents of our store, starting with that commit.

bash:/repo# tree .hgit
.hgit
|-- state
`-- store
    |-- xE9cQhCc0Vvk
    |-- xfUffAHam2Ob
    |-- xodfMZhuFTpg
    `-- yvdB7xqeqRxi


bash:/repo# cat .hgit/store/xE9cQhCc0Vvk 
{"root":"xfUffAHam2Ob","name":"initial demo project","type":"commit","parents":["z"]}

bash:/repo# cat .hgit/store/xfUffAHam2Ob 
{"children":[ {"path":"LICENSE","pointer":"yvdB7xqeqRxi","type":"file"}
            , {"path":"README.md","pointer":"xodfMZhuFTpg","type":"file"}
            ],
"type":"dir"
}

bash:/repo# cat .hgit/store/yvdB7xqeqRxi 
{"contents":"pls no infringe\n","type":"blob"}

bash:/repo# cat .hgit/store/xodfMZhuFTpg 
{"contents":"totally a real project\n","type":"blob"}

so here we have our commit (xE9cQhCc0Vvk), containing a pointer to the null commit and a root directory with our LICENSE and README.md files.

Now we're going to create a branch to demonstrate diffing branches (you'll have to take my word for it, but this is all done lazily):

bash:/repo# hgit status
current branch: default
diffs:
bash:/repo# hgit branch diff-example
bash:/repo# mkdir foo
bash:/repo# touch foo/bar
bash:/repo# touch baz

bash:/repo# tree
|-- LICENSE
|-- README.md
|-- baz
`-- foo
    `-- bar

bash:/repo# hgit status
current branch: diff-example
diffs:
	EntityCreated at baz
	EntityCreated at foo
    
bash:/repo# hgit commit "diff example branch a"

that's our first branch, 'diff-example'. Now lets hop back over to 'default' and make some changes there, too.

bash:/repo# hgit checkout default
bash:/repo# touch foo
bash:/repo# mkdir baz
bash:/repo# touch baz/bar

bash:/repo# tree
|-- LICENSE
|-- README.md
|-- baz
|   `-- bar
`-- foo

bash:/repo# hgit status
current branch: default
diffs:
	EntityCreated at baz
	EntityCreated at foo
    
bash:/repo# hgit commit "diff example branch b"

bash:/repo# hgit diff default diff-example
	DirReplacedWithFile at baz
	FileReplacedWithDir at foo
bash:/repo# hgit diff diff-example default
	FileReplacedWithDir at baz
	DirReplacedWithFile at foo

Here you can see hgit diff handling both the file-replaced-with-dir and dir-replaced-with-file cases.

Now let's try merging two branches!

bash:/repo# hgit branch merge-example

bash:/repo# hgit status
current branch: merge-example
diffs:

bash:/repo# mkdir branchtest
bash:/repo# touch branchtest/a
bash:/repo# echo "same same" > b

bash:/repo# hgit status
current branch: merge-example
diffs:
	EntityCreated at branchtest
	EntityCreated at b
bash:/repo# tree
.
|-- LICENSE
|-- README.md
|-- b
|-- baz
|   `-- bar
|-- branchtest
|   `-- a
`-- foo

Here's our branch - now let's make some changes in the 'default' branch that, while touching the same files and directories, are non-conflicting.

bash:/repo# hgit checkout default

bash:/repo# echo "same same" > b
bash:/repo# mkdir branchtest
bash:/repo# touch branchtest/b

bash:/repo# hgit status
current branch: default
diffs:
	EntityCreated at branchtest
	EntityCreated at b
bash:/repo# tree
.
|-- LICENSE
|-- README.md
|-- b
|-- baz
|   `-- bar
|-- branchtest
|   `-- b
`-- foo

bash:/repo# hgit commit "merge example branch b"

These changes are non-conflicting - both branches have created a file at 'b' with the same contents, and added files with different names to the directory 'branchtest'. They can be merged.

bash:/repo# hgit status
current branch: default
diffs:

bash:/repo# hgit merge merge-example "merge test"
bash:/repo# tree
.
|-- LICENSE
|-- README.md
|-- b
|-- baz
|   `-- bar
|-- branchtest
|   |-- a
|   `-- b
`-- foo

Here's a counterexample, in which a merge fails due to a non-resolvable change:

bash:/repo# hgit branch merge-fail-example
bash:/repo# echo "mario" > character
bash:/repo# hgit commit "merge fail branch a"

in one branch, we will create a file, 'character', containing the string "mario".

bash:/repo# hgit checkout default
bash:/repo# echo "luigi" > character
bash:/repo# hgit commit "merge fail branch b"
bash:/repo# hgit merge merge-fail-example "failing merge"
hgit: user error (merge nonviable due to: MergeViolation {mergeViolationPath = ["character"]})

As expected, this merge fails - the algorithm has no way of knowing which character to pick.

DISCLAIMERS:

disclaimer: all hashes shown below are the result of some janky non-cryptographic hash function being converted into [a..z,A..Z,0..9]. This project now uses blake2 digests encoded as strings using base16 disclaimer: running this example will likely result in different hashes, as the hashes are derived from the serialized json structure of hgit objects which continues to change.

hgit's People

Stargazers

Heneli Kailahi avatar

Watchers

James Cloos avatar

Forkers

hkailahi

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.