[incremental] Patch: FYI: implement anti-dependencies

[Tom Tromey <tromey at redhat dot com>]

I'm checking this in on the incremental-compiler branch.

This patch implements anti-dependencies.  It also changes dependencies
from being per-hunk to being per-decl.

Anti-dependencies are needed so that we can avoid re-using a parsed
hunk if the current context conflicts with what the hunk needs.  For
instance if we see:

    struct a;
    struct a { contents };

and then compile:

    struct a;
    struct a { other contents };
    struct a { contents };

... we don't want to re-use the third line here -- we want to parse it
an emit an error.  With the old dependency scheme we would reuse this,
because we reused all its dependencies.  With the new scheme we will
have a dependency on the binding of 'a' and avoid reuse.

Now that dependencies are per-decl we can contemplate implementing
"semantic dependencies".  The idea here is that we can reuse a hunk if
the bindings in the current context are ABI-compatible with the hunk's
dependencies.

That is for later, though.  I think next I have to fix the decl
look-ahead code to understand K&R-style function definitions.
Unfortunately this means abandoning the current "purely lexical"
approach and doing something closer to real parsing.

Tom

ChangeLog:
2007-11-15  Tom Tromey  <tromey@redhat.com>

	* c-parser.c (struct hunk_binding) <prereqs>: Changed type.
	(c_parser_lookup_callback): Record name/value pairs, not hunk
	signatures.
	(start_new_parsed_hunk): Update.
	(traverse_check_prereq): Update.
	(struct prereq_traverse_data): Removed.
	(c_parser_lex_all): Handle empty files.
	* c-tree.h (lookup_name_no_callback, lookup_tag_no_callback):
	Declare.
	* c-decl.c (lookup_name_no_callback): New function.
	(lookup_tag_no_callback): Likewise.

Index: c-tree.h
===================================================================
--- c-tree.h	(revision 130053)
+++ c-tree.h	(working copy)
@@ -446,7 +446,7 @@
 extern void c_parser_note_smash (tree, tree);
 extern bool object_in_current_hunk_p (tree);
 extern tree c_parser_find_binding (tree);
-extern void c_parser_lookup_callback (tree);
+extern void c_parser_lookup_callback (tree, tree, bool);
 
 /* True if this decl or type has been smashed.  */
 #define C_SMASHED_P(T) TREE_LANG_FLAG_5 (T)
@@ -537,6 +537,9 @@
 extern struct c_declspecs *declspecs_add_attrs (struct c_declspecs *, tree);
 extern struct c_declspecs *finish_declspecs (struct c_declspecs *);
 
+extern tree lookup_name_no_callback (tree);
+extern tree lookup_tag_no_callback (enum tree_code, tree);
+
 /* in c-objc-common.c */
 extern int c_disregard_inline_limits (const_tree);
 extern int c_cannot_inline_tree_fn (tree *);
Index: c-decl.c
===================================================================
--- c-decl.c	(revision 130053)
+++ c-decl.c	(working copy)
@@ -2862,7 +2862,10 @@
   int thislevel = 0;
 
   if (!b || !b->decl)
-    return 0;
+    {
+      c_parser_lookup_callback (name, NULL_TREE, true);
+      return 0;
+    }
 
   /* We only care about whether it's in this level if
      thislevel_only was set or it might be a type clash.  */
@@ -2878,7 +2881,10 @@
     }
 
   if (thislevel_only && !thislevel)
-    return 0;
+    {
+      c_parser_lookup_callback (name, NULL_TREE, true);
+      return 0;
+    }
 
   if (TREE_CODE (b->decl) != code)
     {
@@ -2895,11 +2901,24 @@
     }
 
   if (B_IN_FILE_SCOPE (b))
-    c_parser_lookup_callback (b->decl);
+    c_parser_lookup_callback (name, b->decl, true);
 
   return b->decl;
 }
 
+/* Like lookup_tag, but don't call the parser notification callback.
+   This should only be used by the reuse mechanism itself.  */
+tree
+lookup_tag_no_callback (enum tree_code code, tree name)
+{
+  struct c_binding *b = I_TAG_BINDING (name);
+
+  if (!b || !b->decl || TREE_CODE (b->decl) != code)
+    return 0;
+  return b->decl;
+}
+
+
 /* Print an error message now
    for a recent invalid struct, union or enum cross reference.
    We don't print them immediately because they are not invalid
@@ -2927,12 +2946,24 @@
   if (b && !b->invisible)
     {
       if (B_IN_FILE_SCOPE (b))
-	c_parser_lookup_callback (b->decl);
+	c_parser_lookup_callback (name, b->decl, false);
       return b->decl;
     }
+  c_parser_lookup_callback (name, NULL_TREE, false);
   return 0;
 }
 
+/* Like lookup_name, but don't call the parser notification callback.
+   This should only be used by the reuse mechanism itself.  */
+tree
+lookup_name_no_callback (tree name)
+{
+  struct c_binding *b = I_SYMBOL_BINDING (name);
+  if (b && !b->invisible)
+    return b->decl;
+  return 0;
+}
+
 /* Similar to `lookup_name' but look only at the indicated scope.  */
 
 static tree
