Typescript逆变与协变

刚接触Typescript那会儿有总结过不同类型之间相互赋值的情况:https://www.ccc5.cc/2702.html ,直到最近自己翻官方文档才知道有个更通俗的概念:逆变与协变。中文教程参考这个

假如有三个类有如下关系:

class A{
    a='a'
}

class B extends A{
    b='b'
}

class C extends B{
    c='c'
}

有如下函数:

function test(callback: (arg: B) => B) {
    // ...
}

那么仅有如下类型的函数可以赋值给test函数:

B => B // 这个毋容置疑
A => B // 参数的逆变, 因为test内部会按照符合B类型的方式传参,而B类型赋值给A类型是安全的
B => C // 返回值的协变,因为test内部对于callback的返回值会按照B类型使用,返回B的子类C对于内部使用也是安全的
A => C

Typescript中如何切掉函数参数表的最后一个参数

实现了个Prepend,将指定类型添加到元组类型的最前面:

type Prepend<Tuple extends any[], Addend> = ((_0: Addend, ..._1: Tuple) => any) extends ((..._: infer Result) => any) ? Result : never

然后利用类型递归得到Reverse

type Reverse<Tuple extends any[], Prefix extends any[] = []> = {
    0: Prefix
    1: ((..._: Tuple) => any) extends ((_0: infer First, ..._1: infer Next) => any)
        ? Reverse<Next, Prepend<Prefix, First>>
        : never
}[Tuple extends [any, ...any[]] ? 1 : 0]

停止递归的条件非常巧妙[Tuple extends [any, ...any[]] ? 1 : 0]:

type A<T extends any[]> = T extends [any, ...any[]] ? 'extends' : 'notExtends';
type B = A<[]> // 'notExtens'
type C = A<[string]> // 'extends'

出处: https://zhuanlan.zhihu.com/p/147248333

Y组合子推导(ES6版)

网上以“Y组合子”为关键字搜,结果其实挺多的,这里只是以我个人的理解再推一遍。

在日常开发中,Y组合子除了可以实现匿名递归以外好像也没有其他用,不过推导的过程倒是挺有意思,这里记录下。

另外,对相关问题感兴趣的可以看看《康托尔、哥德尔、图灵——永恒的金色对角线》这篇有意思的文章。

推导前的几个共识:

  1. 如何让下例函数体中不出现console.log
const log = info => console.log(info)
//  升高一阶然后立即执行降一阶
const log =  (fn => info => fn(info))(console.log)
  1. 如何惰性求值?
const fn = cb => {
    // cb 永远不会执行
    if(false) cb("Hello World!")
}
const genCb = msg1 => {
    console.log("可能是个耗时的任务..")
    return msg2 => console.log(`${msg1} ${msg2}`) 
}
// 下例中,尽管fn中的cb永远不会被调用,但genCb还是被执行了
fn(genCb('Hello'))
// 在不改变 fn 与 genCb 的情况下,如何让genCb延迟计算呢?
// 可以试试这个方法:
// 原理是对fn的参数(需是函数)升高一阶,然后在其被执行时自调用一次再执行原来的逻辑
fn((...arg) => genCb('Hello')(...arg))

下面开始推导,以阶乘为例:

const F = x => x ? x * F(x-1) : 1

根据共识1,我们将依赖的F提前出来:

// 这里注意,提取F为参数f后,里面的F(x-1)调用也要改为递归形式f(f,x-1)
const F = (f, x) => x ? x * f(f, x-1) : 1
 // 试下效果
// F(F, 5) // 120

柯里化为单参形式

// f(f, x-1)也要随之变为f(f)(x-1)
const F = f => x => x ? x * f(f)(x-1) : 1
// 再验算下
// F(F)(5) // 120

对于F(F),根据共识1用高阶函数来表示就是:

(f => f(f))(F)

代入前面推导出的F,我们现在得到:

(f => f(f))(f => x => x ? x * f(f)(x-1) : 1)

为了看起来不那么闪眼睛,后面将(f => f(f))A表示:

A(f => x => x ? x * f(f)(x-1) : 1)

接下来想办法从上面的式子中提取出原阶乘函数x => x ? x * f(x-1) : 1,使得其他部分一般化。对比发现,差别在于f(f)(x-1).

根据共识1,我们将f(f)提出去,作为参数传入,得到:

A(f => (g => x => x ? x * g(x-1) : 1)(f(f)))

这里有个问题,最后的f(f)作为参数会被立即求值而没经过条件判断,形成了无限递归,这里按共识2处理一下:

A(f => (g => x => x ? x * g(x-1) : 1)(n => f(f)(n)))

我们将g => x => x ? x * g(x-1) : 1部分用Fn来表示:

A(f => Fn(n => f(f)(n)))

紧接着将Fn 依据共识1往外拧,作为参数传入:

(g => A(f => g(n => f(f)(n))))(Fn)

现在将A所代表的(f => f(f))代回原函数体,得到:

(g => (f => f(f))(f => g(n => f(f)(n))))(Fn)

Y组合子就是前面这部分啦:

const Y = g => (f => f(f))(f => g(n => f(f)(n)))

验算下:

// 阶乘
Y(fac => n => n ? n * fac(n - 1) : 1)(5) // 120
// 斐波拉契
Y(fib => n => n >1 ? fib(n - 2) + fib(n - 1) : 1)(5) // 8

是不是有些绕,但还是蛮有趣的?

哎, 老乡别走呀,不喜欢Y组合子,这里有Z组合子了解下?另外,B、C、K、I、S..也可以看看

AC68U上配置Clash透明Proxy记录

