vorma 0.86.0-pre.4

//! The request plan: one build's client views and the application's
//! declarations compiled into matchers. One nested matcher covers every view
//! position that has a loader, a client view, or both. One flat matcher per
//! method covers endpoints, and one flat matcher per task middleware covers
//! its own patterns.

use std::cmp::Ordering;
use std::collections::HashMap;
use std::fmt;
use std::sync::{Arc, Mutex, PoisonError};

use http::Method;
use primitives_rs::matcher::{
	FlatMatcher, FlatPattern, FlatPatternLanguage, FlatPatternOptions, NestedMatcher,
	NestedPattern, NestedPatternLanguage, NestedPatternOptions, Pattern, PatternComparison,
	Segment, compare_matching_patterns, patterns_can_match_one_path,
};
use vorma_path_wire::{
	DYNAMIC_PARAM_PREFIX, INDEX_SEGMENT, PathWireError, SPLAT_SEGMENT, canonicalize_pattern,
	decode_path_segment,
};

use crate::build_output::{BuildSnapshot, ClientModule};
use crate::declarations::{ApiEndpoint, ApiEndpointInputKind, TaskMiddleware, ViewLoader};
use crate::pattern::DecodedMatch;
use crate::search::{DEPLOYMENT_QUERY_KEY, SearchShape};

fn create_nested_language() -> NestedPatternLanguage {
	NestedPatternLanguage::new(NestedPatternOptions {
		dynamic_param_prefix: DYNAMIC_PARAM_PREFIX,
		splat_segment_identifier: SPLAT_SEGMENT,
		explicit_index_segment_identifier: INDEX_SEGMENT.to_owned(),
	})
	.expect("Vorma's nested pattern language is valid")
}

fn create_flat_language() -> FlatPatternLanguage {
	FlatPatternLanguage::new(FlatPatternOptions {
		dynamic_param_prefix: DYNAMIC_PARAM_PREFIX,
		splat_segment_identifier: SPLAT_SEGMENT,
	})
	.expect("Vorma's flat pattern language is valid")
}

/// Compiles an authored flat pattern after encoding it into matcher wire
/// spelling.
fn compile_flat_pattern(
	language: &FlatPatternLanguage,
	pattern: &str,
) -> Result<FlatPattern, String> {
	let wire = canonicalize_pattern(pattern).map_err(|error| error.to_string())?;
	language
		.compile_pattern(&wire)
		.map_err(|error| error.to_string())
}

/// Compiles an authored nested pattern after encoding it into matcher wire
/// spelling.
fn compile_nested_pattern(
	language: &NestedPatternLanguage,
	pattern: &str,
) -> Result<NestedPattern, String> {
	let wire = canonicalize_pattern(pattern).map_err(|error| error.to_string())?;
	language
		.compile_pattern(&wire)
		.map_err(|error| error.to_string())
}

/// The application's declarations, shared by every plan.
pub(crate) struct Declarations<State> {
	pub(crate) task_middlewares: Vec<TaskMiddleware<State>>,
	pub(crate) view_loaders: Vec<ViewLoader<State>>,
	pub(crate) api_endpoints: Vec<ApiEndpoint<State>>,
}

impl<State> Declarations<State> {
	/// The problems of the search shapes that declare a top-level field
	/// named `dpl`, which Vercel skew protection reserves while it is on.
	pub(crate) fn find_skew_protection_search_problems(&self) -> Vec<String> {
		let view_loaders = self.view_loaders.iter().filter_map(|declaration| {
			let search = (declaration.derive_search_shape_fn)().ok()??;
			Some((declaration.describe(), search))
		});
		let api_endpoints = self.api_endpoints.iter().filter_map(|declaration| {
			let reads_search = (declaration.determine_input_kind_fn)(&declaration.method).ok()?
				== ApiEndpointInputKind::Search;
			let search = reads_search
				.then(|| (declaration.derive_search_shape_fn)().ok())
				.flatten()?;
			Some((declaration.describe(), search))
		});
		view_loaders
			.chain(api_endpoints)
			.filter(|(_, search)| search.has_top_level_field(DEPLOYMENT_QUERY_KEY))
			.map(|(location, _)| {
				format!(
					"{location}: its search input declares the field {DEPLOYMENT_QUERY_KEY:?}, which Vercel skew protection reserves"
				)
			})
			.collect()
	}
}