@@ -2944,9 +2975,10 @@
     if (B_IN_SCOPE (b, scope))
       {
 	if (B_IN_FILE_SCOPE (b))
-	  c_parser_lookup_callback (b->decl);
+	  c_parser_lookup_callback (name, b->decl, false);
 	return b->decl;
       }
+  c_parser_lookup_callback (name, NULL_TREE, false);
   return 0;
 }
 
Index: c-parser.c
===================================================================
--- c-parser.c	(revision 130193)
+++ c-parser.c	(working copy)
@@ -183,6 +183,10 @@
 
 static void create_hunk_binding_map (void);
 
+/* A sentinel value used to indicate that no value has been set in a
+   hunk prerequisite.  */
+static GTY (()) tree hunk_binding_sentinel;
+
 /* Initialization routine for this file.  */
 
 void
@@ -213,6 +217,9 @@
     }
 
   create_hunk_binding_map ();
+
+  /* Any new tree value is ok here.  */
+  hunk_binding_sentinel = tree_cons (NULL_TREE, NULL_TREE, NULL_TREE);
 }
 
 /* The C lexer intermediates between the lexer in cpplib and c-lex.c
@@ -745,8 +752,8 @@
   location_t location;
   /* Map names to bindings.  */
   htab_t GTY ((param_is (struct hunk_binding_entry))) binding_map;
-  /* Set of all prerequisite hunks.  */
-  htab_t GTY ((param_is (struct hunk_binding))) prereqs;
+  /* Set of all prerequisite bindings.  */
+  htab_t GTY ((param_is (struct hunk_binding_entry))) prereqs;
 };
 
 /* A hunk set is a collection of hunk binding structures.  In a given
@@ -874,7 +881,7 @@
    registers a prerequisite for the resulting object's hunk with the
    hunk currently being parsed.  */
 void
-c_parser_lookup_callback (tree result)
+c_parser_lookup_callback (tree name, tree result, bool is_tag)
 {
   struct hunk_binding *binding;
   /* We'd like this to be an argument to this function, but that
@@ -883,17 +890,42 @@
 
   if (!parser || !parser->current_hunk_binding)
     return;
-  binding = find_hunk_binding (result);
+  binding = result ? find_hunk_binding (result) : NULL;
 
   /* We might be using something declared in the current hunk -- don't
-     register that fact.  */
-  if (binding && binding != parser->current_hunk_binding)
+     register that fact.  Otherwise, record the name/value pair in our
+     prerequisite list.  When evaluating prerequisites we look to make
+     sure that all listed names have the indicated value.  FIXME: we
+     also need to handle NULL values properly, since we may do a
+     "failing" lookup.  */
+  if (!result || (binding && binding != parser->current_hunk_binding))
     {
       htab_t prereqs = parser->current_hunk_binding->prereqs;
-      struct hunk_binding **slot
-	= (struct hunk_binding **) htab_find_slot (prereqs, binding, INSERT);
-      /* FIXME: assert that slot is empty? */
-      *slot = binding;
+      struct hunk_binding_entry key, **slot;
+
+      key.name = name;
+      slot = (struct hunk_binding_entry **) htab_find_slot (prereqs, &key,
+							    INSERT);
+      if (!*slot)
+	{
+	  *slot = GGC_NEW (struct hunk_binding_entry);
+	  (*slot)->name = name;
+	  (*slot)->symbol_binding = hunk_binding_sentinel;
+	  (*slot)->tag_binding = hunk_binding_sentinel;
+	}
+
+      if (is_tag)
+	{
+	  gcc_assert ((*slot)->tag_binding == hunk_binding_sentinel
+		      || (*slot)->tag_binding == result);
+	  (*slot)->tag_binding = result;
+	}
+      else
+	{
+	  gcc_assert ((*slot)->symbol_binding == hunk_binding_sentinel
+		      || (*slot)->symbol_binding == result);
+	  (*slot)->symbol_binding = result;
+	}
     }
 }
 
@@ -924,10 +956,11 @@
     = htab_create_ggc (table_size,
 		       hash_hunk_binding_entry, eq_hunk_binding_entry,
 		       NULL);
-  parser->current_hunk_binding->prereqs = htab_create_ggc (table_size,
-							   htab_hash_pointer,
-							   htab_eq_pointer,
-							   NULL);
+  parser->current_hunk_binding->prereqs
+    = htab_create_ggc (table_size,
+		       hash_hunk_binding_entry,
+		       eq_hunk_binding_entry,
+		       NULL);
   parser->current_hunk_binding->location = location;
 }
 
