<div id="app">
    <p>hello world</p>
    <Rate :value="4"></Rate>
</div>

function render(){
    return h('div',{id:"app"},children:[
        h('p',{},'hello world'),
        h(Rate,{value:4}),
    ])
}

const vnode = createVNode( (
    rootComponent as ConcreteComponent,
    rootProps
)
function _createVNode() {
    // 處理屬性和 class
    if (props) {
    ...
    }
    // 標(biāo)記vnode信息
    const shapeFlag = isString(type)
        ? ShapeFlags.ELEMENT
        : __FEATURE_SUSPENSE__ && isSuspense(type)
        ? ShapeFlags.SUSPENSE
        : isTeleport(type)
        ? ShapeFlags.TELEPORT
        : isObject(type)
        ? ShapeFlags.STATEFUL_COMPONENT
        : isFunction(type)
        ? ShapeFlags.FUNCTIONAL_COMPONENT
        : 0
     return createBaseVNode(
        type,
        props,
        children,
        patchFlag,
        dynamicProps,
        shapeFlag,
        isBlockNode,
        true
    )
}
function createBaseVNode(type,props,children,...){
    const vnode = {
    type,
    props,
    key: props && normalizeKey(props),
    ref: props && normalizeRef(props),
    children,
    shapeFlag,
    patchFlag,
    dynamicProps,
    ...
} as VNode
// 標(biāo)準(zhǔn)化子節(jié)點(diǎn)
if (needFullChildrenNormalization) {
    normalizeChildren(vnode, children)
} else if (children) {
    vnode.shapeFlag |= isString(children)
        ? ShapeFlags.TEXT_CHILDREN
        : ShapeFlags.ARRAY_CHILDREN
    }
    return vnode
}componentUpdateFn

const componentUpdateFn = ()=>{
    if (!instance.isMounted) {
    //首次渲染
    instance,
    parentSuspense,
    isSVG
    )
    。。。
}else{
    let { next, bu, u, parent, vnode } = instance
    if (next) {
        next.el = vnode.el
        updateComponentPreRender(instance, next, optimized)
    } else {
        next = vnode
    }
    const nextTree = renderComponentRoot(instance)
    patch(
        prevTree,
        nextTree,
        // parent may have changed if it's in a teleport
        hostParentNode(prevTree.el!)!,
        // anchor may have changed if it's in a fragment
        getNextHostNode(prevTree),
        instance,
        parentSuspense,
        isSVG
        )
    }
}
// 注冊effect函數(shù)
const effect = new ReactiveEffect(
    componentUpdateFn,
    () => queueJob(instance.update),
    instance.scope // track it in component's effect scope
)
const update = (instance.update = effect.run.bind(effect) as S chedulerJo
update()
const updateComponentPreRender = (
    instance: ComponentInternalInstance,
    nextVNode: VNode,
    optimized: boolean
) => {
nextVNode.component = instance
    const prevProps = instance.vnode.props
    instance.vnode = nextVNode
    instance.next = null
    updateProps(instance, nextVNode.props, prevProps, optimized)
    updateSlots(instance, nextVNode.children, optimized)
    pauseTracking()
    // props update may have triggered pre-flush watchers.
    // flush them before the render update.
    flushPreFlushCbs(undefined, instance.update)
    resetTracking()
}

function path(n1, n2, container){
    const { type, shapeFlag } = n2
        switch (type) {
            case Text:
            processText(n1, n2, container)
            break
            // 還有注釋，fragment之類的可以處理，這里忽略
            default:
            // 通過shapeFlag判斷類型
            if (shapeFlag & ShapeFlags.ELEMENT) {
                processElement(n1, n2, container, anchor)
            } else if (shapeFlag & ShapeFlags.STATEFUL_COMPONENT) {
                processComponent(n1, n2, container)
            }
       }
}
function processComponent(n1, n2, container) {
    // 老規(guī)矩，沒有n1就是mount
    if (!n1) {
        // 初始化 component
        mountComponent(n2, container)
    } else {
        updateComponent(n1, n2, container)
    }
}

const instance = (n2.component = n1.component)!
if (shouldUpdateComponent(n1, n2, optimized)) {
    // normal update
    instance.next = n2
    // in case the child component is also queued, remove it to avoid
    // double updating the same child component in the same flush.
    invalidateJob(instance.update)
    // instance.update is the reactive effect.
    instance.update()
} else {
    // no update needed. just copy over properties
    n2.component = n1.component
    n2.el = n1.el
    instance.vnode = n2
}

const patchElement = (
    n1: VNode,
    n2: VNode,
    parentComponent: ComponentInternalInstance | null,
    parentSuspense: SuspenseBoundary | null,
    isSVG: boolean,
    slotScopeIds: string[] | null,
    optimized: boolean
) => {
    const el = (n2.el = n1.el!)
    let { patchFlag, dynamicChildren, dirs } = n2
    patchFlag |= n1.patchFlag & PatchFlags.FULL_PROPS
    const oldProps = n1.props || EMPTY_OBJ
    const newProps = n2.props || EMPTY_OBJ
    // full diff
    patchChildren(
        n1,
        n2,
        el,
        null,
        parentComponent,
        parentSuspense,
        areChildrenSVG,
        slotScopeIds,
        false
    )
    if (patchFlag > 0) {
        if (patchFlag & PatchFlags.FULL_PROPS) {
            patchProps(
                el,
                n2,
                oldProps,
                newProps,
                parentComponent,
                parentSuspense,
                isSVG
            )
        } else {
            // class是動態(tài)的
            if (patchFlag & PatchFlags.CLASS) {
                if (oldProps.class !== newProps.class) {
                    hostPatchProp(el, 'class', null, newProps.class, isSVG)
                }
            }
            // style樣式是動態(tài)的
            if (patchFlag & PatchFlags.STYLE) {
                hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
            }
            // 屬性需要diff
            if (patchFlag & PatchFlags.PROPS) {
                //
                const propsToUpdate = n2.dynamicProps!
                for (let i = 0; i < propsToUpdate.length; i++) {
                    const key = propsToUpdate[i]
                    const prev = oldProps[key]
                    const next = newProps[key]
                    // #1471 force patch value
                    if (next !== prev || key === 'value') {
                        hostPatchProp(
                            el,
                            key,
                            prev,
                            next,
                            isSVG,
                            n1.children as VNode[],
                            parentComponent,
                            parentSuspense,
                            unmountChildren
                        )
                    }
                }
            }
        }
        //文本是動態(tài)的
        if (patchFlag & PatchFlags.TEXT) {
            if (n1.children !== n2.children) {
                hostSetElementText(el, n2.children as string)
            }
        }
    }
}

const patchChildren: PatchChildrenFn = (
    n1,
    n2,
    container,
    anchor,
    parentComponent,
    parentSuspense,
    isSVG,
    slotScopeIds,
    optimized = false
) => {
    const c1 = n1 && n1.children
    const prevShapeFlag = n1 ? n1.shapeFlag : 0
    const c2 = n2.children
    const { patchFlag, shapeFlag } = n2
    // fast path
    if (patchFlag > 0) {
        if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
            // this could be either fully-keyed or mixed (some keyed some not)
            // presence of patchFlag means children are guaranteed to be arrays
            patchKeyedChildren(
                c1 as VNode[],
                c2 as VNodeArrayChildren,
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG,
                slotScopeIds,
                optimized
            )
            return
        } else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
            // unkeyed
            patchUnkeyedChildren(
                c1 as VNode[],
                c2 as VNodeArrayChildren,
                container,
                anchor,
                parentComponent,
                parentSuspense,
                isSVG,
                slotScopeIds,
                optimized
            )
            return
        }
    }
    // children has 3 possibilities: text, array or no children.
    if (shapeFlag & ShapeFlags.TEXT_CHILDREN) {
        // text children fast path
        if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
            unmountChildren(c1 as VNode[], parentComponent, parentSuspense)
        }
        if (c2 !== c1) {
            hostSetElementText(container, c2 as string)
        }
    } else {
        if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
            // prev children was array
            if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
                // two arrays, cannot assume anything, do full diff
                patchKeyedChildren(
                    c1 as VNode[],
                    c2 as VNodeArrayChildren,
                    container,
                    anchor,
                    parentComponent,
                    parentSuspense,
                    isSVG,
                    slotScopeIds,
                    optimized
                )
            } else {
                // no new children, just unmount old
                unmountChildren(c1 as VNode[], parentComponent, parentSuspense, true
    }
        } else {
            // prev children was text OR null
            // new children is array OR null
            if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
                hostSetElementText(container, '')
            }
            // mount new if array
            if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
                mountChildren(
                    c2 as VNodeArrayChildren,
                    container,
                    anchor,
                    parentComponent,
                    parentSuspense,
                    isSVG,
                    slotScopeIds,
                    optimized
                )
            }
        }
    }
}

