func InferCaprefType(re *syntax.Regexp, n int) Type {
	group := getCaptureGroup(re, n)
	if group == nil {
		return None
	}
	if group.Op != syntax.OpAlternate {
		return inferGroupType(group)
	}
	subType := Type(Undef)
	for _, sub := range group.Sub {
		subType = LeastUpperBound(subType, inferGroupType(sub))
	}
	return subType
}
inferCaprefType determines a type for the nth capturing group in re, based on contents
of that capture group.
package types
import (
	"errors"
	"fmt"
	"regexp/syntax"
	"strings"
	"sync"
	"github.com/golang/glog"
)
type Type interface {
	Root() Type
	String() string
}
func Equals(t1, t2 Type) bool {
	t1, t2 = t1.Root(), t2.Root()
	switch t1 := t1.(type) {
	case *Variable:
		r2, ok := t2.(*Variable)
		if !ok {
			return occursInType(t1, t2)
		}
		return t1 == r2
	case *Operator:
		t2, ok := t2.(*Operator)
		if !ok {
			return false
		}
		if t1.Name != t2.Name {
			return false
		}
		if len(t1.Args) != len(t2.Args) {
			return false
		}
		for i := range t1.Args {
			if !Equals(t1.Args[i], t2.Args[2]) {
				return false
			}
		}
		return true
	}
	return true
}
var (
	nextVariableIDMu sync.Mutex
	nextVariableID   int
)
type Variable struct {
	ID int
	instanceMu sync.RWMutex
	Instance   Type
}
func NewVariable() *Variable {
	nextVariableIDMu.Lock()
	id := nextVariableID
	nextVariableID++
	nextVariableIDMu.Unlock()
	return &Variable{ID: id}
}
func (t *Variable) Root() Type {
	t.instanceMu.Lock()
	defer t.instanceMu.Unlock()
	if t.Instance == nil {
		return t
	}
	r := t.Instance.Root()
	t.Instance = r
	return r
}
func (t *Variable) String() string {
	t.instanceMu.RLock()
	defer t.instanceMu.RUnlock()
	if t.Instance != nil {
		return t.Instance.String()
	}
	return fmt.Sprintf("typeVar%d", t.ID)
}
func (t *Variable) SetInstance(t1 Type) {
	t.instanceMu.Lock()
	defer t.instanceMu.Unlock()
	t.Instance = t1
}
type Operator struct {
	Name string
	Args []Type
}
func (t *Operator) Root() Type {
	return t
}
func (t *Operator) String() (s string) {
	switch l := len(t.Args); {
	case l < 2:
		s = t.Name
		for _, a := range t.Args {
			s += " " + a.String()
		}
	default:
		s = t.Args[0].String()
		for _, a := range t.Args[1:] {
			s += t.Name + a.String()
		}
	}
	return s
}
func Function(args ...Type) *Operator {
	return &Operator{"→", args}
}
func IsFunction(t Type) bool {
	if v, ok := t.(*Operator); ok {
		return v.Name == "→"
	}
	return false
}
func Dimension(args ...Type) *Operator {
	return &Operator{"⨯", args}
}
func IsDimension(t Type) bool {
	if v, ok := t.(*Operator); ok {
		return v.Name == "⨯"
	}
	return false
}
func IsComplete(t Type) bool {
	switch v := t.Root().(type) {
	case *Variable:
		return false
	case *Operator:
		for _, a := range v.Args {
			if !IsComplete(a) {
				return false
			}
		}
		return true
	}
	return false
}
var (
	Undef   = &Operator{"Undef", []Type{}}
	Error   = &Operator{"Error", []Type{}}
	None    = &Operator{"None", []Type{}}
	Bool    = &Operator{"Bool", []Type{}}
	Int     = &Operator{"Int", []Type{}}
	Float   = &Operator{"Float", []Type{}}
	String  = &Operator{"String", []Type{}}
	Pattern = &Operator{"Pattern", []Type{}}
	Buckets = &Operator{"Buckets", []Type{}}
)
var Builtins = map[string]Type{
	"int":         Function(NewVariable(), Int),
	"bool":        Function(NewVariable(), Bool),
	"float":       Function(NewVariable(), Float),
	"string":      Function(NewVariable(), String),
	"timestamp":   Function(Int),
	"len":         Function(String, Int),
	"settime":     Function(Int, None),
	"strptime":    Function(String, String, None),
	"strtol":      Function(String, Int, Int),
	"tolower":     Function(String, String),
	"getfilename": Function(String),
	"subst":       Function(Pattern, String, String, String),
}
func FreshType(t Type) Type {
	mappings := make(map[*Variable]*Variable)
	var freshRec func(Type) Type
	freshRec = func(tp Type) Type {
		p := tp.Root()
		switch p1 := p.(type) {
		case *Variable:
			if _, ok := mappings[p1]; !ok {
				mappings[p1] = NewVariable()
			}
			return mappings[p1]
		case *Operator:
			args := make([]Type, 0, len(p1.Args))
			for _, arg := range p1.Args {
				args = append(args, freshRec(arg))
			}
			return &Operator{p1.Name, args}
		default:
			glog.V(1).Infof("Unexpected type p1: %v", p1)
		}
		return tp
	}
	return freshRec(t)
}
func occursIn(v *Variable, types []Type) bool {
	for _, t2 := range types {
		if occursInType(v, t2) {
			return true
		}
	}
	return false
}
func occursInType(v *Variable, t2 Type) bool {
	root := t2.Root()
	if Equals(root, v) {
		return true
	}
	if to, ok := root.(*Operator); ok {
		return occursIn(v, to.Args)
	}
	return false
}
type TypeError struct {
	expected Type
	received Type
}
var ErrRecursiveUnification = errors.New("recursive unification error")
func (e *TypeError) Error() string {
	var estr, rstr string
	if IsComplete(e.expected) {
		estr = e.expected.String()
	} else {
		estr = "incomplete type"
	}
	if IsComplete(e.received) {
		rstr = e.received.String()
	} else {
		rstr = "incomplete type"
	}
	glog.V(2).Infof("type mismatch: expected %q received %q", e.expected, e.received)
	return fmt.Sprintf("type mismatch; expected %s received %s", estr, rstr)
}
func Unify(a, b Type) error {
	glog.V(2).Infof("Unifying %v and %v", a, b)
	a1, b1 := a.Root(), b.Root()
	switch a2 := a1.(type) {
	case *Variable:
		switch b2 := b1.(type) {
		case *Variable:
			if a2.ID != b2.ID {
				glog.V(2).Infof("Making %q type %q", a2, b1)
				a2.SetInstance(b1)
				return nil
			}
		case *Operator:
			if occursInType(a2, b2) {
				return fmt.Errorf("%w on %v and %v", ErrRecursiveUnification, a2, b2)
			}
			glog.V(2).Infof("Making %q type %q", a2, b1)
			a2.SetInstance(b1)
			return nil
		}
	case *Operator:
		switch b2 := b1.(type) {
		case *Variable:
			err := Unify(b, a)
			if err != nil {
				var e *TypeError
				if errors.As(err, &e) {
					return &TypeError{e.received, e.expected}
				}
			}
			return err
		case *Operator:
			if len(a2.Args) != len(b2.Args) {
				return &TypeError{a2, b2}
			}
			if a2.Name != b2.Name {
				t := LeastUpperBound(a, b)
				glog.V(2).Infof("Got LUB = %q", t)
				if t == Error {
					return &TypeError{a2, b2}
				}
				return nil
			}
			for i, argA := range a2.Args {
				err := Unify(argA, b2.Args[i])
				if err != nil {
					return err
				}
			}
		}
	}
	return nil
}
func LeastUpperBound(a, b Type) Type {
	a1, b1 := a.Root(), b.Root()
	glog.V(2).Infof("Computing LUB(%q, %q)", a1, b1)
	if Equals(a1, b1) {
		return a1
	}
	if _, ok := a1.(*Variable); ok {
		return b1
	}
	if _, ok := b1.(*Variable); ok {
		return a1
	}
	if Equals(a1, Undef) {
		return b1
	}
	if Equals(b1, Undef) {
		return a1
	}
	if (Equals(a1, Float) && Equals(b1, Int)) ||
		(Equals(b1, Float) && Equals(a1, Int)) {
		return Float
	}
	if (Equals(a1, String) && Equals(b1, Int)) ||
		(Equals(b1, String) && Equals(a1, Int)) ||
		(Equals(a1, String) && Equals(b1, Float)) ||
		(Equals(b1, String) && Equals(a1, Float)) {
		return String
	}
	if (Equals(a1, Pattern) && Equals(b1, Bool)) ||
		(Equals(a1, Bool) && Equals(b1, Pattern)) {
		return Bool
	}
	if (Equals(a1, Bool) && Equals(b1, Int)) ||
		(Equals(a1, Int) && Equals(b1, Bool)) {
		return Int
	}
	if (Equals(a1, String) && Equals(b1, Pattern)) ||
		(Equals(a1, Pattern) && Equals(b1, String)) {
		return Pattern
	}
	if (Equals(a1, Pattern) && Equals(b1, Int)) ||
		(Equals(a1, Int) && Equals(b1, Pattern)) {
		return Bool
	}
	return Error
}