[gtk+] Extend public and internal documentation about GtkTreeModelFilter

[Kristian Rietveld <kristian src gnome org>]

commit aa9151a6ee497bd3712db7bc6842e1101ae6c94b
Author: Kristian Rietveld <kris gtk org>
Date:   Sat Aug 20 09:36:35 2011 +0200

    Extend public and internal documentation about GtkTreeModelFilter

 gtk/gtktreemodelfilter.c |  205 ++++++++++++++++++++++++++++++++++++++++------
 1 files changed, 180 insertions(+), 25 deletions(-)
---
diff --git a/gtk/gtktreemodelfilter.c b/gtk/gtktreemodelfilter.c
index 1aa7cdf..36d2ef7 100644
--- a/gtk/gtktreemodelfilter.c
+++ b/gtk/gtktreemodelfilter.c
@@ -53,37 +53,192 @@
  * a #GtkTreePath indicating the root node for the filter at construction time.
  * </para></listitem>
  * </itemizedlist>
- */
-
-
-/* ITER FORMAT:
  *
- * iter->stamp = filter->priv->stamp
- * iter->user_data = FilterLevel
- * iter->user_data2 = FilterElt
- */
-
-/* all paths, iters, etc prefixed with c_ are paths, iters, etc relative to the
- * child model.
+ * The basic API is similar to #GtkTreeModelSort. For an example on its usage,
+ * see the section on #GtkTreeModelSort.
+ *
+ * When using #GtkTreeModelFilter, it is important to realize that
+ * #GtkTreeModelFilter maintains an internal cache of all nodes which are
+ * visible in its clients. The cache is likely to be a subtree of the tree
+ * exposed by the child model. #GtkTreeModelFilter will not cache the entire
+ * child model when unnecessary to not compromise the caching mechanism
+ * that is exposed by the reference counting scheme. If the child model
+ * implements reference counting, unnecessary signals may not be emitted
+ * because of reference counting rule 3, see the #GtkTreeModel
+ * documentation. (Note that e.g. #GtkTreeStore does not implement
+ * reference counting and will always emit all signals, even when
+ * the receiving node is not visible).
+ *
+ * Because of this, limitations for possible visible functions do apply.
+ * In general, visible functions should only use data or properties from
+ * the node for which the visibility state must be determined, its siblings
+ * or its parents. Usually, having a dependency on the state of any child
+ * node is not possible, unless references are taken on these explicitly.
+ * When no such reference exists, no signals may be received for these child
+ * nodes (see reference couting rule number 3 in the #GtkTreeModel section).
+ *
+ * Determining the visibility state of a given node based on the state
+ * of its child nodes is a frequently occurring use case. Therefore,
+ * #GtkTreeModelFilter explicitly supports this. For example, when a node
+ * does not have any children, you might not want the node to be visible.
+ * As soon as the first row is added to the node's child level (or the
+ * last row removed), the node's visibility should be updated.
+ *
+ * This introduces a dependency from the node on its child nodes. In order
+ * to accommodate this, #GtkTreeModelFilter must make sure the necesary
+ * signals are received from the child model. This is achieved by building,
+ * for all nodes which are exposed as visible nodes to #GtkTreeModelFilter's
+ * clients, the child level (if any) and take a reference on the first node
+ * in this level. Furthermore, for every row-inserted, row-changed or
+ * row-deleted signal (also these which were not handled because the node
+ * was not cached), #GtkTreeModelFilter will check if the visibility state
+ * of any parent node has changed.
+ *
+ * Beware, however, that this explicit support is limited to these two
+ * cases. For example, if you want a node to be visible only if two nodes
+ * in a child's child level (2 levels deeper) are visible, you are on your
+ * own. In this case, either rely on #GtkTreeStore to emit all signals
+ * because it does not implement reference counting, or for models that
+ * do implement reference counting, obtain references on these child levels
+ * yourself.
  */
 
