README.old

Core Object
===========

Author: Eric Wasylishen
E-Mail: ewasylishen@gmail.com
License: http://www.opensource.org/licenses/mit-license.php


major rewrite - removing the whole "nested" concept because it is unwieldly
and overly general.

the new design is just as powerful but much simpler.

persistent roots are as before, but now they can only exist at the top level of a store.               
instead of trying to use the persistent root mechanism itself to capture the history
of changes to a persistent root (commit, revert to version, create branch, switch branch, etc),
there will now be a command log.


Store concept: no UUID, only has a URL. A proot can be copied into as many stores as you like
but the pair (store URL, proot UUID) uniquely identifies tye proot state. all that's needed is 
to make sure a proot's UUDI is unique within a store, which is trivial.

 rationale:
  - if stores had UUIDs, not sure what the UUID would mean. It wouldn't be unique (e.g. if a store is backed up, you have 2 stores with the same uuid).
  - it would serve as a kind of grouping mechanism for persistent roots, e.g.
    proot X is in store UUID Y, where Y represents my photo library.
  - but this introduces a whole new level of complexity, 
     = can proot exist outside of a store UUID?
     = can proot be moved to different store UUID?
  - no clear benifit - better to use another mechanism (e.g. tagging) to group persistent
    roots together, and keep stores as an implementation detail.


unsure at the moment if this command log will be kept directly in the persistent roots
or in a separate library/location on disk.

--- Branching undo comment:

