Optimize resolving

[emil14]

Write benchmarks first

Related to #173

		"type param with same name as type in scope": func() testcase { // t1<int>, {t1<t3>=t2<t3>, t2<t>=t3<t>, t3<t>=vec<t>, vec<t>, int }
			return testcase{
				expr: h.Inst("t1", h.Inst("int")),
				scope: map[string]ts.Def{
					"t1": h.Def( // t1<t3> = t2<t3>
						h.Inst("t2", h.Inst("t3")),
						h.Param("t3", ts.Expr{}),
					),
					"t2": h.Def( // t2<t> = t3<t>
						h.Inst("t3", h.Inst("t")),
						h.Param("t", ts.Expr{}),
					),
					"t3": h.Def( // t3<t> = vec<t>
						h.Inst("vec", h.Inst("t")),
						h.Param("t", ts.Expr{}),
					),
					"vec": h.Def( // vec<t> (base type)
						ts.Expr{},
						h.Param("t", ts.Expr{}),
					),
					"int": h.Def(ts.Expr{}), // int
				},
				base: h.Base("vec", "int"),
				exprValidator: func(v *MockexpressionValidator) {
					v.EXPECT().
						Validate(h.Inst("t1", h.Inst("int"))).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("int")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t2", h.Inst("t3"))).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t3")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("int")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t3", h.Inst("t"))).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t3")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("int")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("vec", h.Inst("t"))).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("t3")).
						Return(nil)

					v.EXPECT().
						Validate(h.Inst("int")).
						Return(nil)

					// v.EXPECT().Validate(gomock.Any()).AnyTimes()
				},
				want:    h.Inst("vec", h.Inst("int")),
				wantErr: nil,
			}
		},

As we can see there's multiple Validate calls that could be avoided in theory. The reason of this is recursive calls. This would be even worse if those types had constraints. With bigger trees there will be many unnecessary calls.

[emil14]

Map of resolved types

Introduce new argument that is a map (~cache) that will be updated any time we resolve some argument. That map should be expanded with both expression and it's alias (type parameter). This could help to avoid unnecessary recursive calls.

v.EXPECT().
	Validate(h.Inst("t1", h.Inst("int"))). // first call with t1<int>
	Return(nil)

v.EXPECT().
	Validate(h.Inst("int")). // first recursive call with expr's argument. after return, remember that both int and t3 (because t3 mapped onto int) are resolved
	Return(nil)

v.EXPECT().
	Validate(h.Inst("t2", h.Inst("t3"))). // second recursive call with expr's body. 
	Return(nil)

v.EXPECT().
	Validate(h.Inst("t3")). // this should not happened because of map's lookup
	Return(nil)

Problems

Expressions are not hashable

In theory could be solved with custom hashing (think of .String())

UPD: same strings (expression structures?) can (probably?) mean different things depending on (execution/resolving) context. That is probably a problem/

How to differ between normal types from scope and type-parameters

Could be resolved with dividing cache into two separate caches. This statement should be investigated.

[emil14]

Substitution in-place

Kinda did this in b7a5432