platform/platform-impl/src/com/intellij/openapi/vfs/impl/FilePointerPartNode.java - platform/tools/idea - Git at Google

 /*
  * Copyright 2000-2014 JetBrains s.r.o.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 package com.intellij.openapi.vfs.impl;

 import com.intellij.openapi.application.ApplicationManager;
 import com.intellij.openapi.application.impl.ApplicationInfoImpl;
 import com.intellij.openapi.util.Pair;
 import com.intellij.openapi.util.SystemInfo;
 import com.intellij.openapi.util.text.StringUtil;
 import com.intellij.openapi.vfs.VirtualFile;
 import com.intellij.openapi.vfs.VirtualFileManager;
 import com.intellij.util.ArrayUtil;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;

 import java.util.List;

 // all file pointers we store in the tree with nodes corresponding to the file structure on disk
 class FilePointerPartNode {
   private static final FilePointerPartNode[] EMPTY_ARRAY = new FilePointerPartNode[0];
   @NotNull private String part; // common prefix of all file pointers beneath
   @NotNull private FilePointerPartNode[] children;
   private FilePointerPartNode parent;
   VirtualFilePointerImpl leaf;  // file pointer for this exact path (e.g. concatenation of all "part" fields down from the root)
   // in case there is file pointer exists for this part, its info is saved here
   volatile Pair<VirtualFile, String> myFileAndUrl; // must not be both null
   private volatile long myLastUpdated = -1;
   volatile int useCount;

   private int pointersUnder = 1;   // number of alive pointers in this node plus all nodes beneath
   private static final VirtualFileManager ourFileManager = VirtualFileManager.getInstance();

   FilePointerPartNode(@NotNull String part, FilePointerPartNode parent, Pair<VirtualFile,String> fileAndUrl) {
     this.part = part;
     this.parent = parent;
     children = EMPTY_ARRAY;
     myFileAndUrl = fileAndUrl;
   }

   @Override
   public String toString() {
     return part + (children.length == 0 ? "" : " -> "+children.length);
   }

   // returns the node and length of matched characters in that node, or null if there is no match
   int position(@Nullable VirtualFile parent, boolean separator, @NotNull CharSequence childName, @NotNull FilePointerPartNode[] outNode) {
     checkConsistency();

     int partStart;
     if (parent == null) {
       partStart = 0;
       outNode[0] = this;
     }
     else {
       VirtualFile gparent = parent.getParent();
       partStart = position(gparent, gparent != null && !StringUtil.equals(gparent.getNameSequence(), "/"), parent.getNameSequence(), outNode);
       if (partStart == -1) return -1;
     }

     boolean childSeparator = false;
     if (separator) {
       if (partStart == outNode[0].part.length()) {
         childSeparator = true;
       }
       else {
         int sepIndex = indexOfFirstDifferentChar("/", 0, outNode[0].part, partStart);
         if (sepIndex != 1) return -1;
         partStart++;
       }
     }
     int index = indexOfFirstDifferentChar(childName, 0, outNode[0].part, partStart);

     if (index == childName.length()) {
       return partStart+index;
     }

     if (partStart + index == outNode[0].part.length()) {
       // go to children
       for (FilePointerPartNode child : outNode[0].children) {
         int childPos = child.position(null, childSeparator, childName.subSequence(index, childName.length()), outNode);
         if (childPos != -1) return childPos;
       }
     }
     // else there is no match
     return -1;
   }

   // appends to "out" all nodes under this node whose path (beginning from this node) starts in prefix.subSequence(start), then parent.getPath(), then childName
   void getPointersUnder(@Nullable VirtualFile parent,
                         boolean separator,
                         @NotNull CharSequence childName,
                         @NotNull List<FilePointerPartNode> out) {
     FilePointerPartNode[] outNode = new FilePointerPartNode[1];
     int position = position(parent, separator, childName, outNode);
     if (position != -1) {
       FilePointerPartNode node = outNode[0];
       addAllPointersUnder(node, out);
     }
   }

   private static void addAllPointersUnder(@NotNull FilePointerPartNode node, @NotNull List<FilePointerPartNode> out) {
     if (node.leaf != null) out.add(node);
     for (FilePointerPartNode child : node.children) {
       addAllPointersUnder(child, out);
     }
   }

   boolean getPointersUnder(@NotNull String path, int start, @NotNull List<FilePointerPartNode> out) {
     checkConsistency();
     if (pointersUnder == 0) return false;
     // invariant: upper nodes are matched
     int index = indexOfFirstDifferentChar(path, start);
     if (index - start == part.length() // part matched entirely, check children
        || index == path.length() // query matched entirely, add all children to matches
     ) {
       if (index == path.length() && leaf != null) {
         out.add(this);
       }

       for (FilePointerPartNode child : children) {
         child.getPointersUnder(path, index, out);
       }
     }
     // else there is no match
     return false;
   }

   private static final boolean UNIT_TEST = ApplicationManager.getApplication().isUnitTestMode();
   void checkConsistency() {
     if (UNIT_TEST && !ApplicationInfoImpl.isInPerformanceTest()) {
       doCheckConsistency();
     }
   }

   private void doCheckConsistency() {
     int childSum = 0;
     for (FilePointerPartNode child : children) {
       childSum += child.pointersUnder;
       child.doCheckConsistency();
       assert child.parent == this;
     }
     if (leaf != null) childSum++;
     assert (useCount == 0) == (leaf == null) : useCount + " - " +leaf;
     assert pointersUnder == childSum : "expected: "+pointersUnder+"; actual: "+childSum;
   }

   @NotNull
   FilePointerPartNode findPointerOrCreate(@NotNull String path, int start, @NotNull Pair<VirtualFile, String> fileAndUrl) {
     // invariant: upper nodes are matched
     int index = indexOfFirstDifferentChar(path, start);
     if (index == path.length() // query matched entirely
       && index - start == part.length()
       )  {
       if (leaf == null) pointersUnder++;
       return this;
     }
     if (index - start == part.length() // part matched entirely, check children
       ) {
       for (FilePointerPartNode child : children) {
         // find the right child (its part should start with ours)
         int i = child.indexOfFirstDifferentChar(path, index);
         if (i != index && (i > index+1 || path.charAt(index) != '/')) {
           FilePointerPartNode node = child.findPointerOrCreate(path, index, fileAndUrl);
           if (node.leaf == null) pointersUnder++; // the new node's been created
           return node;
         }
       }
       // cannot insert to children, create child node manually
       String pathRest = path.substring(index);
       FilePointerPartNode newNode = new FilePointerPartNode(pathRest, this, fileAndUrl);
       children = ArrayUtil.append(children, newNode);
       pointersUnder++;
       return newNode;
     }
     // else there is no match
     // split
     // try to make "/" start the splitted part
     if (index > start && index != path.length() && path.charAt(index-1)== '/') index--;
     String pathRest = path.substring(index);
     FilePointerPartNode newNode = pathRest.isEmpty() ? this : new FilePointerPartNode(pathRest, this, fileAndUrl);
     String commonPredecessor = StringUtil.first(part, index - start, false);
     FilePointerPartNode splittedAway = new FilePointerPartNode(part.substring(index - start), this, myFileAndUrl);
     splittedAway.children = children;
     for (FilePointerPartNode child : children) {
       child.parent = splittedAway;
     }
     splittedAway.pointersUnder = pointersUnder;
     splittedAway.useCount = useCount;
     splittedAway.associate(leaf, myFileAndUrl);
     associate(null, null);
     useCount = 0;
     part = commonPredecessor;
     children = newNode == this ? new FilePointerPartNode[]{splittedAway} : new FilePointerPartNode[]{splittedAway, newNode};
     pointersUnder++;
     return newNode;
   }

   // return true if the root node must be deleted also
   boolean remove() {
     assert leaf != null : toString();
     associate(null, null);
     useCount = 0;
     myLastUpdated = -1;
     FilePointerPartNode node;
     for (node = this; node.parent != null; node = node.parent) {
       node.pointersUnder--;
     }
     if (--node.pointersUnder == 0) {
       node.children = EMPTY_ARRAY; // clear root node, especially in tests
       return true;
     }
     return false;
   }

   private int indexOfFirstDifferentChar(@NotNull CharSequence path, int start) {
     return indexOfFirstDifferentChar(path, start, part, 0);
   }

   @NotNull
   // returns pair.second != null always
   Pair<VirtualFile, String> update() {
     long lastUpdated = myLastUpdated;
     Pair<VirtualFile, String> fileAndUrl = myFileAndUrl;
     long fsModCount = ourFileManager.getModificationCount();
     if (lastUpdated == fsModCount) return fileAndUrl;
     VirtualFile file = fileAndUrl.first;
     String url = fileAndUrl.second;
     boolean changed = false;

     if (url == null) {
       url = file.getUrl();
       if (!file.isValid()) file = null;
       changed = true;
     }
     boolean fileIsValid = file != null && file.isValid();
     if (file != null && !fileIsValid) {
       file = null;
       changed = true;
     }
     if (file == null) {
       file = ourFileManager.findFileByUrl(url);
       fileIsValid = file != null && file.isValid();
       if (file != null) {
         changed = true;
       }
     }
     if (file != null) {
       if (fileIsValid) {
         url = file.getUrl(); // refresh url, it can differ
         changed |= !url.equals(fileAndUrl.second);
       }
       else {
         file = null; // can't find, try next time
         changed = true;
       }
     }
     Pair<VirtualFile, String> result;
     if (changed) {
       result = Pair.create(file, url);
       myFileAndUrl = result;
     }
     else {
       result = fileAndUrl;
     }
     myLastUpdated = fsModCount;
     return result;
   }

   private static int indexOfFirstDifferentChar(@NotNull CharSequence s1, int start1, @NotNull String s2, int start2) {
     boolean ignoreCase = !SystemInfo.isFileSystemCaseSensitive;
     int len1 = s1.length();
     int len2 = s2.length();
     while (start1 < len1 && start2 < len2) {
       char c1 = s1.charAt(start1);
       char c2 = s2.charAt(start2);
       if (!StringUtil.charsEqual(c1, c2, ignoreCase)) {
         return start1;
       }
       start1++;
       start2++;
     }
     return start1;
   }

   void associate(VirtualFilePointerImpl pointer, Pair<VirtualFile, String> fileAndUrl) {
     if (pointer != null) {
       pointer.myNode = this;
     }
     leaf = pointer;
     myFileAndUrl = fileAndUrl;
     myLastUpdated = -1;
   }

   int incrementUsageCount(int delta) {
     return useCount+=delta;
   }

   int getPointersUnder() {
     return pointersUnder;
   }
 }
	/*
	* Copyright 2000-2014 JetBrains s.r.o.
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/
	package com.intellij.openapi.vfs.impl;

	import com.intellij.openapi.application.ApplicationManager;
	import com.intellij.openapi.application.impl.ApplicationInfoImpl;
	import com.intellij.openapi.util.Pair;
	import com.intellij.openapi.util.SystemInfo;
	import com.intellij.openapi.util.text.StringUtil;
	import com.intellij.openapi.vfs.VirtualFile;
	import com.intellij.openapi.vfs.VirtualFileManager;
	import com.intellij.util.ArrayUtil;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;

	import java.util.List;

	// all file pointers we store in the tree with nodes corresponding to the file structure on disk
	class FilePointerPartNode {
	private static final FilePointerPartNode[] EMPTY_ARRAY = new FilePointerPartNode[0];
	@NotNull private String part; // common prefix of all file pointers beneath
	@NotNull private FilePointerPartNode[] children;
	private FilePointerPartNode parent;
	VirtualFilePointerImpl leaf; // file pointer for this exact path (e.g. concatenation of all "part" fields down from the root)
	// in case there is file pointer exists for this part, its info is saved here
	volatile Pair<VirtualFile, String> myFileAndUrl; // must not be both null
	private volatile long myLastUpdated = -1;
	volatile int useCount;

	private int pointersUnder = 1; // number of alive pointers in this node plus all nodes beneath
	private static final VirtualFileManager ourFileManager = VirtualFileManager.getInstance();

	FilePointerPartNode(@NotNull String part, FilePointerPartNode parent, Pair<VirtualFile,String> fileAndUrl) {
	this.part = part;
	this.parent = parent;
	children = EMPTY_ARRAY;
	myFileAndUrl = fileAndUrl;
	}

	@Override
	public String toString() {
	return part + (children.length == 0 ? "" : " -> "+children.length);
	}

	// returns the node and length of matched characters in that node, or null if there is no match
	int position(@Nullable VirtualFile parent, boolean separator, @NotNull CharSequence childName, @NotNull FilePointerPartNode[] outNode) {
	checkConsistency();

	int partStart;
	if (parent == null) {
	partStart = 0;
	outNode[0] = this;
	}
	else {
	VirtualFile gparent = parent.getParent();
	partStart = position(gparent, gparent != null && !StringUtil.equals(gparent.getNameSequence(), "/"), parent.getNameSequence(), outNode);
	if (partStart == -1) return -1;
	}

	boolean childSeparator = false;
	if (separator) {
	if (partStart == outNode[0].part.length()) {
	childSeparator = true;
	}
	else {
	int sepIndex = indexOfFirstDifferentChar("/", 0, outNode[0].part, partStart);
	if (sepIndex != 1) return -1;
	partStart++;
	}
	}
	int index = indexOfFirstDifferentChar(childName, 0, outNode[0].part, partStart);

	if (index == childName.length()) {
	return partStart+index;
	}

	if (partStart + index == outNode[0].part.length()) {
	// go to children
	for (FilePointerPartNode child : outNode[0].children) {
	int childPos = child.position(null, childSeparator, childName.subSequence(index, childName.length()), outNode);
	if (childPos != -1) return childPos;
	}
	}
	// else there is no match
	return -1;
	}

	// appends to "out" all nodes under this node whose path (beginning from this node) starts in prefix.subSequence(start), then parent.getPath(), then childName
	void getPointersUnder(@Nullable VirtualFile parent,
	boolean separator,
	@NotNull CharSequence childName,
	@NotNull List<FilePointerPartNode> out) {
	FilePointerPartNode[] outNode = new FilePointerPartNode[1];
	int position = position(parent, separator, childName, outNode);
	if (position != -1) {
	FilePointerPartNode node = outNode[0];
	addAllPointersUnder(node, out);
	}
	}

	private static void addAllPointersUnder(@NotNull FilePointerPartNode node, @NotNull List<FilePointerPartNode> out) {
	if (node.leaf != null) out.add(node);
	for (FilePointerPartNode child : node.children) {
	addAllPointersUnder(child, out);
	}
	}

	boolean getPointersUnder(@NotNull String path, int start, @NotNull List<FilePointerPartNode> out) {
	checkConsistency();
	if (pointersUnder == 0) return false;
	// invariant: upper nodes are matched
	int index = indexOfFirstDifferentChar(path, start);
	if (index - start == part.length() // part matched entirely, check children
	\|\| index == path.length() // query matched entirely, add all children to matches
	) {
	if (index == path.length() && leaf != null) {
	out.add(this);
	}

	for (FilePointerPartNode child : children) {
	child.getPointersUnder(path, index, out);
	}
	}
	// else there is no match
	return false;
	}

	private static final boolean UNIT_TEST = ApplicationManager.getApplication().isUnitTestMode();
	void checkConsistency() {
	if (UNIT_TEST && !ApplicationInfoImpl.isInPerformanceTest()) {
	doCheckConsistency();
	}
	}

	private void doCheckConsistency() {
	int childSum = 0;
	for (FilePointerPartNode child : children) {
	childSum += child.pointersUnder;
	child.doCheckConsistency();
	assert child.parent == this;
	}
	if (leaf != null) childSum++;
	assert (useCount == 0) == (leaf == null) : useCount + " - " +leaf;
	assert pointersUnder == childSum : "expected: "+pointersUnder+"; actual: "+childSum;
	}

	@NotNull
	FilePointerPartNode findPointerOrCreate(@NotNull String path, int start, @NotNull Pair<VirtualFile, String> fileAndUrl) {
	// invariant: upper nodes are matched
	int index = indexOfFirstDifferentChar(path, start);
	if (index == path.length() // query matched entirely
	&& index - start == part.length()
	) {
	if (leaf == null) pointersUnder++;
	return this;
	}
	if (index - start == part.length() // part matched entirely, check children
	) {
	for (FilePointerPartNode child : children) {
	// find the right child (its part should start with ours)
	int i = child.indexOfFirstDifferentChar(path, index);
	if (i != index && (i > index+1 \|\| path.charAt(index) != '/')) {
	FilePointerPartNode node = child.findPointerOrCreate(path, index, fileAndUrl);
	if (node.leaf == null) pointersUnder++; // the new node's been created
	return node;
	}
	}
	// cannot insert to children, create child node manually
	String pathRest = path.substring(index);
	FilePointerPartNode newNode = new FilePointerPartNode(pathRest, this, fileAndUrl);
	children = ArrayUtil.append(children, newNode);
	pointersUnder++;
	return newNode;
	}
	// else there is no match
	// split
	// try to make "/" start the splitted part
	if (index > start && index != path.length() && path.charAt(index-1)== '/') index--;
	String pathRest = path.substring(index);
	FilePointerPartNode newNode = pathRest.isEmpty() ? this : new FilePointerPartNode(pathRest, this, fileAndUrl);
	String commonPredecessor = StringUtil.first(part, index - start, false);
	FilePointerPartNode splittedAway = new FilePointerPartNode(part.substring(index - start), this, myFileAndUrl);
	splittedAway.children = children;
	for (FilePointerPartNode child : children) {
	child.parent = splittedAway;
	}
	splittedAway.pointersUnder = pointersUnder;
	splittedAway.useCount = useCount;
	splittedAway.associate(leaf, myFileAndUrl);
	associate(null, null);
	useCount = 0;
	part = commonPredecessor;
	children = newNode == this ? new FilePointerPartNode[]{splittedAway} : new FilePointerPartNode[]{splittedAway, newNode};
	pointersUnder++;
	return newNode;
	}

	// return true if the root node must be deleted also
	boolean remove() {
	assert leaf != null : toString();
	associate(null, null);
	useCount = 0;
	myLastUpdated = -1;
	FilePointerPartNode node;
	for (node = this; node.parent != null; node = node.parent) {
	node.pointersUnder--;
	}
	if (--node.pointersUnder == 0) {
	node.children = EMPTY_ARRAY; // clear root node, especially in tests
	return true;
	}
	return false;
	}

	private int indexOfFirstDifferentChar(@NotNull CharSequence path, int start) {
	return indexOfFirstDifferentChar(path, start, part, 0);
	}

	@NotNull
	// returns pair.second != null always
	Pair<VirtualFile, String> update() {
	long lastUpdated = myLastUpdated;
	Pair<VirtualFile, String> fileAndUrl = myFileAndUrl;
	long fsModCount = ourFileManager.getModificationCount();
	if (lastUpdated == fsModCount) return fileAndUrl;
	VirtualFile file = fileAndUrl.first;
	String url = fileAndUrl.second;
	boolean changed = false;

	if (url == null) {
	url = file.getUrl();
	if (!file.isValid()) file = null;
	changed = true;
	}
	boolean fileIsValid = file != null && file.isValid();
	if (file != null && !fileIsValid) {
	file = null;
	changed = true;
	}
	if (file == null) {
	file = ourFileManager.findFileByUrl(url);
	fileIsValid = file != null && file.isValid();
	if (file != null) {
	changed = true;
	}
	}
	if (file != null) {
	if (fileIsValid) {
	url = file.getUrl(); // refresh url, it can differ
	changed \|= !url.equals(fileAndUrl.second);
	}
	else {
	file = null; // can't find, try next time
	changed = true;
	}
	}
	Pair<VirtualFile, String> result;
	if (changed) {
	result = Pair.create(file, url);
	myFileAndUrl = result;
	}
	else {
	result = fileAndUrl;
	}
	myLastUpdated = fsModCount;
	return result;
	}

	private static int indexOfFirstDifferentChar(@NotNull CharSequence s1, int start1, @NotNull String s2, int start2) {
	boolean ignoreCase = !SystemInfo.isFileSystemCaseSensitive;
	int len1 = s1.length();
	int len2 = s2.length();
	while (start1 < len1 && start2 < len2) {
	char c1 = s1.charAt(start1);
	char c2 = s2.charAt(start2);
	if (!StringUtil.charsEqual(c1, c2, ignoreCase)) {
	return start1;
	}
	start1++;
	start2++;
	}
	return start1;
	}

	void associate(VirtualFilePointerImpl pointer, Pair<VirtualFile, String> fileAndUrl) {
	if (pointer != null) {
	pointer.myNode = this;
	}
	leaf = pointer;
	myFileAndUrl = fileAndUrl;
	myLastUpdated = -1;
	}

	int incrementUsageCount(int delta) {
	return useCount+=delta;
	}

	int getPointersUnder() {
	return pointersUnder;
	}
	}