/// A view loader with its search shape.
pub(crate) struct ViewLoaderNode<State> {
	pub(crate) declaration: ViewLoader<State>,
	pub(crate) search: Option<SearchShape>,
}

/// One view: a loader, a client definition, or both. A view that defines no
/// explicit component, such as one with a loader and no client definition or a
/// client definition without a `component`, is a pass-through view: the client
/// renders its child in its place.
pub(crate) struct ViewNode<State> {
	/// The authored identity exposed to application and browser code.
	pub(crate) pattern: String,
	pub(crate) compiled_pattern: NestedPattern,
	pub(crate) loader: Option<Arc<ViewLoaderNode<State>>>,
	/// The loaders at and above this position with search fields that compose
	/// into its input, outermost first.
	pub(crate) search_owners: Vec<Arc<ViewLoaderNode<State>>>,
	pub(crate) client_view_module: Option<ClientModule>,
}

pub(crate) struct ApiEndpointNode<State> {
	pub(crate) declaration: ApiEndpoint<State>,
	pub(crate) input_kind: ApiEndpointInputKind,
	pub(crate) search: Option<SearchShape>,
}

pub(crate) struct MiddlewareNode<State> {
	pub(crate) declaration: TaskMiddleware<State>,
	/// The patterns that the middleware lists, joined with spaces, as its
	/// reports name them.
	pub(crate) pattern: Arc<str>,
	/// `None` when the middleware lists no patterns.
	matcher: Option<FlatMatcher<()>>,
}

/// One matched view position and the params and splat values of its own pattern.
pub(crate) struct ViewPosition<'plan, State> {
	pub(crate) node: &'plan ViewNode<State>,
	pub(crate) decoded_match: DecodedMatch,
}

pub(crate) enum ClassifiedRequest<'plan, State> {
	ApiEndpoint {
		node: &'plan ApiEndpointNode<State>,
		decoded_match: DecodedMatch,
	},
	/// Outermost to innermost.
	View {
		positions: Vec<ViewPosition<'plan, State>>,
	},
	Unmatched,
}

pub(crate) struct Plan<State> {
	pub(crate) snapshot: Arc<BuildSnapshot>,
	view_nodes: Vec<ViewNode<State>>,
	view_matcher: NestedMatcher<usize>,
	view_by_authored_pattern: HashMap<String, usize>,
	api_endpoint_nodes: Vec<ApiEndpointNode<State>>,
	api_endpoint_matchers: HashMap<Method, FlatMatcher<usize>>,
	api_endpoint_by_method_and_pattern: HashMap<(Method, &'static str), usize>,
	middleware: Vec<MiddlewareNode<State>>,
}

/// The plan for the current build, shared by the handler and the loaded app.
/// In development, a new build gets a new plan when the handler first sees it.
pub(crate) struct CurrentPlan<State>(Mutex<PlanState<State>>);

struct PlanState<State> {
	plan: Arc<Plan<State>>,
	/// The latest snapshot that cannot form a plan, with the error, so that
	/// Vorma neither plans nor reports the same snapshot again.
	failed: Option<(Arc<BuildSnapshot>, Arc<PlanError>)>,
}

impl<State: Send + Sync + 'static> CurrentPlan<State> {
	pub(crate) fn new(plan: Arc<Plan<State>>) -> Self {
		Self(Mutex::new(PlanState { plan, failed: None }))
	}

	pub(crate) fn get(&self) -> Arc<Plan<State>> {
		Arc::clone(&self.0.lock().unwrap_or_else(PoisonError::into_inner).plan)
	}

	/// The plan for `snapshot`: the current plan when it was compiled from
	/// that snapshot, and otherwise a new plan, which becomes the current one.
	/// A snapshot that cannot form a plan is reported to the log once, and
	/// later calls with the same snapshot return the same error.
	pub(crate) fn update(
		&self,
		declarations: &Declarations<State>,
		snapshot: Arc<BuildSnapshot>,
	) -> Result<Arc<Plan<State>>, Arc<PlanError>> {
		let mut state = self.0.lock().unwrap_or_else(PoisonError::into_inner);
		if Arc::ptr_eq(&state.plan.snapshot, &snapshot) {
			return Ok(Arc::clone(&state.plan));
		}
		if let Some((failed, error)) = &state.failed
			&& Arc::ptr_eq(failed, &snapshot)
		{
			return Err(Arc::clone(error));
		}
		match Plan::compile(declarations, Arc::clone(&snapshot)) {
			Ok(plan) => {
				let plan = Arc::new(plan);
				state.plan = Arc::clone(&plan);
				state.failed = None;
				Ok(plan)
			}
			Err(error) => {
				tracing::error!(error = %error, "Vorma could not plan the new build");
				let error = Arc::new(error);
				state.failed = Some((snapshot, Arc::clone(&error)));
				Err(error)
			}
		}
	}
}

