Buffer snapshots from unmodifiable data piece tables
AssigneeMicrosoft Corporation
InventorsDavid Pugh, Jack Tilford
Life of this patent
Estimating the term…
Abstract
A snapshots data structure provides compilers and other tools with snapshots of a buffer at different points in time. Snapshot heads identify trees within a directed acyclic graph (DAG) of nodes. Leaf nodes of a given tree collectively hold data elements representing information that was resident in the buffer at a particular point in time regardless of subsequent editing of the buffer. During buffer editing operations a new tree is created in the DAG with leaf nodes holding data elements that match one-to-one a subsequence of data elements held by leaf nodes of an existing tree.
Claims20
A memory configured by storing data and instructions in a computing system which has a processor operable in communication with the memory, the configured memory comprising:
- an editable buffer;
- a snapshots data structure stored in the memory, including a directed acyclic graph (DAG) of node(s), and a first snapshot head identifying a first tree within the DAG, the first tree including leaf node(s) having unmodifiable span(s) that hold data element(s) representing a first snapshot of a first version of information that was resident in the buffer at a particular point in time regardless of subsequent editing of the buffer;
- and
- processor instructions stored in the memory and designed for creating a second snapshot head identifying a second tree within the DAG and for creating in the DAG a second tree whose leaf node(s) have span(s) whose data element(s) represent a second snapshot of a second version of information that was resident in the buffer including data element(s) that match one-to-one a subsequence of data element(s) held by span(s) of leaf node(s) of the first tree of the DAG, thereby storing in the DAG a plurality of snapshots comprising a plurality of versions of information that was in the editable buffer.
A computer system comprising:
- a program;
- a memory which contains data in the form of a first snapshot of a first version of data elements in a buffer for the program and a second snapshot of a second version of data elements in the buffer for the program, the second snapshot generated at least in part by processor instructions which used a first binary tree of a directed acyclic graph (DAG) to create in the DAG a second binary tree for the second snapshot having unmodifiable leaf nodes with unmodifiable spans that hold data elements matching one-to-one a proper subsequence of data elements held by spans of leaf nodes of the first binary tree for the first snapshot, thereby storing in the DAG a plurality of snapshots comprising a plurality of versions of information that was in the buffer for the program;
- and
- at least one processor, in operable communication with the memory, which performed the processor instructions to create the second binary tree.
A storage medium configured with computer data and computer instructions for a method of providing access to snapshots of a text buffer without preventing buffer editing while a snapshot is in use, the method comprising:
- receiving an identification of a subsequence of data element(s) held by unmodifiable span(s) of leaf node(s) of a first tree of a directed acyclic graph (DAG), the first tree representing a first snapshot of a first version of information in the text buffer;
- and
- creating in the DAG a second tree which shares at least one unmodifiable leaf node with the first tree and whose leaf node(s) hold unmodifiable span(s) having textual data element(s) matching one-to-one the identified subsequence), the second tree representing a second snapshot of a second version of information in the text buffer, thereby storing in the DAG a plurality of snapshots comprising a plurality of versions of information that was in the text buffer.
Dependencies are inferred from the claim text.