家里路由器是华硕AC68U,已经刷了Merlin,但是里面集成的koolshare软件市场的科学Proxy工具实在难用,测速慢、无法自动切换、手动切换一次需要不下30s。Clash的Auto-UrlTest实在是香但koolshare一直没给支持,后面发现社区出了Clash透明Proxy的教程,就跟着一步步实践成功了,这里记录一下。

文件准备

  1. clash下载,在这里 下载对应版本的clash,解压得到二进制文件并重命名为clash。这里我踩到坑了,明明通过uname -a查看到AC68U的cpu是armv7,但对应的二进制死活无法运行,后面搜了一堆相关问题,有人提到了该型号可以使用armv5的版本,试了下,成功跑起来了,不清楚是不是编译的问题。

  2. ip数据库:Country.mmdb,虽然clash启动后会自动下载,但由于下载速度比较慢,建议自行准备,下载该文件,解压得到的文件改名为Country.mmdb

  3. 规则文件可以使用这个模板,加入自己的Proxy配置。由于要做透明Proxy,基本必要的选项如下:

# 透明Proxy端口号,iptables配置时会用到
redir-port: 9280

# 允许局域网的连接
allow-lan: true

# clash 的 RESTful API,用于clash-dashboard连接
external-controller: 0.0.0.0:9090

# RESTful API 的口令 (可选),当允许局域网调用RESTful API时,建议设置secret
secret: "xxxxxxxxxx"

dns:
  enable: true
  listen: 0.0.0.0:55  # 53被DNSmasq占用了,iptables配置会将53转到55
  enhanced-mode: redir-host # 或 fake-ip
  nameserver:
    - 1.2.4.8
    - 114.114.114.114
    - 223.5.5.5
    - tls://13800000000.rubyfish.cn:853
  fallback: # 与 nameserver 内的服务器列表同时发起请求,当规则符合 GEOIP 在 CN 以外时,fallback 列表内的域名服务器生效。
    - tls://13800000000.rubyfish.cn:853
    - tls://1.0.0.1:853
    - tls://dns.google:853
# 1. clash DNS 请求逻辑:
#   (1) 当访问一个域名时, nameserver 与 fallback 列表内的所有服务器并发请求,得到域名对应的 IP 地址。
#   (2) clash 将选取 nameserver 列表内,解析最快的结果。
#   (3) 若解析结果中,IP 地址属于 国外,那么 clash 将选择 fallback 列表内,解析最快的结果。
#
#   因此,我在 nameserver 和 fallback 内都放置了无污染、解析速度较快的国内 DNS 服务器,以达到最快的解析速度。
#   但是 fallback 列表内服务器会用在解析境外网站,为了结果绝对无污染,我仅保留了支持 DoT/DoH 的两个服务器。
# 
# 2. clash DNS 配置注意事项:
#   (1) 如果您为了确保 DNS 解析结果无污染,请仅保留列表内以 tls:// 或 https:// 开头的 DNS 服务器,但是通常对于国内域名没有必要。
#   (2) 如果您不在乎可能解析到污染的结果,更加追求速度。请将 nameserver 列表的服务器插入至 fallback 列表内,并移除重复项。
# 
# 3. 关于 DNS over HTTPS (DoH) 和 DNS over TLS (DoT) 的选择:
#   对于两项技术双方各执一词,而且会无休止的争论,各有利弊。各位请根据具体需求自行选择,但是配置文件内默认启用 DoT,因为目前国内没有封锁或管制。
#   DoH: 以 https:// 开头的 DNS 服务器。拥有更好的伪装性,且几乎不可能被运营商或网络管理封锁,但查询效率和安全性可能略低。
#   DoT: 以 tls:// 开头的 DNS 服务器。拥有更高的安全性和查询效率,但端口有可能被管制或封锁。
#   若要了解更多关于 DoH/DoT 相关技术,请自行查阅规范文档。

三个文件齐活:clash,config.yaml,Country.mmdb

路由器设置

  1. 在路由器管理页面中开启 ssh

  2. 上传上述仨文件,由于路由器是精简的linux系统,所以不集成包管理工具,无法安装lrzsz,得通过scp完成上传:

scp -r ~/clash admin@192.168.1.1:~/clash
  1. 给clash增加执行权限
chmod +x clash
  1. 尝试启动,看看是否有报错
./clash -d . 
  1. iptables 配置
    > iptables 配置还要学习,这里综合了几份别人的配置,不清楚有没有冗余或错误,实验来看,能正常访问网站,国内的请求好像有些慢,但确定没走代理。
# ssh 的22端口
iptables -t nat -A PREROUTING -p tcp --dport 22 -j ACCEPT

# 创建链
iptables -t nat -N Clash

# 保留地址、私有地址、回环地址 不走代理
iptables -t nat -A Clash -d 0.0.0.0/8 -j RETURN
iptables -t nat -A Clash -d 10.0.0.0/8 -j RETURN
iptables -t nat -A Clash -d 127.0.0.0/8 -j RETURN
iptables -t nat -A Clash -d 169.254.0.0/16 -j RETURN
iptables -t nat -A Clash -d 172.16.0.0/12 -j RETURN
iptables -t nat -A Clash -d 192.168.0.0/16 -j RETURN
iptables -t nat -A Clash -d 224.0.0.0/4 -j RETURN
iptables -t nat -A Clash -d 240.0.0.0/4 -j RETURN

# 9280 是clash的redir端口
iptables -t nat -A Clash -p tcp -j REDIRECT --to-ports 9280
iptables -t nat -A PREROUTING -p tcp -j Clash
# 53端口到55
iptables -t nat -A PREROUTING -p udp -m udp --dport 53 -j DNAT --to-destination 192.168.1.1:55

