[go: nahoru, domu]

1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License
15 */
16
17package com.android.server.am;
18
19import static android.content.Intent.FLAG_ACTIVITY_MULTIPLE_TASK;
20import static android.content.Intent.FLAG_ACTIVITY_NEW_DOCUMENT;
21import static android.content.Intent.FLAG_ACTIVITY_NEW_TASK;
22import static com.android.server.am.ActivityManagerDebugConfig.DEBUG_RECENTS;
23import static com.android.server.am.ActivityManagerDebugConfig.DEBUG_TASKS;
24import static com.android.server.am.ActivityManagerDebugConfig.POSTFIX_RECENTS;
25import static com.android.server.am.ActivityManagerDebugConfig.POSTFIX_TASKS;
26import static com.android.server.am.ActivityManagerDebugConfig.TAG_AM;
27import static com.android.server.am.ActivityManagerDebugConfig.TAG_WITH_CLASS_NAME;
28import static com.android.server.am.TaskRecord.INVALID_TASK_ID;
29
30import com.google.android.collect.Sets;
31
32import android.app.ActivityManager;
33import android.app.AppGlobals;
34import android.content.ComponentName;
35import android.content.Intent;
36import android.content.pm.ActivityInfo;
37import android.content.pm.ApplicationInfo;
38import android.content.pm.IPackageManager;
39import android.content.pm.PackageManager;
40import android.graphics.Bitmap;
41import android.os.Environment;
42import android.os.RemoteException;
43import android.os.UserHandle;
44import android.util.Slog;
45import android.util.SparseArray;
46import android.util.SparseBooleanArray;
47
48import java.io.File;
49import java.util.ArrayList;
50import java.util.Arrays;
51import java.util.Collections;
52import java.util.Comparator;
53import java.util.HashMap;
54import java.util.Set;
55
56/**
57 * Class for managing the recent tasks list.
58 */
59class RecentTasks extends ArrayList<TaskRecord> {
60    private static final String TAG = TAG_WITH_CLASS_NAME ? "RecentTasks" : TAG_AM;
61    private static final String TAG_RECENTS = TAG + POSTFIX_RECENTS;
62    private static final String TAG_TASKS = TAG + POSTFIX_TASKS;
63
64    // Maximum number recent bitmaps to keep in memory.
65    private static final int MAX_RECENT_BITMAPS = 3;
66    private static final int DEFAULT_INITIAL_CAPACITY = 5;
67
68    // Whether or not to move all affiliated tasks to the front when one of the tasks is launched
69    private static final boolean MOVE_AFFILIATED_TASKS_TO_FRONT = false;
70
71    /**
72     * Save recent tasks information across reboots.
73     */
74    private final TaskPersister mTaskPersister;
75    private final ActivityManagerService mService;
76    private final SparseBooleanArray mUsersWithRecentsLoaded = new SparseBooleanArray(
77            DEFAULT_INITIAL_CAPACITY);
78
79    /**
80     * Stores for each user task ids that are taken by tasks residing in persistent storage. These
81     * tasks may or may not currently be in memory.
82     */
83    final SparseArray<SparseBooleanArray> mPersistedTaskIds = new SparseArray<>(
84            DEFAULT_INITIAL_CAPACITY);
85
86    // Mainly to avoid object recreation on multiple calls.
87    private final ArrayList<TaskRecord> mTmpRecents = new ArrayList<TaskRecord>();
88    private final HashMap<ComponentName, ActivityInfo> mTmpAvailActCache = new HashMap<>();
89    private final HashMap<String, ApplicationInfo> mTmpAvailAppCache = new HashMap<>();
90    private final ActivityInfo mTmpActivityInfo = new ActivityInfo();
91    private final ApplicationInfo mTmpAppInfo = new ApplicationInfo();
92
93    RecentTasks(ActivityManagerService service, ActivityStackSupervisor mStackSupervisor) {
94        File systemDir = Environment.getDataSystemDirectory();
95        mService = service;
96        mTaskPersister = new TaskPersister(systemDir, mStackSupervisor, service, this);
97        mStackSupervisor.setRecentTasks(this);
98    }
99
100    /**
101     * Loads the persistent recentTasks for {@code userId} into this list from persistent storage.
102     * Does nothing if they are already loaded.
103     *
104     * @param userId the user Id
105     */
106    void loadUserRecentsLocked(int userId) {
107        if (!mUsersWithRecentsLoaded.get(userId)) {
108            // Load the task ids if not loaded.
109            loadPersistedTaskIdsForUserLocked(userId);
110            Slog.i(TAG, "Loading recents for user " + userId + " into memory.");
111            addAll(mTaskPersister.restoreTasksForUserLocked(userId));
112            cleanupLocked(userId);
113            mUsersWithRecentsLoaded.put(userId, true);
114        }
115    }
116
117    private void loadPersistedTaskIdsForUserLocked(int userId) {
118        // An empty instead of a null set here means that no persistent taskIds were present
119        // on file when we loaded them.
120        if (mPersistedTaskIds.get(userId) == null) {
121            mPersistedTaskIds.put(userId, mTaskPersister.loadPersistedTaskIdsForUser(userId));
122            Slog.i(TAG, "Loaded persisted task ids for user " + userId);
123        }
124    }
125
126    boolean taskIdTakenForUserLocked(int taskId, int userId) {
127        loadPersistedTaskIdsForUserLocked(userId);
128        return mPersistedTaskIds.get(userId).get(taskId);
129    }
130
131    void notifyTaskPersisterLocked(TaskRecord task, boolean flush) {
132        if (task != null && task.stack != null && task.stack.isHomeStack()) {
133            // Never persist the home stack.
134            return;
135        }
136        syncPersistentTaskIdsLocked();
137        mTaskPersister.wakeup(task, flush);
138    }
139
140    private void syncPersistentTaskIdsLocked() {
141        for (int i = mPersistedTaskIds.size() - 1; i >= 0; i--) {
142            int userId = mPersistedTaskIds.keyAt(i);
143            if (mUsersWithRecentsLoaded.get(userId)) {
144                // Recents are loaded only after task ids are loaded. Therefore, the set of taskids
145                // referenced here should not be null.
146                mPersistedTaskIds.valueAt(i).clear();
147            }
148        }
149        for (int i = size() - 1; i >= 0; i--) {
150            TaskRecord task = get(i);
151            if (task.isPersistable && (task.stack == null || !task.stack.isHomeStack())) {
152                // Set of persisted taskIds for task.userId should not be null here
153                // TODO Investigate why it can happen. For now initialize with an empty set
154                if (mPersistedTaskIds.get(task.userId) == null) {
155                    Slog.wtf(TAG, "No task ids found for userId " + task.userId + ". task=" + task
156                            + " mPersistedTaskIds=" + mPersistedTaskIds);
157                    mPersistedTaskIds.put(task.userId, new SparseBooleanArray());
158                }
159                mPersistedTaskIds.get(task.userId).put(task.taskId, true);
160            }
161        }
162    }
163
164
165    void onSystemReadyLocked() {
166        clear();
167        mTaskPersister.startPersisting();
168    }
169
170    Bitmap getTaskDescriptionIcon(String path) {
171        return mTaskPersister.getTaskDescriptionIcon(path);
172    }
173
174    Bitmap getImageFromWriteQueue(String path) {
175        return mTaskPersister.getImageFromWriteQueue(path);
176    }
177
178    void saveImage(Bitmap image, String path) {
179        mTaskPersister.saveImage(image, path);
180    }
181
182    void flush() {
183        synchronized (mService) {
184            syncPersistentTaskIdsLocked();
185        }
186        mTaskPersister.flush();
187    }
188
189    /**
190     * Returns all userIds for which recents from persistent storage are loaded into this list.
191     *
192     * @return an array of userIds.
193     */
194    int[] usersWithRecentsLoadedLocked() {
195        int[] usersWithRecentsLoaded = new int[mUsersWithRecentsLoaded.size()];
196        int len = 0;
197        for (int i = 0; i < usersWithRecentsLoaded.length; i++) {
198            int userId = mUsersWithRecentsLoaded.keyAt(i);
199            if (mUsersWithRecentsLoaded.valueAt(i)) {
200                usersWithRecentsLoaded[len++] = userId;
201            }
202        }
203        if (len < usersWithRecentsLoaded.length) {
204            // should never happen.
205            return Arrays.copyOf(usersWithRecentsLoaded, len);
206        }
207        return usersWithRecentsLoaded;
208    }
209
210    private void unloadUserRecentsLocked(int userId) {
211        if (mUsersWithRecentsLoaded.get(userId)) {
212            Slog.i(TAG, "Unloading recents for user " + userId + " from memory.");
213            mUsersWithRecentsLoaded.delete(userId);
214            removeTasksForUserLocked(userId);
215        }
216    }
217
218    /**
219     * Removes recent tasks and any other state kept in memory for the passed in user. Does not
220     * touch the information present on persistent storage.
221     *
222     * @param userId the id of the user
223     */
224    void unloadUserDataFromMemoryLocked(int userId) {
225        unloadUserRecentsLocked(userId);
226        mPersistedTaskIds.delete(userId);
227        mTaskPersister.unloadUserDataFromMemory(userId);
228    }
229
230    TaskRecord taskForIdLocked(int id) {
231        final int recentsCount = size();
232        for (int i = 0; i < recentsCount; i++) {
233            TaskRecord tr = get(i);
234            if (tr.taskId == id) {
235                return tr;
236            }
237        }
238        return null;
239    }
240
241    /** Remove recent tasks for a user. */
242    void removeTasksForUserLocked(int userId) {
243        if(userId <= 0) {
244            Slog.i(TAG, "Can't remove recent task on user " + userId);
245            return;
246        }
247
248        for (int i = size() - 1; i >= 0; --i) {
249            TaskRecord tr = get(i);
250            if (tr.userId == userId) {
251                if(DEBUG_TASKS) Slog.i(TAG_TASKS,
252                        "remove RecentTask " + tr + " when finishing user" + userId);
253                remove(i);
254                tr.removedFromRecents();
255            }
256        }
257    }
258
259    void onPackagesSuspendedChanged(String[] packages, boolean suspended, int userId) {
260        final Set<String> packageNames = Sets.newHashSet(packages);
261        for (int i = size() - 1; i >= 0; --i) {
262            final TaskRecord tr = get(i);
263            if (tr.realActivity != null
264                    && packageNames.contains(tr.realActivity.getPackageName())
265                    && tr.userId == userId
266                    && tr.realActivitySuspended != suspended) {
267               tr.realActivitySuspended = suspended;
268               notifyTaskPersisterLocked(tr, false);
269            }
270        }
271
272    }
273
274    /**
275     * Update the recent tasks lists: make sure tasks should still be here (their
276     * applications / activities still exist), update their availability, fix-up ordering
277     * of affiliations.
278     */
279    void cleanupLocked(int userId) {
280        int recentsCount = size();
281        if (recentsCount == 0) {
282            // Happens when called from the packagemanager broadcast before boot,
283            // or just any empty list.
284            return;
285        }
286
287        final IPackageManager pm = AppGlobals.getPackageManager();
288        for (int i = recentsCount - 1; i >= 0; i--) {
289            final TaskRecord task = get(i);
290            if (userId != UserHandle.USER_ALL && task.userId != userId) {
291                // Only look at tasks for the user ID of interest.
292                continue;
293            }
294            if (task.autoRemoveRecents && task.getTopActivity() == null) {
295                // This situation is broken, and we should just get rid of it now.
296                remove(i);
297                task.removedFromRecents();
298                Slog.w(TAG, "Removing auto-remove without activity: " + task);
299                continue;
300            }
301            // Check whether this activity is currently available.
302            if (task.realActivity != null) {
303                ActivityInfo ai = mTmpAvailActCache.get(task.realActivity);
304                if (ai == null) {
305                    try {
306                        // At this first cut, we're only interested in
307                        // activities that are fully runnable based on
308                        // current system state.
309                        ai = pm.getActivityInfo(task.realActivity,
310                                PackageManager.MATCH_DEBUG_TRIAGED_MISSING, userId);
311                    } catch (RemoteException e) {
312                        // Will never happen.
313                        continue;
314                    }
315                    if (ai == null) {
316                        ai = mTmpActivityInfo;
317                    }
318                    mTmpAvailActCache.put(task.realActivity, ai);
319                }
320                if (ai == mTmpActivityInfo) {
321                    // This could be either because the activity no longer exists, or the
322                    // app is temporarily gone. For the former we want to remove the recents
323                    // entry; for the latter we want to mark it as unavailable.
324                    ApplicationInfo app = mTmpAvailAppCache
325                            .get(task.realActivity.getPackageName());
326                    if (app == null) {
327                        try {
328                            app = pm.getApplicationInfo(task.realActivity.getPackageName(),
329                                    PackageManager.MATCH_UNINSTALLED_PACKAGES, userId);
330                        } catch (RemoteException e) {
331                            // Will never happen.
332                            continue;
333                        }
334                        if (app == null) {
335                            app = mTmpAppInfo;
336                        }
337                        mTmpAvailAppCache.put(task.realActivity.getPackageName(), app);
338                    }
339                    if (app == mTmpAppInfo
340                            || (app.flags & ApplicationInfo.FLAG_INSTALLED) == 0) {
341                        // Doesn't exist any more! Good-bye.
342                        remove(i);
343                        task.removedFromRecents();
344                        Slog.w(TAG, "Removing no longer valid recent: " + task);
345                        continue;
346                    } else {
347                        // Otherwise just not available for now.
348                        if (DEBUG_RECENTS && task.isAvailable) Slog.d(TAG_RECENTS,
349                                "Making recent unavailable: " + task);
350                        task.isAvailable = false;
351                    }
352                } else {
353                    if (!ai.enabled || !ai.applicationInfo.enabled
354                            || (ai.applicationInfo.flags
355                                    & ApplicationInfo.FLAG_INSTALLED) == 0) {
356                        if (DEBUG_RECENTS && task.isAvailable) Slog.d(TAG_RECENTS,
357                                "Making recent unavailable: " + task
358                                        + " (enabled=" + ai.enabled + "/"
359                                        + ai.applicationInfo.enabled
360                                        + " flags="
361                                        + Integer.toHexString(ai.applicationInfo.flags)
362                                        + ")");
363                        task.isAvailable = false;
364                    } else {
365                        if (DEBUG_RECENTS && !task.isAvailable) Slog.d(TAG_RECENTS,
366                                "Making recent available: " + task);
367                        task.isAvailable = true;
368                    }
369                }
370            }
371        }
372
373        // Verify the affiliate chain for each task.
374        int i = 0;
375        recentsCount = size();
376        while (i < recentsCount) {
377            i = processNextAffiliateChainLocked(i);
378        }
379        // recent tasks are now in sorted, affiliated order.
380    }
381
382    private final boolean moveAffiliatedTasksToFront(TaskRecord task, int taskIndex) {
383        int recentsCount = size();
384        TaskRecord top = task;
385        int topIndex = taskIndex;
386        while (top.mNextAffiliate != null && topIndex > 0) {
387            top = top.mNextAffiliate;
388            topIndex--;
389        }
390        if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: adding affilliates starting at "
391                + topIndex + " from intial " + taskIndex);
392        // Find the end of the chain, doing a sanity check along the way.
393        boolean sane = top.mAffiliatedTaskId == task.mAffiliatedTaskId;
394        int endIndex = topIndex;
395        TaskRecord prev = top;
396        while (endIndex < recentsCount) {
397            TaskRecord cur = get(endIndex);
398            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: looking at next chain @"
399                    + endIndex + " " + cur);
400            if (cur == top) {
401                // Verify start of the chain.
402                if (cur.mNextAffiliate != null || cur.mNextAffiliateTaskId != INVALID_TASK_ID) {
403                    Slog.wtf(TAG, "Bad chain @" + endIndex
404                            + ": first task has next affiliate: " + prev);
405                    sane = false;
406                    break;
407                }
408            } else {
409                // Verify middle of the chain's next points back to the one before.
410                if (cur.mNextAffiliate != prev
411                        || cur.mNextAffiliateTaskId != prev.taskId) {
412                    Slog.wtf(TAG, "Bad chain @" + endIndex
413                            + ": middle task " + cur + " @" + endIndex
414                            + " has bad next affiliate "
415                            + cur.mNextAffiliate + " id " + cur.mNextAffiliateTaskId
416                            + ", expected " + prev);
417                    sane = false;
418                    break;
419                }
420            }
421            if (cur.mPrevAffiliateTaskId == INVALID_TASK_ID) {
422                // Chain ends here.
423                if (cur.mPrevAffiliate != null) {
424                    Slog.wtf(TAG, "Bad chain @" + endIndex
425                            + ": last task " + cur + " has previous affiliate "
426                            + cur.mPrevAffiliate);
427                    sane = false;
428                }
429                if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: end of chain @" + endIndex);
430                break;
431            } else {
432                // Verify middle of the chain's prev points to a valid item.
433                if (cur.mPrevAffiliate == null) {
434                    Slog.wtf(TAG, "Bad chain @" + endIndex
435                            + ": task " + cur + " has previous affiliate "
436                            + cur.mPrevAffiliate + " but should be id "
437                            + cur.mPrevAffiliate);
438                    sane = false;
439                    break;
440                }
441            }
442            if (cur.mAffiliatedTaskId != task.mAffiliatedTaskId) {
443                Slog.wtf(TAG, "Bad chain @" + endIndex
444                        + ": task " + cur + " has affiliated id "
445                        + cur.mAffiliatedTaskId + " but should be "
446                        + task.mAffiliatedTaskId);
447                sane = false;
448                break;
449            }
450            prev = cur;
451            endIndex++;
452            if (endIndex >= recentsCount) {
453                Slog.wtf(TAG, "Bad chain ran off index " + endIndex
454                        + ": last task " + prev);
455                sane = false;
456                break;
457            }
458        }
459        if (sane) {
460            if (endIndex < taskIndex) {
461                Slog.wtf(TAG, "Bad chain @" + endIndex
462                        + ": did not extend to task " + task + " @" + taskIndex);
463                sane = false;
464            }
465        }
466        if (sane) {
467            // All looks good, we can just move all of the affiliated tasks
468            // to the top.
469            for (int i=topIndex; i<=endIndex; i++) {
470                if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: moving affiliated " + task
471                        + " from " + i + " to " + (i-topIndex));
472                TaskRecord cur = remove(i);
473                add(i - topIndex, cur);
474            }
475            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: done moving tasks  " +  topIndex
476                    + " to " + endIndex);
477            return true;
478        }
479
480        // Whoops, couldn't do it.
481        return false;
482    }
483
484    final void addLocked(TaskRecord task) {
485        final boolean isAffiliated = task.mAffiliatedTaskId != task.taskId
486                || task.mNextAffiliateTaskId != INVALID_TASK_ID
487                || task.mPrevAffiliateTaskId != INVALID_TASK_ID;
488
489        int recentsCount = size();
490        // Quick case: never add voice sessions.
491        // TODO: VI what about if it's just an activity?
492        // Probably nothing to do here
493        if (task.voiceSession != null) {
494            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS,
495                    "addRecent: not adding voice interaction " + task);
496            return;
497        }
498        // Another quick case: check if the top-most recent task is the same.
499        if (!isAffiliated && recentsCount > 0 && get(0) == task) {
500            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: already at top: " + task);
501            return;
502        }
503        // Another quick case: check if this is part of a set of affiliated
504        // tasks that are at the top.
505        if (isAffiliated && recentsCount > 0 && task.inRecents
506                && task.mAffiliatedTaskId == get(0).mAffiliatedTaskId) {
507            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: affiliated " + get(0)
508                    + " at top when adding " + task);
509            return;
510        }
511
512        boolean needAffiliationFix = false;
513
514        // Slightly less quick case: the task is already in recents, so all we need
515        // to do is move it.
516        if (task.inRecents) {
517            int taskIndex = indexOf(task);
518            if (taskIndex >= 0) {
519                if (!isAffiliated || MOVE_AFFILIATED_TASKS_TO_FRONT) {
520                    // Simple case: this is not an affiliated task, so we just move it to the front.
521                    remove(taskIndex);
522                    add(0, task);
523                    notifyTaskPersisterLocked(task, false);
524                    if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: moving to top " + task
525                            + " from " + taskIndex);
526                    return;
527                } else {
528                    // More complicated: need to keep all affiliated tasks together.
529                    if (moveAffiliatedTasksToFront(task, taskIndex)) {
530                        // All went well.
531                        return;
532                    }
533
534                    // Uh oh...  something bad in the affiliation chain, try to rebuild
535                    // everything and then go through our general path of adding a new task.
536                    needAffiliationFix = true;
537                }
538            } else {
539                Slog.wtf(TAG, "Task with inRecent not in recents: " + task);
540                needAffiliationFix = true;
541            }
542        }
543
544        if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: trimming tasks for " + task);
545        trimForTaskLocked(task, true);
546
547        recentsCount = size();
548        final int maxRecents = ActivityManager.getMaxRecentTasksStatic();
549        while (recentsCount >= maxRecents) {
550            final TaskRecord tr = remove(recentsCount - 1);
551            tr.removedFromRecents();
552            recentsCount--;
553        }
554        task.inRecents = true;
555        if (!isAffiliated || needAffiliationFix) {
556            // If this is a simple non-affiliated task, or we had some failure trying to
557            // handle it as part of an affilated task, then just place it at the top.
558            add(0, task);
559            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: adding " + task);
560        } else if (isAffiliated) {
561            // If this is a new affiliated task, then move all of the affiliated tasks
562            // to the front and insert this new one.
563            TaskRecord other = task.mNextAffiliate;
564            if (other == null) {
565                other = task.mPrevAffiliate;
566            }
567            if (other != null) {
568                int otherIndex = indexOf(other);
569                if (otherIndex >= 0) {
570                    // Insert new task at appropriate location.
571                    int taskIndex;
572                    if (other == task.mNextAffiliate) {
573                        // We found the index of our next affiliation, which is who is
574                        // before us in the list, so add after that point.
575                        taskIndex = otherIndex+1;
576                    } else {
577                        // We found the index of our previous affiliation, which is who is
578                        // after us in the list, so add at their position.
579                        taskIndex = otherIndex;
580                    }
581                    if (DEBUG_RECENTS) Slog.d(TAG_RECENTS,
582                            "addRecent: new affiliated task added at " + taskIndex + ": " + task);
583                    add(taskIndex, task);
584
585                    // Now move everything to the front.
586                    if (moveAffiliatedTasksToFront(task, taskIndex)) {
587                        // All went well.
588                        return;
589                    }
590
591                    // Uh oh...  something bad in the affiliation chain, try to rebuild
592                    // everything and then go through our general path of adding a new task.
593                    needAffiliationFix = true;
594                } else {
595                    if (DEBUG_RECENTS) Slog.d(TAG_RECENTS,
596                            "addRecent: couldn't find other affiliation " + other);
597                    needAffiliationFix = true;
598                }
599            } else {
600                if (DEBUG_RECENTS) Slog.d(TAG_RECENTS,
601                        "addRecent: adding affiliated task without next/prev:" + task);
602                needAffiliationFix = true;
603            }
604        }
605
606        if (needAffiliationFix) {
607            if (DEBUG_RECENTS) Slog.d(TAG_RECENTS, "addRecent: regrouping affiliations");
608            cleanupLocked(task.userId);
609        }
610    }
611
612    /**
613     * If needed, remove oldest existing entries in recents that are for the same kind
614     * of task as the given one.
615     */
616    int trimForTaskLocked(TaskRecord task, boolean doTrim) {
617        int recentsCount = size();
618        final Intent intent = task.intent;
619        final boolean document = intent != null && intent.isDocument();
620        int maxRecents = task.maxRecents - 1;
621        for (int i = 0; i < recentsCount; i++) {
622            final TaskRecord tr = get(i);
623            if (task != tr) {
624                if (task.stack != null && tr.stack != null && task.stack != tr.stack) {
625                    continue;
626                }
627                if (task.userId != tr.userId) {
628                    continue;
629                }
630                if (i > MAX_RECENT_BITMAPS) {
631                    tr.freeLastThumbnail();
632                }
633                final Intent trIntent = tr.intent;
634                final boolean sameAffinity =
635                        task.affinity != null && task.affinity.equals(tr.affinity);
636                final boolean sameIntentFilter = intent != null && intent.filterEquals(trIntent);
637                boolean multiTasksAllowed = false;
638                final int flags = intent.getFlags();
639                if ((flags & (FLAG_ACTIVITY_NEW_TASK | FLAG_ACTIVITY_NEW_DOCUMENT)) != 0
640                        && (flags & FLAG_ACTIVITY_MULTIPLE_TASK) != 0) {
641                    multiTasksAllowed = true;
642                }
643                final boolean trIsDocument = trIntent != null && trIntent.isDocument();
644                final boolean bothDocuments = document && trIsDocument;
645                if (!sameAffinity && !sameIntentFilter && !bothDocuments) {
646                    continue;
647                }
648
649                if (bothDocuments) {
650                    // Do these documents belong to the same activity?
651                    final boolean sameActivity = task.realActivity != null
652                            && tr.realActivity != null
653                            && task.realActivity.equals(tr.realActivity);
654                    // If the document is open in another app or is not the same
655                    // document, we don't need to trim it.
656                    if (!sameActivity || !sameIntentFilter || multiTasksAllowed) {
657                        continue;
658                    // Otherwise only trim if we are over our max recents for this task
659                    } else if (maxRecents > 0 && !doTrim) {
660                        --maxRecents;
661                        continue;
662                    }
663                    // Hit the maximum number of documents for this task. Fall through
664                    // and remove this document from recents.
665                } else if (document || trIsDocument) {
666                    // Only one of these is a document. Not the droid we're looking for.
667                    continue;
668                }
669            }
670
671            if (!doTrim) {
672                // If the caller is not actually asking for a trim, just tell them we reached
673                // a point where the trim would happen.
674                return i;
675            }
676
677            // Either task and tr are the same or, their affinities match or their intents match
678            // and neither of them is a document, or they are documents using the same activity
679            // and their maxRecents has been reached.
680            tr.disposeThumbnail();
681            remove(i);
682            if (task != tr) {
683                tr.removedFromRecents();
684            }
685            i--;
686            recentsCount--;
687            if (task.intent == null) {
688                // If the new recent task we are adding is not fully
689                // specified, then replace it with the existing recent task.
690                task = tr;
691            }
692            notifyTaskPersisterLocked(tr, false);
693        }
694
695        return -1;
696    }
697
698    // Sort by taskId
699    private static Comparator<TaskRecord> sTaskRecordComparator = new Comparator<TaskRecord>() {
700        @Override
701        public int compare(TaskRecord lhs, TaskRecord rhs) {
702            return rhs.taskId - lhs.taskId;
703        }
704    };
705
706    // Extract the affiliates of the chain containing recent at index start.
707    private int processNextAffiliateChainLocked(int start) {
708        final TaskRecord startTask = get(start);
709        final int affiliateId = startTask.mAffiliatedTaskId;
710
711        // Quick identification of isolated tasks. I.e. those not launched behind.
712        if (startTask.taskId == affiliateId && startTask.mPrevAffiliate == null &&
713                startTask.mNextAffiliate == null) {
714            // There is still a slim chance that there are other tasks that point to this task
715            // and that the chain is so messed up that this task no longer points to them but
716            // the gain of this optimization outweighs the risk.
717            startTask.inRecents = true;
718            return start + 1;
719        }
720
721        // Remove all tasks that are affiliated to affiliateId and put them in mTmpRecents.
722        mTmpRecents.clear();
723        for (int i = size() - 1; i >= start; --i) {
724            final TaskRecord task = get(i);
725            if (task.mAffiliatedTaskId == affiliateId) {
726                remove(i);
727                mTmpRecents.add(task);
728            }
729        }
730
731        // Sort them all by taskId. That is the order they were create in and that order will
732        // always be correct.
733        Collections.sort(mTmpRecents, sTaskRecordComparator);
734
735        // Go through and fix up the linked list.
736        // The first one is the end of the chain and has no next.
737        final TaskRecord first = mTmpRecents.get(0);
738        first.inRecents = true;
739        if (first.mNextAffiliate != null) {
740            Slog.w(TAG, "Link error 1 first.next=" + first.mNextAffiliate);
741            first.setNextAffiliate(null);
742            notifyTaskPersisterLocked(first, false);
743        }
744        // Everything in the middle is doubly linked from next to prev.
745        final int tmpSize = mTmpRecents.size();
746        for (int i = 0; i < tmpSize - 1; ++i) {
747            final TaskRecord next = mTmpRecents.get(i);
748            final TaskRecord prev = mTmpRecents.get(i + 1);
749            if (next.mPrevAffiliate != prev) {
750                Slog.w(TAG, "Link error 2 next=" + next + " prev=" + next.mPrevAffiliate +
751                        " setting prev=" + prev);
752                next.setPrevAffiliate(prev);
753                notifyTaskPersisterLocked(next, false);
754            }
755            if (prev.mNextAffiliate != next) {
756                Slog.w(TAG, "Link error 3 prev=" + prev + " next=" + prev.mNextAffiliate +
757                        " setting next=" + next);
758                prev.setNextAffiliate(next);
759                notifyTaskPersisterLocked(prev, false);
760            }
761            prev.inRecents = true;
762        }
763        // The last one is the beginning of the list and has no prev.
764        final TaskRecord last = mTmpRecents.get(tmpSize - 1);
765        if (last.mPrevAffiliate != null) {
766            Slog.w(TAG, "Link error 4 last.prev=" + last.mPrevAffiliate);
767            last.setPrevAffiliate(null);
768            notifyTaskPersisterLocked(last, false);
769        }
770
771        // Insert the group back into mRecentTasks at start.
772        addAll(start, mTmpRecents);
773        mTmpRecents.clear();
774
775        // Let the caller know where we left off.
776        return start + tmpSize;
777    }
778}
779