<commit_before>﻿// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Threading.Tasks;
using Microsoft.Identity.Client.AuthScheme.Bearer;
using Microsoft.Identity.Client.Cache;
using Microsoft.Identity.Client.Cache.Items;
using Microsoft.Identity.Client.Cache.Keys;
using Microsoft.Identity.Client.Instance;
using Microsoft.Identity.Client.Instance.Discovery;
using Microsoft.Identity.Client.Internal;
using Microsoft.Identity.Client.Internal.Requests;
using Microsoft.Identity.Client.OAuth2;
using Microsoft.Identity.Client.Utils;

namespace Microsoft.Identity.Client
{
    /// <summary>
    /// IMPORTANT: this class is perf critical; any changes must be benchmarked using Microsoft.Identity.Test.Performace.
    /// More information about how to test and what data to look for is in https://aka.ms/msal-net-performance-testing.
    /// </summary>
    public sealed partial class TokenCache : ITokenCacheInternal
    {
        async Task<Tuple<MsalAccessTokenCacheItem, MsalIdTokenCacheItem, Account>> ITokenCacheInternal.SaveTokenResponseAsync(
            AuthenticationRequestParameters requestParams,
            MsalTokenResponse response)
        {
            response.Log(requestParams.RequestContext.Logger, LogLevel.Verbose);

            MsalAccessTokenCacheItem msalAccessTokenCacheItem = null;
            MsalRefreshTokenCacheItem msalRefreshTokenCacheItem = null;
            MsalIdTokenCacheItem msalIdTokenCacheItem = null;
            MsalAccountCacheItem msalAccountCacheItem = null;

            IdToken idToken = IdToken.Parse(response.IdToken);
            if (idToken == null)
            {
                requestParams.RequestContext.Logger.Info("ID Token not present in response. ");
            }

            var tenantId = GetTenantId(idToken, requestParams);

            bool isAdfsAuthority = requestParams.AuthorityInfo.AuthorityType == AuthorityType.Adfs;
            string preferredUsername = GetPreferredUsernameFromIdToken(isAdfsAuthority, idToken);
            string username = isAdfsAuthority ? idToken?.Upn : preferredUsername;
            string homeAccountId = GetHomeAccountId(requestParams, response, idToken);
            string suggestedWebCacheKey = SuggestedWebCacheKeyFactory.GetKeyFromResponse(requestParams, homeAccountId);

            // Do a full instance discovery when saving tokens (if not cached),
            // so that the PreferredNetwork environment is up to date.
            var instanceDiscoveryMetadata = await ServiceBundle.InstanceDiscoveryManager
                                .GetMetadataEntryAsync(
                                    requestParams.Authority.AuthorityInfo,
                                    requestParams.RequestContext)
                                .ConfigureAwait(false);

            #region Create Cache Objects
            if (!string.IsNullOrEmpty(response.AccessToken))
            {
                msalAccessTokenCacheItem =
                    new MsalAccessTokenCacheItem(
                        instanceDiscoveryMetadata.PreferredCache,
                        requestParams.AppConfig.ClientId,
                        response,
                        tenantId,
                        homeAccountId,
                        requestParams.AuthenticationScheme.KeyId)
                    {
                        UserAssertionHash = requestParams.UserAssertion?.AssertionHash,
                        IsAdfs = isAdfsAuthority
                    };
            }

            if (!string.IsNullOrEmpty(response.RefreshToken))
            {
                msalRefreshTokenCacheItem = new MsalRefreshTokenCacheItem(
                                    instanceDiscoveryMetadata.PreferredCache,
                                    requestParams.AppConfig.ClientId,
                                    response,
                                    homeAccountId);

                if (!_featureFlags.IsFociEnabled)
                {
                    msalRefreshTokenCacheItem.FamilyId = null;
                }
            }

            Dictionary<string, string> wamAccountIds = GetWamAccountIds(requestParams, response);
            Account account;
            if (idToken != null)
            {
                msalIdTokenCacheItem = new MsalIdTokenCacheItem(
                    instanceDiscoveryMetadata.PreferredCache,
                    requestParams.AppConfig.ClientId,
                    response,
                    tenantId,
                    homeAccountId)
                {
                    IsAdfs = isAdfsAuthority
                };

                msalAccountCacheItem = new MsalAccountCacheItem(
                             instanceDiscoveryMetadata.PreferredCache,
                             response.ClientInfo,
                             homeAccountId,
                             idToken,
                             preferredUsername,
                             tenantId,
                             wamAccountIds);
            }

            #endregion

            account = new Account(
                    homeAccountId,
                    username,
                    instanceDiscoveryMetadata.PreferredNetwork, 
                    wamAccountIds);
            requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Entering token cache semaphore. ");
            await _semaphoreSlim.WaitAsync().ConfigureAwait(false);
            requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Entered token cache semaphore. ");

            try
            {
#pragma warning disable CS0618 // Type or member is obsolete
                HasStateChanged = true;
#pragma warning restore CS0618 // Type or member is obsolete

                try
                {
                    ITokenCacheInternal tokenCacheInternal = this;
                    if (tokenCacheInternal.IsTokenCacheSerialized())
                    {
                        var args = new TokenCacheNotificationArgs(
                            this,
                            ClientId,
                            account,
                            hasStateChanged: true,
                            tokenCacheInternal.IsApplicationCache,
                            hasTokens: tokenCacheInternal.HasTokensNoLocks(),
                            requestParams.RequestContext.UserCancellationToken,
                            suggestedCacheKey: suggestedWebCacheKey);

                        Stopwatch sw = Stopwatch.StartNew();

                        await tokenCacheInternal.OnBeforeAccessAsync(args).ConfigureAwait(false);
                        await tokenCacheInternal.OnBeforeWriteAsync(args).ConfigureAwait(false);
                        requestParams.RequestContext.ApiEvent.DurationInCacheInMs += sw.ElapsedMilliseconds;                        
                    }

                    if (msalAccessTokenCacheItem != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving AT in cache and removing overlapping ATs...");

                        DeleteAccessTokensWithIntersectingScopes(
                            requestParams,
                            instanceDiscoveryMetadata.Aliases,
                            tenantId,
                            msalAccessTokenCacheItem.ScopeSet,
                            msalAccessTokenCacheItem.HomeAccountId,
                            msalAccessTokenCacheItem.TokenType);

                        _accessor.SaveAccessToken(msalAccessTokenCacheItem);
                    }

                    if (idToken != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving Id Token and Account in cache ...");
                        _accessor.SaveIdToken(msalIdTokenCacheItem);
                        MergeWamAccountIds(msalAccountCacheItem);
                        _accessor.SaveAccount(msalAccountCacheItem);
                    }

                    // if server returns the refresh token back, save it in the cache.
                    if (msalRefreshTokenCacheItem != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving RT in cache...");
                        _accessor.SaveRefreshToken(msalRefreshTokenCacheItem);
                    }

                    UpdateAppMetadata(requestParams.AppConfig.ClientId, instanceDiscoveryMetadata.PreferredCache, response.FamilyId);

                    // Do not save RT in ADAL cache for client credentials flow or B2C                        
                    if (ServiceBundle.Config.LegacyCacheCompatibilityEnabled &&
                        !requestParams.IsClientCredentialRequest &&
                        requestParams.AuthorityInfo.AuthorityType != AuthorityType.B2C)
                    {
                        var tenatedAuthority = Authority.CreateAuthorityWithTenant(requestParams.AuthorityInfo, tenantId);
                        var authorityWithPreferredCache = Authority.CreateAuthorityWithEnvironment(
                                tenatedAuthority.AuthorityInfo,
                                instanceDiscoveryMetadata.PreferredCache);

                        CacheFallbackOperations.WriteAdalRefreshToken(
                            Logger,
                            LegacyCachePersistence,
                            msalRefreshTokenCacheItem,
                            msalIdTokenCacheItem,
                            authorityWithPreferredCache.AuthorityInfo.CanonicalAuthority,
                            msalIdTokenCacheItem.IdToken.ObjectId,
                            response.Scope);
                    }
                }
                finally
                {
                    ITokenCacheInternal tokenCacheInternal = this;
                    if (tokenCacheInternal.IsTokenCacheSerialized())
                    {
                        var args = new TokenCacheNotificationArgs(
                            this,
                            ClientId,
                            account,
                            hasStateChanged: true,
                            tokenCacheInternal.IsApplicationCache,
                            tokenCacheInternal.HasTokensNoLocks(),
                            requestParams.RequestContext.UserCancellationToken,
                            suggestedCacheKey: suggestedWebCacheKey);

                        Stopwatch sw = Stopwatch.StartNew();
                        await tokenCacheInternal.OnAfterAccessAsync(args).ConfigureAwait(false);
                        requestParams.RequestContext.ApiEvent.DurationInCacheInMs += sw.ElapsedMilliseconds;
                    }
#pragma warning disable CS0618 // Type or member is obsolete
                    HasStateChanged = false;
#pragma warning restore CS0618 // Type or member is obsolete
                }

                return Tuple.Create(msalAccessTokenCacheItem, msalIdTokenCacheItem, account);
            }
            finally
            {
                _semaphoreSlim.Release();
                requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Released token cache semaphore. ");
            }
        }