-compare with other apps that have
  * linear model-level and linear meta-level,
     (ui has a list of past document states, you can click to reset to a state.
      cmd+Z works as normal - and will undo visiting a state, for example -
      this is the "meta-level" undo.)

  * or branching model-level and no meta-level
     (ui has a tree of past document states, you can click to reset to a state.
      cmd+Z navigates the tree - so you can't undo visiting a state.)
  
- CO will have branching model-level and linear meta-level
   (ui has a tree of past document states, you can click to reset to a state.
    cmd+Z operates on a linear list of UI actions, such as change branch,
    change state, create branch, etc., so all of those actions are undoable/redoable.)

-we can easily undo/redo branch creation/deletion,
proot creation/deletion, because these things are all constant size.

So proot delete just serializes the proot and all branches and stores 
it in the undo log.

app ideas:
- structured text editor
- simple graphing / sketch / presentation slide design / vector drawing app
- ???


-- App concept:

-name is "Typewriter".
-document format: a bundle ".etoileTypewriter"
-each bundle is a coreobject store; with one main persistent root which can have branches

-ui maps one ".etoileTypewriter" bundle to its main persistent root, which is displayed as a document window.
-undo/redo stack is per-persistent-root

-embedded object format:

{ type: "document"
  paragraphs:
    [  {"type" : "paragraph",
        "text" : "<rtf stream>"}, ... ]
  
-menu functions:

document
  - save: tags the current version. stored either in branch or proot metadata
  - duplicate: saves a copy of the store. ?
  - branch: makes a new branch.
  - branches...: shows branches, allows switching, deleting, rename, etc.
  - history..: shows history graph. clicking goes to a state. right click for "backout" aka selective undo
  
edit
  - undo
  - redo
  
  -cut/copy/paste/drag/drop

selection behaviour:
  - for fun we could implement undoable selection


suppose you select a few words before para1 up to a few words after, and hit cut.
 clipboard contents should be an array of  3 things: [ "rich text", { paragraph 1 value object } , "rich text" ]




-- Async saving

- ui only needs to block until immutable snapshot is prepared.
- v2 feature



-- Ideas on sql:

Delta storage inspired by mercurial revlog:

revid INTEGER PRIMARY KEY | contents BLOB | delta BOOLEAN
--------------------------+---------------+--------------
0                         | ???           | no
1                         | ???           | yes
2                         | ???           | no
3                         | ???           | yes
4                         | ???           | yes
5                         | ???           | yes
6                         | ???           | no

suppose we want to reconstruct the delta revision 500000:

SELECT * FROM test WHERE revid <= 500000 AND revid >= (SELECT MAX(revid) FROM test WHERE delta = 0 AND revid < 500000);


With index on delta:

sqlite> explain query plan SELECT * FROM test WHERE revid <= 500000 AND revid >= (SELECT MAX(revid) FROM test WHERE delta = 0 AND revid < 500000);
0|0|0|SEARCH TABLE test USING INTEGER PRIMARY KEY (rowid>? AND rowid<?) (~62500 rows)
0|0|0|EXECUTE SCALAR SUBQUERY 1
1|0|0|SEARCH TABLE test USING COVERING INDEX deltaindex (delta=? AND rowid<?) (~1 rows)

Without index on delta;

sqlite> explain query plan SELECT * FROM test WHERE revid <= 500000 AND revid >= (SELECT MAX(revid) FROM test WHERE delta = 0 AND revid < 500000);
0|0|0|SEARCH TABLE test USING INTEGER PRIMARY KEY (rowid>? AND rowid<?) (~62500 rows)
0|0|0|EXECUTE SCALAR SUBQUERY 1
1|0|0|SEARCH TABLE test USING INTEGER PRIMARY KEY (rowid<?) (~1 rows)
sqlite> SELECT * FROM test WHERE revid <= 500000 AND revid >= (SELECT MAX(revid) FROM test WHERE delta = 0 AND revid < 500000);

The index seems to make no difference, even on 10 million rows with ~2k non-delta rows, it's still instant without the index.




---- Undo.
Thought about per-branch undo/redo logs.
The scenario would be if you had two branches of a persistent open (on screen) at the same time, and were working on both.

Af first glance it seems like we could allow undoing on a subset of the branches (plus the proot-global edits like set metadata, set current branch) of a persistent root. Under closer examination however you can arrive at weird states because you may have undone the proot-global edits but  the branches you're not performing undo/redo are too far ahead.

As a workaround the user could use history navigation commands to achieve the same effect, which is probably fine considering this is an advances use case.


Think about per-app/per-work context undo/redo logs for a persistent root.
My initial feeling is that since these are selective undo ops, they should only happen at the model level, and we should keep the reliable 

Comment from Quentin on COCustomTrack:
 * A persistent history track to aggregate hand-picked revisions produced by 
 * multiple unrelated objects.
 *
 * Unlike COHistoryTrack, COCustomTrack lets you control which revisions exist 
 * on the track, without worrying the objects that produced these revisions 
 * belong to the track. In other words, the tracked objects are lazily computed 
 * based on the revisions that were added to the track until now.
 *
 * COCustomTrack can be used to implement undo/redo track when the changes are 
 * not limited to a root object or root object collection (e.g. library), but 
 * span many objects edited in unrelated applications or concern actions that 
 * doesn't involve core objects.<br />
 * For example, an Object Manager that supports editing the entire CoreObject 
 * graph isn't interested in all the changes to support undo/redo at the 
 * application level, but only in the changes done in the ObjectManager. In this 
 * case, using COHistoryTrack wouldn't work, because most revisions produced by 
 * editing the objects in other applications have to be filtered out.
 
I think the Object Manager couldn't possibly use NestedVersioning's per-Persistent Root undo/redo log to implement its undo system.


Thought:
1. Let's move the undo/redo log entirely outside of CoreObject core.
    - only con is committing the change and adding the edit to the undo log aren't atomic together.
        - alternatively we could keep the log in the same db so we get atomicity, but leave the logic up to the app.
    
2. Accept that the simple per-Persistent Root undo/redo log currently implemented in NestedVersioning, while elegant, can't deal with multi-user collaboration, or different work contexts that should have their own undo/redo (e.g. image editor, object manager)

3. Build a default undo manager like the current one but:
    - each commit is tagged with a work context. This is a dictionary that could be like:
          { editingBranch : aBranch, app : myImageEditor }
          { app : myImageEditor, user : eric }


    - when the app wants to undo, it provides a search query like { app : objectManager, user : eric }.
    - be able to handle selection undo/redo, where selection state exists only in the undo/redo log
    


Lessons about object context:

Objects should send accurate change tracking info to the context




Design decisions
================

- Persistent root deletion, gc?

- Persistent root contents: garbage collected or not? tree structure?
 * 3 options:
 *  1. All objects must have a composite relationship path to the root item
 *     (tree approach)
 *  2. Same as 1, but objects can have a chain of references from the tree
 *     (garbage-collected graph approach)
 *  3. Objects don't need a reference to stay alive (multiple roots approach)
 *
 * 1 seems unnecessairily restrictive.
 * 3 introduces an explicit "delete" operation. This will pollute diffs with
 *   "Delete index 3 of files" + "delete file a, b, c, d" when the set of files
 *   a,b,c,d is derived from "index 3". 
 * 2 seems to be the best option.
 
- 



Editing Context requirements:
=============================

- Support gc'ed context contents
- Track changes.
- Maintain relationship cache within the graph
- Copy algorithm can operate on editing context
- diff can operate on two editing contexts
- convenience algorithms like "remove object from parent"
- move object


Item graph requirements
=======================

- can make incremental changes where each change may not be a "totally valid" (may have missing _composite children_) state
  => this is needed to apply diff.
  
Store requirements
==================
  

Proposed plan:
==============