diff --git a/rust/treedirstate/.cargo/config b/rust/treedirstate/.cargo/config
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/.cargo/config
@@ -0,0 +1,8 @@
+# On OS X targets, configure the linker to perform dynamic lookup of undefined
+# symbols.  This allows the library to be used as a Python extension.
+
+[target.i686-apple-darwin]
+rustflags = ["-C", "link-args=-Wl,-undefined,dynamic_lookup"]
+
+[target.x86_64-apple-darwin]
+rustflags = ["-C", "link-args=-Wl,-undefined,dynamic_lookup"]
diff --git a/rust/treedirstate/Cargo.lock b/rust/treedirstate/Cargo.lock
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/Cargo.lock
@@ -0,0 +1,4 @@
+[[package]]
+name = "rusttreedirstate"
+version = "0.1.0"
+
diff --git a/rust/treedirstate/Cargo.toml b/rust/treedirstate/Cargo.toml
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "rusttreedirstate"
+version = "0.1.0"
+authors = ["Facebook Source Control Team <sourcecontrol-dev@fb.com>"]
+
+[profile.release]
+lto = true
+
+[lib]
+name = "rusttreedirstate"
+crate-type = ["cdylib"]
diff --git a/rust/treedirstate/src/lib.rs b/rust/treedirstate/src/lib.rs
new file mode 100644
--- /dev/null
+++ b/rust/treedirstate/src/lib.rs
@@ -0,0 +1,13 @@
+// Copyright Facebook, Inc. 2017
+//! treedirstate - Tree-based Directory State.
+//!
+//! This is a Rust implementation of the dirstate concept for Mercurial, using a tree structure
+//! in an append-only storage back-end.
+//!
+//! The directory state stores information for all files in a working copy that are of interest
+//! to Mercurial.  In particular, for each file in the working copy it stores the mode flags,
+//! size, and modification time of the file.  These can be compared with current values to
+//! determine if the file has changed.
+//!
+//! The directory state also stores files that are in the working copy parent manifest but have
+//! been marked as removed.
diff --git a/treedirstate/Makefile b/treedirstate/Makefile
new file mode 100644
--- /dev/null
+++ b/treedirstate/Makefile
@@ -0,0 +1,44 @@
+NAME := rusttreedirstate
+
+# Cargo's depfiles use full paths, so we must include the full path
+# to the rust library.
+DIR := $(realpath $(join $(dir $(firstword $(MAKEFILE_LIST))),../rust/treedirstate))
+
+MODE ?= release
+
+ifeq ($(MODE),release)
+CARGO_ARGS += --release
+endif
+
+ifeq ($(shell uname),Darwin)
+LIBSUFFIX := .dylib
+else
+LIBSUFFIX := .so
+endif
+
+RUSTLIB := $(DIR)/target/$(MODE)/lib$(NAME)$(LIBSUFFIX)
+RUSTDEP := $(DIR)/target/$(MODE)/lib$(NAME).d
+
+.PHONY: all
+all: $(NAME).so
+
+$(NAME).so: $(RUSTLIB)
+	cp $< $@
+
+$(RUSTLIB):
+	cd $(DIR) && cargo build $(CARGO_ARGS)
+
+.PHONY: test
+test:
+	cd $(DIR) && cargo test
+
+.PHONY: clean
+clean:
+	$(RM) $(NAME).so
+	cd $(DIR) && cargo clean
+
+# This pattern rule for Rust source files forces a rebuild if any source file
+# is deleted.
+$(DIR)/src/%.rs: ;
+
+-include $(RUSTDEP)