use euclid::default::Point2D;
use petgraph::algo::{astar, dijkstra, has_path_connecting, kosaraju_scc};
#[cfg(test)]
use petgraph::stable_graph::NodeIndex;
use petgraph::visit::{EdgeRef, IntoEdgeReferences};
use rkyv::{Archive, Archived, Deserialize, Place, Resolver, Serialize, rancor::Fallible};
use std::collections::{BTreeMap, HashMap, HashSet};
use uuid::Uuid;
pub use chartulary::stemma::TransitionKind as NodeHistoryTransitionKind;
pub use muniment::Hash as ContentHash;
use crate::address::{Address, AddressKind, address_from_url, cached_host_from_url, detect_mime};
use crate::persistence::{
GraphSnapshot, PersistedAddress, PersistedArrangementEdgeData, PersistedArrangementSubKind,
PersistedContainmentEdgeData, PersistedContainmentSubKind, PersistedEdge, PersistedEdgeFamily,
PersistedImportedEdgeData, PersistedImportedSubKind, PersistedNavigationTrigger, PersistedNode,
PersistedNodeSessionState, PersistedProvenanceEdgeData, PersistedProvenanceSubKind,
PersistedSemanticEdgeData, PersistedSemanticSubKind, PersistedTraversalEdgeData,
PersistedTraversalMetrics, PersistedTraversalRecord,
};
#[allow(unused_imports)] use crate::types::{
ClassificationProvenance, ClassificationScheme, ClassificationStatus, DominantEdge,
FrameLayoutHint, FrameLayoutNodeId, GraphScope, ImportRecord, ImportRecordMembership,
NodeClassification, NodeImportProvenance, NodeImportRecordSummary, NodeTagPresentationState,
SplitOrientation, format_imported_at_secs,
};
pub mod apply;
pub mod assertion_handles;
pub mod capture;
pub mod cross_graph;
pub mod journal;
pub mod legacy_content_migration;
pub(crate) mod legacy_family_attribution;
pub mod legacy_resource_migration;
#[cfg(test)]
mod legacy_resource_migration_copies_tests;
#[cfg(test)]
mod legacy_resource_migration_malformed_tests;
#[cfg(test)]
mod legacy_resource_migration_reason_tests;
pub use cross_graph::ComponentCopy;
mod assertion_write;
pub mod pending_links;
pub use pending_links::{PendingLink, PendingLinkRetention, PendingLinkRetry, PendingLinkState};
pub mod frozen_selection;
pub use frozen_selection::{FrozenSelection, OpenedFrozenSelection};
pub mod frozen_link;
pub use frozen_link::{
FROZEN_LINK, FrozenLink, FrozenLinkEndpoint, FrozenLinkSource, FrozenSourceBinding,
FrozenSourceRevision, OpenedFrozenLink,
};
#[cfg(test)]
mod assertion_handles_tests;
pub mod coverage;
#[cfg(test)]
mod frozen_link_tests;
#[cfg(test)]
mod frozen_selection_tests;
mod residency;
pub use coverage::{CoverageLayer, CoverageLimit, CoverageNote};
mod edge_admission;
pub mod edge_data;
pub mod edge_payload;
pub mod edge_taxonomy;
pub mod facet_projection;
pub mod filter;
#[cfg(feature = "fixtures")]
pub mod fixtures;
pub mod history;
pub mod identity;
mod input_key;
pub use input_key::GraphInputKey;
mod membership;
pub use membership::SurfaceNodeLifetime;
pub mod import_records;
pub mod merge;
mod navigation_check;
pub mod node;
pub mod node_facets;
pub mod node_props;
pub mod predicate_declarations;
pub mod predicate_registry;
mod relation_read;
pub mod resource;
mod resource_pair_bounds;
pub mod resource_classifications;
pub mod resource_content;
#[cfg(test)]
mod resource_content_edge_tests;
#[cfg(test)]
mod resource_content_handle_tests;
#[cfg(test)]
mod resource_content_tests;
pub mod resource_properties;
pub mod resource_tags;
pub mod revert;
pub mod source_time;
mod chart;
mod field_ops;
pub(crate) use identity::UuidAsBytes;
pub use identity::{
EdgeKey, GraphDirection, GraphIndex, GraphViewId, NodeKey, RelationKey, ResourceEdgeKey,
SurfaceNodeKey,
};
pub use assertion_write::StatementWriteError;
pub use edge_ops::Retraction;
pub use node::{Node, SurfaceNode};
pub use node_facets::{NodeFacetStore, VisitHistoryFacet};
pub use predicate_declarations::{
PredicateDeclaration, PredicateDeclarationError, PredicateDeclarations,
};
pub use predicate_registry::{
GraphStratum, built_in_predicate_stratum, built_in_relation_stratum, default_predicate_stratum,
};
pub use resource::ResourceNode;
pub use history::{
NodeHistoryBranchAlternative, NodeHistoryBranchProjection, NodeHistoryBranchVisit,
NodeHistoryOwner, NodeHistoryProjection, NodeHistorySemanticSummary, SharedNavigationMemory,
};
pub use navigation_check::NavigationIndexError;
pub use capture::{
CapturedDelta, DeltaRecorder, GraphTableStats, Malformed, Replay, ReplayRefused, Unwritable,
replay_captured_deltas, replay_captured_deltas_as_onto, replay_captured_deltas_onto,
replay_captured_deltas_onto_checked, set_captured_delta_hook, with_isolated_capture,
};
pub use journal::{
AttributedDelta, Author, AuthorKind, GraphJournal, USER_AUTHOR, journal_capture_hook,
};
pub use merge::import_edits;
pub use revert::{
Part, Revert, Touched, part_edits, part_node, part_of, part_value, recreate_node_edits,
revert_change,
};
pub use source_time::{SourceExtent, SourceTime};
pub use edge_data::{
ArrangementData, AssertionData, ContainmentData, EdgeMetrics, ImportedData, ProvenanceData,
REL_VOCAB, RelationAssertion, RelationAssertionSpec, SemanticData, SemanticStatement,
SemanticStatementSpec, StatementAssert, Traversal, TraversalData, all_semantic_sub_kinds,
predicate_iri, sub_kind_from_iri,
};
pub use edge_payload::EdgePayload;
pub use edge_taxonomy::{
ArrangementSubKind, ContainmentSubKind, EdgeAssertion, EdgeFamily, ImportedSubKind,
NavigationTrigger, ProvenanceSubKind, RelationDurability, RelationKind, RelationSelector,
SemanticSubKind,
};
pub use muniment::{LogId, Seq};
pub use numen::{
COUPLING_VOCAB, Coupling, CouplingId, CouplingResponse, EdgePath, EdgePathRule, Falloff, Field,
FieldDefinition, FieldExtent, FieldId, FieldLifecycle, NodeSelector, ScalarField, VectorField,
};
#[derive(Debug, Clone, PartialEq, Eq, Archive, Serialize, Deserialize)]
pub struct DissolvedTraversalRecord {
#[rkyv(with = UuidAsBytes)]
pub from_node_id: Uuid,
#[rkyv(with = UuidAsBytes)]
pub to_node_id: Uuid,
pub traversals: Vec<Traversal>,
}
fn normalize_import_record_memberships(memberships: &mut Vec<ImportRecordMembership>) {
memberships.sort_by(|left, right| {
left.node_id
.cmp(&right.node_id)
.then_with(|| left.suppressed.cmp(&right.suppressed))
});
let mut deduped: Vec<ImportRecordMembership> = Vec::with_capacity(memberships.len());
for membership in memberships.drain(..) {
if let Some(existing) = deduped.last_mut()
&& existing.node_id == membership.node_id
{
existing.suppressed &= membership.suppressed;
continue;
}
deduped.push(membership);
}
*memberships = deduped;
}
pub(crate) fn normalize_import_records(import_records: &mut Vec<ImportRecord>) {
let mut merged = BTreeMap::<String, ImportRecord>::new();
for mut record in import_records.drain(..) {
normalize_import_record_memberships(&mut record.memberships);
if record.record_id.trim().is_empty() {
continue;
}
let entry = merged
.entry(record.record_id.clone())
.or_insert_with(|| ImportRecord {
record_id: record.record_id.clone(),
source_id: record.source_id.clone(),
source_label: record.source_label.clone(),
imported_at_secs: record.imported_at_secs,
memberships: Vec::new(),
});
if entry.source_id.is_empty() {
entry.source_id = record.source_id.clone();
}
if entry.source_label.is_empty() {
entry.source_label = record.source_label.clone();
}
if entry.imported_at_secs == 0 {
entry.imported_at_secs = record.imported_at_secs;
} else if record.imported_at_secs != 0 {
entry.imported_at_secs = entry.imported_at_secs.min(record.imported_at_secs);
}
entry.memberships.extend(record.memberships);
}
*import_records = merged.into_values().collect();
for record in import_records.iter_mut() {
normalize_import_record_memberships(&mut record.memberships);
}
import_records.sort_by(|left, right| {
left.source_label
.cmp(&right.source_label)
.then_with(|| left.imported_at_secs.cmp(&right.imported_at_secs))
.then_with(|| left.record_id.cmp(&right.record_id))
});
}
pub(crate) fn current_unix_timestamp_secs() -> u64 {
crate::time::unix_epoch_seconds()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct RelationView {
pub from: NodeKey,
pub to: NodeKey,
pub kind: RelationKind,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SemanticEdgeView {
pub from: NodeKey,
pub to: NodeKey,
pub sub_kind: SemanticSubKind,
pub label: Option<String>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ArrangementEdgeView {
pub from: NodeKey,
pub to: NodeKey,
pub sub_kind: ArrangementSubKind,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ContainmentEdgeView {
pub from: NodeKey,
pub to: NodeKey,
pub sub_kind: ContainmentSubKind,
}
#[derive(Clone)]
pub struct Graph {
runtime_input_keys: [GraphInputKey; 4],
pub(crate) inner: chartulary::Graph<Node, EdgePayload>,
surface_node_lifetimes: HashMap<Uuid, SurfaceNodeLifetime>,
pub(crate) resources: chartulary::Graph<ResourceNode, EdgePayload>,
pub(crate) resource_facets: chartulary::FacetStore<Uuid>,
pub(crate) shown_resources: BTreeMap<Uuid, Uuid>,
pub(crate) facets: chartulary::FacetStore<Uuid>,
pub(crate) url_to_nodes: HashMap<String, Vec<NodeKey>>,
pub(crate) import_records: Vec<ImportRecord>,
pub(crate) fields: BTreeMap<Uuid, Field>,
pub(crate) couplings: BTreeMap<Uuid, Coupling>,
pub(crate) nav: SharedNavigationMemory,
revision: u64,
url_grouping_revision: u64,
content_revision: u64,
visit_revision: u64,
current_session: u64,
write_author: Author,
pub(crate) recorder: capture::Recorder,
pub(crate) pending_link_state: PendingLinkState,
pub(crate) pending_derivation_suppressed: pending_links::Suppression,
pub(crate) semantic_observation_revision: u64,
pub(crate) appearance_admission_revision: u64,
pub(crate) known_coverage: CoverageNote,
pub(crate) staged_edges: edge_admission::StagedEdges,
}
impl Graph {
pub fn new() -> Self {
Self {
runtime_input_keys: [GraphInputKey::new_source(); 4],
inner: chartulary::Graph::new(),
surface_node_lifetimes: HashMap::new(),
resources: chartulary::Graph::new(),
resource_facets: chartulary::FacetStore::new(),
shown_resources: BTreeMap::new(),
facets: chartulary::FacetStore::new(),
url_to_nodes: HashMap::new(),
import_records: Vec::new(),
fields: BTreeMap::new(),
couplings: BTreeMap::new(),
nav: SharedNavigationMemory::empty(),
revision: 0,
url_grouping_revision: 0,
content_revision: 0,
visit_revision: 0,
current_session: 0,
write_author: Author::user(),
recorder: capture::Recorder::default(),
pending_link_state: PendingLinkState::default(),
pending_derivation_suppressed: pending_links::Suppression::default(),
semantic_observation_revision: 0,
appearance_admission_revision: 0,
known_coverage: CoverageNote::default(),
staged_edges: Default::default(),
}
}
pub fn set_recorder(&mut self, recorder: Option<DeltaRecorder>) {
self.recorder.0 = recorder;
}
pub fn is_recording(&self) -> bool {
self.recorder.0.is_some()
}
pub fn write_author(&self) -> &Author {
&self.write_author
}
pub fn write_as<R>(&mut self, author: Author, write: impl FnOnce(&mut Self) -> R) -> R {
let previous = std::mem::replace(&mut self.write_author, author);
let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| write(self)));
self.write_author = previous;
match result {
Ok(value) => value,
Err(panic) => std::panic::resume_unwind(panic),
}
}
pub fn set_current_session(&mut self, session: u64) {
self.current_session = session;
}
pub fn current_session(&self) -> u64 {
self.current_session
}
pub fn revision(&self) -> u64 {
self.revision
}
pub fn url_grouping_revision(&self) -> u64 {
self.url_grouping_revision
}
pub fn content_revision(&self) -> u64 {
self.content_revision
}
pub fn visit_revision(&self) -> u64 {
self.visit_revision
}
pub fn url_grouping_key(url: &str) -> &str {
let after_scheme = url.split_once("://").map(|(_, rest)| rest).unwrap_or(url);
after_scheme
.split(['/', '?', '#'])
.next()
.unwrap_or(after_scheme)
}
fn bump_revision(&mut self) {
self.revision = self.revision.wrapping_add(1);
self.runtime_input_keys[0].advance();
}
fn bump_url_grouping_revision(&mut self) {
self.url_grouping_revision = self.url_grouping_revision.wrapping_add(1);
self.runtime_input_keys[2].advance();
}
pub(crate) fn bump_content_revision(&mut self) {
self.content_revision = self.content_revision.wrapping_add(1);
self.runtime_input_keys[1].advance();
}
pub(crate) fn bump_visit_revision(&mut self) {
self.visit_revision = self.visit_revision.wrapping_add(1);
self.runtime_input_keys[3].advance();
}
const NODE_NAMESPACE: Uuid = Uuid::from_u128(0x6D65_7265_4E4F_4445_6E61_6D65_7370_6163);
pub fn node_namespace_id(url: &str) -> Uuid {
Uuid::new_v5(&Self::NODE_NAMESPACE, url.as_bytes())
}
#[cfg(not(target_arch = "wasm32"))]
pub(crate) fn add_node(&mut self, url: String, position: Point2D<f32>) -> NodeKey {
self.add_node_with_id(Uuid::new_v4(), url, position)
}
pub(crate) fn add_node_with_id(
&mut self,
id: Uuid,
url: String,
position: Point2D<f32>,
) -> NodeKey {
self.insert_node_if_missing(id, url, position).0
}
pub(crate) fn insert_node_if_missing(
&mut self,
id: Uuid,
url: String,
_position: Point2D<f32>,
) -> (NodeKey, bool) {
let primary_address = address_from_url(&url);
let mut container = chartulary::Container::with_identity(id)
.with_address_record(primary_address)
.with_title(url.clone());
container.media_type = detect_mime(&url, None);
let (key, inserted) = self.insert_surface_node(Node {
container,
images: std::collections::BTreeMap::new(),
});
if inserted {
self.set_node_last_visited_at_ms(key, Self::epoch_ms());
self.url_to_nodes.entry(url).or_default().push(key);
self.bump_revision();
self.bump_content_revision();
}
(key, inserted)
}
pub(crate) fn remove_node(&mut self, key: NodeKey) -> bool {
if let Some(node) = self.inner.remove(key) {
for address in &node.addresses {
self.remove_url_mapping(address.as_url_str(), key);
}
let node_id = node.id;
self.surface_node_lifetimes.remove(&node_id);
self.shown_resources.remove(&node_id);
self.remove_facets_for_node(node_id);
let removed_id = node_id.to_string();
for record in &mut self.import_records {
record
.memberships
.retain(|membership| membership.node_id != removed_id);
}
self.import_records
.retain(|record| !record.memberships.is_empty());
self.bump_revision();
self.bump_content_revision();
true
} else {
false
}
}
pub(crate) fn update_node_url(&mut self, key: NodeKey, new_url: String) -> Option<String> {
let node = self.inner.node_mut(key)?;
let old_url = node.primary_address().as_url_str().to_string();
let host_changed = cached_host_from_url(&old_url) != cached_host_from_url(&new_url);
let site_group_changed =
Self::url_grouping_key(&old_url) != Self::url_grouping_key(&new_url);
if host_changed {
node.clear_image(crate::types::ImageRole::Favicon);
}
let new_primary_address = address_from_url(&new_url);
if let Some(primary) = node.addresses.first_mut() {
*primary = new_primary_address;
}
let url_changed = old_url != new_url;
self.remove_url_mapping(&old_url, key);
self.url_to_nodes.entry(new_url).or_default().push(key);
if site_group_changed {
self.bump_url_grouping_revision();
}
if url_changed {
self.bump_content_revision();
}
Some(old_url)
}
pub(crate) fn ensure_surface_resource(&mut self, key: NodeKey) -> Option<Uuid> {
self.shown_resource_id(key)
.or_else(|| self.refresh_surface_resource(key))
}
pub(crate) fn refresh_surface_resource(&mut self, key: NodeKey) -> Option<Uuid> {
let node = self.get_node(key)?;
let surface_id = node.id;
let resource = ResourceNode::new(node.primary_address().as_url_str());
let resource_id = resource.id();
if self.resource(resource_id).is_none() {
let record = crate::persistence::PersistedResourceRecord {
canonical_iri: resource.canonical_iri().to_string(),
facets: Vec::new(),
};
if !self.set_resource_record(resource_id, Some(record.clone())) {
return None;
}
self.record_delta(&CapturedDelta::ReplaySetResourceRecordById {
resource_id: resource_id.to_string(),
record: Some(record),
});
}
if self.set_shown_resource(surface_id, Some(resource_id)) {
self.record_delta(&CapturedDelta::ReplaySetShownResourceById {
surface_id: surface_id.to_string(),
resource_id: Some(resource_id.to_string()),
});
}
Some(resource_id)
}
pub(crate) fn navigate_node(
&mut self,
key: NodeKey,
url: &str,
transition: NodeHistoryTransitionKind,
at_ms: u64,
last_session_visited: u64,
) -> Option<Uuid> {
let id = self.inner.node(key)?.id;
self.nav.record_visit(id, url, transition, at_ms);
self.set_node_last_session_visited(key, last_session_visited);
self.update_node_url(key, url.to_string());
self.set_node_last_visited_at_ms(key, at_ms);
Some(id)
}
pub(crate) fn branch_history(
&mut self,
child: NodeKey,
parent: NodeKey,
) -> Option<(Uuid, Uuid)> {
let child_id = self.inner.node(child)?.id;
let parent_id = self.inner.node(parent)?.id;
self.nav.spawn(child_id, parent_id);
Some((child_id, parent_id))
}
pub(crate) fn node_history_back(&mut self, key: NodeKey, at_ms: u64) -> Option<String> {
let id = self.inner.node(key)?.id;
let url = self.nav.back(id, at_ms)?;
self.land_history_step(key, &url, at_ms);
Some(url)
}
pub(crate) fn node_history_forward(&mut self, key: NodeKey, at_ms: u64) -> Option<String> {
let id = self.inner.node(key)?.id;
let url = self.nav.forward(id, at_ms)?;
self.land_history_step(key, &url, at_ms);
Some(url)
}
fn land_history_step(&mut self, key: NodeKey, url: &str, at_ms: u64) {
self.update_node_url(key, url.to_string());
self.set_node_last_visited_at_ms(key, at_ms);
}
pub fn node_can_back(&self, key: NodeKey) -> bool {
self.inner
.node(key)
.is_some_and(|n| self.nav.can_back(n.id))
}
pub fn node_can_forward(&self, key: NodeKey) -> bool {
self.inner
.node(key)
.is_some_and(|n| self.nav.can_forward(n.id))
}
pub fn node_history_projection(&self, key: NodeKey) -> NodeHistoryProjection {
match self.inner.node(key) {
Some(node) => self.nav.projection(node.id),
None => NodeHistoryProjection {
entries: Vec::new(),
current_index: 0,
},
}
}
pub fn node_history_branch_projection(&self, key: NodeKey) -> NodeHistoryBranchProjection {
self.inner
.node(key)
.map(|node| self.nav.branch_projection(node.id))
.unwrap_or_default()
}
pub fn node_history_semantic_summary(&self, key: NodeKey) -> NodeHistorySemanticSummary {
self.inner
.node(key)
.map(|node| self.nav.semantic_summary(node.id))
.unwrap_or_default()
}
fn epoch_ms() -> u64 {
crate::time::unix_epoch_millis()
}
}
pub mod edge_ops;
pub mod query;
pub mod display;
pub mod snapshot;
#[cfg(test)]
mod tests;
#[cfg(test)]
#[path = "tests/resource_lifecycle.rs"]
mod resource_lifecycle_tests;