/// The declarations or the build's client views cannot form a plan.
#[derive(Debug)]
pub(crate) struct PlanError {
	pub(crate) problems: Vec<String>,
}

impl fmt::Display for PlanError {
	fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
		formatter.write_str("the Vorma app's declarations are invalid:")?;
		for problem in &self.problems {
			write!(formatter, "\n- {problem}")?;
		}
		Ok(())
	}
}

impl std::error::Error for PlanError {}

/// Methods that an endpoint may declare. A `HEAD` request is answered as the
/// `GET` request for its URL.
fn is_api_endpoint_method(method: &Method) -> bool {
	[
		Method::GET,
		Method::POST,
		Method::PUT,
		Method::PATCH,
		Method::DELETE,
		Method::OPTIONS,
	]
	.contains(method)
}

impl<State> Plan<State> {
	pub(crate) fn compile(
		declarations: &Declarations<State>,
		snapshot: Arc<BuildSnapshot>,
	) -> Result<Self, PlanError> {
		let nested = create_nested_language();
		let flat = create_flat_language();
		let mut problems = Vec::new();

		let mut loaders: Vec<(NestedPattern, Arc<ViewLoaderNode<State>>)> = Vec::new();
		for declaration in &declarations.view_loaders {
			let registered = compile_nested_pattern(&nested, declaration.pattern);
			let search = (declaration.derive_search_shape_fn)();
			match (registered, search) {
				(Ok(registered), Ok(search)) => loaders.push((
					registered,
					Arc::new(ViewLoaderNode {
						declaration: declaration.clone(),
						search,
					}),
				)),
				(registered, search) => {
					if let Err(error) = registered {
						problems.push(format!("{}: {error}", declaration.describe()));
					}
					if let Err(error) = search {
						problems.push(format!(
							"{}: its search input {error}",
							declaration.describe()
						));
					}
				}
			}
		}

		let mut endpoints: Vec<(FlatPattern, ApiEndpointNode<State>)> = Vec::new();
		for declaration in &declarations.api_endpoints {
			let describe_declaration = || declaration.describe();
			if !is_api_endpoint_method(&declaration.method) {
				problems.push(format!(
					"{}: {} is not an endpoint method",
					describe_declaration(),
					declaration.method
				));
				continue;
			}
			let input_kind = match (declaration.determine_input_kind_fn)(&declaration.method) {
				Ok(input_kind) => input_kind,
				Err(problem) => {
					problems.push(format!("{}: {problem}", describe_declaration()));
					continue;
				}
			};
			let search = if input_kind == ApiEndpointInputKind::Search {
				match (declaration.derive_search_shape_fn)() {
					Ok(search) => Some(search),
					Err(error) => {
						problems.push(format!(
							"{}: its search input {error}",
							describe_declaration()
						));
						continue;
					}
				}
			} else {
				None
			};
			match compile_flat_pattern(&flat, declaration.pattern) {
				Ok(registered) => endpoints.push((
					registered,
					ApiEndpointNode {
						declaration: declaration.clone(),
						input_kind,
						search,
					},
				)),
				Err(error) => problems.push(format!("{}: {error}", describe_declaration())),
			}
		}

		let mut middleware = Vec::new();
		let mut middleware_patterns: Vec<(&TaskMiddleware<State>, &str, FlatPattern)> = Vec::new();
		for declaration in &declarations.task_middlewares {
			let mut registered = Vec::new();
			for pattern in &declaration.patterns {
				match compile_flat_pattern(&flat, pattern) {
					Ok(compiled) => {
						middleware_patterns.push((declaration, pattern.as_str(), compiled.clone()));
						registered.push((pattern.as_str(), compiled));
					}
					Err(error) => problems.push(format!(
						"{}, pattern {pattern:?}: {error}",
						declaration.describe()
					)),
				}
			}
			let conflict_input: Vec<_> = registered
				.iter()
				.map(|(authored, compiled)| (*authored, compiled.as_pattern()))
				.collect();
			for conflict in find_param_conflicts(&conflict_input) {
				problems.push(format!("{}: {conflict}", declaration.describe()));
			}
			for method in &declaration.methods {
				if *method == Method::HEAD {
					problems.push(format!(
						"{}: a HEAD request selects middleware as the GET request for its URL, so list GET instead of HEAD",
						declaration.describe()
					));
				} else if !is_api_endpoint_method(method) {
					problems.push(format!(
						"{}: Vorma does not handle {method} requests, so middleware never runs for them",
						declaration.describe()
					));
				}
			}
			let matcher = (!declaration.patterns.is_empty()).then(|| {
				FlatMatcher::new(registered.into_iter().map(|(_, compiled)| (compiled, ())))
			});
			middleware.push(MiddlewareNode {
				pattern: Arc::from(declaration.patterns.join(" ")),
				declaration: declaration.clone(),
				matcher,
			});
		}

		check_duplicates(&loaders, &endpoints, &mut problems);

		let view_nodes = build_view_nodes(loaders, &snapshot, &nested, &mut problems);
		let view_registrations: Vec<_> = view_nodes
			.iter()
			.map(|node| (node.pattern.as_str(), node.compiled_pattern.as_pattern()))
			.collect();
		for conflict in find_param_conflicts(&view_registrations) {
			problems.push(format!("view patterns: {conflict}"));
		}
		let mut selecting_nothing = Vec::new();
		for declaration in &declarations.task_middlewares {
			if !declaration.methods.is_empty()
				&& !has_target_for_methods(declaration, &view_nodes, &endpoints)
			{
				let methods: Vec<_> = declaration.methods.iter().map(Method::as_str).collect();
				let pages = if declaration.methods.contains(&Method::GET) {
					"and no page exists"
				} else {
					"and pages are selected only by GET"
				};
				problems.push(format!(
					"{}: no API endpoint has one of this middleware's methods ({}) {pages}, so the middleware never runs",
					declaration.describe(),
					methods.join(", ")
				));
				selecting_nothing.push(declaration);
			}
		}
		for (declaration, authored, filter) in &middleware_patterns {
			// A middleware whose methods select no target is reported once, above.
			if selecting_nothing
				.iter()
				.any(|reported| std::ptr::eq(*reported, *declaration))
			{
				continue;
			}
			if !is_filter_applicable(declaration, filter.as_pattern(), &view_nodes, &endpoints) {
				problems.push(format!(
					"{}, pattern {authored:?}: no page and no API endpoint that this middleware's methods select matches any path of this pattern, so the middleware never runs for it",
					declaration.describe()
				));
			}
		}
		let mut by_method: Vec<(&Method, Vec<(&str, &Pattern)>)> = Vec::new();
		for (registered, node) in &endpoints {
			let method = &node.declaration.method;
			let entry = match by_method
				.iter_mut()
				.find(|(existing, _)| *existing == method)
			{
				Some(entry) => entry,
				None => {
					by_method.push((method, Vec::new()));
					by_method.last_mut().expect("just pushed")
				}
			};
			entry
				.1
				.push((node.declaration.pattern, registered.as_pattern()));
		}
		for (method, registrations) in &by_method {
			for conflict in find_param_conflicts(registrations) {
				problems.push(format!("{method} API endpoints: {conflict}"));
			}
		}
		for (registered, node) in &endpoints {
			if node.declaration.method != Method::GET {
				continue;
			}
			let shape = MatchingShape::of(registered.as_pattern());
			for view in &view_nodes {
				if MatchingShape::of(view.compiled_pattern.as_pattern()) == shape {
					problems.push(format!(
						"{}: this endpoint matches the same paths as the view pattern {:?}",
						node.declaration.describe(),
						view.pattern
					));
				}
			}
		}
		if !problems.is_empty() {
			return Err(PlanError { problems });
		}

		let view_matcher = NestedMatcher::new(
			view_nodes
				.iter()
				.enumerate()
				.map(|(index, node)| (node.compiled_pattern.clone(), index)),
		);
		let mut api_endpoint_registrations: HashMap<Method, Vec<(FlatPattern, usize)>> =
			HashMap::new();
		let mut api_endpoint_nodes = Vec::with_capacity(endpoints.len());
		for (index, (registered, node)) in endpoints.into_iter().enumerate() {
			api_endpoint_registrations
				.entry(node.declaration.method.clone())
				.or_default()
				.push((registered, index));
			api_endpoint_nodes.push(node);
		}
		Ok(Self {
			snapshot,
			view_by_authored_pattern: view_nodes
				.iter()
				.enumerate()
				.map(|(index, node)| (node.pattern.clone(), index))
				.collect(),
			view_nodes,
			view_matcher,
			api_endpoint_by_method_and_pattern: api_endpoint_nodes
				.iter()
				.enumerate()
				.map(|(index, node)| {
					(
						(node.declaration.method.clone(), node.declaration.pattern),
						index,
					)
				})
				.collect(),
			api_endpoint_nodes,
			api_endpoint_matchers: api_endpoint_registrations
				.into_iter()
				.map(|(method, registrations)| (method, FlatMatcher::new(registrations)))
				.collect(),
			middleware,
		})
	}

