So I rewrote StGit in Rust

[jpgrayson]

The title says it. Over the past several months I have rewritten StGit in the Rust programming language. It's been great fun, and, I believe, successful.

Status Summary

The Rust implementation exists and works. And it is fast. It is ready for the StGit community to take it for a test drive.

Of course there remains work to do before it is release-ready.

• Command coverage
  • 41 of 44 StGit commands from Python version implemented
  • 1 new command: spill (replaces stg refresh --spill)
  • 3 commands need discussion:
    • copyright: disposition: remove and add copyright notice to stg version
    • clone
    • mail (The future of `stg mail` #186)
• Test suite passing
• Performance improvement: 4x
  • Example: stg top, which one might want to include one's shell prompt, improved from about 80ms to about 20ms.
  • Running the test suite improved from 150 to 35 seconds.
• Updated UI aesthetics
  • Colored output. NO_COLOR env variable is supported as is --color=never command line option.
  • Error message consistency
  • Identify misspelled patch names
  • Terse, symbol-oriented, and colorful output for stack operations
  • Unified interactive patch edit template. Same template used for new, edit, squash, refresh, and import.
  • Normalized and expanded access to patch edit command line options
• I learned more Rust. Yay!
• Man pages
• Shell completions
• Build and packaging details
  • Setup CI
  • build.rs script that does docs and completion business
  • Developer docs
  • Other stuff needed by downstream distributors?
• Testing on non-Linux platforms
  • MacOS: works as of 32516af
  • Windows: builds as of a35783e
  • Windows: get test suite running
• Beta testing

Motivations

Given that "RIIR" has become a bit of a trope, I feel compelled to lay out the motivations. So here is why I rewrote StGit in Rust:

1. A learning opportunity for me. Self-gratification was the primary motive. I wanted to write something substantial in Rust in order to both deepen my understanding of Rust and StGit. The beauty of open source is that this may be useful to others too.
2. Performance as a feature. I have often found the Python implementation of StGit to be frustratingly slow. In some cases, such as with stg series taking several hundred milliseconds, I may just be a latency snob. But as a StGit maintainer, the amount of time it takes to run StGit's test suite directly affects my ability (and will) to work on StGit.
3. A chance to revisit StGit user interface aesthetics. Things like judicious use of color, normalized and more terse representation of stack operations in user-facing output, normalized patch editing interface, and more consistent error messages fit under this umbrella.
4. Opportunities for significant changes afforded by a StGit 2.0 version. Since a reimplementation all but demands a major version bump, the Rust implementation also creates an opportunity to make a few measured, but significant changes to StGit commands.

Implementation Notes

Git vs. libgit2 vs. gitoxide

The Python implementation of StGit runs subordinate git processes for all operations on the Git repo.

For the Rust implementation, I landed on an unholy hybrid approach using both the git executable and git2-rs. The git2 (library) turned out to be good for accessing Git data structures such as the object database, config, references, and index. Where git2 was not as strong was with performing some operations that modify the underlying repository. A key example is patch application where git2::Repository::apply_to_tree() can have different (wrong) outcomes compared to git apply. Additionally, there are numerous higher-level git command behaviors that StGit relies on that would be difficult to replicate using the lower-level git2 capabilities (think git pull or git commit --gpg-sign).

So the general delineation is that git is used for non-trivial modifications to the repository and git2 is used for the simple, low-level (and high-frequency) accesses to repository state.

N.B. I did explore using subordinate git processes for everything, i.e. no libgit2, like how the Python implementation works. I was really hoping that this approach could work since it would cleave-off a significant portion of the dependency tree. I went so far as to implement a relatively complete stupid2 library with a git2-like interface, but using git subprocesses under the hood. The result was: a lot more code and much less performance. The performance landed somewhere between the current Rust implementation and the Python implementation.

On gitoxide

I also evaluated using gitoxide which is an ambitious ground-up implementation of git in Rust. The bottom line is that gitoxide does not yet provide sufficient API's to replace git2-rs. It will be interesting to reevaluate gitoxide for StGit when gitoxide reaches sufficient feature parity with git2.

Third-party dependencies

One thing about the Rust implementation of StGit that doesn't compare well to the Python implementation is its reliance on third-party dependencies. Whereas the Python implementation has zero runtime dependencies on third-party Python packages, the Rust implementation has 19 direct dependencies and 64 direct+transient dependencies.

A key downside to having all these dependencies is increased exposure to supply-chain attacks. This is a problem faced by the whole ecosystem. For StGit, the approach will be to limit direct and transient dependencies to those that are necessary and well established. I'll also be keeping an eye on what the broader Rust community is doing in this space as well as looking to downstream packagers/distros for best practices.

Safety

Type Safety

Expressing StGit's data structures and behaviors using Rust's robust type system has been a joy. There were plenty of challenging bits and pieces, which helped push me up the Rust learning curve, but in the end it felt tremendously productive to have so much more correctness baked-in at compile time versus what may only be uncovered at runtime when implementing in Python.

One typing success story is struct PatchName(String), a tuple-style struct wrapping a regular Rust String, that maintains the invariant of only allowing strings that follow all the weird patch name rules. PatchName is used prolifically throughout StGit and everywhere we see a PatchName we can have 100% confidence that we're dealing with a valid patch name. Contrast to the Python implementation which uses str (without type annotations) when dealing with patch names such that encountering a variable named patch, you first have to wonder whether it is a str or some other type (or None), and if it is a str, whether it has been validated to meet the patch naming rules. Barbarous!

Another success (I think) are stack transactions which are first setup using the builder pattern, then passed a closure which serves as a sandbox for the transaction operations to be defined, before finally being executed, consuming an old Stack and producing a new Stack. The boundaries imposed by struct StackTransaction and friends avoids mutable state and makes it easy to setup and perform a stack transaction correctly.

Memory Safety

StGit only uses unsafe {} in one place in the stupid (git wrapper) module to avoid potentially costly clones and can be replaced once scoped threads is stabilized.

StGit's biggest exposure to memory-unsafe code is via git2-rs, which wraps libgit2, which is implemented in C.

Get Involved

It would be great if some StGit veterans would give the Rust version a try.

$ git pull origin rust
$ git checkout rust
$ cargo install --path=.

File bugs at https://github.com/stacked-git/stgit/issues/new?labels=rust

Otherwise, I would love to hear your thoughts on the rust implementation and/or StGit 2.0 here in this GitHub discussion.

Thanks!
Pete

[ctmarinas]

Nice! One of my main motivations to write the first version of StGit was to learn Python, so I can see the appeal to re-write it in Rust (maybe I'll start contributing again for similar reasons ;)). I haven't looked at the code-base yet and I'm pretty novice in Rust. On one hand, we may get more contributors who are excited about Rust and want to join a fun project. On the other hand, there may not be so many knowledgeable people around compared to Python (and Rust is substantially more difficult, just try to do a doubly-linked list ;)). Another downside is the dependencies, Rust doesn't come with "batteries include" like Python. Distro packaging may become problematic.

Anyway, I think that's great. If we keep 1.x in a stable state, we can always revert to the Python version but I don't think we'd need to.

W.r.t. the commands left, I think 'copyright' needs some change as I'm not really the owner. I even forgot this command existed and I don't remember why I added it. A file in the top source directory should suffice. Personally I'd keep it as GPLv2 and maybe add "SPDX-License-Identifier: GPL-2.0-only" lines in all source files. What I can't tell is how compatible the GPL is with the Rust dependencies. Even changing the StGit license from GPL to something else is slightly problematic since there are lots of contributors we'd need to chase and get them to agree. That's one of the reasons I'd stick with GPLv2.

[ctmarinas]

IANAL but rewriting a program in another language may count as derivative work (and Pete's effort doesn't count as a clean-room implementation since he's now the top contributor to StGit). A quick shortlog shows about 72 contributors that we'd need to convince to agree to a new license. The original contributions were not under a CLA, so no copyright assigned to me.

So I'm not opposed to a new license, I just think it's difficult to change.

[jpgrayson]

Regarding the stg copyright command, my inclination is to simply remove it. I'm looking for reasons that we might want to retain it. That @ctmarinas does recall the rationale is another nail in its coffin. We could extend the stg version command to also include a copyright and license notice--this is what a lot of GNU tools do. I think I'll do that.

Regarding the possibility of a new license, my intent is to keep the GPLv2 license. I agree with @ctmarinas that this rewrite could be viewed as sufficiently derivative, but I could probably also rationalize why it's a sufficiently new expression of StGit to count as a non-derivative work. But I think that's mostly an academic question since I want to retain the same license.

I like the idea of adding the SPDX license identifier to each source file. I really wanted to avoid big copyright headers like we have in the Python source files. So I'll go ahead with the SPDX identifier. Thanks for that suggestion @ctmarinas.

@mandolaerik, I am curious about why we might want a different license? Is there something about MPL-2.0 that would be better for StGit? W.r.t. GPL-2.0-or-later, on the one hand it may protect StGit from currently unforeseen threats to software freedom (i.e. the FSF's stance), but on the other hand it exposes StGit to future/unknown/arbitrary license terms that may be dictated unilaterally by the FSF. So my inclination is to use GPL-2.0-only as @ctmarinas suggests. I'm interested in other thoughts on this topic though.

Regarding GPL compatibility with the new Rust library dependencies, I believe everything is okay. The FSF maintains a list of GPL-compatible licenses. Here is the output from cargo license showing the licenses of all those dependencies:

(Apache-2.0 OR MIT) AND BSD-3-Clause (1): encoding_rs
0BSD OR Apache-2.0 OR MIT (1): adler
Apache-2.0 OR Apache-2.0 WITH LLVM-exception OR MIT (1): wasi
Apache-2.0 OR BSL-1.0 (1): ryu
Apache-2.0 OR MIT (57): anyhow, autocfg, bitflags, bstr, bzip2, bzip2-sys, cc, cfg-if, chrono, clap, clap_lex, crc32fast, fastrand, filetime, flate2, form_urlencoded, git2, hashbrown, hermit-abi, idna, indexmap, itoa, jobserver, lazy_static, libc, libgit2-sys, libz-sys, log, num-integer, num-traits, openssl-probe, os_str_bytes, percent-encoding, pkg-config, proc-macro2, quote, remove_dir_all, serde, serde_derive, serde_json, socket2, syn, tar, tempfile, terminal_size, thiserror, thiserror-impl, time, unicode-bidi, unicode-ident, unicode-normalization, url, vcpkg, winapi, winapi-i686-pc-windows-gnu, winapi-x86_64-pc-windows-gnu, xattr
Apache-2.0 OR MIT OR Zlib (3): miniz_oxide, tinyvec, tinyvec_macros
BSD-3-Clause (1): instant
GPL-2.0-only (1): stgit
MIT (9): atty, curl, curl-sys, matches, openssl-sys, redox_syscall, schannel, strsim, textwrap
MIT OR Unlicense (4): memchr, regex-automata, termcolor, winapi-util

If we heed the FSF's analysis that Apache-2.0 is incompatible with GPL-2.0, all the dependencies may still be licensed as MIT, BSL-1.0, or BSD-3-Clause--all of which are compatible with GPL-2.0. Pruning Apache-2.0 and other superfluous licenses from the above, we end up with:

MIT AND BSD-3-Clause (1): encoding_rs
MIT (1): adler
MIT (1): wasi
BSL-1.0 (1): ryu
MIT (57): anyhow, autocfg, bitflags, bstr, bzip2, bzip2-sys, cc, cfg-if, chrono, clap, clap_lex, crc32fast, fastrand, filetime, flate2, form_urlencoded, git2, hashbrown, hermit-abi, idna, indexmap, itoa, jobserver, lazy_static, libc, libgit2-sys, libz-sys, log, num-integer, num-traits, openssl-probe, os_str_bytes, percent-encoding, pkg-config, proc-macro2, quote, remove_dir_all, serde, serde_derive, serde_json, socket2, syn, tar, tempfile, terminal_size, thiserror, thiserror-impl, time, unicode-bidi, unicode-ident, unicode-normalization, url, vcpkg, winapi, winapi-i686-pc-windows-gnu, winapi-x86_64-pc-windows-gnu, xattr
MIT (3): miniz_oxide, tinyvec, tinyvec_macros
BSD-3-Clause (1): instant
MIT (9): atty, curl, curl-sys, matches, openssl-sys, redox_syscall, schannel, strsim, textwrap
MIT (4): memchr, regex-automata, termcolor, winapi-util

Bottom line is that all dependencies seem to be distributable under GPLv2 compatible terms.

[ctmarinas]

Removing the 'copyright' command and maybe adding something to 'version' makes sense.

[mandolaerik]

@mandolaerik, I am curious about why we might want a different license?

@ctmarinas mentioned compatibility concerns with libs; GPLv3 and MPL-2.0 are two licenses that improve on that area. Personally, I don't think what copyleft license we choose would make a significant difference in how stgit will be forked or used.

[jpgrayson]

@mandolaerik, you make a good point about license compatibility with dependencies. I would be tempted to switch to GPLv3 for that reason, but I don't think I could unilaterally relicense the new code. Relevant excerpt from GPLv2 (emphasis added):

0. This License applies to any program or other work which contains a notice placed by the copyright holder saying it may be distributed under the terms of this General Public License. The "Program", below, refers to any such program or work, and a "work based on the Program" means either the Program or any derivative work under copyright law: that is to say, a work containing the Program or a portion of it, either verbatim or with modifications and/or translated into another language. (Hereinafter, translation is included without limitation in the term "modification".) Each licensee is addressed as "you".

Insofar as this rewrite includes code translated from the Python version, we'd have to audit rust vs. python code to identify the translated parts and get sign-off from all the relevant copyright holders to switch the license. Not impossible, but enough effort to warrant a proportionally strong motive.

To your point, I also don't think sticking with GPLv2 will cause any sort of material hindrance to either StGit adoption or our ability to leverage third-party crates. So I'm not feeling sufficiently motivated to make this license change at this time.

[ctmarinas]

I did want to try this but it seems nearly impossible on current Debian stable. The cargo version complains about 'edition' being 2021 when supports up to 2018. Changing 'edition' to 2018 goes into other issues and some error about unstable features. As I'm only barely familiar with Rust, I can't tell whether that's fixable, so I didn't log a bug against it (I'll compile my own rustc/cargo eventually but it would be nice to support Debian out of the box; maybe by the time 2.0 gets released, Debian will update to whatever cargo version is in testing).

[jpgrayson]

Using rustup is the recommended approach to installing/maintaining rust toolchains. I've found it pretty nice to work with. And in addition to providing a native rust toolchain for your platform, it can also be used to trivially install the rust toolchain for any supported target (e.g. rustup target install armv7-unknown-linux-gnueabi).

It looks like Debian stable ships Rust 1.48 (Nov. 2020). That's twelve releases back and, as you note, does not support the 2021 edition. Given Debian stable's goal of stability, where "stability" means "unchanging", I don't think it's a good environment for either new programming languages or new programs.

I also note that Debian still ships StGit 0.19 (Nov. 2018). My attempts to find/contact a package maintainer to help me to update StGit's Debian package to a recent release have thus far fallen flat, so I don't hold a lot of hope for Debian being a good platform for StGit regardless of the implementation language. As such I don't feel like my time would be well spent trying to make this Rust implementation of StGit work with such an old Rust release. I'd prefer to take the approach of letting Debian come around at its own pace.

Lastly, given that Rust produces statically compiled binaries, we can consider doing binary releases of StGit in the future. This could be a good path to enable StGit users on platforms like Debian that can't/won't package contemporary StGit releases.

[ctmarinas]

Yeah, it makes sense to ignore Debian stable for now. It probably even makes sense to remove the StGit package altogether from Debian, not sure anyone is actually using it.

[proski]

RIIR might be a trope in some circles, but StGit is the first time that a tool I'm actively using has migrated to Rust and I need to upgrade to keep it up-to-date. Now I'm more motivated to contribute fixes to StGit, as I'll be learning Rust in addition to improving this great tool. Thank you, @jpgrayson!

[dhowells]

Any idea how to get this to build on Fedora as an RPM? I've used rust2rpm to generate a specfile, but it doesn't put in the BuildRequires for dnf builddeps to use - and even if I put in the deps manually, Fedora doesn't carry all of them. Further, I tried to used cargo to install the "git-repository" create (since this isn't in Fedora), but it fails because there's no executable in there.

[Byron]

Without knowing anything about rust2rpm or what it takes to bundle an application, let me state that the git-repository is only used as dependency of StGit and handled by cargo entirely. As far as I know, stg only shells out to git occasionally, while everything else is done natively.