Ting 이네 Software 이야기

Just see following test.

Environment

• OS: 4.15.0-47-generic #50-Ubuntu SMP.
• CPU: Intel(R) Xeon(R) CPU E5-2697 v3 @ 2.60GHz
• NodeJs: 10.15.3

Normal

function f() {}

async function main() {
    let tm = -Date.now();
    for (let i = 0; i < 100000; i++) {
        f();
    }
    tm += Date.now();
    console.log(tm);
}
main()

$ node test.js
3

With operations

function f() {
    a = [];
    for (let i = 0; i < 30; i++) { a.push(i); }
}

async function main() {
    let tm = -Date.now();
    for (let i = 0; i < 100000; i++) {
        f();
    }
    tm += Date.now();
    console.log(tm);
}
main()

$ node test.js
27

With await

function f() {}

async function main() {
    let tm = -Date.now();
    for (let i = 0; i < 100000; i++) {
        await f();
    }
    tm += Date.now();
    console.log(tm);
}
main()

$ node test.js
19

With async/await

async function f() {}

async function main() {
    let tm = -Date.now();
    for (let i = 0; i < 100000; i++) {
        await f();
    }
    tm += Date.now();
    console.log(tm);
}
main()

$ node test.js
26

Introduction

3-way-merge(henceforth 3WM) is popularly used at SCM(Source code Configuration Management) tool. But, there is no standard way of implementation. And most of them is for text(source code). So, there are already lots of study regarding Text-3WM. But, for me, it's very difficult to find study regarding Json-3WM. Someone may think Json-3WM is subset of Text-3WM. And I think it can be one of possible algorithm of Json-3WM. But, is it enough? This article is for this topic.

Assumption

Array vs. Object

At Json, Array is considered as Object. At Javascript, typeof [] gives object. For example, [1, 2] can be represented as {0:1, 1:2}. In this article, Array is handled as one of primitive value, not an object - just like JSON-Merge-Patch(RFC 7386).

Merge

Way of merging two Json object is clearly defined at JSON-Merge-Patch(RFC 7386). Therefore this article is only focusing on 3-way-mergee.

3-Way Merge: Clear

In most common cases, it looks clear. For example,

Mergable

<base>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "g"
    }
}

<our>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "g",
        "h": "i"  # <=
    }
}


<their>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "z"  # <=
    }
}

<merged>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "z",  # <=
        "h": "i"   # <=
    }
}

Conflict

<base>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "g"
    }
}

<our>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "z"  # <=
    }
}


<their>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "y"  # <=
    }
}

3-Way Merge: Not clear

This is main topic of this discussion. Consider following example

<base>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "g"
    }
}

<our>
{
    "a": "b",
    "c": {
        "d": "e",
        "f": "z"  # <=
    }
}

And

<their>
{
    "a": "b"
              # <=
}

It seems conflict. Then, which property is conflicted? /c or /c/f?

Case: /c/f (Incorrect)

In this interpretation, merged result with Accept-Our option (resolve strategy for conflicted property) should be

<merged: accept-our>
{
    "a": "b",
    "c": {
        "f": "z"  # <=
    }
}

What is issue of above? In this case, there is no difference from below version of <their> object.

<their>
{
    "a": "b",
    "c": {}  # <=
}

In case of above version, everything looks clear. Definitely, /c/f is property conflicted. Then, Is it natural that two different changes gives same merged result? I think No. Therefore this is not correct interpretation of given example.

Case: /c

In this case, interpretation of changes are

• <their>: Deleting /c.
• <our>: Changing /c/f and /c(sub-property of /c is changed).
  So, /c is conflicted and merged result with Accept-Our option (resolve strategy for conflicted property) should be

  <merged: accept-our>(same with <our>)
  {
    "a": "b",
    "c": {
        "d": "e",
        "f": "z"
    }
  }

  Whole sub-object /c is resolved with /c of <our> object because of Accept-Our merge strategy.

Summary

This article describes private opinion related with 3-way-merge algorithm of Json object. There is NO correct answer. This is just one of suggestion.