def nmatch
= RStr
("match")
def assign
(r
: Inst, n
: Int
): (Inst, Int
) = (Assign
(RInt
(n
), r
), n +
1) def mk
_label
(n
: Int
): (Inst, Int
) = (Label
(RInt
(n
)), n +
1)
def insts
_of
_regex
(re
: Regex
): List
[Inst
] = { def loop
(re
: Regex, n
: Int
): (List
[Inst
], Int
) = re
match {
val (i1, n1
) = mk
_label
(n
) val (i2, n2
) = assign
(Load
(I64P, nsp
), n1
) val (i3, n3
) = assign
(GetElementPtr
(I8P, nstr, RInt
(n1
)), n2
) val (i4, n4
) = assign
(Add
(I64, RInt
(n1
),
1), n3
) val i5
= Store
(I64, RInt
(n3
), I64P, nsp
) val (i6, n5
) = assign
(Load
(I8P, RInt
(n2
)), n4
) val (i7, n6
) = assign
(Cmp
(Eq, I8, RInt
(n4
), VInt
(c.
toInt)), n5
) val i8
= Br2
(RInt
(n5
), RInt
(n6
), nmiss
) (List(i1, i2, i3, i4, i5, i6, i7, i8), n6)
val (i1, n1
) = loop
(a, n
) val (i2, n2
) = loop
(b, n1
) (i1 ++ i2, n2)
val (i1, n1
) = mk
_label
(n
) val (i2, n2
) = assign
(Load
(I64P, nsp
), n1
) val (i3,
_) = assign
(Call
(fname, I1, List
((I8P, BA
(fname, RInt
(n2 +
1))),
(I64, RInt
(n1
)))), n2
) val (i4, n4
) = loop
(a, n2 +
1) val (i5, n5
) = mk
_label
(n4
) val (i6, n6
) = loop
(b, n5
) val i8
= Br2
(RInt
(n2
), nmatch, RInt
(n5
)) (List(i1, i2, i3, i8) ++ i4 ++ List(i5, i7) ++ i6, n6)
case Star
(Star
(r
)) => loop
(Star
(r
), n
)
val (i1, n1
) = mk
_label
(n
) val (i2, n2
) = assign
(Load
(I64P, nsp
), n1
) val (i3,
_) = assign
(Call
(fname, I1, List
((I8P, BA
(fname, RInt
(n2 +
1))),
(I64, RInt
(n1
)))), n2
) val (i4, n3
) = loop
(r, n2 +
1) val (i5, n4
) = mk
_label
(n3
) val i7
= Br2
(RInt
(n2
), nmatch, RInt
(n4
)) (List(i1, i2, i3, i7) ++ i4 ++ List(i5, i6), n4)
}
i ++ List(Label(RInt(n)), Br1(nmatch))
}
def label
_of
_value
(v
: Value
): String
= v
match { case RInt
(n
) => n.
toString }
def var
_of
_value
(v
: Value
): String
= v
match { case VInt
(n
) => n.
toString case BA
(f, l
) => "blockaddress(" + f +
", " + var
_of
_value
(l
) +
")" }
def pp
_cond
(c
: Cond
): String
= c
match { }
def pp
_type
(t
: Type
): String
= t
match { }
}
def pp
_inst
(i
: Inst, tab
: String
= ""): String
= "\n; <label>:" + label_of_value(n)
var_of_value(l) + " = " + pp_inst(r)
"add nsw " + pp_type(t) + " " + var_of_value(v) + ", " + n
"icmp " + pp_cond(c) + " " + pp_type(t) + " " + var_of_value(a) + ", " + var_of_value(b)
"br label " + var_of_value(d)
"br i1 " + var_of_value(c) + ", label " + var_of_value(t) + ", label " + var_of_value(e)
val s
= a.
foldLeft("i8* %str")((x, y
) => x +
", " + pp
_type
(y.
_1
) +
" " + var
_of
_value
(y.
_2
)) "call " + pp_type(rt) + " " + f + "(" + s + ")"
"load " + pp_type(t) + " " + var_of_value(p) + ", align " + align(t)
case Store
(vt, v, pt, pv
) => "store " + pp_type(vt) + " " + var_of_value(v) + ", " + pp_type(pt) + " " +
var_of_value(pv) + ", align " + align(vt)
case GetElementPtr
(t, v, i
) => "getelementptr inbounds " + pp_type(t) + " " + var_of_value(v) + ", i64 " + var_of_value(i)
})
def make
(i
: List
[Inst
]): String
= { "@.match = private unnamed_addr constant [7 x i8] c\"match\\0A\\00\", align 1\n" +
"@.unmatch = private unnamed_addr constant [9 x i8] c\"unmatch\\0A\\00\", align 1\n\n" +
"define i1 @test(i8* %str, i8* %l, i64 %sp_value) {\n" +
" %sp = alloca i64, align 8\n" +
" store i64 %sp_value, i64* %sp, align 8\n" +
" %isnull = icmp eq i8* %l, null\n" +
" br i1 %isnull, label %1, label %jump\n\n" +
"jump:\n" +
" indirectbr i8* %l, [" +
i.
foldRight(List
[String
]())((x, y
) => x
match { case Label
(n
) => ("label " + var
_of
_value
(n
)) :: y
}).mkString(", ") + "]\n"
val llvmir
= i.
map(pp
_inst
(_,
" ")).
foldLeft("")((x, y
) => x + y +
"\n")
"\nmiss:\n" +
" ret i1 0\n\n" +
"match:\n" +
" ret i1 1\n" +
"}\n\n" +
"define i32 @main(i32 %argc, i8** %argv) {\n" +
" %arg1 = getelementptr inbounds i8** %argv, i64 1\n" +
" %str = load i8** %arg1, align 8\n" +
" %res = call i1 @test(i8* %str, i8* null, i64 0)\n" +
" br i1 %res, label %match, label %unmatch\n\n" +
"match:\n" +
" call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([7 x i8]* @.match, i32 0, i32 0))\n" +
" br label %ret\n\n" +
"unmatch:\n" +
" call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([9 x i8]* @.unmatch, i32 0, i32 0))\n" +
" br label %ret\n\n" +
"ret:\n" +
" ret i32 0\n" +
"}\n\n" +
"declare i32 @printf(i8*, ...)"
s + llvmir + e
}
def main
(args
: Array
[String
]): Unit
= { // aa*bb*
val re1
= Con
( Con
(Let
('a'), Star
(Let
('a'))), Con
(Let
('b'), Star
(Let
('b'))) ) // (a|b)c
val re2
= Con
( Alt
(Let
('a'), Let
('b')), Let
('c') ) // (a*)*a
val re3
= Con
(Star
(Star
(Let
('a'))), Let
('a')) // aaaa
val re4
= Con
( Con
(Let
('a'), Let
('a')), Con
(Let
('a'), Let
('a')) ) // (ba*ba*)*a
val re5
= Con
(Star
(Con
(Con
(Star
(Let
('a')), Let
('b')), Star
(Let
('a')))), Let
('a')) // sa*(ba*ba*)*a*e
val re6
= Con
(Con
(Let
('s'), Con
(Con
(Star
(Let
('a')), Star
(Con
(Con
(Let
('b'), Star
(Let
('a'))), Con
(Let
('b'), Star
(Let
('a')))))), Star
(Let
('a')))), Let
('e')) // s(ab*)*e
val re7
= Con
(Con
(Let
('s'), Star
(Con
(Let
('a'), Star
(Let
('b'))))), Let
('e')) // ba*b
val re8
= Con
(Con
(Let
('b'), Star
(Let
('a'))), Let
('b'))
val i
= insts
_of
_regex
(re8
) println(make(i))
}
}
c2VhbGVkIHRyYWl0IFJlZ2V4CmNhc2Ugb2JqZWN0IEVtcHR5ICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBSZWdleApjYXNlIGNsYXNzIExldChjOiBDaGFyKSAgICAgICAgICAgIGV4dGVuZHMgUmVnZXgKY2FzZSBjbGFzcyBDb24oYTogUmVnZXgsIGI6IFJlZ2V4KSBleHRlbmRzIFJlZ2V4CmNhc2UgY2xhc3MgQWx0KGE6IFJlZ2V4LCBiOiBSZWdleCkgZXh0ZW5kcyBSZWdleApjYXNlIGNsYXNzIFN0YXIoYTogUmVnZXgpICAgICAgICAgIGV4dGVuZHMgUmVnZXgKCnNlYWxlZCB0cmFpdCBWYWx1ZQpjYXNlIGNsYXNzIFJJbnQobjogSW50KSAgICAgICAgICAgIGV4dGVuZHMgVmFsdWUKY2FzZSBjbGFzcyBSU3RyKHM6IFN0cmluZykgICAgICAgICBleHRlbmRzIFZhbHVlCmNhc2UgY2xhc3MgVkludChuOiBJbnQpICAgICAgICAgICAgZXh0ZW5kcyBWYWx1ZQpjYXNlIGNsYXNzIEJBKGY6IFN0cmluZywgbDogVmFsdWUpIGV4dGVuZHMgVmFsdWUKCnNlYWxlZCB0cmFpdCBUeXBlCmNhc2Ugb2JqZWN0IEkxICAgZXh0ZW5kcyBUeXBlCmNhc2Ugb2JqZWN0IEk4ICAgZXh0ZW5kcyBUeXBlCmNhc2Ugb2JqZWN0IEk4UCAgZXh0ZW5kcyBUeXBlCmNhc2Ugb2JqZWN0IEk2NCAgZXh0ZW5kcyBUeXBlCmNhc2Ugb2JqZWN0IEk2NFAgZXh0ZW5kcyBUeXBlCgpzZWFsZWQgdHJhaXQgQ29uZApjYXNlIG9iamVjdCBFcSBleHRlbmRzIENvbmQKCnNlYWxlZCB0cmFpdCBJbnN0CmNhc2UgY2xhc3MgTGFiZWwobjogVmFsdWUpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQXNzaWduKGw6IFZhbHVlLCByOiBJbnN0KSAgICAgICAgICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQWRkKHQ6IFR5cGUsIHY6IFZhbHVlLCBuOiBJbnQpICAgICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQ21wKGM6IENvbmQsIHQ6IFR5cGUsIGE6IFZhbHVlLCBiOiBWYWx1ZSkgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQnIxKGQ6IFZhbHVlKSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQnIyKGM6IFZhbHVlLCB0OiBWYWx1ZSwgZTogVmFsdWUpICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgQ2FsbChmOiBTdHJpbmcsIHJ0OiBUeXBlLCBhdDogTGlzdFsoVHlwZSwgVmFsdWUpXSkgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgTG9hZCh0OiBUeXBlLCBwOiBWYWx1ZSkgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgU3RvcmUodnQ6IFR5cGUsIHY6IFZhbHVlLCBwdDogVHlwZSwgcHY6IFZhbHVlKSAgICAgZXh0ZW5kcyBJbnN0CmNhc2UgY2xhc3MgR2V0RWxlbWVudFB0cih0OiBUeXBlLCB2OiBWYWx1ZSwgaTogVmFsdWUpICAgICAgICAgZXh0ZW5kcyBJbnN0CgpvYmplY3QgTWFpbiB7CiAgZGVmIG5zcCAgICA9IFJTdHIoInNwIikKICBkZWYgbnN0ciAgID0gUlN0cigic3RyIikKICBkZWYgbm1hdGNoID0gUlN0cigibWF0Y2giKQogIGRlZiBubWlzcyAgPSBSU3RyKCJtaXNzIikKCiAgZGVmIGZuYW1lID0gIkB0ZXN0IgoKICBkZWYgYXNzaWduKHI6IEluc3QsIG46IEludCk6IChJbnN0LCBJbnQpID0gKEFzc2lnbihSSW50KG4pLCByKSwgbiArIDEpCiAgZGVmIG1rX2xhYmVsKG46IEludCk6IChJbnN0LCBJbnQpID0gKExhYmVsKFJJbnQobikpLCBuICsgMSkKCiAgZGVmIGluc3RzX29mX3JlZ2V4KHJlOiBSZWdleCk6IExpc3RbSW5zdF0gPSB7CiAgICBkZWYgbG9vcChyZTogUmVnZXgsIG46IEludCk6IChMaXN0W0luc3RdLCBJbnQpID0gcmUgbWF0Y2ggewogICAgICBjYXNlIEVtcHR5ID0+IChOaWwsIG4pCgogICAgICBjYXNlIExldChjKSA9PgogICAgICAgIHZhbCAoaTEsIG4xKSA9IG1rX2xhYmVsKG4pCiAgICAgICAgdmFsIChpMiwgbjIpID0gYXNzaWduKExvYWQoSTY0UCwgbnNwKSwgbjEpCiAgICAgICAgdmFsIChpMywgbjMpID0gYXNzaWduKEdldEVsZW1lbnRQdHIoSThQLCBuc3RyLCBSSW50KG4xKSksIG4yKQogICAgICAgIHZhbCAoaTQsIG40KSA9IGFzc2lnbihBZGQoSTY0LCBSSW50KG4xKSwgMSksIG4zKQogICAgICAgIHZhbCAgaTUgICAgICA9IFN0b3JlKEk2NCwgUkludChuMyksIEk2NFAsIG5zcCkKICAgICAgICB2YWwgKGk2LCBuNSkgPSBhc3NpZ24oTG9hZChJOFAsIFJJbnQobjIpKSwgbjQpCiAgICAgICAgdmFsIChpNywgbjYpID0gYXNzaWduKENtcChFcSwgSTgsIFJJbnQobjQpLCBWSW50KGMudG9JbnQpKSwgbjUpCiAgICAgICAgdmFsICBpOCAgICAgID0gQnIyKFJJbnQobjUpLCBSSW50KG42KSwgbm1pc3MpCiAgICAgICAgKExpc3QoaTEsIGkyLCBpMywgaTQsIGk1LCBpNiwgaTcsIGk4KSwgbjYpCgogICAgICBjYXNlIENvbihhLCBiKSA9PgogICAgICAgIHZhbCAoaTEsIG4xKSA9IGxvb3AoYSwgbikKICAgICAgICB2YWwgKGkyLCBuMikgPSBsb29wKGIsIG4xKQogICAgICAgIChpMSArKyBpMiwgbjIpCgogICAgICBjYXNlIEFsdChhLCBiKSA9PgogICAgICAgIHZhbCAoaTEsIG4xKSA9IG1rX2xhYmVsKG4pCiAgICAgICAgdmFsIChpMiwgbjIpID0gYXNzaWduKExvYWQoSTY0UCwgbnNwKSwgbjEpCiAgICAgICAgdmFsIChpMywgXykgID0gYXNzaWduKENhbGwoZm5hbWUsIEkxLCBMaXN0KChJOFAsIEJBKGZuYW1lLCBSSW50KG4yICsgMSkpKSwgKEk2NCwgUkludChuMSkpKSksIG4yKQogICAgICAgIHZhbCAoaTQsIG40KSA9IGxvb3AoYSwgbjIgKyAxKQogICAgICAgIHZhbCAoaTUsIG41KSA9IG1rX2xhYmVsKG40KQogICAgICAgIHZhbCAoaTYsIG42KSA9IGxvb3AoYiwgbjUpCiAgICAgICAgdmFsIGk3ICAgICAgID0gQnIxKFJJbnQobjYpKQogICAgICAgIHZhbCBpOCAgICAgICA9IEJyMihSSW50KG4yKSwgbm1hdGNoLCBSSW50KG41KSkKICAgICAgICAoTGlzdChpMSwgaTIsIGkzLCBpOCkgKysgaTQgKysgTGlzdChpNSwgaTcpICsrIGk2LCBuNikKCiAgICAgIGNhc2UgU3RhcihTdGFyKHIpKSA9PiBsb29wKFN0YXIociksIG4pCgogICAgICBjYXNlIFN0YXIocikgPT4KICAgICAgICB2YWwgKGkxLCBuMSkgPSBta19sYWJlbChuKQogICAgICAgIHZhbCAoaTIsIG4yKSA9IGFzc2lnbihMb2FkKEk2NFAsIG5zcCksIG4xKQogICAgICAgIHZhbCAoaTMsIF8pICA9IGFzc2lnbihDYWxsKGZuYW1lLCBJMSwgTGlzdCgoSThQLCBCQShmbmFtZSwgUkludChuMiArIDEpKSksIChJNjQsIFJJbnQobjEpKSkpLCBuMikKICAgICAgICB2YWwgKGk0LCBuMykgPSBsb29wKHIsIG4yICsgMSkKICAgICAgICB2YWwgKGk1LCBuNCkgPSBta19sYWJlbChuMykKICAgICAgICB2YWwgIGk2ICAgICAgPSBCcjEoUkludChuKSkKICAgICAgICB2YWwgIGk3ICAgICAgPSBCcjIoUkludChuMiksIG5tYXRjaCwgUkludChuNCkpCiAgICAgICAgKExpc3QoaTEsIGkyLCBpMywgaTcpICsrIGk0ICsrIExpc3QoaTUsIGk2KSwgbjQpCiAgICB9CgogICAgdmFsIChpLCBuKSA9IGxvb3AocmUsIDEpCiAgICBpICsrIExpc3QoTGFiZWwoUkludChuKSksIEJyMShubWF0Y2gpKQogIH0KCiAgZGVmIGxhYmVsX29mX3ZhbHVlKHY6IFZhbHVlKTogU3RyaW5nID0gdiBtYXRjaCB7CiAgICBjYXNlIFJJbnQobikgPT4gbi50b1N0cmluZwogICAgY2FzZSBfICAgICAgID0+IHRocm93IG5ldyBFeGNlcHRpb24oKQogIH0KCiAgZGVmIHZhcl9vZl92YWx1ZSh2OiBWYWx1ZSk6IFN0cmluZyA9IHYgbWF0Y2ggewogICAgY2FzZSBSSW50KG4pICA9PiAiJSIgKyBuCiAgICBjYXNlIFJTdHIocykgID0+ICIlIiArIHMKICAgIGNhc2UgVkludChuKSAgPT4gbi50b1N0cmluZwogICAgY2FzZSBCQShmLCBsKSA9PiAiYmxvY2thZGRyZXNzKCIgKyBmICsgIiwgIiArIHZhcl9vZl92YWx1ZShsKSArICIpIgogIH0KCiAgZGVmIHBwX2NvbmQoYzogQ29uZCk6IFN0cmluZyA9IGMgbWF0Y2ggewogICAgY2FzZSBFcSA9PiAiZXEiCiAgfQoKICBkZWYgcHBfdHlwZSh0OiBUeXBlKTogU3RyaW5nID0gdCBtYXRjaCB7CiAgICBjYXNlIEkxICAgPT4gImkxIgogICAgY2FzZSBJOCAgID0+ICJpOCIKICAgIGNhc2UgSThQICA9PiAiaTgqIgogICAgY2FzZSBJNjQgID0+ICJpNjQiCiAgICBjYXNlIEk2NFAgPT4gImk2NCoiCiAgfQoKICBkZWYgYWxpZ24odDogVHlwZSk6IEludCA9IHQgbWF0Y2ggewogICAgY2FzZSBJOCAgID0+IDEKICAgIGNhc2UgSThQICA9PiA4CiAgICBjYXNlIEk2NCAgPT4gOAogICAgY2FzZSBJNjRQID0+IDgKICAgIGNhc2UgSTEgICA9PiB0aHJvdyBuZXcgRXhjZXB0aW9uKCkKICB9CgogIGRlZiBwcF9pbnN0KGk6IEluc3QsIHRhYjogU3RyaW5nID0gIiIpOiBTdHJpbmcgPQogICAgdGFiICsgKGkgbWF0Y2ggewogICAgICBjYXNlIExhYmVsKG4pID0+CiAgICAgICAgIlxuOyA8bGFiZWw+OiIgKyBsYWJlbF9vZl92YWx1ZShuKQogICAgICBjYXNlIEFzc2lnbihsLCByKSA9PgogICAgICAgIHZhcl9vZl92YWx1ZShsKSArICIgPSAiICsgcHBfaW5zdChyKQogICAgICBjYXNlIEFkZCh0LCB2LCBuKSA9PgogICAgICAgICJhZGQgbnN3ICIgKyBwcF90eXBlKHQpICsgIiAiICsgdmFyX29mX3ZhbHVlKHYpICsgIiwgIiArIG4KICAgICAgY2FzZSBDbXAoYywgdCwgYSwgYikgPT4KICAgICAgICAiaWNtcCAiICsgcHBfY29uZChjKSArICIgIiArIHBwX3R5cGUodCkgKyAiICIgKyB2YXJfb2ZfdmFsdWUoYSkgKyAiLCAiICsgdmFyX29mX3ZhbHVlKGIpCiAgICAgIGNhc2UgQnIxKGQpID0+CiAgICAgICAgImJyIGxhYmVsICIgKyB2YXJfb2ZfdmFsdWUoZCkKICAgICAgY2FzZSBCcjIoYywgdCwgZSkgPT4KICAgICAgICAiYnIgaTEgIiArIHZhcl9vZl92YWx1ZShjKSArICIsIGxhYmVsICIgKyB2YXJfb2ZfdmFsdWUodCkgKyAiLCBsYWJlbCAiICsgdmFyX29mX3ZhbHVlKGUpCiAgICAgIGNhc2UgQ2FsbChmLCBydCwgYSkgPT4KICAgICAgICB2YWwgcyA9IGEuZm9sZExlZnQoImk4KiAlc3RyIikoKHgsIHkpID0+IHggKyAiLCAiICsgcHBfdHlwZSh5Ll8xKSArICIgIiArIHZhcl9vZl92YWx1ZSh5Ll8yKSkKICAgICAgICAiY2FsbCAiICsgcHBfdHlwZShydCkgKyAiICIgKyBmICsgIigiICsgcyArICIpIgogICAgICBjYXNlIExvYWQodCwgcCkgPT4KICAgICAgICAibG9hZCAiICsgcHBfdHlwZSh0KSArICIgIiArIHZhcl9vZl92YWx1ZShwKSArICIsIGFsaWduICIgKyBhbGlnbih0KQogICAgICBjYXNlIFN0b3JlKHZ0LCB2LCBwdCwgcHYpID0+CiAgICAgICAgInN0b3JlICIgKyBwcF90eXBlKHZ0KSArICIgIiArIHZhcl9vZl92YWx1ZSh2KSArICIsICIgKyBwcF90eXBlKHB0KSArICIgIiArCiAgICAgICAgICB2YXJfb2ZfdmFsdWUocHYpICsgIiwgYWxpZ24gIiArIGFsaWduKHZ0KQogICAgICBjYXNlIEdldEVsZW1lbnRQdHIodCwgdiwgaSkgPT4KICAgICAgICAiZ2V0ZWxlbWVudHB0ciBpbmJvdW5kcyAiICsgcHBfdHlwZSh0KSArICIgIiArIHZhcl9vZl92YWx1ZSh2KSArICIsIGk2NCAiICsgdmFyX29mX3ZhbHVlKGkpCiAgICB9KQoKICBkZWYgbWFrZShpOiBMaXN0W0luc3RdKTogU3RyaW5nID0gewogICAgdmFsIHMgPQogICAgICAiQC5tYXRjaCAgID0gcHJpdmF0ZSB1bm5hbWVkX2FkZHIgY29uc3RhbnQgWzcgeCBpOF0gY1wibWF0Y2hcXDBBXFwwMFwiLCBhbGlnbiAxXG4iICArCiAgICAgICJALnVubWF0Y2ggPSBwcml2YXRlIHVubmFtZWRfYWRkciBjb25zdGFudCBbOSB4IGk4XSBjXCJ1bm1hdGNoXFwwQVxcMDBcIiwgYWxpZ24gMVxuXG4iICsKICAgICAgImRlZmluZSBpMSBAdGVzdChpOCogJXN0ciwgaTgqICVsLCBpNjQgJXNwX3ZhbHVlKSB7XG4iICsKICAgICAgIiAgJXNwID0gYWxsb2NhIGk2NCwgYWxpZ24gOFxuIiArCiAgICAgICIgIHN0b3JlIGk2NCAlc3BfdmFsdWUsIGk2NCogJXNwLCBhbGlnbiA4XG4iICsKICAgICAgIiAgJWlzbnVsbCA9IGljbXAgZXEgaTgqICVsLCBudWxsXG4iICsKICAgICAgIiAgYnIgaTEgJWlzbnVsbCwgbGFiZWwgJTEsIGxhYmVsICVqdW1wXG5cbiIgKwogICAgICAianVtcDpcbiIgKwogICAgICAiICBpbmRpcmVjdGJyIGk4KiAlbCwgWyIgKwogICAgICAgIGkuZm9sZFJpZ2h0KExpc3RbU3RyaW5nXSgpKSgoeCwgeSkgPT4geCBtYXRjaCB7CiAgICAgICAgICBjYXNlIExhYmVsKG4pID0+ICgibGFiZWwgIiArIHZhcl9vZl92YWx1ZShuKSkgOjogeQogICAgICAgICAgY2FzZSBfICAgICAgICA9PiB5CiAgICAgICAgfSkubWtTdHJpbmcoIiwgIikgKyAiXVxuIgoKICAgIHZhbCBsbHZtaXIgPSBpLm1hcChwcF9pbnN0KF8sICIgICIpKS5mb2xkTGVmdCgiIikoKHgsIHkpID0+IHggKyB5ICsgIlxuIikKCiAgICB2YWwgZSA9CiAgICAgICJcbm1pc3M6XG4iICsKICAgICAgIiAgcmV0IGkxIDBcblxuIiArCiAgICAgICJtYXRjaDpcbiIgKwogICAgICAiICByZXQgaTEgMVxuIiArCiAgICAgICJ9XG5cbiIgKwogICAgICAiZGVmaW5lIGkzMiBAbWFpbihpMzIgJWFyZ2MsIGk4KiogJWFyZ3YpIHtcbiIgKwogICAgICAiICAlYXJnMSA9IGdldGVsZW1lbnRwdHIgaW5ib3VuZHMgaTgqKiAlYXJndiwgaTY0IDFcbiIgKwogICAgICAiICAlc3RyICA9IGxvYWQgaTgqKiAlYXJnMSwgYWxpZ24gOFxuIiArCiAgICAgICIgICVyZXMgID0gY2FsbCBpMSBAdGVzdChpOCogJXN0ciwgaTgqIG51bGwsIGk2NCAwKVxuIiArCiAgICAgICIgIGJyIGkxICVyZXMsIGxhYmVsICVtYXRjaCwgbGFiZWwgJXVubWF0Y2hcblxuIiArCiAgICAgICJtYXRjaDpcbiIgKwogICAgICAiICBjYWxsIGkzMiAoaTgqLCAuLi4pKiBAcHJpbnRmKGk4KiBnZXRlbGVtZW50cHRyIGluYm91bmRzIChbNyB4IGk4XSogQC5tYXRjaCwgaTMyIDAsIGkzMiAwKSlcbiIgKwogICAgICAiICBiciBsYWJlbCAlcmV0XG5cbiIgKwogICAgICAidW5tYXRjaDpcbiIgKwogICAgICAiICBjYWxsIGkzMiAoaTgqLCAuLi4pKiBAcHJpbnRmKGk4KiBnZXRlbGVtZW50cHRyIGluYm91bmRzIChbOSB4IGk4XSogQC51bm1hdGNoLCBpMzIgMCwgaTMyIDApKVxuIiArCiAgICAgICIgIGJyIGxhYmVsICVyZXRcblxuIiArCiAgICAgICJyZXQ6XG4iICsKICAgICAgIiAgcmV0IGkzMiAwXG4iICsKICAgICAgIn1cblxuIiArCiAgICAgICJkZWNsYXJlIGkzMiBAcHJpbnRmKGk4KiwgLi4uKSIKCiAgICBzICsgbGx2bWlyICsgZQogIH0KCiAgZGVmIG1haW4oYXJnczogQXJyYXlbU3RyaW5nXSk6IFVuaXQgPSB7CiAgICAvLyBhYSpiYioKICAgIHZhbCByZTEgPSBDb24oIENvbihMZXQoJ2EnKSwgU3RhcihMZXQoJ2EnKSkpLCBDb24oTGV0KCdiJyksIFN0YXIoTGV0KCdiJykpKSApCiAgICAvLyAoYXxiKWMKICAgIHZhbCByZTIgPSBDb24oIEFsdChMZXQoJ2EnKSwgTGV0KCdiJykpLCAgTGV0KCdjJykgICkKICAgIC8vIChhKikqYQogICAgdmFsIHJlMyA9IENvbihTdGFyKFN0YXIoTGV0KCdhJykpKSwgTGV0KCdhJykpCiAgICAvLyBhYWFhCiAgICB2YWwgcmU0ID0gQ29uKCBDb24oTGV0KCdhJyksIExldCgnYScpKSwgQ29uKExldCgnYScpLCBMZXQoJ2EnKSkgKQogICAgLy8gKGJhKmJhKikqYQogICAgdmFsIHJlNSA9IENvbihTdGFyKENvbihDb24oU3RhcihMZXQoJ2EnKSksIExldCgnYicpKSwgU3RhcihMZXQoJ2EnKSkpKSwgTGV0KCdhJykpCiAgICAvLyBzYSooYmEqYmEqKSphKmUKICAgIHZhbCByZTYgPSBDb24oQ29uKExldCgncycpLCBDb24oQ29uKFN0YXIoTGV0KCdhJykpLCBTdGFyKENvbihDb24oTGV0KCdiJyksIFN0YXIoTGV0KCdhJykpKSwgQ29uKExldCgnYicpLCBTdGFyKExldCgnYScpKSkpKSksIFN0YXIoTGV0KCdhJykpKSksIExldCgnZScpKQogICAgLy8gcyhhYiopKmUKICAgIHZhbCByZTcgPSBDb24oQ29uKExldCgncycpLCBTdGFyKENvbihMZXQoJ2EnKSwgU3RhcihMZXQoJ2InKSkpKSksIExldCgnZScpKQogICAgLy8gYmEqYgogICAgdmFsIHJlOCA9IENvbihDb24oTGV0KCdiJyksIFN0YXIoTGV0KCdhJykpKSwgTGV0KCdiJykpCgogICAgdmFsIGkgICA9IGluc3RzX29mX3JlZ2V4KHJlOCkKICAgIHByaW50bG4obWFrZShpKSkKICB9Cn0K