	/// A request belongs to the endpoint with the method and pattern that match it. A
	/// `GET` request can also belong to a view pattern; when both match, the more
	/// specific pattern wins, and the endpoint wins a tie.
	pub(crate) fn classify(
		&self,
		method: &Method,
		path: &str,
	) -> Result<ClassifiedRequest<'_, State>, PathWireError> {
		let endpoint = self
			.api_endpoint_matchers
			.get(method)
			.and_then(|matcher| matcher.find_best_match(path));
		let view = if method == Method::GET {
			self.view_matcher.find_nested_matches(path)
		} else {
			None
		};
		if let Some(endpoint) = endpoint {
			let wins = view
				.as_ref()
				.and_then(|matches| matches.last())
				.is_none_or(|leaf| {
					compare_matching_patterns(PatternComparison {
						left: endpoint.pattern,
						right: leaf.pattern,
					}) != Ordering::Greater
				});
			if wins {
				return Ok(ClassifiedRequest::ApiEndpoint {
					node: &self.api_endpoint_nodes[*endpoint.value],
					decoded_match: decode_match(&endpoint.params, &endpoint.splat_values)?,
				});
			}
		}
		let Some(matches) = view else {
			return Ok(ClassifiedRequest::Unmatched);
		};
		let mut positions = Vec::with_capacity(matches.len());
		for matched in matches {
			positions.push(ViewPosition {
				node: &self.view_nodes[*matched.value],
				decoded_match: decode_match(&matched.params, &matched.splat_values)?,
			});
		}
		Ok(ClassifiedRequest::View { positions })
	}

	/// The task middleware for a request, in declaration order. A request must
	/// match a listed pattern and a listed method; an empty list imposes no
	/// restriction.
	pub(crate) fn select_middleware(
		&self,
		method: &Method,
		path: &str,
	) -> Vec<&MiddlewareNode<State>> {
		self.middleware
			.iter()
			.filter(|node| {
				let methods = &node.declaration.methods;
				(methods.is_empty() || methods.contains(method))
					&& node
						.matcher
						.as_ref()
						.is_none_or(|matcher| matcher.find_best_match(path).is_some())
			})
			.collect()
	}

	/// The endpoint with this method and the pattern as the application wrote
	/// it.
	pub(crate) fn find_api_endpoint_node(
		&self,
		method: &Method,
		pattern: &'static str,
	) -> Option<&ApiEndpointNode<State>> {
		self.api_endpoint_by_method_and_pattern
			.get(&(method.clone(), pattern))
			.map(|index| &self.api_endpoint_nodes[*index])
	}

	/// A view position by the pattern that an application names: the position's
	/// index position first, then the position itself.
	pub(crate) fn find_view_node(&self, pattern: &str) -> Option<&ViewNode<State>> {
		let index_pattern = format!(
			"{}/{INDEX_SEGMENT}",
			if pattern == "/" { "" } else { pattern }
		);
		self.view_by_authored_pattern
			.get(&index_pattern)
			.or_else(|| self.view_by_authored_pattern.get(pattern))
			.map(|index| &self.view_nodes[*index])
	}
}

