Algorithm to compare OAuth2 Rich Authorization Requests

Question

Authorization Requests spec defines new authorization_details parameter. The authorization server have to somehow compare this parameter to decide whether client wants less, more or the same access.

My way to achieve this is to except two JSON arrays, but I feel my algorithm is not clear and not efficient.

My code looks as below:

public static Dictionary<string, JObject> ReadAuthorizationDetailsArray(this JArray jArray)
{
    return jArray
        .Where(p => p is JObject)
        .ToDictionary(k => ((JObject)k).Property("type")!.Value.ToString(), v => (JObject)v);
}

public static JArray ExceptAuthorizationDetailArrays(this JArray firstArray, JArray secondArray)
{
    Func<JValue, string> getJsonValueIdentifier = (JValue jValue)
        => $"{Regex.Replace(jValue.Path, "\\[\\d+\\]", string.Empty)}:{jValue.Value?.ToString()}";

    var firstAuthorizationDetails = firstArray.ReadAuthorizationDetailsArray();
    var secondAuthorizationDetails = secondArray.ReadAuthorizationDetailsArray();

    foreach (var firstAuthorizationDetail in firstAuthorizationDetails)
    {
        if (!secondAuthorizationDetails.ContainsKey(firstAuthorizationDetail.Key))
            continue;

        var secondAuthorizationDetailObject = secondAuthorizationDetails[firstAuthorizationDetail.Key];

        var firstAuthorizationDetailValuesIdentifiers = firstAuthorizationDetail.Value.Descendants()
            .Where(p => p is JValue)
            .ToDictionary(k => getJsonValueIdentifier((JValue)k), v => v);

        var secondAuthorizationDetailValuesIdentifiers = secondAuthorizationDetailObject.Descendants()
            .Where(p => p is JValue)
            .Select(p => getJsonValueIdentifier((JValue)p));

        var exceptedIdentifiers = firstAuthorizationDetailValuesIdentifiers.Keys.Except(secondAuthorizationDetailValuesIdentifiers);
        if (!exceptedIdentifiers.Any())
        {
            firstArray.Remove(firstAuthorizationDetail.Value);
            continue;
        }

        var toRemove = firstAuthorizationDetailValuesIdentifiers.ExceptBy(exceptedIdentifiers, k => k.Key).Where(p => p.Key != $".type:{p.Value}");
        foreach (var removable in toRemove.Select(p => p.Value))
        {
            if (removable.Parent is JProperty) removable.Parent.Remove();
            else removable.Remove();
        }

        var emptyDescendants = firstAuthorizationDetail.Value.Descendants().Where(p => (p is JObject || p is JArray) && (p is null || !p.Any())).ToList();
        foreach (var descendant in emptyDescendants)
        {
            if (descendant.Parent is JProperty prop)
            {
                if (prop.Value is null || ((prop.Value is JObject || prop.Value is JArray) && !prop.Value.Any())) descendant.Parent.Remove();
            }
            else descendant.Remove();
        }
    }

    return firstArray;
}

When firstArray looks as below:

var thirtyJson = @"[
   {
      ""type"": ""payment_initiation"",
      ""actions"": [
         ""initiate"",
         ""status"",
         ""cancel""
      ],
      ""locations"": [
         ""https://example.com/payments""
      ],
      ""instructedAmount"": {
         ""currency"": ""EUR"",
         ""amount"": 123.50
      },
      ""creditorName"": ""Merchant A"",
      ""creditorAccount"": {
         ""iban"": ""DE02100100109307118603""
      },
      ""remittanceInformationUnstructured"": ""Ref Number Merchant""
   },
   {
      ""type"": ""account_information"",
      ""actions"": [
         ""list_accounts"",
         ""read_balances"",
         ""read_transactions"",
         ""write_accounts""
      ],
      ""locations"": [
         ""https://example.com/accounts""
      ]
   }
]";

And the secondArray looks like it:

var fourtyJson = @"[
   {
      ""type"":""account_information"",
      ""actions"":[
         ""list_accounts"",
         ""read_balances"",
         ""read_transactions""
      ],
      ""locations"":[
         ""https://example.com/accounts""
      ]
   }
]";

The valid result is:

[
  {
    "type": "payment_initiation",
    "actions": [
      "initiate",
      "status",
      "cancel"
    ],
    "locations": [
      "https://example.com/payments"
    ],
    "instructedAmount": {
      "currency": "EUR",
      "amount": 123.5
    },
    "creditorName": "Merchant A",
    "creditorAccount": {
      "iban": "DE02100100109307118603"
    },
    "remittanceInformationUnstructured": "Ref Number Merchant"
  },
  {
    "type": "account_information",
    "actions": [
      "write_accounts"
    ]
  }
]

We can describe this operation like: result = firstArray - secondArray. So result is JSON that contains all firstArray items that are not contained in secondArray. What's more, type property is never removed (unless compared objects with the same type are the equals. Then we remove the entire object from firstArray.)

The regex, getting JSON descendants many times, and these nested loops... I feel it's as bad as possible. What shall I refactor in above code to make it very efficient and more readable?

Answer 1

The naming of the parameters in the original implementation is not very descriptive and should be clarified, I think it's requested and actual scopes?

I would suggest you perform a recursive comparison of the JSON tokens unless the object tree is very deep:

public static class AuthorizationDetailsUtil
{
    public static JArray ScopeDifferences(JArray requested, JArray actual)
    {
        var actualTypeMap = CreateTypeMap(actual);
        var result = new JArray();

        foreach (var requestType in requested.Values<JObject>())
        {
            var type = (string)requestType.Property("type");
            if (actualTypeMap.TryGetValue(type, out var actualType))
            {
                var diff = Differences(requestType, actualType);
                if (diff != null)
                {
                    diff.AddFirst(new JProperty("type", type));
                    result.Add(diff);
                }
            }
            else
            {
                result.Add(requestType);
            }
        }

        return result;
    }

    private static readonly StringComparer PropertyNameComparer = StringComparer.OrdinalIgnoreCase;
    private static Dictionary<string, JObject> CreateTypeMap(JArray array)
    {
        return array.Values<JObject>().ToDictionary(d => (string)d.Property("type"), PropertyNameComparer);
    }

    private static JToken Differences(JToken requested, JToken actual)
    {
        var diff = (requested, actual) switch
        {
            (JObject r, JObject a) => Differences(r, a),
            (JArray r, JArray a) => Differences(r, a),
            (JValue r, JValue a) => Differences(r, a),
            (JToken r, null) => r,
            (null, JToken a) => a,
            (null, null) => null,
            (_, _) => throw new InvalidDataException("Types do not match"),
        };

        return diff;
    }

    private static JObject Differences(JObject requested, JObject actual)
    {
        var actualPropertiesMap = actual.Properties().ToDictionary(p => p.Name, PropertyNameComparer);
        JObject result = null;
        foreach (var requestedProperty in requested.Properties())
        {
            if (actualPropertiesMap.Remove(requestedProperty.Name, out var actualProperty))
            {
                var diff = Differences(requestedProperty.Value, actualProperty.Value);
                if (diff != null)
                {
                    if (result == null)
                    {
                        result = new JObject();
                    }
                    result.Add(requestedProperty.Name, diff);
                }
            }
            else
            {
                result.Add(requestedProperty.Name, requestedProperty.Value);
            }
        }

        return result;
    }

    private static JValue Differences(JValue requested, JValue actual)
    {
        if (object.Equals(requested.Value, actual.Value))
        {
            return null;
        }
        return requested;
    }

    private static JArray Differences(JArray requested, JArray actual)
    {
        //This only works for JArrays of JValues not JObjects.
        var diff = requested.Except(actual).ToList();
        if (diff.Count > 0)
        {
            return new JArray(diff);
        }
        return null;
    }
}

This makes it simpler to tweak how tokens are compared.

var requestedDetails = JArray.Parse(@"[
   {
      ""type"": ""payment_initiation"",
      ""actions"": [
         ""initiate"",
         ""status"",
         ""cancel""
      ],
      ""locations"": [
         ""https://example.com/payments""
      ],
      ""instructedAmount"": {
         ""currency"": ""EUR"",
         ""amount"": 123.50
      },
      ""creditorName"": ""Merchant A"",
      ""creditorAccount"": {
         ""iban"": ""DE02100100109307118603""
      },
      ""remittanceInformationUnstructured"": ""Ref Number Merchant""
   },
   {
      ""type"": ""account_information"",
      ""actions"": [
         ""list_accounts"",
         ""read_balances"",
         ""read_transactions"",
         ""write_accounts""
      ],
      ""locations"": [
         ""https://example.com/accounts""
      ]
   }
]");

var actualDetails = JArray.Parse(@"[
   {
      ""type"":""account_information"",
      ""actions"":[
         ""list_accounts"",
         ""read_balances"",
         ""read_transactions""
      ],
      ""locations"":[
         ""https://example.com/accounts""
      ]
   }
]");
    
var expected = JArray.Parse(@"[
  {
    ""type"": ""payment_initiation"",
    ""actions"": [
      ""initiate"",
      ""status"",
      ""cancel""
    ],
    ""locations"": [
      ""https://example.com/payments""
    ],
    ""instructedAmount"": {
      ""currency"": ""EUR"",
      ""amount"": 123.5
    },
    ""creditorName"": ""Merchant A"",
    ""creditorAccount"": {
      ""iban"": ""DE02100100109307118603""
    },
    ""remittanceInformationUnstructured"": ""Ref Number Merchant""
  },
  {
    ""type"": ""account_information"",
    ""actions"": [
      ""write_accounts""
    ]
  }
]");

var diffs = AuthorizationDetailsUtils.ScopeDifferences(requestedDetails, actualDetails);

Debug.Assert(expected.ToString().Equals(diffs.ToString(), StringComparison.OrdinalIgnoreCase), "Failed Comparison");

Answer 2

I think the following thing can help on performance: differentiate things that needs to be changed from those which should remain intact.

According to my understanding you need to perform any kind of modification on first array's element if it is present in the second array. (Look up is based on type field)

var lhs = JArray.Parse(thirtyJson);
var rhs = JArray.Parse(fourtyJson);

var toBeModifiedObjectPairs = 
      from JObject lhsObj in lhs
      join JObject rhsObj in rhs on lhsObj["type"] equals rhsObj["type"]
      select (lhsObj, rhsObj);

The exact same concept can be applied to the JObject level.

foreach (var (lhsObj, rhsObj) in toBeModifiedObjectPairs)
{
    var toBeComparedProperties = 
            from JProperty lhsProp in lhsObj.AsJEnumerable().Where(p => ((JProperty)p).Name != "type")
            join JProperty rhsProp in rhsObj.AsJEnumerable().Where(p => ((JProperty)p).Name != "type")
            on rhsProp.Name equals rhsProp.Name
            select (lhsProp, rhsProp);
}