view java/src/uk/ac/qmul/eecs/ccmi/network/ServerLockManager.java @ 0:78b7fc5391a2

first import, outcome of NIME 2014 hackaton

/*  
 CCmI Editor - A Collaborative Cross-Modal Diagram Editing Tool
  
 Copyright (C) 2011  Queen Mary University of London (http://ccmi.eecs.qmul.ac.uk/)

 This program is free software: you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation, either version 3 of the License, or
 (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/  

package uk.ac.qmul.eecs.ccmi.network;

import java.nio.channels.SocketChannel;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import javax.swing.tree.TreeNode;

import uk.ac.qmul.eecs.ccmi.diagrammodel.DiagramElement;
import uk.ac.qmul.eecs.ccmi.diagrammodel.DiagramTreeNode;
import uk.ac.qmul.eecs.ccmi.diagrammodel.EdgeReferenceHolderMutableTreeNode;
import uk.ac.qmul.eecs.ccmi.diagrammodel.EdgeReferenceMutableTreeNode;
import uk.ac.qmul.eecs.ccmi.diagrammodel.NodeReferenceMutableTreeNode;
import uk.ac.qmul.eecs.ccmi.gui.Edge;
import uk.ac.qmul.eecs.ccmi.gui.Lock;
import uk.ac.qmul.eecs.ccmi.gui.Node;

/**
 * 
 * This class keeps track of the objects currently locked by the users.
 * Locking is done by inserting a lock entry into a list of entries. All lock types have one or more dependencies. 
 * A dependency is a lock on the same or another tree node, which prevent the lock from being acquired. 
 * The dependency lock can also be of another type of the lock we're trying to acquire. 
 * For example if I want to change the arrow head of edge E, before inserting a arrow-head lock in the list  
 * I must be sure nobody else has already entered a delete-lock for E, as it means that user is about to 
 * delete the edge I want to change the arrow of. Likewise if I want to delete a node I must be sure 
 * nobody else inserted a note-lock on a edge reference laying within that node in the tree as that edge reference 
 * will go after the node is deleted. If a user tries to acquire a lock and one or more dependencies 
 * have been already inserted in the list by other users then the lock won't be granted. I no dependency 
 * exist in the list the lock entry is created and inserted.
 * 
 * 
 * Lock dependencies (unless differently specified the dependency lock is on the same tree node): 
 * DELETE : DELETE,ARROW_HEAD,END_LABEL,MOVE,MUST_EXIST,NAME,NOTES, BOOKMARK,PROPERTIES, 
 *          DELETE on two ended edges if this is a node, NOTES and BOOKMARK on those tree node 
 *          that will be deleted as a result of this action.
 * EDGE_END : EDGE_END, DELETE 
 * MOVE : MOVE, DELETE
 * MUST_EXIST : DELETE 	
 * NAME : NAME, DELETE
 * NOTES : NOTES, DELETE, DELETE on Objects whose deletion would entail the deletion of this tree node
 *         PROPERTIES if this is a subtree of a property node. 
 * BOOKMARK : DELETE 
 * PROPERTIES : PROPERTIES, DELETE
 * 
 *
 */
class ServerLockManager { 
	public ServerLockManager(){
		locksMap = new HashMap<String,List<LockEntry>>();
	}
	
	/* check if the specified lock is present in the lock list for the specified tree node */
	private boolean lockExists(DiagramTreeNode treeNode, Lock lock, List<LockEntry> locks, SocketChannel channel){
		for(LockEntry lockEntry : locks){
			if(lockEntry.treeNode.equals(treeNode) && lockEntry.lock == lock && !lockEntry.channel.equals(channel))
				return true;
		}
		return false;
	}
	
	/* check if either specified locks is present in the lock list for the specified tree node */
	private boolean lockExists(DiagramTreeNode treeNode, Lock lock1, Lock lock2, List<LockEntry> locks, SocketChannel channel){
		for(LockEntry lockEntry : locks){
			if(lockEntry.treeNode.equals(treeNode) && (lockEntry.lock == lock1 || lockEntry.lock == lock2) && !lockEntry.channel.equals(channel) )
				return true;
		}
		return false;
	}
	
