platform/platform-impl/src/com/intellij/openapi/vfs/newvfs/impl/VfsData.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.newvfs.impl;

 import com.intellij.openapi.application.ApplicationAdapter;
 import com.intellij.openapi.application.ApplicationManager;
 import com.intellij.openapi.vfs.InvalidVirtualFileAccessException;
 import com.intellij.util.ArrayUtil;
 import com.intellij.util.SmartFMap;
 import com.intellij.util.concurrency.AtomicFieldUpdater;
 import com.intellij.util.containers.ConcurrentBitSet;
 import com.intellij.util.containers.ConcurrentIntObjectMap;
 import com.intellij.util.containers.ContainerUtil;
 import com.intellij.util.containers.StripedLockIntObjectConcurrentHashMap;
 import com.intellij.util.keyFMap.KeyFMap;
 import com.intellij.util.text.CaseInsensitiveStringHashingStrategy;
 import gnu.trove.THashSet;
 import gnu.trove.TIntHashSet;
 import gnu.trove.TObjectHashingStrategy;
 import org.jetbrains.annotations.Contract;
 import org.jetbrains.annotations.NotNull;
 import org.jetbrains.annotations.Nullable;

 import java.util.Collections;
 import java.util.List;
 import java.util.concurrent.atomic.AtomicIntegerArray;
 import java.util.concurrent.atomic.AtomicReferenceArray;

 import static com.intellij.openapi.vfs.newvfs.impl.VirtualFileSystemEntry.ALL_FLAGS_MASK;
 import static com.intellij.util.ObjectUtils.assertNotNull;

 /**
  * The place where all the data is stored for VFS parts loaded into a memory: name-ids, flags, user data, children.
  *
  * The purpose is to avoid holding this data in separate immortal file/directory objects because that involves space overhead, significant
  * when there are hundreds of thousands of files.
  *
  * The data is stored per-id in blocks of {@link #SEGMENT_SIZE}. File ids in one project tend to cluster together,
  * so the overhead for non-loaded id should not be large in most cases.
  *
  * File objects are still created if needed. There might be several objects for the same file, so equals() should be used instead of ==.
  *
  * The lifecycle of a file object is as follows:
  *
  * 1. The file has not been instantiated yet, so {@link #getFileById} returns null.
  *
  * 2. A file is explicitly requested by calling getChildren or findChild on its parent. The parent initializes all the necessary data (in a thread-safe context)
  * and creates the file instance. See {@link #initFile}
  *
  * 3. After that the file is live, an object representing it can be retrieved any time from its parent. File system roots are
  * kept on hard references in {@link com.intellij.openapi.vfs.newvfs.persistent.PersistentFS}
  *
  * 4. If a file is deleted (invalidated), then its data is not needed anymore, and should be removed. But this can only happen after
  * all the listener have been notified about the file deletion and have had their chance to look at the data the last time. See {@link #killInvalidatedFiles()}
  *
  * 5. The file with removed data is marked as "dead" (see {@link #ourDeadMarker}, any access to it will throw {@link com.intellij.openapi.vfs.InvalidVirtualFileAccessException}
  * Dead ids won't be reused in the same session of the IDE.
  *
  * @author peter
  */
 public class VfsData {
   private static final int SEGMENT_BITS = 9;
   private static final int SEGMENT_SIZE = 1 << SEGMENT_BITS;
   private static final int OFFSET_MASK = SEGMENT_SIZE - 1;
   private static final Object ourDeadMarker = new String("dead file");

   private static final ConcurrentIntObjectMap<Segment> ourSegments = new StripedLockIntObjectConcurrentHashMap<Segment>();
   private static final ConcurrentBitSet ourInvalidatedIds = new ConcurrentBitSet();
   private static TIntHashSet ourDyingIds = new TIntHashSet();
   private static volatile SmartFMap<VirtualFileSystemEntry, VirtualDirectoryImpl> ourChangedParents = SmartFMap.emptyMap();

   static {
     ApplicationManager.getApplication().addApplicationListener(new ApplicationAdapter() {
       @Override
       public void writeActionFinished(Object action) {
         // after top-level write action is finished, all the deletion listeners should have processed the deleted files
         // and their data is considered safe to remove. From this point on accessing a removed file will result in an exception.
         if (!ApplicationManager.getApplication().isWriteAccessAllowed()) {
           killInvalidatedFiles();
         }
       }
     });
   }

   private static void killInvalidatedFiles() {
     synchronized (ourDeadMarker) {
       if (!ourDyingIds.isEmpty()) {
         for (int id : ourDyingIds.toArray()) {
           assertNotNull(getSegment(id, false)).myObjectArray.set(getOffset(id), ourDeadMarker);
           ourChangedParents = ourChangedParents.minus(new VirtualFileImpl(id, null, null));
         }
         ourDyingIds = new TIntHashSet();
       }
     }
   }

   @Nullable
   public static VirtualFileSystemEntry getFileById(int id, VirtualDirectoryImpl parent) {
     Segment segment = getSegment(id, false);
     if (segment == null) return null;

     int offset = getOffset(id);
     Object o = segment.myObjectArray.get(offset);
     if (o == null) return null;

     if (o == ourDeadMarker) {
       throw reportDeadFileAccess(new VirtualFileImpl(id, segment, parent));
     }
     assert segment.getNameId(id) > 0;

     return o instanceof DirectoryData ? new VirtualDirectoryImpl(id, segment, (DirectoryData)o, parent, parent.getFileSystem())
                                       : new VirtualFileImpl(id, segment, parent);
   }

   private static InvalidVirtualFileAccessException reportDeadFileAccess(VirtualFileSystemEntry file) {
     return new InvalidVirtualFileAccessException("Accessing dead virtual file: " + file.getUrl());
   }

   private static int getOffset(int id) {
     return id & OFFSET_MASK;
   }

   @Nullable @Contract("_,true->!null")
   public static Segment getSegment(int id, boolean create) {
     int key = id >>> SEGMENT_BITS;
     Segment segment = ourSegments.get(key);
     if (segment != null || !create) return segment;
     return ourSegments.cacheOrGet(key, new Segment());
   }

   public static void initFile(int id, Segment segment, int nameId, @NotNull Object data) {
     assert id > 0;
     int offset = getOffset(id);

     segment.setNameId(id, nameId);

     if (segment.myObjectArray.get(offset) != null) {
       throw new AssertionError("File already created");
     }
     segment.myObjectArray.set(offset, data);
   }

   static CharSequence getNameByFileId(int id) {
     return FileNameCache.getVFileName(assertNotNull(getSegment(id, false)).getNameId(id));
   }

   static boolean isFileValid(int id) {
     return !ourInvalidatedIds.get(id);
   }

   @Nullable
   static VirtualDirectoryImpl getChangedParent(VirtualFileSystemEntry child) {
     SmartFMap<VirtualFileSystemEntry, VirtualDirectoryImpl> map = ourChangedParents;
     return map == (SmartFMap)SmartFMap.emptyMap() ? null : map.get(child);
   }

   static void changeParent(VirtualFileSystemEntry child, VirtualDirectoryImpl parent) {
     synchronized (ourDeadMarker) {
       ourChangedParents = ourChangedParents.plus(child, parent);
     }
   }

   static void invalidateFile(int id) {
     ourInvalidatedIds.set(id);
     synchronized (ourDeadMarker) {
       ourDyingIds.add(id);
     }
   }

   public static class Segment {
     // user data for files, DirectoryData for folders
     final AtomicReferenceArray<Object> myObjectArray = new AtomicReferenceArray<Object>(SEGMENT_SIZE);

     // <nameId, flags> pairs, "flags" part containing flags per se and modification stamp
     private final AtomicIntegerArray myIntArray = new AtomicIntegerArray(SEGMENT_SIZE * 2);

     int getNameId(int fileId) {
       return myIntArray.get(getOffset(fileId) * 2);
     }

     void setNameId(int fileId, int nameId) {
       myIntArray.set(getOffset(fileId) * 2, nameId);
     }

     void setUserMap(int fileId, KeyFMap map) {
       myObjectArray.set(getOffset(fileId), map);
     }

     KeyFMap getUserMap(VirtualFileSystemEntry file) {
       Object o = myObjectArray.get(getOffset(Math.abs(file.getId())));
       if (!(o instanceof KeyFMap)) {
         throw reportDeadFileAccess(file);
       }
       return (KeyFMap)o;
     }

     boolean changeUserMap(int fileId, KeyFMap oldMap, KeyFMap newMap) {
       return myObjectArray.compareAndSet(getOffset(fileId), oldMap, newMap);
     }

     boolean getFlag(int id, int mask) {
       assert (mask & ~ALL_FLAGS_MASK) == 0 : "Unexpected flag";
       return (myIntArray.get(getOffset(id) * 2 + 1) & mask) != 0;
     }

     void setFlag(int id, int mask, boolean value) {
       assert (mask & ~ALL_FLAGS_MASK) == 0 : "Unexpected flag";
       int offset = getOffset(id) * 2 + 1;
       while (true) {
         int oldInt = myIntArray.get(offset);
         int updated = value ? (oldInt | mask) : (oldInt & ~mask);
         if (myIntArray.compareAndSet(offset, oldInt, updated)) {
           return;
         }
       }
     }

     long getModificationStamp(int id) {
       return myIntArray.get(getOffset(id) * 2 + 1) & ~ALL_FLAGS_MASK;
     }

     void setModificationStamp(int id, long stamp) {
       int offset = getOffset(id) * 2 + 1;
       while (true) {
         int oldInt = myIntArray.get(offset);
         int updated = (oldInt & ALL_FLAGS_MASK) | ((int)stamp & ~ALL_FLAGS_MASK);
         if (myIntArray.compareAndSet(offset, oldInt, updated)) {
           return;
         }
       }
     }

   }

   // non-final field accesses are synchronized on this instance, but this happens in VirtualDirectoryImpl
   public static class DirectoryData {
     private static final AtomicFieldUpdater<DirectoryData, KeyFMap> updater = AtomicFieldUpdater.forFieldOfType(DirectoryData.class, KeyFMap.class);
     volatile KeyFMap myUserMap = KeyFMap.EMPTY_MAP;
     int[] myChildrenIds = ArrayUtil.EMPTY_INT_ARRAY;
     private THashSet<String> myAdoptedNames;

     VirtualFileSystemEntry[] getFileChildren(int fileId, VirtualDirectoryImpl parent) {
       assert fileId > 0;
       VirtualFileSystemEntry[] children = new VirtualFileSystemEntry[myChildrenIds.length];
       for (int i = 0; i < myChildrenIds.length; i++) {
         children[i] = assertNotNull(getFileById(myChildrenIds[i], parent));
       }
       return children;
     }

     boolean changeUserMap(KeyFMap oldMap, KeyFMap newMap) {
       return updater.compareAndSet(this, oldMap, newMap);
     }

     boolean isAdoptedName(String name) {
       return myAdoptedNames != null && myAdoptedNames.contains(name);
     }

     void removeAdoptedName(String name) {
       if (myAdoptedNames != null) {
         myAdoptedNames.remove(name);
         if (myAdoptedNames.isEmpty()) {
           myAdoptedNames = null;
         }
       }
     }
     void addAdoptedName(String name, boolean caseSensitive) {
       if (myAdoptedNames == null) {
         //noinspection unchecked
         myAdoptedNames = new THashSet<String>(0, caseSensitive ? TObjectHashingStrategy.CANONICAL : CaseInsensitiveStringHashingStrategy.INSTANCE);
       }
       myAdoptedNames.add(name);
     }

     List<String> getAdoptedNames() {
       return myAdoptedNames == null ? Collections.<String>emptyList() : ContainerUtil.newArrayList(myAdoptedNames);
     }
   }

 }
	/*
	* 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.newvfs.impl;

	import com.intellij.openapi.application.ApplicationAdapter;
	import com.intellij.openapi.application.ApplicationManager;
	import com.intellij.openapi.vfs.InvalidVirtualFileAccessException;
	import com.intellij.util.ArrayUtil;
	import com.intellij.util.SmartFMap;
	import com.intellij.util.concurrency.AtomicFieldUpdater;
	import com.intellij.util.containers.ConcurrentBitSet;
	import com.intellij.util.containers.ConcurrentIntObjectMap;
	import com.intellij.util.containers.ContainerUtil;
	import com.intellij.util.containers.StripedLockIntObjectConcurrentHashMap;
	import com.intellij.util.keyFMap.KeyFMap;
	import com.intellij.util.text.CaseInsensitiveStringHashingStrategy;
	import gnu.trove.THashSet;
	import gnu.trove.TIntHashSet;
	import gnu.trove.TObjectHashingStrategy;
	import org.jetbrains.annotations.Contract;
	import org.jetbrains.annotations.NotNull;
	import org.jetbrains.annotations.Nullable;

	import java.util.Collections;
	import java.util.List;
	import java.util.concurrent.atomic.AtomicIntegerArray;
	import java.util.concurrent.atomic.AtomicReferenceArray;

	import static com.intellij.openapi.vfs.newvfs.impl.VirtualFileSystemEntry.ALL_FLAGS_MASK;
	import static com.intellij.util.ObjectUtils.assertNotNull;

	/**
	* The place where all the data is stored for VFS parts loaded into a memory: name-ids, flags, user data, children.
	*
	* The purpose is to avoid holding this data in separate immortal file/directory objects because that involves space overhead, significant
	* when there are hundreds of thousands of files.
	*
	* The data is stored per-id in blocks of {@link #SEGMENT_SIZE}. File ids in one project tend to cluster together,
	* so the overhead for non-loaded id should not be large in most cases.
	*
	* File objects are still created if needed. There might be several objects for the same file, so equals() should be used instead of ==.
	*
	* The lifecycle of a file object is as follows:
	*
	* 1. The file has not been instantiated yet, so {@link #getFileById} returns null.
	*
	* 2. A file is explicitly requested by calling getChildren or findChild on its parent. The parent initializes all the necessary data (in a thread-safe context)
	* and creates the file instance. See {@link #initFile}
	*
	* 3. After that the file is live, an object representing it can be retrieved any time from its parent. File system roots are
	* kept on hard references in {@link com.intellij.openapi.vfs.newvfs.persistent.PersistentFS}
	*
	* 4. If a file is deleted (invalidated), then its data is not needed anymore, and should be removed. But this can only happen after
	* all the listener have been notified about the file deletion and have had their chance to look at the data the last time. See {@link #killInvalidatedFiles()}
	*
	* 5. The file with removed data is marked as "dead" (see {@link #ourDeadMarker}, any access to it will throw {@link com.intellij.openapi.vfs.InvalidVirtualFileAccessException}
	* Dead ids won't be reused in the same session of the IDE.
	*
	* @author peter
	*/
	public class VfsData {
	private static final int SEGMENT_BITS = 9;
	private static final int SEGMENT_SIZE = 1 << SEGMENT_BITS;
	private static final int OFFSET_MASK = SEGMENT_SIZE - 1;
	private static final Object ourDeadMarker = new String("dead file");

	private static final ConcurrentIntObjectMap<Segment> ourSegments = new StripedLockIntObjectConcurrentHashMap<Segment>();
	private static final ConcurrentBitSet ourInvalidatedIds = new ConcurrentBitSet();
	private static TIntHashSet ourDyingIds = new TIntHashSet();
	private static volatile SmartFMap<VirtualFileSystemEntry, VirtualDirectoryImpl> ourChangedParents = SmartFMap.emptyMap();

	static {
	ApplicationManager.getApplication().addApplicationListener(new ApplicationAdapter() {
	@Override
	public void writeActionFinished(Object action) {
	// after top-level write action is finished, all the deletion listeners should have processed the deleted files
	// and their data is considered safe to remove. From this point on accessing a removed file will result in an exception.
	if (!ApplicationManager.getApplication().isWriteAccessAllowed()) {
	killInvalidatedFiles();
	}
	}
	});
	}

	private static void killInvalidatedFiles() {
	synchronized (ourDeadMarker) {
	if (!ourDyingIds.isEmpty()) {
	for (int id : ourDyingIds.toArray()) {
	assertNotNull(getSegment(id, false)).myObjectArray.set(getOffset(id), ourDeadMarker);
	ourChangedParents = ourChangedParents.minus(new VirtualFileImpl(id, null, null));
	}
	ourDyingIds = new TIntHashSet();
	}
	}
	}

	@Nullable
	public static VirtualFileSystemEntry getFileById(int id, VirtualDirectoryImpl parent) {
	Segment segment = getSegment(id, false);
	if (segment == null) return null;

	int offset = getOffset(id);
	Object o = segment.myObjectArray.get(offset);
	if (o == null) return null;

	if (o == ourDeadMarker) {
	throw reportDeadFileAccess(new VirtualFileImpl(id, segment, parent));
	}
	assert segment.getNameId(id) > 0;

	return o instanceof DirectoryData ? new VirtualDirectoryImpl(id, segment, (DirectoryData)o, parent, parent.getFileSystem())
	: new VirtualFileImpl(id, segment, parent);
	}

	private static InvalidVirtualFileAccessException reportDeadFileAccess(VirtualFileSystemEntry file) {
	return new InvalidVirtualFileAccessException("Accessing dead virtual file: " + file.getUrl());
	}

	private static int getOffset(int id) {
	return id & OFFSET_MASK;
	}

	@Nullable @Contract("_,true->!null")
	public static Segment getSegment(int id, boolean create) {
	int key = id >>> SEGMENT_BITS;
	Segment segment = ourSegments.get(key);
	if (segment != null \|\| !create) return segment;
	return ourSegments.cacheOrGet(key, new Segment());
	}

	public static void initFile(int id, Segment segment, int nameId, @NotNull Object data) {
	assert id > 0;
	int offset = getOffset(id);

	segment.setNameId(id, nameId);

	if (segment.myObjectArray.get(offset) != null) {
	throw new AssertionError("File already created");
	}
	segment.myObjectArray.set(offset, data);
	}

	static CharSequence getNameByFileId(int id) {
	return FileNameCache.getVFileName(assertNotNull(getSegment(id, false)).getNameId(id));
	}

	static boolean isFileValid(int id) {
	return !ourInvalidatedIds.get(id);
	}

	@Nullable
	static VirtualDirectoryImpl getChangedParent(VirtualFileSystemEntry child) {
	SmartFMap<VirtualFileSystemEntry, VirtualDirectoryImpl> map = ourChangedParents;
	return map == (SmartFMap)SmartFMap.emptyMap() ? null : map.get(child);
	}

	static void changeParent(VirtualFileSystemEntry child, VirtualDirectoryImpl parent) {
	synchronized (ourDeadMarker) {
	ourChangedParents = ourChangedParents.plus(child, parent);
	}
	}

	static void invalidateFile(int id) {
	ourInvalidatedIds.set(id);
	synchronized (ourDeadMarker) {
	ourDyingIds.add(id);
	}
	}

	public static class Segment {
	// user data for files, DirectoryData for folders
	final AtomicReferenceArray<Object> myObjectArray = new AtomicReferenceArray<Object>(SEGMENT_SIZE);

	// <nameId, flags> pairs, "flags" part containing flags per se and modification stamp
	private final AtomicIntegerArray myIntArray = new AtomicIntegerArray(SEGMENT_SIZE * 2);

	int getNameId(int fileId) {
	return myIntArray.get(getOffset(fileId) * 2);
	}

	void setNameId(int fileId, int nameId) {
	myIntArray.set(getOffset(fileId) * 2, nameId);
	}

	void setUserMap(int fileId, KeyFMap map) {
	myObjectArray.set(getOffset(fileId), map);
	}

	KeyFMap getUserMap(VirtualFileSystemEntry file) {
	Object o = myObjectArray.get(getOffset(Math.abs(file.getId())));
	if (!(o instanceof KeyFMap)) {
	throw reportDeadFileAccess(file);
	}
	return (KeyFMap)o;
	}

	boolean changeUserMap(int fileId, KeyFMap oldMap, KeyFMap newMap) {
	return myObjectArray.compareAndSet(getOffset(fileId), oldMap, newMap);
	}

	boolean getFlag(int id, int mask) {
	assert (mask & ~ALL_FLAGS_MASK) == 0 : "Unexpected flag";
	return (myIntArray.get(getOffset(id) * 2 + 1) & mask) != 0;
	}

	void setFlag(int id, int mask, boolean value) {
	assert (mask & ~ALL_FLAGS_MASK) == 0 : "Unexpected flag";
	int offset = getOffset(id) * 2 + 1;
	while (true) {
	int oldInt = myIntArray.get(offset);
	int updated = value ? (oldInt \| mask) : (oldInt & ~mask);
	if (myIntArray.compareAndSet(offset, oldInt, updated)) {
	return;
	}
	}
	}

	long getModificationStamp(int id) {
	return myIntArray.get(getOffset(id) * 2 + 1) & ~ALL_FLAGS_MASK;
	}

	void setModificationStamp(int id, long stamp) {
	int offset = getOffset(id) * 2 + 1;
	while (true) {
	int oldInt = myIntArray.get(offset);
	int updated = (oldInt & ALL_FLAGS_MASK) \| ((int)stamp & ~ALL_FLAGS_MASK);
	if (myIntArray.compareAndSet(offset, oldInt, updated)) {
	return;
	}
	}
	}

	}

	// non-final field accesses are synchronized on this instance, but this happens in VirtualDirectoryImpl
	public static class DirectoryData {
	private static final AtomicFieldUpdater<DirectoryData, KeyFMap> updater = AtomicFieldUpdater.forFieldOfType(DirectoryData.class, KeyFMap.class);
	volatile KeyFMap myUserMap = KeyFMap.EMPTY_MAP;
	int[] myChildrenIds = ArrayUtil.EMPTY_INT_ARRAY;
	private THashSet<String> myAdoptedNames;

	VirtualFileSystemEntry[] getFileChildren(int fileId, VirtualDirectoryImpl parent) {
	assert fileId > 0;
	VirtualFileSystemEntry[] children = new VirtualFileSystemEntry[myChildrenIds.length];
	for (int i = 0; i < myChildrenIds.length; i++) {
	children[i] = assertNotNull(getFileById(myChildrenIds[i], parent));
	}
	return children;
	}

	boolean changeUserMap(KeyFMap oldMap, KeyFMap newMap) {
	return updater.compareAndSet(this, oldMap, newMap);
	}

	boolean isAdoptedName(String name) {
	return myAdoptedNames != null && myAdoptedNames.contains(name);
	}

	void removeAdoptedName(String name) {
	if (myAdoptedNames != null) {
	myAdoptedNames.remove(name);
	if (myAdoptedNames.isEmpty()) {
	myAdoptedNames = null;
	}
	}
	}
	void addAdoptedName(String name, boolean caseSensitive) {
	if (myAdoptedNames == null) {
	//noinspection unchecked
	myAdoptedNames = new THashSet<String>(0, caseSensitive ? TObjectHashingStrategy.CANONICAL : CaseInsensitiveStringHashingStrategy.INSTANCE);
	}
	myAdoptedNames.add(name);
	}

	List<String> getAdoptedNames() {
	return myAdoptedNames == null ? Collections.<String>emptyList() : ContainerUtil.newArrayList(myAdoptedNames);
	}
	}

	}