branch.mx raw

   1  package iskra
   2  
   3  const (
   4  	TritEnd = 0
   5  
   6  	// Level 1: declaration kind
   7  	BranchType = 1
   8  	BranchFunc = 2
   9  	BranchData = 3
  10  
  11  	// Level 2 under BranchType
  12  	SubField  = 1
  13  	SubMethod = 2
  14  	SubEmbed  = 3
  15  
  16  	// Level 2 under BranchFunc
  17  	SubStatement  = 1
  18  	SubExpression = 2
  19  	SubControl    = 3
  20  
  21  	// Level 2 under BranchData
  22  	SubConst  = 1
  23  	SubVar    = 2
  24  	SubImport = 3
  25  )
  26  
  27  type TritPath uint32
  28  
  29  func (p TritPath) Trit(i int) uint8 {
  30  	return uint8((p >> (uint(i) * 2)) & 0x3)
  31  }
  32  
  33  func (p TritPath) Depth() int {
  34  	for i := 0; i < 8; i++ {
  35  		if p.Trit(i) == TritEnd {
  36  			return i
  37  		}
  38  	}
  39  	return 8
  40  }
  41  
  42  func (p TritPath) Branch() uint8 {
  43  	return p.Trit(0)
  44  }
  45  
  46  func MakeTritPath(trits ...uint8) TritPath {
  47  	var p TritPath
  48  	for i, t := range trits {
  49  		if i >= 8 {
  50  			break
  51  		}
  52  		p |= TritPath(t&0x3) << (uint(i) * 2)
  53  	}
  54  	return p
  55  }
  56  
  57  // KindToTritPath maps a NodeKind to its trit-path in the code lattice.
  58  func KindToTritPath(kind NodeKind) TritPath {
  59  	switch {
  60  	// Type branch
  61  	case kind.Has(KindField):
  62  		return MakeTritPath(BranchType, SubField)
  63  	case kind.Has(KindMethod):
  64  		return MakeTritPath(BranchType, SubMethod)
  65  	case kind.Has(KindType):
  66  		return MakeTritPath(BranchType)
  67  
  68  	// Func branch
  69  	case kind.Has(KindControl):
  70  		return MakeTritPath(BranchFunc, SubControl)
  71  	case kind.Has(KindExpr):
  72  		return MakeTritPath(BranchFunc, SubExpression)
  73  	case kind.Has(KindStmt):
  74  		return MakeTritPath(BranchFunc, SubStatement)
  75  	case kind.Has(KindFunc):
  76  		return MakeTritPath(BranchFunc)
  77  
  78  	// Data branch
  79  	case kind.Has(KindConst):
  80  		return MakeTritPath(BranchData, SubConst)
  81  	case kind.Has(KindVar):
  82  		return MakeTritPath(BranchData, SubVar)
  83  	case kind.Has(KindImport), kind.Has(KindPkg):
  84  		return MakeTritPath(BranchData, SubImport)
  85  
  86  	default:
  87  		return MakeTritPath()
  88  	}
  89  }
  90  
  91  func (m *MetaEntry) SetTritPath(p TritPath) {
  92  	m.Extra[0] = byte(p)
  93  	m.Extra[1] = byte(p >> 8)
  94  	m.Extra[2] = byte(p >> 16)
  95  	m.Extra[3] = byte(p >> 24)
  96  }
  97  
  98  func (m *MetaEntry) GetTritPath() TritPath {
  99  	return TritPath(m.Extra[0]) |
 100  		TritPath(m.Extra[1])<<8 |
 101  		TritPath(m.Extra[2])<<16 |
 102  		TritPath(m.Extra[3])<<24
 103  }
 104  
 105  // TritPathDistance measures distance between two trit-paths on the lattice.
 106  // Returns -1 if either path is unassigned.
 107  func TritPathDistance(a, b TritPath) int {
 108  	da := a.Depth()
 109  	db := b.Depth()
 110  	if da == 0 || db == 0 {
 111  		return -1
 112  	}
 113  
 114  	shared := 0
 115  	limit := da
 116  	if db < limit {
 117  		limit = db
 118  	}
 119  	for i := 0; i < limit; i++ {
 120  		if a.Trit(i) != b.Trit(i) {
 121  			break
 122  		}
 123  		shared++
 124  	}
 125  
 126  	return (da - shared) + (db - shared)
 127  }
 128