Adding APIs to enable reporting virtual view hierarchies to accessibility serivces.

Added an interface that is the contract for a client to expose a virtual
view hierarchy to accessibility services. Clients impement this interface
and set it in the View that is the root of the virtual sub-tree. Adding
this finctionality via compostion as opposed to inheritance enables apps
to maintain backwards compatibility by setting the accessibility virtual
hierarchy provider on the View only if the API version is high enough.

bug:5382859

Change-Id: I7e3927b71a5517943c6cb071be2e87fba23132bf

6 files changed, 408 insertions, 93 deletions

diff --git a/core/java/android/view/accessibility/AccessibilityEvent.java b/core/java/android/view/accessibility/AccessibilityEvent.java
index 86dd9df..c6f778f 100644
--- a/core/java/android/view/accessibility/AccessibilityEvent.java
+++ b/core/java/android/view/accessibility/AccessibilityEvent.java
@@ -876,7 +876,7 @@ public final class AccessibilityEvent extends AccessibilityRecord implements Par
         record.mParcelableData = parcel.readParcelable(null);
         parcel.readList(record.mText, null);
         record.mSourceWindowId = parcel.readInt();
-        record.mSourceViewId = parcel.readInt();
+        record.mSourceNodeId = parcel.readLong();
         record.mSealed = (parcel.readInt() == 1);
     }
 
@@ -930,7 +930,7 @@ public final class AccessibilityEvent extends AccessibilityRecord implements Par
         parcel.writeParcelable(record.mParcelableData, flags);
         parcel.writeList(record.mText);
         parcel.writeInt(record.mSourceWindowId);
-        parcel.writeInt(record.mSourceViewId);
+        parcel.writeLong(record.mSourceNodeId);
         parcel.writeInt(record.mSealed ? 1 : 0);
     }
 