	/* Check whether the lock can be granted as it does    */  
	/* not clash with other locks owned by other clients   */
	private boolean checkLockDependencies(DiagramTreeNode treeNode, Lock lock, SocketChannel channel, List<LockEntry> locks){
		/* bookmarks are not shared, we only check them against delete-lock, as editing a  */ 
		/* bookmark on a tree node that has just been would lead to an inconsistent state  */
		if(lock != Lock.BOOKMARK)  
			for(LockEntry lockEntry : locks){
				/* if the two elements are different, there is no possible clash. Go ahead */
				if(!lockEntry.treeNode.equals(treeNode))  
					continue; 
				/* locks are reentrant, that is if a client requests a lock he's already got  * 
				 * then he's automatically granted for that lock                              */
				if(lockEntry.channel.equals(channel)){
					if(lock.equals(lockEntry.lock)){
						return true;
					}
					continue; //if the clients has ad different lock then just go ahead
				}
				/* DELETE depends on all the other locks and all the other locks depend  on it  */ 
				/* (bear in mind that at this point of the code lockEntry.treeNode == treeNode) */
				if(lock == Lock.DELETE||lockEntry.lock == Lock.DELETE)  
					return false;
				/* unless the lock is of type MUST_EXIST, if someone else has the desired lock, then the client   */
				/* cannot get it that is, only MUST_EXIST can be shared by different clients at the same time     */
				if(lock != Lock.MUST_EXIST && lock == lockEntry.lock)
					return false;
			}
		
		/* delete-locks on nodes and edges involved with treeNode will prevent from acquiring the lock as treeNode might     */
		/* no longer exist after the editing. See the following comments to figure out what "involved" means in this context */ 
		if(lock == Lock.NOTES || lock == Lock.BOOKMARK){
			/* no diagram element along the path from root to this treeNode must be delete-locked or properties-locked */
			/* (as editing a property might mean delete some tree nodes and, maybe, this tree node)                    */
			for(TreeNode tn : treeNode.getPath()){
				if(tn instanceof DiagramElement)
					if(lockExists((DiagramElement)tn,Lock.DELETE,Lock.PROPERTIES,locks,channel))
						return false;
			}
			/* if note-locking a reference tree node, the referred diagram element must not be delete-locked */
			/* as the reference will go as well after the diagram element will be deleted                    */
			if(treeNode instanceof NodeReferenceMutableTreeNode){
				NodeReferenceMutableTreeNode referenceNode = (NodeReferenceMutableTreeNode)treeNode; 
				if(lockExists(referenceNode.getNode(),Lock.DELETE,locks,channel))
					return false;
			}
			if(treeNode instanceof EdgeReferenceMutableTreeNode){
				EdgeReferenceMutableTreeNode referenceNode = (EdgeReferenceMutableTreeNode)treeNode; 
				if(lockExists(referenceNode.getEdge(),Lock.DELETE,locks,channel))
					return false;
			}
			/* if note locking an edge reference tree holder which has only one child, we cannot grant    *
			 * the lock if the referred edge is delete-locked as the holder will be deleted as well after *
			 * the eventual deletion of the edge                                                          */
			if(treeNode instanceof EdgeReferenceHolderMutableTreeNode && treeNode.getChildCount() == 1){
				EdgeReferenceMutableTreeNode referenceNode = (EdgeReferenceMutableTreeNode)treeNode.getChildAt(0);
				if(lockExists(referenceNode.getEdge(),Lock.DELETE,locks,channel))
					return false;
			}
		}
		
		if(lock == Lock.DELETE){
			/* all the descendants of the element must be non notes-locked or bookmark-locked */ 
			for(@SuppressWarnings("rawtypes")
			Enumeration enumeration = treeNode.breadthFirstEnumeration(); enumeration.hasMoreElements();){
				if(lockExists((DiagramTreeNode)enumeration.nextElement(),Lock.NOTES,Lock.BOOKMARK,locks,channel))  
					return false;
			}
			
			if(treeNode instanceof Node){
				Node n = (Node)treeNode;
				/* if we want to delete a Node we must get the lock on each attached *
				 * edge as they will be deleted as well  	                         */
				for(int i =0; i< n.getEdgesNum();i++){
					Edge e = n.getEdgeAt(i);
					if(lockExists(e,Lock.DELETE,locks,channel))
						return false;
					/* In order to delete-lock a Node, no referee must be bookmark/notes-locked. The referees         *
					 * are the  NodeReferenceTreeNode's pointing to this Node */
					for(int j=0;j<e.getChildCount();j++){
						NodeReferenceMutableTreeNode nodeRef = (NodeReferenceMutableTreeNode)e.getChildAt(j);
						if(nodeRef.getNode().equals(n))
							if(lockExists(nodeRef,Lock.NOTES,Lock.BOOKMARK,locks,channel)) 
								return false;
					}
				}
			}
			
			if(treeNode instanceof Edge){
				/* for each node check whether the reference to this edge is notes-locked */
				Edge e = (Edge)treeNode;
				for(int i=0;i<e.getNodesNum();i++){
					Node n = e.getNodeAt(i);
					for(int j=0;j<n.getChildCount();j++){
						if(n.getChildAt(j) instanceof EdgeReferenceHolderMutableTreeNode){
							EdgeReferenceHolderMutableTreeNode refHolder = (EdgeReferenceHolderMutableTreeNode)n.getChildAt(j); 
							/* someone else is editing notes on the reference holder and it has only one child         */
							/* which means it will be deleted after the edge deletion, the lock cannot be granted then */ 
							if((refHolder.getChildCount() == 1) && lockExists(refHolder,Lock.NOTES,Lock.BOOKMARK,locks,channel))
								return false;
							/* if a reference tree node pointing to this edge is notes-locked, the edge can't be deleted */
							for(int k=0;k<refHolder.getChildCount();k++){
								EdgeReferenceMutableTreeNode edgeRef = (EdgeReferenceMutableTreeNode)refHolder.getChildAt(k);
								if(lockExists(edgeRef,Lock.NOTES,Lock.BOOKMARK,locks,channel))  
									return false;
							}
						}
					}
				}
			}
		}
		
		/* all the checks have been passed, the client definitely deserves the lock now */
		return true;
	}
	
