;;;-*- Mode: Lisp; Package: XLE -*-

(in-package :XLE)

#||
/* (c) 2002-2004 by the Palo Alto Research Center.  All rights reserved. */
/* (c) 1996-2001 by the Xerox Corporation.  All rights reserved */

#ifndef CHART_INCLUDED_
#define CHART_INCLUDED_

enum ChartMode {
  ChartParsing, ChartGeneration
};

enum ChartDirection {
  ChartTopDown, ChartBottomUp
};
||#

(eval-when (:execute :compile-toplevel :load-toplevel)
  (defconstant +MAX_HEADWORDS+ 150) 
  (defconstant +MAX_FU_FILTER_RESULTS+  100) 
  (defconstant +MAX_PARTIAL_PATHS+ 1000)
  (defconstant +MAX_UNKNOWN_MORPHEMES+ 100))

#||
struct FUFRslt {
  int goal;
  void *context;
  void *avpair; 
};

struct TokenVertexMap {
  int token_id;
  int vertex_id;
  TokenVertexMap *next;
};

struct VertexData {
  TokenVertexMap *map;
  EdgeList *tokens;
  EdgeList *morphemes;
  Edge *unknown_token;
  unsigned int left_char_pos;
  unsigned int right_char_pos;
  unsigned int avpair_id;
  unsigned int connected : 1;
  unsigned int allows_preceding_nonterminal : 1;
  unsigned int embedded : 1;
  unsigned int end_of_input : 1;
  unsigned int mark : 1;
};

struct FactData {
  int id;
  struct AVPair *avp;
  struct AVPair *attr;
  struct CVPair *cvp;
};
||#