@@ -951,7 +951,7 @@ public final class AccessibilityEvent extends AccessibilityRecord implements Par
         if (DEBUG) {
             builder.append("\n");
             builder.append("; sourceWindowId: ").append(mSourceWindowId);
-            builder.append("; sourceViewId: ").append(mSourceViewId);
+            builder.append("; mSourceNodeId: ").append(mSourceNodeId);
             for (int i = 0; i < mRecords.size(); i++) {
                 AccessibilityRecord record = mRecords.get(i);
                 builder.append("  Record ");
diff --git a/core/java/android/view/accessibility/AccessibilityInteractionClient.java b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
index 25b980b..5f2990a 100644
--- a/core/java/android/view/accessibility/AccessibilityInteractionClient.java
+++ b/core/java/android/view/accessibility/AccessibilityInteractionClient.java
@@ -21,6 +21,7 @@ import android.graphics.Rect;
 import android.os.Message;
 import android.os.RemoteException;
 import android.os.SystemClock;
+import android.util.LongSparseArray;
 
 import java.util.Collections;
 import java.util.List;
@@ -65,7 +66,8 @@ public final class AccessibilityInteractionClient
 
     private static final Object sStaticLock = new Object();
 
-    private static AccessibilityInteractionClient sInstance;
+    private static final LongSparseArray<AccessibilityInteractionClient> sClients =
+        new LongSparseArray<AccessibilityInteractionClient>();
 
     private final AtomicInteger mInteractionIdCounter = new AtomicInteger();
 
@@ -84,17 +86,36 @@ public final class AccessibilityInteractionClient
     private final Rect mTempBounds = new Rect();
 
     /**
-     * @return The singleton of this class.
+     * @return The client for the current thread.
      */
     public static AccessibilityInteractionClient getInstance() {
+        final long threadId = Thread.currentThread().getId();
+        return getInstanceForThread(threadId);
+    }
+
+    /**
+     * <strong>Note:</strong> We keep one instance per interrogating thread since
+     * the instance contains state which can lead to undesired thread interleavings.
+     * We do not have a thread local variable since other threads should be able to
+     * look up the correct client knowing a thread id. See ViewRootImpl for details.
+     *
+     * @return The client for a given <code>threadId</code>.
+     */
+    public static AccessibilityInteractionClient getInstanceForThread(long threadId) {
         synchronized (sStaticLock) {
-            if (sInstance == null) {
-                sInstance = new AccessibilityInteractionClient();
+            AccessibilityInteractionClient client = sClients.get(threadId);
+            if (client == null) {
+                client = new AccessibilityInteractionClient();
+                sClients.put(threadId, client);
             }
-            return sInstance;
+            return client;
         }
     }
 
+    private AccessibilityInteractionClient() {
+        /* reducing constructor visibility */
+    }
+
     /**
      * Sets the message to be processed if the interacted view hierarchy
      * and the interacting client are running in the same thread.
@@ -113,16 +134,17 @@ public final class AccessibilityInteractionClient
      *
      * @param connection A connection for interacting with the system.
      * @param accessibilityWindowId A unique window id.
-     * @param accessibilityViewId A unique View accessibility id.
+     * @param accessibilityNodeId A unique node accessibility id
+     *     (accessibility view and virtual descendant id).
      * @return An {@link AccessibilityNodeInfo} if found, null otherwise.
      */
     public AccessibilityNodeInfo findAccessibilityNodeInfoByAccessibilityId(
             IAccessibilityServiceConnection connection, int accessibilityWindowId,
-            int accessibilityViewId) {
+            long accessibilityNodeId) {
         try {
             final int interactionId = mInteractionIdCounter.getAndIncrement();
             final float windowScale = connection.findAccessibilityNodeInfoByAccessibilityId(
-                    accessibilityWindowId, accessibilityViewId, interactionId, this,
+                    accessibilityWindowId, accessibilityNodeId, interactionId, this,
                     Thread.currentThread().getId());
             // If the scale is zero the call has failed.
             if (windowScale > 0) {
@@ -173,16 +195,19 @@ public final class AccessibilityInteractionClient
      * @param text The searched text.
      * @return A list of found {@link AccessibilityNodeInfo}s.
      */
-    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByViewTextInActiveWindow(
+    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByTextInActiveWindow(
             IAccessibilityServiceConnection connection, String text) {
         try {
             final int interactionId = mInteractionIdCounter.getAndIncrement();
-            final float windowScale = connection.findAccessibilityNodeInfosByViewTextInActiveWindow(
+            final float windowScale = connection.findAccessibilityNodeInfosByTextInActiveWindow(
                     text, interactionId, this, Thread.currentThread().getId());
             // If the scale is zero the call has failed.
             if (windowScale > 0) {
                 List<AccessibilityNodeInfo> infos = getFindAccessibilityNodeInfosResultAndClear(
                         interactionId);
+                if (infos == null) {
+                    return Collections.emptyList();
+                }
                 finalizeAccessibilityNodeInfos(infos, connection, windowScale);
                 return infos;
             }
@@ -201,17 +226,17 @@ public final class AccessibilityInteractionClient
      * @param connection A connection for interacting with the system.
      * @param text The searched text.
      * @param accessibilityWindowId A unique window id.
-     * @param accessibilityViewId A unique View accessibility id from where to start the search.
-     *        Use {@link android.view.View#NO_ID} to start from the root.
+     * @param accessibilityNodeId A unique node id (accessibility and virtual descendant id) from
+     *        where to start the search. Use {@link android.view.View#NO_ID} to start from the root.
      * @return A list of found {@link AccessibilityNodeInfo}s.
      */
-    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByViewText(
+    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByText(
             IAccessibilityServiceConnection connection, String text, int accessibilityWindowId,
-            int accessibilityViewId) {
+            long accessibilityNodeId) {
         try {
             final int interactionId = mInteractionIdCounter.getAndIncrement();
-            final float windowScale = connection.findAccessibilityNodeInfosByViewText(text,
-                    accessibilityWindowId, accessibilityViewId, interactionId, this,
+            final float windowScale = connection.findAccessibilityNodeInfosByText(text,
+                    accessibilityWindowId, accessibilityNodeId, interactionId, this,
                     Thread.currentThread().getId());
             // If the scale is zero the call has failed.
             if (windowScale > 0) {
@@ -231,16 +256,16 @@ public final class AccessibilityInteractionClient
      *
      * @param connection A connection for interacting with the system.
      * @param accessibilityWindowId The id of the window.
-     * @param accessibilityViewId A unique View accessibility id.
+     * @param accessibilityNodeId A unique node id (accessibility and virtual descendant id).
      * @param action The action to perform.
      * @return Whether the action was performed.
      */
     public boolean performAccessibilityAction(IAccessibilityServiceConnection connection,
-            int accessibilityWindowId, int accessibilityViewId, int action) {
+            int accessibilityWindowId, long accessibilityNodeId, int action) {
         try {
             final int interactionId = mInteractionIdCounter.getAndIncrement();
             final boolean success = connection.performAccessibilityAction(
-                    accessibilityWindowId, accessibilityViewId, action, interactionId, this,
+                    accessibilityWindowId, accessibilityNodeId, action, interactionId, this,
                     Thread.currentThread().getId());
             if (success) {
                 return getPerformAccessibilityActionResult(interactionId);
diff --git a/core/java/android/view/accessibility/AccessibilityNodeInfo.java b/core/java/android/view/accessibility/AccessibilityNodeInfo.java
index 7671312..e792666 100644
--- a/core/java/android/view/accessibility/AccessibilityNodeInfo.java
+++ b/core/java/android/view/accessibility/AccessibilityNodeInfo.java
@@ -21,7 +21,7 @@ import android.graphics.Rect;
 import android.os.Parcel;
 import android.os.Parcelable;
 import android.text.TextUtils;
-import android.util.SparseIntArray;
+import android.util.SparseLongArray;
 import android.view.View;
 
 import java.util.Collections;
@@ -97,6 +97,59 @@ public class AccessibilityNodeInfo implements Parcelable {
 
     private static final int PROPERTY_SCROLLABLE = 0x00000200;
 
+    /**
+     * Bits that provide the id of a virtual descendant of a view.
+     */
+    private static final long VIRTUAL_DESCENDANT_ID_MASK = 0xffffffff00000000L;
+
+    /**
+     * Bit shift of {@link #VIRTUAL_DESCENDANT_ID_MASK} to get to the id for a
+     * virtual descendant of a view. Such a descendant does not exist in the view
+     * hierarchy and is only reported via the accessibility APIs.
+     */
+    private static final int VIRTUAL_DESCENDANT_ID_SHIFT = 32;
+
+    /**
+     * Gets the accessibility view id which identifies a View in the view three.
+     *
+     * @param accessibilityNodeId The id of an {@link AccessibilityNodeInfo}.
+     * @return The accessibility view id part of the node id.
+     *
+     * @hide
+     */
+    public static int getAccessibilityViewId(long accessibilityNodeId) {
+        return (int) accessibilityNodeId;
+    }
+
+    /**
+     * Gets the virtual descendant id which identifies an imaginary view in a
+     * containing View.
+     *
+     * @param accessibilityNodeId The id of an {@link AccessibilityNodeInfo}.
+     * @return The virtual view id part of the node id.
+     *
+     * @hide
+     */
+    public static int getVirtualDescendantId(long accessibilityNodeId) {
+        return (int) ((accessibilityNodeId & VIRTUAL_DESCENDANT_ID_MASK)
+                >> VIRTUAL_DESCENDANT_ID_SHIFT);
+    }
+
+    /**
+     * Makes a node id by shifting the <code>virtualDescendantId</code>
+     * by {@link #VIRTUAL_DESCENDANT_ID_SHIFT} and taking
+     * the bitwise or with the <code>accessibilityViewId</code>.
+     *
+     * @param accessibilityViewId A View accessibility id.
+     * @param virtualDescendantId A virtual descendant id.
+     * @return The node id.
+     *
+     * @hide
+     */
+    public static long makeNodeId(int accessibilityViewId, int virtualDescendantId) {
+        return (((long) virtualDescendantId) << VIRTUAL_DESCENDANT_ID_SHIFT) | accessibilityViewId;
+    }
+
     // Housekeeping.
     private static final int MAX_POOL_SIZE = 50;
     private static final Object sPoolLock = new Object();
@@ -107,9 +160,9 @@ public class AccessibilityNodeInfo implements Parcelable {
     private boolean mSealed;
 
     // Data.
-    private int mAccessibilityViewId = View.NO_ID;
-    private int mAccessibilityWindowId = View.NO_ID;
-    private int mParentAccessibilityViewId = View.NO_ID;
+    private long mSourceNodeId = makeNodeId(View.NO_ID, View.NO_ID);
+    private int mWindowId = View.NO_ID;
+    private long mParentNodeId = makeNodeId(View.NO_ID, View.NO_ID);
     private int mBooleanProperties;
     private final Rect mBoundsInParent = new Rect();
     private final Rect mBoundsInScreen = new Rect();
@@ -119,7 +172,7 @@ public class AccessibilityNodeInfo implements Parcelable {
     private CharSequence mText;
     private CharSequence mContentDescription;
 
-    private SparseIntArray mChildAccessibilityIds = new SparseIntArray();
+    private SparseLongArray mChildIds = new SparseLongArray();
     private int mActions;
 
     private IAccessibilityServiceConnection mConnection;
@@ -133,13 +186,43 @@ public class AccessibilityNodeInfo implements Parcelable {
 
     /**
      * Sets the source.
+     * <p>
+     *   <strong>Note:</strong> Cannot be called from an
+     *   {@link android.accessibilityservice.AccessibilityService}.
+     *   This class is made immutable before being delivered to an AccessibilityService.
+     * </p>
      *
      * @param source The info source.
      */
     public void setSource(View source) {
+        setSource(source, View.NO_ID);
+    }
+
+    /**
+     * Sets the source to be a virtual descendant of the given <code>root</code>.
+     * If <code>virtualDescendantId</code> equals to {@link View#NO_ID} the root
+     * is set as the source.
+     * <p>
+     * A virtual descendant is an imaginary View that is reported as a part of the view
+     * hierarchy for accessibility purposes. This enables custom views that draw complex
+     * content to report them selves as a tree of virtual views, thus conveying their
+     * logical structure.
+     * </p>
+     * <p>
+     *   <strong>Note:</strong> Cannot be called from an
+     *   {@link android.accessibilityservice.AccessibilityService}.
+     *   This class is made immutable before being delivered to an AccessibilityService.
+     * </p>
+     *
+     * @param root The root of the virtual subtree.
+     * @param virtualDescendantId The id of the virtual descendant.
+     */
+    public void setSource(View root, int virtualDescendantId) {
         enforceNotSealed();
-        mAccessibilityViewId = source.getAccessibilityViewId();
-        mAccessibilityWindowId = source.getAccessibilityWindowId();
+        mWindowId = (root != null) ? root.getAccessibilityWindowId() : View.NO_ID;
+        final int rootAccessibilityViewId =
+            (root != null) ? root.getAccessibilityViewId() : View.NO_ID;
+        mSourceNodeId = makeNodeId(rootAccessibilityViewId, virtualDescendantId);
     }
 
     /**
@@ -148,7 +231,7 @@ public class AccessibilityNodeInfo implements Parcelable {
      * @return The window id.
      */
     public int getWindowId() {
-        return mAccessibilityWindowId;
+        return mWindowId;
     }
 
     /**
@@ -157,7 +240,7 @@ public class AccessibilityNodeInfo implements Parcelable {
      * @return The child count.
      */
     public int getChildCount() {
-        return mChildAccessibilityIds.size();
+        return mChildIds.size();
     }
 
     /**
@@ -176,21 +259,20 @@ public class AccessibilityNodeInfo implements Parcelable {
      */
     public AccessibilityNodeInfo getChild(int index) {
         enforceSealed();
-        final int childAccessibilityViewId = mChildAccessibilityIds.get(index);
-        if (!canPerformRequestOverConnection(childAccessibilityViewId)) {
+        if (!canPerformRequestOverConnection(mSourceNodeId)) {
             return null;
         }
+        final long childId = mChildIds.get(index);
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
-        return client.findAccessibilityNodeInfoByAccessibilityId(mConnection,
-                mAccessibilityWindowId, childAccessibilityViewId);
+        return client.findAccessibilityNodeInfoByAccessibilityId(mConnection, mWindowId, childId);
     }
 
     /**
      * Adds a child.
      * <p>
-     *   <strong>Note:</strong> Cannot be called from an
-     *   {@link android.accessibilityservice.AccessibilityService}.
-     *   This class is made immutable before being delivered to an AccessibilityService.
+     * <strong>Note:</strong> Cannot be called from an
+     * {@link android.accessibilityservice.AccessibilityService}.
+     * This class is made immutable before being delivered to an AccessibilityService.
      * </p>
      *
      * @param child The child.
@@ -198,10 +280,30 @@ public class AccessibilityNodeInfo implements Parcelable {
      * @throws IllegalStateException If called from an AccessibilityService.
      */
     public void addChild(View child) {
+        addChild(child, View.NO_ID);
+    }
+
+    /**
+     * Adds a virtual child which is a descendant of the given <code>root</code>.
+     * If <code>virtualDescendantId</code> equals to {@link View#NO_ID} the root
+     * is added as a child.
+     * <p>
+     * A virtual descendant is an imaginary View that is reported as a part of the view
+     * hierarchy for accessibility purposes. This enables custom views that draw complex
+     * content to report them selves as a tree of virtual views, thus conveying their
+     * logical structure.
+     * </p>
+     *
+     * @param root The root of the virtual subtree.
+     * @param virtualDescendantId The id of the virtual child.
+     */
+    public void addChild(View root, int virtualDescendantId) {
         enforceNotSealed();
-        final int childAccessibilityViewId = child.getAccessibilityViewId();
-        final int index = mChildAccessibilityIds.size();
-        mChildAccessibilityIds.put(index, childAccessibilityViewId);
+        final int index = mChildIds.size();
+        final int rootAccessibilityViewId =
+            (root != null) ? root.getAccessibilityViewId() : View.NO_ID;
+        final long childNodeId = makeNodeId(rootAccessibilityViewId, virtualDescendantId);
+        mChildIds.put(index, childNodeId);
     }
 
     /**
@@ -249,12 +351,11 @@ public class AccessibilityNodeInfo implements Parcelable {
      */
     public boolean performAction(int action) {
         enforceSealed();
-        if (!canPerformRequestOverConnection(mAccessibilityViewId)) {
+        if (!canPerformRequestOverConnection(mSourceNodeId)) {
             return false;
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
-        return client.performAccessibilityAction(mConnection, mAccessibilityWindowId,
-                mAccessibilityViewId, action);
+        return client.performAccessibilityAction(mConnection, mWindowId, mSourceNodeId, action);
     }
 
     /**
@@ -273,12 +374,11 @@ public class AccessibilityNodeInfo implements Parcelable {
      */
     public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByText(String text) {
         enforceSealed();
-        if (!canPerformRequestOverConnection(mAccessibilityViewId)) {
+        if (!canPerformRequestOverConnection(mSourceNodeId)) {
             return Collections.emptyList();
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
-        return client.findAccessibilityNodeInfosByViewText(mConnection, text,
-                mAccessibilityWindowId, mAccessibilityViewId);
+        return client.findAccessibilityNodeInfosByText(mConnection, text, mWindowId, mSourceNodeId);
     }
 
     /**
@@ -293,12 +393,12 @@ public class AccessibilityNodeInfo implements Parcelable {
      */
     public AccessibilityNodeInfo getParent() {
         enforceSealed();
-        if (!canPerformRequestOverConnection(mAccessibilityViewId)) {
+        if (!canPerformRequestOverConnection(mSourceNodeId)) {
             return null;
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
         return client.findAccessibilityNodeInfoByAccessibilityId(mConnection,
-                mAccessibilityWindowId, mParentAccessibilityViewId);
+                mWindowId, mParentNodeId);
     }
 
     /**
@@ -314,8 +414,33 @@ public class AccessibilityNodeInfo implements Parcelable {
      * @throws IllegalStateException If called from an AccessibilityService.
      */
     public void setParent(View parent) {
+        setParent(parent, View.NO_ID);
+    }
+
+    /**
+     * Sets the parent to be a virtual descendant of the given <code>root</code>.
+     * If <code>virtualDescendantId</code> equals to {@link View#NO_ID} the root
+     * is set as the parent.
+     * <p>
+     * A virtual descendant is an imaginary View that is reported as a part of the view
+     * hierarchy for accessibility purposes. This enables custom views that draw complex
+     * content to report them selves as a tree of virtual views, thus conveying their
+     * logical structure.
+     * </p>
+     * <p>
+     *   <strong>Note:</strong> Cannot be called from an
+     *   {@link android.accessibilityservice.AccessibilityService}.
+     *   This class is made immutable before being delivered to an AccessibilityService.
+     * </p>
+     *
+     * @param root The root of the virtual subtree.
+     * @param virtualDescendantId The id of the virtual descendant.
+     */
+    public void setParent(View root, int virtualDescendantId) {
         enforceNotSealed();
-        mParentAccessibilityViewId = parent.getAccessibilityViewId();
+        final int rootAccessibilityViewId =
+            (root != null) ? root.getAccessibilityViewId() : View.NO_ID;
+        mParentNodeId = makeNodeId(rootAccessibilityViewId, virtualDescendantId);
     }
 
     /**
@@ -827,6 +952,7 @@ public class AccessibilityNodeInfo implements Parcelable {
      * Returns a cached instance if such is available otherwise a new one
      * and sets the source.
      *
+     * @param source The source view.
      * @return An instance.
      *
      * @see #setSource(View)
@@ -838,6 +964,22 @@ public class AccessibilityNodeInfo implements Parcelable {
     }
 
     /**
+     * Returns a cached instance if such is available otherwise a new one
+     * and sets the source.
+     *
+     * @param root The root of the virtual subtree.
+     * @param virtualDescendantId The id of the virtual descendant.
+     * @return An instance.
+     *
+     * @see #setSource(View, int)
+     */
+    public static AccessibilityNodeInfo obtain(View root, int virtualDescendantId) {
+        AccessibilityNodeInfo info = AccessibilityNodeInfo.obtain();
+        info.setSource(root, virtualDescendantId);
+        return info;
+    }
+
+    /**
      * Returns a cached instance if such is available otherwise a new one.
      *
      * @return An instance.
@@ -907,15 +1049,15 @@ public class AccessibilityNodeInfo implements Parcelable {
             parcel.writeStrongBinder(mConnection.asBinder());
         }
         parcel.writeInt(isSealed() ? 1 : 0);
-        parcel.writeInt(mAccessibilityViewId);
-        parcel.writeInt(mAccessibilityWindowId);
-        parcel.writeInt(mParentAccessibilityViewId);
+        parcel.writeLong(mSourceNodeId);
+        parcel.writeInt(mWindowId);
+        parcel.writeLong(mParentNodeId);
 
-        SparseIntArray childIds = mChildAccessibilityIds;
+        SparseLongArray childIds = mChildIds;
         final int childIdsSize = childIds.size();
         parcel.writeInt(childIdsSize);
         for (int i = 0; i < childIdsSize; i++) {
-            parcel.writeInt(childIds.valueAt(i));
+            parcel.writeLong(childIds.valueAt(i));
         }
 
         parcel.writeInt(mBoundsInParent.top);
@@ -950,9 +1092,9 @@ public class AccessibilityNodeInfo implements Parcelable {
     private void init(AccessibilityNodeInfo other) {
         mSealed = other.mSealed;
         mConnection = other.mConnection;
-        mAccessibilityViewId = other.mAccessibilityViewId;
-        mParentAccessibilityViewId = other.mParentAccessibilityViewId;
-        mAccessibilityWindowId = other.mAccessibilityWindowId;
+        mSourceNodeId = other.mSourceNodeId;
+        mParentNodeId = other.mParentNodeId;
+        mWindowId = other.mWindowId;
         mBoundsInParent.set(other.mBoundsInParent);
         mBoundsInScreen.set(other.mBoundsInScreen);
         mPackageName = other.mPackageName;
@@ -961,7 +1103,7 @@ public class AccessibilityNodeInfo implements Parcelable {
         mContentDescription = other.mContentDescription;
         mActions= other.mActions;
         mBooleanProperties = other.mBooleanProperties;
-        mChildAccessibilityIds = other.mChildAccessibilityIds.clone();
+        mChildIds = other.mChildIds.clone();
     }
 
     /**
@@ -975,14 +1117,14 @@ public class AccessibilityNodeInfo implements Parcelable {
                     parcel.readStrongBinder());
         }
         mSealed = (parcel.readInt()  == 1);
-        mAccessibilityViewId = parcel.readInt();
-        mAccessibilityWindowId = parcel.readInt();
-        mParentAccessibilityViewId = parcel.readInt();
+        mSourceNodeId = parcel.readLong();
+        mWindowId = parcel.readInt();
+        mParentNodeId = parcel.readLong();
 
-        SparseIntArray childIds = mChildAccessibilityIds;
+        SparseLongArray childIds = mChildIds;
         final int childrenSize = parcel.readInt();
         for (int i = 0; i < childrenSize; i++) {
-            final int childId = parcel.readInt();
+            final long childId = parcel.readLong();
             childIds.put(i, childId);
         }
 
@@ -1012,10 +1154,10 @@ public class AccessibilityNodeInfo implements Parcelable {
     private void clear() {
         mSealed = false;
         mConnection = null;
-        mAccessibilityViewId = View.NO_ID;
-        mParentAccessibilityViewId = View.NO_ID;
-        mAccessibilityWindowId = View.NO_ID;
-        mChildAccessibilityIds.clear();
+        mSourceNodeId = makeNodeId(View.NO_ID, View.NO_ID);
+        mParentNodeId = makeNodeId(View.NO_ID, View.NO_ID);
+        mWindowId = View.NO_ID;
+        mChildIds.clear();
         mBoundsInParent.set(0, 0, 0, 0);
         mBoundsInScreen.set(0, 0, 0, 0);
         mBooleanProperties = 0;
@@ -1047,9 +1189,9 @@ public class AccessibilityNodeInfo implements Parcelable {
         }
     }
 
-    private boolean canPerformRequestOverConnection(int accessibilityViewId) {
-        return (mAccessibilityWindowId != View.NO_ID
-                && accessibilityViewId != View.NO_ID
+    private boolean canPerformRequestOverConnection(long accessibilityNodeId) {
+        return (mWindowId != View.NO_ID
+                && getAccessibilityViewId(accessibilityNodeId) != View.NO_ID
                 && mConnection != null);
     }
 
@@ -1065,10 +1207,10 @@ public class AccessibilityNodeInfo implements Parcelable {
             return false;
         }
         AccessibilityNodeInfo other = (AccessibilityNodeInfo) object;
-        if (mAccessibilityViewId != other.mAccessibilityViewId) {
+        if (mSourceNodeId != other.mSourceNodeId) {
             return false;
         }
-        if (mAccessibilityWindowId != other.mAccessibilityWindowId) {
+        if (mWindowId != other.mWindowId) {
             return false;
         }
         return true;
@@ -1078,8 +1220,9 @@ public class AccessibilityNodeInfo implements Parcelable {
     public int hashCode() {
         final int prime = 31;
         int result = 1;
-        result = prime * result + mAccessibilityViewId;
-        result = prime * result + mAccessibilityWindowId;
+        result = prime * result + getAccessibilityViewId(mSourceNodeId);
+        result = prime * result + getVirtualDescendantId(mSourceNodeId);
+        result = prime * result + mWindowId;
         return result;
     }
 
@@ -1089,9 +1232,10 @@ public class AccessibilityNodeInfo implements Parcelable {
         builder.append(super.toString());
 
         if (DEBUG) {
-            builder.append("; accessibilityId: " + mAccessibilityViewId);
-            builder.append("; parentAccessibilityId: " + mParentAccessibilityViewId);
-            SparseIntArray childIds = mChildAccessibilityIds;
+            builder.append("; accessibilityViewId: " + getAccessibilityViewId(mSourceNodeId));
+            builder.append("; virtualDescendantId: " + getVirtualDescendantId(mSourceNodeId));
+            builder.append("; mParentNodeId: " + mParentNodeId);
+            SparseLongArray childIds = mChildIds;
             builder.append("; childAccessibilityIds: [");
             for (int i = 0, count = childIds.size(); i < count; i++) {
                 builder.append(childIds.valueAt(i));
diff --git a/core/java/android/view/accessibility/AccessibilityNodeProvider.java b/core/java/android/view/accessibility/AccessibilityNodeProvider.java
new file mode 100644
index 0000000..5890417
--- /dev/null
+++ b/core/java/android/view/accessibility/AccessibilityNodeProvider.java
@@ -0,0 +1,130 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * 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 android.view.accessibility;
+
+import android.accessibilityservice.AccessibilityService;
+import android.view.View;
+
+import java.util.List;
+
+/**
+ * This class is the contract a client should implement to enable support of a
+ * virtual view hierarchy rooted at a given view for accessibility purposes. A virtual
+ * view hierarchy is a tree of imaginary Views that is reported as a part of the view
+ * hierarchy when an {@link AccessibilityService} explores the window content.
+ * Since the virtual View tree does not exist this class is responsible for
+ * managing the {@link AccessibilityNodeInfo}s describing that tree to accessibility
+ * services.
+ * </p>
+ * <p>
+ * The main use case of these APIs is to enable a custom view that draws complex content,
+ * for example a monthly calendar grid, to be presented as a tree of logical nodes,
+ * for example month days each containing events, thus conveying its logical structure.
+ * <p>
+ * <p>
+ * A typical use case is to override {@link View#getAccessibilityNodeProvider()} of the
+ * View that is a root of a virtual View hierarchy to return an instance of this class.
+ * In such a case this instance is responsible for managing {@link AccessibilityNodeInfo}s
+ * describing the virtual sub-tree rooted at the View including the one representing the
+ * View itself. Similarly the returned instance is responsible for performing accessibility
+ * actions on any virtual view or the root view itself. For example:
+ * </p>
+ * <pre>
+ *     getAccessibilityNodeProvider(
+ *         if (mAccessibilityNodeProvider == null) {
+ *             mAccessibilityNodeProvider = new AccessibilityNodeProvider() {
+ *                 public boolean performAccessibilityAction(int action, int virtualDescendantId) {
+ *                     // Implementation.
+ *                     return false;
+ *                 }
+ *
+ *                 public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByText(String text, int virtualDescendantId) {
+ *                     // Implementation.
+ *                     return null;
+ *                 }
+ *
+ *                 public AccessibilityNodeInfo createAccessibilityNodeInfo(int virtualDescendantId) {
+ *                     // Implementation.
+ *                     return null;
+ *                 }
+ *             });
+ *     return mAccessibilityNodeProvider;
+ * </pre>
+ */
+public abstract class AccessibilityNodeProvider {
+
+    /**
+     * Returns an {@link AccessibilityNodeInfo} representing a virtual view,
+     * i.e. a descendant of the host View, with the given <code>virtualViewId</code>
+     * or the host View itself if <code>virtualViewId</code> equals to {@link View#NO_ID}.
+     * <p>
+     * A virtual descendant is an imaginary View that is reported as a part of the view
+     * hierarchy for accessibility purposes. This enables custom views that draw complex
+     * content to report them selves as a tree of virtual views, thus conveying their
+     * logical structure.
+     * </p>
+     * <p>
+     * The implementer is responsible for obtaining an accessibility node info from the
+     * pool of reusable instances and setting the desired properties of the node info
+     * before returning it.
+     * </p>
+     *
+     * @param virtualViewId A client defined virtual view id.
+     * @return A populated {@link AccessibilityNodeInfo} for a virtual descendant or the
+     *     host View.
+     *
+     * @see AccessibilityNodeInfo
+     */
+    public AccessibilityNodeInfo createAccessibilityNodeInfo(int virtualViewId) {
+        return null;
+    }
+
+    /**
+     * Performs an accessibility action on a virtual view, i.e. a descendant of the
+     * host View, with the given <code>virtualViewId</code> or the host View itself
+     * if <code>virtualViewId</code> equals to {@link View#NO_ID}.
+     *
+     * @param action The action to perform.
+     * @param virtualViewId A client defined virtual view id.
+     * @return True if the action was performed.
+     *
+     * @see #createAccessibilityNodeInfo(int)
+     * @see AccessibilityNodeInfo
+     */
+    public boolean performAccessibilityAction(int action, int virtualViewId) {
+        return false;
+    }
+
+    /**
+     * Finds {@link AccessibilityNodeInfo}s by text. The match is case insensitive
+     * containment. The search is relative to the virtual view, i.e. a descendant of the
+     * host View, with the given <code>virtualViewId</code> or the host View itself 
+     * <code>virtualViewId</code> equals to {@link View#NO_ID}.
+     *
+     * @param virtualViewId A client defined virtual view id which defined
+     *     the root of the tree in which to perform the search.
+     * @param text The searched text.
+     * @return A list of node info.
+     *
+     * @see #createAccessibilityNodeInfo(int)
+     * @see AccessibilityNodeInfo
+     */
+    public List<AccessibilityNodeInfo> findAccessibilityNodeInfosByText(String text,
+            int virtualViewId) {
+        return null;
+    }
+}
diff --git a/core/java/android/view/accessibility/AccessibilityRecord.java b/core/java/android/view/accessibility/AccessibilityRecord.java
index a4e0688..f3ca0d5 100644
--- a/core/java/android/view/accessibility/AccessibilityRecord.java
+++ b/core/java/android/view/accessibility/AccessibilityRecord.java
@@ -78,7 +78,7 @@ public class AccessibilityRecord {
 
     int mAddedCount= UNDEFINED;
     int mRemovedCount = UNDEFINED;
-    int mSourceViewId = View.NO_ID;
+    long mSourceNodeId = AccessibilityNodeInfo.makeNodeId(View.NO_ID, View.NO_ID);
     int mSourceWindowId = View.NO_ID;
 
     CharSequence mClassName;
@@ -103,14 +103,28 @@ public class AccessibilityRecord {
      * @throws IllegalStateException If called from an AccessibilityService.
      */
     public void setSource(View source) {
+        setSource(source, View.NO_ID);
+    }
+
+    /**
+     * Sets the source to be a virtual descendant of the given <code>root</code>.
+     * If <code>virtualDescendantId</code> equals to {@link View#NO_ID} the root
+     * is set as the source.
+     * <p>
+     * A virtual descendant is an imaginary View that is reported as a part of the view
+     * hierarchy for accessibility purposes. This enables custom views that draw complex
+     * content to report them selves as a tree of virtual views, thus conveying their
+     * logical structure.
+     * </p>
+     *
+     * @param root The root of the virtual subtree.
+     * @param virtualDescendantId The id of the virtual descendant.
+     */
+    public void setSource(View root, int virtualDescendantId) {
         enforceNotSealed();
-        if (source != null) {
-            mSourceWindowId = source.getAccessibilityWindowId();
-            mSourceViewId = source.getAccessibilityViewId();
-        } else {
-            mSourceWindowId = View.NO_ID;
-            mSourceViewId = View.NO_ID;
-        }
+        mSourceWindowId = (root != null) ? root.getAccessibilityWindowId() : View.NO_ID;
+        final int rootViewId = (root != null) ? root.getAccessibilityViewId() : View.NO_ID;
+        mSourceNodeId = AccessibilityNodeInfo.makeNodeId(rootViewId, virtualDescendantId);
     }
 
     /**
@@ -125,12 +139,13 @@ public class AccessibilityRecord {
      */
     public AccessibilityNodeInfo getSource() {
         enforceSealed();
-        if (mSourceWindowId == View.NO_ID || mSourceViewId == View.NO_ID || mConnection == null) {
+        if (mConnection == null || mSourceWindowId == View.NO_ID
+                || AccessibilityNodeInfo.getAccessibilityViewId(mSourceNodeId) == View.NO_ID) {
             return null;
         }
         AccessibilityInteractionClient client = AccessibilityInteractionClient.getInstance();
         return client.findAccessibilityNodeInfoByAccessibilityId(mConnection, mSourceWindowId,
-                mSourceViewId);
+                mSourceNodeId);
     }
 
     /**
@@ -395,6 +410,7 @@ public class AccessibilityRecord {
     public int getMaxScrollX() {
         return mMaxScrollX;
     }
+
     /**
      * Sets the max scroll offset of the source left edge in pixels.
      *
@@ -707,7 +723,7 @@ public class AccessibilityRecord {
         mParcelableData = record.mParcelableData;
         mText.addAll(record.mText);
         mSourceWindowId = record.mSourceWindowId;
-        mSourceViewId = record.mSourceViewId;
+        mSourceNodeId = record.mSourceNodeId;
         mConnection = record.mConnection;
     }
 
@@ -732,7 +748,7 @@ public class AccessibilityRecord {
         mBeforeText = null;
         mParcelableData = null;
         mText.clear();
-        mSourceViewId = View.NO_ID;
+        mSourceNodeId = AccessibilityNodeInfo.makeNodeId(View.NO_ID, View.NO_ID);
         mSourceWindowId = View.NO_ID;
     }
 
diff --git a/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl b/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
index 535d594..a90c427 100644
--- a/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
+++ b/core/java/android/view/accessibility/IAccessibilityInteractionConnection.aidl
@@ -27,7 +27,7 @@ import android.view.accessibility.IAccessibilityInteractionConnectionCallback;
  */
 oneway interface IAccessibilityInteractionConnection {
 
-    void findAccessibilityNodeInfoByAccessibilityId(int accessibilityViewId, int interactionId,
+    void findAccessibilityNodeInfoByAccessibilityId(long accessibilityNodeId, int interactionId,
         IAccessibilityInteractionConnectionCallback callback,
         int interrogatingPid, long interrogatingTid);
 
@@ -35,11 +35,11 @@ oneway interface IAccessibilityInteractionConnection {
         IAccessibilityInteractionConnectionCallback callback,
         int interrogatingPid, long interrogatingTid);
 
-    void findAccessibilityNodeInfosByViewText(String text, int accessibilityViewId,
+    void findAccessibilityNodeInfosByText(String text, long accessibilityNodeId,
         int interactionId, IAccessibilityInteractionConnectionCallback callback,
         int interrogatingPid, long interrogatingTid);
 
-    void performAccessibilityAction(int accessibilityId, int action, int interactionId,
+    void performAccessibilityAction(long accessibilityNodeId, int action, int interactionId,
         IAccessibilityInteractionConnectionCallback callback, int interrogatingPid,
         long interrogatingTid);
 }