// class
// this flag is matched when the element has dynamic class bindings.
if (patchFlag & PatchFlags.CLASS) {
    if (oldProps.class !== newProps.class) {
        hostPatchProp(el, 'class', null, newProps.class, isSVG)
    }
}
// style
// this flag is matched when the element has dynamic style bindings
if (patchFlag & PatchFlags.STYLE) {
    hostPatchProp(el, 'style', oldProps.style, newProps.style, isSVG)
}
if (shapeFlag & ShapeFlags.ELEMENT) {
    processElement(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
    )
} else if (shapeFlag & ShapeFlags.COMPONENT) {
    processComponent(
        n1,
        n2,
        container,
        anchor,
        parentComponent,
        parentSuspense,
        isSVG,
        slotScopeIds,
        optimized
    )
}

(13).toString(2) // 1101
0 & 0 // 0
0 & 1 // 0
1 & 0 // 0
1 & 1 // 1
0 | 0 // 0
0 | 1 // 1
1 | 0 // 1
1 | 1 // 1
1 << 2 // 1左移動兩位，就是100 就是1*2平方 = 4

var isPowerOfTwo = function (n) {
    if (n === 1) return true
    while (n > 2) {
        n = n / 2
        if (n % 2 !== 0) return false
    }
    return n === 2
};

