665bfac0b339
reach.rs
//! What a composition's pixels can depend on, from the project in memory: the items it draws
//! and, when expressions are among them, what those expressions can read (#3184). The disk
//! cache keys a comp's frames by exactly these items, so an edit elsewhere in the project keeps
//! them.
//!
//! An expression reaches its own comp's layers (`thisComp`, `thisLayer`), the sources of the
//! layers it can read (`layer.source`, a precomp's layers through it), and other items by name:
//! `comp("Name")` and `footage("Name")`. A name given as a plain string literal is followed; a
//! computed name (`comp("Shot " + index)`), the object model's constructors and internals
//! (`new Comp(7)`, `__h`), dynamic code (`eval`, `Function`) and anything the scanner can't read
//! for sure (a regular expression literal, a template string, an escape in a name) count as
//! reaching every item of the project. The scan errs on the side of reaching more: an item
//! wrongly left out would serve a stale frame, one wrongly let in only renders again.
//!
//! Known limit (`ponytail`): an expression that builds the names of the object model's private
//! fields at run time into a variable and writes them with a computed key it reads from that
//! variable could forge another comp's id. That is deliberate tampering with the internals, not
//! an expression one writes; the scan refuses every direct form of it (`__` names, the
//! constructors, `Object`, `JSON`, `call`/`apply`/`bind`, computed writes and computed keys).
//! Upgrade: have the expression host record which items an evaluation reached.
use std::collections::{BTreeMap, BTreeSet};
use crate::{Comp, ItemId, ItemKind, LayerId, Node, Project, PropGroup, Value};
/// What an expression's text can reach outside its own comp and the layers it can read.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ExprReach {
/// Only items named by string literals: comps by `comp("…")`, footage by `footage("…")`.
Names { comps: Vec<String>, footage: Vec<String> },
/// Any item of the project.
Anything,
}
/// Names that hand an expression another item by id, run code built at run time, or give it the
/// tools to forge the object model's private fields.
const REACHES_ANYTHING: &[&str] = &[
"Comp",
"Footage",
"Layer",
"Prop",
"Markers",
"eval",
"Function",
"globalThis",
"this",
"self",
"window",
"arguments",
"constructor",
"prototype",
"Object",
"Reflect",
"Proxy",
"JSON",
"call",
"apply",
"bind",
"class",
"with",
"import",
"require",
"fromCharCode",
"fromCodePoint",
"getOwnPropertyDescriptor",
"getOwnPropertyDescriptors",
"getPrototypeOf",
"setPrototypeOf",
"defineProperty",
];
/// Keywords after which a `/` starts a regular expression.
const BEFORE_REGEX: &[&str] = &["return", "typeof", "instanceof", "in", "of", "new", "delete", "void", "throw", "case", "do", "else", "yield", "await"];
/// Keywords whose `( … )` a regular expression may follow (`if (a) /x/.test(s)`).
const CONTROL: &[&str] = &["if", "while", "for", "with"];
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Tok<'a> {
Ident(&'a str),
/// A string literal's text between its quotes; `plain` when it has no escape.
Str {
text: &'a str,
plain: bool,
},
Num,
Punct(u8),
}
/// The tokens of `text`, or `None` when it can't be read for sure.
fn tokens(text: &str) -> Option<Vec<Tok<'_>>> {
let b = text.as_bytes();
let mut out: Vec<Tok<'_>> = Vec::new();
// Per open `(`: whether a control keyword is before it; whether the last `)` closed one
// (only looked at right after a `)`).
let mut parens: Vec<bool> = Vec::new();
let mut control_close = false;
let mut i = 0;
while let Some(&c) = b.get(i) {
match c {
b' ' | b'\t' | b'\n' | b'\r' | 0x0b | 0x0c => i += 1,
b'/' if b.get(i + 1) == Some(&b'/') => {
while b.get(i).is_some_and(|c| *c != b'\n') {
i += 1;
}
}
b'/' if b.get(i + 1) == Some(&b'*') => {
let end = text.get(i + 2..)?.find("*/")?;
i += 2 + end + 2;
}
b'/' => {
if regex_may_start(out.last(), control_close) {
return None;
}
out.push(Tok::Punct(c));
i += 1;
}
b'"' | b'\'' => {
let start = i + 1;
let mut j = start;
let mut plain = true;
loop {
match *b.get(j)? {
q if q == c => break,
b'\n' | b'\r' => return None,
b'\\' => {
// Only escapes that can't spell a name: `\n`, `\t`, a quote...
if !matches!(b.get(j + 1)?, b'n' | b'r' | b't' | b'b' | b'f' | b'v' | b'\'' | b'"' | b'\\') {
return None;
}
plain = false;
j += 2;
}
_ => j += 1,
}
}
let s = text.get(start..j)?;
if s.contains("__") {
return None;
}
out.push(Tok::Str { text: s, plain });
i = j + 1;
}
b'0'..=b'9' => {
while b.get(i).is_some_and(|c| c.is_ascii_alphanumeric() || *c == b'_' || *c == b'.') {
i += 1;
}
out.push(Tok::Num);
}
b'.' if b.get(i + 1).is_some_and(u8::is_ascii_digit) => {
i += 1;
while b.get(i).is_some_and(|c| c.is_ascii_alphanumeric() || *c == b'_' || *c == b'.') {
i += 1;
}
out.push(Tok::Num);
}
c if c.is_ascii_alphabetic() || c == b'_' || c == b'$' => {
let start = i;
while b.get(i).is_some_and(|c| c.is_ascii_alphanumeric() || *c == b'_' || *c == b'$') {
i += 1;
}
out.push(Tok::Ident(text.get(start..i)?));
}
// A template string (code inside `${}`), an escaped identifier, a name in another
// alphabet: not followed.
b'`' | b'\\' => return None,
c if !c.is_ascii() => return None,
c => {
match c {
b'(' => parens.push(matches!(out.last(), Some(Tok::Ident(k)) if CONTROL.contains(k))),
b')' => control_close = parens.pop().unwrap_or(false),
_ => {}
}
out.push(Tok::Punct(c));
i += 1;
}
}
}
Some(out)
}
/// Whether a `/` after `prev` may start a regular expression literal (which the scanner doesn't
/// read: its text could hide a quote).
fn regex_may_start(prev: Option<&Tok<'_>>, control_close: bool) -> bool {
match prev {
None => true,
Some(Tok::Ident(k)) => BEFORE_REGEX.contains(k),
Some(Tok::Num | Tok::Str { .. }) => false,
Some(Tok::Punct(b')')) => control_close,
Some(Tok::Punct(b']')) => false,
Some(Tok::Punct(_)) => true,
}
}
/// What the expression `text` can reach by name, or [`ExprReach::Anything`].
pub fn expression_reach(text: &str) -> ExprReach {
expression_names(text).map_or(ExprReach::Anything, |(comps, footage)| ExprReach::Names { comps, footage })
}
/// The comp names and footage names an expression references by literal name.
/// Returns `None` when it can reach anything by a computed name or cannot be tokenised.
fn expression_names(text: &str) -> Option<(Vec<String>, Vec<String>)> {
let toks = tokens(text)?;
let (mut comps, mut footage) = (Vec::new(), Vec::new());
// Per open `[`: a computed key (`{[k]: v}`), a computed member (`o[k]`).
let mut brackets: Vec<(bool, bool)> = Vec::new();
for (i, t) in toks.iter().enumerate() {
let prev = i.checked_sub(1).and_then(|p| toks.get(p));
let next = |n: usize| toks.get(i + n);
match *t {
Tok::Ident(name) if name.starts_with("__") || REACHES_ANYTHING.contains(&name) => return None,
Tok::Ident(name @ ("comp" | "footage")) => {
// Only a call with a plain literal, not a property of something else.
let (Some(Tok::Punct(b'(')), Some(Tok::Str { text, plain: true }), Some(Tok::Punct(b')'))) = (next(1), next(2), next(3)) else { return None };
if matches!(prev, Some(Tok::Punct(b'.'))) {
return None;
}
if name == "comp" { comps.push((*text).to_string()) } else { footage.push((*text).to_string()) }
}
Tok::Punct(b'[') => {
let key = matches!(prev, Some(Tok::Punct(b'{' | b',')) | Some(Tok::Ident("get" | "set" | "static" | "async")) | Some(Tok::Punct(b'*')));
let member = matches!(prev, Some(Tok::Ident(_) | Tok::Str { .. } | Tok::Num | Tok::Punct(b')' | b']' | b'.')));
brackets.push((key, member));
}
Tok::Str { .. } if brackets.last().is_some_and(|(_, member)| *member) => return None,
Tok::Punct(b']') => {
let (key, _) = brackets.pop().unwrap_or((true, true));
// A computed key (`{[k]: v}`, `{[k]() {}}`) or a write through brackets (`o[k] = v`,
// `o[k] ||= v`, `for (o[k] in …)`, `[o[k]] = v`) could name a private field.
if key && matches!(next(1), Some(Tok::Punct(b':' | b'('))) {
return None;
}
if assigns(&toks, i + 1) || matches!(next(1), Some(Tok::Ident("in" | "of"))) {
return None;
}
}
// A destructuring write (`({a: o[k]} = v)`).
Tok::Punct(b'}') if assigns(&toks, i + 1) => return None,
_ => {}
}
}
Some((comps, footage))
}
/// Whether the tokens from `at` are an assignment operator (`=`, `+=`, `>>>=`, `??=`...), not a
/// comparison (`==`, `<=`) or an arrow (`=>`).
fn assigns(toks: &[Tok<'_>], at: usize) -> bool {
let mut op = Vec::new();
for t in toks.iter().skip(at).take(5) {
match t {
Tok::Punct(c) if b"+-*/%&|^<>?=".contains(c) => op.push(*c),
_ => break,
}
}
let Some(eq) = op.iter().position(|c| *c == b'=') else { return false };
let (before, after) = op.split_at(eq);
if after.get(1).is_some_and(|c| *c == b'=' || *c == b'>') {
return false;
}
matches!(before, b"" | b"+" | b"-" | b"*" | b"/" | b"%" | b"&" | b"|" | b"^" | b"**" | b"<<" | b">>" | b">>>" | b"&&" | b"||" | b"??")
}
/// The items a comp's pixels can depend on ([`Project::pixel_reach`]).
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct PixelReach {
/// The items whose state counts; `None`: every item of the project.
pub items: Option<BTreeSet<ItemId>>,
/// Expressions are among them: they can read every layer of the comps they reach (hidden
/// and silent ones too) and the markers, which therefore count as well (#1083).
pub expressions: bool,
/// The names expressions look items up by (`true`: a comp's, `false`: footage's), each with
/// the ids of the items of that kind that have it now, in id order (the first one is what
/// the lookup finds; another item taking or giving up the name changes it).
pub names: Vec<(bool, String, Vec<ItemId>)>,
}
/// Each property of a group and its subgroups (iterative: no depth limit to hit).
fn each_prop<'a>(g: &'a PropGroup, f: &mut dyn FnMut(&'a crate::Property) -> Option<()>) -> Option<()> {
let mut stack = vec![g];
while let Some(g) = stack.pop() {
for n in &g.children {
match n {
Node::Prop(p) => f(p)?,
Node::Group(sub) => stack.push(sub),
}
}
}
Some(())
}
impl Project {
/// The items comp `comp` draws ([`Self::silent_layers`] aside, with `heard`) and the
/// footage its precomp layers swap in (Essential Graphics Media Replacement); with an
/// expression in any of its comps, everything those expressions can reach
/// ([`expression_reach`]). Memory only: no file is looked at.
pub fn pixel_reach(&self, comp: ItemId, heard: &crate::Heard) -> PixelReach {
let Some(drawn) = self.reach_walk(comp, &|id, c| self.silent_layers(id, c, heard), &mut |_| Some(vec![])) else { return PixelReach::every() };
let has_expression = |g: &PropGroup| each_prop(g, &mut |p| p.expr.is_none().then_some(())).is_none();
if !drawn.iter().filter_map(|id| self.comp(*id)).any(|c| c.layers.iter().any(|l| has_expression(&l.props))) {
return PixelReach { items: Some(drawn), expressions: false, names: vec![] };
}
// Expressions: every layer of a comp they reach counts, and what they name.
let mut names: BTreeMap<(bool, String), Vec<ItemId>> = BTreeMap::new();
let mut scan = |p: &crate::Property| match p.expr.as_ref().map(|e| expression_reach(&e.text)) {
None => Some(vec![]),
Some(ExprReach::Anything) => None,
Some(ExprReach::Names { comps, footage }) => {
let mut found = vec![];
for (is_comp, name) in comps.into_iter().map(|n| (true, n)).chain(footage.into_iter().map(|n| (false, n))) {
let ids = self.named(is_comp, &name);
found.extend(ids.iter().copied());
names.insert((is_comp, name), ids);
}
Some(found)
}
};
let Some(mut items) = self.reach_walk(comp, &|_, _| BTreeSet::new(), &mut scan) else { return PixelReach::every() };
// A source's data is read by its name (`layer.source.sourceData`).
let footage_names: BTreeSet<&str> =
items.iter().filter_map(|id| self.item(*id)).filter(|i| matches!(i.kind, ItemKind::Footage(_))).map(|i| i.name.as_str()).collect();
let same_name: Vec<ItemId> =
self.items.values().filter(|i| matches!(i.kind, ItemKind::Footage(_)) && footage_names.contains(i.name.as_str())).map(|i| i.id).collect();
items.extend(same_name);
PixelReach { items: Some(items), expressions: true, names: names.into_iter().map(|((c, n), ids)| (c, n, ids)).collect() }
}
/// The items of one kind (`is_comp`: comps, else footage) named `name`, in id order.
fn named(&self, is_comp: bool, name: &str) -> Vec<ItemId> {
self.items
.values()
.filter(|i| i.name == name && if is_comp { matches!(i.kind, ItemKind::Comp(_)) } else { matches!(i.kind, ItemKind::Footage(_)) })
.map(|i| i.id)
.collect()
}
/// The items reached from `comp` through its layers (but those `quiet` names) and the items
/// `scan` returns for each of their properties; `None` when something reaches every item.
/// (A stack and a visited set: each item is visited once, cycles included.)
fn reach_walk(
&self,
comp: ItemId,
quiet: &dyn Fn(ItemId, &Comp) -> BTreeSet<LayerId>,
scan: &mut dyn FnMut(&crate::Property) -> Option<Vec<ItemId>>,
) -> Option<BTreeSet<ItemId>> {
let mut seen = BTreeSet::new();
let mut stack = vec![comp];
while let Some(id) = stack.pop() {
if !seen.insert(id) {
continue;
}
let Some(c) = self.comp(id) else { continue };
let quiet = quiet(id, c);
for l in c.layers.iter().filter(|l| !quiet.contains(&l.id)) {
// Every source item: a 3D model's too (it is drawn, and `layer.source` reads its
// name and size).
if let Some(item) = l.source.item() {
stack.push(item);
}
stack.extend(self.media_replacements(l)?);
let mut reached = vec![];
each_prop(&l.props, &mut |p| {
reached.extend(scan(p)?);
Some(())
})?;
stack.extend(reached);
}
}
Some(seen)
}
/// The footage a precomp layer swaps in through its Essential Properties (Media Replacement):
/// the items its overridden properties name. `None` when they can't be listed (an
/// expression or keyframes choose the item over time).
fn media_replacements(&self, layer: &crate::Layer) -> Option<Vec<ItemId>> {
let over = crate::essential::overridden(layer);
let Some(g) = crate::essential::group(layer).filter(|_| !over.is_empty()) else { return Some(vec![]) };
let mut out = vec![];
each_prop(g, &mut |p| {
if !over.contains(&p.uid) {
return Some(());
}
if p.expr.is_some() || !p.keys.is_empty() {
return None;
}
if let Value::Scalar(id) = p.value {
let item = ItemId(id.max(0.0) as u64);
if matches!(self.item(item).map(|i| &i.kind), Some(ItemKind::Footage(_))) {
out.push(item);
}
}
Some(())
})?;
Some(out)
}
}
impl PixelReach {
/// Every item of the project, with expressions.
fn every() -> PixelReach {
PixelReach { items: None, expressions: true, names: vec![] }
}
}
#[cfg(test)]
mod tests;
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.