Representation Search

In general, the search follows a directed acyclic graph (DAG), where multiple forward paths from a given node indicate a choice of equivalent representations. The DAG can be logically traversed from input to output or output to input; however, regardless of logical traversal order, the transformations must be applied in order from input to output for storage and output to input for retrieval. No searching is required for retrieval, as the sequence of operations for retrieval will be determined in advance by the result of the search for storage.

1. fakefs searches from input types to output types, forming a list of transforms corresponding to paths through the DAG. Each path from input to output is traversed, and in the process a series of nested plan objects is generated by each transform.
   1. If no plan object is generated, recursion terminates at this transform function. This is not an error unless no plan object is generated after traversing all paths through the DAG.

   2. If one or more plan objects are generated, their files will be fed into the next step in the path.

2. Any candidate which is the result of a transform at the leaves of the tree has its score computed, and that score aggregates up the branches of the tree. The candidate with the best final score is kept. All others are destroyed.

Short-cuts are not possible; a delta compression output may be larger than a compressed file output but a compressed delta compression output may be smaller.

Each transform is given the score of the current `best' representation at the same recursion depth (if any), the Inode (if any) of the file being inserted, and the file input of the transform. Transforms may inspect fakefs contents during transformation, e.g. to try to find likely co-inputs for delta computation. The return value of the transform is a candidate (a list of file outputs) which is then recursively fed to higher-depth transforms as input.

Note that recursion does not occur within the transformation functions--it happens around them, within the fakefs core.

When fakefs chooses a representation and stores its files, it also notes dependencies between representations in its reference-counting tables.

If the list of candidates generated by a transform is empty, the transform is considered to have failed, recursion is terminated, and a sibling transform is tried. This is the normal case if all possible representations generated by a transform have poorer scores than were known when the transform was attempted.

In case of success, each file is looked up in fakefs and any files already known to fakefs are skipped.

The existence of an `identity storage' transform which accepts the input endpoint as INPUT-TYPE and produces the output endpoint as OUTPUT-TYPE assures that there is always at least one storage candidate.

It is an error if no storage candidate emerges after all transforms are tried.