/// Whether a declared target has a method that the middleware selects: an
/// endpoint with one of its methods or, when the methods include `GET`, a
/// page. Middleware with no methods selects every method.
fn has_target_for_methods<State>(
	middleware: &TaskMiddleware<State>,
	view_nodes: &[ViewNode<State>],
	endpoints: &[(FlatPattern, ApiEndpointNode<State>)],
) -> bool {
	let selects =
		|method: &Method| middleware.methods.is_empty() || middleware.methods.contains(method);
	(selects(&Method::GET) && !view_nodes.is_empty())
		|| endpoints
			.iter()
			.any(|(_, node)| selects(&node.declaration.method))
}

/// Whether a request that reaches the middleware can match `filter`. Every
/// such request matches a view position, for a `GET` request, or an endpoint
/// pattern with the request's method. The check holds when the filter and
/// one of those patterns can match one path.
fn is_filter_applicable<State>(
	middleware: &TaskMiddleware<State>,
	filter: &Pattern,
	view_nodes: &[ViewNode<State>],
	endpoints: &[(FlatPattern, ApiEndpointNode<State>)],
) -> bool {
	let selects =
		|method: &Method| middleware.methods.is_empty() || middleware.methods.contains(method);
	let overlaps = |target: &Pattern| {
		patterns_can_match_one_path(PatternComparison {
			left: filter,
			right: target,
		})
	};
	(selects(&Method::GET)
		&& view_nodes
			.iter()
			.any(|node| overlaps(node.compiled_pattern.as_pattern())))
		|| endpoints.iter().any(|(registered, node)| {
			selects(&node.declaration.method) && overlaps(registered.as_pattern())
		})
}