        private string GetTenantId(IdToken idToken, AuthenticationRequestParameters requestParams)
        {
            // If the input authority was tenanted, use that tenant over the IdToken.Tenant
            // otherwise, this will result in cache misses
            return Authority.CreateAuthorityWithTenant(
                requestParams.Authority.AuthorityInfo, 
                idToken?.TenantId).TenantId;
        }

        private void MergeWamAccountIds(MsalAccountCacheItem msalAccountCacheItem)
        {
            var existingAccount = _accessor.GetAllAccounts()
                .SingleOrDefault(
                    acc => string.Equals(
                        acc.GetKey().ToString(),
                        msalAccountCacheItem.GetKey().ToString(),
                        StringComparison.OrdinalIgnoreCase));
            var existingWamAccountIds = existingAccount?.WamAccountIds;
            msalAccountCacheItem.WamAccountIds.MergeDifferentEntries(existingWamAccountIds);
        }

        private static Dictionary<string, string> GetWamAccountIds(AuthenticationRequestParameters requestParams, MsalTokenResponse response)
        {
            if (!string.IsNullOrEmpty(response.WamAccountId))
            {
                return new Dictionary<string, string>() { { requestParams.AppConfig.ClientId, response.WamAccountId } };
            }

            return new Dictionary<string, string>();
        }

        private static string GetHomeAccountId(AuthenticationRequestParameters requestParams, MsalTokenResponse response, IdToken idToken)
        {
            string subject = idToken?.Subject;
            if (idToken?.Subject != null)
            {
                requestParams.RequestContext.Logger.Info("Subject not present in Id token. ");
            }

            ClientInfo clientInfo = response.ClientInfo != null ? ClientInfo.CreateFromJson(response.ClientInfo) : null;
            string homeAccountId = clientInfo?.ToAccountIdentifier() ?? subject; // ADFS does not have client info, so we use subject
            return homeAccountId;
        }

