editing trees

7.22: adde/gui/editing trees:
. how do we sync a tree with the editor's
textual representation of the tree?
as lines are added to the text,
the line numbers change
but the tree nodes never change
without needing to rebuild the text too.
. there are 3 objects at work here:
the tree, the array of strings,
and an intermediate that's like wordcode,
in that it's a string of ptrs to tree nodes
that are in turn printable as words or symbols .
. at each line we have a ptr to the tree
but a line serves several nodes .
9.5:
. the ptr heading each line of text
is pointing to the root of the subtree
that is on that line .
. if we change that line or insert lines below it,
those changes are happening to that subtree
indicated by the root node;
therefore, to reflect any changes to the text,
we need reparse only that subtree ... ?!
actually,
there are 2 cases of tree:
# prefix:
. in the presentation of a folder system,
all the child nodes are below the parent's .
. that is a very simple and easy case,
as was expected above .
# infix:
. in the presentation of math formulae,
and programming code, such as adda,
we have expressions like (a+b),
where if all these expression tree nodes
are on separate lines,
then you see the root in the middle of the page,
not at the top . a further complication is that
the same text line can be representing
2 different subtrees: eg,
line#1: a*
line#2: b + c*d;
. in that example, line#1 and #2
share pieces of subtree#(a*b),
and line#2 represents parts of 2 subtrees,
so if line#2 is edited,
then there are possibly 2 subtrees to reparse .

9.5: the real-time complication:
. the text editing has to be very responsive;
therefore, we can't map each word
to a subwindow corresponding to a subtree;
instead, we have to let the user edit plain text,
and then have some way of mapping
text changes back to tree changes .
. to minimize reparsing,
we have to map character positions to tree nodes,
and then track how character modifications
have effected our text-to-tree map .

9.5: typical conditions simplifying:
. one simplifier provided by typical conditions
is tree size limits:
the expression trees that are complicated,
are usually only a few lines long;
they are separated by sequence operators,
or list delimiters .
. in the case of programming,
the effect of one tree change
can effect the parsing of another;
because, a symbol's meaning can change
either by deleting or creating a declaration
which will have a scope beyond the current tree
extending throughout the enclosing declare block .
. if there's a decl'deletion,
then we have to notice what type was being declared;
because, sometimes the type is determining
how we parsed the expression trees
that were surrounding that symbol;
eg, a declaration tells us whether or not
a symbol can be used as an infix operator,
or whether it was an atom or a function .
. much of syntax is only allowed for
certain types of symbols and not for others;
so, can we find a symbol of the same name
in an enclosing scope, and of the same type,
or a type change that won't matter ?
we may have to reparse the entire enclosing scope .
. if there's a decl'creation,
we must ensure that this scope
doesn't already declare this symbol .
. if there's a decl'modification,
we must ensure that type change doesn't matter,
else we have to reparse the entire enclosing scope .

large trees composed of byte-ptr trees

1.8: adda/mem'mgt/
large trees composed of byte-ptr trees:
. part of a space-saving obssession has been
finding how to make large trees be composed of
small trees that can use byte-sized pointers .
. the large tree is just like the local heap space:
a function activation record is given one segment
in which to store local data and param's;
after that fills up, it's turned into rib of a backbone segment:
(an array of c pointers to other segs).
. the way this is arranged should be such that
we can refer to the rib segs as indexes of the base seg,
. if all those fill up, then the last seg is the next size up:
. say the backbone hold 10ribs of size 10,
then the last rib is 10x10 size.
...
. isn't this supposed to be building the same way numbers do?
after the backbone fills up, it needs to be extended from above;
ie, replace the seg tree with a new backbone seg,
and then make the full backbone seg
a child of the new backbone seg:
====
|
====
| | | | | .

1.23: adda/type"tree/packing smaller trees:
. you can build a tree in large array
and if detecting under 255,
do a straight copy to small: for 1..256: copy word to byte
because the same links apply using the same structure
only smaller pointers .

byte-sized pointers

1.18: adda/dstr/byte-sized pointers:
. keep pointers small by seeing large lists
as subtrees;
one of the node types of a tree is
"(this subtree root declares a new subheap:
it includes access to a 256-size array of tree node).
. how does that scale? it does because
root of huge subtree had its own subheap
where all terminal nodes were tagged as
(this is a sys'ptr [32bit c pointer]
-- not a pair of byte-sized tree ptrs [byte'ptr])
[1.31:
. as the tree progresses downward with fanout,
it eventually consumes 256 nodes;
any tree-building further down
must be done from a new-subheap node`type
(ie, a node whose purpose is to declare that
the following subtree is based in a new subheap).
. lets say that a tree uses
2 subheaps worth of nodes;
then if the tree is balanced,
it can be built with only 2 new-subheap nodes
by putting the left and right subtrees
each in their own subheap;
if the tree is not balanced,
then space efficiency requires that subheaps be shareable,
so that many smaller subtrees can be
impl'd on the same subheap .
. to make best use of space,
the use of new-subheap node`types
must be minimized because they are overhead .]

. when having a ptr to subtree,
it needs a record:
sys`ptr to the subheap,
byte'ptr to where in the subheap subtree is rooted .

. when building trees from text, [1.31:
or when trees can be modified? ..]
then we need speed more than mem'
whereas figuring out how to pack for byte-ptr's
would be very time-consuming;
so, then these sort of trees should be word-sized .
. both sizes are distinguished from sys'pointers
with the term "(local ptr):
whereas a system pointer is logically a machine address
(practically an index into a process module),
a local ptr is always an index into the current subheap .
1.31:
. our tree node has less than 16 variants,
so the tag can fit in 4bits (a half-byte, nibble,
-- addressing a byte to extract the {hi,lo} 4bits );
the node's data will be sizes larger than a nibble,
and the tag should be at the beginning
to tell us what the rest of the node looks like;
so, in order to accommodate mem'allignment requirements,
without wasteful padding after the tag,
the subheap will have 2 forks
so that tags and data can each be
in their own arrays .

. a subheap supporting byte-ptr's
can hold only 256 nodes,
in turn needing a 128-byte chunk for the 256 * 4bit tags .
. these nodes are word sized:
#branch: (tag, left.byte-ptr, right.byte-ptr);
#leaf: (tag, symbol.word-ptr).

. subheaps are composed of chunks;
so, if a subheap is not enirely used,
it's not entirely alloc'd either .
. both byte-ptr and word-ptr subheaps
can use the same size chunks, 128 bytes,
to match the minimum chunk needed for tags .
. therefore 256*2byte data nodes = 128*2*2 = 4 chunks .
. if less than half of nodes are used,
then it can save on 2 chunks of 128 bytes .

. finally, a byte-ptr subheap needs to be
an array of 5 sys'pointers for access to the
1 tag chunk + 4 data chunks,
plus
whatever else is needed for variant tagging,
or part of an efficiency hack .

. if a large structure has a known minimum at init' time,
then it can be given a superchunk,
which is some arbitrary multiple of contiguous chunks .