16
10000
16-1 = 15
01111
16&15 == 0
var isPowerOfTwo = function(n) {
    return n>0 && (n & (n - 1)) === 0
};

const PatchFlags = {
    TEXT:1, // 0001
    CLASS: 1<<1, // 0010
    STYLE:1<<2, // 0100
    PROPS:1<<3 // 1000
}
const flag1 = PatchFlags.TEXT | PatchFlags.STYLE // 0101
// 權(quán)限校驗(yàn)
flag1 & PatchFlags.TEXT // 有權(quán)限，結(jié)果大于1
flag1 & PatchFlags.CLASS //沒有權(quán)限 是0

/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = function (nums) {
    let n = nums.length;
    if (n == 0) {
        return 0;
    }
    let dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp)
}

/**
* @param {number[]} nums
* @return {number}
*/
const lengthOfLIS = function (nums) {
    let len = nums.length
    if (len <= 1) {
        return len
    }
    let arr = [nums[0]]
    for (let i = 0; i < len; i++) {
        // nums[i] 大于 arr 尾元素時(shí)，直接追加到后面，遞增序列長度+1
        if (nums[i] > arr[arr.length - 1]) {
            arr.push(nums[i])
        } else {
            // 否則，查找遞增子序列中第一個(gè)大于numsp[i]的元素 替換它
            // 遞增序列，可以使用二分查找
            let left = 0
            let right = arr.length - 1
            while (left < right) {
                let mid = (left + right) >> 1
                if (arr[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            arr[left] = nums[i]
        }
    }
    return arr.length
};

// https://en.wikipedia.org/wiki/Longest_increasing_subsequence
function getSequence(arr: number[]): number[] {
    const p = arr.slice() //賦值一份arr
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            j = result[result.length - 1]
            if (arr[j] < arrI) {
                p[i] = j // 存儲在result最后一個(gè)索引的值
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            // 二分查找，查找比arrI小的節(jié)點(diǎn)，更新result的值
            while (u < v) {
                c = (u + v) >> 1
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1]
                }
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    // 查找數(shù)組p 找到最終的索引
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}

for (i = toBePatched - 1; i >= 0; i--) {
    const nextIndex = s2 + i
    const nextChild = c2[nextIndex] as VNode
    const anchor =
        nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchor
    if (newIndexToOldIndexMap[i] === 0) {
        // mount new
        patch(
            null,
            nextChild,
            container,
            anchor,
            parentComponent,
            parentSuspense,
            isSVG,
            slotScopeIds,
            optimized
        )
    } else if (moved) {
        // move if:
        // There is no stable subsequence (e.g. a reverse)
        // OR current node is not among the stable sequence
        if (j < 0 || i !== increasingNewIndexSequence[j]) {
            move(nextChild, container, anchor, MoveType.REORDER)
        } else {
            j--
        }
    }
}