test_pass_alpha_equal.py 21.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.
17
import tvm
18
import numpy as np
19
from tvm import relay
20 21 22 23 24 25 26 27
from tvm.relay import ir_pass

def alpha_equal(x, y):
    """
    Wrapper around alpha equality which ensures that
    the hash function respects equality.
    """
    return ir_pass.alpha_equal(x, y) and ir_pass.structural_hash(x) == ir_pass.structural_hash(y)
28

29
def test_tensor_type_alpha_equal():
30 31 32
    t1 = relay.TensorType((3, 4), "float32")
    t2 = relay.TensorType((3, 4), "float32")
    t3 = relay.TensorType((3, 4, 5), "float32")
33 34 35
    assert t1 == t2
    assert t1 != t3

36 37
    t1 = relay.TensorType((), "float32")
    t2 = relay.TensorType((), "float32")
38 39 40
    assert t1 == t2


41
def test_incomplete_type_alpha_equal():
42 43 44 45 46 47 48 49 50 51 52
    t1 = relay.IncompleteType(relay.Kind.Shape)
    t2 = relay.IncompleteType(relay.Kind.Type)
    t3 = relay.IncompleteType(relay.Kind.Type)

    # only equal when there is pointer equality
    assert t2 == t2
    assert t1 == t1
    assert t1 != t2
    assert t2 != t3


53
def test_type_param_alpha_equal():
54 55 56
    t1 = relay.TypeVar("v1", relay.Kind.Type)
    t2 = relay.TypeVar("v2", relay.Kind.Shape)
    t3 = relay.TypeVar("v3", relay.Kind.Type)
57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74

    # only pointer equality and eq_map allow equal params
    assert t1 == t1
    assert t2 == t2
    assert t1 != t2 # different kind
    assert t1 != t3 # not in eq_map

    # function types are the only way to put type params
    # in eq map
    ft1 = relay.FuncType(tvm.convert([]), t1, tvm.convert([t1]), tvm.convert([]))
    ft2 = relay.FuncType(tvm.convert([]), t3, tvm.convert([t3]), tvm.convert([]))
    # actually an invalid type because t2 is wrong kind
    ft3 = relay.FuncType(tvm.convert([]), t2, tvm.convert([t2]), tvm.convert([]))

    assert ft1 == ft2
    assert ft1 != ft3 # kinds still do not match


75
def test_func_type_alpha_equal():
76 77 78
    t1 = relay.TensorType((1, 2), "float32")
    t2 = relay.TensorType((1, 2, 3), "float32")

79 80 81 82
    tp1 = relay.TypeVar("v1", relay.Kind.Type)
    tp2 = relay.TypeVar("v2", relay.Kind.Type)
    tp3 = relay.TypeVar("v3", relay.Kind.Shape)
    tp4 = relay.TypeVar("v3", relay.Kind.Shape)
83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134

    broadcast = tvm.get_env_func("tvm.relay.type_relation.Broadcast")
    identity = tvm.get_env_func("tvm.relay.type_relation.Identity")

    tr1 = relay.TypeRelation(broadcast, tvm.convert([tp1, tp3]), 1, None)
    tr2 = relay.TypeRelation(broadcast, tvm.convert([tp2, tp4]), 1, None)
    tr3 = relay.TypeRelation(identity, tvm.convert([tp1, tp3]), 1, None)

    ft = relay.FuncType(tvm.convert([t1, t2]), tp1,
                         tvm.convert([tp1, tp3]),
                         tvm.convert([tr1]))
    translate_vars = relay.FuncType(tvm.convert([t1, t2]), tp1,
                         tvm.convert([tp2, tp4]),
                         tvm.convert([tr2]))
    assert ft == translate_vars

    different_args = relay.FuncType(tvm.convert([t1]), tp1,
                         tvm.convert([tp1, tp3]),
                         tvm.convert([tr1]))
    assert ft != different_args

    different_order = relay.FuncType(tvm.convert([t2, t1]), tp1,
                         tvm.convert([tp1, tp3]),
                         tvm.convert([tr1]))
    assert ft != different_order

    no_rel = relay.FuncType(tvm.convert([t1, t2]), tp1,
                         tvm.convert([tp1, tp3]),
                         tvm.convert([]))
    assert ft != no_rel

    more_vars = relay.FuncType(tvm.convert([t1, t2]), tp2,
                         tvm.convert([tp1, tp2, tp3]),
                         tvm.convert([tr1]))
    assert ft != more_vars

    all_the_vars = relay.FuncType(tvm.convert([t1, t2]), tp1,
                         tvm.convert([tp1, tp2, tp3, tp4]),
                         tvm.convert([tr1, tr2]))
    assert ft != all_the_vars

    different_rel = relay.FuncType(tvm.convert([t1, t2]), tp1,
                                   tvm.convert([tp1, tp3]),
                                   tvm.convert([tr3]))
    assert ft != different_rel

    more_rels = relay.FuncType(tvm.convert([t1, t2]), tp1,
                                   tvm.convert([tp1, tp3]),
                                   tvm.convert([tr1, tr3]))
    assert ft != more_rels


