path: root/TODO

- Short-term tasks:

  - Test suite
  - Rename

  - Plan for initialization checks:

    - Implement a tree based data flow analysis

Processing:
	statements and expressions have after sets
	Boolean expressions also have assigned-if-true assigned-if-false
	sets.

	Almost all statements and expressions are called with 
	a before set. The call is supposed to set.

	The "after" set applies after an expression/statement has
	been fully executed, including all its children. Note:
	children means children. goto only has the label
	expression as a child.

	Ast nodes with multiple predecessors are treated
	specially. They need to compute their before sets
	themselves. When we reach them in the tree, they will
	look at the after set of all their other predecessors and
	combine those with the passed before set.

	It's important that labels don't rely on their immediate
	predecessor being stored in their list of predecessors
	because in wacky cases like this:

		while (<expr>)
		     @lll:

	it may not be apparent which node is the predecessor. Or,
	if you try to compute the control flow graph, you will
	find that it's sucessor is some sub-expression of <expr>,
	which then means it doesn't know what to do about if-true
	and if-false assignments.

	Nodes that transfer control (break, continue, goto,
	return) must store an after set that is just a copy of
	the before set, but then return a set that
	is "everything". This is because the code that follows
	immediateloy after such a node can safely dereference
	variables that are not initialized on the path coming
	from the transfer node. Because they will never be
	reached from that node.

	However, functions should ignore the before set because
	their tree-based predecessor doesn't actually transfer
	control.

	Processing terminates once none of the after sets are
	changing.

	Code-wise, we can adopt the convention that a NULL set is
	a full set - ie., intersect will just ignore it. Maybe
	there should even be explicit support for such sets in
	util.c


	So a processing function will

		- take a "before" set as a parameter

		- store an "after" set that contains variables
                  that are initialized on all exits from the
                  node.

		- expressions also store "initialized-if-true"
                  and "initialized-if-false" sets.

		- return a set that contains initialized
                  variables on the path that falls through.

		- For the vast majority of nodes, the "after" set
		  is also the one that should be returned, but
		  those that transfer control will generally
		  return a "full" while storing something else.

	We will need to compute 'begin' and 'end' labels for
	if/for/while/do/switch. This may mean we can get rid of
	those for the nodes since a label will have its own label
	node.
		  
We are going to need a similar static analysis if we do the thing
where all values can be marked as errors. Also if we add
non-nullable pointers.

Note:
	if ((value :+ obj.value) == null)
		return;