	/**
	 * Request an editing lock for a tree node 
	 * 
	 * @param treeNode the treeNode the caller is trying to lock
	 * @param lock the type of lock requested 
	 * @param channel the channel works as a unique identifier for the clients
	 * @param diagramName the name of the diagram the lock is requested on
	 * @return true if the lock is successfully granted, or false otherwise (because of another client 
	 *   holding a lock which clashes with this request) 
	 */
	public boolean requestLock(DiagramTreeNode treeNode, Lock lock, SocketChannel channel,String diagramName){
//		System.out.println("lock before request:"+lockStatusDescription(diagramName)+"\n----");
		List<LockEntry> locks = locksMap.get(diagramName);
		if(locks == null){
			/* if no object in the diagram has ever been locked      */
			/*  there is no entry in the map and one must be created */
			locks = new LinkedList<LockEntry>();
			locksMap.put(diagramName,locks);
		}
		/* deleting a node will cause all the attached two-ended edges to    * 
		 * be deleted, therefore we need to lock all those edges too, before */
		if(lock == Lock.DELETE && treeNode instanceof Node){
			Node n = (Node)treeNode;
			for(int i=0; i<n.getEdgesNum();i++){
				if(n.getEdgeAt(i).getNodesNum() > 2)
					continue;
				boolean succeeded = requestLock(n.getEdgeAt(i),Lock.DELETE,channel,diagramName);
				if(!succeeded){
					/* release the previously acquired locks and return a failure */
					for(int j=0;j<i;j++){
						if(n.getEdgeAt(j).getNodesNum() == 2)
							releaseLock(n.getEdgeAt(j),Lock.DELETE,channel,diagramName);
					}
					return false;
				}
			}
		}
		
		if(!checkLockDependencies(treeNode,lock,channel,locks)){
			if(lock == Lock.DELETE && treeNode instanceof Node){
				Node n = (Node)treeNode;
				for(int j=0;j<n.getEdgesNum();j++){
					if(n.getEdgeAt(j).getNodesNum() == 2)
						releaseLock(n.getEdgeAt(j),Lock.DELETE,channel,diagramName);
				}
			}
			return false;
		}
		
		/* adds the lock only if it doesn't already exist */
		boolean add = true; 
		for(LockEntry l : locks){
			if(l.channel.equals(channel) && l.lock.equals(lock) && l.treeNode.equals(treeNode)){
				add = false;
				break;
			}
		}
		if(add)
			locks.add(new LockEntry(treeNode,lock,channel));
//		System.out.println("lock after request:"+lockStatusDescription(diagramName)+"\n----");
		return true;
	}
	/**
	 * Release a lock previously acquired 
	 * @param treeNode the tree node, whose lock is getting released
	 * @param lock the lock type
	 * @param channel the channel of the client releasing the lock
	 * @param diagramName the diagram whose tree node is affected by this call
	 * 
	 * @return true if a lock was really yielded as a result of the call
	 */
	public boolean releaseLock(DiagramTreeNode treeNode, Lock lock, SocketChannel channel, String diagramName){
		List<LockEntry> locks = locksMap.get(diagramName);
		Iterator<LockEntry> iterator = locks.iterator();
		boolean lockReleased = false;
		while(iterator.hasNext()){
			LockEntry entry = iterator.next();
			if(entry.treeNode.equals(treeNode) && entry.lock == lock && entry.channel == channel){
				iterator.remove();
				lockReleased = true;
				if(lock == Lock.DELETE && treeNode instanceof Node)
					continue; // we have to check for attached edges which must be unlocked too 
				else
					break;// if ain't a delete lock, we found what looking for and we can stop
			}
			/* if a delete lock, we have to check for attached edges which must be unlocked too */
			if(lock == Lock.DELETE && entry.treeNode instanceof Edge && treeNode instanceof Node){
				Edge e = (Edge)entry.treeNode; 
				if(e.getNodesNum() == 2){
					if(e.getNodeAt(0).equals(treeNode) || e.getNodeAt(1).equals(treeNode)){
						iterator.remove();
					}
				}
			}
		}
//		System.out.println("lock release:"+lockStatusDescription(diagramName)+"\n----");
		return lockReleased;
	}
	