135
def test_tuple_type_alpha_equal():
136 137
    t1 = relay.TensorType((1, 2, 3), "float32")
    t2 = relay.TensorType((1, 2, 3, 4), "float32")
138 139
    tp1 = relay.TypeVar("v1", relay.Kind.Type)
    tp2 = relay.TypeVar("v2", relay.Kind.Type)
140 141 142 143 144 145 146 147 148 149 150 151 152

    tup1 = relay.TupleType(tvm.convert([t1, t2, tp1]))
    tup2 = relay.TupleType(tvm.convert([t1, t2, tp1]))
    tup3 = relay.TupleType(tvm.convert([t2, t1, tp1]))
    tup4 = relay.TupleType(tvm.convert([t1, t2, tp2]))

    # as long as types are alpha-equal and in same order,
    # tuples should be alpha-equal
    assert tup1 == tup2
    assert tup1 != tup3
    assert tup1 != tup4


153
def test_type_relation_alpha_equal():
154 155 156 157 158 159 160 161 162 163 164
    t1 = relay.TensorType((1, 2), "float32")
    t2 = relay.TensorType((1, 2, 3), "float32")
    t3 = relay.TensorType((1, 2, 3, 4), "float32")

    # functions are compared only by pointer equality so
    # we need to be sure to use the same pointers
    broadcast = tvm.get_env_func("tvm.relay.type_relation.Broadcast")
    identity = tvm.get_env_func("tvm.relay.type_relation.Identity")

    # attrs are also compared only by pointer equality
    attr1 = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4))
165 166
    attr1_same = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4))
    attr2 = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4,4))
167 168 169 170 171 172 173

    tr = relay.TypeRelation(broadcast, tvm.convert([t1, t2]), 1, attr1)
    same = relay.TypeRelation(broadcast, tvm.convert([t1, t2]), 1, attr1)
    diff_func = relay.TypeRelation(identity, tvm.convert([t1, t2]), 1, attr1)
    diff_order = relay.TypeRelation(broadcast, tvm.convert([t2, t1]), 1, attr1)
    diff_args = relay.TypeRelation(broadcast, tvm.convert([t2, t3]), 1, attr1)
    diff_attr = relay.TypeRelation(broadcast, tvm.convert([t1, t2]), 1, attr2)
174
    same_attr = relay.TypeRelation(broadcast, tvm.convert([t1, t2]), 1, attr1_same)
175 176 177 178 179 180 181 182 183 184

    bigger = relay.TypeRelation(identity, tvm.convert([t1, t3, t2]), 2, attr1)
    diff_num_inputs = relay.TypeRelation(identity, tvm.convert([t1, t3, t2]), 1, attr2)

    # func, number of args, input count, and order should be the same
    assert tr == same
    assert tr != diff_func
    assert tr != diff_order
    assert tr != diff_args
    assert tr != diff_attr
185
    assert tr == same_attr
186 187 188 189
    assert tr != bigger

    assert bigger != diff_num_inputs

190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212
def test_type_call_alpha_equal():
    h1 = relay.GlobalTypeVar("h1")
    h2 = relay.GlobalTypeVar("h2")
    t1 = relay.TensorType((1, 2), "float32")
    t2 = relay.TensorType((1, 2, 3), "float32")
    t3 = relay.TensorType((1, 2, 3, 4), "float32")
    t4 = relay.TensorType((), "float32")

    tc = relay.TypeCall(h1, [t1, t2, t3])
    same = relay.TypeCall(h1, [t1, t2, t3])

    different_func = relay.TypeCall(h2, [t1, t2, t3])
    different_arg = relay.TypeCall(h1, [t1, t2, t4])
    fewer_args = relay.TypeCall(h1, [t1, t2])
    more_args = relay.TypeCall(h1, [t1, t2, t3, t4])
    different_order_args = relay.TypeCall(h1, [t3, t2, t1])

    assert tc == same
    assert tc != different_func
    assert tc != fewer_args
    assert tc != more_args
    assert tc != different_order_args

