implicit_predicates_gen/emit/
mod.rs

1//! Rust code for the stages of a predicate.
2//!
3//! For each predicate the generated module holds its constants, the
4//! floating-point filter ([`filter`]), three exact stages ([`exact`]) and the
5//! chain that runs them ([`chain`]); a second module holds the checks that
6//! its tests use ([`checks`]). The output is built as text, in a fixed
7//! order, so it is the same on every run; it is not formatted.
8
9mod chain;
10mod checks;
11mod edges;
12mod exact;
13mod filter;
14mod program;
15mod statements;
16
17#[cfg(test)]
18mod tests;
19
20use std::fmt::Write;
21
22use implicit_predicates_core::eft::{PRODUCT_OPERAND_MAX, PRODUCT_OPERAND_MIN};
23
24use crate::bound::{FilterConstants, MAX_DEGREE, filter_bound};
25use crate::differences::difference_graph;
26use crate::error::Error;
27use crate::parse::{Predicate, parse};
28use crate::polynomial::check_same_polynomial;
29use crate::range::{ExactRange, Leaves, exact_plan_differences, exact_plan_raw};
30use exact::{Check, Stage, write_in_range, write_product, write_stage};
31use program::{Program, Step};
32
33/// The code generated for one predicate.
34#[derive(Clone, Debug, PartialEq, Eq)]
35pub struct Generated {
36    /// The name of the predicate, and of the files to write.
37    pub name: String,
38    /// The module of its stages, unformatted.
39    pub stages: String,
40    /// The module of its checks, for its tests, unformatted: `exact`, the
41    /// exact sign of the predicate, and `bound_edge_cases`, inputs on either
42    /// side of the error bound of the filter. Empty when there are none, in
43    /// which case no file is written.
44    pub checks: String,
45}
46
47/// Generates the code of every predicate defined in `source`.
48///
49/// `file` labels errors and is named in the header of the generated code,
50/// for instance `predicates/orient3d.pred`. `regenerate` tells how to
51/// regenerate the code, for instance the command that produced it; it is
52/// written in the header of every generated file after "To regenerate,",
53/// one comment line per line of text. The command line tool passes the
54/// command it was run with.
55///
56/// For each predicate the module of its stages holds the constants of its
57/// filter and the ranges of its exact stages, and the functions `filter`,
58/// `exact_differences`, `expansions_translated`, `expansions_untranslated`
59/// (only when the predicate has an `#[exact]` form) and `staged`, which runs
60/// the filter and then the exact stages in the order: differences that are
61/// exact, the translated expansion form, then the `#[exact]` form if one is
62/// given. The order is the same for every predicate for now. The module of
63/// its checks holds `exact`, the main form evaluated with the exact numbers
64/// of `implicit-predicates-oracle`, and `bound_edge_cases`, pairs of inputs
65/// at the edge of the error bound of the filter.
66///
67/// # Errors
68///
69/// Returns the first problem found in the definitions: a syntax error, a
70/// main form that is not homogeneous in differences of coordinates, a
71/// degree above the 1022 that the filter accepts, a definition too large to
72/// derive the filter bound for or to expand, an `#[exact]` form that is a
73/// different polynomial, a main form with more than 256 distinct
74/// subexpressions, or a predicate that the exact stages cannot support.
75///
76/// # Work
77///
78/// The checks run from the cheapest to the most expensive, and each step
79/// whose work can grow faster than the size of the definition has a budget,
80/// checked before the work it limits:
81///
82/// - [`parse`] nests brackets at most 32 deep, and the difference form and
83///   the degree of the `#[exact]` form take one pass each;
84/// - [`crate::filter_bound`] keeps its exact coefficients within `2^26`
85///   bits in all;
86/// - [`crate::canonical`] keeps every expansion within `2^16` terms, `2^16`
87///   bits per coefficient and `2^20` units of work;
88/// - the exact plans reject temporaries of `2^32` components or more, or of
89///   more than `2^51` operations, and take a few passes over the graph for
90///   each power of two they try;
91/// - the search for the edge cases of the checks, the most expensive step
92///   per node, runs only on main forms of at most 256 distinct
93///   subexpressions, and makes at most a fixed number of exact evaluations
94///   of the form.
95///
96/// So the work of `generate` is bounded for every definition, and the
97/// slowest definitions accepted take a few seconds in a debug build, most
98/// of it in the search for the edge cases; a definition beyond a budget is
99/// rejected with an error that names the limit.
100pub fn generate(source: &str, file: &str, regenerate: &str) -> Result<Vec<Generated>, Error> {
101    let notice = notice(file, regenerate);
102    parse(source, file)?
103        .iter()
104        .map(|predicate| generate_one(predicate, file, &notice))
105        .collect()
106}
107
108/// The forms of a predicate, with the plans of their exact stages.
109struct Forms {
110    constants: FilterConstants,
111    differences: (Program, ExactRange),
112    translated: (Program, ExactRange),
113    untranslated: Option<(Program, ExactRange)>,
114}
115
116/// Generates the code of `predicate`, whose files start with `notice`.
117fn generate_one(predicate: &Predicate, file: &str, notice: &str) -> Result<Generated, Error> {
118    // The cheap checks come first: the difference form gives the degree of
119    // the main form, one pass bounds the degree of the exact form, and the
120    // filter bound checks its own size, all before any polynomial is
121    // expanded.
122    let position = predicate.position;
123    let graph = difference_graph(&predicate.main, file, position)?;
124    if let Some(exact) = &predicate.exact {
125        let degree = exact.degree_bound();
126        if degree > u64::from(MAX_DEGREE) {
127            return Err(Error::at(
128                file,
129                predicate.exact_position.unwrap_or(position),
130                format!(
131                    "the exact form of `{}` has a degree of up to {degree}, above {MAX_DEGREE}, \
132                     the highest degree the filter accepts",
133                    predicate.name
134                ),
135            ));
136        }
137    }
138    let constants = filter_bound(&graph, file, position)?.constants();
139    check_same_polynomial(predicate, file)?;
140    if graph.nodes.len() > edges::MAX_NODES {
141        return Err(Error::at(
142            file,
143            position,
144            format!(
145                "the main form of `{}` has {} distinct subexpressions, more than the {} \
146                 for which the checks of its tests are generated: their edge cases take \
147                 thousands of exact evaluations of the whole form",
148                predicate.name,
149                graph.nodes.len(),
150                edges::MAX_NODES
151            ),
152        ));
153    }
154    let (min, max) = (PRODUCT_OPERAND_MIN, PRODUCT_OPERAND_MAX);
155    let plan = |leaves| {
156        exact_plan_differences(&graph, leaves, file, position, min, max).map(|plan| {
157            (
158                Program::differences(&graph, leaves, &plan.lengths),
159                plan.range,
160            )
161        })
162    };
163    let differences = plan(Leaves::One)?;
164    let translated = plan(Leaves::Two)?;
165    let untranslated = match &predicate.exact {
166        Some(exact) => {
167            let position = predicate.exact_position.unwrap_or(position);
168            let plan = exact_plan_raw(exact, file, position, min, max)?;
169            Some((Program::raw(exact, &plan.lengths), plan.range))
170        }
171        None => None,
172    };
173    let forms = Forms {
174        constants,
175        differences,
176        translated,
177        untranslated,
178    };
179    let points = predicate.params.len();
180    let mut out = String::new();
181    write_header(&mut out, predicate, notice);
182    write_constants(&mut out, &forms);
183    let uses_max = filter::write_filter(&mut out, &graph, points, constants.degree);
184    write_exact_stages(&mut out, predicate, &forms);
185    chain::write_chain(&mut out, points, forms.untranslated.is_some());
186    if uses_max {
187        filter::write_max(&mut out);
188    }
189    write_in_range(&mut out);
190    let programs = [&forms.differences, &forms.translated]
191        .into_iter()
192        .chain(&forms.untranslated);
193    if programs
194        .flat_map(|(program, _)| &program.steps)
195        .any(|step| matches!(step, Step::Product { .. }))
196    {
197        write_product(&mut out);
198    }
199    let mut checks = String::new();
200    checks::write_checks(&mut checks, predicate, &graph, &constants, notice);
201    Ok(Generated {
202        name: predicate.name.clone(),
203        stages: out,
204        checks,
205    })
206}
207
208/// The notice that starts every generated file: where it comes from, that
209/// it must not be edited, and how to regenerate it, followed by a blank
210/// line.
211fn notice(file: &str, regenerate: &str) -> String {
212    let mut out = format!("// Generated by implicit-predicates-gen from {file}. Do not edit.\n");
213    for (i, line) in regenerate.lines().enumerate() {
214        let line = if i == 0 {
215            format!("To regenerate, {line}")
216        } else {
217            line.to_string()
218        };
219        writeln!(out, "// {line}").unwrap();
220    }
221    out.push('\n');
222    out
223}
224
225fn write_header(out: &mut String, predicate: &Predicate, notice: &str) {
226    out.push_str(notice);
227    comment(
228        out,
229        "//!",
230        0,
231        &format!(
232            "The stages of the predicate `{}`.\n\n\
233             Every stage takes the points {} of the definition as `p`, in that order, \
234             and returns the sign of the predicate, or `None` when it cannot decide. \
235             [`staged`] runs them in order.",
236            predicate.name,
237            list(&predicate.params)
238        ),
239    );
240    out.push_str("\nuse implicit_predicates_core::{Sign, eft, expansion};\n\n");
241}
242
243/// `a`, `b` and `c`.
244fn list(names: &[String]) -> String {
245    let quoted: Vec<String> = names.iter().map(|n| format!("`{n}`")).collect();
246    match quoted.split_last() {
247        Some((last, rest)) if !rest.is_empty() => format!("{} and {last}", rest.join(", ")),
248        _ => quoted.concat(),
249    }
250}
251
252fn write_constants(out: &mut String, forms: &Forms) {
253    let c = &forms.constants;
254    let constant = |out: &mut String, doc: &str, name: &str, ty: &str, value: String| {
255        comment(out, "///", 0, doc);
256        writeln!(out, "pub const {name}: {ty} = {value};\n").unwrap();
257    };
258    constant(
259        out,
260        "The degree `k` of the predicate in the differences of coordinates.",
261        "DEGREE",
262        "u32",
263        c.degree.to_string(),
264    );
265    constant(
266        out,
267        "The coefficient of `D^k` in the error bound of [`filter`], \
268         `(EPSILON * D + KAPPA * E) * D^(k - 1)`, rounded up. `E` is the `e` given to \
269         the filter and `D` is `E` plus the largest magnitude of a difference of \
270         coordinates.",
271        "EPSILON",
272        "f64",
273        literal(c.epsilon),
274    );
275    constant(
276        out,
277        "The coefficient of `E * D^(k - 1)` in the error bound of [`filter`], rounded up.",
278        "KAPPA",
279        "f64",
280        literal(c.kappa),
281    );
282    constant(
283        out,
284        &format!(
285            "The smallest `D` for which [`filter`] decides, `2^{}`: below it, underflow \
286             could exceed the error bound.",
287            power_of_two(c.d_min)
288        ),
289        "D_MIN",
290        "f64",
291        literal(c.d_min),
292    );
293    constant(
294        out,
295        &format!(
296            "The largest `D` for which [`filter`] decides, `2^{}`: above it, a computed \
297             value could overflow.",
298            power_of_two(c.d_max)
299        ),
300        "D_MAX",
301        "f64",
302        literal(c.d_max),
303    );
304    let range = |out: &mut String, name: &str, what: &str, range: ExactRange| {
305        constant(
306            out,
307            &format!(
308                "`(min, max)`, `(2^{}, 2^{})`: {what} has a magnitude in `min..=max`.",
309                power_of_two(range.min),
310                power_of_two(range.max)
311            ),
312            name,
313            "(f64, f64)",
314            format!("({}, {})", literal(range.min), literal(range.max)),
315        );
316    };
317    range(
318        out,
319        "DIFFERENCES_RANGE",
320        "[`exact_differences`] decides when every difference of coordinates is exact \
321         in `f64` and every nonzero one",
322        forms.differences.1,
323    );
324    range(
325        out,
326        "TRANSLATED_RANGE",
327        "[`expansions_translated`] decides when every nonzero coordinate",
328        forms.translated.1,
329    );
330    if let Some((_, r)) = &forms.untranslated {
331        range(
332            out,
333            "UNTRANSLATED_RANGE",
334            "[`expansions_untranslated`] decides when every nonzero coordinate",
335            *r,
336        );
337    }
338}
339
340fn write_exact_stages(out: &mut String, predicate: &Predicate, forms: &Forms) {
341    let points = predicate.params.len();
342    let doc = "The exact sign of the predicate: its main form evaluated with expansions on \
343         the differences of coordinates, each computed in `f64`.\n\n\
344         `None` means that this stage cannot decide: some difference is not exact in \
345         `f64`, or some nonzero difference has a magnitude outside [`DIFFERENCES_RANGE`], \
346         as when a coordinate is not finite.";
347    write_stage(
348        out,
349        &Stage {
350            name: "exact_differences",
351            doc,
352            program: &forms.differences.0,
353            check: Check::Differences("DIFFERENCES_RANGE"),
354        },
355        points,
356    );
357    let doc = "The exact sign of the predicate: its main form evaluated with expansions, \
358         each difference of coordinates as an exact expansion of two components.\n\n\
359         `None` means that this stage cannot decide: some nonzero coordinate has a \
360         magnitude outside [`TRANSLATED_RANGE`] or is not finite.";
361    write_stage(
362        out,
363        &Stage {
364            name: "expansions_translated",
365            doc,
366            program: &forms.translated.0,
367            check: Check::Coordinates("TRANSLATED_RANGE"),
368        },
369        points,
370    );
371    if let Some((program, _)) = &forms.untranslated {
372        let doc = "The exact sign of the predicate: its form for exact evaluation, marked \
373             `#[exact]` in the definition, evaluated with expansions on the coordinates.\n\n\
374             `None` means that this stage cannot decide: some nonzero coordinate has a \
375             magnitude outside [`UNTRANSLATED_RANGE`] or is not finite.";
376        write_stage(
377            out,
378            &Stage {
379                name: "expansions_untranslated",
380                doc,
381                program,
382                check: Check::Coordinates("UNTRANSLATED_RANGE"),
383            },
384            points,
385        );
386    }
387}
388
389/// The width the generated comments are wrapped at, indentation included.
390const COMMENT_WIDTH: usize = 80;
391
392/// Writes `text` as comment lines that start with `marker` (`///`, `//!` or
393/// `//`), indented by `indent` spaces as rustfmt places them, wrapped at
394/// [`COMMENT_WIDTH`]; a blank line in `text` separates paragraphs.
395pub(crate) fn comment(out: &mut String, marker: &str, indent: usize, text: &str) {
396    let room = COMMENT_WIDTH.saturating_sub(indent + marker.len() + 1);
397    for (i, paragraph) in text.split("\n\n").enumerate() {
398        if i > 0 {
399            writeln!(out, "{marker}").unwrap();
400        }
401        let mut line = String::new();
402        for word in paragraph.split_whitespace() {
403            if !line.is_empty() && line.len() + 1 + word.len() > room {
404                writeln!(out, "{marker} {line}").unwrap();
405                line.clear();
406            }
407            if !line.is_empty() {
408                line.push(' ');
409            }
410            line.push_str(word);
411        }
412        writeln!(out, "{marker} {line}").unwrap();
413    }
414}
415
416/// The exponent of a normal power of two.
417fn power_of_two(x: f64) -> i64 {
418    debug_assert!(x.is_normal() && x.to_bits() & ((1 << 52) - 1) == 0);
419    i64::try_from(x.to_bits() >> 52).expect("11 bits") - 1023
420}
421
422/// An `f64` literal that reads back as exactly `x`, which must be finite:
423/// the shortest decimal that rounds to it.
424pub(crate) fn literal(x: f64) -> String {
425    debug_assert!(x.is_finite());
426    format!("{x:?}")
427}
implicit_predicates_gen/emit/mod.rs

implicit_predicates_gen/emit/
mod.rs