fn decode_match(
	params: &std::collections::BTreeMap<&str, &str>,
	splat_values: &[&str],
) -> Result<DecodedMatch, PathWireError> {
	let mut decoded_params = Vec::with_capacity(params.len());
	for (name, value) in params {
		decoded_params.push(((*name).to_owned(), decode_path_segment(value)?));
	}
	let mut decoded_splat = Vec::with_capacity(splat_values.len());
	for value in splat_values {
		decoded_splat.push(decode_path_segment(value)?);
	}
	Ok(DecodedMatch::new(decoded_params, decoded_splat))
}

fn check_duplicates<State>(
	loaders: &[(NestedPattern, Arc<ViewLoaderNode<State>>)],
	endpoints: &[(FlatPattern, ApiEndpointNode<State>)],
	problems: &mut Vec<String>,
) {
	let mut seen = std::collections::HashSet::new();
	for (registered, node) in loaders {
		if !seen.insert(registered.as_pattern().as_str()) {
			problems.push(format!(
				"{}: another view loader has the same pattern",
				node.declaration.describe()
			));
		}
	}
	let mut seen = std::collections::HashSet::new();
	for (registered, node) in endpoints {
		if !seen.insert((&node.declaration.method, registered.as_pattern().as_str())) {
			problems.push(format!(
				"{}: another API endpoint has the same method and pattern",
				node.declaration.describe()
			));
		}
	}
}

/// View positions from the loaders and the build's client views, keyed by
/// registered pattern in first-registration order, with each position's
/// search owners.
fn build_view_nodes<State>(
	loaders: Vec<(NestedPattern, Arc<ViewLoaderNode<State>>)>,
	snapshot: &BuildSnapshot,
	nested: &NestedPatternLanguage,
	problems: &mut Vec<String>,
) -> Vec<ViewNode<State>> {
	let mut nodes: Vec<ViewNode<State>> = Vec::new();
	let mut by_registered: HashMap<String, usize> = HashMap::new();
	for (registered, loader) in loaders {
		// `check_duplicates` reports a second loader of a pattern. The first loader makes the
		// pattern's position.
		if by_registered.contains_key(registered.as_pattern().as_str()) {
			continue;
		}
		by_registered.insert(registered.as_pattern().as_str().to_owned(), nodes.len());
		nodes.push(ViewNode {
			pattern: loader.declaration.pattern.to_owned(),
			compiled_pattern: registered,
			loader: Some(loader),
			search_owners: Vec::new(),
			client_view_module: None,
		});
	}
	for (pattern, module) in &snapshot.metadata.client_views {
		let registered = match compile_nested_pattern(nested, pattern) {
			Ok(registered) => registered,
			Err(error) => {
				problems.push(format!("the build's client view {pattern:?}: {error}"));
				continue;
			}
		};
		match by_registered.get(registered.as_pattern().as_str()) {
			Some(&index) => {
				let node = &mut nodes[index];
				node.pattern = pattern.clone();
				node.client_view_module = Some(module.clone());
			}
			None => {
				by_registered.insert(registered.as_pattern().as_str().to_owned(), nodes.len());
				nodes.push(ViewNode {
					pattern: pattern.clone(),
					compiled_pattern: registered,
					loader: None,
					search_owners: Vec::new(),
					client_view_module: Some(module.clone()),
				});
			}
		}
	}
	link_search_owners(&mut nodes);
	nodes
}