213 214

def test_constant_alpha_equal():
215 216
    x = relay.const(1)
    y = relay.const(2)
217 218
    assert alpha_equal(x, x)
    assert not alpha_equal(x, y)
219
    assert alpha_equal(x, relay.const(1))
220 221 222 223 224 225 226 227 228 229 230


def test_var_alpha_equal():
    v1 = relay.Var("v1")
    v2 = relay.Var("v2")

    # normally only pointer equality
    assert alpha_equal(v1, v1)
    assert not alpha_equal(v1, v2)

    # let node allows for setting the eq_map
231 232 233
    l1 = relay.Let(v1, relay.const(1), v1)
    l2 = relay.Let(v2, relay.const(1), v2)
    l3 = relay.Let(v1, relay.const(1), v2)
234 235 236 237

    assert alpha_equal(l1, l2)
    assert not alpha_equal(l1, l3)

238 239 240 241 242 243 244 245
    # type annotations
    tt1 = relay.TensorType([], "int32")
    tt2 = relay.TensorType([], "int32")
    tt3 = relay.TensorType([], "int64")
    v3 = relay.Var("v3", tt1)
    v4 = relay.Var("v4", tt2)
    v5 = relay.Var("v5", tt3)

246 247 248
    l4 = relay.Let(v3, relay.const(1), v3)
    l5 = relay.Let(v4, relay.const(1), v4)
    l6 = relay.Let(v5, relay.const(1), v5)
249 250 251 252 253 254 255 256

    # same annotations
    assert alpha_equal(l4, l5)
    # different annotations
    assert not alpha_equal(l4, l6)
    # one null annotation
    assert not alpha_equal(l1, l4)

257 258 259 260 261 262 263 264 265 266 267

def test_global_var_alpha_equal():
    v1 = relay.GlobalVar("v1")
    v2 = relay.GlobalVar("v2")

    # only pointer equality suffices (smoke test)
    assert alpha_equal(v1, v1)
    assert not alpha_equal(v1, v2)


def test_tuple_alpha_equal():
268
    v0 = relay.Var("v0")
269 270 271 272 273 274
    v1 = relay.Var("v1")
    v2 = relay.Var("v2")

    # unit value is a valid tuple
    assert alpha_equal(relay.Tuple([]), relay.Tuple([]))

275 276
    tup = relay.Tuple([v0, relay.const(2), relay.const(3), relay.Tuple([relay.const(4)])])
    same = relay.Tuple([v0, relay.const(2), relay.const(3), relay.Tuple([relay.const(4)])])
277 278 279 280

    assert alpha_equal(tup, same)

    # use the eq_map
281 282


283
    let_tup = relay.Let(v1, tup, v1)
284
    let_mapped = relay.Let(v2, relay.Tuple([v0, relay.const(2), relay.const(3),
285
                                            relay.Tuple([relay.const(4)])]),
286
                           v2)
287

288 289
    assert alpha_equal(let_tup, let_mapped)

290
    more_fields = relay.Tuple([v1, relay.const(2), relay.const(3), relay.Tuple([relay.const(4)]), v2])
291 292
    assert not alpha_equal(tup, more_fields)

293
    fewer_fields = relay.Tuple([v1, relay.const(2), relay.const(3)])
294 295
    assert not alpha_equal(tup, fewer_fields)

296 297
    different_end = relay.Tuple([v1, relay.const(2), relay.const(3),
                           relay.Tuple([relay.const(5)])])
298 299
    assert not alpha_equal(tup, different_end)

300 301
    different_start = relay.Tuple([v2, relay.const(2), relay.const(3),
                                 relay.Tuple([relay.const(4)])])
302 303
    assert not alpha_equal(tup, different_start)

304 305
    longer_at_end = relay.Tuple([v1, relay.const(2), relay.const(3),
                                 relay.Tuple([relay.const(4), relay.const(5)])])
306 307 308
    assert not alpha_equal(tup, longer_at_end)


309 310 311 312 313 314
def test_tuple_get_item_alpha_equal():
    x = relay.Var('x')
    y = relay.Var('y')
    assert not alpha_equal(relay.TupleGetItem(x, 1), relay.TupleGetItem(y, 1))
    assert not alpha_equal(relay.TupleGetItem(x, 1), relay.TupleGetItem(x, 2))
    assert alpha_equal(relay.TupleGetItem(x, 1), relay.TupleGetItem(x, 1))
