XmlDoc
API
Generated with
XmlDoc/com.phasmidsoftware.xmldoc/com.phasmidsoftware.xmldoc.merge

com.phasmidsoftware.xmldoc.merge

package com.phasmidsoftware.xmldoc.merge

Members list

Type members

Classlikes

case object CDataNode extends ContentKind

Attributes

Supertypes
trait Singleton
trait Product
trait Mirror
trait Serializable
trait Product
trait Equals
trait ContentKind
class Object
trait Matchable
class Any
Show all
Self type
CDataNode.type
object Content

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Content.type
case class Content(label: String, tag: String, attributes: Seq[(String, String)], text: Option[String] = ..., textIsCData: Boolean = ..., kind: ContentKind = ...)

The content relation c(label, content). Elements, plain-text nodes and CDATA nodes all get their own identity and their own relation, matching Lindholm's model instead of folding a leaf's character data into its parent element.

The content relation c(label, content). Elements, plain-text nodes and CDATA nodes all get their own identity and their own relation, matching Lindholm's model instead of folding a leaf's character data into its parent element.

tag and attributes are meaningful for ElementNode. text is meaningful for TextNode/CDataNode. The old fields and defaults are retained so callers constructing an element Content(label, tag, attributes) remain source-compatible; new code should prefer the factories in Content.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
sealed trait ContentKind

The kind of XML node described by a Content relation.

The kind of XML node described by a Content relation.

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
object CDataNode
object ElementNode
object TextNode
object ContentMatcher

Matches base against modified using pure content/structural similarity - no identifier needed, unlike TreeMatcher.matchBySelf. Loosely modeled on the real 3dm tool's own matcher (see MERGE.md, "the actual 3dm implementation's matcher"): exact whole-subtree content equality first (a node - and everything below it, byte for byte - is almost certainly the same node even if it moved or its siblings changed), then positional pairing for whatever's left among an already-matched parent's remaining children.

Matches base against modified using pure content/structural similarity - no identifier needed, unlike TreeMatcher.matchBySelf. Loosely modeled on the real 3dm tool's own matcher (see MERGE.md, "the actual 3dm implementation's matcher"): exact whole-subtree content equality first (a node - and everything below it, byte for byte - is almost certainly the same node even if it moved or its siblings changed), then positional pairing for whatever's left among an already-matched parent's remaining children.

Deliberately simpler than 3dm's own algorithm: no fuzzy content similarity (q-gram distance) for the positional fallback - it just pairs whatever's left, in order - and no real "copy resolution" for duplicate content (see matchByExactContent). It also never looks across an unmatched parent: a node moved to a genuinely different parent shows up as a plain delete-from-the-old- parent plus insert-into-the-new-one, not a recognized move - a real, known scope limit, not a bug.

This exists to fix a real, confirmed problem (MERGE.md, "no stable per-node identity" / "silently lose an edit..."): for a document type with nothing like IDML's Self, Pcs.label's NodePath fallback ties identity to raw position, so a deletion that shifts later siblings can make an unrelated, independent edit to one of them silently vanish from a 3-way merge. Matching by content first, and only falling back to position for the unmatched remainder, fixes exactly that: an edited-but-not-moved sibling keeps its base identity across the edit, instead of inheriting whichever base identity now happens to sit at its shifted position.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case object ElementNode extends ContentKind

Attributes

Supertypes
trait Singleton
trait Product
trait Mirror
trait Serializable
trait Product
trait Equals
trait ContentKind
class Object
trait Matchable
class Any
Show all
Self type
case object ListEnd extends Sibling

Attributes

Supertypes
trait Singleton
trait Product
trait Mirror
trait Serializable
trait Product
trait Equals
trait Sibling
class Object
trait Matchable
class Any
Show all
Self type
ListEnd.type
case object ListStart extends Sibling

Attributes

Supertypes
trait Singleton
trait Product
trait Mirror
trait Serializable
trait Product
trait Equals
trait Sibling
class Object
trait Matchable
class Any
Show all
Self type
ListStart.type
case class Matching(matched: Seq[(NodeRef, NodeRef)], onlyInLeft: Seq[NodeRef], onlyInRight: Seq[NodeRef])