;; struct Chart {
(define-foreign-type Chart
    ;; void *compstate	       		; /* The DUCompState for this chart. */
    (compstate :unsigned-long)
  ;; enum ChartMode mode		; /* is this chart being used for */
					; /* parsing or generation? */
  (mode :unsigned-int)
  ;;  enum ChartDirection direction;	; /* should the chart be built in a */
					; /* top-down or bottom up fashion? */
  (direction :unsigned-int)
  ;; union ChartGoal {			; /* the top level goal */
  ;; NETptr expression;			; /* in parsing, input word net */
  ;; void *goal;				; /* used as generic type by chart */
  ;; } goal;
  ;;(goal :unsigned-long) ;; removed 2007
  ;; int missing_fact_ok;               ; /* missing facts are ok in
					; generation */
  (missing-fact-ok :int)
  ;; int duplicate_lexid_ok;            ; /* duplicate semforms are ok in
					; generation */
  (duplicate_semform_id-ok :int)
  ;; int aborted;				; /* chart processing was aborted. */
  (aborted :int)
  ;; int truncated;                        ; /* chart processing was truncated. */
  (truncated :int)
  ;; int input_count;                      /* number of inputs since last reset */
  (input_count :int)
  ;; int lexicon_resets;                   ; /* number of times the lexicon */
					; /* cache was reset. */
  (lexicon-resets :int)
  ;; Grammar *grammar;			; /* the grammar used with this chart */
  (grammar :unsigned-long)

  ;; void *string_table;                   /* the lexicon string table */
  (string-table :unsigned-long)
  ;; void *lexicon_heap;                   /* the heap for the lexicon */
  (lexicon-heap :unsigned-long)
  ;; void *eff_info;                       /* effective info for the lexicon */
  (eff-info :unsigned-long)
  ;; void *lexicon_section;                /* lexicon_section[0] of grammar */
  (lexicon-section :unsigned-long)


  ;; char *rootcat;			; /* the name of the root category */
  (rootcat :unsigned-long)
  ;; char *reparse_cat;                    ; /* the name of the reparse category */
  (reparse-cat :unsigned-long)
  ;; int reparsing;                        ; /* Whether we are reparsing. */
  (reparsing :int)
  ;; STATEptr morph_fs_start;		; /* in the new generator, this is a */
					; /* part of the root category */
  (morph-fs-start :unsigned-long)
  
  ;; /* ----------------------------------------------------------------------- */

  ;; HASH_TABLEptr vertices;		; /* all of the vertices */
  (vertices :unsigned-long)
  ;; HASH_TABLEptr edges;			; /* all of the non-duplicate edges */
  (edges :unsigned-long)
  ;; Hash_HashFN edgehashfn		;		; /* hash key function */
  (edgehashfn :unsigned-long)
  ;; Hash_CompFN edgecompfn		;		; /* hash comparison function */
  (edgecompfn :unsigned-long)
  ;; Edge *duplicates;                     ; /* All the duplicate edges */
  (duplicates :unsigned-long)
  ;; /* ----------------------------------------------------------------------- */
  
  ;; int num_edges;			; /* the number of edges in use */
  (num-edges :int)
  ;; int num_subtrees;			; /* the number of subtrees in use */
  (num-subtrees :int)
  ;; int num_vertices;			; /* the number of vertices in use */
  (num-vertices :int)
  ;; int num_tokens;			; /* the number of tokens in use */
  (num-tokens :int) ;; 2007
  ;; int max_vertex_index;			; /* the maximum Vertex->id.index. */
  (max-vertex-index :int)
  ;; int *embedded_vertex;                   ; /* whether the vertex is embedded
					; in the chart. */
  (embedded-vertex :unsigned-long)
  ;; Agenda *agenda;			; /* THE AGENDA */
  (agenda :unsigned-long)
  ;; int suppress_agenda;                  ; /* don't add to agenda */
  (supress-agenda :int)
  ;; SpanningEdgeFN spanning_edge;  ; /* a function to determine whether an edge */
					; /* is a spanning edge.  The parser and */
					; /* generator use different functions. */
  (spanning-edge :unsigned-long)
  ;; HEAPptr *heaps;			; /* array of fsm heap pointers */
  (heaps :unsigned-long)
  ;; int max_heap;			; /* index of last heap in the array */
  (max-heap :int)
  ;; NETptr *networks;                     ; /* array of networks used. */
  (networks :unsigned-long)
  ;; int networks_size;                    ; /* the size of the network. */
  (networks-size :int)
  ;; int num_networks;                     ; /* number of networks in the array */
  (num-networks :int)
  ;; void **hash_tables;                   ; /* array of hash tables used. */
  (hash-tables :unsigned-long)
  ;; int hash_tables_size;                 ; /* the size of the array. */
  (hash-tables-size :int)
  ;; int num_hash_tables;                  ; /* number of hashtables in the array */
  (num-hash-tables :int)
  ;; NETptr words_fsm;			; /* the input network. */
  (words-fsm :unsigned-long)
  ;; NETptr genstrings;			; /* the output of the generator. */
  (genstrings :unsigned-long)
  ;; struct Graph *goal_graph;		; /* generation goal graph */
  (goal-graph :unsigned-long)
  ;; int max_goal_semform_id;		/* for gen - maximum semform id */
  (max-goal-semform-id :int)
  ;;int min_goal_semform_id;		/* for gen - minimum semform id */
  (min-goal-semform-id :int)
     ;;;;;;;;;; int max_goal_lex_id;			; /* for gen - maximum lex id */
  ;;(max-goal-lex-id :int)
  ;; int num_subgoals;			; /* for gen - number of goals */
  (num-subgoals :int)
  ;; struct AVPair **subgoals;
  (subgoals :unsigned-long)
  ;; void  *gen_good_trees;		; /* gen output trees */
  (gen-good-trees :unsigned-long)
  ;; GoalCtl *goalctl;			; /* gen cache for att_value pairs in */
					; /* each goal used in lexicon lookup */
  (goalctl :unsigned-long)
  ;; /* for storage of goal attribute-value lists */
  ;; char *goal_stg_buf;  
  (goal-stg-buf :unsigned-long)
  ;; char *goal_stg_next;
  (goal-stg-next :unsigned-long)
  ;; char *goal_stg_max;
  (goal-stg-max :unsigned-long)
  ;; int16 gen_pred_ct;			; /* for regression statistics */
  (gen-pred-ct :unsigned-short)

  ;; Edge *empty_edges;			; /* gen: allow edges to be recycled */
  (empty-edges :unsigned-long)
  ;; int last_agenda_n_of_edges;		; /* gen: size of prev agenda */
  (last-agenda-n-of-edges :int)
  ;; VertexData *vertex_index;		; /* Index of information stored */
					; /* with vertices */
  (vertex-index :unsigned-long)
  ;; int vertex_index_size;		; /* Number of VertexData allocated. */
  (vertex-index-size :int)

  ;; CharData *char_data;                  /* character data (by position) */
  (char-data :unsigned-long) ;; new 05.2007
  ;; int char_data_size;                   /* size of char_data array */
  (char-data-size :int) ;; new 05.2007


  ;; Edge *tagedge;
  (tagedge :unsigned-long)
  ;; ChartProp *props;			; /* client properties */
  (props :unsigned-long)
     ;;;;;;; struct Graph *gen_top_graph;    
     ;;;(gen-top-graph :unsigned-long)
  ;; int coord_partial_inc;
  (coord-partial-inc :int)
  ;; int constraint_has_uncertainties;	; /* gen goal predict */
  (constraint-has-uncertainties :int)
  ;; char            last_attr_matched[64];
  (last-attr-matched #+allegro(:array :char 64)
		     #+sbcl(array char 64))
  ;; int             last_attr_addable;  
  (last-attr-addable :int)
  ;; /* for storage of goal partial paths, for underspecified input */
  ;; int             num_partial_paths;
  (num-partial-paths :int)
  ;; char           *partial_paths[MAX_PARTIAL_PATHS];
  (partial-paths #+allegro(:array :unsigned-long #.+MAX_PARTIAL_PATHS+)
		 #+sbcl(array :unsigned-long #.+MAX_PARTIAL_PATHS+))
  
  ;; char           *partial_path_stg_buf	;
  (partial-path-stg-buf :unsigned-long)
  ;; char           *partial_path_stg_next	;
  (partial-path-stg-next :unsigned-long)
  ;; char           *partial_path_stg_max	; 
  (partial-path-stg-max :unsigned-long)
  ;; int             unspecified_synfuns	;
  (unspecified-synfuns :int)
  ;; int             headword_ct;		; /* temp for gen-lex lookup, */
  (headword-ct :int)
  ;; char           *headwords[MAX_HEADWORDS];  ; /* to avoid duplicates */
  (headwords #+allegro(:array :unsigned-long #.+MAX_HEADWORDS+)
	     #+sbcl(array :unsigned-long #.+MAX_HEADWORDS+))
  ;; struct SynMap  *synmap		;
  (synmap :unsigned-long)
  ;; int            num_unknown_morphemes	;
  (num-unknown-morphemes :int)
  ;; char           *unknown_morphemes[MAX_UNKNOWN_MORPHEMES] ;
  (unknown_morphemes #+allegro(:array :unsigned-long #.+MAX_UNKNOWN_MORPHEMES+)
		     #+sbcl(array :unsigned-long #.+MAX_UNKNOWN_MORPHEMES+))


  ;; EdgeList *cycle_entry_points		;
  (cycle-entry-points :unsigned-long)
  ;; void *nec_parent_coverage		;
  (nec-parent-coverage :unsigned-long)
  ;; void *dependent_coverage		;
  (dependent-coverage :unsigned-long)
  ;; HASH_TABLEptr prediction_graphs		;
  (prediction-graphs :unsigned-long)
  ;; HASH_TABLEptr threaded_edge_hash;
  (threaded-edge-hash :unsigned-long)
  ;; HASH_TABLEptr threaded_constraints_hash	;
  (threaded-constraints-hash :unsigned-long)

  ;; /* --------------- */
  ;; /* For translation */
  ;; /* --------------- */
  ;; int next_fact_id;
  (next_fact_id :int)
  ;; FactData **facts;
  (facts :unsigned-long)
  ;; HASH_TABLEptr fact_hash;
  (fact_hash :unsigned-long)
  ;; char *transfer_rule_file;
  (transfer_rule_file :unsigned-long)
  ;; HASH_TABLEptr transfer_rule_hash;
  (transfer_rule_hash :unsigned-long)
  ;; HASH_TABLEptr transfer_index_hash;
  (transfer_index_hash :unsigned-long)

  ;; void *lexical_cooccurrence_db;
  (lexical_cooccurrence_db :unsigned-long)
  ;; void *dominance_db;
  (dominance_db :unsigned-long)
  ;; void *LM;
  (LM :unsigned-long)

  ;; /* --------------------- */
  ;; /* Performance variables */
  ;; /* --------------------- */
  ;; int performance_variables_initialized;
  (performance-variables-initialized :int)
  ;; int timeout;
  (timeout :int)
  ;; int max_solutions;
  (max_solutions :int) ;; new June 2007
  ;; int max_xle_events;
  (max_xle_events :int)
  ;; int bytes_in_use;
  (bytes_in_use :int)
  ;; int max_bytes_in_use;
  (max_bytes_in_use :int)
  ;; int max_bytes_in_use;
  (orig_bytes_in_use :int)
  ;; int max_medial_constituent_weight;
  (max_medial_constituent_weight :int)
  ;; int max_medial2_constituent_weight;
  (max_medial2_constituent_weight :int)
  ;; int max_raw_subtrees;
  (max_raw_subtrees :int)
  ;; int start_skimming_when_scratch_storage_exceeds;
  (start_skimming_when_scratch_storage_exceeds :int)
  ;; int start_skimming_when_bytes_used_exceed;
  (start_skimming_when_bytes_used_exceed :int)
  ;; int start_skimming_when_total_events_exceed;
  (start_skimming_when_total_events_exceed :int)
  ;; int max_new_events_per_graph_when_skimming;
  (max_new_events_per_graph_when_skimming :int)
  ;; int max_selection_additional_storage;
  (max_selection_additional_storage :int)
  (max_selection_bytes_in_use :unsigned-long)
  ;; char *skimming_nogoods;
  (skimming-nogoods :unsigned-long)
  ;; char *property_weights_file		; ; /* used for select_best_parse. */
  (property-weights-file :unsigned-long)
  ;; char *orig_property_weights_file	; ; /* used by make_bug_grammar. */
  (orig-property-weights-file :unsigned-long)
  ;; char *gen_property_weights_file; /* used for select_best_parse. */
  (gen-property-weights-file :unsigned-long)
  ;; char *orig_gen_property_weights_file; /* used by make-bug-grammar. */
  (orig-gen-property-weights-file :unsigned-long)

  ;; char *prune_subtree_file;   /* used by prune_chart_subtrees. */
  (prune_subtree_file :unsigned-long)
  ;; char *orig_prune_subtree_file; /* used by make-bug-grammar. */
  (orig_prune_subtree_file :unsigned-long)
  ;; double prune_subtree_cutoff;
  (prune_subtree_cutoff :double)
  ;; int prune_subtree_location;
  (prune_subtree_location :int)
  ;; int prune_subtree_errors;
  (prune_subtree_errors :int)
  ;; ChartStringList *suppress_pruning_statistics;
  (suppress_pruning_statistics :unsigned-long)
  ;; char *language_model_file;
  (language_model_file :unsigned-long)
  ;; char *orig_language_model_file;
  (orig_language_model_file :unsigned-long)
     
  ;; char *gen_selector;          /* function for selecting a generation output */
  (gen-selector :unsigned-long)
  ;; char *ignoreProjections;     /* used for ignoring projections */
  (ignoreProjections :unsigned-long)
  ;; void *sbp_state            ; /* state used by select_best_parse. */
  (sbp-state :unsigned-long) 
  ;; char *prolog_encoding;       ; /* the character encoding of Prolog files */
  (prolog-encoding :unsigned-long)
  ;; void *sentence_tokenizer;    ; /* for sentence breaking */
  (sentence-tokenizer :unsigned-long)
  ;;clock_t morph_tics;
  ;;clock_t chart_tics;
  ;;clock_t unifier_tics;
  ;;clock_t completer_tics;
  ;;clock_t solver_tics;

  ;; float CPUtime;               /* CPUtime in seconds */
  ;; HASH_TABLEptr subtree_feature_hash;

  )


#||
; /* ------------------------------------------------------------------------- */

struct AgendaArray {

  Agenda **agenda;    ; /* array of agendas */

  int size;            ; /* size of the array */

  int n_of_edges;      ; /* number of edges in all of the agendas */

  int min_agenda_id;    ; /* id of first non-empty agenda in array */

};

/* ------------------------------------------------------------------------- */

struct Agenda {             /* an agenda of edges to be processed */

  int size;                 /* size of the agenda array */

  Edge **edges;             /* array of edges on the agenda */

  int n_of_edges;           /* number of edges in the edge array */

  AgendaArray small;        /* agenda array of small edges */

  AgendaArray non_embedded; /* agenda array of large non-embedded completes */

  AgendaArray partial;      /* agenda array of large partials */

  AgendaArray complete;     /* agenda array of large embedded completes */

  Chart *chart;

  ScheduleFN schedule;      /* function for adding an edge to the agenda */

  UnScheduleFN unschedule;  /* function for removing an edge from the */
			    /* agenda */
};

/* ------------------------------------------------------------------------- */

#define VTYPE_REGULAR 0             /* regular edges */
#define VTYPE_LEXICAL 1             /* lexical edges (different name space) */
#define VTYPE_SUBRULE 2             /* edges for a subrule */
#define VTYPE_SUBRULE_COMPLETE 3    /* edges for the complete of a subrule */
||#

;;struct VertexID {
(define-foreign-type VertexID
    ;;  CategoryID category;	/* Rule category, e.g. NP, VP.  The VertexID */
    ;;			/* conflates string position and category because */
    ;;			/* this produces a more efficient indexing scheme.  */
    (category :unsigned-long)
  ;;  int16 index;		/* in gen: semantic index, in parse: left vertex */
  (index :unsigned-short)
  ;;  int16 type;           /* The type of a vertex. See VTYPE_XXX. */
  (type :unsigned-short)
  ;;  STATEptr fs_state;    /* in gen; transducer pos for begin  */ 
  (fs_state :unsigned-long)
  ;;  STATEptr rule_state;  /* The beginning state in the rule */
  (rule_state :unsigned-long))
;;};

;;/* ------------------------------------------------------------------------- */

;; struct Vertex {
(define-foreign-type Vertex
    ;;  VertexID id;		/* a vertex identifier.  See VertexID. */
    (id VertexID)
  ;;  Requestor *requestors;/* partial edges that are looking for complete */
  ;;			/* edges which have this vertex as their left vertex */
  (requestors :unsigned-long)
  ;;  Edge *completes;      /* complete edges that have this vertex as */
  ;;		        /* their left vertex */
  (completes :unsigned-long)
  ;;  int     filtered : 1;			/* generator lookahead checking done */
  (filtered (#+allegro :bit #+sbcl integer 1))
  ;;  int     mustfail : 1;			/* rule lookahead indicates must fail*/
  (mustfail (#+allegro :bit #+sbcl integer 1))
  ;;  int     lex_edges_searched : 1;	/* to avoid repeating fsm filter */
  (lex_edges_searched (#+allegro :bit #+sbcl integer 1))
  ;;  int     lex_edges_created :  1;
  (lex_edges_created (#+allegro :bit #+sbcl integer 1))
  ;;  int     maynext_stem : 1;		/* gen property, from transducer */
  (maynext_stem (#+allegro :bit #+sbcl integer 1))
  ;;  int     stem_constraints_built : 1;	/* to avoid rechecking lex */
  (stem_constraints_built (#+allegro :bit #+sbcl integer 1))
  ;;  int     stem_constraint_ct : 20;      /* cached results of lex_lookup */
  (stem_constraint_ct (#+allegro :bit #+sbcl integer 20))
  ;;  StemConstraint *stem_constraint_list;  /* from filter. */
  (stem_constraint_list :unsigned-long)
  ;;  int     rule_fsm_index;	/* cache index to avoid repeated lookup */
  (rule_fsm_index :int)
  ;;  int     max_depth;
  (max_depth :int)
  )
;;};

#||
/* ------------------------------------------------------------------------- */

struct SubTreeLink {
  SubTree *pSubtree;
  SubTreeLink *next;
};
||#
;; struct Edge {
(define-foreign-type Edge
    ;; int id;                  /* a unique identifier */
    (id :int)
  ;;int preference_count : 24;  
  ;;/* number of OT marks of a particular rank */
  (preference_count (#+allegro :bit #+sbcl integer 24))
  ;; unsigned int source : 1; /* This is a source edge, used to initiate a */
  ;;/* category. */
  (source (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int is_surface : 1;   /* This is a surface edge (token). */
  (is_surface (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int lexical : 1;   /* This is a lexical (terminal) edge. */
  (lexical (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int preterm : 1;   /* This is a preterminal edge. */
  (preterm (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int cyccheck : 1;   /* This edge has been checked for cycles. */
  (cyccheck (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int cycfixed : 1;   /* A cycle has been removed. */
  (cycfixed (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int cyclic      : 1;    /* for the generation guide */
  (cyclic (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int cycle_root  : 1;    /* for unwinding cycles */
  (cycle_root (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int on_cycle    : 1;    /* for the generation guide */
  (on_cycle (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int along_cycle : 1;    /* for the generation guide */
  (along_cycle (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int refined     : 1;    /* whether coverage info. is recorded */
  (refined (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int on_agenda   : 1;    /* for generation */
  (on_agenda (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int mark : 1;      /* for tree walking algorithms */
  (mark (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int mark2 : 1;      /* for checking for well-formedness */
  (mark2 (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int unknown : 1;  /* for lex edges - word not in lex */
  (unknown (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int lexentry_found : 1; /* for lex edge unknowns - used an lunknown*/
  (lexentry_found (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int analyzed : 1; /* token was analyzable. */
  (analyzed (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_gen_solns : 1; /* temp for gen - completes of top */
  (has_gen_solns (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int nbd : 1;   /* possible non-branching dominator */
  (nbd (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int ctnsnbd : 1;
  (ctnsnbd (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int tagedge :  1;     /* for gen surface forms*/ 
  (tagedge (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int prune :  1;     /* for chart navigation */ 
  (prune (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int unrooted : 1;    /* for chart navigation */
  (unrooted (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int root : 1;    /* root edge of chart */
  (root (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int nogood : 1;  /* constraints are nogood. */
  (nogood (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int unresourced : 1;  /* used for off-line generability. */
  (unresourced (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_pred : 1;  /* Whether the edge has (^ PRED)='xxx' */
  (has_pred (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int always_headed : 1;  /* Whether the edge always has a head,
  ;;				      where the head has a PRED or is a
  ;;				      coordination or is a resourced
  ;;				      expletive. */
  (always_headed (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int always_headed_checked : 1;  /* Whether always_headed has 
  ;;				    already been computed. */
  (always_headed_checked (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_coord_attr : 1;  /* Result of edge_has_coord_attr */
  (has_coord_attr (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_coord_attr_checked : 1; /* Whether edge_has_coord_attr has
  ;;				      already been computed. */
  (has_coord_attr_checked (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_element : 2;  /* Whether the edge has ! $ ^ in ^=! chain */
  (has_element (#+allegro :bit #+sbcl integer 2))
  ;; unsigned int no_uncertainties : 1; /* Whether the edge contains
  ;;				uncertainties in the edges
  ;;			connected by ^ = !. */
  (no_uncertainties (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_arg : 1;   /* Whether the edge has a governable arg */
  (has_arg (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int has_args : 1;  /* Whether the edge has some governable args */
  (has_args (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int duplicated : 1;  /* Edge is duplicated version of shared edge */
  (duplicated (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int max_slash_id : 5;  /* max slash id for this edge */
  (max_slash_id (#+allegro :bit #+sbcl integer 5))
  ;; unsigned int prolog : 1;   /* created by read_prolog_graph */
  (prolog (#+allegro :bit #+sbcl integer 1))
  ;; unsigned int arglist;      /* the arglist for coherence checking. */ 
  (arglist :int)
  ;;#if 0
  ;; unsigned int local_attributes; /* the set of local attributes */ 
					;(local_attributes :int)
  ;; unsigned int external_attributes; /* the set of external attributes */ 
					;(external_attributes :int)
  ;;#endif

  ;;#ifdef FILLER_COUNTS
  ;; unsigned int filler_counts; /* A vector of possible filler counts. */ 
					;(filler_counts :int)
  ;; unsigned int good_filler_counts; /* A vector of good filler counts. */ 
					;(good_filler_counts :int)
  ;;#endif

  ;;  Vertex *vertex;       /* The vertex this edge is associated with */
  ;;			/* The vertex provides a primary indexing for edges */
  (vertex :unsigned-long)

  ;; STATEptr state;       /* the state in the rule fsm that this edge ends in */
  (state :unsigned-long)

  ;;  int right_vertex;	/* for parsing: the right vertex of this edge */
  ;;                         /* for generation: number of facts (for cycles) */
  (right_vertex :int)
  ;;  void *coverage;	/* a bit array recording coverage of the edge in gen */
  (coverage :unsigned-long)

  ;; #define TREE_TRIMMING_EXPERIMENT
  ;; #ifdef TREE_TRIMMING_EXPERIMENT
  ;;   void *nec_coverage;	   /* a bit array recording necessary coverage */
  (nec_coverage :unsigned-long)
  ;;   void *nec_parent_coverage;   /* a bit array recording parent coverage */
  (nec_parent_coverage :unsigned-long)
  ;;   void *local_coverage;	   /* a bit array recording local coverage */
  (local_coverage :unsigned-long)
  ;; #endif

  ;; EdgeList *refined_edges; /* List of refined edges for this edge. */
  (refined_edges :unsigned-long)

  ;; long rt_fs_states;    /* for gen list of rt states for edge */
  ;;                   /* also used in the parser for recording */
  ;;                   /* heavy center embedding. */
  (rt_fs_states :long)
  ;; SubTree *subtrees;    /* the subtrees of this edge */
  (subtrees :unsigned-long)
  ;; SubTreeLink *mothers;    /* the subtrees that contain this edge */
  (mothers :unsigned-long)
  ;; ChartProp *props;     /* client properties */
  (props :unsigned-long)
  ;; float count;   /* the number of trees this edge contains */
  ;;               /* We use 'float' because the number can exceed 2^32. */
  (count :float)
  ;; float score;   /* Used by prune_edge_subtrees. */
  (score :float) ;; 2007
  ;; struct Graph *graph;  /* the contexted graph for this edge.  It */
  ;;			/* represents the disjunction of all of the subtree */
  ;;			/* graphs. */
  (graph :unsigned-long)
  ;; EdgeList *surface_corr;    /* 0 if non_lexical or surface edge, */
  ;;                            /* else list of associated surface edges */
  (surface_corr :unsigned-long)
  ;; int first_tc_offset; /* for dummy surface edge, used in gen output */
  (first_tc_offset :int)
  ;; Edge *next;           /* linked list used by the vertices */
  (next :unsigned-long)
  ;; Chart *chart;         /* the chart that this edge is a part of */
  (chart :unsigned-long)
  ;; Edge *original_edge;		/* these fields serve in the unwinding alg. */
  (original_edge :unsigned-long)
  ;; Edge *vertex_partial;
  (vertex_partial :unsigned-long)
  ;; Edge *vertex_complete;
  (vertex_complete :unsigned-long)
  ) ;;};

;; struct EdgeList {
(define-foreign-type EdgeList

    ;; Edge *pEdge;
    (pEdge :unsigned-long)
  ;; int prune;
  (prune :int)
  ;; EdgeList *next;
  (next :unsigned-long))
;;};

#||
/* used in right vertex */
#define GEN_NBD_INDICATOR  20
#define ACTIVE_EDGE(E)		\
	((E)->state != NULL && STATE_arc_set((E)->state) != NULL)

#define INACTIVE_EDGE(E)	\
	((E)->state == NULL || STATE_final((E)->state))

/* ----------------------------------------------------------------------- */
/* ChartProp is a Lisp-like property value mechanism that allows clients   */
/* of XLE to add properties to a Graph without having to recompile XLE.    */
/* ----------------------------------------------------------------------- */

struct ChartProp {
  char *name;  /* the name of the property */
  void *value; /* its value */
  ChartProp *next;
};

/* ------------------------------------------------------------------------- */
||#

;;struct SubTree {
(define-foreign-type SubTree
    ;; Edge *partial;       /* the left daughter */
    (partial :unsigned-long)
  ;;  Edge *complete;      /* the right daughter */
  (complete :unsigned-long)
  ;; ARCptr arc;          /* the arc in the grammar fsm that was used to */
  ;;		       /* combine the partial and the complete. */
  (arc :unsigned-long)
  ;;  SExp *constraint;    /* the LFG constraints for this subtree.  This */
  ;;                       /* is either derived from SubTree->arc, */
  ;;                       /* or it is added to preterminals from the lexicon. */
  ;;                       /* It can become invalid if the lexicon gets reset by */
  ;;                       /* check_input_caches, so you should always use */
  ;;                       /* get_subtree_constraints to fetch this field. */
  (SExp :unsigned-long)
  ;;  struct Graph *graph; /* the contexted graph that combines the partial and */
  ;;		       /* complete graphs with the arc constraint. */
  (graph :unsigned-long)
  ;;  void *coverage;      /* Coverage for the local subtree constraints. */
  (coverage :unsigned-long)
  ;;  SubTree *next;       /* the next subtree in the edge */
  (next :unsigned-long)
  ;;  Edge *edge;        /* the edge this is a subtree of */
  (edge :unsigned-long)
  ;;#ifdef FILLER_COUNTS
  ;;  unsigned int filler_counts; /* A vector of filler counts. */
  ;;#endif

  ;;  unsigned int mark : 1;    /* a temporary mark bit */
  (mark (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int prune : 1;    /* a temporary mark bit */
  (prune (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int p_cycle : 1;  /* indicates a cycle through the partial */
  (p_cycle (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int c_cycle : 1;  /* indicates a cycle through the complete */
  (c_cycle (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int nogood : 1;  /* This subtree was determined to be
  ;;				      nogood by pre-filtering. */
  (nogood (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int dispreferred : 1;  /* subtree is dispreferred. */
  (dispreferred (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int required : 1;    /* this subtree is required */
  (required (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int allpred : 1;       /* for gen recursives */
  (allpred (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int recursion_checked : 1;    /* for gen recursives */
  (recursion_checked (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int mbr_arcs_indet : 1;    /* temp for gen coordination */
  (mbr_arcs_indet (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int gen_mark : 1;     /* temporary mark bit */
  (gen_mark (#+allegro :bit #+sbcl integer 1))
  ;;  unsigned int maybe_lr_sublex : 1;     /* experimental */
  (maybe_lr_sublex (#+allegro :bit #+sbcl integer 1))
  ;;  int preference_count;   /* number of OT marks of a particular rank */
  (preference_count (#+allegro :bit #+sbcl integer 1))
  ;;#ifdef SUBTREE_SCORE
  ;;float score;
  ;;#endif
  )
;;};

#||

/* ------------------------------------------------------------------------- */

struct Requestor {

  Edge *edge;  /* the edge that is making the request */

  unsigned int nbdbegin :1;   /* gen, possible begin non branching dom i->i */
  unsigned int fu_reduced : 1; /* gen, some mod/nogood on funct. uncertainty*/

  unsigned int mark : 1;

  ARCptr arc;  /* the arc that will combine the requestor with the */
	       /* requested */

  struct Graph *graph;  /* the result of combining the requestor with the */
			/* arc's constraint (only used by the generator) */

  Requestor *next; /* next requestor in the vertex's list */

};

/* ------------------------------------------------------------------------- */

struct GoalCtl {
  struct AVPair *goal_avp;   
  GoalAV   *goal_av_list;        /* for lexicon compare */
  GoalAV   *partial_gav_list;    /* this esp for underspecified input*/
  int       av_list_built;       /* boolean             */
  int       explicit_coord;   
  int       num_goal_avs;        /* size of av-list      */
  int       num_indexed_avs;     /* first n indexed     */
  int       num_partial_avs;     /* up to that with const value */   
  int       goal_is_upconst;     /* for goal prediction */
  int       maybe_shared_goal;   /* for coordination */
  void     *sample_mbr_avp;      /* for coordination */ 
  int       sample_mbr_goal;     /* for coordination */ 
  int       goal_container;      /* if goal member of set, goalid of set*/
  int       goal_size;           /* if goal is set, element count */
  char    **set_att_list;        /* list of dist and non dist atts */   
  int       set_att_list_built;
  int       num_common_mbr_atts; /* if goal is set,possibly distrib atts*/ 
  int       num_nonident_mbr_atts; 
  int       num_ident_mbr_atts;
  int       unspecified_synfuns; /* for goals with preds */ 
  char     *pred_str;              
  int       goal_arg_ct;        
  char      goal_args[4];        /* encoded fn refs or constants or 0*/
  int       first_synmap;        /* pos in chart synmap struct */ 
  int       num_synmaps;         
  struct AVPair *goal_arg_avps[4];   /* NULL for non-avpair args */
  int       arg_is_avp[4];
};

/* ------------------------------------------------------------------------- */

struct GoalAV {
  char *attname;
  char *attvalue;
  int16 predvalue; 
  int16 argclass;		/* F, M, U, ...*/   
  char  argsynfuns[4]; 
};

/* ------------------------------------------------------------------------- */

struct StemConstraint {
  char *stem;
  SExp *constraint;
  unsigned int mcodestar    : 1;
  unsigned int allpred      : 1;
  unsigned int continuation : 1;
};

/* ------------------------------------------------------------------------- */

struct FSState {
  STATEptr rt_fs_state;		/* FS state */
  CategoryID *rt_fs_categories;	/* FS follow categories after state */
  int rt_fs_cat_count;		/* -1 if follow cat not initialized for edge */
  int rt_fs_id;		/* FS identifier */
  char maynext_int_stem;	/* part of compound or contraction */  
};

struct SynMap {
  int attid;      /* of a pred arg syntactic function */ 
  struct AVPair *valavp[4];  /* associated goal avps or NULL     */
}; 
     
#endif /* CHART_INCLUDED_ */

||#

;; from lfg.h

;; struct Grammar {
(define-foreign-type XLEGrammar
    ;; char                 *filename;
    (filename :unsigned-long)
  ;; char                 *performance_vars_file;
  (performance_vars_file :unsigned-long)
  ;; int                  shared;     /* Multiple charts use this grammar. */
  (shared :int)
    
					#|| int                  has_generator; /* One of the charts is a generator. */
  void                 *grammar_heap  ; /* SExp storage for grammar */
  void                 *lexicon_heap  ; /* SExp storage for lexicon */
  void                 *string_table ; /* string storage for grammar and
  lexicon (can be reset) */
  sRule_name_and_fsm   *pRF		;
  int                   number_of_rules	;
  int                   number_of_fsms	;
  lptr                 *complex_rules	;
  int                   num_complex_rules ;
  sRule_and_constraint *pRC		;
  int                   pRC_size	;
  int                   number_of_arc_labels ;
  void                 *Macro_table	;
  int                   Macro_table_size ;
  void                 *Macro_hash	;
  int                   Number_of_macros ;
  void                 *Template_table	;
  int                   Template_table_size ;
  void                 *pTemplate_expansion_info ;
  int                   Number_of_templates ;
  HASH_TABLEptr         feature_hash	;
  grammar_identifier    grammar_id	;
  int                   input_count ;     /* for symbol table recovery*/
  int                   gen_input_count	; /* and lexicon cache recovery*/
  int                   lexicon_resets	;   /* number of recoveries */
  struct AttrProps     *attr_props ; /* used in ../DU/instantiate.c */
  int             number_of_attr_props ; /* used in ../DU/instantiate.c */
  int             number_of_governable ; /* used in ../DU/instantiate.c */
  void *                file_info   ;     /* master index structure */
  void *                lex_info  ;       /* top lex index structure*/
  void *                parse_morph_info ;  /* used in parse morphology*/
  void *                gen_morph_info ; /* used for gen morphology */
  void *                gen_att_info  ;  /* used in gen lex indexing*/
  void *                gen_rule_info	;  /* used in gen filtering */
  void *                synfuncodes	;    /*for gen indexing */ 
  char *                lexgovernable	; /* for gen indexing */ 
  int                   synfuncode_ct	;  
  void *                label_map	;     /* cfsm label map */
  int                   build_multiwords_from_tokens ;
  char *                expletive_attr	;  /* The resourced attr for
  expletives */
  char *                coord_attr    ;      /* The resourced attr for
  coordination */
  char *                grammar_encoding ; /* character encoding */
  char *                gen_morph_encoding ; /* character encoding */    
  char *                parse_morph_encoding ; /* character encoding */    
  lptr  expressions[MAXNETWORK]		;
  NETptr networks[MAXNETWORK]		;
  int netindex				;
  Grammar *next				;
  }					;||#
  )

:eof