315

316 317 318 319 320 321

def test_function_alpha_equal():
    tt1 = relay.TensorType((1, 2, 3), "float32")
    tt2 = relay.TensorType((4, 5, 6), "int8")
    tt3 = relay.TupleType([tt1, tt2])

322 323 324 325 326 327
    v1 = relay.Var("v1", tt1)
    v2 = relay.Var("v2", tt2)
    v3 = relay.Var("v3", tt3)
    v4 = relay.Var("v4", tt2)
    vret = relay.Constant(tvm.nd.array(np.ones(1)))

328 329 330 331
    tp1 = relay.TypeVar("tp1", relay.Kind.Type)
    tp2 = relay.TypeVar("tp2", relay.Kind.Type)
    tp3 = relay.TypeVar("tp3", relay.Kind.Shape)
    tp4 = relay.TypeVar("tp4", relay.Kind.Shape)
332

333
    basic_args = [relay.Var("v3", tt1), relay.Var("v4", tt2)]
334 335
    basic_tps = [tp1, tp2]

336 337 338
    func = relay.Function([v1, v2], v1,
                          tt2, basic_tps)
    mapped = relay.Function(basic_args, basic_args[0], tt2, basic_tps)
339 340
    assert alpha_equal(func, mapped)

341
    fewer_params = relay.Function([relay.Var("v4", tt2)], v4, tt2, basic_tps)
342 343
    assert not alpha_equal(func, fewer_params)

344 345
    more_params = relay.Function([relay.Var("v3", tt1),
                                  relay.Var("v4", tt2),
346
                                  relay.Var("v2", tt2)], v4, tt2, basic_tps)
347 348
    assert not alpha_equal(func, more_params)

349 350
    params_unordered = relay.Function([v2, v1], v1,
                                      tt2, basic_tps)
351 352
    assert not alpha_equal(func, params_unordered)

353 354
    params_mismatch = relay.Function([v1, v3], v1,
                                     tt2, basic_tps)
355 356 357
    assert not alpha_equal(func, params_mismatch)

    # also would not typecheck
358
    ret_type_mismatch = relay.Function(basic_args, v4, tt1, basic_tps)
359 360 361
    assert not alpha_equal(func, ret_type_mismatch)

    # also mis-typed
362
    different_body = relay.Function(basic_args, v3, tt2, basic_tps)
363 364
    assert not alpha_equal(func, different_body)

365
    fewer_type_params = relay.Function(basic_args, v4, tt2, [tp1])
366 367
    assert not alpha_equal(func, fewer_type_params)

368
    more_type_params = relay.Function(basic_args, v4, tt2, [tp1, tp2, tp3])
369 370
    assert not alpha_equal(func, more_type_params)

371
    type_params_unordered = relay.Function(basic_args, v4, tt2, [tp2, tp1])
372 373
    assert not alpha_equal(func, type_params_unordered)

374
    different_type_params = relay.Function(basic_args, v4, tt2, [tp3, tp4])
375 376 377
    assert not alpha_equal(func, different_type_params)

    # a well-typed example that also differs in body, ret type, and type params
378
    tupled_example = relay.Function(basic_args, relay.Tuple([v3, v4]), tt3)
379 380
    assert not alpha_equal(func, tupled_example)

381 382 383 384 385 386 387 388
    # nullable
    no_ret_type = relay.Function(basic_args, v4, None, [tp1, tp2])
    # both null
    assert alpha_equal(no_ret_type, no_ret_type)
    # one null
    assert not alpha_equal(func, no_ret_type)
    assert not alpha_equal(no_ret_type, func)

389 390 391 392 393 394 395

def test_call_alpha_equal():
    v1 = relay.Var("v1")
    v2 = relay.Var("v2")

    # attrs are compared only by pointer equality
    attr1 = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4))
396 397
    attr1_same = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4))
    attr2 = tvm.make.node("attrs.TestAttrs", name="attr", padding=(3,4,4))
398 399 400 401

    tt1 = relay.TensorType((1, 2, 3), "float32")
    tt2 = relay.TensorType((), "int8")

402
    basic_args = [relay.const(1), relay.const(2), v2, relay.Tuple([])]
403 404 405

    # manually writing out args to ensure that args does not rely on
    # pointer equality