/// A position's branch identity: its consuming segments, which exclude index
/// and splat segments.
fn branch_key(segments: &[Segment]) -> Vec<Segment> {
	segments
		.iter()
		.filter(|segment| !matches!(segment, Segment::Index | Segment::Splat))
		.cloned()
		.collect()
}

/// Each position's outer-to-inner chain of registered positions, and from it
/// the loaders that own search fields.
fn link_search_owners<State>(nodes: &mut [ViewNode<State>]) {
	let mut branches: HashMap<Vec<Segment>, usize> = HashMap::new();
	for (index, node) in nodes.iter().enumerate() {
		if !matches!(
			node.compiled_pattern.as_pattern().segments().last(),
			Some(Segment::Index | Segment::Splat)
		) {
			branches.insert(
				node.compiled_pattern.as_pattern().segments().to_vec(),
				index,
			);
		}
	}
	let owners: Vec<Vec<Arc<ViewLoaderNode<State>>>> = nodes
		.iter()
		.enumerate()
		.map(|(index, target)| {
			let consuming = branch_key(target.compiled_pattern.as_pattern().segments());
			let mut chain = Vec::new();
			for depth in 0..=consuming.len() {
				if let Some(&branch) = branches.get(&consuming[..depth]) {
					chain.push(branch);
				}
			}
			if matches!(
				target.compiled_pattern.as_pattern().segments().last(),
				Some(Segment::Index | Segment::Splat)
			) {
				chain.push(index);
			}
			chain
				.into_iter()
				.filter_map(|position| {
					nodes[position]
						.loader
						.as_ref()
						.filter(|loader| loader.search.is_some())
						.map(Arc::clone)
				})
				.collect()
		})
		.collect();
	for (node, owners) in nodes.iter_mut().zip(owners) {
		node.search_owners = owners;
	}
}

/// The matched path shape, without parameter names. A flat pattern's
/// trailing slash counts, and an index segment does not.
#[derive(PartialEq, Eq)]
struct MatchingShape {
	has_trailing_slash: bool,
	segments: Vec<Option<String>>,
	has_splat: bool,
}

impl MatchingShape {
	fn of(pattern: &Pattern) -> Self {
		let mut segments = Vec::new();
		let mut has_splat = false;
		for segment in pattern.segments() {
			match segment {
				Segment::Static { value } => segments.push(Some(value.clone())),
				Segment::Dynamic { .. } => segments.push(None),
				Segment::Splat => has_splat = true,
				Segment::Index => {}
			}
		}
		Self {
			has_trailing_slash: pattern.has_trailing_slash(),
			segments,
			has_splat,
		}
	}
}

/// Patterns in one matcher must use one parameter name at each shared
/// dynamic position. Each conflict names the pattern that arrived second.
fn find_param_conflicts(registrations: &[(&str, &Pattern)]) -> Vec<String> {
	#[derive(Default)]
	struct Branch {
		static_children: HashMap<String, Branch>,
		dynamic: Option<(String, Box<Branch>)>,
	}
	let mut root = Branch::default();
	let mut seen = std::collections::HashSet::new();
	let mut conflicts = Vec::new();
	for (authored, pattern) in registrations {
		if !seen.insert(pattern.as_str().to_owned()) {
			continue;
		}
		let mut branch = &mut root;
		for segment in pattern.segments() {
			match segment {
				Segment::Splat | Segment::Index => break,
				Segment::Static { value } => {
					branch = branch.static_children.entry(value.clone()).or_default();
				}
				Segment::Dynamic { param_name } => {
					let dynamic = branch
						.dynamic
						.get_or_insert_with(|| (param_name.clone(), Box::default()));
					if dynamic.0 != *param_name {
						conflicts.push(format!(
							"{authored:?} names the dynamic segment {param_name:?} where another pattern names it {:?}",
							dynamic.0
						));
						break;
					}
					branch = &mut dynamic.1;
				}
			}
		}
	}
	conflicts
}