NoteMapMerger.java

  1. /*
  2.  * Copyright (C) 2010, Sasa Zivkov <sasa.zivkov@sap.com> and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

  11. package org.eclipse.jgit.notes;

  13. import java.io.IOException;

  15. import org.eclipse.jgit.errors.MissingObjectException;
  16. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  17. import org.eclipse.jgit.lib.AnyObjectId;
  18. import org.eclipse.jgit.lib.MutableObjectId;
  19. import org.eclipse.jgit.lib.ObjectId;
  20. import org.eclipse.jgit.lib.ObjectInserter;
  21. import org.eclipse.jgit.lib.ObjectReader;
  22. import org.eclipse.jgit.lib.Repository;
  23. import org.eclipse.jgit.merge.MergeStrategy;
  24. import org.eclipse.jgit.merge.Merger;
  25. import org.eclipse.jgit.merge.ThreeWayMerger;

  27. /**
  28.  * Three-way note tree merge.
  29.  * <p>
  30.  * Direct implementation of NoteMap merger without using
  31.  * {@link org.eclipse.jgit.treewalk.TreeWalk} and
  32.  * {@link org.eclipse.jgit.treewalk.AbstractTreeIterator}
  33.  */
  34. public class NoteMapMerger {
  35.     private static final FanoutBucket EMPTY_FANOUT = new FanoutBucket(0);

  37.     private static final LeafBucket EMPTY_LEAF = new LeafBucket(0);

  39.     private final Repository db;

  41.     private final NoteMerger noteMerger;

  43.     private final MergeStrategy nonNotesMergeStrategy;

  45.     private final ObjectReader reader;

  47.     private final ObjectInserter inserter;

  49.     private final MutableObjectId objectIdPrefix;

  51.     /**
  52.      * Constructs a NoteMapMerger with custom
  53.      * {@link org.eclipse.jgit.notes.NoteMerger} and custom
  54.      * {@link org.eclipse.jgit.merge.MergeStrategy}.
  55.      *
  56.      * @param db
  57.      *            Git repository
  58.      * @param noteMerger
  59.      *            note merger for merging conflicting changes on a note
  60.      * @param nonNotesMergeStrategy
  61.      *            merge strategy for merging non-note entries
  62.      */
  63.     public NoteMapMerger(Repository db, NoteMerger noteMerger,
  64.             MergeStrategy nonNotesMergeStrategy) {
  65.         this.db = db;
  66.         this.reader = db.newObjectReader();
  67.         this.inserter = db.newObjectInserter();
  68.         this.noteMerger = noteMerger;
  69.         this.nonNotesMergeStrategy = nonNotesMergeStrategy;
  70.         this.objectIdPrefix = new MutableObjectId();
  71.     }

  73.     /**
  74.      * Constructs a NoteMapMerger with
  75.      * {@link org.eclipse.jgit.notes.DefaultNoteMerger} as the merger for notes
  76.      * and the {@link org.eclipse.jgit.merge.MergeStrategy#RESOLVE} as the
  77.      * strategy for resolving conflicts on non-notes
  78.      *
  79.      * @param db
  80.      *            Git repository
  81.      */
  82.     public NoteMapMerger(Repository db) {
  83.         this(db, new DefaultNoteMerger(), MergeStrategy.RESOLVE);
  84.     }

  86.     /**
  87.      * Performs the merge.
  88.      *
  89.      * @param base
  90.      *            base version of the note tree
  91.      * @param ours
  92.      *            ours version of the note tree
  93.      * @param theirs
  94.      *            theirs version of the note tree
  95.      * @return merge result as a new NoteMap
  96.      * @throws java.io.IOException
  97.      */
  98.     public NoteMap merge(NoteMap base, NoteMap ours, NoteMap theirs)
  99.             throws IOException {
  100.         try {
  101.             InMemoryNoteBucket mergedBucket = merge(0, base.getRoot(),
  102.                     ours.getRoot(), theirs.getRoot());
  103.             inserter.flush();
  104.             return NoteMap.newMap(mergedBucket, reader);
  105.         } finally {
  106.             reader.close();
  107.             inserter.close();
  108.         }
  109.     }

  111.     /**
  112.      * This method is called only when it is known that there is some difference
  113.      * between base, ours and theirs.
  114.      *
  115.      * @param treeDepth
  116.      * @param base
  117.      * @param ours
  118.      * @param theirs
  119.      * @return merge result as an InMemoryBucket
  120.      * @throws IOException
  121.      */
  122.     private InMemoryNoteBucket merge(int treeDepth, InMemoryNoteBucket base,
  123.             InMemoryNoteBucket ours, InMemoryNoteBucket theirs)
  124.             throws IOException {
  125.         InMemoryNoteBucket result;

  127.         if (base instanceof FanoutBucket || ours instanceof FanoutBucket
  128.                 || theirs instanceof FanoutBucket) {
  129.             result = mergeFanoutBucket(treeDepth, asFanout(base),
  130.                     asFanout(ours), asFanout(theirs));

  132.         } else {
  133.             result = mergeLeafBucket(treeDepth, (LeafBucket) base,
  134.                     (LeafBucket) ours, (LeafBucket) theirs);
  135.         }

  137.         result.nonNotes = mergeNonNotes(nonNotes(base), nonNotes(ours),
  138.                 nonNotes(theirs));
  139.         return result;
  140.     }

  142.     private FanoutBucket asFanout(InMemoryNoteBucket bucket) {
  143.         if (bucket == null)
  144.             return EMPTY_FANOUT;
  145.         if (bucket instanceof FanoutBucket)
  146.             return (FanoutBucket) bucket;
  147.         return ((LeafBucket) bucket).split();
  148.     }

  150.     private static NonNoteEntry nonNotes(InMemoryNoteBucket b) {
  151.         return b == null ? null : b.nonNotes;
  152.     }

  154.     private InMemoryNoteBucket mergeFanoutBucket(int treeDepth,
  155.             FanoutBucket base,
  156.             FanoutBucket ours, FanoutBucket theirs) throws IOException {
  157.         FanoutBucket result = new FanoutBucket(treeDepth * 2);
  158.         // walking through entries of base, ours, theirs
  159.         for (int i = 0; i < 256; i++) {
  160.             NoteBucket b = base.getBucket(i);
  161.             NoteBucket o = ours.getBucket(i);
  162.             NoteBucket t = theirs.getBucket(i);

  164.             if (equals(o, t))
  165.                 addIfNotNull(result, i, o);

  167.             else if (equals(b, o))
  168.                 addIfNotNull(result, i, t);

  170.             else if (equals(b, t))
  171.                 addIfNotNull(result, i, o);

  173.             else {
  174.                 objectIdPrefix.setByte(treeDepth, i);
  175.                 InMemoryNoteBucket mergedBucket = merge(treeDepth + 1,
  176.                         FanoutBucket.loadIfLazy(b, objectIdPrefix, reader),
  177.                         FanoutBucket.loadIfLazy(o, objectIdPrefix, reader),
  178.                         FanoutBucket.loadIfLazy(t, objectIdPrefix, reader));
  179.                 result.setBucket(i, mergedBucket);
  180.             }
  181.         }
  182.         return result.contractIfTooSmall(objectIdPrefix, reader);
  183.     }

  185.     private static boolean equals(NoteBucket a, NoteBucket b) {
  186.         if (a == null && b == null)
  187.             return true;
  188.         return a != null && b != null && a.getTreeId().equals(b.getTreeId());
  189.     }

  191.     private void addIfNotNull(FanoutBucket b, int cell, NoteBucket child)
  192.             throws IOException {
  193.         if (child == null)
  194.             return;
  195.         if (child instanceof InMemoryNoteBucket)
  196.             b.setBucket(cell, ((InMemoryNoteBucket) child).writeTree(inserter));
  197.         else
  198.             b.setBucket(cell, child.getTreeId());
  199.     }

  201.     private InMemoryNoteBucket mergeLeafBucket(int treeDepth, LeafBucket bb,
  202.             LeafBucket ob, LeafBucket tb) throws MissingObjectException,
  203.             IOException {
  204.         bb = notNullOrEmpty(bb);
  205.         ob = notNullOrEmpty(ob);
  206.         tb = notNullOrEmpty(tb);

  208.         InMemoryNoteBucket result = new LeafBucket(treeDepth * 2);
  209.         int bi = 0, oi = 0, ti = 0;
  210.         while (bi < bb.size() || oi < ob.size() || ti < tb.size()) {
  211.             Note b = get(bb, bi), o = get(ob, oi), t = get(tb, ti);
  212.             Note min = min(b, o, t);

  214.             b = sameNoteOrNull(min, b);
  215.             o = sameNoteOrNull(min, o);
  216.             t = sameNoteOrNull(min, t);

  218.             if (sameContent(o, t))
  219.                 result = addIfNotNull(result, o);

  221.             else if (sameContent(b, o))
  222.                 result = addIfNotNull(result, t);

  224.             else if (sameContent(b, t))
  225.                 result = addIfNotNull(result, o);

  227.             else
  228.                 result = addIfNotNull(result,
  229.                         noteMerger.merge(b, o, t, reader, inserter));

  231.             if (b != null)
  232.                 bi++;
  233.             if (o != null)
  234.                 oi++;
  235.             if (t != null)
  236.                 ti++;
  237.         }
  238.         return result;
  239.     }

  241.     private static LeafBucket notNullOrEmpty(LeafBucket b) {
  242.         return b != null ? b : EMPTY_LEAF;
  243.     }

  245.     private static Note get(LeafBucket b, int i) {
  246.         return i < b.size() ? b.get(i) : null;
  247.     }

  249.     private static Note min(Note b, Note o, Note t) {
  250.         Note min = b;
  251.         if (min == null || (o != null && o.compareTo(min) < 0))
  252.             min = o;
  253.         if (min == null || (t != null && t.compareTo(min) < 0))
  254.             min = t;
  255.         return min;
  256.     }

  258.     private static Note sameNoteOrNull(Note min, Note other) {
  259.         return sameNote(min, other) ? other : null;
  260.     }

  262.     private static boolean sameNote(Note a, Note b) {
  263.         if (a == null && b == null)
  264.             return true;
  265.         return a != null && b != null && AnyObjectId.isEqual(a, b);
  266.     }

  268.     private static boolean sameContent(Note a, Note b) {
  269.         if (a == null && b == null)
  270.             return true;
  271.         return a != null && b != null
  272.                 && AnyObjectId.isEqual(a.getData(), b.getData());
  273.     }

  275.     private static InMemoryNoteBucket addIfNotNull(InMemoryNoteBucket result,
  276.             Note note) {
  277.         if (note != null) {
  278.             return result.append(note);
  279.         }
  280.         return result;
  281.     }

  283.     private NonNoteEntry mergeNonNotes(NonNoteEntry baseList,
  284.             NonNoteEntry oursList, NonNoteEntry theirsList) throws IOException {
  285.         if (baseList == null && oursList == null && theirsList == null)
  286.             return null;

  288.         ObjectId baseId = write(baseList);
  289.         ObjectId oursId = write(oursList);
  290.         ObjectId theirsId = write(theirsList);
  291.         inserter.flush();

  293.         Merger m = nonNotesMergeStrategy.newMerger(db, true);
  294.         if (m instanceof ThreeWayMerger)
  295.             ((ThreeWayMerger) m).setBase(baseId);
  296.         if (!m.merge(oursId, theirsId))
  297.             throw new NotesMergeConflictException(baseList, oursList,
  298.                     theirsList);
  299.         ObjectId resultTreeId = m.getResultTreeId();
  300.         AbbreviatedObjectId none = AbbreviatedObjectId.fromString(""); //$NON-NLS-1$
  301.         return NoteParser.parse(none, resultTreeId, reader).nonNotes;
  302.     }

  304.     private ObjectId write(NonNoteEntry list)
  305.             throws IOException {
  306.         LeafBucket b = new LeafBucket(0);
  307.         b.nonNotes = list;
  308.         return b.writeTree(inserter);
  309.     }
  310. }
Created with JaCoCo 0.8.6.202009150832