-/* A few notes:
- *  There are three model/views involved, so there are two mappings:
- *    * this model -> child model: mapped via offset in FilterElt.
- *    * this model -> parent model (or view): mapped via the position
- *                                            of FilterElt in the sequence.
+/* Notes on this implementation of GtkTreeModelFilter
+ * ==================================================
+ *
+ * Warnings
+ * --------
+ *
+ * In this code there is a potential for confusion as to whether an iter,
+ * path or value refers to the GtkTreeModelFilter model, or to the child
+ * model that has been set. As a convention, variables referencing the
+ * child model will have a c_ prefix before them (ie. c_iter, c_value,
+ * c_path). In case the c_ prefixed names are already in use, an f_
+ * prefix is used. Conversion of iterators and paths between
+ * GtkTreeModelFilter and the child model is done through the various
+ * gtk_tree_model_filter_convert_* functions.
+ *
+ * Even though the GtkTreeModelSort and GtkTreeModelFilter have very
+ * similar data structures, many assumptions made in the GtkTreeModelSort
+ * code do *not* apply in the GtkTreeModelFilter case. Reference counting
+ * in particular is more complicated in GtkTreeModelFilter, because
+ * we explicitly support reliance on the state of a node's children as
+ * outlined in the public API documentation. Because of these differences,
+ * you are strongly recommended to first read through these notes before
+ * making any modification to the code.
+ *
+ * Iterator format
+ * ---------------
+ *
+ * The iterator format of iterators handed out by GtkTreeModelFilter is
+ * as follows:
  *
- *  Note that there are two kinds of paths relative to the filter model
- *  (those generated from the sequence positions): paths taking non-visible
- *  nodes into account, and paths which don't.  Paths which take
- *  non-visible nodes into account should only be used internally and
- *  NEVER be passed along with a signal emission.
+ *     iter->stamp = filter->priv->stamp
+ *     iter->user_data = FilterLevel
+ *     iter->user_data2 = FilterElt
  *
- *  The filter model has a reference on every node that is not in the root
- *  level and has a parent with ref_count > 1.  Exception is a virtual root
- *  level; all nodes in the virtual root level are referenced too.
+ * Internal data structure
+ * -----------------------
+ *
+ * Using FilterLevel and FilterElt, GtkTreeModelFilter maintains a "cache"
+ * of the mapping from GtkTreeModelFilter nodes to nodes in the child model.
+ * This is to avoid re-creating a level each time (which involves computing
+ * visibility for each node in that level) an operation is requested on
+ * GtkTreeModelFilter, such as get iter, get path and get value.
+ *
+ * A FilterElt corresponds to a single node. The FilterElt can either be
+ * visible or invisible in the model that is exposed to the clients of this
+ * GtkTreeModelFilter. The visibility state is stored in the "visible_siter"
+ * field, which is NULL when the node is not visible. The FilterLevel keeps
+ * a reference to the parent FilterElt and its FilterLevel (if any). The
+ * FilterElt can have a "children" pointer set, which points at a child
+ * level (a sub level).
+ *
+ * In a FilterLevel, two separate GSequences are maintained. One contains
+ * all nodes of this FilterLevel, regardless of the visibility state of
+ * the node. Another contains only visible nodes. A visible FilterElt
+ * is thus present in both the full and the visible GSequence. The
+ * GSequence allows for fast access, addition and removal of nodes.
+ *
+ * It is important to recognize the two different mappings that play
+ * a part in this code:
+ *   I.  The mapping from the client to this model. The order in which
+ *       nodes are stored in the *visible* GSequence is the order in
+ *       which the nodes are exposed to clients of the GtkTreeModelFilter.
+ *   II. The mapping from this model to its child model. Each FilterElt
+ *       contains an "offset" field which is the offset of the
+ *       corresponding node in the child model.
+ *
+ * Throughout the code, two kinds of paths relative to the GtkTreeModelFilter
+ * (those generated from the sequence positions) are used. There are paths
+ * which take non-visible nodes into account (generated from the full
+ * sequences) and paths which don't (generated from the visible sequences).
+ * Paths which have been generated from the full sequences should only be
+ * used internally and NEVER be passed along with a signal emisson.
+ *
+ * Reference counting
+ * ------------------
+ *
+ * GtkTreeModelFilter forwards all reference and unreference operations
+ * to the corresponding node in the child model. In addition,
+ * GtkTreeModelFilter will also add references of its own. The full reference
+ * count of each node (i.e. all forwarded references and these by the
+ * filter model) is maintained internally in the "ref_count" fields in
+ * FilterElt and FilterLevel. Because there is a need to determine whether
+ * a node should be visible for the client, the reference count of only
+ * the forwarded references is maintained as well, in the "ext_ref_count"
+ * fields.
+ *
+ * In a few cases, GtkTreeModelFilter takes additional references on
+ * nodes. The first case is that a reference is taken on the parent
+ * (if any) of each level. This happens in gtk_tree_model_filter_build_level()
+ * and the reference is released again in gtk_tree_model_filter_free_level().
+ * This ensures that for all references which are taken by the filter
+ * model, all parent nodes are referenced according to reference counting
+ * rule 1 in the GtkTreeModel documentation.
+ *
+ * A second case is required to support visible functions which depend on
+ * the state of a node's children (see the public API documentation for
+ * GtkTreeModelFilter above). We build the child level of each node that
+ * could be visible in the client (i.e. the level has an ext_ref_count > 0;
+ * not the elt, because the elt might be invisible and thus unreferenced
+ * by the client). For each node that becomes visible, due to insertion or
+ * changes in visibility state, it is checked whether node has children, if
+ * so the child level is built.
+ *
+ * A reference is taken on the first node of each level so that the child
+ * model will emit all signals for this level, due to reference counting
+ * rule 3 in the GtkTreeModel documentation. If due to changes in the level,
+ * another node becomes the first node (e.g. due to insertion or reordering),
+ * this reference is transferred from the old to the new first node.
+ *
+ * When a level has an *external* reference count of zero (which means that
+ * none of the nodes in the level is referenced by the clients), the level
+ * has a "zero ref count" on all its parents. As soon as the level reaches
+ * an *external* reference count of zero, the zero ref count value is
+ * incremented by one for all parents of this level. Due to the additional
+ * references taken by the filter model, it is important to base the
+ * zero ref count on the external reference count instead of on the full
+ * reference count of the node.
+ *
+ * The zero ref count value aids in determining which portions of the
+ * cache are possibly unused and could be removed. If a FilterElt has
+ * a zero ref count of one, then its child level is unused. However, the
+ * child level can only be removed from the cache if the FilterElt's
+ * parent has an external ref count of zero. Otherwise, monitoring
+ * this level is necessary to possibly update the visibility state
+ * of the parent. This is an important difference from GtkTreeModelSort!
+ *
+ * Signals are only required for levels with an external ref count > 0.
+ * This due to reference counting rule 3, see the GtkTreeModel
+ * documentation. In the GtkTreeModelFilter we try hard to stick to this
+ * rule and not emit redundant signals (though redundant emissions of
+ * row-has-child-toggled could appear frequently; it does happen that
+ * we simply forward the signal emitted by e.g. GtkTreeStore but also
+ * emit our own copy).
  */
 
+
 typedef struct _FilterElt FilterElt;
 typedef struct _FilterLevel FilterLevel;
 
@@ -1385,7 +1540,7 @@ gtk_tree_model_filter_remove_elt_from_level (GtkTreeModelFilter *filter,
    *  - else, remove level.
    *
    *  if level != root level and the number of visible nodes is 0 (ie. this
-   *  is the last *  node to be removed from the level), emit
+   *  is the last node to be removed from the level), emit
    *  row-has-child-toggled.
    */