fallow_mutation/
lib.rs

1//! Mutant site discovery and mutation-switching instrumentation.
2//!
3//! The crate is pure: it reads one source text and returns the mutants and
4//! the instrumented text. It does no IO, and it depends on no other Fallow
5//! workspace crate. The engine joins the mutants to graph, diff and
6//! complexity facts.
7//!
8//! The instrumented text is a splice over the original text. The crate never
9//! reprints the AST, so the output keeps the language of the input (TypeScript
10//! stays TypeScript, JSX stays JSX) and runner transforms see the original
11//! syntax.
12//!
13//! Subsumption is a static rule: negate-condition gives no mutant for a test
14//! that is a comparison or a logical expression, because the relational and
15//! logical operator mutants of that test cover it.
16
17mod collect;
18mod emit;
19mod id;
20mod operator;
21
22use serde::Serialize;
23
24pub use operator::Operator;
25
26/// The language of a source text.
27#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
28#[serde(rename_all = "kebab-case")]
29pub enum SourceKind {
30    /// JavaScript. JSX syntax is accepted, and module or script mode is
31    /// detected from the content.
32    Js,
33    /// JavaScript with JSX.
34    Jsx,
35    /// TypeScript without JSX.
36    Ts,
37    /// TypeScript with JSX.
38    Tsx,
39}
40
41impl SourceKind {
42    /// Selects the kind from the file extension of `path`.
43    pub fn from_path(path: &str) -> Option<Self> {
44        let extension = path.rsplit_once('.')?.1;
45        match extension {
46            "js" | "mjs" | "cjs" => Some(Self::Js),
47            "jsx" => Some(Self::Jsx),
48            "ts" | "mts" | "cts" => Some(Self::Ts),
49            "tsx" => Some(Self::Tsx),
50            _ => None,
51        }
52    }
53
54    /// The Oxc source type for this kind.
55    pub const fn source_type(self) -> oxc_span::SourceType {
56        match self {
57            Self::Js => oxc_span::SourceType::unambiguous().with_jsx(true),
58            Self::Jsx => oxc_span::SourceType::jsx(),
59            Self::Ts => oxc_span::SourceType::ts(),
60            Self::Tsx => oxc_span::SourceType::tsx(),
61        }
62    }
63}
64
65/// Options for [`instrument`].
66#[derive(Debug, Clone, PartialEq, Eq)]
67pub struct MutationOptions {
68    /// The operators that may produce mutants.
69    pub operators: Vec<Operator>,
70    /// Byte ranges in the original text. When set, a mutant is kept only when
71    /// its span overlaps one of the ranges. `None` mutates the whole file.
72    pub ranges: Option<Vec<(u32, u32)>>,
73}
74
75impl Default for MutationOptions {
76    fn default() -> Self {
77        Self {
78            operators: Operator::ALL.to_vec(),
79            ranges: None,
80        }
81    }
82}
83
84/// The stable identity of a mutant: 16 lowercase hex digits.
85#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
86#[serde(transparent)]
87pub struct MutantId(pub String);
88
89impl MutantId {
90    /// The id as text.
91    pub fn as_str(&self) -> &str {
92        &self.0
93    }
94}
95
96impl std::fmt::Display for MutantId {
97    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
98        f.write_str(&self.0)
99    }
100}
101
102/// The function that contains a mutant.
103#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
104pub struct FunctionRef {
105    /// The function name, when the syntax gives one.
106    pub name: Option<String>,
107    /// The original byte span of the function.
108    pub span: (u32, u32),
109}
110
111/// One mutant.
112#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
113pub struct Mutant {
114    /// The stable id.
115    pub id: MutantId,
116    /// The operator that produced the mutant.
117    pub operator: Operator,
118    /// The original byte span that the mutant replaces.
119    pub span: (u32, u32),
120    /// The 1-based line of the span start.
121    pub line: u32,
122    /// The 0-based byte column of the span start.
123    pub column: u32,
124    /// The original text of the span.
125    pub original: String,
126    /// The text that replaces the span. The original source with this
127    /// replacement applied is the mutated program. At the start of an
128    /// expression statement, the text can start with `void`, so that the
129    /// statement does not join the line before it.
130    pub replacement: String,
131    /// The innermost function that contains the mutant.
132    pub enclosing_function: Option<FunctionRef>,
133}
134
135/// One copied run of original text in the instrumented output.
136#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize)]
137pub struct SpliceSegment {
138    /// The byte offset in the instrumented output.
139    pub generated_start: u32,
140    /// The byte offset in the original text.
141    pub original_start: u32,
142    /// The length in bytes.
143    pub len: u32,
144}
145
146/// Maps instrumented byte offsets back to original byte offsets.
147///
148/// Each segment is a run of original text that the output copies unchanged.
149/// Text that the instrumentation adds has no segment. The segments are in
150/// increasing `generated_start` order.
151#[derive(Debug, Clone, Default, PartialEq, Eq, Serialize)]
152pub struct SpliceMap {
153    /// The copied runs, in output order.
154    pub segments: Vec<SpliceSegment>,
155}
156
157impl SpliceMap {
158    /// The original offset of a generated offset, or `None` when the
159    /// instrumentation added the byte.
160    pub fn original_offset(&self, generated: u32) -> Option<u32> {
161        let index = self
162            .segments
163            .partition_point(|segment| segment.generated_start <= generated);
164        let segment = self.segments.get(index.checked_sub(1)?)?;
165        let delta = generated - segment.generated_start;
166        (delta < segment.len).then_some(segment.original_start + delta)
167    }
168}
169
170/// The result of [`instrument`].
171#[derive(Debug, Clone, PartialEq, Eq)]
172pub struct Instrumented {
173    /// The mutants, in source order.
174    pub mutants: Vec<Mutant>,
175    /// The instrumented source text.
176    pub code: String,
177    /// The map from output offsets to original offsets.
178    pub map: SpliceMap,
179}
180
181/// An error from [`instrument`].
182#[derive(Debug, Clone, PartialEq, Eq)]
183pub enum MutationError {
184    /// The source text does not parse.
185    Parse {
186        /// The parser messages.
187        messages: Vec<String>,
188    },
189    /// The source text or the instrumented text is larger than `u32::MAX`
190    /// bytes.
191    TooLarge,
192    /// The source declares a binding with a name that the prelude uses. See
193    /// [`RESERVED_PREFIX`].
194    ReservedName {
195        /// The declared name.
196        name: String,
197    },
198}
199
200impl std::fmt::Display for MutationError {
201    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
202        match self {
203            Self::Parse { messages } => {
204                write!(f, "the source does not parse: {}", messages.join("; "))
205            }
206            Self::TooLarge => {
207                f.write_str("the source or the instrumented output is larger than 4 GiB")
208            }
209            Self::ReservedName { name } => write!(
210                f,
211                "the source declares `{name}`, a name that the mutation prelude reserves"
212            ),
213        }
214    }
215}
216
217impl std::error::Error for MutationError {}
218
219/// True for a byte that can continue an identifier. Non-ASCII bytes count,
220/// so that an edit never joins a Unicode identifier with a keyword.
221const fn is_identifier_byte(byte: u8) -> bool {
222    byte.is_ascii_alphanumeric() || matches!(byte, b'_' | b'$') || byte >= 0x80
223}
224
225/// The name prefix that the instrumentation reserves.
226///
227/// The prelude declares [`ACTIVE_FUNCTION`] and [`HIT_FUNCTION`] at the top
228/// level of each instrumented file. A source that declares a binding with one
229/// of these two names, at any scope, gives [`MutationError::ReservedName`],
230/// because that binding would replace or shadow the prelude function. Other
231/// names with this prefix do not give an error now. Do not use names with
232/// this prefix in project code, because a later prelude can use them.
233pub const RESERVED_PREFIX: &str = "__fallow_m_";
234
235/// The prelude function that asks the runtime whether a mutant is active.
236///
237/// The instrumented output calls `__fallow_m_a(id)` before each mutated
238/// branch. The function returns `globalThis.__fallowMutation.a(id)`, or
239/// `false` when the runtime object is not set.
240pub const ACTIVE_FUNCTION: &str = "__fallow_m_a";
241
242/// The prelude function that reports a hit on the original branch.
243///
244/// The instrumented output calls `__fallow_m_c(id)` for each mutant of a site
245/// before the original branch runs. The function calls
246/// `globalThis.__fallowMutation.c(id)` when the runtime object is set.
247pub const HIT_FUNCTION: &str = "__fallow_m_c";
248
249/// Finds the mutants in `source` and returns the instrumented text.
250///
251/// `path` is part of each mutant id. Use the project-relative path, so that
252/// ids are the same on each machine.
253pub fn instrument(
254    source: &str,
255    path: &str,
256    source_type: SourceKind,
257    options: &MutationOptions,
258) -> Result<Instrumented, MutationError> {
259    if u32::try_from(source.len()).is_err() {
260        return Err(MutationError::TooLarge);
261    }
262    let allocator = oxc_allocator::Allocator::default();
263    let parsed = oxc_parser::Parser::new(&allocator, source, source_type.source_type()).parse();
264    if parsed.fatal_error || parsed.diagnostics.has_errors() {
265        let messages = parsed.diagnostics.iter().map(ToString::to_string).collect();
266        return Err(MutationError::Parse { messages });
267    }
268    if let Some(name) = reserved_binding(&parsed.program) {
269        return Err(MutationError::ReservedName { name });
270    }
271    let collected = collect::collect(&parsed.program, source);
272    let insertions = header_insertions(&parsed.program, source);
273    let line_starts = line_starts(source);
274
275    let mut mutants = Vec::new();
276    let mut emit_sites = Vec::new();
277    let mut seen_ids = std::collections::BTreeSet::new();
278    for site in collected.sites {
279        let kept = select_candidates(source, &site, &collected.statement_starts, options);
280        if kept.is_empty() {
281            continue;
282        }
283        let mut emit_mutants = Vec::with_capacity(kept.len());
284        for candidate in kept {
285            let id = unique_id(path, source, &site, &candidate, &mut seen_ids);
286            let (line, column) = line_column(&line_starts, candidate.region.0);
287            emit_mutants.push(emit::EmitMutant {
288                id: id.0.clone(),
289                region: candidate.region,
290                replacement: candidate.replacement.clone(),
291            });
292            mutants.push(Mutant {
293                id,
294                operator: candidate.operator,
295                span: candidate.region,
296                line,
297                column,
298                original: slice(source, candidate.region).to_owned(),
299                replacement: candidate.replacement,
300                enclosing_function: site.function.clone(),
301            });
302        }
303        emit_sites.push(emit::EmitSite {
304            span: site.span,
305            mutants: emit_mutants,
306        });
307    }
308    mutants.sort_by_key(|mutant| mutant.span);
309    let (code, map) = emit::emit(
310        source,
311        &emit_sites,
312        &collected.statement_starts,
313        &insertions,
314    );
315    // The splice map holds `u32` offsets. When the output fits, no offset
316    // was truncated.
317    if u32::try_from(code.len()).is_err() {
318        return Err(MutationError::TooLarge);
319    }
320    Ok(Instrumented { mutants, code, map })
321}
322
323/// The first binding in `program` with the name of a prelude function.
324fn reserved_binding(program: &oxc_ast::ast::Program<'_>) -> Option<String> {
325    use oxc_ast_visit::Visit;
326
327    #[derive(Default)]
328    struct Finder {
329        found: Option<String>,
330    }
331    impl<'a> Visit<'a> for Finder {
332        fn visit_binding_identifier(&mut self, it: &oxc_ast::ast::BindingIdentifier<'a>) {
333            let name = it.name.as_str();
334            if self.found.is_none() && (name == ACTIVE_FUNCTION || name == HIT_FUNCTION) {
335                self.found = Some(name.to_owned());
336            }
337        }
338    }
339
340    let mut finder = Finder::default();
341    finder.visit_program(program);
342    finder.found
343}
344
345/// The prelude: two function declarations that call the runtime.
346///
347/// The prelude uses hoisted function declarations, not a `const`. In a module
348/// cycle, another module can call a hoisted function of this module before
349/// the prelude line runs. A `const` binding is then in its temporal dead
350/// zone and throws a `ReferenceError`. A function declaration exists from
351/// the start of the module, and each call reads the runtime object again.
352/// Two classic scripts can also declare the same functions without a
353/// redeclaration error.
354const PRELUDE: &str = "function __fallow_m_a(id) { const m = globalThis.__fallowMutation; return m ? m.a(id) : false; } function __fallow_m_c(id) { const m = globalThis.__fallowMutation; if (m) m.c(id); }";
355
356const TS_NOCHECK: &str = "// @ts-nocheck";
357
358/// The `// @ts-nocheck` comment goes after the hashbang and the leading
359/// comments, so that pragmas such as `@jsxImportSource` stay before the first
360/// token. The prelude goes after the directive prologue, so that
361/// `"use strict"` and `"use client"` stay the first statements.
362///
363/// A directive can share a line with the last leading comment. The line
364/// comment then ends with a newline, or the directive and the prelude become
365/// comment text.
366fn header_insertions(program: &oxc_ast::ast::Program<'_>, source: &str) -> Vec<emit::Insertion> {
367    let offset = leading_end(program, source);
368    let line_break_follows = source
369        .get(offset as usize..)
370        .is_some_and(|rest| rest.starts_with(['\n', '\r', '\u{2028}', '\u{2029}']));
371    let nocheck = if offset == 0 {
372        format!("{TS_NOCHECK}\n")
373    } else if program.directives.is_empty() || line_break_follows {
374        format!("\n{TS_NOCHECK}")
375    } else {
376        format!("\n{TS_NOCHECK}\n")
377    };
378    let Some(last) = program.directives.last() else {
379        let text = if offset == 0 {
380            format!("{nocheck}{PRELUDE}\n")
381        } else {
382            format!("{nocheck}\n{PRELUDE}")
383        };
384        return vec![emit::Insertion { offset, text }];
385    };
386    let end = last.span.end;
387    let terminated = source
388        .get(..end as usize)
389        .is_some_and(|text| text.ends_with(';'));
390    let separator = if terminated { "" } else { ";" };
391    vec![
392        emit::Insertion {
393            offset,
394            text: nocheck,
395        },
396        emit::Insertion {
397            offset: end,
398            text: format!("{separator}{PRELUDE}"),
399        },
400    ]
401}
402
403/// The end of the hashbang and of the comments before the first token.
404fn leading_end(program: &oxc_ast::ast::Program<'_>, source: &str) -> u32 {
405    use oxc_span::GetSpan;
406    let first_token = program
407        .directives
408        .first()
409        .map(|directive| directive.span.start)
410        .or_else(|| program.body.first().map(|statement| statement.span().start))
411        .unwrap_or(source.len() as u32);
412    let hashbang_end = program
413        .hashbang
414        .as_ref()
415        .map_or(0, |hashbang| hashbang.span.end);
416    program
417        .comments
418        .iter()
419        .take_while(|comment| comment.span.end <= first_token)
420        .map(|comment| comment.span.end)
421        .last()
422        .map_or(hashbang_end, |end| end.max(hashbang_end))
423}
424
425fn slice(source: &str, span: (u32, u32)) -> &str {
426    source
427        .get(span.0 as usize..span.1 as usize)
428        .unwrap_or_default()
429}
430
431/// Applies the operator and range options, then drops candidates that give
432/// the original text or the same text as an earlier candidate of the site.
433fn select_candidates(
434    source: &str,
435    site: &collect::Site,
436    statement_starts: &std::collections::BTreeSet<u32>,
437    options: &MutationOptions,
438) -> Vec<collect::Candidate> {
439    let original = slice(source, site.span);
440    let mut texts = std::collections::BTreeSet::new();
441    let mut kept = Vec::new();
442    for candidate in &site.candidates {
443        if !options.operators.contains(&candidate.operator) {
444            continue;
445        }
446        let (start, end) = candidate.region;
447        let in_range = options
448            .ranges
449            .as_ref()
450            .is_none_or(|ranges| ranges.iter().any(|&(from, to)| start < to && from < end));
451        if !in_range {
452            continue;
453        }
454        let replacement = guard_statement_start(source, statement_starts, candidate);
455        let mutated = format!(
456            "{}{}{}",
457            slice(source, (site.span.0, start)),
458            replacement,
459            slice(source, (end, site.span.1)),
460        );
461        if mutated == original || !texts.insert(mutated) {
462            continue;
463        }
464        kept.push(collect::Candidate {
465            operator: candidate.operator,
466            region: candidate.region,
467            replacement,
468        });
469    }
470    kept
471}
472
473/// Characters that continue the previous line when a statement starts with
474/// them and that line has no semicolon.
475const ASI_HAZARDS: [char; 6] = ['(', '[', '`', '+', '-', '/'];
476
477/// True when a statement that starts with `text` can join the line before it.
478/// A prefix `++` or `--` cannot, because the postfix forms forbid a line
479/// break before the operator.
480fn starts_with_asi_hazard(text: &str) -> bool {
481    let hazard = text.starts_with(ASI_HAZARDS);
482    hazard && !text.starts_with("++") && !text.starts_with("--")
483}
484
485/// Prefixes `void` to a replacement that starts an expression statement with
486/// an ASI hazard, so that the original source with the replacement applied
487/// keeps the statement boundary. When the original also starts with a hazard,
488/// the line before it already ends the statement, and no prefix is needed.
489fn guard_statement_start(
490    source: &str,
491    statement_starts: &std::collections::BTreeSet<u32>,
492    candidate: &collect::Candidate,
493) -> String {
494    let (start, end) = candidate.region;
495    let guarded = statement_starts.contains(&start)
496        && starts_with_asi_hazard(&candidate.replacement)
497        && !starts_with_asi_hazard(slice(source, (start, end)));
498    if !guarded {
499        return candidate.replacement.clone();
500    }
501    // `do!f()` has no space after the keyword; `dovoid` would be a name.
502    let joins = source
503        .as_bytes()
504        .get((start as usize).wrapping_sub(1))
505        .is_some_and(|&byte| is_identifier_byte(byte));
506    let prefix = if joins { " void " } else { "void " };
507    format!("{prefix}{}", candidate.replacement)
508}
509
510fn unique_id(
511    path: &str,
512    source: &str,
513    site: &collect::Site,
514    candidate: &collect::Candidate,
515    seen: &mut std::collections::BTreeSet<MutantId>,
516) -> MutantId {
517    let anchor_start = site.anchor.0;
518    let input = id::IdInput {
519        path,
520        anchor_text: slice(source, site.anchor),
521        relative: (
522            candidate.region.0.saturating_sub(anchor_start),
523            candidate.region.1.saturating_sub(anchor_start),
524        ),
525        operator: candidate.operator,
526        replacement: &candidate.replacement,
527    };
528    let mut occurrence = 0;
529    loop {
530        let id = id::mutant_id(&input, occurrence);
531        if seen.insert(id.clone()) {
532            return id;
533        }
534        occurrence += 1;
535    }
536}
537
538fn line_starts(source: &str) -> Vec<u32> {
539    std::iter::once(0)
540        .chain(
541            source
542                .match_indices('\n')
543                .map(|(index, _)| index as u32 + 1),
544        )
545        .collect()
546}
547
548fn line_column(line_starts: &[u32], offset: u32) -> (u32, u32) {
549    let index = line_starts
550        .partition_point(|&start| start <= offset)
551        .saturating_sub(1);
552    let start = line_starts.get(index).copied().unwrap_or(0);
553    (index as u32 + 1, offset - start)
554}
fallow_mutation/lib.rs

fallow_mutation/
lib.rs