406
    call = relay.Call(v1, [relay.const(1), relay.const(2), v2, relay.Tuple([])],
407 408 409 410 411 412 413
                      attr1, [tt1])
    same = relay.Call(v1, basic_args, attr1, [tt1])
    assert alpha_equal(call, same)

    different_fn = relay.Call(v2, basic_args, attr1, [tt1])
    assert not alpha_equal(call, different_fn)

414
    fewer_args = relay.Call(v1, [relay.const(1), relay.const(2), v2], attr1, [tt1])
415 416
    assert not alpha_equal(call, fewer_args)

417
    reordered_args = relay.Call(v1, [relay.const(2), relay.const(1),
418 419 420
                                     relay.Tuple([]), v2], attr1, [tt1])
    assert not alpha_equal(call, reordered_args)

421
    different_args = relay.Call(v1, [relay.const(1), relay.const(2), relay.const(3)],
422 423 424
                                attr1, [tt1])
    assert not alpha_equal(call, different_args)

425 426
    more_args = relay.Call(v1, [relay.const(1), relay.const(2), v2, relay.Tuple([]),
                                relay.const(3), relay.const(4)], attr1, [tt1])
427 428 429 430 431
    assert not alpha_equal(call, more_args)

    different_attrs = relay.Call(v1, basic_args, attr2, [tt1])
    assert not alpha_equal(call, different_attrs)

432 433 434
    same_attrs = relay.Call(v1, basic_args, attr1_same, [tt1])
    assert alpha_equal(call, same_attrs)

435 436 437 438 439 440 441 442 443 444 445
    no_type_args = relay.Call(v1, basic_args, attr1)
    assert not alpha_equal(call, no_type_args)

    more_type_args = relay.Call(v1, basic_args, attr1, [tt1, tt2])
    assert not alpha_equal(call, more_type_args)

    different_type_arg = relay.Call(v1, basic_args, attr1, [tt2])
    assert not alpha_equal(call, different_type_arg)


def test_let_alpha_equal():
446 447
    tt1 = relay.TensorType((), "float32")
    tt2 = relay.TensorType((), "int8")
448
    v1 = relay.Var("v1")
449
    v1_wtype = relay.Var("v1", tt1)
450 451 452
    v2 = relay.Var("v2")
    v3 = relay.Var("v3")

453 454
    let = relay.Let(v1, relay.const(2), v1)
    mapped = relay.Let(v2, relay.const(2), v2)
455 456
    assert alpha_equal(let, mapped)

457
    mismatched_var = relay.Let(v2, relay.const(2), v3)
458 459
    assert not alpha_equal(let, mismatched_var)

460
    different_value = relay.Let(v2, relay.const(3), v2)
461 462
    assert not alpha_equal(let, different_value)

463
    different_body = relay.Let(v2, relay.const(3), relay.const(12))
464 465 466
    assert not alpha_equal(let, different_body)

    # specified types must match
467

468 469
    let_with_type = relay.Let(v1_wtype, relay.const(2), v1_wtype)
    same_type = relay.Let(v1_wtype, relay.const(2), v1_wtype)
470 471
    assert alpha_equal(let_with_type, same_type)
    assert not alpha_equal(let, let_with_type)
472
    v2 = relay.Var("v1", tt2)
473
    different_type = relay.Let(v2, relay.const(2), v2)
474 475 476 477 478 479 480
    assert not alpha_equal(let_with_type, different_type)


def test_if_alpha_equal():
    v1 = relay.Var("v1")
    v2 = relay.Var("v2")

481 482
    if_sample = relay.If(v1, relay.const(1), relay.Tuple([relay.const(2), relay.const(3)]))
    same = relay.If(v1, relay.const(1), relay.Tuple([relay.const(2), relay.const(3)]))
483 484
    assert alpha_equal(if_sample, same)

485
    different_cond = relay.If(v2, relay.const(1), relay.Tuple([relay.const(2), relay.const(3)]))
486 487
    assert not alpha_equal(if_sample, different_cond)

488
    different_true = relay.If(v1, relay.const(2), relay.Tuple([relay.const(2), relay.const(3)]))
489 490
    assert not alpha_equal(if_sample, different_true)

491
    different_false = relay.If(v1, relay.const(1), relay.Tuple([]))
492 493 494
    assert not alpha_equal(if_sample, different_false)


