rusty_alto/
lib.rs

1//! A small, fast library for bottom-up tree automata.
2//!
3//! A tree automaton reads a tree from the leaves upward. Each leaf receives a
4//! state, then each parent receives a state based on its symbol and the states
5//! assigned to its children. If the root reaches an accepting state, the tree
6//! is accepted.
7//!
8//! The main trait is [`BottomUpTa`]. It treats an automaton as an oracle: given
9//! a symbol and child states, it reports the possible parent states. This works
10//! for both explicit automata, whose rules are stored in tables, and implicit
11//! automata, whose rules are computed on demand.
12//!
13//! Use [`ExplicitBuilder`] when all rules are known ahead of time. Use
14//! [`Memo`] when an implicit automaton has its own state type, such as strings,
15//! tuples, or syntax objects, but a runner needs dense [`StateId`] values. Use
16//! [`materialize()`] when a finite implicit automaton should be explored and
17//! frozen into an [`Explicit`] automaton.
18//!
19//! Deterministic runners use [`StateId::STUCK`] as a sentinel for rejected
20//! subtrees. A node assigned `STUCK` did not match any transition rule, or one
21//! of its children was already stuck.
22//!
23//! # Grammars, algebras, and codecs
24//!
25//! [`Irtg`] combines a weighted grammar automaton with named homomorphisms and
26//! algebras. Built-in algebras cover strings, trees, TAG strings, TAG derived
27//! trees, and feature structures.
28//!
29//! [`InputCodecRegistry`] discovers file readers by their exact result type:
30//! both `.irtg` and Tulipac `.tag` codecs produce [`Irtg`], while `.auto`
31//! produces [`ExplicitWithSignature`]. [`OutputCodecRegistry`] discovers
32//! textual encodings by an algebra's public value type. An algebra's preferred
33//! GUI-neutral display is available through [`Algebra::visualize`].
34//!
35//! Codec metadata lookup is lazy: listing available formats does not read,
36//! evaluate, or encode anything.
37//!
38//! # Parsing strategies and cancellation
39//!
40//! [`Irtg::parse`] uses [`MaterializationStrategy::TopDownCondensed`], the
41//! recommended general default for complete chart construction.
42//! [`Irtg::parse_with`] selects another strategy without changing the input
43//! API. Interactive and service applications can use
44//! [`Irtg::parse_with_control`] with a clonable [`ParseControl`] to request
45//! cooperative cancellation from another thread; cancellation returns
46//! [`IrtgError::Cancelled`] and never exposes a partial chart.
47//!
48//! Algorithm performance depends on the loaded IRTG and input decomposition,
49//! not on the source filename. See the
50//! [parsing-algorithm guide](https://github.com/coli-saar/rusty-alto/wiki/Parsing-Algorithms)
51//! for selection advice and known trade-offs.
52//!
53//! ```
54//! use rusty_alto::*;
55//! use packed_term_arena::tree::TreeArena;
56//!
57//! let a = Symbol(0);
58//! let f = Symbol(1);
59//! let mut builder = ExplicitBuilder::new();
60//! let leaf = builder.new_state();
61//! let root = builder.new_state();
62//! builder.add_rule(a, vec![], leaf);
63//! builder.add_rule(f, vec![leaf, leaf], root);
64//! builder.add_accepting(root);
65//! let automaton = builder.build();
66//!
67//! let mut tree = TreeArena::new();
68//! let left = tree.add_node(a, vec![]);
69//! let right = tree.add_node(a, vec![]);
70//! let root_node = tree.add_node(f, vec![left, right]);
71//! let run = run_det(&automaton, &tree, root_node);
72//! assert!(automaton.is_accepting(&run.root_state));
73//! ```
74
75pub mod algebras;
76pub mod alto;
77pub mod alto_ast;
78pub mod application;
79pub mod astar;
80lalrpop_util::lalrpop_mod!(
81    #[allow(clippy::all)]
82    alto_grammar
83);
84pub mod codec;
85pub mod codecs;
86pub mod combinators;
87pub mod control;
88pub mod corpus;
89pub mod explicit;
90pub mod heuristic;
91pub mod homomorphism;
92pub mod ids;
93pub mod interner;
94pub mod irtg;
95pub mod materialize;
96pub mod memo;
97pub mod obligatory_leaf;
98pub mod parseval;
99pub mod run;
100pub mod score;
101pub mod set_trie;
102pub mod signature;
103pub mod sorted_language;
104pub mod traits;
105pub mod viterbi;
106
107pub use algebras::{
108    APPEND_SYMBOL, Algebra, BinarizedTagTreeDecompositionAutomaton, BinarizedTagTreeState,
109    Binarizing, CONC11, CONC12, CONC21, EvaluatingDecompositionAutomaton, FS_EMBED_PREFIX,
110    FS_PROJECT_PREFIX, FS_REMAP_PREFIX, FS_UNIFY, FeatureStructure, FeatureStructureAlgebra,
111    FeatureStructureAttribute, FeatureStructureFilter, FeatureStructureNode,
112    FeatureStructureNodeId, FeatureStructureParseError, SentenceSxHeuristic, Span, StringAlgebra,
113    StringDecompositionAutomaton, TAG_E, TAG_EE, TAG_HOLE, TAG_SUBSTITUTE, TagSpan,
114    TagStringAlgebra, TagStringDecompositionAutomaton, TagStringValue, TagTreeAlgebra,
115    TagTreeContext, TagTreeDecompositionAutomaton, TreeAlgebra, TreeValue, UniversalSxHeuristic,
116    WRAP21, WRAP22,
117};
118#[allow(deprecated)]
119pub use alto::{
120    AltoParseError, ExplicitWithSignature, ParsedTreeAutomaton, parse_alto,
121    parse_alto_with_signature,
122};
123pub use application::{
124    AutomatonSummary, EvaluatedInterpretation, InterpretationInfo, LanguageCardinality,
125    ParseStrategy, RenderedInterpretation, RenderedValue, ResolvedRule,
126};
127pub use astar::{
128    AstarOptions, AstarStats, PreparedAstarGrammar, astar_one_best, astar_one_best_with,
129    astar_one_best_with_stats, astar_string_one_best_lazy_benchmark_with_stats_prepared,
130    astar_string_one_best_with_stats_prepared, materialize_astar_intersection,
131    materialize_astar_intersection_with, materialize_astar_string_intersection_with_prepared,
132    materialize_astar_viterbi_forest, materialize_astar_viterbi_forest_with,
133};
134pub use codec::{
135    AltoTreeAutomatonInputCodec, CodecMetadata, DisplayCodec, FeatureStructureVisualizationCodec,
136    InputCodec, InputCodecError, InputCodecRegistry, InputCodecRegistryError, IrtgInputCodec,
137    OutputCodec, OutputCodecError, OutputCodecRegistry, RegisteredInputCodec, SpaceJoinCodec,
138    TextOutputCodec, TextVisualizationCodec, TreeVisualizationCodec, VisualRepresentation,
139};
140pub use codecs::{TulipacError, TulipacInputCodec};
141pub use combinators::{Determinized, InvHom, Mapped, Product};
142pub use control::ParseControl;
143pub use corpus::{Corpus, CorpusError, CorpusWriter, Instance, read_corpus};
144pub use explicit::{Explicit, ExplicitBuildError, ExplicitBuilder, Rule};
145pub use heuristic::{
146    IntersectionHeuristic, MinHeuristic, OutsideHeuristic, ScoredZeroHeuristic, ZeroHeuristic,
147};
148pub use homomorphism::{HomLabel, HomTerm, Homomorphism, HomomorphismError};
149pub use ids::{Arity, StateId, Symbol};
150pub use interner::Interner;
151pub use irtg::{
152    AstarHeuristic, EvaluatedAlgebraValue, Interpretation, Irtg, IrtgError,
153    MaterializationStrategy, NonNullFilteredChart, ParseChart, ParseInput, TypedInterpretation,
154    parse_irtg,
155};
156pub use materialize::{
157    IndexedCondensedIntersectionStats, materialize, materialize_indexed_condensed_intersection,
158    materialize_indexed_condensed_intersection_with_pairs,
159    materialize_topdown_condensed_intersection,
160    materialize_topdown_condensed_intersection_with_pairs,
161};
162pub use memo::{Memo, MemoStats};
163pub use obligatory_leaf::{ObligatoryLeafHeuristic, ObligatoryLeafTables};
164pub use parseval::{
165    EvalbParamError, EvalbParams, ParsevalCounts, ParsevalSkip, compare_trees, count_gold,
166};
167pub use run::{DetRun, NonDetRun, StateSet, run_det, run_nondet};
168pub use score::{LogProbabilityScorer, ProbabilityScorer, WeightScorer};
169pub use set_trie::{KeySet, SetTrie};
170pub use signature::{Signature, SignatureError};
171pub use sorted_language::{SortedLanguageIterator, WeightedTree};
172pub use traits::{
173    BottomUpTa, CondensedTa, CondensedTopDownTa, DetBottomUpTa, IndexedBottomUpTa, StateUniverse,
174    SymbolSet, TopDownTa,
175};
176pub use viterbi::ViterbiTree;
177
178pub(crate) type FxHashMap<K, V> = hashbrown::HashMap<K, V, rustc_hash::FxBuildHasher>;
179pub(crate) type FxHashSet<T> = hashbrown::HashSet<T, rustc_hash::FxBuildHasher>;
rusty_alto/lib.rs

rusty_alto/
lib.rs
