This article was originally published at: github.com/bigo-fronte… Welcome to follow and reprint.

Demand background

DMS DaemonSet (BigO K8S). One POD is deployed on each node and the impact is large. The business expects to be able to display a yamL file diff of the current modified configuration and the online configuration when published, with the following effect:

Implementation scheme

jsdiff + diff2html

jsdiff

Get text differences.

diff2html

Translate the differences into HTML. Diff2html provides two ways to display diff effects:

  1. parse+html

    Problem: Highlight syntax does not take effect.

  2. diff2html-ui:

    1. Support JSON, code highlighting.

    2. Support file and directory summary display/hiding.

    3. View files. (In side-by-side mode, the organization cannot be viewed.)

Diff2html Format type: side-by-side and line-by-line.

Implementation effect

All the samples in this paper are displayed with Diff2HTml-UI.

  1. Syntax highlighting is supported.

  2. Support to show/hide difference profiles.

  3. Support file anchor jump.

  4. Display the number of file differences.

  5. File folding is supported (the file can be used only in line-by-line mode).

  • code

  • Multiple files

The implementation code

The core reference

import "diff2html/bundles/css/diff2html.min.css";   
​   
import { createPatch } from "diff";   
import { html, parse } from "diff2html";   
import { Diff2HtmlUI } from "diff2html/lib/ui/js/diff2html-ui";   
​   
// createPatch(fileName, oldString, newString, oldHeader, newHeader, {context: 5}) compare differences
​   
Parse (patch) Retrieves the JSON representation of diff
​   
// HTML (parsePatch) to beautify diff
​   
// Use the Diff2HtmlUI object to generate diff UI, which supports more functions than HTML
Copy the code

The core code

  1. Supports plain text, JSON, and YAML diff.

  2. Supports multiple file list display.

  3. Support parse+ HTML and Diff2HTmL-UI to display diff.

