libdog/README.md at main · gritzko/libdog · GitHub

//blob/show" data-turbo-transient="true" />

Skip to content

Search or jump to...

Search code, repositories, users, issues, pull requests...

-->

Search

Clear

Search syntax tips

Provide feedback

--><br>We read every piece of feedback, and take your input very seriously.

Include my email address so I can be contacted

Cancel

Submit feedback

Saved searches

Use saved searches to filter your results more quickly

-->

Name

Query

To see all available qualifiers, see our documentation.

Cancel

Create saved search

Sign in

//blob/show;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up

Appearance settings

Resetting focus

You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.

Dismiss alert

{{ message }}

gritzko

libdog

Public

Notifications<br>You must be signed in to change notification settings

Fork

Star

FilesExpand file tree

main

/README.md

Copy path

Blame<br>More file actions

Blame<br>More file actions

Latest commit

History<br>History<br>History

160 lines (131 loc) · 6.16 KB

main

/README.md

Copy path

Top

File metadata and controls<br>Preview

Code

Blame

160 lines (131 loc) · 6.16 KB

Raw<br>Copy raw file<br>Download raw file

OutlineEdit and raw actions

libdog: token-level revision control

libdog is a token-level revision control toolkit library. It contains<br>various primitives, algorithms and data structures, including:

source code dogenizers for about 60 languages,

git compatibility utils: object and file formats, git's sync protocol,

CRDT weave diff/merge/blame (RGA/CausalTree like),

N.Fraser's diff cleanup,

B.Cohen's patience diff,

through its libabc dep, also Myers diff and other classic algos,

through libabc, various on-disk formats (hashmaps, sorted sets, etc).

many other things.

libdog is not "git reimplemented" like libgit2 or gitoxide.<br>That was not the objective here as git's commands and formats are<br>highly idiosyncratic legacy, to put that bluntly, and all of its<br>diff/merge/blame logic is line-based. Meanwhile, git's object model<br>is very much an Internet-standard-level thing. For that reason,<br>libdog contains all the necessary and performance-critical revision<br>control primitives that absolutely have to be implemented in a native<br>lib. The size tells the story: gitoxide is about 270 KLoC of<br>Rust. libdog's core is 14 KLoC of C, 24 counting its tests. The<br>tokenizers are another 54 KLoC, but those are Ragel generated.

The revision control system per se uses all these primitives from a<br>safer environment. In particular, libdog jab bindings form the<br>foundation of Beagle the SCM system that is written in fully<br>malleable JavaScript. This is similar to git's plumbing vs porcelain<br>division, but deeper.

libdog is written in ABC, a very minimalistic zero-alloc C dialect.

Tokenizers

Line-granular history is a historical accident of diff(1). Rename<br>one variable and a line-based tool reports the whole line rewritten;<br>two people editing opposite ends of the same line get a conflict that<br>isn't one. libdog versions each language's native tokens. 60 languages<br>are supported. For unknown grammars it falls back to the generic-text<br>tokenizer.

Each tokenizer is a hand-written Ragel scanner that classifies source<br>bytes into tagged tokens. The brilliance of Ragel is that there is no<br>parse tree, no allocation, and no dependencies. For example, the C<br>dogenizer can process 250MB/s on a laptop, which effectively means<br>tokenization is free for any practical purpose. That was in fact the<br>critical finding in applying CRDTs to the git data model: blobs can be<br>parsed on the fly, so all the CausalTree logic can be applied<br>transparently to very regular git blobs.

$ dogtok example.c

S ok64<br>S SumAll<br>P (<br>S u64s<br>S a<br>P )<br>P {<br>W \n<br>S u64<br>L 0<br>P ;<br>D //<br>D fold

Tag alphabet

A token is a tok32: a 5-bit tag, a display bit, a 2-bit diff side, a 24-bit<br>end offset. THEME.h paints the tags.

Tag<br>Meaning

comment

string literal

number literal

preprocessor, annotation

keyword

punctuation

default — identifiers

whitespace

URI — invisible click target

A second pass (tok/DEF.h) enriches these with N for a defined name and<br>C for a call site; F marks a filename column.

Languages

60 dogenizers, dispatched by extension or by filename, for files whose name<br>is their type (Makefile, Dockerfile, .gitignore, .clang-format).<br>Unknown extensions fall back to the plain-text lexer rather than failing.

Family<br>Languages

Systems<br>C .c .h · C++ .cpp .cc .cxx .hpp .hh .hxx · Go .go · Rust .rs · D .d · Zig .zig · Odin .odin · Solidity .sol · Verilog .v .sv · GLSL .glsl .vert .frag .geom .comp · LLVM IR .ll

JVM & .NET<br>Java .java · Kotlin .kt .kts · Scala .scala .sc · C# .cs · F# .fs .fsi .fsx · Clojure .clj .cljs .cljc .edn

Scripting<br>Python .py · JavaScript .js .jsx .mjs · TypeScript .ts .tsx · Ruby .rb · Perl .pl...