001/* 002 * Syncany, www.syncany.org 003 * Copyright (C) 2011-2016 Philipp C. Heckel <philipp.heckel@gmail.com> 004 * 005 * This program is free software: you can redistribute it and/or modify 006 * it under the terms of the GNU General Public License as published by 007 * the Free Software Foundation, either version 3 of the License, or 008 * (at your option) any later version. 009 * 010 * This program is distributed in the hope that it will be useful, 011 * but WITHOUT ANY WARRANTY; without even the implied warranty of 012 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 013 * GNU General Public License for more details. 014 * 015 * You should have received a copy of the GNU General Public License 016 * along with this program. If not, see <http://www.gnu.org/licenses/>. 017 */ 018package org.syncany.database; 019 020import java.util.TreeMap; 021import java.util.regex.Matcher; 022import java.util.regex.Pattern; 023 024/** 025 * Implements a vector clock that records the time stamps of all send and receive 026 * events. It contains functions to compare and merge two vector clocks. 027 * 028 * <p>Vector clocks are a mechanism to track events/actions across multiple distributed 029 * clients. Using vector clocks, one can determine relationships between different events. 030 * In particular: 031 * 032 * <ul> 033 * <li>Event A happened before / was caused by event B (cause)</li> 034 * <li>Event B happened after / caused event B (effect)</li> 035 * <li>Event A and B happened simultaneously (no cause/effect relationship)</li> 036 * </ul> 037 * 038 * @author Frits de Nijs 039 * @author Peter Dijkshoorn 040 * @author Philipp C. Heckel (philipp.heckel@gmail.com) 041 */ 042public class VectorClock extends TreeMap<String, Long> { 043 private static final long serialVersionUID = 109876543L; 044 045 private static final Pattern CLOCK_PATTERN = Pattern.compile("\\(([^)]*)\\)"); 046 private static final int CLOCK_PATTERN_GROUP_CONTENT = 1; 047 048 private static final Pattern ENTRY_PATTERN = Pattern.compile("([a-zA-Z]+)(\\d+)"); 049 private static final int ENTRY_PATTERN_GROUP_NAME = 1; 050 private static final int ENTRY_PATTERN_GROUP_TIME = 2; 051 052 public static final Pattern MACHINE_PATTERN = Pattern.compile("[a-zA-Z]+"); 053 054 public enum VectorClockComparison { 055 SMALLER, GREATER, EQUAL, SIMULTANEOUS; 056 } 057 058 /** 059 * Increases the component of a unit by 1. 060 * 061 * @param unit The identifier of the vector element being increased 062 * @return Returns the new clock value for the given unit 063 */ 064 public Long incrementClock(String unit) { 065 validateUnitName(unit); 066 067 Long newValue = (containsKey(unit)) ? get(unit).longValue() + 1 : 1L; 068 put(unit, newValue); 069 070 return newValue; 071 } 072 073 private void validateUnitName(String unit) { 074 if (!MACHINE_PATTERN.matcher(unit).matches()) { 075 throw new RuntimeException("Machine name cannot be empty and must be only characters (A-Z)."); 076 } 077 } 078 079 /** 080 * Set the component of a unit. 081 * 082 * @param unit The identifier of the vector element being set 083 * @param value The new value of the unit being set 084 */ 085 public void setClock(String unit, long value) { 086 validateUnitName(unit); 087 put(unit, value); 088 } 089 090 /** 091 * Retrieve the unit's value 092 * 093 * @param unit The identifier of the vector element being retrieved 094 * @return Returns the value of the unit (if existent), or <code>null</code> if it does not exist 095 */ 096 public Long getClock(String unit) { 097 return get(unit); 098 } 099 100 @Override 101 public Long get(Object unit) { // TODO [low] This should not be used, or shoul it? Why inherit from TreeMap? 102 Long lResult = super.get(unit); 103 104 if (lResult == null) { 105 lResult = 0L; 106 } 107 108 return lResult; 109 } 110 111 @Override 112 public VectorClock clone() { 113 return (VectorClock) super.clone(); 114 } 115 116 @Override 117 public String toString() { 118 /* 119 * Please note that this is an incredibly important method. 120 * It is used in hundreds of tests! Don't mess with it! 121 */ 122 123 Object[] lIDs = keySet().toArray(); 124 Object[] lRequests = values().toArray(); 125 126 StringBuilder builder = new StringBuilder(); 127 builder.append('('); 128 for (int i = 0; i < lRequests.length; i++) { 129 builder.append(lIDs[i]); 130 builder.append(lRequests[i].toString()); 131 132 if (i + 1 < lRequests.length) { 133 builder.append(','); 134 } 135 } 136 137 builder.append(')'); 138 139 return builder.toString(); 140 } 141 142 /** 143 * Converts a serialized vector clock back into a {@link VectorClock} object. 144 * @see #toString() 145 */ 146 public static VectorClock parseVectorClock(String serializedVectorClock) { 147 VectorClock vectorClock = new VectorClock(); 148 149 Matcher clockMatcher = CLOCK_PATTERN.matcher(serializedVectorClock); 150 151 if (clockMatcher.matches()) { 152 String clockContents = clockMatcher.group(CLOCK_PATTERN_GROUP_CONTENT); 153 String[] clockEntries = clockContents.split(","); 154 155 for (String clockEntry : clockEntries) { 156 Matcher clockEntryMatcher = ENTRY_PATTERN.matcher(clockEntry); 157 158 if (clockEntryMatcher.matches()) { 159 String machineName = clockEntryMatcher.group(ENTRY_PATTERN_GROUP_NAME); 160 Long clockValue = Long.parseLong(clockEntryMatcher.group(ENTRY_PATTERN_GROUP_TIME)); 161 162 vectorClock.put(machineName, clockValue); 163 } 164 else { 165 throw new IllegalArgumentException("Not a valid vector clock, entry does not match pattern: " + clockEntry); 166 } 167 } 168 169 return vectorClock; 170 } 171 else { 172 throw new IllegalArgumentException("Not a valid vector clock: " + serializedVectorClock); 173 } 174 } 175 176 /** 177 * VectorClock compare operation. Returns one of four possible values 178 * indicating how clock one relates to clock two: 179 * 180 * VectorComparison.GREATER If One > Two. VectorComparison.EQUAL If One = 181 * Two. VectorComparison.SMALLER If One < Two. VectorComparison.SIMULTANEOUS 182 * If One != Two. 183 * 184 * @param clock1 First Clock being compared. 185 * @param clock2 Second Clock being compared. 186 * @return VectorComparison value indicating how One relates to Two. 187 */ 188 public static VectorClockComparison compare(VectorClock clock1, VectorClock clock2) { 189 // Initially we assume it is all possible things. 190 boolean isEqual = true; 191 boolean isGreater = true; 192 boolean isSmaller = true; 193 194 // Go over all elements in Clock one. 195 for (String lEntry : clock1.keySet()) { 196 // Compare if also present in clock two. 197 if (clock2.containsKey(lEntry)) { 198 // If there is a difference, it can never be equal. 199 // Greater / smaller depends on the difference. 200 if (clock1.get(lEntry) < clock2.get(lEntry)) { 201 isEqual = false; 202 isGreater = false; 203 } 204 if (clock1.get(lEntry) > clock2.get(lEntry)) { 205 isEqual = false; 206 isSmaller = false; 207 } 208 } 209 // Else assume zero (default value is 0). 210 else if (clock1.get(lEntry) != 0) { 211 isEqual = false; 212 isSmaller = false; 213 } 214 } 215 216 // Go over all elements in Clock two. 217 for (String lEntry : clock2.keySet()) { 218 // Only elements we have not found in One still need to be checked. 219 if (!clock1.containsKey(lEntry) && (clock2.get(lEntry) != 0)) { 220 isEqual = false; 221 isGreater = false; 222 } 223 } 224 225 // Return based on determined information. 226 if (isEqual) { 227 return VectorClockComparison.EQUAL; 228 } 229 else if (isGreater && !isSmaller) { 230 return VectorClockComparison.GREATER; 231 } 232 else if (isSmaller && !isGreater) { 233 return VectorClockComparison.SMALLER; 234 } 235 else { 236 return VectorClockComparison.SIMULTANEOUS; 237 } 238 } 239}