// diffDataList compares file list data [{...diffDataItem}]
// diffDataItem : 
/ / {
PrevData: any(string, json), // Old data
// newData: any(string, json), // newData
// isYaml? : Boolean, // Whether yamL file
//   isJson?: boolean,            // 是否json
// fileName? : string, // file name
// oldHeader? : string, // Rename the old file name
// newHeader? : string // Rename a new file name
// },
/ / outputFormat diff format, the line - by - line | | side - by - side
// isUseUi Whether to use Diff2HtmlUI
// id Diff2HtmlUI Indicates the ID of the mounted HTML. In the case of multiple instances, each instance needs a unique ID to prevent page conflicts
// fileListToggle Diff2HtmlUI File directory profile whether to hide, true to display, false to hide

import React, { useEffect, useState } from "react";
import { createPatch } from "diff";
import { html, parse } from "diff2html";
import { Diff2HtmlUI } from "diff2html/lib/ui/js/diff2html-ui";
import yaml from 'js-yaml';
import "highlight.js/styles/googlecode.css";
import "diff2html/bundles/css/diff2html.min.css";

const DiffComponent = ({ diffDataList, outputFormat, isUseUi, id, fileListToggle }) = > {

  const [ diffData, setDiffData ] = useState("");

  useEffect(() = > {
    createDiffData(diffDataList);
  }, [ diffDataList ])

  const createDiffData = (fileList) = > {
    let diffJsonList = [];
    fileList.forEach(item= > {
      let { fileName, oldHeader, newHeader, prevData, newData, isJson, isYaml } = item;
      let oldString = prevData || "";
      let newString = newData || "";
      // Specific requirements processing
      if(isYaml){
        // Convert json to YAML format
        oldString = yaml.dump(prevData);
        newString = yaml.dump(newData);
      }else if(isJson){
        // Format json
        oldString = JSON.stringify(prevData, null.2);
        newString = JSON.stringify(newData, null.2);
      }
      let args = [ fileName || "", oldString, newString, oldHeader || "", newHeader || "", { context: 99999}];// Compare the differences
      constdiffStr = createPatch(... args);// The difference is jsonized
      const diffJson = parse(diffStr);
      diffJsonList.push(diffJson[0]);
    })
    if(isUseUi){
      / / use diff2html - UI
      const targetElement = document.getElementById(id);
      const configuration = { 
        drawFileList: true.matching: "lines".highlight: true, outputFormat,
      };
      const diff2htmlUi = new Diff2HtmlUI(targetElement, diffJsonList, configuration);
      diff2htmlUi.draw();		// Draw the page
      diff2htmlUi.highlightCode();	// Highlight data
      diff2htmlUi.fileListToggle(fileListToggle);	// Whether to collapse the profile
    }else{
      // Use HTML methods
      const diffHtml = html(diffJsonList, { 
        drawFileList: true.matching: "lines".showFiles: true, outputFormat }); setDiffData(diffHtml); }}return (
    isUseUi ? <div id={id || "code-diff-ui} "/ > : <div id="code-diff" dangerouslySetInnerHTML={{__html: diffData}} / >)}export default DiffComponent
Copy the code

Components use

// parse+html
<DiffComponent 
  diffDataList={fileDiffList}
  outputFormat={outputFormat}
/>

/ / use diff2html - UI
<DiffComponent 
  isUseUi={true} 
  id={"diff-ui-mult"}
  fileListToggle={true}
  diffDataList={fileDiffList}
  outputFormat={outputFormat}
/>
Copy the code

Jsdiff principle

abstract

The process of finding diff can be abstracted as graph search.

Take two strings, SRC =ABCABBA and DST =CBABAC, for example. From these two strings, we can construct the following graph with the SRC content on the horizontal axis and the DST content on the vertical axis.

So, every path in the diagram from the top left to the bottom right represents a diff. Moving to the right means “delete”, moving down means “add”, and a diagonal means “leave the original content unchanged”.

According to the route formed in the picture, we can choose a route to see its effect.

Now, “finding the diff” is abstracted to “finding the path of the graph.” So, what are the characteristics of the paths that correspond to “shortest intuitive” diff?

  • Shortest path length (diagonal does not count as length)

  • First right, then down (delete first, then add)

Myers algorithm

Myers algorithm is an algorithm that can produce the “shortest intuitive” DIff in most cases. The algorithm principle is as follows.

First, define parameters D and k, where D represents the length of the path and k represents the value of the current coordinate X-y. Define a concept of “optimal coordinate”, the optimal coordinate refers to the maximum x value under the condition that d and K are fixed. If x is large, it indicates that the number of moves to the right is large, which indicates that the deletion is preferred.

Let’s take the picture above. We start at the coordinates (0, 0), where d=0, k=0, and then incrementing d to compute the optimal coordinates for each value of k.

Because each step is either to the right (x + 1) or down (y + 1), the diagonal doesn’t affect the path length, so when d is 1, k can only take on two values, either 1 or -1.

When d=1 and k=1, the optimal coordinates are (1, 0).

When d=1 and k=-1, the optimal coordinates are (0, 1).

Because when d=1, k is either 1 or negative 1, and when d=2, that means we’re going to go one step further from d=1, and there are only three possible values for k, minus 2, 0, 2.

When d=2 and k=-2, the optimal coordinates are (2, 4).

When d=2 and k=0, the optimal coordinates are (2, 2).

When d=2 and k=2, the optimal coordinates are (3, 1).

And so on, until we find a value of D and k to reach the final target coordinates (7, 6).

In the figure below, the horizontal axis represents D, the vertical axis represents K, and the optimal coordinate is in the middle. It can be clearly seen from this figure that when D =5 and k=1, we reach the target coordinate (7, 6). Therefore, “The shortest intuitive” path is (0, 0) – > (1, 0) – > (3, 1) – > (5, 4) – > (7, 5) – > (7, 6).

Myers algorithm is a typical “dynamic programming” algorithm, that is, the solution of the parent problem comes down to the solution of the child problem. So if you want to know the optimal coordinates for k at d=5, you have to know the optimal coordinates for k at d=4, you have to solve for d=3, and so on.

Basic flow of Myers algorithm

  1. Iteration D, the value of d ranges from 0 to n+m, where n and M represent the length of source text and target text respectively (here we choose behavior units)

  2. Inside each d, iterate k, the value of k ranges from -d to D, with 2 steps, namely -d, -d + 2, -d + 2 + 2…

  3. Use a dictionary V, indexed by k values, to store the x values of the optimal coordinates

  4. I’m going to store the v dictionary for each d, and I’m going to need it for backtracking

  5. When we find a D and a K, we break out of the loop when we reach the target coordinates (n, m)

  6. Using the v dictionary stored above (one for each d), the path is derived backwards from the endpoint

conclusion

The DMS of this function is online, and the configuration delivery requirements of the BRPC service management platform are about to be introduced. In fact, this function is relatively easy, is the combination of JSDIff + Diff2HTML, but when looking for information, found that diff2HTML update speed is fast, the current online tutorials are basically using abandoned API; In addition, there are many internal systems in the company, and the diff requirement of configuration files is also common. Based on these two reasons, I write a summary, so that we can learn from each other.

If there are any mistakes, please correct them.

The relevant data

jsdiff

diff2html

Myers paper

How Git generates diff: Myers algorithm

Welcome everyone to leave a message to discuss, wish smooth work, happy life!

I’m bigO front. See you next time.