The result of matching two trees: which nodes correspond (matched), and which appear in only one side (onlyInLeft/onlyInRight - candidate deletions/insertions, from the left tree's point of view).

The result of matching two trees: which nodes correspond (matched), and which appear in only one side (onlyInLeft/onlyInRight - candidate deletions/insertions, from the left tree's point of view).

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object NodePath

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
NodePath.type
case class NodePath(indices: Vector[Int])

The location of a node within a GenericElement tree: the sequence of child-element indices from the root (empty means the root itself). Kept alongside a matched/unmatched node (see NodeRef) so a future diff/merge phase can navigate back to it without re-walking the tree.

The location of a node within a GenericElement tree: the sequence of child-element indices from the root (empty means the root itself). Kept alongside a matched/unmatched node (see NodeRef) so a future diff/merge phase can navigate back to it without re-walking the tree.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class NodeRef(path: NodePath, element: GenericElement)

A node found while walking a tree, together with its location.

A node found while walking a tree, together with its location.

Value parameters

element

the node itself.

path

the node's location within its own tree.

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object Pcs

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Pcs.type
case class Pcs(parent: String, predecessor: Sibling, successor: Sibling)

The parent-child-successor relation pcs(parent, predecessor, successor): parent is the parent of both predecessor and successor, and successor immediately follows predecessor in parent's child list. A whole child list is a chain of these, linked end to end from ListStart to ListEnd; parent is identified by its own label, same as any other node.

The parent-child-successor relation pcs(parent, predecessor, successor): parent is the parent of both predecessor and successor, and successor immediately follows predecessor in parent's child list. A whole child list is a chain of these, linked end to end from ListStart to ListEnd; parent is identified by its own label, same as any other node.

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object PcsEditDetector

Detects structural/content edits between a base tree and one modified version, using Pcs.relations rather than TreeMatcher/EditDetector's Self-based matching plus per-node attribute diff. Lindholm's own formula for this ("A Three-way Merge for XML Documents", section 6): the edit set E = T* - T*0 - whatever relation appears in the modified tree's relation set but not the base's is, by definition, an edit; nothing else needs deciding, since Pcs.relations has already reduced both trees to the same uniform vocabulary of relations.

Detects structural/content edits between a base tree and one modified version, using Pcs.relations rather than TreeMatcher/EditDetector's Self-based matching plus per-node attribute diff. Lindholm's own formula for this ("A Three-way Merge for XML Documents", section 6): the edit set E = T* - T*0 - whatever relation appears in the modified tree's relation set but not the base's is, by definition, an edit; nothing else needs deciding, since Pcs.relations has already reduced both trees to the same uniform vocabulary of relations.

This is genuinely simpler than EditDetector, precisely because it doesn't try to classify what happened (insert/delete/update/move) - it just reports the raw relations PcsMerger needs to reconcile across left and right. In particular, unlike EditDetector, a plain reorder of already-matched siblings shows up here (as new Pcs relations), which PcsSpec already demonstrates EditDetector misses entirely.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
object PcsMerger

A structural merger over Pcs/Content relations - the reconciliation half of Lindholm's merge procedure ("A Three-way Merge for XML Documents", section 6: raw-merge-then-resolve- contradictions), applied to whatever PcsEditDetector finds. EditDetector/Merger still only reconcile attributes on already-matched nodes; this is what actually detects and merges a plain reorder, which they cannot (see PcsSpec/PcsEditDetectorSpec).

A structural merger over Pcs/Content relations - the reconciliation half of Lindholm's merge procedure ("A Three-way Merge for XML Documents", section 6: raw-merge-then-resolve- contradictions), applied to whatever PcsEditDetector finds. EditDetector/Merger still only reconcile attributes on already-matched nodes; this is what actually detects and merges a plain reorder, which they cannot (see PcsSpec/PcsEditDetectorSpec).

Checks all three of Lindholm's structural consistency rules: "unique successor" and "unique predecessor" (a node's position within its current parent's child list), and "unique parent" - a node claimed as a child by two genuinely different parents (e.g. Kaining's 10-group-ungroup), which the first two can't see: they only compare values sharing the same (parent, ...) key, but a node moved to a different parent changes which key it appears under at all, not the value at a shared one.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
PcsMerger.type
object PcsTreeBuilder

Reconstructs a GenericElement tree from a RelationSet, by walking it from a given root label along Pcs links - the step Lindholm's paper describes only in passing ("Tm can be reconstructed by traversing from ⊥0 level by level along the PCS relations in Δ", section 6), but that PcsMerger deliberately stops short of, since it's only meaningful once the relation set is actually consistent.

Reconstructs a GenericElement tree from a RelationSet, by walking it from a given root label along Pcs links - the step Lindholm's paper describes only in passing ("Tm can be reconstructed by traversing from ⊥0 level by level along the PCS relations in Δ", section 6), but that PcsMerger deliberately stops short of, since it's only meaningful once the relation set is actually consistent.

Elements, text and CDATA are all independent PCS nodes, so reconstruction preserves their exact order even for mixed content such as `

Hello world!`.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
case class RelationSet(pcs: Set[Pcs], content: Set[Content])

A tree, fully decomposed into Pcs and Content relations - Lindholm's representation of a tree as a set (section 2.3), which is what let his merge algorithm be defined as set operations (union, difference) rather than a tree-editing procedure. This is the foundation for an eventual MERGE.md-style merge that (unlike today's attribute-only EditDetector/Merger) can also detect and reconcile structural edits: moves and reordering (Kaining's 03-single-move, 05-move-move-divergent, 09-zorder cases).

A tree, fully decomposed into Pcs and Content relations - Lindholm's representation of a tree as a set (section 2.3), which is what let his merge algorithm be defined as set operations (union, difference) rather than a tree-editing procedure. This is the foundation for an eventual MERGE.md-style merge that (unlike today's attribute-only EditDetector/Merger) can also detect and reconcile structural edits: moves and reordering (Kaining's 03-single-move, 05-move-move-divergent, 09-zorder cases).

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
sealed trait Sibling

One end of a Pcs chain: the two children-list boundary markers from Lindholm's paper ("A Three-way Merge for XML Documents", DocEng '04, section 2.3) - ⊣ (nothing precedes the first child) and ⊢ (nothing follows the last) - plus an ordinary node, identified by its label (see Pcs.label). The markers can't be edited, so every real child is guaranteed both a predecessor and a successor, even at either end of the list.

