constant_propagate.go

package main

import (
	"fmt"
)

type Expression struct {
	OP byte
	X  interface{}
	Y  interface{}
}

type Set struct {
	data      []Expression
	index     map[Expression]struct{}
	tombstone []bool
}

func (s *Set) Append(e Expression) bool {
	if _, ok := s.index[e]; ok {
		return false
	}
	s.data = append(s.data, e)
	s.index[e] = struct{}{}
	s.tombstone = append(s.tombstone, false)
	return true
}

func (s *Set) GC() {
	idx := 0
	for i := 0; i < len(s.data); i++ {
		if !s.tombstone[i] {
			s.data[idx] = s.data[i]
			idx++
		}
		s.tombstone[i] = false
	}
	s.data = s.data[:idx]
	s.tombstone = s.tombstone[:idx]
}

type Pattern int

type FVar struct {
	fn int
	v  string
}

const (
	varTag = 1 + iota
	constTag
	fvarTag
)

var (
	varEQConst  = makePattern('=', varTag, constTag)
	constEQVar  = makePattern('=', constTag, varTag)
	varEQVar    = makePattern('=', varTag, varTag)
	varGTConst  = makePattern('>', varTag, constTag)
	varLTConst  = makePattern('<', varTag, constTag)
	fvarLTConst = makePattern('<', fvarTag, constTag)
)

func makePattern(op byte, x, y int) Pattern {
	return Pattern((int(op) << 16) | (x << 8) | y)
}

func (e *Expression) Pattern() Pattern {
	var x, y int
	switch e.X.(type) {
	case int:
		x = constTag
	case string:
		x = varTag
	case FVar:
		x = fvarTag
	}
	switch e.Y.(type) {
	case int:
		y = constTag
	case string:
		y = varTag
	case FVar:
		x = fvarTag
	}
	return makePattern(e.OP, x, y)
}

func PropagateConstant(input []Expression) []Expression {
	var exprs Set
	exprs.index = make(map[Expression]struct{})
	for _, v := range input {
		exprs.Append(v)
	}

	fixPoint(&exprs)
	exprs.GC()
	return exprs.data
}

func fixPoint(exprs *Set) {
	var count, snapshot int
	for count != len(exprs.data) {
		count = len(exprs.data)
		for i := 0; i < len(exprs.data) && !exprs.tombstone[i]; i++ {
			for j := snapshot; j < len(exprs.data) && !exprs.tombstone[j]; j++ {
				if i == j {
					continue
				}
				solve(i, j, exprs)
			}
		}
		snapshot = len(exprs.data)
	}
	return
}

func solve(i, j int, exprs *Set) {
	rule := exprs.data[i]
	switch rule.Pattern() {
	case varEQConst:
		solveVarEQConst(rule.X.(string), rule.Y.(int), j, exprs)
	case varGTConst:
		solveVarGTConst(rule.X.(string), rule.Y.(int), j, exprs)
	}
	return
}

func solveVarEQConst(Var string, Const int, ith int, exprs *Set) {
	expr := exprs.data[ith]
	// Substitute.
	if X, ok := expr.X.(string); ok && X == Var {
		// x = const, x op ? => const op ?
		expr.X = Const
	} else if Y, ok := expr.Y.(string); ok && Y == Var {
		// x = const, ? op x => ? op const
		expr.Y = Const
	}

	if expr.Pattern() == fvarLTConst {
		// f(x) < const, x = const => x = const
		fvar := expr.X.(FVar)
		if fvar.v == Var {
			if add(Const) < expr.Y.(int) {
				// always true
				exprs.tombstone[ith] = true
			} else {
				panic("false")
			}
		}
	}

	if expr.Pattern() == constEQVar {
		// Change "const = var" to "var = const"
		expr.X, expr.Y = expr.Y, expr.X
	}
	exprs.Append(expr)
}

func solveVarGTConst(Var string, Const int, ith int, exprs *Set) {
	var expr Expression = exprs.data[ith]
	if expr.Pattern() == varEQVar {
		x := expr.X.(string)
		y := expr.Y.(string)
		// x > const, x = y  => y > const
		if x == Var {
			newRule := Expression{OP: '>', X: expr.Y, Y: Const}
			exprs.Append(newRule)
		}
		// y > const, x = y => x > const
		if y == Var {
			newRule := Expression{OP: '>', X: expr.X, Y: Const}
			exprs.Append(newRule)
		}
		return
	}

	// x > const1, x > const2  => x > max(const1, const2)
	if expr.Pattern() == varGTConst && expr.X.(string) == Var {
		if Const >= expr.Y.(int) {
			exprs.tombstone[ith] = true
			return
		}
		exprs.Append(expr)
		return
	}

	// x > const1, x < const2, const1 >= const2 => false
	if expr.Pattern() == varLTConst && expr.X.(string) == Var {
		if Const >= expr.Y.(int) {
			// return []Expression{{OP: 'f'}}, nil
			panic("!!!")
		}
	}
	exprs.Append(expr)
	return
}

func add(x int) int {
	return x + 10
}

func main() {
	// input := []Expression{
	// 	{'>', "a", 3},
	// 	{'>', "b", 5},
	// 	{'=', "a", "b"},
	// }
	// input := []Expression{
	// 	{'=', "a", 1},
	// 	{'=', "a", "c"},
	// 	{'>', "b", "c"},
	// 	{'=', "b", "d"},
	// 	{'>', "c", "d"},
	// 	{'=', "d", "f"},
	// }
	input := []Expression{
		{'<', FVar{0, "x"}, 13},
		{'=', "y", "x"},
		{'=', "x", 2},
	}

	output := PropagateConstant(input)
	fmt.Println(output)
}