These will need similar code, so some of it may be sharable.


    - Generate code with explicit initialization
    - Optimize dead stores away.
    - The optimizer can't be too aggressive; it must not optimize so
      much that the VM can't prove that variables really are
      initialized. 

    At the moment we simply rely on the optimizer to turn the code
    into something the VM can understand, but this is not viable long
    term.

  - Initialization check should probably be done after constant
    propagation.  Otherwise, things like
    
	if (i == 0 && (k = 100) != 0)
	{
		print k;
	}

    will not be allowed. Also:

    	 if (true)
	    k = 100;

         print k;

    That one might be a little more iffy. Or what about this one:

	if (true && k = 10)
		...;

    Possibly && should do something special if the first expression is
    constant and true. Similarly, || should do something if the first
    is constant false.

    Do we need to follow ECMA 334 here? Or can we get away with
    maintaining the state of each variable at each node:

    	  Assigned if stackpos=k is true
	  Assigned if stackpos=k is false
	  Assigned 
	  Unknown

    Doing this analysis on the graph gets too complicated because we
    need to keep track of the truth values of the whole stack. A way
    to do it may be to have two passes,

    	 init_check_expressions()
	 init_checK_graph()
 
    where init_check_expressions() is a tree walk that computes the
    initialization state of variables for expressions. The graph pass then
    issues INIT nodes, and the graph check does the data flow analysis.

    A similar issue will come up with the non-null check. We need to
    allow things like

	x = null;
	if (bah && (x = new Bah()))
	{
		/* dereference x */
	}

    Is there a way to generalize this "has property after true/false"?
    Maybe expressions (e) could contain a list of subexpressions that
    are evaluated if e is true/false. Then analysis for an if
    statement could look like

       analyze_true (expr)
       {
	   only walk sub-expressions that are guaranteed to be 
           evaluated if expr is true.
       }

       analyze_false (expr)
       {
	   only walk sub-expressions that are guaranteed to be
	   evaluated if expr is false
       }

    A possibly better thing to do might be to first generate the graph
    without generating code for evaluating expressions; instead just
    add them as separte "expression" nodes. [How about statement
    expressions though? - in fact what exactly happens if a statement
    expression has a goto in it?]

    	 y = k + [[ goto label ]] x;

    @label:
	print y

    Not very clear ... maybe it needs to go away and be replaced with
    definition expressions.

    There is actually a big problem here because expression *can* have
    gotos in them:

    	  B() -> int32 { goto blah; return 100; }

	  print 7 + B();

    which will cause problems because the "7" is left on the stack even
    as control goes elsewhere.

  - At the moment we directly change the nodes in optimize.c, this should
    be fixed with helper functions in graph.c (which should probably be
    split out in node.c). Things we need

    	  - delete nodes from the graph
    	  - ability to insert nodes after a node
	  - ability to change nodes into something else
	     (this can probably be accomplished by
	      combining the two others)

    What is it again that we need the ast's for? For nodes where we
    need the types, we should just have the types. The ast's will make it
    harder to copy nodes.

  - Find out if we can avoid having to do ast_type_spec_resolve() all
    over the place.
  - Move much of the stuff in CALL into a new PROLOG node that every
    function has. (There is a PROLOG node now).

  * OBJECT TYPE CHECKING
  - Proper type checking for object assignemnt
  - Probably need a distinction between class types and object
    types. The thing you put after "new" should have class type, but
    instances would have object type.
  - Also need to make a decision about non-nullable pointers.
  - Binary ops that work on objects need to be updated in the interpreter.
  - Generally, there is some thinking that needs to be done about 
    objects and type checking.

  - Liveness:

    We generate a bunch of temporaries when doing assignments. Those
    should be eliminated since they will very often be dead. 

  - peep:

 	do
	{
		Propagation
			- Copy propagation
			- Constant propagation
		Peephole optimization
		liveness analysis
	} while (changed);

    where peephole optimization will replace dead stores with pop's
    (among other things).

    We'll probably just have to fix up the offsets for dead
    variables. The graph stores pointers to definitions, so if we just
    change the offsets in the ast, the graph will automatically pick
    them up. 

    Basically, just run offsets() once more. Actually just run the
    offsets pass after all the optimizations.

    Of course, as an intra-procedural optimization we can't remove
    variables that have wider scope than the function we are
    optimizing. So variables need to know their enclosing definition,
    and if that isn't the function we are optimizing, then we can't
    declare them dead.

    Peephole optimization:

    	     node_t *peep_hole (node_t *node)
	     {
	        do {
		   node = do_peep (node, &changed);
		while (changed);

		if (node->next)
		   return peep_hole (node->next)
		else
		   return node;
             }

    will take a node and optimize it. Labels should be ref counted,
    and maintain a list of all their sources so that two adjacent
    labels can be collapsed.

  - For stuff like this:

    	a.x += <expr>

    where <expr> doesn't change a, we will generate

    	  load a					t = a
	  store tmp					t2 = t  
	  load tmp					t3 = t2
	  load_ind x					t4 = t3.x
	  <expr>   					t5 = expr
	  plus						
	  load tmp					t6 = t2	
	  store_ind x					t6.x = t5

    to eliminate tmp we will have to get the "load tmp" changed to
    "load a" at which point we can prove that tmp is dead and
    eliminate a lot of code. It should be reasonably easy to find out
    that tmp is guaranteed to be equal to a, but how do we determine
    which one to eliminate? Basically this is copy propagation. Ie.,
    how can we be sure that s/load tmp/load a/ is actually making
    progress? Because there is a termination function: the total
    distance between loads and stores becomes smaller

  - Variables that don't escape an activation record should be
    allocated on the stack. Need to figure out just how the stack
    is exposed (ie., is it 32 bits wide, can you get the address of it
    what about 64 bit values? What about 128 bit values?)

  - Move the reachability code into return-check.
    Consider consolidating init-check and return check.

  - Make ++ and -- syntactic sugar for +=. To make this work for
    postfix inc, we will need a statement_expression which is a
    statement followed by an expression. Ie.,

    	     i++           =>        t = i; i = i + 1; t
 
    and 

             ++i           =>        i = i + 1;

    A problem with this is typechecking. The desugared version may be
    accepted by the typechecker where the sugared version would
    not. Is this really worth the trouble? They already work ...

    (Adding temporary variables is a bit nasty since they are quite
     expensive; we should at some point make sure that variables that
     don't escape are allocated on the stack. This way we can actually
     allocate entire activation records on the stack - note that the
     outer pointer only escapes if an inner function is accessing
     variables from outer->outer)

  - This has interactions with the design of the VM since we want the
    code executed by the interpreter to be close to what the VM would
    run.

    The VM should ideally be untyped with type annotations added on
    top in their own segment. This is a lot more flexible for
    high-level compilers, and means the garbage collector can be
    written in bytecode.

    However, some issues that a statically typed bytecode format takes
    care of are now left to the high-level compiler. The most
    important is "what is the size of pointers". Is it 32 bits or 64
    bits? The HLL needs to know so it can compute layouts of
    structures etc.
    
    Making pointers 64 bit is more future-proof, but will also cause
    bloat on both 32 and 64 bit architectures. And 4G should really be
    enough for many people for a couple of years.

    32 bit pointers will work well on 32 bit architectures such as
    x86-32 and ARM. Even on 64 bit architectures, the overhead from
    converting a 32 bit value to a 64 pointer is not too bad,
    particularly if we can get away with mapping the heap in the
    lowest 4G of the address space. If we can get the heap 4G aligned,
    then converting is just a matter of or'ing in a fixed set of bits
    on top of the 32 bits. The stack may be a bit of a problem since
    unaligned access is so expensive. So what will happen if you push
    a 64 bit integer on a 32 bit stack? Maybe just suck it up and do
    two reads. Hot code will be jit-compiled anyway and we should be
    able to allocate 64 bit integers in registers there.

    Or we could say that the stack is 64 bits while keeping pointers
    32. Or we could say that everything is 64 bits.

    Alternative approaches: 
    		- Statically typed bytecode.

		- Adding a ptrsize bytecode.  The idea here would be
		  to dynamically compute the pointer size every time
		  it was needed. This is less crazy than it sounds
		  since

			(a) functions that return the size of
			    particular structure can be generated, so
			    we don't get too much code bloat.

			(b) Such functions would be inlined and
			    reduced to constants by the jit compiler.

    Of course it is also necessary to decide what size floats
    are. Probably only 64 bits - single precision can be added

    Explicitly allowing 32 bit aligned 64 bit access is probably the
    best.

    The VM will need to know what types it should use. Do we add the
    floating point operations or what? If the VM can't statically
    check anything, then yes, we do need typed ops.

  - Maybe split out the graph stuff into node.c
    	  - node.c has utilities
    	  - graph.c builds the graph
	  - flow-check.c checks initialization and return
	    		 (and later null use).

  - typedefs

	- types can be arbitrary identifiers
	- arbitrary identifiers can be shorthands for other types.

	type int_func = fn int32 -> int32;

- Expressions with goto and the spaghetti stack is now done. However,
  if we ever add support for statement expressions, we may need to
  make it so that goto always sets the stack to NULL.

- Calling convention:

    /* On top of the stack is the closure, followed by all
     * the arguments
     *
     * What we need to do:
     *
     *    - find out what function we should be running
     *    - allocate an environment
     *    - copy stuff from the stack to the environment
     *    - push the current environment
     *    - push the 'return address'
     *
     * Should 'current env' and 'return address' be stored in
     * the new environment? If the new environment becomes a
     * closure, then it will be wasted space; on the other
     * hand it avoids annoying stack manipulation with the
     * return value.
     *
     * Of course, the return value could also be stored in
     * a (64 bit) register. For struct returns, the convention
     * could be that the return register would be initialized to
     * a pointer to the location before the call.
     *
     * The call sequence would then look like this (for a something
     * that returns a struct):
     *
     *       push size of retval
     *       push RV
     *       rv = sp			// stack grows down [1]
     *	     push args
     *       push function
     *       call
     *       pop args
     *       pop rv
     *       <return value is now top of stack>
     *
     *
     * [1] We may not want to make the assumption that the stack is
     * addressable. If we do, we may not want to assume that the
     * stack grows down. Although we will almost certainly need the
     * ability to take the address of variables on the stack anyway, eg.
     * for implementing C.
     *
     * It is important that bytecode behaves identically on different
     * types of machines. (Ie., if it breaks on obscure architectures,
     * then it should also break on x86, so that we don't get architecture
     * specific bugs). This probably requires that the stack direction
     * is fixed in one direction. Can this be implemented efficiently
     * on upwards machines?
     *
     */

- Unreachable code. What happens is that the "goto done"
    after the else-part of an if statement can be unreachable if the
    else part ends with a goto. There are some issues though. In this
    code:

    	 for (i = 0; i < n; ++i)
	 {
		break;
	 }
 
    ++i is unreachable. Should we report this? gcc does actually
    report it. What about when it's empty:

    	  for (i = 0; i < n ; )
	  {
		break;
	  }

    internally we generate a "true" expression there, which would be
    reported as unreachable. In this case:

    		 if (true)
		 {
		 }
		 else
		 {
			return;
		 }

    The "goto done" statement can never be executed since it follows
    the return.  How do we prevent that from triggering reports?
    Similar issues may arise basically anywhere we generate code that
    follows a user-provided goto.

    Can we separate the nodes into 'user generated' and 'compiler
    generated' and only report the user-generated ones? We probably
    can, but we also need to mark compiler generated expressions as
    such so that the corresponding nodes can get marked correctly.

    A possibility may be to mark some nodes as "should be reached",
    then if they are not reached, complain. Basically, the first node
    of each statement and expression would me marked this way.

    Unreachable nodes should probably be complained about only if they
    are preceded by a reachable node. That should prevent most
    cascading reports. Or, when a node has been reported unreachable,
    run the reachability algorithm on it, then continue to the next
    node.

    There is no "unreachable" field in program anymore. If/when we
    reinstate this check, just use ast_enclosing() and store a list of
    all nodes, reachable or not, then do a pass and complain about the
    unreachable ones.

- Explicit tail calls.

  In some cases it is useful to rely on tail call optimizations for 
  correctness (ie., it won't overflow the stack). Maybe having the ability
  to say

	goto some_function (x, y, z);

  that would jump to that function and return immediately afterward. It
  would be semantically equivalent to 

	return some_function (x, y, z);

  but the language would guarantee that there is no overhead
  associated with the call. It could make threaded interpreters
  possible if some_function could be a function variable.

  Could this be generalized to allow coroutines?

- We probably should have local type inference. C# 3.0 has some good stuff,
  and it definitely would make lambda expressions nicer to look at.

      - As far as I can tell, in C# 3.0 the only thing you can do to a
        lambda expressions is to convert it to a delegate type; ie.
	you can't directly apply it. This simplifies type inference
	since there is always a list of parameter types. Ie., you
	don't need to infer the type of the body of the expression.

      - Do we also want a "let" statement? Probably not, it's
        equivalent to 

	      {
		x: var = new Whatever();

	      }

	Though:

	      let (cr <- drawable.get_cairo())
	      {
		cr.move_to();
		cr.rectangle();
		cr....
	      }

	has some appeal.

	Also, if we have non-nullable types, accessing fields requires
	something like it:

	      if ((cr := drawable.get_cairo()) != null)
	      {
			...;
	      }

      - Maybe "var" should just be empty, like

      	    x: = new Whatever();

        Which could also be written as

	    x := new Whatever();

        In for loops:

	   for (i := 0; i < 100; ++i)
	   {
	   }

	Maybe a bit too cute though.

        In foreach loops:

	   foreach (e: in employees)
	   {
	   }

	"<-" is also a possibility as "type inferred declaration". 

	   for (i <- 0; i < 100; ++i)
	   {
	   }

      - Implementation of type inference may be as simple as simply
        passing a "inference target type" to each type checker function.
	Then whenever a type needs to be inferred, we know what type
	to shoot for. If the type is NULL, then type inference can't
	work at that particular point.

	For example a call expression would not be able to generate
	a target type, which means inferred lambda expressions can't
	be called directly.

        Assignments and coercions would generally generate an
	inferable context.

      - It is desirable to have inferred types even without
        initialization.  Ie., sometimes it's just not very convenient
        to have to come up with an initializer, especially if the type
        is not nullable.

	Maybe all assignments to that variable could be looked at, and
	the best possible type selected. Example:

	     x: ;

	     if (something())
	     {
		x = new Fish();
	     }
	     else
	     {
		x = null;
	     }


         would ideally cause x to get the inferred type Fish?.

	 So, for assignment expressions:

	 - if left hand doesn't have a type, set it to
	   the type of the right hand, but marked with "inferred".

	 - if left hand has an inferred type T, and the type of the
	   right hand is NullType, then infer the type "T?"

	 The problem with this approach is that sometimes this will
	 cause us to infer a too specific type

	       x = new Fish();

	       print x;		// ok since x is non-nullable

	       x = null;	// ok, since the type of x is infered

	       print x;		// not ok since x is now nullable

	 On the other hand this is how the flow analysis is supposed
	 to work anyway. Basically, nullable and non-nullable types
	 should be indistinguishable wrt. to the type checker.

	 So inferring should just always produce a nullable type; the
	 flow analyzer can sort things out later.
	 
	 Maybe nullability should only be a question for interface
	 types. Ie. an interface can declare that some pointer can't
	 be null, but local variables can always be null. Field
	 variables and arrays are probably always nullable as a flow
	 analysis is going to have a hard time proving them non-null
	 across unrelated method calls. (But then, when are you
	 allowed to dereference them?)

	 Possibly nullable fields should never be inferred as
	 non-null. Instead the user can just use a local variable. If
	 we allow them in if statements it's not that horrible. Ie.,
	 do

	       if (tmp <- obj.a)
		       bah (tmp);
	
  	 instead of

	       if (obj.a)
	       	  bah (obj.a);

	  Keep in mind that the code between checking and calling the
	  function really *could* change obj.a, so we are potentially
	  preventing real bugs.

	  We'd also want

               if (t1 <- obj.a && t2 <- obj.b && t3 <- obj.c)
	       	  bah (t1, t2, t3);

          In some cases we'd probably want to also check that obj is
          non-null:

	  if (o <- obj && t <- o.a)
	     bah (t);

	  of course if obj is a local, then this is fine:

	     if (obj && t <- obj.a)
	     	bah (t);

	  When checking a long chain:  o1.o2.o3.o4.o5.a:

	       if (o1 && o1.o2 && o1.o2.o3 && o1.o2.o3.o4 && o1.o2.o3.o4.o5 && o1.o2.o3.o4.o5.a)
	       {
		   bah (o1.o2.o3.o4.o5.a);
	       }

	  it was pretty stupid in the first place, but it highlights
	  the need for non-null field variables, with the associated
	  issue of initialization.  We will probably have to prevent
	  constructors from calling virtual methods in "this".

	  With the locals, it looks like this:

	       if (o <- o1 && o <- o.o2 && o <- o.o3 && o <- o.o4 && o <- o.o5 && a <- o.a)
	       {
		  bah (a);
	       }

	  If we allow the same variable to be declared multiple times.
	  Maybe there should be syntaxtic sugar for checking a chain
	  of nullable fields:

		if (o <- o1&.o2&.o3&.o4&.o5 && a <- o.a)
		   bah (a);

          In foreach:

	  get_files (...) -> array[string!]!
	  {
	  }

	  foreach (s <- get_files())
	  {
		bah (s);
	  }

- Dependent types.

  Integers that are confined to the size of an array?  Arrays can
  never be dereferenced by an integer that is not guaranteed to fit
  within it?

- Can we get to the point where runtime exceptions *never* occur?

  - Division by zero?
  - Out of memory?

- Integers 

  Maybe it's worthwhile to have bigints built into the language (as
  opposed to the library). That way type promotion for integers
  becomes really simple: Just promote to the closest type that
  contains both.

- Precedence:

  At the moment Oort inherits the broken precedence from C where ==
  and >= have higher precedence than &, | and ^.

  This means that

       	     a == b & c

  will be parsed as (a == b) & c, which can never be legal since
  (a == b) is a bool. Hence changing the precedence would 
  not cause any confusion.

  It is probably a bad idea to make &, | and ^ have a higher
  precedence than >> and << since a << b & c is more usefully parsed
  as (a << b) & c.

- Test suite

- Sane error, warning, and debug output.

- Maybe s/type/kind/g whenever type means "type of ast node", to
  prevent confusion with type_specs. Maybe also rename kind ->
  st_kind/ex_kind

- in the type checker, consider inserting cast nodes for expressions
  where widening is going to take place. This should reduce the amount
  of runtime type checking in the interpreter.

- Consider adding new binary ops PLUS_DOUBLE, PLUS_INT etc.  That will
  make the interpreter and code generator simpler.  Then again maybe
  it's not worth it.

- How to deal with errors in the parser. One possibility is to mark
  tokens that have successfully been parsed, then if parsing fails,
  report the first token without such a mark.

- for-, while- and if-statements should allow declarations, at least
  in the first expression

  Note that 

       for (a; b; c) d; 

  is *not* equivalent to 

       a; while (b) { d; c; }

  since if d contains a "continue" (which we will want to support at
  some point), c will not be executed in the while statement, but it
  will in the for statement.

  However, I don't see any reason "a" could not be treated taken out
  and the for expression reduced to two expressions. Ie.,

      for (i: int32; i < 20; ++i)
      	  ;

      would become

      {
	i: int32;
	for (; i < 20; ++i)
	{
		;
	}
      }

- A less stupid name?

  - Zinc? already used for some other software (see zinc.com)
  - Boron? sounds like an insult, which is good. boron.com is
       available.  People could take other insults and replace the
       first letter with b: bool, bucktard, bimbecile, bimbo, bretin.


- "is" and "as"

  Lifted from C#.


- Much casting happens as a result of parsing binary streams. Can we
  add language support to help with that?

	uint32 x = b1 + b2 * 256 + b3 * 256 * 256 + b4.
	uint32 y;

	int i;

	bparser
	{
		x: uint32;
		p: enum { X, Y, Z };

		align 32;
		
		y: array[struct bah] (x);

		switch (p)
		{
		case Y:
			uint32: pp;
			uint32: xx;
			uint16: x;
			uint16: z;

			{ little_endian;

				


			}
			bparser LE
			{
			


		for (i = 0; i < x; ++i)
		{
			uint y;
			
		if (x > 100) 
		{
			uint32 y;
		}
		else 
		{
			int32 z;
		}
	}	

	


DONE:

* Expressions with goto in them

  A simple example is

      F() { goto blah; }

      print 7 + F();

      @blah:;

  where we jump to blah, leaving 7 on the stack.

  There is another case, captured in popbug3.nl, where we keep
  returning from the same function. Each time the result is added to
  something popped from the stack. This results in a stack underflow.

  Part of the solution will have to be to keep a reference to the
  expression stack. This of course implies that popping the stack can't
  actually remove the stack entries.

  A different problem is if the stack references a variable. Should
  that variable be evaluated every time? My intuition says no. Consider

       ret: label = null;

       x = 0;

       F() { ret = back; @back: return 10; }

       print x + F();

       x++;

       if (x < 100)
       	  goto ret;

   if you do this, F() will return 100 times, but the evaluation of
   the 'x' in 'x + F()' will be skipped every time.

   It seems the expression stack will have to become a tree with heap
   allocated entries. An environment will then contain a pointer to a
   node of this tree.

   What does this mean for the bytecode? For example, an ADD operation
   should now take the two values on top of the stack and create a new
   value whose 'next' pointer is the same as the next pointer of the
   second value on the stack.

   Should this be done at the bytecode level? It may be that there
   should be separate 'dynamic' versions of all the stack ops. These
   might operate on a leaf pointer on the stack.

   In the case where we can detect that an expression doesn't escape,
   the array based stack could then be used. Is detection as simple as
   there being no function calls in the expression? And no
   statement-expressions, presumably. Not sure. This will have to be
   considered an optimization.

   With these changes, will it be possible to move the return address
   back onto the 'stack'? If so, the contents of an environment will
   look like this:

   	env_t *outer;
	env_t *prev;
	stack_t *stack;
	[variables]

   A label consists of a code pointer, an environment, and a stack
   pointer.  Jumping to a label consists of activating the
   environment, resetting the stack pointer, and then going to the
   code pointer.

   Is is in fact going to be the case that a label will *always* have
   a stack height of zero? Then jumping to a label just needs to set
   the stack pointer to NULL. Jumping into the middle of an expression
   that hasn't been activated seems ill-defined, which would indicate
   that the (expression) stack height is indeed NULL. (This probably
   then precludes having the return pointer stored on the stack).

   Preliminary conclusions:

   - expression stack must become a heap allocated tree
     - there is a global current_stack

   - environments need to contain
     - outer_env	[pointer to containing environment]
     - prev_env		[the environment to restore after return]
     - return address	[where to jump when returning]
     - return stack     [stack to restore when returning]

   = Expressions:
     - Operate on current stack

   = Call:
     - Allocate new env
     - Store current env as prev_env
     - Store closure env as outer_env
     - Store current stack as prev_stack
     - Set stack pointer to NULL
     - Set return address to current address
     - Jump to function

   = Returning:
     - push the return value on top of prev_stack
     - restore outer environment
     - set stack to prev_stack
     - jump to return address

   = Generating a label:
     - push env and code pointer

   = Goto:
     - restore env
     - set expression stack pointer to NULL
     - goto code pointer

  - consolidate while and for into a new "loop" that takes two expressions,
    a test, and an increment. then

    for (e1; e2; e3) s;      =>       e1; loop (e2; e3) s;
    while (e1) s;            =>       loop (e1; true) s;

    break exits the loop, and continue evaluates the increment
    before testing.

    Unfortunately do/while doesn't fit here. Probably still worth
    doing though. hmm 
    
	do s while e;           =>  s while (e) s  =>  
	goto l; while (e) l: s  => goto l; loop (e, true) l: s;

    requires a jump into a loop though.

    Can we use do/while for everything?

    while (e) s;    =>       do { goto l;  s; l: } while (e);

    Or a new construction:

       loop (e, inc) s;

    which executes s, then tests e, then if e is true, incs, and restarts.

    do s while (e)      =>    loop (e, true) s;
    for (e1;e2;e3) s	=>    e1; goto l; loop (e2; e3) { s; l:; }
    while (e) s;	=>    goto l; loop (e; true) { s; l:; }

  * Expression variables
    - Make sure variables defined in an expression survive
    - Add scope expression whose only purpose is to limit scope of
      variables, but still allow values to survive:

      		 struct scope_expression
		 {
			symbol_table *table;
			expression_t *expr;
		 }
    - 

  - see if the offsets pass can't be done with a generic tree walk
      - possibly, but there are some subtle considerations. Not
        worth it.
  - We produce false reports of uninitialized variables at the
    moment. This is because the list_predecessors() doesn't list
    predecessors for the callee nodes.  The solution here may be to
    have separate prolog and fun-ref nodes.

    Or maybe better, just somehow special-case it in the
    init-check. Do we need the feature elsewhere?

    No, the separate nodes are better. We can delete them in the
    optimize path so they don't interfere with the peephole patterns.

  - Remove nop is crack at the moment
    Removing nodes is horribly complicated because the successor and
    predecessor arrays have to be updated. Think it through.
    	One possibility is to completely ignore those arrays, and
    keep a separate ref count for labels. That's pretty simple.
        There is also the "unreachable" node in program which is
    annoying as it keeps things alive. Also the recursive 
    remove_nops() is too complicated. Just do a simple for-loop and
    with a saved next pointer. 
    	 Maybe succ/pred could be confined to init-check? We need
    it for breadth-first though.
        It's annoying that we lose program->exit/program->unreachable,
    even though it's not actually harmful.
    	 optimizing should actually work reasonably now.

  - allow constant expressions in case statements.
    	  - Should be done by splitting the expression evaluator out
	    from the interpreter. This will also be useful for the
	    peephole optimizer
  - Find out exactly when identifier types should get resolved. Note
    that they are needed as part of argument lists. Note defs.nl
    crashes.  (Yes, they are needed as part of argument lists, but in
    the gathering phase (pass1) they don't have to be resolved. So we
    can do it as a pass between pass1 and pass2).
  - A simpler solution might be to just have a  prepare_lvalue(expr) that
    would generate the necessary temporary variables and return an expr
    making use of it. Eg.

    	   birnan().i += 200

    For a compound assignment like this we first make a statement:

    	ast_statement_t *statement;
	ast_expression_t *safe_expr;

	prepare_lvalue (expr, &statement, &expr);

	return ast_expression_new_statement
	       (statement,
			expression_new_assign (
			     safe_expr, 
			     ast_new_binop (PLUS, safe_expr, right)));		

    One potential problem is that the temporary variable would have to
    have its type inferred as its not available at parse time. So
    local type inference may be a prerequisite. Or we could add a "get
    your type from this expression" type. (That would be sufficient
    for this problem, but possibly not for local type inference where
    the expression to get the type from is not necessarily known at
    parse time).

    However,
    liveness analysis is easiest to do on the graph, but eliminating
    variables will affect the offsets which are calculated before the
    code is generated. (Actually, we could split offsets into 'levels'
    and 'offsets') The only thing we copy into the nodes are the 'levels'.

    Or instead of storing levels, we could store expressions ... (done)

  - Find out how to generate code for dot expressions as lvalues.

    There is the beginning of this now. Remaining to do still:

    	  - Generate the correct types for temporaries (currently
                hardcoded to Link).

	    This will require a new "Take the type from this
	    expression" type. Or maybe the expression in question
	    should have a pointer to the variable to whom it is
	    supposed to donate its type.


          - Add a new store_ind bytecode similar to the load_ind, and
            make the various lvalue expressions use it.

    Issues:
	To leave a copy of the value on the stack, we will have to duplicate it somehow.
	Ie.,

	tmp.x = <expr2>

	<expr2>
	dup 
	tmp
	store_ind

    we can do this safely since we know the evaulation of "tmp" will not have any side
    effects, nor will the value of tmp be affected by <expr2>. 

    Maybe add a new ast_lvalue_t node, then have the parser or the
    prepare pass convert expressions into lvalues as required.

    An lvalue could contain a statement to be executed first. Ie., 

       <complicated expression>.id

    would be converted to 

    	  statement_t s;
	  
	  union { dot, variable }

    generating code for an assignment would then be

    	       lvalue.code  (code for s);

	       lvalue.load (just treat the dot/variable normally)
	       lvalue.store 

    birnan().i += j  =>   lvalue (t = birnan(), t.i) = 

  - Add null value (and probably null type too).

  - Insert init nodes for class variables (just don't complain about fields)

  - Implementing methods as closures. The important observation is that for a method,
    the 'this' pointer is actually just the outer pointer. So for this case:

    	blah.foo(a, b, c);

    we need to generate a closure with "blah" as the environment and "foo" as the
    function. So object layout has to be with "outer" as the first pointer, and 
    vtable as the second.one.

    (Of course for objects without an outer, we can omit it, with a
    bit extra complexity in other places).

  - Make the interpreter graph (and stack-) based
	 - should be faster
    	 - can support gotos
	 - closer to be able to generate machine code.
    Nodes should probably get types:
    	 - IF
	 - BINOP
	 - UNOP
	 - LABEL
	 - GOTO
	 - LOAD_ID
	 - etc.
    with statically determined successors. LOAD_ID would have a successor
    called 'entry', that would be used in the init-check. It may also
    be worthwhile to say that LABEL nodes are the only ones that can
    have more than one sucessor. And IF nodes are the only ones that can
    have more than one successor. 

  - Consider making the compound-assignment operators real ast nodes. We
    would then only have to compute the left-hand once. The current
    sugar scheme may even be incorrect according to the java spec.

  - Find out why reachability broke (unreach2.nl)
 
  - Make a new ast_is (common_type, specific_type) so we can write

      	 if (ast_is (AST_EXPRESSION, AST_IDENTIFIER_EXPRESSION))
	    ...;

  - add a child list to ast_common.
    Should make it possible to delete a ton of tree-walking code.

  - Make sure the function pass walks all of the tree
  
  - Make graph.c use "next" nodes
    - 'next' nodes are automatically added as successors, except for
      return and goto nodes.
  - Check that the graph passes (return and init-check) work

  - Fix assign compounds. Currently the lvalue is evaluated twice. 
    Eg.    
    	   blah().x += 100

    will cause blah() to be called twice.

   The solution is probably to just have a new assign_compound_expression_t
   with a binary operator. 

  - Return check is completely broken at the moment, since
  	   - it doesn't recurse into expressions, so lambda functions
  	     do not get checked

	   - it ignores gotos and labels.

	   - it should probably be graph based

	   - "If exit has a predecessor which is reachable and 
              not a return, then complain" should be right. 

	   - Need list of functions. Maybe just add a new pass that
	     gathers various misc stuff?

  - Is there any good reason that labels have a 'child' statment?
    - don't think so.

  - Add initialization for variables
    x: int32 = 30; can be syntactic sugar for x: int32; x = 30;
    x, y: int32 = 40, 50; can be syntactic sugar for 
    x: int32; x = 40; y: int32; y = 50;
    which will also prevent weird stuff such as  x, y: int32 = y, x;

  - Split unary expressions into their own ast_unary_expression_t type

  - allow function valued variables
    - will require full closure support. A closure is a pointer to
      an ast_function_t and a pointer to an environment. When the
      closure is invoked, a new environment for the function is
      created and the 'outer' pointer is set to saved environment.
      Then the function body is interpreted.

  - "bool" or "boolean"? 
  	 "bool" is fine.

  - get rid of crackrock ast_statement_definition_t node

  - allow nested functions
    - should hopefully be fairly simple with the environment
      level code above.
  - allow mutual recursion
    - symbol checker needs to be two-pass:
      - first gather all functions names
      - then look at the function bodies
    - type checker needs to be two-pass
      - first generate the types of all functions
      - then type check the function bodies
  - allow function definitions to be mixed with
    global variables

    To do this a new ast node that can contain a function or a statement
    will be needed. And classes, when those are added. When things
    can be nested, this thing will be allowed everywhere a statement
    is allowed. Maybe call it a definition, and have

       definition -> declaration
		  -> function
		  -> class
		  [->statement]

       statement [-> definition]
       		 -> ...;

    which would also allow us to get rid of the symbol_t type and just store a
    pointer to a definition.

    - requires two-level environments, so the offsets pass should
      compute the env level. The interpreter should chase the 'outer'
      pointers as necessary.

      Declarations will store the level on which they were declared,
      and either

	- the interpreter can keep track of the current level

      or

        - each identifier can know the level on which it is used.

      The second one preferable. While it uses more memory, it is the
      correct thing to do in a compiler.

      Based on this information the interpreter can track env pointers
      until it is at the right level.

  - Return checking is broken at the moment

    	   - it doesn't detect if part1 of a compound statement has
             the required return in it.

  Should split flow.c into several files.

- First class labels
 
  Is this actually that complicated to do? A first class label would
  be a code pointer and an environment. When you goto such a label,
  the environment is restored and control is transferred to the code
  pointer.

  This subsumes coroutines and continuations.

- Flow check

  - Required initialization:

    - Zeroth, compute a list of all function definitions in the program - 
      maybe as part of the parser.

    - First, for every function body compute a list of
      uninitialized outer variables. That is, variables that are
        - defined outside the function
	- used in the function without being initialized by the
          function body (disregarding any further nested functions)

    - Second, for every function compute a list of other functions that it
      references. Essentially walk the identifiers used in its body, and
      list those that refer to functions.

    - Third, walk the tree and do normal initialization checks. At every
      point in the program maintain a table of uninitialized variables.

      Every time a function name is referenced
      
	- Walk the graph of referenced functions from that function
	
	- For every referenced function, if any variables are in both
	  the list of uninitialized variables in the function and in
	  the maintained table of uninitialized, report an error.

      Every time a variable name is referenced

        - Just check that it is not in the table of uninitialized variables.

  Figure out how required local variable initialization interacts with 
  nested function. For example:

  	    foo -> int32
	    {
		x: int32;

		bar();

		x = 100;

		bar -> int32
		{
		    return x;     /* use of initialized variable 
		          	   * that we don't catch 
				   */
		}
	    }

  With closures this could get more complicated. Can we require that a
  function is not used for _anything_ until it is known that all
  variables it references are initialized? Or do we need to bite the
  bullet and initialize locals to 0?

  The conservative check should be fairly easy to do:
      - Maintain table of initialized variables as we do now
      - Whenever the name of a function is used (for anything) check
        the function body for references to uninitialized variables.
  won't work due to recursion. Maybe this:

      - For every function body generate a list of variables
        referenced

      - Do this transitively, so if a function references other
        functions, those variables are also included. Note that
        functions defined in the function itself should not be
        included.

      - Then, maintain table of initialized variables. When a function
        name is used check the table against the list of variables.
	   Actually the function may initialize the variable
	itself. If it does that, then it's always okay for it to use
	it. So the list of variables should be those that it uses
	uninitialized.

- Rethink scope_table_t and what it can be used for.
  We are sort of abusing it in init-check.c, and it was always a bit
  iffy the way scope_table_insert() just assumes symbol table semantics.
     Maybe the init table should just be its own data structure and 
  scope_table folded back into symbol.c

  - Simplify graph.c to walk the parent chains instead of
    passing a ton of nodes around. unreachable should be
    stored in program_t.

  - There is a bug in the optimizer. callcc.nl produces different results
    depending on whether it's run with optimization turned on.

  - Fix crasher.nl (actually this was just a bug in the program,
         generating NULL pointer exceptions is really needed)