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 &gt; Two. VectorComparison.EQUAL If One =
181         * Two. VectorComparison.SMALLER If One &lt; 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}