+
+/*** Structure: how GtkFileSystemModel works
+ *
+ * This is a custom GtkTreeModel used to hold a collection of files for GtkFileChooser. There are two use cases:
+ *
+ * 1. The model populates itself from a folder, using the GIO file enumerator API. This happens if you use
+ * _gtk_file_system_model_new_for_directory(). This is the normal usage for showing the contents of a folder.
+ *
+ * 2. The caller populates the model by hand, with files not necessarily in the same folder. This happens
+ * if you use _gtk_file_system_model_new() and then _gtk_file_system_model_add_and_query_file(). This is
+ * the special kind of usage for "search" and "recent-files", where the file chooser gives the model the
+ * files to be displayed.
+ *
+ * Internal data structure
+ * -----------------------
+ *
+ * Each file is kept in a FileModelNode structure. Each FileModelNode holds a GFile* and other data. All the
+ * node structures have the same size, determined at runtime, depending on the number of columns that were passed
+ * to _gtk_file_system_model_new() or _gtk_file_system_model_new_for_directory() (that is, the size of a node is
+ * not sizeof (FileModelNode), but rather model->node_size). The last field in the FileModelNode structure,
+ * node->values[], is an array of GValue, used to hold the data for those columns.
+ *
+ * The model stores an array of FileModelNode structures in model->files. This is a GArray where each element is
+ * model->node_size bytes in size (the model computes that node size when initializing itself). There are
+ * convenience macros, get_node() and node_index(), to access that array based on an array index or a pointer to
+ * a node inside the array.
+ *
+ * The model accesses files through two of its fields:
+ *
+ * model->files - GArray of FileModelNode structures.
+ *
+ * model->file_lookup - hash table that maps a GFile* to an index inside the model->files array.
+ *
+ * The model->file_lookup hash table is populated lazily. It is both accessed and populated with the
+ * node_get_for_file() function. The invariant is that the files in model->files[n] for n < g_hash_table_size
+ * (model->file_lookup) are already added to the hash table. The hash table will get cleared when we re-sort the
+ * files, as the array will be in a different order and the indexes need to be rebuilt.
+ *
+ * Each FileModelNode has a node->visible field, which indicates whether the node is visible in the GtkTreeView.
+ * A node may be invisible if, for example, it corresponds to a hidden file and the file chooser is not showing
+ * hidden files. Also, a file filter may be explicitly set onto the model, for example, to only show files that
+ * match "*.jpg". In this case, node->filtered_out says whether the node failed the filter. The ultimate
+ * decision on whether a node is visible or not in the treeview is distilled into the node->visible field.
+ * The reason for having a separate node->filtered_out field is so that the file chooser can query whether
+ * a (filtered-out) folder should be made sensitive in the GUI.
+ *
+ * Visible rows vs. possibly-invisible nodes
+ * -----------------------------------------
+ *
+ * Since not all nodes in the model->files array may be visible, we need a way to map visible row indexes from
+ * the treeview to array indexes in our array of files. And thus we introduce a bit of terminology:
+ *
+ * index - An index in the model->files array. All variables/fields that represent indexes are either called
+ * "index" or "i_*", or simply "i" for things like loop counters.
+ *
+ * row - An index in the GtkTreeView, i.e. the index of a row within the outward-facing API of the
+ * GtkFileSystemModel. However, note that our rows are 1-based, not 0-based, for the reason explained in the
+ * following paragraph. Variables/fields that represent visible rows are called "row", or "r_*", or simply
+ * "r".
+ *
+ * Each FileModelNode has a node->row field which is the number of visible rows in the treeview, *before and
+ * including* that node. This means that node->row is 1-based, instead of 0-based --- this makes some code
+ * simpler, believe it or not :) This also means that when the calling GtkTreeView gives us a GtkTreePath, we
+ * turn the 0-based treepath into a 1-based row for our purposes. If a node is not visible, it will have the
+ * same row number as its closest preceding visible node.
+ *
+ * We try to compute the node->row fields lazily. A node is said to be "valid" if its node->row is accurate.
+ * For this, the model keeps a model->n_nodes_valid field which is the count of valid nodes starting from the
+ * beginning of the model->files array. When a node changes its information, or when a node gets deleted, that
+ * node and the following ones get invalidated by simply setting model->n_nodes_valid to the array index of the
+ * node. If the model happens to need a node's row number and that node is in the model->files array after
+ * model->n_nodes_valid, then the nodes get re-validated up to the sought node. See node_validate_rows() for
+ * this logic.
+ *
+ * You never access a node->row directly. Instead, call node_get_tree_row(). That function will validate the nodes
+ * up to the sought one if the node is not valid yet, and it will return a proper 0-based row.
+ *
+ * Sorting
+ * -------
+ *
+ * The model implements the GtkTreeSortable interface. To avoid re-sorting
+ * every time a node gets added (which would lead to O(n^2) performance during
+ * the initial population of the model), the model can freeze itself (with
+ * freeze_updates()) during the intial population process. When the model is
+ * frozen, sorting will not happen. The model will sort itself when the freeze
+ * count goes back to zero, via corresponding calls to thaw_updates().
+ */