@@ -1127,7 +1160,7 @@
 /* Lex the entire file into the parser's buffer.  */
 
 static void
-c_parser_lex_all (c_parser *parser, c_token *initial)
+c_parser_lex_all (c_parser *parser, c_token *token)
 {
 #define C_LEXER_BUFFER_SIZE ((256 * 1024) / sizeof (c_token))
 
@@ -1145,12 +1178,12 @@
   next_hunk_pointer = &parser->first_hunk;
   hunk_start = 0;
 
-  /* Add the initial token.  */
-  buffer[pos] = *initial;
+  /* Add the token token.  */
+  buffer[pos] = *token;
   buffer[pos].user_owned = lstate->user_owned;
   ++pos;
 
-  while (true)
+  while (token->type != CPP_EOF)
     {
       if (pos >= alloc)
 	{
@@ -1187,9 +1220,8 @@
 
       c_parser_update_checksum (&current_hash, &buffer[pos]);
 
+      token = &buffer[pos];
       ++pos;
-      if (buffer[pos - 1].type == CPP_EOF)
-	break;
     }
 
   parser->buffer = buffer;
@@ -1832,26 +1864,51 @@
 static tree c_parser_objc_message_args (c_parser *);
 static tree c_parser_objc_keywordexpr (c_parser *);
 
-/* Helper state for checking a hunk's prerequisites.  */
-struct prereq_traverse_data
-{
-  /* The associated parser.  */
-  c_parser *parser;
-  /* True if all prerequisites are satisfied, false otherwise.  */
-  bool result;
-};
-
-/* Check a single prerequisite hunk.  */
+/* Check a single prerequisite hunk.  We do this by looking at a
+   name/value prerequisite pair and verifying that the current binding
+   of the name is identical to the prerequisite binding.  Note that in
+   the future we may want to handle "semantic dependencies" here.
+   This means checking that the current value is ABI compatible with
+   the prerequisite value.  (One wrinkle here is handling inlining
+   properly.)  */
 static int
 traverse_check_prereq (void **valp, void *ptd)
 {
-  struct prereq_traverse_data *data = (struct prereq_traverse_data *) ptd;
-  struct hunk_binding *binding = (struct hunk_binding *) *valp;
-  if (!htab_find (data->parser->used_hunks, binding))
+  bool *result = (bool *) ptd;
+  struct hunk_binding_entry *entry = (struct hunk_binding_entry *) *valp;
+  if (entry->symbol_binding != hunk_binding_sentinel)
     {
-      data->result = false;
-      return false;
+      if (lookup_name_no_callback (entry->name) != entry->symbol_binding)
+	{
+	  *result = false;
+	  return false;
+	}
     }
+  if (entry->tag_binding != hunk_binding_sentinel)
+    {
+      if (entry->tag_binding)
+	{
+	  if (lookup_tag_no_callback (TREE_CODE (entry->tag_binding),
+				      entry->name) != entry->tag_binding)
+	    {
+	      *result = false;
+	      return false;
+	    }
+	}
+      else
+	{
+	  /* Here we expect there to be no tag binding, so check them
+	     all.  */
+	  if (lookup_tag_no_callback (UNION_TYPE, entry->name)
+	      || lookup_tag_no_callback (RECORD_TYPE, entry->name)
+	      || lookup_tag_no_callback (ENUMERAL_TYPE, entry->name))
+	    {
+	      *result = false;
+	      return false;
+	    }
+	}
+    }
+
   return true;
 }
 
@@ -1877,8 +1934,8 @@
   struct can_reuse_hunk_data *info = (struct can_reuse_hunk_data *) crhd;
   c_parser *parser = info->parser;
   struct parsed_hunk *hunk = info->hunk;
-  struct prereq_traverse_data data;
   struct parsed_hunk *binding_iter, *self_iter;
+  bool ok;
 
   /* We can't re-use a hunk twice in one compilation unit.  FIXME:
      this is a weird restriction and I think will go away once we have
@@ -1886,14 +1943,16 @@
      "extern int f;" the second time we will re_bind the same decl,
      eventually tripping over the GC since the decl's chain will point
      to itself (as part of scope popping).  */
+  /* FIXME: need more testing before really deleting this.  */
+#if 0
   if (htab_find (parser->used_hunks, binding))
     return true;
+#endif
 
   /* Check prerequisites for this binding.  */
-  data.parser = parser;
-  data.result = true;
-  htab_traverse_noresize (binding->prereqs, traverse_check_prereq, &data);
-  if (!data.result)
+  ok = true;
+  htab_traverse_noresize (binding->prereqs, traverse_check_prereq, &ok);
+  if (!ok)
     return true;
 
   /* If we have a multi-hunk binding, check to make sure the