One end of a Pcs chain: the two children-list boundary markers from Lindholm's paper ("A Three-way Merge for XML Documents", DocEng '04, section 2.3) - ⊣ (nothing precedes the first child) and ⊢ (nothing follows the last) - plus an ordinary node, identified by its label (see Pcs.label). The markers can't be edited, so every real child is guaranteed both a predecessor and a successor, even at either end of the list.

Attributes

Supertypes
class Object
trait Matchable
class Any
Known subtypes
object ListEnd
object ListStart
class SiblingNode
case class SiblingNode(label: String) extends Sibling

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait Sibling
class Object
trait Matchable
class Any
Show all
case class StructuralConflict(slot: String, baseValue: Option[String], leftValue: Option[String], rightValue: Option[String])

A genuine structural conflict: two sides impose incompatible requirements on the same relation slot (Lindholm's Update/Update and Position/Position conflicts, section 6.3), and it isn't this code's job to guess a winner. slot names what's in contention (e.g. "content of u13d", or "successor after u1 under us"); baseValue/leftValue/rightValue are each side's value there, rendered as a string (None when a side has nothing there at all - e.g. a freshly inserted node has no base value).

A genuine structural conflict: two sides impose incompatible requirements on the same relation slot (Lindholm's Update/Update and Position/Position conflicts, section 6.3), and it isn't this code's job to guess a winner. slot names what's in contention (e.g. "content of u13d", or "successor after u1 under us"); baseValue/leftValue/rightValue are each side's value there, rendered as a string (None when a side has nothing there at all - e.g. a freshly inserted node has no base value).

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case class StructuralMergeResult(relations: RelationSet, rootLabel: String, conflicts: Seq[StructuralConflict])

The result of a structural (Pcs-level) 3-way merge. relations is Δ after resolving whatever could be resolved automatically - safe to reconstruct a merged tree from by walking it from rootLabel (see PcsTreeBuilder). conflicts is everywhere that couldn't be resolved. For a conflicting slot, relations keeps the base's own value if it had one (Lindholm's rule: an edit always wins over the base, so a real conflict - two edits disagreeing - is the one case with no automatic winner); a conflicting slot with no base value at all (e.g. both sides independently insert different content at the same anchor) is simply absent from relations. Either way, relations isn't guaranteed internally consistent when conflicts is non-empty - per Lindholm, that's expected: Δ only becomes Tm once every conflict is resolved one way or another (PcsTreeBuilder.build fails cleanly rather than silently reconstructing a bad tree when it isn't).

The result of a structural (Pcs-level) 3-way merge. relations is Δ after resolving whatever could be resolved automatically - safe to reconstruct a merged tree from by walking it from rootLabel (see PcsTreeBuilder). conflicts is everywhere that couldn't be resolved. For a conflicting slot, relations keeps the base's own value if it had one (Lindholm's rule: an edit always wins over the base, so a real conflict - two edits disagreeing - is the one case with no automatic winner); a conflicting slot with no base value at all (e.g. both sides independently insert different content at the same anchor) is simply absent from relations. Either way, relations isn't guaranteed internally consistent when conflicts is non-empty - per Lindholm, that's expected: Δ only becomes Tm once every conflict is resolved one way or another (PcsTreeBuilder.build fails cleanly rather than silently reconstructing a bad tree when it isn't).

Value parameters

rootLabel

the label of base/left/right's shared root node (they're assumed to already correspond, same as everywhere else in this package).

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
case object TextNode extends ContentKind

Attributes

Supertypes
trait Singleton
trait Product
trait Mirror
trait Serializable
trait Product
trait Equals
trait ContentKind
class Object
trait Matchable
class Any
Show all
Self type
TextNode.type
object TreeMatcher

First matching prototype for idml's eventual 3-way merge (see MERGE.md): matches two GenericElement trees purely by their literal Self attribute value.

First matching prototype for idml's eventual 3-way merge (see MERGE.md): matches two GenericElement trees purely by their literal Self attribute value.

This deliberately does not attempt any content/structural heuristic matching (the "3dm-style" fallback MERGE.md describes for un-identified content) - it only reports what Self alone can tell us. That's a real scope limit: nodes with no Self at all (most obviously, story text) never appear in the result, in either the matched or the unmatched sets. It also assumes Self is unique within each tree (a real IDML invariant); if that's ever violated, whichever node is visited last silently wins the slot in the index, since this is meant as a starting point, not a validator of well-formed IDML.

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
Generated with