Source file src/oss.terrastruct.com/d2/d2ir/d2ir.go

Documentation: oss.terrastruct.com/d2/d2ir

     1  // Package d2ir implements a tree data structure to keep track of the resolved value of D2
     2  // keys.
     3  package d2ir
     4  
     5  import (
     6  	"errors"
     7  	"fmt"
     8  	"strings"
     9  
    10  	"oss.terrastruct.com/util-go/go2"
    11  
    12  	"oss.terrastruct.com/d2/d2ast"
    13  	"oss.terrastruct.com/d2/d2format"
    14  	"oss.terrastruct.com/d2/d2graph"
    15  	"oss.terrastruct.com/d2/d2parser"
    16  	"oss.terrastruct.com/d2/d2target"
    17  )
    18  
    19  // Most errors returned by a node should be created with d2parser.Errorf
    20  // to indicate the offending AST node.
    21  type Node interface {
    22  	node()
    23  	Copy(newParent Node) Node
    24  	Parent() Node
    25  	Primary() *Scalar
    26  	Map() *Map
    27  	Equal(n2 Node) bool
    28  
    29  	AST() d2ast.Node
    30  	fmt.Stringer
    31  
    32  	LastRef() Reference
    33  	LastPrimaryRef() Reference
    34  	LastPrimaryKey() *d2ast.Key
    35  }
    36  
    37  var _ Node = &Scalar{}
    38  var _ Node = &Field{}
    39  var _ Node = &Edge{}
    40  var _ Node = &Array{}
    41  var _ Node = &Map{}
    42  
    43  type Value interface {
    44  	Node
    45  	value()
    46  }
    47  
    48  var _ Value = &Scalar{}
    49  var _ Value = &Array{}
    50  var _ Value = &Map{}
    51  
    52  type Composite interface {
    53  	Node
    54  	Value
    55  	composite()
    56  }
    57  
    58  var _ Composite = &Array{}
    59  var _ Composite = &Map{}
    60  
    61  func (n *Scalar) node() {}
    62  func (n *Field) node()  {}
    63  func (n *Edge) node()   {}
    64  func (n *Array) node()  {}
    65  func (n *Map) node()    {}
    66  
    67  func (n *Scalar) Parent() Node { return n.parent }
    68  func (n *Field) Parent() Node  { return n.parent }
    69  func (n *Edge) Parent() Node   { return n.parent }
    70  func (n *Array) Parent() Node  { return n.parent }
    71  func (n *Map) Parent() Node    { return n.parent }
    72  
    73  func (n *Scalar) Primary() *Scalar { return n }
    74  func (n *Field) Primary() *Scalar  { return n.Primary_ }
    75  func (n *Edge) Primary() *Scalar   { return n.Primary_ }
    76  func (n *Array) Primary() *Scalar  { return nil }
    77  func (n *Map) Primary() *Scalar    { return nil }
    78  
    79  func (n *Scalar) Map() *Map { return nil }
    80  func (n *Field) Map() *Map {
    81  	if n == nil {
    82  		return nil
    83  	}
    84  	if n.Composite == nil {
    85  		return nil
    86  	}
    87  	return n.Composite.Map()
    88  }
    89  func (n *Edge) Map() *Map {
    90  	if n == nil {
    91  		return nil
    92  	}
    93  	return n.Map_
    94  }
    95  func (n *Array) Map() *Map { return nil }
    96  func (n *Map) Map() *Map   { return n }
    97  
    98  func (n *Scalar) value() {}
    99  func (n *Array) value()  {}
   100  func (n *Map) value()    {}
   101  
   102  func (n *Array) composite() {}
   103  func (n *Map) composite()   {}
   104  
   105  func (n *Scalar) String() string { return d2format.Format(n.AST()) }
   106  func (n *Field) String() string  { return d2format.Format(n.AST()) }
   107  func (n *Edge) String() string   { return d2format.Format(n.AST()) }
   108  func (n *Array) String() string  { return d2format.Format(n.AST()) }
   109  func (n *Map) String() string    { return d2format.Format(n.AST()) }
   110  
   111  func (n *Scalar) LastRef() Reference { return parentRef(n) }
   112  func (n *Map) LastRef() Reference    { return parentRef(n) }
   113  func (n *Array) LastRef() Reference  { return parentRef(n) }
   114  
   115  func (n *Scalar) LastPrimaryRef() Reference { return parentPrimaryRef(n) }
   116  func (n *Map) LastPrimaryRef() Reference    { return parentPrimaryRef(n) }
   117  func (n *Array) LastPrimaryRef() Reference  { return parentPrimaryRef(n) }
   118  
   119  func (n *Scalar) LastPrimaryKey() *d2ast.Key { return parentPrimaryKey(n) }
   120  func (n *Map) LastPrimaryKey() *d2ast.Key    { return parentPrimaryKey(n) }
   121  func (n *Array) LastPrimaryKey() *d2ast.Key  { return parentPrimaryKey(n) }
   122  
   123  type Reference interface {
   124  	reference()
   125  	// Most specific AST node for the reference.
   126  	AST() d2ast.Node
   127  	Primary() bool
   128  	Context() *RefContext
   129  	// Result of a glob in Context or from above.
   130  	DueToGlob() bool
   131  	DueToLazyGlob() bool
   132  }
   133  
   134  var _ Reference = &FieldReference{}
   135  var _ Reference = &EdgeReference{}
   136  
   137  func (r *FieldReference) reference()           {}
   138  func (r *EdgeReference) reference()            {}
   139  func (r *FieldReference) Context() *RefContext { return r.Context_ }
   140  func (r *EdgeReference) Context() *RefContext  { return r.Context_ }
   141  func (r *FieldReference) DueToGlob() bool      { return r.DueToGlob_ }
   142  func (r *EdgeReference) DueToGlob() bool       { return r.DueToGlob_ }
   143  func (r *FieldReference) DueToLazyGlob() bool  { return r.DueToLazyGlob_ }
   144  func (r *EdgeReference) DueToLazyGlob() bool   { return r.DueToLazyGlob_ }
   145  
   146  type Scalar struct {
   147  	parent Node
   148  	Value  d2ast.Scalar `json:"value"`
   149  }
   150  
   151  func (s *Scalar) Copy(newParent Node) Node {
   152  	tmp := *s
   153  	s = &tmp
   154  
   155  	s.parent = newParent
   156  	return s
   157  }
   158  
   159  func (s *Scalar) Equal(n2 Node) bool {
   160  	s2 := n2.(*Scalar)
   161  	if _, ok := s.Value.(d2ast.String); ok {
   162  		if _, ok = s2.Value.(d2ast.String); ok {
   163  			return s.Value.ScalarString() == s2.Value.ScalarString()
   164  		}
   165  	}
   166  	return s.Value.Type() == s2.Value.Type() && s.Value.ScalarString() == s2.Value.ScalarString()
   167  }
   168  
   169  type Map struct {
   170  	parent Node
   171  	Fields []*Field `json:"fields"`
   172  	Edges  []*Edge  `json:"edges"`
   173  
   174  	globs []*globContext
   175  }
   176  
   177  func (m *Map) initRoot() {
   178  	m.parent = &Field{
   179  		Name: "root",
   180  		References: []*FieldReference{{
   181  			Context_: &RefContext{
   182  				ScopeMap: m,
   183  			},
   184  		}},
   185  	}
   186  }
   187  
   188  func (m *Map) Copy(newParent Node) Node {
   189  	tmp := *m
   190  	m = &tmp
   191  
   192  	m.parent = newParent
   193  	pfields := m.Fields
   194  	m.Fields = make([]*Field, 0, len(pfields))
   195  	for _, f := range pfields {
   196  		m.Fields = append(m.Fields, f.Copy(m).(*Field))
   197  	}
   198  	m.Edges = append([]*Edge(nil), m.Edges...)
   199  	for i := range m.Edges {
   200  		m.Edges[i] = m.Edges[i].Copy(m).(*Edge)
   201  	}
   202  	if m.parent == nil {
   203  		m.initRoot()
   204  	}
   205  	return m
   206  }
   207  
   208  // CopyBase copies the map m without layers/scenarios/steps.
   209  func (m *Map) CopyBase(newParent Node) *Map {
   210  	if m == nil {
   211  		return (&Map{}).Copy(newParent).(*Map)
   212  	}
   213  
   214  	layers := m.DeleteField("layers")
   215  	scenarios := m.DeleteField("scenarios")
   216  	steps := m.DeleteField("steps")
   217  
   218  	m2 := m.Copy(newParent).(*Map)
   219  	if layers != nil {
   220  		m.Fields = append(m.Fields, layers)
   221  	}
   222  	if scenarios != nil {
   223  		m.Fields = append(m.Fields, scenarios)
   224  	}
   225  	if steps != nil {
   226  		m.Fields = append(m.Fields, steps)
   227  	}
   228  	return m2
   229  }
   230  
   231  // Root reports whether the Map is the root of the D2 tree.
   232  func (m *Map) Root() bool {
   233  	// m.parent exists even on the root map as we store the root AST in
   234  	// m.parent.References[0].Context.Map for reporting error messages about the whole IR.
   235  	// Or if otherwise needed.
   236  	f, ok := m.parent.(*Field)
   237  	if !ok {
   238  		return false
   239  	}
   240  	return f.Root()
   241  }
   242  
   243  func (f *Field) Root() bool {
   244  	return f.parent == nil
   245  }
   246  
   247  type BoardKind string
   248  
   249  const (
   250  	BoardLayer    BoardKind = "layer"
   251  	BoardScenario BoardKind = "scenario"
   252  	BoardStep     BoardKind = "step"
   253  )
   254  
   255  // NodeBoardKind reports whether n represents the root of a board.
   256  // n should be *Field or *Map
   257  func NodeBoardKind(n Node) BoardKind {
   258  	var f *Field
   259  	switch n := n.(type) {
   260  	case *Field:
   261  		if n.parent == nil {
   262  			return BoardLayer
   263  		}
   264  		f = ParentField(n)
   265  	case *Map:
   266  		var ok bool
   267  		f, ok = n.parent.(*Field)
   268  		if !ok {
   269  			return ""
   270  		}
   271  		if f.Root() {
   272  			return BoardLayer
   273  		}
   274  		f = ParentField(f)
   275  	}
   276  	if f == nil {
   277  		return ""
   278  	}
   279  	switch f.Name {
   280  	case "layers":
   281  		return BoardLayer
   282  	case "scenarios":
   283  		return BoardScenario
   284  	case "steps":
   285  		return BoardStep
   286  	default:
   287  		return ""
   288  	}
   289  }
   290  
   291  type Field struct {
   292  	// *Map.
   293  	parent Node
   294  
   295  	Name string `json:"name"`
   296  
   297  	// Primary_ to avoid clashing with Primary(). We need to keep it exported for
   298  	// encoding/json to marshal it so cannot prefix _ instead.
   299  	Primary_  *Scalar   `json:"primary,omitempty"`
   300  	Composite Composite `json:"composite,omitempty"`
   301  
   302  	References []*FieldReference `json:"references,omitempty"`
   303  }
   304  
   305  func (f *Field) Copy(newParent Node) Node {
   306  	tmp := *f
   307  	f = &tmp
   308  
   309  	f.parent = newParent
   310  	f.References = append([]*FieldReference(nil), f.References...)
   311  	if f.Primary_ != nil {
   312  		f.Primary_ = f.Primary_.Copy(f).(*Scalar)
   313  	}
   314  	if f.Composite != nil {
   315  		f.Composite = f.Composite.Copy(f).(Composite)
   316  	}
   317  	return f
   318  }
   319  
   320  func (f *Field) LastPrimaryRef() Reference {
   321  	for i := len(f.References) - 1; i >= 0; i-- {
   322  		if f.References[i].Primary() {
   323  			return f.References[i]
   324  		}
   325  	}
   326  	return nil
   327  }
   328  
   329  func (f *Field) LastPrimaryKey() *d2ast.Key {
   330  	fr := f.LastPrimaryRef()
   331  	if fr == nil {
   332  		return nil
   333  	}
   334  	return fr.(*FieldReference).Context_.Key
   335  }
   336  
   337  func (f *Field) LastRef() Reference {
   338  	return f.References[len(f.References)-1]
   339  }
   340  
   341  type EdgeID struct {
   342  	SrcPath  []string `json:"src_path"`
   343  	SrcArrow bool     `json:"src_arrow"`
   344  
   345  	DstPath  []string `json:"dst_path"`
   346  	DstArrow bool     `json:"dst_arrow"`
   347  
   348  	// If nil, then any EdgeID with equal src/dst/arrows matches.
   349  	Index *int `json:"index"`
   350  	Glob  bool `json:"glob"`
   351  }
   352  
   353  func NewEdgeIDs(k *d2ast.Key) (eida []*EdgeID) {
   354  	for _, ke := range k.Edges {
   355  		eid := &EdgeID{
   356  			SrcPath:  ke.Src.IDA(),
   357  			SrcArrow: ke.SrcArrow == "<",
   358  			DstPath:  ke.Dst.IDA(),
   359  			DstArrow: ke.DstArrow == ">",
   360  		}
   361  		if k.EdgeIndex != nil {
   362  			eid.Index = k.EdgeIndex.Int
   363  			eid.Glob = k.EdgeIndex.Glob
   364  		}
   365  		eida = append(eida, eid)
   366  	}
   367  	return eida
   368  }
   369  
   370  func (eid *EdgeID) Copy() *EdgeID {
   371  	tmp := *eid
   372  	eid = &tmp
   373  
   374  	eid.SrcPath = append([]string(nil), eid.SrcPath...)
   375  	eid.DstPath = append([]string(nil), eid.DstPath...)
   376  	return eid
   377  }
   378  
   379  func (eid *EdgeID) Match(eid2 *EdgeID) bool {
   380  	if eid.Index != nil && eid2.Index != nil {
   381  		if *eid.Index != *eid2.Index {
   382  			return false
   383  		}
   384  	}
   385  
   386  	if len(eid.SrcPath) != len(eid2.SrcPath) {
   387  		return false
   388  	}
   389  	if eid.SrcArrow != eid2.SrcArrow {
   390  		return false
   391  	}
   392  	for i, s := range eid.SrcPath {
   393  		if !strings.EqualFold(s, eid2.SrcPath[i]) {
   394  			return false
   395  		}
   396  	}
   397  
   398  	if len(eid.DstPath) != len(eid2.DstPath) {
   399  		return false
   400  	}
   401  	if eid.DstArrow != eid2.DstArrow {
   402  		return false
   403  	}
   404  	for i, s := range eid.DstPath {
   405  		if !strings.EqualFold(s, eid2.DstPath[i]) {
   406  			return false
   407  		}
   408  	}
   409  
   410  	return true
   411  }
   412  
   413  // resolve resolves both underscores and commons in eid.
   414  // It returns the new eid, containing map adjusted for underscores and common ida.
   415  func (eid *EdgeID) resolve(m *Map) (_ *EdgeID, _ *Map, common []string, _ error) {
   416  	eid = eid.Copy()
   417  	maxUnderscores := go2.Max(countUnderscores(eid.SrcPath), countUnderscores(eid.DstPath))
   418  	for i := 0; i < maxUnderscores; i++ {
   419  		if eid.SrcPath[0] == "_" {
   420  			eid.SrcPath = eid.SrcPath[1:]
   421  		} else {
   422  			mf := ParentField(m)
   423  			eid.SrcPath = append([]string{mf.Name}, eid.SrcPath...)
   424  		}
   425  		if eid.DstPath[0] == "_" {
   426  			eid.DstPath = eid.DstPath[1:]
   427  		} else {
   428  			mf := ParentField(m)
   429  			eid.DstPath = append([]string{mf.Name}, eid.DstPath...)
   430  		}
   431  		m = ParentMap(m)
   432  		if m == nil {
   433  			return nil, nil, nil, errors.New("invalid underscore")
   434  		}
   435  	}
   436  
   437  	for len(eid.SrcPath) > 1 && len(eid.DstPath) > 1 {
   438  		if !strings.EqualFold(eid.SrcPath[0], eid.DstPath[0]) || eid.SrcPath[0] == "*" {
   439  			return eid, m, common, nil
   440  		}
   441  		common = append(common, eid.SrcPath[0])
   442  		eid.SrcPath = eid.SrcPath[1:]
   443  		eid.DstPath = eid.DstPath[1:]
   444  	}
   445  
   446  	return eid, m, common, nil
   447  }
   448  
   449  type Edge struct {
   450  	// *Map
   451  	parent Node
   452  
   453  	ID *EdgeID `json:"edge_id"`
   454  
   455  	Primary_ *Scalar `json:"primary,omitempty"`
   456  	Map_     *Map    `json:"map,omitempty"`
   457  
   458  	References []*EdgeReference `json:"references,omitempty"`
   459  }
   460  
   461  func (e *Edge) Copy(newParent Node) Node {
   462  	tmp := *e
   463  	e = &tmp
   464  
   465  	e.parent = newParent
   466  	e.References = append([]*EdgeReference(nil), e.References...)
   467  	if e.Primary_ != nil {
   468  		e.Primary_ = e.Primary_.Copy(e).(*Scalar)
   469  	}
   470  	if e.Map_ != nil {
   471  		e.Map_ = e.Map_.Copy(e).(*Map)
   472  	}
   473  	return e
   474  }
   475  
   476  func (e *Edge) LastPrimaryRef() Reference {
   477  	for i := len(e.References) - 1; i >= 0; i-- {
   478  		fr := e.References[i]
   479  		if fr.Context_.Key.EdgeKey == nil && !fr.DueToLazyGlob() {
   480  			return fr
   481  		}
   482  	}
   483  	return nil
   484  }
   485  
   486  func (e *Edge) LastPrimaryKey() *d2ast.Key {
   487  	er := e.LastPrimaryRef()
   488  	if er == nil {
   489  		return nil
   490  	}
   491  	return er.(*EdgeReference).Context_.Key
   492  }
   493  
   494  func (e *Edge) LastRef() Reference {
   495  	return e.References[len(e.References)-1]
   496  }
   497  
   498  type Array struct {
   499  	parent Node
   500  	Values []Value `json:"values"`
   501  }
   502  
   503  func (a *Array) Copy(newParent Node) Node {
   504  	tmp := *a
   505  	a = &tmp
   506  
   507  	a.parent = newParent
   508  	a.Values = append([]Value(nil), a.Values...)
   509  	for i := range a.Values {
   510  		a.Values[i] = a.Values[i].Copy(a).(Value)
   511  	}
   512  	return a
   513  }
   514  
   515  type FieldReference struct {
   516  	String  d2ast.String   `json:"string"`
   517  	KeyPath *d2ast.KeyPath `json:"key_path"`
   518  
   519  	Context_       *RefContext `json:"context"`
   520  	DueToGlob_     bool        `json:"due_to_glob"`
   521  	DueToLazyGlob_ bool        `json:"due_to_lazy_glob"`
   522  }
   523  
   524  // Primary returns true if the Value in Context.Key.Value corresponds to the Field
   525  // represented by String.
   526  func (fr *FieldReference) Primary() bool {
   527  	if fr.KeyPath == fr.Context_.Key.Key {
   528  		return len(fr.Context_.Key.Edges) == 0 && fr.KeyPathIndex() == len(fr.KeyPath.Path)-1
   529  	} else if fr.KeyPath == fr.Context_.Key.EdgeKey {
   530  		return len(fr.Context_.Key.Edges) == 1 && fr.KeyPathIndex() == len(fr.KeyPath.Path)-1
   531  	}
   532  	return false
   533  }
   534  
   535  func (fr *FieldReference) KeyPathIndex() int {
   536  	for i, sb := range fr.KeyPath.Path {
   537  		if sb.Unbox() == fr.String {
   538  			return i
   539  		}
   540  	}
   541  	panic("d2ir.KeyReference.KeyPathIndex: String not in KeyPath?")
   542  }
   543  
   544  func (fr *FieldReference) EdgeDest() bool {
   545  	return fr.KeyPath == fr.Context_.Edge.Dst
   546  }
   547  
   548  func (fr *FieldReference) InEdge() bool {
   549  	return fr.Context_.Edge != nil
   550  }
   551  
   552  func (fr *FieldReference) AST() d2ast.Node {
   553  	if fr.String == nil {
   554  		// Root map.
   555  		return fr.Context_.Scope
   556  	}
   557  	return fr.String
   558  }
   559  
   560  type EdgeReference struct {
   561  	Context_       *RefContext `json:"context"`
   562  	DueToGlob_     bool        `json:"due_to_glob"`
   563  	DueToLazyGlob_ bool        `json:"due_to_lazy_glob"`
   564  }
   565  
   566  func (er *EdgeReference) AST() d2ast.Node {
   567  	return er.Context_.Edge
   568  }
   569  
   570  // Primary returns true if the Value in Context.Key.Value corresponds to the *Edge
   571  // represented by Context.Edge
   572  func (er *EdgeReference) Primary() bool {
   573  	return len(er.Context_.Key.Edges) == 1 && er.Context_.Key.EdgeKey == nil
   574  }
   575  
   576  type RefContext struct {
   577  	Edge     *d2ast.Edge `json:"edge"`
   578  	Key      *d2ast.Key  `json:"key"`
   579  	Scope    *d2ast.Map  `json:"-"`
   580  	ScopeMap *Map        `json:"-"`
   581  	ScopeAST *d2ast.Map  `json:"-"`
   582  }
   583  
   584  func (rc *RefContext) Copy() *RefContext {
   585  	tmp := *rc
   586  	return &tmp
   587  }
   588  
   589  func (rc *RefContext) EdgeIndex() int {
   590  	for i, e := range rc.Key.Edges {
   591  		if e == rc.Edge {
   592  			return i
   593  		}
   594  	}
   595  	return -1
   596  }
   597  
   598  func (rc *RefContext) Equal(rc2 *RefContext) bool {
   599  	// We intentionally ignore edges here because the same glob can produce multiple RefContexts that should be treated  the same with only the edge as the difference.
   600  	// Same with ScopeMap.
   601  	return rc.Key.Equals(rc2.Key) && rc.Scope == rc2.Scope && rc.ScopeAST == rc2.ScopeAST
   602  }
   603  
   604  func (m *Map) FieldCountRecursive() int {
   605  	if m == nil {
   606  		return 0
   607  	}
   608  	acc := len(m.Fields)
   609  	for _, f := range m.Fields {
   610  		if f.Map() != nil {
   611  			acc += f.Map().FieldCountRecursive()
   612  		}
   613  	}
   614  	for _, e := range m.Edges {
   615  		if e.Map_ != nil {
   616  			acc += e.Map_.FieldCountRecursive()
   617  		}
   618  	}
   619  	return acc
   620  }
   621  
   622  func (m *Map) IsContainer() bool {
   623  	if m == nil {
   624  		return false
   625  	}
   626  	for _, f := range m.Fields {
   627  		_, isReserved := d2graph.ReservedKeywords[f.Name]
   628  		if !isReserved {
   629  			return true
   630  		}
   631  	}
   632  	return false
   633  }
   634  
   635  func (m *Map) EdgeCountRecursive() int {
   636  	if m == nil {
   637  		return 0
   638  	}
   639  	acc := len(m.Edges)
   640  	for _, f := range m.Fields {
   641  		if f.Map() != nil {
   642  			acc += f.Map().EdgeCountRecursive()
   643  		}
   644  	}
   645  	for _, e := range m.Edges {
   646  		if e.Map_ != nil {
   647  			acc += e.Map_.EdgeCountRecursive()
   648  		}
   649  	}
   650  	return acc
   651  }
   652  
   653  func (m *Map) GetClassMap(name string) *Map {
   654  	root := RootMap(m)
   655  	classes := root.Map().GetField("classes")
   656  	if classes != nil && classes.Map() != nil {
   657  		class := classes.Map().GetField(name)
   658  		if class != nil && class.Map() != nil {
   659  			return class.Map()
   660  		}
   661  	}
   662  	return nil
   663  }
   664  
   665  func (m *Map) GetField(ida ...string) *Field {
   666  	for len(ida) > 0 && ida[0] == "_" {
   667  		m = ParentMap(m)
   668  		if m == nil {
   669  			return nil
   670  		}
   671  	}
   672  	return m.getField(ida)
   673  }
   674  
   675  func (m *Map) getField(ida []string) *Field {
   676  	if len(ida) == 0 {
   677  		return nil
   678  	}
   679  
   680  	s := ida[0]
   681  	rest := ida[1:]
   682  
   683  	if s == "_" {
   684  		return nil
   685  	}
   686  
   687  	for _, f := range m.Fields {
   688  		if !strings.EqualFold(f.Name, s) {
   689  			continue
   690  		}
   691  		if len(rest) == 0 {
   692  			return f
   693  		}
   694  		if f.Map() != nil {
   695  			return f.Map().getField(rest)
   696  		}
   697  	}
   698  	return nil
   699  }
   700  
   701  // EnsureField is a bit of a misnomer. It's more of a Query/Ensure combination function at this point.
   702  func (m *Map) EnsureField(kp *d2ast.KeyPath, refctx *RefContext, create bool, c *compiler) ([]*Field, error) {
   703  	i := 0
   704  	for kp.Path[i].Unbox().ScalarString() == "_" {
   705  		m = ParentMap(m)
   706  		if m == nil {
   707  			return nil, d2parser.Errorf(kp.Path[i].Unbox(), "invalid underscore: no parent")
   708  		}
   709  		if i+1 == len(kp.Path) {
   710  			return nil, d2parser.Errorf(kp.Path[i].Unbox(), "field key must contain more than underscores")
   711  		}
   712  		i++
   713  	}
   714  
   715  	var gctx *globContext
   716  	if refctx != nil && refctx.Key.HasGlob() && c != nil {
   717  		gctx = c.getGlobContext(refctx)
   718  	}
   719  
   720  	var fa []*Field
   721  	err := m.ensureField(i, kp, refctx, create, gctx, c, &fa)
   722  	if len(fa) > 0 && c != nil && len(c.globRefContextStack) == 0 {
   723  		for _, gctx2 := range c.globContexts() {
   724  			old := c.lazyGlobBeingApplied
   725  			c.lazyGlobBeingApplied = true
   726  			c.compileKey(gctx2.refctx)
   727  			c.lazyGlobBeingApplied = old
   728  		}
   729  	}
   730  	return fa, err
   731  }
   732  
   733  func (m *Map) ensureField(i int, kp *d2ast.KeyPath, refctx *RefContext, create bool, gctx *globContext, c *compiler, fa *[]*Field) error {
   734  	filter := func(f *Field, passthrough bool) bool {
   735  		if gctx != nil {
   736  			var ks string
   737  			if refctx.Key.HasTripleGlob() {
   738  				ks = d2format.Format(d2ast.MakeKeyPath(IDA(f)))
   739  			} else {
   740  				ks = d2format.Format(d2ast.MakeKeyPath(BoardIDA(f)))
   741  			}
   742  			if !kp.HasGlob() {
   743  				if !passthrough {
   744  					gctx.appliedFields[ks] = struct{}{}
   745  				}
   746  				return true
   747  			}
   748  			// For globs with edges, we only ignore duplicate fields if the glob is not at the terminal of the keypath, the glob is on the common key or the glob is on the edge key. And only for globs with edge indexes.
   749  			lastEl := kp.Path[len(kp.Path)-1]
   750  			if len(refctx.Key.Edges) == 0 || lastEl.UnquotedString == nil || len(lastEl.UnquotedString.Pattern) == 0 || kp == refctx.Key.Key || kp == refctx.Key.EdgeKey {
   751  				if _, ok := gctx.appliedFields[ks]; ok {
   752  					return false
   753  				}
   754  			}
   755  			if !passthrough {
   756  				gctx.appliedFields[ks] = struct{}{}
   757  			}
   758  		}
   759  		return true
   760  	}
   761  	faAppend := func(fa2 ...*Field) {
   762  		for _, f := range fa2 {
   763  			if filter(f, false) {
   764  				*fa = append(*fa, f)
   765  			}
   766  		}
   767  	}
   768  
   769  	us, ok := kp.Path[i].Unbox().(*d2ast.UnquotedString)
   770  	if ok && us.Pattern != nil {
   771  		fa2, ok := m.multiGlob(us.Pattern)
   772  		if ok {
   773  			if i == len(kp.Path)-1 {
   774  				faAppend(fa2...)
   775  			} else {
   776  				for _, f := range fa2 {
   777  					if !filter(f, true) {
   778  						continue
   779  					}
   780  					if f.Map() == nil {
   781  						f.Composite = &Map{
   782  							parent: f,
   783  						}
   784  					}
   785  					err := f.Map().ensureField(i+1, kp, refctx, create, gctx, c, fa)
   786  					if err != nil {
   787  						return err
   788  					}
   789  				}
   790  			}
   791  			return nil
   792  		}
   793  		for _, f := range m.Fields {
   794  			if matchPattern(f.Name, us.Pattern) {
   795  				if i == len(kp.Path)-1 {
   796  					faAppend(f)
   797  				} else {
   798  					if !filter(f, true) {
   799  						continue
   800  					}
   801  					if f.Map() == nil {
   802  						f.Composite = &Map{
   803  							parent: f,
   804  						}
   805  					}
   806  					err := f.Map().ensureField(i+1, kp, refctx, create, gctx, c, fa)
   807  					if err != nil {
   808  						return err
   809  					}
   810  				}
   811  			}
   812  		}
   813  		return nil
   814  	}
   815  
   816  	head := kp.Path[i].Unbox().ScalarString()
   817  
   818  	if _, ok := d2graph.ReservedKeywords[strings.ToLower(head)]; ok {
   819  		head = strings.ToLower(head)
   820  		if _, ok := d2graph.CompositeReservedKeywords[head]; !ok && i < len(kp.Path)-1 {
   821  			return d2parser.Errorf(kp.Path[i].Unbox(), fmt.Sprintf(`"%s" must be the last part of the key`, head))
   822  		}
   823  	}
   824  
   825  	if head == "_" {
   826  		return d2parser.Errorf(kp.Path[i].Unbox(), `parent "_" can only be used in the beginning of paths, e.g. "_.x"`)
   827  	}
   828  
   829  	if head == "classes" && NodeBoardKind(m) == "" {
   830  		return d2parser.Errorf(kp.Path[i].Unbox(), "%s is only allowed at a board root", head)
   831  	}
   832  
   833  	if findBoardKeyword(head) != -1 && NodeBoardKind(m) == "" {
   834  		return d2parser.Errorf(kp.Path[i].Unbox(), "%s is only allowed at a board root", head)
   835  	}
   836  
   837  	for _, f := range m.Fields {
   838  		if !strings.EqualFold(f.Name, head) {
   839  			continue
   840  		}
   841  
   842  		// Don't add references for fake common KeyPath from trimCommon in CreateEdge.
   843  		if refctx != nil {
   844  			f.References = append(f.References, &FieldReference{
   845  				String:         kp.Path[i].Unbox(),
   846  				KeyPath:        kp,
   847  				Context_:       refctx,
   848  				DueToGlob_:     len(c.globRefContextStack) > 0,
   849  				DueToLazyGlob_: c.lazyGlobBeingApplied,
   850  			})
   851  		}
   852  
   853  		if i+1 == len(kp.Path) {
   854  			faAppend(f)
   855  			return nil
   856  		}
   857  		if !filter(f, true) {
   858  			return nil
   859  		}
   860  		if _, ok := f.Composite.(*Array); ok {
   861  			return d2parser.Errorf(kp.Path[i].Unbox(), "cannot index into array")
   862  		}
   863  		if f.Map() == nil {
   864  			f.Composite = &Map{
   865  				parent: f,
   866  			}
   867  		}
   868  		return f.Map().ensureField(i+1, kp, refctx, create, gctx, c, fa)
   869  	}
   870  
   871  	if !create {
   872  		return nil
   873  	}
   874  	shape := ParentShape(m)
   875  	if _, ok := d2graph.ReservedKeywords[strings.ToLower(head)]; !ok && len(c.globRefContextStack) > 0 {
   876  		if shape == d2target.ShapeClass || shape == d2target.ShapeSQLTable {
   877  			return nil
   878  		}
   879  	}
   880  	f := &Field{
   881  		parent: m,
   882  		Name:   head,
   883  	}
   884  	defer func() {
   885  		if i < kp.FirstGlob() {
   886  			return
   887  		}
   888  		for _, grefctx := range c.globRefContextStack {
   889  			var ks string
   890  			if grefctx.Key.HasTripleGlob() {
   891  				ks = d2format.Format(d2ast.MakeKeyPath(IDA(f)))
   892  			} else {
   893  				ks = d2format.Format(d2ast.MakeKeyPath(BoardIDA(f)))
   894  			}
   895  			gctx2 := c.getGlobContext(grefctx)
   896  			gctx2.appliedFields[ks] = struct{}{}
   897  		}
   898  	}()
   899  	// Don't add references for fake common KeyPath from trimCommon in CreateEdge.
   900  	if refctx != nil {
   901  		f.References = append(f.References, &FieldReference{
   902  			String:         kp.Path[i].Unbox(),
   903  			KeyPath:        kp,
   904  			Context_:       refctx,
   905  			DueToGlob_:     len(c.globRefContextStack) > 0,
   906  			DueToLazyGlob_: c.lazyGlobBeingApplied,
   907  		})
   908  	}
   909  	if !filter(f, true) {
   910  		return nil
   911  	}
   912  	m.Fields = append(m.Fields, f)
   913  	if i+1 == len(kp.Path) {
   914  		faAppend(f)
   915  		return nil
   916  	}
   917  	if f.Composite == nil {
   918  		f.Composite = &Map{
   919  			parent: f,
   920  		}
   921  	}
   922  	return f.Map().ensureField(i+1, kp, refctx, create, gctx, c, fa)
   923  }
   924  
   925  func (m *Map) DeleteEdge(eid *EdgeID) *Edge {
   926  	if eid == nil {
   927  		return nil
   928  	}
   929  
   930  	for i, e := range m.Edges {
   931  		if e.ID.Match(eid) {
   932  			m.Edges = append(m.Edges[:i], m.Edges[i+1:]...)
   933  			return e
   934  		}
   935  	}
   936  	return nil
   937  }
   938  
   939  func (m *Map) DeleteField(ida ...string) *Field {
   940  	if len(ida) == 0 {
   941  		return nil
   942  	}
   943  
   944  	s := ida[0]
   945  	rest := ida[1:]
   946  
   947  	for i, f := range m.Fields {
   948  		if !strings.EqualFold(f.Name, s) {
   949  			continue
   950  		}
   951  		if len(rest) == 0 {
   952  			for _, fr := range f.References {
   953  				for _, e := range m.Edges {
   954  					for _, er := range e.References {
   955  						if er.Context_ == fr.Context_ {
   956  							m.DeleteEdge(e.ID)
   957  							break
   958  						}
   959  					}
   960  				}
   961  			}
   962  			m.Fields = append(m.Fields[:i], m.Fields[i+1:]...)
   963  
   964  			// If a field was deleted from a keyword-holder keyword and that holder is empty,
   965  			// then that holder becomes meaningless and should be deleted too
   966  			parent := ParentField(f)
   967  			for keywordHolder := range d2graph.ReservedKeywordHolders {
   968  				if parent != nil && parent.Name == keywordHolder && len(parent.Map().Fields) == 0 {
   969  					keywordHolderParentMap := ParentMap(parent)
   970  					for i, f := range keywordHolderParentMap.Fields {
   971  						if f.Name == keywordHolder {
   972  							keywordHolderParentMap.Fields = append(keywordHolderParentMap.Fields[:i], keywordHolderParentMap.Fields[i+1:]...)
   973  							break
   974  						}
   975  					}
   976  				}
   977  			}
   978  			return f
   979  		}
   980  		if f.Map() != nil {
   981  			return f.Map().DeleteField(rest...)
   982  		}
   983  	}
   984  	return nil
   985  }
   986  
   987  func (m *Map) GetEdges(eid *EdgeID, refctx *RefContext, c *compiler) []*Edge {
   988  	if refctx != nil {
   989  		var gctx *globContext
   990  		if refctx.Key.HasGlob() && c != nil {
   991  			gctx = c.ensureGlobContext(refctx)
   992  		}
   993  		var ea []*Edge
   994  		m.getEdges(eid, refctx, gctx, &ea)
   995  		return ea
   996  	}
   997  
   998  	eid, m, common, err := eid.resolve(m)
   999  	if err != nil {
  1000  		return nil
  1001  	}
  1002  	if len(common) > 0 {
  1003  		f := m.GetField(common...)
  1004  		if f == nil {
  1005  			return nil
  1006  		}
  1007  		if f.Map() != nil {
  1008  			return f.Map().GetEdges(eid, nil, nil)
  1009  		}
  1010  		return nil
  1011  	}
  1012  
  1013  	var ea []*Edge
  1014  	for _, e := range m.Edges {
  1015  		if e.ID.Match(eid) {
  1016  			ea = append(ea, e)
  1017  		}
  1018  	}
  1019  	return ea
  1020  }
  1021  
  1022  func (m *Map) getEdges(eid *EdgeID, refctx *RefContext, gctx *globContext, ea *[]*Edge) error {
  1023  	eid, m, common, err := eid.resolve(m)
  1024  	if err != nil {
  1025  		return err
  1026  	}
  1027  
  1028  	if len(common) > 0 {
  1029  		commonKP := d2ast.MakeKeyPath(common)
  1030  		lastMatch := 0
  1031  		for i, el := range commonKP.Path {
  1032  			for j := lastMatch; j < len(refctx.Edge.Src.Path); j++ {
  1033  				realEl := refctx.Edge.Src.Path[j]
  1034  				if el.ScalarString() == realEl.ScalarString() {
  1035  					commonKP.Path[i] = realEl
  1036  					lastMatch += j + 1
  1037  				}
  1038  			}
  1039  		}
  1040  		fa, err := m.EnsureField(commonKP, nil, false, nil)
  1041  		if err != nil {
  1042  			return nil
  1043  		}
  1044  		for _, f := range fa {
  1045  			if _, ok := f.Composite.(*Array); ok {
  1046  				return d2parser.Errorf(refctx.Edge.Src, "cannot index into array")
  1047  			}
  1048  			if f.Map() == nil {
  1049  				f.Composite = &Map{
  1050  					parent: f,
  1051  				}
  1052  			}
  1053  			err = f.Map().getEdges(eid, refctx, gctx, ea)
  1054  			if err != nil {
  1055  				return err
  1056  			}
  1057  		}
  1058  		return nil
  1059  	}
  1060  
  1061  	srcFA, err := refctx.ScopeMap.EnsureField(refctx.Edge.Src, nil, false, nil)
  1062  	if err != nil {
  1063  		return err
  1064  	}
  1065  	dstFA, err := refctx.ScopeMap.EnsureField(refctx.Edge.Dst, nil, false, nil)
  1066  	if err != nil {
  1067  		return err
  1068  	}
  1069  
  1070  	for _, src := range srcFA {
  1071  		for _, dst := range dstFA {
  1072  			eid2 := eid.Copy()
  1073  			eid2.SrcPath = RelIDA(m, src)
  1074  			eid2.DstPath = RelIDA(m, dst)
  1075  
  1076  			ea2 := m.GetEdges(eid2, nil, nil)
  1077  			for _, e := range ea2 {
  1078  				if gctx != nil {
  1079  					var ks string
  1080  					if refctx.Key.HasTripleGlob() {
  1081  						ks = d2format.Format(d2ast.MakeKeyPath(IDA(e)))
  1082  					} else {
  1083  						ks = d2format.Format(d2ast.MakeKeyPath(BoardIDA(e)))
  1084  					}
  1085  					if _, ok := gctx.appliedEdges[ks]; ok {
  1086  						continue
  1087  					}
  1088  					gctx.appliedEdges[ks] = struct{}{}
  1089  				}
  1090  				*ea = append(*ea, ea2...)
  1091  			}
  1092  		}
  1093  	}
  1094  	return nil
  1095  }
  1096  
  1097  func (m *Map) CreateEdge(eid *EdgeID, refctx *RefContext, c *compiler) ([]*Edge, error) {
  1098  	var ea []*Edge
  1099  	var gctx *globContext
  1100  	if refctx != nil && refctx.Key.HasGlob() && c != nil {
  1101  		gctx = c.ensureGlobContext(refctx)
  1102  	}
  1103  	err := m.createEdge(eid, refctx, gctx, c, &ea)
  1104  	if len(ea) > 0 && c != nil && len(c.globRefContextStack) == 0 {
  1105  		for _, gctx2 := range c.globContexts() {
  1106  			old := c.lazyGlobBeingApplied
  1107  			c.lazyGlobBeingApplied = true
  1108  			c.compileKey(gctx2.refctx)
  1109  			c.lazyGlobBeingApplied = old
  1110  		}
  1111  	}
  1112  	return ea, err
  1113  }
  1114  
  1115  func (m *Map) createEdge(eid *EdgeID, refctx *RefContext, gctx *globContext, c *compiler, ea *[]*Edge) error {
  1116  	if ParentEdge(m) != nil {
  1117  		return d2parser.Errorf(refctx.Edge, "cannot create edge inside edge")
  1118  	}
  1119  
  1120  	eid, m, common, err := eid.resolve(m)
  1121  	if err != nil {
  1122  		return d2parser.Errorf(refctx.Edge, err.Error())
  1123  	}
  1124  	if len(common) > 0 {
  1125  		commonKP := d2ast.MakeKeyPath(common)
  1126  		lastMatch := 0
  1127  		for i, el := range commonKP.Path {
  1128  			for j := lastMatch; j < len(refctx.Edge.Src.Path); j++ {
  1129  				realEl := refctx.Edge.Src.Path[j]
  1130  				if el.ScalarString() == realEl.ScalarString() {
  1131  					commonKP.Path[i] = realEl
  1132  					lastMatch += j + 1
  1133  				}
  1134  			}
  1135  		}
  1136  		fa, err := m.EnsureField(commonKP, nil, true, c)
  1137  		if err != nil {
  1138  			return err
  1139  		}
  1140  		for _, f := range fa {
  1141  			if _, ok := f.Composite.(*Array); ok {
  1142  				return d2parser.Errorf(refctx.Edge.Src, "cannot index into array")
  1143  			}
  1144  			if f.Map() == nil {
  1145  				f.Composite = &Map{
  1146  					parent: f,
  1147  				}
  1148  			}
  1149  			err = f.Map().createEdge(eid, refctx, gctx, c, ea)
  1150  			if err != nil {
  1151  				return err
  1152  			}
  1153  		}
  1154  		return nil
  1155  	}
  1156  
  1157  	ij := findProhibitedEdgeKeyword(eid.SrcPath...)
  1158  	if ij != -1 {
  1159  		return d2parser.Errorf(refctx.Edge.Src.Path[ij].Unbox(), "reserved keywords are prohibited in edges")
  1160  	}
  1161  	ij = findBoardKeyword(eid.SrcPath...)
  1162  	if ij == len(eid.SrcPath)-1 {
  1163  		return d2parser.Errorf(refctx.Edge.Src.Path[ij].Unbox(), "edge with board keyword alone doesn't make sense")
  1164  	}
  1165  
  1166  	ij = findProhibitedEdgeKeyword(eid.DstPath...)
  1167  	if ij != -1 {
  1168  		return d2parser.Errorf(refctx.Edge.Dst.Path[ij].Unbox(), "reserved keywords are prohibited in edges")
  1169  	}
  1170  	ij = findBoardKeyword(eid.DstPath...)
  1171  	if ij == len(eid.DstPath)-1 {
  1172  		return d2parser.Errorf(refctx.Edge.Dst.Path[ij].Unbox(), "edge with board keyword alone doesn't make sense")
  1173  	}
  1174  
  1175  	srcFA, err := refctx.ScopeMap.EnsureField(refctx.Edge.Src, refctx, true, c)
  1176  	if err != nil {
  1177  		return err
  1178  	}
  1179  	dstFA, err := refctx.ScopeMap.EnsureField(refctx.Edge.Dst, refctx, true, c)
  1180  	if err != nil {
  1181  		return err
  1182  	}
  1183  
  1184  	for _, src := range srcFA {
  1185  		for _, dst := range dstFA {
  1186  			if src == dst && (refctx.Edge.Src.HasGlob() || refctx.Edge.Dst.HasGlob()) {
  1187  				// Globs do not make self edges.
  1188  				continue
  1189  			}
  1190  
  1191  			if refctx.Edge.Src.HasMultiGlob() {
  1192  				// If src has a double glob we only select leafs, those without children.
  1193  				if src.Map().IsContainer() {
  1194  					continue
  1195  				}
  1196  				if NodeBoardKind(src) != "" || ParentBoard(src) != ParentBoard(dst) {
  1197  					continue
  1198  				}
  1199  			}
  1200  			if refctx.Edge.Dst.HasMultiGlob() {
  1201  				// If dst has a double glob we only select leafs, those without children.
  1202  				if dst.Map().IsContainer() {
  1203  					continue
  1204  				}
  1205  				if NodeBoardKind(dst) != "" || ParentBoard(src) != ParentBoard(dst) {
  1206  					continue
  1207  				}
  1208  			}
  1209  
  1210  			eid2 := eid.Copy()
  1211  			eid2.SrcPath = RelIDA(m, src)
  1212  			eid2.DstPath = RelIDA(m, dst)
  1213  
  1214  			e, err := m.createEdge2(eid2, refctx, gctx, c, src, dst)
  1215  			if err != nil {
  1216  				return err
  1217  			}
  1218  			if e != nil {
  1219  				*ea = append(*ea, e)
  1220  			}
  1221  		}
  1222  	}
  1223  	return nil
  1224  }
  1225  
  1226  func (m *Map) createEdge2(eid *EdgeID, refctx *RefContext, gctx *globContext, c *compiler, src, dst *Field) (*Edge, error) {
  1227  	if NodeBoardKind(src) != "" {
  1228  		return nil, d2parser.Errorf(refctx.Edge.Src, "cannot create edges between boards")
  1229  	}
  1230  	if NodeBoardKind(dst) != "" {
  1231  		return nil, d2parser.Errorf(refctx.Edge.Dst, "cannot create edges between boards")
  1232  	}
  1233  	if ParentBoard(src) != ParentBoard(dst) {
  1234  		return nil, d2parser.Errorf(refctx.Edge, "cannot create edges between boards")
  1235  	}
  1236  
  1237  	eid.Index = nil
  1238  	eid.Glob = true
  1239  	ea := m.GetEdges(eid, nil, nil)
  1240  	index := len(ea)
  1241  	eid.Index = &index
  1242  	eid.Glob = false
  1243  	e := &Edge{
  1244  		parent: m,
  1245  		ID:     eid,
  1246  		References: []*EdgeReference{{
  1247  			Context_:       refctx,
  1248  			DueToGlob_:     len(c.globRefContextStack) > 0,
  1249  			DueToLazyGlob_: c.lazyGlobBeingApplied,
  1250  		}},
  1251  	}
  1252  
  1253  	if gctx != nil {
  1254  		var ks string
  1255  		// We only ever want to create one of the edge per glob so we filter without the edge index.
  1256  		e2 := e.Copy(e.Parent()).(*Edge)
  1257  		e2.ID = e2.ID.Copy()
  1258  		e2.ID.Index = nil
  1259  		if refctx.Key.HasTripleGlob() {
  1260  			ks = d2format.Format(d2ast.MakeKeyPath(IDA(e2)))
  1261  		} else {
  1262  			ks = d2format.Format(d2ast.MakeKeyPath(BoardIDA(e2)))
  1263  		}
  1264  		if _, ok := gctx.appliedEdges[ks]; ok {
  1265  			return nil, nil
  1266  		}
  1267  		gctx.appliedEdges[ks] = struct{}{}
  1268  	}
  1269  
  1270  	m.Edges = append(m.Edges, e)
  1271  
  1272  	return e, nil
  1273  }
  1274  
  1275  func (s *Scalar) AST() d2ast.Node {
  1276  	return s.Value
  1277  }
  1278  
  1279  func (f *Field) AST() d2ast.Node {
  1280  	k := &d2ast.Key{
  1281  		Key: &d2ast.KeyPath{
  1282  			Path: []*d2ast.StringBox{
  1283  				d2ast.MakeValueBox(d2ast.RawString(f.Name, true)).StringBox(),
  1284  			},
  1285  		},
  1286  	}
  1287  
  1288  	if f.Primary_ != nil {
  1289  		k.Primary = d2ast.MakeValueBox(f.Primary_.AST().(d2ast.Value)).ScalarBox()
  1290  	}
  1291  	if f.Composite != nil {
  1292  		k.Value = d2ast.MakeValueBox(f.Composite.AST().(d2ast.Value))
  1293  	}
  1294  
  1295  	return k
  1296  }
  1297  
  1298  func (e *Edge) AST() d2ast.Node {
  1299  	astEdge := &d2ast.Edge{}
  1300  
  1301  	astEdge.Src = d2ast.MakeKeyPath(e.ID.SrcPath)
  1302  	if e.ID.SrcArrow {
  1303  		astEdge.SrcArrow = "<"
  1304  	}
  1305  	astEdge.Dst = d2ast.MakeKeyPath(e.ID.DstPath)
  1306  	if e.ID.DstArrow {
  1307  		astEdge.DstArrow = ">"
  1308  	}
  1309  
  1310  	k := &d2ast.Key{
  1311  		Edges: []*d2ast.Edge{astEdge},
  1312  	}
  1313  
  1314  	if e.Primary_ != nil {
  1315  		k.Primary = d2ast.MakeValueBox(e.Primary_.AST().(d2ast.Value)).ScalarBox()
  1316  	}
  1317  	if e.Map_ != nil {
  1318  		k.Value = d2ast.MakeValueBox(e.Map_.AST().(*d2ast.Map))
  1319  	}
  1320  
  1321  	return k
  1322  }
  1323  
  1324  func (e *Edge) IDString() string {
  1325  	ast := e.AST().(*d2ast.Key)
  1326  	if e.ID.Index != nil {
  1327  		ast.EdgeIndex = &d2ast.EdgeIndex{
  1328  			Int: e.ID.Index,
  1329  		}
  1330  	}
  1331  	ast.Primary = d2ast.ScalarBox{}
  1332  	ast.Value = d2ast.ValueBox{}
  1333  	return d2format.Format(ast)
  1334  }
  1335  
  1336  func (a *Array) AST() d2ast.Node {
  1337  	if a == nil {
  1338  		return nil
  1339  	}
  1340  	astArray := &d2ast.Array{}
  1341  	for _, av := range a.Values {
  1342  		astArray.Nodes = append(astArray.Nodes, d2ast.MakeArrayNodeBox(av.AST().(d2ast.ArrayNode)))
  1343  	}
  1344  	return astArray
  1345  }
  1346  
  1347  func (m *Map) AST() d2ast.Node {
  1348  	if m == nil {
  1349  		return nil
  1350  	}
  1351  	astMap := &d2ast.Map{}
  1352  	if m.Root() {
  1353  		astMap.Range = d2ast.MakeRange(",0:0:0-1:0:0")
  1354  	} else {
  1355  		astMap.Range = d2ast.MakeRange(",1:0:0-2:0:0")
  1356  	}
  1357  	for _, f := range m.Fields {
  1358  		astMap.Nodes = append(astMap.Nodes, d2ast.MakeMapNodeBox(f.AST().(d2ast.MapNode)))
  1359  	}
  1360  	for _, e := range m.Edges {
  1361  		astMap.Nodes = append(astMap.Nodes, d2ast.MakeMapNodeBox(e.AST().(d2ast.MapNode)))
  1362  	}
  1363  	return astMap
  1364  }
  1365  
  1366  func (m *Map) appendFieldReferences(i int, kp *d2ast.KeyPath, refctx *RefContext, c *compiler) {
  1367  	sb := kp.Path[i]
  1368  	f := m.GetField(sb.Unbox().ScalarString())
  1369  	if f == nil {
  1370  		return
  1371  	}
  1372  
  1373  	f.References = append(f.References, &FieldReference{
  1374  		String:         sb.Unbox(),
  1375  		KeyPath:        kp,
  1376  		Context_:       refctx,
  1377  		DueToGlob_:     len(c.globRefContextStack) > 0,
  1378  		DueToLazyGlob_: c.lazyGlobBeingApplied,
  1379  	})
  1380  	if i+1 == len(kp.Path) {
  1381  		return
  1382  	}
  1383  	if f.Map() != nil {
  1384  		f.Map().appendFieldReferences(i+1, kp, refctx, c)
  1385  	}
  1386  }
  1387  
  1388  func RootMap(m *Map) *Map {
  1389  	if m.Root() {
  1390  		return m
  1391  	}
  1392  	return RootMap(ParentMap(m))
  1393  }
  1394  
  1395  func ParentMap(n Node) *Map {
  1396  	for {
  1397  		n = n.Parent()
  1398  		if n == nil {
  1399  			return nil
  1400  		}
  1401  		if m, ok := n.(*Map); ok {
  1402  			return m
  1403  		}
  1404  	}
  1405  }
  1406  
  1407  func ParentField(n Node) *Field {
  1408  	for {
  1409  		n = n.Parent()
  1410  		if n == nil {
  1411  			return nil
  1412  		}
  1413  		if f, ok := n.(*Field); ok {
  1414  			return f
  1415  		}
  1416  	}
  1417  }
  1418  
  1419  func IsVar(n Node) bool {
  1420  	for {
  1421  		if n == nil {
  1422  			return false
  1423  		}
  1424  		if NodeBoardKind(n) != "" {
  1425  			return false
  1426  		}
  1427  		if f, ok := n.(*Field); ok && f.Name == "vars" {
  1428  			return true
  1429  		}
  1430  		n = n.Parent()
  1431  	}
  1432  }
  1433  
  1434  func ParentBoard(n Node) Node {
  1435  	for {
  1436  		n = n.Parent()
  1437  		if n == nil {
  1438  			return nil
  1439  		}
  1440  		if NodeBoardKind(n) != "" {
  1441  			return n
  1442  		}
  1443  	}
  1444  }
  1445  
  1446  func ParentEdge(n Node) *Edge {
  1447  	for {
  1448  		n = n.Parent()
  1449  		if n == nil {
  1450  			return nil
  1451  		}
  1452  		if e, ok := n.(*Edge); ok {
  1453  			return e
  1454  		}
  1455  	}
  1456  }
  1457  
  1458  func ParentShape(n Node) string {
  1459  	for {
  1460  		f, ok := n.(*Field)
  1461  		if ok {
  1462  			if f.Map() != nil {
  1463  				shapef := f.Map().GetField("shape")
  1464  				if shapef != nil && shapef.Primary() != nil {
  1465  					return shapef.Primary().Value.ScalarString()
  1466  				}
  1467  			}
  1468  		}
  1469  		n = n.Parent()
  1470  		if n == nil {
  1471  			return ""
  1472  		}
  1473  	}
  1474  }
  1475  
  1476  func countUnderscores(p []string) int {
  1477  	for i, el := range p {
  1478  		if el != "_" {
  1479  			return i
  1480  		}
  1481  	}
  1482  	return 0
  1483  }
  1484  
  1485  func findBoardKeyword(ida ...string) int {
  1486  	for i := range ida {
  1487  		if _, ok := d2graph.BoardKeywords[ida[i]]; ok {
  1488  			return i
  1489  		}
  1490  	}
  1491  	return -1
  1492  }
  1493  
  1494  func findProhibitedEdgeKeyword(ida ...string) int {
  1495  	for i := range ida {
  1496  		if _, ok := d2graph.SimpleReservedKeywords[ida[i]]; ok {
  1497  			return i
  1498  		}
  1499  		if _, ok := d2graph.ReservedKeywordHolders[ida[i]]; ok {
  1500  			return i
  1501  		}
  1502  	}
  1503  	return -1
  1504  }
  1505  
  1506  func parentRef(n Node) Reference {
  1507  	f := ParentField(n)
  1508  	if f != nil {
  1509  		return f.LastRef()
  1510  	}
  1511  	e := ParentEdge(n)
  1512  	if e != nil {
  1513  		return e.LastRef()
  1514  	}
  1515  	return nil
  1516  }
  1517  
  1518  func parentPrimaryRef(n Node) Reference {
  1519  	f := ParentField(n)
  1520  	if f != nil {
  1521  		return f.LastPrimaryRef()
  1522  	}
  1523  	e := ParentEdge(n)
  1524  	if e != nil {
  1525  		return e.LastPrimaryRef()
  1526  	}
  1527  	return nil
  1528  }
  1529  
  1530  func parentPrimaryKey(n Node) *d2ast.Key {
  1531  	f := ParentField(n)
  1532  	if f != nil {
  1533  		return f.LastPrimaryKey()
  1534  	}
  1535  	e := ParentEdge(n)
  1536  	if e != nil {
  1537  		return e.LastPrimaryKey()
  1538  	}
  1539  	return nil
  1540  }
  1541  
  1542  // BoardIDA returns the absolute path to n from the nearest board root.
  1543  func BoardIDA(n Node) (ida []string) {
  1544  	for {
  1545  		switch n := n.(type) {
  1546  		case *Field:
  1547  			if n.Root() || NodeBoardKind(n) != "" {
  1548  				reverseIDA(ida)
  1549  				return ida
  1550  			}
  1551  			ida = append(ida, n.Name)
  1552  		case *Edge:
  1553  			ida = append(ida, n.IDString())
  1554  		}
  1555  		n = n.Parent()
  1556  		if n == nil {
  1557  			reverseIDA(ida)
  1558  			return ida
  1559  		}
  1560  	}
  1561  }
  1562  
  1563  // IDA returns the absolute path to n.
  1564  func IDA(n Node) (ida []string) {
  1565  	for {
  1566  		switch n := n.(type) {
  1567  		case *Field:
  1568  			ida = append(ida, n.Name)
  1569  			if n.Root() {
  1570  				reverseIDA(ida)
  1571  				return ida
  1572  			}
  1573  		case *Edge:
  1574  			ida = append(ida, n.IDString())
  1575  		}
  1576  		n = n.Parent()
  1577  		if n == nil {
  1578  			reverseIDA(ida)
  1579  			return ida
  1580  		}
  1581  	}
  1582  }
  1583  
  1584  // RelIDA returns the path to n relative to p.
  1585  func RelIDA(p, n Node) (ida []string) {
  1586  	for {
  1587  		switch n := n.(type) {
  1588  		case *Field:
  1589  			ida = append(ida, n.Name)
  1590  			if n.Root() {
  1591  				reverseIDA(ida)
  1592  				return ida
  1593  			}
  1594  		case *Edge:
  1595  			ida = append(ida, n.String())
  1596  		}
  1597  		n = n.Parent()
  1598  		f, fok := n.(*Field)
  1599  		e, eok := n.(*Edge)
  1600  		if n == nil || (fok && (f.Root() || f == p || f.Composite == p)) || (eok && (e == p || e.Map_ == p)) {
  1601  			reverseIDA(ida)
  1602  			return ida
  1603  		}
  1604  	}
  1605  }
  1606  
  1607  func reverseIDA(ida []string) {
  1608  	for i := 0; i < len(ida)/2; i++ {
  1609  		tmp := ida[i]
  1610  		ida[i] = ida[len(ida)-i-1]
  1611  		ida[len(ida)-i-1] = tmp
  1612  	}
  1613  }
  1614  
  1615  func (f *Field) Equal(n2 Node) bool {
  1616  	f2 := n2.(*Field)
  1617  
  1618  	if f.Name != f2.Name {
  1619  		return false
  1620  	}
  1621  	if !f.Primary_.Equal(f2.Primary_) {
  1622  		return false
  1623  	}
  1624  	if !f.Composite.Equal(f2.Composite) {
  1625  		return false
  1626  	}
  1627  	return true
  1628  }
  1629  
  1630  func (e *Edge) Equal(n2 Node) bool {
  1631  	e2 := n2.(*Edge)
  1632  
  1633  	if !e.ID.Match(e2.ID) {
  1634  		return false
  1635  	}
  1636  	if !e.Primary_.Equal(e2.Primary_) {
  1637  		return false
  1638  	}
  1639  	if !e.Map_.Equal(e2.Map_) {
  1640  		return false
  1641  	}
  1642  	return true
  1643  }
  1644  
  1645  func (a *Array) Equal(n2 Node) bool {
  1646  	a2 := n2.(*Array)
  1647  
  1648  	if len(a.Values) != len(a2.Values) {
  1649  		return false
  1650  	}
  1651  
  1652  	for i := range a.Values {
  1653  		if !a.Values[i].Equal(a2.Values[i]) {
  1654  			return false
  1655  		}
  1656  	}
  1657  
  1658  	return true
  1659  }
  1660  
  1661  func (m *Map) Equal(n2 Node) bool {
  1662  	m2 := n2.(*Map)
  1663  
  1664  	if len(m.Fields) != len(m2.Fields) {
  1665  		return false
  1666  	}
  1667  	if len(m.Edges) != len(m2.Edges) {
  1668  		return false
  1669  	}
  1670  
  1671  	for i := range m.Fields {
  1672  		if !m.Fields[i].Equal(m2.Fields[i]) {
  1673  			return false
  1674  		}
  1675  	}
  1676  	for i := range m.Edges {
  1677  		if !m.Edges[i].Equal(m2.Edges[i]) {
  1678  			return false
  1679  		}
  1680  	}
  1681  
  1682  	return true
  1683  }
  1684  
  1685  func (m *Map) InClass(key *d2ast.Key) bool {
  1686  	classes := m.Map().GetField("classes")
  1687  	if classes == nil || classes.Map() == nil {
  1688  		return false
  1689  	}
  1690  
  1691  	for _, class := range classes.Map().Fields {
  1692  		if class.Map() == nil {
  1693  			continue
  1694  		}
  1695  		classF := class.Map().GetField(key.Key.IDA()...)
  1696  		if classF == nil {
  1697  			continue
  1698  		}
  1699  
  1700  		for _, ref := range classF.References {
  1701  			if ref.Context_.Key == key {
  1702  				return true
  1703  			}
  1704  		}
  1705  	}
  1706  	return false
  1707  }
  1708  
  1709  func (m *Map) IsClass() bool {
  1710  	parentBoard := ParentBoard(m)
  1711  	if parentBoard.Map() == nil {
  1712  		return false
  1713  	}
  1714  	classes := parentBoard.Map().GetField("classes")
  1715  	if classes == nil || classes.Map() == nil {
  1716  		return false
  1717  	}
  1718  
  1719  	for _, class := range classes.Map().Fields {
  1720  		if class.Map() == m {
  1721  			return true
  1722  		}
  1723  	}
  1724  	return false
  1725  }
  1726  

View as plain text