	/**
	 * Removes all the locks related to a diagram element, to be called when a diagram element is deleted.
	 * If the diagram element is a Node all the locks of the two-ended edges attached to it will be 
	 * removed as well.    
	 * @param element the diagram element whose locks must be removed 
	 * @param diagramName the diagram the element has to be removed from
	 */
	public void removeLocks(DiagramElement element, String diagramName){
		List<LockEntry> locks = locksMap.get(diagramName);
		if(locks == null)
			return;
		Iterator<LockEntry> iterator = locks.iterator();
		boolean isNode = (element instanceof Node);
		while(iterator.hasNext()){
			LockEntry entry = iterator.next();
			if(entry.treeNode.equals(element)){
				iterator.remove();
			}
			/* remove the lock id it's a two ended edges locks attached to this Node */
			if(isNode && entry.treeNode instanceof Edge){
				Edge e = (Edge)entry.treeNode;
				if(e.getNodesNum() > 2)
					continue;
				if(e.getNodeAt(0).equals(element) || e.getNodeAt(1).equals(element)){
					iterator.remove();
				}
			}
		}
	}
	
	/**
	 * remove all the locks acquired by a client, this is normally called when a client disconnects
	 * @param channel the channel uniquely identifying the client
	 * @param diagramName the name of the diagram the channel is related to
	 */
	public void removeLocks(SocketChannel channel, String diagramName){
		if(!locksMap.containsKey(diagramName))
			/* this can happen if a client connects and downloads the diagram list *
			 * and then disconnects without opening any diagram                    */
			return;
		Iterator<LockEntry> itr = locksMap.get(diagramName).iterator();
		while(itr.hasNext())
			if(itr.next().channel.equals(channel))
					itr.remove();
	}
	
	public String lockStatusDescription(String diagramName){
		StringBuilder builder = new StringBuilder();
		if(locksMap.containsKey(diagramName)){
			List<LockEntry> locks = locksMap.get(diagramName);
			builder.append(diagramName).append('\n');
			for(LockEntry entry : locks){
				builder.append(entry.channel.socket().getInetAddress().getHostAddress()).append(' ').
					append(entry.lock).append(' ').
					append(entry.treeNode.getName()).append('\n');
			}
		}
		return builder.toString();
	}
	
	public void clearAllLocks(){ // should not be used unless in a debugging session 
		locksMap = new HashMap<String,List<LockEntry>>();
	}
	
	private Map<String,List<LockEntry>> locksMap;
	
	private static class LockEntry {
		public LockEntry(DiagramTreeNode treeNode,Lock lock,SocketChannel channel) {
			this.channel = channel;
			this.lock = lock;
			this.treeNode = treeNode;
		}
		
		public SocketChannel channel;
		public Lock lock;
		public DiagramTreeNode treeNode;
	}
}