495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567
def test_constructor_alpha_equal():
    # smoke test: it should be pointer equality
    mod = relay.Module()
    p = relay.prelude.Prelude(mod)

    assert alpha_equal(p.nil, p.nil)
    assert alpha_equal(p.cons, p.cons)
    assert not alpha_equal(p.nil, p.cons)


def test_match_alpha_equal():
    mod = relay.Module()
    p = relay.prelude.Prelude(mod)

    x = relay.Var('x')
    y = relay.Var('y')
    nil_case = relay.Clause(relay.PatternConstructor(p.nil), p.nil())
    cons_case = relay.Clause(relay.PatternConstructor(p.cons,
                                                      [relay.PatternVar(x),
                                                       relay.PatternVar(y)]),
                       p.cons(x, y))

    z = relay.Var('z')
    a = relay.Var('a')
    equivalent_cons = relay.Clause(relay.PatternConstructor(p.cons,
                                                            [relay.PatternVar(z),
                                                             relay.PatternVar(a)]),
                                   p.cons(z, a))

    data = p.cons(p.z(), p.cons(p.z(), p.nil()))

    match = relay.Match(data, [nil_case, cons_case])
    equivalent = relay.Match(data, [nil_case, equivalent_cons])
    empty = relay.Match(data, [])
    no_cons = relay.Match(data, [nil_case])
    no_nil = relay.Match(data, [cons_case])
    different_data = relay.Match(p.nil(), [nil_case, cons_case])
    different_order = relay.Match(data, [cons_case, nil_case])
    different_nil = relay.Match(data, [
        relay.Clause(relay.PatternConstructor(p.nil), p.cons(p.nil(), p.nil())),
        cons_case
    ])
    different_cons = relay.Match(data, [
        nil_case,
        relay.Clause(relay.PatternConstructor(p.cons,
                                              [relay.PatternWildcard(),
                                               relay.PatternWildcard()]),
                     p.nil())
    ])
    another_case = relay.Match(data, [
        nil_case,
        cons_case,
        relay.Clause(relay.PatternWildcard(), p.nil())
    ])
    wrong_constructors = relay.Match(data, [
        relay.Clause(relay.PatternConstructor(p.z), p.nil()),
        relay.Clause(relay.PatternConstructor(p.s, [relay.PatternVar(x)]),
                     p.cons(x, p.nil()))
    ])

    assert alpha_equal(match, match)
    assert alpha_equal(match, equivalent)
    assert not alpha_equal(match, no_cons)
    assert not alpha_equal(match, no_nil)
    assert not alpha_equal(match, empty)
    assert not alpha_equal(match, different_data)
    assert not alpha_equal(match, different_order)
    assert not alpha_equal(match, different_nil)
    assert not alpha_equal(match, different_cons)
    assert not alpha_equal(match, another_case)
    assert not alpha_equal(match, wrong_constructors)


568 569 570 571 572 573 574 575 576 577
def test_op_alpha_equal():
    # only checks names
    op1 = relay.op.get("add")
    op2 = relay.op.get("add")
    assert alpha_equal(op1, op2)

    op3 = relay.op.get("take")
    assert not alpha_equal(op1, op3)


578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598
def test_graph_equal():
    x = relay.var("x")

    y0 = relay.add(x, x)
    z0 = relay.add(y0, y0)

    y1 = relay.add(x, x)
    z1 = relay.add(y1, y1)

    z3 = relay.add(relay.add(x, x), relay.add(x, x))

    assert alpha_equal(z0, z1)

    # z3's dataflow format is different from z0
    # z0 is computed from a common y0 node
    # Relay view them as different programs
    # Check the difference in the text format.
    assert not alpha_equal(z0, z3)



599
if __name__ == "__main__":
600 601
    test_tensor_type_alpha_equal()
    test_incomplete_type_alpha_equal()
602
    test_constant_alpha_equal()
603 604 605
    test_func_type_alpha_equal()
    test_tuple_type_alpha_equal()
    test_type_relation_alpha_equal()
606
    test_type_call_alpha_equal()
607 608 609
    test_constant_alpha_equal()
    test_global_var_alpha_equal()
    test_tuple_alpha_equal()
610
    test_tuple_get_item_alpha_equal()
611 612 613 614
    test_function_alpha_equal()
    test_call_alpha_equal()
    test_let_alpha_equal()
    test_if_alpha_equal()
615 616
    test_constructor_alpha_equal()
    test_match_alpha_equal()
617
    test_op_alpha_equal()
618
    test_var_alpha_equal()
619
    test_graph_equal()