        private static string GetPreferredUsernameFromIdToken(bool isAdfsAuthority, IdToken idToken)
        {
            // The preferred_username value cannot be null or empty in order to comply with the ADAL/MSAL Unified cache schema.
            // It will be set to "preferred_username not in id token"
            if (idToken == null)
            {
                return NullPreferredUsernameDisplayLabel;
            }

            if (string.IsNullOrWhiteSpace(idToken.PreferredUsername))
            {
                if (isAdfsAuthority)
                {
                    //The direct to ADFS scenario does not return preferred_username in the id token so it needs to be set to the UPN
                    return !string.IsNullOrEmpty(idToken.Upn)
                        ? idToken.Upn
                        : NullPreferredUsernameDisplayLabel;
                }
                return NullPreferredUsernameDisplayLabel;
            }

            return idToken.PreferredUsername;
        }

        /// <summary>
        /// IMPORTANT: this class is perf critical; any changes must be benchmarked using Microsoft.Identity.Test.Performace.
        /// More information about how to test and what data to look for is in https://aka.ms/msal-net-performance-testing.
        /// 
        /// Scenario: client_creds with default in-memory cache can get to ~500k tokens
        /// </summary>
        async Task<MsalAccessTokenCacheItem> ITokenCacheInternal.FindAccessTokenAsync(
            AuthenticationRequestParameters requestParams)
        {
            var logger = requestParams.RequestContext.Logger;
            // no authority passed
            if (requestParams.AuthorityInfo?.CanonicalAuthority == null)
            {
                logger.Warning("FindAccessToken: No authority provided. Skipping cache lookup. ");
                return null;
            }

            // take a snapshot of the access tokens to avoid problems where the underlying collection is changed,
            // as this method is NOT locked by the semaphore
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems = GetAllAccessTokensWithNoLocks(true).ToList();            

            tokenCacheItems = FilterByHomeAccountTenantOrAssertion(requestParams, tokenCacheItems);
            tokenCacheItems = FilterByTokenType(requestParams, tokenCacheItems);
            tokenCacheItems = FilterByScopes(requestParams, tokenCacheItems);
            tokenCacheItems = await FilterByEnvironmentAsync(requestParams, tokenCacheItems).ConfigureAwait(false);

            // perf: take a snapshot as calling Count(), Any() etc. on the IEnumerable evaluates it each time
            IReadOnlyList<MsalAccessTokenCacheItem> finalList = tokenCacheItems.ToList();

            CacheInfoTelemetry cacheInfoTelemetry = CacheInfoTelemetry.None;

            // no match
            if (finalList.Count == 0)
            {
                logger.Verbose("No tokens found for matching authority, client_id, user and scopes. ");
                return null;
            }

            MsalAccessTokenCacheItem msalAccessTokenCacheItem = GetSingleResult(requestParams, finalList);
            msalAccessTokenCacheItem = FilterByKeyId(msalAccessTokenCacheItem, requestParams);
            msalAccessTokenCacheItem = FilterByExpiry(msalAccessTokenCacheItem, requestParams);

            if (msalAccessTokenCacheItem == null)
            {
                cacheInfoTelemetry = CacheInfoTelemetry.Expired;
            }

            requestParams.RequestContext.ApiEvent.CacheInfo = (int)cacheInfoTelemetry;

            return msalAccessTokenCacheItem; 
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByScopes(
            AuthenticationRequestParameters requestParams,
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            var logger = requestParams.RequestContext.Logger;
            var requestScopes = requestParams.Scope.Where(s =>
                !OAuth2Value.ReservedScopes.Contains(s));

            tokenCacheItems = tokenCacheItems.FilterWithLogging(
                item => {
                    bool accepted = ScopeHelper.ScopeContains(item.ScopeSet, requestScopes);
                    
                    if (logger.IsLoggingEnabled(LogLevel.Verbose))
                    {
                        logger.Verbose($"Access token with scopes {string.Join(" ", item.ScopeSet)} " +
                            $"passes scope filter? {accepted} ");
                    }
                    return accepted;
                    },
                logger,
                "Filtering by scopes");

            return tokenCacheItems;
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByTokenType(AuthenticationRequestParameters requestParams, IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                            string.Equals(
                                item.TokenType ?? BearerAuthenticationScheme.BearerTokenType,
                                requestParams.AuthenticationScheme.AccessTokenType,
                                StringComparison.OrdinalIgnoreCase),
                            requestParams.RequestContext.Logger,
                            "Filtering by token type");
            return tokenCacheItems;
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByHomeAccountTenantOrAssertion(
            AuthenticationRequestParameters requestParams,
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            string requestTenantId = requestParams.Authority.TenantId;
            bool filterByTenantId = true;

            if (requestParams.UserAssertion != null) // OBO
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                                !string.IsNullOrEmpty(item.UserAssertionHash) &&
                                item.UserAssertionHash.Equals(requestParams.UserAssertion.AssertionHash, StringComparison.OrdinalIgnoreCase),
                                requestParams.RequestContext.Logger,
                                "Filtering by user assertion id");

                // OBO calls FindAccessTokenAsync directly, but we are not able to resolve the authority 
                // unless the developer has configured a tenanted authority. If they have configured /common
                // then we cannot filter by tenant and will use whatever is in the cache.
                filterByTenantId =
                    !string.IsNullOrEmpty(requestTenantId) &&
                    !AadAuthority.IsCommonOrganizationsOrConsumersTenant(requestTenantId);
            }

            if (filterByTenantId)
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                    string.Equals(item.TenantId ?? string.Empty, requestTenantId ?? string.Empty, StringComparison.OrdinalIgnoreCase),
                    requestParams.RequestContext.Logger,
                    "Filtering by tenant id");
            }
            else
            {
                requestParams.RequestContext.Logger.Warning("Have not filtered by tenant ID. " +
                    "This can happen in OBO scenario where authority is /common or /organizations. " +
                    "Please use tenanted authority.");
            }

