WIP: Document the design of Nix

The current docs are all "how to do things" and no "what is Nix" or "why
are things the way they are".

I see lots of misconception on the wider internet, and I also think we
would benefit from a "living document" to answer some questions people
currently turn to the thesis for.

I think a new section of the manual can address all these issues.

7 files changed, 109 insertions, 1 deletions

diff --git a/doc/manual/local.mk b/doc/manual/local.mk
index 371ed6f21..a26fb8fcf 100644
--- a/doc/manual/local.mk
+++ b/doc/manual/local.mk
@@ -1,5 +1,9 @@
 ifeq ($(doc_generate),yes)
 
+MANUAL_SRCS := \
+  $(call rwildcard, $(d)/src, *.md) \
+  $(call rwildcard, $(d)/src, */*.md)
+
 # Generate man pages.
 man-pages := $(foreach n, \
   nix-env.1 nix-build.1 nix-shell.1 nix-store.1 nix-instantiate.1 \
@@ -97,7 +101,7 @@ doc/manual/generated/man1/nix3-manpages: $(d)/src/command-ref/new-cli
 	done
 	@touch $@
 
-$(docdir)/manual/index.html: $(MANUAL_SRCS) $(d)/book.toml $(d)/anchors.jq $(d)/custom.css $(d)/src/SUMMARY.md $(d)/src/command-ref/new-cli $(d)/src/command-ref/conf-file.md $(d)/src/expressions/builtins.md $(call rwildcard, $(d)/src, *.md)
+$(docdir)/manual/index.html: $(MANUAL_SRCS) $(d)/book.toml $(d)/anchors.jq $(d)/custom.css $(d)/src/SUMMARY.md $(d)/src/command-ref/new-cli $(d)/src/command-ref/conf-file.md $(d)/src/expressions/builtins.md
 	$(trace-gen) RUST_LOG=warn mdbook build doc/manual -d $(DESTDIR)$(docdir)/manual
 
 endif
diff --git a/doc/manual/src/SUMMARY.md.in b/doc/manual/src/SUMMARY.md.in
index c8cb72fc0..c320bde3f 100644
--- a/doc/manual/src/SUMMARY.md.in
+++ b/doc/manual/src/SUMMARY.md.in
@@ -15,6 +15,11 @@
     - [Multi-User Mode](installation/multi-user.md)
   - [Environment Variables](installation/env-variables.md)
   - [Upgrading Nix](installation/upgrading.md)
+- [Design and Data Model](design/design.md)
+  - [Overview](design/overview.md)
+  - [The Store Layer](design/store/store.md)
+    - [Store Entries](design/store/entries.md)
+    - [Store Paths](design/store/paths.md)
 - [Package Management](package-management/package-management.md)
   - [Basic Package Management](package-management/basic-package-mgmt.md)
   - [Profiles](package-management/profiles.md)
diff --git a/doc/manual/src/design/design.md b/doc/manual/src/design/design.md
new file mode 100644
index 000000000..7d4211764
--- /dev/null
+++ b/doc/manual/src/design/design.md
@@ -0,0 +1,5 @@
+# Design and Data Model
+
+Most of the manual is about how to use Nix.
+This chapter is about what Nix actually is.
+The hope is that it can serve as a reference for key concepts, and also shed light on why things are the way they are.
diff --git a/doc/manual/src/design/overview.md b/doc/manual/src/design/overview.md
new file mode 100644
index 000000000..05f4a70b2
--- /dev/null
+++ b/doc/manual/src/design/overview.md
@@ -0,0 +1,13 @@
+# Overview
+
+Nix is broken into layers that operate fairly independently.
+
+At the top is the *command line interface*, i.e. the argument parsing of the various Nix executables.
+
+Below that is the Nix *expression language*, in which packages and configurations are written.
+These are the layers which users interact with most.
+
+Below that is the *store layer*, Nix's machinery for presenting and files and fully elaborated build plans, and also executing those build plans.
+The store layer may not be as visible, but this is the heart of Nix.
+
+This chapter will start there and work up towards the more user-facing interfaces described in the rest of the manual.
diff --git a/doc/manual/src/design/store/entries.md b/doc/manual/src/design/store/entries.md
new file mode 100644
index 000000000..c16c98a36
--- /dev/null
+++ b/doc/manual/src/design/store/entries.md
@@ -0,0 +1,46 @@
+# Store Entries
+
+File system data in Nix is organized into *store entries*.
+A store entry is the combination of
+
+  - some file system data
+  - references to store entries
+
+## File system data
+
+Nix supports the a similar model of the file system as Git.
+Namely, every file system object falls into these three cases:
+
+ - File: arbitrary data
+
+ - Directory: mapping of names to child file system objects.
+   File children additionally have an executable flag.
+
+ - Symlink: may point anywhere.
+   In particular, Symlinks that do not point within the containing file system data or that of another store entry referenced by the containing store entry are allowed, but might not function as intended.
+
+A bare file as the "root" file system object is allowed.
+Note that there is no containing directory object to store its executable bit; it's deemed non-executable by default.
+
+## References
+
+Store entries can refer to both other store entries and themselves.
+
+Store references are normally calculated by scanning the file system data for store paths when a new store entry is created, but this isn't mandatory, as store entries are allowed to have references that don't correspond to contained store paths, and contained store paths that don't correspond to references.
+
+The references themselves need not be store paths per-se (this is an implementation detail of the store).
+But, like rendered store paths (see next section) in addition to identifying store entries they must also identify the store directory of the store(s) that contain those store entries.
+That said, all the references of the store entry must agree on a store dir.
+Also the store directory of the references must equal that of any store which contains the store entry doing the referencing.
+
+## Relocatability
+
+The two final restrictions of the previous section yield an alternative of view of the same information.
+Rather than associating store dirs with the references, we can say a store entry itself has a store dir if and only if it has at least once reference.
+
+This corresponds to the observation that a store entry with references, i.e. with a store directory under this interpretation, is confined to stores sharing that same store directory, but a store entry without any references, i.e. thus without a store directory, can exist in any store.
+
+Lastly, this illustrates the purpose of tracking self references.
+Store entries without self-references or other references are relocatable, while store paths with self-references aren't.
+This is used to tell apart e.g. source code which can be stored anywhere, and pesky non-reloctable executables which assume they are installed to a certain path.
+\[The default method of calculating references by scanning for store paths handles these two example cases surprisingly well.\]
diff --git a/doc/manual/src/design/store/paths.md b/doc/manual/src/design/store/paths.md
new file mode 100644
index 000000000..1e4369625
--- /dev/null
+++ b/doc/manual/src/design/store/paths.md
@@ -0,0 +1,30 @@
+# Store Paths
+
+A store path is a pair of a 20-byte digest and a name.
+
+Historically it is the triple of those two and also the store directory, but the modern implementation's internal representation is just the pair.
+This change is because in the vast majority of cases, the store dir is fully determined by the context in which the store path occurs.
+
+## String representation
+
+A store path is rendered as the concatenation of
+
+  - the store directory
+
+  - a path-separator (`/`)
+
+  - the digest rendered as Base-32 (20 bytes becomes 32 bytes)
+
+  - a hyphen (`-`)
+
+  - the name
+
+Let's take the store path from the very beginning of this manual as an example:
+
+    /nix/store/b6gvzjyb2pg0kjfwrjmg1vfhh54ad73z-firefox-33.1/
+
+This parses like so:
+
+    /nix/store/b6gvzjyb2pg0kjfwrjmg1vfhh54ad73z-firefox-33.1/
+    ^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^
+    store dir  digest                           name
diff --git a/doc/manual/src/design/store/store.md b/doc/manual/src/design/store/store.md
new file mode 100644
index 000000000..c2431f1c5
--- /dev/null
+++ b/doc/manual/src/design/store/store.md
@@ -0,0 +1,5 @@
+A Nix store is a collection of *store entries* referred to by *store paths*.
+Every store also has a "store directory path", which is a path prefix used for various purposes.
+
+There are many types of stores, but all of them at least respect this model.
+Some however offer additional functionality.