;;;-*- Mode: Lisp; Package: XLE -*- (in-package :XLE) #|| /* (c) 1996-2001 by the Xerox Corporation. All rights reserved */ #ifndef GRAPH_H #define GRAPH_H /* ---------------------------------------------------------------------- */ /* The Graph data structure represents a contexted feature structure. */ /* There will usually be one Graph for each Edge and SubTree. */ /* ---------------------------------------------------------------------- */ struct Graph { DUCompState *compstate; /* the global state for the parser or generator */ /* that is using this Graph */ AVPair *attrs; /* the list of top-level variables or meta-variables */ /* defined in this graph. Each top-level variable is an */ /* attribute-value tree of AVPairs. The AVPairs are */ /* never re-entrant: instead re-entrancy is handled by */ /* having explicit equality links between AVPairs. */ Clause *context; /* Whenever a subtree belongs to an edge with other */ /* valid subtrees, then its graph will get assigned a */ /* context that distinguishes it from the graphs of */ /* other subtrees. */ Clause *nogoods; /* a CONS list of nogoods asserted on this graph. */ unsigned int choice_id; /* the last choice identifier used. */ unsigned int disj_id; /* the last disjunction identifier used. */ unsigned short disjunctive : 1; /* The graph is attached to an edge */ /* that has multiple valid */ /* subtrees. It represents the OR */ /* of the subtree graphs. */ unsigned short prune : 1; /* whether the clause package should prune. */ unsigned short prune_exported : 1; /* whether exported clauses should be pruned and simplified. */ unsigned short nogoods_pulled : 1; unsigned short completeness_checked : 1; unsigned short completeness_checked1 : 1; unsigned short local_completeness : 1; /* Whether something in the graph was completed. */ unsigned short nogood : 1; /* The graph has no solutions. */ unsigned short inconsistent : 1; /* The graph has no solutions. */ unsigned short unreachable : 1; /* The graph cannot be reached */ /* because an aunt is nogood. */ unsigned short goal_cons_mark : 1; unsigned short chart_temp_mark : 1; unsigned short mark : 1; /* a mark bit for temporary marks */ unsigned short mark2 : 1; /* a mark bit for temporary marks */ unsigned short open: 1; /* Make an open-world assumption. */ unsigned short ordinaryvars : 1; /* Indicates that the AVPairs in the attrs */ /* field are not metavars connecting */ /* different edges in the chart, */ /* but rather ordinary variables. This is */ /* used by extract_chart_graph. */ unsigned short chart_clauses : 1; /* The clauses are from a chart */ unsigned short inert : 1; /* Don't do deductions. */ unsigned short input : 1; /* graph read by read_prolog_graph */ unsigned short lexical : 1; /* This is a lexical graph. */ unsigned short truncated : 1; /* max_new_events_per_graph_when_skimming was exceeded. */ unsigned short unresourced : 1; /* used for off-line generability. */ unsigned int normalized : 1; /* records normalize_chart_graphs */ unsigned int postpone_uncertainties: 1; unsigned int processing_queue: 1; DUProp *props; /* a Lisp-style property list for extensions */ UnificationQueue *queue; /* Whenever a fact is asserted on a locked */ /* AVPair, the fact is added to this queue to be */ /* processed with the AVPair is unlocked. */ RestrictionSet *solution_sets; /* The list of restriction sets and their */ /* solutions. */ RestrictionSet *intermediate_solution_sets; /* The list of intermediaterestriction sets and their solutions. */ #ifdef notdef /* Used by extract_nogood_clauses. */ GraphClauses *imports; /* The list of clauses imported from each daughter graph. */ #endif GraphList *consumers; /* A list of Graphs that consume this graph in the */ /* chart. This is used in the completeness code. */ struct Edge *edge; /* The Edge that this Graph is part of, either */ /* on the edge or one of its subtrees. */ /* We use an incomplete type for Edge so that */ /* we can get type checking now and the parsing */ /* code can still give its own definition. */ Clause *clauses; /* list of clauses allocated in this Graph */ Disjunction *disjunctions; /* list of disjunctions allocated in this */ /* Graph */ Gensym *gensyms; /* list of gensyms for this graph */ CopiedGensym *copiedgensyms; /* list of gensyms that have been copied into this graph. */ CopiedGensym *pushedgensyms; /* list of gensyms that have been pushed onto this graph. */ PushDef *pushdefs; /* Defines pushed contexts. */ AVPairList *pushed_avpairs; /* List of AVPairs with pushed facts. */ SuppressionIndex *suppressions; /* List of suppressed copy facts. */ unsigned int factcount : 16; /* AVPairs + CVPairs */ unsigned int nogoodcount : 16; /* number of nogoods */ unsigned int clausecount; unsigned int skimming_events; /* Number of events processed while skimming */ unsigned int id; /* a unique id used for debugging purposes */ PushedFU *pushedfus; /* List of pushed functional uncertainties. */ unsigned int pushedfus_processed; /* Whether the pushed uncertainties have been processed. */ }; /* ----------------------------------------------------------------------- */ /* The GraphList structure is used by Graph to keep a list of consumers. */ /* ----------------------------------------------------------------------- */ struct GraphList { Graph *item; GraphList *next; }; /* ------------------------------------------------------------------ */ /* The GraphClauses structure is used by Graph to keep track of which */ /* clauses are imported from each daughter. */ /* ------------------------------------------------------------------ */ struct GraphClauses { Graph *graph; Clause *clauses; GraphClauses *next; }; /* ----------------------------------------------------------------------- */ /* DUProp is a Lisp-like property value mechanism that allows clients of */ /* XLE to add properties to a Graph without having to recompile XLE. */ /* ----------------------------------------------------------------------- */ struct DUProp { char *name; /* the name of the property */ void *value; /* its value */ DUProp *next; }; /* ----------------------------------------------------------------------- */ /* AVPairList is used by Graph to keep track of AVPairs with pushed facts. */ /* ----------------------------------------------------------------------- */ struct AVPairList { AVPair *item; AVPairList *next; }; /* --------------------------------------------------------------- */ /* CSubTree is used to represent contexted subtrees. You can get */ /* the contexted subtrees for a chart graph by the following call: */ /* (CSubTree *)get_graph_prop(graph, "SubTrees"). */ /* --------------------------------------------------------------- */ struct CSubTree { /* contexted subtree, used by chart-extract.c */ struct Edge *mother; struct Edge *partial; struct Edge *complete; struct Edge *surface_corr; Clause *context; CSubTreeList *surface_terminals; /* terminals that map to this surface form */ CVPair *phi_projection; CVPair *cstruct_projection; int mark; CSubTree *next; }; struct CSubTreeList { CSubTree *subtree; CSubTreeList *next; }; ||# ;; /* ----------------------------------------------------------------------- */ ;; /* The Gensym data structure is used for gensym values (such as the */ ;; /* implicit index in a semantic form) that should be different even if the */ ;; /* same instance arrives at a Graph via two different routes (such as can */ ;; /* happen in generation because the generation chart can be re-entrant). */ ;; /* ----------------------------------------------------------------------- */ ;; #include "values.h" ;;struct Gensym { (ff:def-foreign-type Gensym (:struct ;; unsigned int global : 1 ; /* is this a local or global gensym? */ (global (:bit 1)) ;; unsigned int pushed : 1 ; /* is this a pushed gensym? */ ;(pushed (:bit 1)) ; OBSOLETE! ;; unsigned int id : 18 ; /* the gensym's identifier */ (id (:bit 18)) ;; Clause *context ; /* the context in which it is defined */ (context :unsigned-long) ;; TypedValueList *values ; /* the values that it was embedded in. */ (values :unsigned-long) ;; Gensym *next ; /* the next gensym in the list */ (next :unsigned-long))) ;;struct TypedValueList { (ff:def-foreign-type TypedValueList (:struct ;; TypedValue value; (value TypedValue) ;; int relID; (relid :int) ;; AVPair *avp; (avp :unsigned-long) ;; TypedValueList *next; (next :unsigned-long))) #|| struct CopiedGensym { int lower; /* the gensym in the lower graph */ Graph *graph; /* the lower graph (for copied gensyms) */ /* the upper graph (for pushed gensyms) */ int upper; /* the gensym in the upper graph */ CopiedGensym *next;/* the next gensym in the list */ }; struct HeadPrecedenceCache { int gensym1; /* the gensym of the first PRED */ int gensym2; /* the gensym of the second PRED */ Clause *context; /* the contexts in which gensym1