            // Only AcquireTokenSilent has an IAccount in the request that can be used for filtering
            if (requestParams.ApiId != TelemetryCore.Internal.Events.ApiEvent.ApiIds.AcquireTokenForClient &&
                requestParams.ApiId != TelemetryCore.Internal.Events.ApiEvent.ApiIds.AcquireTokenOnBehalfOf)
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item => item.HomeAccountId.Equals(
                                requestParams.Account.HomeAccountId?.Identifier, StringComparison.OrdinalIgnoreCase),
                                requestParams.RequestContext.Logger,
                                "Filtering by home account id");
            }

            return tokenCacheItems;
        }

        private MsalAccessTokenCacheItem FilterByExpiry(MsalAccessTokenCacheItem msalAccessTokenCacheItem, AuthenticationRequestParameters requestParams)
        {
            var logger = requestParams.RequestContext.Logger;
            if (msalAccessTokenCacheItem != null)
            {

                if (msalAccessTokenCacheItem.ExpiresOn > DateTime.UtcNow + AccessTokenExpirationBuffer)
                {
                    // due to https://github.com/AzureAD/microsoft-authentication-library-for-dotnet/issues/1806
                    if (msalAccessTokenCacheItem.ExpiresOn > DateTime.UtcNow + TimeSpan.FromDays(ExpirationTooLongInDays))
                    {
                        logger.Error(
                           "Access token expiration too large. This can be the result of a bug or corrupt cache. Token will be ignored as it is likely expired." +
                           GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                        return null;
                    }

                    if (logger.IsLoggingEnabled(LogLevel.Info))
                    {
                        logger.Info(
                            "Access token is not expired. Returning the found cache entry. " +
                            GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                    }

                    return msalAccessTokenCacheItem;
                }

                if (ServiceBundle.Config.IsExtendedTokenLifetimeEnabled &&
                    msalAccessTokenCacheItem.ExtendedExpiresOn > DateTime.UtcNow + AccessTokenExpirationBuffer)
                {
                    if (logger.IsLoggingEnabled(LogLevel.Info))
                    {
                        logger.Info(
                            "Access token is expired.  IsExtendedLifeTimeEnabled=TRUE and ExtendedExpiresOn is not exceeded.  Returning the found cache entry. " +
                            GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                    }

                    msalAccessTokenCacheItem.IsExtendedLifeTimeToken = true;
                    return msalAccessTokenCacheItem;
                }

                if (logger.IsLoggingEnabled(LogLevel.Info))
                {
                    logger.Info(
                        "Access token has expired or about to expire. " +
                        GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                }
            }

            return null;
        }

        private static MsalAccessTokenCacheItem GetSingleResult(
            AuthenticationRequestParameters requestParams,
            IReadOnlyList<MsalAccessTokenCacheItem> filteredItems)
        {
            // if only one cached token found
            if (filteredItems.Count == 1)
            {
                return filteredItems[0];
            }

            requestParams.RequestContext.Logger.Error("Multiple tokens found for matching authority, client_id, user and scopes. ");
            throw new MsalClientException(
                MsalError.MultipleTokensMatchedError,
                MsalErrorMessage.MultipleTokensMatched);
        }

        private async Task<IEnumerable<MsalAccessTokenCacheItem>> FilterByEnvironmentAsync(AuthenticationRequestParameters requestParams, IEnumerable<MsalAccessTokenCacheItem> filteredItems)
        {
            // at this point we need env aliases, try to get them without a discovery call
            var instanceMetadata = await ServiceBundle.InstanceDiscoveryManager.GetMetadataEntryTryAvoidNetworkAsync(
                                     requestParams.AuthorityInfo,
                                     filteredItems.Select(at => at.Environment),  // if all environments are known, a network call can be avoided
                                     requestParams.RequestContext)
                            .ConfigureAwait(false);

            // In case we're sharing the cache with an MSAL that does not implement env aliasing,
            // it's possible (but unlikely), that we have multiple ATs from the same alias family.
            // To overcome some of these use cases, try to filter just by preferred cache alias
            var filteredByPreferredAlias = filteredItems.Where(
                at => at.Environment.Equals(instanceMetadata.PreferredCache, StringComparison.OrdinalIgnoreCase));

            if (filteredByPreferredAlias.Any())
            {
                return filteredByPreferredAlias;
            }

            return filteredItems.Where(
                item => instanceMetadata.Aliases.ContainsOrdinalIgnoreCase(item.Environment));
        }

        private MsalAccessTokenCacheItem FilterByKeyId(MsalAccessTokenCacheItem item, AuthenticationRequestParameters authenticationRequest)
        {
            if (item == null)
            {
                return null;
            }

            string requestKid = authenticationRequest.AuthenticationScheme.KeyId;
            if (string.IsNullOrEmpty(item.KeyId) && string.IsNullOrEmpty(requestKid))
            {
                authenticationRequest.RequestContext.Logger.Verbose("Bearer token found");
                return item;
            }

            if (string.Equals(item.KeyId, requestKid, StringComparison.OrdinalIgnoreCase))
            {
                authenticationRequest.RequestContext.Logger.Verbose("Keyed token found");
                return item;
            }

            authenticationRequest.RequestContext.Logger.Info(
                    string.Format(
                        CultureInfo.InvariantCulture,
                        "A token bound to the wrong key was found. Token key id: {0} Request key id: {1}",
                        item.KeyId,<commit_msg>Add extra filtering by env logs. (#2678)<commit_after>﻿// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT License.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Globalization;
using System.Linq;
using System.Threading.Tasks;
using Microsoft.Identity.Client.AuthScheme.Bearer;
using Microsoft.Identity.Client.Cache;
using Microsoft.Identity.Client.Cache.Items;
using Microsoft.Identity.Client.Cache.Keys;
using Microsoft.Identity.Client.Instance;
using Microsoft.Identity.Client.Instance.Discovery;
using Microsoft.Identity.Client.Internal;
using Microsoft.Identity.Client.Internal.Requests;
using Microsoft.Identity.Client.OAuth2;
using Microsoft.Identity.Client.Utils;

namespace Microsoft.Identity.Client
{
    /// <summary>
    /// IMPORTANT: this class is perf critical; any changes must be benchmarked using Microsoft.Identity.Test.Performace.
    /// More information about how to test and what data to look for is in https://aka.ms/msal-net-performance-testing.
    /// </summary>
    public sealed partial class TokenCache : ITokenCacheInternal
    {
        async Task<Tuple<MsalAccessTokenCacheItem, MsalIdTokenCacheItem, Account>> ITokenCacheInternal.SaveTokenResponseAsync(
            AuthenticationRequestParameters requestParams,
            MsalTokenResponse response)
        {
            response.Log(requestParams.RequestContext.Logger, LogLevel.Verbose);

            MsalAccessTokenCacheItem msalAccessTokenCacheItem = null;
            MsalRefreshTokenCacheItem msalRefreshTokenCacheItem = null;
            MsalIdTokenCacheItem msalIdTokenCacheItem = null;
            MsalAccountCacheItem msalAccountCacheItem = null;

            IdToken idToken = IdToken.Parse(response.IdToken);
            if (idToken == null)
            {
                requestParams.RequestContext.Logger.Info("ID Token not present in response. ");
            }

            var tenantId = GetTenantId(idToken, requestParams);

            bool isAdfsAuthority = requestParams.AuthorityInfo.AuthorityType == AuthorityType.Adfs;
            string preferredUsername = GetPreferredUsernameFromIdToken(isAdfsAuthority, idToken);
            string username = isAdfsAuthority ? idToken?.Upn : preferredUsername;
            string homeAccountId = GetHomeAccountId(requestParams, response, idToken);
            string suggestedWebCacheKey = SuggestedWebCacheKeyFactory.GetKeyFromResponse(requestParams, homeAccountId);

            // Do a full instance discovery when saving tokens (if not cached),
            // so that the PreferredNetwork environment is up to date.
            var instanceDiscoveryMetadata = await ServiceBundle.InstanceDiscoveryManager
                                .GetMetadataEntryAsync(
                                    requestParams.Authority.AuthorityInfo,
                                    requestParams.RequestContext)
                                .ConfigureAwait(false);

            #region Create Cache Objects
            if (!string.IsNullOrEmpty(response.AccessToken))
            {
                msalAccessTokenCacheItem =
                    new MsalAccessTokenCacheItem(
                        instanceDiscoveryMetadata.PreferredCache,
                        requestParams.AppConfig.ClientId,
                        response,
                        tenantId,
                        homeAccountId,
                        requestParams.AuthenticationScheme.KeyId)
                    {
                        UserAssertionHash = requestParams.UserAssertion?.AssertionHash,
                        IsAdfs = isAdfsAuthority
                    };
            }

            if (!string.IsNullOrEmpty(response.RefreshToken))
            {
                msalRefreshTokenCacheItem = new MsalRefreshTokenCacheItem(
                                    instanceDiscoveryMetadata.PreferredCache,
                                    requestParams.AppConfig.ClientId,
                                    response,
                                    homeAccountId);

                if (!_featureFlags.IsFociEnabled)
                {
                    msalRefreshTokenCacheItem.FamilyId = null;
                }
            }

            Dictionary<string, string> wamAccountIds = GetWamAccountIds(requestParams, response);
            Account account;
            if (idToken != null)
            {
                msalIdTokenCacheItem = new MsalIdTokenCacheItem(
                    instanceDiscoveryMetadata.PreferredCache,
                    requestParams.AppConfig.ClientId,
                    response,
                    tenantId,
                    homeAccountId)
                {
                    IsAdfs = isAdfsAuthority
                };

                msalAccountCacheItem = new MsalAccountCacheItem(
                             instanceDiscoveryMetadata.PreferredCache,
                             response.ClientInfo,
                             homeAccountId,
                             idToken,
                             preferredUsername,
                             tenantId,
                             wamAccountIds);
            }

            #endregion

            account = new Account(
                    homeAccountId,
                    username,
                    instanceDiscoveryMetadata.PreferredNetwork, 
                    wamAccountIds);
            requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Entering token cache semaphore. ");
            await _semaphoreSlim.WaitAsync().ConfigureAwait(false);
            requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Entered token cache semaphore. ");

            try
            {
#pragma warning disable CS0618 // Type or member is obsolete
                HasStateChanged = true;
#pragma warning restore CS0618 // Type or member is obsolete

                try
                {
                    ITokenCacheInternal tokenCacheInternal = this;
                    if (tokenCacheInternal.IsTokenCacheSerialized())
                    {
                        var args = new TokenCacheNotificationArgs(
                            this,
                            ClientId,
                            account,
                            hasStateChanged: true,
                            tokenCacheInternal.IsApplicationCache,
                            hasTokens: tokenCacheInternal.HasTokensNoLocks(),
                            requestParams.RequestContext.UserCancellationToken,
                            suggestedCacheKey: suggestedWebCacheKey);

                        Stopwatch sw = Stopwatch.StartNew();

                        await tokenCacheInternal.OnBeforeAccessAsync(args).ConfigureAwait(false);
                        await tokenCacheInternal.OnBeforeWriteAsync(args).ConfigureAwait(false);
                        requestParams.RequestContext.ApiEvent.DurationInCacheInMs += sw.ElapsedMilliseconds;                        
                    }

                    if (msalAccessTokenCacheItem != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving AT in cache and removing overlapping ATs...");

                        DeleteAccessTokensWithIntersectingScopes(
                            requestParams,
                            instanceDiscoveryMetadata.Aliases,
                            tenantId,
                            msalAccessTokenCacheItem.ScopeSet,
                            msalAccessTokenCacheItem.HomeAccountId,
                            msalAccessTokenCacheItem.TokenType);

                        _accessor.SaveAccessToken(msalAccessTokenCacheItem);
                    }

                    if (idToken != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving Id Token and Account in cache ...");
                        _accessor.SaveIdToken(msalIdTokenCacheItem);
                        MergeWamAccountIds(msalAccountCacheItem);
                        _accessor.SaveAccount(msalAccountCacheItem);
                    }

                    // if server returns the refresh token back, save it in the cache.
                    if (msalRefreshTokenCacheItem != null)
                    {
                        requestParams.RequestContext.Logger.Info("Saving RT in cache...");
                        _accessor.SaveRefreshToken(msalRefreshTokenCacheItem);
                    }

                    UpdateAppMetadata(requestParams.AppConfig.ClientId, instanceDiscoveryMetadata.PreferredCache, response.FamilyId);

                    // Do not save RT in ADAL cache for client credentials flow or B2C                        
                    if (ServiceBundle.Config.LegacyCacheCompatibilityEnabled &&
                        !requestParams.IsClientCredentialRequest &&
                        requestParams.AuthorityInfo.AuthorityType != AuthorityType.B2C)
                    {
                        var tenatedAuthority = Authority.CreateAuthorityWithTenant(requestParams.AuthorityInfo, tenantId);
                        var authorityWithPreferredCache = Authority.CreateAuthorityWithEnvironment(
                                tenatedAuthority.AuthorityInfo,
                                instanceDiscoveryMetadata.PreferredCache);

                        CacheFallbackOperations.WriteAdalRefreshToken(
                            Logger,
                            LegacyCachePersistence,
                            msalRefreshTokenCacheItem,
                            msalIdTokenCacheItem,
                            authorityWithPreferredCache.AuthorityInfo.CanonicalAuthority,
                            msalIdTokenCacheItem.IdToken.ObjectId,
                            response.Scope);
                    }
                }
                finally
                {
                    ITokenCacheInternal tokenCacheInternal = this;
                    if (tokenCacheInternal.IsTokenCacheSerialized())
                    {
                        var args = new TokenCacheNotificationArgs(
                            this,
                            ClientId,
                            account,
                            hasStateChanged: true,
                            tokenCacheInternal.IsApplicationCache,
                            tokenCacheInternal.HasTokensNoLocks(),
                            requestParams.RequestContext.UserCancellationToken,
                            suggestedCacheKey: suggestedWebCacheKey);

                        Stopwatch sw = Stopwatch.StartNew();
                        await tokenCacheInternal.OnAfterAccessAsync(args).ConfigureAwait(false);
                        requestParams.RequestContext.ApiEvent.DurationInCacheInMs += sw.ElapsedMilliseconds;
                    }
#pragma warning disable CS0618 // Type or member is obsolete
                    HasStateChanged = false;
#pragma warning restore CS0618 // Type or member is obsolete
                }

                return Tuple.Create(msalAccessTokenCacheItem, msalIdTokenCacheItem, account);
            }
            finally
            {
                _semaphoreSlim.Release();
                requestParams.RequestContext.Logger.Verbose("[SaveTokenResponseAsync] Released token cache semaphore. ");
            }
        }

        private string GetTenantId(IdToken idToken, AuthenticationRequestParameters requestParams)
        {
            // If the input authority was tenanted, use that tenant over the IdToken.Tenant
            // otherwise, this will result in cache misses
            return Authority.CreateAuthorityWithTenant(
                requestParams.Authority.AuthorityInfo, 
                idToken?.TenantId).TenantId;
        }

        private void MergeWamAccountIds(MsalAccountCacheItem msalAccountCacheItem)
        {
            var existingAccount = _accessor.GetAllAccounts()
                .SingleOrDefault(
                    acc => string.Equals(
                        acc.GetKey().ToString(),
                        msalAccountCacheItem.GetKey().ToString(),
                        StringComparison.OrdinalIgnoreCase));
            var existingWamAccountIds = existingAccount?.WamAccountIds;
            msalAccountCacheItem.WamAccountIds.MergeDifferentEntries(existingWamAccountIds);
        }

        private static Dictionary<string, string> GetWamAccountIds(AuthenticationRequestParameters requestParams, MsalTokenResponse response)
        {
            if (!string.IsNullOrEmpty(response.WamAccountId))
            {
                return new Dictionary<string, string>() { { requestParams.AppConfig.ClientId, response.WamAccountId } };
            }

            return new Dictionary<string, string>();
        }

        private static string GetHomeAccountId(AuthenticationRequestParameters requestParams, MsalTokenResponse response, IdToken idToken)
        {
            string subject = idToken?.Subject;
            if (idToken?.Subject != null)
            {
                requestParams.RequestContext.Logger.Info("Subject not present in Id token. ");
            }

            ClientInfo clientInfo = response.ClientInfo != null ? ClientInfo.CreateFromJson(response.ClientInfo) : null;
            string homeAccountId = clientInfo?.ToAccountIdentifier() ?? subject; // ADFS does not have client info, so we use subject
            return homeAccountId;
        }

        private static string GetPreferredUsernameFromIdToken(bool isAdfsAuthority, IdToken idToken)
        {
            // The preferred_username value cannot be null or empty in order to comply with the ADAL/MSAL Unified cache schema.
            // It will be set to "preferred_username not in id token"
            if (idToken == null)
            {
                return NullPreferredUsernameDisplayLabel;
            }

            if (string.IsNullOrWhiteSpace(idToken.PreferredUsername))
            {
                if (isAdfsAuthority)
                {
                    //The direct to ADFS scenario does not return preferred_username in the id token so it needs to be set to the UPN
                    return !string.IsNullOrEmpty(idToken.Upn)
                        ? idToken.Upn
                        : NullPreferredUsernameDisplayLabel;
                }
                return NullPreferredUsernameDisplayLabel;
            }

            return idToken.PreferredUsername;
        }

        /// <summary>
        /// IMPORTANT: this class is perf critical; any changes must be benchmarked using Microsoft.Identity.Test.Performace.
        /// More information about how to test and what data to look for is in https://aka.ms/msal-net-performance-testing.
        /// 
        /// Scenario: client_creds with default in-memory cache can get to ~500k tokens
        /// </summary>
        async Task<MsalAccessTokenCacheItem> ITokenCacheInternal.FindAccessTokenAsync(
            AuthenticationRequestParameters requestParams)
        {
            var logger = requestParams.RequestContext.Logger;
            // no authority passed
            if (requestParams.AuthorityInfo?.CanonicalAuthority == null)
            {
                logger.Warning("FindAccessToken: No authority provided. Skipping cache lookup. ");
                return null;
            }

            // take a snapshot of the access tokens to avoid problems where the underlying collection is changed,
            // as this method is NOT locked by the semaphore
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems = GetAllAccessTokensWithNoLocks(true).ToList();            

            tokenCacheItems = FilterByHomeAccountTenantOrAssertion(requestParams, tokenCacheItems);
            tokenCacheItems = FilterByTokenType(requestParams, tokenCacheItems);
            tokenCacheItems = FilterByScopes(requestParams, tokenCacheItems);
            tokenCacheItems = await FilterByEnvironmentAsync(requestParams, tokenCacheItems).ConfigureAwait(false);

            // perf: take a snapshot as calling Count(), Any() etc. on the IEnumerable evaluates it each time
            IReadOnlyList<MsalAccessTokenCacheItem> finalList = tokenCacheItems.ToList();

            CacheInfoTelemetry cacheInfoTelemetry = CacheInfoTelemetry.None;

            // no match
            if (finalList.Count == 0)
            {
                logger.Verbose("No tokens found for matching authority, client_id, user and scopes. ");
                return null;
            }

            MsalAccessTokenCacheItem msalAccessTokenCacheItem = GetSingleResult(requestParams, finalList);
            msalAccessTokenCacheItem = FilterByKeyId(msalAccessTokenCacheItem, requestParams);
            msalAccessTokenCacheItem = FilterByExpiry(msalAccessTokenCacheItem, requestParams);

            if (msalAccessTokenCacheItem == null)
            {
                cacheInfoTelemetry = CacheInfoTelemetry.Expired;
            }

            requestParams.RequestContext.ApiEvent.CacheInfo = (int)cacheInfoTelemetry;

            return msalAccessTokenCacheItem; 
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByScopes(
            AuthenticationRequestParameters requestParams,
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            var logger = requestParams.RequestContext.Logger;
            var requestScopes = requestParams.Scope.Where(s =>
                !OAuth2Value.ReservedScopes.Contains(s));

            tokenCacheItems = tokenCacheItems.FilterWithLogging(
                item => {
                    bool accepted = ScopeHelper.ScopeContains(item.ScopeSet, requestScopes);
                    
                    if (logger.IsLoggingEnabled(LogLevel.Verbose))
                    {
                        logger.Verbose($"Access token with scopes {string.Join(" ", item.ScopeSet)} " +
                            $"passes scope filter? {accepted} ");
                    }
                    return accepted;
                    },
                logger,
                "Filtering by scopes");

            return tokenCacheItems;
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByTokenType(AuthenticationRequestParameters requestParams, IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                            string.Equals(
                                item.TokenType ?? BearerAuthenticationScheme.BearerTokenType,
                                requestParams.AuthenticationScheme.AccessTokenType,
                                StringComparison.OrdinalIgnoreCase),
                            requestParams.RequestContext.Logger,
                            "Filtering by token type");
            return tokenCacheItems;
        }

        private static IEnumerable<MsalAccessTokenCacheItem> FilterByHomeAccountTenantOrAssertion(
            AuthenticationRequestParameters requestParams,
            IEnumerable<MsalAccessTokenCacheItem> tokenCacheItems)
        {
            string requestTenantId = requestParams.Authority.TenantId;
            bool filterByTenantId = true;

            if (requestParams.UserAssertion != null) // OBO
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                                !string.IsNullOrEmpty(item.UserAssertionHash) &&
                                item.UserAssertionHash.Equals(requestParams.UserAssertion.AssertionHash, StringComparison.OrdinalIgnoreCase),
                                requestParams.RequestContext.Logger,
                                "Filtering by user assertion id");

                // OBO calls FindAccessTokenAsync directly, but we are not able to resolve the authority 
                // unless the developer has configured a tenanted authority. If they have configured /common
                // then we cannot filter by tenant and will use whatever is in the cache.
                filterByTenantId =
                    !string.IsNullOrEmpty(requestTenantId) &&
                    !AadAuthority.IsCommonOrganizationsOrConsumersTenant(requestTenantId);
            }

            if (filterByTenantId)
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item =>
                    string.Equals(item.TenantId ?? string.Empty, requestTenantId ?? string.Empty, StringComparison.OrdinalIgnoreCase),
                    requestParams.RequestContext.Logger,
                    "Filtering by tenant id");
            }
            else
            {
                requestParams.RequestContext.Logger.Warning("Have not filtered by tenant ID. " +
                    "This can happen in OBO scenario where authority is /common or /organizations. " +
                    "Please use tenanted authority.");
            }

            // Only AcquireTokenSilent has an IAccount in the request that can be used for filtering
            if (requestParams.ApiId != TelemetryCore.Internal.Events.ApiEvent.ApiIds.AcquireTokenForClient &&
                requestParams.ApiId != TelemetryCore.Internal.Events.ApiEvent.ApiIds.AcquireTokenOnBehalfOf)
            {
                tokenCacheItems = tokenCacheItems.FilterWithLogging(item => item.HomeAccountId.Equals(
                                requestParams.Account.HomeAccountId?.Identifier, StringComparison.OrdinalIgnoreCase),
                                requestParams.RequestContext.Logger,
                                "Filtering by home account id");
            }

            return tokenCacheItems;
        }

        private MsalAccessTokenCacheItem FilterByExpiry(MsalAccessTokenCacheItem msalAccessTokenCacheItem, AuthenticationRequestParameters requestParams)
        {
            var logger = requestParams.RequestContext.Logger;
            if (msalAccessTokenCacheItem != null)
            {

                if (msalAccessTokenCacheItem.ExpiresOn > DateTime.UtcNow + AccessTokenExpirationBuffer)
                {
                    // due to https://github.com/AzureAD/microsoft-authentication-library-for-dotnet/issues/1806
                    if (msalAccessTokenCacheItem.ExpiresOn > DateTime.UtcNow + TimeSpan.FromDays(ExpirationTooLongInDays))
                    {
                        logger.Error(
                           "Access token expiration too large. This can be the result of a bug or corrupt cache. Token will be ignored as it is likely expired." +
                           GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                        return null;
                    }

                    if (logger.IsLoggingEnabled(LogLevel.Info))
                    {
                        logger.Info(
                            "Access token is not expired. Returning the found cache entry. " +
                            GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                    }

                    return msalAccessTokenCacheItem;
                }

                if (ServiceBundle.Config.IsExtendedTokenLifetimeEnabled &&
                    msalAccessTokenCacheItem.ExtendedExpiresOn > DateTime.UtcNow + AccessTokenExpirationBuffer)
                {
                    if (logger.IsLoggingEnabled(LogLevel.Info))
                    {
                        logger.Info(
                            "Access token is expired.  IsExtendedLifeTimeEnabled=TRUE and ExtendedExpiresOn is not exceeded.  Returning the found cache entry. " +
                            GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                    }

                    msalAccessTokenCacheItem.IsExtendedLifeTimeToken = true;
                    return msalAccessTokenCacheItem;
                }

                if (logger.IsLoggingEnabled(LogLevel.Info))
                {
                    logger.Info(
                        "Access token has expired or about to expire. " +
                        GetAccessTokenExpireLogMessageContent(msalAccessTokenCacheItem));
                }
            }

            return null;
        }

        private static MsalAccessTokenCacheItem GetSingleResult(
            AuthenticationRequestParameters requestParams,
            IReadOnlyList<MsalAccessTokenCacheItem> filteredItems)
        {
            // if only one cached token found
            if (filteredItems.Count == 1)
            {
                return filteredItems[0];
            }

            requestParams.RequestContext.Logger.Error("Multiple tokens found for matching authority, client_id, user and scopes. ");
            throw new MsalClientException(
                MsalError.MultipleTokensMatchedError,
                MsalErrorMessage.MultipleTokensMatched);
        }

        private async Task<IEnumerable<MsalAccessTokenCacheItem>> FilterByEnvironmentAsync(AuthenticationRequestParameters requestParams, IEnumerable<MsalAccessTokenCacheItem> filteredItems)
        {
            // at this point we need env aliases, try to get them without a discovery call
            var instanceMetadata = await ServiceBundle.InstanceDiscoveryManager.GetMetadataEntryTryAvoidNetworkAsync(
                                     requestParams.AuthorityInfo,
                                     filteredItems.Select(at => at.Environment),  // if all environments are known, a network call can be avoided
                                     requestParams.RequestContext)
                            .ConfigureAwait(false);

            // In case we're sharing the cache with an MSAL that does not implement env aliasing,
            // it's possible (but unlikely), that we have multiple ATs from the same alias family.
            // To overcome some of these use cases, try to filter just by preferred cache alias
            var filteredByPreferredAlias = filteredItems.FilterWithLogging(
                item => item.Environment.Equals(instanceMetadata.PreferredCache, StringComparison.OrdinalIgnoreCase),
                requestParams.RequestContext.Logger,
                $"Filtering by preferred environment {instanceMetadata.PreferredCache}");

            if (filteredByPreferredAlias.Any())
            {
                return filteredByPreferredAlias;
            }

            return filteredItems.FilterWithLogging(
                item => instanceMetadata.Aliases.ContainsOrdinalIgnoreCase(item.Environment),
                requestParams.RequestContext.Logger,
                $"Filtering by environment");
        }

        private MsalAccessTokenCacheItem FilterByKeyId(MsalAccessTokenCacheItem item, AuthenticationRequestParameters authenticationRequest)
        {
            if (item == null)
            {
                return null;
            }

            string requestKid = authenticationRequest.AuthenticationScheme.KeyId;
            if (string.IsNullOrEmpty(item.KeyId) && string.IsNullOrEmpty(requestKid))
            {
                authenticationRequest.RequestContext.Logger.Verbose("Bearer token found");
                return item;
            }

            if (string.Equals(item.KeyId, requestKid, StringComparison.OrdinalIgnoreCase))
            {
                authenticationRequest.RequestContext.Logger.Verbose("Keyed token found");
                return item;
            }

            authenticationRequest.RequestContext.Logger.Info(
                    string.Format(
                        CultureInfo.InvariantCulture,
                        "A token bound to the wrong key was found. Token key id: {0} Request key id: {1}",
                        item.KeyId,
{'fraction_non_alphanumeric': 0.05968988040311929, 'fraction_numerical': 0.0012303461253143715, 'mean_word_length': 1.6794977456731468, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 75, 'https://': 6, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6615957', 'n_tokens_mistral': 12440, 'n_tokens_neox': 11830, 'n_words': 2617}