6 . 启动

./clash -d . &
# 或者 
nohup ./clash -d .

clash自启动或iptables配置持久化什么的,暂时就没搞了,这个也只是暂时的方案,后面整个软路由,刷lede吧,折腾没个头了。

获取对象key集合的一些姿势

有原始对象:

const obj = {
    a: 1,
    [Symbol('b')]: 2
}

再加工一下:

Object.defineProperty(obj,'c',{
    value: 3,
    enumerable: false
})

Object.prototype.d = 4

姿势1

const keys = []
for (let key in obj){
    keys.push(key)
}
console.log(keys) // ["a", "d", "e"]

key特点:自身及原型链上可枚举、非Symbol的key

姿势2

console.log(Object.keys(obj))  // ["a"]

key特点:自身可枚举、非Symbol 的key

姿势3

console.log(Object.getOwnPropertyNames(obj)) // ["a", "c"]

key特点:自身非Symbol的key

姿势4

console.log(Object.getOwnPropertySymbols(obj)) // [Symbol(b)]

key特点:自身的Symbol key

姿势5

console.log(Reflect.ownKeys(obj)) // ["a", "c", Symbol(b)]

key特点:姿势4 + 姿势5

一个题考察对Promise的掌握情况

近半年面试了很多的人,其中不乏高级前端开发,而对Promise这个现代前端异步基础掌握得实在是惨不忍睹,除了烂大街的考察事件循环中Promise执行顺序的问题,以下这个题也是一个很好的考察点,问,以下代码输出什么?

Promise.resolve(x).then((y) => console.log(x === y))

如果你脱口而出truefalse,那显然是欠考虑的。

而如果对Promise的发展稍有研究,其实就会发现这是考察Promise Resolution Procedure,根据Promise/A+中的描述,x应当分如下情况考虑:

  1. xPromise对象
    1.1 若xResolved状态的Promise,则yx的value,输出false
    1.2 若xRejected状态的Promise,则不会进入上面的回调,什么也不会输出
    1.3 若xPendding状态的Promise,则等待x状态发生变化,再走1.11.2的决议

  2. x是函数或对象, 取 then = x.then
    2.1 若上述过程抛出异常,则不会进入y所在的回调函数,什么也不会输出
    2.2 若then 不是一个函数,则决议值为x,则输出true
    2.3 若then为函数,则调用该函数,传入resolvePromiserejectPromise两个函数
    2.3.1 若rejectPromise被调用,则不会进入y所在回调,什么也不会输出
    2.3.2 若resolvePromise被调用,则走决议流程1
    2.3.3 若在then内调用resolvePromise之前发生异常,则不会进入y所在回调,什么也不会输出

  3. x非上述其他情况,则决议为x,即输出true(其实还要考虑NaN的情况😄)

TypeScript类型兼容

先看代码:

let x = { a: 1 };
let y = { a: 1, b: 2 };
x = y; // OK
y = x; // Error

let xx = (a: number) => 0;
let yy = (a: number, b: number) => 0;

xx = yy; // Error
yy = xx; // OK

一开始看文档我很疑惑: 为什么对象允许携带额外属性赋值,而不允许缺少属性,而函数赋值则反之

结合实际使用场景我们很快就能发现这么做的好处,先讲函数,以Array.prototype.map为例,其回调函数的签名为:

 (value: any, index: number, array: any[]) => {}

而很多场景下,我们只需要用到回调函数的第一个参数,所以我们更期望是这样来调用:

[].map((value: any)=>{})

而不是每次都要带上多余的index与array参数。

更准确来讲,我们作为函数参数使用方,选择性使用传入的参数是安全的,所以函数赋值允许忽略额外参数。

而对象则不一样,我们作为对象提供方,赋值给其他类型,被赋值的类型可能在任何场合被我们不可控的计算过程所使用,如果缺少了必要的属性可能会出现不安全的取值。

记一次anti anti debug

去年在微博上看到某前端大佬提供的一种检测用户是否打开控制台的方式,后面自己也去探索了一种方式,同时也发现在StackOverflow上有关于这个话题的讨论。不过这些方式后面都失效了。

今天偶然打开了一个视频网站,好奇按了下F12,发现浏览器彻底卡死了,Chrome自带的控制台都无法被打开了,心中瞬间冒出两个疑点:
1. 他是通过什么新的方式知道我打开了控制台
2. 他是通过什么方式让我的浏览器挂掉的,chrome不是多进程的吗?我们代码里面出现死循环都只是这个标签死掉,完全可以打开Chrome的进程工具结束掉这个标签的进程

在不停重启浏览器,再打开这个网站开启控制台的过程中发现了问题出在地址栏,一旦我打开控制台,地址栏便由a.com变成了a.com/0123456789101112....然后浏览器就挂掉了。

那第二个疑惑解除了:原来Chrome的网址不停增长会导致浏览器主进程挂掉。

不刷新而改变了地址栏,那应该是用了history.pushState

先实验一把,打开浏览器输入网址,不着急打开控制台,直接在地址栏输入:javascript:history.pushState = function(){}回车,以覆盖pushState实现,然后打开控制台,果然没有再卡死。

然后在其引入的js代码中搜pushState关键字,找到关键代码:

eval(function(e, t, n, r, o, i) {
        if (o = function(e) {
            return e.toString(20)
        }
        ,
        !"".replace(/^/, String)) {
            for (; n--; )
                i[o(n)] = r[n] || o(n);
            r = [function(e) {
                return i[e]
            }
            ],
            o = function() {
                return "\\w+"
            }
            ,
            n = 1
        }
        for (; n--; )
            r[n] && (e = e.replace(new RegExp("\\b" + o(n) + "\\b","g"), r[n]));
        return e
    }("1 2=c.3('8');4.b(2,'5',{6:7(){1 a=\"\";9(1 i=0;i<d;i++){a=a+i.e();f.g(0,0,a)}}});h.j(2);", 0, 20, " var x createElement Object id get function div for  defineProperty document 1000000 toString history pushState console  log".split(" "), 0, {}))

改eval为console.log,我们即可得到源码:

var x = document.createElement('div');
Object.defineProperty(x, 'id', {
  get: function() {
    var a = "";
    for (var i = 0; i < 1000000; i++) {
      a = a + i.toString();
      history.pushState(0, 0, a)
    }
  }
});
console.log(x);

看来检查控制台打开的原理还和原来失效的new Image差不多,控制台打开后,会自动触发一些通过console输出的标签的getter,然后在getter中就可以为所欲为了。

至此两点疑虑解开。

不过,他都这么做了,完全可以防得更彻底:

// 页面一加载就先备份
var p = history.pushState.bind(history)
// 检测到控制台被打开再做地址栏填充
 var a = "";
for (var i = 0; i < 1000000; i++) {
    a = a + i.toString();
    p(0, 0, a)
}

这样,我最开始通过地址栏直接覆盖原生API验证想法的路子就行不通了。

不过,这还是太小儿科了,太简单粗暴的告知调试者:老子知道你在调试我的网页了,我现在要原地爆炸。

而猥琐流的做法应该是:发现后偷偷打下标记,然后埋雷,在一些本来应该走a分支的地方走到b分支,一些关键的中间数据也故意做处理,时不时来个大的循环卡几秒钟….

当然,这些方式都不是我创的,参考EtherDream大佬的前端加密与混淆 ,当时看完一阵感慨:原来反调试的套路原来这么多。

一种探测你近期是否访问过指定网站的方式

html的a标签有一个特性,当用户访问过其href指向的链接后,在任意其他网站出现一个a标签,链接也是一样的话,显示的标签内的内容颜色会跟默认的颜色不一样。当然,开发者也可以通过css的伪类选择器指定其为别的颜色:

a:visited {color: #00FF00}

那么,我们是不是可以在自己的网站插入一堆的隐藏a标签,诱导某用户访问,然后使用js去获取各个a标签颜色的值就能知道该用户是否访问过对应的网站呢?

实际上,在过去几年前,确实是可以的,但后面由于该特性泄露用户隐私而被浏览器给处理了,任何时候通过window.getComputedStyle(someATage).color拿到的值都是与用户访问前一样。那么我们还有没有方式可以达到类似的效果呢?

最近研究http缓存的时候,突然想到,用户既然访问过某网站,而某网站又配置了静态资源缓存的话,那么我们是不是可以通过判断用户加载指定资源的时长来大致确定用户之前是否访问过某网站呢?

思路:

  1. 找一个某网站首页加载的静态资源,越大越好,比如知乎的main.app.js
  2. 诱导用户访问evail.com,用户打开后,尝试创建script标签去加载该静态资源,并记录加载时长a
  3. 再次创建script标签,依然去加载该静态资源,并记录加载时长b
  4. 计算a-b的值,即可大致判断用户是否曾经(近段时间内)是否打开过知乎了
async function iKonwYouVisitedTheWebsite(resourceSrc){
      function getLoadTime(){
        return new Promise(r=>{
          const script = document.createElement('script')
          const start = Date.now()
          script.onload = () => {
            document.body.removeChild(script)
            r(Date.now() - start)
          }
          script.src = resourceSrc
          document.body.appendChild(script)
        })
      }
      const t1 = await getLoadTime()
      const t2 = await getLoadTime()
      return t1 - t2
}
  iKonwYouVisitedTheWebsite('https://static.zhihu.com/heifetz/main.app.a662d8a4162fcbc4916e.js').then(t=>{
    document.write(t>250 ? `您没上过知乎:${t}` : `您上过知乎:${t}`)
  })

互联网上随时可能泄露自己的隐私,浏览器隐私模式保平安。不是开发者不防,有时候连开发者都不知道某些机制会泄露用户隐私。举一个我最近研究跨域想到的例子:

如果我们的静态资源需要授权的话(比如有权限则正常响应200,无权限响应401之类的),那么用心人利用在evail.com插入一个img标签嵌入该图片,即可通过图片是否加载成功刺探到用户是否在该网站有注册。

斐波拉契数列计算之从递归到记忆到动态规划的演进

递归版本:

function fib(n) {
  if (n <= 1) return 1;
  return fib(n - 1) + fib(n - 2);
}

这样做的问题在哪呢? 简单粗暴的实验就是将fib(100)丢去执行基本就卡在那算不出来了,实际我们以fib(4)为例,看看是怎么计算的:
https://s2.ax1x.com/2019/11/24/MLFxfg.md.png
fib(2)被计算了2次,fib(1)被计算了4次,当计算规模变大时,重复的计算会越来越多,如果我们能将计算过得结果保留下来,下次直接使用,可以节省不少计算时间。

记忆递归版本:

function fib(n, arr = [1, 1]) {
  if (n <= 1) return 1;
  // 如果结果已经被保存则直接返回
  if (arr[n]) return arr[n];
  // 新增保存记录,并返回
  return (arr[n] = fib(n - 1, arr) + fib(n - 2, arr));
}

记忆优化去递归版本(时间O(n) 空间O(n)的动态规划):

function fib(n) {
  if (n <= 1) return 1;
  let arr = [1, 1];
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

继续优化(时间O(n)空间O(1)的动态规划):

function fib(n) {
  if (n <= 1) return 1;
  let [a, b] = [1, 1];
  for (let i = 2; i <= n; i++) {
    [b, a] = [a + b, b];
  }
  return b;
}

当然,这是最简单的动态规划应用,后续继续学习背包问题、最长上升子序列、最短路径等问题。

Koa洋葱模型的另种实现

洋葱模型如下图:
onion model

middleware1而言,其next就是一个函数,返回middleware2的执行结果(一个promise对象),同理middleware2next就是一个函数,其返回middleware3的执行结果(又是一个pormise对象)…以此类推。

用函数表示为:middleware1(()=>middleware2(()=>middleware3(...))),类似函数式编程中的compose,同步情况下的简单写法就是这样:

function compose(middlewares){
    // 期望返回一个层层包裹的middleware函数
    // 这个函数接收一个next函数
    return middlewares.reduce((last, cur) => next => last(() => cur(next)));
}

// 这样就完成了一个同步的模型,测试一下

compose([
  function(next) {
    console.log("before a");
    next();
    console.log("after a");
  },
  function(next) {
    console.log("before b");
    next();
    console.log("after b");
  }
])(() => {});
/**
before a
before b
after b
after a
*/

基于上面这个基本版,稍加改造处理一些边界情况即可:

function compose(middlewares) {
  if (!Array.isArray(middlewares)) throw new TypeError('Middlewares must be an array!');

  middlewares.forEach(item => {
    if (typeof item !== 'function') throw new TypeError('Middleware must be componsed of function');
  });

  const noop = () => {};
  // next=noop work for 0 middleware
  const emptyMiddleware = async (_, next = noop) => next();

  // 保证在一个中间件中next只被调用一次
  const guard = ctx => next => {
    let runed = false;
    // next 返回promise,包装一层依然要返回promise
    return async () => {
      if (runed) throw new Error('next() should not be called multiple times in one middleware!');
      runed = true;
      // 这里保证 middlewareChain(ctx,middleware) 正常
      return next(ctx, noop);
    };
  };

  return middlewares.reduce(
    // middlewareChain可能没被传入next
    (last, cur) => (ctx, next = noop) =>
      // 不看guard的话很好理解  last(ctx,() => cur(ctx,next))
      // 白话就是 前一个middleware 的参数为一个函数 返回当前middleware的执行结果
      // 而当前middleware的执行需要传入next
      last(
        ctx,
        guard(ctx)(() => cur(ctx, guard(ctx)(next)))
      ),
    emptyMiddleware
  );
}

使用:

compose([
    async (ctx,next)=>{
        console.log('before a')
        await next()
        console.log('after a')
    },
    async (ctx,next)=>{
        console.log('before b')
        await next()
        console.log('after b')
    }
])()

/**
before a
before b
after b
after a
*/

已跑通全部用例: https://github.com/koajs/compose/blob/master/test/test.js

某数二进制中包含1的个数计算

这是一个来自社区的题目,表述如下:

实现一个函数countOne,计算给定的参数数值(自然数)的二进制包含“1”的个数,如:

  • countOne(10) => 2
  • countOne(16) => 1
  • countOne(3) => 2

如果不让使用 Number.prototype.toString 又该如何实现呢?

丢到公司技术群里沉没了,周末了自己来写下思考过程,实际上自己思考过程中不会这么顺利,写这篇文章只是为了梳理对比自己思考的过程,所谓:思考思考的过程。能帮助自己之后碰到一些问题能快速的切中要点而得出解法。


分割线


捷径

以10进制的27为例,二进制形式为: 11011,我们肉眼可以很快得出含有四个1,那么如何让计算机数出来呢?
当然,最容易想到的就是:

num.toString(2).replace(/0/g,"").length

当不让使用Number.prototype.toString的时候,我们依然最先想到的自己实现一个十进制转二进制的函数。然后按上面的方法来计算1的个数.

那么有没有更好的方式呢?

分析

我们分析下11011这个二进制数,如何一个个数1呢?试想一下,如果我们能通过某种方式一次性去掉一个1,直到这个数最终变为0,我们统计消除1的次数不就好了嘛?

我们先复习下几个位运算符:

  1. 与运算 &
  • 1 & 0 => 0
  • 1 & 1 => 1
  • 0 & 0 => 0
  1. 或运算 |
  • 1 | 0 => 1
  • 1 | 1 => 1
  • 0 | 0 => 0
  1. 异或运算 ^
  • 1 ^ 0 => 1
  • 1 ^ 1 => 0
  • 0 ^ 0 => 0

眼尖的小伙伴已经注意到上面的每种位运算符的三种运算情况,只有两个符合我们的需求(成功把前面的1变成了0):

1 & 0   // 0
1 ^ 1  // 0

尝试

我们注意力重新回到11011这个二进制数上来,我们需要挑一个怎样的数字来应用上面的两种运算符号与11011做运算从而消除一个1呢?

  1. 先分析异或运算

1.1 如果我们要消除第一个1

`11011` ^ X   => `01011`    (注意是二进制运算,不是十进制的11011)

我们很容易可以写出X应该为:10000

1.2 同理,我们要消除最后一个1

`11011` ^ X  => `11010`

依然很容易得出X应该为:00001 (为了方便你肉眼对齐验证,估计补了4个0)

无论我们是为了从前到后消除1而需要的二进制数10000,还是为了从后到前消除1而得到的二进制数1都与我们原来的数11011好像并没有什么明显的关联。

注意,我这里用了明显二字,而你要分析的话,还是有那么些规律的,比如我们多换几个数:

原数 左->右 右->左
10101 10000 101
10101010 10000000 11
111000 100000 1111
10000 10000 11111

从左至右消1的那个数与原数还是有关系的,那么我们的问题就会变为如何从诸如11011得到10000的问题了,其实也不难,但总归是麻烦的,我们不妨先按同样的套路分析下与运算,看看会不会更简单。

2.与运算分析

2.1 如果我们要消除第一个1

`11011` &  X   => `01011` 

我们很容易可以写出X应该为:0101101111

2.2 同理,如果我们要消除最后一个1

`11011` & X  => `11010`

依然很容易得出X应该为:1101011110

眼尖的小伙伴应该已经发现了,要通过与运算消除最后一个1用到的数11010与原数11011不是亲兄弟嘛(原数减1)。

我们用这个规律多验证下试试:

`11010` & `11001` => `11000`
`11000` & `10111` => `10000`
`1000` & `0111` => `0000`

再试下:

`1110010` & `1110001` => `1110000`
`1110000` & `1101111` => `1100000`
`1100000` & `1011111` => `1000000`
`1000000` & `0111111` => `0000000`

是不是完美?

Coding

function countOne(num){
  let count = num > 0 ? 1 : 0
  while(num = num & (num - 1))count++
  return count
}

真正诠释了分析一大堆,代码两三行。其实无论是解决实际问题,还是做题,真正有意思的是过程,分析的过程,而非这个结果。

基于webpack构建项目的SourceMap(伪)最佳实践

SourceMap是什么

像C++、OC等语言的编译器,在编译的时候会生成符号文件,对外无需发布这些符号文件,而当有异常上报或本地Debug二进制文件时,可以帮助开发人员将二进制尽可能还原成源码级别(好像无法完全还原)进行调试或进行错误分析。

而前端工程中的SourceMap也是类似的功能。我们构建前端工程时会做这么多动作:

  • 各类型文件处理,如vue、jsx、less、ts等
  • es6+ 转 es5
  • 代码压缩
  • 代码混淆

经过这些处理后,代码往往被处理得面目全非了,变量名也变成了无意义的字母,感受下:

点击查看大图

被处理成这样子了,要调试是很困难的,而SourceMap就是在编译阶段由构建工具生成的源码与目标代码的对照表,所以,我们可以通过SourceMap将打包后的代码完美还原为源代码:
点击查看大图

既然SourceMap有这么强大的作用,我们必然不能将其暴露到生产环境,不然我们辛辛苦苦开发的功能会被有心人直接下载,稍加修改就改头换面上线了。这也就是为什么会有本文章的原因。至于SourceMap的原理,大家可以参考阮一峰的JavaScript Source Map 详解

webpack下的SourceMap

webpack项提供了devtool选项来配置是否需要在构建的时候生成SourceMap,需要的话生成何种SourceMap。

咦,SourceMap不就是那个什么映射文件么,怎么在webpack这边还分品种了呢?实际上,不同的人对构建速度、SourceMap对编译后代码的还原程度、SourceMap的安全问题都有不同的要求,为了满足不同人的要求,同时又降低配置难度,webpack只给devtool提供了13个单选值,开发者根据需求选择就好了(说得好轻松呀:只有13个):
img

该用哪个?我好方!我好南!

不过其实静下心来仔细看看说明,搞清三个概念,再配合你对构建速度的要求、安全问题就能很快抉择了:

以SourceMap对js文件的还原度为例

  • 打包后的代码: 就是最开始那张截图,基本无法调试
  • 生成后的代码:经webpack处理了模块化依赖、经babel等loader处理了es6+转es5的代码,但保留了模块信息
  • 转换过的代码:经babel等loader处理了es6+转es5的代码,还未处理模块化(可以看到import之类的语法)
  • 原始源代码:和我们开发中的源代码一致,还原度非常高
  • 仅限行:由于SourceMap中没有列信息,所以调试只能在行级别,无法进行单行多表达式调试

记住上面几个概念,我们就能很快通过查表确定自己需要哪种SourceMap了。而我们若想通过这些配置项名称快速决定使用哪种SourceMap,请继续看。

我们仔细对比可以发现:

  • 名字中带eval的(重新)构建速度一般比其他的快
  • 名字中带cheap的没有列信息,只能进行行调试,同类型SourceMap带cheap比不带cheap速度要快一些
  • 名字中带module都能映射原始源代码
  • 名字中带inlineeval的都不能用于生产环境
  • 还原度最高的是source-mapeval-source-maphidden-source-map

注:带inlineeval的不能用于生产环境是因为这两者生成的SourceMap是内嵌在构建完成的js代码中的,会在生产环境直接暴露源代码。

怎么选?

开发环境,追求重新构建速度,同时也要高度还原代码,可选:eval-source-mapcheap-module-eval-source-map,这二者可以自己抉择,后者速度更快、生成的包体积更小,但无法进行行内调试。

生产环境,又要安全,又要高还原度,不在乎打包速度,那么可选source-maphidden-source-map

生产环境的SourceMap

为什么在生成环境需要SourceMap呢?试想下,如果生成环境出现什么Bug,而在其他环境不容易复现,最简单的方式就是直接在生产调试,如果没有SourceMap,这个调试过程势必十分痛苦。

上面我们提到了,生产环境可选的两种配置,他们的区别在于:source-map会在构建后的js文件末尾添加类似:

//# sourceMappingURL=jquery.min.map

的注释,告知浏览器该文件对应的SourceMap在何处下载,而hidden-source-map则仅仅生成SourceMap,不会告知浏览器该去哪寻找SourceMap还原代码。这里我们面临两个问题:

  1. 选择source-map,我们的SourceMap路径会暴露在外面,如果我们的浏览器能下载,那么别人一样可以下载
  2. 选择hidden-source-map,该怎么告诉浏览器我们的SourceMap在何处呢?

针对问题2,Chrome确实提供了针对单个js文件手动导入SourceMap的方式,方式是在开发者工具的Sources面板,找到需要调试的js文件,右键代码区域,在弹出的菜单中点击Add source map...,然后填入这个文件对应的SourceMap文件地址,弊端就是:得针对构建完成的文件一个个手动添加,而且一刷新就没了,需要再次手动添加。

ps: 实际上hidden-source-map更多的场景是用于类似于sentry这样的异常监控平台,在监控到线上的异常后上传对应的SourceMap文件,精确分析错误。

针对问题1,我们可以在构建后将SourceMap上传至一个仅内网可访问的地方,这样,同样打开控制台,我们自己的人可以进行源码调试,而其他人则没办法。但是,这样就没问题了嘛?没问题说明你的日子还是太安逸啊,居然没有在休假的时候被打电话告知线上出现了一个bug,需要紧急定位一下,这时候,我们用VPN拨号回公司确实可以解决问题,那么还有没有其他方式呢?

只要努力去想,方法的数量总是高过问题的。

我这里借助gitlab来实现,相信很多公司都部署了私有的gitlab,同时为了方便小伙伴在任何地方都方便提交代码,是允许外网授权访问的。gitblab中的项目权限有一项:“内部”,也就是仅内部员工登录后可查看,这就符合我们的需求了。
图片

借力gitlab

心路历程:其实我一开始是去尝试用gitlab的代码片段(类似于GitHub的gist)来做这个事情,但是后面发现其比gist的功能要弱很多,只支持单文件,只好放弃。

依据我们的需求,webpack提供的几种SourceMap已经无法满足我们的需求了,需要通过SourceMapDevToolPlugin插件来定制需求,该插件实现了对SourceMap生成内容进行更细粒度的控制,说白了,上面预制的一些选项都可以通过该插件配置而来。

先来确定下我们的需求:

  • 完整的SourceMap
  • SourceMap地址需要以自定义地址的形式注释在js文件的末尾

SourceMapDevToolPlugin很容易达成该要求:

new webpack.SourceMapDevToolPlugin({
    append: `\n//# sourceMappingURL=[url]`,
    filename: '[file].map',
    publicPath: 'https://gitlab.xxx.com/xxxx/sourcemap/raw/dev',
    fileContext: 'js',
    include: /\.jsx?$|\.vue$/,
})

这样,我们构建完成的js文件最后都会带上诸如如下的SourceMap路径注释了:

//# sourceMappingURL=https://gitlab.xxx.com/xxxx/sourcemap/raw/dev/xxxx.map

另一边,我们还需要将map文件给提交到项目xxxx/sourcemapdev分支才行,要拿到SourceMap文件并上传,需等到资源构建完成或者webpack的整个流程完成,我们这里选择用插件的形式在资源构建完成的时候push至gitlab,先完成插件:

const path = require('path');
const fs = require('fs');

class SourcemapWebpackPlugin {
  constructor(handler) {
    if (typeof handler !== 'function')
      throw new TypeError('SourcemapWebpackPlugin构造函数参数只能是函数');
    this.handler = handler;
  }

  apply(compiler) {
    // 监听`afterEmit`事件
    compiler.hooks.afterEmit.tapAsync('SourcemapPlugin', (compilation, callback) => {
     // 取得所有构建出来的资源
      const assets = compilation.assets;
      const files = [];
      Object.keys(assets).forEach(fileName => {
         // 我们只care map文件
        if (/\.map$/.test(fileName)) {
        // 拧出文件完整路径、文件名、文件内容
          files.push({
            path: assets[fileName].existsAt,
            name: path.basename(fileName),
            // 不用到的时候不要取出来
            get content() {
              return assets[fileName].source();
            },
          });
        }
      });
      // 丢给插件使用者自行做上传处理
      this.handler(files, err => {
        // map文件清理,防止发布到线上
        files.forEach(file => fs.unlink(file.path, () => {}));
        callback(err);
      });
    });
  }
}

gitlab文件的push需要用到这个API,然后事情就简单了:

const got = require('got');
const qs = require('qs');

new SourcemapWebpackPlugin((files, callback) => {
    console.log('开始上传SourceMap...');
    const actions = files.map(file => ({
    action: 'create',
    file_path: file.name,
    content: file.content,
  }));
  const data = {
    actions,
    // 事先创建一个空白的master分支,然后在此基础上分出dev
    // 以后每次都是以master为基础,对dev进行commit
    // 配合 force: true 选项,每次构建都能清理上次提交的map文件
    force: true,
    branch: "dev",
    start_branch: "master",
    commit_message: 'commit at sourcemap',
  };
  return got
    .post(`https://gitlab.xxx.com/api/v4/projects/xxx%2F/sourcemap/repository/commits`, {
      body: qs.stringify(data, { arrayFormat: 'brackets' }),
      headers: {
        'PRIVATE-TOKEN': "<YOUR_ACCESS_TOKEN>",
        'Content-Type': 'application/x-www-form-urlencoded',
      },
    }).then(() => callback()).catch(err => callback(err.body));
    // plugin hook的callback正常情况下不能传参,传参代表失败
});

至此,全部工作完成,可以build构建试试,如果没得效果,请确认当前浏览器是否登录了gitlab,是否有权限打开xxx/sourcemap这个项目。

任何框架、方法都不是银弹,只有适合自己实际情况才是王道,并没有完美的最佳实践。

《完》

一起来洗牌

一副扑克牌:

const arr = ["A","2","3","4","5","6","7","8","9","10","J","Q","K","S"]

通过何种方式洗牌才是足够乱的呢?

如果单论“洗牌”二字,很多前端的伙计肯定想都不想就这么写了:

arr.sort(()=> Math.random() - 0.5)

但我这里强调了“足够乱”,是否让你驻足思考下,如何才能证明一个洗牌算法是足够乱的?

“足够乱”说明每张牌出现在任意位置的概率理论上应该是接近的,按照统计学的说法,当独立重复实现足够多的时候,实验数据越接近理论数据。

如何表示某张牌出现在某位置的概率?

有点费解,我们这里换下概念,把“概率”换成“次数”,表述换成:

如何表示实验xx次,某张牌出现在某位置的次数呢?

这好办,如下:

let ret = {
    "A-0": 12, // 表示A出现在0位置12次
    "A-1": 6, // 表示A出现在1位置6次
    "2-1": 9 // 表示2出现在1位置9次
    // ...
}

定好数据结构,我们就可以来实现我们的统计算法了:

function statistics(shuffle, loopCount = 2e5) {
    const arr = ["A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "S"]
    let obj = {}
    let i = 0
    while (i++ < loopCount) {
        let copy = shuffle(arr)
        for (let j = 0; j < arr.length; j++) {
            // 打乱后 j 位置的字符
            let item = copy[j]
            // 以item与j组合 记录出现次数
            const key = `${item}-${j}`
            if (obj[key] === undefined) obj[key] = 0
            obj[key]++
        }
    }
    // 为了看出差异,我们按次数排序,并放到数组中
    return Object.keys(obj)
        .sort((a, b) => obj[b] - obj[a])
        .reduce((acc, cur) => [...acc, { [cur]: obj[cur] }], [])
}

我们把上面那个“洗牌算法”,稍微改造下,以适配这个统计函数:

function shuffle(arr) {
    let copy = [...arr]
    return copy.sort(() => Math.random() - 0.5)
}

测试一波:

// 测试20万次出结果
const ret = statistics(shuffle,  2e5)
console.log(ret)
// [{"A-0":30278},{"S-6":25056},{"S-13":24947},{"A-1":23413}...{"4-13":8261},{"2-12":7133},{"2-13":3190}]

注意到:20万次试验中,A出现在位置0处的次数达30278(概率约为15.14%),而2出现在位置13处的次数仅有3190次(概率约为1.60%),结果明显不均匀。

多重复几次的结果:

[{"A-0":30354},{"S-13":25075},{"S-6":24972},{"A-1":23243}...{"4-13":8115},{"2-12":7175},{"2-13":3182}]
[{"A-0":30421},{"S-13":24925},{"S-6":24847},{"A-1":23298}...{"4-13":8328},{"2-12":7124},{"2-13":2998}]
[{"A-0":30248},{"S-13":24944},{"S-6":24888},{"A-1":23321}...{"4-13":8348},{"2-12":7230},{"2-13":3134}]
[{"A-0":30151},{"S-6":25103},{"S-13":24851},{"A-1":23201}...{"4-13":8125},{"2-12":6950},{"2-13":3226}]
[{"A-0":29966},{"S-6":24984},{"S-13":24941},{"A-1":23181}...{"4-13":8354},{"2-12":7078},{"2-13":3032}]
// ...

我们还是得换种方式实现洗牌算法(Fisher–Yates shuffle):

function shuffle(arr) {
    let copy = [...arr]
    let i = copy.length, j;
    // 倒着循环
    while (i--) {
        // 从[0,i) 随机找一个位置j
        j = parseInt(Math.random() * i);
        // 交换位置i与位置j处的值
        [copy[i], copy[j]] = [copy[j], copy[i]]
    }
    return copy;
}

实现其实很简单,不会写记住就好了,总有你会用到的场合

再测试一波:

// 测试20万次出结果
const ret = statistics(shuffle,  2e5)
console.log(ret)
// [{"3-6":15716},{"Q-2":15715},{"A-12":15686},{"K-10":15681}...{"3-13":15152},{"5-5":15124},{"S-12":15101}]

已经肉眼可见的“均匀”了,我们算下概率:概率最高的A出现在位置13处的概率约为7.89%,而概率最低的6出现在位置10处的位置约为7.54%,差距已经在0.3%左右了。

多重复几次的结果

[{"5-13":15678},{"10-6":15667},{"3-8":15621},{"10-11":15612}...{"10-8":15127},{"8-11":15081},{"7-3":15033}]
[{"4-5":15756},{"6-4":15755},{"K-0":15655},{"4-6":15654}...{"4-0":15069},{"S-7":15006},{"A-0":1}]
[{"A-8":15741},{"8-1":15681},{"4-2":15656},{"K-7":15627}...{"J-9":15112},{"4-1":15100},{"A-0":1}]
[{"K-0":15705},{"5-6":15621},{"Q-2":15614},{"5-3":15596}...{"S-6":15119},{"5-12":15105},{"K-7":15088}]
[{"2-11":15804},{"7-1":15770},{"5-12":15745},{"K-7":15727}...{"S-0":15106},{"7-9":15075},{"K-3":15057}]
// ...

上面的数据,是跑了20w遍测试得到的,而我自己后面在尝试加到100w次试验时,这个差距降到了0.1%左右。

[{"5-12":77936},{"3-9":77495},{"J-13":77464},{"2-12":77445}...{"J-3":76355},{"2-11":76273},{"2-9":76233}]

你说会写测试代码重不重要?